The A* algorithm is generally used to solve combinatorial optimization problems, but it requires high computing power and a large amount of memory, hence, efficient parallel A* algorithms are needed. In this sense, Ha...
详细信息
ISBN:
(纸本)9783319495835;9783319495828
The A* algorithm is generally used to solve combinatorial optimization problems, but it requires high computing power and a large amount of memory, hence, efficient parallel A* algorithms are needed. In this sense, hash Distributed A* (HDA*) parallelizes A* by applying a decentralized strategy and a hash-based node distribution scheme. However, this distributionscheme results in frequent node transfers among processors. In this paper, we present Optimized AHDA*, a version of HDA* for shared memory architectures, that uses an abstraction-basednodedistributionscheme and a technique to group several nodes before transferring them to the corresponding thread. Both methods reduce the amount of node transfers and mitigate communication and contention. We assess the effect of each technique on algorithm performance. Finally, we evaluate the scalability of the proposed algorithm, when it is run on a multicore machine, using the 15-puzzle as a case study.
暂无评论