2003 Fall

CIS-2233 Machine Org


Dr. Tom Pittman tpittman@sbuniv.edu
Taylor 108, 1p.M-F 328-1562

SBU policy is that they own the Syllabus; other material is the property of the instructor who prepared it.
 

Resources

Gate Simulator
Test Data for Decimal Adder
TinyMIPS in GateSim
Simple Computer
 

Class: 2-2:50, MWF Taylor 222
Final: Dec.16, 1pm

Assignments, Due:

Dec.5: Term Projects, turn in a block diagram showing how your circuit works and a detailed schematic with matching GateSim source listing, with sufficient trace output to show that you adequately tested your circuit. Turn in MIPS/SPIM assembly listing(s) of the programs you tested your circuit with. Be prepared to explain to the rest of the class in 10 minutes what you did and generally how it works. Choose one of the following and sign up for it on the sign-up sheet:
1.  3-port Register File. Design and implement a 32-register x 32-bits block of registers that can simultaneously read any two registers and write any register. Show how to connect it into the TinyMIPS circuit so that (apart from carry propagation delays) the ALU operations can execute in a single cycle. You will probably need to do this with flip-flops instead of the present memory, and you will need to adjust the microcode timing to reduce 3-cycle operations to 1-cycle.
2.  Look-ahead Carry. Design and implement a look-ahead carry part that you can use to reduce the present 64-gate-delay carry propagation to something less than 7 gate delays, so that add/subtract/compare operations take about the same time as logic operations. Adjust the microcode sequences as necessary to achieve this timing.
3.  Pipeline. Design and implement a pipeline execution unit, so that a new instruction starts every clock cycle. You might find it convenient to work with whoever does #1 (3-port register file) or #4 (state-machine sequencer), because of the need to eliminate the present microcode sequencer.
4.  State Machine Sequencer. Redesign the current microcode sequencer to use a finite-state machine (FSM) instead of the present microcode. Verify that all programs still work correctly, and determine if your FSM sequencer is faster than the microcode.
5.  Hardware Multiply. The current TinyMIPS circuit implementation has no multiply hardware. Your enhancement would implement a 32-bit signed multiply instruction (mult/multu) which starts when the instructioin is issued, then runs asynchronously until it finishes, leaving the product in the Hi and Lo registers.
6.  Hardware Divide. The current TinyMIPS circuit implementation has no divide hardware. Your enhancement would implement a 32-bit signed divide instruction (div/divu) which starts when the instructioin is issued, then runs asynchronously until it finishes, leaving the quotient and remainder in the Hi and Lo registers.
7.  Floating-Point Coprocessor. The current TinyMIPS implementation has no provision for any coprocessors like floating-point (FP). Your project is to add the necessary circuitry to make a FP engine work. This includes implementing the (almost trivial) FP instructions mfc1, mtc1, bc1t, bc1f, c.eq.s, c.le.s, and c.lt.s. Note that you can do the compares without regard to the FP format as if they were sign-magnitude integers and get the correct result. Extra credit will be given for finishing early.
8.  Floating-Point Add. This requires some collaboration with whoever does #7 Floating-Point Coprocessor. Your task is to implement a FP addition and subtractioin (add.s and sub.s) and the two converts (cvt.s.w and cvt.w.s, which use much of the same logic).
9.  Floating-Point Multiply. This requires some collaboration with whoever does #7 Floating-Point Coprocessor. Your task is to implement a FP multiply instruction (mul.s).
10. Barrel Shifter. Implement a full 0-31-bit shifter in either direction, so that it executes in one cycle. Adjust the microcode so it knows about your instructions (sll, sllv, srl, srlv, sra, and srav).
11. Instruction Cache. Build a cache memory that  reads ahead the next few words of ROM memory, so that the next instruction is probably already in the cache when needed. Make sure you keep several words already executed, in case of small loops. For extra credit, decode unconditional jumps to continue fetching from the jumped address, essentially removing them from the instruction stream.
12. Data Cache. Build an associative memory cache which retains recently accessed RAM data with its addresses, and eliminates redundant reads from memory. Be sure to write data stores through the cache to main memory.


Oct.27:  Design, using full adders, counters, and/or such other gates as are necessary, an 8x8 (unsigned) multiplier. Test it with at least two different (interesting) products, for example 123*57; note that 2*4 is not an interesting product (there is only one bit in the product, and the product does not extend past 8 bits). Turn in a schematic diagram, plus a listing of the source file showing the inputs to GateSim, plus enough of the output trace to show that you fully tested it.

Extra credit: Use Booth's Algorithm to do a signed 8x8 multiply.

Oct.15:  Design, using full adders and/or such other gates as are necessary, a one-digit decimal adder (four-bit Binary-Coded-Decimal "BCD" inputs, with a pure (4-bit BCD) decimal output and a correct carry. Turn in a schematic diagram, plus a listing of the source file showing the inputs to GateSim, plus enough of the output trace to show that you fully tested it for all 100 valid inputs. Note that you will need to use one or more counters to sequence through all possible input values to your circuit.

Oct.8: Ch.4, #4.14, 4.17, 4.40

Sep.22:

a.  Write (in Java) a binary multiply method which keeps all data values in arrays of boolean (or ints with values between 0 and 1). Show that you tested it with at least two different products, including for example, the values we multiplied in class (27*43):
int[] multiplicand = {0,0,0,1,1,0,1,1} /*27*/
int[]   multiplier = {0,0,1,0,1,0,1,1} /*43*/
b.  Write (also in Java) a binary multiply method using the same algorithm, but which keeps all data values packed into integers, and uses only the following operators (that is, no built-in multiply):
=  +  >>1  %2  !=0  ==0
c.  Translate your Java program in (b) to MIPS assembly language and run it in SPIM. Turn in a listing that shows you succeeded.


Sep.15: Ch.3, #3.5, 3.8, 3.11, 3.16

For 3.11, you may assume the code fragment is really Java, and that you can use the 'Load Address' pseudo-instruction (see p.A-65) to load registers $a0 and $a1, for the following data (corrected):
  .data
b:
  .word  5,67,16,87,17,29,68,56,42,67
  .word  14,65,81,94,32,95,32,18,76,96
  .word  54,63,32,33,30,2,20,10,14,74
  .word  67,56,66,49,6,5,42,63,40,89
  .word  26,83,23,47,75,14,10,33,84,7
  .word  7,8,34,31,72,32,92,12,87,92
  .word  26,49,20,40,46,7,56,88,97,72
  .word  6,89,68,73,17,84,75,77,61,6
  .word  25,9,37,87,42,9,66,9,67,97
  .word  61,64,19,20,53,50,26,24,23,53
  .word  85
a:
  .space 404


Sept.5: Ch.2, #2.3, 2.13, 2.18
 
 
 

Back to T.Pittman home

Rev. 2003 November 21