skip to main content
10.1145/2228360.2228434acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

WCET-centric partial instruction cache locking

Published:03 June 2012Publication History

ABSTRACT

Caches play an important role in embedded systems by bridging the performance gap between high speed processors and slow memory. At the same time, caches introduce imprecision in Worst-case Execution Time (WCET) estimation due to unpredictable access latencies. Modern embedded processors often include cache locking mechanism for better timing predictability. As the cache contents are statically known, memory access latencies are predictable, leading to precise WCET estimate. Moreover, by carefully selecting the memory blocks to be locked, WCET estimate can be reduced compared to cache modeling without locking. Existing static instruction cache locking techniques strive to lock the entire cache to minimize the WCET. We observe that such aggressive locking mechanisms may have negative impact on the overall WCET as some memory blocks with predictable access behavior get excluded from the cache. We introduce a partial cache locking mechanism that has the flexibility to lock only a fraction of the cache. We judiciously select the memory blocks for locking through accurate cache modeling that determines the impact of the decision on the program WCET. Our synergistic cache modeling and locking mechanism achieves substantial reduction in WCET for a large number of embedded benchmark applications.

References

  1. A. Arnaud and I. Puaut. Dynamic instruction cache locking in hard real-time systems. In RTNS, 2006.Google ScholarGoogle Scholar
  2. B. Buck and J. K. Hollingsworth. An API for runtime code patching. Int. J. High Perform. Comput. Appl., 14(4), 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. D. Burger and T. M. Austin. The simplescalar tool set, version 2.0. SIGARCH Comput. Archit. News, 25(3), 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. A. M. Campoy, I. Puaut, A. P. Ivars, and J. V. B. Mataix. Cache contents selection for statically-locked instruction caches: An algorithm comparison. In ECRTS, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. H. Falk and J. C. Kleinsorge. Optimal static WCET-aware scratchpad allocation of program code. In DAC, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. H. Falk, S. Plazar, and H. Theiling. Compile-time decided instruction cache locking using worst-case execution paths. In CODES+ISSS, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. C. Guillon, F. Rastello, T. Bidault, and F. Bouchez. Procedure placement using temporal-ordering information: Dealing with code size expansion. J. Embedded Comput., 1(4), 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. J. Gustafsson, A. Betts, A. Ermedahl, and B. Lisper. The Mälardalen WCET benchmarks -- past, present and future. In WCET, 2010.Google ScholarGoogle Scholar
  9. X. Li, Y. Liang, T. Mitra, and A. Roychoudury. Chronos: A timing analyzer for embedded software. Science of Computer Programming, 69(1--3), 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. Y.-T. S. Li, S. Malik, and A. Wolfe. Cache modeling for real-time software: beyond direct mapped instruction caches. In RTSS, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Y. Liang and T. Mitra. Cache modeling in probabilistic execution time analysis. In DAC, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Y. Liang and T. Mitra. Improved procedure placement for set associative caches. In CASES, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Y. Liang and T. Mitra. Instruction cache locking using temporal reuse profile. In DAC, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. T. Liu, M. Li, and C. J. Xue. Minimizing WCET for real-time embedded systems via static instruction cache locking. In RTAS, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. F. Martin, M. Alt, R. Wilhelm, and C. Ferdinand. Analysis of loops. In CC, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. I. Puaut and D. Decotigny. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In RTSS, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. V. Suhendra and T. Mitra. Exploring locking & partitioning for predictable shared caches on multi-cores. In DAC, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. V. Suhendra, T. Mitra, A. Roychoudhury, and T. Chen. WCET centric data allocation to scratchpad memory. In RTSS, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. H. Theiling, C. Ferdinand, and R. Wilhelm. Fast and precise WCET prediction by separated cache and path analyses. Real-Time Syst., 18(2/3), 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. X. Vera, B. Lisper, and J. Xue. Data cache locking for higher program predictability. SIGMETRICS Perform. Eval. Rev., 31(1), 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. WCET-centric partial instruction cache locking

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        DAC '12: Proceedings of the 49th Annual Design Automation Conference
        June 2012
        1357 pages
        ISBN:9781450311991
        DOI:10.1145/2228360

        Copyright © 2012 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 3 June 2012

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate1,770of5,499submissions,32%

        Upcoming Conference

        DAC '24
        61st ACM/IEEE Design Automation Conference
        June 23 - 27, 2024
        San Francisco , CA , USA

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader