Transcript Building the CPU - Texas State Department of Computer Science

Building the CPU
CS 1308 – Computer Literacy and the Internet
It’s Not Magic
 The goal of the next series of lectures is to show you exactly
how a computer works.
 We will discuss the logic used to create computer
instructions and how the computer decides which
instructions to execute.
 Although at times it may appear to be magical. It’s just math
and science.
2
Our Picture of a Computer
Data Bus
memory
control
unit
input/
output
registers
arithmeticlogic unit
Central Processing
Unit (CPU)
The Reliability of Binary Representation
 Electronic devices are most reliable in a bistable environment
 Bistable environment
 Distinguishing only two electronic states
 Current flowing or not
 Direction of flow
 Computers are bistable: hence binary representations
4
A Switch is a 2-state device that can be
toggled
A relay is a switch built with an electromagnet
controlled current
controlling current
when the controlling current is 1, the electromagnet pulls
the switch closed, and the controlled current flows through
the switch
5
Switches can do it all
 With switches we can implement AND, OR, and NOT gates
 With just those types of gates, we can design circuits to
perform any computation
 Remember, computers do very simple tasks, very quickly
6
Basic electric circuits:
Computing AND
in1
power
source
in1
in2
7
and
in2
out
when both inputs are 1,
the circuit is closed
out
= in1 in2
CS 302 - Computer Fluency
in1 in2 out
0 0
0
0 1
0
1
0
0
1
1
1
}
truth table
for AND
Basic electric circuits:
Computing OR
in1
in2
out
when either input is 1,
the circuit is closed
in1
in2
8
or
in1 in2 out
0 0
0
0 1
1
out
1
0
1
1
1
= in1 + in2 1
}
truth table
for OR
Basic electric circuits:
Computing NOT
in1
A new type of
switch
which is closed
at rest
in1
9
not
out
= in1’
in1 out
0 1
1 0
out
}
truth table
for NOT
A better switch: Transistors
 bi-stable, solid state device
 switching is done electronically, not mechanically
 no moving parts; therefore, fast, small, reliable
 can switch states in about one 10 billionth of a second
 about 5 million transistors can fit on a chip 1 centimeter square.
Density is increasing rapidly with new technology.
10
Figure 4.11
Simplified Model of a Transistor
CS 302 - Computer Fluency
11
Boolean Logic and Gates: Boolean
Logic
 Boolean logic describes operations on true/false values
 True/false maps easily onto bistable environment
 Boolean logic operations on electronic signals may be
built out of transistors and other electronic devices
12
Boolean Logic (continued)
 Boolean expressions
 Constructed by combining together Boolean operations
 Example: (a AND b) OR ((NOT b) AND (NOT a))
 Truth tables capture the output/value of a Boolean expression
 A column for each input plus the output
 A row for each combination of input values
13
Boolean Logic (continued)
 Example:
(a AND b) OR ((NOT b) and (NOT a))
14
a
b
Value
0
0
1
0
1
0
1
0
0
1
1
1
Building Computer Circuits:
Introduction
 A circuit is a collection of logic gates:
 Transforms a set of binary inputs into a set of binary outputs
 Values of the outputs depend only on the current values of the
inputs
 Combinational circuits have no cycles in them (no outputs feed
back into their own inputs)
15
A Compare-for-equality Circuit
 Compare-for-equality circuit
 CE compares two unsigned binary integers for equality
 Built by combining together 1-bit comparison circuits (1-CE)
 Integers are equal if corresponding bits are equal (AND
together 1-CD circuits for each pair of bits)
16
A Compare-for-equality Circuit
(continued)
 1-CE circuit truth table
17
a
b
Output
0
0
1
0
1
0
1
0
0
1
1
1
Figure 4.22
One-Bit Compare for Equality Circuit
CS 302 - Computer Fluency
18
A Compare-for-equality Circuit
(continued)
 1-CE Boolean expression
 First case: (NOT a) AND (NOT b)
 Second case: a AND b
 Combined:
((NOT a) AND (NOT b)) OR (a AND b)
19
Figure 4.19
Diagram of a Typical Computer Circuit
CS 302 - Computer Fluency
20
A Circuit Construction Algorithm
 Sum-of-products algorithm
 Truth table captures every input/output possible for circuit
 Repeat process for each output line
 Build a Boolean expression using AND and NOT for each 1 of the
output line
 Combine together all the expressions with ORs
 Build circuit from whole Boolean expression
21
Examples Of Circuit Design And
Construction
 Compare-for-equality circuit
 Addition circuit
 Both circuits can be built using the sum-of-products
algorithm
22
An Addition Circuit
 Addition circuit
 Adds two unsigned binary integers, setting output bits and an overflow
 Built from 1-bit adders (1-ADD)
 Starting with rightmost bits, each pair produces
 A value for that order
 A carry bit for next place to the left
23
An Addition Circuit (continued)
 1-ADD truth table
 Input
 One bit from each input integer
 One carry bit (always zero for rightmost bit)
 Output
 One bit for output place value
 One “carry” bit
24
Figure 4.24
The 1-ADD Circuit and Truth Table
25
An Addition Circuit (continued)
 Building the full adder
 Put rightmost bits into 1-ADD, with zero for the input carry
 Send 1-ADD’s output value to output, and put its carry value as
input to 1-ADD for next bits to left
 Repeat process for all bits
26
Computer Instructions
 The logic for every instruction is executed on
every cycle by the Arithmetic and Logic Unit
(ALU).
 The answer used is the one for the instruction
that is currently decoded and executed by the
CPU.
 This selection is done by the Control Circuits.
27
Control Circuits
 Do not perform computations
 Choose order of operations or select among data values
 Major types of controls circuits
 Multiplexors
 Select one of inputs to send to output
 Decoders
 Sends a 1 on one output line, based on what input line indicates
28
Control Circuits (continued)
 Multiplexor form
 2N regular input lines
 N selector input lines
 1 output line
 Multiplexor purpose
 Given a code number for some input, selects that input to pass along to
its output
 Used to choose the right input value to send to a computational circuit
29
Figure 4.28
A Two-Input Multiplexor Circuit
30
Control Circuits (continued)
 Decoder
 Form
 N input lines (typically the size of the BUS)
 2N output lines
 N input lines indicate a binary number, which is used to select one of the
output lines
 Selected output sends a 1, all others send 0
31
Control Circuits (continued)
 Decoder purpose
 Given a number code for some operation, trigger just that operation
to take place
 Numbers might be codes for arithmetic: add, subtract, etc.
 Decoder signals which operation takes place next
32
Figure 4.29
A 2-to-4 Decoder Circuit
33
Summary
 Binary values create a bistable environment, making
computers reliable
 Boolean logic maps easily onto electronic hardware
 Circuits are constructed using Boolean expressions as an
abstraction
 Computational and control circuits may be built from Boolean
gates
34