CO · GATE CS 2027
8 topics and 21 sheets. Open a topic for its sheets and the topics it depends on.
Instruction formats and field widths, counting instructions with expanding opcodes, zero- to three-address code, instruction types, RISC versus CISC, condition flags, byte ordering and alignment, and every addressing mode with its effective-address rule, memory-reference count and typical use.
Ripple-carry and carry-lookahead adders with gate-delay counts, the adder-subtractor, overflow logic and flags, array and Booth multiplication, shifters, and the single-bus and three-bus datapaths with the register transfers and control steps of fetch and execute.
Hardwired control from a step counter, decoders and sum-of-products signal equations; microprogrammed control with control words, horizontal and vertical microinstructions, control-memory size calculations, microinstruction sequencing and a short note on nanoprogramming.
Building a memory from smaller chips: chip counts, decoders, address maps, partial decoding, DRAM address multiplexing and interleaving. Then locality, hit ratio and average access time for hierarchical and simultaneous access, multilevel formulas and memory stall cycles.
Direct, set-associative and fully associative mapping, the tag, index and offset split, tag-memory size and lookup hardware, traced reference strings with LRU and FIFO, the three miss types, array traversal misses, write-through and write-back with allocation policies, and multilevel caches.
I/O interfaces, memory-mapped and isolated I/O, programmed I/O, the interrupt sequence, vectored and daisy-chain priority, masking and nesting, CPU overhead of polling and interrupts, and DMA: controller, bus handshake, burst, cycle-stealing and transparent modes with CPU-time fractions.
Pipeline clock from stage and latch delays, total time, speedup, efficiency, throughput and CPI; data hazards with space-time diagrams, stalls and forwarding; control hazards with branch penalties, prediction and delay slots; structural hazards and combined CPI.
The last three sheets: traps that cost marks with the rule that fixes each, question patterns with the routine to run, and a one-page master sheet of formulas, tables and numbers to recognise.
Fixed-length instruction formats: opcode, mode, register, address and immediate fields, each sized with a ceiling log. Zero-, one-, two- and three-address code for one expression with instruction counts, data references and code size. Expanding opcodes level by level with a Kraft-style feasibility check, and three solved past GATE questions on field budgets and expanding opcodes.
The instruction set architecture (ISA): instruction types, ISA classes by where ALU operands live, RISC versus CISC, the CPU-time equation with a worked comparison, condition flags with the signed and unsigned compare rules, big- and little-endian byte order with a byte table, alignment, CALL and RET on a downward stack, and what belongs to the ISA versus the implementation.
Every addressing mode with its effective-address (EA) rule, the memory reads needed to reach the operand and its typical use: immediate, register, direct, indirect, register indirect, indexed, base plus displacement, PC-relative, auto-increment, auto-decrement and implied. One instruction worked in every mode, PC-relative offsets and ranges, relocation, memory references per instruction and the usual traps.
Half and full adders, the ripple-carry adder with given full-adder delays and with a gate-delay model, carry lookahead with generate and propagate, the delays of single-level, rippled-block and two-level lookahead adders for 16 bits, the adder-subtractor, overflow logic with a table of 8-bit cases, the four flags and the two's complement facts behind them.
Shift-and-add multiplication, the combinational array multiplier and its gate counts, Booth's algorithm with a full register trace of 7 times minus 3, Booth recoding with best and worst cases, bit-pair (radix-4) recoding, the most-negative-multiplicand edge case, logical and arithmetic shifts and rotates with their numeric meaning, and the barrel shifter.
The single-bus datapath with its PC, MAR, MDR, IR, register file and the Y and Z registers around the ALU, register-transfer notation and the four classes of micro-operation, the control steps and signals for instruction fetch, register and memory-operand ADD, store and branch, and the same addition on a three-bus datapath, with the rules for counting steps.
The hardwired control unit: instruction decoder, step counter and step decoder, condition and external inputs, and control signals as sums of step-and-instruction products derived from the single-bus step tables. Step-counter sizing, waiting for memory, conditional end of an instruction, and a side-by-side comparison with microprogrammed control.
Microprogrammed control: control word, microinstruction, microprogram, control memory, microprogram counter and mapping logic. Horizontal and vertical microinstruction formats with width and control-memory size worked twice, solving a format for its next-address field, microinstruction sequencing by increment, branch and mapping, a microprogram for the single-bus instructions and a short note on nanoprogramming.
Building a memory from smaller chips: chip pins and capacity, chip count for width and depth expansion, the row decoder on the high address bits, address ranges per row, which chip holds a given address, a byte-addressable 2 MB example, full versus partial decoding and aliasing, DRAM row and column address multiplexing with refresh overhead, SRAM versus DRAM, and low- and high-order interleaving.
Locality and the levels of the hierarchy, hit ratio, average access time for hierarchical (look-through) and simultaneous (look-aside) access, solving for a target hit ratio, block refill time, three-level formulas in both models, local versus global miss rates, memory stall cycles in CPI with two solved past GATE questions, and average cost per unit of storage.
Direct, set-associative and fully associative mapping: the tag, index and offset formulas, one cache at one, two, four and all ways, locating a given address, how many memory blocks compete for a set, tag-memory size with valid, dirty and replacement bits, comparators and multiplexers, the rules for doubling ways, capacity or block size, a word-addressable split and a solved past GATE question.
One block reference string replayed on a direct-mapped, a 2-way FIFO, a 2-way LRU and a fully associative cache, the compulsory, capacity and conflict classification, replacement policies and their bookkeeping bits, miss counts for row-order and column-order traversal of a 2-D array (simulated), a 1-D sweep, the effect of block size, associativity and capacity, and FIFO's anomaly.
Write-through versus write-back, write-allocate versus no-write-allocate and their usual pairings, the dirty bit and write buffer, effective access time under each policy worked with one set of numbers, memory write traffic, two-level caches with local and global miss rates, stall cycles per instruction and misses per thousand instructions, inclusion, and a solved past GATE question on write policies.
The I/O interface and its data, status and control registers, memory-mapped versus isolated I/O, programmed I/O with polling, the interrupt sequence with a solved past GATE question, finding the source by polling, daisy chain, priority encoder or vector, masking, priority and nesting, interrupts versus exceptions, and the CPU time spent on polling, interrupts and DMA worked with one set of numbers.
Direct memory access: the DMA controller and its registers, the bus request and grant handshake, the steps of a transfer, burst, cycle-stealing and transparent modes compared, the CPU-blocked fraction and the cycle-stealing rate formulas, a solved past GATE question on transfer rate, block-time and CPU-loss examples, when the bus can be granted, DMA against interrupt overhead and the cache-coherence caveat.
Instruction pipelining: clock period from the slowest stage plus latch delay, total time for n instructions, speedup and its limit, efficiency and throughput, unequal stages and stage splitting, latency, CPI with stall cycles and speedup against a multi-cycle machine, with two solved past GATE questions and original examples, all computed by script.
Data hazards in the 5-stage pipeline: RAW, WAR, WAW and RAR dependences, a space-time diagram of a load and two dependent instructions with and without forwarding, the stall table by producer type and distance, the stall formula with and without a split-cycle register file, how the forwarding unit and the load-use detector work, removing a stall by scheduling, and a solved past GATE question on dependences.
Control hazards: branch penalty from the stage where the branch resolves, CPI under stall-always, predict-not-taken and dynamic prediction worked with one set of numbers, delayed branches, 1-bit and 2-bit predictors simulated on a loop, structural hazards from a single memory port or a non-pipelined unit, and the combined CPI and speedup when data, control and structural stalls add up.
The common wrong turns in Computer Organization questions, grouped from instruction formats to pipeline hazards: each row gives the wrong belief, the correct rule and a checked number or pointer to the sheet that explains it. Covers field widths, expanding opcodes, addressing, overflow, Booth, microinstruction widths, chip arrays, access-time models, cache splits and write policies, interrupts, DMA, pipeline time, forwarding and branch penalties.
Recognition cues for the usual Computer Organization question types, each with the first step and method to run and the assumption or slip to check, from instruction formats and addressing through ALU delays, control memory, chip arrays, access time, cache splits and traces, write policies, interrupts and DMA to pipeline time, stalls and branches. Ends with a general routine for numericals and answer-size sanity checks.
One-page summary of the pack: field widths and expanding opcodes, addressing-mode reads, adder delays, overflow and Booth, control steps and control-memory size, chip arrays, access-time formulas, the cache split with its worked table, write policies, interrupt order and DMA formulas, pipeline time and CPI, the stall table and branch penalties, with the numbers worth recognising and the last-minute checks.
