Important Formulas — Computer Organization & Architecture

Introduction

Computer Organization is a formula-heavy subject. Whether you are preparing for GATE, university exams, or technical interviews, having these formulas at your fingertips makes all the difference between struggling through problems and solving them confidently. This page organizes every important formula by topic, with brief explanations of when and how to use each one. Bookmark this page — you will come back to it often.

CPU Performance Formulas

Basic CPU Time

The fundamental performance equation connects three factors:

Or equivalently:

Where:

• Instruction Count (IC): Number of instructions executed by the program
• CPI (Cycles Per Instruction): Average clock cycles per instruction
• Clock Cycle Time: Duration of one clock cycle (= 1/Clock Rate)

MIPS (Million Instructions Per Second)

Caution: MIPS is misleading because different ISAs need different instruction counts for the same task. A RISC machine may have higher MIPS but more instructions.

Weighted Average CPI

When different instruction types have different cycle counts:

Example: If 50% of instructions take 1 cycle, 30% take 2 cycles, and 20% take 4 cycles: CPI = 0.5×1 + 0.3×2 + 0.2×4 = 0.5 + 0.6 + 0.8 = 1.9

Speedup

Amdahl's Law

Where:

• f = fraction of execution time that can be improved
• S = speedup of the improved portion

Maximum possible speedup (S → ∞):

Gustafson's Law (Scaled Speedup)

Where S = number of processors, α = serial fraction. More optimistic than Amdahl's for parallel scaling.

Memory Hierarchy Formulas

Effective Memory Access Time

For single-level cache:

Or equivalently:

Multi-Level Cache AMAT

For three levels:

Cache Organization

Address Bit Breakdown

For a cache with S sets, B bytes per block, total address of A bits:

Cache Miss Rate Types

Memory Bandwidth

For DDR (Double Data Rate):

Virtual Memory Formulas

Page Table Size

Effective Access Time with TLB

(With page fault):

Where p = page fault rate.

Number of Levels in Multi-Level Paging

If page table does not fit in one page:

Pipelining Formulas

Pipeline Clock Cycle

Pipeline Execution Time

For n instructions in k-stage pipeline:

Pipeline Speedup

Where τ = non-pipelined cycle time, τ_p = pipeline cycle time.

For large n (steady state):

Ideal speedup (τ = k × τ_p): Speedup = k

Pipeline Throughput

Maximum throughput = 1/Pipeline_cycle_time

CPI with Stalls

Branch Penalty

I/O and DMA Formulas

Data Transfer Rate

DMA Transfer Time

Bus Bandwidth Utilization by DMA

Disk Access Time

Arithmetic Formulas

Booth's Multiplication

Number of additions/subtractions in Booth's algorithm depends on bit transitions in multiplier:

• 0→1 transition: Subtract
• 1→0 transition: Add
• Same consecutive bits: Shift only

Floating Point Range (IEEE 754)

Single Precision:

Double Precision:

Carry Lookahead Adder

Expanding for CLA:

Parallel Processing Formulas

Speedup (with p processors)

Flynn's Classification (Reference)

• SISD: Single Instruction, Single Data (uniprocessor)
• SIMD: Single Instruction, Multiple Data (vector/GPU)
• MISD: Multiple Instruction, Single Data (rare, fault tolerance)
• MIMD: Multiple Instruction, Multiple Data (multicore, clusters)

Quick Reference: Units and Conversions

Formula Application Tips

1. Always check units — convert everything to consistent units before calculating
2. Miss rate = 1 - Hit rate — simple but often confused under pressure
3. Pipeline speedup assumes ideal — real speedup is always less due to hazards
4. Amdahl's Law fraction f refers to time fraction, not instruction fraction
5. AMAT formula nests — for multi-level caches, the penalty of one level includes the next level's AMAT
6. CPI is an average — different programs have different CPI on the same processor