Application Representations for Multiparadigm Performance Modeling of Large-Scale Parallel Scientific Codes

Abstract

Effective performance prediction for large parallel applications on very large-scale systems requires a comprehensive modeling approach that combines analytical models, simulation models, and measurement for different application and system components. This paper presents a common parallel program representation, designed to support such a comprehensive approach, with four design goals: (1) the representation must support a wide range of modeling techniques; (2) it must be automatically computable using parallelizing compiler technology, in order to minimize the need for user intervention; (3) it must be efficient and scalable enough to model teraflop-scale applications; and (4) it should be flexible enough to capture the performance impact of changes to the application, including changes to the parallelization strategy, communication, and scheduling. The representation we present is based on a combination of static and dynamic task graphs. It exploits recent compiler advances that make it possible to use concise, symbolic static graphs and to instantiate dynamic graphs. This representation has led to the development of a compiler-supported simulation approach that can simulate regular, message-passing programs on systems or problems 10 to 100 times larger than was possible with previous state-of-the-art simulation techniques.

Get full access to this article

View all access options for this article.

References

Adve, V. , Bagrodia, R. , Browne, J. C. , Deelman, E. , Dube, A. , Houstis, E. , Rice, J. , Sakellariou, R. , Sundaram-Stukel, D. , Teller, P. , and Vernon, M. K. In press. POEMS: End-to-end performance design of large parallel adaptive computational systems . IEEE Trans. on Software Engineering.

Adve, V. , Bagrodia, R. , Deelman, E. , Phan, T. , and Sakellariou, R. 1999. Compiler-supported simulation of highly scalable parallel applications . In Proceedings of SC99: High Performance Networking and Computing.

Adve, V. , and Mellor-Crummey, J. 1998. Using integer sets for data-parallel program analysis and optimization . In Proceedings of the SIGPLAN ’98 Conference on Programming Language Design and Implementation, pp. 186-198 .

Adve, V. , and Sakellariou, R. 2000. Compiler synthesis of task graphs for a parallel system performance modeling environment . In Proceedings of the 13th International Workshop on Languages and Compilers for High Performance Computing (LCPC ’00), August.

Adve, V. , and Vernon, M. K. 1998. A deterministic model for parallel program performance evaluation. Technical Report CS-TR98-333, Computer Science Department, Rice University . Also available online: http://www-sal.cs.uiuc.edu/vadve/Papers/detmodel.ps.gz

Bagrodia, R. , Deelman, E. , Docy, S. , and Phan, T. 1999. Performance prediction of large parallel applications using parallel simulations . In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May, Atlanta, GA.

Bagrodia, R. , and Liao, W. 1994. Maisie: A language for design of efficient discrete-event simulations . IEEE Transactions on Software Engineering 20 (4): 225-238 .

Browne, J. C. , and Dube, A. 2000. Compositional development of performance models in POEMS . International Journal of High Performance Computing Applications 14 (4): 283-291 .

Browne, J. C. , Hyder, S. I. , Dongarra, J. , Moore, K. , and Newton, P. 1995. Visual programming and debugging for parallel computing . IEEE Parallel and Distributed Technology 3 (1): 75-83 .

10.

Cosnard, M. , and Loi, M. 1995. Automatic task graph generation techniques . Parallel Processing Letters 5 (4): 527-538 .

11.

Dikaiakos, M. , Rogers, A. , and Steiglitz, K. 1994. FAST: A functional algorithm simulation testbed . In International Workshop on Modelling, Analysis and Simulation of Computer and Telecommunication Systems—Mascots ’94, 142-146 . IEEE Computer Society Press.

12.

Eager, D. L. , Zahorjan, J. , and Lazowska, E. D. 1989. Speedup versus efficiency in parallel systems . IEEE Transactions on Computers C-38 (3): 408-423 .

13.

Hoisie, A. , Lubeck, O. M. , and Wasserman, H. J. 1998. Performance analysis of multidimensional wavefront algorithms with application to deterministic particle transport. Technical Report LA-UR-98-3316, Los Alamos National Laboratory, New Mexico .

14.

Newton, P. , and Browne, J. C. 1992. The CODE 2.0 graphical parallel programming language . In Proceedings of the 1992 ACM International Conference on Supercomputing, July, Washington, DC.

15.

Pai, V. S. , Ranganathan, P. , and Adve, S. V. 1997. The impact of instruction level parallelism on multiprocessor performance and simulation methodology . In Proc. Third International Conference on High Performance Computer Architecture, pp. 72-83 .

16.

Papaefstathiou, E. , Kerbyson, D. J. , Nudd, G. R. , Harper, J. S. , Perry, S. C. , and Wilcox, D. V. 1998. A performance analysis environment for life . In Proceedings of the Second ACM SIGMETRICS Symposium on Parallel and Distributed Tools, August, Welches, OR.

17.

Parashar, M. , Hariri, S. , Haupt, T. , and Fox, G. 1994. Interpreting the performance of HPF/Fortran 90D . Paper presented at Supercomputing ’94, November, Washington, DC.

18.

Reinhardt, S. K. , Hill, M. D. , Larus, J. R. , Lebeck, A. R. , Lewis, J. C. , and Wood, D. A. 1993. The Wisconsin wind tunnel: Virtual prototyping of parallel computers . In Proc. 1993 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pp. 48-60 .

19.

Rogers, A. , and Pingali, K. 1989. Process decomposition through locality of reference . In Proceedings of the SIGPLAN ’89 Conference on Programming Language Design and Implementation, June, Portland, OR.

20.

Rosenblum, M. , Herrod, S. , Witchel, E. , and Gupta, A. 1995. Complete computer system simulation: The SimOS approach. In IEEE Parallel and Distributed Technology, pp. 34-43.

21.

Sundaram-Stukel, D. , and Vernon, M. K. 1999. Predictive analysis of a wavefront application using LogGP . In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, May, Atlanta, GA.

22.

Yang, T. , and Gerasoulis, A. 1992. PYRROS: Static task scheduling and code generation for message passing multiprocessors . In Proceedings of the ACM International Conference on Supercomputing, July, Washington, DC.