COSC 201: Computer Organization

Purpose

Learn about the criteria for designing a good instruction set architecture.

Method

Work in teams of two to design an instruction set for a simple machine with 8-bit instructions.

Preparation

Read Chapter 3 of the textbook.

Files to Use

None.

What to Hand In

Each team must turn in a typed description of the instruction set and assembly code.

Machine Language Specifications

• 8-bit instructions and 32-bit words
• 4 general purpose 32-bit registers (r0, r1, r2, r3)
• Instruction types
  1. add immediate uses one register (rd) and an immediate operand
  2. arithmetic/logical use two registers (rd, rs)
  3. load/store use two registers (rw, ra) and a 2-bit address offset
  4. (conditional) branches use a 2-bit condition code and a 4-bit address offset

1. The addi (add immediate) instruction adds an immediate value (a small signed integer within the instruction) to the value in a register, and places the result back into the same register. The addi instruction sets one of the internal zero or negative condition codes depending on the value of the result.

2. Arithmetic and logical instructions operate on the values in the specified source and destination registers and (with the exception of cmp) place the result in the destination register. For example:

   add $0, $1 # r0 = r0 + r1
cmp $2, $3 # r2 - r3 (set condition codes only, discard result)

   These instructions must include add (addition), sub (subtraction), and cmp (comparison). All of these instructions set one of the internal zero or negative condition codes depending on the value of the result.

3. The lw (load word) and sw (store word) instructions add a 2-bit immediate value to the value in one register (ra) to calculate a memory address, then either load the value of the memory word at that address into another register (rw) or store the register's value at the calculated memory address. For example:

   lw $1, 1($0) # r1 = memory[r0+1]
sw $2, 0($0) # memory[r0] = r2

4. Branch instructions behave as follows. If the condition indicated by the 2-bit condition code is true, the next instruction to be executed is located in memory at the address given by adding the immediate address offset (a 4-bit signed integer within the instruction) to the address of the next instruction. Otherwise, the next instruction in order is executed.

   The condition is based on the result of the immediately previous arithmetic/logical instruction:

   • 00 - always branch
   • 01 - branch if previous result was zero
   • 10 - branch if previous result was less than zero
   • 11 - branch if previous result was less than or equal zero

Procedure

• Determine the number of bits needed to specify a register field.
• Determine the number of bits available to specify the opcode for each of the different instruction types.
• Select which bits will represent which fields for each type of instruction. Try to keep register fields in the same positions for different instruction types in order to make the interpretation of the bits for a register field have little or no dependence on the value of the opcode. This property of independence is called orthogonality.
• Try to make the immediate field for the addi (add immediate) instruction as large as possible, yet maintain orthogonality as much as possible.
• Ensure that your machine language can be decoded uniquely. Each (legal) combination of 8 bits should correspond to one (and only one) instruction.
• Define an appropriate assembly language for your instruction set.
• Do you have any unused bits? If so, what instruction(s) might you add to your machine language? How might you add more instructions to your assembly language, even if you have no unused bits?
• Challenge
• Add a nop (no operation) instruction that does nothing. The machine language instruction for nop must be all zeros. This insruction might not preserve the values of the condition codes, thus a nop should not be placed between an arithmetic/logical instruction and a conditional branch.
• Write assembly code for the code segments given below.

What to Hand In

A typed write-up of your instruction set, including a diagram of the field layout for each type of instruction, a description of what the values in each field mean, and the assembly language notation for each instruction. Explain the choices you made in the design of your instruction set. If you add any instruction(s) with a different format, explain their format.

Challenge

Translate one or both of the following C++ code segments into functionally equivalent assembly code for your machine. You may use any additional instructions that you invented.

Code Segment 1

sum = 0;
for (k = 0; k < n; k++)
{
    sum += k;
}

Code Segment 2

sum = 0;
for (k = 0; k < n; k++)
{
    sum += list[k];
}

Assume the following initial register assignments:

Hint

First try to write assembly code assuming that there are no limits on the number of available registers or the size of immediate values within instructions, then modify your code to take these limitations into account. If you cannot completely satisfy these limitations in your assembly code, then clearly explain which of these limitations are violated.