An important performance metric is parallel efficiency. Parallel
efficiency, E(N, P),
for a problem of size N on P nodes is
defined in the usual
way [65, 92] by
where T(N,P) is the runtime of the parallel algorithm, and is the runtime of the best sequential algorithm. For dense matrix computations, an implementation is said to be scalable if the parallel efficiency is an increasing function of , the problem size per node. The algorithms implemented in the ScaLAPACK library are scalable in this sense.
Figure 5.1 shows the scalability of the ScaLAPACK implementation of the LU factorization on the Intel XP/S Paragon computer. The nodes of the Intel XP/S Paragon computer are general-purpose (GP) or multiprocessor (MP) nodes, based on the Intel i860 XP RISC processors. Each Intel i860 processor is capable of a peak performance of 50 Mflop/s. On such a processor, however, the vendor-supplied BLAS matrix-matrix multiply routine DGEMM can achieve only approximately 45 Mflop/s. The computer used for obtaining the performance results presented in this chapter consisted of MP nodes configured as follows: each MP node had three Intel i860 XP processors -- two to execute application code and a third used exclusively as a message coprocessor . On such a node, the vendor-supplied BLAS matrix-matrix multiply routine DGEMM can achieve approximately 90 Mflop/s.
Figure 5.1: LU Performance per Intel XP/S MP Paragon node
Figure 5.1 shows the speed in Mflop/s per node of the ScaLAPACK LU factorization routine PDGETRF for different computer configurations. This figure illustrates that when the number of nodes is scaled by a constant factor, the same efficiency or speed per node is achieved for equidistant problem sizes on a logarithmic scale. In other words, maintaining a constant memory use per node allows efficiency to be maintained. (This scalability behavior is also referred to as isoefficiency, or isogranularity .) In practice, however, a slight degradation is acceptable. The ScaLAPACK driver routines, in general, feature the same scalability behavior up to a constant factor that depends on the exact number of floating-point operations and the total volume of data exchanged during the computation.
In large dense linear algebra computations, the computation cost dominates the communication cost. In the following, the time to execute one floating-point operation by one node is denoted by . The time to communicate a message between two nodes is approximated by a linear function of the number of items communicated. The function is the sum of the time to prepare the message for transmission () and the time taken by the message to traverse the network to its destination, that is, the product of its length by the time to transfer one data item () . Alternatively, is also called the latency, since it is the time to communicate a message of zero length. On most modern interconnection networks, the order of magnitude of the latency varies between a microsecond and a millisecond.
The bandwidth of the network is also referred to as its throughput. It is proportional to the reciprocal of . On modern networks, the order of magnitude of the bandwidth is the megabyte per second. For a scalable algorithm with held constant, one expects the performance to be proportional to P. The algorithms implemented in ScaLAPACK are scalable in this sense. Table 5.1 summarizes the relevant constants used in our scalability analysis.
Table 5.1: Variable definitions
Using the notation presented in table 5.1,
the execution time of the ScaLAPACK drivers can be
The corresponding parallel efficiency
can then be approximated by
Equation 5.2 illustrates, in particular, that the communication versus computation performance ratio of a distributed-memory computer significantly affects parallel efficiency. The ratio of the latency to the time per flop greatly affects the parallel efficiency of small problems. The ratio of the network throughput to the flop rate significantly affects the parallel efficiency of medium-sized problems. For large problems, the node flop rate is the dominant factor contributing to the parallel efficiency of the parallel algorithms implemented in ScaLAPACK.