Pipeline Scheduling

Generate DLX code that avoids pipeline stalls for the following sequence of statements:


a = b + c ;
d = a - f ;
e = g - h ;

Assume that all variables are 32-bit integers. Wherever necessary, explicitly explain the actions that are needed to avoid pipeline stalls in your scheduled code.

Solution:

The DLX assembly code for the given sequence of statements is :
 
  1 2 3 4 5 6  7  8  9  10 11 12  13  14  15  16 17 18
LW Rb, b IF ID EX M WB                          
LW Rc, c   IF ID EX M WB                        
Add Ra,Rb, Rc     IF ID stall EX M WB                     
SW Ra, a       IF  stall ID EX M WB                   
LW Rf, f         stall IF ID EX M WB                 
Sub Rd, Ra, Rf             IF ID stall EX M  WB             
SW Rd, d               IF stall ID EX M WB           
LW Rg, g                 stall IF ID EX M WB         
LW Rh, h                     IF ID EX M WB       
Sub Re, Rg, Rh                       IF ID stall EX  M WB  
SW Re, e                         IF stall ID EX M WB

Running this code segment will need some forwarding. But instructions LW and ALU(Add or Sub), when put in sequence, are generating hazards for the pipeline that can not be resolved by forwarding. So the pipeline will stall. Observe that in time steps 4, 5, and 6, there are two forwards from the Data memory unit to the ALU in the EX stage of the Add instruction. So also the case in time steps 13, 14, and 15. The hardware to implement this forwarding will need two Load Memory Data registers to store the output of data memory. Note that for the SW instructions, the register value is needed at the input of Data memory. The better solution with compiler assist is given below.

Rather then just allow the pipeline to stall, the compiler could try to schedule the pipeline to avoid these stalls by rearranging the code sequence to eliminate the hazards.

Suggested version is (the problem has actually more then one solution) :
 
Instruction 1 2 3 4 5 6  7  8  9  10  11  12  13  14  15  Explanation
LW Rb, b IF ID EX M WB                      
LW Rc, c   IF ID EX M WB                    
LW Rf, f     IF ID EX M WB                  
Add Ra, Rb, Rc       IF  ID  EX M WB               Rb read in second half of ID;
Rc forwarded
SW Ra, a         IF ID EX M WB             Ra forwarded
Sub Rd, Ra, Rf           IF ID EX M WB           Rf read in second half of ID;
Ra forwarded
LW Rg, g             IF ID EX M WB          
LW Rh, h               IF ID EX M WB        
SW Rd, d                 IF ID EX M WB     Rd read in second half of ID;
Sub Re, Rg, Rh                   IF ID EX M WB   Rg read in second half of ID;
Rh forwarded
SW Re, e                     IF ID EX M WB Re forwarded

The same color is used to outline the source and destination of forwarding.
The blue color is used to indicate the technique to perform the register file reads in the second half of a cycle, and the writes in the first half.

Note: Notice that the use of different registers for the first, second and third statements was critical for this schedule to be legal! In general, pipeline scheduling can increase the register count required.