Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Runtime prediction of real programs on real machines

Finkler, Ulrich and Mehlhorn, Kurt

MPI-I-96-1-032. December 1996, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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

Methods to determine the constants based on regression analysis or operation
counting are not practicable in the general case due to inaccuracy and costs
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.
frequencies are at most 50 \% on the tested hardware platforms.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-96-1-032.ps179 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},