CS316 Autumn 2013 2014 C. Kozyrakis

Part C: Static Branch Prediction. [8 points]

Download 410.65 Kb.

Page	2/6
Date	31.01.2017
Size	410.65 Kb.
	#13195

1 2 3 4 5 6

Part D: Dynamic Branch Prediction. [16 points]

Part C: Static Branch Prediction. [8 points]
Static branch prediction is a compile-time technique of influencing branch execution in order to reduce control dependency stalls. Branch opcodes are supplemented with a static prediction bit that indicates a likely direction during execution of the branch. This is done based on profiling information, ala that in Part B. For this part of Problem 4, new branch opcodes are introduced:
bget - branch greater than or equal with static predict taken

bgen - branch greater than or equal with static predict not-taken

blet - branch less than or equal with static predict taken

blen - branch less than or equal with static predict not-taken
Static branch prediction information is processed in the decode stage of the 5-stage pipeline. When a branch instruction with static predict taken (i.e. bget) is decoded the machine predicts taken. Conversely, when a branch instruction with static predict not-taken (i.e. bgen) is decoded the machine predicts not-taken.

1. [6 points] Pretend you are the compiler, rewrite each conditional branch instruction in the original code sequence using the new conditional branch instructions with static branch prediction encoded.

2. [2 points] Assuming the same execution trace, what is the new total cycle count of the modified code sequence incorporating static branch prediction instructions. Indicate the resultant IPC.

Part D: Dynamic Branch Prediction. [16 points]
This part examines the use of a Branch Target Buffers (BTB) for performing dynamic branch prediction on the 5-Stage scalar pipeline.
The 5-Stage Pipeline without Dynamic Branch Prediction

The BTB is accessed simultaneously with the instruction cache. If the BTB hits and returns a branch target address and the branch is predicted taken, then the next fetch address is the target address from the BTB. If the branch is predicted not taken or the BTB misses, then the sequential address is the next fetch address.

The branch target buffer (BTB) in the 5-Stage pipeline contains 4 entries and is direct mapped. The BTB caches all branch and jump instructions. It stores the branch fetch addresses along with the branch target addresses. If the branch fetch address “hits” in the BTB, the target address in the BTB is used if the branch is predicted taken.

The BTB is updated immediately after prediction in the instruction fetch pipe stage, i.e. assuming speculative update.

1. [6 points] Assume each entry of the BTB employs a 2-bit saturating up/down counter (initialized to the state 00) that maintains branch history. The BTB uses the following prediction algorithm: 00 - Not taken, 01 - Not taken, 10 - Taken, 11 - Taken. Fill in the table below with the state of the BTB after each dynamic branch instruction is executed. Use I[2:1] as the address of an instruction to determine which BTB entry is referenced, where I is the instruction number in its binary form. (2^nd and 3^rd bits resp.)

Dynamic Branches Executed	BTB Entry #0			BTB Entry #1			BTB Entry #2			BTB Entry #3
Dynamic Branches Executed	Stat. Br #	Tar. Instr#	Hist. bits	Stat. Br #	Tar. Instr#	Hist. bits	Stat. Br #	Tar. Instr#	Hist. bits	Stat. Br #	Tar. Instr#	Hist. bits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2. [4 points] Fill in the table below to evaluate how accurately each branch is predicted.

Branch Instr. Number		Branch Instruction Execution
Branch Instr. Number		1	2	3	4	5	6	7	8	9	10
4	Taken or Not
	Pred. Direction
	Correct? (Y/N)
6	Taken or Not
	Pred. Direction
	Correct? (Y/N)
10	Taken or Not
	Pred. Direction
	Correct? (Y/N)
14	Taken or Not
	Pred. Direction
	Correct? (Y/N)
16	Taken or Not
	Pred. Direction
	Correct? (Y/N)
18	Taken or Not
	Pred. Direction
	Correct? (Y/N)

3. [2 points] Compare and contrast the effectiveness and efficiency of the dynamic branch predictor of

Download 410.65 Kb.

Share with your friends:

1 2 3 4 5 6