ISSN:
1436-5057
Keywords:
68
;
68C05
;
Computational structures
;
systolic algorithms
;
spacetime representations
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Eine allgemeine Theorie zur Charakterisierung und Realisierung von Algorithmen in Hardware wird angegeben. Der physikalische Vorgang des Rechenprozesses wird als Graph in einem physikalischen Raum-Zeit-System dargestellt. Sodam wird angegeben, wie in diesen Graphen ein weiterer Graph, der den Datenfluß in speziellen Algorithmen charakterisiert, eingebettet werden kann. Typen spezieller Klassen von Rechenstrukturen, sogenannte systolische Felder (systolic arrays), die physikalisch auftreten können, werden vollständig beschrieben und eine Methode entwickelt, um die Graphen eines gegebenen systolischen Algorithmus in eine physikalisches Feld abzubilden. Beispiele illustrieren die Vorgehensweise.
Notes:
Abstract A general theory for characterizing and then realizing algorithms in hardware is given. The physical process of computation is interpreted in terms of a graph in physical space and time, and then an embedding into this graph of another graph which characterizes data flow in particular algorithms is given. The types of the special class of computational structures called systolic arrays which can occur physically are completely described, and a technique is developed for mapping the graph of a particular systolic algorithm into a physical array. Examples illustrate the methodology.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02253685
