10

Reading and Writing Assignments, Discussion Topics
COS/ELE 375

for class on Wednesday Oct. 20, 2010


Although the single-cycle MIPS design we've been looking at (Figure 4.17, e.g.) is a sound pedagogical stepping stone on the road to pipelined implementations, it is a very unsound example of sensible engineering tradeoffs. It occupies a peculiar position in the space of possible MIPS implementations: it is both very large and very slow. It has two memories and three ALUs, and its cycle time must be long enough for the longest path used by any instruction, which is probably a load. This means that every instruction must take this long to execute, even ones whose own longest logical paths aren't nearly as long as this cycle time.

Pipelining (which we'll explore after fall break) will fix the speed problem, but will still require lots of hardware. Let's go the other way: let's put together a design that economizes on the hardware. We'll make a datapath that has just one memory and one ALU. (It will still need the register file and a few other special registers like PC, and doubtless a passel of multiplexers.) This will mean multiple trips through the datapath--multiple cycles, in other words--for every MIPS instruction, but the cycle time can be much smaller than in the single-cycle design. For an old idea on how to control such a thing, please read the 1951 paper by Maurice Wilkes (him again!), modestly titled "The Best Way to Design an Automatic Computing Machine". Skim the first page, and focus on the second and third, starting in the left column of the second page with the phrase "It remains to consider the control proper". Some translations of antique terminology: "store" means the memory; "order code" means the instruction set; and an "order" is an instruction.

Please turn in a written response to this question:

1. At a high and abstract level, sketch the datapath for a multi-cycle MIPS implementation. You get one memory, one ALU, one register file, a PC, and Instruction Register, and as many muxes as you like. Just show what should get connected to what, and don't worry too much about any extra registers you might need. For example, since the one and only ALU will have to do PC+4, the PC should be connected to the input mux on one side of the ALU, and the constant 4 should be connected to the other. (We're not looking for a complete and detailed design--just a sketch. You may anticipate lenient grading.)

Then, be prepared to discuss the following in class:

2. Assume that all the following things will take one cycle each: reading the memory, writing the memory, reading the register file, writing the register file, and using the ALU. Assume that reading or writing the PC and IR, and going through multiplexors, take no time. What sequence of Wilkes-style micro-orders would you use to execute a MIPS add instruction? A load instruction? Here's the first one for both:

IR = Memory[PC]; PC = PC+4

Note that even though memory reading and PC incrementing each take a cycle, they can be done in the same cycle because they use different units.

3. In the single-cycle design, all of the state was programmer-visible: memories, registers, and PC. But the multi-cycle design will need some extra state to hold temporary results: the Instruction Register, for example, is needed both because the PC will get changed early and because the memory address will change if the instruction is a load or a store. What other registers do you think might be needed? Can you come up with a general rule that explains the need for such registers?