Subject: REPLY to Generalised Speedup - 2

From: Sun Xian-He <[email-masked]>
Date: Wed, 30 Jun 93 11:18:48 -0400

Through Roger Hockney's questions, I see that some confusion still 
exist. The following is my answer to these questions. I see my role
in here is to explain the generalized speedup. There is no intention
to argue that this metric is better than another. Especially, I think
execution time is important and should be reported, though execution time
will be heavily influenced by a programmer's programming skill.

I would like to thank Roger Hockney for his respectful discussion.

---------------------------------------------------------------------------
>                    REPLY to Xian-He SUN - 2
>                        from Roger Hockney
>                    -------------------------

>I see that TU, the unit of time used in GS, changes for 
>different computers, and even for different numbers of processors on the 
>same computer, i.e. the dependency is, in general, TU(A,X:N;p). Thus, I
>conclude the following: 
---------------------------------------------------------------------------

      The answer is YES and No. TU changes for different computers, but
      changing for different numbers of processors on the same computer
      is questionable. Recall that

                       TU                     W(p) * T(1;1)
             GS(p) = --------     where  TU = ---------------
                      T(p;p)                      W(1)

      If the problem size is fixed, TU is independent of number of 
      processors. More precisely, TU_1 = T(1;1)/W(1) is independent of number 
      of processors.  
      
---------------------------------------------------------------------------
>  (1) We *cannot* conclude that if the GS on computer B is greater than
>      the GS on computer A on a particular benchmark (same X:N), then 
>      computer B executes the benchmark in less wallclock time than 
>      computer A. 
---------------------------------------------------------------------------

       True. The generalized speedup measures speedup, not wallclock time.
       However, as a good metric, it is closed related with execution time.
       Let
            GS(A,X:N;p) = GS = TU/T,  TU = (W(p) * T(1;1))/W(1)
       and 
            GS(B,X:N;p) = GS' = TU'/T',  TU' = (W'(p) * T'(1;1))/W'(1)).
       If 
            GS > GS'
       then by definition
                       TU         TU'
                      ----   >   ----
                        T          T'
      or
                       TU
                  T <  -- * T'
                       TU'
      If we run the same problem size on both machine A and B, then W(p)=W'(p)
      and TU/TU' = TU_1/TU'_1. TU_1 and TU'_1 are pre-measured and are 
      independent of number of processors. 
      TU_1 and TU'_1 gives the sequential computation power of the two
      machines. GS and GS' gives their computation power variation with
      parallel processing. 

      The usefulness of speedup is its ability to show an algorithm, 
      architecture's potential of parallel processing.

---------------------------------------------------------------------------
>  (3) Looked at in another way, the GS metric uses different time units
>      for different computers. Such numbers cannot be directly compared
>      across computers, and to do so is like comparing the numerical values
>      of speeds of cars measured in different units, m.p.h., f.p.s, cm/s,
>      in order to decide which is the fastest. In both cases such comparisons
>      are not comparing like with like, and are invalid. More confusing
>      still, the time unit changes with the number of processors, making
>      GS values incomparable even for measurements on the same computer 
>      for different numbers of processors.
---------------------------------------------------------------------------

       Based on the reasons given above, I don't agree these conclusions. 
       The TU_1 is measured with the same unit. It does not change with 
       the number of processors. 

Xian-He Sun