VMX命令セットを用いる高速なソートアルゴリズム(数値アルゴリズム)
スポンサーリンク
概要
- 論文の詳細を見る
データを値の順番に並べ直すソート処理は多くのソフトウェアで使用される最も基本的な操作の1つであり,ソート処理の高速化は多くのワークロードの性能向上に寄与する.ソート処理は基本的な操作であるため,古くから多くのアルゴリズムが提案されているが,近年の高性能な汎用プロセッサのSIMD命令を用いて高速にソートを行うことのできるアルゴリズムはこれまで提案されていない.そこで本研究ではPowerPCアーキテクチャが持つSIMD命令セットであるVMXを使用して,並列に処理を行うとともに分岐予測ミスの影響をなくすことで高速にソート処理を行うことのできるアルゴリズムを提案する.このアルゴリズムを実装し,PowerPC970FXプロセッサ上で評価を行い,クイックソートと比較して最大で5.6倍の性能向上が得られることを示した.
- 一般社団法人情報処理学会の論文
- 2006-05-15
著者
-
小松 秀昭
日本IBM東京基礎研究所
-
森山 孝男
日本アイ・ビー・エム株式会社東京基礎研究所
-
小松 秀昭
日本アイ・ビー・エム株式会社東京基礎研究所
-
中谷 登志男
日本アイ・ビー・エム(株)東京基礎研究所
-
井上 拓
日本IBM東京基礎研究所
-
中谷 登志男
日本IBM東京基礎研究所
-
井上 拓
日本アイ・ビー・エム株式会社東京基礎研究所
-
小松 秀昭
日本ibm株式会社東京基礎研究所
-
小松 秀昭
日本アイ・ビー・エム株式会社 東京基礎研究所
-
井上 拓
日本アイ・ビー・エム(株)
関連論文
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法 (ディペンダブルコンピューティング)
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法 (コンピュータシステム)
- ループパーティショニングを用いたショートベクトル化技法
- 6N-4 レジスタ干渉グラフの分割による高速化手法に関する研究(数値計算とコンパイラ技術,学生セッション,アーキテクチャ)
- 非再試行型レジスタ割付けとその評価
- 生存区間分割時に発生する偽干渉を避けるための同時コピー中間コードの利用(ARC-6 : ソフトウェア最適化,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- 分岐の相関を利用した効率的なパスプロファイリング
- 計算機資源を考慮したパイプライン並列性抽出手法
- 並列トランザクショナルアプリケーションのためのプログラミングフレームワーク
- 多重ループにおける最適ループ展開数算定技法
- 数値演算ループの多次元展開技法
- 浮動小数点演算の正確さに関する投機を用いたJavaの数値計算の高速化
- アトリビュートプロセッサを用いて効率化した三次元グラフィクスのジオメトリ演算の並列処理
- マルチコア・システムにおける SAP Java アプリケーション・サーバのスケーラビリティ性能比較
- 並列コピーの導入による生存区間分割手法の性能向上
- Javaにおける例外処理の実行時情報を利用した最適化
- コンパイル速度の向上を目的とした非反復型レジスタ割付け手法
- 頻出メソッド管理テーブルを用いたinvokeinterface命令の実行高速化手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- SIMD命令を用いるUTF-8文字列デコード処理の高速化
- 多重ループにおける最適ループ展開数算定技法
- 再現コンパイル手法を用いたJava JITコンパイラの問題判別
- PowerPCプロセッサの特性を考慮した高速Javaバイトコードインタプリタの構成法
- 動的コンパイラのための実行時分岐予測を用いた最適化手法
- Blue Gene/Pにおける第一原理分子動力学ソフトウェアPHASEの最適化
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- ECUソフトウェアのシミュレーション実行時における状態方程式の遷移解析手法
- VMX命令セットを用いる高速なソートアルゴリズム(数値アルゴリズム)
- Simultaneous Multi Thread (SMT) 技術を用いるCPU上で動作する計算資源予約システム
- PowerPCを用いたハードウェアシステム用のGDBサーバ
- 4.3次元グラフィックスのハードウェア (コンピュータ・グラフィックスの基本的テクノロジーと最近の話題)
- 3次元グラフィックスのハ-ドウェア
- PHIGS の構造体を処理するジオメトリ演算のマルチプロセッサ上での実行効率評価
- PHlGS の構造体を処理するジオメトリ演算のマルチプロセッサ上での実行効率評価
- TOP-1オペレーティング・システム : (5)デバッグ環境
- TOP-1オペレーティング・システム : (3)メモリ管理
- TOP-1オペレーティング・システム : (2)プロセス・スケジューリング
- TOP-1オペレーティングシステム : (1)基本方針
- ポータブルなPrologコンパイラーの実現
- JSIAIワークステーション(7) : Prologコンパイラの評価
- JSIAIワークステーション(6) : Prologコンパイラの最適化技法
- JSIAIワークステーション(5) : Prologコンパイラの概要と設計方針
- プログラムの信頼性向上を目的とした補助スレッドの効率的利用(ジョブスケジューリング, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- プログラムの信頼性向上を目的とした補助スレッドの効率的利用(ジョブスケジューリング, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- プログラムの信頼性向上を目的とした補助スレッドの効率的利用
- レジスタ生存グラフを用いたレジスタ割付けへのプロセッサ並列度の考慮
- B-001 補助スレッドによるソフトウェアの信頼性向上(B.ソフトウェア)
- 領域分割レジスタ生存グラフを用いたレジスタ割付けへの動的計画法の適用
- C-13 レジスタの有効利用を考慮した部分冗長性除去(計算機アーキテクチャと最適化,C.アーキテクチャ・ハードウェア)
- レジスタ生存グラフを用いたレジスタ割付け及びコードスケジューリング技法
- 実行時命令再構成機構を用いた投機的例外復旧手法(21世紀のコンピュータセキュリティ技術)
- ループパーティショニングを用いたショートベクトル化技法
- 制御依存の緩和を考慮した並列性抽出手法
- Java Just-In-Timeコンパイラにおける最適化とその評価
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成 (ディペンダブルコンピューティング)
- SILSを対象としたMCUペリフェラルプログラムの自動コード生成 (コンピュータシステム)
- 静的プロファイルを用いたファイル・プリフェッチ手法の提案
- HPF処理系の実現と評価
- コード書換えによる動的メソッド呼び出しの直接Devirtualization
- Javaプログラムにおいて例外による順序制約を投機的命令移動を用いて除去する方法
- 3. SP2のためのHPFコンパイラにおける最適化技術 (>特集
- シリーズパラレル型レジスタ生存グラフを用いたレジスタ割付け技法とその評価
- 2000-ARC-139-6 シリーズパラレル型レジスタ生存グラフを用いたレジスタ割付けへの動的計画法の適用
- レジスタ生存グラフを用いたレジスタ割付け手法の改善
- 動的コンパイラにおける実行時経路情報の構造的収集手法の提案
- 大域的なコード移動を使った複数式の実行コスト削減法
- Java言語に対する投機的なメモリアクセスの最適化手法
- 拡張VLIWプロセッサGIFTの命令供給機構
- 拡張 VLIW プロセッサ GIFT における命令レベル並列処理機構
- 条件分岐の効率的実行を可能とする細粒度並列アーキテクチャ
- 拡張PDGを利用した最適ループ展開数算定法
- マルチプロセッサシステムにおけるリダクションオペレーション
- バイトコードパターンマッチングを用いたJavaインタプリタの高速化
- ソフトウェアを援用した投機的例外処理機構の実現と評価
- データ依存不確定ループの最内ループ並列化
- 2D-1 ガード付きPDGを用いた命令レベル並列アーキテクチャのための最適化コンパイラの実現
- プレディケート付き依存グラフを用いたバージョニング手法
- 拡張VLIWプロセッサGIFTにおけるブランチハンドリング機構
- ソフトウェアによる投機的例外処理の実現
- 命令レベル並列アーキテクチャのためのコードスケジューラおよびレジスタアロケータの協調技法
- レジスタ生存グラフを用いたレジスタ割付け技法
- 拡張VLIWプロセッサGIFTにおける投機的実行支援機構
- 多重ループステージングにおける通信遅延隠蔽技法
- 命令レベル並列アーキテクチャのための大域的コードスケジューリング技法
- 共有メモリ型並列計算機における多重ループステージングによるパイプライン実行
- コードスケジューリングとレジスタ割付けの協調による最適化
- ショートベクトルプロセッサ向けループ並列化技法
- ショートベクトルプロセッサ向けループ並列化技法
- 実行環境が異なる2つのコード間の遷移を行う際の効果的な最適化手法