home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / parallel / 3029 < prev    next >
Encoding:
Text File  |  1993-01-22  |  2.3 KB  |  60 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!gatech!hubcap!fpst
  3. From: kunisada@is.kyushu-u.ac.jp (Katuhiro KUNISADA)
  4. Subject: Re: definition of parallel efficiency
  5. In-Reply-To: kitchel@manta.dpsi.com's message of Mon, 11 Jan 1993 15:28:55 GMT
  6. X-Nntp-Posting-Host: is-og8.is.kyushu-u.ac.jp
  7. Message-ID: <KUNISADA.93Jan22162745@is-og8.is.kyushu-u.ac.jp>
  8. Sender: news@is.kyushu-u.ac.jp
  9. Organization: Dept. of Information Systems, Kyushu Univ., Japan
  10. References: <1993Jan11.142638.7789@hubcap.clemson.edu>
  11.     <kitchel.726766135@manta>
  12. Date: Fri, 22 Jan 1993 07:27:45 GMT
  13. Approved: parallel@hubcap.clemson.edu
  14. Lines: 44
  15.  
  16. In article <kitchel.726766135@manta> kitchel@manta.dpsi.com (Sidney W. Kitchel) writes:
  17.  
  18.    >Stephen Vavasis <vavasis@cs.cornell.EDU> writes:
  19.    >
  20.    >
  21.    >>I have seen two definitions of "parallel efficiency" in the literature,
  22.    >>and I am wondering whether one definition or the other has prevailed.
  23.    >>They are:
  24.    >
  25.    >>(1) par eff = (seq. time of the par. algorithm) / (p * parallel time)
  26.    >
  27.    >>(2) par eff = (seq. time of the best possible sequential algorithm
  28.    >>               for the problem) / (p * parallel time)
  29.    >
  30.    >>If you had a parallel cyclic reduction algorithm, would you rate it
  31.    >>against a sequential cyclic reduction algorithm or against tridiagonal
  32.    >>Cholesky factorization?
  33.    >
  34.    >>How about when the underlying problem is more complicated, for example
  35.    >>solving a boundary value problem?  In this case it's not clear how to
  36.    >>identify the best possible sequential algorithm.
  37.    >
  38.    >>I would like to get this definition straight because I am teaching a
  39.    >>class on parallelism.
  40.    >
  41.    >        Since Frontiers '92, it also depends on whether you did the
  42.    >programming or God did.
  43.  
  44.  
  45. As we are not god.
  46.  
  47. I think that, the best way to estimate parallel efficiency is to use
  48. the sequential algorithm that is known to perform best, as the following.
  49.  
  50.            (worst seq. time of the seq. algorithm that is known to be best)
  51.  par eff = ----------------------------------------------------------------
  52.                                 (p * parallel time of the worst case)
  53.  
  54.  
  55.  
  56. ----------------------------------------------------------------------
  57. K. kunisada                kunisada@is.kyushu-u.ac.jp
  58. My name is same with the most famous Yakuza (Kunisada Tyuuji)
  59.  
  60.