Computer Organization and Architecture

Instruction cycle

How a stored-program computer runs: fetch, decode, optional indirect cycle, execute, and the interrupt check; the registers involved, register-transfer notation, the PC after the fetch, memory references per instruction and the clock cost of each instruction.

Instruction set architecture and formats

What an instruction set architecture is, the classes of ISA by where operands live (stack, accumulator, register-memory, load-store), the same expression on each, endianness and alignment, condition codes, word size and address bits, and the code-size and speed trade-offs.

Instruction formats and expanding opcodes

How an instruction word is divided into fields, how to compute field widths from the machine's parameters, fixed-format examples, branch and jump reach, and the expanding-opcode technique that GATE counts again and again.

Addressing modes

The ways an instruction names its operands: immediate, direct, indirect, register, register indirect, displacement, indexed, PC-relative and auto-increment or decrement, with the effective-address rule, the number of memory references and the typical use of each.

Procedure calls and stack frames in hardware

How the hardware supports procedure calls: the stack pointer, push and pop, CALL and RET, the frame layout (arguments, return address, saved frame pointer, locals), prologue and epilogue, register saving, recursion depth and stack usage.

ALU design

How an arithmetic and logic unit is built from one-bit slices: AND, OR, adder, B inversion and a multiplexer, the flags it produces, set-less-than, the zero detector, shifters, and what limits its speed.

Multiplication: shift-add and Booth

How hardware multiplies: the shift-and-add multiplier for unsigned numbers, Booth's algorithm for two's complement numbers, why it works, how many operations it needs, the radix-4 (bit-pair) version, array multipliers and the size of the product.

Single-bus datapath and register transfer

The registers, ALU and bus that execute instructions: the control signals, the sequence of control steps for fetch and for ADD and LOAD, why a single bus needs the temporary registers Y and Z, memory access with WMFC, and how steps translate into clocks.

Hardwired control unit

A control unit built from logic gates: the control step counter, the instruction decoder and the logic that turns them (and the condition flags) into control signals; the equations of each signal, its speed, size and the contrast with microprogramming.

Microprogrammed control unit

A control unit built around a memory: microinstructions in a control store, the micro-program counter and sequencing, horizontal and vertical formats, the control-word size and control-store size calculations, and the trade-offs against hardwired control.

Memory hierarchy and performance (AMAT)

Why computers have levels of memory, the principle of locality, hit and miss, hit ratio, average memory access time for one and several levels, hierarchical against simultaneous access, and what a hierarchy buys.

Memory interfacing and address decoding

Connecting memory chips to a processor: address, data and control lines, chip select from a decoder, building a memory from smaller chips in width and in depth, the address map, partial decoding and aliasing, memory-mapped I/O and interleaving.

Cache memory mapping

How a block of memory is placed in the cache: direct, fully associative and set-associative mapping, the tag, index and offset fields, the size of the tag store, hit detection, and the three kinds of misses.

Cache replacement and write policies

What the cache does when a set is full (LRU, FIFO, random, optimal) and when the processor writes (write-through, write-back, allocate or not), the dirty bit, memory traffic, and why more cache lines can mean more misses under FIFO.

Cache performance and multilevel caches

What a cache costs in time: average memory access time, memory stall cycles and CPI, local and global miss rates, two-level caches, split caches, the effect of block size and associativity, and how to improve a cache.

I/O interface and programmed I/O

How a processor talks to a device: the interface registers, memory-mapped and isolated I/O, strobe and handshake transfer, serial framing, and programmed I/O by polling with its cost, compared with interrupt-driven I/O and DMA.

Interrupts and vectoring

Interrupt-driven I/O: the interrupt cycle step by step, maskable and non-maskable requests, interrupts versus traps and exceptions, how the source is identified (polling, vectored, daisy chain, parallel priority), priorities and nesting, latency and the CPU time an interrupt-driven device costs.

Direct memory access

DMA: the controller's registers, the sequence from setup to the final interrupt, burst, cycle-stealing and transparent modes, bus request and grant, how long the CPU is held up, the break-even against interrupt-driven I/O, and cache and address traps.

Instruction pipelining

Overlapping the execution of instructions: the stages and pipeline registers, the space-time diagram, fill and drain, latency versus throughput, the clock set by the slowest stage plus register overhead, balancing and splitting stages, and why uniform RISC instructions pipeline well.

Pipeline speedup and CPI calculations

The arithmetic of pipeline performance: cycles and time for n instructions, speedup against a non-pipelined machine, efficiency and throughput, unequal stages and register overhead, deeper pipelines and their limit, and CPI and speedup when stalls are added.

Structural, data and control hazards

Why a pipeline cannot always start an instruction every cycle: structural hazards (a shared resource), data hazards (RAW, and WAR and WAW), control hazards (branches), how many stall cycles each costs with and without forwarding, and how interlocks and compilers deal with them.

Forwarding, stalls and branch prediction

How hazards are reduced: forwarding paths and their control conditions, the load-use stall, compiler scheduling, the branch penalty and the ways to cut it (stall, predict not taken, resolve early, delayed branch), and static and dynamic branch prediction with one-bit and two-bit counters, with the effect on CPI.

Performance: CPI, MIPS and Amdahl's law

Measuring and comparing processors: CPU time as instruction count times CPI times clock period, average CPI from an instruction mix, MIPS and why it misleads, speedup, and Amdahl's law with its limit for one or several enhancements and for parallel processors.

Disk structure and access time

The hard disk as GATE models it: platters, surfaces, tracks, sectors and cylinders; capacity and the size of a sector address; converting between a (cylinder, surface, sector) address and a sector number; rotation, seek and transfer time; and why a contiguous file is read hundreds of times faster than the same sectors scattered.