|
Abstract : |
We present a variation of the partitionmethod for solving m th-order linear recurrences that is well-suited to vector multiprocessors. The algorithm fully utilizes both vector and multiprocessor capabilities, and reduces the number of memory accesses as compared to the more commonly used version of the partition method. Our variation uses a general loop restructuring technique called loop raking. We describe an implementation of this technique on the CRAY Y-MP, and present performance results on first- and second-order linear recurrences, as well as on Livermore loops 5, 11 and 19, which are based on linear recurrences. On a single processor of the Y-MP our implementations run between 1.5 and 4 times faster than the corresponding, |
