On-the-fly Validation of Hierarchical Cache Coherence Protocols using Directed Testing

Abstract

Recent advances in memory technologies and programming models have heightened the demand for sophisticated memory hierarchies. A critical aspect of these hierarchies is the implementation of cache coherence protocols, which play a pivotal role in maintaining data integrity across multi-core memory systems. Despite the availability of various validation techniques, such as random testing, constrained random testing, and formal verification, these approaches often lack exhaustiveness guarantees or are resource-intensive, requiring significant time and memory to guarantee protocol correctness. Existing directed testing frameworks, while promising, often encounter challenges such as state space explosion and the potential omission of critical states if not applied meticulously. We propose an enhanced on-the-fly directed validation method specifically designed for multilevel cache coherence protocols to address these limitations. Our approach achieves complete state and transition coverage with approximately 50% fewer test cases without increasing memory overheads.