Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/22089
DC Field | Value | |
---|---|---|
dc.title | Scope-aware data cache analysis for WCET estimation | |
dc.contributor.author | HUYNH BACH KHOA | |
dc.date.accessioned | 2011-04-30T18:00:26Z | |
dc.date.available | 2011-04-30T18:00:26Z | |
dc.date.issued | 2010-12-13 | |
dc.identifier.citation | HUYNH BACH KHOA (2010-12-13). Scope-aware data cache analysis for WCET estimation. ScholarBank@NUS Repository. | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/22089 | |
dc.description.abstract | Caches are widely used in modern computer systems to bridge the increasing gap between processor speed and memory access time. However, presence of caches, especially data caches, complicates the static worst case execution time (WCET) analysis. Access pattern analysis (e.g., cache miss equations) are applicable to only a specific class of programs, where all array accesses must have predictable access patterns. Abstract interpretation-based methods (must/persistence analysis) determines cache conflicts based on coarse-grained memory access information from address analysis, which usually leads to significant over-estimation. In this thesis, we first present a refined persistence analysis method which fixes the potential underestimation problem in the original persistence analysis. Based on our new persistence analysis, we propose a framework to combine access pattern analysis and abstract interpretation for accurate data cache analysis. We capture the dynamic behavior of a memory access by computing its temporal scope (the loop iterations where a given memory block is accessed for a given data reference) during address analysis. Temporal scopes as well as loop hierarchy structure (the static scopes) are integrated and utilized to achieve a more precise abstract cache state modeling. We also prove the correctness of the proposed new persistence analysis. Experimental results shows that our proposed analysis obtains up to 74% reduction in the WCET estimates compared to existing data cache analysis. | |
dc.language.iso | en | |
dc.subject | data cache analysis, abstract interpretation, wcet, program analysis, | |
dc.type | Thesis | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.contributor.supervisor | ABHIK ROYCHOUDHURY | |
dc.description.degree | Master's | |
dc.description.degreeconferred | MASTER OF SCIENCE | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Master's Theses (Open) |
Show simple item record
Files in This Item:
File | Description | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
HuynhBachKhoa.pdf | 916.31 kB | Adobe PDF | OPEN | None | View/Download |
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.