Precise Shared Instruction Cache Analysis to Estimate WCET of Multi-threaded Programs
P. Padma Priya Dharishini, PVR Murthy · 2021 IEEE 18th India Council International Conference (INDICON) · 2021
Worst Case Execution Time analysis has received considerable attention in the recent past, mainly to guarantee safety criteria for real-time embedded applications. Several investigations have provided techniques to determine the latency contribution, to WCET, due to instruction cache misses. However, their main drawback is that the set of inter-thread interferences to the shared instruction cache includes interferences that never arise in actual runs of the multi-threaded program. Thus, for a more precise WCET analysis of accesses to shared instruction cache, instructions in a competing thread that would never cause interferences should be excluded. The main contribution is to propose an algorithm whereby a multi-threaded program, running on multiple cores, is partitioned one or more times corresponding to the number of synchronization pairs (wait, notify) in the threads. Each partition of threads represents a concurrent region of instructions which corresponds to incomparable instructions with respect to the happens before relation. Our Algorithm is integrated into the multi-core chronos open source WCET analyzer. A number of benchmark programs are run using the simulator. WCET analysis, for shared instruction cache, based on partitioned inter-thread interferences, yields more precise WCET estimates and the hypothesis is proven theoretically and validated empirically on benchmark programs.