CSE1003-Digital Logic Design Arithmetic-logic units

• An arithmetic-logic unit, or ALU, performs many different arithmetic

and logic operations. The ALU is the “heart” of a processor—you could
say that everything else in the CPU is there to support the ALU.
• Here’s the plan:
– We’ll show an arithmetic unit first, by building off ideas from the
adder-subtractor circuit.
– Then we’ll talk about logic operations a bit, and build a logic unit.
– Finally, we put these pieces together using multiplexers.
• We use some examples from the textbook, but things are re-labeled
and treated a little differently.

1 2

The four-bit adder It’s the adder-subtractor again!

• The basic four-bit adder always computes S = A + B + CI. • Here the signal Sub and some XOR gates alter the adder inputs.
– When Sub = 0, the adder inputs A, B, CI are Y, X, 0, so the adder
produces G = X + Y + 0, or just X + Y.
– When Sub = 1, the adder inputs are Y’, X and 1, so the adder output
is G = X + Y’ + 1, or the two’s complement operation X - Y.

• But by changing what goes into the adder inputs A, B and CI, we can
change the adder output S.
• This is also what we did to build the combined adder-subtractor circuit.

3 4
 The multi-talented adder Modifying the adder inputs
• So we have one adder performing two separate functions. • By following the same approach, we can use an adder to compute other
• “Sub” acts like a function select input which determines whether the functions as well.
circuit performs addition or subtraction. • We just have to figure out which functions we want, and then put the
• Circuit-wise, all “Sub” does is modify the adder’s inputs A and CI. right circuitry into the “Input Logic” box .

5 6

Some more possible functions The role of CI

• We already saw how to set adder inputs A, B and CI to compute either • The transfer and increment operations have the same A and B inputs,
X + Y or X - Y. and differ only in the CI input.
• How can we produce the increment function G = X + 1? • In general we can get additional functions (not all of them useful) by
using both CI = 0 and CI = 1.
One way: Set A = 0000, B = X, and CI = 1 • Another example:
– Two’s-complement subtraction is obtained by setting A = Y’, B = X,
• How about decrement: G = X - 1? and CI = 1, so G = X + Y’ + 1.
– If we keep A = Y’ and B = X, but set CI to 0, we get G = X + Y’. This
A = 1111 (-1), B = X, CI = 0 turns out to be a ones’ complement subtraction operation.

• How about transfer: G = X?

(This can be useful.)

A = 0000, B = X, CI = 0

This is almost the same as the

increment function!

7 8
 Table of arithmetic functions Mapping the table to an adder
• Here are some of the different possible arithmetic operations. • This second table shows what the adder’s inputs should be for each of
• We’ll need some way to specify which function we’re interested in, so our eight desired arithmetic operations.
we’ve randomly assigned a selection code to each operation. – Adder input CI is always the same as selection code bit S0.
– B is always set to X.
– A depends only on S2 and S1.
S2 S1 S0 Arithmetic operation
• These equations depend on both the desired operations and the
0 0 0 X (transfer)
assignment of selection codes.
0 0 1 X+1 (increment)
0 1 0 X+Y (add) Selection code Desired arithmetic operation Required adder inputs
0 1 1 X+Y+1 S2 S1 S0 G (A + B + CI) A B CI
1 0 0 X + Y’ (1C subtraction) 0 0 0 X (transfer) 0000 X 0
1 0 1 X + Y’ + 1 (2C subtraction) 0 0 1 X+1 (increment) 0000 X 1
1 1 0 X–1 (decrement) 0 1 0 X+Y (add) Y X 0
1 1 1 X (transfer) 0 1 1 X+Y+1 Y X 1
1 0 0 X + Y’ (1C subtraction) Y’ X 0
1 0 1 X + Y’ + 1 (2C subtraction) Y’ X 1
1 1 0 X–1 (decrement) 1111 X 0
1 1 1 X (transfer) 1111 X 1
9 10

Building the input logic Primitive gate-based input logic

• All we need to do is compute the adder input A, given the arithmetic • We could build this circuit using primitive gates.
unit input Y and the function select code S (actually just S2 and S1). • If we want to use K-maps for simplification, then we should first
• Here is an abbreviated truth table: expand out the abbreviated truth table.
– The Y that appears in the output column (A) is actually an input.
– We make that explicit in the table on the right.
• Remember A and Y are each 4 bits long!
S2 S1 A
0 0 0000
S2 S1 Yi Ai
0 1 Y
0 0 0 0
1 0 Y’
S2 S1 A 0 0 1 0
1 1 1111
0 0 0000 0 1 0 0
0 1 Y 0 1 1 1
1 0 Y’ 1 0 0 1
• We want to pick one of these four possible values for A, depending on 1 1 1111 1 0 1 0
S2 and S1. 1 1 0 1
1 1 1 1

11 12
 Primitive gate implementation Bitwise operations
• From the truth table, we can find • Most computers also support logical operations like AND, OR and NOT,
an MSP: but extended to multi-bit words instead of just single bits.
• To apply a logical operation to two words X and Y, apply the operation
S1 on each pair of bits Xi and Yi:
0 0 1 0
S2 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
Yi AND 1 1 1 0 OR 1 1 1 0 XOR 1 1 1 0
1 0 1 0 1 1 1 1 01 01

Ai = S2Yi’ + S1Yi • We’ve already seen this informally in two’s-complement arithmetic,

when we talked about “complementing” all the bits in a number.
• Again, we have to repeat this
once for each bit Y3-Y0,
connecting to the adder inputs
A3-A0.

• This completes our arithmetic

unit.

13 14

Bitwise operations in programming Bitwise operations in networking

• Languages like C, C++ Java and HDLs provide bitwise logical operations: • IP addresses are actually 32-bit binary numbers, and bitwise operations
can be used to find network information.
& (AND) | (OR) ^ (XOR) ~ (NOT) • For example, you can bitwise-AND an address 192.168.10.43 with a
• These operations treat each integer as a bunch of individual bits: “subnet mask” to find the “network address,” or which network the
machine is connected to.
13 & 25 = 9 because 01101 & 11001 = 01001
192.168. 10. 43 = 11000000.10101000.00001010.00101011
• They are not the same as the operators &&, || and !, which treat each & 255.255.255.224 = 11111111.11111111.11111111.11100000
integer as a single logical value (0 is false, everything else is true): 192.168. 10. 32 = 11000000.10101000.00001010.00100000

13 && 25 = 1 because true && true = true • You can use bitwise-OR to generate a “broadcast address,” for sending
data to all machines on the local network.
• Bitwise operators are often used in programs to set a bunch of Boolean
options, or flags, with one argument. 192.168. 10. 43 = 11000000.10101000.00001010.00101011
• Easy to represent sets of fixed universe size with bits: | 0. 0. 0. 31 = 00000000.00000000.00000000.00011111
– 1: is member, 0 not a member. Unions: OR, Intersections: AND 192.168. 10. 63 = 11000000.10101000.00001010.00111111

15 16
 Defining a logic unit Our simple logic unit
• A logic unit supports different logical
functions on two multi-bit inputs X and Y,
producing an output G.
• This abbreviated table shows four
possible functions and assigns a selection
code S to each. • Inputs:
– X (4 bits)
S1 S0 Output – Y (4 bits)
0 0 Gi = XiYi – S (2 bits)
0 1 Gi = Xi + Yi • Outputs:
1 0 Gi = Xi  Yi – G (4 bits)
1 1 Gi = Xi’

• We’ll just use multiplexers and some

primitive gates to implement this.
• Again, we need one multiplexer for each
bit of X and Y.

17 18

Combining the arithmetic and logic units Our ALU function table
• Now we have two pieces of the puzzle: • This table shows a sample
– An arithmetic unit that can compute eight functions on 4-bit inputs. function table for an ALU.
S3 S2 S1 S0 Operation
– A logic unit that can perform four functions on 4-bit inputs. • All of the arithmetic operations
0 0 0 0 G=X
have S3=0, and all of the logical
0 0 0 1 G=X+1
operations have S3=1.
• We can combine these together into a single circuit, an arithmetic-logic 0 0 1 0 G=X+Y
unit (ALU). • These are the same functions we
0 0 1 1 G=X+Y+1
saw when we built our arithmetic
0 1 0 0 G = X + Y’
and logic units a few minutes ago.
0 1 0 1 G = X + Y’ + 1
• Since our ALU only has 4 logical 0 1 1 0 G=X–1
operations, we don’t need S2. The 0 1 1 1 G=X
operation done by the logic unit
1 x 0 0 G = X and Y
depends only on S1 and S0.
1 x 0 1 G = X or Y
1 x 1 0 G=XY
1 x 1 1 G = X’

19 20
 A complete ALU circuit Comments on the multiplexer

The / and 4 on a line indicate that it’s actually four lines.

• Both the arithmetic unit and the logic unit are “active” and produce
outputs.
4
– The mux determines whether the final result comes from the
arithmetic or logic unit.
4 Cout should be ignored – The output of the other one is effectively ignored.
•
when logic operations are
performed (when S3=1). Our hardware scheme may seem like wasted effort, but it’s not really.
4 – “Deactivating” one or the other wouldn’t save that much time.
4
– We have to build hardware for both units anyway, so we might as
4
well run them together.
• This is a very common use of multiplexers in logic design.
G is the final ALU output.
• When S3 = 0, the final
output comes from the
arithmetic unit.
• When S3 = 1, the
output comes from the
logic unit.
The arithmetic and logic units share the select inputs S1
and S0, but only the arithmetic unit uses S2.

21 22

The completed ALU ALU summary

• This ALU is a good example of hierarchical design. • We looked at:
– With the 12 inputs, the truth table would have had 212 = 4096 lines. – Building adders hierarchically, starting with one-bit full adders.
That’s an awful lot of paper. – Representations of negative numbers to simplify subtraction.
– Instead, we were able to use components that we’ve seen before to – Using adders to implement a variety of arithmetic functions.
construct the entire circuit from a couple of easy-to-understand – Logic functions applied to multi-bit quantities.
components.
– Combining all of these operations into one unit, the ALU.
• As always, we encapsulate the complete circuit in a “black box” so we
can reuse it in fancier circuits. • Where are we now?
– We started at the very bottom, with primitive gates, and now we
can understand a small but critical part of a CPU.
4 – This all built upon our knowledge of Boolean algebra, Karnaugh maps,
multiplexers, circuit analysis and design, and data representations.
4
4
4

23 24
1 2

Datapaths
• We’ll focus on computer architecture: how to assemble the
combinational and sequential components we’ve studied so far into a
complete computer.
• The datapath is the part of the central processing unit (CPU) that does
the actual computations.

3 4
 Keeping it simple! An overview of CPU design
• Abstraction is very helpful in understanding processors. • We can divide the design of our CPU into three parts:
– Although we studied how devices like registers and muxes are built, – The datapath does all of the actual data processing.
we don’t need that level of detail here. – An instruction set is the programmer’s interface to CPU.
– You should focus more on what these component devices are doing, – A control unit uses the programmer’s instructions to tell the
and less on how they work. datapath what to do.
• Otherwise, it’s easy to get bogged down in the details, and datapath and
control units can be a little intimidating. • We’ll look in detail at a processor’s datapath, which is responsible for
doing all of the dirty work.
– An ALU does computations, as we’ve seen before.
– A limited set of registers serve as fast temporary storage.
– A larger, but slower, random-access memory is also available.

5 6

What’s in a CPU? Register transfers

ALU ALU

Registers Registers

• A processor is just one big sequential circuit. • Fundamentally, the processor is just moving data between registers,
– Some registers are used to store values, which form the state. possibly with some ALU computations.
– An ALU performs various operations on the data stored in the • To describe this data movement more precisely, we’ll use a register
registers. transfer language.
– The objects in the language are registers.
– The basic operations are transfers, where data is copied from one
register to another.
• We can also use the ALU to perform arithmetic operations on the data
while we’re transferring it.

7 8
 Register transfer language review (from Chapter 8) Register transfer operations (cont’d)
• Two-character names denote registers, such as R0, R1, DR, or SA. • We can apply arithmetic operations to registers.
• Arrows indicate data transfers. To copy the contents of the source
register R2 into the destination register R1 in one clock cycle: R1  R2 + R3
R3  R1 - 1
R1  R2
• Logical operations are applied bitwise. AND and OR are denoted with
• A conditional transfer is performed only if the Boolean condition in special symbols, to prevent confusion with arithmetic operations.
front of the colon is true. To transfer R3 to R2 when K = 1:
R2  R1  R2 bitwise AND
K: R2  R3
R3  R0  R1 bitwise OR

• Multiple transfers on the same clock cycle are separated by commas.

• Lastly, we can shift registers. Here, the source register R1 is not
R1  R2, K: R2  R3 modified, and we assume that the shift input is just 0.

R2  sl R1 left shift
• Don’t confuse this register transfer language with assembly language, R2  sr R1 right shift
which we’ll discuss later.

9 10

Block symbols for registers Register file

• Modern processors have a
Load number of registers grouped D
together in a register file. n

Data input
n
• Much like words stored in a
RAM, individual registers are D data
n R0 WR Write
identified by an address. k
•
Data output DA D address
Here is a block symbol for a
k Register File
2 x n register file.
• We’ll use this block diagram to represent an n-bit register. – There are 2k registers, so k k
•
AA A address B address BA
There is a data input and a load input. register addresses are k
bits long.
– When Load = 1, the data input is stored into the register.
A data B data

– Each register holds an n-

– When Load = 0, the register will keep its current value. bit word, so the data
n n

• The register’s contents are always available on the output lines, inputs and outputs are n A B
regardless of the Load input. bits wide.
• The clock signal is not shown because it would make the diagram messy.
• Remember that the input and output lines are actually n bits wide!

11 12
 Accessing the register file What’s inside the register file
• You can read two registers at • Here’s a 4 x n register file. (We’ll assume a 4 x n register file for all
once by supplying the AA and our examples.)
D
BA inputs. The data appears n
on the A and B outputs. n

• You can write to a register by

D data
using the DA and D inputs, WR Write
and setting WR = 1. k
DA D address
• These are registers so there
Register File
must be a clock signal, even
though we usually don’t show k k
AA A address B address BA
it in diagrams.
– We can read from the A data B data

register file at any time. n n

– Data is written only on
the positive edge of the A B
clock.

n n

13 14

Explaining the register file The all-important ALU

• The 2-to-4 decoder selects one of the four registers for writing. If • The main job of a central processing unit is to “process,” or to perform
WR = 1, the decoder will be enabled and one of the Load signals will computations....remember the ALU from way back when?
be active. • We’ll use the following general block symbol for the ALU.
• The n-bit 4-to-1 muxes select the two register file outputs A and B, – A and B are two n-bit numeric inputs.
based on the inputs AA and BA. – FS is an m-bit function select code, which picks one of 2m functions.
– The n-bit result is called F.
• We need to be able to read two registers at once because most – Several status bits provide more
arithmetic operations require two operands. information about the output F: n n

• V = 1 in case of signed overflow.

• C is the carry out.
A B
m
FS
• N = 1 if the result is negative.
• Z = 1 if the result is 0.
ALU
V
C
N
Z
F

15 16
 ALU functions Our first datapath
• For concrete examples, we’ll use the • Here is the most basic datapath.
ALU as it’s presented in the textbook. FS Operation
– The ALU’s two data inputs come D data
• The table of operations on the right is 00000 F=A from the register file. WR Write

taken from the book. 00001 F=A+1

– The ALU computes a result, which DA 2 D address

• The function select code FS is 5 bits 00010 F=A+B

is saved back to the registers. Register File
00011 F=A+B+1
long, but there are only 15 different
00100 F = A + B’
• WR, DA, AA, BA and FS are control
functions here. signals. Their values determine the AA 2 A address B address 2 BA
F = A + B’ + 1
• We use an alternative notation for
00101
00110 F=A–1
exact actions taken by the datapath— A data B data
AND and OR to avoid confusion with which registers are used and for what n n
00111 F=A
arithmetic operations. operation.
01000 F = A  B (AND)
• Remember that many of the signals A B
01010 F = A  B (OR) here are actually multi-bit values. FS 5 FS
01100 F=AB
ALU
01110 F = A’ V
C
10000 F=B N
Z
n
10100 F = sr B (shift right) F
11000 F = sl B (shift left)

17 18

An example computation Two questions

• Let’s look at the proper control signals • Four registers isn’t a lot. What if we
for the operation below: D data need more storage? D data

R0  R1 + R3
WR
1
Write • Who exactly decides which registers WR Write

DA D address are read and written and which ALU DA D address

• Set AA = 01 and BA = 11. This causes 00
Register File function is executed? Register File
the contents of R1 to appear at A
data, and the contents of R3 to AA A address B address BA AA A address B address BA
appear at B data. 01 11

• Set the ALU’s function select input A data B data A data B data

FS = 00010 (A + B).
• Set DA = 00 and WR = 1. On the next A B A B
positive clock edge, the ALU result FS FS FS FS
00010
(R1 + R3) will be stored in R0.
ALU ALU
V V
C C
N N
Z Z
F F

19 20
 We can access RAM also Reading from RAM
• Here’s a way to connect RAM n • To read from RAM, A data must n
into our existing datapath. supply the address.
• To write to RAM, we must give WR Write
D data • Set MW = 0 for reading. WR Write
D data

an address and a data value. DA D address • The incoming data will be sent DA D address
• These will come from the Register File to the register file for storage. Register File

registers. We connect A data AA A address B address BA • This means that the register AA A address B address BA
to the memory’s ADRS input, A data B data file’s D data input could come A data B data
and B data to the memory’s
RAM RAM
n
ADRS from either the ALU output or n
ADRS
n n
DATA input. DATA OUT the RAM. DATA OUT

•
+5V CS +5V CS
Set MW = 1 to write to the
FS FS
A B MW
1
WR
• A mux MD selects the source FS FS
A B MW
0
WR

RAM. (It’s called MW to V for the register file. V

ALU ALU
distinguish it from the WR – When MD = 0, the ALU
C C
N N
write signal on the register Z
output can be stored in the
Z
F F
file.) n register file. n

D0
Q D1
n – When MD = 1, the RAM D0
Q D1
n
S MD output is sent to the S MD
register file instead.

21 22

Notes about this setup Memory transfer notation

• We now have a way to copy n • In our transfer language, the contents at random access memory
data between our register file address X are denoted M[X]. For example:
and the RAM. D data – The first word in RAM is M[0].
•
WR Write
Notice that there’s no way for DA D address – If register R1 contains an address, then M[R1] are the contents of
the ALU to directly access the Register File that address.
memory—RAM contents must AA A address B address BA • The M[ ] notation is like a pointer dereference operation in C or C++.
go through the register file
A data B data
first. RAM
n
• n ADRS
Here the size of the memory is DATA OUT
+5V CS
limited by the size of the A B MW WR
FS FS
registers; with n-bit registers,
n V
we can only use a 2 x n RAM. ALU
C

•
N
For simplicity we’ll assume the Z
F
RAM is at least as fast as the n
CPU clock. (This is definitely D0
n
not the case in real processors Q D1
S MD
these days.)

23 24
 Example sequence of operations R3  M[R0]
• Here is a simple series of register transfer instructions: • AA should be set to 00, to read n
register R0.
R3  M[R0] • The value in R0 will be sent to 1 D data
R3  R3 + 1 the RAM address input, so
WR Write
DA D address
M[R0]  R3 M[R0] appears as the RAM 11 Register File
output OUT.
• This just increments the contents at address R0 in RAM.
• MD must be 1, so the RAM
AA
00
A address B address BA

– Again, our ALU only operates on registers, so the RAM contents output goes to the register file.
A data
n
B data
RAM
ADRS
must first be loaded into a register, and then saved back to RAM.
•
n
To store something into R3, DATA OUT
– R0 is the first register in our register file. We’ll assume it contains we’ll need to set DA = 11 and A B
+5V
MW
CS
WR
FS FS 0
a valid memory address. WR = 1.
•
V
•
ALU
How would these instructions execute in our datapath? MW should be 0, so nothing is C
N
Z
accidentally changed in RAM. F
• Here, we did not use the ALU n
(FS) or the second register file D0
n
Q D1
output (BA). S MD
1

25 26

R3  R3 + 1 M[R0]  R3
• AA = 11, so R3 is read from the n • Finally, we want to store the n
register file and sent to the contents of R3 into RAM
ALU’s A input. 1 D data address R0. 0 D data

• •
WR Write WR Write
FS needs to be 00001 for the DA D address Remember the RAM address DA D address
operation A + 1. Then, R3 + 1 11 Register File comes from “A data,” and the Register File
appears as the ALU output F. AA A address B address BA
contents come from “B data.” AA A address B address BA
• If MD is set to 0, this output 11
A data B data
• So we have to set AA = 00 and 00
A data B data
11
RAM RAM
will go back to the register file. n
ADRS
BA = 11. This sends R0 to n
ADRS
•
n n
To write to R3, we need to DATA OUT ADRS, and R3 to DATA. DATA OUT

•
+5V CS +5V CS
make DA = 11 and WR = 1. 00001 A B MW WR MW must be 1 to write to A B MW WR
FS FS 0 FS FS 1
• Again, MW should be 0 so the V memory. V
•
ALU ALU
RAM isn’t inadvertently C
N No register updates are C
N
Z Z
changed. F needed, so WR should be 0, and F
• We didn’t use BA. n MD and DA are unused. n

D0
n
• We also didn’t use the ALU, so D0
n
Q D1 Q D1
S MD FS was ignored. S MD
0

27 28
 Constant in Control units
• One last refinement is the • From these examples, you can see that different actions are
addition of a Constant input. WR Write
D data performed when we provide different inputs for the datapath
• The modified datapath is DA D address control signals.
shown on the right, with one Register File • The second question we had was “Who exactly decides which
extra control signal MB. AA A address B address BA registers are read and written and which ALU function is
• We’ll see how this is used A data B data
executed?”
later. Intuitively, it provides Constant
– In real computers, the datapath actions are determined by the
an easy way to initialize a MB program that’s loaded and running.
register or memory location S D1 D0 – A control unit is responsible for generating the correct control
with some arbitrary number. Q RAM
signals for a datapath, based on the program code.
ADRS

+5V
DATA OUT
CS
• We’ll talk about programs and control units later.
A B MW WR
FS FS
V
ALU
C
N
Z
F

D0
Q D1
S MD

29 30

Summary HW
• The datapath is the part of a processor where computation is done. 1. Design a 4 bit arithmetic circuit, with two selection variables S1
– The basic components are an ALU, a register file and some RAM. and S0, that generates the arithmetic operations below. Draw
– The ALU does all of the computations, while the register file and the logic diagram for a single bit stage. (Q 10-4)
RAM provide storage for the ALU’s operands and results. 2. A computer has a 32 bit instruction word broken into fields as
• Various control signals in the datapath govern its behavior. follows: opcode, 6 bits; two register fields, 6 bits each; and one
• Next, we’ll see how programmers can give commands to the processor, immediate operand/register field, 14 bits.
and how those commands are translated in control signals for the • (a) What is the maximum number of operations that can be
datapath. specified?
• (b) How many registers can be addressed?
• (c) What is the range of unsigned immediate operands that can
be provided? (Q 10-13) S1S0 Cin = 0 Cin = 1

00 F = A + B (add) F=A+B+1

01 F = A (transfer) F=A+1
(increment)
10 F = B’ F = B’ + 1
(complement) (negate)
11 F = A + B’ F = A + B’ + 1
31 32 (subtract)
 Control units Datapath review
• Set WR = 1 to write one of WR D

• We introduced the basic structure of a control unit, and translated the registers. DA Register file

assembly instructions into a binary representation. • DA is the register to save to. AA A B BA

• The last piece of the processor is a control unit to convert these binary • AA and BA select the source constant
instructions into datapath signals. registers. 1 0
MB
• At the end we’ll have a complete example processor! • MB chooses a register or a Mux B

constant operand.
• FS selects an ALU operation.
• MW = 1 to write to memory. FS A B ADRS DATA

• MD selects between the ALU

V
C ALU MW Data RAM
N
result and the RAM output. Z G OUT

• V, C, N and Z are status bits.

0 1
MD
Mux D

33 34

Block diagram of a processor Where does the program go?

Program • We’ll use a Harvard architecture, which includes two memory units.
– An instruction memory holds the program.
Control signals – A separate data memory is used for computations.
Control Datapath – The advantage is that we can read an instruction and load or store
Unit Status signals data in the same clock cycle.
• For simplicity, our diagrams do not show any WR or DATA inputs to the
• The control unit connects programs with the datapath. instruction memory.
– It converts program instructions into control words for the
ADRS
datapath, including signals WR, DA, AA, BA, MB, FS, MW, MD. ADRS DATA
Instruction
– It executes program instructions in the correct sequence. RAM MW Data RAM

– It generates the “constant” input for the datapath. OUT OUT

• The datapath also sends information back to the control unit. For
instance, the ALU status bits V, C, N, Z can be inspected by branch • Caches in modern CPUs often feature a Harvard architecture like this.
instructions to alter a program’s control flow. • However, there is usually a single main memory that holds both program
instructions and data, in a Von Neumann architecture.

35 36
 Program counter Instruction decoder
• A program counter or PC addresses the instruction memory, to keep • The instruction decoder is a combinational Data
track of the instruction currently being executed. circuit that takes a machine language
• On each clock cycle, the counter does one of two things. instruction and produces the matching Load PC

– If Load = 0, the PC increments, so the next instruction in memory control signals for the datapath.
will be executed. • These signals tell the datapath which ADRS

– If Load = 1, the PC is updated with Data, which represents some registers or memory locations to access, Instruction
RAM
address specified in a jump or branch instruction. and what ALU operations to perform.
OUT

Data
Instruction Decoder

Load PC

DA AA BA MB FS MD WR MW
ADRS
Instruction
RAM (to the datapath)
OUT

37 38

Jumps and branches That’s it!

• Finally, the branch control unit • This is the basic control unit. On
decides what the PC’s next value V
C Branch each clock cycle: V
C Branch
PC PC
should be. N
Z
Control
1. An instruction is read from N
Z
Control

– For jumps, the PC should be the instruction memory.

ADRS ADRS
loaded with the target Instruction 2. The instruction decoder Instruction
address specified in the RAM generates the matching RAM
instruction. OUT datapath control word. OUT

– For branch instructions, the 3. Datapath registers are read

PC should be loaded with the and sent to the ALU or the
target address only if the Instruction Decoder
data memory.
Instruction Decoder

corresponding status bit is 4. ALU or RAM outputs are

true. written back to the register
– For all other instructions, the
DA AA BA MB FS MD WR MW DA AA BA MB FS MD WR MW
file.
PC should just increment. 5. The PC is incremented, or
reloaded for branches and
jumps.

39 40
 The whole processor Instruction format
Control Unit Datapath • We have three different instruction formats, each 16 bits long with a
seven-bit opcode and nine bits for source registers or constants.

V
WR D • The first three bits of the opcode determine the instruction category,
DA Register file
C Branch
PC while the other four bits indicate the exact instruction.
– For ALU/shift instructions, the four bits choose an ALU operation.
N Control AA A B BA
Z

ADRS
constant – For branches, the bits select one of eight branch conditions.
Instruction
RAM
1 0
Mux B
MB – We only support one load, one store, and one jump instruction.
OUT
15 9 8 6 5 3 2 0
Register B (SB),
Destination (DR) or
FS A B ADRS DATA Opcode Register A (SA) Operand (OP), or
Instruction Decoder Address 5-3 (AD)
V ALU MW Data RAM Address 2-0 (AD)
C
N
Z G OUT
DA AA BA MB FS MD WR MW

0 1
MD
Mux D

41 42

Instruction Formats Register format

15 9 8 6 5 3 2 0
15 9 8 6 5 3 2 0 Destination Source Source
Destination Source reg- Source reg- Opcode Register Register A Register B
Opcode register (DR) ister A (SA) ister B (SB) (DR) (SA) (SB)
(a) Register
15 9 8 6 5 3 2 0
• An example register-format instruction:
Destination Source reg- ADD R1, R2, R3
Opcode register (DR) ister A (SA) Operand (OP)

(b) Immediate • Our binary representation for these instructions will include:
15 9 8 6 5 3 2 0 – A 7-bit opcode field, specifying the operation (e.g., ADD).
Opcode
Address (AD)
(Left)
Source reg-
ister A (SA)
Address (AD)
(Right)
– A 3-bit destination register, DR.
– Two 3-bit source registers, SA and SB.
(c) Jump and Branch

• The three formats are: Register, Immediate, and Jump and Branch
• All formats contain an Opcode field in bits 9 through 15.
• The Opcode specifies the operation to be performed

43 44
 Immediate format Jump and branch format
15 9 8 6 5 3 2 0 15 9 8 6 5 3 2 0
Destination Source Address Source Address
Operand
Opcode Register Register A Opcode Bits 5-3 Register A Bits 2-0
(OP)
(DR) (SA) (AD) (SA) (AD)

• An example immediate-format instruction: • Two example jump and branch instructions:

ADD R1, R2, #3 BZ R3, -24
JMP 18
• Immediate-format instructions will consist of:
– A 7-bit instruction opcode. • Jump and branch format instructions include:
– A 3-bit destination register, DR. – A 7-bit instruction opcode.
– A 3-bit source register, SA. – A 3-bit source register SA for branch conditions.
– A 3-bit constant operand, OP. – A 6-bit address field, AD, for storing jump or branch offsets.
• Our branch instructions support only one source register. Other types
of branches can be simulated from these basic ones.

45 46

Assembly  machine language Table 10-8

• we defined a machine language, or a binary representation of the
assembly instructions that our processor supports.
• Our CPU includes three types of instructions, which have different Instruction Specifications for the SimpleComputer - Part 1
operands and will need different representations. St atus
– Register format instructions require two source registers. Instr uction Opcode Mnemonic Format Description Bits

– Immediate format instructions have one source register and one Move A  R[SA ]
0000000 MOVA RD ,RA R [DR] N, Z
constant operand.  R [SA]
Increment 0000001 INC R D,RA R[DR] +1 N, Z
– Jump and branch format instructions need one source register and Add 0000010 ADD R D,RA,RB R [DR]  R[SA ] + R[ SB] N, Z
one constant address. Subtract 0000101 SUB R D,RA,RB R [DR]  R[SA ] - R [SB] N, Z
• Even though there are three different instruction formats, it is best to D ecrement 0000110 DEC R D,RA R[DR]  R[SA ] -1 N, Z
make their binary representations as similar as possible. AND 0001000 AND R D,RA,RB R [DR]  R[SA ]  R[SB ] N, Z
– This will make the control unit hardware simpler. OR 0001001 OR RD,RA,RB R[DR]  R[SA]  R[SB] N, Z
RD,RA,RB R[DR]  R[SA]  R[SB]
– For simplicity, all of our instructions are 16 bits long.
Exclusive OR 0001010 XOR N, Z
NO T 0001011 NO T R D,RA R[DR]  R[SA ] N, Z

47 48
 Summary
• We saw an outline of the control unit hardware.
– The program counter points into a special instruction memory, which
contains a machine language program.
– An instruction decoder looks at each instruction and generates the
correct control signals for the datapath and a branching unit.
– The branch control unit handles instruction sequencing.
• The control unit implementation depends on both the instruction set
architecture and the datapath.
– Careful selection of opcodes and instruction formats can make the
control unit simpler.
• We now have a whole processor! This is the culmination of everything
we did this semester, starting from primitive gates.

49