Computer Organization

A 4 kilobyte (KB) byte-addressable memory is
realized using four 1 KB memory blocks. Two
input address lines (IA4 and IA3) are connected
to the chip select (CS) port of these memory
blocks through a decoder as shown in the figure.
The remaining ten input address lines from IA11-
IA0 are connected to the address port of these
blocks. The chip select (CS) is active high.

The input memory addresses (IA11-IA0), in
decimal, for the starting locations (Addr = 0 ) of
each block (indicated as X1, X2, X3, X4 in the
figure) are among the options given below.
Which one of the following options is
CORRECT?

• (a)(0,1,2,3)
• (b)(0,1024,2048,3072)
• (c)(0,8,16,24)
• (d)(0,0,0,0)

If the numerical value of a 2-byte unsigned integer
on a little endian computer is 255 more than that
on a big endian computer, which of the following
choices represent(s) the unsigned integer on a little
endian computer?

• (a)0x6665
• (b)0x 0001
• (c)0x4243
• (d)0x 0100

The chip select logic for a certain DRAM chip in a
memory system design is shown below. Assume that
the memory system has 16 address lines denoted by
A15 to A0. What is the range of address (in
hexadecimal) of the memory system that can get
enabled by the chip select (CS) signal?

• (a)C800 to CFFF
• (b)CA00 to CAFF
• (c)C800 to C8FF
• (d)DA00 to DFFF

A 32 -bit wide main memory unit with a capacity of
1 GB is built using 256M × 4-bit DRAM chips.
The number of rows of memory cells in the DRAM
chip is 214 .The time taken to perform one refresh
operation is 50 nanoseconds.The refresh period is 2
milliseconds.The percentage(rounded to the
closest integer)of the time available for performing
the memory read/write operations in the main
memory unit is   .
Computer Organization and Architecture

A processor can support a maximum memory of 4
GB, where the memory is word-addressable (a
word consists of two bytes). The size of address bus
of the processor is at least   bits.

How many 32k × 1 RAM chips are needed to
provide a memory capacity of 256 K-bytes?

• (a)8
• (b)32
• (c)64
• (d)128

Which one of the following dependencies among
the register operands of different instructions can
cause a data hazard in a pipelined processor?

• (a)Read-after-read
• (b)Read-after-write
• (c)Write-after-read
• (d)Write-after-write

The EX stage of a pipelined processor performs
the memory read operations for LOAD
instructions, and the operations for the arithmetic
and logic instructions. Let tEX denote the time
taken by the EX stage to perform the operation for
an instruction. For each instruction type, the
values of tEX and M (the number of instructions of
that type in a sequence of 100 instructions for a
program P), are given in the table below. The
duration of the pipeline clock cycle is 1
nanosecond. Assume that the latch time for the
interstage buffers in the pipeline is negligible.

When program P is executed, the number of clock
cycles for which the pipeline is stalled due to
structural hazards in the EX-stage is
.
(answer in integer).

A non-pipelined instruction execution unit that
operates at 1.6 GHz clock takes an average of 5
clock cycles to complete the execution of an
instruction. To improve the performance, the system
was pipelined with a goal of achieving an average
throughput of one instruction per clock cycle.
However, it could operate only at 1.2 GHz due to
pipeline overheads. While executing a program in
the pipelined design, 30% of instructions
encountered a stall of 2 cycles due to pipeline
hazards. The speed-up obtained by the pipelined
design over the non-pipelined one for this program
is
. (rounded off to two decimal places)
Note: 1G = 109

A 5-stage instruction pipeline has stage delays of 180,
250, 150, 170, and 250, respectively, in nanoseconds.
The delay of an inter-stage latch is 10 nanoseconds.
Assume that there are no pipeline stalls due to
branches and other hazards. The time taken to process
1000 instructions in microseconds is
.
(Rounded off to two decimal places)
FDIV
3.2
5
All other
instructions
Less than 1.0
35
Instruction
tEX (in ns)
M
LOAD
1.8
15
IMUL
1.5
10
IDIV
2.5
5
FADD
1.7
10
FSUB
1.7
5
FMUL
2.8
15
Computer Organization and Architecture

An instruction format has the following structure:
Instruction Number: Opcode destination reg,
source reg-1, source reg-2
Consider the following sequence of instructions to
be executed in a pipelined processor:
I1 : DIVR3,R1,R2
I2 : SUB R5,R3,R4
I3 : ADDR3,R5,R6
I4: MUL R7,R3,R8
Which of the following statements is/are TRUE?

• (a)There is a RAW dependency on R3 between I1 and I2
• (b)There is a WAR dependency on R3 between I1 and I3
• (c)There is a RAW dependency on R3 between I2 and I3
• (d)There is a WAW dependency on R3 between I3 and I4

Consider a 5-stage pipelined processor with
Instruction Fetch (IF), Instruction Decode (ID),
Execute (EX), Memory Access (MEM), and
Register Writeback (WB) stages. Which of the
following statements about forwarding is/are
CORRECT?

• (a)In a pipelined execution, forwarding means the result from a source stage of an earlier instruction is passed on to the destination stage of a later instruction.
• (b)In forwarding, data from the output of the MEM stage can be passed on to the input of the EX-stage of the next instruction.
• (c)Forwarding cannot prevent all pipeline stalls.
• (d)Forwarding does not require any extra hardware to retrieve the data from the pipeline stages.

A
non-pipelined
instruction
execution
unit
operating at 2 GHz takes an average of 6 cycles to
execute an instruction of a program P. The unit is
then redesigned to operate on a 5-stage pipeline at
2 GHz. Assume that the ideal throughput of the
pipelined unit is 1 instruction per cycle. In the
execution of program P, 20% instructions incur an
average of 2 cycles stall due to data hazards and 20%
instructions incur an average of 3 cycles stall due to
control hazards. The speedup (rounded off to one
decimal place) obtained by the pipelined design over
the non-pipelined design is

The baseline execution time of a program on a 2GHz
single core machine is 100 nanoseconds (ns). The
code corresponding to 90% of the execution time can
be fully parallelized. The overhead for using an
additional core is 10 ns when running on a multicore
system. Assume that all cores in the multicore system
run their share of the parallelized code for an equal
amount of time.
The number of cores that minimize the execution time
of the program is
.

Consider a 3-stage pipelined processor having a
delay of 10 ns (nanoseconds), 20 ns, and 14 ns, for
the first, second, and the third stages, respectively.
Assume that there is no other delay and the
processor does not suffer from any pipeline hazards.
Also assume that one instruction is fetched every
cycle.
The total execution time for executing 100
instructions on this processor is
ns.

A processor X1 operating at 2 GHz has a standard 5-
stage RISC instruction pipeline having a base CPI
(cycles per instruction) of one without any pipeline
hazards. For a given program P that has 30% branch
instructions, control hazards incur 2 cycles stall for
every branch. A new version of the processor X2
operating at the same clock frequency has an
additional
branch
predictor
unit
(BPU)
that
completely eliminates stalls for correctly predicted
branches. There is neither any savings nor any
additional stalls for wrong predictions. There are no
structural hazards and data hazards for X1 and X2. If
the BPU has a prediction accuracy of 80%, the speed
up (rounded off to two decimal places) obtained by
X2 over X1 in executing P is
.
Computer Organization and Architecture

Consider a pipelined processor with 5 stages,
Instruction Fetch (IF), Instruction Decode (ID),
Execute (EX), Memory Access (MEM), and Write
Back (WB). Each stage of the pipeline, except the
EX-stage, takes one cycle. Assume that the ID stage
merely decodes the instruction and the register read
is performed in the EX-stage. The EX-stage takes
one cycle for ADD instruction and two cycles for
MUL instruction. Ignore pipeline register latencies.
Consider the following sequence of 8 instructions:
ADD, MUL, ADD, MUL, ADD, MUL, ADD,
MUL
Assume that every MUL instruction is data-
dependent on the ADD instruction just before it and
every ADD instruction (except the first ADD) is
data-dependent on the MUL instruction just before
it. The speedup is defined as follows:

Speedup = Execution time without operand forwarding
Execution time with operand forwarding

The Speedup achieved in executing the given
instruction sequence on the pipelined processor
(rounded to 2 decimal places) is
.
and 50% of the branch instructions cause stalls of 2
cycles each. Assume that there are no stalls
associated with the execution of ALU instructions.
For this program, the speedup achieved by the
pipelined processor over the non-pipelined processor
(round off to 2 decimal places) is
.

A five-stage pipeline has stage delays of 150, 120,
150, 160 and 140 nanoseconds. The registers that
are used between the pipeline stages have a delay
of 5 nanoseconds each.
The total time to execute 100 independent
instructions on this pipeline, (assuming there are no
pipeline stalls) is
nanoseconds.

Consider a non-pipelined processor operating at
2.5 GHz. It takes 5 clock cycles to complete an
instruction. You are going to make a 5-stage
pipeline out of this processor. Overheads
associated with pipelining force you to operate the
pipelined processor at 2 GHz. In a given program,
assume that 30% are memory instructions, 60%
are ALU instructions and the rest are branch
instructions. 5% of the memory instructions cause
stalls of 50 clock cycles each due to cache misses

The instruction pipeline of a RISC processor has the
following stages: Instruction Fetch (IF), Instruction
Decode (ID), Operand Fetch (OF), Perform
Operation (PO) and Writeback (WB). The IF, ID, OF
and WB stages take 1 clock cycle each for every
instruction. Consider a sequence of 100 instructions.
In the PO stage, 40 instructions take 3 clock cycles
each, 35 instructions take 2 clock cycles each, and the
remaining 25 instructions take 1 clock cycle each.
Assume that there are no data hazards and no control
hazards.
The number of clock cycles required for completion
of execution of the sequence of instructions is

.

Instruction execution in a processor is divided into
5 stages,Instruction Fetch(IF),Instruction
Decode(ID),Operand fetch(OF),Execute
(EX),and Write Back(WB).These stages
take 5,4,20, 10 and 3 nanoseconds(ns)
respectively.A pipelined implementation of the
processor requires buffering between each pair of
consecutive stages with a delay of 2 ns .Two
pipelined implementation of the processor are
contemplated:
i.A naive pipeline implementation(NP)with 5
stages and
ii.An efficient pipeline(EP)where the OF
stage is divided into stages OF1 and OF2 with
execution times of 12 ns and 8 ns respectively.
The speedup(correct to two decimal places)
achieved by EP over NP in executing 20
independent instructions with no hazards is
.
Computer Organization and Architecture

Suppose the functions F and G can be computed in
5 and 3 nanoseconds by functional units UF and UG,
respectively. Given two instances of UF and two
instances of UG, it is required to implement the
computation F(G(Xi)) for 1 ≤ i ≤ 10. Ignoring all
other delays, the minimum time required to
complete this computation is
nanoseconds.

Consider a 3 GHz (gigahertz) processor with a
three-stage pipeline and stage latencies τ1, τ2, and τ3
such that τ1 = 3τ2/4 = 2τ3. If the longest pipeline
stage is split into two pipeline stages of equal
latency, the new frequency is
 GHz,
ignoring delays in the pipeline registers.

The stage delays in a 4-stage pipeline are 800, 500,
400 and 300 picoseconds. The first stage (with
delay 800 picoseconds) is replaced with a
functionally equivalent design involving two stages
with respective delays 600 and 350 picoseconds.
The throughput increase of the pipeline is percent.

Consider the following reservation table for a
pipeline having three stages S1, S2 and S3.

The minimum average latency (MAL) IS

Consider the sequence of machine instructions
given below

In the above sequence, R0 to R8 are general purpose
registers. In the instructions shown, the first register
stores the result of the operation performed on the
second and the third registers. This sequence of
instructions is to be executed in a pipelined
instruction processor with the following 4 stages:
(1)
Instruction Fetch and Decode (IF)
(2)
Operand Fetch (OF)
(3)
Perform Operation (PO) and
(4)
Write back the result (WB).
The IF, OF and WB stages take 1 clock cycle each for
any instruction. The PO stage takes 1 clock cycle for
ADD or SUB instruction, 3 clock cycles for MUL
instruction and 5 clock cycles for DIV instruction.
The pipelined processor uses operand forwarding
from the PO stage to the OF stage. The number of
clock cycles taken for the execution of the above
sequence of instructions is
.

Consider a non-pipelined processor with a clock rate
of 2.5 gigahertz and average cycles per instruction of
four. The same processor is upgraded to a pipelined
processor with five stages; but due to the internal
pipeline delay, the clock speed is reduced to 2
gigahertz. Assume that there are no stalls in the
pipeline. The speedup achieved in this pipelined
processor is
,

Consider the following code sequence having five
instructions from I1 to I5. Each of these instructions
has the following format.
OP Ri, Rj, Rk
Where operation OP is performed on contents of
registers Rj and Rk and the result is stored in register
MUL
R5, R0, R1
DIV
R6, R2, R3
ADD
R7, R5, R6
SUB
R8, R7, R4
Computer Organization and Architecture

Ri.
I1 : ADD R1, R2, R3
I2 : MUL R7, R1, R3
I3 : SUB R4, R1, R5
I4 : ADD R3, R2, R4
I5: MUL R7, R8, R9
Consider the following three statements.
S1: There is an anti-dependence between
instructions I2 and I5
S2: There is an anti-dependence between
instructions I2 and I4
S3: Within an instruction pipeline an anti-
dependence always creates one or more stalls
Which one of the above statements is/are
correct?

• (a)Only S1 is true
• (b)Only S2 is true
• (c)Only S1 and S3 are true
• (d)Only S2 and S3 are true

Consider two processors P1 and P2 executing the
same instruction set. Assume that under identical
conditions, for the same input, a program running
on P2 takes 25% less time but incurs 20% more
CPI (clock cycles per instruction) as compared to
the program running on P1. If the clock frequency
of P1 is 1 GHZ , then the clock frequency of P2 (in
GHz ) is    .

An instruction pipeline has five stages, namely,
instruction fetch (IF), instruction decode and
register fetch (ID/RF), instruction execution (EX),
memory access (MEM), and register writeback
(WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns,
and
0.75
ns,
respectively
(ns
stands
for
nanoseconds). To gain in terms of performance, the
designers have decided to split the ID/RF stage into
three stages (ID, RF1, RF2) each of latency 2.2/3
ns. Also, the EX stage is split into two stages (EX1,
EX2) each of latency 1 ns. The new design has a
total of eight pipeline stages. A program has 20%
branch instructions which execute in the EX stage and
produce the next instruction pointer at the end of the
EX stage in the old design and at the end of the EX2
stage in the new design. The IF stage stalls after
fetching a branch until the next instruction pointer is
computed. All instructions other than the branch
instruction have an average CPI of one in both the
designs. The execution times of this program on the
old and the new design are P and Q nanoseconds,
respectively. The value of P/Q is
.

Consider the following processors (ns stands for
nanoseconds). Assume that the pipeline registers have
zero latency.
P1: Four – stage pipeline with stage latencies 1ns, 2
ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1ns, 1.5
ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage latencies 0.5 ns, 1
ns, 1 ns, 0.6 ns. 1 ns.
P4: Five-stage pipeline with stage latencies 0.5 ns, 0.5
ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock
frequency?

• (a)P1
• (b)P2
• (c)P3
• (d)P4

Consider a 6-stage instruction pipeline, where all
stages are perfectly balanced. Assume that there is no
cycle-time overhead of pipelining. When an
application is executing on this 6-stage pipeline, the
speedup achieved with respect to non-pipelined
execution is 25% if the instructions incur 2 pipeline
stall cycles is
.

Consider an instruction pipeline with five stages
without any branch prediction: Fetch Instruction (FI),
Decode Instruction (DI), Fetch Operand (FO),
Execute Instruction (EI) and Write Operand (WO).
The stage delays for FI, DI, FO, EI and WO are 5 ns,
7 ns, 10 ns, 8 ns and 6 ns, respectively. There are
Computer Organization and Architecture

intermediate storage buffers after each stage and
the delay of each buffer is 1 ns. A program
consisting of 12 instructions I1, I2, I3, .... I12 is
executed in this pipelined processor. Instruction I4
is the only branch instruction and its branch target
is I9. If the branch is taken during the execution of
this program, the time (in ns) needed to complete
the program is

• (a)132
• (b)165
• (c)176
• (d)328

Register renaming is done in pipelined processors

• (a)as an alternative to register allocation at compile time
• (b)for efficient access to function parameters and local variables
• (c)to handle certain kinds of hazards
• (d)as part of address translation

Consider an instruction pipeline with four stages
(S1, S2, S3 and S4) each with a combinational
circuit only. The pipeline registers are required
between each stage and at the end of the last stage.
Delays for the stages and for the pipeline registers
are as given in the figure:

What is the approximate speed up of the pipeline
in steady state under ideal conditions when
compared to the corresponding non-pipeline
implementation?

• (a)4.0
• (b)2.5
• (c)1.1
• (d)3.0

A 5-stage pipelined processor has Instruction Fetch
(IF), Instruction Decode (ID), Operand Fetch (OF),
Perform Operation (PO) and Write Operand (WO)
stages. The IF, ID, OF and WO stage take 1 clock
cycle each for any instruction. The PO stage takes 1
clock cycle for ADD and SUB instructions ,3 clock
cycles for MUL instruction, and 6 clock cycles for
DIV instruction respectively. Operand forwarding is
used in the pipeline. What is the number of clock
cycles needed to execute the following sequence of
instructions?

• (a)13
• (b)15
• (c)17
• (d)19

Consider a 4 stage pipeline processor. The number of
cycles needed by the four instructions I1, I2, I3, I4 in
stages S1, S2, S3, S4 is shown below.

What is the number of cycles needed to execute the
following loop?
For (i = 1 to 2) {I1; I2; I3; I4;}

• (a)16
• (b)23
• (c)28
• (d)30 Computer Organization and Architecture

Delayed branching can help in the handling of
control hazards
The following code is to run on a pipelined
processor with one branch delay slot:
I1: ADD R2 ← R7 + R8
I2: SUB R4 ← R5 - R6
I3: ADD R1 ← R2 + R3
I4: STORE Memory [R4] ← R1
BRANCH to Label if R1 == 0
Which of the instructions I1, I2, I3 or I4 can
legitimately occupy the delay slot without any other
program modification?

• (a)I1
• (b)I2
• (c)I3
• (d)I4

Which of the following are NOT true in a pipelined
processor?
1. Bypassing can handle all RAW hazards.
2. Register renaming can eliminate all register
carried WAR hazards.
3. Control hazard penalties can be eliminated by
dynamic branch prediction.

• (a)1 and 2 only
• (b)1 and 3 only
• (c)2 and 3 only
• (d)1, 2 and 3

Delayed branching can help in the handling of
control hazards
For all delayed conditional branch instructions,
irrespective of whether the condition evaluates to
true or false.

• (a)The instruction following the conditional branch instruction in memory is executed
• (b). The first instruction in the fall through path is executed
• (c). The first instruction in the taken path is executed
• (d). The branch takes longer to execute than any other instruction

A non-pipelined single cycle processor operating at
100MHz is converted into a synchronous pipelined
processor with five stages requiring
2.5nsec,1.5nsec,2nsec,1.5nsec and 2.5nsec,
respectively. The delay of the latches is 0.5nsec. The
speedup of the pipeline processor for a large number
of instructions is:

• (a)4.5
• (b)4.0
• (c)3.33
• (d)3.0

Consider a pipelined processor with the following
four stages:
IF: Instruction Fetch
ID: Instruction Decode and Operand Fetch
EX: Execute
WB: Write Back
The IF, ID, and WB stages take one clock cycle each
to complete the operation.
The number of clock cycles for the EX stage depends
on the instruction. The ADD and SUB instructions
need 1 clock cycle, and the MUL instruction needs 3
clock cycles in the EX stage.
Operand forwarding is used in the pipelined
processor.
What is the number of clock cycles taken to complete
the following sequence of instructions?

• (a)7
• (b)8
• (c)10
• (d)14 Computer Organization and Architecture

A processor takes 12 cycles to complete an
instruction
1.
The
corresponding
pipelined
processor uses 6 stages with the execution times of
3,2,5,4,6 and 2 cycles respectively. What is the
asymptotic speedup assuming that a very large
number of instructions are to be executed?

• (a)1.83
• (b)2
• (c)3
• (d)6

A CPU has a five-stage pipeline and runs at a 1
GHz frequency. Instruction fetch happens in the
first stage of the pipeline. A conditional branch
instruction computes the target address and
evaluates the condition in the third stage of the
pipeline.
The processor stops fetching new instructions
following a conditional branch until the branch
outcome is known.
A program executes 109 instructions out of which
20% are conditional branches.
If each instruction takes one cycle to complete on
average, then the total execution time of the
program is:

• (a)1.0 second
• (b)1.2 Seconds
• (c)1.4 Seconds
• (d)1.6 Seconds

A pipelined processor uses a 4-stage instruction
pipeline with the following stages: Instruction fetch
(IF), Instruction decode (ID), Execute (EX) and
Writeback (WB). The arithmetic operations as well
as the load and store operations are carried out in
the EX stage. The sequence of instructions
corresponding to the statement X=(S-R*(P+Q))/T
is given below. The
values of variables P,Q,R,S and T are available in
the registers R0,R1,R2,R3 and R4 respectively,
before the execution of the instruction sequence.
ADD R5,R0,R1 ;R5←R0 + R1
MUL R6,R2,R5 ;R6←R2 * R5
SUB R5,R3,R6 ;R5←R3 -R6
DIV R6,R5,R4 ;R6←R5/R4
STORE R6,X ;X←R6
The IF, ID and WB stages take 1 clock cycle each.
The EX stage takes 1 clock cycle each for the ADD,
SUB and STORE operations, and 3 clock cycles each
for MUL
and DIV operations. Operand forwarding from the
EX
stage to the ID stage is used. The number of Read-
After-Write (RAW) dependencies, Write-After-
Read( WAR) dependencies, and Write After-Write
(WAW) dependencies in the sequence of instructions
are, respectively,

• (a)2,2,4
• (b)3,2,3
• (c)4,2,2
• (d)3,3,2

A pipelined processor uses a 4-stage instruction
pipeline with the following stages: Instruction fetch
(IF), Instruction decode (ID), Execute (EX) and
Writeback (WB). The arithmetic operations as well as
the load and store operations are carried out in the EX
stage. The sequence of instructions corresponding to
the statement X=(S-R*(P+Q))/T is given below. The
values of variables P,Q,R,S and T are available in the
registers R0,R1,R2,R3 and R4 respectively, before the
execution of the instruction sequence.
ADD R5,R0,R1 ;R5←R0 + R1
MUL R6,R2,R5 ;R6←R2 * R5
SUB R5,R3,R6 ;R5←R3 -R6
DIV R6,R5,R4 ;R6←R5/R4
STORE R6,X ;X←R6
The IF, ID and WB stages take 1 clock cycle each.
The EX stage takes 1 clock cycle each for the ADD,
SUB and STORE operations, and 3 clock cycles each
for MUL
and DIV operations. Operand forwarding from the
EX
stage to the ID stage is used. The number of clock
cycles
required to complete the sequence of instructions i

• (a)10
• (b)12
• (c)14
• (d)16 Computer Organization and Architecture

A 5 stage pipelined CPU has the following
sequence of stages:
IF – Instruction fetch from instruction memory
RD – Instruction decode and register read
EX – Execute: ALU operation for data and
address computation
MA – Data memory access - for write access, the
register read at RD state is used.
WB – Register write back
Consider the following sequence of instructions:
I1: L R0, Loc1;
R0 ← M[Loc1]
I2: A R0, R0;
R0 ← R0 + R0
I3: A R2, R0;
R2 ← R2 - R0
Let each stage takes one clock cycle.
What is the number of clock cycles taken to
complete the above sequence of instructions
starting from the fetch of I1?

• (a)8
• (b)10
• (c)12
• (d)15

We have two designs D1 and D2 for a
synchronous pipeline processor. D1 has 5 pipeline
stages with execution times of 3 nsec, 2 nsec, 4
nsec, 2 nsec and 3 nsec while the design D2 has 8
pipeline stages each with 2 nsec execution time.
How much time can be saved using design D2
over design D1 for executing 100 instructions?

• (a)214 nsec
• (b)202 nsec
• (c)86 nsec
• (d)-200 nsec

Consider a processor P whose instruction set
architecture is the load-store architecture. The
instruction format is such that the first operand of
any instruction is the destination operand. Which
one of the following sequences of instructions
corresponds to the high-level language statement
Z = X + Y?
Note: X, Y, and Z are memory operands. R0, R1,
and R2 are registers.

• (a)ADD Z, X, Y
• (b)LOAD R0, X ADD Z, R0, Y
• (c)ADD R0, X, Y STORE Z, R0
• (d)LOAD R0, X LOAD R1, Y ADD R2, R0, R1 STORE Z, R2

Match each addressing mode in List I with a
data element or an element of a data structure
(in a high-level language) in List II.
List I
 P. Immediate
 Q. Indirect
 R. Base with index
 S. Base with offset/displacement
List II
1. Element of an array
2. Pointer
3. Element of a record
4. Constant

• (a)P-4, Q-3, R-1, S-2
• (b)P-4, Q-2, R-1, S-3
• (c)P-1, Q-4, R-3, S-2
• (d)P-2, Q-3, R-1, S-4

Consider a processor that has 16 general purpose
registers and it uses 2-byte instruction format for all
its instructions. Variable-sized opcodes are
permitted. There are three different types of
instructions; M-type, R-type, and C-type. Each M-
type instruction has 2 register operands and a 6-bit
immediate operand. Each R-type instruction has 3
register operands. Each C-type instruction has a
register operand and a 6-bit offset value. If there are
2 unique M-type opcodes and 7 unique R-type
opcodes, which one of the following options gives
the maximum number of unique opcodes possible
for C-type instructions?

• (a)8
• (b)4
• (c)64
• (d)16

An application executes 6.4 × 108 number of
instructions in 6.3 seconds. There are four types of
instructions, the details of which are given in the
table. The duration of a clock cycle in nanoseconds
is
(rounded off to one decimal place).

Instruction
type
Clock cycles
required per
instruction
(CPI)
Number of
instruction
executed
Branch
2
2.25 × 108
Load
5
1.20 × 108
Store
4
1.65 × 108
Arithmetic
3
1.30 × 108
3 3
Computer Organization and Architecture

Which of the following is/are part of an Instruction
Set Architecture of a processor?

• (a)The size of the cache memory
• (b)The clock frequency of the processor
• (c)The number of cache memory levels
• (d)The total number of registers

A processor has 64 general-purpose registers and
50 distinct instruction types. An instruction is
encoded in 32-bits. What is the maximum number
of bits that can be used to store the immediate
operand for the given instruction?

• (a)16
• (b)20
• (c)22
• (d)24

A processor with 16 general purpose registers uses
a 32-bit instruction format. The instruction format
consists of an opcode field, an addressing mode
field, two register operand fields, and a 16-bit
scalar field. If 8 addressing modes are to be
supported, the maximum number of unique
opcodes possible for every addressing mode is

A processor uses a 32-bit instruction format and
supports byte-addressable memory access. The
ISA of the processor has 150 distinct instructions.
The instructions are equally divided into two
types, namely R-type and I-type, whose formats
are shown below.
R-type Instruction Format:

I- type Instruction Format:

In the OPCODE, 1 bit is used to distinguish between
I-type and R-type instructions, and the remaining
bits indicate the operation. The processor has 50
architectural registers, and all register fields in the
instructions are of equal size.
Let X be the number of bits used to encode the
UNUSED field, Y be the number of bits used to
encode the OPCODE field, and Z be the number of
bits used to encode the immediate value/address
field The value of X + 2Y + Z is
.

Consider the given C-code and its corresponding
assembly code, with a few operands U1-U4 being
unknown. Some useful information as well as the
semantics of each unique assembly instruction is
annotated as inline comments in the code. The
memory is byte-addressable.

;assembly code (; indicates comments)
;r1-r5 are 32-bit integer registers
//C-code
;initialize r1=0, r2=10
;initialize r3, r4 with base address of a, b
L01: jeq r1, r2, end ;if(r1==r2) goto end
L02: lw, r5, 0(r4) ;r5 <- Memory[r4+0]
int a[10], b[10], i;
L03: sh1, r5, r5, U1 ;r5 <- r5 << U1
// int is 32 bit
L04: sw, r5, 0(r3) ;Memory[r3+0] <- r5
for(i=0; i<10; i++)
L05: add, r3, r3, U2 ;r3 <- r3+U2
a[i] = b[i] * 8;
L06: add, r4, r4, U3
L07: add, r1, r1, 1
L08: jmp U4 ;goto U4
L09: end
Which one of the following options is a CORRECT
replacement for operands in the position (U1, U2,
U3, U4) in the above assembly code?

• (a)(8, 4, 1, L02)
• (b)(3, 4, 4, L01)
• (c)(8, 1, 1, L02)
• (d)(3, 1, 1, L01) Computer Organization and Architecture

Consider the following instruction sequence
where registers R1, R2 and R3 are general
purpose and MEMORY [X] denotes the content
at the memory location X .

Instruction
Semantics
Instruction
Size
(bytes)
MOV
R1,(5000)
R1 ←
MEMORY[5000]
4
MOV
R2,(R3)
R2
←MEMORY[R3]
4
ADDR2,
R1
R2 ← R1 + R2
2
MOV
(R3), R2
MEMORY[R3]←
R2
4
INC R3
R3 ← R3 + 1
2
DEC R1
R1 ← R1 - 1
2
BNZ 1004
Branch if not zero
to the given
absolute address
2
HALT
Stop
1

Assume that the content of the memory location
5000 is 10 , and the content of the register R3 is
3000 . The content of each of the memory
locations from 3000 to 3010 is 50 . The
instruction sequence starts from the memory
location 1000. All the numbers are in decimal
format. Assume that the memory is byte
addressable.
After the execution of the program, the content
of memory location 3010 is

A processor has 64 registers and uses 16-bit
instruction format. It has two types of instructions:
I-type and R-type. Each I-type instruction contains
an opcode, a register name, and a 4-bit immediate
value. Each R-type instruction contains an opcode
and two register names. If there are 8 distinct I-type
opcodes, then the maximum number of distinct R-
type opcodes is
.

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 eight 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). The maximum
value of N is
.

The following are some events that occur after a
device controller issues an interrupt while the
process L is under execution.
(P) The processor pushes the process status of L
onto the control stack.
(Q) The processor finishes the execution of the
current instruction.
(R) The processor executes the interrupt service
routine.
(S) The processor pops the process status of L
from the control stack.
(T) The processor loads the new PC value based
on the interrupt.
Which one of the following is the correct order
in which these events above occur?

• (a)QPTRS
• (b)PTRSQ
• (c)TRPQS
• (d)QTPRS Computer Organization and Architecture GATE CSE – NAT 2016 SET- 2 (1-MARKS)

Consider a RISC machine where each instruction is
exactly 4 bytes long. Conditional and unconditional
branch instructions use the PC-relative addressing
mode, with the offset specified in bytes to the target
location of the branch instruction.
Furthermore, the offset is always with respect to the
address of the next instruction in the program
sequence.
Consider the following instruction sequence:

If the target of the branch instruction is i, then the
decimal value of the Offset is
.

Consider the C struct defined below:
struct data {
int marks [100];
char grade:
int cnumber;
l:
struct data student:

The base address of student is available in register
R1. The field student.grade can be accessed
efficiently using:

• (a)Post-increment addressing mode, (R1)+
• (b)Pre-decrement addressing mode, -(R1)
• (c)Register direct addressing mode, R1
• (d)Index addressing mode, X(R1), where X is an offset represented in 2's complement 16 -bit representation

A processor has 40 distinct instructions and 24
general purpose registers. A 32-bit instruction word
has an opcode, two register operands and an
immediate operand The number of bits available for
the immediate operand field is
.

Consider a Processor with 64 registers and an
instruction set of size twelve. Each instruction has
five distinct fields, namely, opcode, two source
register identifiers, one destination register
identifier, and a twelve-bit immediate value. Each
instruction must be stored in memory in a byte
aligned fashion. If a program has 100 instructions,
the amount of memory (in bytes) consumed by the
program text is
.

Consider a processor with byte-addressable memory.
Assume that all registers, including Program
Counter (PC) and Program Status Word (PSW), are
of size 2 bytes. A stack in the main memory is
implemented from memory location (0100)16 and it
grows upward The stack pointer (SP) points to the
top element of the stack. The current value of SP is
(016E)16. The CALL instruction is of two words, the
first word is the op-code and the second word is the
starting address of the subroutine (one word = 2
bytes). The CALL instruction is implemented as
follows:
• Store the current value of the PC in the stack.
• Store the value of the PSW register in the stack.
• Load the starting address of the subroutine in PC
The content of the PC just before the fetch of a
CALL instruction is (5FA0)16. After execution of the
CALL instruction, the value of the stack pointer is

• (a)(O16A) 16
• (b)(O16C) 16
• (c)(O170) 16
• (d)(O172) 16 Instr. No. Instruction i: add R2, R3, R4 i + 1: sub R5, R6, R7 i + 2: cmpR1, R9, R10 i + 3: beqR1, Offset Computer Organization and Architecture GATE MCQ – 2008 MCQ (1-MARKS) GATE MCQ – 2008 MCQ (2-MARKS)

For computers based on three-address instruction
formats, each address field can be used to specify
which of the following:
S1: A memory operand
S2: A processor register
S3: An implied accumulator register

• (a)Either S1 or S2
• (b)Either S2 or S3
• (c)Only S2 and S3
• (d)All of S1, S2 and S3

A machine has a 32-bit architecture, with 1-word
long instructions. It has 64 registers, each of which
is 32 bits long. It needs to support 45 instructions,
which have an immediate operand in addition to
two register operands. Assuming that the
immediate operand is an unsigned integer, the
maximum value of the immediate operand is

.

Consider a hypothetical processor with an
instruction of type LW R1, 20(R2), which during
execution reads a 32-bit word from memory and
stores it in a 32-bit register R1. The effective
address of the memory location is obtained by the
addition of a constant 20 and the contents of
register R2. Which of the following best reflects
the addressing mode implemented by this
instruction for operand in memory?

• (a)Immediate Addressing
• (b)Register Addressing
• (c)Register Indirect Scaled Addressing
• (d)Base or Indexed Addressing

Which of the following is/are true of the auto-
increment addressing mode?
I. It is useful in creating self-relocating code
II. If it is included in an Instruction Set Architecture,
then an additional ALU is required for effective
address calculation
III. The amount of increment depends on the size of
the data item accessed

• (a)I only
• (b)Il only
• (c)III only
• (d)II and III only

Which of the following must be true for the
RFE (Return From Exception) instruction on a
general purpose processor?
I.It must be a trap instruction
II. It must be a privileged instruction
III. An exception cannot be allowed to occur
during execution of an RFE instruction

• (a)I only
• (b)II only
• (c)I and II only
• (d)I, II and III only

Assume that EA = (X)+ is the effective address
equal to the contents of location X, with X
incremented by one word length after the
effective address is calculated; EA = -(X) is the
effective address equal to the contents of location
X, with X decremented by one word length before
the effective address is calculated; EA = (X)- is
the effective address equal to the contents of
location X, with X decremented by one word
length after the effective address is calculated.
The format of the instruction is (opcode, source,
destination), which means (destination ← source
op destination). Using X as a stack pointer, which
of the following instructions can pop the top two
elements from the stack, perform the addition
operation and push the result back to the stack.
GATE MCQ – 2008 MCQ (1-MARKS)
GATE MCQ – 2011 MCQ (1-MARKS)
Computer Organization and Architecture

• (a)ADD (X)-, (X)
• (b)ADD (X), (X)-
• (c)ADD -(X), (X)+
• (d)ADD -(X), (X)

Consider the following program segment. Here
R1, R2 and R3 are the general purpose registers.

Instruction
Operation
Instruction
Size (no.
of words)

MOV
R1,(3000)
R1 ← M3000]
2
LOOP:
MOV
R2,(R3)
R2←M[R3]
1

ADD R2,R1
R2 ← R1 + R2
1

MOV
(R3),R2
M[R3] ←R2
1

INC R3
R3←R3+1
1

DEC R1
R1 ← R1 - 1
1

BNZLOOP
Branch on not zero
2

HALT
Stop
1

Assume that the content of memory
location 3000 is 10 and the content of the
register R3 is 2000. The content of each of
the memory locations
from 2000 to 2010 is 100. The program is
loaded from the memory location 1000. All
the numbers are in decimal.
Assume that the memory is word addressable. The
number of memory references for accessing the
data in executing the program completely is

• (a)10
• (b)11
• (c)20
• (d)21

Consider the following program segment. Here R1,
R2 and R3 are the general purpose registers.

Instruction
Operation
Instruction
Size (no.
of words)
MOV
R1,(3000)
R1 ← M3000]
2
LOOP:
MOV
R2,(R3)
R2←M[R3]
1
ADD R2,R1
R2 ← R1 + R2
1
MOV
(R3),R2
M[R3] ←R2
1
INC R3
R3←R3+1
1
DEC R1
R1 ← R1 - 1
1
BNZLOOP
Branch on not zero
2
HALT
Stop
1

Assume that the content of memory location 3000 is
10 and the content of the register R3 is 2000. The
content of each of the memory locations from 2000 to
2010 is 100. The program is loaded from the memory
location 1000. All the numbers are in decimal.
Assume that the memory is word addressable. After
the execution of this program, the content of memory
location 2010 is:

• (a)100
• (b)101
• (c)102
• (d)110 Computer Organization and Architecture

Consider the following program segment. Here
R1, R2 and R3 are the general purpose registers.

Instruction
Operation
Instruction
Size
(no. of
words)

MOV
R1,(3000)
R1←M[3000]
2
LOOP:
MOV
R2,(R3)
R2 ← [R3]
1

ADD
R2,R1
R2 ← R1+R2
1

MOV
(R3),R2
M[R3] ←R2
1

INC R3
R3 ← R3+1
1

DEC R1
R1 ← R1-1
1

BNZ
LOOP
Branch on not
zero
2

HALT
Stop
1

Assume that the content of memory location 3000
is 10 and the content of the register R3 is 2000 . The
content of each of the memory locations from 2000
to 2010 is 100 . The program is loaded from the
memory location 1000. All the numbers are in
decimal.
Assume that the memory is byte addressable and
the word size is 32 bits. If an interrupt occurs during
the execution of the instruction "INC R3", what
return address will be pushed on to the stack?

• (a)1005
• (b)1020
• (c)1024
• (d)1040

In a simplified computer the instructions are:

OP Rj, Ri
Perform Rj OP Ri and store the result in
register Rj
OP m, Ri
Perform val OP Ri and store the result in
register Ri
val denotes the content of the memory
location m
MOV
m, Ri
Moves the content of memory location
m to register Ri
MOV
Ri, m
Moves the content of register Ri to
memory location m

The computer has only two registers, and OP is either
ADD or SUB. Consider the following basic block:

t1 = a + b

t2 = c + d

t3 = e - t2

t4 = t1 - t3
Assume that all operands are initially in memory. The
final value of the computation should be in memory.
What is the minimum number of MOV instructions in
the code generated for this basic block?

• (a)2
• (b)3
• (c)5
• (d)6

Data forwarding techniques can be used to speed up
the operation in the presence of data dependencies.
Consider the following replacements of LHS with
RHS:
(i)
R1 → Loc,
Loc → R2 ≡ R1 → R2,R1→Loc
(ii)
R1 → Loc,
Loc → R2 ≡ R1 → R2
(iii) R1 → Loc,
R2 → Loc ≡ R1 → Loc
(iv) R1 → Loc,
R2 → Loc ≡ R2 → Loc
In which of the following options will the result of
executing the RHS be the same as executing the
LHS irrespective of the instruction that follow ?
Computer Organization and Architecture

• (a)(i) and (iii)
• (b)(i) and (iv)
• (c)(ii) and (iii)
• (d)(ii) and (iv)

Following table indicates the latencies of
operations between the instruction producing the
result and instruction using the result.

Instruction producing
the result
Instruction using the
result
Latency
ALU Operation
ALU Operation
2
ALU Operation
Store
2
Load
ALU Operation
1
Load
Store
0

Consider the following code segment:
Load R1, Loc 1; Load R1 from memory location Loc1
Load R2, Loc 2; Load R2 from memory location Loc 2
Add R1, R2, R1; Add R1 and R2 and save result in R1
Dec R2; Decrement R2
Dec R1; Decrement R1
Mpy R1, R2, R3; Multiply R1 and R2 and save
result in R3
Store R3, Loc 3; Store R3 in memory location Loc 3

What is the number of cycles needed to execute
the above code segment assuming each instruction
takes one cycle to execute?

• (a)7
• (b)10
• (c)13
• (d)14

A CPU has 24-bit instructions. A program starts at
address 300 (in decimal). Which one of the
following is a legal program counter (all values in
decimal)?

• (a)400
• (b)500
• (c)600
• (d)

Which of the following statements about relative
addressing mode is FALSE?

• (a)It enables reduced instruction size
• (b)It allows indexing of array elements with same instruction
• (c)It enables easy relocation of data
• (d)It enables faster address calculations than absolute addressing

The memory locations 1000, 1001 and 1020 have
data values 18, 1 and 16 respectively before the
following program is executed.

MOVI
Rs, 1
Move immediate
LOAD
Rd, 1000(Rs)
Load from memory
ADDI
Rd, 1000
Add immediate
STOREI
0(Rd), 20
Store immediate

Which of the statements below is TRUE after the
program is executed?

• (a)Memory location 1000 has value 20
• (b)Memory location 1020 has value 20
• (c)Memory location 1021 has value 20
• (d)Memory location 1001 has value 20

Consider a three-word machine instruction:
ADD A [R0], @B
The first operand (destination) "A [R0]" uses
indexed addressing mode with R0 as the index
register.
The second operand (source) "@B" uses indirect
addressing mode.
A and B are memory addresses residing at the
second and the third words, respectively.
The first word of the instruction specifies the
opcode, the index register designation, and the
source and destination addressing modes.
Computer Organization and Architecture

During execution of the ADD instruction, the two
operands are added and stored in the destination
(first operand).
The number of memory cycles needed during the
execution cycle of the instruction is:

• (a)3
• (b)4
• (c)5
• (d)6

Match List-I with List-II and select the
correct answer using the codes given below
the lists:
List-I
List-II
A.[I] = B[J];
1. Indirect addressing
B. while(*A++);
2. Indexed addressing
C. int temp = *x;
3. Autoincrement
A B C

• (a)3 2 1
• (b)1 3 2
• (c)2 3 1
• (d)1 2 3

A partial data path of a processor is given in the
figure, where RA, RB, and RZ are 32-bit registers.
Which option(s) is/are CORRECT related to
arithmetic operations using the data path as shown?

• (a)The data path can implement arithmetic operations involving two registers.
• (b)The data path can implement arithmetic operations involving one register and one immediate value.
• (c)The data path can implement arithmetic operations involving two immediate values.
• (d)The data path can only implement arithmetic operations involving one register and one immediate value.

Consider the following data path diagram

Consider an instruction: R0 ← R1 + R2. The
following steps are used to execute it over the given
data path. Assume that the PC is incremented
appropriately. The subscripts r and w indicate read
and write operations, respectively.
1. R2r TEMP1r, ALUadd, TEMP2w
2. R1r TEMP1w,
3. PCr, MARw, MEMr
4. TEMP2r, R0w
5. MDRr, IRw
Which one of the following is the correct order of
execution of the above steps?

• (a)2,1,4,5,3
• (b)1,2,4,3,5
• (c)3,5,2,1,4
• (d)3,5,1,2,4

Consider the following processor design
characteristics:
I. Register-Io-register arithmetic operations only
II. Fixed-length instruction format
III. Hardwired control unit
Which of the characteristics above are used in the
design of a RISC processor?

• (a)I and II only
• (b)II and III only
• (c)I and III only
• (d)I, II and III

Consider the following sequence of micro
-
operations.
MBR ← PC
MAR ← X
PC ← Y
Memory ← MBR
Which one of the following is a possible operation
performed by this sequence?
Computer Organization and Architecture

• (a)Instruction fetch
• (b)Operand fetch
• (c)Conditional fetch
• (d)Initiation of interrupt service

Consider a CPU where all the instructions require
7 clock cycles to complete execution. There are 140
instructions in the instruction set. It is found that
125 control signals are needed to be generated by
the control unit. While designing the horizontal
micro-programmed control unit, single address
field format is used for branch control logic. What
is the minimum size of the control word and control
address register?

• (a)125, 7
• (b)125, 10
• (c)135, 9
• (d)135, 10

The following data path of a CPU

The ALU, the bus and all the registers in the data
path are of identical size. All operations including
incrementation of the PC and the GPRs are to be
carried out in the ALU. Two clock cycles are
needed for memory read operation—the first one
for loading addresses in the MAR and the next one
for loading data from the memory bus into the
MDR.
The instruction "add R0, R1" has the register
transfer interpretation
R0 ← R0 + R1.
The minimum number of cycles needed for
execution cycle of this instruction is

• (a)2
• (b)3
• (c)4
• (d)5

Consider the following data path of a CPU.

The ALU, the bus and all the registers in the data
path are of identical size. All operations including
incrementation of the PC and the GPRs are to be
carried out in the ALU. Two clock cycles are
needed for memory read operation - the first one
for loading address in the MAR and the next one
for loading data from the memory bus into the
MDR.
The instruction "call Rn, sub" is a two word
instruction. Assuming that PC is incremented
during the fetch cycle of the first word of the
instruction, its register transfer interpretation is
Rn ← PC + 1
PC ← M[PC]
The minimum number of CPU clock cycles needed
during the execution cycle of this instruction is:

• (a)2
• (b)3
• (c)4
• (d)5 Computer Organization and Architecture
• (a)S5 = T1 + I2 ⋅ T3 and

An instruction set of a processor has 125 signals
which can be divided into 5 groups of mutually
exclusive signals as follows:

Group 1: 20 signals,
Group 2: 70 signals,
Group 3: 2 signals,
Group 4: 10 signals,
Group 5: 23 signals.

How many bits of the control words can be saved
by using vertical microprogramming over
horizontal microprogramming?

• (a)0
• (b)103
• (c)22
• (d)55

A hardwired CPU uses 10 control
signals S1 to S10, in various time steps T1 to T5, to
implement 4 instructions I1 to I4 as shown below:

T1
T2
T3
T4
T5
I1
S1, S3, S5
S2, S4, S6
S1, S7
S10
S3, S8
I2
S1, S3, S5
S8, S9, S10
S5, S6S7
S6
S10
I3
S1, S3, S5
S7, S8, S10
S2, S6, S9
S10
S1, S3
I4
S1, S3, S5
S2, S6, S7
S5, S10
S6, S9
S10

Which of the following pairs of expressions
represent the circuit for generating control
signals S5 and S10 respectively?
((Ij + Ik)Tn indicates that the control signal
should be generated in time step Tn if the
instruction being executed is Ij or lk)
S10 = (I1 + I3) ⋅ T4 + (I2 + I4) ⋅ T5
(b)
S5 = T1 + (I2 + I4) ⋅ T3 and
S10 = (I1 + I3) ⋅ T4 + (I2 + I4) ⋅ T5
(c)
S5 = T1 + (I2 + I4) ⋅ T3 and
S10 = (I2 + I3 + I4) ⋅ T2 + (I1 + I3) ⋅ T4
+(I2 + I4) ⋅ T5
(d)
S5 = T1 + (I2 + I4) ⋅ T3 and
S10 =(I2 +I3). T2 +I4.T3 +(I1+I3).

S10 = (I2 + I3) ⋅ T2 + I4 ⋅ T3 + (I1

+I3 ) ⋅ T4 + (I2 + I4) ⋅ T5

The size of the physical address space of a
processor is 232 bytes. The capacity of a cache
memory unit is 223 bytes. The cache block size is
128 bytes. The cache memory unit can be built as
a direct mapped cache or as a K-way set-
associative cache, where K = 2L and L ∈ {1, 2, 3}.
Let the length of the TAG field be M bits for the
direct mapped cache, and N bits for the set-
associative cache.
Which one of the following options is true?

• (a)N = M + L
• (b)N = M - L
• (c)N = M + K
• (d)N = M – K

Consider a system with a processor and a 4 KB
direct mapped cache with block size of 16 bytes.
The system has a 16 MB physical memory. Four
words P, Q, R, and S are accessed by the
processor in the same order 10 times. That is,
there are a total of 40 memory references in the
sequence P, Q, R, S, P, Q, R, S,... Assume that the
cache memory is initially empty. The physical
addresses of the words are given below (1 word =
1 byte).
P: 0X845B32, Q: 0X845B26, R: 0X845B36,
S: 0X846B32
Which of the following statements is/are true?
Note: 1 K = 210 and 1M = 220

• (a)Every access to P results in a cache miss
• (b)Every access to R results in a cache hit
• (c)Every access to Q results in a cache miss
• (d)Except the first access to S, all subsequent accesses to S result in cache hits

Consider a system with 1 MB physical memory and
a word length of 1 byte. The system uses a direct
mapped cache, with block numbers starting from 0.
The word with physical address 0XA2C28 is
mapped to the cache block number (176)10. The
maximum possible size of the cache (in KB) for this
configuration is
. (answer in integer)
Note: 1K = 210 and 1M = 220

Given a computing system with two levels of cache
(L1 and L2) and a main memory. The first level (L1)
cache access time is 1 nanosecond (ns) and the "hit
rate" for L1 cache is 90% while the processor is
accessing the data from L1 cache. Whereas, for the
second level (L2) cache, the "hit rate" is 80% and the
"miss penalty" for transferring data from L2 cache to
L1 cache is 10 ns. The "miss penalty" for the data to
be transferred from main memory to L2 cache is 100
ns.
Then the average memory access time in this system
in nanoseconds is
. (rounded off to one
decimal place)

For a direct-mapped cache, 4 bits are used for the tag
field and 12 bits are used to index into a cache block.
The size of each cache block is one byte. Assume that
there is no other information stored for each cache
block.
Which ONE of the following is the CORRECT option
for the sizes of the main memory and the cache
memory
in
this
system
(byte
addressable),
respectively?

• (a)64 KB and 4 KB
• (b)128 KB and 16 KB
• (c)64 KB and 8 KB
• (d)128 KB and 6 KB Computer Organization and Architecture

A computer has a memory hierarchy consisting of
two-level cache (L1 and L2) and a main memory.
If the processor needs to access data from memory,
it first looks into L1 cache. If the data is not found
in L1 cache, it goes to L2 cache. If it fails to get the
data from L2 cache, it goes to main memory, where
the data is definitely available. Hit rates and access
times of various memory units are shown in the
figure. The average memory access time in
nanoseconds (ns) is
. (rounded off to two
decimal places)

Consider a memory system with 1M bytes of main
memory and 16K bytes of cache memory. Assume
that the processor generates a 20-bit memory
address, and the cache block size is 16 bytes. If the
cache uses direct mapping, how many bits will be
required to store all the tag values? [Assume
memory is byte addressable, 1K = 210, 1M = 220.]

• (a)6 × 210
• (b)8 × 210
• (c)212
• (d)214

A given program has 25% load/store instructions.
Suppose the ideal CPI (cycles per instruction)
without any memory stalls is 2. The program
exhibits 2% miss rate on instruction cache and 8%
miss rate on data cache. The miss penalty is 100
cycles. The speedup (rounded off to two decimal
places) achieved with a perfect cache (i.e., with NO
data or instruction cache misses) is

Consider
two
set-associative
cache
memory
architectures: WBC, which uses the write back
policy, and WTC, which uses the write through
policy. Both of them use the LRU (Least Recently
Used) block replacement policy. The cache memory
is connected to the main memory. Which of the
following statements is/are TRUE?

• (a)A read miss in WBC never evicts a dirty block
• (b)A read miss in WTC never triggers a write back operation of a cache block to main memory
• (c)A write hit in WBC can modify the value of the dirty bit of a cache block
• (d)A write miss in WTC always writes the victim cache block to main memory before loading the missed block to the cache

An 8-way set associative cache of size 64 KB (1 KB
= 1024 bytes) is used in a system with a 32-bit
address. The address is sub-divided into TAG,
INDEX, and BLOCK OFFSET.
The number of bits in the TAG is
.

Consider a system with a 2 KB direct-mapped data
cache with a block size of 64 bytes. The system has a
physical address space of 64 KB and a word length of
16 bits. During the execution of a program, four data
words P, Q, R, and S are accessed in that order 10
times (i.e., PQRS...). Hence, there are 40 accesses to
Computer Organization and Architecture

the data cache altogether. Assume that the data
cache is initially empty and no other data words are
accessed by the program. The addresses of the first
bytes of P, Q, R, and S are 0XA248, 0XC28A,
0XCA8A, and 0XA262, respectively. For the
execution of the above program, which of the
following statements is/are TRUE with respect to
the data cache?

• (a)Every access to S is a hit.
• (b)Once P is brought to the cache it is never evicted.
• (c)At the end of the execution-only R and S reside in the cache.
• (d)Every access to R evicts Q from the cache.

A cache memory that has a hit rate of 0.8 has an
access latency 10 ns and miss penalty 100 ns.
Optimization is done on the cache to reduce the
miss rate. However, the optimization results in an
increase of cache access latency to 15 ns, whereas
the miss penalty is not affected The minimum hit
rate (rounded off to two decimal places) needed
after the optimization such that it should not
increase the average memory access time
is
.

Let WB and WT be two set associative cache
organizations that use LRU algorithm for cache
block replacement. WB is a write back cache and
WT is a write through cache. Which of the
following statements is/are FALSE?

• (a)Each cache block in WB and WT has a dirty bit.
• (b)Every write hit in WB leads to a data transfer from cache to main memory.
• (c)Eviction of a block from WT will not lead to data transfer from cache to main memory.
• (d)A read miss in WB will never lead to eviction of a dirty block from WB.

Assume a two-level inclusive cache hierarchy, L1
and L2, where L2 is the larger of the two. Consider
the following statements.
S1: Read misses in a write through L1 cache do not
result in writebacks of dirty lines to the L2
S2: Write allocate policy must be used in
conjunction with write through caches and no-write
allocate policy is used with writeback caches.
Which of the following statements is correct?

• (a)S1 is true and S2 is false
• (b)S1 is false and S2 is true
• (c)S1 is true and S2 is true
• (d)S1 is false and S2 is false

Consider a set-associative cache of size 2KB
(1KB=210 bytes) with cache block size of 64 bytes.
Assume that the cache is byte-addressable and a 32 -
bit address is used for accessing the cache. If the
width of the tag field is 22 bits, the associativity of
the cache is
.

Consider a computer system with a byte-addressable
primary memory of size 232 bytes. Assume the
computer system has a direct-mapped cache of size
32 KB (1 KB = 210 bytes), and each cache block is of
size 64 bytes.
The size of the tag field is
bits.

A computer system with a word length of 32 bits has
a 16 MB byte- addressable main memory and a 64
KB, 4-way set associative cache memory with a
block size of 256 bytes. Consider the following four
physical addresses represented in hexadecimal
notation.
A1=0x42C8A4,
A2=0x546888,
A3=0x6A289C,
A4=0x5E4880
Which one of the following is TRUE?
Computer Organization and Architecture

• (a)A1 and A4 are mapped to different cache sets
• (b)A2 and A3 are mapped to the same cache set.
• (c)A3 and A4 are mapped to the same cache set.
• (d)A1 and A3 are mapped to the same cache set.

A direct mapped cache memory of 1 MB has a
block size of 256 bytes. The cache has an access
time of 3 ns and a hit rate of 94%. During a cache
miss, it takes 20 ns to bring the first word of a
block from the main memory, while each
subsequent word takes 5 ns. The word size is 64
bits. The average memory access time in ns (round
off to 1 decimal place) is
.

A certain processor deploys a single-level cache.
The cache block size is 8 words and the word size
is 4 bytes. The memory system uses a 60-MHz
clock. To service a cache-miss, the memory
controller first takes 1 cycle to accept the starting
address of the block, it then takes 3 cycles to fetch
all the eight words of the block, and finally
transmits the words of the requested block at the
rate of 1 word per cycle. The maximum bandwidth
for the memory system when the program running
on the processor issues a series of read operations
is
× 106 bytes/sec.

A certain processor uses a fully associative cache
of size 16 kB. The cache block size is 16 bytes.
Assume that the main memory is byte addressable
and uses a 32-bit address. How many bits are
required for the Tag and the Index fields
respectively in the addresses generated by the
processor?

• (a)24 bits and 0 bits
• (b)28 bits and 4 bits
• (c)24 bits and 4 bits
• (d)28 bits and 0 bits

The size of the physical address space of a processor
is 2P bytes. The word length is 2W bytes. The
capacity of cache memory is 2N bytes. The size of
each cache block is 2M words. For a K-way set-
associative cache memory, the length (in number of
bits) of the tag field is

• (a)P - N - log2K
• (b)P - N + log2K
• (c)P - N - M - W - log2K
• (d)P - N - M - W + log2K

Consider a machine with a byte addressable main
memory of 232 bytes divided into blocks of size 32
bytes. Assume that a direct mapped cache having
512 cache lines is used with this machine. The size
of the tag field in bits is
.

The read access times and the hit ratios for different
caches in a memory hierarchy are as given below.
Cache
Read access
time (in
nanoseconds)
Ht ratio
I-cache
2
0.8
D-cache
2
0.9
L2-cache
8
0.9
The read access time of main memory is 90
nanoseconds. Assume that the caches use the
referred word-first read policy and the write back
policy. Assume that all the caches are direct mapped
caches. Assume that the dirty bit is always 0 for all
the blocks in the caches. In execution of a program,
60% of memory reads are for instruction fetch and
40% are for memory operand fetch. The average
read access time in nanoseconds (up to 2 decimal
places) is
.
Computer Organization and Architecture

In a two-level cache system, the access times of L1
and L2 1 and 8 clock cycles, respectively. The
miss penalty from the L2 cache to main memory is
18 clock cycles. The miss rate of L1 cache is twice
that of L2. The average memory access
time(AMAT) of this cache system is 2 cycles. The
miss rates of L1 and L2 respectively are:

• (a)0.111 and 0.056
• (b)0.056 and 0.111
• (c)0.0892 and 0.1784
• (d)0.1784 and 0.0892

A cache memory unit with capacity of N words
and block size of B words is to be designed. If it is
designed as a direct mapped cache, the length of
the TAG field is 10 bits. If the cache unit is now
designed as a 16-way set-associative cache, the
length of the TAG field is
bits.

Consider a 2-way set associative cache with 256
blocks and use LRU replacement, initially the
cache is empty. Conflict misses are those misses
which occur due to the contention of multiple
blocks for the same cache set. Compulsory misses
occur due to first time access to the block. The
following sequence of accesses to memory blocks.

{0,128,256,128,0,128,256,128,1,129,257,129,1,12
9,257,129}

is repeated 10 times. The number of conflict
misses experienced by the cache is
.

Consider a two-level cache hierarchy with L1 and
L2 caches. An application incurs 1.4 memory
accesses per instruction on average. For this
application, the miss rate of L1 cache 0.1, the L2
cache experiences, on average, 7 misses per 1000
instructions. The miss rate of L2 expressed correct to
two decimal places is
.

A file system uses an in-memory cache to cache disk
blocks. The miss rate of the cache is shown in the
figure. The latency to read a block from the cache is
1 ms and to read a block from the disk is 10 ms.
Assume that the cost of checking whether a block
exists in the cache is negligible. Available cache
sizes are in multiples of 10 MB.

The smallest cache size required to ensure an
average read latency of less than 6 ms is

MB.

The width of the physical address on a machine is 40
bits. The width of the tag field in a 512KB 8-way set
associative cache is
bits.

Consider a machine with a byte addressable main
memory of 220 bytes, block size of 16 bytes and a
direct mapped cache having 212 cache lines. Let the
addresses of two consecutive bytes in main memory
be (E201F)16 and (E2020)16. What are the tag and
Computer Organization and Architecture

cache line address (in hex) for main memory
address (E201F)16?

• (a)E, 201
• (b)F, 201
• (c)E, E20
• (d)2, 01F

Assume that for a certain processor, a read request
takes 50 nanoseconds on a cache miss and 5
nanoseconds on a cache hit. Suppose while
running a program, it was observed that 80% of
the processor's read requests result in a cache hit.
The average read access time in nanoseconds is

.

The memory access time is 1 nanosecond for a
read operation with a hit in cache, 5 nanoseconds
for a read operation with a miss in cache, 2
nanoseconds for a write operation with a hit in
cache and 10 nanoseconds for a write operation
with a miss in cache. Execution of a sequence of
instructions involves 100 instruction fetch
operations, 60 memory operand read operations
and 40 memory operand write operations. The
cache hit-ratio is 0.9. The average memory access
time (in nanoseconds) in executing the sequence
of instructions is

.

If the associativity of a processor cache is doubled
while keeping the capacity and block size
unchanged, which one of the following is
guaranteed to be NOT affected?

• (a)Width of tag comparator
• (b)Width of set index decoder
• (c)Width of way selection multiplexor
• (d)Width of processor to main memory data bus

In designing a computer's cache system, the cache
block (or cache line) size is an important parameter.
Which one of the following statements is correct in
this context?

• (a)A smaller block size implies better spatial locality
• (b)A smaller block size implies a smaller cache tag and hence lower cache tag overhead
• (c)A smaller block size implies a larger cache tag and hence lower cache hit time
• (d)A smaller block size incurs a lower cache miss penalty

A 4-way set-associative cache memory unit with a
capacity of 16 KB is built using a block size of 8
words. The word length is 32 bits. The size of the
physical address space is 4 GB. The number of bits
for the TAG field is
.

Consider a main memory system that consists of 8
memory modules attached to the system bus, which
is one word wide. When a write request is made, the
bus is occupied for 100 nanoseconds (ns) by the
data, address, and control signals. During the same
100 ns, and for 500 ns thereafter, the addressed
memory module executes one cycle accepting and
storing the data. The (internal) operation of different
memory modules may overlap in time, but only one
request can be on the bus at any time. The maximum
number of stores (of one word each) that can be
initiated in 1 millisecond is
.

An access sequence of cache block addresses is of
length N and contains n unique block addresses. The
number of unique block addresses between two
consecutive accesses to the same block address is
bounded above K. What is the miss ratio if the
access sequence is passed through a cache of
associativity A≥k exercising least-recently-used
Computer Organization and Architecture

replacement policy?
The number of bits in the tag field of an address is

• (a)n/N
• (a)11
• (b)1/N
• (b)14
• (c)1/A
• (c)16
• (d)k/n
• (d)27

In a k-way set associative cache, the cache is
divided into v sets, each of which consists of k
lines. The lines of a set are placed in sequence one
after another. The lines in set s are sequenced
before the lines in set (s+1). The main memory
blocks are numbered 0 onwards. The main
memory block numbered j must be mapped to any
one of the cache lines from

• (a)(j mod v) *k to (j mod v) *k + (k-1)
• (b)(j mod v) to (j mod v) +(k-1)
• (c)(j mod k) to (j mod k) +(v-1)
• (d)(j mod k) *v to (j mod k) *v + (v-1)

A computer has a 256 -KByte, 4 -way set
associative, write back data cache with block size
of 32 Bytes. The processor sends 32 bit addresses
to the cache controller. Each cache tag directory
entry contains, in addition to address tag, 2 valid
bits, 1 modified bit and 1 replacement bit.
The size of the cache tag directory is:

• (a)160 Kbits
• (b)136 Kbits
• (c)40 Kbits
• (d)32 Kbits

A computer has a 256-KByte, 4-way set
associative, write back data cache with block size
of 32-Bytes. The processor sends 32-bit addresses
to the cache controller. Each cache tag directory
entry contains, in addition to address tag, 2 valid
bits, 1 modified bit and 1 replacement bit.

An 8KB direct mapped write-back cache is organized
as multiple blocks, each of size 32-bytes. The
processor generates 32-bit addresses. The cache
controller maintains the tag information for each
cache block consisting of the following.
1 Valid bit, 1 Modified bit as many bits as the
minimum needed to identify the memory block
mapped in the cache.
What is the total size of memory needed at the cache
controller to store metadata (tags) for the cache?

• (a)4864 bits
• (b)6144 bits
• (c)6656 bits
• (d)5376 bits

A computer system has an L1 cache, an L2 cache,
and a main memory unit connected as shown below.
The block size in L1 cache is 4 words. The block
size in L2 cache is 16 words. The memory access
times are 2 nanoseconds. 20 nanoseconds and 200
nanoseconds for L1 cache, L2 cache and main
memory unit respectively.

When there is a miss in both L1 cache and L2 cache,
first a block is transferred from main memory
to L2 cache, and then a block is transferred
from L2 cache to L1 cache. What is the total time
taken for these transfers?

• (a)222 nanoseconds
• (b)888 nanoseconds
• (c)902 nanoseconds
• (d)968 nanoseconds
• (a)n/N
• (b)1/N
• (c)1/A
• (d)k/n
• (a)11
• (b)14
• (c)16
• (d)27 Computer Organization and Architecture

A computer system has an L1 cache, an L2 cache,
and a main memory unit connected as shown
below. The block size in L1 cache is 4 words. The
block size in L2 cache is 16 words. The memory
access times are 2 nanoseconds. 20 nanoseconds
and 200 nanoseconds for L1 cache, L2 cache and
main memory unit respectively.

When there is a miss in L1 cache and a hit in L2
cache, a block is transferred from L2 cache to L1
cache. What is the time taken for this transfer?

• (a)2 nanoseconds
• (b)20 nanoseconds
• (c)22 nanoseconds
• (d)88 nanoseconds

Consider a 4-way set associative cache (initially
empty) with total 16 cache blocks. The main
memory consists of 256 blocks and the request
for memory blocks are in the following order:
0,255,1,4,3,8,133,159,216,129,63,8,48,32,73,92,155.
Which one of the following memory block will
NOT be in cache if LRU replacement policy is
used?

• (a)3
• (b)8
• (c)129
• (d)216

For inclusion to hold between two cache levels L1
and L2 in a multilevel cache hierarchy, which of
the following are necessary?
1. L1 must be a write-through cache
2. L2 must be a write-through cache
3. The associativity of L2 must be greater than that
of L1
4. The L2 cache must be at least as large as the L1
cache

• (a)4 only
• (b)1 and 2 only
• (c)1, 2 and 4 only
• (d)1, 2, 3 and 4

Consider a machine with a 2 -way set associative data
cache of size 64 Kbytes and block size 16 bytes. The
cache is managed using 32 bit virtual addresses and
the page size is 4 Kbytes . A program to be run on
this machine begins as follows:

double ARR[1024][1024];
int i, j;

for(i = 0; i < 1024; i++)
for(j= 0; j < 1024; j++)
ARR[i][j] = 0.0;

The size of double is 8Bytes. Array ARR is located
in memory starting at the beginning of virtual page
0 xFF000 and stored in row major order. The
cache is initially empty and no pre-fetching is
done. The only data memory references made by
the program are those to array ARR.
The total size of the tags in the cache directory is:

• (a)32 Kbits
• (b)34 Kbits
• (c)64 Kbits
• (d)68 Kbits Computer Organization and Architecture

Consider a machine with a 2 -way set associative
data cache of size 64 Kbytes and block size 16
bytes. The cache is managed using 32 bit virtual
addresses and the page size is 4 Kbytes . A
program to be run on this machine begins as
follows:
double ARR[1024][1024];
int i, j;

for(i = 0; i < 1024; i++)
for(j= 0; j < 1024; j++)
ARR[i][j] = 0.0;

The size of double is 8Bytes. Array ARR is
located in memory starting at the beginning of
virtual page 0 xFF000 and stored in row major
order. The cache is initially empty and no pre-
fetching is done. The only data memory
references made by the program are those to
array ARR.
Which of the following array elements have the
same cache index as ARR[0][0] ?

• (a)ARR[0][4]
• (b)ARR[4][0]
• (c)ARR[0][5]
• (d)ARR[5][0]

Consider a machine with a 2 -way set associative
data cache of size 64 Kbytes and block size 16
bytes. The cache is managed using 32 bit virtual
addresses and the page size is 4 Kbytes . A
program to be run on this machine begins as
follows:
double ARR[1024][1024];
int i, j;
for(i = 0; i < 1024; i++)
for( = 0; j < 1024; j++)

The size of double is 8 bytes. Array ARR is
located in memory starting at the beginning of
virtual page 0 xFF000 and stored in row major
order. The cache is initially empty and no pre-
fetching is done. The only data memory references
made by the program are those to array ARR.
The cache hit ratio for this initialization loop is:

• (a)0%
• (b)25%
• (c)50%
• (d)75%

Consider a computer with a 4-ways set-associative
mapped cache of the following characteristics: a
total of 1 MB of main memory, a word size of 1
byte, a block size of 128 words and a cache size of 8
KB.
The number of bits in the TAG, SET and WORD
fields, respectively are:

• (a)7, 6, 7
• (b)8, 5, 7
• (c)8, 6, 6
• (d)9, 4, 7

Consider a computer with a 4-ways set-associative
mapped cache of the following characteristics: a
total of 1 MB of main memory, a word size of 1
byte, a block size of 128 words and a cache size of 8
KB. While accessing the memory location 0C795H
by the CPU, the contents of the TAG field of the
corresponding cache line is:

• (a)000011000
• (b)110001111
• (c)00011000
• (d)110010101 ARR[i][j] = 0.0; Computer Organization and Architecture

Consider a machine with a byte addressable main
memory of 216 bytes. Assume that a direct
mapped data cache consisting of 32 lines of 64
bytes each is used in the system. A 50 × 50 two-
dimensional array of bytes is stored in the main
memory starting from memory location 1100 H .
Assume that the data cache is initially empty. The
complete array is accessed twice. Assume that the
contents of the data cache do not change in
between the two accesses.
Which of the following lines of the data cache will
be replaced by new blocks in accessing the array
for the second time?

• (a)line 4 to line 11
• (b)line 4 to line 12
• (c)line 0 to line 7
• (d)line 0 to line 8

Consider a 4-way set associative cache consisting
of 128 lines with a line size of 64 words. The CPU
generates a 20-bit address of a word in main
memory. The numbers of bits in the TAG, SET,
and WORD fields are respectively:

• (a)9, 6, 5
• (b)7, 7, 6
• (c)7, 5, 8
• (d)9, 5, 6

Consider a machine with a byte addressable main
memory of 216 bytes. Assume that a direct mapped
data cache consisting of 32 lines of 64 bytes each
is used in the system. A 50 × 50 two-dimensional
array of 1 byte is stored in the main memory
starting from memory location 1100H. The data
cache is initially empty.
The complete array is accessed twice. Assume that
the contents of the data cache do not change in
between the two accesses.
How many data cache misses will occur in total?

• (a)48
• (b)50
• (c)56
• (d)59

A CPU has a cache with block size 64 bytes. The
main memory has k banks, each bank being c bytes
wide. Consecutive c-byte chunks are mapped on
consecutive banks, with wrap-around All the k
banks can be accessed in parallel, but two accesses
to the same bank must be serialized. A cache block
access may involve multiple iterations of parallel
bank accesses depending on the amount of data
obtained by accessing all the k banks in parallel.
Each iteration requires decoding the bank numbers
to be accessed in parallel and this takes k/2 ns. The
latency of one bank access is 80 ns.
If c = 2 and k = 24, then the latency of retrieving a
cache block starting at address zero from main
memory is:

• (a)92 ns
• (b)104 ns
• (c)172 ns
• (d)184 ns

Consider two cache organizations: The first one is a
32 KB 2-way set associative with 32-byte block size.
The second one is of the same size but directly
mapped. The size of an address is 32 bits in both
cases. A 2-to-1 multiplexer has latency of 0.6 ns
while a k-bit comparator has a latency of k/10 ns.
The hit latency of the set associative organization is
h1 while that of the direct mapped one is h2.
The value of h1 is :

• (a)2.4 ns
• (b)2.3 ns
• (c)1.8 ns
• (d)1.7 ns Computer Organization and Architecture

Consider two cache organizations: The first one is
a 32 KB 2-way set associative with 32-byte block
size. The second one is of the same size but
directly mapped. The size of an address is 32 bits
in both cases. A 2-to-1 multiplexer has latency of
0.6 ns while a k-bit comparator has a latency of
k/10 ns. The hit latency of the set associative
organization is h1 while that of the direct mapped
one is h2.
The value of h2 is :

• (a)2.4 ns
• (b)2.3 ns
• (c)1.8 ns
• (d)1.7 ns

A CPU has a 32KB direct mapped cache with
128 byte-block size.Suppose A is two
dimensional array of size 512 × 512 with
elements that occupy 8 -bytes each.Consider
the following two C code segments, P1 and P2
.
P1:
for(i=0; i<512 ; i++)

{
for (j=0;j<512; j++)
}
x +=A[i][j]
}

P2:

for(i=0; i<512 ; i++)

{

for ( j=0:j<512:j++ )
{
x +=A[j][i]
1
P1 and P2 are executed independently with the
same initial state,namely,the array A is not in
the cache and i, j , x are in registers.Let the
number of cache misses experienced by P1 be M1
and that for P2 be M2 .
The value of the ratio M1 :
M2

• (a)0
• (b)1 16
• (c)1 8
• (d)16

A CPU has a 32KB direct mapped cache with 128
byte-block size.Suppose A is two dimensional
array of size 512 × 512 with elements that occupy
8 -bytes each.Consider the following two C
code segments, P1 and P2 .
P1:
for(i=0; i<512 ; i++)

{
for (j=0;j<512; j++)
}
x +=A[i][j]
}
P2:
for(i=0; i<512 ; i++)

{

for ( j=0:j<512:j++ )
{
x +=A[j][i]
1
Computer Organization and Architecture

P1 and P2 are executed independently with the
same initial state,namely,the array A is not in
the cache and i, j , x are in registers.Let the
number of cache misses experienced by P1 be
M1 and that for P2 be M2 .
The value of M1:

• (a)0
• (b)2048
• (c)16384
• (d)262144

Consider a direct mapped cache of size 32 KB
with block size 32 bytes. The CPU generates 32-
bit addresses. The number of bits needed for cache
indexing and the number of tag bits are
respectively:

• (a)10, 17
• (b)10, 22
• (c)15, 17
• (d)5, 17

Consider a 2-way set associative cache memory
with 4 sets and total 8 cache blocks (0–7) and
main memory with 128 blocks (0–127). Which
memory blocks will be present in the cache after
the following sequence of memory block
references if LRU policy is used for cache block
replacement? If initially the cache did not have
any memory block from the current job?

0 5 3 9 7 0 16 55

• (a)0 3 5 7 16 55
• (b)0 3 5 7 9 16 55
• (c)0 5 7 9 16 55
• (d)3 5 7 9 16 55

A computer system has a level-1 instruction cache
(I-cache), a level-1 data cache (D-cache) and a level-
2 cache (L2-cache) with the following
specifications:

Cache
Capacity
Mapping
method
Block
size
I-cache
4K words
Direct mapping
4 Words
D-cache
4K words
2-way set-
associative
mapping
4 Words
L2-cache
64K
words
4-way set-
associative
mapping
16 Words

Capacity Mapping method Block size I-cache 4K
words Direct mapping 4 Words D-cache 4K words
2-way set-associative mapping 4 Words L2-cache
64K words 4-way set-associative mapping 16 Words

The length of the physical address of a word in the
main memory is 30 bits. The capacity of the tag
memory in the I-cache, D-cache and L2-cache is,
respectively,

• (a)1K × 18-bit, 1K × 19-bit, 4K × 16-bit
• (b)1K × 16-bit, 1K × 19-bit, 4K × 18-bit
• (c)1K × 16-bit, 512 × 18-bit, 1K × 16-bit
• (d)1K × 18-bit, 512 × 18-bit, 1K × 18-bit Computer Organization and Architecture

Consider the following two statements about
interrupt handling mechanisms in a CPU,
S1: In non-vectored interrupt mechanism, it
usually takes more time to start the Interrupt
Service Routine (ISR) when compared to that in a
vectored interrupt mechanism.
S2: In daisy-chain interrupt mechanism, the CPU
polls all the input devices individually to
determine the source of the interrupt.
Which one of the following options is correct with
respect to SI and S2?

• (a)Both S1 and S2 are true
• (b)Both S1 and S2 are false
• (c)S1 is true and S2 is false
• (d)S1 is false and S2 is true .

Suppose a program is running on a non-pipelined
single processor computer system. The computer
is connected to an external device that can
interrupt the processor asynchronously. The
processor needs to execute the interrupt service
routine (ISR) to serve this interrupt. The following
steps (not necessarily in order) are taken by the
processor when the interrupt arrives:
(i) The processor saves the content of the program
counter.
(ii) The program counter is loaded with the start
address of the ISR.
(iii) The processor finishes the present instruction.
Which ONE of the following is the CORRECT
sequence of steps?

• (a)(iii), (i), (ii)
• (b)(i), (iii), (ii)
• (c)(i), (ii), (iii)
• (d)(iii), (ii), (i)

Consider a computer with a 4 MHz processor. Its
DMA controller can transfer 8 bytes in 1 cycle from
a device to main memory through cycle stealing at
regular intervals. Which one of the following is the
data transfer rate (in bits per second) of the DMA
controller if 1% of the processor cycles are used for
DMA?

• (a)2,56,000
• (b)3,200
• (c)25,60,000 (d 32,000

Which one of the following statements is FALSE?

• (a)In the cycle stealing mode of DMA, one word of data is transferred between an I/O device and main memory in a stolen cycle
• (b)For bulk data transfer, the burst mode of DMA has a higher throughput than the cycle stealing mode
• (c)Programmed I/O mechanism has a better CPU utilization than the interrupt driven I/O mechanism
• (d)The CPU can start executing an interrupt service routine faster with vectored interrupts than with non-vectored interrupts

A keyboard connected to a computer is used at a rate
of 1 keystroke per second The computer system
polls the keyboard every 10 ms to check for a
keystroke and consumes 100 μs (micro seconds) for
each poll. If it is determined after polling that a key
has been pressed, the system consumes an additional
Computer Organization and Architecture

200 μs to process the keystroke. Let T1 denote the
fraction of a second spent in polling and
processing a keystroke.
In an alternative implementation, the system uses
interrupts instead of polling. An interrupt is raised
for every keystroke. It takes a total of 1 ms for
servicing an interrupt and processing a keystroke.
Let T2 denote the fraction of a second spent in
servicing the interrupt and processing a keystroke.
The ratio T1 / T2 is
. (Rounded off to
one decimal place)

Which one of the following facilitates transfer of
bulk data from hard disk to main memory with the
highest throughput?

• (a)DMA based I/O transfer
• (b)Interrupt driven I/O transfer
• (c)Polling based I/O transfer
• (d)Programmed I/O transfer

Consider a computer system with DMA support.
The DMA module is transferring one 8-bit
character in one CPU cycle from a device to
memory through cycle stealing at regular
intervals. Consider a 2 MHz processor. If 0.5%
processor cycles are used for DMA, the data
transfer rate of the device is
bits per
second.

Consider the following statements.
I. Daisy chaining is used to assign priorities in
attending interrupts.
II. When a device raises a vectored interrupt, the
CPU does polling to identify the source of the
interrupt.
III. In polling, the CPU periodically checks the
status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA
controller can be bus masters at the same time.
Which of the above statements is/are TRUE?

• (a)I and IV only
• (b)I and II only
• (c)III only
• (d)I and III only

The size of the data count register of a DMA controller
is 16 bits.The processor needs to transfer a file of
29,154 kilobytes from disk to main memory.The
memory is byte addressable
The minimum number of times the DMA controller
needs to get the control of the system bus from the
processor to transfer the file from the disk to main
memory is

Consider a typical disk that rotates at 15000
rotations per minute (RPM) and has a transfer rate
of 50 × 106 bytes /sec. If the average seek time of
the disk is twice the average rotational delay and
the controller's transfer time is 10 times the disk
transfer time, the average time (in milliseconds) to
read or write a 512-byte sector of the disk is .

Consider a disk pack with a seek time of 4
milliseconds and rotational speed of 10000 rotations
per minute (RPM). It has 600 sectors per track and
each sector can store 512 bytes of data. Consider a file
stored in the disk. The file contains 2000 sectors
Assume that every sector access necessitates a seek,
And the average rotational latency for accessing each
sector is half of the time for one complete rotation.
The total time (in milliseconds) needed to read the
entire file is

Consider a hard disk with 16 recording surfaces (0-
15) having 16384 cylinders (0-16383) and each
Computer Organization and Architecture

cylinder contains 64 sectors (0-63). Data storage
capacity in each sector is 512 bytes. Data are
organized cylinder-wise and addressing format is
<cylinder no., surface no., sector no>. A file of
size 42797 KB is stored in the disk and the starting
disk location of the file is < 1200, 9, 40>. What is
the cylinder number of the last sector of the file, if
it is stored in a contiguous manner?

• (a)1281
• (b)1282
• (c)1283
• (d)1284

An application loads 100 libraries at start-up.
Loading each library requires exactly one disk
access. The seek time of the disk to a random
location is given as 10 ms . Rotational speed of disk
is 6000 rpm . If all 100 libraries are loaded from
random locations on the disk, how long does it take
to load all libraries? (The time to transfer data from
the disk block once the head has been positioned at
the start of the block may be neglected.)

• (a)0.50 s
• (b)1.50 s
• (c)1.25 s
• (d)1.00 s

On a non-pipelined sequential processor, a
program segment, which is the part of the interrupt
service routine, is given to transfer 500 bytes from
an I/O device to memory.
Intialize the address register
Intilatize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address
register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is
equivalent to a machine instruction which takes one
clock cycle to execute if it is a non-load/store
instruction. The load-store instructions take two
clock cycles to execute.
The designer of the system also has an alternate
approach of using the DMA controller to implement
the same transfer. The DMA controller requires 20
clock cycles for initialization and other overheads.
Each DMA transfer cycle takes two clock cycles to
transfer one byte of data from the device to the
memory.
What is the approximate speed up when the DMA
controller based design is used in a place of the
interrupt driven program based input-output?

• (a)3.4
• (b)4.4
• (c)5.1
• (d)6.7

A CPU generally handles an interrupt by executing
an interrupt service routine

• (a)as soon as an interrupt is raised
• (b)by checking the interrupt register at the end of fetch cycle
• (c)by checking the interrupt register after finishing the execution of the current instruction
• (d)by checking the interrupt register at fixed time intervals

A device with data transfer rate 10 KB/sec is
connected to a CPU. Data is transferred byte-wise.
Let the interrupt overhead be 4 μ sec The byte
transfer time between the device interface register
and CPU or memory is negligible.
What is the minimum performance gain of operating
the device under interrupt mode over operating it
under program controlled mode?
Computer Organization and Architecture

• (a)15
• (b)25
• (c)35
• (d)45

Consider the disk drive with the following
specifications: 16 surfaces, 512 tracks/surface, 512
sectors/track, 1 KB/sector, rotation speed 3000
rpm. The disk is operated in cycle stealing mode
whereby whenever one byte is ready it is sent to
memory, similarly, for writing, the disk interface
reads a 4-byte word from the memory in each
DMA cycle. Memory cycle time is 40 nsec The
maximum percentage of time that the CPU gets
blocked during DMA operation is

• (a)10
• (b)25
• (c)40
• (d)50