by Carl Burch, Hendrix College, October 2011
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.
Let's start by seeing the types of memory found in the MINIAC.
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
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 (
BN), the PC can go up by other values instead.
Completing the circuit is an interesting exercise that is best
done on your own.
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.
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.
|if AC = 0 then PC ← PC + signed(x) else PC ← PC + 1|
|if AC < 0 then PC ← PC + signed(x) else PC ← PC + 1|
|RAM[x] ← AC; PC ← PC + 1|
|AC ← AC rotated left by distance given in lower 3 bits of x; PC ← PC + 1|
|AC ← signed(x); PC ← PC + 1|
|AC ← RAM[x]; PC ← PC + 1|
|AC ← AC + RAM[x]; PC ← PC + 1|
|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.
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
When the MINIAC encounters an
The above table explains an
|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
|PC = 2, AC = 5:|
At address 2 of program memory is 11000001.
This is an
|PC = 3, AC = 10:|
At address 3 of program
memory is 01000000, another
|PC = 4, AC = 10:|
At address 4 of program
memory is 10000000, another
|PC = 5, AC = 0:|
At address 5 of program
memory is 00000000, a
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.
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.
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.
ST 1 # Store 5 into memory so it can be added
ST 0 # Store result of addition into memory location 0.
LI 0 # Stop the computer.
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
In writing longer pieces of assembly language, one of the biggest
potential irritations is the need to compute the argument to
BN instruction; the argument
indicates how far to jump if the AC is 0 (
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
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,
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
LI 0 # Store result into memory location 0,
ST 0 # initially 0 but increased later.
loop LI -1 # Decrement memory location 2
BN stop # If we've passed 0, go down to stop the computer.
LM 0 # Add memory location 1 into result
LI 0 # Go back up to decrementing memory location 2
stop LI 0 # Stop the computer.
In assembling the
line, the assembler notes that
stop instruction is 6 instructions later in the program, so it
assembles this line is 001 00110. Likewise, in assembling the
instruction, it finds that the
is eight instructions earlier, so this line is assembled to 000 11000.
One final feature of MINIAC's assembly language is the
directive. A directive is a line in the assembly code that
configures the assembler rather than adding a machine language
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
any time that we're
referencing the memory for the number to be halved, and so that
we can write
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.
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.
neg LI 1 # Set AC to 0x80.
AD ret # Add 0x80 to ret.
LI 0 # Stop computer.
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.
LI 0 # Set up result for product, initially 0.
LI 8 # Set up counter, starting at 8.
LI -1 # Set up constant -1.
loop LM n1 # Load multiplier, rotate it right once.
BN add # If top bit is set after rotation, go to add.
double LM n0 # Double multiplicand.
LI -1 # Decrement counter.
LI 0 # Repeat loop.
add LM ret # Add multiplicand into product
LI 0 # Go back to continuing the loop.
exit LI 0 # Stop computer.