Article

Free access

Another view on parallel speedup

Authors:

Xian-He Sun,

Lionel M. NiAuthors Info & Claims

Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing

Pages 324 - 333

Published: 01 October 1990 Publication History

PDF eReader

Abstract

In this paper three models of parallel speedup are studied. They are fixed-size speedup, fixed-time speedup and memory-bounded speedup. Two sets of speedup formulations are derived for these three models. One set requires more information and gives more accurate estimation. Another set considers a simplified case and provides a clear picture of possible performance gain of parallel processing. The simplified fixed-size speedup is Amdahl's law. The simplified fixed-time speedup is Gustafson's scaled speedup. The simplified memory-bounded speedup contains both Amdahl's law and Gustafson's scaled speedup as its special cases. This study proposes a new metric for performance evaluation and leads to a better understanding of parallel processing.

References

[1]

A. H. Karp and H. P. Flatt, "Measuring parallel processor performance," CA CM, vol. 33, pp. 539-543, May 1990.

Digital Library

Google Scholar

[2]

J. Ortega and It. Voigt, "Solution of partial differential equations on vector and parallel computers," SIAM Review, june 1985.

Crossref

Google Scholar

[3]

M. Barton and G. Withers, "Computing performance as a function of the speed, quantity, and cost of the processors," in Proc. Supercomputing'S9, pp. 759-764, 1989.

Digital Library

Google Scholar

[4]

G. Amdahl, "Validity of the single-processor approch to achieving large scale computing capabilities," in Proc. AFIPS Conf., pp. 483-485, 1967.

Google Scholar

[5]

J. Gustafson, Reevaluating amdahl's law," CACM, vol. 31, pp. 523-533, May 1988.

Digital Library

Google Scholar

[6]

J. Gustafson, G. Montry, and R. Benner, "Development of parallel methods for a 1024- processor hypercube," SIAM J. on S3TC, vol. 9, July 1988.

Google Scholar

[7]

A. Veen, "Dataflow machine architectures," A CM Cornp. Surv., pp. 365-396, Dec. 1986.

Digital Library

Google Scholar

[8]

E. Coffman, "Introduction to deterministic scheduling theory." Computer and Job/Shop Scheduling Theory, 1976. ed. E.G. Coffman, John Wiley and Sons.

Google Scholar

[9]

M. A. Marsan, G. Bailbo, and G. Conte, "A class of generalized stochastic petri nets for the performance analysis of multiproceasor systems," A CM TOCS, pp. 93-122, May 1984.

Digital Library

Google Scholar

[10]

D. Eager, J. Zahorjan, and E. Lazowska, "Speedup versus efficiency in parallel system," IEEE TC, pp. 403-423, March 1989.

Digital Library

Google Scholar

[11]

M. Kumar, "Measuring parallelism in computation intensive scientific/engineering applications," IEEE-TC, vol. 37, pp. 1088-1098, Sep. 1988.

Digital Library

Google Scholar

[12]

X.-H. Sun, "Parallel computation models for scientific computing on multicomputers." Ph.D. Dissertation, Computer Science Department, Michigan State University, 1990. In preparation.

Google Scholar

[13]

K. Sevcik, "Characterizations of parallelism in applications and their use in scheduling," in Proc. of A CM SIGMETRICg and Performance'89, May 1989.

Digital Library

Google Scholar

[14]

J. Gustafson, "Fixed time, tiered memory, and superlinear speedup," in Proc. of the Fifth Conf. on Distributed Memory Computers, 1990. to appear.

Google Scholar

Cited By

View all

Loghin DTeo Y(2018)The Energy Efficiency of Modern Multicore SystemsWorkshop Proceedings of the 47th International Conference on Parallel Processing10.1145/3229710.3229714(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3229710.3229714
Yu QHuang LQian CMa JWang Z(2018)FC-AMATInnovations in Systems and Software Engineering10.1007/s11334-018-0313-x14:2(143-156)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11334-018-0313-x
Li HXu XWang MLi CRen XYang X(2017)Insertion of PETSc in the OpenFOAM FrameworkACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/30988212:3(1-19)Online publication date: 8-Aug-2017
https://dl.acm.org/doi/10.1145/3098821
Show More Cited By

Index Terms

Another view on parallel speedup
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Parallel speedup estimates for serial programs
Speedup for Multi-Level Parallel Computing
IPDPSW '12: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum

This paper studies the speedup for multi-level parallel computing. Two models of parallel speedup are considered, namely, fixed-size speedup and fixed-time speedup. Based on these two models, we start with the speedup formulation that takes into account ...
Estimating the Speedup in Parallel Parsing

A method for estimating the speedup for asynchronous bottom-up parallel parsing is presented. Two models for bottom-up parallel parsing are proposed, and the speedup for each of the two models is estimated. The speedup obtained for model A is a very ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Supercomputing '90: Proceedings of the 1990 ACM/IEEE conference on Supercomputing

November 1990

982 pages

ISBN:0897914120

Co-chairs:
Daniel V. Pryor
Supercomputing Research Center
,
Gary Montry
Myrias Computer Corporation
,
General Chair:
Joanne L. Martin
IBM Corporation

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 October 1990

Check for updates

Qualifiers

Article

Conference

SC '90

Sponsor:

SIGARCH
IEEE-CS

SC '90: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 16, 1990

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
906
Total Downloads

Downloads (Last 12 months)94
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Loghin DTeo Y(2018)The Energy Efficiency of Modern Multicore SystemsWorkshop Proceedings of the 47th International Conference on Parallel Processing10.1145/3229710.3229714(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3229710.3229714
Yu QHuang LQian CMa JWang Z(2018)FC-AMATInnovations in Systems and Software Engineering10.1007/s11334-018-0313-x14:2(143-156)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11334-018-0313-x
Li HXu XWang MLi CRen XYang X(2017)Insertion of PETSc in the OpenFOAM FrameworkACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/30988212:3(1-19)Online publication date: 8-Aug-2017
https://dl.acm.org/doi/10.1145/3098821
Yu QHuang LQian CWang ZGiorgi RBecchi MPalumbo F(2017)BC-AMATProceedings of the Computing Frontiers Conference10.1145/3075564.3076264(230-236)Online publication date: 15-May-2017
https://dl.acm.org/doi/10.1145/3075564.3076264
Liu YSun X(2017)Evaluating the Combined Effect of Memory Capacity and Concurrency for Many-Core Chip DesignACM Transactions on Modeling and Performance Evaluation of Computing Systems10.1145/30389152:2(1-25)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/3038915
Liu YSun XKern JVetter J(2015)C2-boundProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/2807591.2807641(1-11)Online publication date: 15-Nov-2015
https://dl.acm.org/doi/10.1145/2807591.2807641
Liu YWang S(2015)A scalable parallel genetic algorithm for the Generalized Assignment ProblemParallel Computing10.1016/j.parco.2014.04.00846:C(98-119)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.parco.2014.04.008
Sun XWang D(2012)APCACM SIGMETRICS Performance Evaluation Review10.1145/2381056.238108240:2(125-130)Online publication date: 8-Oct-2012
https://dl.acm.org/doi/10.1145/2381056.2381082
Juurlink BMeenderinck C(2012)Amdahl's law for predicting the future of multicores considered harmfulACM SIGARCH Computer Architecture News10.1145/2234336.223433840:2(1-9)Online publication date: 31-May-2012
https://dl.acm.org/doi/10.1145/2234336.2234338
Sun XWang DJarvis S(2011)Memory access cycle and the measurement of memory systemsProceedings of the second international workshop on Performance modeling, benchmarking and simulation of high performance computing systems10.1145/2088457.2088474(25-26)Online publication date: 13-Nov-2011
https://dl.acm.org/doi/10.1145/2088457.2088474
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Parallel speedup estimates for serial programs

Speedup for Multi-Level Parallel Computing

Estimating the Speedup in Parallel Parsing