Skip to content

Research at St Andrews

Towards Compositional Worst-Case Execution Time Analysis for Hume Programs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In order to safely construct time-critical systems, it is necessary to ensure that responses are produced in accordance with the required time deadlines. This requires us to determine safe upper bounds on the worst-case execution time (WCET) for each primitive action, and then to combine these WCETs to determine overall WCETs for each response.
Our overall objective is to perform WCET analysis for reactive, hard real-time programs written in the very high-level language Hume, which combines purely functional expressions into a network of reactive, asynchronous “boxes”. The WCET analysis for each box is per- formed using an automatic amortised cost analysis, based on the Hume operational semantics. This analysis generates a set of constraints that can be solved using standard linear program- ming techniques. This paper considers how to construct a WCET analysis for a network of compositions of Hume boxes from the WCETs for each individual box. The main novel contri- bution of this paper is the treatment of abstract program values. In particular, we deal with the constraints that are induced by dynamic changes to program values, and with repetitive execution of box compositions. In order to increase the precision of our analysis, we distinguish between several different situations in which boxes may be used. Each situation is expressed in terms of abstract input values and assigned an independent WCET. In contrast to most other work on WCET analysis, the solutions that we obtain from our analysis provide a function for the WCET in terms of abstract program values.
Close

Details

Original languageEnglish
Title of host publicationProceedings of the ERCIM/DECOS Workshop
PublisherERCIM DECOS Workshop
Pages1-13
Number of pages13
StatePublished - 2008
EventERCIM/DECOS-Interest Group (DIG)/COOPERS Workshop 2008 on Dependable Embedded Systems - Newcastle, United Kingdom
Duration: 25 Sep 200825 Sep 2008

Conference

ConferenceERCIM/DECOS-Interest Group (DIG)/COOPERS Workshop 2008 on Dependable Embedded Systems
CountryUnited Kingdom
CityNewcastle
Period25/09/0825/09/08

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically deriving cost models for structured parallel processes using hylomorphisms

    Castro, D., Hammond, K., Sarkar, S. & Alguwaifli, Y. Feb 2018 In : Future Generation Computer Systems. 79, Part 2, p. 653-668

    Research output: Contribution to journalArticle

  2. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V. Feb 2018 In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  3. Proof-relevant Horn clauses for dependent type inference and term synthesis

    Farka, F., Komendantskya, E. & Hammond, K. 2018 In : Theory and Practice of Logic Programming. 18, 3-4, p. 484-501

    Research output: Contribution to journalArticle

  4. Type-based cost analysis for lazy functional languages

    Jost, S., Vasconcelos, P., Florido, M. & Hammond, K. Jun 2017 In : Journal of Automated Reasoning. 59, 1, p. 87-120 34 p.

    Research output: Contribution to journalArticle

ID: 5089934