Performance evaluation and improvement of parallel applications on high performance architectures.

Abstract

An effective methodology of performance evaluation and improvement enables application developers to quickly and efficiently tune their applications to achieve good performance. One efficient approach to improving performance for scientific applications is to bound the best achievable performance that a machine could deliver on a particular application code and then try to approach this bound in delivered performance. A useful abstraction is to approximate components of the application, architecture, compiler as independent contributors to the total application runtime. A hierarchy of such bounds equations can be constructed by successively taking into account actual rather than idealized additional components of machine runtime (and hence performance) and creating a new bounds equation for each such increasingly detailed abstraction. The MACS12*B bounds hierarchy that we develop models most of the common factors contributing to run time including limits posed by peak performance, essential operations in the high level code, nonessential instructions inserted by the compiler and scheduler, misses in the first level cache, misses in the second level cache which generate communication events, congestion effects leading to long miss latencies, and load imbalance effects. Given this hierarchy, it is possible to focus application performance improvement efforts on the causes of the largest gaps between successive performance bounds in the hierarchy. We develop a methodology of performance improvement in which we analyze performance, target performance bottleneck(s), select a standard heuristic applicable to the targeted bottleneck, restructure or change the high-level application, and iterate until acceptable performance has been achieved. A case study in which two of the NAS parallel benchmarks are tuned for the Kendall Square Research KSR parallel computer illustrates the power of this approach. These applications are analyzed with the MACS12*B bounds hierarchy and their performance bottlenecks are identified. The original applications are progressively restructured and/or changed using the iterative methodology. The performance of the resulting codes is found to compare favorably to the KSR-supplied hand-tuned versions.