Computer and Information Science and Engineering 

Processors with multiple cores and complex cache coherence protocols are widely employed to improve the overall performance. Since the number of reachable states in a cache coherence protocol grows exponentially with the number of cores, the verification team are facing a dramatic challenge to verify the correctness of the protocol. In this paper, we propose an efficient test generation technique, which can be used to achieve full state and transition coverage in simulation based verification for a wide variety of cache coherence protocols. Based on effective analysis of the state space structure, our method can generate more efficient test sequences (50% shorter) compared with tests generated by breadth first search. Moreover, the proposed approach can generate tests on-the-fly due to its space efficient design. Experimental results demonstrate that our approach can significantly reduce the validation effort compared to existing methods.