Systolic designs for Bernoulli's method (Q921868)

This paper studies the systolic implementation of Bernoulli's method for obtaining dominant roots of a polynomial of degree n, and offers two systolic architectures. The first one is a linear systolic array of n inner product step processors with bidirectional data flow. It has a throughput rate of 1/2 and its processor utilization is 1/2. The second architecture is a systolic ring. The ring requires only half of the cells of the linear array and now the data flow is unidirectional. Each cell is active during every cycle. The throughput rate is 1/2 while the processor utilization becomes 1. An important feature of the proposed ring architecture is that it degrades gracefully as the number of defective cells increases. This systolic solution is quite suitable both for hardware (using WSI techniques) and soft systolic implementation. Many implementation details and the possibilities to use the proposed architectures for the obtaining of a polynomial solver are also presented. A simulation program in OCCAM is listed in the Appendix. We remark that three different systolic designs for Bernoulli's method were also presented by the reviewer [Publ. Inst. Math., Nouv. Ser. 44(58), 137-142 (1988; Zbl 0678.68052)].