Description
Exercise A: Datapath and control signals
Read This First
The point of this exercise is to make a detailed examination of the behaviour of the
single-cycle processor circuit of Figure 7.11 in the course textbook.
What to Do, Part I
Suppose the instruction
lw $t8, 40($sp)
is located at address 0x0040_0154 in instruction memory. Suppose that just before
the instruction is executed, the following GPRs have the given values:
$sp = 0x7fff_fe90
$t7 = 0x0005_4321
Finally suppose that data memory contains the following words:
ADDRESS DATA
0x7fff_feb0 0x0001_2345
0x7fff_feb4 0x0002_3456
0x7fff_feb8 0x0003_4567
0x7fff_febc 0x0004_5678
0x7fff_fec0 0x0005_6789
0x7fff_fec4 0x0006_789a
0x7fff_fec8 0x0007_89ab
(Note: You have been given more information than you actually need to solve the
problem.)
During the clock cycle in which the instruction is executed, most of the signals
in the circuit will change values. This problem asks you to find the values of some
of these signals just before the end of the clock cycle, when all of the signals will
have stabilized to their final values for the clock cycle.
Determine and write out the values of these signals:
• The values of the control signals MemtoReg, MemWrite, Branch, ALUControl,
ALUSrc, RegDst, and RegWrite. Use base two for the 3-bit ALUControl
signal.
• The values of the 5-bit A1, A2, and A3 inputs to the Register File, as base
two numbers.
• The values of the 32-bit ALU input signals and the ALUResult signal, in
hexadecimal format.
• The value of the 32-bit WD3 input to the Register File, in hexadecimal format.
• The value, in hexadecimal format, of the 32-bit output of the adder that
computes PCBranch, the branch target address. (The branch target address
is useless in an lw instruction, of course, but this circuit will compute it
anyway.)
(If you don’t have a calculator that can display numbers in hexadecimal, you may
want to use the C programs in encm369w18lab07/exA to help generate some of bit
patterns you will need.)
ENCM 369 Winter 2018 Lab 7 page 3 of 9
What to Do, Part II
Repeat Part I, but this time assume that the instruction address is 0x0040_0158
and the instruction is
and $s2, $s2, $t3
Use these starting values for the source registers:
$s1 = 0x1002_d364
$t5 = 0xffff_ffc0
What to Hand In
Hand in your answers to Parts I and II. They may be either typed or neatly
handwritten, whichever you find easier.
Exercise B: Immediate-mode instructions in the singlecycle machine
Read This First
A good way to see whether you understand the design of the circuit of Figure 7.11
in your textbook is to try to enhance it to support more instructions. When doing
this kind of exercise it is important to remember this:
It’s not enough to modify the datapath and control so that the new instructions work—the eight instructions already implemented must continue to work properly!
Let’s consider adding support for the following useful instructions: addi, slti,
andi, and ori.
It turns out that including just addi is easy. The datapath is already set up to
have the ALU add a GPR and a sign-extended 16-bit constant. All we have to do is
add a row for addi to the table that specifies the main decoder within the Control
Unit. This is done in Section 7.3.3 of the textbook.
Since the datapath doesn’t have to change at all, and no new control signals
have been added, it’s obvious that the eight existing instructions will still work.
However, the problem becomes more difficult if we move on to slti, andi, and
ori. For the andi and ori instructions, the 16-bit constant is zero-extended to 32
bits, not sign-extended. For all three new instructions, the existing communication
between the main decoder and the ALU decoder is not capable of getting the ALU
to do an slt, and, or or operation.
What to Do
Suppose the Sign Extend unit of Figure 7.11 is replaced with the unit shown in
Figure 1.
Suppose also that the ALUOp signal in textbook Figure 7.12 is widened from
2 bits to 3 bits. Bit patterns 000, 001, and 010 should mean what 00, 01, and 10
meant in the original design, and other 3-bit patterns can be used to support slti,
andi, and ori.
Show how the above two modifications will allow support for this set of twelve
instructions:
add, sub, and, or, slt,
lw, sw, beq,
addi, slti, andi, ori
ENCM 369 Winter 2018 Lab 7 page 4 of 9
Figure 1: A circuit to do either sign-extension, when SZ = 1, or zero-extension, when
SZ = 0. A symbol is on the left, and a simple implementation with an and gate is on the
right.
16
32 SZ Y31:0 Extend
.
.
.
.
.
.
.
.
.
Y31
Y15
SZ
Instr15
Y30
Y17
Y16
Y14
Y1
Y0
Instr14
Instr1
Instr0
.
.
.
.
.
.
Your answer should be:
• a few sentences to explain how the main decoder and ALU decoder within the
Control Unit are modified, and what the SZ input of the Extend unit should
be connected to;
• two tables, similar to textbook Tables 7.2 and 7.3, to completely specify how
the redesigned main decoder and ALU decoder should behave.
What to Hand In
Your answer, as described in “What to Do”.
Exercise C: Support for shift instructions
Read This First
Let’s return to the processor of Figure 7.11, forget about the immediate-mode instructions of Exercise B, and think about adding support for sll and srl. Suppose
the following combinational logic unit is available:
Shift
32 32
5
LR
DI
C
DO
DI stands for “Data In” and DO stands for “Data Out”. If the control input LR
is 1, the unit does a left shift, and if it’s 0, the unit does a right shift. The input C
is a 5-bit shift count—for example, if C = 00010two, the shift amount is two bit
positions.
Note that the instruction formats are as follows, where sssss is a 5-bit code
for the source GPR, ddddd is a 5-bit code for the destination GPR, and ccccc is a
5-bit unsigned shift count:
sll: 000000_sssss_00000_ddddd_ccccc_000000
srl: 000000_sssss_00000_ddddd_ccccc_000010
ENCM 369 Winter 2018 Lab 7 page 5 of 9
Figure 2: Incomplete single-cycle processor for Exercise C.
Shift
0
1
0
1
0
1
3
PC
0
0
1
RD
A
I-Mem
+
Sign Extend
+
LR
DI
C
DO
MemtoReg
MemWrite
Branch
ALUSrc
RegDst
RegWrite
Control
Unit
opcode
funct
WD3
WE3 RD1 A1
R-File
A2
A3
25:21
20:16
20:16
RD2
ALU
Zero
ALUResult RD
A
D-Mem
WD
ALUControl
15:11
4
Instr
31:26
5:0
WE
15:0 <<2
PCPlus4
PCBranch
(aka branch target address)
CLK
CLK CLK
PC
ENCM 369 Winter 2018 Lab 7 page 6 of 9
What to Do
Print page 5, so that you have a hard copy of Figure 2. This is a modified version of
textbook Figure 7.11—the Shift unit has been added, along with two new unnamed
control signals. As you can see, there are a number of unconnected wires.
Choose helpful names for the new control signals.
Add connections and functional units (hint: a new mux might be helpful) to
the schematic to show how sll and srl can be supported, while allowing all of the
eight original instructions to run correctly. Be as tidy and clear as you can with
your wiring and labelling of wires.
For the Control Unit, it turns out to be tedious to work through all of the
changes needed to the two-level main-decoder/ALU-decoder structure. Instead,
let’s just specify the Control Unit as a single element. To do that, make a table
that looks like this:
Instruction
RegWrite
RegDst
ALUSrc
ALUControl
Branch
MemWrite
MemtoReg
ADD 1 1 0 010 0 0 0
SUB 1 1 0 110 0 0 0
AND 1 1 0 000 0 0 0
OR 1 1 0 001 0 0 0
SLT 1 1 0 111 0 0 0
LW 1 0 1 010 0 0 1
SW 0 X 1 010 0 1 X
BEQ 0 X 0 110 1 0 X
SLL
SRL
Write in the names you’ve chosen for your new control signals, and fill in the two
blank columns and two blank rows with 0’s, 1’s, and X’s, so that all ten instructions
will work correctly.
What to Hand In
Hand in your completed schematic and your completed table for the Control Unit.
Exercise D: A single-cycle machine for a different
instruction set
Attention!
This exercise will not be marked, because it’s pretty easy to find a solution for it
using previous years’ ENCM 369 web pages. However, please do not think of this
as an optional exercise. Doing the work may be very helpful as you prepare for
Midterm #2.
Read This First
This exercise is adapted from a problem on the Winter 2006 final exam.
The Exam16 ISA (instruction set architecture) describes a system in which
addresses, instructions, and data words are all 16 bits wide. It has sixteen 16-bit
general purpose registers, and a 16-bit PC. The instructions of Exam16 are given
ENCM 369 Winter 2018 Lab 7 page 7 of 9
in the table in Figure 3. Note that unlike with MIPS, there are no offsets built into
Exam16 load and store instructions.
Figure 4 is a nearly-complete datapath for a computer that implements the
Exam16 ISA. It is very much in the style of the single-cycle MIPS subset implementation studied in ENCM 369. Note that there are two 16-bit adders and a 16-bit
ALU. The ALUOp signal works as follows: 00 asks for addition, 01 for subtraction,
and 10 for set-on-less-than. The circuit labeled “All Bits 0?” is a big nor gate—the
1-bit output is 1 if all 16 input bits are 0, and is 0 otherwise.
Data Memory in Figure 4 works very slightly differently from Data Memory
in examples in the 2018 textbook and 2018 lectures. In Figure 4, MemRead and
MemWrite should both be zero for instructions that do not access memory, to avoid
wasting energy. Values of MemRead and MemWrite are obvious for loads and stores,
I hope!
Figure 3: Exam16 instruction set.
Mnemonic Format Description
add 0000_ssss_tttt_dddd Add source registers selected by bits ssss
and tttt, put result in register selected
by bits dddd.
sub 0001_ssss_tttt_dddd Same as add, except ALU operation is
subtraction.
slt 0010_ssss_tttt_dddd Same as add, except ALU operation is seton-less-than.
brz 0011_ssss_oooo_oooo Branch if register is zero: If register selected by bits ssss contains zero, branch
forward or backward by number of instructions in 8-bit 2’s-complement offset
oooo_oooo.
lw 0100_0000_aaaa_dddd Using register selected by bits aaaa as an
address, load word from data memory into
register selected by bits dddd.
sw 0101_ssss_aaaa_0000 Using register selected by bits aaaa as an
address, store word from register selected
by bits ssss into data memory.
What to Do
In some of the following parts, it may be helpful to draw a simple diagram or two
to go along with the text you write to answer the question being asked.
Part a. The Address and Write Data inputs to the Data Memory are not connected
to anything in Figure 4. What signals should be sent to these inputs? Explain why.
Part b. The WD3 input to the Register File is not connected to anything. How
should this signal be driven? Here is a hint: Introduce a new control signal, give
it a name, and use it to control a multiplexer. Briefly give reasons to support your
design.
Part c. The input to the PC register is not connected to anything. How should
this signal be driven? A new control signal, a new multiplexer, and perhaps some
other new, simple logic element will be needed. Briefly give reasons to support your
design.
ENCM 369 Winter 2018 Lab 7 page 8 of 9
Figure 4: Nearly complete datapath for Exam16 single-cycle implementation.
Instruction
Memory
Instruction
[15−0]
PC Address
All
Bits 0?
Shift
Left 1
16
16
Instruction[11−8]
Instruction[7−0] Sign
Extend
16
16
clock
Instruction[15−12]
to Control Unit
RegWrite clock
MemRead MemWrite clock
ALUOp
Adder
#1
Adder
#2
ALU
2
Instruction[7−4]
Instruction[3−0]
WD3
Registers
A1
A2
A3 RD2
RD1
WE3
Address
Data
Write
Data
Memory
Read
Data
Figure 5: Table of control signals for part d of Exercise D.
Instruction MemRead MemWrite RegWrite ALUOp
add
sub
slt
brz
lw
sw
Part d. Make a copy of the table from Figure 5, or print the page that it is on.
Then fill in all the blank cells with the correct values of control signals for the given
instructions.
The last two columns are reserved for the new control signals you introduced in
parts b and c—please write in the names of these signals.
Use “X” in table cells to indicate that a particular control signal is a “don’t care”
for a particular instruction.
Part e. Suppose you want to extend the Exam16 ISA to include an addc (“add
constant”) instruction with the following format:
1000_ssss_cccc_dddd
ssss encodes the source register, dddd encodes the destination register, and cccc
encodes a constant in the range from 0 to 15. Describe all the datapath changes (not
control changes) that would be needed to add support for addc while continuing to
support the original six Exam16 instructions.
ENCM 369 Winter 2018 Lab 7 page 9 of 9
What to Hand In
Nothing. You can check your answers against solutions that will be posted well in
advance of Midterm #2.
