Tournament Predictors Example
Tournament Predictors
Example
Jiayi Huang
jyhuang@cse.tamu.edu
Tournament Predictors
• Features:
– Combine global and local predictors
– Use a selector to select the prediction outcome from one of them
– Update both predictors as well as the selector for each branch
• Selector Update
– Update selector based on the prediction correctness of two predictors
• Predictor Indexing
– Global predictor: indexed by history register
– Local predictor: indexed by LSBs of branch PC
Tournament Predictor Diagram
Selector
Branch PC
Local predictor (P1)
Global predictor (P2)
Global history register
Pred 1
Pred 2
Selected prediction
Selector State Transition Machine
• Transition condition is the correctness of predictors
(00) Use
predictor 1
(01) Use
predictor 1
(11) Use
predictor 2
(10) Use
predictor 2
0/0, 1/0, 1/1 0/0, 0/1, 1/1
0/0, 1/1 0/0, 1/1
1/0 0/1
0/1
0/1
1/0
1/0
(P1_correctness/P2_correctness)
Two-bit saturation predictor
(00) NT
(01) NT
(11) T
(10) T
NT T
NT T
T
T
NT
NT
Example
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T
B2: …011 T
B3: …010 NT
• One Selector Entry
• P1: two entry local predictor
• P2: two-bit global history register (shift register), meaning four entries
• All predictor are two-bit saturation counter
Example: Initial states
00
Selector
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T
B2: …011 T
B3: …010 NT
00
00
P1: local predictor
11
11
P2: global predictor
11
11
0
1
00
01
10
11
00 History register
Example: B1 (states not updated yet)
00
Selector
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T NT T NT(P1) 0/1
B2: …011 T
B3: …010 NT
00
00
P1: local predictor
11
11
P2: global predictor
11
11
0
1
00
01
10
11
00 History register
Selector State Transition: B1
(00) Use
predictor 1
(01) Use
predictor 1
(11) Use
predictor 2
(10) Use
predictor 2
0/0, 1/0, 1/1 0/0, 0/1, 1/1
0/0, 1/1 0/0, 1/1
1/0 0/1
0/1
0/1
1/0
1/0
Example: B2 (updated states after B1)
01
Selector
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T NT T NT(P1) 0/1
B2: …011 T NT T NT(P1) 0/1
B3: …010 NT
01
00
P1: local predictor
11
11
P2: global predictor
11
11
0
1
00
01
10
11
01 History register
Selector State Transition: B2
(00) Use
predictor 1
(01) Use
predictor 1
(11) Use
predictor 2
(10) Use
predictor 2
0/0, 1/0, 1/1 0/0, 0/1, 1/1
0/0, 1/1 0/0, 1/1
1/0 0/1
0/1
0/1
1/0
1/0
Example: B3 (states updated after B2)
10
Selector
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T NT T NT(P1) 0/1
B2: …011 T NT T NT(P1) 0/1
B3: …010 NT NT T T(P2) 1/0
01
01
P1: local predictor
11
11
P2: global predictor
11
11
0
1
00
01
10
11
11 History register
Selector State Transition: B3
(00) Use
predictor 1
(01) Use
predictor 1
(11) Use
predictor 2
(10) Use
predictor 2
0/0, 1/0, 1/1 0/0, 0/1, 1/1
0/0, 1/1 0/0, 1/1
1/0 0/1
0/1
0/1
1/0
1/0
Example: Final states
01
Selector
Branch PC Action P1 P2 Prediction
P1_correct/P2_c
orrect
B1: …100 T NT T NT(P1) 0/1
B2: …011 T NT T NT(P1) 0/1
B3: …010 NT NT T T(P2) 1/0
00
01
P1: local predictor
11
11
P2: global predictor
11
10
0
1
00
01
10
11
10 History register