Technical Reports

Permanent URI for this collection

https://dl.comp.nus.edu.sg/handle/1900.100/12

Browse

Browsing Technical Reports by Subject "Cache-efficient Algorithms"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Program Transformations for Predictable Cache Behavior
    (2009-05-25T06:47:26Z) HUYNH, Bach Khoa; JU, Lei; CHATTOPADHYAY, Sudipta; ROYCHOUDHURY, Abhik
    Real-time embedded software developers need to balance the dual (and seemingly conflicting) concerns of efficiency and predictability. Efficiency concerns are typically addressed by tuning the application and its underlying processing platform through a variety of techniques such as generating custom instructions in the instruction set, or configuring the processing platform. However, timing predictability remains a difficult goal to achieve, specifically in the presence of performance-enhancing micro-architectural features such as data caches. Presence of data caches can cause vast variation in the execution time for even programs with a single path. In this paper, we study a new approach to achieve predictable cache behavior (without large performance degradation) in data-intensive embedded applications. Our approach is to rewrite a given application into a “cache-efficient” style, where the data memory accesses are tracked and transformed to systematically reduce data cache conflicts. Our program transformation leads to lesser execution time variation in the transformed program (across program inputs as well as across cache configurations). We also develop a new Worst-case Execution Time (WCET) analysis method for data caches, and show that it leads to tighter WCET estimates for cache-efficient programs. Our experiments indicate that adopting the cache-efficient style of programming for data-intensive embedded software can help balance the dual concerns of efficiency and predictability.