Minimizing WCET for real-time embedded systems via static instruction cache locking

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)

48 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Pages35-44
Publication statusPublished - 2009

Publication series

Name
ISSN (Print)1545-3421

Conference

Title15th IEEE Real-Time and Embedded Technology and Application Symposium, RTAS 2009
PlaceUnited States
CitySan Francisco
Period14 - 16 April 2009

Abstract

Cache is effective in bridging the gap between processor and memory speed. It is also a source of unpredictability because of its dynamic and adaptive behavior. Worst-case execution time (WCET) of an application is one of the most important criteria for real-time embedded system design. The unpredictability of instruction miss/hit behavior in the instruction cache (I-Cache) leads to an unnecessary overestimation of the real-time application's WCET. A lot of modern processors provide cache locking capability. Static ICache locking locks function/instruction blocks of a program into the I-Cache before program execution. In this way, a more precise estimation of WCET can be achieved. The selection of functions/instructions to be locked in the I-Cache has dramatic influence on the performance of the real-time application. This paper focuses on the static I-Cache locking problem to minimize WCET for real-time embedded systems. We formulate the problem using an Execution Flow Tree (EFT) and a linear programming model. For a subset of the problems with certain properties, corresponding polynomial time optimal algorithms are proposed. We prove that the general problem is an NP-Hard problem. We also show that for a subset of the general problem with certain patterns, optimal solutions can be achieved in polynomial time. Experimental results show that our algorithms can reduce the WCET of applications further compared to current best known techniques. © 2009 IEEE.

Citation Format(s)

Minimizing WCET for real-time embedded systems via static instruction cache locking. / Liu, Tiantian; Li, Minming; Xue, Chun Jason.

Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS. 2009. p. 35-44 4840565.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)