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

I. FUNDAMENTALS OF COMPUTER ORGANIZATION & SYSTEM STRUCTURE

Computer System Overview & Basic Principles

A digital computer system consists of five functional units that work together:

1. Input Unit: Accepts data/instructions from outside world.

2. Memory Unit: Stores programs and data (primary & secondary).

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

4. Control Unit (CU): Directs the operation of all other units.

5. Output Unit: Communicates results to the outside world.

Block Diagram Structure:

[Input] --> [Memory] <--> [ALU] <--> [Control Unit] <--> [Output]

     (Data & Instructions flow through buses)

Instruction Execution Cycle (Fetch-Decode-Execute)

The fundamental cycle for program execution:

1. Fetch: CU gets the next instruction from memory (pointed by PC) and places it in IR.

2. Decode: CU interprets the opcode in IR to determine the operation and required operands.

3. Execute: CU sends control signals to ALU, memory, or I/O to perform the operation.

Key Registers & Their Roles:

Flow of a Fetch Cycle:

PC -> MAR (Address of next instruction sent to memory)

Memory[MAR] -> MDR (Instruction read from memory)

MDR -> IR (Instruction loaded into IR)

PC + 1 -> PC (PC incremented for next instruction)

Register Organization

• General-Purpose Registers (R0-Rn): Used for any data/address manipulation by programmer. Reduce memory accesses.

• Accumulator (AC): Implicit operand for many arithmetic/logic operations (single-register organization, older style).

• Index Registers: Used for indexed addressing (e.g., ADD R1, X(R2) where R2 holds base address, R1 holds index offset).

• Stack Organization: Uses a dedicated Stack Pointer (SP) register. Implements LIFO (Last-In-First-Out). Supports PUSH/POP operations. Efficient for procedure calls, interrupts.

Instruction Set Architecture (ISA)

• Instruction Formats (based on number of address fields):

  • 3-Address: ADD R1, R2, R3 (R1 <- R2 + R3). More complex instruction, fewer instructions per program.

  • 2-Address: ADD R1, R2 (R1 <- R1 + R2). Common.

  • 1-Address: ADD R1 (AC <- AC + R1). Uses implicit accumulator.

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

• Instruction Types:

  • Data Transfer: LOAD, STORE, PUSH, POP.

  • Arithmetic: ADD, SUB, MUL, DIV.

  • Logical: AND, OR, NOT, SHIFT.

  • Branch/Control: JUMP, JZ, JNZ, CALL, RET.

  • I/O: IN, OUT.

• Addressing Modes (How operand address is specified):

  | Mode | How Address is Formed | Example (Assume X=100) | Use Case | | :--- | :--- | :--- | :--- | | Immediate | Operand is part of instruction | ADD R1, #5 | Load constant. | | Direct | Address field gives operand's memory address | ADD R1, 100 | Fast, fixed address. | | Indirect | Address field points to a memory location that holds the operand's address | ADD R1, @100 | Dynamic addressing, pointers. | | Register | Operand is in a specified register | ADD R1, R2 | Fastest. | | Register Indirect| Register holds the operand's memory address | ADD R1, (R2) | Array/string traversal. | | Displacement | Address = Base Reg + Constant | ADD R1, 100(R2) | Array element access. | | Relative | Address = PC + Constant | JUMP +10 | Position-independent code. |

Register Transfer Language (RTL)

• Definition: A symbolic language (like a micro-code) used to describe the micro-operation sequences within a computer. It specifies the transfer of data between registers and the operations performed.

• Purpose: To specify the digital system's behavior at the register-transfer level during design and analysis.

• Representation:

  • Basic Format: Destination : Source

  • Example: R2 <- R1 + R3 (Add contents of R1 and R3, store in R2).

  • Micro-operation Control: R2 <- R1 + R3, READ (The READ signal is activated for this transfer).

  • Conditional Transfer: If (Z=1) then (PC <- PC + 1) (Z is Zero flag).

Example - Fetch Cycle in RTL:

1. MAR <- PC

2. MDR <- Memory[MAR]

3. IR <- MDR

4. PC <- PC + 1

II. CONTROL UNIT DESIGN

Control Unit Functions & Types

The CU generates timing and control signals (Read, Write, Select, Enable) to orchestrate data movement and operations.

Micro-programming Concepts

• Micro-instruction: A word in control memory that generates one or more control signals (micro-operations) for one cycle.

• Micro-operation: The smallest unit of control (e.g., PC -> MAR, ALU_ADD).

• Micro-program: A sequence of micro-instructions that implements one machine instruction.

• Micro-instruction Formats:

  • Horizontal: One bit per control signal. Wide, fast, many parallel operations. Low encoding.

  • Vertical: Encoded format (fields specify operations). Narrow, slow, fewer parallel ops. More like machine code.

• Micro-instruction Fields: Typically includes:

  1. Control Field: Bits for generating control signals.

  2. Next Address Field: Specifies address of next micro-instruction (for sequencing).

  3. Condition Field: For conditional branching (e.g., based on status flags).

• Micro-program Sequencer: Hardware that determines the next micro-instruction address. Handles:

  • Sequencing: CA + 1 -> CAR (Next sequential address).

  • Branching: CA <- Branch Address (Based on condition field).

  • Subroutine Call/Return: Save/restore address.

Control Word & Micro-operation Execution

• Control Word (CW): The binary representation of a micro-instruction. Each bit (or field) directly or indirectly controls a specific hardware component (e.g., PC_IN=1, ALU_ADD=1).

• How it Works: The CU's sequencing logic fetches a CW from CM. The CW's bits activate specific control lines (e.g., enable registers, select ALU operation, set read/write) to perform a set of micro-operations simultaneously in one clock cycle.

Example: Control Word for ADD R1, R2 (assuming R1 is destination):

Control Word Bits:

[PC_OUT=0, PC_IN=0, MAR_IN=0, MDR_OUT=0, ... ,

R1_OUT=1, R2_OUT=1, ALU_OP=ADD, R1_IN=1, ...]

This CW would:

1. Enable output of R1 and R2 to ALU inputs.

2. Set ALU to ADD operation.

3. Enable input to R1 to receive ALU output.

4. All other control signals are 0 (inactive).

III. DATA REPRESENTATION & ARITHMETIC

Number Systems & Negative Number Representation

• 1's Complement: Invert all bits of the positive number.

  • +5 (0101) -> -5 (1010) in 4-bit.

  • Drawback: Two representations for zero (0000, 1111). End-around carry needed in addition.

• 2's Complement: 1's Complement + 1.

  • +5 (0101) -> 1's: 1010 -> +1: 1011 = -5.

  • Advantage: Single zero (0000). Addition/Subtraction use same circuitry. No end-around carry.

  • Rule: For an n-bit number, range is $$\displaystyle -2^{n-1} $$ to $$\displaystyle 2^{n-1}-1 $$.

  • Subtraction as Addition: A - B = A + (2's complement of B). Discard carry-out from MSB.

Fixed-Point Arithmetic

• Addition/Subtraction: Straightforward binary addition. For subtraction, take 2's complement of subtrahend and add. Watch for overflow (when result sign is incorrect).

• Multiplication (Unsigned - Shift & Add):

  1. Initialize product = 0.

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

  3. Shift multiplicand left by 1 bit.

  4. Shift multiplier right by 1 bit.

  5. Repeat for n bits.

• Division (Restoring):

  1. Initialize remainder = dividend.

  2. For each bit from MSB to LSB:

     • Shift remainder left, bring down next divisor bit.

     • Subtract divisor from remainder.

     • If remainder >= 0, quotient bit = 1; else, add divisor back (restore) and quotient bit = 0.

  3. Final remainder and quotient.

Floating-Point Arithmetic (IEEE 754 Standard)

A number is represented as: $$\displaystyle \pm S \times B^E $$

Where:

• S (Significand/Mantissa): Fractional part (normalized: 1.xxxx for base 2).

• E (Exponent): Biased ( Excess-K, e.g., 127 for single-precision).

• B (Base): Usually 2.

Operations Steps:

1. Align Exponents: Adjust the number with smaller exponent by shifting its significand right until exponents match.

2. Add/Subtract Significands: Perform operation on aligned significands.

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

4. Round: Fit significand back to field size.

5. Check for Overflow/Underflow.

Comparison: Fixed-Point vs. Floating-Point

| Feature | Fixed-Point | Floating-Point |

| :--- | :--- | :--- |

| Range | Limited, small. | Very large (due to exponent). |

| Precision | Fixed, uniform. | Variable; higher for numbers near 1.0, lower for very large/small. |

| Complexity | Simpler hardware, faster. | Complex hardware (alignment, normalization, rounding). |

| Use Case | Financial calculations, control systems (exact decimal). | Scientific computing, graphics (wide dynamic range). |

| Example | 12.75 stored as 1275 with implied decimal. | 12.75 ≈ 1.59375 × 2^3 -> S=1.59375, E=3+127=130. |

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

• Purpose: Efficient multiplication of signed numbers by reducing the number of additions/subtractions. It examines pairs of bits in the multiplier.

• Key Idea: Replace strings of 1s with a subtraction at the start and an addition at the end of the string.

• Algorithm Steps (4-bit example, M: multiplicand, Q: multiplier, A: accumulator, Q-1: extra bit):

  1. Initialize A=0, Q=Multiplier, Q-1=0, Count=n.

  2. Examine (Q0, Q-1):

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

     • 01: A = A + M (Add multiplicand).

     • 10: A = A - M (Subtract multiplicand, i.e., add 2's complement of M).

  3. Arithmetic Right shift (preserves sign) (A, Q, Q-1) as one unit.

  4. Decrement count, repeat until count=0.

  5. Result is in (A, Q).

Example: (-5) × (+3) (5-bit: M=11011 (-5), Q=00011 (3))

Step | A | Q | Q-1 | Operation (Q0,Q-1)

0 | 00000 | 00011 | 0 | Init

1 | 11011 | 00011 | 1 | 01 -> A=A+M (Add M)

 | (A+M)   |         |     | Shift -> 11101 10011 1

2 | 11101 | 10011 | 1 | 11 -> No op, Shift

 |         |         |     | -> 11110 01001 1

3 | 11110 | 01001 | 1 | 01 -> A=A+M (Add M)

 | (A+M)   |         |     | Shift -> 11101 10100 0

4 | 11101 | 10100 | 0 | 00 -> No op, Shift

 |         |         |     | -> 11110 11010 0

Final (A,Q)=11110 11010. This is -15 in 2's complement (correct).

Arithmetic Logic Unit (ALU) Design

• Core Components:

  • Adder/Subtractor (e.g., using full adders with XOR for subtraction).

  • Logic Unit (AND, OR, NOT, XOR gates).

  • Multiplexers (MUX): To select between operations (Arith, Logic, input).

  • Shifter (for shift operations).

  • Control Logic: Generates signals for MUX selects and operation control based on opcode.

• Functional Block:

  
  [Input A] -----
  
                \
  
                 [MUX] --> [Logic/Arith Unit] --> [Output]
  
  [Input B] ----/  ^       ^
  
                   |       |
  
              [Control] [Shifter]
  
      (Selects operation: ADD, AND, etc.)
  
  

IV. BUS STRUCTURE & I/O ORGANIZATION

Bus Fundamentals

• Concept: A shared communication pathway (set of parallel wires) that interconnects multiple components (CPU, memory, I/O).

• Need: Reduces the number of physical connections (from O(n²) to O(n)). Enables modularity.

• How it Aids Communication: All units attach to the same bus. Only one unit can drive (send on) the bus at a time, controlled by bus arbitration. Others receive.

• Types:

  • Data Bus: Carries data. Bidirectional. Width (bits) determines transfer size.

  • Address Bus: Carries memory/I/O addresses. Unidirectional (from CPU/memory controller). Width determines address space.

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

I/O Interfaces & Data Transfer Methods

• Need for Interface: CPU and I/O devices have different electrical characteristics, data formats, and speeds. Interface (I/O controller) acts as a translator and buffer.

• Connection: I/O device <--> I/O Interface/Controller <--> System Bus.

• Comparative Note on I/O Interfaces:

  | Interface | Key Features | Typical Use | | :--- | :--- | :--- | | USB | Plug-and-play, hot-swappable, serial, supports up to 127 devices via hub. Low to medium speed. | Peripherals (mouse, keyboard, flash drive). | | PCI | Parallel, high-speed, bus mastering (devices can control bus), plug-and-play. | Internal cards (graphics, network). | | SCSI | Parallel, supports multiple devices (8-16) on a single bus, each with unique ID. High speed, expensive, complex configuration. | High-performance storage (servers, workstations). |

• Serial vs. Parallel Transfer:

  | | Serial | Parallel | | :--- | :--- | :--- | | Data Transmission| 1 bit at a time over 1 line. | Multiple bits simultaneously over multiple lines. | | Speed | Slower per wire, but higher clock speeds possible (less skew). | Faster per transfer, limited by clock skew and crosstalk over distance. | | Complexity/Cost| Simpler, cheaper wiring, longer distances. | Complex, expensive wiring, shorter distances. | | Example | USB, SATA, PCI Express. | Traditional PCI, SCSI (parallel). |

• Synchronous vs. Asynchronous Transfer:

  | | Synchronous | Asynchronous | | :--- | :--- | :--- | | Timing | Events occur at fixed intervals defined by a common clock. | No common clock. Handshaking signals coordinate transfer. | | Speed | Faster (no handshake overhead). | Slower due to handshake delays. | | Use Case | All components with matched speeds (e.g., CPU-cache). | Devices with varying speeds (CPU-I/O). | | Mechanism | Read/Write pulses timed to clock edges. | Strobe Control or Handshaking. |

• Strobe Control & Handshaking (Asynchronous):

  • Strobe: Source unit sends a single control pulse (strobe) to indicate data is valid. Receiver must latch data immediately upon detecting strobe. No confirmation.

  • Handshaking: Two-way coordination.

    1. Source places data on bus, asserts Data Valid.

    2. Destination accepts data, asserts Data Accepted.

    3. Source removes data and Data Valid upon seeing Data Accepted.

    Ensures reliable transfer despite speed differences.

Specific I/O Buses & Standards

• PCI Bus (Peripheral Component Interconnect):

  • Working: Parallel, shared bus. Uses bus mastering – devices can become bus masters to transfer data directly to/from other devices/ memory without CPU intervention (reduces CPU load).

  • Improves Performance: High bandwidth (133 MB/s for 32-bit/33MHz), bus mastering, plug-and-play (auto-configuration of IRQs, I/O addresses).

• USB (Universal Serial Bus):

  • Features: Host-centric (host controls bus), supports up to 127 devices in a tiered star topology via hubs. Hot-plugging, power delivery. Speeds: USB 2.0 (480 Mbps), USB 3.x (5-20 Gbps).

  • Architecture: Host <--> Root Hub <--> External Hubs <--> Devices. Uses transaction packets (token, data, handshake).

• SCSI Bus (Small Computer System Interface):

  • Features: Parallel bus, intelligent devices with unique IDs (0-7 or 0-15). Supports daisy-chaining. High performance, but expensive and requires termination at both ends.

  • Architecture: Single SCSI bus, one initiator (usually host adapter) and multiple targets (disks, scanners). Uses arbitration if multiple initiators.

Comparison: USB vs. SCSI

| | USB | SCSI |

| :--- | :--- | :--- |

| Speed | Lower to medium (USB 3.x high). | Historically higher (Ultra-320, 320 MB/s). |

| Cost | Very low (integrated in chipsets). | High (dedicated controller cards, devices). |

| Application | General-purpose PCs, consumer electronics. | Servers, high-end workstations, professional storage. |

| Configuration | Simple (plug-and-play, auto). | Complex (manual ID setting, termination). |

| Topology | Tiered star (via hubs). | Daisy-chain (parallel). |

Advanced I/O Concepts

• Direct Memory Access (DMA):

  • Concept: Allows an I/O controller to read/write main memory directly without CPU intervention, after initial setup. CPU is freed for other tasks.

  • Need: For high-speed I/O (disk, network) where CPU handling each byte/word would be a bottleneck.

  • Operation:

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

    2. CPU initiates transfer.

    3. DMA controller takes control of the bus (via bus arbitration).

    4. DMA controller performs block transfer (read from I/O -> memory or memory -> I/O).

    5. DMA controller interrupts CPU upon completion.

• DMA Controller Block Diagram:

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

  DMA Controller Registers: Source Address Reg, Destination Address Reg, Transfer Count Reg, Control/Status Reg.

• I/O Processor (IOP):

  • A specialized processor (like a mini-CPU) dedicated to managing I/O operations for a set of devices.

  • Role: Executes its own I/O instructions from its own memory. Handles device-specific protocols, data formatting, error checking. Communicates with main CPU via shared memory or messages.

  • Difference from DMA: DMA does simple block transfers. IOP can execute complex I/O programs, handle multiple devices, and perform data processing (e.g., disk controller with cache).

V. MEMORY ORGANIZATION & HIERARCHY

Memory Hierarchy Concept

• Principle: Organize memory into a pyramid based on speed, cost, and capacity.

  
  Registers (fastest, smallest, costliest)
  
      |
  
  Cache (SRAM)
  
      |
  
  Main Memory (DRAM)
  
      |
  
  Secondary Storage (HDD, SSD) (slowest, largest, cheapest)
  
  

• Significance: Exploits Principle of Locality to achieve near-fast speed at near-slow cost.

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

  • Spatial Locality: Items near a recently accessed item likely to be accessed soon.

• Goal: Minimize Average Memory Access Time (AMAT).

  AMAT = Hit Time + Miss Rate * Miss Penalty

Semiconductor Memories

• RAM (Random Access Memory) - Volatile:

  • SRAM (Static RAM): Uses 6 transistors per bit (flip-flop). Fast, expensive, power-hungry. Used for Cache.

  • DRAM (Dynamic RAM): Uses 1 transistor + 1 capacitor per bit. Slower, cheaper, dense. Needs periodic refreshing. Used for Main Memory.

• ROM (Read Only Memory) - Non-Volatile:

  | Type | Programming | Erasable? | Use | | :--- | :--- | :--- | :--- | | ROM | Mask-programmed (factory). | No | Firmware (BIOS). | | PROM | User-programmable once (fuse). | No | One-time configuration. | | EPROM| UV light through quartz window. | Yes (slow). | Development, rare now. | | EEPROM| Electrical. | Yes (byte-wise). | Configuration storage, small data. | | Flash| Electrical (block-wise). | Yes (block-wise). | USB drives, SSDs, BIOS/UEFI. |

Volatile vs. Non-Volatile:

• Volatile (SRAM, DRAM): Lose data on power-off. Fast. Main/working storage.

• Non-Volatile (ROM, Flash, HDD): Retain data. Slower (except some Flash). Permanent storage.

Secondary Storage Comparison

Cache Memory

• How it Improves Performance: Exploits locality. Stores frequently used blocks of main memory in a small, fast SRAM. Reduces average access time from slow DRAM to fast SRAM for hits.

• Cache Design Parameters:

  1. Block Size: Number of bytes transferred per cache line. Larger -> better spatial locality, but higher miss penalty & fewer blocks.

  2. Mapping Function: Determines where a memory block can be placed in cache.

  3. Replacement Algorithm: Which block to evict on a miss (if cache full).

  4. Write Policy: Write-through (update both cache & memory) vs. Write-back (update cache only, mark dirty, write on eviction).

• Cache Mapping Techniques:

  | Technique | How it Works | Advantages | Disadvantages | | :--- | :--- | :--- | :--- | | Direct Mapped| Each memory block maps to exactly one cache line (index = BlockNum % #Lines). | Simple, fast hardware. | High conflict misses (two hot blocks mapping to same line). | | Set-Associative| Cache divided into sets (e.g., 4-way). Block maps to a set, can go into any line within set. | Balance between conflict misses & cost/speed. | More complex, slower than direct. | | Fully Associative| Block can be placed in any cache line. | Minimum conflict misses. | Very expensive (need to search all lines in parallel). Used for small TLBs. |

• Cache Performance & Misses:

  • Cache Hit: Data found in cache.

  • Cache Miss: Data not in cache.

  • Miss Types:

    • Compulsory (Cold): First access to a block.

    • Capacity: Cache is full, working set > cache size.

    • Conflict: Due to mapping policy (even if cache not full).

• Replacement Algorithms:

  • LRU (Least Recently Used): Replace block not used for longest time. Optimal for temporal locality. Requires tracking usage order.

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

  • Random: Replace random block. Simple, often good enough.

  • Pseudocode for LRU Simulation:

    
    On Cache Access (for block X):
    
        if X is in cache:
    
            Update LRU age of X (make it most recent)
    
        else: // Cache Miss
    
            if Cache is full:
    
                Find block Y with MAX(LRU_age)
    
                Evict Y
    
            Insert X into cache, set LRU_age = 0 (most recent)
    
        Increment LRU_age of all other blocks in cache
    
    

• Methods to Improve Cache Performance:

  1. Reduce Miss Penalty: Smaller block size, multi-level caches (L1, L2, L3).

  2. Reduce Miss Rate: Larger cache size, higher associativity, victim cache (small buffer for evicted blocks).

  3. Reduce Hit Time: Smaller/ simpler cache (direct-mapped), pipelined access.

Virtual Memory

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

• Need: Allows running programs larger than physical RAM, provides memory protection and isolation.

• Role of MMU (Memory Management Unit):

  • Hardware that translates Virtual Addresses (VA) generated by CPU to Physical Addresses (PA).

  • Uses page tables (or segment tables) stored in memory.

  • Employs a TLB (Translation Lookaside Buffer) – a fast, small associative cache for recent VA->PA translations.

• Memory Segmentation:

  • Divides memory into logical segments (Code, Data, Stack, Heap) of variable size.

  • Address: Segment Number : Offset.

  • How it complements VM: Segmentation provides logical grouping and protection. Paging (often used with segmentation) provides fixed-size allocation to avoid external fragmentation.

  • Advantages: Natural program view, protection (segment limits), sharing (shared code segment).

  • Challenges: External fragmentation (variable-sized segments), complex allocation.

• Page Replacement Algorithms (when a page fault occurs and no free frame):

  • LRU, FIFO, Clock (Second Chance). Goal: Minimize future page faults.

  • Pseudocode for LRU Page Replacement (similar to cache LRU, but on page frames).

• Memory Management Hardware:

  • Page Table Base Register (PTBR): Points to base of page table.

  • Page Number (PN): Extracted from VA.

  • PA = (Page Table[PN].Frame Number) * PageSize + Offset

  • TLB: Speeds up translation. On TLB miss, hardware walks page table (or OS handles).

VI. ADVANCED ARCHITECTURES & PARALLEL PROCESSING

RISC vs. CISC

Pipelining

• Concept: Divide instruction execution into stages (e.g., IF, ID, EX, MEM, WB). Multiple instructions are in different stages simultaneously. Increases throughput (instructions per cycle), not necessarily latency of single instruction.

• Pipeline Stages (Classic 5-stage):

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

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

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

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

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

• Pipeline Hazards:

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

  • Data: Dependency between instructions (RAW - Read After Write). Solution: Forwarding/bypassing, stall (bubble).

  • Control: Branch/jump decision not known until late stage. Solution: Stalling, branch prediction, delayed branch.

• Layout: Instructions flow like an assembly line. Ideal CPI = 1.

Multiprocessor Systems

• Characteristics: Multiple CPUs sharing memory and/or I/O.

• Types:

  • Tightly-Coupled (SMP): Processors share global memory and clock, connected via shared bus or crossbar. Close communication.

  • Loosely-Coupled (Cluster): Each processor has local memory, connected via high-speed network (message passing). More scalable.

• Inter-processor Communication & Synchronization:

  • Shared Memory: Processors read/write common memory locations. Fast but needs synchronization.

  • Message Passing: Explicit send/receive messages over network. Slower but explicit.

  • Synchronization Issues:

    • Race Condition: Multiple processors accessing shared data concurrently, outcome depends on timing.

    • Solution: Use atomic operations (test-and-set, compare-and-swap) to implement locks and semaphores.

• Inter-processor Arbitration: When multiple processors request a shared resource (bus, memory), an arbiter grants access based on a policy (fixed priority, round-robin, LRU).

• Interconnection Networks:

  | Network | Structure | Pros | Cons | | :--- | :--- | :--- | :--- | | Bus | Single shared line. | Simple, cheap. | Bottleneck, limited scalability. | | Ring | Processors in a loop. | Simple, scalable. | High diameter (latency). | | Mesh | 2D/3D grid. | Good scalability, locality. | Complex routing. | | Crossbar| Dedicated path between any pair. | No contention, fast. | Expensive (O(n²) switches). |

Array & Vector Processing

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

  • Definition: A single instruction operates on multiple data elements simultaneously using multiple processing elements (PEs).

  • Significance: Exploits data parallelism. Core of GPUs and modern vector extensions (SSE, AVX).

  • Example: ADD V1, V2, V3 adds 8 pairs of numbers in one cycle if vector length=8.

• Vector Processing:

  • Definition: A processor with vector registers and vector instructions that operate on entire vectors (arrays). Pipelined functional units.

  • Difference from Scalar: Scalar processes one data element per instruction. Vector processes a vector (multiple elements) per instruction.

  • Vector Machines: Have deep pipelines for vector operations (load, add, store). High bandwidth memory.

• Comparison: Vector vs. Array:

  • Vector Processing: Often refers to specialized CPUs with vector registers/instructions (e.g., Cray).

  • Array Processing: Often refers to massively parallel systems with many simple PEs (e.g., SIMD array, GPU cores). Modern usage often overlaps (GPUs do both).

Multicore Processors

• Concept: Integrate multiple independent processor cores (CPUs) on a single chip.

• Significance: Improves performance without increasing clock frequency (power/heat limits). Enables thread-level parallelism.

• Challenges:

  • Memory Consistency: Ensuring all cores see a consistent view of shared memory (snooping, directory-based protocols).

  • Communication: Inter-core communication latency (via shared L2/L3 cache or interconnect).

  • Parallelism: Writing efficient multi-threaded software (Amdahl's Law). Load balancing, synchronization overhead.