Search code examples
halide

Having problems with scheduling


I am trying to lower the execution time of my erosion function and the execution is actually slower when I try to divide the problem with tiling as shown in picture:

erosion time differences

my code without any scheduling is:

Halide::Image<uint8_t> erode(Halide::Image<uint8_t> input, int dimension) {
Halide::Var x("x"), y("y");
Halide::Image<uint8_t> output;
Halide::Func limit("limit"), e("e");
limit = Halide::BoundaryConditions::repeat_edge(input);
Halide::RDom r(dimension*-1 / 2, dimension, dimension*-1 / 2, dimension);
e(x, y) = limit(x, y);
e(x, y) = Halide::min(limit(x + r.x, y + r.y), e(x, y));
output = e.realize(input.width(), input.height());
return output;
}

my code with a tiling attempt (I tried to use the example, shown in the tutorial):

Halide::Image<uint8_t> erodeTiling(Halide::Image<uint8_t> input, int dimension) {
Halide::Var x("x"), y("y"), x_outer, x_inner, y_outer, y_inner, tile_index;
Halide::Image<uint8_t> output;
Halide::Func limit("limit"), e("e");
limit = Halide::BoundaryConditions::repeat_edge(input);
Halide::RDom r(dimension*-1 / 2, dimension, dimension*-1 / 2, dimension);
e(x, y) = limit(x, y);
e(x, y) = Halide::min(limit(x + r.x, y + r.y), e(x, y));
e.tile(x, y, x_outer, y_outer, x_inner, y_inner, 64,64).fuse(x_outer, y_outer, tile_index).parallel(tile_index);
output = e.realize(input.width(), input.height());
return output;
}

Any tips on how to schedule properly would be greatly appreciated as I'm still very new to this.

EDIT: the code used to get times:

__int64 ctr1 = 0, ctr2 = 0, freq = 0;
output = erode(input, dimension);


if (QueryPerformanceCounter((LARGE_INTEGER *)&ctr1) != 0) {
    // Activity to be timed
    output = erode(input, dimension);
    QueryPerformanceCounter((LARGE_INTEGER *)&ctr2);
    QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
}
std::cout << "\nerosion " << dimension << "x" << dimension << ":" << ((ctr2 - ctr1) *1.0 / freq) << "..."; 
ctr1 = 0, ctr2 = 0, freq = 0;

Solution

  • One big problem here is that you're recompiling the imaging pipeline every time you want to erode an image. If you use an ImageParam for the input and a Param for the dimension, you can just compile it once then realize it multiple times on different images.

    Putting that aside, scheduling is done independently per stage of a Func. Your Func has two stages (each line beginning with "e(x, y) =" is a stage), and you're only scheduling the first (cheap) one. Try something like this to schedule both the initialization and update the same way:

    e.tile(x, y, x_outer, y_outer, x_inner, y_inner, 64,64).fuse(x_outer, y_outer, tile_index).parallel(tile_index);
    e.update(0).tile(x, y, x_outer, y_outer, x_inner, y_inner, 64,64).fuse(x_outer, y_outer, tile_index).parallel(tile_index);
    

    If dimension > 3 you probably want a separable min filter. I'd write it like this:

    Func minx, miny;
    miny(x, y) = minimum(limit(x, y+r));
    minx(x, y) = minimum(miny(x+r, y));
    
    minx.parallel(y, 4).vectorize(x, 32);
    miny.compute_at(minx, y).vectorize(x, 32);