From: sun@elc04.icase.edu (Dr. Xian-He Sun)
Subject: Re: definition of parallel efficiency
Organization: ICASE/NASA Langley
Date: 21 Jan 1993 21:21:59 GMT


Parallel efficiency is defined as the quotient of the speedup
and the number of processors used, p. Since there are two
different definitions of speedup, there are two different
definitions of efficiency [1], [2], [3]. In one definition speedup 
is defined as

(1)  (seq. time of the par. algorithm) / parallel time ,

which is called absolute speedup. In another speedup is defined as

(2)  (seq. time of the best possible sequential algorithm
               for the problem) /  parallel time,

which is called relative speedup. Definition (1) is a good
measurement of parallel processing gain versus sequential
processing. Definition (2) is a good measurement of the
inherent parallelism of the parallel algorithm. In practice,
(1) is oftenly used in newly designed parallel algorithms, and
(2) is used in performance and scalability analysis [4]. The 
well known Amdahl's law and Gustafson's scaled speedup [5],[6] are 
all based on definition (2).  


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                          sun@icase.edu

------------------------------------------------------------------
Reference:

@INPROCEEDINGS{SuNi90,
          author = "Xian-He Sun and L. Ni",
          title  = "Another View on Parallel Speedup",
          booktitle = "Proc. of Supercomputing'90",
          address = "NY, NY",
          year = "1990",
          pages = "324--333",
  }

@BOOKLET{SuNi92,
          author = "Xian-He Sun and L. Ni",
          title  = "Scalable Problems and Memory-Bounded Speedup",
          howpublished = "ICASE Technical Report, 92-59",
          address = "ICASE, NASA Langley Research Center",
          year = "1992",
  }

@ARTICLE{Hock91,
          author = "Roger W. Hockney",
          title = "Performance Parameters and Benchmarking of
                   Supercomputers",
          journal = "Parallel Computing",
          Note = "This issue of Parallel Computing",
  }

@BOOKLET{SuRo91,
          author = "Xian-He Sun and D.T. Rover",
          title ="Scalability of Parallel Algorithm-Machine Combinations",
          howpublished = "Technical Report, IS-5057, UC-32",
          address = "Ames Laboratory, U.S. Department of Energy",
          year = "1991",
  }

@ARTICLE{GuMB88,
          author = "J.L. Gustafson and G.R. Montry and R.E. Benner",
          title = "Development of Parallel Methods for a 1024-processor
                   Hypercube",
          journal = "SIAM J. on SSTC",
          Volume = 9,
          YEAR = "1988",
          month = "July",
          number = "4",
  }

@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",
  }



Newsgroups: comp.parallel