Stochastic modeling of scaled parallel programs

Testing the performance scalabilityof parallelprograms can be a time consuming task, involving many performance runs for different computer configurations, processor num-bers, and problem sizes. Ideally, scalability issues would be addressed during parallel program design, but tools are not presently available that allow program developers to study the impact of algorithmicchoices under different pro-blem and system scenarios. Hence, scalability analysis is often reserved to existing (and available) parallelmachines as well as implemented algorithms. In this paper, we propose techniques for analyzing sca-led parallel programs using stochastic modeling approa-ches. Although allowing more generality and flexibility in analysis, stochastic modeling of large parallel programs is difficult due to solution tractability problems. We observe, however, that the complexity of parallel program models depends significantly on the type of parallel computation, and we present several computation classes where tracta-ble, approximate graph models can be generated. Our approach is based on a parallelization description of programs to be scaled. From this description, “scaled” stochastic graph models are automatically generated. Dif-ferent approximate models are used to compute lower and upper bounds of the mean runtime. We present evaluation results of several of these scaled (approximate) models and compare their accuracy and modeling expense (i.e., time to solution) with other solution methods implemented in our modeling tool PEPP. Our results indicate that accurate and efficient scalability analysis is possible using stochastic modeling together with model approximation techniques.