A general framework for static cost analysis of parallel logic programs

Klemen, Maximiliano and López García, Pedro and Gallagher, John P. and Morales Caballero, José Francisco and Hermenegildo, Manuel V. (2019). A general framework for static cost analysis of parallel logic programs. In: "29th International Symposium on Logic-Based Program Synthesis and Transformation ( LOPSTR 2019)", 8-10 Oct 2019, Oporto, Portugal. ISBN 978-3-030-45259-9. pp. 19-35. https://doi.org/10.1007/978-3-030-45260-5_2.

Description

Title: A general framework for static cost analysis of parallel logic programs
Author/s:
  • Klemen, Maximiliano
  • López García, Pedro
  • Gallagher, John P.
  • Morales Caballero, José Francisco
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 29th International Symposium on Logic-Based Program Synthesis and Transformation ( LOPSTR 2019)
Event Dates: 8-10 Oct 2019
Event Location: Oporto, Portugal
Title of Book: Logic-Based Program Synthesis and Transformation
Date: 2019
ISBN: 978-3-030-45259-9
Volume: 12042
Subjects:
Freetext Keywords: Resource usage analysis; Parallelism; Static analysis; Complexity analysis; (Constraint) Logic programming; Prolog
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (999kB) | Preview

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 AndParallelism, 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.

Funding Projects

TypeCodeAcronymLeaderTitle
Government of SpainTIN2015-67522-C3-1-RTRACESFundación IMDEA SoftwareTecnologías y herramientas para el desarrollo de software consciente de los recursos, correcto y eficiente (IMDEA)
Madrid Regional GovernmentP2018/TCS-4339BLOQUES-CMUnspecifiedContratos inteligentes y blockchains escalables y seguros mediante verificación y análisis

More information

Item ID: 62514
DC Identifier: http://oa.upm.es/62514/
OAI Identifier: oai:oa.upm.es:62514
DOI: 10.1007/978-3-030-45260-5_2
Official URL: https://link.springer.com/content/pdf/10.1007%2F978-3-030-45260-5_2.pdf
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 27 Apr 2020 15:08
Last Modified: 29 Apr 2020 09:54
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM