Computer Architecture and Engineering CS152 Quiz 4 Solutions Problem Q4 1 Out of Order Scheduling Problem Q4 1 A I1 I2 I3 I4 I5 I6 I7 Time Issued WB Decode ROB 1 0 1 2 3 4 5 0 2 13 3 4 7 18 1 12 15 5 6 17 20 Committed OP L D 2 MUL D 13 ADD D 16 ADDI 17 L D 18 MUL D 19 ADD D 21 Table Q4 1 1 Dest Src1 Src2 T0 T1 T2 T3 T4 T5 T6 R2 T0 T1 R2 T3 T4 T5 F0 F0 T4 T2 Common mistakes Forgetting in order commit integer result bypassing single ported ROB register files issue dependent on writeback of sources and completed decode Problem Q4 1 B I1 I2 I3 I4 I5 I6 I7 Decode ROB 1 0 3 14 17 19 21 Issued 0 2 13 15 18 20 31 Time WB 1 12 15 17 19 30 33 Committed 2 13 16 18 20 31 34 Table Q4 1 2 OP Dest Src1 Src2 L D MUL D ADD D ADDI L D MUL D ADD D T0 T1 T0 T1 T0 T1 T0 R2 T0 T1 R2 T1 T0 T1 F0 F0 T0 F3 Common mistakes Forgetting in order commit not reusing T0 and T1 appropriately Problem Q4 2 Fetch Pipelines PC PC Generation F1 ICache Access F2 D1 Instruction Decode D2 RN Rename Reorder RF Register File Read EX Integer Execute Problem Q4 2 A Pipelining Subroutine Returns Immediately after what pipeline stage does the processor know that it is executing a subroutine return instruction D2 Immediately after what pipeline stage does the processor know the subroutine return address RF How many pipeline bubbles are required when executing a subroutine return 6 Problem Q4 2 B Adding a BTB A subroutine can be called from many different locations and thus a single subroutine return can return to different locations A BTB holds only the address of the last caller Problem Q4 2 C Adding a Return Stack Normally instruction fetch needs to wait until the return instruction finishes the RF stage before the return address is known With the return stack as soon as the return instruction is decoded in D2 instruction fetch can begin fetching from the return address This saves 2 cycles A return address is pushed after a JAL JALR instruction is decoded in D2 A return address is popped after a JR r31 instruction is decoded in D2 Problem Q4 2 D Return Stack Operation A JAL B A 1 A 2 B JR r31 B 1 B 2 instructio n A A 1 A 2 A 3 A 4 B B 1 B 2 B 3 B 4 A 1 time PC F1 PC Problem Q4 2 E F2 F1 PC D1 F2 F1 PC D2 D1 F2 F1 PC RN D2 D1 F2 F1 PC RF RN D2 D1 F2 F1 PC EX RF RN D2 D1 F2 F1 PC EX RF RN D2 D1 F2 F1 PC EX RF RN D2 D1 F2 F1 PC EX RF RN D2 D1 F2 F1 PC EX RF RN D2 D1 F2 F1 EX RF RN D2 D1 F2 EX RF RN D2 D1 EX RF RN D2 EX RF RN EX RF EX Handling Return Address Mispredicts When a value is popped off the return stack after D2 it is saved for two cycles as part of the pipeline state After the RF stage of the return instruction the actual r31 is compared against the predicted return address If the addresses match then we are done Otherwise we mux in the correct program counter at the PC stage and kill the instructions in F1 and F2 Depending on how fast the address comparison is assumed to be you might also kill the instruction in D1 So there is an additional 2 or 3 cycles on a return mispredict Problem Q4 2 F Further Improving Performance Ben should add a cache of the most recently encountered return instruction addresses During F1 the contents of the cache are looked up to see if any entries match the current program counter If so then by the end of F1 instead of D2 we know that we have a return instruction We can then use the return stack to supply the return address Problem Q4 3 Bounds on ILP Problem Q4 3 A Maximum ILP The solution to this question comes from Little s Law Every instruction in flight needs a separate destination physical register unless it does not produce a result We also need enough physical registers to map the committed architectural registers We want to find the minimum number of physical registers for some piece of code to saturate the machine pipelines The machine cannot fetch and commit more than four instructions per cycle so we pick the four lowest latency functional units i e the two integer and the two memory out of the six available as these will require the least number of instructions in flight to saturate the machine s pipelines Instructions allocate a physical register in the decode stage then need to hold it for at least the issue stage plus the execute stage s plus the writeback stage plus the commit stage This is at least 3 cycles in addition to the number of execute stages An acceptable answer was minimum physical 2 3 1 Two integer instructions 2 3 2 Two memory instructions architectural registers 18 architectural registers Answers based on this Little s argument received 6 7 points minus 1 point if the architectural registers was not included We obtain a better solution if we realize that we only need to find one piece of code that saturates the pipelines Stores and branches do not need to allocate a destination register Consider the following unrolled loop which zeros a region of memory written in MIPS assembly code loop sw r0 0 r1 sw r0 4 r1 bne r1 r2 loop addu r1 r1 8 in delay slot This loop will reach a steady state of one iteration per cycle and will saturate the machine four instructions per cycle while allocating only one physical register per cycle also freeing one physical register per cycle The number of physical registers neededfor this loop is only minimum physical 4 Addu instruction architectural registers This possibility got full credit 7 7 Another possible reading of the question was to find a piece of code that had a different performance bottleneck e g a data dependency and find the number of physical registers required for it This wouldn t actually saturate the machines pipelines These answers received almost full credit depending on quality of answer Common errors Many students incorrectly thought that each instruction needs to allocate three physical registers one for each source operand and one for the destination Problem Q4 4 B Maximum ILP with no FPU The answer does not change because the FPU would not be used in a solution that minimized the number of physical registers needed However if in part A the assumption had been that code with a performance bottleneck was used and that included …
View Full Document
Unlocking...