Amdahl s law

Fig. 1. Amdahl s law. Speedup as a function of the percentage of the program that can be vectorized. Lower curve vector—scalar speedup = 10 upper curve...

Assume that we have a program we will run on np processors and that this program has a serial portion and a parallel portion. For example, the serial portion of the code might read in input and calculate certain global parameters. It does not make any difference if this work is done on one processor and the results distributed, or if each processor performs identical tasks independently this is essentially serial work. Then the time t it takes the program to run in serial on one processor is the sum of the time spent in the serial portion of the code and the time spent in the parallel portion (i.e., the portion of the code that can be parallelized) is t = tg + tp. Amdahl s law defines a parallel efficiency, Pe, of the code as the ratio of total wall clock time to run on one processor to the total wall clock time to run on np processors. We give a formulation of Amdahl s law due to Meijer [42] ... 

An important aspect of an efficient implementation of any program on current and future high-performance computers is the level of parallelism. Our tests show that for the ZUj4 cluster 96% of the code is parallel and for larger clusters this ratio increases. Taking into account Amdahl s law (48) we can expect a factor of at least 3.5 improvement in performance (total time) on a four procesor machine. In the last column of Table VI the expected wall clock time is presented. 

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%.

One quick way to tell whether Ts riai is the most important factor or whether other issues should be explored is to quantitatively test empirical speed-up curves for consistency with Amdahl s law. If they are not, then some factor other than is at work. In that case, further investigation will be... 

Figure 7 shows how the HF application scales, based on this modified definition of Amdahl s law. The cases in Figure 7 are defined as parallel) overhead) The base case is (30,3000,30). Larger cases scale as 0 N), 0(N ), 0(N), respectively, which is similar to a traditional HF algorithm. For small problems, the serial and overhead terms are relatively important and become more so as the processor count increases. For the smallest case shown, overhead increases until it outweighs the actual computation, and the speed-up curve turns over, with the result that using more processors actually makes the computation go slower. Conversely, as the problem size is increased, the serial and overhead terms become less significant, and speed-up approaches the ideal linear curve. 

This simple modified Amdahl s law illustrates the incentives for optimal load balancing. The case(0,3000,0) corresponds to a hypothetical situation in which there is no serial execution time and no overhead for communication. The deviation from linear speed-up in this case (about 10%) is due only to load imbalance. 

Amdahl s Law The performance of an application cannot surpass what is possible if the parallelized (or vectorized) component of the application is executed in zero time cf. Equations [2] and [4]. 

L. Kleinrock and J. H. Huang, IEEE Trans. Software Eng., SE-18, 434 (1992). On Parallel Processing Systems. Amdahl s Law Generalized and Some Results on Optimal Design. 

R. A. Kendall, unpublished work, 1993. The source code for the Hartree-Fock modified Amdahl s law application is available from anonymous ftp at ftp.pnl.gov. It may be necessary to send electronic mail to ftpadmin pnl.gov to get access from your site. 

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 speedup limit of 1// given by Amdahl s law is derived using the assumption that the fraction of serial code is independent of the problem size. It has been argued by Gustafson, however, that the serial fraction is likely to decrease when the problem size increases, and that the definition of the speedup should reflect this. Gustafson expressed the execution time on p processes and on a single process as follows... 

At the same time, there is a significant benefit when the system is large, since the Jacobian and system are calculated and solved at least twice at the starting and final points. Nevertheless, according to Amdahl s law (Amdahl, 1967), the relevance of the benefits can be limited to a small number of processors (e.g., 2-16). 

However, this is not the end of the matter, because the 1.6 times increase in processor performance does not necessarily mean that an application will run 1.6 times faster. This is due to the fact that in order to exploit the performance of the dual cores, the application needs to exhibit sufficient parallelism so that different parts of the application can run concurrently on each core. In general, the parallel speedup which can be achieved with multiple processors (or cores) is determined by the portion of the application which must be executed sequentially. This is known as Amdahl s Law (Amdahl 1967), which can be expressed formally as the... 

For high performance, the computer architecture must be planned using the principles discussed previously and Amdahl s law. 

Amdahl s law The maximum concurrent speedup for a concurrent algorithm is limited by its sequential components. Thus, if the sequential component takes a fraction /seq of the total run time on one node of a concurrent processor, the maximum possible speedup is... 

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 ... 

---