Modulo Scheduling with Reduced Register Pressure.
AbstractSoftware pipelining is a scheduling technique that is used by some product compilers in order to expose more instruction level parallelism out of innermost loops. Modulo scheduling refers to a class of algorithms for software pipelining. Most previous research on modulo scheduling has focused on reducing the number of cycles between the initiation of consecutive iterations (which is termed II) but has not considered the effect of the register pressure of the produced schedules. The register pressure increases as the instruction level parallelism increases. When the register requirements of a schedule are higher than the available number of registers, the loop must be rescheduled perhaps with a higher II. Therefore, the register pressure has an important impact on the performance of a schedule. This paper presents a novel heuristic modulo scheduling strategy that tries to generate schedules with the lowest II, and, from all the possible schedules with such II, it tries to select that with the lowest register requirements. The proposed method has been implemented in an experimental compiler and has been tested for the Perfect Club benchmarks. The results show that the proposed method achieves an optimal II for at least 97.5 percent of the loops and its compilation time is comparable to a conventional top-down approach, whereas the register requirements are lower. In addition, the proposed method is compared with some other existing methods. The results indicate that the proposed method performs better than other heuristic methods and almost as well as linear programming methods, which obtain optimal solutions but are impractical for product compilers because their computing cost grows exponentially with the number of operations in the loop body.
Introduction
Increasing the instruction level parallelism is an observed trend in the design of current
microprocessors. This requires a combined effort from the hardware and software in order
to be effective. Since most of the execution time of common programs is spent in loops,
many efforts to improve performance have targeted loop nests.
Software pipelining [5] is an instruction scheduling technique that exploits the instruction
level parallelism of loops by overlapping the execution of successive iterations of a
loop. There are different approaches to generate a software pipelined schedule for a loop
[1]. Modulo scheduling is a class of software pipelining algorithms that was proposed at
the begining of last decade [23] and has been incorporated into some product compilers
(e.g. [21, 7]). Besides, many research papers have recently appeared on this topic
[11, 14, 25, 13, 28, 12, 26, 22, 29, 17].
Modulo scheduling framework relies on generating a schedule for an iteration of the
loop such that when this same schedule is repeated at regular intervals, no dependence is
violated and no resource usage conflict arises. The interval between the succesive iterations
is termed Initiation Interval (II ). Having a constant initiation interval implies that no
resource may be used more than once at the same time modulo II .
Most modulo scheduling approaches consists of two steps. First, they compute an
schedule trying to minimize the II but without caring about register allocation and then,
variables are allocated to registers. The execution time of a software pipelined loop depends
on the II , the maximum number of live values of the schedule (termed MaxLive) and the
length of the schedule for one iteration. The II determines the issue rate of loop iterations.
Regarding the second factor, if MaxLive is not higher than the number of available registers
then the computed schedule is feasible and then it does not influence the execution time.
Otherwise, some actions must be taken in order to reduce the register pressure. Some
possible solutions outlined in [24] and evaluated in [16] are:
ffl Reschedule the loop with an increased II . In general, increasing the II reduces
MaxLive but it decreases the issue rate, which has a negative effect on the execution
time.
ffl Add spill code. This again has a negative effect since it increases the required memory
bandwidth and it will result in additional memory penalties (e.g. cache misses).
Besides, memory may become the most saturated resource and therefore adding spill
code may require to increase the II .
Finally, the length of the schedule for one iteration determines the cost of the epilogue
that should be executed after the main loop in order to finish the last iterarions which
have been initiated in the main loop but have not been completed (see section 2.1). This
cost may be negligible when the iteration count of the loop is high.
Most previous works have focused on reducing the II and sometimes also the length of
the schelude for one iteration but they have not considered the register requirements of the
proposed schedule, which may have a severe impact on the performance as outlined above.
A current trend in the design of new processors is the increase in the amount of instruction
level parallelism that they can exploit. Exploiting more instruction level parallelism results
in a significant increase in the register pressure [19, 18], which exacerbates the problem of
ignoring its effect on the performance of a given schedule.
In order to obtain more effective schedules, a few recently proposed modulo scheduling
approaches try to minimize both the II and the register requirements of the produced
schedules.
Some of these approaches [10, 9] are based on formulating the problem in terms of an
optimization problem and solve it using an integer linear programming approach. This
may produce optimal schedules but unfortunately, this approach has a computing cost
that grows exponentially with the number of basic operations in the loop body. Therefore,
they are impractical for big loops, which in most cases are the most time consuming parts
of a program and thus, they may be the ones that most benefit from software pipelining.
Practical modulo scheduling approaches used by product compilers use some heuristics
to guide the scheduling process. The two most relevant heuristic approaches proposed
in the literature that try to minimize both the II and the register pressure are: Slack
Scheduling [12] and Stage Scheduling [8].
Slack Scheduling is an iterative algorithm with limited backtracking. At each iteration
the scheduler chooses an operation based on a previouly computed dynamic priority. This
priority is a function of the slack of each operation (i.e., a measure of the scheduling
freedom for that operation) and it also depends on how much critical the resources used
by that operation are. The selected operation is placed in the partial schedule either as
early as possible or as late as possible. The choice between these two alternative is made
basically by determining how many of the operation's inputs and outputs are stretchable
and choosing the one that minimizes the involved values' lifetimes. If the scheduler cannot
place the selected operation due to a lack of conflict-free issue slots, then it is forced to a
particular slot and all the conflicting operations are ejected from the partial scheduler. In
order to limit this type of backtracking, if operations are ejected too many times, the II is
incremented and the scheduling is started all over again.
Stage Scheduling is not a whole modulo scheduler by itself but a set of heuristic techniques
that reduce the register requirements of any given modulo schedule. This objective
is achieved by shifting operations by multiples of II cycles. The resulting schedule has the
same II but lower register requirements.
This paper presents Hypernode Reduction Modulo Scheduling (HRMS) 1 , a heuristic
modulo scheduling approach that tries to generate schedules with the lowest II , and from
all the possible schedules with such II , it tries to select that with the lowest register
requirements. The main part of HRMS is the ordering strategy. The ordering phase orders
the nodes before scheduling them, so that only predecessors or successors of a node can be
scheduled before it is scheduled (except for recurrences). During the scheduling step the
nodes are scheduled as early/late as possible, if their predecessors/successors have been
preliminary version of this work appeared in [17].
previously scheduled.
The performance of HRMS is evaluated and compared with that of a conventional
approach (a top-down scheduler) that does not care about register pressure. For this
evaluation we have used over a thousand loops from the Perfect Club Benchmark Suite
[4] that account for 78% of its execution time. The results show that HRMS achieves an
optimal II for at least 97.5% of the loops and its compilation time is comparable to the
top-down approach whereas the register requirements are lower.
In addition, HRMS has been tested for a set of loops taken from [10] and compared
against two other heuristic strategies. These two strategies are the previously mentioned
Slack Scheduling, and FRLC [27], which is an heuristic strategy that does not take into
account the register requirements. In addition, HRMS is compared with SPILP [10], which
is a linear programming formulation of the problem. Because of the computing requirements
of this latter approach, only small loops are used for this comparison. The results
indicate that HRMS obtains better schedules than the other two heuristic approaches and
its results are very close to the ones produced by the optimal scheduler. The compilation
time of HRMS is similar to the other heuristic methods and much lower than the linear
programming approach.
The rest of this paper is organized as follows. In Section 2, an example is used to
illustrate the motivation for this work, that is, reducing the register pressure in modulo
scheduled loops while achieving near optimal II . Section 3 describes the proposed modulo
scheduling algorithm that is called HRMS. Section 4 evaluates the performance of the
proposed approach, and finally, Section 5 states the main conclusions of this work.
2 Overview of modulo scheduling and motivating ex-
ample
This section includes an overview of modulo scheduling and the motivation for the work
presented in this paper. For a more detailed discussion on modulo scheduling refer to [1].
2.1 Overview of modulo scheduling
In a software pipelined loop the schedule for an iteration is divided into stages so that the
execution of consecutive iterations that are in distinct stages is overlapped. The number
of stages in one iteration is termed stage count(SC). The number of cycles per stage is
II .

Figure

1 shows the dependence graph for the running example used along this section.
In this graph, nodes represent basic operations of the loop and edges represent values
generated and consumed by these operations. For this graph, Figure 2a shows the execution
of the six iterations of the software pipelined loop with an II of 2 and a SC of 5. The
operations have been scheduled assuming a four-wide issue machine, with general-purpose
functional units (fully pipelined with a latency of two cycles). The scheduling of each
iteration has been obtained using a top-down strategy that gives priority to operations in
A
G
F

Figure

1: A sample dependence graph.
the critical path with the additional constraint that no resource can be used more than
once at the same cycle modulo II . The figure also shows the corresponding lifetimes of
the values generated in each iteration.
The execution of a loop can be divided into three phases: a ramp up phase that fills
the software pipeline, an steady state phase where the software pipeline achieves maximum
overlap of iterations, and a ramp down phase that drains the software pipeline. The code
that implements the ramp up phase is termed the prologue. During the steady state
phase of the execution, the same pattern of operations is executed in each stage. This is
achieved by iterating on a piece of code, termed the kernel, that correspods to one stage
of the steady state phase. A third piece of code called the epilogue, is required to drain
the software pipeline after the execution of the steady state phase.
The initiation interval II between two successive iterations is bounded either by loop-carried
dependences in the graph (RecMII ) or by resource constraints of the architecture
(ResMII ). This lower bound on the II is termed the Minimum Initiation Interval
)). The reader is refered to [7, 22] for an extensive dissertation
on how to calculate ResMII and RecMII .
Since the graph in Figure 1 has no recurrence circuits, its initiation interval is constrained
only by the available resources: number of operations
divided by number of resources). Notice that in the scheduling of Figure 2a no dependence
is violated and every functional unit is used at most once at all even cycles (cycle modulo
and at most once at all odd cycles (cycle modulo
The code corresponding to the kernel of the software pipelined loop is obtained by
ovelapping the different stages that constitute the schedule of one iteration. This is shown
in Figure 2b. The subscripts in the code indicate relative iteration distance in the original
loop between operations. For instance, in this example, each iteration of the kernel executes
an instance of operation A and an instance of operation B of the previous iteration in the
initial loop.
Values used in a loop correspond either to loop-invariant variables or to loop-variant
variables. Loop-invariants are repeatedly used but never defined during loop execution.
Loop-invariants, have a single value for all the iterations of the loop and therefore they
iteration 1
iteration 2
iteration 3
iteration 4
iteration 5
Prologue
Steady
Epilogue
II
Kernel Code
iteration 6
a)
G
F
G
F
G
F
G
F
G
F
G
F

Figure

2: a) Software pipelined loop execution, b) Kernel, and c) Register requirements.
require one register each regardless of the scheduling and the machine configuration.
For loop-variants, a value is generated in each iteration of the loop and, therefore,
there is a different value corresponding to each iteration. Because of the nature of software
pipelining, lifetimes of values defined in an iteration can overlap with lifetimes of
values defined in subsequent iterations. Figure 2a shows the lifetimes for the loop-variants
corresponding to every iteration of the loop. By overlapping the lifetimes of the different
iterations, a pattern of length II cycles that is indefinetely repeated is obtained. This
pattern is shown in Figure 2c. This pattern indicates the number of values that are live
at any given cycle. As it is shown in [24], the maximum number of simultaneously live
values MaxLive is an accurate approximation of the number of register required by the
schedule 2 . In this section, the register requirements of a given schedule will be approximated
by MaxLive. However, in the experiments section we will measure the actual register
requirements after register allocation.
Values with a lifetime greater than II pose an additional difficulty since new values are
generated before previous ones are used. One approach to fix this problem is to provide
some form of register renaming so that successive definitions of a value use distinct registers.
Renaming can be performed at compile time by using modulo variable expansion [15], i.e.,
2 For an extensive discussion on the problem of allocating registers for software-pipelined loops refer to
[24]. The strategies presented in that paper almost always achieve the MaxLive lower bound. In particular,
the wands-only strategy using end-fit with adjacency ordering never required more than MaxLive
registers.
unrolling the kernel and renaming at compile time the multiple definitions of each variable
that exist in the unrolled kernel. A rotating register file can be used to solve this problem
without replicating code by renaming different instantiations of a loop-variant at execution
time [6].
2.2 Motivating example
In many modulo scheduling approaches, the lifetimes of some values can be unnecessarily
large. As an example, Figure 2a shows a top-down scheduling, and Figure 3a a bottom-up
scheduling for the example graph of Figure 1 and a machine with four general-purpose
functional units with a two-cycle latency.
In a top-down strategy, operations can only be scheduled if all their predecessors have
already been scheduled. Each node is placed as early as possible in order not to delay any
possible successors. Similary, in a bottom-up strategy, an operation is ready for scheduling
if all its successors have already been scheduled. In this case, each node is placed as late
as possible in order not to delay possible predecessors. In both strategies, when there are
several candidates to be scheduled, the algorithm chooses the one that is more critical in
the scheduling.
In the top-down scheduling, node E is scheduled before node F. Since E has no predecessors
it can be placed at any cycle, but in order not to delay any possible successor, it is
placed as early as possible. Figure 2a shows the lifetimes of loop variants for the top-down
scheduling assuming that a value is alive from the beginning of the producer operation to
the beginning of the last consumer. Notice that loop variant VE has an unnecessary large
lifetime due to the early placement of E during the scheduling.
In the bottom-up approach E is scheduled after F, therefore it is placed as late as
possible reducing the lifetime of VE (Figure 3b). Unfortunately C is scheduled before B
and, in order to not delay any possible predecessor it is scheduled as late as possible. Notice
that the VB has an unnecessary large lifetime due to the late placement of C.
In HRMS, an operation will be ready for scheduling even if some of its predecessors
and successors have not been scheduled. The only condition (to be guaranteed by the
pre-ordering step) is that when an operation is scheduled, the partial schedule contains
only predecessors or successors or none of them, but not both of them (in the absence
of recurrences). The ordering is done with the aim that all operations have a previously
scheduled reference operation (except for the first operation to be scheduled). For instance,
consider that nodes of the graph in Figure 1 are scheduled in the order fA, B, C, D, F,
Gg. Notice that node F will be scheduled before nodes fE, Gg, a predecessor and a
successor respectively, and that the partial scheduling will contain only a predecessor (D)
of F. With this scheduling order, both C and E (the two conflicting operations in the top-down
and bottom-up strategies) have a reference operation already scheduled, when they
are placed in the partial schedule.
Figure 4a shows the HRMS scheduling for one iteration. Operation A will be scheduled
in cycle 0. Operation B, which depends on A, will be scheduled in cycle 2. Then C and later
D, are scheduled in cycle 4. At this point, operation F is scheduled as early as possible,
G C9
Cycle
c) d)

Figure

3: Bottom-Up scheduling: a) Schedule of one iteration, b) Lifetimes of variables, c)
Kernel, d) Register requirements.
i.e. at cycle 6 (because it depends on D), but there are no available resources at this cycle,
so it is delayed to cycle 7. Now the scheduler places operation E as late as possible in the
scheduling because there is a successor of E previously placed in the partial scheduling,
thus operation E is placed at cycle 5. And finally, since operation G has a predecessor
previously scheduled, it is placed as early as possible in the scheduling, i.e. at cycle 9.
Figure 4b shows the lifetimes of loop variants. Notice that neither C nor E have
been placed too late or too early because the scheduler always takes previously scheduled
operations as a reference point. Since F has been scheduled before E, the scheduler has a
reference operation to decide a late start for E. Figure 4d shows the number of live values
in the kernel (Figure 4c) during the steady state phase of the execution of the loop. There
are 6 live values in the first row and 5 in the second. In contrast the top-down schedule
has simultaneosly live values and the bottom-up schedule has 9.
The following section describes the algorithm that orders the nodes before scheduling,
and the scheduling step.
3 Hypernode Reduction Modulo Scheduling
The dependences of an innermost loop can be represented by a Dependence Graph
is the set of vertices of the graph G, where each vertex
an operation of the loop. E is the dependence edge set, where each edge (u; v) 2 E
represents a dependence between two operations u, v. Edges may correspond to any of
the following types of dependences: register dependences, memory dependences or control
dependences. The dependence distance ffi (u;v)
is a nonnegative integer associated with each
edge There is a dependence of distance ffi (u;v)
between two nodes u and v if the
execution of operation v depends on the execution of operation u at ffi (u;v) iterations before.
The latency - u is a nonzero positive integer associated with each node u 2 V and is defined
Cycle
c) d)

Figure

4: HRMS scheduling: a) Schedule of one iteration, b) Lifetimes of variables, c)
Kernel, d) Register requirements.
as the number of cycles taken by the corresponding operation to produce a result.
HRMS tries to minimize the register requirements of the loop by scheduling any operation
u as close as possible to their relatives i.e. the predecessors of u, P red(u), and the
successors of u, Succ(u). Scheduling operations in this way shortens operand's lifetime
and therefore reduces the register requirements of the loop.
To software pipeline a loop, the scheduler must handle cyclic dependences caused by
recurrence circuits. The scheduling of the operations in a recurrence circuit must not be
stretched
beyond\Omega \Theta II ,
where\Omega is the sum of the distances in the edges that constitute
the recurrence circuit.
HRMS solves these problems by splitting the scheduling into two steps: A pre-ordering
step that orders nodes and, the actual scheduling, that schedules nodes (once at a time)
in the order given by the pre-ordering step.
The pre-ordering step orders the nodes of the dependence graph with the goal of scheduling
the loop with an II as close as possible to MII and using the minimum number of reg-
isters. It gives priority to recurrence circuits in order not to stretch any recurrence circuit.
It also ensures that, when a node is scheduled, the current partial scheduling contains only
predecessors or successors of the node, but never both (unless the node is the last node of
a recurrence circuit to be scheduled).
The ordering step assumes that the dependence graph, -), is connected
component. If G is not a connected component it is decomposed into a set of connected
components fG i g, each G i is ordered separately and finally the lists of nodes of all G i are
concatenated giving a higher priority to the G i with a more restrictive recurrence circuit(in
terms of RecMII ).
Next the pre-ordering step is presented. First we will assume that the dependence graph
function Pre Ordering(G, L, h)
fReturns a list with the nodes of G orderedg
fIt takes as input: g
fThe dependence graph (G) g
fA list of nodes partially ordered (L) g
fAn initial node (i.e the hypernode) (h) g
List
return List

Figure

5: Function that pre-orders the nodes in a dependence graph without recurrence
circuits
has no recurrence circuits (Section 3.1), and in Section 3.2 we introduce modifications in
order to deal with recurrence circuits. Finally Section 3.3 presents the scheduling step.
3.1 Pre-ordering of graphs without recurrence circuits
To order the nodes of a graph, an initial node, that we call Hypernode, is selected. In an
iterative process, all the nodes in the dependence graph are reduced to this Hypernode.
The reduction of a set of nodes to the Hypernode consists of: deleting the set of edges
among the nodes of the set and the Hypernode, replacing the edges between the rest of
the nodes and the reduced set of nodes by edges between the rest of the nodes and the
Hypernode, and finally deleting the set of nodes being reduced.
The pre-ordering step (Figure 5) requires an initial Hypernode and a partial list of
ordered nodes. The current implementation selects the first node of the graph (i.e the
node corresponding to the first operation in the program order) but any node of the graph
can be taken as the initial Hypernode 3 . This node is inserted in the partial list of ordered
3 Preliminary experiments showed that selecting different initial nodes produced different schedules
function Hypernode Reduction(V 0 ,G,h)
f Creates the subgraph G
f And reduces G 0 to the node h in the graph G g
for each do
for each do
else
return G 0

Figure

Function Hypernode Reduction
nodes, then the pre-ordering algorithm sorts the rest of the nodes.
At each step, the predecessors (successors) of the Hypernode are determined. Then the
nodes that appear in any path among the predecessors (successors) are obtained (function
Search All Paths) 4 . Once the predecessors (successors) and all the paths connecting them
have been obtained, all these nodes are reduced (see function Hypernode Reduction in

Figure

to the Hypernode, and the subgraph which contains them is topologically sorted.
The topological sort determines the partial order of predecessors (successors), which is
appended to the ordered list of nodes. The predecessors are topologically sorted using the
PALA algorithm. The PALA algorithm is like an ALAP (As Late As Possible) algorithm,
but the list of ordered nodes is inverted. The successors are topologically sorted using an
ASAP (As Soon As Possible) algorithm.
As an example, consider the dependence graph in Figure 7a. Next, we illustrate the
ordering of the nodes of this graph step by step.
1. Initially, the list of ordered nodes is empty (List = fg). We start by designating a
node of the graph as the Hypernode (H in Figure 7). Assume that A is the first node
of the graph. The resulting graph is shown in Figure 7b. Then A is appended to the
that had approximately the same register requirements (there were minor differences caused by resource
constraints).
4 The execution time of Search All Paths is O(kV k
list of ordered nodes (List = fAg).
2. In the next step the predecessors of H are selected. Since it has no predecessors, the
successors are selected (i.e. the node C). Node C is reduced to H, resulting in the
graph of Figure 7c, and C is added to the list of ordered nodes (List = fA; Cg).
3. The process is repeated, selecting nodes G and H. In the case of selecting multiple
nodes, there may be paths connecting these nodes. The algorithm looks for the
possible paths, and topologically sorts the nodes involved. Since there are no paths
connecting G and H, they are added to the list (List = fA; C; G; Hg), and reduced
to the Hypernode, resulting the graph of Figure 7d.
4. Now H has D as a predecessor, thus D is reduced, producing the graph in Figure 7e,
and appended to the list (List = fA; C; G; H;Dg).
5. Then J, the successor of H, is ordered (List = fA; C; G; H;D;Jg) and reduced,
producing the graph in Figure 7f.
6. At this point H has two predecessors B and I, and there is a path between B and
I that contains the node E. Therefore B, E, and I are reduced to H producing the
graph of Figure 7g. Then, the subgraph that contains B, E, and I is topologically
sorted, and the partially ordered list fI; E; Bg is appended to the list of ordered
circuits. Then, we order this dependence graph as shown in Subsection 3.1.
Before presenting the ordering algorithm for recurrence circuits, let us put forward some
considerations about recurrences. Recurrence circuits can be classified as:
ffl Single recurrence circuits (Figure 8a).
I
G
F
I
G
F
I
G
F
I
F
I
F
I
F
a) b) c)
d) e) f) g) h)

Figure

7: Example of reordering without recurrences.
A
A
A
A
a) b) c) d)

Figure

8: Types of recurrences
Recurrence circuits that share the same set of backward edges (Figure 8b). We
call recurrence subgraph to the set of recurrence circuits that share the same set of
backward edges. In this way Figures 8a and 8b are recurrence subgraphs.
ffl Several recurrence circuits can share some of their nodes (Figures 8c and 8d) but
have distinct sets of backward edges. In this case we consider that these recurrence
circuits are different recurrence subgraphs.
All recurrence circuits are identified during the calculation of RecMII . For instance, the
recurrence circuits of the graph of Figure 8b are fA, D, Eg and fA, B, C, Eg. Recurrence
circuits are grouped into recurrence subgraphs (in the worst case there may be a recurrence
subgraph for each backward edge). For instance, the recurrence circuits of Figure 8b are
grouped into the recurrence subgraph fA, B, C, D, Eg. Recurrence subgraphs are ordered
based on the highest RecMII value of the recurrence circuits contained in each subgraph,
in a decreasing order. The nodes that appear in more than one subgraph are removed from
all of them excepting the most restrictive subgraph in terms of RecMII . For instance, the
procedure Ordering Recurrences(G, L, List, h)
fThis procedure takes the dependence graph (G)g
fand the simplified list of recurrence subgraphs (L)g
fIt returns a partial list of ordered nodes (List)g
fand the resulting hypernode (h)g
List := Pre Ordering(G 0 , List, h);
while L 6= ; do
function Generate Subgraph(V , G)
fThis function takes the dependence graph (G) and a subset of nodes V g
fand returns the graph that consists of all the nodes in V and the edgesg
famong themg

Figure

9: Procedure to order the nodes in recurrence circuits
list of recurrence subgraphs associated with Figure 8c ffA, C, Dg, fB, C, Egg will be
simplified to the list ffA, C, Dg, fB, Egg.
The algorithm that orders the nodes of a grah with recurrence circuits (see Figure
takes as input a list L of the recurrence subgraphs ordered by decreasing values of their
RecMII . Each entry in this list is a list of the nodes traversed by the associated recurrence
subgraph. Trivial recurrence circuits, i.e. dependences from an operation to itself, do not
affect the preordering step since they do not impose scheduling constraints, as the scheduler
previously ensured that II - RecMII . The algorithm starts by generating the corresponding
subgraph for the first recurrence circuit, but without one of the backward edges that
causes the recurrence (we remove the backward edge with higher ffi (u;v)
). Therefore the
resulting subgraph has no recurrences and can be ordered using the algorithm without
recurrences presented in Section 3.1. The whole subgraph is reduced to the Hypernode.
Then, all the nodes in any path between the Hypernode and the next recurrence subgraph
are identified (in order to properly use the algorithm Search All Paths it is required that all
the backward edges causing recurrences have been removed from the graph). After that,
the graph containing the Hypernode, the next recurrence circuit, and all the nodes that are
in paths that connect them are ordered applying the algorithm without recurrence circuits
and reduced to the Hypernode. If there is no path between the Hypernode and the next
recurrence circuit, any node of the recurrence circuit is reduced to the Hypernode, so that
the recurrence circuit is now connected to the Hypernode.
A
F
G
IH
KA
F
G
I
KH
G
I
a) b) c) d) e)

Figure

10: Example for Ordering Recurrences procedure
This process is repeated until there are no more recurrence subgraphs in the list. At this
point all the nodes in recurrence circuits or in paths connecting them have been ordered
and reduced to the Hypernode. Therefore the graph that contains the Hypernode and the
remaining nodes, is a graph without recurrence circuits, that can be ordered using the
algorithm presented in the previous subsection.
For instance, consider the dependence graph of Figure 10a. This graph has two recurrence
subgraphs fA, C, D, Fg and fG, J, Mg. Next, we will illustrate the reduction of the
recurrence subgraphs:
1. The subgraph fA, C, D, Fg is the one with the highest RecMII . Therefore the algorithm
starts by ordering it. By isolating this subgraph and removing the backward
edge we obtain the graph of Figure 10b. After ordering this graph the list of ordered
nodes is (List = fA; C; D;Fg). When the graph of Figure 10b is reduced to the
Hypernode H in the original graph (Figure 10a), we obtain the dependence graph of

Figure

10c.
2. The next step is to reduce the following recurrence subgraph fG, J, Mg. For this
purpose the algorithm searches for all the nodes that are in all possible paths between
H and the recurrence subgraphs. Then, the graph that contains these nodes is
constructed (see Figure 10d). Since backward edges have been removed, this graph
has no recurrence circuits, so it can be ordered using the algorithm presented in the
previous section. When the graph has been ordered, the list of nodes is appended to
the previous one resulting in the partial list (List = fA; C; D;F; I; G; J; Mg). Then,
this subgraph is reduced to the Hypernode in the graph of Figure 10c producing the
graph of Figure 10e.
3. At this point, we have a partial ordering of the nodes belonging to recurrences, and
the initial graph has been reduced to a graph without recurrence circuits (Figure 10e).
This graph without recurrence circuits is ordered as presented in Subsection 3.1. So
finally the list of ordered nodes is List = fA; C; D;F; I; G; J; M;H;E;B; L; Kg.
3.3 Scheduling step
The scheduling step places the operations in the order given by the ordering step. The
scheduling tries to schedule the operations as close as possible to the neighbors that have
already been scheduled. When an operation is to be scheduled, it is scheduled in different
ways depending on the neighbors of these operations that are in the partial schedule.
ffl If an operation u has only predecessors in the partial schedule, then u is scheduled
as early as possible. In this case the scheduler computes the Early Start of u as:
Early Start
Where t v is the cycle where v has been scheduled, - v is the latency of v, ffi (v;u)
is the dependence distance from v to u, and PSP (u) is the set of predecessors of
u that have been previously scheduled. Then the scheduler scans in the partial
schedule for a free slot for the node u starting at cycle Early Start u until the cycle
Early Start u 1. Notice that, due to the modulo constraint, it makes no sense
to scan more than II cycles.
ffl If an operation u has only successors in the partial schedule, then u is scheduled as
late as possible. In this case the scheduler computes the Late Start of u as:
Late Start
Where PSS(u) is the set of successors of u that have been previously scheduled.
Then the scheduler scans in the partial schedule for a free slot for the node u starting
at cycle Late Start u until the cycle Late Start
ffl If an operation u has predecessors and successors, then the scheduler scans the partial
schedule starting at cycle Early Start u until the cycle min(Late Start
ffl Finally, if an operation u has neither predecessors nor successors, the scheduler computes
the Early Start of u as: Early Start scans the partial schedule
for a free slot for the node u from cycle Early Start u to cycle Early Start u
are found for a node, then the II is increased by 1. The scheduling
step is repeated with the increased II , which will result in more opportunities for finding
slots. An advantage of HRMS is that the nodes are ordered only once, even if the
scheduling step has to do several trials.
4 Evaluation of HRMS
In this section we present some results of our experimental study. First, the complexity and
performance of HRMS are evaluated for a benchmark suite composed of a large number of
Number of registers6080100
%of
loops L4 HRMS
L4 Top-down
L6 Top-down

Figure

cumulative distribution of register requirements of loop variants.
innermost DO loops in the Perfect Club [4]. We have selected those loops that include a
single basic block. Loops with conditionals in their body have been previously converted to
single basic block loops using IF-conversion [2]. We have not included loops with subroutine
calls or with conditional exits. The dependence graphs have been obtained using the
experimental ICTINEO compiler [3]. A total of 1258 loops, which account for 78% of
the total execution time 5 of the Perfect Club, have been scheduled. For these loops, the
performance of HRMS is compared with the performance of a Top-Down scheduler. Second,
we compare HRMS with other scheduling methods proposed in the literature using a small
set of dependence graphs for which there are previously published results.
4.1 Performance evaluation of HRMS
We have used two machine configurations to evaluate the performance of HRMS. Both
configurations have 2 load/store units, 2 adders, 2 multipliers and 2 Div/Sqrt units. We
assume a unit latency for store instructions, a latency of 2 for loads, a latency of 4 (con-
figuration L4) or 6 (configuration L6) for additions and multiplications, a latency of 17
for divisions and a latency of roots. All units are fully pipelined except the
Div/Sqrt units which are not pipelined at all.
In order to evaluate performance the execution time (in cycles) of a scheduled loop has
been estimated as the II of this loop times the number of iterations this loop performs (i.e.
the number of times the body of the loop is executed). For this purpose the programs of
the Perfect Club have been instrumented to obtain the number of iterations of the selected
loops.
HRMS achieved loops, which means that it is optimal in terms of
II for at least 97.5% of the loops. On average, the scheduler achieved an
5 Executed on an HP 9000/735 workstation.
HRMS Top-down HRMS Top-down
Memory
ideal
regs.
regs.

Figure

12: Memory traffic with infinite registers, 64 registers and registers.
HRMS Top-down HRMS Top-down
L4 L61030Cycles
regs.
regs.

Figure

13: Cycles required to execute the loops with infinite registers, 64 registers and
registers.
Considering dynamic execution time, the scheduled loops would execute at 98.4% of the
maximum performance.
Register allocation has been performed using the wands-only strategy using end-fit with
adjacency ordering. For an extensive discussion of the problem of allocating registers for
software-pipelined loops refer to [24].

Figure

11 compares the register requirements of loop-variants for the two scheduling
techniques (Top-down that does not care about register requirements and HRMS) for the
two configurations mentioned above. This figure plots the percentage of loops that can
been scheduled with a given number of registers without spill code. On average, HRMS
requires 87% of the registers required by the Top-down scheduler.
Since machines have a limited number of registers, it is also of interest to evaluate
the effect of the register requirements on performance and memory traffic. When a loop
requires more than the available number of registers, spill code has to be added and the
loop has to be re-scheduled. In [16] different alternatives and heuristics are proposed to
speed-up the generation of spill code. Among them, we have used the heuristic that spills
the variable that maximizes the quotient between lifetime and the number of additional
loads and stores required to spill the variable; this heuristic is the one that produces the
best results.

Figures

12 and 13 show the memory traffic and the execution time respectively of the
loops scheduled with both schedulers when there are infinite, 64 and registers available.
Notice that in general HRMS requires less memory traffic than Top-down when the number
of registers is limited. The difference in memory traffic requirements between both
schedulers increases as the number of available registers decreases. For instance, for configuration
L6, HRMS requires 88% of the traffic required by the Top-down scheduler if 64
registers are available. If only 32 registers are available, it requires 82.5% of the traffic
required by the Top-down scheduler.
In addition, assuming an ideal memory system, the loops scheduled by HRMS execute
faster than the ones scheduled by Top-down. This is because HRMS gives priority to
recurrence circuits, so in loops with recurrences usually produces better results than Top-
down. An additional factor that increases the performance of HRMS over Top-down is that
it reduces the register requirements. For instance, for configuration L6, scheduling the loops
with HRMS produces a speed-up over Top-down of 1.18 under the ideal assumption that
an infinite register file is available. The speed-up is 1.20 if the register file has 64 registers
and 1.25 if it has only registers.
Notice that for both schedulers, the most agressive configuration (L6) requires more registers
than the L4 configuration. This is because the degree of pipelining of the functional
units has an important effect on the register pressure [19, 16]. The high register requirements
of aggressive configurations produces a significant degradation of performance and
memory traffic when a limited number of registers is available [16]. For instance, the loops
scheduled with HRMS require 6% more cycles to execute for configuration L6 than for L4,
if an infinite number of registers is assumed. If only 32 registers are available, L6 requires
16% more cycles than L4.
4.2 Complexity of HRMS
Scheduling our testbench consumed 55 seconds in a Sparc-10/40 workstation. This time
compares to the 69 seconds consumed by the Top-Down scheduler. The break-down of the
scheduler execution time in the different steps is shown in Figure 14. Notice that in HRMS,
computing the recurrence circuits consumed only 7%, the pre-ordering step consumed 66%,
and the scheduling step consumed 27%. Even though most of the time is spent in the preordering
step, the overall time is extremely short. The extra time lost in pre-ordering the
nodes, allows for a very simple (and fast) scheduling step. In the Top-Down scheduler,
the pre-ordering step consumed a small percentage of the time but the the scheduling step
required a lot of time; when the scheduler fails to find an schedule with a given II , the
loop has to be rescheduled again with an increased initiation interval, and Top-Down has
to re-schedule the loops much more often than HRMS.
Time (seconds)
HRMS
Top-Down Scheduling
Priority function
Find recurrences and compute MII

Figure

14: Time to schedule all 1258 loops for the HRMS and Top-Down schedulers.
4.3 Comparison with other scheduling methods
In this section we compare HRMS with three schedulers: an heuristic method that does not
take into account register requirements (FRLC [27]), a life-time sensitive heuristic method
(Slack [12]) and a linear programming approach (SPILP [10]).
We have scheduled 24 dependence graphs for a machine with 1 FP Adder, 1 FP Mul-
tiplier, 1 FP Divider and 1 Load/Store unit. We have assumed a unit latency for add,
subtract and store instructions, a latency of 2 for multiply and load, and a latency of 17
for divide.

Table

1 compares the initiation interval II , the number of buffers (Buf) and the total
execution time of the scheduler on a Sparc-10/40 workstation, for the four scheduling
methods. The results for the other three methods have been obtained from [10] and the
dependence graphs to perform the comparison supplied by its authors. The number of
buffers required by a schedule is defined in [10] as the sum of the buffers required by each
value in the loop. A value requires as many buffers as the number of times the producer
instruction is issued before the issue of the last consumer. In addition, stores require one
buffer. In [20], it was shown that the buffer requirements provide a very tight upper bound
on the total register requirements.

Table

2 summarizes the main conclusions of the comparison. The entries of the table
represent the number of loops for which the schedules obtained by HRMS are better (II !),
equal (II =), or worse (II ?) than the schedules obtained by the other methods, in terms
Application HRMS SPILP Slack FRLC
Program II Buf Secs II Buf Secs II Buf Secs II Buf Secs
Liver Loop5 3 5
Linpack
Whets. Cycle1 4 4

Table

1: Comparison of HRMS schedules with other scheduling methods.
of the initiation interval. When the initiation interval is the same, it also shows the number
of loops for which HRMS requires less buffers (Buf !), equal number of buffers (Buf =),
or more buffers (Buf ?). Notice that HRMS achieves the same performance as the SPILP
method both in terms of II and buffer requirements. When compared to the other methods,
HRMS obtains a lower II in about 33% of the loops. For the remaining 66% of the loops
the II is the same but in many cases HRMS requires less buffers, specially when compared
with FRLC.
Finally Table 3 compares the total compilation time in seconds for the four methods.
Notice that HRMS is slightly faster than the other two heuristic methods; in addition, these
methods perform noticeably worse in finding good schedulings. On the other hand, the
linear programming method (SPILP) requires a much higher time to construct a scheduling
that turns out to have the same performance than the scheduling produced by HRMS. In
fact, most of the time spent by SPILP is due to Livermore Loop 23, but even without
taking into account this loop, HRMS is over 40 times faster.
Slack 7 1

Table

2: Comparison of HRMS performance versus the other 3 methods.
HRMS SPILP Slack FRLC
Compilation Time 0.32 290.72 0.93 0.71

Table

3: Comparison of HRMS compilation time to the other 3 methods.
Conclusions
In this paper we have presented Hypernode Reduction Modulo Scheduling (HRMS), a novel
and effective heuristic technique for resource-constrained software pipelining. HRMS attempts
to optimize the initiation interval while reducing the register requirements of the
schedule.
HRMS works in three main steps: computation of MII , pre-ordering of the nodes of
the dependence graph using a priority function, and scheduling of the nodes following
this order. The ordering function ensures that when a node is scheduled, the partial
scheduling contains at least a reference node (a predecessor or a successor), except for the
particular case of recurrences. This tends to reduce the lifetime of loop variants and thus
reduce register requirements. In addition, the ordering function gives priority to recurrence
circuits in order not to penalize the initiation interval.
We provided an exhaustive evaluation of HRMS using 1258 loops from the Perfect Club
Benchmark Suite. We have seen that HRMS generates schedules that are optimal in terms
of II for at least 97.4% of the loops. Although the pre-ordering step consumes a high
percentage of the total compilation time, the total scheduling time is smaller than the time
required by a convential Top-down scheduler. In addition, HRMS provides a significant
performance advantage over a Top-down scheduler when there is a limited number of
registers. This better performance comes from a reduction of the execution time and the
memory traffic (due to spill code) of the software pipelined execution.
We have also compared our proposal with three other methods: the SPILP integer
programming formulation, Slack Scheduling and FRLC Scheduling. Our schedules exhibit
significant improvement in performance in terms of initiation interval and buffer requirements
compared to FRLC, and a significant improvement in the initiation interval when
compared to Slack lifetime sensitive heuristic. We obtained similar results to SPILP, which
is an integer linear programming approach that obtains optimal solutions but has a prohibitive
compilation time for real loops.



--R

Software pipelining.
Conversion of control dependence to data dependence.
A uniform representation for high-level and instruction-level transformations
The Perfect Club benchmarks: Effective performance evaluation of supercomputers.
An approach to scientific array processing: The architectural design of the AP120B/FPS-164 family
Overlapped loop support in the Cydra 5.
Compiling for the Cydra 5.
Stage scheduling: A technique to reduce the register requirements of a modulo schedule.
Optimum modulo schedules for minimum register requirements.
Minimizing register requirements under resource-constrained software pipelining
Highly Concurrent Scalar Processing.

Circular scheduling: A new technique to perform software pipelining.
Software pipelining: An effective scheduling technique for VLIW machines.
A Systolic Array Optimizing Compiler.
Reducing the Impact of Register Pressure on Software Pipelined Loops.
Hypernode reduction modulo scheduling.
Register requirements of pipelined loops and their effect on performance.
Register requirements of pipelined processors.
A novel framework of register allocation for software pipelin- ing
Software pipelining in PA-RISC compilers
Iterative modulo scheduling: An algorithm for software pipelining loops.
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing.
Register allocation for software pipelined loops.

Parallelisation of loops with exits on pipelined architectures.
Decomposed software pipelining: A new perspective and a new approach.
Enhanced modulo scheduling for loops with conditional branches.
Modulo scheduling with multiple initiation intervals.
--TR

--CTR
Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
David Lpez , Josep Llosa , Mateo Valero , Eduard Ayguad, Widening resources: a cost-effective technique for aggressive ILP architectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.237-246, November 1998, Dallas, Texas, United States
David Lpez , Josep Llosa , Mateo Valero , Eduard Ayguad, Cost-Conscious Strategies to Increase Performance of Numerical Programs on Aggressive VLIW Architectures, IEEE Transactions on Computers, v.50 n.10, p.1033-1051, October 2001
Josep Llosa , Eduard Ayguad , Antonio Gonzalez , Mateo Valero , Jason Eckhardt, Lifetime-Sensitive Modulo Scheduling in a Production Environment, IEEE Transactions on Computers, v.50 n.3, p.234-249, March 2001
software pipelining;register allocation;register spilling;loop scheduling;instruction scheduling