超平面ハッシュ関数に基づく分散A^* アルゴリズムの提案と多重配列アラインメント問題への応用

• Item type: SIG Technical Reports(1)
• 公開日: 2011-05-09
• タイトル: 超平面ハッシュ関数に基づく分散A^* アルゴリズムの提案と多重配列アラインメント問題への応用
• タイトル / 言語: en
• タイトル: A Distributed A^* Algorithm Based on the Hyperplane Function and Its Application to Multiple Sequence Alignment
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻
• 著者所属: 東京工業大学大学院情報理工学研究科数理・計算科学専攻
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Sciences, Graduate School of Information Science and Engineering, Tokyo Institute of Technology
• 著者名: 小林, 義和; 岸本, 章宏; 渡辺, 治
• 著者名(英): Yoshikazu, Kobayashi; Akihiro, Kishimoto; Osamu, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散メモリ環境での A* アルゴリズムの並列化は，アルゴリズムの解答速度および解答能力向上のために重要な課題である．本論文では，単純であるが効果的な A* の並列化である Hash Distributed A*(HDA*) アルゴリズム上に超平面ハッシュ関数を利用し仕事を分配する方法を提案する．この仕事分配方法の性能を，マルチコア CPU を持つマシンで構成される PC クラスター上で，最適多重配列アラインメントの難しいベンチマーク問題を解かせることで評価し，この手法でベンチマーク問題に対しては，384CPU コアまで高い台数効果を達成すること示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Parallelizing the A* algorithm in distributed memory environments plays an important role in both achieving speedups and improving its solving ability. This paper presents a new work distribution strategy based on the hyperplane function, which is combined with simple but scalable parallel A* called Hash Distributed A*. The performance was evaluated on a cluster of multi-core machines and the presented strategy was shown to scale well up to 384 cores in solving difficult instances of the optimal multiple sequence alignment.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-135, 号 2, p. 1-8, 発行日 2011-05-09
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会