@article{oai:ipsj.ixsq.nii.ac.jp:00018512,
 author = {蓬来祐一郎 and 西田, 晃 and 小柳, 義夫 and Yuichiro, Hourai and Akira, Nishida and Yoshio, Oyanagi},
 issue = {SIG03(ACS5)},
 journal = {情報処理学会論文誌コンピューティングシステム（ACS）},
 month = {Mar},
 note = {集合通信のスケジューリングは，通信時間を大きく左右する．従来の研究ではネットワークを抽象化し，ハブや不均一なネットワークなどのより現実的なモデルを避けていた．しかし，グリッドコンピューティングへの関心や分散データベースなどの需要の増加とともにこの問題の重要性が増してきている．そこで本研究において，スケジューリングの影響が大きいと考えられる木構造におけるブロードキャストの最適スケジューリングを考える．まず，不均一なネットワークを考慮した場合，NP困難な問題になることを示し，最適解の探索に深さ優先探索による分枝限定法を用いた方法を提案する．その際，木構造の対称性からくる冗長性を高速な木の同型判定アルゴリズムにより省く手法を紹介し，その有効性を示す．また実機によるテストを行い，汎用的なMPI実装のブロードキャスト関数MPI Bcastと比較し，ブロードキャストの実行時間が大幅に削減される場合があることを示す．, 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.},
 pages = {100--108},
 title = {木構造型ネットワークにおける最適ブロードキャストスケジューリング},
 volume = {45},
 year = {2004}
}