Parallel execution time

NWChem (we tested Version 3.2.1) is a program for ah initio, band-structure, molecular mechanics, and molecular dynamics calculations. The DFT band-structure capability is still under development and was not included in the Linux version tested. NWChem is unique in that it was designed from scratch for efficient parallel execution. The user agreement is more restrictive than most, apparently because the code is still under active development. At the time of this book s publication, limited support was available for users outside of the EMSL facility. 

Parallel tasks with different execution times... 

Here the execution time (T) of the program is described as a function of the number of processors ( ), the problem size (N), the memory size (M), the latency and transmission time of remote memory references (fO,tl), and other relevant parameters. We understand already that T can be a nonlinear function of the problem size and sensitive to the algorithm [e.g., conventional self-consistent field (SCF),29 T(N) = 0 N ) + 0 N ) vs. pseudospectral SCF," T(N) = 0 N ) + 0(N3)], and similarly the dependence on P can be complex. As discussed earlier, one measure of the efficiency of parallel execution may then be derived as follows ... 

For data-parallel environments (SIMD programming model), performance can be represented using standard profiling techniques that associate fraction of overall execution time with particular pieces of code. As noted earlier, this programming model has limited utility for the applications we address, and we do not dwell on performance evaluation. 

In this relation, known as Amdahl s law, f represents the fraction of the singleprocess execution time that is consumed by the parts of the algorithm that have not been parallelized, and / is defined as... 

The execution time for a parallel algorithm is a function of the number of processes, p, and the problem size, n. Additionally, the execution time depends parametrically on several machine-specific parameters that characterize the communication network and the computation speed the latency and the inverse of the bandwidth, a and p, respectively (both defined in section 5.1),... 

Let us develop an expression for the execution time for a parallel program, assuming that computation is not overlapped with communication and that no process is ever idle. Each process, then, will always be engaged in either computation or communication, and the execution time can be expressed as a sum of the computation and the communication times... 

Measured parallel LMP2 speedups for the uracil dimer using the cc-pVDZbasis set. Timings were obtained on a Linux cluster speedups were computed (from measured wall times) relative to the execution time required using one process. 

The execution time includes various synchronization and communication overheads, which means that in fact only part of the whole computational work can be performed in parallel. The overheads are usually machine dependent and are harder to estimate, so theoretical analysis frequently ignores them and tends to give overly optimistic estimates for the power of various parallel algorithms. 

---