Subject: More Questions to Sun on GS

From: [email-masked]
Date: Wed, 16 Jun 93 11:11:10 GMT

REPLY TO Xian-He SUN
                  --------------------
                   from Roger Hockney
                   ------------------
Thank you for your efforts to explain Generalised Speedup to me.  I
think that I am getting there slowly, but I think we start from rather
different perspectives with probably different hidden assumptions.
Your answers have in fact raised more questions, which I will try to keep
to the minimum. So, if you will bear with me a little longer ...
  (1) We can express generalised speedup as a scaled inverse-time
      metric, as follows:
                       TU                     W(N;p) * T(N;1)
           GS(N;p) = --------     where  TU = ---------------
                      T(N;p)                      W(N;1)
      Here TU defines the unit of time measurement.
  (2) The key question from my view point is:
           Does TU change when one calculates GS for two different
           computers, and when one is comparing the same benchmark 
           and the same problem size ?
  (3) What do you mean by asymptotic performance?
  (4) How does one calculate and or measure 
               W(N;p),   W(N;1)  and T(N;1)
      and on what do they depend, see question (6)?
  (5) Showing Dependence
         If we adopt a useful convention, and use the symbols: 
         A or B to describe the computer and software being benchmarked
         X or Y ............... benchmark being timed
         N or M ............... problem size
         p or q ............... number of processors
           *    to mean any value 
      We can show dependence with 4 parameters. Thus for the elapsed
      time of the benchmark, we have in general
         T(A,X:N;p) time for p-processors on computer A with benchmark
                    X of problem size N.
      It is convenient to keep this ordering and punctuation of the 
      parameters and show explicitly a non-dependence with the wild 
      any-value symbol *
      e.g (a) Temporal Performance can be written with full dependence
              explicitly:
                     R_T(A,X:N;p)= TU(*,*:*;*)/T(A,X:N;p)
              because TU=1 identically.
          (b) Benchmark Performance can be written:
                     R_B(A,X:N;p)= TU(*,X:N;*)/T(A,X:N;p)
              because TU=F_B(N) for any benchmark X, but there is no 
              dependence of TU on the computer or the number of 
              processors.
     (6) Can you please express the dependence of the following, using
         the above notation:
             W(?,?:N;p)  does the p-processor work depend on the computer 
                         and benchmark      
             W(?,?:N;1)  ........ 1-processor ...........................
             T(?,?:N;1)  .................... time ......................
             TU(?,?:?;?) ?
I hope the above questions are not too much to ask, but their answers would
clarify a lot to me.  Thank you,   Roger Hockney.

---

From: Sun Xian-He <[email-masked]>
Date: Wed, 16 Jun 93 14:20:58 -0400

John Gustafson and me proposed the generalized speedup metric in 1991.
In our original paper, we didn't give implementation details. 
With a partner, I am working on a paper on generalized speedup and
scalability. Using experimental results on KSR, we will explain
all the details and give a comparisons between traditional and 
generalized speedup. Since Roger Hockney has asked me some very 
precise, thoughtful questions on the net. I will use some of our 
unpublished results to answer his questions. I will appreciate if
the readers on this net could reference the source when any of the
results would be used.

>                  REPLY TO Xian-He SUN

            The two equations are correct, though the notations could
            be improved to make the relations more clear. For me, I would 
            rather use W(p), W(1), T(p;p),
            and T(1;1) to replace W(N;p), W(N;1), T(N;p), and T(N;1)
            respectively. W(p) is the problem size (in float-count) when p 
            processors used. W(1) is the problem size when single processor
            used. The problem size (or work) could be a function of some
            parameter, N, but it is not important here. With these new
            notations, we have

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

            Let 
                m = W(p)/W(1)
            then
                TU = m *  T(1;1).

            Let 
                T(p;1) = m* T(1;1), where  T(p;1) is the single processor
             execution time for solving problem size W(p). Then

                      TU       m * T(1;1)        T(p;1)
           GS(p) = -------- =  ------------ =  ------------ = TS(p)
                      T(p;p)       T(p;p)        T(p;p)

            TS is the traditional speedup. The above equation gives the
            relation between GS and TS. In general, measured T(p;1) may be
            not equal to m * T(1;1). GS can be seen as a TS in which the
            T(p;1) is given by m * T(1;1). If single processor speed is 
            independent of problem size, the measured T(p;1) is equal to
            m * T(1;1).

>           and the same problem size ?

            W(1)/T(1;1) is a fraction of the asymptotic speed. 
            Asymptotic speed is machine dependent. So, TU may be
            different for different computers. Speed is defined
            as work/time.

>  (3) What do you mean by asymptotic performance?

            Asymptotic speed is the best achieved speed of your application 
            on a single processor. Without virtual memory, in general,
            it is the achieved speed when the memory is full filled.

>      and on what do they depend, see question (6)?

            W(1), T(1;1) are determined by the asymptotic speed. W(p) 
            depends on how do you scale the problem size.

>             W(?,?:N;p)  does the p-processor work depend on the computer 

              The user has the freedom to scale the problem size. If the 
              the problem size is fixed, the p-processor work does not
              depend on the computer and benchmark. If the problem size
              is scaled up with time or memory constrains, the p-processor
              work depends on the computer and benchmark.

>             W(?,?:N;1)  ........ 1-processor ...........................

                 W(A;X;N;1)

>             T(?,?:N;1)  .................... time ......................

                 T(A,X,N,1)

>             TU(?,?:?;?) ?

                 TU(A;X;N;q) in general. TU(A;X;*,q) if problem size is fixed.

The above are my interpret of the generalized speedup. I regret that
I didn't discuss this issue with Roger Hockney at the Supercomputing'92. I
would like to thank Roger for his consideration of generalized speedup.

Xian-He Sun
=======================   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]

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