A Generic Datapath

Instead of having each individual register perform its microoperations directly, computer systems
often employ a number of storage registers in conjunction with a shared operation unit called an
arithmetic/logic unit, abbreviated ALU. To perform a microoperation, the contents of specified source
registers are applied to the inputs of the shared ALU. The ALU performs an operation, and the result
of this operation is transferred to a destination register. With the ALU as a combinational circuit, the
entire register transfer operation from the source registers, through the ALU, and into the destination
register is performed during one clock cycle. The shift operations are often performed in a separate
unit, but sometimes these operations are also implemented within the ALU.

The combination of a set of registers with a shared ALU and interconnecting paths is the datapath for
the system. The design of a particular ALU, including the arithmetic and logic circuits, is undertaken
to show the process involved in implementing a complex combinational circuit. We also design a
shifter and combine the two, along with the necessary registers, decoders, multiplexers, buses, and
control signals, to constitute a complete datapath.

The datapath and the control unit are the two parts of the processor, or CPU, of a computer. In
addition to the registers, the datapath contains the digital logic that implements the various
microoperations. This digital logic consists of buses, multiplexers, decoders, and processing circuits.
When a large number of registers is included in a datapath, the registers are most conveniently
connected through one or more buses. Registers in a datapath interact by the direct transfer of data,
as well as in the performance of the various types of microoperations. A simple bus-based datapath
with four registers, an ALU, and a shifter is shown below.
Each register is connected to two multiplexers to form ALU and shifter input buses A and B. The
select inputs on each multiplexer select one register for the corresponding bus. For Bus B, there is an
additional multiplexer, MUX B, so that constants can be brought into the datapath from outside using
Constant in. Bus B also connects to Data out, to send data outside the datapath to other components
of the system, such as memory or input–output. Likewise, Bus A connects to Address out, to send
address information outside of the datapath for memory or input–output.

Arithmetic and logic microoperations are performed on the operands on the A and B buses by the
ALU. The G select inputs select the microoperation to be performed by the ALU. The shift
microoperations are performed on data on Bus B by the shifter. The H select input either passes the
operand on Bus B directly through to the shifter output or selects a shift microoperation. MUX F
selects the output of the ALU or the output of the shifter. MUX D selects the output of MUX F or
external data on input Data in to be applied to Bus D. The latter is connected to the inputs of all the
registers. The destination select inputs determine which register is loaded with the data on Bus D.
Since the select inputs are decoded, only one register Load signal is active for any transfer of data
into a register from Bus D. A Load enable signal that can force all register Load signals to 0 using
AND gates is present for transfers that are not to change the contents of any of the four registers.

It is useful to have certain information, based on the results of an ALU operation, available for use by
the control unit of the CPU to make decisions. Four status bits are shown with the ALU in Figure 8-1.
The status bits, carry C and overflow V, were explained in conjunction with Figure 3-46. The zero
status bit Z is 1 if the output of the ALU contains all zeros and is 0 otherwise. Thus, if the result of an
operation is zero, and if the result is nonzero. The sign status bit N (for negative) is the leftmost bit of
the ALU output, which is the sign bit for the result in signed-number representations. Status values
from the shifter can also be incorporated into the status bits if desired.

Performing a Microoperation
The control unit for the datapath directs the information flow through the buses, the ALU, the shifter,
and the registers by applying signals to the select inputs. For example, to perform the microoperation

R0 ← R1 + R2

the control unit must provide binary selection values to the following sets of control inputs:

• Apply 01 to A select to place contents of R1 onto Bus A

• Apply 10 to B select to place contents of R2 onto B data
• Apply 0 to MB select to place B data on Bus B
• Apply 0010 to G select to perform addition G = Bus A + Bus B
• Apply 0 to MF select and 0 to MD select to place the value of G onto Bus D
• Apply 00 to Destination select to enable the Load input to R0
• Apply 1 to Load Enable to force the Load input to R0 to 1 so that R0 is loaded on the
clock pulse

The sets of values must be generated and must become available on the corresponding control lines
early in the clock cycle. The binary data from the two source registers must propagate through the
multiplexers and the ALU and on into the inputs of the destination register, all during the remainder
of the same clock cycle. Then, when the next positive clock edge arrives, the binary data on Bus D is
loaded into the destination register. To achieve fast operation, the ALU and shifter are constructed
with combinational logic having a limited number of levels.

Examples of Other Microoperations

Shifters
The shifter shifts the value on Bus B, placing the result on an input of MUX F. The basic
shifter performs one of two main types of transformations on the data: right shift and
left shift.
A seemingly obvious choice for a shifter would be a bidirectional shift register with
parallel load. Data from Bus B can be transferred to the register in parallel and then
shifted to the right, the left, or not at all. A clock pulse loads the output of Bus B into the
shift register, and a second clock pulse performs the shift. Finally, a third clock pulse
transfers the data from the shift register to the selected destination register.
Alternatively, the transfer from a source register to a destination register can be done
using only one clock pulse if the shifter is implemented as a combinational circuit.
Because of the faster operation that results from the use of one clock pulse instead of
three, this is the preferred method. In a combinational shifter, the signals propagate
through the gates without the need for a clock pulse. Hence, the only clock needed for a
shift in the datapath is for loading the data from Bus H into the selected destination
register.

Basic Barrel Shifter

A combinational shifter can be constructed with multiplexers as shown below.

The selection variable S is applied to all four multiplexers to select the type of operation within the
shifter. S = 00 causes B to be passed through the shifter unchanged. S= 01 causes a right-shift
operation and causes a left-shift operation. The right shift fills the position on the left with the value
on serial input IR. The left shift fills the position on the right with the value on serial input IL. Serial
outputs are available from serial output R and serial output L for right and left shifts, respectively.

The diagram shows only four stages of the shifter, which will have n stages in a system with n-bit
operands. Additional selection variables may be employed to specify what goes into IR and IL during a
single bit-position shift. Note that to shift an operand by m > 1 bit positions, this shifter must perform
a series of m 1-bit position shifts, taking m clock cycles.
4-bit Barrel Shifter
In datapath applications, often the data must be shifted more than one bit position in a single clock
cycle. A barrel shifter is one form of combinational circuit that shifts or rotates the input data bits by
the number of bit positions specified by a binary value on a set of selection lines. The shift we
consider here is a rotation to the left, which means that the binary data is shifted to the left, with the
bits coming from the most significant part of the register rotated back into the least significant part of
the register.

A 4-bit version of this kind of barrel shifter is shown above. It consists of four multiplexers with
common select lines S1 and S0. The selection variables determine the number of positions that the
input data will be shifted to the left by rotation. When S1S0 = 00, no shift occurs, and the input data
has a direct path to the outputs. When S1S0 = 01, the input data is rotated one position, with D0 going
to Y1, D1 going to Y2, D2 going to Y3, and D3 going to Y0. When S1S0 = 10, the input is rotated two
positions, and when S1S0 = 11, the rotation is by three bit positions.

Function Table for 4-Bit Barrel Shifter

For each binary value of the selection variables, the table lists the inputs that go to the corresponding
output. Thus, to rotate three positions, S1S0 must be equal to 11, causing D0 to go to Y3, D1 to go to Y0,
D2 to go to Y1, and D3 to go to Y2. Note that, by using this left-rotation barrel shifter, one can generate
all desired right rotations as well. For example, a left rotation by three positions is the same as a right
rotation by one position in this 4-bit barrel shifter. In general, in a 2n-bit barrel shifter, i positions of
left rotation are the same as 2n - 1 bits of right rotation.

A barrel shifter with 2n input and output lines requires 2n multiplexers, each having 2n data inputs and
n selection inputs. The number of positions for the data to be rotated is specified by the selection
variables and can be from 0 to 2n − 1 positions.
The ALU
The ALU is a combinational circuit that performs a set of basic arithmetic and logic microoperations.
It has a number of selection lines used to determine the operation to be performed. The selection
lines are decoded within the ALU, so that k selection lines can specify up to 2k distinct operations.

This is the symbol for a typical n-bit ALU. The n data inputs from A are combined with the n data
inputs from B to generate the result of an operation at the G outputs. The mode-select input
S2 distinguishes between arithmetic and logic operations. The two Operation select inputs S1 and
S0 and the Carry input Cin specify the eight arithmetic operations with S2 at 0. Operand select input
S0 and Cin specify the four logic operations with S2 at 1.

We perform the design of this ALU in three stages. First, we design the arithmetic section. Then we
design the logic section, and finally, we combine the two sections to form the ALU.

Arithmetic Circuit
The basic component of an arithmetic circuit is a parallel adder, which is constructed with a number of
full-adder circuits connected in cascade, as shown below.
By controlling the data inputs to the parallel adder, it is possible to obtain different types of arithmetic
operations.

The block diagram above demonstrates a configuration in which one set of inputs to the parallel adder is
controlled by the select lines S1 and S0. There are n bits in the arithmetic circuit, with two inputs A and B
and output G. The n inputs from B go through the B input logic to the Y inputs of the parallel adder. The
input carry Cin goes in the carry input of the full adder in the least-significant-bit position. The output
carry Cout is from the full adder in the most-significant-bit position. The output of the parallel adder is
calculated from the arithmetic sum as

G = X + Y + Cin

where X is the n-bit binary number from the inputs and Y is the n-bit binary number from the B input
logic. Cin is the input carry, which equals 0 or 1. Note that the symbol + in the equation denotes
arithmetic addition.

The function table shows the arithmetic operations that are obtainable by controlling the value of Y with
the two selection inputs S1 and S0. If the inputs from B are ignored and we insert all 0s at the Y inputs,
the output sum becomes G = A + 0 + Cin. This gives G = A when Cin = 0 and G = A + 1 when Cin = 1. In the
first case, we have a direct transfer from input A to output G. In the second case, the value of A is
incremented by 1. For a straight arithmetic addition, it is necessary to apply the B inputs to the Y inputs
of the parallel adder. This gives G = A + B when Cin = 0. Arithmetic subtraction is achieved by applying
the complement of inputs B to the Y inputs of the parallel adder, to obtain G = A + B′ + 1 when Cin =
1. This gives A plus the 2s complement of B, which is equivalent to 2s complement subtraction. All 1s is
the 2s complement representation for -1. Thus, applying all 1s to the Y inputs with Cin = 0 produces the
decrement operation .
The B input logic can be implemented with n multiplexers. The data inputs to each multiplexer in
stage i for i = 0, 1, . . . , n-1 are 0, Bi, Bi′, and 1, corresponding to selection values S1S0: 00, 01, 10, and 11,
respectively. Thus, the arithmetic circuit can be constructed with n full adders and n 4-to-1 multiplexers.

The number of gates in the B input logic can be reduced if, instead of using 4-to-1 multiplexers, we go
through the logic design of one stage (one bit) of the B input logic.

The truth table for one typical stage i of the logic is given above. The inputs are S1, S0, and Bi, and the
output is Yi.

We can plot the minterms in a Karnaugh map and obtain a simplified Boolean expression for Yi.

Yi = BiS0 + Bi′S1

where S1 and S0 are common to all n stages. Each stage i is associated with input Bi and output Yi for i
= 0, 1, . . . , n-1. This logic corresponds to a 2-to-1 multiplexer with Bi on the select input and S1 and S0 on
the data inputs.
The logic diagram of an arithmetic circuit for n = 4 is shown above. The four full-adder (FA) circuits
constitute the parallel adder. The B input logic requires only four gates per stage. The carry into the
first stage is the input carry Cin. All other carries are connected internally from one stage to the next.

The selection variables are S1, S0, and Cin. Variables S1 and S0 control all Y inputs of the full adders
according to the Boolean function derived for Yi. Whenever Cin is 1, A + Y has 1 added.

Logic Circuit
The logic microoperations manipulate the bits of the operands by treating each bit in a register as a
binary variable, giving bitwise operations. There are four commonly used logic operations—AND, OR,
XOR (exclusive-OR), and NOT—from which others can be conveniently derived.

Figure (a) shows one stage of the logic circuit. It consists of four gates and a 4-to-1 multiplexer,
although simplification could yield less complex logic. Each of the four logic operations is generated
through a gate that performs the required logic. The outputs of the gates are applied to the inputs of
the multiplexer with two selection variables S1 and S0. These choose one of the data inputs of the
multiplexer and direct its value to the output. The diagram shows a typical stage with subscript i.

The function table in Figure (b) lists the logic operations obtained for each combination of the
selection values.

For the logic circuit with n bits, the diagram must be repeated n times, for . The selection variables are
applied to all stages. The diagram below is an example of how this mux based logic circuit can be used
in a 4-bit ALU:
The Complete ALU
Finally, we combine the arithmetic circuit and the logic circuit into the complete ALU. One stage of
the combined circuits is shown below. It must be repeated n times for an n-bit ALU.

The arithmetic and logic circuits are purely combinational. Hence, they are always processing the
inputs and providing outputs. The 2-to-1 Mux is used to select whether an arithmetic or logic
function is being used. The mode select control S2 controls which circuit provides the output.

The output carry of this stage must be connected to the input carry of the next stage.

This is the complete function table for our ALU. This architecture provides for 8 arithmetic
operations and 4 logic operations. S1 has no effect on the logic microoperations and is marked don’t
care.

It is interesting to note that G ← A appears twice in the table. This is a harmless by-product of using
Cin as one of the control variables while implementing both increment and decrement instructions.

This ALU has a lot of logic levels and can be simplified or it can be made faster with look-ahead logic.
But that is a topic for another course…