GATE Computer Science and Information Technology (CS) Flashcards

24 sample cards from the Computer Science and Information Technology (CS) deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. Name the four general categories of a CPU's functional units / register-level organization.

   The datapath (ALU and registers), the control unit (generates control signals), the register file (general-purpose registers, PC, IR, MAR, MBR), and the bus/interconnect linking them to memory and I/O.

2. What is the purpose of the Program Counter (PC) and Instruction Register (IR)?

   The PC holds the address of the next instruction to fetch. The IR holds the currently fetched instruction being decoded and executed.

3. Define the five classic stages of a RISC instruction pipeline.

   IF (instruction fetch), ID (instruction decode/register read), EX (execute/ALU), MEM (memory access), WB (write back). Each stage handles a different instruction concurrently.

4. What is the ideal speedup of a $k$-stage pipeline, and why is it not achieved in practice?

   Ideal speedup approaches $k$ (the number of stages) for a large instruction count. It is not achieved due to pipeline hazards, stage imbalance, pipeline fill/drain overhead, and stalls.

5. List the three types of pipeline hazards.

   Structural hazards (resource conflict), data hazards (instruction depends on a result not yet available), and control hazards (branches changing the instruction flow). Each can cause pipeline stalls.

6. What is a data hazard, and how does forwarding (bypassing) mitigate it?

   A data hazard occurs when an instruction needs a value that a prior instruction hasn't yet written back. Forwarding routes the ALU result directly from one stage to a dependent instruction's input, avoiding a stall instead of waiting for write-back.

7. Define the three RAW, WAR, and WAW data dependencies.

   RAW (read-after-write, true dependency): an instruction reads a register a prior one writes. WAR (write-after-read, anti-dependency): writes after a prior read. WAW (write-after-write, output dependency): two writes to the same register. Only RAW is a true data hazard in in-order pipelines.

8. Give the formula for the effective CPI of a pipeline with stalls.

   $\text{CPI}_{eff} = 1 + \text{stall cycles per instruction}$. Execution time $= \text{Instruction count} \times \text{CPI}_{eff} \times \text{clock cycle time}$.

9. What is the typical ordering of the memory hierarchy from fastest to slowest?

   Registers $\rightarrow$ L1 cache $\rightarrow$ L2 cache $\rightarrow$ L3 cache $\rightarrow$ main memory (DRAM) $\rightarrow$ secondary storage (SSD/disk). Speed and cost per bit decrease, while capacity increases, going down the hierarchy.

10. State the average memory access time (AMAT) formula.

    $\text{AMAT} = \text{Hit time} + \text{Miss rate} \times \text{Miss penalty}$. With multiple levels it is applied recursively for each cache level.

11. Compare direct-mapped, fully associative, and set-associative cache mapping.

    Direct-mapped: each memory block maps to exactly one cache line (fast, high conflict misses). Fully associative: a block can go anywhere (no conflict misses, costly search). Set-associative: a block maps to one set of $k$ lines, balancing the two ($k$-way).

12. How is a memory address split for cache lookup in a set-associative cache?

    The address divides into Tag, Set Index, and Block Offset fields. Offset bits $= \log_2(\text{block size})$, index bits $= \log_2(\text{number of sets})$, and the remaining high-order bits form the tag.

13. Distinguish write-through from write-back cache policies.

    Write-through updates both cache and main memory on every write (simple, consistent, more traffic). Write-back updates only the cache and marks the line dirty, writing to memory only on eviction (less traffic, needs a dirty bit).

14. Name the three categories of cache misses (the '3 Cs').

    Compulsory (cold) misses on first access to a block, Capacity misses when the working set exceeds cache size, and Conflict misses when multiple blocks map to the same set in non-fully-associative caches.

15. Contrast programmed I/O, interrupt-driven I/O, and DMA.

    Programmed I/O: CPU polls the device status (wastes cycles). Interrupt-driven I/O: device signals the CPU when ready (no busy-waiting). DMA: a controller transfers data directly between device and memory, interrupting the CPU only at completion (best for bulk transfer).

16. What happens during an interrupt service sequence?

    The CPU finishes the current instruction, saves the program state (PC and registers), disables/acknowledges the interrupt, jumps to the Interrupt Service Routine via the vector table, executes the ISR, then restores state and resumes the interrupted program.

17. What is the difference between the storage classes 'static' and 'automatic' in C?

    Automatic (local) variables live on the stack, are created on block entry and destroyed on exit. Static variables persist for the program's lifetime in a fixed memory region, retaining value between function calls; file-scope static also limits linkage to that file.

18. In C, what is the difference between call-by-value and call-by-reference (via pointers)?

    Call-by-value copies the argument, so changes inside the function don't affect the caller's variable. C passes a pointer (address) to simulate call-by-reference: dereferencing the pointer (e.g., $*p$) lets the function modify the caller's actual variable.

19. What does pointer arithmetic $p + n$ compute for a pointer $p$ to type $T$?

    It yields the address $p + n \times \text{sizeof}(T)$, advancing by $n$ elements (not $n$ bytes). This is why $a[i]$ is equivalent to $*(a + i)$ for an array $a$.

20. What two components must every recursive function have to terminate correctly?

    A base case (stopping condition that returns without recursing) and a recursive case that moves toward the base case. Each call uses a new stack frame; missing or unreachable base cases cause infinite recursion and stack overflow.

21. Compare the time and space complexity of array vs. linked-list operations for random access and insertion.

    Array: random access $O(1)$, insertion/deletion at arbitrary position $O(n)$ (shifting). Linked list: random access $O(n)$ (traversal), insertion/deletion given the node pointer $O(1)$. Linked lists also use extra space for pointers.

22. Contrast a stack and a queue by their access discipline and core operations.

    A stack is LIFO (last-in first-out) with push and pop at one end (top). A queue is FIFO (first-in first-out) with enqueue at the rear and dequeue at the front. Both basic operations are $O(1)$.

23. What are the worst-case search, insert, and delete complexities of a balanced BST versus an unbalanced BST?

    Balanced BST (e.g., AVL, red-black): $O(\log n)$ for search, insert, and delete. Unbalanced (degenerate/skewed) BST: $O(n)$ because it can degrade into a linked list. In-order traversal of a BST yields sorted order.

24. State the heap property and the array index relationships for a binary heap.

    Max-heap: every parent $\geq$ its children (min-heap: parent $\leq$ children). For a node at index $i$ (0-based): left child $= 2i+1$, right child $= 2i+2$, parent $= \lfloor (i-1)/2 \rfloor$. Insert and extract-min/max are $O(\log n)$; peek is $O(1)$.

What this deck covers

Computer Science and Information Technology (CS) flashcards FAQ