The complexity of verifying memory coherence and consistency

Author

Cantin, Jason F. ; Lipasti, Mikko H. ; Smith, James E.

Author_Institution

Dept. of Electr. & Comput. Eng., Wisconsin-Madison Univ., Madison, WI, USA

Volume

16

Issue

7

fYear

2005

fDate

7/1/2005 12:00:00 AM

Firstpage

663

Lastpage

671

Abstract

The problem of testing shared memories for memory coherence and consistency is studied. First, it is proved that detecting violations of coherence in an execution is NP-complete, and it remains NP-complete for a number of restricted instances. This result leads to a proof that all known consistency models are NP-hard to verify. The complexity of verifying consistency models is not a mere consequence of coherence, and verifying sequential consistency remains NP-complete even after coherence has been verified.

Keywords

computational complexity; fault tolerant computing; processor scheduling; shared memory systems; storage management; NP-complete problems; NP-hard problems; error-checking; fault-tolerance; memory coherence verification; memory consistency complexity; memory structures; scheduling; shared memory testing; Algorithm design and analysis; Circuit testing; Coherence; Fault tolerance; Hardware; Multiprocessing systems; Processor scheduling; Reliability theory; Scheduling algorithm; System testing; Hardware; design styles; error-checking; fault-tolerance; memory structures; nonnumerical algorithms and problems; reliability; sequencing and scheduling.; shared memory; testing; theory of computation;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/TPDS.2005.86

Filename

1435343