Verifying Self-consistent MPI Performance Guidelines

The Message-Passing Interface (MPI) is the paradigmatic, de facto standard for parallel application development in both High- and Medium Performance Scientific Computing areas. MPI implementations often provide high system utilization for many operations, and support application portability. On the other hand, MPI implementations often suffer from performance inconsistencies, such as different performance characteristics for apparently similar MPI functions, unintuitive performance jumps for different problem sizes caused by less than optimal algorithm and protocol choices, and many similar effects; this can harmfully influence the performance portability of MPI applications. In particular, performance inconsistencies often lead application programmers to look for work- arounds, that can be detrimental to performance for other MPI implementations and systems. The project on "Verifying Self-consistent MPI performance guidelines" will contribute significantly to indentify such problems, and per implication to improve the quality of MPI library implementations. Through the development of accurate, robust, fast, and customizable benchmarking procedures, coupled with automated data- mining guided by socalled self-consistent performance guidelines, the performance consistency of any given MPI implementation can be automatically validated. The procedures and tools will help to make application programmers and MPI implementers aware of MPI functionality that in given libraries may cause performance and/or performance portability problems. The aim of the project is to build a high-quality MPI benchmark together with an exhaustive set of self-consistent MPI performance guidelines with the ambitious goal of finding acceptance for this way of benchmarking and validation for performance portability in the MPI and High-Performance communities. The technical aspects of the project are: providing statistically solid foundations for MPI benchmarking, engineering an accurate, fast, exible and customizable MPI benchmark, developing data mining techniques for quickly and automatically identifying self-consistent performance guideline violations, and defining an in principle complete set of performance guidelines for the MPI standard. In addition to the technical challenges, the project aims to consolidate the technical recognition in the MPI community for the TU Wien, and will contribute to solidifying the MPI knowledge in the TU Wien group for parallel computing. Possible contributions to improving aspects of MPI performance for given MPI functions, collective operations in particular, by improved algorithms and engineering should likewise be seen as a part of the project. The project is based on community recognized research over the last years, and will extend this promising direction.

Parallel computers, in particular large-scale High-Performance systems are programmed using convenient programming languages or, as is more often the case, interfaces extending sequential programming languages with operations and algorithms for expressing and exploiting parallelism. Such interfaces should support the algorithmic thinking of the application programmer and at the same time allow efficient utilization of the parallel computer, which may be a large and expensive system. If the interface is not efficient in these two respects, resources are wasted in two ways: a) time, if the parallel resources of the system are not used efficiently and leading to the expected performance promised by the system, and b) effort on behalf of the application programmer trying to work around an inefficient interface. The project on Verifying Self-consistent MPI Performance Guidelines explored an idea to address these two sources of waste and presented solutions for the specific and widely used High-Performance Computing Message-Passing Interface (MPI). The idea is to formulate expectations on how certain operations should behave in comparison to certain other operations in a manner that can be validated by benchmarking the operations on concrete systems. Expectations typically state that more specific operations should perform no worse than the same operations expressed by more general means. Such expectations are thus guidelines on how good implementations of the MPI interface ought to behave, formulated by relating different aspects of the interface to each other. Fulfilled expectations guarantee that an operation gives a) consistent performance and b) guarantees that optimizations of this functionality on behalf of the application programmer will not be needed. Characterizing the performance of operations offered by the MPI interface requires accurate and reproducible benchmarking coupled with statistical procedures for deciding whether one operation (on one system) is better than some other operation that implements the same functionality (possibly on another system). The project contributed extensively to the surprisingly difficult problem of benchmarking MPI functionality, and lead to extensive work on synchronizing individual clocks in large, distributed-memory systems. Using these new procedures with natural sets of performance guidelines for the so-called collective operations, different MPI interface implementations were studied on different systems, and many severe violations documented. Performance guidelines immediately suggest an obvious way of improving the situation, namely by replacing the operation in the range of violation by the measured better operation. This replacement can be performed automatically and this way of the quality of MPI implementations was also pursued. MPI is a rich interface with strong interrelations between orthogonal parts of the interface. This can be exploited to formulate performance guidelines that go beyond simple expectations on similar collective operations. The project contributed extensively to formulating, and investigating the adherence to new performance guidelines for structured data communication using MPI user-defined datatypes, and for sparse, collective communication with neighborhood collective operations. Also for the algorithmically difficult irregular collective operations, new performance guidelines were formulated and investigated. In these new areas, algorithmic problems were studied and new, better algorithms in many cases proposed, implemented, and shown to be able to improve performance and guideline adherence. The results of the projects and the further research stimulated by the project will have a long- term impact towards improving the quality of implementations of the MPI standard.