Space-limited procedures: a methodology for portable high-performance

This paper presents the generic program approach to achieving portable high-performance. This approach has three phases. In the first, a generic program, defining a family of semantically-equivalent program variants, is written. In the second, the generic program as specialized to the variant that performs best on an abstract model of the target computer. In the third, this variant is translated to run on the target computer. The Parallel Memory Hierarchy (PMH) generic model is used to define the abstract models of target computers. Using this approach, a spectrum of solutions is possible. At one end of the spectrum, a simple generic program can be written, with roughly the same difficulty as writing a sequential program, that can be tuned automatically to achieve reasonably good performance on a wide variety of computers. This solution can be refined to give better performance. At the labor-intensive end of the spectrum, an application can be tuned so that it achieves the best possible performance on each of a collection of computers