Abstract The critical path of a parallel application is a fundamental metric for its execution. It represents the longest execution sequence without wait delays and hence dictates the complete overall runtime: adding to the critical path will directly increase the runtime, while shortening or optimizing sections of the critical path will result in a reduction of the overall runtime. On the other hand, changing the execution time of program sections not on the critical path will not affect the program runtime. Knowing the critical path allows the user to characterize the application and its communication behavior, explore differences in the execution behavior with respect to scaling and parameter changes, and identify potential bottlenecks or performance problems. It is also a prerequisite for dealing with scalability problems in performance analysis and optimization. The increasing number of nodes in modern clusters, often reaching thousands, makes it impossible to investigate, manually analyze, or often just visualize the performance data collected from all nodes. Knowing the critical path, however, enables us to restrict optimization efforts to the relevant parts of the execution. In this paper we present an hybrid online/post-mortem approach to identify, isolate, and visualize the critical path of MPI applications. During the online component we gather information on each processor locally, in order not to add additional communication requirements. After program termination we combine the individual local results for global analysis. In order to implement our approach, we abstract the program as an execution graph in which all MPI communication operations are shown as nodes. Directed edges represent both sequential execution within one processor as well as message events between processors. The critical path is then a subset of the complete execution graph. To extract it, we build relevant subsets dynamically at runtime using an MPI wrapper library that traces all MPI communication operations. At each receive operation, we identify the execution graph edges that do not incur a wait time and are hence potentially part of the critical path; we store them as part of a local subgraph. After the termination of the application, we merge these subgraphs, identify which of the potential edges stored in the local graphs are actually part of the completed global critical path, prune the remaining nodes, and export to result in a portable graph format for visualization and further processing. This graph shows all sections in the program's execution that contribute to the critical path as well as all communication events that cause the critical path to transit between processors. The graph form has the further advantage, in contrast to profiling data or tabular representations, that it retains much of the structural information of the initial application execution and with that eases further high-level analysis steps.
There are also many similarities to the critical path profiling presented by Schulz in REF .
Extracting Critical Path Graphs from MPI Applications
2005 IEEE International Conference on Cluster Computing
2005 IEEE International Conference on Cluster Computing
Computer Science