Publication Details
Title: On the Definition of Speedup
Author: W. Ertel
Group: ICSI Technical Reports
Date: November 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-069.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-069
Bibliographic Reference:
W. Ertel. On the Definition of Speedup. ICSI Technical Report TR-93-069, November 1993
Author: W. Ertel
Group: ICSI Technical Reports
Date: November 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-069.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-069
Bibliographic Reference:
W. Ertel. On the Definition of Speedup. ICSI Technical Report TR-93-069, November 1993