Computer Science > QUESTIONS & ANSWERS > Computer Science 605.611 (All)

Computer Science 605.611

Document Content and Description Below

Computer Science 605.611 Problem Set 8 Answers (For all of the questions on this problem set, assume that all branch instructions are treated as delayed branches.) 1. Consider the following instru... ction sequence that executes on our 5-stage scalar pipelined a system with a hazard unit as well as a forwarding unit: ori $4,$0,4 loop: add $6,$7,$8 and $9,$4,$7 bne $4,$0,loop srl $4,$4,1 addi $3,$0,1 add $3,$3,$3 sll $3,$3,1 a) (5) The ori instruction is fetched in cycle 1. During which clock cycle does the sll instruction complete the write-back stage if no early branch condition evaluation or branch prediction is used? The ori instruction initializes $4 to the value 4. Each time that the bne instruction is executed, the srl in the delay slot is executed whether the branch is taken or not. The first time through the loop $4=4, $4=2 the second time, $4=1 the third time, $4=0 the last time through the loop. The bne takes effect when it is in the memory stage. When the bne branches, the instructions in the decode and fetch stages will be flushed causing two bubbles. The last time through the loop, no flushing occurs since the branch is not taken. The instructions flow through the pipeline as follows: Cycle Fetch Decode Exec Mem Write-back 1 ori 2 add $6 ori 3 and add ori 4 bne and add ori 5 srl bne and add ori 6 addi srl bne and add 7 add $3 addi srl bne and 8 add $6 bubble bubble srl bne 9 and add bubble bubble srl 10 bne and add bubble bubble 11 srl bne and add bubble 12 addi srl bne and add 13 add $3 addi srl bne and 14 add $6 bubble bubble srl bne 15 and add bubble bubble srl 16 bne and add bubble bubble 17 srl bne and add bubble 18 addi srl bne and add 19 add $3 addi srl bne and 20 add $6 bubble bubble srl bne 21 and add bubble bubble srl 22 bne and add bubble bubble 23 srl bne and add bubble 24 addi srl bne and add 25 add $3 addi srl bne and 26 sll add addi srl bne 27 sll add addi srl 28 sll add addi 29 sll add 30 sll 1Therefore the sll completes its write-back stage in cycle 30. b) (5) The ori instruction is fetched in cycle 1. There is no early branch condition evaluation. During which clock cycle does the sll instruction complete the write-back stage if branch prediction based on a decode history table (DHT) is used? Assume that the DHT always predicts that the branch will be taken. When the branch is predicted in stage 2, the instruction in the delay slot (srl) will already be in the fetch stage. The next instruction that is fetched into the pipeline behind the srl instruction will be from the branch target address (i.e., the first add instruction). The first three predictions will be correct, but the last is incorrect. When the bne actually branches, no flushing occurs. Flushing only occurs when the prediction is wrong. The incorrect branch prediction will be detected and acted on when the bne is in the MEM stage which causes the two instructions (addi, and) along the incorrect path to be flushed. Hence the instructions flow through the pipeline as follows: Cycle Fetch Decode Exec Mem Write-back 1 ori 2 add $6 ori 3 and add ori 4 bne and add ori 5 srl bne and add ori 6 add $6 srl bne and add 7 and add srl bne and 8 bne and add srl bne 9 srl bne and add srl 10 add $6 srl bne and add 11 and add srl bne and 12 bne and add srl bne [Show More]

Last updated: 2 years ago

Preview 1 out of 10 pages

Buy Now

Instant download

We Accept: