COA Cheatsheet

Quick reference cheatsheet for computer organization formulas, concepts, and key facts.

Introduction

This cheatsheet is your go-to quick reference before exams or interviews. It covers all the essential formulas, concepts, and key facts from Computer Organization and Architecture in a condensed format. Think of it as your last-minute revision companion — everything important, nothing extra.

Number Systems and Data Representation

Conversion Quick Reference

Binary to Decimal: Multiply each bit by its positional weight (powers of 2) and sum them up. Example: 1011₂ = 1×8 + 0×4 + 1×2 + 1×1 = 11₁₀
Decimal to Binary: Repeatedly divide by 2, collect remainders bottom-to-top
Hexadecimal: Group binary digits in sets of 4. Example: 1010 1111₂ = AF₁₆
Octal: Group binary digits in sets of 3. Example: 101 111₂ = 57₈

Signed Number Representations

Method	Range (n bits)	Key Feature
Sign-Magnitude	-(2ⁿ⁻¹-1) to +(2ⁿ⁻¹-1)	Two zeros (+0, -0)
1's Complement	-(2ⁿ⁻¹-1) to +(2ⁿ⁻¹-1)	Invert all bits for negative
2's Complement	-2ⁿ⁻¹ to +(2ⁿ⁻¹-1)	One zero, most used in hardware

IEEE 754 Floating Point

Single Precision (32-bit): 1 sign + 8 exponent + 23 mantissa, bias = 127
Double Precision (64-bit): 1 sign + 11 exponent + 52 mantissa, bias = 1023
Value = (-1)ˢ × 1.mantissa × 2^(exponent - bias)

Performance Formulas

CPU Performance

Example

CPU Time = Instruction Count × CPI × Clock Cycle Time CPU Time = Instruction Count × CPI / Clock Rate MIPS = Clock Rate / (CPI × 10⁶) Speedup = Time_old / Time_new

Amdahl's Law

Example

Speedup = 1 / [(1 - f) + f/S]

Where f = fraction of program that can be enhanced, S = speedup of enhanced portion. This tells you that even with infinite speedup on a fraction, overall improvement is limited by the sequential portion.

Memory Performance

Example

Effective Access Time = Hit_rate × Cache_time + Miss_rate × Memory_time Average Memory Access Time (AMAT) = Hit_time + Miss_rate × Miss_penalty

For multi-level cache:

Example

AMAT = L1_hit_time + L1_miss_rate × (L2_hit_time + L2_miss_rate × Memory_penalty)

Cache Memory Key Facts

Cache Mapping Techniques

Technique	Placement	Comparison	Pros	Cons
Direct Mapped	One fixed location	1 comparator	Simple, fast	High conflict misses
Fully Associative	Any location	N comparators	No conflict misses	Expensive hardware
Set Associative (N-way)	Any slot in one set	N comparators	Balanced	Moderate complexity

Cache Address Breakdown

For direct-mapped cache with 2ᵏ blocks of 2ⁿ bytes each:

Offset bits = n (to address bytes within a block)
Index bits = k (to select the cache line)
Tag bits = Address_bits - k - n

Replacement Policies

LRU (Least Recently Used): Replace the block not accessed for longest time
FIFO (First In First Out): Replace the oldest block
Random: Replace any block randomly — surprisingly effective

Write Policies

Write-through: Write to both cache and memory simultaneously (simpler, slower)
Write-back: Write only to cache, write to memory on eviction (faster, complex)

Pipelining Formulas

Basic Pipeline Performance

Example

Pipeline cycle time = Max(stage delays) + Pipeline register overhead Pipeline throughput = 1 / Pipeline cycle time Speedup (ideal) = Number of stages (k) Speedup (actual) = k / [1 + (k-1)/n] for n instructions

Pipeline with Stalls

Example

CPI_pipeline = 1 + Pipeline stall cycles per instruction Speedup = CPI_non-pipelined / (1 + Stall_cycles_per_instruction)

Hazards Summary

Structural Hazard: Two instructions need same hardware — fix with resource duplication
Data Hazard: Instruction depends on result of previous — fix with forwarding/stalling
Control Hazard: Branch outcome not known — fix with prediction, delayed branching

Data Hazard Types (RAW, WAR, WAW)

RAW (Read After Write): True dependency — most common, requires forwarding
WAR (Write After Read): Anti-dependency — problem in out-of-order execution
WAW (Write After Write): Output dependency — problem in out-of-order execution

I/O Organization

DMA Transfer Time

Example

Transfer time = Data_size / Transfer_rate DMA overhead = Setup_time + (Blocks × Interrupt_handling_time)

I/O Methods Comparison

Method	CPU Involvement	Speed	Use Case
Programmed I/O	100% (busy waiting)	Slowest	Simple devices
Interrupt-driven	Only during transfer	Medium	Keyboard, mouse
DMA	Only at start/end	Fastest	Disk, network

Instruction Set Architecture

Instruction Formats

Three-address: OP Dest, Src1, Src2 — most flexible, longer instructions
Two-address: OP Dest/Src1, Src2 — one operand is both source and destination
One-address: OP Operand — uses accumulator implicitly
Zero-address: OP — uses stack (push/pop operations)

Addressing Modes

Mode	Operand Location	Use
Immediate	In instruction itself	Constants
Direct	Memory[Address]	Simple variables
Indirect	Memory[Memory[Address]]	Pointers
Register	In register	Fast access
Register Indirect	Memory[Register]	Array traversal
Indexed	Memory[Base + Offset]	Array elements
Relative	Memory[PC + Offset]	Branch targets

Register Transfer Language

Common RTL Notations

Example

R1 ← R2 (Transfer content of R2 to R1) R1 ← R1 + R2 (Add and store) M[AR] ← R1 (Store register to memory at address in AR) R1 ← M[AR] (Load from memory to register) If (condition): R1 ← R2 (Conditional transfer)

Microoperation Types

Arithmetic: Add, subtract, increment, decrement, complement
Logic: AND, OR, XOR, NOT, shift
Shift: Logical shift, arithmetic shift, circular shift (rotate)
Transfer: Register-to-register, memory-to-register

Quick Number Crunching

Powers of 2 (Memorize These)

Power	Value	Approx
2¹⁰	1,024	1K
2²⁰	1,048,576	1M
2³⁰	~1.07 billion	1G
2³²	~4.29 billion	4G (max 32-bit address space)

Common Clock Speed Conversions

1 GHz = 10⁹ Hz → 1 ns cycle time
2 GHz → 0.5 ns cycle time
3.5 GHz → ~0.286 ns cycle time

RISC vs CISC Quick Comparison

Feature	RISC	CISC
Instructions	Simple, fixed-length	Complex, variable-length
Addressing modes	Few (3-5)	Many (12-20)
Registers	Many (32+)	Few (8-16)
Cycles per instruction	Usually 1	Multiple (2-15)
Pipelining	Easy	Difficult
Examples	ARM, MIPS, RISC-V	x86, VAX

Bus System Facts

Synchronous bus: Operations tied to clock — simpler but limited by slowest device
Asynchronous bus: Handshaking protocol — flexible but complex
Bus width: Data bus width determines transfer bandwidth
Bus bandwidth = Bus_width × Transfer_rate

Key Exam Tips

Always specify whether you are using 2's complement or sign-magnitude when doing signed arithmetic
In cache problems, count bits carefully — tag + index + offset = total address bits
Pipeline speedup approaches k (stages) only when instruction count is much larger than k
DMA frees the CPU — but CPU still cannot access memory during DMA bus cycles
Amdahl's Law is the most commonly tested formula — practice with different f and S values
For GATE: Cache numerical problems and pipeline hazard detection are high-frequency topics

Introduction

Number Systems and Data Representation

Conversion Quick Reference

Binary to Decimal: Multiply each bit by its positional weight (powers of 2) and sum them up. Example: 1011₂ = 1×8 + 0×4 + 1×2 + 1×1 = 11₁₀
Decimal to Binary: Repeatedly divide by 2, collect remainders bottom-to-top
Hexadecimal: Group binary digits in sets of 4. Example: 1010 1111₂ = AF₁₆
Octal: Group binary digits in sets of 3. Example: 101 111₂ = 57₈

Signed Number Representations

Method	Range (n bits)	Key Feature
Sign-Magnitude	-(2ⁿ⁻¹-1) to +(2ⁿ⁻¹-1)	Two zeros (+0, -0)
1's Complement	-(2ⁿ⁻¹-1) to +(2ⁿ⁻¹-1)	Invert all bits for negative
2's Complement	-2ⁿ⁻¹ to +(2ⁿ⁻¹-1)	One zero, most used in hardware

IEEE 754 Floating Point

Single Precision (32-bit): 1 sign + 8 exponent + 23 mantissa, bias = 127
Double Precision (64-bit): 1 sign + 11 exponent + 52 mantissa, bias = 1023
Value = (-1)ˢ × 1.mantissa × 2^(exponent - bias)

Performance Formulas

CPU Performance

Example

CPU Time = Instruction Count × CPI × Clock Cycle Time CPU Time = Instruction Count × CPI / Clock Rate MIPS = Clock Rate / (CPI × 10⁶) Speedup = Time_old / Time_new

Amdahl's Law

Example

Speedup = 1 / [(1 - f) + f/S]

Memory Performance

Example

Effective Access Time = Hit_rate × Cache_time + Miss_rate × Memory_time Average Memory Access Time (AMAT) = Hit_time + Miss_rate × Miss_penalty

For multi-level cache:

Example

AMAT = L1_hit_time + L1_miss_rate × (L2_hit_time + L2_miss_rate × Memory_penalty)

Cache Memory Key Facts

Cache Mapping Techniques

Technique	Placement	Comparison	Pros	Cons
Direct Mapped	One fixed location	1 comparator	Simple, fast	High conflict misses
Fully Associative	Any location	N comparators	No conflict misses	Expensive hardware
Set Associative (N-way)	Any slot in one set	N comparators	Balanced	Moderate complexity

Cache Address Breakdown

For direct-mapped cache with 2ᵏ blocks of 2ⁿ bytes each:

Offset bits = n (to address bytes within a block)
Index bits = k (to select the cache line)
Tag bits = Address_bits - k - n

Replacement Policies

LRU (Least Recently Used): Replace the block not accessed for longest time
FIFO (First In First Out): Replace the oldest block
Random: Replace any block randomly — surprisingly effective

Write Policies

Write-through: Write to both cache and memory simultaneously (simpler, slower)
Write-back: Write only to cache, write to memory on eviction (faster, complex)

Pipelining Formulas

Basic Pipeline Performance

Example

Pipeline with Stalls

Example

CPI_pipeline = 1 + Pipeline stall cycles per instruction Speedup = CPI_non-pipelined / (1 + Stall_cycles_per_instruction)

Hazards Summary

Structural Hazard: Two instructions need same hardware — fix with resource duplication
Data Hazard: Instruction depends on result of previous — fix with forwarding/stalling
Control Hazard: Branch outcome not known — fix with prediction, delayed branching

Data Hazard Types (RAW, WAR, WAW)

RAW (Read After Write): True dependency — most common, requires forwarding
WAR (Write After Read): Anti-dependency — problem in out-of-order execution
WAW (Write After Write): Output dependency — problem in out-of-order execution

I/O Organization

DMA Transfer Time

Example

Transfer time = Data_size / Transfer_rate DMA overhead = Setup_time + (Blocks × Interrupt_handling_time)

I/O Methods Comparison

Method	CPU Involvement	Speed	Use Case
Programmed I/O	100% (busy waiting)	Slowest	Simple devices
Interrupt-driven	Only during transfer	Medium	Keyboard, mouse
DMA	Only at start/end	Fastest	Disk, network

Instruction Set Architecture

Instruction Formats

Three-address: OP Dest, Src1, Src2 — most flexible, longer instructions
Two-address: OP Dest/Src1, Src2 — one operand is both source and destination
One-address: OP Operand — uses accumulator implicitly
Zero-address: OP — uses stack (push/pop operations)

Addressing Modes

Mode	Operand Location	Use
Immediate	In instruction itself	Constants
Direct	Memory[Address]	Simple variables
Indirect	Memory[Memory[Address]]	Pointers
Register	In register	Fast access
Register Indirect	Memory[Register]	Array traversal
Indexed	Memory[Base + Offset]	Array elements
Relative	Memory[PC + Offset]	Branch targets

Register Transfer Language

Common RTL Notations

Example

Microoperation Types

Arithmetic: Add, subtract, increment, decrement, complement
Logic: AND, OR, XOR, NOT, shift
Shift: Logical shift, arithmetic shift, circular shift (rotate)
Transfer: Register-to-register, memory-to-register

Quick Number Crunching

Powers of 2 (Memorize These)

Power	Value	Approx
2¹⁰	1,024	1K
2²⁰	1,048,576	1M
2³⁰	~1.07 billion	1G
2³²	~4.29 billion	4G (max 32-bit address space)

Common Clock Speed Conversions

1 GHz = 10⁹ Hz → 1 ns cycle time
2 GHz → 0.5 ns cycle time
3.5 GHz → ~0.286 ns cycle time

RISC vs CISC Quick Comparison

Feature	RISC	CISC
Instructions	Simple, fixed-length	Complex, variable-length
Addressing modes	Few (3-5)	Many (12-20)
Registers	Many (32+)	Few (8-16)
Cycles per instruction	Usually 1	Multiple (2-15)
Pipelining	Easy	Difficult
Examples	ARM, MIPS, RISC-V	x86, VAX

Bus System Facts

Synchronous bus: Operations tied to clock — simpler but limited by slowest device
Asynchronous bus: Handshaking protocol — flexible but complex
Bus width: Data bus width determines transfer bandwidth
Bus bandwidth = Bus_width × Transfer_rate

Key Exam Tips

Always specify whether you are using 2's complement or sign-magnitude when doing signed arithmetic
In cache problems, count bits carefully — tag + index + offset = total address bits
Pipeline speedup approaches k (stages) only when instruction count is much larger than k
DMA frees the CPU — but CPU still cannot access memory during DMA bus cycles
Amdahl's Law is the most commonly tested formula — practice with different f and S values
For GATE: Cache numerical problems and pipeline hazard detection are high-frequency topics

Introduction

Number Systems and Data Representation

Conversion Quick Reference

Signed Number Representations

IEEE 754 Floating Point

Performance Formulas

CPU Performance

Amdahl's Law

Memory Performance

Cache Memory Key Facts

Cache Mapping Techniques

Cache Address Breakdown

Replacement Policies

Write Policies

Pipelining Formulas

Basic Pipeline Performance

Pipeline with Stalls

Hazards Summary

Data Hazard Types (RAW, WAR, WAW)

I/O Organization

DMA Transfer Time

I/O Methods Comparison

Instruction Set Architecture

Instruction Formats

Addressing Modes

Register Transfer Language

Common RTL Notations

Microoperation Types

Quick Number Crunching

Powers of 2 (Memorize These)

Common Clock Speed Conversions

RISC vs CISC Quick Comparison

Bus System Facts

Key Exam Tips

Continue learning this concept

Introduction

Number Systems and Data Representation

Conversion Quick Reference

Signed Number Representations

IEEE 754 Floating Point

Performance Formulas

CPU Performance

Amdahl's Law

Memory Performance

Cache Memory Key Facts

Cache Mapping Techniques

Cache Address Breakdown

Replacement Policies

Write Policies

Pipelining Formulas

Basic Pipeline Performance

Pipeline with Stalls

Hazards Summary

Data Hazard Types (RAW, WAR, WAW)

I/O Organization

DMA Transfer Time

I/O Methods Comparison

Instruction Set Architecture

Instruction Formats

Addressing Modes

Register Transfer Language

Common RTL Notations

Microoperation Types

Quick Number Crunching

Powers of 2 (Memorize These)

Common Clock Speed Conversions

RISC vs CISC Quick Comparison

Bus System Facts

Key Exam Tips

Continue learning this concept