The Case for a Single-Chip Multiprocessor
Kunle Olukotun, Basem A. Nayfeh, Lance Hammond, Ken Wilson, and Kunyung Chang
Computer Systems Laboratory
Stanford University
Stanford, CA 94305-4070
http://www-hydra.stanford.edu

Abstract
Advances in IC processing allow for more microprocessor design
options. The increasing gate density and cost of wires in advanced
integrated circuit technologies require that we look for new ways to
use their capabilities effectively. This paper shows that in advanced
technologies it is possible to implement a single-chip multiprocessor in the same area as a wide issue superscalar processor. We findthat for applications with little parallelism the performance of thetwo microarchitectures is comparable. For applications with large
amounts of parallelism at both the fine and coarse grained levels,
the multiprocessor microarchitecture outperforms the superscalararchitecture by a significant margin. Single-chip multiprocessor
architectures have the advantage in that they offer localized implementation of a high-clock rate processor for inherently sequential
applications and low latency interprocessor communication for parallel applications.

1

Introduction

Advances in integrated circuit technology have fueled microprocessor performance growth for the last fifteen years. Each increase inintegration density allows for higher clock rates and offers newopportunities for microarchitectural innovation. Both of these are
required to maintain microprocessor performance growth. Microarchitectural innovations employed by recent microprocessors
include multiple instruction issue, dynamic scheduling, speculative
execution and non-blocking caches. In the future, the trend seems to
be towards CPUs with wider instruction issue and support for larger
amounts of speculative execution. In this paper, we argue against
this trend. We show that, due to fundamental circuit limitations andlimited amounts of instruction level parallelism, the superscalar
execution model will provide diminishing returns in performancefor increasing issue width. Faced with this situation, building acomplex wide issue superscalar CPU is not the most efficient use ofsilicon resources. We present the case that a better use of siliconarea is a multiprocessor microarchitecture constructed from simpler
processors.

Appears in Proceedings Seventh International
Symp. Architectural Support for Programming
Languages and Operating Systems (ASPLOS VII),
Cambridge, MA, October 1996

To understand the performance trade-offs between wide-issue processors and multiprocessors in a more quantitative way, we compare the performance of a six-issue dynamically scheduled
superscalar processor with a 4 × two-issue multiprocessor. Our
comparison has a number of unique features. First, we accurately
account for and justify the latencies, especially the cache hit time,associated with the two microarchitectures. Second, we develop
floor-plans and carefully allocate resources to the two microarchitectures so that they require an equal amount of die area. Third, we
evaluate these architectures with a variety of integer, floating point
and multiprogramming applications running in a realistic operating
system environment.
The results show that on applications that cannot be parallelized,
the superscalar microarchitecture performs 30% better than one
processor of the multiprocessor architecture. On applications withfine grained thread-level parallelism the multiprocessor microarchitecture can exploit this parallelism so that the superscalar microarchitecture is at most 10% better. On applications with large grained
thread-level parallelism and multiprogramming workloads the multiprocessor microarchitecture performs 50–100% better than thewide superscalar microarchitecture.
The remainder of this paper is organized as follows. In Section 2,
we discuss the performance limits of superscalar design from atechnology and implementation perspective. In Section 3, we makethe case for a single chip multiprocessor from an applications perspective. In Section 4, we develop floor plans for a six-issue superscalar microarchitecture and a 4 × two-issue multiprocessor andexamine their area requirements. We describe the simulation methodology used to compare these two microarchitectures in Section 5,
and in Section 6 we present the results of our performance comparison. Finally, we conclude in Section 7.

2

The Limits of the Superscalar Approach

A recent trend in the microprocessor industry has been the designof CPUs with multiple instruction issue and the ability to execute
instructions out of program order. This ability, called dynamicscheduling, first appeared in the CDC 6600 [21]. Dynamic scheduling uses hardware to track register dependencies between instructions; an instruction is executed, possibly out of program order, assoon as all of its dependencies are satisfied. In the CDC 6600 theregister dependency checking was done with a hardware structure
called the scoreboard. The IBM 360/91 used register renaming to
improve the efficiency of dynamic scheduling using hardware struc-

Instruction
Fetch

Issue andRetirement

Execution

Integer
Units
Reorder
Buffer
Instruction
Fetch &
Decode

and

FP
Units

Instruction
Issue
QueuesLD/ST
Units

Instruction
Cache

Data
Cache

Figure 1. A dynamic superscalar CPUtures called reservation stations [3]. It is possible to design adynamically scheduled superscalar microprocessor using reservation stations; Johnson gives a thorough description of this approach[13]. However, the most recent implementations of dynamic superscalar processors have used a structure similar to the one shown in
Figure 1. Here register renaming between architectural and physicalregisters is done explicitly, and instruction scheduling and register
dependency tracking between instructions are performed in an
instruction issue queue. Examples of microprocessors designed inthis manner are the MIPS Technologies R10000 [24] and the HP
PA-8000 [14]. In these processors the instruction queue is actually
implemented as multiple instruction queues for different classes of
instructions (e.g. integer, floating point, load/store). The three major
phases of instruction execution in a dynamic superscalar machine
are also shown in Figure 1. They are fetch, issue and execute. In therest of this section we describe these phases and the limitations thatwill arise in the design of a very wide instruction issue CPU.
The goal of the fetch phase is to present the rest of the CPU with alarge and accurate window of decoded instructions. Three factors
constrain instruction fetch: mispredicted branches, instruction misalignment, and cache misses. The ability to predict branches correctly is crucial to establishing a large, accurate window of
instructions. Fortunately, by using a moderate amount of memory(64Kbit), branch predictors such as the selective branch predictor
proposed by McFarling are able to reduce misprediction rates tounder 5% for most programs [15]. However, good branch prediction is not enough. As Conte pointed out, it is also necessary toalign a packet of instructions for the decoder [7]. When the issue
width is wider than four instructions there is a high probability that
it will be necessary to fetch across a branch for a single packet of
instructions since, in integer programs, one in every five instructions is a branch [12]. This will require fetching from two cachelines at once and merging the cache lines together to form a single
packet of instructions. Conte describes a number of methods forachieving this. A technique that divides the instruction cache intobanks and fetches from multiple banks at once is not too expensive
to implement and provides performance that is within 3% of a perfect scheme on an 8-wide issue machine. Even with good branchprediction and alignment a significant cache miss rate will limit theability of the fetcher to maintain an adequate window of instructions. There are still some applications such as large logic simulations, transactions processing and the OS kernel that havesignificant instruction cache miss rates even with fairly large 64 KB
two way set-associative caches [19]. Fortunately, it is possible tohide some of the instruction cache miss latency in a dynamicallyscheduled processor by executing instructions that are already inthe instruction window. Rosenblum et. al. have shown that over
60% of the instruction cache miss latency can be hidden on a database benchmark with a 64KB two way set associative instruction
cache [19]. Given good branch prediction and instruction alignment
it is likely that the fetch phase of a wide-issue dynamic superscalar
processor will not limit performance.
In the issue phase, a packet of renamed instructions is inserted into
the instruction issue queue. An instruction is issued for execution
once all of its operands are ready. There are two ways to implement
renaming. One could use an explicit table for mapping architecturalregisters to physical registers, this scheme is used in the R10000[24], or one could use a combination reorder buffer/instruction
queue as in the PA-8000 [14]. The advantage of the mapping table
is that no comparisons are required for register renaming. The disadvantage of the mapping table is that the number of access ports
required by the mapping table structure is O × W , where O is thenumber of operands per instruction and W is the issue width of themachine. An eight-wide issue machine with three operands per
instruction requires a 24 port mapping table. Implementing renaming with a reorder buffer has its own set of drawbacks. It requiresn × Q × O × W 1-bit comparators to determine which physical registers should supply operands for a new packet of instructions,where n is the number of bits required to encode a register identifier and Q is the size of the instruction issue queue. Clearly, thenumber of comparators grows with the size of the instruction queue
and issue width. Once an instruction is in the instruction queue, allinstructions that issue must update their dependencies. Thisrequires another set of n × Q × O × W comparators. For example, amachine with eight wide issue, three operand instructions, a 64entry instruction queue, and 6-bit comparisons requires 9,216 1-bit
comparators. The net effect of all the comparison logic and encoding associated with the instruction issue queue is that it takes a large
amount of area to implement. On the PA-8000, which is a fourissue machine with 56 instruction issue queue entries, the instruction issue queue takes up 20% of the die area. In addition, as issue
widths increase, larger windows of instructions are required to findindependent instructions that can issue in parallel and maintain thefull issue bandwidth. The result is a quadratic increase in the size ofthe instruction issue queue. Moving to the circuit level, the instruction issue queue uses a broadcast mechanism to communicate thetags of the instructions that are issued, which requires wires thatspan the length of the structure. In future advanced integrated circuit technologies these wires will have increasingly long delays relative to the gates that drive them [9]. Given this situation,
ultimately, the instruction issue queue will limit the cycle time ofthe processor. For these reasons we believe that the instruction issue

queue will fundamentally limit the performance of wide issue
superscalar machines.
In the execution phase, operand values are fetched from the register
file or bypassed from earlier instructions to execute on the functional units. The wide superscalar execution model will encounter
performance limits in the register file, in the bypass logic and in thefunctional units. Wider instruction issue requires a larger window of
instructions, which implies more register renaming. Not only mustthe register file be larger to accommodate more renamed registers,
but the number of ports required to satisfy the full instruction issue
bandwidth also grows with issue width. Again, this causes a quadratic increase in the complexity of the register file with increases
in issue width. Farkas et. al. have investigated the effect of register
file complexity on performance [10]. They find that an eight-issue
machine only performs 20% better than a four-issue machine whenthe effect of cycle-time is included in the performance estimates.
The complexity of the bypass logic also grows quadratically withnumber of execution units; however, a more limiting factor is thedelay of the wires that interconnect the execution units. As far as
the execution units themselves are concerned, the arithmetic functional units can be duplicated to support the issue width, but more
ports must be added to the primary data cache to provide the necessary load/store bandwidth. The cheapest way to add ports to thedata cache is by building a banked cache [20], but the added multiplexing and control required to implement a banked cache increases
the access time of the cache. We investigate this issue in more detailin Section 4.2.

3

The Case for a Single-Chip Multiprocessor

The motivation for building a single chip multiprocessor comesfrom two sources; there is a technology push and an application
pull. We have already argued that technology issues, especially thedelay of the complex issue queue and multi-port register files, will
limit the performance returns from a wide superscalar execution
model. This motivates the need for a decentralized microarchitecture to maintain the performance growth of microprocessors. From
the applications perspective, the microarchitecture that works best
depends on the amount and characteristics of the parallelism in theapplications.
Wall has performed one of the most comprehensive studies ofapplication parallelism [22]. The results of his study indicate thatapplications fall in two classes. The first class consists of applications with low to moderate amounts of parallelism; under ten
instructions per cycle with aggressive branch prediction and large,
but not infinite window sizes. Most of these applications are integer
applications. The second class consists of applications with large
amounts of parallelism, greater than forty instructions per cyclewith aggressive branch prediction and large window sizes. The
majority of these applications are floating point applications andmost of the parallelism is in the form of loop-level parallelism.
The application pull towards a single-chip multiprocessor arises
because these two classes of applications require different execution models. Applications in the first class work best on processorsthat are moderately superscalar (2 issue) with very high clock rates
because there is little parallelism to exploit. To make this more concrete we note that a 200 MHz MIPS R5000, which is a single issue
machine when running integer programs, achieves a SPEC95 inte-

ger rating which is 70% of the rating of a 200 MHz MIPS R10000,
which is a four-issue machine [6]. Both machines have the same
size data and instruction caches, but the R5000 has a blocking data
cache, while the R10000 has a non-blocking data cache. Applications in the second class have large amounts of parallelism and see
performance benefits from a variety of methods designed to exploit
parallelism such as superscalar, VLIW or vector processing. However, the recent advances in parallel compilers make a multiprocessor an efficient and flexible way to exploit the parallelism in these
programs [1]. Single-chip multiprocessors, designed so that theindividual processors are simple and achieve very high clock rates,
will work well on integer programs in the first class. The addition of
low latency communication between processors on the same chip
also allows the multiprocessor to exploit the parallelism of the floating point programs in the second class. In Section 6 we evaluate
the performance of a single-chip multiprocessor for these two
application classes.
There are a number of ways to use a multiprocessor. Today, themost common use is to execute multiple processes in parallel toincrease throughput in a multiprogramming environment under thecontrol of a multiprocessor aware operating system. We note that
there are a number of commercially available operating systems
that have this capability (e.g. Silicon Graphics IRIX, Sun Solaris,
Microsoft Windows NT). Furthermore, the increasingly widespreaduse of visualization and multimedia applications tends to increase
the number of active processes or independent threads on a desktop
machine or server at a particular point in time.
Another way to use a multiprocessor is to execute multiple threads
in parallel that come from a single application. Two examples aretransaction processing and hand parallelized floating point scientific applications [23]. In this case the threads communicate using
shared memory, and these applications are designed to run on parallel machines with communication latencies in the hundreds of CPU
clock cycles; therefore, the threads do not communicate in a veryfine grained manner. Another example of manually parallelized
applications are fine-grained thread-level integer applications.
Using the results from Wall’s study, these applications exhibit moderate amounts of parallelism when the instruction window size isvery large and the branch prediction is perfect because the parallelism that exists is widely distributed. Due to the large window size
and the perfect branch prediction it will be very difficult for thisparallelism could be extracted with a superscalar execution model.
However, it is possible for a programmer that understands thenature of the parallelism in the application to parallelize the application into multiple threads. The parallelism exposed in this manner
is fine-grained and cannot be exploited by a conventional multiprocessor architecture. The only way to exploit this type of parallelism
is with a single-chip multiprocessor architecture.
A third way to use a multiprocessor is to accelerate the execution ofsequential applications without manual intervention; this requires
automatic parallelization technology. Recently, this automatic parallelization technology was shown to be effective on scientificapplications [2], but it is not yet ready for general purpose integer
applications. Like the manually parallelized integer applications,these applications could derive significant performance benefits
from the low-latency interprocessor communication provided by asingle-chip multiprocessor.

6-way SS

4x2-way MP# of CPUs

1

4

Degree superscalar

64x2# of architectural registers

32int / 32fp

4 x 32int / 32fp

# of physical registers

160int / 160fp

4 x 40int / 40fp

# of integer functional units3

4x1# of floating pt. functional units3

4x1# of load/store ports

8 (one per bank)

4x1

BTB size

2048 entries

4 x 512 entries

Return stack size

32 entries

4 x 8 entries

Instruction issue queue size

128 entries

4 x 8 entries

I cache32 KB, 2-way S. A.

4 x 8 KB, 2-way S. A.

D cache32 KB, 2-way S. A.

4 x 8 KB, 2-way S. A.

L1 hit time

2 cycles (4 ns)

1 cycle (2 ns)

L1 cache interleaving

8 banks

N/A

Unified L2 cache

256 KB, 2-way S. A.

256 KB, 2-way S. A.

L2 hit time / L1 penalty

4 cycles (8 ns)

5 cycles (10 ns)

Memory latency / L2 penalty

50 cycles (100 ns)

50 cycles (100 ns)

Table 1. Key characteristics of the two microarchitectures

4

Two Microarchitectures

To compare the wide superscalar and multiprocessor design
approaches, we have developed the microarchitectures for two
machines that will represent the state of the art in processor design
a few years from now. The superscalar microarchitecture (SS) is alogical extension of the current R10000 superscalar design, widened from the current four-way issue to a six-way issue implementation. The multiprocessor microarchitecture (MP), is a four-way
single-chip multiprocessor composed of four identical 2-way superscalar processors. In order to fit four identical processors on a die ofthe same size, each individual processor is comparable to the Alpha21064, which became available in 1992 [8].
These two extremely different microarchitectures have nearly identical die sizes when built in identical process technologies. The processor size we select is based upon the kinds of processor chips that
advances in silicon processing technology will allow in the next few
years. When manufactured in a 0.25 µm process, which should bepossible by the end of 1997, each of the chips will have an area of
430 mm2 — about 30% larger than leading-edge microprocessors
being shipped today. This represents typical die size growth overthe course of a few years among the largest, fastest microprocessors[11].
We have argued that the simpler two-issue CPU used in the multiprocessor microarchitecture will have a higher clock rate than thesix issue CPU; however, for the purposes of this comparison we
have assumed that the two processors have the same clock rate. To
achieve the same clock rate the wide superscalar architecture would
require deeper pipelining due to the large amount of instruction
issue logic in the critical path. For simplicity, we ignore latency
variations between the architectures due to the degree of pipelining.
We assume the clock frequency of both machines is 500 MHz. At
500 MHz the main memory latencies experienced by the processor
are large. We have modeled the main memory as a 50-cycle, 100 ns

delay for both architectures, typical values in a workstation todaywith 60 ns DRAMs and 40 ns of delays due to buffering in the
DRAM controller chips [25].
Table 1 shows the key characteristics of the two architectures. We
explain and justify these characteristics in the following sections.
The integer and floating point functional unit result and repeat
latencies are the same as the R10000 [24]4.1

6-Way Superscalar Architecture

The 6-way superscalar architecture is a logical extension of the current R10000 design. As the floorplan in Figure 2 and the area breakdown in Table 2 indicate, the logic necessary for out-of-orderinstruction issue and scheduling dominates the area of the chip, due
to the quadratic area impact of supporting 6-way instruction issue.
First, we increased the number of ports in the instruction buffers by
50% to support 6-way issue instead of 4-way, increasing the area of
each buffer by about 30-40%. Second, we increased the number of
instruction buffers from 48 to 128 entries so that the processor
examines a larger window of instructions for ILP to keep the execution units busy. This large instruction window also compensates forthe fact that the simulations do not execute code that is optimized
for a 6-way superscalar machine. The larger instruction window
size and wider issue width causes a quadratic area increase of the
instruction sequencing logic to 3-4 times its original size. Altogether, the logic necessary to handle out-of-order instruction issue
occupies about 120 mm2 — about 30% of the die. In comparison,
the actual execution units only occupy about 70 mm2 — just 18%of the die is required to build triple R10000 execution units in a
0.25 µm process.
Due to the increased rate at which instructions are issued, we alsoenhanced the fetch logic by increasing the size of the branch target
buffer to 2048 entries and the call-return stack to 32 entries. This
increases the branch prediction accuracy of the processor and pre-

21 mmInstruction
Cache(32 KB)

Reorder Buffer,
Instruction Queues,
and Out-of-Order Logic

21 mm

Processor#2

D-Cache #1 (8K) D-Cache #2 (8K)
D-Cache #3 (8K) D-Cache #4 (8K)

Processor#3

Processor#4

I-Cache #3 (8K)

I-Cache #4 (8K)

Floating Point
Unit

On-Chip L2 Cache (256KB)

Data
Cache
(32 KB)

Processor#1

L2 Communication Crossbar

Inst. Decode &RenameInteger Unit

21 mm

Clocking & Pads

TLB

I-Cache #2 (8K)
External
Interface

Clocking & Pads

Instruction
Fetch

On-Chip L2 Cache (256KB)

External
Interface

21 mm
I-Cache #1 (8K)

Figure 2. Floorplan for the six-issue dynamic superscalar
microprocessor.

Figure 3. Floorplan for the four-way single-chip
multiprocessor.

vents the instruction fetch mechanism from becoming a bottlenecksince the 6-way execution engine requires a much higher instruction fetch bandwidth than the 2-way processors used in the MP
architecture.

sors is less than one-fourth the size of the 6-way SS processor, as
shown in Table 3. The number of execution units actually increases
in the MP because the 6-way processor had three units of each type,while the 4-way MP must have four — one for each CPU. On theother hand, the issue logic becomes dramatically smaller, due to thedecrease in instruction buffer ports and the smaller number of
entries in each instruction buffer. The scaling factors of these twounits balance each other out, leaving the entire processor very close
to one-fourth of the size of the 6-way processor.

The on-chip memory hierarchy is similar to the Alpha 21164 — asmall, fast level one (L1) cache backed up by a large on-chip leveltwo (L2) cache. The wide issue width requires the L1 cache to support wide instruction fetches from the instruction cache and multiple loads from the data cache during each cycle. The two-way set
associative 32 KB L1 data cache is banked eight ways into eightsmall, single-ported, independent 4 KB cache banks each of whichhandling one access every 2 ns processor cycle. However, the additional overhead of the bank control logic and crossbar required toarbitrate between the multiple requests sharing the 8 data cachebanks adds another cycle to the latency of the L1 cache, andincreases the area by 25%. Therefore, our modeled L1 cache has a
hit time of 2 cycles. Backing up the 32 KB L1 caches is a large, unified, 256 KB L2 cache that takes 4 cycles to access. These latencies
are simple extensions of the times obtained for the L1 caches ofcurrent Alpha microprocessors [4], using a 0.25 µm process technology

4.2

4 x 2-way Superscalar Multiprocessor
Architecture

The MP architecture is made up of four 2-way superscalar processors interconnected by a crossbar that allows the processors to sharethe L2 cache. On the die, the four processors are arranged in a gridwith the L2 cache at one end, as shown in Figure 3. Internally, eachof the processors has a register renaming buffer that is much more
limited than the one in the 6-way architecture, since each CPU only
has an 8-entry instruction buffer. We also quartered the size of the
branch prediction mechanisms in the fetch units, to 512 BTB
entries and 8 call-return stack entries. After the area adjustments
caused by these factors are accounted for, each of the four proces-

The on-chip cache hierarchy of the multiprocessor is significantly
different from the cache hierarchy of the 6-way superscalar processor. Each of the 4 processors has its own single-banked and singleported 8 KB instruction and data caches that can both be accessedin a single 2 ns cycle. Since each cache can only be accessed by asingle processor with a single load/store unit, no additional overhead is incurred to handle arbitration among independent memoryaccess units. However, since the four processors now share a single
L2 cache, that cache requires an extra cycle of latency during every
access to allow time for interprocessor arbitration and crossbar
delay. We model this additional L2 delay by penalizing the MP an
additional cycle on every L2 cache access, resulting in a 5 cycle L2
hit time.

5

Simulation Methodology

Accurately evaluating the performance of the two microarchitectures requires a way of simulating the environment in which wewould expect these architectures to be used in real systems. In thissection we describe the simulation environment and the applications used in this study.

5.1 Simulation Environment
We execute the applications in the SimOS simulation environment[18]. SimOS models the CPUs, memory hierarchy and I/O devices

0.35mm R10K
Original Size (mm2)Size Extrapolated
to 0.25mm (mm2)% Growth Due to
New Functionality

219

112

0%

112

26%

8-bank D Cache (32 KB)

26

13

25%

17

4%

8-bank I Cache (32 KB)

28

14

25%

18

4%

TLB Mechanism

10

5

200%

15

3%

External Interface Unit

27

14

0%

14

3%

Instruction Fetch Unit and BTB

18

9

200%

28

6%

CPU Component
256K On-Chip L2 Cachea

New Size (mm2)% AreaInstruction Decode Section

21

11

250%

38

9%

Instruction Queues

28

14

250%

50

12%

Reorder Buffer

17

9

300%

34

9%

Integer Functional Units

20

10

200%

31

7%

FP Functional Units

24

12

200%

37

9%

Clocking & Overhead

73

37

0%

37

9%

Total Size

—

—

—

430

100%

Table 2. Size extrapolations for the 6-way superscalar from the MIPS R10000 processor% Area(of CPU / of entire
chip)

CPU Component

0.35mm R10K
Original Size (mm2)Size Extrapolated
to 0.25mm (mm2)% Growth Due to
New Functionality

D Cache (8 KB)

26

13

-75%

3

6% /3%I Cache (8 KB)

28

14

-75%

4

7% / 3%TLB Mechanism

10

5

0%

5

9% / 5%

Instruction Fetch Unit and BTB

18

9

-25%

7

13% / 7%

New Size (mm2)Instruction Decode Section

21

11

-50%

5

10% / 5%

Instruction Queues

28

14

-70%

4

8% / 4%

Reorder Buffer

17

9

-80%

2

3% / 2%Integer Functional Units

20

10

0%

10

20% / 10%

FP Functional Units

24

12

0%

12

23% / 12%

Per-CPU Subtotal

—

—

—

53

100% / 50%

256K On-Chip L2 Cache a

219

112

0%

112

26%

External Interface Unit

27

14

0%

14

3%

Crossbar Between CPUs

—

—

—

50

12%

Clocking & Overhead

73

37

0%

37

9%

Total Size

—

—

—

424

100%

Table 3. Size extrapolations in the 4 × 2-way MP from the MIPS R10000 processor.
a.

estimated from current L1 caches

of uniprocessor and multiprocessor systems in sufficient detail toboot and run a commercial operating system. SimOS uses the
MIPS-2 instruction set and runs the Silicon Graphics IRIX 5.3
operating system which has been tuned for multiprocessor performance. SimOS actually simulates the operating system; therefore,
all the memory references made by the operating system and theapplications are generated. This feature is particularly important forthe study of multiprogramming workloads where the time spentexecuting kernel code makes up a significant fraction of the nonidle execution time.
A unique feature of SimOS that makes studies such as this feasible
is that SimOS supports multiple CPU simulators that use a common
instruction set architecture. This allows trade-offs to be madebetween the simulation speed and accuracy. The fastest CPU simu-

lator, called Embra, uses binary-to-binary translation techniques
and is used for booting the operating system and positioning theworkload so that we can focus on interesting regions of execution.
The medium performance CPU simulator, called Mipsy, is twoorders of magnitude slower than Embra. Mipsy is an instruction set
simulator that models all instructions with a one cycle result latency
and a one cycle repeat rate. Mipsy interprets all user and privileged
instructions and feeds memory references to a memory system simulator. The slowest, most detailed CPU simulator is MXS, which
supports dynamic scheduling, speculative execution and non-blocking memory references. MXS is over four orders of magnitude
slower than Embra.
The cache and memory system component of our simulator is completely event-driven and interfaces to the SimOS processor model

Integer applications
compress

compresses and uncompresses file in memory

eqntotttranslates logic equations into truth tables

m88ksim

Motorola 88000 CPU simulator

MPsim

VCS compiled Verilog simulation of a multiprocessor

applu

solver for parabolic/elliptic partial differential equations

apsi

solves problems of temperature, wind, velocity, and distribution of pollutants

swim

shallow water model with 1K × 1K grid

tomcatv

mesh-generation with Thompson solver

Floating point applications

Multiprogramming applicationpmake

parallel make of gnuchess using C compiler

Table 4. The applications.
which drives it. Processor memory references cause threads to begenerated which keep track of the state of each memory reference
and the resource usage in the memory system. A call-back mechanism is used to inform the processor of the status of all outstandingreferences, and to inform the processor when a reference completes. These mechanisms allow for very detailed cache and memory system models, which include cycle accurate measures ofcontention and resource usage throughout the system.

5.2

Applications

The performance of nine realistic applications is used to evaluate
the two microarchitectures. Table 4 shows that the nine applications
are made up of two SPEC95 integer benchmarks (compress,
m88ksim), one SPEC92 integer benchmark (eqntott), one otherinteger application (MPsim), four SPEC95 floating point benchmarks (applu, apsi, swim, tomcatv), and a multiprogramming application (pmake).
The applications are parallelized in different ways to run on the MP
microarchitecture. Compress is run unmodified on both the SS andMP microarchitectures; using only one processor of the MP architecture. Eqntott is parallelized manually by modifying a single bit
vector comparison routine that is responsible for 90% of the execution time of the application [16]. The CPU simulator m88ksim isalso parallelized manually into three threads using the SUIF compiler runtime system. Each of the three threads is allowed to be in adifferent phase of simulating a different instruction at the sametime. This style of parallelization is very similar to the overlap of
instruction execution that occurs in hardware pipelining. The
MPsim application is a Verilog model of a bus based multiprocessor
running under a multi-threaded compiled code simulator (Chronologic VCS-MT). The multiple threads are specified manually byassigning parts of the model hierarchy to different threads. The
MPsim application uses four closely coupled threads; one for eachof the processors in the model. The parallel versions of the SPEC95
floating point benchmarks are automatically generated by the SUIF
compiler system [2]. The pmake application is a program development workload that consists of the compile phase of the Modified
Andrew Benchmark [17]. The same pmake application is executedon both microarchitectures; however, the OS takes advantage of theextra processors in the MP microarchitecture to run multiple compilations in parallel.
A difficult problem that arises when comparing the performance ofdifferent processors is ensuring that they do the same amount ofwork. The solution is not as easy as comparing the execution timesof each application on each machine. Due to the slow simulation
speed of the detailed CPU simulator (MXS) used to collect theseresults it would take far too long to run the applications to completion. Our solution is to compare the two microarchitectures over a
portion of the application using a technique called representative
execution windows [5]. In most compute intensive applications
there is a steady state execution region that consists of a single outer
loop or a set of loops that makes up the bulk of the execution time.
It is sufficient to sample a small number of iterations of these loops
as a representative execution window if the execution time behaviorof the window is indeed representative of the entire program. Simulation results show that for most applications the cache miss rates
and the number of instructions executed in the window deviates byless than 1% from the results for the entire program.
The simulation procedure begins with a checkpoint taken with the
Embra simulator. Simulation from the checkpoint starts with the
instruction level simulator Mipsy and the full memory system.
After the caches are warmed by running the Mipsy simulator
through the representative execution window at least once, the simulator is switched to the detailed simulator, MXS, to collect the performance results presented in this paper.
We use the technique of representative execution windows for all
the applications except pmake. Pmake does not have a well defined
execution region that is representative of the application as a whole.
Therefore, the results for pmake are collected by running the entire
application with MXS.

6

Performance Comparison

We begin by examining the performance of the superscalar
microarchitecture and one processor of the multiprocessor microarchitecture. Table 5 shows the IPC, branch prediction rates andcache miss rates for one processor of the MP; Table 6 shows the
IPC, branch prediction rates, and cache miss rates for the SSmicroarchitecture. The cache miss rates are presented in the tables
in terms of misses per completed instruction (MPCI); including
instructions that complete in kernel and user mode. When the issue
width is increased from two to six we see that the actual IPC
increases by less than a factor of 1.6 for all of the integer and multiprogramming applications. For the floating point applications theperformance improvement varies from a factor of 1.6 for tomcatv to
2.4 for swim..

have significant instruction cache stall time which is due to thelarge instruction working set size of these applications. Pmake also
has multiple processes and significant kernel execution time whichfurther increases the instruction cache miss rate.

2
D Cache Stall
I Cache Stall
Pipeline Stall

1.5

1.0

0.8

0.7

m88ksim

1.4

91.7

2.2

0.4

0.0

MPsim

0.8

78.7

5.1

2.3

2.3

applu

0.9

79.2

0.0

2.0

1.7

apsi

0.6

95.1

1.0

4.1

2.1

swim

0.9

99.7

0.0

1.2

1.2

tomcatv

0.8

99.6

0.0

7.7

2.2

pmake

1.0

86.2

2.3

2.1

0.4

1

0.5

0

pmake

3.5

0.0

tomcatv

0.0

79.8

swim

85.9

1.3

apsi

0.9

eqntott

applu

compress

Actual IPC

MPsim

IPC

m88ksim

L2 cache%MPCI

eqntott

D cache%MPCI

compress

I cache%MPCI

IPC

ProgramBP Rate%Figure 4. IPC Breakdown for a single 2-issue processor.

Table 5. Performance of a single 2-issue superscalar processor.
6

ProgramIPC

BP Rate%I cache%MPCI

D cache%MPCI

L2 cache%MPCI

compress

1.2

86.4

0.0

3.9

1.1

eqntott

1.8

80.0

0.0

1.1

1.1

m88ksim

2.3

92.6

0.1

0.0

0.0

MPsim

1.2

81.6

3.4

1.7

2.3

D Cache Stall
I Cache Stall

5

applu

1.7

79.7

0.0

2.8

2.8

apsi

1.2

95.6

0.2

3.1

2.6

swim

2.2

99.8

0.0

2.3

2.5

tomcatv

1.3

99.7

0.0

4.2

4.3

pmake

1.4

82.7

0.7

1.0

0.6

Pipeline Stall
Actual IPC

IPC

4

3

2

One of the major causes of processor stalls in a superscalar processor is cache misses. However, cache misses in a dynamically scheduled superscalar processor with speculative execution and nonblocking caches are not straightforward to characterize. The cache
misses that occur in a single issue in-order processor are not necessarily the same as the misses that will occur in the speculative outof-order processor. In speculative processors there are misses thatare caused by speculative instructions that never complete. With
non-blocking caches, misses may also occur to lines which alreadyhave outstanding misses. Both types of misses tend to inflate thecache miss rate of a speculative out-of-order processor. The second
type of miss is mainly responsible for the higher L2 cache missrates of the 6-issue processor compared to the 2-issue processor,
even though the cache sizes are equal.
Figure 4 shows the IPC breakdown for one processor of the MP
microarchitecture with an ideal IPC of two. In addition to the actual
IPC achieved, we show the loss in IPC due to data and instruction
cache stalls, and pipeline stalls. We see that a large percentage of
the IPC loss is due to data cache stall time. This is caused by thesmall size of the primary data cache. Mk88ksim, MPsim and pmake

pmake

tomcatv

swim

apsi

applu

MPsim

m88ksim

eqntott

0compress

Table 6. Performance of the 6-issue superscalar processor.

1

Figure 5. IPC Breakdown for the 6-issue processor.
Figure 5 shows the IPC breakdown for the SS microarchitecture.
We see that a significant amount of IPC is lost due to pipeline stalls.
The increase in pipeline stalls relative to the two-issue processor isdue to limited ILP in the applications and the 2-cycle L1 data cache
hit time. The larger instruction cache in the SS microarchitecture
eliminates most of the stalls due to instruction misses for all of theapplications except MPsim and pmake. Although the SPEC95 floating point applications have a significant amount of ILP, their performance is limited on the SS microarchitecture due to data cachestalls which consume over one-half of the available IPC
Table 7 shows cache miss rates for the MP microarchitecture given
in terms of MPCI. To reduce miss-rate effects caused by the idle
loop and spinning due to synchronization, the number of completed
instructions are those of the single 2-issue processor. Comparing
Table 5 and Table 7 shows that for eqntott, m88ksim and apsi the
MP microarchitecture has significantly higher data cache miss rates
than the single 2-issue processor. This is due primarily to the high-Application

I cache%MPCI

D cache%MPCI

L2 cache%MPCI

4compress

0.0

3.5

1.0

3.5

eqntott

0.6

5.4

1.2

m88ksim

2.3

3.3

0.0

MPsim

4.8

2.5

3.4

applu

0.0

2.1

1.8

apsi

2.7

6.9

2.0

swim

0.0

1.2

1.5

tomcatv

0.0

7.8

2.5

pmake

2.4

4.6

0.7

SS
MP

Relative Speedup

3
2.5
2
1.5

pmake

tomcatv

swim

apsi

applu

0

MPsim

degree of communication present in these applications. Althoughpmake also exhibits an increase in the data cache miss rate, it iscaused by process migration from processor to processor in the MP
microarchitecture.

m88ksim

0.5

eqntott

Table 7. Performance of the 4 × 2-issue processor.

compress

1

Figure 6. Performance comparison of SS and MP.
Figure 6 shows the performance comparison between the SS andMP microarchitectures. The performance is measured as the
speedup of each microarchitecture relative to the single 2-issue processor. On compress, an application with little parallelism, the MP
is able to achieve 75% of the SS performance even though three ofthe four processors are idle. Neither microarchitecture shows significant improvement over the 2-issue processor, however.
For applications with fine-grained parallelism and high-communication, such as eqntott, m88ksim and apsi, the MP and SS are similar. Both architectures are able to exploit fine-grained parallelism,
although in different ways. The SS microarchitecture relies on the
dynamic extraction of ILP from a single thread of control. The MP
can take advantage of moderate levels of ILP and can, unlike conventional multiprocessors, exploit fine-grained thread-level parallelism. Both the SS and MP approaches provide a 30% to 100%
performance increase over the 2-issue processor.
Applications with large amounts of parallelism allow the MP
microarchitecture to take advantage of coarse-grained parallelism
in addition to fine-grained parallelism and ILP. For these applications, the MP is able to significantly outperform the SS microarchitecture, whose ability to dynamically extract parallelism is limitedby the 128 instruction window.

7

Conclusions

The characteristics of advanced integrated circuit technologies
require us to look for new ways to utilize large numbers of gatesand mitigate the effects of high interconnect delays. We have discussed the details of implementing both a wide, dynamically scheduled superscalar processor and a single chip multiprocessor. The
implementation complexity of the dynamic issue mechanisms andsize of the register files scales quadratically with increasing issue
width and ultimately impacts the cycle time of the machine. The
alternative multiprocessor microarchitecture, which is composed ofsimpler processors, can be implemented in approximately the same
area. We believe that the multiprocessor microarchitecture will beeasier to implement and will reach a higher clock rate.

Our results show that on applications that cannot be parallelized thesuperscalar microarchitecture performs 30% better than one processor of the multiprocessor architecture. On applications with finegrained thread-level parallelism the multiprocessor microarchitecture can exploit this parallelism so that the superscalar microarchitecture is at most 10% better, even at the same clock rate. We
anticipate that the higher clock rates possible with simpler CPUs in
the multiprocessor will eliminate this small performance difference.
On applications with large grained thread-level parallelism andmultiprogramming workloads the multiprocessor microarchitecture
performs 50–100% better than the wide superscalar microarchitecture.

Acknowledgments
We would like to thank Edouard Bugnion, Mendel Rosenblum, Ben
Verghese and Steve Herrod for their help with SimOS, Doug Williams for his assistance with MXS, the SUIF compiler group for useof their applications, and the reviewers for their insightful comments. This work was supported by DARPA contracts DABT63-95C-0089 and DABT63-94-C-0054.

References

SimOS approach,” IEEE Parallel and Distributed
Technology, vol. 4, no. 3, 1995.

[1]

S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C.-W.
Tseng, “An overview of the SUIF compiler for scalable
parallel machines,” Proceedings of the Seventh SIAM
Conference on Parallel Processing for Scientific
Compiler, San Francisco, 1995.

[19] M. Rosenblum, E. Bugnion, S. Herrod, E. Witchel, and A.
Gupta, “The impact of architectural trends on operating
system performance,” Proceedings of 15th ACM
symposium on Operating Systems Principles, Colorado,
December, 1995.

[2]

S. Amarasinghe et.al., “Hot compilers for future hot chips,”
presented at Hot Chips VII, Stanford, CA, 1995.

[3]

D. W. Anderson, F. J. Sparacio, and R. M. Tomasulo, “TheIBM System/360 model 91: Machine philosophy andinstruction-handling,” IBM Journal of Research andDevelopment, vol. 11, pp. 8–24, 1967.

[20] G. Sohi and M. Franklin, “High Bandwidth Data Memory
Systems for Superscalar Processors,” Proceedings of 4th
Int. Conf. Architectural Support for Programming
Languages and Operating Systems (ASPLOS-IV), pp. 53–
62, April, 1991.

[4]

W. Bowhill et. al., “A 300MHz 64b quad-issue CMOS
microprocessor,” IEEE International Solid-State Circuits
Conference Digest of Technical Papers, pp. 182–183, San
Francisco, CA, 1995.

[5]

E. Bugnion, J. Anderson, T. Mowry, M. Rosenblum, and M.
Lam.
“Compiler-Directed
Page
Coloring
for
Multiprocessors,” Proceedings Seventh International
Symp. Architectural Support for Programming
Languages and Operating Systems (ASPLOS VII),
October 1996.

[6]“Chart watch: RISC processors,” Microprocessor Report, vol.
10, no. 1, p. 22, January, 1996.

[7]

T. Conte, K. Menezes, P. Mills, and B. Patel, “Optimization of
instruction fetch mechanisms for high issue rates,”
Proceedings of the 22nd Annual International Symposiumon Computer Architecture, pp. 333–344, Santa
Margherita Ligure, Italy, June, 1996.

[8]

D. Dobberpuhl et. al., “A 200-MHz 64-b dual-issue CMOS
microprocessor,” IEEE Journal of Solid-State Circuits,
vol. 27, pp. 1555–1557, 1992.

[9]

Don Drappper, “The interconnect nightmare,” IEEE
International Solid-State Circuits Conference Digest ofTechnical Papers, p. 278, San Francisco, CA, 1996.

[10] K. Farkas, N. Jouppi, and P. Chow, “Register fileconsiderations in dynamically scheduled processors,”
Proceedings of the 2nd Int. Symp. on High-Performance
Computer Architecture, pp. 40–51, San Jose, CA,
February, 1996.
[11] J. Hennessy and N. Jouppi, “Computer technology andarchitecture: an evolving interaction,” IEEE Computer
Magazine, vol. 24, no. 1, pp. 18–29, 1991.
[12] J. L. Hennessy and D. A. Patterson, Computer Architecture A
Quantitative Approach 2nd Edition. San Francisco,California: Morgan Kaufman Publishers, Inc., 1996.
[13] M. Johnson, Superscalar Microprocessor Design. Englewood
Cliffs, NJ: Prentice Hall, Inc., 1991
[14] J. Lotz, G. Lesartre, S. Naffzinger, and D. Kipp, “A quad issue
out-of-order RISC CPU,” IEEE International Solid-State
Circuits Conference Digest of Technical Papers, pp. 210–
211, San Francisco, CA, 1996.
[15] S. McFarling, “Combining branch predictors,” WRL
Technical Note TN-36, Digital Equipment Corporation,
1993.
[16] B. A. Nayfeh, L. Hammond, and K. Olukotun, “Evaluating
alternatives for a multiprocessor microprocessor,”
Proceedings of 23rd Int. Symp. Computer Architecture,
pp. 66–77, Philadelphia, PA, 1996.
[17] J. Ousterhout, “Why aren’t operating systems getting faster as
fast as hardware?,” Summer 1990 USENIX Conference,
pp. 247–256, June 1990.
[18] M. Rosenblum, S. Herrod, E. Witchel, and A. Gupta, “The[21] J. E. Thornton, “Parallel operation in the Control Data 6600,”
Proceedings of Spring Joint Computer Conference, 1964.
[22] D. W. Wall, “Limits of Instruction-Level Parallelism,” Digital
Western Research Laboratory, WRL Research Report 93/
6, November 1993.
[23] S. C. Woo, M. Ohara, E. Torrie, J.P. Singh and A. Gupta, “TheSPLASH-2
Programs:
Characterization
andMethodological Considerations”, 22nd Annual Int. Symp.
Computer Architecture, Santa Margherita, Italy, June
1995.
[24] K. Yeager et. al., “R10000 Superscalar Microprocessor,”presented at Hot Chips VII, Stanford, CA, 1995.
[25] J. Zurawski, J. Murray and P. Lemmon, “The design andverification of the AlphaStation 600 5-series
workstation,” Digital Technical Journal, vol. 7, no. 1, pp.
89–99, 1995.