著者

石崎 一明 川人 基弘 今野 和浩 安江 俊明 竹内 幹雄 小笠原 武史 菅沼 俊夫 小野寺 民也 小松 秀昭

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CPSY, コンピュータシステム (ISSN:09135685)

巻号頁・発行日

vol.99, no.252, pp.17-24, 1999-08-05

被引用文献数

1

---

Javaはプログラムの安全性のために、例外チェックやポインタを排除したオブジェクトへのアクセスなど、他の言語より大きなオーバヘッドを持つ。またプログラムの柔軟性を提供するために、型検査、動的なクラスリンク、オブジェクトを伴ったインスタンスメソッド呼び出し、を提供している。これらの特徴を失うことなくプログラムの性能を改善するためには、実行時にバイトコードからネイティブコードへコンパイルを行うJust-In-Time (JIT)コンパイラが必須である。本稿では、JITコンパイラへ実装した以下の最適化、定数伝搬、不要コードの除去、例外チェックの除去、共通部分式の除去、型検査の単純化、メソッド呼び出しのインライン展開、メソッド呼び出しの一意決定、について述べる。さらに、9つのプログラムの実行結果より、これらの最適化が効果的であることを示す。

著者

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

出版者

情報処理学会

雑誌

情報処理学会論文誌プログラミング(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の言語仕様を満たしつつ平均実行時間を短縮する.

著者

石崎 一明 安江 俊明 川人 基弘 小松 秀昭

出版者

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

雑誌

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

巻号頁・発行日

vol.43, no.8, pp.110, 2002-09-15

---

本発表では,Java などの動的クラスロードをともなう言語において,実装が容易な動的メソッド呼び出しの直接devirtualization 手法を提案する.本手法では,コンパイル時に動的メソッド呼び出しに対して直接devirtualization されたコードとメソッドがオーバライドされた場合に実行する動的メソッド呼び出し,の2 種類のコードを生成する.最初は前者を実行し,オーバライドが起きたときにコードを書き換えて後者を実行する.本手法では,コード書換えによって直接devirtualization されたコードを無効化するので,脱最適化のような再コンパイルのための複雑な実装が不要である.一方,再コンパイルを不要にするためにコンパイル時に2 種類のコードを用意するので,制御フロー上に合流点が生成される.一般に制御フローの合流点はコンパイラの最適化を妨げるが,本発表では合流点が存在しても十分な最適化を可能にする手法を示す.さらに,本手法と他のdevirtualization 手法を組み合わせてJava のJust-In-Time コンパイラに実装し,評価を行った.その結果,devirtualizationを行わない場合に比べ,SPECjvm98 とSPECjbb2000 において0 ?181%(平均24%)性能を改善できることを示す.This presentation presents a direct devirtualization technique for a language such as Java with dynamic class loading.The implementation of this technique is easy.For a given dynamic method call,a compiler generates the inlined code of the method,together with the code of making the dynamic call.Only the inlined code is actually executed until our assumption about the devirtualizationbecomes invalidated,at which time the compiler performs code patching to make the code of dynamic call executed subsequently.This technique does not require the complicated implementation such as deoptimization to recompile the method that is active on stack.Since this technique prevents some optimizations across the merge point between the inlined code and the dynamic call,we have further more proposed optimization techniques effectively.We made some experiments to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time compiler.In summary, we improved the execution performance of SPECjvm98 and SPECjbb2000 by ranging from 0%to 181%(with the geometric mean of 24%).

著者

石崎 一明 安江 俊明 川人 基弘 小松 秀昭

出版者

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

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.43, no.1, pp.124-136, 2002-01-15

参考文献数

13

被引用文献数

1

---

本論文では,Java等の動的クラスローディングをともなう言語において,実装が容易な動的メソッド呼び出しの直接devirtualization手法を提案する.本手法では,動的メソッド呼び出しに対して直接devirtualizationされたコードと,メソッドがオーバライドされた場合に実行する動的メソッド呼び出しの2種類のコードをコンパイル時に生成する.最初は前者を実行し,メソッドのオーバライドが起きたときにコードを書き換えて後者を実行する.本手法では,コード書換えによって直接devirtualizationされたコードを無効化するので,脱最適化のような再コンパイルのための複雑な実装が不要である.一方,再コンパイルを不要にするためにコンパイル時に2種類のコードを用意するため,制御フロー上に合流点が生成される.一般に制御フローの合流点はコンパイラの最適化を妨げるが,本論文では合流点が存在しても十分な最適化を可能にする手法を示す.また本手法と他のdevirtualization手法を組み合わせてJavaのJust-In-Timeコンパイラに実装し評価を示す.その結果,devirtualizationを行わない場合に比べ,SPECjvm98とSPECjbb2000において0?181%(平均24%)性能を改善できることを示す.This paper presents a direct devirtualization technique for a language such as Java with dynamic class loading.The implemetation of this technique is easy. For a given dynamic method call, a compiler generates the inlined code of the method, together with the code of making the dynamic call. Only the inlined code is actually executed until our assumption about the devirtualization becomes invalidated, at which time the compiler performs code patching to make the code of dynamic call executed subsequently. This technique does not require complicated implementations such as deoptimization to recompile the method that is active on the stack. Since this technique prevents some optimizations across the merge point between the inlined code and the dynamic call, we have furthermore proposed optimization techniques effectively. We made some experiments to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time compiler. To summarize our result, we improved the execution performance of SPECjvm98 and SPECjbb2000 ranging from 0% to 181% (with the geometric mean of 24%).

著者

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

雑誌

情報処理学会論文誌コンピューティングシステム(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.