THE STANFORD HYDRA CMPCHIP MULTIPROCESSORS OFFER AN ECONOMICAL, SCALABLE ARCHITECTURE
FOR FUTURE MICROPROCESSORS. THREAD-LEVEL SPECULATION SUPPORTALLOWS THEM TO SPEED UP PAST SOFTWARE.

The Hydra chip multiprocessor(CMP) integrates four MIPS-based processors
and their primary caches on a single chip
together with a shared secondary cache. A standard CMP offers implementation and performance advantages compared to wide-issue
superscalar designs. However, it must be programmed with a more complicated parallel
programming model to obtain maximum performance. To simplify parallel programming,the Hydra CMP supports thread-level speculation and memory renaming, a paradigm thatallows performance similar to a uniprocessor ofcomparable die area on integer programs. This
article motivates the design of a CMP,
describes the architecture of the Hydra design
with a focus on its speculative thread support,
and describes our prototype implementation.

Lance Hammond
Benedict A. Hubbert
Michael Siu Why build a CMP?
As Moore’s law allows increasing numbers
Manohar K. Prabhu of smaller and faster transistors to be integrated on a single chip, new processors are
Michael Chen being designed to use these transistors effectively to improve performance. Today, mostKunle Olukotun microprocessor designers use the increasedtransistor budgets to build larger and more
Stanford University complex uniprocessors. However, several
problems are beginning to make this approachto microprocessor design difficult to continue. To address these problems, we have proposed that future processor design
methodology shift from simply making progressively larger uniprocessors to implementing more than one processor on each chip.1
The following discusses the key reasons why
single-chip microprocessors are a good idea.

0272-1732/00/$10.00  2000 IEEE

Parallelism
Designers primarly use additional transistors on chips to extract more parallelism fromprograms to perform more work per clock
cycle. While some transistors are used to build
wider or more specialized data path logic (toswitch from 32 to 64 bits or add special multimedia instructions, for example), most areused to build superscalar processors. These
processors can extract greater amounts of
instruction-level parallelism, or ILP, by finding nondependent instructions that occur
near each other in the original program code.
Unfortunately, there is only a finite amountof ILP present in any particular sequence of
instructions that the processor executes
because instructions from the same sequence
are typically highly interdependent. As aresult, processors that use this technique areseeing diminishing returns as they attempt to
execute more instructions per clock cycle, evenas the logic required to process multiple
instructions per clock cycle increases quadratically. A CMP avoids this limitation by
primarily using a completely different type ofparallelism: thread-level parallelism. We
obtain TLP by running completely separate
sequences of instructions on each of the separate processors simultaneously. Of course, a
CMP may also exploit small amounts of ILP
within each of its individual processors, since
ILP and TLP are orthogonal to each other.

Wire delay
As CMOS gates become faster and chips
become physically larger, the delay caused byinterconnects between gates is becoming more71

HYDRA CMPCentralized bus arbitration mechanisms
CPU 0

CPU 1

CPU 2

CPU 3

L1 inst.
cache L1 data cache
CPU 0 memory controller

L1 inst.
cache L1 data cache
CPU 1 memory controller

L1 inst.
cache L1 data cache
CPU 2 memory controller

L1 inst.
cache L1 data cache
CPU 3 memory controller

Write-through bus(64 bits)
Read/replace bus (256 bits)
On-chip L2 cache

Main memory interface

I/O bus interface

DRAM main memory

I/O devices

Figure 1. An overview of the Hydra CMP.

significant. Due to rapid process technology
improvement, within the next few years wires
will only be able to transmit signals over a small
portion of large processor chips during eachclock cycle.2 However, a CMP can be designed
so that each of its small processors takes up a
relatively small area on a large processor chip,minimizing the length of its wires and simplifying the design of critical paths. Only the more
infrequently used, and therefore less critical,
wires connecting the processors need to be long.

Design time
Processors are already difficult to design.
Larger numbers of transistors, increasingly
complex methods of extracting ILP, and wiredelay considerations will only make this worse.
A CMP can help reduce design time, however,
because it allows a single, proven processor
design to be replicated multiple times over adie. Each processor core on a CMP can bemuch smaller than a competitive uniprocessor,
minimizing the core design time. Also, a core
design can be used over more chip generations
simply by scaling the number of cores present
on a chip. Only the processor interconnection
logic is not entirely replicated on a CMP.

Why aren’t CMPs used now?
Since a CMP addresses all of these potential
problems in a straightforward, scalable manner, why aren’t CMPs already common? One

72

IEEE MICRO

reason is that integration densities are justreaching levels where these problems are
becoming significant enough to consider a paradigm shift in processor design. The primaryreason, however, is because it is very difficult toconvert today’s important uniprocessor programs into multiprocessor ones.
Conventional multiprocessor programming
techniques typically require careful data layout
in memory to avoid conflicts between processors, minimization of data communication
between processors, and explicit synchronization at any point in a program where
processors may actively share data. A CMP ismuch less sensitive to poor data layout andpoor communication management, since theinterprocessor communication latencies arelower and bandwidths are higher. However,sequential programs must still be explicitly
broken into threads and synchronized properly. Parallelizing compilers have been only
partially successful at automatically handlingthese tasks for programmers.3 As a result,
acceptance of multiprocessors has been slowed
because only a limited number of programmers have mastered these techniques.

Base Hydra design
To understand the implementation andperformance advantages of a CMP design, weare developing the Hydra CMP. Hydra is a
CMP built using four MIPS-based cores as its

individual processors (see Figure 1). Each corehas its own pair of primary instruction anddata caches, while all processors share a single, large on-chip secondary cache. The
processors support normal loads and storesplus the MIPS load locked (LL) and store conditional (SC) instructions for implementing
synchronization primitives.
Connecting the processors and the secondary cache together are the read and write
buses, along with a small number of addressand control buses. In the chip implementation,
almost all buses are virtual buses. While they
logically act like buses, the physical wires are
divided into multiple segments using repeaters
and pipeline buffers, where necessary, to avoid
slowing down the core clock frequencies.
The read bus acts as a general-purpose systembus for moving data between the processors,secondary cache, and external interface to offchip memory. It is wide enough to handle anentire cache line in one clock cycle. This is anadvantage possible with an on-chip bus that all
but the most expensive multichip systems cannot match due to the large number of pins thatwould be required on all chip packages.
The narrower write bus is devoted to writing all writes made by the four cores directly tothe secondary cache. This allows the permanent machine state to be maintained in the secondary cache. The bus is pipelined to allow
single-cycle occupancy by each write, preventing it from becoming a system bottleneck. The
write bus also permits Hydra to use a simple,
invalidation-only coherence protocol to maintain coherent primary caches. Writes broadcast
over the bus invalidate copies of the same line
in primary caches of the other processors. No
data is ever permanently lost due to these invalidations because the permanent machine stateis always maintained in the secondary cache.
The write bus also enforces memory consistency in Hydra. Since all writes must passover the bus to become visible to the otherprocessors, the order in which they pass is
globally acknowledged to be the order inwhich they update shared memory.
We were primarily concerned with minimizing two measurements of the design: thecomplexity of high-speed logic and the latency of interprocessor communication. Since
decreasing one tends to increase the other, a
CMP design must strive to find a reasonablebalance. Any architecture that allows interprocessor communication between registers
or the primary caches of different processors
will add complex logic and long wires to paths
that are critical to the cycle time of the individual processor cores. Of course, this complexity results in excellent interprocessor
communication latencies—usually just one
to three cycles. Past results have shown thatsharing this closely is helpful, but not if it
extends the access time to the registers and/or
primary caches. Consequently, we chose notto connect our processors this tightly. On theother hand, these results also indicated that
we would not want to incur the delay of an
off-chip reference, which can often take 100
or more cycles in modern processors during
each interprocessor communication.
Because it is now possible to integrate reasonable-size secondary caches on processor diesand since these caches are typically not tightly
connected to the core logic, we chose to usethat as the point of communication. In the
Hydra architecture, this results in interprocessor communication latencies of 10 to 20 cycles,
which are fast enough to minimize the performance impact from communication delays.
After considering the bandwidth required byfour single-issue MIPS processors sharing a secondary cache, we concluded that a simple bus
architecture would be sufficient to handle thebandwidth requirements for a four. This is
acceptable for a four- to eight-processor Hydra
implementation. However, designs with morecores or faster individual processors may need
to use either more buses, crossbar interconnections, or a hierarchy of connections.

Parallel software performance
We have performed extensive simulation toevaluate the potential performance of theHydra design. Using a model with the memory hierarchy summarized in Table 1 (nextpage), we compared the performance of a single Hydra processor to the performance of all
four processors working together. We used the
10 benchmarks summarized in Table 2 to generate the results presented in Figure 2 (p. 75).
The results indicate that for multiprogrammed workloads and highly parallel benchmarks such as large matrix-based or multimedia
applications, we can obtain nearly linear
speedup by using multiple Hydra processors

MARCH–APRIL 2000

73

HYDRA CMP

Table 1. The Hydra system configuration used for our simulations.
Characteristic
Configuration
Capacity
Bus width
Access time
Associativity
Line size
Write policy
Inclusion

L1 cache
Separate I and D SRAM cachepairs for each CPU
16 Kbytes each32-bit connection to CPU
1 CPU cycle
4 way
32 bytes
Write through, no allocate on write
N/A

L2 cacheShared, on-chip SRAM cache

Main memory
Off-chip DRAM

2 Mbytes
256-bit read bus + 32-bit write bus
5 CPU cycles
4 way
64 bytes
Write back, allocate on writes
Inclusion enforced by L2 on L1 caches

128 Mbytes
64-bit bus at half CPU speed
At least 50 cycles
N/A
4-Kbyte pages
Write back (virtual memory)
Includes all cached data

Table 2. A summary of the conventionally parallelized applications we used to makeperformance measurements with Hydra.
PurposeGeneraluniprocessor
applications

Matrix andmultimedia
applications

Multiprogrammed
workloads

Application
compress

SourceSPEC95

Description
Entropy-encoding file compression

eqntott

SPEC92

Logic minimization

m88ksimSPEC95

CPU simulation of Motorola 88000

apsi

SPEC95

Weather and air pollution modeling

MPEG2Mediabench suiteapplu

SPEC95

Decompression of an MPEG-2
bitstream
Solver for partial differential equations

swim

SPEC95

Grid-based finite difference modeling

tomcatv

SPEC95

Mesh generation

OLTP

TPC-B

Database transaction processing

pmake

Unix command

Parallel compilation ofseveral source files

working together. These speedups typically will
be much greater than those that can beobtained simply by making a single large ILP
processor occupying the same area as the four
Hydra processors.1 In addition, multiprogrammed workloads are inherently parallel,
while today’s compilers can automatically parallelize most dense matrix Fortran applications.3
However, there is still a large category of lessparallel applications, primarily integer ones thatare not easily parallelized (eqntott, m88ksim,
and apsi). The speedups we obtained with
Hydra on these applications would be difficult

74

IEEE MICROHow parallelized
Not possible using
conventional means
On inner bit vector
comparison loop
Simulated CPU is pipelined
across processors
Automatically by the SUIF
compiler“Slices” in the input bitstream
distributed among processors
Automatically by the SUIF
compiler
Automatically by the SUIF
compiler
Automatically by the SUIF
compiler
Different transactions executein parallel
Compilations of different files
execute in parallel

or impossible to achieve on a conventional multiprocessor, with the long interprocessor communication latencies required by a multichip
design. Even on Hydra, the speed improvement
obtained after weeks of hand-parallelization isjust comparable to that obtainable with a similar-size ILP processor with no programmer
effort. More troubling, compress represents alarge group of applications that cannot be parallelized at all using conventional techniques.

Thread-level speculation: A helpful extension
Applications such as database and Web servers

4
General uniprocessor
applications

3.5
Speedup over one Hydra CPU

3

Matrix and multimedia
applications
Multiprogrammed workload

2.5
2
1.5
1

pmake

OLTP

tomcatv

swim

applu

MPEG2

apsi

m88ksim0

eqntott

0.5

compress

perform well on conventional multiprocessors,
and therefore these applications will provide theinitial motivation to adopt CMP architectures,at least in the server domain. However, general
uniprocessor applications must also work wellon CMP architectures before they can everreplace uniprocessors in most computers. Hence,
there needs to be a simple, effective way to parallelize even these applications. Hardware support for thread-level speculation is a promisingtechnology that we chose to add to the basic
Hydra design, because it eliminates the need forprogrammers to explicitly divide their original
program into independent threads.
Thread-level speculation takes the sequenceof instructions run during an existing uniprocessor program and arbitrarily breaks it into asequenced group of threads that may be run inparallel on a multiprocessor. To ensure that eachprogram executes the same way that it did originally, hardware must track all interthreaddependencies. When a “later” thread in thesequence causes a true dependence violation byreading data too early, the hardware must ensurethat the misspeculated thread—or at least the
portion of it following the bad read—re-executes with the proper data. This is a considerably
different mechanism from the one used to
enforce dependencies on conventional multiprocessors. There, synchronization is inserted
so that threads reading data from a different
thread will stall until the correct value has been
written. This process is complex because it isnecessary to determine all possible true dependencies in a program before synchronization
points may be inserted.
Speculation allows parallelization of a program into threads even without prior knowledge of where true dependencies between
threads may occur. All threads simply run inparallel until a true dependency is detected
while the program is executing. This greatly
simplifies the parallelization of programs
because it eliminates the need for human programmers or compilers to statically place synchronization points into programs by hand orat compilation. All places where synchronization would have been required are simply
found dynamically when true dependencies
actually occur. As a result of this advantage,
uniprocessor programs may be obliviously parallelized in a speculative system. While conventional parallel programmers must

Application

Figure 2. Speedup of conventionally parallelized applications running on
Hydra compared with the original uniprocessor code running on one of
Hydra’s four processors.

constantly worry about maintaining program
correctness, programmers parallelizing code
for a speculative system can focus solely onachieving maximum performance. The speculative hardware will ensure that the parallelcode always performs the same computation
as the original sequential program.
Since parallelization by speculation dynamically finds parallelism among program threads
at runtime, it does not need to be as conservative as conventional parallel code. In many
programs there are many potential dependencies that may result in a true dependency, butwhere dependencies seldom if ever actuallyoccur during the execution of the program. A
speculative system may attempt to run thethreads in parallel anyway, and only back up
the later thread if a dependency actually occurs.
On the other hand, a system dependent on
synchronization must always synchronize at
any point where a dependency might occur,
based on a static analysis of the program,whether or not the dependency actually everoccurs at runtime. Routines that modify data
objects through pointers in C programs are a

MARCH–APRIL 200075

HYDRA CMP

Time

Original sequential loop

Speculatively parallelized loop

Iteration i

Iteration i

Read X

Read X

Read X

Read X

Write X

Write X

Read X

Read X

Forwardingfrom write:
Iteration i+1

Violation

Read X
Read X
Forwarding

Write X

Iteration i +1
Read X
Read X(b)

Read X
Write X
Read X(a)
Writes after violations

Writes after successful iterations
Iteration i

Iteration i

Iteration i +1

Iteration i +1
Write A

Write X

Time

Read X
Write X

Write B

Write X

1
Discarded2

Permanent
state
(d)

(c)
Multiple memory "views"
Iteration i
Iteration i +1
Write X

Time

Write X
Read X

Read X

Iteration i +2
Read X(e)

Figure 3. Five basic requirements for special coherency hardware: a sequential program thatcan be broken into two threads (a); forwarding and violations caused by interaction of reads
and writes (b); speculative memory state eliminated following violations (c); reordering of
writes following thread commits (d); and memory renaming among threads (e).

76IEEE MICRO

frequent source of this problem within many integer
applications. In these programs, a compiler (and sometimes even a programmer
performing hand parallelization) will typically have toassume that any later pointerreads may be dependent on
the latest write of data using apointer, even if that is rarelyor never the case. As a result,a significant amount of
thread-level parallelism canbe hidden by the way the
uniprocessor code is written,
and therefore wasted as acompiler conservatively parallelizes a program.
Note that speculation andsynchronization are notmutually exclusive. A program with speculative threads
can still perform synchronization around uses ofdependent data, but this synchronization is optional. As aresult, a programmer or feedback-driven compiler can still
add synchronization into a
speculatively parallelized program if that helps the program execute faster. In our
experiments, we found a few
cases where synchronization
protecting one or two key
dependencies in a speculatively parallelized program
produced speedup by dramatically reducing the number of violations that
occurred. Too much synchronization, however, tended tomake the speculative parallelization too conservative andwas a detriment to performance.
To support speculation, we
need special coherency hardware to monitor data sharedby the threads. This hardware
must fulfill five basic requirements, illustrated in Figure 3.

The figure shows some typical data access patterns in two threads, i and i + 1. Figure 3ashows how data flows through these accesses
when the threads are run sequentially on a normal uniprocessor. Figures 3b-d show how the
hardware must handle the requirements.
1. Forward data between parallel threads.
While good thread selection can minimize the data shared among threads, typically a significant amount of sharing isrequired, simply because the threads arenormally generated from a program inwhich minimizing data sharing was nota design goal. As a result, a speculative
system must be able to forward shareddata quickly and efficiently from an earlier thread running on one processor to alater thread running on another. Figure
3b depicts this.
2. Detect when reads occur too early (RAWhazards). The speculative hardware must
provide a mechanism for tracking reads
and writes to the shared data memory. If
a data value is read by a later thread andsubsequently written by an earlier thread,the hardware must notice that the read
retrieved incorrect data since a true
dependence violation has occurred. Violation detection allows the system todetermine when threads are not actually
parallel, so that the violating thread canbe re-executed with the correct data values. See Figure 3b.
3. Safely discard speculative state after violations. As depicted in Figure 3c, speculative memory must have a mechanism
allowing it to be reset after a violation.
All speculative changes to the machinestate must be discarded after a violation,
while no permanent machine state may
be lost in the process.
4. Retire speculative writes in the correct order(WAW hazards). Once speculative threads
have completed successfully, their statemust be added to the permanent state of
the machine in the correct program
order, considering the original sequencing of the threads. This may require thehardware to delay writes from later
threads that actually occur before writes
from earlier threads in the sequence, as
Figure 3d illustrates.

5. Provide memory renaming (WAR hazards).
Figure 3e depicts an earlier thread reading an address after a later processor has
already written it. The speculative hardware must ensure that the older threadcannot “see” any changes made by later
threads, as these would not have occurred
yet in the original sequential program.
This process is complicated by the factthat each processor will eventually berunning newly generated threads (i + 2
in the figure) that will need to “see” thechanges.
In some proposed speculative hardware, thelogic enforcing these requirements monitors
both the processor registers and the memory
hierarchy.4 However, in Hydra we chose tohave hardware only enforce speculative coherence on the memory system, while software
handles register-level coherence.
In addition to speculative memory support,
any system supporting speculative threads
must have a way to break up an existing program into threads and a mechanism for controlling and sequencing those threads acrossmultiple processors at runtime. This generally consists of a combination of hardware andsoftware that finds good places in a program
to create new, speculative threads. The systemthen sends these threads off to be processedby the other processors in the CMP.
While in theory a program may be speculatively divided into threads in a completely
arbitrary manner, in practice one is limited.
Initial program counter positions (and, for
Hydra, register states) must be generated
when threads are started. As a result, we investigated two ways to divide a program into
threads: loops and subroutine calls. Withloops, several iterations of a loop body can bestarted speculatively on multiple processors.
As long as there are only a few straightforward
loop-carried dependencies, the execution ofloop bodies on different processors can beoverlapped to achieve speedup. Using subroutines, a new thread can start to run thecode following a subroutine call’s return, while
the original thread actually executes the subroutine itself (or vice-versa). As long as thereturn value from the subroutine is predictable(typically, when there is no return value) andany side effects of the subroutine are not used

MARCH–APRIL 2000

77

HYDRA CMPCentralized bus arbitration mechanisms
CPU 0

CP2

CPU 1

CP2

CPU 2

CP2

CPU 3

CP2

L1 inst. L1 data cache andspeculation bitscache

L1 inst. L1 data cache andspeculation bitscache

L1 inst. L1 data cache andspeculation bitscache

L1 inst. L1 data cache andspeculation bitscache

CPU 0 memory controller

CPU 1 memory controller

CPU 2 memory controller

CPU 3 memory controller

Write-through bus(64 bits)
Read/replace bus (256 bits)
Speculation write buffers
0

1

2

3

RetireMain memory interface

I/O bus interface

DRAM main memory

I/O devices

On-chip L2 cache

Figure 4. An overview of Hydra with speculative support.

immediately, the two threads can run in parallel. In general, achieving speedup with thistechnique is more challenging because thread
sequencing and load balancing among theprocessors is more complicated with subroutines than loops.
Once threads have been created, the speculation runtime system must select the four least
speculative threads available and allocate themto the four processors in Hydra. Note that theleast speculative, or head, thread is special. This
thread is actually not speculative at all, since
all older threads that could have caused it toviolate have already completed. As a result, it
can handle events that cannot normally behandled speculatively (such as operating system calls and exceptions). Since all threads
eventually become the head thread, simply
stalling a thread until it becomes the head willallow the thread to process these events during speculation.

Implementing speculation in Hydra
Speculation is an effective method forbreaking an existing uniprocessor program
into multiple threads. However, the threads
created automatically by speculation often
require fast interprocessor communication of

78

IEEE MICRO

large amounts of data. After all, minimizing
communication between arbitrarily createdthreads is not a design consideration in most
uniprocessor code. A CMP like Hydra is necessary to provide low-enough interprocessor
communication latencies and high-enoughinterprocessor bandwidth to allow the designof a practical speculative thread mechanism.
Among CMP designs, Hydra is a particularly good target for speculation because it has
write-through primary caches that allow allprocessor cores to snoop on all writes performed. This is very helpful in the design ofviolation-detection logic. Figure 4 updates
Figure 1, noting the necessary additions. The
additional hardware is enabled or bypassed
selectively by each memory reference, depending upon whether a speculative thread generates the reference.
Most of the additional hardware is contained in two major blocks. The first is a set of
additional tag bits added to each primarycache line to track whether any data in the line
has been speculatively read or written. The
second is a set of write buffers that hold speculative writes until they can be safely committed into the secondary cache, which isguaranteed to hold only nonspeculative data.

NonspeculativeSpeculative,
Speculative,
One buffer is allocated tohead CPU
earlier CPU
later CPU“Me”
each speculative thread currently running on a Hydra
CPU
CPU
CPU
CPU
i −2
i −1
i
i +1
processor, so the writes fromdifferent threads are always
kept separate. Only when1
speculative threads complete
2
successfully are the contents of
L1
these buffers actually written
cache
into the secondary cache andmade permanent. As shown in
4
3
2
1
Figure 4, one or more extra
buffers may be included to
Write
Write
Write
Write
allow buffers to be drained
bufferbufferbufferbuffer
L2
into the secondary cache incacheparallel with speculative execution on all of the CPUs. We
Modified bit of the newly read line is set
Preinvalidate bit is set if
have previously published5
if there is a hit in any of these buffers
there is a hit here
more details about the addi(or, more optimally, only i −1 and i )tional primary cache bits andsecondary cache buffers.
Figure 5. How secondary cache speculative buffers are read. 1) A CPU reads from its L1
To control the threadcache. The L1 read bit of any hit lines are set. 2) The L2 and write buffers are checked insequencing in our system, weparallel in the event of an L1 miss. Priority encoders on each byte (indicated by priorities 1-4
also added a small amount ofhere) pull in the newest bytes written to a line. The appropriate word is delivered to the CPU
hardware to each core using
and L1 with the L1 modified and preinvalidate bits set appropriately.
the MIPS coprocessor interface. These simple “speculathem, they will miss in their primarytion coprocessors” consist of several control
cache and access the secondary cache. At
registers, a set of duplicate secondary cache
this point, as is outlined in Figure 5, thebuffer tags, a state machine to track the curspeculative data contained in the write
rent thread sequencing among the processors,buffers of the current or older threads
and interrupt logic that can start software hanreplaces data returned from the secdlers when necessary to control thread
ondary cache on a byte-by-byte basis justsequencing. These software handlers are
responsible for thread control and sequencing.
before the composite line is returned toPrior publications5,6 provide complete details
the processor and primary cache. Overof how these handlers work for sequence specall, this is a relatively simple extension toulative threads in the Hydra hardware.
the coherence mechanism used in the
Together with the architecture of Hydra’s
baseline Hydra design.
existing write bus, the additional hardware
2. Detect when reads occur too early. Primaallows the memory system to handle the fivery cache bits are set to mark any reads
memory system requirements outlined previthat may cause violations. Subsequently,
ously in the following ways:
if a write to that address from an earlier
thread invalidates the address, a violation
1.Forward data between parallel threads.
is detected, and the thread is restarted.
When a speculative thread writes data
3. Safely discard speculative state after violations. Since all permanent machine state inover the write bus, all more-speculative
Hydra is always maintained within the secthreads that may need the data have their
ondary cache, anything in the primary
current copy of that cache line invalidatcaches may be invalidated at any timeed. This is similar to the way the system
without risking a loss of permanent state.
works during nonspeculative operation.
As a result, any lines in the primary cache
If any of the threads subsequently need
containing speculative data (marked with
the new speculative data forwarded to

MARCH–APRIL 2000

79

HYDRA CMPOther CMP and TLS efforts
Several other research groups have investigated the design of chip multiprocessors andthe implementation of thread-level speculation mechanisms. While there are too many tomention all here, a few of the most important follow:•

Wisconsin Multiscalar.4,7 This CMP design proposed the first reasonable hardware to
implement TLS. Unlike Hydra, Multiscalar implements a ringlike network between allof the processors to allow direct register-to-register communication. Along with hardware-based thread sequencing, this type of communication allows much smaller threads
to be exploited at the expense of more complex processor cores. The designers proposed
two different speculative memory systems to support the Multiscalar core. The firstwas a unified primary cache, or address resolution buffer (ARB). Unfortunately, the ARB
has most of the complexity of Hydra’s secondary cache buffers at the primary cachelevel, making it difficult to implement. Later, they proposed the speculative versioning
cache. The SVC uses write-back primary caches to buffer speculative writes in the primary caches, using a sophisticated coherence scheme.
• Carnegie-Mellon Stampede.8 This CMP-with-TLS proposal is very similar to Hydra,
including the use of software speculation handlers. However, the hardware is simpler
than Hydra’s. The design uses write-back primary caches to buffer writes—similar to
those in the SVC—and sophisticated compiler technology to explicitly mark all memory references that require forwarding to another speculative thread. Their simplified
SVC must drain its speculative contents as each thread completes, unfortunately resulting in heavy bursts of bus activity.
• MIT M-machine.9 This one-chip CMP design has three processors that share a primary cache and can communicate register-to-register through a crossbar. Each processor
can also switch dynamically among several threads. As a result, the hardware connecting processors together is quite complex and slow. However, programs executedon the M-machine can be parallelized using very fine-grain mechanisms that are impossible on an architecture that shares outside of the processor cores, like Hydra. Performance results show that on typical applications extremely fine-grained parallelization
is often not as effective as parallelism at the levels that Hydra can exploit. The overhead incurred by frequent synchronizations reduces the effectiveness.
Recently, Sun and IBM announced plans to make CMPs. Sun’s plans offer limited TLS support.
IBM Power4.10 This is the first commercially proposed CMP targeted at servers andother systems that already make use of conventional multiprocessors. It resembles
Hydra but does not have TLS support (an unnecessary feature for most types of servers)
and has two large processors per chip.
• Sun MAJC.11 This CMP with a shared primary cache is designed to support Java execution. It also supports a subroutine-based TLS scheme. MAJC has interrupt hardware
similar to that in our speculative coprocessors, but it implements speculative memory
using only software handlers invoked during the execution of each sharable load orstore. This is possible with Java, the target language, because the rare loads and storesto global objects that can be shared among subroutines are clearly defined in Java
bytecode binaries. However, even with the shared primary cache allowing quick interprocessor communication of changes to the speculation-control memory structures
and the low percentage of shared memory accesses, it may be difficult for this scheme
to scale to more than two processors due to the overhead of the software handlers.
•a special modified bit) may simply be invalidated all at once to clear any speculative

80

IEEE MICRO

state from a primary cache. In parallel withthis operation, the secondary cache buffer
for the thread may be emptied to discard
any speculative data written by the thread
without damaging data written by otherthreads or the permanent state of themachine in the secondary cache.
4. Retire speculative writes in the correct order.
Separate secondary cache buffers aremaintained for each thread. As long as
these are drained into the secondary
cache in the original program sequenceof the threads, they will reorder speculative memory references correctly. The
thread-sequencing system in Hydra alsosequences the buffer draining, so thebuffers can meet this requirement.
5. Provide memory renaming. Each processor
can only read data written by itself or earlier threads when reading its own primary cache or the secondary cache buffers.
Writes from later threads don’t cause
immediate invalidations in the primarycache, since these writes should not be visible to earlier threads. This allows each primary cache to have its own local copy ofa particular line. However, these “ignored”
invalidations are recorded using an additional pre-invalidate primary cache bit
associated with each line. This is because
they must be processed before a different
speculative or nonspeculative thread executes on this processor. If a thread has toload a cache line from the secondary
cache, the line it recovers only contains
data that it should actually be able to “see,”from its own and earlier buffers, as Figure
5 indicates. Finally, if future threads havewritten to a particular line in the primarycache, the pre-invalidate bit for that line
is set. When the current thread completes,
these bits allow the processor to quickly
simulate the effect of all stored invalidations caused by all writes from later processors all at once, before a new thread begins
execution on this processor.
Based on the amount of memory and logic
required, we estimate that the cost of adding
speculation hardware is comparable to adding
an additional pair of primary caches to the system. This enlarges the Hydra die only by afew percent.

Table 3. A summary of the speculatively parallelized applications used to make performance measurementswith Hydra. Applications in italics were also hand-parallelized and run on the base Hydra design.

SPEC92
Numeric recipes

Speculation performance

4
3.5
3
2.5
Speedup

2
1.5
1
0.5
0
compress

We extended our model of the Hydra system with speculation support to verify ourthread-level speculation mechanisms. On all
applications except eqntott—which was parallelized using subroutine speculation—weused our source-to-source loop-translating
system to convert loops in the original programs to their speculative forms. Even with
our simple, early programming environment,
we could parallelize programs just by picking
out which loops and/or subroutines we wanted speculatively parallelized. We then let thetools do the rest of the work for us.
Both because this design environment is Cbased and Fortran programs can often be automatically parallelized using compilers such as
SUIF, we limited our set of applications to awide variety of integer and floating-point C
programs. Table 3 lists them. Many of these
programs are difficult or impossible to parallelize using conventional means due to thepresence of frequent true dependencies. However, all of the more highly parallel applications
listed in Table 3 can be parallelized by hand.
Still, automatically parallelizing compilers arestymied by the presence of many C pointersin the original source code that they cannot
statically disambiguate at compile time.
Figure 6 summaries our results. After our
initial speculative runs with unmodified loops

simplexear
simplexear

Mediabench suite
SPEC92
Numeric recipes

cholesky

MPEG2
alvin
choleskyalvin

SPEC95

mpeg2

ijpeg

ijpeg

Unix command

wc

wc

m88ksimSPEC92
Unix command
SPEC95

How parallelized
Speculation on loop for processing each input
character
Logic minimization
Subroutine speculation on core quick sort routine
Finds matches to a regular expression in a file Speculation on loop for processing each input line
CPU simulation of Motorola 88000
Speculation on loop for processing each
instruction
Counts the number of characters, words,
Speculation on loop for processing each input
and lines in a filecharacter
Compression of an RGB image to a JPEG file Speculation on several different loops used toprocess the image
Decompression of an MPEG-2 bitstream
Speculation on loop for processing slices
Neural network training
Speculation on 4 key loops
Cholesky decomposition and substitution
Speculation on main decomposition andsubstitution loops
Inner ear modelingSpeculation on outer loop of modelLinear algebra kernels
Speculation on several small loops

grep

eqntott
grep
m88ksim

Description
Entropy-encoding compression of a fileeqntott

Application Sourcecompress SPEC95

Application

Figure 6. Speedup of speculatively parallelized applications running on Hydracompared with the original uniprocessor code running on one of Hydra’s four
processors. The gray areas show the improved performance following tuningwith feedback-based code.

from the original programs, we used feedback
from our first simulations to optimize our

MARCH–APRIL 2000

81

HYDRA CMP

benchmarks by hand. This avoided the mostcritical violations that caused large amounts
of work to be discarded during restarts. These
optimizations were usually minor—usuallyjust moving a line of code or two or adding
one synchronization point. 6 However, they
had a dramatic impact on benchmarks such
as MPEG2.
Overall, these results are at least comparable to and sometimes better than a single large
uniprocessor of similar area running theseapplications, based on our past work simulating CMPs and uniprocessors.1
Of course, a CMP can also perform fasterby running fully parallelized programs without speculation, when those programs areavailable. A uniprocessor cannot. It is evenpossible to mix and match using multiprogramming. For example, two processors could
be working together on a speculative application, while others work on a pair of completely different jobs. While we have not fully
implemented it in our prototype, we could
relatively easily enhance the speculative support routines so that multiple speculative tasks
could run simultaneously. Two processors
would run one speculative program, and two
would run a completely different speculative
program. In this manner, it is possible for a
CMP to nearly always outperform a large
uniprocessor of comparable area.
Speedups are only a part of the story, however. Speculation also makes parallelizationmuch easier, because a parallelized programthat is guaranteed to work exactly like theuniprocessor version can be generated automatically. As a result, programmers only need
to worry about choosing which program sections should be speculatively parallelized andtweaked for performance optimization. Even
when optimization is required, we found that
speculative parallelization typically took a single programmer a day or two per application.
In contrast, hand parallelization of these C
benchmarks typically took one programmer
anywhere from a week to a month, since it wasnecessary to worry about correctness and performance throughout the process. As a result,even though adding speculative hardware to
Hydra will make the chip somewhat harderto design and verify, the reduced cost of generating parallel code will offer significant
advantages.

82

IEEE MICRO

Prototype implementation
To validate our simulations, develop more
speculative software, and verify that the Hydraarchitecture is as simple to design as we believe
it to be, we are working with IDT to manufacture a prototype Hydra. It will use IDT’s
embedded MIPS-based RC32364 core and
SRAM macrocells. We have a Verilog modelof the chip and are moving it into a physicaldesign using synthesis. With 8-Kbyte primary instruction and data caches and approximately 128 Kbytes of on-chip secondary
cache, the die (depicted in Figure 7) will be
about 90 mm2 in IDT’s 0.25-micron process.
We based these area and layout estimates on
the current RC32364 layout and area estimates of new components obtained using our
Verilog models of the different sections of theHydra memory system.
The memory system we are designing toconnect the IDT components together consists of the following:
our speculative coprocessor,
interconnection buses,• controllers for all memory resources,• speculative buffers and bits,• a simple off-chip main memory controller, and• an I/O and debugging interface that we
can drive using a host workstation.
••

We are designing most of this using a fairly straightforward standard cell methodology.
The clock rate target for the cores is about 250
MHz, and we plan on inserting pipeline stages
into our memory system logic as necessary to
avoid slowing the cores. The most critical partof the circuit design will be in the central arbitration mechanism for the memory controllers. This circuit is difficult to pipeline,
must accept many requests for arbitration
every cycle, and must respond to each request
with a grant signal. The large numbers of highfan-in and fan-out gates that must operate
during every cycle make it a challenging circuit design problem.

A

chip multiprocessor such as Hydra will
be a high-performance, economical alternative to large single-chip uniprocessors. A
CMP of comparable die area can achieve performance similar to a uniprocessor on integer11 mmInstruction
cache
CPU
core

CPU
core

Systemcontrol
Data
cache

Memorycontrol

L2 cachebank

Systemcontrol
MMU

MMU

Memorycontrol

L2 cache
bank

Data
cache

Centralresource arbiter

8 mm
I/O bus control

L2
cache
tags

L2
control

L2 buffers

L2 buffers

L2
control

L2 buffers

L2 cache
bank

L2
cache
tags

L2 cachebank

L2 buffers

Processor-memory communication buses
Centraladdress arbiter
Data
cache

Memorycontrol

MMU

MMU

Systemcontrol

Memorycontrol

Data
cache

Systemcontrol
CPU
core

CPU
core

Instruction
cache

Main memory control

Instruction
cache

Instruction
cache

Figure 7. The floor plan of the Hydra implementation.

programs using thread-level speculation
mechanisms. In addition, with multiprogrammed workloads or highly parallel applications a CMP can significantly outperform auniprocessor of comparable cost by operating
as a multiprocessor. Furthermore, the hardware required to support thread-level speculation is not particularly area-intensive.
Inclusion of this feature is not expensive, eventhough it can significantly increase the number of programs that can be easily parallelized
to fully use the CMP.
MICRO
Acknowledgments
Many people gave us invaluable help during the Hydra design. Basem Nayfeh guided
the early development of Hydra’s memory system and thread-level speculation hardware.
Monica Lam, Jeff Oplinger, and David Heine
from the SUIF group provided help with compiler support and analysis of early speculation
algorithms. Nick Kucharewski, Raymond M.

Chu, Tuan Luong, and Maciek Kozyrczak at
IDT worked closely with us during the processof building the Hydra prototype.
US Defense Advanced Research Projects
Agency contracts DABT 63-95-C-0089 and
MDA 904-98-C-A933 provided researchfunding.
References
1. K. Olukotun et al., “The Case for a Single Chip
Multiprocessor,” Proc. Seventh Int’l Conf. for
Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII),
ACM Press, New York, Oct. 1996, pp. 2-11.
2. D. Matzke, “Will Physical Scalability Sabotage Performance Gains?,” Computer, Sep.
1997, pp. 37-39.
3. M.W. Hall et al., “Maximizing Multiprocessor Performance With the SUIF Compiler,”
Computer, Dec. 1996, pp. 84-88.
4. G. Sohi, S. Breach, and T. Vijaykumar, “Multiscalar Processors,” Proc. 22nd Annual Int’l

MARCH–APRIL 2000

83

HYDRA CMP

5.

6.

7.

8.

9.

10.

11.

Symp. Computer Architecture, ACM Press,
Jun. 1995, pp. 414-425.
L. Hammond, M. Willey, and K. Olukotun,“Data Speculation Support for a Chip Multiprocessor,” Proc. Eighth Int’l Conf. Architectural
Supportfor
Programming
Languages and Operating Systems (ASPLOS-VIII), ACM Press, Oct. 1998, pp. 58-69.
K. Olukotun, L. Hammond, and M. Willey,“Improving the Performance of Speculatively Parallel Applications on the Hydra
CMP,” Proc. 1999 Int’l Conf. Supercomputing, ACM Press, June 1999, pp. 21-30.
S. Gopal et al., “Speculative Versioning
Cache,” Proc. Fourth Int’l Symp. High-Performance Computer Architecture (HPCA-4),
IEEE Computer Society Press, Los Alamitos,
Calif., Feb. 1998, pp. 195-205.
J.G. Steffan and T. Mowry, “The Potential
for Using Thread-level Data Speculation to
Facilitate Automatic Parallelization,” Proc.
Fourth Int’l Symp. High-Performance Computer Architecture (HPCA-4), IEEE CS Press,
Feb. 1998, pp. 2-13.
S. Keckler et al., “Exploiting Fine-Grain
Thread Level Parallelism on the MIT MultiALU Processor,” Proc. 25th Ann. Int’l Symp.
Computer Architecture, ACM Press, Jun.Jul. 1998, pp. 306-317.
J. Kahle, “The IBM Power4 Processor,”
Microprocessor Forum presentation reported
in: K. Diefendorff, “Power4 Focuses on
Memory Bandwidth,” Microprocessor
Report, Oct. 6, 1999, pp. 11-17.
M. Tremblay, “MAJC(tm): An Architecture
for the New Millennium,” Proc. Hot Chips
11, Aug. 1999, pp. 275-288. Also reported in
B. Case, “Sun Makes MAJC With Mirrors,”
Microprocessor Report, Oct. 25, 1999, pp.
18-21.

Lance Hammond’s biography is not available.
Benedict A. Hubbert is a PhD candidate inelectrical engineering at Stanford University.
His research interests include parallel computer architecture and software. Hubbert
received a BS in electrical engineering fromthe University of Michigan and a MS in electrical engineering from Stanford University.
Michael Siu is a senior design engineer at
Advanced Micro Devices, where he partici-

84

IEEE MICRO

pated in the design of the K6, Athlon (K7),and most recently the Sledgehammer (K8)
processors. His responsibilities include architecture, logic design, and physical implementation. Siu received a BS degree in electricalengineering from the University of Florida
and an MS in electrical engineering from
Stanford University.
Manohar K. Prabhu is a doctoral candidate in
the Department of Electrical Engineering at
Stanford University. He is currently investigating methods of parallel program development for chip multiprocessors. Prabhu has an
SB degree in engineering sciences from Harvard University and an MS in electrical engineering from Stanford University. His researchhas been funded in part by the National Science Foundation and by the Alliance for Innovative Manufacturing at Stanford.
Michael Chen is a PhD candidate in electrical engineering at Stanford University. His
research interests are in high-performance andparallel computer architectures and optimizations for improving the performance ofmodern programming language features suchas garbage collection and dynamic compilation. Chen received a BS and an MS in electrical engineering and an MS in industrial
engineering from Stanford University.
Kunle Olukotun is an associate professor ofelectrical engineering at Stanford University,where he leads the Hydra project(http://www-hydra.stanford.edu). He is interested in the design, analysis, and verificationof computer systems using ideas from computer and computer-aided design. Olukotunreceived a BS from Calvin College and an MS
and PhD in computer engineering from the
University of Michigan. He is a member of
the IEEE and the ACM.

Direct questions concerning this article toKunle Oluktoun, Stanford University, Room
302, Gates Computer Science 3A, Stanford,
CA 94305-9030; kunle@ogun.stanford.edu.