分割可能なグローバルバスをもつプロセッサアレー上での最大値選出と中央値選択問題

前場 隆史  辰巳 昭治  菅谷 光啓  

誌名
電子情報通信学会論文誌 A   Vol.J72-A   No.6   pp.950-958
発行日: 1989/06/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造,計算複雑度
キーワード: 


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




あらまし: 
プロセッサアレーにグローバルバスを設けることによって,N個のデータ中の最大値をみつける問題等に対しては,計算時間を改善することができるということから,種々なグローバルバス形態が提案されている.本論文では,開閉装置をグローバルバス中に複数個挿入し,プロセッサから開閉制御を行うことにより分割可能なグローバルバスをもつプロセッサアレーを考え,最大値選出等の半群計算および中央値選択問題が効率良く計算できる並列アルゴリズムを構成する.また,提案するアルゴリズムの計算量を評価し,本手法が漸近的に優れていることを示す.更に,分割可能グローバルバスはVLSIチップ上に有効に埋め込めることを確かめるため,VLSI回路の良さを表す尺度面積時間積を導出し,従来のグローバルバス形態をもつプロセッサアレーに比べ,よりVLSI向きであることを明らかにする.