• Pennsylvania State University

• CMPEN 431

 Midterm 2 – Solutions 1 (18 pts) Pipelining A company has designed a new 11-stage instruction pipeline processor: IF -> ID -> RF -> E1 -> E2 -> E3 -> E4 -> M1 -> M2 -> M3 -> WB In this architecture, IF is for instruction fetch, ID is for instruction decoding, RF is for register file read, E1 E2, E3 and E4 are for ALU execution, M1, M2 and M3 are for memory access, and WB is for write back. Assume that the branch target address is calculated at stage E2, and the outcome of the branch condition is determined at stage E4. All ALU instructions go through E1, E2, E3 and E4 stages and similarly all memory (load/store) instructions go through M1, M2 and M3 stages. (a) (3 pts) Explain, considering different execution and resource allocation scenarios, how structural hazards can occur in this 11-stage pipeline? How can structural hazards be eliminated? Answer: There are four scenarios, in which structural hazard can happen. In all these scenarios stalling the processor can solve the problem. However, we will talk about more performance optimized solutions. (1) If we have only one memory unit, then a structural hazard will occur if one instruction is being fetched from the shared memory and another is reading data from memory. If these two instructions overlap, both will attempt to access memory at the same time. More ports and resources can solve this problem. (2) If our memory units only have one port for accessing it, and we have two memory instructions in our M1 to M3 stages, it can cause structural hazards. More ports and resources can solve this problem. (3) Another structural hazard can occur if one instruction is reading from the register le and another is concurrently attempting to write back to the memory le. The typical way to x this structural hazard is to ensure that writes are done to the register le in the rst half of a cycle and reads are performed in the second half. (4) The last type is when we want to use ALU during other computations, such as branch target calculations. To solve it, we need to use additional ALU hardware. (b) (3 pts) Explain, giving examples, how data hazards can occur in this pipeline? What are the possible solutions for data hazards (in addition to stalling the pipeline)? Answer: One possible data hazard would occur when an instruction is attempting to use register data that is calculated by the previous instruction. If this is the case, then the second instruction will not be able to read from the register file until the first instruction has written data back to the register. One way to alleviate this issue is to use forwarding, where the result of the first instruction is forwarded to the second instruction. However, if the result of the first instruction is not ready until the E4 stage, then the second instruction will still have to stall for 3 cycles until the result can be ready before the second instruction begins executing. Another data hazard can occur when an instruction loads data from memory and the second instruction uses that data in a calculation. As before, forwarding can help alleviate this problem, but the data will not be ready until the M3 stage of the first instruction. Therefore, the second instruction must stall for 6 cycles before the data is ready to be forwarded to the execution stages. (c) (3 pts) How can control hazards happen in this pipeline? Please list three different cases that a control hazard can happen. Illustrate each case clearly.