著者

蓬来祐一郎 西田 晃 小柳 義夫

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.45, no.SIG03(ACS5), pp.100-108, 2004-03-15

---

集合通信のスケジューリングは,通信時間を大きく左右する.従来の研究ではネットワークを抽象化し,ハブや不均一なネットワークなどのより現実的なモデルを避けていた.しかし,グリッドコンピューティングへの関心や分散データベースなどの需要の増加とともにこの問題の重要性が増してきている.そこで本研究において,スケジューリングの影響が大きいと考えられる木構造におけるブロードキャストの最適スケジューリングを考える.まず,不均一なネットワークを考慮した場合,NP困難な問題になることを示し,最適解の探索に深さ優先探索による分枝限定法を用いた方法を提案する.その際,木構造の対称性からくる冗長性を高速な木の同型判定アルゴリズムにより省く手法を紹介し,その有効性を示す.また実機によるテストを行い,汎用的なMPI実装のブロードキャスト関数MPI Bcastと比較し,ブロードキャストの実行時間が大幅に削減される場合があることを示す.