A General Framework for Static Cost Analysis of Parallel Logic Programs

Maximiliano Klemen*, Pedro López-García, John Patrick Gallagher, José F. Morales, Manuel Hermenegildo

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

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.
Original languageEnglish
Title of host publicationLogic-Based Program Synthesis and Transformation - 29th International Symposium : LOPSTR 2019 Revised Selected Papers
EditorsMaurizio Gabbrielli
Volume12042
PublisherSpringer
Publication dateApr 2020
Pages19-35
ISBN (Print)9783030452599
ISBN (Electronic)9783030452605
DOIs
Publication statusPublished - Apr 2020
Event29th International Symposium Logic-Based Program Synthesis and Transformation - Porto, Portugal
Duration: 8 Oct 201910 Oct 2019
Conference number: 29
http://www.cs.unibo.it/projects/lopstr19/

Conference

Conference29th International Symposium Logic-Based Program Synthesis and Transformation
Number29
Country/TerritoryPortugal
CityPorto
Period08/10/201910/10/2019
Internet address
SeriesLecture Notes in Computer Science
Volume12042
ISSN0302-9743
SeriesTheoretical Computer Science and General Issues
Volume12042

Bibliographical note

Important note from the Publisher regarding the attached version of the article: “This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-45260-5_2”.

Keywords

  • Program analysis
  • Parallel programming
  • static cost analysis

Cite this