データパラレル超並列計算機における適応型ソートアルゴリズム

概要

論文の詳細を見る
ソーティングネットワークを初めとして、並列ソーティングアルゴリズムは多数提案されており、最近では超並列計算機上への実装についても報告されるようになった。しかし逐次型と違い、並列ソーティングの場合は比較的計算量やメモリアクセスの他に、ネットワークを介したデータの移動を考慮しなくてはならなくなるため、プロセッサ数、データ数によって最適なアルゴリズムは異なる。異なるアーキテクチャを持つ計算機ではなおさらのことである。そこで本論文ではデータパラレル超並列計算機におけるデータ数、プロセッサ数に適応したソーティングについて述べるとともにアーキテクチャに応じたソーティングについて考察する。今回使用したのは、MasPar MP-1というSIMD型の超並列計算機である。MP-1は4bitのPEを2次元格子上に配置し、隣接する8方向のPEと通信が可能であるX-netと、多段クロスパ結合による汎用通信網ルータを備えている。PE数は1Kである。ソート対象は32bit整数のキーのみとし、以下の説明においてPをPE数、Nをデータ数とする。また、グラフ中の処理時間はPEあたりのデータ数で正規化している。
1992-09-28