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.
Separate Memory Access and
ALU Operation
 Load R2, LOC ; R2  [LOC]
 Add R4, R2, R3 ; R4  [R2] +[R3]
 Store R4, LOC ; [LOC]  R4
 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)
 Processor Memory Interface
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
Processor mem. interface
 A Read signal is sent to the memory
 The first instruction is read out and loaded
into Processor mem. interface and trasferred
to IR
 Decode and execute the instruction
Typical Operating Steps
(Cont’)
 Get operands for ALU
 General-purpose register
 Memory (Address from Processor memory interface –
Read signal)
 Perform operation in ALU
 Store the result back
 To general-purpose register
 To memory (Address and data from Processor memory
interface – Write signal)
 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)
 Number
Representation and
Arithmetic
Operations
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 (Mod-16 system)
-7 +0
-6 1111 0000 +1
1110 0001
-5 +2 +
1101 0010
-4 1100 0 0 1 1 +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 0 0 1 1 +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 0 0 1 1 +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
Page 28
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)
Page 31 (- 2)
0101 ( + 5) 1110
(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
 Sign Extension
 Task:
 Given w-bit signed integer x

 Convert it to w+k-bit integer with same value

 Rule:
 Make k copies of sign bit:

 X  = xw–1 ,…, xw–1 , xw–1 , xw–2 ,…, x0

w
X • • •
k copies of MSB

• • •

X • • • • • •
k w
 Chapter 2.
Instruction Set
Architecture
Objectives
 Machine instructions and program execution,
including branching and subroutine call and return
operations.
 Addressing methods for accessing register and
memory operands.
 Assembly language for representing machine
instructions, data, and programs.
 Program-controlled Input/Output operations.
Memory Locations
and Addresses
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
 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.
 Load R1, LOCA ; R1←[LOCA]
 Store R2, LOCA, ; [LOCA] ← [R2]
 Add R3, R1, R2 ; R3 ←[R1]+[R2]
Instruction Formats
 RISC Instructions
 Lots of registers. Memory is restricted to Load & Store
C = A + B; HLL

Load R2, A ; for RISC machine

Load R3,B
Add R4, R2, R3
Store R4,C

Opcode Operand(s) or Address(es)

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 Load R2, A
i+4
4-instruction
program
- One memory operand
Load R3, B
segment per instruction
i+8 Add R4, R2, R3
- 32-bit word length
I + 12 Store R4, C
- 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].

Branching

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

Branching

Figure 2.9. Using a loop to add n numbers.

Condition Codes
 Condition code flags
 Condition code register / status register
 N (negative)
 Z (zero)
 V (overflow)
 C (carry)
 Different instructions affect different flags
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 ...

Addressing Modes
 Register
 The operand is the contents of a processor register;
the name of the register is given in the instruction.
MOV R1, R2
 Absolute mode
 .The operand is in a memory location; the address of
this location is given explicitly in the instruction.
Load R4, LOCA
 Immediate
 The operand is given explicitly in the instruction

Add R4, R6, #200

Addressing Modes
 Indirect Address
 Indicate the memory location that holds the
address of the memory location that holds the
data
Addressing Modes
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
Indexing and Arrays
Indexing and Arrays
Indexing and Arrays
Assembly
Language
 A complete set of symbolic names (mnemonics)
and rules for their use constitute Assembly
Language.
 Assembler program one of a collection of utility
programs that are a part of the system software.
 It translates programs written in Assembly
language(source pgm.) to sequence of machine
instructions automatically(object pgm.).
 It may or may not be case sensitive.
Assembler Directives
 If the assembler is to produce an object program
according to this arrangement, it has to know
• How to interpret the names
• Where to place the instructions in the memory
• Where to place the data operands in the memory
 For this, along with instructions assembler allows the
programmer to specify other information needed to
translate source pgm. into object pgm. in the form of
Assembler Directives.
 These are not instructions and will not appear in the
object pgm.
Assembler Directives (Ref. pg. 60-61)

 Eg: EQU -> assigns a value to the name

SUM EQU 200
 ORIGIN -> tells the assembler wherein memory to place the data
block that follows.
ORIGIN 100
 DATAWORD -> loads the value to variables and constants.
N DATAWORD 100
 RESERVE -> reserves block of memory
NUM1 RESERVE 400
 END -> indicates the end of source pgm.
 START -> address of the location at which the execution of the pgm.
Is to begin.
Assembling and Execution of
Programs
 Symbol Table
 Two Pass Assembler
 Loader - Executing the loader performs a sequence of
input operations needed to transfer the machine-
language program from the disk into a specified place in
the memory.
 Having loaded the object code, the loader starts
execution of the object program by branching to the first
instruction to be executed
 Debugger - To help the user find other programming
errors, the system software usually includes a debugger
program.
Stacks
 A stack is a list of data elements, usually
words, with the accessing restriction that
elements can be added or removed at one
end of the list only.
 This end is called the top of the stack, and
the other end is called the bottom.
 last-in–first-out (LIFO) stack, pushdown stack
 The terms push and pop are used to describe
placing a new item on the stack and
removing the top item from the stack,
respectively.
 the stack pointer (SP) register is used to
access the stack.
 Push:
Subtract SP, SP, #4
Store Rj, (SP)

 Pop
Load Rj, (SP)
Add SP, SP, #4
Stack Organization

Current
Top of Stack
 LIFO TOS 0
Last In First Out 1
2
3
4
5
SP 6 0 1 2 3
7 0 0 5 5
FULL EMPTY 8 0 0 0 8
9 0 0 2 5
Stack Bottom 10 0 0 1 5
Stack
Stack Organization

Current 1 6 9 0
Top of Stack
 PUSH TOS 0
SP ← SP – 1 1
M[SP] ← DR 2
3
If (SP = 0) then (FULL ← 1) 4
EMPTY ← 0 5 1 6 9 0
SP 6 0 1 2 3
7 0 0 5 5
FULL EMPTY 8 0 0 0 8
9 0 0 2 5
Stack Bottom 10 0 0 1 5
Stack
Stack Organization
Current
Top of Stack
 POP TOS 0
DR ← M[SP] 1
SP ← SP + 1 2
3
If (SP = 11) then (EMPTY ← 1) 4
FULL ← 0 5 1 6 9 0
SP 6 0 1 2 3
7 0 0 5 5
FULL EMPTY 8 0 0 0 8
9 0 0 2 5
Stack Bottom 10 0 0 1 5
Stack
Stack Organization
 Memory Stack
 PUSH PC 0
1
SP ← SP – 1 2
M[SP] ← DR
 POP AR 100
DR ← M[SP] 101
102
SP ← SP + 1
200
SP 201
202
Subroutines
 A block of instructions that is executed each time
a task has to be performed is called subroutine.
 Implemented using CALL and RETURN
instructions.
 The way in which a computer makes it possible
to call and return from subroutines is referred to
as its subroutine linkage method.
 The simplest subroutine linkage method is to
save the return address in a specific location,
which may be a register dedicated to this
function. Such a register is called the link
register.
 Call instruction steps:
 Store the contents of the PC in the link
register
 Branch to the target address specified by the
Call instruction
 Return instruction steps:
 Branch to the address contained in the link
register.
Subroutine Nesting and Processor
Stack
 One subroutine calling another.
 Subroutine nesting can be carried out to any
depth.
 The last subroutine called completes its
computations and returns to the subroutine
that called it.
 Return addresses associated with subroutine
calls should be pushed onto the processor
stack
Parameter Passing
 Registers:
Parameter Passing
 Stack:
Parameter Passing
 Stack:
Parameter Passing
 Stack:
Stack Frame
 During execution of the subroutine, locations at
the top of the stack contain entries that are
needed by the subroutine.
 These locations constitute a private work space
for the subroutine, allocated at the time the
subroutine is entered and deallocated when the
subroutine returns control to the calling program.
Such space is called a stack frame.
 In addition to the stack pointer SP, it is useful to
have another pointer register, called the frame
pointer (FP), for convenient access to the
parameters passed to the subroutine and to the
local memory variables used by the subroutine.
 Stack Frame
 FP register points to
the location just
above the stored
parameters.
 The parameters can
be accessed by using
addresses 4(FP),
8(FP), . . . .
 The local variables
can be accessed by
using addresses
−4(FP), −8(FP), . . . .
 The contents of FP
remain fixed
throughout the
execution of the
subroutine, unlike
SP.
 Additional
Instructions
Logical Shifts
 Logical shift – shifting left (LShiftL) and shifting right
(LShiftR)
C R0 0

before: 0 0 1 1 1 0 . . . 0 1 1

after: 1 1 1 0 . . . 0 1 1 0 0

(a) Logical shift left LShiftL R0, R0 #2

0 R0 C

before: 0 1 1 1 0 . . . 0 1 1 0

after: 0 0 0 1 1 1 0 . . . 0 1

(b) Logical shift ight

r LShiftR R0, R0 #2
Arithmetic Shifts

R0 C

before: 1 0 0 1 1 . . . 0 1 0 0

after: 1 1 1 0 0 1 1 . . . 0 1

(c) Arithmetic shift right AShiftR R0, R0 #2

 C R0

before: 0 0 1 1 1 0 . . . 0 1 1

Rotate after: 1 1 1 0 . . . 0 1 1 0 1

(a) Rotate left without carr

y RotateL R0, R0 #2

C R0

before: 0 0 1 1 1 0 . . . 0 1 1

after: 1 1 1 0 . . . 0 1 1 0 0

(b) Rotate left with carr

y RotateLC R0, R0 #2

R0 C

before: 0 1 1 1 0 . . . 0 1 1 0

after: 1 1 0 1 1 1 0 . . . 0 1

(c) Rotate ight

r without carry RotateR R0, R0 #2

R0 C

before: 0 1 1 1 0 . . . 0 1 1 0

after: 1 0 0 1 1 1 0 . . . 0 1

(d) Rotate ight

r with carry RotateRC R0, R0 #2

Figure 2.32. Rotate instructions.

 RISC VS. CISC
RISC style is characterized by:
• Simple addressing modes
• All instructions fitting in a single word
• Fewer instructions in the instruction set, as a consequence of simple
addressing modes
• Arithmetic and logic operations that can be performed only on
operands in processor registers
• Load/store architecture that does not allow direct transfers from one
memory location to another; such transfers must take place via a
processor register
• Simple instructions that are conducive to fast execution by the
processing unit using techniques such as pipelining
• Programs that tend to be larger in size, because more, but simpler
instructions are needed to perform complex tasks
 RISC VS. CISC
CISC style is characterized by:
• More complex addressing modes
• More complex instructions, where an instruction may span multiple
words
• Many instructions that implement complex tasks
• Arithmetic and logic operations that can be performed on memory
operands as well as operands in processor registers
• Transfers from one memory location to another by using a single
Move instruction
• Programs that tend to be smaller in size, because fewer, but more
complex instructions are needed to perform complex tasks