並列コンピュータのための高速再配置可能合網
スポンサーリンク
概要
- 論文の詳細を見る
本論文は,ベンズIN(Interconnection Network)の並列処理への応用が,より実際的となるような高速制御アルゴリズムについて考察している.まず,サイクリック・キューブ・トポロジーに基づいたCCE(Cyclic Cube Engine)と呼ぶ高速並列計算モデルを構成する.但し,φ=N^<(1+1/h)>とする.ここで、φとNは,それぞれ,計算モデルを構成する処理要素の数と入力の数を表す.また、bは2≦h≦log Nを満たす任意の整数である.次に、このモデルを用いて、任意のパーミュテーションをO(h log_2N)の時間で実現可能とするベンズINの並列セッティングアルゴリズムを与える.これは、前述の並列セッティングアルゴリズムをAcceleratorと呼ぶもう一つの高速アルゴリズムにより駆動することにより実現される.また,この手法による結果が、プロセッサ数が有眼のもとで,一般的なnonsharedモデルについて,任意のパーミュテーションに対して下限値内にあることが証明される.さらに、これらのアルゴリズムを用いて、任意のパーミュテーションに対して、ベンズINのスイッチをO(h log_2N)の時間で設定するための高速並列アルゴリズムを構成している.
- 一般社団法人情報処理学会の論文
- 1995-03-10