A Thread Partitioning Algorithm
using Structural Analysis
Niko Demus Barli,† Hiroshi Mine,† Shuichi Sakai†and Hidehiko Tanaka†Speculative Multithreading has been proposed as a method to increase performance of asingle thread program on a Chip Multiprocessor. To achieve optimal performance, however, aneﬀective thread partitioning algorithm is required. This paper proposes a thread partitioning
algorithm using Structural Analysis, and describes design rationale behind the algorithm.
Preliminary evaluation shows that a moderate performance can be achieved with a simple
heuristic. However, further reﬁnement is needed in order to achieve more ﬂexibility andbetter performance.

pendent, but may include some sort of dependences (control, register or memory). The processors aggressively execute these speculative
threads, and take necessary action when thespeculative execution failed.
To eﬀectively utilize CMP resources andachieve high performance with speculative multithreading, an eﬀective thread partitioning
mechanism is required. In this paper, we propose an algorithm to partition a program intoa speculative threads. The algorithm staticallyanalyze control ﬂowgraph of a program and partition the ﬂowgraph into subgraphs, which wewill call threads. Observing that it is diﬃcult toﬁnd an algorithm which is optimal to all classesof applications, we design the algorithm to be
ﬂexible. It uses structural analysis7)8) to ﬁnd
thread candidates, and uses heuristics to pickan optimal combination of threads. Structural
analysis provides a common framework, so that
diﬀerent type of heuristics and thread selection
methods can be applied selectively.
The rest of this paper is organized as follows.
Section 2 describes related work on thread partitioning algorithm. Section 3 describes structural analysis and how we use the result ofstructural analysis as a common framework
for thread selection mechanism. Section 4 describes current implementation of the algorithm
and shows preliminary evaluation results. Finally, section 5 concludes this paper and describes future works of our research.

1. Introduction
Chip Multiprocessor (CMP) approach has
emerged as a promising approach for future
processor architecture. CMP is constructedfrom several relatively simple processing units,each is capable to maintain single thread control. Compared to centralized approach suchas found in superscalar, CMP has several advantages. It oﬀers an eﬀective way to utilize
available silicon space, and at the same time,
simplicity in design eases the requirement forvalidation phase, which has been becoming themost time consuming phase in processor design. CMP processor can naturally exploit parallelism from multithread programs or in a multiprogram workload, and well ﬁtted to the requirements for server processors.
Despite the advantages described above, however, for CMP approach to be fully accepted,
it must also be able to give high performance
when executing single thread (sequential) programs. Sequential applications constitute a major portion of software today, so that it is essential for CMP to be able to execute these programs at competitive speed.
To accelerate performance of single thread applications, Speculative Multithreading has been
proposed in some CMP architectures2)3)4)5)6) .
These architectures partition a program intothreads and speculatively execute them in parallel. These threads are not necessarily inde-2. Related Works† Graduate School of Engineering, University ofTokyo

Many CMP architectures which support some1

Second, we need some ﬂexibility to choose
which thread selection method to use for a particular class of application. Performance gainedby speculative thread execution is largely inﬂuenced by characteristics of application. Multimedia application, for example tends to havelarge parallelism and can be exploit with large
threads. Language processing programs, on theother hand, tends to have little parallelism andmay suﬀer from misspeculation if partitioned
into large threads. While we can optimize thealgorithm, to meet requirements of one class ofapplication, the result will likely not always besuitable for all other types of applications.
Another consideration is harmony with currently available analysis algorithms. Data dependence analysis such as live register analysis,
will be used extensively inside the algorithm.
These types of analysis have already reached amatured point, so that it is preferable if thepartitioning algorithm can use them directly.
Considering the above points, we propose apartitioning algorithm using structural analysis. The algorithm mainly consists of 2 phases.
First, the algorithm analyze program’s control
ﬂowgraph using structural analysis and ﬁndthread candidates. This phase reduce the number of candidates signiﬁcantly, compare to abrute approach. Thread candidates are in theform of extended basic block with single entry
node. This will make data dependence analysis easier since many analysis algorithms aredirectly applicable.
The next phase of algorithm is applying
heuristics to select optimal thread combination.
We will show that structural analysis provide acommon framework, on which we can apply different type of heuristics in a ﬂexible way. This
will allow us to select optimal approach for different class of applications.

sorts of speculative thread executions have been
proposed. Each architecture has its own way
to partition a single thread program into speculative threads. Multiscalar architecture use
heuristics based on task size, control dependence and data dependence to statically traverse program’s CFG and form speculativethreads9) . SKY architecture employs thread
model that guarantees no control dependence
between threads. A combination of threads
which has maximal estimated gain is selected.
The gain estimation uses fork distance and data
dependence characteristics as parameters10) .
Hydra and DMT (Dynamic Multithreading) architecture spawn speculative threads on function invocations or loop iterations. Programmer or compiler helps the processor by marking functions or loops on which the processor
will spawn speculative threads2)12) . MUSCAT
architecture does register dependence analysis,and puts fork instruction where the register dependences between current and next thread areresolved11) .
Our proposal for thread partitioning algorithm diﬀers from previously proposed methods
in that we use structural analysis to ﬁnd thread
candidates. It also diﬀers in that we use a common framework provided by structural analysis
to apply diﬀerent kind of heuristics and thread
selection algorithms, which will be selected tosuit the target application the best.
3. Thread Partitioning using Structural Analysis
To run an application on a speculative multithreading architecture, we ﬁrst need to identify
threads. This may be achieved in software by
performing a compilation step, or in hardwarethat support dynamic thread identiﬁcation. To
keep the CMP hardware simple, we choose theﬁrst approach and propose a thread partitioning algorithm described below.

3.2 Thread Model
We deﬁne thread as a connected subgraph of astatic control ﬂowgraph with single entry node.
A thread can be described as G <Nodes, Edges,entry> where Nodes, Edges and entry denoteset of nodes included in the thread, set of edges
included in the thread, and entry node of thethread, respectively.
According to this deﬁnition, a thread may
comprise a basic block, multiple basic blocks,

3.1 Design Considerations
There are some important points to be considered when designing the algorithm. First,
the algorithm should not take unreasonable
long time. A brute eﬀort to ﬁnd all possibilitesof thread partitioning, for example, will resultin an algorithm that requires a huge amount oftime to do the analysis.

2

as improper region.
Structural analysis proceeds by examining
control ﬂow graph’s nodes in postorder and try
to ﬁnd instances of the various region types described above. Postorder traversal is a traversal
in which each node is processed after its successors. For example, if node A have two successors, B and C, in postorder traversal node A
will not be processed until node B and C areprocessed.
After identifying a region of nodes, structural analysis will collapse and replace the region with an abstract node, reconstructing ﬂowgraph for further analysis. This steps are repeated until the entire ﬂowgraph collapsed intoa single node.

loop body, entire loop, or entire function. Also,logically, a thread may also comprise one ormore threads. This hierarchical property of ourthread model will be exploited when we use
structural analysis described in the next subsection.
For our thread model, we allow control anddata dependence (both register and memory)
between threads. We assume a CMP hardware
similar to Multiscalar3) to execute speculative
threads generated by our algorithm.
3.3 Structural Analysis
Structural analysis is originally proposed bySharir7) to make syntax directed method of
data-ﬂow analysis applicable to lower level intermediate code. It can discover control ﬂow
structures from arbitrary ﬂow graph. Thus, forexample, it can take up a loop and discover thatit has a form of a while or repeat/self loop, eventhough there is no syntactical information available.
One important concept in structural analysis
is that every region it identiﬁes has exactly one
entry point. The deﬁnition of region used instructural analysis is identical to the deﬁnition
we used to deﬁne our thread model, so that
we are able to directly treat regions found bystructural analysis as thread candidates.
Figure 1 and 2 shows typical acyclic controlstructures (regions which do not contain anyback edges) and cyclic control structures (regions which contain back edges), respectively,that can be recognized by structural analysis.
The regions shown here represent the most common control structure found in program written
in C language.
Proper region shown in Figure 1 is an arbitrary acyclic structure that failed to be identiﬁed by other simple acyclic cases. Since a control ﬂow graph of program can take any possible
form, it is diﬃcult to set the algorithm to recognize all the possibilities of control structures.
For this reason, the algorithm will recognize an
acyclic region as a proper region if the region
cannot be further reduced by any of the simple
acyclic cases. Similarly, natural loop shown inﬁgure 2 is a special case of cyclic region which
includes loop structure that is natural but cannot be further reduced. Loop that is not natural, such as the one in ﬁgure 2 will be identiﬁed

continuousblock

if-thenif-then-else

proper region

B1B1B1

B1
B2

B2

B2

B3

B2

B3
B4B5

B1
B2B3B4B5switch-caseFig. 1 Acyclic regions
self-loop

while-loop

natural-loop

improper-loop

B1

B1

B1

B1
B2

B2

B2B3Fig. 2 Cyclic regions

001

D1

E22C

35A

B

6466Fig. 3 Example of structural analysis

Figure 3 illustrates an example of structuralanalysis. Following the postorder traversal, ﬁrst
the analysis algorithm examines node 6 but fails
to ﬁnd any identiﬁable region. Next, it examines node 5 and ﬁnds a self-loop region. It3

step.
• Combination of the above two approaches.
Regardless of what type of approach used inapplying heuristic, the process of ﬁnding theright combination should guarantee that thecombination found covers the original control
ﬂow graph entirely. It must also guarantee that
there is no overlaps between threads. To fullﬁl this requirement, we deﬁned some rules thatmust be obeyed when identifying thread froma control tree. We call this rules Tree ColoringRules.
( 1 ) If node X is identiﬁed as a thread, thenall of X’s predecessors and all of X’s successors cannot exist as threads.
( 2 ) If node X is identiﬁed as not-a-thread (i.e.
there is no possibility that the node willbe identiﬁed as thread), then all of X’s
direct successors that have no successor
must be set as a thread.
( 3 ) Tree coloring is ﬁnished when all nodes
are checked (i.e. identiﬁed as thread or
as not-a-thread).

then collapses the region into node A and reconstructs the ﬂow graph. Successively, it ﬁnds
continuous-block region formed by node 3 and4, and collapses it into node B. In the samemanner, if-then-else region formed by node 2,A, and B, is identiﬁed and collapsed into nodeC. if-then region formed by node 0 and 1 is collapsed into node D. And lastly continuous-block
region formed by D, C, and 6, is collapsed into
node E.
As shown in the example above, structural
analysis gradually collapse a control ﬂow graphof a program into a single node. During the process, the algorithm constructs corresponding
control tree, which deﬁnes inclusion relation between identiﬁed regions. Since we treat the regions identiﬁed by structural analysis as thread
candidates, the control tree also deﬁnes inclusion relation between the thread candidates.
Figure 4 shows the control tree of our previous
example. From the ﬁgure we are able to identify
that, for example, thread candidate E, includes
thread candidates D, C, and 6 in it.

E0E

D

C

612B

A

4350E

DC

612B

A

4350D

C

612BA

435Fig. 5 Tree Coloring Rule 1

Fig. 4 Control Tree of previous example

3.4 Heuristics and Tree Coloring Rules
After identifying thread candidates using
structural analysis, we can then select a combination of threads that is the most likely togive best performance. In general, since it ishard for the compiler to know precisely what
will happen during execution (e.g. cache stall,branch misprediction, TLB miss etc), a compiler can at best predict and use some heuristic
approaches to ﬁnd the most promising threads
combination.
There are some possible ways to apply heuristics to our control tree.
• Find all combination possibilities, deﬁne aheuristic function and then apply the function to ﬁnd the “best” combination.
• Apply some types of heuristic in sequence,and identify one or more threads in eachE0EDC

612B

A

4350D

C

612B

A

435Fig. 6 Tree Coloring Rule 2

E0DC

612BA

435Fig. 7 Tree Coloring Rule 3

Figure 5, 6, and 7 illustrates an example ofTree Coloring Rules when applied to our control tree in ﬁgure 4. Suppose that node B is
identiﬁed as thread. Then following rule no. 1,4

all of B’s successors (3 and 4) and predecessors(C and E) cannot possibly exists as threads,
so that we put cross marks on them (ﬁgure 5).
Next, we discover that node 6 whose direct predecessor already marked as not-a-thread, has nosuccessor. Applying rule no. 2, we mark node
6 as a thread. In similar fashion, we also marknode 2 as a thread (ﬁgure 6). Suppose successively we identify node D and A as threads
and apply rule no.1, the resulted control tree isshown in ﬁgure 7. Following rule no. 3 then weknow that the process of ﬁnding threads combination is ﬁnished.

5IPC

4

Preliminary

1

Ideliazed
conditions

147.vorte x

134.pe rl

132.ijpe g130.li126.gcc

099.go129.compre s s0Fig. 8 Performance estimation

Figure 9 shows size distribution of threads
created with our algorithm. Except for ijpeg,
most of the threads created in each apllication
have size of less than 20 instructions. We foundthat the overall thread size is small then we expected. Small threads are not only sensitive toincreasing delay, but they also limit the potential of parallelism that may be exploited. For
example, a 4 PUs CMP running 4 threads of 10
instructions each, will have an eﬀective instruction window stretched for only 40 instructions,which is relatively small even when compared towindow size of currently available superscalar
processors.

Table 1 Trace simulation tool parameter100%

4 Processing Units
Out-of-Order Superscalar
4 functional units
2 load/store units
4 instruction fetch width
64 entry instruction window
1 cycle execution for all insts.
1 cycle thread spawn delay
1 cycle comm. latency
1 cycle restart delay
Perfect cache
Perfect branch prediction
Perfect speculative store buﬀer

80%> 100<= 100<= 50<= 20<= 1060%
40%

147.vortex

134.perl

132.ijpeg

130.li129.compress

0%126.gcc

20%099.go

Delay

CM P

2

We implemented the partitioning algorithm
as a binary annotation tool for Alpha-AXP binary. First, we build control-ﬂow graph fromthe binary, then we perform structural analysis
on function per function basis. For preliminaryevaluation, a simple heuristic is incorporated
to the annotation tool. The heuristic ﬁrst ﬁnd
innermost loops in control tree and mark theiterations as threads. Then, for the rest partsof control tree, it ﬁnds and marks the biggest
possible regions as threads.
Annotation informations generated by theanalysis are used to generate execution traces,
to be then analyzed by a CMP trace simulation
tool. Table 1 shows the simulation parameters.
Currently, we do not simulate pipeline in detail. Fetched instruction is executed as soon as
its dependences are resolved and there is execution unit available.

No of. PUs
PUparameters

SS-OOO

3124.m88ks imand

6124.m88ksim

4. Implementation
Evaluation

We simulated 8 programs from SPECint95
benchmark suites. The result is shown in ﬁgure 8. The evaluation shows a moderate performance, ranging from 3 to 5 IPC, can beachieved for each application. This is about
1.5 - 2 times of the IPC achieved by an outof-order superscalar processor which has same
capability as one PU (Processing Unit) of CMP.

Fig. 9 Thread size distribution

Investigating problem of small threads in ouralgorithm, we found that it is mainly causedby restrictions imposed by function calls. Since5our algorithm and thread model assume thatnew thread will always be created at function
boundaries, we must put thread partition whenever a function call encountered. This strictly
limits possible combination of threads, resulted
in many small threads created. There are however some possible solutions to the problem.
• Selectively inline functions so that bigger
threads, spanning accross function calls,can be created.
• Incorporate function calls recognition into
structural analysis, so that even when wemust put partition at function calls, there
is still enough freedom to create bigger
threads.
• Add some architectural features to prevent
performance degradation caused by small
threads. For example, the processor canbe made to switch from speculative multithreading mode to normal mode when
it executes parts of programs with small
threads.

References[1] Kunle Olukotun, Basem A. Nayfeh, Lance
Hammond, Ken Wilson and Kunyung Chang,
The Case for a Single Chip Multiprocessor,
Proceedings of the 7th International Symposium Architectural Support for Programming
Languages and Operating Systems (ASPLOSVII), Cambridge MA, October 1996
[2] Lance Hammond, Mark Willey, and Kunle
Olukotun, Data Speculation Support for a Chip
Multiprocessor, Proceedings of the 8th International Conference on Architectural Support forProgramming Languages and Operating Systems, pp. 58-69, San Jose CA, 1998
[3] Gurindar S. Sohi, Scott E. Breach, and T. N.
Vijaykumar, Multiscalar Processors, Proceedings of the 22nd Annual International Symposium on Computer Architecture, pp. 414-425,
1995[4] 小林 良太郎, 岩田 充晃, 安藤 秀樹, 島田 俊夫,
非数値計算プログラムのスレッド 間命令レベル並列を利用するプロセッサ・アーキテクチャSKY,
並列処理シンポジウム JSPP’98, pp.87-94, Jun
1998[5] 鳥居 淳, 近藤 真己, 本村 真人, 西 直樹, 小長谷 明彦, On Chip Multiprocessor 指向 制御並列アーキテクチャMUSCAT の提案, 並列処理シンポジウム JSPP’97, pp.229-236, 1997[6] Venkata Krishnan, Josep Torellas, A ChipMultiprocessor Architecture with Speculative
Multithreading, IEEE Transactions on Computers, Vol. 48, No. 9, September 1999
[7] Micha Sharir, Structural Analysis : A New Approach to Flow Analysis in Optimizing Compilers, Computer Languages, Vol. 5, Nos. 3/4,
1980, pp. 141-153[8] Steven S. Muchnick, Advanced Compiler Design and Implementation, Morgan Kauﬀmann,
1997[9] T.N. Vijaykumar and Gurindar S. Sohi, Task
Selection for a Multiscalar Processor, Proceedings of the 31st International Symposium on
Microarchitecture (MICRO-31), Nov-Dec 1998
[10] 岩田 充晃, 小林 良太郎, 安藤 秀樹, 島田 俊夫, 制御等価を利用したスレッド 分割技法, 情報処理学
会研究報告 97-ARC-128 pp.127-132, Mar 1998[11] 堺 淳嗣, 鳥居 淳, 近藤 真己, 市川 成浩, 大俣 仁美, 西 直樹, 枝広 正人, 制御並列アーキテクチャ向け自動並列化コンパイラ手法, 並列処理シンポ
ジウム JSPP’98, pp.383-390, 1998
[12] Haitham Akkary, Michael A. Driscoll, A Dynamic Multithreading Architecture, Proceedings of the 31st International Symposium on
Microarchitecture (MICRO-31), Nov-Dec 1998

5. Conclusion
We proposed an algorithm to partition a program into threads using structural analysis.
Observing that it is diﬃcult to ﬁnd an algorithm which is optimal to all classes of applications, we design the algorithm to be ﬂexible to
let diﬀerent types of thread selection heuristics
applicable. Structural analysis used in the algorithm, combined with Tree Coloring Rules,
provide a common framework for identifying
threads using diﬀerent types of heuristics.
Currently we develop the algorithm as a binary annotation tool targeted for Alpha-AXPbinaries. Simple heuristic to identify innermost
loop iterations is incorporated. Preliminary
evaluation shows that, for a given parameter,
moderate performance can be achieved. However, we also found that the restriction imposedby function calls, reduced freedom to create different combination of threads signiﬁcantly andresulted in many small threads created.
To cope with the problem, we plan to investigate solutions as described in previous section.
We also plan to develop and incorporate somemore sophisticated heuristics, involving controlﬂow and data-ﬂow analysis into our algorithm.

6