Performance analysis of parallel programs via message-passing graph traversal

The ability to understand the factors contributing to parallel program performance are vital for understand-ing the impact of machine parameters on the perfor-mance of specific applications. We propose a method-ology for analyzing the performance characteristics of parallel programs based on message-passing traces of their execution on a set of processors. Using this methodology, we explore how perturbations in both sin-gle processor performance and the messaging layer im-pact the performance of the traced run. This analysis provides a quantitative description of the sensitivity of applications to a variety of performance parameters to better understand the range of systems upon which an application can be expected to perform well. These per-formance parameters include operating system inter-ference and variability in message latencies within the interconnection network layer. 1