CPU requirements manual CPSC / ECE 3710, Fall 2006

Each project group must design a CPU as per specifications here. While all attempts have been made to keep these specifications consistent, changes will invariably arise. You will be notified of these changes in a timely manner.

The CPU after which our's is adapted from is described at
http://www.national.com/appinfo/compactrisc/files/prog_16c.pdf.
A class taught at the University of Michigan (EECS 427) produced a nice set of handouts describing our adaptation. Past instructors, Profs. Brunvand and Kalla, have created other helpful material. Sean Curtis (a former student who took 3710) created an Excel sheet containing the instruction set descriptions. All these are available from the Fall 2004 webpage of 3710, which is linked on our class webpage. I've checked what I say below against the information contained in these pages, but cannot vouch for their accuracy. The best descriptions I have found are in the documents entitled ``EECS 427 RISC processor'' which you will find among the documents linked off in ``Prof. Brunvand's CS 3710 page from Fall'02'' linked above. I am not duplicating the information contained in the above pages. Instead, I am stating the CPU's spec in my own words and style, below. Please also note the FAQ pages in my Fall 2004 webpage for 3710 mentioned above. I've tried to incorporate all the above FAQs in what I say below.

1 Overview of your CPUs

Your CPU will evolve in three installments. The first will be called MCR16-ts for Micro CR-16, thin slice. The second will be called MCR16-bl (bl standing for ``baseline'') and finally MCR16-ex (ex standing for ``extended.'')

All these processors will be 16-bit machines, meaning they will have 16-bit data paths. A 16-bit quantity will be called a word. We will assume 16-bit addresses also, thus providing an address range of 0000 to FFFF. By `word size' we will mean `size of a word,' or equivalently, 16 bits.

The ts version will have at least the following instructions implemented:

  LUI   -- Load Upper Immediate -- load a byte into the upper byte of a word
  ORI   -- OR a register with an immediate data item
  LOAD  -- Load from a memory address into a register
  ADD   -- Add the contents of two registers, storing the result into a third
  STOR  -- Store a register into memory

The bl version will have at least the following instructions implemented:

ADD, ADDI, SUB, SUBI, CMP,  CMPI,  AND,   ANDI, OR, ORI, XOR, XORI, MOV, MOVI,
LSH, LSHI, LUI, LOAD, STOR, BCOND, JCOND, JSL

The ex version will have one or more of these features:

additional instructions (which are specified in one of the CR-16 documents, or a completely new instruction) implemented.
additional features (e.g., interrupts), DMA instructions, etc., implemented.

You will receive extra points for adding these features, depending on the level of creativity as well as the quality of documentation.

1.1 Memory Map

The following memory map is recommended for all your processors. Differences are acceptable. Please document the memory map finally chosen.


FFFF  vvvvvvv

        I/O

C000  ^^^^^^^
BFFF  vvvvvvv

        code

8000  ^^^^^^^
7FFF  vvvvvvv
        stack
          |
          v
          
4000  ^^^^^^^
3FFF  vvvvvvv

       data
       
0000  ^^^^^^^

2 Semantics

The meaning (semantics) of the CR-16 instructions are described in earlier handouts. Here I shall attempt a condensed description at a slightly more formal level. Clearly, careful reviews are needed before bugs (I'm sure many are present) are removed from these descriptions -- hence, do ask me questions via email.

In all state-transition descriptions, we will assume that the state vector
```
{ MEM, RF, F, L, C, N, Z, PC }
```
evolves into state vector
```
{ MEM', RF', F', L', C', N', Z', PC' }
```
For clarity, we only show the things that change.
We are trying to make the semantic definition suggest the required hardware, in addition to being a clear description for your consumption. Sometimes, however, a clear explanation may be written using one set of operators, when in fact the hardware uses other operators in order to obtain a fast implementation. See discussions under Section 2.5 (alternative sub Rsrc, Rdst using adders) for an elaboration of this point.

I shall present the baseline instructions in the order in which MCR16-bl instructions are listed in the EECS 427 handout. See those handouts for an exact bit-level layout of the instructions. Also, while I shall use the assembly language syntax and mnemonics in what follows, the exact assembly syntax you have to employ in your assembler will be specified in a separate document. Here, the focus is on what your CPU -- and hence, your simulator -- must implement.

I shall introduce notations as needed, and flag each such notation for easy reference by using the boldface word Notation.

2.1 CPU state elements

Your CPU consists of the PC, flags F, L, C, N, Z, a register file RF, and a memory MEM. One or more of these state elements gets updated by each instruction of the CPU. The CPU semantic specification simply consists of describing these updates. Our notation for writing this description follows shortly.

The PC is of word size.
The flags F, L, C, N, Z are Boolean variables. Here is what the flags are:
- F = overflow
- L = less
- C = carry
- N = negative
- Z = zero
The CPU has a register file RF of eight registers named r0 through r7. RF[0] refers to the contents of r0, and so on for the remaining registers.
The XSA board has a 4 Megabyte DRAM memory. However, your processor can directly address only 64K words of memory, since all addresses are words. It is possible to use memory above the 64K boundary as video memory for access by the VGA controller!

The memory addressable by the CPU will be denoted by MEM or sometimes written MEM[ ]. Thus, MEM[23] refers to the 24th memory word (recall that the first memory word is MEM[0]).
All memory accesses are assumed to be aligned, i.e. all addresses supplied to the memory refer to words.

As an example, let A be a memory address where a word W1 made of two bytes B1H_B1L are situated (the underscore _ is added in this manual to enhance readability). Let the word W2 made of two bytes B2H_B2L be situated at address A+1. Then, there is no direct method of obtaining the word B1L_B2H. One method of forming such a word would be:
- obtain the words W1 and W2,
- logical left-shift W1 by 8 positions,
- logical right-shift W2 by 8 positions, and
- then bit-wise OR the results.

Notation:

PC refers to the PC contents as a word (unsigned binary number).
Sometimes we will write 00_11_10 to mean the same as 001110. The underscores (_) are used to enhance readability. Such embedded underscores are allowed in hardware description languages such as VHDL and Verilog.
RF[regno] denotes the bit-string that emerges when we index RF with regno. This can be subject to addition or other logical operations.
`+' denotes unsigned addition between two bit-strings of word length (16 bits), yielding a result bit-string of word length. Recall that whether these bit strings denote unsigned numbers or twos-complement numbers, addition works the same as far as the 16-bit results produced are concerned.

Example: 1100110011001100 + 0011001100110011 = 1111111111111111

Example: 1111111111111111 + 0000000000000001 = 0000000000000000

Notice from the second example that + is supposed to retain just the 16-bit result of addition.
RF[regno ] := value is our notation to say that the register file RF is updated. In particular, register regno gets value, and all other registers remain unchanged (continue to hold their old values).

Example:
```
    RF' = RF[a] := b
  
```
means that RF' remains the same as RF except that register a is updated to now have the value b.

Sometimes we write RF' = (RF[a] := b) to enhance readability.
In the same manner as with RF, MEM[addr] denotes the bit-string that emerges when we index MEM with an address, addr.
A similar update notation (as with REG) is allowed for MEM also. Specifically, MEM [ addr ] := value updates the said memory location w/o affecting the other locations.
Let zex(value) always refers to zero-extending an 8-bit quantity to fill 16 bit positions. (This is a simplification from the previous version of the CPU manual.)

Examples
```
  zex(FF) = 00FF
  zex(01) = 0001
  zex(03) = 0003
  
```
Later, when we write the instruction semantics, we may write zex(Imm). In these cases, Imm will be an 8-bit quantity, and will be zero-extended to 16 bits.
For denoting the new value of any quantity foo, we write foo'.

Example: The new value of RF is denoted by RF'.

Example: The new value of flag C is denoted by C'.
Rdst and Rsrc are collectively called regno standing for ``register number.'' regno is also an unsigned binary quantity

Armed with these notations, we can begin describing some of the instructions. We will introduce more notation to progressively describe the remaining instructions.

2.2 add Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 0101 Rsrc

Instruction semantics:

let vd    = RF[Rdst]
let vs    = RF[Rsrc]                           
let va    = vd + vs                            
let carry = cb(vd+vs)                       
let ovflo = if (msb(vd) XOR msb(vs)) then 0 -- recall that this is how 
            else (msb(vs) XOR msb(va))      -- overflow is computed 

then

RF'  = (RF[ Rdst ] := va),
F'   = ovflo,
C'   = carry,
PC'  = PC + 0x0001

Notice that the PC update is specified more directly than in the previous version of the CPU manual.
In this CPU manual, hexadecimal quantities will often be prefixed with 0x. I may leave out 0x and simply say ``ABCD'' if the usage (hex) is clear from the context.

Notice that the flags L, N, Z are unaffected.

Example: Let the CPU state be such that register r0 contains 1000_0000_0000_0000 while r1 contains 1111_1111_1111_1111. Then, with PC at FFFE (writing in hex), and this address containing instruction
add r0, r1,
we obtain as the new CPU state

  RF' = (RF[r1] := 0111_1111_1111_1111)
  F'  = 1
  C'  = 1
  PC' = FFFF

Additional notations used:

`cb' stands for the carry / borrow generated under addition / subtraction, treating the quantities as two normal (unsigned) words. Thus, cb(a+b) means the carry/borrow generated by performing the addition a+b where a and b are 16-bit quantities.
Soon we will be using the word sex to denote sign extension.

sex(value) always refers to sign-extending an 8-bit quantity to fill 16 bit positions. (This is a simplification from the previous version of the CPU manual.)

Examples:
```
  sex(0x0F) = 0x000F
  sex(0F)   = 000F -- omitting the  `0x' which is clear from context.

  sex(0x80) = FF80

  sex(0xF0) = FFF0
  
```
Later, when we write the instruction semantics, we may write sex(Imm). In these cases, Imm will be an 8-bit quantity, and will be sign-extended to 16 bits.
unsigned2decimal(..) is a function that imparts an unsigned interpretation to a word-sized bit-string and returns its decimal (unsigned) value
twos_complement(..) finds the 2's complement of a word given as a bit-string returning a bit-string as the result
msb(..) takes the MSB - used as a sign bit
`-' is unsigned subtraction between two bit-strings of word length yielding a result bit-string of word length.
bv_and, bv_or, bv_xor perform bit-vector and/or/xor.
bv_lshift(item,N) shifts item by N (if N is positive, then shift left that much; if negative, then shift right that much). Zeros are filled into the newly vacated positions, and the bits shifted out are lost.
bv_rshift(item,N) shifts item by N (if N is positive, then shift right that much; if negative, then shift left that much). Zeros are filled into the newly vacated positions, and the bits shifted out are lost.
branch(cond,F,L,C,N,Z), where cond are the condition bits in the instruction, consults Table 1 of the EECS 427 handout and decides whether to branch or not. Returns a Boolean.
`=' compares two items of the same type resulting in a Boolean result.

2.3 addi Imm, Rdst

The machine encoding is as follows:

  0101 Rdst Immhi Immlo

The only thing to point out is that we are treating the immediate values as signed 2's complement values (-128 through +127). Since my ``+'' denotes 16-bit addition, I have to sign extend the immediate value before addition.

Instruction semantics:

let vd = RF[Rdst]                           
and vs = sex(Imm) -- recall that this sign extends a byte to fill a 16-bit word
and va = vd + vs                            
and carry = cb(vd+vs)                       
and ovflo = if (msb(vd) XOR msb(vs)) then 0
            else (msb(vs) XOR msb(va))      

RF'  = (RF[ Rdst ] := va),
F'   = ovflo,
C'   = carry,
PC'  = PC + 0x0001

2.4 sub Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 1001 Rsrc

Note that the opcode extension is what distinguishes this operation from add.

Instruction semantics:


let vd = RF[Rdst]                             
and vs = RF[Rsrc]                             
and va = vd - vs                              
and carry = cb(vd-vs)                         
and ovflo = if (msb(vd) XNOR msb(vs)) then 0
            else (msb(vs) XNOR msb(va))       

RF'  = (RF[ Rdst ] := va),
F'   = ovflo,
C'   = carry,
PC'  = PC + 0x0001

2.5 Alternative sub Rsrc, Rdst using adders

Suppose your CPU only has adders. How do we then carry out sub? We can do so using 2's complement arithmetic.

[ Note: such alternatives might be needed for other operations also. I've not shown those. Those are left for you to derive.]

ALTERNATIVE sub Rsrc, Rdst

let vd = RF[Rdst]                             
and vs = twos_complement(RF[Rsrc])                      
and va = vd + vs                              
and carry = cb(vd+vs)                         
and ovflo = if (msb(vd) XOR msb(vs)) then 0
            else (msb(vs) XOR msb(va))        

RF'  = (RF[ Rdst ] := va),
F'   = ovflo,
C'   = carry,
PC'  = PC + 0x0001

2.6 subi Imm, Rdst

The machine encoding is as follows:

  1001 Rdst Immhi Immlo

Instruction semantics:

let vd = RF[Rdst]                             
and vs = sex(Imm)
and va = vd - vs                              
and carry = cb(vd-vs)                         
and ovflo = if (msb(vd) XNOR msb(vs)) then 0
            else (msb(vs) XNOR msb(va))       

RF'  = (RF[ Rdst ] := va),
F'   = ovflo,
C'   = carry,
PC'  = PC + 0x0001

2.7 cmp Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 1011 Rsrc

Instruction semantics:

let vd = RF[Rdst]                             
and vs = RF[Rsrc]                             
and va = vd - vs                              
and carry = cb(vd-vs)                         
and neg   = carry XOR msb(vd) XOR msb(vs)     
and zero  = if (va = zex(0x00)) then 1 else 0 -- clearer writing

L'   = carry
N'   = neg
Z'   = zero
PC'  = PC + 0x0001

2.8 cmpi Imm, Rdst

The machine encoding is as follows:

  1011 Rdst Immhi Immlo

Instruction semantics:

let vd = RF[Rdst]                             
and vs = sex(Imm)
and va = vd - vs                              
and carry = cb(vd-vs)                         
and neg   = carry XOR msb(vd) XOR msb(vs)     
and zero  = if (va = zex(0x00)) then 1 else 0

L'   = carry
N'   = neg
Z'   = zero
PC'  = PC + 0x0001

2.9 and Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 0001 Rsrc

Instruction semantics:

let vd = RF[Rdst]                             
and vs = RF[Rsrc]                             
and va = bv_and(vd,vs)                        

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.10 andi Imm, Rdst

The machine encoding is as follows:

  0001 Rdst Immhi Immlo

Instruction semantics:

let vd = RF[Rdst]                             
and vs = zex(Imm)                         
and va = bv_and(vd,vs)                        

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.11 or Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 0010 Rsrc

Instruction semantics:

let vd = RF[Rdst]                             
and vs = RF[Rsrc]                             
and va = bv_or(vd,vs)                         

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.12 ori Imm, Rdst

The machine encoding is as follows:

  0010 Rdst ImmHi ImmLo

Instruction semantics:

let vd = RF[Rdst]                            
and vs = zex(Imm)                        
and va = bv_or(vd,vs)                        

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.13 xor Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 0011 Rsrc

Instruction semantics:

let vd = RF[Rdst]                             
and vs = RF[Rsrc]                             
and va = bv_xor(vd,vs)                        

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.14 xori Imm, Rdst

The machine encoding is as follows:

  0011 Rdst ImmHi ImmLo

Instruction semantics:

let vd = RF[Rdst]                             
and vs = zex(Imm)                         
and va = bv_xor(vd,vs)                        

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.15 mov Rsrc, Rdst

The machine encoding is as follows:

  0000 Rdst 1101 Rsrc

Instruction semantics:

let vs = RF[Rsrc]                             

RF'  = (RF[Rdst] := vs)
PC'  = PC + 0x0001

2.16 movi Imm, Rdst

The machine encoding is as follows:

  1101 Rdst ImmHi ImmLo

Instruction semantics:

let vs = zex(Imm)                         

RF'  = (RF[Rdst] := vs)
PC'  = PC + 0x0001

2.17 lsh Ramount, Rdst

The machine encoding is as follows:

  1000 Rdst 0100 Ramount

This instruction is well defined only for values of 'vamount' (contained in register Ramount) in the range +15 to -15. These values are expressed in sign-magnitude form (to be consistent with the immediate case -- lshi -- that follows). This may be a deviation from the original CR-16.

In other words,

the highest Ramount is 0x000F (in sign-magnitude, this is +15). This means left-shift 15 places.
the lowest Ramount is 0x001F (in sign-magnitude, this is -15). This means right-shift 15 places.

It is highly recommended that you implement this instruction last. Even so, you may wish to implement only the vamount=1 case first. Thus:

Allow Ramount to contain 0x0001 in order to left-shift by one position.
Allow Ramount to contain 0x0011 in order to right-shift by one position.

This is a logical shift instruction - i.e. zero-fill hapens (see below)

Instruction semantics:

let vd = RF[Rdst]
and amount = RF[Ramount]  -- a 16-bit quantity
and sign   = if (bv_and(0x0010, amount) = 0x0000) then 0 else 1
                    -- 0 means left, and 1 means right
and magnitude = unsigned2decimal( bv_and(0x000F, amount) ) -- get magnitude of shift

RF'  = (RF[Rdst] := if sign = 0 then bv_lshift(vd, magnitude)
                                else bv_rshift(vd, magnitude)
       )     
PC'  = PC + 0x0001

2.18 lshi Imm, Rdst

The machine encoding is as follows:

  1000 Rdst 000s ImmLo

Again, it is highly recommended that you implement only the +1 / -1 cases first.

If s=0, then we take it to be a left shift. So if s=1, treat it as a right shift.

Instruction semantics:

let vd = RF[Rdst]                             
and vamount = unsigned2decimal(ImmLo)                        

RF'  = (RF[Rdst] := if s=0
                     then bv_lshift(vd, vamount)
                     else bv_rshift(vd, vamount)    
       )              
PC'  = PC + 0x0001

2.19 lui Imm, Rdst

The machine encoding is as follows:

  1111 Rdst ImmHi ImmLo

Instruction semantics:

let va = bv_lshift(zex(Imm), 8)           

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.20 load Rdst, Raddr

The machine encoding is as follows:

  0100 Rdst 0000 Raddr

Instruction semantics:

let va = MEM [ RF[Raddr] ]                     

RF'  = (RF[Rdst] := va)
PC'  = PC + 0x0001

2.21 stor Rsrc, Raddr

The machine encoding is as follows:

  0100 Rsrc 0100 Raddr

Instruction semantics:

let vd = RF[Raddr]                             
and vs = RF[Rsrc]                             

MEM' = (MEM [ vd ] := vs)                
PC'  = PC + 0x0001

2.22 bcond Disp, Cond

The machine encoding is as follows:

  1100 Cond DispHi DispLo

Instruction semantics:

let cond_met = branch(Cond,F,L,C,N,Z) ; Consult Table 1 of the EE 427 handout
                                      ; and see if the branch condition is met
PC'  = if cond_met
          then PC + sex(Disp) -- branch taken. Disp = DispHi_DispLo
          else PC + 0x0001    -- not taken; PC increments normally by 1

2.23 jcond Cond, Rtarget

The machine encoding is as follows:

  0100 Cond 1100 Rtarget

Instruction semantics:

let vt = RF[Rtarget]                          
and cond_met = branch(Cond,F,L,C,N,Z)         
                                                 
PC'  = if cond_met
          then vt          -- jump taken
          else PC + 0x0001 -- jump not taken

2.24 jal Rlink, Rtarget

The machine encoding is as follows:

  0100 Rlink 1000 Rtarget

Instruction semantics:

vt = RF[Rtarget]                          

RF'  = (RF [ Rlink ] := PC + 0x0001)
PC'  = vt

3 Exercises -- as well as ``thin-slice'' defined

In order to reliably build your CPU, you must know its machine semantics well. Here are exercises that help you practice your knowledge.

What does this program do?

  lui 0xBF r1
  ori 0xFF r1
  load  r1 r1
  lui 0xC0 r2
  load  r2 r2
  add   r1 r2
  lui 0xC0 r3
  ori 0x01 r3
  stor  r2 r3

Note: The instructions in this program constitute MCR16-ts, the thin-slice version of MCR16.

Calculate the state changes caused by each instruction of the following program. Assume suitable initial values for the memory locations involved in this program. Hex numbers are entered starting with 0x.

This document was translated from L^AT_EX by H^EV^EA.