COMPUTER ARCHITECTURE
BRANCH TARGET BUFFER PROJECT
Objective: To write a program that simulates a
anch target buffer (BTB) that performs dynamic
anch prediction.
Input: A long set of PC addresses from program traces.
Programming language: Use any programming language (C++, Phyton, Java, …).
Figure 1 below shows the basic structure of the BTB which was introduced in class. It has four fields with an entry: Entry number, Cu
ent PC, Target PC, and Prediction. In this project the BTB number of entries is 1024; thus, only 10 bits are needed to address the entire BTB.
Entry Num. Cu
ent PC Target PC Prediction 0:
1:
PC 10
1023:
Figure XXXXXXXXXXentry Branch Target Buffer.
In order to determine the BTB entry, 10 bits (from bit 2 to bit 11) from the PC address are used as shown in Figure 2. The least significant bits (0 and 1) are always 0; thus, they are not needed.
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
PC
Figure 2. 10-bit BTB address obtained from the 32-bit PC.
Here is an example how the BTB index is determined. Let us assume the cu
ent PC address is:
0x4001c4 (this is an hexadecimal number).
31
29
28
27
25
24
23
21
20
19
17
16
15
13
12
11
9
8
7
6
5
4
3
2
1
0
c
4
We need only the last 3 hexadecimal numbers:
11
9
8
7
6
5
4
3
2
1
0
c
1
0
0
0
1
1
1
0
0
0
0
0
The binary number are shown as well.
Using the binary number we can obtained the BTB entry XXXXXXXXXX = XXXXXXXXXX = 113
We can obtain the address using the hexadecimal numbers (this might be a bit easier).
1c4 = 1* XXXXXXXXXX*16 + 4 = 452
Now, we need to remove the 2 least significant bits (we divide by 4): 452/4 = 113
Trace .
400190
To compute index, 10 bits are need (for 1024-entry BTB).
400194
We used the 3 least significant bytes (in red);
400198
40019c
the 2 least significat bits are not considered (they are always 00)
4001a0
4001c4 1* XXXXXXXXXX*16 + 4 ïƒ 452 / 4 =113
4001a4
XXXXXXXXXX = XXXXXXXXXX = 113
4001a8
↑↑↑↑ ↑↑↑↑ ↑↑
4001ac
4001b0
2n → XXXXXXXXXX
4001b4
4001b8
Cu
ent PC Target PC Prediction
4202d4
4202d8
4202dc
4202dc 2* XXXXXXXXXX*16 + 12 ïƒ 732 / 4 =183
42ac30
42ac34
42ac38
42ac3c
42ac40
42ac44
XXXXXXXXXX = XXXXXXXXXX XXXXXXXXXX = 183
42ac48
42ac5c
42ac60
42ac64
42ac68
42ac6c
42ac70
42ac74
42ac78
42ac7c
42ac80
42ac84 42ac88
42ac8c
42ac90
42ac94
42ac98
42ac9c
42ac48
12*162 + 4*16 + 8
ïƒ 3144/4 =786
4001bc 4001c4
10
:
:
:
:
113
4001c4
4202b0
Taken
(00)
183
4202
dc
42
ac
30
Taken
(00)
786
48
ac
42
ac5c
42
Taken
(00)
entries
1024
4001c0
4202b0
4202b4 index
4202b8
4202bc
4202c0
4202c4
4202c8
4202cc
4202d0
Specifications:
· BTB size: 1024 Entries
· Two Benchmarks. Use the least significant digit in your ID*:
· Even (0, 2, 4, 6 or 8): Li_int and Doduc_FP
· Odd (1, 3, 5, 7 or 9): Espresso_int and Spice_FP
· Two prediction state machines. Use second least significant digit of ID*: - Even: Class state machine (Figure 3) and State Machines A (Figure 4)
· Odd: Class state machine (Figure 3) and State Machines B (Figure 5)  Total number of instructions executed: instruction count (IC).
· Number of hits (Hit): number of times a
anch is found in BTB.
· Number of misses (Miss): number of times a
anch is not found in BTB.
· Number of right predictions (Right): number of times the prediction is right.
· Number of wrong predictions (Wrong) ): number of times the prediction is wrong.
· Number of taken
anches/jumps (B_Taken)
· Number of collisions (Collisions): number of times a
anch displaces a
anch in BTB.
· Number of wrong address predictions (Wrong_addr): A wrong addres is when a
anch is predicted (as taken) but the address is not right.
· Hit rate: This is defined as follows
?????? ?? â„Ž???
??? ???? (%) =
(?????? ?? â„Ž???) + (?????? ?? ??????)
· Prediction accuracy:
?????? ?? ??????? (???â„Ž?) ???????????
???????? (%) =
(?????? ?? â„Ž???)
· Inco
ect address (%)
?????_????
???????_????? (%) =
(?????? ?? ????? ???????????)
00
Predicted
Taken
Taken
Not taken
01
Predicted
Taken
Taken
Not taken
10
Predicted not
Taken
Not taken
Not taken
11
Predicted not
Taken
Taken
Taken
Initial state
Figure 3.
Class Prediction State Machine
Figure
. Prediction State Machine A
4
.
T
00
T
01
NT
11
NT
10
Initial state
Prediction
T: Taken
NT: Not taken
Actual Branch
Taken
Not taken
Figure 5
. Prediction State Machine
B.
T
00
T
01
NT
11
NT
10
Initial state
Prediction
T: Taken
NT: Not taken
Actual Branch
Taken
Not taken
Deadlines
Deadline
Items
Grade
April 12 (11:59 pm) BTB w/
anches
A list of
anches (PC and Target) and their entry number in BTB. (See Appendix A, below). Program code needs be included as a file.
The trace sample is used (11,154 addresses).
10 points
April 19 (11:59 pm) BTB w/ predictions
Mid-project report using sample trace.
This will include the status of BTB with prediction at the end of the run. (See Appendix B, below)
10 points
Monday, May 1 Project Report
Project report with all the results (11:59 pm). An outline of the report will be provided at a later time.
(Final exam 11am - 12noon.)
80 points
Appendix A. BTB entries with PC and Target PC. Please include only entries with content.
Entry PC Target
0
423000
425E40
7
8
11
42E01C
42E028
423020
4230A8
42E02C
42B30C
14
:
:
423038
425E40
:
:
:
:
1018
422FE8
4230A8
Appendix B. BTB entries with PC, Target PC, and Prediction.
Entry PC Target Pred.
0
423000
425E40
00
7
42E01C
42E028
00
8
11
14 :
423020
4230A8
00
42E02C
42B30C
00
423038
425E40
00
:
:
:
:
:
:
:
1018
422FE8
4230A8
00
Branch prediction
Variables to Keep Track (& initial values)
Hit = 0
Miss = 0
Right = 0
Wrong = 0
Wrong_addr = 0
Collision = 0
‹#›
EE334 Computer Architecture
Step 1 (IF stage)
Example
Trace
4001c4
4202b0
4202b4
PC_cu
ent = 4001c4
PC_next = 4202b0
Is PC_cu
ent in BTB ?
No
Yes
Use PC_cu
ent address to determine BTB location. BTB_Address: 113
Next slide
BTB (113) has either:
No prediction at all
PC in BTB is not equal to PC_cu
ent
‹#›
EE334 Computer Architecture
Step 2 (ID stage –No found side)
Is instruction a
taken
anch?
No
Yes
Normal Instruction Execution
Miss=Miss+1
Taken=Taken+1
Is PC_next not equal
to PC_cu
ent + 4
PC_cu
ent= 4001c4
PC_next = 4202b0
‹#›
EE334 Computer Architecture
Step 2 (ID stage –No found side)
Is instruction a
taken
anch?
No
Yes
Normal Instruction Execution
Miss=Miss+1
Taken=Taken+1
Is PC_next not equal
to PC_cu
ent + 4
PC_cu
ent= 4001c4
PC_next = 4202b0
ïƒ
Step 3 (EX stage)
If BTB entry is used by other
anch address: Collision = Collision + 1
Enter
anch address and next PC into BTB
Entry PC Target Prediction
113: 4001c4 4202b0 Taken (strong)
‹#›
EE334 Computer Architecture
Back to Step 1 (IF stage)
Example
Trace
4001c4
4202b0
4202b4
PC_cu
ent = 4001c4
PC_next = 4202b0
Is PC_cu
ent in BTB ?
No
Yes
Hit = Hit + 1
Use PC_cu
ent address to determine BTB location. BTB_Address: 113
Next slide
B T B
Entry PC Target Prediction
113: 4001c4 4202b0 Taken (00)
‹#›
EE334 Computer Architecture
Step 2, 3 (ID,EX)
Right prediction?
No
Yes
If prediction is Taken:
If (PC_next = BTB target)
{PC_next = BTB Target= 4202b0}
Then Right = Right + 1; Taken = Taken + 1; updateBTB (predictor: Br T)
Else Wrong = Wrong + 1
If (PC_next = PC_Cu
ent+4)
XXXXXXXXXXThen updateBTB (predictor: Br NT)