Transcript Bild 1 - miun.se

MICROPROCESSOR
SYSTEM DESIGN
LECTURE 2
Muhammad Amir Yousaf
1
oVon-Neumann Architecture
oInstruction execution in Von Neumann Architecture
oVon Neumann Architecture’s limitation
oHarvard Architecture
oData Representation in computer
Muhammad Amir Yousaf
2
VON NEUMANN
ARCHITECTURE
Von Neumann, a mathematician and early
computer scientist described a design architecture
for electronic digital computer.
He was the first to spell out the requirements for a general purpose
electronic computer.
‘
The architecture is still alive in the basis of modern computers
Muhammad Amir Yousaf
3
VON NEUMANN
ARCHITECTURE
To Von Neumann, the key to building a general purpose
device was in its ability to store the instructions (along with
data and temporary results) in it.
In a special purpose machine the computational procedure
could be part of the hardware.
In General purpose computers instructions must be
changeable.
Instruction are encoded into numeric form and stored in
memory
Muhammad Amir Yousaf
4
VON NEUMANN
ARCHITECTURE
Major organs of Von Neumann architecture:
Memory
o The arithmetic logic unit
o The control unit
o The memory
o The input-output devices
Control
Unit
ALU
Input / Output
Muhammad Amir Yousaf
5
VON NEUMANN
ARCHITECTURE
Von Neumann general purpose computer is a programmable
machine that:
o Store a set of coded instruction along with data in its memory.
o Respond to instructions in a well defined manner(sequential or
told otherwise).
o Set of instruction is called program.
o Memory can be loaded with new programs.
Muhammad Amir Yousaf
6
INSTRUCTION
An instruction is a binary coded command to perform a specific
task:
o Arithmetic and Logic Instruction.
o Looping and decision making.
o Transfer of data.
o Transfer of control.
Muhammad Amir Yousaf
7
EXECUTION OF
INSTRUCTION
Instruction execution in Von Neumann computer
oGet the coded instruction.
oDecode the instruction.
oGet the operand.
oPerform the desired operation.
oCommunicate the results back.
Muhammad Amir Yousaf
8
COMPONENTS OF VON
NEUMANN COMPUTER
o Memory: to store program and data.
oInstruction Decoder: to decode the
binary coded instructions.
o Program Counter: to execute
instructions in order.
oArithmetic Logic Unit: to perform logical
and arithmetic operations.
Instruction
Decoder
Program counter
RAM
Input /
Outputs
ALU
oInputs/Outputs: to give the results back
oRegisters: Temporary data storage
Muhammad Amir Yousaf
9
INSTRUCTION FORMAT
Instruction
Muhammad Amir Yousaf
10
Von Neumann Architechture
CPU
Execution unit
Memory
ALU
Both data and instructions
at the same system bus
Registers
BU
IR
PC
IO units
Controller
Control unit
System bus
Execution unit
The number of bits in the execution unit
usually denotes the processor’s size
For example an 8-bit processor stores 8-bits in registers and
performs 8-bit operations in the ALU.
The execution unit
comprise:
- ALU
Aritmethic Logic Unit
Performs arithmetic (+-*/)
and logical calculations
- Registers
Intermediate storing of
results
Processor
Execution unit
ALU
Registers
BU
IR
PC
Controller
Controller unit
2N is the number of
adressable
memory positions
Bus unit
Processor
Execution unit
Address (N-1:0)
Data (M-1:0)
ALU
Registers
Control
BU
IR
Request
Acknowlege
Read/Write
Etc.
PC
System bus
Unique signals for
each processor bus
Controller
Control unit
Control unit, Registers
Processor
The control unit comprise of:
Execution unit
- IR, the instruction register
stores the instruction that
is executed
- PC, the program counter
stores the adress to
the executing instruction
- Controller, controls the other
parts (registers, bus unit
och execution unit
ALU
Registers
BE
IR
PC
Controller
Control unit
Instruction execution
Data ($73) from memory,
equalizes the instruction ADD
Memory
ADD $23,reg1
Execution unit
10: $73 (ADD $23,reg1)
…
23: $55
Set the address bus to 10,
the control bus to read
ALU
Registers
BU
IR:73
PC: 10
IO units
Read data from
address 10
Fetch instruction
Processor
Controller
Control unit
ADD $23,REG1
Processor
Execution unit
Memory
10: $73 (ADD $23,reg1)
…
23: $55
ADD $23,reg1 is
the instruction that
is to be executed
IO units
ALU
BU
Registers
Decode the machine code
73 to an instruction
IR: 73
PC: 10
Controller
ADD $23,reg1
Instruction decoder
Control unit
Fetch instr.
Decode instr.
$73
ADD $23,REG1
Value from reg1
Processor
Data ($55) from memory
Execution unit
Memory
10: $73 (ADD $23,reg1)
…
23: $55
ALU
BU
Set the address bus to $23,
the control bus to read
IO units
IR
PC: 10
Read data from
address $23
Fetch instr.
Decode instr.
Registers
Fetch operand
Controller
Control unit
ADD $23,reg1
The content in memory position
($23)=55 is added with the
content in reg1: reg1 +$55
Processor
ADD $23,REG1
Exekveringsenhet
Memory
10: $73 (ADD $23,reg1)
…
23: $55
ALU
Registers
BU
IR
PC: 10
IO units
Add reg1 and
value from memory
Fetch instr.
Decode instr.
Fetch operand
Controller
Control unit
Execute
The result of the addition
is written to register reg1
reg1 +$55 => reg1
Processor
ADD $23,REG1
Exececution unit
Memory
10: $73 (ADD $23,reg1)
…
23: $55
ALU
Registers
BU
IR
PC: 10
IO units
Save the result in
register reg1
Fetch instr.
Decode instr.
Fetch operand
Controller
Control unit
Execute
Write result
EXECUTION IN I FIVE STAGES
Processor
Execution unit
Memory
10: $73 (ADD $23,reg1)
…
23: $55
ALU
Registers
BU
IR
PC: 10
IO units
Controller
Control unit
Fetch instr.
Decode instr.
Fetch operand
Execute
Write result
VON NEUMANN LIMITATION
The shared bus between the program memory and data memory
leads to the Von Neumann bottleneck.
 Because program memory and data memory cannot be accessed
at the same time, throughput is much smaller than the rate at which
the CPU can work.
The CPU is continuously forced to wait for needed data to be
transferred to or from memory.
For example if we try to read an operand at the same time as we
try to read an instruction. This is not possible in the von Neumann
architecture since we only have one system bus and cannot
address two memory positions simultaneously.
Muhammad Amir Yousaf
21
Other Architectures
HARVARD ARCHITECTURE
In the Harvard architecture this is
solved by having two separate
system buses:
oOne for instructions
oOne for data
oData and instructions can be
loaded simultaneously, which
improves the efficiency.
Program
Memory
Program system Bus
CPU
Computer
Memory
Data system Bus
Means more I/O signals.
oMore expensive processor.
oUses more power.
Is used internally in modern 32-bit
microprocessors and RISC
processors.
Muhammad Amir Yousaf
22
IOs
Components in a microprocessor system
PROCESSOR TYPES:
CISC (Complex Instruction Set Computer)
oMany instructions to facilitate for assembler programmers and
complier constructors.
oThe drawback is that the compiler uses just a few instructions
and the construction of a complex processor becomes slow.
oIt takes a lot of information to describe an instruction.
oFor example, MC68040 with 200 instructions and 18 modes of
addressing.
oAssembler: Different instructions are executed with different
speed.
Muhammad Amir Yousaf
23
Components in a microprocessor system
REDUCED INSTRUCTION
SET COMPUTING
RISC (Reduced Instruction Set Computer)
o Simpler instructions (that is used by the compiler).
o Gives a faster implementation.
o Only one code word to describe an instruction.
o For example, Alpha, ARM, PIC, PowerPC, AVR….
o Assembler: All instructions take 1 clock cycle.
Muhammad Amir Yousaf
24
Components in a microprocessor system
MEMORY:
 To store data or instructions
the computer system uses a socalled primary memory
The executable program code
and data is stored in main
memory.
The primary memory is divided
in two main parts
The memory can be seen as a
number of post boxes
o RAM
o ROM
Muhammad Amir Yousaf
25
Von Neumann Architecture
MICROCONTROLLERS
What does a computer system
comprise:
oProcessor (CPU, Central Processing
Unit)
oMemory
oPeripheral units, I/O
oSystem bus, to communicate with
peripheral units
If we have a chip that comprise all this it
is often called a ‘Micro Controller’
Muhammad Amir Yousaf
Primary Memory
RAM
CPU
ROM
I/O unit
The outer world/ The user
26
Components in a microprocessor system
PROCESSOR SYSTEM BUS
 Data bus
oCommunication channel to move data to and from CPU and
peripheral units.
 Address bus
oUsed to point out which memory position or IO port that is to
be read or written.
 Control signals
o Used to signal when a data
transaction starts and stops.
o For example signals if a
transaction is a read or write
operation.
Muhammad Amir Yousaf
27
DATA REPRESENTATION
28
DATA TYPES
NUMBERS
Integers
oUnsigned
oSigned
Real data types
oFixed-Point
oFloating-Point
Binary-Coded Decimal
TEXT
oASCII Characters
oStrings
OTHERS
oGraphics
oImages
oVideo
oAudio
29
NUMBERS ARE DIFFERENT!
 Computers use binary (not decimal) numbers (0's and 1's).
 Requires more digits to represent the same magnitude.
 Computers store and process numbers using a fixed number
of digits (“fixed-precision”) after Radix point.
 Computers represent signed numbers using 2's complement
instead of sign-plus-magnitude (not our familiar “sign-plusmagnitude”).
30
POSITIONAL NUMBER
SYSTEMS
 Numeric values are represented by a sequence of digit
symbols.
 Symbols represent numeric values.
 Symbols are not limited to ‘0’-’9’!
 Each symbol’s contribution to the total value of the
number is weighted according to its position in the
sequence.
D
p 1

d i 10i
i 0
Integers numbers
D
p 1

d i 10i
i  n
Fractional numbers
31
POLYNOMIAL EVALUATION
 Whole Numbers (Radix = 10):
123410 = 1  103 + 2  102 + 3  101 + 4  100
 With Fractional Part (Radix = 10):
36.7210 = 3  101 + 6  100 + 7  10-1 + 2  10-2
 General Case (Radix = R):
(S1S0.S-1S-2)R =
S1  R1 + S0  R0 + S-1  R -1 + S-2  R-2
32
CONVERTING RADIX R TO
DECIMAL
EXAMPLE R = 8
36.728 = 3  81 + 6  80 + 7  8-1 + 2  8-2
=
24 + 6 + 0.875 + 0.03125
= 30.9062510
Important: Polynomial evaluation “doesn’t” work if
you try to convert in the other direction – I.e.,
from decimal to something else! Why?
33
BINARY TO DECIMAL
CONVERSION
Converting to decimal, so we can use polynomial
evaluation:
101101012 = 18510
= 127 + 026 + 125 + 124 + 023
+ 122 + 021 + 120
= 128 + 32 + 16 + 4 + 1
= 18510
34
DECIMAL TO BINARY
CONVERSION
 Converting to binary – can’t use polynomial
evaluation!
 Whole part and fractional parts must be handled
separately!
 Whole part: Use repeated division.
 Fractional part: Use repeated multiplication.
 Combine results when finished.
35
DECIMAL TO BINARY
CONVERSION
Whole part: Repeated Division
 Divide by target radix (2 in this case)
 Remainders become digits in the new representation
(0 <= digit < R)
 Digits produced in right to left order (LSB to MSB).
 Quotient is used as next dividend.
 Stop when the quotient becomes less than divisor, but
use the corresponding remainder.
36
DECIMAL TO BINARY
CONVERSION
Whole part: Repeated Division
Convert 9710 to a binary number
97  2 
48  2 
24  2 
12  2 
62
32
12
quotient = 48,
quotient = 24,
quotient = 12,
quotient = 6,
quotient = 3,
quotient = 1,
quotient = 0 (Stop)
remainder = 1 (LSB)
remainder = 0.
remainder = 0.
remainder = 0.
remainder = 0.
remainder = 1.
remainder = 1 (MSB)
Result = 1 1 0 0 0 0 12
37
DECIMAL TO BINARY
CONVERSION
Fractional Part: Repeated Multiplication
 Multiply by target radix (2 in this case)
 Whole part of product becomes digit in the new
representation (0 <= digit < R)
 Digits produced in left to right order (MSB to LSB)
 Fractional part of product is used as next multiplicand.
 Stop when the fractional part becomes zero (sometimes
it won’t)
38
DECIMAL TO BINARY
CONVERSION
(Fractional Part: Repeated Multiplication)
Convert 0.110 to a binary number
.1  2  0.2 (fractional part = .2, whole part = 0)
.2  2  0.4 (fractional part = .4, whole part = 0)
.4  2  0.8 (fractional part = .8, whole part = 0)
.8  2  1.6 (fractional part = .6, whole part = 1)
.6  2  1.2 (fractional part = .2, whole part = 1)
Result = .000110011001100112…..
(How much should we keep?)
Some fractional
numbers have an exact
representation in one
number system, but
not in another!
E.g., 1/3rd has no exact
representation in
decimal, but does in
base 3!
39
COUNTING
Principle is the same regardless of radix.
 Add 1 to the least significant digit.
 If the result is less than R, write it down and copy
all the remaining digits on the left.
 Otherwise, write down zero and add 1 to the next
digit position, etc.
Add 1 to next digit
Copy digits to the left
123
+ 1
124
3+1<10
129
+ 1
130
9+1=10
Write down zero in first position
40
COUNTING IN BINARY
Dec
0
1
2
3
4
5
6
7
Binary
0000
0001
0010
0011
0100
0101
0110
0111
Note the pattern!
 LSB (bit 0) toggles on every count.
 Bit 1 toggles on every second count.
 Bit 2 toggles on every fourth count.
 Etc….
41
QUESTION:
Do you trust the used car salesman that tells you
that the 1966 Mustang he wants to sell you has only
the 13,000 miles that it’s odometer shows?
If not, what has happened?
Why?
42
REPRESENTATION ROLLOVER





Rollover is a consequence of fixed precision.
Computers use fixed precision!
Digits are lost on the left-hand end.
Remaining digits are still correct.
Rollover while counting . . .
Up: “999999”  “000000” (Rn-1  0)
Down: “000000”  “999999” (0  Rn-1 )
The old MUSTANG has probably been running 113,000 miles
43
ROLLOVER IN UNSIGNED
BINARY
 Consider 8 bits used to represent an unsigned
integer:
 Range: 00000000  11111111 (0  25510)
 Incrementing a value of 255 should yield 256, but this
exceeds the range.
 Decrementing a value of 0 should yield –1, but this
exceeds the range.
 Exceeding the range is known as overflow.
44
ROLLOVER IS NOT SYNONYMOUS
WITH OVERFLOW!
 Rollover describes a pattern sequence.
 Overflow describes an arithmetic behavior.
 Whether or not rollover causes overflow depends on
how the patterns are interpreted as numeric values!
 E.g., In signed two’s complement representation, 11111111
00000000 corresponds to counting from minus one to
zero.
• This is rollover, but not overflow
 E.g., In signed two’s complement representation, 01111111
10000000 corresponds to counting from 127 to minus 128
• This is overflow, but not rollover
45
HEXADECIMAL NUMBERS
(RADIX = 16)
 The number of digit symbols is determined by the radix (e.g., 16)
 The value of the digit symbols range from 0 to 15 (0 to R-1).
 The symbols are 0-9 followed by A-F.
 Conversion between binary and hex is trivial!
 Use as a shorthand for binary (significantly fewer digits are
required for same magnitude).
 Hexadecimal numbers are sometimes indicated using $, e.g.
$00FF, or with an index H, e.g. 00FFH
 In program languages such as C, the representation 0x is used to
indicate a hexadecimal numeric constants and \x may be used for
character and string constants.
46
MEMORIZE THIS!
Hex
Binary
Hex
Binary
0
0000
8
1000
1
0001
9
1001
2
0010
A
1010
3
0011
B
1011
4
0100
C
1100
5
0101
D
1101
6
0110
E
1110
7
0111
F
1111
47
BINARY TO HEX CONVERSIONS
 Hex digits are in one-to-one correspondence with groups of
four binary digits:
0011 1010 0101 0110 . 1110 0010 1111 1000
3
A
5
6
.
E
2
F
8

Conversion is a simple table lookup!

Zero-fill on left and right ends to complete the groups!

Works because 16 = 24 (power relationship)
48
INTERPRETATIONS OF
NUMBERS
 Signed vs. unsigned is a matter of interpretation; thus
a single bit pattern can represent two different values.
 Do we need both interpretations?
 Why aren't all numbers represented as signed?
 Some data (e.g., count, age) can never be negative, and
having a greater range is useful.
16710
unsigned
signed
-8910
101001112
49
WHICH IS GREATER: 1001
OR 0011?
Answer: It depends!
So how does the computer decide:
“if (x > y)..”
/* Is this true or false? */
It’s a matter of interpretation, and depends on how x and y
were declared: signed? Or unsigned?
In C/C++ the compiler decides which instruction to use
depending on the declaration of the integer.
In assembly language, it is the programmers responsibility to
chose the correct instruction.
50
SIGNED NUMBER
REPRESENTATION
 Sign and Magnitude.
 First approach was to allocate the MSB to represent sign i.e. 0 for
positive and 1 for negative. The remaining bits indicate the magnitude.
 Two representations for zero i.e. 00000000 and 10000000.
 Range -127 to 127 for 8 bits.
 1’s compliment.
 Bitwise NOT applied to number — the "complement" of its positive
counterpart.
 Two representations for zero i.e. 00000000 and 11111111.
 Range -127 to 127 for 8 bits.
 Addition can be performed as conventional binary addition with adding
back resulting carry to the resulting sum e.g. add -1 and +2.
51
SIGNED NUMBER
REPRESENTATION
 2’s Compliment.
 Multiple representation of zero and need for taking the carry back made
place for the development of another representation system.
 2’s compliment of a number is achieved by inverting all bits and add 1 to
the result.
 Only one zero representation i.e. 00000000.
 Range is -128 to 127.
 Addition of 2’c compliment numbers are same as addition of unsigned
numbers.
 Overflow need to be detected.
52
WHY NOT SIGN + MAGNITUDE?
The sign is indicated with the most significant bit.
A ‘1’ indicates a negative number and a ‘0’ in the
MSB bit is indicating a positive number.
Complicates addition :
 To add, first check the signs. If they agree, then add
the magnitudes and use the same sign; else subtract
the smaller from the larger and use the sign of the
larger.
 How do you determine which is smaller/larger?
Complicates comparators:
 Two zeroes!
+3
0011
+2
0010
+1
0001
+0
0000
-0
1000
-1
1001
-2
1010
-3
1011
53
WHY NOT SIGN + MAGNITUDE?
9
1001
3
+
1
Right!
2
-1
+3
0011
Hardware
Adder
+
Wrong!
-4
1100
54
WHY 2’S COMPLEMENT?
 Just as easy to determine sign as when bits
are representing in sign + magnitude.
 Addition can be performed without worrying
about which operand is larger.
+3
0011
+2
0010
+1
0001
0
0000
-1
1111
-2
1110
-3
1101
-4
1100
 A single zero!.
 One hardware adder works for both signed
and unsigned operands.
55
ONE HARDWARE ADDER SHOULD
HANDLE BOTH (SIGNED AND UNSIGNED)
1001
9
0011
3
+
1
2
-7
+3
Hardware
Adder
Manipulates bit
patterns, not
numbers!
+
-4
1100
56
CHANGING THE SIGN
Sign+Magnitude:
+4 = 0100
2’s Complement:
+4 = 0100
Change 1 bit
-4 = 1100
Invert
+4 = 1011
Increment
+1
-4 = 1100
57
REPRESENTATION WIDTH
Be Careful!
For the algorithm to work you need to use the complete
representation
Wrong: +25 = 11001  00111  00000111 = +7
Right: +25 = 11001  00011001  11100111 = -25
Expand to 8-bits
+25 = 11001=00011001
If positive: Add leading 0’s
If negative: Add leading 1’s
Apply algorithm
58
SUBTRACTION IS EASY!
B=0100=4
A
Just a bunch of
exclusive-OR
gates!
Controlled
Inverter
B XOR Ctrl
B = 0100 if C=0
B = 1011 if C=1
Adder
A+(B + Ctrl)
Result
B = 0100 if C=0
B = 1100=-B if C=1
Ctrl
0 = add (A+B)
1 = sub (A-B)
X Y X xor Y
0 0 0
0 1 1
1 0 1
1 1 0
59
RANGE OF UNSIGNED INTEGERS
Each of ‘n’ bits can have one of two values.
Total # of patterns of n bits = 2 2 2… 2
=>‘n’ 2’s
=> 2n
If n-bits are used to represent an unsigned integer
value:
Range: 0 to 2n-1 (2n different values)
60
RANGE OF SIGNED INTEGERS
 Half of the 2n patterns will be used for positive
values, and half for negative.
 Half is 2n-1 since each position has a value which is
two times higher than the position to the right.
 Positive Range: 0 to 2n-1-1 (2n-1 patterns)
 Negative Range: -2n-1 to -1 (2n-1 patterns)
 8 bits (n = 8): -27 (-128) to +27-1 (+127)
61
UNSIGNED OVERFLOW
1100
+0111
10011
(12)
( 7)
Value of lost bit is 2n (16).
LOST
16 + 3 = 19
(The right answer!)
0011
( 3) WRONG
(Result limited by word size)
We only have four bits
62
SIGNED OVERFLOW
 Overflow is impossible  when adding
(subtracting) numbers that have different (same)
signs.
 Overflow occurs when the magnitude of the result
extends into the sign bit position:
01111111  (0)10000000
This is not rollover!
Rollover occur in the middle of the range for 2-comp
63
SIGNED OVERFLOW
-12010
-1710
sum: -13710

100010002
+111011112
1011101112
011101112 (keep 8 bits)
(+11910) wrong
Note: 119 – 28 = 119 – 256 = -137
64
REFERENCES
Lecture slides: Benny Thörnberg, Mattias O’ Nils
Video Lecture: Prof. Anshul Kumar
http://www.computersciencelab.com/ComputerHistory/History.htm
Webopedia
http://www.csupomona.edu/~hnriley/www/VonN.html
Muhammad Amir Yousaf
65