Instruction set for the Mini ALU

This section is about encoding and decoding instructions for our Mini ALU.

Relevant for encoding/decoding an instruction is the instruction set which in particularly specifies what operations are supported and describes the format of an instruction.

Video tutorial

Supplements for instruction set and the introduced notations

All instructions are 8-bit patterns and have a simple format. The format can be described by grouping the bits by pairs and denoting them, from left to right, as Op, X, Y and Z. For example

\[\text{10011011} \leadsto \text{10 01 10 11} \leadsto \text{Op} = \text{10}, \text{X} = \text{01}, \text{Y} = \text{10},\text{Z} = \text{11}.\]

The bit pattern Op is the opcode of the instruction. It specifies the type of instruction. Because the opcode is a 2-bit pattern we have (only) 4 types of instructions, and the remaining bits are used as operands. The instruction set of the ALU can be described as follows:

\[\begin{array}{ll}\text{Op} & \text{Effect} \\00 & \bigl(u(\text{%}00) + u(\text{XY})\bigr) \bmod 2^8 \to u(\text{%}Z) \\01 & \bigl(u(\text{%}Z)\cdot 2^4 + u(\text{XY})\bigr) \bmod 2^8 \to u(\text{%}Z) \\10 & \bigl(u(\text{%}Y) + u(\text{%}X)\bigr) \bmod 2^8 \to u(\text{%}Z) \\11 & \bigl(u(\text{%}Y) - u(\text{%}X)\bigr) \bmod 2^8 \to u(\text{%}Z) \\\end{array}\]

In this description the following conventions and formal notations are used:

  • With XY the concatenated bit pattern of X and Y is denoted. For example, if X = 01 and Y = 10 then XY denotes 0110.

  • A register with id X is addressed by using the %. Hence, %00 denotes register with id 00, %01 denotes register with id 01, etc.

  • Whit the notation \(u(\dots)\) the interpretation of the bit pattern as unsigned integer is expressed. This basically an abbreviation for the positional notation with base \(2\):

    \[u(\text{"bit pattern"}) := (\text{"bit pattern"})_2\]

    so for example

    \[u(1011) := (1011)_2 := 8 + 2+ 1.\]

    The motivation to introduce another notation will become clear when we introduce the notation \(s(\dots)\) for the interpretation as signed integer.

  • For a given integer \(n\) we describe with \(n \to u(\text{%}Z)\) how a destination register gets changed by an instruction. For \(n \in \{0,\dots,2^8-1\}\) there is an unique 8-bit pattern \(N\) such that \(n = u(N)\) so this denotes that \(\text{%}Z\) gets overwritten by \(N\).

This method of describing an instruction set was developed by Donald Knuth (see Volume 1 Fascicle 1 of TAOCP were he describes his MMIX). It has the advantage that you can describe the effect of an instruction without the need to describe how the instruction is implemented. The price for this elegance requires some idealised hardware design (that is why you realize it by a virtual machine and not actual hardware) but it is perfect for teaching. And most important, it is giving you the essential idea.

If you want to see a description of an instruction set from the industrial world have a look at the ARM instruction set (e.g. inArmv8-M Architecture Reference Manual) or the Intel 64 instruction set (e.g. Intel® 64 and IA-32 Architectures Software Developer’s Manual). Both look scary at first, but you will see that having the big picture makes them readable!

Description of the register bank (using the notations)

For the register bank we can now express with \(\text{out0} \leadsto \text{%}\text{sel_out0}\) that the output out0 is connected to the register with id sel_out0. So in total the register bankk can be described as

\[\text{out0} \leadsto \text{%}\text{sel_out0}, \;\text{out1} \leadsto \text{%}\text{sel_out1}, \;\text{in} \leadsto \text{%}\text{sel_in}, \;\]

and

\[\text{%}\text{sel_in} = \text{in},\;\text{if}\;\text{clock}=1.\]

In particular this makes it easy to describe the role of the register bank for implementing the instruction set. For example, implementing the operation \(\bigl(u(\text{%}Y) + u(\text{%}X)\bigr) \bmod 2^8 \to u(\text{%}Z)\) requires

\[\text{out0} \leadsto \text{%}\text{Y}, \;\text{out1} \leadsto \text{%}\text{X}, \;\text{in} \leadsto \text{%}\text{Z}\]

so that we get the needed source and destination registers for the adder.

How this prepares you for upcoming sessions

The format used for the ALU is very similar to the format used by the 32-bit instruction of the MMIX or the ULM.