recursion with a function of the function

[palindromoroz]

Hi,

I know recursive calls are not the strong point of Halide. You can still make recursive IIR filters for example:

iir(0) = 0
RDom rx(1, N-1);
iir(rx) = (1 - alpha)*iir(rx - 1) + alpha*in(rx);

Now I had hopes I could do implement "Semi global matching" which requires recursive computation. I now need argmin in the recursion. Something like (just dummy example code here):

RDom rd(0,D)
L(rx,d)= C(rx,d) + argmin(rd,L(rx-1,rd)) ...

Since argmin is a function and can not be written as an expression this is not allowed. L is already consumed by the argmin and can not be used to define the recursion. I do not see any option how to implement this nicely in Halide except writing it out explicitly in a loop and generating N function updates.

I believe all the dynamic programming type of algorithms will have the same problem.

[abadams]

I have come to the same conclusion in the past with a very similar algorithm (patchmatch). I do not currently have any good answer for this :(

On Fri, Mar 31, 2017 at 5:30 AM, Zoran Zivkovic notifications@github.com wrote:

Hi,

I know recursive calls are not the strong point of Halide. You can still make recursive IIR filters for example:

iir(0) = 0 RDom rx(1, N-1); iir(rx) = (1 - alpha)iir(rx - 1) + alphain(rx);

Now I had hopes I could do implement "Semi global matching" which requires recursive computation. I now need argmin in the recursion. Something like (just dummy example code here):

RDom rd(0,D) L(rx,d)= C(rx,d) + argmin(rd,L(rx-1,rd)) ...

Since argmin is a function and can not be written as an expression this is not allowed. L is already consumed by the argmin and can not be used to define the recursion. I do not see any option how to implement this nicely in Halide except writing it out explicitly in a loop and generating N function updates.

I believe all the dynamic programming type of algorithms will have the same problem.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/halide/Halide/issues/1965, or mute the thread https://github.com/notifications/unsubscribe-auth/AAfdRgez_H_VV5yXijxvArY02prGFqw5ks5rrPHzgaJpZM4Mvm30 .

[palindromoroz]

I hope somebody will come with a cool solution that still keeps all the current goodies. It seems to me as something that could have a major influence on the wide use of Halide.

[SanderVocke]

Just a question, @abadams: is this a limitation of the Halide language's principles (e.g. is it fundamentally incompatible with the intent of the scheduling directives that exist), or just of the current Halide compiler?

[zvookin]

Andrew is the expert here, but two issues with expanding the computational power of the Halide language are:

1) Halide has to be able to do bounds inference through the computation. While this is already not completely solvable, the cases where it fails need to remain rare and easy to fix via additional annotation. The annotations often turn into asserts so they have to be hoisted in some fashion otherwise guaranteeing correctness comes at the expense of performance.

2) As computations become more general, there are tricky problems in figuring out how to run them on parallel hardware efficiently, or even at all. GPU hardware is getting more sophisticated and modern SIMT GPUs have quite a lot of interesting support for dynamic behavior in code, but making that available through scheduling is non-trivial. It is also likely hard to make the code fast across different hardware with a single algorithm.

As this sort of thing is very much relevant to problem domains Halide wants to cover, such as vision algorithms, it is something we'd like to address. But just extending the high-level language to allow arbitrary compute is tough. RecFilter is one of my favorite pieces of work around the second issue above.

-Z-

On Tue, Apr 4, 2017 at 2:58 AM, Sander Vocke notifications@github.com wrote:

Just a question: is this a limitation of the Halide language's principles (e.g. is it fundamentally incompatible with the intent of the scheduling directives that exist), or just of the current Halide compiler?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/halide/Halide/issues/1965#issuecomment-291452666, or mute the thread https://github.com/notifications/unsubscribe-auth/ABbqFMtrjRwULlob_THQrM09RgUsXUByks5rshQ1gaJpZM4Mvm30 .

[palindromoroz]

In general case it is probably not possible to do the bound inference. In the particular case of the Semi Global Matching algorithm, the argmax of the previous result is just added to the current result so it seems to me no issue with the bounds and no dynamic behaviour. Would be nice to have some work-around for such cases. Not sure how "such cases" could be defined. For example if you could somehow restrict the use of the function value in some way.