Analysis of scalability of parallel algorithms and architectures: A survey

Vipin Kumar, Anshul Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations


The scalability of a parallel algorithm on a parallel architecture is a measure of its capability to effectively utilize an increasing number of processors. The scalability analysis may be used to select the best algorithm-architecture combination for a problem under different constraints on the growth of the problem size and the number of processors. It may be used to predict the performance of a parallel algorithm and a parallel architecture for a large number of processors from the known performance on fewer processors. For a fixed problem size it may be used to determine the optimal number of processors to be used and the maximum possible speedup for that problem size. The objective of this paper is to critically assess the state of the art in the theory of scalability analysis, and motivate further research on the development of new and more comprehensive analytical tools to study the scalability of parallel algorithms and architectures. We survey a number of techniques and formalisms that have been developed for studying the scalability issues, and discuss their interrelationships.

Original languageEnglish (US)
Title of host publicationICS 1991 - Proceedings of the 5th International Conference on Supercomputing
EditorsEdward S. Davidson, Friedel Hossfield
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)0897914341, 9780897914345
StatePublished - Jun 1 1991
Event5th International Conference on Supercomputing, ICS 1991 - Cologne, Germany
Duration: Jun 17 1991Jun 21 1991

Publication series

NameProceedings of the International Conference on Supercomputing


Other5th International Conference on Supercomputing, ICS 1991

Bibliographical note

Funding Information:
*This work was supported by Army Research Office grant # 28408-MA-SDI to the University of Minnesota and by the Army High Performance Computing Research Center at the University of Minnesota. An extended version of this paper is available from the authors upon request.

Publisher Copyright:
© 1991 ACM.


Dive into the research topics of 'Analysis of scalability of parallel algorithms and architectures: A survey'. Together they form a unique fingerprint.

Cite this