二次元メッシュ型バス機械上での極並列アルゴリズムの研究

点击翻译按钮获取中文摘要

メッシュバス計算機(MB)はメッシュ計算機(MC)の局所通信機能を,ニ次元メッシュ状に配置されたバスによるグロ-バル通信機能に置き換えた並列モデルである.MBはMCに比べてそれほど劣らないハ-ドウエア的実現性を有しており,実用的には最も有望な極並列ア-キテクチャの一つであろう.本研究の目的は,このMBがどの程度の能力を発揮するかをアルゴリズム論的観点により調べるものであり,以下の成果を得ることが出来た.1.MBはMCに比べ,グラフ問題等の数多くの問題でMCより格段に速いアルゴリズムを提供してくれる.しかし,ソ-ティング問題に関してはMC上で多くのO(n)時間アルゴリズムが知られているのに対し,MBはMCの様に再帰的な分割統治法が使えそうにないため,同様な時間のMB上でのソ-ティングアルゴリズムの開発が困難視されていた.我々は,MB上で唯一並列にソ-ティングが可能と思われる,行及び列に関するソ-トを基本演算にして,O(n)時間の新しい確率アルゴリズム(2項分布ソ-ト)を開発した.本アルゴリズムは,確率論における2項分布曲線の対称性を積極的に利用するという新しいアイデアによっている.これによって,MBのMCに対する最大の弱点を一応解消することができた.2.MB上でのラウティング問題も考察し,以下の結果を得た.(1)MCでは2nの自明な下限が存在するのに対し,MB上で1.5n時間のラウティングアルゴリズムを得た.(2)下限としてn時間を得た.(3)デ-タの迂回効果等を調べるために,様々な特殊入力に対して上限を考察し,迂回を実際に生かせる興味深い結果を得た.本考察は上記の上下限の間隙を縮めることへの寄与が期待される.3.その他,最大値問題に対する対数時間アルゴリズムや,κ番目に大きいデ-タを求めるO(n)のアルゴリズムの開発に成功した.