The derivation of systolic computations
type: Item
instance of: scholarly article
title: The derivation of systolic computations
zbMATH Open document ID: 0709.68020
DOI: 10.1016/0167-6423(90)90021-5
author: Anne Kaldewaij
author: Martin Rem
published in: Science of Computer Programming
publication date: 1990-01-01T00:00:00Z
review text: 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.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 4166860
zbMATH Keywords: systolic algorithms
zbMATH Keywords: derivation of parallel programs
MaRDI profile type: Publication
full work available at URL: 0167-6423(90)90021-5
OpenAlex ID: W2158031696
description: scientific article; zbMATH DE number 4166860