kumar@uunet.UU.NET (Vipin Kumar) (05/18/91)
The following reports/papers on scalability analysis
can be obtained by sending mail to
US Mail: Dr. Vipin Kumar
Computer science Department
University of Minnesota
Minneapolis, MN 55455
Tel: 612-624-8023
Arpanet: kumar@cs.umn.edu
FAX:612-625-0572
Analyzing Scalability of Parallel Algorithms and Architectures
by Vipin Kumar and Anshul Gupta
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.
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 that can be obtained.
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 scalability issues, and discuss their interrelationships.
We point out some of the weaknesses of the existing schemes,
and discuss possible ways of extending them.
A short version of the above report appears in the proceedings
of the 1991 International Conference on Supercomputing,
Cologne, Germany, June 1991
------------------------
Other reports/papers on scalability analysis:
Scalability of Parallel Algorithms for the All-Pairs Shortest Path problems.
by Vipin Kumar and Vineet Singh.
To appear in Journal of Parallel and Distributed
Processing (special issue on massively parallel computation), 1991
On the scalability of FFT on parallel computers.
by Anshul Gupta and Vipin Kumar.
Proceedings of the Frontiers 90 Conference on Massively
Parallel Computation, October 1990.
An extended version paper is available as a technical report
from Army High Performance Computing Research Center,
University of Minnesota, Minneapolis,
MN 55455.
Scalability of parallel sorting on mesh multicomputers.
by Vineet Singh, Vipin Kumar, Gul Agha, and Chris Tomlinson.
Proceedings of the Fifth International Parallel Processing
Symposium, March 1991.
An Extended version available as a technical report (number TR 90-45)
from the department of computer science, University of Minnesota,
Minneapolis, MN 55455.