Pipelined evaluation of first-order recurrence systems
Lionel Ming-shuan Ni, Kai Hwang · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1983
A first-order recurrence is a sequence of evaluations in which the value of the latest term depends on the previously computed term. Due to the sequential nature, it presents a special problem for parallel processing. For most scientific applications, only the final term is desired. This paper presents various strategies to evaluate the final value of first-order recurrence using pipeline. Two methods, symmetric reduction and asymmetric reduction, are proposed and compared in a static pipeline environment. The pipeline utilization can be further improved when multiple recurrence systems are evaluated. 13 references.