Subject: Reply to Ron Sercely regarding COMMS1

From: Roger Hockney <[email-masked]>
Date: Fri, 13 Dec 1996 13:52:03 +0000

I would like to thank Ron Sercely for bringing to our attention the problems 
with the COMMS1 benchmark (which will equally apply to COMMS2). I have spent 
about a week considering his data and isolating the cause of the parametric 
fitting problem. I believe that I have found a solution to the problem which 
means only a minor change to the existing benchmark.

The assumption made by the parametric fitting part of the COMMS1 benchmark is 
that the time, t, can be represented approximately as a linear function of
message length, n, i.e.

                      t=(n+nhalf)/rinf                                  (1)

which implies that the bandwidth is given by

                                    rinf
                       r = n/t = ----------                             (2)
                                 (1+nhalf/n)

This type of variation is a very good fit to most of the data that I have seen
and is even a reasonable fit to the data given by Ron both for n<=576 and for
n>=577, as can be seen in the log(r) vs log(n) graph is available on my Web 
page at URL:

      http://www.minnow.demon.co.uk/Pbench/emails/sercely1.htm

This graph shows the measured data taken from Ron's e-mail as green circles, 
and two fits using the formula (2) above shown as dashed  lines. These are 
NOT the fit lines produced by the current COMMS1, but show that the 
functional form (2) can fit Ron's data if rinf and nhalf are chosen sensibly. 

The falloff of bandwidth in the measured data for large r, mentioned by Ron, 
is only small (about 20%) and can be satisfactorily fitted by (2) which 
is roughly constant in this region. 

The problem is not that the above functional form is unsatisfactory, but 
that the current COMMS1 fitting program does not produce sensible values for 
the parameters (rinf,nhalf) when the range of time values becomes very 
large such as e+6 and the bandwidth decreases with increasing large n, 
as in his data.

The rest of this note is concerned with explaining how COMMS1 can be easily 
modified to produce sensible values of rinf and nhalf even in the case of 
such data. The graph shows the result of the proposed modified fitting 
procedure which I regard as satisfactory for all message lengths.

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

The reasons for the bad fit are as follows: 

Current Method
--------------
The (rinf,nhalf) performance parameters are determined in the current COMMS1 
by fitting the straight line (1) to the measured t vs n data in such a way as 
to minimise the sum of the squares of the ABSOLUTE difference (or error) 
between the measured and predicted value from (1). This is the normal way of 
fitting straight lines to measured data and is called linear regression by 
the statisticians or linear least-squares fitting by others.

I have checked that the current COMMS1 produces the correct parameters using 
the above procedure by comparing the results with those produced by the Jandel 
SigmaPlot (SP) package that I happen to use. Both SigmaPlot and COMMS1 produce 
a negative nhalf=-33310 [SP value -33567 which I regard as agreement]. 

The curve from (2) with these parameters fits the last six data values 
(n>=3e+5) very well but gives silly even negative values for r for smaller 
values of n. But I emphasise these are the correct parameter values if one 
sets the condition to minimise the sum of the squares of the ABSOLUTE error, 
and that this procedure has worked satisfactorily with earlier versions of 
COMMS1 which used a maximum message length of about 40000. 

The problem with using the absolute error is that data values associated with 
the larger n-values are over emphasised in the sum being minimised with the 
effect that values for lower n are virtually ignored. Hence the parameters 
give a good fit for large n and can give a bad fit for small n. But this is 
what you get with standard unweighted linear least squares.

Weighted Least Squares
----------------------
This is evidently a well known problem in curve fitting with data that ranges 
in value over many orders of magnitude, as it does NOW with COMMS1. The
solution
is to use weighted least squares (or regression) in which each value in the
sum 
to be minimised is multiplied by a weight in such a way as to make each term
of 
the sum of comparable magnitude and therefore of comparable importance in the 
fitting condition. If the weights are taken as the inverse square of the
measured
values t_i, then the sum of the squares of the RELATIVE (rather than absolute) 
error is minimised. When one thinks about it this is what we really want to
do: 
to be able to predict t with a certain relative error over the whole range. We 
would be happy to know that t was fitted to within say 20%, but this would
mean 
an absolute error that could vary by six orders of magnitude if the values of
t 
varied by that amount, as they typically do. So we cannot achieve the desired 
result by demanding a roughly even absolute error as is done in the current 
benchmark. Using the relative error has the additional advantsge that if t is 
known to within a certain relative error, then r is also known to the same 
relative error.

If weighted least squares is used with Ron's data to minimise the relative
error 
as described above, we obtain rinf=2.15e8 and nhalf=+6494 as the best fit 
parameters. Note that nhalf is now positive, that there are no negative values 
of r, and that now the fitted curve is held close to all the data values 
including those between n=577 and n=10000 that were previously not fitted at
all.
This is seen as the red dashed line (labelled fit8) on the log(r) vs log(n) 
graph that can be found on the web page mentioned above. 

Conclusion
----------
The problem of the unsatisfactory calculation of the (rinf,nhalf) performance 
parameters is solved by modifying the least-squares fitting procedure to 
minimise the sum of the squares of the relative rather than the absolute error 
(as the current code does). This requires only a small modification of the 
existing benchmark. I am making these modifications and will test them on the 
Cray T3D at Edinburgh, and also make the revised code available to others for 
evaluation. But give me a few more weeks.

Although the current COMMS1 fitting routine gives satisfactory results for 
message lengths less than about 40000, there is no doubt that the 
curve-fitting procedure within COMMS1 needs to be modified to cope with the 
larger range of message length that are now being tested. I believe that 
the above changes will make the routine much more robust to wide variations 
in time values.

*****************************************************************************
                             RON's OTHER POINTS
*****************************************************************************

>>With the current comms1 and comms2 benchmarks, the results are such non-
sense
>>that we cannot report results, so a prompt resolution is necessary.

Actually the values of rinf reported are quite OK, it is only the nhalf values
that are useless for the reasons given above.

>>                      MY (Ron's) CONCLUSIONS
>>Vendors should report startup for short messages, maximum bandwidth and the
>>message size that produced it, and the result file, only.
>>A plot of the result file should allow a user of the benchmark get the 
>>relevant information from the benchmark.

If the fitting procedure is corrected as proposed above, the example of the 
revised fit to Ron's data shows that there is no need to throw away the 
parametric description which has the following advantages:

(1) Accuracy: The parametric values can be considered as a kind of average
    --------  calculated from all the data values (i.e. their value depends 
    on all the measured values). In the face of experimental error, their 
    values should be intrinsicaly more reliable than a single spot measured 
    value, such as the highest bandwidth observed or time for a zero length 
    message. In much the same way that one would consider the average of a 20 
    measurements of the same quantity to be more reliable than a single spot
    measurement.

(2) Completeness: The parametric values give an approximate fit to all the 
    ------------  measured date, compared to the spot values which only
    give the performance at the two extremes of message length (zero and e+8)

(3) Importance of nhalf: nhalf characterises, in terms of message length, the 
    -------------------  extent to which t0 degrades measured bandwidth. This
    is very important and should appear as part of the result summary.
      
(4) Data Compression: Two numbers, rinf and nhalf, give through equations (1)
    ----------------  and (2) the performance for all message lengths. Or if 
    there are different protocols are used for short and long messages, 4 
    numbers do the job. This contrasts with recording about 22 pairs of (t,n) 
    values or 44 numbers. A data compression of a factor of 10.

(5) Performance understanding: The parameters together with equations
    -------------------------  (1) and (2) can be used in formulae for the 
    performance of more complex codes. This contributes to the understanding 
    of performance and the identification of bottlenecks.

More on the meaning and significance of rinf and nhalf can be found in my 
new book "The Science of Computer Benchmarking, SIAM 1996, in Jack's series 
"Software, Environments, and Tools" at URL:

           http://www.siam.org/catalog/mcc07/hockney.htm

>>                      MY CONCLUSIONS
>>Vendors should report startup for short messages, maximum bandwidth and the
>>message size that produced it, and the result file, only.

>>Four changes are necessary to the benchmarks:
>>1. New ESTCOM routine that does not assume asymtotic behavior.

If this routine is the one that does the least-squares fit, I outline above 
how I think this should be changed.     

>>2. Modified COMMS to correct times based upon total time spent in CHECK.

My comments here have no connection with this point. Perhaps Ron's patch 
addresses this?

>>3. Result Summary should ONLY report startup for short messages, and maximum
>>bandwidth/message size.  Possible instead of fitting for startup time, the
>>measured time for 0 or 1 byte messages should be used

I agree that the Result Summary should be improved, and think we should
include 
both the fitted parameters AND the spot values suggested above. 
I suggest a layout as follows:

------------------------------------------------------------------
                          Result Summary
                          --------------
Short Messages, fit to n <= 576 Byte
Bandwidth fitted to r = pi0*n/(1+n/nhalf)

pi0  = 1.472e5 Hz,   nhalf =  217.020 B 

measured t0 = 5.180e-6 s,  fitted t0 = 6.793e-6 s   
(agreement to 31.1 %)  
                                            
--------------
Long Messages,  fit to n >  576 Byte
Bandwidth fitted to r = rinf/(1+nhalf/n)

rinf = 2.154e+8 B/s, nhalf = 6494.??? B;  

measured r (at n=e+8) = 1.8275e+8 B/s, fitted rinf = 2.154e+8 B/s 
(agreement to 17.9 %)
                                          
-------------------------------------------------------------------
In the case that there is no break in the message transfer protocol, 
"fit to n = 576" and "fit to n >577" in the above format should both be 
replaced by "fit to all data". Then the two formulae give identical results: 
nhalf is the same for both fits and pi0=rinf/nhalf . The reason for 
keeping the two different functional forms even though they are identical 
algebraically is to emphasise the asymptotic form of r = pi0*n for short 
messages (defined as  messages with n < nhalf), and the asymptotic form 
r = rinf for long messages (defined as n > nhalf).
 
In the above revised result summary, I have included the fitting formula 
for convenience and completeness, and used the alternative (pi0,nhalf) 
parametric formula for short messages. This emphasises the linear increase 
of r with n for small n at a rate given by pi0 (units are (B/s) per Byte 
or s^(-1) = Hz).

Note pi0=nhalf/rinf=1/t0(fit). Hence t0(fit)=1/pi0.
Consistency of the fit can be checked by comparing t0(measured) to t0(fit) 
and measured r (at largest n) to fitted rinf. The absolute % difference
is also given.

This layout should satisfy everybody.

Those liking performance parameters can look at the first line of results, 
and those who only believe measured spot values can look at the second line
which also gives a directly comparison of the two approaches.

>>4. Results file should print measured, as opposed to fit bandwidth.

I think BOTH should be included. This means keeping the existing output 
layout and adding a column for the measured bandwidth. The purpose of 
listing the fit values of rinf and nhalf for each value of n is to observe 
how stable these values are as n increases, and therefore how reliable 
they are.
-- 
Roger Hockney.  Checkout my new Web page at URL   http://www.minnow.demon.co.uk
                and link to my new book: "The Science of Computer Benchmarking"
                suggestions welcome. Know any fish movies or suitable links?