Parallel inference algorithms for the connection method on systolic arrays
Yongfei Han, David John Evans · International Journal of Computer Mathematics · 1994
In practice, various techniques are used to speed up the reasoning in logic programming and parallel machines. Three major approaches have generally been adapted to solve this problem. The most common approach involves some methods of the development of AND and OR parallelism, as in Parlog[Clark84], Concurrent-Prolog[Shapiro83] and IDIOM[Gupta&Hermenegildo]. In these schemes, the three main forms of implicit parallelism-Independent AND-Parallelism, Dependent AND-parallelism and OR-parallel-ism are exploited. The second approach is to build parallel architectures to execute different level parallelism inherent in inference, such as DADO[Stolfo84, Miranker90], NON-VON[Hillyer86] and PSM[Gupta87]. The third approach is to develop faster match and search algorithms, as in Rete[Forgy82] and Treat The bottle-neck in inference systems is the match phase. Around 90% of execution time is consumed in this phase[Gupta87]. In this paper, we present algorithms to realize the connection method on systolic arrays. The algorithms try to partition the paths in connections matrices for parallel inference. Firstly, parallelism in reasoning is discussed; then the parallel inference on systolic arrays and algorithms for partition of paths are introduced. Finally, the correctness and completeness of the algorithms is shown. The paper consists of five sections. The connection method is presented and parallel inference algorithms on systolic arrays are designed after introduction. The third section describes an example in partition of the paths in the connection method, the example executing on normal systolic and tree systolic models are shown. The fourth section discusses the analysis of the algorithms. The final section works out conclusions and related work.