Skip to main content
SpringerLink
Log in

Parallel and distributed model checking in Eddy

  • SPECIAL SECTION ON SPIN
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

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 (1) performing overlapped asynchronous message passing, and (2) 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Stern, U., Dill, D.: Parallelizing the Mur\({\phi}\) verifier. Form Methods Sys Des 18(2), 117–129 (2001) (Journal version of their CAV 1997 paper)

  2. Lerda, F., Sisto, R.: Distributed-memory model checking with SPIN. In: Proceedings of SPIN 1999, Lecture Notes in Computer Science, vol. 1680. Springer, Heidelberg (1999)

  3. Dill, D.L.: The mur phi verification system. In: Proceedings of CAV 1996, Lecture Notes in Computer Science, vol. 1102, pp. 390–393. Springer, Heidelberg (1996)

  4. Butenhof D.R.: Programming with POSIX Threads. Addison-Wesley, Reading (1997)

    Google Scholar 

  5. POSIX PThreads http://www.llnl.gov/computing/tutorials/pthreads/

  6. MPI tutorial http://www-unix.mcs.anl.gov/mpi/tutorial/gropp/talk.html

  7. PThreads Win32 home page http://sourceware.org/pthreads-win32/

  8. MCCS 2003 http://www.microsoft.com/windowsserver2003/ccs/overview.mspx

  9. Palmer, R., Gopalakrishnan, G.: Refactoring spin for safety. Technical report, University of Utah, July 2005

  10. Della Penna G., Intrigila B., Melatti I., Tronci E., Venturini Zilli M.: Exploiting transition locality in automatic verification of finite state concurrent systems. Softw Tools Technol Transf 6(4), 320–341 (2004)

    Article  Google Scholar 

  11. Eddy_Murphi distribution http://www.cs.utah.edu/formal_verification/software/murphi/eddy_murphi

  12. Grumberg, O., Heyman, T., Ifergan, N., Schuster, A.: Achieving speedups in distributed symbolic reachability analysis through asynchronous computation. In: Proceedings of CHARME 2005, Lecture Notes in Computer Science, vol. 3725, pp. 129–145. Springer, Heidelberg (2005)

  13. Feldman, Y., Dershowitz, N., Hanna, Z.: Parallel multithreaded satisfiability solver: design and implementation. In: Proceedings of PDMC 2004, Electronic Notes in Theoretical Computer Science, vol. 128(3), pp. 75–90. Elsevier, Amsterdam (2005)

  14. Kumar, R., Mercer, E.: Scalable distributed model checking: experiences, lessons, and expectations. In: Proceedings of PDMC 2003, Electronic Notes in Theoretical Computer Science, vol. 89(1), p. 3. Elsevier, Amsterdam (2003)

  15. Stern, U., Dill, D.L.: Automatic verification of the sci cache coherence protocol. In: Proceedings of CHARME 1995, Lecture Notes in Computer Science, vol. 987, pp. 21–34. Springer, Heidelberg (1995)

  16. Sivaraj, H., Gopalakrishnan, G.: Random walk based heuristic algorithms for distributed memory model checking. In: Proceedings of PDMC 2003, Electronic Notes in Theoretical Computer Science, vol. 89(1), pp. 51–67. Elsevier, Amsredam (2003)

  17. Kumar, R., Mercer, E.: Load balancing parallel explicit state model checking. In: Proceedings. of PDMC 2004, Electronic Notes in Theoretical Computer Science, vol. 128 (3), pp. 19–34. Elsevier (2004)

  18. Andrews, T., Qadeer, S., Rajamani, S.K., Rehof, J., Xie, Y.: Zing: A model checker for concurrent software. Technical report, Microsoft Research (2004)

  19. Gropp, W., Lusk, E., Skjellum, A.: Using MPI: Portable Parallel Programming with the Message-Passing Interface. MIT Press (1999)

  20. MPI official specification http://www.mpi-forum.org/docs/docs.html

  21. Murphi distribution http://sprout.stanford.edu/dill/murphi.html

  22. Stern, U., Dill, D.: Parallelizing the murφ verifier. In: Grumberg, O. (ed.) Proceedings. of CAV 1997, Lecture Notes in Computer Science, vol. 1254, pp. 256–278. Springer (1997)

  23. Kuskin, J., Ofelt, D. et al.: The Stanford FLASH multiprocessor. In: Proceedings. of SIGARCH 1994, pp. 302–313, May 1994

  24. Holzmann G.J., Puri A.: A minimized automaton representation of reachable states. Software Tools for Technology Transfer 3(1), 270–278 (1998)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, University of Utah, Salt Lake City, UT, USA

    I. Melatti, R. Palmer, G. Sawaya, Y. Yang, R. M. Kirby & G. Gopalakrishnan

Authors
  1. I. Melatti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. Palmer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. G. Sawaya
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Y. Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. R. M. Kirby
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. G. Gopalakrishnan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to I. Melatti.

Additional information

Supported in part by NSF award CNS-0509379 and SRC Contract 2005-TJ-1318.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Melatti, I., Palmer, R., Sawaya, G. et al. Parallel and distributed model checking in Eddy. Int J Softw Tools Technol Transfer 11, 13–25 (2009). https://doi.org/10.1007/s10009-008-0094-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-008-0094-x

Keywords

Search

Navigation