# Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis
## 3 Approach Overview  
Considering the analysis that was conducted in the previous section, we propose a high-level overview of the implementation of the MPI critical path-finding method which consists of the following stages:  
1. Synchronize timestamps of all MPI processes. * We use a monotonic clock to save timestamps and synchronize clocks using MPI_Allreduce at the start of the program (in MPI_init).
2. Log relevant MPI operations with relevant arguments and start-end timestamps. Link local operations into a linear graph. * We log every MPI call that involves process communication (e.g., MPI_Send, MPI_Recv, MPI_Reduce, MPI_Broadcast, etc.) using the MPI profiling interface. * For each MPI call, we log the start timestamp, end timestamp, function name, and function arguments (except user data). * Each MPI process maintains its own log-in memory. * The log represents a linear graph: an edge connects the log record \(N\) to the log record \(N+1\). The weight of the edge equals the difference between the start time \(N+1\) and the end time \(N\).
3. After MPI_Finalize, link corresponding local and remote operations (send/recv) to produce the final graph. * After the previous step, we have the log which is distributed across all MPI processes, and we now convert it to the graph. The local log contains only the edges for the vertices of the corresponding MPI process, and we need to create edges between the different MPI processes. (For each MPI call, we have a starting and ending vertex that is connected with the edge.) * To achieve this, each MPI process goes over all log records, and, for each MPI call, it requests information from the processes that were involved in this call. (It does not matter whether the receiver or sender obtains the information; we need to create the edges only in one MPI process not to produce duplicates.) The information is requested using the appropriate MPI calls (MPI_Send, MPI_Recv, MPI_Reduce, etc.), and the calls are different for each collective and point-to-point operation. * We can optimize the graph during conversion using techniques from [2]. For example, for MPI_Barrier, we need only one edge that connects the starting vertex for the last process to reach the barrier with the ending vertex for the last process to leave the barrier. For other blocking collective operations, the optimizations are similar. 4. Find the critical path using different algorithms and existing data distribution between nodes. * Now, we have the final graph that is composed of local graphs, which are stored in the corresponding MPI processes. The global graph is partitioned already, and all we need is to find the critical path. * For parallel processing, we need to map each vertex and edge of the graph to the rank of the MPI process that stores this edge or vertex. This is trivial to implement in the previous step by saving the rank of the target MPI process for each inter-process edge; all other vertices and edges are local to the node. * There are several algorithms for parallel graph search. The most common one is Delta-stepping (see Section 4). We make all weights negative and start the search from the vertex with the largest timestamp (which can also be determined in the previous step). * The algorithm can be optimized using the techniques in [12; 33].  
The implementation of the methods and algorithms for each stage is described in the following sections.