Nothing Special   »   [go: up one dir, main page]

Skip to main content

Sequentialization of parallel logic programs with mode analysis

  • Conference paper
  • First Online:
Logic Programming and Automated Reasoning (LPAR 1993)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 698))

Abstract

The family of concurrent logic programming languages has proved to be a great asset to programmers seeking to quickly construct efficient programs for highly parallel shared-memory machines. If these languages are to be implemented efficiently for other architectures, however, language-specific compile-time analysis techniques must be improved. This work describes a technique and implementation of “sequentialization” (compile-time ordering of body goals) based on automatic “mode analysis” (identification of input and output parameters) for a large subset of concurrent logic programs: feedback-free, fully-moded, flat-guarded programs. We present preliminary performance results from an FGHC-to-C compiler, utilizing these techniques, which produces very fast code.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. L. Alkalaj et al. Architectural Support for the Management of Tightly-Coupled, Fine-Grain Goals in Flat Concurrent Prolog. In ISCA '90, Seattle, June 1990.

    Google Scholar 

  2. M. Bruynooghe et al. An Instance of Abstract Interpretation Integrating Type and Mode Inference. In Int. Conf. and Symp. on Logic Prog., MIT Press, August 1988.

    Google Scholar 

  3. T. Chikayama. A Portable and Reasonably Efficient Implementation of KL1, ICOT, Tokyo, June 1992. Unpublished draft.

    Google Scholar 

  4. T. Chikayama et al. Overview of the Parallel Inference Machine Operating System PIMOS. In FGCS'88, pp 230–251, Tokyo, November 1988. ICOT.

    Google Scholar 

  5. K. L. Clark and S. Gregory. PARLOG: Parallel Programming in Logic. ACM Transactions on Programming Languages and Systems, 8(1):1–49, January 1986.

    Article  Google Scholar 

  6. M. Codish et al. Suspension Analysis for Concurrent Logic Programs. In International Conference on Logic Programming, pages 331–345. Paris, MIT Press, June 1991.

    Google Scholar 

  7. S. K. Debray. Static Inference of Modes and Data Dependencies in Logic Programs. ACM TOPLAS, 11(3):418–450, July 1989.

    Article  Google Scholar 

  8. S. K. Debray and D. S. Warren. Automatic Mode Inference for Prolog Programs. Journal of Logic Programming, pages 207–229, September 1988.

    Google Scholar 

  9. I. Foster and S. Taylor. Strand: New Concepts in Parallel Programming. Prentice Hall, Englewood Cliffs, NJ, 1989.

    Google Scholar 

  10. D. Gudeman et al. jc: An Efficient and Portable Sequential Implementation of Janus. In Joint Int. Conf. and Symp. on Logic Prog.. MIT Press, November 1992.

    Google Scholar 

  11. D. Gudeman and S. Miller. User Manual for jc — A Janus Compiler (version 1.56). University of Arizona, July 1992.

    Google Scholar 

  12. A. King and P. Soper. Schedule Analysis: A Full Theory, A Pilot Implementation, And A Preliminary Assessment. Technical Report CSTR 92-06, Department of Electronics and Computer Science, University Of Southampton, February 1992.

    Google Scholar 

  13. A. King and P. Soper. Schedule Analysis of Concurrent Logic Programs. In Joint Int. Conf. and Symp. on Logic Prog., pages 478–492. MIT Press, November 1992.

    Google Scholar 

  14. D. E. Knuth. The Art of Computer Programming: Searching and Sorting. Addison-Wesley, Reading MA, 2nd edition, 1973.

    Google Scholar 

  15. M. Korsloot and E. Tick. Sequentializing Parallel Programs. In Phoenix Seminar and Workshop on Declarative Programming. Sasbachwalden, FGR, November 1991.

    Google Scholar 

  16. B. C. Massey. Sequentialization of Parallel Logic Programs with Mode Analysis. Master's thesis, University of Oregon, September 1992. Tech. report CIS-TR-92-18.

    Google Scholar 

  17. K. Muthukumar et al. Determination of Variable Dependence Information Through Abstract Interpretation. In North American Conf. on Logic Prog., MIT Press, 1989.

    Google Scholar 

  18. C. D. Polychronopoulos. Parallel Programming and Compilers. Kluwer Academic Publishers, Norwell MA, 1988.

    Google Scholar 

  19. K. A. Ross and C. R. B. Wright. Discrete Mathematics. Prentice-Hall, Englewood Cliffs NJ, 2nd edition, 1988.

    Google Scholar 

  20. V. Sarkar. Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. MIT Press, Cambridge MA, 1989.

    Google Scholar 

  21. R. Sedgewick. Algorithms. Addison-Wesley, Reading MA, 1st edition, 1983.

    Google Scholar 

  22. E. Y. Shapiro. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys, 21(3):413–510, September 1989.

    Article  Google Scholar 

  23. R. M. Stallman. Using and Porting GNU CC (version 2.0). Free Software Foundation, Boston, MA, November 1990.

    Google Scholar 

  24. E. Tick. Parallel Logic Programming. MIT Press, Cambridge MA, 1991.

    Google Scholar 

  25. E. Tick and C. Banerjee. Performance Evaluation of Monaco Compiler and Runtime Kernel. In Int. Conf. on Logic Programming. Budapest, MIT Press, June 1993.

    Google Scholar 

  26. E. Tick and X. Zhong. A Compile-Time Granularity Analysis Algorithm and its Performance Evaluation. New Generation Computing, 11(3–4), June 1993.

    Google Scholar 

  27. K. R.Traub et al. Global Analysis for Partitioning Non-Strict Programs into Sequential Threads. In Conf. on Lisp and Functional Prog., pp 324–334. ACM Press, 1992.

    Google Scholar 

  28. K. Ueda and M. Morita. Moded Flat GHC and Its Message-Oriented Implementation Technique. New Generation Computing, 1993. In press.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Andrei Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Massey, B.C., Tick, E. (1993). Sequentialization of parallel logic programs with mode analysis. In: Voronkov, A. (eds) Logic Programming and Automated Reasoning. LPAR 1993. Lecture Notes in Computer Science, vol 698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56944-8_54

Download citation

  • DOI: https://doi.org/10.1007/3-540-56944-8_54

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56944-2

  • Online ISBN: 978-3-540-47830-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics