Amdahl

The Fourier sum, involving the three dimensional FFT, does not currently run efficiently on more than perhaps eight processors in a network-of-workstations environment. On a more tightly coupled machine such as the Cray T3D/T3E, we obtain reasonable efficiency on 16 processors, as shown in Fig. 5. Our initial production implementation was targeted for a small workstation cluster, so we only parallelized the real-space part, relegating the Fourier component to serial evaluation on the master processor. By Amdahl s principle, the 16% of the work attributable to the serially computed Fourier sum limits our potential speedup on 8 processors to 6.25, a number we are able to approach quite closely. 

Amdahl, G. M. Validity of the single processor approach to achieve large scale computing capabilities. In Proc. AFIPS spring computer conf. vol. 30. AFIPS Press, Reston, Virginia, 1967. 

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

The EROS program system is written in PL/I and implemented on various IBM, Amdahl, CDC, and Siemens machines. Presently, two versions are supported, the 3.2 and 4.1 versions, consisting of about 9,000 and 13,000 statements, respectively. The essential difference between these two versions is that in EROS 3.2 the various... 

The CFF is known to run or have run on CRAY XMP, Amdahl VPllOO, many IBMs, Siemens, UNISYS, CDC, many VAXes, Ardent Titan. The program is a patchwork prepared over 20 years, written in IBM FORTRAN IV and later cleaned to conform to FORTRAN 77 new routines are written in FORTRAN 77. Development is now done on an Amdahl VPllOO, and vectorization is used where appropriate. 

EROS requires a minimum size of 300 K bytes of core storage. On an AMDAHL 470 V6, six reactions are generated per second for a molecule of 20 to 30 atoms. 

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

G. Amdahl, AFIPS, Comput. Conf., 30, 483 (1967). The Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities. 

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. 

Shuhnan DG, Amdahl L, Washington C, Graves A. A combined analysis of two studies assessing the ocular comfort of antiaUergy ophthalmic agents. Clin Ther 200325(4) 1096-1106. 

The EROS program system is written in PL/I and implemented on various IBM, Amdahl, CDC, and Siemens machines. Presently, two versions are supported, the... 

In that same year. Gene Amdahl, the designer of IBM Systems 360 and 370, left IBM to start his own company. Unsuccessful in raising 44 million in the United States, he turned to Fujitsu, which by providing the funds became the dominant stockholder in Amdahl s company. Its first product was made in Japan. Beginning in 1975, Fujitsu and then Hitachi were producing in Japan their version of Amdahl s System 370. Once IBM s technology be-... 

---