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

Memory Allocation III CSE 351 Autumn 2016

Digital Logic – Combinational

CMPT 295
L25: Combinational Logic

Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
2

CMPT 295
L25: Combinational Logic

Roadmap
3
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
L25: Combinational Logic

3

Why is this important?
Why study hardware design?
Background for other more in-depth classes
Only course in CMPT that deals with hardware
We need some digital systems knowledge to build our own processor
4

CMPT 295
L25: Combinational Logic

Why is this important?

We need some digital systems knowledge to build our own processor

Why build our own processor?
Because we believe computer scientists should have an answer to the question “How does a computer work?”
So you can understand how code is actually executed on a computer
5

CMPT 295
L25: Combinational Logic

Why is this important?

So you can understand how code is actually executed on a computer

Why do we care about how code executes?
Reliability
Performance
Security
6

CMPT 295
L25: Combinational Logic

Hardware Design
Why study hardware design and processors and computers
if you only care about high-level software?

Example of the power of layered abstractions
Transistors -> Combinational Logic
Combinational Logic -> Sequential Logic
Sequential Logic -> Processors
Processors -> Machine Language
Machine Language -> Assembly
Assembly -> High-level Programming Languages
High-level Programming Languages -> Word,Minecraft,Twitter

At each step we can “abstract away” the lower steps and (mostly) forget they exist
7

CMPT 295
L25: Combinational 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
8

CMPT 295
L25: Combinational Logic

9

CMPT 295
L25: Combinational Logic

9

Historical Trend
10
Trend:
Hardware gets more powerful every year.
(Really due to hard work of thousands of engineers)

Therefore:
Software gets more resources and faster compute!
(And has to keep up with ever-changing hardware)

CMPT 295
L25: Combinational Logic

10

Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification

11

CMPT 295
L25: Combinational 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)

12

CMPT 295
L25: Combinational 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!
13

CMPT 295
L25: Combinational 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

14

CMPT 295
L25: Combinational Logic

15

A
B
C
D
Combining Multiple Logic Gates

(NOT(A AND B)) AND (A OR (NOT B AND C))

CMPT 295
L25: Combinational Logic

15

Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification

16

CMPT 295
L25: Combinational Logic

Representations of
Combinational Logic
Text Description
Circuit Diagram
Transistors and wires
Logic Gates
Truth Table
Boolean Expression

All are equivalent
17

CMPT 295
L25: Combinational Logic

Truth Tables
Table that relates the inputs to a combinational logic circuit to its output
Output only depends on current inputs
Use abstraction of 0/1 instead of high/low V
Shows output for every possible combination of inputs
How big?
0 or 1 for each of N inputs, so 2N rows
18

CMPT 295
L25: Combinational 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

19
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
L25: Combinational Logic
Circle the output, use variables/animations, talk about the output as a bit combination (integer?)
Maybe 3 inputs?

Multiple Outputs
For 3 outputs, just three indep. functions:
X(A,B,C,D), Y(A,B,C,D), and Z(A,B,C,D)
Can show functions in separate columns without
adding any rows!
F
Y
A
B
C
D
X
Z
20

CMPT 295
L25: Combinational Logic

Question: Convert the following statements into
a Truth Table for: (x XOR y) OR (NOT z)
X Y Z (A) (B) (C) (D)
0 0 0 1 1 1 1
0 0 1 0 0 0 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 0 1
1 1 0 1 1 1 0
1 1 1 1 0 1 1

21

CMPT 295
L25: Combinational Logic

21

Question: Convert the following statements into
a Truth Table for: (x XOR y) OR (NOT z)
X Y Z (A) (B) (C) (D)
0 0 0 1 1 1 1
0 0 1 0 0 0 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 0 1
1 1 0 1 1 1 0
1 1 1 1 0 1 1

22

CMPT 295
L25: Combinational Logic

22

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?

23

CMPT 295
L25: Combinational Logic

Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification

24

CMPT 295
L25: Combinational Logic

My Hand Hurts…
Truth tables are huge
Write out EVERY combination of inputs and outputs (thorough, but inefficient)
Finding a particular combination of inputs involves scanning a large portion of the table
There must be a shorter way to represent combinational logic
Boolean Algebra to the rescue!
25

CMPT 295
L25: Combinational 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
26

CMPT 295
L25: Combinational Logic

Laws of Boolean Algebra
These laws allow us to perform simplification:
27

CMPT 295
L25: Combinational Logic
Demorgan’s law example
27

We can show that these
are equivalent!
Truth Table to Boolean Expression
Read off of table
For 1, write variable name
For 0, write complement of variable
Sum of Products (SoP)
Take rows with 1’s in output column,
sum products of inputs
c=
Product of Sums (PoS)
Take rows with 0’s in output column, product the sum of the complements of the inputs
c =
a b c
0 0 0
0 1 1
1 0 1
1 1 0

28
¬a
b
+
a

¬b

(a + b) · (¬a + ¬b)

CMPT 295
L25: Combinational Logic
Choice between the two generally comes down to whether the output function has more 0’s or 1’s. Choosing the conversion (SoP/PoS) with less items will result in a shorter expression!
(This example happens to be balanced: 2 0’s and 2 1’s)
28

Faster Hardware?
Recall: Everything we are dealing with is just an abstraction of transistors and wires
Inputs propagating to the outputs are voltage signals passing through transistor networks
There is always some delay before a CL’s output updates to reflect the inputs
Simpler Boolean expressions ↔ smaller transistor networks ↔ smaller circuit delays ↔ faster hardware
29

CMPT 295
L25: Combinational Logic

Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary

Bonus Slides
Logisim Intro
30

CMPT 295
L25: Combinational 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
31

This input is passed to output if selector bits match shown value
Represents that this wire has n bits

CMPT 295
L25: Combinational Logic

Implementing a 1-bit 2-to-1 MUX
Schematic:

Truth Table:
Boolean Algebra:

Circuit Diagram:
32

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
L25: Combinational Logic

1-bit 4-to-1 MUX (1/2)
Schematic:

Truth Table: How many rows?
Boolean Expression:
e = ¬s1¬s0a + ¬s1s0b + s1¬s0c + s1s0d
33

26

CMPT 295
L25: Combinational Logic

1-bit 4-to-1 MUX (2/2)
Can we leverage what we’ve previously built?
Alternative hierarchical approach:
34

CMPT 295
L25: Combinational Logic

Bonus slides (not testable)

35

CMPT 295
L25: Combinational Logic
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification

36

CMPT 295
L25: Combinational Logic

Manipulating Boolean Algebra
SoP and PoS expressions can still be long
We wanted to have shorter representation than a truth table!
Boolean algebra follows a set of rules that allow for simplification
Goal will be to arrive at the simplest equivalent expression
Allows us to build simpler (and faster) hardware
37

CMPT 295
L25: Combinational Logic

Boolean Algebraic
Simplification Example

38

CMPT 295
L25: Combinational Logic
Do on black board
From distribution: a(b +1) + c
Froms laws of 0s and 1s: b+1 = b
= ab + c
Truth Table
a b c y
0 0 0 0
0 0 1 1
0 0 1 1

38

Circuit Simplification

(Transistors and/or Gates)
1)
2)
3)
4)
39

CMPT 295
L25: Combinational Logic

Representations of
Combinational Logic
Text Description
Circuit Diagram
Transistors and wires
Logic Gates
Truth Table
Boolean Expression

All are equivalent
40

CMPT 295
L25: Combinational Logic

Try all input
combinations

SoP or PoS

Propagate signals
through gates

Try all input combinations
Converting Combinational Logic
Truth
Table
Boolean
Expression
Circuit
Diagram
This is difficult to do efficiently!

Wire inputs to proper gates
(easiest to use AND, OR, and NOT)
41

CMPT 295
L25: Combinational Logic

Circuit Simplification Example (1/4)
Simplify the following circuit:

Options:
Test all combinations of the inputs and build the Truth Table, then use SoP or PoS
Write out expressions for signals based on gates
Will show this method here

A
B
C
D
42

CMPT 295
L25: Combinational 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
43
Arrive at D = ¬(AB)(A + ¬BC)

CMPT 295
L25: Combinational 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”?
44

CMPT 295
L25: Combinational 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
45

CMPT 295
L25: Combinational 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.
45