自己相似型ネットワークを有するマルチプロセッサシステム上での並列アルゴリズム

菅谷 光啓  前場 隆史  辰巳 昭治  阿部 健一  

誌名
電子情報通信学会論文誌 D   Vol.J73-D1   No.11   pp.847-855
発行日: 1990/11/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(797.7KB)>>
論文を購入




あらまし: 
自己相似型の相互結合網を有するマルチプロセッサシステム上でのいくつかの並列アルゴリズムを提案する.自己相似型の結合網とは全体の形を相似縮小したいくつかの結合網から構成される結合網であり,2進木やスノーフレーク構造などが代表的な例である.筆者らは既に3-クリークを基本図形とした自己相似結合網で結ばれたマルチプロセッサシステムを提案しているが,本論文ではこのシステム上でいくつかのデータの中から最大値を選出する最大値抽出問題,ソーティング,中央値選択問題を解く並列アルゴリズムを提案し,計算複雑性を議論する.また,処理要素と通信リンクの間に開閉装置を付加することによって,上記三つの問題に対する並列アルゴリズムが計算量的に改善されることを明らかにする.また,ウェーハスケールでの実現を考えた場合における提案アルゴリズムの面積時間評価を行い,各アルゴリズムの理論的な下界および2進木の場合と比較・検討し,十分効率よく実現され得るという結果を得ている.