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

Journal of Inforamtion Science and Engineering, Vol. 16, No. 2, pp. 225-242 (March 2000)

Flat Indexing Scheme: A New Compilation Technique to
Enhance Parallelism of Logic Programs

Hiecheol Kim, Kangwoo Lee+ and Jean-Luc Gaudiot++
Department of Computer and Communication Engineering
Taegu University, Korea
E-mail: hckim@biho.taegu.ac.kr
+Department of Computer and Communication Engineering
Dongguk University, Korea
E-mail: klee@cakra.dongguk.ac.kr
++Department of Electrical Engineering-Systems
University of Southern California
Los Angeles, CA 90089-2563, U.S.A.
E-mail: gaudiot@usc.edu

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 the average parallelism per node (i.e., choice point) as well as the number of clause trials. It also provides a way to evaluate the number of cases in which the control is passed to the failure code by means of an indexing instruction, such as switch_on_term, switch_on_constant, or switch_on_structure. By analyzing the indexing tree created when the indexing scheme is implemented in the WAM, we show the drawback of the WAM indexing scheme in terms of parallelism exposition and scheduling. Subsequently, we propose a new indexing scheme, which we call the the Flat indexing. The experimental results show that over one half of our benchmarks benefit from 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 occur during the execution of indexing instructions is reduced by 35%.

Keywords: logic programming, clause indexing, OR-parallelism, WAM, Prolog

Full Text () Retrieve PDF document (200003_04.pdf : 3,563,874 bytes)

Received March 28, 1999; revised July 16, 1999; accepted November 26, 1999.
Communicated by Shang-Rong Tsai.