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

UNIT 4: Advanced CPU & Memory Systems

I. Historical Foundations & Basic Architecture

Evolution of Computer Generations

Key Influence: Each generation reduced size, cost, and power while increasing speed and reliability, driving the shift from custom-built machines to general-purpose, stored-program computers based on the von Neumann model.

Von Neumann Architecture

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

1. Memory Unit: Stores both data & instructions.

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

3. Control Unit (CU): Fetches, decodes, and executes instructions.

4. Input/Output (I/O) Equipment.

5. System Bus: Communication pathway (Address, Data, Control buses).

Exam Tip: The bottleneck between CPU and memory (von Neumann bottleneck) is a central theme in later topics like cache and pipelining.

II. Data Representation & Arithmetic

Fixed-Point Number Representations

Range for n-bit: $$\displaystyle \pm(2^{n-1} - 1) $$ for SM/1's, $$\displaystyle \pm2^{n-1} $$ for 2's (asymmetric).

Floating-Point Arithmetic (Addition/Subtraction)

Core Steps (Flowchart Logic):

1. Align Exponents: Shift the mantissa of the number with the smaller exponent right until exponents are equal. Track lost bits (guard, round, sticky bits).

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

3. Normalize Result: Shift result mantissa left/right to restore leading 1 (for normalized numbers). Adjust exponent accordingly.

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

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

Critical: Alignment is the most complex step, requiring a barrel shifter.

Booth's Multiplication Algorithm

Goal: Efficiently multiply signed numbers (2's complement) by reducing the number of addition operations. Key Idea: Scan multiplier bits from LSB to MSB (including an extra implied 0 on the right). Based on the current bit (Q_i) and the previous bit (Q_{i+1}):

• 00 or 11 → No operation (just shift).

• 01 → Add multiplicand to accumulator (A).

• 10 → Subtract multiplicand from accumulator (A).

After each step, perform an arithmetic right shift on [A, Q, Q_{-1}].

Example: -4 × 3 (4-bit)

• Represent: -4 = 1100, 3 = 0011. Multiplicand (M) = 1100, Multiplier (Q) = 0011.

• Initial: [A, Q, Q_{-1}] = [0000, 0011, 0]

Final Product: [A, Q] = 00011100 = 28 in decimal? Wait: -4 * 3 = -12.

00011100 is +28. Error in example calculation above due to 4-bit overflow. Correct 5-bit result: 10100 = -12. The algorithm works but requires sufficient bit-width to avoid overflow in partial products.

Exam Tip: Always show the [A, Q, Q_{-1}] register triple and the decision based on (Q_0, Q_{-1}).

III. Register Transfer & Micro-Operations

Register Transfer Language (RTL)

An algorithmic notation to describe the micro-operation transfers between registers in a digital system.

• Syntax: R2 ← R1 (Transfer contents of R1 to R2).

• Bus Transfer: BUS ← R1; R2 ← BUS (Two-step, uses common bus).

• Control: Operations occur only when control signals are active (e.g., R2_out, BUS_in).

Arithmetic Logic Shift Unit (ALSU)

Combines arithmetic, logic, and shift functions into one unit.

• Inputs: Two source operands (A, B), function select lines.

• Outputs: Result (F), status flags (Zero, Carry, Overflow).

• Control: S2 S1 S0 selects operation (e.g., 000=Transfer A, 001=A+B, 010=A-B, 100=Shift left, etc.).

Bus Transfer vs. Memory Transfer

Control Signal Coordination

For a register transfer like R2 ← R1 via a bus:

1. Enable source: R1_out signal enabled → R1 drives bus.

2. Enable destination: R2_in signal enabled → R2 latches bus value.

3. Timing: Both signals must be active simultaneously for at least the setup/hold time of R2.

4. Bus contention prevention: Ensure only one source drives the bus at a time (mutual exclusion in control logic).

Common Pitfall: Forgetting that bus drivers must be tri-stated when not in use to prevent short circuits.

IV. CPU Control Unit Design

Hardwired Control Unit

• Design: Uses combinational logic gates (PLA, ROM) to generate control signals directly from instruction opcode and timing signals.

• Implementation: Fixed, fast, and optimized for a specific ISA.

• Characteristics:

  • Speed: Very fast (no memory access for microcode).

  • Flexibility: Difficult to modify/debug. Changes require hardware rewiring.

  • Complexity: Becomes unwieldy for complex ISAs (many control signals).

  • Cost: Lower per unit for simple designs.

Microprogrammed Control Unit

• Design: Uses control memory (CM) storing microinstructions. A microsequencer fetches and executes these microprograms.

• Implementation: Control signals are fields within the microinstruction.

• Characteristics:

  • Speed: Slower (one memory access per microinstruction).

  • Flexibility: Easy to modify/debug by changing microcode.

  • Complexity: Handles complex ISAs cleanly (horizontal/vertical microcode).

  • Cost: Higher due to control memory, but cheaper to design.

Comparative Analysis: Hardwired vs. Microprogrammed

Control Memory (CM)

• Role: Stores the microprogram – a sequence of microinstructions that define the control signals for each machine instruction's execution cycle.

• Organization:

  • Address: Determined by microsequencer (next address logic) based on current microinstruction and condition flags.

  • Content: Each word is a microinstruction containing control signal bits and next address field.

• Advantages:

  1. Simplifies Design: Complex sequences are encoded as microprograms.

  2. Eases Modification: Bug fixes/ISA extensions via microcode patches.

  3. Supports Complex Instructions: Implements multi-step, variable-length instructions easily.

  4. Facilitates Emulation: Can implement other ISAs by loading different microprograms.

Exam Tip: Modern CPUs often use a hybrid approach: hardwired for common, simple instructions (fast path) and microcode for complex/rare instructions (slow path).

V. Instruction Set Architecture (ISA)

Instruction Formats

RISC vs. CISC

Modern Trend: CISC ISAs (x86) are internally translated to RISC-like micro-ops for execution.

VI. CPU Organization & Specialized Structures

Major Components of CPU

1. Control Unit (CU): Generates control signals.

2. Arithmetic Logic Unit (ALU): Integer/logic operations.

3. Floating-Point Unit (FPU): Floating-point operations.

4. Register File: Fast, on-chip storage (general-purpose, special like PC, IR, MAR, MDR).

5. Cache Memory: L1/L2/L3, bridges CPU-memory speed gap.

6. Memory Management Unit (MMU): Handles virtual-to-physical translation.

7. Bus Interface Unit (BIU): Manages bus transactions.

Stack Organization in CPUs

• Implementation:

  • Hardware Stack: Dedicated register (SP) and memory region. PUSH/POP are single instructions.

  • Software Stack: General-purpose registers or memory managed by compiler (common in RISC).

• Role in Function Calling & Recursion:

  1. Call: PUSH return address, PUSH old frame pointer (BP/FP), set new SP/BP.

  2. Local Variables: Allocate space by decrementing SP.

  3. Return: POP old BP, POP return address into PC.

  4. Recursion: Each call creates a new stack frame, enabling independent local variable storage and return addresses.

Key: Stack provides LIFO order, perfect for nested calls and unwinding.

VII. Memory System Hierarchy & Organization

Memory Hierarchy Concept

Principle of Locality: Temporal (reuse) & Spatial (nearby addresses) → justifies caching.

Main Memory vs. Associative Memory

Advantage of Associative Memory: Eliminates search time for lookups, crucial for translation lookaside buffers (TLBs) and content-addressable caches.

Memory Interleaving

• Technique: Distribute consecutive memory blocks across multiple memory banks.

  • Low-order interleaving: Address bits i to j select bank (consecutive words in different banks).

  • High-order interleaving: Address bits k to l select bank (consecutive words in same bank).

• Purpose: Allow overlapping of memory accesses. While bank 0 is accessing, bank 1 can start next access → increases bandwidth.

• Role in Multiprocessors: Reduces access conflicts when multiple CPUs/cores access memory simultaneously. If addresses are interleaved, different processors likely hit different banks, reducing contention.

Factors Affecting Effective Memory Access Time

1. Hit Ratio (h): Probability data is in faster memory (cache).

2. Access Times: $$\displaystyle t_c $$ (cache), $$\displaystyle t_m $$ (main memory).

3. Block Transfer Time: For multi-word blocks.

4. Interleaving & Bank Conflicts.

5. Write Policy: Write-through (slower) vs. Write-back (faster on hits, complex on misses).

6. Replacement Policy: LRU, FIFO, Random (affects hit ratio).

Effective Access Time (EAT) for Cache:

$$ \text{EAT} = h \cdot t_c + (1 - h) \cdot (t_c + t_m) $$

For write-back: misses may require block write-back → longer penalty.

VIII. Virtual Memory & Memory Management

Virtual Memory Concept

• Necessity: Allows execution of programs larger than physical memory. Provides illusion of large, contiguous, private memory to each process. Enables memory protection and simplified programming (no manual overlay).

• Mechanism: Demand paging/segmentation. OS + MMU handle translation on page faults.

Paging

• Mechanism:

  1. Divide: Virtual & physical memory into fixed-size pages (virtual) and frames (physical).

  2. Page Table (PT): Per-process table mapping Virtual Page Number (VPN) → Physical Frame Number (PFN). Contains valid bit, dirty bit, protection bits.

  3. Translation: CPU generates Virtual Address (VA). MMU uses PT to get PFN, combines with page offset to form Physical Address (PA).

  4. Page Fault: If valid bit = 0, OS loads page from disk into a free frame, updates PT.

Segmentation

• Mechanism:

  1. Divide: Memory into variable-length segments (logical units: code, data, stack).

  2. Segment Table (ST): Per-process table mapping Segment Number (SN) → Segment Base Address & Limit.

  3. Translation: VA = [SN, offset]. MMU checks offset < limit, then PA = Base + offset.

  4. Protection: Segment-level read/write/execute bits.

Paging vs. Segmentation

Modern Systems: Typically use paged segmentation (segments divided into pages) for benefits of both.

IX. Cache Memory

Cache Organization & Mapping Techniques

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

• Fully Associative: Block can map to any cache line. Flexible, low conflict misses, but requires parallel search of all tags → expensive, slow.

• Set-Associative: Compromise. Cache divided into N-way sets (e.g., 2-way, 4-way). Block maps to a specific set (like direct-mapped), but can go into any line within that set. N-way set-associative = N-way within-set associativity.

Cache Performance Calculation: Tag Directory Size

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

Solution:

1. Cache lines: $$\displaystyle \frac{\text{Cache Size}}{\text{Block Size}} = \frac{16 \text{ KB}}{256 \text{ B}} = \frac{16384}{256} = 64 $$ lines.

2. Sets: Since 2-way, $$\displaystyle \text{Sets} = \frac{64 \text{ lines}}{2} = 32 $$ sets.

3. Address bits: Main memory 128 KB = $$\displaystyle 2^{17} $$ bytes → VA = 17 bits.

4. Offset bits: Block size 256 B = $$\displaystyle 2^8 $$ → Offset = 8 bits.

5. Index bits: Sets = 32 = $$\displaystyle 2^5 $$ → Index = 5 bits.

6. Tag bits: Tag = VA bits - Index bits - Offset bits = 17 - 5 - 8 = 4 bits.

7. Tag directory size: Each set has 2 tags (2-way). Total tags = $$\displaystyle 32 \text{ sets} \times 2 = 64 $$ tags.

   Size = $$\displaystyle 64 \text{ tags} \times 4 \text{ bits/tag} = 256 \text{ bits} = 32 \text{ bytes} $$.

\boxed{\text{Tag Directory Size} = 32 \text{ bytes}}

Formula: Tag bits = (log2(Main Memory Size) - log2(Block Size) - log2(Sets)). Always include valid bits in full tag store size if asked.

X. Pipelining & Parallel Arithmetic

Arithmetic Pipeline Design

• Stages: Break a complex operation (e.g., floating-point add, multiplication) into sequential sub-operations.

  • Example (FP Add): 1. Exponent compare, 2. Mantissa alignment (shift), 3. Mantissa addition, 4. Normalization, 5. Rounding.

• Implementation: Each stage is a hardware unit. Pipeline registers between stages hold intermediate results.

• Speed-up: Ideal speedup ≈ number of stages (k). Throughput increases, latency per instruction also increases slightly.

• Hazards:

  • Structural: Resource conflict (e.g., two stages need same hardware).

  • Data: Dependency between instructions (RAW, WAR, WAW). Solved by forwarding/bypassing, stalling.

  • Control: Branch instructions → pipeline fetches wrong instructions. Solved by branch prediction, delayed slots.

Instruction Pipeline (Basic)

Classic 5-Stage RISC Pipeline:

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

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

3. EX (Execute): ALU operation (address calc, arithmetic).

4. MEM (Memory Access): Load/store to data cache.

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

Speedup: $$\displaystyle S = \frac{n}{k + n - 1} $$ for $n$ instructions, $k$ stages. Approaches $k$ for large $n$.

Key Limitation: Pipeline bubbles from hazards reduce effective speedup.

XI. Parallel & Multiprocessor Systems

Parallel Processing Concepts & Classifications

• 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 (most common: multiprocessors, multicore, clusters).

Characteristics of Multiprocessors

Symmetric vs. Asymmetric Multiprocessing:

• SMP (Symmetric): All CPUs equal, share OS, memory, I/O. OS runs on any CPU. Common in multicore.

• ASMP (Asymmetric): One master CPU controls OS, others slaves run user tasks. Master handles I/O. Less common now.

Interconnection Networks:

• Bus: Simple, limited bandwidth (SMP).

• Ring/Mesh: Used in multi-core chips (e.g., Intel ring, mesh).

• Crossbar: Non-blocking, expensive.

• Multistage (e.g., Omega): Balance of cost & performance.

Memory Interleaving in Multiprocessors: Critical to distribute memory accesses from different CPUs across banks, minimizing contention and maximizing aggregate bandwidth.

XII. I/O Systems & Direct Memory Access

Direct Memory Access (DMA)

• Concept: Offloads bulk data transfer between I/O device and memory from CPU. CPU only initiates transfer and handles interrupts on completion.

• Operation:

  1. CPU programs DMA controller with: source address, destination address, transfer count.

  2. CPU continues other work.

  3. DMA controller takes control of system bus (becomes bus master).

  4. Transfers data directly between device and memory.

  5. On completion, DMA controller interrupts CPU.

• DMA Controller Functionality:

  • Registers: Source Addr, Dest Addr, Count, Control/Status.

  • Bus Arbitration: Requests and gains bus control from CPU.

  • Data Transfer: Reads/writes data, increments addresses, decrements count.

• Transfer Modes:

  • Burst Mode: DMA takes bus, transfers entire block in one go. Fast, but CPU starved for long periods.

  • Cycle Stealing: DMA transfers one word, then releases bus. CPU gets alternating cycles. Slower but fairer.

DMA Controller Calculation Example

Problem: The size of the data count register of a DMA controller is 16 bits. The processor needs to transfer a file of 29,154 kilobytes from disk to main memory. The memory is byte addressable. The minimum number of times the DMA controller needs to get the control of the system bus from the processor to transfer the file from the disk to main memory is?

Solution:

1. File size = 29,154 KB = $29,154 \times 1024$ bytes = 29,154,096 bytes.

2. DMA data count register is 16 bits → max count per transfer = $$\displaystyle 2^{16} = 65,536 $$ bytes.

3. Minimum number of bus acquisitions = $$\displaystyle \left\lceil \frac{\text{Total Bytes}}{\text{Max Count per Transfer}} \right\rceil $$.

$$ \frac{29,154,096}{65,536} \approx 444.75 $$

4. Minimum acquisitions = 445 times.

\boxed{445}

Note: This assumes burst mode. In cycle-stealing, it would be far more (one word per acquisition).

Bus Standards Overview

Exam Focus: Know DMA calculation (data count register size limits max bytes per bus acquisition) and key differentiators between bus types (parallel vs. serial, internal vs. external, speed).