0
Alien head

Test 1 - Computer Organization & Architecture | Computer Science(CS)

Description: GATE Previous year Topic Wise Questions and Answers | Computer Organization & Architecture
Number of Questions: 20
Created by:
Tags: Computer Organization and Architecture GATE CS
Attempted 0/20 Correct 0 Score 0

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

  1. O (1)

  2. O (log n)

  3. O (n)

  4. O (n2)


Correct Option: C
Explanation:

The no. of gates used in n bit array multiplier (n x n) is 2n - 1. So. if every single gate takes unit delay, then total delay 0 (2n -1) = 0 (n) It is of linear order

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$\dfrac{k}{2}$ns .latency of one bank access is 80 ns. If c = 2 and k = 24, the latency of retrieving cache block starting at address zero from main memory is:

  1. 92 ns

  2. 104 ns

  3. 172 ns

  4. 184 ns


Correct Option: D
Explanation:

For a pipelined CPU with a single ALU, consider the following situations
I. The j + 1-st instruction uses the result of the j-th instruction as an operand
II. The execution of a conditional jump instruction
III. The j-th and j + 1-st instructions require the ALU at the same time

Which of the above can cause a hazard?

  1. I and II only

  2. II and III only

  3. III only

  4. All the three


Correct Option: D
Explanation:

Case 1 is here of data dependency, this can't be safe with single ALU so read after write.
Case 2 Conditional jumps are always hazardous they create conditional dependency in pipeline
Case 3 this is write after read problem or concurrency dependency so hazardous
All the three are hazardous.

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a 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:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

  4. 1.7 ns


Correct Option: A
Explanation:

A CPU has a five-stage pipeline and runs at 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 9 10 instructions out of which 20% are conditional branches. If each instruction takes one cycle to complete on average, the total execution time of the program is:

  1. 1.0 second

  2. 1.2 seconds

  3. 1.4 seconds

  4. 1.6 seconds


Correct Option: B
Explanation:


Consider the ALU shown below

GATE 2003 Paper
If the operands are in 2's complement representation, which of the following operations can be performed by suitably setting the control lines K and C0 only (+ and - denote addition and subtraction respectively)?

  1. A + B, and A - B, but not A + 1

  2. A + B, and A + 1, but not A - B

  3. A + B, but not A - B or A + 1

  4. A + B, and A - B, and A + 1


Correct Option: D
Explanation:

Consider a new instruction named branch-on-bit-set (mnemonic bbs). The instruction “bbs reg, pos, label” jumps to label if bit in position pos of register operand reg is one. A register is 32 bits wide and the bits are numbered 0 to 31, bit in position 0 being the least significant. Consider the following emulation of this instruction on a processor that does not have bbs implemented.
temp$\leftarrow$reg & mask
Branch to label if temp is non-zero.
The variable temp is a temporary register. For correct emulation, the variable mask must be generated by

  1. mask $\leftarrow$ 0 ×l << pos

  2. musk $\leftarrow$ 0 × ffffffff >> pos

  3. mask $\leftarrow$pos

  4. masdk $\leftarrow$0×f


Correct Option: A
Explanation:

Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a 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:

  1. 2.4 ns

  2. 2.3 ns

  3. 1.8 ns

  4. 1.7 ns


Correct Option: B
Explanation:

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 number of bits in the TAG, LINE and WORD fields are respectively:

  1. 9, 6, 5

  2. 7, 7, 6

  3. 7, 5, 8

  4. 9, 5, 6


Correct Option: D
Explanation:

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a 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];
}
}
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 $\dfrac{M_1}{M_2}$

  1. 0

  2. $\dfrac{1}{16}$

  3. $\dfrac{1}{8}$

  4. 16


Correct Option: B
Explanation:


Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:

  1. 256 Mbyte, 19 bits

  2. 256 Mbyte, 28 bits

  3. 512 Mbyte, 20 bits

  4. 64 Gbyte, 28 bits


Correct Option: A
Explanation:

Consider the following assembly language program for a hypothetical processor
A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, #0 ; B $\leftarrow$ 0
MOV C, #8 ; C $\leftarrow$ 8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C $\leftarrow$ C - 1
RRC A, #1 ; right rotate A through carry by one bit. Thus:
; if the initial values of A and the carry flag are a7… a0 and
; instruction will be c0a7…a1 and a0 respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B $\leftarrow$ B + 1
X: If the initial value of register A is A0, the value of register B after the program execution will be

  1. the number of 0 bits in A0

  2. the number of 1 bits in A0

  3. A0

  4. 8


Correct Option: B
Explanation:

Here value of B is incremented by 1 only if carry flag is 1, carry is filled using right rotation, so B will store the no. of 1s in A0.

Consider the following assembly language program for a hypothetical processor
A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments.
MOV B, #0 ; B $\leftarrow$0
MOV C, #8 ; C$\leftarrow$8
Z: CMP C, #0 ; Compare C with 0
JZX ; Jump to X if zero flag is set
SUB C, #1 ; C $\leftarrow$ C -1
RRC A, #1 ; right rotate A through carry by one bit. Thus:
; if the initial values of A and the carry flag are a7… a0 and
; instruction will be c0a7…a1 and a0 respectively
JCY ; jump to Y if carry flag is set
JMP Z ; jump to Z
Y: ADD B, #1 ; B $\leftarrow$ B + 1
X:

Which of the following instructions when inserted at location X will ensure that the value of register A after program execution is the same as its initial value?

  1. RRC A, #1

  2. NOP ; no operation

  3. LRC A, #1 ; left rotate A through carry flag by one bit

  4. ADD A, #1


Correct Option: A
Explanation:

In the end of program execution to check whether both initial and final value of register A is A0, we need to right rotate register A through carry by one bit.

A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a 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];
}
}
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 1 M is:

  1. 0

  2. 2048

  3. 16384

  4. 262144


Correct Option: C
Explanation:

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 1100H. 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?

  1. line 4 to line 11

  2. line 4 to line 12

  3. line 0 to line 7

  4. line 0 to line 8


Correct Option: C
Explanation:

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?
ADD R2, R1, R0 R2 $\rightarrow$ R1 + R0
MUL R4, R3, R2 R4$\rightarrow$ R3 * R2
SUB R6, R5, R4 R6 $\rightarrow$R5 - R4

  1. 7

  2. 8

  3. 10

  4. 14


Correct Option: B
Explanation:


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 1100H. 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.

How many data cache misses will occur in total?

  1. 48

  2. 50

  3. 56

  4. 59


Correct Option: C
Explanation:

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

InstructionR OperationR Instruction size (no. of words)R
MOV R1, (3000)R R1 _ m[3000]R 2R
LOOP: MOV R2, (R3)R R2 _ M[R3]R 1R
ADD R2, R1R R2 _ R1 + R2R 1R
MOV (R3), R2R M[R3] _ R2R 1R
INC R3R R3 _ R3 + 1R 1R
DEC R1R R1 _ R1 - 1R 1R
BNZ LOOPR Branch on not zeroR 2R
HALTR StopR 1R

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:

  1. 10

  2. 11

  3. 20

  4. 21


Correct Option: D
Explanation:

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

InstructionR OperationR Instruction size (no. of words)R
MOV R1, (3000)R R1 _ m[3000]R 2R
LOOP: MOV R2, (R3)R R2 _ M[R3]R 1R
ADD R2, R1R R2 _ R1 + R2R 1R
MOV (R3), R2R M[R3] _ R2R 1R
INC R3R R3 _ R3 + 1R 1R
DEC R1R R1 _ R1 - 1R 1R
BNZ LOOPR Branch on not zeroR 2R
HALTR StopR 1R

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:

  1. 100

  2. 101

  3. 102

  4. 110


Correct Option: A
Explanation:

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

InstructionR OperationR Instruction size (no. of words)R
MOV R1, (3000)R R1 _ m[3000]R 2R
LOOP: MOV R2, (R3)R R2 _ M[R3]R 1R
ADD R2, R1R R2 _ R1 + R2R 1R
MOV (R3), R2R M[R3] _ R2R 1R
INC R3R R3 _ R3 + 1R 1R
DEC R1R R1 _ R1 - 1R 1R
BNZ LOOPR Branch on not zeroR 2R
HALTR StopR 1R

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?

  1. 1005

  2. 1020

  3. 1024

  4. 1040


Correct Option: C
Explanation:


+ View questions