Memory Allocation III CSE 351 Autumn 2016
Digital Logic – Sequential
CMPT 295
L26: Sequential Logic
Roadmap
2
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
L26: Sequential Logic
2
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary
Bonus Slides
Logisim Intro
3
CMPT 295
L26: Sequential Logic
3
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)
4
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
5
CMPT 295
L26: Sequential Logic
No!
How to control the next iteration of the ‘for’ loop?
How do we say: ‘S=0’?
Feedback
X
First Try: Does this work?
6
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
7
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
8
CMPT 295
L26: Sequential Logic
Registers
Same as registers in assembly:
small memory storage locations
9
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
9
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)
10
CMPT 295
L26: Sequential Logic
Signals and Waveforms
All signals change after clock “triggers”
Stack signals on top of each other
11
CMPT 295
L26: Sequential Logic
Dealing with Waveform Diagrams
Easiest to start with CLK on top
Solve signal by signal, from inputs to outputs
Can only draw the waveform for a signal if all of its input waveforms are drawn
When does a signal update?
A state element updates based on CLK triggers
A combinational element updates ANY time ANY of its inputs changes
12
CMPT 295
L26: Sequential Logic
Signals and Waveforms: Grouping
A group of wires when interpreted as a bit field is called a bus
X
13
Time
CMPT 295
L26: Sequential Logic
Rough
timing …
Time
Second Try: How About This?
Delay through Adder
14
CMPT 295
L26: Sequential Logic
n instances of a “Flip-Flop”
Output flips and flops between 0 and 1
Specifically this is a “D-type Flip-Flop”
D is “data input”, Q is “data output”
In reality, has 2 outputs (Q and Q), but we only care about 1
http://en.wikibooks.org/wiki/Practical_Electronics/Flip-flops
Register Internals
15
CMPT 295
L26: Sequential Logic
Can see Wikipedia page for gate internals and other types of flip-flops.
Flip-Flop Timing Behavior (1/2)
Edge-triggered D-type flip-flop
This one is “rising edge-triggered”
“On the rising edge of the clock, input d is sampled and transferred to the output. At other times, the input d is ignored and the previously sampled value is retained.”
Example waveforms:
16
CMPT 295
L26: Sequential Logic
Flip-Flop Timing Terminology (1/3)
Camera Analogy: non-blurry digital photo
Don’t move while camera shutter is opening
Don’t move while camera shutter is closing
Wait until image appears on the display
17
CMPT 295
L26: Sequential Logic
Flip-Flop Timing Terminology (2/3)
Camera Analogy: Taking a photo
Setup time: don’t move since about to take picture (open camera shutter)
Hold time: need to hold still after shutter opens until camera shutter closes
Time to data: time from open shutter until image appears on the output (viewfinder)
18
CMPT 295
L26: Sequential Logic
Flip-Flop Timing Terminology (3/3)
Now applied to hardware:
Setup Time: how long the input must be stable before the clock trigger for proper input read
Hold Time: how long the input must be stable after the clock trigger for proper input read
“Clock-to-Q” Delay: how long it takes the output to change, measured from the clock trigger
19
CMPT 295
L26: Sequential Logic
20
Flip-Flop Timing Behavior
CMPT 295
L26: Sequential Logic
21
Flip-Flop Timing Behavior
Setup Time
CMPT 295
L26: Sequential Logic
22
Flip-Flop Timing Behavior
Hold Time
CMPT 295
L26: Sequential Logic
23
Flip-Flop Timing Behavior
Clock-to-Q
CMPT 295
L26: Sequential Logic
Accumulator Revisited
Proper Timing
reset signal shown
In practice Xi might not arrive to the adder at the same time as Si-1
Si temporarily is wrong, but register always captures correct value
In good circuits, instability never happens around rising edge of CLK
“Undefined” (unknown) signal
24
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
25
CMPT 295
L26: Sequential Logic
STOP HERE
25
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary
Bonus Slides
Logisim Intro
26
CMPT 295
L26: Sequential Logic
26
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?
27
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
28
CMPT 295
L26: Sequential Logic
28
Maximum Clock Frequency
29
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.
31
CMPT 295
L26: Sequential Logic
31
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!
32
Timing:
CMPT 295
L26: Sequential Logic
Pipelining and Clock Frequency (2/2)
33
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
34
CMPT 295
L26: Sequential Logic
35
Question: Want to run on 1 GHz processor.
tadd = 100 ps. tmult = 200 ps. tsetup = thold = 50 ps.
What is the maximum clock-to-q time?
550 ps
(A)
750 ps
(B)
500 ps
(C)
700 ps
(D)
CMPT 295
L26: Sequential Logic
Spend 2-3 min on
35
36
550 ps
(A)
750 ps
(B)
500 ps
(C)
700 ps
(D)
Bottom path is critical path:
clock-to-q + 100 + 200 + 100 + 50 < 1000 ps = 1ns
clock-to-q + 450 < 1000 ps
clock-to-q < 550
Question: Want to run on 1 GHz processor.
tadd = 100 ps. tmult = 200 ps. tsetup = thold = 50 ps.
What is the maximum clock-to-q time?
CMPT 295
L26: Sequential Logic
36
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Functional Units
Summary
Bonus Slides
FSMs
37
CMPT 295
L26: Sequential Logic
37
Functional Units (a.k.a. Execution Unit)
Now that we know sequential logic, we can explore some pieces of a processor!
Functional Units are a part of the processor that perform operations and calculations based on the running program
Arithmetic Logic Unit
Floating Point Unit
Load/Store Unit
and several more...
38
Invented by John Von Neumann
He also invented
Stored Program Concept
Mergesort
Mutually Assured Destruction
CMPT 295
L26: Sequential Logic
Should be at no later than 10
Most processors contain a special logic block called the “Arithmetic Logic Unit” (ALU)
We’ll show you an easy one that does ADD, SUB, bitwise AND, and bitwise OR
Schematic:
39
Arithmetic Logic Unit (ALU)
when S=00, R = A + B
when S=01, R = A – B
when S=10, R = A AND B
when S=11, R = A OR B
CMPT 295
L26: Sequential Logic
Simple ALU Schematic
40
Notice that 3 values are ALWAYS calculated in parallel, but only 1 makes it to the Result
CMPT 295
L26: Sequential Logic
Adder/Subtractor Design
Combinational Logic design we’ve seen before:
write out truth table
convert to boolean logic
minimize logic
then implement
How big might truth table and/or Boolean expression get?
41
CMPT 295
L26: Sequential Logic
Adder/Subtractor Design
Break down the problem into smaller pieces that we can cascade or hierarchically layer
Let’s try this approach instead
42
CMPT 295
L26: Sequential Logic
Adder/Subtractor: 1-bit LSB Adder
43
Carry-out bit
CMPT 295
L26: Sequential Logic
Adder/Subtractor: 1-bit Adder
44
Here defining XOR of many inputs to be 1 when an odd number of inputs are 1
Possible carry-in c1
CMPT 295
L26: Sequential Logic
Adder/Subtractor: 1-bit Adder
45
Circuit Diagrams:
CMPT 295
L26: Sequential Logic
N x 1-bit Adders → N-bit Adder
46
+
+
+
b0
Connect CarryOuti-1 to CarryIni to chain adders:
CMPT 295
L26: Sequential Logic
Two’s Complement Adder/Subtractor
47
+
+
+
Subtraction accomplished by adding negated number:
x ^ 1 = x’
(flips the bits)
This signal is only
high when you
perform subtraction
Add 1
Where did this come from?
CMPT 295
L26: Sequential Logic
Detecting Overflow
48
Unsigned overflow
On addition, if carry-out from MSB is 1
On subtraction, if carry-out from MSB is 0
This case is a lot harder to see than you might think
Signed overflow
Overflow from adding “large” positive numbers
Overflow from adding “large” negative numbers
CMPT 295
L26: Sequential Logic
Unsigned: still use signed subtraction procedure (flip bits & add 1). When doing x-x, get all 1s plus 1, which leads to carry-out. If y>x in x-y, then fewer 1s in sum, so no carry-out.
48
Signed Overflow Examples (4-bit)
49
Overflow from two positive numbers:
0111 + 0111, 0111 + 0001, 0100 + 0100.
Carry-out from the 2nd MSB (but not MSB)
pos + pos ≠ neg
Overflow from two negative numbers:
1000 + 1000, 1000 + 1111, 1011 + 1011.
Carry-out from the MSB (but not 2nd MSB)
neg + neg ≠ pos
Expression for signed overflow: Cn XOR Cn-1
CMPT 295
L26: Sequential Logic
Simple ALU Schematic
50
CMPT 295
L26: Sequential Logic
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary
Bonus Slides
Logisim Intro
51
CMPT 295
L26: Sequential Logic
51
Summary
Hardware systems are constructed from Stateless Combinational Logic and
Stateful Sequential Logic (includes registers)
Circuits have a delay to them, and the critical path (longest delay between registers) determines the maximum clock frequency
52
CMPT 295
L26: Sequential Logic
Non Testable Material
53
CMPT 295
L26: Sequential Logic
Back to representations
How do we represent sequential logic?
Truth tables could account for history
We could do boolean logic with prior state as a variable
We can also use a new representation:
Finite State Machines
54
CMPT 295
L26: Sequential Logic
54
A convenient way to conceptualize computation over time
Function can be represented with a state transition diagram
With combinational
logic and registers, any
FSM can be implemented
in hardware!
Finite State Machines (FSMs)
55
CMPT 295
L26: Sequential Logic
An FSM (in this class) is defined by:
A set of states S (circles)
An initial state s0 (only arrow not between states)
A transition function that maps from the current input and current state to the output and the next state (arrows between states)
State transitions are controlled by the clock:
On each clock cycle the machine checks the inputs and generates a new state (could be same) and new output
56
FSM Overview
CMPT 295
L26: Sequential Logic
57
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
States: S0, S1, S2
Initial State: S0
Transitions of form:
input/output
CMPT 295
L26: Sequential Logic
58
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
59
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
60
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
61
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
62
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
63
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
64
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
65
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
CMPT 295
L26: Sequential Logic
66
FSM to detect 3 consecutive 1’s in the Input
Example: 3 Ones FSM
Starting state in red
Resulting state in Blue
And so on…
CMPT 295
L26: Sequential Logic
Hardware Implementation of FSM
Register holds a representation of the FSM’s state
Must assign a unique bit pattern for each state
Output is present/current state (PS/CS)
Input is next state (NS)
Combinational Logic implements transition function (state transitions + output)
7/5/2018
CS61C Su18 – Lecture 10
67
+
=
CMPT 295
L26: Sequential Logic
FSM: Combinational Logic
Read off transitions into Truth Table!
Inputs: Current State (CS) and Input (In)
Outputs: Next State (NS) and Output (Out)
68
CS In NS Out
00 0 00 0
00 1 01 0
01 0 00 0
01 1 10 0
10 0 00 0
10 1 00 1
CMPT 295
L26: Sequential Logic
In lecture: Implement logic for Out (1 NOT, 2 AND gates)
68
Unspecified Output Values
Our FSM has only 3 states
2 entries in truth table are
undefined/unspecified
Use symbol ‘X’ to mean it can
be either a 0 or 1
Make choice to simplify final
expression
Any choice is correct
69
CS In NS Out
00 0 00 0
00 1 01 0
01 0 00 0
01 1 10 0
10 0 00 0
10 1 00 1
11 0 XX X
11 1 XX X
CMPT 295
L26: Sequential Logic
3 Ones FSM in Hardware
2-bit Register needed for state
CL: NS1 = CS0In, NS0 = ¬CS1¬CS0In, Out = CS1In
70
CMPT 295
L26: Sequential Logic
1050 cutoff