Consider the following instruction: Instruction: AND Rd,Rs,Rt Interpretation: Reg[ Rd ] = Reg[ Rs ] AND Reg[ Rt ]
Read moreTextbook Solutions for Computer Organization and Design
Chapter 4 Problem 4.12
Question
This exercise is intended to help you understand the cost/complexity/performance trade-offs of forwarding in a pipelined processor. Problems in this exercise refer to pipelined datapaths from Figure 4.45. These problems assume that, of all the instructions executed in a processor, the following fraction of these instructions have a particular type of RAW data dependence. The type of RAW data dependence is identified by the stage that produces the result (EX or MEM) and the instruction that consumes the result (1st instruction that follows the one that produces the result, 2nd instruction that follows, or both). We assume that the register write is done in the first half of the clock cycle and that register reads are done in the second half of the cycle, so “EX to 3rd” and “MEM to 3rd” dependences are not counted because they cannot result in data hazards. Also, assume that the CPI of the processor is 1 if there are no data hazards.
\(\begin{array}{|c|c|c|c|c|c|}
\hline \begin{array}{c}
\text { EX to } 1^{\text {st }} \\
\text { Only }
\end{array} & \begin{array}{c}
\text { MEM to } 1^{\text {st }} \\
\text { Only }
\end{array} & \begin{array}{c}
\text { EX to } 2^{\text {nd }} \\
\text { Only }
\end{array} & \begin{array}{c}
\text { MEM to } 2^{\text {nd }} \\
\text { Only }
\end{array} & \begin{array}{l}
\text { EX to } 1^{\text {st }} \\
\text { and MEM } \\
\text { to 2nd }
\end{array} & \begin{array}{c}
\text { Other RAW } \\
\text { Dependences }
\end{array} \\
\hline 5 \% & 20 \% & 5 \% & 10 \% & 10 \% & 10 \% \\
\hline
\end{array}\)
Assume the following latencies for individual pipeline stages. For the EX stage, latencies are given separately for a processor without forwarding and for a processor with different kinds of forwarding.
\(\begin{array}{|c|c|c|c|c|c|c|c|}
\hline \text { IF } & \text { ID } & \begin{array}{c}
\text { EX } \\
\text { (no FW) }
\end{array} & \begin{array}{c}
\text { EX } \\
\text { (full FW) }
\end{array} & \begin{array}{c}
\text { EX (FW from } \\
\text { EX/MEM only) }
\end{array} & \begin{array}{c}
\text { EX (FW } \\
\text { from MEM/ } \\
\text { WB only) }
\end{array} & \text { MEM } & \text { WB } \\
\hline 150 \mathrm{ps} & 100 \mathrm{ps} & 120 \mathrm{ps} & 150 \mathrm{ps} & 140 \mathrm{ps} & 130 \mathrm{ps} & 120 \mathrm{ps} & 100 \mathrm{ps} \\
\hline
\end{array}\)
Solution
The first step in solving 4 problem number 60 trying to solve the problem we have to refer to the textbook question: This exercise is intended to help you understand the cost/complexity/performance trade-offs of forwarding in a pipelined processor. Problems in this exercise refer to pipelined datapaths from Figure 4.45. These problems assume that, of all the instructions executed in a processor, the following fraction of these instructions have a particular type of RAW data dependence. The type of RAW data dependence is identified by the stage that produces the result (EX or MEM) and the instruction that consumes the result (1st instruction that follows the one that produces the result, 2nd instruction that follows, or both). We assume that the register write is done in the first half of the clock cycle and that register reads are done in the second half of the cycle, so “EX to 3rd” and “MEM to 3rd” dependences are not counted because they cannot result in data hazards. Also, assume that the CPI of the processor is 1 if there are no data hazards.\(\begin{array}{|c|c|c|c|c|c|}\hline \begin{array}{c}\text { EX to } 1^{\text {st }} \\\text { Only }\end{array} & \begin{array}{c}\text { MEM to } 1^{\text {st }} \\\text { Only }\end{array} & \begin{array}{c}\text { EX to } 2^{\text {nd }} \\\text { Only }\end{array} & \begin{array}{c}\text { MEM to } 2^{\text {nd }} \\\text { Only }\end{array} & \begin{array}{l}\text { EX to } 1^{\text {st }} \\\text { and MEM } \\\text { to 2nd }\end{array} & \begin{array}{c}\text { Other RAW } \\\text { Dependences }\end{array} \\\hline 5 \% & 20 \% & 5 \% & 10 \% & 10 \% & 10 \% \\\hline\end{array}\)Assume the following latencies for individual pipeline stages. For the EX stage, latencies are given separately for a processor without forwarding and for a processor with different kinds of forwarding.\(\begin{array}{|c|c|c|c|c|c|c|c|}\hline \text { IF } & \text { ID } & \begin{array}{c}\text { EX } \\\text { (no FW) }\end{array} & \begin{array}{c}\text { EX } \\\text { (full FW) }\end{array} & \begin{array}{c}\text { EX (FW from } \\\text { EX/MEM only) }\end{array} & \begin{array}{c}\text { EX (FW } \\\text { from MEM/ } \\\text { WB only) }\end{array} & \text { MEM } & \text { WB } \\\hline 150 \mathrm{ps} & 100 \mathrm{ps} & 120 \mathrm{ps} & 150 \mathrm{ps} & 140 \mathrm{ps} & 130 \mathrm{ps} & 120 \mathrm{ps} & 100 \mathrm{ps} \\\hline\end{array}\)
From the textbook chapter The Processor you will find a few key concepts needed to solve this.
Visible to paid subscribers only
Step 3 of 7)Visible to paid subscribers only
Subscribe to view the
full solution
full solution
Title
Computer Organization and Design 5
Author
David A. Patterson
ISBN
9780124077263
This exercise is intended to help you understand the
Chapter 4 textbook questions
-
Chapter 4: Problem 4 Computer Organization and Design 5
-
Chapter 4: Problem 4 Computer Organization and Design 5
What are the values of control signals generated by the control in Figure 4.2 for the above instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Which resources (blocks) perform a useful function for this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Which resources (blocks) produce outputs, but their outputs are not used for this instruction? Which resources produce no outputs for this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The basic single-cycle MIPS implementation in Figure 4.2 can only implement some instructions. New instructions can be added to an existing Instruction Set Architecture (ISA), but the decision whether or not to do that depends, among other things, on the cost and complexity the proposed addition introduces into the processor datapath and control. The first three problems in this exercise refer to the new instruction: Instruction: LWI Rt,Rd(Rs) Interpretation: Reg[ Rt ] = Mem[ Reg[ Rd ]+Reg[ Rs ] ]
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Which existing blocks (if any) can be used for this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Which new functional blocks (if any) do we need for this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What new signals do we need (if any) from the control unit to support this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
When processor designers consider a possible improvement to the processor datapath, the decision usually depends on the cost/performance trade-off . In the following three problems, assume that we are starting with a datapath from Figure 4.2, where I-Mem, Add, Mux, ALU, Regs, D-Mem, and Control blocks have latencies of 400 ps, 100 ps, 30 ps, 120 ps, 200 ps, 350 ps, and 100 ps, respectively, and costs of 1000, 30, 10, 100, 200, 2000, and 500, respectively. Consider the addition of a multiplier to the ALU. This addition will add 300 ps to the latency of the ALU and will add a cost of 600 to the ALU. The result will be 5% fewer instructions executed since we will no longer need to emulate the MUL instruction.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the clock cycle time with and without this improvement?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the speedup achieved by adding this improvement?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Compare the cost/performance ratio with and without this improvement.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Problems in this exercise assume that logic blocks needed to implement a processor’s datapath have the following latencies:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If the only thing we need to do in a processor is fetch consecutive instructions (Figure 4.6), what would the cycle time be?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Consider a datapath similar to the one in Figure 4.11, but for a processor that only has one type of instruction: unconditional PC-relative branch. What would the cycle time be for this datapath?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.4.2, but this time we need to support only conditional PC-relative branches. The remaining three problems in this exercise refer to the datapath element Shift - left -2:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Which kinds of instructions require this resource?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For which kinds of instructions (if any) is this resource on the critical path?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assuming that we only support beq and add instructions, discuss how changes in the given latency of this resource affect the cycle time of the processor. Assume that the latencies of other resources do not change.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For the problems in this exercise, assume that there are no pipeline stalls and that the breakdown of executed instructions is as follows:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In what fraction of all cycles is the data memory used?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In what fraction of all cycles is the input of the sign-extend circuit needed? What is this circuit doing in cycles in which its input is not needed?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
When silicon chips are fabricated, defects in materials (e.g., silicon) and manufacturing errors can result in defective circuits. A very common defect is for one wire to affect the signal in another. This is called a cross-talk fault. A special class of cross-talk faults is when a signal is connected to a wire that has a constant logical value (e.g., a power supply wire). In this case we have a stuck-at-0 or a stuck- at-1 fault, and the affected signal always has a logical value of 0 or 1, respectively. The following problems refer to bit 0 of the Write Register input on the register file in Figure 4.24.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Let us assume that processor testing is done by filling the PC, registers, and data and instruction memories with some values (you can choose which values), letting a single instruction execute, then reading the PC, memories, and registers. These values are then examined to determine if a particular fault is present. Can you design a test (values for PC, memories, and registers) that would determine if there is a stuck-at-0 fault on this signal?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.6.1 for a stuck-at-1 fault. Can you use a single test for both stuck-at-0 and stuck-at-1? If yes, explain how; if no, explain why not.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If we know that the processor has a stuck-at-1 fault on this signal, is the processor still usable? To be usable, we must be able to convert any program that executes on a normal MIPS processor into a program that works on this processor. You can assume that there is enough free instruction memory and data memory to let you make the program longer and store additional data. Hint: the processor is usable if every instruction “broken” by this fault can be replaced with a sequence of “working” instructions that achieve the same effect.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.6.1, but now the fault to test for is whether the “MemRead” control signal becomes 0 if RegDst control signal is 0, no fault otherwise.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.6.4, but now the fault to test for is whether the “Jump” control signal becomes 0 if RegDst control signal is 0, no fault otherwise.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we examine in detail how an instruction is executed in a single-cycle datapath. Problems in this exercise refer to a clock cycle in which the processor fetches the following instruction word: 10101100011000100000000000010100. Assume that data memory is all zeros and that the processor’s registers have the following values at the beginning of the cycle in which the above instruction word is fetched:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What are the outputs of the sign-extend and the jump “Shift left 2” unit (near the top of Figure 4.24) for this instruction word?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What are the values of the ALU control unit’s inputs for this instruction?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the new PC address after this instruction is executed? Highlight the path through which this value is determined.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For each Mux, show the values of its data output during the execution of this instruction and these register values.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For the ALU and the two add units, what are their data input values?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What are the values of all inputs for the “Registers” unit?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise, we examine how pipelining affects the clock cycle time of the processor. Problems in this exercise assume that individual stages of the datapath have the following latencies: Also, assume that instructions executed by the processor are broken down as follows:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the clock cycle time in a pipelined and non-pipelined processor?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the total latency of an LW instruction in a pipelined and non-pipelined processor?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If we can split one stage of the pipelined datapath into two new stages, each with half the latency of the original stage, which stage would you split and what is the new clock cycle time of the processor?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assuming there are no stalls or hazards, what is the utilization of the data memory?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assuming there are no stalls or hazards, what is the utilization of the write-register port of the “Registers” unit?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Instead of a single-cycle organization, we can use a multi-cycle organization where each instruction takes multiple cycles but one instruction finishes before another is fetched. In this organization, an instruction only goes through stages it actually needs (e.g., ST only takes 4 cycles because it does not need the WB stage). Compare clock cycle times and execution times with single-cycle, multi-cycle, and pipelined organization.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise, we examine how data dependences affect execution in the basic 5-stage pipeline described in Section 4.5. Problems in this exercise refer to the following sequence of instructions: or r1, r2, r3 or r2, r1, r4 or r1, r1, r2 Also, assume the following cycle times for each of the options related to forwarding:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Indicate dependences and their type.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assume there is no forwarding in this pipelined processor. Indicate hazards and add nop instructions to eliminate them.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assume there is full forwarding. Indicate hazards and add NOP instructions to eliminate them.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the total execution time of this instruction sequence without forwarding and with full forwarding? What is the speedup achieved by adding full forwarding to a pipeline that had no forwarding?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Add nop instructions to this code to eliminate hazards if there is ALU-ALU forwarding only (no forwarding from the MEM to the EX stage).
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What is the total execution time of this instruction sequence with only ALU-ALU forwarding? What is the speedup over a no-forwarding pipeline?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise, we examine how resource hazards, control hazards, and Instruction Set Architecture (ISA) design can affect pipelined execution. Problems in this exercise refer to the following fragment of MIPS code: sw r16, 12(r6) lw r16, 8(r6) beq r5, r4, Label # Assume r5!=r4 add r5, r1, r4 slt r5, r15,r4 Assume that individual pipeline stages have the following latencies:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For this problem, assume that all branches are perfectly predicted (this eliminates all control hazards) and that no delay slots are used. If we only have one memory (for both instructions and data), there is a structural hazard every time we need to fetch an instruction in the same cycle in which another instruction accesses data. To guarantee forward progress, this hazard must always be resolved in favor of the instruction that accesses data. What is the total execution time of this instruction sequence in the 5-stage pipeline that only has one memory? We have seen that data hazards can be eliminated by adding nops to the code. Can you do the same with this structural hazard? Why?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For this problem, assume that all branches are perfectly predicted (this eliminates all control hazards) and that no delay slots are used. If we change load/store instructions to use a register (without an offset) as the address, these instructions no longer need to use the ALU. As a result, MEM and EX stages can be overlapped and the pipeline has only 4 stages. Change this code to accommodate this changed ISA. Assuming this change does not affect clock cycle time, what speedup is achieved in this instruction sequence?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assuming stall-on-branch and no delay slots, what speedup is achieved on this code if branch outcomes are determined in the ID stage, relative to the execution where branch outcomes are determined in the EX stage?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Given these pipeline stage latencies, repeat the speedup calculation from 4.10.2, but take into account the (possible) change in clock cycle time. When EX and MEM are done in a single stage, most of their work can be done in parallel. As a result, the resulting EX/MEM stage has a latency that is the larger of the original two, plus 20 ps needed for the work that could not be done in parallel.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Given these pipeline stage latencies, repeat the speedup calculation from 4.10.3, taking into account the (possible) change in clock cycle time. Assume that the latency ID stage increases by 50% and the latency of the EX stage decreases by 10ps when branch outcome resolution is moved from EX to ID.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Assuming stall-on-branch and no delay slots, what is the new clock cycle time and execution time of this instruction sequence if beq address computation is moved to the MEM stage? What is the speedup from this change? Assume that the latency of the EX stage is reduced by 20 ps and the latency of the MEM stage is unchanged when branch outcome resolution is moved from EX to MEM.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Consider the following loop. loop: lw r1, 0(r1) and r1, r1, r2 lw r1, 0(r1) lw r1, 0(r1) beq r1, r0, loop Assume that perfect branch prediction is used (no stalls due to control hazards), that there are no delay slots, and that the pipeline has full forwarding support. Also assume that many iterations of this loop are executed before the loop exits.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Show a pipeline execution diagram for the third iteration of this loop, from the cycle in which we fetch the first instruction of that iteration up to (but not including) the cycle in which we can fetch the first instruction of the next iteration. Show all instructions that are in the pipeline during these cycles (not just those from the third iteration).
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
How often (as a percentage of all cycles) do we have a cycle in which all five pipeline stages are doing useful work?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise is intended to help you understand the cost/complexity/performance trade-offs of forwarding in a pipelined processor. Problems in this exercise refer to pipelined datapaths from Figure 4.45. These problems assume that, of all the instructions executed in a processor, the following fraction of these instructions have a particular type of RAW data dependence. The type of RAW data dependence is identified by the stage that produces the result (EX or MEM) and the instruction that consumes the result (1st instruction that follows the one that produces the result, 2nd instruction that follows, or both). We assume that the register write is done in the first half of the clock cycle and that register reads are done in the second half of the cycle, so “EX to 3rd” and “MEM to 3rd” dependences are not counted because they cannot result in data hazards. Also, assume that the CPI of the processor is 1 if there are no data hazards. Assume the following latencies for individual pipeline stages. For the EX stage, latencies are given separately for a processor without forwarding and for a processor with different kinds of forwarding.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If we use no forwarding, what fraction of cycles are we stalling due to data hazards?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If we use full forwarding (forward all results that can be forwarded), what fraction of cycles are we staling due to data hazards?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Let us assume that we cannot afford to have three-input Muxes that are needed for full forwarding. We have to decide if it is better to forward only from the EX/MEM pipeline register (next-cycle forwarding) or only from the MEM/WB pipeline register (two-cycle forwarding). Which of the two options results in fewer data stall cycles?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For the given hazard probabilities and pipeline stage latencies, what is the speedup achieved by adding full forwarding to a pipeline that had no forwarding?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
What would be the additional speedup (relative to a processor with forwarding) if we added time-travel forwarding that eliminates all data hazards? Assume that the yet-to-be-invented time-travel circuitry adds 100 ps to the latency of the full-forwarding EX stage.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.12.3 but this time determine which of the two options results in shorter time per instruction.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise is intended to help you understand the relationship between forwarding, hazard detection, and ISA design. Problems in this exercise refer to the following sequence of instructions, and assume that it is executed on a 5-stage pipelined datapath: add r5, r2,r1 lw r3, 4(r5) lw r2, 0(r2) or r3, r5, r3 sw r3, 0(r5)
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If there is no forwarding or hazard detection, insert nops to ensure correct execution.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.13.1 but now use nops only when a hazard cannot be avoided by changing or rearranging these instructions. You can assume register R7 can be used to hold temporary values in your modified code.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If the processor has forwarding, but we forgot to implement the hazard detection unit, what happens when this code executes?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If there is forwarding, for the first five cycles during the execution of this code, specify which signals are asserted in each cycle by hazard detection and forwarding units in Figure 4.60.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
If there is no forwarding, what new inputs and output signals do we need for the hazard detection unit in Figure 4.60? Using this instruction sequence as an example, explain why each signal is needed.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For the new hazard detection unit from 4.13.5, specify which output signals it asserts in each of the first five cycles during the execution of this code.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise is intended to help you understand the relationship between delay slots, control hazards, and branch execution in a pipelined processor. In this exercise, we assume that the following MIPS code is executed on a pipelined processor with a 5-stage pipeline, full forwarding, and a predict-taken branch predictor: lw r2, 0(r1) label1: beq r2, r0, label2 # not taken once, then taken lw r3, 0(r2) beq r3, r0, label1 # taken add r1, r3, r1 label2: sw r1, 0(r2)
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Draw the pipeline execution diagram for this code, assuming there are no delay slots and that branches execute in the EX stage.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Repeat 4.14.1, but assume that delay slots are used. In the given code, the instruction that follows the branch is now the delay slot instruction for that branch.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
One way to move the branch resolution one stage earlier is to not need an ALU operation in conditional branches. The branch instructions would be “bez rd,label” and “bnez rd,label”, and it would branch if the register has and does not have a zero value, respectively. Change this code to use these branch instructions instead of beq. You can assume that register R8 is available for you to use as a temporary register, and that an seq (set if equal) R-type instruction can be used. Section 4.8 describes how the severity of control hazards can be reduced by moving branch execution into the ID stage. This approach involves a dedicated comparator in the ID stage, as shown in Figure 4.62. However, this approach potentially adds to the latency of the ID stage, and requires additional forwarding logic and hazard detection.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Using the first branch instruction in the given code as an example, describe the hazard detection logic needed to support branch execution in the ID stage as in Figure 4.62. Which type of hazard is this new logic supposed to detect?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
For the given code, what is the speedup achieved by moving branch execution into the ID stage? Explain your answer. In your speedup calculation, assume that the additional comparison in the ID stage does not affect clock cycle time.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
Using the first branch instruction in the given code as an example, describe the forwarding support that must be added to support branch execution in the ID stage. Compare the complexity of this new forwarding unit to the complexity of the existing forwarding unit in Figure 4.62.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: Stall cycles due to mispredicted branches increase the CPI. What is the extra CPI due to mispredicted branches with the always-taken predictor? Assume that branch outcomes are determined in the EX stage, that there are no data hazards, and that no delay slots are used.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: Repeat 4.15.1 for the “always-not-taken” predictor.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: Repeat 4.15.1 for for the 2-bit predictor.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: With the 2-bit predictor, what speedup would be achieved if we could convert half of the branch instructions in a way that replaces a branch instruction with an ALU instruction? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: With the 2-bit predictor, what speedup would be achieved if we could convert half of the branch instructions in a way that replaced each branch instruction with two ALU instructions? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows: Also, assume the following branch predictor accuracies: Some branch instructions are much more predictable than others. If we know that 80% of all executed branch instructions are easy-to-predict loop-back branches that are always predicted correctly, what is the accuracy of the 2-bit predictor on the remaining 20% of the branch instructions?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT What is the accuracy of always-taken and always-not-taken predictors for this sequence of branch outcomes?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT What is the accuracy of the two-bit predictor for the fi rst 4 branches in this pattern, assuming that the predictor starts off in the bottom left state from Figure 4.63 (predict not taken)?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT What is the accuracy of the two-bit predictor if this pattern is repeated forever?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT Design a predictor that would achieve a perfect accuracy if this pattern is repeated forever. You predictor should be a sequential circuit with one output that provides a prediction (1 for taken, 0 for not taken) and no inputs other than the clock and the control signal that indicates that the instruction is a conditional branch.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT What is the accuracy of your predictor from 4.16.4 if it is given a repeating pattern that is the exact opposite of this one?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT Repeat 4.16.4, but now your predictor should be able to eventually (after a warm-up period during which it can make wrong predictions) start perfectly predicting both this pattern and its opposite. Your predictor should have an input that tells it what the real outcome was. Hint: this input lets your predictor determine which of the two repeating patterns it is given.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions:
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions: Which exceptions can each of these instructions trigger? For each of these exceptions, specify the pipeline stage in which it is detected.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions: If there is a separate handler address for each exception, show how the pipeline organization must be changed to be able to handle this exception. You can assume that the addresses of these handlers are known when the processor is designed.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions: If the second instruction is fetched right after the first instruction, describe what happens in the pipeline when the first instruction causes the first exception you listed in 4.17.1. Show the pipeline execution diagram from the time the first instruction is fetched until the time the first instruction of the exception handler is completed.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions: In vectored exception handling, the table of exception handler addresses is in data memory at a known (fixed) address. Change the pipeline to implement this exception handling mechanism. Repeat 4.17.3 using this modified pipeline and vectored exception handling.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores how exception handling affects pipeline design. The first three problems in this exercise refer to the following two instructions: We want to emulate vectored exception handling (described in 4.17.4) on a machine that has only one fixed handler address. Write the code that should be at that fixed address. Hint: this code should identify the exception, get the right address from the exception vector table, and transfer execution to that handler.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. Translate this C code into MIPS instructions. Your translation should be direct, without rearranging instructions to achieve better performance.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. If the loop exits after executing only two iterations, draw a pipeline diagram for your MIPS code from 4.18.1 executed on a 2-issue processor shown in Figure 4.69. Assume the processor has perfect branch prediction and can fetch any two instructions (not just consecutive instructions) in the same cycle.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. Rearrange your code from 4.18.1 to achieve better performance on a 2-issue statically scheduled processor from Figure 4.69.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. Repeat 4.18.2, but this time use your MIPS code from 4.18.3.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. What is the speedup of going from a 1-issue processor to a 2-issue processor from Figure 4.69? Use your code from 4.18.1 for both 1-issue and 2-issue, and assume that 1,000,000 iterations of the loop are executed. As in 4.18.2, assume that the processor has perfect branch predictions, and that a 2-issue processor can fetch any two instructions in the same cycle.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
In this exercise we compare the performance of 1-issue and 2-issue processors, taking into account program transformations that can be made to optimize for 2-issue execution. Problems in this exercise refer to the following loop (written in C): \(\begin{array}{r}\text { for }(i=0 ; i !=j ; i+=2) \\\quad b[i]=a[i]-a[i+1]\end{array}\) When writing MIPS code, assume that variables are kept in registers as follows, and that all registers except those indicated as Free are used to keep various variables, so they cannot be used for anything else. Repeat 4.18.5, but this time assume that in the 2-issue processor one of the instructions to be executed in a cycle can be of any kind, and the other must be a non-memory instruction.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies.
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. How much energy is spent to execute an ADD instruction in a single-cycle design and in the 5-stage pipelined design?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. What is the worst-case MIPS instruction in terms of energy consumption, and what is the energy spent to execute it?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. If energy reduction is paramount, how would you change the pipelined design? What is the percentage reduction in the energy spent by an LW instruction after this change?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. What is the performance impact of your changes from 4.19.3?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. We can eliminate the MemRead control signal and have the data memory be read in every cycle, i.e., we can permanently have MemRead=1. Explain why the processor still functions correctly after this change. What is the effect of this change on clock frequency and energy consumption?
Read more -
Chapter 4: Problem 4 Computer Organization and Design 5
This exercise explores energy efficiency and its relationship with performance. Problems in this exercise assume the following energy consumption for activity in Instruction memory, Registers, and Data memory. You can assume that the other components of the datapath spend a negligible amount of energy. Assume that components in the datapath have the following latencies. You can assume that the other components of the datapath have negligible latencies. If an idle unit spends 10% of the power it would spend if it were active, what is the energy spent by the instruction memory in each cycle? What percentage of the overall energy spent by the instruction memory does this idle energy represent?
Read more