CS3351 - Unit IV- Processor

Syllabus
Instruction Execution – Building a Data Path – Designing a Control Unit – Hardwired Control,
Microprogrammed Control – Pipelining – Data Hazard – Control Hazards.
3.1 Basic MIPS implementation
An Overview of the Implementation
The first two steps are identical for every instruction:
1. Send the program counter (PC) to the memory that contains the code and fetch the instruction
from that memory.
2. Read one or two registers, using fields of the instruction to select the registers to read.
After these two steps, the actions required to complete the instruction depend on the three instruction class.
a. Memory-reference - lw, sw
b. Arithmetic-logical - add, sub, and, or, slt
c. Branches - beq, j

Figure3.1 shows data going to a particular unit as coming from two different sources. For example,
 The value written into the PC can come from one of two adders
 The data written into the register file can come from either the ALU or the data memory,
 The second input to the ALU can come from a register or the immediate field of the
instruction.
1. All instructions start by using the program counter to supply the instruction address to the instruction
memory.
2. After the instruction is fetched, the register operands used by an instruction are specified by fields of
that instruction.
3. Once the register operands have been fetched, they can be operated on to compute a memory address
(for a load or store), to compute an arithmetic result (for an integer arithmetic-logical instruction), or
a compare (for a branch).
4. If the instruction is an arithmetic-logical instruction, the result from the ALU must be written to a
register.
5. If the operation is a load or store, the ALU result is used as an address to either store a value from the
registers or load a value from memory into the registers.
6. The result from the ALU or memory is written back into the register file.
7. Branches require the use of the ALU output to determine the next instruction address, which comes
either from the ALU (where the PC and branch off set are summed) or from an adder that increments
the current PC by 4.
8. The thick lines interconnecting the functional units represent buses, which consist of multiple signals.
9. The arrows are used to guide the reader in knowing how information flows.
10. Since signal lines may cross, crossing lines are explicitly connected by the presence of a dot where
the lines cross.
Multiplexor or Data Selector
 A logic element which is added to wire the data lines that chooses from the multiple sources and
steers one of those sources to its destination.
 The control lines are set based primarily on information taken from the instruction being executed.
Figure 3.2 shows the data path
A control unit, has the instruction as an input, is used to determine how to set the control lines for
the functional units and two of the multiplexors.

1
 Figure3.1 High-level view of a MIPS implementation

Figure 3.2 the MIPS subset, including necessary multiplexors and control lines.
i. The top multiplexor (“Mux”) controls the value replaces the PC (PC + 4 or the branch destination
address)
 It is controlled by the gate that “ANDs” together the Zero output of the ALU and a control
signal that indicates that the instruction is a branch.
ii. The middle multiplexor is used to return the output of the ALU or the output of the data memory into
the register file.
iii. The bottommost multiplexor determines, whether the second ALU input is from the registers or from
the offset field of the instruction.
iv. The added control lines are straightforward and states the operation performed at the ALU,
a. whether the data memory should read or write,
b. Whether the registers should perform a write operation.
3.2 Building datapath
Datapath element:
 A unit used to operate on or hold data within a processor.
 In the MIPS implementation, the datapath elements include the instruction and data memories,
the register file, the ALU, and adders.

2
1. Figure 3.3a shows the first element needed: A memory unit to store the instructions of a program and
supply instructions given an address.
 The instruction memory need only provide read access because the datapath does not write
instructions.
 The instruction memory is treated as combinational logic since it only reads,
 Output at any time reflects the contents of the location specified by the address input,
 No read control signal is needed.
2. Figure 3.3b shows the program counter (PC), a register that holds the address of the current instruction.
 The program counter is a 32-bit register that is written at the end of every clock cycle.
 So, it does not need a write control signal.
3. Figure 3.3c shows the adder needed to increment the PC to the address of the next instruction.
 The adder is a wired ALU that always add its two 32-bit inputs and place the sum on its output.

Figure 3.3 Elements needed for datapath design Figure 3.4 Combination of three elements
4. Figure 3.4 shows how to combine the three elements from Figure 3.3 to form a datapath that fetches
instructions and increments the PC to obtain the address of the next sequential instruction.
R-format instructions
1. They all read two registers, perform an ALU operation on the contents of the registers, and write the
result to a register called as R-type instructions or arithmetic-logical instructions.
2. This instruction class includes add, sub, AND, OR, and slt.
3. The processor’s 32 general-purpose registers are stored in a structure called a register file.
 It is a collection of registers in which any register can be read or written by specifying the number of
the register in the file.
 It contains the register state of the computer and an ALU to operate on the values read from the
registers.
4. R-format instructions have three register operands,
a. To read two data words from the register file
 an input to the register file that specifies the register number to be read
 an output from the register file that will carry the value that has been read from the registers.
b. Write one data word into the register file for each instruction.
 Two inputs: one to specify the register number to be written and one to supply the data to be
written into the register.
 Outputs the contents of whatever register numbers are on the Read register inputs
5. Writes are controlled by the write control signal, which must be asserted for a write to occur at the clock
edge.
6. Figure 3.5a shows the elements of R-format instruction, a total of four inputs are needed (3 for register
numbers and 1 for data) and two outputs (both for data).

3
7. The register number inputs are 5 bits wide to specify one of 32 registers (32 = 25), whereas the data input
and two data output buses are each 32 bits wide.
8. Figure 3.5b shows the ALU, which takes two 32-bit inputs and produces a 32-bit result, as well as a 1-bit
signal if the result is 0.

Figure 3.5 Elements of R-Format instruction. Figure 3.6. Elements of loads and stores
Implementation of loads and stores
1. The MIPS load word and store word instructions computes a memory address by adding the base register,
which is $t2, to the 16-bit signed off set field contained in the instruction.
lw $t1,offset_value($t2)
sw $t1,offset_value ($t2)
2. A sign-extend unit is needed to extend the 16-bit off set field in the instruction to a 32-bit signed value,
and a data memory unit to read from or write to as shown in Figure 3.6.
3. sign-extend To increase the size of a data item by replicating the high-order sign bit of the original data
item in the high order bits of the larger, destination data item.
4. The data memory must be written on store instructions; hence, it has read and write control signals, an
address input, and an input for the data to be written into memory.
5. Diagram explanation
 The memory unit is a state element with inputs for the address and the write data, and a single output
for the read result.
 There are separate read and write controls, although only one of these may be asserted on any given
clock.
 The memory unit needs a read signal, since, unlike the register file, reading the value of an invalid
address can cause problems.
 The sign extension unit has a 16-bit input that is sign-extended into a 32-bit result appearing on the
output.
 The data memory is assumed to be edge-triggered for writes. Standard memory chips actually have a
write enable signal that is used for writes.
 Although the write enable is not edge-triggered, our edge-triggered design could easily be adapted to
work with real memory chips.
Branch instructions
beq $t1,$t2,offset
1. The beq instruction has three operands,
 Two registers that are compared for equality,
 A 16-bit off set used to compute the branch target address relative to the branch instruction address.
2. Branch target address
 The address specified in a branch, which becomes the new program counter (PC) if the branch is
taken.

4
  In the MIPS architecture the branch target is given by the sum of the offset field of the instruction and
the address of the instruction following the branch.
3. Definition of branch instructions
a. ISA specifies that the base for the branch address calculation is the address of the instruction
following the branch.
b. It also states that the offset field is shifted left 2 bits so that it is a word off set; this shift increases the
effective range of the offset field by a factor of 4.
4. Branch taken
 A branch where the branch condition is satisfied and the program counter (PC) becomes the branch
target. All unconditional jumps are taken branches.
5. Branch not taken or (untaken branch)
 A branch where the branch condition is false and the program counter (PC) becomes the address of
the instruction that sequentially follows the branch.
Thus, the branch datapath must do two operations:
i. Compute the branch target address
ii. Compare the register contents.
6. Figure 3.7 shows the structure of the datapath segment that handles branches. The data path for a branch
uses
 The ALU -evaluates the branch condition
 A separate adder - computes the branch target (incremented PC + the branch displacement), shifted
left 2 bits.
7. Shift left 2 unit – routes the signals between input and output that adds 00two to the low-order end of the
sign-extended off set field; no actual shift hardware is needed, since the amount of the “shift” is constant.
8. Since the offset was sign-extended from 16 bits, the shift throws away only “sign bits.”
9. Control logic –decides whether the incremented PC or branch target should replace the PC, based on the
Zero output of the ALU.

Figure 3.7. The datapath for a branch instruction

5
3. Therefore a separate memory is needed for instructions and data. Although some of the functional units
need to be duplicated, many of the elements can be shared by different instruction flows.

Figure 3.9. MIPS architecture data path for different instruction classes.
4. To share a datapath element between two different instruction classes,
 A multiplexor is used to allow multiple connections to the input of an element,
 A control signal is used to select one among the multiple inputs.
5. The branch instruction uses the main ALU for comparison of the register operands, so the adder is used
for computing the branch target address.
6. An additional multiplexor is required to select either the sequentially following instruction address (PC +
4) or the branch target address to be written into the PC.
7. The control unit must be able to take inputs and generate a write signal for each state element, the
selector control for each multiplexor, and the ALU control.