Automated scalability analysis of message-passing parallel programs

Scalability analysis, which characterizes large-scale performance, is indispensable for parallel-program performance debugging. To assist developers in this usually difficult process, we've developed a methodology and a toolkit that provide automatic, fast and accurate scalability analysis for a class of deterministic message-passing scientific applications. Modeling Kernel, our scalability analysis toolkit, generates a model based on a program's parse tree, which represents the program's syntactic structure. We have successfully demonstrated our approach by automatically characterizing the scalability of several scientific applications that run on Intel's iPSC/860 and Paragon supercomputers. To characterize large-scale performance, this scalability analysis toolkit constructs augmented parse trees (APTs). APTs combine two key data structures: annotated parse trees and communication phase graphs. By parsing the APT, the toolkit supports simulation, abstract interpretation and complexity analysis.>