WCET Analysis of Multilevel Data Cache with Multitier Coherence Protocol

The high parallel computing performance of multicore processors has made them popular for real-time systems. However, compared to single-core processors, the worst-case execution time (WCET) analysis of multicore processors is confronted with challenges due to shared resource competition and parallel task interference. The cache coherence protocol in multicore processors makes WCET analysis even more complex. In this paper, we propose a method to analyze the WCET of multicore processors’ multilevel data cache with multitier coherence protocols. The safe filtering mechanism of memory access is extended to define which reference may occur at each cache level under the multitier coherence protocols. We use a hierarchical coherency-domain model to organize coherence analysis within and across domains. Based on the memory hierarchy access rules and coherency domains, the method divides the shared data access of multicore processors into intra-domain access and cross-domain access, calculates the cache access latency, and provides a function for updating and joining the abstract states of the multilevel data cache with a multitier coherence protocol to calculate the WCET of tasks. For the evaluated cache configurations, the WCET estimates are not lower than the corresponding Gem5 execution times, supporting the analysis under the stated modeling assumptions. Compared with published KTA results obtained under different evaluation conditions, the average overestimation ratio is 37.98% lower.