Timing Analysis of Parallel Software Applications for Multi-core Embedded Systems
Abstract
Real-Time Embedded Systems (RTES) must be verified for their timing correctness where knowledge about the Worst-Case Execution Time (WCET) is the building block of such verification. Traditionally, research on the WCET analysis of RTES assumes sequential code running on single-core platforms. However, as computation is steadily moving towards using a combination of parallel programming and multi-core hardware, new challenges in timing analysis, and especially in WCET analysis need to be addressed. Towards this direction, this paper presents the Timing Analysis tool for Parallel Embedded Software (TAPES). The proposed tool allows the WCET estimation of parallel applications running on multi-core hardware through a hybrid measurement-based analysis method, that combines the program flow and timing information into an Integer-Linear Programming problem to estimate the WCET. In addition, the TAPES tool allows the measurement of the longest end-to-end execution time by capturing the timing properties of the parallel executing threads using time-stamped execution traces of the program. The applicability of the proposed tool is demonstrated through the timing analysis of an embedded parallel benchmark suite – the ParMiBench. The results showed that the calculated WCET estimates have significantly less over-approximation compared to the measured WCET estimates. The comparison of the calculated and measured WCET estimates showed modest over-estimates.References
[1] I. Bate, D. Kazakov, New directions in worst-case execution time analysis, in: IEEE World Congress on Computational Intelligence, IEEE, 2008, pp. 3545–3552.
[2] N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, et al., The gem5 simulator, ACM SIGARCH Computer Architecture News 39 (2) (2011) 1–7.
[3] D. Burger, T. M. Austin, The simplescalar tool set, version 2.0, ACM SIGARCH Computer Architecture News 25 (3) (1997) 13–25.
[4] J. Engblom, Analysis of the execution time unpredictability caused by dynamic branch prediction, in: Real-Time and Embedded Technology and Applications Symposium, 2003. Proceedings. The 9th IEEE, IEEE, 2003, pp. 152–159.
[5] J. Gustafsson, A. Ermedahl, Merging techniques for faster derivation of wcet flow information using abstract execution., in: Proceedings of the 8th International Workshop on Worst-Case Execution Time (WCET) Analysis, July, 2008, pp. 79–89.
[6] J. Gustafsson, A. Betts, A. Ermedahl, B. Lisper, The mälardalen wcet benchmarks: Past, present and future, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[7] A. Gustavsson, A. Ermedahl, B. Lisper, P. Pettersson, Towards WCET analysis of multicore architectures using UPPAAL, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[8] A. Gustavsson, Worst-case execution time analysis of parallel systems, in: Proc. Real Time in Sweden (RTiS2011).
[9] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, R. B. Brown, Mibench: A free, commercially representative embedded benchmark suite, in: IEEE International Workshop on Workload Characterization, IEEE, 2001, pp. 3–14.
[10] C. Healy, M. Sjodin, V. Rustagi, D. Whalley, Bounding loop iterations for timing analysis, in: Proceedings of Fourth IEEE Symposium on Real-Time Technology and Applications, IEEE, 1998, pp. 12–21.
[11] C. A. Healy, R. D. Arnold, F. Mueller, D. B. Whalley, M. G. Harmon, Bounding pipeline and instruction cache performance, Computers, IEEE Transactions on 48 (1) (1999) 53–70.
[12] D. Kästner, M. Schlickling, M. Pister, C. Cullmann, G. Gebhard, R. Heckmann, C. Ferdinand, Meeting real-time requirements with multi-core processors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7613 LNCS (2012) 117–131.
[13] D. Kebbal, Automatic flow analysis using symbolic execution and path enumeration, in: IEEE International Conference on Parallel Processing, IEEE, 2006, pp. 8–pp.
[14] Y.-T. S. Li, S. Malik, Performance analysis of embedded software using implicit path enumeration, in: ACM SIGPLAN Notices, Vol. 30, ACM, 1995, pp. 88–98.
[15] Y.-T. S. Li, S. Malik, A. Wolfe, Performance estimation of embedded software with instruction cache modeling, in: Computer-Aided Design. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on, IEEE, 1995, pp. 380–387.
[16] X. Li, A. Roychoudhury, T. Mitra, Modeling out-of-order processors for software timing analysis, in: Proceedings of 25th IEEE International Symposium on Real-Time Systems, IEEE, 2004, pp. 92–103.
[17] S. M. Z. Iqbal, Y. Liang, H. Grahn, Parmibench-an open-source benchmark for embedded multiprocessor systems, Computer Architecture Letters 9 (2) (2010) 45–48.
[18] Y. Liang, H. Ding, T. Mitra, A. Roychoudhury, Y. Li, V. Suhendra, Timing analysis of concurrent programs running on shared cache multi-cores, Real-Time Systems 48 (6) (2012) 638–680.
[19] B. Lisper, A. Ermedahl, D. Schreiner, J. Knoop, P. Gliwa, Practical experiences of applying source-level wcet flow analysis on industrial code, Leveraging Applications of Formal Methods, Verification, and Validation (2010) 449–463.
[20] D. Lo, G. E. Suh, Worst-case execution time analysis for parallel run-time monitoring, in: Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE, IEEE, 2012, pp. 421–429.
[21] A. Marref, Predicated worst-case execution-time analysis, Ph.D. dissertation, York, UK, 2009.
[22] H. Ozaktas, C. Rochange, P. Sainrat, Automatic wcet analysis of real-time parallel applications, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 30, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.
[23] C. Park, A. C. Shaw, Experiments with a program timing tool based on source-level timing schema, in: Real-Time Systems Symposium, 1990. Proceedings., 11th, IEEE, 1990, pp. 72–81.
[24] D. Potop-Butucaru, I. Puaut, Integrated worst-case response time evaluation of multicore non-preemptive applications , in: Research Report RR-8234. INRIA, 2013. URL ttps://hal.inria.fr/hal-00787931/document
[25] C. Rochange, A. Bonenfant, P. Sainrat, M. Gerdes, J. Wolf, T. Ungerer, Z. Petrov, F. Mikulu, Wcet analysis of a parallel 3d multigrid solver executed on the merasa multi-core, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[26] H. Theiling, C. Ferdinand, R. Wilhelm, Fast and precise wcet prediction by separated cache and path analyses, Real-Time Systems 18 (2-3) (2000) 157–179.
[27] T. Ungerer, F. Cazorla, H. Casse, S. Uhrig, I. Guliashvili, M. Houston, F. Kluge, S. Metzlaff, J. Mische, P. Sainrat, et al., Merasa: Multicore execution of hard real-time applications supporting analyzability, IEEE Micro (5) (2010) 66–75.
[28] R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, et al., The worst-case execution-time problem – overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS) 7 (3) (2008) 36.
[29] L. Wu, W. Zhang, A model checking based approach to bounding worst-case execution time for multicore processors, ACM Transactions on Embedded Computing Systems (TECS) 11 (S2) (2012) 56.
[2] N. Binkert, B. Beckmann, G. Black, S. K. Reinhardt, A. Saidi, A. Basu, J. Hestness, D. R. Hower, T. Krishna, S. Sardashti, et al., The gem5 simulator, ACM SIGARCH Computer Architecture News 39 (2) (2011) 1–7.
[3] D. Burger, T. M. Austin, The simplescalar tool set, version 2.0, ACM SIGARCH Computer Architecture News 25 (3) (1997) 13–25.
[4] J. Engblom, Analysis of the execution time unpredictability caused by dynamic branch prediction, in: Real-Time and Embedded Technology and Applications Symposium, 2003. Proceedings. The 9th IEEE, IEEE, 2003, pp. 152–159.
[5] J. Gustafsson, A. Ermedahl, Merging techniques for faster derivation of wcet flow information using abstract execution., in: Proceedings of the 8th International Workshop on Worst-Case Execution Time (WCET) Analysis, July, 2008, pp. 79–89.
[6] J. Gustafsson, A. Betts, A. Ermedahl, B. Lisper, The mälardalen wcet benchmarks: Past, present and future, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[7] A. Gustavsson, A. Ermedahl, B. Lisper, P. Pettersson, Towards WCET analysis of multicore architectures using UPPAAL, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[8] A. Gustavsson, Worst-case execution time analysis of parallel systems, in: Proc. Real Time in Sweden (RTiS2011).
[9] M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, R. B. Brown, Mibench: A free, commercially representative embedded benchmark suite, in: IEEE International Workshop on Workload Characterization, IEEE, 2001, pp. 3–14.
[10] C. Healy, M. Sjodin, V. Rustagi, D. Whalley, Bounding loop iterations for timing analysis, in: Proceedings of Fourth IEEE Symposium on Real-Time Technology and Applications, IEEE, 1998, pp. 12–21.
[11] C. A. Healy, R. D. Arnold, F. Mueller, D. B. Whalley, M. G. Harmon, Bounding pipeline and instruction cache performance, Computers, IEEE Transactions on 48 (1) (1999) 53–70.
[12] D. Kästner, M. Schlickling, M. Pister, C. Cullmann, G. Gebhard, R. Heckmann, C. Ferdinand, Meeting real-time requirements with multi-core processors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7613 LNCS (2012) 117–131.
[13] D. Kebbal, Automatic flow analysis using symbolic execution and path enumeration, in: IEEE International Conference on Parallel Processing, IEEE, 2006, pp. 8–pp.
[14] Y.-T. S. Li, S. Malik, Performance analysis of embedded software using implicit path enumeration, in: ACM SIGPLAN Notices, Vol. 30, ACM, 1995, pp. 88–98.
[15] Y.-T. S. Li, S. Malik, A. Wolfe, Performance estimation of embedded software with instruction cache modeling, in: Computer-Aided Design. ICCAD-95. Digest of Technical Papers., 1995 IEEE/ACM International Conference on, IEEE, 1995, pp. 380–387.
[16] X. Li, A. Roychoudhury, T. Mitra, Modeling out-of-order processors for software timing analysis, in: Proceedings of 25th IEEE International Symposium on Real-Time Systems, IEEE, 2004, pp. 92–103.
[17] S. M. Z. Iqbal, Y. Liang, H. Grahn, Parmibench-an open-source benchmark for embedded multiprocessor systems, Computer Architecture Letters 9 (2) (2010) 45–48.
[18] Y. Liang, H. Ding, T. Mitra, A. Roychoudhury, Y. Li, V. Suhendra, Timing analysis of concurrent programs running on shared cache multi-cores, Real-Time Systems 48 (6) (2012) 638–680.
[19] B. Lisper, A. Ermedahl, D. Schreiner, J. Knoop, P. Gliwa, Practical experiences of applying source-level wcet flow analysis on industrial code, Leveraging Applications of Formal Methods, Verification, and Validation (2010) 449–463.
[20] D. Lo, G. E. Suh, Worst-case execution time analysis for parallel run-time monitoring, in: Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE, IEEE, 2012, pp. 421–429.
[21] A. Marref, Predicated worst-case execution-time analysis, Ph.D. dissertation, York, UK, 2009.
[22] H. Ozaktas, C. Rochange, P. Sainrat, Automatic wcet analysis of real-time parallel applications, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 30, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013.
[23] C. Park, A. C. Shaw, Experiments with a program timing tool based on source-level timing schema, in: Real-Time Systems Symposium, 1990. Proceedings., 11th, IEEE, 1990, pp. 72–81.
[24] D. Potop-Butucaru, I. Puaut, Integrated worst-case response time evaluation of multicore non-preemptive applications , in: Research Report RR-8234. INRIA, 2013. URL ttps://hal.inria.fr/hal-00787931/document
[25] C. Rochange, A. Bonenfant, P. Sainrat, M. Gerdes, J. Wolf, T. Ungerer, Z. Petrov, F. Mikulu, Wcet analysis of a parallel 3d multigrid solver executed on the merasa multi-core, in: International Workshop on Worst-Case Execution Time (WCET) Analysis, Vol. 15, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2010.
[26] H. Theiling, C. Ferdinand, R. Wilhelm, Fast and precise wcet prediction by separated cache and path analyses, Real-Time Systems 18 (2-3) (2000) 157–179.
[27] T. Ungerer, F. Cazorla, H. Casse, S. Uhrig, I. Guliashvili, M. Houston, F. Kluge, S. Metzlaff, J. Mische, P. Sainrat, et al., Merasa: Multicore execution of hard real-time applications supporting analyzability, IEEE Micro (5) (2010) 66–75.
[28] R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, et al., The worst-case execution-time problem – overview of methods and survey of tools, ACM Transactions on Embedded Computing Systems (TECS) 7 (3) (2008) 36.
[29] L. Wu, W. Zhang, A model checking based approach to bounding worst-case execution time for multicore processors, ACM Transactions on Embedded Computing Systems (TECS) 11 (S2) (2012) 56.
Downloads
Published
2018-03-07
Issue
Section
Electrical Engineering and Computer Science
