even though all measurements contain
errors. Put simply, all measurements
are “wrong” by definition: the only
question is, how much “wrongness”
can be tolerated? That question cannot
be answered without quantifying mea-
surement error. (Later in this article,
Table 2 quantifies Hadoop measure-
In addition to determining measurement errors, all performance data
should be assessed within the context of a validation method. One such
method is a performance model. In
the context of superlinear speedup, the
USL6–11, 17, 18 fulfills that role in a relatively simple way.
Universal Scalability Model
To quantify scalability more formally,
we first define the empirical speedup
metric in equation 1:
Sp = T1 Tp ( 1)
where Tp is the measured
runtime on p = 1, 2, 3,... processors or
14 Since the multinode
runtime Tp is expected to be shorter
than the single-node runtime T1, the
speedup is generally a discrete concave
function of p. The following special
cases can be identified.
˲ Linear scalability. If Tp = T1/p for
each cluster configuration, then the
speedup will have values Sp = 1, 2, 3, …
for each p, respectively. The speedup
function exhibits linear scalability (the
dashed line in Figure 1).
˲ Sublinear scalability. If Tp > T1/p for
each cluster configuration, then successive speedup values will be
inferior (red curve) to the linear scalability bound in Figure 1. For example, if
p = 2 and T2 = 3 T1/4, then S2 = 1. 33. Since it
is less than S2 = 2, the speedup is sublinear. The red curve is the most common
form of scalability observed on both
monolithic and distributed systems.
˲ Superlinear scalability. If Tp < T1/p,
then successive speedup values will
be superior (blue curve) to the linear
bound in Figure 1. For example, if p
= 2 and T2 = T1/3, then S2 = 3, which is
greater than linear speedup.
The scalability of any computer system can be validated by comparing the
measured speedup in equation 1 with
the theoretically expected speedup, defined here.
Components of scalability.
Scalability, treated as an aggregation of
computer hardware and software, can
be thought of as resulting from several
1. Ideal parallelism or maximal concurrency.
2. Contention for shared resources.
3. Saturation resulting from the primary bottleneck resource.
4. Exchange of data between nonlocal resources to reach consistency or
This does not yet take superlinearity into consideration. The individual
effect of these factors on scalability,
as measured by the speedup metric in
equation 1, is shown schematically in
Each of these scaling effects can
also be represented as separate terms
in an analytic performance model: the