Quantitative Evaluation of Register Pressure on Software Pipelined Loops.
Software Pipelining is a loop scheduling technique that extracts loop parallelism by overlapping the execution of several consecutive iterations. One of the drawbacks of software pipelining is its high register requirements, which increase with the number of functional units and their degree of pipelining. This paper analyzes the register requirements of software pipelined loops. It also evaluates the effects on performance of the addition of spill code. Spill code is needed when the number of registers required by the software pipelined loop is larger than the number of registers of the target machine. This spill code increases memory traffic and can reduce performance. Finally, compilers can apply transformations in order to reduce the number of memory accesses and increase functional unit utilization. The paper also evaluates the negative effect on register requirements that some of these transformations might produce on loops.
Introduction
Current high-performance floating-point microprocessors try to maximize the exploitable
parallelism by: heavily pipelining functional units (1;2) , making aggressive
use of parallelism (3;4) , or a combination of both (5) which is the trend in current
and future high-performance microprocessors. To exploit effectively this amount of
available parallelism, aggressive scheduling techniques such as software pipelining are
required.
Software pipelining (6) is an instruction scheduling technique that exploits the
Instruction Level Parallelism (ILP) of loops by overlapping the execution of successive
iterations. There are different approaches to generate a software pipelined schedule
for a loop (7) . Modulo scheduling is a class of software pipelining algorithms that
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. Modulo scheduling was proposed at the beginning of the 80s (8) .
Since then, many research papers have appeared on the topic (9;10;11;12;13;14;15;16) , and
it has been incorporated into some production compilers (17;18) .
The drawback of aggressive scheduling techniques such as software pipelining is
that they increase register requirements. In addition, increasing either the stages of
functional units or the number of functional units, which are the current trends in
microprocessor design, tends to increase the number of registers required by software
pipelined loops (19) .
The register requirements of a schedule are of extreme importance for compilers
since any valid schedule must fit in the available number of registers of the target ma-
chine. In this way there has been a research effort to produce optimal/near-optimal
modulo schedules with minimum/reduced register requirements. The optimal methods
are mainly based on linear programming approaches (20;21) . Unfortunately, optimal
techniques have a prohibitive computational cost which make them impractical
for product compilers. Some practical modulo scheduling approaches use heuristics to
produce near-optimal schedules with reduced register requirements (11;16;22) . Other
approaches try to reduce the register requirements of the schedules by applying a
post-pass process (23;24) .
There have been proposals to perform register allocation for software pipelined
loops (25;26;27) . If the number of registers required is larger than the available number
of registers, spill code has to be introduced to reduce register usage. Different alternatives
to generate spill code for software pipelined loops have been proposed and
evaluated in (28) . This spill code can also reduce performance. In this paper we show
that the performance and memory traffic of aggressive (in terms of ILP) machines
are heavily degraded due to a lack of registers.
To avoid this performance degradation big register files are required. In addition,
the number of read and write ports increases with the number of functional units.
The number of registers and the number of ports have a negative effect on the area
required by the register file (29) and on the access time to the register file (30) . Some
new register file organizations have been proposed to have big register files (in terms
of registers and access ports) without degrading either area or access time (31;32;33;34) .
Some of these organizations have been used, combined with register-sensitive software
pipelinig techniques (35) , resulting in better performance. This shows that most of
the techniques for reducing the effects of register pressure are complementary.
In this paper, register requirements of pipelined floating-point intensive loops are
evaluated. Several studies are performed. First, the register requirements of loop
invariants, which are a machine-independent characteristic of the loops, are studied
in Section 3. Section 4 carries out a study of the register requirements of loop variants
as a function of the latency and the number of functional units. Section 5 studies
the cumulative register requirements of both (loop variants and invariants) and show
that loops with high register requirements represent a high percentage of the execution
time of the Perfect Club. Section 6 considers the effects of a limited size register file
on performance and memory traffic; for this purpose spill code has been added to
those loops that require more registers than are available. Finally, Section 7 analyzes
the effects on the register requirements of some optimizations that try to improve
performance by reusing data and increasing functional unit usage.
2. Related Concepts and Experimental Framework
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 the initiation interval (II).
The execution of a loop can be divided into three phases: a ramp up phase that
fills the software pipeline, a steady state phase where the software pipeline achieves
maximum overlap of iterations, and a ramp down phase that drains the software
pipeline. 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 corresponds to one stage 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 (MII= max (RecMII, ResMII)). The reader is referred to (18;13) for an
extensive dissertation on how to calculate ResMII and RecMII.
2.2. Register Requirements
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;
each invariant requires one register 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. Lifetimes of loop variants can be
measured in different ways depending on the execution model of the machine. We
assume that a variable is alive from the beginning of the producer operation, until
the start of the last consumer operation.
By overlapping the lifetimes of the different iterations, a pattern of length II cycles
that is indefinitely repeated is obtained. This pattern indicates the number of values
that are live at any given cycle. As it is shown in (26) , the maximum number of
simultaneously live values (MaxLive) is an accurate approximation of the number of
registers required by the schedule.
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 (MVE) (36) , i.e., 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 (37) . In this paper
we assume the presence of rotating register files.
2.3. Experimental Framework
The experimental evaluation has been done using all the innermost loops of the
Perfect Club Benchmark Suite (38) that are suitable for software pipelining. These
loops have been obtained with the ICTINEO compiler (39) . ICTINEO is a source-to-
source restructurer developed on top of Polaris (40) with an internal representation that
combines both high and low-level information. It includes some basic transformations
that allow us to obtain optimized data dependence graphs.
A total of 1258 loops suitable for software pipelining have been used. This set
includes all the innermost loops that do not have subroutine calls or conditional exits.
Loops with conditional structures in their bodies have been IF-converted (41) , with
the result that the loop now looks like a single basic block. The loops represent 78% of
the total execution time of the Perfect Club measured on a HP-PA 7100. In addition,
to show the effects of aggressive optimizations in individual loops, we have also used
some Livermore Loops (42) .
The loops have been scheduled for a wide range of VLIW-like target configura-
tions, with different number of functional units and latencies. Table 1 shows the
different configurations used along the paper. All functional units are fully pipelined,
except the divider, which is not pipelined at all. We labeled the different configurations
by PxLy where x is the number of functional units of each kind and y is the
latency (number of stages) of the mostly used functional units, that is, the adder
and the multiplier. We considered a constant latency for loads, stores, divisions and
square roots independently of the configuration.
Different metrics are used along the paper to evaluate performance. On the one
side, the register requirements are evaluated computing the maximum number of
simultaneously live values MaxLive. It has been shown (26) that some allocation
strategies almost always achieve the MaxLive lower bound. In particular, the wands-
only strategy using end-fit with adjacency ordering almost never requires more than
MaxLive registers. Second, execution times are approximated as the II obtained
after modulo scheduling times the trip count of the loop. Finally, memory traffic is
approximated evaluating the number of memory accesses that are needed to execute
a loop, considering both the memory accesses defined in the graph and the spill code
introduced due to having a finite register file.
3. Register Requirements of Loop Invariants
Loop invariants are values that are repeatedly used by a loop at each iteration,
but never written by it. That is, they are defined before entering the loop, are used
by it, and are not redefined at least until the loop has finished.
Loop-invariant variables can be either stored in registers or in memory but, since
memory bandwidth is without doubt the most performance limiting factor in current
processors, even the most simple optimizing compilers try to hold them in registers
during the execution of the loop. For this purpose loop-invariant variables are loaded
from memory to a register before entering the loop that uses them. Even assuming no
memory bandwidth restrictions loading these variables to registers before entering the
loop saves instruction bandwidth in load/store architectures, i.e. almost all current
processors.
Another source of loop invariants are the invariant computations (i.e. computations
that produce the same result during all the iterations of the loops). These
computations can be extracted out of the loop -where they are performed at every
iteration- and computed only once before entering the loop. Also because of memory
bandwidth and instruction bandwidth, the partial result of these computations is held
in registers.
This optimization is termed loop-invariant removal and is one of the optimizations
performed by the ICTINEO compiler. In fact, if we consider load and store
operations as computations, they also can be extracted during the loop-invariant
removal optimization. Figure 1a shows an example. Figure 1b shows a low-level
representation of the loops before removing loop-invariant computations. Figure 1c
shows the same loops after removing loop-invariant computations. Notice that q and
are loop-invariant variables for both loops, so they can be loaded to registers before
entering them. C(j) is also a loop-invariant variable for the innermost loop, so it can
be extracted from it, but not from the outermost loop. Because v1 and v2 are loop
invariants (which are assumed to be allocated in registers), the computation v3 is a
loop-invariant computation, and therefore can be extracted from the innermost loop.
The extraction of loop invariants has lead to a smaller innermost loop -the one
that is executed most of the time- with less operations. In the original one there
were: 1 addition, 2 multiplications and 5 memory accesses, while in the optimized
one there are only 1 addition, 1 multiplication and 2 memory accesses.
The ICTINEO compiler performs -among other optimizations- an aggressive extraction
of loop-invariant computations. We have used the optimized dependence
graph to evaluate the register requirements of loops due to loop invariants. Figure 2
shows the cumulative distribution of the requirements for loop invariants for all 1258
loops. In general loops have very few loop invariants. For instance 25% of the loops
have no loop invariants and 95% of the loops have 8 or less invariants. Nevertheless
a few loops have a high number of loop invariants. For instance 9 loops have more
than invariants and 1 of them requires 68 loop invariants.
4. Register Requirements of Loop Variants
Unlike loop invariants, the number of registers required by loop variants is a schedule
dependent characteristic. So, the register requirements depend on the scheduling
technique, and the target machine configuration for which the scheduling is performed,
as well as the topology of the loop.
In this section we are interested in the effects of the machine configuration on the
register requirements. The main characteristics that influence the final schedule, and
therefore the register requirements, are the number of stages of functional units and
the number of functional units. That is, the degree of pipelining and the degree of
parallelism. For this purpose we have generated the software pipelined schedule for
all the Perfect Club loops for the target configurations shown in Table 1.

Figure

3 shows the cumulative distribution of registers for each configuration.
Notice that when the product of the latency of functional units and the number of
functional units goes up, the number of registers needed by the loops also increases.
Note that the number of functional units has a slightly bigger effect on the number
of registers required than the degree of pipelining has. This is mainly due to the fact
that the latency of some functional units is kept constant for all the configurations.
There is a small number of loops (6%) that do not require any register for loop
variants. The loop bodies of these loops have no invariants because they only have
store operations. These loops are typically used to initialize data structures.
There is another region (6% to 30%) where the loops have few register requirements
and where the register requirements of the loops are not influenced by the
number of stages. This is due to the fact that these loops have no arithmetic opera-
tions, that is, their bodies only have load and store operations. These loops have few
register requirements to hold the values between loads and stores. They are basically
used to copy data structures.
5. Combined Register Requirements
Although some special architectures, such as the Cydra-5 (43) , have separated register
files for loop-invariant variables (global register file) and loop-variant variables
(rotating register file), all the current superscalar microprocessors, for which software
pipelining can also be applied, have a single register file to store both sets of variables.
Therefore it is of great interest to know the combined register pressure of loop-variant
variables plus loop-invariant variables. Figure 4 shows the cumulative distribution
of the register requirements of the loops of the Perfect Club when software pipelined
for the configurations of Table 1.
It is interesting to notice that 96% of the loops can be scheduled with registers
and without adding spill code for the less aggressive configuration (P1L2). On
the contrary only 85% of the loops can be scheduled with registers for the more
aggressive configuration (P2L6). If 64 registers were available we would be able to
schedule 99.5% and 96% of the loops respectively. Also, approximately 60% of the
loops (it varies depending on the configuration) require a small number of registers
or less).
From these figures, one can conclude that register requirements are not extremely
high, and that 64 registers might seem enough for the configurations used. Even
though, we have observed that small loops represent a small percentage of the execution
time and that most of the time is spent in big loops which, in general, have
higher register requirements.

Figure

5 shows the dynamic register requirements, where each loop has been
weighted by its execution time. The graph of Figure 5 is similar to the one of Figure
4 but instead of representing the percentage of loops that require a certain amount
of registers, it represents the percentage of time spent on loops that require a certain
amount of registers.
Data gathered from this figure shows that small loops requiring less that 8 registers
portion of the execution time (about 15%). If only 32 registers are
available, the loops that can be scheduled without adding spill code represent only
between 67% and 52% of the execution time. And even for a machine with 64 registers,
the loops that can be scheduled without adding spill code represent only between 78%
and 69% of the execution time. Even more, a big percentage of the execution time of
the Perfect Club is spent on a few loops that require more than 100 registers.
6. Effects of a Limited Register File
In the previous sections an infinite number of registers has been assumed. In this
section we study the effects of having a limited amount of registers on performance.
When there is a limited number of registers and the register allocator fails to find a
solution with the number of registers available, some additional action must be taken.
In (28) we have proposed several alternatives to schedule software pipelined loops with
register constraints. For the purposes of our experiments, we use the best option, in
terms of performance for the loops, to add spill code.
Current microprocessors have only floating-point registers and 32 integer reg-
isters. We think that future generations of microprocessors will enlarge the register
file to 64 registers (at least for the floating point-register file). Since this study is targeted
to floating point intensive applications, we study the effects of having register
files with registers and with 64 registers compared to the ideal case of having an
infinite number of registers.
Adding spill code to generate a valid schedule with a given number of registers
produces two negative effects. One of them can hurt performance indirectly, since
spill code adds new load and store operations, which might interfere in the memory
subsystem or cause additional cache misses. The other effect, that affects performance
directly, is that if new operations are added it might be necessary to increase the II
of the loop, reducing the throughput even in the hypothetical case of having a perfect
memory system.

Figure

6 shows the number of memory accesses required to execute all the loops for
the six configurations we use. Notice that the number of memory accesses is the same
for all the configurations if no spill code is added. Also predictable is the fact that
the number of memory accesses increases as the number of registers is reduced. It can
also be observed that the growth of memory accesses is more dramatic for aggressive
configurations. For instance the configuration P2L6 with 64 registers requires 52%
more accesses than an ideal machine with an infinite register file and 176% more
memory accesses if it only has registers. Anyway it is difficult to predict the
performance degradation that these additional accesses can have without simulating
the memory subsystem, which is out of the scope of this paper.
In any case, we can easily predict the direct effect on performance that the spill
code has on the execution time of the loops because of larger IIs. Figure 7 shows the
number of cycles required to execute all the loops for the six configurations, with an
infinite number of registers, with 64 registers, and with registers. Notice that, as
expected, fewer registers mean lower performance (more cycles are required to execute
all the loops). In general, the more aggressive the machine configuration is, the bigger
the performance degradation. For instance, a P1L6 machine can have a speed-up of
1.19 if the register file is doubled from 32 registers to 64 registers. Instead, a P2L6
machine will have a speed-up of 1.29 by doubling the register file.
Through the data gathered from this experiment it can be concluded that simply
adding functional units without caring about the number of registers results in
performance figures lower than expected (due to the negative effects of the additonal
spill code). For instance, doubling the number of functional units (i.e. going from
P1L6 to P2L6) produces a speed-up of 1.59 if the number of registers is not limited.
For machines with 64 and 32 registers, the speed-up is 1.56 and 1.43, respectively.
However, if the number of register is doubled together with the number of functional
units (i.e. from P1L6 with 32 registers to P2L6 with 64 registers), the speed-up is
1.85.
7. Optimizations and Register Requirements
In addition to the effect of latency and the number of functional units, register
requirements of loops can also increase when certain optimizations are applied to the
loops. In order to see how some 'advanced' optimizations affect the register requirements
of loops we have hand-optimized some of the Livermore Loops and a few loops
from the Perfect Club, where the optimizations are applicable. We have not considered
common optimizations such as loop-invariant removal, common subexpression
elimination, redundant load and store removal, or dead code removal which we assume
are applied by any compiler. In the following subsections, we present a brief
description of the optimizations studied and the effect that applying the optimizations
has on both performance and register requirements.
7.1. Loop Unrolling
Loop unrolling (44) is an optimization used by the compilers of current micro-
processors. It allows a better usage of resources because several iterations can be
scheduled together, increasing the number of instructions available to the scheduler.
It also reduces the loop overhead caused by branching and index update.
In our case we achieve efficient iteration overlapping through Software Pipelining.
Unrolling is required to match the number of resources required by the loop with the
resources of the processor and also to schedule loops with fractional MII (45) . As an
example, assume a loop with 5 additions and a processor with 2 adders. If there are
no recurrences and additional resources do not limit the scheduling, this loop can be
scheduled with cycles. The loop will be executed at 83.3% of the peak
machine performance. If the loop is unrolled once before scheduling, we obtain a new
loop with 10 additions. This new loop can be scheduled with an
but each iteration of the new loop corresponds to two iterations of the original loop, so
on average an iteration is completed in 2.5 cycles. The unrolled loop can be executed
at 100% of the peak machine performance. Unroll increases the register requirements
because bigger loops have more temporal variables to store, which usually requires
more registers.

Table

2 shows the effects of unrolling some loops on their register requirements.
For the loops used, unrolling them once results in a better usage of the available
resources. Unfortunately it also produces an increase in the register requirements
which, as we have seen in Section 6, can degrade performance if the number of available
registers is less than the registers required.
7.2. Common Subexpression Elimination Across Iterations
Common subexpression elimination across iterations (CSEAI) is an extension for
inner loops of the common subexpression elimination optimization applied by almost
all optimizing compilers. It consists of the reuse of values generated in previous
iterations. The reused data has to be stored in a register and, since the value is used
across iterations, more than one physical register is required in order not to overwrite
a live value with a new instantiation of the same variable. This is an extension to loops
of the 'common subexpression elimination' optimization. It is more sophisticated in
the sense that it can only be applied to loops and that it requires a dependence
analysis to know which values of the current iteration are used in further iterations.
The objective of this optimization will be to reduce the number of operations of the
loop body which can lead to a lower II. Even if after applying the optimization the
final II is not lowered, it is worthwhile applying it if the number of memory accesses
is reduced.
As an example consider the loop of Figure 8a whose unoptimized body is shown in
Figure 8b. We have added to each of the loop variants generated by the operations a
subindex associated to the iteration where it is generated. For instance
represents
the value generated by the first operation at iteration i.
A conventional common subexpression elimination step will recognize that both
load the same value Z(i+1). Therefore, operation V 4 i
be removed and all subsequent uses of V 4 i
be substituted by uses of V 2 i
. This
optimization produces as output the loop shown in Figure 8c. Notice that because of
this optimization the loop requires only 7 operations instead of 8.
The common subexpression elimination optimization can detect that the value of
V 3 at the previous iteration (V 3
is equivalent to the value of
. Therefore the operations required to calculate V 6 i
can be removed, and all uses
of
substituted by V 3
. The same can be done with operations
producing the loop body of Figure 8d. Notice that the resulting
loop body has only 4 operations.

Table

3 shows the II and the memory traffic of some loops with and without
applying CSEAI. Notice that in all cases there are improvements in memory traffic,
in the II or in both. It is also interesting to notice that, even though the optimization
reduces the number of operations of the loops and therefore the number of lifetimes
per iteration, the register requirements increase in most cases. This is mainly due to
the fact that some loop variants must be preserved across several iterations.
7.3. Back-substitution
Back-substitution (37) is a technique that increases the parallelism of loops that
have single recurrences and therefore limited parallelism, but it increases the number
of operations executed per iteration. For instance, consider the Livermore Loop 11
shown in Figure 9a. There is a recurrence of weight 1 that limits the MII . If we
have an adder with 6 cycles of latency, this loop can be scheduled with an II of 6
cycles. Using back-substitution once, the loop becomes the one shown in Figure 9b.
Now the recurrence that limits the schedule of the loop has a weight of 2. Obviously
in this case we have to do two additions instead of one, but this transformed loop
can be executed with an II of 3 cycles doubling the performance. To avoid part
of this increase in operations, other optimizations can be applied such as common
subexpression elimination across iterations. In this example it reduces the number of
loads, but not the number of additions.
A way of further reducing the increment of operations is to perform unroll as well
as back-substitution. If we apply unroll to Livermore Loop 11 together with back-substitution
we can obtain the loop of Figure 9c. Notice that in this loop we require
3 additions to compute two iterations of the original loop. The loop of Figure 9c can
be executed with an II of 6 cycles but it performs two iterations, so the performance
is the same as in the loop of Figure 9b and requires fewer operations.
When back-substitution is applied the number of operations per iteration is in-
creased, and the II is reduced. In general, bigger loops require more registers because
they have more temporal values to store; in addition a reduced II requires more registers
for the same temporal values, because new values are created in each iteration.

Table

4 shows the effect on both performance and register requirements when applying
back-substitution to Livermore Loops 11 and 5. Notice that for loop 5 in some
cases the II is 13. This is because, in those cases, the scheduler used fails to find a
schedule in 12 cycles, even though it exists.
7.4. Blocking
Blocking at the register level is a well-known optimization in the context of dense
matrix linear algebra (46) . Blocking is a transformation applied to multiple nested
loops that finds opportunities for reuse of subscripted variables and replaces the
memory references involved by references to temporary scalar variables allocated in
registers.
Blocking basically consists of unrolling the outer loops and restructuring the body
of the innermost loop so that the memory references that are reused in the same
iteration are held in registers for further uses. Blocking reduces the number of memory
accesses, so if the loop is memory-bound, a reduction of the number of memory
references improves the maximum performance. Also, a reduction of the memory
references can improve performance due to less interference in the memory subsystem.
Finally, if the innermost loop is bound by recurrences, doing several iterations of the
outermost loops, in one iteration of the innermost loop, can improve the resource
usage.
Unfortunately, blocking increases the size of the loop, which in general increases
the register requirements. It also enlarges the lifetimes of some loop variants, which
must be stored in registers for a longer time because they are reused later. This
enlargement of lifetimes also contributes to an increase of the register requirements
of the transformed loop versus the original one. Table 5 shows the II , the effective II
per iteration, the memory traffic and the registers required when blocking is applied
to a basic matrix by matrix kernel.
8. Conclusions
In this paper we have evaluated the register requirements of software pipelined
loops. We have evaluated the register requirements of loop invariants and loop variants
of the loops of the Perfect Club. We have shown empirically that the register
requirements of loop variants increases with the latency and the number of functional
units. These results corroborate the theoretical study done in (19) . We have also
shown that loops with high register requirements take up an important proportion of
the execution time of some representative numerical applications.
We have also evaluated the effect of register file size on the number of memory
accesses and on the performance. We have shown that the memory traffic can have
a high growth if the register file is small and the machine configuration is very ag-
gressive. Also performance (even under the hypothesis of a perfect memory system)
is degraded with small register files.
Finally, we have done a limited evaluation of the effects of some advanced opti-
mizations. We have shown that these advanced optimizations increase performance
and reduce memory traffic at the expense of an increase in the register requirements.
This suggests that, in practice, the optimizations must be performed carefully. If a
loop is excessively optimized, the high register requirements can offset the benefits of
the optimization applied, and even produce worse results.
As future work, we will integrate those advanced optimizations in the ICTINEO
compiler in order to perform an extensive evaluation of the effect of those optimizations
on performance and the tradeoffs with the performance degradation due to the
higher register requirements.

Acknowledgements

This work has been supported by the Ministry of Education of Spain under contract
TIC 429/95, and by CEPBA (European Center for Parallelism of Barcelona).



--R


The Mips R4000 processor.
Next generation of the RISC System/6000 family.

Superscalar instruction execution in the 21164 Alpha microprocessor.
An approach to scientific array processing: The architectural design of the AP120B/FPS-164 family
Software pipelining.
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing.
Software pipelining: An effective scheduling technique for VLIW ma- chines
Circular scheduling: A new technique to perform software pipelining.

Parallelisation of loops with exits on pipelined architectures.
Iterative modulo scheduling: An algorithm for software pipelining loops.
A realistic resource-constrained software pipelining algo- rithm
Modulo scheduling with multiple initiation inter- vals
Hypernode reduction modulo scheduling.
Software pipelining in PA-RISC compilers
Compiling for the Cydra 5.
Register requirements of pipelined processors.
Minimal register requirements under resource-constrained software pipelining
Optimum modulo schedules for minimum register requirements.
Swing modulo scheduling: A lifetime
Stage scheduling: A technique to reduce the register requirements of a modulo schedule.
RESIS: A new methodology for register optimization in software pipelining.
Register allocation using cyclic interval graphs: A new approach to an old problem.
Register allocation for software pipelined loops.
The meeting a new model for loop cyclic register allocation.
Heuristics for register-constrained software pipelining

Principles of CMOS VLSI Design: A systems Per- spective
Partitioned register files for VLIWs: A preliminary analysis of tradeoffs.
Using Sacks to organize register files in VLIW machines.

Digital 21264 sets new standard.
Reducing the Impact of Register Pressure on Software Pipelining.
A Systolic Array Optimizing Compiler.
Overlapped loop support in the Cydra

The Perfect Club benchmarks: Effective performance evaluation of supercomputers.
A uniform representation for high-level and instruction-level transformations
POLARIS: The next generation in parallelizing compilers.
Conversion of control dependence to data dependence.
The Livermore FORTRAN kernels: A computer test of the numerical performance range.
The Cydra 5 departmental super- computer: design philosophies
Unrolling loops in FORTRAN.
Software pipelining: A comparison and improvement.
Improving register allocation for subscripted variables.
--TR
Principles of CMOS VLSI design: a systems perspective
Software pipelining: an effective scheduling technique for VLIW machines
The Cydra 5 Departmental Supercomputer
Overlapped loop support in the Cydra 5
Improving register allocation for subscripted variables
Parallelization of loops with exits on pipelined architectures
Circular scheduling
Register allocation for software pipelined loops
Register requirements of pipelined processors
Partitioned register files for VLIWs
Lifetime-sensitive modulo scheduling
Compiling for the Cydra 5
Designing the TFP Microprocessor
Iterative modulo scheduling
Minimizing register requirements under resource-constrained rate-optimal software pipelining
Software pipelining
Optimum modulo schedules for minimum register requirements
Modulo scheduling with multiple initiation intervals
Stage scheduling
Hypernode reduction modulo scheduling
Heuristics for register-constrained software pipelining
Software pipelining
A Systolic Array Optimizing Compiler
Conversion of control dependence to data dependence
The Mips R4000 Processor
Superscalar Instruction Execution in the 21164 Alpha Microprocessor
RESIS
Using Sacks to Organize Registers in VLIW Machines
Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing
Non-Consistent Dual Register Files to Reduce Register Pressure
Swing Modulo Scheduling

--CTR
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Software and hardware techniques to optimize register file utilization in VLIW architectures, International Journal of Parallel Programming, v.32 n.6, p.447-474, December 2004
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
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Two-level hierarchical register file organization for VLIW processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.137-146, December 2000, Monterey, California, 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
Javier Zalamea , Josep Llosa , Eduard Ayguad , Mateo Valero, Improved spill code generation for software pipelined loops, ACM SIGPLAN Notices, v.35 n.5, p.134-144, May 2000
SOFTWARE PIPELINING;REGISTER REQUIREMENTS;SPILL CODE;LOOP TRANSFORMATIONS;PERFORMANCE EVALUATION