The MINIAC machine

by Carl Burch, Hendrix College, October 2011

The MINIAC machine by Carl Burch is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.
Based on a work at www.cburch.com/books/miniac/.

Contents

Even after understanding the basic components that one typically uses to build digital circuits, it's still not easy to see how these components can be used to fit together to build a computer. In this document, we'll study a very simple design for a computer called the MINIAC, for which you can hope to build a circuit yourself.

1. MINIAC layout

Let's start by seeing the types of memory found in the MINIAC.

1.1. MINIAC memory

The MINIAC's memory is split into two entirely different regions called program memory and data memory.

• MINIAC's program memory contains 256 bytes for storing the program that the computer will execute. It is made of ROM (read-only memory), since the MINIAC provides no way for a computer to modify the contents of program memory: The program to be executed simply must be stored into ROM before the MINIAC starts up, and that will be the only program that the MINIAC will use while it is running.

• MINIAC's data memory contains 32 bytes, implemented using RAM (random-access memory). A program uses this memory for storing any numbers that it wants to remember temporarily and later retrieve. Essentially you can think of this memory as the space where variables' values are stored.

In addition, the MINIAC includes two eight-bit registers.

• The program counter (PC) holds an eight-bit number that is the address of the instruction that is to be executed.

• The accumulator (AC) temporarily holds a number for computation. You can think of the accumulator as the MINIAC's short-term memory, while the data memory is its long-term memory.

The following diagram shows roughly how these pieces fit together.

At the top of the circuit diagram are the MINIAC's two memories, and below it are the two registers. As you can see, the PC's current value is wired directly to the address input of the program memory. As a result, the program memory fetches whatever is at the address found in the PC, and the value found at that address exits through the red wire stub on the program memory's right side: This is the eight-bit value that contains the instruction that the MINIAC is currently assigned to execute. Omitted from the diagram is a rather complex circuit that interprets and executes this instruction.

This circuit also feeds the current PC value into an 8-bit adder, whose other input is the number 1. The sum is wired back to be the input to the PC.

Finally, you can see that the clock, which repeatedly toggles between 0 and 1, is wired into the PC's clock input. Consequently, whenever the clock goes from 0 to 1, the PC will increase by 1 (since that's the value received from the adder). This will lead the program memory to receive this new address, which will then lead the program memory's output to change to the next instruction found in the program.

This diagram omits quite a bit. Left unsaid is how the circuit will process that instruction coming out of the program memory. The circuit also implies that PC always goes up by 1 with each clock cycle, but we will later see that for some instructions (BZ and BN), the PC can go up by other values instead. Completing the circuit is an interesting exercise that is best done on your own.

1.2. Harvard and von Neumann architectures

The MINIAC includes two separate memories, one for the program and the other for data. A two-memory design like this is called a Harvard architecture. This name is based on one of the earliest computers, which was built for Harvard University in 1944, and which read its program from a strip of paper fed into it (the program memory), with a separate random-access storage for data (which could hold seventy-two 23-digit numbers). An early computer pioneer named John von Neumann later observed that a computer's program could be stored in the same memory as the data, which leads to more flexibility. This single-memory design is called the von Neumann architecture, and it is used in all general-purpose computing devices today.

The von Neumann architecture allows more flexibility, allowing a system to load another program into memory and then execute that program instead. But it also has the notable disadvantage of leading to a more complex circuit. In particular, executing an instruction often involves two different memory accesses — one to fetch the instruction from memory and another to access data from memory that the instruction uses. Thus, you end up with a more complex design where executing each instruction requires separate steps (one to load the instruction, another to execute it), whereas a computer using the Harvard architecture can do this process in a single clock cycle. The MINIAC is designed to use a Harvard architecture precisely because that makes its circuit design much simpler.

While the von Neumann architecture has mostly supplanted the Harvard architecture, the Harvard architecture still exists today in the simplest processors, used in devices like microwave ovens or digital watches. Such devices typically use a microcontroller, which combines a processor with its memory and other functions into a single chip. The PIC and AVR architectures are two popular microcontrollers, both using a Harvard architecture. For amateurs, the most accessible way of playing with these microcontrollers is probably the Arduino board, which uses an Atmel AVR processor.

2. Machine language

Each MINIAC instruction stored in the program memory is eight bits long. The first three bits, called the opcode, identify the type of instruction to be performed; and the last five bits provide an argument customizing what the operation should do.

The three opcode bits allow any of eight different bit combinations, and each of these combinations corresponds to a different instruction type.

000xxxxx	BZ: Branch if Zero
if AC = 0 then PC ← PC + signed(x) else PC ← PC + 1
001xxxxx	BN: Branch if Negative
if AC < 0 then PC ← PC + signed(x) else PC ← PC + 1
010xxxxx	ST: STore
RAM[x] ← AC; PC ← PC + 1
011xxxxx	RL: Rotate Left
AC ← AC rotated left by distance given in lower 3 bits of x; PC ← PC + 1
100xxxxx	LI: Load Immediate
AC ← signed(x); PC ← PC + 1
101xxxxx	LM: Load from Memory
AC ← RAM[x]; PC ← PC + 1
110xxxxx	AD: ADd
AC ← AC + RAM[x]; PC ← PC + 1
111xxxxx	SB: SuBtract
AC ← AC − RAM[x]; PC ← PC + 1

We can simply take an example to see how these instructions fit together. Suppose we have the following values in the MINIAC's program memory as we start the MINIAC.

addr	value	op	arg
0:	10000101	(LI	5)
1:	01000001	(ST	1)
2:	11000001	(AD	1)
3:	01000000	(ST	0)
4:	10000000	(LI	0)
5:	00000000	(BZ	0)

When we turn the computer on, both registers PC and AC contain zero, and the computer goes through the following steps.

PC = 0, AC = 0:	Since the PC is 0, we fetch from memory address 0 in program memory to determine the instruction to be executed. Found at address 0 is the value 10000101. The first three bits are 100, so we are looking at an LIinstruction, and the last five bits hold 00101. When the MINIAC encounters an LI instruction, it places the five-bit value in the instruction (00101 here) into the accumulator, and the program counter increases by one. So after executing this instruction the AC will be 5 while the PC will be 1. The above table explains an LI instruction by AC ← signed(x); PC ← PC + 1. The appearance of signed indicates that the five-bit value will be interpreted as a two's-complement number. Thus, if the instruction read 10011111, then the five-bit argument would represent the number −1, and so the eight-bit value −1 would go into AC.
PC = 1, AC = 5:	Now that the PC is 1, the MINIAC fetches its next instruction from address 1 of program memory, where it finds 01000001. This is an ST instruction, in which the number from AC (5) is stored in data memory at the address given in the instruction. The PC also increases by 1, so it now becomes 2.
PC = 2, AC = 5:	At address 2 of program memory is 11000001. This is an AD instruction, and the AC accordingly updates to be the sum of its current value (5) and of the data memory found in the address specified in the instruction (address 1, where 5 was just stored by the previous instruction). Thus, the AC updates to 10 (from 5 + 5), and the PC also increases by 1.
PC = 3, AC = 10:	At address 3 of program memory is 01000000, another ST instruction, which says to store the current AC value of 10 into data memory at address 0. Also the PC increases by 1 to become 4.
PC = 4, AC = 10:	At address 4 of program memory is 10000000, another LI instruction, which says to change the AC to hold the number found in the last five bits of the instruction, which in this case is 0. Also the PC increases by 1 to become 5.
PC = 5, AC = 0:	At address 5 of program memory is 00000000, a BZ instruction, which says to increase the PC by the five-bit value found in the instruction if the accumulator holds 0. In this case, the accumulator holds 0, so in fact the PC changes to be the sum of its current value of 5 plus the 0 found in the instruction. Thus the PC is set to remain at its current value of 5. Because PC remains at the same value, the next instruction executed will still be fetched from the same location, and the instruction will have the same result of no changes to the PC (or anywhere else). The computer has entered a tight loop in which nothing happens, so it has effectively frozen. This is our way of essentially shutting the computer off.

3. Assembly language

The binary code that is loaded into memory is called machine language. Because this binary encoding is difficult for humans to work with, programmers prefer to compose programs in assembly language, which uses mnemonic codes to describe the instructions. Then they use a program called an assembler, which translates the mnemonic codes into the corresponding machine code.

3.1. Instruction mnemonics

For the MINIAC, our assembly language has one instruction on each line of a text file. The instruction will contain the two-letter abbreviation for the instruction type followed by a base-10 number providing the instruction argument. Thus, here is an example of a complete program written in the MINIAC assembly language.

# Compute 2 * 5 by adding the number 5 to itself.
LI 5
ST 1 # Store 5 into memory so it can be added
AD 1
ST 0 # Store result of addition into memory location 0.

LI 0 # Stop the computer.
BZ 0

A comment is specified by a sharp (#), and any characters following it in the same line are ignored. Notice that you are allowed to have an empty line; the assembler simply ignores such lines as it generates the corresponding machine code. Thus, the above program contains eight lines, but the assembler generates only six instructions (which would be exactly the machine code that we saw in Section 2.

3.2. Labels

In writing longer pieces of assembly language, one of the biggest potential irritations is the need to compute the argument to each BZ or BN instruction; the argument indicates how far to jump if the AC is 0 (BZ) or negative (BN). But here we have a computer right in front of us — why not let it compute the numbers for us? This is the idea of a label, which allows us to associate a word with the location of an instruction by simply writing the word before the instruction. Then in the BZ or BN instruction, we can use that word in place of the number, and the assembler will compute the number to use in place of the label.

The following program uses two labels, loop and stop. Notice that we follow the convention of including any labels at the very beginning of a line, and we make it so that the instructions opcodes all line up further into each line.

# Multiply two numbers (5 and 7) using repeated addition.
     LI 5     # Place 5 and 7 into memory locations 1 and 2
     ST 1
     LI 7
     ST 2
     LI 0     # Store result into memory location 0,
     ST 0     # initially 0 but increased later.

loop LI -1    # Decrement memory location 2
     AD 2
     ST 2
     BN stop  # If we've passed 0, go down to stop the computer.
     LM 0     # Add memory location 1 into result
     AD 1
     ST 0
     LI 0     # Go back up to decrementing memory location 2
     BZ loop

stop LI 0     # Stop the computer.
     BZ 0

In assembling the BN stop line, the assembler notes that the stop instruction is 6 instructions later in the program, so it assembles this line is 001 00110. Likewise, in assembling the BZ loop instruction, it finds that the loop instruction is eight instructions earlier, so this line is assembled to 000 11000.

3.3. Directives

One final feature of MINIAC's assembly language is the EQ directive. A directive is a line in the assembly code that configures the assembler rather than adding a machine language instruction.

The EQ directive allows you to create a name with a particular integer value. This is intended particularly for associating names with memory addresses, so that the EQ directive can be used in a way that's analogous to a variable declaration.

The below program illustrates this. The program takes the number placed in memory location 1, halves it, and places the result into memory location 0. At the beginning, we use EQ directives so that we can write arg any time that we're referencing the memory for the number to be halved, and so that we can write ret any time that we're referencing the memory for the result.

ret  EQ 0    # Address where result is placed.
arg  EQ 1    # Address where number to be halved is placed.

     LI 15
     ST arg
     LM arg   # Load number to be halved,
     RL 7     # rotate it right once, and
     ST ret   # store rotated result.
     BN neg   # Go to neg if top bit is 1 (1's bit before rotation).
done LI 0     # If bit is 0, stop computer.
     BZ 0
neg  LI 1     # Set AC to 0x80.
     RL 7
     AD ret   # Add 0x80 to ret.
     ST ret
     LI 0     # Stop computer.
     BZ 0

4. Multiplication program

The MINIAC is designed to be simple enough that to understand everything in the circuit and the assembler with very little effort. Thus, we have seen everything there is to know about the MINIAC's instruction set and its assembly language.

Let's close our study with a reasonably complex program. We saw earlier a program that multiplies two numbers using the repeated-addition technique: To multiply 5 by 7, it would start at 0 and add 5 into it 7 times to arrive at 35. The repeated-addition algorithm is quite slow; the following program uses a more sophisticated technique that more closely resembles the well-known multiplication algorithm, illustrated below.

				1	0	1
×				1	1	1
				1	0	1
			1	0	1
+		1	0	1
		1	0	0	1	1

ret     EQ 0    # Address where product goes.
n0      EQ 1    # Address for multiplicand - doubles each iteration.
n1      EQ 2    # Address for multiplier - rotates right each iteration.
i       EQ 3    # Address for counter from 8 down to 0.
vn1     EQ 4    # Address for constant -1.

        LI 7    # Set up parameters for multiplication.
        ST n0
        LI 5
        ST n1
        LI 0    # Set up result for product, initially 0.
        ST ret
        LI 8    # Set up counter, starting at 8.
        ST i
        LI -1   # Set up constant -1.
        ST vn1
loop    LM n1   # Load multiplier, rotate it right once.
        RL 7
        ST n1
        BN add  # If top bit is set after rotation, go to add.
double  LM n0   # Double multiplicand.
        AD n0
        ST n0
        LI -1   # Decrement counter.
        AD i
        ST i
        BN exit
        LI 0    # Repeat loop.
        BZ loop
add     LM ret  # Add multiplicand into product
        AD n0
        ST ret
        LI 0    # Go back to continuing the loop.
        BZ double
exit    LI 0    # Stop computer.
        BZ 0