On Hash-Based Work Distribution Methods for Parallel Best-First Search
원문 초록
Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
PGT-I: Scaling Spatiotemporal GNNs with Memory-Efficient Distributed Training
Demystifying Distributed Training of Graph Neural Networks for Link Prediction
DistMLIP: A Distributed Inference Platform for Machine Learning Interatomic Potentials
Hierarchical Superpixel Segmentation via Structural Information Theory
FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning
Towards the efficacy of federated prediction for epidemics on networks
토론
이 논문과 연결된 포럼 글이 아직 없습니다.