The Rewrite Rule Machine Project
Abstract
Current generation parallel machines are typically either coarse-grain or fine-grain. Each design has certain limits, either in the amount of parallelism that it can effectively exploit, or else in the types of problem for which it is suitable. For example, only very homogeneous computations can make efficient use of today's fine-grained machines. However, many complex computations are locally homogeneous, but not globally homogeneous. The Rewrite Rule Machine (RRM) resolves this dilemma through its hierarchical architecture, which has several levels of organization. The lowest level is the cell, which stores a token and pointers to other cells; this organization avoids the von Neumann memory access bottleneck. Next, an ensemble contains many cells, representing a complex data structure to which rewrite rules are applied under the direction of a common controller. A cluster consists of many ensembles which cooperate in larger computations. Ensembles support fine-grained homogeneous parallelism, while clusters support coarse-grained inhomogeneous parallelism. This multi-grained parallelism allows the RRM to exploit the local homogeneity that is typical of many complex computations. The RRM can support the efficient execution of many different programming paradigms by compiling them into its concurrent rewriting model of computation.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA210528
Entities
People
- Hitoshi Aida
- Joseph A. Goguen
- José Meseguer
- Sany Leinwand
- Timothy Winkler
Organizations
- SRI International