Scheduling infrastructure in CIRCT

[jopperm]

Hi @cgyurgyik,

this is a quick follow-up to the discussion we just had on the CIRCT call. I'm building infrastructure for static schedulers in CIRCT (more info: Recording, Slides of my pitch). Right now, this models only a very basic scheduling problem, but I plan to add more useful problems and algorithms to CIRCT soon (e.g., modulo schedulers). Calyx seems really interesting, and if you think the scheduling lib could help you to bring a calyx to hw lowering to CIRCT (as @mikeurbach suggested), please let me know!

[cgyurgyik]

Hi @jopperm. Thanks for the introduction today.

CC @rachitnigam, @EclecticGriffin, @sampsyo as well, the current brains behind Calyx.

[rachitnigam]

Hi @jopperm! We’ve been following the progress of the scheduling dialect through the email threads and have been excited by the idea of bringing some op-level scheduling into Calyx as well.

in fact, we were talking about scheduling in calyx just yesterday when discussing a different topic (#588). The TLDR is that we’re going to add a new control operator to calyx that will allow us to explicitly model data flow. Once a front end generates such a dataflow graph, it’ll be the responsibility of the compiler to schedule it and generate groups (a calyx concept for encapsulating assignments) which can be lowered by the calyx compiler.

It seems that the best place for collaboration would be here—calyx can use the scheduling dialect to schedule these dataflow graphs and hook into the rest of the infrastructure for lowering.

Our question for you is what are your current short term priorities with the scheduling dialect and how would be proceed towards a shared scheduling infrastructure of this form?

[jopperm]

Hi @rachitnigam,

I’d say my top priority actually is to find users/actual synthesis flows for the scheduling infra, to prove (hopefully…) that the way I think about the scheduling problems works for CIRCT. The data flow operator you describe would be perfect place to start, so what a happy coincidence that this topic came up on the call yesterday.

The first step would be to formalize the kind of schedule you want for your data flow graph. The basic problem currently available in CIRCT considers operations with integer latencies, and expects the scheduling algorithm to compute integer start times that honor the dependence edges (here, it’s a simple precedence, meaning an op can start once its operand values are computed). Would that already suffice for a first version of the data flow operator?

If not, let’s discuss what you need/want in addition (e.g. resource sharing, pipelining, chaining, binding, distinguishing individual operands and results, or something completely new). Once that’s clear, I’d set up the problem model and would look for a suitable algorithm.

I agree that the transformation you describe (lowering the new data flow operator into explicit groups) would be a great MVP. The interface which would be used by this transformation is still really simple (insertOperation, setLatency, getStartTime, … @teqdruid coined it the "flat" API) -- figuring out something more convenient for clients (via OpInterfaces or Traits, for example) would be a welcome side product.

[sampsyo]

Wow; this seems like an awesome way to collaborate! For my money (although @rachitnigam would be the expert here), what you described seems like the right starting point:

The basic problem currently available in CIRCT considers operations with integer latencies, and expects the scheduling algorithm to compute integer start times that honor the dependence edges

That is, scheduling a simple memory-free SSA-ish DFG to use unbounded parallelism. I think you're right to omit a complete treatment of memory accesses, for example, which would incur a lot of up-front complexity to cope with aliasing. And yeah, not dealing with pipelining also seems like a critical simplification for v1. (Pipelining would want to build on that initial foundation.)

[mikeurbach]

Once a front end generates such a dataflow graph

Would the Handshake dialect make a decent starting point? https://circt.llvm.org/docs/Dialects/Handshake/#principle

[jopperm]

Great, then everything you'll need for this v1 should already be there. Looking forward to work with you on this!

(For future reference: Once you have a frontend that can provide alias information, you can insert "auxiliary" dependences (= pairs of operations) to encode the memory dependencies.)

[rachitnigam]

Hey @jopperm, I had a few more thoughts about building a scheduling system on top of Calyx and was wondering if you'd be interested in chatting at some point. With the Calyx dialect being somewhat mature and the addition of the comb group construct, I think we're in a good position to implement some basic scheduling infrastructure.

[jopperm]

Yes, that sounds interesting! Let's find a date in the Calyx/CIRCT-Slack, ok?

[rachitnigam]

Yup! Let's do that.