{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T13:18:04Z","timestamp":1665062284869},"reference-count":58,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper describes the development of the<jats:italic>PALS<\/jats:italic>system, an implementation of Prolog capable of efficiently exploiting or-parallelism on<jats:italic>distributed-memory<\/jats:italic>platforms\u2014specifically Beowulf clusters. PALS makes use of a novel technique, called<jats:italic>incremental stack-splitting<\/jats:italic>. 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\u2014e.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.<\/jats:p>","DOI":"10.1017\/s1471068406002985","type":"journal-article","created":{"date-parts":[[2007,10,23]],"date-time":"2007-10-23T08:48:53Z","timestamp":1193129333000},"page":"633-695","source":"Crossref","is-referenced-by-count":1,"title":["PALS: Efficient Or-Parallel execution of Prolog on Beowulf clusters"],"prefix":"10.1017","volume":"7","author":[{"given":"ENRICO","family":"PONTELLI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAREN","family":"VILLAVERDE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HAI-FENG","family":"GUO","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GOPAL","family":"GUPTA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,11,1]]},"reference":[{"key":"S1471068406002985_ref46","first-page":"41","volume-title":"Proceedings of Techniques for Implementing Constraint Programming Systems, Post-conference workshop of CP 2000","author":"Schulte","year":"2000"},{"key":"S1471068406002985_ref44","first-page":"136","volume-title":"Proceedings of the Portuguese Conference on Artificial Intelligence (EPIA)","author":"Rocha","year":"1999"},{"key":"S1471068406002985_ref40","first-page":"181","article-title":"An Optimal Data Structure to Handle Dynamic Environments in Non-Deterministic Computations","volume":"28","author":"Pontelli","year":"2002","journal-title":"Computer Languages"},{"key":"S1471068406002985_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037223"},{"key":"S1471068406002985_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037217"},{"key":"S1471068406002985_ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-83189-8"},{"key":"S1471068406002985_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/358080.358103"},{"key":"S1471068406002985_ref42","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013301"},{"key":"S1471068406002985_ref45","first-page":"275","volume-title":"International Conference on Logic Programming","author":"Schulte","year":"1999"},{"key":"S1471068406002985_ref25","doi-asserted-by":"publisher","DOI":"10.1145\/155183.155220"},{"key":"S1471068406002985_ref38","first-page":"346","volume-title":"Proceedings of the International Conference on Principles and Practice of Constraint Programming","author":"Perron","year":"1999"},{"key":"S1471068406002985_ref31","volume-title":"Logic for Problem Solving","author":"Kowalski","year":"1979"},{"key":"S1471068406002985_ref26","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/SPDP.1996.570380"},{"key":"S1471068406002985_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2778-7"},{"key":"S1471068406002985_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(96)00117-3"},{"key":"S1471068406002985_ref13","first-page":"45","volume-title":"Implementations of Distributed Prolog","author":"Briat","year":"1992"},{"key":"S1471068406002985_ref8","unstructured":"Babu H. 1996. Porting muse on ipsc860. Master's thesis, New Mexico State University."},{"key":"S1471068406002985_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407834"},{"key":"S1471068406002985_ref54","unstructured":"Warren D. H. D. 1987. The SRI Model for OR-Parallel Execution of Prolog\u2013-Abstract Design and Implementation. Proceedings of the Symposium on Logic Programming, IEEE Computer Society, pp. 92\u2013102."},{"key":"S1471068406002985_ref22","volume-title":"Proceedings of ACM SIGMOD Conference on Management of Data","author":"Ganguly","year":"1990"},{"key":"S1471068406002985_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45241-9_20"},{"key":"S1471068406002985_ref55","first-page":"943","volume-title":"Fifth Generation Computer Systems","author":"Warren","year":"1988"},{"key":"S1471068406002985_ref2","first-page":"1531","volume-title":"Proceedings of the International Conference and Symposium on Logic Programming","author":"Ali","year":"1988"},{"key":"S1471068406002985_ref9","unstructured":"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\u201357."},{"key":"S1471068406002985_ref14","first-page":"1565","volume-title":"Proceedings of the International Conference and Symposium on Logic Programming","author":"Butler","year":"1988"},{"key":"S1471068406002985_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2005.03.004"},{"key":"S1471068406002985_ref30","first-page":"831","volume-title":"International Conference on Fifth Generation Computer Systems","author":"Hausman","year":"1988"},{"key":"S1471068406002985_ref15","first-page":"899","volume-title":"Proceedings of EuroPar","author":"Castro","year":"1999"},{"key":"S1471068406002985_ref6","doi-asserted-by":"crossref","unstructured":"Araujo L. 1997. Full Prolog on a Distributed Architecture. I Euro-Par, pp. 1173\u20131180. Springer Verlag.","DOI":"10.1007\/BFb0002870"},{"key":"S1471068406002985_ref11","first-page":"135","volume-title":"Proceedings of the International Conference on Logic Programming","author":"Beaumont","year":"1993"},{"key":"S1471068406002985_ref32","first-page":"479","article-title":"Parallel Depth-First Search on Multiprocessors","volume":"16","author":"Kumar","year":"1979","journal-title":"Int. J. Parallel Program."},{"key":"S1471068406002985_ref23","first-page":"1070","volume-title":"International Symposium on Logic Programming","author":"Gelfond","year":"1988"},{"key":"S1471068406002985_ref29","doi-asserted-by":"publisher","DOI":"10.1145\/504083.504085"},{"key":"S1471068406002985_ref21","unstructured":"Foong W.-K. 1995. Combining and- and or-parallelism in Logic Programs: a distributed approach. PhD thesis, University of Melbourne."},{"key":"S1471068406002985_ref12","doi-asserted-by":"crossref","unstructured":"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\u2013301, Heidelberg. Springer Verlag.","DOI":"10.1007\/3-540-57186-8_86"},{"key":"S1471068406002985_ref28","first-page":"290","volume-title":"International Conference on Logic Programming","author":"Gupta","year":"1999"},{"key":"S1471068406002985_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037415"},{"key":"S1471068406002985_ref18","first-page":"457","volume-title":"International Symposium on Logic Programming","author":"Conery","year":"1987"},{"key":"S1471068406002985_ref43","first-page":"178","volume-title":"LNAI 1695, Proceedings of EPIA'99: The 9th Portuguese Conference on Artificial Intelligence","author":"Rocha","year":"1999"},{"key":"S1471068406002985_ref36","first-page":"290","volume-title":"ACM Symposium on Principles of Distributed Computing","author":"Misra","year":"1983"},{"key":"S1471068406002985_ref20","first-page":"72","volume-title":"Proceedings of the AAAI Spring Symposium on Answer Set Programming","author":"Finkel","year":"2001"},{"key":"S1471068406002985_ref27","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1109\/IPPS.1997.580937"},{"key":"S1471068406002985_ref47","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00064-3"},{"key":"S1471068406002985_ref49","first-page":"355","volume-title":"Proceedings of the International Logic Programming Symposium","author":"Szeredi","year":"1991"},{"key":"S1471068406002985_ref51","volume-title":"International Conference on Parallel Processing","author":"Villaverde","year":"2001"},{"key":"S1471068406002985_ref5","unstructured":"Apt A. R. 1997. From Logic Programming to Prolog. Prentice Hall, 1997."},{"key":"S1471068406002985_ref48","first-page":"296","volume-title":"Proceedings of the Symposium on Parallel and Distributed Processing","author":"Sindaha","year":"1992"},{"key":"S1471068406002985_ref53","volume-title":"Euro-Par","author":"Villaverde","year":"2001"},{"key":"S1471068406002985_ref19","first-page":"163","volume-title":"Proc. of the ACM Conference on Functional Programming Languages and Computer Architecture","author":"Conery","year":"1981"},{"key":"S1471068406002985_ref50","unstructured":"Villaverde K. 2002 An Efficient Methodology to Exploit Or-parallelism on Distributed Memory Systems. PhD thesis, New Mexico State University."},{"key":"S1471068406002985_ref58","volume-title":"Supercompilers for Parallel and Vector Computers","author":"Zima","year":"1991"},{"key":"S1471068406002985_ref56","volume-title":"High Performance Compiler for Parallel Computing","author":"Wolfe","year":"1996"},{"key":"S1471068406002985_ref52","volume-title":"Procs. International Conference on Logic Programming","author":"Villaverde","year":"2001"},{"key":"S1471068406002985_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037208"},{"key":"S1471068406002985_ref4","first-page":"1578","volume-title":"Fifth International Conference and Symposium on Logic Programming","author":"Alshawi","year":"1988"},{"key":"S1471068406002985_ref57","first-page":"329","volume-title":"Proceedings of the SIGMOD International Conference on Management of Data","author":"Wolfson","year":"1988"},{"key":"S1471068406002985_ref16","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1145\/185403.185453","article-title":"Parallel Logic Programming Systems","volume":"26","author":"Chassin","year":"1994","journal-title":"ACM Computing Surveys"},{"key":"S1471068406002985_ref1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/7160.001.0001","volume-title":"Warren's Abstract Machine: a Tutorial Reconstruction","author":"Kaci","year":"1991"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068406002985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,27]],"date-time":"2020-04-27T09:55:32Z","timestamp":1587981332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068406002985\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["S1471068406002985"],"URL":"https:\/\/doi.org\/10.1017\/s1471068406002985","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]}}}