PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

56 Consider a paging system that uses a 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns. TLB lookup takes 20 ns. Each page transfer to/from the disk takes 5000 ns. Assume that the TLB hit ratio is 95%, page fault rate is 10%. Assume that for 20% of the total page faults, a dirty page has to be written back to disk before required page is read in from disk. TLB update time is negligible. The average memory access time is ns (round off to 1 decimal places) is ______.

Note – Numerical Type question

Main memory access time, T_m = 100 ns
TLB lookup, T_TLB = 20ns
Page transfer time, T_PT = 5000 ns
TLB hit ratio, x = 0.95 (95%)
page fault rate, p = 0.10 (10%)
Gate2020 cs

We know,
EMAT for multilevel paging,
EMAT = x (T_c + T_m) + (1 – x) (T_c + (n + 1) T_m)
EMAT, when there is a page fault, S → is service time
EMAT = (1 – P) T_m + Ps
Here, we are using TLB, and page fault occurs whenever there is a miss in TLB, So the required EMAT is ,
EMAT = x(T_tlb + T_m) + (1 – x) [(1 – P) (T_tlb + T_m + T_m) + p(% dirty (T_tlb + T_m + 2T_PT) + % clean (T_tlb + T_m + T_PT)
∴ EMAT = 0.95 (20 + 100) + 0.05 (0.9 (20 + 100 + 100) + 0.1 (0.2 (20 + 100 + 2(5000)) + 0.8 (20 + 100 + 5000))
= 154.5 ns

57 Consider a graph G = (V, E), where V = {v₁, v₂, …, v₁₀₀}, E = {(v_i, v_j)|1≤i≤j≤100}, and weight of the edge (v_i, v_j) is |i – j|. The weight of the minimum spanning tree of G is _____.

Note – Numerical Type question

If we consider a small graph with 5 vertices, then the minimum spanning tree will have a weight 4.
So, for n-vertices, MST weight would be (n – 1)
As n = 100 (no. of vertices), So, minimum spanning tree weight = (100 – 1) = 99

58 For n > 2, let a ∈ {0, 1}ⁿ be a non-zero vector. Suppose that x is chosen uniformly at random form (0,1)n. Then, the probability that Gate2020 cs

is an number is _______ .

Note – Numerical Type question

Let n = 3
0 ϵ < 0,1]³
Gate2020 cs

x = 0 or 1
Gate2020 cs

= x₁ = x₃ (∵ a₁ = 1, a₂= 0, a₃ = 1)
= 0 or 1 or 1 or 2.
Gate2020 cs

= x₃ (∵ a₁ = a₂ = 0)
= 0 or 1
Gate2020 cs

Total number of cases = 2 × 3 + 4 × 3 = 18
Now odd number of cases = 9
P = 9/18 = 0.5

59 Consider the array representation of a binary min-heap containing 1023 element. The minimum number of comparisons required to find the maximum in the heap is ______.

Note – Numerical Type question

Min-heap contains 1023 elements.
Min-heap means, parent should be minimum or equal to it’s children so, max children could be either left or right one.
Following this logic, maximum can be definitely at leaf nodes.
Gate2020 cs

No. of elements in leaf = n/2 = 1023/2 = 512
To find maximum among 512 elements, no. of comparisons needed is 511.

60 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 pipeline processor at 2 GHz. In a given program, assume that 30% are memory instructions, 60% are ALU instructions and the rest are branch instruction. 5% of the memory instructions cause stalls of 50 clock cycles each due to cache misses 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-pipeline processor (round off to 2 decimal places) is ______.

Note – Numerical Type question

Non-pipeline
Clock frequency = 2.5 GHz.
Cycle time = 1/2.5 GHz = 0.4ns
Given, CPI = 5
So, ET_non-pipe = CPI × Cycle time
= 5 × 0.4 ns = 2 ns
Pipeline:
Clock frequency = 24 GHz
Cycle time = 1/2 GHz = 0.5ns
Gate2020 cs

∴ Number of stalls/instruction = 0.3 × 0.05 × 50 + 0.1 * 0.5 × 2
= 0.85
Avg. instruction ETpipe = (1 + No. of stall instruction) * cycle time
= (1 + 0.85) × 0.5 ns = 0.925 ns
Gate2020 cs

i = 0	i = 1	i = 2
ex = 3 x 3	ex = 9 x 3	tot = t * t *ex
= 9	= 81	= 1 * 81 = 81

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2020

Follow Us :