A systolic algorithm is an algorithm that is executed on a synchronous array of computing cells that only communicate locally. This paper discusses a design technique for such algorithms that is based on established methods used in sequential programming. The authors illustrate their technique with three examples: palindrome recognition, Carré recognition, and the generation of polynomials for cyclic codes. All the algorithms consist of an initialization step followed by a loop in which the iterative step is a concurrent assignment statement.
The authors’ design method consists of first determining a recurrence relation based on the program specification (palindrome, Carré, or cyclic code) and then “guessing” a loop invariant P(n). A program is derived from P(n), and then checked by incrementing n by 1. Typically this dictates either changes in the program or a revised invariant. The design of each of the example algorithms involves several applications of the defining recurrence relation and corresponding refinements in the loop invariant and program. The authors argue that not only does their use of formal methods in algorithm design lead to successful programs, but the formulation of the invariant relations makes explicit the solution space, especially the distribution of values over cells and program steps. The examples discussed support this argument.
The paper is well written and free of errors. It is an important addition to the literature in this field.