COMPUTING APPLICATIONS USING AMDAHL AS A METRIC USING AMDAHL’S LAW AS A METRIC TO DRIVE CODE PARALLELIZATION: TWO CASE STUDIES

Using Amdahl’s law as a metric, the authors illustrate a technique for developing efficient code on massively par-allel processor performance-class networks to solve nontrivial, high performance scientific problems.They also show the importance of collective communication within the message-passing interface paradigm for some appli-cations. Given the popularity of Beowulf-like clusters of workstations, this work also indicates the necessity of a scalable high performance network for obtaining efficient performance in parallel code. Using this approach, the au-thors were able to obtain an effective speedup (compari-son with the best sequential time) of 170 when using 256 of the Cray T3E 900 processing elements to solve a car-bon, molecular-dynamic problem. The authors also exam-ine the approach on a very different application:a Lanczos eigenvalue solver. Creating efficient parallel codes is a complex process that does not appear to have a solution in sight (Kuck, 1996). In this paper, we illustrate how one can use Amdahl’s law to analyze the characteristics of a program to achieve sig-nificant speedup. One can extend Amdahl’s law to incor-porate the most important factors limiting performance (Horoi and Enbody, 1998): • the magnitude of the sequential fraction of the code, • the communication overhead, and • the work imbalance on different processors. This report describes the quantitative analysis of these factors and the solutions used to diminish or eliminate their contribution in two case studies. Using this approach, we were able to obtain an effec-tive speedup (comparison with the best sequential time) of 170 when using 256 of the Cray T3E 900 processing el-ements (PEs). To understand the factors responsible for the limited performance of parallel codes, we turn to Amdahl’s law (Amdahl, 1967). Extending Amdahl, the speedup S can be given b