A Rewrite Rule Machine. Models of Computation for the Rewrite Rule Machine.
SRI INTERNATIONAL MENLO PARK CA COMPUTER SCIENCE LAB
Pagination or Media Count:
A new model of computation, concurrent tree rewriting, is proposed as a bridge easily programmed Ultra High Level Languages UHLLs featuring implicit concurrency, and an advanced parallel architecture of unprecedented performance, the Rewrite Rule Machine RRM architecture. At the highest level of abstraction, computation is understood as rewriting a tree at multiple sites concurrently. Less abstractly, such a possibly very large tree can be partitioned into fragments that are assigned to different processors, with each processor doing concurrent rewriting on its own fragment of the tree this gives the second level, partitioned concurrent rewriting. After introducing the basic concepts and properties of the model, we discuss tradeoffs between tree and directed acyclic graph dag data representations we also study partitioned concurrent rewriting, including tree and rule partitioning, and discuss evaluation strategies as a flexible control mechanism for concurrent rewriting. The mathematical definitions are gathered in an appendix. Author
- Computer Programming and Software
- Computer Hardware