On the Scaling Behavior of HDA*

Abstract

HDA* is a simple, parallelization of A* where work is asynchronously distributed among the nodes by a global hash function. Using up to 1024 cores on a large distributed memory cluster, we evaluate HDA* for a domain-independent planner as well an application-specific 24-puzzle solver. We show that HDA* scales fairly well on a large cluster using up to 1024 cores. Our analysis of the scaling behavior shows that on a cluster of multicore nodes, using only a subset of the available cores and leaving some cores idle can, surprisingly, lead to better results.