Please use this identifier to cite or link to this item:
Title: Instruction and data cache modeling for timing analysis in real-time systems
Authors: LI YANHUI
Keywords: WCET, Cache, Real-time System, input-dependent data access, NP-completeness, System Performance
Issue Date: 9-Feb-2009
Citation: LI YANHUI (2009-02-09). Instruction and data cache modeling for timing analysis in real-time systems. ScholarBank@NUS Repository.
Abstract: Caches in Embedded Systems improve average case performance, but they are a source of unpredictability, especially in the worst case software timing analysis with the consideration of data caches. This is a critical problem in real-time systems, where tight Worst Case Execution Time (WCET) is required for their schedulability analysis. To provide an efficient and accurate analysis for input-dependent data caches, we develop classified cache architecture and a WCET framework for the architecture. Our work classifies predictable and unpredictable accesses, then allocates them into predictable caches and unpredictable caches accordingly, and uses CME (Cache Miss Equations) and our reuse-distance-based algorithm for their timing analysis respectively. Compared with simulation, our analysis framework produces a very good WCET tightness, and our architecture creates almost no hardware overhead or performance degradation. In addition, we examine NP-completeness for theoretical support and proved WCET analysis is NP-complete. We also explore data allocation techniques to improve system performance, and our algorithm improves cache hit ratios efficiently according to our experimental results.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
2008Thesis-Yanhui LI-ECE.pdf2.77 MBAdobe PDF



Page view(s)

checked on Apr 20, 2019


checked on Apr 20, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.