Галогенный эквивалент цикла

Question

Я пытаюсь реализовать алгоритм преобразования расстояния Мейстера в Halide. Я уже переписал 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 
} 

Есть любой галоидный способ заменить этот цикл? Сейчас единственное решение я пришел до сих пор является 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 программ Turing-complete; без них мы всегда можем анализировать границы ваших циклов, но мы, они, сталкиваемся с проблемой остановки.

Существует такой люк-побег для такого рода вещей: вы можете вызвать внешние функции (реализованные на C или что-то еще) изнутри трубопровода Halide. Интерфейс к функции extern выглядит так же, как интерфейс к скомпилированному конвейеру (он принимает скалярные и буферные аргументы, причем конечным буфером является вывод, а если он вызывается с нулевыми буферами, он должен вычислять оценки, требуемые от его входов с учетом границ с просьбой о его выходе). Ознакомьтесь с тестовыми программами extern_* для некоторых примеров, например, https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp. Быстро взглянув на ваш код, я считаю, что он должен быть легко реализован на внешнем этапе с использованием кода C, который у вас уже есть.