Designing an Instruction Set Architecture

 

Want: Resulting computer to be able to compute any computable function.

Usual Approach: Build in a few simple "commands" it can perform; make sure that the commands of some "complete" architecture can be simulated by sequences of the new commands.

Command Forms: Designed to allow computation of arithmetic expressions like A+B-C<6 using a short sequence of instructions. Prefer all instructions to have similar behavior (follow a pattern).

Binary Arithmetic Operations: Are the most common forms of algebraic operation found in arithmetic expressions. Translate these to operations which read at most two operands and compute one result, by performing ONE arithmetic operation.
T = B-C
S = A+T
Res = S<6
is a sequence of such single-operator commands, using "temporary" variables T, and S. The result appears as the answer computed using a comparison operator, which can produce a 0 or 1, depending on the truth of the condition it tests.

3 address instructions: The command forms above must be "encoded" into a form the computer can understand easily. Each such command is encoded into one computer word. Each of the command operands, and the result is identified by its location in memory (its address). A command like "T = B - C" is encoded as:
"Subtract: &T gets &B minus &C"
That is, the ADDRESSes of the variables that participate in the command are stored in the instruction. Each address, and the code indicating what operation is performed, is placed into a different "field" of the word representing the encoded command -- the instruction. Each field occupies a sequence of bits of the instruction. For instance, the "operation code" of all instructions might occupy bits 31..28. The result address might occupy bits 27..23, and so on.

Registers and Memory: It should be clear that if a computer's memory holds 2**28 bytes, that it would be impossible to encode 3 memory addresses, plus an operation code, into and instruction that occupies one 32-bit word. Various solutions to this dilemma have been used, but most of them wind up introducing a second class of memory, a register file. A register file consists of a small number of registers, usually each holding one word, numbered from 0 to perhaps 31. Only 5 bits are needed to specify one of these registers, so most 3-address instructions are restricted to use register numbers for operand addresses. Special instructions are supplied to move data from memory to register (load), and from register to memory (store). The encoding of these instructions need not be the same as for the arithmetic operations. The "addressing" problem hasn't been solved by this -- just limited to load/store instructions. To allow a load instruction to obtain data from any location in memory, we use registers in a different way: a register is allowed to hold the ADDRESS of a quantity, and the load command can then be encoded as: Load register X with the data found at the memory location held in register Y. That is, R[X] = Mem[R[Y]]. (Here, I'm using R[], a C array, to represent the register file, and Mem[] to represent memory.) Only the values of X and Y need by encoded into fields of the load instruction -- in effect a load instruction is a 2-address instruction. To get the proper address into register Y, a sequence of computation instructions is done by the program. Other designs are sometimes used: Some computers restrict the size of addressable memory, so at least one address can appear in an instruction; others use multi-word instructions. Using registers to hold addresses in this way has another huge advantage over encoding each address in an instruction field -- it allows computed addresses without requiring the program to modify instructions. Computed addresses are essential for referencing arrays, and for returning from subroutines.

Decisions: A computer must be able to test computed results, and choose different actions, depending on the outcome of such tests. In the usual case, the computer executes instructions in the sequence they appear in memory. This is done using a register maintained by the hardware, called the PC (Program Counter). The next instruction to be executed comes from Mem[PC], and then PC+=4 is executed, to cause the following instruction to be fetched from the next word of memory. The branch operation changes this default pattern. It sets PC to some value built in to a field of the instruction, or coming from a register. Usually, the branch is conditional -- done only if some test of a register's value is TRUE. If the test results in FALSE, the PC is incremented as usual, and the instruction sequence continues in order through memory.

RMI: Robert Wagner's Minimal Instruction machine is designed with very few different instructions. This makes the hardware easy to build, and it is easy to learn what each do. However, it requires sequences of several instructions to do anything useful, so this may not be a machine you find user-friendly.
Sub (X, Y, B) Computes X = Y-B, where X and Y must be variables, and B may be a variable or a constant.
Bltz(X,L) Branches to label L if variable X holds a negative number.

The RMI has only 2 instruction types, and uses a multi-word instruction format. RMI is almost complete -- I'd have to add the ability to compute instruction addresses to make it complete, and I haven't done that. Some more useful instructions can be built by stylized sequences or patterns of RMI instructions. (These are not built in to the RMI hardware, but have to be written out whenever you need one. To make this easy, I've defined them as C macros.)
Variable T is used to hold temporary results, and variable Zero is supposed to be initialized to hold 0, either in its declaration, or using the RMI instruction:
Sub(Zero, Zero, Zero) // Sets Zero=0.\

#define Add(X. Y, B)\
Sub(T, Zero, B) // T = -B\
Sub(X, Y, B) // X = Y - (-B)
(The "\" marks at the ends of all but the last line group all the lines above into the macro definition. When you next write "Add(Count, Temp, 3)", the C compiler "spills" the above definition, with "Count" substituted for each X in the definition, "Temp" for each Y, and "3" for each B. This makes it unnecessary to remember the details of Add() when you write programs using it.)

#define Bnze(X, L) // Is supposed to branch to L if X!=0\
Bltz(X, L) // Branch to L if X<0 \
Sub(T, Zero, X) // T = -X, where X >= 0 is known \
Bltz(T, L) // Branch to L if -X<0 \
// Otherwise, X==0, and no branch takes place.