並列分散システムにおけるデータ配信アルゴリズム

摘要

Parallel distributed systems are studied by many researchers. There are many important problems in parallel distributed systems. We consider a problem called broadcast scheduling. In case of one to one communication, the broadcast scheduling is studied as Minimum Broadcast Time Problem to find the shortest schedule. Previous studies pay attention to network topology or the complexity of problems. And there are few studies for wide area parallel distributed systems. In this paper, we study broadcast scheduling for wide area parallel distributed systems.%近年，クラスタシステムなどの並列分散システムに関する研究，および開発が盛んである．複数の並列分散システムをWANなどで結合した広域の並列分散システムも研究されるようになってきた．並列分散システムの重要な処理の1つにブロードキャストがある．ブロードキャストとは，システムを構成する全ノードにデータを配信する処理である．ここでは，データの配信の仕方をブロードキャストスケジュールと呼ぶことにする．ブロードキャストスケジュールには数多くのパターンが存在するが，高性能なシステムにおいては短時間で完了するスケジュールが望まれる．1対1通信を仮定した場合，完了までの時間が最短のスケジュールを見つける問題は，最小ブロードキャスト時間問題（Minimum Broadcast Time Problem：MBT），またはブロードキャストスケジューリングとして知られ，これまでに数多く研究されてきた．この問題に対する従来の研究は，ネットワークトポロジと問題の複雑さとの関係について議論するか，実際のクラスタへの適用を想定してトポロジが完全グラフのシステムを対象とするものが多く，複数のクラスタを結合した広域並列分散システムを対象としたものはあまり多くない．ここでは複数のクラスタを結合した広域並列分散システムに対するブロードキャストスケジューリングを検討する．