# Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis
## 4 Methods and Algorithms for Finding Critical Path
### Topological Sorting  
The main idea of this algorithm is taken from topological sorting: \"Sorting the vertices by the lengths of their longest incoming paths produces a topological ordering\" [35]. Topological sorting is used to determine the order of execution of dependent tasks (Figure 4). Here, we have the inverse problem: we already executed each task and now want to find the critical path. To find it, we sort each program edge by the start time, then find groups of overlapping edges, and, in each group, choose the largest edge. The main idea of inverse topological sorting is to decompose the edges into groups that come together (overlap). A straightforward implementation of this idea for any realistic MPI program will produce only one group that consists of all edges of the program run. The more practical approach is to group computation and communication edges separately  
Figure 3: Parallel splits: graph with no splits (**left**); graph with splits (**right**). or even to skip communication edges as they are redundant for deriving a critical path. We used the latter approach. The sequential topological sorting-based algorithm is as follows:  
1. Record intervals that denote MPI edges and program edges. 2. Gather all intervals in rank 0. 3. Sort them by start time (actually merge sorted arrays). 4. Find overlapping program edges. In each group, the longest edge belongs to the critical path (Figure 5). 5. Connect the longest program edges to each other. The parallel algorithm is mostly the same, but we have to distribute (shuffle) the data between the MPI processes (Figure 6), execute the algorithm on each individual part, and then collect the results from all processes to the root process. The algorithm follows:  
1. Record intervals that denote MPI edges and program edges. 2. Shuffle intervals between ranks. Each rank receives its own period of time. 3. Merge shuffled arrays in each rank. 4. Find overlapping program edges. In each group, the longest edge belongs to the critical path. 5. Connect the longest program edges to each other. 6. Gather all critical path segments in rank 0. Figure 4: Example of topological sorting. Figure 5: Groups of overlapping program edges. The topological sorting algorithm has the following advantages. * Linear time O(n). * Reliable: works even without cross-process edges. * No graph: no graph cycles are possible, nor are infinite program loops. There are some disadvantages as well. * Shuffle can be slow: need to transfer \((n-1)/n\) of the total size of the graph. * Overlapping is good enough but not perfect: e.g., need to detect non-MPI_COMM_WORLD communicators. The main disadvantage of this algorithm is that we have to somehow handle groups of interleaving intervals that spread two or more parts, i.e., the interval starts in part \(N\) and ends in part \(>=N+1\). There are two possible algorithms here. First, we can search for the rank that contains the end of this interval. This would result in exchanging all of the edges that overlap this interval from the \(currentrank+1\) up to the rank where the interval ends. This approach is simple but increases the amount of information sent over the network enormously: in the worst case, all MPI processes have to send all of their edges to all of the other processes, and the algorithm is no longer linear in terms of how much data are sent over the network--it is now quadratic. We call this algorithm _'topological-sorting-overlap'_, and this is the most accurate algorithm, although it requires sending an enormous amount of data over the network. Second, we can search for the last interval that overlaps the interval that spreads several parts. This algorithm is more efficient than sending all intervals from the next part but is more sophisticated to implement. It is not clear whether it is faster considering the difficulty of the implementation. We call this algorithm _'topological-sorting-master-worker'_. In our benchmarks, we resorted to using a simple algorithm that does not handle overlap of the intervals across parts.