Kim Hie Cheol, Lee Yong Doo

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 7, pp. 1908-1922, Jul. 1998
10.3745/KIPSTE.1998.5.7.1908,   PDF Download:

Abstract

This paper presents a systematic approach to the compilation of logic programs for efficient clause indexing. As the kernel of the approach, we propose the indexing tree which provides a simple, but precise representation of average parallelism per node (i.e., choice point) as well as the amount of clause trials. It also provides the way to evaluate the number of the cases that the control is passed to the failure code by the indexing instruction such as switch_on_term, switch_on_constant, or switch_on_structure. By analyzing the indexing tree created when using the indexing scheme implemented in the WAM, we show the drawback of the WAM indexing scheme in terms of parallelism exposition and scheduling efficiency. Subsequently we propose a new indexing scheme, which we call the Flat indexing. The experiment result shows that over one half of the benchmarks benefit from the Flat indexing such that, compared with the WAM indexing scheme, the number of choice points is reduced by 15%. Moreover, the amount of failures which occurs during the execution of indexing instructions is reduced by 35%.

Statistics
Cite this article