Dừng - trong khi vòng lặp tương đương

Question

Tôi đang cố gắng triển khai thuật toán biến đổi khoảng cách Meijster trong Halide. Tôi đã viết lại this code thành C++ (sử dụng openCV) và nó hoạt động tốt. Bài báo về thuật toán này là here. Ngay bây giờ đang halogen của tôi là 50% hoàn thành - giai đoạn đầu tiên là làm việc tốt, vấn đề bây giờ tôi đã có với giai đoạn 2 (quét 3 trong các mã liên kết) mà (giản thể) trông như thế này:

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

Có bất kỳ halide-friendly cách nào để thay thế vòng lặp while này? Ngay bây giờ là giải pháp duy nhất tôi đã đi cho đến nay được smething như thế này (không được thử nghiệm chưa):

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

nhưng ngay cả nếu điều này sẽ làm việc, có khả năng nhất halogen sẽ cố gắng để đánh giá cả hai giá trị của chọn trước khi kiểm tra điều kiện và đệ quy sẽ làm cho nó rất chậm.

Nếu không có cách nào để triển khai trong khi vòng lặp trong Halide thì có cách nào để chỉ sử dụng một phần mã của bạn bên trong Halide không? Bất kỳ ý tưởng nào khác?

Answer 1

Bạn phải lưu ý rằng không rõ ràng cách thể hiện vòng lặp kết thúc động (trong khi) — chúng không thể thể hiện trong Halide thuần túy ngay bây giờ! Điều này có thể thay đổi trong tương lai (vô hạn, dài hạn) nhưng việc thêm vào đó sẽ làm cho các chương trình Halide lặp lại Turing-complete; không có chúng, chúng tôi luôn có thể phân tích các giới hạn của các vòng lặp của bạn, nhưng chúng tôi, chúng tôi sẽ đối mặt với vấn đề dừng lại.

Có một lối thoát hiểm cho chính xác loại điều này, mặc dù: bạn có thể gọi các chức năng bên ngoài (được triển khai trong C hoặc bất kỳ thứ gì khác) từ bên trong đường ống Halide. Giao diện cho một hàm bên ngoài trông giống như giao diện cho một đường dẫn biên dịch (nó lấy các đối số vô hướng và đệm, với bộ đệm cuối cùng là đầu ra, và nếu được gọi với các bộ đệm rỗng, nó phải tính các giới hạn yêu cầu của các đầu vào của nó. yêu cầu đầu ra của nó). Xem các chương trình thử nghiệm extern_* đối với một số ví dụ, ví dụ: https://github.com/halide/Halide/blob/master/test/correctness/extern_stage.cpp. Xem nhanh mã của bạn, tôi tin rằng nó nên dễ dàng triển khai trong một giai đoạn bên ngoài bằng cách sử dụng mã C bạn đã có.