Performance: CPI, MIPS and Amdahl's law

Why it exists

Faster hardware is only useful if it reduces the time a program takes. This page gives the standard equation for that time, shows how the three factors (how many instructions, how many cycles each, how long a cycle) are traded against each other by the instruction set, the organization and the technology, and states the law that limits what any single improvement can give: Amdahl's law. GATE uses it constantly, in the form "this much of the time is sped up by this factor, what is the overall speedup?", and in CPI, MIPS and execution-time comparisons.

Prerequisites

You need the idea of cycles per instruction, introduced with pipelining and used in pipeline performance.

Precise definitions

CPU performance equation.

$\text{CPU time} = \text{instruction count} \times \text{CPI} \times \text{clock period} = \frac{\text{IC} \times \text{CPI}}{\text{clock rate}}.$

• Instruction count (IC) depends on the program, the compiler and the instruction set.
• CPI (cycles per instruction) depends on the organization (pipelining, caches) and the instruction mix.
• Clock period depends on the technology and the organization (the slowest stage).

An improvement in one factor can worsen another: a richer instruction set lowers IC but may raise CPI or lengthen the clock period.

Average CPI from an instruction mix. With classes $i$ of frequency $f_i$ (fractions of the instructions) and cycles $\text{CPI}_i$,

$\text{CPI} = \sum_i f_i\,\text{CPI}_i.$

The cycles for the program are $\text{IC} \times \text{CPI}$; with cache misses or pipeline stalls add the stall cycles per instruction to the CPI (cache performance, pipeline performance).

MIPS (million instructions per second).

$\text{MIPS} = \frac{\text{IC}}{\text{time} \times 10^6} = \frac{\text{clock rate}}{\text{CPI} \times 10^6}.$

MIPS depends on the instruction set (what an instruction does), so it cannot compare machines with different instruction sets or compilers, and it can even rank a machine as faster when it is slower. MFLOPS counts floating-point operations per second and has similar problems. The only reliable comparison is execution time of real programs.

Speedup and relative performance. Performance is the reciprocal of execution time. "A is $n$ times faster than B" means $\text{time}_B/\text{time}_A = n$, and the speedup from a change is $\text{time}_{old}/\text{time}_{new}$.

Amdahl's law. If an enhancement speeds up a part of the program that takes a fraction $f$ of the original execution time by a factor $s$, the new time is $(1 - f) + f/s$ (relative to the old one), so

$\text{overall speedup} = \frac{1}{(1 - f) + f/s}.$

The part that is not enhanced, $1 - f$, is unchanged. Even if $s \to \infty$ the speedup cannot exceed

$\text{limit} = \frac{1}{1 - f}.$

It shows diminishing returns: making the same part ever faster brings less and less, and the best use of effort is the part with the largest remaining share of the time. For several enhancements on separate parts with fractions $f_1, f_2, \ldots$ and speedups $s_1, s_2, \ldots$,

$\text{speedup} = \frac{1}{(1 - \sum f_j) + \sum f_j / s_j}.$

For a program with a parallel fraction $f$ run on $p$ processors, $s = p$ gives the speedup $1/((1 - f) + f/p)$ and the limit $1/(1 - f)$ however many processors are used.

Required enhancement. To reach an overall speedup $S$ by enhancing a fraction $f$ the part must be sped up by

$s = \frac{f}{1/S - (1 - f)},$

which is possible only if $S < 1/(1 - f)$.

How it works

The explorer applies the law. Set the fraction of the original time that is enhanced and the speedup of that part. The bar shows the new execution time (the grey unchanged part never shrinks; only the blue part does), and the curve shows how the overall speedup flattens against its limit as the enhancement gets larger. Try 50% with the enhancement at 100x and see how little is gained; then try 95%.

Worked examples

#include <stdio.h>
 
int main(void) {
    /* instruction mix and CPI per class */
    const char *name[4] = {"ALU", "load", "store", "branch"};
    double freq[4] = {0.50, 0.20, 0.10, 0.20}, cpi[4] = {1, 2, 2, 3};
    double avg = 0;
    for (int i = 0; i < 4; i++) {
        avg += freq[i] * cpi[i];
        printf("%-6s %.0f%% x CPI %.0f = %.2f\n", name[i], 100 * freq[i], cpi[i], freq[i] * cpi[i]);
    }
    double clock = 2e9, ic = 1e9;
    printf("average CPI = %.2f\n", avg);
    printf("CPU time for %.0e instructions at %.0f GHz = %.3f s\n", ic, clock / 1e9, ic * avg / clock);
    printf("MIPS = %.1f\n", clock / (avg * 1e6));
    return 0;
}

ALU    50% x CPI 1 = 0.50
load   20% x CPI 2 = 0.40
store  10% x CPI 2 = 0.20
branch 20% x CPI 3 = 0.60
average CPI = 1.70
CPU time for 1e+09 instructions at 2 GHz = 0.850 s
MIPS = 1176.5

#include <stdio.h>
 
int main(void) {
    /* the same program on two machines at 1 GHz: M1 needs 2e9 simple instructions at CPI 1, M2 needs 1e9 complex ones at CPI 1.5 */
    double clock = 1e9;
    double ic1 = 2e9, cpi1 = 1.0, ic2 = 1e9, cpi2 = 1.5;
    printf("M1: MIPS %.0f, time %.2f s\n", clock / (cpi1 * 1e6), ic1 * cpi1 / clock);
    printf("M2: MIPS %.0f, time %.2f s\n", clock / (cpi2 * 1e6), ic2 * cpi2 / clock);
    return 0;
}

M1: MIPS 1000, time 2.00 s
M2: MIPS 667, time 1.50 s

#include <stdio.h>
 
static double amdahl(double f, double s) { return 1 / (1 - f + f / s); }
 
int main(void) {
    printf("f = 0.8, s = 4: speedup %.3f, limit %.2f\n", amdahl(0.8, 4), 1 / (1 - 0.8));
    /* two enhancements on disjoint parts: 40% sped up 2x and 30% sped up 3x, 30% unchanged */
    printf("two parts: speedup %.3f\n", 1 / (0.3 + 0.4 / 2 + 0.3 / 3));
    /* 90%% parallelisable on 10 processors */
    printf("90%% parallel on 10 processors: %.2f (limit %.0f)\n", amdahl(0.9, 10), 1 / (1 - 0.9));
    /* what enhancement of 80% of the time gives an overall speedup of 3? */
    double f = 0.8, target = 3, s = f / (1 / target - (1 - f));
    printf("overall speedup %.0f needs the 80%% part %.2f times faster (check: %.3f)\n", target, s, amdahl(f, s));
    /* the share of the NEW time that is spent in the enhanced part */
    double new_time = 1 - 0.8 + 0.8 / 4;
    printf("after the f = 0.8, s = 4 change the enhanced part is %.0f%% of the new time\n", 100 * (0.8 / 4) / new_time);
    return 0;
}

f = 0.8, s = 4: speedup 2.500, limit 5.00
two parts: speedup 1.667
90% parallel on 10 processors: 5.26 (limit 10)
overall speedup 3 needs the 80% part 6.00 times faster (check: 3.000)
after the f = 0.8, s = 4 change the enhanced part is 50% of the new time

Cheat box

Traps and GATE patterns

Connections

The CPI used here is the one the pipeline makes close to 1 and hazards push up; the memory stall cycles per instruction of cache performance are added the same way. The trade between IC and CPI is the design question of ISA design: a richer instruction lowers IC and tends to raise CPI. The number of cycles each instruction takes comes from the instruction cycle.

PYQs

The baseline execution time of a program on a 2GHz
single core machine is 100 nanoseconds (ns). The
code corresponding to 90% of the execution time can
be fully parallelized. The overhead for using an
additional core is 10 ns when running on a multicore
system. Assume that all cores in the multicore system
run their share of the parallelized code for an equal
amount of time.
The number of cores that minimize the execution time
of the program is
.

An application executes 6.4 × 108 number of
instructions in 6.3 seconds. There are four types of
instructions, the details of which are given in the
table. The duration of a clock cycle in nanoseconds
is
(rounded off to one decimal place).

Instruction
type
Clock cycles
required per
instruction
(CPI)
Number of
instruction
executed
Branch
2
2.25 × 108
Load
5
1.20 × 108
Store
4
1.65 × 108
Arithmetic
3
1.30 × 108
3 3
Computer Organization and Architecture

Self-check

Revision card

References