Accession Number:

ADA142010

Title:

Canonical Realizations of Completely Regular Modular Computing Networks,

Descriptive Note:

Corporate Author:

INTEGRATED SYSTEMS INC PALO ALTO CA

Personal Author(s):

Report Date:

1984-05-01

Pagination or Media Count:

47.0

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

Subject Categories:

  • Statistics and Probability
  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE