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

UNIT 4: COMPUTER SYSTEM ORGANIZATION

1. FUNDAMENTAL COMPUTER ARCHITECTURE

Von Neumann Model

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

• Key Components:

  • Memory: Stores both data and instructions.

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

  • Arithmetic Logic Unit (ALU): Performs arithmetic/logic operations.

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

  • System Bus: Shared communication pathway (Address, Data, Control).

• Instruction & Data Processing: Sequential Fetch-Decode-Execute cycle. The CU fetches an instruction from memory (using PC), decodes it, fetches operands (from memory/registers), executes via ALU, and writes back results.

  [!TIP] The bottleneck in Von Neumann architecture is the single bus for both data and instructions, known as the Von Neumann bottleneck.

Instruction Cycle & Micro-operations

• Phases (Classic 5-stage):

  1. Instruction Fetch (IF): MAR ← PC, MDR ← Memory[MAR], IR ← MDR, PC ← PC + 1

  2. Instruction Decode/Operand Fetch (ID/OF): Decode opcode in IR. Fetch operands from registers/memory.

  3. Execute (EX): ALU performs operation (e.g., ADD, AND).

  4. Memory Access (MEM): Read/write data from/to memory (for LOAD/STORE).

  5. Write-back (WB): Write result from ALU or MDR to destination register.

• 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 be written to or read from memory.

• Micro-operations: Elementary operations on data stored in registers (e.g., R1 ← R1 + R2).

• Register Transfer Language (RTL): Symbolic notation to describe micro-operations.

  • Example: R2 ← R1 + M[AR] means add the contents of register R1 to the memory word at address in AR, and load result into R2.

Common Bus System & Interconnection Structures

• Purpose: Enables multiple components (registers, memory, ALU) to share a single set of communication lines.

• Operation: Uses multiplexers to select which component's output drives the bus. Control signals (S0, S1, etc.) select the source. BUS ← R1 means R1's output is enabled onto the bus.

• Block Diagram: Registers connected to a common bus via tri-state buffers/gates. The ALU and memory also connect to the bus. Control signals from CU manage data flow.

• Application: Used in basic computer design, I/O systems, and simple multiprocessors for cost-effective communication.

  [!TIP] In a common bus, only one source can drive the bus at a time to prevent data collision.

2. INSTRUCTION FORMAT & ADDRESSING MODES

Instruction Format Design

• Components:

  • Opcode: Specifies the operation (e.g., ADD, LOAD). Number of bits n allows 2^n distinct instructions.

  • Address Fields: Specify operands (memory location or register). Number of bits a allows 2^a addressable locations.

  • Mode Bits: Specify addressing mode.

  • Immediate Data: Constant operand embedded in instruction.

• Common Formats:

  • Zero-address (Stack): OP (e.g., PUSH, POP). Operands from stack.

  • One-address: OP addr1 (Accumulator implied as other operand).

  • Two-address: OP addr1, addr2 (Result often overwrites addr1).

  • Three-address: OP addr1, addr2, addr3 (Most flexible, larger instruction size).

• Bit Allocation Example:

  For a 16-bit instruction with 6-bit opcode and a 2-address format:

  • Distinct instructions: 2^6 = 64.

  • If each address field is 5 bits: Addressable memory locations = 2^5 = 32.

Addressing Modes

[!TIP] Immediate vs. Direct: Immediate has the value in instruction; Direct has the address of the value.

3. CONTROL UNIT DESIGN

Hardwired Control Unit

• Design: Uses combinational logic (decoders, gates, flip-flops) to generate control signals directly from the instruction decoder output and timing (clock) signals.

• Operation: A state machine. Each instruction and each time step (T1, T2,...) within its execution defines a unique combination of control signals.

• Boolean Expressions: Control signals are functions of instruction bits and time. Example: S5 = I1·T2 + I3·T1 + I4·T4.

• Advantages: Fast (no memory access for microcode), efficient for simple ISAs.

• Disadvantages: Complex, inflexible wiring. Difficult to modify or add new instructions.

Microprogrammed Control Unit

• Concept: Control signals are stored as microinstructions in a Control Memory (CM). The CU's job is to sequence through this microprogram.

• Micro-instruction Format:

  • Control Field: Bits that directly activate control signals (parallel micro-ops).

  • Next Address Field: Specifies address of next microinstruction (can be sequential or branch).

  • Branching/Decision Logic: Conditions for branching (e.g., based on ALU flags).

• Encoding Techniques:

  • Horizontal: One bit per control signal. Max parallelism, but very wide (many bits).

  • Vertical: Encoded fields (e.g., 3 bits for 8 signals). Compact, but limited parallelism per cycle.

  • Field-encoded: Groups of mutually exclusive signals encoded together (balance between horizontal and vertical).

• Microprogram Sequencer:

  • Generates address of next microinstruction.

  • Block Diagram: Contains a microprogram counter (μPC), logic for incrementing, multiplexers for branch addresses, and logic for conditional branching (using condition codes).

  • Operations: Increment (μPC+1), unconditional branch (load new address), conditional branch (based on test).

• Advantages: Flexible, easy to design/debug/modify (change microcode). Handles complex ISAs well.

• Disadvantages: Slower (extra memory access per microinstruction).

Comparison: Hardwired vs. Microprogrammed

[!TIP] Hybrid approach: Use hardwired for common/fast paths, microprogrammed for complex/rare instructions.

4. ARITHMETIC & LOGIC UNIT (ALU) OPERATIONS

Basic Arithmetic Circuits

• Half-Adder (HA): Adds 2 bits.

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

  • Truth Table & Logic Diagram.

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

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

  • Built from 2 HAs or direct logic.

• Binary Addition/Subtraction (2's Complement):

  • Addition: Straight binary addition. Discard carry-out.

  • Subtraction (A - B): A + (2's complement of B). Invert B bits, add 1.

Multiplication Algorithm & Circuit

• Sequential (Add-and-Shift) Algorithm:

  1. Initialize product = 0.

  2. If LSB of multiplier is 1, add multiplicand to product.

  3. Shift product and multiplier right (arithmetic shift for signed).

  4. Repeat for n bits.

• Hardware Challenges:

  • Speed: Sequential is slow. Parallel (array multiplier) is faster but complex.

  • Partial Products: Need to generate and sum many partial products ( Booth's algorithm reduces this).

  • Accumulation: Large adder needed for summing partial products.

  • Sign Handling: Must correctly handle signed numbers (2's complement).

Floating-Point Representation & Arithmetic (IEEE 754)

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

  • S: Sign bit (0=+, 1=-).

  • E: Biased exponent (Bias = 127 for single, 1023 for double).

  • M: Fraction/Mantissa (implicit leading 1 for normalized numbers).

• Normalization: Shift number to form 1.xxxxx × 2^E. Adjust exponent accordingly.

• Rounding: Modes (Round to nearest even, toward zero, etc.).

• Addition/Subtraction Flowchart:

  1. Align Exponents: Shift the number with smaller exponent right until exponents equal. (Loss of precision).

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

  3. Normalize Result: Shift left/right to restore 1.xxxxx form. Adjust exponent.

  4. Round: Apply rounding to the mantissa.

  5. Check for Underflow/Overflow.

• Comparison: More complex than fixed-point due to exponent alignment and normalization. Handles wide dynamic range.

5. INPUT/OUTPUT (I/O) ORGANIZATION & DATA TRANSFER

I/O Interface & Peripheral Devices

• Role: Acts as a translator and buffer between CPU/memory and I/O devices.

• Functions:

  • Data Buffering: Match speed differences (using registers/FIFOs).

  • Signal Conversion: Voltage levels, serial/parallel conversion.

  • Timing & Control: Handshaking signals (READY, ACK).

  • Device Selection: Decoding address to select specific I/O port.

• I/O Ports: Addressable locations in I/O interface (Memory-Mapped I/O vs. Isolated I/O).

Data Transfer Modes

Asynchronous vs. Synchronous Data Transfer

• Synchronous: Events occur at fixed intervals defined by a global clock. Simple, but all devices must operate at same speed or use wait states.

• Asynchronous: Uses handshaking signals.

  • Strobe: One-way pulse (e.g., source sends data + strobe).

  • Ready/ACK (Two-way): Source sends data, then waits for READY from destination. More reliable for variable-speed devices.

I/O Processor (IOP)

• Definition: A dedicated processor (like a small CPU) that manages I/O operations for one or more devices.

• Role: Offloads I/O tasks from main CPU. Handles device-specific protocols, data formatting, error checking, and can perform simple processing (e.g., disk controller).

• Block Diagram: IOP connects to system bus (like CPU) and to I/O devices via its own buses/controllers. Communicates with CPU via interrupts and shared memory (dual-port RAM).

• Benefit in Asynchronous Transfer: IOP can handle slow device timing independently, using its own control logic, freeing main CPU.

Duplex Communication Modes

6. MEMORY HIERARCH & CACHE MEMORY

Memory Hierarchy Concept

• Principle: Organize memory into levels (Registers → L1/L2/L3 Cache → Main Memory → Disk) based on speed, size, cost.

• Locality of Reference:

  • Temporal: Recently accessed items likely soon again.

  • Spatial: Access to an address likely accesses nearby addresses.

• Significance: Exploits locality to create an illusion of large, fast, cheap memory. Reduces Average Memory Access Time (AMAT) significantly.

Cache Memory Organization

• Purpose: Small, fast SRAM buffer between CPU and slower main memory (DRAM). Stores copies of frequently used memory blocks.

• Mapping Techniques:

  • Direct Mapping:

    • Each memory block maps to exactly one cache line (index = Block number mod #cache blocks).

    • Tag stored in cache line identifies which memory block is present.

    • Formula: Cache Index = (Memory Block Number) mod (Number of Cache Blocks)

    • Example: 16-block cache. Memory block 37 → Cache line 37 mod 16 = 5.

  • Associative Mapping:

    • Fully Associative: Memory block can go in any cache line. Requires searching all tags (parallel comparators). Flexible but expensive.

    • Set-Associative (e.g., N-way): Cache divided into sets. Block maps to a specific set (like direct), but can be placed in any line within that set (N lines/set). N=1 = direct, N=#blocks = fully associative. 2-way is common.

    • Replacement Policy: When set is full, choose victim (LRU, FIFO, Random). LRU (Least Recently Used) is common.

  • Example Problem: Given access sequence A, B, C, D, A, B, E, A, B, C, D, E and 4-block direct cache: Simulate to count hits/misses.

Write Policies

• Write-through: Data written to both cache and main memory simultaneously. Simple, consistent. Slow (writes go to DRAM).

• Write-back: Data written only to cache. A dirty bit marks modified blocks. Written to memory only when evicted. Faster writes, but complex (need write-back on eviction).

Cache Performance Metrics

• Hit Ratio (HR): Fraction of accesses found in cache. HR = Hits / Total Accesses.

• Miss Rate (MR): MR = 1 - HR.

• Average Memory Access Time (AMAT):

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

*   **Hit Time:** Time to access cache (typically 1-4 cycles).

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

> [!TIP] **AMAT Calculation Example:** Hit Time = 100 ns, Miss Penalty = 10,000 ns, HR=0.95 → `AMAT = 100 + 0.05 × 10000 = 600 ns`.

Virtual Memory & Paging

• Concept: Gives each process the illusion of a large, contiguous private address space. Physical memory (RAM) is used as a cache for disk.

• Paging:

  • Logical (Virtual) Address: [Page Number | Offset]

  • Physical Address: [Frame Number | Offset]

  • Page Table: Maps virtual pages to physical frames. Stored in memory (or TLB cache).

  • Page Fault: Occurs when accessed page not in physical memory. OS brings page from disk (high cost).

• Benefits: Larger address space than RAM, memory protection (permissions in page table), simplified allocation (no external fragmentation).

• Fragmentation:

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

  • External Fragmentation: Wasted space between allocated regions (occurs in segmentation, not pure paging).

Associative Memory (Content-Addressable Memory - CAM)

• Operation: Access by content (data value), not by address. All entries searched in parallel.

• Difference from Cache:

  • Purpose: CAM used for fast lookup/search (e.g., TLB, router tables). Cache used to reduce average access time to a larger memory.

  • Access: CAM is associative search (given data, find address). Cache is address-based (given address, find data).

  • Organization: CAM stores (key, value) pairs; hardware compares input key with all stored keys simultaneously.

7. ADVANCED PROCESSING TECHNIQUES

Instruction Pipelining

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

• Basic 5-Stage Pipeline (RISC):

  1. IF: Instruction Fetch from memory.

  2. ID: Instruction Decode & Register Fetch.

  3. EX: Execute / Calculate address.

  4. MEM: Memory Access (read/write).

  5. WB: Write result back to register.

• Advantages: Increased throughput (Ideally 1 instruction/cycle after fill). Reduced CPI (Cycles Per Instruction).

• Limitations/Hazards:

  • Structural: Resource conflict (e.g., two instructions need memory in same cycle). Solution: Duplicate resources.

  • Data Hazards: Dependency between instructions.

    • RAW (Read After Write): True dependency. Solution: Forwarding/Bypassing (EX result to next instruction's EX input), Stalling (bubbles).

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

  • Control Hazards: Caused by branches/jumps. Next instruction unknown until branch resolved. Solution: Branch delay slots, Branch prediction, Speculative execution.

• Pipeline Performance: Speedup ≤ Number of stages. Affected by hazards (stalls) and imbalance between stage times.

Vector Processing

• Scalar vs. Vector:

  • Scalar: Processes one data element per instruction (e.g., ADD R1, R2).

  • Vector: Instructions operate on entire vectors/arrays (e.g., VADD V1, V2, V3 adds corresponding elements of three vectors).

• Vector Processors: Have pipelined functional units (add, multiply) that can start a new operation every cycle. Use vector registers (hold multiple elements) and vector instructions.

• Applications: Scientific computing, matrix operations, signal processing, multimedia (pixel operations). High throughput for data-parallel tasks.

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 messages via network (e.g., buses, switches). No shared memory, explicit send/receive.

• Interconnection Structures:

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

  • Crossbar Switch: Dedicated paths between any pair. High cost, complex.

  • Multi-stage Networks (e.g., Omega, Butterfly): Logarithmic depth, scalable.

• UMA vs. NUMA:

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

  • NUMA (Non-Uniform Memory Access): Memory physically distributed. Access time depends on location of memory relative to processor. Used in large-scale systems.

• MIMD (Multiple Instructions, Multiple Data): Most common multiprocessor type. Each processor fetches its own instruction stream and operates on its own data stream. Includes both shared-memory and distributed-memory systems.