Flores-Montoya, Antonio (2016)
Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations.
Report, Bibliographie
Kurzbeschreibung (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.
| Typ des Eintrags: | Report |
|---|---|
| Erschienen: | 2016 |
| Autor(en): | Flores-Montoya, Antonio |
| Art des Eintrags: | Bibliographie |
| Titel: | Upper and Lower Amortized Cost Bounds of Programs Expressed as Cost Relations |
| Sprache: | Deutsch |
| Publikationsjahr: | September 2016 |
| Zugehörige Links: | |
| Kurzbeschreibung (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. |
| Freie Schlagworte: | Cost analysis, Cost relations, Amortized cost, Lower bounds |
| ID-Nummer: | TUD-CS-2016-1436 |
| Fachbereich(e)/-gebiet(e): | Zentrale Einrichtungen > Universitäts- und Landesbibliothek (ULB) Zentrale Einrichtungen |
| Hinterlegungsdatum: | 31 Dez 2016 10:40 |
| Letzte Änderung: | 30 Mai 2018 12:51 |
| PPN: | |
| Zugehörige Links: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum