Skip to main content
Erschienen in: Real-Time Systems 6/2012

01.11.2012

Timing analysis of concurrent programs running on shared cache multi-cores

verfasst von: Yun Liang, Huping Ding, Tulika Mitra, Abhik Roychoudhury, Yan Li, Vivy Suhendra

Erschienen in: Real-Time Systems | Ausgabe 6/2012

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Memory accesses form an important source of timing unpredictability. Timing analysis of real-time embedded software thus requires bounding the time for memory accesses. Multiprocessing, a popular approach for performance enhancement, opens up the opportunity for concurrent execution. However due to contention for any shared memory by different processing cores, memory access behavior becomes more unpredictable, and hence harder to analyze. In this paper, we develop a timing analysis method for concurrent software running on multi-cores with a shared instruction cache. Communication across tasks is by message passing. Our method progressively improves the lifetime estimates of tasks that execute concurrently on multiple cores, in order to estimate potential conflicts in the shared cache. Possible conflicts arising from overlapping task lifetimes are accounted for in the hit-miss classification of accesses to the shared cache, to provide safe execution time bounds. We show that our method produces lower worst-case response time (WCRT) estimates than existing shared-cache analysis on a real-world embedded application. Furthermore, we also exploit instruction cache locking to improve WCRT. By locking some beneficial memory blocks into L1 cache, the WCET of the tasks and L2 cache conflicts are reduced, resulting in better WCRT. Experiments demonstrate that significant WCRT reduction is achieved through cache locking.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Alt M, Ferdinand C, Martin F, Wilhelm R (1996) Cache behavior prediction by abstract interpretation. In: Lecture notes in computer science, vol 1145, pp 52–66 Alt M, Ferdinand C, Martin F, Wilhelm R (1996) Cache behavior prediction by abstract interpretation. In: Lecture notes in computer science, vol 1145, pp 52–66
Zurück zum Zitat Alur R, Yannakakis M (1999) Model checking message sequence charts. In: Proceedings of the international conference on concurrency theory Alur R, Yannakakis M (1999) Model checking message sequence charts. In: Proceedings of the international conference on concurrency theory
Zurück zum Zitat Austin T, Larson E, Ernst D (2002) SimpleScalar: an infrastructure for computer system modeling. IEEE Comput 35(2) Austin T, Larson E, Ernst D (2002) SimpleScalar: an infrastructure for computer system modeling. IEEE Comput 35(2)
Zurück zum Zitat Baldawa S (2007) CMPSIM: A flexible multiprocessor simulation environment. Master’s thesis, The University of Texas at Dallas Baldawa S (2007) CMPSIM: A flexible multiprocessor simulation environment. Master’s thesis, The University of Texas at Dallas
Zurück zum Zitat Campoy AM et al. (2005) Cache contents selection for statically-locked instruction caches: an algorithm comparison. In: ECRTS’05: proceedings of the 17th Euromicro conference on real-time systems Campoy AM et al. (2005) Cache contents selection for statically-locked instruction caches: an algorithm comparison. In: ECRTS’05: proceedings of the 17th Euromicro conference on real-time systems
Zurück zum Zitat Chattopadhyay S, Roychoudhury A (2011) Static bus schedule aware scratchpad allocation in multiprocessors. In: Proceedings of the 2011 SIGPLAN/SIGBED conference on languages, compilers and tools for embedded systems, LCTES’11, pp 11–20 CrossRef Chattopadhyay S, Roychoudhury A (2011) Static bus schedule aware scratchpad allocation in multiprocessors. In: Proceedings of the 2011 SIGPLAN/SIGBED conference on languages, compilers and tools for embedded systems, LCTES’11, pp 11–20 CrossRef
Zurück zum Zitat Chattopadhyay S, Roychoudhury A, Mitra T (2010) Modeling shared cache and bus in multi-cores for timing analysis. In: Proceedings of the 13th international workshop on software & compilers for embedded systems, SCOPES’10, pp 6:1–6:10 Chattopadhyay S, Roychoudhury A, Mitra T (2010) Modeling shared cache and bus in multi-cores for timing analysis. In: Proceedings of the 13th international workshop on software & compilers for embedded systems, SCOPES’10, pp 6:1–6:10
Zurück zum Zitat Coutinho LMN, Mendes JLD, Martins CAPS (2006) MSCSim—multilevel and split cache simulator. In: 36th annual frontiers in education conference Coutinho LMN, Mendes JLD, Martins CAPS (2006) MSCSim—multilevel and split cache simulator. In: 36th annual frontiers in education conference
Zurück zum Zitat Falk H, Plazar S, Theiling H (2007) Compile-time decided instruction cache locking using worst-case execution paths. In: CODES+ISSS’07: proceedings of the 5th IEEE/ACM international conference on hardware/software codesign and system synthesis Falk H, Plazar S, Theiling H (2007) Compile-time decided instruction cache locking using worst-case execution paths. In: CODES+ISSS’07: proceedings of the 5th IEEE/ACM international conference on hardware/software codesign and system synthesis
Zurück zum Zitat Gustavsson A, Ermedahl A, Lisper B, Pettersson P (2010) Towards wcet analysis of multicaore architecures using uppaal. In: Proceedings of 10th international workshop on Worst-Case Execution-Time analysis, WCET’10 Gustavsson A, Ermedahl A, Lisper B, Pettersson P (2010) Towards wcet analysis of multicaore architecures using uppaal. In: Proceedings of 10th international workshop on Worst-Case Execution-Time analysis, WCET’10
Zurück zum Zitat Hardy D, Puaut I (2008) WCET analysis of multi-level non-inclusive set-associative instruction caches. In: Proceedings of the real-time systems symposium Hardy D, Puaut I (2008) WCET analysis of multi-level non-inclusive set-associative instruction caches. In: Proceedings of the real-time systems symposium
Zurück zum Zitat Hardy D, Piquet T, Puaut I (2009) Using bypass to tighten wcet estimates for multi-core processors with shared instruction caches. In: Proceedings of the 2009 30th IEEE real-time systems symposium, RTSS’09 Hardy D, Piquet T, Puaut I (2009) Using bypass to tighten wcet estimates for multi-core processors with shared instruction caches. In: Proceedings of the 2009 30th IEEE real-time systems symposium, RTSS’09
Zurück zum Zitat Heckmann R et al (2003) The influence of processor architecture on the design and the results of WCET tools. Proc IEEE 9(7) Heckmann R et al (2003) The influence of processor architecture on the design and the results of WCET tools. Proc IEEE 9(7)
Zurück zum Zitat ITU (1996) Message sequence charts. ITU-TS Recommendation Z.120 ITU (1996) Message sequence charts. ITU-TS Recommendation Z.120
Zurück zum Zitat Lee C-G et al. (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713 MathSciNetCrossRef Lee C-G et al. (1998) Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Trans Comput 47(6):700–713 MathSciNetCrossRef
Zurück zum Zitat Lee JW, Asanovic K (2006) METERG: measurement-based end-to-end performance estimation technique in QoS-capable multiprocessors. In: Proceedings of the IEEE real-time and embedded technology and applications symposium Lee JW, Asanovic K (2006) METERG: measurement-based end-to-end performance estimation technique in QoS-capable multiprocessors. In: Proceedings of the IEEE real-time and embedded technology and applications symposium
Zurück zum Zitat Li Y-TS, Malik S, Wolfe A (1996) Cache modeling for real-time software: beyond direct mapped instruction caches. In: Proceedings of the real-time systems symposium Li Y-TS, Malik S, Wolfe A (1996) Cache modeling for real-time software: beyond direct mapped instruction caches. In: Proceedings of the real-time systems symposium
Zurück zum Zitat Liang Y, Mitra T (2010) Instruction cache locking using temporal reuse profile. In: DAC’10: proceedings of the 47th annual design automation conference Liang Y, Mitra T (2010) Instruction cache locking using temporal reuse profile. In: DAC’10: proceedings of the 47th annual design automation conference
Zurück zum Zitat Liu T, Li M, Xue CJ (2009) Minimizing WCET for real-time embedded systems via static instruction cache locking. In: RTAS’09: proceedings of the 15th IEEE real-time and embedded technology and applications symposium Liu T, Li M, Xue CJ (2009) Minimizing WCET for real-time embedded systems via static instruction cache locking. In: RTAS’09: proceedings of the 15th IEEE real-time and embedded technology and applications symposium
Zurück zum Zitat Lundqvist T, Stenstrom P (1999) An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Syst 17(2–3) Lundqvist T, Stenstrom P (1999) An integrated path and timing analysis method based on cycle-level symbolic execution. Real-Time Syst 17(2–3)
Zurück zum Zitat Mueller F (2000) Timing analysis for instruction caches. Real-Time Syst. 18(2–3) Mueller F (2000) Timing analysis for instruction caches. Real-Time Syst. 18(2–3)
Zurück zum Zitat Negi HS, Mitra T, Roychoudhury A (2003) Accurate estimation of cache-related preemption delay. In: Proceedings of the IEEE/ACM/IFIP international conference on hardware/software codesign and system synthesis Negi HS, Mitra T, Roychoudhury A (2003) Accurate estimation of cache-related preemption delay. In: Proceedings of the IEEE/ACM/IFIP international conference on hardware/software codesign and system synthesis
Zurück zum Zitat Nemer F, Cassé H, Sainrat P, Bahsoun JP, De Michiel M (2006) Papabench: a free real-time benchmark. In: WCET’06 Nemer F, Cassé H, Sainrat P, Bahsoun JP, De Michiel M (2006) Papabench: a free real-time benchmark. In: WCET’06
Zurück zum Zitat Puaut I, Decotigny D (2002) Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In: RTSS’02: proceedings of the 23rd IEEE real-time systems symposium Puaut I, Decotigny D (2002) Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In: RTSS’02: proceedings of the 23rd IEEE real-time systems symposium
Zurück zum Zitat Puschner P, Schoeberl M (2008) On composable system timing, task timing, and WCET analysis. In: International workshop on worst-case execution time analysis Puschner P, Schoeberl M (2008) On composable system timing, task timing, and WCET analysis. In: International workshop on worst-case execution time analysis
Zurück zum Zitat Schliecker S, Negrean M, Nicolescu G, Paulin P, Ernst R (2008) Reliable performance analysis of a multicore multithreaded system-on-chip. In: Proceedings of the IEEE/ACM/IFIP international conference on hardware/software codesign and system synthesis Schliecker S, Negrean M, Nicolescu G, Paulin P, Ernst R (2008) Reliable performance analysis of a multicore multithreaded system-on-chip. In: Proceedings of the IEEE/ACM/IFIP international conference on hardware/software codesign and system synthesis
Zurück zum Zitat Staschulat J, Ernst R (2004) Multiple process execution in cache related preemption delay analysis. In: Proceedings of the 4th ACM international conference on embedded software Staschulat J, Ernst R (2004) Multiple process execution in cache related preemption delay analysis. In: Proceedings of the 4th ACM international conference on embedded software
Zurück zum Zitat Suhendra V, Mitra T, Roychoudhury A, Chen T (2006) Efficient detection and exploitation of infeasible paths for software timing analysis. In: Proceedings of the design automation conference Suhendra V, Mitra T, Roychoudhury A, Chen T (2006) Efficient detection and exploitation of infeasible paths for software timing analysis. In: Proceedings of the design automation conference
Zurück zum Zitat Tan Y, Mooney V (2005) WCRT analysis for a uniprocessor with a unified prioritized cache. In: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on languages, compilers, and tools for embedded systems Tan Y, Mooney V (2005) WCRT analysis for a uniprocessor with a unified prioritized cache. In: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on languages, compilers, and tools for embedded systems
Zurück zum Zitat Theiling H, Ferdinand C, Wilhelm R (2000) Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst 18(2/3) Theiling H, Ferdinand C, Wilhelm R (2000) Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst 18(2/3)
Zurück zum Zitat Tomiyama H, Dutt ND (2000) Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In: Proceedings of the eighth international workshop on hardware/software codesign Tomiyama H, Dutt ND (2000) Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In: Proceedings of the eighth international workshop on hardware/software codesign
Zurück zum Zitat Yan J, Zhang W (2008) WCET analysis for multi-core processors with shared L2 instruction caches. In: Proceedings of the IEEE real-time and embedded technology and applications symposium Yan J, Zhang W (2008) WCET analysis for multi-core processors with shared L2 instruction caches. In: Proceedings of the IEEE real-time and embedded technology and applications symposium
Zurück zum Zitat Zhang W, Yan J (2009) Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches. In: Proceedings of the 2009 15th IEEE international conference on embedded and real-time computing systems and applications, RTCSA’09 Zhang W, Yan J (2009) Accurately estimating worst-case execution time for multi-core processors with shared direct-mapped instruction caches. In: Proceedings of the 2009 15th IEEE international conference on embedded and real-time computing systems and applications, RTCSA’09
Metadaten
Titel
Timing analysis of concurrent programs running on shared cache multi-cores
verfasst von
Yun Liang
Huping Ding
Tulika Mitra
Abhik Roychoudhury
Yan Li
Vivy Suhendra
Publikationsdatum
01.11.2012
Verlag
Springer US
Erschienen in
Real-Time Systems / Ausgabe 6/2012
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-012-9160-2

Weitere Artikel der Ausgabe 6/2012

Real-Time Systems 6/2012 Zur Ausgabe