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

摘要

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)