TU Darmstadt / ULB / TUbiblio

Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations

Flores-Montoya, Antonio (2016):
Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations.
[Report]

Abstract

Resource analysis aims at statically obtaining bounds on the resource consumption of programs in terms of input parameters. A well known approach to resource analysis is based on transforming the target program into a set of cost relations, then solving these into a closed-form bound. In this paper we develop a new analysis for computing upper and lower cost bounds of programs expressed as cost relations. The analysis is compositional : it computes the cost of each loop or function separately and composes the obtained expressions to obtain the total cost. Despite being modular, the analysis can obtain precise upper and lower bounds of programs with amortized cost. The key is to obtain bounds that depend on the values of the variables at the beginning and at the end of each program part. In addition we use a novel cost representation called cost structure. It allows to reduce the inference of complex polynomial expressions to a set of linear problems that can be solved efficiently. We implemented our method and performed an extensive experimental evaluation that demonstrates its power.

Item Type: Report
Erschienen: 2016
Creators: Flores-Montoya, Antonio
Title: Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations
Language: German
Abstract:

Resource analysis aims at statically obtaining bounds on the resource consumption of programs in terms of input parameters. A well known approach to resource analysis is based on transforming the target program into a set of cost relations, then solving these into a closed-form bound. In this paper we develop a new analysis for computing upper and lower cost bounds of programs expressed as cost relations. The analysis is compositional : it computes the cost of each loop or function separately and composes the obtained expressions to obtain the total cost. Despite being modular, the analysis can obtain precise upper and lower bounds of programs with amortized cost. The key is to obtain bounds that depend on the values of the variables at the beginning and at the end of each program part. In addition we use a novel cost representation called cost structure. It allows to reduce the inference of complex polynomial expressions to a set of linear problems that can be solved efficiently. We implemented our method and performed an extensive experimental evaluation that demonstrates its power.

Uncontrolled Keywords: Cost analysis, Cost relations, Amortized cost, Lower bounds
Divisions: Zentrale Einrichtungen > University and State Library Darmstadt (ULB)
Zentrale Einrichtungen
Date Deposited: 31 Dec 2016 10:40
Identification Number: TUD-CS-2016-1436
Related URLs:
Export:

Optionen (nur für Redakteure)

View Item View Item