木構造型ネットワークにおける最適Broadcastスケジューリング(HPC-4 : ネットワーク)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))

スポンサーリンク

概要

論文の詳細を見る
集合通信のスケジューリングは、通信時間を大きく左右する。今回、我々は、その影響が大きいと考えられる木構造におけるBroadcastの最適スケジューリングを考える。この問題は、並列計算に限らず、大規模データベースのミラーリング等にも関連し、幅広い研究がある。しかし、従来の研究では、ネットワークを抽象化したりスイッチや不均一なネットワークなどのより現実的なモデルを避けていた。本研究では、このような不均一なネットワークも考慮した場合、NP困難な問題になることを示し、最適解の探索に深さ優先探索による分枝限定法を用いた方法を提案する。その際、木構造の対称性からくる冗長性を高速な木の同型判定アルゴリズムにより省く手法を紹介し、その有効性を検証する。また実機によるテストを行いBroadcastの実行時間が大幅に削減される場合があることを示す。
一般社団法人情報処理学会の論文
2003-08-04

著者

関連論文

もっと見る

スポンサーリンク