UNIT 2: Computer System Organization

I. Fundamental Computer Architecture & Instruction Processing

Von Neumann Model

• Components:

  • Memory: Stores both data and instructions (stored-program concept).

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

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

  • Input/Output (I/O): Communicates with external devices.

• Stored-Program Concept: Instructions and data reside in the same main memory and are treated as binary numbers.

• Processing Flow: Fetch-Decode-Execute Cycle.

  • Fetch: CU gets instruction from memory (address in PC) → IR.

  • Decode: CU interprets opcode in IR, determines operands and micro-ops.

  • Execute: ALU performs operation, result stored, PC updated.

• Significance: Foundation of most modern computers; enables programmability and flexibility.

[!TIP] Exam often asks for a labeled diagram. Remember: PC → MAR → Memory → MDR → IR is the fetch path.

Instruction Cycle

• Phases:

  1. Fetch (F): PC → MAR, Memory Read, MDR → IR, PC + 1 → PC.

  2. Decode (D): Control unit decodes opcode in IR, identifies addressing mode.

  3. Execute (E): ALU operates on operands (from registers/memory), result stored.

  4. Interrupt (Optional): Check for interrupts after instruction completion.

  5. Write-back (Optional): Write result back to register/memory.

• Key Registers: Program Counter (PC) holds address of next instruction. Instruction Register (IR) holds current instruction being executed.

• Flowchart: Linear sequence F → D → E with possible interrupt check and loop back to F.

Instruction Format

• Fields:

  • Opcode: Specifies operation (e.g., ADD, LOAD). Bits = $$\displaystyle \log_2 $$(# of instructions).

  • Address Fields: Specifies operand location (register or memory address).

  • Mode Bits: Specifies addressing mode.

• Length:

  • Fixed-length: All instructions same size (e.g., 32-bit). Simplifies decoding, may waste space.

  • Variable-length: Instructions vary in size (e.g., x86). Saves memory, complex decoding.

• Example Calculation: For 16-bit instruction with 6-bit opcode and one address field:

  • of distinct instructions = $$\displaystyle 2^6 = 64 $$.

  • Address bits = 16 - 6 = 10 bits → Addressable memory locations = $$\displaystyle 2^{10} = 1024 $$.

Addressing Modes

[!TIP] Impact: Immediate/Register modes → shorter/faster execution. Indirect/Indexed → more flexible but slower (extra memory access).

II. Control Unit Design

Hardwired Control

• Design: Uses decoders, logic gates (AND/OR/NOT), and timing signals from a clock and state register.

• Operation: Opcode and current state (time step) inputs → combinational logic → generates control signals (e.g., MemRead, ALUOp, RegWrite). It's a finite state machine.

• Boolean Expressions: Derived from a timing table listing required control signals for each (instruction, state) pair. Example: S5 = I1·T2 + I3·T2 + ...

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

• Disadvantages: Inflexible (changes require rewiring), complex design for large ISAs, difficult to debug.

• Suitability: RISC (simple, fixed ISA) and high-performance designs.

Microprogrammed Control

• Core Concept: Control signals are generated by executing a microprogram stored in a Control Memory (CM), typically ROM.

• Microinstruction: A word in CM. Format has three fields:

  1. Control Field: Bits for each control signal (or encoded fields).

  2. Next Address Field: Address of next microinstruction.

  3. Condition Field: For conditional branching (based on flags).

• Microprogram: A sequence of microinstructions that implements one machine instruction.

• Sequencer: Generates address for next microinstruction. Modes:

  • Increment: CAR + 1 → CAR.

  • Branch (Unconditional): Load address from Next Address field.

  • Branch (Conditional): Use Condition field to choose between increment and branch address.

  • Subroutine Call/Return: Save/restore return address.

• Encoding:

  • Horizontal: Minimal encoding; one bit per control signal. High parallelism, wide microinstructions.

  • Vertical: Field encoding; groups of mutually exclusive signals share bits. Narrower, more sequential, slower.

Comparison: Hardwired vs. Microprogrammed

RISC Characteristics (Reduced Instruction Set Computer)

• Small, simple ISA (fewer instructions, typically < 100).

• Fixed-length instruction format (e.g., 32-bit).

• Load/Store Architecture: Only load/store instructions access memory. ALU ops work only on registers.

• Few addressing modes (typically 1-2, e.g., register, immediate).

• Hardwired control is common.

• Single-cycle instruction execution or deep pipelining optimization.

• Goal: Simplify hardware for higher clock speeds and efficient pipelining.

III. Arithmetic and Logic Unit (ALU) & Data Representation

Micro-operations and Register Transfer Language (RTL)

• Micro-operation: Elementary operation on data stored in registers (e.g., transfer, arithmetic, logical, shift).

• RTL Notation: Symbolic language to describe micro-operations.

  • R2 ← R1 (Transfer)

  • R3 ← R1 + R2 (Arithmetic)

  • R4 ← R1 AND R2 (Logical)

  • R5 ← SHL R5 (Shift left)

• Example: ADD R1, R2 instruction execution in RTL:

  1. MAR ← PC (Fetch address)

  2. MDR ← Memory[MAR]

  3. IR ← MDR

  4. R1 ← R1 + R2 (Execute)

Multiplication Circuit Design

• Algorithms:

  • Shift-and-Add: Sequential. For each bit of multiplier, if bit=1, add multiplicand (shifted) to accumulator. Slow ($O(n)$ steps for $n$-bit).

  • Array Multiplier: Combines multiple adders in parallel (e.g., using full adders). Fast but large hardware ($$\displaystyle O(n^2) $$ gates).

  • Booth's Algorithm: Recodes multiplier to reduce number of additions/subtractions (handles signed numbers). Uses shifting and conditional add/subtract.

• Challenges:

  • Speed: Propagation delay through adders limits clock rate.

  • Hardware Complexity: Trade-off between speed (parallel) and area (gate count).

  • Partial Products: Generation and summation of many partial products.

Floating-Point Representation and Arithmetic (IEEE 754)

• Format (Single Precision, 32-bit):

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

  • Exponent (8 bits): Biased (bias = 127). Stored value = actual exponent + 127.

  • Mantissa/Fraction (23 bits): Normalized binary number with implicit leading 1 (hidden bit). Represents $1.F$.

  • Value = $$\displaystyle (-1)^S \times 1.F \times 2^{(E - 127)} $$.

• Special Values:

  • Zero: E=0, F=0.

  • Infinity (∞): E=255, F=0.

  • NaN (Not a Number): E=255, F≠0 (invalid operation).

• Floating-Point Addition/Subtraction Steps:

  1. Align Exponents: Find larger exponent. Shift mantissa of smaller exponent right until exponents equal. (Loss of precision possible).

  2. Add/Subtract Mantissas: Perform operation on aligned mantissas (consider sign bits).

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

  4. Round: Apply rounding mode (e.g., round to nearest even) to fit mantissa field. May cause re-normalization.

  5. Check for Overflow/Underflow: Exponent too large/small.

• Flowchart: Align → Operate → Normalize → Round → Check.

Basic ALU Design

• Half Adder (1-bit):

  • Sum = $A \oplus B$, Carry = $A \cdot B$.

  • Truth table and logic diagram.

• Full Adder (1-bit):

  • Sum = $$\displaystyle A \oplus B \oplus C_{in} $$, Carry = $$\displaystyle (A \cdot B) + (C_{in} \cdot (A \oplus B)) $$.

  • Can be built from two half-adders + OR gate.

• n-bit ALU:

  • Cascade full adders for arithmetic unit.

  • Use multiplexers to select operation (ADD, SUB, AND, OR, etc.) based on control signals (ALUOp).

  • Typical block: Operand inputs → Functional units (adder, logic gates) → MUX → Result & Zero/Overflow flags.

IV. Input/Output (I/O) Systems and Data Transfer

Data Transfer Modes

[!TIP] Key Difference: Polling = CPU active wait. Interrupt = CPU notified per byte/word. DMA = CPU out of data path for block.

I/O Interface

• Role: Buffer (temporary storage), Signal conversion (voltage levels), Protocol handling (handshaking), Address decoding.

• Asynchronous Data Transfer (Handshaking):

  • Source places data, asserts Data Valid.

  • Destination reads data, asserts Data Accepted.

  • Source deasserts Data Valid after seeing Data Accepted.

  • Ensures reliable transfer without shared clock.

• Synchronous: All devices synchronized to a common clock. Simpler but requires fixed timing.

I/O Processor (IOP)

• Dedicated processor (e.g., channel, GPU, disk controller) that handles I/O tasks independently.

• Operation: CPU initializes IOP with I/O program (list of commands). IOP fetches/executes its own instructions, manages devices, transfers data to/from memory (often using DMA), and interrupts CPU on completion.

• Role in Modern Systems: Offloads I/O-intensive tasks (graphics rendering, disk scheduling, network packet processing), freeing CPU for computation. Examples: GPU, SSD controller, NIC.

Duplex Communication Modes

• Half-Duplex: One-way communication at a time. Devices take turns transmitting (e.g., walkie-talkie, early Ethernet). Requires channel turnaround time.

• Full-Duplex: Simultaneous two-way communication (e.g., telephone, modern Ethernet, PCIe). Requires separate channels or frequency division.

DMA Controller Interfacing & CPU Overhead Calculation

• Block Diagram:

  • Registers: DR (Data Register), AR (Address Register), CR (Count Register), Control/Status Register.

  • Interfaces: To system bus (as master), to I/O device (as slave).

  • Bus Arbitration: Requests and gains control of system bus.

• Operation:

  1. Initialization: CPU programs DMA (source addr, dest addr, byte count), sets start bit.

  2. Transfer Cycles: DMA reads from source, writes to dest, decrements count, repeats until count=0. May use burst mode or cycle stealing.

  3. Completion: DMA interrupts CPU.

• CPU Overhead Calculation (from Nov 2022 paper):

  • Total CPU cycles per DMA transaction = Initiation cycles + (Interrupt handling cycles).

  • Total cycles for all data transfers = (Data size / Transfer size per interrupt) × (Init cycles + Interrupt cycles).

  • Fraction of CPU time = (Total CPU cycles for DMA) / (Total CPU cycles during transfer period).

  • Example: 10 MB data, 4 KB pages → 2500 transfers. Init = 1000 cycles, Interrupt = 1500 cycles. CPU = 200 MHz. Total DMA CPU cycles = 2500 × (1000+1500) = 6.25e6 cycles. Time for data transfer at device rate (10 MB/s) = 10e6 bytes / 10e6 bytes/s = 1 s. Total CPU cycles in 1s = 200e6. Fraction = 6.25e6 / 200e6 = 0.03125 (3.125%).

V. Memory Hierarchy and Organization

Memory Hierarchy Concept

• Levels: Registers (fastest, smallest) → L1/L2/L3 Cache → Main Memory (RAM) → Secondary Storage (SSD/HDD) (slowest, largest).

• Principle of Locality:

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

  • Spatial Locality: Access to an item likely to be followed by access to nearby items.

• Significance: Exploits locality to provide large, cheap, slow memory with performance approaching small, fast, expensive memory. Reduces average access time and cost per bit.

Cache Memory

• Organization:

  • Cache Line/Block: Smallest unit of transfer between cache and memory (e.g., 64 bytes).

  • Tag: Portion of memory address stored to identify which block is cached.

  • Valid Bit: Indicates if cache line contains valid data.

  • Dirty Bit (Write-back): Indifies if cache line has been modified.

• Mapping Techniques (Address breakdown: Tag | Set Index | Block Offset):

  • Direct-Mapped: Each memory block maps to exactly one cache line (set). Set Index = (Block Address) mod (# of cache sets).

    • Simple, fast. But conflict misses if two hot blocks map to same line.

  • Set-Associative: Cache divided into sets, each set holds n blocks (n-way). Block maps to a set, can go in any line within set.

    • n-way set-associative is a compromise. Set Index = (Block Address) mod (# of sets). Tag must be compared with all n tags in set in parallel.

  • Fully Associative: Block can be placed in any cache line. Requires all tags compared in parallel (content-addressable). Highest flexibility, highest hardware cost.

• Performance Metrics:

  • Hit Ratio (h): Fraction of memory accesses found in cache. Miss Ratio (m) = 1 - h.

  • Average Memory Access Time (AMAT):

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

    *   `Hit Time` = Time to access cache.

    *   `Miss Penalty` = Time to replace a block from memory + access it (includes transfer time).

*   **Example**: Cache hit = 100 ns, miss penalty = 1000 ns, hit ratio = 0.9 → AMAT = 100 + 0.1×1000 = **200 ns**.

• Replacement Policies (on a miss when cache full):

  • LRU (Least Recently Used): Replace block not used for longest time. Good temporal locality, expensive to implement (need timestamps/stack).

  • FIFO (First-In-First-Out): Replace oldest block. Simple, may replace frequently used block.

  • Random: Pick random block. Simple, surprisingly effective.

• Write Policies:

  • Write-through: Write to cache and main memory simultaneously. Simple, consistent, but high memory traffic.

  • Write-back: Write only to cache. Mark line dirty. Write to memory only when dirty line is evicted. Reduces memory traffic, but complex (need dirty bits, write-back on eviction).

• Example Cache Problem (Nov 2022):

  • Given access sequence, cache size, block size, associativity → compute hits/misses.

  • Steps:

    1. Calculate number of blocks = Cache Size / Block Size.

    2. For Direct-mapped: Set Index = (Address / Block Size) mod (# of blocks). Track each set's tag and valid bit.

    3. For Set-Associative: Set Index = (Address / Block Size) mod (# of sets). Within set, use LRU/FIFO to choose victim.

    4. For Fully Associative: Any block can hold any address. Use replacement policy on full cache.

  • Example: 4 blocks, 1-word blocks, addresses: 433, 435, 536, 535, 443, 444, 551, 538, 539, 553.

    • Direct-mapped (4 sets): Block index = address mod 4. 433%4=1, 435%4=3, 536%4=0, 535%4=3 (hit), 443%4=3 (miss), 444%4=0 (miss), 551%4=3 (miss), 538%4=2 (miss), 539%4=3 (miss), 553%4=1 (miss). Total Misses = 9.

    • 2-way set-assoc (2 sets): Sets = 2. Set index = address mod 2. Use LRU per set. (Detailed tracking needed, but typically fewer misses than direct-mapped).

    • Fully associative FIFO (4 blocks): Fill cache in order, evict oldest. (Typically fewer misses than set-assoc).

Memory Mapping

• Memory-Mapped I/O: I/O device registers are assigned addresses in the same address space as main memory. CPU uses LOAD/STORE instructions to access devices.

  • Advantages: No special I/O instructions, all memory access instructions work, easier to program.

  • Disadvantages: Consumes memory address space, need protection mechanisms.

• Isolated (Port-Mapped) I/O: I/O devices have a separate address space (I/O ports). Special instructions (IN, OUT) access ports.

  • Advantages: Does not reduce memory address space, simpler protection.

  • Disadvantages: Requires separate instruction set, less flexible.

• Effect on Program Execution: Memory-mapped I/O simplifies programming but requires OS to manage address space allocation to avoid conflicts. Isolated I/O keeps memory space pure but adds instruction complexity.

Virtual Memory

• Concept: Gives each process the illusion of a large, contiguous address space larger than physical memory. Uses secondary storage (disk) as backing store.

• Paging:

  • Pages: Fixed-size blocks of virtual address space.

  • Frames: Fixed-size blocks of physical memory (same size as page).

  • Page Table: Per-process table mapping virtual page number → physical frame number. Stored in memory.

  • Translation Lookaside Buffer (TLB): Small, fast associative cache for page table entries (VPN → PFN). Speeds up translation.

  • Translation: Virtual Address → (VPN, offset) → TLB lookup → if miss, walk page table → get PFN → Physical Address = (PFN × Frame Size) + offset.

• Segmentation:

  • Segments: Variable-sized blocks corresponding to logical units (code, data, stack).

  • Segment Table: Per-process table mapping segment number → base address + limit.

  • Provides protection (limit check) and sharing (multiple processes map same segment).

• Benefits:

  • Larger address space than physical memory.

  • Memory Protection: Hardware checks access rights (read/write/execute) via page/segment tables.

  • Sharing: Multiple processes can map same physical page/segment (e.g., shared libraries).

  • Simplified Allocation: No need for contiguous physical allocation.

• Fragmentation:

  • Internal Fragmentation: Wasted space within an allocated block (e.g., last page of a process not full). Common in paging (fixed-size pages).

  • External Fragmentation: Free memory exists but is in small, non-contiguous pieces, too small for allocation request. Common in segmentation (variable-size segments).

VI. Advanced Processor Architectures and Parallelism

Instruction Pipelining

• Principle: Overlap execution of multiple instructions by dividing the instruction cycle into pipeline stages (segments). Each stage works on a different instruction simultaneously.

• Typical 5-Stage Pipeline (RISC):

  1. IF (Instruction Fetch): PC → MAR, read memory, PC+1.

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

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

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

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

• Throughput: Ideally, one instruction completes per clock cycle after pipeline fill (CPI ≈ 1).

• Hazards (Pipeline Stalls):

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

  • Data Hazard: Dependency between instructions (e.g., ADD R1, R2 followed by SUB R3, R1). Solutions:

    • Forwarding/Bypassing: Route result from EX/MEM or MEM/WB stage directly to ALU input of dependent instruction.

    • Stall (Bubble): Insert no-op until data ready.

  • Control Hazard: Branch instruction changes PC, instructions after branch may be wrong. Solutions:

    • Branch Delay Slot: Execute instruction after branch regardless (wasted slot).

    • Branch Prediction: Predict taken/not-taken, speculatively execute.

    • Flush: Discard incorrectly fetched instructions if prediction wrong.

• Advantages: Increased throughput, better hardware utilization.

• Limitations: Hazards reduce ideal speedup. Pipeline depth increase → more stalls from hazards and branch mispredictions.

Vector Processing

• Concept: Process vectors (arrays) with a single instruction. Instruction operates on entire vector registers (e.g., 64 elements).

• Vector Registers: Special wide registers holding multiple data elements (e.g., 64×64-bit).

• Vector Operations: VADD V1, V2, V3 adds corresponding elements of V2 and V3, stores in V1.

• Architecture: Vector pipelines for functional units. Chaining: Result of one vector op can feed next before entire vector written (pipelined vector ops).

• Comparison with Scalar:

  • Scalar: One data element per instruction (e.g., loop of adds). High instruction fetch/decode overhead.

  • Vector: Single instruction for entire array. Reduced instruction overhead, better memory bandwidth utilization (streaming access).

• Application Areas: Scientific computing (matrix ops), multimedia (image/audio processing), signal processing, AI/ML kernels. Examples: Cray supercomputers, GPU SIMD units.

Multiprocessor Systems

• Flynn's Taxonomy:

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

  • SIMD: Single Instruction, Multiple Data (vector processors, GPU cores). Same instruction on multiple data elements.

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

  • MIMD: Multiple Instruction, Multiple Data (common multiprocessors). Each processor has own instruction stream. Can be shared memory or distributed memory.

• Inter-Processor Communication:

  • Shared Memory: All processors access global memory.

    • Bus-Based: All share a bus. Snooping caches maintain coherence (write-invalidate/write-update protocols).

    • Scalability Issue: Bus becomes bottleneck.

  • Message Passing: Processors have private memory, communicate via network (send/receive messages). Used in distributed memory systems (clusters).

• Interconnection Networks:

  • Shared Bus: Simple, low cost. Arbitration needed, limited bandwidth.

  • Crossbar Switch: Dedicated path between any pair. Non-blocking, fast, but expensive ($$\displaystyle O(n^2) $$ switches).

  • Hypercube: Processors at vertices of n-cube. Logarithmic diameter, scalable. Used in some parallel machines.

Interconnection Structures (Summary)

• Shared Bus: Multiple devices share lines. Bus Arbiter grants control. Simple, but bandwidth shared, contention.

• Multi-Port Memory: Memory with multiple independent read/write ports. Allows simultaneous access but complex and expensive.

• Crossbar Switch: Matrix of switches connecting n inputs to n outputs. Non-blocking, high performance, high cost.

• Hypercube: $$\displaystyle 2^n $$ nodes, each connected to $n$ neighbors. Scalable, good bisection bandwidth, complex routing.

VII. Special Topics and Problem-Solving

Associative Memory vs Cache

Common Bus System Architecture

• Diagram: Multiple registers (PC, IR, MAR, MDR, etc.) and memory connected to a common set of bus lines (address, data, control).

• Operation: Multiplexers select which unit's output drives the bus. Control signals (from CU) enable outputs onto bus and select destination register's load signal.

• Example: MDR → Bus → MAR transfer: Control signals enable MDR output, MAR load. PC → Bus → MAR requires different control signals.

• Significance: Reduces number of physical connections, standardizes communication.

Synchronous vs Asynchronous Data Transfer

I/O Bandwidth and Performance Calculations

• Bus Bandwidth = Clock Frequency × Data Width (bits per transfer).

  • Example: 33 MHz, 32-bit bus → Bandwidth = 33e6 × 32 / 8 = 132 MB/s.

• Device Requirement: Compare device's maximum sustained transfer rate (e.g., 40 MB/s) with bus bandwidth.

• Justification: If device requirement < bus bandwidth, bus can theoretically handle it (ignoring overhead, multiple devices). If >, bus is bottleneck.

  • Example (Nov 2022): Bus = 33 MHz × 32-bit = 132 MB/s. Video card needs 128 MB/s. Yes, possible because 128 < 132, but marginal; overhead (addressing, control) may make it infeasible in practice.

Floating-Point Addition Flowchart

1. Start

2. Unpack operands: Get sign (S1, S2), exponent (E1, E2), mantissa (M1, M2 with hidden bit).

3. Compare Exponents: ΔE = E1 - E2. Determine larger exponent E_max.

4. Align Mantissas: Shift mantissa of smaller exponent right by |ΔE| bits. (May lose LSBs).

5. Add/Subtract Mantissas: If signs equal → add. If signs different → subtract. Compute sum/difference M_sum, new sign S_sum.

6. Normalize: Shift M_sum left/right to restore leading 1. Adjust E_max accordingly. Handle underflow/overflow.

7. Round: Apply rounding to M_sum to fit fraction field. May cause re-normalization.

8. Pack Result: Combine S_sum, rounded exponent, rounded mantissa.

9. Check for Special Cases: Zero, infinity, NaN.

10. End

Micro-instruction Encoding

• Goal: Minimize control bits while preserving inherent parallelism (micro-ops that can occur simultaneously).

• Field Encoding (Vertical): Group mutually exclusive control signals into fields. Each field encoded with fewer bits (e.g., 4 mutually exclusive signals → 2 bits).

• Example (from Nov 2022 table):

  • Signals: a,b,c,d,e,f,g,h,i,j.

  • Find groups where signals never appear together in same microinstruction.

  • From table:

    • I1: a,b,c,d,e

    • I2: a,d,f,g

    • I3: b,h

    • I4: c

    • I5: c,e,g,i

    • I6: a,h,j

  • Analysis:

    • a appears with b,c,d,e (I1) and with d,f,g (I2) and with h,j (I6). So a can be with d, but not with h? Check: I1 has a,b,c,d,e; I6 has a,h,j → a and h can coexist? No, I1 has a, I6 has a and h, but no single instruction has both a and h? I6 has a and h together. So a and h can be together (in I6). Need to find signals that never appear together.

    • Better approach: Build compatibility matrix. Signals that can be active together in some instruction can share a field only if they are never mutually exclusive? Actually, for field encoding, signals in same field must be mutually exclusive (never 1 at same time). So we group signals that never appear together in any microinstruction.

    • From table:

      • b and f: I1 has b, I2 has f → no overlap? But need to check all pairs. b appears in I1, I3. f appears in I2. No instruction has both b and f → can be in same field.

      • This is a compatibility graph problem. Signals are nodes, edge if they can be together. Then find coloring (minimum colors) where each color = field. But simpler: list groups where no two signals in group ever appear together.

    • Manual grouping (one possible solution):

      • Group 1: a, b, c, i (Check: a with b? I1 yes. a with c? I1 yes. a with i? I5 has c,e,g,i but no a; I6 has a,h,j no i. So a and i never together? I1: a,b,c,d,e; I5: c,e,g,i; I6: a,h,j. No instruction has both a and i. b and i? I1 has b, I5 has i, no overlap. c and i? I5 has both c and i! Conflict. So c and i cannot be in same field.

      • This is complex without systematic method. Typical exam expects: Identify fields like ALU_Op (ADD, SUB, etc.), Reg_Src (select register source), etc., based on micro-ops that are mutually exclusive.

    • Simplified Example Answer:

      • Field 1 (Register selection): Signals for selecting source/dest register (e.g., R1_out, R2_in). Mutually exclusive.

      • Field 2 (ALU operation): ALU_Add, ALU_Sub, ALU_And etc.

      • Field 3 (Memory control): MemRead, MemWrite.

      • Field 4 (PC control): PC_Inc, PC_Load.

      • Number of bits = sum of log2(size of each field).

Cache Performance Problem (AMAT)

• Given: Separate I-cache and D-cache or unified? Usually separate.

• Formula for Unified Cache:

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

• For Split I/D Caches (common):

  • Instruction AMAT = I-Hit Time + I-Miss Rate × I-Miss Penalty

  • Data AMAT = D-Hit Time + D-Miss Rate × D-Miss Penalty

  • Overall AMAT depends on instruction/data access mix.

  • Example (from Nov 2022): 16KB I-cache, 16KB D-cache. Hit cycle = 1, Miss cycle = 50. 75% read (assume data access?), 25% write? Actually: "75% read access and 25% write access". Likely for data cache. Read miss rate = 0.64%, Write miss rate = 6.47%.

    • Data Access AMAT = 1 + (0.0064 × 50) for reads? But writes may have different penalty. Typically, write-through: write miss may write to memory immediately. Write-back: write miss may allocate block then write.

    • Assuming write-through and write miss penalty similar to read miss (50 cycles):

      • Read AMAT = 1 + 0.0064 × 50 = 1 + 0.32 = 1.32 cycles

      • Write AMAT = 1 + 0.0647 × 50 = 1 + 3.235 = 4.235 cycles

    • Weighted by access type: 75% reads, 25% writes → AMAT_data = 0.75×1.32 + 0.25×4.235 = 0.99 + 1.05875 = 2.04875 cycles.

    • If also considering instruction cache (no data given), assume perfect I-cache or separate. Question likely asks for data cache AMAT given the read/write percentages.

Hardwired Control Boolean Expression Example (from Nov 2022)

• Given timing table for 4 instructions (I1-I4) over 5 time steps (T1-T5) with control signals S1-S10.

• Task: Find Boolean expression for S5, S6, S10.

• Method:

  1. For each signal, list all (Instruction, Time Step) pairs where signal is 1.

  2. Let I1, I2, I3, I4 be 1-hot signals for current instruction.

  3. Let T1, T2, T3, T4, T5 be 1-hot signals for current time step.

  4. Expression = Sum (OR) of products (AND) of relevant I and T terms.

• Example from table:

  • S5: I1-T1, I1-T3, I2-T1, I2-T3, I3-T1, I4-T1, I4-T3.

    → S5 = I1·T1 + I1·T3 + I2·T1 + I2·T3 + I3·T1 + I4·T1 + I4·T3

  • S6: I1-T2, I2-T3, I2-T4, I3-T3, I4-T2, I4-T4.

    → S6 = I1·T2 + I2·T3 + I2·T4 + I3·T3 + I4·T2 + I4·T4

  • S10: I1-T4, I2-T2, I2-T5, I3-T2, I3-T4, I4-T2, I4-T5.

    → S10 = I1·T4 + I2·T2 + I2·T5 + I3·T2 + I3·T4 + I4·T2 + I4·T5

Virtual Memory Fragmentation

• Internal Fragmentation: Wasted space inside allocated region.

  • Cause: Fixed-size allocation units (pages, segments with rounding).

  • Example: Last page of a 5.2 KB process in a 4 KB paging system uses 0.8 KB, wastes 3.2 KB.

  • Mitigation: Smaller page sizes (but increases page table size), segmentation.

• External Fragmentation: Free memory exists but is scattered in small holes between allocated blocks.

  • Cause: Variable-size allocation (segmentation) with allocation/deallocation.

  • Example: After many allocations/frees, 100 KB free but in 10 KB pieces, cannot satisfy 50 KB request.

  • Mitigation: Compaction (move processes to gather free memory), paging (eliminates external fragmentation by fixing frame size, but causes internal).

Microprogram Sequencer

• Role: Generates microinstruction address (CAR) for control memory.

• Inputs: Current CAR, IR (for opcode), Condition signals (from ALU flags), Subroutine stack.

• Modes:

  • Increment: CAR + 1 → CAR (next sequential microinstruction).

  • Branch (Unconditional): Load CAR from Next Address field.

  • Branch (Conditional): If Condition true → branch address; else → increment.

  • Subroutine Call: Push current CAR+1 onto stack, load branch address.

  • Return: Pop stack → CAR.

• Block Diagram: Control Memory → Microinstruction → (Control signals, Next Address, Condition) → Sequencer Logic (with multiplexers for address source) → CAR. Stack for returns.

DMA Controller Block Diagram

• Components:

  • Data Buffer (temporary storage).

  • Address Register (AR): Holds memory address for transfer.

  • Count Register (CR): Number of bytes/words to transfer.

  • Control/Status Register (CSR): Start/stop control, interrupt enable, status bits (busy, error).

  • Interrupt Logic: Signals CPU on completion.

  • Bus Interface: Bus Master logic (requests bus, drives address/data lines).

  • I/O Interface: Connects to device (often FIFO).

• Operation:

  1. CPU programs AR, CR, CSR (sets start bit).

  2. DMA requests bus (via bus arbiter).

  3. Once bus granted, DMA reads from I/O device → buffer → writes to memory (or vice versa), updating AR, CR.

  4. When CR=0, DMA releases bus, raises interrupt.

  5. CPU handles interrupt, checks status.

Associative Memory (Content-Addressable Memory)

• Access Method: Specify data/content, memory returns address(es) where it is stored (or the data itself).

• Operation: All cells compared in parallel with input key. Matching lines activate.

• Use in Computer Systems:

  • Cache Tags: To find if a memory block is in cache (compare tag with all cache tags in parallel).

  • TLB: To translate virtual page number to physical frame number quickly.

  • Router Forwarding Tables: Match IP destination address.

• Advantage: Very fast search (O(1) for lookup).

• Disadvantage: Expensive (per cell has comparator), high power, limited size.

Synchronous vs Asynchronous Data Transfer (Recap)

• Synchronous: All transfers occur on clock edges. Devices must be ready at specified times. Used for memory buses, CPU internal buses. Requires wait states if device slower.

• Asynchronous: Uses handshaking (Strobe/Acknowledge or Data Valid/Data Accepted). No common clock. Flexible for I/O devices with variable speeds.

Common Bus System (Recap)

• Structure: Shared address, data, control lines.

• Control: Multiplexers select source for data bus. Decoders generate load signals for destination registers based on control signals.

• Diagram: Show registers (PC, IR, MAR, MDR, GPRs) with outputs to bus via 3-state buffers, inputs from bus. Control unit generates PC_in, MAR_in, MDR_out, etc.

Four-Segment Instruction Pipeline (Example)

1. F (Fetch): MAR ← PC, read memory, MDR → IR, PC + 1 → PC.

2. D (Decode): Decode opcode, read source registers A ← Reg[IR[rs1]], B ← Reg[IR[rs2]].

3. E (Execute): ALU operates: ALUout ← A op B or ALUout ← A + offset (for branch).

4. M (Memory): For load/store: MDR ← Memory[ALUout] (load) or Memory[ALUout] ← B (store).

5. W (Write-back): Reg[IR[rd]] ← ALUout or Reg[IR[rd]] ← MDR (for load).

[!TIP] Pipeline depth can vary (e.g., 5-stage common for RISC). More stages → higher clock frequency but more hazards.