Speedup of band linear recurrences in the presence of resource constraints
Haigeng Wang, Alexandru Eugen Nicolau · 1992
An m-th order linear recurrence system of N equations computes x i = c i + P j=i0m i01 a ij x j for 1 i N . Linear recurrences have a role of central importance in computer design, numerical analysis, program analysis, digital signal processing and many non-numerical algorithms. However, programs containing band linear recurrences are difficult to significantly parallelize due to loop-carried dependences. We present a new method for systematically approaching the optimal parallel schedules for computing mth-order linear recurrences with a fixed number of processors p independent of problem size N . Using our method, we first derive two kinds of parallel schedules, called the pipelined schedules and the exact schedules, for parallel evaluation of band linear recurrences. Our schedules have better execution times than the fastest previously published parallel schedules for p ? m 1. In particular, the exact schedules achieve an execution time of (2m 2 + 3m)N p + (m(m+1)(2m+1)) 2...