# Finding Bottlenecks in Message Passing Interface Programs by Scalable Critical Path Analysis
## 6 Benchmarking
### NAS Parallel Benchmarks
\begin{table}
\begin{tabular}{p{56.9 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt} p{113.8 pt}} \hline \hline
**Benchmark** & **Name** & **Description** & **Problem Sizes and Parameters (Class C)** \\ \hline MG & Multi-grid on a sequence of meshes, long- and short-distance communication, memory intensive & Approximation of the solution of a three-dimensional discrete Poisson equation using the V-cycle multigrid method. & grid size: \(512\times 512\times 512\) no. of iterations: 20 \\ \hline CG & Conjugate gradient, irregular memory access and communication & Approximation to the smallest eigenvalue of a large sparse, symmetric positive-definite matrix using inverse iteration together with the conjugate gradient method as a subroutine for solving linear systems of algebraic equations. & no. of rows: 150,000 no. of nonzeros: 15 no. of iterations: 75 eigenvalue shift: 110 \\ \hline FT & Discrete 3D fast Fourier Transform all-to-all communication & Solving a three-dimensional partial differential equation using the Fast Fourier Transform (FFT). & grid size: \(512\times 512\times 512\) no. of iterations: 20 \\ \hline IS & Integer sort, random memory access & Sorting small integers using pocket sorting. & no. of keys: \(2^{27}\) key max. value: \(2^{23}\) \\ \hline EP & Embarrassingly Parallel & Generation of independent normally distributed random variables using Marsaglia polar method. & no. of random-number pairs: \(2^{32}\) \\ \hline BT & Block tri-diagonal solver & Solves a synthetic system of nonlinear diffs. partial differential equations (a 3-dimensional system of Navier–Stokes equations for a compressible liquid or gas) using a three-block tridiagonal scheme with the method of variable directions (BT), a scalar five-diagonal scheme (SP), and a method of symmetric sequential upper relaxation (SSOR algorithm, LU problem). & grid size: \(162\times 162\times 162\) no. of iterations: 200 \\ \hline SP & Scalar penta-diagonal solver & Solution of the heat equation taking into account diffusion and convection in a cube. The heat source is mobile, the grid is irregular, and changes every \(5\) steps. & grid size: \(162\times 162\times 162\) no. of iterations: 250 \\ \hline LU & Lower-upper Gauss–Seidel solver & Same problem as SP, but the method is different. & grid size: \(162\times 162\times 162\) no. of iterations: 250 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: NAS Parallel Benchmarks description with problem sizes and parameters of Class C.  
Figure 15: NAS Benchmarks execution time: real time (no critical path data collection). The detailed benchmark results obtained for different NPB cases with the topological sorting algorithm follow in Tables 3-8 and the benchmark parameters in Table 9:  
Figure 16: NAS Benchmarks execution time: with mpi-graph (parallel Dijkstra algorithm). Figure 17: Relative overhead of _mpi-graph_ (parallel Dijkstra). \begin{table}
\begin{tabular}{l l l l l l} \hline \hline
**Benchmark** & **Nprocesses** & **Nnodes** & **Tasks-per-Node** & \
\begin{tabular}{c} **Rel. Overhead** \\ **(No Compression)** \\ \end{tabular} &
\begin{tabular}{c} **Rel. Overhead** \\ **(Compression)** \\ \end{tabular} \\ \hline ep.C & 4 & 1 & 4 & 0.02 & 0.01 \\ ep.C & 16 & 2 & 8 & 0 & 0.01 \\ ep.C & 32 & 4 & 8 & 0.09 & 0.02 \\ ep.C & 64 & 8 & 8 & 0.44 & 0.05 \\ is.C & 4 & 1 & 4 & 0 & 0 \\ is.C & 16 & 2 & 8 & 0.02 & 0.001 \\ is.C & 32 & 4 & 8 & 0.19 & 0.06 \\ is.C & 64 & 8 & 8 & 0.06 & 0 \\ lu.C & 4 & 1 & 4 & 0 & 0.01 \\ lu.C & 16 & 2 & 8 & 0.06 & 0.02 \\ lu.C & 32 & 4 & 8 & 0.10 & 0.04 \\ lu.C & 64 & 8 & 8 & 0.16 & 0.09 \\ mg.C & 4 & 1 & 4 & 0 & 0.01 \\ mg.C & 16 & 2 & 8 & 0.04 & 0 \\ mg.C & 32 & 4 & 8 & 0.14 & 0.02 \\ mg.C & 64 & 8 & 8 & 0.25 & 0.06 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of versions without/with compression of shuffle data using topological sorting algorithm.