Vol. 45

No. 7

IPSJ Journal

July 2004

Regular Paper

Cache Coherence Strategies for Speculative Multithreading CMPs :Characterization and Performance Study
Niko Demus Barli,† Luong Dinh Hung, † Hideyuki Miura,†
Chitaka Iwama, † Daisuke Tashiro, † Shuichi Sakai †and Hidehiko Tanaka†
Thread-level memory speculation is one of speculation techniques usually employed in speculative multithreading architectures. On shared-bus chip multiprocessors (CMPs), the technique can be implemented by extending their cache coherence mechanisms. Several implementations have been proposed and evaluated. However, there is no study that compares
the impact of the taken strategies and identiﬁes which of the strategies are important. In
this paper, we ﬁrst characterize the eﬀect of speculative multithreading executions to cache
misses. We ﬁnd that sharing misses occupy the largest portion of misses, and spreading accesses in speculative multithreading executions cause a signiﬁcant increase in the miss rate.
Then, we perform a performance study of several cache coherence strategies. Our study showsthat update-based protocols, which do not suﬀer from sharing misses, achieve signiﬁcantly
higher performance than invalidation-based protocols. The study also reveals that applying a
modiﬁed read-broadcast (snarﬁng) approach is eﬀective for suppressing the eﬀect of spreading
cache accesses. Finally, the study shows that managing the exclusivity of data in caches oﬀers
little performance improvement.

Several implementations have been proposedand evaluated12)∼14),20) . However, to our extent of knowledge, there is no study that compares the impact of the taken strategies andidentiﬁes which of the strategies are important.
In this paper, we ﬁrst characterize the effect of speculative multithreading executions tocache misses. We ﬁnd that sharing misses occupy the largest portion of misses, and spreading cache accesses in speculative multithreading executions causes a signiﬁcant increase in
the miss rate. These results suggest that eliminating the sharing misses and suppressing theeﬀect of spreading accesses are important factors for achieving good performance.
We then perform a performance study ofseveral cache coherence strategies. Our study
shows that update-based protocols, which do
not suﬀer from sharing misses, achieve significantly higher performance than invalidationbased protocols. Update-based protocols also
have lower bus utilization. These results are interesting since they contradict previous resultsin the context of conventional multithreading
executions on multiprocessors. In this context,
update-based protocols often suﬀer from a large
increase in bus utilization, outweighing the beneﬁt of lower cache miss rate7),9),10) .
The study also reveals that applying a modiﬁed read-broadcast (snarﬁng) approach is eﬀec-

1. Introduction
Speculative multithreading has been proposed to accelerate the execution of sequential programs by dividing a sequential execution stream into threads and executing thethreads speculatively1),4),8),14)∼16),19),21),23) . In
contrast to conventional parallelization approaches, control and data dependencies may
exist among the threads. To guarantee the correctness of the execution, a number of hardware
and software supports are typically integrated
to the underlying architectures.
Thread-level memory speculation is one of
speculation techniques usually employed in
speculative multithreading architectures. A
speculative thread may issue memory operations without waiting for memory operations of
its predecessor threads to complete. This implies that we need to buﬀer values stored by the
speculative threads, perform version management of memory values, and detect dependency
violations. These functions can be implemented
on shared-bus chip multiprocessors (CMPs) byextending their cache coherence mechanisms.
† Graduate School of Information Science and Technology, The University of Tokyo☆
Presently with Texas Instruments Japan☆☆
Presently with East Japan Railway Company☆☆☆
Presently with Institute of Information Security
1

2

IPSJ Journal

tive for reducing the eﬀect of spreading cache
accesses. Originally, read-broadcast approachis intended to reduce sharing misses in multiprocessor caches11),17) . The bus is snooped
for read-miss transactions, and whenever a response appears on the bus and there is a matching tag of an invalid line, the line is inserted in
the cache. The original approach is however
not suﬃcient since the spreading cache accesses
also cause a signiﬁcant increase in non-sharing
misses. The modiﬁed read-broadcast approach
extends the original approach by inserting thesnooped line not only when an invalid copy ofthe line found, but also when there is no matching copy of the line in the cache.
Finally, our study also shows that managing the exclusivity of data in caches oﬀers little
performance improvement. This suggests that
exclusivity management can be traded oﬀ if a
simpler design in the cache coherence protocol
is preferred.
The rest of this paper is organized as follows.
Section 2 presents the related work of cache coherence protocols that support speculative multithreading executions. Section 3 describes themethodology of this study. The results of thestudy are presented and discussed in Section 4.
Finally Section 5 concludes the paper.
2. Related work
Several cache coherence protocols for speculative multithreading CMPs have been proposed12)∼14),20) and an analysis of the complexity involved has been reported24) . Speculative
versioning cache (SVC)12) proposed for Multiscalar architecture, uses an invalidation-based
protocol. The state of data is managed ona per-word basis and a linked-list structure isused for version management. SVC employs aslightly modiﬁed read-broadcasted approach inwhich the line is snarfed if there is a free line
available.
Hydra13) also uses an invalidation-based protocol. The state of data is managed on a
per-line basis. Write-through policy is employed: non-speculative writes are written directly through to the L2 cache, while speculative writes are temporarily stored into dedicated speculative buﬀers attached to the bus.
STAMPede20) extends the MESI invalidationbased protocol to support memory speculation.
Similar to Hydra, the state of data is managed
on a per-line basis. However, it retains speculative values in the cache.

July 2004

In IACOMA14) , memory speculation is supported using a centralized table called Memory
Disambiguation Table (MDT). MDT is locatedbetween the private L1 caches and the shared
L2 cache. It records loads and stores executedon L1 caches. The state of data is managed ona per-word basis. Similar to STAMPede, speculative values are retained in the L1 caches.
SVC, Hydra, STAMPede, and IACOMA, alluse invalidation-based protocols. Our study
however reveals that update-based protocols
considerably reduce the number of cache misses
and oﬀer a signiﬁcant performance improvement over invalidation-based protocols. The
study also shows that, applying the modiﬁed read-broadcast approach to the updatebased protocols further improves the performance achieved.
3. Methodology
3.1 Execution model
In this paper, we deﬁne thread as a connected
subgraph of the control ﬂow graph with a single
entry node. This deﬁnition is similar to theone used in Multiscalar19) . It diﬀers in that weallow overlap among the tail regions of diﬀerent
threads2) .
A program is partitioned into threads by acompiler. We incorporated a partitioning algorithm into an improved version of newcc optimizing compiler 3) originally developed by Fujitsu Laboratories. The compiler ﬁrst ﬁnds
thread candidates by analyzing the program’scontrol ﬂow graph using structural analysis18).
In our algorithm, structural analysis is conﬁgured to identify structures that meet therequirements of our thread model describedabove. These structures include if-then blocks,
if-then-else blocks, and loop structures.
After ﬁnding the thread candidates, the compiler applies a heuristic approach for selecting a
combination of threads that is most likely give
optimal performance. Here, we use a simple
heuristic that mainly considers loop structures
and thread size characteristic. We ﬁrst identify innermost loop structures from the candidates. Then, we select a combination that includes the loop structures and minimizes thetotal number of threads. Furthermore, only
for candidates whose estimated size exceed apreset threshold value, we then insert a thread
header into each control ﬂow edge that enters
the candidates. Note that this thread header
indicates the start of a thread and by insertingVol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs

Table 1 Average dynamic size of threads and thecoverage of parallel execution
Application
099.go124.m88ksim
126.gcc
129.compress
130.li
132.ijpeg
134.perl
147.vortex
harmonic mean

thread size [insts]
25.98
24.30
26.92
20.66
22.18
51.61
29.05
31.09
27.99

coverage [%]
99.69
89.99
90.12
99.89
99.82
94.71
66.23
80.68
88.57

the headers into the edges rather than to the entry blocks of the thread candidates allows us tooverlap the tail regions of two or more threads.
Overlapping tail regions is useful to avoid thecreation of tiny threads that was a problem forsustaining a large execution window2) . Table 1
shows the average dynamic size of threads andthe coverage of parallel execution in our evaluation environment.
During execution, a thread predictor5) dynamically predicts the sequence of threads that
follow the program order. The threads are thenassigned to the processing units of the CMP in around-robin fashion. If a misprediction occurs,
the mispredicted thread and all its successors
are ﬂushed and the execution is restarted.
Inter-thread register dependencies are handled using a synchronization mechanism6) . The
compiler helps the hardware to identify which
registers to synchronize and the timing to safely
send the values. In contrast, inter-thread memory dependencies are handled in a speculative way. A thread may issue memory operations without waiting until its predecessors
complete all memory operations. If a predecessor thread afterwards stores to a location previously loaded by the thread, a dependency violation is detected, and the violating thread andall its successors are ﬂushed and restarted.
3.2 Simulation setup
Eight applications from SPEC95INT benchmark are used for the simulations. The parameters, shown in Table 2, are set so that one
execution will ﬁnish in 100 to 300 million instructions.
We use two types of simulator in this paper. The ﬁrst simulator is a trace-based cachesimulator used for characterizing the impact ofpartitioning a sequential program into threads
to cache miss rate. We ﬁrst generate traces
that record memory accesses performed by thethreads. The threads are assumed to be per-3

Table 2 SPEC95INT benchmark parameters
Application
Parameter099.go99
124.m88ksim
train/ctl.in
126.gcc-quiet -funroll-loops -ﬀorce-mem-fcse-follow-jumps -fcse-skip-blocks-fexpensive-optimizations-fstrength-reduce -fpeephole-fschedule-insns -ﬁnline-functions-fschedule-insns2 -Ogenrecog.i genrecog.s
129.compress 30000 1 2131
130.litrain.lsp
132.ijpeg-image ﬁle specmun.ppm-compression.quality 50-compression.optimize coding 0-compression.smoothing factor 50-diﬀerence.image 1-diﬀerence.x stride 10-diﬀerence.y stride 10-verbose 1 -GO.ﬁndoptcomp
134.perlscrabble.pl scrabble.in
147.vortex
train/vortex.infectly predicted and scheduled to the processing
unit in a round-robin fashion. The sequence ofthe threads follows the program order as deﬁned in our execution model. The memory
trace in each thread also follows the program
order. Given these traces, the simulator thensimulates the behavior of the caches and classiﬁes the occurring cache misses. The timingof cache update is ideal. When a miss occurs,
the corresponding line is assumed to be brought
to the cache immediately before another accessmay occur.
In this simulator, since our purpose is tocharacterize the sharing misses and the eﬀectof spreading accesses introduced by speculative
multithreading executions, we simulate neither
the parallel execution of the threads nor thesuperscalar execution. All memory accesses bypredecessor threads must have been issued before a new thread is scheduled to a processing
unit. It is because at this evaluation stage,
we want to isolate the inherent characteristics
from the side eﬀects of the speculative executions (i.e. memory accesses by misspeculated
threads or by instructions that follow a mispredicted branch).
For example, assume that a thread stores toa location whose copy also exists in the cacheof a processing unit running one of its successors. Also assume that the successor threadloads the value from the location. This example
illustrates a producer-consumer sharing patternthat inherently causes a sharing miss in the con-

4

IPSJ Journal

Thread Predictor
PU 0

PU 1

PU 2

PU 3

register communication network
I$ D$

I$ D$

I$ D$

I$ D$

L2 cache

July 2004

Table 4 Types of protocols used in this study
Name
Description
inv
invalidation-based protocol
no read-broadcast
inv-robr
invalidation-based protocol
read-broadcast in read misses
upd
update-based protocol
no read-broadcast
upd-robr
update-based protocol
read-broadcast in read misses
upd-rwbr update-based protocol
read-broadcast in both read/write misses

Fig. 1 CMP organization used in this study
Table 3 Processing unit and cache parameters
Parameter
Pipeline stages
Fetch/Issue/Retire width
No. of physical registers
Functional units
Reorder buﬀer
Issue queue
Load/store queue
BTB
Bimodal predictor
L1 instruction cache

L1 data cache

L2 uniﬁed cacheValue
7 stages
4 instructions/cycle
128 registers
2 ALUs + 2 Addr. Units
64 entries
20 entries
20 entries
1024 entries
4096 entries
16-kB 64-B line
2-way set associative
1-cycle hit latency
16-kB 64-B line
2-way set associative
2-cycle hit latency
ideal (always hit)
16-cycle latency

sumer’s cache in invalidation-based protocols.
However, in real speculative multithreading execution, the consumer may speculatively load
the value resulting in a cache hit. It is thenfollowed by a store by the producer, causing amemory dependency violation and invalidationof the line. The consumer thread is restarted
and eventually loads from the location, now resulting in a cache miss. In this case, the ﬁrst
cache hit is irrelevant and better not to be included in the statistics taken.
The second simulator is an execution-driven
cycle-accurate simulator used for the performance study in this paper.
It simulates
the aspects of out-of-order superscalar andspeculative multithreading executions, including branch prediction, speculative spawning of
threads, and speculative accesses to the memory system. The simulator simulates a CMP
consisting of four processing units. Each processing unit is an out-of-order superscalar corewith a 7-stage pipeline. The processing unit
can fetch, issue, and retire four instructions per
cycle. Each processing unit has private L1 in-struction and data caches, and shares a uniﬁed
L2 cache. The hardware organization of the
CMP is shown in Fig. 1. The parameters of
the processing units and their caches are summarized in Table 3.
The simulator incorporates a dual-length
path-based predictor5) with lazy update policy
as the dynamic thread predictor. We combine
two path-based predictors with path length of
one and four respectively. Each predictor uses a
2048-entry prediction table. The selection tablehas 4096 entries of 3-bit counter. The predictor is able to predict one thread in each cycle.
For the SPEC95INT benchmark we use in thispaper, the prediction accuracy achieved ranges
from 62% (099.go) to 95% (124.m88ksim), withan average of 82%.
For register communication, we assume a register communication mechanism previously proposed in6) . The update and propagate latency
to an adjacent processing unit is set to one cycle, while the update and propagate bandwidthis set to one register/cycle.
For cache coherence protocol of the data
caches, the simulator incorporates ﬁve types ofprotocols to be described in the next section.
Memory dependency violations are detected ona per-word basis. A memory violation ﬂushes
the execution of the current thread and the execution is restarted after one cycle penalty.
Finally, the simulator simulates a sharedbus that connects the data caches. The bus
model and its parameters are described in section 3.4. For instruction caches, we do notmodel bus contention. However, we apply theread-broadcast approach to avoid misses causedby the spreading accesses to the instruction
cache.
3.3 Coherence protocols
In this study, we assume a non-blocking
write-back write-allocate cache as the base design. Speculatively stored data is retained inVol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs

Table 5 Processor and bus events
Name
PrRd
PrWr
PrNonSpec
PrFlushPrCommit
PrEvict
PrInv
PrUpd
BusWb
BusRd
BusRdXBusUpdBusUpgBusFwdDescription
Processor read (load)
Processor write (store)
The thread becomes non-speculative
The thread is ﬂushed
The thread is committed
The data is evicted from the cache
Invalidate the data
Update the data
Bus write-back transaction
Bus read transaction
Bus read-with-intent-to-modify
Bus update transaction (upd-based)
Bus upgrade transaction (inv-based)
Bus forward (part of BusRd/BusRdX)

Table 6 The basic states of cache data
State
Invalid
Clean Shared
Clean Exclusive
Modiﬁed Shared
Modiﬁed Exclusive

I
S
E
O
M

Valid
√
√
√
√

Excl.
√
√

Owned
√
√

the cache. Cache ﬁll and eviction are performed
on a per-line basis while the state of data is
managed on a per-word basis.
We consider ﬁve types of protocols as shownin Table 4. For each protocol, we deﬁne twovariants: one that manage and one that does
not manage the exclusivity of data in the cache.
The set of processor and bus events assumed
in the protocols are summarized in Table 5.
Note that bus upgrade transaction (BusUpg)
is speciﬁc to invalidation-based protocols while
bus update transaction (BusUpd) is speciﬁc to
update-based protocols.
In conventional cache coherence protocols,
there are basically three properties used fordeﬁning the state of data in the cache: Validity, Exclusivity, and Ownership 22). Using
these properties, we can deﬁne ﬁve basic states
as shown in Table 6. These states are suﬃcient for describing cache coherence protocols
when there is only one version of valid data inthe cache. Unfortunately, in speculative multithreading executions, it is possible to have multiple versions of valid data at the same time.
To correctly describe the states of data in
speculative multithreading executions, we needto deﬁne four additional properties described asfollows:• Speculativeness: Data is speculative if itis stored or forwarded by a speculative
thread. When a thread is ﬂushed due
to misspeculation, all speculative data in5

the corresponding cache must be invalidated.
Speculativeness of data is reset when the thread is promoted to nonspeculative thread.
• Violation possibility: Data is possible tocause memory dependency violation when
the ﬁrst speculative access to the data isa load. Violation is detected when a lessspeculative thread later stores to the corresponding location of the data. Violation
possibility is reset when the thread is promoted to non-speculative thread.
• Committed data: A modiﬁcation to data issaid to be committed when the thread thatmade the modiﬁcation retired. The cache
may retain the data after the thread retired. However, it is responsible to write
the data back before invalidating or replacing the data. For each data, there may
be only one cache that has the committed
property set. This property has no meaning for non-modiﬁed data.
• Delayed invalidation: Data is delayedinvalidated if a later (more speculative)
thread stored the the same location. A
delayed-invalidated data must be invalidated before a new thread is assigned tothe corresponding processing unit. If thedata is committed, it must be written backbefore being invalidated.
These new properties increase the numberof possible states in speculative multithreading caches. Showing all possible state transitions consumes a lot of space and is diﬃcult
to comprehend. We simplify the description
as follows. Each property described above canbe seen as a dimension in a multi-dimension
state space. Thus, we have a seven-dimension
state space. The state space can be separated
into several sets of independent domains. We
can then equivalently describe the protocol by
deﬁning the transition rules among the domains
in each set. Note that an event may initiate domain transition in more than one sets at a time.
We deﬁne ﬁve sets of domains as follows:( 1 ) speculativeness cleared (u) or set (U)( 2 ) violation possibility cleared (v) or set (V)( 3 ) committed data cleared (c) or set (C)( 4 ) delayed invalidation cleared (d) or set (D)( 5 ) M, O, E, S, or I
The ﬁrst four sets each have two domains, characterized by whether one of the four properties speciﬁc to speculative multithreading executions is cleared or set. The ﬁfth set has ﬁve

6

IPSJ Journal

July 2004

Table 7 Rules for transition in domains speciﬁc to speculative multithreading executions
curr
event
conditionactionnextuPrWr
thread is speculative
U
u
BusRd
forwarded by speculative thread and version matchedUu
BusRdX
forwarded by speculative thread and version matchedUuBusUpdupdated by speculative thread and version matchedU
U
PrNonSpecu
U
PrFlush
PrInv
u
v
PrRd
ﬁrst speculative access
V
V
PrNonSpecv
V
BusRdX
version matched
PrFlushv
V
BusUpdversion matched
PrFlushv
V
BusUpgversion matched
PrFlushv
c
PrCommit
the data is modiﬁed
CC
PrEvict
BusWb
cC
BusRdX
version matched
BusWb
c
C
BusUpdversion matched
BusWb
c
C
BusUpgversion matched
BusWb
c
d
BusRdXby more speculative threadDdBusUpdby more speculative threadDdBusUpgby more speculative thread
D
D
PrCommit
PrInv
d

curr
I
I
I
I
{I}
{I}
S
S
S
S
E
E
E
E
O
O
O
M
M

event
PrRd
PrRd
PrWr
PrWr
BusRd
BusRdX
PrInv
PrWr
BusRdXBusUpdPrInv
PrWr
BusRdXBusUpd
PrInv
PrWr
BusRd
PrInv
BusRd

Table 8 Rules for transition in MOESI domains
Exclusivity managed
Exclusivity not managed
updateinvalidation
updateinvalidation
conditionactionnext
actionnext
actionnext
actionnext
shared data
BusRd
S
BusRd
S
BusRd
S
BusRd
S
unshared data
BusRd
E
BusRd
E
BusRd
S
BusRd
S
shared data
BusRdXOBusRdXM
BusRdXOBusRdXO
unshared data BusRdX
M
BusRdXM
BusRdXOBusRdX
O
S
S
S
S
S
I
S
I
I
I
I
I
BusUpdO
BusUpgM
BusUpdO
BusUpg
O
PrUpd
S
PrInv
I
PrUpd
S
PrInv
I
PrUpd
S
PrInv
I
PrUpd
S
PrInv
I
I
I
M
M
PrUpd
S
PrInv
I
PrUpd
S
PrInv
I
BusWb
I
BusWb
I
BusWb
I
BusWb
I
BusUpdO
BusUpgM
BusUpdO
BusUpgO
BusFwdO
BusFwdO
BusFwdO
BusFwd
O
BusWb
I
BusWb
I
BusFwdO
BusFwdOcommon condition : the version of the data involved matcheddomains characterized by the three properties
common to conventional multiprocessor caches.
Table 7 shows the transitions among the domains in the ﬁrst four sets. The ﬁelds in thetable are: the current domain, the event that
initiates the transition, conditions necessary forthe transition, the action taken by the cachecontroller when the condition is satisﬁed, andthe next domain after the transition. The rulesin this table are common to all types of protocols we consider in this paper.
The condition “version matched” indicates
whether the version of data involved is rele-vant to the current thread running on the corresponding processing unit. In other words, whenthe version is matched, if the thread performs aload from the location, the same version of dataas the one under consideration will be provided.
Table 8 shows the transitions among the
MOESI domains in the ﬁfth set. The condition “version matched” is applied to all thetransitions in this table. We show the rules
for update-based and invalidation-based protocols. The ﬁfth and sixth rows in the table show
the rules that are relevant only if the readbroadcast capability is enabled (the ﬁfth row

Vol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs

Table 9 Latency settings for each stage in addressand data tenure

BusWb
BusRd
BusRdXBusUpdBusUpg4-PU 16-kB 2-way 64-B line
35%

Data tenure
Ovh-Arb-Ctrl-Data-Fin
0-1-4-4-1
6-1-4-4-1
6-1-4-4-1
0-1-1-1-1
0-0-0-0-0

false sharing
true sharing
cap/conflict

30%
25%
miss rate

Address tenure
Arb-Addr-Fin
1-1-1
1-1-1
1-1-1
1-1-1
1-1-1

Trans.

7

20%
15%
10%
5%

AVG

147.vortex

134.perl

132.ijpeg

130.li129.compress

Fig. 3 Data cache miss classiﬁcation in inv protocol

Data tenure
BusRd
BusWb
BusUpd126.gcc

BusRd Arb Addr Fin
BusWb
Arb Addr Fin
BusUpdArb Addr Fin

124.m88ksim

099.go0%Address tenure

Ovh
Arb
Arb

Ctrl

Arb
Ctrl

Data

Ctrl

Fin
Data Fin

Data

Fin

Fig. 2 Example of address and data tenure of the
split transaction bus

is for read-broadcast on read misses while thesixth row is for read-broadcast on write misses).
For each class of protocols, we show the twovariants that manage and does not manage theexclusivity of data. Note that in the variants
that do not manage the exclusivity of data,transitions to E or M domain are not possible.
Also note that update-based protocols broadcast cache updates using BusUpd or BusRdX
transactions, while invalidation-based protocols
broadcast invalidation messages using BusUpg
or BusRdX transactions. Finally, also note thatno update or invalidation is broadcast if thedata is exclusive (in E or M domain).
3.4 Bus model
The execution-driven cycle-accurate simulator models a split transaction bus with outof-order completion. A transaction consists ofan address tenure and a data tenure. Address
tenure is pipelined into three stages: Arbitration (Arb), Address (Addr), and Final (Fin).
The type and memory address of the transaction are broadcast at Addr stage. The corresponding data tenure can be started the next
cycle after the Arb stage of the address tenure.
Data tenure is pipelined into ﬁve stages:
Overhead (Ovh), Arbitration (Arb), Control(Ctrl), Data (Data), and Final (Fin). Ovh stage
is used to simulate latency necessary for accessing lower level (L2) cache array and is fully
pipelined. Ctrl stage is used to simulate latency
necessary for version identiﬁcation. Data stageis where the corresponding data is broadcast on
the bus.
For address bus arbitration, we applied anarbitration algorithm that prioritizes requests

by a less speculative thread over requests bya more speculative thread. A transaction thatwins the arbitration is inserted into a waiting
queue. Some transactions require several cycles
of overhead before becoming ready for data bus
arbitration. Transactions are issued for data
bus arbitration from the queue in an out-oforder fashion. When there are more than one
ready transactions, the oldest one wins the arbitration.
The length of Ovh, Ctrl, and Data stages
depends on the type of the transaction. Table 9 summarizes the latency setting we use in
the simulations. Note that BusUpg transaction
does not have data tenure, and BusUpd transaction occupies fewer cycles of the data bus since
it only needs to transfer one word rather than
the whole cache line. We assume a data bus
width of 16 bytes, so that it takes four cycles
to transfer a 64-byte cache line. Also note that
BusRd and BusRdX have a six cycle overhead
before the data arbitration can be started.
Figure 2 illustrates an example of the operation of the split transaction bus. It shows threebus transactions, BusRd, BusWb, and BusUpd
scheduled to the bus. After competing for theaddress bus, they are scheduled to the pipeline
for data tenure. Since BusRd involves additional overhead before being able to arbitratefor data bus, the later two transactions are completed ﬁrst.
4. Results
4.1 Classiﬁcation of misses
Figure 3 shows the classiﬁcation of data
cache misses in inv protocol. We assume executions on a CMP with four processing units,each with a private 16-kB 64B-line 2-way setassociative data cache. We classify the cache
misses into three classes as follows:

8

IPSJ Journal

July 2004
16-kB 2-way 64-B line

4-PU 16-kB 2-way
35%

40%
false sharing
true sharing
cap/conflict

35%

30%
average miss rate

average miss rate

30%
25%
20%
15%
10%

false sharing
true sharing
cap/conflict

25%
20%
15%
10%
5%

5%

0%

0%
8

16

32

64

128

256

Line size [bytes]

1

2

4

8

16

32

No. of PUs

Fig. 4 Varying the line size and its impact to cache
miss rate

Fig. 5 Varying the number of processing units and its
impact to cache miss rate

• Capacity/conflict misses: occur when thecache cannot contain all the lines, or when
too many lines map to the same cache set.
We also include cold misses in this category.
However, in most cases, the portion of cold
misses is small and negligible.
• True sharing misses: occur when the corresponding cache line was invalidated by awrite to the same word being accessed.
• False sharing misses: occur when the corresponding cache line was invalidated by awrite to a diﬀerent word in the same line.
We prioritize true sharing misses to false
sharing misses. Even if the ﬁrst invalidation
was to a diﬀerent word in the line, but if a later
invalidation to the line was to the same wordthat causes the miss, we classify the miss as atrue sharing miss. This is because inherently,
the miss still occurs even if we manage the validity of data on a per-word basis in which no false
sharing miss may occur. The ﬁgure shows thatsharing misses occupy more than 75% of thetotal misses. These results imply that a largepart of the cache accesses are in the form of
producer-consumer sharing. This fact is natural, considering that, the threads in speculative
multithreading are the results of partitioning asequential program.
Figure 4 shows the average miss rate when
we vary the line size from 8 bytes to 256 bytes.
As we increase the line size, true sharing misses
decrease while false sharing misses increase.
False sharing misses can be avoided by managing the states on a per-word basis rather
than on a per-line basis. This way, if a predecessor thread write to a word in the cache,
we only need to invalidate the word written
rather than the whole cache line. For a 64byte line shown in Fig. 4, we can expect thatthe average miss rate can be reduced to approximately 17%. However, the remaining true
sharing misses still occupy more than half ofthe total misses. These results hint that, using update-based protocols which do not suﬀer
from sharing misses may be a better choice ifthey do not generate excessive bus traﬃc.
4.2 Eﬀect of spreading accesses
Another possible problem in implementing coherence protocols for speculative multithreading CMPs is the spreading of the cache
accesses over the multiple data caches. The
spreading accesses decrease both the spatial
locality and temporal locality of memory accesses. To quantify this eﬀect, we vary the
number of processing units and measure how
the cache miss rate varies. The results, shownin Fig. 5, indicate that the miss rate increasesigniﬁcantly conﬁrming the large impact of the
spreading accesses.
Looking into each miss category individually, the impact of spreading accesses to capacity/conﬂict miss rate is larger than to sharing
miss rate. Even if the sharing misses can becompletely eliminated in update-based protocols, the increase in capacity/conﬂict miss rate
remains as a problem.
A possible approach to improve the situation is by using a modiﬁed read-broadcast approach. Originally, read-broadcast approachis intended to reduce sharing misses in multiprocessor caches11),17) . The bus is snooped
for read-miss transactions, and whenever a response appears on the bus and there is a matching tag of an invalid line, the line is inserted in
the cache. The original approach is however not
suﬃcient since the spreading accesses also causea signiﬁcant increase in non-sharing misses, as
shown in Fig. 5. The modiﬁed read-broadcast

Cache Coherence Strategies for Speculative Multithreading CMPs

1.4

0.9
0.8
0.7
0.6
099.go

5%
0%
1

2

4

8

16

32

GMEAN

10%

1.0

147.vortex

15%

inv
inv-robr
upd
upd-robr
upd-rwbr

1.1

134.perl20%

1.2

132.ijpeg

25%

1.3

130.liinv-robr30%129.compress

Speedup over 1-PU execution

inv

et
ar
ss
i
m
eg
ar
ev
a

9

4-PU 16-kB 2-way 64-B line

16-kB 2-way 64-B line

35%

126.gcc

No. 7

124.m88ksim

Vol. 45

No. of PUs

Fig. 8 Speedup achieved using the diﬀerent types ofprotocolsFig. 6 Estimated read-broadcast eﬀect ininvalidation-based protocols

4-PU 16-kB 2-way 64-B line

100%
95%

16-kB 2-way 64-B line

upd

upd-rwbr

8%

6%

90%
inv
inv-robr
upd
upd-robr
upd-rwbr
1-PU

85%
80%
75%
70%

1

2

4

8

16

32

No. of PUs

Fig. 7 Estimated read-broadcast eﬀect in updatebased protocols

approach extends the original approach by inserting the snooped line not only when an invalid copy of the line found in the case, but also
when there is no matching copy of the line in
the cache. Note that the approach we consider
here is more aggressive than the approach taken
in Multiscalar’s SVC. SVC only inserts the line
if there is a free line available.
The logic of the approach is as follows. We
expect that there is spatial and temporal locality of memory accesses between a thread
and its nearby successors. Thus, when thethread misses a cache line, there is large possibility that the successors may also need thedata from the same line. By using the readbroadcast approach to prefetch the line, we can
avoid the corresponding misses in the successors. Note that for invalidation-based protocols, the prefetching can be performed only onread miss transactions. On write miss transactions, there is no advantage of prefetching theline since it will be invalidated immediately.

HARMEAN147.vortex

134.perl

132.ijpeg

130.li129.compress

0%124.m88ksim

60%

2%

126.gcc

65%

4%099.go

tea
r
ss
i
m
eg
ar
ev
a

upd-robr

Data cache hit rate

10%Fig. 9 Data cache hit rate for each type of protocols

We estimate how much we can suppress
the increase in cache miss rate by using thetechnique. Figure 6 shows the results forinvalidation-based protocols. Comparing themiss rate of inv-robr (read-broadcast enabled)
to the miss rate of inv conﬁrm that we can suppress the increase in cache miss rate using thetechnique. However, the miss rate in multiplePU conﬁgurations remains signiﬁcantly higher
than the miss rate in single-PU conﬁguration.
This is mostly because there are still a lot ofsharing misses remaining.
Figure 7 shows the improvement in the caseof update-based protocols. From the ﬁgure, it
can be seen that applying read-broadcast on
read misses alone (upd-robr) signiﬁcantly suppresses the increase in cache miss rate. Applying read-broadcast also on write misses (updrwbr) further reduces the miss rate, helping tomaintain the cache miss rate almost constanteven when the number of processing units is increased.
4.3 Performance comparisons
Figure 8 shows the speedup over conventional execution on one processing unit

10

IPSJ Journal

July 2004
4-PU 16-kB 2-way 64-B line

18%

40%

16%

35%

20%

HARMEAN099.goHARMEAN147.vortex

134.perl

132.ijpeg

130.li129.compress

0%126.gcc5%0%124.m88ksim

10%

2%

147.vortex

15%

4%

134.perl

6%132.ijpeg

8%

inv
inv-robr
upd
upd-robr
upd-rwbr25%

130.li10%30%129.compress

inv
inv-robr
upd
upd-robr
upd-rwbr

126.gcc12%124.m88ksim

14%

Data bus utilization

45%

099.goAddress bus utilization

4-PU 16-kB 2-way 64-B line
20%

Fig. 10 Address bus utilization

Fig. 11 Data bus utilizationachieved for the ﬁve protocols shown in Table 4.
Here, we used protocol variants that manage
the exclusivity of data. The ﬁgure shows thaton average the three update-based protocols
outperform the other two invalidation-based
protocols. The ﬁgure also shows that applying read-broadcast approach signiﬁcantly improves the performance for both invalidationbased and update-based protocols. The impact
is however larger for invalidation-based protocols since the cache hit rate in the baseline conﬁguration (read-broadcast disabled) is lower.
We can also observe that applying readbroadcast on both read and write misses as
in upd-rwbr only slightly improves the performance over upd-robr. However, we expect thatthe impact becomes larger for larger number ofprocessing units as we previously indicated inFig. 7.
Figure 9 shows the data cache hit rate foreach type of protocols. Note that the hit rate
is lower than the predicted miss rate shown in
Fig. 6 and Fig. 7 since we treat a partial hit (ahit to a cache line being brought to the cache) asa miss. For reference, we also shows the hit rate
for conventional execution on a single processing unit. Overall, the results conﬁrm that using
update-based protocols instead of invalidationbased protocols, and applying read-broadcast
approach signiﬁcantly reduce the cache missrate.
4.4 Bus utilization
Figure 10 and Fig. 11 show the bus utilization of address bus and data bus respectively.
We measure the utilization by counting the bus
cycles consumed in Addr stage for address bus,
and in Data stage for data bus. The ﬁgures
show that using update-based protocols andapplying read-broadcast approach decrease thebus utilization. The results for update-based

protocols are quite surprising since the use of
update-based approach works in favor of lower
bus utilization.
Figure 12 and Fig. 13 show the breakdownof the address and data bus cycles consumed ineach protocol. They show that, using updatebased protocols and applying read-broadcast
approach signiﬁcantly reduce BusRd and BusRdX transactions caused by cache misses.
Since we set the latency of Addr stage to
one cycle for all types of transactions, the data
shown in Figure 12 can also be interpreted
as the breakdown of the number of transactions that occupied the address bus. The ﬁgure shows that the number of BusUpd transactions in update protocols is at most 80% larger
compared to the number of BusUpg (invalidation) transactions in invalidation-based protocols. This indicates that there is only a small
number of useless update transactions. Furthermore, although the BusUpd transactions
require additional data bus traﬃc in updatebased protocols, the increase in traﬃc is oﬀset
by the signiﬁcant decrease in BusRd and BusRdX traﬃc.
Finally, we can also observe that applying themodiﬁed read-broadcast approach slightly increases the number of bus write-back (BusWb)transactions. This is because the prefetchingeﬀect of the approach initiates more cache replacements. For most cases, however, the increase is smaller than the reduction in the number of miss transactions (BusRd and BusRdX),
resulting in saved bus cycles.
The reasons why speculative multithreading
favors update-based protocols in terms of bus
utilization, contradicting previous results in thecontext of conventional multiprocessors, are as
follows:( 1 ) Update-based protocols reduce sharingVol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs
4-PU 16-kB 2-way 64-B line

7.E+07
BusUpgBusUpdBusRdX
BusRd
BusWB

6.E+07Address Bus Cycle

11

5.E+07
4.E+07
3.E+072.E+07
1.E+070.E+00

v
in

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

099.go

r v
b n
i
w
r
d
p
u

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

r v
b n
i
w
r
d
p
u

124.m88ksim

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

126.gcc

r v
b n
i
w
r
d
p
u

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

r v
b n
i
w
r
d
p
u

129.compress

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

130.li

r v
b n
i
w
r
d
p
u

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

132.ijpeg

r v
b n
i
w
r
d
p
u

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

134.perl

r v
b n
i
w
r
d
p
u

r
b
o
r
v
n
i

d
p
u

r
b
o
r
d
p
u

r
b
w
r
d
p
u

147.vortex

Fig. 12 Address bus cycle breakdown

2.E+081.E+08
Data Bus Cycle

1.E+08

4-PU 16-kB 2-way 64-B line
BusUpdBusRdX
BusRd
BusWB

1.E+088.E+07
6.E+07
4.E+070.E+00inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr
inv
inv-robr
upd
upd-robr
upd-rwbr

2.E+07099.go124.m88ksim

126.gcc

129.compress

130.li

132.ijpeg

134.perl

147.vortex

Fig. 13 Data bus cycle breakdown

misses more signiﬁcantly in speculative
multithreading context than in conventional multiprocessor context.
( 2 ) The length of write-runs in speculative
multithreading is shorter than in typical workloads of conventional multiprocessors.
Write-run is deﬁned by Eggers et.al. as asequence of write references to a shared cachedata by a single processor uninterrupted byany memory access to the same block by another processor9) . It is useful as an indicator of whether an application is suitable forinvalidation-based protocols or update-based

protocols. Application with long write-runs
beneﬁts from invalidation-based protocols since
it avoids unnecessary updates, while the reverse
is true for update-based protocols.
In speculative multithreading, we divide theprogram into small chunks (threads), thus,
there are only a few stores inside a thread.
These threads are then assigned to multiple
processing units, forming sharing patterns withshort write-runs. Invalidation-based protocols
perform better if write-run length is considerably large. For example Dahlgren reported that
Cholesky has more than 50% of the write-runswith length of eight7) . In our case, however,12

IPSJ Journal

July 2004

Table 10 Impact of managing exclusivity
Reduction in
No. BusUpd
No. BusUpg
Addr. bus cycle
Data. bus cycle
Addr. bus utilization
Data. bus utilization
Execution cycles

inv
7.9
1.9
-0.2
0.3
-0.1
0.2

Reduction rate [%]inv-robr
upd upd-robr- 20.8
26.6
33.3
14.1 12.3
15.5
1.4
7.5
8.0
2.1
1.9
2.2
0.4
1.9
1.8
-0.3
1.1
0.5

5. Conclusion

Write-run length distribution
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%

147.vortex

134.perl

132.ijpeg

130.li129.compress

126.gcc

124.m88ksim

>4
2-4
1

099.goupd-rwbr
28.7
17.5
8.8
2.6
2.1
0.4

Fig. 14 Write-run length distribution

more than 80% of the write-runs have length
less than or equal to four as shown in Fig. 14.
This, combined with the signiﬁcant reduction inmiss rate, explain why update-based protocols
perform better.
4.5 Impact of managing exclusivity
Table 10 presents the impact of managing
exclusivity in the ﬁve protocols we used in thisstudy. The table shows the reduction in thenumber of BusUpd and BusUpg transactions,consumed bus cycles, bus utilization, and theexecution cycles. It can be seen that managing exclusivity helps to reduce the number ofBusUpd and BusUpg transactions between 7.9%
to 33.3%. These reductions in turn reduce thetotal number of bus cycles consumed. The reductions in update-based protocols are larger
than in invalidation-based protocols, ranging
from 12.3% to 17.5% for address bus, and from
7.5% to 8.8% for data bus. These reductions,however, only contribute to a few percents ofdecrease in bus utilization of the address bus
and the data bus. As the result, managing exclusivity only provides a slight performance improvement over the protocols that do not manage the exclusivity. These results suggest that
if a simpler design is preferred, it is better tochoose protocols that do not manage exclusivity of data.

This paper studied the impact of several
cache coherence strategies for speculative multithreading chip multiprocessors. We ﬁrst characterized the eﬀect of speculative multithreading executions to cache misses. We found thatsharing misses occupy the largest portion of
misses, and spreading accesses in speculative
multithreading executions cause a signiﬁcant
increase in the miss rate. These two factors,
if not handled properly, limit the speedup thatcan be achieved using the speculative multithreading executions.
Performance study further showed that
update-based protocols, which do not suﬀer
from sharing misses, achieve signiﬁcantly higher
performance than invalidation-based protocols.
Interestingly, the update-based protocols also
have lower bus utilization. The study also revealed that applying a modiﬁed read-broadcast(snarﬁng) approach is eﬀective for suppressing
the eﬀect of spreading cache accesses. Finally,
the study showed that managing the exclusivity of data in caches oﬀer little performance improvement, suggesting that it can be traded oﬀ
if a simpler design is preferred.
Acknowledgments This research is partially supported by Grant-in-Aid for Fundamental Scientiﬁc Research B(2) #13480077
from Ministry of Education, Culture, Sports,
Science and Technology Japan, Semiconductor Technology Academic Research Center(STARC) Japan, CREST project of Japan Science and Technology Corporation, and by 21st
century COE project of Japan Society for the
Promotion of Science. We are also thankful foranonymous reviewers for their constructive critics and suggestions.
References
1) 小林 良太郎, 岩田 充晃, 安藤 秀樹, 島田 俊夫.
非数値計算プログラムのスレッド間命令レベル並列を利用するプロセッサアーキテクチャ SKY. In

Vol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs

Proc. of the JSPP 1998, pages 87–94, 1998.
2) 田代 大輔、バルリ ニコ デムス、坂井 修一、田中英彦. スレッド投機実行におけるエッジに着目したスレッド分割手法. ARC-2003-153, 2003(40):67–
72, 2003.
3) 飯塚 大介、小沢 年弘、坂井 修一、田中 英彦.
C コンパイラによるループ最適化の検討. HPC99-77, 99(66):65–70, 1999.
4) H. Akkary and M. A. Driscoll. A Dynamic
Multithreading Processor. In Proc. of the 31st
MICRO, pages 226–236, 1998.
5) N.D. Barli, L.D. Hung, H.Miura, S.Sakai, and
H. Tanaka. A Dual-Length Path-Based Predictor for Thread Prediction. International Workshop on Innovative Architectures 2003, 2003.
6) N.D. Barli, D.Tashiro, C.Iwama, S.Sakai, and
H. Tanaka. A Register Communication Mechanism for Speculative Multithreading Chip Multiprocessors. In Proc. of the SACSIS 2003,
pages 275–282, 2003.
7) F. Dahlgren. Boosting the Performance of Hybrid Snooping Cache Protocols. In Proc. of the22th ISCA, pages 60–69, 1995.
8) M. Edahiro, S. Matsushita, M. Yamashina,
and N. Nishi. A Single-Chip Multiprocessor
for Smart Terminals. IEEE Micro, 20(4):12–
20, 2000.
9) S. J. Eggers and R. H. Katz. A Characterization of Sharing in Parallel Programs. In Proc.
of the 15th ISCA, pages 373–382, 1988.
10) S. J. Eggers and R. H. Katz. Evaluating
The Performance of Four Snooping Cache Coherency Protocols. In Proc. of the 16th ISCA,
pages 2–15, 1989.
11) J. R. Goodman and P. J. Woest. The Wisconsin Multicube: A New Large-Scale CacheCoherent Multiprocessor. In Proc. of the 15th
ISCA, pages 422–431, 1988.
12) S. Gopal, T. N. Vijaykumar, J. E. Smith, and
G. S. Sohi. Speculative Versioning Cache. In
Proc. of the 4th HPCA, pages 195–205, 1998.
13) L. Hammond, M. Willey, and K. Olukotun.
Data Speculation Support for a Chip Multiprocessor. In Proc. of the 8th ASPLOS, pages
58–69, 1998.
14) V. Krishnan and J. Torrellas.
A ChipMultiprocessor Architecture with Speculative
Multithreading. IEEE Transactions on Computers, 48(9):866–880, 1999.
15) P. Marcuello, A. Gonzalez, and J. Tubella.
Speculative Multithreaded Processors. In Proc.
of the 12th ICS, pages 77–84, 1998.
16) K.Olukotun, L.Hammond, and M.Willey. Improving The Performance of Speculatively Parallel Applications on the Hydra CMP. In Proc.
of the 13th ICS, pages 21–30, 1999.
17) Z. Segall and L. Rudolph. Dynamic Decentral-

13

ized Cache Schemes for MIMD Parallel Processors. In Proc. of the 11th ISCA, pages 340–347,
1984.
18) M. Sharir. Structural Analaysis: A New Approach to Flow Analysis in Optimizing Compilers. Computer Languages, 5(3/4):141–153,
1980.
19) G.S. Sohi, S.E. Breach, and T.N. Vijaykumar.
Multiscalar Processors. In Proc. of the 22nd
ISCA, pages 414–425, 1995.
20) J. G. Steﬀan, C. B. Colohan, A. Zhai, and T. C.
Mowry. A Scalable Approach to Thread-Level
Speculation. In Proc. of the 27th ISCA, pages
1–12, 2000.
21) J. G. Steﬀan, C. B. Colohan, A. Zhai, and T. C.
Mowry. Improving Value Communication for
Thread-Level Speculation. In Proc. of the 8th
HPCA, pages 65–75, 2002.
22) P. Sweazey and A. J. Smith. A Class of Compatible Cache Consistency Protocols and theirSupport by the IEEE Futurebus. In Proc. of
the 13th ISCA, pages 414–423, 1986.
23) J.-Y. Tsai, J. Huang, C. Amlo, D. J. Lilja,
and P.-C. Yew. A Chip-Multiprocessor Architecture with Speculative Multithreading.
IEEE Transactions on Computers, 48(9):881–
902, 1999.
24) Y. Yanagawa, L. D. Hung, C. Iwama, N. D.
Barli, S. Sakai, and H. Tanaka. Complexity
Analysis of A Cache Controller for Speculative
Multithreading Chip Multiprocessors. In Proc.
of the 10th HiPC (LNCS 2913), pages 393–404,
2003.

(Received January 30, 2004)(Accepted May 9, 2004)
Niko Demus Barli received
the M.E. degree in Information
Engineering from The University of Tokyo in 2001. He graduated with the Ph.D. degree in Information and Communication
Engineering from The University of Tokyo in 2004. His graduate researchmainly focused on speculative multithreading
techniques on Chip Multiprocessors. He currently works for Texas Instruments Japan.

14

IPSJ Journal

July 2004

Luong Dinh Hung is currently a Ph.D. student in Information and Communication Engineering in The University ofTokyo. He received the M.E.
degree in Information and Communication Engineering fromThe University of Tokyo in 2004. He actively
pursues new ideas in the ﬁeld of architecture
and circuit techniques for VLSI power reduction.

Daisuke Tashiro is currently
a Ph.D. candidate in Information and Communication Engineering in The University ofTokyo. He received the M.E. degree in Information Engineeringfrom The University of Tokyo in
2002. His research interests are in speculationand compiler techniques for speculative multithreading architectures.

Hideyuki Miura received
the M.E. degree in Information and Communication Engineering from The University ofTokyo in 2004. He currently
works for East Japan Railway
Company. He investigated andevaluated control speculation techniques andinstruction fetch mechanisms for speculative
multithreading architectures in his graduate research.

Shuichi Sakai received the
M.E. degree and Ph.D. degree in Information Engineeringfrom The University of Tokyoin 1983 and 1986 respectively.
He worked in ElectrotechnicalLaboratory Japan from 1986 to
1990. From 1991 to 1992, he became a visiting scientist in Computation Structures Group,
Massachusetts Institute of Technology. From1993 to 1996, he was a chief at Massively Parallel Architecture Laboratory in Real World
Computing Partnership. He became an Associate Professor in University of Tsukuba in 1996
and came to The University of Tokyo in 1998
as an Associate Professor. From 2001, he has
been a Professor in Graduate School of Information Science and Technology of The University of Tokyo. His research interests include
dependable computer systems, microprocessor
architecture, compiler, parallel computing, andmultimedia processing. He wrote several books
on logic circuits and computer architecture, including “Introduction to Logic Circuits” and“Computer Architecture with Illustrated Explanation”. He is a member of IPSJ, IEEE,
ACM, IEICE, and JSAI.

Chitaka Iwama received
the M.E. degree in Information and Communication Engineering from The University ofTokyo in 2003. She is currently
a Ph.D. student in Information
and Communication Engineering in The University of Tokyo. Her researchinterests are in architecture level power modeling framework and power reduction techniques.

Vol. 45

No. 7

Cache Coherence Strategies for Speculative Multithreading CMPs

Hidehiko Tanaka received
the M.E. degree and Ph.D. degree in Electronis Engineeringfrom The University of Tokyo in
1967 and 1970 respectively. He
became an Associate Professor
in Graduate School of Engineering of The University of Tokyo in 1971. From1978 to 1979, he was a visiting professor in The
City University of New York. He became a
Professor in Graduate School of Engineering of
The University of Tokyo in 1987. From 2001 to
2004, he served as the Dean of Graduate Schoolof Information Science and Technology of The
University of Tokyo. Currently, he is the Deanof Graduate School of Information Security of
Institute of Information Security Japan. His research interests include computer architecture,parallel and distributed processing, natural language processing, multimedia processing, andcomputer aided design. He wrote many books
on computer systems, including “Non Von Neumann Computers”, “Information and Communication Systems”, “Parallel Inference Engine PIE”, “Computer Architecture”, “VLSI Computer I, II”, and “Software-oriented Architectures”. He is a member of IPSJ, IEEE, ACM,
IEICE, JSAI, and JSSST.

15