uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
WCET analysis with MRU caches: Challenging LRU for predictability
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
2012 (engelsk)Inngår i: Proc. 18th Real-Time and Embedded Technology and Applications Symposium, IEEE Computer Society, 2012, s. 55-64Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Most previous work in cache analysis for WCET estimation assumes a particular replacement policy called LRU. In contrast, much less work has been done for non-LRU policies, since they are generally considered to be very "unpredictable". However, most commercial processors are actually equipped with these non-LRU policies, since they are more efficient in terms of hardware cost, power consumption and thermal output, but still maintaining almost as good average-case performance as LRU. In this work, we study the analysis of MRU, a non-LRU replacement policy employed in mainstream processor architectures like Intel Nehalem. Our work shows that the predictability of MRU has been significantly underestimated before, mainly because the existing cache analysis techniques and metrics, originally designed for LRU, do not match MRU well. As our main technical contribution, we propose a new cache hit/miss classification, k-Miss, to better capture the MRU behavior, and develop formal conditions and efficient techniques to decide the k-Miss memory accesses. A remarkable feature of our analysis is that the k-Miss classifications under MRU are derived by the analysis result of the same program under LRU. Therefore, our approach inherits all the advantages in efficiency, precision and composability of the state-of-the-art LRU analysis techniques based on abstract interpretation. Experiments with benchmarks show that the estimated WCET by our proposed MRU analysis is rather close to (5% similar to 20% more than) that obtained by the state-of-the-art LRU analysis, which indicates that MRU is also a good candidate for the cache replacement policy in real-time systems.

sted, utgiver, år, opplag, sider
IEEE Computer Society, 2012. s. 55-64
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-184597DOI: 10.1109/RTAS.2012.31ISI: 000309190700006ISBN: 978-1-4673-0883-0 (tryckt)OAI: oai:DiVA.org:uu-184597DiVA, id: diva2:566829
Konferanse
RTAS 2012/Cyber-Physical Systems Week, April 16-19, Beijing, China
Prosjekter
UPMARCTilgjengelig fra: 2012-11-09 Laget: 2012-11-09 Sist oppdatert: 2014-01-23
Inngår i avhandling
1. New Techniques for Building Timing-Predictable Embedded Systems
Åpne denne publikasjonen i ny fane eller vindu >>New Techniques for Building Timing-Predictable Embedded Systems
2013 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design.

On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework.

On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem.

On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.

sted, utgiver, år, opplag, sider
Uppsala: Acta Universitatis Upsaliensis, 2013. s. 45
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1094
Emneord
Real-time systems, WCET analysis, cache analysis, abstract interpretation, multiprocessor scheduling, fixed-priority scheduling, EDF, multi-core processors, response time analysis, utilization bound, real-time calculus, scalability
HSV kategori
Forskningsprogram
Datavetenskap med inriktning mot realtidssystem
Identifikatorer
urn:nbn:se:uu:diva-209623 (URN)978-91-554-8797-3 (ISBN)
Disputas
2013-12-17, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (engelsk)
Opponent
Veileder
Prosjekter
UPMARC
Tilgjengelig fra: 2013-11-26 Laget: 2013-10-22 Sist oppdatert: 2019-02-25

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Guan, NanYi, Wang

Søk i DiVA

Av forfatter/redaktør
Guan, NanYi, Wang
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 628 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf