AN EFFICIENT IMPLEMENTATION OF TERM REWRITING SYSTEM ON A DISTRIBUTED-MEMORY ARCHITECTURE

Term Rewriting System (TRS) is a model of computation and it is used i n various application such as algebraic specification. TRS has an inhe rent concurrency and it is suitable for parallel computing. We have al ready proposed BOB (Bundle Of Branches), which is a mechanism of data management for parallel rewriting. We have proposed a model of paralle l rewriting using BOB and implemented a TRS simulator based on this mo del on a shared memory parallel computer. Because it fully depends on the feature of a shared memory architecture, that is, a process can ac cess any memory element, it is hard to transport it on a distributed m emory parallel computer. In this paper, we propose autonomous BOB mode l. This model is suitable for a distributed memory architecture since a process uses message passing protocol and the method of load balanci ng is provided. We implement a TRS simulator using this model on a dis tributed memory architecture and it runs about 30 times faster on 64 p rocessors than on a single processor.