Subject: COMMENTS ON GENERALISED SPEEDUP

From: Sun Xian-He <[email-masked]>
Date: Fri, 11 Jun 93 10:03:00 -0400

I would like to thank Roger Hockney and David Bailey for their comments on
the generalized speedup. I agree that there is a need to explain the definition
of generalized speedup more clearly. As an effort to do so, 
I will answer Roger Hockney comments one by one in the following. David 
Bailey's question will be answered during the way.

>              COMMENTS ON GENERALISED SPEEDUP
>              -------------------------------
>                      Roger Hockney

>  (1) If generalised speedup is defined as
>                          W(N;p)*T(N;1)
>                GS(N;p) = -------------
>                          W(N;1)*T(N;p)
>then to make the number given for GS unambiguous, we must ask that the 
>benchmarker give the values used for W(N;p), W(N;1) and T(N;1), so that
>we can work out the time it took to run the benchmark = T(N;p). This is
>impractical and unnecessarily complicated.

      This is not true. In general, the T(N;p) is independent of W(N;1) and 
      T(N;1). The only complication has added on is the computation of the
      asymptotic speed. However, the asymptotic speed is important on itself
      (I did refer Roger Hockney's work for this point).

>  (2) In comparing a parallel implementation with a serial one, it is 
>essential that we use the same flop-count or work. That is to say, not
>give the parallel version credit for performing unnecessary redundant
>operations, i.e. we require W(N;p)=W(N,1). In this case, of course,
>generalised speedup reduces to ordinary speedup, and my comments about
>the undesirabilty of ordinary speedup have already been expressed. 

       In gerealized speedup, the flop-count or work is based on a practical 
       sequential algorithm (I did refer David Bailey's work for this point).  
       It will not give credit for performing unnecessary redundant operation.

>  (3) In any case I do not understand what generalised speedup is 
>supposed to be a measure of? Unless this can be satisfactorily
>answered, we should not use it.

       Generalized speedup measures the speed-up. In contrast, the 
       traditional speedup gives the ratio of time reduction. If we ask the
       question in different way, if we ask how is the measurement of
       generalized speedup related with the measurement of traditional
       speedup. The answer is: The generalized speedup is a REFORM of
       traditional speedup. The generalized speedup is a 
       traditional speedup in which the sequential time T(N,1) is
       computed by using the asymptotic speed. (With few lines I can
       prove this, but I would like to leave it as a quiz).

       I think most of us agree that we need a good way to compute T(N,1).
       Our application has achieved superlinear speedup (traditional) on
       KSR and I am sure we will get superlinear speedup (traditional) on
       Paragon also. In fact, with traditional speedup, a big class of
       applications will achieve superlinear speedup on machines supporting
       virtual memory. It is a misleading. Generalized speedup is a way to
       avoid it.
        
Xian-He Sun