並列処理向きシステムCubematについて  [in Japanese] The Cubemat : a parallel processing system  [in Japanese]

工業,産業,科学等の諸分野において,数値,非数値演算を高速に処理する実用的な要求が高い.このような要求に答える効率的な構成として,多数の処理要素を用いた並列計算処理機構が,これまで数多く提案されてきた.それらの代表的な結合構成としては,格子結合,超立方体結合,木結合,多段相互結合ネットワーク等がある.本報告では並列処理向きシステムCubematを提案し,その2次元レイアウトとそれを用いたアルゴリズムを与える.Cubematの各ノード間結合は,超立方体(キューブ)結合と高速バス結合を基本にしている.提案している反射2進Cubematのレイアウトは,ノード数nが大きいとき単純なレイアウト構成の約4/9の面積で実現できる.また,反射2進Cubematのキューブ結合の一部は,すべてのノードに対して格子結合を形成している.このことは,反射2進Cubematが超立方体アルゴリズムと格子結合アルゴリズムの双方を実行できることを示している.また,本報告ではCubematを用いたバイトニックソートの例を与えている.nノードCubematが,一度に√<n>データを取り扱うことのできる主計算機のもとで動作するとき,nデータ・バイトニックソートの本体はO(log^2n)時間,データ入出力はO(√<n>)時間で実行できる.