loading...
Reducing Verification Complexity of a Multicore Coherence Protocol Using Assume/Guarantee
San Jose, California, USA November 12-November 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FMCAD.2006.28Formal Methods in Computer Aided Desi ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Xiaofang Chen, University of Utah, USA
Yu Yang, University of Utah, USA
Ganesh Gopalakrishnan, University of Utah, USA
Ching-Tsun Chou, Intel Corporation
We illustrate how to employ metacircular assume/ guarantee reasoning to reduce the verification complexity of finite instances of protocols for safety, using nothing more than an explicit state model checker. The formal underpinnings of our method are based on establishing a simulation relation between the given protocol M, and several overapproximations thereof, \tilde M_1,..., \tilde M_k. Each \tilde M_i simulates M, and represents one "view" of it. The \tilde M_{i}s depend on each other both to define the abstractions as well as to justify them.We show that in case of our hierarchical coherence protocol, its designer could easily construct each of the \tilde M_i in a counterexample guided manner. This approach is practical, considerably reduces the verification complexity, and has been successfully applied to a complex hierarchical multicore cache coherence protocol which could not be verified through traditional model checking.
Citation:
Xiaofang Chen, Yu Yang, Ganesh Gopalakrishnan, Ching-Tsun Chou, "Reducing Verification Complexity of a Multicore Coherence Protocol Using Assume/Guarantee," fmcad, pp.81-88, Formal Methods in Computer Aided Design (FMCAD'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.