Performance Considerations of Shared Virtual Memory Machines.
AbstractGeneralized speedup is defined as parallel speed over sequential speed. In this paper the generalized speedup and its relation with other existing performance metrics, such as traditional speedup, efficiency, scalability, etc., are carefully studied. In terms of the introduced asymptotic speed, we show that the difference between the generalized speedup and the traditional speedup lies in the definition of the efficiency of uniprocessor processing, which is a very important issue in shared virtual memory machines. A scientific application has been implemented on a KSR-1 parallel computer. Experimental and theoretical results show that the generalized speedup is distinct from the traditional speedup and provides a more reasonable measurement. In the study of different speedups, an interesting relation between fixed-time and memory-bounded speedup is revealed. Various causes of superlinear speedup are also presented.
Introduction
In recent years parallel processing has enjoyed unprecedented attention from researchers, government
agencies, and industries. This attention is mainly due to the fact that, with the current circuit
technology, parallel processing seems to be the only remaining way to achieve higher performance.
However, while various parallel computers and algorithms have been developed, their performance
evaluation is still elusive. In fact, the more advanced the hardware and software, the more difficult
it is to evaluate the parallel performance. In this paper, targeting recent development of shared
virtual memory machines, we study the generalized speedup [1] performance metric, its relation
with other existing performance metrics, and the implementation issues.
Distributed-memory parallel computers dominate today's parallel computing arena. These
machines, such as the Kendall Square KSR-1, Intel Paragon, TMC CM-5, and IBM SP2, have
successfully delivered high performance computing power for solving some of the so-called "grand-
challenge" problems. From the viewpoint of processes, there are two basic process synchronization
and communication models. One is the shared-memory model in which processes communicate
through shared variables. The other is the message-passing model in which processes communicate
through explicit message passing. The shared-memory model provides a sequential-like program
paradigm. Virtual address space separates the user logical memory from physical memory. This
separation allows an extremely large virtual memory to be provided on a sequential machine when
only a small physical memory is available. Shared virtual address combines the private virtual address
spaces distributed over the nodes of a parallel computer into a globally shared virtual memory
[2]. With shared virtual address space, the shared-memory model supports shared virtual memory,
but requires sophisticated hardware and system support. An example of a distributed-memory machine
which supports shared virtual address space is the Kendall Square KSR-1 1 . Shared virtual
memory simplifies the software development and porting process by enabling even extremely large
programs to run on a single processor before being partitioned and distributed across multiple
processors. However, the memory access of the shared virtual memory is non-uniform [2]. The
access time of local memory and remote memory is different. Running a large program on a small
number of processors is possible but could be very inefficient. The inefficient sequential processing
will lead to a misleading high performance in terms of speedup or efficiency.
Generalized speedup, defined as parallel speed over sequential speed, is a newly proposed performance
metric [1]. In this paper, through both theoretical proofs and experimental results, we
show that generalized speedup provides a more reasonable measurement than traditional speedup.
In the process of studying generalized speedup, the relation between the generalized speedup and
many other metrics, such as efficiency, scaled speedup, scalability, are also studied. The relation
1 Traditionally, the message-passing model is bounded by the local memory of the processing processors. With
recent technology advancement, the message-passing model has extended the ability to support shared virtual memory.
between fixed-time and memory-bounded scaled speedup is analyzed. Various reasons for superlin-
in different speedups are also discussed. Results show that the main difference between the
traditional speedup and the generalized speedup is how to evaluate the efficiency of the sequential
processing on a single processor.
The paper is organized as follows. In section 2 we study traditional speedup, including the
scaled speedup concept, and introduce some terminology. Analysis shows that the traditional
speedup, fixed-size or scaled size, may achieve superlinearity on shared virtual memory machines.
Furthermore, with the traditional speedup metric, the slower the remote memory access is, the
larger the speedup. Generalized speedup is studied in Section 3. The term asymptotic speed
is introduced for the measurement of generalized speedup. Analysis shows the differences and
the similarities between the generalized speedup and the traditional speedup. Relations between
different performance metrics are also discussed. Experimental results of a production application
on a Kendall Square KSR-1 parallel computer are given in Section 4. Section 5 contains a summary.
2 The Traditional Speedup
One of the most frequently used performance metrics in parallel processing is speedup. It is defined
as sequential execution time over parallel execution time. Parallel algorithms often exploit
parallelism by sacrificing mathematical efficiency. To measure the true parallel processing gain, the
sequential execution time should be based on a commonly used sequential algorithm. To distinguish
it from other interpretations of speedup, the speedup measured with a commonly used sequential
algorithm has been called absolute speedup [3]. Another widely used interpretation is the relative
speedup [3], which uses the uniprocessor execution time of the parallel algorithm as the sequential
time. There are several reasons to use the relative speedup. First, the performance of an algorithm
varies with the number of processors. Relative speedup measures the variation. Second, relative
speedup avoids the difficulty of choosing the practical sequential algorithm, implementing the sequential
algorithm, and matching the implementation/programming skill between the sequential
algorithm and the parallel algorithm. Also, when problem size is fixed, the time ratio of the chosen
sequential algorithm and the uniprocessor execution of the parallel algorithm is fixed. Therefore,
the relative speedup is proportional to the absolute speedup. Relative speedup is the speedup
commonly used in performance study. In this study we will focus on relative speedup and reserve
the terms traditional speedup and speedup for relative speedup. The concepts and results of this
study can be extended to absolute speedup.
From the problem size point of view, speedup can be divided into the fixed-size speedup and
the scaled speedup. Fixed-size speedup emphasizes how much execution time can be reduced with
parallel processing. Amdahl's law [4] is based on the fixed-size speedup. The scaled speedup is
concentrated on exploring the computational power of parallel computers for solving otherwise
intractable large problems. Depending on the scaling restrictions of the problem size, the scaled
speedup can be classified as the fixed-time speedup [5] and the memory-bounded speedup [6]. As the
number of processors increases, fixed-time speedup scales problem size to meet the fixed execution
time. Then the scaled problem is also solved on an uniprocessor to get the speedup. As the number
of processors increases, memory-bounded speedup scales problem size to utilize the associated
memory increase. A detailed study of the memory-bounded speedup can be found in [6].
Let p and S p be the number of processors and the speedup with p processors.
ffl Unitary speedup: S
ffl Linear speedup: S
It is debatable if any machine-algorithm pair can achieve "truly" superlinear speedup. Seven
possible causes of superlinear speedup are listed in Fig. 1. The first four causes in Fig. 1 are
patterned from [7].
1. cache size increased in parallel processing
2. overhead reduced in parallel processing
3. latency hidden in parallel processing
4. randomized algorithms
5. mathematical inefficiency of the serial algorithm
6. higher memory access latency in the sequential processing
7. profile shifting

Figure

1. Causes of Superlinear Speedup.
Cause 1 is unlikely applicable for scaled speedup, since when problem size scales up, by memory
or by time constraint, the cache hit ratio is unlikely to increase. Cause 2 in Fig. 1 can be considered
theoretically [8], there is no measured superlinear speedup ever attributed to it. Cause 3 does not
exist for relative speedup since both the sequential and parallel execution use the same algorithm.
Since parallel algorithms are often mathematically inefficient, cause 5 is a likely source of superlinear
speedup of relative speedup. A good example of superlinear speedup based on 5 can be found in
[9]. Cause 7 will be explained in the end of Section 3, after the generalized speedup is introduced.
With the virtual memory and shared virtual memory architecture, cause 6 can lead to an
extremely high speedup, especially for scaled speedup where an extremely large problem has to be
run on a single processor. Figure 5 shows a measured superlinear speedup on a KSR-1 machine.
The measured superlinear speedup is due to the inherent deficiency of the traditional speedup
metric. To analyze the deficiency of the traditional speedup, we need to introduce the following
definition.
2 The cost of parallelism i is the ratio of the total number of processor cycles consumed
in order to perform one unit operation of work when i processors are active to the machine clock
rate.
The sequential execution time can be written in terms of work:
Sequential execution Amount of work \Theta
Processor cycles per unit of work
Machine clock rate
The ratio in the right hand side of Eq. (1), processor cycles per unit of work over machine clock
rate, is the cost of sequential processing.
Work can be defined as arithmetic operations, instructions, transitions, or whatever is needed to
complete the application. In scientific computing the number of floating-point operations
is commonly used to measure work. In general, work may be of different types, and units of different
operations may require different numbers of instruction cycles to finish. (For example, the times
consumed by one division and one multiplication may be different depending on the underlying
machine, and operation and memory reference ratio may be different for different computations.)
The influence of work type on the performance is one of the topics studied in [1]. In this paper, we
study the influence of inefficient memory access on the performance. We assume that there is only
one work type and that any increase in the number of processor cycles is due to inefficient memory
access.
In a shared virtual memory environment, the memory available depends on the system size.
Let W i be the amount of work executed when i processors are active (work performed in all steps
that use i processors), and let
work. The cost of parallelism i in
a p processor system, denoted as c p (i; W ), is the elapsed time for one unit operation of work when
i processors are active. Then, W i \Delta c p (i; W ) gives the accumulated elapsed time where i processors
are active. c p (i; W ) contains both computation time and remote memory access time.
The uniprocessor execution time can be represented in terms of uniprocessor cost.
where c p (s; W ) is the cost of sequential processing on a parallel system with p processors. It is
different from c p (1; W ) which is the cost of the sequential portion of the parallel processing. Parallel
execution time can be represented in terms of parallel cost,
The traditional speedup is defined as
Depending on architecture memory hierarchy, in general c p (i; W ) may not equal
[10]. If c p (i; W
The first ratio of Eq. (3) is the cost ratio, which gives the influence of memory access delay. The
second ratio,
is the simple analytic model based on degree of parallelism [6]. It assumes that memory access
time is constant as problem size and system size vary. The cost ratio distinguishes the different
performance analysis methods with or without consideration of the memory influence. In general,
cost ratio depends on memory miss ratio, page replacement policy, data reference pattern, etc. Let
remote access ratio be the quotient of the number of remote memory accesses and the number
of local memory accesses. For a simple case, if we assume there is no remote access in parallel
processing and the remote access ratio of the sequential processing is (p \Gamma 1)=p, then
time of per remote access
time of per local access : (5)
Equation (5) approximately equals the time of per remote access over the time of per local access.
Since the remote memory access is much slower than the local memory access under the current
technology, the speedup given by Eq. (3) could be considerably larger than the simple analytic
model (4). In fact, the slower the remote access is, the larger the difference. For the KSR-1, the
time ratio of remote and local access is about 7.5 (see Section 4). Therefore, for the cost
ratio is 7.3. For any W=
under the assumed remote access ratio, we will have a
superlinear speedup.
3 The Generalized Speedup
While parallel computers are designed for solving large problems, a single processor of a parallel
computer is not designed to solve a very large problem. A uniprocessor does not have the computing
power that the parallel system has. While solving a small problem is inappropriate on a parallel
system, solving a large problem on a single processor is not appropriate either. To create a useful
comparison, we need a metric that can vary problem sizes for uniprocessor and multiple processors.
Generalized speedup [1] is one such metric.
Generalized
Sequential Speed
Speed is defined as the quotient of work and elapsed time. Parallel speed might be based on scaled
parallel work. Sequential speed might be based on the unscaled uniprocessor work. By definition,
generalized speedup measures the speed improvement of parallel processing over sequential pro-
cessing. In contrast, the traditional speedup (2) measures time reduction of parallel processing. If
the problem size (work) for both parallel and sequential processing are the same, the generalized
speedup is the same as the traditional speedup. From this point of view, the traditional speedup is
a special case of the generalized speedup. For this and for historical reasons, we sometimes call the
traditional speedup the speedup, and call the speedup given in Eq. (6) the generalized speedup.
Like the traditional speedup, the generalized speedup can also be further divided into fixed-
size, fixed-time, and memory-bounded speedup. Unlike the traditional speedup, for the generalized
speedup, the scaled problem is solved only on multiple processors. The fixed-time generalized
speedup is sizeup [1]. The fixed-time benchmark SLALOM [11] is based on sizeup.
If memory access time is fixed, one might always assume that the uniprocessor cost c p
be stablized after some initial decrease (due to initialization, loop overhead, etc.), assuming the
memory is large enough. When cache and remote memory access are considered, cost will increase
when a slower memory has to be accessed. Figure 2 depicts the typical cost changing pattern.
From Eq. (1), we can see that uniprocessor speed is the reciprocal of uniprocessor cost. When
the cost reaches its lowest value, the speed reaches its highest value. The uniprocessor speed corresponding
to the stablized main memory cost is called the asymptotic speed (of uniprocessor).
Asymptotic speed represents the performance of the sequential processing with efficient memory
access. The asymptotic speed is the appropriate sequential speed for Eq. (6). For memory-bounded
speedup, the appropriate memory bound is the largest problem size which can maintain
the asymptotic speed. After choosing the asymptotic speed as the sequential speed, the corresponding
asymptotic cost has only local access and is independent of the problem size. We use
to denote the corresponding asymptotic cost, where W 0 is a problem size which achieves
the asymptotic speed. If there is no remote access in parallel processing, as assumed in Section 2,
then c(s; W 0 )=c p (p; W 0 (3), the corresponding speedup equals the simple speedup
Fits in
Cache
Cost
Problem Size
Fits in Main Memory
Fits in Remote
Memory
Execution Time
Increases Sequential
Insufficient Memory

Figure

2. Cost Variation Pattern.
which does not consider the influence of memory access time. In general, parallel work W is not
the same as W 0 , and c p (i; W ) may not equal in general, we have
Generalized
Equation (7) is another form of the generalized speedup. It is a quotient of sequential and parallel
time as is traditional speedup (2). The difference is that, in Eq. (7), the sequential time is based
on the asymptotic speed. When remote memory is needed for sequential processing, c(s; W 0 ) is
smaller than c p (s; W ). Therefore, the generalized speedup gives a smaller speedup than traditional
speedup.
Parallel efficiency is defined as
number of processors : (8)
The Generalized efficiency can be defined similarly as
Generalized Efficiency = generalized speedup
number of processors :
By definition,
and
Generalized Efficiency
Equations (10) and (11) show the difference between the two efficiencies. Traditional speedup compares
parallel processing with the measured sequential processing. Generalized speedup compares
parallel processing with the sequential processing based on the asymptotic cost. From this point
of view, generalized speedup is a reform of traditional speedup. The following lemmas are direct
results of Eq.(7).
independent of problem size, traditional speedup is the same as generalized
speedup.
Lemma 2 If the parallel work, W , achieves the asymptotic speed, that is then the
fixed-size traditional speedup is the same as the fixed-size generalized speedup.
By Lemma 1, if the simple analytic model (4) is used to analyze performance, there is no difference
between the traditional and the generalized speedup. If the problem size W is larger than the
suggested initial problem size W 0 , then the single processor speedup S 1 may not equal to one. S 1
measures the sequential inefficiency due to the difference in memory access.
The generalized speedup is also closely related to the scalability study. Isospeed scalability
has been proposed recently in [12]. The isospeed scalability measures the ability of an algorithm-
machine combination maintaining the average (unit) speed, where the average speed is defined as
the speed over the number of processors. When the system size is increased, the problem size is
scaled up accordingly to maintain the average speed. If the average speed can be maintained, we
say the algorithm-machine combination is scalable and the scalability is
where W 0 is the amount of work needed to maintain the average speed when the system size has
been changed from p to p 0 , and W is the problem size solved when p processors were used. By
definition
Since the sequential cost is fixed in Eq. (11), fixing average speed is equivalent to fixing generalized
efficiency. Therefore the isospeed scalability can be seen as the iso-generalized-efficiency scalability.
When the memory influence is not consedered, i.e. c p (s; W ) is independent of the problem size, the
iso-generalized-efficiency will be the same as the iso-traditional-efficiency. In this case, the isospeed
scalability is the same as the isoefficiency scalability proposed by Kumar [13, 2].
Lemma 3 If the sequential cost c p (s; W ) is independent of problem size or if the simple analysis
model (4) is used for speedup, the isoefficiency and isospeed scalability are equivalent to each other.
The following theorem gives the relation between the scalability and the fixed-time speedup.
Theorem 1 Scalability (12) equals one if and only if the fixed-time generalized speedup is unitary.
Proof: Let c(s; W 0 be as defined in Eq. (7). If scalability (12) equals 1, let
be as defined in Eq. (12) and define W 0
similarly as W i , we have
for any number of processors p and p 0 . By definition, generalized speedup
With some arithmetic manipulation, we have
Similarly, we have
By Eq. (13) and the above two equations,
For fixed speed,
By equation (13),
Substituting Eq. (15) into Eq. (14), we have
For
Equation (16) is the corresponding unitary speedup when G S 1 is not equal to one. If the work W
which is the unitary speedup defined in definition 1 .
If the fixed-time generalized speedup is unitary, then for any number of processors, p and p 0 ,
and the corresponding problem sizes, W and W 0 , where W 0 is the scaled problem size under the
fixed-time constraint, we have
and
Therefore,
The average speed is maintained. Also since
we have the equality
The scalability (12) equals one. 2
The following theorem gives the relation between memory-bounded speedup and fixed-time
speedup. The theorem is for generalized speedup. However, based on Lemma 1, the result is true
for traditional speedup when uniprocessor cost is fixed or the simple analysis model is used.
Theorem 2 If problem size increases proportionally to the number of processors in memory-bounded
scaleup, then memory-bounded generalized speedup is linear if and only if fixed-time generalized
speedup is linear.
Proof: Let c(s; W 0 ); c p (i; W ), W and W i be as defined in Theorem 1. Let W 0 ; W   be the scaled
problem size of fixed-time and memory-bounded scaleup respectively, and W 0
i and W
i be defined
accordingly.
If memory-bounded speedup is linear, we have
and
for some constant a ? 0. Combine the two equations, we have the equation
By assumption, W   is proportional to the number of processors available,
Substituting Eq. (18) into Eq. (17), we get the fixed-time equality:
That is W and the fixed-time generalized speedup is linear.
If fixed-time speedup is linear, then, following similar deductions as used for Eq. (17), we have
Applying the fixed-time equality Eq. (19) to Eq. (20), we have the reduced equation
With the assumption Eq. (18), Eq. (21) leads to
and memory-bounded generalized speedup is linear. 2
The assumption of Theorem 2 is problem size (work) increases proportionally to the number of
processors. The assumption is true for many applications. However, it is not true for dense matrix
computation where the memory requirement is a square function of the order of the matrix and the
computation is a cubic function of the order of the matrix. For this kind of computational intensive
applications, in general, memory-bounded speedup will lead to a large speedup. The following
corollaries are direct results of Theorem 1 and Theorem 2.
Corollary 1 If problem size increases proportionally to the number of processors in memory-bounded
scaleup, then memory-bounded generalized speedup is unitary if and only if fixed-time
generalized speedup is unitary.
Corollary 2 If work increases proportionally with the number of processors, then scalability (12)
equals one if and only if the memory-bounded generalized speedup is unitary.
Since uniprocessor cost varies on shared virtual memory machines, the above theoretical results
are not applicable to traditional speedup on shared virtual memory machines.
Finally, to complete our discussion on the superlinear speedup, there is a new cause of superlin-
for generalized speedup. The new source of superlinear speedup is called profile shifting [11],
and is due to the problem size difference between sequential and parallel processing (see Figure
1). An application may contain different work types. While problem size increases, some work
types may increase faster than the others. When the work types with lower costs increase faster,
superlinear speedup may occur. A superlinear speedup due to profile shifting was studied in [11].
4 Experimental Results
In this section, we discuss the timing results for solving a scientific application on KSR-1 parallel
computers. We first give a brief description of the architecture and the application, and then
present the timing results and analyses.
4.1 The Machine
The KSR-1 computer discussed here is a representative of parallel computers with shared virtual
memory. Figure 3 shows the architecture of the KSR-1 parallel computer [14]. Each processor
on the KSR-1 has 32 Mbytes of local memory. The CPU is a super-scalar processor with a peak
performance of 40 Mflops in double precision. Processors are organized into different rings. The
local ring (ring:0) can connect up to 32 processors, and a higher level ring of rings (ring:1) can
contain up to 34 local rings with a maximum of 1088 processors.
If a non-local data element is needed, the local search engine (SE:0) will search the processors
in the local ring (ring:0). If the search engine SE:0 can not locate the data element within the local
ring, the request will be passed to the search engine at the next level (SE:1) to locate the data.
This is done automatically by a hierarchy of search engines connected in a fat-tree-like structure
[14, 15]. The memory hierarchy of KSR-1 is shown in Fig. 4.
Each processor has 512 Kbytes of fast subcache which is similar to the normal cache on other
parallel computers. This subcache is divided into two equal parts: an instruction subcache and a
data subcache. The 32 Mbytes of local memory on each processor is called a local cache. A local
ring (ring:0) with up to 32 processors can have 1 Gbytes total of local cache which is called Group:0
cache. Access to the Group:0 cache is provided by Search Engine:0. Finally, a higher level ring
ring:1
connecting up to 34 ring:0's
ring:0
connecting up
to processers
ring:0 ring:0

Figure

3. Configuration of KSR-1 parallel computers.
Mbytes of local memory
Group:0 Cache
34 GB
Group:1 Cache
512 KB Subcache
Processor
Search Engine:0
Search Engine:1

Figure

4. Memory hierarchy of KSR-1.
of rings (ring:1) connects up to 34 local rings with 34 Gbytes of total local cache which is called
Group:1 cache. Access to the Group:1 cache is provided by Search Engine:1. The entire memory
hierarchy is called ALLCACHE memory by the Kendall Square Research. Access by a processor
to the ALLCACHE memory system is accomplished by going through different Search Engines as
shown in Fig. 4. The latencies for different memory locations [16] are: 2 cycles for subcache, 20
cycles for local cache, 150 cycles for Group:0 cache, and 570 cycles for Group:1 cache.
4.2 The Application
Regularized least squares problems (RLSP) [17] are frequently encountered in scientific and engineering
applications [18]. The major work is to solve the equation
by orthogonal factorization schemes (Householder Transformations and Givens rotations). Efficient
Householder algorithms have been discussed in [19] for shared memory supercomputers, and in [20]
for distributed memory parallel computers.
Note that Eq. (22) can also be written as
ffI)@ A
ffI)@ b1
A (23)
or
so that the major task is to carry out the QR factorization for matrix B which is neither a complete
full matrix nor a sparse matrix. The upper part is full and the lower part is sparse (in diagonal
form). Because of the special structure in B, not all elements in the matrix are affected in a
particular step. Only a submatrix of B will be transformed in each step. If the columns of the
at step i are denoted by B
then the Householder Transformation
can be described as:
Householder Transformation
Initialize matrix B
1: ff
2:
3:
ii
4: b i
end for
The calculation of fi j 's and updating of b i
j 's can be done in parallel for different index j.
4.3 Timing Results
The numerical experiments reported here were conducted on the KSR-1 parallel computer installed
at the Cornell Theory Center. There are 128 processors altogether on the machine. During the
period when our experiments were performed, however the computer was configured as two stand-alone
machines with 64 processors each. Therefore, the numerical results were obtained using less
than 64 processors.

Figure

5 shows the traditional fixed-size speedup curves obtained by solving the regularized
least squares problem with different matrix sizes n. The matrix is of dimensions 2n \Theta n. We can
see clearly that as the matrix size n increases, the speedup is getting better and better. For the
case when the speedup is 76 on 56 processors. Although it is well known that on most
parallel computers, the speedup improves as the problem size increases, what is shown in Fig. 5 is
certainly too good to be a reasonable measurement of the real performance of the KSR-1.
The problem with the traditional speedup is that it is defined as the ratio of the sequential
time to the parallel time used for solving the same fixed-size problem. The complex memory
hierarchy on the KSR-1 makes the computational speed of a single processor highly dependent on
the problem size. When the problem is so big that not all data of the matrix can be put in the local
memory (32 Mbytes) of the single computing processor, part of the data must be put in the local
memory of other processors on the system. These data are accessed by the computing processor
through Search Engine:0. As a result, the computational speed on a single processor slows down
significantly due to the high latency of Group:0 cache. The sustained computational speed on a
single processor is 5.5 Mflops, 4.5 Mflops and 2.7 Mflops for problem sizes 1024, 1600 and 2048
respectively. On the other hand, with multiple processors, most of the data needed are in the local
memory of each processor, so the computational speed suffers less from the high Group:0 cache
Number of Processors
\Theta \Theta
\Theta
\Theta
\Theta
\Theta \Theta

Figure

5. Fixed-size (Traditional) Speedup on KSR-1
latency. Therefore, the excellent speedups shown in Fig. 5 are the results of significant uniprocessor
performance degradation when a large problem is solved on a single processor.

Figure

6 shows the measured single processor speed as a function of problem size n. The Householder
Transformation algorithm given before was implemented in KSR Fortran. The algorithm
has a numerical complexity of 26:5n, and the speed is calculated using
where t is the CPU time used to finish the computation.
As can be seen from Fig. 6, the three segments represent significantly different speeds for
different matrix sizes. When the whole matrix can be fit into the subcache, the performance is
close to 7 Mflops. The speed decreases to around 5.5 Mflops when the matrix can not be fit into
the subcache, but still can be accommodated in the local cache. Note, however, when the matrix is
so big that access to Group:0 cache through Search Engine:0 is needed, the performance degrades
significantly and there is no clear stable performance level as can be observed in the other two
segments. This is largely due to the high Group:0 cache latency and the contention for the Search
Engine which is used by all processors on the machine. Therefore, the access time of Group:0 cache
is less uniform as compared to that of the subcache and local cache.
To take the difference of single processing speeds for different problem sizes into consideration,
we have to use the generalized speedup to measure the performance of multiple processors on
the KSR-1. As can be seen from the definition of Eq. (6), the generalized speedup is defined
as the ratio of the parallel speed to the asymptotic sequential speed, where the parallel speed is
based on a scaled problem. In our numerical tests, the parallel problem was scaled in a memory-
dOrder of the Matrices
Subcache
Group:0 Cache \Theta
\Theta
\Theta
\Theta

Figure

6. Speed Variation of Uniprocessor Processing on KSR-1
bounded fashion as the number of processors increases. The initial problem was selected based
on the asymptotic speed (5.5 Mflops from Fig. 6) and then scaled proportionally according to the
number of processors, i.e. with p processors, the problem is scaled to a size that will fill M \Theta p
Mbytes of memory, where M is the memory required by the unscaled problem. Figure 7 shows
the comparisons of the traditional scaled speedup and the generalized speedup. For the traditional
scaled speedup, the scaled problem is solved on both one and p processors, and the value of the
speedup is calculated as the ratio of the time of one processor to that of p processors. While for
the generalized speedup, the scaled problem is solved only on multiple processors, not on a single
processor. The value of the speedup is calculated using Eq. (6), where the asymptotic speed is used
for the sequential speed. It is clear that Fig. 7 shows that the generalized speedup gives much more
reasonable performance measurement on KSR-1 than does the traditional scaled speedup. With
the traditional scaled speedup, the speedup is above 20 with only 10 processors. This excellent
superlinear speedup is a result of the severely degraded single processors speed, rather than the
perfect scalability of the machine and the algorithm.
Finally, table 1 gives the measured isospeed scalability (see Eq. (12)) of solving the regularized
least squares problem on a KSR-1 computer. The speed to be maintained on different number of
processors is 3.25 Mflops, which is 60% of the asymptotic speed of 5.5 Mflops. The size of the 2n \Theta n
matrix is increased as the number of processors increases. It starts as on one processor and
increases to processors. One may notice that /(2; table 1, which
means that the machine-algorithm pair scales better from 2 processors to 4 processors than it does
Number of Processors
Generalized Speedup \Theta
\Theta
\Theta \Theta
\Theta \Theta
\Theta
\Theta
\Theta
Traditional Speedup

Figure

7. Comparison of Generalized and Traditional Speedup on KSR-1
from one processor to two processors. This can be explained by the fact that on one processor,
the matrix is small enough that all data can be accommodated in the subcache. Once all the data
is loaded into the subcache, the whole computation process does not need data from local cache
and Group:0 cache. Therefore, the data access time on one processor is significantly shorter than
that on two processors which involves subcache, local cache and Group:0 cache to pass messages.
As a result, significant increase in the work W is necessary in the case of two processors to offset
the extra data access time involving different memory hierarchies. This is the major reason for the
low /(1; 2) value. When the number of processors increases from 2 to 4, the data access pattern
is the same for both cases with subcache, local cache and Group:0 cache all involved, so that the
work W does not need to be increased significantly to offset the extra communication cost when
going from 2 processors to 4 processors. It is interesting to notice, while the scalability of the
RLSP-KSR1 combination is relatively low, the data in Table 1 has a similar decreasing pattern
as the measured and computed scalability of Burg-nCUBE, SLALOM-nCUBE, Burg-MasPar and
SLALOM-MasPar combinations [12]. The scalabilities are all decreasing along columns and have
some irregular behavior at /(1; 2) and /(2; 4).
Interested readers may wonder how the measured scalability is related to the measured generalized
speedup given in Fig. 7. While Fig. 7 demonstrates a nearly linear generalized speedup, the
corresponding scalability given in Table 1 is far from ideal (the ideal scalability would be unity).
The low scalability is expected. Recall that the scaled speedup given in Fig. 7 is memory-bounded
speedup [6]. That is when the number of processors is doubled, the usage of memory is also doubled.

Table

1. Measured Scalability of RLSP-KSR1 combination.
As a result, the number of elements in the matrix is increased by a factor of 2. Corollary 2 shows
that if work W increases linearly with the number of processors, then unitary memory-bounded
speedup will lead to ideal scalability. For the regularized least squares application, however, the
work W is a cubic function of the matrix size n. When the memory usage is doubled, the number
of floating point operations is increased by a factor of eight. If a perfect generalized speedup is
achieved from p to p 0
2p, the average speed at p and p 0
should be the same. By Eq. (12) we have
With the measured speedup being a little lower than unitary as shown in Fig. 7, a less than 0:25
scalability is expected. Table 1 confirms this relation, except at /(2; 4) for the reason pointed out
earlier. The scalability in the last column is noticeably lower than other columns. It is because
when 56 nodes are involved in computations, communication has to pass through ring:1, which
slows down the communication significantly.
Computation intensive applications have often been used to achieve high flops. The RLSP
application is a computation intensive application. Table 1 shows that isospeed scalability does
not give credits for computation intensive applications. The computation intensive applications
may achieve a high speed on multiple processors, but the initial speed is also high. The isospeed
scalability measures the ability to maintain the speed, rather than to achieve a particular speed.
The implementation is conducted on a KSR-1 shared virtual memory machine. The theoretical
and analytical results given in Section 2 and Section 3, however, are general and can be applied
on different parallel platforms. For instance, for Intel Paragon parallel computers, where virtual
memory is supported to swap data in and out from memory to disk, we expect that inefficient sequential
processing will cause similar superlinear (traditional) speedup as demonstrated on KSR-1.
For distributed-memory machines which do not support virtual memory, such as CM-5, traditional
speedup has another draw back. Due to memory constraint, scaled problems often cannot be
solved on a single processor. Therefore, scaled speedup is unmeasurable. Defining asymptotic speed
similarly as given in Section 3, the generalized speedup can be applied to this kind of distributed-memory
machines to measure scalable computations. Generalized speedup is defined as parallel
speed over sequential speed. Given a reasonable initial sequential speed, it can be used on any
parallel platforms to measure the performance of scalable computations.
5 Conclusion
Since the scaled up principle was proposed in 1988 by Gustafson and other researchers at Sandia
National Laboratory [21], the principle has been widely used in performance measurement of parallel
algorithms and architectures. One difficulty of measuring scaled speedup is that vary large problems
have to be solved on uniprocessor, which is very inefficient if virtual memory is supported, or
is impossible otherwise. To overcome this shortcoming, generalized speedup was proposed [1].
Generalized speedup is defined as parallel speed over sequential speed and does not require solving
large problems on uniprocessor. The study [1] emphasized the fixed-time generalized speedup,
sizeup. To meet the need of the emerging shared virtual memory machines, the generalized speedup,
particularly implementation issues, has been carefully studied in the current research. It has shown
that traditional speedup is a special case of generalized speedup, and, on the other hand, generalized
speedup is a reform of traditional speedup. The main difference between generalized speedup and
traditional speedup is how to define the uniprocessor efficiency. When uniprocessor speed is fixed
these two speedups are the same. Extending these results to scalability study, we have found that
the difference between isospeed scalability [12] and isoefficiency scalability [13] is also due to the
uniprocessor efficiency. When the uniprocessor speed is independent of the problem size, these
two proposed scalabilities are the same. As part of the performance study, we have shown that
an algorithm-machine combination achieves a perfect scalability if and only if it achieves a perfect
speedup. An interesting relation between fixed-time and memory-bounded speedups is revealed.
Seven causes of superlinear speedup are also listed.
A scientific application has been implemented on a Kendall Square KSR-1 shared virtual memory
machine. Experimental results show that uniprocessor efficiency is an important issue for
virtual memory machines, and that the asymptotic speed provides a reasonable way to define the
uniprocessor efficiency.
The results in this paper on shared virtual memory can be extended to general parallel com-
puters. Since uniprocessor efficiency is directly related to parallel execution time, scalability, and
benchmark evaluations, the range of applicability of the uniprocessor efficiency study is wider than
speedups. The uniprocessor efficiency might be explored further in a number of contexts.

Acknowledgement

The authors are grateful to the Cornell Theory Center for providing access to its KSR-1 parallel
computer, and to the referees for their helpful comments on the revision of this paper.



--R

"Toward a better parallel performance metric,"
Advanced Computer Architecture: Parallelism
"Solution of partial differential equations on vector and parallel com- puters,"
"Validity of the single-processor approach to achieving large scale computing capabilities,"

"Scalable problems and memory-bounded speedup,"
"Modeling speedup(n) greater than n,"
"Parallel efficiency can be greater than unity,"
"Inflated speedups in parallel simulations via malloc(),"
"Performance prediction of scalable computing: A case study,"
"The design of a scalable, fixed-time computer benchmark,"
"Scalability of parallel algorithm-machine combinations,"
"Isoefficiency: Measuring the scalability of parallel algorithms and architectures,"
"KSR parallel programming."
"Fat-trees: Universal networks for hardware-efficient supercomputing,"
"KSR technical summary."
Solution of Ill-posed Problems
"GPST inversion algorithm for history matching in 3-d 2-phase simulators,"
Solving Linear Systems on Vector and Shared Memory Computers.
"Distributed orthogonal factorization: Givens and Householder algorithms,"
"Development of parallel methods for a 1024- processor hypercube,"
--TR

--CTR
Prasad Jogalekar , Murray Woodside, Evaluating the Scalability of Distributed Systems, IEEE Transactions on Parallel and Distributed Systems, v.11 n.6, p.589-603, June 2000
Xian-He Sun, Scalability versus execution time in scalable systems, Journal of Parallel and Distributed Computing, v.62 n.2, p.173-192, February 2002
Xian-He Sun , Jianping Zhu, Performance Prediction: A Case Study Using a Scalable Shared-Virtual-Memory Machine, IEEE Parallel & Distributed Technology: Systems & Technology, v.4 n.4, p.36-49, December 1996
Xian-He Sun , Wu Zhang, A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.97-106, February 2004
Xian-He Sun , Mario Pantano , Thomas Fahringer, Integrated Range Comparison for Data-Parallel Compilation Systems, IEEE Transactions on Parallel and Distributed Systems, v.10 n.5, p.448-458, May 1999
shared virtual memory;speedup;scalability;performance evaluation;performance metrics;high performance computing;parallel processing