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 4
Digital 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
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 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?
Where Does the Control Connect, and How is The Datapath
Determined, and Controlled?
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:
– Inverteachdigit – Add1
• 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
AB Cin
Full-Adder
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
Full adder
Cout Sum
S A B Ci
ABCi ABCi ABCi ABCi
CO ABBCi ACi
Digital Logic Review – Chang Liu 14
14
AB Cin
Adder
Full adder
Cout Sum
Propagate (P ) A B
Delete AB
Digital Logic Review – Chang Liu
15
S A B Ci
ABCi ABCi ABCi ABCi
CO ABBCi ACi
Generate (G) AB
Ripple-Carry Adder
A0 B0 A1 B1 Ci,0 Co,0
(= Ci,1)
Co,1
A2 B2 A3 B3
Co,2 Co,3
FA
FA
FA
FA
S0 S1 S2 S3
• 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.
Digital Logic Review – Chang Liu 16
Multipliers
• Multiplicationsareexpensiveandslowoperations
• 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
• Multipliersareineffectcomplexadderarrays
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)
Multiplicand
Multiplier Accumulator
Multiplier bit 0
Accumulator
Shift multiplicand left and multiplier right – Multiplier bit 1
Accumulator
Shift multiplicand left and multiplier right – Multiplier bit 2
Accumulator
Shift multiplicand left and multiplier right – Multiplier bit 3
Accumulator
0111
1010 00000000 0000 00000000
0111 00001110
0000 00001110
0111 01000110
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.
occurring during the shift. • Product stored in AC.
MULTIPLICAND SHIFT DIRECTION
M7 M6 M5 M4 M3 M2 M1 M0
X3 X2 X1 X0
MULTIPLIER
SHIFTLINE
8-BIT ADDER
ADD ENABLE
AAAAAAAA 76543210
ACCUMULATOR OUTPUT ENABLE
Note: the inverters prevent add operations
Digital Logic Review – Chang Liu 20
Combinational Logic: Multiplexers • Multiplexers (MUX)
– Very important for FPGAs
• Build up multi-bit & multi-input from basic
ABC
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
• Clocked
• StorageElement
Registers
• 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
Digital Logic Review – Chang Liu
4Mx1 DRAM
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
Horizontal routing channel
switching matrix
Interconnect point
Vertical routing channel
CLB
Digital Logic Review – Chang Liu
33
CLB
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