Algorithm transformations for unlimited parallelism
Gerhard Paul Fettweis, Lothar Thiele, G. Meyr · 2002
A unified algebraic basis for transforming algorithms to achieve unlimited parallelism is provided. In the case of recursive algorithms, a certain class of algebraic structures is shown to be sufficient for the application of the look-ahead computation. This approach is generalized to matrix-based algorithms where the operations form a semiring. Previously known approaches to speeding up recursions are shown to be special instances of the given approach. A block processing realization corresponding to the logarithmic look-ahead computation is given which is efficient in its area and time requirements.>