UNIT 2: Computer Organization & Architecture - Short Notes

1. CPU Organization and Instruction Execution

Registers in CPU

• Program Counter (PC): Holds address of next instruction to fetch.

• Instruction Register (IR): Holds current instruction after fetch.

• Memory Register (MR) / Memory Address Register (MAR): Holds address for memory read/write.

• Memory Data Register (MDR): Holds data read from or to be written to memory.

• General Purpose Registers (R0–Rn): Used for data manipulation.

• Accumulator (ACC): Implicit operand for arithmetic/logical operations.

• Index Registers: Used for indexed addressing (e.g., ADD R1, X(R2)).

• Stack Organization: LIFO structure; Stack Pointer (SP) tracks top.

Fetch-Execute Cycle

1. Fetch: PC → MAR; Memory read; MDR → IR; PC ← PC + 1.

2. Decode: Control unit decodes opcode in IR.

3. Execute: Operand fetch, ALU operation, result store.

4. Interrupt Check: If interrupt pending, handle.

Instruction Formats

Key: Opcode size determines instruction set size; address fields determine memory/register usage.

Addressing Modes

Instruction Types

• Data Transfer: MOV, PUSH, POP

• Arithmetic: ADD, SUB, MUL, DIV

• Logical: AND, OR, NOT, XOR

• Control/Program Control: JMP, JZ, CALL, RET

• I/O: IN, OUT

Stack-based CPU Organization

• Uses stack for operands and return addresses.

• Instructions implicit on top-of-stack (e.g., ADD pops two values, pushes result).

• Advantage: Compact instruction format (zero-address).

• Disadvantage: Increased memory accesses; slower than register-based.

2. Control Unit Design

Hardwired vs Micro-programmed Control

Control Word

• Binary word that generates control signals for micro-operations.

• Each bit corresponds to a control line (e.g., PCin, IRload, ALUadd).

• Example: For MAR ← PC:

  • Control word bits: PCout=1, MARin=1, other=0.

Micro-instruction Formats

• Horizontal:

  • Many control bits (one per signal).

  • Advantage: Parallel operations, fast.

  • Disadvantage: Large microinstruction size.

• Vertical:

  • Encoded fields (log₂N bits for N signals).

  • Advantage: Compact, less memory.

  • Disadvantage: Serial operations, slower.

• Encoding Techniques:

  • Field Direct Encoding: Groups mutually exclusive signals.

  • Field Indirect Encoding: Uses micro-instruction fields to select from a sub-rom.

Micro-program Sequencer

• Generates address of next microinstruction.

• Types:

  • Incrementer: CAR ← CAR + 1

  • Branch/Jump: Conditional/unconditional based on status bits.

  • Subroutine: Push/pop for CALL/RET in microcode.

  • Map: Decodes opcode to branch address.

Control Memory

• Stores microprogram (sequence of microinstructions).

• Organization:

  • Vertical microinstructions: More compact, slower.

  • Horizontal microinstructions: Wider, faster.

• Size: #Microinstructions × Microinstruction width (bits).

Register Transfer Language (RTL)

• Notation to describe micro-operations.

• Syntax: Destination ← Source

• Examples:

  • MAR ← PC

  • MDR ← Memory[MAR]

  • IR ← MDR

  • R1 ← R1 + R2

Execution of Micro-instructions

1. Fetch microinstruction from control memory (using CAR).

2. Decode fields to generate control signals.

3. Apply control signals to data path (registers, ALU, buses).

4. Update status bits (zero, carry, etc.).

5. Determine next microinstruction address (sequencer).

3. Data Representation and Arithmetic Logic

Number Representation

• Unsigned Binary: Direct binary.

• Signed Numbers:

  • 1's Complement: Invert all bits. Range: -(2ⁿ⁻¹ - 1) to +(2ⁿ⁻¹ - 1); two zeros.

  • 2's Complement: Invert bits + 1. Range: -2ⁿ⁻¹ to +(2ⁿ⁻¹ - 1); single zero.

    • Subtraction: A - B = A + (2's complement of B).

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

Arithmetic Operations

• Addition/Subtraction: Binary ripple-carry adder; subtraction via 2's complement.

• Multiplication: Shift-add algorithm (unsigned); Booth for signed.

• Division: Restoring/non-restoring algorithms (flowchart-based).

Booth's Algorithm (Signed Multiplication)

• Key Idea: Recode multiplier to reduce additions for consecutive 1s.

• Rules:

  • Q0 Q-1 | Operation

  • 0 0 | No op (just shift)

  • 0 1 | Add multiplicand to accumulator

  • 1 0 | Subtract multiplicand

  • 1 1 | No op

• 4-bit Example: Multiply -3 (1101) by +2 (0010) (2's complement).

  
  Initial: ACC=0000, Q=0010, Q-1=0, M=1101 (-3)
  
  Step1: Q0Q-1=00 → shift right → ACC=0000, Q=0001, Q-1=0
  
  Step2: Q0Q-1=10 → ACC = ACC - M = 0000 + 0011 = 0011; shift → ACC=0001, Q=1000, Q-1=1
  
  Step3: Q0Q-1=01 → ACC = ACC + M = 0001 + 1101 = 1110; shift → ACC=1111, Q=0100, Q-1=0
  
  Step4: Q0Q-1=00 → shift → ACC=1111, Q=0010, Q-1=0
  
  Result: ACC&Q = 11110010 = -6 (correct: -3 × 2 = -6)
  
  

Fixed Point vs Floating Point Arithmetic

Arithmetic Unit Design

• Components:

  • ALU: Performs operations (add, logic).

  • Shifter: For multiplication/division (shift left/right).

  • Registers: Accumulator, temporary registers.

  • Multiplexers: Select inputs.

• 4-bit Adder/Subtractor Circuit:

  • Use 4-bit adder with XOR gates on B input controlled by SUB signal.

  • SUB=0: A + B; SUB=1: A + B' + 1 (2's complement subtraction).

Serial Addition and Subtraction

• Bit-Serial Arithmetic: Data transmitted one bit at a time.

• Circuit: Shift registers for A, B; full adder; result shift register.

• Process:

  • For addition: LSB first, propagate carry.

  • For subtraction: Use 2's complement of B.

• Advantage: Minimal hardware (1-bit ALU).

• Disadvantage: Very slow (n cycles for n bits).

4. Bus Systems and I/O Interfaces

Bus Structure

• Concept: Shared communication pathway for multiple devices.

• Types:

  • Data Bus: Bidirectional, carries data (width = word size).

  • Address Bus: Unidirectional, carries memory/I/O addresses.

  • Control Bus: Carries read/write, interrupt, clock signals.

• CPU-Memory Communication:

  • CPU places address on address bus, asserts read/write on control bus, data transferred on data bus.

I/O Interfaces

• Need: Match device speed/voltage/data format with CPU/memory.

• Connection:

  • I/O Ports: Memory-mapped (same address space) or isolated (special instructions).

  • Interface Circuit: Buffers, handshaking logic, voltage converters.

Data Transfer Methods

Standard I/O Buses

• PCI Bus:

  • Working: Processor-independent bus; plug-and-play; bus mastering for DMA.

  • Features: 32/64-bit, 33/66 MHz, burst mode.

  • Performance Improvement: Dedicated pathways, bus mastering reduces CPU load.

• SCSI vs USB:

  | Feature | SCSI | USB | |---------------|-----------------------------------|------------------------------------| | Speed | High (up to 320 MB/s Ultra320) | Lower (USB 2.0: 480 Mb/s; 3.0: 5 Gb/s) | | Cost | High (complex controller) | Low (simple host controller) | | Application | Servers, high-performance devices | Peripherals (mouse, keyboard, storage) | | Topology | Daisy-chain (up to 7/15 devices) | Hub-based (up to 127 devices) |

• USB:

  • Types: USB 1.x (12 Mbps), USB 2.0 (480 Mbps), USB 3.x (5-20 Gbps).

  • Features: Hot-plug, power delivery, multiple speeds.

Direct Memory Access (DMA)

• Concept: I/O device transfers data directly to/from memory without CPU intervention.

• DMA Controller Block Diagram:

  
  CPU ↔ DMA Controller ↔ Memory
  
         ↑
  
      I/O Device
  
  

  • Components:

    • Address Register: Holds memory address.

    • Word Count Register: Tracks number of words.

    • Control/Status Registers: Start, interrupt, done flags.

    • Data Buffer: Temporary storage.

• Operation:

  1. CPU programs DMA controller (address, count, direction).

  2. DMA requests bus control (HOLD/HOLDA signals).

  3. DMA transfers data in burst/cycle-stealing mode.

  4. DMA releases bus, interrupts CPU on completion.

I/O Processor

• Need: Offload I/O tasks from CPU; handle complex I/O protocols.

• Working: Dedicated processor with its own instruction set; executes I/O programs; communicates with CPU via shared memory or messages.

Interrupts

• Vectored: Interrupt vector provides address of ISR (faster).

• Non-vectored: ISR address fixed; ISR polls devices (slower).

5. Memory Hierarchy and Management

Memory Hierarchy

Registers → L1 Cache → L2 Cache → Main Memory → Secondary Storage

• Principle of Locality:

  • Temporal: Recently accessed items likely reused.

  • Spatial: Adjacent locations likely accessed.

• Significance: Balances speed, capacity, cost; exploits locality to reduce average access time.

Main Memory: Semiconductor Memories

Secondary Storage Comparison

Cache Memory

• Role: Reduce CPU-memory speed gap; store frequently used data.

• Design Principles: Exploit locality; small, fast SRAM between CPU and memory.

• Cache Performance Metrics:

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

  • Average Access Time (AAT) = H × t_cache + (1-H) × t_memory

  • Miss Penalty: Time to replace a line and deliver data.

Cache Mapping Techniques

Replacement Policies

• LRU (Least Recently Used): Replace least recently accessed line.

• FIFO (First-In-First-Out): Replace oldest line.

• Random: Random replacement (simple, decent).

Write Policies

• Write-through: Write to cache and memory simultaneously.

• Write-back: Write only to cache; mark dirty; write to memory on replacement.

Improving Cache Performance

1. Increase cache size.

2. Increase associativity.

3. Use victim cache (small fully-associative cache for evicted lines).

4. Prefetching (sequential, stride).

5. Optimize block size (trade-off: spatial locality vs. miss penalty).

Cache Coherency (Multiprocessor)

• Problem: Multiple caches may have copies of same memory block.

• Protocols:

  • Write-invalidate: Writing processor invalidates others' copies.

  • Write-update (write-broadcast): Writing processor updates all caches.

Virtual Memory

• Concept: Use secondary storage to extend main memory; each process has its own virtual address space.

• Need: Allow larger programs than physical memory; memory protection; simplify programming.

• Implementation:

  • Paging: Fixed-size pages; page table maps virtual → physical frames.

  • Segmentation: Variable-size segments (code, data, stack); segment table maps → base/limit.

• Hybrid: Paged segmentation (segments divided into pages).

Memory Management Unit (MMU)

• Role: Hardware that translates virtual addresses to physical addresses.

• Components:

  • Page Table: Stored in memory; accessed by MMU.

  • TLB (Translation Lookaside Buffer): Fast associative cache for page table entries.

• Address Translation:

  
  Virtual Address → [Page Number | Offset]
  
  Page Number → TLB lookup → Page Frame Number
  
  Physical Address = (Page Frame Number × Page Size) + Offset
  
  

Page Replacement Algorithms

• LRU: Maintain access time order; replace oldest.

• FIFO: Queue; replace first-in.

• Optimal (Belady): Replace page not used for longest time (theoretical).

• Clock (Second Chance): Approximate LRU with reference bit.

Pseudo-code for LRU Simulation

Initialize: LRU_stack = empty list (most recent at front)

On page access:

  if page in LRU_stack: 

    move page to front of LRU_stack

  else:

    if cache full:

      evict page at end of LRU_stack (least recent)

    add page to front of LRU_stack

Memory Segmentation

• Concept: Divide memory into logical segments (code, data, stack).

• Advantages:

  • Protection (per-segment read/write/execute).

  • Sharing (multiple processes share code segment).

  • Easier programming (logical view).

• Challenges:

  • External fragmentation (variable sizes).

  • Complex allocation.

• Complement to Virtual Memory: Segmentation provides logical division; paging provides physical allocation. Often combined (segmented paging).

6. Advanced Processor Architectures

RISC vs CISC

Pipelining

• Concept: Overlap execution of multiple instructions.

• Stages (Classic 5-stage):

  1. IF (Instruction Fetch): MAR ← PC; IR ← Memory[MAR]; PC ← PC+4

  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 register.

• Throughput: Ideally 1 instruction/cycle (CPI → 1).

• Hazards:

  • Structural: Resource conflict (e.g., two instructions need memory).

  • Data: Dependency (RAW, WAR, WAW); solved by forwarding/stalling.

  • Control: Branch delay; solved by branch prediction, delayed slots.

Instruction Pipelining Layout

Cycle:   1    2    3    4    5    6    7    8

Instr1: IF   ID   EX   MEM  WB

Instr2:      IF   ID   EX   MEM  WB

Instr3:           IF   ID   EX   MEM  WB

Note: Hazards cause bubbles (stalls).

Vector Processing vs Array Processing

Array Processors

• Structure: Multiple processing elements (PEs) under single control.

• Usage: SIMD (Single Instruction, Multiple Data); e.g., GPU cores, vector extensions.

Multicore Processors

• Structure: Multiple independent cores on single chip.

• Advantages:

  • Parallelism (true multitasking).

  • Power efficiency (lower frequency per core).

  • Resource sharing (L2/L3 cache, memory controller).

• Challenges: Cache coherency, synchronization, software parallelism.

7. Multiprocessing and Parallelism

Multiprocessor Systems

• Tightly-Coupled: Shared memory, close communication (UMA).

• Loosely-Coupled: Distributed memory, each has its own memory (NUMA).

Inter-Processor Communication

• Shared Memory:

  • Processes read/write common memory locations.

  • Requires synchronization (semaphores, locks).

• Message Passing:

  • Processes exchange messages (send/receive).

  • Used in distributed systems; no shared memory.

Inter-Processor Synchronization

• Need: Coordinate access to shared resources; prevent race conditions.

• Tools:

  • Semaphores: Integer variable with atomic wait/signal.

  • Locks (Mutexes): Binary semaphore for exclusive access.

  • Barriers: All processors wait until all arrive.

  • Monitors: High-level synchronization construct.

Inter-Processor Arbitration

• For Shared Resources (bus, memory):

  • Daisy Chain: Serial priority; fixed priority order.

  • Centralized Arbiter: Single arbiter (fixed/rotating priority).

  • Distributed Arbitration: Each device decides based on bus signals (e.g., IEEE 488).

Interconnection Networks in Multiprocessors

[!TIP] Exam Tips

• Fetch-Execute Cycle: Always trace PC, MAR, MDR, IR in order.

• Booth's Algorithm: Practice 4-bit examples for both positive and negative multipliers.

• Cache Mapping: Know formulas for number of sets (direct/associative).

• DMA: Be ready to draw block diagram and explain cycle stealing vs burst.

• RISC vs CISC: Use ARM vs x86 as concrete examples.

• Pipelining Hazards: Know forwarding for data hazards; branch prediction for control.

• Addressing Modes: Distinguish indirect vs register indirect.

• Virtual Memory: Page table vs segment table differences.

• USB vs SCSI: Focus on cost, topology, and typical applications.

• LRU Pseudo-code: Implement with list/stack; O(1) with doubly-linked list + hash (advanced).