X. Zhang and Z. Xu
``Multiprocessor Scalability Predictions
Through Detailed Program Execution Analysis"

in Proceedings of the 9th ACM International Conference on Supercomputing,
(ICS'95), July, 1995. (Best Paper Award)

Abstract
--------

Scalability measures the ability of a parallel system to improve performance
as the size of an application problem and the number of processors involved
increase. There are some limits to existing scalability studies.
First, the problem size in a computation is not well-defined.
Second, the methods used to differentiate algorithmic and
architectural scalabilities are not effective enough.
Thirdly, most approaches to scalability study are either highly
time-consuming or restricted to simple problem/architecture structures.
A major effort of this work  is to address these limits.
We have extended the latency metric for more complex scaling of
problems, and to possibly isolate the scalability
of an algorithm from a parallel system.
The scalability prediction is based on a semi-empirical approach
that significantly  reduces the time and cost of measurements and simulation.
Our prediction results were validated on the KSR-1 and on the CM-5.