The Performance Equation

The performance equation says that a program's run time is the number of instructions it executes, times the average number of clock cycles each instruction takes, times the length of one clock cycle. It is the most useful formula in computer architecture, because it turns the vague question "how do I make this faster?" into three separate questions, each answered by different people. This article explains each factor, shows how the compiler, the instruction set, the microarchitecture and the chip technology each move one of them, and uses a small array program to show why looking at only one factor gives the wrong answer.

13 min read | Beginner

What You'll Learn

• Write the performance equation and explain each of its three factors
• Compute run time, CPI and speedup from instruction and cycle counts
• Say which design decisions change which factor
• Avoid comparisons based on clock frequency, CPI or MIPS alone

What "Faster" Means

When a person says one computer is faster than another, they can mean two different things. Response time, also called execution time or latency, is how long one task takes from start to finish. Throughput is how much work is finished per unit of time, such as requests served per second. A faster processor usually improves both, but not always: adding a second processor core to a server lets it finish twice as many requests per second, while each single request takes just as long.

This article is about response time for one program on one processor, because that is the base on which everything else is built. The rule for this kind of performance is simple: the only reliable measure is the time the real program takes. Everything else, clock frequency included, is at best a part of the answer.

When we compare two designs, we use the word speedup: the old run time divided by the new run time. A speedup of 1.25 means the new design does the job 1.25 times as fast, so it takes 1 / 1.25 = 0.8 of the old time, 20 percent less. Notice that "25 percent faster" and "20 percent less time" describe the same change. Mixing them up is a common source of confusion.

The Equation

Run time can be split into three factors:

run time = (instructions / program) x (cycles / instruction) x (seconds / cycle)
         = instruction count x CPI x clock period

The units cancel like fractions: instructions per program, times cycles per instruction, times seconds per cycle, leaves seconds per program. Each factor has its own meaning:

• The instruction count is the number of instructions the processor actually executes while the program runs, not the number stored in the program file. A loop of four instructions that runs a thousand times counts as 4,000, as How a Program Runs explains.
• CPI, cycles per instruction, is the average number of clock cycles each executed instruction takes. Its inverse, IPC, instructions per cycle, says the same thing the other way up, and is the usual measure for processors that finish more than one instruction per cycle.
• The clock period is the length of one cycle, which is 1 / frequency. Clocks, Cycles and Time explains what sets it.

A worked example with simple numbers: a program executes 1 million instructions at a CPI of 1.5 on a 100 MHz processor. The clock period is 10 ns, so the run time is 1,000,000 x 1.5 x 10 ns = 15,000,000 ns, or 15 ms. These numbers are assumptions for this example. Doubling the clock, or reducing the CPI to 0.75, or removing half the instructions would each cut the time to 7.5 ms. To the equation they are all the same; in practice they cost very different amounts of work.

What Moves Each Factor

The value of the equation is that it shows who controls what:

A better algorithm can reduce the instruction count by a factor of a thousand, which no hardware can match. A compiler changes which instructions run and in what order. An instruction set with a multiply instruction replaces a library routine of dozens of instructions with one. The microarchitecture, meaning how the processor is organized inside, decides how many cycles instructions need on average, and also how much logic must fit in one cycle. The manufacturing process and the layout decide how fast each gate switches.

The factors are not independent. That is what makes processor design interesting. Splitting the work into more pipeline stages shortens the clock period but raises the CPI, because more instructions are thrown away after a wrong branch. Adding a complicated instruction lowers the instruction count but may lengthen the clock period for everything else. Almost every design decision moves two factors in opposite directions, and only the product matters.

One Program, Two Builds

Here is a real case. A small program fills an array of 1,024 numbers and adds them up. It was compiled twice from the same C file, with optimization (-O2) and without it (-O0), and both builds were run on a simple five-stage processor at 100 MHz:

The clock period is the same in both rows, because the hardware did not change. The unoptimized build executes about four times as many instructions, because it keeps every variable in memory, as Registers and the Register File shows. So far that is what you would expect.

Now look at CPI. The unoptimized build has the better CPI, about 1.3 against 1.5, and yet it takes 3.5 times as long. Its extra instructions are mostly simple loads and stores that rarely upset the pipeline, while the tight optimized loop takes a branch every four instructions and loses cycles each time. This is the classic trap: a lower CPI can belong to a slower program, because CPI says nothing about how many instructions were needed. A processor or compiler change must always be judged by the product of the factors.

Where the Cycles Go: The CPI Stack

A CPI above 1 on a processor that can finish one instruction per cycle means cycles are being lost somewhere. Engineers split the CPI into its causes. If a program spends its time like this, the total CPI is the base of 1 plus each kind of lost cycle per instruction. The result is called a CPI stack:

CPI = 1.0                               every instruction takes one cycle
    + branch flushes per instruction    wrong instructions thrown away
    + load-use stalls per instruction   waiting for a value from memory
    + memory waits per instruction      waiting for a slow memory

Six small programs measured this way on a simple five-stage processor had a CPI between about 1.26 and 1.6. For most of them, nearly all the lost cycles were branch flushes: about a third of all cycles in the array program and in a linked-list program, and about a fifth in a checksum program. A bubble sort also lost about a tenth of its cycles to load-use stalls. The processor's memory was very fast in this test, so nothing was lost waiting for it. On a real system with slower memory, the stack would look very different.

The stack tells an architect where to work. If branch flushes make up a third of the run, then better branch handling is worth studying. If they make up 2 percent, the same idea is a waste of time. PPA Trade-offs and Amdahl's Law turns this into a rule for how much a change can possibly gain.

Why Single Numbers Mislead

The equation also explains why the popular single numbers for a processor do not tell you how fast it is.

Clock Frequency

Frequency is only one factor out of three. In the early 2000s, one well-known desktop processor family reached very high frequencies by using an unusually long pipeline, and it was often beaten by competitors at much lower frequencies that finished more instructions per cycle. Two processors at the same frequency can differ in speed by a factor of several.

CPI or IPC Alone

The array program above shows it: the slower build had the better CPI. CPI comparisons only make sense for the same instructions. Comparing the CPI of two processors with different instruction sets means little, because their instructions do different amounts of work.

MIPS

MIPS here means millions of instructions per second (not the processor family of the same name). It is frequency divided by CPI, so it ignores the instruction count entirely. The unoptimized build above reaches a higher MIPS rating than the optimized one, because it runs simple instructions with a lower CPI, even though it takes 3.5 times as long to do the same job. A rating that rewards doing the job badly is not a good rating.

Peak Numbers

Datasheets often state the best case: the highest frequency reached for a moment before the chip gets too hot, or the highest IPC on the most favorable code. A real program running for minutes on a real thermal design sees something lower.

Using the Equation in Design Work

Architects use the equation to estimate a change before building anything. Suppose a five-stage processor loses 2 cycles on each taken branch, and taken branches are 15 percent of executed instructions. Branches then add 0.15 x 2 = 0.30 to the CPI. A cheap branch predictor that avoids three quarters of those lost cycles removes 0.225 from the CPI. If the CPI was 1.5, it becomes 1.275, a speedup of 1.5 / 1.275 = 1.18, as long as the clock period stays the same. These numbers are assumptions for this example, but the method is exactly what is done in practice, and it takes one minute with a calculator.

The same calculation also shows when a change is not worth making. If the predictor's logic made the clock period 20 percent longer, the time per instruction would be 1.275 x 1.2 = 1.53 compared with the original 1.5 and the design would be slower overall, despite the better CPI.

Estimates like this are only as good as the measurements behind them, which is why choosing the right programs to measure matters so much. Workloads and Benchmarks covers that.

Common Mistakes