Computer System Organization (EC-504 (B)) - Unit 5 Short Notes

UNIT 5: COMPUTER SYSTEM ORGANIZATION

I. FUNDAMENTAL COMPUTER STRUCTURE & MODELS

Von Neumann Architecture (Princeton Architecture)

• Core Idea: Stored-program concept – both instructions and data reside in the same main memory.

• Key Components:

  • Memory: Stores both data and instructions.

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

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

  • Input/Output (I/O) Equipment: For external communication.

  • System Bus: Shared pathway for data, addresses, and control signals.

• Handling: A single bus is used for transferring both instructions and data, leading to the "Von Neumann bottleneck" – limited bandwidth between CPU and memory.

• Significance: Foundation of most modern computers. Defines the basic fetch-decode-execute cycle.

[!TIP] Exam Focus: Be prepared to draw the block diagram and explain the bottleneck. Contrast with Harvard architecture (separate memories for instructions/data).

Computer Block Diagram & Common Bus System

• Registers & Their Functions:

  • MAR (Memory Address Register): Holds address for memory read/write.

  • MDR (Memory Data Register): Holds data being read from or written to memory.

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

  • IR (Instruction Register): Holds the currently fetched instruction.

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

  • General-Purpose Registers (R0...Rn): For operands and results.

• Common Bus: A set of shared lines (data, address, control). Multiplexers select which register connects to the bus.

• Bus Arbitration: Mechanism (e.g., using a bus arbiter) to decide which master (CPU, DMA, etc.) controls the bus when multiple requests exist.

[!DIAGRAM: CANVAS] Draw: A block diagram showing CPU (CU, ALU), registers (PC, IR, MAR, MDR, AC, GPRs), main memory, and I/O, all connected via a common system bus with multiplexers on register inputs.

II. INSTRUCTION EXECUTION CYCLE & CONTROL

Instruction Cycle Phases

1. Fetch: PC -> MAR -> Memory -> MDR -> IR. PC is incremented.

2. Decode: Control unit decodes opcode in IR. Determines operation, addressing mode, and required operands.

3. Execute: CU activates control signals to perform the operation (e.g., AC <- AC + MDR). May involve:

   • Memory Access: For load/store instructions.

   • Write-back: Storing result to a register or memory.

4. Interrupt Check: After execution, before next fetch, check for interrupts.

[!TIP] Exam Focus: Know the micro-operations for each phase. A flowchart is a common question.

Control Unit Design Comparison

[!TIP] Exam Focus: Be ready to draw a simplified block diagram for both. The microprogram sequencer (with micro-PC and address logic) is key for microprogrammed control.

Micro-operations & Register Transfer Language (RTL)

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

• Types:

  • Register Transfer: Move data between registers (R2 <- R1).

  • Memory Transfer: Between register and memory (M[AR] <- MDR).

  • Bus Transfer: Data movement onto/off the bus.

• RTL: Symbolic notation to describe micro-operations. Example: AR <- (PC) + 1 (increment PC and load into AR).

• Significance: Provides a formal language to describe the sequence of control signals needed for an instruction, forming the basis for both hardwired logic equations and microprograms.

III. INSTRUCTION SET ARCHITECTURE & ADDRESSING

Instruction Formats

• Length: Fixed (simpler CU, faster decode) vs. Variable (more compact code).

• Address Fields:

  • 0-address: Stack-based (e.g., ADD).

  • 1-address: Accumulator-based (e.g., ADD M).

  • 2-address: ADD R1, R2 (R1 <- R1 + R2).

  • 3-address: ADD R1, R2, R3 (R1 <- R2 + R3).

• Bit Allocation: #bits(opcode) + #bits(addr1) + #bits(addr2) + #bits(mode) = Total instruction length.

  • Calculation Example: 16-bit instruction, 6-bit opcode, 2-address format. Addresses + mode bits = 10 bits. If mode=2 bits, each address = 4 bits → 2^4 = 16 addressable locations.

Addressing Modes

[!TIP] Exam Focus: Know definitions and give an example for each. PC-relative and Indexed are frequently asked.

IV. ARITHMETIC & LOGIC UNIT (ALU) DESIGN

Basic Arithmetic Circuits

• Half Adder: 2 inputs (A,B), outputs Sum (A⊕B) and Carry (A·B).

• Full Adder: 3 inputs (A,B,Cin), outputs Sum (A⊕B⊕Cin) and Carry (AB + BCin + ACin).

• n-bit Adder: Chain of full adders (Ripple Carry) or use carry-lookahead for speed.

• Subtractor: A - B = A + (2's complement of B). Use adder with B_inverted and Cin=1.

• Multiplication (Shift-and-Add):

  
  Initialize Product = 0
  
  For each bit of multiplier (LSB to MSB):
  
      If bit == 1: Product = Product + (Multiplicand << position)
  
      Shift Multiplicand left by 1
  
  

  • Challenges: Partial product generation/accumulation, high propagation delay for large operands, area/power trade-offs. Array multipliers are faster but use more hardware.

Floating-Point Arithmetic (IEEE 754)

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

  • Single (32-bit): 1 sign bit, 8 exponent (bias=127), 23 mantissa bits.

  • Double (64-bit): 1 sign bit, 11 exponent (bias=1023), 52 mantissa bits.

• Addition/Subtraction Flowchart:

  1. Align Exponents: Shift smaller operand's mantissa right until exponents equal.

  2. Add/Subtract Mantissas: Based on sign bits.

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

  4. Round: Using guard, round, sticky bits.

  5. Check for Special Cases: Overflow, underflow, zero, NaN, infinity.

• Special Values: Zero (all bits 0), Denormalized (exp=0, leading 0), Infinity (exp all 1s, mantissa 0), NaN (exp all 1s, mantissa ≠0).

[!DIAGRAM: CANVAS] Draw: The 4-step flowchart for floating-point addition: 1. Align exponents, 2. Add mantissas, 3. Normalize, 4. Round.

V. INPUT/OUTPUT ORGANIZATION & DATA TRANSFER

I/O Interface & Modes of Data Transfer

• I/O Interface Role: Handles signal conversion (voltage/level), buffering, timing coordination (handshaking), and data format conversion between CPU/IOP and devices.

• Data Transfer Modes Comparison:

• Synchronous vs. Asynchronous:

  • Synchronous: Data transfer timed by a common clock. Fast, but devices must operate at same speed.

  • Asynchronous: Uses handshaking signals (e.g., STB, ACK). Flexible, devices can operate at different speeds.

• Duplex Modes:

  • Half-duplex: Communication in one direction at a time (e.g., walkie-talkie).

  • Full-duplex: Simultaneous two-way communication (e.g., telephone).

DMA Controller

• Purpose: Offload bulk data transfer from CPU.

• Typical Registers:

  • DR (Data Register): Holds data being transferred.

  • AR (Address Register): Holds memory address.

  • DC (Data Count): Number of words to transfer.

  • TC (Terminal Count): Flag set when DC=0.

• Operation:

  1. CPU initializes DMA (sets AR, DC, control bits).

  2. DMA takes control of bus (cycle stealing or burst mode).

  3. DMA transfers data between I/O device and memory directly.

  4. DMA raises interrupt upon completion (TC=1).

• Calculation Example (From Nov 2022):

  • CPU time = (Initiation cycles + Interrupt cycles) / Total cycles.

  • Given: 1000 cycles to init, 1500 cycles for interrupt, 2500 pages of 4KB each = 10MB total.

  • Transfer time on bus = Data size / Bus bandwidth = 10MB / 100MB/s = 0.1s.

  • CPU cycles during transfer = 0.1s × 200MHz = 20,000,000 cycles.

  • Total CPU cycles involved = 1000 + 1500 = 2500.

  • Fraction of CPU time = 2500 / (20,000,000 + 2500) ≈ 0.000125 or 0.0125%.

[!DIAGRAM: CANVAS] Draw: DMA controller block diagram showing connections to CPU (control, address, data buses), memory (address, data buses), and I/O device (data lines). Label DR, AR, DC, TC registers and control logic.

I/O Processor (IOP)

• Role: A dedicated processor (like a small CPU) that manages I/O operations for one or more devices. Offloads I/O tasks completely from main CPU.

• Operation: Executes its own I/O instructions. Communicates with main CPU via memory or messages (e.g., mailbox). Used in modern systems (e.g., disk controllers, GPUs).

VI. MEMORY SYSTEM ORGANIZATION

Memory Hierarchy

• Principle of Locality:

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

  • Spatial: Access to an item likely to lead to access to nearby items.

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

• Significance: Exploits locality to provide large, cheap, slow memory with performance approaching small, fast, expensive memory. Optimizes cost/performance.

Cache Memory

• Organization:

  • Cache Size (C): Total storage capacity.

  • Block/Line Size (B): Smallest unit transferred between cache and memory (e.g., 64 bytes).

  • Number of Blocks: C / B.

  • Address Format: [Tag] [Index] [Block Offset].

• Mapping Techniques:

• Performance Metrics:

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

  • Miss Ratio (MR) = 1 - HR.

  • Average Memory Access Time (AMAT):

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

    *   `Hit Time`: Time for cache access.

    *   `Miss Penalty`: Time to fetch block from lower level (main memory + transfer).

*   **Write Policies:**

    *   **Write-through:** Write to cache **and** memory simultaneously. Simple, consistent. High memory traffic.

    *   **Write-back:** Write only to cache. Mark block "dirty". Write to memory only when evicting. Lower traffic, complex.

• Cache vs. Associative Memory (CAM):

  • Cache: Maps memory address to cache location (by index). Search by index.

  • CAM (Content-Addressable Memory): Search by content (data). Used for fast lookups (e.g., TLBs, network switches). Hardware is more complex and power-hungry.

[!TIP] Exam Focus: AMAT calculation is mandatory. Know how to calculate index/tag bits for direct/associative mapping. Example (Nov 2022): Cache 8KB, B=64B → #blocks=128 → Index needs 7 bits.

Virtual Memory & Paging

• Concept: Gives each process the illusion of a large, contiguous private address space. Only active parts need be in physical memory (RAM).

• Implementation (Paging):

  • Virtual Address (VA): [Virtual Page Number (VPN) | Page Offset].

  • Physical Address (PA): [Physical Frame Number (PFN) | Page Offset].

  • Page Table: OS-maintained table mapping VPN → PFN. Stored in memory.

  • Page Fault: Occurs when VPN not in page table (not in RAM). OS fetches page from disk (swap space) into a free frame.

• Fragmentation:

  • Internal: Wasted space within allocated region (e.g., last page of a process). Fixed by variable page sizes.

  • External: Wasted space between allocated regions (in physical memory). Solved by paging (no external frag).

Memory Mapping

• Memory-Mapped I/O: I/O device registers appear as memory locations in the address space. CPU uses LOAD/STORE to access devices. Simple, uniform.

• Isolated (Port-Mapped) I/O: Separate IN/OUT instructions. Dedicated I/O address space. Clearer separation, but requires special instructions.

• Significance: Determines how CPU communicates with devices. Memory-mapped I/O allows using all memory addressing modes for I/O.

VII. ADVANCED PROCESSOR ARCHITECTURES

Instruction Pipelining

• Basic Structure: Divide instruction execution into sequential segments (stages). Each stage works on a different instruction simultaneously.

  • Typical 5-stage RISC Pipeline:

    1. IF (Instruction Fetch): PC -> IR, PC <- PC+4

    2. ID (Instruction Decode): Decode opcode, read registers.

    3. EX (Execute): ALU operation (e.g., R1 + R2).

    4. MEM (Memory Access): Read/write data memory.

    5. WB (Write Back): Write result to destination register.

• Advantage: Increased Throughput (Instructions Per Cycle, IPC). Ideal speedup ≈ number of stages.

• Hazards & Mitigation:

  • Structural: Resource conflict (e.g., two instructions need memory in MEM stage). Mitigation: Duplicate resources (separate instruction/data caches).

  • Data Hazards: Dependency between instructions.

    • RAW (Read-After-Write): Most common. Mitigation: Forwarding/Bypassing (result from EX/MEM stage fed directly to next instruction's EX input), Stalling (insert bubbles).

    • WAR (Write-After-Read), WAW (Write-After-Write): Occur in out-of-order execution.

  • Control Hazards: Caused by branches/jumps. Mitigation: Branch Delay Slot (execute instruction after branch regardless), Branch Prediction (static/dynamic), Speculative Execution.

[!DIAGRAM: CANVAS] Draw: A 5-stage pipeline diagram showing 4 instructions (I1, I2, I3, I4) progressing through IF, ID, EX, MEM, WB stages in parallel cycles.

Vector Processing (SIMD)

• Concept: Single instruction operates on entire vectors (arrays of data) simultaneously. Single Instruction, Multiple Data.

• Organization: Requires vector registers (large, hold multiple elements), vector functional units (pipelined ALUs), and strided memory access.

• Comparison with Scalar: Scalar processes one data element per instruction. Vector achieves high throughput for data-parallel tasks (scientific simulations, image processing, ML).

• Modern Form: SIMD extensions in CPUs (SSE, AVX, NEON) where a single register holds multiple packed values (e.g., 4 floats, 8 shorts).

Multiprocessor Systems

• Inter-Processor Communication:

  • Shared Memory: Processors communicate by reading/writing common memory locations. Requires cache coherence protocols (e.g., MESI).

  • Message Passing: Processors send explicit messages over a network. Used in distributed memory systems (clusters).

• Flynn's Taxonomy:

  • SISD: Single Instruction, Single Data (uniprocessor).

  • SIMD: Single Instruction, Multiple Data (vector, GPU cores).

  • MISD: Multiple Instruction, Single Data (rare, fault tolerance).

  • MIMD: Multiple Instruction, Multiple Data (most multiprocessors, multi-cores).

• MIMD Architectures:

  • UMA (Uniform Memory Access): All processors have equal access time to shared memory (SMP - Symmetric Multiprocessing).

  • NUMA (Non-Uniform Memory Access): Access time depends on memory location relative to processor (local vs. remote memory).

• Interconnection Networks: Connect processors/memory.

  • Shared Bus: Simple, but bandwidth-limited, contention.

  • Crossbar: Dedicated paths, non-blocking, expensive.

  • Multistage (e.g., Omega, Butterfly): Scalable, uses switches in stages.

[!TIP] Exam Focus: Differentiate UMA vs. NUMA. Know the 4 Flynn's classes with examples. Be able to draw a simple crossbar or multistage network.

RISC vs. CISC (Brief)

• CISC (Complex Instruction Set Computer): Many complex instructions (e.g., string ops, complex addressing). Variable length. Microprogrammed control. Goal: Reduce program size (memory was expensive). Example: x86.

• RISC (Reduced Instruction Set Computer): Few, simple, fixed-length instructions. Load/store architecture (only load/store access memory). Hardwired control. Many general-purpose registers. Goal: Increase IPC via pipelining. Example: ARM, MIPS, RISC-V.

• Modern Convergence: Modern CISC (x86) internally translates to RISC-like micro-ops. RISC ISAs have added some complex instructions (e.g., atomic ops).

Final Exam Checklist:

• [ ] Draw & explain Von Neumann model.

• [ ] Write micro-operations for instruction fetch/decode/execute.

• [ ] Compare hardwired vs. microprogrammed control (pros/cons, diagram).

• [ ] Calculate cache mapping (index/tag bits) and AMAT.

• [ ] Explain DMA operation and calculate CPU overhead.

• [ ] Describe pipeline stages, hazards, and solutions.

• [ ] Define all addressing modes with examples.

• [ ] Explain floating-point addition steps.

• [ ] Differentiate UMA/NUMA, SIMD/MIMD, synchronous/asynchronous, half/full-duplex.