Subject: Re: Revised SPEEDUP section

From: Sun Xian-He <[email-masked]>
Date: Tue, 8 Jun 93 13:49:38 -0400

Recently, Roger Hockney has sent two messages to this news group.
The first is the proposed amendment of speedup, in which he emphasizes
the execution time is very important. The second is a response to
readers, in which he emphasizes the work (in flop-count)
is also very important. I agree his points. In fact, if we agree that 
time and work are the two
important factors under consideration, we may consider to use the
GENERALIZED SPEEDUP [1] [2]. The generalized speedup is defined as

Generalized Speed = Parallel_speed/Sequential_speed,

where speed is defined as work/time. Parallel speed is defined as
parallel work over parallel time. Sequential speed is defined as
sequential work over sequential time. The parallel work could be
the scaled work, with fixed-time or memory-bounded constrain.
The sequential work could be the unscaled work and can be measured.
All the nice properties of traditional
speedup, defined as sequential_time/parallel_time, will remain.
When the problem size is fixed, the generalized speedup is the same as
the traditional speedup. Also, it has been shown [2] that when the
single processor speed is independent of work (no memory influence)
the generalized speedup is the same as the traditional speedup. 
Therefore, all the analytic results based on the traditional speedup
can be applied to the generalized speedup, while the 
superlinear speedups, which due to memory miss of sequential 
processing, cannot.

In our practice, the sequential speed is fixed for each application.
It is a fraction of the asymptotic speed [3]. The sequential speed
shows the single processor power of each machine. The ratio of 
sequential speeds can be used to compare speedups measured on different
machines. The work (flop-count) is unified by using the flop-count of a
practical sequential algorithm [4].

If work should be given along with the speedup, as Roger Hockney
suggested, the generalized speedup does not increase measurement
complexity. With the above merits, the generalized speedup may
be a metric worth to consider.

Xian-He Sun

[1]
@INPROCEEDINGS{Gust90,
          author = "J.L. Gustafson",
          title = "Fixed time, Tiered Memory, and Superlinear Speedup",
          booktitle = "Proc. of the Fifth Conf. on Distributed
                       Memory Computers",
          year = "1990",
}
[2]
@ARTICLE{SuGu91,
          AUTHOR = "Xian-He Sun and J.L. Gustafson",
          TITLE =  "Toward a Better Parallel Performance Metric",
          JOURNAL = "Parallel Computing",
          VOLUME = "17",
          MONTH = "Dec.",
          YEAR =   "1991",
          pages = "1093--1109",
}
[3]
@ARTICLE{Hock91,
          author = "Roger W. Hockney",
          title = "Performance Parameters and Benchmarking of
                   Supercomputers",
          journal = "Parallel Computing",
          volume = "17",
          month = "Dec.",
          year =   "1991",
}
[4]
@INPROCEEDINGS{Bail92,
          author = "David H. Bailey",
          title  = "Misleading Performance in the Supercomputing Field",
          booktitle = "Proc. Supercomputing '92",
          address = " ",
          year = "1992",
          pages = "155--158",
}

=======================   Xian-He Sun  ============================

ICASE 
(Institute for Computer Applications in Science and Engineering)
Mail Stop 132C                                  804-864-8018 (O)
NASA Langley Research Center                    804-864-6134 (fax)
Hampton, VA 23681-0001                          [email-masked]

====================================================================