In the following chapters, we will build a sequence of six CPU’s, each more developed than the previous one. These CPU’s will be named after the evolutionary sequence of animals: Invertebrate, fish, frog, reptile, bird and mammal. The properties of each are as follows:
- Invertebrate is very simple: It consists a register bank and an ALU only. At every clock edge, it performs a given ALU operation on any two given registers and writes the result back on any register. It does not have external program or data memory and is not programmable. A human operator is necessary so set the necessary control signals between the clock edges.
- Fish: Same with Invertebrate, but has external code memory. The desired ALU operations with the desired source and target registers is written into external memory as a sequence of ALU instructions, and at each clock edge one instruction is fetched from memory and executed. These ALU instructions are executed sequentially. There is no looping (ie, JUMP instruction) and no data memory (ie, Load, Load immediate and Store instructions)
- Frog: Load Immediate operation is added to fish.
- Reptile: Load, load immediate, store, jump and jump if zero instructions are added to frog.
- Bird: Stack instructions (push, pop, call and return) are added.
- Mammal: Interrupt processing is added.
This may seem complicated now, as we have not explained the terms “control unit”, “interrupt processing” etc. yet. We will give detailed explanations for each in their turn. Below, we will start with invertebrate.
3. A simple Pocket Calculator: Invertebrate
Invertebrate is a simple, human-operated pocket calculator which can perform nine different arithmetic and logical (AL) operations on eight 16-bit numbers.
Before going on, let us fix our terminology: In an arithmetic/logic expression like [++(3+22)]-(5&14) we have to distinguish two sorts of things :
- Arithmetic/Logic operations
Data are the numbers 3, 22, 5, 14. (The numbers we will deal with will always be 16-bit 2’s complement integers.)
Arithmetic/Logic operations are +, ++, -, & etc.
Parentheses are neither data nor operations. They simply tell us the operation ordering, ie, that we have to do + before ++..
3.1 Software view of Invertebrate: Instruction set and Programs
How a user sees Invertebrate (without the hardware details) is depicted below:
As can be seen from the figure, invertebrate has
- eight 16-bit registers, numbered from 0 to 7.
- three DIP-switch sets, Ra, Rb and Rc, with 3 switches each,
- one DIP-switch set, ALUOP, with 4-switches
- a pushbutton.
3.1.1 Instructions and Instruction set
An instruction of a CPU is a command that can be executed by that CPU. In case of invertebrate, the instructions are the nine AL operations that the invertebrate can perform. All invertebrate instructions have the same form.
- Take data (ie, 16 bit numbers) from one or two registers.
- Perform an arithmetic/logical operation on it/them,
- Write down the result on a register.
The register(s) from which the data is taken are called “source register(s)”. The register into which the result is written is called the “target register”. After the instruction is executed, the previous content of the target register is lost, replaced by the result. The contents of the source registers is left unchanged. Hence, each invertebrate instructions needs three pieces of information:
- One or more source register(s), from which data is taken.
- A single target register, into which the result is written.
- An AL operation to perform. In invertebrate, there are nine possible AL operations.
Therefore, an instruction can be completely expressed by one of the three following short hands:
OP tr sr1 sr2
OP tr sr
Here, OP denotes one of the nine AL operations to be performed. It must be replaced with one of the following strings: “add”, “sub”, “and”, “or”, “xor”, “not”, “mov”. “inc”, “dec”.
sr1, sr2 and sr denote source registers. tr denote the target register. r acts as both source and target register. All these are numbers between 0 and 7.
The AL operations “add”, “sub”, “and”, “or”, “xor” require two source registers. Hence they use the first shorthand..
The AL operations “not” and “mov” require only one source register. Hence they use the second shorthand.
The AL instructions “inc” and “dec” are the special case. Their source and target registers are the same. Hence they use the third shorthand.
The short hands we have just used to denote the instructions of invertebrate in a form known as the “assembly language” of invertebrate.
The set of all instructions of a CPU is known as that CPU’s instruction set. The instruction set of Invertebrate is given in the table below, together with some explanations about how each instruction works.. The column “AluCode” will be explained shortly.
Table 3.1.1 INSTRUCTION SET FOR INVERTEBRATE
|Instruction in assembly language||AluCode||C / C++ Definition||Explanations|
|add tr sr1 sr2||0||tr = sr1 + sr2||Add registers sr1 and register sr2 in twos complement, put the result into register tr|
|sub tr sr1 sr2||1||tr = sr1 – sr2||Subtracts register sr1 and register sr2 in twos complement, put the result into register tr|
|and tr sr1 sr2||2||tr = sr1 & sr2||Bitwise-ANDs register sr1 and register sr2, put the result into register tr|
|or tr sr1 sr2||3||tr = sr1 | sr2||Bitwise-ORs register sr1 and register sr2, put the result into register tr|
|exor tr sr1 sr2||4||tr = sr1 ^ sr2||Bitwise-Exclusive-ORs register sr1 and register sr2, put the result into register tr|
|not tr sr||5||tr = !sr||Bitwise-NOT’s Register sr and put the result into Register tr.|
|mov tr, sr||6||tr = sr||Move the contents of the Register sr into Register tr.|
|inc r||7||r = r+1 ,||Increment the contents of Register r|
|dec r||8||r = r-1 ,||Decrement the contents of Register r|
Let us write some example instructions in assembly language:
- add 7 3 2 // adds registers 3 and 2, writes down the result on register 7.
- xor 5 0 5
- not 4 3
- mov 0 6
- inc 3
To see how these instructions work, consider the figure given below, where we have depicted the contents of the register bank after the execution of each instruction, one after the other. Source registers are shown in Green. Target register is shown in Red. If a register is both source and target, it is shown in red.
3.1.2 Clock and instruction execution
Each instruction takes a certain amount of time to execute. This is because the instruction execution is carried out by the propagation of electric signals throughout the processor, and electrical propagation takes some time. The danger is to start a new instruction before the previous instruction is completed, which results in unpredictable behavior. For example, assume that the “add” instruction takes 10 ns to execute.. This means that once the cpu started to execute an add instruction, no new instruction must be started for at least 10 ns.
In order to solve this synchronization problem between instructions, each CPU has an associated clock. The period of the clock is longer than the longest instruction execution time (or, part of the instruction as we will see in the coming chapters). Instructions are sent to CPU only at the rising edges of the clock signal. This prevents any clashes between instructions and ensures that a new instruction is sent only after the previous instruction is completed..
Invertebrate (and all the other CPU’s we will develop in this class) can execute only one instruction at a given time . This is not so with most modern CPU’s which deploy pipelined and superscalar designs. In such designs more than one instructions can be executed at a given time..
Invertebrate’s clock is controlled by a human operator. Each time the human operator presses and releases a pushbutton, Invertebrate receives a clock edge. We assume that the human operator is slower than the slowest instruction in the instruction set..
3.1.3 Executing an instruction on invertebrate
The human operator sends an instruction to invertebrate in a multi-step process:
- The human operator sets the ALUCODE switch to the alucode of the instruction he wants to execute. The ALUCODE of all instructions are listed in Table 1.
- If the instruction is of the form OP tr sr1 sr2, he sets the switches Ra, Rb and Rc into tr, sr1 and sr2, in that order.
- If the instruction is of the form OP tr sr, he sets the switches Ra and Rb into tr and sr and sr2, in that order. In this case, the settings of the switch Rc is unimportant, or, “don’t care’
- If the instruction is of the form OP r, he sets both the switches Ra and Rb into r. In this case, the settings of the switch Rc is unimportant, or, “don’t care. Recall that this case corresponds to inc and dec instructions.
- After all the switches are set as described above, the human operator presses the pushbutton/clock and sends a clock edge to invertebrate. Invertebrate reads the source registers, executes the desired AL operation, and updates the register bank by writing the result back into the target register.
- The instruction is completed. Invertebrate waits for the next instruction.
A single instruction achieves very little. In order to achieve even a modestly complicated task, we have to use many instructions one after another. Such a string of instructions dedicated to accomplish a single task is called “a program“. A program is always executed sequentially, ie, an instruction is always executed before the instructions following it. Examples are given below.
Invertebrate programs are always in the form of calculations on some given data. The first step for such calculations is to load the data into the registers. But invertebrate do not have any capacity for loading data into registers. Therefore, we will assume that when our program has started the data had already been loaded into registers by some magical means. In later chapters we will add an instruction to our instruction set for that purpose: In chapter 4, LDI instruction will be added to our instruction set to load data into registers.
Example 1: Write a program to perform the following calculation with Invertebrate:((10+124)&12-15)++. The result must be in register 0.
Answer 1: Assume that initially
- register 0 contains 10
- register 1 contains 124
- register 2 contains 12
- register 3 contains 15
Then the program is:
add 0 0 1
and 0 0 2
sub 0 0 3
The dip-switch settings corresponding to this program is
ALUCODE Ra Rb Rc
0 0 0 1
2 0 0 2
1 0 0 3
7 0 0 d
In the fourth line, “d” means “don’t care”, as the switch settings are not important. Also note that the inc operation source and destination are the same..
Example 2: Write a program to perform the following calculation with Invertebrate:((46&37)-(7|42)–). The result must be in register 3.
Answer 2: Assume that
- Register 0 contains 46
- Register 1 contains 37
- Register 2 contains 7
- Register 3 contains 42
Then the program is
and 0 0 1
or 2 2 3
sub 0 0 2
mov 3 0
The switch settings corresponding to the program is:
ALUCODE Ra Rb Rc
2 0 0 1
3 2 2 3
8 2 2 d
1 0 0 2
6 3 0 d
Exercise 1: Write a program to perform the following calculation with Invertebrate: ( [(20&34) – (12^122)]– ) + !(47|25). The result must be in register 5.
Note that with Invertebrate we can deal with at most eight numbers, as we only have eight registers.
3.1.5 Assembly language vs. Switch “language”
Note that each assembly instruction has a corresponding setting on 13 switches and vice versa. Therefore, any program can be written as a sequence of assembly instructions, or, equivalently, as a sequence of switch settings. Naturally we prefer to write our programs in assembly language, but the machine only understands switch settings. Hence, we first write our programs in assembly, then convert them to switch settings.
3.2 Hardware implementation of Invertebrate
The hardware schematic is given below. ALU and the register bank are as described in the previous chapter.
(When we don’t want to do any operation, we put regload=0)
Invertebrate executes an instruction at every positive clock edge. Here, Ra, Rb and Rc are numbers between 0 and 7 and they denote one of the eight registers, op denote an operation given in Table 3.1.1.
Note that Frog has four control inputs, controlled by the dip-switches, set by the human operator.
- REG1CHOOSE (3 bits): Number of Rb is entered here.
- REG2CHOOSE (3bits): Number of Rc is entered here.
- ALUCHOOSE (4 bits) : Number corresponding to desired ALU operation is entered here
- REGSELECT (3 bits): Number of Ra is entered here.
These control inputs are collectively known as control signals.
Exercise 2: Realize invertebrate in Logisim, run the computation in exercise 1 and produce the result.an
Key concepts Covered
- ALU operation
- Source and target registers of an Instruction
- Instruction set
- Assembly Language
- Switch settings
- Time taken for an instruction to execute.
- Clock period