Speedup ideal

Speedup. The good performance merits discussioa. The ideal parallel computer has as many as an infinite number of processors, as much as... 

Figure 6 Amdahl s law as a function of the number of processors. Each curve in this family of curves represents a different percentage of the code that runs in parallel. The Speedup(lOO) curve is the ideal curve because the code executes in parallel 100%.

Given these characteristics, it is evident that large-scale semiempirical SCF-MO calculations are ideally suited for vectorization and shared-memory parallelization the dominant matrix multiplications can be performed very efficiently by BLAS library routines, and the remaining minor tasks of integral evaluation and Fock matrix construction can also be handled well on parallel vector processors with shared memory (see Ref. [43] for further details). The situation is less advantageous for massively parallel (MP) systems with distributed memory. In recent years, several groups have reported on the hne-grained parallelization of their semiempirical SCF-MO codes on MP hardware [76-79], but satisfactory overall speedups are normally obtained only for relatively small numbers of nodes (see Ref. [43] for further details). 

In practice, ideal speedups are difficult to achieve, especially if the number of processes is large. One factor that reduces the speedup is the existence in an algorithm of inherently sequential parts of code that cannot benefit from a parallel implementation. An upper bound on the speedup was formulated by Amdahl, who expressed the maximum attainable speedup for a parallel algorithm in terms of the serial fraction, f, of the algorithm... 

Speedup curves illustrating commonly encountered performance patterns, (a) ideal (b) superlinear speedup with performance degradation due to, e.g., communication overhead or load imbalance (c) logarithmic communication overhead (d) linear communication overhead (e) incompletely parallelized program (serial fraction of 0.025). See text for details. 

Predicted and measured speedups and efficiencies for the simple parallel matrix-vector multiplication outlined in Figure 5.4. Dashed curves represent predictions by the performance model, solid curves show measured values, and the dot-dashed line is the ideal speedup curve. The... 

As it stands, nowadays the architectural advantage of supercomputers is due almost entirely to parallelism, i.e., many processors in a supercomputer are commonly involved in a single computational task. Ideally, the speedup that is achieved increases linearly with the number of processors that are contributing to such a computational task. Because of the time spent in the coordination of the processors, this linear increase in speed is seldomly observed. Nevertheless, parallelism enables us to tackle computational problems that would be simply unthought of without it. 

In general, the ideal speedup is 5(/tp, n) = /tp, but this situation is usually not attainable due to load imbalance, communication overhead, and the fact that parts of the code are inherently sequential. Assuming that the sequential parts of an algorithm constitute the only deviation from the ideal case, and that the sequential parts consume a fraction / of the total execution time, the speedup limit may be expressed by the following relation known as Amdahl s law ... 

---