Embedded Systems Group (ES)

Basic Block Scheduling for SCAD Processors

Starting with MiniC Programs

This tool translates a given MiniC program without control flow statements (like conditional statements and loops) to an equivalent (leveled) dataflow process network and generates then SAT constraints that ensure that the leveled DPN can be scheduled for the specified number of processing units (PUs). The SAT constraints essentially specify that there are no crossing edges that refer to the same virtual channel. A virtual channel is a connection PU[p].out[i] -> PU[q].in[j] from output buffer out[i] of PU p to the input buffer in[j] of PU q. SCAD code can be generated for such an ordering if and only if there are no crossing edges in a level that refer to the same virtual channel. If such edges should be there, one needs to use another PU for one of the four nodes involved or to reorder the nodes accordingly.

If zero processing units are specified, the tool will determine the least number of processing units to schedule the example.

no. PUs:
show constraints




Starting with Dataflow Graphs

Instead of starting with a MiniC program as input, the tool below starts with a dataflow graph that can be specified directly using the nodes described in this paper. The tool will then add Copy nodes to the given DPN to organize its nodes on levels, and will then generate and solve the SAT constraints.

no. PUs:
show constraints