Parallel logic programming systems

ABSTRACT

Parallelizing logic programming has attracted much interest in the research community, because of the intrinsic OR- and AND-parallelisms of logic programs. One research stream aims at transparent exploitation of parallelism in existing logic programming languages such as Prolog, while the family of concurrent logic languages develops language constructs allowing programmers to express the concurrency—that is, the communication and synchronization between parallel processes—within their algorithms. This article concentrates mainly on transparent exploitation of parallelism and surveys the most mature solutions to the problems to be solved in order to obtain efficient implementations. These solutions have been implemented, and the most efficient parallel logic programming systems reach effective speedups over state-of-the-art sequential Prolog implementations. The article also addresses current and prospective research issues in extending the applicability and the efficiency of existing systems, such as models merging the transparent parallelism and the concurrent logic languages approaches, combination of constraint logic programming with parallelism, and use of highly parallel architectures.

REFERENCES

• 1: Hassan Aït-Kaci, Warren's abstract machine: a tutorial reconstruction, MIT Press, Cambridge, MA, 1991
• 2: ALl, K. A. M. AND KARLSSON, R. 1992. OR-Parallel speedups in a knowledge based system. On Muse and Aurora. In Proceedtngs of the International Conference on Fifth Geaerattoa Computer Systems ICOT, Tokyo.
• 3: ALl, K A. M aa'~D KaRLSSON, R. 1991. Scheduhng Or-Parallehsm in Muse. In Proceedtngs of the 8th Internatzonal Conference on Logic Programmmg. MIT Press, Cambridge, Mass., 807 821.
• 4: Khayri A. M. Ali , Roland Karlsson, The Muse Or-parallel Prolog model and its performance, Proceedings of the 1990 North American conference on Logic programming, p.757-776, January 1990, Austin, Texas, United States
• 5: BAHGAT, R. 1993. Non-Determtntstlc Concurrent Logzc Programming in Pandora. World Scientific Publishing, London, U.K.
• 6: BARON, U. C., CHASSIN DE KERGOMMEAUX, J., HAIL- PERIN, M., RATCLIFFE, M., ROBERT, P, SYRE, J. C., AND WESTPHAL, H. 1988a. The parallel ECRC Prolog system PEPSys: An overview and evaluation results. In Proceedings of the Internattonal Conference on Ftfth Generation Computer Systems. ICOT, Tokyo.
• 7: BARON, U. C., ING, B., RATCLIFFE, M., AND ROBERT, P. 1988b. A distributed architecture for the PEPSys parallel logic programming system. In Proceedings of ICPP'88. Pennsylvania State Univ., 410-413.
• 8: Anthony Beaumont , S. Muthu Raman , Péter Szeredi , David H. D. Warren, Flexible scheduling of or-parallelism is Aurora: the Bristol scheduler, Proceedings on Parallel architectures and languages Europe : volume II: parallel languages: volume II: parallel languages, p.403-420, June 1991, Eindhoven, The Netherlands
• 9: Gordon Bell, Ultracomputers: a teraflop before its time, Communications of the ACM, v.35 n.8, p.26-47, Aug. 1992 [doi>10.1145/135226.135227]
• 10: BORGWARDT, P. 1984. Parallel prolog using stack segments on shared memory multiprocessors. In the 84 International Symposium on Logtc Programming. IEEE, New York, 2-11.
• 11: P. G. Bosco , C. Cecchi , C. Moiso , M. Porta , G. Sofi, Logic and functional programming on distributed memory architectures, Logic programming, MIT Press, Cambridge, MA, 1990
• 12: BRAND, P. 1988. Wavefront scheduling. Int. Rep., gigalips project, SICS.
• 13: BRIAT, J., FAVRE, M., GEYER, C., AND CHASSIN DE KERGOMMEAUX, J. 1992. OPERA: OR-Parallel Prolog system on supernode. In Implementations of Distributed Prolog. John Wiley and Sons, New York, 45-63.
• 14: J. Briat , M. Favre , C. Geyer , J. Chassin de Kergommeaux, Scheduling of OR-parllel Prolog on a scalable, reconfigurable, distributed-memory multiprocessor, Proceedings on Parallel architectures and languages Europe : volume II: parallel languages: volume II: parallel languages, p.385-402, June 1991, Eindhoven, The Netherlands
• 15: Maurice Bruynooghe, A practical framework for the abstract interpretation of logic programs, Journal of Logic Programming, v.10 n.2, p.91-124, Feb. 1991 [doi>10.1016/0743-1066(91)80001-T]
• 16: BUTLER, R., DISZ, T., LUSK, E., OLSON, R., OVER- BEEK, R. A., AND STEVENS, R., 1988. Scheduling OR-paralle}ism: An Argonne perspective. In Proceedings of the 5th International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., 1590 1605.
• 17: BUTLER, R., LUSK, E. L., OLSON, R., AND OVERBEEK, R.A. 1986. ANLWAM: A parallel implementation of the Warren Abstract Machine. Tech. Rep., Argonne National Laboratories.
• 18: CALDERWOOD, A. AND SZEREDI, P. 1989. Scheduling Or-parallelism in Aurora. In Proceedings of the 6th International Conference on Logic Programming. MIT Press, Cambridge, Mass.
• 19: CARLSSON, M. AND W~DEN, J. 1988. SICStus Prolog User Manual. Res. Rep., SICS.
• 20: CHU~AYAMA, T. AND I~MURA, Y 1987. Multiple reference management in fiat GHC. In Proceedings of the 4th International Conference on Logtc Programming. MIT Press, Cambridge, Mass., 276 293.
• 21: Keith Clark , Steve Gregory, PARLOG: parallel programming in logic, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.1-49, Jan. 1986 [doi>10.1145/5001.5390]
• 22: Keith L. Clark , Steve Gregory, A relational language for parallel programming, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.171-178, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806776]
• 23: CLARK, K. AND McCABE, F. 1981. The control facilities of IC-Prolog. In Expert Systems in the Micro Electronic Age, D. Mitchie, Ed. Edinburgh University Press, Edinburgh, U. K.
• 24: W. F. Clocksin , H. Alshawi, A method for efficiently executing Horn clause programs using multiple processors, New Generation Computing, v.5 n.4, p.361-376, 1988 [doi>10.1007/BF03037415]
• 25: Christian Codognet , Philippe Codognet , Marc-Michel Corsini, Abstract interpretation for concurrent logic languages, Proceedings of the 1990 North American conference on Logic programming, p.215-232, January 1990, Austin, Texas, United States
• 26: Alain Colmerauer, An introduction to Prolog III, Communications of the ACM, v.33 n.7, p.69-90, July 1990 [doi>10.1145/79204.79210]
• 27: COLMERAUER, A. 1986. Theoretical model of Prolog II. In Logic Programming and Its Application, M. van Caneghem and D. Warren, Eds. Ablex, Norwood, N. J., 3 31.
• 28: CONERY, J.S. 1992. The OPAL Machine. In Implementations of Distributed Prolog. John Wiley and Sons, New York, 159-185.
• 29: John Simpson Conery, The and/or process model for parallel interpretation of logic programs, 1983
• 30: COSTA, V. S., WARREN, D. H. D., AND YANG, R. 1991a. The Andorra-I engine: A parallel implementation of the basic Andorra model. In Proceedings of the 8th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 825-839.
• 31: COSTA, V. S., WARREN, D. H. D., AND YANG, R. 1991b. The Andorra~I preprocessor: Supporting full Prolog on the basic Andorra model. In Proceedings of the 8th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 443-456.
• 32: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 33: James Alexander Crammond, Implementation of committed choice logic languages on shared memory multiprocessors, 1988
• 34: CHASSIN DE KERGOMMEAUX, J. 1989. Measures of the PEPSys implementation on the MX500. Tech. Rep. CA-44, ECRC.
• 35: J. Chassin de Kergommeaux , P. Robert, An abstract machine to implement or-and parallel PROLOG efficiently, Journal of Logic Programming, v.8 n.3, p.249-264, May 1990 [doi>10.1016/0743-1066(90)90025-Z]
• 36: VILLEMONTE DE LA CLERGERIE, E. 1992. Dyalog: Complete evaluation of Horn clauses by dynamic programming. Ph.D. thesis, INRIA.
• 37: Saumya K. Debray , Nai-Wei Lin , Manuel Hermnegildo, Task granularity analysis in logic programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.174-188, June 1990, White Plains, New York, United States
• 38: DEGROOT, D. 1984. Restricted And-parallelism. In Proceedings of the International Con/~rence on Fifth Generation Computer Systems 1984. ICOT, Tokyo, 471-478
• 39: DELGADO-RANNAURO, S. A. 1992a. OR-parallel logic computational models. In Implementations of D~strlbuted Prolog. John Wiley and Sons, New York, 3 26.
• 40: DELC~ADO-RANNAURO, S. A. 1992b Restricted AND- and AND/OR-parallel logic computational models. In Implementations of Distrlbuted Prolog. John Wiley and Sons, New York, 121-141.
• 41: DEI,OADO-RANNAURO, S. A. 1992c. Stream AND- parallel logic computational models. In Implementatwns of Dlstrzbated Prolog. John Wiley and Sons, New York, 239 257.
• 42: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 43: Mehmet Dincbas , Helmut Simonis , Pascal Van Hentenryck, Solving large combinatorial problems in logic programming, Journal of Logic Programming, v.8 n.1-2, p.75-93, Jan./Mar. 1990 [doi>10.1016/0743-1066(90)90052-7]
• 44: DISZ, T, LUSK, E., AND OVERBEEK, R. 1987. Experiments with OR-parallel logic programs. In the 4th International Conference on Logic Programrmng. ACM Press, New York, 576 599.
• 45: Ian Foster, Systems programming in parallel logic languages, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 46: Ian Foster , Stephen Taylor, Strand: new concepts in parallel programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 47: M. Furuichi , K. Taki , N. Ichiyoshi, A multi-level load balancing scheme for OR-parallel exhaustive search programs on the multi-PSI, ACM SIGPLAN Notices, v.25 n.3, p.50-59, Mar. 1990
• 48: Koichi Furukawa, Logic programming as the integrator of the Fifth Generation Computer Systems project, Communications of the ACM, v.35 n.3, p.82-92, March 1992 [doi>10.1145/131295.131298]
• 49: Gopal Gupta , Manuel V. Hermenegildo, ACE: And/Or-parallel Copying-based Execution of Logic Programs, Pre-Conference Workshop on Parallel Execution of Logic Programs, p.146-158, June 24, 1991
• 50: GUPTA, G ANn HERMENEGIL~)O, M. 1991b. ACE: And/Or-parallel copying-based execution of logic programs. Tech. Rep. Universidad Polit~cnica de Madrid, Spain
• 51: Gopal Gupta , Bharat Jayaraman, Optimizing and-or parallel implementations, Proceedings of the 1990 North American conference on Logic programming, p.605-623, January 1990, Austin, Texas, United States
• 52: GUPTA, G, COSTA, V. S., YANG, R., AND HERMENE- OmDO, M. V 1991 IDIOM' Integrating dependent And-, independent And-, and Or-parallelism. In Proceedings of the 1991 Internatwnal Logic Programming Symposium. MIT Press, Cambridge, Mass., 152-166.
• 53: MOOLENAR, R., VAN HECKER, H., AND DEMOEN, B. 1991. A parallel implementation of AKL. In the ILPS 91 Workshop on Implementatwn of Parallel Logic Programming Systems. ILPS.
• 54: Seif Haridi , Sverker Janson, Kernel Andorra Prolog and its computation model, Logic programming, MIT Press, Cambridge, MA, 1990
• 55: HAUSMAN, B. 1990. Pruning and speculative work in OR-Parallel Prolog. Ph.D. thesis, SICS Res. Rep D-90-9001, Royal Inst of Technology, Stockholm, Sweden.
• 56: Bogumil Hausman, Pruning and Scheduling Speculative Work in Or-Parallel Prolog, Proceedings of the Parallel Architectures and Languages Europe, Volume II: Parallel Languages, p.133-150, June 12-16, 1989
• 57: Manuel V Hermenegildo, An abstract machine for restricted AND-parallel execution of logic programs, Proceedings on Third international conference on logic programming, p.25-39, September 1986, London, United Kingdom
• 58: M. V. Hermenegildo , K. J. Greene, Prolog and its performance: exploiting independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 59: Manuel Hermenegildo , Francesca Rossi, Non-strict independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 60: N. Ichiyoshi , K. Rokusawa , K. Nakajima , Y. Inamura, A new external reference management and distributed unification for KL1, New Generation Computing, v.7 n.2-3, p.159-177, 1990 [doi>10.1007/BF03037204]
• 61: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• 62: JANSON, S. AND HARIDL S. 1991. Programming paradigms of the Andorra Kernel Language. In Proceedings of the 1991 International Logic Programming Symposium. MIT Press, Cambridge, Mass., 167 186
• 63: JONES, N. AND SONDERGAARD, H. 1987. A semantic-based framework for the abstract interpretation of Prolog. In Abstract Interpretatwn of Declaratwe Languages, S. Abramsky and C. Hankin, Eds. Ellis Horwood, 123-142.
• 64: KALi, L. V. 1987. The REDUCE-OR process model for parallel evaluation of logic programs. In Proceedings of the 4th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 616-632.
• 65: KALe, L. V. AND RAMKUMAR, B. 1992. The Reduce-OR process model for parallel logic programming on non-shared memory machines. In Implementations of Distributed Prolog. John Wiley and Sons, New York, 187-212.
• 66: Laxmikant V. Kalé , Balkrishna Ramkumar, Joining AND parallel solutions in AND/OR parallel systems, Proceedings of the 1990 North American conference on Logic programming, p.624-641, January 1990, Austin, Texas, United States
• 67: KLINGER, S. AND SHAPmO, E. 1988. A decision tree compilation algorithm for FCP ( , :, ?). In Proceedtngs of the 5th International Conference and Symposium on Logic Programming. MIT Press, Cambridge, Mass., 1315 1336.
• 68: Robert Kowalski, Logic for problem-solving, North-Holland Publishing Co., Amsterdam, The Netherlands, 1986
• 69: KUMON, K., ASATO, A., ARAI, S., SHINOGI, T., AND HATTORI, A. 1992. Architecture and implementation of PIM/p. In Proceedings' of the Internattonal Conference on Fi/~h Generatton Computer Systems 1992. ICOT, Tokyo, 414-424.
• 70: LIN, Y. J. AND KUMAR, V. 1988. AND-parallel execution of logic programs on a shared memory multiprocessor: A summary of results. In Proceedings of the 5th International Conference and Sympostum on Logic Programming. MIT Press, Cambridge Mass., 1123-1141.
• 71: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 72: LusK, E., BUTLER, R., Dfsz, T., OLSON, R., OVER- BEEK, R., STEVENS, R., WARREN, D. H. n., CALDERWODD, A., SZEREDI, P., HARIDI, S., BRAND, P., CARLSON, M., CIEPIELEWSKI, A., AND HAUS- MAN, B., 1988. The Aurora Or-parallel prolog system. In Proceedtngs of the International Conference on Fifth Generation Computer Systems 1988. ICOT, Tokyo.
• 73: MAES, L. 1992. Or-parallel speedups in a compiled PROLOG engine: Results of the integration of the Muse scheduler in the ProLog by BIM engine. Draft, BIM, Kwikcstraat 4, B-3078 Everberg, Belgium.
• 74: MAHER, M.J. 1987. Logic semantics for a class of committed-choice programs. In Proceedings of the 4th Internattonal Conference on Logic Programming. MIT Press, Cambridge, Mass., 858 876.
• 75: Hideo Masuzawa , Kouichi Kumon , Akihiro Itashiki , Ken Satoh , Yukio Sohma, “KABU-WAKE” parallel inference mechanism and its evaluation, Proceedings of 1986 ACM Fall joint computer conference, p.955-962, November 1986, Dallas, Texas, United States
• 76: C S Mellish, Abstract interpretation of Prolog programs, Proceedings on Third international conference on logic programming, p.463-474, September 1986, London, United Kingdom
• 77: MUDAMBI, S. 1991. Performances of Aurora on NUMA machmes. In Proceedings of the 8th International Conference on Logic Programruing. MIT Press, Cambridge, Mass., 793 806.
• 78: K. Muthukumar , M. V. Hermenegildo, The DCG, UDG, and MEL methods for automatic compile-time parallelization of logic programs for independent and-parallelism, Logic programming, MIT Press, Cambridge, MA, 1990
• 79: MUTHUKUMAR, K. AND HERMENEGILDO, M. 1989a. Complete and efficient methods for supporting side-effects in independent/restricted AND- parallelism. In Proceedings of the 6th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 80 97.
• 80: MUTHUKUMAR, K. AND HERMENEGILDO, M. 1989b. Determination of variable dependence information through abstract interpretation. In Proceedings of the North American Conference on Logic Programming. MIT Press, Cambridge, Mass., 166 188.
• 81: NAISH, L. 1988. Parallelizing NU-Prolog. In Proceedzngs of the 5th International Conference and Symposium on Logic Programmtng. MIT Press, Cambridge, Mass., 1546-1564.
• 82: NAISH, L. 1984. Mu-Prolog 3.1db Reference Manual. Melbourne University, Melbourne, Australia.
• 83: NAKAJIMA, K., INAMURA, Y., ICHIYOSHI, N., ROKU- SAWA, K., AND CHIKAYAMA, T. 1989. Distributed implementation of KL1 on the Multi- PSI/V2. In the 6th Internattonal Conference on Logic Programming.
• 84: NAKASHIMA, H. AND NAKAJIMA, K. 1992. Architecture and implementation of PIM/m. In Proceedings of the Internattonal Conference on Ftf~h Generation Computer Systems 1992. ICOT, Tokyo, 425-435.
• 85: PALMER, D. AND NAISH, L. 1991. NUA-Prolog: An extension to the WAM for parallel andorra. In Proceedings of the 8th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 429-442.
• 86: PERCEBOIS, C., SIGNES, N., AND SELLE, L. 1992. An actor-oriented computer for logic and its application. In Implementattons of D~stributed Prolog. John Wiley and Sons, New York, 213 235.
• 87: PEREIRA, L. M. AND PORTO, A. 1979. Intelligent backtracking and sidetracking in Horn clause programs. Tech. Rep., CINUL 2/79, Universitade Nuova de Lisboa, Portugal.
• 88: Gowri Ramanathan , Joel Oren, Survey of commercial parallel machines, ACM SIGARCH Computer Architecture News, v.21 n.3, p.13-33, June 1993 [doi>10.1145/152835.152837]
• 89: Balkrishna Ramkumar, Machine independent “and” and “or” parallel execution of logic programs, University of Illinois at Urbana-Champaign, Champaign, IL, 1992
• 90: RAMKUMAR, B. AND K~t, L.V. 1989. Compiled execution of the Reduce-OR process model on multiprocessors. In Proceedings of the North American Conference on Logtc Programming. MIT Press, Cambridge, Mass., 313-331.
• 91: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989
• 92: V. A. Saraswat, The concurrent logic programming language CP: Definition and operational semantics, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.49-62, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41630]
• 93: Vijay A. Saraswat , Martin Rinard, Concurrent constraint programming, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, December 1989, San Francisco, California, United States [doi>10.1145/96709.96733]
• 94: SATO, M. AND GOTO, A. 1988. Evaluation of the KL1 parallel system on shared memory multiprocessor. In Proceedings of the IFIP Working Conference on Parallel Processing. North-Holland, Amsterdam.
• 95: Ehud Shapiro, The family of concurrent logic programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.413-510, Sep. 1989 [doi>10.1145/72551.72555]
• 96: SHAP1RO, E. 1983. A subset of Concurrent Prolog and its interpreter. Tech. Rep, Weizmann Institute, Rehovot, Israel.
• 97: SHEN, K. AND I-IERMENEGILDO, M.V. 1991. A simulation study of Or- and independent And- parallelism. In Proceedings of the 1991 International Logic Programming Symposium. MIT Press, Cambridge, Mass., 135 151.
• 98: SZERr:m, P. 1989. Performance analysis of the Aurora OR-parallel Prolog system. In Proceedlngs of the North American Conference on Logic Programming. MIT Press, Cambridge, Mass.
• 99: TAKI, K. 1992. Parallel Inference Machine PIM. In Proceedings of the International Con/erence on F~fth Generation Computer Systems 1992. ICOT, Tokyo, 50 72.
• 100: Stephen Taylor, Parallel logic programming techniques, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 101: Stephen Taylor , Shmuel Safra , Ehud Shapiro, A parallel implementation of flat concurrent prolog, International Journal of Parallel Programming, v.15 n.3, p.245-275, June 1986 [doi>10.1007/BF01414556]
• 102: Evan Tick, Comparing Two Parallel Logic-Programming Architectures, IEEE Software, v.6 n.4, p.71-80, July 1989 [doi>10.1109/52.31654]
• 103: TICK, E. 1988 Compile-time granularity analysis for parallel logic programming languages In Proceedings of the International Conference on Fifth Generation Computer Systems 1988. ICOT, Tokyo, 994 1000.
• 104: K. Ueda , T. C. Chikayama, Design of the kernel language for the parallel inference machine, The Computer Journal, v.33 n.6, p.494-500, Dec. 1990 [doi>10.1093/comjnl/33.6.494]
• 105: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 106: VAN HENTENRYCK, P. 1989b. Parallel constraint satisfaction in logic programming. Preliminary results of Chip within PEPSys In Proceedings of the 6th International Conference on Logic Programming. MIT Press, Cambridge, Mass., 165-180.
• 107: Pascal Van Hentenryck , Vijay Saraswat , Yves Deville, Design, Implementation, and Evaluation of the Constraint Language cc(FD), Brown University, Providence, RI, 1993
• 108: Peter Van Roy , Alvin M. Despain, High-Performance Logic Programming with the Aquarius Prolog Compiler, Computer, v.25 n.1, p.54-68, January 1992 [doi>10.1109/2.108055]
• 109: André Véron , Kees Schuerman , Mike Reeve , Liang-Liang Li, Why and How in the ElipSys OR-parallel CLP System, Proceedings of the 5th International PARLE Conference on Parallel Architectures and Languages Europe, p.291-303, June 14-17, 1993
• 110: WARREN, D. H.D. 1990 The extended Andorra model with m~plicit control. In the ICLP 90 Workshop olz Parallel Logic Programming. Presentation slides
• 111: WARREN, D. H. D. 1988. The Andorra principle. Int. Rep., Gigalips Group.
• 112: WARREN, D. H.D. 1987. The SRI model for Orparallel execution of Prolog. Abstract design and ~mplementation issues. In Proceedtngs of the 1987 Symposium on Logic Programmtng. IEEE Computer Society Press, Los Alamitos, Call/, 46-53.
• 113: WARREN, D. H. D. 1983. An abstract Prolog instruction set. Tech. Rep. in309, SRI, Menlo Park, Calif.
• 114: WARREN, D. H. D. AND HARIDI, S. 1988. Data Diffusion Machme--A scalable shared virtual memory multiprocessor. In Proceedmgs of the International Conference on Fifth Generation Computer Systems 1988. ICOT, Tokyo, 943 952.
• 115: WESTPHAL, H, ROBERT, P., CHASSIN, J., AND SYRE, J.-C. 1987 The PEPSys Model: Cmnbinmg backtracking, AND- and OR-parallelism. In Proceedings of the 1987 Symposium on Logic Programming IEEE Computer Society Press, Los Alamitos, Cahf., 436-448
• 116: WINS~OROU(~H, W AND WAERN, A. 1988. Transparent And-parallelism in the presence of shared free variables. In Proceedings of the 5th Internatto,al Conference and Symposium on Logic PrograrnmLng. MIT Press, Cambridge, Mass, 749 764.
• 117: Rong Yang , Hideo Aiso, P-Prolog: a parallel logic programming language based on exclusive relation, Proceedings on Third international conference on logic programming, p.255-269, September 1986, London, United Kingdom
• 118: Rong Yang , Tony Beaumont , Inês Dutra , Víctor Santos Costa , David H. D. Warren, Performance of the compiler-based Andorra-I system, Proceedings of the tenth international conference on logic programming on Logic programming, p.150-166, August 1993, Budapest, Hungary

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages
      D.3.4 Processors
          Subjects: Compilers; Interpreters

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

General Terms:
Languages

Keywords:
AND-parallelism, OR-parallelism, Prolog, Warren Abstract Machine, binding arrays, concurrent constraint programming, constraints, guard, hash windows, load balancing, massive parallelism, memory management, multisequential implementation techniques, nondeterminism, scheduling parallel tasks, static analysis