  In high performance computing environments, we observe an ongoing increase in
the available numbers of cores. This development calls for re-emphasizing
performance (scalability) analysis and speedup laws as suggested in the
literature (e.g., Amdahl's law and Gustafson's law), with a focus on asymptotic
performance. Understanding speedup and efficiency issues of algorithmic
parallelism is useful for several purposes, including the optimization of
system operations, temporal predictions on the execution of a program, and the
analysis of asymptotic properties and the determination of speedup bounds.
However, the literature is fragmented and shows a large diversity and
heterogeneity of speedup models and laws. These phenomena make it challenging
to obtain an overview of the models and their relationships, to identify the
determinants of performance in a given algorithmic and computational context,
and, finally, to determine the applicability of performance models and laws to
a particular parallel computing setting. In this work, we provide a generic
speedup (and thus also efficiency) model for homogeneous computing
environments. Our approach generalizes many prominent models suggested in the
literature and allows showing that they can be considered special cases of a
unifying approach. The genericity of the unifying speedup model is achieved
through parameterization. Considering combinations of parameter ranges, we
identify six different asymptotic speedup cases and eight different asymptotic
efficiency cases. Jointly applying these speedup and efficiency cases, we
derive eleven scalability cases, from which we build a scalability typology.
Researchers can draw upon our typology to classify their speedup model and to
determine the asymptotic behavior when the number of parallel processing units
increases. In addition, our results may be used to address various extensions
of our setting.
