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

閲覧数: 2
ダウンロード数: 0
このエントリーをはてなブックマークに追加

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

フォーマット:
助成・補助金
Kyushu Univ. Production 九州大学成果文献
責任表示:
岩間 一雄(九州大学・工学部・助教授)
本文言語:
日本語
研究期間:
1990
概要(最新報告):
メッシュバス計算機(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)のアルゴリズムの開発に成功した. 続きを見る
本文を見る

類似資料:

7
学習と教示のアルゴリズム論的研究 by 宮野 悟; MIYANO Satoru
11
定理自動証明技術の計算論的研究 by 岩間 一雄; IWAMA Kazuo
6
探索アルゴリズムの効率化 by 宮野 悟; MIYANO Satoru
6.
探索アルゴリズムの効率化 by 宮野 悟; MIYANO Satoru
7.
学習と教示のアルゴリズム論的研究 by 宮野 悟; MIYANO Satoru
8.
計算科学への圏論の応用 by 河原 康雄
11.
定理自動証明技術の計算論的研究 by 岩間 一雄; IWAMA Kazuo