UNIT 3: COMPUTER ARCHITECTURE - COMPREHENSIVE NOTES

A. FOUNDATIONS & COMPUTER EVOLUTION

Computer Generations & Evolution

[!TIP] Exam Focus: Link each generation's tech shift to architectural outcomes (e.g., VLSI → RISC, parallelism).

Von Neumann Architecture

• Stored-Program Concept: Instructions and data stored in the same memory unit.

• Five Core Components:

  1. Memory Unit: Stores data & instructions.

  2. Arithmetic Logic Unit (ALU): Performs computations.

  3. Control Unit (CU): Directs operations.

  4. Input/Output (I/O) Unit: Communicates with external world.

  5. System Bus: Interconnect for data, address, control signals.

Computer Architecture vs. Organization

B. DATA REPRESENTATION & ARITHMETIC

Fixed-Point Number Representations

For an n-bit word:

• Signed Magnitude:

  • MSB = sign (0=+, 1=-), remaining bits = magnitude.

  • Range: $$\displaystyle -(2^{n-1}-1) $$ to $$\displaystyle +(2^{n-1}-1) $$.

  • Pros: Simple, intuitive.

  • Cons: Two zeros (+0, -0), complex arithmetic hardware.

• 1's Complement:

  • Negative number = bitwise complement of positive equivalent.

  • Range: $$\displaystyle -(2^{n-1}-1) $$ to $$\displaystyle +(2^{n-1}-1) $$.

  • Pros: Simple negation.

  • Cons: Two zeros, end-around carry in addition.

• 2's Complement (Most Used):

  • Negative number = 1's complement + 1.

  • Range: $$\displaystyle -2^{n-1} $$ to $$\displaystyle +(2^{n-1}-1) $$.

  • Advantages: Single zero, seamless addition/subtraction, no end-around carry.

[!TIP] Key Formula: For n-bit 2's complement:

Min: $$\displaystyle -2^{n-1} $$  Max: $$\displaystyle 2^{n-1}-1 $$  Boxed: \boxed{\text{Range: } -2^{n-1} \text{ to } 2^{n-1}-1}

Floating-Point Arithmetic (IEEE 754)

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

  • Single Precision: 1 sign bit, 8 exponent bits (Bias=127), 23 mantissa bits.

  • Double Precision: 1 sign bit, 11 exponent bits (Bias=1023), 52 mantissa bits.

• Addition/Subtraction Algorithm:

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

  2. Add/Subtract Mantissas.

  3. Normalize Result: Shift left/right to get form 1.xxxx.

  4. Round (Guard, Round, Sticky bits).

  5. Check for Underflow/Overflow.

Multiplication Algorithms

• Booth's Algorithm: Recodes multiplier to reduce additions for consecutive 1s.

  • Steps: Examine Q0 & Q-1 bits. If 10 → A = A - M; 01 → A = A + M; else no change. Arithmetic right shift (A, Q, Q-1).

  • Example: $-4 \times 3$ (4-bit 2's complement)

    • M = 1100 (-4), -M = 0100 (4), Multiplicand Q = 0011 (3)

    • Initial: A=0000, Q=0011, Q-1=0, Count=4

    • Step 1: Q0Q-1=10 → A = A - M = 0000 + 0100 = 0100. Shift → A=0010, Q=0001, Q-1=1.

    • Step 2: Q0Q-1=11 → No add. Shift → A=0001, Q=1000, Q-1=1.

    • Step 3: Q0Q-1=01 → A = A + M = 0001 + 1100 = 1101. Shift → A=1110, Q=0100, Q-1=0.

    • Step 4: Q0Q-1=00 → No add. Shift → A=1111, Q=0010, Q-1=0.

    • Result: (A,Q) = 1111 0010 = -12 (correct).

C. CPU DESIGN & CONTROL

Register Transfer Language (RTL) & Microoperations

• RTL Syntax: [Destination] ← [Source] with operations.

  • Example: R2 ← R1 + R3 (arithmetic), R4 ← R4 ⊕ R5 (logic), R6 ← shl R6 (shift).

• Arithmetic Logic Shift Unit (ALSU): Single unit with multiplexers to select operation (ADD, AND, SHL, etc.).

Bus & Memory Transfers

Control Unit Design Comparison

[!TIP] Exam Distinction: Hardwired = "wired logic," fast. Microprogrammed = "software-like control," flexible.

Stack Organization

• LIFO Structure: Pointer (SP) points to top.

• Instructions: PUSH (SP←SP-1, M[SP]←src), POP (dst←M[SP], SP←SP+1).

• Role in Recursion: Each call creates an Activation Record (return address, parameters, local vars) on stack. Enables multiple active instances of same function.

D. INSTRUCTION SET ARCHITECTURE (ISA)

Instruction Formats

RISC vs. CISC Design Philosophy

[!TIP] Key RISC Feature: All operations between registers. Memory access only via dedicated LOAD/STORE.

E. MEMORY SYSTEMS

Memory Hierarchy Principle

• Principle of Locality:

  • Temporal: Recently accessed items likely reused soon.

  • Spatial: Access to an item likely accesses nearby items.

• Hierarchy Diagram: Registers → L1 Cache → L2 Cache → Main Memory → Disk.

• Justification: Faster, smaller memories at top; slower, larger at bottom. Exploits locality to achieve average access time near top level.

Cache Memory

• Mapping Techniques:

  • Direct Mapped: Each block maps to exactly one cache line. Simple, but conflict misses.

  • Fully Associative: Block can map to any cache line. Flexible, but slow (search all).

  • Set-Associative: k-way compromise. Cache divided into sets; block maps to a set, then can go to any line in set.

    • Example: 2-way set-associative: each set has 2 lines.

• Performance Metrics:

  • Hit Ratio (HR) = Hits / Total accesses.

  • Miss Ratio (MR) = 1 - HR.

  • Average Access Time (AAT) = Hit Time + MR × Miss Penalty.

Cache Calculation Example (2022 Q)

Consider a 2-way set associative cache of size 16KB, block size 256 bytes. Main memory size 128KB. Find tag directory size.

Solution Steps:

1. Cache lines: $$\displaystyle 16KB / 256B = 64 $$ lines.

2. Sets (S): 2-way → $$\displaystyle 64 / 2 = 32 $$ sets.

3. Main memory blocks: $$\displaystyle 128KB / 256B = 512 $$ blocks.

4. Address bits: $$\displaystyle \log_2(128KB) = \log_2(131072) = 17 $$ bits.

5. Offset bits (O): $$\displaystyle \log_2(256) = 8 $$ bits.

6. Index bits (I): $$\displaystyle \log_2(32) = 5 $$ bits.

7. Tag bits (T): $$\displaystyle 17 - (5+8) = 4 $$ bits.

8. Tag directory size: Number of sets × (ways × tag bits) = $$\displaystyle 32 \times (2 \times 4) = 256 $$ bits.

[!TIP] Formula: Tag Directory Size = $S \times (k \times T)$ bits, where S=sets, k=associativity, T=tag bits.

Virtual Memory

• Concept: Gives program illusion of large, contiguous memory. Uses secondary storage (disk).

• Paging:

  • Divides memory into fixed-size pages (logical) and frames (physical).

  • Page Table: Maps page number → frame number.

  • TLB (Translation Look-aside Buffer): Fast associative cache for page table entries.

  • Diagram: Logical address → (Page #, Offset) → Page Table → Frame # → Physical address.

• Segmentation:

  • Divides memory into variable-size segments (code, data, stack).

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

  • Logical address: (Segment #, Offset).

  • Diagram: Segment Table lookup → Base + Offset → Physical address.

Effective Access Time (EAT)

• Formula:

$$\text{EAT} = t_{hit} \times h + t_{miss} \times (1-h)$$

where $h$ = hit ratio, $$\displaystyle t_{hit} $$ = cache hit time, $$\displaystyle t_{miss} $$ = cache miss time (includes main memory access + possible page fault service).

• For Virtual Memory (with paging):

$$EAT = h \times t_{cache} + (1-h) \times (t_{page\ fault\ overhead} + t_{memory\ access})$$

• Factors: Hit ratio (locality), miss penalty (TLB miss, page fault service time).

Associative Memory

• Concept: Content-addressable (search by data, not address).

• Organization: All cells compared in parallel with search key.

• Comparison with RAM:

  | Aspect | Associative Memory | RAM | |------------------|---------------------------------|-----------------------------| | Access | By content (parallel search). | By address (sequential). | | Speed | Faster for search (O(1)). | Slower for search (O(n)). | | Cost | Much higher (complex cell). | Lower. | | Use Cases | TLB, cache tags, lookup tables. | Main memory. |

Memory Interleaving

• Purpose: Increase memory bandwidth, reduce access conflicts in multiprocessors.

• Types:

  • Low-order Interleaving: Lower-order address bits select module. Consecutive addresses go to different modules → good for sequential access.

  • High-order Interleaving: Higher-order bits select module. Used for distributing processes/threads across modules.

• Effect: Allows multiple simultaneous memory accesses if addresses map to different banks.

F. I/O & DMA

Direct Memory Access (DMA)

• Need: For block transfers (disk, network), CPU would be burdened by byte/word I/O. DMA offloads.

• DMA Controller Operation:

  1. Initialization: CPU programs DMA (source, destination, count).

  2. Transfer: DMA takes bus control, transfers block between I/O device and memory.

  3. Termination: DMA interrupts CPU after transfer.

• Transfer Modes:

  • Burst Mode: DMA holds bus for entire block. Fast, but CPU starved.

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

• Numerical Problem (2022 Q):

  Data count register = 16 bits. File = 29,154 KB. Memory byte-addressable. Minimum bus acquisitions?

  Solution:

  1. Max bytes per acquisition = $$\displaystyle 2^{16} = 65,536 $$ bytes (since 16-bit register).

  2. Total file size in bytes = $$\displaystyle 29,154 \times 1024 = 29,839,296 $$ bytes.

  3. Number of acquisitions = $\lceil 29,839,296 / 65,536 \rceil$.

  4. Calculation: $$\displaystyle 29,839,296 \div 65,536 = 455.25... $$

  5. Minimum acquisitions = 456.

  [!TIP] Key: Data count register size (n bits) → max transfer per bus acquisition = $$\displaystyle 2^n $$ bytes (if byte-addressable). Always convert file size to bytes.

G. PIPELINING

Arithmetic Pipeline

• Concept: Break complex operation (e.g., FP add) into sequential stages (e.g., exponent compare, mantissa align, add, normalize, round).

• Design Example (FP Addition Stages):

  1. Stage 1: Compare exponents, select larger.

  2. Stage 2: Shift smaller mantissa.

  3. Stage 3: Add mantissas.

  4. Stage 4: Normalize result.

  5. Stage 5: Round result.

• Speedup: Ideal speedup ≈ number of stages (k). Throughput = 1 result per cycle after pipeline fill.

• Hazards: Structural (resource conflict), Data (dependencies), Control (branches).

Instruction Pipeline (Classic RISC)

• 5 Stages:

  1. IF (Instruction Fetch): Get instruction from memory.

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

  3. EX (Execute): ALU operation.

  4. MEM (Memory Access): Load/store.

  5. WB (Write Back): Update register file.

• Performance:

  • Speedup (S): $$\displaystyle S = \frac{n \times k}{k + n - 1} $$ for n instructions, k stages.

  • Efficiency: $$\displaystyle \frac{S}{k} $$ (ideal = 1).

• Hazard Mitigation:

  • Structural: Duplicate resources (e.g., separate instruction/data caches).

  • Data: Forwarding/bypassing, stall (bubble).

  • Control: Branch delay slots, dynamic prediction.

H. PARALLEL & MULTIPROCESSOR SYSTEMS

Flynn's Taxonomy

Amdahl's Law

• Formula:

$$S_{speedup} = \frac{1}{(1 - P) + \frac{P}{N}}$$

where $P$ = proportion of code that can be parallelized, $N$ = number of processors.

• Implication: Speedup limited by sequential portion. Even with infinite processors, max speedup = $1/(1-P)$.

Characteristics of Multiprocessors

• Definition: Multiple CPUs sharing memory & resources.

• Shared vs. Distributed Memory:

  • Shared Memory: All processors access global memory (UMA - Uniform Memory Access). Easier programming, but scalability limited by bus contention.

  • Distributed Memory: Each processor has local memory (NUMA - Non-Uniform). Scales better, but programming harder (explicit message passing).

• Symmetric vs. Asymmetric:

  • SMP (Symmetric): All CPUs equal, share OS, memory, bus.

  • AMP (Asymmetric): Master-slave; master controls I/O, OS.

• Key Characteristics: Scalability, fault tolerance, synchronization (locks, semaphores), cache coherence (MESI protocol).

I. BUS STANDARDS & INTERCONNECTS

[!TIP] Distinguish: PCI = internal expansion bus. SCSI = high-speed device interface (often internal). USB = external peripheral serial bus.

END OF UNIT 3 NOTES
Focus on diagrams (Von Neumann, FP flow, Paging/Segmentation, Cache mapping, Pipeline stages) and numerical problems (Booth's, Cache tag, DMA, EAT).