SME
Computer Organization & Architecture · Problem type
Amdahl’s law
Use this for “80% of a program’s time is made 4 times faster. What is the overall speedup, and what is its limit?”
This is an example. Type your own values to start a new problem.
S
=
1
(1
−
)
+
÷
Sₘₐₓ
=
1
1
−
Formulas
S
=
1
(1 −
f
) +
f
÷
s
2.5
=
1
(1 − 0.8) + 0.8 ÷ 4
Sₘₐₓ
=
1
1 −
f
5
=
1
1 − 0.8
Assumptions
•
Fraction f of the old run time can be sped up; the rest, 1 − f, runs as before.
•
The improved part runs s times faster, so it takes f ÷ s of the old time.
•
However fast the improved part gets, the time never drops below 1 − f.
Step-by-step
WE KNOW
f = 0.8, s = 4
FIND
overall speedup (S), largest speedup (Sₘₐₓ)
Step 1 · Find overall speedup (S)
Use S = 1 ÷ ((1 − f) + f ÷ s)
The
new
time
is
the
untouched
part
plus
the
improved
part
s
times
faster;
speedup
is
old
time
over
new.
S
=
1
(1 − 0.8) + 0.8 ÷ 4
S
=
1
1 − 0.8 + 0.2
S
=
1
0.4
S
=
2.5
Step 2 · Find largest speedup (Sₘₐₓ)
Use Sₘₐₓ = 1 ÷ (1 − f)
With
the
improved
part
taking
no
time
at
all,
only
1
−
f
of
the
old
time
is
left.
Sₘₐₓ
=
1
1 − 0.8
Sₘₐₓ
=
1
0.2
Sₘₐₓ = 5
Check
Put the numbers back in. Both sides should match.
2.5
=
1
(1 − 0.8) + 0.8 ÷ 4
✓
5
=
1
1 − 0.8
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.