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

Autor:	Yuu Jinnai, Alex Fukunaga
Rok vydání:	2016
Předmět:	General Medicine
Zdroj:	Proceedings of the AAAI Conference on Artificial Intelligence. 30
ISSN:	2374-3468 2159-5399
DOI:	10.1609/aaai.v30i1.10065
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b7b5d1f0a78556aa4db895d2068961fc https://doi.org/10.1609/aaai.v30i1.10065 Zobrazit plný text záznamu