OASIcs, Volume 18

Bringing Theory to Practice: Predictability and Performance in Embedded Systems



Thumbnail PDF

Event

PPES 2011, March 18, 2011, Grenoble, France

Editors

Philipp Lucas
Reinhard Wilhelm

Publication Details

  • published at: 2011-03-21
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
  • ISBN: 978-3-939897-28-6
  • DBLP: db/conf/date/ppes2011

Access Numbers

Documents

No documents found matching your filter selection.
Document
Complete Volume
OASIcs, Volume 18, PPES'11, Complete Volume

Authors: Philipp Lucas, Lothar Thiele, Benoit Triquet, Theo Ungerer, and Reinhard Wilhelm


Abstract
OASIcs, Volume 18, PPES'11, Complete Volume

Cite as

Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@Proceedings{lucas_et_al:OASIcs.PPES.2011,
  title =	{{OASIcs, Volume 18, PPES'11, Complete Volume}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011},
  URN =		{urn:nbn:de:0030-drops-35804},
  doi =		{10.4230/OASIcs.PPES.2011},
  annote =	{Keywords: Special-purpose and application-based systems\rbrack: Real-time and embedded systems}
}
Document
Front Matter
Preface (Frontmatter, Table of Contents, Preface)

Authors: Philipp Lucas and Reinhard Wilhelm


Abstract
Frontmatter, Table of Contents, Preface

Cite as

Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. i-vii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{lucas_et_al:OASIcs.PPES.2011.i,
  author =	{Lucas, Philipp and Wilhelm, Reinhard},
  title =	{{Preface (Frontmatter, Table of Contents, Preface)}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{i--vii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.i},
  URN =		{urn:nbn:de:0030-drops-30767},
  doi =		{10.4230/OASIcs.PPES.2011.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface}
}
Document
Software Structure and WCET Predictability

Authors: Gernot Gebhard, Christoph Cullmann, and Reinhold Heckmann


Abstract
Being able to compute worst-case execution time bounds for tasks of an embedded software system with hard real-time constraints is crucial to ensure the correct (timing) behavior of the overall system. Any means to increase the (static) time predictability of the embedded software are of high interest -- especially due to the ever-growing complexity of such software systems. In this paper we study existing coding proposals and guidelines, such as MISRA-C, and investigate whether they simplify static timing analysis. Furthermore, we investigate how additional knowledge, such as design-level information, can further aid in this process.

Cite as

Gernot Gebhard, Christoph Cullmann, and Reinhold Heckmann. Software Structure and WCET Predictability. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{gebhard_et_al:OASIcs.PPES.2011.1,
  author =	{Gebhard, Gernot and Cullmann, Christoph and Heckmann, Reinhold},
  title =	{{Software Structure and WCET Predictability}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{1--10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.1},
  URN =		{urn:nbn:de:0030-drops-30836},
  doi =		{10.4230/OASIcs.PPES.2011.1},
  annote =	{Keywords: WCET Predictability, Embedded Software Structure, Coding Guidelines}
}
Document
Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach

Authors: Martin Schoeberl, Pascal Schleuniger, Wolfgang Puffitsch, Florian Brandner, and Christian W. Probst


Abstract
Current processors are optimized for average case performance, often leading to a high worst-case execution time (WCET). Many architectural features that increase the average case performance are hard to be modeled for the WCET analysis. In this paper we present Patmos, a processor optimized for low WCET bounds rather than high average case performance. Patmos is a dual-issue, statically scheduled RISC processor. The instruction cache is organized as a method cache and the data cache is organized as a split cache in order to simplify the cache WCET analysis. To fill the dual-issue pipeline with enough useful instructions, Patmos relies on a customized compiler. The compiler also plays a central role in optimizing the application for the WCET instead of average case performance.

Cite as

Martin Schoeberl, Pascal Schleuniger, Wolfgang Puffitsch, Florian Brandner, and Christian W. Probst. Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 11-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{schoeberl_et_al:OASIcs.PPES.2011.11,
  author =	{Schoeberl, Martin and Schleuniger, Pascal and Puffitsch, Wolfgang and Brandner, Florian and Probst, Christian W.},
  title =	{{Towards a Time-predictable Dual-Issue Microprocessor: The Patmos Approach}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{11--21},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.11},
  URN =		{urn:nbn:de:0030-drops-30774},
  doi =		{10.4230/OASIcs.PPES.2011.11},
  annote =	{Keywords: Time-predictable architecture, WCET analysis, WCET-aware compilation}
}
Document
A Template for Predictability Definitions with Supporting Evidence

Authors: Daniel Grund, Jan Reineke, and Reinhard Wilhelm


Abstract
In real-time systems, timing behavior is as important as functional behavior. Modern architectures turn verification of timing aspects into a nightmare, due to their "unpredictability". Recently, various efforts have been undertaken to engineer more predictable architectures. Such efforts should be based on a clear understanding of predictability. We discuss key aspects of and propose a template for predictability definitions. To investigate the utility of our proposal, we examine above efforts and try to cast them as instances of our template.

Cite as

Daniel Grund, Jan Reineke, and Reinhard Wilhelm. A Template for Predictability Definitions with Supporting Evidence. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 22-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{grund_et_al:OASIcs.PPES.2011.22,
  author =	{Grund, Daniel and Reineke, Jan and Wilhelm, Reinhard},
  title =	{{A Template for Predictability Definitions with Supporting Evidence}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{22--31},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.22},
  URN =		{urn:nbn:de:0030-drops-30785},
  doi =		{10.4230/OASIcs.PPES.2011.22},
  annote =	{Keywords: predictability, uncertainty, precision}
}
Document
An Overview of Approaches Towards the Timing Analysability of Parallel Architecture

Authors: Christine Rochange


Abstract
In order to meet performance/low energy/integration requirements, parallel architectures (multithreaded cores and multi-cores) are more and more considered in the design of embedded systems running critical software. The objective is to run several applications concurrently. When applications have strict real-time constraints, two questions arise: a) how can the worst-case execution time (WCET) of each application be computed while concurrent applications might interfere? b)~how can the tasks be scheduled so that they are guarantee to meet their deadlines? The second question has received much attention for several years~\cite{CFHS04,DaBu11}. Proposed schemes generally assume that the first question has been solved, and in addition that they do not impact the WCETs. In effect, the first question is far from been answered even if several approaches have been proposed in the literature. In this paper, we present an overview of these approaches from the point of view of static WCET analysis techniques.

Cite as

Christine Rochange. An Overview of Approaches Towards the Timing Analysability of Parallel Architecture. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 32-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{rochange:OASIcs.PPES.2011.32,
  author =	{Rochange, Christine},
  title =	{{An Overview of Approaches Towards the Timing Analysability of Parallel Architecture}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{32--41},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.32},
  URN =		{urn:nbn:de:0030-drops-30798},
  doi =		{10.4230/OASIcs.PPES.2011.32},
  annote =	{Keywords: WCET analysis, multicore, time predictability}
}
Document
Towards the Implementation and Evaluation of Semi-Partitioned Multi-Core Scheduling

Authors: Yi Zhang, Nan Guan, and Wang Yi


Abstract
Recent theoretical studies have shown that partitioning-based scheduling has better real-time performance than other scheduling paradigms like global scheduling on multi-cores. Especially, a class of partitioning-based scheduling algorithms (called semi-partitioned scheduling), which allow to split a small number of tasks among different cores, offer very high resource utilization, and appear to be a promising solution for scheduling real-time systems on multi-cores. The major concern about the semi-partitioned scheduling is that due to the task splitting, some tasks will migrate from one core to another at run time, and might incur higher context switch overhead than partitioned scheduling. So one would suspect whether the extra overhead caused by task splitting would counteract the theoretical performance gain of semi-partitioned scheduling. In this work, we implement a semi-partitioned scheduler in the Linux operating system, and run experiments on a Intel Core-i7 4-cores machine to measure the real overhead in both partitioned scheduling and semi-partitioned scheduling. Then we integrate the obtained overhead into the state-of-the-art partitioned scheduling and semi-partitioned scheduling algorithms, and conduct empirical comparison of their real-time performance. Our results show that the extra overhead caused by task splitting in semi-partitioned scheduling is very low, and its effect on the system schedulability is very small. Semi-partitioned scheduling indeed outperforms partitioned scheduling in realistic systems.

Cite as

Yi Zhang, Nan Guan, and Wang Yi. Towards the Implementation and Evaluation of Semi-Partitioned Multi-Core Scheduling. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 42-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{zhang_et_al:OASIcs.PPES.2011.42,
  author =	{Zhang, Yi and Guan, Nan and Yi, Wang},
  title =	{{Towards the Implementation and Evaluation of Semi-Partitioned Multi-Core Scheduling}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{42--46},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.42},
  URN =		{urn:nbn:de:0030-drops-30804},
  doi =		{10.4230/OASIcs.PPES.2011.42},
  annote =	{Keywords: real-time operating system, multi-core, semi-partitioned scheduling}
}
Document
An Automated Flow to Map Throughput Constrained Applications to a MPSoC

Authors: Roel Jordans, Firew Siyoum, Sander Stuijk, Akash Kumar, and Henk Corporaal


Abstract
This paper describes a design flow to map throughput constrained applications on a Multi-processor System-on-Chip (MPSoC). It integrates several state-of-the-art mapping and synthesis tools into an automated tool flow. This flow takes as input a throughput constrained application, modeled with a synchronous dataflow graph, a C-based implementation for each actor in the graph, and a template based architecture description. Using these inputs, the tool flow generates an MPSoC platform tailored to the application requirements and it subsequently maps the application to this platform. The output of the flow is an FPGA programmable bit file. An easily extensible template based architecture is presented, this architecture allows fast and flexible generation of a predictable platform that can be synthesized using the presented tool flow. The effectiveness of the tool flow is demonstrated by mapping an MJPEG-decoder onto our MPSoC platform. This case study shows that our flow is able to provide a tight, conservative bound on the worst-case throughput of the FPGA implementation. The presented tool flow is freely available at http://www.es.ele.tue.nl/mamps.

Cite as

Roel Jordans, Firew Siyoum, Sander Stuijk, Akash Kumar, and Henk Corporaal. An Automated Flow to Map Throughput Constrained Applications to a MPSoC. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 47-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{jordans_et_al:OASIcs.PPES.2011.47,
  author =	{Jordans, Roel and Siyoum, Firew and Stuijk, Sander and Kumar, Akash and Corporaal, Henk},
  title =	{{An Automated Flow to Map Throughput Constrained Applications to a MPSoC}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{47--58},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.47},
  URN =		{urn:nbn:de:0030-drops-30819},
  doi =		{10.4230/OASIcs.PPES.2011.47},
  annote =	{Keywords: design flow automation, multi-processor system-on-chip, throughput constrained, synchronous data-flow graphs}
}
Document
Towards Formally Verified Optimizing Compilation in Flight Control Software

Authors: Ricardo Bedin França, Denis Favre-Felix, Xavier Leroy, Marc Pantel, and Jean Souyris


Abstract
This work presents a preliminary evaluation of the use of the CompCert formally specified and verified optimizing compiler for the development of level A critical flight control software. First, the motivation for choosing CompCert is presented, as well as the requirements and constraints for safety-critical avionics software. The main point is to allow optimized code generation by relying on the formal proof of correctness instead of the current un-optimized generation required to produce assembly code structurally similar to the algorithmic language (and even the initial models) source code. The evaluation of its performance (measured using WCET) is presented and the results are compared to those obtained with the currently used compiler. Finally, the paper discusses verification and certification issues that are raised when one seeks to use CompCert for the development of such critical software.

Cite as

Ricardo Bedin França, Denis Favre-Felix, Xavier Leroy, Marc Pantel, and Jean Souyris. Towards Formally Verified Optimizing Compilation in Flight Control Software. In Bringing Theory to Practice: Predictability and Performance in Embedded Systems. Open Access Series in Informatics (OASIcs), Volume 18, pp. 59-68, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{franca_et_al:OASIcs.PPES.2011.59,
  author =	{Fran\c{c}a, Ricardo Bedin and Favre-Felix, Denis and Leroy, Xavier and Pantel, Marc and Souyris, Jean},
  title =	{{Towards Formally Verified Optimizing Compilation in Flight Control Software}},
  booktitle =	{Bringing Theory to Practice: Predictability and Performance in Embedded Systems},
  pages =	{59--68},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-28-6},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{18},
  editor =	{Lucas, Philipp and Wilhelm, Reinhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.PPES.2011.59},
  URN =		{urn:nbn:de:0030-drops-30824},
  doi =		{10.4230/OASIcs.PPES.2011.59},
  annote =	{Keywords: Compiler verification, avionics software, WCET, code optimization}
}

Filters


Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail