HOME       UP       PREV       NEXT (Pipelined Schedulling - Between Basic Blocks)  

Pipelined Schedulling - One Basic Block

After loop unrolling, we have an expanded control-flow graph that has larger basic blocks than in the original HLL program.

In classical HLS, each basic block of the expanded graph is given a time-domain static scheudle.

Example static schedule for a basic block containing a single assignment.
Example static schedule for a basic block containing a single assignment.

Our figure shows only one assignment.

A basic block schedule typically contains multiple assignments, with sub-expressions and functional units being reused in the time domain throughout the schedule and shared between assignments.

To avoid RaW hazards within one basic block, all reads to a variable or memory location must be schedulled before all writes to the same.

The name alias problem means we must be conservative in this analysis when considering whether arrays subscripts are equal. This is `undecidable' in general theory, but often doable in practice. Indeed may subscript expressions will be simple functions of loop `induction variables' whose pattern we need to understand for high performance.


19: (C) 2008-18, DJ Greaves, University of Cambridge, Computer Laboratory.