🚀 go-pugleaf

In article <l7gi3fINNmsd@utkcs2.cs.utk.edu>, eijkhout@cupid.cs.utk.edu 
(Victor Eijkhout) writes...
> 
>I would like to get an idea of the difference in performance
>between inner products
> 
>       do i=1,n    x = x + a(i)*b(i)
> 
>and axpy operations
> 
>       do i=1,n   x(i) = x(i) + a*b(i)
> 
>which both have the same number of operations, but the inner product
>has an accumulation, which traditionally seems to be an
>unvectorizable idea.
> 

I tried this with VAX FORTRAN-HPO; as long as one uses the 
/ASSUME=NOACCURACY_SENSITIVE qualifier so that the dot product's reduction
transformation can be performed (the default is ACCURACY_SENSITIVE which
disables transformations that could yield different results than scalar
execution), both forms vectorize very nicely.  (The dot product form,
of course, has a final reduction step that the "axpy" form doesn't need.)
The actual vector mul-add sequences are essentially the same between the two.

Of course, one can also use the BLAS SDOT and SAXPY intrinsics, which
VAX FORTRAN-HPO will expand and vectorize (and parallelize, if you like.)

Steve Lionel                    lionel@quark.enet.dec.com
SDT Languages Group
Digital Equipment Corporation
110 Spit Brook Road
Nashua, NH 03062

eijkhout@cupid.cs.utk.edu (Victor Eijkhout) writes:
: Yo hardcore number crunchers!
: 
: I would like to get an idea of the difference in performance
: between inner products
: 
:        do i=1,n    x = x + a(i)*b(i)
: 
: and axpy operations
: 
:        do i=1,n   x(i) = x(i) + a*b(i)
: 
: which both have the same number of operations, but the inner product
: has an accumulation, which traditionally seems to be an
: unvectorizable idea.
: 
: Please post if you know how your favourite vector processor / vector
: chip / Risc processor / whatever performs differently / the same
: on the two.
: 
: My guess would be that the difference between these two operations
: can nowadays be conveniently neglected, but I might be wrong.
: 
: Victor.

You're right, inner products aren't directly vectorizable, but there 
are some good reasons why you would want to organize, say, a matrix 
multiply around an inner product, rather than an 'axpy on a modern 
RISC workstation.

The first reason is memory bandwidth.  If you look at the two loops above,
you can see that the first one performs two memory references per
iteration-- two loads, and the second performs three-- two loads and
a store.  Current RISC processors can do at most one memory operation
per clock cycle, so a savings in memory traffic gives you a chance to
run into some other barrier.

The second reason is that the floating point units on many newer RISC
processors feature a "multiply and accumulate" instruction.  This 
can do a floating point addition and multiply in the same time it
takes to do one of them alone.  That is, you get two flops per
clock, rather than one, if you can find a use for this instruction.
(By the way, this is the reason that many vendors quote floating point
rates that are twice the clock rate-- they are saying that if you
can use a "multiply and accumulate" instruction every cycle, you 
will get, say, 100 mflops on a 50 Mhz computer).  An inner product 
is custom made for a "multiply and accumulate" instruction, though in
this case you are still memory bandwidth limited.

On the other hand, the 'axpy version is better on some vector 
supercomputers.  Take the Cray Y-MP as an example.  It can perform 
*three* memory operations per clock (per processor)-- two loads and 
a store.  It also has two independent pipelined vector units.  
Because the 'axpy is fully vectorizable, and because there is enough 
memory bandwidth to go around, it will run better on a big vector 
supercomputer than the inner product.  

-Kevin
-- 
   \      //   //                       General purpose computer wizards.
    \    //   T E C H N O L O G I E S   Kevin Dowd, dowd@wisper.com    
     \  //\  // ` ((   // ) ((/  //''   Wethersfield, Connecticut
      \//  \// //  )) //    ((/ //      USA (203) 257-7670 

In article <1992Aug3.171551.27311@wisper.com>, dowd@wisper.com (Kevin Dowd) writes:
|> eijkhout@cupid.cs.utk.edu (Victor Eijkhout) writes:
|> : Yo hardcore number crunchers!
|> : 
|> : I would like to get an idea of the difference in performance
|> : between inner products

|> : and axpy operations
|> : 
|> :        do i=1,n   x(i) = x(i) + a*b(i)


|> : My guess would be that the difference between these two operations
|> : can nowadays be conveniently neglected, but I might be wrong.


You might be able to ignore it on some machines, but only because the
compiler is smart enough to recognize what you are doing and emit some
substitute code for you, or call a library routine for you.

|> : 
|> : Victor.
|> 
|> You're right, inner products aren't directly vectorizable, but there 
|> are some good reasons why you would want to organize


There is an art to doing such calculations efficiently.  Start by 
reading the publications of Jack Dongarra, et al., on BLAS{1,2,3},
Linpack, and LAPACK, if you are interested.

In the meantime, if you want to do matrix multiplies fast, get the
BLAS3 routine SGEMM.  The default version is pretty good, but the
real payoff is that some machines (Cray, Convex, IBM RS/6000) have
hand coded SGEMM routines which are optimized for their particular
architectures, so that *you* don't have to worry about it.

For example, the Cray has high memory bandwidth, and doesn't have cache.
So, with an appropriate routine, you can stream operands through at full
speed on the entire matrix.  The IBM RS/6000, on the other hand, has
a limited mapped area of memory and a limited cache.  So, you want a 
block oriented version of SGEMM for the IBM, which would have some
unnecessary loop/vector startup on the Cray.  The easiest way you can
avoid having to delve into the subtleties of a particular system is
to use the BLAS3 and LAPACK codes you need to avoid having to duplicate
the clever hand-coding effort that the vendors have already accomplished.




-- 
  Hugh LaMaster, M/S 233-9,     UUCP:      ames!lamaster
  NASA Ames Research Center     Internet:  lamaster@ames.arc.nasa.gov
  Moffett Field, CA 94035-1000  Or:        lamaster@george.arc.nasa.gov 
  Phone:  415/604-1056                     #include <usenet/std_disclaimer.h>