MPI-I-96-1-032
Runtime prediction of real programs on real machines
Finkler, Ulrich and Mehlhorn, Kurt
December 1996, 10 pages.
.
Status: available - back from printing
Algorithms are more and more made available as part of libraries or tool
kits. For a user of such a library statements of asymptotic
running times are almost meaningless as he has no way to estimate the
constants involved. To choose the right algorithm for the targeted problem
size and the available hardware, knowledge about these constants is
important.
Methods to determine the constants based on regression analysis or operation
counting are not practicable in the general case due to inaccuracy and costs
respectively.
We present a new general method to determine the implementation and hardware
specific running time constants for combinatorial
algorithms. This method requires no changes of the implementation
of the investigated algorithm and is
applicable to a wide range of
of programming languages. Only some additional code is necessary.
The determined constants
are correct within a constant factor which depends only on the
hardware platform. As an example the constants of an implementation
of a hierarchy of algorithms and data structures are determined.
The hierarchy consists of an algorithm for the
maximum weighted bipartite matching problem (MWBM), Dijkstra's algorithm,
a Fibonacci heap and a graph representation based on adjacency lists.
ion
frequencies are at most 50 \% on the tested hardware platforms.
-
- Attachement: MPI-I-96-1-032.ps (179 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1996-1-032
BibTeX
@TECHREPORT{FinklerMehlhorn96,
AUTHOR = {Finkler, Ulrich and Mehlhorn, Kurt},
TITLE = {Runtime prediction of real programs on real machines},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-96-1-032},
MONTH = {December},
YEAR = {1996},
ISSN = {0946-011X},
}