Abstract
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 language | English (US) |
|---|---|
| Title of host publication | ICS 1991 - Proceedings of the 5th International Conference on Supercomputing |
| Editors | Edward S. Davidson, Friedel Hossfield |
| Publisher | Association for Computing Machinery |
| Pages | 396-405 |
| Number of pages | 10 |
| ISBN (Print) | 0897914341, 9780897914345 |
| State | Published - Jun 1 1991 |
| Event | 5th International Conference on Supercomputing, ICS 1991 - Cologne, Germany Duration: Jun 17 1991 → Jun 21 1991 |
Publication series
| Name | Proceedings of the International Conference on Supercomputing |
|---|
Other
| Other | 5th International Conference on Supercomputing, ICS 1991 |
|---|---|
| Country/Territory | Germany |
| City | Cologne |
| Period | 6/17/91 → 6/21/91 |
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.