Back to Search Start Over

The complexity of verifying memory coherence and consistency

Authors :
Cantin, Jason F.
Lipasti, Mikko H.
Smith, James E.
Source :
IEEE Transactions on Parallel and Distributed Systems. July, 2005, Vol. 16 Issue 7, p663, 9 p.
Publication Year :
2005

Abstract

The problem of testing shared memories for memory coherence and consistency is studied where 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. The results indicate that the complexity of verifying consistency models is not a mere consequence of coherence and verifying sequential consistency remains NP-Complete even after coherence is verified.

Subjects

Subjects :
Error analysis (Mathematics) -- Methods
Fault tolerance (Computers) -- Design and construction
Memory compaction -- Analysis
Memory management -- Analysis
Memory mapping -- Analysis
Memory partitioning -- Analysis
Memory protection -- Analysis
Memory refresh (Computers) -- Analysis
Fault tolerance
Storage capacity
Business
Computers
Electronics
Electronics and electrical industries

Details

Language :
English
ISSN :
10459219
Volume :
16
Issue :
7
Database :
Gale General OneFile
Journal :
IEEE Transactions on Parallel and Distributed Systems
Publication Type :
Academic Journal
Accession number :
edsgcl.135810110

Tools

Authors Abstract Subjects Details