Mixed Shared-Distributed Hash Tables Approaches for Parallel State Space ConstructionReportar como inadecuado




Mixed Shared-Distributed Hash Tables Approaches for Parallel State Space Construction - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LAAS - Laboratoire d-analyse et d-architecture des systèmes Toulouse

Abstract : We propose an algorithm for parallel state space construction based on an original concurrent data structure, called a localization table, that aims at better spatial and temporal balance. Our proposal is close in spirit to algorithms based on distributed hash tables, with the distinction that states are dynamically assigned to processors; i.e. we do not rely on an a-priori static partition of the state space. In our solution, every process keeps a share of the global state space. Data distribution and coordination between processes is made through the localization table, that is a lockless, thread-safe data structure that approximates the set of states being processed. The localization table is used to dynamically assign newly discovered states and can be queried to return the identity of the processor that own a given state. With this approach, we are able to consolidate a network of local hash tables into an abstract distributed one without sacrificing memory affinity - data that are -logically connected- and physically close to each others - and without incurring performance costs associated to the use of locks to ensure data consistency. We evaluate the performance of our algorithm on different benchmarks and compare these results with other solutions proposed in the literature and with existing verification tools.

Keywords : Parallel State Space Construction Model Checking Parallel Algorithm Lock-Free Dictionary





Autor: Rodrigo Saad - Silvano Dal Zilio - Bernard Berthomieu -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados