Computer Basics and Performance

Computer organization is about how the parts of a computer are built and connected (data paths, control, memory); computer architecture is what the programmer sees (the instruction set, registers, addressing). GATE combines both.

The stored-program computer

In the von Neumann design, instructions and data are stored in the same memory, and the CPU fetches instructions from it one after another. Its main parts:

The CPU talks to memory and I/O over a bus: address lines (which location), data lines (the value) and control lines (read, write, timing). With n address lines, 2ⁿ locations can be addressed.

A Harvard design uses separate memories (or caches) for instructions and data, so an instruction fetch and a data access can happen in the same cycle. Modern CPUs have a von Neumann main memory but split L1 instruction and data caches.

Important registers

The instruction cycle

Measuring performance

The time a program takes on a processor is

CPU time = Instruction count × CPI × Clock cycle time = (IC × CPI) / Clock rate

• IC: the number of instructions executed (depends on the program, compiler and ISA).
• CPI: average clock cycles per instruction (depends on the hardware design and the instruction mix).
• Clock rate f = 1 / cycle time.

With an instruction mix, CPI is a weighted average: CPI = Σ (fraction of class i × cycles of class i).

MIPS (millions of instructions per second) = Clock rate / (CPI × 10⁶). MIPS is easy to quote but misleading across different instruction sets, because one instruction set may need more instructions for the same work. Execution time for the same program is the only fair comparison.

Speedup of A over B = Time(B) / Time(A), and "A is n times faster than B" means Time(B) = n × Time(A).

ic, cpi, clock = 2e9, 1.5, 2.5e9
print(f"CPU time = {ic * cpi / clock:.2f} s")

mix = [("ALU", 0.5, 1), ("load/store", 0.2, 3), ("branch", 0.3, 2)]
avg_cpi = sum(frac * cycles for _, frac, cycles in mix)
print(f"average CPI = {avg_cpi:.2f}, MIPS at 2 GHz = {2e9 / avg_cpi / 1e6:.1f}")

CPU time = 1.20 s
average CPI = 1.70, MIPS at 2 GHz = 1176.5

Amdahl's law

If an enhancement speeds up a fraction f of the execution time by a factor s, the overall speedup is

Speedup = 1 / ((1 − f) + f / s)

Even with an infinite s, the speedup can never exceed 1 / (1 − f): the part that is not improved dominates. Speeding up 80% of a program 4 times gives 1 / (0.2 + 0.2) = 2.5, and no amount of speeding up that 80% gives more than 5.

def amdahl(f, s):
    return 1 / ((1 - f) + f / s)

for f, s in [(0.8, 4), (0.8, 100), (0.6, 10), (0.4, 8)]:
    print(f"f = {f}, s = {s:3}: speedup {amdahl(f, s):.3f} (limit {1 / (1 - f):.2f})")

f = 0.8, s =   4: speedup 2.500 (limit 5.00)
f = 0.8, s = 100: speedup 4.808 (limit 5.00)
f = 0.6, s =  10: speedup 2.174 (limit 2.50)
f = 0.4, s =   8: speedup 1.538 (limit 1.67)

Practice questions