On the Definition of Speedup

TitleOn the Definition of Speedup
Publication TypeTechnical Report
Year of Publication1993
AuthorsErtel, W.
Other Numbers857

We propose an alternative definition for the speedup of parallel algorithms. Let A be a sequential algorithm and B a parallel algorithm for solving the same problem. If A and/or B are randomized or if we are interested in their performance on a probability distribution of problem instances, the running times are described by random variables T^A and T^B. The speedup is usually defined as E[T^A]/E[T^B] where E is the arithmetic mean. This notion of speedup delivers just a number, i.e. much information about the distribution is lost. For example, there is no variance of the speedup. To define a measure for possible fluctuations of the speedup, a new notion of speedup is required. The basic idea is to define speedup as M(T^A/ T^B) where the functional form of M has to be determined. Also, we argue that in many cases M(T^A/T^B) is more informative than E[T^A]/E[T^B] for a typical user of A and B. We present a set of intuitive axioms that any speedup function M(T^A/T^B) must fulfill and prove that the geometric mean is the only solution. As a result, we now have a uniquely defined speedup function that will allow the user of an improved system to talk about the average performance improvement as well as about its possible variations.

Bibliographic Notes

ICSI Technical Report TR-93-069

Abbreviated Authors

W. Ertel

ICSI Publication Type

Technical Report