Computer Organization and Architecture — Complete Notes

Unit 1: Number Systems and Data Representation

Number Systems

| System | Base | Digits | Prefix | |---|---|---|---| | Binary | 2 | 0,1 | 0b | | Octal | 8 | 0-7 | 0o | | Decimal | 10 | 0-9 | — | | Hexadecimal | 16 | 0-9, A-F | 0x |

Conversions:

Decimal to Binary: Divide by 2, collect remainders in reverse. 45 → 45/2=22r1, 22/2=11r0, 11/2=5r1, 5/2=2r1, 2/2=1r0, 1/2=0r1 → 101101

Binary to Decimal: Multiply each bit by 2^position. 101101 = 32+0+8+4+0+1 = 45

Binary to Hex: Group 4 bits from right. 1011 0101 → B5 (hex)

Integer Representation

Sign-Magnitude: MSB is sign bit (0=positive, 1=negative)

• +5 = 0101, -5 = 1101

1's Complement: Flip all bits

• +5 = 0101, -5 = 1010

2's Complement (Most used!): Flip all bits + add 1

• +5 = 0101, -5 = 1011
• Self-consistent arithmetic, single zero

Range for n-bit 2's complement: -2^(n-1) to +2^(n-1) - 1

• 8-bit: -128 to +127
• 16-bit: -32768 to +32767

Floating Point (IEEE 754)

Single Precision (32-bit):

• 1 sign bit + 8 exponent bits + 23 mantissa bits
• Value = (-1)^S × 1.Mantissa × 2^(Exponent-127)

Double Precision (64-bit):

• 1 + 11 + 52 bits
• Exponent bias = 1023

---

Unit 2: ALU and Arithmetic Operations

Adder Circuits

Half Adder: Adds 2 single bits

• Sum = A ⊕ B (XOR)
• Carry = A·B (AND)

Full Adder: Adds 3 bits (A, B, Cin)

• Sum = A ⊕ B ⊕ Cin
• Cout = AB + BCin + ACin

Ripple Carry Adder: Chain of full adders; carry ripples through — slow for large n.

Carry Lookahead Adder (CLA): Computes carries in parallel — faster O(log n).

Multiplication Algorithms

Booth's Algorithm: Handles both positive and negative multiplication efficiently.

• Key rule: Look at current and previous bit
  • 01 → Add multiplicand
  • 10 → Subtract multiplicand
  • 00, 11 → No operation (just shift)

Array Multiplier: Hardware implementation using AND gates and adders.

---

Unit 3: CPU Organization

Basic CPU Structure

         ┌─────────────────────────────────┐
         │           CPU                   │
         │  ┌──────────┐  ┌──────────────┐ │
Input ───┤  │  Control │  │     ALU      │ │──→ Output
         │  │   Unit   │  │              │ │
         │  └──────────┘  └──────────────┘ │
         │  ┌──────────────────────────────┤
         │  │     Register File            │ │
         │  │ PC, IR, ACC, MAR, MDR, SP   │ │
         │  └──────────────────────────────┤
         └─────────────────────────────────┘

Key Registers: | Register | Full Name | Purpose | |---|---|---| | PC | Program Counter | Address of next instruction | | IR | Instruction Register | Current instruction being executed | | MAR | Memory Address Register | Address to read/write | | MDR | Memory Data Register | Data to/from memory | | ACC | Accumulator | Stores intermediate results | | SP | Stack Pointer | Points to top of stack | | PSW | Program Status Word | Flags (Z, N, C, V) |

Instruction Cycle

1. Fetch: PC → MAR, Memory[MAR] → MDR → IR, PC++
2. Decode: Control unit interprets opcode in IR
3. Execute: ALU performs operation
4. Write Back: Store result to register/memory

Instruction Formats

3-Address: OP D, S1, S2 → D = S1 OP S2 (more flexibility) 2-Address: OP D, S → D = D OP S (source or destination) 1-Address: OP X → ACC = ACC OP X (accumulator-based) 0-Address: OP → uses stack (stack machine)

Addressing Modes

| Mode | Effective Address | Example | |---|---|---| | Immediate | Operand is the value | ADD #5 | | Register | Operand in register | ADD R1 | | Direct | EA = address in instruction | ADD 2000H | | Indirect | EA = Memory[address] | ADD (2000H) | | Register Indirect | EA = Memory[Register] | ADD (R1) | | Indexed | EA = address + index register | ADD 100H(R1) | | Base+Offset | EA = base + offset | Used in arrays |

---

Unit 4: Memory Hierarchy

     Fastest/Smallest/Most Expensive
     ┌─────────────────┐
     │   Registers      │ ~1 ns, bytes
     ├─────────────────┤
     │   Cache (L1/L2/L3)│ ~2-20 ns, KB-MB
     ├─────────────────┤
     │   Main RAM       │ ~100 ns, GB
     ├─────────────────┤
     │   SSD/HDD        │ ~100μs-10ms, TB
     └─────────────────┘
     Slowest/Largest/Cheapest

Cache Memory

Principle of Locality:

• Temporal locality: recently accessed data likely to be accessed again
• Spatial locality: data near recently accessed data likely to be accessed soon

Cache Mapping Techniques:

| Technique | How | Advantage | Disadvantage | |---|---|---|---| | Direct Mapped | Block maps to exactly one cache line | Simple, fast | High miss rate (conflicts) | | Fully Associative | Block can go anywhere | Maximum flexibility | Complex, expensive | | Set Associative | Block maps to one set (2/4/8-way) | Balance of both | Moderate complexity |

Cache Write Policies:

• Write-through: Write to cache AND memory simultaneously — consistent, slow
• Write-back: Write only to cache; write to memory when evicted — faster but risk of loss

Cache Replacement Policies:

• LRU (Least Recently Used): Replace oldest unused — best performance
• FIFO: Replace oldest loaded block
• Random: Replace random block — simple

Hit rate and Miss penalty: Average access time = Hit rate × Cache time + Miss rate × (Cache time + Memory time)

---

Unit 5: Pipelining

Pipelining is an implementation technique where multiple instructions are overlapped in execution.

5-Stage RISC Pipeline:

1. IF — Instruction Fetch
2. ID — Instruction Decode & Register Fetch
3. EX — Execute / ALU operation
4. MEM — Memory Access
5. WB — Write Back to register

Ideal Speedup: k-stage pipeline → k× speedup over non-pipelined

Pipeline Hazards (Problems):

1. Structural Hazards

Resource conflict — two instructions need same hardware simultaneously. Solution: Stall pipeline (insert bubble) or duplicate hardware.

2. Data Hazards

Instruction depends on result of previous instruction not yet completed.

ADD R1, R2, R3   ; R1 = R2 + R3
SUB R4, R1, R5   ; Needs R1 (not ready yet!) → Hazard

Solutions:

• Stalling: Insert NOPs (bubbles) until dependency resolved
• Forwarding/Bypassing: Pass result directly to next instruction without waiting for WB
• Out-of-order execution: Reorder instructions to avoid hazard

3. Control Hazards

Branch instructions — pipeline doesn't know which instruction to fetch next. Solutions:

• Stall: Wait until branch resolved (wastes cycles)
• Branch prediction: Predict taken/not-taken; flush if wrong
  • Static: always predict not-taken
  • Dynamic: use branch history table (BTB)
• Delayed branching: Execute instruction after branch regardless

---

Unit 6: I/O Organization

I/O Techniques:

| Technique | CPU involvement | Use Case | |---|---|---| | Programmed I/O (Polling) | 100% — busy waits | Simple, slow devices | | Interrupt-driven I/O | On completion only | Most general devices | | DMA (Direct Memory Access) | Only setup + completion | High-speed bulk transfer |

DMA Operation:

1. CPU tells DMA: source address, destination, count, direction
2. DMA takes control of bus, transfers data directly
3. DMA interrupts CPU when done

Bus Architecture:

• System bus: connects CPU, Memory, I/O
• Address bus: carries memory address (unidirectional)
• Data bus: carries data (bidirectional)
• Control bus: carries control signals (direction varies)

---

Solved PYQs

Q1 (2023): Convert (0.625)₁₀ to binary. 0.625 × 2 = 1.25 → 1 0.25 × 2 = 0.5 → 0 0.5 × 2 = 1.0 → 1 (0.625)₁₀ = (0.101)₂

Q2 (2022): Show Booth's multiplication: 7 × (-3) in 4-bit. 7 = 0111, -3 = 1101 (2's complement) Apply Booth's algorithm: result = -21 = 101011 (6-bit 2's complement)

Q3 (2024): What is the speedup of a 5-stage pipeline over non-pipelined for 100 instructions? Without pipeline: 5 × 100 = 500 cycles With pipeline: 5 + (100-1) = 104 cycles Speedup = 500/104 ≈ 4.81×

Q4 (2023): Cache has hit time 10ns, main memory 200ns, hit rate 90%. Find average access time. Average = 0.9 × 10 + 0.1 × (10 + 200) = 9 + 21 = 30 ns

---

Quick Revision Checklist

• 2's complement: flip bits + add 1; range -2^(n-1) to 2^(n-1)-1
• IEEE 754: 1+8+23 single; 1+11+52 double
• Full adder: Sum = A⊕B⊕Cin, Cout = AB+BCin+ACin
• Key registers: PC, IR, MAR, MDR, ACC, SP
• 5 addressing modes: immediate, register, direct, indirect, indexed
• Cache mapping: direct, fully associative, set associative
• LRU vs FIFO replacement
• 3 pipeline hazards: structural, data, control
• Forwarding solves data hazards
• DMA for bulk data transfer