Computer Architecture

Lecture - 1
Dr. Fatma Sakr
 Chapter 1

Digital Design and Computer Architecture, 2nd Edition

David Money Harris and Sarah L. Harris

Chapter 1 <2>
 Chapter 1 :: Topics
• Background
• The Game Plan
• The Art of Managing Complexity
• The Digital Abstraction
• Number Systems
• Logic Gates
• Logic Levels
• CMOS Transistors
• Power Consumption

Chapter 1 <3>
 Background
• Microprocessors have revolutionized our world
– Cell phones, Internet, rapid advances in medicine, etc.
• The semiconductor industry has grown from $21
billion in 1985 to $300 billion in 2011

Chapter 1 <4>
 The Game Plan
• Purpose of course:
– Understand what’s under the hood of a computer
– Learn the principles of digital design
– Learn to systematically debug increasingly
complex designs
– Design and build a microprocessor

Chapter 1 <5>
 The Art of Managing Complexity
• Abstraction
• Discipline
• The Three –y’s
– Hierarchy
– Modularity
– Regularity

Chapter 1 <6>
 Abstraction
• Hiding details when programs

they aren’t important device drivers

instructions
registers

focus of this course

datapaths
controllers

adders
memories

AND gates
NOT gates

amplifiers
filters

transistors
diodes

electrons

Chapter 1 <7>
 Discipline
• Intentionally restrict design choices
• Example: Digital discipline
– Discrete voltages instead of continuous
– Simpler to design than analog circuits – can build more sophisticated
systems
– Digital systems replacing analog predecessors:
• i.e., digital cameras, digital television, cell phones,
CDs

Chapter 1 <8>
 The Three -y’s
• Hierarchy
– A system divided into modules and submodules

• Modularity
– Having well-defined functions and interfaces

• Regularity
– Encouraging uniformity, so modules can be easily reused

Chapter 1 <9>
 Example: The Flintlock Rifle
• Hierarchy
– Three main modules:
lock, stock, and barrel

– Submodules of lock:
hammer, flint, frizzen,
etc.

Chapter 1 <10>
 Example: The Flintlock Rifle
• Modularity
– Function of stock :
mount barrel and lock
– Interface of stock :
length and location of
mounting pins

• Regularity
– Interchangeable parts

Chapter 1 <11>
 The Digital Abstraction

• Most physical variables are continuous

– Voltage on a wire
– Frequency of an oscillation
– Position of a mass
• Digital abstraction considers discrete
subset of values

Chapter 1 <12>
 The Analytical Engine
• Designed by Charles
Babbage from 1834 –
1871
• Considered to be the
first digital computer
• Built from mechanical
gears, where each gear
represented a discrete
value (0-9)
• Babbage died before it
was finished
Chapter 1 <13>
 Digital Discipline: Binary Values
• Two discrete values:
– 1’s and 0’s
– 1, TRUE, HIGH
– 0, FALSE, LOW
• 1 and 0: voltage levels, rotating gears, fluid
levels, etc.
• Digital circuits use voltage levels to represent
1 and 0
• Bit: Binary digit

Chapter 1 <14>
 Chapter 1 <15>
Number Systems
• Decimal numbers

• Binary numbers
537410 =

11012 =
1's column 1's column
10's column 2's column
100's column 4's column
1000's column 8's column
 Number Systems
• Decimal numbers

1000's column

10's column
1's column
100's column

537410 = 5 × 103 + 3 × 102 + 7 × 101 + 4 × 100

five three seven four
thousands hundreds tens ones

• Binary numbers
8's column

2's column
1's column
4's column

11012 = 1 × 23 + 1 × 22 + 0 × 21 + 1 × 20 = 1310
one one no one
eight four two one

Chapter 1 <16>
 Powers of Two
• 20 = • 28 =
• 21 = • 29 =
• 22 = • 210 =
• 23 = • 211 =
• 24 = • 212 =
• 25 = • 213 =
• 26 = • 214 =
• 27 = • 215 =

Chapter 1 <17>
 Powers of Two
• 20 = 1 • 28 = 256
• 21 = 2 • 29 = 512
• 22 = 4 • 210 = 1024
• 23 = 8 • 211 = 2048
• 24 = 16 • 212 = 4096
• 25 = 32 • 213 = 8192
• 26 = 64 • 214 = 16384
• 27 = 128 • 215 = 32768
• Handy to memorize up to 29
Chapter 1 <18>
 Number Conversion
• Binary to Decimal conversion:
– Convert 100112 to decimal

• Decimal to binary conversion:

– Convert 4710 to binary

Chapter 1 <19>
 Number Conversion
• Binary to Decimal conversion:
– Convert 100112 to decimal
– 16×1 + 8×0 + 4×0 + 2×1 + 1×1 = 1910

• Decimal to binary conversion:

– Convert 4710 to binary
– 32×1 + 16×0 + 8×1 + 4×1 + 2×1 + 1×1 = 1011112

- Or use long division method by repeated division on base = 2

as in the following slide

Chapter 1 <20>
 Decimal to Binary Conversion
Repeated
Division

Divide the decimal

number by 2.
Write the remainder
after each division
until a quotient of
zero is obtained.
The first remainder
is the LSB.
The last is the
MSB.

Chapter 1 <21>
 Binary Values and Range
• N-digit decimal number
– How many values?
– Range?
– Example: 3-digit decimal number: 000 ….999

• N-bit binary number

– How many values?
– Range:
– Example: 3-digit binary number:000….111

Chapter 1 <22>
 Binary Values and Range
• N-digit decimal number
– How many values? 10N
– Range? [0, 10N - 1]
– Example: 3-digit decimal number:
• 103 = 1000 possible values
• Range: [0, 999]

– N-bit binary number ----- = 2N -1

– How many values? 2N

– Range: [0, 2N - 1]
– Example: 3-digit binary number:
• 23 = 8 possible values
• Range: [0, 7] = [0002 to 1112]

Chapter 1 <23>
Hexadecimal Numbers
Hex Digit Decimal Equivalent Binary Equivalent
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
A 10
B 11
C 12
D 13
E 14
F 15

Chapter 1 <24>
Hexadecimal Numbers
Hex Digit Decimal Equivalent Binary Equivalent
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
A 10 1010
B 11 1011
C 12 1100
D 13 1101
E 14 1110
F 15 1111

Chapter 1 <25>
 Hexadecimal Numbers
• Base 16
• Shorthand for binary
• 1100  C
• 10001100  8C

Chapter 1 <26>
 Hexadecimal to Binary Conversion
• Hexadecimal to binary conversion:
– Convert 4AF16 (also written 0x4AF) to binary

• Hexadecimal to decimal conversion:

– Convert 0x4AF to decimal

Chapter 1 <27>
 Hexadecimal to Binary Conversion
• Hexadecimal to binary conversion:
– Convert 4AF16 (also written 0x4AF) to binary
– 0100 1010 11112

• Hexadecimal to decimal conversion:

– Convert 4AF16 to decimal
– 162×4 + 161×10 + 160×15 = 119910

Chapter 1 <28>
Bits, Bytes, Nibbles…
• Bits 10010110
most least
significant significant
bit bit

• Bytes & Nibbles

byte

10010110
nibble

• Bytes CEBF9AD7
most least
significant significant
byte byte

Chapter 1 <29>
Large Powers of Two
• 210 = 1 kilo ≈ 1000 (1024)
• 220 = 1 mega ≈ 1 million (1,048,576)

• 230 = 1 giga ≈ 1 billion (1,073,741,824)

Chapter 1 <30>
Estimating Powers of Two
• What is the value of 224?

• How many values can a 32-bit variable

represent?

Chapter 1 <31>
Estimating Powers of Two
• What is the value of 224?
24 × 220 ≈ 16 million

• How many values can a 32-bit variable

represent?
22 × 230 ≈ 4 billion

Chapter 1 <32>
 Addition
• Decimal
3734
+ 5168

• Binary
1011
+ 0011

Chapter 1 <33>
 Addition
• Decimal 11 carries
3734
+ 5168 0.. 9, 10 …..99, 100….. 999
8902

• Binary 11 carries
1011
+ 0011 0 , 1 , 10 , 11 , 100

1110

Chapter 1 <34>
 Binary Addition Examples
• Add the following
1001
4-bit binary
+ 0101
numbers

• Add the following 1011

4-bit binary + 0110
numbers

Chapter 1 <35>
 Binary Addition Examples
• Add the following 1
1001
4-bit binary
+ 0101
numbers
1110

111
• Add the following 1011
4-bit binary + 0110
numbers 10001
Overflow!
Chapter 1 <36>
 Overflow
• Digital systems operate on a fixed number of
bits
• Overflow: when result is too big to fit in the
available number of bits
• See previous example of 11 + 6

Chapter 1 <37>
 Signed Binary Numbers
• Sign/Magnitude Numbers
• Two’s Complement Numbers

• 4 , -4
• 17, -56

Chapter 1 <38>
 Sign/Magnitude Numbers
• 1 sign bit, N-1 magnitude bits
• Sign bit is the most significant (left-most) bit
– Positive number: sign bit = 0
A : aN 1 , a N 2 , a2 , a1 , a0 
– Negative number: sign bit = 1
n 2
A  ( 1)an 1  ai 2i
i 0
• Example, 4-bit sign/mag representations of ± 6:
+6 =
-6=

• Range of an N-bit sign/magnitude number:

0 1 0 0 1 1 1 1 0 0

Chapter 1 <39>
 Sign/Magnitude Numbers
• 1 sign bit, N-1 magnitude bits
• Sign bit is the most significant (left-most) bit
– Positive number: sign bit = 0 A : a N 1 , a N 2 , a2 , a1 , a0 
– Negative number: sign bit = 1 n 2
A  ( 1)
a n 1
i
a 2
i 0
i

• Example, 4-bit sign/mag representations of ± 6:

+6 = 0 110
- 6 = 1 110

• Range of an N-bit sign/magnitude number:

[-(2N-1-1), 2N-1-1]

Chapter 1 <40>
 Sign/Magnitude Numbers
• Problems:
– Addition doesn’t work, for example -6 + 6:
1110
+ 0110
10100 (wrong!)

– Two representations of 0 (± 0):

1 000
0 000
Chapter 1 <41>
 Two’s Complement Numbers
• Don’t have same problems as sign/magnitude
numbers:
– Addition works
– Single representation for 0

– -6  110 -> 010

– -6 in eight bits  00000110  11111010

Chapter 1 <42>
 Two’s Complement Numbers
+6 = 110 -6 = 110 -> 001-> 010
1

• Msb has value of -2N-1 n 2

A  an 1  2n 1    ai 2i
i 0

• Most positive 4-bit number:

• Most negative 4-bit number:
• The most significant bit still indicates the sign
(1 = negative, 0 = positive)
• Range of an N-bit two’s comp number:
Chapter 1 <43>
 Two’s Complement Numbers
• Msb has value of -2N-1
n 2
A  an 1  2n 1    ai 2i
i 0

• Most positive 4-bit number: 0111

• Most negative 4-bit number: 1000
• The most significant bit still indicates the sign
(1 = negative, 0 = positive)
• Range of an N-bit two’s comp number:
[-(2N-1), 2N-1-1]
Chapter 1 <44>
 “Taking the Two’s Complement”
• Flip the sign of a two’s complement number
• Method:
1. Invert the bits
2. Add 1
• Example: Flip the sign of 310 = 00112

Chapter 1 <45>
 “Taking the Two’s Complement”
• Flip the sign of a two’s complement number
• Method:
1. Invert the bits
2. Add 1
• Example: Flip the sign of 310 = 00112
1. 1100
2. + 1
1101 = -310

Chapter 1 <46>
 Two’s Complement Examples
• Take the two’s complement of 610 = 01102

• What is the decimal value of 10012?

Chapter 1 <47>
 Two’s Complement Examples
• Take the two’s complement of 610 = 01102
1. 1001
2. + 1
10102 = -610

• What is the decimal value of the two’s

complement number 10012?
1. 0110
2. + 1
01112 = 710, so 10012 = -710

Chapter 1 <48>
 Two’s Complement Addition
• Add 6 + (-6) using two’s complement
numbers
0110
+ 1010

• Add -2 + 3 using two’s complement numbers

1110
+ 0011

Chapter 1 <49>
 Two’s Complement Addition
• Add 6 + (-6) using two’s complement
numbers 111
0110
+ 1010
10000
• Add -2 + 3 using two’s complement numbers
111
1110
+ 0011
10001
Chapter 1 <50>
 Increasing Bit Width
• Extend number from N to M bits (M > N) :
– Sign-extension
– Zero-extension

11110010

0 0 1 1 1 1 0 0 1 0

Copyright © 2012 Elsevier

Chapter 1 <51>
 Sign-Extension
• Sign bit copied to msb’s
• Number value is same

• Example 1:
– 4-bit representation of 3 = 0011
– 8-bit sign-extended value: 00000011
• Example 2:
– 4-bit representation of -5 = 1011
– 8-bit sign-extended value: 11111011

Chapter 1 <52>
 Zero-Extension
• Zeros copied to msb’s
• Value changes for negative numbers

• Example 1:
– 4-bit value = 00112 = 310
– 8-bit zero-extended value: 00000011 = 310
• Example 2:
– 4-bit value = 1011 = -510
– 8-bit zero-extended value: 00001011 = 1110

Chapter 1 <53>
 Number System Comparison
Number System Range
Unsigned [0, 2N-1]
Sign/Magnitude [-(2N-1-1), 2N-1-1]
Two’s Complement [-2N-1, 2N-1-1]

For example, 4-bit representation:

-8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Unsigned 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 Two's Complement

0000
1111 1110 1101 1100 1011 1010 1001
1000
0001 0010 0011 0100 0101 0110 0111 Sign/Magnitude

Chapter 1 <54>
 Logic Gates

• Perform logic functions:

– inversion (NOT), AND, OR, NAND, NOR, etc.
• Single-input:
– NOT gate, buffer
• Two-input:
– AND, OR, XOR, NAND, NOR, XNOR
• Multiple-input

Chapter 1 <55>
Single-Input Logic Gates

NOT BUF
A Y A Y

Y=A Y=A

A Y A Y
0 0
1 1

Chapter 1 <56>
Single-Input Logic Gates

NOT BUF
A Y A Y

Y=A Y=A

A Y A Y
0 1 0 0
1 0 1 1

Chapter 1 <57>
Two-Input Logic Gates

AND OR
A A
Y Y
B B

Y = AB Y=A+B

A B Y A B Y
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1

Chapter 1 <58>
Two-Input Logic Gates

AND OR
A A
Y Y
B B

Y = AB Y=A+B

A B Y A B Y
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1

Chapter 1 <59>
More Two-Input Logic Gates

XOR NAND NOR XNOR

A A A A
Y Y Y Y
B B B B

Y=A+B Y = AB Y=A+B Y=A+B

A B Y A B Y A B Y A B Y
0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1

Chapter 1 <60>
More Two-Input Logic Gates

XOR NAND NOR XNOR

A A A A
Y Y Y Y
B B B B

Y=A+B Y = AB Y=A+B Y=A+B

A B Y A B Y A B Y A B Y
0 0 0 0 0 1 0 0 1 0 0 1
0 1 1 0 1 1 0 1 0 0 1 0
1 0 1 1 0 1 1 0 0 1 0 0
1 1 0 1 1 0 1 1 0 1 1 1

Chapter 1 <61>
Multiple-Input Logic Gates
NOR3 AND3
A A
B Y B
C
Y
C
Y = A+B+C Y = ABC

A B C Y A B C Y
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 0
1 1 1 1 1 1

Chapter 1 <62>
Multiple-Input Logic Gates
NOR3 AND3
A A
B Y B
C
Y
C
Y = A+B+C Y = ABC

A B C Y A B C Y
0 0 0 1 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 0 0 1 1 0
1 0 0 0 1 0 0 0
1 0 1 0 1 0 1 0
1 1 0 0 1 1 0 0
1 1 1 0 1 1 1 1

• Multi-input XOR: Odd parity

Chapter 1 <63>
 Logic Levels
• Discrete voltages represent 1 and 0
• For example:
– 0 = ground (GND) or 0 volts
– 1 = VDD or 5 volts
• What about 4.99 volts? Is that a 0 or a 1?
• What about 3.2 volts?

Chapter 1 <64>
 Logic Levels
• Range of voltages for 1 and 0
• Different ranges for inputs and outputs to
allow for noise

Chapter 1 <65>
 What is Noise?
• Anything that degrades the signal
– E.g., resistance, power supply noise, coupling
to neighboring wires, etc.
• Example: a gate (driver) outputs 5 V but,
because of resistance in a long wire,
receiver gets 4.5 V
Noise
Driver Receiver

5V 4.5 V

Chapter 1 <66>
 The Static Discipline
• With logically valid inputs, every circuit
element must produce logically valid
outputs

• Use limited ranges of voltages to

represent discrete values

Chapter 1 <67>
Logic Levels
Driver Receiver

Output Characteristics Input Characteristics

VDD
Logic High
Output Range Logic High
VO H Input Range
NMH
Forbidden VIH
Zone VIL
VO L NML
Logic Low
Logic Low Input Range
Output Range
GND

Chapter 1 <68>
 Noise Margins
Driver Receiver

Output Characteristics Input Characteristics

VDD
Logic High
Output Range Logic High
VO H Input Range
NMH
Forbidden VIH
Zone VIL
VO L NML
Logic Low
Logic Low Input Range
Output Range
GND

NMH = VOH – VIH

NML = VIL – VOL
Chapter 1 <69>
 4.1 v
Driver Receiver

NMH = 0.6 v NML =0.7 VOH= 4.9v

VIH = 4.9 – 0.6= 4.3 v

NMH = VOH – VIH

NML = VIL – VOL
Chapter 1 <70>
 DC Transfer Characteristics
Ideal Buffer: Real Buffer:
V(Y) V(Y)
A Y

VOH VDD VDD

VOH

Unity Gain
Points
VOL Slope = 1

VOL 0 V(A) V(A)

0
VDD / 2 VDD VIL VIH VDD
VIL, VIH

NMH = NML = VDD/2 NMH , NML < VDD/2

Chapter 1 <71>
 DC Transfer Characteristics
A Y

V(Y)
Output Characteristics Input Characteristics
VDD VDD
VOH
VO H
NMH
Forbidden VIH
Zone VIL

Unity Gain NML

Points VO L
VOL Slope = 1

V(A)
0
VIL VIH VDD GND

Chapter 1 <72>
 VDD Scaling
• In 1970’s and 1980’s, VDD = 5 V
• VDD has dropped
– Avoid frying tiny transistors
– Save power
• 3.3 V, 2.5 V, 1.8 V, 1.5 V, 1.2 V, 1.0 V, …
• Be careful connecting chips with
different supply voltages

Chips operate because they contain magic

smoke
Proof:
– if the magic smoke is let out, the chip
stops working

Chapter 1 <73>
Logic Family Examples

Logic Family VDD VIL VIH VOL VOH

TTL 5 (4.75 - 5.25) 0.8 2.0 0.4 2.4

CMOS 5 (4.5 - 6) 1.35 3.15 0.33 3.84

LVTTL 3.3 (3 - 3.6) 0.8 2.0 0.4 2.4

LVCMOS 3.3 (3 - 3.6) 0.9 1.8 0.36 2.7

Chapter 1 <74>