Truth Table
ehmagrzm7i
1431354_.pdf
CS/CMPE 3430, sp16 – Assignment 5 (30 points total)
Due: Saturday May 7 th
, 11:59 pm on Blackboard
Instructor: Dr. Lei
READ: Sections 8.1-8.2, 8.4, Tables 8.2-8.3, Figures 8.2, 8.11-8.12, 8.16 of Spring 2016 Doering text
IMPORTANT: Submit all answers onto Blackboard using Logicworks .cct files. Use Excel spreadsheets to generate text,
truth tables and K-maps, and copy and paste into the .cct files.
In this assignment, you are to implement the ALU for the MIPS 3-stage pipeline CPU. The ALU is a combinational circuit
that executes arithmetic, logic, slt, and shift instructions for the CPU. The ALU takes two 32-bit operands as inputs, and
produces a 32-bit output. The ALU also takes in a function code that specifies the operation to be performed on the 32-
bit inputs. Consider the following MIPS instructions in Table 8.2 – add, addu, sub, sub, and, or, xor, nor, slt (set-less-
than), sltu (set-less-than-unsigned). The table shows the machine code of each instruction, and each machine code has
a 6-bit function code in the func 5:0 column. This function code signals to the ALU which operation to perform, and one
function code uniquely corresponds to one instruction. Table 8.3 has C/C++ implementations of each MIPS instruction.
Familiarize yourself with the high-level ALU implementation on Figure 8.12, with some details on Figure 8.11. The A
input bus is the A31..0 input. The B input bus is the B31..0 input. The D output bus is the 32-bit D31..0 output. The func
bus is the 6-bit function code input. The sa bus is the “shift amount” input, which is only used during shift operations.
Those instructions are the sll, srl, sra, sllv, srlv, and srav instructions on Table 8.2. The implementation consists of a set
of 32 slices. All slices are the same except for Slice 0 and slice MSB.
The inputs to all slices except for Slice 0 are the following:
a) A 6-bit function code input, corresponding to values in the func5:0 column of Table 8.2. This is the func bus input of each slice, which contains the 6 bits.
b) A 1-bit “A” input, which is a single bit of the 32-bit A31..0 input of the overall ALU. c) A 1-bit “B” input, which is a single bit of the 32-bit B31..0 input of the overall ALU. d) A 1-bit “C” input (on the right side of each slice), which is equivalent to the “carry-in” input of a full-adder circuit.
The outputs of each slice except for Slice MSB are the following:
a) A 1-bit “R” output, which is the result for any arithmetic (add, subtract), logic (and, or, xor, nor), or slt operation. b) A 1-bit “g” output, which is equal to 1 if the slice “Generates” a carry output. For instance, during an addition
operation, a slice generates a carry output if both “A” and “B” inputs are 1.
c) A 1-bit “p” output, which is equal to 1 if the slice “Propagates” a carry input to become a carry output. For instance, during an addition operation, a slice propagates a carry input if either “A” or “B”, or both, inputs are
“1”.
Slice MSB has an additional slt output, which is used only during an slt operation. An slt operation compares the 32-bit
numbers A31..0 and B31..0, to see if A31..0 is less than B31..0. If so, then the slt output is 1. Otherwise, the slt output is
0. The slt output bit can only be performed in Slice MSB, because it needs the A31, B31, and D31 bits for its
computation. The slt output bit is then sent to Slice 0, which sends the output to D0. All other output bits D1-D31 are set
to 0.
Hence, during an slt operation, the 32-bit output D31..0 is equal to either a 1 (i.e. 0000 0000 0000 0000 0000 0000 0000
0001), or a 0 (0000 0000 0000 0000 0000 0000 0000 0000). Lastly, Slice MSB also has an overflow output, which
indicates if arithmetic overflow occurred during addition or subtraction, and slice 0 does not have a “C” input.
CS/CMPE 3430, sp16 – Assignment 5 (30 points total)
Due: Saturday May 7 th
, 11:59 pm on Blackboard
Instructor: Dr. Lei
When implementing an addition/subtraction operation using Full Adder circuits, the carry output of the Full Adder for
each bit is normally fed to the carry input of the Full Adder for the next bit. This is called the “ripple-carry” method. The
ALU slices are like the Full Adder circuits, where each slice operates on a single bit. However, with 32 slices, there will be
a delay, simply because the ripple-carry method needs to travel through 32 total slices. In Figure 8.12, a set of Carry
Look Ahead Units (CLUs) in a tree structure is connected to each slice. The CLUs compute the carry input bits of each
slice is an efficient manner, avoiding the delays introduced by the ripple-carry method. The CLU circuit and tree-
structure implementations are provided in Figure 8.12.
Your task:
Implement the ALU slices and CLUs shown in Figure 8.12, but using PLAs to implement each slice. For each PLA,
minimize the number of product terms of each output by incorporating “don’t care” inputs (i.e. “x”). The PLAs should
then be packaged into a device symbol for each slice. To help you with the PLA implementations, refer to the 6-bit
function codes of each instruction. For this assignment, you only need to consider the add, addu, sub, subu, and, or,
xor, nor, slt, sltu instructions in Table 8.2. As a further simplification, you may assume that add/addu have the exact
same implementation, and sub/subu have the exact same implementation. slt/sltu DO NOT have the same
implementation. A C/C++ style pseudo code of each instruction can be found on Table 8.3 to assist your understanding
of each instruction.
All PLAs except for the ones in Slice 0 and Slice MSB should have a total of 9 inputs, and 4 outputs. The inputs are the 6
function code bits, and the A, B, and C inputs; the outputs are TS, p g, and R. For Slice 0, the C input is replaced with the
slt input. For Slice MSB, the PLA has 6 outputs – TS, p, g, R, slt, and ov (arithmetic overflow).
The purpose of the TS output is to disable the R output, in case if the operation is a shift operation, which requires the
use of the Barrel Shifter and not the slices. Since the TS output is driving the gate of a tri-state buffer, when it equals 1,
then the R output is disabled. Hence, the TS output needs to be Active Low, which you can specify in the PLA
implementation. The following figures show you how to connect the PLAs to the input and output ports of each slice.
You must create separate device symbols for Slice 0, Slice, and Slice MSB, packaging the PLAs and input/output ports.
Slice 0 PLA (for bit 0):
func5 func4 func3 func2 func1 func0
A B
slt
funcfunc
P G
R
In0 In1 In2 In3 In4 In5 In6 In7 In8
Out0 Out1 Out2 Out3
alu_plaslice0
CS/CMPE 3430, sp16 – Assignment 5 (30 points total)
Due: Saturday May 7 th
, 11:59 pm on Blackboard
Instructor: Dr. Lei
Slice PLA (for bits 1-30):
Slice MSB PLA (for bit 31):
A spreadsheet called “ALU_slice_plas_blank.xlsx” has been posted on Blackboard under Assignment 5 to assist you with
creating the three PLAs.
For this assignment, you are not required to complete the Barrel Shifter (Figure 8.16), but it is strongly recommended
that you complete the Barrel Shifter in order to not have to redo the overall ALU device symbol in the next assignment.
If the instruction involves a shift operation (i.e. sll, srl, sra, sllv, srlv, and srav), then the Barrel Shifter output is used. If
the instruction involves arithmetic, logic, or slt operations, then the slices output is used. The TS output of the PLAs in
each slice, along with the 32-bit tri-state buffer in the Barrel Shifter, work together such that the Barrel Shifter output
and the slices output do not conflict with each other. Once you finish implementing the Slices, CLUs, and Barrel Shifter (if
you choose to do so in this assignment), package everything into a top-level ALU device symbol.
See next page for instructions regarding deliverables for the assignment.
funcfunc
A B C
P G
func5 func4 func3 func2 func1 func0
In0 In1 In2 In3 In4 In5 In6 In7 In8
Out0 Out1 Out2 Out3
alu_plaslice1-30
R
funcfunc func5 func4 func3 func2 func1 func0
A B C
ov slt P G
R
In0 In1 In2 In3 In4 In5 In6 In7 In8
Out0 Out1 Out2 Out3 Out4 Out5
plaslice_msb
CS/CMPE 3430, sp16 – Assignment 5 (30 points total)
Due: Saturday May 7 th
, 11:59 pm on Blackboard
Instructor: Dr. Lei
Deliverables: Submit on a Logicworks file your ALU device symbol, along with an attached test circuit with Hex
Keyboards and Displays demonstrating the operation of the add, addu, sub, sub, and, or, xor, nor, slt, sltu instructions.
For each instruction, write the 32-bit Hex outputs (in the same logicworks file) of each instruction for the following 32-
bit inputs:
32-bit A input: 0x5A5A5A5A
32-bit B input: 0x6B6B6B6B
The figure below shows an example of what your submission should look like. The function code is set to 0x2A, which
performs the slt instruction of the two inputs. The inputs are set to 0x5A5A5A5A and 0x6B6B6B6B. As a sanity check,
your inputs and outputs for the slt instruction should at least match the ones in the figure. Note that the slt output in
this example is 1, since the 32-bit A31..0 input is less than the 32-bit B31..0 input.
A 0
A 1
A 2
A 3
A 4
A 5
A 6
A 7
A 8
A 9
A 1
0 A
1 1
A 1
2 A
1 3
A 1
4 A
1 5
A 1
6 A
1 7
A 1
8 A
1 9
A 2
0 A
2 1
A 2
2 A
2 3
A 2
4 A
2 5
A 2
6 A
2 7
A 2
8 A
2 9
A 3
0 A
3 1
B 0
B 1
B 2
B 3
B 4
B 5
B 6
B 7
B 8
B 9
B 1
0 B
1 1
B 1
2 B
1 3
B 1
4 B
1 5
B 1
6 B
1 7
B 1
8 B
1 9
B 2
0 B
2 1
B 2
2 B
2 3
B 2
4 B
2 5
B 2
6 B
2 7
B 2
8 B
2 9
B 3
0 B
3 1
D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24 D25 D26 D27 D28 D29 D30 D31
0 fu
n c0
fu n
c1 fu
n c2
fu n
c3 fu
n c4
fu n
c5
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0
0
0
0
0
0
0
1
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
0 1
2 3
4 5
6 7
8 9
A B
C D
E F
ALU
A
B
fu n
c
D
sa
ov
slt output = 1
