The derivation of systolic computations (Q921907)

Even if mechanical derivation of programs from their specification seems to suppress the beauty of creative programming, undoubtedly it is the best way to ensure that programs meet their specifications. Fortunately, still there is a place for creativity there, as long as efficiency of the resulting program is taken into account. The article presents a design technique for the systematic derivation of parallel programs from specifications. The method starts with the input/output relation of a program, and expresses it in a form of relation between input and output streams (sequences). The next step consists of partitioning the input/output relation into simpler ones - and to consider each part to be one cell, capable of doing some computation and communication. The efficiency of the resulting (parallel) program depends on this splitting, hence there is a space for creativity, too. The rest of the design consists of a precise specification of the cells, and of their communications. In the authors' terms the derivation process consists of the following steps: 1. Messaging the specification, 2. Deriving recurrence relations, 3. Deriving communication behaviors, 4. Coding. The authors give detailed illustration of their technique by deriving a linear systolic array for nontrivial rank order filter problem. Unfortunately, they didn't try to specify the class of problems to which their method can be applied.