Chain-based pseudorandom tests for pre-silicon verification of CMP memory systems

The coherent shared-memory abstraction is expected to keep its crucial role in Chip Multiprocessors even on the scale of hundreds of cores. As a result, the growing hardware complexity to support such abstraction makes the design of the memory system proner to error. Therefore, it is crucial to check for errors in shared-memory behavior as early as possible in the design flow. Given a design representation of a memory subsystem, this paper addresses the pre-silicon verification of its expected behavior, which is captured by the axioms that specify the coherence and consistency requirements of a memory model. As opposed to typical pseudorandom generation of test programs, this paper proposes the exploitation of significant operation orderings from aggressive memory model specifications for inducing load/store sequences that are more effective in uncovering design errors. The effectiveness of the novel technique was evaluated, for 8, 16, and 32-core architectures, when synthesizing 1200 distinct test programs for verifying 8 derivative designs containing errors (9600 use cases per architecture). The synthesized tests explored 5 program sizes, 4 levels of sharing, 4 instruction mixes, and 15 random seeds. Our results show that, as compared to typical pseudorandom generation, the proposed technique is more effective in exposing design errors whose sharing-level distributions are flat. For such design errors, our technique was more effective by 30% on average.