A Study on Abstract Machines for Concurrent Rewriting

我们设计了一个用于并发（并行）重写的抽象机器，称为并行TRAM。并行TRAM可以通过并行e策略合理地控制并行重写，并行e策略是对代数规范语言OBJ2发起的求值策略（e策略）的扩展。我们还在大规模并行计算机Cray Research T3E上实现了并行TRAM，该计算机携带128个处理单元，并使用了广泛使用的消息传递库MOI。其实现称为PTRAM/MPI。通过在PTRAM/MPI上执行一些基准测试程序，发现PTRAM/MPI在顺序重写方面比抽象机TRAM快50倍左右。这显示了本研究中使用的方法的有效性。我们进一步详细描述了PTRAM/MPI。TRAM是一个用于有序条件项（图）重写系统的抽象机器，可用于实现高级代数规范语言（如OBJ3和CafeOBJ）的高效处理器。TRAM的更重要的重写策略是评估策略（E-strategy），它允许人们为每个操作指定局部策略，以控制重写。e策略可以模拟惰性求值的一种变体。平行有轨电车是有轨电车的平行变体。它被设计为在共享内存多处理器上高效执行，其并行计算模型为共享内存模型。平行电车的改写策略是e策略的延伸，称为并行e策略。并行e策略可以通过与条件的结合来合理地控制并行重写。PTRAM/MPI是并行TRAM的改进版本。它被设计为在大规模并行计算机或工作站集群上高效执行，其并行计算模型为消息传递模型。PTRAM/MPI已在Cray Research T3E上实现，携带128个带有MPI的处理元件。由于MPI，可以很容易地在其他大规模并行计算机或工作站集群上移植或实现PTRAM/MPI。少

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