Accession Number:

ADA171089

Title:

A Rewrite Rule Machine. Models of Computation for the Rewrite Rule Machine.

Descriptive Note:

Final rept.,

Corporate Author:

SRI INTERNATIONAL MENLO PARK CA COMPUTER SCIENCE LAB

Report Date:

1986-07-01

Pagination or Media Count:

23.0

Abstract:

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

Subject Categories:

  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE