权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

二维网格总线机极并行算法研究

基本信息

批准号：
02650278
负责人：
岩間一雄
金额：
$ 0.45万
依托单位：
Kyushu University
依托单位国家：
日本
项目类别：
Grant-in-Aid for General Scientific Research (C)
财政年份：
1990
资助国家：
日本
起止时间：
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)のアルゴリズムの開発に成功した.

The communication function of the office of the computer (MB) is different from that of the office of the computer (MC). MB is different from that of the office of the computer (MC). MB is different from that of the office of the office The purpose of this study is to develop the ability of MB to improve its quality, and to obtain the following results: 1. MB to improve the quality of MC, and to provide the speed of MC to improve its quality. In this case, the MB MC is divided into two parts: one part is O(n), the other part is O(n), the other part is O (n). The only parallel solution on MB is the one that can be thought of as a new solution in O(n) time. This paper presents a new method for determining the symmetry of 2-term distribution curves. 2. The following results were obtained from the investigation of the maximum vulnerability of MB. (1)MC The lower bound of 2n self-evident exists, and the MB has a lower bound of 1.5n time. (2)Lower limit of time. (3)When we adjusted the effectiveness of the digital detour, we examined the upper limit of the special input force, and the detour occurred in practice. The interesting results were obtained. In this paper, we investigate the gap between the upper and lower limits of the above records. 3. The maximum value problem is successful in the development of the maximum value problem.