Effective MIPS Under Exclusive Program Execution: Amdahl’s Law

Let $a$ be the fraction of a program’s code that can be executed simultaneously by $n$ processors, and let $1-a$ be the fraction that must run sequentially on a single processor. If each processor runs at $x$ MIPS, then the effective system throughput (in MIPS) is governed by Amdahl’s Law: overall speedup is limited by the sequential fraction.

We model exclusive execution as follows:

• Parallel fraction $a$ is sped up by using $n$ processors.
• Sequential fraction $1-a$ has no parallel benefit and runs at the single-processor rate.

keyword

keyword

keyword

keyword

(a) Effective MIPS in terms of $n$, $\\alpha$, and $x$

Let $\\alpha$ denote the parallelizable fraction (your problem statement uses $\alpha$; it plays the role of $a$). Then the effective MIPS for exclusive execution is:

$\\boxed{\\text{Effective MIPS}(n)=\\frac{x}{(1-\\alpha)+\\frac{\\alpha}{n}}}$

This follows directly from Amdahl’s Law speedup $S(n)=\\dfrac{1}{(1-\\alpha)+\\frac{\\alpha}{n}}$ and multiplying by the per-processor rate $x$ when processors are otherwise identical. 2

(b) Find the $\\alpha$ that yields 40 MIPS for $n=16$, $x=4$

We need $\\text{Effective MIPS}(16)=40$:

$40=\\frac{4}{(1-\\alpha)+\\frac{\\alpha}{16}}$

Divide both sides by 4:

$10=\\frac{1}{(1-\\alpha)+\\frac{\\alpha}{16}}$

Invert:

$(1-\\alpha)+\\frac{\\alpha}{16}=\\frac{1}{10}=0.1$

Solve:

$1-\\alpha+\\frac{\\alpha}{16}=0.1$ $1-\\alpha\\left(1-\\frac{1}{16}\\right)=0.1$ $\\alpha\\left(1-\\frac{1}{16}\\right)=0.9$ $\\alpha\\left(\\frac{15}{16}\\right)=0.9$ $\\alpha=0.9\\cdot\\frac{16}{15}=0.96$

So the required parallel fraction is:

$\\boxed{\\alpha=0.96}$