Scheduling and Allocation in SPARK
Center for Embedded Computer Systems Computer Science and Engineering
Microelectronic Embedded Systems Laboratory University Of California, San Diego
menu Home Methodology Download News Publications Benchmarks Links Internal

Speculative code motions in SPARK

Scheduling Pass in SPARK

SPARK uses a toolbox approach towards scheduling. In the toolbox are a set of basic code transformations and code motion primitive operations such as percolation, trailblazing, loop pipelining et cetera. These transformations are directed by a set of speculative code motion and loop transformation heuristics.

We employ a range of parallelizing compiler and compiler transformations before, during, and after scheduling. These transformations include a set of speculative code motions (see DAC 01 and ISSS 01 papers), a set of dynamic transformations such as dynamic CSE (ISSS 02) and dynamic branch balancing (DATE 03), and a set of basic compiler transformations such as common sub-expression elimination, dead code elimination, copy propagation, and so on.

Scheduling under Resource Constraints

Code motions can be used for improved resource sharing and also to reduce the schedule length. This is demonstrated in Figure 1 below. The first control-data flow graph (CDFG) shown int the figure corresponds to the original presented by Wakabayashi et al. From this CDFG, it is evident that the longest path in the schedule is through the basic block containing the operations g, e, i and j. As shown in the second CDFG, this can be improved by performing the operations g and e in parallel with the operation c in the previous basic block. This assumes that there are enough resources for this to be done. In this way, the schedule length can be reduced.

Similarly, the 3rd CDFG in the figure shows how the original CDFG can be scheduled with the resource constraint of 1 adder, 1 substractor and 1 comparator. In this CDFG, notably, operation c has been reverse speculated (also referred to as lazy-execution) and hence, been moved into the conditional where it is used. And the operations g and e have been speculated outside the conditional.


Figure 1: Scheduling under Resource Constraints

This scheduled CDFG can then be used to generate the finite state machine(FSM) and the corresponding synthesizable register-transfer level (RTL) VHDL. Figure 2 shows an example of the type of RTL VHDL generated in pseudo-VHDL.

case CurrentState 
when S0 =>
    a; b; p;     NextState <= S1;
when S1 =>
    d; k; q;     NextState <= S2;
 
when S3 =>
    if not(p) then
       if (q) then
          i;     NextState <= S4;
       else 
          c;     NextState <= S4;

       end if;
    end if;
when S4 =>
        if (q) then
        else 
           h;    NextState <= S5;
        end if;
     end if;
 when S5 =>
        l;       NextState <= S6;
     else 
        m;       NextState <= S6;

     end if;
     if not(p) then
           j;    NextState <= S5;
     if not(p) then
 when S6 =>
     n;          NextState <= S0;
 end case;
Figure 2: From CDFG to Synthesizable RTL VHDL (pseudo-VHDL shown)

Maintained by Sumit Gupta <sumitg@cecs.uci.edu>