c++ - single - Halide-while while equivalent

tensorflow python opencv

Question

Estoy tratando de implementar el algoritmo de transformación de distancia Meijster en Halide. Ya reescribí este código en C ++ (usando openCV) y funciona bien. El documento sobre este algoritmo está aquí . En este momento mi código de haluro está completo al 50% - la primera fase funciona bien, ahora tengo un problema con la fase 2 (escaneo 3 en el código vinculado) que (simplificado) se ve así:

//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
}

¿Hay alguna forma amigable de haluro para reemplazar este ciclo while? En este momento, la única solución que he llegado hasta ahora es similar a esto (aún no probado):

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);
}

pero incluso si esto funciona, lo más probable es que halide intente evaluar ambos valores de select antes de verificar la condición y la recursividad lo hará muy lento.

Si no hay forma de implementar while loop en Halide, ¿hay alguna forma de usar alguna parte de tu código dentro de Halide? ¿Alguna otra idea?

Answer 1

Tiene razón al señalar que no es obvio cómo expresar un ciclo de terminación dinámica (while): ¡no es posible expresarlo en Halide puro en este momento! Esto puede cambiar en el futuro (indefinido, a largo plazo) pero agregar estos haría que los programas de Halide de bucle sean completos. sin ellos, siempre podemos analizar los límites de sus bucles, pero nosotros, enfrentaríamos el problema de detenerse.

Sin embargo, hay una ventana de escape para exactamente este tipo de cosas: puede llamar a funciones externas (implementadas en C o cualquier otra cosa) desde dentro de una tubería de Halide. La interfaz a una función externa tiene el mismo aspecto que la interfaz a una canalización compilada (toma argumentos escalares y de buffer, siendo el último buffer el resultado, y si se llama con buffers nulos debe calcular los límites requeridos de sus entradas dados los límites solicitado de su salida). Consulte los programas de prueba extern_* para ver algunos ejemplos, por ejemplo, https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp . Echando un vistazo rápido a su código, creo que debería ser fácilmente implementable en una etapa externa utilizando el código C que ya tiene.