(MUST DO) A Closer Look at the Control Unit

Objectives

• Describe the state diagram for the Fetch and Decode phases of the LC-3 instruction cycle and for 13 of the 15 LC-3 instructions.

• Describe the inputs to the control unit, which determine which state transition the LC-3 will take.

• Describe the purpose of 19 of the 42 control signals.

Video Notes

• The control signals DRMUX and SR1MUX are probably new; they control which value is sent to the "DR" and "SR1" ports of the register file, since where the LC-3 is supposed to find that information changes for certain states. For example, in order to execute the JSR(R) instruction, R7 has be to loaded with the current value of the PC. To do this, DRMUX has to select "7" as the value to go to "DR", not IR[11:9] (see below).

Additional Resources

• "Introduction to Computing Systems", Sections C.1-C.3

Exercises

• End-of-chapter exercises 5.51

• Pick a state and list the values of the pertinent control signals for that state.

• Pick a control signal and a value and list the states for which that control signal takes on that value.

• Which instruction takes the fewest clock cycles and how do you know? Which takes the longest? Does your answer change if accessing memory takes 5 clock cycles instead of 1, as you may have just assumed?

(MUST DO) Hardwired vs. Microprogrammed

Objectives

• Describe the operation of a microprogrammed FSM and of a microprogrammed FSM with sequencer.

• Compare and contrast hardwired FSMs, microprogrammed FSMs, and microprogrammed FSMs with sequencers.

Video Notes

• I noticed only after I recorded the video above that the microprogrammed FSM with sequencer that I discuss has some superfluous elements! Owing to the fact that the sequencer implements both a "Branch taken" and a "Branch NOT taken" field, there isn't really a need for both "PB" and "~PB", "0" and "1", etc. For example, notice how the two rows of the mircoprogrammed FSM below both encode the same thing!

A simpler implementation is shown below, requiring only 2 bits for the "Condition" field instead of 3.

Additional Resources

• "Microprogrammed FSMs" (All About Circuits)

• "Basic Computer Architecture", Sections 8.3 and 8.4

• "Microprogrammed Architectures" (University of Maryland, Baltimore County)

Exercises

• Find an FSM problem from EE360, or make up one of your own, and convert it to a microprogrammed FSM either (1) without a sequencer or (2) with a sequencer. Build your design in Logisim and test it.

• In the video I showed one way of rewriting a state diagram with a transition that was one input ANDed with another. Can you think of any other ways to do this with the sequencer shown? How would you encode a transition that was one input ORed with another?

• There are lots of different ways to design sequencers that encode state transitions. Can you think of another one?

(MUST DO) Implementation of the Control Unit

Objectives

• Describe the operation of the microprogrammed FSM and sequencer that are in the LC-3 Control Unit.

• Show the reasoning behind the state numbers.

• Describe the Control Store.

Additional Resources

• "Introduction to Computing Systems", Sections C.4 and C.8

• "Basic Computer Architecture", Sections 8.5-8.8

Exercises

• Write out the entries in the Control Store that would be required to implement the subtract instruction from the end-of-chapter exercise 5.51.

• Is it possible to use this sequencer to specify a transition based on two or more inputs? If so, explain how. If not, explain how the sequencer could be modified to support this.

• Pick a new state from the state diagram and write out the values for J, COND, and IRD that would be in the Control Store for that state.

(SHOULD DO) Implementation of the Address Control Logic

Objectives

• Describe the truth table for the Address Control Logic

Additional Resources

• "Introduction to Computing Systems", Section C.6

Exercises

• Draw the circuit to implement the Address Control Logic on paper or in Logisim (where you can test it!). Does your design easily scale to the possibility of many more peripheral devices?

• What would happen if the LC-3 attempted to read from or write to an address in the HW page (xFE00-xFFFF) that didn't correspond to an actual hardware register like KBSR or DDR? Do you think this is what should happen? If not, what would you need to change about the current design of the LC-3 for it to do what you do think should happen?

(MUST DO) TRAP, Interrupt, and Exception Control

Objectives

• Describe the 6 paths in the Control Unit state diagram that implement TRAP, interrupt, and exception control.

• List and describe the 3 types of exceptions in the LC-3.

Video Notes

• As mentioned at 8:15, there's a typo in State 45. It should read "Saved_USP <-- SP" and "SP <-- Saved_SSP".

Additional Resources

• "Introduction to Computing Systems", Section C.5 and C.7

Exercises

• Pick a state from Figure C.7 and list all of the active control signals for that state.

• Pick a control signal and list all of the states where that control signal is active.

• Pick a logic element from Figure C.8 and list the states where that element is used.

• Using multiple copies of the datapath from Figure C.8, draw out how the LC-3 processes the TRAP instruction, the keyboard interrupt, or the three exceptions.

• Can you think of any other types of exceptions that would be useful to implement in the LC-4?

• Say that many, many more IO devices are added, each with an associated interrupt signal. Does the state machine need to change to accommodate these new interrupts? What about the datapath shown in Figure C.8? Justify your answers.

• Open the LC-3 Simulator and find the OS service routines that handle each of the three exceptions. What do they do? Can you think of any way to improve them or to improve the way the LC-3 handles exceptions?

• Open the LC-3 Simulator and notice that every entry in the TRAP vector table that isn't associated with an actual TRAP routine (i.e. x00-x1F and x26-xFF) directs to "BAD_TRAP" and every entry in the interrupt vector table that isn't associated with an actual interrupt service routine directs to "BAD_INT". What do those two routines do? Can you think of any way to improve them or to improve the way the LC-3 handles those exceptions?

(SHOULD DO) The Completed LC-3

Objectives

• Describe the LC-3 in its entirety.

• Identify whether certain features are part of the LC-3 architecture or it's organization.

Exercises

• Which aspect of the LC-3 (e.g. a certain instruction, handling interrupts, privileged memory, etc) do you think makes the design the most complicated? What features would you lose if you decided not to implement that part of the LC-3 and would losing that feature mean that you're no longer implementing the full LC-3 ISA? Given your answers, do you think it would be worth it to pursue eliminating that feature?

• In your opinion, what's the best way to improve the LC-3 (e.g. change the word size to 32-bit, allow for larger memory, add other useful instructions, add more registers, incorporate additional IO, etc)? How difficult would that be to implement and, given your answer, do you think it would be worth it to pursue?

• If you completed the "Turing Machines" lesson, you'll know that every Universal Turing Machine (UTM) has exactly as much computing "power" as any other UTM and this can be proven by using a UTM to simulate another UTM. Because of this we can say that the LMC is exactly as "powerful" as the LC-3, even for it's dearth of features, since it can be proven that the LMC can simulate the LC-3. Try to prove this by taking an instruction or feature in the LC-3 and showing how the LMC could simulate that instruction or feature. For an extreme challenge, read about a category of computers called "one instruction set computers" (OISCs; try here or here first) and show how they, too, can simulate the LC-3!

• Consider the scenarios below and then answer each of the following questions with respect to each scenario.

  • Scenarios

    • A proposed update to the LC-3 uses opcode 1101 to do something useful instead of cause an illegal opcode exception.

    • A computer manufacturer decides to miniaturize the LC-3 by packaging it with only half of the original memory (all memory regions are simply reduced by half).

    • A computer manufacturer wants to help future-proof the LC-3 so they build it exactly as it’s shown in the book with the exception that all registers and memory are now 32-bits wide instead of just 16-bits wide.

  • Questions

    • Does this scenario constitute a change to the architecture or to the organization of the LC-3?

    • Will programs written for the LC-3 without this update run correctly on the new machine? Why or why not?

    • Will programs written for the new machine run correctly on previous implementations of the LC-3? Why or why not?

• If the value of a control signal truly does not matter, than put a "don't care" (i.e. "x") in the Control Store. Otherwise, put down either a 0 or a 1.

• Here are some tips for you:

  • None of the registers should randomly load new pieces of data, so none of the "LD.xxx" signals should be "don't cares". Multiple "LD.xxx" signals can be 1 at the same time.

  • Only one device should ever be putting data on the processor bus at a time, so only one of the "GateXXX" signals should ever be 1 in each state and the rest of the signals should be 0.

  • If the output of a mux or the ALU isn't used (i.e. the corresponding "GateXXX" or "LD.xxx" signal is 0), then the control signal to that mux or to the ALU probably doesn't matter.

  • "MIO.EN" is set to 1 in the specific state when the Control Logic is actually trying to read or write from memory/IO. It's not set in the preceding states when MAR (and possibly MDR) are being loaded with the appropriate values. "R.W" tells the memory/IO section whether the memory operation taking place is a read or a write; it's value doesn't matter if "MIO.EN" is 0.

• Use this form to test whether each of your states have been encoded correctly. Take note of the directions at the top!

• Additionally, you may find it helpful to observe the microarchitecture simulator in-action as you're figuring out each of the control signals. I won't say that it's 100% accurate (the LEA instruction incorrectly updates the NZP register, for example) and it won't handle any TRAP calls, interrupts, or exceptions, but it may still be a good resource.

Going Further

• Change opcode 1101 (13) so that it performs a useful function. Which operation do you think you should implement? How does the Control Store need to change in order to implement that operation?

• Tragedy has struck and the ADDR1MUX is broken! It only outputs the PC, never BaseR. Is it possible to modify the Control Logic to work around this problem, either by (1) using different control signals in the same state or (2) adding states to the Control Store that have the same effect as the affected states? Can you do it without changing the size of the Control Store?

What to Submit

• Your completed Control Store in CSV format, named according to the following format: "Lab4_<LastName_Partner1>_<LastName_Partner2>_<LastName_Partner3>_<LastName_Partner4>_<Section>.csv".