Y. Hachisu et al., AN EFFICIENT IMPLEMENTATION OF TERM REWRITING SYSTEM ON A DISTRIBUTED-MEMORY ARCHITECTURE, IEICE transactions on information and systems, E80D(4), 1997, pp. 510-517
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.