Subject: Low Level Benchmarks

From: Charles Grassl <[email-masked]>
Date: Mon, 26 Jan 1998 10:21:23 -0600 (CST)

To:      Parkbench interests
From:    Charles Grassl
Subject: Low Level benchmarks

Date:    26, January, 1998

A short review of where we have been and decided:

Last year we agreed (via email exchanges) that the Parkbench Low Level
benchmark suite is not intended to be an -MPI- -test- suite.  There was a
consensus that we intended to measure low level performance, not algorithm
design or implementation.  This is why the Pallas benchmark, though
useful for testing the performance of several important MPI functions,
is not the basic low level test which we desire.  (I believe that the
performance measurement of the MPI functions is a worthwhile project for
this group, but it needs to be separate from the low level benchmarks.)

At the May, 1997 Parkbench meeting in Knoxville, TN, we unanimously
decided that the measurement and analysis (fitting) portions of the
COMMS programs would be made into a separate program.  This from Michael
Berry's minutes (23 May 1997):

  After more discussion, the following COMMS changes/outputs were
  unanimously agreed upon:

	  1.  Maximum bandwidth with corresp. message size.
	  2.  Minimum message-passing time with corresp. message
	      size.
	  3.  Time for minimum message length (could be 0, 1, 8,
	      or 32 bytes but must be specified).
	  4.  The software will be split into two program: one
	      to report the spot measurements and the other for
	      the analysis.

Some of the objections with the Parkbench Low Level codes are that they
are difficult to build, run and analyze.  This attributable to their
organization and design.  Separating the analysis would greatly simply
the programs, but the programs still need to be rewritten.

I include in this email message a simple replacement code for COMMS1.
It uses the "back and forth" methodology, reports maximum and minimum
times with corresponding sizes and and does not include "analysis".
It is equivalent to the measurement portion of COMMS1, though it is much
simpler and easier to use.

I will comment on the experimental methodology used in this program.

 - The reported times in standard out are actual round trip times.  It is
   a poor experimental practice to modify raw measurements too early.
   We should not mix measured times with derived times.  The practice
   leads to confusion and errors (witness the Pallas benchmark code and
   and an earlier version of Parkbench).  If we desire to divide the
   times by two (because of the round trip), then this should be done
   in a analysis portion.  Otherwise we misrepresent round trip times
   as actual single trip times, which hay are not.

 - All times are saved and written to unit 7.  The reported times
   in standard out are the first and the last measurements for each
   message size.  The experimental principle is that no data should be
   discarded with out analysis.  We can use statistical analysis or
   graphics or fitting routines to analyze the raw output.  (I favor
   graphics and statistical analysis.)  If we look at the raw output,
   we will see interesting features, such as the actual "warm up" count
   (usually five or less repetitions) and the distribution of times
   (not Gaussian!).

 - Each repetition is individually timed.  If the timer does not have
   adequate resolution, then the times for a number of repetitions, from
   two to all, can be aggregated and used.  This aggregation can be done
   in the analysis phase.  (Most computers should be able to time and
   resolve single round trip messages.)  This aggregation should not be
   done before adequate analysis or evidence that it needs to be done.

 - Each message size is tested the same number of repetitions.  We prefer
   to keep this number a constant so that the experimental sampling
   error (proportional to 1/sqrt[repetitions]) is the same for each
   message size.  Also, it is difficult to cleanly and simply adjust
   the repetition count relative to the message size.

I also have one replacement program for both COMMS2 and COMMS3 (note
that the COMMS2 measurement is a subset of COMMS3 measurements).
More on that later.

Charles Grassl
SGI/Cray Research
Eagan, Minnesota USA

-----------------------------------------------------------------------

      program       Single ! Compile: f90 file.f -l mpi
      character*40  Title
      data          Title/' Single Messages --- MPI'/

      integer       log2nmax,nmax,n_repetitions
      parameter     (log2nmax=18,nmax=2**log2nmax,n_repetitions=50)
      integer       n_starts,n_mess
      parameter     (n_starts=2,n_mess=2)
      include       'mpif.h'
      integer       ier,status(MPI_STATUS_SIZE)
      integer       my_pe,npes
      integer       log2n,n,nrep,i
      real*8        t_call,timer,tf(0:n_repetitions)
      real*8        A(0:nmax-1)
      save          A

      call mpi_init( ier )
      call mpi_comm_rank(MPI_COMM_WORLD, my_pe, ier)
      call mpi_comm_size(MPI_COMM_WORLD, npes, ier)

      radian=1
      do i=0,nmax-1
        A(i) = acos(radian)*i
      end do
        
      tf(0) = timer()
      do nrep=1,n_repetitions
        tf(nrep) = timer()
      end do
      t_call=(tf(n_repetitions)-tf(0))/n_repetitions

      if (my_pe.eq.0) then
        call table_top(Title,npes,n_starts,n_mess,n_repetitions,t_call)
      end if

      do log2n=0,log2nmax
        n = 2**log2n
        call mpi_barrier( MPI_COMM_WORLD, ier )
        tf(0) = timer()
        do nrep=1,n_repetitions
          if (my_pe.eq.1) then
            call MPI_SEND(A,8*n,MPI_BYTE,0,10,MPI_COMM_WORLD,ier)
            call MPI_RECV(A,8*n,MPI_BYTE,0,20,MPI_COMM_WORLD,status,ier)
          end if
          if (my_pe.eq.0) then
            call MPI_RECV(A,8*n,MPI_BYTE,1,10,MPI_COMM_WORLD,status,ier)
            call MPI_SEND(A,8*n,MPI_BYTE,1,20,MPI_COMM_WORLD,ier)
          end if
          tf(nrep) = timer()
        end do
        if (my_pe.eq.0) then
          call table_body(8*n,n_mess,n_repetitions,tf,t_call)
        end if
      end do

      call mpi_finalize(ier)
      end
      subroutine table_top( Title,npes,
     .     n_starts,n_mess,n_repetitions,t_call)
      integer       M
      parameter     (M = 1 000 000)
      character*40  Title
      integer       npes,n_starts,n_mess,n_repetitions
      real*8        t_call

      write(6,9010) Title,npes,n_starts,n_mess,n_repetitions,t_call*M

      return
9010  format(//a40,
     .  // ' Number of PEs:  ',i8
     .  // ' Starts:         ',i8,
     .   / ' Messages:       ',i8,
     .   / ' Repetitions:    ',i8,
     .   / ' Timer overhead: ',f8.3,' microsecond',
     .  // 8x,'            First      ',
     .        '              Last     ',
     .   /'  Length',2x,2('      Time       Rate ',1x),
     .   /' [Bytes]',2x,2(' [Microsec.] [Mbyte/s]',1x),
     .   /' ',8('-'),2x,2(21('-'),2x))
      end
      subroutine table_body(n_byte,n_mess,n_repetitions,tf,t_call)
      integer       M
      parameter     (M = 1 000 000)
      integer   n_byte,n_mess,n_repetitions,i
      real*8    tf(0:n_repetitions)
      real*8    t_call
      real*8    t_first,t_last

      t_first = (tf(1)-tf(0))-t_call
      t_last  = (tf(n_repetitions)-tf(n_repetitions-1))-t_call
      write(6,9020) n_byte,t_first*M,n_mess*n_byte/(t_first*M),
     .                      t_last *M,n_mess*n_byte/(t_last *M)
      write(7) n_byte,n_repetitions,n_mess
      write(7) ((tf(i)-tf(i-1))-t_call,i=1,n_repetitions)

      return
9020  format(i8,     2x,2(f10.1,1x,f10.0,2x))
      end

---

From: Mark Baker <[email-masked]>
Date: Mon, 26 Jan 98 17:23:08 GMT

This came direct to me... The rest of Parkbench are probably interested
in Bodo's comments.

Mark

--- On Mon, 26 Jan 1998 08:28:15 -0800  Bodo Parady - SMCC Performance Development 
<[email-masked]> wrote:
> The key items to find are:
> 
>         Lock time (defined as time to release a lock remotely)
>             Example would be reader spinning on memory, waiting
>             for change in memory word, or receipt of interrupt.
>             This is the effective ping-pong half time.  Sadly
>             subroutine and library call overhead can render
>             this result meaningless.
> 
>             Measuring one way rates is no good here since the response
>             time must be factored in.  This is a two-way transfer
> 
>         Channel rate (defined as large block transfer rate).
> 
>         Block size at half channel rate.
> 
>         Block size at twice lock time latency.
> 
>         Full curve, stepping at 1, 2, 4, 8, 16, ..., 2*n byte block sizes
>                 at full issue rate.  This is probably the least important
>                 since it involves coalescence of transmitted data.
> 
> The fear is that given the limitations of MPI/PVM, and to some degree
> of C and Fortran that accurate measures of these quantities may
> not be practical.
> 
> Regards.
> 
>                 Bodo Parady
> 
> Mark Baker wrote:
> 
> > Charles,
> >
> > Thanks for your thoughts and experiences with the Pallas PMB codes -
> > I will  forward them to the authors...  The main points in favour of
> > the PMB codes are that they are in C and potentially produce results
> > for a variety of MPI calls... Obviously if the results they produce are
> > flawed...
> >
> > Regarding new low-level codes I would be in favour of taking up your
> > kind offer of writing a set of codes in C/Fortran. I guess the main
> > problem is getting a concensus with regards methodology and measurements
> > that are used with these codes.
> >
> > Maybe we can decide that a number of actions should be undertaken...
> >
> > 1) It seems clear that no one is 100% happy with the current version
> >    of the low-level codes. So, this implies that they need to be
> >    replaced !?
> >
> > 2) If we are going to replace the codes we can go down a couple of routes;
> >    start from scratch, replace with Roger's new codes or some combination of
> >    both...
> >
> > 3) I would be happy to see us start from scratch and  create
> >    C/Fortran codes where the methodology and design of each can be
> >    "hammered out" by discussion first and then implemented
> >    (and iterated as necessary).
> >
> > 4) Assuming that we want to go down this route, I suggest we make a starting
> >    point of Charles' "suggestions and requirements for the low level
> >    benchmark design" - towards the end of this email. I am happy to
> >    put these words on the web and update/change them as our dicussions
> >    evolve...
> >
> > 5) Charles has offered his services to help write/design/test these new codes -
> >    I'm willing to offer my services in a similar fashion. I'm sure that others
> >    interested in the low-level codes could contribute something here as well.
> >
> > Overall, it seems clear to me that we have enough energy and manpower to
> > produce a new set low-level codes whose methodology and design is correct
> > and relevant to todays systems...
> >
> > I look forward to your comments...
> >
> > Regards
> >
> > Mark
> >
> > --- On Thu, 15 Jan 1998 11:11:39 -0600 (CST)  Charles Grassl <[email-masked]> wrote:
> > >
> > > To:      Parkbench interests
> > > From:    Charles Grassl
> > > Date:    15 January, 1998
> > > Mark, thank you for pointing us to the PMB benchmark.  It is well written
> > > and coded, but has some discrepancies and shortcomings.  My comments
> > > lead to suggestions and recommendation regarding low level communication
> > > benchmarks.
> > >
> > > First, in program PMB the PingPong tests are twice as fast (in time)
> > > as the corresponding message length tests in the PingPing tests (as run
> > > on a CRAY T3E).  The calculation of the time and bandwidth is incorrect
> > > by a factor of 100% in one of the programs.
> > >
> > > This error can be fixed by recording, using and reporting the actual
> > > time, amount of data sent and their ratio.  That is, the time should not
> > > be divided by two in order to correct for a round trip.  This recorded
> > > time is for a round trip message, and is not precisely the time for
> > > two messages.  Half the round trip message passing time, as reported in
> > > the PMB tests, is not the time for a single message and should not be
> > > reported and such.  This same erroneous technique is used in the COMMS1
> > > and COMMS2 two benchmarks.  (Is Parkbench is responsible for propagating
> > > this incorrect methodology.)
> > >
> > > In program PMB, the testing procedure performs a "warm up".  This
> > > procedure is a poor testing methodology because is discards important
> > > data.  Testing programs such as this should record all times and calculate
> > > the variance and other statistics in order to perform error analysis.
> > >
> > > Program PMB does not measure contention or allow extraction of network
> > > contention data.  Tests "Allreduce" and "Bcast" and several others
> > > stress the inter-PE communication network with multiple messages,
> > > but it is not possible to extract information about the contention from
> > > these tests.  The MPI routines for Allreduce and Bcast have algorithms
> > > which change with respect to number of PEs and message lengths,  Hence,
> > > without detailed information about the specific algorithms used, we cannot
> > > extract information about network performance or further characterize
> > > the inter-PE network.
> > >
> > > Basic measurements must be separated from algorithms.  Tests PingPong,
> > > PingPing, Barrier, Xover, Cshift and Exchange are low level.  Tests
> > > Allreduce and Bcast are algorithms.  The algorithms Allreduce and Bcast
> > > need additional (algorithmic) information in order to be described in
> > > terms of the basic level benchmarks.
> > >
> > >
> > > With respect to low level testing, the round trip exchange of messages,
> > > as per PingPing and PingPong in PMB or COMMS1 and COMMS2, is not
> > > characteristic of the lowest level of communication.  This pattern
> > > is actually rather rare in programming practice.  It is more common
> > > for tasks to send single messages and/or to receive single messages.
> > > In this scheme, messages do not make a round trip and there is not
> > > necessarily caching or other coherency effects.
> > >
> > > The single message passing is a distinctly different case from that
> > > of round trip tests.  We should be worried that the round trip testing
> > > might introduce artifacts not characteristic of actual (low level) usage.
> > > We need a better test of basic bandwidth and latency in order to measure
> > > and characterize message passing performance.
> > >
> > >
> > > Here are suggestions and requirements, in an outline form, for a low
> > > level benchmark design:
> > >
> > >
> > >
> > >     I. Single and double (bidirectional) messages.
> > >
> > >        A. Test single messages, not round trips.
> > >          1. The round trip test is an algorithm and a pattern.  As
> > >             such it should not be used as the basic low level test of
> > >             bandwidth.
> > >          2. Use direct measurements where possible (which is nearly
> > >             always).  For experimental design, the simplest method is
> > >             the most desirable and best.
> > >          3. Do not perform least squares fits A PIORI.  We know that
> > >             the various message passing mechanisms are not linear or
> > >             analytic because different mechanisms are used for different
> > >             message sizes.  It is not necessarily known before hand
> > >             where this transition occurs.  Some computer systems have
> > >             more than two regimes and their boundaries are dynamic.
> > >          4. Our discussion of least squares fitting is loosing tract
> > >             of experimental design versus modeling.  For example, the
> > >             least squares parameter for t_0 from COMMS1 is not a better
> > >             estimate of latency than actual measurements (assuming
> > >             that the timer resolution is adequate).  A "better" way to
> > >             measure latency is to perform addition DIRECT measurements,
> > >             repetitions or otherwise, and hence decrease the statistical
> > >             error.  The fitting as used in the COMMS programs SPREADS
> > >             error.  It does not reduce error and hence it is not a
> > >             good technique for measuring such an important parameter
> > >             as latency.
> > >
> > >        B. Do not test zero length messages.  Though valid, zero length
> > >           messages are likely to take special paths through library
> > >           routines.  This special case is not particularly interesting or
> > >           important.
> > >           1. In practice, the most common and important message size is 64
> > >              bits (one word).  The time for this message is the starting
> > >              point for bandwidth characterization.
> > >
> > >        D. Record all times and use statistics to characterize the message
> > >           passing time.  That is, do not prime or warm up caches
> > >           or buffers.  Timings for unprimed caches and buffers give
> > >           interesting and important bounds.  These timings are also the
> > >           nearest to typical usage.
> > >           1. Characterize message rates by a minimum, maximum, average
> > >              and standard deviation.
> > >
> > >        E. Test inhomogeneity of the communication network.  The basic
> > >           message test should be performed for all pairs of PEs.
> > >
> > >
> > >    II. Contention.
> > >
> > >        A. Measure network contention relative to all PEs sending and/or
> > >           receiving messages.
> > >
> > >        B. Do not use high level routines where the algorithm is not known.
> > >           1. With high level algorithms, we cannot deduce which component
> > >              of the timing is attributable to the "operation count"
> > >              and which is attributable to the actual system (hardware)
> > >              performance.
> > >
> > >
> > >   III. Barrier.
> > >
> > >        A. Simple test of barrier time for all numbers of processors.
> > >
> > >
> > >
> > >
> > > Additionally, the suite should be easy to use.  C and Fortran programs
> > > for direct measurements of message passing times are short and simple.
> > > These simple tests are of order 100 lines of code and, at least in
> > > Fortran 90, can be written in a portable and reliable manner.
> > >
> > > The current Parkbench low level suite does not satisfy the above
> > > requirements.  It is inaccurate, as pointed out by previous letters, and
> > > uses questionable techniques and methodologies.  It is also difficult to
> > > use, witness the proliferation of files, patches, directories, libraries
> > > and the complexity and size of the Makefiles.
> > >
> > > This Low Level suite is a burden for those who are expecting a tool to
> > > evaluate and investigate computer performance.  The suite is becoming
> > > a liability for our group.  As such, it should be withdrawn from
> > > distribution.
> > >
> > > I offer to write, test and submit a new set of programs which satisfy
> > > most of the above requirements.
> > >
> > >
> > > Charles Grassl
> > > SGI/Cray Research
> > > Eagan, Minnesota  USA
> > >
> >
> > ---------------End of Original Message-----------------
> >
> > -------------------------------------
> > CSM, University of Portsmouth, Hants, UK
> > Tel: +44 1705 844285    Fax: +44 1705 844006
> > E-mail: [email-masked]
> > Date: 01/26/98 - Time: 10:14:38
> > URL http://www.sis.port.ac.uk/~mab/
> > -------------------------------------
> 
> 
> 
> 

---------------End of Original Message-----------------

-------------------------------------
CSM, University of Portsmouth, Hants, UK
Tel: +44 1705 844285	Fax: +44 1705 844006
E-mail: [email-masked]
Date: 01/26/98 - Time: 17:23:08
URL http://www.sis.port.ac.uk/~mab/
-------------------------------------