uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
New Techniques for Building Timing-Predictable Embedded Systems
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2013. , 45 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1094
Keyword [en]
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
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
URN: urn:nbn:se:uu:diva-209623ISBN: 978-91-554-8797-3 (print)OAI: oai:DiVA.org:uu-209623DiVA: diva2:660045
Public defence
2013-12-17, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2013-11-26 Created: 2013-10-22 Last updated: 2014-07-21
List of papers
1. WCET analysis with MRU caches: Challenging LRU for predictability
Open this publication in new window or tab >>WCET analysis with MRU caches: Challenging LRU for predictability
2012 (English)In: Proc. 18th Real-Time and Embedded Technology and Applications Symposium, IEEE Computer Society, 2012, 55-64 p.Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
IEEE Computer Society, 2012
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-184597 (URN)10.1109/RTAS.2012.31 (DOI)000309190700006 ()978-1-4673-0883-0 (ISBN)
Conference
RTAS 2012/Cyber-Physical Systems Week, April 16-19, Beijing, China
Projects
UPMARC
Available from: 2012-11-09 Created: 2012-11-09 Last updated: 2014-01-23
2. FIFO cache analysis for WCET estimation: A quantitative approach
Open this publication in new window or tab >>FIFO cache analysis for WCET estimation: A quantitative approach
2013 (English)In: Proc. 16th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2013, 296-301 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2013
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-209547 (URN)10.7873/DATE.2013.073 (DOI)978-1-4673-5071-6 (ISBN)
Conference
DATE 2013, March 18-22, Grenoble, France
Projects
UPMARC
Note

Best Paper Award

Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2014-01-23
3. New Response Time Bounds for Fixed Priority Multiprocessor Scheduling
Open this publication in new window or tab >>New Response Time Bounds for Fixed Priority Multiprocessor Scheduling
2009 (English)In: Proc. Real-Time Systems Symposium: RTSS 2009, Piscataway, NJ: IEEE , 2009, 387-397 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2009
National Category
Computer Science
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
urn:nbn:se:uu:diva-130904 (URN)10.1109/RTSS.2009.11 (DOI)000277465500036 ()978-0-7695-3875-4 (ISBN)
Conference
IEEE Real-Time Systems Symposium (RTSS)
Projects
UPMARCCoDeR-MP
Note

Best Paper Award

Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2014-01-23
4. Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling
Open this publication in new window or tab >>Schedulability analysis for non-preemptive fixed-priority multiprocessor scheduling
Show others...
2011 (English)In: Journal of systems architecture, ISSN 1383-7621, E-ISSN 1873-6165, Vol. 57, no 5, 536-546 p.Article in journal (Refereed) Published
National Category
Computer Engineering Computer Science
Identifiers
urn:nbn:se:uu:diva-141648 (URN)10.1016/j.sysarc.2010.08.003 (DOI)000291286900005 ()
Projects
UPMARC
Available from: 2010-08-27 Created: 2011-01-12 Last updated: 2017-12-11Bibliographically approved
5. Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound
Open this publication in new window or tab >>Fixed-Priority Multiprocessor Scheduling with Liu & Layland's Utilization Bound
2010 (English)In: Proc. 16th Real-Time and Embedded Technology and Applications Symposium, Piscataway, NJ: IEEE , 2010, 165-174 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2010
National Category
Computer Engineering Computer Science
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
urn:nbn:se:uu:diva-130901 (URN)10.1109/RTAS.2010.39 (DOI)978-1-4244-6690-0 (ISBN)
Conference
RTAS 2010, April 12-15, Stockholm, Sweden
Projects
CoDeR-MPUPMARC
Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2014-01-23
6. Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
Open this publication in new window or tab >>Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
2012 (English)In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS), 2012, 261-272 p.Conference paper, Published paper (Refereed)
Abstract [en]

Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Layland utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.

Series
International Parallel and Distributed Processing Symposium IPDPS
National Category
Engineering and Technology
Identifiers
urn:nbn:se:uu:diva-184746 (URN)10.1109/IPDPS.2012.33 (DOI)000309131900024 ()978-0-7695-4675-9 (ISBN)
Conference
26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), MAY 21-25, 2012, Shanghai, PEOPLES R CHINA
Projects
UPMARC
Available from: 2012-11-14 Created: 2012-11-13 Last updated: 2014-01-23
7. Cache-aware scheduling and analysis for multicores
Open this publication in new window or tab >>Cache-aware scheduling and analysis for multicores
2009 (English)In: Proc. 9th ACM International Conference on Embedded Software, New York: ACM Press, 2009, 245-254 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
New York: ACM Press, 2009
National Category
Computer Science
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
urn:nbn:se:uu:diva-130914 (URN)10.1145/1629335.1629369 (DOI)978-1-60558-627-4 (ISBN)
Conference
9th ACM International Conference on Embedded Software
Projects
UPMARC
Available from: 2010-09-20 Created: 2010-09-17 Last updated: 2014-01-23
8. Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems
Open this publication in new window or tab >>Finitary Real-Time Calculus: Efficient Performance Analysis of Distributed Embedded Systems
2013 (English)In: Proc. Real-Time Systems Symposium: RTSS 2013, IEEE Computer Society, 2013Conference paper, Published paper (Refereed)
Abstract [en]

Real-Time Calculus (RTC) is a powerful framework to analyzereal-time performance of distributed embedded systems. However,RTC may run into serious analysis efficiency problems when appliedto systems of large scale and/or with complex timing parameter characteristics.The main reason is that many RTC operations generatecurves with periods equal to the hyper-period of the input curves.Therefore, the analysis in RTC has exponential complexity. In practisethe curve periods may explode rapidly when several componentsare serially connected, which leads to low analysis efficiency.In this work, we propose Finitary RTC to solve the above problem.Finitary RTC only maintains and operates on a limited part ofeach curve that is relevant to the final analysis results, which resultsin pseudo-polynomial computational complexity. Experiments showthat Finitary RTC can drastically improve the analysis efficiency overthe original RTC. The original RTC may take hours or even days toanalyze systems with complex timing characteristics, but FinitaryRTC typically can complete the analysis in seconds. Even for simplesystems, Finitary RTC also typically speeds up the analysis procedureby hundreds of times. While getting better efficiency, FinitaryRTC does not introduce any extra pessimism, i.e., it yields analysisresults as precise as the original RTC.

Place, publisher, year, edition, pages
IEEE Computer Society, 2013
National Category
Computer Systems
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-209549 (URN)
Conference
RTSS 2013
Projects
UPMARC
Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2014-01-23
9. General and Efficient Response Time Analysis for EDF Scheduling
Open this publication in new window or tab >>General and Efficient Response Time Analysis for EDF Scheduling
2014 (English)In: Proc. 17th Conference on Design, Automation and Test in Europe, Piscataway, NJ: IEEE , 2014Conference paper, Published paper (Other academic)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2014
National Category
Computer Systems
Identifiers
urn:nbn:se:uu:diva-209546 (URN)10.7873/DATE.2014.268 (DOI)000354965500255 ()978-3-9815370-2-4 (ISBN)
Conference
DATE 2014, March 24–28, Dresden, Germany
Projects
UPMARC
Available from: 2013-10-21 Created: 2013-10-21 Last updated: 2015-12-16Bibliographically approved

Open Access in DiVA

fulltext(1726 kB)945 downloads
File information
File name FULLTEXT03.pdfFile size 1726 kBChecksum SHA-512
ddd0fc8a5759925131fe42116237fbd8b99a49cefc162e230387893bc740823e78b266effd117f693975141487ad3ca2f4e911dd7b7e79ca30860e7c9b7d9fd7
Type fulltextMimetype application/pdf
Buy this publication >>

Authority records BETA

Guan, Nan

Search in DiVA

By author/editor
Guan, Nan
By organisation
Division of Computer SystemsComputer Systems
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 945 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 824 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf