Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!paperboy!hsdndev!cmcl2!lanl!cochiti.lanl.gov!jlg
From: jlg@cochiti.lanl.gov (Jim Giles)
Newsgroups: comp.arch
Subject: Re: Vector vs Cache/Superscalar
Message-ID: <23348@lanl.gov>
Date: 7 May 91 22:00:30 GMT
References: <1991May4.031835.7979@midway.uchicago.edu> <1991May6.035310.26794@marlin.jcu.edu.au> <11921@mentor.cc.purdue.edu>
Sender: news@lanl.gov
Organization: Los Alamos National Laboratory
Lines: 52

In article <1991May6.035310.26794@marlin.jcu.edu.au>, csrdh@marlin.jcu.edu.au (Rowan Hughes) writes:
> [...]
> The latest Fujitsu compiler (for the VP2000 series) will handle 1st order
> backwards recurrence, ie A(I)=A(I-1)+B(I), as well as the usual forward
> recurrence, in full vector mode. Many old scalar problems can now be
> vectorized. I'd be interested to hear if Cray/ETA/Alliant etc have this
> capability too.

First order recurrence can be rewritten using a technique call recursive
doubling (which is, presumably what the Fujitsu compiler is doing automatically).
If you can't get your compiler to do it automatically, use the following
code as a guide to the technique (or read "A Parallel Algorithm for the 
Efficient Solution of a General Class of Recurrence Equations", Kogge, H.S.
and P.M. Stone, IEEE Transactions of Computers, Vol. C-22, No. 8, August 1973,
pp. 786-793) - (yes, the method really _has_ been around for 18 years):

   
      DO 10 i = 1, N
         A(i) = B(i)
  10  continue

      j = 1

  20  IF (j<N) THEN

         DO 30 i = j+1, N
            A(i) = A(i) + A(i-j)
  30     continue

         j = 2 * j

         GO TO 20
      ENDIF

This is Fortran 77 code (with lower case as a readibility extension).
The contents of both DO loops fully vectorize on the Crays, etc.  If the
DO loops are replaced with the Fortran 90 style array assignments:

   A(1:N) = B(1:N)
and
   A(j+1:N) = A(j+1:N) + A(1:N-j)

respectively, then the code will be fully parallel on the Connection Machine.
The 'while' loop is scalar and will execute floor(LOG2(N)) times.

Although it would be nicer if the compiler automatically saw recursions of
this kind and applied this optimization, this is not too bad and gives the
user direct control.  Fujitso apparently already does this, maybe some of the
compilers of the other companies on your list do also (or will soon follow
suit).

J. Giles