Introduction to Algorithms, Third Edition

A chess lesson
We close this section with a true story that occurred during the development of
the world-class multithreaded chess-playing program
?
Socrates [80], although the
timings below have been simplified for exposition. The program was prototyped
on a
32
-processor computer but was ultimately to run on a supercomputer with
512
processors. At one point, the developers incorporated an optimization into the pro-
gram that reduced its running time on an important benchmark on the
32
-processor
machine from
T
32
D
65
seconds to
T
0
32
D
40
seconds. Yet, the developers used
the work and span performance measures to conclude that the optimized version,
which was faster on
32
processors, would actually be slower than the original ver-
sion on
512
processsors. As a result, they abandoned the “optimization.”
Here is their analysis. The original version of the program had work
T
1
D
2048
seconds and span
T
1
D
1
second. If we treat inequality (27.4) as an equation,
T
P
D
T
1
=P
C
T
1
, and use it as an approximation to the running time on
P
pro-
cessors, we see that indeed
T
32
D
2048=32
C
1
D
65
. With the optimization, the
work became
T
0
1
D
1024
seconds and the span became
T
0
1
D
8
seconds. Again
using our approximation, we get
T
0
32
D
1024=32
C
8
D
40
.
The relative speeds of the two versions switch when we calculate the running
times on
512
processors, however. In particular, we have
T
512
D
2048=512
C
1
D
5

---

27.1
The basics of dynamic multithreading
791
seconds, and
T
0
512
D
1024=512
C
8
D
10
seconds. The optimization that sped up
the program on
32
processors would have made the program twice as slow on
512
processors! The optimized version’s span of
8
, which was not the dominant term in
the running time on
32
processors, became the dominant term on
512
processors,
nullifying the advantage from using more processors.
The moral of the story is that work and span can provide a better means of
extrapolating performance than can measured running times.