A Dual-Length Path-Based Predictor for Thread Prediction
Niko Demus Barli, Luong Dinh Hung, Hideyuki Miura,Shuichi Sakai and Hidehiko Tanaka
Graduate School of Information Science and Technology, The University of Tokyo.
7-3-1 Hongo Bunkyo-ku, Tokyo 113-8656, Japan{niko,hung,hide-m,sakai,tanaka}@mtl.t.u-tokyo.ac.jp

1

Introduction

Using pattern of recent branches outcomes has beena successful approach for achieving a high branch preIn speculative multithreading (SpMT) architectures diction accuracy [12,13]. Alternatively, a path-based apwhich exploit thread level parallelism from a sequential proach for branch correlation has also been proposed andprogram, predicting and spawning threads that follow shown to achieve a similar prediction accuracy [8]. In thea correct control ﬂow is a major performance factor. context of Multiscalar’s thread prediction, Jacobson et.
Strategies for this control speculation issue can be di- al. has shown that path-based approach achieves higher
vided into two approaches. The ﬁrst approach is to sup- prediction accuracy compared to the pattern-based apport a limited control speculation, in which threads may proach [4]. In this paper, we also base our thread preonly be spawn at speciﬁc points in the program. For ex- diction investigation on a path-based approach.
ample: loop iterations, function call and returns, or conMcFarling introduced the concept of combining diftrol equivalent points. This approach minimizes thread ferent branch predictors to form a hybrid predictor [6].
misprediction by only speculating at highly predictable Using hybrid predictors whose components have diﬀerplaces. The second approach is a more aggressive one,ent path history length has also been reported [3]. Thisin which threads are predicted and spawned as soon as
paper applies the concept of using diﬀerent path history
possible. This latter approach bears a larger potential length components of hybrid predictors in thread prefor performance improvement, given that the thread pre- dictions, and further explores the possibility of reducing
dictor is suﬃciently accurate.
aliasing by manipulating predictor’s updating policy.
This paper targets architectures that use the latter
While hybrid predictors dynamically select one of theapproach. It ﬁrst studies the predictability of thread ad- components for each prediction, branch classiﬁcation [1],dresses using a dynamic path-based predictor. The re- predictor with elastic history buﬀer [11], and variable
sults show that, in an alias free situation, a high predic- length path-based branch prediction [10], use execution
tion accuracy can be achieved by including suﬃciently proﬁle for classifying and associating each static branchlong path information. However, the requirements for to an optimal prediction mechanism.
prediction table entries are also increasing almost exponentially when longer path information included. For 3Methodology
a ﬁnite size table, there are cases when a longer path,due to capacity aliasing, leads to a severely deteriorated Throughout this paper, we employed a static method topartition a sequential program into threads. A threadaccuracy.
To overcome the problem, this paper introduces a is a connected subgraph of the program’s control ﬂow
dual-length path-based prediction technique. We com- graph with exactly one entry point. Overlapped regions
bine two path-based predictors: one predictor is indexed shared by two or more threads may not exist. Threadusing a shorter path information, while the other predic- boundaries were put at function invocations, returns,
tor is indexed using a longer path information. A selec- and at innermost loop iterations by a compiler. For thetion table is added to dynamically select which predic- remaining parts of the program, thread boundaries weretor’s outcome to use. The rationale behind this hybrid placed so that the resulting threads have a maximum
technique is to have the shorter path predictor, which size. For Spec95int applications, the resulting threads
has lower capacity requirements, to redeem the situa- had an average dynamic size ranging from 14 to 21 intion when the longer path predictor suﬀers from a severe structions.
Simulations were conducted using traces generated
capacity aliasing. Furthermore, by manipulating predictor’s table update policy, threads that can be accurately by a speculative multithreading simulator. The benchpredicted by one predictor can be ﬁltered out from con- mark used in simulations are eight applications fromtaminating the other predictor. Simulation results show Spec95int suite. Input for each application was modithat the combined eﬀect signiﬁcantly improves the ac- ﬁed to keep the trace size within reasonable size (100M 200M instructions). When presenting simulation results,
curacy of thread prediction.
we will use harmonic mean for measuring the “average”
of prediction accuracy.
2 Related Work
We assumed an idealized predictor update timing:
In general, thread prediction is very similar to branch before predicting a succeeding thread, the predictor isprediction. There are diﬀerences in that there is basi- properly updated using the most recent thread informacally no concept of taken/not-taken and that the infor- tion. When a thread exited from a return instruction, we
mation of intra-thread branches is unavailable in thread excluded the succeeding thread from the trace. Threadsprediction. Nevertheless, the wealth idea of branch cor- that follow a thread exiting from a return instruction
relation, combining predictors, aliasing reduction, and is best predicted using a return address stack, which isother branch prediction techniques can be borrowed.
however beyond the scope of this paper.
1130.li

Direct-mapped tagless tables were used during experiments. For an n-length path-based predictor table,
we concatenate address bits from the latest n threads,
and fold (using bitwise XOR) the concatenated bits toform index for the table. The notation is, for example,
12-8-8-8|3|: we concatenate 12-bit address from the current thread, 8-bit address from the next three threads,
and fold the resulting bits by three, generating a 12-bit
index.

finite099.gofiniteideal

809570]]% 90[etar85ith%[ 60etar 50
ith40

80

30207512345678

9 10 11 12 13 14 15 16 17 18 19 20

1234

path length

Dual-Length Path-Based Predictor
4.2 Combining Predictors

4.1

Predictability

Predictability
100

harmean
099.go124.m88ksim
126.gcc
129.compress
130.li
132.ijpeg
134.perl
147.vortex

95

75

678

9 10 11 12 13 14 15 16 17 18 19 20
path length

Predictability study in the previous section has indicatedthat, for a ﬁnite size table the optimal path length varies
following footprint characteristics of the program. The
penalty incurred when missing the optimal point is not
negligible. Thus, it is diﬃcult to optimize a ﬁxed singlelength predictor to cover a wide range of applications.
This observation leads us to the idea of combining
two path-based predictors with diﬀerent path length. A
selection table indexed by the address of current thread
is added. This table contains 3-bit saturating counterswith the counter’s MSB bit serves as a selection bit.
When one of the predictor predicted correctly and theother predictor missed the prediction, the counter is incremented or decremented accordingly. The logic behind this hybrid approach is to prepare both a longer
path (high-predictability high-aliasing) predictor and ashorter path (low-predictability low-aliasing) predictor.
Applications that can take advantage of a longer path
length can be predicted with high accuracy, while theones suﬀering from severe aliasing may still be rescued.

Fig. 1 shows prediction accuracy achieved using pathbased approach, given an alias free table and completethread address information for the path. High prediction accuracy is theoretically achievable if suﬃciently
long path information is incorporated. However, when
we lengthen the path, the number of table entries required for prediction is also increasing almost exponentially (ﬁg. 2). For three applications of Spec95int, usinga path length of four requires more than 10k entries.
Assuming that each entry holds a 32-bit address, a 4kentry table has already occupied 32-kB of space. Thus,
although the predictability is high, limitation on tablesize may restrict the ﬁnal accuracy achieved.

90%(eta 85Rit
H 80

5Figure 3: Accuracy for ﬁnite size table4)

ideal

90

100

70
123456789101112131415161718

1920

4.3

path length

Figure 1: Predictability using path information
Table Size

1.E+07099.go124.m88ksim
126.gcc
129.compress
130.li
132.ijpeg
134.perl
147.vortex

1.E+06sie 1.E+05
rtnE
f 1.E+04o.
oN1.E+03
1.E+02

1.E+0112345678910111213141516171819

Reducing AliasingAliasing, speciﬁcally capacity aliasing, is the origin of
the problem that prevents the path-based predictor fromachieving higher prediction accuracy. While combining
predictors of diﬀerent path length helps to adaptively adjust the prediction to its optimal performance, anotherpossible approach to increase prediction accuracy is toreduce the aliasing itself.
A number of dealiased branch predictors have been
proposed in the past. Skewed predictor [7] uses majority vote from odd number of component predictors
to produce ﬁnal prediction. This predictor exploits thecharacteristics that in a lightly aliased situation, if anentry in one predictor is aliased, there is little possibility that the other tables are also aliased. Agree [9] andBimode [5] predictor avoid destructive aliasing by trying
to store identical prediction bits in the same table. Filter predictor [2] ﬁlters highly biased branches and uses
BTB instead of PHT to predict these branches, thus,
reducing aliasing in the PHT.
We explored the possibility of reducing aliasing in thehybrid predictor by manipulating prediction table update policy. In the original hybrid predictor approach,both component predictors are always checked for prediction miss and updated when a miss occured. However, for branches that can be predicted correctly in one
predictor, updating the other table introduces unnecessary contamination. To reduce this contamination, we20

path length

Figure 2: No. of entries used in prediction table
For a ﬁnite size table, the accuracy can be considered
as a function of path length and application’s footprint.
While longer path is advantageous for small applications,severe capacity aliasing may occur in large applications.
Fig. 3 shows prediction accuracy for two representative
applications using a 4k-entry table. For n-th threadin the path m bits of address is concatenated, wherem=max(12-2n,4). The concatenating result is folded asneeded to form a 12-bit index. The ﬁgure shows that,
although in li lengthening the path from one to four increased the prediction accuracy by 11%, in case of go, it
decreased the accuracy by 7.5%.
2

investigated the following two update policies in addition to the original update policy (we call the original
policy as Hybrid-Always).

Fig. 5 shows the average hit rate when prediction table size varied from 256 to 16k entries. The eﬀect ofaliasing reduction, especially in Hybrid-Lazy predictor, is increasing for smaller table size. When the table
gets larger, the advantages of hybrid approach over single scheme predictor with path length of four is diminishing. At this point, we should consider longer path
length for the components of the hybrid predictors.

• Hybrid-Partial: Conﬁdence counter (2-bit resetting counter) is added into each entry of the selection table. The counter is incremented in thecase of prediction hit and the selection counter isalready saturated. When the conﬁdence counter isalso saturated, only the currently selected prediction table is checked and updated. The counter isreset when a miss occurred.
• Hybrid-Lazy: Prediction tables are checked andupdated only when the selected prediction missed.
In case of hit, the unselected table is not updated
even if its prediction would have missed.

56

The predictability of threads achieved using path-based
approach is fairly high if suﬃciently long path information is incorporated. However, long path information
may lead into severe aliasing problem in programs withlarge footprint. To solve this problem, this paper introduced a dual-length path-based predictor in which twopredictors with diﬀerent path length are combined toform a hybrid predictor. The hybrid approach allows us
to exploit higher predictability of the longer path predictor when the aliasing is not prohibitive. At the sametime, the shorter path predictor provides backup when
the aliasing is becoming severe. Furthermore, aliasing
can be reduced by ﬁltering unnecessary update to prediction tables of the hybrid predictor. Evaluation results
showed the combined eﬀect signiﬁcantly improved theprediction accuracy over single scheme predictors.

Evaluations

Fig. 4 shows prediction accuracy for single scheme predictors with path length of one (4k-entry, index=12|1|)
and four (4k-entry, index=12-8-8-8|3|), and prediction
accuracy for variations of dual-length hybrid predictorsthat combined predictors with path length of one (2kentry, index=11|1|) and four (2k-entry, index=11-8-77|3|). A 4k-entry selection table is used in hybrid predictors constituting approximately 10% additional bits.
Hit rate for an ideal predictor of path length four is also
shown as references.

References

100[1] P.-Y. Chang. Branch Classiﬁcation: a New Mechanism for
Improving Branch Predictor Performance. In Proc. of the27th MICRO, pages 22–31, 1994.

95
90

Single-PathLen=1
Single-PathLen=4
Hybrid-Always
Hybrid-Partial
Hybrid-Lazy
Ideal-PathLen=4][% 85etarti 80h75[2] P.-Y. Chang, M. Evers, and Y. N. Patt. Improving BranchPrediction Accuracy by Reducing Pattern History Table Interference. In Proc. of the 1996 PACT, pages 48–57, 1996.
[3] K. Driesen and U. Holzle. Accurate Indirect Branch Prediction. In Proc. of the 25th ISCA, pages 167–178, 1998.

7065

go.
99
0cc.g621

im
ks88.m
42
1

sse
rpom
.c9
21i.l
301

egp
j.i
23
1lr
ep
.4
13

exrt
vo.
74
1anermha[4] Q. Jacobson, S. Bennett, N. Sharma, and J. E. Smith. Control Flow Speculation in Multiscalar Processors . In Proc. ofthe 3rd HPCA, pages 218–229, 1997.
[5] C.-C. Lee, I.-C. K. Chen, and T. N. Mudge. The Bi-mode
Branch Predictor. In Proc. of the 30th MICRO, pages 4–13,1997.

Figure 4: Hit rate for 4k-entry prediction table[6] S. McFarling. Combining Branch Predictors. Technical Report TN-36 Digital Western Research Lab., 1993.

The results show considerable improvement achievedby hybrid predictors over the single scheme predictors.
Especially in the case of go, gcc, and vortex, in which
capacity aliasing is prohibitive, improvement over single
scheme predictor with path length of four is signiﬁcant.
In average, Hybrid-Always outperforms single scheme
predictor (path length of four) by 2.4%. HybridPartial and Hybrid-Lazy further improve the prediction accuracy by 0.6% and 0.7% respectively.

[7] P. Michaud, A. Seznec, and R. Uhlig. Trading Conﬂict andCapacity Aliasing in Conditional Branch Predictors. In Proc.
of the 24th ISCA, pages 292–303, 1997.
[8] R. Nair. Dynamic Path-Based Branch Correlation. In Proc.
of the 28th MICRO, pages 15–23, 1995.
[9] E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt. The
Agree Predictor: A Mechanism for Reducing Negative Branch
History Interference. In Proc. of the 24th ISCA, pages 284–291, 1997.

95[10] J. Stark, M. Evers, and Y. N. Patt. Variable Length Path
Branch Prediction. In Proc. of the 8th ASPLOS, pages 170–179, 1998.

90]

85%
[etaRitH[11] M.-D. Tarlescu, K. B. Theobald, and G. R. Gao. Elastic
History Buﬀer: A Low-Cost Method to Improve Branch Prediction Accuracy. In Proc. of the 1997 ICCD, pages 82–87,1997.

80
Single-PathLen=1
Single-PathLen=4
Hybrid-Always
Hybrid-Partial
Hybrid-Lazy75
70
65

Conclusion

256

512

1024
2048
4096
Table No.of Entries

8192[12] T.-Y. Yeh and Y. N. Patt. Two-Level Adaptive Branch Prediction. In Proc. of the 24th MICRO, pages 51–61, 1991.

16384[13] T.-Y. Yeh and Y. N. Patt. Alternative Implementations ofTwo-Level Adaptive Branch Prediction. In Proc. of the 19thISCA, pages 124–134, 1992.

Figure 5: Average hit rate vs. prediction table size3