UNIT 5: COMPUTER ORGANIZATION & ARCHITECTURE - EXAM-FOCUSED NOTES

I. CPU ORGANIZATION & INSTRUCTION EXECUTION

Registers & Their Roles

• Program Counter (PC):

  • Holds the memory address of the next instruction to be fetched.

  • Automatically increments after fetch (unless modified by branch/jump).

• Instruction Register (IR):

  • Holds the current instruction fetched from memory.

  • Decoder interprets the opcode and address fields from IR.

• Memory Address Register (MAR) / Memory Buffer Register (MBR):

  • MAR: Holds the address for a memory read/write operation.

  • MBR: Holds the data read from or to be written to memory.

• General Register Organization:

  • Accumulator (AC): Implicit operand for many arithmetic/logic operations (common in accumulator-based architectures).

  • Index Registers (IX): Used for indexed addressing (e.g., LOAD A(IX)). Hold displacement values.

  • Stack Pointer (SP): Points to the top of the stack in memory. Used for PUSH/POP, subroutine calls.

  • General-Purpose Registers (R0-Rn): Versatile registers for operands and addressing. Reduce memory accesses.

Fetch-Execute Cycle (Instruction Cycle)

1. Fetch: PC -> MAR -> Memory -> MBR -> IR. PC increments.

2. Decode: Control unit decodes opcode in IR. Determines operation and addressing mode.

3. Execute: Control signals activate to perform operation (e.g., ALU operation, memory read/write, register transfer).

4. Store: Results written back to destination (register or memory). Cycle repeats.

[!TIP] In hardwired control, each step corresponds to a specific clock pulse and control signal combination.

Instruction Formats & Types

• Structure: [Opcode | Address Field(s) | Mode Bits]

• Types (by number of address fields):

  • Zero-address (Stack): ADD (operands from stack). Implicit.

  • One-address: ADD A (AC is implicit second operand). AC <- AC + M[A].

  • Two-address: ADD R1, R2 (R1 <- R1 + R2). Destination is also a source.

  • Three-address: ADD R1, R2, R3 (R1 <- R2 + R3). Requires larger instruction word size.

Addressing Modes

II. CONTROL UNIT DESIGN

Hardwired Control Unit

• Structure: Combinational logic (gates) + Decoder + Sequencing logic (counters/shift registers).

• Operation: Instruction opcode directly generates control signals via logic gates. Fixed, fast timing.

• Advantages: High speed, no control memory access delay.

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

Micro-programmed Control Unit

• Concept: Control signals are stored as micro-instructions in a Control Memory (CM).

• Micro-instruction: A word where each bit (or field) is a control signal (1=activate). A sequence of micro-instructions (micro-program) implements a machine instruction.

• Micro-instruction Formats:

  • Horizontal: One bit per control signal. Long word, high parallelism, fast execution.

  • Vertical: Encoded fields (e.g., 4-bit field for 16 ALU ops). Short word, slower (needs decoding), more compact CM.

• Micro-program Sequencer: Generates address of next micro-instruction. Inputs: Current address, branch conditions (from IR, flags), subroutine stack.

• Control Word (CW): The micro-instruction itself. A bit pattern that simultaneously activates all required control signals for one micro-operation cycle.

  Example: For R1 <- R1 + R2:

  1. PC -> MAR (Control Word 1: PCout=1, MARin=1)

  2. Memory -> MBR (CW 2: Read=1, MBRin=1)

  3. MBR -> IR (CW 3: MBRout=1, IRin=1)

  4. R1out, R2out -> ALU, ALUadd, Zin (CW 4: R1out=1, R2out=1, ALU=ADD, Zin=1)

  5. Zout -> R1in (CW 5: Zout=1, R1in=1)

Comparison: Hardwired vs. Micro-programmed

III. ARITHMETIC & LOGIC UNIT (ALU) OPERATIONS

Number Representation (Signed)

• 1's Complement: Invert all bits. Range: -(2^n-1 - 1) to +(2^n-1 - 1). Two zeros (+0, -0).

  • Example (4-bit): +5 = 0101, -5 = 1010.

• 2's Complement: Invert bits + 1. Range: -(2^n-1) to +(2^n-1 - 1). Single zero.

  • Example: +5 = 0101, -5 = 1011 (1010 + 1).

  • Subtraction: A - B = A + (2's comp of B). Discard end carry.

    • 7 - 3 = 0111 + 1101 = 10100 -> 0100 (4) ✓

Arithmetic Algorithms

Booth's Algorithm (Multiplication of Signed 2's Complement)

• Idea: Recodes multiplier to reduce additions/subtractions by examining pairs of bits (Q₀, Q₋₁).

• Registers: [AC | Q | Q₋₁ | M] (M = Multiplicand). Initial Q₋₁ = 0.

• Steps per cycle (based on Q₀):

  • 00 or 11: Only Arithmetic Right Shift (ASHR) of [AC|Q|Q₋₁].

  • 01: AC <- AC - M (Add 2's comp of M), then ASHR.

  • 10: AC <- AC + M, then ASHR.

• 4-bit Example: M = 3 (0011), Q = -4 (1100)

  
  Step | AC   | Q   | Q-1 | M   | Operation
  
  0    | 0000 | 1100| 0   | 0011| Init
  
  1    | 1101 | 1100| 0   |     | 00 -> ASHR -> 1110 1100 0
  
  2    | 1110 | 1100| 0   |     | 00 -> ASHR -> 1111 0110 0
  
  3    | 0101 | 0110| 0   |     | 10 -> AC+M -> 0101+0011=1000 -> ASHR -> 1100 0011 0
  
  4    | 1111 | 0011| 0   |     | 01 -> AC-M -> 1111-0011=1100 -> ASHR -> 1110 0001 1
  
  Result = [AC|Q] = 1110 0001 = -12 (Correct: 3 * -4 = -12)
  
  

Binary Division (Restoring)

• Registers: [A | Q] (A = Accumulator, Q = Dividend/Remainder), M = Divisor.

• Steps (n times):

  1. Shift Left: [A|Q] left by 1 bit.

  2. Subtract: A <- A - M.

  3. Check: If A >= 0, set Q₀ = 1; else A <- A + M (restore), Q₀ = 0.

• Non-Restoring: Skips restore step. If A < 0, next step adds M instead of subtracting.

ALU Design & 4-bit Adder/Subtractor

• Components: 1-bit full adders (FA), multiplexers (MUX), control logic.

• 4-bit Adder/Subtractor:

  • Use 4 FA units in cascade (ripple-carry).

  • For subtraction A - B: A + (2's comp of B) = A + (B' + 1).

  • Control: S (0=Add, 1=Sub). Feed B bits through XOR with S (B XOR S = B if S=0, B' if S=1). Set Cin = S (adds the +1 for 2's comp).

  • Circuit: A[i] XOR B[i] XOR Cin -> Sum[i], Carry_out.

Fixed-Point vs. Floating-Point Arithmetic

IV. INPUT/OUTPUT ORGANIZATION & INTERFACES

I/O Interface & I/O Processor (IOP)

• Need for Interface: CPU and I/O devices have different control signals, data formats, and speeds. Interface acts as a translator/controller.

• Connection: CPU ↔ System Bus ↔ I/O Interface ↔ I/O Device.

  • Interface has data buffer, control/status registers, decoder.

• I/O Processor (IOP): A specialized processor (like a DMA controller with intelligence) that manages I/O operations independently.

  • Fetches and executes its own I/O instructions from main memory.

  • Handles device-specific protocols, data formatting, error checking.

  • CPU only involved at start/end (initiate IOP, get interrupt on completion).

Data Transfer Methods

• Handshaking (Asynchronous):

  1. Source puts data on bus, asserts Data_valid.

  2. Destination sees Data_valid, reads data, asserts Ack.

  3. Source sees Ack, removes Data_valid and data.

  4. Destination sees Data_valid low, deasserts Ack.

Direct Memory Access (DMA)

• Concept: I/O device bypasses CPU to transfer data directly to/from main memory. CPU only involved in initiation and completion (interrupt).

• Need: For high-speed devices (disk, network, graphics) to avoid CPU bottleneck.

• DMA Controller Block Diagram:

  
  [I/O Device] <-> [DMA Controller] <-> [System Bus] <-> [Main Memory]
  
                    |          |
  

| -> [CPU] (for programming, interrupt)

                  |

              [Internal Registers: MAR, MBR, Word Count, Control/Status]

```

*   **Registers:** `MAR` (memory address), `MBR` (data buffer), `WC` (word count), `Control/Status`.

• DMA Transfer Cycle (Burst Mode):

  1. CPU programs DMA: sets MAR (start addr), WC (count), control bits (read/write, enable), and gives device address.

  2. CPU continues other tasks.

  3. DMA controller takes bus control (requests via HRQ, gets HLDA from CPU).

  4. DMA performs read from device / write to memory (or vice versa) in a burst until WC=0.

  5. DMA releases bus (HLDA deasserted), sends interrupt to CPU.

Bus Structures & Standard Interfaces (COMPARISON)

• Bus Structure Concept:

  • A shared communication pathway (wires) connecting multiple components (CPU, memory, I/O).

  • Three Types of Lines:

    • Address Bus: Unidirectional (CPU->mem/I/O). Carries addresses. Width determines max addressable memory.

    • Data Bus: Bidirectional. Carries data/instructions. Width determines data transfer chunk size (e.g., 32-bit, 64-bit).

    • Control Bus: Carries control signals (Read, Write, Interrupt, Clock, Bus Request/Grant).

  • Aids Communication: Reduces wiring complexity (single set vs. point-to-point), allows modular addition of devices.

USB vs. SCSI: USB is cheaper, simpler, universal for low-to-medium speed devices. SCSI is faster, more robust, expensive for professional storage/performance-critical external devices.

V. MEMORY HIERARCHY & MANAGEMENT

Memory Hierarchy Concept

• Principle of Locality:

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

  • Spatial Locality: Items with adjacent addresses likely to be accessed together.

• Hierarchy Levels (Speed/Cost/Size): Registers → L1 Cache → L2 Cache → Main Memory (DRAM) → Secondary Storage (Disk) → Tertiary (Tape).

• Significance: Exploits locality to average access time close to fastest level while maintaining large, cheap capacity.

Cache Memory

• Role: Small, fast SRAM between CPU and main memory. Stores copies of frequently used memory blocks.

• Cache Hit/Miss: Hit = data in cache (fast). Miss = data not in cache (fetch from slower memory, penalty).

• Mapping Techniques:

  | Technique | How Main Memory Block Maps to Cache | Advantages | Disadvantages | | :--- | :--- | :--- | :--- | | Direct Mapped | Cache line = (Block addr) mod (No. of lines) | Simple, fast hardware. | High conflict misses (two blocks map to same line). | | Fully Associative | Block can go in any cache line. | Lowest conflict misses. | Complex hardware (search all lines), slow. | | Set Associative (k-way) | Cache divided into s sets. Block -> Set = (addr) mod s. Block can go in any line of that set. | Balance between direct & fully. Reduced conflicts vs. direct. | More complex than direct (search k lines). |

• Improving Cache Performance:

  1. Reduce Miss Rate: Larger cache, higher associativity, better replacement policy.

  2. Reduce Miss Penalty: Faster memory, multi-level caches (L1/L2/L3), critical word first, write buffers.

  3. Reduce Hit Time: Smaller/ simpler cache, pipelined access.

Virtual Memory & MMU

• Concept: Program uses virtual addresses larger than physical memory. Only needed parts (pages/segments) loaded into main memory. OS handles swapping.

• Need: Allows multiprogramming with large address spaces, memory protection, simplifies programming.

• Memory Management Unit (MMU): Hardware that translates virtual address → physical address on every memory reference.

  • Translation Lookaside Buffer (TLB): Fast associative cache storing recent VPN -> PFN mappings.

  • Page Table Walk: If TLB miss, MMU consults page table in memory (causes multiple memory accesses).

• Memory Segmentation: Memory divided into variable-sized logical segments (code, data, stack, heap).

  • Address: Segment Number : Offset.

  • Complements Virtual Memory: Provides logical organization and protection (segment limit check). Often combined with paging (segmented-paging).

Page Replacement Algorithms

• LRU (Least Recently Used): Replace the page not used for the longest time.

  • Idea: Based on temporal locality. Pages used recently likely to be used again soon.

  • Pseudo-code for Simulation:

    
    function LRU_Replace(page_references, num_frames):
    
        frames = []  // list of pages in frames, most recent at end
    
        page_faults = 0
    
        for page in page_references:
    
            if page in frames:
    
                frames.remove(page)  // move to most recent
    
                frames.append(page)
    
            else:
    
                page_faults += 1
    
                if len(frames) == num_frames:
    
                    frames.pop(0)  // remove least recent (front)
    
                frames.append(page)  // add new page as most recent
    
        return page_faults
    
    

• FIFO: Replace oldest page (first in). Simple but can replace frequently used pages.

• Optimal (OPT): Replace page whose next use is farthest in future. Impossible to implement in practice (requires future knowledge), used for comparison.

Secondary Storage & Semiconductor Memories

VI. MULTIPROCESSING & PARALLEL ARCHITECTURE

Multiprocessor Systems

• Characteristics: Multiple CPUs sharing memory & I/O. Tightly-coupled.

• Structures:

  • UMA (Uniform Memory Access): All CPUs have equal access time to shared memory. Symmetric Multiprocessing (SMP).

  • NUMA (Non-Uniform Memory Access): Memory physically distributed. Access time depends on memory location relative to CPU.

• Types of Data Transfer: Shared Memory (read/write common variables), Message Passing (send/receive packets over network).

Inter-Processor Communication & Synchronization

• Need: Coordinate access to shared resources (memory, I/O, data structures) to avoid race conditions.

• Structure: Shared Memory (with synchronization primitives like locks, semaphores) or Interconnection Network (for message passing).

• Synchronization Mechanisms:

  • Locks/Mutexes: Exclusive access.

  • Semaphores: Counting access permits.

  • Barriers: Wait for all processors to reach a point.

  • Atomic Operations: Test-and-set, compare-and-swap (hardware-supported).

Inter-Processor Arbitration

• Concept: Resolve conflicts when multiple processors request shared resource (bus, memory) simultaneously.

• Mechanisms:

  • Daisy Chain (Serial): Processors connected in chain. Bus Grant signal passed serially. First requesting processor gets it. Simple, but priority fixed, bottleneck.

  • Independent Requesting (Parallel): Each processor has Bus Request and Bus Grant lines. Arbiter logic selects one. Flexible priority, faster, more complex.

Array & Vector Processing

• Array Processing:

  • Definition: Use of multiple processing elements (PEs) operating in lockstep on different data elements of the same instruction stream (SIMD).

  • Structure: Attached Array Processor (external to host CPU) or Centralized Array Processor (integrated).

  • Significance: High throughput for data-parallel tasks (matrix ops, image processing).

• Vector Processing:

  • Definition: Processor with vector registers and pipelined functional units that operate on entire vectors (arrays) with single instruction.

  • Pipelined Vector Processor: Has multiple parallel functional units (e.g., 4 adders). One instruction can initiate multiple operations over time.

  • Comparison:

    • Array: Many simple PEs, each executes same instruction on its data. Good for fine-grained parallelism.

    • Vector: Fewer, more complex units. Better for streaming vector operations with long pipelines. Higher performance per PE.

Pipelining

• Concept: Divide instruction execution into stages (Fetch, Decode, Execute, Memory, Writeback). Multiple instructions in different stages simultaneously.

• Improves Throughput: Not individual instruction time, but instructions per cycle (IPC) increases.

• Layout: Stage1 | Stage2 | Stage3 | Stage4. New instruction enters Stage1 each clock cycle (ideally).

• Pipeline Hazards:

  • Structural: Resource conflict (two instructions need same unit).

  • Data: Dependency (e.g., ADD R1, R2 followed by SUB R3, R1). Solved by forwarding/bypassing or stalls.

  • Control: Branch/jump instructions cause pipeline to fetch wrong instructions. Solved by branch delay slots, branch prediction, speculative execution.

VII. ARCHITECTURAL COMPARISONS: RISC vs. CISC

[!TIP] Modern processors are hybrids. x86 (CISC) internally micro-ops and uses RISC-like pipelines. ARM (RISC) adds some complex instructions (e.g., NEON SIMD). The distinction is now more about design emphasis.