that any given processor will be more than a few standard deviations away from the mean, so the load imbalance should satisfy:
9.2.5 Waiting
Overhead associated with waiting can be difficult to disentangle from load imbalance. Waiting occurs when there is fine-grained imbalance even though the overall load may be balanced. For example, if processes must synchronize frequently between short computations, there is a possibility of substantial waiting overhead even if the computation on each processor is balanced in aggregate. In the sort algorithm the only synchronization occurs during the calls to MPI_Alltoall and MPI_Alltoallv, and they occur immediately after the initial decomposition, which should not suffer from load imbalance. Therefore, waiting overhead is negligible. It is also possible that waiting overhead could appear inside the implementation of MPI_Alltoallv.
9.3 Measurement of Integer Sort
Now that we have a general idea of sources of parallel overhead, we can instrument the code to ascertain how much overhead is actually present in practice. Overhead is usually a complicated function of hardware, implementation details, problem size, software environment, etc. Even on a particular machine, the relative importance of different operations depends on the size of the problem and the number of processors employed. The presence of other users and non-determinism due to cache effects, swapping, etc., further complicates the problem. It is easy to become overwhelmed with data when trying to understand the behavior of a parallel program. One solution to this problem is to use graphical tools to render a visual representation of the behavior of a parallel program. One such tool is upshot, which is part of the MPICH package. A screen shot is shown in Figure 9.1.
Upshot reads an event log which is automatically generated if the program is compiled with the -mpilog argument to mpicc. By default, the log records the start-time and finish-time of most of the basic MPI primitives. It is possible to add user-defined, application-specific elements to the trace, and to view them along with the communication routines using upshot. Consult the man pages for MPE_Log_event, MPE_Describe_event and MPE_Describe_state for details. Upshot has a sophisticated user interface that allows zooming, panning scrolling, etc., so that fine detail can be viewed within a much larger context.
