Internal Document, UIC CS Department. Used with Permission

From Jon A. Solworth, Computer Architecture,
c. 1989-1996.

Internal document, UIC CS Department. Used with permission.

Ch2, Datapath Review

Each register is stored as shown in Fig. 2.3 (note the 2-stage clock)

Multiple registers can then be stored together, with multiplexer’s selecting between them. We can select the A register as well as the B register. Note each multiplexer has 3 select bits.

The ALU operations can be given as shown.

Fig. 2.5 shows how multiple bit-slices are combined together to give an 8-bit ALU.

The circuits for each bit slice are shown in Fig. 2.6.

NOT, OR, AND, XOR are straightforward implementations using those gates.

The circuitry for ADD can be derived from a truth table with ai, bi, cin as inputs, and si, cout as outputs.

Resulting Datapath Diagram:

Shifting to the left can be accomplished by adding a number to itself.

Passing a number through the ALU can be accomplished by ANDing it to itself.

Datapath Control Statements:

To implement:

r0 = r5 = (r1+r2);

we could use:

r0write, r5write, asel 0, bsel 1, alusel 2

which means:

The order of listing signals doesn’t matter. Consider the bits in asel:

Bits in asel
2 / 1 / 0
0 / 0 / 1

Examples:

We could write r2  r0 + r1 as either of:

r2write, asel= 0, bsel= 1, alusel= ADD

r2write, bsel 0, alusel 2

The second method works because no bits are set for asel, so it defaults to 0, and register 0 is placed on the a bus.

To clear register r3, we could use:

r3write, alusel= SUB, asel= 0, bsel= 0, cin // r3  0

To represent r7  r0 + r3, we could use:

r7write, bsel 0, bsel 1, alusel 2
This works because a is not set, and the settings for bits for bsel gives register 11, which is 3. ALU line 2 being set is equal to binary 100, which corresponds to ADD.

Arithmetic shift left of register i is accomplished by:

When i=3 this becomes:

To load a register with a constant k, where we have shifting and cin, but do not have parallel load, we could use:

which when executed gives:

Control statements can also have branches, such as in this code that circularly shifts left 1 bit:

A circular right-shift of k bits involves left-shifting n-k bits, where there are n bits in the register.

r5write, asel=<k>, alusel=ADDA; // r5 <- r<k>

loop:r5write, asel=5, alusel=SUBA, // r5--

if m7 then goto done;

asel=<i>,bsel=<i>,alusel=AND

if m7 then goto shift1 else goto shift0 endif;

shift1:r<i>write, asel=<i>,bsel=<i>, alusel=ADD, cin=1,

goto next;

shift0:r<i>write, asel=<i>,bsel=<i>, alusel=ADD, cin=0,

goto next;

next:goto loop;

done:

This code does a left shift rk number of times:

r<i> < r<k>

We must also be able to address memory.
The structure of the architecture for this is:

where the various memory register control lines are:

The datapath now consists of the following control signals and status lines:

We can write programs to read from memory:

And write to memory:

Data read from memory is stored as 8-bit bytes. The instruction register, ir can store 16 bits, so it requires two memory loads, 8-bits at a time. These 16 bits are stored in two halves, ir0 for the lower-order bits, and ir1 for the higher-order 8 bits. These bits can then be used in different ways, as we’ll see later. The full datapath is now:

where result_sel is now 2 bits chosing between 4 options:

Fetch/Execute Cycle
(taken from handout at Mythsim.org)

Assume a C/C++ program containing the statement:

x = y + 7;

Assuming the value for x is stored at memory position 120 and the value for y is stored at memory position 110, the corresponding assembly language code might be as follows:

li $r0, 110// load immediate into register 0 the address of y

lw $r1, 0($r0)// load word at address $r0 into $r1

li $r2, 7// load immediate into register 2 the value 7

add $r3, $r1, $r2// register 3 <- register 1 + register 2

li$r0, 120// load immediate into register 0 the address of x

sw$r3, 0($r0)// store word into register 3 from the memory address stored in register 0

We need a mechanism to fetch each of the above assembler instructions, one by one, so that we can extract the information from the instruction to perform the necessary steps inside the control unit. Each of the assembler instructions is stored in 16 bits, but need to be retrieved 8 bits at a time from memory as shown below. [See the two different instruction formats if you haven’t already done so.]

The control lines for each fetch would be set as follows:

// Example 1 - The Fetch Microcode

// example_1.ucode

// 1) Pass r7 though the ALU and store it in the mar.

// (Note: ORing a value with itself will pass it

// through the ALU without modifying it.)

a: a_sel=7, b_sel=7, alu_sel=OR, mar_sel=LOAD;

// 2) Read the value from memory and store

// in the lower 8 bits of the ir

b: read, ir0_sel=LOAD;

// 3) Repeat/Goto step 2 while the wait status line is on.

c: if wait then goto b endif;

// 4) Increment the program counter

d: a_sel=7, c_in, alu_sel=ADDA, result_sel=ALU, r7_write;

// 5) Pass r7 though the ALU and store it in the mar.

e: a_sel=7, b_sel=7, alu_sel=OR, mar_sel=LOAD;

// 6) Read the value from memory and store

// in the upper 8 bits of the ir.

f: read, ir1_sel=LOAD;

// 7) Repeat/Goto step 6 while the wait status line is on.

g: if wait then goto f endif;

// 8) Increment the program counter

h: a_sel=7, c_in, alu_sel=ADDA, result_sel=ALU, r7_write;

By overlapping parts of instructions, the above 8 steps can be compressed into 5 (see above right).

Each of these assembler instructions could be implemened with control lines as follows:

li $r0, 110// load immediate into register 0 the address of y

1.resultSel = 3 (8 bit literal value from ir); r0write = 1

lw $r1, 0($r0)// load word at address $r0 into $r1

1.Pass r0 through the ALU and store in the mar.

a_sel = 0; b_sel = 0; aluSel = 1(OR); marSel = 1(LOAD)

2.Read the value from memory and store in the mdr

read = 1; mdr_sel = 2 (LOAD from Memory)

3.Repeat/Goto step 2 while the wait status line is on.

4.Put the value in the mdr into r1

resultSel = 1 (value from mdr); r1write = 1

li $r2, 7// load immediate into register 2 the value 7

1. resultSel = 3 (8 bit literal value from ir); r2write = 1

add $r3, $r1, $r2// register 3 <- register 1 + register 2

1.a_sel = 1; b_sel = 2; aluSel = 4 (ADD); resultSel = 0 (Output from ALU);

r3write = 1

li$r0, 120// load immediate into register 0 the address of x

1.resultSel = 3 (8 bit literal value from ir); r0write = 1

sw$r3, 0($r0)// store word into register 3 from the memory address stored in register 0

1.Pass r0 through the ALU and store in the mar.

a_sel = 0; b_sel = 0; aluSel = 1(OR); mar_sel = 1(LOAD)

2.Pass r3 through the ALU and store in the mdr

a_sel = 3; b_sel = 3; aluSel = 1(OR); mdr_sel = 1(LOAD from ALU)

3.Write the value to memory

write = 1

4.Repeat/Goto step 3 while the wait status line is on.

Note that we have explicitly implemented each instruction. What remains is to implement a general mechanism for each different type of assembler instruction (li, lw, add, sw). This general mechanism would use information extracted from the instruction to know what registers or addresses to use.