Evaluations of Hash Distributed A* in Optimal Sequence Alignment

Kobayashi, Yoshikazu; Kishimoto, Akihiro; Watanabe, Osamu

doi:10.5591/978-1-57735-516-8/IJCAI11-105

Evaluations of Hash Distributed A* in Optimal Sequence Alignment

Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 584-589.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-105

Abstract

Hash Distributed A* (HDA*) is a parallel A* algorithm that is proven to be effective in optimal sequential planning with unit edge costs. HDA* leverages the Zobrist function to almost uniformly distribute and schedule work among processors. This paper evaluates the performance of HDA* in optimal sequence alignment. We observe that with a large number of CPU cores HDA* suffers from an increase of search overhead caused by reexpansions of states in the closed list due to nonuniform edge costs in this domain. We therefore present a new work distribution strategy limiting processors to distribute work, thus increasing the possibility of detecting such duplicate search effort. We evaluate the performance of this approach on a cluster of multi-core machines and show that the approach scales well up to 384 CPU cores.

Yoshikazu Kobayashi, Akihiro Kishimoto, and Osamu Watanabe. 2011. Evaluations of Hash Distributed A* in Optimal Sequence Alignment. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 584–589. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-105

@inproceedings{ijcai2011p105,
  title     = {Evaluations of Hash Distributed A* in Optimal Sequence Alignment},
  author    = {Kobayashi, Yoshikazu and Kishimoto, Akihiro and Watanabe, Osamu},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {584--589},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-105},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-105},
}

TY  - CPAPER
TI  - Evaluations of Hash Distributed A* in Optimal Sequence Alignment
AU  - Kobayashi, Yoshikazu
AU  - Kishimoto, Akihiro
AU  - Watanabe, Osamu
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 584
EP  - 589
DO  - 10.5591/978-1-57735-516-8/IJCAI11-105
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-105
ER  -