Recursive bounds inference can produce incorrect results in define_extern usage

[steven-johnson]

This is complicated to explain, so bear with me.

It's legal in Halide to have recursive bounds expressions for inputs to a Func; this can happen either explicitly, e.g.:

  in.set_extent(0, ((in.extent(0)+1)/2)*2)

or implicitly (e.g., as a result of using BoundaryConditions in the function definitions.

Unfortunately, when used in a multi-stage pipeline of realized functions (connected via define_extern), recursive bounds query expressions aren't always evaluated properly; in some cases, this can lead to pathological memory usage; in others, it can produce incorrect output.

I've attached an example of incorrect-output produced by this approach; in a nutshell, we have a toplevel pipeline that calls two define_extern()'ed functions; the "middle" function uses a BoundaryCondition that produces a recursive boundary condition for its input; when called in this pipeline, it ends up producing an "input required" that is always 1x1 pixel, regardless of the actual input size. (This basically means that all but that pixel in the output is essentially uninitialized).

This is a perplexing problem, as I don't know what the right answer is; in other fora, it's been suggested that the right way to handle bounds-query logic is to iterate until there's a stable answer, but this isn't what currently happens with define_extern() bounds queries, and even if it was, it's not clear whether it could be bounded effectively for all general cases.

bad_recursive_bounds_query.cpp.txt

[zvookin]

I'm not convinced a recursive definition is really what the alignment case
means. I believe the intent of:
in.set_extent(0, ((in.extent(0)+1)/2)*2)
is to say "the extent of the zeroth dimension must be a multiple of 2." In
bounds query mode, I would expect this to mean that the bounds should be
inferred via normal logic and then rounded up to a multiple of 2. It is not
clear to me how that happens and it is certainly a bug if this results in
the bounds query simply taking the input passed in for that extent in the
query, rounding it up to a multiple of 2 and returning that. Perhaps all
the bounds are merged, but if that is the case, then that expression does
not actually access the extent passed in to the bounds query. Rather it
access the bounds inferred by the rest of the bounds inference algorithm.

The more I think about this the more I feel it should be an error to access
the bounds information in a buffer while computing bounds inference for
that buffer.

If we do really need an iterative algorithm, then the initial values used
for inference in define_extern pipelines made by Halide seem fairly
critical.

-Z-

On Thu, Jan 14, 2016 at 3:08 PM, Steven Johnson notifications@github.com
wrote:

This is complicated to explain, so bear with me.

It's legal in Halide to have recursive bounds expressions for inputs to a
Func; this can happen either explicitly, e.g.:

in.set_extent(0, ((in.extent(0)+1)/2)*2)

or implicitly (e.g., as a result of using BoundaryConditions in the
function definitions.

Unfortunately, when used in a multi-stage pipeline of realized functions
(connected via define_extern), recursive bounds query expressions aren't
always evaluated properly; in some cases, this can lead to pathological
memory usage; in others, it can produce incorrect output.

I've attached an example of incorrect-output produced by this approach; in
a nutshell, we have a toplevel pipeline that calls two define_extern()'ed
functions; the "middle" function uses a BoundaryCondition that produces a
recursive boundary condition for its input; when called in this pipeline,
it ends up producing an "input required" that is always 1x1 pixel,
regardless of the actual input size. (This basically means that all but
that pixel in the output is essentially uninitialized).

This is a perplexing problem, as I don't know what the right answer is; in
other fora, it's been suggested that the right way to handle bounds-query
logic is to iterate until there's a stable answer, but this isn't what
currently happens with define_extern() bounds queries, and even if it was,
it's not clear whether it could be bounded effectively for all general
cases.

bad_recursive_bounds_query.cpp.txt
https://github.com/halide/Halide/files/91131/bad_recursive_bounds_query.cpp.txt

—
Reply to this email directly or view it on GitHub
#1007.

[abadams]

Bounds querying can't give a sensible reply when it doesn't care what the
size of the input is (e.g. because it has a boundary condition that kicks
in at whatever its size is). So it just asks for a 1x1 input at position 0,
0. It might be possible to get it to throw an error instead, but I don't
think it's trivial to do so. If the middle pipeline really needs a boundary
condition, I'd suggest passing the correct boundary locations as separate
Params instead of using the properties of the ImageParam.

On Thu, Jan 14, 2016 at 3:16 PM, Zalman Stern notifications@github.com
wrote:

I'm not convinced a recursive definition is really what the alignment case
means. I believe the intent of:
in.set_extent(0, ((in.extent(0)+1)/2)*2)
is to say "the extent of the zeroth dimension must be a multiple of 2." In
bounds query mode, I would expect this to mean that the bounds should be
inferred via normal logic and then rounded up to a multiple of 2. It is not
clear to me how that happens and it is certainly a bug if this results in
the bounds query simply taking the input passed in for that extent in the
query, rounding it up to a multiple of 2 and returning that. Perhaps all
the bounds are merged, but if that is the case, then that expression does
not actually access the extent passed in to the bounds query. Rather it
access the bounds inferred by the rest of the bounds inference algorithm.

The more I think about this the more I feel it should be an error to access
the bounds information in a buffer while computing bounds inference for
that buffer.

If we do really need an iterative algorithm, then the initial values used
for inference in define_extern pipelines made by Halide seem fairly
critical.

-Z-

On Thu, Jan 14, 2016 at 3:08 PM, Steven Johnson notifications@github.com
wrote:

This is complicated to explain, so bear with me.

It's legal in Halide to have recursive bounds expressions for inputs to a
Func; this can happen either explicitly, e.g.:

in.set_extent(0, ((in.extent(0)+1)/2)*2)

or implicitly (e.g., as a result of using BoundaryConditions in the
function definitions.

Unfortunately, when used in a multi-stage pipeline of realized functions
(connected via define_extern), recursive bounds query expressions aren't
always evaluated properly; in some cases, this can lead to pathological
memory usage; in others, it can produce incorrect output.

I've attached an example of incorrect-output produced by this approach;
in
a nutshell, we have a toplevel pipeline that calls two define_extern()'ed
functions; the "middle" function uses a BoundaryCondition that produces a
recursive boundary condition for its input; when called in this pipeline,
it ends up producing an "input required" that is always 1x1 pixel,
regardless of the actual input size. (This basically means that all but
that pixel in the output is essentially uninitialized).

This is a perplexing problem, as I don't know what the right answer is;
in
other fora, it's been suggested that the right way to handle bounds-query
logic is to iterate until there's a stable answer, but this isn't what
currently happens with define_extern() bounds queries, and even if it
was,
it's not clear whether it could be bounded effectively for all general
cases.

bad_recursive_bounds_query.cpp.txt
<
https://github.com/halide/Halide/files/91131/bad_recursive_bounds_query.cpp.txt

—
Reply to this email directly or view it on GitHub
#1007.

—
Reply to this email directly or view it on GitHub
#1007 (comment).

[zvookin]

I'd want this to be a compile time error, not runtime.

On Thu, Jan 14, 2016 at 3:45 PM, Andrew Adams notifications@github.com
wrote:

Bounds querying can't give a sensible reply when it doesn't care what the
size of the input is (e.g. because it has a boundary condition that kicks
in at whatever its size is). So it just asks for a 1x1 input at position 0,
0. It might be possible to get it to throw an error instead, but I don't
think it's trivial to do so. If the middle pipeline really needs a boundary
condition, I'd suggest passing the correct boundary locations as separate
Params instead of using the properties of the ImageParam.

On Thu, Jan 14, 2016 at 3:16 PM, Zalman Stern notifications@github.com
wrote:

I'm not convinced a recursive definition is really what the alignment
case
means. I believe the intent of:
in.set_extent(0, ((in.extent(0)+1)/2)*2)
is to say "the extent of the zeroth dimension must be a multiple of 2."
In
bounds query mode, I would expect this to mean that the bounds should be
inferred via normal logic and then rounded up to a multiple of 2. It is
not
clear to me how that happens and it is certainly a bug if this results in
the bounds query simply taking the input passed in for that extent in the
query, rounding it up to a multiple of 2 and returning that. Perhaps all
the bounds are merged, but if that is the case, then that expression does
not actually access the extent passed in to the bounds query. Rather it
access the bounds inferred by the rest of the bounds inference algorithm.

The more I think about this the more I feel it should be an error to
access
the bounds information in a buffer while computing bounds inference for
that buffer.

If we do really need an iterative algorithm, then the initial values used
for inference in define_extern pipelines made by Halide seem fairly
critical.

-Z-

On Thu, Jan 14, 2016 at 3:08 PM, Steven Johnson <
notifications@github.com>
wrote:

This is complicated to explain, so bear with me.

It's legal in Halide to have recursive bounds expressions for inputs
to a
Func; this can happen either explicitly, e.g.:

in.set_extent(0, ((in.extent(0)+1)/2)*2)

or implicitly (e.g., as a result of using BoundaryConditions in the
function definitions.

Unfortunately, when used in a multi-stage pipeline of realized
functions
(connected via define_extern), recursive bounds query expressions
aren't
always evaluated properly; in some cases, this can lead to pathological
memory usage; in others, it can produce incorrect output.

I've attached an example of incorrect-output produced by this approach;
in
a nutshell, we have a toplevel pipeline that calls two
define_extern()'ed
functions; the "middle" function uses a BoundaryCondition that
produces a
recursive boundary condition for its input; when called in this
pipeline,
it ends up producing an "input required" that is always 1x1 pixel,
regardless of the actual input size. (This basically means that all but
that pixel in the output is essentially uninitialized).

This is a perplexing problem, as I don't know what the right answer is;
in
other fora, it's been suggested that the right way to handle
bounds-query
logic is to iterate until there's a stable answer, but this isn't what
currently happens with define_extern() bounds queries, and even if it
was,
it's not clear whether it could be bounded effectively for all general
cases.

bad_recursive_bounds_query.cpp.txt
<

https://github.com/halide/Halide/files/91131/bad_recursive_bounds_query.cpp.txt

—
Reply to this email directly or view it on GitHub
#1007.

—
Reply to this email directly or view it on GitHub
#1007 (comment).

—
Reply to this email directly or view it on GitHub
#1007 (comment).

[steven-johnson]

I'd even settle for a runtime error; the current situation (in which you
can quietly get incorrect results) is really problematic.

On Thu, Jan 14, 2016 at 3:55 PM, Zalman Stern notifications@github.com
wrote:

I'd want this to be a compile time error, not runtime.

On Thu, Jan 14, 2016 at 3:45 PM, Andrew Adams notifications@github.com
wrote:

Bounds querying can't give a sensible reply when it doesn't care what the
size of the input is (e.g. because it has a boundary condition that kicks
in at whatever its size is). So it just asks for a 1x1 input at position
0,
0. It might be possible to get it to throw an error instead, but I don't
think it's trivial to do so. If the middle pipeline really needs a
boundary
condition, I'd suggest passing the correct boundary locations as separate
Params instead of using the properties of the ImageParam.

On Thu, Jan 14, 2016 at 3:16 PM, Zalman Stern notifications@github.com
wrote:

I'm not convinced a recursive definition is really what the alignment
case
means. I believe the intent of:
in.set_extent(0, ((in.extent(0)+1)/2)*2)
is to say "the extent of the zeroth dimension must be a multiple of 2."
In
bounds query mode, I would expect this to mean that the bounds should
be
inferred via normal logic and then rounded up to a multiple of 2. It is
not
clear to me how that happens and it is certainly a bug if this results
in
the bounds query simply taking the input passed in for that extent in
the
query, rounding it up to a multiple of 2 and returning that. Perhaps
all
the bounds are merged, but if that is the case, then that expression
does
not actually access the extent passed in to the bounds query. Rather it
access the bounds inferred by the rest of the bounds inference
algorithm.

The more I think about this the more I feel it should be an error to
access
the bounds information in a buffer while computing bounds inference for
that buffer.

If we do really need an iterative algorithm, then the initial values
used
for inference in define_extern pipelines made by Halide seem fairly
critical.

-Z-

On Thu, Jan 14, 2016 at 3:08 PM, Steven Johnson <
notifications@github.com>
wrote:

This is complicated to explain, so bear with me.

It's legal in Halide to have recursive bounds expressions for inputs
to a
Func; this can happen either explicitly, e.g.:

in.set_extent(0, ((in.extent(0)+1)/2)*2)

or implicitly (e.g., as a result of using BoundaryConditions in the
function definitions.

Unfortunately, when used in a multi-stage pipeline of realized
functions
(connected via define_extern), recursive bounds query expressions
aren't
always evaluated properly; in some cases, this can lead to
pathological
memory usage; in others, it can produce incorrect output.

I've attached an example of incorrect-output produced by this
approach;
in
a nutshell, we have a toplevel pipeline that calls two
define_extern()'ed
functions; the "middle" function uses a BoundaryCondition that
produces a
recursive boundary condition for its input; when called in this
pipeline,
it ends up producing an "input required" that is always 1x1 pixel,
regardless of the actual input size. (This basically means that all
but
that pixel in the output is essentially uninitialized).

This is a perplexing problem, as I don't know what the right answer
is;
in
other fora, it's been suggested that the right way to handle
bounds-query
logic is to iterate until there's a stable answer, but this isn't
what
currently happens with define_extern() bounds queries, and even if it
was,
it's not clear whether it could be bounded effectively for all
general
cases.

bad_recursive_bounds_query.cpp.txt
<

https://github.com/halide/Halide/files/91131/bad_recursive_bounds_query.cpp.txt

—
Reply to this email directly or view it on GitHub
#1007.

—
Reply to this email directly or view it on GitHub
#1007 (comment).

—
Reply to this email directly or view it on GitHub
#1007 (comment).

—
Reply to this email directly or view it on GitHub
#1007 (comment).

[abadams]

The problem is when a pipeline converts a Func (which does not have well-defined bounds) to an ImageParam (which does have well-defined bounds) by passing it as an argument in an extern stage call, and then that extern stage uses the bounds in its algorithm. Using it in the schedule (e.g. with constraints) should be OK.

We could try to engineer linker errors, or jam stuff into the metadata that we check at runtime, but I'm having trouble with the transitive case: Consider the case where pipeline A computes a Func in tiles and passes it as an input to pipeline B, which passes it through to pipeline C, which depends on its bounds. A would ask B somehow whether it's OK to use a Func for that input. B doesn't know, because it depends on what C is doing, so it asks C in turn.

Sounds a lot like the existing bounds querying infrastructure.

Hrm. Maybe we should just throw a runtime error on any bounds queries to imageparams where the algorithm depends on their size - i.e. assert that the host field is not null for any such imageparam. Would that solve it? True input images will never have a non-null host pointer, no matter how many extern stages deep we are, so it's OK to depend on their bounds anywhere.

[steven-johnson]

Yeah, good point. I don't know what the right answer is yet.

After further consideration, I realized that my characterizing these results as "incorrect" may not be fair, but the results are certainly wildly different from my expectations -- in the original case that led to this issue, I was getting "correct" results but at something like 100x the necessary memory usage.

I suspect that further work on the code that led me to file this issue will help inform how the situation can be improved; I'll update this issue as appropriate.

Re: "assert that the host field is not null for any such imageparam. Would that solve it?" -- I can't think of a counterexample right now, but my brain is still spinning up for the week. Would be interesting to prototype a patch that does so and see what breaks.

[abadams]

Try the branch no_bounds_query_when_bounds_used