SY

Corporate Office (Delhi): 44-A/1 Kalu Sarai (Sarvapriya Vihar) , New Delhi-16, Ph: 011-45124612, 9958995830
Visit us at: www.madeeasy.in | E-mail us at: info@madeeasy.in

Delhi | Hyderabad | Noida | Bhopal | Jaipur | Lucknow | Indore | Pune | Bhubaneswar | Kolkata | Patna
EA
Lockdown Period
Open Practice Test Series
(Also useful for Other Exams)
E

CS & IT : COMPUTER SCIENCE & IT

AD

TEST No. -03 | COMPUTER ORGANISATION

Read the following instructions carefully

1. This question paper contains 33 MCQ’s & NAQ’s. Bifurcation of the questions are given below:
M

17 to 28

29 to 33

2. Choose the closest numerical answer among the choices given.

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Multiple Choice Questions : Q.1 to Q.10 carry 1 mark each

Q.1 Consider the following statements with respect to control unit.

S1 : Operating speed of vertical microprogramming is higher than that of horizontal micropgramming.
S2 : Horizontal microprogramming needs signal decoders as like vertical microprogramming.
Which of the following option in correct?
(a) Both S1 and S2 are correct (b) Only S1 is correct
(c) Only S2 is correct (d) None of S1 or S2 is correct

1. (d)
• Since, vertical microprogram encode the control signals hence a signal decoder is needed which
decrease the operation speed of vertical micro-programming in comparison with horizontal micro-
programming.

SY
• Since, the control signal bits under horizontal microprogram control unit are not encoded. Hence no
signal decoder is needed.

Q.2 Consider a CPU, where all the instructions require 6 clock cycles to complete their execution. Under the
instruction set there are 215 instructions and a total of 125 control signals are needed to be generated by
the control unit. While designing the horizontal micro-programmed control unit, single address field format
EA
is used for branch control logic.
What is the minimum size of control word and control address register.
(a) 136, 11 (b) 7, 12
(c) 7, 11 (d) 125, 12

2. (a)
Since, it uses horizontal micro-programmed that requires 1 bit control / signal.
For 125 control signal, we need 125 bits.
E

Total number of micro-operation instruction = 215 × 6 = 1290

It requires 11 bit.

Q.3 In a vectored interrupt:

AD

(a) the interrupting device supplies the branch information to the processor through an interrupt vector.
(b) the CPU does not know, which device cause the interrupt without polling each I/O interface.
(c) the branch address is always assigned to a fixed location in memory.
(d) None of the above.

3. (a)
M

A vectored interrupt is the one, where CPU actually knows the address of the ISR in advance, with the help
of an interrupt vector, the interrupting device supplies the branch information to the processor.

2 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.4 In a 16 bit computer instruction format, the size of address field is 5 bits. The computer uses expanding
opcode technique. It has two 2-address instructions and 1024 one address instruction. How many zero-
address instruction can be formulated?
(a) 28720 (b) 30704
(c) 30720 (d) 32704

4. (c)
Address format
16 bits
Opcode Address Address
6 5 5

Number of operations = 26 =64

SY
Number of free opcodes after 2-address = 64 – 2 = 62
Number of 1 add instruction = 62 × 32 = 1984
Free opcodes = 1984 – 1024 = 960
Number of 0 add instruction = 960 × 32 = 30720

EA
E
AD
M

3 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.5 Consider the evaluation of following expression tree on a machine in which memory can be accessed only
through load and store instructions. The variable p, q, r, s, t, u and v are initially stored in memory. The
binary operators used in the tree can be evaluated by the machine only when all operands are in register.
The instruction produce result only in a register.

+ – ∗

∗ t u + v

p q r s

SY
What is the the minimum number of registers needed to evaluate the expression if, no intermediate results
can be stored in memory?
(a) 3 (b) 4
(c) 5 (d) 6

5. (b)
EA r1
+

∗ r2
r3
r1 + – ∗ r2
r2
r1 ∗ t r3 r4 u + r3 v
r3
E

r1 p q r2 r2 r s

Load r1, p
AD

Load r2, q
MUL r1, r2
Load r2, r
Load r3, s
Add r2, r3
Load r3, v
MUL r2, r3
M

Load r3, t
Add r1, r3
Load r4, u
SUB r3, r4
MUL r2, r3
Add r1, r2
Total 4 registers are required.

4 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.6 Consider the following statements:

S1: More than one word are put in one cache block to reduce the miss penalty.
S2: Virtual memory increases the degree of multiprogramming.
S3: Increasing the RAM of a computer typically improves performance because virtual memory increase.
How many of the above statements are correct?
(a) only S1 and S3 (b) only S1 and S2
(c) only S2 (d) All S1, S2 and S3

6. (b)
• More than one word are put in one cache block to explicit in the spatial locality of reference.
• By the help of virtual memory, programs can exceed from the size of primary memory, hence increases
the degree of multi programming.
• Increasing RAM will result in fewer page faults.

SY
Hence only S2 is the correct statement.

Q.7 Consider the following Booth’s multiplication

Multiplicand : 1011 0111 1111
Multiplier : 0110 1001 0110
EA
How many arithmetic operations are required in the multiplication.
(a) 6 (b) 7
(c) 8 (d) 9

7. (c)

Multiplier Pair with (q – 1) Recorder

0 0 0
1 0 –1
E

1 1 0
0 1 +1
1 0 –1
0 1 +1
AD

0 0 0
1 0 –1
0 1 +1
1 0 –1
1 1 0
0 1 +1
M

5 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.8 The following assembly code is to be executed in a 3-stage pipelined processor with hazard detection
and resolution in each stage. The stage are IF, OF (one or more as required) and execution (including write-
back operation). What are the number of possible RAW, WAW and WAR hazards in the execution of the
code.
Instruction Meaning
I1: Inc R0 R0 ← (R0) + 1
I2: Mul ACC, R0 Acc ← (ACC) × (R0)
I3: Store R1, ACC R1 ← (ACC)
I4: Add ACC, R0 Acc ← (ACC) + (R0)
I5: Store M, ACC M ← (ACC)

SY
(a) 6, 1, 2 (b) 5, 3, 3
(c) 5, 3, 2 (d) 5, 1, 2

8. (d)
RAW hazards: I1 – I2, I1 – I4, I2 – I3, I2 – I4, I2 – I5
WAW hazards: I2 – I4
WAR hazards: I3 – I4 and I2 – I4

Q.9
EA
The average seek time and rotational delay in a disk system are 6 ms and 3 ms, respectively. The rate of
data transfer to or from the disk is 30 MBps and all disk accesses are of 8 KB of data. Disk DMA
controller, the processor, and the main memory are all attached to a single bus. The data bus width is 32
bits, and a bus transfer to or from the main memory takes 10 nanoseconds. How many disk units are there
that can be simultaneously transferring data to or from the main memory?
(a) 11 (b) 12
(c) 13 (d) 14
E

9. (c)
Rate of transfer to or from any one disk = 30 MBps.
AD

4B
Maximum memory transfer rate = = 400 × 106 Bps = 400 MBps
10 × 10 −9
Since rate of data transfer = 30 MBps

⎡ 400 ⎤
Here number of disk transfer = ⎢ ⎥ = 13
⎢ 30 ⎥
M

Therefore, 13 disks can simultaneously transfer data to or from the main memory.

6 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.10 A computer system has a main memory of 64 K words where a word is a byte in length. It also has a 32 B
cache organized as 4 lines of 8 words. The cache mapping function is the direct mapping function. The
tags in the cache are currently:

Cache line Tag

0 11011111010
1 00110001100
2 01010010111
3 10001000111

Consider memory addresses 73B2, DF45, 8C7C and 07E9. For each memory address, the cache line in
which they will be mapped are ______ respectively.
(a) 00, 01, 10, 11 (b) 10, 00, 11, 01
(c) 11, 00, 01, 10 (d) 01, 10, 00, 11

SY
10. (b)
The address division will be given as:
11 2 3
Tag Line Word Line

73B2 0111 001110 1100 10 10

DF45

8C7C
EA 11 0 11111 0 1 0 0 0 1 0 1

1 0 0 0 11 0 0 0 11111 0 0
00

11

07E9 0 0 0 0 0 111111 0 1 0 0 1 01

Numerical Data Type Questions : Q. 11 to Q. 16 carry 1 mark each

Q.11 Consider a scenario where instruction operation codes are represented in 8 bits, memory addresses are
E

64 bits and register addresses are 6 bits and data values are 32 bit integers.
Consider the code sequence for “C = A + B” is as follows:
AD

Register Register
Stack Accumulator (Register-Memory) (Load-store)
Push A Load A Load R1, A Load R1, A
Push B Add B Add R3, R1, B Load R2, B
Add Store C Store R3, C Add R3, R1, R2
Pop C Store R3, C
M

Note that the add instruction has implicit operands for stack and accumulator architectures explict operands
for register architectures. It is assumed that A, B and C all being in memory and that the values of A and
B can not be destroyed. The total code size is ______ (in bits).

11. (940)
Stack Accumulator Register-Memory Load-store
Push (A) 8 + 64 Load A 8 + 64 Load R1, A 8 + 6 + 64 Load R1, A 8 + 6 + 64
Push (B) 8 + 64 Add B 8 + 64 Add R3, R1, B 8 + 6 + 6 + 64 Load R2, B 8 + 6 + 64
Add 8 Store C 8 + 64 Store R3, C 8 + 6 + 64 Add R3, R1, R2 8 + 6 + 6 + 6
Pop (C) 8 + 64 Store R3, C 8 + 6 + 64
= 224 bits = 216 bits = 240 bits = 260 bits
Total size = 224 + 216 + 240 + 260 = 940 bits

7 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.12 Assume that there are 251 different opcode and 32 registers in the machine. Every instruction has 3
register as input and 1 register as output [opcode R1, R2, R3, R4]. The number of bits to encode an
instruction is _____.

12. (28)
251 opcodes ⇒ 8 bits for each register

∴ Opcode R1, R2, R3, R4

8 bits + 5 × 4 bits = 8 + 20 = 28 bits
[∵ 4 for 4 registers i.e., R1, R2, R3, R4].

Q.13 Consider the following IEEE single precision floating point number shown below
01000011110100000000000000000000

SY
The octal equivalent of above number is ________.

13. (640)
Format of single precision floating point is
32 bits

S Exponant Mantissa

1 bit
EA 8 bits 23 bits

0 10000111 101000000000...00

Value = 1.M × 2E–127

= 1.1010 × 2135 – 127
= (1.1010)2 × 28
E

= 1.625 × 28
= (416)10
Octal representation
AD

8 416
8 52 0
6 4

Octal representation is (640).

Q.14 A RISC processor has 208 registers. Each window has 4 input, 8 local and 4 output register. The total
number of global registers are ______. The register windows are 16 in numbers.
M

14. (16)
Number of registers in RISC = G + W (L + C)
208 = G + 16 (8 + 4)
G = 16

8 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.15 A PC relative mode branch instruction is 5 B long. The address of the instruction in decimal is 238715. The
branch target address if the signed displacement is –32 is _____.

15. (238688)

238715 I1
238716 I1 Fetch I1 IR:
238717 I1 PC = 238720
238718 I1
238719 I1
238720
238721

Effective address = PC + Relative value

SY
= 238720 + (–32)
= 238688

Q.16 Consider a hypothetical control unit that supports 5 groups of mutually exclusive control signals. Also
assume that group-1 and group-2 are using horizontal micro-programming whereas group-3, 4 and 5 are
using vertical micro-programming. The total number of bits used for control words are ______.
Groups G1 G2 G3 G4 G5
EA
Control signals 3 9 6 13 10

16. (23)
Group-1 and 2 are using horizontal micro-programming,
Hence, total bits are:
3 + 9 = 12
Group-3, 4 and 5 are using vertical micro-programming,
E

Hence, total bits are:

⎡⎢log2 6⎤⎥ + ⎡⎢log2 13⎤⎥ + ⎡⎢log2 10⎤⎥ = 3 + 4 + 4 = 11
AD

Total bits for control word = 12 + 11 = 23 bits

Multiple Choice Questions : Q.17 to Q.28 carry 2 marks each

Q.17 Consider the following statements:

S1: Comparing the time T1 taken for a single instruction on a pipelined CPU with time T2 taken on a non-
pipelined but identical CPU we can say that T1 ≤ T2.
S2: The performance of pipelined processor suffers if the pipeline stages have different delays.
M

Which of the following option is correct?

(a) Both S1 and S2 are correct (b) only S1 is correct
(c) Only S2 is correct (d) None of S1 or S2 is correct

17. (c)
• In pipelined CPU, there will be buffer delays. So, for single instruction non-pipelined CPU takes less
time compared to pipelined CPU.
• Structural dependencies cause hazards during pipelining.

9 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.18 Consider an instruction of indirect addressing mode. What are the number of memory reference by the
processor when instruction is a computation that requires a single operand and when it is a branch
instruction respectively?
(a) 3, 3 (b) 2, 3
(c) 3, 2 (d) 2, 2

18. (c)
When instruction is a computation:
Memory reference : Fetch instruction
Fetch reference of the operand
Fetch operand
Total 3 memory references.
When instruction is a branch:

SY
Memory reference : Fetch instruction
Fetch operand reference and loading program counter
Total 2 memory references.
Q.19 Consider a scenario where a non-pipelined processor has a clock rate of 5 GHz which has a average CPI
of 5. An upgrade to the processor includes a 5-stage pipeline where the clock rate is 3 GHz. What is the
speed-up achieved by using upgrated processor?
(a) 3.03
(c) 4.62
EA(b) 4.02
(d) 2.34

19. (a)
For non-pipelined processor:

(p × 5)
For p-instruction execution time = = p ns
5
E

Pipelined processor:

p
For p-instruction execution time = = 0.33p ns
3
AD

p
Speed-up = = 3.03
0.33p

Q.20 Consider the following statement. Out of the statements choose the one which best characterize computers
that use memory mapped I/O.
M

(a) the computer provides special instruction for manipulating I/O port.
(b) I/O ports are placed at address on bus and as accessed just like other memory location.
(c) to perform an I/O operation, it is sufficient to place the data in an address and call the channel to
perform the operation.
(d) ports are referenced only by memory mapped instruction of the computer and are located at hardwired
memory location.

20. (b)
Memory mapped I/O uses the same address bus to address both memory and I/O devices the memory
and registers of the I/O devices are mapped to address values.
So, when an address is accessed by the CPU, it may refer to a portion of physical RAM, but it can also
refer to memory of I/O device.

10 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.21 Consider a 4-way set associative Cache (initially empty) with total 16 cache blocks. The main memory
consist of 512 blocks and the request for memory blocks in the order which is given as:
0, 31, 17, 45, 67, 85, 213, 167, 302, 17, 31, 67, 85, 167, 37, 39, 41, 17, 7, 31
What is the number of misses in the cache when least recently policy and least frequently policy is used
respectively?
(a) 12, 13 (b) 12, 14
(c) 14, 13 (d) 13, 14

21. (c)

LRU : 0 LFU : 0

Set-0 Set-0

SY
17 17
45 37 45 37
Set-1 Set-1
85 Total misses 85 Total misses
in cache = 14 in cache = 13
213 41 213 41
302 302
Set-2 Set-2
EA
31 7 31
67 31 Set-3 67 Set-3
167 167
39 39 7

Q.22 Consider 4-way set associative cache of a 64 KB organized into a 32 blocks. Main memory size is 4 GB.
E

In the cache controller, each line in the set contain 1 valid, 1 modified and 2 replacement bits along with a
tag. How much space is required in the cache controller to store the tag information (Meta data) (in Kb)?
(a) 44 (b) 22
AD

(c) 32 (d) 18

22. (a)
64 K
Number of lines = = 211
32

211 211
M

Number of sets = = 2 = 29
4 2

32 bits
Tag SO WO

18 bits log229 = 9 log232 = 5 bit

Tag memory size = S × P × # tag bits

= 29 × 4 × (18 + 1 + 1 + 2)
= 29 × 22 × 22 bits
= 210 × 2 × 22 bits
= 44 K bits

11 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.23 Match List-I with List-II and select the correct answer using the codes given below the lists:
List-I
A. Programmed IO
B. Interrupt driven IO
C. Direct memory access
List-II
1. On I/O command issued by the processor, the process busy-waits for the operation to be completed.
2. After issuing an I/O command, processor continues to execute subsequent instructions, and is intrupted
by the concerned module, when latter has completed its work.
3. Processor send a request for the transfer of a block of data to the concerned module and is interupted
when the entire block has been transferred.
Which of the following code is correct?

SY
Codes:
A B C
(a) 1 3 2
(b) 1 2 3
(c) 2 1 3
(d) 1 3 2

23. (b)
Pr
EA
ogrammed I/O: Processor issues an I/O command, on behalf of a processor, to an IO module; that
Programmed
process then busy-waits for the operation to be completed before proceeding.
Interrupt driven I/O: The processor isues an IO command on behalf of a process, continues to execute
subsequent instruction, and is interrupted by the IO module when the latter has completed its work.
Direct memory access: A DMA module controls the exchange of data between main memory and IO
module.
E

Q.24 Consider a system that uses interrupt-driven I/O for a particular device which has an average data transfer
rate of 10 KBps. The processing of the interrupt which includes the time to jump to ISR,, its execution and
returning to the main program is 250 μs. What fraction of processor time of consume by IO device, if IO
AD

device interrupts for every 2 byte (in %)?

(a) 80 (b) 40
(c) 12 (d) None of these

24. (a)
Number of interupts generated = 5000 interrupt / sec
M

Time by 1 interrupt = 200 μsec

Time consumed by every interrupt = 250 μs
Fraction of processor time consumed = 200/250 = 0.8
In % = 0.8 × 100 = 80

12 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.25 Consider the cache memory which is 30 times faster than main memory and it can be uses 90% of the total
time. What is the speedup gain by cache memory?
(a) 7.33 (b) 7.46
(c) 7.69 (d) 7.52

25. (c)
1
Speedup (S) =
⎡ Cache % used ⎤
(1− Cache % used) + ⎢ ⎥
⎣ Speedup using cache ⎦

1 1 1
= = =
⎛F ⎞ ⎛ 0.9 ⎞ ⎛ 0.9 ⎞
(1 − F ) + ⎜ ⎟ (1 − 0.9) + ⎜ (0.1) + ⎜
⎝S⎠ ⎝ 30 ⎟⎠ ⎝ 30 ⎟⎠

SY
30
= = 7.69
3.9

Q.26 Consider the following program segment:

Instruction
Instruction Meaning
size (in word)
I1
I2
EA
Load r0 , 300
MOV r1, 5000
r0 ← [300]
r1 ← Mem [5000]
2
2
I3 MOV r2 , (r1 ) r2 ← Mem [r1] 1
I4 Add r0, r2 r0 ← r0 + r2 1
I5 MOV, 6000, r0 Mem [6000] ← r0 2
I6 HALT Machine Halts 1
E
Consider that the memory is byte addressable with size 16 bits, and the program has been loaded
starting from memory location (2000)10. What will be the return address saved in the stack, if an interrupt
occurs while the CPU has been halted after executing the HALT instruction?
AD

(a) 2015 (b) 2016

(c) 2017 (d) 2018

26. (b)

Instruction Instruction size Location

I1 Load r0 , 300 2 word 2000-2003
I2 MOV r1, 5000 2 word 2004-2007
M

I3 MOV r2 , (r1 ) 1 word 2008-2009

I4 Add r0, r2 1 word 2010-2011
I5 MOV, 6000, r0 2 word 2012-2015
I6 HALT 1 word 2016-2017

∴ Since 1 word is of 2 bytes.

If an interrupt occurs, the CPU has been halted after executing the HALT instruction, the return address
2016 is saved in the stack.

13 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.27 Suppose that a processor has access to three levels of memory. Level 1 contain 2000 words and has an
access time of 0.02 msec. Level 2 contain 10,000 words and has an access time of 0.2 msec. Level 3
contains 20,000 words and has an access time of 2 msec. Assume that if a word to be accessed is in level
1, then processor access it directly. If it is in level 2 the word is first transferred to L1 and then accessed
by the processor. Similarly for L3 the word is transferred to L2 then to L1 and then accessed. The hit ratio
for level 1 is 0.65 and for level 2 is 0.45. What is the average access time (in μsec)?
(a) 232.3 (b) 475
(c) 131.1 (d) 429.5

27. (b)
Tavg = h1 t1 + (1 – h1)h2 (t2 + t1) + (1 – h1) (1 – h2) (t3 + t2 + t1)
= 0.65 × 0.02 + 0.35 × 0.45 × 0.22 + 0.35 × 0.55 × 2.22
= 0.013 + 0.03465 + 0.42735

SY
= 0.475 = 475 μsec

Q.28 Consider the following floating point format

15 14 8 7 0

Sign bit Exponent Mantissa

Excess-64
EA
Mantissa is a pure fraction in sign-magnitude form. What is the representation of decimal number 0.625 × 218
in hexadecimal without normalization and rounding off ?
(a) 52B0 (b) 52A0
(c) 52A1 (d) None of these

28. (b)
Biased exponent = 18 + 64 = 82
Representing 82 in binary
E

(82)2 = (1010010)2
Representing mantissa in binary
(0.625)10 = (0.10100000)
AD

Floating point representation is as follows:

Sign bit Exponent Mantissa

0 1010010 10100000

5 2 A 0
M

14 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Numerical Data Type Questions : Q.29 to Q.33 carry 2 marks each

Q.29 A computer system has a main memory consisting of 1 M 16 bit words. It also has a 4 K word cache
organized in the block set-associative manner, with 4 blocks per set and 64 words per block.
Assume that cache is initially empty. Suppose that the processor fetches 4532 words from locations 0, 1,
2, ..., 4351, in that order. It then repeat this fetch sequence 9 more times. If the cache is 10 times faster
than the main memory, the improvement factor resulting from the use of cache is _______. Assume LRU
algorithm is used for block replacement.

29. (2.15)
Address format:

10 4 6
Tag Set Word

SY
Words, 0, 1, 2, ..., 4351 occupies block 0 to 67 in the main memory. After blocks 0, 1, 2, ..., 63 have been
read from MM into the cache on first pass, the cache is full. Because, LRU is used, MM blocks that
occupy first four sets of 16 cache sets are always overwritten before they can be used on a successive
pass. In particular, MM blocks 0, 16, 32, 48 and 64 continually displace each other in competing for the
four block position in cache set 0. The same thing occurs in cache set 1 (MM blocks 1, 17, 33, 49, 65),
cache set 2 (MM blocks 2, 18, 34, 50, 66) and cache set 3 (MM blocks 3, 19, 35, 51, 67), MM blocks that
EA
occupy the last 12 sets (set 4 to 15) are fetched once on the first pass and remain in the cache for next
passes.
On the first pass, all 68 blocks of the loop must be fetched from the main memory. On each of the 9
successive passes, blocks in the last 12 sets of the cache (4 × 12 = 48) are found in the cache, and the
remaining 20(68 – 48) blocks must be fetched from the MM.
Time without cache
Improvment factor =
Time with cache
E

10 × 68 × 10x
= = 2.15
1× 68 × 11x + 9(20 × 11x + 48 × 1x)
AD

Q.30 Suppose that in 500 memory references there are 100 misses in first level and 50 miss in second level
cache. Assume that miss penalty from L2 cache to memory is 100 cycles. The hit time of L2 cache is 20
cycles. If there are 2 memory references per instruction, the average stall per instruction is _________.

30. (28)
2 memory references → 1 Instruction
500 memory references → ? instructions.
M

500
Number of instructions = = 250
2

⎡ # memory stalls ⎤ ⎡ # misses L1 ⎤ ⎡ # misses L2 ⎤

⎢ # Instructions ⎥ = ⎢⎣ # Instructions × hit L2 ⎥⎦ + ⎢⎣ # Instructions × miss panality L2 ⎥⎦
⎣ ⎦

= ⎡⎢ ⎤ ⎡ 50 ⎤
100
× 20 ⎥ + ⎢ × 100 ⎥
⎣ 250 ⎦ ⎣ 250 ⎦
= [20 + 8] = 28 cycles

15 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.31 Consider a CPU that executes at a clock rate of 200 MHz (5 ns per cycle) with a single level of cache.
CPIexecution i.e. CPI with ideal memory is 1.1. Instruction mix are 50% arithmetic / logical, 30% load / store,
20% control instruction. Assume the cache miss rate is 15% and a miss penalty of 5 cycles. The number
of times cpu with ideal memory is faster when no miss-occurs _______.

31. (1.88)
CPI = CPIexecution + Memory stall per instruction ...(1)
Memory stall per instruction = Memory access / Instruction ∗ Miss rate ∗ Miss penalty ...(2)
Memory access / Instruction = Instruction fetch + Load / store = 1 + 0.3 = 1.3 ...(3)
from (2) and (3)
Memory stall / Instruction = 1.3 × 0.15 × 5 = 0.975 ...(4)
from (1) and (4)
CPI = 1.1 + 0.975 = 2.075

SY
2.075
The ideal memory CPU with no misses = = 1.88 time faster
1.1

Q.32 A DMA module is transferring characters to memory using cycle stealing mode, from a device which is
transmitting at a rate of 19200 bps. The rate at which processor is fetching the instruction is 2 million
instructions per second (2 MIPS). Due to DMA, CPU slowed down by ______ (in %, upto 2 decimal

32.
places).

0.11 (0.10 - 0.12)

EA
DMA transfer character at rate of 19200 bpsec
8 bit = 1 character
So, 192000 b = 2400 character
So, 1 sec = 2400 character
1
E

1 character = = 416.7 × 10 −6 sec

2400
Processor fetch rate is 2 MIPS
1 MIPS = 1 sec
AD

1
1 Instruction = = 0.5 micro-sec
2 × 106

0.5 × 10 −6
% slow down using DMA = × 100
416.7 × 10 −6
0.5
M

= = 0.11%
416.7

16 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.33 Consider a multiplier pipeline with 5 stages which consist of input lines X and Y and output line Z. The
pipeline has a register R as its output, where the temporary result can be stored and feed back to S1 at a
later point in time. The inputs X and Y are multiplexed with the outputs R and Z.
Z
X
S1 S2 S3 S4 R
Y

Assume that elements of vector A are fed in to the pipeline through input X, one element per cycle. The
minimum number of clock cycles required to compute the product of an element vector.
The following code is running on a above pipeline with operand forwarding.

SY
Instruction Meaning
I1: Load ACC, R ACC ← (R) {R = Ai}
I2: Inc, R R ← (R) + 1
I3: Mul ACC, R ACC ← (ACC) × (R)
I4: Store R, ACC R ← (ACC)
EA
How many cycles required to compute the program __________.

33. (7)
The minimum number of clock cycles can be obtained by writing its assembly code. The process in
obtaining the outputs Z and R from input line X or Y via the same manner, such that the codes are not
much different except there is a line code to execute store command when using input line X. The code is
as follows:
Instruction Meaning
E

I1: Load ACC, R ACC ← (R) {R = Ai}

I2: Inc, R R ← (R) + 1
I3: Mul ACC, R ACC ← (ACC) × (R)
AD

I4: Store R, ACC R ← (ACC)

Constructing the table:

1 2 3 4 5 6 7
I1 F D E W
I2 F D E W
M

I3 F D E W
I4 F D E W

So, the minimum clock cycles required to complete one process is 7 clock cycles.

„„„„„

17 • Computer Organisation (Basic Level) www.madeeasy.in © Copyright : MADE EASY