Relative roles of instruction count and cycles per instruction in WCET estimation

ABSTRACT

Most of the existing WCET estimation methods directly estimate execution time, ET, in cycles. We propose to study ET as a product of two factors, ET = IC * CPI, where IC is instruction count and CPI is cycles per instruction. Considering directly the estimation of ET may lead to a highly pessimistic estimate since implicitly these methods may be using worst case IC and worst case CPI. We hypothesize that there exists a functional relationship between CPI and IC such that CPI=f(IC). This is ascertained by computing the covariance matrix and studying the scatter plots of CPI versus IC. IC and CPI values are obtained by running benchmarks with a large number of inputs using the cycle accurate architectural simulator, Simplescalar on two different architectures. It is shown that the benchmarks can be grouped into different classes based on the CPI versus IC relationship. For some benchmarks like FFT, FIR etc., both IC and CPI are almost a constant irrespective of the input. There are other benchmarks that exhibit a direct or an inverse relationship between CPI and IC. In such a case, one can predict CPI for a given IC as CPI=f(IC). We derive the theoretical worst case IC for a program, denoted as SWIC, using integer linear programming(ILP) and estimate WCET as SWIC*f(SWIC). However, if CPI decreases sharply with IC then measured maximum cycles is observed to be a better estimate. For certain other benchmarks, it is observed that the CPI versus IC relationship is either random or CPI remains constant with varying IC. In such cases, WCET is estimated as the product of SWIC and measured maximum CPI. It is observed that use of the proposed method results in tighter WCET estimates than Chronos, a static WCET analyzer, for most benchmarks for the two architectures considered in this paper.

References

1. "http://www.comp.nus.edu.sg/~rpembed/chronos/ download.html".
2. "http://www.eecs.umich.edu/mibench".
3. "http://www.mrtc.mdh.se/projects/wcet".
4. A. Colin et al. Experimental evaluation of code properties for WCET analysis. In RTSS, pages 190-199, 2008.
5. A. Dupuy et al. An empirical evaluation of the mc/dc coverage criterion on the hete-2 satellite software. In DASC, 2000.
6. G. Bernat et al. pWCET: a tool for probabilistic worst case execution time analysis of real-time systems. In Technical Report YCS-2003-353, Univ. of York, UK.
7. J. Hansen et al. Statistical based WCET estimation and validation. In ECRTS, pages 123-133, 2009.
8. M. Zolda et al. Towards adaptable control flow segmentation for measurement-based execution time analysis. In RTNS, 2009.
9. Matteo Corti et al. Approximation of worst-case execution time for preemptive multitasking systems. In LCTES, pages 178-198, 2000.
10. P. Keim et al. Extending the path analysis technique to obtain a soft WCET. In ECRTS, pages 134-142, 2009.
11. R. Wilhelm et al. The worst-case execution time problem- overview of methods and survey of tools. ACM Trans. Embedded. Comp. Syst., 7(3):36-53, April 2008.
12. S. B?unte et al. A benchmarking suite for measurement based WCET analysis. In ICSTW, pages 353-356, 2008.
13. V. Suhendra et al. Efficient detection and exploitation of infeasible paths for software timing analysis. In DAC, pages 358-363, 2006.

Index Terms

• Software and its engineering