Compiling techniques for first-order linear recurrences on a vector computer

Abstract

Linear recurrences are the most important class of non-vectorizable problems in typical scientific/engineering calculations. This work discusses high performance methods for solving first-order linear recurrences on a vector computer, investigates automatic transformations, and develops the compiling techniques for first-order linear recurrence problems.These results show that the improved vector code generated by the vectorizing compiler run at the rate of 150 MFLOPS (million floating operations per second), in the case of the moderate loop lengths (>1000), and at the rate of over 200 MFLOPS, in the case of the long loop lengths (>10000), on the HITAC S-820 supercomputer. Also, overall performance improvements of 69% in the 14 Lawrence Livermore Loops and 25% in the 24 Lawrence Livermore Loops, as measured by the harmonic mean, are attained.