You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at http://www.ieee.org/web/publications/rights/copyrightpolicy.html)
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at http://www.acm.org/pubs/copyright_policy/)
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact webmaster@ide.mdh.se

Relative Census Analysis Supports the Census Method of WCET Analysis

Authors:

Niklas Holsti

Research group:

Programming Languages

Publication Type:

Report - MRTC

Publisher:

Mälardalen Real-Time Research Centre, Mälardalen University

ISRN:

MDH-MRTC-298/2014-1-SE

Abstract

In the "census method" of WCET analysis, the number of executions of a program loop is bounded from above by the "census", defined as the total number of possible combined values of the variables that influence loop termination. Considering only integer-valued variables, an upper bound on the census is typically found by counting the number of integer points in the volume of states generated by a relational value-analysis, such as a polyhedral analysis. Any non-linear computation of variables significant to loop termination can then introduce huge over-estimation in the census bound, since the result of the non-linear computation is unbounded in the polyhedral model. For example, a single unbounded 32-bit variable causes an over-estimation by the factor 2^32. We aim to counteract such over-estimation by computing the number of values that the unbounded variable(s) can take, for each value-combination of the other variables. This typically smaller number – the relative census – replaces the huge number of all representable values as a factor in the census bound. This report formally defines the relative census (RC) concept and studies its mathematical properties. The report also develops formulas for bounding the evolution of the RC along program execution flow, as required for static analysis tools. The report concludes with a discussion of possible forms of static analysis of RC, in particular for supporting census-based WCET analysis.

Bibtex

@techreport{Holsti3840,
author = {Niklas Holsti},
title = {Relative Census Analysis Supports the Census Method of WCET Analysis},
month = {November},
year = {2014},
publisher = {M{\"a}lardalen Real-Time Research Centre, M{\"a}lardalen University},
url = {http://www.es.mdu.se/publications/3840-}
}