Cache Design And Timing Analysis For Preemptive Multi Tasking Real Time Uniprocessor Systems

Cache Design and Timing Analysis for Preemptive Multi-tasking Real-time Uniprocessor Systems

In this thesis, we propose an approach to estimate the Worst Case Response Time (WCRT) of each task in a preemptive multi-tasking single-processor real-time system utilizing an L1 cache. The approach combines inter-task cache eviction analysis and intra-task cache access analysis to estimate the Cache Related Preemption Delay (CRPD). CRPD caused by preempting task(s) is then incorporated into WCRT analysis. We also propose a prioritized cache to reduce CRPD by exploiting cache partitioning technique. Our WCRT analysis approach is then applied to analyze the behavior of a prioritized cache. Four sets of applications with up to six concurrent tasks running are used to test our WCRT analysis approach and the prioritized cache. The experimental results show that our WCRT analysis approach can tighten the WCRT estimate by up to 32% (1.4X) over prior state-of-the-art. By using a prioritized cache, we can reduce the WCRT estimate of tasks by up to 26%, as compared to a conventional set associative cache.

ACM SIGPLAN Notices

Real Time and Such

This Festschrift reflects Professor Wang Yi's contributions to the fields of formal methods, real-time systems and scheduling, and multicore systems. Wang Yi received a PhD in Computer Science from Chalmers University of Technology in 1991, since 2000 he has been Chair in Embedded Systems at Uppsala University. He has not only pushed the boundaries of theoretical research but also pioneered practical implementations in software tools that have had a profound impact on both academia and industry. He codeveloped the UPPAAL tool, the foremost system for verifying timed automata, now widely used in both academia and industry. Over the years he expanded his research to include scheduling theories, and he developed the TIMES and TIMES-Pro tools, which enhanced the analysis and implementation of real-time systems. His innovative work has significantly influenced the design and verification of complex, multicore real-time systems. Among many awards, honours, and responsibilities, Wang received a grant from the Knut and Alice Wallenberg Foundation, an ERC Advanced Grant from the European Research Council in 2019, Uppsala University’s Rudbeck Medal, the IEEE TCRTS Award for technical achievement and leadership in real-time computing, and the CAV Award; he is a Fellow of the ACM and the IEEE, and a member of the Royal Society of Sciences in Uppsala and the Academia Europaea; and he has chaired major software engineering and embedded system conferences and served on ACM SIGBED and IEEE TCRTS executive committees. His guidance and mentorship have shaped the careers of many researchers and professionals in the field, and the contributions in this volume celebrate his enduring impact.