CPSC220: Introduction to Computer Architecture (Fall 2014)

Assignment #8

Due at the start of class on Friday, 11/21/2013

Reading and Tools

In our class meetings this week (and next week, too), we have studied the construction of a simple, one instruction per clock cycle data path for a subset of the MIPS 32-bit ISA. The instruction set we are considering consists of operations for arithmetic and logic (add,sub,and,or, and slt), for loading from and storing to a main memory (lw and sw), and support for conditional and unconditional jumps (beq and j).

We have focused our efforts on dividing the data path into individual modules whose abstractions will allow us to compose them together in a finished project. In this assignment, you'll implement simulations for all of our work to date.

Here, at a high level, is what we've built so far:

Your job

  1. Instruction Selection. In class, we divided this into two "components". On the one hand, we have INSTR. SELECTION, which includes the program counter (PC), the instruction memory, and the mechanism for advancing the address of the next instruction ("pc + 4"). Along with this is the circuit (at top on the diagram) for computing the next address to write to the PC. This component has as inputs the 32-bit PC+4 value, the low order 26 bits of the current instruction (the jump target), and the value of the current instruction's 16-bit immediate field. It also has a pair of one-bit control inputs, PCSrc (which controls whether the sequential (0) or branch address (1) value is used) and Jump (which controls whether the jump target value is used).

    Implement these components, according to the techniques we covered in class.


    • For now, just make the control input lines as inputs. We'll worry about connecting them to an actual instruction when we study control.

    • In Logisim, the component you want for the instruction memory is a RAM (look under the Memory tool menu). Set the "address bit width" to 24 and the "data bit width" to 32.

      Note that 24 bits is the largest possible address size, but that we're working with 32-bit addresses. This is a fundamental limitation of Logisim, which has selfishly refused to provided an unlimited supply of objects each equal in size to the the total resources of some personal computers. There's no way around this. Just drop the 8 high-order bits, and we'll pretend that all addressing happens to the low-order 224 bytes. (Actually, this is not unrealistic, since in a real machine, programs and data all reside in the memory addressing space.) Also, addressing in Logism RAM components is by word, not byte, so you'll need to divide the MIPS address by 4. Here's the "hack circuit" I gave in class:

      (That's a slight correction from class, where I dropped the upper bits before shifting. Shifting first gives you 4 times the addressing range.)

    • You can (and should) test your work by loading instructions for a program into the instruction memory and watching the instructions output in sequence with each clock edge. See the entries for the RAM component and for "poking memory", in the online User's Guide. You won't be able to run an actual program yet, but you should be to determine whether the next-address calculation is working correctly.

    • In class, I showed how the 16 bit immediate field value is sign-extended to 32 bits, before multiplying it by 4 and adding that to the PC+4 value. All of that is hidden by the abstraction of the diagram above. However, the REGISTERS/ALU component must also use the 32 bit sign-extension of the immediate field. To avoid redundant circuitry, you can (and should) use a single bit extender for both inputs.

  2. The Registers and Arithmetic/Logic Instructions. This section of the data path consists of the register file and the ALU. Its abstraction is given by the rightmost component in the figure above.

    Implement this component, sufficient to support the instructions add, sub, and, or, and slt. In addition to the obvious correctness requirements regarding the selection of registers for reading and writing, your component must support the correct ALUOp values, as documented in Section 4.4 and in Appendix B of P&H (yes, this is just a re-statement of Lab #6).


    • In Assignments #6 and #7, you built your own 32-bit register file and 32-bit ALU, both of which are, in principle, adequate to the job here. Indeed most of this task consists of connecting those two major components together, though you'll have to deal with subtleties such as selecting the inputs for ALU. See also my comment above about handling the sign-extended immediate field value.

      You're also welcome to use my solutions for either the register file or the ALU, though you don't need it, if yours is working correctly. I encourage you to refer to mine as a study reference only. Besides it's much more satisfying to use your own.

    • Unlike the instruction selection component, our work for this part is still in progress. In particular, we have not addressed the role of arithmetic and logic operations in implementing the load and store operations, nor the use of this component in determining whether a branch is taken. If you find that the abstraction given here is incomplete or can be improved (adding additional control signals as inputs, consolidating or modifying input output lines, etc.), feel free to do so. Just make sure that the abstraction you design is clear (i.e. save this component as a sub-circuit, separate from other components in the datapath).

      Similarly, we have not studied the implementation of control signals in the datapath. The 1-bit RegWrite, ALUSrc, and 4-bit ALUOp controls will eventually be connected to a control unit, but for now, you can just leave them as inputs.

      If your curiosity and ambition lead you to try either or both of these (i.e., the lw/sw instructions, or the control unit, know that your effort will not be wasted, as these problems will arise in the next assignment.

  3. Instruction Decoding

    In Lab #4, you wrote a disassembler, which decoded a MIPS instruction by extracting the appropriate fields from each 32-bit instruction value. To connect the next instruction to the REGISTERS/ALU part of the data path, you'll need to do something similar here, though the task is a bit easier: just break out the appropriate bit fields using splitters and connect them to the right places. This is clearly diagrammed in our text (see Fig. 4.24).

    Some fields won't yet have anything to connect to. Just render those as outputs for now.

To hand in your files: