A method to improve the estimated worst-case performance of data caching

The paper presents a method for tight prediction of worst case performance of data caches in high performance real time systems. Our approach is to distinguish between data structures that exhibit a predictable versus unpredictable cache behavior. Cache performance of accesses to predictable data structures can be automatically and accurately determined by our method, whereas we let accesses to unpredictable data structures bypass the cache to simplify and improve the analysis. Through experimentation with a number of benchmark programs, we show that a vast majority of data accesses stems from predictable data structures. We analyze the type of data structures that fall into this category. Remarkably, we find that all data structures in five out of the seven programs are predictable and will lead to a worst case cache performance which is as high as the real performance. Moreover, for the remaining two benchmarks, a majority of the accesses go to predictable data structures. Hence, empirically our data suggest that data caching is expected to improve worst case performance considerably using our method.