Automated Scalability Prediction via Data Parallel Compiler Support
Resumo
Despite the performance potential of multicomputers, several factors have limited their widespread adoption. Of these, performance variability is among the most significant. Execution of some programs may yield only a small fraction of peak system performance, whereas others approach the system’s theoretical performance peak. Moreover, the observed performance may change substantially as application program parameters vary. Data parallel languages, which facilitate the programming of multicomputers, increase the semantic distance between the program’s source code and its observable performance, thus aggravating the performance problem. In this paper, we propose a new methodology to automatically predict the performance scalability of data parallel applications on multicomputers. Our technique represents the execution time of a program as a symbolic expression that is a function of the number of processors (P), problem size (N), and other system-dependent parameters. This methodology is based on information collected at compile time. By extending an existing data parallel compiler (Fortran D95), we derive, during compilation, a symbolic model that represents the cost of each high-level program section and, inductively, of the complete program. These symbolic expressions may be simplified externally with current symbolic tools. Predicting performance of the program for a given pait (P,N) requires simply the evaluation of its corresponding cost expression. We validate our implementation by predicting scalability of a variety of loop nests, with distinct computation and communication patterns.
Referências
BALASUNDARAM, V., FOX, G., KENNEDY, K., AND KREMER, U. A static performance estimator in the Fortran D programming system. ln Languages, Compilers and Run-Time Environments for Distributed Memory Machines. North-Holland, Amsterdam, The Netherlands, 1992.
BANERJEE, U. Loop Transformations for Restructuring Compilers: The Foundations. Kluwer Academic Publishers, Norwell, Massachusetts, 1993.
BIXBY, R., KENNEDY K., AND KREMER, U. Automatic data layout using 0-1 integer programming. Tech. Rep. CRPC-TR93349-S, CRPC/Rice University, 1993.
CLEMENT, M. J., AND QUINN, M. J. Analytical performance prediction on multicomputers. ln Proceedings of Supercomputing'93 (Portland, November 1993), pp. 886-894.
CLEMENT, M. J., AND QUINN, M. J. Symbolic performance prediction of scalable parallel programs. In Proceedings of the 9th International Parallel Processing Symposium (April 1995).
FAHRINGER, T. Automatic Performance Prediction of Parallel Programs. Kluwer Academic Publishers, Norwell, Massachusetts, 1996.
HATCHER, P. J., AND QUINN, M. J. Data Parallel Programming on MIMD Computers. The MIT Press, Cambridge, Massachusetts, 1991.
LEVINE, D., CALLAHAN, D., AND DONGARRA, J. Test Suite for Vectorizing Compilers. 1991.
MELLOR-CRUMMEY, J., AND ADVE, V. Fortran D95 Compiler Overview. Available from http://www.cs.rice.edu/mpal/SC95, 1996.
MENDES, C. L. Performance Scalability Prediction on Multicomputers. PhD thesis, University of Illinois at Urbana-Champaign, May 1997.
VAN GEMUND, A. J. C. Compile-time performance prediction of parallel systems. In Proceedings of the 8th International Conference on Modeling Techniques and Tools for Computer Performance Evaluation (Heidelberg, September 1995), pp. 299-313.
