Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search

AAAI 2016 pp. 717-723

doi:10.1609/AAAI.V30I1.10065 /aaai/2016/jinnai2016aaai-abstract/

Abstract

Hash Distributed A* (HDA*) is an efficient parallel best first algorithm that asynchronously distributes work among the processes using a global hash function. Although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since it requires many node transfers among threads. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which reduces node transfers and mitigates communication overhead by using feature projection functions. We evaluate Abstract Zobrist hashing for multicore HDA*, and show that it significantly outperforms previous work distribution methods.

PDF AAAI Semantic Scholar

Cite

Text

Jinnai and Fukunaga. "Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10065

Markdown

[Jinnai and Fukunaga. "Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/jinnai2016aaai-abstract/) doi:10.1609/AAAI.V30I1.10065

BibTeX

@inproceedings{jinnai2016aaai-abstract,
  title     = {{Abstract Zobrist Hashing: An Efficient Work Distribution Method for Parallel Best-First Search}},
  author    = {Jinnai, Yuu and Fukunaga, Alex},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2016},
  pages     = {717-723},
  doi       = {10.1609/AAAI.V30I1.10065},
  url       = {https://mlanthology.org/aaai/2016/jinnai2016aaai-abstract/}
}