Comments
Description
Transcript
Java仮想マシンにおける オブジェクトキャッシュ機構の
東海大学大学院 2002 年度 修士論文 Java 仮想マシンにおける オブジェクトキャッシュ機構の検討と評価 および Java プロセッサに関する研究 指導教員 清水 尚彦 助教授 東海大学大学院 工学研究科 電気工学専攻 近 千秋 目次 第 1 章 はじめに 1 第 2 章 Java Virtual Machine(JVM) 2.1 Java プログラムの実行 . . . . . . . . . 2.2 オブジェクト操作命令 . . . . . . . . . 2.2.1 命令動作 . . . . . . . . . . . . . 2.3 配列アクセス命令 . . . . . . . . . . . . 2.3.1 配列アクセス時に発生する例外 2.3.2 命令動作 . . . . . . . . . . . . . 2.4 参照の解決に対する既存技術 . . . . . 2.4.1 quick 擬似命令 . . . . . . . . . 2.4.2 コンスタントプールタグ . . . . 第 3 章 Object Cache 3.1 理論 . . . . . . . . . . . . . . . 3.2 命令動作 . . . . . . . . . . . . . 3.2.1 静的参照 . . . . . . . . . 3.2.2 動的参照 . . . . . . . . . 3.2.3 定数参照 . . . . . . . . . 3.2.4 クラス参照 . . . . . . . 3.2.5 配列アクセス . . . . . . 3.3 オブジェクトキャッシュの利点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第 4 章 シミュレーションによる性能評価 4.1 kaffe へのオブジェクトキャッシュの実装 4.2 ベンチマークプログラム . . . . . . . . . 4.2.1 SPECjvm98 . . . . . . . . . . . . 4.2.2 Caffeine Mark 2.5 . . . . . . . . . 4.2.3 Embedded Caffeine Mark . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 6 7 9 9 10 11 11 12 . . . . . . . . 13 13 15 15 16 17 17 17 24 . . . . . 26 26 29 29 29 30 4.3 ベンチマーク結果 . . . . . . . . 4.3.1 SPECjvm98 . . . . . . . 4.3.2 CaffineMark 2.5 . . . . . 4.3.3 Embedded CaffeineMark 4.3.4 全体的な傾向 . . . . . . . . . . . 31 31 33 33 51 Java プロセッサ 全体構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ソフトウェアに対する要求 . . . . . . . . . . . . . . . . . . . . . . ガーベッジコレクタ . . . . . . . . . . . . . . . . . . . . . . . . . 52 52 57 58 第 6 章 関連文献 6.1 Virtual Address Object Cache . . . . . . . . . . . . . . . . . . . . 6.2 動的再構成部分を持つ Java プロセッサ . . . . . . . . . . . . . . . 59 59 60 第 7 章 結論 61 謝辞 62 業績 63 第5章 5.1 5.2 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 図目次 1.1 アクセルレータ型 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 ハード ウェア JIT 型 . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Java ベース型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 オブジェクト操作命令 . . 2.2 getfield 命令の実行処理 2.3 配列アクセス命令 . . . . . 2.4 配列ロード 命令の実行処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8 9 10 3.1 オブジェクトキャッシュの構成例 . . . . . . . . . . . . . . . . 3.2 オブジェクトキャッシュを使用する場合の基本的な実行の流れ 3.3 静的オブジェクトの参照をする場合 . . . . . . . . . . . . . . . 3.4 動的オブジェクトの参照をする場合 . . . . . . . . . . . . . . . 3.5 定数の参照をする場合 . . . . . . . . . . . . . . . . . . . . . . 3.6 クラスの参照をする場合 . . . . . . . . . . . . . . . . . . . . . 3.7 配列アクセスを行なう場合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 19 20 21 22 22 23 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 . . . . . . . . . . . . . . . . . . . . . . . . 27 28 34 34 35 35 36 36 37 37 38 38 オブジェクトキャッシュ構造体 . . . . オブジェクトキャッシュ内の探索処理 SPECjvm98 - キャッシュ容量 2KB . SPECjvm98 - キャッシュ容量 4KB . SPECjvm98 - キャッシュ容量 8KB . SPECjvm98 - キャッシュ容量 16KB . SPECjvm98 - compress . . . . . . . . SPECjvm98 - db . . . . . . . . . . . SPECjvm98 - mpegaudio . . . . . . . SPECjvm98 - jess . . . . . . . . . . . SPECjvm98 - javac . . . . . . . . . . SPECjvm98 - jack . . . . . . . . . . 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 4 . . . . . . . . . . . . . . . . . . . . . . . . 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 4.28 4.29 4.30 4.31 4.32 4.33 4.34 SPECjvm98 - キャッシュヒット率 - キャッシュ容量 2KB . . SPECjvm98 - キャッシュヒット率 - キャッシュ容量 4KB . . SPECjvm98 - キャッシュヒット率 - キャッシュ容量 8KB . . SPECjvm98 - キャッシュヒット率 - キャッシュ容量 16KB . . SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 2KB . SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 4KB . SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 8KB . SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 16KB SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 2KB . SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 4KB . SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 8KB . SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 16KB CaffeineMark2.5 - キャッシュ容量 2KB . . . . . . . . . . . . CaffeineMark2.5 - キャッシュ容量 4KB . . . . . . . . . . . . CaffeineMark2.5 - キャッシュ容量 8KB . . . . . . . . . . . . CaffeineMark2.5 - キャッシュ容量 16KB . . . . . . . . . . . CaffeineMark 2.5 - overall . . . . . . . . . . . . . . . . . . . EmbeddedCaffeineMark - キャッシュ容量 2KB . . . . . . . . EmbeddedCaffeineMark - キャッシュ容量 4KB . . . . . . . . EmbeddedCaffeineMark - キャッシュ容量 8KB . . . . . . . . EmbeddedCaffeineMark - キャッシュ容量 16KB . . . . . . . Enbedded CaffeineMark - overall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 48 48 49 49 50 5.1 5.2 Java プロセッサの内部構成 . . . . . . . . . . . . . . . . . . . . . スタックユニット . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 56 第 1 章 はじめに 近年 Java 言語によるプログラム開発がその対象分野を大きく広げている．Java 言語は 1995 年に Sun Microsystems 社 [1] より発表された．Java 言語は C++言 語のようなオブジェクト指向言語であり，特にネットワーク，インターネット関 係の標準クラスを多数持っていたため，WEB 開発の分野で急速に普及が進んで いった．また，Java 言語の持つ特性から他の分野，主にサーバ分野，組み込み分 野での使用が広がっている．Java 言語の特性としては以下のような事柄が挙げら れる． 1. オブジェクト指向 2. プログラムサイズ 3. 堅牢性 4. クロスプラットフォーム Java 言語はオブジェクト指向言語として開発された．一般にオブジェクト指向 言語は，プログラムを多数のパーツに分割し，プログラムの残りのパーツからプ ログラミングの詳細を隠蔽する．オブジェクト同士の通信は制御可能なインター フェースを使用し，プログラム同士の相互依存を減らす．これは開発者全員がプ ログラム全体の詳細を把握していなくてもよいということである．また，クラス ライブラリを用意することで，新たなコードを書く為の負担は大幅に軽減される． 例えば，コンピュータ上に GUI コンポーネントを用いたプログラムを作成する場 合，クラスライブラリは大きな助けになる筈である．これらは全て生産性の向上 につながっている．よく知られるオブジェクト指向言語としては C++が挙げら れる．C++プログラムはそれ自身のみでコンピュータ上で実行可能なネイティブ コード である．これは，プログラムサイズが必然的に大きくなることを示す． Java プログラムは Java クラスファイルにコンパイルされる．Java プログラム は実際にはコンピュータ上に存在する Java 仮想マシンによって実行される．よっ 1 第 1 章 はじめに て，Java プログラムは自己完結する必要がなく，必然的にプログラムサイズは小 さくなる．プログラムサイズが小さいということはネットワーク上で流通させる 上で重要である．これが Java が WEB 開発を中心に普及していった大きな要因と いえる． また，Java はセキュリティーの面でも優れている．Java の実行環境は Java コー ド の監視を行っており，疑わしいコードは処理しない．開発環境も，参照型を使 うことで開発者に明示的にポインタを可視化せず，ポインタ操作を不能にしてい る．これによって，メモリの安全性を高めることが出来る． そして，Java が普及した最も大きな要因といえるのがクロスプラットフォーム であることである．前述したように，Java プログラムはコンピュータ上の Java 仮 想マシンによって実行される．Java 仮想マシンは一般的にはソフトウェアとして 実装され，コンピュータ上ではアプリケーションの一つとして動作する．つまり Java クラスファイルは実行中のコンピュータの OS，プロセッサ等の種類に拠ら ず，Java 仮想マシンさえ実装していればどのようなコンピュータ上でも実行可能 である．しかし，Java 仮想マシンは基本的には Java 仮想マシン命令を逐次解釈し ながら実行するプログラム（ インタプリター）であり，実行速度の点で劣るとい う欠点があった．そこで，Java の速度面を改善する為に一般的に用いられるのが JIT コンパイラである．JIT コンパイラは実行するバイトコード を，実行するコ ンピュータに則したネイティブコードに変する．変換されたコードはメモリ中の コードキャッシュに置かれ，バイトコードの代わりにコンパイルされたコードを実 行することで処理速度の向上を図っている．この手法はパーソナルコンピュータ， サーバ等の使用可能なリソースが比較的大きな分野では非常に有効であり，通常 はこの手法で実装されている．しかしながら，組み込み分野のように使用可能な リソースが制限される環境では有効とはいえない．JIT コンパイラを立ち上げる ことで，JIT コンパイラの実行自体がオーバーヘッド となり，更にコード キャッ シュも満足な容量を使用することが難しい為，パーソナルコンピュータ，サーバ と同じように高いパフォーマンスを得ることとは難しい．そこで現在注目されて いるのが，バイトコード を実行することが可能なハード ウェア，Java プロセッサ である． Java プロセッサは，ハード ウェアによる Java 仮想マシン命令の実行エンジン である．組み込み分野では，JIT コンパイラよりも良好なパフォーマンスを得る ことが出来る．携帯電話，PDA 等の携帯情報機器に Java 実行の為のアプリケー ションプロセッサとしての採用が進んでいる．現状では採用実績の無さ，リアル タイム対応への問題から難しいが，将来的には Java で記述したシステム上でホ ストプロセッサとして動作する可能性もある．また，より小型なシステムでの採 2 第 1 章 はじめに Prefetcher Host Decoder MEM Address Accelerator 図 1.1: アクセルレータ型 用も考えられる． 一般に Java プロセッサと呼ばれるものは，大きく次の三種 類に分類することができる． • アクセラレータ型 (図 1.1) • ハード ウェア JIT 型 (図 1.2) • Java ベース型 (直接実行型)(図 1.3) アクセラレータ型は，既存のホストプロセッサとメモリバスの間などに命令変換 用のハード ウェアを配置し，Java 仮想マシン命令をホストプロセッサ命令に変換 する．アクセラレータ LSI はクロック当たり一つのホストプロセッサ命令を出力 し，ホストプロセッサが実行する．ハード ウェア JIT 型は，ソフトウェア JIT コ ンパイラの仕組みをそのままハード ウェアに落とし込んだものと言える．ソフト ウェア JIT コンパイラの場合と同様に変換した命令の為のコード キャッシュが必 要である．Java ベース型は，Java 仮想マシン命令をプロセッサが直接デコードし 実行する，バイトコード をネイティブコード として持つプロセッサと言える． 以上のように Java 実行環境としてはインタプリター型，JIT コンパイラ型，ハー ド ウェア実行型の三種類に大別できる．これら Java 実行環境で共通する実装上の 問題点として，Java の実行処理時に動的に解決されるオブジェクト参照の扱いが ある．これらのオブジェクト参照は初期状態では文字列によるシンボリック参照 であり，実際のオブジェクトのアドレスはこれらの文字列を使って複数のテーブ ルから検索を行なわなくてはならない．検索処理は実行上大きなオーバーヘッド となる為，これらの処理を簡略化，或いはスキップする方法が必要となる．我々 はオブジェクト参照の処理を解決する手法としてオブジェクトキャッシュの使用 を提案している．我々のオブジェクトキャッシュは，内部にオブジェクトのアド 3 第 1 章 はじめに Host IN MEM OUT Translation Cache Code Translation 図 1.2: ハード ウェア JIT 型 Host MEM Java Processor MEM 図 1.3: Java ベース型 レスと実行情報を格納し，Java プロセッサの命令実行をサポートする． 本論分は次のように構成される．第 2 章では Java プログラムの実行に関する 詳細と，その中で我々が問題とする”オブジェクト参照の解決”に関して説明する． 第 3 章では我々の提案するオブジェクトキャッシュについて説明を行い，第 4 章で はオブジェクトキャッシュをソフトウェア Java 仮想マシンに実装し，ベンチマー クプログラムを用いて行った性能評価について述べる．第 5 章では，オブジェク トキャッシュを使用した Java プロセッサのアーキテクチャについて説明する．ま た，第 6 章では関連する研究について説明し，第 7 章で結論を述べる． 4 第2章 2.1 Java Virtual Machine(JVM) Java プログラムの実行 Java プログラムは Java 仮想マシンによって実行処理される．Java 仮想マシン は Java 仮想マシン命令が実行可能であり，実行時に様々な記憶域処理を行なう抽 象的なコンピュータとして定義される．実装形態は問われるものではなく，一般 的に既存のコンピュータシステム上では，Java 仮想マシンはエミュレータとして 実現される．一般的なコンピュータ上では，Java プログラム実行の際にはエミュ レータを起動し ，実行する Java プログラムはその引数として渡される．ここで は例としてクラス foo を実行すると仮定し ，典型的な Java 仮想マシンの動作を 簡単に説明する． Java 仮想マシンを実行すると，まずガーベッジコレクタの起動，ヒープ領域の 確保等，自らの初期化動作を行なう．初期化の終了後，foo の実行に移るところ で，クラス foo がロード されていないことを検出する．クラスがロード されてい ない場合，Java 仮想マシンは指定されたクラスパスより該当するクラスのロード を開始する． ロード されたクラス foo は，実行時クラスに展開されリンクされる．まず，Java 仮想マシンは，クラス foo の Java クラスファイルとしての妥当性を検証する．こ こで問題が検出された場合はエラーがスローされ，Java 仮想マシンは終了する． 問題が検出されなければ，foo の任意のデータを Java 仮想マシン内部で使用する 各種テーブルに登録する．ここで，実装によっては静的にリンクされるシンボル 参照の解決を行なうが，必須ではない．ここで静的なシンボル参照を解決しない 場合は，実行時に必要に応じて解決されていく． 5 第 2 章 JVM リンクされたクラスは，初期化コードに応じて初期化される．この際，クラス foo にスーパークラスが存在する場合，スーパークラスが初期化されたいる必要 がある．クラスが初期化された後，Java 仮想マシンは main メソッド の実行を開 始し，実際にユーザーが動作させたいプログラムが開始されることになる．以後， Java 仮想マシンは必要に応じてクラスのロード を行ないながら foo を実行する． クラスフィルには実行可能なメソッド の Java 仮想マシン（バイトコード ）命令 配列が含まれている．Java 仮想マシン命令は，組み込まれた命令実行エンジンに よって解釈，実行される．実行エンジンは実装により形は様々であり，インタプ リター型，コンパイラ型等の種類がある．Java 仮想マシンはスタックマシンであ る為，多くの命令は単純に処理を行なうことが可能である．しかしながら，一部 の命令は次に示すような複雑な処理を必要とする． • オブジェクト参照 • メモリ確保 • 例外処理 これらの処理を効率的に行なうことが Java のパフォーマンスを向上させる大き なポイントの一つである．この点に関しては後述する． Java 仮想マシンは命令実行と共にガーベッジコレクタを動作させている．ガー ベッジコレクタは Java 仮想マシンに割り当てられたヒープ領域 ( メソッド 領域を 含む場合もある) を監視し ，容量が足りなくなった場合にガーベッジコレクショ ンを実行する．ガーベッジコレクタは，プログラム中で必要が無くなったデータ を削除し ，必要なデータも再割り当てすることでヒープの空き領域を確保する． 多くの場合，ガーベッジコレクションの実行が Java プログラム実行の最大のオー バーヘッド となる．1 2.2 オブジェクト 操作命令 前述の通り，Java 仮想マシンは実行時に命令実行以外に様々な処理を行い，ま た命令実行自体も複雑な処理を行なう必要がある．この中で我々が特に着目した 点は，オブジェクト参照の解決に関する処理である．Java 仮想マシン命令中には， 実行時にコンスタントプール内に文字列として表されるオブジェクト参照を，実 際のメモリアドレスに変換してオブジェクトにアクセスする必要がある命令が含 1 Java 仮想マシンの動作に関して詳細に知る必要がある場合 [2][3][4][8] を参照すること．また， ガーベッジコレクションに関しては [10] 等が参考になる． 6 第 2 章 JVM anewarray checkcast getfield getstatic instanceof invokeinterface invokespecial invokestatic invokevirtial ldc ldc w ldc2 w multianewarray new putfield putstatic 図 2.1: オブジェクト操作命令 まれる．ここではこれらの命令をオブジェクト 操作命令と呼ぶことにする．オブ ジェクト操作命令を図 2.1 に示す．まず，オブジェクト操作命令に必要となる参 照の解決処理について説明する． 2.2.1 命令動作 図 2.2 より，オブジェクト操作命令の命令動作を説明する．ここでは，例とし て getfield 命令の命令動作について説明する．命令列から getfield がフェ ッチされると，Java 仮想マシンは直渡しオペランド として 2 バイトのコンスタ ントプールインデックスを得る．getfield 命令の場合，コンスタントプール内 の CONSTANT Fieldref エントリーを指し，更に CONSTANT Fieldref が CONSTANT Class エントリーと CONSTANT NameAndType エントリーを指す．CONSTANT Class と CONSTANT NameAndType はコン スタントプ ール内の Constant Utf8 エントリーを指し，ここから目的のフィールドを指す Utf8 文字列を取 得する．この文字列を使用して，まずクラステーブルよりクラスの検索を行い， 該当するクラスのフィールド テーブルより目的とするフィールド の情報を得る． 7 第 2 章 JVM Class foo Class Table Class bar Field Table constantpool bar 0x1110 bar / a a method code : getfield 0x1110 : Offset Address instance object bar_ objectref bar_ a Stack 図 2.2: getfield 命令の実行処理 これら文字列による参照をシンボリック参照と呼ぶ．図 2.2 の場合，フィールド 情報よりフィールド エントリーのオブジェクト先頭からのオフセットアドレスを 取得し，スタック上のオブジェクトの先頭アドレスを示すオブジェクト参照に加 算を行い，目的とするフィールド のアドレスを得ている．ここで問題となるのが， フィールド のアドレスを得るまでの処理の過程である．前述したようにクラス検 索，及びフィールド 検索で使用される検索キーは Utf8 文字列であり，複数のテー ブルの中で文字列比較を行いながら，目的とするフィールド を検索していかなく てはならない．文字列検索処理は，他のオブジェクト操作命令に於いても実行し なければならず，これら命令の実行処理が複雑化する主な原因となっている． このように，コンスタントプール中の Utf8 文字列より実際のオブジェクトのア ドレスを得る事を，オブジェクト 参照の解決と呼ぶ．ここで，参照の解決ルーチ ンをオブジェクト操作命令が実行される毎に行なうとすれば，Java プログラム実 行上の大きなオーバーヘッド となってくる．そこで，オブジェクト参照の解決に よるオーバーヘッドを避けるため，Java 仮想マシンには一度解決されたオブジェ クト参照を保存する機能が必要となる． 8 第 2 章 JVM iaload laload faload daload aaload baload caload saload iastore lastore fastore dastore aastore bastore castore sastore arraylength 図 2.3: 配列アクセス命令 2.3 配列アクセス命令 Java 仮想マシンに於いて配列に対するアクセスは単純にデータアクセスをする だけではなく，実行時の例外を検出しなければならない．配列にアクセスするた めの命令を図 2.3 に示す．配列アクセス命令時に発生する例外と，命令動作につ いて説明する． 2.3.1 配列アクセス時に発生する例外 Java ではデータの安全性を確保するために配列データへのアクセス時に，アク セス対象のデータに対するインデックス値，格納するデータのデータ型を監視し ている．アクセス対象データへのインデックス値が，データが格納される配列の 長さを超える場合，メモリ内データの不正な取得，或いは書き換えを行なうこと になる．これはプログラム実行上の安全性が損なわれる危険があるため，Java 仮 想マシンは例外を発生させる必要がある．また，参照型として定義されている配 列に，プリミティブ型のデータを書き込むことは，ポインタの不正な書き換えに 9 第 2 章 JVM if ((index < 0) || (index >= length)) Exception index length array bar : : data array bar stack 図 2.4: 配列ロード 命令の実行処理 つながる．そこでやはり，配列アクセス時にソースのデータ型とディスティネー ションのデータ型を比較し，データ型が異なる場合は例外を発生させる． 2.3.2 命令動作 図 2.4 に配列ロード 命令の動作を示す．スタック上には配列参照型と配列の要 素へのインデックス値が積まれている．配列参照型は配列オブジェクトのアドレ スを示し，配列オブジェクトには配列長，配列のデータ型，配列の要素，或いは 配列の要素へのポインタ等のデータが含まれる．これらのデータを取得し，例外 のチェックを行ない目的データにアクセスを行なう．この時，配列の一つの要素 にアクセスするために複数のアドレス計算と，メモリアクセスが必要になる．つ まり，配列アクセスに伴う例外のチェックは Java プログラム実行時のオーバヘッ ドと成り，これら処理を最適化することにより，Java 仮想マシンの性能向上を見 込める． 10 第 2 章 JVM 2.4 2.4.1 参照の解決に対する既存技術 quick 擬似命令 Sun Microsystems[1] の Java 仮想マシンではオブジェクト参照が解決したオブ ジェクト操作命令を， quick 修飾のついた別の命令に書き換えることでオブジェ クトアクセスの最適化を行い，オブジェクトアクセスの高速化を図る [2]2 ． Sun の Java 仮想マシンのインタプ リタエンジンにおいて，オブジェクト操作 命令は最初の実行時にはコンスタントプール内のシンボリック参照によってオブ ジェクト参照の解決を行なう．一度解決された命令の参照の解決に関する情報は， ガーベッジコレクトによる再配置が実行されるまでは有効である．そこで，解決 された命令を quick 修飾子の付いた新たな命令に書き換え，解決した参照に関 する情報を quick 命令の直渡しオペランド，該当するコンスタントプールエント リーに上書きする．これにより命令長が変化することは無い．一度解決された命 令に関して，該当するコンスタントプールエントリーは，シンボリック参照から 直接参照（ 多くの場合アドレス）に書き換えられている．命令の直渡しオペラン ドには，参照型からのオフセットアドレス，呼び出したいメソッド の引数の数等， 命令実行に必要な情報が埋め込まれる．このように命令列とコンスタントプール を書き換えることで，Utf8 文字列を使ったオブジェクトアドレスの検索を行なう 必要が無くなり，命令実行を最適化することが可能になる． quick 命令の問題点として，実現の為に命令列の書き換え，及びコンスタン トプールの書き換えが必要である事が挙げられる．まず，ガーベッジコレクトに よるオブジェクト再配置が行われた場合，書き換えられた命令列とコンスタント プールは無意味な物になり，クラスを再ロードし初期化を行なう必要がある．ま た，同様のコンスタントプールエントリーを参照している命令同士で， quick 擬 似命令に変換された命令とされてない命令が存在する可能性があり，解決後の命 令列とコンスタントプールを新たに持つ必要が出てくる可能性がある． これは 実行時間，メモリ使用量の点で大きなオーバーヘッドとなる可能性がある．また， クラスファイルの多くの部分を書き換える必要があるため，データの ROM 化が 難しい．このように，実行上，またハード ウェア化という観点から問題が生じる 2 ソフトウェア Java 仮想マシンに於いて， quick 擬似命令による高速化はクラシックな高速 化手法であり，現在では主に JIT コンパイラが用いられている．また，KVM と呼ばれる組込み 機器向けの小型の Java 仮想マシンでは，FAST 命令として quick 命令と同様の実装が行なわれて いる． 11 第 2 章 JVM と考えられる．3 2.4.2 コンスタントプールタグ kaffe[26] ではアクセスフラグに解決ビットを定義することで参照の解決の有無 を判別する．Java クラスファイルのコンスタントプールエントリータグのビット フィールドに於いて未使用のビットに注目し，このビットで参照の解決の有無に 関する情報を示す．該当するコンスタントプールエントリーは直接参照に上書き され，2 度目の実行からはコンスタントプールタグの解決ビットが有効であるこ とを確認し，直接参照を用いて実行処理を行なうことが可能になる． この手法の問題点として，参照の解決に関する情報を格納する場所として，コ ンスタントプールエントリーの 1 スロット分のみが割り当てるられる点である． つまり，4 バイトを越えるデータを実行時に必要とする命令に関しては，この手 法を用いることが出来ない．実際に，kaffe に於いてこの手法が用いられているの は，クラスに対する参照の解決のみであり，フィールド，メソッドに対してはシ ンボリックリンクによる解決を行なっている． オブジェクトキャッシュも同様に，オブジェクト参照の解決の有無と命令動作 に必要なデータを保持することで，以降の命令動作を高速に行なうことが可能で ある．そして，前述した方法の問題点に対して，解決する手法を持っている．ま た，配列アクセス命令の最適化に関してもオブジェクトキャッシュが有効である． 次の章では，我々の提案するオブジェクトキャッシュに関して説明をする． 3 なお現在，Sun Microsystems の Java 仮想マシンは Sun の Java ホームページで登録を行な うことで無料でソースコード をダウンロード することが出来る． 12 第3章 Object Cache オブジェクト操作命令の実行時におけるオブジェクト参照解決ルーチンのオー バーヘッド と，それに伴う解決済みの参照を保存する事の必要性，また配列アク セスに伴う例外チェックの為のオーバーヘッドについて述べてきた．我々は，これ らの問題を解決するためにオブジェクトキャッシュを使用する事を提案する．オブ ジェクトキャッシュは，Java プロセッサのオブジェクト操作命令の実行をサポー トする．本章ではオブジェクトキャシュと，オブジェクトキャッシュ使用時の命 令動作について説明する． 3.1 理論 前章で述べてきたように，解決されたオブジェクト操作命令，コンスタントプー ルエントリーを保存しておくことで命令実行を最適化することが可能になるが， 問題はこれらを保存していく領域をど う確保するかである． quick 擬似命令，コ ンスタンプールタグを使用する方法では，既存の領域を上書きすることで実現を 行なっていると述べたが，そのために発生する問題も存在した．我々の提案する オブジェクトキャッシュは，オブジェクト参照の解決の有無，直接参照，或いは 間接参照，命令実行に必要であるデータをキャッシュする新たな領域である．ま ず，オブジェクトキャッシュがオブジェクト参照の解決を保存する領域として有 効である事を説明する． 図 2.1 に示した，我々がオブジェクト操作命令と呼んでいる命令は，命令の直渡 しオペランド としてコンスタントプールのインデックス値を持っている．このイ ンデックス値は，各々の命令に対して有効なコンスタントプールエントリーを指 し示し，ここから目的のオブジェクトが検索されていく．また，命令実行に必要 となる情報は，目的とするオブジェクトの構造体，或いは目的とするオブジェク トをメンバーとして持つオブジェクトの構造体に含まれていると考えられる．つ まり，オブジェクト操作命令の実行に必要となる情報は，直渡しオペランドであ 13 第 3 章 Object Cache るインデックス値から決定されるコンスタンプールエントリから得られる．また， 一度解決されたコンスタントプールエントリーは，同じエントリーを参照してい る他の命令に対しても有効であるといえる．そこで，個々のコンスタントプール エントリーに関連付けたデータ領域を用意することで，オブジェクト操作命令実 行時にこの領域から命令実行に必要なデータを取得してくることが可能であると いえる．これが，我々が考えるオブジェクトキャッシュの基本的な考え方である． 前述したように，オブジェクトキャッシュの任意のエントリーはコンスタント プールの任意のエントリーに一意に関連付けられている必要がある．Java 仮想マ シン内では，コンスタントプールはクラスに対して一意のものと認識され，各エ ントリーはインデックス値によって決定できる．即ち，任意のオブジェクトキャッ シュエントリーを，クラスに固有の数値とコンスタントプールエントリへのイン デックス値に関連付けることで，オブジェクトキャッシュ内のデータ探索を一意 に行うことが可能である． オブジェクトキャッシュへのデータの登録は，最初にコンスタントプールエン トリが解決された際に行なう．キャッシュに登録するデータは，解決されたコンス タントプールエントリの種類，Java 仮想マシン内で用いられるデータ構造体に依 存する．この点に関しては，次の節で説明を行う．登録されたオブジェクトキャッ シュエントリーは，ガーベッジコレクトによってデータの再配置が行なわれるま では有効である．ガーベッジコレクトが実行さると，オブジェクトキャッシュが 保持するデータと，実際のオブジェクトに関する情報の間で一貫性が保てなくな る可能性がある．そこで，ガーベッジコレクトの実行後，オブジェクトキャッシュ 内の全てのエントリーを無効化する操作が必要となる． オブジェクトキャッシュに配列に関するデータを格納する場合は，配列オブジェ クトを指し示す参照型に関連付けられる必要がある．クラスに一意なデータとし てはクラスに固有なアドレス値を用いることが典型的な例であり，また参照型は 通常はメモリアドレスである事から，上記のように関連付けるキーを選ぶことで， 参照の解決データと配列データが衝突することはない．配列キャッシュとして使 用されるコンスタントプールエントリに格納されるデータに関しては後述する． データを登録するタイミングはは，配列が生成される際，配列アクセス命令の実 行時にキャッシュミスであった場合，配列オブジェクトの構成が変更された場合 等が考えられる． 以上，説明した動作が可能なオブジェクトキャッシュを実装することでオブジェ クト操作命令，配列アクセス命令の実行処理を最適化できると考える．図 3.1 に， オブジェクトキャッシュの構成例を示す．今まで述べてきたオブジェクトキャッ シュは，通常使用されるキャッシュの構造と，ほぼ同様の構造で実現が可能であ 14 第 3 章 Object Cache る．異なる点は検索キー，格納されるデータ，データを書き込むタイミング等の 変更が容易な部分である．キャッシュ内データの入れ替えアルゴ リズムに関して も，ラウンド ロビン，LRU 等の既知の方法で管理可能であると考えている．図 3.1 の例は，4 ウェイセットアソシエイティブキャッシュと同様の構成になっている． 3.2 命令動作 図 2.1 と図 2.3 に示される命令の，オブジェクトキャッシュを使用する場合の 実行処理の方法に関して説明をする．バイトコード 配列から命令がフェッチされ， それがオブジェクト操作命令，或いは配列アクセス命令であった場合，Java 仮想 マシンはオブジェクトキャッシュ内のデータ探索を行なう．探索用のキーは前述 のようにクラス固有のアドレス+コンスタントプールへのインデックス値，もし くは配列オブジェクトの参照型を用いる．目的データがオブジェクトキャッシュ 内に存在し，更にそのデータが有効である場合にキャッシュヒットとなり，オブ ジェクトキャッシュよりデータが転送される．目的データがオブジェクトキャッ シュ内に存在しない，或いは目的データが無効である場合は，シンボリック参照 を用いた解決，または通常の配列アクセスが行われ，命令実行完了後にオブジェ クトキャッシュへの登録が行われる．以降の命令実行動作は，参照するコンスタ ントプールエントリーの種別によって異なってくる．各命令動作について個別に 説明していく． 3.2.1 静的参照 命令が静的オブジェクトの参照をする場合，図 3.3 の様に動作する．これには， getstatic 命令，putstatic 命令，invokestatic 命令，そして一部の invokespecial 命令が含まれる．オブジェクトが静的なデータである場合，その配置は Java 仮 想マシン中で一意に決定できる．即ち，コンスタントプールエントリーが静的な データを指し示している場合，オブジェクトキャッシュには目的データへのポイ ンタが格納されていればよい事になる。 コンスタントプールエントリーがフィールド 参照の場合は，目的フィールド へ のポインタと，データ型がオブジェクトキャッシュより転送されてくる．データ 型よりデータ長を判別し，ポインタを使ってアクセスを行えばよい．メソッド 呼 び出しの場合は，メソッド 構造体のアドレス，引数の数等が転送されてくる．メ ソッド 呼出し命令は命令完了に複数の段階を要する命令であり，その動作も Java 15 第 3 章 Object Cache 仮想マシンの実装，内部データ構造体に依存する1 ．オブジェクトキャッシュに格 納するデータは，実装を考慮した命令実行上，最も有効な値を保持すべきである． 図 3.3 の例ではメソッド 構造体へのポインタ，スタック上の一番目の引数へのバ イトオフセット値い（ invokespecial の場合はスタック上の objectref へのバイ トオフセット値．スタックポインタとこの値の計算結果が次のローカル変数配列 のベースアドレスになる． ），メソッド の返値の型が保持されている． 3.2.2 動的参照 命令が動的オブジェクトの参照をする場合，図 3.4 のように動作する．これに は，getfield 命令，putfield 命令，invokevirtual 命令，invokeinterface 命 令，そして一部の invokespecial 命令が含まれる．動的オブジェクトを参照し ている場合，参照するデータはどのインスタンスオブジェクトに属しているかに よって位置が異なってくる．つまり，一意に決定するにはスタック上の objectref と関連付けなければならない．そこでインスタンスオブジェクト構造体を，同一 クラスから生成されたインスタンス同士は同一の構造を持つように構成する．こ れにより，スタック上の objectref が異なる場合であっても，インスタンスオブ ジェクト内のバイトオフセット値を保持していれば所望のデータにアクセスが可 能になる．つまり，オブジェクトキャッシュには目的データのインスタンスオブ ジェクト内のバイトオフセット値が格納されていればよい． フィールド 参照の場合は，オブジェクトの先頭からフィールド 先頭へのバイト オフセット値とデータ型がオブジェクトキャッシュから転送されてくる．スタック 上のオブジェクト参照とオフセット値を用いてアドレス計算した後，フィールドへ のアクセスを行う．図 3.4 のメソッド 呼び出しの場合は，スタック上の objectref へのバイトオフセット値とスタックポインタよりスタック上の objectref を取得 し，更に objectref と byte offset でアドレス計算を行ってメソッド のアドレス を取得している． 16 第 3 章 Object Cache 3.2.3 定数参照 命令が定数の参照をする場合，図 3.5 のように動作する．これには，ldc 命令， ldc w 命令，ldc2 w 命令が含まれる．これらの命令は，スタックに定数をプッシュ する．図 3.5 では，定数，或いは定数への参照がオブジェクトキャッシュより転 送されてくる．文字列定数の場合は定数への参照が使われ，その他の場合はオブ ジェクトキャッシュエントリーのサイズに依存する． 3.2.4 クラス参照 命令がクラスの参照をする場合，図 3.6 のように動作する．これには，anewarray 命令，multianewarray 命令，checkcast 命令，instanceof 命令，new 命令が含 まれる．この中で，anewarray，multianewarray，new はヒープ領域確保を行な う命令であり，複雑な処理を必要とする．checkcast と instanceof はスタック 上の objectref の型をチェックする．オブジェクトキャッシュからは，参照すべき データが複数の場合はクラス構造体のアドレスと，参照するデータへのオフセッ ト値が，単一の場合はそのアドレスが転送される． 3.2.5 配列アクセス 命令が配列アクセスを行なう場合，図 3.7 のように動作する．これには全ての 配列アクセス命令が含まれる．オブジェクトキャッシュには配列長とデータ型が 保持されている2 ．配列要素へのアクセスを行なう場合，まず配列長とインデック スの比較と型の比較をし例外のチェックを行なう．例外が発生しない場合，イン デックス値を型のバイト長に合わせて左シフトした値と，配列データの先頭アド レスによってアドレス計算を行なうことで，データの存在する先頭アドレスが得 られる．arraylength の場合は，配列長をスタックに積む． 1 基本的には，解決後のメソッド 呼び出し命令は，モニター獲得の必要性のチェック，新たなス タックフレームの生成，現在のステータスの保存が必要になってくる．モニターの獲得が必要で あれば，モニターを獲得するまで待たなければならない．参照するメソッドが動的な場合でも同 様である． 2 配列オブジェクトが実際の要素のデータを含まない実装の場合，実際のデータ配列の先頭ア ドレスも保持されるべきである． 17 第 3 章 Object Cache constant or arrayref (47:16) constant pool entry number (15:0) tag block offset index compare compare compare compare MUX MUX MUX MUX v Data Hit 図 3.1: オブジェクトキャッシュの構成例 18 第 3 章 Object Cache 図 3.2: オブジェクトキャッシュを使用する場合の基本的な実行の流れ 19 第 3 章 Object Cache opcode index object cache constant cache type data address (a) Field access opcode index object cache constant nargs rettype method address invoke static method with object cache hit interupt (b) Invoke method 図 3.3: 静的オブジェクトの参照をする場合 20 第 3 章 Object Cache opcode index constant object cache byte offset type objectref cache : : stack (a) Field access opcode index constant object cache nargs rettype byte offset SP : objectref : : invoke non-static method with object cache hit interupt stack (b) Invoke method 図 3.4: 動的オブジェクトの参照をする場合 21 第 3 章 Object Cache opcode index constant object cache constant or constantref constant cache : : stack 図 3.5: 定数の参照をする場合 opcode index object cache constant byteoffset, ... classref new or type check method with object cache hit interupt 図 3.6: クラスの参照をする場合 22 第 3 章 Object Cache object cache length type out of bounds exception index shifter arrayref data address : : stack 図 3.7: 配列アクセスを行なう場合 23 第 3 章 Object Cache 3.3 オブジェクト キャッシュの利点 オブジェクト参照解決の保存にオブジェクトキャッシュを使用することで次に 挙げるような利点があると考える． クラスファイルの静的データ化 最初に述べたように，Java を使った組み込み機器開発が注目されているが，こ の分野ではプログラム，クラスライブラリ等を ROM 化することが求められる． quick 擬似命令，コンスタントプールタグを使用する場合，オブジェクト参照の 解決を保存するために，バイトコード 配列，或いはコンスタントプールを書き換 える必要があるため，クラスファイル全体を ROM 化する場合に柔軟なメモリの 割り当てが難しくなる．オブジェクトキャッシュを使用する場合は，クラスファ イルに含まれるデータの書き換えを行なう必要がなく，メモリの割り当ても柔軟 に行なえる． ガーベッジコレクタ時の初期化が容易 オブジェクト参照の解決を記憶するためにデータの上書きを必要とする場合， 上書きをされたデータと，そうでないデータの切り分けを行なう事が難しい．オ ブジェクトキャッシュを使用する場合，参照の解決に関するデータは全て専用の 領域に格納されているので，切り分け作業は必要ない．参照の解決に関するデー タを初期化するには，オブジェクトキャッシュ内の全エントリーを無効化すれば よい． 動的オブジェクト の直接参照が可能 オブジェクトキャッシュを用いる場合，参照の解決に関する情報を書き込むス ペースを制限されることがない．よって，必要であれば大きなデータを保存して おくことも可能である．オブジェクトキャッシュ内に，解決したオブジェクトを メンバーに持つインスタンスオブジェクトを示す参照型を保存しておけば，実行 時にスタック上の参照型と比較することで，どのインスタンスのデータであるか を判別することが可能である．また，探索キーに参照型を使用することでも実現 できる．つまり，動的なオブジェクトの位置を一意に決定することが可能となり， オブジェクトキャッシュからの直接参照が可能になる． 24 第 3 章 Object Cache ハード ウェア指向 データの上書きを必要とする手法は，結果的に複数回のデータアクセスが必要 となるため，命令処理動作も複雑になるため，ハード ウェアでの実現を考えた場 合に性能向上を見込むことが難しい．前述したように，オブジェクトキャッシュ は従来のキャッシュと同様の機構で実現することが可能である．また，オブジェ クトキャッシュの使用に伴う命令処理の実行もハード ウェア的に容易に行うこと が可能である． 25 第 4 章 シミュレーションによる性能 評価 オブジェクトキャッシュを実装した Java 仮想マシンの性能の検討を行なうため， オープンソースの Java 仮想マシンである kaffe virtual machine にオブジェクト キャッシュを実装し性能評価を行なった．本章では性能評価方法，結果について 述べる． 4.1 kaffe へのオブジェクト キャッシュの実装 kaffe は Transvirtual Technologies 社が提供する Java 実行環境である [26]．GPL ライセンスに準じて配布されている．kaffe は Java の実行エンジンとしてインタ プ リター型と JIT 型が選択可能になっている．今回は，Java プロセッサが Java ベース型であることを念頭に置き，命令を逐次実行するインタプリターエンジン にオブジェクトキャッシュの実装を行なった． 実装したオブジェクトキャッシュ関数の処理に関して説明する．図 4.1 にオブ ジェクトキャッシュ構造体を，図 4.2 にオブジェクトキャッシュ内の探索処理を示す． 1 個のデータアレイは 4 個の Set に分割され，index 値より Set が選択される．各 Set に収容できる Block 数は連想度 SET SIZE によって決定される．1 個の Block は，BLOCK SIZE に 8 を乗じたバイト数のデータが格納可能である．オブジェクト キャッシュの総容量は，8 × BLOCK SIZE × SET SIZE × IN DEX SIZE と なる．また，データアレ イのほかにタグアレ イが必要である．データアレ イとし て 4 × SET SIZE × IN DEX SIZE の大きさのメモリ領域を使用している． オブジェクトキャッシュ内の探索は図 4.2 に示すように行なわれる．キャッシュ検 索キーには Hjava lang Class 構造体の head と，コンスタントプールスロットのイ ンデックス番号を使用する．head は Hjava lang Object の変数で，Hjava lang Ob ject は void 型である．コンスタントプールインデックスは 16bit の値である．こ こで，head から得られる値を Key1 とし，コンスタントプールインデックスより 26 第 4 章 シミュレーションによる性能評価 BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE BLOCK_SIZE SET_SIZE 図 4.1: オブジェクトキャッシュ構造体 得られる値を Key2 とする．まず，index 値は，Key1 の 11-10bit から得る．この ビットフィールド を用いる根拠としては，Key1 のとる値を測定し最も変化が大 きかったビットフィールドであった事が挙げられる．Key1 の残りのビットはタグ として使用し，2 次元配列 dir0 の [index] の各要素と比較される．Key2 の上位 ビットは，2 次元配列 dir1 の [index] の各要素と比較するためのタグとなる．ま た，dir1 の MSB は該当ブロックの有効性を示すものであり，MSB が 1 である場 合は既に有効なデータが書き込まれている． ．Key2 の下位ビットはブロック内ア ドレスとなり，Block[block offset] が目的とするデータとなる．cache entry は address と info の 2 つの unsigned int 値からなる構造体で，address にオブ ジェクトの直接参照，または間接参照アドレスが保持され，info にはオブジェク トの型情報等の 命令実行時に必要となる情報が保持される．また，info の MSB は該当エント リーの有効性を示し，1 であるときに有効となる．以上の探索と，エントリーの 有効性がチェックされ，全てが真であった場合にオブジェクトキャッシュにヒット したことになる． キャッシュヒットした場合は，そのデータを使用して以降の処理を進めていく． キャッシュミスをした場合は，kaffe に元々備えられたコンスタントプールから探 索を行なうオブジェクト探索ルーチンによって，オブジェクト参照の解決を行な う．解決されたオブジェクト参照はオブジェクトキャッシュに登録する．オブジェ クトキャッシュへの登録は次のように行われる．まずタグの検索を行い，一致す るタグが存在する場合は該当する Block[index] にオブジェクト情報の登録を行 なう．一致するタグが存在しない場合，登録が行われていない（ 有効ではない） 27 第 4 章 シミュレーションによる性能評価 class.head 31 12 11 10 9 0 idx 15 0 tag1 index byte offset tag0 cmp HIT ! dir 0 cmp dir 1 00 01 10 11 00 TAG val 01 data 10 11 DATA 図 4.2: オブジェクトキャッシュ内の探索処理 タグに登録を行い，該当 Block にオブジェクト情報を登録する．一致するタグが 存在せず，かつ未使用のタグが存在しない場合，キャッシュの入れ替えを行なう． キャッシュの入れ替えはラウンド ロビンアルゴ リズムで行なう．Java 仮想マシン 内でガーベッジコレクション，或いは明示的なオブジェクトの削除が行われた場 合，オブジェクトキャッシュのフラッシュを行なう．ガーベッジコレクションが 行われた場合，全てのキャッシュエントリー内の情報は，実際のオブジェクト情 報と一貫性が無くなる可能性があるので，全ての情報をクリアする．明示的な削 除が行われた場合，該当するタグと Block を無効にする必要がある． 以上の処理を行なう objectcache.c を追加し ，更に命令実行をオブジェクト キャッシュを使用する為に修正した．また，ガーベッジコレクト，オブジェクト 削除時にキャッシュクリアを行なうように修正をした．また，キャッシュヒット 率，キャッシュ使用率を算出するための処理を有効にすることで測定を行なう事 が可能になる． 28 第 4 章 シミュレーションによる性能評価 4.2 4.2.1 ベンチマークプログラム SPECjvm98 SPEC(The Standard Performance Evaluation Corporation)[23] が 開発し た Java 仮想マシンの性能を測定するためのベンチマークプログラムである．SPECjvm98 は次の 8 つのプログラムから成る． • 200 check:Java 仮想マシンと Java の機能をテスト • 201 compress:Lempel-Ziv 法によるデータ圧縮 • 202 jess:NASA の CLIP エキスパートシェルシステム • 205 raytrace:レ イトレーシングソフト • 209 db:IBM が開発した住所録データベース管理 • 213 javac:Sun からライセンスを受けた JDK1.0.2 の Java コンパイラ • 222 mpegaudio:MPEG-3 の復号アルゴ リズムのコア部分 • 227 mtrt:恐竜のレ イトレーシング • 228 jack:Sun からライセンスを受けたパーサジェネレータ この中で， 200 check は実行可能であるがテストからは省いた．また， 205 raytrace と 227 mtrt はコードを変更する前の kaffe でも実行不能であったため省いてある． よって全体値の算出は出来なかった．SPECjvm98 は CPU に PowerPC 604 133MHz を搭載したコンピュータを 1 としたときの相対値で示されるが，本測定では実行 時間で評価を行なっている． 4.2.2 Caffeine Mark 2.5 Pendragon Software が提供する Java 仮想マシンの性能を測定するためのベン チマークプログラムである [24]．アプレットとして動作し，次の 9 項目のテスト を実行する． • sieve:エラストテネスの篩による 2048 以下の素数の算出 • loop:複数の整数ループ 29 第 4 章 シミュレーションによる性能評価 • string:文字列の連結と探索 • method: メソッド コールの速度 • floating-point:50 個の 3 次元の点を 1 度に 5 度，90 度まで回転させる • logic:デシジョンツリーを含むループ • image:drawImage メソッド の速度 • graphics:drawLine，setColor，fillReact メソッド の速度 • dialog:ダ イアログボックス上にコンポーネントプロパティを呼び出す速度 以上のベンチマークを複数回実行し，平均時間を測定する．その後，0.5×(sieve+ loop + method + logic) + string + f loating − point + image + graphics + dialog より全体の CaffeinwMark 値を決定する．基準となるシステムは次の通りであり， CaffeineMark 値は 100 となる． • Tyan Titan 3 Mother Board • Cyrix 6x86 120MHz • 32MB RAM, 512KB Cache • Genoa Phantom 64 graphics adapter • Maxtor 1.6 GB HDD • Windows 95 • Cafe Debugger Appletviewer Ver.1.0 4.2.3 Embedded Caffeine Mark CaffeineMark のグラフィカルなテストを除いたベンチマークである．テスト内 容は同様である．各プログラムは，組み込みシステムのようにメモリ容量が小さ ば動作環境でも，快適に動作するように最適化されている．全体値の算出式，基 準システムは言及されていないが，CaffeineMark と同様と思われる． 30 第 4 章 シミュレーションによる性能評価 4.3 ベンチマーク結果 各ベンチマークプログラムを，オブジェクトキャッシュを実装した kaffe で実行 した結果を示す．測定に使用したコンピュータの仕様は次のようになる． • MSI MS-6524/G Micro ATX Mainboard • Intel Pentium4 1.60GHz • 879.5MB RAM, 512KB Cache • SIS 650 • Seagate ST340810A 40GB • Vine 2.6 Linux Kernel 2.4.18-0v13 測定はオブジェクトキャッシュの総容量を固定し連想度を 1,2,4,8,16,32 と変化さ せたときの値を，総容量が 2KB,4KB,8KB,16KB の場合について行なった．また， 比較のためオリジナルの kaffe をインタプ リターエンジンで実行した場合のベン チマーク値を，連想度 0 として同時に記載してある．また，SPECjvm98 の各ベ ンチプログラムについては，実行時のキャッシュヒット率，キャッシュの使用率 を測定した． 4.3.1 SPECjvm98 ベンチマーク性能 SPECjvm98 の各ベンチマークプログラムの実行結果を図 4.3 から図 4.6 に示す． 縦軸は実行処理時間であり，低いほど 性能が高いといえる．また，キャッシュ構 成による各ベンチマークプログラムの性能の変化を図 4.7 から図 4.12 に示す．縦 軸は同様に実行処理時間であり，塗り潰しの色が濃いほど 高性能である．まずプ ログラム別に見ると，compress,db,mpegaudio の様に同様の処理を複数回繰り返 す，クラスの再利用性が高いと考えられるベンチマークプログラムでは，一部の キャッシュ構成でオリジナルの kaffe と比較して高速に処理が出来ていることが判 る．jess,javac,jack の様に，処理を繰り返すことが少ない，クラスの再利用性が低 いと考えられるベンチマークプログラムでは，逆にオリジナルの kaffe に比べて 性能を落としている． キャッシュ構成による性能の変化を見ると，4WAY もしくは 8WAY 構成で最も 31 第 4 章 シミュレーションによる性能評価 高速に動作し，それ以上の連想度では若干性能を落としている．これは，セット 検索時のタグ比較がソフトウェアでは並列に行われず，順次に比較が実行される ためのオーバーヘッド と，キャッシュミス時の登録処理で順次タグのチェックを することで起きるオーバーヘッドが主な要因であると考えられる．キャッシュ容 量の変化に注目すると，連想度を変化した場合に比べ性能差が小さいことが判る． この原因として，キャッシュ容量を大きくしていくと，キャッシュの無効化時に発 生するオーバーヘッドが増大し，性能の伸びが相殺される可能性が考えられる． キャッシュヒット 率 図 4.13 から図 4.16 に SPECjvm98 の各ベンチマークプログラムのキャッシュヒッ ト率を示す．性能向上が見られたベンチマークプログラムでは 70%以上の高い数 値を示している．また連想度が大きいほど ，キャッシュヒット率も高いといえる． これより，前述した様な連想度の向上に伴うオーバーヘッド の影響が小さければ， 性能の向上が見込めると考えられる． キャッシュ使用率 図 4.21 から図 4.24 にキャッシュの平均使用率を，図 4.17 から図 4.20 に最大使 用率を示す．この測定は，キャッシュの無効化を行なう際にオブジェクトキャシュ の状態を観測した値を採用した．まず，最大使用率の変化を見る．全ての場合に おいて，キャッシュ使用率は連想度に比例して高くなっている．キャッシュ容量 の変化に注目すると，連想度とは逆に容量の増加によって使用率は低くなる．こ れは，キャッシュに格納される情報量が，キャッシュ容量の増加に対して大きく はならないという事と考えられる．また，キャッシュの使用率がピークに近いと 思われる瞬間で値を測定しているにも拘らず，キャッシュの使用率が 100%を大き く下回っている事実は，オブジェクトキャッシュに格納すべきデータの局所性が 低いという事を示しいる． 平均での使用率に注目すると，いずれも低い値を示していることが判る．特 に，compress と mpegaudio は 0 に近い値を示している．しかし ，compress と mpegaudio は，他のベンチマークプログラムと比較してオブジェクトキャッシュ による性能向上が大きく，また最大使用率では他のベンチマークプログラムの値 と変わらない．これらの原因として，Java 仮想マシン実行時にプログラムの処理 32 第 4 章 シミュレーションによる性能評価 自体に関わる時間に対し，コンストラクタの実行等の処理以外にかかる時間の比 率が他のプログラムより高かった等が推測されるが，決定的な原因を特定するの は難しい．また，平均使用率の測定では long long int 型の変数が 1 周したと推 測されるような結果が javac で測定されるなど ，測定法に問題もあったと考えら れる． 4.3.2 CaffineMark 2.5 CaffeineMark 2.5 の各ベンチマークプログラムの実行結果を図 4.25 から図 4.28 に，キャッシュ構成の変化による oveall の変化を図 4.29 に示す．縦軸はベンチ マークスコアであり，高いほど 性能が高いといえる．overall を見ると，全体の 性能は元の kaffe に対し低い，もしくはほぼ変わらない値となっている．個別で見 ると，method，また image，graphics の様な描画系のベンチマークプログラム では性能の向上が見られる一方で，dialog は大きく性能を下げている．string の性能曲線が SPECjvm98 の場合に最も近い．sieve，logic，fp では大きな性能 の変化は見られなかった．また，loop は測定値のばらつきが大きく傾向を読み取 ることが難しい．キャッシュ構成では連想度 1，即ちダ イレクトマップキャッシュ 構成では大きく性能を落としている．連想度 4 でほぼピーク性能を示している． 4.3.3 Embedded CaffeineMark Embedded CaffeineMark の各ベンチマークプログラムの実行結果を図 4.30 か ら図 4.33 に，キャッシュ構成の変化による oveall の変化を図 4.34 に示す．縦軸 はベンチマークスコアであり，高いほど 性能が高いといえる．キャッシュ容量が 2K の場合に，loop のスコアが若干落ちているため overall のスコアも伸びては いないが，それ以外の場合でははっきりとした性能の向上が見られる．プログラ ムはどれも連想度が 1-4 程度で最高の性能を示し，その後は連想度が大きくなる と性能が落ちていく．これは SPECjvm98 の性能曲線とほぼ同様であるといえる． キャッシュ構成で見ても連想度 4 で最高であり，キャッシュ容量による依存は 4K 以降はほぼ無いといってよい． 33 第 4 章 シミュレーションによる性能評価 図 4.3: SPECjvm98 - キャッシュ容量 2KB 図 4.4: SPECjvm98 - キャッシュ容量 4KB 34 第 4 章 シミュレーションによる性能評価 図 4.5: SPECjvm98 - キャッシュ容量 8KB 図 4.6: SPECjvm98 - キャッシュ容量 16KB 35 第 4 章 シミュレーションによる性能評価 図 4.7: SPECjvm98 - compress 図 4.8: SPECjvm98 - db 36 第 4 章 シミュレーションによる性能評価 図 4.9: SPECjvm98 - mpegaudio 図 4.10: SPECjvm98 - jess 37 第 4 章 シミュレーションによる性能評価 図 4.11: SPECjvm98 - javac 図 4.12: SPECjvm98 - jack 38 第 4 章 シミュレーションによる性能評価 図 4.13: SPECjvm98 - キャッシュヒット率 - キャッシュ容量 2KB 図 4.14: SPECjvm98 - キャッシュヒット率 - キャッシュ容量 4KB 39 第 4 章 シミュレーションによる性能評価 図 4.15: SPECjvm98 - キャッシュヒット率 - キャッシュ容量 8KB 図 4.16: SPECjvm98 - キャッシュヒット率 - キャッシュ容量 16KB 40 第 4 章 シミュレーションによる性能評価 図 4.17: SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 2KB 図 4.18: SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 4KB 41 第 4 章 シミュレーションによる性能評価 図 4.19: SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 8KB 図 4.20: SPECjvm98 - 最大キャッシュ使用率 - キャッシュ容量 16KB 42 第 4 章 シミュレーションによる性能評価 図 4.21: SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 2KB 図 4.22: SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 4KB 43 第 4 章 シミュレーションによる性能評価 図 4.23: SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 8KB 図 4.24: SPECjvm98 - 平均キャッシュ使用率 - キャッシュ容量 16KB 44 第 4 章 シミュレーションによる性能評価 図 4.25: CaffeineMark2.5 - キャッシュ容量 2KB 図 4.26: CaffeineMark2.5 - キャッシュ容量 4KB 45 第 4 章 シミュレーションによる性能評価 図 4.27: CaffeineMark2.5 - キャッシュ容量 8KB 図 4.28: CaffeineMark2.5 - キャッシュ容量 16KB 46 第 4 章 シミュレーションによる性能評価 図 4.29: CaffeineMark 2.5 - overall 47 第 4 章 シミュレーションによる性能評価 図 4.30: EmbeddedCaffeineMark - キャッシュ容量 2KB 図 4.31: EmbeddedCaffeineMark - キャッシュ容量 4KB 48 第 4 章 シミュレーションによる性能評価 図 4.32: EmbeddedCaffeineMark - キャッシュ容量 8KB 図 4.33: EmbeddedCaffeineMark - キャッシュ容量 16KB 49 第 4 章 シミュレーションによる性能評価 図 4.34: Enbedded CaffeineMark - overall 50 第 4 章 シミュレーションによる性能評価 4.3.4 全体的な傾向 ベンチマーク結果の全体的な傾向として次がいえる． • SPECjvm98 の結果と Enbedded CaffeineMark の結果から，連想度 4 程度で 最も良い結果が得られるといえる．SPECjvm98 の節で述べたように，連想 度を上げていくとキャッシュヒット率，キャッシュ使用率は伸びていくが， それに伴うオーバーヘッド も大きくなり，結果的には連想度 4 で最もバラ ンスが取れるようになる．連想度増加によるオーバーヘッド を低く抑える ことが出来れば，より高い連想度で最高の結果が得られる様になると考え られる． • キャッシュ容量を 4K から増加しても大きな効果が表れなかった．連想度の 増加と違い，キャッシュヒット率，使用率の変化が小さいことから，キャッ シュ容量増加によるオーバーヘッド を改善することで性能曲線が変わって いくとは考えにくい． • SPECjvm98 に於ける compress，db，mpegaudio，CaffeineMark 2.5 に於け る image，graphic の様にクラスの再利用性が高いと考えられるプログラ ム，Embedded CaffeineMark の様なプログラムサイズが小さなプログラム でよい性能が得られた．オブジェクトキャッシュは，上記のようなアプ リ ケーションに効果的であるといえる．また，CaffeineMark 2.5，Embedded CaffeineMark の method の値が高いことで，メソッド 呼び出しの最適化が高 速化に繋がっていることが判る． • 前述したように，オブジェクトキャッシュの効果的である点として，データ の書き換えを行なうような手法に対してハード ウェアに適しているという 点が挙げられる．本性能評価ではキャッシュ内の探索，無効化等を WAY ご とに順次に行なっているが，ハード ウェアの動作並列性を考慮するとこの 点が大きく改善できると考えられ，本結果より良好な値が期待できる． 51 第5章 Javaプロセッサ 第 3 章に於けるオブジェクトキャッシュ使用時の命令動作を考慮して Java プロ セッサの構成について考える． 5.1 全体構成 図 5.1 に設計する Java プロセッサの全体構成を示す．まず，命令実行の流れを 簡単に示す．Prefetch Buffer はプリフェッチ用のプログラムカウンター PPC が 示すアドレスのデータを Cache ユニットに要求する．要求データがキャッシュ内に 存在すれば，キャッシュ内のデータが Prefetch Buffer に転送される．Prefetch Buffer は，PC が指し示す命令を Decoder に転送し，ここで命令がデコード され る．また，命令に伴う直渡しオペランドを Operand に転送する．命令のソースと なるデータは，Operand，Cache，Object Cache，Stack から選択される．ハー ド ウェアによる直接実行が不可能な場合，またはオブジェクトキャッシュミスし た場合は内部割込みを発生し，適切な処理ルーチンを呼び出す．ソースデータは Dispatcher で各実行ユニットに振り分けられ，実行結果が Cache，Object Cache， Stack に書き込まれる． 以降，各ユニットについて説明する． 命令セット Java 仮想マシン仕様に含まれる命令を全て実行できる必要がある．一部の命令 はハード ウェアによる直接実行が困難であるため，ソフトウェアエミュレーショ ンによって処理を行なうが，デコード の必要性はある．また，既存の Java 仮想マ シン命令に加えて，メモリアクセス，I/O アクセス，特殊レジスタアクセス等を 行なう，独自拡張命令が実行できる必要がある [11][12][13]．Java はユーザー・プ 52 第 5 章 Java プロセッサ ログラマーからはメモリアクセス，I/O アクセスなどのシステム上クリティカル となる点を隠蔽することで安全性を確保している．即ち，Java 仮想マシン命令で は明示的なメモリアクセス，I/O アクセスを行なう命令が存在しない．明示的な メモリアクセス，I/O アクセスが不可能であると，プロセッサが動作することも 不可能であるといってよい．そこで，これらの動作を実行する命令を拡張する必 要がある．また，プロセッサ内部で使用する特殊なレジスタへのアクセスも命令 によって行える必要がある．これらの拡張命令は，一部の命令のソフトウェアエ ミュレーション中，または特殊なクラスの内部で使用される． 実行ユニット 命令は Integer，Floating，Branch/Mem の 3 つの実行ユニットにより実行さ れる．各ユニットには，実行時に Dispatcher より適切なデータが転送されてく る．Integer ユニットは整数算術演算，整数論理演算，整数比較，整数−整数間 の型変換を実行する．整数乗算，整数除算，整数除余算も Integer で実行される とする．Floating ユニットでは，浮動小数点算術演算，浮動小数点比較，浮動 小数点−整数間，浮動小数点−浮動小数点間の型変換を実行する．Branch/Mem ユニットは，メモリアドレス計算，分岐先アドレス計算など の整数非算術演算， データのロード /ストアを実行する．各命令は，複数実行ユニットにアクセス可 能であり，例えば 2 値の比較とアドレス計算は 1 クロックサイクル中に並列実行 することが出来る． 特殊レジスタ Local と Constant はそれぞれ，ローカル変数配列のベースアドレス，実行時コ ンスタントプールのベースアドレスを示すためのレジスタである．また，Stack ユニット内部にはスタックトップを示す SP レジスタが存在する．これらのレジ スタは，Java 仮想マシン内部で参照するテーブルを指し示すために必要である． メソッド 呼出し命令が実行されコンテキストスイッチする際には，値を保存し呼 び出されるメソッド の為の値に変更する必要がある．ローカル変数は，実行速度 が問題になる場合はレジスタ化する必要が出てくる． 53 第 5 章 Java プロセッサ 内部割込み Java 仮想マシン命令にはハード ウェア化が困難である複雑な命令が存在する． これらの命令は，デコード 後に内部割込みを発生させてソフトウェアエミュレー ションで処理を行なう．また，オブジェクトキャッシュ使用命令で，キャッシュミ ス時には内部割込みを発生させて，オブジェクト参照の解決を行なう． スタックユニット Java プロセッサの設計に於いて議論になる点として，スタックの取り扱いが挙 げられる [19]．ここで問題となる点として，必要となるスタックの深さと，多量 のスタックデータへのアクセスが必要となる Java 仮想マシン命令の存在が挙げ られる． Java 仮想マシンはスタックマシンであるため，多くの命令に於いて演算オペ ランドはスタック上からポップされる．このため，スタックに対するリクエスト が頻繁に発生し，スタックアクセスの速度が問題になる．Java プロセッサに於い ては，高速化の為にスタックをレジスタとして実装する手法が考えられるが，ス タックとして用意するレジスタエントリー数が問題になる．レジスタが少ないと スタックのメモリーへの退避が頻繁に発生し，ロード /ストアに伴うオーバーヘッ ドが増大する．レジスタを増加すると，ゲート数，消費電力の点で問題が起こり， 設計上のトレード オフになる可能性がある．また，Java 仮想マシン命令中には， 一命令中で多量のオペランド スタックへのリクエストを発生させる命令が存在す る．即ちスタックレジスタは，一度に多量のデータリクエストに応える必要があ る． これらを考慮したスタックレジスタを図 5.2 に示す．データリクエストは，コン トローラ部が一括して受け付ける．レジスタファイルはマルチバンク構成になっ ており，バンク単位でリクエストを受け付けることが可能である．スタック上の データへの複数リクエストはアドレス順に発生し，また典型的な例は 4 ポップ -2 プッシュ，2 ポップ -1 プッシュの様な 2 値演算である．上記の様な構成を取るこ とで，ほとんど の命令で 1 クロックサイクル中のリード /ライトを行なうことが 可能である．また，プロセッサをパイプライン構成で設計する場合，データリク エストをリクエストキューに投入し，ライトとリードを相殺させることによって， スタックハザード を予測することが可能でありスタックからのメモリアクセスを 最適化できる可能性がある． 54 第 5 章 Java プロセッサ Data Control Address Prefetch Buffer Constant Local Operand PPC Decoder PC Object Cache Source Selecter Interupt Stack Dispatcher Floating FPU Integer Branch / Mem ALU ADD Cache Dispatcher Bus Unit 図 5.1: Java プロセッサの内部構成 55 第 5 章 Java プロセッサ Source / Destination Data Request Controler R0 R1 R2 R3 r3 r3 r3 r3 r2 r2 r2 r2 r1 r1 r1 r1 r0 r0 r0 r0 Load / Store 図 5.2: スタックユニット 56 SP Base Address 第 5 章 Java プロセッサ 5.2 ソフト ウェアに対する要求 Java 仮想マシンには，動的なクラスロード，クラスベリファイヤ等のハードウェ ア実装が困難である機能が多数含まれている．このため，Java プロセッサを用い て Java 仮想マシンとして動作する場合でも，一部機能をソフトウェアとして実 装する必要がある． ハード ウェアによる直接実行が困難な命令 我々が問題としたオブジェクト操作命令を含めて，Java 仮想マシン命令中には ハード ウェアによる直接実行が困難な命令が多数存在する．これらの命令は，設 計する Java プロセッサで直接実行可能な命令を使用して動作できるようなルー チンを作成し，命令実行時は Java プロセッサ内部で割り込みを発生させ，ソフト ウェアールーチンによってエミュレートする必要がある．これらの命令には，参 照の解決，オブジェクトの新規生成等の複雑な動作をする命令が多数含まれる． ガーベッジコレクト，内部テーブルの作成等の Java 仮想マシンでは隠蔽されて いる動作 Java 仮想マシン内部では，オブジェクト検索を行なうための複数のテーブルの 構築，自動的に行なわれるガーベッジコレクト，スレッドの切り替え等のユーザー・ プログラマには隠蔽された動作を行なっている．これらは，通常のコンピュータ における OS が実行する処理と同様であるといってよい．これらの処理が行なわ れないと Java プログラムの実行は不可能である． 内部で使用するデータ構造体の決定 Java 仮想マシン内部で使用するデータ構造体を効果的に決定することが必要で ある．前述しているように，本手法はインスタンスオブジェクトの先頭アドレス から，オフセット値を使用して目的データにアクセスが可能であることが前提に なっている．データ構造体の形式が決定しなければ，実行動作が決定しない命令 も存在するため，ハード ウェアの検討と並列にこれらの検討を行なっていく必要 がある．また，インスタンスオブジェクトを小型化することは，メモリ使用率， 実行速度面で非常に効果的である [18]． 57 第 5 章 Java プロセッサ 特殊なクラスの実装 ユーザ・プログラマーが明示的なメモリアクセスを行なう際に，アセンブラプ ログラミングのみで実現するのは非常に難しい．そこで，Java 言語でシステム記 述が可能なように，メモリアクセス，I/O アクセス等の特殊なクラスを作成する ことが望ましい．ユーザ・プログラマーはこれらのクラスを使用することで，明 示的なメモリ，I/O アクセスを行うことが可能になる． 5.3 ガーベッジコレクタ Java の実行環境に於ける最も大きなオーバーヘッドとして，ガーベッジコレク タによるメモリの最適化処理が挙げられる．特に，組み込みシステムのように実 時間実行が必要となる分野では，実行上の大きな問題となる可能性が高い．そこ で，ガーベッジコレクタの実行する処理に関しても何らかの最適化を行なう必要 がある．一つの方法としてはガーベッジコレクタをハード ウェア化する方法も考 えられる． また，オブジェクトキャッシュとガーベッジコレクタのメモリ割り当てアルゴ リスムは深い関わりがある．オブジェクトキャッシュは，検索キーの一部にメモ リアドレスを使用している．これらのアドレスはガーベッジコレクタによって割 り付けられたものであり，効果的なハッシュ関数を見出すにはガーベッジコレク タのメモリ割り当てを考慮しなければならない． 本研究ではガーベッジコレクタに関しては，まだ深い検討がされておらず，こ の点に関して追求する必要があると考えている． 58 第6章 関連文献 本研究に関連が深い研究について言及する．また，この他にも Java プロセッ サとして [27][28][29][30] 等が挙げられる．[27][28][29][30] らに関しては，高速化技 術，最適化技術に対する資料が乏しく，手法的な比較が難しい．また，我々が着 目しているオブジェクト参照の解決をど う処理するかについても不明である．一 般的に見て，オブジェクト参照の解決に関する問題は決定的な技術が無いといっ てよい． 6.1 Virtual Address Object Cache Vijaykrishnan らによる研究である [14][15]．Java プロセッサに於いて，オブジェ クト参照をハード ウェア的に解決する手段を提案している．文献 [16][17] で述べ られる Object Cache を Java システム上で実現した物である．Java プロッセサー のオブジェクトキャッシュアクセスに関する論文は我々の物も含めて非常に少な く，ユニークな研究であるといえる．ここで言及される Virtual Address Object Cache はオブジェクト参照とフィールド オフセットの組を検索キーとして内部を 探索される．これは，オブジェクト参照とフィールド オフセットにより一意にオ ブジェクト位置が決定できるという理由からである．ただし，Java のメソッド 呼 出し命令では，オブジェクト参照はスタック上に積まれた引数の最も底に存在し， 何らかの方法で引数の数を通知しなくてはならない．また，我々のオブジェクト キャッシュの大きな違いとして，我々のオブジェクトキャッシュが参照の解決が 行なわれたことを保存するのに対し，[15] では，通常命令を quick 擬似命令に書 き換えることで，この問題を解決しているようであるが，本論分で指摘してきた ような問題が残る．[15] では，Object Cache を実装した Java 仮想マシンの性能 を，3 つの方法についてオブジェクトアクセスに掛かるクロックサイクルを用い て論じている．プログラムに因って違いがあるものの，1 から 5 クロックの間で オブジェクトにアクセスできることが示されている．また，オブジェクトキャッ 59 第 6 章 関連文献 シュのヒット率に関しても言及されているが，これらの数値は我々が測定した値 に対して高い数値になっている．実行したプログラム，オブジェクトキャッシュ を使用した命令の数にもよると考えられるが，ヒット率の向上に関しては我々も 検討を行なうべきである． 6.2 動的再構成部分を持つ Java プロセッサ 木村らによる研究である [20][21]．文献 [20] で設計されている Java プロセッサ は，メインの命令パイプラインの外に再構成可能部を持ち，必要に応じて外部回 路を構成することで演算の高速実行を図ろうというものである．プロセッサは命 令パイプラインの実行ステージと並列に FPGA ユニットを持っており，通常の命 令パイプラインで実行を行うことが困難な動作を FPGA ユニットで実現し ，デ コード ステージから転送されるデータを FPGA 部にバイパスすることで処理の 効率化を図っている．ただし，FPGA 部へのプログラミング方法，FPGA 部に構 成されるべき回路については情報が乏しい．FPGA により柔軟に回路が書き換え られることで我々と同様の機能を実現することは可能ではあると考えられるが， その点に関する言及はされていない．また，文献 [21] で言及されている Java プ ロセッサは，動的に命令解析を実行し複数命令を一つの命令で実行する，いわゆ る命令畳み込み機能を有する．ここでは，動的再構成可能といえるような部分は 持っていない様である． 60 第7章 結論 Java 仮想マシンにおけるオブジェクトキャッシュ機構の提案と性能評価，また オブジェクトキャッシュを使用した Java プロセッサのアーキテクチャについて述 べてきた． オブジェクトキャッシュは，Java 仮想マシン内のオブジェクトアクセス，配列 アクセスを最適化するための手法であり，オブジェクトキャッシュを使用した命 令処理，期待できる効果について説明した．また，ソフトウェア Java 仮想マシ ンにオブジェクトキャッシュを実装しベンチマークプログラムを動作させること で，この手法の評価を行なった．結果として，一部の構成では性能の向上が見ら れ，プログラム実行の高速化に効果があることがわかった． 本論分で問題としてきた命令動作に関しては，決定的な技術はまだ存在せず， 既存の Java プロセッサによる Java 実行環境に於いても効果的な実装が行われて いるとは言い難い．本論分で述べてきた，オブジェクトキャッシュを使用する手 法は，オブジェクト参照の解決処理を最適化する手法としては非常に効果的なも のである．ここでは，オリジナルの Java プロセッサをターゲットにしてきたが， 既存の Java プロセッサにオブジェクトキャッシュ機構を組み込むこ手法，また得 られる効果を検討する必要もあるかと思われる．また，キャッシュ内探索キーと して，アドレス以外のデータを一意に決定できるデータを使用する手法は，様々 な応用が可能であると考えられ，オブジェクトキャッシュの応用事例の検討も有 用であると考える． 今後は，ソフトウェア部分とハード ウェア部分を並列に検討し，Java プログラ ムの実行に対して効果的な実装を行なう必要がある． 61 謝辞 まず，本研究を進める上で若輩者である私を多大なる忍耐により御指導下さった 東海大学電子情報学部コミュニケーション工学科助教授 清水尚彦先生に感謝致し ます。 また，我々の研究室に欠かせない PARTHENON システムをメンテナンスして頂 いた NTT 未来ねっと研の皆様のご苦労が無ければ本研究を進める事は不可能で した．授業，TA 等でお世話になりました吉田正廣先生を始めとする東海大学工 学部通信工学科の先生方に感謝いたします．最後になりましたが，日常的に技術 的，精神的支援を頂いた三竹氏，宮坂氏，孕石氏，李氏，早坂氏，神山氏をはじ めとする清水研究室の諸学生，及び他研究室の友人に感謝致します． 62 業績 1. 津田, 渡辺, 宮坂, 近, 孕石:”ASIC デザインコンテスト 16-bit Free CPU” 第 16 回 PARTHENON 研究会予稿集 (2000) 2. 近, 孕石, 清水:”CPLD ベンダーライブラリサポートツール ” 第 17 回 PARTHENON 研究会予稿集 (2000) 3. 石川，近，秋元:”ASIC デザインコンテスト 16-bit Free CPU” 第 18 回 PARTHENON 研究会予稿集 (2001) 4. 近:”ASIC デザインコンテスト SFL による 8080 互換プロセッサとコンピュー タシステムの設計及び CP/M マシンとしての実現” 第 18 回 PARTHENON 研究 会予稿集 (2001) 5. 神山，名野，高田，石黒，近:”ASIC デザインコンテスト USB インターフェー ス IF” 第 20 回 PARTHENON 研究会予稿集 (2002) 6. 名野，神山，近:”ハード ウェア主体の USB デバイスコントローラ設計と USB デバイスへの実装” 第 21 回 PARTHENON 研究会予稿集 (2002) 7. 近，清水:”ハード ウェア統合開発環境の検討” 電子情報通信学会総合大会 A-315 (2001) 8. 近，清水:”Linux による 8bitCP/M マシンの開発” Linux カンファレンス (2001) 9. 近，清水:”オブジェクトキャッシュを用いた JVM 命令互換プロセッサの設計” 情報処理学会研究報告 Vol.2001, No.116(ARC-145-7) PP.45-50 (2001) 10. 近，清水:”オブジェクトキャッシュを用いた JVM 命令互換プロセッサの設計” 電子情報通信学会技術研究報告 Vol.101, No.671(CPSY2001-108) PP.25-31 (2002) 11. 近，清水:”オブジェクトキャッシュを用いた JVM 命令互換プロセッサの設計” 情報処理学会研究報告 Vol.2002, Np.112(ARC-150-13) PP.65-70 (2002) 12. C. Kon and N. Shimizu:”The Design of a i8080A Instruction Compatible Processor with Extended Memory Address” ASP-DAC 6D-7 (2003) 13. T. Kouyama, H. Nano, C. Kon and N. Shimizu:”The Design of a USB Device Controller IYOYOYO” ASP-DAC 6D-8 (2003) 14. 名野，神山，近，清水:”プロトコル処理の多くをハード ウェア化した USB デ バイスコントローラの開発” FPGA/PLD Design Conference (2003) 63 15. 名野，神山，近，清水:”プロトコル処理の多くをハード ウェア化した USB イ ンターフェースと USB デバイスの開発” SWEST4 (2002) 16. 名野，神山，近，清水:”プロトコル処理の多くをハード ウェア化した USB イ ンターフェースの設計” 電子情報通信学会総合大会 C-12-12 (2003) 64 参考文献 [1] Sun Microsystems http://java.sun.com [2] Lindholm, T. and Yellin F. 著, 野崎裕子 訳:”Java 仮想マシン仕様” アジソン・ウェ スレ ィ・パブリッシャーズ・ジャパン (1997) [3] Lindholm T. and Yellin F. 著, 村上雅章 訳:”Java 仮想マシン仕様第 2 版” ピアソ ン・エデュケーション (2001) [4] Meyer J. and Downing T. 著, 鷲見 豊 訳:”Java バーチャルマシン ” オライリージャ パン (1997) [5] Arnold K.,Gosling J. and Holms D. 著, 柴田芳樹 訳:”プログラミング言語 Java 第 3 版” ピアソン・エデュケーション (2001) [6] Gosling J., Joy B., Steele G. and Bracha G. 著, 村上雅章 訳:”Java 言語仕様” ピア ソン・エデュケーション (2000) [7] Venners B.:”Inside the Java2 Virtual Machine” McGraw-Hill (1999) [8] 村山 敏清:”Java 仮想マシン入門” Java Press No.14 - No.23 [9] Levy M.:”Java 仮想マシンの高速化手法” 日経エレクトロニクス No. 797 - No. 801 [10] ”特集：ごみ集めの基礎と最近の動向” 情報処理，Vol. 35, No.11, (1994) [11] 内藤，清水: ”パルテノンによるパイプライン JAVA チップの設計” 第 12 回パルテ ノン研究会予稿集 [12] 内藤:”パイプライン Java チップの設計” 1997 年度 東海大学工学部通信工学科卒業 論文 [13] 青柳:”Java Virtual Machine 命令互換プロセッサの高速化に関する研究” 1996 年度 東海大学工学部通信工学科卒業論文 [14] Vijaykrishnan N., Ranganatham N. and Gadekarla, R.:”Object-Oriented Architectual Support for a Java Processor” ECOOP’98 Object-Oriented Programming LNCS1445 (1998) 65 [15] Vijaykrishnan N. and Ranganatham N.:”Supporting Object accesses in a Java Processor” IEE Proc.-Comput. Digit. Tech. Vol.147, No.6, Nov. (2000) [16] Wolczko M. and WILLIAMS I.:”The influence of the object-oriented language model on a supporting architecture” Proc. 26th Hawaii Conference on System Science, PP.182-191 (1993) [17] Williams I.:”Object-based memory architecture” PhD Thesis, Dept. Conputer Science, Univ. Manchester (1989) [18] Bacon F., Fink S. and Grove D.:”Space- and Time-Efficient Inplementation of the Java Object Model” ECOOP 2002, LNCS 2374, PP.111-132 (2002) [19] 渡辺，金田，大津山:”Java Virtual Machine の静的・動的解析” 情報処理学会研究 報告 Vol.97, No.76(ARC-125) PP.73-78 (1997) [20] 木田，木村，高木，あべ松，渡邉:”再構成可能部を持つ java プロセッサ” 電子情報 通信学会総合大会 PP.442-443 (1999) [21] 鈴木，木村，渡邉:”動的命令変更機能を持つ組込み向け Java プロセッサの設計と 評価” 電子情報通信学会技術研究報告 Vol.101, No.671(CPSY-2001-109) PP.33-40 (2002) [22] Dhrystone Benchmark http://www.c-creators.co.jp/okayan/ [23] Spec http://www.spec.org/ [24] Caffeine Mark 2.5 http://www.webfayre.com/pendragon/cm2/ [25] Embedded Caffeine Mark http://www.webfayre.com/pendragon/cm3/ [26] Kaffe Virtual Machine http://www.kaffe.org [27] JeRTy http://www.jerty.com/ [28] picoJava Microprocessor Core http://www.sun.com/microelectronics/picoJava/ [29] Jazelle Technology http://www.arm.com/armtech/Jazelle Tech [30] XPRESSO Core http://www.zucotto.com/home/index.html 66 [31] 富田:”コンピュータアーキテクチャ 第 2 版” 丸善株式会社 [32] 坂本:”UNIX カーネルの設計”共立出版 [33] Furber S. 著, アーム（ 株）監訳:”ARM プロセッサ 32 ビット RISC マシンのシス テム・アーキテクチャ” CQ 出版社 67