Automated Creation of Efficient Work Distribution Functions for Parallel Best-First Search. Jinnai, Y. & Fukunaga, A. In
Automated Creation of Efficient Work Distribution Functions for Parallel Best-First Search [link]Paper  abstract   bibtex   
Hash Distributed A* (HDA*) is an efficient parallel best first algorithm that asynchronously distributes work among the processes using a global hash function. We investigate domain-independent methods for automatically creating effective work distribution functions for HDA*. First, we propose a new method for generating abstract features for the recently proposed abstract Zobrist hashing method. Second, we propose a method for modifying Zobrist hashing such that selected operators are guaranteed to generate children that are mapped to the same process as the parent, ensuring that no communications overhead is incurred for such operators. Finally, we present an improvement to state-abstraction based HDA* which dynamically selects the abstraction graph size based on problem features. We evaluate these new work distribution methods for a domain-independent planner on a cluster with 48 cores and show that these methods result in signficantly higher speedups than previous methods.
@inproceedings {icaps16-28,
    track    = {​Main Track},
    title    = {Automated Creation of Efficient Work Distribution Functions for Parallel Best-First Search},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13081},
    author   = {Yuu Jinnai and  Alex Fukunaga},
    abstract = {Hash Distributed A* (HDA*) is an efficient parallel best first algorithm that asynchronously distributes work among the processes using a global hash function.
We investigate domain-independent methods for automatically creating effective work distribution functions for HDA*. 
First, we propose a new method for generating abstract features for the recently proposed abstract Zobrist hashing method.
Second, we propose a method for modifying Zobrist hashing such that selected operators are guaranteed to generate children that are mapped to the same process as the parent, ensuring that no communications overhead is incurred for such operators.
Finally, we present an improvement to state-abstraction based HDA* which dynamically selects the abstraction graph size based on problem features.
We evaluate these new work distribution methods for a domain-independent planner on a cluster with 48 cores and show that these methods result in signficantly higher speedups than previous methods.},
    keywords = {Classical planning,Search techniques}
}

Downloads: 0