Characterizing Load and Communication Imbalance in Parallel Applications

More about the book

The increasing parallelism in modern supercomputers is expected to reach millions of processor cores per system, necessitating efficient software-managed parallelism for enhanced application performance. This requires optimal data exchange and workload distribution among processing elements. Performance analysis tools are essential for developers to evaluate and optimize parallel efficiency by identifying bottlenecks. However, many existing tools struggle to detect complex imbalance patterns and their performance impacts reliably. This dissertation introduces two innovative methods for automatically identifying imbalance-related performance issues from MPI program event traces. The first method, delay analysis, uncovers the root causes of wait states, which occur when one process takes longer than another, leading to idle periods during synchronization. While wait states are easy to spot, tracing them back to their causes can be challenging due to their potential distance from delays. Delay analysis addresses this by providing a cost model to describe delay severity and a scalable algorithm to locate delays and assess their impact. The second method, critical-path analysis, evaluates how imbalance affects program runtime by identifying the longest execution path without wait states. Optimizing activities on this path can significantly reduce runtime. This method yields compact performance indicators that help users assess