Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T00:59:06.457Z Has data issue: false hasContentIssue false
  • English
  • Français

Annotation of logic programs for independent AND-parallelism by partial evaluation*

Published online by Cambridge University Press:  05 September 2012

GERMAN VIDAL
GERMAN VIDAL*
Affiliation:
MiST, DSIC, Universitat Politècnica de València, Camino de Vera, S/N, 46022 Valencia, Spain (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Traditional approaches to automatic AND-parallelization of logic programs rely on some static analysis to identify independent goals that can be safely and efficiently run in parallel in any possible execution. In this paper, we present a novel technique for generating annotations for independent AND-parallelism that is based on partial evaluation. Basically, we augment a simple partial evaluation procedure with (run-time) groundness and variable sharing information so that parallel conjunctions are added to the residual clauses when the conditions for independence are met. In contrast to previous approaches, our partial evaluator is able to transform the source program in order to expose more opportunities for parallelism. To the best of our knowledge, we present the first approach to a parallelizing partial evaluator.

Keywords

partial evaluationautomatic parallelizationprogram analysis
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 12 , Issue 4-5: 28th International Conference on Logic Programming , July 2012 , pp. 583 - 600
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

SWI Prolog 2012. URL: http://www.swi-prolog.org/.Google Scholar
Benkerimi, K. and Lloyd, J. 1989. A Procedure for the Partial Evaluation of Logic Programs. Technical Report TR-89-04, Department of Computer Science, University of Bristol, Bristol, England. May.Google Scholar
Consel, C. and Danvy, O. 1992. Partial evaluation in parallel. Lisp and Symbolic Computation 5, 4, 327–342.CrossRefGoogle Scholar
De Schreye, D., Glück, R., Jørgensen, J., Leuschel, M., Martens, B. and Sørensen, M. 1999. Conjunctive partial deduction: foundations, control, algorihtms, and experiments. Journal of Logic Programming 41, 2/3, 231–277.CrossRefGoogle Scholar
Debois, S. 2004. Imperative program optimization by partial evaluation. In Proc. of PEPM'04, Heintze, N. and Sestoft, P., Eds. ACM, 113–122.CrossRefGoogle Scholar
Debray, S. K. 1989. Static inference of modes and data dependencies in logic programs. ACM Transactions Programming Languages and Systems 11, 3, 418–450.CrossRefGoogle Scholar
Gallagher, J. 1991. A System for Specialising Logic Programs. Technical Report TR-91-32, University of Bristol.Google Scholar
Gallagher, J. 1993. Tutorial on Specialisation of Logic Programs. In Proceedings of the ACM Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'93). ACM, New York, 88–98.Google Scholar
Gras, D. C. and Hermenegildo, M. V. 2009. Non-strict independence-based program parallelization using sharing and freeness information. Theoretical Computer Science 410, 46, 4704–4723.CrossRefGoogle Scholar
Gurr, C. 1994. A Self-Applicable Partial Evaluator for the Logic Programming Language Goedel. PhD Thesis, Department of Computer Science, University of Bristol.Google Scholar
Jones, N. D. 1997. Combining abstract interpretation and partial evaluation (brief overview). In Proceedings of the 4th International Symposium on Static Analysis (SAS'97), Hentenryck, P. V., Ed. Lecture Notes in Computer Science, vol. 1302. Springer, 396–405.Google Scholar
Jones, N. D. 2004. Transformation by interpreter specialisation. Science of Computer Programming 52, 307–339.CrossRefGoogle Scholar
Jones, N., Gomard, C. and Sestoft, P. 1993. Partial Evaluation and Automatic Program Generation Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Leuschel, M. 2002. Homeomorphic embedding for online termination of symbolic methods. In The Essence of Computation, Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones. Springer LNCS 2566, 379–403.Google Scholar
Leuschel, M., Elphick, D., Varea, M., Craig, S. and Fontaine, M. 2006. The ecce and logen partial evaluators and their web interfaces. In Proceedings of PEPM'06. IBM Press, 88–94.CrossRefGoogle Scholar
Leuschel, M. and Vidal, G. 2009. Fast offline partial evaluation of large logic programs. In Proceedings of the 18th Int'l Symposium on Logic-based Program Synthesis and Transformation (LOPSTR 2008). Springer LNCS 5438, 119–134.CrossRefGoogle Scholar
Lloyd, J. and Shepherdson, J. 1991. Partial evaluation in logic programming. Journal of Logic Programming 11, 217–242.CrossRefGoogle Scholar
Muthukumar, K., Bueno, F., de la Banda, M. J. G. and Hermenegildo, M. V. 1999. Automatic compile-time parallelization of logic programs for restricted, goal level, independent and parallelism. Journal of Logic Programming 38, 2, 165–218.CrossRefGoogle Scholar
Sahlin, D. 1990. The mixtus approach to automatic partial evaluation of full prolog. In Proceedings of the 1990 North American Conference on Logic Programming, Debray, S. and Hermenegildo, M., Eds. The MIT Press, Cambridge, MA, 377–398.Google Scholar
Sperber, M., Thiemann, P. and Klaeren, H. 1997. Distributed partial evaluation. In Proceedings of the 2nd Int'l Workshop on Parallel Symbolic Computation (PASCO 1997), Hong, H., Kaltofen, E., and Hitz, M. A., Eds. ACM, 80–87.Google Scholar
Surati, R. J. and Berlin, A. A. 1994. Exploiting the parallelism exposed by partial evaluation. In Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques (PACT'94). IFIP Transactions, vol. A-50. North-Holland, 181–192.Google Scholar
Vidal, G. 2011. A hybrid approach to conjunctive partial evaluation of logic programs. In Logic-Based Program Synthesis and Transformation - 20th Int'l Symposium (LOPSTR 2010), Revised Selected Papers. Springer LNCS 6564, 200–214.Google Scholar