A Study on Abstract Machines for Concurrent Rewriting

点击翻译按钮获取中文摘要

We have designed an abstract machine for concurrent (parallel) rewriting called Parallel TRAM.Parallel TRAM can reasonably control parallel rewriting with the parallel E-strategy that is an extension of the evaluation strategy (the E-strategy) initiated by the algebraic specification language OBJ2. We also have implemented Parallel TRAM on the massively parallel computer Cray Research T3E carrying 128processing elements with the widely used message passing library MOI.The implementation is called PTRAM/MPI.PTRAM/MPI has been found to be about 50 times faster than TRAM the abstract machine for sequential rewriting by executing some benchmark programs with both of them. That shows the usefulness of the approach used in this research.We describe PTRAM/MPI in further detail. TRAM is an abstract machine for order-sorted conditional term (graph) rewriting systems, which may be used to implement efficient processors for advanced algebraic specification languages such as OBJ3 and CafeOBJ.The r … More ewriting strategy of TRAM is the evaluation strategy (the E-strategy) that allows one to specify local strategies for each operation so as to control rewriting. The E-strategy can simulate a variant of lazy evaluation. Parallel TRAM is a parallel variant of TRAM.It has been designed to be efficiently executed on a shared memory multiprocessor, and its parallel computational model is the shared memory model. The rewriting strategy of Parallel TRAM is an extension of the E-strategy called the parallel E-strategy. The parallel E-strategy may control parallel rewriting reasonably by combining with conditionals. PTRAM/MPI is an improved version of Parallel TRAM.It has been designed to be efficiently executed on a massively parallel computer or a workstation cluster, and its parallel computational model is the message passing model. PTRAM/MPI has been implemented on Cray Research T3E carrying 128 processing elements with MPI.Thanks to MPI,it may be easy to port or implement PTRAM/MPI on other massively parallel computers or workstation clusters. Less