Analyzing data cache related preemption delay with multiple preemptions

Wei Zhang, Nan Guan, Lei Ju, Weichen Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Timing analysis of real-time tasks under preemptive scheduling must take cache-related preemption delay (CRPD) into account. Typically, a task may be preempted more than once during the execution in each period. To bound the total CRPD of k preemptions, existing CRPD analysis techniques estimate the CRPD at each program point, and use the sum of the k-largest CRPD among all program points as the total CRPD upper bound. In this paper, we disclose that the above-mentioned approach, although works well for instruction caches, leads to significant overestimation when dealing with data caches. This is because on data caches, the CRPD of preemptions at different program points may have correlations, and the total CRPD of multiple preemptions is in general smaller than the simple sum of the worst-case CRPD of each preemption. To address this problem, we propose a new technique to efficiently explore the correlation among the CRPD of different preemptions, and thus more precisely calculate the total CRPD. Experiments with benchmark programs show that the proposed technique leads to substantially tighter total CRPD estimation with multiple preemptions comparing with the state-of-the-art.

Original languageEnglish
Article number8493517
Pages (from-to)2255-2265
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume37
Issue number11
DOIs
Publication statusPublished - Nov 2018

Keywords

  • Cache-related preemption delay (CRPD)
  • data cache
  • real-time systems
  • timing analysis

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this