Dartmouth College Computer Science
Technical Report series
TR search TR listserv
|By author:||A B C D E F G H I J K L M N O P Q R S T U V W X Y Z|
|By number:||2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986|
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
Submitted to Journal of Parallel and Distributed Computing.
Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]
Or copy and paste:
David M. Nicol and Gianfranco F. Ciardo, "Automated Parallelization of Discrete State-space Generation." Dartmouth Computer Science Technical Report PCS-TR97-304, January 1997.
Notify me about new tech reports.
Search the technical reports.
To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu
Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Technical reports collection maintained by David Kotz.