xxx | GATE 2017 Solved Paper CS: Set – 1

Question Number: 50 Question Type: NAT In a 2-way set associative cache, a block is placed in the
Instruction execution in a processor is divided into 5 stages, location,
Instruction Fetch (IF), Instruction Decode (ID), Operand Block number % No. of sets in cache.
Fetch (OF), Execute (EX), and Write Back (WB). These set 0
0 % 128 = 0  → compulsory miss.
stages take 5, 4, 20, 10, and 3 nanoseconds (ns) respec-
tive. A pipelined implement action of the processor requires set 0
128 % 128 = 0  → compulsory miss.
buffering between each pair of consecutive stages with a set 0
256 % 128 = 0  → compulsory miss (1st time access)
delay of 2 ns. Two pipelined implementations of the proces-
sor are contemplated: set 0
128 % 128 = 0  → hit.
(i) A navie pipeline implementation (NP) with 5 stages set 0
0 % 128 = 0  → replace block 256, conflict miss.
and
(ii) An efficient pipeline (EP) where the OF stage is divided set 0
128 % 128 = 0  → hit.
into stages OF1 and OF2 with execution times of 12 ns set 0
256 % 128 = 0  → replace block 0, conflict miss.
and 8 ns respectively.
set 0
The speedup (correct to two decimal places) achieved by EP 128 % 128 = 0  → hit.
over NP in executing 20 independent instructions with no set 1
1 % 128 = 1 → compulsory miss.
hazards is .
set 1
129 % 128 = 1 → compulsory miss.
Solution: 5-stage pipeline: set 1
257 % 128 = 1 → compulsory miss (1st time access)
Cycle time = 20 + 2 set 1
129 % 128 = 1 → hit.
Execution time for 20 instructions = [5 + (20 − 1)] 22
set 1
1 % 128 = 1 → replace block 257, conflict miss.
6-stage pipeline:
set 1
Cycle time = 12 + 2 = 14 129 % 128 = 1 → hit.
set 1
Execution time for 20 instructions = [6 + (20 − 1)] 14 257 % 128 = 1 → replace block 1, conflict miss.
5 + (20 −1) 22 129 % 128 = 1 hit.
Speed up of EP over NP =  
 6 + (20 −1) 14 ∴ For 1st access, number of conflict misses = 4.
 
= 1.51 The contents of cache before starting 2nd time access is
Hence, the correct answer is (1.51).
256
......
Question Number: 51 Question Type: NAT set 0
128
Consider a 2-way set associative cache with 256 blocks and
257
......
uses LRU replacement. Initially the cache is empty. Conflict set 1
misses are those misses which occur due to contention of 129
multiple blocks for the same cache set. Compulsory misses
occur due to first time access to the block. The following
set 0
sequence of accesses to memory blocks 0 % 128 = 0  → conflict miss, replace block 256.
(0, 128, 256, 128, 0, 128, 256, 128, 1, 129, 257, 129, 1, 129, set 0
128 % 128 = 0  → Hit.
257, 129) set 0
256 % 128 = 0  → conflict miss, replace block 0.
is repeated 10 times. The number of conflict misses experi-
set 0
enced by the cache is . 128 % 128 = 0  → Hit.
set 0
0 % 128 = 0  → conflict miss, replace block 256.
Solution: Cache has 256 blocks and is organized in a 2-way
set associative manner. set 0
128 % 128 = 0  → Hit.
∴ The cache has 256 = 128 sets. set 0
256 % 128 = 0  → conflict miss, replace block 0.
2 set 0
128 % 128 = 0  → Hit.
set 0
Similarly for next 8 accesses, we will get 4 conflict misses.
set 0
∴ Number of conflict misses for second access = 8.
Now, the cache state is same as before accessing the se-
set 127 quence for the second time.
 GATE 2017 Solved Paper CS: Set – 1 | xxxi

So, for remaining accesses also there will be 8 conflict Solution:

misses.
a b c d e f g h
∴ Total number of conflict misses to access the sequence
for 10 times = 4 + 9 × 8 = 76.
Hence, the correct answer is (76).
Question Number: 52 Question Type: NAT
∗
Consider the expression (a—1) (((b + c)/3) + d)). Let X
be the minimum number of registers required by an optimal
code generation (without any register spill) algorithm for
a load/store architecture, in which (i) only load and store s t
instruction can have memory operands and (ii) arithmetic
instructions can have only register or immediate operands. strlen (t) = 5
strlen (s) = 3
The value of X is .
strlen( ) function return an unsigned value, computation
Solution: Consider the expression among unsigned variables will result in unsigned value i.e.,
positive value.
(a – 1) * ((b + c) / 3) + d)
strlen(s) − strlen(t)

Consider 2 registers R1 and R2. ⇓
R1 = b (3 − 5)
R2 = c ⇓
| −2 | > 0 ⇒ 2 > 0
R1 = R1 + R2
R1 = R1/3 as condition is true, it stores strlen(s) into variable len.
It prints 3.
R2 = d
Hence, the correct answer is (3).
R1 = R1 + R2
R2 = a Question Number: 54 Question Type: NAT
R2 = R2 – 1 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
R1 + R1 × R2
mapped cache, the length of the TAG field is 10 bits. If
Only 2 registers are required the cache unit is now designed as a 16-way set-associative
cache, the length of the TAG filed is _________ bits.
Hence, the correct answer is (2).
Solution: Direct mapped cache:
Question Number: 53 Question Type: NAT
n
Consider the following C program.
Tag Line word
# include <<stdio.h>
10 l b
# include <<string.h>
void printlength (char *s, char *t) { Where, block size B = 2b
unsigned int c = 0;
int len = ((strlen(s) − strlen (t)) > Number of Lines = 2l
c) ? strlen (s) : strlen (t); 16-way set associative cache:
printf (“%d\n”, len); n
}
void main ( ) { Tag Set word
char *x = “abc”; t l-4 b
char *y = “defgh”; l
printlength (x, y); 2
Number of sets = = 2l−4
} 16
10 + l + b = t + l – 4 + b
Recall that strlen is defined in string.h as returning a value
t = 14.
of type size_t, which is an unsigned int. the output of the
program is _________. ∴ Required tag field is 14-bits.
Hence, the correct answer is (14).