Memory Allocation III CSE 351 Autumn 2016
Digital Logic – Combinational
CMPT 295
L26: Sequential Logic
Synchronous Digital Systems (SDS)
Synchronous:
All operations coordinated by a central clock
“Heartbeat” of the system! (processor frequency)
Digital:
Represent all values with two discrete values
Electrical signals are treated as 1’s and 0’s
1 and 0 are complements of each other
High/Low voltage for True/False, 1/0
Hardware of a processor, such as a RISC-V processor, is an example of a Synchronous Digital System
2
CMPT 295
L26: Sequential Logic
Type of Circuits
Digital Systems consist of two basic types of circuits:
Combinational Logic (CL)
Output is a function of the inputs only, not the history of its execution
e.g. circuits to add A, B (ALUs)
Sequential Logic (SL)
Circuits that “remember” or store information
a.k.a. “State Elements”
e.g. memory and registers (Registers)
3
CMPT 295
L26: Sequential Logic
Logic Gates (1/2)
Special names and symbols:
NOT
AND
OR
a b c
0 0 0
0 1 0
1 0 0
1 1 1
a b c
0 0 0
0 1 1
1 0 1
1 1 1
a c
0 1
1 0
Circle means NOT!
4
CMPT 295
L26: Sequential Logic
Logic Gates (2/2)
Inverted versions are easier to implement in CMOS
NAND
NOR
XOR
a b c
0 0 1
0 1 0
1 0 0
1 1 0
a b c
0 0 0
0 1 1
1 0 1
1 1 0
a b c
0 0 1
0 1 1
1 0 1
1 1 0
5
CMPT 295
L26: Sequential Logic
6
A
B
C
D
Combining Multiple Logic Gates
(NOT(A AND B)) AND (A OR (NOT B AND C))
CMPT 295
L26: Sequential Logic
6
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
7
CMPT 295
L26: Sequential Logic
General Form
F
Y
A
B
C
If N inputs, how many distinct functions F do we have?
Function maps each row to 0 or 1, so possible functions
8
A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Y
F(0,0,0)
F(0,0,1)
F(0,1,0)
F(0,1,1)
F(1,0,0)
F(1,0,1)
F(1,1,0)
F(1,1,1)
0
1
0
0
0
1
1
0
2N
CMPT 295
L26: Sequential Logic
Circle the output, use variables/animations, talk about the output as a bit combination (integer?)
Maybe 3 inputs?
More Complicated Truth Tables
3-Input Majority
a b c y
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
2-bit Adder
A B C
a1 a0 b1 b0 c2 c1 c0
.
.
.
+
c1
a1
a0
b1
b0
c2
c0
How many
rows?
9
CMPT 295
L26: Sequential Logic
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
10
CMPT 295
L26: Sequential Logic
Boolean Algebra
Represent inputs and outputs as variables
Each variable can only take on the value 0 or 1
Overbar or ¬ is NOT: “logical complement”
e.g. if A is 0, A is 1. If A is 1, then ¬A is 0
Plus (+) is 2-input OR: “logical sum”
Product (·) is 2-input AND: “logical product”
All other gates and logical expressions can be built from combinations of these
¬AB + A¬B == (NOT(A AND B)) OR (A AND NOT B)
For slides, will use ¬A
11
CMPT 295
L26: Sequential Logic
Laws of Boolean Algebra
These laws allow us to perform simplification:
12
CMPT 295
L26: Sequential Logic
Demorgan’s law example
12
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary
Bonus Slides
Logisim Intro
13
CMPT 295
L26: Sequential Logic
Should be at no later than 10
Data Multiplexor
Multiplexor (“MUX”) is a selector
Place one of multiple inputs onto output (N-to-1)
Shown below is an n-bit 2-to-1 MUX
Input S selects between two inputs of n bits each
14
This input is passed to output if selector bits match shown value
Represents that this wire has n bits
CMPT 295
L26: Sequential Logic
Implementing a 1-bit 2-to-1 MUX
Schematic:
Truth Table:
Boolean Algebra:
Circuit Diagram:
15
s a b c
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
CMPT 295
L26: Sequential Logic
1-bit 4-to-1 MUX (1/2)
Schematic:
Truth Table: How many rows?
Boolean Expression:
e = ¬s1¬s0a + ¬s1s0b + s1¬s0c + s1s0d
16
26
CMPT 295
L26: Sequential Logic
1-bit 4-to-1 MUX (2/2)
Can we leverage what we’ve previously built?
Alternative hierarchical approach:
17
CMPT 295
L26: Sequential Logic
Circuit Simplification
(Transistors and/or Gates)
1)
2)
3)
4)
18
CMPT 295
L26: Sequential Logic
Circuit Simplification Example (2/4)
Simplify the following circuit:
Start from left, propagate signals to the right
A
B
C
D
A
C
¬B
B
A
AB
¬BC
¬(AB)
A+¬BC
19
Arrive at D = ¬(AB)(A + ¬BC)
CMPT 295
L26: Sequential Logic
Circuit Simplification Example (3/4)
Simplify Expression:
D = ¬(AB)(A + ¬BC)
= (¬A + ¬B)(A + ¬BC) DeMorgan’s
= ¬AA + ¬A¬BC + ¬BA + ¬B¬BC Distribution
= 0 + ¬A¬BC + ¬BA + ¬B¬BC Complementarity
= ¬A¬BC + ¬BA + ¬BC Idempotent Law
= (¬A + 1)¬BC + ¬BA Distribution
= ¬BC + ¬BA Law of 1’s
= ¬B(A + C) Distribution
Which of these
is “simpler”?
20
CMPT 295
L26: Sequential Logic
Circuit Simplification Example (4/4)
Draw out final circuit:
D = ¬BC + ¬BA = ¬B(A + C)
Simplified Circuit:
Reduction from 6 gates to 3!
How many gates
do we need for each?
5
3
A
B
C
D
21
CMPT 295
L26: Sequential Logic
Also only has to go through 2 “stages” worth of gates as opposed to 4 previously.
Longest path here is B → NOT → AND → D. Before one of the longest paths was B → NOT → AND → OR → AND → D.
21
Digital Logic – Sequential
CMPT 295
L26: Sequential Logic
Want: S=0;
for X1,X2,X3 over time…
S = S + Xi
An example of why we would need sequential logic
Assume:
Each X value is applied in succession, one per cycle
The sum since time 1 (cycle) is present on S
SUM
Xi
S
Accumulator Example
23
CMPT 295
L26: Sequential Logic
Second Try: How About This?
A Register is the state element that is used here to hold up the transfer
of data to the adder
24
CMPT 295
L26: Sequential Logic
Uses for State Elements
Place to store values for some amount of time:
Register files (like in RISCV)
Memory (caches and main memory)
Help control flow of information between combinational logic blocks
State elements are used to hold up the movement of information at the inputs to combinational logic blocks and allow for orderly passage
25
CMPT 295
L26: Sequential Logic
Registers
Same as registers in assembly:
small memory storage locations
26
Clock input
(inputs active only on a clock “tick”)
Data input
(can be various bit widths)
Data output
(can be various bit widths)
Reset
(sets value to zero)
Write Enable
(can it be written to)
CMPT 295
L26: Sequential Logic
26
Signals transmitted over wires continuously
Transmission is effectively instantaneous
Implies that any wire only contains one value at any given time
Signals and Waveforms: Clocks
Rising Edge
Falling Edge
Clock period
(CPU cycle time)
27
CMPT 295
L26: Sequential Logic
Review of Timing Terms
Clock: steady square wave that synchronizes system
Register: several bits of state that samples on rising edge of Clock (positive edge-triggered); also has RESET
Setup Time: when input must be stable before Clock trigger
Hold Time: when input must be stable after Clock trigger
Clock-to-Q Delay: how long it takes output to change from Clock trigger
28
CMPT 295
L26: Sequential Logic
STOP HERE
28
Model for Synchronous Systems
Combinational logic blocks separated by registers
Clock signal connects only to sequential logic elements
Feedback is optional depending on application
How do we ensure proper behavior?
How fast can we run our clock?
29
CMPT 295
L26: Sequential Logic
When can the input change?
Needs to be stable for duration of
setup time + hold time
Often unstable until at least clock-to-q time has passed
Because register output isn’t ready yet
Needs to account for all combinational logic delay too
30
CMPT 295
L26: Sequential Logic
30
Maximum Clock Frequency
31
Max Delay =
Min Period = Max Delay
Max Freq = 1/Min Period
CLK-to-Q Delay
+ CL Delay
+ Setup Time
Assumes Max Delay > Hold Time
CMPT 295
L26: Sequential Logic
Hold time is included in CLK-to-Q delay.
Make sure to shift thinking for setup time for next clock trigger (one clock cycle).
+
Reg
Reg
The Critical Path
The critical path is the longest delay between any two registers in a circuit
The clock period must be longer than this critical path, or the signal will not propagate properly to that next register
Critical Path =
CLK-to-Q Delay
+ CL Delay 1
+ CL Delay 2
+ CL Delay 3
+ Adder Delay
+ Setup Time
CMPT 295
L26: Sequential Logic
How do we go faster?
Pipelining!
Split operation into smaller parts and add a register between each one.
33
CMPT 295
L26: Sequential Logic
33
Pipelining and Clock Frequency (1/2)
Clock period limited by propagation delay of adder and shifter
Add an extra register to reduce the critical path!
34
Timing:
CMPT 295
L26: Sequential Logic
Pipelining and Clock Frequency (2/2)
35
Reduced critical path → allows higher clock freq.
Extra register → extra (shorter) cycle to produce first output
CMPT 295
L26: Sequential Logic
Notice anything weird?
Register with two inputs? (variable widths)
How is an adder or shifter implemented?
Pipelining Basics
By adding more registers, break path into shorter “stages”
Aim is to reduce critical path
Signals take an additional clock cycle to propagate through each stage
New critical path must be calculated
Affected by placement of new pipelining registers
Faster clock rate → higher throughput (outputs)
More stages → higher startup latency
Pipelining tends to improve performance
More on this (and application to CPUs) later
36
CMPT 295
L26: Sequential Logic