PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2017 Shift 1

61 Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially the cache is empty. Conflict misses are those misses which occur due 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,129,257,129) is repeated 10 times. The number of conflict misses experienced by the cache is __________.

A miss is not considered a conflict miss if the block is accessed for the first time.
1st round: (2+2) misses
2nd round: (4+4) misses
∴Total = 4 + (8 × 9) = 76 conflict misses

62 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 loads and store instructions can have memory operands and
(ii) arithmetic instructions can have only register or immediate operands.
The value of X is _____.

Note – Numerical Type question

The given expression is (a-1) * ((( b + c ) / 3 ) + d)
The optimal generated code is:
Load R₁, b R₁ ⟵ b
Load R₂, c R₂ ⟵ c
ADD R₁, R₂ R₁ ⟵ R₁ + R₂
Div R₁, 3 R₁ ⟵ R₁/3
Load R₂, d R₂ ⟵ d
Add R₁, R₂ R₁ ⟵ R₁ + R₂
Load R₂, a R₂ ⟵ a
Sub R₂, 1 R₂ ⟵ R₂ - 1
Mul R₂, R₁ R2 ⟵ R₂ * R₁
Hence minimum 2 registers required.

63 The values of parameters for the Stop-and – Wait ARQ protocol are as given below:
Bit rate of the transmission channel = 1 Mbps
Propagation delay from sender to receiver = 0.75 ms
Time to process a frame = 0.25 ms
Number of bytes in the information frame = 1980
Number of bytes in the acknowledge frame = 20
Number of overhead bytes in the information frame = 20
Assume that there are no transmission errors. Then the transmission efficiency (expressed in percentage) of the Stop-and – Wait ARQ protocol for the above parameters is _____.

Note – Numerical Type question

Given Data:
B = 1Mbps
T_proc = 0.25ms
T_p = 0.75ms
L = 1980 Bytes
L_OH = 20 Bytes
L_A = 20 Bytes
Efficiency (η) = ?

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

Note – Numerical Type question

where T is the required length of TAG field
∴ T = 14

65 Consider a database that has the relation schema CR (StudentName, CourseName). An instance of the schema CR is as given below.

CR
Student Name	Course Name
SA	CA
SA	CB
SA	CC
SB	CB
SB	CC
SC	CA
SC	CB
SC	CC
SD	CA
SD	CB
SD	CC
SD	CD
SE	CD
SE	CA
SE	CB
SF	CA
SF	CB
SF	CC

The following query is made on the database.

T1 ← π_CourseName(σ_{StudentName=’SA’}(CR))

T2 ← CR ÷ T1
The number of rows in T2 is ________.

Note – Numerical Type question

Explanation: Result of T1:
CA
CB
CC

Result of T2 = CR/T1
SA
SC
SD
SF
Total = 4
Therefore, option C is correct

Alternate Solution :
The output of query T1 will be the courses enrolled by student SA i.e CA, CB, CC
The output of query T2 will be the names of the students who enroll all the courses that are the output of query T1 (division operator) i.e CA, CB, CC
From the table we can see that SA, SC, SD, SF have enrolled all the courses so the output of T2 will have 4 row