UNIT 3: Computer System Organization

I. Fundamental Computer Architecture & Models

Von Neumann Model

• Definition: A stored-program digital computer architecture where instruction memory and data memory share the same underlying memory unit and bus.

• Key Components:

  • Memory: Stores both data and instructions.

  • Control Unit (CU): Fetches, decodes, and controls execution of instructions.

  • Arithmetic Logic Unit (ALU): Performs arithmetic and logical operations.

  • Input/Output (I/O): Interface with external devices.

• Stored-Program Concept: Instructions are stored in memory as binary codes and fetched sequentially by the CU for execution.

• Handling of Processing: A single bus is used for both data and instructions, creating the von Neumann bottleneck—a limitation on throughput.

Instruction Cycle

The fundamental operation cycle of a CPU. Phases:

1. Fetch (F): CU reads instruction from memory address in Program Counter (PC) into Instruction Register (IR). PC is incremented.

2. Decode (D): CU decodes opcode in IR to determine operation and required operands.

3. Execute (E): CU signals ALU or other units to perform the operation (e.g., ADD, LOAD).

4. Indirect (Optional): If addressing mode is indirect, fetch effective address from memory.

5. Interrupt (Optional): Check for and service interrupts.

6. Store (Optional): Write result back to memory or register.

[!TIP] Exam questions often ask for a flowchart. Remember: Fetch → Decode → Execute is the core loop. Indirect and Interrupt are conditional phases.

Micro-operations & Register Transfer Language (RTL)

• Micro-operation: The elementary operations performed on data stored in registers (e.g., R1 ← R2, R3 ← R1 + R2).

• Types:

  • Register Transfer: Move data between registers (e.g., R2 ← R1).

  • Arithmetic: R3 ← R1 + R2.

  • Logic: R4 ← R1 AND R2.

  • Shift: R5 ← shift_left(R6).

• RTL: A symbolic language to describe micro-operations and data flow between registers.

II. Central Processing Unit (CPU) & Control

Control Unit Design: Comparison

[!TIP] Hardwired is fast but rigid. Microprogrammed is flexible but slower. Modern CPUs often use a hybrid approach.

Microprogramming Details

Micro-instruction Format

A microinstruction typically contains three fields:

1. Control Field (Operation): Bits that activate specific control signals (e.g., ALU_OP, READ, WRITE).

2. Next Address Field: Determines address of next microinstruction. Can be:

   • Sequential: CA + 1

   • Branch: Based on condition bits (e.g., ZERO?).

3. Condition Field (Optional): Specifies condition for branching.

Encoding Techniques:

• Horizontal Microprogramming: Wide microinstructions (~1 bit per control signal). High parallelism, large CM size.

• Vertical Microprogramming: Encoded fields (log₂N bits for N signals). Less parallelism, smaller CM size, resembles machine code.

Microprogram Sequencer

• Function: Generates the address of the next microinstruction to be fetched from CM.

• Block Diagram Components:

  • Control Memory (CM): Stores microprogram.

  • Microinstruction Register (μIR): Holds current microinstruction.

  • Address Register (CAR): Holds address of next microinstruction.

  • Sequencer Logic: Increments CAR, selects branch addresses based on condition bits from ALU or instruction decoder.

• Working: Output of CAR → CM address → CM outputs microinstruction → μIR. Sequencer logic uses condition bits and next-address field to load new address into CAR.

Instruction Formats & Addressing Modes

Instruction Format Design

An instruction typically has:

• Opcode: Specifies operation (e.g., ADD, LOAD). Number of bits = log₂(Number of instructions).

• Address Fields: Specifies operand location(s).

• Mode Bits: Specifies addressing mode.

• Example Calculation: 16-bit instruction, 6-bit opcode, 2-address format.

  • Address field size = (16 - 6) / 2 = 5 bits per address.

  • Max instructions = 2⁶ = 64.

  • Max addressable memory locations = 2⁵ = 32 locations.

Addressing Modes (with Examples)

CPU Registers & Common Bus System

• Key Registers:

  • PC (Program Counter): Holds address of next instruction.

  • IR (Instruction Register): Holds current instruction being executed.

  • MAR (Memory Address Register): Holds address for memory access.

  • MDR (Memory Data Register): Holds data to/from memory.

  • AC (Accumulator): Primary register for ALU operations.

  • General Purpose Registers (R1...Rn): For user data.

• Common Bus System: A single set of shared lines (bus) connects all registers, ALU, and memory.

  • Operation: A control signal (e.g., R1→BUS) enables a register's output onto the bus. Another signal (e.g., BUS→R2) loads bus data into a register.

  • Constraint: Only one source can drive the bus at a time. Requires multiplexers and careful timing.

III. Arithmetic Logic Unit (ALU)

Design of Arithmetic Circuits

• Half Adder: Adds 2 bits.

  • Sum = A ⊕ B, Carry = A·B.

  • Truth Table:

    | A | B | Sum | Carry | |---|---|---|---| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 0 | | 1 | 1 | 0 | 1 |

• Full Adder: Adds 3 bits (A, B, Cin).

  • Sum = A ⊕ B ⊕ Cin, Carry = (A·B) + (Cin·(A ⊕ B)).

  • Built from two Half Adders + OR gate.

Multiplication Algorithm & Circuit

• Sequential Multiplication (Add-and-Shift):

  1. Initialize Accumulator (AC) = 0, Multiplier (Q) in register, Multiplicand (M) in another.

  2. Check LSB of Q:

     • If 1: AC ← AC + M.

  3. Shift AC and Q right as one unit (arithmetic shift right for signed).

  4. Repeat for n bits (where n = bit width).

• Challenges:

  • Speed: Sequential, n clock cycles for n-bit multiplication.

  • Complexity: Need adders, shifters, control logic.

  • Partial Products: In array multipliers, many partial products to sum (area/power trade-off).

Floating-Point & Decimal Arithmetic

Floating-Point Representation (IEEE 754)

• Format: (-1)^S × (1.M) × 2^(E - Bias)

  • S: Sign bit (1 bit).

  • E: Biased exponent (8 bits single, 11 bits double). Bias = 127 (single), 1023 (double).

  • M: Fraction/Mantissa (23 bits single, 52 bits double). Leading 1 is implicit (normalized).

• Special Values:

  • E = 0, M = 0 → ±0.

  • E = all 1s, M = 0 → ±∞.

  • E = all 1s, M ≠ 0 → NaN (Not a Number).

Floating-Point Addition/Subtraction

1. Align Exponents: Shift mantissa of smaller exponent right until exponents match.

2. Add/Subtract Mantissas: Perform operation on aligned mantissas.

3. Normalize Result: Shift result left/right to restore leading 1. Adjust exponent.

4. Round: Apply rounding mode (e.g., round to nearest even).

5. Check for Underflow/Overflow.

[!TIP] The alignment step is critical and can cause loss of precision (catastrophic cancellation).

Decimal Arithmetic (BCD)

• BCD (Binary-Coded Decimal): Each decimal digit (0-9) represented by 4 bits (0000 to 1001).

• Addition: Add BCD numbers. If result > 9 or carry out, add 6 (0110) to correct.

• Use Case: Financial calculations where exact decimal precision is required.

IV. Memory System Organization

Memory Hierarchy

• Levels (Fast → Slow): Registers → L1/L2/L3 Cache → Main Memory (RAM) → Secondary Storage (SSD/HDD).

• Principle of Locality:

  • Temporal: Recently accessed items likely to be accessed again soon.

  • Spatial: Access to an address likely to be followed by access to nearby addresses.

• Significance: Exploits locality to make average access time close to fast memory speed while maintaining large, cheap slow memory capacity. Cost-performance trade-off.

Cache Memory

Organization & Purpose

• Purpose: Small, fast SRAM placed between CPU and main memory to reduce average memory access time (AMAT).

• Hit: Data found in cache.

• Miss: Data not in cache → fetch from main memory (slow).

Mapping Techniques

• Direct Mapping:

  • Each memory block maps to exactly one cache line (block).

  • Cache Index = (Block Address) mod (Number of Cache Blocks).

  • Tag stored in cache line to identify block.

  • Pros: Simple, cheap. Cons: High conflict misses.

• Set-Associative Mapping (e.g., 2-way):

  • Cache divided into sets (each set has k lines, here k=2).

  • Block maps to a specific set (like direct map), but can go into any line within that set.

  • Replacement Policy: LRU (Least Recently Used) needed within set.

  • Pros: Lower conflict misses than direct. Cons: More complex, slower.

• Fully Associative Mapping:

  • Block can map to any cache line.

  • Tag must be compared with all cache tags in parallel (content-addressable).

  • Replacement Policy: FIFO, LRU, Random.

  • Pros: Lowest conflict misses. Cons: Expensive, slow (full tag search).

Performance Calculation

• Hit Ratio (h): Fraction of memory accesses found in cache.

• Average Memory Access Time (AMAT):

$$ \text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty} $$

Where `Miss Rate = 1 - h`, `Miss Penalty` = time to fetch block from next level (main memory).

• Impact: Write misses may have different penalty (write-allocate vs. write-around).

Virtual Memory

• Concept: Gives each process its own large, contiguous virtual address space, larger than physical memory. Only active parts kept in RAM.

• Implementation (Paging):

  • Virtual memory divided into pages.

  • Physical memory divided into frames (same size as page).

  • Page Table: Maps virtual page number → physical frame number.

• Fragmentation:

  • Internal Fragmentation: Wasted space within allocated region (e.g., last page of a process not full). Exists in paging.

  • External Fragmentation: Wasted space between allocated regions (free memory in small, non-contiguous holes). Does NOT exist in paging (frames are non-contiguous).

Memory Mapping

• Concept: Assigning specific physical memory addresses to:

  1. Program code & data (for loading/execution).

  2. I/O device registers (for communication).

• Types:

  • Memory-Mapped I/O: I/O device registers appear as memory addresses. CPU uses regular load/store instructions to access devices. Simpler, but uses address space.

  • Isolated I/O: Separate I/O address space and special IN/OUT instructions. Protects memory space.

• Effect on Program Execution: Determines how OS loads program and how CPU accesses devices. Memory-mapped I/O allows device access via pointers.

V. Input/Output (I/O) Organization & Data Transfer

Data Transfer Modes

DMA Performance Analysis (CPU Overhead)

• Overhead Cycles = Cycles to initiate DMA + Cycles for interrupt handling at completion.

• Fraction of CPU Time = $$\displaystyle \frac{\text{Overhead Cycles per Transfer}}{\text{Total Cycles during Transfer}} $$

• Example: Transfer 10 MB as 2500 pages (4 KB each). CPU 200 MHz. Initiation = 1000 cycles, Interrupt = 1500 cycles.

  • Total overhead per page = 1000 + 1500 = 2500 cycles.

  • Total overhead for 2500 pages = 2500 × 2500 = 6,250,000 cycles.

  • Time for DMA transfer of 10 MB at 10 MB/s = 1 second.

  • Total CPU cycles in 1 sec = 200 × 10⁶ = 200,000,000.

  • Fraction = 6.25e6 / 200e6 = 0.03125 (3.125%).

I/O Processor (IOP)

• Role: A specialized processor (often a microcontroller) dedicated to managing I/O operations for one or more devices.

• Operation:

  • CPU loads IOP with I/O program (list of commands, memory addresses, counts).

  • IOP executes program asynchronously, handling data transfers, error checking, etc.

  • IOP interrupts CPU only on completion or error.

• Benefit: Offloads I/O management from main CPU, allowing CPU to focus on computation. Used in modern systems (e.g., disk controllers, GPUs).

Data Transfer Communication

Synchronous vs. Asynchronous Transfer

Duplex Modes

• Half-Duplex: Data can flow in only one direction at a time (e.g., walkie-talkie, old Ethernet).

• Full-Duplex: Data can flow in both directions simultaneously (e.g., telephone, modern Ethernet, PCIe).

I/O Interface

• Role: Electronic circuitry (often part of IOP or chipset) that:

  1. Converts CPU bus signals to device-specific signals.

  2. Provides data buffering (to match speed differences).

  3. Implements handshaking protocol (REQ, ACK).

  4. May perform format conversion (serial/parallel).

VI. Performance Enhancement & Parallelism

Instruction Pipelining

• Principle: Overlap execution of multiple instructions by dividing the instruction cycle into stages (segments). Each stage works on a different instruction simultaneously.

• Four-Segment Pipeline Example:

  1. F (Fetch): Get instruction from memory.

  2. D (Decode): Decode opcode, read registers.

  3. E (Execute): Perform ALU operation.

  4. W (Write): Write result back to register/memory.

• Advantages:

  • Increased Throughput: Ideally n-stage pipeline gives n-fold speedup.

  • Better resource utilization.

• Limitations & Hazards:

  • Structural Hazards: Resource conflict (e.g., two instructions need memory in same cycle). Solution: Separate instruction/data caches.

  • Data Hazards: Instruction depends on result of previous instruction not yet available.

    • Forwarding/Bypassing: Route result directly from EX stage to next instruction's EX input.

    • Stall/Bubble: Insert no-op cycles.

  • Control Hazards: Caused by branches/jumps. Next instruction unknown until branch resolved.

    • Solutions: Branch delay slots, branch prediction.

• Speedup: $$\displaystyle S = \frac{n}{(k + n - 1)} $$ for n instructions in k-stage pipeline (ideal case: $S ≈ k$ for large n).

Vector Processing

• Concept: Process entire vectors (arrays) with a single instruction. Contrast with scalar processing (one data item per instruction).

• Organization:

  • Vector Registers: Long registers holding multiple data elements (e.g., 64 elements).

  • Vector Functional Units: Pipelined ALUs that operate on entire vectors in one instruction.

  • Example: VADD V1, V2, V3 → V1[i] = V2[i] + V3[i] for all i.

• Application Areas: Scientific computing (matrix ops), computer graphics (transformations), media processing (audio/video codecs).

Multiprocessor Systems

• Inter-Processor Communication:

  • Shared Memory: All processors access common physical memory. Communication via reads/writes to shared variables. Requires cache coherence protocols (e.g., MESI).

  • Message Passing: Processors have private memory. Communicate by sending explicit messages over a network. Scalable, but programming model different.

• MIMD (Multiple Instruction, Multiple Data):

  • Architecture: Multiple independent processors, each executing its own instruction stream on its own data.

  • Types:

    • Symmetric Multiprocessing (SMP): All processors share memory and OS; peers.

    • Asymmetric Multiprocessing: One master CPU controls others (slaves).

VII. Advanced & Special Topics

Associative Memory

• Concept: Content-Addressable Memory (CAM). Data is accessed by content (search key) rather than by address.

• Operation: Entire memory searched in parallel. Returns address(es) where match occurs.

• Difference from Cache:

  • Cache: Small, fast, address-based access. Goal: Reduce average access time to main memory.

  • Associative Memory: Used for fast search/lookup (e.g., TLB in virtual memory, network router tables). Access is by content.

RISC (Reduced Instruction Set Computer)

• Key Characteristics:

  • Fixed-length instructions (e.g., 32 bits).

  • Load/Store Architecture: Only load/store instructions access memory. ALU ops only on registers.

  • Simple addressing modes (typically only register indirect and immediate).

  • Large register file (≥ 16 general-purpose registers).

  • Hardwired control (often).

  • Single-cycle execution for most instructions (in classic RISC).

• Contrast with CISC:

  • CISC: Variable-length instructions, memory-to-memory ops, many addressing modes, microprogrammed control, goal: reduce # of instructions per program.

Interconnection Structures

• Bus: Shared communication pathway. Simple, but contention limits bandwidth. Requires arbitration.

• Crossbar Switch: Dedicated path between any source-destination pair. Non-blocking, fast, but expensive (O(n²) switches for n ports).

• Multistage Networks (e.g., Omega, Butterfly): Hierarchical switches. Cheaper than crossbar, but may have blocking.

Floating-Point Unit (FPU) Design Considerations

• Special Values: Must handle ±0, ±∞, NaN correctly per IEEE 754 (e.g., 1/0 = ∞, 0/0 = NaN).

• Rounding Modes: Round to nearest (even), toward zero, toward +∞, toward -∞.

• Precision: Single (32-bit), Double (64-bit), Extended (80-bit). Trade-off between range/precision and speed/area.

• Pipeline: FP operations are multi-cycle; often deeply pipelined (e.g., ADD: 3-4 stages, MUL: 5-7 stages).