著者

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

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.1, no.2, pp.1-8, 2008-09-26

---

近年,XMLなど多くの用途において,テキストデータの標準的な表現形式として,1文字を1~3バイトの可変長で表現するUTF-8エンコーディングが用いられている.一方,Java仮想マシンなど多くの処理系においては,文字列の内部表現として1文字が2バイトの固定長であるUTF-16エンコーディングが用いられている.そのため,Javaで記述されたWebアプリケーションサーバなどの多量のテキストデータを取り扱うワークロードにおいては,テキストデータをUTF-8とUTF-16との間で相互に変換する処理が大きな処理時間を占める場合があり,このテキストデータ変換処理の高速化はシステム全体の性能向上において重要な意味を持つ.本研究では,SIMD命令を用いてUTF-8からUTF-16への変換をはじめとする可変長符号化データのデコード処理を高速に行う手法を提案する.この手法では複数のデータを並列に処理することに加えて,条件分岐での分岐予測ミスによるオーバヘッドを減少させることで,大きな性能向上が得られる.本手法をPowerPCアーキテクチャのSIMD命令セットであるVMX命令を用いて実装し,様々なテキストデータを入力としてUTF-8文字列デコード処理の性能を計測した結果,SIMD命令を用いない既存の方法と比較して単純な例で10倍以上,実際のテキストデータを用いたケースでも2倍から10倍の性能向上が得られた.Recently UTF-8 encoding is widely used as a standard format for text data exchange. The Java programming language, however, uses UTF-16 encoding as its internal representation format for text data. As a result, data conversions between UTF-8 and UTF-16 consume considerable amount of CPU time in workloads that process large amount of text data, such as web application servers. Hence accelerating these conversions are important to improve the performance of many applications. In this paper, we present our new technique to accelerate decoding of variable-length formats, such as conversion from UTF-8 to UTF-16, by using SIMD instructions. The new technique can achieve higher performance by reducing overhead of branch mispredictions in addition to exploiting data parallelism of SIMD instructions. We implemented the technique using VMX instructions of the PowerPC architecture and evaluated its performance to decode various UTF-8 sequences on a PowerPC 970MP processor. As a result, we showed that our technique significantly accelerated the UTF-8 decoding compared to the existing method.

著者

竹内 幹雄 小松 秀昭 中谷 登志男

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.20, no.4, pp.355-362, 2003-07-25 (Released:2012-02-15)

---

Javaの高速化の研究が盛んになされているが,数値計算の分野では依然Fortranに水をあけられたままである.その理由の1つに,浮動小数点演算の厳密な正確さ(accuracy)が原因で最適化が困難なことがある.とりわけ,融合型積和演算(fused multiply-add (FMA))命令や,再結合(reassociation)を利用できないことが,Javaの性能に大きく影響している.この論文では,浮動小数点演算の正確さに関する投機(floating-point (FP) speculation)を提案する.FP speculationは,既存アーキテクチャの余ったハードウェア資源(浮動小数点レジスタと演算ユニット)を利用して,各最適化対象に対し正確さの異なる2通りの計算(投機計算と検算)を同時に実行することで,Javaの言語仕様を満たしつつ平均実行時間を短縮する.

著者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

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

出版者

一般社団法人情報処理学会

雑誌

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

巻号頁・発行日

vol.47, no.7, pp.105-113, 2006-05-15

---

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