Halide - while while loop

Question

我正试图在Halide中实现Meijster距离变换算法。我已经将this code改写为C++（使用openCV）并且工作正常。关于这种算法的文章是here。现在我的卤化物代码是完成50％ - 第一阶段工作正常，现在我有问题，第2阶段（在链接的代码扫描3）（简体）是这样的：

//g is 2 dimensional cv::Mat (something like array) - result of previous stage 
// m is g.width and n is g.height 
int(*functionF)(int x, int i, int g_i) = EDT_f; 
int(*functionSep)(int i, int u, int g_i, int g_u, int max_value) = EDT_Sep; 
cv::Mat dt = cv::Mat(n, m, CV_32SC1); 
int* s = new int[m]; 
int* t = new int[m]; 
int q = 0, w; 

for (int y = 0; y<n; y++) 
{ 
    q = 0; 
    s[0] = 0; 
    t[0] = 0; 

    // Scan 3 
    for (int u = 1; u<m; u++) 
    { 
    //how can i replace this loop: 
     while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u))) 
      q--; 
     //some operations which might change value of q, s[] and t[] 
    } 
    // Scan 4 - not important here 
} 

有任何卤化物友好方式来取代这个while循环？现在唯一的解决办法，到目前为止我来是smething像这样（没有测试过）：

Expr calculateQ(Expr currentQValue, Expr y, Func t, Func s, Func g) 
{ 
    //while (q >= 0 && functionF(t[q], s[q], g.at<int>(y, s[q])) > functionF(t[q], u, g.at<int>(y, u))) 
     //q--; 
    return select(currentQValue >= 0 && functionF(t[q], s[q], g[s[q], y]) > functionF(t[q], u, g[u, y]), calculateQ(currentQValue - 1, y, t, s, g), currentQValue); 
} 

但即使这会的工作，最有可能的卤化物将试图评估选择这两个值检查条件之前递归会使其非常缓慢。

如果没有办法实现while Halide循环有什么方法可以在Halide中使用代码的一部分？任何其他想法？

Answer 1

你说得没错，如何表达一个动态终止（while）循环 - 他们不可能在纯粹的Halide中表现出来！这可能会在（无限期的，长期的）未来发生变化，但是增加这些可以使循环Halide程序图灵完成;没有他们，我们总是可以分析你的循环的边界，但是我们他们，我们会面临停滞的问题。

尽管有这样的事情的逃生舱口盖：你可以从Halide管道内调用外部函数（用C或其他任何东西实现）。 extern函数的接口看起来与编译管道的接口相同（它需要标量和缓冲区参数，最终的缓冲区是输出，如果使用空缓冲区调用，它必须计算其输入所需的边界，给定边界要求输出）。查看extern_*测试程序的一些示例，例如https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp。快速浏览你的代码，我相信它应该很容易在extern阶段使用你已经拥有的C代码来实现。