CONSIDERATIONS IN THE
DESIGN OF HYDRA:A MULTIPROCESSOR-ON-A-CHIP
MICROARCHITECTURE
Lance Hammond
Kunle Olukotun

Technical Report No.: CSL-TR-98-749

February 1998

This work was supported by DARPA contract DABT63-95-C-0089.

Considerations in the Design of Hydra:
A Multiprocessor-on-a-Chip Microarchitecture
Lance Hammond and Kunle Olukotun
CSL-TR-98-749
February 1998
Computer Systems Laboratory
Departments of Electrical Engineering and Computer Science
Stanford University
Gates Computer Science Building, #408
Stanford, CA 94305-9040
pubs@shasta.stanford.edu

Abstract
As more transistors are integrated onto larger dies, single-chip multiprocessors integrated
with large amounts of cache memory will soon become a feasible alternative to the large,monolithic uniprocessors that dominate today’s microprocessor marketplace. Hydra offers
a promising way to build a small-scale MP-on-a-chip using a fairly simple design that still
maintains excellent performance on a wide variety of applications. This report examines
key parts of the Hydra design — the memory hierarchy, the on-chip buses, and the control
and arbitration mechanisms — and explains the rationale for some of the decisions made in
the course of finalizing the design of this memory system, with particular emphasis given to
applications that stress the memory system with numerous memory accesses. With thebalance between complexity and performance that we obtain, we feel Hydra offers a promising model for future MP-on-a-chip designs.

Keywords & Phrases: microprocessors, multiprocessors, MP-on-a-chip (CMP), cachememories, cache coherence, SimOS, SUIFi

Copyright © 1997, 1998.
Lance Hammond and Kunle Olukotun

Considerations in the Design of Hydra:
A Multiprocessor-on-a-Chip Microarchitecture
Lance Hammond and Kunle Olukotun
Computer Systems Laboratory
Stanford University
Stanford, CA 94305-4070
email: lance@leland.stanford.edu, kunle@ogun.stanford.edu, http://www-hydra.stanford.edu
ferent parts of memory are described in section 4. Control

1. Introduction

mechanisms, including the resource and address arbiters, aredescribed briefly in section 5. Finally, section 6 concludes.

The Hydra microarchitecture is a research vehicle currently
being designed at Stanford in an effort to evaluate the conceptof a multiprocessor on a chip as an alternative for future microprocessor development, when large numbers of transistors

2. Simulation Methodology and Results

and RAM may be integrated on a single chip. We have previously demonstrated the value of this approach, in a general-

Hydra is currently being evaluated using a sophisticated, cycleaccurate memory simulator written in C++ that is interfaced

ized processor [1]. This technical report provides a more detailed view of the system we are currently designing.

with the SimOS machine simulator [7]. SimOS allows us tosimulate four fully functional MIPS-II ISA CPUs and a suiteof I/O devices with enough realism to boot and execute the
IRIX 5.3 operating system under our tested applications. As a

Hydra is composed of four 2-way superscalar MIPS CPUs on
a single chip, each similar to a small R10000 processor [2]result, system calls and I/O in our benchmarks were simulated with exceptional realism. Hydra simulates the memory

with individual L1 instruction and data caches attached. A
single, unified L2 cache supports the individual L1 caches andsystem using a group of interconnected state machine controllers to evaluate the memory’s response to all memory ref-provides a path for rapid and simple communication between
the processors. These two levels of the memory hierarchy

erences, both instruction and data, supplied by SimOS. These
controllers communicate through shared models of the cen-and the bus interconnections between them are the focus of
the Hydra design effort described here. However, the design

tral arbitration mechanisms and the caches in order to accurately model the time required to complete all accesses.

would be incomplete without a state-of-the-art off-chip
memory system. On one side of the chip, a 128-bit L3 cache
bus attaches to an array of high-speed cache SRAMs, whileon the other side Rambus channels directly connect main

This paper focuses on describing the Hydra hardware qualitatively, but some key numbers from two applications that wememory to Hydra and a more conventional bus connects Hydra to I/O devices. Fig. 1 shows a diagram of the architecture,evaluated are used throughout the text to illustrate the rationale for key design features of Hydra. The numbers of inter-

while fig. 2 depicts a possible layout for the completed design.

est are plotted in figs. 3–6. Representative samples from thecore loops of the swim and tomcatv SPEC95FP benchmarks,
parallelized automatically using the SUIF compiler system [8],were executed on the simulator to get these results. While weThis paper gives a brief overview of the microarchitecture andattempts to describe some of the trade-offs that have been

have examined several other applications from the SPEC suite,
these two have exhibited the most interesting memory systemevaluated in the course of revising the design. Section 2 givesa brief overview of the simulation environment we are using

behavior because they stress the memory system with large
numbers of accesses. In contrast, the Hydra memory system’s

to evaluate Hydra, and presents a few of our most interesting
results obtained through simulation. Section 3 presents a de-cache hierarchy easily handles the small data sets of the otherSPEC benchmarks. In the future, we may examine other ap-

scriptive overview of Hydra’s memory hierarchy, along witha qualitative view of how the different levels interact. The

plications with large data sets, such as databases.

communication buses used to transmit data between the dif1

Centralized Bus Arbitration Mechanisms

CPU 0

L1 Inst.
Cache

CPU 1

L1 DataCache

L1 Inst.
Cache

CPU 0 Memory Controller
Cache
refills

CPU 2

L1 DataCache

L1 Inst.
Cache

CPU 1 Memory Controller
Writes out,
invalidates in

Cache
refills

CPU 3

L1 DataCache

L1 Inst.
Cache

CPU 2 Memory Controller
Writes out,
invalidates in

Cache
refills

L1 DataCache

CPU 3 Memory Controller
Writes out,
invalidates in

Cache
refills

Writes out,
invalidates inWrite-through Bus (64b)
Read/Replace Bus (256b)
Direct I/O

On-chip L2 Cache

Off-chip L3 Interface

Rambus Memory
Interface

Cache SRAM
Array

DRAM Main
MemoryDMA

I/O Bus Interface

The Edge of the Chip

I/O Devices

Figure 1: A schematic overview of Hydra

CPU
#0

CPU
#1

PMMU #0

PMMU #1

#0
#0
#1
#1
I-Cache D-Cache I-Cache D-Cache
CPU0 Memory Address CPU1 Memory
JammerControl
Control

Memory Bus Wiring Channel
CPU2 Memory Central CPU3 Memory
Control
Control
Arbiter

Main Memory RamBus Interface

FPU #1I/O System Bus

FPU #0

RamBus Interface Controller Clocking &Test

L2 CacheData

L2 / L3 Cache
Controller

L3 Tag and Address Port

L2
Tags

Clock & Test Ports

System Bus
Control Unit

L3 Data Port “A”

#2
#2
#3
#3
I-Cache D-Cache I-Cache D-Cache

L2
Tags

L2 Cache
Data

PMMU #2

PMMU #3

CPU
#2

CPU
#3

FPU #2

FPU #3L3 Data Port “B”

Figure 2: A possible layout of Hydra
2

16

100
90

tomcatv

70
60
50
40
30
20
10
0

14

swim

12

tomcatv

10
8
6
4
2

L2 Ports

L3 Associativity# of buses

L2 Ports

Dual Bus

Single Bus

2-Way SA L3

1-Way SA L3

1-Port L2

2-Bus (W)2-Bus (R)Single Bus

2-Way SA L3

1-Way SA L3

2-Port (W)2-Port (R)1-Port02-Port L2% of time Occupied

80% slowdown from “perfect” caseswim

L3 Associativity# of buses

Figure 3: Resource occupancies in Hydra for several simu-

Figure 4: The % increase in execution time seen as a result oflated situations. (see section 3 for the L2/L3 cache discussion and section 4 for discussion of the buses)

several architectural decisions, over “perfect” scenarios.
(see section 3 for the L2/L3 cache discussion and section 4

All Pipelined

30

Pipelined L2 & L3

Roughly Pipelined

tomcatv
40

0.5% slowdown from “All Pipelined” case% slowdown from “perfect” case

swim

50

Pipelined L2 Onlyfor discussion of the buses)

60

20
10

Pipelined / new arbiter

Pipelined / old arbiter

Unpipelined / old arbiter

Address Jamming Only

0

0
-0.5
-1
-1.5

swim
tomcatv-2-2.5

Figure 5: The % increase in execution time, over “perfect”
scenarios with no arbitration at all between fully pipelined

Figure 6: The % increase in execution time seen as a result ofvariations in the degree of pipelining used in the read andstate machines, seen as a result of variations in the arbitration mechanisms and pipelining of the read and write con-write control state machines. (see section 5 for discussion)

trol state machines. (see section 5 for discussion)3

L1 Cache

L2 CacheL3 Cache

Separate I & D
SRAM cache pairs
for each CPU

Shared, on-chip
SRAM cache

Shared, off-chip
SRAM cache

Off-chip DRAM

Capacity

16KB each

512KB

8 MB

128 MBBus Width64-bit connection toCPU128-bit synchronous
256-bit read bus + 64SRAM (running at
bit write bus*
half the CPU speed)

Access Time

1 CPU cycle

5 CPU cycles

10 cycles to first word at least 50 cycles

Associativity

4-way

4-way

2-way*

N/A

Line Size

32 bytes

32 bytes

64 bytes

4 KB pages

Writethrough, no
allocate on write

Writeback, allocate on
WritebackwritesN/A

Inclusion not enforced Includes all data in L1 Includes all cachedby L2 on L1 caches
and/or L2 caches
data

Configuration

Write Policy
Inclusion

Main Memory

32-bit Rambus(running at the full
CPU speed)“writeback” (virtual
memory paging)

Table 1: A summary of the cache hierarchy. The two entries marked with asterisks, L2 cache bus width and L3 cache associativity, were varied during the experiments documented in figures 2 and 3. A third experiment, comparing a single L2 port
against a pair of separate read and write ports, is also documented in the graphs but is not reflected in this table, since all otherlevels of memory are strictly single-ported.
fairly sophisticated arbitration logic between the L1 cache andthe processors. Such hardware would tend to have an impact

3. The Memory Hierarchy
The Hydra memory system uses a four-level arrangement, sum-on the processor’s clock speed and/or increase the number ofcycles required for each L1 cache access, which would nega-marized in Table 1. Each level is explored further below.

3.1. The L1 Caches
The individual L1 instruction and data caches associated withtively impact the load-use penalty seen by executing code andcause more pipeline stalls. The combination of these threeeach processor are designed to supply data to each processor
in a single cycle while supporting the very high memory band-

effects makes the design of a shared-L1 cache a problematic
solution, as shown in [4].

width needed to sustain processor performance. Since 30–
40% of instructions in a typical MIPS-II ISA instruction stream

In contrast, Hydra’s independent L1 caches allow each processor to have its own small and fast L1 cache that processes

are loads and stores, dynamically [3], a reasonably efficient
2-way superscalar implementation will have to deal with abouta single access every cycle. Such caches can be easily optimized to return data within a single cycle. Our measurements

two data memory accesses from each processor every threecycles, in addition to a constant stream of instruction fetches.

have shown that in typical applications significantly more than
90% of loads hit in these L1 caches and do not need to progress

Multiplied by four processors, the first level data caches considered together must be able to support a throughput of ap-

further down the memory hierarchy. The only concession thatmust be made to allow multiprocessing is that each data cacheproximately three accesses per cycle, on average.
A single, shared cache would have to be extensively

must snoop the write bus and invalidate any lines to which
other processors write, in order to maintain cache coherence.

multiported and/or multibanked in order to sustain this bandwidth. Additionally, such a shared cache would have to beThis can be easily performed using a duplicate set of L1 tags
dedicated to handling snoops on the write bus, and then only

larger than the four separate data caches we propose, since itwould have to hold the active working sets of all four proces-interrupting the rest of the L1 cache when an invalidation is
actually necessary.

sors. Third, a shared cache would require a crossbar and/or
4

Fig. 3 shows the occupancies of the cache ports when the L2
cache is single-ported or dual-ported, with dedicated read and3.2. The L2 Cache
The large, on-chip L2 cache serves several functions. First, it
acts as a larger on-chip cache to back up the small L1 caches

write ports. The occupancies from the 2-port case clearly showthat most of the bandwidth in the L2 cache is used to absorb

with a nearby memory an order of magnitude larger, but fiveor more cycles slower. In practice, the L2’s access latency iswrites from the L1, while only a small percentage of the cycles
are used to handle read accesses (L1 cache refills). Compar-

so short that it has little effect on the overall execution time.
With most applications, the L1 caches have already exploiteding caches of equal capacity, fig. 4 shows that the performanceloss incurred by using a single-ported L2 cache is at most aboutmuch of the locality present in memory accesses, so unlessthe application’s entire data set fits into the L2 the local cache

4% over an infinitely-ported cache — or 2% over a dual-ported
cache — largely due to the fact that the small number of read

hit rate in the L2 tends to be poor — usually well under 50%,and sometimes under 20%. More importantly, the L2 cache

accesses does not disturb the stream of writes into the L2 much.
In reality, a single-ported design could have a larger capacity

serves as a sort of write buffer between the processors and theoutside world. Since the L1 caches are write-through, the writein a given area, since it could be made using simpler, morecompact SRAM cells. Due to the negligible performance loss,

bandwidth generated by the four processors would easily overwhelm off-chip buses. Using numbers from [3], a typical pro-

we have chosen a single-ported implementation for Hydra.

gram can be expected to write about once every ten instructions, or about once every five cycles from a 2-way processor

3.3. The L3 Cache
The off-chip L3 cache offers a cache with another order of

executing at its peak rate. With four processors executing at
peak throughput, about 80% of cycles will produce a write

magnitude larger capacity than the L2, but which can only beaccessed through a relatively narrow, 128-bit port that oper-from one of the processors, on average. Our simulations
showed that after CPU stalls were considered, there were writes

ates at half of the processor speed. As a result, it provides
good hit rates with a reasonably short access time of about 15

in 40-60% of cycles, typically, supporting these estimates. The
L2 cache captures all writes and collects them into dirty cache

cycles to the first word, minimum (including L1 and L2 misstime), but with bandwidth restrictions that are severe com-lines before passing them down to the lower levels of memory
via its writeback data handling protocol. By doing this, it

pared to the on-chip caches.
The design of this level of the memory hierarchy was fairly

reduces the off-chip bandwidth caused by writes to a manageable level. The L2 also acts as a communication medium

straightforward, but we did examine the consequences of having the L3 cache be both direct-mapped and 2-way set asso-

through which the four processors can communicate using
shared-memory mechanisms. Since it always contains the mostciative. Since we do not have on-chip cache tags, the 2-way
version of the cache speculatively starts fetching from both

up-to-date state for any line, it can supply shared data immediately to any processors that need it.

cache lines contained in a set until the correct way is known.
The former consumes less bandwidth, since erroneous data

The communication mechanism through the L2 allows the L1
caches to be simplified — they only have to support the exter-from the “wrong” way of the set will not be speculatively
fetched, as shown in fig. 3, while the latter offers higher hit

nal invalidations mentioned in the previous section, instead offull MESI protocols and L1 cache-to-L1 cache data transfers,

rates. The 2-way L3 exhibits extremely high occupancies on
the L3 interface, but its increased hit rate and flexibility in thesince they cannot hold private data. With this simple protocol, inter-processor communication speed is still quick — justface of cache conflicts make it better choice, in general. Fig.
4 shows that the two applications slowed down about 4% in

the round trip time to write to the L2 and then read back into a
different processor’s L1 cache — about 10 cycles, minimum.

both cases due to contention at the interface with the 2-way
associative cache. However, swim incurred a significant pen-

Another advantage that this design offers on a low level isthat the L1 and L2 caches may be individually tailored to theiralty from a cache conflict that could not be averted in the direct mapped cache but was easily avoided in the set-associa-

distinct purposes — the L1 caches to handling high-speed,
high-bandwidth accesses in a single clock cycle, and the L2 totive one. Since the latency of main memory is an order ofmagnitude longer than the L3 latency, a small number of thesehigh capacity, filling up all die area not required by the processors with as much cache memory as possible.

conflicts can cause a significant slowdown.
5Another interesting variation is a design with no off-chip
SRAM L3 cache at all. This arrangement is beneficial for3.4. Main Memory
Even with a large L3 cache, some applications have large
enough working sets to miss in all of the caches frequently,

several reasons. First, high-speed cache SRAM chips are expensive, so eliminating them would reduce the system costseverely taxing the main memory subsystem. In order to keep
up with the processors on swim and tomcatv, we have founddramatically. Second, approximately half of the I/Os on Hydra are devoted to the L3 cache interface. Without this cache,that the memory system would have to be able to deliver a 32bit word to the chip on every processor cycle, on average —a much cheaper package and simpler motherboard could be
used to hold each Hydra part. Third, design of the Hydra andhalf the bandwidth of the L3 cache. With processor speeds oftomorrow, this will take multiple Rambus-style memory in-

the system would be simpler and therefore cheaper without
the L3, since the design of the L3 interface, from both electri-

terfaces directly attached to the processor to supply the necessary bandwidth while keeping the number of pins connecting
Hydra to the DRAM reasonable.

cal and control perspectives, is a nontrivial task. Finally, as
time passes it is becoming possible to integrate larger amounts

3.5. Other Alternativesof cache memory on the processor die. Thus, the on-chip
SRAM L2 may eventually become large enough to have a good

While the current Hydra design addresses a fairly high-end

local hit rate on read accesses, and therefore perform the jobof the L3 cache in the current design. Another possibility isand expensive CPU design, with many high-speed SRAM and
DRAM chips directly attached to the Hydra chip, alternative
designs are possible in systems with different constraints.

that the SRAM L2 cache could be replaced with on-chip
DRAM, a larger but slower on-chip memory technology, inA small variation could be made by pulling the L3 cache tags

order to fully replace the L3 cache with an on-chip alternativeof similar size and speed. Larger on-chip SRAM caches andon-chip, like those in the PowerPC 750 [9]. In the current
design, the L2 cache acts primarily as a buffer for writes andon-chip DRAM are explored in [6].

interprocessor communication, due to the L2’s low local hit
rate on read accesses. As a result, most data not found in the

4. Communication BusesThe read/replace (or “read”) and write-through (or “write”)
buses, depicted in fig. 1, are the principal paths of communi-

L1 has to be recovered from the L3 cache. Trading some L2
cache for L3 tags, in order to improve the performance of thecation across the Hydra chip. Both buses are controlled in apipelined manner, with bus arbitration occurring at least a cycle

L3 cache, might therefore be a reasonable trade-off. The L2
hit rate will decrease, but that should not affect overall perfor-

before bus use, to keep throughput at one access per cycle
each bus. Such throughput is necessary to avoid bus satura-

mance much. This would help improve L3 performance in
two ways. First, the L3 cache could be made highly associa-

tion in the current implementation of Hydra on applications
such as tomcatv and swim.

tive. While it is not practical to check more than one or two
off-chip tags at once, many on-chip tags can be checked inparallel. The increased associativity would tend to reduce L3
miss rates and thereby increase performance. Second, the L3

4.1. The Read Bus
The read/replace bus is the largest and most important data
highway across the Hydra chip. It is 256 bits wide, matchingtags could be checked in parallel with each L2 access. Accesses that miss in the L3 entirely could be routed directly to

the L1 and L2 cache line size, in order to allow entire lines tobe transmitted across the chip at once. It is used to movemain memory, not wasting any of the L3 cache port’s limited
bandwidth on useless accesses. Also, even a highly associa-

cache lines around among the on-chip caches and the off-chip
interfaces, since all connect to it. While only one interface

tive L3 would only exhibit bandwidth requirements similar to
the tested direct-mapped version. Instead of wasting band-

may broadcast data at a time, many may listen to data broadcast across the read bus — for example, data brought in fromwidth speculatively reading multiple lines from a set of associative cache lines, the on-chip tags would simply select the

memory can be accepted by the L1 cache, L2 cache, and L3
cache interface on the same cycle, from a single broadcast.

correct line before the off-chip access was started. The reduced contention at the L3 cache port would both improve

Since it is not a crossbar, the read bus must be arbitrated for
before each data broadcast, as described in section 5. How-

performance, as our tomcatv results in fig. 4 show, and savepower by reducing the number of accesses to off-chip memory.

ever, while it performs many tasks, we have found that the bus
6

is typically occupied less than 50% of the time, as shown infig. 3, even with our most memory-intensive applications.

ever. First, it would be possible to have multiple write buses
on a single Hydra chip. As long as they did not carry data

Contention for this particular resource is thus not a problem.
As fig. 4 indicates, contention for both the read bus and thebeing written to the same address at once, the multiple write
buses would appear just like a single, faster write bus to thewrite bus slows performance by only a few percent over aperfect crossbar, even in the worst cases.

CPUs. This scheme would require that extra ports be supplied to the L1 tags, to allow multiple snoops and invalida-

4.2. Write Bus

tions per cycle, and to the L2 cache, to allow multiple datawords to be written every cycle. This latter modification would

While the read bus is a general-purpose data bus, the write
bus has one specific job — it takes write-through traffic fromprobably significantly enlarge the L2 cache, and thus could
make this solution impractical. A second scheme would be to

the CPUs and sends them into the L2 cache. Since it only
carries data from one store at a time, it only needs to be 64 bits

have a single, line-wide write bus. Since many bursts of writes
will fall within a cache line or two, merging writes that fall on

wide, at most — the width of the widest MIPS-II store instruction. This dedicated bus is necessary because our L1

single cache lines together in the CPU write buffers would
allow greater store throughput on these critical sections of code.

caches are writethrough and all stores from the CPUs must be
broadcast due to our simple coherence scheme. Since the L1

Third, the write bus could be discarded altogether and a moreconventional MESI coherence protocol between the L1 caches

caches do not filter this bandwidth, bus traffic can be quite
high — sometimes exceeding 60% full, as is shown in fig. 3,

could be adopted. This would eliminate the write bus altogether, and would make the system look like a conventional

even though each access only reserves the bus for a single
cycle — and the bus can be saturated at times of high write

shared-bus multiprocessor centered around the read bus. As
such systems have already been examined [5], and have sig-

traffic. Reasonably deep write buffers are needed between
the processors and the write bus to collect and feed stores onto

nificant control overhead, we chose to look at a more simple
and novel architecture. Finally, in the long-term future, mul-

the bus one by one while not stalling the processors as they
execute bursts of store instructions. Merging this bus with thetiple Hydra-like architectures could be connected hierarchically on a single chip, to achieve scalability while still includ-

read bus would typically result in a completely saturated bus
and significantly reduced performance, as figs. 3 and 4 indi-

ing high-performance clusters of processors. Such an architecture is beyond the scope of this technical report.

cate.

5. Control Mechanisms

As well as giving writes a clear path to the L2 cache, the write

The buses and caches in Hydra are controlled by a group ofbus also serves as a crucial mechanism for synchronizing theprocessors. Writes are serialized as they pass through the write

memory control pipelines, each devoted to a particular CPU
or interface. To prevent the pipelines from attempting to use

bus, so multiple writes to the same address will update thepermanent state of the machine in a consistent order. Since

resources or addresses simultaneously, access to these two limiting factors is controlled through the resource and address

all state changes are broadcast in this one location, L1 cachecoherence may be maintained by having the L1 caches snoop

arbiters.

on just this bus, and then invalidate their own contents when
they contain a line to which new data is being written. Since

5.1. Memory Control Pipelines
Eight of the ten different “memory control pipelines” are con-the write bus carries written data along with addresses thatneed to be invalidated, it is fairly easy to use an update cachetained in the CPUs. Each of the CPU memory controllers in
fig. 1 contains two independent pipelines, one for handling

protocol instead, should that be desired. We chose not to use
an update protocol since this generally results in many uselessread accesses — both from instruction fetches and loads —and one for handling writes from stores. These pipelines areinterventions into other processors’ L1 caches.
One critical issue that should be noted is that the write bus isused for any access that requires the use of any level of memory
below the L1 caches. While a processor will make approxi-

not scalable to larger numbers of processors, or to a four-way
MP made up of more complex, and therefore faster, proces-

mately two read accesses per cycle on typical code [3], mostread accesses are handled by one of the L1 caches. Thus, asors. This problem is easily addressed in several ways, how-single read pipeline is sufficient to process the occasional cache7

misses. On the other hand, due to the writethrough L1 cachepolicy, every write made by each processor must pass throughHowever, our old arbiter was often letting young accesses,
going to the L2 cache, pass up older accesses trying to use thethe write pipeline. On average, typically a store will happen
only about every 5 cycles [3], even with the processor run-L3 cache or main memory — a problem often called “priority
inversion.” As a result, we improved the resource arbiter (seening at peak efficiency. However, bursts of stores do appear
frequently in real code. Hydra only includes one write pipe-

the next subsection), and managed to dramatically improve
results. Since the “perfect” baseline represented in fig. 5 could

line, but this is usually sufficient because the bursts of stores
may simply be buffered without stalling the processor. We

be obtained only with full crossbars instead of buses and with
infinitely-ported caches, we feel that our results are quite good,

have found that the store buffer and write pipeline combination can be saturated by store-intensive code, but generally

given our realistic resource limits. In a later experiment, wereduced the degree of pipelining by eliminating the cycle-by-other system resources such as the write bus or the L2 cacheport are also approaching the saturation point at these times,

cycle pipelining in some or all of the three main pipeline access stages. This allowed only a single access to be handled

so the pipeline is not much of a bottleneck. Therefore, shortof making a much more complex and expensive system, thein each of these main stages at a time. The surprising results
are shown in fig. 6. The more coarse pipelines were actually

single pair of control pipelines on each CPU appear to form areasonable design.

slightly better than the full cycle-by-cycle ones, even though
they are much simpler and easier to build. The reason is simple— along with the improved arbiter, the coarser pipeline reduced the amount of priority inversion that occurred. Han-

The read and write pipelines in each CPU are very similar.
Each consists of three main stages: the L2 cache access (whichdling more than one access per main pipe stage, in contrast,
turned out to be unnecessary — the coarser stages were suffi-

is about 5 cycles long), the L3 cache access (about 15 cycles),and the initiation of a main memory access (about 5–10 cycles).

cient.

Each access goes through each stage in succession until therequired cache line is located in one of the levels of the memory

The remaining two pipelines are in the main memory and I/Ohierarchy. Resource arbitrations are made at the start of eachsection of the pipeline in order to ensure that the pipeline hasinterfaces. These controllers process data returning frommemory or I/O requests, sending it to the appropriate caches

reserved needed resources before initiating an access to a cache
or using a bus. The only real difference between the two pipe-on the Hydra chip as it arrives. They are much simpler cousins to the CPU controllers, since they basically just respond tolines is that the write pipeline writes its data into the L2 fromthe write bus at the end of every access, while the read pipe-

all data arriving from off-chip in a programmed manner. Like
the other pipelines, they were gradually pipelined from simple

line forces the desired cache line out onto the read bus.

state machines. However, the limited bandwidth of the main
memory and I/O buses also imposed a limit on the degree ofIn the process of tuning Hydra, these pipelines were adjusted

pipelining that was necessary. The main memory controller
only needed to be divided into two main pipeline sections —extensively to improve performance. Initially, the pipelines
were not actually pipelines — instead, they were just state

one for sending data to the L1/L2 and one for recording cachelines into the L3 cache. Currently, the I/O controller is still

machines, that could only process a single access at a time.
The performance of this system was surprisingly good. On

completely unpipelined, since that is enough to handle oursimulated I/O traffic.

applications other than swim and tomcatv, the limited numberof accesses that could be processed at once was never a problem. These simple controllers became a tremendous performance drag with the more memory-intensive applications,5.2. Resource Arbiter
The resource arbiter is responsible for allocating the chip’s
key resources — the buses, caches, and some buffers — for

however. We next evaluated the opposite alternative — controllers that could start processing a new access every cycle.

the next several cycles ahead. Many arbitration mechanisms
handle requests on a cycle-by-cycle or resource-by-resource

As shown in fig. 5, performance improved, but not as much as
we had hoped. In particular, we found that switching to suchbasis, but the Hydra arbiter processes entire “resource requests”
at once — requests for a group of resources required by aan extensively pipelined design undermined our arbitration
priority scheme. For best performance, a good heuristic is

pipeline over the course of the next 5-20 cycles. Each CPU

that the oldest accesses should get resources before newer ones.
8

pipeline sends the arbiter a resource request before each of
the three main pipe stages, and then stalls until the arbiter tells

ply because they were never able to acquire resources. The
second version of the arbiter solved this problem by handlingthe pipeline it may continue. The memory and I/O pipelines
work similarly, but are designed to make several small resource

each resource request only once, on the cycle it arrives at thearbiter. On that cycle, the arbiter scans ahead until it finds therequests as words of data are brought into Hydra from offchip. Since pipelines send out their resource requests at leastearliest time that the request can be handled. After finding
this time, the arbiter reserves the resources immediately anda cycle before any of the critical resources are actually needed
for processing, the resource arbiter causes no unnecessary

notifies the pipeline how many cycles it must wait. While thesimple L2 cache accesses are still usually delayed less thandelays when resources are free. Some of the resource requests,
especially those involving the L3 cache, may be for quite com-the more complex L3 accesses by this arbitration mechanism,
the arbiter can guarantee that the L3 accesses are able to getplicated combinations of buses and caches on different cycles.
The arbiter imposes a fixed priority on the requests, depend-

the minimum delays that their resource requirements allow.

5.3. Address Arbiter

ing upon the pipeline and the request type. All memory and I/
O pipeline requests always get first priority, followed by main

If multiple accesses to the same address are processed simultaneously by different pipeline controllers in Hydra, problems
may occur. The first problem is that multiple copies of a single

memory requests, L3 cache requests, and finally L2 cache requests. Among the CPU pipeline request types, the read pipe-

cache line may be generated within an associative set of lines.
If a pipeline controller misses in a cache, it will immediately

lines generally have priority over the write pipelines. However, each CPU may select to invert the priority of its read andattempt to recover the line from the next level of the cachehierarchy. Unfortunately, if another controller is already pro-write pipelines intentionally on a cycle-by-cycle basis, giving
its writes higher priority, in case its write buffer is nearly full.

cessing a miss to the same line, both will return with theirown copies. Along with wasting precious cache space on re-

We found this feature to be quite helpful with memory-intensive applications that must frequently recover cache lines fromdundant data, duplicate lines may cause functional errors if
writes are made to both copies, since eventually both copies

the L3 cache or main memory in order to handle theirwritethrough traffic, since even a few L2 cache misses onof the cache line will be written back to lower levels of memory— so the writes to the copy written back first will be errone-

writethroughs can allow a CPU fill up its write buffer. Priorities among the different CPUs are changed round-robin, so

ously overwritten. A similar problem can occur if one controller is writing back a dirty line to the next level of memory.

that no CPU may hog the arbiter. We tried more complex
inter-CPU priority schemes, also, but they did not affect per-While the line is being written back, it is no longer listed in
the tag directory of the cache that is discarding it. Hence,

formance significantly.
As shown in fig. 5 and discussed in the previous subsection,

another controller may miss in the cache and subsequently
fetch the old, stale version from the lower level of memory

the arbiter has gone through two main stages of development
in order to prevent accidental priority inversions. The first

while the more recent version is still in the process of being
written back. The cache will refill with the stale data, and theversion of the arbiter checked all pending resource requests
from all pipelines on every cycle. If a request failed, it was

written-back modifications to the line will be permanently lost.
Making these problems worse, each access may involve up to

tried again on the next cycle. If a request succeeded, its resource reservations for the next several cycles were recorded,

three different cache lines — the line requested, the L2 cache
writeback, and the L3 cache writeback.

and the requesting pipeline was allowed to continue. This
scheme had the unfortunate side effect of giving the simple

Hydra’s address arbiter solves these problems by simply forbidding multiple accesses to the same address in the L2/L3/

L2 cache accesses higher priority than the complex L3 accesses. Since these simpler requests demanded fewer re-main memory system until all previous accesses to that address have completed. In order to protect all three cache lines

sources, it was easier for them to find all of their resources
free on any given cycle. They would then reserve resourcesthat an access may use with only a single arbitration, the Hydra address arbiter actually checks only the address bits thatfor the next several cycles ahead, and frequently block pending L3 cache accesses further in the process. This resulted inare used for indexing into both the L2 and L3 — 8 bits in thesome references taking thousands of cycles to complete, sim9

current implementation. This works because a line and any
writebacks it may generate will always be in the same asso-

keep the on-chip caches coherent. Off-chip memory is controlled through two glueless ports to attached SRAM andciative set, so by protecting its sets in both the L2 and L3 we
automatically protect all three lines that might be active at

DRAM chips. Arbitration of key resources and addresses isaccomplished with two custom mechanisms that have been

once. The address arbiter “checks in” each access when it
initially tries to access the L2 cache tags — always the firsthighly tuned. With this balance between complexity and performance, we believe Hydra offers a promising model forstep of any access. Most accesses continue on without problems, but if an address collision is detected the L2 cache ac-

future MP-on-a-chip designs.

References

cess is aborted and the access is queued up behind all previous
accesses to that particular index. To keep the mechanism[1]K. Olukotun, K. Chang, L. Hammond, B. Nayfeh, and K.
Wilson, “The Case for a Single Chip Multiprocessor,” Pro-

simple, no prioritizing is performed among the queued accesses. When all previous accesses to that index have com-ceedings of the 7th Int. Conf. for Architectural Support for
Programming Languages and Operating Systems

pleted, the access is freed and it retries the aborted L2 cache
access.

(ASPLOS-VII), pp. 2–11, Cambridge, MA 1996.
[2]K. Yeager, “The MIPS R10000 superscalar microproces-

While this mechanism might appear to be rather heavy-handed
and excessive, in reality it has a negligible impact on perfor-

sor,” IEEE Micro, vol. 16, No. 2, pp. 28–40, April 1996.
[3]D. Patterson and J. Hennessy, Computer Architecture: A

mance, as fig. 5 demonstrates. There are three basic reasons
why it is not a problem. First, the mechanism is not invoked

Quantitative Approach, 2nd Ed., Morgan Kaufmann Publishers, Inc., pp. 105–6, San Francisco 1996.

by reads that hit in the L1 cache, so the number of accesses“checking in” to the arbiter is reasonably small. Second, even[4]B. Nayfeh, L. Hammond, and K. Olukotun, “Evaluation of
Design Alternatives for a Multiprocessor Microprocessor,”

8-bit indices offer 256 different possible values. Since there
are typically nowhere near that many active references reserv-

Proceedings of the 23rd Int. Symposium on Computer Architecture, pp. 67–77, Philadelphia, PA 1996.

ing addresses at once in Hydra, odds of a random collision arereasonably small. Finally, the mechanism allows accesses to[5]M. Takahashi, H. Takano, E. Kaneko, and S. Suzuki, “A
Shared Bus Control Mechanism and a Cache Coherence

the same address to work together more efficiently. Whenmultiple processors attempt to read the same cache line fromProtocol for a High-performance On-chip Multiprocessor,”
Proceedings of the 2nd Conference on High Performancethe L2 cache and miss, the address arbiter will allow only the
first pipeline controller to actually see and process the miss.

Computer Architecture (HPCA-2), pp. 314–322, San Jose,CA 1996.

The others are stalled by the address arbiter, and not using any
resources in the meantime, until after the first controller reads[6]T. Yamauchi, L. Hammond, and K. Olukotun, “A SingleChip Multiprocessor Integrated with DRAM,” Stanford

the line into the L2 cache. Any trailing processors then just
hit in the L2 cache, effectively riding on the coattails of the

University Technical Report No. CSL-TR-97-731, August
1997.

first access.

[7]M. Rosenblum, S. Herrod, E. Witchel, and A. Gupta., “The
SimOS approach,” IEEE Parallel and Distributed Tech-

6. Conclusions

nology, vol.4, no. 3, 1995.
[8]R. Wilson, R. French, C. Wilson, S. Amarasinghe, J. Ander-

As more transistors are integrated onto larger dies, single-chip
multiprocessors integrated with large amounts of cacheson, S. Tjiang, S.-W. Liao, C.-W. Tseng, M. Hall, M. Lam,and J. Hennessy, “The SUIF Compiler System: A

memory will soon become a feasible alternative to the large,monolithic uniprocessors that dominate today’s microproces-

Parallelizing and Optimizing Research Compiler,” Stanford
University Technical Report No. CSL-TR-94-620, May

sor marketplace. Hydra offers a promising way to build asmall-scale MP-on-a-chip with a fairly simple design while

1994.
[9]L. Gwennap, “Arthur Revitalizes PowerPC Line,” Micro-

maintaining excellent performance on a wide variety of applications. Simple buses are used to connect several optimized,

processor Report, pp. 10–13, February 17, 1997.

single-ported caches together. With the write bus based architecture, no sophisticated coherence protocols are necessary to10