木構造型ネットワークにおける最適ブロードキャストスケジューリング

• Item type: Trans(1)
• 公開日: 2004-03-15
• タイトル: 木構造型ネットワークにおける最適ブロードキャストスケジューリング
• タイトル / 言語: en
• タイトル: Optimal Broadcast Scheduling on Tree - structured Networks
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列・分散システム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京大学大学院情報理工学系研究科／科学技術振興機構CREST
• 著者所属: 東京大学大学院情報理工学系研究科／科学技術振興機構CREST
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Tokyo/CREST, Japan Science and Technology Agency
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Tokyo/CREST, Japan Science and Technology Agency
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, The University of Tokyo
• 著者名: 蓬来祐一郎; 西田, 晃; 小柳, 義夫
• 著者名(英): Yuichiro, Hourai; Akira, Nishida; Yoshio, Oyanagi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 集合通信のスケジューリングは，通信時間を大きく左右する．従来の研究ではネットワークを抽象化し，ハブや不均一なネットワークなどのより現実的なモデルを避けていた．しかし，グリッドコンピューティングへの関心や分散データベースなどの需要の増加とともにこの問題の重要性が増してきている．そこで本研究において，スケジューリングの影響が大きいと考えられる木構造におけるブロードキャストの最適スケジューリングを考える．まず，不均一なネットワークを考慮した場合，NP困難な問題になることを示し，最適解の探索に深さ優先探索による分枝限定法を用いた方法を提案する．その際，木構造の対称性からくる冗長性を高速な木の同型判定アルゴリズムにより省く手法を紹介し，その有効性を示す．また実機によるテストを行い，汎用的なMPI実装のブロードキャスト関数MPI Bcastと比較し，ブロードキャストの実行時間が大幅に削減される場合があることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The communication time of a group communication on a specific network depends on the scheduling of communications. Schedules should be suited to network structures. Conventional researches have assumed symmetric and uniform networks, and have neglected some practical network properties. However, heterogeneity of networks exists almost everywhere, and recent growth of grid computing increases the importance of this challenging task. In this research, we focus our attention on broadcast scheduling on networks of tree topology by one-to-one communications. Since trees have no multiple paths between any two nodes and multiple communication pairs can share a communication line, the broadcast time is sensitive on schedules. First, we propose a network and communication model and show the computational complexity of broadcast scheduling. Then, we propose an efficient algorithm to solve this hard problem by the depth-first branch-and-bound algorithm with the use of a fast tree isomorphism determination algorithm. Our experiments show the efficiency and effectiveness of our algorithm. We also show that the communication times of the optimized broadcast are greatly superior to built-in MPI Bcast in some cases.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 45, 号 SIG03(ACS5), p. 100-108, 発行日 2004-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会