We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A new formula for speedup and its characterization.
- Authors
Aczél, János; Ertel, Wolfgang
- Abstract
We address the task of measuring the relative speed (speedup) of two systems A and B for solving the same problem. For example, B may be a parallel algorithm, parametrized by the number of processors used, whose running time has to be related to a serial standard algorithm A. If A and/or B are randomized or if we are interested in their performance on a (discrete) probability distribution of problem instances, the running times are described by random variables T and T . The speedup of B over A is usually defined as E(T )/E(T ) where E denotes the expected value. In many cases this definition is not appropriate for the user of A or B, because the summation in E(T ) and E(T ) hides information about the speedup of individual runs. We propose an alternative speedup definition of the form (T /T ) and present a set of intuitive functional equations, which any such function (T /T ) should fulfill. Finally, we prove that the weighted geometric mean is the only solution of these equations.
- Subjects
ALGORITHMS; PROBABILITY measures; RANDOM variables; GEOMETRIC measure theory; FUNCTIONAL equations
- Publication
Acta Informatica, 1997, Vol 34, Issue 8, p637
- ISSN
0001-5903
- Publication type
Article