Software Pipelining Notes | EduRev

Created by: Ankita Sharma

: Software Pipelining Notes | EduRev

 Page 1


Software Pipelining
Y.N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Software Pipelining
Page 2


Software Pipelining
Y.N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining
Overlaps execution of instructions from multiple iterations
of a loop
Executes instructions from different iterations in the same
pipeline, so that pipelines are kept busy without stalls
Objective is to sustain a high initiation rate
Initiation of a subsequent iteration may start even before
the previous iteration is complete
Unrolling loops several times and performing global
scheduling on the unrolled loop
Exploits greater ILP within unrolled iterations
Very little or no overlap across iterations of the loop
Y .N. Srikant Software Pipelining
Page 3


Software Pipelining
Y.N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining
Overlaps execution of instructions from multiple iterations
of a loop
Executes instructions from different iterations in the same
pipeline, so that pipelines are kept busy without stalls
Objective is to sustain a high initiation rate
Initiation of a subsequent iteration may start even before
the previous iteration is complete
Unrolling loops several times and performing global
scheduling on the unrolled loop
Exploits greater ILP within unrolled iterations
Very little or no overlap across iterations of the loop
Y .N. Srikant Software Pipelining
Approaches to Software Pipelining
Iterative modulo scheduling
Similar to list scheduling, computes priorities and uses
operation scheduling (details later)
Uses Modulo Reservation Tables (MRT)
A global resource reservation table with II columns and R
rows
MRT records resource usage of the schedule (of the kernel)
as it is constructed
Initially all entries are 0
If an instruction uses a resource r at time step t, then the
entry MRT(r, t mod II) is set to 1
Slack scheduling
Uses earliest and latest issue times for each instruction
(difference is slack)
Schedules an instruction within its slack
Also uses MRT
Y .N. Srikant Software Pipelining
Page 4


Software Pipelining
Y.N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining
Overlaps execution of instructions from multiple iterations
of a loop
Executes instructions from different iterations in the same
pipeline, so that pipelines are kept busy without stalls
Objective is to sustain a high initiation rate
Initiation of a subsequent iteration may start even before
the previous iteration is complete
Unrolling loops several times and performing global
scheduling on the unrolled loop
Exploits greater ILP within unrolled iterations
Very little or no overlap across iterations of the loop
Y .N. Srikant Software Pipelining
Approaches to Software Pipelining
Iterative modulo scheduling
Similar to list scheduling, computes priorities and uses
operation scheduling (details later)
Uses Modulo Reservation Tables (MRT)
A global resource reservation table with II columns and R
rows
MRT records resource usage of the schedule (of the kernel)
as it is constructed
Initially all entries are 0
If an instruction uses a resource r at time step t, then the
entry MRT(r, t mod II) is set to 1
Slack scheduling
Uses earliest and latest issue times for each instruction
(difference is slack)
Schedules an instruction within its slack
Also uses MRT
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining - contd.
More complex than instruction scheduling
NP-Complete
Involves ?nding initiation interval for successive iterations
Trial and error procedure
Start with minimum II, schedule the body of the loop using
one of the approaches below and check if schedule length
is within bounds
Stop, if yes
Try next value of II, if no
Requires a modulo reservation table
Schedule lengths are dependent on II, dependence
distance between instructions and resource contentions
Y .N. Srikant Software Pipelining
Page 5


Software Pipelining
Y.N. Srikant
Department of Computer Science
Indian Institute of Science
Bangalore 560 012
NPTEL Course on Compiler Design
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining
Overlaps execution of instructions from multiple iterations
of a loop
Executes instructions from different iterations in the same
pipeline, so that pipelines are kept busy without stalls
Objective is to sustain a high initiation rate
Initiation of a subsequent iteration may start even before
the previous iteration is complete
Unrolling loops several times and performing global
scheduling on the unrolled loop
Exploits greater ILP within unrolled iterations
Very little or no overlap across iterations of the loop
Y .N. Srikant Software Pipelining
Approaches to Software Pipelining
Iterative modulo scheduling
Similar to list scheduling, computes priorities and uses
operation scheduling (details later)
Uses Modulo Reservation Tables (MRT)
A global resource reservation table with II columns and R
rows
MRT records resource usage of the schedule (of the kernel)
as it is constructed
Initially all entries are 0
If an instruction uses a resource r at time step t, then the
entry MRT(r, t mod II) is set to 1
Slack scheduling
Uses earliest and latest issue times for each instruction
(difference is slack)
Schedules an instruction within its slack
Also uses MRT
Y .N. Srikant Software Pipelining
Introduction to Software Pipelining - contd.
More complex than instruction scheduling
NP-Complete
Involves ?nding initiation interval for successive iterations
Trial and error procedure
Start with minimum II, schedule the body of the loop using
one of the approaches below and check if schedule length
is within bounds
Stop, if yes
Try next value of II, if no
Requires a modulo reservation table
Schedule lengths are dependent on II, dependence
distance between instructions and resource contentions
Y .N. Srikant Software Pipelining
Software Pipelining Example-1
for (i=1; i<=n; i++) {
   a[i+1] = a[i] + 1;
   b[i] = a[i+1]/2;
   c[i] = b[i] + 3;
   d[i] = c[i]
}
(1,1)
(0,1)
(0,1)
(0,1)
4
1
2
3
(dep.dist, delay)
             Iterations
1       S1
2       S2   S1
3       S3   S2   S1
4       S4   S3   S2   S1
5              S4    S3  S2   S1
7                             S4   S3   S2   S1                         
6                      S4   S3   S2   S1
8                                    S4   S3   S2
9                                            S4   S3
10                                                 S4
T
I
M
E
Y .N. Srikant Software Pipelining
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!