COMPUTER ORGANIZATION

(21CS34)

SANDEEP KUMAR

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CAMBRIDGE INSTITUTE OF TECHNOLOGY

K.R. PURAM, BANGALORE-560 036
21CS34 COMPUTER ORGANIZATION

Question Bank

MODULE -1: BASIC STRUCTURE OF COMPUTERS

1. Explain the different functional units of a computer.

2. Describe the operational concepts between the processor and memory (or)
With a neat diagram, discuss the operational concepts of a computer(or)
Draw and explain the connection between memory and processor with the respectiveregisters.
3. Explain the steps to execute an instruction.
4. Explain the bus structure of computer system
5. List the steps needed to execute the machine instruction Add LOCA, R0 in terms of transfer between
processor and the memory along with some simple control commands. Assume that the instruction itself is
stored in the memory at location INSTR and that this address initially in registers PC. The first two steps
might be expressed as:
• Transfer the content of register PC to register MAR
• Issue read command to the memory and then waits until it has transferred the requested word int
register MDR.
6. What is performance measurement? Or How to measure the performance of the computer? Explain the
overall SPEC rating for the computer ina program suite
7. Mention four types of operations to be performed by instructions in a computer. Explain with basic types
of instruction formats to carry out C =[A] + [B]
8. Write the difference between RISC and CISC processors.
9. 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.

10. List the steps needed to execute the machine instruction:

• Load R2, LOC
in terms of transfers between the components of processor and some simple control commands. Assume that
the address of the memory-location containing this instruction is initially in register PC.
11. List the steps needed to execute the machine instruction:
• Add R4, R2, R3
in terms of transfers between the components of processor and some simple control commands. Assume that
the address of the memory-location containing this instruction is initially in register PC.
12. A) Give a short sequence of machine instructions for the task “Add the contents of memory-location Ato
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. Add
instructions are described in Section 1.3. Do not change contents of either location A or B.
B) Suppose that Move and Add instructions are available with the formats:
Move Location1, Location2 and
Add Location1, Location2
These instructions move or add a copy of the operand at the second location to the first location, overwriting
the original operand at the first location. Either or both of the operands can be in the memory or 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.
13. For the following processor, obtain the performance. Clock rate = 800 MHz, No. of instructions executed =
1000, Average no of steps needed / machine instruction = 20

MODULE 1: MACHINE INSTRUCTIONS AND PROGRAMS

1. Explain the concept of memory location and address.
2. Explain little endian and big-endian memory assignment. Represent the number 64243848H in 32 bits big
endian and little-endian memory.
3. Explain the two types of memory operations.
4. Explain INSTRUCTION EXECUTION & STRAIGHT-LINE SEQUENCING.
5. Explain the concept of Branching.
6. Explain conditional codes.
7. What is an addressing mode? Explain different addressing modes, with example for each.
8. Explain indirection and pointers with an example.
9. Explain indexing and arrays with examples.
10. 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

11. 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?

Load 20(R1), R5
Move #3000,R5
Store R5,30(R1,R2)
Add -(R2),R5
Subtract (R1)+,R5

12. 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?
Load R1, 55(R2)
Move #2000, R7
Store 95(R1,R2), R5
Add (R1)+, R5
Subtract‐(R2), R5

13. Consider a Computer that has a byte addressable memory organized in 32 bit words according to the Bi-endian
scheme/little endian scheme . A program treads ASCII characters entered at a keyboard and store them in
successive byte locations, starting at location 1000. Show the content of the two memory words at locations
1000 and 1004 After the name “ Johnson” has been entered. (ASCII Codes : J=4A, o=6F, h=68, n=6E, s=73).
14. Write ALP program to copy 'N' numbers from array 'A' to array 'B' using indirect addresses. (Assume A and B
are the starting memory location of an array)

MODULE 2: INPUT/OUTPUTORGANIZATION
1. Draw the arrangement of a single bus structure and explain memory mapped I/O and I/O mapped I/O with
examples.
2. What are the three MECHANISMS USED FOR INTERFACING I/O-DEVICES.
3. What is an interrupt? Explain the transfer of program control through the use of interrupts with an example.
4. Explain interrupt hardware. / Explain how interrupt requests from several IO devices can be communicated to a
processor through a single INTR line.
5. Explain the following terms w r. to interrupt
i) Interrupt service routine(ISR) ii) Interrupt latency iii) enabling and disabling of interrupts.
6. Explain in detail, the situations where a number of devices capable of initiating interrupts are connected to the
processor? How to resolve the problems? /Explain following methods of handling interrupts from multiple devices.
i) i)Interrupt nesting/priority structure
ii) ii)Vectored interrupt
iii) iii)Simultaneous requests/Daisy chain technique.
7. What is an exception? Explain Recovery from Errors, Debugging , and Privilege Exception.
8. What is DMA and DMA controller?
9. Explain following w. r.to DMA
i) DMA controllers in a computer system.
ii) Registers in a DMA interface.
10. What is bus arbitration? Explain different approaches to bus arbitration.
11. Explain Centralized bus arbitration with diagrams.
12. Explain Distributed bus arbitration with examples.
13. What is a bus ? What are three types of buses.
14. Explain synchronous bus with a timing diagram for read operation.
15. Explain synchronous bus with a timing diagram for Multiple Cycle Read-operation.
16. Explain asynchronous bus with a timing diagram for read operation.
17. Explain parallel port.
18. Explain input interface circuit.
19. Explain output interface circuit.
20. Explain a serial port interface.
MODULE – 3: MEMORYSYSTEM
1. Draw the connection of memory to the processor and explain basic concepts.
2. Explain the internal organization of memory chips with a neat diagram./ Explain the organization of 16 words of 8
bits each memory cells ( ie.,16 x 8).
3. Draw the organization of 1024( or 1K) memory cells as 1K x 1 format.
4. Explain the operation of static Ram cell.
5. Explain the operation of single transistor dynamic memory cell.
6. Draw a diagram and explain the internal organization of 16 Megabits DRAM chip configured as 2MX8. Also
explain as at how it can be made to work in fast page mode.
.
7. Explain the working of 16-megabyte DRAM chip configured as 1M x 6 memory chip. (6 M) June 2014
8. Discuss the internal organization of a 2M x 8 asynchronous DRAM chip. (10M) Dec 2014
9. Explain Synchronous DRAM.
10. Explain the memory controller with a neat diagram.
11. Explain Rambus memory.
12. Explain the operation of a ROM cell.
13. Explain types of ROMs and mention their advantages and disadvantages/ Briefly explain any five non-volatile
memory concepts.
14. Explain with diagram the memory hierarchy with respect to speed, size and cost.
15. What is cache memory. Explain the use and operation of cache memory with a diagram.
16. Explain direct mapping with an example.
17. Explain associative mapping with an example.
18. Explain set-associative mapping with an example.
19. A program is to be run on a computer that has an instruction cache organized in the direct mapped manner and that
has t Main Memory Size 64K words, Cache size 1K words and Block size 128 word. Determine the following:
i)Number of bits in the TAG, BLOCK and WORD fields in main memory address.
ii) Number of bits in the main memory address.

20. A program is to be run on a computer that has an instruction cache organized in the Associative mapped manner
and that has the Main Memory Size 64K words, Cache size 1K words and Block size 128 word. Determine the
following:
i)Number of bits in the TAG and WORD fields in main memory address.
ii) Number of bits in the main memory address.
21. A block -set -associative cache consists of a total of 64 blocks divided into 4 block sets. The main memory
contains 4096 blocks, each consisting of 128 word. Determine:
i)Number of bits in the TAG, SET and WORD fields in main memory address.
ii) Number of bits in the main memory address.

22. A computer system has a main memory consisting of 1M 16 bit words. It also has a 4K word cache organized in
the block set associative manner, with 4 blocks per set and 64 word per block. Determine:
i)Number of bits in the TAG, SET and WORD fields in main memory address.
ii) Number of bits in the main memory address.

23. A computer system uses 16-bit memory addresses. It has a 2K-byte cache organized in a direct-mapped manner
with 64 bytes per cache block. Assume that the size of each memory word is 1 byte.
i. Calculate the number of bits in each of the Tag, Block, and Word fields of the memory address.

MODULE – 4: ARITHMETIC
1. List the different systems used to represent a signed number and give one example for each. Specify
which number representation system is preferred in a computer and why?
2. .Represent the decimal values 4, -4, 14, -12, 26, -16, 21 and -27 as signed 6-bit numbers in the
following binary formats:
(a) sign-and-magnitude
(b) 1’s-complement
(c) 2’s-complement
3. Perform the following operations on the 5 bit signed numbers using 2’s complement representation
system. Also indicate whether overflow has occurred.
(i)(-10)+ (-13) (ii) (-10) - (+4) (iii) (-3) + (-8) (iv) (-10) - (+7)
4. Convert the following pairs of decimal numbers to 5-bit 2’s-complement numbers, then add them. State
whether or not overflow occurs in each case.
(a) a) 4 and 12 b) 9 and 14
(b) c) –11 and 14 d) –6 and 12
(c) e) –7 and –13
5. Repeat Problem 4 for the subtract operation, where the second number of each pair is to be subtracted
from the first number. State whether or not overflow occurs in each case.
6. Perform following operations on the 6-bit signed numbers using 2's complement representation system.
Also indicate whether overflow has occurred.
i) 101010 + 010011
ii) 000111 – 100010
iii) 101000 + 100100
iv) 010000 - 101000
7. Explain the design and working of n- bit ripple carry adder.
8. Explain with a diagram the working of addition/subtraction logic unit/Design a logic circuit to perform
addition/subtraction of two ‘n’ bit numbers X and Y.

9. Explain with figure, the design and working of a 4-bit carry look ahead adder.
10. Explain with figure the design and working of a 16-bit carry look ahead adder built from 4 bit adders.
11. Explain the working of multiplication of positive numbers( Unsigned) using array implementation.
12. Explain the working of sequential circuit binary multiplier with an example.

MODULE 4 : BASIC PROCESSINGUNIT

1. Draw the Main hardware components of a processor and explain the steps needed to execute an instruction.
2. Draw and explain the single-bus organization of the data path inside a processor.
3. Explain with an example, the register transfer in single bus organization/ Explain a sequence of steps in which
data are transferred from one register to another with an example.
4. Explain with an example, how a processor performs arithmetic or logic operations and store the result in a
processor register.
5. Explain the control signals of MDR and MAR.
6. Explain the sequence of steps in fetching a word from memory with an example.
7. List out the actions needed to execute the instruction ADD (R3), R1. Write and explain the sequence of control
steps for the execution of the same.
8. Write and explain the control sequence for execution of an unconditional branch instruction.
9. Draw and explain multiple bus organization. Explain its advantages. /Explain the three - bus organization of the
processor.
10. Write down the control sequence for the instruction ADD R4, R5, R6 for three bus organization.
11. Discuss the organization of hardwired control unit.
12. With a neat sketch, explain the organization of a micro programmed control unit.
13. Differentiate hardwired and micro programmed control unit.
14. With an example, explain micro instructions.
15. Explain microprogram sequencing. Write the micro-routine for the instruction Add - (Rsrc), Rdst.
16. Explain wide branch addressing.
17. Explain MICROINSTRUCTIONS WITH NEXT-ADDRESS FIELDS.

Module 5: Parallel processing and Vector processing

18. Explain how parallel processing can be achieved with processor having multiple functional units.
19. Explain the pipelining operation with an example.
20. In certain scientific computations it is necessary to perform the arithmetic operation (Ai + Bi)(Ci + Di) with a
stream of numbers. Specify a pipeline configuration to cany out this task. thliste contents of all registers in the
pipeline for i = 1 through 6.
21. Explain the general structure of four segment pipelining.
22. Define the speedup ratio of pipeline.
23. Draw a space-time diagram for a six-segment pipeline showing the time it
takes to process eight tasks.
24. Determine the number of dock cydes that it takes to process 200 tasks in a
six-segment pipeline.
A non-pipeline system takes 50 ns to process a task. The same task can be processed in a six-segment pipeline
with a dock cycle of 10 ns. Determine the speedup ratio of the pipeline for 100 tasks. What is the maximum
speedup that can be achieved?
25. Explain arithmetic pipelining with an example.
26. Explain instruction pipelining with an example
27. Explain vector processing with an example.
28. Show the matrix multiplication pipelining.
29. Explain memory interleaving.
30. Explain Attached Array Processor.
31. Explain SIMD array processor.
COMPUTER ORGANIZATION

MODULE 1: BASIC STRUCTURE OF COMPUTERS

BASIC CONCEPTS
• Computer Architecture (CA) is concerned with the structure and behaviour of the computer.
• CA includes the information formats, the instruction set and techniques for addressing memory.
• In general covers, CA covers 3 aspects of computer-design namely: 1) Computer Hardware, 2)
Instruction set Architecture and 3) Computer Organization.
1. Computer Hardware
➢ It consists of electronic circuits, displays, magnetic and optical storage media and
communication facilities.
2. Instruction Set Architecture
➢ It is programmer visible machine interface such as instruction set, registers, memory
organization and exception handling.
➢ Two main approaches are 1) CISC and 2) RISC.
(CISC→Complex Instruction Set Computer, RISC→Reduced Instruction Set Computer)
3. Computer Organization
➢ It includes the high level aspects of a design, such as
→ memory-system
→ bus-structure &
→ design of the internal CPU.
➢ It refers to the operational units and their interconnections that realize the architectural
specifications.
➢ It describes the function of and design of the various units of digital computer that store and
process information.

FUNCTIONAL UNITS
• A computer consists of 5 functionally independent main parts:
1) Input
2) Memory
3) ALU
4) Output &
5) Control units.

1-1
COMPUTER ORGANIZATION
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.
• 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.
• The same instruction can be realized using 2 instructions as:
Load LOCA, R1
Add R1, R0
• 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 register R1.
Step 3: Add the content of Register R1 and the contents of register R0.
Step 4: Store the result (sum) in R0.

1-2
COMPUTER ORGANIZATION
MAIN PARTS OF PROCESSOR
• 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.
2) The contents of PC (i.e. address) are transferred to the MAR & control-unit issues Read signal to
memory.
3) After certain amount of elapsed time, the first instruction is read out of memory and placed into
MDR.
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 is
initiated.
10) At some point during execution, contents of PC are incremented to point to next instruction in the
program.

1-3
COMPUTER ORGANIZATION
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.
➢ 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.

1-4
COMPUTER ORGANIZATION
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.
• 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 is measured in cycles per second.

• Cycles per second is also called Hertz (Hz)

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

(1)
• Equ1 is referred to as the basic performance equation.
• To achieve high performance, the computer designer must reduce the value of T, which means
reducing 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.

1-5
COMPUTER ORGANIZATION
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.
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 application
domains. (SPEC → System Performance Evaluation Corporation).
• SPEC Rating is given by

• 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 = no. of programs in the suite.

INSTRUCTION SET: CISC AND RISC

RISC CISC
Simple instructions taking one cycle. Complex instructions taking multiple cycle.
Instructions are executed by hardwired control Instructions are executed by microprogrammed
unit. control unit.
Few instructions. Many instructions.
Fixed format instructions. Variable format instructions.
Few addressing modes, and most instructions Many addressing modes.
have register to register addressing mode.
Multiple register set. Single register set.
Highly pipelined. No pipelined or less pipelined.

Problem 1:
List the steps needed to execute the machine instruction:
Load R2, LOC
in terms of transfers between the components of processor and some simple control commands.
Assume that the address of the memory-location containing this instruction is initially in register PC.
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 1 to operand in ALU and transfer incremented address to PC.

1-6
COMPUTER ORGANIZATION
Problem 2:
List the steps needed to execute the machine instruction:
Add R4, R2, R3
in terms of transfers between the components of processor and some simple control commands.
Assume that the address of the memory-location containing this instruction is initially in register PC.
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 1 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.
Add instructions are described in Section 1.3. Do not change contents of either location A or B.
(b) Suppose that Move and Add instructions are available with the formats:
Move Location1, Location2
and
Add Location1, Location2
These instructions move or add a copy of the operand at the second location to the first location,
overwriting the original operand at the first location. Either or both of the operands can be in the
memory or 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.
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.

1-7
COMPUTER ORGANIZATION
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 for
the 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.

(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.

Problem 7:
(a) Suppose that execution time for a program is proportional to instruction fetch time. Assume that
fetching an instruction from the cache takes 1 time unit, but fetching it from the main-memory takes
10 time units. Also, assume that a requested instruction is found in the cache with probability 0.96.
Finally, assume that if an instruction is not found in the cache it must first be fetched from the main-
memory into the cache and then fetched from the cache to be executed. Compute the ratio of program
execution time without the cache to program execution time with the cache. This ratio is called the
speedup resulting from the presence of the cache.
(b) If the size of the cache is doubled, assume that the probability of not finding a requested
instruction there is cut in half. Repeat part (a) for a doubled cache size.
Solution:
(a) Let cache access time be 1 and main-memory access time be 20. Every instruction that is
executed must be fetched from the cache, and an additional fetch from the main-memory must
be performed for 4% of these cache accesses.
Therefore,

(b)

1-8
COMPUTER ORGANIZATION

MODULE 1 (CONT.): 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 distinct
addresses for each item location. (It is customary to use numbers from 0 through 2k-1 as the
addresses 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).

1-9
COMPUTER ORGANIZATION
BYTE-ADDRESSABILITY
• 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.

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.

• 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 Aligned in 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.

1-10
COMPUTER ORGANIZATION
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
• 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.

INSTRUCTIONS & INSTRUCTION SEQUENCING

• 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).

1-11
COMPUTER ORGANIZATION
REGISTER TRANSFER NOTATION (RTN)
• The possible locations in which transfer of information occurs are: 1) Memory-location 2) Processor
register & 3) Registers in I/O device.
Location Hardware Binary Address Example Description
Memory LOC, PLACE, NUM R1  [LOC] Contents of memory-location LOC
are transferred into register R1.
Processor R0, R1 ,R2 [R3]  [R1]+[R2] Add the contents of register R1 &R2
and places their sum into R3.
I/O Registers DATAIN, DATAOUT R1  DATAIN Contents of I/O register DATAIN are
transferred into register R1.

ASSEMBLY LANGUAGE NOTATION

• To represent machine instructions and programs, assembly language format is used.
Assembly Language Format Description
Move LOC, R1 Transfer data from memory-location LOC to register R1. The contents of LOC
are unchanged by the execution of this instruction, but the old contents of
register R1 are overwritten.
Add R1, R2, R3 Add the contents of registers R1 and R2, and places their sum into register R3.

BASIC INSTRUCTION TYPES

Instruction Syntax Example Description Instructions
Type for
Operation
C<-[A]+[B]
Three Opcode Source1,Source2,Destination Add A,B,C Add the contents of
Address memory-locations A & B.
Then, place the result into
location C.
Two Address Opcode Source, Destination Add A,B Add the contents of Move B, C
memory-locations A & B. Add A, C
Then, place the result into
location B, replacing the
original contents of this
location.
Operand B is both a source
and a destination.
One Address Opcode Source/Destination Load A Copy contents of memory- Load A
location A into accumulator. Add B
Add B Add contents of memory- Store C
location B to contents of
accumulator register &
place sum back into
accumulator.
Store C Copy the contents of the
accumulator into location C.
Zero Opcode [no Source/Destination] Push Locations of all operands Not possible
Address are defined implicitly.
The operands are stored in
a pushdown stack.
• Access to data in the registers is much faster than to data stored in memory-locations.
• Let Ri represent a general-purpose register. The instructions: Load A,Ri
Store Ri,A
Add A,Ri
are generalizations of the Load, Store and Add Instructions for the single-accumulator case, in which
register Ri performs the function of the accumulator.
• In processors, where arithmetic operations as allowed only on operands that are in registers, the task
C<-[A]+[B] can be performed by the instruction sequence:
Move A,Ri
Move B,Rj
Add Ri,Rj
Move Rj,C

1-12
COMPUTER ORGANIZATION
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 be
performed. The specified-operation is then performed by the processor.

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.

1-13
COMPUTER ORGANIZATION
BRANCHING
• 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.

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.

1-14
COMPUTER ORGANIZATION
ADDRESSING MODES
• The different ways in which the location of an operand is specified in an instruction are referred to as
Addressing Modes (Table 2.1).

IMPLEMENTATION OF VARIABLE AND CONSTANTS

• Variable is represented by allocating a memory-location to hold its value.
• Thus, the value can be changed as needed using appropriate instructions.
• There are 2 accessing modes to access the variables:
1) Register Mode
2) Absolute Mode
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.
Absolute (Direct) Mode
• The operand is in a memory-location.
• The address of memory-location is given explicitly in the instruction.
• 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.
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.

1-15
COMPUTER ORGANIZATION
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 of
register 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.

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.

1-16
COMPUTER ORGANIZATION
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 effective-
address.
• The constant X may be given either
→ as an explicit number or
→ as a symbolic-name representing a numerical value.

• 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.

1-17
COMPUTER ORGANIZATION
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.
• 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.
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.

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 location
identified by name LOOP if branch condition is satisfied.

ADDITIONAL ADDRESSING MODES

1) 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)+ ;where Ri=pointer-register.
2) 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.

1-18
COMPUTER ORGANIZATION
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:
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
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.

1-19
COMPUTER ORGANIZATION
Problem 6:
Register R5 is used in a program to point to the top of a stack. Write a sequence of instructions using
the Index, Autoincrement, and Autodecrement addressing modes to perform each of the following
tasks:
(a) Pop the top two items off the stack, and them, and then push the result onto the stack.
(b) Copy the fifth item from the top into register R3.
(c) Remove the top ten items from the stack.
Solution:
(a) Move (R5)+,R0
Add (R5)+,R0
Move R0,-(R5)
(b) Move 16(R5),R3
(c) Add #40,R5

Problem 7:
Consider the following possibilities for saving the return address of a subroutine:
(a) In the processor register.
(b) In a memory-location associated with the call, so that a different location is used when the
subroutine is called from different places
(c) On a stack.
Which of these possibilities supports subroutine nesting and which supports subroutine recursion(that
is, a subroutine that calls itself)?
Solution:
(a) Neither nesting nor recursion is supported.
(b) Nesting is supported, because different Call instructions will save the return address at
different memory-locations. Recursion is not supported.
(c) Both nesting and recursion are supported.

Problem 8: A memory Byte location contains the pattern 00101100. What does this pattern represent when
interpreted as a binary number ? What does it represent as an ASCII code ?

Solution:The number 44 and the ASCII punctuation character “ , ”

Problem 9:
Consider a Computer that has a byte addressable memory organized in 32 bit words according to the Bi-
endian scheme. A program treads ASCII characters entered at a keyboard and store them in successive byte
locations, starting at location 1000. Show the content of the two memory words at locations 1000 and 1004
After the name “ Johnson” has been entered.

Solution : Byte contents in hex, starting at location 1000, will be 4A, 6F, 68, 6E, 73, 6F, 6E. The two words at
1000 and 1004 will be 4A6F686E and 736F6EXX. Byte 1007 (shown as XX) is unchanged.

(ASCII Codes : J=4A, o=6F, h=68, n=6E, s=73).

Problem 10:
Consider a Computer that has a byte addressable memory organized in 32 bit words according to the little-
endian scheme. A program treads ASCII characters entered at a keyboard and store them in successive byte
locations, starting at location 1000. Show the content of the two memory words at locations 1000 and 1004
After the name “ Johnson” has been entered.

Solution: Byte contents in hex, starting at location 1000, will be 4A, 6F, 68, 6E, 73, 6F, 6E. The two words at
1000 and 1004 will be 6E686F4A and XX6E6F73. Byte 1007 (shown as XX) is unchanged.

1-20
COMPUTER ORGANIZATION

MODULE 2: INPUT/OUTPUT ORGANIZATION

ACCESSING I/O-DEVICES
• A single bus-structure can be used for connecting I/O-devices to a computer (Figure 7.1).
• Each I/O device is assigned a unique set of address.
• Bus consists of 3 sets of lines to carry address, data & control signals.
• When processor places an address on address-lines, the intended-device responds to the command.
• The processor requests either a read or write-operation.
• The requested-data are transferred over the data-lines.

• There are 2 ways to deal with I/O-devices: 1) Memory-mapped I/O & 2) I/O-mapped I/O.
1) Memory-Mapped I/O
➢ Memory and I/O-devices share a common address-space.
➢ Any data-transfer instruction (like Move, Load) can be used to exchange information.
➢ For example,
Move DATAIN, R0; This instruction sends the contents of location DATAIN to register R0.
Here, DATAIN → address of the input-buffer of the keyboard.
2) I/O-Mapped I/O
➢ Memory and I/0 address-spaces are different.
➢ A special instructions named IN and OUT are used for data-transfer.
➢ Advantage of separate I/O space: I/O-devices deal with fewer address-lines.
I/O Interface for an Input Device
1) Address Decoder: enables the device to recognize its address when this address
appears on the address-lines (Figure 7.2).
2) Status Register: contains information relevant to operation of I/O-device.
3) Data Register: holds data being transferred to or from processor. There are 2 types:
i) DATAIN → Input-buffer associated with keyboard.
ii) DATAOUT → Output data buffer of a display/printer.

2-1
COMPUTER ORGANIZATION

MECHANISMS USED FOR INTERFACING I/O-DEVICES

1) Program Controlled I/O
• Processor repeatedly checks status-flag to achieve required synchronization b/w processor & I/O
device. (We say that the processor polls the device).
• Main drawback:
The processor wastes time in checking status of device before actual data-transfer takes place.
2) Interrupt I/O
• I/O-device initiates the action instead of the processor.
• I/O-device sends an INTR signal over bus whenever it is ready for a data-transfer operation.
• Like this, required synchronization is done between processor & I/O device.
3) Direct Memory Access (DMA)
• Device-interface transfer data directly to/from the memory w/o continuous involvement by the
processor.
• DMA is a technique used for high speed I/O-device.

2-2
COMPUTER ORGANIZATION
INTERRUPTS
• There are many situations where other tasks can be performed while waiting for an I/O device to
become ready.
• A hardware signal called an Interrupt will alert the processor when an I/O device becomes ready.
• Interrupt-signal is sent on the interrupt-request line.
• The processor can be performing its own task without the need to continuously check the I/O-device.
• The routine executed in response to an interrupt-request is called ISR.
• The processor must inform the device that its request has been recognized by sending INTA signal.
(INTR → Interrupt Request, INTA → Interrupt Acknowledge, ISR → Interrupt Service Routine)
• For example, consider COMPUTE and PRINT routines (Figure 3.6).

• The processor first completes the execution of instruction i.

• Then, processor loads the PC with the address of the first instruction of the ISR.
• After the execution of ISR, the processor has to come back to instruction i+1.
• Therefore, when an interrupt occurs, the current content of PC is put in temporary storage location.
• A return at the end of ISR reloads the PC from that temporary storage location.
• This causes the execution to resume at instruction i+1.
• When processor is handling interrupts, it must inform device that its request has been recognized.
• This may be accomplished by INTA signal.
• The task of saving and restoring the information can be done automatically by the processor.
• The processor saves only the contents of PC & Status register.
• Saving registers also increases the Interrupt Latency.
• Interrupt Latency is a delay between
→ time an interrupt-request is received and
→ start of the execution of the ISR.
• Generally, the long interrupt latency in unacceptable.

Difference between Subroutine & ISR

Subroutine ISR
A subroutine performs a function required by the ISR may not have anything in common with
program from which it is called. program being executed at time INTR is received
Subroutine is just a linkage of 2 or more function Interrupt is a mechanism for coordinating I/O
related to each other. transfers.

2-3
COMPUTER ORGANIZATION
INTERRUPT HARDWARE
• Most computers have several I/O devices that can request an interrupt.
• A single interrupt-request (IR) line may be used to serve n devices (Figure 4.6).
• All devices are connected to IR line via switches to ground.
• To request an interrupt, a device closes its associated switch.
• Thus, if all IR signals are inactive, the voltage on the IR line will be equal to Vdd.
• When a device requests an interrupt, the voltage on the line drops to 0.
• This causes the INTR received by the processor to go to 1.
• The value of INTR is the logical OR of the requests from individual devices.
INTR=INTR1+ INTR2+ ............... +INTRn
• A special gates known as open-collector or open-drain are used to drive the INTR line.
• The Output of the open collector control is equal to a switch to the ground that is
→ open when gates input is in ”0‟ state and
→ closed when the gates input is in “1‟ state.
• Resistor R is called a Pull-up Resistor because
it pulls the line voltage up to the high-voltage state when the switches are open.

ENABLING & DISABLING INTERRUPTS

• All computers fundamentally should be able to enable and disable interruptions as desired.
• The problem of infinite loop occurs due to successive interruptions of active INTR signals.
• There are 3 mechanisms to solve problem of infinite loop:
1) Processor should ignore the interrupts until execution of first instruction of the ISR.
2) Processor should automatically disable interrupts before starting the execution of the ISR.
3) Processor has a special INTR line for which the interrupt-handling circuit.
Interrupt-circuit responds only to leading edge of signal. Such line is called edge-triggered.
• Sequence of events involved in handling an interrupt-request:
1) The device raises an interrupt-request.
2) The processor interrupts the program currently being executed.
3) Interrupts are disabled by changing the control bits in the processor status register (PS).
4) The device is informed that its request has been recognized.
In response, the device deactivates the interrupt-request signal.
5) The action requested by the interrupt is performed by the interrupt-service routine.
6) Interrupts are enabled and execution of the interrupted program is resumed.

2-4
COMPUTER ORGANIZATION
HANDLING MULTIPLE DEVICES
• While handling multiple devices, the issues concerned are:
1) How can the processor recognize the device requesting an interrupt?
2) How can the processor obtain the starting address of the appropriate ISR?
3) Should a device be allowed to interrupt the processor while another interrupt is being
serviced?
4) How should 2 or more simultaneous interrupt-requests be handled?

POLLING
• Information needed to determine whether device is requesting interrupt is available in status-register
• Following condition-codes are used:
➢ DIRQ → Interrupt-request for display.
➢ KIRQ → Interrupt-request for keyboard.
➢ KEN → keyboard enable.
➢ DEN → Display Enable.
➢ SIN, SOUT → status flags.
• For an input device, SIN status flag in used.
SIN = 1 → when a character is entered at the keyboard.
SIN = 0 → when the character is read by processor.
IRQ=1 → when a device raises an interrupt-requests (Figure 4.3).
• Simplest way to identify interrupting-device is to have ISR poll all devices connected to bus.
• The first device encountered with its IRQ bit set is serviced.
• After servicing first device, next requests may be serviced.
• Advantage: Simple & easy to implement.
Disadvantage: More time spent polling IRQ bits of all devices.

2-5
COMPUTER ORGANIZATION
VECTORED INTERRUPTS
• A device requesting an interrupt identifies itself by sending a special-code to processor over bus.
• Then, the processor starts executing the ISR.
• The special-code indicates starting-address of ISR.
• The special-code length ranges from 4 to 8 bits.
• The location pointed to by the interrupting-device is used to store the staring address to ISR.
• The staring address to ISR is called the interrupt vector.
• Processor
→ loads interrupt-vector into PC &
→ executes appropriate ISR.
• When processor is ready to receive interrupt-vector code, it activates INTA line.
• Then, I/O-device responds by sending its interrupt-vector code & turning off the INTR signal.
• The interrupt vector also includes a new value for the Processor Status Register.

CONTROLLING DEVICE REQUESTS

• Following condition-codes are used:
➢ KEN → Keyboard Interrupt Enable.
➢ DEN → Display Interrupt Enable.
➢ KIRQ/DIRQ → Keyboard/Display unit requesting an interrupt.
• There are 2 independent methods for controlling interrupt-requests. (IE → interrupt-enable).
1) At Device-end
IE bit in a control-register determines whether device is allowed to generate an interrupt-request.
2) At Processor-end, interrupt-request is determined by
→ IE bit in the PS register or
→ Priority structure

2-6
COMPUTER ORGANIZATION
INTERRUPT NESTING
• A multiple-priority scheme is implemented by using separate INTR & INTA lines for each device
• Each INTR line is assigned a different priority-level (Figure 4.7).
• Priority-level of processor is the priority of program that is currently being executed.
• Processor accepts interrupts only from devices that have higher-priority than its own.
• At the time of execution of ISR for some device, priority of processor is raised to that of the device.
• Thus, interrupts from devices at the same level of priority or lower are disabled.
Privileged Instruction
• Processor's priority is encoded in a few bits of PS word. (PS → Processor-Status).
• Encoded-bits can be changed by Privileged Instructions that write into PS.
• Privileged-instructions can be executed only while processor is running in Supervisor Mode.
• Processor is in supervisor-mode only when executing operating-system routines.
Privileged Exception
• User program cannot
→ accidently or intentionally change the priority of the processor &
→ disrupt the system-operation.
• An attempt to execute a privileged-instruction while in user-mode leads to a Privileged Exception.

2-7
COMPUTER ORGANIZATION
SIMULTANEOUS REQUESTS
• The processor must have some mechanisms to decide which request to service when simultaneous
requests arrive.
• INTR line is common to all devices (Figure 4.8a).
• INTA line is connected in a daisy-chain fashion.
• INTA signal propagates serially through devices.
• When several devices raise an interrupt-request, INTR line is activated.
• Processor responds by setting INTA line to 1. This signal is received by device 1.
• Device-1 passes signal on to device 2 only if it does not require any service.
• If device-1 has a pending-request for interrupt, the device-1
→ blocks INTA signal &
→ proceeds to put its identifying-code on data-lines.
• Device that is electrically closest to processor has highest priority.
• Advantage: It requires fewer wires than the individual connections.
Arrangement of Priority Groups
• Here, the devices are organized in groups & each group is connected at a different priority level.
• Within a group, devices are connected in a daisy chain. (Figure 4.8b).

2-8
COMPUTER ORGANIZATION
EXCEPTIONS
• An interrupt is an event that causes
→ execution of one program to be suspended &
→ execution of another program to begin.
• Exception refers to any event that causes an interruption. For ex: I/O interrupts.
1. Recovery from Errors
• These are techniques to ensure that all hardware components are operating properly.
• For ex: Many computers include an ECC in memory which allows detection of errors in stored-data.
(ECC → Error Checking Code, ESR → Exception Service Routine).
• If an error occurs, control-hardware
→ detects the errors &
→ informs processor by raising an interrupt.
• When exception processing is initiated (as a result of errors), processor.
→ suspends program being executed &
→ starts an ESR. This routine takes appropriate action to recover from the error.
2. Debugging
• Debugger
→ is used to find errors in a program and
→ uses exceptions to provide 2 important facilities: i) Trace & ii) Breakpoints
i) Trace
• When a processor is operating in trace-mode, an exception occurs after execution of every instruction
(using debugging-program as ESR).
• Debugging-program enables user to examine contents of registers, memory-locations and so on.
• On return from debugging-program,
next instruction in program being debugged is executed,
then debugging-program is activated again.
• The trace exception is disabled during the execution of the debugging-program.
ii) Breakpoints
• Here, the program being debugged is interrupted only at specific points selected by user.
• An instruction called Trap (or Software interrupt) is usually provided for this purpose.
• When program is executed & reaches breakpoint, the user can examine memory & register contents.
3. Privilege Exception
• To protect OS from being corrupted by user-programs, Privileged Instructions are executed only
while processor is in supervisor-mode.
• For e.g.
When processor runs in user-mode, it will not execute instruction that change priority of processor.
• An attempt to execute privileged-instruction will produce a Privilege Exception.
• As a result, processor switches to supervisor-mode & begins to execute an appropriate routine in OS.

2-9
COMPUTER ORGANIZATION
DIRECT MEMORY ACCESS (DMA)
• The transfer of a block of data directly b/w an external device & main-memory w/o continuous
involvement by processor is called DMA.
• DMA controller
→ is a control circuit that performs DMA transfers (Figure 8.13).
→ is a part of the I/O device interface.
→ performs the functions that would normally be carried out by processor.
• While a DMA transfer is taking place, the processor can be used to execute another program.

• DMA interface has three registers (Figure 8.12):

1) First register is used for storing starting-address.
2) Second register is used for storing word-count.
3) Third register contains status- & control-flags.

• The R/W bit determines direction of transfer.

If R/W=1, controller performs a read-operation (i.e. it transfers data from memory to I/O),
Otherwise, controller performs a write-operation (i.e. it transfers data from I/O to memory).
• If Done=1, the controller
→ has completed transferring a block of data and
→ is ready to receive another command. (IE → Interrupt Enable).
• If IE=1, controller raises an interrupt after it has completed transferring a block of data.
• If IRQ=1, controller requests an interrupt.
• Requests by DMA devices for using the bus are always given higher priority than processor requests.
• There are 2 ways in which the DMA operation can be carried out:
1) Processor originates most memory-access cycles.
➢ DMA controller is said to "steal" memory cycles from processor.
➢ Hence, this technique is usually called Cycle Stealing.
2) DMA controller is given exclusive access to main-memory to transfer a block of data without
any interruption. This is known as Block Mode (or burst mode).

2-10
COMPUTER ORGANIZATION
BUS ARBITRATION
• The device that is allowed to initiate data-transfers on bus at any given time is called bus-master.
• There can be only one bus-master at any given time.
• Bus Arbitration is the process by which
→ next device to become the bus-master is selected &
→ bus-mastership is transferred to that device.
• The two approaches are:
1) Centralized Arbitration: A single bus-arbiter performs the required arbitration.
2) Distributed Arbitration: All devices participate in selection of next bus-master.
• A conflict may arise if both the processor and a DMA controller or two DMA controllers try to use the
bus at the same time to access the main-memory.
• To resolve this, an arbitration procedure is implemented on the bus to coordinate the activities of all
devices requesting memory transfers.
• The bus arbiter may be the processor or a separate unit connected to the bus.

2-11
COMPUTER ORGANIZATION
CENTRALIZED ARBITRATION
• A single bus-arbiter performs the required arbitration (Figure: 4.20).
• Normally, processor is the bus-master.
• Processor may grant bus-mastership to one of the DMA controllers.
• A DMA controller indicates that it needs to become bus-master by activating BR line.
• The signal on the BR line is the logical OR of bus-requests from all devices connected to it.
• Then, processor activates BG1 signal indicating to DMA controllers to use bus when it becomes free.
• BG1 signal is connected to all DMA controllers using a daisy-chain arrangement.
• If DMA controller-1 is requesting the bus,
Then, DMA controller-1 blocks propagation of grant-signal to other devices.
Otherwise, DMA controller-1 passes the grant downstream by asserting BG2.
• Current bus-master indicates to all devices that it is using bus by activating BBSY line.
• The bus-arbiter is used to coordinate the activities of all devices requesting memory transfers.
• Arbiter ensures that only 1 request is granted at any given time according to a priority scheme.
(BR → Bus-Request, BG → Bus-Grant, BBSY → Bus Busy).

• The timing diagram shows the sequence of events for the devices connected to the processor.
• DMA controller-2
→ requests and acquires bus-mastership and
→ later releases the bus. (Figure: 4.21).
• After DMA controller-2 releases the bus, the processor resources bus-mastership.

2-12
COMPUTER ORGANIZATION
DISTRIBUTED ARBITRATION
• All device participate in the selection of next bus-master (Figure 4.22).
• Each device on bus is assigned a 4-bit identification number (ID).
• When 1 or more devices request bus, they
→ assert Start-Arbitration signal &
→ place their 4-bit ID numbers on four open-collector lines ARB 0 through ARB 3 .
• A winner is selected as a result of interaction among signals transmitted over these lines.
• Net-outcome is that the code on 4 lines represents request that has the highest ID number.
• Advantage:
This approach offers higher reliability since operation of bus is not dependent on any single device.

For example:
➢ Assume 2 devices A & B have their ID 5 (0101), 6 (0110) and their code is 0111.
➢ Each device compares the pattern on the arbitration line to its own ID starting from MSB.
➢ If the device detects a difference at any bit position, it disables the drivers at that bit position.
➢ Driver is disabled by placing ”0” at the input of the driver.
➢ In e.g. “A” detects a difference in line ARB1, hence it disables the drivers on lines ARB1 & ARB0.
➢ This causes pattern on arbitration-line to change to 0110. This means that “B” has won
contention.

2-13
COMPUTER ORGANIZATION
BUS
• Bus
→ is used to inter-connect main-memory, processor & I/O-devices
→ includes lines needed to support interrupts & arbitration.

2-14
COMPUTER ORGANIZATION
• Primary function: To provide a communication-path for transfer of data.
• Bus protocol is set of rules that govern the behavior of various devices connected to the buses.
• Bus-protocol specifies parameters such as:
→ asserting control-signals
→ timing of placing information on bus
→ rate of data-transfer.
• A typical bus consists of 3 sets of lines:
1) Address,
2) Data &
3) Control lines.
• Control-signals
→ specify whether a read or a write-operation is to be performed.
→ carry timing information i.e. they specify time at which I/O-devices place data on the bus.
• R/W line specifies
→ read-operation when R/W=1.
→ write-operation when R/W=0.
• During data-transfer operation,
➢ One device plays the role of a bus-master.
➢ Master-device initiates the data-transfer by issuing read/write command on the bus.
➢ The device addressed by the master is called as Slave.
• Two types of Buses: 1) Synchronous and 2) Asynchronous.
SYNCHRONOUS BUS
• All devices derive timing-information from a common clock-line.
• Equally spaced pulses on this line define equal time intervals.
• During a ”bus cycle‟, one data-transfer can take place.
A sequence of events during a read-operation
• At time t0, the master (processor)
→ places the device-address on address-lines &
→ sends an appropriate command on control-lines (Figure 7.3).
• The command will
→ indicate an input operation &
→ specify the length of the operand to be read.
• Information travels over bus at a speed determined by physical & electrical characteristics.
• Clock pulse width(t1-t0) must be longer than max. propagation-delay b/w devices connected to bus.
• The clock pulse width should be long to allow the devices to decode the address & control signals.
• The slaves take no action or place any data on the bus before t1.
• Information on bus is unreliable during the period t0 to t1 because signals are changing state.
• Slave places requested input-data on data-lines at time t1.
• At end of clock cycle (at time t2), master strobes (captures) data on data-lines into its input-buffer
• For data to be loaded correctly into a storage device,
data must be available at input of that device for a period greater than setup-time of device.

2-15
COMPUTER ORGANIZATION

2-16
COMPUTER ORGANIZATION
A Detailed Timing Diagram for the Read-operation

• The picture shows two views of the signal except the clock (Figure 7.4).
• One view shows the signal seen by the master & the other is seen by the salve.
• Master sends the address & command signals on the rising edge at the beginning of clock period (t0).
• These signals do not actually appear on the bus until tam.
• Sometimes later, at tAS the signals reach the slave.
• The slave decodes the address.
• At t1, the slave sends the requested-data.
• At t2, the master loads the data into its input-buffer.
• Hence the period t2, tDM is the setup time for the master‟s input-buffer.
• The data must be continued to be valid after t2, for a period equal to the hold time of that buffers.
Disadvantages
• The device does not respond.
• The error will not be detected.

2-17
COMPUTER ORGANIZATION
Multiple Cycle Transfer for Read-operation

• During, clock cycle-1, master sends address/command info the bus requesting a “read‟ operation.
• The slave receives & decodes address/command information (Figure 7.5).
• At the active edge of the clock i.e. the beginning of clock cycle-2, it makes accession to respond
immediately.
• The data become ready & are placed in the bus at clock cycle-3.
• At the same times, the slave asserts a control signal called slave-ready.
• The master strobes the data to its input-buffer at the end of clock cycle-3.
• The bus transfer operation is now complete.
• And the master sends a new address to start a new transfer in clock cycle4.
• The slave-ready signal is an acknowledgement from the slave to the master.

2-18
COMPUTER ORGANIZATION
ASYNCHRONOUS BUS
• This method uses handshake-signals between master and slave for coordinating data-transfers.
• There are 2 control-lines:
1) Master-Ready (MR) is used to indicate that master is ready for a transaction.
2) Slave-Ready (SR) is used to indicate that slave is ready for a transaction.
The Read Operation proceeds as follows:
• At t0, master places address/command information on bus.
• At t1, master sets MR-signal to 1 to inform all devices that the address/command-info is ready.
➢ MR-signal =1 → causes all devices on the bus to decode the address.
➢ The delay t1 – t0 is intended to allow for any skew that may occurs on the bus.
➢ Skew occurs when 2 signals transmitted from 1 source arrive at destination at different time
➢ Therefore, the delay t1 – t0 should be larger than the maximum possible bus skew.
• At t2, slave
→ performs required input-operation &
→ sets SR signal to 1 to inform all devices that it is ready (Figure 7.6).
• At t3, SR signal arrives at master indicating that the input-data are available on bus.
• At t4, master removes address/command information from bus.
• At t5, when the device-interface receives the 1-to-0 transition of MR signal, it removes data and SR
signal from the bus. This completes the input transfer.

• A change of state is one signal is followed by a change is the other signal. Hence this scheme is
called as Full Handshake.
• Advantage: It provides the higher degree of flexibility and reliability.

2-19
COMPUTER ORGANIZATION

MODULE 2: INPUT/OUTPUT ORGANIZATION (CONT.)

INTERFACE-CIRCUITS
• An I/O Interface consists of the circuitry required to connect an I/O device to a computer-bus.
• On one side of the interface, we have bus signals.
On the other side, we have a data path with its associated controls to transfer data between the
interface and the I/O device known as port.
• Two types are:
1. Parallel Port transfers data in the form of a number of bits (8 or 16) simultaneously to or
from the device.
2. Serial Port transmits and receives data one bit at a time.
• Communication with the bus is the same for both formats.
• The conversion from the parallel to the serial format, and vice versa, takes place inside the interface-
circuit.
• In parallel-port, the connection between the device and the computer uses
→ a multiple-pin connector and
→ a cable with as many wires.
• This arrangement is suitable for devices that are physically close to the computer.
• In serial port, it is much more convenient and cost-effective where longer cables are needed.
Functions of I/O Interface
1) Provides a storage buffer for at least one word of data.
2) Contains status-flags that can be accessed by the processor to determine whether the buffer
is full or empty.
3) Contains address-decoding circuitry to determine when it is being addressed by the
processor.
4) Generates the appropriate timing signals required by the bus control scheme.
5) Performs any format conversion that may be necessary to transfer data between the bus and
the I/O device (such as parallel-serial conversion in the case of a serial port).

2-20
COMPUTER ORGANIZATION
PARALLEL-PORT
KEYBOARD INTERFACED TO PROCESSOR

• The output of the encoder consists of

→ bits representing the encoded character and
→ one signal called valid, which indicates the key is pressed.
• The information is sent to the interface-circuits (Figure 7.10).
• Interface-circuits contain
1) Data register DATAIN &
2) Status-flag SIN.
• When a key is pressed, the Valid signal changes from 0 to1.
Then, SIN=1 → when ASCII code is loaded into DATAIN.
SIN = 0 → when processor reads the contents of the DATAIN.
• The interface-circuit is connected to the asynchronous bus.
• Data transfers on the bus are controlled using the handshake signals:
1) Master ready &
2) Slave ready.

2-21
COMPUTER ORGANIZATION
INPUT-INTERFACE-CIRCUIT

Figure 4.29: Input-interface-circuit

• Output-lines of DATAIN are connected to the data-lines of bus by means of 3-state drivers (Fig 4.29).
• Drivers are turned on when
→ processor issues a read signal and
→ address selects DATAIN.
• SIN signal is generated using a status-flag circuit (Figure 4.30).
SIN signal is connected to line D0 of the processor-bus using a 3‐state driver.
• Address-decoder selects the input-interface based on bits A1 through A31.
• Bit A0 determines whether the status or data register is to be read, when Master‐ready is active.
• Processor activates the Slave‐ready signal, when either the Read‐status or Read‐data is equal to 1.

2-22
COMPUTER ORGANIZATION
PRINTER INTERFACED TO PROCESSOR

• Keyboard is connected to a processor using a parallel-port.

• Processor uses
→ memory‐mapped I/O and
→ asynchronous bus protocol.
• On the processor-side of the interface, we have:
→ Data-lines
→ Address-lines
→ Control or R/W line
→ Master‐Ready signal and
→ Slave‐Ready signal.
• On the keyboard-side of the interface, we have:
→ Encoder-circuit which generates a code for the key pressed.
→ Debouncing-circuit which eliminates the effect of a key.
→ Data-lines which contain the code for the key.
→ Valid line changes from 0 to 1 when the key is pressed. This causes the code to be loaded
into DATAIN and SIN to be set to 1.

2-23
COMPUTER ORGANIZATION
GENERAL 8 BIT PARALLEL PROCESSING

Figure 4.34: General 8 bit parallel interface

• Data-lines P7 through PO can be used for either input or output purposes (Figure 4.34).
• For increased flexibility,
→ some lines can be used as inputs and
→ some lines can be used as outputs.
• The DATAOUT register is connected to data-lines via 3-state drivers that are controlled by a DDR.
• The processor can write any 8-bit pattern into DDR. (DDR → Data Direction Register).
• If DDR=1,
Then, data-line acts as an output-line;
Otherwise, data-line acts as an input-line.
• Two lines, C1 and C2 are used to control the interaction between interface-circuit and I/0 device.
Two lines, C1 and C2 are also programmable.
• Line C2 is bidirectional to provide different modes of signaling, including the handshake.
• The Ready and Accept lines are the handshake control lines on the processor-bus side.
Hence, the Ready and Accept lines can be connected to Master-ready and Slave-ready.
• The input signal My-address should be connected to the output of an address-decoder.
The address-decoder recognizes the address assigned to the interface.
• There are 3 register select lines: RS0-RS2.
Three register select lines allows up to eight registers in the interface.
• An interrupt-request INTR is also provided.
INTR should be connected to the interrupt-request line on the computer-bus.

2-24
COMPUTER ORGANIZATION

MODULE 3: MEMORY SYSTEM

BASIC CONCEPTS
• Maximum size of memory that can be used in any computer is determined by addressing mode.

• If MAR is k-bits long then

→ memory may contain upto 2K addressable-locations
• If MDR is n-bits long, then
→ n-bits of data are transferred between the memory and processor.
• The data-transfer takes place over the processor-bus (Figure 8.1).
• The processor-bus has
1) Address-Line
2) Data-line &
3) Control-Line (R/W‟, MFC – Memory Function Completed).
• The Control-Line is used for coordinating data-transfer.
• The processor reads the data from the memory by
→ loading the address of the required memory-location into MAR and
→ setting the R/W‟ line to 1.
• The memory responds by
→ placing the data from the addressed-location onto the data-lines and
→ confirms this action by asserting MFC signal.
• Upon receipt of MFC signal, the processor loads the data from the data-lines into MDR.
• The processor writes the data into the memory-location by
→ loading the address of this location into MAR &
→ setting the R/W‟ line to 0.
• Memory Access Time: It is the time that elapses between
→ initiation of an operation &
→ completion of that operation.
• Memory Cycle Time: It is the minimum time delay that required between the initiation of the two
successive memory-operations.

3-1
COMPUTER ORGANIZATION
RAM (Random Access Memory)
• In RAM, any location can be accessed for a Read/Write-operation in fixed amount of time,
Cache Memory
➢ It is a small, fast memory that is inserted between
→ larger slower main-memory and
→ processor.
➢ It holds the currently active segments of a program and their data.
Virtual Memory
➢ The address generated by the processor is referred to as a virtual/logical address.
➢ The virtual-address-space is mapped onto the physical-memory where data are actually
stored.
➢ The mapping-function is implemented by MMU. (MMU = memory management unit).
➢ Only the active portion of the address-space is mapped into locations in the physical-memory.
➢ The remaining virtual-addresses are mapped onto the bulk storage devices such as magnetic
disk.
➢ As the active portion of the virtual-address-space changes during program execution, the
MMU
→ changes the mapping-function &
→ transfers the data between disk and memory.
➢ During every memory-cycle, MMU determines whether the addressed-page is in the memory.
If the page is in the memory.
Then, the proper word is accessed and execution proceeds.
Otherwise, a page containing desired word is transferred from disk to memory.
• Memory can be classified as follows:
1) RAM which can be further classified as follows:
i) Static RAM
ii) Dynamic RAM (DRAM) which can be further classified as synchronous & asynchronous
DRAM.
2) ROM which can be further classified as follows:
i) PROM
ii) EPROM
iii) EEPROM &
iv) Flash Memory which can be further classified as Flash Cards & Flash Drives.

3-2
COMPUTER ORGANIZATION
SEMI CONDUCTOR RAM MEMORIES
INTERNAL ORGANIZATION OF MEMORY-CHIPS
• Memory-cells are organized in the form of array (Figure 8.2).
• Each cell is capable of storing 1-bit of information.
• Each row of cells forms a memory-word.
• All cells of a row are connected to a common line called as Word-Line.
• The cells in each column are connected to Sense/Write circuit by 2-bit-lines.
• The Sense/Write circuits are connected to data-input or output lines of the chip.
• During a write-operation, the sense/write circuit
→ receive input information &
→ store input info in the cells of the selected word.

• The data-input and data-output of each Sense/Write circuit are connected to a single bidirectional
data-line.
• Data-line can be connected to a data-bus of the computer.
• Following 2 control lines are also used:
1) R/W’ → Specifies the required operation.
2) CS’ → Chip Select input selects a given chip in the multi-chip memory-system.

3-3
COMPUTER ORGANIZATION
STATIC RAM (OR MEMORY)
• Memories consist of circuits capable of retaining their state as long as power is applied are known.

• Two inverters are cross connected to form a latch (Figure 8.4).

• The latch is connected to 2-bit-lines by transistors T1 and T2.
• The transistors act as switches that can be opened/closed under the control of the word-line.
• When the word-line is at ground level, the transistors are turned off and the latch retain its state.
Read Operation
• To read the state of the cell, the word-line is activated to close switches T1 and T2.
• If the cell is in state 1, the signal on bit-line b is high and the signal on the bit-line b‟ is low.
• Thus, b and b‟ are complement of each other.
• Sense/Write circuit
→ monitors the state of b & b‟ and
→ sets the output accordingly.
Write Operation
• The state of the cell is set by
→ placing the appropriate value on bit-line b and its complement on b‟ and
→ then activating the word-line. This forces the cell into the corresponding state.
• The required signal on the bit-lines is generated by Sense/Write circuit.

CMOS Cell
• Transistor pairs (T3, T5) and (T4, T6) form the inverters in the latch (Figure 8.5).
• In state 1, the voltage at point X is high by having T5, T6 ON and T4, T5 are OFF.
• Thus, T1 and T2 returned ON (Closed), bit-line b and b‟ will have high and low signals respectively.
• Advantages:
1) It has low power consumption „.‟ the current flows in the cell only when the cell is active.
2) Static RAM‟s can be accessed quickly. It access time is few nanoseconds.
• Disadvantage: SRAMs are said to be volatile memories „.‟ their contents are lost when power is
interrupted.

3-4
COMPUTER ORGANIZATION
ASYNCHRONOUS DRAM
• Less expensive RAMs can be implemented if simple cells are used.
• Such cells cannot retain their state indefinitely. Hence they are called Dynamic RAM (DRAM).
• The information stored in a dynamic memory-cell in the form of a charge on a capacitor.
• This charge can be maintained only for tens of milliseconds.
• The contents must be periodically refreshed by restoring this capacitor charge to its full value.

• In order to store information in the cell, the transistor T is turned „ON‟ (Figure 8.6).
• The appropriate voltage is applied to the bit-line which charges the capacitor.
• After the transistor is turned off, the capacitor begins to discharge.
• Hence, info. stored in cell can be retrieved correctly before threshold value of capacitor drops down.
• During a read-operation,
→ transistor is turned „ON‟
→ a sense amplifier detects whether the charge on the capacitor is above the threshold value.
➢ If (charge on capacitor) > (threshold value) → Bit-line will have logic value „1‟.
➢ If (charge on capacitor) < (threshold value) → Bit-line will set to logic value „0‟.

3-5
COMPUTER ORGANIZATION
ASYNCHRONOUS DRAM DESCRIPTION
• The 4 bit cells in each row are divided into 512 groups of 8 (Figure 5.7).
• 21 bit address is needed to access a byte in the memory. 21 bit is divided as follows:
1) 12 address bits are needed to select a row.
i.e. A8-0 → specifies row-address of a byte.
2) 9 bits are needed to specify a group of 8 bits in the selected row.
i.e. A20-9 → specifies column-address of a byte.

• During Read/Write-operation,
→ row-address is applied first.
→ row-address is loaded into row-latch in response to a signal pulse on RAS’ input of chip.
(RAS = Row-address Strobe CAS = Column-address Strobe)
• When a Read-operation is initiated, all cells on the selected row are read and refreshed.
• Shortly after the row-address is loaded, the column-address is
→ applied to the address pins &
→ loaded into CAS’.
• The information in the latch is decoded.
• The appropriate group of 8 Sense/Write circuits is selected.
R/W’=1(read-operation) → Output values of selected circuits are transferred to data-lines D0-D7.
R/W’=0(write-operation) → Information on D0-D7 are transferred to the selected circuits.
• RAS‟ & CAS‟ are active-low so that they cause latching of address when they change from high to
low.
• To ensure that the contents of DRAMs are maintained, each row of cells is accessed periodically.
• A special memory-circuit provides the necessary control signals RAS‟ & CAS‟ that govern the timing.
• The processor must take into account the delay in the response of the memory.
Fast Page Mode
➢ Transferring the bytes in sequential order is achieved by applying the consecutive sequence
of column-address under the control of successive CAS‟ signals.
➢ This scheme allows transferring a block of data at a faster rate.
➢ The block of transfer capability is called as fast page mode.

3-6
COMPUTER ORGANIZATION
SYNCHRONOUS DRAM
• The operations are directly synchronized with clock signal (Figure 8.8).
• The address and data connections are buffered by means of registers.
• The output of each sense amplifier is connected to a latch.
• A Read-operation causes the contents of all cells in the selected row to be loaded in these latches.
• Data held in latches that correspond to selected columns are transferred into data-output register.
• Thus, data becoming available on the data-output pins.

• First, the row-address is latched under control of RAS‟ signal (Figure 8.9).
• The memory typically takes 2 or 3 clock cycles to activate the selected row.
• Then, the column-address is latched under the control of CAS‟ signal.
• After a delay of one clock cycle, the first set of data bits is placed on the data-lines.
• SDRAM automatically increments column-address to access next 3 sets of bits in the selected row.

3-7
COMPUTER ORGANIZATION
LATENCY & BANDWIDTH
• A good indication of performance is given by 2 parameters: 1) Latency 2) Bandwidth.
Latency
• It refers to the amount of time it takes to transfer a word of data to or from the memory.
• For a transfer of single word, the latency provides the complete indication of memory performance.
• For a block transfer, the latency denotes the time it takes to transfer the first word of data.
Bandwidth
• It is defined as the number of bits or bytes that can be transferred in one second.
• Bandwidth mainly depends on
1) The speed of access to the stored data &
2) The number of bits that can be accessed in parallel.

DOUBLE DATA RATE SDRAM (DDR-SDRAM)

• The standard SDRAM performs all actions on the rising edge of the clock signal.
• The DDR-SDRAM transfer data on both the edges (loading edge, trailing edge).
• The Bandwidth of DDR-SDRAM is doubled for long burst transfer.
• To make it possible to access the data at high rate, the cell array is organized into two banks.
• Each bank can be accessed separately.
• Consecutive words of a given block are stored in different banks.
• Such interleaving of words allows simultaneous access to two words.
• The two words are transferred on successive edge of the clock.

STRUCTURE OF LARGER MEMORIES

Dynamic Memory System
• The physical implementation is done in the form of memory-modules.
• If a large memory is built by placing DRAM chips directly on the Motherboard,
then it will occupy large amount of space on the board.
• These packaging consideration have led to the development of larger memory units known as SIMM‟s
& DIMM‟s.
1) SIMM → Single Inline memory-module
2) DIMM → Dual Inline memory-module
• SIMM/DIMM consists of many memory-chips on small board that plugs into a socket on motherboard.

3-8
COMPUTER ORGANIZATION
MEMORY-SYSTEM CONSIDERATION
MEMORY CONTROLLER
• To reduce the number of pins, the dynamic memory-chips use multiplexed-address inputs.
• The address is divided into 2 parts:
1) High Order Address Bit
➢ Select a row in cell array.
➢ It is provided first and latched into memory-chips under the control of RAS‟ signal.
2) Low Order Address Bit
➢ Selects a column.
➢ They are provided on same address pins and latched using CAS‟ signals.
• The Multiplexing of address bit is usually done by Memory Controller Circuit (Figure 5.11).

• The Controller accepts a complete address & R/W‟ signal from the processor.
• A Request signal indicates a memory access operation is needed.
• Then, the Controller
→ forwards the row & column portions of the address to the memory.
→ generates RAS‟ & CAS‟ signals &
→ sends R/W‟ & CS‟ signals to the memory.

RAMBUS MEMORY
• The usage of wide bus is expensive.
• Rambus developed the implementation of narrow bus.
• Rambus technology is a fast signaling method used to transfer information between chips.
• The signals consist of much smaller voltage swings around a reference voltage Vref.
• The reference voltage is about 2V.
• The two logical values are represented by 0.3V swings above and below Vref.
• This type of signaling is generally is known as Differential Signalling.
• Rambus provides a complete specification for design of communication called as Rambus Channel.
• Rambus memory has a clock frequency of 400 MHz.
• The data are transmitted on both the edges of clock so that effective data-transfer rate is 800MHZ.
• Circuitry needed to interface to Rambus channel is included on chip. Such chips are called RDRAM.
(RDRAM = Rambus DRAMs).
• Rambus channel has:
1) 9 Data-lines (1st-8th line ->Transfer the data, 9th line->Parity checking).
2) Control-Line &
3) Power line.
• A two channel rambus has 18 data-lines which has no separate Address-Lines.
• Communication between processor and RDRAM modules is carried out by means of packets
transmitted on the data-lines.
• There are 3 types of packets:
1) Request
2) Acknowledge &
3) Data.

3-9
COMPUTER ORGANIZATION
READ ONLY MEMORY (ROM)
• Both SRAM and DRAM chips are volatile, i.e. They lose the stored information if power is turned off.
• Many application requires non-volatile memory which retains the stored information if power is
turned off.
• For ex:
OS software has to be loaded from disk to memory i.e. it requires non-volatile memory.
• Non-volatile memory is used in embedded system.
• Since the normal operation involves only reading of stored data, a memory of this type is called ROM.
➢ At Logic value ‘0’ → Transistor(T) is connected to the ground point (P).
Transistor switch is closed & voltage on bit-line nearly drops to zero (Figure 8.11).
➢ At Logic value ‘1’ → Transistor switch is open.
The bit-line remains at high voltage.

• To read the state of the cell, the word-line is activated.

• A Sense circuit at the end of the bit-line generates the proper output value.

TYPES OF ROM
• Different types of non-volatile memory are
1) PROM
2) EPROM
3) EEPROM &
4) Flash Memory (Flash Cards & Flash Drives)

PROM (PROGRAMMABLE ROM)

• PROM allows the data to be loaded by the user.
• Programmability is achieved by inserting a „fuse‟ at point P in a ROM cell.
• Before PROM is programmed, the memory contains all 0‟s.
• User can insert 1‟s at required location by burning-out fuse using high current-pulse.
• This process is irreversible.
• Advantages:
1) It provides flexibility.
2) It is faster.
3) It is less expensive because they can be programmed directly by the user.

3-10
COMPUTER ORGANIZATION
EPROM (ERASABLE REPROGRAMMABLE ROM)
• EPROM allows
→ stored data to be erased and
→ new data to be loaded.
• In cell, a connection to ground is always made at „P‟ and a special transistor is used.
• The transistor has the ability to function as
→ a normal transistor or
→ a disabled transistor that is always turned „off‟.
• Transistor can be programmed to behave as a permanently open switch, by injecting charge into it.
• Erasure requires dissipating the charges trapped in the transistor of memory-cells.
This can be done by exposing the chip to ultra-violet light.
• Advantages:
1) It provides flexibility during the development-phase of digital-system.
2) It is capable of retaining the stored information for a long time.
• Disadvantages:
1) The chip must be physically removed from the circuit for reprogramming.
2) The entire contents need to be erased by UV light.

EEPROM (ELECTRICALLY ERASABLE ROM)

• Advantages:
1) It can be both programmed and erased electrically.
2) It allows the erasing of all cell contents selectively.
• Disadvantage: It requires different voltage for erasing, writing and reading the stored data.

FLASH MEMORY
• In EEPROM, it is possible to read & write the contents of a single cell.
• In Flash device, it is possible to read contents of a single cell & write entire contents of a block.
• Prior to writing, the previous contents of the block are erased.
Eg. In MP3 player, the flash memory stores the data that represents sound.
• Single flash chips cannot provide sufficient storage capacity for embedded-system.
• Advantages:
1) Flash drives have greater density which leads to higher capacity & low cost per bit.
2) It requires single power supply voltage & consumes less power.
• There are 2 methods for implementing larger memory: 1) Flash Cards & 2) Flash Drives
1) Flash Cards
➢ One way of constructing larger module is to mount flash-chips on a small card.
➢ Such flash-card have standard interface.
➢ The card is simply plugged into a conveniently accessible slot.
➢ Memory-size of the card can be 8, 32 or 64MB.
➢ Eg: A minute of music can be stored in 1MB of memory. Hence 64MB flash cards can store an
hour of music.
2) Flash Drives
➢ Larger flash memory can be developed by replacing the hard disk-drive.
➢ The flash drives are designed to fully emulate the hard disk.
➢ The flash drives are solid state electronic devices that have no movable parts.
Advantages:
1) They have shorter seek & access time which results in faster response.
2) They have low power consumption. .‟. they are attractive for battery driven
application.
3) They are insensitive to vibration.
Disadvantages:
1) The capacity of flash drive (<1GB) is less than hard disk (>1GB).
2) It leads to higher cost per bit.
3) Flash memory will weaken after it has been written a number of times (typically at
least 1 million times).

3-11
COMPUTER ORGANIZATION
SPEED, SIZE COST

• The main-memory can be built with DRAM (Figure 8.14)

• Thus, SRAM‟s are used in smaller units where speed is of essence.
• The Cache-memory is of 2 types:
1) Primary/Processor Cache (Level1 or L1 cache)
➢ It is always located on the processor-chip.
2) Secondary Cache (Level2 or L2 cache)
➢ It is placed between the primary-cache and the rest of the memory.
• The memory is implemented using the dynamic components (SIMM, RIMM, DIMM).
• The access time for main-memory is about 10 times longer than the access time for L1 cache.

3-12
COMPUTER ORGANIZATION
CACHE MEMORIES
• The effectiveness of cache mechanism is based on the property of „Locality of Reference’.
Locality of Reference ILAP
• Many instructions in the localized areas of program are executed repeatedly during some time period
• Remainder of the program is accessed relatively infrequently (Figure 8.15).
• There are 2 types:
1) Temporal
➢ The recently executed instructions are likely to be executed again very soon.
2) Spatial
➢ Instructions in close proximity to recently executed instruction are also likely to be executed soon.
• If active segment of program is placed in cache-memory, then total execution time can be reduced.
• Block refers to the set of contiguous address locations of some size.
• The cache-line is used to refer to the cache-block.

• The Cache-memory stores a reasonable number of blocks at a given time.

• This number of blocks is small compared to the total number of blocks available in main-memory.
• Correspondence b/w main-memory-block & cache-memory-block is specified by mapping-function.
• Cache control hardware decides which block should be removed to create space for the new block.
• The collection of rule for making this decision is called the Replacement Algorithm.
• The cache control-circuit determines whether the requested-word currently exists in the cache.
• The write-operation is done in 2 ways: 1) Write-through protocol & 2) Write-back protocol.
Write-Through Protocol
➢ Here the cache-location and the main-memory-locations are updated simultaneously.
Write-Back Protocol
➢ This technique is to
→ update only the cache-location &
→ mark the cache-location with associated flag bit called Dirty/Modified Bit.
➢ The word in memory will be updated later, when the marked-block is removed from cache.
During Read-operation
• If the requested-word currently not exists in the cache, then read-miss will occur.
• To overcome the read miss, Load–through/Early restart protocol is used.
Load–Through Protocol
➢ The block of words that contains the requested-word is copied from the memory into cache.
➢ After entire block is loaded into cache, the requested-word is forwarded to processor.
During Write-operation
• If the requested-word not exists in the cache, then write-miss will occur.
1) If Write Through Protocol is used, the information is written directly into main-memory.
2) If Write Back Protocol is used,
→ then block containing the addressed word is first brought into the cache &
→ then the desired word in the cache is over-written with the new information.

MAPPING-FUNCTION
• Here we discuss about 3 different mapping-function:
1) Direct Mapping
2) Associative Mapping
3) Set-Associative Mapping

3-13
COMPUTER ORGANIZATION
DIRECT MAPPING
• The block-j of the main-memory maps onto block-j modulo-128 of the cache (Figure 8.16).
• When the memory-blocks 0, 128, & 256 are loaded into cache, the block is stored in cache-block 0.
Similarly, memory-blocks 1, 129, 257 are stored in cache-block 1.
• The contention may arise when
1) When the cache is full.
2) When more than one memory-block is mapped onto a given cache-block position.
• The contention is resolved by
allowing the new blocks to overwrite the currently resident-block.
• Memory-address determines placement of block in the cache.

• The memory-address is divided into 3 fields:

1) Low Order 4 bit field
➢ Selects one of 16 words in a block.
2) 7 bit cache-block field
➢ 7-bits determine the cache-position in which new block must be stored.
3) 5 bit Tag field
➢ 5-bits memory-address of block is stored in 5 tag-bits associated with cache-location.
• As execution proceeds,
5-bit tag field of memory-address is compared with tag-bits associated with cache-location.
If they match, then the desired word is in that block of the cache.
Otherwise, the block containing required word must be first read from the memory.
And then the word must be loaded into the cache.

3-14
COMPUTER ORGANIZATION
ASSOCIATIVE MAPPING
• The memory-block can be placed into any cache-block position. (Figure 8.17).
• 12 tag-bits will identify a memory-block when it is resolved in the cache.
• Tag-bits of an address received from processor are compared to the tag-bits of each block of cache.
• This comparison is done to see if the desired block is present.

• It gives complete freedom in choosing the cache-location.

• A new block that has to be brought into the cache has to replace an existing block if the cache is full.
• The memory has to determine whether a given block is in the cache.
• Advantage: It is more flexible than direct mapping technique.
• Disadvantage: Its cost is high.

3-15
COMPUTER ORGANIZATION
SET-ASSOCIATIVE MAPPING
• It is the combination of direct and associative mapping. (Figure 8.18).
• The blocks of the cache are grouped into sets.
• The mapping allows a block of the main-memory to reside in any block of the specified set.
• The cache has 2 blocks per set, so the memory-blocks 0, 64, 128…..... 4032 maps into cache set „0‟.
• The cache can occupy either of the two block position within the set.
6 bit set field
➢ Determines which set of cache contains the desired block.
6 bit tag field
➢ The tag field of the address is compared to the tags of the two blocks of the set.
➢ This comparison is done to check if the desired block is present.

• The cache which contains 1 block per set is called direct mapping.
• A cache that has „k‟ blocks per set is called as “k-way set associative cache‟.
• Each block contains a control-bit called a valid-bit.
• The Valid-bit indicates that whether the block contains valid-data.
• The dirty bit indicates that whether the block has been modified during its cache residency.
Valid-bit=0 → When power is initially applied to system.
Valid-bit=1 → When the block is loaded from main-memory at first time.
• If the main-memory-block is updated by a source & if the block in the source is already exists in the
cache, then the valid-bit will be cleared to “0‟.
• If Processor & DMA uses the same copies of data then it is called as Cache Coherence Problem.
• Advantages:
1) Contention problem of direct mapping is solved by having few choices for block placement.
2) The hardware cost is decreased by reducing the size of associative search.

4-1
COMPUTER ORGANIZATION

MODULE 4: ARITHMETIC

NUMBERS, ARITHMETIC OPERATIONS AND CHARACTERS

NUMBER REPRESENTATION
• Numbers can be represented in 3 formats:
1) Sign and magnitude
2) 1's complement
3) 2's complement
• In all three formats, MSB=0 for +ve numbers & MSB=1 for -ve numbers.
• In sign-and-magnitude system,
negative value is obtained by changing the MSB from 0 to 1 of the corresponding positive value.
For ex, +5 is represented by 0101 &
-5 is represented by 1101.
• In 1's complement system,
negative values are obtained by complementing each bit of the corresponding positive number.
For ex, -5 is obtained by complementing each bit in 0101 to yield 1010.
(In other words, the operation of forming the 1's complement of a given number is equivalent to
subtracting that number from 2n-1).
• In 2's complement system,
forming the 2's complement of a number is done by subtracting that number from 2n.
For ex, -5 is obtained by complementing each bit in 0101 & then adding 1 to yield 1011.
(In other words, the 2's complement of a number is obtained by adding 1 to the 1's complement of
that number).
• 2's complement system yields the most efficient way to carry out addition/subtraction operations.

ADDITION OF POSITIVE NUMBERS

• Consider adding two 1-bit numbers.
• The sum of 1 & 1 requires the 2-bit vector 10 to represent the value 2. We say that sum is 0 and the
carry-out is 1.

4-1
COMPUTER ORGANIZATION
ADDITION & SUBTRACTION OF SIGNED NUMBERS
• Following are the two rules for addition and subtraction of n-bit signed numbers using the 2's
complement representation system (Figure 1.6).
Rule 1:
➢ To Add two numbers, add their n-bits and ignore the carry-out signal from the MSB position.
➢ Result will be algebraically correct, if it lies in the range -2n-1 to +2n-1-1.
Rule 2:
➢ To Subtract two numbers X and Y (that is to perform X-Y), take the 2's complement of Y and
then add it to X as in rule 1.
➢ Result will be algebraically correct, if it lies in the range (2n-1) to +(2n-1-1).
• When the result of an arithmetic operation is outside the representable-range, an arithmetic overflow
is said to occur.
• To represent a signed in 2's complement form using a larger number of bits, repeat the sign bit as
many times as needed to the left. This operation is called sign extension.
• In 1's complement representation, the result obtained after an addition operation is not always
correct. The carry-out(cn) cannot be ignored. If cn=0, the result obtained is correct. If c n=1, then a 1
must be added to the result to make it correct.

OVERFLOW IN INTEGER ARITHMETIC

• When result of an arithmetic operation is outside the representable-range, an arithmetic overflow
is said to occur.
• For example: If we add two numbers +7 and +4, then the output sum S is 1011(0111+0100),
which is the code for -5, an incorrect result.
• An overflow occurs in following 2 cases
1) Overflow can occur only when adding two numbers that have the same sign.
2) The carry-out signal from the sign-bit position is not a sufficient indicator of overflow when
adding signed numbers.

4-2
COMPUTER ORGANIZATION
ADDITION & SUBTRACTION OF SIGNED NUMBERS
n-BIT RIPPLE CARRY ADDER
• A cascaded connection of n full-adder blocks can be used to add 2-bit numbers.
• Since carries must propagate (or ripple) through cascade, the configuration is called an n-bit ripple
carry adder (Figure 9.1).

4-3
COMPUTER ORGANIZATION

4-4
COMPUTER ORGANIZATION
ADDITION/SUBTRACTION LOGIC UNIT
• The n-bit adder can be used to add 2's complement numbers X and Y (Figure 9.3).
• Overflow can only occur when the signs of the 2 operands are the same.
• In order to perform the subtraction operation X-Y on 2's complement numbers X and Y; we form the
2's complement of Y and add it to X.
• Addition or subtraction operation is done based on value applied to the Add/Sub input control-line.
• Control-line=0 for addition, applying the Y vector unchanged to one of the adder inputs.
Control-line=1 for subtraction, the Y vector is 2's complemented.

DESIGN OF FAST ADDERS

• Drawback of ripple carry adder: If the adder is used to implement the addition/subtraction, all
sum bits are available in 2n gate delays.
• Two approaches can be used to reduce delay in adders:
1) Use the fastest possible electronic-technology in implementing the ripple-carry design.
2) Use an augmented logic-gate network structure.

4-5
COMPUTER ORGANIZATION
CARRY-LOOKAHEAD ADDITIONS
• The logic expression for si(sum) and ci+1(carry-out) of stage i are
si=xi+yi+ci ------(1) ci+1=xiyi+xici+yici ------------- (2)
• Factoring (2) into
ci+1=xiyi+(xi+yi)ci
we can write
ci+1=Gi+PiCi where Gi=xiyi and Pi=xi+yi
• The expressions Gi and Pi are called generate and propagate functions (Figure 9.4).
• If Gi=1, then ci+1=1, independent of the input carry ci. This occurs when both xi and yi are 1.
Propagate function means that an input-carry will produce an output-carry when either xi=1 or yi=1.
• All Gi and Pi functions can be formed independently and in parallel in one logic-gate delay.
• Expanding ci terms of i-1 subscripted variables and substituting into the ci+1 expression, we obtain
ci+1=Gi+PiGi-1+PiPi-1Gi-2. . . . . .+P1G0+PiPi-1 .......... P0c0
• Conclusion: Delay through the adder is 3 gate delays for all carry-bits &
4 gate delays for all sum-bits.
• Consider the design of a 4-bit adder. The carries can be implemented as
c1=G0+P0c0
c2=G1+P1G0+P1P0c0
c3=G2+P2G1+P2P1G0+P2P1P0c0
c4=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0c0
• The carries are implemented in the block labeled carry-lookahead logic. An adder implemented in this
form is called a Carry-Lookahead Adder.
• Limitation: If we try to extend the carry-lookahead adder for longer operands, we run into a problem
of gate fan-in constraints.

4-6
COMPUTER ORGANIZATION
HIGHER-LEVEL GENERATE & PROPAGATE FUNCTIONS
• 16-bit adder can be built from four 4-bit adder blocks (Figure 9.5).
• These blocks provide new output functions defined as Gk and Pk,
where k=0 for the first 4-bit block,
k=1 for the second 4-bit block and so on.
• In the first block,
P0=P3P2P1P0
&
G0=G3+P3G2+P3P2G1+P3P2P1G0
• The first-level Gi and Pi functions determine whether bit stage i generates or propagates a carry, and
the second level Gk and Pk functions determine whether block k generates or propagates a carry.
• Carry c16 is formed by one of the carry-lookahead circuits as
c16=G3+P3G2+P3P2G1+P3P2P1G0+P3P2P1P0c0
• Conclusion: All carries are available 5 gate delays after X, Y and c0 are applied as inputs.

4-7
COMPUTER ORGANIZATION
MULTIPLICATION OF POSITIVE NUMBERS

ARRAY MULTIPLICATION
• The main component in each cell is a full adder(FA)..
• The AND gate in each cell determines whether a multiplicand bit m j, is added to the incoming partial-
product bit, based on the value of the multiplier bit qi (Figure 9.6).

4-8
COMPUTER ORGANIZATION
SEQUENTIAL CIRCUIT BINARY MULTIPLIER
• Registers A and Q combined hold PPi(partial product)
while the multiplier bit qi generates the signal Add/Noadd.
• The carry-out from the adder is stored in flip-flop C (Figure 9.7).
• Procedure for multiplication:
1) Multiplier is loaded into register Q,
Multiplicand is loaded into register M and
C & A are cleared to 0.
2) If q0=1, add M to A and store sum in A. Then C, A and Q are shifted right one bit-position.
If q0=0, no addition performed and C, A & Q are shifted right one bit-position.
3) After n cycles, the high-order half of the product is held in register A and
the low-order half is held in register Q.

4-9
COMPUTER ORGANIZATION
Problem 10:

Problem 1:
Represent the decimal values 5, -2, 14, -10, 26, -19, 51 and -43 as signed 7-bit numbers in the
following binary formats:
(a) sign-and-magnitude
(b) 1’s-complement
(c) 2’s-complement
Solution:
The three binary representations are given as:
(a) Convert the following pairs of decimal numbers to 5-bit 2’s-complement numbers, then add them.
State whether or not overflow occurs in each case.
a) 5 and 10 b) 7 and 13
c) –14 and 11 d) –5 and 7
e) –3 and –8
(b) Repeat Problem 1.7 for the subtract operation, where the second number of each pair is to be
subtracted from the first number. State whether or not overflow occurs in each case.
Solution:
(a)

(b) To subtract the second number, form its 2's-complement and add it to the first number.

4-10
COMPUTER ORGANIZATION
Problem 11:
Perform following operations on the 6-bit signed numbers using 2's complement representation
system. Also indicate whether overflow has occurred.

Solution:

4-11
COMPUTER ORGANIZATION

4-12
COMPUTER ORGANIZATION

MODULE 5: BASIC PROCESSING UNIT

SOME FUNDAMENTAL CONCEPTS

• To execute an instruction, processor has to perform following 3 steps:
1) Fetch contents of memory-location pointed to by PC. Content of this location is an instruction
to be executed. The instructions are loaded into IR, Symbolically, this operation is written as:
IR [[PC]]
2) Increment PC by 4.
PC [PC] +4
3) Carry out the actions specified by instruction (in the IR).
• The first 2 steps are referred to as Fetch Phase.
Step 3 is referred to as Execution Phase.
• The operation specified by an instruction can be carried out by performing one or more of the
following actions:
1) Read the contents of a given memory-location and load them into a register.
2) Read data from one or more registers.
3) Perform an arithmetic or logic operation and place the result into a register.
4) Store data from a register into a given memory-location.
• The hardware-components needed to perform these actions are shown in Figure 5.1.

5-1
COMPUTER ORGANIZATION
SINGLE BUS ORGANIZATION
• ALU and all the registers are interconnected via a Single Common Bus (Figure 7.1).
• Data & address lines of the external memory-bus is connected to the internal processor-bus via MDR
& MAR respectively. (MDR→ Memory Data Register, MAR → Memory Address Register).
• MDR has 2 inputs and 2 outputs. Data may be loaded
→ into MDR either from memory-bus (external) or
→ from processor-bus (internal).
• MAR‟s input is connected to internal-bus;
MAR‟s output is connected to external-bus.
• Instruction Decoder & Control Unit is responsible for
→ issuing the control-signals to all the units inside the processor.
→ implementing the actions specified by the instruction (loaded in the IR).
• Register R0 through R(n-1) are the Processor Registers.
The programmer can access these registers for general-purpose use.
• Only processor can access 3 registers Y, Z & Temp for temporary storage during program-execution.
The programmer cannot access these 3 registers.
• In ALU, 1) „A‟ input gets the operand from the output of the multiplexer (MUX).
2) „B‟ input gets the operand directly from the processor-bus.
• There are 2 options provided for „A‟ input of the ALU.
• MUX is used to select one of the 2 inputs.
• MUX selects either
→ output of Y or
→ constant-value 4( which is used to increment PC content).

• An instruction is executed by performing one or more of the following operations:

1) Transfer a word of data from one register to another or to the ALU.
2) Perform arithmetic or a logic operation and store the result in a register.
3) Fetch the contents of a given memory-location and load them into a register.
4) Store a word of data from a register into a given memory-location.
• Disadvantage: Only one data-word can be transferred over the bus in a clock cycle.
Solution: Provide multiple internal-paths. Multiple paths allow several data-transfers to take place in
parallel.

5-2
COMPUTER ORGANIZATION
REGISTER TRANSFERS
• Instruction execution involves a sequence of steps in which data are transferred from one register to
another.
• For each register, two control-signals are used: Riin & Riout. These are called Gating Signals.
• Riin=1 → data on bus is loaded into Ri.
Riout=1 → content of Ri is placed on bus.
Riout=0, → bus can be used for transferring data from other registers.
• For example, Move R1, R2; This transfers the contents of register R1 to register R2. This can be
accomplished as follows:
1) Enable the output of registers R1 by setting R1out to 1 (Figure 7.2).
This places the contents of R1 on processor-bus.
2) Enable the input of register R2 by setting R2out to 1.
This loads data from processor-bus into register R4.
• All operations and data transfers within the processor take place within time-periods defined by the
processor-clock.
• The control-signals that govern a particular transfer are asserted at the start of the clock cycle.

Input & Output Gating for one Register Bit

• A 2-input multiplexer is used to select the data applied to the input of an edge-triggered D flip-flop.
• Riin=1 → mux selects data on bus. This data will be loaded into flip-flop at rising-edge of clock.
Riin=0 → mux feeds back the value currently stored in flip-flop (Figure 7.3).
• Q output of flip-flop is connected to bus via a tri-state gate.
Riout=0 → gate's output is in the high-impedancestate.
Riout=1 → the gate drives the bus to 0 or 1, depending on the value of Q.

5-3
COMPUTER ORGANIZATION
PERFORMING AN ARITHMETIC OR LOGIC OPERATION
• The ALU performs arithmetic operations on the 2 operands applied to its A and B inputs.
• One of the operands is output of MUX;
And, the other operand is obtained directly from processor-bus.
• The result (produced by the ALU) is stored temporarily in register Z.
• The sequence of operations for [R3][R1]+[R2] is as follows:
1) R1out, Yin
2) R2out, SelectY, Add, Zin
3) Zout, R3in
• Instruction execution proceeds as follows:
Step 1 --> Contents from register R1 are loaded into register Y.
Step2 --> Contents from Y and from register R2 are applied to the A and B inputs of ALU;
Addition is performed &
Result is stored in the Z register.
Step 3 --> The contents of Z register is stored in the R3 register.
• The signals are activated for the duration of the clock cycle corresponding to that step. All other
signals are inactive.

CONTROL-SIGNALS OF MDR
• The MDR register has 4 control-signals (Figure 7.4):
1) MDRin & MDRout control the connection to the internal processor data bus &
2) MDRinE & MDRoutE control the connection to the memory Data bus.
• MAR register has 2 control-signals.
1) MARin controls the connection to the internal processor address bus &
2) MARout controls the connection to the memory address bus.

5-4
COMPUTER ORGANIZATION
FETCHING A WORD FROM MEMORY
• To fetch instruction/data from memory, processor transfers required address to MAR.
At the same time, processor issues Read signal on control-lines of memory-bus.
• When requested-data are received from memory, they are stored in MDR. From MDR, they are
transferred to other registers.
• The response time of each memory access varies (based on cache miss, memory-mapped I/O). To
accommodate this, MFC is used. (MFC → Memory Function Completed).
• MFC is a signal sent from addressed-device to the processor. MFC informs the processor that the
requested operation has been completed by addressed-device.
• Consider the instruction Move (R1),R2. The sequence of steps is (Figure 7.5):
1) R1out, MARin, Read ;desired address is loaded into MAR & Read command is issued.
2) MDRinE, WMFC ;load MDR from memory-bus & Wait for MFC response from memory.
3) MDRout, R2in ;load R2 from MDR.
where WMFC=control-signal that causes processor's control.
circuitry to wait for arrival of MFC signal.

Storing a Word in Memory

• Consider the instruction Move R2,(R1). This requires the following sequence:
1) R1out, MARin ;desired address is loaded into MAR.
2) R2out, MDRin, Write ;data to be written are loaded into MDR & Write command is issued.
3) MDRoutE, WMFC ;load data into memory-location pointed by R1 from MDR.

5-5
COMPUTER ORGANIZATION
EXECUTION OF A COMPLETE INSTRUCTION
• Consider the instruction Add (R3),R1 which adds the contents of a memory-location pointed by R3 to
register R1. Executing this instruction requires the following actions:
1) Fetch the instruction.
2) Fetch the first operand.
3) Perform the addition &
4) Load the result into R1.

• Instruction execution proceeds as follows:

Step1--> The instruction-fetch operation is initiated by
→ loading contents of PC into MAR &
→ sending a Read request to memory.
The Select signal is set to Select4, which causes the Mux to select constant 4. This value
is added to operand at input B (PC‟s content), and the result is stored in Z.
Step2--> Updated value in Z is moved to PC. This completes the PC increment operation and
PC will now point to next instruction.
Step3--> Fetched instruction is moved into MDR and then to IR.
The step 1 through 3 constitutes the Fetch Phase.
At the beginning of step 4, the instruction decoder interprets the contents of the IR. This
enables the control circuitry to activate the control-signals for steps 4 through 7.
The step 4 through 7 constitutes the Execution Phase.
Step4--> Contents of R3 are loaded into MAR & a memory read signal is issued.
Step5--> Contents of R1 are transferred to Y to prepare for addition.
Step6--> When Read operation is completed, memory-operand is available in MDR, and the
addition is performed.
Step7--> Sum is stored in Z, then transferred to R1.The End signal causes a new instruction
fetch cycle to begin by returning to step1.

5-6
COMPUTER ORGANIZATION
BRANCHING INSTRUCTIONS
• Control sequence for an unconditional branch instruction is as follows:

• Instruction execution proceeds as follows: offsex get to bus

Step 1-3--> The processing starts & the fetch phase ends in step3.
Step 4--> The offset-value is extracted from IR by instruction-decoding circuit.
Since the updated value of PC is already available in register Y, the offset X is gated onto
the bus, and an addition operation is performed.
Step 5--> the result, which is the branch-address, is loaded into the PC.
• The branch instruction loads the branch target address in PC so that PC will fetch the next instruction
from the branch target address.
• The branch target address is usually obtained by adding the offset in the contents of PC.
• The offset X is usually the difference between the branch target-address and the address
immediately following the branch instruction.
• In case of conditional branch,
we have to check the status of the condition-codes before loading a new value into the PC.
e.g.: Offset-field-of-IRout, Add, Zin, If N=0 then End
If N=0, processor returns to step 1 immediately after step 4.
If N=1, step 5 is performed to load a new value into PC.

5-7
COMPUTER ORGANIZATION
MULTIPLE BUS ORGANIZATION
• Disadvantage of Single-bus organization: Only one data-word can be transferred over the bus in
a clock cycle. This increases the steps required to complete the execution of the instruction
Solution: To reduce the number of steps, most processors provide multiple internal-paths. Multiple
paths enable several transfers to take place in parallel.
• As shown in fig 7.8, three buses can be used to connect registers and the ALU of the processor.
• All general-purpose registers are grouped into a single block called the Register File.
• Register-file has 3 ports:
1) Two output-ports allow the contents of 2 different registers to be simultaneously placed on
buses A & B.
2) Third input-port allows data on bus C to be loaded into a third register during the same
clock-cycle.
• Buses A and B are used to transfer source-operands to A & B inputs of ALU.
• The result is transferred to destination over bus C.
• Incrementer Unit is used to increment PC by 4.

• Instruction execution proceeds as follows:

Step 1--> Contents of PC are
→ passed through ALU using R=B control-signal &
→ loaded into MAR to start memory Read operation. At the same time, PC is incremented by 4.
Step2--> Processor waits for MFC signal from memory.
Step3--> Processor loads requested-data into MDR, and then transfers them to IR.
Step4--> The instruction is decoded and add operation takes place in a single step.

5-8
COMPUTER ORGANIZATION
COMPLETE PROCESSOR
• This has separate processing-units to deal with integer data and floating-point data.
Integer Unit → To process integer data. (Figure 7.14).
Floating Unit → To process floating –point data.
• Data-Cache is inserted between these processing-units & main-memory.
The integer and floating unit gets data from data cache.
• Instruction-Unit fetches instructions
→ from an instruction-cache or
→ from main-memory when desired instructions are not already in cache.
• Processor is connected to system-bus &
hence to the rest of the computer by means of a Bus Interface.
• Using separate caches for instructions & data is common practice in many processors today.
• A processor may include several units of each type to increase the potential for concurrent
operations.
• The 80486 processor has 8-kbytes single cache for both instruction and data.
Whereas the Pentium processor has two separate 8 kbytes caches for instruction and data.

Note:
To execute instructions, the processor must have some means of generating the control-signals. There
are two approaches for this purpose:
1) Hardwired control and 2) Microprogrammed control.

5-9
COMPUTER ORGANIZATION
HARDWIRED CONTROL
• Hardwired control is a method of control unit design (Figure 7.11).
• The control-signals are generated by using logic circuits such as gates, flip-flops, decoders etc.
• Decoder/Encoder Block is a combinational-circuit that generates required control-outputs
depending on state of all its inputs.
• Instruction Decoder
➢ It decodes the instruction loaded in the IR.
➢ If IR is an 8 bit register, then instruction decoder generates 2 8(256 lines); one for each
instruction.
➢ It consists of a separate output-lines INS1 through INSm for each machine instruction.
➢ According to code in the IR, one of the output-lines INS1 through INSm is set to 1, and all
other lines are set to 0.
• Step-Decoder provides a separate signal line for each step in the control sequence.
• Encoder
➢ It gets the input from instruction decoder, step decoder, external inputs and condition codes.
➢ It uses all these inputs to generate individual control-signals: Yin, PCout, Add, End and so on.
➢ For example (Figure 7.12), Zin=T1+T6.ADD+T4.BR
;This signal is asserted during time-slot T1 for all instructions.
during T6 for an Add instruction.
during T4 for unconditional branch instruction
• When RUN=1, counter is incremented by 1 at the end of every clock cycle.
When RUN=0, counter stops counting.
• After execution of each instruction, end signal is generated. End signal resets step counter.
• Sequence of operations carried out by this machine is determined by wiring of logic circuits, hence
the name “hardwired”.
• Advantage: Can operate at high speed.
• Disadvantages:
1) Since no. of instructions/control-lines is often in hundreds, the complexity of control unit is
very high.
2) It is costly and difficult to design.
3) The control unit is inflexible because it is difficult to change the design.

5-10
COMPUTER ORGANIZATION
HARDWIRED CONTROL VS MICROPROGRAMMED CONTROL
Attribute Hardwired Control Microprogrammed Control
Definition Hardwired control is a control Micro programmed control is a control
mechanism to generate control- mechanism to generate control-signals
signals by using gates, flip- by using a memory called control store
flops, decoders, and other (CS), which contains the control-
digital circuits. signals.
Speed Fast Slow
Control functions Implemented in hardware. Implemented in software.
Flexibility Not flexible to accommodate More flexible, to accommodate new
new system specifications or system specification or new instructions
new instructions. redesign is required.
Ability to handle large Difficult. Easier.
or complex instruction
sets
Ability to support Very difficult. Easy.
operating systems &
diagnostic features
Design process Complicated. Orderly and systematic.
Applications Mostly RISC microprocessors. Mainframes, some microprocessors.
Instructionset size Usually under 100 instructions. Usually over 100 instructions.
ROM size - 2K to 10K by 20-400 bit
microinstructions.
Chip area efficiency Uses least area. Uses more area.
Diagram

5-11
COMPUTER ORGANIZATION
MICROPROGRAMMED CONTROL
• Microprogramming is a method of control unit design (Figure 7.16).
• Control-signals are generated by a program similar to machine language programs.
• Control Word(CW) is a word whose individual bits represent various control-signals (like Add, PCin).
• Each of the control-steps in control sequence of an instruction defines a unique combination of 1s &
0s in CW.
• Individual control-words in microroutine are referred to as microinstructions (Figure 7.15).
• A sequence of CWs corresponding to control-sequence of a machine instruction constitutes the
microroutine.
• The microroutines for all instructions in the instruction-set of a computer are stored in a special
memory called the Control Store (CS).
• Control-unit generates control-signals for any instruction by sequentially reading CWs of
corresponding microroutine from CS.
• µPC is used to read CWs sequentially from CS. (µPC→ Microprogram Counter).
• Every time new instruction is loaded into IR, o/p of Starting Address Generator is loaded into µPC.
• Then, µPC is automatically incremented by clock;
causing successive microinstructions to be read from CS.
Hence, control-signals are delivered to various parts of processor in correct sequence.

Advantages
• It simplifies the design of control unit. Thus it is both, cheaper and less error prone implement.
• Control functions are implemented in software rather than hardware.
• The design process is orderly and systematic.
• More flexible, can be changed to accommodate new system specifications or to correct the design
errors quickly and cheaply.
• Complex function such as floating point arithmetic can be realized efficiently.
Disadvantages
• A microprogrammed control unit is somewhat slower than the hardwired control unit, because time is
required to access the microinstructions from CM.
• The flexibility is achieved at some extra hardware cost due to the control memory and its access
circuitry.

5-12
COMPUTER ORGANIZATION
ORGANIZATION OF MICROPROGRAMMED CONTROL UNIT TO SUPPORT CONDITIONAL
BRANCHING
• Drawback of previous Microprogram control:
➢ It cannot handle the situation when the control unit is required to check the status of the
condition codes or external inputs to choose between alternative courses of action.
Solution:
➢ Use conditional branch microinstruction.
• In case of conditional branching, microinstructions specify which of the external inputs, condition-
codes should be checked as a condition for branching to take place.
• Starting and Branch Address Generator Block loads a new address into µPC when a
microinstruction instructs it to do so (Figure 7.18).
• To allow implementation of a conditional branch, inputs to this block consist of
→ external inputs and condition-codes &
→ contents of IR.
• µPC is incremented every time a new microinstruction is fetched from microprogram memory except
in following situations:
1) When a new instruction is loaded into IR, µPC is loaded with starting-address of microroutine
for that instruction.
2) When a Branch microinstruction is encountered and branch condition is satisfied, µPC is
loaded with branch-address.
3) When an End microinstruction is encountered, µPC is loaded with address of first CW in
microroutine for instruction fetch cycle.

5-13
COMPUTER ORGANIZATION
MICROINSTRUCTIONS
• A simple way to structure microinstructions is to assign one bit position to each control-signal
required in the CPU.
• There are 42 signals and hence each microinstruction will have 42 bits.
• Drawbacks of microprogrammed control:
1) Assigning individual bits to each control-signal results in long microinstructions because
the number of required signals is usually large.
2) Available bit-space is poorly used because
only a few bits are set to 1 in any given microinstruction.
• Solution: Signals can be grouped because
1) Most signals are not needed simultaneously.
2) Many signals are mutually exclusive. E.g. only 1 function of ALU can be activated at a time.
For ex: Gating signals: IN and OUT signals (Figure 7.19).
Control-signals: Read, Write.
ALU signals: Add, Sub, Mul, Div, Mod.
• Grouping control-signals into fields requires a little more hardware because
decoding-circuits must be used to decode bit patterns of each field into individual control-signals.
• Advantage: This method results in a smaller control-store (only 20 bits are needed to store the
patterns for the 42 signals).

5-14
COMPUTER ORGANIZATION
TECHNIQUES OF GROUPING OF CONTROL-SIGNALS
• The grouping of control-signal can be done either by using
1) Vertical organization &
2) Horizontal organisation.

Vertical Organization Horizontal Organization

Highly encoded schemes that use compact The minimally encoded scheme in which many
codes to specify only a small number of control resources can be controlled with a single
functions in each microinstruction are referred microinstuction is called a horizontal
to as a vertical organization. organization.
Slower operating-speeds. Useful when higher operating-speed is desired.
Short formats. Long formats.
Limited ability to express parallel Ability to express a high degree of parallelism.
microoperations.
Considerable encoding of the control Little encoding of the control information.
information.

MICROPROGRAM SEQUENCING
• The task of microprogram sequencing is done by microprogram sequencer.
• Two important factors must be considered while designing the microprogram sequencer:
1) The size of the microinstruction &
2) The address generation time.
• The size of the microinstruction should be minimum so that the size of control memory required to
store microinstructions is also less.
• This reduces the cost of control memory.
• With less address generation time, microinstruction can be executed in less time resulting better
throughout.
• During execution of a microprogram the address of the next microinstruction to be executed has 3
sources:
1) Determined by instruction register.
2) Next sequential address &
3) Branch.
• Microinstructions can be shared using microinstruction branching.
• Disadvantage of microprogrammed branching:
1) Having a separate microroutine for each machine instruction results in a large total number
of microinstructions and a large control-store.
2) Execution time is longer because it takes more time to carry out the required branches.
• Consider the instruction Add src,Rdst ;which adds the source-operand to the contents of Rdst and
places the sum in Rdst.
• Let source-operand can be specified in following addressing modes (Figure 7.20):
a) Indexed
b) Autoincrement
c) Autodecrement
d) Register indirect &
e) Register direct
• Each box in the chart corresponds to a microinstruction that controls the transfers and operations
indicated within the box.
• The microinstruction is located at the address indicated by the octal number (001,002).

5-15
COMPUTER ORGANIZATION

5-16
COMPUTER ORGANIZATION
BRANCH ADDRESS MODIFICATION USING BIT-ORING
• The branch address is determined by ORing particular bit or bits with the current address of
microinstruction.
• Eg: If the current address is 170 and branch address is 171 then the branch address can be
generated by ORing 01(bit 1), with the current address.
• Consider the point labeled in the figure. At this point, it is necessary to choose between direct and
indirect addressing modes.
• If indirect-mode is specified in the instruction, then the microinstruction in location 170 is performed
to fetch the operand from the memory.
If direct-mode is specified, this fetch must be bypassed by branching immediately to location 171.
• The most efficient way to bypass microinstruction 170 is to have bit-ORing of
→ current address 170 &
→ branch address 171.

WIDE BRANCH ADDRESSING

• The instruction-decoder (InstDec) generates the starting-address of the microroutine that
implements the instruction that has just been loaded into the IR.
• Here, register IR contains the Add instruction, for which the instruction decoder generates the
microinstruction address 101. (However, this address cannot be loaded as is into the μPC).
• The source-operand can be specified in any of several addressing-modes. The bit-ORing technique
can be used to modify the starting-address generated by the instruction-decoder to reach the
appropriate path.
Use of WMFC
• WMFC signal is issued at location 112 which causes a branch to the microinstruction in location 171.
• WMFC signal means that the microinstruction may take several clock cycles to complete. If the
branch is allowed to happen in the first clock cycle, the microinstruction at location 171 would be
fetched and executed prematurely. To avoid this problem, WMFC signal must inhibit any change in the
contents of the μPC during the waiting-period.

5-17
COMPUTER ORGANIZATION
Detailed Examination of Add (Rsrc)+,Rdst
• Consider Add (Rsrc)+,Rdst; which adds Rsrc content to Rdst content, then stores the sum in Rdst
and finally increments Rsrc by 4 (i.e. auto-increment mode).
• In bit 10 and 9, bit-patterns 11, 10, 01 and 00 denote indexed, auto-decrement, auto-increment and
register modes respectively. For each of these modes, bit 8 is used to specify the indirect version.
• The processor has 16 registers that can be used for addressing purposes; each specified using a 4-
bit-code (Figure 7.21).
• There are 2 stages of decoding:
1) The microinstruction field must be decoded to determine that an Rsrc or Rdst register is
involved.
2) The decoded output is then used to gate the contents of the Rsrc or Rdst fields in the IR into
a second decoder, which produces the gating-signals for the actual registers R0 to R15.

5-18
COMPUTER ORGANIZATION
MICROINSTRUCTIONS WITH NEXT-ADDRESS FIELDS

• Drawback of previous organization:

➢ The microprogram requires several branch microinstructions which perform no useful
operation. Thus, they detract from the operating-speed of the computer.
Solution:
➢ Include an address-field as a part of every microinstruction to indicate the location of the next
microinstruction to be fetched. (Thus, every microinstruction becomes a branch
microinstruction).
• The flexibility of this approach comes at the expense of additional bits for the address-field(Fig 7.22).
• Advantage: Separate branch microinstructions are virtually eliminated. (Figure 7.23-24).
• Disadvantage: Additional bits for the address field (around 1/6).
• There is no need for a counter to keep track of sequential address. Hence, μPC is replaced with μAR.
• The next-address bits are fed through the OR gate to the μAR, so that the address can be modified
on the basis of the data in the IR, external inputs and condition-codes.
• The decoding circuits generate the starting-address of a given microroutine on the basis of the
opcode in the IR. (μAR → Microinstruction Address Register).

5-19
COMPUTER ORGANIZATION

5-20
COMPUTER ORGANIZATION
PREFETCHING MICROINSTRUCTIONS
• Disadvantage of Microprogrammed Control: Slower operating-speed because of the time it takes
to fetch microinstructions from the control-store.
Solution: Faster operation is achieved if the next microinstruction is pre-fetched while the
current one is being executed.
Emulation
• The main function of microprogrammed control is to provide a means for simple, flexible and
relatively inexpensive execution of machine instruction.
• Its flexibility in using a machine's resources allows diverse classes of instructions to be implemented.
• Suppose we add to the instruction-repository of a given computer M1, an entirely new set of
instructions that is in fact the instruction-set of a different computer M2.
• Programs written in the machine language of M2 can be then be run on computer M1 i.e. M1
emulates M2.
• Emulation allows us to replace obsolete equipment with more up-to-date machines.
• If the replacement computer fully emulates the original one, then no software changes have to be
made to run existing programs.
• Emulation is easiest when the machines involved have similar architectures.

5-21
COMPUTER ORGANIZATION
Problem 1:
Why is the Wait-for-memory-function-completed step needed for reading from or writing to the main
memory?
Solution:
The WMFC step is needed to synchronize the operation of the processor and the main memory.

Problem 2:
For the single bus organization, write the complete control sequence for the instruction: Move (R1), R1
Solution:
1) PCout, MARin, Read, Select4, Add, Zin
2) Zout, PCin, Yin, WMFC
3) MDRout, IRin
4) R1out, MARin, Read
5) MDRinE, WMFC
6) MDRout, R2in, End

Problem 3:
Write the sequence of control steps required for the single bus organization in each of the following
instructions:
a) Add the immediate number NUM to register R1.
b) Add the contents of memory-location NUM to register R1.
c) Add the contents of the memory-location whose address is at memory-location NUM to
register R1.
Assume that each instruction consists of two words. The first word specifies the operation andN the
addressing mode, and the second word contains the number NUM
Solution:

Problem 4:
Show the control steps for the Branch on Negative instruction for a processor with three-bus
organization of the data path
Solution:

5-22
COMPUTER ORGANIZATION

MODULE 5: Pipeline and Vector Processing

Parallel Processing
• Simultaneous data processing tasks for the purpose of increasing the computational speed
• Perform concurrent data processing to achieve faster execution time
• Parallel processing is established by distributing the data among the multiple functional units. For
example, the arithmetic, logic, and shift operations can be separated into three units and the operands
diverted to each unit under the supervision of a control unit.
• Multiple Functional Unit : Separate the execution unit into eight functional units operating in
parallel.
• Figure 9-1 shows one possible way of separating the execution unit into eight functional units operating
in parallel.
• The operands in the registers are applied to one of the units depending on the operation specified by the
instruction associated with the operands.
• The operation performed in each functional unit is indicated in each block of the diagram.
• The adder and integer multiplier perform the arithmetic operations with integer numbers.
• The floating-point operations are separated into three circuits operating in parallel.
• The logic, shift, and increment operations can be performed concurrently on different data.
• All units are independent of each other, so one number can be shifted while another number is being
incremented.

5-23
COMPUTER ORGANIZATION

Adder-subtractor

Integer multiply

Logic unit

Shift unit

To Memory

Incrementer
Processor
registers
Floatint-point
add-subtract

Floatint-point
multiply

Floatint-point
divide

Figure 9. 1 Processor with multiple functional units

Pipelining
• Decomposing a sequential process into suboperations.
• Each subprocess is executed in a special dedicated segment concurrently.
• A pipeline can be visualized as a collection of processing segments through which binary information
flows.
• Each segment performs partial processing dictated by the way the task is partitioned.
• The result obtained from the computation in each segment is transferred to the next segment in the
pipeline. The final result is obtained after the data have passed through all segments.
• The pipeline organization will be demonstrated by means of a simple example.
• Suppose that we want to perform the combined multiply and add operations with a stream of numbers.

• Each suboperation is to be implemented in a segment within a pipeline. Each segment has one or two
registers and a combinational circuit as shown in Fig. 9-2.
• R 1 through R5 are registers that receive new data with every clock pulse.
• The suboperations performed in each segment of the pipeline are as follows:

5-24
COMPUTER ORGANIZATION

• The five registers are loaded with new data every clock pulse. The effect of each
clock is shown in Table 9-1.

• The first clock pulse transfers A1 and 81 into R 1 and R2.

5-25
COMPUTER ORGANIZATION
• The second dock pulse transfers the product of R 1 and R2 into R3 and C1 into R4. The same clock pulse
transfers A2 and B2 into R 1 and R2.
• The third clock pulse operates on all three segments simultaneously. It places A, and B, into R1 and R2,
transfers the product of R1 and R2 into R3, transfers C, into R4, and places the sum of R3 and R4 into
RS. It takes three clock pulses to fill up the pipe and retrieve the first output from R5.
• From there on, each dock produces a new output and moves the data one step down the pipeline. This
happens as long as new input data flow into the system.
• When no more input data are available, the clock must continue until the last output emerges out of the
pipeline.

Problem: In certain scientific computations it is necessary to perform the arithmetic operation (Ai + Bi)(Ci + Di)
with a stream of numbers. Specify a pipeline configuration to cany out this task. thliste contents of all registers
in the pipeline for i = 1 through 6.

General Structure of four segment pipeline

• The operands pass through all four segments in a fixed sequence.
• Each segment consists of a combinational circuit S; that performs a suboperation over the data stream
flowing through the pipe.
• The segments are separated by registers R; that hold the intermediate results between the stages.
Information flows between adjacent stages under the control of a common clock applied to all the
registers simultaneously.
• We define a task as the total operation performed going through all the segments in the pipeline.

• The behavior of a pipeline can be illustrated with a space-time diagram.

• This is a diagram that shows the segment utilization as a function of time. The space-time diagram of a
four-segment pipeline is demonstrated in Fig. 9-4.
• The horizontal axis displays the time in clock cycles and the vertical axis gives the segment number.
• The diagram shows six tasks T1 through T6 executed in four segments.
• Initially, task T1 is handled by segment 1. After the first clock, segment 2 is busy with T1, while segment
1 is busy with task T2•

5-26
COMPUTER ORGANIZATION
• Continuing in this manner, the first task T1 is completed after the fourth clock cycle. From then on, the
pipe completes a task every clock cycle.
• No matter how many segments there are in the system, once the pipeline is full, it takes only one clock
period to obtain an output.

Speedup ratio of pipeline:

• Consider the case where a k-segment pipeline with a clock cycle time tp, is used to execute n tasks.
• The first task T1 requires a time equal to ktp, to complete its operation since there are k segments in the
pipe.
• The remaining n - 1 tasks emerge from the pipe at the rate of one task per clock cycle and they will be
completed after a time equal to (n - 1)tp, .
• Therefore, to complete n tasks using a k-segment pipeline requires k + (n - 1) clock cycles.
• For example, the diagram of Fig. 9-4 shows four segments and six tasks. The time required to complete
all the operations is 4 + (6 - 1) = 9 clock cycles.
• Next consider a non-pipelined unit that performs the same operation and takes a time equal to tn. to
complete each task. The total time required for n tasks is ntn (= nktp)

The speedup of a pipeline processing over an equivalent nonpipelined processing is defined by the ratio

S= time taken in non-pipelined system/ time taken in pipelined system.

n: number of tasks
tn : time to complete each task in non-pipelined ( = k tp)
tp : clock cycle time
k : segment number

5-27
COMPUTER ORGANIZATION

Example:
• Let the time it takes to process a suboperation in each segment be equal to tp, = 20 ns. Assume that the
pipeline has k = 4 segments and executes n = 100 tasks in sequence.
• The pipeline system will take (k + n - 1)tp, = (4 + 99) x 20 = 2060 ns to complete.
• Assuming that tn = ktp = 4 x 20 = 80 ns, a non pipeline system requires nktp, = 100 x 80 = 8000 ns to
complete the 100 tasks.
• The speedup ratio is equal to 8000/2060 = 3 .88.

Problems :
1) Draw a space-time diagram for a six-segment pipeline showing the time it
takes to process eight tasks.
2)Determine the number of dock cydes that it takes to process 200 tasks in a
six-segment pipeline.
3)A non-pipeline system takes 50 ns to process a task. The same task can 􀃝
processed in a six-segment pipeline with a dock cycle of 10 ns. Determine
the speedup ratio of the pipeline for 100 tasks. What is the maximum
speedup that can be achieved?
Arithmetic Pipeline
The inputs to the floating-point adder pipeline are two normalized floating- point binary numbers.
X = A X 2a
Y = 8 X 2b
A and B are two fractions that represent the mantissas and a and b are the exponents.
The floating-point addition and subtraction can be performed in four segments, as shown in Fig. 9-6. The
registers labeled R are placed between the segments to store intermediate results. The suboperations that are
performed in the four segments are:
1. Compare the exponents.
2. Align the mantissas.
3. Add or subtract the mantissas.
4. Normalize the result.
The following numerical example may clarify the suboperations performed in each segment.
Consider the two normalized floating-point numbers:
X = 0. 9504 X 103
Y = 0.8200 X 102
The two exponents are subtracted in the first segment to obtain 3 - 2 = 1.
The larger exponent 3 is chosen as the exponent of the result. The next segment shifts the mantissa of Y to the
right to obtain
X = 0.9504 X 103

5-28
COMPUTER ORGANIZATION
Y = 0. 0820 X 103
This aligns the two mantissas under the same exponent. The addition of the two mantissas in segment 3
produces the sum
Z = 1. 0324 X 103
The sum is adjusted by normalizing the result so that it has a fraction with a nonzero first digit. This is done by
shifting the mantissa once to the right and incrementing the exponent by one to obtain the normalized sum.
Z = 0.10324 X 104

Exponents
a b
Mantissas
A B

R R

Compare Difference
Segment 1 : exponents
by subtraction

Segment 2 : Choose exponent Align mantissas

Add or subtract
Segment 3 :
mantissas

R R

Adjust Normalize
Segment 4 :
exponent result

R R

Instruction Pipeline
In the most general case, the computer needs to process each instruction with the following sequence of steps.
1) Fetch the instruction from memory
2) Decode the instruction
3) Calculate the effective address
4) Fetch the operands from memory

5-29
COMPUTER ORGANIZATION
5) Execute the instruction
6) Store the result in the proper place
Example : Four-segment Instruction pipeline
Four-segment CPU pipeline :
1) FI : Instruction Fetch
2) DA : Decode Instruction & calculate EA
3) FO : Operand Fetch
4) EX : Execution

Step : 1 2 3 4 5 6 7 8 9 10 11 12 13
Instruction : 1 FI DA FO EX

2 FI DA FO EX

(Branch) 3 FI DA FO EX

4 FI FI DA FO EX

5 FI DA FO EX

6 FI DA FO EX

7 FI DA FO EX

• Assume now that instruction 3 is a branch instruction. As soon as this instruction is decoded in segment
DA in step 4, the transfer from FI to DA of the other instructions is halted until the branch instruction is
executed in step 6.
• If the branch is taken, a new instruction is fetched in step 7. If the branch is not taken, the instruction
fetched previously in step 4 can be used. The pipeline then continues until a new branch instruction is
encountered.

5-30
COMPUTER ORGANIZATION

Fetch instruction
Segment 1 :
from memory

Decode instruction
Segment 2 : and calculate
effective address

Branch ?

Fetch operand
Segment 3 :
from memory

Segment 4 : Execute instruction

Interrupt
Interrupt ?
handling

Update PC

Empty pipe

Vector Processing
• There is a class of computational problems that are beyond the capabilities of a conventional computer.
• These problems are characterized by the fact that they require a vast number of computations that will
take a conventional computer day or even weeks to complete.
• In many science and engineering applications, the problems can be formulated in terms of vectors and
matrice1that lend themselves to vector processing.
• Computers with vector processing capabilities are in demand in specialized applications.
• The following are representative application areas where vector processing is of the utmost importance.
Long-range weather forecasting
Petroleum explorations
Seismic data analysis

5-31
COMPUTER ORGANIZATION
Medical diagnosis
Aerodynamics and space flight simulations
Artificial intelligence and expert systems
Mapping the human genome
Image processing
• Many scientific problems require arithmetic operations on large arrays of numbers. These numbers are
usually formulated as vectors and matrices of floating-point numbers.
• A vector is an ordered set of a one-dimensional array of data items. A vector V of length n is represented
as a row vector by
V = [V1, V2, V3 ,· · · Vn] .
A conventional sequential computer is capable of processing operands one at a time. Consequently, operations
on vectors must be broken down into single computations with subscripted variables. The element V;
of vector V is written as V(I) and the index I refers to a memory address or register where the number is stored.
To examine the difference between a conventional scalar processor and a vector processor, consider the
following Fortran DO loop:
DO 20 I = 1 , 1 0 0
20C(I)=B(I)+A(I)

This is a program for adding two vectors A and B of length 100 to produce a vector C . This is implemented in
machine language by the following sequence of operations.
InitializeI=0
20 ReadA(I)
ReadB(I)
StoreC(I)=A(I)+B(I)
IncrementI=I+1
I f I <=1 0 0 go to 2 0
Continue
A computer capable of vector processing eliminates the overhead associated with the time it takes to fetch and
execute the instructions in the program loop. It allows operations to be specified with a single vector instruction
of the form
C(1 : 100) = A(1 : 100) + B(1 : 100)
The vector instruction includes the initial address of the operands, the length of the vectors, and the operation to
be performed, all in one composite instruction.

Matrix Multiplication
• Matrix multiplication is one of the most computationally intensive operations performed in computers with
vector processors.
• The multiplication of two n x n matrices consists of n 2 inner products or n3 multiply-add operations.

5-32
COMPUTER ORGANIZATION
• An n x m matrix of numbers has n rows and m columns and may be considered as constituting a set of n
row vectors or a set of m column vectors.

Consider an example, the multiplication of two 3 x 3 matrices A and B .

The product matrix C i s a 3 x 3 matrix

the number in the first row and first column of matrix C is calculated by letting i = 1, j = 1, to obtain

The computation consists of n2 inner products, with each inner product requiring n multiply-add operations.
In general, the inner product consists of the sum of k product terms of the form

C = A1B1+A2B2+A3B3+…+Ak Bk

The inner product calculation on a pipeline vector processor is shown in Fig. 9-12. The values of A and B are
either in memory or in processor registers. The floating-point multiplier pipeline and the floating-point adder
pipeline are assumed to have four segments each.

At the end of the eighth cycle, the first four products A1 B1 through A4 B4 are in the four adder segments, and
the next four products, A5 B5 through A, B,, are in the multiplier segments.
At the beginning of the ninth cycle, the output of the adder is A1 B1 and the output of the multiplier is A5 B5•
Thus the ninth cycle starts the addition A1 B1 + A5 B5 in the adder pipeline. The tenth cycle starts the

5-33
COMPUTER ORGANIZATION
addition A2 B, + A6 B6, and so on. This pattern breaks down the summation into four sections as follows:

Memory Interleaving

5-34
COMPUTER ORGANIZATION

5-35
COMPUTER ORGANIZATION

Array Processors
• An array processor is a processor that performs computations on large arrays of data. The term is used to
refer to two different types of processors.
• An attached array processor is an auxiliary processor attached to a general-purpose computer. It is
intended to improve the performance of the host computer in specific numerical computation tasks.
• An SIMD array processor is a processor that has a single-instruction multiple-data organization. It
manipulates vector instructions by means of multiple functional units responding to a common
instruction.

Attached Array Processor

• An attached array processor is designed as a peripheral for a conventional host computer, and its purpose
is to enhance the performance of the computer by providing vector processing for complex scientific
applications.
• It achieves high performance by means of parallel processing with multiple functional units.
• It includes an arithmetic unit containing one or more pipelined floating point adders and multipliers.
• The array processor can be programmed by the user to accommodate a variety of complex arithmetic
problems.
• Figure 9-14 shows the interconnection of an attached array processor to a host computer.
• The host computer is a general-purpose commercial computer and the attached processor is a back-end
machine driven by the host computer.
• The array processor is connected through an input-output controller to the computer and the computer
treats it like an external interface.
• The data for the attached processor are transferred from main memory to a local memory through a
high-speed bus.
• The general-purpose computer without the attached processor serves the users that need conventional
data processing.
• The system with the attached processor satisfies the needs for complex arithmetic applications.

SIMD Array Processor

5-36
COMPUTER ORGANIZATION
• An SIMD array processor is a computer with multiple processing units operating
• in parallel.
• The processing units are synchronized to perform the same operation under the control of a common
control unit, thus providing a single instruction stream, multiple data stream (SIMD) organization.
• A general block diagram of an array processor is shown in Fig. 9-15. It contains a set of identical
processing elements (PEs), each having a local memory M.
• Each processor element includes an ALU, a floating-point arithmetic unit, and working registers.
• The master control unit controls the operations in the processor elements.
• The main memory is used for storage of the program.
• The function of the master control unit is to decode the instructions and determine how the instruction is
to be executed.
• Scalar and program control instructions are directly executed within the master control unit.
• Vector instructions are broadcast to all PEs simultaneously. Each PE uses operands stored in its local
memory.
• Vector operands are distributed to the local memories prior to the parallel execution of the instruction.

5-37