Computer Architecture (IT-402) - Unit 1 Short Notes

UNIT 1: COMPUTER ARCHITECTURE - COMPREHENSIVE NOTES

I. FOUNDATIONS & BASIC ORGANIZATION

A. Evolution of Computer Generations

[!TIP] Exam Focus: Link each generation's tech to modern features (e.g., transistor → VLSI → multi-core; batch → interactive → cloud).

B. Basic Computer Organization & Architecture

• Von Neumann Architecture (Stored Program Concept):

  • Key Idea: Instructions and data stored in the same memory unit.

  • Diagram:

    DiagramCANVAS: Central Processing Unit (CPU) with Control Unit (CU) and Arithmetic Logic Unit (ALU), connected via System Bus to a single Memory unit containing both instructions and data. I/O devices also connected via bus.

  • Limitation: Von Neumann Bottleneck – single bus limits data/instruction fetch rate.

• Major Functional Units:

  1. CPU: Fetches, decodes, executes instructions (CU + ALU + Registers).

  2. Memory: Stores instructions/data (Hierarchy: Registers → Cache → Main → Secondary).

  3. I/O: Communicates with external world (Keyboard, Disk, Display).

  4. System Interconnection (Buses): Shared communication pathways (Address, Data, Control).

• Architecture vs. Organization:

  • Architecture (ISA): What the system does (Instruction set, registers, memory model). Visible to programmer.

  • Organization: How it's implemented (Control signals, memory tech, pipeline). Hidden from programmer.

[!TIP] Common Pitfall: Confusing ISA (e.g., x86, ARM) with microarchitecture (e.g., Intel Core, Apple M1). Same ISA can have different organizations.

II. DATA REPRESENTATION & ARITHMETIC

A. Fixed-Point Number Representations

[!TIP] 2's Complement is dominant because it simplifies ALU design (no need for separate subtractor). Always convert subtraction to addition: A - B = A + (2's comp of B).

B. Floating-Point Representation (IEEE 754 Standard)

• Format: $$\displaystyle (-1)^S \times (1.M) \times 2^{(E - Bias)} $$

  • S: Sign bit (0 = positive, 1 = negative)

  • E: Exponent field (stored with bias: 127 for single, 1023 for double)

  • M: Fraction/Mantissa (stored as fractional part, implicit leading 1 for normalized numbers).

• Single Precision (32-bit): 1-bit S, 8-bit E, 23-bit M. Bias = 127.

• Double Precision (64-bit): 1-bit S, 11-bit E, 52-bit M. Bias = 1023.

• Special Values:

  • Zero: E=0, M=0 → $$\displaystyle (-1)^S \times 0 $$

  • Denormalized: E=0, M≠0 → $$\displaystyle (-1)^S \times (0.M) \times 2^{1-Bias} $$ (gradual underflow).

  • Infinity: E=all 1s, M=0 → $$\displaystyle (-1)^S \times \infty $$

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

[!TIP] Normalized numbers have an implicit leading 1, so significand = 1.M. This gives one extra bit of precision.

C. Arithmetic Operations

• Addition/Subtraction (2's Complement):

  1. Align binary points (for fixed-point).

  2. Perform binary addition.

  3. Discard carry-out from sign bit (if no overflow).

  4. Overflow Detection: $$\displaystyle V = C_n \oplus C_{n-1} $$ (carry into sign bit XOR carry out).

• Floating-Point Addition/Subtraction Algorithm:

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

  2. Add/Subtract mantissas (consider sign bits).

  3. Normalize result: Shift mantissa left/right, adjust exponent.

  4. Round (to nearest even, etc.).

  5. Check for underflow/overflow.

  • DiagramCANVAS: Flowchart: Start → Compare exponents → Align → Add/Sub mantissa → Normalize → Round → Check exceptions → End

• Multiplication: Booth's Algorithm (for signed 2's complement):

  • Idea: Reduce number of additions by examining pairs of bits (Q₀, Q₋₁).

  • Steps:

    1. Initialize: A=0, Q₋₁=0, Count=n, [A, Q, Q₋₁] as registers.

    2. Examine (Q₀, Q₋₁):

       • 01 → A = A + M (add multiplicand)

       • 10 → A = A - M (subtract multiplicand)

       • 00 or 11 → No operation.

    3. Arithmetic right shift [A, Q, Q₋₁] as one unit.

    4. Decrement count, repeat until count=0.

    5. Result in [A, Q].

  • Example: -4 × 3 (4-bit):

    • M = -4 = 1100, -M = 0100, Q = 3 = 0011.

    • Initial: A=0000, Q=0011, Q₋₁=0, Count=4.

    • Steps: (Q₀Q₋₁=10) → A=A-M=0000+0100=0100, Shift → A=0010, Q=0001, Q₋₁=1.

    • (01) → A=A+M=0010+1100=1110 (ignore carry), Shift → A=1111, Q=0000, Q₋₁=1.

    • (11) → No op, Shift → A=1111, Q=0000, Q₋₁=0.

    • (00) → No op, Shift → A=1111, Q=0000, Q₋₁=0.

    • Final [A,Q] = 1111 0000 = -12 (correct).

• Division: Restoring/Non-Restoring (Conceptual):

  • Restoring: Subtract divisor from remainder, if negative add back (restore). Shift remainder-quotient left.

  • Non-Restoring: If remainder negative, add divisor (no restore), set quotient bit accordingly. More complex but faster.

III. REGISTER TRANSFER LANGUAGE (RTL) & MICROOPERATIONS

A. Register Transfer Language (RTL)

• Purpose: Symbolic language to describe microoperations and data transfers between registers.

• Syntax:

  • R2 ← R1 (Transfer)

  • R3 ← R1 + R2 (Arithmetic)

  • R4 ← R4 ⊕ R5 (Logic)

  • R5 ← shl R5 (Shift)

  • Controlled by control functions: C1: R2 ← R1 (executed if C1=1).

• Example: READ: R ← M[AR] (Read memory at address AR into register R when READ control signal is active).

B. Microoperations

• Types:

  1. Register Transfer: Move data between registers.

  2. Arithmetic: ADD, SUB, INC, etc.

  3. Logic: AND, OR, XOR, CLR (clear).

  4. Shift: SHL (left), SHR (right), ROT (rotate).

• Arithmetic Logic Shift Unit (ALU) - Block Diagram:

  • DiagramCANVAS: Block diagram with two input buses (A, B), a control selector (for operation: ADD, AND, SHIFT, etc.), an output bus (F), and status flags (Zero, Carry, Overflow). The shifter is a separate unit or integrated.

  • Functions: Performs all arithmetic/logic/shift operations based on control signals.

C. Memory & Bus Transfers

[!TIP] Bus Arbitration: When multiple devices (CPU, DMA, I/O) want bus control, a bus arbiter grants permission. DMA often uses cycle stealing (borrows bus cycles from CPU).

D. Control Signal Coordination

• Microoperations are executed in a sequence dictated by the control unit.

• Control signals (e.g., READ, WRITE, INCREG) enable/disable specific microoperations.

• Example: Instruction ADD R1, R2 might require:

  1. AR ← PC (Fetch address)

  2. DR ← M[AR] (Read instruction)

  3. IR ← DR (Load instruction register)

  4. R1 ← R1 + R2 (Execute)

• Each step is triggered by timing signals from the sequencer.

IV. CONTROL UNIT DESIGN

A. Hardwired Control Unit

• Design: Uses combinational logic (decoders, gates) and a sequence counter.

• Control Word: A binary word where each bit is a control signal (1 = active). For n control signals, word length = n bits.

• Operation: Instruction decoder + current state (from sequence counter) → generates next control word.

• Advantages: Very fast (no memory access), efficient.

• Disadvantages: Inflexible (hard to modify ISA), complex wiring for complex ISAs.

B. Microprogrammed Control Unit

• Concept: Control signals stored as microinstructions in Control Memory (CM).

• Microprogram: Sequence of microinstructions that implement one machine instruction.

• Microinstruction Formats:

  • Horizontal: One bit per control signal → wide, fast, little encoding.

  • Vertical: Encoded fields → narrow, slower, more memory efficient.

• Next Address Logic: Determines next microinstruction (sequencing: sequential, branch, subroutine call).

• Advantages: Flexible (easy to modify/debug), simpler design for complex ISAs.

• Disadvantages: Slower (extra memory access), requires CM.

C. Comparative Analysis

[!TIP] Modern processors use hybrid: Hardwired for common/fast paths, microcode for complex/rare instructions (e.g., x86).

V. INSTRUCTION SET ARCHITECTURE (ISA)

A. Instruction Formats

B. Addressing Modes (Implied in formats):

• Immediate: Operand in instruction (ADD R1, #5).

• Direct: Address of operand in instruction (ADD R1, 1000).

• Indirect: Instruction gives address of address (ADD R1, @1000).

• Register: Operand in register (ADD R1, R2).

• Register Indirect: Address in register (ADD R1, (R2)).

• Displacement/Indexed: ADD R1, 1000(R2) = M[1000 + R2].

C. Design Philosophies: RISC vs. CISC

[!TIP] RISC favors pipelining and compiler optimization. CISC aims for programmer convenience and memory efficiency.

VI. CPU ORGANIZATION

A. Major CPU Components

• General Register Set: Fast storage inside CPU.

  • AC (Accumulator): For ALU operations (in accumulator-based).

  • DR (Data Register): Holds data read/written to memory.

  • AR (Address Register): Holds memory address.

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

  • IR (Instruction Register): Holds current instruction.

  • TR (Temporary Register): For intermediate results.

• ALU: Performs arithmetic/logic operations.

• Control Unit (CU): Generates control signals (from hardwired/microprogrammed logic).

• System Interconnection: Internal buses (e.g., common bus for registers).

B. Stack Organization

• Stack: LIFO (Last-In-First-Out) structure.

• Operations:

  • PUSH: SP ← SP - 1, M[SP] ← operand.

  • POP: operand ← M[SP], SP ← SP + 1.

• Stack-based CPU:

  • Register Stack: Fast, limited size (e.g., 8-32 registers).

  • Memory Stack: Larger, slower (main memory).

• Applications:

  • Function Calling: CALL pushes return address & registers; RET pops.

  • Parameter Passing: Push args onto stack.

  • Recursion: Each call has its own stack frame.

  • Expression Evaluation: Postfix (Reverse Polish) notation.

VII. MEMORY SYSTEM ORGANIZATION

A. Memory Hierarchy

Registers (fastest, smallest, costliest)

    ↓

Cache (SRAM, ns)

    ↓

Main Memory (DRAM, ~100ns)

    ↓

Secondary Storage (Disk, ms)

• Trade-off: Speed ↑, Cost ↑, Capacity ↓ as we go up.

• Principle of Locality: Temporal (reuse) and Spatial (nearby addresses) → justifies cache.

B. Main Memory & RAM Organization

• Memory Address Map: Decoding logic to select specific memory chips from address lines.

  • Example: 16-bit address, 4 chips of 4KB each → use high 2 address bits as chip select.

C. Associative Memory (Content-Addressable Memory - CAM)

• Organization: Each word has comparator circuits. Search key compared in parallel with all words.

• Operation: Provide content, get address(es) of matching words.

• Advantages over RAM:

  • Parallel search → much faster for lookups.

  • Ideal for table lookups where search key is known (not address).

• Applications:

  • Cache Tag Storage: Compare tag from address with all tags in set simultaneously.

  • Translation Lookaside Buffer (TLB): Fast virtual-to-physical address translation.

  • Database/Network routers: Fast pattern matching.

D. Cache Memory

• Mapping Functions:

  • Direct Mapped: Each main memory block maps to exactly one cache line (set index = block number mod #sets). Simple, but conflict misses.

  • Set-Associative: Each block maps to k lines in one set (k-way). Compromise.

  • Fully Associative: Block can go anywhere. Best hit ratio, but expensive (search all tags).

• Replacement Policies (when cache full):

  • LRU (Least Recently Used): Best average, but needs hardware counters.

  • FIFO (First-In-First-Out): Simple, but may evict frequently used.

  • Random: Simple, often good enough.

• Write Policies:

  • Write-through: Write to both cache and memory. Simple, consistent, but slow (memory write on every store).

  • Write-back: Write to cache only, mark dirty. Write to memory only when evicted. Faster, but complex (need dirty bits).

• Performance Calculation:

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

  • Average Access Time (AAT):

$$T_{avg} = H \cdot T_{cache} + (1-H) \cdot (T_{cache} + T_{miss})$$

    where $$\displaystyle T_{miss} $$ = time to access main memory (and possibly fill cache).

*   **Example Problem** (from 2022 paper):

    *   Cache: 2-way set associative, size 16KB, block size 256B.

    *   Main Memory: 128KB, byte-addressable.

    *   Find **tag directory size** (in bits/bytes).

    *   **Solution**:

        1.  Cache blocks = 16KB / 256B = 64 blocks.

        2.  Sets = 64 blocks / 2 ways = 32 sets.

        3.  Address bits: 128KB → 2^17 bytes → 17 bits.

        4.  Block offset = log₂(256) = 8 bits.

        5.  Set index = log₂(32) = 5 bits.

        6.  Tag bits = 17 - 8 - 5 = **4 bits**.

        7.  Tag directory size = Sets × Ways × Tag bits = 32 × 2 × 4 = **256 bits** = **32 bytes**.

E. Virtual Memory

• Concept: Illusion of large main memory using secondary storage (disk). Program sees virtual address space larger than physical RAM.

• Paging:

  • Divide: Virtual memory → fixed-size pages (e.g., 4KB). Physical memory → frames (same size).

  • Page Table: Maps virtual page number → frame number (per process).

  • Translation: Virtual address = [VPN | Offset] → [Frame # | Offset] via page table.

  • Page Fault: Access to page not in memory → OS loads page from disk (expensive).

  • Diagram:

    DiagramCANVAS: Virtual Address split into Page Number and Offset. Page Number indexes Page Table to get Frame Number. Frame Number concatenated with Offset gives Physical Address.

• Segmentation:

  • Divide: Variable-size segments (code, data, stack) based on program logic.

  • Segment Table: Maps segment number → base address + limit (length).

  • Translation: Virtual address = [Segment # | Offset] → check offset < limit, then [Base + Offset].

  • Advantages: User-view (logical grouping), protection (limit check), sharing (common code segment).

• Comparison: Paging vs. Segmentation

  | | Paging | Segmentation | |---|------------|------------------| | Division | Fixed-size pages | Variable-size segments | | Fragmentation | Internal (last page unused) | External (holes between segments) | | User View | Invisible (physical frames) | Visible (logical segments) | | Protection | Per-page (read/write/execute) | Per-segment (more natural) | | Sharing | Difficult (pages scattered) | Easy (share whole segment) | | Typical Use | Base for virtual memory | Often combined (paged segmentation) |

F. Factors Affecting Effective Memory Access Time

• Hierarchical Memory: Average time depends on hit ratios at each level.

• For Two-Level Cache/Main Memory:

$$T_{eff} = T_{L1} + (1 - H_{L1}) \cdot (T_{L2} + (1 - H_{L2}) \cdot T_{mem})$$

• For Cache with Write Policy:

  • Write-through: $$\displaystyle T_{write} = T_{cache} + T_{mem} $$ (always write to mem).

  • Write-back: $$\displaystyle T_{write} = T_{cache} $$ (only when dirty line evicted).

• Virtual Memory Impact: Page fault rate (p) → $$\displaystyle T_{eff} = (1-p) \cdot T_{mem} + p \cdot T_{page\_fault} $$, where $$\displaystyle T_{page\_fault} $$ is huge (disk access ~ ms).

VIII. I/O ORGANIZATION & INTERFACE

A. I/O Interface & Buses

• I/O Bus Structure: Contains Address lines (select device/register), Data lines (transfer data), Control lines (read/write, interrupt, etc.).

• Bus Standards:

  | Standard | Purpose | Topology | Key Features | Data Rate (approx) | |----------|---------|----------|--------------|-------------------| | PCI (Peripheral Component Interconnect) | Internal PC expansion | Parallel, shared bus | 32/64-bit, 33/66 MHz, plug-and-play | 133-533 MB/s | | SCSI (Small Computer System Interface) | High-speed peripherals (disk, scanner) | Parallel, daisy-chain | Multiple devices, separate controller, high reliability | Up to 640 MB/s (Ultra-640) | | USB (Universal Serial Bus) | External plug-and-play devices | Serial, star (hub) | Hot-swap, power delivery, multiple speeds (1.1 to 4.0) | USB 3.2: 20 Gbps |

B. Data Transfer Modes

1. Programmed I/O (Polling):

   • CPU continuously checks status register of I/O device.

   • Wastes CPU cycles (busy wait).

2. Interrupt-Initiated I/O:

   • I/O device interrupts CPU when ready.

   • Vectored: Device provides interrupt vector (address of ISR) → faster.

   • Non-Vectored: CPU searches interrupt service routine → slower.

3. Direct Memory Access (DMA):

   • Idea: DMA controller transfers data between I/O and memory without CPU.

   • DMA Controller Block Diagram:

     DiagramCANVAS: Block with registers: Data Count (DC), Address (AR), Control/Status (CS). Buses: System Bus (to memory), I/O Bus (to device). Control lines: Request (to CPU), Acknowledge (from CPU), Interrupt (on completion).

   • Operation:

     1. CPU programs DMA: sets AR (memory address), DC (byte count), control bits.

     2. CPU issues start command.

     3. DMA requests bus (via HRQ/HLDA in 8237).

     4. CPU relinquishes bus (floats its drivers).

     5. DMA reads/writes one word/byte, increments AR, decrements DC.

     6. Repeat until DC=0 → DMA releases bus, sends interrupt.

   • Transfer Modes:

     • Burst Transfer: DMA keeps bus until all data transferred. Fast, but CPU starved.

     • Cycle Stealing: DMA takes one bus cycle at a time, interleaving with CPU. Slower, but fair.

   • DMA Cycle Calculation (from 2022 paper):

     • Problem: Data count register = 16 bits → max transfer per DMA acquisition = $$\displaystyle 2^{16} $$ bytes = 65,536 bytes.

     • File size = 29,154 KB = 29,154 × 1024 B = 29,827,776 B.

     • Minimum number of bus acquisitions = $$\displaystyle \lceil \frac{29,827,776}{65,536} \rceil = \lceil 455.25 \rceil = \boxed{456} $$.

     • (Note: Each acquisition may transfer up to DC size, but last may be partial).

C. Parallel Processing & Multiprocessors (Introductory)

• Flynn's Taxonomy:

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

  • SIMD: Single Instruction, Multiple Data (vector processors, GPUs).

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

  • MIMD: Multiple Instruction, Multiple Data (multiprocessors, multicore).

• Characteristics of Multiprocessors:

  • Shared Memory: Common physical memory space.

  • Interconnection Network: Bus, crossbar, mesh (connect CPUs/memory).

  • Synchronization: Locks, semaphores for shared data.

  • Cache Coherence: Problem: Multiple caches have copies → need coherence protocol (e.g., MESI).

• Memory Interleaving:

  • Concept: Distribute consecutive memory addresses across multiple memory modules.

  • Example: 4-way interleaving: Address 0 → Module 0, 1 → 1, 2 → 2, 3 → 3, 4 → 0, etc.

  • Benefit: Reduces access conflicts in multiprocessors because different processors likely access different modules simultaneously → higher bandwidth.

IX. PIPELINING & ARITHMETIC PIPELINE

A. Instruction Pipelining

• Pipeline Stages (Classic 5-stage):

  1. IF (Instruction Fetch): Read instruction from memory (PC → MAR → M → IR).

  2. ID (Instruction Decode): Decode opcode, read registers (IR → control, read RF).

  3. EX (Execute): ALU operation (e.g., add, branch target calc).

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

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

• Speedup: Ideal speedup ≈ number of stages (n). For m instructions, time without pipeline = m×k, with pipeline = (k + m - 1). Speedup = $$\displaystyle \frac{mk}{k+m-1} \rightarrow k $$ as m→∞.

• Hazards (Prevent next instruction from executing in next cycle):

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

  • Data: Dependency (e.g., ADD R1, R2 followed by SUB R3, R1). Solution: Forwarding/bypassing, stall (bubble).

  • Control: Branch/jump decision not ready (in EX stage). Solution: Branch prediction, delayed slot.

B. Arithmetic Pipeline Design

• Idea: Break arithmetic operation into sub-operations (stages) to achieve throughput of one result per clock cycle after fill.

• Example: Floating-Point Adder Pipeline Stages:

  1. Exponent Compare & Alignment: Subtract exponents, shift smaller mantissa.

  2. Addition: Add aligned mantissas.

  3. Normalization: Shift result to normalize (leading 1).

  4. Rounding: Apply rounding mode.

  5. Exception Check: Overflow, underflow, NaN.

• How it Improves Speed:

  • Without pipeline: Latency = sum of all stage times (e.g., 5×τ).

  • With pipeline: Throughput = 1 result/τ after initial latency (5τ). Speedup ≈ number of stages for long sequences.

  • Used in floating-point units (FPU), multipliers, dividers.

[!TIP] Pipeline throughput (results/cycle) increases, but latency (time per result) stays similar. Hazards reduce ideal speedup.