バイトニックソートの並列計算機へのマッピング
スポンサーリンク
概要
- 論文の詳細を見る
Batcherにより開発されたバイトニックソートは最も高速な並列ソート法の一つである。バイトニックソートは本来はソートネットワークのためのアルゴリズムである。しかし実際には一般の並列計算機を用いて複数の比較器を少数のPEにマッピングし、比較器間の結合をPE間の通信でシュミレートすることで実現されている。特に超立方体結合の並列計算機では比較器間の結合を効率よくシュミレートできるのでバイトニックソートはよく用いられる。バイトニックソートを超立方体結合の並列計算機に移植する場合、従来のマッピングでは1つのPEに1つのソートエレメントを置く(1PE-1エレメントマッピング)。このマッピングではPE間通信を超立方体結合上で閉塞なしに処理できる。またどの通信も超立方体結合上の隣接間のみに限定できる。しかし1つの比較を2つのPEで重複して行なう無駄が生じる。これに対して筆者等は1つのPEに2つのソートエレメントを置く新マッピングを考案した(1PE-1比較マッピング)。新マッピングでは比較の重複がない。また1PE-1エレメントマッピングと同様にPE間通信を超立方体結合上で閉塞なしに処理し、どの通信も超立方体結合上の隣接間のみに限定できる。本報告では、バイトニックソート、1PE-1エレメントマッピングについて簡単にレビューした後、1PE-1比較マッピングを紹介し、その性能評価を行なう。
- 一般社団法人情報処理学会の論文
- 1992-09-28
著者
-
野口 泰生
(株)富士通研究所
-
武 理一郎
(株)富士通研究所
-
野口 泰生
富士通研究所
-
萩原 つね子
富士通研究所
-
赤星 直輝
富士通研究所
-
武 理一郎
富士通研究所
-
赤星 直輝
(株)富士通研究所ソフトウェア研究部
関連論文
- オーガニックストレージシステムの大規模ハードウェアへの実装(IPストレージ, SWOPP武雄2005 (2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ))
- 疎結合並列計算機における多重結合演算の評価
- バイトニックソートの並列計算機へのマッピング
- トランスピュータを用いた並列データベースマシンにおける結合演算の性能評価
- 分散制御型全対全通信結合網
- 全対全通信の応用
- ソート及びハッシュジョインの並列処理
- 分散データベースシステムRDB/DVにおけるリカバリ方式
- オーガニックストレージシステム : 自律し成長するストレージシステム(ネットワークストレージシステム及び一般)
- 動的負荷分散を考慮した並列相関分析アルゴリズム (高度データベース論文特集)
- 全対全通信に於けるフロー制御方式の影響のシミュレーションによる評価
- 大量ディジタルデータの長期保存システム(貴重な音声・音楽データの採録・修復・保存を考える)
- 並列DB処理への取り組み
- 訪問研究員の憂鬱