Abstract
Model checking of safety properties can be scaled up by pooling the CPU and memory resources of multiple computers. As compute clusters containing 100s of nodes, with each node realized using multi-core (e.g., 2) CPUs will be widespread, a model checker based on the parallel (shared memory) and distributed (message passing) paradigms will more efficiently use the hardware resources. Such a model checker can be designed by having each node employ two shared memory threads that run on the (typically) two CPUs of a node, with one thread responsible for state generation, and the other for efficient communication, including (i) performing overlapped asynchronous message passing, and (ii) aggregating the states to be sent into larger chunks in order to improve communication network utilization. We present the design details of such a novel model checking architecture called Eddy. We describe the design rationale, details of how the threads interact and yield control, exchange messages, as well as detect termination. We have realized an instance of this architecture for the Murphi modeling language. Called Eddy_Murphi, we report its performance over the number of nodes as well as communication parameters such as those controlling state aggregation. Nearly linear reduction of compute time with increasing number of nodes is observed. Our thread task partition is done in such a way that it is modular, easy to port across different modeling languages, and easy to tune across a variety of platforms.
Supported in part by NSF award CNS-0509379 and SRC Contract 2005-TJ-1318.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Stern, U., Dill, D.: Parallelizing the Murφ verifier. Formal Methods in System Design 18(2), 117–129 (2001); Journal version of their CAV paper
Lerda, F., Sisto, R.: Distributed-memory model checking with SPIN. In: Dams, D.R., Gerth, R., Leue, S., Massink, M. (eds.) SPIN 1999. LNCS, vol. 1680, p. 22. Springer, Heidelberg (1999)
Dill, D.L.: The murphi verification system. In: Alur, R., Henzinger, T.A. (eds.) CAV 1996. LNCS, vol. 1102, pp. 390–393. Springer, Heidelberg (1996)
Butenhof, D.R.: Programming with POSIX Threads. Addison-Wesley, Reading (1997)
POSIX PThreads, http://www.llnl.gov/computing/tutorials/pthreads/
MPI tutorial, http://www-unix.mcs.anl.gov/mpi/tutorial/gropp/talk.html
PThreads Win32 home page, http://sourceware.org/pthreads-win32/
MCCS (2003), http://www.microsoft.com/windowsserver2003/ccs/overview.mspx
Palmer, R., Gopalakrishnan, G.: Refactoring spin for safety. Technical report, University of Utah (July 2005)
Della Penna, G., Intrigila, B., Melatti, I., Tronci, E., Venturini Zilli, M.: Exploiting transition locality in automatic verification of finite state concurrent systems. Software Tools for Technology Transfer 6(4), 320–341 (2004)
Eddy Murphi distribution, http://www.cs.utah.edu/formal_verification/software/murphi/eddy_murphi/
Grumberg, O., Heyman, T., Ifergan, N., Schuster, A.: Achieving speedups in distributed symbolic reachability analysis through asynchronous computation. In: Borrione, D., Paul, W. (eds.) CHARME 2005. LNCS, vol. 3725, pp. 129–145. Springer, Heidelberg (2005)
Feldman, Y., Dershowitz, N., Hanna, Z.: Parallel multithreaded satisfiability solver: Design and implementation. In: Proc. of PDMC 2004. Electronic Notes in Theoretical Computer Science, vol. 128(3), pp. 75–90. Elsevier, Amsterdam (2005)
Kumar, R., Mercer, E.: Scalable distributed model checking: Experiences, lessons, and expectations. In: Proc. of PDMC 2003. Electronic Notes in Theoretical Computer Science, vol. 89(1), p. 3. Elsevier, Amsterdam (2003)
Stern, U., Dill, D.L.: Automatic verification of the sci cache coherence protocol. In: Camurati, P.E., Eveking, H. (eds.) CHARME 1995. LNCS, vol. 987, pp. 21–34. Springer, Heidelberg (1995)
Sivaraj, H., Gopalakrishnan, G.: Random walk based heuristic algorithms for distributed memory model checking. In: Proc. of PDMC 2003. Electronic Notes in Theoretical Computer Science, vol. 89(1), pp. 51–67. Elsevier, Amsterdam (2003)
Kumar, R., Mercer, E.: Load balancing parallel explicit state model checking. In: Proc. of PDMC 2004. Electronic Notes in Theoretical Computer Science, vol. 128(3), pp. 19–34. Elsevier, Amsterdam (2004)
Andrews, T., Qadeer, S., Rajamani, S.K., Rehof, J., Xie, Y.: Zing: A model checker for concurrent software. Technical report, Microsoft Research (2004)
Gropp, W., Lusk, E., Skjellum, A.: Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press, Cambridge (1999)
MPI official specification, http://www.mpi-forum.org/docs/docs.html
Murphi distribution, http://sprout.stanford.edu/dill/murphi.html
Stern, U., Dill, D.: Parallelizing the murϕ verifier. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 256–278. Springer, Heidelberg (1997)
Kuskin, J., Ofelt, D., et al.: The Stanford FLASH multiprocessor. In: Proc. of SIGARCH 1994, May 1994, pp. 302–313 (1994)
Holzmann, G.J., Puri, A.: A minimized automaton representation of reachable states. Software Tools for Technology Transfer 3(1), 270–278 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Melatti, I., Palmer, R., Sawaya, G., Yang, Y., Kirby, R.M., Gopalakrishnan, G. (2006). Parallel and Distributed Model Checking in Eddy. In: Valmari, A. (eds) Model Checking Software. SPIN 2006. Lecture Notes in Computer Science, vol 3925. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11691617_7
Download citation
DOI: https://doi.org/10.1007/11691617_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33102-5
Online ISBN: 978-3-540-33103-2
eBook Packages: Computer ScienceComputer Science (R0)