An empirical study of decentralized ILP execution models.
Recent fascination for dynamic scheduling as a means for exploiting instruction-level parallelism has introduced significant interest in the scalability aspects of dynamic scheduling hardware. In order to overcome the scalability problems of centralized hardware schedulers, many decentralized execution models are being proposed and investigated recently. The crux of all these models is to split the instruction window across multiple processing elements (PEs) that do independent, scheduling of instructions. The decentralized execution models proposed so far can be grouped under 3 categories, based on the criterion used for assigning an instruction to a particular PE. They are: (i) execution unit dependence based decentralization (EDD), (ii) control dependence based decentralization (CDD), and (iii) data dependence based decentralization (DDD). This paper investigates the performance aspects of these three decentralization approaches. Using a suite of important benchmarks and realistic system parameters, we examine performance differences resulting from the type of partitioning as well as from specific implementation issues such as the type of PE interconnect.We found that with a ring-type PE interconnect, the DDD approach performs the best when the number of PEs is moderate, and that the CDD approach performs best when the number of PEs is large. The currently used approach---EDD---does not perform well for any configuration. With a realistic crossbar, performance does not increase with the number of PEs for any of the partitioning approaches. The results give insight into the best way to use the transistor budget available for implementing the instruction window.
Introduction
To extract significant amounts of parallelism from sequential
programs, instruction-level parallel (ILP) processors often
perform dynamic scheduling. The hardware typically
collects decoded instructions in an instruction window, and
executes instructions as and when their source operands become
available. In going from today's modest issue rates
to 12- or 16-way issue, centralized dynamic schedulers face
complexity at all phases of out-of-order execution [2] [10].
The hardware needed to forward new results to subsequent
instructions and to identify ready-to-execute instructions
from the instruction window limits the size of the hardware
window. It is very important, therefore, to decentralize the
dynamic scheduling hardware.
The importance of decentralization is underscored in recently
developed processors/execution models such as the
MIPS R10000 [20] and R12000, the DEC Alpha 21264 [7],
the multiscalar model [4] [14], the superthreading model [17],
the trace processing model [13] [15] [19], the MISC (Multiple
Instruction Stream Computer) [18], the PEWs (Parallel Execution
model [6] [11], and the multicluster model
[3]. All of these execution models split the dynamic instruction
window across multiple processing elements (PEs) so
as to do dynamic scheduling and parallel execution of in-
structions. Dynamic scheduling is achieved by letting each
execute instructions as and when their operands become
available.
An important issue pertaining to decentralization is the criterion
used for partitioning the instruction stream among
the PEs. Three types of decentralization approaches have
been proposed based on the criterion they use for this parti-
tioning: (i) Execution unit Dependence based Decentralization
(EDD), (ii) Control Dependence based Decentralization
(CDD), and (iii) Data Dependence based Decentralization
(DDD). The first category groups instructions that use the
same execution unit-such as an adder or multiplier-into
the same PE. Examples are the R10000, R12000, and Alpha
21264. The second category groups control-dependent instructions
into the same PE. The multiscalar, superthread-
ing, and trace processing models come under this category.
The last category groups data-dependent instructions into
the same PE. Examples are the MISC, PEWs, and multi-cluster
models.
Each of the three categories has different hardware requirements
and trade-offs. This paper reports the results of a
set of experiments that were conducted to provide specific,
quantitative evaluations of different trade-offs. We address
the following specific questions:
What kind of programs benefit from each kind of partitioning

ffl How well does performance scale with each decentralization
ffl How much benefit would there be if a crossbar is used
to interconnect the PEs?
The question of how to select the best decentralization approach
to use at each granularity of parallelism is an important
one, and we discuss how this might be accomplished. Of
more immediate concern is the question of whether it is even
worth attempting to use such decentralization techniques for
more than a few PEs. While we do not yet know the exact
shape these execution models will take in the future,
we show that if the right choices are made, these decentralization
approaches can provide reasonable improvements in
instruction completion rate without much of an impact on
the cycle time.
The rest of this paper is organized as follows. Section 2 provides
background and motivation behind decentralization
of the dynamic scheduling hardware. It also describes the
three decentralization approaches under investigation. Section
3 describes our experimentation methodology. Section
presents detailed simulation results of the different decentralization
approaches. In particular, it examines the impact
of increasing the number of PEs, and the effects of two different
PE interconnection topologies. Section 5 presents a
discussion of the results, and the conclusions of this paper.
Decentralized ILP Execution Models
Programs written for current instruction set architectures
are generally in control-driven form, i.e., control is
assumed to step through instructions in a sequential or-
der. Dynamically scheduled ILP processors convert the total
ordering implied in the program into a partial ordering
determined by dependences on resources, control, and
data. This involves identifying instructions that are mutually
resource-independent, control-independent, and data-
independent. In order to scale up the degree of multiple is-
sue, resources that are in high demand are decentralized. To
more reordering and parallel execution of instruc-
tions, constraints due to resource dependences are overcome
(i) by replicating resources such as the fetch unit, the decode
unit, the physical registers, and the execution units (EUs)
(i.e., functional units), and (ii) by providing multiple banks
of resources such as the Dcache, as shown in Figure 1(a).
2.1 Decentralizing the Dynamic Scheduler
On inspecting the block diagram of Figure 1(a), we can see
that the important structures that remain to be decentralized
are the dynamic scheduler (DS), the register rename
Dynamic
(DS)
Scheduler
Control Misprediction Information
ISA-visible
Registers
Decode
Units
Register
Rename
Unit
Control
Flow
Icache
Physical
Registers
Memory
Address
Resolution
Dcache
Banks
(a)
EU
EU
EU
EU
EU
EU
EU
EU
Dynamic
(DS)
Scheduler
Dynamic
(DS)
Scheduler
Dynamic
(DS)
Scheduler
Dynamic
(DS)
Scheduler
Control Misprediction Information
Flow
Control Instruction
ISA-visible
Registers
ICN
Distribution
Unit
Address
Dcache
Banks
Memory
Resolution
(b)

Figure

1: Generic Organization of
Dynamically Scheduled ILP Processors
(a) Centralized Scheduler; (b) Decentralized Scheduler
unit, and the memory address resolution unit 1 . Incidentally,
these are the most difficult parts to decentralize because
they deal with inter-instruction dependences, which preclude
decentralization by mere replication. Of these parts,
the DS is the hardest to decentralize because it often needs
to handle all of the active instructions that are simultaneously
present in the processor. Detailed studies with 0.8-m,
0.35-m, and 0.18-m CMOS technology [10] also confirm
that a centralized DS does not scale well. Thus, it is important
to decentralize the DS. Many researchers have proposed
decentralizing the DS with the use of multiple PEs,
each having a set of EUs, as shown in Figure 1(b).
In the decentralized processor, the dynamic instruction stream
is partitioned across the PEs, which operate in parallel. The
1 The complexity of these structures can be partly reduced by off-loading
part of their work to special hardware that is not in the critical
path of program execution [8] [9] [19].
instructions assigned to PEs can have both control dependences
and data dependences between them. A natural
question that arises at this point is: on what basis should instructions
be distributed among the decentralized PEs? The
criterion used for partitioning the instruction stream is very
important, because an improper partitioning could in fact
increase inter-PE communication, and degrade performance!
True decentralization should not only aim to reduce the demand
on each PE, but also aim to minimize the demand
on the PE interconnect by localizing a major share of the
inter-instruction communication occurring in the processor
to within the decentralized PEs.
The three current approaches for grouping instructions into
PEs revolve around three important constraints to execute
instructions in parallel- (i) execution unit dependences,
(ii) control dependences, and (iii) data dependences. We
shall look at each of the three decentralization approaches.
For the ensuing discussion, we use the example control flow
graph (CFG) and code shown in Figure 2. This CFG consists
of three basic blocks A, B, and C, with block B control-dependent
on the conditional branch in A, and block C
control-dependent on the conditional branch in B. We shall
assume that the control flow predictor has selected blocks
A, B, and C to be a trace.
I12: BR IF R13 == 0
I9: BR IF R4 >= 0
A I2:
I4: BR IF R4 == 0

Figure

2: Example Control Flow Graph and Code
2.2 Execution unit Dependence based Decentralization
In this type of decentralization, instructions are assigned to
PEs based on the EU that it will execute on. Thus, instructions
that are resource dependent on a particular EU execute
in the same PE. An artifact of this arrangement is that
instructions wait near where its EU dependence is resolved.
Interestingly, one of the pioneer dynamic scheduling schemes,
implemented in IBM 360/91 [16], had incorporated this type
of decentralization in 1967 itself! Very recently the MIPS
R10000 and R12000 processors also use this approach [20].
A potential advantage of the EDD approach is that each PE
need have only one or a few types of execution units. Another
advantage is that instruction partitioning is straight-forward
and static in nature when only a single PE has an
EU of a particular type. In such a situation, dynamic instances
of a given static instruction always get assigned to
the same PE. When multiple PEs have an EU of a particular
type, then there is a choice involved in allocating
instructions that require that EU type. One option in that
situation is to do a static allocation by a compiler or by off-line
hardware. Another option is to do dynamic allocation
(as in Alpha 21264 [7]), perhaps based on the queue lengths
in each of the concerned PEs. With either option, a ready
instruction may sometimes have to wait for its allotted EU
to become free, although another EU of the same type (in
another PE) is free. Furthermore, if the processor performs
speculative execution, then recovery actions arising from incorrect
speculations will necessitate selective discarding of
instructions from different PEs. the main shortcoming with
the EDD approach, however, is that generally the result
from a PE may be needed in any other PE, necessitating a
global interconnect between the PEs, which does not scale
well [10].
2.3 Control Dependence based Decentralization
(CDD)
In the second decentralization approach, a contiguous portion
of the dynamic instruction stream is assigned to the
same PE. Thus, instructions that are control-dependent on
the same conditional branch are generally assigned to the PE
to which the branch has been assigned, and instructions wait
near where their control dependences will be resolved. Examples
for this approach are the multiscalar execution model [4]
[14], the superthreading model [17], and the trace processing
model [13] [15] [19] 2 . Control-dependence-based decentralization
fits well with the control-driven program specification
typically adopted in current ISAs. Because control-dependent
instructions tend to be grouped together in the
program executable, partitioning of instructions among the
PEs can be easily done by statically partitioning the CFG.
Furthermore, no regrouping of instructions is needed at instruction
commit time.
CDD hardware implementations proposed so far, such as the
multiscalar processor, the superthreading processor, and the
trac processors, all organize the PEs as a circular queue as
shown in Figure 3. The circular queue imposes a sequential
order among the PEs, with the head pointer indicating the
oldest active PE. Programs execute on these processors as
follows. Each cycle, if the tail PE is idle, the control flow
predictor (CFP) predicts the next task in the dynamic instruction
stream, and invokes it on the tail PE; a task is
a path or subgraph contained in the CFG of the executed
program. For instance, if a CDD processor uses trace-based
tasks, then blocks A, B, and C of our example code (which
forms a trace) are assigned to a single PE. After invocation,
the tail pointer is advanced, and the invocation process continues
at the new tail in the next cycle. The successor task
in our example code will be the one starting at the predicted
target of the conditional branch in block C. Thus, the CFP
steps through the CFG, distributing tasks (speculatively)
Multiprocessors also partition instructions based on control de-
pendences. However, their partitioning granularity is generally much
coarser (several hundreds of instructions or more per task). Fur-
thermore, multiple tasks in a multiprocessor do not share the same
register space.
to the PEs. When the head PE completes its task, its instructions
are committed, and the head pointer is advanced,
causing that PE to become idle. When a task misprediction
is detected, all PEs between the incorrect speculation point
and the tail PE are discarded in what is known as a squash.

Figure

3: Block Diagram of an 8-PE CDD Processor
Whereas trace processors consider a trace (a single path consisting
of multiple basic blocks) as a task, multiscalar processors
consider a subgraph of the control flow graph as a
task, thereby embedding alternate flows of control in a task.
These processors also differ in terms of how the instructions
of a task are fetched. Whereas trace processors fetch all instructions
of a task in a single cycle and supply them to a
PE, multiscalar processors let all of the active PEs parallelly
fetch their instructions, one by one. Architectural support is
provided in them to facilitate the hardware in determining
data dependences.
Studies [5] [19] have shown that in CDD processors, most
of the register operands are produced in the same PE or a
nearby PE, so that a unidirectional ring-type PE interconnect
is quite sufficient. Each PE typically keeps a working
copy of the register file, which also helps to maintain precise
state at task boundaries.
2.4 Data Dependence based Decentralization
(DDD)
In the third approach of decentralization, data dependences
are used as the basis of partitioning. That is, instructions
that are data dependent on an instruction are typically dispatched
to the PE to which the producer instruction has
been dispatched. Mutually data-independent instructions
are most likely dispatched to different PEs. Thus, instructions
wait near where their data dependences will be resolved.
The MISC (Multiple Instruction Stream Computer) [18], the
PEWs execution model [6] [11], the dependency-based model
given in [10], and the multicluster model [3] come under this
category. As data dependences dictate most of the communication
occurring between instructions, the DDD approach
attempts to minimize communication across multiple PEs.
Because the instructions in a PE are mostly data-dependent,
it becomes less important to do run-time scheduling within
each PE [10]. However, partitioning of instructions in a
DDD processor is generally harder than that in a CDD pro-
cessor. This is because programs are generally written in
control-driven form, which causes individual strands of data-dependent
instructions to be often spread over a large segment
of code. Thus, the hardware has to first construct the
data flow graph (DFG), and then do the instruction parti-
tioning, as shown in Figure 4. Notice that if programs were
specified in data-driven form, then data-dependence-based
partitioning would have been easier. To reduce the hardware
complexity, the DFG corresponding to a path (or trace) can
be generated by off-line hardware, and stored in a special
i-cache for later re-use.
I4: BR IF R4 == 0
I9: BR IF R4 >= 0
I12: BR IF R13 == 0

Figure

4: Register Data Flow Graph (RDFG)
of Trace ABC in Figure 2
The DDD hardware implementations proposed so far, such
as the PEWs [6] [11], the dependence-based model in [10],
and the multicluster [3], differ in terms of how the PEs are
interconnected. PEWs uses a unidirectional ring-type con-
nection, whereas the MISC and dependence-based model of
[10] use a crossbar. When a crossbar is employed, all PEs are
of same proximity to each other, and hence the instruction
partitioning algorithm becomes straightforward. However,
as discussed earlier, a crossbar does not scale well.
In the multicluster execution model, the ISA-visible registers
are partitioned across the PEs. An instruction is assigned a
PE based on its source and destination (ISA-visible) regis-
ters. Thus, its partitioning is static in nature. In the PEWs
execution model, the partitioning is done dynamically. In
order to reduce the burden on the partitioning hardware
and the complexity on the instruction pipeline, the DFG
corresponding to a path is built by off-line hardware, and
stored in a special i-cache [11]. Alternately, architectural
support can be provided to permit the compiler to convey
the DFG and other relevant information to the hardware.
2.5 Comparison
We have seen three approaches for partitioning instructions
amongst decentralized processing elements. Table 1 succinctly
compares the different attributes and hardware features
of the three decentralization approaches. From the
implementation point of view, CDD and EDD potentially
have an edge, because of the static nature of their partition-
ing. CDD implementations have a further advantage due
Attribute EDD CDD DDD
Basis for partitioning Resource usage Control dependence Data dependence
Execution unit types in a PE Only a few EU types All EU types All EU types
Logical ordering among PEs
Partitioning granularity Instruction Task Instruction
Time at which partitioning is done Static/Dynamic Static/Dynamic Static/Dynamic
Complexity of dynamic partitioning hardware Moderate Moderate High

Table

1: Comparison of Different Decentralization Approaches
to partitioning at a higher level. Instead of having a 16-
way instruction fetch mechanism that fetches and decodes
instructions every cycle from an i-cache or a trace cache,
the instruction fetch mechanism (including the i-cache) can
be distributed across the PEs, as is done in the multiscalar
processor [4] [14].
3 Experimental Methodology
The previous section presented a detailed description and
comparison of three decentralization approaches. Next, we
present a detailed simulation-based performance evaluation
of these three decentralization approaches.
3.1 Experimental Setup
The setup consists of 3 execution-driven simulators-based
on the MIPS-II ISA-that simulate the 3 decentralization
approaches in detail. The simulators do cycle-by-cycle sim-
ulation, including execution along mispredicted paths. The
simulators are equivalent in every respect except for the instruction
partitioning strategy. In particular, the following
aspects are common for all of the simulators.
Instruction Fetch Mechanism: All execution models use
a common control flow predictor to speculate the outcome of
multiple branches every cycle. This high-level predictor, an
extension of the tree-level predictor given in [1], considers a
tree-like subgraph of the dynamic control flow graph as the
basis of prediction. A tree of depth 4, having up to 8 paths,
is used. The predictor predicts one out of these 8 paths using
a 2-level PAg predictor. Each tree-path (or trace) is allowed
to have a maximum of 16 instructions. The first level table
(Subgraph History Table) of the predictor has 1024 entries,
is direct mapped, and uses a pattern size of 6. The second
level table (Pattern History Table) entries consist of 3-bit
up/down saturating counters.
A 128 Kbyte trace cache [12] is used to store recently seen
traces. The trace cache is 8-way set-associative, has 1 cycle
access time, and a block size of 16 instructions. All traces
starting at the same address map to the same set in the
trace cache. Every cycle, the fetch mechanism can fetch
and dispatch up to 16 instructions.
Data Memory System: All execution models use the same
memory system, with an L1 data cache and a perfect L2
cache (so as to reduce the memory requirements of the simu-
lators). The L1 data cache is 64 Kbytes, 4-way set-associative,
32-way interleaved, non-blocking, 16 byte blocks, and 1 cycle
access latency. Memory address disambiguation is performed
in a decentralized manner using a structure called
arcade [11], which has the provision to execute memory references
prior to doing address disambiguation.
Instruction Retirement: All of the investigated execution
models retire (i.e., commit) instructions in program order,
one trace at a time, so as to support precise exceptions.
PE Interconnection Topology: Three types of PE inter-connects
are modeled in the simulators-a unidirectional
ring, a bi-directional ring, and a crossbar. The rings take
1 cycle for each adjacent PE!PE transfer. The crossbar
takes log 2 p cycles for all PE!PE transfers, where p is the
number of PEs.
Parameters for the Study:
ffl Maximum Fetch Size (f): instructions.
ffl PE issue width (d): the maximum number of instructions
executed from a PE per cycle is fixed at 3 (be-
cause higher values gave only marginal improvements).
Thus, each PE has 3 EUs.
ffl PE issue strategy: the default strategy is to use out-
of-order execution within each PE.
The experiments involve varying 3 parameters: the partitioning
strategy, the number of PEs (p), and the PE inter-connect

3.2 Benchmarks and Performance Metrics

Table

2 gives the list of SPEC95 integer programs that we
use, along with the input files we use. The compress95
Average Path
Benchmark Input File Trace Length Prediction
gcc stmt.i 13.06 81.78%
go 9stone21.in 14.29 70.17%
li test.lsp 12.28 91.04%
vortex vortex.raw 13.59 94.98%

Table

2: Benchmark Statistics
program is based on the UNIX compression utility, and
performs a compression/decompression sequence on a large
buffer of data. The gcc program is a version of the GNU
C compiler. It has many short loops, and has poor instruction
locality. The go program is based on the internationally
ranked Go program, "The Many Faces of Go". The li
Benchmark Percentage of Instrs Using an EU type EU!EU communication
Program Integer Load/Store Branch Int!Int Int!Load/Store Int!Branch Load/Store!Int
gcc 43.2% 36.1% 20.7% 26.2% 32.6% 13.9% 11.2%
go 52.4% 32.2% 15.4% 34.9% 28.9% 9.0% 14.5%
li 26.6% 48.7% 24.7% 14.3% 37.8% 6.3% 7.6%
vortex 28.7% 52.4% 18.9% 13.5% 47.6% 7.5% 8.7%

Table

3: Distribution of Instructions based on Execution Unit Used
program is a lisp interpreter written in C. The m88ksim program
is a simulator for the Motorola 88100 processor, and
the vortex program is a single-user object-oriented database
program that exercises a system kernel coded in integer C.
The programs are compiled for a MIPS R3000-Ultrix platform
with a MIPS C (Version 3.0) compiler using the optimization
flags specified with the SPEC benchmark suite.
The benchmarks are simulated to completion or up to 500
million instructions, depending on whichever occurred first.

Table

also gives some execution statistics, such as the number
of instructions simulated, the average tree-path (trace)
length, and the path prediction accuracy. From these statis-
tics, we can see that gcc and go have very poor control flow
predictability, primarily arising from poor instruction local-
ity, which causes too many conflicts in the first level table
of the predictor.
For measuring performance, execution time is the sole metric
that can accurately measure the performance of an integrated
software-hardware computer system. Accordingly,
our simulation experiments measure the execution time in
terms of the number of cycles required to execute a fixed
number of instructions. While reporting the results, the execution
time is expressed in terms of instructions per cycle
(IPC). Notice that the IPC figures include only the committed
instructions and do not include nops. We also measure
register traffic to get more insight into the behavior
of the different decentralization approaches.
3.3 Partitioning Algorithms Simulated
EDD: In the EDD system, each PE has execution units
(EUs) of a particular type. To decide how many PEs should
have EUs of a particular type, we measured the percentage
of instructions that use each EU type. Table 3 gives these
percentages. Based on the percentage of instructions using a
particular EU, we used the following EU assignments. When
the system has a single PE, all 3 EUs of that PE can execute
any type of instruction. When the system has 2 PEs, the
first PE houses 3 Integer/FP EUs, and the second PE houses
3 Load/Store/Branch EUs. When the system has 4 or more
PEs, the division of PEs is as in Table 4. PEs having EUs
Number of Integer Load/Store Branch FP
PEs PEs PEs PEs PEs

Table

4: Division of PEs for EDD Scheme
of the same kind are placed adjacent to each other. The
set of PEs with the Load/Store EUs is placed immediately
after the set of PEs with the Integer EUs, because there is
significant amount of traffic from integer EUs to Load/Store
EUs (c.f.

Table

3). The instruction partitioning strategy has
a dynamic component in that when an instruction can be
assigned to multiple PEs, it is assigned to the candidate PE
having the least number of instructions.
CDD: For studying the CDD partitioning approach, we
connect the PEs in a circular queue-like manner. Two different
task sizes, namely 8 and 16, are used. In the first case,
called CDD-8, a trace of up to 8 instructions is fetched in a
cycle and assigned to the PE at the tail of the PE circular
queue. In the second case, called CDD-16, a trace of up to
instructions is fetched in a cycle and assigned to the tail
PE.
DDD: For studying the DDD partitioning approach, we use
two different partitioning algorithms. The first algorithm,
called (DDD-Multicluster), follows the multicluster
approach depicted in [3]. A subset of the ISA-visible registers
is assigned to each PE such that each ISA-visible register
has the notion of a home-PE. For our studies, the n th
PE was considered the home-PE for registers r
through
r
is the number of general-purpose
registers and p is the number of PEs. The assignment of
instructions to PEs is done as depicted in Table 5.
Number of Number of PE to which
Source Dest. Instruction
Registers Registers is Assigned
of dest. register
of source register
of dest. register
st source register
If 2 or more source registers &
destination register are same,
then, home-PE of that register;
else, home-PE of dest. register

Table

5: Instruction Assignment for
DDD-M Partitioning Scheme
The second DDD algorithm, called DDD-P (DDD-PEWs),
makes better use of data dependence information. It uses
off-line hardware to construct the register data flow graph
(RDFG) for each trace (tree-path) when the trace is encountered
for the first time. Once the RDFG of a trace is
data dependence chains (or strands) are identified
in the RDFG. Some dependence strands may have communication
between them. Once the strands are identified, a
relative PE assignment is made for the strands, with a view
IPC
Number of PEs
DDD-M
EDD
IPC
gcc
Number of PEs31
go
IPC
Number of PEs31
li
IPC
Number of PEs31
IPC
Number of PEs31
vortex
IPC
Number of PEs

Figure

5: IPC without Nops for Varying Number of PEs, with Unidirectional Ring PE Interconnect
to reduce the communication latency between strands. That
is, if there is flow of data from one strand to another, the
strands are given a relative PE assignment such that the
consumer strand's PE is the one immediately following the
producer strand's PE. Strands that do not have data dependences
with any other strands of the trace are marked
as relocatable. At the time of instruction dispatch, the dispatch
unit decides the PE placement for each strand based
on its dependences to data coming from outside the trace
and the relative PE placement decided statically by the off-line
hardware. A 2-cycle penalty (stall) is imposed when a
trace is seen for the first time in order to form the RDFG
and the relative PE assignments. If the PE assigned to an
instruction is full, the instruction is assigned to the closest
succeeding PE having an empty slot.
Performance Results
4.1 IPC with Unidirectional Ring
Our first set of studies focuses on comparing the performance
of different partitioning algorithms as the number of
PEs is varied, and a unidirectional ring is used to connect
the PEs. Figure 5 plots the IPC values obtained with the default
parameters (PE scheduler
for each
benchmark. The values of p that we consider are f1, 2, 4, 8,
12, 16g. Each graph in Figure 5 corresponds to a particular
benchmark program, and has 3 plots, one corresponding to
each decentralization approach.
EDD: First of all, the EDD approach does not perform well
at all with a ring-type PE interconnect, as expected. This
is because the EDD approach is unable to exploit localities
of communication, which is very important when using a
ring topology to interconnect the PEs. The performance
increases slightly as the number of PEs is increased to 2,
but thereafter it is downhill.
DDD: The performance of the two DDD partitioning algorithms
are quite different. The performance of the DDD-M
algorithm is generally poor, and similar to the performance
of the EDD algorithm simulated. To get good performance
from the DDD-M approach, an optimizing compiler needs
to rename register specifiers considering the idiosyncrasies
of the DDD-M execution model; otherwise, very little of the
data dependence localities are likely to be captured. For the
DDD-P approach, performance generally keeps increasing as
the number of PEs (p) is increased from 1 to 8. For these
values of p, the DDD-P algorithm performs the best among
the investigated partitioning algorithms. This is because
DDD-P is better able to exploit localities of communication
when instructions are spread across a moderate number of
PEs. The most striking observation is that the performance
of DDD-P starts dropping when the number of PEs is increased
beyond 8. This drop in performance is because some
data-dependent instructions are getting allocated to distant
PEs, resulting in large delays in forwarding register values
between these distant PEs. One reason for the spreading
of data-dependent instructions is that the RDFG formation
and the instruction partitioning are done on an individual
trace basis. If a knowledge of the subsequent traces is available
and made use of while partitioning instructions, then a
better placement of instructions can be made.
CDD: The performance of both CDD schemes keeps increasing
steadily as the number of PEs is increased from 1
to 16. This is because of two reasons: (i) available parallelism
increases with instruction window size, and (ii) most
register instances have a short lifetime [5] [19], resulting in
very little communication of register values between non-adjacent
PEs. As the number of PEs is increased beyond 8,
the CDD approach starts performing better than the DDD
approaches; both DDD and EDD begin to perform worse
in this arena! Notice, however, that for three of the benchmarks
(compress95, li, and m88ksim), the performance of
DDD-P with 4 PEs is better than the performance of CDD-
with And for the remaining three benchmarks,
the performance of a 4 PE DDD-P processor is not much
lower than that of a 16 PE CDD-16 processor. This highlights
the importance of developing DDD algorithms that
can perform better distribution of instructions over a large
number of PEs.
4.2 IPC with Bi-directional Ring
To investigate if the unidirectional nature of the ring was
the cause of the drop in DDD-P's performance for higher
values of p, we also experimented with a bi-directional ring.

Table

6 tabulates the IPC values obtained for 12 PE DDD-
P with the unidirectional PE interconnect and with the bi-directional
PE interconnect. (We simulated the bi-directional
ring configuration for 12 PEs, because the performance of
DDD-P starts dropping at
The data in Table 6 indicate that a bi-directional ring does
little to improve the performance of DDD-P when
(except for m88ksim which registers a modest improvement
from 3.13 to 3.46).
Benchmark IPC obtained with
Program Unidirectional Ring Bi-directional Ring
gcc 2.27 2.27
go 1.82 1.82
li 3.15 3.17
vortex 3.59 3.64

Table

Unidirectional Ring and Bi-directional Ring
PE Interconnects
4.3 IPC with Crossbar
The results presented so far were obtained with ring-type interconnections
between the PEs. Next, we investigate how
the decentralization approaches scale when the PEs are interconnected
by a realistic crossbar. Figure 6 plots the IPC
values obtained when the PEs are interconnected by a log 2 p-cycle
crossbar. A comparison of the data in Figures 5 and
6 show that with a crossbar interconnect, the performance
of EDD has improved slightly for some of the benchmarks.
For DDD-P, the performance has decreased (compared to
that with ring interconnect) for lower values of p, and remains
more or less the same as before for higher values of p.
For CDD, the performance with a crossbar is consistently
lower than the performance with a ring. In fact, contrary to
the case with a ring-type interconnect, the performance of
CDD-16 with a realistic crossbar decreases as the number of
PEs is increased. Overall, the results with a realistic cross-bar
show the performance of DDD-P to be slightly better
than that of CDD-16 for most benchmarks.
4.4 Register Traffic
In order to get a better understanding of the IPC results
seen so far, we next analyze the register traffic occurring in
the decentralized processors when different partitioning algorithms
are used. Figure 7 plots for the distribution
of register results based on the number of PEs they had to
travel. For each benchmark, distributions are given for the
EDD, CDD-16, and DDD-P partitioning algorithms.
The curves for EDD indicate a significant amount of register
traffic between distant PEs. For both CDD and DDD, the
amount of register traffic between PEs steadily decreases as
PE distance increases. For DDD-P, the traffic dies down to
almost zero as register values travel about 7 PEs, which explains
why using a bi-directional ring does not fetch much of
performance improvements. However, a noticeable fraction
of register values travel up to 5-6 hops, which affects the performance
of the DDD-P scheme. One of the reasons for this
is that the DDD-P scheme forms the DFGs for each trace
independently, and assigns instructions of a trace to the PEs
without considering the DFGs of the subsequent traces who
need the values produced by this trace. For CDD, register
traffic almost dies down to almost zero, as register values
travel about 3 PEs. This is because most register instances
have a short lifetime [5] [19], which explains why the performance
of CDD with a ring-type interconnect continues to
increase as the number of PEs is increased.
5 Discussion and Conclusions
The central idea behind decentralized execution models is to
split the dynamic execution window of instructions amongst
smaller, parallel PEs. By keeping each PE relatively small,
the circuitry needed to search it when forwarding newly produced
values is greatly reduced, thus reducing the impact of
dynamic scheduling on clock speed. By allocating dependent
instructions to the same PE as much as possible, communication
localities can be exploited, thereby minimizing
global communication within the processor. We examined
three categories of decentralized execution models, based on
the type of dependence they use as the basis for instruction
partitioning. These categories are (i) Execution unit
Dependence based Decentralization (EDD), (ii) Control Dependence
based Decentralization (CDD), and (iii) Data Dependence
based Decentralization (DDD).
The detailed performance results that we obtained, on an
ensemble of well-known benchmarks, lead us to two important
conclusions. First, the currently used approach-
EDD-does not provide good performance even when the
instruction window is split across a moderate number of PEs
and when a crossbar is used to connect the PEs. Second,
when a unidirectional ring is used to interconnect the PEs,
the DDD-P approach provides the best IPC values when a
IPC
Number of PEs
12Number of PEs
gcc
IPC
EDD
DDD-P
Number of PEs
Number of PEs
li31
Number of PEs31
Number of PEs
vortex

Figure

Nops with a Realistic (log 2 p cycle) Crossbar PE Interconnect
moderate number of PEs is used. This is due to its ability
to exploit localities of communication between instructions.
When a large number of PEs is used, the performance of
DDD-P starts dropping, and the CDD approach begins to
perform better. This is because of the inability of the implemented
DDD-P algorithm to judiciously partition complex
data dependence graphs across a large number of PEs.
Nevertheless, the performance of the implemented DDD-P
algorithm with 4 PEs is comparable to or better than the
performance of the implemented CDD with PEs.
Although the results presented in this paper help in understanding
the general trends in the performance of different
decentralization approaches, the study of this topic is not
complete by any means. There are a variety of execution
model-specific techniques (both at the ISA-level and at the
microarchitectural level) that need to be explored for each of
the decentralized execution models before a conclusive verdict
can be reached. In addition, it is important to investigate
the extent to which factors such as value prediction,
instruction replication, and multiple flows of control introduce
additional wrinkles to performance. Finally, it would
be worthwhile to explore the possibility of a good blending
of the CDD and DDD models by using a DDD-P processor
(i.e., a cluster of DDD-P PEs) as the basic PE in a CDD
processor. Such a processor can attempt to exploit data independences
at the lowest level of granularity and control
independences at a higher level.

Acknowledgements

This work was supported by the US National Science Foundation
(NSF) through a Research Initiation Award (CCR
9410706), a CAREER Award (MIP 9702569), and a research
grant (CCR 9711566). We are indebted to the reviewers for
their comments on the paper and to Dave Kaeli for helps in
getting the SPEC95 programs compiled for the MIPS-Ultrix
platform.



--R

"Control Flow Prediction with Tree-like Subgraphs for Superscalar Processors,"
"Understanding Some Simple Processor- Performance Limits,"
"The Multicluster Architecture: Reducing Cycle Time Through Partitioning,"
"The Multiscalar Architecture,"
"Register Traffic Analysis for Streamlining Inter-Operation Communication in Fine-Grain Parallel Processors,"
"PEWs: A Decentralized Dynamic Scheduler for ILP Processing,"
"The Alpha 21264: A 500 MHz Out-of-Order Execution Microprocessor,"
"Exploiting Fine Grained Parallelism Through a Combination of Hardware and Software Techniques,"

"Complexity-Effective Superscalar Processors,"
"Complexity- Effective PEWs Microarchitecture,"
"Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching,"
"Trace Processors,"
"Mul- tiscalar Processors,"
"Multiscalar Execution along a Single Flow of Control,"
"An Efficient Algorithm for Exploiting Multiple Arithmetic Units,"
"The Superthreaded Archi- tecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation,"
"MISC: A Multiple Instruction Stream Computer,"
"Improving Superscalar Instruction Dispatch and Issue by Exploiting Dynamic Code Sequences,"
"The MIPS R10000 Superscalar Micro- processor,"
--TR
Exploiting fine-grained parallelism through a combination of hardware and software techniques
MISC
Register traffic analysis for streamlining inter-operation communication in fine-grain parallel processors
The multiscalar architecture
Multiscalar processors
Control flow prediction with tree-like subgraphs for superscalar processors
Trace cache
Improving superscalar instruction dispatch and issue by exploiting dynamic code sequences
Exploiting instruction level parallelism in processors by caching scheduled groups
Complexity-effective superscalar processors
Trace processors
The multicluster architecture
Understanding some simple processor-performance limits
The MIPS R10000 Superscalar Microprocessor
Multiscalar Execution along a Single Flow of Control
The Alpha 21264
The Superthreaded Architecture

--CTR
D. Morano , A. Khalafi , D. R. Kaeli , A. K. Uht, Realizing high IPC through a scalable memory-latency tolerant multipath microarchitecture, ACM SIGARCH Computer Architecture News, v.31 n.1, March
Aneesh Aggarwal , Manoj Franklin, Scalability Aspects of Instruction Distribution Algorithms for Clustered Processors, IEEE Transactions on Parallel and Distributed Systems, v.16 n.10, p.944-955, October 2005
Ramadass Nagarajan , Karthikeyan Sankaralingam , Doug Burger , Stephen W. Keckler, A design space evaluation of grid processor architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
Joan-Manuel Parcerisa , Julio Sahuquillo , Antonio Gonzalez , Jose Duato, On-Chip Interconnects and Instruction Steering Schemes for Clustered Microarchitectures, IEEE Transactions on Parallel and Distributed Systems, v.16 n.2, p.130-144, February 2005
Rajeev Balasubramonian, Cluster prefetch: tolerating on-chip wire delays in clustered microarchitectures, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Dynamically managing the communication-parallelism trade-off in future clustered processors, ACM SIGARCH Computer Architecture News, v.31 n.2, May
speculative execution;instruction-level parallelism;hardware window;control dependence;dynamic scheduling;decentralization;execution unit dependence;data dependence