Variations on Multi-Core Nested Depth-First Search

Alfons Laarman, Jan Cornelis van de Pol

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    9 Downloads (Pure)

    Abstract

    Recently, two new parallel algorithms for on-the-fly model checking of LTL properties were presented at the same conference: Automated Technology for Verification and Analysis, 2011. Both approaches extend Swarmed NDFS, which runs several sequential NDFS instances in parallel. While parallel random search already speeds up detection of bugs, the workers must share some global information in order to speed up full verification of correct models. The two algorithms differ considerably in the global information shared between workers, and in the way they synchronize. Here, we provide a thorough experimental comparison between the two algorithms, by measuring the runtime of their implementations on a multi-core machine. Both algorithms were implemented in the same framework of the model checker LTSmin, using similar optimizations, and have been subjected to the full BEEM model database. Because both algorithms have complementary advantages, we constructed an algorithm that combines both ideas. This combination clearly has an improved speedup. We also compare the results with the alternative parallel algorithm for accepting cycle detection OWCTY-MAP. Finally, we study a simple statistical model for input models that do contain accepting cycles. The goal is to distinguish the speedup due to parallel random search from the speedup that can be attributed to clever work sharing schemes.
    Original languageEnglish
    Title of host publicationProceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011
    EditorsJ. Barnat, K. Heljanko
    Place of PublicationUSA
    PublisherEPTCS
    Pages13-28
    Number of pages16
    DOIs
    Publication statusPublished - 14 Jul 2011
    Event10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011 - Snowbird, United States
    Duration: 14 Jul 201114 Jul 2011
    Conference number: 10
    http://anna.fi.muni.cz/PDMC/PDMC11/

    Publication series

    NameElectronic Proceedings in Theoretical Computer Science
    PublisherEPTCS
    Volume72
    ISSN (Print)2075-2180
    ISSN (Electronic)2075-2180

    Workshop

    Workshop10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011
    Abbreviated titlePDMC
    CountryUnited States
    CitySnowbird
    Period14/07/1114/07/11
    Internet address

    Fingerprint

    Parallel algorithms
    Model checking
    Statistical Models

    Keywords

    • IR-78261
    • METIS-278846
    • Parallel
    • LTL model checking
    • EWI-20618
    • Multi-Core
    • depth first search
    • swarmed
    • Nested DFS

    Cite this

    Laarman, A., & van de Pol, J. C. (2011). Variations on Multi-Core Nested Depth-First Search. In J. Barnat, & K. Heljanko (Eds.), Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011 (pp. 13-28). (Electronic Proceedings in Theoretical Computer Science; Vol. 72). USA: EPTCS. https://doi.org/10.4204/EPTCS.72.2
    Laarman, Alfons ; van de Pol, Jan Cornelis. / Variations on Multi-Core Nested Depth-First Search. Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011. editor / J. Barnat ; K. Heljanko. USA : EPTCS, 2011. pp. 13-28 (Electronic Proceedings in Theoretical Computer Science).
    @inproceedings{7bbf3fd4d5f74a0fa953579363a8d778,
    title = "Variations on Multi-Core Nested Depth-First Search",
    abstract = "Recently, two new parallel algorithms for on-the-fly model checking of LTL properties were presented at the same conference: Automated Technology for Verification and Analysis, 2011. Both approaches extend Swarmed NDFS, which runs several sequential NDFS instances in parallel. While parallel random search already speeds up detection of bugs, the workers must share some global information in order to speed up full verification of correct models. The two algorithms differ considerably in the global information shared between workers, and in the way they synchronize. Here, we provide a thorough experimental comparison between the two algorithms, by measuring the runtime of their implementations on a multi-core machine. Both algorithms were implemented in the same framework of the model checker LTSmin, using similar optimizations, and have been subjected to the full BEEM model database. Because both algorithms have complementary advantages, we constructed an algorithm that combines both ideas. This combination clearly has an improved speedup. We also compare the results with the alternative parallel algorithm for accepting cycle detection OWCTY-MAP. Finally, we study a simple statistical model for input models that do contain accepting cycles. The goal is to distinguish the speedup due to parallel random search from the speedup that can be attributed to clever work sharing schemes.",
    keywords = "IR-78261, METIS-278846, Parallel, LTL model checking, EWI-20618, Multi-Core, depth first search, swarmed, Nested DFS",
    author = "Alfons Laarman and {van de Pol}, {Jan Cornelis}",
    year = "2011",
    month = "7",
    day = "14",
    doi = "10.4204/EPTCS.72.2",
    language = "English",
    series = "Electronic Proceedings in Theoretical Computer Science",
    publisher = "EPTCS",
    pages = "13--28",
    editor = "J. Barnat and K. Heljanko",
    booktitle = "Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011",

    }

    Laarman, A & van de Pol, JC 2011, Variations on Multi-Core Nested Depth-First Search. in J Barnat & K Heljanko (eds), Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011. Electronic Proceedings in Theoretical Computer Science, vol. 72, EPTCS, USA, pp. 13-28, 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011, Snowbird, United States, 14/07/11. https://doi.org/10.4204/EPTCS.72.2

    Variations on Multi-Core Nested Depth-First Search. / Laarman, Alfons; van de Pol, Jan Cornelis.

    Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011. ed. / J. Barnat; K. Heljanko. USA : EPTCS, 2011. p. 13-28 (Electronic Proceedings in Theoretical Computer Science; Vol. 72).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

    TY - GEN

    T1 - Variations on Multi-Core Nested Depth-First Search

    AU - Laarman, Alfons

    AU - van de Pol, Jan Cornelis

    PY - 2011/7/14

    Y1 - 2011/7/14

    N2 - Recently, two new parallel algorithms for on-the-fly model checking of LTL properties were presented at the same conference: Automated Technology for Verification and Analysis, 2011. Both approaches extend Swarmed NDFS, which runs several sequential NDFS instances in parallel. While parallel random search already speeds up detection of bugs, the workers must share some global information in order to speed up full verification of correct models. The two algorithms differ considerably in the global information shared between workers, and in the way they synchronize. Here, we provide a thorough experimental comparison between the two algorithms, by measuring the runtime of their implementations on a multi-core machine. Both algorithms were implemented in the same framework of the model checker LTSmin, using similar optimizations, and have been subjected to the full BEEM model database. Because both algorithms have complementary advantages, we constructed an algorithm that combines both ideas. This combination clearly has an improved speedup. We also compare the results with the alternative parallel algorithm for accepting cycle detection OWCTY-MAP. Finally, we study a simple statistical model for input models that do contain accepting cycles. The goal is to distinguish the speedup due to parallel random search from the speedup that can be attributed to clever work sharing schemes.

    AB - Recently, two new parallel algorithms for on-the-fly model checking of LTL properties were presented at the same conference: Automated Technology for Verification and Analysis, 2011. Both approaches extend Swarmed NDFS, which runs several sequential NDFS instances in parallel. While parallel random search already speeds up detection of bugs, the workers must share some global information in order to speed up full verification of correct models. The two algorithms differ considerably in the global information shared between workers, and in the way they synchronize. Here, we provide a thorough experimental comparison between the two algorithms, by measuring the runtime of their implementations on a multi-core machine. Both algorithms were implemented in the same framework of the model checker LTSmin, using similar optimizations, and have been subjected to the full BEEM model database. Because both algorithms have complementary advantages, we constructed an algorithm that combines both ideas. This combination clearly has an improved speedup. We also compare the results with the alternative parallel algorithm for accepting cycle detection OWCTY-MAP. Finally, we study a simple statistical model for input models that do contain accepting cycles. The goal is to distinguish the speedup due to parallel random search from the speedup that can be attributed to clever work sharing schemes.

    KW - IR-78261

    KW - METIS-278846

    KW - Parallel

    KW - LTL model checking

    KW - EWI-20618

    KW - Multi-Core

    KW - depth first search

    KW - swarmed

    KW - Nested DFS

    U2 - 10.4204/EPTCS.72.2

    DO - 10.4204/EPTCS.72.2

    M3 - Conference contribution

    T3 - Electronic Proceedings in Theoretical Computer Science

    SP - 13

    EP - 28

    BT - Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011

    A2 - Barnat, J.

    A2 - Heljanko, K.

    PB - EPTCS

    CY - USA

    ER -

    Laarman A, van de Pol JC. Variations on Multi-Core Nested Depth-First Search. In Barnat J, Heljanko K, editors, Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011. USA: EPTCS. 2011. p. 13-28. (Electronic Proceedings in Theoretical Computer Science). https://doi.org/10.4204/EPTCS.72.2