Maximal rate pipelined solutions to recurrence problems
Peter Michael Kogge · ACM SIGARCH Computer Architecture News · 1973
An m th order recurrence problem is defined as the computation of X 1 , . . . X N , where X i =f ( a i , X i-1 , . . X i-m ) and a i is a set of parameters. On a pipelined computer, where the total stage delay in computing f is d f time units, the solution output rate is one new X i each d f time unit. This paper describes a method for increasing this rate to 1 per time unit when the function f has certain simple functional properties. The total stage delay and complexity of the resulting pipelines are also described.