著者

井上 拓 森山 孝男 小松 秀昭 中谷 登志男

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.47, no.SIG7(ACS14), pp.105-113, 2006-05-15

---

データを値の順番に並べ直すソート処理は多くのソフトウェアで使用される最も基本的な操作の1 つであり,ソート処理の高速化は多くのワークロードの性能向上に寄与する.ソート処理は基本的な操作であるため,古くから多くのアルゴリズムが提案されているが,近年の高性能な汎用プロセッサのSIMD 命令を用いて高速にソートを行うことのできるアルゴリズムはこれまで提案されていない.そこで本研究ではPowerPC アーキテクチャが持つSIMD 命令セットであるVMX を使用して,並列に処理を行うとともに分岐予測ミスの影響をなくすことで高速にソート処理を行うことのできるアルゴリズムを提案する.このアルゴリズムを実装し,PowerPC 970FX プロセッサ上で評価を行い,クイックソートと比較して最大で5.6 倍の性能向上が得られることを示した.