License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2017.6
URN: urn:nbn:de:0030-drops-73103
Go to the corresponding OASIcs Volume Portal

Brandner, Florian ; Naji, Amine

Worst-Case Execution Time Analysis of Predicated Architectures

OASIcs-WCET-2017-6.pdf (0.5 MB)


The time-predictable design of computer architectures for the use in (hard) real-time systems is becoming more and more important, due to the increasing complexity of modern computer architectures. The design of predictable processor pipelines recently received considerable attention. The goal here is to find a trade-off between predictability and computing power.

Branches and jumps are particularly problematic for high-performance processors. For one, branches are executed late in the pipeline. This either leads to high branch penalties (flushing) or complex software/hardware techniques (branch predictors). Another side-effect of branches is that they make it difficult to exploit instruction-level parallelism due to control dependencies.

Predicated computer architectures allow to attach a predicate to the instructions in a program. An instruction is then only executed when the predicate evaluates to true and otherwise behaves like a simple nop instruction. Predicates can thus be used to convert control dependencies into data dependencies, which helps to address both of the aforementioned problems.

A downside of predicated instructions is the precise worst-case execution time (WCET) analysis of programs making use of them. Predicated memory accesses, for instance, may or may not have an impact on the processor's cache and thus need to be considered by the cache analysis. Predication potentially has an impact on all analysis phases of a WCET analysis tool. We thus explore a preprocessing step that explicitly unfolds the control-flow graph, which allows us to apply standard analyses that are themselves not aware of predication.

BibTeX - Entry

  author =	{Florian Brandner and Amine Naji},
  title =	{{Worst-Case Execution Time Analysis of Predicated Architectures}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{6:1--6:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Jan Reineke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-73103},
  doi =		{10.4230/OASIcs.WCET.2017.6},
  annote =	{Keywords: Predication, Worst-Case Execution Time Analysis, Real-Time Systems}

Keywords: Predication, Worst-Case Execution Time Analysis, Real-Time Systems
Collection: 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)
Issue Date: 2017
Date of publication: 23.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI