Let the symbols “⊕” represents XOR and “⊙” represents XNOR. Which of the following is a valid identity? [MSQ]
x ⊕ y = (x⊙y)'
(x ⊕ y) ⊕ z = x ⊙ (y ⊙ z)
x ⊕ y = x’ + y’, if x+y = 1
x ⊕ y = (x’⊙y)'
Correct Answer
Option 1,2,3
Solution
1. XOR is equivalent to XNOR if the number of input variables is odd.
2. XOR is a complement of XNOR if the number of input variables is even.
3. x+y = 1 => (x’y’) = 0.
x⊙y= xy + x’y’= xy.
If x⊙y= xy, then x⊕y = (xy)’ = x’+y’.
4. x ⊕ y = (x’⊙y)' is not valid because x ⊕ y = (x’⊙y) or x ⊕ y = (x⊙y’)
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
Which of the following is different from others?
Ring Counter
Johnson’s Counter
Shift Counter
Ripple Counter
Correct Answer
Option 4
Solution
A shift counter is a synchronous counter that consists of clocked flip-flops arranged as a shift register. Data is propagated between the flip-flops (left to right or right to left) by the application of a clock. Ring counters and Jounhson’s counters are shift counters.
On the other hand, ripple counters are not shift counters.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
How many 4-to-16 line decoders with an enable input are needed to construct a 8-to-256 line decoder without using any other logic gates?
17
16
32
33
Correct Answer
Option 1
Solution
The 8-to-256 line decoder has 256 output lines.
The 4-to-16 line decoder has 16 lines.
So, the level 1 needs 256/16 = 16 decoders of size 4-to-16.
Level 2 needs 16/16= 1 decoder of size 4-to-16.
Total= 16 in level 1 + 1 in level 2 = 16 + 1= 17.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let two n-bit positive numbers A and B represented in 2’s complement form are added. After adding A and B, the carry in and carry out of the MSB bits have different values. Let “OF” represent the overflow flag. Then, OF is updated with ____
1
Correct Answer
Option 1
Solution
Overflow occurs when
Both have same sign
and
Carry_in ≠ Carry_out
In the given problem, both the numbers are positive and Carry_in ≠ Carry_out. So, there is an overflow. Hence, OF is set to 1.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
A set S of Boolean connectives is functionally complete if all Boolean functions can be synthesized using the set S. Which of the following sets of connectives is functionally complete? [MSQ]
{EX-OR}
{AND, NOT}
{Implication, NOT}
ALL of the above
Correct Answer
Option 2,3
Solution
The sets {AND, NOT}, and {OR, NOT} are functionally complete.
Implication: f(P,Q) = P’+Q.
Use NOT to complement the input P’.
f(P’,Q) = (P’)’ + Q = P+Q ← OR
The set {Implication, NOT} is equivalent to {OR, NOT}. Hence {Implication, NOT} is also functionally complete.
EX-OR is not functionally complete.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.00
A processor that has flags Carry C, Overflow V and Sign S as part of its program status word (PSW), performs addition of the following two 2's complement numbers 01001101 and 11101001. After the execution of this addition operation, the status of the carry, overflow and sign flags, respectively will be_______
C=1, V=0, and S=0
C=1, V=1, and S=0
C=1, V=1, and S=1
C=1, V=0, and S=1
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let F(X,Y,Z)= X’Y + Z’. Which of the following statements is true?
F is functionally complete
F is not functionally but partially functionally complete
F is neither functionally complete nor partially functionally complete
None
Correct Answer
Option 1
Solution
F(X,Y,Z)= X’Y + Z’
F(X,X,X)= X’X +X’ = 0 + X’ = X’ ← NOT
F(X’,X,Z’)= (X’)’ X + (Z’)’ = X + Z ← OR
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Let f1(x,y,z)= Σ(1,2,6,7) + Φ(3,4) and f2(x,y,z)= Σ(0,1,2,4) + Φ(3,5).
How many functions does the combined function f1+f2 represent?
4
8
2
1
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
[MSQ]
Kn = 2^m, and Km = 1
Km =2^n, and Kn =1
Km =2^n, and Kn =2^m
Km =2^m, and Kn =2^n
Correct Answer
Option 1,2
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Let (142)x + (151)x = (323)x . If (142)x+(93)10=(Y)10, then Y=___
172
145
162
163
Correct Answer
Option 1
Solution
(142)x + (151)x = (323)x
x^2 + 4x + 2 + x^2 + 5x + 1 = 3x^2 + 2x + 3
x^2 - 7x=0
x=7
(142)x = (142)7= (79)10.
(79)10 + (93)10 = (172)10.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Which of the following circuits is not identical with other circuits?
None
Correct Answer
Option 4
Solution
All the circuits are identical.
The state Q1 is updated when Q0 changes from 0 to 1.
Q1n = ; (Q0: 0 → 1 or : 1 → 0)
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider a ROM of size 1K x 16. If two decoders of size nx2^n are used for address decoding, then what is the possible value of n?
9
10
8
11
Correct Answer
Option 1
Solution
A ROM of size 1Kx16 has 1K words, each of size 16 bits.
The ROM has 1K= 1024 addresses, one for each word. So, log 1024 = 10 address lines are needed to specify 2^10 words.
A decoder is also known as address decoder. Two decoders are used to implement the ROM.
Each decoder decodes 1024/2 = 512 addresses.
So, the size of the decoders is 9x2^9.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following circuit with n-bit binary inputs A= An-1An-2 ...A0 and B= Bn-1Bn-2 ...B0 .
The circuit performs A+1 whenever___?
C0=1 and B=0.
C0=1 and B=1
C0=0 and B=0
C0=0 and B=1
Correct Answer
Option 1
Solution
When C0=1 and B=0, the output of XNOR gates is all zeros.
So, the circuit performs (A+B) +C0 = (A+0)+1= A+1.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Two numbers are chosen independently and uniformly at random from the set {-4,-3,-2,-1,0,1, 2,3}. The probability (rounded off to 3 decimal places) that their 3-bit 2’s complement binary representations have the different most significant bit is ______.
1/2
1/4
1/3
1
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Data transmitted on a link uses the following 2D parity scheme for error detection:
2
3
1
4
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
S1=B and S2=
S1= and S2= B
S1= B and S2= A
S1= and S2=
Correct Answer
Option 1
Solution
f(A,B)= = + A B
If S1=B, then output MUX2 is .
Output of MUX1 is B.
The inputs to MUX3 are and B.
If S2 = , then f= B + = A B + .
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Let f(A,B,C,D)= (A B+)(C+D). The minimum number of NOR gates required to implement the function f is___
7
6
8
9
Correct Answer
Option 1
Solution
NOR is an OR operation followed by NOT i.e OR-NOT.
NOT-AND is equivalent to NOR.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider the following statements:
S1: Horizontal microprogramming does not require use of signal decoders
S2: Horizontal microprogramming results in larger sized microinstructions than vertical microprogramming
S3: Vertical microprogramming uses one bit for each control signal
Choose the correct option from below.
Only S1 is true
Only S1 & S2 are true
All of S1, S2 & S3 are true
All of S1, S2 & S3 are false
Correct Answer
Option 2
Solution
S1: Horizontal microprogramming does not require use of signal decoders because it uses one bit for each control signal and there is no signal encoding in horizontal microprogramming. So S1 is True.
S2: Horizontal microprogramming results in larger sized microinstructions than vertical microprogramming as there is no signal encoding in horizontal microprogramming whereas in vertical microprogramming signal encoding is there. So S2 is true.
S3: Vertical microprogramming doesn’t use one bit for each control signal. So S3 is false.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
A hypothetical control unit supports 5 groups of mutually exclusive control signals. The
number of bits that can be saved using vertical approach compared to horizontal are
Groups
G1
G2
G3
G4
G5
#Control Signals
3
7
10
25
3
12
22
32
42
Correct Answer
Option 3
Solution
In horizontal microprogramming we use one bit for each control signal.
So the no. of bits required for the control signal in horizontal case = 3+7+10+25+3 = 48
But in vertical case we can represent the encoded version of the control signals:
So the no. of bits required for the control signal in vertical case = ceil(log 3)+ ceil(log 7)+ ceil(log 10) + ceil(log 25)+ ceil(log 3) = 2+3+4+5+2 = 16
No. of bits saved = 48 - 16 = 32
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
How many memory modules of size 1M*8 are required to construct a memory module of size 8M * 16 are ?
12
8
32
16
Correct Answer
Option 4
Solution
Number of modules required=Target capacity/given capacity
=(8M*16)/(1M*8)
=16 modules are required.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider the following statements
S1: In 2’s complement sum carry flag and overflow are not the same
S2: In 2’s complement sum if the sum of two negative numbers yields a positive result, the sum has overflowed
Select the correct option:
Only S1 is true
Only S2 is true
Both S1 and S2 are true
Both S1 and S2 are false
Correct Answer
Option 2
Solution
In unsigned numbers, carry out is equivalent to overflow. But in two's complement, carry out tells nothing about overflow. So S1 is false.
Following are the rules for detecting overflow in a two's complement sum:
>>If the sum of two positive numbers yields a negative result, the sum has overflowed.
>>If the sum of two negative numbers yields a positive result, the sum has overflowed.
Otherwise, the sum has not overflowed.
Based on this S2 is true.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
A device has been used in burst mode of DMA. A file of size 1KB has to be transferred and the word size is 2 bytes long. The memory cycle time is 40 ms and the CPU is idle for 10% of its time. What is the data transfer rate of the device in bytes/sec?
6.48
5.56
8.34
10.52
Correct Answer
Option 2
Solution
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider a hard disk with 16 recording surfaces (0-15) having 8192 cylinders (0-8191) where each track within the cylinder has 128 sectors (0-127). Data storage capacity in each sector is 1KB. Data are organized cylinder-wise and the addressing format is <cylinder no., surface no., sector no.>. A file of size 32768 KB is stored in the disk and the starting disk location of the file is <984, 10, 20>. What is the cylinder number of the last sector of the file, if it is stored in a contiguous manner?
1000
1100
1200
1300
Correct Answer
Option 1
Solution
Each sector is 1KB in size.
Number of sectors required for 32768 KB = 32768KB / 1KB = 32768
One cylinder has 16*128 = 2048 sectors .
For 32768 sectors , cylinders required are = 32768/ 2048 = 16
The starting cylinder number is 984. The last sector will be on 984+16 = 1000 cylinder.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The main memory of a computer has 800 blocks while the cache has 40 blocks. If it is a 4-way set associative cache then block number 653 of main memory maps to set X. What is the value of X?
1
3
2
4
Correct Answer
Option 2
Solution
There are 40 blocks in the cache. It is a 4-way set associative cache, so there are 4 blocks within each set.
Number of sets =40/4=10
The main memory block number 653 gets mapped to the set number given by 653 mod 10 = 3
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
Consider execution of 100 instructions on a 4 stage pipeline. Let P be the probability of an instruction being a branch. The value of P ()such that speed up with the pipeline over non-pipelined execution is at least 3 is __________. Assume each stage takes 1 cycle to perform its task and the branch is predicted on the 3rd stage of the pipeline.
0.166
0.133
0.122
0.144
Correct Answer
Option 1
Solution
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
In absolute addressing mode what is mentioned in place of the operand within the instruction ?
The value of the operand itself
Memory address where the operand is stored
Memory address where the effective address of the operand is stored
An offset value to be added to PC
Correct Answer
Option 2
Solution
Direct addressing mode is also called absolute addressing mode. In direct addressing the memory address where the operand is stored is given within the instruction.
Difficulty Level: 1
Positive Marks: 1.00
Negative Marks: 0.33
The access time of cache memory is 50ns and that of main memory is 500ns. The cache has a hit ratio of 0.9 for read operations and 0.85 for write operations respectively and write back policy is used. What is the average memory access time(in ns) if there are 70% of read operations and the remaining are write operations?
150.8
120.4
107.5
90.3
Correct Answer
Option 3
Solution
For read operation:
For read operation nothing is mentioned about hierarchical or simultaneous access. So by default we consider it as hierarchical memory.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider a 2-way set associative cache with 8 blocks. If the memory block requests are accessed in the following order 9, 4, 2, 0, 6, 12, 2, 6, 9, 1, 5, 8, 0, 4 what are the total number of conflict misses when LRU replacement algorithm is used?
1
2
3
4
Correct Answer
Option 1
Solution
There are 8 blocks and it is a 2-way set associative cache, so there are 8/2 = 4 sets in the cache. We can see the mapping as shown below:
Whenever a block is accessed the first time and it results in a miss then it is called compulsory miss. Using this definition from the mapping shown in the picture the accesses of 12, 8, 5 are all compulsory misses only as they are accessed the first time. The second time accesses of 2,6 are not resulting in miss. Only the second time accesses of 0, 4 are resulting in a miss.
We need to check whether the second accesses of 0, 4 are conflict miss or not.
By the definition of conflict miss when the second access of a block results in a miss then we assume the cache is fully associative with LRU replacement and in the fully associative scenario if the second time access of the given block is not a miss but in the present set associative mapping it is resulting in miss..then we call it conflict miss.
When the second access of a block is a miss in the set associative cache, then by assuming fully associative cache with LRU replacement..if the second access is a miss in the fully associative scenario also..then we call the miss in the actual set associative scenario as capacity miss.
When we assume the fully associative cache with LRU replacement we get the below mapping.
We can see in this the second access of block 0 is not a miss.. But in the original 2-way set associative case it is a miss.. So the second access to block 0 is a conflict miss.
The second access to block 4 is a miss in the fully associative scenario also. So the second access to block 4 in the original 2-way set associative cache is a capacity miss.
So, there is only one conflict miss.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider a 2-way set associative cache with 8 blocks with LRU replacement algorithm. If the memory block requests are accessed in the following order 9, 4, 2, 0, 6, 12, 2, 6, 9, 1, 5, 8, 0, 4. If the number of compulsory misses are x and the number of capacity misses are y, then what is the value of x+2y?
10
11
12
13
Correct Answer
Option 2
Solution
There are 8 blocks and it is a 2-way set associative cache, so there are 8/2 = 4 sets in the cache. We can see the mapping as shown below:
Whenever a block is accessed the first time and it results in a miss then it is called compulsory miss. There are a total of 9 unique block accesses, all of them are compulsory misses. So, x = 9.
The second time accesses of 2,6 are not resulting in miss. Only the second time accesses of 0, 4 are resulting in a miss.
We need to check whether the second accesses of 0, 4 are capacity miss or not.
By the definition of conflict miss when the second access of a block results in a miss then we assume the cache is fully associative with LRU replacement and in the fully associative scenario if the second time access of the given block is not a miss but in the present set associative mapping it is resulting in miss..then we call it conflict miss.
When the second access of a block is a miss in the set associative cache, then by assuming fully associative cache with LRU replacement..if the second access is a miss in the fully associative scenario also..then we call the miss in the actual set associative scenario as capacity miss.
When we assume the fully associative cache with LRU replacement we get the below mapping. We can see in this the second access of block 0 is not a miss.. But in the original 2-way set associative case it is a miss.. So the second access to block 0 is a conflict miss.
The second access to block 4 is a miss in the fully associative scenario also. So the second access to block 4 in the original 2-way set associative cache is a capacity miss.
So, there is only one capacity miss. So, y = 1.
The given expression x+2y = 9 + 2*1 = 9+2 = 11.
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider a pipeline x with 5 stages having delays: 4ns, 3ns, 5ns, 2ns and 9ns. An alternative pipeline y is designed from x by dividing the last stage into three substages each with the delay of 3ns. In the pipelines x and y the memory reference instructions are not overlapped so the penalty of memory reference instructions in the pipeline x is 4 cycles and in the pipeline y the penalty is 6 cycles. If the program contains 20% of instructions which are memory based instructions, the ratio of speedup of the pipeline x over non-pipelined execution to the speedup of the pipeline y over non-pipelined execution is_______
0.547
0.258
0.679
0.823
Correct Answer
Option 3
Solution
For pipeline x:
The execution time in the non-pipelined case: 4ns+3ns+5ns+2ns+9ns = 23ns
In the case of pipelined execution we need to calculate the updated Clocks per instruction(CPI), for pipeline x the updated CPI = 1+ stall frequency * number of stalls = 1+0.2*4 = 1.8
The clock cycle time in pipeline x = max(4ns, 3ns, 5ns, 2ns, 9ns) = 9ns
Execution time for one instruction in pipeline x = CPI*clock cycle time = 1.8 * 9 = 16.2ns
The speedup of pipeline x = Time without pipeline / Time with pipeline = 23ns / 16.2ns = 1.42
For pipeline y:
It is given that the last stage is divided into 3 substages each of equal delay 3ns.
So, the stages in pipeline y with delays are : 4ns, 3ns, 5ns, 2ns, 3ns, 3ns, 3ns
The execution time in the non-pipelined case: 4ns+ 3ns+5ns+2ns+ 3ns+ 3ns+ 3ns = 23ns
The updated CPI = 1 + stall frequency * number of stalls = 1+ 0.2*6 = 2.2
The clock cycle time in pipeline y = max(4ns, 3ns, 5ns, 2ns, 3ns, 3ns, 3ns) = 5ns
Execution time for one instruction in pipeline y = CPI * clock cycle time = 2.2*5 = 11ns
Speedup of pipeline y = Time without pipeline / Time with pipeline = 23ns / 11ns = 2.09
We are asked for the ratio of speedup of pipeline x to speedup of pipeline y,
The required ratio = 1.42/2.09 = 0.679
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
Consider a k-way set associative cache with n blocks. Each block has 32 words and the main memory has 1M blocks. If the tag field is 16 bits long and the TAG directory size is 2KB, what are the values of k and n respectively?
64, 1024
32, 512
16, 256
8, 256
Correct Answer
Option 1
Solution
TAG directory size is given as 2KB.
Tag field size is given as 16 bits.
We can write the TAG directory size = tag field size * number of lines in the cache
2KB = 16bits * n
2KB = 2 bytes * n
n = 2KB / 2bytes = 1K
So, there are 1024 blocks within the cache.
Each block size = 32 words = 2^5 words
It is given that the main memory has 1M blocks, main memory size in words = 1M*32
= 2^20 * 2^5 = 2^25
The physical address is 25 bits long.
We know, in a set associative cache the physical address is divided into three fields as (TAG, SET, OFFSET).
Since the block size is 32 words, OFFSET = 5
It is given in the question TAG bits are = 16
From this we can write the SET = 25 - 16 - 5 = 25 - 21 = 4
Number of sets in the cache = 2^4 = 16
In a k-way set associative cache there are k blocks within each set.
We can write the number of sets in a k-way set associative cache
= number of blocks in the cache / k
16 = 1024 / k
k = 1024/16 = 64
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.66
The stage delays in a 5-stage pipeline are 200, 500, 300, 150 and 400 nanoseconds. The second stage (with delay 500 nanoseconds) is replaced with a functionally equivalent design involving two stages with respective delays 450 and 350 nanoseconds. The throughput increase of the pipeline is ________ percent (upto 2 decimal points).
((11.00,11.11))
Correct Answer
Option 1
Solution
In a pipelined processor the throughput is 1/clock cycle time.
Cycle time = max of all stage delays.
In the first case max stage delay = 500.
So throughput = 1/500 initially.
After replacing this stage with two stages of delays 450, 350... the cycle time = maximum stage delay = 450.
So the new throughput = 1/450.
The new throughput > old throughput.
And the increase in throughput = 1/450 - 1/500.
We calculate the percentage increase in throughput w.r.t initial throughput, so the % increase in throughput
= (1/450 - 1/500) / (1/500) * 100
= ((500 / 450) - 1) * 100
= ((10/9) -1) * 100
= 11.11%
Difficulty Level: 1
Positive Marks: 2.00
Negative Marks: 0.00
Consider a processor with 100 registers and an instruction set of size 20. Each instruction has five distinct fields, namely, opcode, two source register identifiers, one destination register r identifier, and a 10-bit immediate value. Each instruction must be stored in memory in a byte-aligned fashion. If a program has 120 instructions, the amount of memory (in bytes) consumed by the program text is _______
600
Correct Answer
Option 1
Solution
One instruction is divided into five parts,
(i) The opcode- As we have instruction set of size 20, an instruction opcode can be identified by 5 bits, as 2^4 < 20 < 2^5 and we cannot go any less.
(ii) & (iii) Two source register identifiers- As there are total 100 registers, each register can be identified by 7 bits. As they are two we need 7 bits + 7 bits.
iv) One destination register identifier- Again it will need 7 bits.
[MSQ]
and S2= 
; (Q0: 0 → 1 or 
: 1 → 0)
= 
B + 
