Automated parallelization of discrete state-space generation

David M. Nicol, Gianfranco Ciardo

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of generating a large state-space in a distributed fashion. Unlike previously proposed solutions that partition the set of reachable states according to a hashing function provided by the user, we explore heuristic methods that completely automate the process. The first step is an initial random walk through the state space to initialize a search tree, duplicated in each processor. Then, the reachability graph is built in a distributed way, using the search tree to assign each newly found state to classes assigned to the available processors. Furthermore, we explore two remapping criteria that attempt to balance memory usage or future workload, respectively. We show how the cost of computing the global snapshot required for remapping will scale up for system sizes in the foreseeable future. An extensive set of results is presented to support our conclusions that remapping is extremely beneficial.

Original languageEnglish (US)
Pages (from-to)153-167
Number of pages15
JournalJournal of Parallel and Distributed Computing
Volume47
Issue number2
DOIs
StatePublished - Dec 15 1997
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Automated parallelization of discrete state-space generation'. Together they form a unique fingerprint.

Cite this