ハライド - whileループの等価物

Question

私はハイドレーデスでMeijster距離変換アルゴリズムを実装しようとしています。私はすでにopenCVを使ってC++にthis codeを書き直しました。うまくいきました。このアルゴリズムに関する論文は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 
} 

がありますany ハライドフレンドリーこの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); 
} 

それでも、これは動作する場合、最も可能性の高いハロゲン化物は、条件をチェックする前に選択の両方の値を評価しようとします再帰は非常に遅くなります。

Halideでwhileループを実装する方法がない場合、Halideの内部でコードの一部を使用する方法はありますか？他のアイデア？

Answer 1

あなたは、動的終了（while）ループを表現する方法が明白ではないことに注意してください。これは純粋なハライドでは表現できません。これは、（不定期、長期的な）将来変化する可能性がありますが、これらを追加するとHalideのプログラムチューリングが完了します。それがなければ、ループの境界をいつも分析することができますが、私たちは、停止問題に直面します。

ハイドライドパイプラインの内部から外部関数（C言語などで実装されています）を呼び出すことができます。 extern関数へのインタフェースは、コンパイルされたパイプラインへのインタフェースと同じように見えます（スカラー引数とバッファ引数を取ります。最後のバッファは出力となり、NULLバッファで呼び出された場合は、その出力を要求した）。いくつかの例についてはextern_*のテストプログラムをチェックしてください（例：https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp）。あなたのコードを素早く見て、私はあなたがすでに持っているCコードを使って外部ステージで簡単に実装できるはずだと信じています。