Chapter 1.

Basic
Structure of Computers
Functional Units
Functional Units
Arithmetic
Input and
logic

Memory

Output Control

I/O Processor

Figure 1.1. Basic functional units of a computer.

Information Handled by a
Computer
 Instructions/machine instructions
 Govern the transfer of information within a computer as
well as between the computer and its I/O devices
 Specify the arithmetic and logic operations to be
performed
 Program
 Data
 Used as operands by the instructions
 Source program
 Encoded in binary code – 0 and 1
Memory Unit
 Store programs and data
 Two classes of storage
 Primary storage
 Fast
 Programs must be stored in memory while they are being executed
 Large number of semiconductor storage cells
 Processed in words
 Address
 RAM and memory access time
 Memory hierarchy – cache, main memory
 Secondary storage – larger and cheaper
Arithmetic and Logic Unit
(ALU)
 Most computer operations are executed in
ALU of the processor.
 Load the operands into memory – bring them
to the processor – perform operation in ALU
– store the result back to memory or retain in
the processor.
 Registers
 Fast control of ALU
Control Unit
 All computer operations are controlled by the control
unit.
 The timing signals that govern the I/O transfers are
also generated by the control unit.
 Control unit is usually distributed throughout the
machine instead of standing alone.
 Operations of a computer:
 Accept information in the form of programs and data through an
input unit and store it in the memory
 Fetch the information stored in the memory, under program control,
into an ALU, where the information is processed
 Output the processed information through an output unit
 Control all activities inside the machine through a control unit
Basic Operational
Concepts
Review
 Activity in a computer is governed by instructions.
 To perform a task, an appropriate program
consisting of a list of instructions is stored in the
memory.
 Individual instructions are brought from the memory
into the processor, which executes the specified
operations.
 Data to be used as operands are also stored in the
memory.
A Typical Instruction
 Add LOCA, R0
 Add the operand at memory location LOCA to the
operand in a register R0 in the processor.
 Place the sum into register R0.
 The original contents of LOCA are preserved.
 The original contents of R0 is overwritten.
 Instruction is fetched from the memory into the
processor – the operand at LOCA is fetched and
added to the contents of R0 – the resulting sum is
stored in register R0.
Separate Memory Access and
ALU Operation
 Load LOCA, R1
 Add R1, R0
 Whose contents will be overwritten?
Connection Between the
Processor and the Memory
Registers
 Instruction register (IR)
 Program counter (PC)
 General-purpose register (R0 – Rn-1)
 Memory address register (MAR)
 Memory data register (MDR)
Typical Operating Steps
 Programs reside in the memory through input
devices
 PC is set to point to the first instruction
 The contents of PC are transferred to MAR
 A Read signal is sent to the memory
 The first instruction is read out and loaded
into MDR
 The contents of MDR are transferred to IR
 Decode and execute the instruction
Typical Operating Steps
(Cont’)
 Get operands for ALU
 General-purpose register
 Memory (address to MAR – Read – MDR to ALU)
 Perform operation in ALU
 Store the result back
 To general-purpose register
 To memory (address to MAR, result to MDR – Write)
 During the execution, PC is
incremented to the next instruction
Interrupt
 Normal execution of programs may be preempted if
some device requires urgent servicing.
 The normal execution of the current program must
be interrupted – the device raises an interrupt
signal.
 Interrupt-service routine
 Current system information backup and restore (PC,
general-purpose registers, control information,
specific information)
Bus Structures
 There are many ways to connect different
parts inside a computer together.
 A group of lines that serves as a connecting
path for several devices is called a bus.
 Address/data/control
Bus Structure
 Single-bus
Speed Issue
 Different devices have different
transfer/operate speed.
 If the speed of bus is bounded by the slowest
device connected to it, the efficiency will be
very low.
 How to solve this?
 A common approach – use buffers.
Software
System Software
 System software is a collection of programs that are
executed as needed to perform functions such as-
 Receiving and interpreting user commands
 Entering and editing application programs and storing them
as files in secondary devices.
 Managing the storage and retrieval of files in secondary
storage devices.
 Running standard application programs such as word
processors, games with data supplied by the user.
 Controlling I/O units to receive input information and
produce output results.
 Translating programs from source form prepared by the
user into object form consisting of machine instructions.
 Linking and running user-written application programs with
existing standard library routines, such as numerical
computation packages.
Operating System(OS)
 It is a collection of routines, that is used to control the sharing of and
interaction among various computer units as they execute
application programs.

 OS routines perform tasks required to assign computer resources to

individual application programs.

 Tasks include assigning magnetic disk space to program and data

files, moving data between memory and disk units, and handling I/O
operations.
Performance
Performance
 The most important measure of a computer is
how quickly it can execute programs.
 Three factors affect performance:
 Hardware design
 Instruction set
 Compiler
Performance
 Processor time to execute a program depends on the hardware
involved in the execution of individual machine instructions.

Main Cache
memory memory Processor

Bus

Figure 1.5. The processor cache.

Performance
 The processor and a relatively small cache
memory can be fabricated on a single
integrated circuit chip.
 Speed
 Cost
 Memory management
Processor Clock
 Processor circuits are controlled by a timing signal
called a Clock.
 The clock defines regular time intervals, called clock
cycle.
 The execution of each instruction is divided into
several steps, each of which completes in one clock
cycle.
 The length P of one clock cycle affects processor
performance.
 The clock rate is inverse of P. i.e., R =1/P cycles per
second.
 Hertz – cycles per second
Basic Performance Equation
 T – processor time required to execute a program that has been
prepared in high-level language
 N – number of actual machine language instructions needed to
complete the execution (note: loop)
 S – average number of basic steps needed to execute one
machine instruction. Each step completes in one clock cycle
 R – clock rate
 Note: these are not independent to each other

N S
T
R
How to improve T?
Pipeline and Superscalar
Operation
 Instructions are not necessarily executed one after
another.
 The value of S doesn’t have to be the number of
clock cycles to execute one instruction.
 Pipelining – overlapping the execution of successive
instructions.
 Add R1, R2, R3
 Superscalar operation – multiple instruction
pipelines are implemented in the processor.
 Goal – reduce S (could become <1!)
Clock Rate
 Increase clock rate
 Improve the integrated-circuit (IC) technology to make
the circuits faster
 Reduce the amount of processing done in one basic step
(however, this may increase the number of basic steps
needed)
 Increases in R that are entirely caused by
improvements in IC technology affect all
aspects of the processor’s operation equally
except the time to access the main memory.
CISC and RISC
 Tradeoff between N and S
 A key consideration is the use of pipelining
 S is close to 1 even though the number of basic steps
per instruction may be considerably larger
 It is much easier to implement efficient pipelining in
processor with simple instruction sets
 Reduced Instruction Set Computers (RISC)
 Complex Instruction Set Computers (CISC)
Compiler
 A compiler translates a high-level language program
into a sequence of machine instructions.
 To reduce N, we need a suitable machine instruction
set and a compiler that makes good use of it.
 Goal – reduce N×S
 A compiler may not be designed for a specific
processor; however, a high-quality compiler is
usually designed for, and with, a specific processor.
Performance Measurement
 T is difficult to compute.
 Measure computer performance using benchmark programs.
 System Performance Evaluation Corporation (SPEC) selects and
publishes representative application programs for different application
domains, together with test results for many commercially available
computers.
 Compile and run (no simulation)
 Reference computer

Running time on the reference computer

SPEC rating 
Running time on the computer under test
n 1
SPEC rating  ( SPEC i ) n

i 1
Multiprocessors and
Multicomputers
 Multiprocessor computer
 Execute a number of different application tasks in parallel
 Execute subtasks of a single large task in parallel
 All processors have access to all of the memory – shared-memory
multiprocessor
 Cost – processors, memory units, complex interconnection networks
 Multicomputers
 Each computer only have access to its own memory
 Exchange message via a communication network – message-
passing multicomputers
Chapter 2. Machine
Instructions and
Programs
Objectives
 Machine instructions and program execution,
including branching and subroutine call and return
operations.
 Number representation and addition/subtraction in
the 2’s-complement system.
 Addressing methods for accessing register and
memory operands.
 Assembly language for representing machine
instructions, data, and programs.
 Program-controlled Input/Output operations.
Number, Arithmetic
Operations, and
Characters
Signed Integer
 3 major representations:
Sign and magnitude
One’s complement
Two’s complement
 Assumptions:
4-bit machine word
16 different values can be represented
Roughly half are positive, half are negative
Sign and Magnitude
Representation
-7 +0
-6 1111 0000 +1
1110 0001
-5 +2 +
1101 0010
-4 1100 0011 +3 0 100 = + 4

-3 1011 0100 +4 1 100 = - 4

1010 0101
-2 +5 -
1001 0110
-1 1000 0111 +6
-0 +7
High order bit is sign: 0 = positive (or zero), 1 = negative
Three low order bits is the magnitude: 0 (000) thru 7 (111)
Number range for n bits = +/-2n-1 -1
Two representations for 0
One’s Complement
Representation
-0 +0
-1 1111 0000 +1
1110 0001
-2 +2 +
1101 0010
-3 1100 0011 +3 0 100 = + 4

-4 1011 0100 +4 1 011 = - 4

1010 0101
-5 +5 -
1001 0110
-6 1000 0111 +6
-7 +7
 Subtraction implemented by addition & 1's complement
 Still two representations of 0! This causes some problems
 Some complexities in addition
Two’s Complement
Representation
-1 +0
-2 1111 0000 +1
1110 0001
-3 +2 +
like 1's comp 1101 0010
except shifted -4 1100 0011 +3 0 100 = + 4
one position
clockwise -5 1011 0100 +4 1 100 = - 4
1010 0101
-6 +5 -
1001 0110
-7 1000 0111 +6
-8 +7

 Only one representation for 0

 One more negative number than positive
number
Binary, Signed-Integer
Representations
B Values represented

Sign and
b 3 b 2 b1 b 0 magnitude 1' s complement 2' s complement

0 1 1 1 +7 +7 + 7
0 1 1 0 +6 +6 + 6
0 1 0 1 +5 +5 + 5
0 1 0 0 +4 +4 + 4
0 0 1 1 +3 +3 + 3
0 0 1 0 +2 +2 + 2
0 0 0 1 +1 +1 + 1
0 0 0 0 +0 +0 + 0
1 0 0 0 - 0 -7 - 8
1 0 0 1 - 1 -6 - 7
1 0 1 0 - 2 -5 - 6
1 0 1 1 - 3 -4 - 5
1 1 0 0 - 4 -3 - 4
1 1 0 1 - 5 -2 - 3
1 1 1 0 - 6 - 1 - 2
1 1 1 1 - 7 -0 - 1

Figure 2.1. Binary, signed-integer representations.

Addition and Subtraction – 2’s
Complement
4 0100 -4 1100
+3 0011 + (-3) 1101
If carry-in to the high
order bit = 7 0111 -7 11001
carry-out then ignore
carry

if carry-in differs from 4 0100 -4 1100

carry-out then overflow
-3 1101 +3 0011
1 10001 -1 1111

Simpler addition scheme makes twos complement the most common

choice for integer number systems within digital systems
2’s-Complement Add and
Subtract Operations
(a) 0010 ( + 2) (b) 0100 ( + 4)
+ 0011 ( + 3) + 1010 (- 6)
0101 ( + 5) 1110 (- 2)
(c) 1011 (- 5) (d) 0111 ( + 7)
+ 1110 (- 2) + 1101 ( - 3)
1001 (- 7) 0100 ( + 4)
(e) 1101 (- 3) 1101
- 1001 (- 7) + 0111
0100 ( + 4)
(f) 0010 ( + 2) 0010
- 0100 ( + 4) + 1100
1110 ( - 2)
(g) 0110 ( + 6) 0110
- 0011 ( + 3) + 1101
0011 ( + 3)
(h) 1001 ( - 7) 1001
- 1011 (- 5) + 0101
1110 ( - 2)
(i) 1001 (- 7) 1001
- 0001 ( + 1) + 1111
1000 ( - 8)
(j) 0010 ( + 2) 0010
- 1101 ( - 3) + 0011
0101 ( + 5)

Figure 2.4. 2's-complement Add and Subtract operations.

Overflow - Add two positive numbers to get a
negative number or two negative numbers to
get a positive number

-1 +0 -1 +0
-2 1111 0000 +1 -2 1111 0000 +1
1110 0001 1110 0001
-3 +2 -3
1101 1101 +2
0010 0010
-4 -4
1100 0011 +3 1100 0011 +3
-5 1011 -5 1011
0100 +4 0100 +4
1010 1010
-6 0101 -6 0101
1001
+5 +5
0110 1001 0110
-7 1000 0111 +6 -7 1000 +6
0111
-8 +7 -8 +7

5 + 3 = -8 -7 - 2 = +7
Overflow Conditions
0111 1000
5 0101 -7 1001
3 0011 -2 1100
-8 1000 7 10111
Overflow Overflow
0000 1111
5 0101 -3 1101
2 0010 -5 1011
7 0111 -8 11000
No overflow No overflow
Overflow when carry-in to the high-order bit does not equal carry out
Memory Locations,
Addresses, and
Operations
Memory Location, Addresses,
and Operation
n bits
first word
 Memory consists
second word
of many millions of
storage cells,
•
each of which can •
•
store 1 bit.
 Data is usually i th word
accessed in n-bit
groups. n is called •
word length. •
•

last word

Figure 2.5. Memory words.

Memory Location, Addresses,
and Operation
 32-bit word length example
32 bits

b31 b30 b1 b0

•
•
•
Sign bit: b31= 0 for positive numbers
b31= 1 for negative numbers

(a) A signed integer

8 bits 8 bits 8 bits 8 bits

ASCII ASCII ASCII ASCII

character character character character

(b) Four characters

Memory Location, Addresses,
and Operation
 To retrieve information from memory, either for one
word or one byte (8-bit), addresses for each location
are needed.
 A k-bit address memory has 2k memory locations,
namely 0 – 2k-1, called memory space.
 24-bit memory: 224 = 16,777,216 = 16M (1M=220)
 32-bit memory: 232 = 4G (1G=230)
 1K(kilo)=210
 1T(tera)=240
Memory Location, Addresses,
and Operation
 It is impractical to assign distinct addresses to
individual bit locations in the memory.
 The most practical assignment is to have
successive addresses refer to successive byte
locations in the memory – byte-addressable
memory.
 Byte locations have addresses 0, 1, 2, … If word
length is 32 bits, they successive words are
located at addresses 0, 4, 8,…
Big-Endian and Little-Endian
Assignments
Big-Endian: lower byte addresses are used for the most significant bytes of the word
Little-Endian: opposite ordering. lower byte addresses are used for the less significant
bytes of the word
Word
address Byte address Byte address

0 0 1 2 3 0 3 2 1 0

4 4 5 6 7 4 7 6 5 4

• •
• •
• •

k k k k k k k k k k
2 -4 2 -4 2 -3 2- 2 2 - 1 2 - 4 2- 1 2 - 2 2 -3 2 -4

(a) Big-endian assignment (b) Little-endian assignment

Figure 2.7. Byte and word addressing.

Memory Location, Addresses,
and Operation
 Address ordering of bytes: b7,b6...b0
 Word alignment
 Words are said to be aligned in memory if they
begin at a byte addr. that is a multiple of the num
of bytes in a word.
 16-bit word: word addresses: 0, 2, 4,….
 32-bit word: word addresses: 0, 4, 8,….
 64-bit word: word addresses: 0, 8,16,….
 Access numbers, characters, and character
strings
Memory Operation
 Load (or Read or Fetch)
 Copy the content. The memory content doesn’t change.
 Address – Load
 Registers can be used
 Store (or Write)
 Overwrite the content in memory
 Address and Data – Store
 Registers can be used
Instruction and
Instruction
Sequencing
“Must-Perform” Operations
 Data transfers between the memory and the
processor registers
 Arithmetic and logic operations on data
 Program sequencing and control
 I/O transfers
Register Transfer Notation
 Identify a location by a symbolic name
standing for its hardware binary address
(LOC, R0,…)
 Contents of a location are denoted by placing
square brackets around the name of the
location (R1←[LOC], R3 ←[R1]+[R2])
 Register Transfer Notation (RTN)
Assembly Language Notation
 Represent machine instructions and
programs.
 Move LOC, R1 = R1←[LOC]
 Add R1, R2, R3 = R3 ←[R1]+[R2]
CPU Organization
 Single Accumulator
 Result usually goes to the Accumulator
 Accumulator has to be saved to memory quite
often
 General Register
 Registers hold operands thus reduce memory
traffic
 Register bookkeeping
 Stack
 Operands and result are always in the stack
Instruction Formats
 Three-Address Instructions
 ADD R1, R2, R3 R1 ← R2 + R3
 Two-Address Instructions
 ADD R1, R2 R1 ← R1 + R2
 One-Address Instructions
 ADD M AC ← AC + M[AR]
 Zero-Address Instructions
 ADD TOS ← TOS + (TOS – 1)
 RISC Instructions
 Lots of registers. Memory is restricted to Load & Store

Opcode Operand(s) or Address(es)

Instruction Formats
Example: Evaluate (A+B)  (C+D)
 Three-Address
1. ADD R1, A, B ; R1 ← M[A] + M[B]
2. ADD R2, C, D ; R2 ← M[C] + M[D]
3. MUL X, R1, R2 ; M[X] ← R1  R2
Instruction Formats
Example: Evaluate (A+B)  (C+D)
 Two-Address
1. MOV R1, A ; R1 ← M[A]
2. ADD R1, B ; R1 ← R1 + M[B]
3. MOV R2, C ; R2 ← M[C]
4. ADD R2, D ; R2 ← R2 + M[D]
5. MUL R1, R2 ; R1 ← R1  R2
6. MOV X, R1 ; M[X] ← R1
Instruction Formats
Example: Evaluate (A+B)  (C+D)
 One-Address
1. LOAD A ; AC ← M[A]
2. ADD B ; AC ← AC + M[B]
3. STORE T ; M[T] ← AC
4. LOAD C ; AC ← M[C]
5. ADD D ; AC ← AC + M[D]
6. MUL T ; AC ← AC  M[T]
7. STORE X ; M[X] ← AC
Instruction Formats
Example: Evaluate (A+B)  (C+D)
 Zero-Address
1. PUSH A ; TOS ← A
2. PUSH B ; TOS ← B
3. ADD ; TOS ← (A + B)
4. PUSH C ; TOS ← C
5. PUSH D ; TOS ← D
6. ADD ; TOS ← (C + D)
7. MUL ; TOS ←
(C+D)(A+B)
8. POP X ; M[X] ← TOS
Instruction Formats
Example: Evaluate (A+B)  (C+D)
 RISC
1. LOAD R1, A ; R1 ← M[A]
2. LOAD R2, B ; R2 ← M[B]
3. LOAD R3, C ; R3 ← M[C]
4. LOAD R4, D ; R4 ← M[D]
5. ADD R1, R1, R2 ; R1 ← R1 + R2
6. ADD R3, R3, R4 ; R3 ← R3 + R4
7. MUL R1, R1, R3 ; R1 ← R1  R3
8. STORE X, R1 ; M[X] ← R1
Using Registers
 Registers are faster
 Shorter instructions
 The number of registers is smaller (e.g. 32
registers need 5 bits)
 Potential speedup
 Minimize the frequency with which data is
moved back and forth between the memory
and processor registers.
Instruction Execution and
Straight-Line Sequencing
Address Contents

i
Assumptions:
Begin execution here Move A,R0
i+4
3-instruction
program
- One memory operand
Add B,R0
segment per instruction
i+8 Move R0,C
- 32-bit word length
- Memory is byte
addressable
A - Full memory address
can be directly specified
in a single-word instruction
B Data for
the program
Two-phase procedure
-Instruction fetch
-Instruction execute
C

Figure 2.8. A program for C  [A] + [B].

i Move NUM1,R0
i+4 Add NUM2,R0

Branching i+8 Add NUM3,R0

•
•
•
i + 4n - 4 Add NUMn,R0
i + 4n Move R0,SUM

•
•
•
SUM
NUM1
NUM2

•
•
•
NUMn

Figure 2.9. A straight-line program for adding n numbers.

Move N,R1
Clear R0

Branching LOOP
Determine address of
"Next" number and add
Program "Next" number to R0
loop
Decrement R1
Branch>0 LOOP
Branch target
Move R0,SUM

Conditional branch
•
•
•
SUM
N n
NUM1

Figure 2.10. Using a loop to add n numbers. NUM2

•
•
•
NUM n
Condition Codes
 Condition code flags
 Condition code register / status register
 N (negative)
 Z (zero)
 V (overflow)
 C (carry)
 Different instructions affect different flags
Status Bits

Cn-1
A B

Cn ALU
F
V Z S C
Fn-1

Zero Check
Addressing
Modes
Generating Memory Addresses
 How to specify the address of branch target?
 Can we give the memory operand address
directly in a single Add instruction in the loop?
 Use a register to hold the address of NUM1;
then increment by 4 on each pass through
the loop.
Addressing Modes

Opcode Mode ...

 Implied
 AC is implied in “ADD M[AR]” in “One-Address”
instr.
 TOS is implied in “ADD” in “Zero-Address” instr.
 Immediate
 The use of a constant in “MOV R1, 5”, i.e. R1 ←
5
 Register
 Indicate which register holds the operand
Addressing Modes
 Register Indirect
 Indicate the register that holds the number of the
register that holds the operand R1
MOV R1, (R2)
R2 = 3
 Autoincrement / Autodecrement
 Access & update in 1 instr. R3 = 5

 Direct Address
 Use the given address to access a memory
location
Addressing Modes
 Indirect Address
 Indicate the memory location that holds the
address of the memory location that holds the
data
AR = 101

100
101 0 1 0 4
102
103
104 1 1 0 A
Addressing Modes

 Relative Address
0
 EA = PC + Relative Addr 1
PC = 2 2

100
AR = 100
101
102 1 1 0 A
Could be Positive or 103
Negative 104
(2’s Complement)
Addressing Modes
 Indexed
 EA = Index Register + Relative Addr

Useful with XR = 2
“Autoincrement” or
“Autodecrement”
+

100
AR = 100
101
Could be Positive or
Negative 102 1 1 0 A
(2’s Complement) 103
104
Addressing Modes
 Base Register
 EA = Base Register + Relative Addr

Could be Positive or AR = 2
Negative
(2’s Complement)
+

100 0 0 0 5
BR = 100
101 0 0 1 2
102 0 0 0 A
Usually points to 103 0 1 0 7
the beginning of 104 0 0 5 9
an array
Addressing Modes
Name Assembler syntax Addressingfunction
 The different
ways in which Immediate #Value Op erand = Value
the location of
an operand is Register Ri EA = Ri
specified in Absolute (Direct) LOC EA = LOC
an instruction
are referred Indirect (R i ) EA = [Ri ]
to as (LOC) EA = [LOC]
addressing
modes. Index X(R i ) EA = [Ri ] + X

Base with index (R i ,Rj ) EA = [Ri ] + [Rj ]

Base with index X(R i ,Rj ) EA = [Ri ] + [Rj ] + X
and offset

Relative X(PC) EA = [PC] + X

Autoincrement (R i )+ EA = [Ri ] ;
Increment R i

Autodecrement  (R i ) Decrement R i ;
EA = [Ri ]
Indexing and Arrays
 Index mode – the effective address of the operand
is generated by adding a constant value to the
contents of a register.
 Index register
 X(Ri): EA = X + [Ri]
 The constant X may be given either as an explicit
number or as a symbolic name representing a
numerical value.
 If X is shorter than a word, sign-extension is needed.
Indexing and Arrays
 In general, the Index mode facilitates access to an
operand whose location is defined relative to a reference
point within the data structure in which the operand
appears.

 Several variations:
(Ri, Rj): EA = [Ri] + [Rj]
X(Ri, Rj): EA = X + [Ri] + [Rj]
Relative Addressing
 Relative mode – the effective address is determined
by the Index mode using the program counter in
place of the general-purpose register Ri .
 X(PC) – note that X is a signed number
 Branch>0 LOOP
 This location is computed by specifying it as an
offset from the current value of PC.
 Branch target may be either before or after the
branch instruction, the offset is given as a singed
num.
Additional Modes
 Autoincrement mode – the effective address of the operand is
the contents of a register specified in the instruction. After
accessing the operand, the contents of this register are
automatically incremented to point to the next item in a list.
 (Ri)+. The increment is 1 for byte-sized operands, 2 for 16-bit
operands, and 4 for 32-bit operands.
 Autodecrement mode: -(Ri) – decrement first
Move N,R1
Move #NUM1,R2 Initialization
Clear R0
LOOP Add (R2)+,R0
Decrement R1
Branch>0 LOOP
Move R0,SUM

Figure 2.16. The Autoincrement addressing mode used in the program of Figure 2.12.