Suchergebnisse

In this thesis, we propose and study new algorithms and data structures for model checking nite-state, concurrent systems. We focus on techniques that target shared memory, multi-cores architectures, that are a current trend in computer architectures. In this context, we present new algorithms and data structures for exhaustive parallel model checking that are as effi cient as possible, but also "friendly" with respect to the work-sharing policies that are used for the state space generation (e.g. a work-stealing strategy): at no point do we impose a restriction on the way work is shared among the processors. This includes both the construction of the state space as the detection of cycles in parallel, which is one of the key points of performance for the evaluation of more complex formulas. Alongside the defi nition of enumerative, model checking algorithms for manycores architectures, we also study probabilistic verifi cation algorithms. By the term probabilistic, we mean that, during the exploration of a system, any given reachable state has a high probability of being checked by the algorithm. Probabilistic veri fication trades savings at the level of memory usage for the probability of missing some states. Consequently, it becomes possible to analyze part of the state space of a system when there is not enough memory available to represent the entire state space in an exact manner. ; Nous proposons de nouveaux algorithmes et de nouvelles structures de données pour la vérifi cation formelle de systèmes réactifs nis sur architectures parallèles. Ces travaux se basent sur les techniques de véri cation par model checking. Notre approche cible des architectures multi-processeurs et multi-coeurs, avec mémoire partagée, qui correspondent aux générations de serveurs les plus performants disponibles actuellement. Dans ce contexte, notre objectif principal est de proposer des approches qui soient à la fois effi caces au niveau des performances, mais aussi compatibles avec les politiques de partage dynamique du ...

In this thesis, we propose and study new algorithms and data structures for model checking nite-state, concurrent systems. We focus on techniques that target shared memory, multi-cores architectures, that are a current trend in computer architectures. In this context, we present new algorithms and data structures for exhaustive parallel model checking that are as effi cient as possible, but also "friendly" with respect to the work-sharing policies that are used for the state space generation (e.g. a work-stealing strategy): at no point do we impose a restriction on the way work is shared among the processors. This includes both the construction of the state space as the detection of cycles in parallel, which is one of the key points of performance for the evaluation of more complex formulas. Alongside the defi nition of enumerative, model checking algorithms for manycores architectures, we also study probabilistic verifi cation algorithms. By the term probabilistic, we mean that, during the exploration of a system, any given reachable state has a high probability of being checked by the algorithm. Probabilistic veri fication trades savings at the level of memory usage for the probability of missing some states. Consequently, it becomes possible to analyze part of the state space of a system when there is not enough memory available to represent the entire state space in an exact manner. ; Nous proposons de nouveaux algorithmes et de nouvelles structures de données pour la vérifi cation formelle de systèmes réactifs nis sur architectures parallèles. Ces travaux se basent sur les techniques de véri cation par model checking. Notre approche cible des architectures multi-processeurs et multi-coeurs, avec mémoire partagée, qui correspondent aux générations de serveurs les plus performants disponibles actuellement. Dans ce contexte, notre objectif principal est de proposer des approches qui soient à la fois effi caces au niveau des performances, mais aussi compatibles avec les politiques de partage dynamique du ...

In this thesis, we propose and study new algorithms and data structures for model checking nite-state, concurrent systems. We focus on techniques that target shared memory, multi-cores architectures, that are a current trend in computer architectures. In this context, we present new algorithms and data structures for exhaustive parallel model checking that are as effi cient as possible, but also "friendly" with respect to the work-sharing policies that are used for the state space generation (e.g. a work-stealing strategy): at no point do we impose a restriction on the way work is shared among the processors. This includes both the construction of the state space as the detection of cycles in parallel, which is one of the key points of performance for the evaluation of more complex formulas. Alongside the defi nition of enumerative, model checking algorithms for manycores architectures, we also study probabilistic verifi cation algorithms. By the term probabilistic, we mean that, during the exploration of a system, any given reachable state has a high probability of being checked by the algorithm. Probabilistic veri fication trades savings at the level of memory usage for the probability of missing some states. Consequently, it becomes possible to analyze part of the state space of a system when there is not enough memory available to represent the entire state space in an exact manner. ; Nous proposons de nouveaux algorithmes et de nouvelles structures de données pour la vérifi cation formelle de systèmes réactifs nis sur architectures parallèles. Ces travaux se basent sur les techniques de véri cation par model checking. Notre approche cible des architectures multi-processeurs et multi-coeurs, avec mémoire partagée, qui correspondent aux générations de serveurs les plus performants disponibles actuellement. Dans ce contexte, notre objectif principal est de proposer des approches qui soient à la fois effi caces au niveau des performances, mais aussi compatibles avec les politiques de partage dynamique du ...