WEKO3
-
RootNode
アイテム
VMX命令セットを用いる高速なソートアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/18333
https://ipsj.ixsq.nii.ac.jp/records/183335f129f10-805b-4416-a918-7d1c3ab3d04c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TACS4707010.pdf (1.0 MB)
|
Copyright (c) 2006 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2006-05-15 | |||||||
| タイトル | ||||||||
| タイトル | VMX命令セットを用いる高速なソートアルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Fast Sorting Algorithm for VMX Instruction Set | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | 数値アルゴリズム | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 日本アイ・ビー・エム株式会社東京基礎研究所 | ||||||||
| 著者所属 | ||||||||
| 日本アイ・ビー・エム株式会社東京基礎研究所 | ||||||||
| 著者所属 | ||||||||
| 日本アイ・ビー・エム株式会社東京基礎研究所 | ||||||||
| 著者所属 | ||||||||
| 日本アイ・ビー・エム株式会社東京基礎研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Research Laboratory, IBM Japan | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Research Laboratory, IBM Japan | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Research Laboratory, IBM Japan | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Tokyo Research Laboratory, IBM Japan | ||||||||
| 著者名 |
井上, 拓
森山, 孝男
小松, 秀昭
中谷, 登志男
× 井上, 拓 森山, 孝男 小松, 秀昭 中谷, 登志男
|
|||||||
| 著者名(英) |
Hiroshi, Inoue
Takao, Moriyama
Hideaki, Komatsu
Toshio, Nakatani
× Hiroshi, Inoue Takao, Moriyama Hideaki, Komatsu Toshio, Nakatani
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | データを値の順番に並べ直すソート処理は多くのソフトウェアで使用される最も基本的な操作の1 つであり，ソート処理の高速化は多くのワークロードの性能向上に寄与する．ソート処理は基本的な操作であるため，古くから多くのアルゴリズムが提案されているが，近年の高性能な汎用プロセッサのSIMD 命令を用いて高速にソートを行うことのできるアルゴリズムはこれまで提案されていない．そこで本研究ではPowerPC アーキテクチャが持つSIMD 命令セットであるVMX を使用して，並列に処理を行うとともに分岐予測ミスの影響をなくすことで高速にソート処理を行うことのできるアルゴリズムを提案する．このアルゴリズムを実装し，PowerPC 970FX プロセッサ上で評価を行い，クイックソートと比較して最大で5.6 倍の性能向上が得られることを示した． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Sorting is one of the most common operations done by computers and used in variety of software. Sorting is a well-studied problem and hence there are many sorting algorithms and implementations available. However there is no sorting algorithm that effectively exploits SIMD execution units of recent general purpose processors. In this paper, we proposed a novel sorting algorithm for VMX instruction set of the PowerPC architecture. This algorithm divides input data in sorting phase and merges them after sort in order to exploit parallelism of the VMX instruction set. Also it removes stall cycles due to conditional branches by replacingthem with vector minimum and vector maximum instructions. We implemented the algorithm and evaluated the performance on the PowerPC 970FX processor. Our results showed that our new algorithm achieved up to 5.6 times higher performance than quicksort. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11833852 | |||||||
| 書誌情報 |
情報処理学会論文誌コンピューティングシステム（ACS） 巻 47, 号 SIG7(ACS14), p. 105-113, 発行日 2006-05-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7829 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
