Call for Paper - October 2019 Edition
IJCA solicits original research papers for the October 2019 Edition. Last date of manuscript submission is September 20, 2019. Read More

Survey : Various Methods for WCET Estimate Calculation

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Manjiri K. Kulkarni, J.S. Umale
10.5120/ijca2016908152

Manjiri K Kulkarni and J S Umale. Article: Survey : Various Methods for WCET Estimate Calculation. International Journal of Computer Applications 136(8):14-17, February 2016. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Manjiri K. Kulkarni and J.S. Umale},
	title = {Article: Survey : Various Methods for WCET Estimate Calculation},
	journal = {International Journal of Computer Applications},
	year = {2016},
	volume = {136},
	number = {8},
	pages = {14-17},
	month = {February},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

The design of a real-time system revolves heavily around a model known as a task schedule, which allots computational resources to executing tasks, i.e. programs. Many different scheduling algorithms have been invented, all of which depend on a set of temporal properties relevant to each task. One such property is the Worst Case Execution Time (WCET), intuitively described as the longest possible execution time. It is required to determine variation in execution times. If the variation is bounded then the system has time predictable behavior. Otherwise, we cannot provide any guaranties for the worst case execution time and the architecture is time unpredictable. Embedded controllers are expected to finish their tasks reliably within time bounds. Task scheduling must be performed essential: upper bound on the execution times of all tasks statically known Commonly called the Worst-Case Execution Time (WCET). To use the GPUs in real time systems it is required to have time predictable behavior. However, it is hard to give an estimation of the WCET of a GPU program.

In this paper , we focused on comparative analysis of various WCET estimate techniques with their results evaluations as well as observations.

References

  1. P. Puschner and A. Schedl, “Computing Maximum Task Execution Times - A Graph-Based Approach,” Real-Time Systems, vol. 13, no. 1, pp. 67–91, 1997.
  2. J. Wegener and M. Grochtmann, “Verifying timing constraints of realtime systems by means of evolutionary testing,” Real-Time Systems, vol. 15, no. 3, pp. 275–298, 1998.
  3. A. Colin and I. Puaut. A modular and retargetable framework for tree-based WCET analysis. In Proceedings of the 13th Euromicro Conference on Real-Time Systems, pages 37–44, Delft, Netherlands, June 13–15 2001.
  4. J. L. Diaz, D. F. Garcia, K. Kim, C. Lee, L. Lo Bello, J. M. Lopez, S. L. Min, and O. Mirabella. Stochastic analysis of periodic real-time systems. In Proceedings of the 23rd Real Time Systems Symposium RTSS 2002, Austin, Texas, USA, Dec. 3–5 2002.
  5. Guillem Bernat Antoine Colin Stefan M. Petters, “WCET Analysis of Probabilistic Hard Real-Time Systems”, Real-Time Systems Research Group Department of Computer Science University of York, UK, 2002.
  6. R. Arnold, F. Mu¨ller, D. Whalley, and M. Harmon. Bounding worst–case instruction cache performance. In Proc. of the IEEE Real–Time Systems Symposium (RTSS’94). IEEE Computer Society Press, Dec. 1994. [3] I. Berger. Can you trust your car? IEEE Spectrum, 39:40–45, Apr. 2002.
  7. A. Colin and S. M. Petters, “Experimental Evaluation of Code Properties for WCET Analysis,” in RTSS, 2003.
  8. A. Aho, R. Sethi, M. S. Lam, and J. Ullman, Compilers: Principles, Techniques and Tools, 2nd ed. Addison-Wesley, 2006.
  9. A. Betts, “Hybrid Measurement-Based WCET Analysis using Instrumentation Point Graphs,” Ph.D. dissertation, University of York, November 2008.
  10. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenstr¨om. The worst-case execution time problem — overview of methods and survey of tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3):1–53, 2008.
  11. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenstro¨m, “The Worst-Case Execution-Time Problem–Overview of Methods and Survey of Tools,” ACM Transations on Embedded Computing Systems, vol. 7, no. 3, pp. 1–53, 2008.
  12. Andreas Ermedahl, Johan Fredriksson, Jan Gustafsson, “Deriving the Worst-Case Execution Time Input Values”, 21st Euromicro Conference on Real-Time Systems, 2009.
  13. Ma¨lardalen University WCET project homepage, http://www.mrtc.mdh.se/projects/wcet, May 2010.
  14. Adam Betts, Amine Marref, “WCET Analysis of Component-Based Systems using Timing Traces”, 16th IEEE International Conference on Engineering of Complex Computer Systems, 2011.
  15. Adam Betts and Alastair Donaldson, ”Estimating the WCET of GPU-Accelerated Applications using Hybrid Analysis”, 25th Euromicro Conference on Real-Time Systems, 2013.

Keywords

WCET, IPG, ETP, Static Analysis, Hybrid Analysis, GPU.