Analysis of Or-parallel execution models

ABSTRACT

We discuss fundamental limitations of or-parallel execution models of nondeterministic programming languages. Or-parallelism corresponds to the execution of different nondeterministic computational paths in parallel. A natural way to represent the state of (parallel) execution of a nondeterministic program is by means of an or-parallel tree. We identify three important criteria that underlie the design of or-parallel implementations based on the or-parallel tree: constant-time access to variables, constant-time task creation, and constant-time task switching, where the term constant-time means that the time for these operations is independent of the number of nodes in the or-parallel tree, as well as the size of each node. We prove that all three criteria cannot be simultaneously satisfied by any or-parallel execution model based on a finite number of processors but unbounded memory. We discuss in detail the application of our result to the class of logic programming languages and show how our result can serve as a useful way to categorize the various or-parallel methods proposed in this field. We also discuss the suitability of different or-parallel implemenation strategies for different parallel architectures.

REFERENCES

• 1: ALI, K. Or-parallel execution of Prolog on BC-machine. In Proceedings of the 5th International Conference and Symposium on Logic Programming (Seattle,, Wash.). MIT Press, Cambridge, Mass., 1988, 253-268.
• 2: 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
• 3: BEAUMONT, A. J., RAMAN, M., 8ZEREDI, P., AND WARREN, D. H D. The Bristol scheduler for Aurora. Tech. Rep. TR-90-O4, Dept. of Computer Science, Univ. of Bristol, U.K., 1990.
• 4: BORGWARDT, P. Parallel Prolog using stack segments on shared memory multiprocessors. In Proceedings of the 1984 I, ternational Symposium on Logic Progromming (Atlantic City, N.J.). IEEE Computer Society, Washington, D.C., 1984~ 2 11.
• 5: CALDERWOOD, A., AND SZEREDI, P. The Manchester scheduler. In Internattonal Conference on Logtc Programmtng '89. MIT Press, Cambridge, Mass., 1989, 419 435.
• 6: 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]
• 7: CoI~ER~, J. S. Binding environments for parallel logic programs in nonshared memory multiprocessors. In 1987 IEEE Internatwnal Symposium m Logtc Programmtng (San Francisco, Calif.) IEEE, New York, 1987, 457 467.
• 8: DIsz, T., LUSK, E., AND OVERBEEK, R. Experiments with OR-parallel logic programs. In 1987 IEEE International Symposium in Logic Programming (San Francisco, Calif.). IEEE Computer Society, Washington, D.C., 1987, 576-600.
• 9: Gopal Gupta, Parallel execution of logic programs on shared memory multiprocessors, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1992
• 10: GUPTA, G., AND JAYARAMAN, B. Compiled and-or parallel execution of logic programs. In Proceedmgs of ~he North Amer~can Conference on Log~c Programmmg '89. MIT Press, Cambridge, Mass., 1989, 332-349.
• 11: HAUSMAN, B., AND CIEPIELEWSKI, A. A formal model for or-parallel execution of logic programs. In IFIP 83, P. C. Mason, Ed. North-Holland, Amsterdam, 1983.
• 12: HAUSMAN, B., AND CIEPIELEWSKI, A. Performance evaluation of an or-parallel execution model for logic programs. In Symposium on Logic ProAEramminAE. IEEE Computer Society, 1986, 246-255.
• 13: HAUSMAN, B., CmPmLEWSKI, A., AND HAreng, S. Or-parallel Prolog ruade efficient on shared memory multiprocessors. In 1987 IEEE Internatwnal Symposium in Logic Programming (San Francisco, Calif.). IEEE, New York, 1987, 69-79.
• 14: HERMENEGILDO, M., AND GREEN, K. J. &-Prolog system: Exploiting independent andparallelism. New Gen. Comput. 9, 3 (May 1991). 233-256.
• 15: V. K. Janakiram , D. P. Agrawal , R. Mehrotra, A Randomized Parallel Backtracking Algorithm, IEEE Transactions on Computers, v.37 n.12, p.1665-1676, December 1988 [doi>10.1109/12.9745]
• 16: KUMON, K., MASUZAWA, H., ITASHIKI, A., SATOH, K., AND SOHMA, Y. Kabu-wake: A new parallel method and its evaluation. In Proceedings of CompCon '86. IEEE Computer Society, Washington, D.C., 1986, 168-172.
• 17: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989 [doi>10.1145/75104.75105]
• 18: LIN, Z. Expected performance of the randomized parallel backtracking method. In Proceedings of the North American Conference on Logic Programming '89. MIT Press, Cambridge, Mass., 1989, 677-696.
• 19: LINDSTROM, G. Or-parallelism on applicative architectures. In 2nd International Logic Programming Conference (Uppsala, Sweden). Uppsala Univ., Uppsala, Sweden, 1984, 1-2.
• 20: E. Lusk , R. Butler , T. Disz , R. Olson , R. Overbeek , R. Stevens , D. H.D. Warren , A. Calderwood , P. Szeredi , S. Haridi , P. Brand , M. Carlsson , A. Ciepielewski , B. Hausman, The Aurora or-parallel Prolog system, New Generation Computing, v.7 n.2-3, p.243-271, 1990 [doi>10.1007/BF03037208]
• 21: MAIER, D. An efficient method for storing ancestor information in trees. SIAM J. Comput. 8, 4 (Nov. 1979), 599-618.
• 22: RAMKUMAR, B.. AND KALE, L.V. Compiled execution of the REDUCE-OR process model. In Proceedings of the North American Conference on Logic ProgramminAE '89. MIT Press, Cambridge, Mass., 1989, 313-331.
• 23: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 24: SZEREDI, P. Performance analysis ofthe Aurora or-parallel Prolog system. In Proceedings of the North Amer~can Conference on Logic Programmmg '89. MIT Press, Cambridge, Mass., 1989, 713-734.
• 25: TANAKA, H., ED. Proceedings of the International Conference on Fifth Generatzon Computer Systems. OHMSA Ltd., Tokyo, 1992.
• 26: Peter A. Tinker, Performance of an OR-parallel logic programming system, International Journal of Parallel Programming, v.17 n.1, p.59-92, Feb. 1988 [doi>10.1007/BF01379323]
• 27: WARREN, D H.D. The SRI~model for or-parallel execution of Prolog--Abs~ract design and implementation issues. In 1987 IEEE International Symposium in Loglc Programming (San Francisco, Calif.). IEEE, New York, 1987, 92-102.
• 28: D. H. D. Warren, Or-parallel execution models of prolog, II and Colloquium on Functional and Logic Programming and Specifications (CFLP) on TAPSOFT '87: Advanced Seminar on Foundations of Innovative Software Development, p.243-259, March 1987, Pisa, Italy
• 29: WARREN, D. H. D., AND HARIDI, S. The data diffusion machine--A shared virtual memory architecture for parallel execution of logic programs. In Proceedings of FGCS '88. ICOT, Tokyo, 1988, 943 952.
• 30: WARREN, D.S. Efficient Prolog memory management for flexible control strategies. In The 1984 International Symposium on Logic ProAE'ramming (Atlantlc City, N.J.) IEEE Computer Society, Washington, D.C., 1984, 198 202.
• 31: WESTPHAL, H., ROBERT, P, C~ASSI~, J., ^r~D SXXE, J. The PEPSys modeh Combining backtracking, AND- and OR-parallelism. In 1987 IEEE Internatwnal Symposzum in Logic Programming (San Francisco, Calif.). IEEE, New York, 1987, 436 448.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Nondeterministic languages**; Applicative (functional) languages

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

General Terms:
Languages, Performance

Keywords:
Or-parallel execution models