# Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis
## 6 Benchmarking  
### NAS Parallel Benchmarks  
The NAS Parallel Benchmarks [4] is a set of performance tests aimed at testing the capabilities of highly parallel supercomputers. They were developed in the early 1990s as part of the NASA Numerical Aerodynamic Simulation Program and are supported by the NASA Advanced Supercomputing (NAS) Division located at NASA Ames Research Center. There are several classes for each benchmark that are related to the problem size. * Class S: small for quick test purposes;
* Class W: workstation size (a 1990s workstation; now likely too small)
* Classes A, B, and C: standard test problems; 4\(\times\) size increase going from one class to the next;
* Classes D, E, and F: large test problems; 16\(\times\) size increase from each of the previous classes. Different benchmarks have different requirements for the number of processes, as listed below:  
* BT, SP--a square number of processes (1, 4, 9,...);
* LU--2D (n1 \(\times\) n2) process grid where n1/2 \(<\)= n2 \(<\)= n1;
* CG, FT, IS, MG--a power-of-two number of processes (1, 2, 4,...);
* EP, DT--no special requirement. The required process count is checked at runtime. By default, a run will abort if the process count requirement is not met. For IS and DT, there is a minimal process count for a given class of problem size. Table 1 presents the description of each benchmark including the problem sizes and parameters of Class C, which were used in the experiments. We tested the performance of the _mpi-graph_ tool (applying different versions of the critical path algorithms) using the NAS Parallel Benchmarks of Class C run on 4, 16, 32, and 64 processors. We measured the following:  
* total run time with MPI call recording;
* total run time with MPI call recording + critical path finding;
* total run time without _mpi-graph_. The results for the sequential Dijkstra algorithm are presented in Figure 14.  
Figure 14 shows that the _mpi-graph_ tool incurs some overhead, the magnitude of which depends on the particular benchmark. Further analysis revealed that most of the overhead is caused by critical path finding rather than log collection. Figures 15 and 16 present the bar charts of the NAS Benchmarks' execution time on various numbers of processors without/with _mpi-graph_ usage (with the parallel Dijkstra algorithm). Figure 17 shows the relative overhead of using the _mpi-graph_ tool (MPI call recording + critical path finding with the parallel Dijkstra). In this plot, the overhead is measured in the number of times the execution of the application with _mpi-graph_ exceeds the execution of the original program. In particular, we can see that the _ep.D_ benchmark runtime is more than 2.5 times longer when _mpi-graph_ is used with the parallel Dijkstra algorithm, which demonstrates that this approach is not scalable enough. Our experiments with classical algorithms (sequential and parallel Dijkstra, Delta-stepping) revealed noticeable overheads for some benchmark cases. To deal with this further, we concentrated on the topological sorting algorithm, which showed much better results in the same cases. In addition, the compression technique described in the same section allowed for further improvement to the results (see Table 2). In this table, the relative overhead corresponds to the quotient of difference between _mpi-graph_ and non-_mpi-graph_ runtimes divided by the _mpi-graph_ runtime. In some cases, however, compression can lead to slowdown (e.g., in the case in which large data volumes are sent over fast communications and slow computing nodes), so the effect of using compression must be evaluated in each particular case; compression can be switched on or off in the configuration file. Figure 14: NAS Parallel Benchmarks test results (sequential Dijkstra).