SOLVING LINEAR RECURRENCES WITH LOOP RAKING

We present a variation of the partition method for solving linear recu rrences that is well-suited to vector multiprocessors. The algorithm f ully utilizes both vector and multiprocessor capabilities, and reduces the number of memory accesses and temporary memory requirements as co mpared to the more commonly used version of the partition method. Our variation uses a general loop restructuring technique called loop raki ng. We describe an implementation of this technique on the GRAY Y-MP C 90, and present performance results for first- and second-order linear recurrences. On a single processor of the C90 our implementations are up to 7.3 times faster than the corresponding optimized library routi nes in SCILIB, an optimized mathematical library supplied by Gray Rese arch. On four processors, we gain an additional speedup of at least 3. 7. (C) 1995 Academic Press, Inc.