Francisco Bueno
Skip Abstract Section
Abstract
We report on a detailed study of the application and effectiveness of program analysis based on abstract interpretation of automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology for the application in the parallelization task of the information inferred by abstract interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of different analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain defined. The transformation directly illustrates the revelance and applicability of each abstract domain for the application. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benefits obtained from the information inferred. Such benefits are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data flow analysis plays an important role in achieving efficient parallelizations, and that the cost of such analysis con be reasonable even for quite sophisticated abstract domains. Furthermore, the results also offer significant insight into the characteristics of the domains, the demands of the application, and the trade-offs involved.
- ALI, K. A. M. AND I~ARLSSON~ R. 1990. The Muse Or-Parallel Prolog Model and its Performance. In 1990 North American Conference on Logic Programming (October 1990), pp. 757-776. MIT Press. Google Scholar
- BACON~ D.~ GRAHAM~ S.~ AND NHARP~ O. 1994. Compiler Transformations for High- Performance Computing. Computing Surveys 26, 4 (December), 345-420. Google Scholar
- BISWAS~ P., Su, S., AND YUN~ D. 1988. A Scalable Abstract Machine Model to Support Limited-OR/Restricted AND Parallelism in Logic Programs. In Fifth International Conference and Symposium on Logic Programming (Seattle,Washington, 1988), pp. 1160-1179.Google Scholar
- BRUYNOOGHE, M. 1991. A Practical Framework for the Abstract Interpretation of Logic Programs. Journal of Logic Programming 10, 91-124. Google Scholar
- BRUYNOOGHE, M. AND JANSSENS, CJ. 1988. An Instance of Abstract Interpretation Integrating Type and Mode Inference. In Fifth International Conference and Symposium on Logic Programming (Seattle, Washington, August 1988), pp. 669-683. MIT Press.Google Scholar
- BUENO, F., CABEZA, D., HERMENEGILDO, M., AND PUEBLA, CJ. 1996. Global Analysis of Standard Prolog Programs. In European Symposium on Programming, Number 1058 in LNCS (Sweden, April 1996), pp. 108-124. Springer-Verlag. Google Scholar
- BUENO, F., CJARCfA DE LA BANDA, M., AND HERMENEGILDO, M. 1994. A Comparative Study of Methods for Automatic Compile-time ParMlelization of Logic Programs. In First International Symposium on Parallel Symbolic Computation (September 1994), pp. 63-73. World Scientific Publishing Company.Google Scholar
- BUENO, F., HERMENEGILDO, M., MONTANARI, U., AND ROSSI, F. 1998. Partial Order and Contextual Net Semantics for Atomic and Locally Atomic CC Programs. Science of Computer Programming 30, 51-82. Special CCP95 Workshop issue. Google Scholar
- BUENO CARRILLO, F. 1994. Automatic Optimisation and Parallelisation of Logic Programs through Program Transformation. Ph.D. thesis, Universidad Polit6cnica de Madrid (UPM).Google Scholar
- CABEZA, D. AND HERMENEGILDO, M. 1994. Extracting Non-strict Independent Andparallelism Using Sharing and Freeness Information. In 199~ International Static Analysis Symposium, Number 864 in LNCS (Namur, Belgium, September 1994), pp. 297-313. Springer- Verlag.Google Scholar
- CHANG, J.-H., DESPAIN, A. M., AND DEGROOT, D. 1985. And-ParMlelism of Logic Programs Based on Static Data Dependency Analysis. In Compcon Spring '85 (February 1985), pp. 218-225.Google Scholar
- CHANG, S.-E. AND CHIANG, Y. P. 1989. Restricted AND-ParMlelism Execution Model with Side-Effects. In E. L. LUSK AND R. A. OVERBEEK Eds., Proceedings of the North American Conference on Logic Programming (1989), pp. 350-368. MIT Press, Cambridge, MA.Google Scholar
- CHASSIN, J. AND CODOGNET, P. 1994. Parallel Logic Programming Systems. Computing Surveys 26, 3 (September), 295-336. Google Scholar
- CLARK, K. AND GREGORY, S. 1986. Parlog: Parallel Programming in Logic. Journal of the A CM 8, 1-49. Google Scholar
- CODISH, M., BRUYNOOGHE, M., CJARCIA DE LA BANDA, M., AND HERMENEGILDO, M. 1997. Exploiting Goal Independence in the Analysis of Logic Programs. Journal of Logic Programruing 32, 3 (September), 247-261.Google Scholar
- CODISH, M., DAMS, D., AND YARDENI, E. 1991. Derivation and Safety of an Abstract Unification Algorithm for Groundness and Aliasing Analysis. In Eighth International Conference on Logic Programming (Paris, France, June 1991), pp. 79-96. MIT Press.Google Scholar
- CODISH, M., DAMS, D., AND YARDENI, E. 1994. Bottom-up Abstract Interpretation of Logic Programs. Theoretical Computer Science 12~, 93-125. Google Scholar
- CODISH, M., MULKERS, A., BRUYNOOGHE, M., GARCfA DE LA BANDA, M., AND HERMENEGILDO, M. 1995. Improving Abstract Interpretations by Combining Domains. A CM Transactions on Programming Languages and Systems 17, 1 (January), 28-44. Google Scholar
- CONERY, J.S. 1983. The And/Or Process Model for Parallel Interpretation of Logic Programs. Ph. D. thesis, The University of California At Irvine. Technical Report 204. Google Scholar
- COUSOT, P. AND COUSOT, R. 1977. Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Fourth A CM Symposium on Principles of Programming Languages (1977), pp. 238-252. Google Scholar
- COUSOT, P. AND COUSOT, R. 1979. Systematic Design of Program Analysis Frameworks. In Sixth A CM Symposium on Principles of Programming Languages (San Antonio, Texas, 1979), pp. 269-282. Google Scholar
- DEBRAY, S. Ed. 1992. Journal of Logic Programming, Special Issue: Abstract Interpretation, Volume 13(1-2). North-Holland.Google Scholar
- DEBRAY, S.K. 1989. Static Inference of Modes and Data Dependencies in Logic Programs. ACM Transactions on Programming Languages and Systems 11, 3, 418-450. Google Scholar
- DEGROOT, D. 1984. Restricted AND-ParMlelism. In International Conference on Fifth Generation Computer Systems (November 1984), pp. 471-478. Tokyo.Google Scholar
- DEGROOT, D. 1987. Restricted AND-ParMlelism and Side-Effects. In International Symposium on Logic Programming (August 1987), pp. 80-89. San Francisco: IEEE Computer Society.Google Scholar
- FERNANDEZ, ~/{., CARRO, ~/{., AND HERMENEGILDO, ~/{. 1996. IDRA (IDeal Resource Allocation): Computing Ideal Speedups in Parallel Logic Programming. In Proceedings of EuroPar'96, Number 1124 in LNCS (August 1996), pp. 724-734. Springer-Verlag. Google Scholar
- GARCIA DE LA BANDA, M. 1994. Independence, Global Analysis, and Parallelism in Dynamically Scheduled Constraint Logic Programming. Ph. D. thesis, Universidad Polit6cnica de Madrid (UPM), Facultad Informatica UPM, 28660-Boadilla del Monte, Madrid-Spain.Google Scholar
- GARCfA DE LA BANDA, ~/{., BUENO, F., AND HERMENEGILDO, ~/{. 1996. Towards Independent And-ParMlelism in CLP. In Programming Languages: Implementation, Logics, and Programs, Number 1140 in LNCS (Aachen, Germany, September 1996), pp. 77-91. Springer-Verlag. Google Scholar
- GARCIA DE LA BANDA, M., HERMENEGILDO, M., AND MARRIOTT, K. 1993. Independence in Constraint Logic Programs. In 1993 International Logic Programming Symposium (October 1993), pp. 130-146. MIT Press, Cambridge, MA. Google Scholar
- GETZlNGER, W.W. 1993. Abstract Interpretation for the Compile-Time Optimization of Logic Programs. Ph. D. thesis, University of Southern California, Dept. of Computer Science. Google Scholar
- GIACOBAZZI, R. 1993. Semantic Aspects of Logic Program Analysis. Ph.D. thesis, UniversitS~ degli Studi di Pisa, Dipartimento di Informatica.Google Scholar
- GUPTA, G. AND COSTA, V.S. 1992. Cuts and Side-Effects in And-Or Parallel Prolog. Journal of Logic Programmin9 27, 1 (April), 45-71.Google Scholar
- GUPTA, G. AND JAYARAMAN, B. 1989. Compiled And-Or Parallelism on Shared Memory Multiprocessors. In 1989 North American Conference on Logic Programming (October 1989), pp. 332-349. MIT Press.Google Scholar
- GUPTA, G., SANTOS-COSTA, V., YANG, R., AND HERMENEGILDO, M. 1991. IDIOM: Integrating Dependent And-, Independent And-, and Or-parMlelism. In 1991 International Logic Programming Symposium (October 1991), pp. 152-166. MIT Press.Google Scholar
- HERMENEGILDO, M. 1986a. An Abstract Machine Based Execution Model for Computer Architecture Design and Efficient Implementation of Logic Programs in Parallel. Ph.D. thesis, Dept. of Electrical and Computer Engineering (Dept. of Computer Science TR-86-20), University of Texas at Austin, Austin, Texas 78712. Google Scholar
- HERMENEGILDO, M. 1986b. An Abstract Machine for Restricted AND-parallel Execution of Logic Programs. In Third International Conference on Logic Programming, Number 225 in Lecture Notes in Computer Science (July 1986), pp. 25-40. Imperial College: Springer-Verlag. Google Scholar
- HERMENEGILDO, M. 1997. Automatic Parallelization of Irregular and Pointer-Based Computations: Perspectives from Logic and Constraint Programming. In Proceedings of EUROPAR'97, LNCS (August 1997), pp. 31-46. Springer-Verlag. (invited). Google Scholar
- HERMENEGILDO, M. AND GREENE, K. 1991. The &-Prolog System: Exploiting Independent And-Parallelism. New Generation Computing 9, 3,4, 233-257.Google Scholar
- HERMENEGILDO, M. AND ROSSI, F. 1995. Strict and Non-Strict Independent And-Parallelism in Logic Programs: Correctness, Efficiency, and Compile-Time Conditions. Journal of Logic Programmin9 22, 1, 1-45.Google Scholar
- HERMENEGILDO, M. AND THE CLIP GROUP. 1994. Some Methodological Issues in the Design of CIAO - A Generic, Parallel, Concurrent Constraint System. In Principles and Practice of Constraint Programming, Number 874 in LNCS (May 1994), pp. 123-133. Springer-Verlag. Google Scholar
- HERMENEGILDO, M., WARREN, R., AND DEBRAY, S. K. 1992. Global Flow Analysis as a Practical Compilation Tool. Journal of Logic Programming 13, 4 (August), 349-367. Google Scholar
- JACOBS, D. AND LANGEN, A. 1988. Compilation of Logic Programs for Restricted And- Parallelism. In European Symposium on Programming (1988), pp. 284-297. Google Scholar
- JACOBS, D. AND LANGEN, A. 1989. Accurate and Efficient Approximation of Variable Aliasing in Logic Programs. In 1989 North American Conference on Logic Programming (October 1989). MIT Press.Google Scholar
- JACOBS, D. AND LANGEN~ A. 1992. Static Analysis of Logic Programs for Independent And- Parallelism. Journal of Logic Programming 13, 2 and 3 (July), 291-314. Google Scholar
- KALI~, L.V. 1987. Completeness and Full Parallelism of Parallel Logic Programming Schemes. In Fourth IEEE Symposium on Logic Programming (1987), pp. 125-133. IEEE.Google Scholar
- LE CHARLIER~ B.~ DAGIMBE~ O.~ MICHEL~ L.~ AND VAN HENTENRYCK~ P. 1993. Optimization Techniques for General Purpose Fixpoint Algorithms: Practical Efficiency for the Abstract Interpretation of Prolog. In Workshop on Static Analysis (September 1993), pp. 15-26. Springer- Verlag. Google Scholar
- LIN~ Y.-J. 1988. A Parallel Implementation of Logic Programs. Ph. D. thesis, Dept. of Computer Science, University of Texas at Austin, Austin, Texas 78712. Google Scholar
- LIN~ Y. J. AND KUMAR~ V. 1988. AND-ParMlel Execution of Logic Programs on a Shared Memory Multiprocessor: A Summary of Results. In Fifth International Conference and Symposium on Logic Programming (August 1988), pp. 1123-1141. MIT Press.Google Scholar
- LOPEZ CxARCIAv P., HERMENEGILDOv M., AND DEBRAYv S. I~. 1996. A Methodology for Granularity Based Control of Parallelism in Logic Programs. Journal of Symbolic Computation, Special Issue on Parallel Symbolic Computation 22, 715-734. Google Scholar
- LUSK ET AL.~ E. 1988. The Aurora Or-ParMlel Prolog System. In International Conference on Fifth Generation Computer Systems (November 1988). Tokyo.Google Scholar
- LUSK ET AL.~ E. 1990. The Aurora Or-ParMlel Prolog System. New Generation Computing 7, 2,3. Google Scholar
- MARIEN~ A.~ JANSSENS~ CJ.~ MULKERS~ A.~ AND BRUYNOOGHE~ M. 1989. The Impact of Abstract Interpretation: an Experiment in Code Generation. In Sixth International Conference on Logic Programming (June 1989), pp. 33-47. MIT Press.Google Scholar
- MARRIOTT~ K.~ GARCfA DE LA BANDA~ M.~ AND HERMENEGILDO~ M. 1994. Analyzing Logic Programs with Dynamic Scheduling. In 20th. Annual A CM Conf. on Principles of Programruing Languages (January 1994), pp. 240-254. ACM. Google Scholar
- MARRIOTT~ K. AND SONDERGAARD~ H. 1989. Semantics-based dataflow analysis of logic programs. Information Processing, 601-606.Google Scholar
- McALOON, K. AND TRETKOFF~ C. 1989. 2LP: A logic programming and linear programming system. Technical Report 1989-21, Brooklyn College of CUNY, CIS department.Google Scholar
- MELLISH~ C. 1986. Abstract Interpretation of Prolog Programs. In Third International Conference on Logic Programming, Number 225 in LNCS (July 1986), pp. 463-475. Springer-Verlag. Google Scholar
- MUTHUKUMAR~ K.~ BUENO~ F.~ DE LA BANDA~ M. CJ.~ AND HERMENEGILDO~ M. 1999. Automatic Compile-time Parallelization of Logic Programs for Restricted, GoM-level, Independent And-parMlelism. Journal of Logic Programming 38, 2 (February), 165-218.Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1989a. Complete and Efficient Methods for Supporting Side Effects in Independent/Restricted And-parMlelism. In 1989 International Conference on Logic Programming (June 1989), pp. 80-101. MIT Press.Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1989b. Determination of Variable Dependence Information at Compile-Time Through Abstract Interpretation. In 1989 North American Conference on Logic Programming (October 1989), pp. 166-189. MIT Press.Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1990a. Deriving A Fixpoint Computation Algorithm for Top-down Abstract Interpretation of Logic Programs. Technical Report ACT-DC- 153-90 (April), Microelectronics and Computer Technology Corporation (MCC), Austin, TX 78759. Available from http ://www. clip. dia. fi. upm. es.Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1990b. The CDG, UDG, and MEL Methods for Automatic Compile-time Parallelization of Logic Programs for Independent And-parallelism. In Int'l. Conference on Logic Programming (June 1990), pp. 221-237. MIT Press. Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1991. Combined Determination of Sharing and Freeness of Program Variables Through Abstract Interpretation. In 1991 International Conference on Logic Programming (June 1991), pp. 49-63. MIT Press.Google Scholar
- MUTHUKUMAR~ K. AND HERMENEGILDO~ M. 1992. Compile-time Derivation of Variable Dependency Using Abstract Interpretation. Journal of Logic Programming 13, 2/3 (July), 315-347. Originally published as Technical Report FIM 59.1/IA/90, Computer Science Dept, Universidad Politecnica de Madrid, Spain, August 1990. Google Scholar
- PONTELLI, E., GUPTA, G., PULVIRENTI, F., AND FERRO, A. 1997. Automatic Compile-time Parallelization of Prolog Programs for Dependent And-Parallelism. In Proc. of the Fourteenth International Conference on Logic Programming (July 1997), pp. 108-122. HIT Press.Google Scholar
- RAMKUMAR, B. AND KALE, L.V. 1989. Compiled Execution of the Reduce-OR Process Model on Multiprocessors. In 1989 North American Conference on Logic Programming (October 1989), pp. 313-331. HIT Press.Google Scholar
- SaNTOS-COSTa, V., WARREN, D., AND YANG, R. 1990. Andorra-I: A Parallel Prolog System that Transparently Exploits both And- and Or-parallelism. In Proceedings of the 3rd. A CM SIGPLAN Symposium on Principles and Practice of Parallel Programming (April 1990). ACM. Google Scholar
- SANTOS COSTA, V. M. 1993. Compile-Time Analysis for the Parallel Execution of Logic Programs in Andorra-I. Ph. D. thesis, University of Bristol.Google Scholar
- SARASWAT, V. 1989. Concurrent Constraint Programming Languages. Ph. D. thesis, Carnegie Mellon, Pittsburgh. School of Computer Science. Google Scholar
- SARKAR, V. (1989). Partitioning and Scheduling Parallel Programs for Multiprocessors. Pitman, London. Google Scholar
- SARKAR, V. 1990. Instruction Reordering for Fork-Join Parallelism. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, Volume 25 (June 1990), pp. 322-336. Google Scholar
- SHAPIRO, E. 1989. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys 21, 3 (September), 412-510. Google Scholar
- SHEN, K. 1996. Overview of DASWAM: Exploitation of Dependent And-parallelism. Journal of Logic Programming 29, 1-3 (November), 245-293.Google Scholar
- SHEN, K. AND HERMENEGILDO, M. 1991. A Simulation Study of Or- and Independent Andparallelism. In International Logic Programming Symposium (October 1991), pp. 135-151. HIT Press.Google Scholar
- SONDERGAARD, H. 1986. An application of abstract interpretation of logic programs: occur check reduction. In European Symposium on Programming, LNCS 123 (1986), pp. 327-338. Springer-Verlag. Google Scholar
- SZEREDI, P. 1989. Performance Analysis of the Aurora Or-Parallel Prolog System. In 1989 North American Conference on Logic Programming (October 1989). HIT Press.Google Scholar
- TAYLOR, A. 1990. LIPS on a HIPS: Results from a prolog compiler for a RISC. In 1990 International Conference on Logic Programming (June 1990), pp. 174-189. HIT Press. Google Scholar
- TAYLOR, S., SAFRA, S., AND SHAPIRO, E. 1987. A parallel implementation of flat concurrent prolog. In E. SHAPIRO Ed., Concurrent Prolog: Collected Papers (Cambridge HA, 1987), pp. 575-604. HIT Press. Google Scholar
- UEDA, K. 1987. Guarded Horn Clauses. In E. SHAPIRO Ed., Concurrent Prolog: Collected Papers, pp. 140-156. Cambridge HA: HIT Press. Google Scholar
- VAN HENTENRYCK, P. 1989. Parallel Constraint Satisfaction in Logic Programming. In Sixth International Conference on Logic Programming (Lisbon, Portugal, June 1989), pp. 165-180. HIT Press.Google Scholar
- VAN ROY, P. AND DESPAIN, A. M. 1990. The Benefits of Global Dataflow Analysis for an Optimizing Prolog Compiler. In North American Conference on Logic Programming (October 1990), pp. 501-515. HIT Press. Google Scholar
- WARREN, D. 1983. An Abstract Prolog Instruction Set. Technical Report 309, SRI International.Google Scholar
- WARREN, D. 1987a. OR-Parallel Execution Models of Prolog. In Proceedings of TAPSOFT '87, Lecture Notes in Computer Science (March 1987). Springer-Verlag. Google Scholar
- WARREN, D. 1987b. The SRI Model for OR-Parallel Execution of Prolog--Abstract Design and Implementation. In International Symposium on Logic Programming (August 1987), pp. 92-102. San Francisco: IEEE Computer Society. Google Scholar
- WARREN~ R.~ HERMENEGILDO~ ~/{.~ AND DEBRAY~ S. I~. 1988. On the Practicality of Global Flow Analysis of Logic Programs. In Fifth International Conference and Symposium on Logic Programming (August 1988), pp. 684-699. MIT Press.Google Scholar
- WESTPHAL~ H. AND ROBERT~ P. 1987. The PEPSys Model: Combining Backtracking, AND- and OR- Parallelism. In Syrup. of Logic Prog. (August 1987), pp. 436-448.Google Scholar
Index Terms
- Effectivness of abstract interpretation in automatic parallelization: a case study in logic programming
Recommendations
Complementation in abstract interpretation
Reduced product of abstract domains is a rather well-known operation for domain composition in abstract interpretation. In this article, we study its inverse operation, introducing a notion of domain complementation in abstract interpretation. ...
Non-strict independence-based program parallelization using sharing and freeness information
The current ubiquity of multi-core processors has brought renewed interest in program parallelization. Logic programs allow studying the parallelization of programs with complex, dynamic data structures with (declarative) pointers in a comparatively ...
A comparison of automatic parallelization tools/compilers on the SGI origin 2000
SC '98: Proceedings of the 1998 ACM/IEEE conference on SupercomputingPorting applications to new high performance parallel and distributed computing platforms is a challenging task. Since writing parallel code by hand is time consuming and costly, porting codes would ideally be automated by using some parallelization ...
Comments