Previous [1] 2 [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.7 No.4, pp.487-512 (December 1991)
An Or-Parallel Inference Model Based on
Multi RISC-Style Processing System*

Cheng Chen, Chung Ping Chung, Cheng Chin Chiang,
Hsin Chia Fu and S. J. Wang+
Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsin Chu, Taiwan, R.O.C.
+Computer and Communication Research Laboratory
Industrial Technology Research Institution
Hsin Chu, Taiwan, R.O.C.

Recently, RISC (Reduced Instruction Set Computer) has been widely and successfullyused in many high-performance, general-purpose computer systems.On the other hand,symbolic manipulation and logic inferences have also been attractive and have played an important role in various application areas of artificial intelligence. How to design a high performance inference engine based on an RISC-type machine has, thus, become an exciting research trend in computer system design area. In this paper, we will introduce a new OR-parallel inference model based on a multi-RISC-style processing system, called MIEP (Multiple Inference Engine for Prolog), to execute prolog programs efficiently. Our model consists of two main parts. One is forward execution and the other is backward execution algorithms. We also design an intelligent backtracking technique to speed up the backward execution. To evaluate the performance of our OR model on the MIEP system, several benchmark programs are compiled and then executed by the simulato. The results show that our method has a very good speed up scaling-factor within 16 processors. The detailed description of our model and its evaluation will be given. In addition, some interesting future works are also introduced at the end of the paper.

Keywords: Prolog, RISC, OR-parallelism, intelligent backtracking, forward execution, AND-parallelism, shallow backtracking, deep backtracking, MIEP

Received July 1, 1991; revised November 1, 1991.
Communicated by Ferng-Ching Lin.
*This work was supported inpart by NSC under the contract NSC76-0408-E009-15.