PowerPCプロセッサの特性を考慮した高速Javaバイトコードインタプリタの構成法

全文

(1)Vol. 43. No. SIG 8(PRO 15). Sep. 2002. 情報処理学会論文誌：プログラミング. PowerPC プロセッサの特性を考慮した高速 Java バイトコードインタプリタの構成法緒. 方. 一. 則†. 小. 松. 秀. 昭†. 中谷. 登志男†. インタプリタは多くのコンピュータ言語実行環境において重要な役割を持ち，その実行速度は，Java など仮想マシンを用いる言語において非常に重要である．さらに，Just-In-Time（ JIT ）コンパイラ技術を用いた高性能 Java 実行時環境においても重要である．なぜなら，コンパイル時間やメモリ使用量の増加を避けるためにメソッドを選択的にコンパイルするので，多くのメソッドがインタプリタで実行されるためである．インタプリタを高速化する技術は数多く提案されているが，スーパスカラプロセッサ上でインタプリタを実行した場合の，冗長なメモリロードと高頻度な間接分岐のオーバヘッドの問題に注目した手法は提案されていない．これらの問題は，ほとんどのバイトコード命令が数バイト長と短く，オペコードを基本的操作ごとに割り当て，その処理ルーチンが短いコード断片となる Java では特に顕著である．本稿では，これらの問題点を PowerPC プロセッサ用の Java バイトコードインタプリタにおいて解決する手法を提案し，それぞれの実行速度に対する効果を IBM POWER3 プロセッサ上で主要な Java ベンチマークプログラムを用いて示す．. Constructing a Fast Java Bytecode Interpreter for PowerPC Processors Kazunori Ogata,† Hideaki Komatsu† and Toshio Nakatani† Interpreters play the important role in many languages, and their performance is critical particularly for a popular language like Java. The performance of the interpreter is important even in the context of high performance Java Virtual Machines (JVMs) that employ Just-InTime (JIT) compiler technology, because there is more and more pressure to delay the start of compilation and reduce the number of the target methods to compile. Many techniques have been proposed to improve the performance of various interpreters, but none of them has fully addressed the issues of minimizing redundant memory accesses and the overhead of indirect branches caused by the nature of interpreters on superscalar processors. These issues are even more serious for Java particularly because the bytecode is typically one or a few bytes and the execution routine for each bytecode is short due to the low-level, stack semantics of Java bytecode. In this paper, we describe a few novel features of our Java bytecode interpreter developed for the PowerPC processor to solve these problems, and we show how each feature contributes to the overall performance of the interpreter for major Java benchmark programs on an IBM POWER3 processor.. 伸長やメモリ消費量の増大を避けるために，選択的な. 1. はじめに. コンパイルが必要23)であり，多くのメソッドがイン. Java 5)などの仮想マシンを用いる言語処理系におい. タプリタで実行されるからである．我々の最新の処理. て，インタプリタは，アプリケーション実行速度に大き. 系23)では，実行されたメソッドの 20%程度しか JIT. な影響を与える重要な構成要素である．また，Just-In-. コンパイルされない．. Time（ JIT ）コンパイラ18),22)∼24)を持つ高性能 Java 16) 仮想マシン（ JVM ）においても重要である．なぜなら，それらの仮想マシンにおいても，すべてのメソッ. パスカラプロセッサ上で実行する場合に起きる，同一. ドをコンパイルすることによるプログラム起動時間の. ワードを複数回ロードすることによる冗長なメモリア. インタプリタを高速化する手法は様々なものが提案されている1)∼3),6),7) ．しかし，インタプリタをスー. クセスと，高頻度で予測困難な間接分岐のオーバヘッドに注目した手法は提案されていない．これらの問題. † 日本 IBM 株式会社東京基礎研究所 Tokyo Research Laboratory, IBM Japan, Ltd.. は，Java 言語のバイナリ形式であるバイトコードでは 1.

(2) 2. 情報処理学会論文誌：プログラミング. Sep. 2002. 特に顕著である．原因は，1 命令の長さが一般に数バイト以下と短いことと，オペコードが基本的な操作ごとに割り当てられており，それらを処理するバイトコードハンドラ（以下単にハンドラと呼ぶ）が短いコード断片となることである．スーパスカラプロセッサではメモリアクセスがワード単位で行われ，ワード境界をまたぐメモリアクセスに対して内部で追加のメモリアクセスが行われる．そのため，1 ワード未満のバイトコードやワード境界をまたぐバイトコードのフェッチで同一ワードを複数回ロードし，高頻度なロードが大きなボトルネックとなる．我々はバイトコードをレジスタ（ Bytecode. Cache Register または BCR ）にキャッシュすることで，フェッチによる冗長なメモリアクセスを最小化した．さらにワード内の，バイトコードが始まる位置ごとにカスタマイズしたハンドラを用意し，それらでステートマシンを構成することで，実行時チェックなしにバイトコードのワード中の位置を決定できるよう. Fig. 1. 図 1 基本的なインタプリタの構造 Structure of a basic bytecode interpreter.. にした．この手法を位置別ハンドラと呼ぶ．ハンドラにおけるディスパッチのための間接分岐に. 2.1 ベースインタプリタ. よるパイプラインストールも，スーパスカラプロセッ. 最も基本的なインタプリタは，図 1 (b) に示すよう. サにおけるボトルネックとなる．プロセッサの分岐予. にデコードループと呼ばれる短いコードの制御により，. 測機構でこれらの間接分岐の飛び先を予測することは. バイトコードのフェッチ，デコード，ディスパッチおよ. 困難である．この問題に対し，次の次のバイトコード. び実行を繰り返す．図 1 (c) に示すスレッデッドコー. のオペコードの候補となるバイトを投機的にデコード. ド 1),2) インタプリタは，デコードループを各ハンドラ. する解決法が，VLIW プロセッサ向けに提案されてい. にインラインすることで，ハンドラの処理完了後，次. 6). る．我々は，この手法のスーパスカラプロセッサ上. のハンドラへ直接ジャンプする．. の実装法として位置別投機デコードを提案する．本手. 我々のベースインタプリタは，スレッデッドコード. 法では，Address Pool Register（ APR ）と呼ぶ. インタプリタに，実行中のバイトコードのオペランド. レジスタを 4 個用意し，オペコードの候補 3 個を投機. と次のバイトコードのオペコードを，同一のロード命. 的にデコードすることで，次のハンドラのアドレスを. 令でロードする最適化を適用したものである．また，. ハンドラの実行の最初で命令フェッチユニットに送り. 各ハンドラを 64 バイト境界ごとにオペコード順に配. パイプラインストールを減らす．. 置し，オペコード 0 のハンドラを 16 K バイト境界に. 本稿では，PowerPC プロセッサ12) 向けの Java バイ. 整列することで，デコードを PowerPC の rlwimi 命. トコードインタプリタの高速化手法を提案し，各々の. 令☆ 1 命令で処理する．この配置によりハンドラ全体. 効果を最新の PowerPC プロセッサの 1 つである IBM. のサイズは 16 K バイトとなる．. POWER3 プロセッサ上でのベンチマーク結果を用いて示す．以下，2 章では我々が提案・評価したインタ. 2.2 スタックキャッシュ Java バイトコードなどのスタック型仮想マシンの. プリタ高速化手法について述べ，3 章では提案した手. インタプリタでは，スタックオペランドのプッシュ・. 法の移植性を考察する．4 章では各高速化手法を評価. ポップのために，メモリ上に配置されたオペランドス. する．5 章では従来の研究について述べる．. タックを頻繁に操作する．したがって，数個のスタッ. 2. インタプリタ高速化手法本章では，我々のベースインタプリタと，我々が提案・評価した，PowerPC 向け Java バイトコードインタプリタを高速化する手法について述べる．. クオペランドをレジスタにキャッシュすれば実行速度を向上できる．Java では，1 つのバイトコードで使用 ☆. ソースレジスタの内容を指定のビット数ローテートし，結果のビット列から一部分を取り出し，そのビット列でターゲットレジスタの対応するビット列を置換する命令12) ．.

(3) Vol. 43. No. SIG 8(PRO 15). 高速 Java バイトコードインタプリタの構成法. 3. するスタックオペランドはほとんどの場合 2 個以下な. マイズされた部分は太斜体で記述されている．図 2 (c). ので，スタックトップのみ，もしくはスタックトップ. は各ステップ終了時の BCR の内容を示す．. と 2 番目をキャッシュすれば十分である．PowerPC プ. 位置別ハンドラはソフトウェアパイプライン手法の. ロセッサでは，4 章で示すように，ライトスルー方式. 一種なので，分岐が起きるたびにソフトウェアパイプ. でスタックトップのみをキャッシュすればよい．1 個. ラインの再始動が必要で，その頻度が高い場合，その. のキャッシュで十分なのは，メモリロードのレイテン. オーバヘッドにより実行速度が低下する可能性がある．. シが短く，それをインタプリタで必要な他の処理で隠. しかし，通常 Java プログラムの分岐頻度は 5∼7 命令. せるためである．ライトスルー方式で十分なのは，ア. に 1 回20) なので，本手法は一般的なプログラムに対. ウトオブオーダ実行によりストア命令がほかの命令の. して効果を期待できる．4 章に示す実行結果でも，多. 実行を妨げないためである．. くのベンチマークにおいて速度向上が得られた．. 2.3 位置別ハンドラベースインタプリタは，各ハンドラでバイトコード. 2.4 位置別投機デコードスレッデッドコードインタプリタでは，ハンドラは. のフェッチを行い，ワード境界をまたぐメモリロード. 間接分岐命令で次のバイトコードのハンドラへジャン. のために 2 ワードをロードする場合が多い．. プする．Branch target buffer（ BTB ）などの分岐予. これらの無駄なメモリロードを減らすために，バイ. 測機構は分岐先アドレスの時間的な局所性を利用して. トコード列をワードごとにレジスタ（ BCR ）にキャッ. いるので，次のバイトコードによって決まるハンドラ. シュする．Java バイトコードでは 2 個の BCR を用意. のアドレスの予測は困難である．たとえば Java バイ. すれば十分である．しかし，バイトコードの先頭は必. トコード aload 0 と，その次に実行されるバイトコー. ずしもワード境界にないので，バイトコードのレジス. ドの間には，時間的局所性がない．. タ内の位置を実行時に求める必要がある．この実行時. 一部のプロセッサは，分岐先アドレスを命令フェッ. チェックはハンドラのクリティカルパス長を 2 倍以上. チユニットにセットすることで間接分岐実行時のパ. にする可能性があり現実的でない．Hoogerbugge らの. 8),12) イプラインストールを減らす機構を持っている．. 6). る．しかし，この方法は，実行時にレジスタシフトの. PowerPC プロセッサは，間接分岐実行の 4 サイクル以上前13)に分岐先アドレスを特殊レジスタ（リンクレジスタもしくはカウントレジスタ）にセットすること. コストが必要になると同時に，バイトコードがワード. で，パイプラインストールをなくすことができる．イ. 境界を越えたかどうかの実行時チェックが必要である．. ンテル IA-64 プロセッサ8),9) も同様な機構を持ってい. 手法のように，オペコードのレジスタ内の位置が一定になるようにレジスタの内容をシフトする方法もあ. 我々の解決法では，各ハンドラをワード中のバイト. る．遅延分岐命令を持つプロセッサでは，遅延命令ス. 位置ごとの 4 通りにカスタマイズし，実行中のバイト. ロットを使用することで同等の効果を得られる6) ．し. コードの位置に対応するハンドラでバイトコードを処. かし，これらの機構を利用するためのレイテンシは多. 理する．各ハンドラは図 2 (b) に示すステートマシン. くのハンドラの実行サイクル数に対して長いので，ハ. により，実行時チェックなしに次のハンドラを選択す. ンドラがデコード後に分岐先アドレスをセットすると. る．カスタマイズにより次の 5 つの処理を削減できる．. 十分な効果を得られない．. • バイトコードポインタの下位 2 ビットから，実行中のバイトコードの位置を算出．. パイプライン化インタプリタ手法の一部として実装された投機的デコード手法6),7)は，バイトコードの. • 2 つの BCR のどちらに実行中のバイトコードのオペランドがあるかを判定．. をオーバラップさせることで，VLIW プロセッサにお. • オペランドを BCR から取り出すためのシフトカウントを，現在のバイト位置から算出．. が次の次のバイトコードをデコードすることで，次の. • 次のオペコードを BCR から取り出すためのシフトカウントを，現在のバイト位置から算出． • 次のワードをロードする必要があるかを，現在のバイト位置から判定．. フェッチ，デコード，ディスパッチ，実行の各ステージいてこの問題を解決した．この手法では，各ハンドラバイトコードのハンドラが，その次のハンドラのアドレスを命令フェッチユニットに早くセットできるようにする．可変長命令では，次のバイトコードをデコードしないとその次のバイトコードの位置を特定できな. 図 2 (d) はカスタマイズされたハンドラの動作を示. いという問題があるが，いくつかの，次の次のバイト. す．灰色の矢印は図 2 (a) のバイトコード列を実行し. コードのオペコードの候補を投機的にデコードするこ. たときの制御フローである．ハンドラの処理でカスタ. とで解決している．投機デコード結果はレジスタに保.

(4) 4. 情報処理学会論文誌：プログラミング. Fig. 2. Sep. 2002. 図 2 位置別ハンドラを適用したハンドラの動作 Operations in bytecode handlers with position-based handler customization.. 持し，可能ならば再利用して，複数の候補をデコード. い．また，我々のインタプリタはバイト位置ごとにカ. するオーバヘッドを減らしている．. スタマイズしたバイトコードハンドラを持つので，候. 最適な候補の数はバイトコード命令セットに依存し， Java では 3 個である．実行頻度の高い Java バイト. 補と APR の対応を実行時に求める必要がない．. コードの命令長は 1∼3 バイトなので，次の命令の長. 同時に実装したインタプリタの動作を，図 3 (a) のバイ. 図 3 (b) に位置別ハンドラと位置別投機デコードを. さを 1∼3 バイトと仮定した場合の候補 3 個をデコー. トコード列を実行した場合の例で示す．図 3 (c) は各ス. ドすれば，高い頻度で投機デコードの効果を得られる．. テップ終了時の BCR と APR の内容を示す．灰色の背. 我々の手法は，Hoogerbrugge ら 6)と異なり，デコー. 景で示した処理は，バイトコード istore 1（図 3 (a). ド結果を保持するためのレジスタ（ APR ）を 4 個用. に灰色の背景で示した）を実行するするために必要な. 意し，候補のバイト位置と対応づけるので，デコード. 処理である．ステップ 1 では，BCR0 バイト位置 3 の. 結果の再利用のためにレジスタ間で移動する必要がな. デコード結果を再利用するので，実際にハンドラがデ.

(5) Vol. 43. No. SIG 8(PRO 15). Fig. 3. 高速 Java バイトコードインタプリタの構成法. 5. 図 3 位置別投機デコードにおけるハンドラの動作 A sequence of operations in bytecode handlers for position-based speculative decoding.. コードするのは BCR1 のバイト位置 0 と 1 のみでよ. できる．バイトコードをキャッシュする C 言語のロー. い．ステップ 2 では，ハンドラの先頭で次のバイト. カル変数は，ハンドラ実行中はレジスタに載っていな. コード（ istore 1 ）のハンドラのアドレスを APR1. いと効果が少ない．switch 文を用いたインタプリタに. から取得しセットできる．. 適用するには，case ブロックをカスタマイズし，それ. 3. 移植性の考察. ぞれに個別の case ラベルを付ける．GNU C コンパイ. 本章は，我々の手法をほかのハードウェアおよびソ. デッドコードインタプリタの場合は，アセンブラで記. フトウェア環境に移植する場合の問題点を考察する．. 3.1 位置別ハンドラの移植性. ラ4) の拡張機能「 Labels as Values 」を用いたスレッ述したインタプリタと同様に実装する．. 64-bit プロセッサ用のインタプリタでは，汎用レジ. 本手法を実装するためには，BCR のために 2 個の. スタが 8 バイト幅なので，バイトコードを 8 バイトず. 汎用レジスタを予約する必要があり，インタプリタの. つキャッシュすれば最大の効果が得られる．この場合. 実装に必要な他のレジスタと合わせると，12 個程度. 8 通りのカスタマイズされたハンドラが必要になる．. の汎用レジスタが必要となる．他のレジスタとは，た. また，BCR0 にキャッシュされたバイトコード中に分. とえばスタックトップのキャッシュ，バイトコードポ. 岐命令が含まれる可能性が増えるので，BCR1 のロー. インタ，フレームポインタ，スタックポインタ，ロー. ドを遅らせた方がよい．しかし，コードサイズの増加. カル変数領域のベースポインタ，コンスタントプール. や，32-bit プロセッサとのバイナリ互換性を考慮する. へのポインタ，スレッドローカルデータへのポインタ，. と，64-bit プロセッサでも 32-bit プロセッサ用の実装. 数個の作業用レジスタである．したがって，インテル. を用いる方が好ましいと考えられる．たとえば，我々. x86 プロセッサのようなレジスタが少ないプロセッサ. のインタプリタの場合，8 通りのハンドラでは 128 K. に移植した場合，本手法は効果が少ないと考えられる．. バイト必要となる．. 本手法は C 言語で記述されたインタプリタにも適用.

(6) 6. Sep. 2002. 情報処理学会論文誌：プログラミング表1 Table 1. 3.2 位置別投機デコードの移植性移植先プロセッサは，命令フェッチユニットに分岐先アドレスをセットすることで，間接分岐時のパイプ. POWER3 17),19) , 400 MHz 32 Kbytes, 128-way set associative, 128 bytes/line 4 Kbyte 768 Mbytes AIX 4.3.3 IBM SDK Java edition 1.3.0 10). CPU I-Cache. ラインストールサイクルを減らす機構を備えている必要がある．たとえば，PowerPC の mtlr 命令や mtctr 命令. 12). ，Intel Itanium プロセッサの mov br=gr,tag. 命令8),9) のような特殊命令，もしくは遅延分岐6)であ. ベンチマーク実行環境 Execution environment.. Page size Memory OS Java VM. る．セットした飛び先アドレスが反映されるまでのレ表2 Table 2. イテンシは，ハンドラの最小実行サイクル数を決定するので，短いほど本手法の効果が大きい．また，飛び先アドレスのセットに特殊命令を必要とするので，ハンドラをアセンブラで記述するか，特殊命令を生成で. Interpreter Base Wt. Description ベースインタプリタ. Base にライトスルー・スタックトップキャッシングを適用したもの. きるようにコンパイラを変更する必要がある．インタプリタは，APR のために 4 個の汎用レジス. DSC. タを予約する必要がある．複数の候補をバイトコード実行と並列にデコードす. Wt+PHC. るので，移植先プロセッサは，スーパスカラプロセッサや VLIW プロセッサなど，命令レベル並列性（ ILP ）. 評価したインタプリタ Evaluated interpreters.. Wt+PHC+PSD. を活用する必要がある．PowerPC プロセッサでは，投機デコードとバイトコード実行を同時に行うために，. Base にダイナミック・キャッシング 3) を適用し，2 個までのスタックオペランドをキャッシュするもの Base に，ライトスルー・スタックトップキャッシングと位置別ハンドラを適用したもの Base に，ライトスルー・スタックトップキャッシング，位置別ハンドラ，位置別投機デコードを適用したもの. 整数演算命令を 1 サイクルあたり 2 命令以上実行できる必要がある．また，位置別投機デコードを適用したハンドラの最小実行サイクル数は 4 サイクルで，典型. Table 3. 的なハンドラの命令数は，投機デコードの 1∼3 命令. ベンチマーク. およびデコードループの 5 命令と合わせて 10∼16 命. SPECjvm. 令なので，1 サイクルあたりの発行命令数とリタイア. 表 3 評価したベンチマーク Evaluated application benchmarks. 概要. SPECjvm98 21) の各プログラムの実行時間「 Geom. Mean 」は各ベンチマーク結果の幾何平均．「 controls 」は 10 に変更した. 命令数は 4 以上が必要である．これらの条件を満たさ. jBYTEmark. Java 版 BYTEmark のインデックス値. ない場合は十分な効果を得られない可能性があり，投. JavaGrande. Java Grande Forum Benchmark Suite 15) の実行時間．Section 3 のみ測定. 機デコードする候補の数を減らすことなどが必要となる可能性がある．. APR は，64-bit プロセッサの場合でも 4 個でよい． 8 通りのカスタマイズされたハンドラを持つ場合，下. SPECjbb XMLparser. SPECjbb-2000 21) ベンチマークのスコア XMLparser for Java 11) で，サンプルの XML ファイルをパースする時間. 位 2 ビットが同じ値のバイト位置に対応するハンドラ. る相対実行速度をグラフ化した．相対実行速度は値が. は，同じ APR を操作する．. 大きいほど実行速度が速いように正規化した．. 4. 評. 価. 測定したベンチマークの多くにおいて最も効果があったのは位置別ハンドラであった．このことから，. 我々は 2 章で述べた手法を表 3 のベンチマークで. バイトコードフェッチのための高頻度で冗長なメモリ. 評価した．実行環境は表 1 に示す．POWER3 は最新. ロードが，インタプリタの実行速度を制限する最大の. の PowerPC プロセッサの 1 つである．各手法の効果. 要因であることが確かめられた．. を個別に測定するために，IBM SDK for AIX，Java この JVM は 64-bit プロセッサ上でも 32-bit 互換モー. 4.1 スタックキャッシュ手法の評価ライトスルー・スタックトップキャッシングの効果を，キャッシュしているスタックオペランドの数に対. ドで動作し，32-bit プロセッサ用のインタプリタを用. 応するキャッシュ状態ごとにカスタマイズしたハンド. いる．JIT コンパイラは使用していない．. ラを用いるダイナミック・スタックキャッシング 3) の効. edition. 10). を変更し，表 2 のインタプリタを作成した．. 表 4 に測定結果と，ベースインタプリタに対する相. 果と比較して評価した．Wt および DSC インタプリ. 対実行速度を示す．図 4 にベースインタプリタに対す. タの実行速度はそれぞれのスタックキャッシュ手法の.

(7) Vol. 43. No. SIG 8(PRO 15). Table 4. 高速 Java バイトコードインタプリタの構成法. 7. 表 4 実行結果とベースインタプリタからの速度向上率（カッコ内） Benchmark results and the improvement over the base interpreter. Each cell shows: raw result (improvement over base).. SPECjvm98 (smaller is better). mtrt jess compress db mpegaudio jack javac Geom. Mean jBYTEmark Num. Sort (larger is better) Str. Sort Bitfield FP Emu. Fourier Assignment IDEA Huffman Neural Net LU Decomp. INT Index FP Index JavaGrande Search (smaller is better) Euler MolDyn MonteCarlo RayTracer SPECjbb (larger is better) XMLparser (smaller is better). Fig. 4. Base 10.060 4.307 30.679 2.734 31.556 5.810 2.688 7.822 6.492 6.746 6.777 6.607 3.121 6.466 4.847 6.559 5.997 6.500 6.321 4.955 200.1 429.1 233.7 127.9 385.4 684 6889. Wt 9.787 (102.8%) 4.182 (103.0%) 28.868 (106.3%) 2.597 (105.3%) 30.264 (104.3%) 5.641 (103.0%) 2.564 (106.4%) 7.491 (104.4%) 6.768 (104.3%) 7.179 (106.4%) 7.075 (104.4%) 6.903 (104.5%) 3.155 (101.1%) 7.162 (110.8%) 5.261 (108.5%) 7.110 (108.4%) 6.451 (107.6%) 7.174 (110.4%) 6.746 (106.7%) 5.266 (106.3%) 190.1 (105.3%) 386.0 (111.2%) 219.0 (106.7%) 124.1 (103.1%) 370.7 (104.0%) 717 (104.8%) 6427 (107.2%). DSC 9.550 (105.3%) 4.088 (105.4%) 28.900 (110.0%) 2.525 (108.3%) 30.417 (103.7%) 5.688 (102.1%) 2.546 (105.6%) 7.397 (105.7%) 6.851 (105.5%) 7.258 (107.4%) 7.258 (107.1%) 7.116 (108.8%) 3.396 (108.8%) 7.428 (114.9%) 5.353 (110.4%) 7.160 (109.2%) 6.343 (105.8%) 7.078 (108.9%) 6.880 (108.9%) 5.343 (107.8%) 186.3 (107.4%) 390.2 (110.0%) 213.5 (109.5%) 123.2 (103.8%) 372.6 (103.4%) 710 (103.8%) 6287 (109.6%). Wt+PHC 9.437 (106.6%) 3.790 (113.6%) 22.626 (135.6%) 2.367 (115.5%) 24.347 (129.6%) 5.685 (102.2%) 2.449 (109.8%) 6.766 (115.6%) 9.384 (144.5%) 8.631 (127.9%) 8.486 (129.7%) 8.486 (128.4%) 3.088 (98.9%) 9.125 (141.1%) 6.171 (127.3%) 8.690 (132.5%) 7.866 (131.2%) 8.998 (138.4%) 8.402 (132.9%) 6.023 (121.6%) 154.9 (129.2%) 313.9 (136.7%) 188.5 (124.0%) 113.8 (112.4%) 329.6 (116.9%) 752 (109.9%) 5128 (134.3%). Wt+PHC+PSD 9.254 (108.7%) 3.692 (116.7%) 21.737 (141.1%) 2.234 (122.4%) 23.662 (133.4%) 5.834 (99.6%) 2.396 (112.2%) 6.606 (118.4%) 10.060 (155.0%) 9.170 (135.9%) 8.894 (138.3%) 8.894 (134.6%) 3.155 (101.1%) 9.511 (147.1%) 6.412 (132.3%) 9.159 (139.6%) 8.166 (136.2%) 9.368 (139.2%) 9.863 (140.2%) 6.226 (125.7%) 147.3 (135.8%) 275.0 (156.0%) 169.2 (138.1%) 103.0 (124.1%) 328.4 (117.4%) 769 (112.4%) 4926 (139.8%). 図 4 ベースインタプリタからの速度向上率 Performance improvement over the base interpreter.. 効果を示し，前者では平均 5.9%の速度向上が得られ. 評価したベンチマークのほとんどで，そのようなバイ. た．後者の前者からの速度向上は平均 1.3%であった．. トコードの実行回数は全体の 30%以下であった．. 速度向上の差が少ない原因として，我々は以下の 2. 第 2 は，ハンドラのクリティカルパス長が，バイト. つを考えている．第 1 は，スタックオペランドを 2 個. コード実行パスと，インラインされたデコードループ. 必要とするバイトコードの実行頻度が低いことである．. の，長い方で決まることである．スタックキャッシュに.

(8) 8. 情報処理学会論文誌：プログラミング. Sep. 2002. オブオーダ実行を行うプロセッサでは，ライトスルー・スタックトップキャッシングで十分である．. Wt+PHC インタプリタの実行速度が示すライトスルー・スタックトップキャッシングと位置別ハンドラの組合せにより，平均 24.4%の実行速度向上が得られた．ダイナミック・キャッシングも 3 通りのカスタマイズされたハンドラを必要とするので，コードサイズの増加に対する速度向上効果の観点から，我々の手法の組合せの方が優れている．. 4.2 位置別ハンドラの評価 Wt インタプリタに対する Wt+PHC インタプリタの速度向上は位置別ハンドラの効果を示す．多くのベンチマークで 10%以上の速度向上が得られ，平均向上率は 17.4%であった．一方，いくつかのベンチマークでは実行速度が向上しないか，または低下している．SPECjvm98 の jack のように頻繁に Java 例外をあげたり，jBYTEmark の Fourier のように頻繁にネイティブメソッドを呼び出したりするプログラムである．高頻度の BCR 再読込のオーバヘッドのため実行速度が向上しない．位置別ハンドラの問題点は，ハンドラのサイズ増加により命令キャッシュの利用効率が低下することである．しかし，全ハンドラのサイズが 64 K バイトであることと，実行頻度の高いバイトコードは全体の半分よりずっと少ない20) ことから，実行頻度の高いバイトコードハンドラは，32 K バイトの命令キャッシュですべてキャッシュできると考えられる．POWER3 プロセッサのパフォーマンスモニタによる測定結果では，. SPECjvm98 において，本手法適用後でも実行命令あたりのキャッシュミスは 1%以下であった．. Fig. 5. 図 5 バイトコード iaload のハンドラ The bytecode handlers for iaload bytecode.. 4.3 位置別投機デコードの評価 Wt+PHC インタプリタに対する Wt+PHC+PSD インタプリタの速度向上は，位置別投機デコードの効果を示す．多くのベンチマークで実行速度が向上し，. よりバイトコード実行パスがインラインされたデコードループより短くなっても実行速度は向上しない．図 5 に Java バイトコード iaload のハンドラを POWER3. 平均 4.6%，最大 14.1%の速度向上が得られた．. PowerPC プロセッサで最大の効果を得られるのは，デコードのための 1 サイクルがクリティカルパスから. プロセッサ上で実行した場合の例を示す．この例は，. なくなり，実行サイクル数が 5 サイクルから 4 サイク. 我々の JIT コンパイラ同様トラップ命令で Java 例外. ルになる場合である．JavaGrande の Euler のように，. を検出する最適化14)を適用している．Wt インタプリ. クリティカルパス長が 4 サイクル以下のハンドラの実. タはスタックキャッシュにより実行サイクル数が 1 サ. 行頻度が高く，間接分岐のオーバヘッドがボトルネッ. イクル減っている．しかし，DSC インタプリタは，イ. クとなっていたプログラムで効果が高い．. ンラインされたデコードループ（灰色の背景）のため. 一方，本手法により SPECjvm98 の jack の実行速. に実行サイクル数が Wt インタプリタと変わらない．. 度が低下している．高頻度の Java 例外により，例外. 今回評価した手法では効果の差が少ないので，. ハンドラから実行を再開するために，頻繁に 3 個の候. PowerPC のようにロードのレイテンシが短くアウト. 補すべてを投機デコードするオーバヘッドが原因と考.

(9) Vol. 43. No. SIG 8(PRO 15). 高速 Java バイトコードインタプリタの構成法. えられる．. 9. さの予測から決定するので，デコード結果の再利用に. 5. 関連研究. レジスタ移動命令が必要となる．VLIW プロセッサで. スレッデッドコード 1),2)は，デコードループをイン. 処理できるので，実行時オーバヘッドがない．しかし，. は 2 個のレジスタ移動命令を未使用の実行ユニットで. ラインすることでディスパッチのためのサブルーチン. スーパスカラプロセッサでは，ハードウェア資源の制. コールのオーバヘッドを減らす手法である．ハンドラ. 約により実行速度が低下する可能性がある．. の終わりから，デコードループが次のハンドラへジャンプするまでの短いパスで連続する間接分岐を避け，. 6. おわりに. オーバヘッドを減らす．ILP を利用するプロセッサに. 本稿では，PowerPC プロセッサ用バイトコードイ. おける副次的効果は，デコードループの実行時オーバ. ンタプリタを高速化する手法と，それらと従来手法. ヘッドを軽減することである．デコードループとバイ. との効果的な組合せを示した．また，これらの手法を. トコード実行パスの間は依存がなく，バイトコード実. 他のハードウェアおよびソフトウェア環境に移植する. 行パスのほとんどは逐次実行される命令列なので，デ. 場合の問題点について議論した．そして，それぞれの. コードループを未使用の実行ユニットで実行でき，そ. 手法の実行速度向上への貢献を，主要な Java ベンチ. の実行サイクルを隠せる．. マークを用い IBM POWER3 プロセッサ上で評価し. スタックキャッシュは，スタックオペランドをプッシュ・ポップするためのメモリ操作を減らす手法である．スタック型言語ではスタックトップ付近を操作す. た．本稿で述べたすべての手法を適用した場合，平均. 30.5%，最大 56%の速度向上が得られた．謝辞本稿をまとめる際に貴重な助言をいただいた，. る頻度が高いので，それらをレジスタにキャッシュし. 日本 IBM 東京基礎研究所ネットワークコンピューティ. て，データが使用可能になるまでのレイテンシを減ら. ングプラットフォームの河内谷清久仁研究員に深く感謝. す．ダイナミック・キャッシング 3)は，キャッシュ状態. します．また，本稿に対して助言をいただいた，IBM. ごとにカスタマイズしたハンドラでスタックへのメモ. T.J. Watson 研究所の David P. Grove 研究員およ. リ操作を最適化し，キャッシュ状態をハンドラによる. び日本 IBM 東京基礎研究所ネットワークコンピュー. ステートマシンで効率良くトラックする手法である．しかし，アウトオブオーダ実行を行うプロセッサではストールしたストア命令が後続命令の実行を妨げないので，ストアの数を減らすことによる実行速度向上の効果は少ない．ロードのレイテンシが 1∼2 サイクルの場合，ライトスルー方式でスタックトップデータのみをキャッシュする簡単な実装でスタックキャッシュの効果の大半を得ることができる．4 章で示した結果でも，ほとんどのベンチマークにおいてダイナミック・キャッシングを用いた場合との効果の差は非常に小さい．バイトコードフェッチの冗長なメモリロードを減らす方がより効果的であった．投機デコードを行うパイプライン化インタプリタ6),7) は，バイトコードのフェッチ，デコード，ディスパッチ，実行の各フェーズ間の依存をソフトウェアパイプライン手法により解消し，並行して実行する手法である．Hoogerbrugge らは VLIW プロセッサ用のインタプリタで実装した．ハンドラは，次の次のバイトコードのオペコードの候補数個を投機的にデコードし，正しい候補が確定した時点でそのデコード結果を選択する．複数候補のデコードのオーバヘッドを減らすために，可能ならばデコード結果を再利用する．彼らの実装は候補とレジスタの対応を次の命令の長. ティングプラットフォームの小野寺民也研究員に感謝します．. 参考文献 1) Bell, J.R.: Threaded Code, Comm. ACM, Vol.16, No.6, pp.370–372 (1973). 2) Dewar, R.B.: Indirect Threaded Code, Comm. ACM, Vol.18, No.6, pp.330–331 (1975). 3) Ertl, M.A.: Stack Caching for Interpreters, SIGPLAN ’95 Conference on Programming Language Design and Implementation (PLDI ), pp.315–327 (1995). 4) GNU Project: GCC Home Page. http://www.gnu.org/software/gcc/gcc.html 5) Gosling, J., Joy, B. and Steele, G.: The Java Language Specification, Addison-Wesley (1996). ISBN 0-201-63451-1. 6) Hoogerbrugge, J. and Augusteijn, L.: Pipelined Java Virtual Machine Interpreters, Lecture notes in computer science 1781 CC/ETAPS 2000, pp.35–49 (2000). 7) Hoogerbrugge, J., Augusteijn, L., Trum, J. and de Wiel, R.V.: A Code Compression System Based on Pipelined Interpreters, SOFTWARE — Practice and Experience, Vol.29, No.11, pp.1005–1023 (1999)..

(10) 10. Sep. 2002. 情報処理学会論文誌：プログラミング. 8) Intel Corp.: Intel IA-64 Architecture Software Developer’s Manual, Volume 3: Instruction Set Reference, Revision 1.1 (2000). Document Number: 246319-002. 9) Intel Corp.: Itanium Processor Microarchitecture Reference for Software Optimization (2000). Document Number: 245473-001. 10) International Business Machines, Inc.: IBM SDK, Java edition. http://www.ibm.com/java/ 11) International Business Machines, Inc.: XML Parser for Java. http://www.alphaworks.ibm.com/tech/xml4j 12) International Business Machines, Inc.: The PowerPC Architecture: A specification for a new family of RISC processors (1994). ISBN 1-55860-316-6. 13) International Business Machines, Inc.: The PowerPC Compiler Writer’s Guide (1996). Publication Number: SA14-2094-00. 14) Ishizaki, K., Kawahito, M., Yasue, T., Takeuchi, M., Ogasawara, T., Suganuma, T., Onodera, T., Komatsu, H. and Nakatani, T.: Design, Implementation, and Evaluation of Optimizations in a Just-In-Time Compiler, ACM 1999 Java Grande Conference, pp.119– 128 (1999). 15) Java Grande Forum: Java Grande Forum Benchmark Suite. http://www.epcc.ed.ac.uk/javagrande/ 16) Lindholm, T. and Yellin, F.: The Java Virtual Machine Specification, Addison-Wesley (1996). ISBN 0-201-63452-X. 17) O’Connel, F.P. and White, S.W.: POWER3: The next generation of PowerPC processors, IBM Journal of Research and Development, Vol.44, No.6, pp.873–884 (2000). 18) Paleczny, M., Vick, C. and Click, C.: The Java HotSpot Server Compiler, Java Virtual Machine Research and Technology Symposium (JVM ’01 ), pp.1–12 (2001). 19) Papermaster, M., Dinkjian, R., Mayfield, M., Lenk, P., Ciarfella, B., O’Cornnel, F.P. and DuPont, R.: POWER3: Next Generation 64bit PowerPC Processor Design (1998). http://www.ibm.com/servers/eserver/pseries/ hardware/whitepapers/power3wp.html 20) Radhakrishnan, R., Vijaykrishnan, N., John, L.K., Sivasubramaniam, A., Rubio, J. and Sabarinathan, J.: Java Runtime Systems: Characterization and Architectural Implications, IEEE Trans. Comput., Vol.50, No.2, pp.131–146 (2001). 21) Standard Performance Evaluation Corporation: SPEC JVM98 Benchmarks and SPECjbb-. 2000. http://www.spec.org/osg/jvm98/および http://www.spec.org/osg/jbb2000/ 22) Suganuma, T., Ogasawara, T., Takeuchi, M., Yasue, T., Kawahito, M., Ishizaki, K., Komatsu, H. and Nakatani, T.: Overview of the IBM Java Just-in-Time compiler, IBM System Journal, Vol.39, No.1, pp.175–193 (2000). 23) Suganuma, T., Yasue, T., Kawahito, M., Komatsu, H. and Nakatani, T.: A Dynamic Optimization Framework for a Java JustIn-Time Compiler, Object-Oriented Programming, System Languages, and Application (OOPSLA ’01 ), pp.180–194 (2001). 24) Sun Microsystems: The Java HotSpot Virtual Machine Technical White Paper (2001). http://java.sun.com/products/hotspot/ (平成 14 年 1 月 7 日受付) (平成 14 年 3 月 16 日採録) 緒方一則（正会員）. 1967 年生．1990 年東京工業大学工学部電気電子工学科卒業．同年，日本 IBM（株）入社．現在，東京基礎研究所において，Java 仮想マシンのインタプリタの研究に従事．小松秀昭（正会員）. 1960 年生．1985 年早稲田大学大学院理工学研究科電気工学専攻修了．同年日本 IBM（株）東京基礎研究所入社．コンパイラ，アーキテクチャ，並列処理の研究に従事．博士（情報科学）．中谷登志男（正会員）. 1975 年早稲田大学理工学部数学科卒業．同年日本 IBM（株）野洲工場入社．1983 年から米国プリンストン大学大学院（コンピュータ・サイエンス学科）．1985 年同大学から M.S.E. および M.A.，1987 年同大学から Ph.D. 同年より，日本アイ・ビー・エム（株）東京基礎研究所に移り，VLIW コンパイラ，HPF コンパイラ，JIT コンパイラ等のプロジェクトを担当．一貫して，プログラムを最適化して高速に実行させるための新しいソフトウェア技術について研究開発している．現在，IBM. Distinguished Engineer，ネットワーク・コンピュ― ティング・プラットフォーム担当．.

(11)