### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011 |

Editors | J. Barnat, K. Heljanko |

Place of Publication | USA |

Publisher | EPTCS |

Pages | 13-28 |

Number of pages | 16 |

DOIs | |

State | Published - 14 Jul 2011 |

Event | 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011 - Snowbird, United States |

### Publication series

Name | Electronic Proceedings in Theoretical Computer Science |
---|---|

Publisher | EPTCS |

Volume | 72 |

ISSN (Print) | 2075-2180 |

ISSN (Electronic) | 2075-2180 |

### Workshop

Workshop | 10th International Workshop on Parallel and Distributed Methods in verifiCation, PDMC 2011 |
---|---|

Abbreviated title | PDMC |

Country | United States |

City | Snowbird |

Period | 14/07/11 → 14/07/11 |

Internet address |

### Fingerprint

### Keywords

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

### Cite this

*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. DOI: 10.4204/EPTCS.72.2

}

*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-14 July. DOI: 10.4204/EPTCS.72.2

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

Research output: Scientific › Conference contribution

TY - CHAP

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

PB - EPTCS

ER -