Modeling the Execution Time

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), 

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. 

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 

The commimication time required by an algorithm is a tunction ot the number ot messages sent and ot the length ot these messages. Using the idealized machine model (Eq. 5.1), the total commimication time can be estimated as 

The presence of nonuniform computational tasks whose sizes are not known in advance is often the cause of load imbalance, and quantitative modeling of load imbalance can therefore be difficult to do. However, simulations that involve distribution of nonuniform tasks can sometimes provide empirical data that can be used to model load imbalance. In chapter 7 we will illustrate the use of empirical data to model load imbalance in the computation of the two-electron integrals, which is a required step in many quantum chemical methods. Parallel programs involving uniform computational tasks will experience load imbalance whenever the number of tasks is not a multiple of the number of processes. This kind of load imbalance is easier to include in a performance model because the amount of work assigned to the process 

---