- 著者
-
野口 泰生
萩原 つね子
赤星 直輝
武 理一郎
- 雑誌
- 全国大会講演論文集
- 巻号頁・発行日
- vol.45, pp.255-256, 1992-09-28
Batcherにより開発されたバイトニックソートは最も高速な並列ソート法の一つである。バイトニックソートは本来はソートネットワークのためのアルゴリズムである。しかし実際には一般の並列計算機を用いて複数の比較器を少数のPEにマッピングし、比較器間の結合をPE間の通信でシュミレートすることで実現されている。特に超立方体結合の並列計算機では比較器間の結合を効率よくシュミレートできるのでバイトニックソートはよく用いられる。バイトニックソートを超立方体結合の並列計算機に移植する場合、従来のマッピングでは1つのPEに1つのソートエレメントを置く(1PE-1エレメントマッピング)。このマッピングではPE間通信を超立方体結合上で閉塞なしに処理できる。またどの通信も超立方体結合上の隣接間のみに限定できる。しかし1つの比較を2つのPEで重複して行なう無駄が生じる。これに対して筆者等は1つのPEに2つのソートエレメントを置く新マッピングを考案した(1PE-1比較マッピング)。新マッピングでは比較の重複がない。また1PE-1エレメントマッピングと同様にPE間通信を超立方体結合上で閉塞なしに処理し、どの通信も超立方体結合上の隣接間のみに限定できる。本報告では、バイトニックソート、1PE-1エレメントマッピングについて簡単にレビューした後、1PE-1比較マッピングを紹介し、その性能評価を行なう。