An Efficient Implementation of Term Rewriting System on a Distributed Memory Architecture

Yoshinari HACHISU  Shinichirou YAMAMOTO  Takeshi HAMAGUCHI  Kiyoshi AGUSA  

IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.4   pp.510-517
Publication Date: 1997/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Parallel and Distributed Supercomputing)
TRS,  parallel rewriting,  BOB,  

Full Text: PDF>>
Buy this Article

Term Rewriting System (TRS) is a model of computation and it is used in various application such as algebraic specification. TRS has an inherent concurrency and it is suitable for parallel computing. We have already proposed BOB (Bundle Of Branches), which is a mechanism of data management for parallel rewriting. We have proposed a model of parallel rewriting using BOB and implemented a TRS simulator based on this model on a shared memory parallel computer. Because it fully depends on the feature of a shared memory architecture, that is, a process can access any memory element, it is hard to transport it on a distributed memory parallel computer. In this paper, we propose autonomous BOB model. This model is suitable for a distributed memory architecture since a process uses message passing protocol and the method of load balancing is provided. We implement a TRS simulator using this model on a distributed memory architecture and it runs about 30 times faster on 64 processors than on a single processor.