Understanding performance stairs: elucidating heuristics

Bryan Marker, Don S. Batory, Robert A. van de Geijn

Abstract

How do experts navigate the huge space of implementations for a given specification to find an efficient choice with minimal searching? Answer: They use "heuristics" -- rules of thumb that are more street wisdom than scientific fact. We provide a scientific justification for Dense Linear Algebra (DLA) heuristics by showing that only a few decisions (out of many possible) are critical to performance; once these decisions are made, the die is cast and only relatively minor performance improvements are possible. The (implementation x performance) space of DLA is stair-stepped. Each stair is a set of implementations with very similar performance and (surprisingly) share key design decision(s). High-performance stairs align with heuristics that prescribe certain decisions in a particular context. Stairs also tell us how to tailor the search engine of a DLA code generator to reduce the time it needs to find implementations that are as good or better than those crafted by experts.

BibTeX

@inproceedings{Marker-al:ASE14,
  author    = {Bryan Marker and
               Don S. Batory and
               Robert A. van de Geijn},
  title     = {Understanding performance stairs: elucidating heuristics},
  booktitle = {ASE},
  pages     = {301--312},
  publisher = {{ACM}},
  year      = {2014},
}

Understanding performance stairs: elucidating heuristics

Abstract

Related papers