---
title: "Evaluations of Hash Distributed A* in Optimal Sequence Alignment"
authors:
  - "Yoshikazu Kobayashi"
  - "Akihiro Kishimoto"
  - "Osamu Watanabe"
doi: "10.5591/978-1-57735-516-8/IJCAI11-105"
url: "https://ijcai.org/proceedings/2011/105"
pdf: "https://ijcai.org/proceedings/2011/0105.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "584-589"
track: ""
keywords:
---

# Evaluations of Hash Distributed A* in Optimal Sequence Alignment

Yoshikazu Kobayashi, Akihiro Kishimoto, Osamu Watanabe

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 584-589. DOI: [10.5591/978-1-57735-516-8/IJCAI11-105](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.