Trace Theory and Systolic Computations
Abstract
We discuss a class of concurrent computations, or special-purpose computing engines, that may be characterized by (i) they consist of regular arrangements of simple cells; (ii) the arrangement consumes streams of input values and produces streams of output values; (iii) the cells communicate with a fixed number of neighbor cells only; (iv) the communication behaviors of the cells are independent of the values communicated. Such arrangements are often referred to as systolic arrays. Our computations, however, have a few other characteristics that are usually not found among systolic arrays: (v) synchronization of cells is by message passing only; (vi) each output value is produced as soon as all input values on which it depends have been consumed. The formalism we use to discuss these computations is trace theory [4], [7], [8]. Section 1 is an introduction to trace theory, in which only those subjects are covered that are needed to understand the subsequent sections. Section 2, called Data Independence, addresses the question what it means that communication behaviors are independent of the values communicated. To express the simplicity of (the communication behaviors of) the cells we define in Section 3 the concept of conservative processes. The results of Sections 2 and 3 are assembled into a number of theorems that are used in Sections 4, 5, and 6. Each of these remaining sections discusses an illustrative example of a systolic computation: polynomial multiplication, cyclic encoding, and palindrome recognition.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA443163
Entities
People
- Martin Rem
Organizations
- California Institute of Technology