Reevaluating Amdahl's law

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reevaluating Amdahl's law

Full text

Pdf (148 KB)

Source

Communications of the ACM archive
Volume 31 , Issue 5 (May 1988) table of contents

Pages: 532 - 533

Year of Publication: 1988

ISSN:0001-0782

Author

John L. Gustafson

Sandia National Laboratory, Albuquerque, NM

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 48, Downloads (12 Months): 328, Citation Count: 79

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/42411.42415 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Amdahl, G.M. Validity of the single-processor approach to achieving large scale computing capabilities. In AFIP$ Conference Proceedings, vol. 30 (Atlantic City, N.I., Apr. 18-20). AFIPS Press, Reston, Va., 1967, pp. 483-485.
	2	Benner, R.E., Gustafson, J.L., and Montry, R.E. Development and analysis of scientific application programs on a 1024~processor hypercube. SAND 88-0317, Sandia National Laboratories, Albuquerque, N.M., Feb. 1988.

CITED BY 79

	R. Nelson, Including queueing effects in Amdahl's law, Communications of the ACM, v.39 n.12es, Dec. 1996
	Steven K. Reinhardt , Mark D. Hill , James R. Larus , Alvin R. Lebeck , James C. Lewis , David A. Wood, The Wisconsin Wind Tunnel: virtual prototyping of parallel computers, ACM SIGMETRICS Performance Evaluation Review, v.21 n.1, p.48-60, June 1993
	A. Cox , R. Fowler, The implementation of a coherent memory abstraction on a NUMA multiprocessor: experiences with platinum, ACM SIGOPS Operating Systems Review, v.23 n.5, p.32-44, Dec. 3–6, 1989
	CORPORATE Tech Correspondence, Technical correspondence, Communications of the ACM, v.32 n.8, p.1014-1024, Aug. 1989
	Narsingh Deo , Muralidhar Medidi , Sushil Prasad, Processor allocation in parallel battlefield simulation, Proceedings of the 24th conference on Winter simulation, p.718-725, December 13-16, 1992, Arlington, Virginia, United States
	M. L. Barton , G. R. Withers, Computing performance as a function of the speed, quantity, and cost of the processors, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.759-764, November 12-17, 1989, Reno, Nevada, United States
	D. E. Platt , A. R. Rossi , J. W. Wells , J. Becker, Realities associated with parallel processing, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.162-174, November 12-17, 1989, Reno, Nevada, United States
	C. S. Chang , R. Nelson, Bounds on the speedup and efficiency of partial synchronization in parallel processing systems, Journal of the ACM (JACM), v.42 n.1, p.204-231, Jan. 1995
	Paolo Cremonesi , Claudio Gennaro, Integrated Performance Models for SPMD Applications and MIMD Architectures, IEEE Transactions on Parallel and Distributed Systems, v.13 n.7, p.745-757, July 2002
	Bob Boothe , Abhiram Ranade, Improved multithreading techniques for hiding communication latency in multiprocessors, ACM SIGARCH Computer Architecture News, v.20 n.2, p.214-223, May 1992
	J. K. Cringean , R. England , G. A. Manson , P. Willett, Parallel text searching in serial files using a processor farm, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.429-453, September 05-07, 1990, Brussels, Belgium
	Philippe Collard , Andre Goforth , Matthew Marquardt, Ada as a parallel language for high performance computers: experience and results, Proceedings of the conference on TRI-ADA '90, p.346-351, December 03-06, 1990, Baltimore, Maryland, United States
	Steve A. Strate , Roger L. Wainwright, Load balancing techniques for dynamic programming algorithms on hypercube multiprocessors, Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, p.562-569, February 14-16, 1993, Indianapolis, Indiana, United States
	CORPORATE Tech Correspondence, Technical correspondence, Communications of the ACM, v.32 n.8, p.1014-1024, Aug. 1989
	Leo Chin Sim , Heiko Schroder , Graham Leedham, Major line removal morphological hough transform on a hybrid system, Journal of Parallel and Distributed Computing, v.64 n.9, p.1060-1068, September 2004
	Alan H. Karp , Horace P. Flatt, Measuring parallel processor performance, Communications of the ACM, v.33 n.5, p.539-543, May 1990
	K. C. Sevcik, Characterizations of parallelism in applications and their use in scheduling, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.171-180, May 1989
	Kenneth E. Hoganson, High-performance computer architecture and algorithm simulator, Journal on Educational Resources in Computing (JERIC), v.2 n.1, p.131-148, March 2002
	Michael Tinker, DVI parallel image compression, Communications of the ACM, v.32 n.7, p.844-851, July 1989
	Daniel Nussbaum , Anant Agarwal, Scalability of parallel machines, Communications of the ACM, v.34 n.3, p.57-61, March 1991
	Parallel computing with generalized cellular automata, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	Amit Reisman , Craig Gotsman , Assaf Schuster, Parallel progressive rendering of animation sequences at interactive rates on distributed-memory machines, Proceedings of the IEEE symposium on Parallel rendering, p.39-47, October 20-21, 1997, Phoenix, Arizona, United States
	Omer F. Rana , Kate Stout, What is scalability in multi-agent systems?, Proceedings of the fourth international conference on Autonomous agents, p.56-63, June 03-07, 2000, Barcelona, Spain
	Gordon Lyon, Comparison of two code scalability tests, Information Processing Letters, v.81 n.3, p.169-174, 14 February 2002
	W. A. Maniatty , B. K. Szymanski , T. Caraco, Parallel computing with generalized cellular automata, Progress in computer research, Nova Science Publishers, Inc., Commack, NY, 2001
	Françoise Roch-Siebert , Gilles Villard, PAC: first experiments on a 128 transputers méganode, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.343-351, July 15-17, 1991, Bonn, West Germany
	G. Karypis , V. Kumar, Unstructured Tree Search on SIMD Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1057-1072, October 1994
	Paolo Cremonesi , Claudio Gennaro, Integrated Performance Models for SPMD Applications and MIMD Architectures, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1320-1332, December 2002
	Kenneth E. Hoganson, Workload Execution Strategies and Parallel Speedup on Clustered Computers, IEEE Transactions on Computers, v.48 n.11, p.1173-1182, November 1999
	Randolph Nelson, A performance evaluation of a general parallel processing model, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.13-26, May 1990
	Xian-He Sun , Lionel M. Ni, Another view on parallel speedup, Proceedings of the 1990 conference on Supercomputing, p.324-333, October 1990, New York, New York, United States
	Vipin Kumar , Anshul Gupta, Analysis of scalability of parallel algorithms and architectures: a survey, Proceedings of the 5th international conference on Supercomputing, p.396-405, June 17-21, 1991, Cologne, West Germany
	Sartaj Sahni , Venkat Thanvantri, Performance Metrics: Keeping the Focus on Runtime, IEEE Parallel & Distributed Technology: Systems & Technology, v.4 n.1, p.43-56, March 1996
	Silvia Cambi , Alessandra Esposito , Mauro Mongiardo , Luciano Tarricone , Federico Malucelli, A parallel: distributed approach to the analysis of complex waveguide circuits, Practical parallel computing, Nova Science Publishers, Inc., Commack, NY, 2001
	Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
	Selim G. Akl , Stefan D. Bruda, Improving A Solution's Quality Through Parallel Processing, The Journal of Supercomputing, v.19 n.2, p.221-233, June 2001
	Tim Purcell, Parallel ray tracing on a chip, Practical parallel rendering, A. K. Peters, Ltd., Natick, MA, 2002
	Nicolas Barberou , Marc Garbey , Matthias Hess , Michael M. Resch , Tuomo Rossi , Jari Toivanen , Damien Tromeur-Dervout, Efficient metacomputing of elliptic linear and non-linear problems, Journal of Parallel and Distributed Computing, v.63 n.5, p.564-577, May 2003
	Leo Chin Sim , Heiko Schroder , Graham Leedham, MIMD-SIMD hybrid system: towards a new low cost parallel system, Parallel Computing, v.29 n.1, p.21-36, January 2003
	Vikram S. Adve , Mary K. Vernon, Parallel program performance prediction using deterministic task graph analysis, ACM Transactions on Computer Systems (TOCS), v.22 n.1, p.94-136, February 2004
	N. Balram , C. Belo , J. M. F. Moura, Parallel processing on supercomputers: a set of computional experiments, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.247-257, November 12-17, 1988, Orlando, Florida, United States
	P. Krueger , T. H. Lai , V. A. Dixit-Radiya, Job Scheduling is More Important than Processor Allocation for Hypercube Computers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.5, p.488-497, May 1994
	C. B. Stunkel , W. K. Fuchs, An Analysis of Cache Performance for a Hypercube Multicomputer, IEEE Transactions on Parallel and Distributed Systems, v.3 n.4, p.421-432, July 1992
	D. P. Helmbold , C. E. McDowell, Modeling Speedup (n) Greater than n, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.250-256, April 1990
	Scott T. Leutenegger , Mary K. Vernon, The performance of multiprogrammed multiprocessor scheduling algorithms, ACM SIGMETRICS Performance Evaluation Review, v.18 n.1, p.226-236, May 1990
	Kai Hwang , Cho-Li Wang , Choming Wang , Zhiwei Xu, Resource Scaling Effects on MPP Performance: The STAP Benchmark Implications, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.509-527, May 1999
	Kenneth Hoganson, Mapping Parallel Application Communication Topology to Rhombic Overlapping-Cluster Multiprocessors, The Journal of Supercomputing, v.17 n.1, p.67-90, Aug. 2000
	Zhongqiang Chen , Alex Delis , Henry L. Bertoni, Radio-wave propagation prediction using ray-tracing techniques on a network of workstations (NOW), Journal of Parallel and Distributed Computing, v.64 n.10, p.1127-1156, October 2004
	Kien A. Hua , Chiang Lee , Chau M. Hua, Dynamic Load Balancing in Multicomputer Database Systems Using Partition Tuning, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.968-983, December 1995
	A. Gupta , V. Kumar, The Scalability of FFT on Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.922-932, August 1993
	Gregory D. Peterson , Roger D. Chamberlain, Beyond Execution Time: Expanding the Use of Performance Models, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.2, p.37-49, June 1994
	Jaswinder Pal Singh , John L. Hennessy , Anoop Gupta, Scaling Parallel Programs for Multiprocessors: Methodology and Examples, Computer, v.26 n.7, p.42-50, July 1993
	Ignacio Martín , Francisco Tirado, Relationships Between Efficiency and Execution Time of Full Multigrid Methods on Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.8 n.6, p.562-573, June 1997
	X. H. Sun , D. T. Rover, Scalability of Parallel Algorithm-Machine Combinations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.6, p.599-613, June 1994
	Selim G. Akl, Superlinear Performance in Real-Time Parallel Computation, The Journal of Supercomputing, v.29 n.1, p.89-111, July 2004
	Leonard Kleinrock , Jau-Hsiung Huang, On Parallel Processing Systems: Amdahl's Law Generalized and Some Results on Optimal Design, IEEE Transactions on Software Engineering, v.18 n.5, p.434-447, May 1992
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	Xian-He Sun , Jianping Zhu, Performance Considerations of Shared Virtual Memory Machines, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1185-1194, November 1995
	Ananth Y. Grama , Anshul Gupta , Vipin Kumar, Isoefficiency: Measuring the Scalability of Parallel Algorithms and Architectures, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.3, p.12-21, August 1993
	Melissa C. Smith , Gregory D. Peterson, Parallel application performance on shared high performance reconfigurable computing resources, Performance Evaluation, v.60 n.1-4, p.107-125, May 2005
	Krishna P. C. Madhavan , Laura L. Arns , Gary R. Bertoline, A Distributed Rendering Environment for Teaching Animation and Scientific Visualization, IEEE Computer Graphics and Applications, v.25 n.5, p.32-38, September 2005
	Ilya Sharapov , Robert Kroeger , Guy Delamarter , Razvan Cheveresan , Matthew Ramsay, A case study in top-down performance estimation for a large-scale parallel application, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA
	Uri Lublin , Dror G. Feitelson, The workload on parallel supercomputers: modeling the characteristics of rigid jobs, Journal of Parallel and Distributed Computing, v.63 n.11, p.1105-1122, November 2003
	Victor E. Bazterra , Martin Cuma , Marta B. Ferraro , Julio C. Facelli, A general framework to understand parallel performance in heterogeneous clusters: analysis of a new adaptive parallel genetic algorithm, Journal of Parallel and Distributed Computing, v.65 n.1, p.48-57, January 2005
	José Fridman , Elias S. Manolakos, On the Scalability of 2-D Discrete Wavelet Transform Algorithms, Multidimensional Systems and Signal Processing, v.8 n.1-2, p.185-217, Jan. 1997
	Xiaodong Zhang, Performance Measurement and Modeling to Evaluate Various Effects on a Shared memory Multiprocessor, IEEE Transactions on Software Engineering, v.17 n.1, p.87-93, January 1991
	Anshul Gupta , Vipin Kumar , Ahmed Sameh, Performance and Scalability of Preconditioned Conjugate Gradient Methods on Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.5, p.455-469, May 1995
	S. Q. Zheng , Balaji Calidas , Yanjun Zhang, An Efficient General In-Place Parallel Sorting Scheme, The Journal of Supercomputing, v.14 n.1, p.5-17, July 1999
	Mark D. Hill, What is scalability?, ACM SIGARCH Computer Architecture News, v.18 n.4, p.18-21, Dec. 1990
	James Donald , Margaret Martonosi, Power efficiency for variation-tolerant multicore processors, Proceedings of the 2006 international symposium on Low power electronics and design, October 04-06, 2006, Tegernsee, Bavaria, Germany
	Xizhou Feng , Kirk W. Cameron , Duncan A. Buell, Biology---PBPI: a high performance implementation of Bayesian phylogenetic inference, Proceedings of the 2006 ACM/IEEE conference on Supercomputing, November 11-17, 2006, Tampa, Florida
	Mashhuda Glencross , Alan G. Chalmers , Ming C. Lin , Miguel A. Otaduy , Diego Gutierrez, Exploiting perception in high-fidelity virtual environments Additional presentations from the 24th course are available on the citation page , ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts
	Bradley J. Barnes , Barry Rountree , David K. Lowenthal , Jaxk Reeves , Bronis de Supinski , Martin Schulz, A regression-based approach to scalability prediction, Proceedings of the 22nd annual international conference on Supercomputing, June 07-12, 2008, Island of Kos, Greece
	Huijuan Zhang , Timothy S. Newman, Efficient Parallel Out-of-core Isosurface Extraction, Proceedings of the 2003 IEEE Symposium on Parallel and Large-Data Visualization and Graphics, p.3, October 20-21, 2003
	Eduardo Javier Huerta Yero , Marco Aurélio Amaral Henriques, Speedup and scalability analysis of Master--Slave applications on large heterogeneous clusters, Journal of Parallel and Distributed Computing, v.67 n.11, p.1155-1167, November, 2007
	Dominik Henrich, Fast Motion Planning by Parallel Processing – a Review, Journal of Intelligent and Robotic Systems, v.20 n.1, p.45-69, September 1997
	Jing Du , Xuejun Yang , Zhiyuan Wang, Effective runtime scalability metric to measure productivity in high performance computing systems, Proceedings of the 2008 conference on Computing frontiers, May 05-07, 2008, Ischia, Italy
	Haim Mendelson, Laws, computer, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003
	Dejiang Jin , Sotirios G. Ziavras, Robust scalability analysis and SPM case studies, The Journal of Supercomputing, v.43 n.3, p.199-223, March 2008

INDEX TERMS

Primary Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**

Additional Classification:
C. Computer Systems Organization
C.4 PERFORMANCE OF SYSTEMS
Subjects: Measurement techniques

General Terms:
Performance, Theory

REVIEW

"Michael Wolfe : Reviewer"

This short technical note could just as well have been entitled “Validity of the multiple-processor approach to achieving large-scale computing capabilities.” Amdahl's law states that given any problem of fixed size, a certain percen more...

Collaborative Colleagues:

John L. Gustafson: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player

Additional presentations from the 24th course are available on the citation page