Persistence-Based Branch Misprediction Bounds for WCET Analysis

Wolfgang Puffitsch

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Branch prediction is an important feature of pipelined processors to achieve high performance. However, it can lead to overly pessimistic worst-case execution time (WCET) bounds when being modeled too conservatively. This paper presents bounds on the number of branch mispredictions for local dynamic branch predictors. To handle interferences between branch instructions we use the notion of persistence, a concept that is also found in cache analyses. The bounds apply to branches in general, not only to branches that close a loop. Furthermore, the bounds can be easily integrated into integer linear programming formulations of the WCET problem. An evaluation on a number of benchmarks shows that with these bounds, dynamic branch prediction does not necessarily lead to higher WCET bounds than static prediction schemes.
Original languageEnglish
Title of host publicationProceedings of the 30th Annual ACM Symposium on Applied Computing (SAC '15)
PublisherAssociation for Computing Machinery
Publication date2015
Pages1898-1905
ISBN (Print)978-1-4503-3196-8
DOIs
Publication statusPublished - 2015
Event30th Annual ACM/SIGAPP Symposium on Applied Computing - Salamanca, Spain
Duration: 13 Apr 201517 Apr 2015
Conference number: 30
https://www.sigapp.org/sac/sac2015/
http://www.acm.org/conferences/sac/sac2015/

Conference

Conference30th Annual ACM/SIGAPP Symposium on Applied Computing
Number30
CountrySpain
CitySalamanca
Period13/04/201517/04/2015
Internet address

Keywords

  • Worst-case execution time analysis
  • Branch prediction

Fingerprint Dive into the research topics of 'Persistence-Based Branch Misprediction Bounds for WCET Analysis'. Together they form a unique fingerprint.

Cite this