Guaranteed Loop Bound Identification from Program Traces for WCET

M. Bartlett; I. Bate; D. Kazakov

doi:10.1109/RTAS.2009.29

Guaranteed Loop Bound Identification from Program Traces for WCET

M. Bartlett, I. Bate, D. Kazakov

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.

Original language	English
Title of host publication	Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
Place of Publication	LOS ALAMITOS
Publisher	IEEE Computer Society
Pages	287-294
ISBN (Print)	978-0-7695-3636-1
DOIs	https://doi.org/10.1109/RTAS.2009.29
Publication status	Published - 1 Apr 2009
Event	16th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems - San Francisco Duration: 14 Apr 2009 → 16 Apr 2009

Conference

Conference	16th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems
City	San Francisco
Period	14/04/09 → 16/04/09

Keywords

REAL-TIME SYSTEMS
EXECUTION
PATHS

Access to Document

10.1109/RTAS.2009.29

http://doi.ieeecomputersociety.org/10.1109/RTAS.2009.29

Cite this

@inproceedings{14bb2ae721894c67917892c8aa5cecf1,

title = "Guaranteed Loop Bound Identification from Program Traces for WCET",

abstract = "Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.",

keywords = "REAL-TIME SYSTEMS, EXECUTION, PATHS",

author = "M. Bartlett and I. Bate and D. Kazakov",

year = "2009",

month = apr,

day = "1",

doi = "10.1109/RTAS.2009.29",

language = "English",

isbn = "978-0-7695-3636-1",

pages = "287--294",

booktitle = "Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)",

publisher = "IEEE Computer Society",

address = "United States",

note = "16th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems ; Conference date: 14-04-2009 Through 16-04-2009",

}

Bartlett, M , Bate, I & Kazakov, D 2009, Guaranteed Loop Bound Identification from Program Traces for WCET. in Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE Computer Society, LOS ALAMITOS, pp. 287-294, 16th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems, San Francisco, 14/04/09. https://doi.org/10.1109/RTAS.2009.29

TY - GEN

T1 - Guaranteed Loop Bound Identification from Program Traces for WCET

AU - Bartlett, M.

AU - Bate, I.

AU - Kazakov, D.

PY - 2009/4/1

Y1 - 2009/4/1

N2 - Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.

AB - Static analysis can be used to determine safe estimates of Worst Case Execution Time. However, overestimation of the number of loop iterations, particularly in nested loops, can result in substantial pessimism in the overall estimate. This paper presents a method of determining exact parametric values of the number of loop iterations for a particular class of arbitrarily deeply nested loops. It is proven that values are guaranteed to be correct using information obtainable from a finite and quantifiable number of program traces. Using the results of this proof, a tool is constructed and its scalability assessed.

KW - REAL-TIME SYSTEMS

KW - EXECUTION

KW - PATHS

UR - http://www.scopus.com/inward/record.url?scp=67650245536&partnerID=8YFLogxK

U2 - 10.1109/RTAS.2009.29

DO - 10.1109/RTAS.2009.29

M3 - Conference contribution

SN - 978-0-7695-3636-1

SP - 287

EP - 294

BT - Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)

PB - IEEE Computer Society

CY - LOS ALAMITOS

T2 - 16th IEEE International Conference and Workshop on the Engineering of Computer-Based Systems

Y2 - 14 April 2009 through 16 April 2009

ER -

Guaranteed Loop Bound Identification from Program Traces for WCET

Abstract

Conference

Keywords

Access to Document

Other files and links

Using Learning to Support the Development of Embedded Systems

Cite this

Guaranteed Loop Bound Identification from Program Traces for WCET

Abstract

Conference

Keywords

Access to Document

Other files and links

Projects

Using Learning to Support the Development of Embedded Systems

Cite this