Enjoy this GIF of Carlton dancing. You've earned it.

Video Notes

• The throughput of a pipeline is equal to one over the time required for the longest stage. In the car factory, the longest stage was "Paint" so the throughput of that pipeline was 1/(2.5 hrs). In the 4-bit adder, the longest stage was a 3-way tie with each of the full adders so the throughput of that pipeline (not forgetting to account for the propagation delay and setup times of the D flip-flops!) was 1/(30 ns).

• As a consequence of the note above, the latency of a k-stage pipeline is equal to k * the longest stage, not simply the sum of the delays from all the pipeline stages, as I incorrectly state in the video. Since no stage can advance until the longest stage has finished executing, all stages in a pipeline effectively take as long as the longest stage.

  • Thus, the correct latency of the car factory should be 10 hours (4 stages * 2.5 hours for the longest stage [Paint]).

  • Also the correct latency of the 4-bit adder should be 120 ns (4 stages * 30 ns for the longest stage [full adder with D flip-flops])

Additional Resources

• "Basic Computer Architecture", Section 9.1

• Latch delays when pipelining (the data for the graph from the notes)

• The Why and How of Pipelining in FPGAs (All About Circuits)

• Pipelining Digital Logic In FPGAs (Hackaday)

Exercises

• Assume each stage from the factory example in the notes has the new delays listed below. What's the new latency? Throughput? What would be the ideal throughput for a pipelined factory? What is the actual throughput if the factory were pipelined? Why are those last two numbers different?

  • Chassis: 3 hrs

  • Engine: 1 hr

  • Body: 1.25 hours

  • Paint: 2.5 hours

• Assume that, in a more realistic factory, it takes a car 15 minutes to move from one stage to the next. Update your values above given this additional constraint. Draw a graph like the one in the notes that shows the theoretical limit to the improvements that could be gained from additional pipeline stages (assuming one could add them).

• What are realistic values for the propagation delays and setup times of a half-adder, full-adder, and D flip-flop? How much of a speed-up would be gained for the example circuit using those values? What if the adder were 32- or 64-bits wide?

• For the two examples in the notes (car factory and 4-bit adder), state what the idealized speed-up from pipelining should be and explain in your own words why those values aren't achieved.

Video Notes

• To keep things simple, we'll also not show how a pipelined LC-3 would handle TRAPs, interrupts, or exceptions.

• The register file can appear twice in our LC-3 pipeline only because it has separate ports for reading and writing, meaning that we can read from the register file at the same time as we are writing to it. Thus, we can have separate "Read register" and "Write register" stages in our pipeline without any structural hazards. If, on the other hand, a certain instruction were to read from or write to the registers twice during its execution then we would either need to make separate stages for each read/write (e.g. "1st read register" and "2nd read register" stages) or we would need to add additional read/write ports on our register file (e.g. "DR1" and "DR2" for multiple register writes).

• Technically the STR instruction poses a structural hazard, since both "SR" and "BaseR" are read from SR1. There's an easy fix for this (to see it, take a look at "Pipelining the LC-3, v2"). For now, you can take my word that STR doesn't pose any structural hazard.

• @05:30: The LDR instruction reads it's base register from the register file, not the "offset", as I incorrectly say.

• @08:40: After considering this some more, I think this is not an example of a Harvard architecture, despite the fact that the instructions and data may live in separate memory components. This is because the memory space, as defined by the LC-3 ISA, is shared between instructions and data; there is only one value that lives at memory space xABCD in the LC-3 and it's either an instruction or a piece of data. In a true Harvard architecture, there may very well be one value (an instruction of some kind) at location xABCD in the instruction memory and an entirely different value (a piece of data) at location xABCD in the data memory.

Additional Resources

• "Basic Computer Architecture", Sections 9.2 and 9.4.4

Exercises

• Define "structural hazard" in terms a non-EECS friend could understand.

• For the LD, ST, JMP, and JSR instructions, list the components used by each. Confirm that there wouldn't be any structural hazards for any combination of these instructions (including the ones depicted in the notes, ADD/AND/NOT/LDR/LEA/BR) in our pipeline by showing that each instruction uses the Fetch, Read register, Evaluate address, Execute, and Write register components exactly once (or not at all) and exactly in that order.

  • Note: STR is conspicuously left out in the list above, owing to the fact that there is a little extra work we would need to do in order to remove the structural hazard it presents. Take a look at "Pipelining the LC-3, v2" to see how!

• The "ALU" and "Access memory" blocks are placed in the same stage of the pipeline (stacked on top of each other) instead of in separate stages (placed next to each other with a register in between them). Why does this not result in a structural hazard?

• Consider the "stack protocol" program from Figure 8.11 of "Introduction to Computing Systems". If ADD R2,R6,R1 on Line 0B is being fetched from instruction memory in a pipelined version of the LC-3, which instructions are in the other four stages? Prove that there are no structural hazards by labeling which parts of the LC-3 datapath are being used for each instruction (you can use the datapath diagram from "Introduction to Computing Systems" for this, with the assumption that the functional units you're annotating are connected like the pipeline shown in the notes, as opposed to being connected to the processor bus like they are in the diagram).

• Assume that the delay from each of the pipeline stages is as shown below.

  • What's the latency of this pipeline?

  • What's the throughput of this pipeline?

  • 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 throughput of the processor?

• What is the minimum number of cycles needed to completely execute n instructions on a CPU with a k stage pipeline? Justify your formula.

• An intrepid computer engineer suggests adding the instructions below to the LC-3 ISA. For each new instruction, answer the following questions:

  • Which components might this new instruction use and in which order?

  • Based on your answer to the question above, does this new instruction pose a structural hazard to the current pipelined implementation of the LC-3?

  • If the answer to the question above is "Yes", how could you modify the pipelined LC-3 to remove the structural hazard?

• Add STI, LDI, TRAP, RTI, interrupt handling, or exception handling to the pipeline depicted in this lesson.

Additional Resources

• "Basic Computer Architecture", Sections 9.2 and 9.3 (the SimpleRISC processor mentioned in these sections is described in Chapter 8 of this textbook).

Exercises

• Finish the Control Unit truth table for the remaining 11 instructions (not including TRAP or RTI).

• Answer the question from the last lesson about adding "Swap" and "Store Sum" instructions to the LC-3 if you haven't already. This time, modify the version of the LC-3 shown in this lesson in order to remove any structural hazards. Additionally, list the control signals required to implement those new instructions.

• Go back to the "stack protocol" program from Figure 8.11 of "Introduction to Computing Systems". Assuming, again, that the ADD R2,R6,R1 instruction on Line 0B is being fetched from instruction memory, annotate which instruction is in which other stage of the pipeline and fill in appropriate values for each signal in the processor to show what each component is doing.

• Continuing the exercise from above, advance the pipeline by one instruction (i.e. so that Line 0C is now being fetched from memory) and repeat the process of annotating each signal in the processor.

• Add TRAP, RTI, interrupt handling, or exception handling to the pipeline depicted in this lesson.

• Pick a control signal from the last page of notes.

  • Which instructions fail to execute correctly if that control signal is "stuck at 0"?

  • Which instructions fail to execute correctly if that control signal is "stuck at 1"?

• In this pipeline the PC value comes from the "Execute" stage. What error would occur if the value of the PC came from an earlier stage?

Additional Resources

• "Basic Computer Architecture", Sections 9.4.1, 9.4.2, 9.5.1, 9.6 (intro), and 9.6.2

Exercises

• Assume that R1 is initialized to 11 and R2 is initialized to 22. Suppose you executed the code below on a pipelined version of the LC-3 that does not have a Datalock Unit (i.e. it is susceptible to RAW hazards). What would the final values of registers R3 and R4 be? How many NOPs would be inserted by the Datalock Unit to eliminate the RAW hazard(s) from this code snippet and where would they be?
  ADD R1, R2, #5
  ADD R3, R1, R2
  ADD R4, R1, #15

• How many NOPs would be inserted by the Datalock Unit to eliminate the RAW hazard(s) from the code snippet below and where would they be?
  ADD R1, R2, #5
  ADD R3, R1, R2
  ADD R4, R1, #15
  ADD R5, R3, R2

• For one of the examples below, determine where it exhibits any RAW hazard. For each RAW hazard, state how the hazard would occur and how many NOPs would be inserted by the Datalock Unit to eliminate that hazard. What's the ratio of total instructions executed (including NOPs to eliminate the RAW hazards) to total assembly instructions in the program?

  • Figure 7.2

  • Figure 8.1

  • Figure 8.5

  • Figure 8.11 (note that this figure shows 2 subroutines: PUSH and POP)

  • Figure 8.14

  • Figure 8.16

  • Figure 8.18

  • Figure 8.19

  • Figure 8.27 (note that this figure shows 2 subroutines: INSERT and REMOVE)

  • Figure 8.30

  • Figure 8.32

• Design the digital logic to implement the Datalock Unit from this lesson.

• The instruction AND R3, R4, x0F is being stalled in the "Read register" stage. What can be said of any of the instructions in the "Evaluate address", "Execute", or "Write register" stages?

• Assume there is a STR instruction that is not stalled in the "Read register" stage while a LD instruction is being processed in the "Execute" stage. What can be said of the operands for these two instructions?

Additional Resources

• "Basic Computer Architecture", Section 9.7

Exercises

• Repeat the exercises above (from "Data Hazards 1") for a pipeline that includes bypassing. (Don't forget that we are using a 6-stage pipeline in this lesson as opposed to the 5-stage pipeline in "Data Hazards 1"!)

• For the questions below, consider a pipelined version of the LC-3 that does not have a Datalock Unit (i.e. it is susceptible to RAW hazards). Suppose that, after addressing these hazards by inserting NOPs in appropriate location (either in software or hardware), a typical n-instruction program requires an additional .4*n NOP instructions to correctly handle data hazards. (Each of the questions below counts as one of the four questions needed to get full credit for this lesson.)

  • Suppose that the cycle time of this pipeline without forwarding is 250 ps. Suppose also that adding forwarding hardware will reduce the number of NOPs from .4*n to .05*n, but increase the cycle time to 300 ps. What is the speedup of this new pipeline compared to the one without forwarding?

  • Different programs will require different amounts of NOPs. How many NOPs (as a percentage of code instructions) can remain in the typical program before that program runs slower on the pipeline with forwarding?

  • Repeat the question above; however, this time let x represent the number of NOP instructions relative to n. (In the previous question, x was equal to .4.) Your answer will be with respect to x.

  • Can a program with only .075*n NOPs possibly run faster on this pipeline with forwarding? Explain why or why not.

  • At minimum, how many NOPs (as a percentage of code instructions) must a program have before it can possibly run faster on this pipeline with forwarding?

Video Notes

• I'll use the term "branch" or "BR" often to denote not just the literal "BR" instruction but also any instruction which potentially changes the PC (i.e. JMP, JSR, and JSRR).

• Another strategy for removing control hazards, which I ran out of time for in this lesson, is "Fill the delay slots"; this is a SW only technique (or, more accurately, there's also a way to do this with HW, but it's far beyond the scope of this course). The spots after a branch that would otherwise be NOPs, which are called "delay slots", can sometimes be filled with the instructions that came before the BR, provided moving them doesn't affect program correctness. For example, the sample BR in this lesson could have been preceded by the instructions below, none of which set the condition codes so it's safe to move them after the BR.
  ST R3, VAL
  LEA R0, CHAR
  OUT
  BRzp NEXT
  The re-ordered instructions would look like this:
  BRzp NEXT
  ST R3, VAL
  LEA R0, CHAR
  OUT
  Since the 3 instructions following a taken branch are always executed anyways, this solution results in only as many cycle penalties as there are unfilled delay slots.

• I also think my discussion of branch penalties was a bit confusing. The correct table (including the new strategy discussed above) is below. Note that most branch instructions suffer a 3 cycle penalty, owing to the fact that by the time the LC-3 determines it needs to jump, there are already 3 instructions in the pipeline in the Fetch, Read Register, and Evaluate Address stages that need to be flushed.

Additional Resources

• "Basic Computer Architecture", Sections 9.4.1, 9.4.3, 9.5.2, 9.6 (intro), 9.6.1, and 9.6.3

Exercises

• For one of the examples below, determine where it exhibits any control hazard. For each control hazard, state how the hazard would occur and how many NOPs would be inserted by the Branchlock Unit to eliminate that hazard. State which strategy you're using and feel free to assume starting values for any of the registers, if needed. What's the ratio of total instructions executed (including NOPs to eliminate the control hazards) to total assembly instructions in the program?

  • Figure 7.2

  • Figure 8.1

  • Figure 8.5

  • Figure 8.11 (note that this figure shows 2 subroutines: PUSH and POP)

  • Figure 8.14

  • Figure 8.16

  • Figure 8.18

  • Figure 8.19

  • Figure 8.27 (note that this figure shows 2 subroutines: INSERT and REMOVE)

  • Figure 8.30

  • Figure 8.32

• Design the digital logic to implement the Branchlock Unit from this lesson.

• Consider a program for which 20% of the instructions are some kind of branch instruction (JMP/JSR/BR). Further, assume that 45% of those branches are taken when the program actually executes. What's the ratio of clock cycles per instruction (CPI) for two pipelines, one that uses Strategy #1 versus one that uses Strategy #1.5?

• Assume a program is written with the following composition of instructions and that Strategy #1.5 is used to eliminate control hazards. Further, assume that, when run, the Branchlock unit needs to flush the pipeline an average of 45% of the time.
  Operate/ALU instructions: 40%
  BR instructions: 25%
  JMP/JSR(R) instructions: 5%
  LDx/STx instructions: 30%

  • What's the ratio of CPI for this pipeline versus one with a perfect Branchlock unit that never needs to flush the pipeline?

  • What speedup would be achieved if we could convert half of the branch instructions to some ALU instruction? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced.

  • 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.

Additional Resources

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Section 9.11.1

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Sections 9.11.2 and 9.11.3

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Section 9.11.4

• The First Pipelined Computers (from "Computer Organization and Design, ARM edition")

Exercises

(MUST DO) Performance Improvements with Pipelines

Objectives

• Describe the performance equation for a computer

• Calculate the performance for a given combination of computer architecture and program

• Compare the performance of the standard LC-3 and the pipelined LC-3

• List two industry standards for comparing computer performance

• Describe the things that affect a computer's performance

Additional Resources

• "Basic Computer Architecture", Section

Exercises

• asdf

Additional Resources

• "Basic Computer Architecture", Sections 10.1.1-10.1.3, 10.1.7 (excluding "Performance Benefit of a Hierarchical Memory System"), 10.1.8, and 10.3 (intro)

• Memory Technologies (from "Computer Organization and Design, ARM edition")

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Sections 10.2.1, 10.2.3-10.2.7

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Section 10.2.2 ("Fully Associative (FA) Cache")

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Section 10.2.2 ("Direct Mapped (DM) Cache")

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Section 10.2.2 ("Set Associative Cache")

Exercises

• adsf

Additional Resources

• "Basic Computer Architecture", Sections 10.1.7 ("Performance Benefit of a Hierarchical Memory System") and 10.3.1

Exercises

• adsf

There is NO lab for Unit 5