程序代写代做代考 chain cache assembly Java Memory Allocation III CSE 351 Autumn 2016

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