Cheatsheet Computer Architecture & Organisation (CAO) - Computer Architecture

2. Boolean Algebra & Logic Gates

2.1 Boolean Laws & Theorems

2.2 Basic Logic Gates

• NAND and NOR are universal gates (can implement any Boolean function)

2.3 Canonical Forms

2.4 K-Map (Karnaugh Map) Minimization

• 2-variable K-map: 2×2 grid (4 cells)
• 3-variable K-map: 2×4 grid (8 cells)
• 4-variable K-map: 4×4 grid (16 cells)
• Group cells in powers of 2: 1, 2, 4, 8, 16
• Larger groups → fewer literals in minimized expression
• Don't care conditions (X) can be grouped as 0 or 1 for optimization

3. Combinational Circuits

3.1 Adders

• Ripple Carry Adder: n full adders cascaded. Delay = n × (delay of full adder)
• Carry Look-Ahead Adder: Uses generate and propagate logic to compute carries faster than ripple carry adders.
• Carry Save Adder: Used for multiple operand addition

3.2 Subtractors

3.3 Multiplexer (MUX)

• 2ⁿ:1 MUX has n select lines, 2ⁿ data inputs, 1 output
• Selects one of many inputs based on select lines
• Can implement any Boolean function
• 4:1 MUX: Y = S1'·S0'·I0 + S1'·S0·I1 + S1·S0'·I2 + S1·S0·I3

3.4 Demultiplexer (DEMUX)

• 1:2ⁿ DEMUX has n select lines, 1 data input, 2ⁿ outputs
• Routes input to one of many outputs based on select lines
• Functions as a decoder when data input is enabled

3.5 Encoder & Decoder

3.6 Comparator

• Compares two n-bit numbers A and B
• Outputs: A>B, A=B, A<>
• 1-bit comparator:
  A = B when A ⊕ B = 0
  A > B when A · B' = 1
  A < B when A' · B = 1

3.7 Parity Generator & Checker

• Even parity: total number of 1s (including parity bit) is even
• Odd parity: total number of 1s is odd
• Generated using XOR gates cascaded

4. Sequential Circuits

4.1 Flip-Flops

• SR Flip-Flop: S=1,R=1 is invalid state
• JK Flip-Flop: J=1,K=1 toggles output (solves SR limitation)
• Edge-triggered: responds to clock edge (positive or negative)
• Level-triggered (Latch): responds to clock level

4.2 Registers

• Bidirectional Shift Register: can shift left or right
• Universal Shift Register: can perform all operations (SISO, SIPO, PISO, PIPO)

4.3 Counters

• n-bit counter: modulo-2ⁿ (counts 2ⁿ states: 0 to 2ⁿ-1)
• Modulo-m counter: counts m states and resets when the count reaches m.
• Decade counter: modulo-10 counter (counts 0-9)

5. Central Processing Unit (CPU)

5.1 CPU Components

5.2 Instruction Cycle

• Fetch: PC → MAR; Memory[MAR] → MDR → IR; PC = PC + instruction_size
• Decode: Control unit decodes instruction in IR, identifies operation and operands
• Execute: Perform operation specified by instruction
• Interrupt (if any): Handle interrupts before next fetch

5.3 Instruction Format

5.4 Addressing Modes

5.5 Instruction Types

• Data Transfer: MOV, LOAD, STORE, PUSH, POP, EXCHANGE
• Arithmetic: ADD, SUB, MUL, DIV, INC, DEC
• Logical: AND, OR, NOT, XOR, SHIFT, ROTATE
• Control Transfer: JUMP, CALL, RETURN, BRANCH
• I/O: INPUT, OUTPUT

5.6 Control Unit Design

6. Processor Architecture

6.1 RISC vs CISC

6.2 Pipelining

• Overlapping execution of multiple instructions
• 5-stage pipeline: IF (Fetch) → ID (Decode) → EX (Execute) → MEM (Memory) → WB (Write Back)
• Speedup = (Non-pipelined execution time) / (Pipelined execution time)
  Ideal speedup ≈ Number of pipeline stages (k)
• Max speedup = Number of pipeline stages (ideal case)
• Throughput = n / (k + n - 1) instructions per cycle, where n=instructions, k=stages

6.3 Pipeline Hazards

6.3.1 Data Hazard Types

• RAW (Read After Write): True dependency. Most common
• WAR (Write After Read): Anti-dependency
• WAW (Write After Write): Output dependency

6.4 Instruction Level Parallelism (ILP)

• Superscalar: Multiple instructions issued per cycle from single instruction stream
• VLIW (Very Long Instruction Word): Compiler packs multiple operations into one instruction
• Out-of-Order Execution: Execute instructions as operands become available
• Speculative Execution: Execute instructions before knowing if needed (branch prediction)

6.5 Flynn's Taxonomy

7. Memory Organization

7.1 Memory Hierarchy

7.2 RAM Types

7.3 ROM Types

7.4 Cache Memory

7.5 Cache Mapping Techniques

7.5.1 Mapping Comparison

7.6 Cache Replacement Policies

7.7 Cache Write Policies

7.8 Virtual Memory

• Separation of logical address space from physical address space
• Allows execution of programs larger than physical memory
• Logical Address = Page Number + Page Offset
• Physical Address = Frame Number + Frame Offset
• Page size = Frame size (power of 2)

7.8.1 Paging

• Logical address bits: n = page bits + offset bits
• Number of pages = 2^page_bits
• Page/Frame size = 2^offset_bits

7.8.2 Segmentation

• Variable-size segments based on logical divisions (code, data, stack)
• Logical Address = Segment Number + Offset
• Segment Table: contains base address and limit for each segment

7.8.3 Page Replacement Algorithms

• Belady's Anomaly: More frames can lead to more page faults (FIFO)

7.9 Memory Interleaving

8. Input/Output Organization

8.1 I/O Interface

8.2 I/O Data Transfer Modes

8.3 DMA Transfer

• DMA Controller contains: Address register, Word count register, Control register
• Modes: Burst (block) mode, Cycle stealing mode, Transparent mode
• Steps: CPU initializes DMA → DMA requests bus → Bus granted → DMA transfers data → Interrupt on completion

8.4 Interrupts

8.4.1 Interrupt Processing

• Device sends interrupt signal → CPU finishes current instruction → Save context (PC, registers) → Identify interrupt source → Jump to ISR (Interrupt Service Routine) → Execute ISR → Restore context → Resume execution

8.4.2 Interrupt Priority

• Daisy Chain: Serial priority. Simple, slow
• Parallel Priority: Hardware priority encoder. Fast, complex
• Software Poll: CPU checks each device in sequence

8.5 Bus Organization

8.5.1 Bus Arbitration

8.6 I/O Processor

• Independent processor dedicated to I/O operations
• Channel: executes channel programs for I/O operations
• Types: Selector channel (high-speed devices), Multiplexor channel (low-speed devices)

9. Performance Metrics

9.1 Key Formulas

9.2 Amdahl's Law

• Maximum speedup limited by non-enhanced portion
• If f=0.8 enhanced with S=5, max speedup = 1 / (0.2 + 0.8/5) = 2.78
• As S→∞, max speedup → 1/(1-f)

9.3 Benchmark Types

• Synthetic Benchmarks: Dhrystone, Whetstone, Linpack
• Application Benchmarks: SPEC (Standard Performance Evaluation Corporation)

10. Miscellaneous Topics

10.1 Booth's Algorithm

• Efficient binary multiplication using 2's complement
• Based on examining pairs of bits: current and previous
• 00 or 11: Arithmetic shift right
• 01: Add multiplicand, then shift
• 10: Subtract multiplicand, then shift
• Reduces number of additions/subtractions

10.2 Restoring vs Non-Restoring Division

10.3 Hamming Code

• Error detection and single-bit error correction
• Parity bits at positions 2ⁱ: 1, 2, 4, 8, 16...
• For m data bits, need r parity bits where 2^r ≥ m + r + 1
• Parity bit at position 2ⁱ covers positions where bit i is 1 in binary representation
• Error position = sum of positions of incorrect parity bits

10.4 Multiprocessor Systems

10.5 Cache Coherence

• Problem: Multiple caches may have copies of same memory block
• Write-Update: Update all copies on write
• Write-Invalidate: Invalidate other copies on write
• Snoopy Protocol: All caches monitor bus for relevant transactions
• Directory-Based: Central directory tracks cache line status

10.6 RAID Levels

10.7 Endianness

10.8 Memory Mapping

• Memory-Mapped I/O: I/O devices share address space with memory. Same instructions for memory and I/O
• I/O-Mapped I/O (Isolated I/O): Separate address space for I/O. Special I/O instructions (IN, OUT)