|
複数の要素プロセッサ上に分散している情報をどのようにして共有するかという問題は、共有メモリをもたない並列・分散システムにおける本質的な問題のひとつである。この問題は通常、放送(broadcast)やゴシップ(gossip)に代表されるような"情報散布問題"として一般に定式化される。情報散布問題は、並列計算機に実装されることによってアルゴリズムの善し悪しがその性能に直ちに反映されるという現実的な側面をもつ一方で、グラフの埋め込み問題や資源のスケジューリング問題などといった理論的な諸問題とも関わり合いをもっている。またラウティングテーブルのサイズを小さくするためのcompact routing法や耐故障性のある情報散布に関する考察、さらには通信技術の進歩に伴って実用化されつつあるcut-through routingやATMなどの新しい情報転送モデル上でのアルゴリズムの開発など、この分野の研究は、近年特に幅広い展開を見せている。本講演では、この分野における過去の研究の流れと最近の動向について概説した後、講演者の最近の成果として、1)ハイパーキューブにおける回路交換モデル上での最適なゴシップアルゴリズム2)バスネットワーク上でのゴシップアルゴリズム3)ハイパーキューブ上でのall-portモデルのsingle-portモデルによる効率のよいシミュレーション方法などについて述べる。
|
