Abstract
The execution of a concurrent logic program on a distributed system is very dependent on the program granularity and the communication costs. We present a framework based on the abstract interpretation technique to obtain information about these program characteristics and show how its execution time can be improved using the analysis.
The method proposed is realized partially in compile time and partially during execution in order to minimize the runtime overhead. The static part mainly consists of a mode analysis and a type analysis. Using this latter analysis we develop one algorithm to obtain the size relationships between the terms in the heads of the program clauses. This information is essential for building the functions which give the process cost and the communication cost.
We also show how to use the static analysis to transform a concurrent logic program into a distributed program. During transformed program execution, a process will be moved to a remote node only if the relation between the computational and communication costs given by the analysis will improve its execution.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barbuti R., R. Giacobazzi, G. Levi. A General Framework for Semantics-Based Bottom-up Abstract Interpretation of Logic Programs. ACM Transactions on Programming Languages and Systems vol 15, n∘ 1, January 1993. Pages 133–181
Bruynooghe M. A Practical Framework for the Abstract Interpretation of Logic Programs. Journal of Logic Programming 10(2):91–124 (Feb. 1991)
Cortesi, A., Le Charlier, B., Van Hentenryck, P. 1994. Combinations of abstract domains for logic programming. In proceedings of the 21st ACM Symposium on Principles of Programming Languages.
Cousot P., R. Cousot. Abstract interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. Proc. 4th Ann. ACM Symp. Principles of Programming Languages, Los Angeles, California (1977) 238–252.
Debray S.K., N-W Lin. Cost Analysis of Logic Programs. ACM Transactions on Programming Languages and Systems Vol 15 N∘ 5. November 1993. Pages 826–875
Debray S.K., N-W Lin, M. Hermenegildo. Task Granularity Analysis in Logic Programs. In Proc. of the 1990 ACM Conf. on Programming Language Design and Implementation, pg. 174–188. ACM Press, June 1990.
Gallardo M., J. M. Troya. Parlog Programs Non-termination Analysis. Eighth Conference on Logic Programming. Guizzeria, Italy.(1993)
Gallardo M., J. M. Troya. Granularity Analysis of Concurrent Logic Languages based on Abstract Interpretation. In Proceedings of the Joint Conference GulpProde94.
Ichiyoshi, N., Mitazaki T., Taki K., A distributed implementation of Flat GHC on the Multi-PSI. Logic programming: Proc. of the 4th Int. Conf., MIT Press, 1987.
King A., P. Soper. Schedule Analysis of Concurrent Logic Programs. Proceedings of the Joint International Conference and Symposium on Logic Programming. Apt Editor 1992.
King A., P. Soper. Granularity Analysis of Concurrent Logic Programs. In the fifth International Symposium on Computer and Information Sciences, Nevsehir, Cappadocia, Turkey.
King, A. 1994. Depth-k sharing and freeness. In Proceedings of the 11th International Conference on Logic Progrmming. MIT Press, Cambridge, Mass., 553–568.
Mellish C. S. Abstract Interpretation of Prolog Programs. Third International Conference on Logic Programming, n. 225 Lecture Notes in Computer Science. Imperial College, Springer-Verlg, July 1986.
Sarkar V. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, Cambridge MA, 1989.
Tick E. Compile-time Granularity Analyisis for Parallel Logic Programming. Proceeding of the International Conference on fifth generation computer system.
Ueda K., Guarded Horn Clauses. Ph. D. Thesis, Graduate School, University of Tolyo, 1986.
Warren R., M. Hermenegildo, S. Debray. On the Practicality of Global Flow Analysis of Logic Programs. Fifth International Conference and Symposium on Logic Programming. MIT Press, August 1988.
Zhong X., E. Tick, S. Durvuru, A. Hansen, A.V.S. Sastry, R. Dudararajan, Towards and Efficient Compile-Time Analysis Algorithm. Proceedings of the International Conference on fifth Generation Computer Systems, 1992. Ed ICOT.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gallardo, M.M., Troya, J.M. (1996). Studying the cost of logic languages in an abstract interpretation framework for granularity analysis. In: Proietti, M. (eds) Logic Program Synthesis and Transformation. LOPSTR 1995. Lecture Notes in Computer Science, vol 1048. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60939-3_7
Download citation
DOI: https://doi.org/10.1007/3-540-60939-3_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60939-1
Online ISBN: 978-3-540-49745-5
eBook Packages: Springer Book Archive