最大値問題に対するメッシュバス上でのO((log log n)^2)アルゴリズム

情報処理学会

書誌事項

タイトル別名
  • An O((log log n)^2) Mesh-Bus Algorithm for Finding the Maximum

この論文をさがす

抄録

メツシユバス計算機(MBUS)は,メッシュ計算機(MC)の局所通信機能をバスによるグローバル通信機能に置き換えた並列モデルである.その物理的実現性はMCに比べてそれほど劣らないと考えられ,上記のようなモデル上の制約による計算時間の自明な下限も存在しない.実際,グラフ問題に対しては,達結成分等め基本的問題に対して,PRAMモデルに匹敵する高速アルゴリズムが実現されることが知られている.本稿では,最大値問題に対するO((log log n)^2)時間の確率アルゴリズムを考える.n^2個の各プロセッサに与えられたn^2の整数の中から最大の整数を探す問題である.PRAM上ではO(log log n)時間のそれ以上改良できない決定性アルゴリズムが知られているが,それに比べてもそれ程悪くない.PRAM以外のいわゆる実用的モデル上で,log nより小さい計算時間で実現した例はほとんどないと思われる.プロセッサ間の物理的距離が小さいという利点がMBUSの特色ではあるが,逆に,1度に通信できるデータの数が2n(バスの数=プロセッサ数の約平方根)に限定されるという欠点がある.従って,必要なデータ通信の絶対量が多い問題,例えば全てのプロセッサが1度はデータをバスに乗せる必要のある問題では対数時間を実現することはできない.もちろんそのような問題は数多く存在し,最近ラウティング問題に対してかなり良い下限が証明された.本稿で扱う問題は必要なデータ通信量の少ない問題の範疇に入り,MBUSに向いた問題であることは確かである.

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ