# Accession Number:

## ADA443163

# Title:

## Trace Theory and Systolic Computations

# Descriptive Note:

# Corporate Author:

## CALIFORNIA INST OF TECH PASADENA DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1987-01-01

# Pagination or Media Count:

## 23.0

# 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.

# Descriptors:

# Subject Categories:

- Numerical Mathematics