Computer Organization & Architecture (COA) Academic Curriculum Guide
Computer Organization and Architecture examines the functional operational units and hardware-software interface governing computation. This guide covers Instruction Set Architecture (ISA), addressing modes, arithmetic algorithms (Booth's, restoring/non-restoring division), pipelining hazards, cache memory mapping architectures, and I/O interrupt/DMA systems.
Unit-by-Unit Theoretical Revision
Unit 1: Basic Computer Structure & Instruction Set Architecture
Functional units include the Arithmetic and Logic Unit (ALU), Control Unit (CU), Memory Unit, Input, and Output subsystems connected via system buses (data, address, and control).
- Von Neumann vs Harvard Architecture: Von Neumann utilizes shared memory and buses for instructions and data (subject to Von Neumann Bottleneck); Harvard provides separate memory and buses for concurrent instruction and data fetching.
- Instruction Formats: Zero-address (stack-based), One-address (accumulator-based), Two-address, and Three-address instructions.
- Addressing Modes: Immediate (operand in instruction), Direct / Absolute (instruction contains memory address), Indirect (address of address), Register (operand in register), Register Indirect, Displacement / Indexed, and PC-Relative (branch instructions).
- RISC vs CISC Architectures: RISC emphasizes single-cycle fixed-length instructions, load/store architecture, and hardwired control. CISC provides variable-length complex instructions, multiple addressing modes, and microprogrammed control.
Unit 2: Computer Arithmetic & ALU Design
- Addition & Subtraction: Ripple Carry Adder (propagation delay O(n)) vs Carry Lookahead Adder (CLA) generating carry bits in parallel using
G_i = A_i · B_iandP_i = A_i ⊕ B_i. - Booth’s Multiplication Algorithm: Multiplies signed 2's complement numbers efficiently by scanning adjacent bits
(Q_i, Q_{i-1}). Replaces strings of consecutive 1s with an addition at the start and subtraction at the end, reducing addition operations. - Division Algorithms: Restoring Division (subtracts divisor and restores original remainder if result is negative) vs Non-Restoring Division (avoids restoration step by performing conditional addition or subtraction in the subsequent cycle).
- Floating-Point Representation: IEEE 754 Standard: Single Precision (32 bits: 1 sign, 8 exponent with bias 127, 23 mantissa) and Double Precision (64 bits: 1 sign, 11 exponent with bias 1023, 52 mantissa).
Unit 3: Processor Design & Instruction Pipelining
- Instruction Execution Cycle: Fetch → Decode → Execute → Memory Access → Write Back (IF, ID, EX, MEM, WB).
- Pipeline Performance Metrics: Speedup
S_k = (n · k) / (k + n - 1)for n instructions on a k-stage pipeline. Ideal throughput reaches 1 instruction per cycle (CPI = 1). - Pipelining Hazards:
- Structural Hazards: Hardware resource conflicts (e.g., simultaneous memory access by IF and MEM stages; resolved using separate instruction and data caches).
- Data Hazards: Read-After-Write (RAW / True dependence), Write-After-Read (WAR / Anti-dependence), and Write-After-Write (WAW / Output dependence). Resolved using Operand Forwarding (Bypassing) or pipeline stalls (bubbles).
- Control Hazards: Arise from branch and jump instructions modifying Program Counter. Resolved via Branch Prediction (static or dynamic branch target buffers) and delayed branching.
Unit 4: Memory System & Cache Hierarchy
Memory hierarchy balances access speed, capacity, and cost per bit: Registers → Cache (L1, L2, L3) → Main RAM → Secondary Storage.
- Principle of Locality: Temporal Locality (recently referenced items likely accessed again soon) and Spatial Locality (adjacent memory locations likely accessed soon).
- Cache Mapping Techniques:
- Direct Mapping: Block
jmaps to cache line(j % m). Simplest hardware; susceptible to conflict misses. - Fully Associative Mapping: Memory block can reside in any cache line. Eliminates conflict misses; requires expensive parallel content-addressable memory (CAM) comparator hardware.
- Set-Associative Mapping: Cache divided into sets of k lines (k-way associative). Balances speed and hardware complexity.
- Direct Mapping: Block
- Cache Write Policies: Write-Through (writes simultaneously to cache and RAM) vs Write-Back (writes only to cache, setting dirty bit; RAM updated on line eviction).
Unit 5: Input/Output Organization & Interrupts
- I/O Data Transfer Modes: Programmed I/O (CPU polls I/O status register continuously; high CPU wastage), Interrupt-Driven I/O (device interrupts CPU when ready), and Direct Memory Access (DMA).
- DMA Controller (DMAC): Transfers entire data blocks directly between I/O device and memory without CPU intervention. Bus arbitration via Burst Mode (entire block transferred) or Cycle Stealing (DMA steals single bus cycles from CPU).
- Interrupt Handling: Vectored vs Non-Vectored interrupts, Interrupt Service Routine (ISR), priority interrupt controllers (Daisy Chaining).
Cache Mapping Architectures Comparison
| Mapping Scheme | Cache Placement | Address Fields | Hardware Complexity | Conflict Misses |
|---|---|---|---|---|
| Direct Mapping | Exactly one line: (Block % Lines) | Tag, Line, Word | Lowest (1 comparator) | High |
| Fully Associative | Any available line anywhere in cache | Tag, Word | Highest (N comparators) | Zero |
| k-Way Set Associative | Any line within set (Block % Sets) | Tag, Set, Word | Moderate (k comparators) | Low to Moderate |
High-Frequency University Exam Questions
Q1: Explain the three types of pipeline hazards and discuss methods to overcome them.
Pipeline hazards prevent the next instruction from executing in its designated clock cycle: (1) Structural Hazards: Occur when two stages attempt to use the same physical resource simultaneously. Overcome by hardware duplication (separate Harvard instruction and data caches). (2) Data Hazards: Occur when instructions depend on the result of a previous incomplete instruction (RAW, WAR, WAW). Overcome by operand forwarding, compiler instruction reordering, or inserting pipeline stalls. (3) Control Hazards: Occur due to branch instructions. Overcome by dynamic branch prediction, branch target buffers, and delayed branching.
Q2: Explain Booth’s Multiplication Algorithm and multiply signed numbers (-5) and (+3).
Booth’s algorithm inspects adjacent multiplier bits (Qâ‚€, Qâ‚‹â‚). If bits are 10, subtract multiplicand from accumulator; if 01, add multiplicand; if 00 or 11, perform arithmetic right shift only. In each step, the combined register [A, Q, Qâ‚‹â‚] is arithmetically right-shifted by 1 bit, preserving the sign bit. This handles 2's complement signed integers uniformly without separate sign processing.
Q3: How does Direct Memory Access (DMA) transfer data, and what is cycle stealing?
DMA offloads high-volume data transfers from the CPU by allowing the DMA controller to take control of the system bus. The CPU initializes the DMA controller with the start memory address, transfer count, and transfer direction, and resumes other processing. In Burst Mode, the DMA controller transfers the entire block of data at once. In Cycle Stealing, the DMA controller temporarily takes control of the memory bus for a single bus cycle between CPU instruction phases, allowing concurrent CPU computation with low transfer delay.