UNIT 4: Computer Organization & Architecture - Short Notes

I. FUNDAMENTAL COMPUTER ORGANIZATION & INSTRUCTION CYCLE

★ Fetch-Execute Cycle (Instruction Cycle)

The fundamental process by which a CPU retrieves, decodes, and executes instructions. It consists of four primary phases:

1. Fetch: The CPU fetches the next instruction from memory.

   • PC (Program Counter) holds the address of the next instruction.

   • MAR (Memory Address Register) is loaded with the contents of PC.

   • Memory places the instruction (at address in MAR) into MDR (Memory Data Register).

   • MDR's content is transferred to IR (Instruction Register).

   • PC is incremented to point to the next instruction.

2. Decode: The control unit decodes the opcode in the IR to determine the operation and required operands.

3. Execute: The CPU performs the operation (e.g., ALU computation, memory access, I/O).

4. Store (Write-back): Results are written back to a register or memory location.

[!TIP] Exam Focus: Be prepared to draw the sequence and state the role of PC, IR, MAR, MDR in each step. A common question is to "Discuss the structure and role of PC, IR, and MAR/MDR during fetch-execute."

General Register Organization

Registers are fast storage locations within the CPU.

Instruction Formats

An instruction is typically divided into fields:

• Opcode (Operation Code): Specifies the operation (e.g., ADD, LOAD).

• Address Field(s): Specifies the location of operand(s) (register or memory).

• Mode Bits: Specifies the addressing mode for the address field(s).

Common Organizations:

• 0-Address (Stack): ADD (Operands implicit from stack).

• 1-Address (Accumulator): ADD R1 (AC is implicit operand).

• 2-Address: ADD R1, R2 (Result overwrites one source).

• 3-Address: ADD R1, R2, R3 (R1 ← R2 + R3).

Addressing Modes

Determines how the operand address is calculated from the address field.

[!TIP] Common Pitfall: Confusing Indirect (address field → memory → address) with Register Indirect (address field → register → memory).

II. CONTROL UNIT DESIGN

★ Hardwired vs. Microprogrammed Control Unit

Control Word & Micro-operations

• Micro-operation: The smallest unit of control (e.g., PC ← PC + 1, MDR ← Memory[MAR]).

• Control Word (CW): A binary word where each bit (or group) controls a specific functional unit (e.g., PC_in=1, ALU_Op=ADD, MemRead=1).

• Role: A sequence of control words (a microprogram) defines the complete behavior of each machine instruction.

[!TIP] Exam Example: "Illustrate with an example." For the fetch cycle, a control word sequence could be:

1. PC_out=1, MAR_in=1 (Place PC on address bus, load MAR)

2. MemRead=1, MDR_in=1 (Read memory, load MDR)

3. MDR_out=1, IR_in=1 (Place instruction in IR)

4. PC_in=1, ALU_Op=INC (Increment PC)

Micro-instruction Formats

Control Memory & Micro-instruction Sequencing

• Control Memory (CM): Stores the microprogram. Addressed by a Micro-program Counter (μPC).

• Sequencer: Determines the next μPC address.

  • Next Address Logic: Typically μPC ← μPC + 1 (sequential) unless:

    • Branch/Jump: Based on branch conditions (e.g., IR opcode, ALU zero flag) and branch address field in current microinstruction.

    • Call/Return: For subroutines (push/pop return address).

III. DATA REPRESENTATION & ARITHMETIC

★ Number Systems & Complements

• Sign-Magnitude: MSB is sign (0=+, 1=-). Remaining bits are magnitude. Two representations for zero.

• 1's Complement: Negative of N is ~N (bitwise complement). Range: -(2^{n-1}-1) to +(2^{n-1}-1). End-around carry in addition.

• 2's Complement: Negative of N is 2^n - N (or ~N + 1). Most widely used. Range: -2^{n-1} to +(2^{n-1}-1). Single zero. Addition/subtraction use same circuitry.

Subtraction using 2's Complement:

To compute A - B:

1. Form 2's complement of B (-B).

2. Add A + (-B).

3. Discard any carry out from MSB.

Example: 7 - 5 (4-bit): 0111 + 1011 = 10010 → Discard carry → 0010 (2). ✓

★ Fixed-Point vs. Floating-Point Arithmetic

★ Booth's Algorithm for Multiplication (Signed 2's Complement)

Goal: Efficiently multiply two signed binary numbers by examining pairs of bits to reduce additions.

Algorithm Steps (for multiplier Q):

1. Initialize: AC=0, Q[-1]=0, Count=n, M=Multiplicand, Q=Multiplier.

2. Examine Q0 and Q[-1]:

   • 00 or 11 → Arithmetic Right Shift (AC, Q, Q[-1] as one register).

   • 01 → AC ← AC + M then Arithmetic Right Shift.

   • 10 → AC ← AC - M (add 2's complement of M) then Arithmetic Right Shift.

3. Decrement count. Repeat until count=0.

4. Result is in (AC, Q).

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

Binary Division (Restoring)

Algorithm Steps:

1. Initialize: Remainder (A)=0, Divisor (M), Dividend (Q), Count=n.

2. Shift Left: A, Q as one register, shift left by 1.

3. Subtract: A ← A - M.

4. Test: If A >= 0 (sign bit 0), set Q0=1. Else (A < 0), set Q0=0 and Restore: A ← A + M.

5. Decrement count. Repeat until count=0.

6. Quotient in Q, Remainder in A.

Non-Restoring: Skips the restore step; next step uses A+M or A-M based on previous sign. Slightly faster.

ALU Design (4-bit Adder/Subtractor)

A basic 4-bit ALU for addition/subtraction uses:

• Four 1-bit full adders (FA) cascaded.

• Control input S (0=Add, 1=Subtract).

• For subtraction (A - B), we compute A + (2's complement of B).

• Implementation: Use XOR gates to conditionally invert B bits when S=1. The LSB carry-in is set to S (1 for subtract).

      S ────┐    ┌───┐

            ├───►│XOR│───► B'[i]

      B[i] ─┘    └───┘

Circuit: B'[i] = B[i] XOR S. C_in = S for LSB FA. Outputs: Sum[i], Carry_out.

IV. BUS STRUCTURES & I/O SYSTEMS

★ Bus Structure

A bus is a shared communication pathway connecting multiple components (CPU, memory, I/O).

• Address Bus: Carries memory/I/O addresses (unidirectional, from CPU).

• Data Bus: Carries data (bidirectional).

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

• Types:

  • Dedicated: Separate lines for each function (e.g., separate address & data lines).

  • Multiplexed: Same lines carry different info at different times (e.g., address then data). Saves pins, needs more control.

[!TIP] Exam Focus: "Illustrate the concept of bus structure." Draw a simple diagram with CPU, Memory, I/O connected via Address, Data, Control lines. Explain how CPU uses address bus to select a device, data bus to transfer, control bus to specify operation (Read/Write).

Data Transfer Methods

★ I/O Interfaces & Buses (Comparative Analysis)

[!TIP] Exam Focus: "How does USB differ from SCSI?" Use the table above. Key points: USB is host-controlled, cheap, universal; SCSI is peer-to-peer, expensive, high-performance storage. "How does PCI improve I/O performance?" → Bus Mastering allows devices to transfer data directly to memory without CPU intervention (DMA-like), Burst mode transfers blocks efficiently.

★ Direct Memory Access (DMA)

Need: To transfer large blocks of data between I/O and memory without CPU intervention, freeing CPU for other tasks. Working Principle:

1. CPU initializes DMA controller (DMA): sets source, destination address, transfer count.

2. CPU issues "start DMA" command.

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

4. DMA performs data transfer: Read from I/O port → Write to memory (or vice-versa).

5. After transfer, DMA releases bus and interrupts CPU.

Cycle Stealing Mode: DMA controller "steals" a bus cycle from the CPU when CPU is not using it (e.g., during CPU's internal operation). Minimizes impact on CPU performance.

Block Diagram:

CPU <---> [DMA Controller] <---> I/O Device

         |            |

         V            V

      [Memory]    [Byte Count]

• DMA Controller Registers: Source Address, Destination Address, Byte Count, Control/Status.

• Interrupt Line: To signal completion to CPU.

I/O Processor (IOP)

A specialized processor dedicated to managing I/O operations for a set of devices.

• Need: To offload complex I/O tasks (e.g., disk controller logic, network protocol processing) from the main CPU.

• Working: CPU sends high-level I/O commands to IOP. IOP fetches its own instructions (from its local memory) to handle the device protocol, data formatting, error checking, and transfers data to/from main memory (often using DMA). CPU is only interrupted on completion or error.

• Role: Greater autonomy than DMA controller. Can execute I/O programs. Used in high-end systems (e.g., mainframes, GPUs as IOPs for graphics).

V. MEMORY SYSTEMS & HIERARCHY

Memory Hierarchy Concept

Based on the Principle of Locality:

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

• Spatial Locality: Items whose addresses are close to recently accessed items are likely to be accessed soon.

Hierarchy: Registers → Cache → Main Memory (RAM) → Secondary Storage (Disk).

• Top (Fast, Small, Expensive per bit): Registers, L1/L2 Cache (SRAM).

• Bottom (Slow, Large, Cheap per bit): Disk (magnetic/optical).

Significance: Exploits locality to provide a system with average access time close to top level and capacity close to bottom level. Cost-performance trade-off.

★ Cache Memory

Role: A small, fast SRAM memory placed between CPU and main memory to reduce average memory access time.

• Hit: Data found in cache.

• Miss: Data not in cache; must fetch from main memory.

• Hit Ratio (h): Fraction of accesses that are hits.

• Average Access Time (AAT): AAT = h * t_c + (1-h) * (t_c + t_m) where t_c = cache access time, t_m = main memory access time.

• Improving Performance: Increase h (better mapping, larger cache) or reduce t_m impact (write-back, victim cache).

Cache Design & Mapping Techniques

Determines where a block from main memory can be placed in cache.

Cache Performance Improvement Methods

• Reduce Miss Rate:

  • Larger Block Size: Exploits spatial locality but may increase conflict & compulsory misses.

  • Higher Associativity: Reduces conflict misses (e.g., 8-way > 2-way).

  • Victim Cache: Small, fully associative cache holding recently evicted blocks (reduces conflict misses).

• Reduce Miss Penalty:

  • Write-Through vs. Write-Back: Write-back (write only to cache, write to memory on eviction) reduces memory writes, but needs dirty bit and write allocate policy. More complex.

  • Non-blocking Cache: Allows CPU to proceed on a hit while a miss is being serviced.

  • Multi-level Caches (L1, L2, L3): L1 fast/small, L2/L3 larger/slower. Miss from L1 goes to L2, etc.

Cache Replacement Policies (for set-associative/full associative when cache full)

• ★ LRU (Least Recently Used): Replace the block that hasn't been accessed for the longest time.

  • Pseudo-code for a 4-way set:

    
    On Cache Access (Hit):
    
        Mark the accessed line as "Most Recently Used" in its set.
    
        (Shift other lines' LRU counters down)
    
    On Cache Miss (Eviction Needed):
    
        Find the line in the set with the smallest LRU counter (oldest).
    
        Evict that line.
    
        Load new block into that line, mark it as "Most Recently Used".
    
    

  • Requires tracking access order (hardware counters or bits).

• FIFO: Replace the block that has been in the cache the longest.

• Random: Pick a random block to replace. Simple, surprisingly effective.

Cache Coherency

Problem: In multiprocessor systems, each CPU may have its own cache. If one CPU modifies a cached copy of a shared memory block, other CPUs' caches have stale copies. Solutions:

• Write-Invalidate: When a CPU writes to a shared block, it invalidates copies in all other caches (via bus snooping). Subsequent reads miss and fetch new data.

• Write-Update (Write-Broadcast): When a CPU writes, it broadcasts the new data to all other caches that have a copy. Keeps all copies up-to-date.

• Snooping: Caches monitor (snoop) the bus to detect accesses to shared addresses by other processors.

Virtual Memory

Concept: Gives each process the illusion of a large, contiguous private memory space (larger than physical RAM). Uses secondary storage (disk) as an extension.

• Addresses: Virtual (generated by CPU) vs. Physical (to memory).

• Memory Management Unit (MMU): Hardware that translates virtual to physical addresses using page tables (or segment tables).

  • Translation: Physical Address = (Page Table Base + Page Number * Entry Size) + Offset.

  • TLB (Translation Lookaside Buffer): A fast, small cache inside MMU for recent virtual-to-physical translations. TLB hit is crucial for performance.

Memory Segmentation

Divides virtual address space into logical segments (Code, Data, Stack, Heap) of variable size.

• Address: Segment Number : Offset.

• MMU uses a Segment Table (base, limit) to translate.

• Advantages: Better protection (read/write/execute per segment), natural grouping, easier sharing.

• Challenges: External fragmentation (variable size segments leave holes), complex allocation.

• Complements Virtual Memory: Segmentation provides logical organization, paging (if used with segmentation) provides physical allocation without fragmentation.

Page Replacement Algorithms (when a page fault occurs and physical memory is full)

• LRU (Least Recently Used): Replace page not used for longest time. Optimal but expensive hardware.

• FIFO (First-In-First-Out): Replace oldest loaded page. Simple, may replace frequently used page (Belady's anomaly).

• Optimal (Belady's): Replace page that will not be used for the longest time in future. Theoretical minimum faults, not implementable (requires future knowledge).

Main Memory & Semiconductor Memories

[!TIP] Exam Focus: "Write a short note on Read Only Memory." Cover types: Mask ROM, PROM, EPROM, EEPROM, Flash. Highlight Volatile vs. Non-Volatile: Volatile (SRAM, DRAM) loses data on power-off; Non-Volatile (ROM, Flash) retains data.

★ Secondary Storage Comparison

VI. ADVANCED PROCESSOR ARCHITECTURES

★ RISC vs. CISC Architectures

Pipelining

Concept: Overlap the execution of multiple instructions by dividing the CPU into stages. Each stage works on a different instruction simultaneously. Classic 5-Stage (MIPS/RISC) Pipeline:

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

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

3. EX (Execute): Perform ALU operation (add, subtract, address calculation).

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

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

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

Pipeline Hazards:

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

• Data: Dependency between instructions (e.g., ADD R1, R2, R3 followed by SUB R4, R1, R5). Solution: Forwarding/Bypassing (send EX result directly to next instruction's EX input), or stall (bubble).

• Control: Uncertainty of next PC due to branches/jumps. Solution: Branch delay slot (execute instruction after branch regardless), branch prediction (static/dynamic).

[!TIP] Exam Focus: "Layout of pipelined instruction execution." Draw the pipeline diagram for a sequence of instructions (e.g., ADD, SUB, AND, OR), showing stages and potential hazards (especially data hazards). Be ready to explain forwarding.

Instruction-Level Parallelism (ILP)

Techniques to execute more than one instruction per clock cycle.

• Superscalar: Multiple parallel functional units (e.g., 2 ALUs, 1 multiplier). Dynamic scheduling (out-of-order execution) with scoreboarding or Tomasulo's algorithm to handle dependencies and avoid stalls.

• Superpipeline: Increase pipeline depth (more stages, shorter clock period). Increases clock frequency but also hazard penalties.

VII. MULTIPROCESSING & PARALLEL SYSTEMS

Multiprocessor Systems

Multiple CPUs sharing memory and resources.

• UMA (Uniform Memory Access): All CPUs have equal access time to all memory (symmetric multiprocessing - SMP). Shared bus or crossbar.

• NUMA (Non-Uniform Memory Access): Memory physically distributed; access time depends on location of memory relative to CPU. Used in large systems.

★ Inter-processor Communication & Synchronization

• Shared Memory: Processors communicate by reading/writing common memory locations.

  • Synchronization Needed: To prevent race conditions on shared data.

  • Mechanisms:

    • Locks (Test-and-Set, Compare-and-Swap): Atomic instructions to acquire/release a lock variable.

    • Semaphores: Counting or binary, with wait() and signal() operations (must be atomic).

    • Barriers: All processors must reach a point before any proceed.

• Message Passing: Processors communicate by sending/receiving messages (no shared memory). Common in distributed systems, clusters. More explicit but scalable.

Inter-processor Arbitration

When multiple processors request a shared resource (e.g., system bus), an arbiter grants access.

• Daisy Chain (Serial): Bus grant line passed in priority order (fixed priority). Simple, but low-priority device may starve.

• Centralized Parallel: Dedicated arbiter (e.g., using priority encoder) polls or receives requests, grants to highest priority. Fast, but arbiter is bottleneck/single point of failure.

• Distributed: Each device has logic to decide (e.g., based on ID). No central point, scalable.

Array & Vector Processing

• Array Processor (SIMD - Single Instruction, Multiple Data):

  • One instruction operates on multiple data elements simultaneously (e.g., add two vectors).

  • Attached Array Processor: A separate unit (like a GPU) attached to a host CPU.

  • SIMD Processor: Integrated into CPU (e.g., Intel SSE/AVX, ARM NEON). Has wide vector registers (128-bit, 256-bit, 512-bit).

• Vector Processing:

  • Specialized for vectors (arrays). Has vector registers (hold many elements) and vector functional units.

  • Chaining: Overlap operations on different vector instructions (e.g., while one add is computing, next load starts).

  • Advantage over Scalar: High throughput for data-parallel tasks (scientific computing, graphics). Less instruction fetch/decode overhead.

Multicore Processors

• Concept: Multiple independent processor cores (full CPUs) integrated onto a single chip.

• Design Challenges:

  • Cache Coherency: Each core has private L1/L2 cache. Must maintain coherency (MESI protocol common).

  • Memory Bandwidth: Shared memory bus can become bottleneck. Solutions: shared L3 cache, multi-channel memory.

  • Programming: Requires parallel programming (threads, OpenMP, etc.) to utilize cores.

• Comparison:

  • vs. Single-Core: Higher throughput for parallel workloads, but not faster for single-threaded code (unless higher clock).

  • vs. Multiprocessor (Multi-socket): Multicore is chip-level (shared L3, fast interconnect). Multiprocessor is board-level (separate chips, NUMA more common). Multicore has lower latency, higher integration, lower power.

[!TIP] Exam Focus: "Describe the structure and working of inter-processor communication and synchronization." Focus on Shared Memory with Locks/Semaphores. Draw a simple diagram of two CPUs with a shared memory and a lock variable. Explain the critical section problem and how a lock (using atomic Test-and-Set) solves it. For "Compare RISC and CISC," use the table. For "Booth's Algorithm," be ready to trace a 4-bit example step-by-step.