List of top Computer Organization and Architecture Questions asked in GATE CS

A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)

A computer system supports a logical address space of \( 2^{32} \) bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a \( b \)-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size. The value of \( b \) is ___________ . (Answer in integer)

Consider a demand paging system with three frames, and the following page reference string: \[ 1\ 2\ 3\ 4\ 5\ 4\ 1\ 6\ 4\ 5\ 1\ 3\ 2. \] The contents of the frames are as follows initially and after each reference (from left to right): 

The *-marked references cause page replacements. Which one or more of the following could be the page replacement policy/policies in use?

Refer to the given 3-address code sequence. This code sequence is split into basic blocks. The number of basic blocks is __________. (Answer in integer)
1001: i = 1
1002: j = 1
1003: t1 = 10i
1004: t2 = t1+j
1005: t3 = 8t2
1006: t4 = t3-88
1007: a[t4] = 0.0
1008: j = j+1
1009: if j <= 10 goto 1003
1010: i = i+1
1011: if i <= 10 goto 1002
1012: i = 1
1013: t5 = i-1
1014: t6 = 88t5
1015: a[t6] = 1.0
1016: i = i+1
1017: if i <= 10 goto 1013

A computer has a memory hierarchy consisting of two-level cache (L1 and L2) and a main memory. If the processor needs to access data from memory, it first looks into L1 cache. If the data is not found in L1 cache, it goes to L2 cache. If it fails to get the data from L2 cache, it goes to main memory, where the data is definitely available. Hit rates and access times of various memory units are shown in the figure. The average memory access time in nanoseconds (ns) is __________. (rounded off to two decimal places) 

Consider a memory system with 1M bytes of main memory and 16K bytes of cache memory. Assume that the processor generates a 20-bit memory address, and the cache block size is 16 bytes. If the cache uses direct mapping, how many bits will be required to store all the tag values? [Assume memory is byte addressable, 1K = \(2^{10}\), 1M = \(2^{20}\).]
In optimal page replacement algorithm, information about all future page references is available to the operating system (OS). A modification of the optimal page replacement algorithm is as follows: The OS correctly predicts only up to next 4 page references (including the current page) at the time of allocating a frame to a page. A process accesses the pages in the following order of page numbers: 1, 3, 2, 4, 2, 3, 1, 2, 4, 3, 1, 4. If the system has three memory frames that are initially empty, the number of page faults that will occur during execution of the process is \_\_\_\_\_\_\_\_. (Answer in integer)

Consider the following operations on an initially empty stack: 
Push 10 
Push 20 
Pop 
Push 30 
Pop 
Push 40 

What is the final content of the stack?

Which of the following is true about the binary search algorithm when applied to a sorted array?

Given a pipeline with 5 stages, the delay for each stage is as follows:

\[ \begin{array}{|c|c|} \hline \textbf{Stage} & \textbf{Delay (ns)} \\ \hline 1 & 250 \\ 2 & 150 \\ 3 & 100 \\ 4 & 200 \\ 5 & 50 \\ \hline \end{array} \]

The buffer delay is 10 ns. Find the time for \( n = 1000 \) instructions.

In an IPv4 packet, if \( X \) is written in the protocol field, which of the following is not a valid protocol \( X \)?
What is included in the Instruction Set Architecture (ISA)?
Let \(Z_n\) be the group of integers \(\{0, 1, 2, \dots, n - 1\}\) with addition modulo \(n\) as the group operation. The number of elements in the group \(Z_2 \times Z_3 \times Z_4\) that are their own inverses is ............
A non-pipelined instruction execution unit operating at 2 GHz takes an average of 6 cycles to execute an instruction of a program \(P\). The unit is then redesigned to operate on a 5-stage pipeline at 2 GHz. Assume that the ideal throughput of the pipelined unit is 1 instruction per cycle. In the execution of program \(P\), 20\% instructions incur an average of 2 cycles stall due to data hazards and 20\% instructions incur an average of 3 cycles stall due to control hazards. The speedup (rounded off to one decimal place) obtained by the pipelined design over the non-pipelined design is ............
A processor uses a 32-bit instruction format and supports byte-addressable memory access. The ISA of the processor has 150 distinct instructions. The instructions are equally divided into two types, namely R-type and I-type, whose formats are shown below. R-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|c|} \hline OPCODE & UNUSED & DST Register & SRC Register1 & SRC Register2
\hline \end{tabular} \end{center} \vspace{0.5cm} I-type Instruction Format: \begin{center} \setlength{\tabcolsep}{15pt} % Adjust column spacing \renewcommand{\arraystretch}{1.5} % Adjust row spacing \begin{tabular}{|c|c|c|c|} \hline OPCODE & DST Register & SRC Register & \# Immediate Value/Address
\hline \end{tabular} \end{center} In the OPCODE, 1 bit is used to distinguish between I-type and R-type instructions, and the remaining bits indicate the operation. The processor has 50 architectural registers, and all register fields in the instructions are of equal size. Let \(X\) be the number of bits used to encode the UNUSED field, \(Y\) be the number of bits used to encode the OPCODE field, and \(Z\) be the number of bits used to encode the immediate value/address field. The value of \(X + 2Y + Z\) is ............
A processor with 16 general-purpose registers uses a 32-bit instruction format. The instruction format consists of an opcode field, an addressing mode field, two register operand fields, and a 16-bit scalar field. If 8 addressing modes are to be supported, the maximum number of unique opcodes possible for every addressing mode is ............
Which of the following statements is/are FALSE?}
An instruction format has the following structure: \begin{center} Instruction Number: Opcode destination reg, source reg-1, source reg-2} \end{center} Consider the following sequence of instructions to be executed in a pipelined processor: I\(_1\): DIV R3, R1, R2
I\(_2\): SUB R5, R3, R4
I\(_3\): ADD R3, R5, R6
I\(_4\): MUL R7, R3, R8 Which of the following statements is/are TRUE?
Node X has a TCP connection open to node Y. The packets from X to Y go through an intermediate IP router R. Ethernet switch S is the first switch on the network path between X and R. Consider a packet sent from X to Y over this connection. Which of the following statements is/are TRUE about the destination IP and MAC addresses on this packet at the time it leaves X?
The format of a single-precision floating-point number as per the IEEE 754 standard is:} \begin{center} \begin{tabular}{|c|c|c|} \hline Sign (1 bit) & Exponent (8 bits) & Mantissa (23 bits)
\hline \end{tabular} \end{center} Choose the largest floating-point number among the following options:
Let \( T(n) \) be the recurrence relation defined as follows: \[ T(0) = 1, \quad T(1) = 2, \quad T(n) = 5T(n-1) - 6T(n-2) \quad \text{for } n \geq 2 \] Which one of the following statements is TRUE?
Consider a computer with a \(4 \, \text{MHz}\) processor. Its DMA controller can transfer \(8 \, \text{bytes}\) in \(1\) cycle from a device to main memory through cycle stealing at regular intervals. Which one of the following is the data transfer rate (in bits per second}) of the DMA controller if \(1\%\) of the processor cycles are used for DMA?
Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?
A processor X1 operating at 2 GHz has a standard 5-stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X2 operating at same clock frequency has an additional branch predictor unit (BPU) that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for X1 and X2. If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X2 over X1 in executing P is \(\underline{\hspace{1cm}}\).
Consider a system with 2 KB direct-mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS…). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?