Digital System Design 4
Digital System Design 4
Lecture 5 – Digital Logic Review
Computer Architecture
Dr Chang Liu
Course Outline
Week Lecture Topic Chapter Tutorial
1 1 Introduction
1 2 A Historical Perspective
2 3 Modern Technology and Types of Computer
2 4 Computer Perfomance 1
3 5 Digital Logic Review C
3 6 Instruction Set Architecture 1
4 7 Instruction Set Architecture 2
4 8 Processor Architecture 1
5 9 Instruction Set Architecture 3
5 10 Processor Architecture 2
Festival of Creative Learning
6 11 Processor Architecture 3
6 12 Processor Architecture 4Digital Logic Review – Chang Liu 2
Course Outline
Week Lecture Topic Chapter Tutorial
7 11 Memory and Caches 1
7 12 Memory and Caches 2
8 13 Memory and Caches 3
8 14 Parallel Architectures 1
9 15
Guest Lecture TBC
9 16
Guest Lecture TBC
10 17 Parallel Architectures 2
10 18 Parallel Architectures 3
11 19 Revision 1
11 20 Revision 2
Digital Logic Review – Chang Liu 3
Office Hours
• Wednesday 4-5 pm AGB 1.09
• Email: c.liu@ed.ac.uk
Digital Logic Review – Chang Liu 4
mailto:c.liu@ed.ac.uk
This Lecture
• A review of 2nd-3rd year digital logic and some
new blocks that you’ll need for this course.
Digital Logic Review – Chang Liu 5
Motivation: A Preview of Lecture 8
Where Does the Control Connect, and How is The Datapath
Determined, and Controlled?
Where Does the Clock Connect?
What width are each of these bus
lines?
What are the elements below this
high-level abstract diagram?
What are the elements below that?
How could you implement this
architecture in a given technology?
Digital Logic Review – Chang Liu 6
Gates
• AND Gate
• OR Gate
• NOT Gate
• Can make all logic functions from these
Digital Logic Review – Chang Liu 7
2’s Complement Notation
• The largest number that can be represented by an n-
digit number is 2n – 1.
• [-B] represented in 2’s complement by
[-B] = 2n – B
• e.g., if n = 4, B =510= 01012
[-B] = 24 – 5 = 1110 = 10112
• In 2’s complement:
– All positive numbers begin with 0
– All negative numbers begin with 1
– Zero is regarded as positive
Digital Logic Review – Chang Liu 8
2’s Complement Notation
• It would appear that a dedicated subtractor circuit is still
required to generate the 2’s complement!
• However, there is a method to obtain the 2’s complement of a
number which avoids using a subtractor:
– Invert each digit
– Add 1
• Example:
– +5: 0101
Invert each digit: 1010
Add 1: 1011 (-5 = 2’s complement of +5)
Digital Logic Review – Chang Liu 9
2’s Complement Notation
Decimal Binary 2’s complement binary
+7 111 0111
+6 110 0110
+5 101 0101
+4 100 0100
+3 011 0011
+2 010 0010
+1 001 0001
0 000 0000
-1 – 1111
-2 – 1110
-3 – 1101
-4 – 1100
-5 – 1011
-6 – 1010
-7 – 1001
-8 – 1000
Digital Logic Review – Chang Liu 10
Performing Subtraction with 2’s
Complement
• 710 – 510 = 01112 – 01012 = 01112 + 10112 = 00102
– msb = 0, therefore result is positive
– Difference = 00102 = +210
• 310 – 510 = 00112 – 01012 = 00112 + 10112 = 11102
– msb = 1, therefore result is negative
– Take 2’s complement of result : 0001 + 1 = 0010
– Difference = 00102 = -210
Digital Logic Review – Chang Liu 11
2’s Complement Notation
• 2’s complement is used almost universally.
• Same hardware can be used for addition and
subtraction.
• Need 2’s complement hardware (i.e., invert and add)
Digital Logic Review – Chang Liu 12
Combinational Logic
• Not clocked
• No state
• No reset needed
• Takes time for signals to ‘flow through’
(Propagation Delay)
• More logic in series = more delay
Digital Logic Review – Chang Liu 13
14
Full-Adder
A B
Cout
Sum
Cin Full
adder
S ABC
i
ABC
i
ABC
i
ABC
i
ABC
i
C
O
AB BC
i
AC
i
A B Ci S Co Carry status
0 0 0 0 0 delete
0 0 1 1 0 delete
0 1 0 1 0 propagate
0 1 1 0 1 propagate
1 0 0 1 0 propagate
1 0 1 0 1 propagate
1 1 0 0 1 generate
1 1 1 1 1 generate
Digital Logic Review – Chang Liu 14
Adder
Generate (G) AB
Propagate (P) AB
Delete AB
S ABC
i
ABC
i
ABC
i
ABC
i
ABC
i
C
O
AB BC
i
AC
i
A B
Cout
Sum
Cin Full
adder
Digital Logic Review – Chang Liu 15
Ripple-Carry Adder
• Cascade N full-adder (FA) stages in series for N-bit adder.
• Carry ripples from one stage to the next – hence name.
• Delay depends on the number of logic stages traversed to produce the
output, and is a function of the input.
• For some inputs there is no rippling at all.
• For other inputs the carry must ripple from the lsb to the msb.
• Propagation delay (also called critical path) is defined as the worst case
delay over all possible input patterns.
FA FA FA FA
A0 B0
S0
A1 B1
S1
A2 B2
S2
A3 B3
S3
Ci,0 Co,0
(= Ci,1)
Co,1 Co,2 Co,3
Digital Logic Review – Chang Liu 16
Multipliers
• Multiplications are expensive and slow operations
• Performance of many computational problems is
often dominated by the speed at which a
multiplication operation can be executed
• Most microprocessors and digital signal processors
have dedicated multiplication units
• Multipliers are in effect complex adder arrays
Digital Logic Review – Chang Liu 17
Binary Multiplication
• Simplest form is to use the principle of shift and add.
– The multiplicand is multiplied by (ANDed with) the
multiplier lsb and added to the accumulator register.
– The multiplicand is shifted left (multiplied by 2), then
ANDed with the 2nd lsb and the result added to the
accumulator register.
– The process continues until all multiplier bits have been
included and the accumulator register contains the result.
Digital Logic Review – Chang Liu 18
Binary Multiplication – Shift & Add
• Example: 0111 x 1010 (7×10)
0 1 1 1
1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1
0 0 0 0 1 1 1 0
0 0 0 0
0 0 0 0 1 1 1 0
0 1 1 1
0 1 0 0 0 1 1 0
Accumulator
Accumulator
Accumulator
Accumulator
Accumulator
Multiplicand
Multiplier
Multiplier bit 0
Shift multiplicand left and multiplier right – Multiplier bit 1
Shift multiplicand left and multiplier right – Multiplier bit 2
Shift multiplicand left and multiplier right – Multiplier bit 3
Digital Logic Review – Chang Liu 19
Binary Multiplication – Shift & Add
• Reset accumulator register (AC).
• Load multiplicand (M) and
multiplier (X) registers.
• AND M with X0 to give the first
partial product.
• Add to AC.
• Shift M one place left and X one
place right.
• AND M with X1 for 2nd partial
product.
• Add to previously stored result in
AC and restore to AC.
• Continue for all bits of X.
• Product stored in AC.
Note: the inverters prevent add operations
occurring during the shift.
M
7
M
6
M
5
M
4
M
3
M
2
M
1
M
0
X
3
X
2
X
1
X
0
A
7
A
6
A
5
A
4
A
3
A
2
A
1
A
0
8-BITADDER
ACCUMULATOR
SHIFTLINE
SHIFT DIRECTIONMULTIPLICAND
MULTIPLIER
ADD ENABLE
OUTPUT ENABLE
Digital Logic Review – Chang Liu 20
Combinational Logic: Multiplexers
• Multiplexers (MUX)
– Very important for FPGAs
• Build up multi-bit & multi-input from basic
A B C
Digital Logic Review – Chang Liu 21
Look Up Tables (LUT)
• Multiplexer with fixed inputs -> LUT
– Same thing as a ROM
– Select signal of MUX becomes input
– This is how logic is implemented on FPGAs
– (Logic becomes just data stored in ROM)
Digital Logic Review – Chang Liu 22
Arithmetic Logic Unit (ALU)
Digital Logic Review – Chang Liu 23
ALU
Digital Logic Review – Chang Liu 24
ALU
• Same input goes to multiple different functions
• Output MUX selects function required
• MUX select changes circuit layout (datapath control)
Digital Logic Review – Chang Liu 25
Synchronous vs Asynchronous sequential circuits
• A synchronous circuit is a circuit where all the
changes occur simultaneously at a time determined by
a clock signal. Thus a synchronous circuit has a clock
line going to each memory element (flip-flop in the
circuit).
• An asynchronous circuit is one in which the changes
occur at times determined only by the inputs and the
propagation delays in the circuit.
Digital Logic Review – Chang Liu 26
Registers
• Clocked
• Storage Element
• All digital logic is Reg/Comb/Reg sandwiches
• Amount of logic between each register determines
Maximum Clock Frequency
• Faster clock? More registers! (Pipelining)
• D-type most common (and most useful)
Digital Logic Review – Chang Liu 27
Timing
• The clock must be long enough to allow signals to be
valid for the required setup time before the next
clock edge.
Digital Logic Review – Chang Liu 28
Static RAM
• Bank of registers, with MUX at input & output
• Common for on-chip RAM
Digital Logic Review – Chang Liu 29
Dynamic RAM
• Array of tiny capacitors
• Leak, so need to be read & rewritten
• Common for large off-chip RAM
4Mx1 DRAM
Digital Logic Review – Chang Liu 30
Field Programmable Gate Arrays (FPGAs)
Digital Logic Review – Chang Liu 31
FPGAs
• ‘Soup’ of configurable logic cells (LUTs)
• Meshes of configurable interconnect
• Block RAM
• I/O Blocks
• Clock Controllers
• DSP Cores
• (Microprocessor Cores)
Digital Logic Review – Chang Liu 32
Field-Programmable Gate Arrays
RAM-based
CLB CLB
CLBCLB
switching matrix
Horizontal
routing
channel
Vertical routing channel
Interconnect point
Digital Logic Review – Chang Liu 33
Summary: Hardware is Plumbing
Software Hardware
Digital Logic Review – Chang Liu 34
Hardware/Software Divide
Digital Logic Review – Chang Liu 35
Next Lecture: Instruction Sets 1
• Instruction Sets!
•
Digital Logic Review – Chang Liu 36