ScheduleParams should allow for deferred value specification

[steven-johnson]

(Hoisted from discussion on PR#1936)

abadams@ said:

I have an idea:

The reason we separate schedule() from generate() is so that scheduling can be deferred, in case it depends on symbols that come from later in the algorithm definition (e.g. a compute_at LoopLevel).

But the whole essence of the algorithm language is deferred execution -- you can use a Param in your algorithm without knowing its value yet.

So what if we allowed scheduling to use unbound ScheduleParams? What if ScheduleParams were a little more like Params and less like GeneratorParams? They all need to be bound before you actually compile, but you can do that at any point up until lowering. There would be a phase at the top of lowering that resolved the necessary level of indirection. (e.g. a compute_at(schedule_param_5) would become a compute_at(schedule_param_5's bound value)).

ScheduleParams in scalar types would act as Exprs that get replaced by constant values at the top of lowering, so you can tile using them, specialize on them to turn on/off vectorization, etc.

Usage would be something like:

auto demosaic = MyDemosaicGeneratorOrStub::do_something( ... inputs ...);

// define rest of pipeline ...
 ... demosaic.output(x, y) ...

// schedule for processed
....

// schedule for demosaic
demosaic.compute_at_level = {processed, y}
demosaic.store_at_level = {processed, yo}

// Always vectorize demosaic in this context. Other uses of demosaic might not.
demosaic.vector_lanes = 8;
// I've bound the scheduleparam to a constant.
// Demosaic already ran code like foo.specialize(vector_lanes > 1).vectorize(x, vector_lanes);

// parallelize the demosaic only when I'm not being parallelized
demosaic.parallelize = !(this->parallelize);  
// I've bound the scheduleparam to an Expr that depends on one of my scheduleparams

Note that the last bit assumes you can bind scheduleparams using any Expr, including other unresolved scheduleparams, which allows transitively communicating information upwards.

The point of this is so that you can do all your scheduling at the bottom of generate(), and there's no schedule() method.

The design goal here is: You shouldn't have to be aware of a feature until it solves a problem that you have. When you do become aware of it, you shouldn't need to restructure all the code you've written so far to make use of it.

In this specific instance it means that people can just put everything in generate(), and when they need a ScheduleParam they can add it as a member without having to tease apart their code into generate() and schedule(). This particular demo app can ignore deferred scheduling. camera_pipe would use it.

[steven-johnson]

jrk@ commented:

I definitely like this. It's worth working a few examples, of course, to further develop it. The obvious cases seem to be the camera pipe, and also something where a module would be scheduled differently in different contexts which would historically have been guarded with C++-level ifs (vectorizing an internal stage within a module which is compute_at some level of the module's output, in cases where the module might be inlined into its uses). This seems to do a nice job with the scoping challenge in things like camera pipe, but it's less clear to me if it has an impact on things that need to propagate through downstream uses in the face of inlining, etc.

[zvookin]

Just a quick note, but the first order reason we separated generate and schedule is to support auto scheduling.

[zvookin]

Also, one of the first things we tell people about Halide is that its main innovation is separation of algorithm and schedule. A goal of separating the two in the program structure was to add clarity around the issue, not make things more difficult to understand. For code where the algorithm is interleaved with scheduling, I've more than once a way to tell which helper functions do scheduling internally and to what degree, so providing some clues in the syntax or layout does strike me as helpful.

[abadams]

I agree that separating them in the program structure would be good, but scheduling must be in the same scope or a nested scope w.r.t the Funcs and Vars that make the algorithm. Putting scheduling into its own method forced all the Funcs and Vars out into class members (where you get silly side-effects, like mandatory trailing underscores), or forces the schedule to be a mutable lambda that slurps up all the names in scope in the generate method (which works OK, but it's a heavy-duty piece of C++). It's more palatable to me to just put the scheduling code back into generate(). That has served us acceptably so far. If we can do that and also solve the deferred scheduling problem, that would be an OK point in the design space, I think.

Ad-hoc helpers need to document what scheduling they do. If we make Generators usable as local components, then the contract is much more clear. They schedule themselves internally parameterized by the ScheduleParams. The ScheduleParams are the explicit scheduling interface to the component.

Not sure what to do about autoscheduling. I think we need more experience with it. E.g. we don't know if human assistance will always be required in practice - there certainly needs to be some piece of code that sets size estimates, which feels like scheduling code to me.

On Thu, Mar 23, 2017 at 3:24 PM, Zalman Stern notifications@github.com wrote:

Also, one of the first things we tell people about Halide is that its main innovation is separation of algorithm and schedule. A goal of separating the two in the program structure was to add clarity around the issue, not make things more difficult to understand. For code where the algorithm is interleaved with scheduling, I've more than once a way to tell which helper functions do scheduling internally and to what degree, so providing some clues in the syntax or layout does strike me as helpful.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/halide/Halide/issues/1940#issuecomment-288879049, or mute the thread https://github.com/notifications/unsubscribe-auth/AAfdRt1Ua8vWKOcl9uo-jx-bLH-UrgJiks5rovEvgaJpZM4MnYQs .

[steven-johnson]

ScheduleParams in scalar types would act as Exprs that get replaced by constant values at the top of lowering

Our belief right now is that we can probably get by with ScheduleParam<any-scalar-type> and ScheduleParam<LoopLevel>

The first would be pretty straightforward to do (since an Expr can hold every scalar type we care about); there are several ways to implement it, but doing it just as a type of Variable that we can mutate at the top of lower() seems effective.

LoopLevel is a bit more interesting, though, as it doesn't fit into an Expr right now (and probably shouldn't, period), and isn't really a visible part of the IR tree in general IIUC (it gets stored into various special places inside the bowels of Schedule); further, we may also need to have LoopLevel split into wrapper/contents objects (a la Param/Parameter) to allow for mutating the values without requiring a global table.

[zvookin]

Re: auto scheduler estimates being scheduling, in the component use cases we were considering, it seemed unlikely one would know the estimates when writing the Generator, so they would either need to be ScheduleParams or some new sort of parameter, or in our initial idea, provided as arguments to a command line tool or build rule. But yes, we're way ahead of actual use and experience here.

[steven-johnson]

See https://github.com/halide/Halide/pull/1955 for a take on this.

[steven-johnson]

Address by #1955