| Shared-memory multiprocessors are becoming the dominant architecture for single-chip and multi-chip microprocessor based systems. Shared memory architectures are difficult to design because they must correctly implement the complexity of cache coherence and a memory consistency model. Memory consistency is a contract between hardware and software that specifies how memory behaves with respect to read and write operations from multiple processors.; We address the challenge of correctly implementing a memory consistency model by developing a methodology for testing shared-memory multiprocessors which is composed of three steps: generating pseudo-random multithreaded programs, executing these programs on a system under test, and checking their compliance with the given memory consistency model. Although the last step is known to be an NP-complete problem, we develop a suite of novel algorithms that work efficiently in practice. Using these algorithms, our methodology has found hundreds of bugs during design and verification of several commercial-graded processors. Many of these bugs are subtle and could not have been detected otherwise.; We also successfully apply our methodology to transactional memory, an emerging architecture that can significantly improve programmability while preserving or even enhancing efficiency of the memory system. |
