Transcript 60-265 Computer Organization

60-265
COMPUTER ARCHITECTURE I:
Digital Design
Akshai Aggarwal
1
Course Outline
•Binary, Octal and Hexadecimal number system
•Digital logic and Boolean Algebra
•Combinational and sequential circuit design
• Digital components: decoders, multiplexers, registers,
counters, memory etc.; Digital Integrated Circuits
•Register transfer and micro-operations
• Basic computer organization and design
• CPU structure, control unit design, interrupt handling
 HOW DOES A COMPUTER WORK?
• Elementary assembly language instruction set and the
execution process
2
Grading Scheme
Quizzes/
Individual
Assignments
Quizzes: to be conducted at the beginning of some of
10% the labs;
For dates, please see the web-site.
Midterm 1
15% Saturday May 30, 12.30 PM, Venue: Erie 1118
Midterm 2
15% Saturday June 13, 12.30 PM, Venue: Erie 1118
Final
40% As scheduled by the university
Labs
10% Attendance is mandatory
Group
Assignment
10%
Submission of Assignment: in the Lab on Monday
1STJune
3
Quizzes
Day and Date
Wednesday, 13th
May
Wednesday, 20th
May
Wednesday, 27th
May
Wednesday, 3rd
June
Wednesday,10th
June
Time of Quiz
for
Section 51
Time of Quiz
for
Section 52
4 PM
5.30 PM
4 PM
5.30 PM
4 PM
5.30 PM
4 PM
5.30 PM
4 PM
5.30 PM
4
Digital Computers
DIGITAL : information represented by variables that take a
limited number of values
•BINARY : - reliability of hardware
-binary nature of human logic
DIGITAL COMPUTER: A discrete information processing
system
A SYSTEM: An organized collection of components, that
interact through communication links among themselves and
with their environment to provide a predefined functionality.
5
ARRAYS OF BITS:
1001011 may represent
•75 in decimal, or
•K in ASCII code or
•some control code.
6
History: ENIAC
Electrical Numerical Integrator And Computer
(ENIAC):





developed by Professor John Mauchly and his
graduate student John Presper Eckert
For army’s Ballistic Research Lab for calculating
range and trajectory tables for new weapons
Start 1943; development completed in 1946; used for
Nuclear bomb computations
18000 vacuum tubes, 140 kW power, 30 ton, 1500
sq ft of floor space
Decimal machine; programming manually by setting
switches and plugging and unplugging cables
7
1945: A New Project:
Electronic Discrete Variable Computer (EDVAC)



EDVAC: planned by John Von Neumann as a Stored
Program machine
Developed at Princeton Institute for Advanced
Studies as the IAS computer from 1946 -1952
consisted of
main memory
 Arithmetic Logic Unit and Control Unit  CPU
 Registers in CPU: Accumulator, Address Register,
Program Counter, Data Register and other Registers
 Input/Output


Used binary numbers
8
FUNCTIONAL PARTS:
- hardware: CPU, memory, I/O units
-software
• System software
• Application program
Logical view vs. Physical components
9
Architecture
Architecture of a computer:
 those properties, which directly affect
the logical working of a program;
 the attributes, which are apparent to a
programmer
Examples: instruction set, number of bits
used to represent data
10
Von Neumann Architecture of a
digital computer:
Von Neumann Architecture of a Digital Computer
Memory
Central processing
unit
Input
I/O Processor
Output
Devices
11
Computer Architecture:
• Structure and behavior of the computer as seen by
the user.
It includes:
1. Instruction set.
2. Information formats.
3. Techniques for addressing memory.
The course is an introduction to the three aspects.
12
Organization

Organization: operational units and
their interconnection for realizing the
architectural specifications
•
•
Determination of which hardware should
be used and
how the parts should be connected
together
13
Logic Gates and Boolean Algebra:
1832: 17 years old Boole: inspired to put logical
statements in a mathematical form
1854: ‘The Laws of thought’ - George Boole.
“An investigation of the laws of
thought, on which are founded the
Mathematical Theories of Logic and
Probabilities”
Binary Variables:
Logic Operations – Truth Table, logic diagram,
Boolean Expressions.
14
Objectives of Boole



to investigate the fundamental laws of
those operations of the mind by which
reasoning is performed;
to give expression to them in the
symbolic language of a Calculus
to deduce, from these studies, some
probable imitations concerning the
nature and constitution of the human
mind.
15
The Values of Boole’s variables



"the Universe" and "Nothing"
“True” and “False”
1 and 0
Boole thought: Boole’s Algebra: represented
mathematical systemization of human thought.
 Not true.
But thinking about machines, which think
like a human being  powerful machines.
16
Hollerith  IBM
 1881:Mechanical Engineer at American
Census Bureau, Washington: devised a
punched card system for processing the
census data of 1890 – the idea from his
boss, John Shaw Billings
 1882-83: Instructor at MIT
 1896: Hollerith’s Tabulating Machines
Company  International Business
Machines
17
Logic gates:
Buffer gate
Inverter or NOT gate
Logic Symbol Truth Table
A
A
Out
NOT gate
Out
0 1
1 0
Algebraic Expression
–
A, A’
18
Gates (continued): AND and OR
GATES
Logic Symbol
A
B
A
B
Out
AND
Out
OR
Truth Table
A B
Out
0
0
1
1
0
1
0
1
A
0
0
1
1
B
0
1
0
1
0
0
0
1
Out
0
1
1
1
Algebraic Expression
A.B, AB, A*B, A^B
A+B, AvB
19
Gates (continued): XOR and NAND
gates
Logic symbol
Truth Table
Algebraic Expression
A B Out
A
B
A
B
Out
XOR
Out
NAND
0
0
1
1
0
1
0
1
0
1
1
0
A
0
0
1
1
B
0
1
0
1
Out
1
1
1
0
AB
A.B,
(AB)’
20
Gates (continued): NOR and XNOR
gates
Logical Symbol
Truth Table
Algebraic Expression
A B Out
A
B
Out
NOR
A
B
Out
XNOR
0
0
1
1
0
1
0
1
1
0
0
0
A B Out
0 0 1
0 1 0
1 0 0
1 1 1
A+B
AB
21
Boolean Gates

Gates:
AND, OR, NOT
 XOR, XNOR
 NAND, NOR
 Buffer
NOT and Buffer are single-input gates.
All the others are multi-input gates.
The number of inputs to a gate is known as its



Fan-in.
22
Boolean Algebra




Boolean Algebra uses Boolean variables.
A Boolean variable can have only two possible
values: 0 or 1.
Boolean operations: any of the operations
defined by logic gates
Property of CLOSURE: If A and B are Boolean
variables, A + B and A.B are also Boolean
variables.
Identity Element

identity element (or neutral element) is a special
type of element of a set with respect to a binary
operation on that set. It leaves other elements
unchanged when combined with them. This is used
for groups and related concepts.
(Ref: http://en.wikipedia.org/wiki/Identity_element)

OR operation: 0 is the Identity Element for OR:
1 + 0 = 1; 0 + 0 = 0

AND operation: 1 is the Identity Element for AND:
1.1 = 1; 0.1 = 0
24
Boolean identities:
1
2
3
x+0=x
x+1=1
x+x=x
(Idempotency)
4
5
x + x’ = 1
x+y=y+x
(Commutativity)
6 x + (y + z) = (x + y) + z
(Associativity)
x.0=0
x.1=x
x.x= x
(Idempotency)
x . x’ = 0
x.y=y.x
(Commutativity)
x . (y . z) = (x . y) . z
(Associativity)
25
Continuation of Boolean Identities:
7
8
x.(y + z) = x.y + x.z
(Distributive)
(x + y)’ = x’.y’
(De Morgan’s Theorem)
9
10
11
12
x + (y.z)=(x + y).(x + z)
(Distributive)
(x.y)’ = x’ + y’
(De Morgan’s Theorem)
(x’)’ = x
x + xy = x
x + x’y = x + y
xy + xy’ = x
13 xy + x’z + yz = xy + x’z
(Consensus Theorem)
x (x + y) = x
x (x’ + y) = xy
(x + y).(x + y’) = x
(x+y)(x’+z)(y+z)=(x+y)(x’+z)
(Consensus Theorem)
26
Example 7(b):
A few comments:
7(b)
x + yz = (x + y)(x + Z)
RHS = x + xy + xz + yz
= x(1 + y + z) + yz
= x + yz
= LHS
27
De Morgan’s Theorem:
De Morgan’s Theorems
8(a) (x + y)’ = x’.y’
F
X
y
NOR
X
Y
F
NOR
28
Continuation of the proof:
De’ Morgan’s theorem
Proof:
x
y x + y (x+y)’ x’
y’ x’ . y’
0
0
0
1
1
1
1
0
1
1
0
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
29
Another Method for proving
De Morgan’s theorem …1
Identity 4(a):
A + A’ = 1
 Identity 4(b):
A.A’ = 0
 To prove: A is the complement of B 
prove that (i) A + B = 1 and (ii) A.B = 0
 To prove: (x + y)’ = x’.y’,
consider A = x’.y’ and B = x + y;
Prove that (i) x’.y’ + (x + y) = 1 and
(ii) x’.y’.(x + y) = 0 
A is the complement of B.

30
Another Method for proving
De Morgan’s theorem …2
Proof: (i) LHS = x’.y’ + (x + y)
= (x’.y’ + x) + y
= x + y’ + y
by using Th. 11(a)
=x+1
by using Th. 4(a)
=1
by using Th. 2(a)
(ii) LHS = x’.y’.(x + y) = x.x’.y’ + x’.y’.y
= 0.y’ + x’.0
by using Th. 4(b)
=0
Hence (x + y)’ = x’.y’.
31
Examples 8(b) and 10 (b):
8(b) (x y)’ = x’ + y’; The proof is similar to that
for 8(a).
10(b)
LHS = x (x + y)
= x + xy
= x (1 + y)
=x
= RHS
32
Examples 11(a):
11 (a)
LHS = x + x’y
Use x = x.(1 + y)
by using 1 + y = 1 and x.1 = x
= x + x.y
= x.x + x.y
by using x = x.x
= x.x + x.y + x.x’
by using x.x’ = 0 and A + 0 = A
LHS = (x.x + x.y + x.x’) + x’.y
= x.(x + y) + x’.(x + y)
= (x + x’).(x + y)
=x+y
by using x + x’ = 1 and 1.B = B
33
Examples 11(b) and 12:
11(b)
12 (b)
x.(x’ + y)
= x.x’ + x.y
= x.y
by using x.x’ = 0 and
(x + y).(x + y’)
= x + x.y’ + x.y + y.y’
= x.(1 + y’ + x)
0+A=A
by using x.x’ = 0 and 0 + A = A
=x
by using 1 + y’ + x = 1 and x.1 = x
34
Example 13:
13 (a)
13 (b)
LHS = x.y + x’.z + y.z
= x.y + x’.z + (x + x’).y.z
= x.y.(1 + z) + x’.z.(1 + y)
= xy + x’z = RHS
LHS = (x + y).(x’ + z).(y + z)
= (x.y + x.z + y + y.z).(x’ + z)
= (x.z + y.(1 + x + z)). (x’ + z)
= (y + x.z).(x’ + z)
= x’.y + y.z + x.x’.z + x.z
= xx’ + x’y + yz + xz
= x’.(x + y) + z.(x + y)
= (x + y).(x’ + z) = RHS
35
Boolean Algebra






Closure:
X + Y, X.Y
Identity Element:
0,
1
Commutation:
X + Y = Y + X,
X.Y = Y.X
Distribution: X.(Y + Z) = X.Y + X.Z,
X + (Y.Z) = (X + Y).(X + Z)
Complements:
X + X’ = 1,
X.X’ = 0
Idempotency
X + X = X, X.X = X
36
Boolean cont…
Decimal
A
B
C
D
0
0
0
0
0
1
0
0
1
0
2
0
1
0
0
3
0
1
1
0
4
1
0
0
0
5
1
0
1
0
6
1
1
0
0
7
1
1
1
1
37