The suffix problem can be defined for any semigroup ⟨ S , ○ ⟩ as follows: Given s n , s n - 1 , ..., s 1 , s 0 ∈ S , compute each of the products p k = s k ○ s k - 1 ○ ,..., ○ s 1 ○ s 0 for all k , 0 ≤ k ≤ n.
This problem has appeared in solutions of recurrence systems for parallel and pipelined systems as well as in the design of gate and silicon compilers. The authors present two algorithms to generate parallel suffix solutions with minimum cost for a given length, time delay, availability of initial values, and fanout. The first algorithm generates a minimal solution for any length n and depth range from log2 n to n. The second algorithm reduces the size of the solutions generated by the first algorithm.
