UNIT 2: Computer Organization & Architecture

Based on analysis of C COMPUTER ORGANIZATION AND ARCHITECTURE exam papers (Dec 2024 & Nov 2023).

I. Fundamental Computer Organization

Basic Structure of a Computer System

A digital computer system consists of three primary functional units that are interconnected:

1. CPU (Central Processing Unit): The "brain" that executes instructions and controls operations.

2. Memory Unit: Stores data and instructions (primary storage: RAM, cache; secondary: disk).

3. I/O Subsystem: Handles communication with the external world (keyboard, monitor, disk drives).

Data Flow & Interconnection: These units communicate via a system bus, a set of parallel electronic lines that carry addresses, data, and control signals.

[!TIP] Exam Focus: Be prepared to draw and label the basic functional units diagram, showing the flow of data/control between CPU, Memory, and I/O via the bus.

System Bus Structure

A bus is a shared communication pathway. A typical system bus is divided into three types:

Key Characteristics:

• Bus Width: Number of physical lines. Wider buses transfer more data per cycle.

• Bus Bandwidth: Maximum data transfer rate (bytes/sec).

• Bus Master: The unit that initiates a transfer (usually CPU, but DMA controller can be master).

II. Central Processing Unit (CPU) Architecture

Register Organization

Registers are fast, small storage locations inside the CPU.

General-Purpose Registers (GPRs): Used for holding operands and intermediate results during program execution (e.g., R0, R1, ..., Rn in RISC). Their number and size (16/32/64-bit) define the CPU's register-memory architecture.

Special-Purpose Registers:

• Memory Address Register (MAR): Holds the address of the memory location to be accessed.

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

• Instruction Register (IR): Holds the current instruction being decoded/executed.

• Program Counter (PC) / Instruction Pointer (IP): Holds the address of the next instruction to be fetched.

[!TIP] Common Pitfall: Remember the direction of data flow for MAR (output to memory) and MDR (bidirectional).

Stack Operations in CPU

A stack is a LIFO (Last-In, First-Out) data structure used for subroutine calls, interrupts, and temporary storage.

• Hardware Stack: Implemented using a dedicated register (Stack Pointer - SP) and a memory region. PUSH decrements SP and stores data; POP reads data and increments SP.

• Software Stack: Simulated using general-purpose registers and memory via explicit instructions.

Example (Hardware Stack, descending):

Initial: SP = 1000, Memory[1000] = X

PUSH R1:  SP = 999, Memory[999] = R1

PUSH R2:  SP = 998, Memory[998] = R2

POP R3:   R3 = Memory[998], SP = 999  (R3 gets R2)

Instruction Set Architecture (ISA)

ISA defines the programmer-visible interface of a processor: instruction formats, registers, data types, and addressing modes.

Instruction Format Fields:

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

• Operand Address Fields: Specify source/destination locations.

• Mode Field: Specifies the addressing mode.

• Formats vary: Zero-address (stack), One-address (accumulator), Two-address, Three-address.

Addressing Modes: Specify how to find an operand.

[!TIP] Exam Key: Be able to identify the addressing mode from an instruction and calculate the Effective Address (EA) for each mode.

Control Unit Design

The Control Unit (CU) generates the control signals that orchestrate the CPU and bus activities.

1. Hardwired Control Unit

• Principle: Control logic is implemented with fixed, hardwired digital circuits (gates, flip-flops). The instruction opcode directly drives a combinational logic network that outputs the control word (set of control signals).

• Diagram: A typical block diagram shows the instruction register's opcode bits feeding into a decoder and logic gates, whose outputs are the control signals (e.g., ALU_OP, READ, WRITE, REG_EN).

• Advantages: Very fast (minimal propagation delay).

• Disadvantages: Inflexible. Adding new instructions requires rewiring. Complex to design/debug for large ISAs.

2. Microprogrammed Control Unit

• Principle: Control is stored in a control memory (CM). Each machine instruction is associated with a microprogram (a sequence of microinstructions). A microprogram sequencer fetches and executes these microinstructions.

• Microinstruction (Control Word): A wide word where each bit (or group) is a control signal (1=active). Also contains the address of the next microinstruction.

• Microprogram Sequencer: Logic that determines the next microaddress (sequential, branch based on condition codes, jump to new routine for interrupt).

• Advantages: Flexible, easy to modify/debug. Simplifies design of complex ISAs.

• Disadvantages: Slower than hardwired (extra memory access per microinstruction).

[!TIP] Diagram Requirement: You must know how to sketch a simple block diagram for both types, highlighting the key components (decoder/logic gates for hardwired; control memory, microinstruction register, sequencer for microprogrammed).

Instruction Execution Cycle (Fetch-Decode-Execute Cycle)

The fundamental cycle for executing a single instruction.

1. Fetch: PC -> MAR -> Memory -> MDR -> IR. PC is incremented.

2. Decode: Instruction Register (IR) is decoded. Operand addresses are calculated (if needed).

3. Execute: The operation specified by the opcode is performed (ALU operation, memory access, I/O, branch).

4. Store: Results are written back to the destination (register or memory).

Flowchart: A standard flowchart connects these four phases, with branches for jumps/calls/interrupts.

Pipelining

Concept: Overlap the execution of multiple instructions by dividing the CPU into N independent stages (e.g., Fetch, Decode, Execute, Writeback). Each stage works on a different instruction simultaneously.

Space-Time Diagram (4-Stage Pipeline):

Cycle: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
------------------------------------

I1:    | F | D | E | W |   |   |   |

I2:    |   | F | D | E | W |   |   |

I3:    |   |   | F | D | E | W |   |

I4:    |   |   |   | F | D | E | W |

• Throughput: Ideally, one instruction completes per cycle after pipeline fill (cycle 4 onwards).

• Speedup (Ideal): $S \approx N$ (for N stages).

Pipeline Hazards:

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

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

• Control: Uncertainty due to branches/jumps. Solved by branch prediction, delayed slots.

Advanced CPU Architectures

RISC vs CISC

Instruction-Level Parallelism (ILP) vs Thread-Level Parallelism (TLP)

• ILP: Exploits parallelism within a single instruction stream.

  • Examples: Pipelining, Superscalar (multiple execution units, e.g., 4 ALUs), Out-of-Order Execution (OoO), Speculative Execution.

  • Goal: Execute multiple instructions from the same thread in parallel.

• TLP: Exploits parallelism across multiple instruction streams (threads).

  • Examples: Multicore Processors (multiple CPU cores), Simultaneous Multithreading (SMT/Hyper-Threading) (multiple threads share one core's resources).

  • Goal: Keep CPU resources busy by switching between threads when one stalls.

Multicore Processor Architecture

A single physical processor package containing multiple independent CPU cores (e.g., Dual-core, Quad-core, Octa-core). Each core has its own:

• Fetch/Decode logic

• ALU, FPU

• L1 cache (often split into I-cache & D-cache)

Cores share:

• L2/L3 cache

• Memory controller

• System bus interface

• Challenge: Programming for parallelism (Amdahl's Law).

Case Study: ARM Processor Architecture

• RISC-based, Load/Store architecture.

• Fixed 32-bit instruction length (ARM state) & optional 16-bit Thumb for code density.

• Large register file (16 x 32-bit visible registers, R13=SP, R14=LR, R15=PC).

• Conditional Execution: Most instructions can be predicated (execute only if condition true), reducing branches.

• Pipeline: Classic 3-stage (Fetch, Decode, Execute) or 5-stage (ARM7/9). Modern cores (Cortex-A) are deeply pipelined, superscalar, OoO.

• Power Efficiency: Key design goal, making it dominant in mobile/embedded.

III. Arithmetic and Logic Unit (ALU)

Fixed-point Arithmetic

• Addition/Subtraction: Use 2's complement arithmetic for signed numbers. Subtraction A - B is A + (2's complement of B). The same hardware adder circuit performs both operations. Check for overflow (carry into sign bit ≠ carry out of sign bit).

Floating-point Arithmetic (IEEE 754 Standard)

Single Precision (32-bit): 1 bit sign | 8 bit exponent (bias 127) | 23 bit mantissa (fraction, implicit leading 1). Double Precision (64-bit): 1 | 11 | 52.

Floating-Point Addition/Subtraction Flowchart:

1. Align Exponents: Shift the mantissa of the number with the smaller exponent right until exponents are equal. (Loss of precision).

2. Add/Subtract Mantissas: Perform fixed-point addition/subtraction on aligned mantissas.

3. Normalize Result: Shift result mantissa left/right to restore form 1.xxxxx. Adjust exponent accordingly.

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

5. Check for Special Cases: Overflow, underflow, NaN, Infinity.

Arithmetic Unit Handling: A dedicated Floating-Point Unit (FPU) handles these complex, multi-cycle operations, often using a separate pipeline.

Decimal Arithmetic (BCD)

• BCD Representation: Each decimal digit (0-9) is represented by its 4-bit binary equivalent. Packed BCD stores two digits per byte.

• Arithmetic: Addition/subtraction must be done digit-by-digit with adjustment after each operation (e.g., DAA - Decimal Adjust Accumulator instruction in x86 after ADD). If a digit sum > 9 or carry occurs, add 6 to correct to valid BCD.

• Arithmetic Unit Handling: Requires additional logic for BCD adjustment. Slower than pure binary. Used in financial/commercial applications where decimal precision is critical.

IV. Memory Systems

Memory Hierarchy

A pyramid of storage levels with increasing speed, decreasing size, and increasing cost per bit as you move up.

Role of Cache: Exploits locality of reference (temporal & spatial). By keeping frequently accessed data in a small, fast cache, the average memory access time (AMAT) is drastically reduced, improving system performance.

Cache Memory Organization

Cache is a small, fast SRAM placed between CPU and main memory. It holds blocks/lines of data from main memory.

Key Parameters:

• Block Size (b): Number of bytes transferred per memory access (e.g., 32, 64 bytes).

• Cache Size (C): Total capacity.

• Number of Blocks (N): $$\displaystyle N = C / b $$.

• Address Format: [Tag | Index | Offset]

Mapping Techniques

1. Direct Mapped:

   • Each main memory block maps to exactly one cache line (index = (Block Address) mod N).

   • Merits: Simple, fast hardware. Easy to implement.

   • Demerits: High conflict misses (two hot blocks mapping to same line thrash). Low flexibility.

   • Hit: Tag field in cache line matches Tag from address.

2. Fully Associative:

   • A memory block can be placed in any cache line.

   • Merits: Lowest conflict miss rate. Maximum flexibility.

   • Demerits: Requires searching all N tags in parallel (expensive comparator hardware). Slow.

   • Hit: Tag from address matches any tag in cache.

3. Set-Associative (k-way):

   • Compromise. Cache is divided into N/k sets, each containing k lines. A block maps to a specific set (like direct-mapped), but can go into any line within that set.

   • Merits: Reduces conflict misses vs. direct-mapped. Hardware cost/comparison complexity is less than fully associative.

   • Demerits: More complex than direct-mapped. Still has conflict misses.

   • Hit: Tag from address matches any of the k tags in the indexed set.

[!TIP] Diagram Requirement: Be ready to draw the address breakdown for each mapping scheme and a simple cache organization diagram.

Multilevel Caches (L1, L2, L3)

• L1 Cache: Smallest, fastest, split into I-cache (instruction) and D-cache (data). On-chip, private to a core.

• L2 Cache: Larger, slightly slower. Can be private to a core or shared.

• L3 Cache: Largest, slowest (but still faster than RAM). Typically shared among all cores in a multicore chip.

• Inclusion Policy: Usually inclusive (L3 contains all data in L1/L2) or exclusive.

Performance Metrics

• Hit Ratio (h): Fraction of memory accesses found in cache.

• Miss Ratio (m): $1 - h$.

• Hit Time ($$\displaystyle t_c $$): Time for a cache access.

• Miss Penalty ($$\displaystyle t_m $$): Time to replace a block from main memory + deliver to CPU (includes $$\displaystyle t_c $$).

• Effective Access Time (EAT):

$$ \text{EAT} = h \times t_c + (1 - h) \times t_m $$

\boxed{\text{EAT} = t_c + (1 - h) \times \text{Miss Penalty}}

> **Miss Penalty** is often $$\displaystyle t_m - t_c $$.

[!TIP] Calculation: A classic exam question: "Calculate EAT given hit ratio, cache access time, main memory access time." Remember the formula and that $$\displaystyle t_m $$ typically includes the time to access main memory plus the time to transfer the block to cache.

Associative Memory

• Concept: Memory where the content (data) is used to find the address (like a hash table). Also called Content-Addressable Memory (CAM).

• Organization: Each stored word is compared in parallel with the search argument. All matching locations are flagged.

• Difference from Cache:

  • Cache: Uses address to find data (location-based access).

  • Associative Memory: Uses data to find address (content-based access).

  • Use Case: Fast lookup tables (e.g., TLB - Translation Lookaside Buffer for virtual-to-physical address translation).

Main Memory Organization

RAM (Random Access Memory)

• Static RAM (SRAM): Uses 6-transistor flip-flop cells. Fast, expensive, volatile. Used for cache.

• Dynamic RAM (DRAM): Uses 1-transistor + 1-capacitor cell. Slower, cheaper, dense, volatile. Needs periodic refresh. Used for main memory (DDR SDRAM).

ROM (Read-Only Memory)

Non-volatile, programmed during manufacturing or later.

• ROM: Mask-programmed.

• PROM: Programmable once by user (fuse links).

• EPROM: Erasable by UV light, reprogrammable.

• EEPROM: Electrically erasable/programmable (byte-wise).

• Flash Memory: A type of EEPROM with block-wise erase. Used in SSDs, USB drives.

V. Input/Output Organization

I/O Methods and Comparison

Interrupts

A mechanism for an I/O device or exception to asynchronously get the CPU's attention.

Types:

• Hardware vs. Software: Hardware (from device) vs. Software (INT instruction, exceptions).

• Maskable vs. Non-Maskable (NMI): Can CPU ignore? Maskable (yes, via interrupt flag), NMI (no, critical like power failure).

• Vectored vs. Non-Vectored: Does interrupt provide its service routine address? Vectored (device supplies vector/index to interrupt table) is faster. Non-vectored requires CPU to poll devices to find source.

Interrupt Handling & Priority:

1. CPU finishes current instruction, saves PC and status registers (context).

2. Disables further interrupts (usually).

3. Jumps to Interrupt Service Routine (ISR) via interrupt vector table (for vectored).

4. ISR executes, services the device.

5. Restores context, re-enables interrupts, returns to original program.

Priority Management: Hardware interrupt controller (e.g., 8259 PIC, APIC) manages multiple interrupt requests. It can prioritize (highest priority served first), mask (disable lower priorities), and cascade (multiple controllers).

Case Study: 8086 Microprocessor Interrupts

• Interrupt Types: TYPE 0 (Divide Error) to TYPE 255.

• Vectored: Hardware interrupts INTR (maskable, non-vectored) and NMI (non-maskable, vectored). INTR requires external interrupt controller (8259) to provide vector.

• Interrupt Vector Table (IVT): Located at physical address 0000:0000. Contains 4-byte far pointers (CS:IP) for each ISR.

• Response: CPU sends INTA (Interrupt Acknowledge) pulse. For INTR, CPU reads interrupt type number from data bus during second INTA. Uses this number to index IVT (index = type * 4). For NMI, type is fixed 2.

I/O Channels and Processors

• I/O Channel: A dedicated, programmable I/O processor with its own instruction set. It executes channel programs stored in memory to control complex I/O operations (e.g., moving blocks, seeking disks). Offloads I/O management from CPU.

• I/O Processor (IOP): A more powerful, general-purpose processor dedicated to I/O tasks. Can perform computations on I/O data (e.g., graphics processor).

Data Transfer Techniques

Serial vs Parallel Transfer

Strobe Method (Handshaking)

A synchronous method for reliable data transfer between two units (source & destination) using a strobe control signal.

Source-Initiated (Source sends data):

1. Source places data on data lines.

2. Source activates strobe signal (e.g., goes high).

3. Destination reads data when it detects strobe.

4. Destination may acknowledge (optional).

5. Source deactivates strobe after a delay, removes data.

Diagram: Shows two blocks (Source, Destination), data lines (D0-D7), and a single STROBE line from Source to Destination. Timing diagram shows Data stable, then STROBE pulse, then data change.

[!TIP] Exam Tip: Be able to draw the timing diagram for the strobe method and explain the role of the strobe signal (indicates data is valid).

VI. Advanced Topics

Vector Processing

• Concept: Processing of vectors (one-dimensional arrays) using a single instruction that operates on multiple data elements simultaneously. Requires vector registers and pipelined functional units (e.g., 8-element vector add in one cycle).

• Applications: Scientific computing, matrix operations, signal processing, graphics (SIMD extensions like SSE, AVX are modern forms).

• Key Feature: Reduced instruction fetching overhead (one instruction for many operations).

Optical Storage (CD, DVD, Blu-ray)

• Principle: Data stored as pits (bumps) on a spiral track on a reflective disc. A laser beam reads the disc; pits cause interference (destructive) vs. lands (constructive), detected as 0/1.

• Characteristics:

  • CD: ~700 MB, 780 nm red laser, single layer.

  • DVD: 4.7 GB (single layer), 650 nm red laser, smaller pits.

  • Blu-ray: 25-50 GB (single layer), 405 nm blue-violet laser (shorter wavelength → smaller pits → higher density). Often dual/triple layer.

• Advantages: Low cost, removable, durable (no physical contact).

• Disadvantages: Slower access than HDD/SSD, sequential access pattern, lower capacity than modern HDD/SSD.