Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On the design of some systolic algorithms
van de Snepscheut J., Swenker J. Journal of the ACM36 (4):826-840,1989.Type:Article
Date Reviewed: Nov 1 1990

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.

Reviewer:  Thomas B. Hilburn Review #: CR114390
Bookmark and Share
 
Unbounded-Action Devices (F.1.1 ... )
 
 
Invariants (F.3.1 ... )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
 
Semantics Of Programming Languages (F.3.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Unbounded-Action Devices": Date
An efficient solution of the firing mob problem
Karel I., Dube S. Theoretical Computer Science 91(1): 57-69, 1991. Type: Article
Nov 1 1992
Real-time, pseudo real-time, and linear-time ITA
Karel I., Yu S. Theoretical Computer Science 47(1): 15-26, 1986. Type: Article
May 1 1988
Cellular automata machines: a new environment for modeling
Toffoli T. (ed), Margolus N., MIT Press, Cambridge, MA, 1987. Type: Book (9789780262200608)
Jan 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy