Canonical Realizations of Completely Regular Modular Computing Networks,
Abstract
This paper establishes a simple technique for transforming a given 3- dimensional space-time representation into an equivalent canonical form. A catalogue of canonical forms is constructed, showing a total of 34 distinct systolic architectures. The task of selecting an appropriate transformation for a given space-time representation reduces, therefore, to the determination of the equivalent canonical form. The important result, which has been overlooked in previous research, is that the canonical equivalent of any given space-time representation is unique. This means that once a space-time representation has been specified there is no flexibility left in the process of mapping into systolic-array architectures. A small fraction of space-time representation do allow some flexibility in selecting the hardware architecture, but only at the cost of inefficient implementation. The well-known example of matrix multiplication, which has four distinct realizations turns out to be one of the few cases where such flexibility is available. A closer examination of the structure of the matrices to be multiplied reveals that each realization is efficient under a different set of structural assumptions. Thus, in summary, carefully specified algorithms lead to unique space-time representations which, in turn, lead to essentially unique architectures. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1984
- Accession Number
- ADA142010
Entities
People
- H. Lev-ari