COMPUTER ORGANIZATION NOTES

Subject Code: 18CS34

MODULE 1:
 BASIC STRUCTURE OF COMPUTERS
 MACHINE INSTRUCTIONS AND PROGRAMS

Basic Structure of Computers: Basic Operational Concepts, Bus Structures, Performance –

Processor Clock,Basic Performance Equation, Clock Rate, Performance Measurement.

Machine Instructions and Programs: Memory Location and Addresses, Memory

Operations, Instructions andInstruction Sequencing, Addressing Modes, Assembly Language,
Basic Input and Output Operations, Stacks and Queues, Subroutines, Additional Instructions,
Encoding of Machine Instructions

Computer Organization
It describes the function of and design of the various units of digital computer that store and
process information.

1.2 Functional Units of computer

A computer consists of five functionally independent main parts: input, memory, arithmetic
and logic, output, and control units, as shown in Figure

MAIN PARTS OF PROCESSOR

1.2.1 Input Unit

Computers accept coded information through input units. The most common input device
isthe keyboard. Whenever a key is pressed, the corresponding letter or digit is
automaticallytranslated into its corresponding binary code and transmitted to the processor.

1
1.2.2 Memory Unit
The function of the memory unit is to store programs and data. There are two classes
ofstorage, called primary and secondary.
Primary Memory
Primary memory, also called main memory, is a fast memory that operates at
electronicspeeds. Programs must be stored in this memory while they are being executed.

Cache Memory
As an adjunct to the main memory, a smaller, faster RAM unit, called a cache, is usedto hold
sections of a program that are currently being executed, along with any associateddata.

Secondary Storage
Although primary memory is essential, it tends to be expensive and does not
retaininformationwhen power is turned off. Thus additional, less expensive, permanent
secondarystorage is used when large amounts of data and many programs have to be stored,
particularlyfor information that is accessed infrequently.

1.2.3 Arithmetic and Logic Unit

Most computer operations are executed in the arithmetic and logic unit (ALU) of
theprocessor. Any arithmetic or logic operation, such as addition, subtraction,
multiplication,division, or comparison of numbers, is initiated by bringing the required
operands into theprocessor, where the operation is performed by the ALU.

1.2.4 Output Unit

The output unit is the counterpart of the input unit. Its function is to send processed resultsto
the outside world. Afamiliar example of such a device is a printer. Most printers
employeither photocopying techniques, as in laser printers, or ink jet streams.

1.2.5 Control Unit

The memory, arithmetic and logic, and I/O units store and process information and
performinput and output operations. The operation of these units must be coordinated in some
way.This is the responsibility of the control unit.

----------------------------------------------------------------------------------------------------------------

Q)With a neat diagram, discuss the basic operational concepts of a computer. Dec 2015

Basic Operational Concepts

An Instruction consists of 2 parts,
1) Operation code (Opcode) and
2) Operands.

OPCODE OPERANDS

The data/operands are stored in memory.

The individual instruction are brought from the memory to the processor.
Then, the processor performs the specified operation.

2
• Let us see a typical instruction
ADD LOCA, R0
• This instruction is an addition operation. The following are the steps to execute the
instruction:

Step 1: Fetch the instruction from main-memory into the processor.

Step 2: Fetch the operand at location LOCA from main-memory into the processor.
Step 3: Add the memory operand (i.e. fetched contents of LOCA) to the contents of register
R0.
Step 4: Store the result (sum) in R0.

Processor components

The processor contains ALU, control-circuitry and many registers.

• The processor contains „n‟ general-purpose registers R0 through Rn-1.

• The IR holds the instruction that is currently being executed.
• The control-unit generates the timing-signals that determine when a given action is to take
place.
• The PC contains the memory-address of the next-instruction to be fetched & executed.
• During the execution of an instruction, the contents of PC are updated to point to next
instruction.
• The MAR holds the address of the memory-location to be accessed.
• The MDR contains the data to be written into or read out of the addressed location.
• MAR and MDR facilitates the communication with memory.
(IR : Instruction-Register, PC : Program Counter)
(MAR :Memory Address Register, MDR : Memory Data Register)

STEPS TO EXECUTE AN INSTRUCTION

1) The address of first instruction (to be executed) gets loaded into PC.

3
2) The contents of PC (i.e. address) are transferred to the MAR & control-unit issues Read
signal tomemory.
3) After certain amount of elapsed time, the first instruction is read out of memory and placed
intoMDR.
4) Next, the contents of MDR are transferred to IR. At this point, the instruction can be
decoded &executed.
5) To fetch an operand, it's address is placed into MAR & control-unit issues Read signal. As
a result,the operand is transferred from memory into MDR, and then it is transferred from
MDR to ALU.
6) Likewise required number of operands is fetched into processor.
7) Finally, ALU performs the desired operation.
8) If the result of this operation is to be stored in the memory, then the result is sent to the
MDR.
9) The address of the location where the result is to be stored is sent to the MAR and a Write
cycle isinitiated.
10) At some point during execution, contents of PC are incremented to point to next
instruction in the program.

----------------------------------------------------------------------------------------------------------------------

BUS STRUCTURE
• A bus is a group of lines that serves as a connecting path for several devices.
• A bus may be lines or wires.
• The lines carry data or address or control signal.
• There are 2 types of Bus structures:
1) Single Bus Structure and 2) Multiple Bus Structure.

1) Single Bus Structure

Because the bus can be used for only one transfer at a time, only 2 units can actively use the
bus at any given time.Bus control lines are used to arbitrate multiple requests for use of the
bus.

Advantages:
1) Low cost &
2) Flexibility for attaching peripheral devices.

2) Multiple Bus Structure

Systems that contain multiple buses achieve more concurrency in operations.Two or more
transfers can be carried out at the same time.

4
Advantage: Better performance.
Disadvantage: Increased cost.

• The devices connected to a bus vary widely in their speed of operation.

• To synchronize their operational-speed, buffer-registers can be used.

• Buffer Registers
→ are included with the devices to hold the information during transfers.
→ prevent a high-speed processor from being locked to a slow I/O device during data
transfers.

----------------------------------------------------------------------------------------------------------------
Performance – Processor Clock, Basic Performance Equation, Clock Rate, Performance
Measurement.

PERFORMANCE
• The most important measure of performance of a computer is how quickly it can execute
programs.

• The speed of a computer is affected by the design of

1) Instruction-set.
2) Hardware & the technology in which the hardware is implemented.
3) Software including the operating system.

• Because programs are usually written in a HLL, performance is also affected by the
compiler that translates programs into machine language. (HLL :High Level Language).

• For best performance, it is necessary to design the compiler, machine instruction set and
hardware in a co-ordinated way.

• Let us examine the flow of program instructions and data between the memory & the
processor.
• At the start of execution, all program instructions are stored in the main-memory.
• As execution proceeds, instructions are fetched into the processor, and a copy is placed in
the cache.

5
• Later, if the same instruction is needed a second time, it is read directly from the cache.
•A program will be executed faster if movement of instruction/data between the main-
memory and the processor is minimized which is achieved by using the cache.

PROCESSOR CLOCK
• Processor circuits are controlled by a timing signal called a Clock.
• The clock defines regular time intervals called Clock Cycles.
• To execute a machine instruction, the processor divides the action to be performed into a
sequence of basic steps such that each step can be completed in one clock cycle.
• Let P = Length of one clock cycle
R = Clock rate.
• Relation between P and R is given by R=
• R is measured in cycles per second.
• Cycles per second is also called Hertz (Hz)

Q) Write the basic performance equation. explain the role of each of the parameters in the
equation on the performance of the computer. July 2014

BASIC PERFORMANCE EQUATION

• Let T = Processor time required to executed a program.

N = Actual number of instruction executions.
S = Average number of basic steps needed to execute one machine instruction.
R = Clock rate in cycles per second.
• The program execution time is given by T= ------ (1)

• Equ1 is referred to as the basic performance equation.

• To achieve high performance, the computer designer must reduce the value of T, which
meansreducing N and S, and increasing R.

The value of N is reduced if source program is compiled into fewer machine instructions.
The value of S is reduced if instructions have a smaller number of basic steps to perform.
The value of R can be increased by using a higher frequency clock.
Care has to be taken while modifying values since changes in one parameter may affect the
other.

CLOCK RATE
There are 2 possibilities for increasing the clock rate R:
1) Improving the IC technology makes logic-circuits faster.
This reduces the time needed to compute a basic step. (IC :integrated circuits).
This allows the clock period P to be reduced and the clock rate R to be increased.

2) Reducing the amount of processing done in one basic step also reduces the clock period P.

In presence of a cache, the percentage of accesses to the main-memory is small.

Hence, much of performance-gain expected from the use of faster technology can be realized.

6
The value of T will be reduced by same factor as R is increased „.‟ S & N are not affected.

PERFORMANCE MEASUREMENT
• Benchmark refers to standard task used to measure how well a processor operates.
• The Performance Measure is the time taken by a computer to execute a given benchmark.
• SPEC selects & publishes the standard programs along with their test results for different
applicationdomains. (SPEC :System Performance Evaluation Corporation).
• SPEC Rating is given by

SPEC rating =

• SPEC rating = 50 :The computer under test is 50 times as fast as reference-computer.

• The test is repeated for all the programs in the SPEC suite.
Then, the geometric mean of the results is computed.
• Let SPECi = Rating for program „i' in the suite.

Overall SPEC rating for the computer is given by

(∏ )

Where n is the number of programs in the suite

Geometrical mean= Is defined as the nth root of the product of n numbers
----------------------------------------------------------------------------------------------------------------
Problem 1:
List the steps needed to execute the machine instruction:

ADD LOC A, R0

Solution:
1. Transfer the contents of register PC to register MAR.
2. Issue a Read command to memory. And, then wait until it has transferred the requested
word into register MDR.
3. Transfer the instruction from MDR into IR and decode it.
4. Transfer the address LOCA from IR to MAR.
5. Issue a Read command and wait until MDR is loaded.
6. Transfer contents of MDR to the ALU.
7. Transfer contents of R0 to the ALU.
8. Perform addition of the two operands in the ALU and transfer result into R0.
9. Transfer contents of PC to ALU.
10. Add 4 to operand in ALU and transfer incremented address to PC.

Problem 2:
List the steps needed to execute the machine instruction:

7
Add R1, R2, R3

Solution:
1. Transfer the contents of register PC to register MAR.
2. Issue a Read command to memory. And, then wait until it has transferred the requested
word into register MDR.
3. Transfer the instruction from MDR into IR and decode it.
4. Transfer contents of R1 and R2 to the ALU.
5. Perform addition of two operands in the ALU and transfer answer into R3.
6. Transfer contents of PC to ALU.
7. Add 4 to operand in ALU and transfer incremented address to PC.

Problem 3:
(a) Give a short sequence of machine instructions for the task “Add the contents of memory-
location A to those of location B, and place the answer in location C”.

Instructions:

Load Ri, LOC

and
Store Ri, LOC

are the only instructions available to transfer data between memory and the general purpose
registers.

Is it possible to use fewer instructions of these types to accomplish the task in part (a)? If yes,
give the sequence.

Solution:

(a)
Load A, R0
Load B, R1
Add R0, R1
Store R1, C

(b) Yes;
Move B, C
Add A, C

Problem 4:
A program contains 1000 instructions. Out of that 25% instructions requires 4 clock
cycles,40% instructions requires 5 clock cycles and remaining require 3 clock cycles for
execution. Find the total time required to execute the program running in a 1 GHz machine.

8
Solution:
N = 1000

25% of N= 250 instructions require 4 clock cycles.

40% of N =400 instructions require 5 clock cycles.
35% of N=350 instructions require 3 clock cycles.

T = (N*S)/R=

=(250*4+400*5+350*3)/1X109

=(1000+2000+1050)/1*109

= 4.05 μs.

Problem 5:

For the following processor, obtain the performance.

Clock rate = 800 MHz
No. of instructions executed = 1000
Average no of steps needed / machine instruction = 20

Solution:

Problem 6:
(a) Program execution time T is to be examined for a certain high-level language program.
The program can be run on a RISC or a CISC computer. Both computers use pipelined
instruction execution, but pipelining in the RISC machine is more effective than in the CISC
machine. Specifically, the effective value of S in the T expression for the RISC machine is
1.2, bit it is only 1.5 for the CISC machine. Both machines have the same clock rate R. What
is the largest allowable value for N, the number of instructions executed on the CISC
machine, expressed as a percentage of the N value forthe RISC machine, if time for execution
on the CISC machine is to be longer than on the RISC machine?

(b) Repeat Part (a) if the clock rate R for the RISC machine is 15 percent higher than that for
the CISC machine.

Solution:
(a) Let TR = (NR X SR)/RR & TC = (NC X SC)/RC be execution times on RISC and CISC
processors.
Equating execution times and clock rates, we have
1.2NR = 1.5NC
Then
NC/NR = 1.2/1.5 = 0.8

Therefore, the largest allowable value for NC is 80% of NR.

9
(b) In this case,

1.2NR/1.15 = 1.5NC/1.00

Then
NC/NR =1.2/(1.15 X 1.5) = 0.696

Therefore, the largest allowable value for NC is 69.6% of NR.

----------------------------------------------------------------------------------------------------------------

MACHINE INSTRUCTIONS & PROGRAMS

MEMORY-LOCATIONS & ADDRESSES

• Memory consists of many millions of storage cells (flip-flops).

• Each cell can store a bit of information i.e. 0 or 1 (Figure 2.1).
• Each group of n bits is referred to as a word of information, and n is called the word
length.
• The word length can vary from 8 to 64 bits.
• A unit of 8 bits is called a byte.
• Accessing the memory to store or retrieve a single item of information (word/byte) requires
distinctaddresses for each item location. (It is customary to use numbers from 0 through 2k-1
as theaddresses of successive-locations in the memory).

• If 2k = no. of addressable locations;

then 2k addresses constitute the address-space of the computer.
For example, a 24-bit address generates an address-space of 224 locations (16 MB).

10
BYTE-ADDRESSABILITY

A byte is always 8 bits, but the word length typically ranges from 16 to 64 bits.

• In byte-addressable memory, successive addresses refer to successive byte locations in the

memory.
• Byte locations have addresses 0, 1, 2. . . . .
• If the word-length is 32 bits, successive words are located at addresses 0, 4, 8. . with each
word having 4 bytes.

Q) Discuss two ways in which byte addresses are assigned June 2015
Q) Big-Endian and Little-Endian assignment, explain with necessary figure. Jan 2014

BIG-ENDIAN & LITTLE-ENDIAN ASSIGNMENTS

• There are two ways in which byte-addresses are arranged (Figure 2.3).

1) Big-Endian: Lower byte-addresses are used for the more significant bytes of the word.

2) Little-Endian: Lower byte-addresses are used for the less significant bytes of the word

• In both cases, byte-addresses 0, 4, 8. . . . . are taken as the addresses of successive words in

the memory.

11
Consider a 32-bit integer (in hex): 0x12345678 which consists of 4 bytes: 12, 34, 56, and 78.
Hence this integer will occupy 4 bytes in memory.
Assume, we store it at memory address starting 1000.
On little-endian, memory will look like

Address Value
1000 78
1001 56
1002 34
1003 12
On big-endian, memory will look like

Address Value
1000 12
1001 34
1002 56
1003 78

WORD ALIGNMENT
• Words are said to be Alignedin memory if they begin at a byte-address that is a multiple of
the number of bytes in a word.

• For example,
If the word length is 16(2 bytes), aligned words begin at byte-addresses 0, 2, 4 . . . . .
If the word length is 64(2 bytes), aligned words begin at byte-addresses 0, 8, 16 . . . . .

• Words are said to have Unaligned Addresses, if they begin at an arbitrary byte-address.

12
ACCESSING NUMBERS, CHARACTERS & CHARACTERS STRINGS

• A number usually occupies one word. It can be accessed in the memory by specifying its
word address. Similarly, individual characters can be accessed by their byte-address.

• There are two ways to indicate the length of the string:

1)A special control character with the meaning "end of string" can be used as the last
character in the string.

2)A separate memory word location or register can contain a number indicating the length of
the string in bytes.
----------------------------------------------------------------------------------------------------------------

MEMORY OPERATIONS

Both program instructions and data operands are stored in the memory. To execute
aninstruction, the processor control circuits must cause the word (or words) containing
theinstruction to be transferred from the memory to the processor. Operands and results
mustalso be moved between the memory and the processor. Thus, two basic operations
involvingthe memory are needed, namely, Read and Write.

• Two memory operations are:

1) Load (Read/Fetch) &

2) Store (Write).

• The Load operation transfers a copy of the contents of a specific memory-location to the
processor.

The memory contents remain unchanged.

• Steps for Load operation:

1) Processor sends the address of the desired location to the memory.

2) Processor issues „read‟ signal to memory to fetch the data.
3) Memory reads the data stored at that address.
4) Memory sends the read data to the processor.

• The Store operation transfers the information from the register to the specified memory-
location. This will destroy the original contents of that memory-location.

• Steps for Store operation are:

1) Processor sends the address of the memory-location where it wants to store data.
2) Processor issues „write‟ signal to memory to store the data.
3) Content of register(MDR) is written into the specified memory-location.

----------------------------------------------------------------------------------------------------------------

13
INSTRUCTIONS & INSTRUCTION SEQUENCING

The tasks carried out by a computer program consist of a sequence of small steps, suchas
adding two numbers, testing for a particular condition, reading a character from thekeyboard,
or sending a character to be displayed on a display screen.

• A computer must have instructions capable of performing 4 types of operations:

1) Data transfers between the memory and the registers (MOV, PUSH, POP, XCHG).
2) Arithmetic and logic operations on data (ADD, SUB, MUL, DIV, AND, OR, NOT).
3) Program sequencing and control(CALL.RET, LOOP, INT).
4) I/0 transfers (IN, OUT).

REGISTER TRANSFER NOTATION (RTN)

Here we describe the transfer of information from one location in a computer to

another.Possible locations that may be involved in such transfers are memory locations,
processorregisters, or registers in the I/O subsystem. Most of the time, we identify such
locationssymbolically with convenient names.

• The possible locations in which transfer of information occurs are:

1) Memory-location
2) Processor register &
3) Registers in I/O device.

ASSEMBLY LANGUAGE NOTATION

• To represent machine instructions and programs, assembly language format is used.

14
BASIC INSTRUCTION TYPES

INSTRUCTION EXECUTION & STRAIGHT LINE SEQUENCING

• The program is executed as follows:
1) Initially, the address of the first instruction is loaded into PC (Figure 2.8).
2) Then, the processor control circuits use the information in the PC to fetch and execute
instructions, one at a time, in the order of increasing addresses.

This is called Straight-Line sequencing.

3) During the execution of each instruction, PC is incremented by 4 to point to next
instruction.

• There are 2 phases for Instruction Execution:

1) Fetch Phase: The instruction is fetched from the memory-location and placed in the IR.

2) Execute Phase: The contents of IR is examined to determine which operation is to

beperformed. The specified-operation is then performed by the processor.

15
Program Explanation

• Consider the program for adding a list of n numbers (Figure 2.9).

• The Address of the memory-locations containing the n numbers are symbolically given as
NUM1, NUM2…..NUMn.

• Separate Add instruction is used to add each number to the contents of register R0.

• After all the numbers have been added, the result is placed in memory-location SUM.

16
BRANCHING[Diagram 2.10]

• Consider the task of adding a list of „n‟ numbers (Figure 2.10).

• Number of entries in the list „n‟ is stored in memory-location N.
• Register R1 is used as a counter to determine the number of times the loop is executed.
• Content-location N is loaded into register R1 at the beginning of the program.
• The Loop is a straight line sequence of instructions executed as many times as needed.

The loop starts at location LOOP and ends at the instruction Branch>0.

• During each pass,

→ address of the next list entry is determined and
→ that entry is fetched and added to R0.

• The instruction Decrement R1 reduces the contents of R1 by 1 each time through the loop.

• Then Branch Instruction loads a new value into the program counter. As a result, the
processor fetches and executes the instruction at this new address called the Branch Target.

• A Conditional Branch Instruction causes a branch only if a specified condition is

satisfied. If the condition is not satisfied, the PC is incremented in the normal way, and the
next instruction in sequential address order is fetched and executed.

17
CONDITION CODES
• The processor keeps track of information about the results of various operations. This is
accomplished by recording the required information in individual bits, called Condition
Code Flags.

• These flags are grouped together in a special processor-register called the condition code
register (or statue register).

• Four commonly used flags are:

1) N (negative) set to 1 if the result is negative, otherwise cleared to 0.

2) Z (zero) set to 1 if the result is 0; otherwise, cleared to 0.
3) V (overflow) set to 1 if arithmetic overflow occurs; otherwise, cleared to 0.
4) C (carry) set to 1 if a carry-out results from the operation; otherwise cleared to 0.
---------------------------------------------------------------------------------------------------------------

ADDRESSING MODES

Q) What is an addressing mode .Explain different generic addressing modes with an

example for each Dec 2014/Jan 2015

18
Q) What is the need for an addressing mode? Explain the following addressing modes with
examples: immediate, direct, indirect, index, relative Dec 2014 /July 2015

• The different ways in which the location of an operand is specified in an instruction are
referred to as

Addressing Modes (Table 2.1).

1)Immediate Mode
• The operand is given explicitly in the instruction.
• For example, the instruction
Move #200, R0 ;Place the value 200 in register R0.
• Clearly, the immediate mode is only used to specify the value of a source-operand.

2)Register Mode
• The operand is the contents of a register.
• The name (or address) of the register is given in the instruction.
• Registers are used as temporary storage locations where the data in a register are accessed.
• For example, the instruction
Move R1, R2 ;Copy content of register R1 into register R2.

3)Absolute (Direct) Mode

• The operand is in a memory-location.
• The address of memory-location is given explicitly in the instruction.

19
• The absolute mode can represent global variables in the program.
• For example, the instruction
Move LOC, R2 ;Copy content of memory-location LOC into register R2.

4)INDIRECTION AND POINTERS

• Instruction does not give the operand or its address explicitly.
• Instead, the instruction provides information from which the new address of the operand can
be determined.
• This address is called Effective Address (EA) of the operand.

Indirect Mode
• The EA of the operand is the contents of a register(or memory-location).
• The register (or memory-location) that contains the address of an operand is called a
Pointer.

• We denote the indirection by

→ name of the register or
→ new address given in the instruction.

E.g: Add (R1),R0;The operand is in memory. Register R1 gives the effective-address (B) of
the operand. The data is read from location B and added to contents ofregister R0.

• To execute the Add instruction in fig 2.11 (a), the processor uses the value which is in
register R1, as the EA of the operand.
• It requests a read operation from the memory to read the contents of location B. The value
read is the desired operand, which the processor adds to the contents of register R0.
• Indirect addressing through a memory-location is also possible as shown in fig 2.11(b). In
this case, the processor first reads the contents of memory-location A, then requests a second
read operation using the value B as an address to obtain the operand.

20
Program Explanation

• In above program, Register R2 is used as a pointer to the numbers in the list, and the
operands are accessed indirectly through R2.
• The initialization-section of the program loads the counter-value n from memory-location N
into R1 and uses the immediate addressing-mode to place the address value NUM1, which is
the address of the first number in the list, into R2. Then it clears R0 to 0.
• The first two instructions in the loop implement the unspecified instruction block starting at
LOOP.
• The first time through the loop, the instruction Add (R2), R0 fetches the operand at location
NUM1 and adds it to R0.
• The second Add instruction adds 4 to the contents of the pointer R2, so that it will contain
the address value NUM2 when the above instruction is executed in the second pass through
the loop.

5)INDEXING AND ARRAYS

• A different kind of flexibility for accessing operands is useful in dealing with lists and
arrays.

Index mode
• The operation is indicated as X(Ri)
where X=the constant value which defines an offset(also called a displacement).
Ri=the name of the index register which contains address of a new location.

• The effective-address of the operand is given by EA=X+[Ri]

• The contents of the index-register are not changed in the process of generating the
effectiveaddress.

• The constant X may be given either

→ as an explicit number or
→ as a symbolic-name representing a numerical value.

21
• Fig(a) illustrates two ways of using the Index mode. In fig(a), the index register, R1,
contains the address of a memory-location, and the value X defines an offset(also called a
displacement) from this address to the location where the operand is found.

• To find EA of operand:

Eg: Add 20(R1), R2

EA=>1000+20=1020

• An alternative use is illustrated in fig(b). Here, the constant X corresponds to a memory

address, and the contents of the index register define the offset to the operand. In either case,
the effective-address is the sum of two values; one is given explicitly in the instruction, and
the other is stored in a register.

6)Base with Index Mode

• Another version of the Index mode uses 2 registers which can be denoted as(Ri, Rj)
• Here, a second register may be used to contain the offset X.

22
• The second register is usually called the base register.
• The effective-address of the operand is given by EA=[Ri]+[Rj]
• This form of indexed addressing provides more flexibility in accessing operands because
both components of the effective-address can be changed.

7)Base with Index & Offset Mode

• Another version of the Index mode uses 2 registers plus a constant, which can be denoted as
X(Ri, Rj)
• The effective-address of the operand is given by EA=X+[Ri]+[Rj]
•This added flexibility is useful in accessing multiple components inside each item in a
record, where the beginning of an item is specified by the (Ri, Rj) part of the addressing-
mode. In other words, this mode implements a 3-dimensional array.

8)RELATIVE MODE
• This is similar to index-mode with one difference:
The effective-address is determined using the PC in place of the general purpose register Ri.

• The operation is indicated as X(PC).

• X(PC) denotes an effective-address of the operand which is X locations above or below the
current contents of PC.
• Since the addressed-location is identified "relative" to the PC, the name Relative mode is
associated with this type of addressing.
• This mode is used commonly in conditional branch instructions.

• An instruction such as

Branch > 0 LOOP ;Causes program execution to go to the branch target locationidentified by
name LOOP if branch condition is satisfied.

9) Auto Increment Mode

Effective-address of operand is contents of a register specified in the instruction (Fig: 2.16).
After accessing the operand, the contents of this register are automatically incremented to
point to the next item in a list.
Implicitly, the increment amount is 1.
This mode is denoted as

(Ri)+ ;whereRi=pointer-register.

10) Auto Decrement Mode

The contents of a register specified in the instruction are first automatically decremented and
are then used as the effective-address of the operand.

This mode is denoted as

-(Ri) ;where Ri=pointer-register.

These 2 modes can be used together to implement an important data structure called a stack.

23
----------------------------------------------------------------------------------------------------------------
ASSEMBLY LANGUAGE
• We generally use symbolic-names to write a program.
• A complete set of symbolic-names and rules for their use constitute an Assembly
Language.
• The set of rules for using the mnemonics in the specification of complete instructions and
programs is called the Syntax of the language.
• Programs written in an assembly language can be automatically translated into a sequence
of machine instructions by a program called an Assembler.
• The user program in its original alphanumeric text formal is called a Source Program, and
the assembled machine language program is called an Object Program.
For example:

MOVE R0,SUM;

The term MOVE represents OP code for operation performed by instruction.

ADD #5,R3;

Adds number 5 to contents of register R3 & puts the result back into registerR3.

ASSEMBLER DIRECTIVES
• Directives are the assembler commands to the assembler concerning the program being
assembled.
• These commands are not translated into machine opcode in the object-program.

24
• EQU informs the assembler about the value of an identifier (Figure: 2.18).
Ex: SUM EQU 200 ;Informs assembler that the name SUM should be replaced by the value
200.

• ORIGIN tells the assembler about the starting-address of memory-area to place the data
block.
Ex: ORIGIN 204 ;Instructs assembler to initiate data-block at memory-locations starting
from 204.

• DATAWORD directive tells the assembler to load a value into the location.
Ex: N DATAWORD 100 ;Informs the assembler to load data 100 into the memory-location
N(204).

• RESERVE directive is used to reserve a block of memory.

Ex: NUM1 RESERVE 400 ;declares a memory-block of 400 bytes is to be reserved for data.

• END directive tells the assembler that this is the end of the source-program text.

• RETURN directive identifies the point at which execution of the program should be
terminated.
• Any statement that makes instructions or data being placed in a memory-location may be
given a

label. The label(say N or NUM1) is assigned a value equal to the address of that location.

GENERAL FORMAT OF A STATEMENT

• Most assembly languages require statements in a source program to be written in the form:

25
1) Label is an optional name associated with the memory-address where the machine
language instruction produced from the statement will be loaded.
2) Operation Field contains the OP-code mnemonic of the desired instruction or assembler.
3) Operand Field contains addressing information for accessing one or more operands,
depending on the type of instruction.
4) Comment Field is used for documentation purposes to make program easier to
understand.

ASSEMBLY AND EXECUTION OF PROGRAMS

So far, we have used normal words, such as Load, Store, Add, andBranch, for the instruction
operations to represent the corresponding binary code patterns.When writing programs for a
specific computer, such words are normally replaced byacronyms called mnemonics, such as
LD, ST, ADD, and BR. A shorthand notation is alsouseful when identifying registers, such as
R3 for register 3. Finally, symbols such as LOCmay be defined as needed to represent
particular memory locations. A complete set ofsuch symbolic names and rules for their use
constitutes a programming language, generallyreferred to as an assembly language.

2.5.1 Assembler Directives

In addition to providing a mechanism for representing instructions in a program,
assemblylanguage allows the programmer to specify other information needed to translate the
sourceprogram into the object program. We have already mentioned that we need to
assignnumerical values to any names used in a program. Suppose that the name TWENTY
isused to represent the value 20. This fact may be conveyed to the assembler program
throughan equate statement such as

TWENTY EQU 20

• Assembler Program
→ replaces all symbols denoting operations & addressing-modes with binary-codes used in
machine instructions.
→ replaces all names and labels with their actual values.
→ assigns addresses to instructions & data blocks, starting at address given in ORIGIN
directive
→ inserts constants that may be given in DATAWORD directives.
→ reserves memory-space as requested by RESERVE directives.

• Two Pass Assembler has 2 passes:

1) First Pass: Work out all the addresses of labels.

As the assembler scans through a source-program, it keeps track of all names of numerical
values that correspond to them in a symbol-table.

2) Second Pass: Generate machine code, substituting values for the labels.
When a name appears a second time in the source-program, it is replaced with its value from
the table.

26
• The assembler stores the object-program on a magnetic-disk. The object-program must be
loaded into the memory of the computer before it is executed. For this, a Loader Program is
used.

• Debugger Program is used to help the user find the programming errors.

• Debugger program enables the user

→ to stop execution of the object-program at some points of interest &
→ to examine the contents of various processor-registers and memory-location.

----------------------------------------------------------------------------------------------------------------

BASIC INPUT/OUTPUT OPERATIONS

• Consider the problem of moving a character-code from the keyboard to the processor
(Figure: 2.19).

For this transfer, buffer-register DATAIN & a status control flags(SIN) are used.
• When a key is pressed, the corresponding ASCII code is stored in a DATAIN register
associated with the keyboard.

SIN=1 When a character is typed in the keyboard. This informs the processor that a valid
character is in DATAIN.
SIN=0 When the character is transferred to the processor.

• An analogous process takes place when characters are transferred from the processor to the
display.

For this transfer, buffer-register DATAOUT & a status control flag SOUT are used.
SOUT=1 When the display is ready to receive a character.
SOUT=0 When the character is being transferred to DATAOUT.

• The buffer registers DATAIN and DATAOUT and the status flags SIN and SOUT are part
of circuitry commonly known as a device interface.

I/O Driver program (Programmed IO):

READWAIT Branch to READWAIT if SIN=0

INPUT from DATAIN to R1
WRITEWAIT Branch to WRITEWAIT if SOUT=0
Output from R1 to DATAOUT

27
MEMORY-MAPPED I/O

• Some address values are used to refer to peripheral device buffer-registers such as DATAIN
& DATAOUT.

• No special instructions are needed to access the contents of the registers; data can be
transferred between these registers and the processor using instructions such as Move, Load
or Store.

• For example, contents of the keyboard character buffer DATAIN can be transferred to
register R1 in the processor by the instruction

MoveByte DATAIN,R1

• The MoveByte operation code signifies that the operand size is a byte.

• The Testbitinstruction tests the state of one bit in the destination, where the bit position to
be tested is indicated by the first operand.

READWAIT Test bit #3, INSTATUS

Branch=0 READWAIT
Move Byte DATAIN, R1

WRITEWAIT Test bit #3, OUTSTATUS

Branch=0 WRITEWAIT
Move Byte R1, DATAOUT

Program to read a line of character and display it :

--------------------------------------------------------------------------------------------------------------

28
STACKS

A stack is a list of data elements, usually words, with the accessing restrictionthat elements
can be added or removed at one end of the list only. This end is called the topof the stack, and
the other end is called the bottom. The structure is sometimes referred to asa pushdown stack.

The terms push and pop are used to describe placing a new item onthe stack and removing
the top item from the stack, respectively.In modern computers, a stack is implemented by
using a portion of the main memoryfor this purpose. One processor register, called the stack
pointer (SP), is used to point to aparticular stack structure called the processor stack

.14).

• The various operations performed on stack:

1) Insert: An element is inserted from top end. Insertion operation is called push operation.

2) Delete: An element is deleted from top end. Deletion operation is called pop operation.

• A processor-register is used to keep track of the address of the element of the stack that is at
the top at any given time. This register is called the Stack Pointer (SP).

• If we assume a byte-addressable memory with a 32-bit word length,

1) The push operation can be implemented as

Subtract #4, SP
Move NEWITEM, (SP)

29
2) The pop operation can be implemented as

Move (SP), ITEM

Add #4, SP

• Routine for a safe pop and push operation as follows:

----------------------------------------------------------------------------------------------------------------
QUEUE
• Data are stored in and retrieved from a queue on a FIFO basis.

• Difference between stack and queue?

1) One end of the stack is fixed while the other end rises and falls as data are pushed and
popped.
2) In stack, a single pointer is needed to keep track of top of the stack at any given time. In
queue, two pointers are needed to keep track of both the front and end for removal and
insertion respectively.
3) Without further control, a queue would continuously move through the memory of
acomputer in the direction of higher addresses. One way to limit the queue to a fixed region
in memory is to use a circular buffer.
----------------------------------------------------------------------------------------------------------------
Q) What is subroutine linkage? How are parameters passed to subroutines

SUBROUTINES
• A subtask consisting of a set of instructions which is executed many times is called a
Subroutine.
• A Call instruction causes a branch to the subroutine (Figure: 2.16).
• At the end of the subroutine, a return instruction is executed
30
• Program resumes execution at the instruction immediately following the subroutine call
• 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.
• When the subroutine completes its task, the Return instruction returns to the calling-
program by branching indirectly through the link-register.
• The Call Instruction is a special branch instruction that performs the following operations:

→ Store the contents of PC into link-register.

→ Branch to the target-address specified by the instruction.
• The Return Instruction is a special branch instruction that performs the operation:
→ Branch to the address contained in the link-register.

SUBROUTINE NESTING AND THE PROCESSOR STACK

• Subroutine Nesting means one subroutine calls another subroutine.

• In this case, the return-address of the second call is also stored in the link-register,
destroying its previous contents.
• Hence, it is essential to save the contents of the link-register in some other location before
calling another subroutine. Otherwise, the return-address of the first subroutine will be lost.
• Subroutine nesting can be carried out to any depth. Eventually, the last subroutine called
completes its computations and returns to the subroutine that called it.
• The return-address needed for this first return is the last one generated in the nested call
sequence. That is, return-addresses are generated and used in a LIFO order.

31
• This suggests that the return-addresses associated with subroutine calls should be pushed
onto a stack. A particular register is designated as the SP(Stack Pointer) to be used in this
operation.
• SP is used to point to the processor-stack.
• Call instruction pushes the contents of the PC onto the processor-stack.

Return instruction pops the return-address from the processor-stack into the PC.
----------------------------------------------------------------------------------------------------------------
PARAMETER PASSING TO SUBROUTINES
• The exchange of information between a calling-program and a subroutine is referred to as
Parameter Passing (Figure: 2.25).
• The parameters may be placed in registers or in memory-location, where they can be
accessed by the subroutine.
• Alternatively, parameters may be placed on the processor-stack used for saving the return-
address.
• Following is a program for adding a list of numbers using subroutine with the parameters
passed through registers.

32
----------------------------------------------------------------------------------------------------------------
STACK FRAME

Q) What is stack frame? Explain June 2016

During execution of the subroutine, six locations at the top of the stack contain entriesthat are
needed by the subroutine. These locations constitute a private work space forthe subroutine,
allocated at the time the subroutine is entered and deallocated when thesubroutine returns
control to the calling program. Such space is called a stack frame. If thesubroutine requires
more space for local memory variables, the space for these variablescan also be allocated on
the stack.

• Stack Frame refers to locations that constitute a private work-space for the subroutine.

33
• Fig: 2.27 show an example of a commonly used layout for information in a stack-frame.

• Frame Pointer (FP) is used to access the parameters passed

→ to the subroutine &

→ to the local memory-variables.

• The contents of FP remains fixed throughout the execution of the subroutine, unlike stack-
pointer SP, which must always point to the current top element in the stack.

Operation on Stack Frame

• Initially SP is pointing to the address of oldTOS.

• The calling-program saves 4 parameters on the stack (Figure 2.27).
• The Call instruction is now executed, pushing the return-address onto the stack.
• Now, SP points to this return-address, and the first instruction of the subroutine is executed.
• Now, FP is to be initialized and its old contents have to be stored. Hence, the first 2
instructions in the subroutine are:

Move FP,-(SP)
Move SP,FP

• The FP is initialized to the value of SP i.e. both FP and SP point to the saved FP address.
• The 3 local variables may now be pushed onto the stack. Space for local variables is
allocated by executing the instruction

Subtract #12,SP

34
• Finally, the contents of processor-registers R0 and R1 are saved in the stack. At this point,
the stackframe has been set up as shown in the fig 2.27.

• The subroutine now executes its task. When the task is completed, the subroutine pops the
saved values of R1 and R0 back into those registers, removes the local variables from the
stack frame by executing the instruction.

Add #12, SP

• And subroutine pops saved old value of FP back into FP. At this point, SP points to return-
address, so the Return instruction can be executed, transferring control back to the calling-
program.

STACK FRAMES FOR NESTED SUBROUTINES

• Stack is very useful data structure for holding return-addresses when subroutines are nested.

• When nested subroutines are used; the stack-frames are built up in the processor-stack.

35
36
The Flow of Execution is as follows:

• Main program pushes the 2 parameters param2 and param1 onto the stack and then calls
SUB1.
• SUB1 has to perform an operation & send result to the main-program on the stack
(Fig:2.28& 29).
• During the process, SUB1 calls the second subroutine SUB2 (in order to perform some
subtask).
• After SUB2 executes its Return instruction; the result is stored in register R2 by SUB1.
• SUB1 then continues its computations & eventually passes required answer back to main-
program on the stack.
• When SUB1 executes return statement, the main-program stores this answers in memory-
location RESULT and continues its execution.

----------------------------------------------------------------------------------------------------------------
LOGIC INSTRUCTIONS

• Logic operations such as AND, OR, and NOT applied to individual bits.
• These are the basic building blocks of digital-circuits.
• This is also useful to be able to perform logic operations is software, which is done using
instructions that apply these operations to all bits of a word or byte independently and in
parallel.
• For example, the instruction Not dst

Q) Explain the shift and rotate operation with examples June 2015
Q) Explain logical and arithmetic shift instructions with an example. July 2016

SHIFT AND ROTATE INSTRUCTIONS

• There are many applications that require the bits of an operand to be shifted right or left
some specified number of bit positions.
• The details of how the shifts are performed depend on whether the operand is a signed
number or some more general binary-coded information.
• For general operands, we use a logical shift.

For a number, we use an arithmetic shift, which preserves the sign of the number.

LOGICAL SHIFTS
• Two logical shift instructions are
1) Shifting left (LShiftL) &
2) Shifting right (LShiftR).

• These instructions shift an operand over a number of bit positions specified in a count
operand contained in the instruction.

37
Another important observation is that on a right shift the sign bit must be repeated as the fill-
in bit for the vacated position as a requirement of the 2’s-complement representation for
numbers. This requirement
when shifting right distinguishes arithmetic shifts from logical shifts in which the fill-in bit is
always 0. Otherwise, the two types of shifts are the same

Note: Arithmetic left shift is same as logical shift left

ROTATE OPERATIONS
• In shift operations, the bits shifted out of the operand are lost, except for the last bit shifted
out which is retained in the Carry-flag C.
• To preserve all bits, a set of rotate instructions can be used.
• They move the bits that are shifted out of one end of the operand back into the other end.
• Two versions of both the left and right rotate instructions are usually provided.
In one version, the bits of the operand is simply rotated.

In the other version, the rotation includes the C flag.

38
----------------------------------------------------------------------------------------------------------------
ENCODING OF MACHINE INSTRUCTIONS
• To be executed in a processor, an instruction must be encoded in a binary-pattern. Such
encoded instructions are referred to as Machine Instructions.
• The instructions that use symbolic-names and acronyms are called assembly language
instructions.
• We have seen instructions that perform operations such as add, subtract, move, shift, rotate,
and branch. These instructions may use operands of different sizes, such as 32-bit and 8-bit
numbers.
• Let us examine some typical cases.

The instruction

Add R1, R2 ;

Has to specify the registers R1 and R2, in addition to the OP code. If theprocessor has 16
registers, then four bits are needed to identify each register.

39
Additional bits are needed to indicate that the Register addressing-mode is usedfor each
operand.

The instruction

Move 24(R0), R5 ;

Requires 16 bits to denote the OP code and the two registers, andsome bits to express that the
source operand uses the Indexaddressing mode and that the index value is 24.

• In all these examples, the instructions can be encoded in a 32-bit word (Fig 2.39).
• The OP code for given instruction refers to type of operation that is to be performed.
• Source and destination field refers to source and destination operand respectively.
• The "Other info" field allows us to specify the additional information that may be needed
such as anindex value or an immediate operand.
• Using multiple words, we can implement complex instructions, closely resembling
operations in highlevelprogramming languages. The term complex instruction set computers
(CISC) refers to processorsthat use
• CISC approach results in instructions of variable length, dependent on the number of
operands andthe type of addressing modes used.
• In RISC (reduced instruction set computers), any instruction occupies only one word.
• The RISC approach introduced other restrictions such as that all manipulation of data must
be doneon operands that are already in registers.

Ex: Add R1,R2,R3

• In RISC type machine, the memory references are limited to only Load/Store operations.

Problem 1:
Write a program that can evaluate the expression A*B+C*D In a single-accumulator
processor. Assume that the processor has Load, Store, Multiply, and Add instructions and
that all values fit in the accumulator

Solution:

40
A program for the expression is:

Load A
Multiply B
Store RESULT
Load C
Multiply D
Add RESULT
Store RESULT

Problem 2:

Registers R1 and R2 of a computer contains the decimal values 1200 and 4600. What is the
effective address of the memory operand in each of the following instructions?

(a) Load 20(R1), R5

(b) Move #3000,R5
(c) Store R5,30(R1,R2)
(d) Add -(R2),R5
(e) Subtract (R1)+,R5

Solution:

(a) EA = [R1]+Offset=1200+20 = 1220

(b) EA = 3000
(c) EA = [R1]+[R2]+Offset = 1200+4600+30=5830
(d) EA = [R2]-1 = 4599
(e) EA = [R1] = 1200

Problem 3:

Registers R1 and R2 of a computer contains the decimal values 2900 and 3300. What is the
effective address of the memory operand in each of the following instructions?

(a) Load R1,55(R2)

(b) Move #2000,R7
(c) Store 95(R1,R2),R5
(d) Add (R1)+,R5
(e) Subtract‐(R2),R5

Solution:
a) Load R1,55(R2) This is indexed addressing mode.

So EA = 55+R2=55+3300=3355.

b) Move #2000,R7 This is an immediate addressing mode. So, EA = 2000

41
c) Store 95(R1,R2),R5 This is a variation of indexed addressing mode, in which contents of
2 registers are added with the offset or index to generate EA. So,
95+R1+R2=95+2900+3300=6255.

d) Add (R1)+,R5 This is Autoincrement mode. Contents of R1 are the EA so, 2900 is the
EA.

e) Subtract -(R2),R5 This is Auto decrement mode. Here, R2 is subtracted by 4 bytes

(assuming 32‐bt processor) to generate the EA, so, EA= 3300‐4=3296.

Problem 4:

Given a binary pattern in some memory-location, is it possible to tell whether this pattern
represents a machine instruction or a number?

Solution:
No; any binary pattern can be interpreted as a number or as an instruction.

----------------------------------------------------------------------------------------------------------------

42