A general framework for static cost analysis of parallel logic programs

DOI10.1007/978-3-030-45260-5_2MaRDI QIDQ5097623zbMATH OpenOpenAlexFDO

Authors Maximiliano Klemen, P. López-García, John P. Gallagher, Manuel Hermenegildo, J. F. Morales

Publication date 25 August 2022

Published in Logic-Based Program Synthesis and Transformation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.13272, http://oa.upm.es/62514/

zbMATH Keywords

(constraint) logic programmingcomplexity analysisparallelismPrologresource usage analysisstatic analysis

Mathematics Subject Classification ID

Logic programming (68N17) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Abstract: The estimation and control of resource usage is now an important challenge in an increasing number of computing systems. In particular, requirements on timing and energy arise in a wide variety of applications such as internet of things, cloud computing, health, transportation, and robots. At the same time, parallel computing, with (heterogeneous) multi-core platforms in particular, has become the dominant paradigm in computer architecture. Predicting resource usage on such platforms poses a difficult challenge. Most work on static resource analysis has focused on sequential programs, and relatively little progress has been made on the analysis of parallel programs, or more specifically on parallel logic programs. We propose a novel, general, and flexible framework for setting up cost equations/relations which can be instantiated for performing resource usage analysis of parallel logic programs for a wide range of resources, platforms and execution models. The analysis estimates both lower and upper bounds on the resource usage of a parallel program (without executing it) as functions on input data sizes. In addition, it also infers other meaningful information to better exploit and assess the potential and actual parallelism of a system. We develop a method for solving cost relations involving the max function that arise in the analysis of parallel programs. Finally, we instantiate our general framework for the analysis of logic programs with Independent And-Parallelism, report on an implementation within the CiaoPP system, and provide some experimental results. To our knowledge, this is the first approach to the cost analysis of parallel logic programs.

Recommendations

• Automatic Static Cost Analysis for Parallel Programs
• Parallel cost analysis
• A cost model for the AND-parallel execution of logic programs
• Using Combined Static Analysis and Profiling for Logic Program Execution Time Estimation
• Static analysis of logic programs for independent and parallelism

Cites work

• A Flexible, (C)LP-Based Approach to the Analysis of Object-Oriented Programs
• A framework for verification and debugging of resource usage properties: resource usage verification
• A general framework for static profiling of parametric resource usage
• A provable time and space efficient implementation of NESL
• A transformational approach to parametric accumulated-cost static profiling
• An asymptotic theory for recurrence relations based on minimization and maximization.
• Automatic Static Cost Analysis for Parallel Programs
• Closed-form upper bounds in static cost analysis
• Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor)
• Interval-based resource usage verification by translation into Horn clauses and an application to energy consumption
• Mechanical program analysis
• Multidimensional Divide-and-Conquer Maximin Recurrences
• Parallel cost analysis
• Practical foundations for programming languages
• Resource usage analysis of logic programs via abstract interpretation using sized types
• Strict and nonstrict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions
• Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences

Cited in

(11)

• Automatic Static Cost Analysis for Parallel Programs
• Resource usage analysis of logic programs via abstract interpretation using sized types
• A Dependently Typed Framework for Static Analysis of Program Execution Costs
• A general framework for static profiling of parametric resource usage
• Parallel cost analysis
• ANALYSIS OF PRAM INSTRUCTION SETS FROM A LOG COST PERSPECTIVE
• Using Combined Static Analysis and Profiling for Logic Program Execution Time Estimation
• Characterising effective resource analyses for parallel and distributed coordination
• Parallel Logic Programming: A Sequel
• Analysing parallel complexity of term rewriting
• On complexity bounds and confluence of parallel term rewriting

This page was built for publication: A general framework for static cost analysis of parallel logic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097623)