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.
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Cardelli, L.: Doctoral Dissertation, University of Edinborough, 1982.
Kuch, D. J.: A survey of parallel machine organization and programming. ACM Comp. Survey9 (1977).
Kung, H. T.: Why systolic architectures. CMU-CS-81-148, Carnegie-Mellon University, 1981.
Mead, C. A., Conway, L. A.: Introduction to VLSI Systems. Reading, Mass: Addison-Wesley 1980.
Miranker, W. L.: A survey of parallelism in numerical analysis. SIAM Rev.13 (1971).
Miranker, W. L., Winkler, A.: Spacetime representations of systolic computational structures. IBM Research Center Report 9775, December 1982.
Moldovan, D. I.: On the design of algorithms for VLSI systolic arrays. Proc. IEEE71 (1983).
Mordell, L. J.: Diophantine equations, pp. 30ff. New York: Academic Press 1969.
Sameh, A. H.: Numerical parallel algorithms. In: High speed computer and algorithm organization (Kuck, D. J., Lawrie, D. H., Sameh, A. H., eds.). New York: Academic Press 1977.
Stockmeyer, L. A.: Private communication.
Weiser, U., Davis, A.: A wavefront notation tool for VLSI array design. In: VLSI Systems and Computations (Kunz, H. T., Sproul, B., Steek, G., eds.). Rockville, Maryland: Computer Science Press 1981.
Author information
Authors and Affiliations
Additional information
Under the auspices of a student interaction agreement with the Courant Institute.
Rights and permissions
About this article
Cite this article
Miranker, W.L., Winkler, A. Spacetime representations of computational structures. Computing 32, 93–114 (1984). https://doi.org/10.1007/BF02253685
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02253685