並列分枝限定法と動的探索木分割によるクラスタシステム向き最適順序付けアルゴリズム

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: 並列分枝限定法と動的探索木分割によるクラスタシステム向き最適順序付けアルゴリズム
• タイトル / 言語: en
• タイトル: Optimum Ordering Algorithm Suitable for Cluster System Based on Parallel Branch and Bound Method and Dynamic Division of Search Tree
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 京都産業大学
• 著者所属(英): en
• 著者所属(英): Kyoto Sangyo University
• 著者名: 平石, 裕実
• 著者名(英): Hiromi, Hiraishi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Task Control Architecture（TCA）と呼ばれるロボット制御プログラムの開発法において，開発したプログラムがデッドロックに陥らないことを検証する際に，複数のプログラムモジュール間に適切な順序付けを与えると検証時間を大幅に短縮できる．本稿ではそのような順序付けを求めるための並列アルゴリズムを提案する．本アルゴリズムは，クラスタマシン上での実行を前提としており，最適な順序付けを探索する際に，並列分枝限定法を用いる．さらに，探索過程において，探索木を動的に分割しながらクラスタマシンの各ノードに部分探索問題を割り当てることにより，各ノードの計算負荷をバランスさせている．実験の結果，91 並列で236 倍の高速化を達成することができ，提案アルゴリズムがきわめて有効であることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In verification of deadlock-free property of robot control programs using TCA (Task Control Architecture), it is possible to improve verification time drastically by giving a good total order over program modules. In this paper, we propose a parallel algorithm to obtain such a good ordering. The algorithm is suitable for execution on cluster machines. It searches an optimal ordering by parallel branch and bound method. In addition, it creates partial search problems by dividing its search tree dynamically and assigns them to each node of a cluster machine in order to obtain good load balance. Experimental results show that we can obtain 236 times speed up by using 91 nodes and the proposed algorithm is very effective.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 46, 号 SIG12(ACS11), p. 330-337, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会