GATE CS & IT Engineering Computer Organization and Architecture Syllabus

What are the three cache mapping techniques?

Direct mapping (each block maps to exactly one cache line), Fully associative mapping (a block can go in any line), and Set-associative mapping (a block maps to one set, but any line within that set).

In direct-mapped cache, how is a physical address divided?

Into three fields: Tag, Line (index) number, and Block/word offset. The line bits select the cache line; the tag is compared to validate the block; the offset selects the word within the block.

For a k-way set-associative cache, how does each address map?

The address is split into Tag, Set number, and Word offset. The block maps to a specific set (= block number mod number of sets) and may occupy any of the $k$ lines in that set.

What are the three categories of cache misses (the 'three Cs')?

Compulsory (cold/first-reference) misses, Capacity misses (cache too small to hold the working set), and Conflict (collision) misses (multiple blocks competing for the same set/line).

What are the two main cache write policies for hits?

Write-through (write to both cache and main memory simultaneously) and Write-back (write only to cache, mark the line dirty, and update memory only when the block is evicted).

Compare write-through and write-back caches.

Write-through keeps memory always consistent but causes more memory traffic. Write-back reduces memory traffic but needs a dirty bit and risks inconsistency until the block is written back on eviction.

Name three common cache replacement policies for associative caches.

LRU (Least Recently Used), FIFO (First In First Out), and Random replacement. (Optimal/Belady's is theoretical.)

What is the formula for average access time of a two-level (L1, L2) cache hierarchy?

$$T_{avg} = h_1 t_1 + (1-h_1)\big[h_2 t_2 + (1-h_2)\, t_m\big]$$ where $h_1, h_2$ are L1 and L2 hit ratios and $t_1, t_2, t_m$ are L1, L2, and main-memory access times.

If a cache has $S$ sets, $K$ ways, and block size $B$ bytes, what is its total data capacity?

Total capacity $= S \times K \times B$ bytes (number of sets $\times$ associativity $\times$ block size).

What is the basic difference between SRAM and DRAM?

SRAM stores each bit in a latch (typically 6 transistors), is fast, needs no refresh, and is used for cache. DRAM stores each bit as charge on a capacitor (1 transistor + 1 capacitor), is denser and cheaper, needs periodic refresh, and is used for main memory.

Why does DRAM require periodic refreshing?

DRAM stores bits as charge on tiny capacitors that leak over time; without periodic refresh (rewriting the charge) the stored data would be lost.

How is a memory of $2^n$ words by $m$ bits addressed, and how many address lines and data lines does it need?

It needs $n$ address lines (to select one of $2^n$ words) and $m$ data lines (the word width). Total capacity is $2^n \times m$ bits.

What is memory interleaving and why is it used?

Memory interleaving divides memory into multiple independent modules (banks) so that consecutive addresses lie in different banks, allowing several accesses to proceed in parallel and increasing effective memory bandwidth.

Distinguish low-order and high-order memory interleaving.

Low-order interleaving uses the least-significant bits to select the module, so consecutive addresses spread across modules (good for parallel/sequential access). High-order interleaving uses the most-significant bits, keeping consecutive addresses in the same module.

What is the memory hierarchy ordered from fastest/smallest to slowest/largest?

Registers → Cache (L1, L2, L3) → Main memory (DRAM) → Secondary storage (SSD/HDD) → Tertiary/offline storage. Speed and cost-per-bit decrease, while capacity increases, as you go down.

What distinguishes secondary storage from main memory?

Secondary storage (HDDs, SSDs, optical) is non-volatile, much larger and cheaper per bit, slower, and not directly addressable by the CPU; it retains data without power, unlike volatile main memory.

For a magnetic hard disk, what is the formula for total access time of a request?

$$T_{access} = T_{seek} + T_{rotational} + T_{transfer}$$ i.e., seek time (move head to track) + rotational latency (sector rotates under head) + transfer time (read/write the data).

What is the average rotational latency of a disk spinning at $R$ revolutions per minute?

Average rotational latency = half a rotation = $$\frac{1}{2} \cdot \frac{60}{R} \text{ seconds} = \frac{30}{R}\text{ s}.$$ For example, at $R = 7200$ RPM it is about $4.17\text{ ms}$.

How is disk storage organized in terms of tracks, sectors, and cylinders?

Each platter surface has concentric tracks; each track is divided into sectors (smallest addressable unit). A cylinder is the set of tracks at the same radius across all platter surfaces.

What is the data transfer rate of a disk track with $N$ bytes per track spinning at one rotation per $T$ seconds?

Transfer rate $= \dfrac{N}{T}$ bytes/second; equivalently it equals (bytes per track) $\times$ (rotations per second), i.e. $N \cdot \frac{R}{60}$ for $R$ RPM.

What are the main advantages of SSDs over HDDs?

SSDs use flash memory with no moving parts, giving much lower (near-zero) seek/rotational latency, higher random-access speed, lower power, silent operation, and better shock resistance; HDDs offer lower cost per bit and higher capacity.

What are the three primary methods of I/O data transfer between an I/O device and memory/CPU?

Programmed I/O (polling), Interrupt-driven I/O, and Direct Memory Access (DMA).

What is programmed (polled) I/O and its main drawback?

In programmed I/O the CPU continuously polls the device status flag and transfers each data word itself. Drawback: the CPU is fully busy-waiting, wasting cycles that could do useful work.

What is interrupt-driven I/O?

The device sends an interrupt signal to the CPU when it is ready; the CPU suspends its current program, runs an interrupt service routine (ISR) to handle the transfer, then resumes. This avoids busy-waiting.

What is the difference between maskable and non-maskable interrupts?

Maskable interrupts can be disabled/ignored by the CPU (via an interrupt-enable/mask bit), while non-maskable interrupts (NMI) cannot be disabled and are reserved for critical events such as hardware failures or power loss.

Distinguish vectored and non-vectored interrupts.

In vectored interrupts the device supplies the address (vector) of its ISR directly to the CPU. In non-vectored interrupts the ISR address is fixed/predetermined, and the CPU must poll to identify the interrupting device.

What is an interrupt service routine (ISR), and what must the CPU save before running it?

An ISR is the routine that handles a specific interrupt. Before executing it the CPU saves the current context — at minimum the program counter (return address) and processor status/flags — so the interrupted program can resume correctly.

What is DMA (Direct Memory Access) and its main advantage?

DMA lets an I/O device transfer data directly to/from main memory through a DMA controller without the CPU handling each word. Advantage: the CPU is freed during bulk transfers, greatly improving throughput for high-speed devices.

What are the three modes of DMA transfer?

Burst (block) mode — the DMA controller holds the bus and transfers the whole block at once; Cycle stealing mode — DMA transfers one word per stolen bus cycle, interleaving with CPU; Transparent/hidden mode — DMA transfers only when the CPU is not using the bus.

In DMA, what is 'cycle stealing' and how does it differ from burst mode?

In cycle stealing the DMA controller transfers one word at a time, 'stealing' an occasional memory bus cycle from the CPU so the CPU is only briefly delayed. In burst mode the DMA controller seizes the bus and transfers the entire block continuously, halting the CPU's bus access for that duration.