# Speedup and efficiency of computational parallelization:
A unifying approach and asymptotic analysis

Guido Schryen<EMAIL_ADDRESS>
Management Information Systems and Operations Research (MISOR, www.misor.org)
Paderborn University, Germany

###### Abstract

In high performance computing environments, we observe an ongoing increase in
the available numbers of cores. For example, the current TOP500 list reveals
that nine clusters have more than 1 million 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 suggested
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 and extended in future research to address various
extensions of our setting.

##  1 Introduction

Parallel computing has become increasingly relevant to tackle hard
computational problems in a variety of scientific disciplines and industrial
fields. The large diversity and deployment of parallel computing across
disciplines, including artificial intelligence, arts and humanities, computer
science, digital agriculture, earth and environmental sciences, economics,
engineering, health sciences, mathematics, and natural sciences, is mirrored
in usage statistics published by supercomputer clusters (e.g., [25, 20]). This
ongoing progress in computational sciences through parallelization has been
fostered through the end of exponential growth in single processor core
performance [14] and the availability of high performance computing (HPC)
infrastructures, tools, libraries, and services as commodity goods offered by
computing centers of universities, public cloud providers, and open source
communities..

Beyond these developments, the number of cores available as parallel
processing units has increased substantially over the past years. While the
statistics of the TOP500 list (as of June 2022) shows values of 35,339.2 (10th
percentile), 67,328 (median), and 225,465.6 (90th percentile), the
corresponding values of the lists as of June 2017 and June 2012 amount to
(16,545.6; 36,000; 119,808) and (6,776; 13,104; 37,036.8), respectively [35].
In addition, in contrast to the lists of 2012 and 2017, which both include
only one site with more than 1 million cores, the current list shows that nine
clusters have more than 1 million cores. This enormous growth in the number of
cores which are available for parallel processing calls for re-emphasizing
asymptotic performance analysis (e.g., [8, 3]) and speedup laws as suggested
in the literature (e.g., Amdahl’s law [4] and Gustafson’s law [16]).

In general, studying performance of algorithmic parallelism is useful for
several purposes; these include optimizing system operations via design-time
and run-time management (e.g., [17, 41, 37, 40, 9]), making temporal
predictions on the execution of a program (e.g., [29, 1]), and analyzing
asymptotic speedup and efficiency properties as well as determining speedup
and efficiency bounds (e.g., [32, 8]). In this article, we focus on the two
latter purposes, which have been addressed only rarely in the literature.

Analyzing performance of parallel algorithms is challenging as it needs to
account for diversity in several regards. For example, existing speedup models
and laws make different assumptions with respect to the
homogeneity/heterogeneity of parallel processing units, variations of
workloads, and methodological characteristics and application fields of
algorithms (e.g., optimization, data analytics, simulation). This
heterogeneity has resulted in a landscape of many speedup models and laws,
which, in turn, makes it difficult 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.

Our focus lies on the development of a generic and unifying speedup and
efficiency model for homogeneous parallel computing environments. We consider
a range of determinants of speedup covered in the literature and prove that
existing speedup laws can be derived from special cases of our model. Our
model depends neither on specific system architectures, such as symmetric
multiprocessing (SMP) systems or graphics processing units (GPU), nor on
software properties, such as critical regions; we rather perform a theoretical
analysis. We further focus on the analysis of asymptotic properties of the
suggested model to study speedup and efficiency limits and bounds in the light
of a computing future with an increasing number of parallel processing units.

Our results contribute to research on the performance (in terms of
scalability) of computational parallelization in homogeneous computing
environments in several regards: (1) We suggest a generic speedup and
efficiency model which accounts for a variety of conditions under which
parallelization occurs so that it is broadly applicable. This wide scope
allows conducting performance analysis in many of those cases which are not
covered by existing models and laws with restrictive assumptions. (2) We
generalize the fragmented landscape of speedup and efficiency models and
results, and we provide a unifying speedup and efficiency model which allows
overcoming the perspective of conflicting speedup models by showing that these
models can be interpreted as special cases of a more universal model; (3) From
our asymptotic analysis, we derive a typology of scalability (speedup and
efficiency), which researchers may use to classify their speedup model and/or
to determine the asymptotic behavior of their particular application. We also
provide a theoretical basis for explaining sublinear, linear and superlinear
speedup and efficiency and for deriving speedup and efficiency bounds in the
presence of an enormous growth of the number of available parallel processing
units. To sum up, we consolidate prior research on performance in homogeneous
parallel computing environments and we provide a theoretical understanding of
quantitative effects of various determinants of asymptotic performance in
parallel computing.

The remainder of the article is structured as follows: In Section 2, we
provide a brief overview of the foundations of speedup and efficiency analysis
in parallel computing. We proceed in Section 3 with the suggestion of a
generic speedup and efficiency model. In Section 4, we perform a mathematical
analysis of our model in order to determine theoretical speedup and efficiency
limits. We discuss the application of the suggested scalability typology in
Section 5 before we provide conclusions of our research in Section 6.

##  2 Foundations of speedup and efficiency analysis

The main purpose of parallel computation is to take advantage of increased
processing power to solve problems faster or to achieve better solutions. The
former goal is referred to as scalability, and scalability measures fall into
two main groups: speedup and efficiency. Speedup $S(N)$ is defined as the
ratio of sequential computation time $T(1)$ to parallel computation time
$T(N)$ needed to process a task with given workload when the parallel
algorithm is executed on $N$ parallel processing units (PUs) (e.g., cores in a
multicore processor architecture); i.e.,

$S(N):=\frac{T(1)}{T(N)},\;T:\mathbb{N}\rightarrow R^{>0}$ (1)

The sequential computation time $T(1)$ can be measured differently, leading to
different interpretations of speedup [5]: When $T(1)$ refers to the fastest
serial time achieved on any serial computer, speedup is denoted as absolute.
Alternatively, it may also refer to the time required to solve a problem with
the parallel program on one of the parallel PUs. This type of speedup is
qualified as relative. In this work, we focus on relative speedup.

As speedup relates the time required to process a given workload on a single
PU to the time required to process the same workload on $N$ PUs, we need to
determine this workload. It is usually divided into two sub-workloads, the
sequential workload and the parallelizable workload. While the former is
inherently sequential and necessarily needs to be executed on a single PU, the
latter can be executed in parallel on several PUs. Independent of the number
of available parallel PUs $N$, the time required to solve a task is the sum of
the time to handle the sequential workload and the time to handle the
parallelizable workload of the given task. When only a single PU is available,
the time for the sequential workload $s$ and for the parallelizable workload
$p$ are usually normalized by setting $s+p=1$; i.e., $s$ and $p$ represent the
sequential and the parallelizable fractions of the overall execution time.

For some applications, it is useful to consider a fixed workload (e.g., when
solving an instance of an optimization problem), which is independent of the
number of parallel PUs ($N$) available, and then to analyze how computation of
the fixed workload on a single PU can be speeded up by using multiple PUs.
Speedup models of this type are referred to as fixed-size models, such as
Amdahl’s law [4]. For other applications (e.g., when analyzing data), is more
appropriate to use the availability of $N$ PUs to solve tasks with workloads
which increase depending on $N$. Then, scalability analysis deals with
investigating how computation of the variable workload on one PU can be
speeded up by using multiple PUs. Speedup models of that type are referred to
as scaled-size models, such as Gustafson’s law [16].

With varying number of PUs $N$, both the sequential and parallelizable
workload may be considered scalable. It is common in the literature to
introduce two workload scaling functions $f(\cdot),g(\cdot)$ with
$f,g:\mathbb{N}\rightarrow R^{>0}$ for the sequential and parallelizable
workload, respectively; i.e.; the (normalized) time to process the sequential
and the parallelizable workload on a single PU are $s\cdot f(N)$ and $p\cdot
g(N)$, respectively. Thus, the (normalized) time to process the overall
workload on a single PU amounts to $s\cdot f(N)+p\cdot g(N)$. Usually, it is
assumed that $f(1)=g(1)=1$ so that $T(1)=s+p=1$ holds; however, our workload
scaling functions do not require to meet this assumption.111The option to have
values $f(1)\neq 1$ and/or $g(1)\neq 1$ allows scaling both fractions $s$ and
$p$, which may be useful when an overall workload to be executed on a machine
$A$ (with $p+s=1$) is now executed on a different machine $B$ on which the
times to execute the serial and the parallelizable workload are scaled at
either the same or different rates. An example of using a scaling function for
the sequential workload can be found in the scaled speedup model suggested by
Schmidt et al. [31, p. 31ff]. While scaling functions for sequential workloads
can be found only rarely, scaling functions for parallelizable workloads are
much more common; see, for example, the scale-sized speedup model of Gustafson
[16], the memory-bound speedup model of Sun and Ni [33, 34, 32], the
generalized scaled speedup model of Juurlink and Meenderinck [19] and the
scaled speedup model of Schmidt et al. [31, p. 31ff]. A discussion of the
relationship between problem size and the number of PUs $N$ can be found in
[36, p. 32f].

While the time required to process the sequential workload is independent of
the number of PUs $N$, the time required to process the parallelizable
workload depends on $N$ as this workload can be processed in parallel.
Usually, the parallelizable workload is considered to be equally distributed
on $N$ PUs, resulting in the (normalized) time $\frac{p\cdot g(N)}{N}$ to
handle the parallelizable workload. However, there are tasks possible when the
time required to handle the parallelizable workload is affected due to its
actual parallel execution; for example, when a mathematical optimization
problem, such as a mixed-inter linear program (MILP), is solved with a
parallelized branch-and-bound algorithm, then good bounds may be found early
so that the branch-and-bound tree does not grow as large as with the
sequential execution of the branch-and-bound algorithm. This effect may result
in a denominator function which is not identical to $N$ and allows explaining
superlinear speedup as it has been observed in the literature (e.g., [30, 11,
15]). We account for this effect with a scaling function $h(\cdot)$, with
$h:\mathbb{N}\rightarrow R^{>0}$.

Finally, processing one single large task on several parallel PUs involves
some sort of overhead, which is often rooted in initialization, communication,
and synchronization efforts [38, 18, 13]. We account for the additional time
required for these efforts with an overhead function $z(\cdot)$,
$z:\mathbb{N}\rightarrow R^{>0}$.

The abovementioned workloads and temporal effects are visualized in Figure 1.
The resulting general speedup equation is the given by

$S(N)=\frac{T(1)}{T(N)}=\frac{s\cdot f(1)+p\cdot g(1)}{s\cdot
f(N)+\frac{p\cdot g(N)}{h(N)}+z(N)}\;,N\in\mathbb{N}$ (2)

Figure 1: Workloads and temporal effects of parallelization

Note that the speedup equation given in (2) is a generalization of several
well known speedup models, including those used in Amdahl’s law [4] (set
$f(N)=g(N)=1,h(N)=N,z(N)=0$), Gustafson’s law [16] (set
$f(N)=1,g(N)=h(N)=N,z(N)=0$), and the generalized scaled speedup model [19]
(set $f(N)=1,g(N)=N^{0.5},h(N)=N,z(N)=0$).

Based upon speedup $S(N)$, efficiency $E(N)$ relates speedup to the number of
parallel PUs used to achieve this speedup, and it is defined by

$E(N)=\frac{S(N)}{N}=\frac{T(1)}{N\cdot T(N)}=\frac{s\cdot f(1)+p\cdot
g(1)}{N\cdot(s\cdot f(N)+\frac{p\cdot g(N)}{h(N)}+z(N))}\;,N\in\mathbb{N}$ (3)

##  3 A generic speedup and efficiency model

Based upon the general speedup equation (2), we derive a generic speedup and
efficiency model, which we use in the remainder of this article to analyze its
asymptotic behavior. The generic speedup model uses power functions for
$f(\cdot),g(\cdot),h(\cdot)$ and ignores any overhead induced through
parallelization. The use of power functions is widely adopted in the
literature, included in many prominent speedup models [4, 16, 31, 34, 19] and
is based on the assumption that many algorithms have a polynomial complexity
in terms of computation and memory requirement [32, p. 184]. As we focus on
the analysis of the asymptotic behavior, we always take the highest degree
term. The motivation for neglecting any parallelization overhead (i.e.,
$z(N)=0\;\forall N\in\mathbb{N}$), as it is done in many, if not most speedup
and efficency models in the literature, is manifold: First, the overhead is
often unknown. Second, omitting an overhead term simplifies computations and
provides a basis for developing laws which include an overhead function
$z(N)\neq 0$. Third, speedup and efficiency values determined without
considering overhead represent upper bounds for practically achievable speedup
and efficiency values when overhead occurs.

We use the following power functions:

$f(N):=c_{f}N^{\alpha_{f}}\qquad g(N):=c_{g}N^{\alpha_{g}}\qquad
h(N):=c_{h}N^{\alpha_{h}},\qquad
c_{f},c_{g},c_{h}>0,\;\alpha_{f},\alpha_{g},\alpha_{h}\geq 0$ (4)

and yield the following generic speedup equation (for $N>1$)222The
applicability of this speedup equation to $N=1$ would require setting
$c_{h}=1$. In order to allow using an arbitrary coefficient in the power
function $h(\cdot)$, we require $N$ to be larger than $1$.

$S(N)=\frac{s\cdot f(N)+p\cdot g(N)}{s\cdot f(N)+\frac{p\cdot
g(N)}{h(N)}+z(N)}=\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}+p\cdot c_{g}\cdot
N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{\alpha_{f}}+\frac{p\cdot c_{g}\cdot
N^{\alpha_{g}}}{c_{h}\cdot N^{\alpha_{h}}}}=\frac{s\cdot c_{f}\cdot
N^{\alpha_{f}}+p\cdot c_{g}\cdot N^{\alpha_{g}}}{s\cdot c_{f}\cdot
N^{\alpha_{f}}+\frac{p\cdot c_{g}}{c_{h}}\cdot N^{(\alpha_{g}-\alpha_{h})}}$
(5)

and the following efficiency equation (for $N>1$):

$E(N)=\frac{S(N)}{N}=\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}+p\cdot c_{g}\cdot
N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{(\alpha_{f}+1)}+\frac{p\cdot
c_{g}}{c_{h}}\cdot N^{(\alpha_{g}-\alpha_{h}+1)}}$ (6)

The generic speedup equation given in (5) generalizes several well-known
speedup equations and laws suggested in the literature (see Table 1).

Table 1: Instantiations of generic speedup model Parameter values | Speedup equation |  Speedup model or law
---|---|---
$c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=\alpha_{g}=0$ | $S(N)=\frac{s+p}{s+\frac{p}{N}}$ |  Amdahl’s law [4]
$c_{f}=c_{g}=c_{h}=\alpha_{g}=\alpha_{h}=1,\alpha_{f}=0$ | $S(N)=\frac{s+p\cdot N}{s+p}$ |  Gustafson’s law [16]
$c_{h}=\alpha_{h}=1$ | $S(N)=\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}+p\cdot c_{g}\cdot N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{\alpha_{f}}+p\cdot c_{g}\cdot N^{(\alpha_{g}-1)}}$ |  Scaled speedup model [31]
|  |  (under the assumption that the sequential and parallel workloads are given by power functions $c_{f}\cdot N^{\alpha_{f}}$ and $c_{g}\cdot N^{\alpha_{g}}$, resp.)
$c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0$ | $S(N)=\frac{s+p\cdot N^{\alpha_{g}}}{s+p\cdot N^{(\alpha_{g}-1)}}$ |  Sun and Ni’s law [33, 34]
|  |  (under the assumption that the parallel workload is given by a power function $N^{\alpha_{g}}$)
$c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}=\frac{1}{2}$ | $S(N)=\frac{s+p\cdot N^{\frac{1}{2}}}{s+\frac{p}{N^{\frac{1}{2}}}}$ |  Generalized scaled speedup model [19]

##  4 Theoretical speedup and efficiency limits

###  4.1 Asymptotic speedup

As we are interested in asymptotic speedup, we determine limits for
$N\rightarrow\infty$. We rewrite the generic speedup equation (5) as follows:

$S(N)=\underbrace{\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}}{s\cdot c_{f}\cdot
N^{\alpha_{f}}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h})}}}_{\begin{subarray}{c}(I)\end{subarray}}+\underbrace{\frac{p\cdot
c_{g}\cdot N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{\alpha_{f}}+\frac{p\cdot
c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h})}}}_{\begin{subarray}{c}(II)\end{subarray}}$ (7)

For term (I), we yield the following limits (the proof can be obtained from
equations (34)-(37) in Appendix A):

$\displaystyle 1$ $\displaystyle,\;\alpha_{f}>\alpha_{g}-\alpha_{h}$ (8)
$\displaystyle\frac{s\cdot c_{f}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-\alpha_{h}$ (9) $\displaystyle 0$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-\alpha_{h}$ (10)

For term (II), we yield the following limits (the proof can be obtained from
equations (38) - (46) in Appendix A):

$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}}$
$\displaystyle,\;\alpha_{g}=\alpha_{f},\alpha_{h}>0$ (11)
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{g}=\alpha_{f},\alpha_{h}=0$ (12) $\displaystyle 0$
$\displaystyle,\;\alpha_{g}<\alpha_{f}$ (13)
$\displaystyle\infty\;(\Theta(N^{\alpha_{h}}))$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}\geq
0$ (14) $\displaystyle\infty\;(\Theta(N^{(\alpha_{g}-\alpha_{f})}))$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}<0$
(15) $\displaystyle c_{h}$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}=0$ (16)

Aggregating the above given limits for terms (I) and (II), yields the
following limits for the speedup given in equations (5) and (7):

$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}}+1=\frac{p\cdot c_{g}+s\cdot
c_{f}}{s\cdot c_{f}}$ $\displaystyle,\;\alpha_{g}=\alpha_{f},\alpha_{h}>0$
(17) $\displaystyle(\Leftrightarrow 0=\alpha_{g}-\alpha_{f}<\alpha_{h})$
$\displaystyle\frac{s\cdot c_{f}}{s\cdot c_{f}+\frac{p\cdot
c_{g}}{c_{h}}}+\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot
c_{g}}{c_{h}}}=\frac{s\cdot c_{f}+p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot
c_{g}}{c_{h}}}$ $\displaystyle,\;\alpha_{g}=\alpha_{f},\alpha_{h}=0$ (18)
$\displaystyle(\Leftrightarrow 0=\alpha_{g}-\alpha_{f}=\alpha_{h})$
$\displaystyle 1+0=1$ $\displaystyle,\;\alpha_{g}<\alpha_{f}$ (19)
$\displaystyle(\Leftrightarrow\alpha_{g}-\alpha_{f}<0)$
$\displaystyle\infty\;(\Theta(N^{\alpha_{h}}))$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}\geq
0$ (20) $\displaystyle(\Leftrightarrow 0<\alpha_{h}\leq\alpha_{g}-\alpha_{f})$
$\displaystyle\infty\;(\Theta(N^{(\alpha_{g}-\alpha_{f})}))$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}<0$
(21) $\displaystyle(\Leftrightarrow 0<\alpha_{g}-\alpha_{f}<\alpha_{h})$
$\displaystyle 0+c_{h}=c_{h}$
$\displaystyle,\;\alpha_{g}>\alpha_{f},\alpha_{h}=0$ (22)
$\displaystyle(\Leftrightarrow 0=\alpha_{h}<\alpha_{g}-\alpha_{f})$

We now briefly discuss each of the six equations and refer to these as speedup
cases; a visual illustration of the speedup cases can be retrieved from Figure
2.

Figure 2: Overview of speedup limits

  * Case $A_{S}$:

The speedup limit given in eq. (17) represents an upper bound for
$S(N)\;\forall N>1$ (see Appendix A) and refers to situations in which the
number $N$ of available PUs affects the time required to address the
parallelizable workload (due to $\alpha_{h}>0$). While the speedup limit holds
for any $c_{h},\alpha_{h}>0$, it seems reasonable to assume that
$h(N)=c_{h}\cdot N^{\alpha_{h}}\geq 1$ holds as increasing the number of PUs
from $N=1$ to $N>1$ should not lead to an increase of time required to execute
the parallelizable workload. However, the speedup limit in this case does not
depend on the values of $c_{h}$ and $\alpha_{h}$. Also, this case assumes that
the scaling functions $f(N)=c_{f}\cdot N^{\alpha_{f}}$ and $g(N)=c_{g}\cdot
N^{\alpha_{g}}=c_{g}\cdot N^{\alpha_{f}}$ change the serial and parallelizable
workloads using the same factor $N^{\alpha_{f}}$. It should be noticed that
case $A_{S}$ results in Amdahl’s law [4] when setting
$c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=\alpha_{g}=0$; then, the limit on
speedup amounts to $\frac{1}{s}$. As the speedup model of Amdahl’s law is a
special case of the memory-bound model suggested in [33, 34] (Sun and Ni’s
law) under the assumption that the parallelizable workload in the memory-bound
model is given by a power function $N^{\alpha_{g}}$, case $A_{S}$ partly
covers the abovementioned model. This case also (partly) covers the scaled
workload model of Schmidt et al. [31] under the assumption that the sequential
and parallelizable workloads are given by power functions $c_{f}\cdot
N^{\alpha_{f}}$ and $c_{g}\cdot N^{\alpha_{g}}$, resp., with
$\alpha_{f}=\alpha_{g}$.

  * Case $B_{S}$:

The speedup limit given in eq. (18) represents an upper bound for
$S(N)\;\forall N>1$ (see Appendix A). It refers to the same situation as
described in case $A_{S}$ with the modification that, here, $N$ does not
affect the time required to address the parallelizable workload (due to
$\alpha_{h}=0$); that time is rather modified through a division by the scalar
$c_{h}$; i.e., when executing the parallelizable workload in parallel, the
corresponding time changes are determined by a constant factor $\alpha_{h}$.
It seems reasonable to assume that $c_{h}\geq 1$ holds in this case (cmp. the
analogeous discussion of case $A_{S}$), with a resulting speedup limit of
$\lim_{N\rightarrow\infty}S(N)\geq 1$. While case $B_{S}$ seems not useful
under the premise that the parallelizable workload is infintely
parallelizable, it becomes useful when this assumption is replaced by the
expectation that a given parallelizable workload can be executed in parallel
only on a limited number $N_{max}$ PUs; then, $\alpha_{h}$ may represent this
limitation. For a discussion of limited parallelization, see, for example,
[10, p. 772ff] and [3, p. 141ff]).

  * Case $C_{S}$:

When the increase of serial workload is asymptotically higher than that of
parallelizable workload ($\alpha_{f}>\alpha_{g}$), speedup converges against
$1$ (see eq. (19)) as a lower bound regardless of the values of $c_{h}$ and
$\alpha_{h}$; i.e., in this case, any parallelization does not reduce the
overall execution time asymptotically due to the “dominant”’ increase of the
serial workload. Case $C_{S}$ (partly) covers the scaled workload model of
Schmidt et al. [31] under the assumption that the sequential and
parallelizable workloads are given by power functions $c_{f}\cdot
N^{\alpha_{f}}$ and $c_{g}\cdot N^{\alpha_{g}}$, resp., with
$\alpha_{f}<\alpha_{g}$.

  * Case $D_{S}$:

This case covers situations in which speedup is not limited and increases
asymptotically with $\Theta(N^{\alpha_{h}})$ for (i) $\alpha_{g}>\alpha_{f}$,
(ii) $\alpha_{h}>0$, and (iii) $\alpha_{g}-\alpha_{h}\geq\alpha_{f}$ (see eq.
(20)); (i) ensures that the parallelizable workload increases faster than the
sequential workload, (ii) ensures that parallelization asymptotically reduces
the time required to execute the parallelizable workload, and (iii) ensures
that the temporal effect induced through the joint growth of the
parallelizable workload and its actual parallel execution
($N^{(\alpha_{g}-\alpha_{h})}$) is not weaker than the temporal effect induced
through the growth of the sequential workload ($N^{\alpha_{f}}$). Depending on
the value of $\alpha_{h}$, speedup asymptotically grows sublinearly
($0<\alpha_{h}<1$), linearly ($\alpha_{h}=1$), or superlinearly
($\alpha_{h}>1$). It should be noticed that case $D_{S}$ results in
Gustafson’s law [16] when setting
$c_{f}=c_{g}=c_{h}=\alpha_{g}=\alpha_{h}=1,\alpha_{f}=0$; then, the speedup
asypmtotically grows linearly. Case $D_{S}$ (partly) cover Sun and Ni’s law
when setting $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}\geq 1$
(under the assumption that the parallelizable workload in this model is given
by a power function $N^{\alpha_{g}}$). Finally, case $D_{S}$ (partly) covers
the scaled workload model of Schmidt et al. [31] under the assumption that the
sequential and parallelizable workloads are given by power functions
$c_{f}\cdot N^{\alpha_{f}}$ and $c_{g}\cdot N^{\alpha_{g}}$, resp., with
$\alpha_{g}-\alpha_{f}\geq 1$.

Interestingly, case $D_{S}$ may help explaining superlinear speedup as is has
been observed in research on mathematical optimization (at least for a limited
range of $N$) [27, 6, 30, 15], for example.

  * Case $E_{S}$:

Similar to case $D_{S}$, case $E_{S}$ refers to situations in which speedup is
not limited and increases asymptotically, but now with
$\Theta(N^{(\alpha_{g}-\alpha_{f})})$ for (i) $\alpha_{g}>\alpha_{f}$, (ii)
$\alpha_{h}>0$, and (iii) $\alpha_{g}-\alpha_{h}<\alpha_{f}$ (see eq. (21)).
The conditions under which case $E_{S}$ differ from those in case $D_{S}$ only
with regard to (iii); i.e., here, the temporal effect induced through the
joint growth of the parallelizable workload and its actual parallel execution
($N^{(\alpha_{g}-\alpha_{h})}$) is weaker than the temporal effect induced
through the growth of the sequential workload ($N^{\alpha_{f}}$). Now, the
difference $(\alpha_{g}-\alpha_{f})$ determines the asymptotic growth of
speedup: it asymptotically grows sublinearly ($0<\alpha_{g}-\alpha_{f}<1$),
linearly ($\alpha_{g}-\alpha_{f}=1$), or superlinearly
($\alpha_{g}-\alpha_{f}>1$).

Similarly to case $D_{S}$, case $E_{S}$ (partly) includes speedup models and
laws suggested in the literature: Case $E_{S}$ (partly) covers Sun and Ni’s
law when setting $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}<1$
(under the assumption that the parallelizable workload in this model is given
by a power function $N^{\alpha_{g}}$). With $\alpha_{g}=\frac{1}{2}$, Sun and
Ni’s model becomes the “generalized scaled speedup” model suggested in [19];
thus, case $E_{S}$ also covers the generalized scaled speedup model. Finally,
case $E_{S}$ also (partly) includes the model of Schmidt et al. [31] under the
assumption that the sequential and parallelizable workloads are given by power
functions $c_{f}\cdot N^{\alpha_{f}}$ and $c_{g}\cdot N^{\alpha_{g}}$, resp.,
with $0<\alpha_{g}-\alpha_{f}<1$); then, speedup grows asymptotically
sublinearly with $\Theta(N^{(\alpha_{g}-\alpha_{f})})$.

As case $D_{S}$, also case $E_{S}$ may help explaining superlinear speedup.

  * Case $F_{S}$:

This case covers situations in which speedup converges to $c_{h}$ for (i)
$\alpha_{g}>\alpha_{f}$ and (ii) $\alpha_{h}=0$ (see eq. (22)). For $c_{h}\geq
1$, the limit $c_{h}$ is a lower bound; for $c_{h}\leq 1$, the limit $c_{h}$
is an upper bound. Condition (i) ensures that the parallelizable workload
increases faster than the sequential workload, and with condition (ii) we
assume that $N$ does not affect the time required to address the
parallelizable workload (due to $\alpha_{h}=0$). As with case $B_{S}$, case
$F_{S}$ is useful with the expectation that a given parallelizable workload
can be executed in parallel only on a limited number $N_{max}$ of PUs.

###  4.2 Asymptotic efficiency

In order to determine theoretical efficiency limits, we proceed analogously to
the determination of speedup limits. We rewrite the generic efficiency
equation (eq. (6)) as follows:

$E(N)=\underbrace{\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}}{s\cdot c_{f}\cdot
N^{(\alpha_{f}+1)}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h}-1)}}}_{\begin{subarray}{c}(I^{\prime})\end{subarray}}+\underbrace{\frac{p\cdot
c_{g}\cdot N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{(\alpha_{f}+1)}+\frac{p\cdot
c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h}+1)}}}_{\begin{subarray}{c}(II^{\prime})\end{subarray}}$
(23)

For term (I’), we yield the following limit (see equations (47) - (49) in
Appendix B):

$\lim_{N\rightarrow\infty}(I^{\prime})=0$ (24)

For term (II’), we yield the following limits (the proof can be obtained from
equations (50) - (62) in Appendix B):

$\displaystyle 0$ $\displaystyle,\;\alpha_{f}>\alpha_{g}-1$ (25)
$\displaystyle(\Leftrightarrow\alpha_{g}-\alpha_{f}<1)$ $\displaystyle 0$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,0\leq\alpha_{h}<1$ (26)
$\displaystyle(\Leftrightarrow 0\leq\alpha_{h}<\alpha_{g}-\alpha_{f}=1)$
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,\alpha_{h}=1$ (27)
$\displaystyle(\Leftrightarrow\alpha_{g}-\alpha_{f}=\alpha_{h}=1)$
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,\alpha_{h}>1$ (28)
$\displaystyle(\Leftrightarrow\alpha_{g}-\alpha_{f}=1<\alpha_{h})$
$\displaystyle 0$ $\displaystyle,\;\alpha_{f}<\alpha_{g}-1,0\leq\alpha_{h}<1$
(29) $\displaystyle(\Leftrightarrow 0<\alpha_{h}<1<\alpha_{g}-\alpha_{f})$
$\displaystyle c_{h}$ $\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}=1$
(30) $\displaystyle(\Leftrightarrow 1=\alpha_{h}<\alpha_{g}-\alpha_{f})$
$\displaystyle\infty\;(\Theta(N^{\alpha_{g}-\alpha_{f}-1}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}>\alpha_{g}-\alpha_{h}$
(31) $\displaystyle(\Leftrightarrow 1<\alpha_{g}-\alpha_{f}<\alpha_{h})$
$\displaystyle\infty\;(\Theta(N^{\alpha_{h}-1}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}\leq\alpha_{g}-\alpha_{h}$
(32) $\displaystyle(\Leftrightarrow 1<\alpha_{h}\leq\alpha_{g}-\alpha_{f})$

With $\lim_{N\rightarrow\infty}(I^{\prime})=0$, we yields the following limits
for efficiency equations (6) and (23):

$\lim_{N\rightarrow\infty}E(N)=\lim_{N\rightarrow\infty}\left[(I^{\prime})+(II^{\prime})\right]=\lim_{N\rightarrow\infty}(II^{\prime})$
(33)

We now briefly discuss each of the eight equations and refer to these as
(efficiency) cases; a visual illustration of the efficiency cases can be
retrieved from Figure 3 which, unsurprisingly, shows structural similarities
with the visual representation of speedup limits due to the relationship
between efficiency and speedup as given by $E(N)=\frac{S(N)}{N}$.

  * Case $A_{E}$:

The efficiency limit given in eq. (25) equals zero regardless of the value of
$\alpha_{h}$ and apparently represents a lower bound for $E(N)\;\forall N>1$.
This case refers to a situation in which the increase of the serial workload
is asymptotically higher than that of a(n) (adjusted) parallelizable workload
(adjusted based upon a decrease of the number of PUs by $1$)
($\alpha_{f}>\alpha_{g}-1$).

  * Case $B_{E}$:

The efficiency limit given in eq. (26) equals zero when the value of
$\alpha_{h}$ is upper bounded by $1$. Again, it apparently represents a lower
bound for $E(N)\;\forall N>1$. This case refers to a situation in which the
ratio of the increases of serial workload and adjusted parallelizable workload
converges against the constant $\frac{c_{f}}{c_{g}}$ and in which the increase
of time reduction of executing the parallelizable workload is sublinear in $N$
($\alpha_{h}<1$).

  * Case $C_{E}$:

The efficiency limit given in eq. (27) describes a situation that differs from
that in case $B_{E}$ only in that the increase of time reduction of executing
the parallelizable workload is now linear in $N$ ($\alpha_{h}=1$). Then, the
limit of efficiency is given by a constant larger than $0$ assuming that the
parallelizable workload is positive ($p>0$).

  * Case $D_{E}$:

The efficiency limit given in eq. (28) describes a situation that differs from
that in case $B_{E}$ only in that the increase of time reduction of executing
the parallelizable workload is now superlinear in $N$ ($\alpha_{h}>1$).
Despite this increase of time reduction and due to the relatively large
increase of the serial workload compared to that of the parallelizable
workload ($\alpha_{f}=\alpha_{g}-1$), the limit of efficiency is still given
by a constant (larger than $0$) assuming that the parallelizable workload is
positive ($p>0$).

  * Case $E_{E}$:

The efficiency limit given in eq. (29) describes a situation that is similar
to that of case $B_{E}$. While $\alpha_{h}<1$ holds again, the (adjusted and
the non-adjusted) parallelizable workload grows faster than the serial
workload ($\alpha_{f}<\alpha_{g}-1$). However, as the increase of time
reduction of executing the parallelizable workload is sublinear in $N$
($\alpha_{h}<1$), efficiency converges against $0$.

  * Case $F_{E}$:

In contrast to case $E_{S}$, the efficiency limit given in eq. (30) describes
a situation in which the increase of time reduction of executing the
parallelizable workload is linear in $N$ ($\alpha_{h}=1$). Then, efficiency
asymptotically equals a constant larger than $0$ (assuming $p>0$).

  * Case $G_{E}$:

One situation in which efficiency is unbounded is decribed in eq. (31), where
the (adjusted and the non-adjusted) parallelizable workload grows faster than
the serial workload ($\alpha_{f}<\alpha_{g}-1$) and the increase of time
reduction of executing the parallelizable workload is superlinear in $N$
($\alpha_{h}>1$). When also $\alpha_{f}>\alpha_{g}-\alpha_{h}$ holds,
efficiency grows asymptotically with $\Theta(N^{\alpha_{g}-\alpha_{f}-1})$;
i.e., the asymptotic growth does not depend on $\alpha_{h}$. For
$\alpha_{g}-\alpha_{f}>1$, $\alpha_{g}-\alpha_{f}=1$ and
$\alpha_{g}-\alpha_{f}<1$, efficiency is superlinear, linear and sublinear,
respectively.

  * Case $H_{E}$:

A second situation in which efficiency is unbounded is decribed in eq. (32),
where the (adjusted and the non-adjusted) parallelizable workload grows faster
than the serial workload ($\alpha_{f}<\alpha_{g}-1$) and the increase of time
reduction of executing the parallelizable workload is superlinear in $N$
($\alpha_{h}>1$). When also $\alpha_{f}\leq\alpha_{g}-\alpha_{h}$ holds,
efficiency grows asymptotically with $\Theta(N^{\alpha_{h}-1})$; i.e., the
asymptotic growth does now depend on $\alpha_{h}$. For $\alpha_{h}>1$,
$\alpha_{h}=1$ and $0<\alpha_{h}<1$, efficiency is superlinear, linear and
sublinear, respectively.

Figure 3: Overview of efficiency limits

###  4.3 Asymptotic scalability

In the previous subsections, we identify speedup cases and efficiency cases.
Now, we consider speedup cases and efficiency cases jointly, which results in
various speedup-efficiency cases. We refer to these cases as scalability
cases, which are defined by both speedup and efficiency limits (see Table 2
and Figure 4). We assign to each scalability case a scalabilty type, which
describes both speedup (as first parameter) and efficiency (as second
parameter), using the following semantics:

  * •

$\beta_{h},\gamma_{h}$: fixed values which depend on the reduced parallel
workload scaling function $h$

  * •

$\infty_{f,g}$: unbounded and monotonically increasing; the extent of increase
depends on workload scaling functions $f$ and $g$

  * •

$\beta_{s,f,g},\gamma_{s,f,g}$: fixed values which depend on the sequential
part $s$ (note: $p=1-s$) and the workload scaling functions $f$ and $g$

  * •

$\beta_{s,f,g,h},\gamma_{s,f,g,h}$: fixed values which depend on the
sequential part $s$ (note: $p=1-s$), the workload scaling functions $f$ and
$g$, and the reduced parallel workload scaling function $h$

  * •

$\infty_{f,g}$: unbounded and monotonically increasing; the extent of increase
depends on workload scaling functions $f$ and $g$

  * •

$\infty_{h}$: unbounded and monotonically increasing; the extent of increase
depends on reduced parallel workload scaling function $h$

Figure 4: Overview of scalability cases

Each scalability type refers to exactly one scalability case and set of
conditions (see Table 2).

Table 2: Scalability cases Cases | Limit values | Type |  Conditions
---|---|---|---
Scalability | Speedup | Efficiency | Speedup∗ | Efficiency∗∗
$A_{SC}$ | $C_{S}$ | $A_{E}$ | $1$ | $0$ | $(1/0)$ |  $\alpha_{g}-\alpha_{f}<0$
$B_{SC}$ | $A_{S}$ | $A_{E}$ | $\beta:=\frac{s\cdot c_{f}+p\cdot c_{g}}{s\cdot c_{f}}>1$ | $0$ | $(\beta_{s,f,g}/0)$ |  $0=\alpha_{g}-\alpha_{f}<\alpha_{h}$
$C_{SC}$ | $B_{S}$ | $A_{E}$ | $\beta:=\frac{s\cdot c_{f}+p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$ | $0$ | $(\beta_{s,f,g,h}/0)$ |  $0=\alpha_{g}-\alpha_{f}=\alpha_{h}$
$D_{SC}$ | $F_{S}$ |  $E_{E}$, $B_{E}$ | $\beta:=c_{h}$ | $0$ | $(\beta_{h}/0)$ |  $0=\alpha_{h}<\alpha_{g}-\alpha_{f}$
$E_{SC}$ | $D_{S}$ |  $E_{E}$, $B_{E}$ | $\infty\left(\Theta(N^{\alpha_{h}})\right)$ | $0$ | $(\infty_{h}/0)$ |  $0<\alpha_{h}<1\leq\alpha_{g}-\alpha_{f}$
$F_{SC}$ | $H_{E}$ | $\infty\left(\Theta(N^{(\alpha_{h}-1)})\right)$ | $(\infty_{h}/\infty_{h})$ |  $1<\alpha_{h}\leq\alpha_{g}-\alpha_{f}$
$G_{SC}$ | $C_{E}$ | $\gamma:=\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$ | $(\infty_{h}/\gamma_{s,f,g,h})$ |  $\alpha_{h}=\alpha_{g}-\alpha_{f}=1$
$H_{SC}$ | $F_{E}$ | $\gamma:=c_{h}$ | $(\infty_{h}/\gamma_{h})$ |  $1=\alpha_{h}<\alpha_{g}-\alpha_{f}$
$I_{SC}$ | $E_{S}$ | $G_{E}$ | $\infty\left(\Theta(N^{(\alpha_{g}-\alpha_{f})})\right)$ | $\infty\left(\Theta(N^{(\alpha_{g}-\alpha_{f}-1)}\right)$ | $(\infty_{f,g}/\infty_{f,g})$ |  $1<\alpha_{g}-\alpha_{f}<\alpha_{h}$
$J_{SC}$ | $A_{E}$ | $0$ | $(\infty_{f,g}/0)$ |  $0<\alpha_{g}-\alpha_{f}<\min{\left\\{1,\alpha_{h}\right\\}}$
$K_{SC}$ | $D_{E}$ | $\gamma:=\frac{p\cdot c_{g}}{s\cdot c_{f}}$ | $(\infty_{f,g}/\gamma_{s,f,g})$ |  $1=\alpha_{g}-\alpha_{f}<\alpha_{h}$
∗: Values for cases $A_{S}$ and $B_{S}$ are upper bounds, value for case
$C_{S}$ is lower bound, value for case $F_{S}$ is lower bound ($c_{h}\geq 1$)
or upper bound ($c_{h}\leq 1$).
∗∗: Values for cases $A_{E}$ to $G_{E}$ are lower bounds, the value for case
$H_{E}$ is an upper bound (for sufficiently large values of $N$ ($c_{h}\cdot
N\geq 1$)).

For the discussion of speedup, efficiency and scalability results derived in
the preceding section, we recall the meaning of parameters $\alpha_{f}$,
$\alpha_{g}$ and $\alpha_{b}$ since their values determine the (speedup,
efficiency and scalability) case of a particular parallel algorithm: The
parameters $\alpha_{f}$, $\alpha_{g}$ and $\alpha_{h}$ affect the serial
workload, the parallelizable workload and the actual reduction of
parallelizable workload through parallelization, respectively, depending on
the number of PUs $N$; they are given by $f(N):=c_{f}N^{\alpha_{f}}$,
$g(N):=c_{g}N^{\alpha_{g}}$ and $c_{h}N^{\alpha_{h}}$, respectively. We also
recall the abovementionded speedup and efficiency equations:

$S(N)=\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}+p\cdot c_{g}\cdot
N^{\alpha_{g}}}{s\cdot c_{f}\cdot N^{\alpha_{f}}+\frac{p\cdot
c_{g}}{c_{h}}\cdot N^{(\alpha_{g}-\alpha_{h})}}\;\text{(see eq.
(\ref{eq:genericSpeedupEquation}))}$ $E(N)=\frac{s\cdot c_{f}\cdot
N^{\alpha_{f}}+p\cdot c_{g}\cdot N^{\alpha_{g}}}{s\cdot c_{f}\cdot
N^{(\alpha_{f}+1)}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h}+1)}}\;\text{(see eq.
(\ref{eq:genericEfficiencyEquation}))}$

We now discuss each of the eleven scalability cases $A_{SC}$ to $K_{SC}$. As
the definition of scalability cases (and types) is based upon combinations of
speedup cases and efficiency cases, the characteristics of scalability cases
(and types) can be derived from the above descriptions of the characteristics
of speedup and efficiency cases.

  * Case $A_{SC}$:

With speedup case $C_{S}$, the increase of serial workload is asymptotically
higher than that of parallelizable workload ($\alpha_{f}>\alpha_{g}$). Then,
speedup converges against $1$. Case $C_{S}$ induces efficiency class $A_{E}$
so that the resulting asymptotic efficiency equals $0$. The scalability type
is $(1,0)$. Overall, parallelization does not scale at all and parallelization
efforts do not make much sense.

  * Case $B_{SC}$:

With speedup case $A_{S}$, the scaling functions $f$ and $g$ change the serial
and parallelizable workloads using the same factor $N^{\alpha_{f}}$ with
possibly different values $c_{f}$ and $c_{g}$; furthermore, case $A_{S}$
refers to situations in which the number $N$ of available PUs affects the time
required to address the parallelizable workload (due to $\alpha_{h}>0$). Then,
speedup converges against a constant $\beta_{s,f,g}=\frac{s\cdot
c_{f}+(1-s)\cdot c_{g}}{s\cdot c_{f}}>1$. Speedup case $A_{S}$ leads to
efficiency case $A_{E}$; i.e., efficiency converges against zero.

Scalability case $B_{SC}$, which refers to scalability type
$(\beta_{s,f,g},0)$, includes Amdahl’s law [4] and partly Sun and Ni’s law
[33, 34] (see the discusssion of speedup case $A_{S}$).

  * Case $C_{SC}$:

This scalability case is similar to scalability case $B_{SC}$ and differs from
it only as $\alpha_{h}$ equals zero; i.e., $N$ does not affect the time
required to address the parallelizable workload. With speedup case $B_{S}$ and
resulting efficiency case $A_{E}$, the associated scalability type is
$(\beta_{s,f,g,h},0)$, with speedup $\beta_{s,f,g,h}=\frac{s\cdot
c_{f}+(1-s)\cdot c_{g}}{s\cdot c_{f}+\frac{(1-p)\cdot c_{g}}{c_{h}}}$. As
discussed above, speedup case $B_{S}$, and thus scalability case $C_{SC}$, are
not useful under the premise that the parallelizable workload is infintely
parallelizable, but it becomes useful when a given parallelizable workload can
be executed in parallel only on a limited number of PUs.

  * Case $D_{SC}$:

Scalability case $D_{SC}$, which corresponds to scalability type
$(\beta_{h}/0)$, includes speedup case $F_{S}$, in which the parallelizable
workload increases faster than the sequential workload
($\alpha_{g}>\alpha_{f}$) and $N$ does not affect the time required to address
the parallelizable workload ($\alpha_{h}=0$). Then, speedup converges to
$c_{h}$. When speedup case $F_{S}$ applies, either efficiency case $E_{E}$ or
$B_{E}$ applies with efficency converging towards zero in both cases. As with
scalability case $C_{SC}$, case $D_{SC}$ is useful with the expectation that a
given parallelizable workload can be executed in parallel only on a limited
number of PUs.

  * Case $E_{SC}$:

This scalability case refers to a situation in which (i) the parallelizable
workload increases at least one magnitude faster than the sequential workload
($\alpha_{g}\geq\alpha_{f}+1$) and (ii) the number of available PUs affects
the time required to address the parallelizable workload with unlimited and
sublinear growth ($0<\alpha_{h}<1$). This scalability case is linked to
speedup case $D_{S}$ and one of the efficiency cases $E_{E}$ or $B_{E}$,
resulting to scalability class ($\infty_{h},0$). Case $E_{SC}$ involves a
speedup growth of $\Theta(N^{\alpha_{h}})$; i.e., speedup convergence is
determined by the reduced parallel workload scaling function $h$. Due to the
condition $\alpha_{h}<1$, this growth is sublinearly in $N$ and efficiency
converges towards zero.

  * Case $F_{SC}$:

This case describes to a situation in which the parallelizable workload
increases more than one magnitude faster than the sequential workload
($\alpha_{g}\geq\alpha_{f}+1$) and the number of available PUs affects the
time required to address the parallelizable workload with superlinear growth
($1<\alpha_{h}\leq(\alpha_{g}-\alpha_{f}))$). Under such conditions, speedup
case $D_{S}$ and efficiency case $H_{E}$ apply, resulting in the scalability
type $(\infty_{h},\infty_{h})$, where both speedup and efficiency are
unlimited, speedup grows superlinearly with $\Theta(N^{\alpha_{h}})$, and
efficiency grows sublinearly (when $1<\alpha_{h}<2$), linearly (when
$\alpha_{h}=2$), or superlinearly (when $2<\alpha_{h}$).

  * Case $G_{SC}$:

This scalability case describes a situation in which the parallelizable
workload increases one magnitude faster than the sequential workload
($\alpha_{g}=\alpha_{f}+1$) and the number of available PUs affects the time
required to address the parallelizable workload with linear growth
$(\alpha_{h}=1$). Under such conditions, speedup case $D_{S}$ and efficiency
case $C_{E}$ apply, resulting in the scalability type
$(\infty_{h},\gamma_{s,f,g,h})$, where speedup is unlimited and grows linearly
and where efficiency converges against a constant $\gamma$ that depends upon
functions $f,g,h$ and upon $s$ ($\gamma_{s,f,g,h}=\frac{p\cdot c_{g}}{s\cdot
c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$).

Scalability case $G_{SC}$ covers Gustafson’s law [16], where
$\alpha_{g}=\alpha_{h}=1,\alpha_{f}=0$. It also (partly) covers the model of
Schmidt et al. [31].

  * Case $H_{SC}$:

Scalability case $H_{SC}$ differs from scalability case $G_{SC}$ only in the
regard that the parallelizable workload increases more than one magnitude
faster than the sequential workload ($\alpha_{g}>\alpha_{f}+1$). Similiar to
case $G_{SC}$, the scalability type is $(\infty_{h},\gamma_{h})$ but here
$\gamma_{h}$ is set to $c_{h}$ (efficiency case $F_{E}$).

Analogously to scalability case $G_{SC}$, also case $H_{SC}$ (partly) covers
the model of Schmidt et al. [31]. In addition, case $H_{SC}$ also (partly)
covers Sun and Ni’s law when $c_{f}=c_{g}=c_{h}=1$ holds and when the
parallelizable workload in this model is given by a power function
$N^{\alpha_{g}}$.

  * Case $I_{SC}$:

This scalability case applies when (i) the parallelizable workload increases
at least one magnitude faster than the sequential workload
($\alpha_{g}>\alpha_{f}+1$) and (ii) the number of available PUs affects the
time required to address the parallelizable workload with unlimited and
superlinear growth ($1<\alpha_{g}-\alpha_{f}<\alpha_{h}$). Under these
conditions, speedup case $E_{S}$ and efficiency case $G_{E}$ apply, leading to
scalability type $(\infty_{f,g},\infty_{f,g})$; i.e., both speedup and
efficiency are unbounded and grow superlinearly.

  * Case $J_{SC}$:

The conditions under which this case apply differ from those of case $I_{SC}$
in that the parallelizable workload increases less than one magnitude faster
than the sequential workload ($0<\alpha_{g}-\alpha_{f}<1$). Then, speedup case
$E_{S}$ and efficiency case $A_{E}$ apply, leading to scalability type
$(\infty_{f,g},0)$; i.e., while speedup is unbounded and grow sublinearly,
efficiency converges against zero.

With $\alpha_{f}=0,\alpha_{h}=1$, it partly covers Sun and Ni’s law, and with
$\alpha_{f}=0,\alpha_{g}=\frac{1}{2},\alpha_{h}=1$, it covers the speedup
model of Juurlink and Meenderinck [19].

  * Case $K_{SC}$:

When (i) the parallelizable workload increases one magnitude faster than the
sequential workload ($\alpha_{g}=\alpha_{f}+1$) and (ii) the number of
available PUs affects the time required to address the parallelizable workload
with unlimited and superlinear growth ($1<\alpha_{h}$), scalability case
$K_{SC}$ applies with speedup case $E_{S}$ and efficiency case $D_{E}$; then,
speedup is unlimited and grows linearly, efficiency converges against a
constant $\gamma=\frac{p\cdot c_{g}}{s\cdot c_{f}}$, and scalability type
$(\infty_{f,g},\gamma_{s,f,g})$ applies.

##  5 Discussion

The scalability typology developed in the previous section allows researchers
to determine the limits of speedup and efficiency of their applications and
the extent to which computational parallelization scales for their needs. They
also support researchers regarding their decision of how many parallel PUs to
use in the presence of economic budget constraints. Our typology shown in
Table 2 provides a more comprehensive picture of scalability in homogeneous
computing environments than speedup laws suggested in the literature (shown in
Table 1), thereby widening the scope of applying scalability insights. At the
same time, our typology includes all of the abovementioned speedup laws as
illustrated in Table 3.

Table 3: Scalability types of speedup models suggested in the literature Speedup model | Scalability case | Scalability type | Conditions
---|---|---|---
Amdahl’s law [4] | $B_{SC}$ | $(\beta_{s,f,g}=\frac{1}{s},0)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=\alpha_{g}=0$
Gustafson’s law [16] | $G_{SC}$ | $(\infty_{h},\gamma_{s,f,g,h}=1-s)$ | $c_{f}=c_{g}=c_{h}=\alpha_{g}=\alpha_{h}=1,\alpha_{f}=0$
Generalized scaled speedup model [19] | $J_{SC}$ | $(\infty_{f,g},0)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}=\frac{1}{2}$
Sun and Ni’s law [33, 34] | $B_{SC}$ | $(\beta_{s,f,g}=\frac{1}{s},0)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}=0$
| $G_{SC}$ | $(\infty_{h},\gamma_{s,f,g,h}=1-s)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}=1$
| $H_{SC}$ | $(\infty_{h},\gamma_{h}=1)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,\alpha_{g}>1$
| $J_{SC}$ | $(\infty_{f,g},0)$ | $c_{f}=c_{g}=c_{h}=\alpha_{h}=1,\alpha_{f}=0,0<\alpha_{g}<1$
Scaled speedup model [31] | $A_{SC}$ | $(1,0)$ | $c_{h}=\alpha_{h}=1,\alpha_{g}-\alpha_{f}<0$
| $B_{SC}$ | $(\beta_{s,f,g},0)$ | $c_{h}=\alpha_{h}=1,\alpha_{g}-\alpha_{f}=0$
| $G_{SC}$ | $(\infty_{h},\gamma_{s,f,g,h})$ | $c_{h}=\alpha_{h}=1,\alpha_{g}-\alpha_{f}=1$
| $H_{SC}$ | $(\infty_{h},\gamma_{h}=1)$ | $c_{h}=\alpha_{h}=1,\alpha_{g}-\alpha_{f}>1$
| $J_{SC}$ | $(\infty_{f,g},0)$ | $c_{h}=\alpha_{h}=1,0<\alpha_{g}-\alpha_{f}<1$

A key issue for researchers is the assignment of their particular application
to a scalability class, which requires determining the sequential workload $s$
and the power functions $f,g,h$ (see Definition 4). In order to determine $s$,
a straightforward approach is to execute the application on a single PU and
measure the execution times $t_{seq}$ ans $t_{par}$ of the sequential and
parallelizable workloads, resp., leading to
$s=\frac{t_{seq}}{t_{seq}+t_{par}}$ and $p=1-s$. The power functions $f$ and
$g$, which correspond to the problem size in terms of the sequential and
parallelizable workloads depending on the number $N$ of PUs, can be specified
by the researcher or are given by the particular application. For example,
when the application is concerned with processing and analyzing data, the
volume of data to be processed can be aligned to $N$. However, in an
optimization context when, for example, an instance of a mixed-integer linear
program needs to be solved to optimality with a branch-and-bound algorithm,
the size of the problem instance is fixed. With regard to the function $h$,
which allows adjusting the time required to handle the parallelizable workload
when this workload is actually executed in parallel, in many applications
researchers may find it appropriate to set $h(N)=N$, which assumes that the
parallelizable workload is equally distributed on $N$ PUs. However,
researchers may derive from this assumption when, for example, superlinear
speedup is observed in computational experiments. Ideally, $h$ can be derived
from algorithmic analysis; but in many cases this approach may not work and,
then, researchers are advised to determine $h$ with computational experiments.

##  6 Conclusion

In this work, we provide a generic speedup (and thus also efficiency) model,
which generalizes many prominent models suggested in the literature and allows
showing that they can be considered special cases with different assumptions
of a unifying approach. The genericity of the speedup model is achieved
through parameterization. Considering combinations of parameter ranges, we
identify six different asymptotic speedup cases and eight different asymptotic
efficiency cases; these cases include sublinear, linear and superlinear
speedup and efficiency. Based upon the identified speedup and efficiency
cases, we derive eleven different scalability cases and types, to which
instantiations of our generic speedup (and efficiency) model may lead.
Researchers can draw upon our suggested typology to classify their speedup
model and/or to determine asymptotic scalability of their application when the
number of parallel PUs increases.

Our theoretical analysis is based upon several assumptions which are common in
the literature (e.g., [34]). First, we assume that the overall workload only
contains two parts, a sequential part and a perfectly parallelizable part,
which can be executed in parallel on all available parallel PUs. In practice,
the latter condition may not always hold but even then our speedup and
efficiency results are useful as they can be used as upper bounds of
achievable speedup and efficiency. In the literature, alternative models which
do not require the abovementioned dichotom disctinction have been suggested,
including parallelism/span-and-work models, multiple-fraction models, and
roofline models (e.g., [10, p. 772ff], [3, p. 141ff]), [7]). Future
theoretical analysis of speedup and efficiency limits may consider those types
of models,

Second, while our generic speedup model includes a function for
parallelization overhead, we assume that this overhead is negligible and omit
this function from our analysis. However, we admit that parallelization
overhead may cause large scalability degradation [18] and have considerably
large effects on speedup and efficiency. Overhead can be rooted in several
phenomena, including the existence of critical regions (exclusive access for
one process only), inter-process communication, and sequential-to-parallel
synchronization due to data exchange [38]. While, in this case, speedup and
efficiency results can again be used as upper bounds of achievable speedup and
efficiency, future work should identify appropriate overhead functions and
complement asymptotic analysis with the analysis of speedup and efficiency
optima in order to determine the optimal number of parallel PUs to be used in
particular problem settings. In the literature, different ways to integrate
overhead functions into the determination of execution times have been
suggested. One option is the provision of additive terms as it has been done
for overhead of data preparation [26] or communication required for mapping a
workload onto multiple cores [21, 3]. A theoretical analysis of an additive
overhead function can be found in [13]. Another option involves adding a
coefficient function to the execution time of the parallelized workload (e.g.,
[12, 33]).

Third, in our analysis we focus on homogeneous parallel computing
environments. We acknowledge that, in modern parallel computing environments,
parallel processing units are not necessarily equally potential in their
computing capabilities and that a substantial body of literature on speedup in
such heterogeneous computing environments exist; see, for example, the surveys
on heterogeneous multicore environments of Al-Babtain et al. [2] and Al-
hayanni et al. [3]. Many works suggest extensions of Amdahl’s law, Gustafson’s
law and/or Sun and Ni’s Law for such environments (e.g., [17, 19, 39, 28, 42,
23, 22]). Studies on speedup and efficiency properties of architecture-
dependent laws are particularly helpful for the design of multi-core
environments. Future work may extend our generic speedup model by concepts of
different types of parallel PUs as suggested in the literature and adapt our
theoretical analysis to heterogeneous settings.

Finally, merging the two abovementioned research streams leads to the
consideration of speedup and efficiency in heterogeneous parallel computing
environments under the consideration of overhead (functions). Our model and
theoretical analysis may be extended in both regards, drawing on prior work.
For example, Huang et al. [18] suggest an extension of Amdahl’s law and
Gustafson’s law in architecture-specific multi-core settings by considering
communication overheads and area constraints; Pei et al. [26] extend Amdahl’s
law for heterogeneous multicore processors with the consideration of overhead
through data preparation; and Morad et al. [24] analyze overheads as a result
of synchronization, communication and coherence costs based upon Amdahl’s
model for asymmetric cluster chip multiprocessors.

With the suggestion of a generic and unifying speedup (and efficiency) model
and its asymptotic analysis, we hope to provide a theoretical basis for and
typology of scalability of parallel algorithms in homogeneous computing
environments. Future research can draw upon and extend our research results to
address various extensions of our setting.

## References

  * Ababei and Moghaddam [2018] C. Ababei and M. G. Moghaddam.  A survey of prediction and classification techniques in multicore processor systems.  _IEEE Transactions on Parallel and Distributed Systems_ , 30(5):1184–1200, 2018.
  * Al-Babtain et al. [2013] B. M. Al-Babtain, F. J. Al-Kanderi, M. F. Al-Fahad, and I. Ahmad.  A survey on amdahl’s law extension in multicore architectures.  _International Journal of New Computer Architectures and their Applications (IJNCAA)_ , 3(3):30–46, 2013.
  * Al-hayanni et al. [2020] M. A. N. Al-hayanni, F. Xia, A. Rafiev, A. Romanovsky, R. Shafik, and A. Yakovlev.  Amdahl’s law in the context of heterogeneous many-core systems–a survey.  _IET Computers & Digital Techniques_, 14(4):133–148, 2020.
  * Amdahl [1967] G. M. Amdahl.  Validity of the single processor approach to achieving large scale computing capabilities.  In _Proceedings of the April 18-20, 1967, spring joint computer conference_ , pages 483–485, 1967.
  * Barr and Hickman [1993] R. S. Barr and B. L. Hickman.  Reporting computational experiments with parallel algorithms: Issues, measures, and experts’ opinions.  _ORSA Journal on Computing_ , 5(1):2–18, 1993\.
  * Borisenko et al. [2011] A. Borisenko, P. Kegel, and S. Gorlatch.  Optimal design of multi-product batch plants using a parallel branch-and-bound method.  In _International Conference on Parallel Computing Technologies_ , pages 417–430. Springer, 2011.
  * Cassidy and Andreou [2011] A. S. Cassidy and A. G. Andreou.  Beyond amdahl’s law: An objective function that links multiprocessor performance gains to delay and energy.  _IEEE Transactions on Computers_ , 61(8):1110–1126, 2011.
  * Che and Nguyen [2014] H. Che and M. Nguyen.  Amdahl’s law for multithreaded multicore processors.  _Journal of Parallel and Distributed Computing_ , 74(10):3056–3069, 2014.  ISSN 0743-7315.  doi: https://doi.org/10.1016/j.jpdc.2014.06.012.  URL https://www.sciencedirect.com/science/article/pii/S0743731514001142.
  * Chen et al. [2018] J. Chen, C. Du, F. Xie, and B. Lin.  Scheduling non-preemptive tasks with strict periods in multi-core real-time systems.  _Journal of Systems Architecture_ , 90:72–84, 2018.
  * Cormen et al. [2022] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  _Introduction to algorithms_.  MIT press, 2022.
  * Dabah et al. [2022] A. Dabah, I. Chegrane, S. Yahiaoui, A. Bendjoudi, and N. Nouali-Taboudjemat.  Efficient parallel branch-and-bound approaches for exact graph edit distance problem.  _Parallel Computing_ , 114:102984, 2022.
  * Eyerman and Eeckhout [2010] S. Eyerman and L. Eeckhout.  Modeling critical sections in amdahl’s law and its implications for multicore design.  In _Proceedings of the 37th annual international symposium on Computer architecture_ , pages 362–370, 2010.
  * Flatt and Kennedy [1989] H. P. Flatt and K. Kennedy.  Performance of parallel processors.  _Parallel Computing_ , 12(1):1–20, 1989.
  * Fuller and Millett [2011] S. H. Fuller and L. I. Millett.  _The future of computing performance: game over or next level?_ National Academy Press, 2011.
  * Gonggiatgul et al. [2023] T. Gonggiatgul, G. Shobaki, and P. Muyan-Özçelik.  A parallel branch-and-bound algorithm with history-based domination and its application to the sequential ordering problem.  _Journal of Parallel and Distributed Computing_ , 172:131–143, 2023.  ISSN 0743-7315.  doi: https://doi.org/10.1016/j.jpdc.2022.10.007.  URL https://www.sciencedirect.com/science/article/pii/S0743731522002167.
  * Gustafson [1988] J. L. Gustafson.  Reevaluating amdahl’s law.  _Communications of the ACM_ , 31(5):532–533, 1988\.
  * Hill and Marty [2008] M. D. Hill and M. R. Marty.  Amdahl’s law in the multicore era.  _Computer_ , 41(7):33–38, 2008.
  * Huang et al. [2013] T. Huang, Y. Zhu, M. Qiu, X. Yin, and X. Wang.  Extending amdahl’s law and gustafson’s law by evaluating interconnections on multi-core processors.  _The Journal of Supercomputing_ , 66(1):305–319, 2013.
  * Juurlink and Meenderinck [2012] B. H. Juurlink and C. H. Meenderinck.  Amdahl’s law for predicting the future of multicores considered harmful.  _ACM SIGARCH Computer Architecture News_ , 40(2):1–9, 2012.
  * [20] Jülich Supercomputing Centre.  Research fields and geographic distribution of supercomputer users.  https://www.fz-juelich.de/en/ias/jsc/systems/supercomputers/user-research-fields-distribution.
  * Li and Malek [1988] X. Li and M. Malek.  Analysis of speedup and communication/computation ratio in multiprocessor systems.  In _Proceedings. Real-Time Systems Symposium_ , pages 282–283. IEEE Computer Society, 1988.
  * Moncrieff et al. [1996] D. Moncrieff, R. E. Overill, and S. Wilson.  Heterogeneous computing machines and amdahl’s law.  _Parallel Computing_ , 22(3):407–413, 1996.
  * Morad et al. [2012] A. Morad, T. Y. Morad, Y. Leonid, R. Ginosar, and U. Weiser.  Generalized multiamdahl: Optimization of heterogeneous multi-accelerator soc.  _IEEE Computer Architecture Letters_ , 13(1):37–40, 2012.
  * Morad et al. [2006] T. Y. Morad, U. C. Weiser, A. Kolodnyt, M. Valero, and E. Ayguade.  Performance, power efficiency and scalability of asymmetric cluster chip multiprocessors.  _IEEE Computer Architecture Letters_ , 5(1):14–17, 2006.
  * National Center for Supercomputing Applications [2021] National Center for Supercomputing Applications.  Pushing boundaries. farther.  https://www.ncsa.illinois.edu/research/, 2021.
  * Pei et al. [2016] S. Pei, M.-S. Kim, and J.-L. Gaudiot.  Extending amdahl’s law for heterogeneous multicore processor with consideration of the overhead of data preparation.  _IEEE Embedded Systems Letters_ , 8(1):26–29, 2016.
  * Ponz-Tienda et al. [2017] J. L. Ponz-Tienda, A. Salcedo-Bernal, and E. Pellicer.  A parallel branch and bound algorithm for the resource leveling problem with minimal lags.  _Computer-Aided Civil and Infrastructure Engineering_ , 32(6):474–498, 2017.
  * Rafiev et al. [2018] A. Rafiev, M. A. Al-Hayanni, F. Xia, R. Shafik, A. Romanovsky, and A. Yakovlev.  Speedup and power scaling models for heterogeneous many-core systems.  _IEEE Transactions on Multi-scale computing systems_ , 4(3):436–449, 2018.
  * Rai et al. [2010] J. K. Rai, A. Negi, R. Wankar, and K. Nayak.  Performance prediction on multi-core processors.  In _2010 International Conference on Computational Intelligence and Communication Networks_ , pages 633–637. IEEE, 2010.
  * Rauchecker and Schryen [2019] G. Rauchecker and G. Schryen.  Using high performance computing for unrelated parallel machine scheduling with sequence-dependent setup times: Development and computational evaluation of a parallel branch-and-price algorithm.  _Computers & Operations Research_, (104):338–357, 2019.
  * Schmidt et al. [2017] B. Schmidt, J. Gonzalez-Dominguez, C. Hundt, and M. Schlarb.  _Parallel programming: concepts and practice_.  Morgan Kaufmann, 2017.
  * Sun and Chen [2010] X.-H. Sun and Y. Chen.  Reevaluating amdahl’s law in the multicore era.  _Journal of Parallel and distributed Computing_ , 70(2):183–188, 2010.
  * Sun and Ni [1990] X.-H. Sun and L. M. Ni.  Another view on parallel speedup.  In _Proceedings of the 1990 ACM/IEEE conference on Supercomputing_ , pages 324–333, 1990.
  * Sun and Ni [1993] X.-H. Sun and L. M. Ni.  Scalable problems and memory-bounded speedup.  _Journal of Parallel and Distributed Computing_ , 19(1):27–37, 1993.
  * TOP500.org [2022] TOP500.org.  Top500.  https://www.top500.org/lists/top500/, 2022.
  * Trobec et al. [2018] R. Trobec, B. Slivnik, P. Bulic, and B. Robic.  _Introduction to Parallel Computing: From Algorithms to Programming on State-of-Art Platforms_.  Springer, 2018.
  * Xia et al. [2017] F. Xia, A. Rafiev, A. Aalsaud, M. Al-Hayanni, J. Davis, J. Levine, A. Mokhov, A. Romanovsky, R. Shafik, A. Yakovlev, et al.  Voltage, throughput, power, reliability, and multicore scaling.  _Computer_ , 50(8):34–45, 2017.
  * Yavits et al. [2014] L. Yavits, A. Morad, and R. Ginosar.  The effect of communication and synchronization on amdahl’s law in multicore systems.  _Parallel Computing_ , 40(1):1–16, 2014.
  * Ye et al. [2013] N. Ye, Z. Hao, and X. Xie.  The speedup model for manycore processor.  In _2013 International Conference on Information Science and Cloud Computing Companion_ , pages 469–474, 2013.  doi: 10.1109/ISCC-C.2013.146.
  * Zhuravlev et al. [2012] S. Zhuravlev, J. C. Saez, S. Blagodurov, A. Fedorova, and M. Prieto.  Survey of scheduling techniques for addressing shared resources in multicore processors.  _ACM Computing Surveys (CSUR)_ , 45(1):1–28, 2012\.
  * Zidenberg et al. [2012] T. Zidenberg, I. Keslassy, and U. Weiser.  Multiamdahl: How should i divide my heterogenous chip?  _IEEE Computer Architecture Letters_ , 11(2):65–68, 2012.
  * Zidenberg et al. [2013] T. Zidenberg, I. Keslassy, and U. Weiser.  Optimal resource allocation with multiamdahl.  _Computer_ , 46(07):70–77, 2013.

##  Appendix A Calculations of speedup limits

We rewrite (I) as follows:

$(I)=\frac{s\cdot c_{f}\cdot N^{\alpha_{f}}}{s\cdot c_{f}\cdot
N^{\alpha_{f}}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h})}}=\frac{s\cdot c_{f}}{s\cdot c_{f}+\frac{p\cdot
c_{g}}{c_{h}}\cdot N^{\alpha_{g}-\alpha_{h}-\alpha_{f}}}$ (34)

and obtain

$\displaystyle 1$ $\displaystyle,\;\alpha_{f}>\alpha_{g}-\alpha_{h}$ (35)
$\displaystyle\frac{s\cdot c_{f}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\alpha_{f}=\alpha_{g}-\alpha_{h}$ (36) $\displaystyle 0$
$\displaystyle,\alpha_{f}<\alpha_{g}-\alpha_{h}$ (37)

It should be noticed that, in contrast to the limits in equations (35) and
(36), which show upper bounds, the limit in equation (37) represents a lower
bound.

We rewrite (II) as follows:

$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}\cdot
N^{(\alpha_{f}-\alpha_{g})}+\frac{p\cdot c_{g}}{c_{h}\cdot N^{\alpha_{h}}}}$
$\displaystyle,\;\alpha_{f}>\alpha_{g}$ (38) $\displaystyle\frac{p\cdot
c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}\cdot N^{\alpha_{h}}}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}$ (39) $\displaystyle\frac{p\cdot
c_{g}\cdot N^{(\alpha_{g}-\alpha_{f})}}{s\cdot c_{f}+\frac{p\cdot
c_{g}}{c_{h}}\cdot c_{h}\cdot N^{(\alpha_{g}-\alpha_{h}-\alpha_{f})}}$
$\displaystyle,\;\alpha_{f}<\alpha_{g}$ (40)

For equation (38), we obtain

$\lim_{N\rightarrow\infty}(II)=0,\;\alpha_{f}>\alpha_{g}$ (41)

For equation (39), we obtain

$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g},\alpha_{h}>0$ (42)
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g},\alpha_{h}=0$ (43)

For equation (40), we obtain

$\displaystyle\lim_{N\rightarrow\infty}\frac{p\cdot c_{g}\cdot
N^{\alpha_{h}}}{\frac{s\cdot
c_{f}}{N^{(\alpha_{g}-\alpha_{h}-\alpha_{f})}}+\frac{p\cdot
c_{g}}{c_{h}}}=\infty\;(\Theta(N^{\alpha_{h}}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}\geq
0$ (44) $\displaystyle\lim_{N\rightarrow\infty}\frac{p\cdot c_{g}\cdot
N^{(\alpha_{g}-\alpha_{f})}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(\alpha_{g}-\alpha_{h}-\alpha_{f})}}=\infty\;(\Theta(N^{(\alpha_{g}-\alpha_{f})}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g},\alpha_{h}>0,\alpha_{g}-\alpha_{h}-\alpha_{f}<0$
(45) $\displaystyle\lim_{N\rightarrow\infty}\frac{p\cdot c_{g}}{\frac{s\cdot
c_{f}}{N^{(\alpha_{g}-\alpha_{f})}}+\frac{p\cdot c_{g}}{c_{h}}}=c_{h}$
$\displaystyle,\;\alpha_{f}<\alpha_{g},\alpha_{h}=0$ (46)

It should be noticed that, in contrast to the limits in equations (42), (43)
and (46), which show upper bounds, the limit in equation (41) represents a
lower bound.

##  Appendix B Calculations of efficiency limits

$\displaystyle 0$ $\displaystyle,\;\alpha_{g}-\alpha_{h}-\alpha_{f}+1>0$ (47)
$\displaystyle 0$ $\displaystyle,\;\alpha_{g}-\alpha_{h}-\alpha_{f}+1=0$ (48)
$\displaystyle 0$ $\displaystyle,\;\alpha_{g}-\alpha_{h}-\alpha_{f}+1<0$ (49)

It should be noticed that the limits in equations (47) to (49) all show lower
bounds.

We rewrite $(II^{\prime})$ as follows:

$\displaystyle\frac{p\cdot c_{g}\cdot N^{(\alpha_{g}-\alpha_{f}-1)}}{s\cdot
c_{f}+\frac{p\cdot c_{g}}{c_{h}}\cdot N^{(\alpha_{g}-\alpha_{h}-\alpha_{f})}}$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}\geq\alpha_{g}-\alpha_{h}$
(50) $\displaystyle\frac{p\cdot c_{g}\cdot N^{(\alpha_{h}-1)}}{\frac{s\cdot
c_{f}}{N^{(\alpha_{g}-\alpha_{f}-1)}}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}<\alpha_{g}-\alpha_{h}$
(51) $\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}\cdot
N^{(\alpha_{f}-\alpha_{g}+1)}+\frac{p\cdot c_{g}}{c_{h}}\cdot
N^{(-\alpha_{h}+1)}}$ $\displaystyle,\;\text{else}$ (52)

and obtain

$\displaystyle 0$ $\displaystyle,\;\alpha_{f}>\alpha_{g}-1,0\leq\alpha_{h}\leq
1$ (53) $\displaystyle 0$
$\displaystyle,\;\alpha_{f}>\alpha_{g}-1,\alpha_{h}>1$ (54) $\displaystyle 0$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,0\leq\alpha_{h}\leq 1$ (55)
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}+\frac{p\cdot c_{g}}{c_{h}}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,\alpha_{h}=1$ (56)
$\displaystyle\frac{p\cdot c_{g}}{s\cdot c_{f}}$
$\displaystyle,\;\alpha_{f}=\alpha_{g}-1,\alpha_{h}>1$ (57) $\displaystyle 0$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,0\leq\alpha_{h}<1$ (58)
$\displaystyle c_{h}$ $\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}=1$
(59) $\displaystyle\infty\;(\Theta(N^{\alpha_{g}-\alpha_{f}-1}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}>\alpha_{g}-\alpha_{h}$
(60) $\displaystyle\infty\;(\Theta(N^{\alpha_{h}-1}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}=\alpha_{g}-\alpha_{h}$
(61) $\displaystyle\infty\;(\Theta(N^{\alpha_{h}-1}))$
$\displaystyle,\;\alpha_{f}<\alpha_{g}-1,\alpha_{h}>1,\alpha_{f}<\alpha_{g}-\alpha_{h}$
(62)

It should be noticed that the limits in equations (53) to (58) all show lower
bounds while the limit in equation (59) is an upper bound.