Dynamic Thread Extension forSpeculative Multithreading Architectures
Niko Demus Barli,† Daisuke Tashiro, †† Shuichi Sakai†and Hidehiko Tanaka†
To reduce the eﬀect of thread overheads when executing small threads in speculative multithreading architectures, we propose a mechanism called Dynamic Thread Extension. Thismechanism allows the hardware to dynamically combine two or more consecutive threads andtreat them as a single thread. By having the compiler to estimate the size of threads, thismechanism can be implemented with minimal hardware support. Simulation results showthat more an average of 13% performance improvement can be achieved.

to the compiler, we show that Dynamic Thread
Extension mechanism can be implemented withsimple hardware while still achieving its purpose
to reduce the eﬀect of thread overheads.
The rest of this paper is organized as follows.
Section 2 describes the baseline architecture andthread partitioning method used in this work.
Section 3 investigates the eﬀect of thread overheads and discusses a number of alternatives toreduce this eﬀect. Section 4 describes the idea
and implementation of Dynamic Thread Extension. Section 5 shows the evaluation results. Finally, section 6 concludes this paper.

1. Introduction
Speculative Multithreading has been employed in a number of microprocessor architectures to accelerate the execution of single
threaded applications [1–7]. These architectures
partition a single threaded program into threads
either statically or dynamically. These threads
are not necessarily independent, but may include some sort of control or data dependencies. It has been shown that considerable performance improvement can be achieved by executing these threads speculatively.
There are many challenges in designing a wellbalanced speculative multithreading architecture. This paper is intended to deal with oneof the design problems: how to reduce the effect of thread overheads in speculative multithreaded execution. We ﬁrst verify the fact that
there are many small threads created during a
speculative multithreaded execution, thus introducing large overhead eﬀect. It will be shownthat the performance degradation due to thisoverhead eﬀect may not be easily solved using
software approaches alone. Consequently, wechoose to combine both hardware and software
approaches and propose an eﬀective mechanism
called Dynamic Thread Extension.
Dynamic Thread Extension dynamically combines two or more statically deﬁned threads toform a larger thread, thus reducing the number of small threads executed. Compiler is responsible to estimate the size of these threads.
This information is used by the hardware to decide whether it should extend the execution of athread or not. By shifting some functionalities

2. Methodology
2.1 Baseline Architecture
Thread Control Unit

PU 0

PU 1

PU 2

PU 3

Reg

Reg

Reg

Reg

Spec
Buf

Spec
Buf

Spec
Buf

Spec
Buf

MemoryFig. 1 Baseline Architecture

For the rest of this paper, we assume a baseline processor shown in ﬁgure 1. The processor is a Chip Multiprocessor (CMP), consistingof a thread control unit, four processing units,
and a memory system. Thread control unit
is responsible for resolving inter-thread control
dependencies and scheduling threads into PUs.
We assume a perfect next-thread prediction, i.e.
the thread control unit always predicts successor threads correctly.

† Graduate School of Information Science and Technology, The University of Tokyo†† Graduate School of Engineering, The University of
Tokyo

1

Table 1 Baseline Architecture Parameters
No. of PUs
4 Processing UnitsPU
6-stage out-of-order superscalarparameters
4 functional units
2 load/store units
4-instruction fetch width
64-entry instruction window
32-entry speculative buﬀer
Inst. Latency 2 cycles for Load/Store
1 cycle for other instruction
Delays1 cycle thread start/stop ovh.
1 cycle communication delay
1 cycle restart ovh
Idealized
Perfect memory
conditions
Perfect next thread prediction

3. Thread Overheads
3.1 Reducing Thread Overheads Eﬀect
Many eﬀorts have been done to reduce execution penalties originating from data misspeculation, control misspeculation, and synchronization/communication latency [8–11]. However, little attention has been paid to performance degradation caused by thread overheads.
This problem arises when there are many small
threads created during the execution. This paper focuses on this problem and oﬀers a solution
to reduce the eﬀect of these overheads.
In general, thread overheads can be categorized into:• thread start overhead: time required toschedule a thread into a processing unit
• pipeline ﬁll overhead: time required fora processing unit to ﬁll its pipeline before it
can execute any instructions in the thread• pipeline drain overhead: time required
for a processing unit to retire remaining instructions left in the pipeline after it ﬁnishedexecuting a thread• thread stop overhead: time required tostop the execution of a thread and commit
its speculative state to architectural state

Each processing unit (PU) in this architecture is a 6-stage out-of-order superscalar core.
Two-cycle execution latency is assumed for
Load/Store instructions, whereas one-cycle execution latency is assumed for all other instructions. Table 1 summarizes the other parameters
used in our baseline architecture.
To support speculative multithreaded execution, a register communication mechanism isassumed. Compiler statically analyzes a program for inter-thread register dependencies andinserts communication primitives into the program. Load instructions are speculatively executed. A mechanism to detect memory dependency violation is assumed. In case a violation
occurs, the violating threads are squashed andrestarted. Finally, each PU has a 32-entry speculative buﬀer to temporarily hold data speculatively written to memory.

For our baseline processor, the thread startand stop overhead are set to one cycle each.
The sum of pipeline ﬁll and drain overhead isapproximately equal to the number of pipeline
stages, which is six in our baseline processor.
Thus, in our case, the total overhead is approximately eight cycles.
Since the trend in microprocessor design istoward deeper pipeline and more complex design, it is very unlikely that these overheads canbe reduced. Thus, rather than trying reduce
the overheads themselves, we should ﬁnd a way
to reduce their eﬀect to processor performance.
There are a number of alternatives available:• Use simpler narrow-issue cores as PUs andincrease the number of the PUs. This approach has some drawbacks. First, simpler
narrow-issue cores will give inferior performance when used in traditional execution(single threaded execution). Second, thehardware cost and complexity for managing
speculative multithreaded execution tend toincrease when more PUs added.
• Introduce a mechanism to let a processing
unit start fetching another thread as soon
as there is no more instruction to be fetchedfrom the current thread. This approach can

2.2 Thread Partitioning Method
A program is statically analyzed and partitioned into threads. We deﬁne thread as a connected subgraph of a control ﬂow graph withexactly one entry point. Overlapped regions
shared by two or more threads may not exist. A thread partitioning algorithm proposedin [12] is used to put thread boundaries in function invocations and innermost loop iterations.
For the remaining parts of the program, threadboundaries are put at places so that the resulting threads have a maximum size.
For clarity, it should be noted that when usedin diﬀerent contexts, the term thread may havediﬀerent semantics. For the rest of paper, we
will use the term static thread to refer to a portion of control ﬂow graph deﬁned as thread atcompile time, and a plain thread to refer to a
stream of instructions from a static thread actually executed by a PU.

2

shown in this evaluation do not necessarily haveimportant meanings, the evaluation results imply that size of threads executed should be adjusted to a range that compromises the tradeoﬀ of thread overheads and inter-thread data
dependency. Dynamic Thread Extension, described in the following section, oﬀers the ﬂexibility to fulﬁll this requirement.

eﬀectively hide the eﬀect of thread overheads by overlapping the execution processof the two threads. However, it may introduce complexity and considerably increase
the requirements of hardware support.
• Form larger threads so that the proportionof overhead to the actual execution cycles
decreases. However, we may not freely create large threads since large threads generally impose strong inter-thread data dependencies.
Although the second approach also looks
promising, we choose to employ the third approach. As it will be shown later, this approach
can be implemented with simple hardware support while still giving substantial improvementin performance.

4. Dynamic Thread Extension
4.1 Basic Idea
The idea behind DTE is to combine two or
more threads to form a larger thread whose size
is within a range that compromises the trade-oﬀ
of thread overheads and inter-thread data dependency. From preliminary evaluation result
shown in ﬁgure 2, this range is approximately
between 30-60 instructions for our baseline processor.

3.2 Thread Size and Performance
We conducted a preliminary evaluation to
give a more concrete understanding on the relation between thread size and the performanceachieved by speculative multithreaded execution. It is also intended to verify the trade-oﬀ
between decreasing overhead eﬀect and increasing data dependency when the threads are madelarger.

overhead

PU0

A

PU1

PU2

PU3

PU0

A

PU1

PU2

PU3

A
B

C
C

B

D

E

B

G

D
F
E

H
F
G

H

(a)
Threads inprogram ordert(b)Conventional
Execution

H

t

(c)
Dynamic Thread
Extension enabled

Fig. 3 Basic idea of Dynamic Thread Extension

Figure 3 illustrates the idea of DTE. Suppose
we are executing threads A to H in a sequence
shown in ﬁgure(a). Conventional speculative
multithreading architecture schedules thread A
to PU0, B to PU1, and so on, as shown in ﬁgure(b). If the size of these threads is small,thread overheads will take a signiﬁcant portionof execution time. In contrast, DTE combinesconsecutive threads, thread A and thread B,
thread C and D, and so on, if it founds thethreads are small in size. The combined threads
are then executed as single chunks in each PU,
as shown in ﬁgure(c). In this way, the portionof overheads to execution time can be reduced
and the overall performance of speculative multithreaded executed can be improved.

Fig. 2 Normalized performance with ﬁxed thread size

Figure 2 shows normalized performance whena hypothetical thread partition algorithm which
can create threads with a ﬁxed size is assumed.
Eight applications from Spec95int are used inthis evaluation. As the thread size was varied from 10 to 50 instructions, the performance
showed a signiﬁcant improvement due to the decreasing thread overhead eﬀect. However, when
the thread size was further increased, the performance started to degrade. At this point,
the limitation imposed by inter-thread data dependency governed the performance achieved byspeculative multithreaded execution.
Although the absolute thread size values

4.2 Why Dynamic Thread Extension ?
Figure 4 shows the distribution of number of
instructions, categorized by the size of thread inwhich the instructions were executed. The partitioning method employed in this data is as described in 2.2. According to this ﬁgure, 56% of

3Function inlining and loop unrolling may help
reduce the number of small threads of type (1)and (2). However, since for most applications
these types of threads occupy only small portion of the total threads, we cannot expect adequate performance improvement by employing
these techniques alone. Thus, a more universal
approach is required. Since DTE is theoreticallyapplicable to all types of threads, we may expect
more performance improvement from it.

Fig. 4 Distribution of number of instructions executed
within a thread whose size between n − (n + 10)
instructions, where n is varied between 0 − 110

4.3 Implementation
DTE may be implemented completely in the
hardware. However, since it is preferable to keep
the hardware simple, we moved some functionalities into the software. The implementation is
described as follows.
Compiler support
For each statically deﬁned thread the compiler
estimates its size (the number of instructions thethread will contain when executed). We employed a simple estimation method that takes
the average size of all possible paths between
the entry point and exit points of the thread.
After estimating the size, the compiler decide
whether the thread should be marked extendable
or not-extendable. If the estimated size is lessthan or equal to a preset threshold, the thread
is marked extendable. Otherwise, it is marked
not-extendable. We used two types of thread
start instruction, thrstart ext and thrstart noext,
to distinguish extendable from not-extendable
threads.

Fig. 5 Distribution of number of instructions, executed in threads whose size is less than 30 instructions

the executed instructions are belong to threads
whose size is less than 30 instructions. It can be
imagined that since the threads are very small,the performance suﬀers severely from the eﬀectof thread overheads. Thus, a mechanism suchas DTE is required to improve this situation.
A question of, whether conventional compiler
techniques such as function inlining and loop
unrolling are suﬃcient to do the task of creating larger threads, may arise. Function inlining reduces the number of small threads comprising functions as a whole, whereas loop unrolling is useful to enlarge the threads createdfrom loop iterations. Our investigations however suggested that these techniques may not
be suﬃcient. Figure 5 shows the distributionof number of instructions, executed in threads
whose size is less than 30 instructions. These
threads are classiﬁed into:(1) function threads: threads that contains thewhole function(2) loop iteration threads: threads that are created from innermost loop iterations (one iteration per thread)(3) other type of threads: threads that are
not classiﬁed either to (1) or (2), generated
mostly due to the restriction that threadboundaries should always be put at function
calls

Hardware support
Hardware to support DTE is implemented ineach PU of the CMP. The hardware is responsible to decide whether the execution of an extendable thread should be extended to the successor thread, or be left unextended. We prepare a counter to count how many dynamic instructions has been fetched (not including instructions from mispredicted control path or violating execution). We also prepare an extended
flag bit that when asserted indicates that the execution of a thread will be extended.
Figure 6 shows the state diagram of DTE
hardware. The state Normal corresponds tothe state when the extended flag is cleared,
whereas the state Extended corresponds to thestate when extended flag is asserted. The instruction counter is assumed to be reset to zero
before an execution starts.
When the execution of a thread starts and theﬁrst instruction in the thread is a thrstart noext
then the state changes to Normal. In this case,4timate the thread size and the threshold value
used by the compiler is less than or equal to
the threshold value used by the hardware, DTE
guarantees that the size of chunk of instructions the processor executed as a single thread
is more than the hardware threshold. However,since the estimation cannot be 100% accurate,
we could expect that there will exist a numberof threads whose size is less than or equal to thehardware threshold.

Start
thrstart_ext
counter=0

thrstart_noext
counter=0

Normalthrstart_noext
counter=...
thrstart_ext
counter=...

thrstart_noext
counter=...
thrstart_ext
counter>threshold

Extended

thrstart_ext
counter<=threshold

5. EvaluationEnd

We conducted simulations to evaluate thebeneﬁt of DTE in speculative multithreaded execution. Considering the result of preliminary
evaluation already shown in ﬁgure 2, we set thecompiler threshold to 20 instruction, and the
hardware threshold to 30 instruction. We expected that larger portion of programs will be
executed in threads whose size is larger than 30
instructions, thus reducing the eﬀect of thread
overheads and increasing the achieved performance.

Fig. 6 State diagram of Dynamic Thread Extension
hardwarethe execution will terminate the next time itreaches any thread start instruction, either athrstart noext or a thrstart ext. The value of
instruction counter is ignored in both cases.
When the execution of a thread starts and theﬁrst instruction in the thread is a thrstart ext,
then the state changes to Extended. In this case,the execution of the thread will be extended toinclude at least the next one thread. It should
be noted that in this state, all register communication instructions will be ignored since theregister values may be redeﬁned when the execution is extended.
When in Extended state, there are three possible state transitions of DTE hardware:• If the next thread start instruction reachedis a thrstart noext, then the state changes
to Normal and the execution will terminate
the next time it reaches any thread start
instruction.
• If the next thread start instruction reachedis a thrstart ext and the value of instruction
counter is greater than a preset threshold,then the state changes to Normal and theexecution will terminate the next time itreaches any thread start instruction.
• If the next thread start instruction reachedis a thrstart ext and the value of instruction counter is less than or equal to thepreset threshold, then the state remains unchanged. The execution will be further extended.

Fig. 7 Performance improvement by Dynamic Thread
Extension

Figure 7 shows the results of simulations.
When DTE is employed, all applications showed
performance improvements, ranging from 8.5%
to 16%, or 13% in average. Figure 8 shows
the distribution of number of instructions executed within a thread whose size is within thespeciﬁed range, when DTE is disabled and enabled. It becomes clear that DTE succeeded toreduce the fraction of program executed in small
threads, thus, shifting the distribution graph to
the right. The fraction of program executed inthreads whose size is less than 30 instruction,for example, is reduced from 56% to 15%.
Our evaluation results shown above, veriﬁes
that DTE is an eﬀective mechanism for reducing the number of small threads, thus reducing

As can be imagined from the above explanation, DTE can be implemented using a very simple hardware. Moreover, it requires no inter-PU
communication. Thus, it is very unlikely that it
becomes the bottleneck of the processor’s critical path.
Assuming that the compiler can accurately es-

5Acknowledgement
This work is partially supported by Grant-inAid for Scientiﬁc Research, Ministry of Education, Culture, Sports, Science and Technology,
Japan, Basic Research No.(B)(2)50291290.
References[1] G.S. Sohi, S.E. Breach, and T. N. Vijaykumar,
Multiscalar Processors, Proc. 22nd ISCA, pp.
414-425, 1995
[2] L. Hammond, M. Willey, and K. Olukotun,
Data Speculation Support for a Chip Multiprocessor, Proc. 8th ASPLOS, pp. 58-69, San JoseCA, 1998[3] 小林 良太郎, 岩田 充晃, 安藤 秀樹, 島田 俊夫,
非数値計算プログラムのスレッド間命令レベル並列を利用するプロセッサ・アーキテクチャSKY,
Proc. JSPP’98, pp.87-94, June 1998
[4] 鳥居 淳, 近藤 真己, 本村 真人, 西 直樹, 小長
谷 明彦, On Chip Multiprocessor 指向 制御並列アーキテクチャMUSCAT の提案, Proc. JSPP’97,
pp.229-236, 1997[5] V. Krishnan, J. Torellas, A Chip-Multiprocessor
Architecture with Speculative Multithreading,IEEE Transactions on Computers, Vol. 48, No.
9, Sept 1999
[6] A. Gonzalez and P. Marcuello, Speculative
Multithreaded Processors, Proc. 12th International Conference on Supercomputing, July
1998[7] H. Akkary, M.A. Driscoll, A Dynamic Multithreading Architecture, Proc. 31st MICRO,
Nov-Dec 1998
[8] T.N. Vijaykumar and G.S. Sohi, Task Selection for a Multiscalar Processor, Proc. 31st MICRO, Nov-Dec 1998
[9] 岩田 充晃, 小林 良太郎, 安藤 秀樹, 島田 俊夫, 制
御等価を利用したスレッド分割技法, 97-ARC-128
pp.127-132, Mar 1998
[10] 堺 淳嗣, 鳥居 淳, 近藤 真己, 市川 成浩, 大俣 仁美, 西 直樹, 枝広 正人, 制御並列アーキテクチャ
向け自動並列化コンパイラ手法, Proc. JSPP’98,
pp.383-390, 1998[11] R. Kobayashi, M. Iwata, Y. Ogawa, H. Ando,and T. Shimada, An On-Chip Multiprocessor
Architecture with a Non-Blocking Synchronization Mechanism, Proc. 25th EUROMICRO,
pp.432-440, Sept 1999.
[12] N.D. Barli, H. Mine, S. Sakai, and H. Tanaka,
A Thread Partitioning Algorithm using Structural Analysis, ARC-2000-139 Vol. 2000, No. 24,
pp. 37-42, Aug 2000
[13] C. Iwama, N.D. Barli, S. Sakai, and H. Tanaka,
Improving Conditional Branch Prediction on
Speculative Multithreading Architectures, Proc.
JSPP 2001, pp. 165-172, Jun 2001

Fig. 8 Distribution of number of instructions executed
within a thread whose size between n − (n + 10)
instructions, where n is varied between 0 − 110,with and without using DTE

the eﬀect of thread overheads. It should also
be noted that the potential of performance improvement by DTE is actually larger than what
was shown above. There is a limitation in ourcurrent register communication scheme, i.e. a
register value deﬁned in an Extended state, may
be sent to the consumer PU only after the execution enters Normal state, even though the register is never redeﬁned any time later. In case an
ideal register communication mechanism is assumed, DTE gives performance improvements
between 15% to 37%.
6. Concluding Remarks
This paper investigated thread overheads
problem, and veriﬁed its impact on the performance of speculative multithreaded execution. We investigated a number of possible solutions to the problem, and proposed a mechanism called Dynamic Thread Extension (DTE).
By moving some functionalities to the compiler,
we showed that DTE can be implemented using
a simple hardware support. Despite the simplicity, our evalution results showed that DTE
helps the processor achieving a performance improvement of 13% in average.
However, there are still a number of reﬁnements needed to further improve the eﬀectiveness of DTE. We plan to investigate the following issues:• Register communication mechanism thatcan more eﬀectively exploit the potential of
DTE.
• Incorporating data dependence information
for the compiler to decide whether a static
thread should be marked extendable or not.
• Hardware reﬁnement, for example rather
than using a counter of number of fetched
instructions, the hardware may should haveto use a counter of execution cycles.
• The interaction between DTE and nextthread prediction mechanism.

6