Abstract
This paper describes the architecture of a cellular processor capable of directly and efficiently executing reduction languages as defined by Backus. The processor consists of two interconnected networks of microprocessors, one of which is a linear array of identical cells, and the other a tree-structured network of identical cells. Both kinds of cells have modest processing and storage requirements. The processor directly interprets a high-level language, and its efficient operation is not restricted to any special class of problems. Memory space permitting, the processor accommodates the unbounded parallelism allowed by reduction languages in any single user program; it is also able to execute many user programs simultaneously.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arvind and K. P. Gostelow, “A Computer Capable of Exchanging Processors for Time,”Information Processing 77 (North-Holland Publishing Co., 1977), pp. 849–853.
J. W. Backus, “Reduction Languages and Variable-Free Programming,” IBM Research Report RJ1010, Yorktown Heights, New York (April 1972).
J. W. Backus, “Programming Language Semantics and Closed Applicative Languages,” IBM Research Report RJ1245, Yorktown Heights, New York (July 1973).
A. L. Davis, ”The Architecture of DDM1: A Recursively Structured Data Driven Machine,“ Technical Report UUCS-77-113, Department of Computer Science, University of Utah, Salt Lake City, Utah (October 1977).
J. B. Dennis, “Computation Structures,”COSINE Committee Lectures, Princeton University, Department of Electrical Engineering, Princeton, New Jersey (July 1968).
J. B. Dennis, “Programming Generality, Parallelism and Computer Architecture,”Information Processing 68 (North-Holland Publishing Co., 1969), pp. 484–492.
J. B. Dennis, “First Version of a Data Flow Procedure Language,”Lecture Notes in Computer Science, Vol. 19 (Springer-Verlag, New York, 1974), pp. 362–376.
J. B. Dennis and D. P. Misunas, “A Preliminary Architecture for a Basic Data-Flow Processor,”Proceedings of the Second Annual Symposium on Computer Architecture (IEEE, New York, 1975), pp. 126–132.
A. W. Holt and F. Commoner, “Events and Conditions,”Record of the Project MAC Conference on Concurrent Systems and Parallel Computation (ACM, New York, 1970), pp. 3–52.
A. Koster, “Execution Time and Storage Requirements of Reduction Language Programs on a Reduction Machine,” Ph.D. thesis, Department of Computer Science, University of North Carolina at Chapel Hill (March 1977).
P. McJones, “A Church-Rosser Property of Closed Applicative Languages,” IBM Research Report RJ1589, Yorktown Heights, New York (May 1975).
S. S. Patil and J. B. Dennis, “The description and realization of digital systems,”Rev. Fr. Autom. Inf. Rech. Oper. 55–69 (February 1973).
C. A. Petri,Kommunikation mit Automaten, No. 2. (Schriften des Rheinisch-Westfälischen Institutes für Instrumentelle Mathematik an der Universität Bonn, Bonn, 1962).
M. Pozefsky, “Programming in Reduction Languages,” Ph.D. thesis, Department of Computer Science, University of North Carolina at Chapel Hill (October 1977).
D. F. Stanat and G. A. Magó, “Minimizing maximum flows in linear graphs,” to appear inNetworks.
D. F. Stanat and G. A. Magó, “A parallel algorithm for minimizing maximum flows in linear graphs,” in preparation.
K. J. Thurber,Large Scale Computer Architecture-Parallel and Associative Processors (Hayden Book Co., Rochelle Park, New Jersey, 1976).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Magó, G.A. A network of microprocessors to execute reduction languages, part I. International Journal of Computer and Information Sciences 8, 349–385 (1979). https://doi.org/10.1007/BF00995174
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00995174