CPSC 330 - Fall 2009
Program 2
Due by midnight on Wednesday, October 21
Turn in using "handin.330.1 2 <filename>".

(corrected 10/15/09)


You may work in whatever programming language you wish, and you
may work individually or in teams of at most two in size.

1. Write a program that simulates an extension of the simple
   microprogrammed CPU found in www.cs.clemson.edu/~mark/uprog.html

2. Write the microinstructions needed for the three additional
   instructions other than halt and include them in the control
   store for the simulator.

The instruction set is:

  ---basic instruction set---
  load  -- opcode = 000 -- acc <- mem[addr]
  add   -- opcode = 001 -- acc <- acc + mem[addr]
  store -- opcode = 010 -- mem[addr] <- acc
  brz   -- opcode = 011 -- if( acc==0 ) pc <- addr

  ---extended instruction set---
  sub   -- opcode = 100 -- acc <- acc - mem[addr]
  jsub  -- opcode = 101 -- mem[addr] <- updated pc; pc <- addr + 1
  jmpi  -- opcode = 110 -- pc <- mem[addr]
  halt  -- opcode = 111 -- halt

Execution of the machine language program always starts at address
0, and the halt instruction means halt the simulation.  (That is,
when the IR contains anything in the range 0xe00-0xfff.)

For the CPU of the simulated computer, there should be:

  9-bit registers: PC, MAR
  12-bit registers: IR, MDR, ACC, TMP

and for the microprogrammed control:

  32 x 22-bit control store
  5-bit CSAR
  22-bit CSIR

and for the memory:

  512 x 12-bit main memory

The instruction format is a 3-bit opcode followed by a 9-bit
address.  An example instruction is:

  memory-word 010 000001001
  bit #       012 345678911
                         01

    where bits 0-2  == 3-bit opcode
          bits 3-11 == 9-bit address field

    or, given as three hex digits

  memory-word 0x409

  (The example is "store 9", that is, store a copy of the value
  in the accumulator into the 12-bit memory word at location 9.)

The microinstruction format is similar to that given in Figure 6
of the web page, with three extensions:

 * an alu_sub signal (for subtraction) is included after the
   alu_add signal,
 * a 5-bit next control store address field (instead of a 4-bit
   field), and,
 * the decoding table is eight entries, each of size five bits 

All other signals are the same.  An example microinstruction is:

  cs-word 0000001000100000 00010 0

    or

  cs-word 0000001000100000  0x02 0 (with next cs addr as two hex
  bit #   0123456789111111 11112 2                       digits)
                    012345 67890 1

    where bit  0 == ACC_in
          bit  1 == ACC_out
          bit  2 == alu_add
          bit  3 == alu_sub
          bit  4 == IR_in
          bit  5 == IR_out
          bit  6 == MAR_in
          bit  7 == MDR_in
          bit  8 == MDR_out
          bit  9 == PC_in
          bit 10 == PC_out
          bit 11 == pc_incr
          bit 12 == read
          bit 13 == TMP_out
          bit 14 == write
          bit 15 == br_table
          bits 16-20 == 5-bit next control store address field
          bit 21 == or_addr

    (The example microinstruction is MAR_in, PC_out, and
    next_cs_addr=0x02.)

Registers should be initialized to 0, and the first 16 locations
of the control store should be set to contents similar to those
given in Figure 4 of the web page.  (That is, add the two extra
0 bits to each of the 20-bit microinstructions from the web page.)
The remaining 16 locations are for you to use to implement the
sub, jsub, and jmpi instructions.

  control store contents

  addr   control signals    next addr   or  control signal names
      +------------------+------------+---+
   0  | 0000001000100000 | 00010 (=2) | 0 | MAR_in  PC_out      decoding
   1  | 0000010001000000 | 00000 (=0) | 0 | PCin    IR_out        table
   2  | 0000000000011000 | 00011 (=3) | 0 | pc_incr read       opc   addr
   3  | 0000100010000000 | 00100 (=4) | 0 | IR_in   MDR_out       +-----+
   4  | 0000000000000001 | 00000 (=0) | 0 | br_table---------> 000|00101|
   5  | 0000011000000000 | 00110 (=6) | 0 | MAR_in  IR_out     001|01000|
   6  | 0000000000001000 | 00111 (=7) | 0 | read               010|01100|
   7  | 1000000010000000 | 00000 (=0) | 0 | ACC_in  MDR_out    011|01111|
   8  | 0000011000000000 | 01001 (=9) | 0 | MAR_in  IR_out     100| ... |
   9  | 0000000000001000 | 01010 (=a) | 0 | read               101| ... |
   a  | 0110000000000000 | 01011 (=b) | 0 | ACC_out alu_add    110| ... |
   b  | 1000000000000100 | 00000 (=0) | 0 | ACC_in  TMP_out    111| ... |
   c  | 0000011000000000 | 01101 (=d) | 0 | MAR_in  IR_out        +-----+
   d  | 0100000100000000 | 01110 (=e) | 0 | MDR_in  ACC_out
   e  | 0000000000000010 | 00000 (=0) | 0 | write
   f  | 0000000000000000 | 00000 (=0) | 1 | or_addr (low bit of next addr is
  10  | ...                               |      or'ed with ACC==0 condition)

  1f  | ...                               |
      +------------------+------------+---+

For input, you should read from stdin a list of memory words in
hex, ending with a sentinel of -1.

For output, you should print the initial contents of the first
few words of memory, a cycle-by-cycle trace of control signals,
and finally the ending contents of the first few words of memory.

The cycle-by-cycle trace should include the contents of all six
control and datapath registers, along with the CSAR and CSIR,
prior to the execution of the microinstruction for that cycle.
The CSIR should be printed bit-by-bit except for the next
address field.

For the following simple program, the simulator should produce
the appended output.  (You can change the output format, but at
least the same amount of information should be printed.)


example program (using only basic instruction set and halt):

        load  a
        add   b
        brz   zero
        add   b
        brz   zero
        add   b
  zero: store c
        halt

  a:    .word 2
  b:    .word -1
  c:    .word 5


input (after hand assembly):

  8 209 606 209 606 209 40a e00 2 fff 5 -1


simulator output:

  low memory:    8  209  606  209  606  209  40a  e00    2  fff
                 5    0    0    0    0    0    0    0    0    0

  cycle  PC  IR MAR MDR ACC TMP  CSAR          CSIR            cntl signals
       +---+---+---+---+---+---+/----//---------------------//---------------/
     1:   0   0   0   0   0   0     0  0000001000100000|02|0  MAR_in PC_out
     2:   0   0   0   0   0   0     2  0000000000011000|03|0  pc_incr read
     3:   1   0   0   8   0   0     3  0000100010000000|04|0  IR_in MDR_out
     4:   1   8   0   8   0   0     4  0000000000000001|00|0  br_table
     5:   1   8   0   8   0   0     5  0000011000000000|06|0  MAR_in IR_out
     6:   1   8   8   8   0   0     6  0000000000001000|07|0  read
     7:   1   8   8   2   0   0     7  1000000010000000|00|0  ACC_in MDR_out
       +---+---+---+---+---+---+/----//---------------------//---------------/
     8:   1   8   8   2   2   0     0  0000001000100000|02|0  MAR_in PC_out
     9:   1   8   1   2   2   0     2  0000000000011000|03|0  pc_incr read
    10:   2   8   1 209   2   0     3  0000100010000000|04|0  IR_in MDR_out
    11:   2 209   1 209   2   0     4  0000000000000001|00|0  br_table
    12:   2 209   1 209   2   0     8  0000011000000000|09|0  MAR_in IR_out
    13:   2 209   9 209   2   0     9  0000000000001000|0a|0  read
    14:   2 209   9 fff   2   0     a  0110000000000000|0b|0  ACC_out alu_add
    15:   2 209   9 fff   2   1     b  1000000000000100|00|0  ACC_in TMP_out
       +---+---+---+---+---+---+/----//---------------------//---------------/
    16:   2 209   9 fff   1   1     0  0000001000100000|02|0  MAR_in PC_out
    17:   2 209   2 fff   1   1     2  0000000000011000|03|0  pc_incr read
    18:   3 209   2 606   1   1     3  0000100010000000|04|0  IR_in MDR_out
    19:   3 606   2 606   1   1     4  0000000000000001|00|0  br_table
    20:   3 606   2 606   1   1     f  0000000000000000|00|1  or_addr
       +---+---+---+---+---+---+/----//---------------------//---------------/
    21:   3 606   2 606   1   1     0  0000001000100000|02|0  MAR_in PC_out
    22:   3 606   3 606   1   1     2  0000000000011000|03|0  pc_incr read
    23:   4 606   3 209   1   1     3  0000100010000000|04|0  IR_in MDR_out
    24:   4 209   3 209   1   1     4  0000000000000001|00|0  br_table
    25:   4 209   3 209   1   1     8  0000011000000000|09|0  MAR_in IR_out
    26:   4 209   9 209   1   1     9  0000000000001000|0a|0  read
    27:   4 209   9 fff   1   1     a  0110000000000000|0b|0  ACC_out alu_add
    28:   4 209   9 fff   1   0     b  1000000000000100|00|0  ACC_in TMP_out
       +---+---+---+---+---+---+/----//---------------------//---------------/
    29:   4 209   9 fff   0   0     0  0000001000100000|02|0  MAR_in PC_out
    30:   4 209   4 fff   0   0     2  0000000000011000|03|0  pc_incr read
    31:   5 209   4 606   0   0     3  0000100010000000|04|0  IR_in MDR_out
    32:   5 606   4 606   0   0     4  0000000000000001|00|0  br_table
    33:   5 606   4 606   0   0     f  0000000000000000|00|1  or_addr
    34:   5 606   4 606   0   0     1  0000010001000000|00|0  PC_in IR_out
       +---+---+---+---+---+---+/----//---------------------//---------------/
    35:   6 606   4 606   0   0     0  0000001000100000|02|0  MAR_in PC_out
    36:   6 606   6 606   0   0     2  0000000000011000|03|0  pc_incr read
    37:   7 606   6 40a   0   0     3  0000100010000000|04|0  IR_in MDR_out
    38:   7 40a   6 40a   0   0     4  0000000000000001|00|0  br_table
    39:   7 40a   6 40a   0   0     c  0000011000000000|0d|0  MAR_in IR_out
    40:   7 40a   a 40a   0   0     d  0100000100000000|0e|0  MDR_in ACC_out
    41:   7 40a   a   0   0   0     e  0000000000000010|00|0  write
       +---+---+---+---+---+---+/----//---------------------//---------------/
    42:   7 40a   a   0   0   0     0  0000001000100000|02|0  MAR_in PC_out
    43:   7 40a   7   0   0   0     2  0000000000011000|03|0  pc_incr read
    44:   8 40a   7 e00   0   0     3  0000100010000000|04|0  IR_in MDR_out
    45:   8 e00   7 e00   0   0     4  0000000000000001|00|0  br_table
       +---+---+---+---+---+---+/----//---------------------//---------------/
  end of simulation

  low memory:    8  209  606  209  606  209  40a  e00    2  fff
                 0    0    0    0    0    0    0    0    0    0


example program (using extended instruction set and halt):

          load  a
          jsub  subr_1
          store c
          halt

  subr_1: .word 0        // reserved for return address
          jsub  subr_2
          jmpi  subr_1

  subr_2: .word 0        // reserved for return address
          sub   b
          jmpi  subr_2

  a:      .word 1
  b:      .word 2
  c:      .word 0


input (after hand assembly):

  a a04 40c e00 0 a07 c04 0 80b c07 1 2 0 -1


simulator output:

  low memory:    a  a04  40c  e00    0  a07  c04    0  80b  c07
                 1    2    0    0    0    0    0    0    0    0

  start of simulation of simple cpu
  [...]
  end of simulation

  low memory:    a  a04  40c  e00    2  a07  c04    6  80b  c07
                 1    2  fff    0    0    0    0    0    0    0