Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-18T23:00:17.926Z Has data issue: false hasContentIssue false
  • English
  • Français

PALS: Efficient Or-Parallel execution of Prolog on Beowulf clusters

Published online by Cambridge University Press:  01 November 2007

ENRICO PONTELLI ,
KAREN VILLAVERDE ,
HAI-FENG GUO  and
GOPAL GUPTA
ENRICO PONTELLI
Affiliation:
Department of Computer Science, New Mexico State University, NM, USA (e-mail: [email protected], [email protected])
KAREN VILLAVERDE
Affiliation:
Department of Computer Science, New Mexico State University, NM, USA (e-mail: [email protected], [email protected])
HAI-FENG GUO
Affiliation:
Department of Computer Science, University of Nebraska at Omaha, NE, USA (e-mail: [email protected])
GOPAL GUPTA
Affiliation:
Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper describes the development of the PALS system, an implementation of Prolog capable of efficiently exploiting or-parallelism on distributed-memory platforms—specifically Beowulf clusters. PALS makes use of a novel technique, called incremental stack-splitting. The technique proposed builds on the stack-splitting approach, previously described by the authors and experimentally validated on shared-memory systems, which in turn is an evolution of the stack-copying method used in a variety of parallel logic and constraint systems—e.g., MUSE, YAP, and Penny. The PALS system is the first distributed or-parallel implementation of Prolog based on the stack-splitting method ever realized. The results presented confirm the superiority of this method as a simple yet effective technique to transition from shared-memory to distributed-memory systems. PALS extends stack-splitting by combining it with incremental copying; the paper provides a description of the implementation of PALS, including details of how distributed scheduling is handled. We also investigate methodologies to effectively support order-sensitive predicates (e.g., side-effects) in the context of the stack-splitting scheme. Experimental results obtained from running PALS on both Shared Memory and Beowulf systems are presented and analyzed.

Keywords

Or-ParallelismBeowulf clustersorder-sensitive predicates
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 7 , Issue 6 , November 2007 , pp. 633 - 695
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Kaci, H. A. 1991. Warren's Abstract Machine: a Tutorial Reconstruction. MIT Press.CrossRefGoogle Scholar
Ali, K. A. M. 1988. Or-parallel Execution of Prolog on BC-machine. Proceedings of the International Conference and Symposium on Logic Programming, MIT Press, pp. 1531–1545.Google Scholar
Ali, K. A. M. and Karlsson, R. (1990. The MUSE Approach to Or-Parallel Prolog. Int. J. Parallel Programming, 19 (2): 129–162.CrossRefGoogle Scholar
Alshawi, D. B. and Moran, D. N. 1988. The Delphi Model and Some Preliminary Experiments. Fifth International Conference and Symposium on Logic Programming, MIT Press, pp. 1578–1589.Google Scholar
Apt, A. R. 1997. From Logic Programming to Prolog. Prentice Hall, 1997.Google Scholar
Araujo, L. 1997. Full Prolog on a Distributed Architecture. I Euro-Par, pp. 1173–1180. Springer Verlag.CrossRefGoogle Scholar
Araujo, L. and Ruz, J. 1998. A Parallel Prolog System for Distributed Memory. J. Logic Program., 33 (1): 49–79.CrossRefGoogle Scholar
Babu, H. 1996. Porting muse on ipsc860. Master's thesis, New Mexico State University.Google Scholar
Balduccini, M., Pontelli, E. and Bermudez, F. 2003. Non-monotonic Reasoning on Beowulf Platforms. Proceedings of the Symposium on Practicals Aspects of Declarative Languages, Springer Verlag, pp. 37–57.Google Scholar
Balduccini, M., Pontelli, E., Elkhatib, O. and Le, H. 2005. Issues in Parallel Execution of Non-monotonic Reasoning Systems. Parallel Computing, 31 (6): 608–647.CrossRefGoogle Scholar
Beaumont, A. J. and Warren, D. H. D. 1993. Scheduling Speculative Work in Or-Parallel Prolog Systems. In: Warren, D. S., editor, Proceedings of the International Conference on Logic Programming, pp. 135–149, Cambridge, MA.Google Scholar
Benjumea, V. and Troya, J. M 1993. An OR Parallel Prolog Model for Distributed Memory Systems. In: M. Bruynooghe and J. Penjam, editors, International Symposium on Programming Languages Implementations and Logic Programming, pp. 291–301, Heidelberg. Springer Verlag.CrossRefGoogle Scholar
Briat, J., Favre, M., Geyer, C. and Chassinde Kergommeaux, J. de Kergommeaux, J. 1992. OPERA: Or-Parallel Prolog System on Supernode. In: Kacsuk, P. and Wise, M., editors, Implementations of Distributed Prolog, pp. 45–64. J. Wiley & Sons.Google Scholar
Butler, R., Disz, T., Lusk, E., Olson, R., Overbeek, R. and Stevens, R. 1988. Scheduling Or-Parallelism: An Argonne Perspective. Proceedings of the International Conference and Symposium on Logic Programming, MIT Press, pp. 1565–1577.Google Scholar
Castro, L. F., SantosCosta, V. Costa, V., Geyer, C. F. R., Silva, F., Vargas, P. K. and Correia, M. E. 1999. DAOS: Scalable And-Or Parallelism. In Pritchard, D. and Reeve, J., editors, Proceedings of EuroPar, pages 899–908, Heidelberg, 1999. Springer Verlag.Google Scholar
Chassinde Kergommeaux, J. de Kergommeaux, J. and Codognet, P. 1994. Parallel Logic Programming Systems. ACM Computing Surveys, 26 (3): 295–336.Google Scholar
Clocksin, W. F. and Alshawi, H. 1988. A Method for Efficiently Executing Horn Clause Programs Using Multiple Processors. New Generation Computing, 5: 361–376.CrossRefGoogle Scholar
Conery, J. S. 1987. Binding Environments for Parallel Logic Programs in Nonshared Memory Multiprocessors. International Symposium on Logic Programming, pp. 457–467. San Francisco, IEEE Computer Society.Google Scholar
Conery, J. S. and Kibler, D. F. 1981. Parallel Interpretation of Logic Programs. Proc. of the ACM Conference on Functional Programming Languages and Computer Architecture, ACM Press, pp. 163–170.Google Scholar
Finkel, R., Marek, V., Moore, N. and Truszczyński, M. 2001. Computing stable models in parallel. In: Provetti, A. and Tran, S. C., editors, Proceedings of the AAAI Spring Symposium on Answer Set Programming, pp. 72–75, Cambridge, MA. AAAI/MIT Press.Google Scholar
Foong, W.-K. 1995. Combining and- and or-parallelism in Logic Programs: a distributed approach. PhD thesis, University of Melbourne.Google Scholar
Ganguly, S., Silberschatz, A. and Tsur, S. 1990. A Framework for the Parallel Processing of Datalog Queries. In: Garcia-Molina, H. and Jagadish, H., editors, Proceedings of ACM SIGMOD Conference on Management of Data, New York. ACM Press.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The Stable Model Semantics for Logic Programs. International Symposium on Logic Programming, pp. 1070–1080. MIT Press.Google Scholar
Gupta, G. 1994. Multiprocessor Execution of Logic Programs. Kluwer.CrossRefGoogle Scholar
Gupta, G. and Jayaraman, B. 1993. Analysis of Or-parallel Execution Models. ACM Trans. Program. Lang. Syst. 15 (4): 659–680.CrossRefGoogle Scholar
Gupta, G. and Pontelli, E. 1996. Last Alternative Optimization for Or-parallel Logic Programming Systems. Eight International Symposium on Parallel and Distributed Processing. IEEE Computer Society.Google Scholar
Gupta, G. and Pontelli, E. 1997. Optimization Schemas for Parallel Implementation of Nondeterministic Languages and Systems. International Parallel Processing Symposium, Los Alamitos, CA. IEEE Computer Society.Google Scholar
Gupta, G. and Pontelli, E. 1999. Stack-splitting: A Simple Technique for Implementing Or-parallelism and And-parallelism on Distributed Machines. International Conference on Logic Programming, pp. 290–304. MIT Press.Google Scholar
Gupta, G., Pontelli, E., Carlsson, M., Hermenegildo, M. and Ali, K. M. 1999. Parallel Execution of Prolog Programs: a Survey. ACM Trans. Program. Lang. Syst. 23 (4): 472–602.CrossRefGoogle Scholar
Hausman, B., Ciepielewski, A. and Calderwood, A. 1988. Cut and Side-Effects in Or-Parallel Prolog. In: Staff, ICOT, editor, International Conference on Fifth Generation Computer Systems, pp. 831–840, Tokyo, Japan. Springer Verlag.Google Scholar
Kowalski, R. A. 1979. Logic for Problem Solving. Elsevier.Google Scholar
Kumar, V. and Kanal, L. N. 1979. Parallel Depth-First Search on Multiprocessors. Int. J. Parallel Program. 16 (6): 479–499.Google Scholar
Lai, T.-H. and Sahni, S. 1984. Anomalies in Parallel Branch-and-Bound Algorithms. Comm. ACM, 27 (6): 594–602.CrossRefGoogle Scholar
Lloyd, J. W. 1987. Foundations of Logic Programming. Springer Verlag.CrossRefGoogle Scholar
Lusk, E., Butler, R., Disz, T. et al. 1990. The Aurora Or-parallel Prolog System. New Generation Computing, 7 (2/3): 243–271.CrossRefGoogle Scholar
Misra, J. 1983. Detecting Termination of Distributed Computations using Markers. ACM Symposium on Principles of Distributed Computing, ACM Press, pp. 290–294.Google Scholar
Montelius, J. and Ali, K. 1996. A Parallel Implementation of AKL. New Generation Computing, 14 (1): 31–52.CrossRefGoogle Scholar
Perron, L. 1999. Search Procedures and Parallelism in Constraint Programming. In: Jaffar, J., editor, Proceedings of the International Conference on Principles and Practice of Constraint Programming, volume 1713 of LNCS, pp. 346–360, Heidelberg. Springer-Verlag.Google Scholar
Pontelli, E. and El-Kathib, O. 2001. Construction and Optimization of a Parallel Engine for Answer Set Programming. In: Ramakrishnan, I. V., editor, Practical Aspects of Declarative Languages, volume 1990 of LNCS, pp. 288–303, Heidelberg. Springer Verlag.CrossRefGoogle Scholar
Pontelli, E., Ranjan, D. and DalPalu, A. Palu, A. 2002. An Optimal Data Structure to Handle Dynamic Environments in Non-Deterministic Computations. Computer Languages, 28 (2): 181–201.Google Scholar
Ranjan, D., Pontelli, E. and Gupta, G. 1999. On the Complexity of Or-Parallelism. New Generation Computing, 17 (3): 285–308.CrossRefGoogle Scholar
Ranjan, D., Pontelli, E. and Gupta, G. 2000. Data Structures for Order-Sensitive Predicates in Parallel Nondetermistic Systems. ACTA Informatica, 37 (1): 21–43.CrossRefGoogle Scholar
Rocha, R., Silva, F. and SantosCosta, V. Costa, V. 1999. YapOr: an Or-Parallel Prolog System based on Environment Copying. LNAI 1695, Proceedings of EPIA'99: The 9th Portuguese Conference on Artificial Intelligence, pp. 178–192. Springer-Verlag LNAI Series.Google Scholar
Rocha, R., Silva, S. and Martins, R. 1999. YapDss: an Or-Parallel Prolog System for Scalable Beowulf Clusters. Proceedings of the Portuguese Conference on Artificial Intelligence (EPIA), Springer-Verlag, pp. 136–150.Google Scholar
Schulte, C. 1999. Compairing Trailing and Copying for Constraint Programming. International Conference on Logic Programming, pp. 275–289. MIT Press.Google Scholar
Schulte, C. 2000. Parallel Search Made Simple. In: Beldiceanu, N. et al. , editor, Proceedings of Techniques for Implementing Constraint Programming Systems, Post-conference workshop of CP 2000, number TRA9/00, pp. 41–57, University of Singapore.Google Scholar
Silva, F. and Watson, P. 2000. Or-Parallel Prolog on a Distributed Memory Architecture. J. Logic Program. 43 (2): 173–186.CrossRefGoogle Scholar
Sindaha, R. 1992. The Dharma Scheduler –- Definitive Scheduling in Aurora on Multiprocessor Architecture. Proceedings of the Symposium on Parallel and Distributed Processing. IEEE Computer Society, pp. 296–303.Google Scholar
Szeredi, P. 1991. Using dynamic predicates in an or-parallel prolog system. In: Saraswat, V. and Ueda, K., editors, Proceedings of the International Logic Programming Symposium, pp. 355–371, Cambridge, MA. MIT Press.Google Scholar
Villaverde, K. 2002 An Efficient Methodology to Exploit Or-parallelism on Distributed Memory Systems. PhD thesis, New Mexico State University.Google Scholar
Villaverde, K., Pontelli, E., Gupta, G. and Guo, H. 2001. Incremental Stack Splitting Mechanisms for Efficient Parallel Implementation of Search-based Systems. International Conference on Parallel Processing. IEEE Computer Society.Google Scholar
Villaverde, K., Pontelli, E., Gupta, G. and Guo, H. 2001. PALS: An Or-parallel Implementation of Prolog on Bewoulf Architectures. Procs. International Conference on Logic Programming. Springer Verlag.Google Scholar
Villaverde, K., Pontelli, E., Gupta, G. and Guo, H. 2001. Villaverde, K., Pontelli, E., Gupta, G., and Guo., H. A Methodology for Order-sensitive Execution of Non-deterministic Languages on Beowulf Platforms. Euro-Par.Google Scholar
Warren, D. H. D. 1987. The SRI Model for OR-Parallel Execution of Prolog–-Abstract Design and Implementation. Proceedings of the Symposium on Logic Programming, IEEE Computer Society, pp. 92–102.Google Scholar
Warren, D. H. D. and Haridi, S. 1988. The Data Diffusion Machine – a Scalable Shared Virtual Memory Multiprocessor. Fifth Generation Computer Systems, pp. 943–952.Google Scholar
Wolfe, M. 1996. High Performance Compiler for Parallel Computing. Addison Wesley.Google Scholar
Wolfson, G. and Silberschatz, A. 1988. Distributed Processing of Logic Programs. In: Boral, H. and Larson, P., editors, Proceedings of the SIGMOD International Conference on Management of Data, pp. 329–336, New York. ACM Press.Google Scholar
Zima, H. and Chapman, B. 1991. Supercompilers for Parallel and Vector Computers. ACM Press.Google Scholar