TY - JOUR
T1 - Automated parallelization of discrete state-space generation
AU - Nicol, David M.
AU - Ciardo, Gianfranco
N1 - Funding Information:
1This work was supported in part by NSF Grants CCR-9201195, NCR-9527163, CCR-9625894, in part by a subcontract on the Grant 96-SC-NSF-1011 to the Center for Advanced Computing and Communication, and in part by NASA Contract S1-19480 to the Institute for Computer Applications in Science and Engineering.
PY - 1997/12/15
Y1 - 1997/12/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031574534&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031574534&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1997.1409
DO - 10.1006/jpdc.1997.1409
M3 - Article
AN - SCOPUS:0031574534
SN - 0743-7315
VL - 47
SP - 153
EP - 167
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 2
ER -