Communication collective

Message passing, collective communication, and similar alternatives for programming software libraries for large-scale applications on distributed-memory computer systems. 

We now reexamine message passing as it pertains to software development and the interface of application software and library software. Compiler-managed parallelism is not yet ready for prime time. This means that efficient parallel programs are usually coded by hand, typically using point-to-point message passing and simple collective communications. There are many problems associated with this approach. 

Kiclmann, T. Hofman, R.H.F., Bal, H.E., Plaat, A., Bhoedjang, R.A.F. (1993) "Magpie MPFs collective communication operations via clustered wide area systems In Proc. Symposium on Principles and Practice of Parallel Programming, Sand Diego. 

Algorithms and cost analyses for a number of collective communication operations have been discussed in some detail by Grama et al. A comprehensive performance comparison of implementations of MPI on different network interconnects (InfiniBand, Myrinet , and Quadrics ), including both micro-level benchmarks (determination of latency and bandwidth) and application-level benchmarks, has been carried out by Liu et al. A discussion of the optimization of collective communication in MPICH, including performance analyses of many collective operations, has been given by Thakur et al. ... 

Thakur, R., R. Rabenseifner, and W. Gropp. Optimization of collective communication operations in MPICH. Int.. High Perform. C. 19 49-66,2005. 

The values for these machine-specific parameters can be somewhat dependent on the application. For example, the flop rate can vary significantly depending on the type of operations performed. The accuracy of a performance model may be improved by using values for the machine-specific parameters that are obtained for the type of application in question, and the use of such empirical data can also simplify performance modeling. Thus, if specific, well-defined types of operations are to be performed in a parallel program (for instance, certain collective communication operations or specific computational tasks), simple test programs using these types of operations can be written to provide the appropriate values for the pertinent performance parameters. We will show examples of the determination of application specific values for a, and y in section 5.3.2. 

Collective communication operations can reduce the scalability of a parallel program by introducing a communication bottleneck. Consider, for example, an algorithm requiring floating point operations and using... 

The efficiency obtained is a decreasing function of the number of processes, and the algorithm is not strongly scalable. In fact, parallel algorithms employing collective communication are never strongly scalable. 

We will illustrate parallel matrix-vector multiplication algorithms using collective communication in section 6.4, and detailed examples and performance analyses of quantum chemistry algorithms employing collective communication operations can be found in sections 8.3,9.3, and 10.3. 

Can collective communication be used without introducing a communication bottleneck ... 

Collective communication simplifies programming but tends to reduce scalability, particularly when replicated data is involved... 

Try to identify potential bottlenecks (serial code, replicated arrays, collective communication steps)... 

The computation of the residual is the dominant step in the iterative procedure. From Eq. 10.6, we see that a given residual matrix R,y, with elements Rfj , contains contributions from the integrals and double-substitution amplitudes with the same occupied indices, K,j and T,-y, respectively, as well as from the double-substitution amplitudes Tik and Tkj- The contributions from Tik and Tkj complicate the efficient parallelization of the computation of the residual and make communication necessary in the iterative procedure. The double-substitution amplitudes can either be replicated, in which case a collective communication (all-to-all broadcast) step is required in each iteration to copy the new amplitudes to all processes or the amplitudes can be distributed, and each process must then request amplitudes from other processes as needed throughout the computation of the residual. Achieving high parallel efficiency in the latter case requires the use of one-sided messagepassing. 

As opposed to the collective communication operation used in the integral transformation, this communication step is not scalable the communication time will increase with p, or, if the latency term can be neglected, remain nearly constant as p increases. This communication step is therefore a potential bottleneck, which may cause degrading parallel performance for the LMP2 procedure as the number of processes increases. To what extent this will happen depends on the actual time required for this step compared with the other, more scalable, steps of the LMP2 procedure, and we will discuss this issue in more detail in the following section. 

Looking at the parallel performance for the iterative procedure, the speedups are significantly lower than for the integral transformation, and for the uracil dimer the iterative procedure achieves a speedup of 52 for 100 processes. The nonscalable collective communication step required in each iteration is the primary factor contributing to lowering the speedup, but a... 

Having introduced the basic MPI calls for managing fhe execution environment, let us now discuss how to use MPI for message-passing. MPI provides support for both point-to-point and collective communication operations. 

A number of the most widely used collective communication operations provided by MPI are listed in Table A.3. The collective operations have been grouped into operations for data movement only (broadcast, scatter, and gather operations), operations that both move data and perform computation on data (reduce operations), and operations whose only function is to synchronize processes. In the one-to-all broadcast, MPl Bcast, data is sent from one process (the root) to all other processes, while in the all-to-all broadcast, MPI A11 gather, data is sent from every process to every other process (one-to-all and all-to-all broadcast operations are discussed in more detail in section 3.2). The one-to-all scatter operation, MPI Scatter, distributes data from the root process to all other processes (sending different data to different processes), and the all-to-one gather, MPI Gather, is the reverse operation, gathering data from all processes onto the root. 

To illustrate the use of collective commimication operations, we show in Figure A.2 an MPI program that employs the collective communication operations MPI.Scatter and MPi.Reduce the program distributes a matrix (initially located at the root process) across all processes, performs some computations on the local part of the matrix on each process, and performs a global summation of the data computed by each process, putting the result on the root process. 

---