A Hardware/Software Approach for Thread Level Control Speculation
Luong Dinh Hung, † Hideyuki Miura,† Chitaka Iwama , †Daisuke Tashiro, † Niko Demus Barli,† Shuichi Sakai†and Hidehiko Tanaka†Speculative multithreading is a promising approach that exploits thread level parallelism
from sequential programs. This paper focuses on thread level control speculation for a speculative multithreading architecture, and proposes a hardware/software techniques that improves
its performance. Our approach is to use static analysis of control ﬂow to validate dynamic
prediction at an earlier stage, and also to reduce task of the dynamic thread predictor. We
show that this approach reduces prediction miss penalty and, at the same time, improves thethread prediction accuracy.

1. Introduction
The limit of Instruction Level Parallelism (ILP)
hinders superscalar microprocessors from achieving high performance against general purpose application [1]. The approach of exploiting Thread
Level Parallelism (TLP) has proved to be very
successful for several types of applications, suchas multiprogrammed workloads or multithreaded
applications. However, applying this approach tosequential programs still remains a challenge.
Recently, numerous researches have focused on
speculative multithreadings to exploit TLP fromsequential applications [2] [3] [7]. Those architectures break sequential programs into threads
and execute them in parallel using multiple execution units. In order to ease the program partitioning, threads that are candidates for parallel
execution are allowed to be dependent on eachother, i.e. data dependences or control dependences may exist between threads. In exchange,
additional hardware and software support is integrated to maintain sequential semantics.
Since the eﬀectiveness of such parallelization islimited by the inter-thread dependences, speculative multithreading architectures perform various forms of thread level speculation. Threads
are speculatively executed in parallel regardless ofdata or control dependences among them. Intensive researches have been done on the mechanismof thread level speculation. Data speculation canbe performed using speculative load [7] or data
value prediction [10], whereas control speculation
is based on various form of control ﬂow predic† Graduate School of Information Science and Technology, The University of Tokyo

1

tion.
This paper focuses on thread level control speculation to improve the performance of speculative
multithreading execution. We address the speculation problem from two perspectives: improving
the prediction accuracy and reducing the speculation miss penalty. We propose a combination of
hardware and software approach: a thread prediction hardware assisted by static information
inserted by a compiler. The static information
is used to validate thread prediction at an earlier stage and also to reduce capacity and conﬂict
misses of thread prediction table.
The remainder of this paper is organized as follows. Section 2 explains the thread level control
speculation mechanism in our architecture model,
and refer to how other proposed speculative multithreading models deal with inter-thread control
dependences. Section 3 presents our proposed
techniques. Section 4 evaluates the contributionof the techniques to the overall performance anddiscusses their trade-oﬀs. Section 5 concludes thepaper.
2. Thread Level Control Speculation
2.1 Baseline Architecture
Throughout the paper, we assume a speculative multithreading architecture described as follows. First, sequential programs are partitioned
into threads at compile time. A thread is deﬁned
as a connected subgraph of a static control ﬂow
graph with a single entry node. It may comprisea basic block, multiple basic blocks, loop body,or entire function. Most threads consist of 20-30
dynamic instructions [8].
Those threads are then executed in parallel on aThread Control Unit
Thread Predictor
PU 1

Thread Validation
and Retire Unit
PU 4

SS
Core

Reg.
Sync.
Unit

ICacheDCacheController andSpeculation support

SS
Core

Reg.
Sync.
Unit

ICacheDCacheController andSpeculation support

Secondary Cache

Fig. 1 Baseline architecture

chip multiprocessor that integrates four processing units on a single chip. Figure 1 illustrates theorganization. Register ﬁles and ﬁrst-level caches
are distributed to each processing unit. For handling inter-thread data-dependences, we assume
a register synchronization mechanism similar tothe one found in [2], and a memory speculation
mechanism similar to [7]. Inter-thread control dependences are handled by a centralized thread
control unit. The unit includes a hardware wecall thread predictor, which predicts address of thethread that should be executed next. The processing units are logically organized in the formof an one-directional ring. According to the suggestion made by the thread predictor, the thread
control unit speculatively assigns a thread to thetail of the ring of the processing units. If the prediction fails, the thread control unit discards the
misspeculated threads and recovers execution.
2.2 Importance of Thread Prediction
The thread prediction mechanism has a great
impact on overall performance. Figure 2 shows
an example of thread level control speculation.
Let us consider the control ﬂow graph shown inﬁgure 2 (a), where thread B and C are control dependent on thread A. Which of the two threads
should be executed cannot be determined until
the last branch in thread A resolves. However,in order to gain performance, the thread predictor predicts which path will be taken so that thethreads can be speculatively executed in parallel. In ﬁgure 2 (b), the predictor has successfully
predicted thread B to be executed. The three
threads are spawned successively after a shortthread starting overhead, and completed withina minimum cycle time. On the other hand, ﬁgure 2 (c) shows a case in which the prediction
turned out to be a miss. After the last branch inthread A resolved, the thread control unit is in-2

formed that thread 3 should be executed insteadof thread B. Then the control unit ﬂushes all the
successors of thread B, and restart execution of
thread C. It can be seen that a large number ofcycles are waisted by the execution of misspeculated threads and the recovery of the execution
states.
This example shows that the performance of the
speculative multithreading execution is largely
improved when the thread prediction hits, but
suﬀers severely when the prediction misses. Thus,
it is important to design a speculation mechanismthat can maximize the thread prediction accuracy
and/or minimize the speculation miss penalty.
2.3 Related Work
Various models of speculative multithreading
have been previously proposed, each with diﬀerent ways of handling control dependences.
Some architectures do not allow inter-thread
control dependences.
In SKY architecture,
threads are only forked at control equivalentpoints [3]. This scheme avoids control misspeculation and eliminates its penalty. However, it sacriﬁces chances to achieve more performance gain
in inherently parallel applications.
Multiscalar processor relies on thread level control speculation. A detail work has been done onits mechanism [6]. Multiscalar uses both hardware and software to achieve high thread prediction accuracy. Software assistance comes in theform of a thread header appended to each thread.
Compiler includes in the header the number andtype of the thread exit points, as well as addressesof the next threads if they are known at compile time. At runtime, a dedicated hardware predicts the control ﬂow based on a similar scheme toconventional branch predictors. First, it predicts
which exit of the current thread is most likely to
be taken, using a Pattern History Table (PHT).
Then, it predicts the address of the exit. The address is either obtained from the thread header
or predicted using a Thread Target Buﬀer(TTB),
which is an extension of a Branch Target Buﬀer.
Although this approach is successful in achieving
high prediction accuracy, it does not consider the
possibility to achieve more performance by reducing prediction miss penalty.
3. Hardware/Software Approach
3.1 Concept
As already noted in the previous section, to im-ThreadC

time

ThreadB

time

ThreadA

spawn

ThreadA

spawn

ThreadB

spawn

ThreadA

spawn

ThreadB

ThreadDcommitThreadC

commitcommitThreadD(a) Control flow graphMispredictedflush

ThreadD

Successors ofmispredicted
thread arealso flushed

ThreadD

New threads areloaded & executed(b) Correct thread prediction(c)Thread misprediction

Fig. 2 Example of thread level control speculation

prove execution performance through thread level
control speculation, it is important to achieve
high prediction accuracy and low misspeculation
penalty. Since thread prediction can be seen as
an extension of branch prediction, it is possible toapply a number of sophisticated branch prediction mechanisms previously proposed. However,these mechanisms are mainly designed only to increase the accuracy of prediction. Alternatively,
we investigate a method that use compiler assistance to reduce misspeculation penalty as well as
to improve prediction accuracy.
Our approach is to let the compiler perform
reachability analysis of the control ﬂow graph andprovide a mechanism to inform the thread control
unit about thread reachability. Speciﬁcally, thecompiler marks points in the control ﬂow graphwhere a successor thread can be uniquely identiﬁed or where it becomes unreachable. Using
this information, the thread control unit may beable to validate the prediction result at an earlier
stage. The early validation permits an early recovery from the misspeculated execution states,
leading to lower misprediction penalty.
It is also possible to use the thread reachability information to increase the accuracy of
thread prediction. There are cases when a successor thread can be uniquely determined statically. We deﬁne a thread whose successor thread
can be ﬁxed before its execution begins as a fixedsuccessor thread. If the compiler marks the ﬁxedsuccessor threads with appropriate information,
the thread control unit is able to obtain the correct address of a successor thread without using
the thread predictor, thus reducing the requirement for prediction table entries. It is expectedthat it will lead to a reduced capacity and conﬂict misses of prediction table and an increased
overall prediction accuracy.
In the following subsections, the structure of3

thread prediction hardware used in this research
is described. Then, the analysis method andmechanism for early control speculation validation is explained. Finally, the mechanism for handling ﬁxed-successor threads is described.
3.2 Hardware Structure of Thread Predictor
In this research we use a thread predictor whose
structure is shown in ﬁgure 3. Thread Target
Buﬀer (TTB) is a table that caches the starting
address of successor threads. The index for accessing the TTB is generated by applying a hashing function on history registers. History registers record starting addresses of the most recently executed threads. They are used to generate thread history pattern to exploit correlation
among threads to achieve better prediction accuracy.

Index generation
ThreadHistory
Registers

HashingFunction

Look-up Target

Buffer(TTB)

Next
ThreadAddress

Updating
Fig. 3 Structure of thread predictor

To reduce conﬂict misses when accessing TTB,
the hashing function must also eﬀectively encode the thread history pattern into a designatedlength index. Here we adopt a hashing function
proposed by Multiscalar group [6]. Figure 4 illustrates the index generation mechanism. First,
lower address bits of the History Registers areconcatenated to form an intermediate index. The

n1 bits
BB1

N-
N-2

BB1

br1

Intermediate index

br1
REJECT C,D

nd bits

Concatenating

BB2

BB3

BB2

br2

br3

br2

Folding

N-d

ASSERT A

BB4

History Registers

Final index

Thread A

BB5

Thread C Thread D

Thread B

Fig. 4 Index generation mechanism(a)Thread Structure

ﬁnal index is then constructed by folding the intermediate index. Folding is done by dividing theintermediate index into several, identical length
subﬁelds and then XORing those subﬁelds.
3.3 Software Assisted Early Validation
This subsection explains how we implement theconcept of early control speculation validation using compiler assistance. After partitioning a program into threads, the compiler does control ﬂow
reachability analysis for each thread. The analysis identiﬁes points where a successor thread canbe uniquely determined, or where it becomes unreachable. The compiler then inserted assert andreject instructions for the two cases respectively.
The assert and reject instructions carry a pointerto a register that will hold starting address of a
successor thread.
Figure 5 illustrates how the compiler inserted
these instructions. Suppose there is a threadwhich comprises six basic blocks (BB1∼BB6) asshown in ﬁgure 5(a). It has four possible successors, thread A, thread B, thread C and thread D.
Using control ﬂow reachability analysis, the compiler identiﬁes points where only one of the four
threads is reachable and insert assert instructions.
Similarly, the compiler ﬁnds points where one ormore of the four threads become unreachable, andinsert reject instructions. Figure 5 shows where
those instructions will be inserted for the example.
Assert instruction indicates that the control
ﬂow will absolutely go to the designated successor thread. When a processing unit executing athread encounters an assert instruction, it notiﬁes the thread control unit and sends the address of the successor thread. Thread control unit
then checks if the address of thread predicted earlier matches the address notiﬁed by the processing unit. If a mismatch occurs, the thread control unit knows it has mispredicted the successor

4

BB6

BB4
Thread A

REJECT A,B

BB3
br3
ASSERT C

ASSERT D

BB5

BB6

Thread C Thread D

Thread B(b) Insertion of assert & rejectFig. 5 Illustration of sofware assisted early validation

thread and can start the procedure to ﬂush themispredicted thread and restart the execution ofa correct successor thread.
In contrast to assert instruction, a reject instruction indicates that there is no possibility thatthe control ﬂow will go to the designated successor thread. The notiﬁcation mechanism is identical to the case of assert instruction. When thethread control unit is notiﬁed by a processing
unit, it again does the address matching process.
In case of notiﬁcation initiated by reject instructions, misprediction can be detected if the notiﬁed address matches the the predicted address.
If it is the case, the thread control can ﬂush themispredicted thread, and optionally repredict andrestart an execution of another thread.
3.4 Fixed-Successor Thread
As noted previously, we deﬁned a ﬁxedsuccessor thread as a thread that has only one
successor whose address can be statically determined. Fixed-successor threads can be identiﬁedusing the same reachability analysis explained in
the previous subsection. When the compiler canassure that a thread may only have one successor, and the start address of the successor canbe determined statically, it marks the thread asa ﬁxed-successor thread. The compiler also inserts the starting address of the successor into thethread’s header. The thread control unit will use
this address to start the correct successor thread.
Figure 6 illustrates the ﬂow of the thread prediction mechanism. First, the thread control unit
checks if the thread is marked as a ﬁxed-successor
thread. In that case, the address of the successor
thread is obtained from the thread header. Otherwise, it is predicted using the hardware predictor.
By exploiting the characteristics of ﬁxed-

structions are handled using the mechanism described in section3. As for reject instructions, incase a misprediction is detected due to a reject
notiﬁcation, the thread predictor repredicts andrestarts a new successor thread. In order to evaluate the potential of using reject information, here
we assume that the reprediction is always successful.

begin
Is
fixed-successor

Thread?

Yes
Predicted by
TTB

No Next-thread address
is derived fromthread header

end

Fig. 6 Flow of thread prediction

successor threads, we can eliminate the possibilityof mispredicting a successor of a ﬁxed-successor
threads. In addition, since the ﬁxed-successor
threads do not use entry in the TTB, it is also
expected that the accuracy of the thread predictor can be further improved, resulting in more
performance gain.
4. Evaluation
4.1 Simulation Environment
We use a trace-based simulator that models a
4-PU (processing unit) CMP described in section 2.1. The architecture conﬁguration is summarized in table 1.
Parameter
Pipeline stages
Arith/Logic units
Address units
Reorder buﬀer size
Load/Store queue size
Fetch/Decode/Rename/Retire width
L1 Instruction cache
L1 Data cache
L2 Uniﬁed cacheInter PU register comm.
TTB no. of entries
TTB history depth
TTB index folding

Conﬁguration
10
4
2
64
20
4
32 kb - 2 cycles
32 kb - 2 cycles
ideal - 6 cycles
1 cycle2048
4
3 times

4.2 Results
Figure 7 shows the normalized execution timeof SPECint95 programs. Binaries with fixedsuccessor thread information resulted in better
performance for all programs, especially go, gcc
and vortex. The average speed-up was 3.3%.
Adding assert instructions gave further performance improvements in most cases. For go andvortex, the execution time was reduced by morethan 8.5%. However, the eﬀect of assert instructions varied among applications. For example,
ijpeg and m88ksim required slightly longer execution time than in FS case. The reject instructions
did not contribute to the performance. Except
compress and go which showed limited improvement, all the programs suﬀered degraded performance. The execution time of perl was increasedby more than 50%.
The positive eﬀect of the additional control ﬂow
information comes from both early validation of
the thread prediction and higher prediction accuracy. On the other hand, there is also a negative eﬀect that comes from the increased numberof executed instructions. Those factors are discussed in detail below.
1.2

Table 1 Conﬁguration parameters

We prepared four types of binaries ofSPECint95 benchmarks.
• BASE: no control ﬂow information is added.
• FS: for each fixed-successor thread, its header
is marked and equipped with the address of
its successor thread.
• FS+ASSERT: in addition to fixed-successor
information, assert instructions are inserted
wherever possible.
• FS+ASSERT+REJECT: reject instructions are fully added.
The fixed-successor information and assert in-

5

1.36

BASE
FS
FS+ASSERTFS+ASSERT+REJECTemti 1.1noit
uc 1.05exe1
deizl 0.95am
ro 0.9
N
1.15

0.85
0.8

compress

gcc

go

ijpeg

li

m88ksimperl

vortexFig. 7 Normalized execution time of eight SPECint95
programs

Prediction hit-rate. We found that, on average, 28.4% of executed threads are fixed-successor
threads. Since the fixed-successor threads do not
occupy entries in TTB, the thread predictor canachieve higher prediction accuracy. We veriﬁedthat average hit-rate of FS set was 2.8% higher
compared to that of BASE binaries. The hitrate improvement was considerable for go, gcc
and vortex, whose control ﬂow is relatively lesspredictable. This explains the outstanding performance improvement of those programs that wehave observed in ﬁgure7.
Number of retired instructions.
The
number of retired instructions is shown in ﬁgure 8. Checking whether a thread is a fixedsuccessor thread is done by consulting the thread
header.Therefore, BASE and FS binaries show
the same number of retired instructions. Adding
assert and reject information increased the number of instructions by 5.7% and 8.1%, respectively. In case of assert information, for mostprograms, the beneﬁt of early misprediction validation was larger than the extra overheads due tothe increased number of instructions. However,
the reverse was true for reject information. Especially for perl, the number of instructions wasincreased by 44%, resulting in severe slowdown inperformance as shown in ﬁgure 7.
Number of retired
instructions (normalized)

1.2

BASE
FS
FS+ASSERTFS+ASSERT+REJECT

1.15

1.48

1.05

1

compress

gcc

go

ijpeg

Acknowledgement
This research is partially supported by Semiconductor Technology Academic Research Center(STARC) Japan, under project name Researchon Next Generation Low-power Chip Multiprocessors.
References[1] David W. Wall, Limits of Instruction Level
Parallelism, Proceedings of the 4th ASPLOS,
pp.176-188, Apr. 1991
[2] Gurindar S. Sohi, Scott E. Breach, and T. N.
Vijaykumar, Multiscalar Processors, Proceedingsof the 22nd ISCA, pp.414-425, Jun. 1995
[3] 小林 良太郎, 岩田 充晃, 安藤 秀樹, 島田 俊夫, 非数
値計算プログラムのスレッド間命令レベル並列を利用するプロセッサ・アーキテクチャ SKY, 並列処理シンポジウム JSPP98, pp.87-94, Jun. 1998

1.1

0.95

information reduced the execution time further
by 3.7%. However, the gain achieved by inserting
reject information was cancelled by the increased
number of executed instructions.
More work is needed to improve the eﬀectiveness of early misprediction validation. Currently,
assert or reject instructions are inserted wherever
possible. A smarter approach that inserts information only where a substantial gain is expected,
might result in a better performance.

li

m88ksimperl

vortexFig. 8 Number of retired instructions ( normalized )5. Conclusion
This paper explored an approach of combining hardware and software to provide a better
thread level control speculation. The approach isto let the compiler insert thread reachability information into the binaries. We introduced three
types of information: fixed-successor, assert andreject. Using this information, the validation of
the thread prediction can be initiated earlier, reducing the penalty when a misprediction occurs.
Moreover, fixed-successor information is also useful for achieving higher prediction accuracy.
Our evaluation results showed that using fixedsuccessor information alone reduced the execution time by an average of 3.3%. Adding assert

6[4] Venkata Krishnan, Josep Torellas, A ChipMultiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers,Vol. 48, No. 9, Sep. 1999
[5] Simonjit Dutta, Manoj Franklin, Control Flow
Prediction Schemes for Wide- Issue Superscalar
Processor, IEEE Transactions on Parallel andDistributed System, Vol 10, No.4, Apr. 1999
[6] Quinn Jacobson, Steve Bennett, Nikhil Sharma,
J.E. Smith, Control Flow Speculation on Multiscalar Processors, Proceedings of the 3rd HPCA,
pp.218-229, Feb. 1997
[7] Lance Hammond, Benedict A.Hubbert, MichaelSiu, Manokar K.Prabhu, Michael Chen, Kunle
Olukotun, The Stanford Hydra CMP, IEEE Micro, pp.71-84, Dec. 2000
[8] Niko D. Barli, Hiroshi Mine, Shuichi Sakai, andHidehiko Tanaka, A Thread Partitioning Algorithm using Structural Analysis, 情報処理学会 計算機アーキテクチャ研究会, ARC-2000-139 Vol. 2000,
No. 24, pp.37-42, Aug 2000
[9] Haitham Akkary, Michael A. Driscoll, A Dynamic Multithreading Architecture, Proceedingsof the 31st MICRO, pp.226-236, Nov. 1998
[10] Pedro Marcuello, Jordi Tubella, Antonio Gonzalez, Value Prediction of Speculative Multithreaded
Architecture, Proceedings of the 32nd MICRO,
pp.230-237, Nov. 1999