Shared Hash Tables in Parallel Model Checking

BARNAT, Jiří and Petr ROČKAI. Shared Hash Tables in Parallel Model Checking. Online. Electronic Notes in Theoretical Computer Science. Elsevier, 2008, vol. 2008, 198(1), p. 79-91, 12 pp. ISSN 1571-0661. [citováno 2024-04-23]

Basic information

• Original name: Shared Hash Tables in Parallel Model Checking
• Name in Czech: Sdílené hašovací tabulky v paralelním model checkingu
• Authors: BARNAT, Jiří (203 Czech Republic, guarantor) and Petr ROČKAI (203 Czech Republic)
• Edition: Electronic Notes in Theoretical Computer Science, Elsevier, 2008, 1571-0661.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Germany
• Confidentiality degree: is not subject to a state or trade secret
• RIV identification code: RIV/00216224:14330/08:00024166
• Organization unit: Faculty of Informatics
• Keywords in English: Hash tables; locking schemes; parallel
• Tags: Hash tables, locking schemes, parallel
• Tags: International impact, Reviewed

Abstract

In light of recent shift towards shared-memory systems in parallel explicit model checking, we explore relative advantages and disadvantages of shared versus private hash tables. Since usage of shared state storage allows for techniques unavailable in distributed memory, these are evaluated, both theoretically and practically, in a prototype implementation. Experimental data is presented to assess practical utility of those techniques, compared to static partitioning of state space, more traditional in distributed memory algorithms.

Abstract (in Czech)

Vzhledem k výraznému posunu výzkumu v paralelním explicitním model checkingu směrem k platformám se sdílenou pamětí je smyslem článku prozkoumat a vyhodnotit výhody a nevýhody přístupů implementace algoritmů se sdílenou a privátní hašovací tabulkou. Přístupy jsou vyhodnoceny jak po teoretické stránce, tak i prakticky s využitím prototypové implementace. Experimentální data jsou prezentována a porovnána s statickým dělením práce typickým pro algoritmy pracující s distribuovanou pamětí.

Links

• GA201/06/1338, research and development project: Name: Automatizovaná verifikace softwaru

Investor: Czech Science Foundation, Automated software verification

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

• 1ET408050503, research and development project: Name: Techniky automatické verifikace a validace softwarových a hardwarových systémů

Investor: Academy of Sciences of the Czech Republic, Techniques for automatic verification and validation of software nad hardware systems

• 1M0545, research and development project: Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science