Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2005-05-10
2005-05-10
Beausoliel, Robert (Department: 2113)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S042000, C714S718000, C716S030000
Reexamination Certificate
active
06892319
ABSTRACT:
A method of verifying a protocol for a shared-memory multiprocessor system for sequential consistency. In the system there are n processors and m memory locations that are shared by the processors. A protocol automaton, such as a cache coherence protocol automaton, is developed. The protocol automaton and a plurality of checker automata are provided to a model checker which exhaustively searches the state space of the protocol automaton. During the search, the plurality of checker automata check for the presence of cycles in a graph that is the union of the total orders of the processor references and the partial orders at each memory location. If the plurality of checker automata detect the presence of a cycle, then the protocol does not meet the sequential consistency requirement.
REFERENCES:
patent: 5406504 (1995-04-01), Denisco et al.
patent: 5958072 (1999-09-01), Jacobs et al.
patent: 6446241 (2002-09-01), Mobley et al.
patent: 6539503 (2003-03-01), Walker
patent: 6651228 (2003-11-01), Narain et al.
patent: 6654715 (2003-11-01), Iwashita
Henzinger, Thomas et al. Verifying Sequential Consistency on Shared-memory Multiprocessor Systems.http://www-cad.eecs.berkeley.edu/˜tah/Publications/verifying_sequential_consistency_for_multiprocessor_memory_protocols.pdf.*
Qadeer, Shaz Verifying Sequential Consistency on Shared-Memory Multiprocessors by Model Checking. www.ieeexplore.com.*
Condon, Anne et al. Automatable Verification of Sequential Consistency. www.acm.org.*
Qadeer, Shaz Algorithms and Methodology for Scalable Model Checking. research.microsoft.com/˜qadeer/docs/thesis-pdf.pd.
Beausoliel Robert
Hewlett--Packard Development Company, L.P.
Wilson Yolanda L
LandOfFree
Method for verifying abstract memory models of shared memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for verifying abstract memory models of shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for verifying abstract memory models of shared memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3452931