Designing a high performance parallel logic programming system

Abstract

Compilation techniques such as those portrayed by the Warren Abstract Machine (WAM) have greatly improved the speed of execution of logic programs. The research presented herein is geared towards providing additional performance to logic programs through the use of parallelism, while preserving the conventional semantics of logic languages. Two areas to which special attention is given are the preservation of sequential performance and storage efficiency, and the use of low overhead mechanisms for controlling parallel execution. Accordingly, the techniques used for supporting parallelism are efficient extensions of those which have brought high inferencing speeds to sequential implementations. At a lower level, special attention is also given to design and simulation detail and to the architectural implications of the execution model behavior. This paper offers an overview of the basic concepts and techniques used in the parallel design, simulation tools used, and some of the results obtained to date.

References

1. [1] P. Borgwardt and D. Rea. Distributed Semi-intelligent Backtracking for a Stack-based AND-parallel Prolog. In Proceedings of the 1986 Symposium on Logic Programming, pages 211-222. IEEE Computer Society, 1986.
2. [2] J.-H. Chang, A. M. Despain, and D. DeGroot. AND-parallelism of Logic Programs Based on Static Data Dependency Analysis. In Digest of Papers of COMPCON Spring '85, pages 218-225. 1985.
3. [3] A. Ciepilewski and S. Haridi. Control of Activities in the Or-Parallel Token Machine. In 1984 International Symposium on Logic Programming, Atlantic City, pages 49-58. IEEE Computer Society Press, Silver Spring, MD, February, 1984.
4. [4] M. Codish and E. Shapiro. Compiling OR-Parallelism into AND-Parallelism. In Proceedings of the Third International Conference on Logic Programming, pages 283-298. Springer-Verlag, 1986.
5. [5] J. S. Conery. The AND/OR Process Model for Parallel Interpretation of Logic Programs. PhD thesis, The University of California at Irvine, 1983. Technical Report 204.
6. [6] Doug DeGroot. Restricted And-Parallelism. Int'l Conf. on Fifth Generation Computer Systems, November, 1984.
7. [7] T. P. Dobry, Y. N. Patt, and A. M. Despain. Design Decisions Influencing the Microarchitecture for a Prolog Machine. In MICRO 17 Proceedings. 1984.
8. [8] S. Gregory. Design, Application and Implementation of a Parallel Logic Programming Language. PhD thesis, Imperial College of Science and Technology, 1985.
9. [9] M. V. Hermenegildo. An Abstract Machine Based Execution Model for Computer Architecture Design and Efficient Implementation of Logic Programs in Parallel. PhD thesis, Dept. of Electrical and Computer Engineering (Dept. of Computer Science TR-86-20), University of Texas at Austin, August, 1986.
10. [10] M. V. Hermenegildo. Relating Goal Scheduling, Precedence, and Memory Management in AND-Parallel Execution of Logic Programs. In Proceedings of the Fourth International Conference on Logic Programming. MIT Press, May, 1987.
11. [11] M. V. Hermenegildo and R. I. Nasr. Efficient Management of Backtracking in AND-parallelism. In Proceedings of the Third International Conference on Logic Programming, pages 40-55. Springer-Verlag, 1986.
12. [12] R. A. Kowalski. Predicate Logic as a Programming Language. Proc. IFIPS 74, 1974.
13. [13] Y.-J. Lin, V. Kumar, and C. Leung. An Intelligent Backtracking Algorithm for Parallel Execution of Logic Programs. In Proceedings of the Third International Conference on Logic Programming, pages 55-69. Springer-Verlag, 1986.
14. [14] R. A. Overbeek, J. Gabriel, T. Lindholm, and E. L. Lusk. Prolog on Multiprocessors. Technical Report, Argonne National Laboratory, Argonne, Ill. 60439, 1985.
15. [15] E. Y. Shapiro. A subset of Concurrent Prolog and its interpreter. Technical Report TR-003, ICOT, January, 1983. Tokyo.
16. [16] N. Tamura and Y. Kaneda. Implementing Parallel Prolog on a Multiprocessor Machine. In 1984 International Symposium on Logic Programming, Atlantic City, pages 42-49. IEEE Computer Society Press, Silver Spring, MD, February, 1984.
17. [17] E. Tick. Studies in Prolog Architectures. PhD thesis, Stanford University, 1987. In preparation.
18. [18] E. Tick and D. H. D. Warren. Towards a Pipelined Prolog Processor. In 1984 International Symposium on Logic Programming, Atlantic City, pages 29-42. IEEE Computer Society Press, Silver Spring, MD, February, 1984.
19. [19] K. Ueda. Guarded Horn Clauses. Technical Report TR-103, ICOT, 1985. Tokyo.
20. [20] K. Ueda. Making Exhaustive Search Programs Deterministic. In Proceedings of the Third International Conference on Logic Programming, pages 270-283. Springer-Verlag, 1986.
21. [21] D. H. D. Warren. An Abstract Prolog Instruction Set. Technical Note 309, SRI International, AI Center, Computer Science and Technology Division, 1983.
22. [22] D. H. D. Warren. OR-Parallel Execution Models of Prolog. In Proceedings of TAPSOFT '87. Springer-Verlag, 1987.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Logic programming and answer set programming

• Information systems

  • Information storage systems

    • Record storage systems

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software maintenance

• Software and its engineering

  • Software creation and management

    • Software post-development issues

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching

  • Logic

    • Constraint and logic programming

  • Models of computation

    • Concurrency

      • Parallel computing models