# Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis
## 5 Profiling MPI Applications
### Converting the Log Records to the Graph  
In order to transform the log to the graph, we repeat all of the MPI calls from the log, but, instead of the real data, we send the data that are needed by the receiving process to construct nodes and edges of the graph. The resulting graph is per process but may contain outgoing or incoming communication edges from other processes.  
Blocking point-to-point call (send and receive) handling is straightforward. For non-blocking send and receive, we maintain a list of requests, and, when we encounter MPI_Wait, we find the corresponding request in this list and use it to complete the wait call. MPI_Waitall is simulated by calling MPI_Wait for each request in the corresponding array.  
Blocking collective calls are handled by gathering the start and end times of the call for each rank in the first MPI process. Then, we compute the maximum start time and minimum end time for the statistics, broadcast all of the statistics and the start/end time to all processes in the communicator, and compute the per-rank statistics. Next, we generate all possible edges between the start and end nodes of each process (from the start of each process to the end of each process).  
The per-rank statistics include the execution time (the time spent actually executing the collective MPI call), wait-before time (the time the process waited for other processes before executing the call), and wait-after time (the time the process waited after executing the call). These data are computed using the following formulas.  
t_wait_before = t_start_max - t_start[i] t_wait_after = t_end[i] - t_end_min t_execution = t_end[i] - t_start[i] - t_wait_before - t_wait_after = = t_end_min - t_start_max imbalance = (t_wait_before + t_wait_after) / t_execution  
These formulas work very well if the MPI call has an implicit barrier at the end, but, if there is no such behavior, then the formulas may produce a negative wait time. Edges with negative times can be removed from the graph to speed up the critical path finding. The calls with implicit barriers can be found experimentally: in OpenMPI v4.1.1, we found that MPI_Bcast, MPI_Barrier, and MPI_Reduceall all have implicit barriers, but MPI_Reduce does not, for example.  
Using these formulas, we computed the imbalance for each MPI call as the ratio of the total wait time to the total execution time. For MPI calls, this metric shows how much time (in percentages of execution time) we would save if the call was made well balanced (i.e., no wait time). The same metric is computed for each MPI process (but we sum all the numerators and denominators and add the execution time of the program edges to the denominator) and for the whole program (but we sum all the numerators and denominators across processes and divide them by the number of ranks). The corresponding formulas are presented below.  
imbalance_call = (t_wait_before + t_wait_after) / t_execution imbalance_process = sum(t_wait_before + t_wait_after for each call) / (sum(t_execution for each call) + t_program_edges) imbalance_program = sum(t_wait_before + t_wait_after for each call and process) / (sum(t_execution for each call and process) + sum(t_program_edges for each process))