程序代写代做代考 cache RISC-V assembly Memory Allocation III CSE 351 Autumn 2016

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