Computer Organization & Architecture (CSE2202)

Practice Problem Set

1. (a) Explain the use of the following registers-

(i) Program counter
(ii) Instruction register
(iii) Memory address register
(iv) Memory data register
(v) Accumulator
(vi) Stack Pointer

(b) A processor has 16 integer registers (R0, R1, …, R15) and 64 floating point registers (F0, F1, …, F63).
It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3,
and Type-4. Type-1 category consists of four instructions, each with 3 integer register operands
(3Rs). Type-2 category consists of four instructions, each with 2 floating point register operands
(2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and
one floating point register operand (1R+1F). Type-4 category consists of N instructions, each with a
floating point register operand (1F).
(i) Specify instruction format for each type.
(ii) What is the maximum value of N?

2. (a) Evaluate the arithmetic statement X = (A+B)/(C-D) in one, two, three, zero addresses machine
instructions. A, B, C, D are variables.
(b) With example explain Direct, Indirect addressing mode.
(c) What are the different phases of instruction cycle?

3. (a) Two word instruction ”LOAD AC” is stored at location 200 with its address field at location 201. The
address field has the value 500. A processor register R1 contains the number 400. The content of
memory locations 400, 500, 600, 700, 702, and 900 are 60, 70, 50, 80, 90, and 100 respectively.
Evaluate the effective address and the content of accumulator after the execution of this statement if
the following addressing modes are used.
(i) Direct
(ii) Indirect
(iii) Immediate
(iv) Relative
(v) Register indirect (use register R1)
(vi) Index with R1 as index register

(b) Differentiate between Von Neumann and Harvard Architecture. Explain using schematic diagrams.

4. (a) Draw a simplified block diagram of Micro-programmed control organization and briefly explain how
it works.

(b) Differentiate between Hardwired and Micro-programmed control unit.

(c) What value remains on the stack after the following sequence of instructions?
PUSH #3 (symbol # indicates direct value of the number)
PUSH #5
PUSH #4
ADD
PUSH #7
SUB
MULT
5. (a) There are 50 registers, and total 55 instructions available in a general purpose computer. The
computer allows only 2-address instructions, where one operand can be a register and another can
be a memory location. The memory is byte addressable with 64KB (Kilo bytes) in size. What will
be the minimum number of bits to encode the instruction? Give details of instruction format.

(b) Which Addressing Mode is used for accessing the array elements in sequence? In a relative (PC-
relative) addressing, there is a “BR 20” instruction (instruction length = 1 word) at the word address
205F (Hex). What will be the content of the Program Counter after execution of the instruction?
(Assume the number 20 is in decimal).

(c) The block diagram of control memory has 4096 words of 24 bits each.
(i) How many bits are there in the control address register?
(ii) How many bits are there in each of the four inputs of multiplexer?

6. (a) What is addressing mode? Briefly explain different types of addressing modes .Registers R1 and R2
of a computer contain the decimal values 1000 and 2000 respectively. What is the effective address
of the memory operand in each of the following instructions?
(i) Load (50)R1, R5
(ii) Add –(R2), R5
(iii) Move #2000, R5
(iv) Sub (R1)+, R5
(b) There are 58 processor Registers, 7 addressing modes and 16K X 32 main memory. State the
instruction format and size of each field if each instruction supports one register operand and one
address operand and size of instruction format is 32 bits.

7. (a) Explain IAS Computer using a schematic diagram.

(b) What is Von Neumann bottleneck? How von Neumann bottleneck can be overcome?

8. (a) In a computer, there are 30 processor Registers, 6 addressing modes and 32K X 32 main memory.
Each instruction (having size of 32 bits) supports one register operand and one memory address
operand. State the instruction format, after finding out the size of each field.

(b) A 50 MHz processor was used to execute a program with the following instruction mix and clock cycle
counts:

Instruction Type Instruction Count Clock Cycle Count

Integer Arithmatic 60000 2
Data Transfer 75000 3
Floating point arithmetic 20000 1
Branch 5000 2

Calculate the effective CPI, MIPS rate and execution time for this program

(c) If each register is specified by 3 bits and instruction ADD R1, R2, R3 is 2 byte long, then what is the
length of op-code field?

9. (a) With the help of a block diagram, briefly explain Direct Memory Access.

(b) In a 4-way set-associative cache mapping, the cache size is 64KWords and the size of the main
memory is 16 MWords. The main memory is divided into a number of blocks, each of size 2 KWords.
Find the number of bits for tag, set and word offset. Find out the set number in Hex if the block
number is 0BAD16.
 (c) Describe briefly, the steps involved after an external IO device requests the processor to transfer data
by activating the interrupt signal on the CPU.

10. (a) Briefly describe, with example, one software technique to reduce Cache Miss Rate.
(b) Mention the steps followed by the CPU, when an external device interrupts the CPU.
(c) State one reason why Write-back policy is better than Write-through Policy.
(d) “In case of Direct Mapping Cache, no replacement policy is required”. Justify.
(e) What is NMI? Give examples.

11. (a) Describe briefly, the sequence of events involved in DMA Transfer.
(b) State one advantage and one disadvantage of memory-mapped IO, compared to IO-mapped IO.
(c) Briefly explain, with examples, vectored and non-vectored interrupts.

12. (a) Consider a reference pattern that accesses a sequence of blocks 0, 4, 0, 2, 1, 8, 0, 1, 2, 3, 0, 4. If the
cache uses associative mapping, and LRU algorithm is used for page replacement, find the hit ratio
for a cache with four lines.

(b) How are “Tag” bits used in cache memory systems? Explain with reference to the three cache
mapping techniques.

(c) A hierarchical Cache-MS memory has the following specifications:

Cache access time of 90 ns;
∙ Main memory access time of 500 ns;
∙ 80% of memory references are for read and 20% for writes;
∙ The hit ratio of 0.9 for read accesses and 0.80 for write access for cache.
(i) Compute effective memory access time for read.
(ii) Compute Average memory access times for both read and write considering write
through policy.

13. (a) Briefly explain, with a diagram, Daisy Chaining method for Bus Arbitration.
(b) From the entry in a segment table, it is understood that segment #0 has base address 215 and length
of 500 words, segment #1 has base address 2000 and length of 160 words, segment #2 has base
address 1200 and length of 40 words. Find out the physical addresses corresponding to the following
logical addresses?
(i) 0, 430 (ii) 1, 234 (iii) 2, 13 (iv) 1, 100
(c) Differentiate between the concept of Memory mapped I/O and I/O mapped I/O.

14. (a) Explain the working principle of polling method and How the limitations of daisy chaining method
are reduced by using polling.
(c) Explain the associative and direct mapped cache mapping approaches.
(d) Consider the following sequence of memory references:
1,2,1,3,7,4,5,6,3,1
The cache memory can hold three blocks and is initially empty. How many misses occur for the
following replacement policies?
(i) LRU (ii) FIFO

15. (a) What are the different types of interrupt? Give examples.
(b) “Interrupt request is serviced at the end of current instruction cycle while DMA request is serviced
almost as soon as it is received, even before completion of current instruction execution.” Explain.
(c) What are the advantages and disadvantages of an asynchronous transfer? Differentiate between
polled I/O and interrupt driven I/O.

16. (a) A computer has a main memory of 64K X 16 and a cache memory of 1K words. The cache uses direct
mapping with a block size of four words.
(i) How many bits are there in the tag, index, block and word fields of the address format?
 (ii) How many bits are there in each word of cache?
(iii) How many blocks can the cache accommodate?
(b) Consider a logical address space of 8 pages of 1024 words each, mapped onto a physical memory of
32 frames.
(a) How many bits are there in the logical address?
(b) How many bits are there in the physical address?

17. Consider the following Reservation Table.

1 2 3 4 5 6
S1 X X
S2 X X
S3 X X

(a) Draw a neat diagram of the corresponding Pipelined processor, showing the input, output and
various stages along with the interconnection between the stages.
(b) Determine the set of Forbidden Latencies, and the Initial Collision Vector.
(c) Draw the state diagram for scheduling the pipeline, showing the steps for at least one state.
(d) List all simple cycles and point out the Greedy cycle.
(e) Determine the Minimum Average Latency (MAL) of the pipeline? Find out the lower and upper
bounds of MAL.

18. Consider the Reservation Table given below:

1 2 3 4 5 6
S1 X X
S2 X X
S3 X
S4 X X

(a) Determine the set of Forbidden Latencies and Permissible Latencies, and the Initial Collision Vector.
(b) Draw the state diagram for scheduling the pipeline.
(c) List all simple cycles. Especially point out the Greedy Cycles (GC).
(d) What is the Minimum Average Latency (MAL) of the pipeline? Specify lower and upper bounds of
MAL?

19. Consider the Reservation Table given below:

1 2 3 4 5 6
S1 X X
S2 X X
S3 X
S4 X
S5 X X

(a) Determine the set of Forbidden Latencies and Permissible Latencies, and the Initial Collision Vector.
 (b) Draw the state diagram for scheduling the pipeline.
(c) List all simple cycles. Especially point out the Greedy Cycles (GC).
(d) What is the Minimum Average Latency (MAL) of the pipeline? Specify lower and upper bounds of
MAL?

20. (a) Explain Gather and Scatter instructions in Vector processing.

(b) Explain vector chaining and vector stride using examples.
(c) What is Strip Mining?
(d) Consider a 4 segments pipeline with 10 ns clock period. Find out speedup for 200 tasks.

21. (a) How can hazard occur in executing the following set of instructions?
I1: MOV R1, A
I2: ADD R2, R3
I3: SUB R4, R5
I4: NOP
All the symbols have their usual meanings.
You may assume a pipeline unit consisting of four stages.

(b) Consider the following program being executed on a vector processor.

For I=0 to 49
C(I) = A(I) + B(I)
Show the sequence of vector instructions for the above program. Also calculate how many cycles will
be needed by the vector processor to complete the same.

(c) How can use of vector chaining improve performance if we add the following line to the program in
(b)?
E(I) = C(I) + D(I).

22. (a) You have the following Instruction Stream coming into a chained Vector Processor.
Load VR , A[3:0]
Add VR , #1
MulVR , #2
Store A[3:0] , VR
A is a vector if length 4. VR is a Vector register.
Show how the above code is executed in a Vector processor with four pipeline stages (Load / Add /
Multiply and Store).

(b) Explain vector stride and strip mining using examples.

(c) With an example show how the vector processors perform better than scalar processors?

23. (a) Distinguish between the different types of pipeline hazards using suitable examples.

(b) Consider a 3-stage pipelined processor having a delay of 10ns, 20ns, and 14 ns for the first, second
and the third stages respectively. Assuming that there is no other delay and the processor does not
encounter any pipeline hazard, one instruction is fetched in every cycle. Calculate the total execution
time for 100 instructions using this processor.

(c) Consider a 5-segment pipeline with a clock cycle time of 20ns in each sub-operation. Find out the
approximate speed-up ratio between pipelined and non-pipelined system to execute 100
instructions. (If an average, every five cycles, a bubble due to data hazard has to be introduced in the
pipeline.)

24. (a) Explain the five basic types of vector operations with suitable examples.
(b) Explain Vector Start-up & Initiation Rate.
 (c) The start-up time of a vector multiply operation is 12 clock cycles. After start-up, the initiation rate
is 1 per clock cycle. Calculate the number of clock cycles required per result for a 64-element vector.

25. (a) Load the eight numbers 24, 37, 86, 5, 77, 8, 54, 62 in the processing elements (PEs) of a 4 × 2 Array
Processor in snakelike row-major indexing. With the help of diagrams, show the various operations
performed in the M(4, 2) sorting algorithm to sort the above numbers in ascending order.
(b) Illustrate the necessity of data routing and masking in an array processor by showing the execution
details to compute the sum S(k) of the first (k+1) components in a vector A = (A0, A1, …….., An-1) for
each k from 0 to (n-1).

26. (a) Draw the diagram of a 23 × 33 Delta Network.

(b) Draw the diagram of a multi-stage 8 × 8 Omega network. On this diagram, show the paths (along with
the explanations why you have chosen this path) for routing a message from node #6 to node #0 and
from node #2 to node #7 simultaneously. State with reasons whether blocking exists in this case.

27. (a) Load the two sorted sequences {6, 17, 43, 85} and {15, 31, 59, 68} on a linear array of Processing
Elements (PEs). With the help of diagrams, show the various operations performed in the Batcher’s
odd-even merge sort algorithm to sort these numbers in ascending order.
(b) Draw the diagram of a 3-stage Cube Interconnection Network. On this diagram, clearly show the path
for broadcast from the Source node 2 to the Destination nodes 4, 5, 6 and 7. Explain why you have
chosen this path.
(c) Draw a diagram to illustrate 4-shuffle of 12 objects (S4*3).

28. (a) Taking an example, show how (i) shuffle and (ii) unshuffle operations can be implemented by a
sequence of ‘Interchange’ operations.
(b) Load the two sorted sequences {2, 6, 13, 17, 43, 67, 85, 93} and {7, 9, 16, 29, 31, 59, 78, 90} in the
processing elements (PEs) of a 4 × 4 Array Processor in snakelike row-major indexing. With the help
of diagrams, show the various operations performed in the M(4, 4) sorting algorithm to sort the
numbers in ascending order.

29. (a) Describe briefly, with examples, Flynn’s classification of computers.

(b) Draw the diagram of Illiac Network with 16 processing elements.
(c) Show how the following two matrices can be multiplied in an SIMD computer.

30. (a) Draw the diagram of a 2-stage Delta network, in which, 4-shuffle of 12 objects is used as the
interconnection network.
(b) Derive an expression for the total number of a × b crossbar modules required in an × bn delta network.
What happens when a = b?
(c) Write down the expressions for Shuffle (S) and Exchange (E) functions of an n-bit binary number.
From these expressions, implement single-stage recirculating shuffle-exchange network for 8 nodes.

31. (a) Load the two sorted sequences {5, 24, 37, 86} and {8, 54, 62, 77} on a 4 × 2 Array Processor. With the
help of diagrams, illustrate the various operations performed in the M(4, 2) sorting algorithm to sort
the above eight numbers in the ascending order.
(b) Draw the block diagram of an Interconnection network consisting of 3 identical stages and perfect
shuffle interconnection between two adjacent stages.

32. (a) Draw the block diagram, showing the configuration of Illiac IV computer.
(b) With the help of block diagram(s), show that the 3-cube network has the same interconnection
topology as the repositioned Omega network.