Distributed graph-based state space generation

Share/Save/Bookmark

Blom, Stefan and Kant, Gijs and Rensink, Arend (2010) Distributed graph-based state space generation. Electronic Communications of the EASST, 32 . ISSN 1863-2122

[img]
Preview
PDF
304Kb
Abstract:LTSMIN provides a framework in which state space generation can be distributed easily over many cores on a single compute node, as well as over multiple compute nodes. The tool works on the basis of a vector representation of the states; the individual cores are assigned the task of computing all successors of states that are sent to them. In this paper we show how this framework can be applied in the case where states are essentially graphs interpreted up to isomorphism, such as the ones we have been studying for GROOVE. This involves developing a suitable vector representation for a canonical form of those graphs. The canonical forms are computed using a third tool called BLISS. We combined the three tools to form a system for distributed state space generation based on graph grammars. We show that the time performance of the resulting system scales well (i.e., close to linear) with the number of cores. We also report surprising statistics on the memory
consumption, which imply that the vector representation used to store graphs in LTSMIN is more compact than the representation used in GROOVE.
Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/75906
Official URL:http://journal.ub.tu-berlin.de/eceasst/article/view/521
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 275864