UNIT 4: COMPUTER SYSTEM ORGANIZATION - EXAM-FOCUSED NOTES

(Aligned with RGPV past papers for EC-504(C) / Computer System Organization)

** I. VON NEUMANN ARCHITECTURE**

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

Key Components:

1. Memory: Stores both instructions and data.

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

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

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

5. Registers: Fast storage inside CPU (PC, IR, MAR, MDR, Accumulator).

Stored-Program Concept:

Instructions are stored in memory as binary data and are fetched sequentially by the CU for execution.

Processing Flow:

Fetch → Decode → Execute → Store Result (Repeats in Instruction Cycle)

[!TIP] Exam Focus: Von Neumann bottleneck refers to the limited bandwidth between CPU and memory due to shared bus. Contrast with Harvard architecture (separate buses).

** II. INSTRUCTION EXECUTION CYCLE & RTL**

Phases:

1. Fetch (F): PC → MAR → Memory → MDR → IR; PC ← PC + 1

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

3. Execute (E): ALU performs operation (e.g., ADD, SHIFT). May involve memory access.

4. Write-back (W): Result written to destination register/memory.

Micro-operations: Elementary operations on data stored in registers (e.g., transfer, arithmetic, logic). Register Transfer Language (RTL): Symbolic notation to describe micro-operations. Example: R1 ← R2 + R3 (Arithmetic), MAR ← PC (Transfer)

Instruction Format Design:

• Fields: [Opcode | Address/Mode | Address/Mode]

• Addressing Bits: For n address fields of k bits each → Address space = $$\displaystyle 2^k $$ locations.

• Opcode Bits: For m instructions → Opcode bits ≥ $$\displaystyle \log_2 m $$.

[!TIP] Common Pitfall: In 2-address format, one operand is often implied (accumulator). Calculate total instruction length by summing bits for all fields.

** III. ADDRESSING MODES**

[!TIP] Exam Tip: Immediate mode has no memory access. Indirect modes require two memory accesses (fetch address, then fetch operand).

** IV. CONTROL UNIT DESIGN**

A. Hardwired Control

• Design: Combinational logic (gates) + Sequential logic (state machine). Control signals generated directly from instruction decoder and timing signals.

• Advantages: High speed (no memory access for microcode).

• Disadvantages: Inflexible, complex to design/modify, instruction set is fixed.

• Application: Simple, high-performance processors (RISC often uses hardwired).

B. Microprogrammed Control

• Design: Control signals stored as microinstructions in Control Memory (CM). A microprogram sequencer fetches and executes microinstructions.

• Microinstruction Formats:

  • Horizontal: One bit per control signal → high parallelism, large CM size.

  • Vertical: Encoded fields → smaller CM, less parallelism, slower.

• Microprogram Sequencer: Generates address of next microinstruction (incremental, conditional branches, subroutine calls).

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

• Disadvantages: Slower (extra CM access step).

Comparison Table:

[!TIP] Hybrid Approach: Use hardwired for frequently used instructions, microprogrammed for complex/rare ones.

** V. ARITHMETIC AND LOGIC UNIT (ALU)**

A. Integer Arithmetic Circuits

• Half Adder: 1-bit addition. Sum = A ⊕ B, Carry = A·B

• Full Adder: 1-bit addition with carry-in. Sum = A ⊕ B ⊕ Cin, Cout = (A·B) + (Cin·(A⊕B))

• Multi-bit Adder: Ripple-carry (slow), Carry-lookahead (fast, complex).

• Multiplication (Shift-and-Add): Repeated addition and shifting. For M × N:

  1. Initialize product = 0.

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

  3. Shift multiplicand left, multiplier right.

  4. Repeat for all bits.

• Challenges: Carry propagation delay, large area for fast multipliers (array/parallel multipliers).

B. Floating-Point Arithmetic (IEEE 754)

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

  • Single (32-bit): 1 sign, 8 exponent, 23 mantissa (Bias=127)

  • Double (64-bit): 1 sign, 11 exponent, 52 mantissa (Bias=1023)

• Addition/Subtraction Steps:

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

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

  3. Normalize Result: Shift result left/right to get 1.xxxx form; adjust exponent.

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

  5. Check for Underflow/Overflow.

• Key Difference from Integer: Needs exponent alignment and normalization; more complex hardware.

[!TIP] Exam Problem: Given two FP numbers, trace alignment and normalization steps. Remember: Exponents must match before mantissa addition.

** VI. DATA TRANSFER AND I/O ORGANIZATION**

DMA Operation Modes:

• Burst Mode: DMA takes complete control of bus for entire block transfer.

• Cycle Stealing: DMA transfers one word, then releases bus (minimizes CPU stall).

I/O Interface Functions:

• Buffering, signal conversion (serial↔parallel), protocol handling, device addressing.

Duplex Modes:

• Half-Duplex: Communication in one direction at a time (e.g., walkie-talkie).

• Full-Duplex: Simultaneous two-way communication (e.g., telephone).

Asynchronous vs. Synchronous Transfer:

• Asynchronous: Uses handshaking (REQ/ACK). No common clock. Flexible for variable-speed devices.

• Synchronous: Uses a common clock. Faster, but all devices must operate at same speed.

[!TIP] DMA Calculation: CPU time fraction = (Cycles for DMA init + Cycles for interrupt per transfer) / Total cycles for data transfer. Given data size and transfer rate, compute total cycles.

** VII. MEMORY HIERARCHY & CACHE MEMORY**

Principle of Locality:

• Temporal: Recently accessed data likely to be accessed again soon.

• Spatial: Data near recently accessed data likely to be accessed soon.

Cache Memory Parameters:

• Cache Size (C), Block Size (B), Number of Blocks (C/B), Hit (H) / Miss (M).

• Hit Ratio (h) = Hits / (Hits + Misses)

Mapping Techniques:

Cache Performance - Average Memory Access Time (AMAT):

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

Where:

• Hit Time = Time to access cache.

• Miss Penalty = Time to fetch block from main memory + possibly deliver to CPU (often ≈ Main Memory Access Time).

[!TIP] AMAT Calculation: Given Cache access = 100ns, Main memory = 1000ns, Hit ratio = 0.9:

AMAT = 100ns + (1-0.9) × 1000ns = 100ns + 100ns = 200ns.

** VIII. ADVANCED CPU DESIGN**

A. Instruction Pipelining

• Idea: Overlap execution of multiple instructions.

• Typical 5-Stage Pipeline:

  1. IF (Instruction Fetch): IR ← Mem[PC], PC ← PC+1

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

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

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

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

• Speedup (Ideal): ≈ Number of stages (n). Efficiency = Speedup / n.

• Hazards:

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

  • Data: Dependency between instructions (RAW, WAR, WAW). Solution: Forwarding/bypassing, stalls.

  • Control: Branch/jump instructions change PC. Solution: Branch prediction, delayed branch.

B. Parallel Processing & Flynn's Taxonomy

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

• SIMD: Single Instruction, Multiple Data (Vector processors, GPUs). Same operation on multiple data elements.

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

• MIMD: Multiple Instruction, Multiple Data (Multiprocessors, multicores). Independent threads.

Vector Processors:

• Have vector registers and vector functional units.

• Execute a single vector instruction on an entire array (e.g., VADD V1, V2, V3 adds corresponding elements of two vectors).

• Applications: Scientific computing, graphics, signal processing (highly data-parallel).

Inter-Processor Communication (MIMD):

• Shared Memory: Processors communicate via common memory (requires synchronization: locks, semaphores).

• Message Passing: Processors communicate via network (send/receive messages).

[!TIP] Pipeline Throughput: Max throughput = 1 instruction/cycle (if no hazards). Speedup ≤ n (number of stages) due to pipeline fill/drain overhead and hazards.

** IX. SPECIALIZED TOPICS & PRACTICAL PROBLEMS**

A. Virtual Memory & Paging

• Goal: Give each process illusion of large, contiguous private memory.

• Paging: Divide virtual & physical memory into fixed-size pages/frames.

• Page Table: Maps virtual page number → physical frame number.

• Page Fault: Required page not in memory → OS loads from disk (high penalty).

• Replacement Algorithms: FIFO, LRU (Least Recently Used), Optimal.

• Fragmentation:

  • Internal: Wasted space within allocated block (due to fixed block size).

  • External: Wasted space between allocated blocks (in variable partitioning, not in paging).

B. Common Calculation Problems

1. Cache Mapping (Direct-Mapped):

   • Index bits = $$\displaystyle \log_2 $$(Number of sets). For direct-mapped, sets = number of blocks.

   • Offset bits = $$\displaystyle \log_2 $$(Block size in bytes).

   • Tag bits = Address bits - Index bits - Offset bits.

   • Hit/Miss: Calculate Index = (Address / BlockSize) % NumBlocks. Compare Tag.

2. AMAT: Use formula above.

3. Instruction Format:

   • For k-bit instruction, with opcode (x bits), address (y bits), mode (z bits): x + y + z = k.

   • Max instructions = $$\displaystyle 2^x $$, Max addressable locations = $$\displaystyle 2^y $$.

4. Hardwired Control Logic (Boolean Expressions):

   • From truth table (Instructions × Time Steps), derive expression for each control signal.

   • Example: S5 = I1·T1 + I2·T1 + I3·T1 + I4·T1 (if S5 active in T1 for all I1-I4).

5. Microinstruction Encoding (Minimize Bits):

   • Group mutually exclusive control signals into fields.

   • Use binary encoding within each field.

   • Preserve parallelism: signals in same field cannot be active simultaneously.

6. DMA Bandwidth & CPU Overhead:

   • Total DMA transfer time = Data Size / Transfer Rate.

   • CPU cycles for init/interrupt = (Init cycles + Interrupt cycles) * Number of transfers.

   • Fraction CPU time = CPU cycles for DMA / (CPU cycles for DMA + Total DMA transfer cycles * CPU clock rate).

[!TIP] Cache Problem Strategy: Always convert addresses to binary/hex, clearly mark Tag/Index/Offset bits. For set-associative, Set Index = (Address / BlockSize) % Number of Sets.

** X. FREQUENTLY ASKED SHORT NOTES (7-Mark Questions)**

1. Von Neumann Model: Emphasize stored-program and shared bus for data/instructions. Mention bottleneck.

2. Cache Memory: Define purpose. Explain direct, associative, set-associative mapping with diagrams. State AMAT formula.

3. Pipelining: Draw 5-stage pipeline. Explain speedup and three hazards with examples.

4. DMA: Draw block diagram (CPU, DMA controller, memory, I/O). Explain cycle stealing vs burst mode. Contrast with programmed I/O and interrupt-driven.

5. Virtual Memory: Explain paging. Define page fault, page table, replacement algorithms. Benefits: larger address space, isolation.

6. Microprogrammed Control: Draw organization (Control Memory, Sequencer, Register). Compare horizontal vs vertical microinstructions. Role of sequencer.

7. I/O Processor: Offloads I/O tasks from CPU. Acts as a specialized processor for I/O channels. Enables asynchronous operation.

8. Floating-Point Representation: IEEE 754 format. Steps for addition (align, add, normalize, round). Contrast with integer.

9. Addressing Modes: List all 7 modes with one-line example and primary use case.

10. Inter-Processor Communication: In MIMD, explain shared memory (synchronization needed) and message passing.

[!TIP] For 7-mark questions: Always start with a clear definition, explain with a simple diagram/example, list advantages/disadvantages or steps, and conclude with significance/application.

Final Exam Strategy:

• High Weightage: Cache Memory, Pipelining, DMA, Control Unit (Hardwired vs Micro), Virtual Memory.

• Numericals: Practice AMAT, cache mapping (direct/set-associative), DMA time fraction, instruction format bit allocation.

• Diagrams: Von Neumann, Common Bus, 5-stage Pipeline, Cache Mapping, DMA Controller, Microprogrammed Control.

• Comparisons: Hardwired/Microprogrammed, Synchronous/Asynchronous, Half/Full Duplex, Direct/Set/Associative Cache.