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
Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
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.

Place, publisher, year, edition, pages
2012. 261-272 p.
Series
International Parallel and Distributed Processing Symposium IPDPS
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-184746DOI: 10.1109/IPDPS.2012.33ISI: 000309131900024ISBN: 978-0-7695-4675-9 (print)OAI: oai:DiVA.org:uu-184746DiVA: diva2:567887
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
In thesis
1. New Techniques for Building Timing-Predictable Embedded Systems
Open this publication in new window or tab >>New Techniques for Building Timing-Predictable 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
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:nbn:se:uu:diva-209623 (URN)978-91-554-8797-3 (ISBN)
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

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Guan, NanStigge, MartinYi, Wang

Search in DiVA

By author/editor
Guan, NanStigge, MartinYi, Wang
By organisation
Computer Systems
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 436 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