(57)【要約】      （修正有）【課題】NUMAコンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置する技術を提供する。【解決手段】NUMAコンピュータ・システム上に構築される仮想マシン環境において、ロック実行時に要求元スレッドが動作するプロセッサに関する情報をロック対象のオブジェクトに残しておき、オブジェクト参照グラフをトラバースしながらオブジェクトの最適配置を行う際に、ロック対象のオブジェクトについては、該オブジェクトを最後にロックしたスレッドが動作するノードに割り当てられたサブ領域を最適配置位置とし、その他のオブジェクトについては、親オブジェクトの最適配置位置を承継させる。【選択図】図２
2011081610.tif 000002
【特許請求の範囲】
【請求項１】
１以上のプロセッサとローカル・メモリとを含むノードを複数有する非均一メモリ・アクセス（NUMA)コンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置する最適配置装置であって、
複数のサブ領域を含むヒープであって、各サブ領域は該サブ領域をローカル・メモリの少なくとも一部とする前記ノードに割り当てられる、前記ヒープと、
各々対応するスレッドに割り当てられた複数のスタックと、
複数のスレッドの各々について、該スレッドを実行するプロセッサの情報を取得するスレッド管理部と、
前記ヒープ内のオブジェクトのロックを要求するスレッドから、ロック対象の前記オブジェクトの識別子を取得し、前記オブジェクトの識別子が識別する前記オブジェクトのヘッダ内に前記スレッドの識別子を書き込むロック管理部と、
前記ヒープ内の各オブジェクトをグラフノード、該オブジェクトから前記ヒープ内の他のオブジェクトへの参照をエッジ、および各スレッドに割り当てられた前記スタックをルート・ノードとする複数のオブジェクト参照のグラフを、前記ルート・ノードを出発点としてそれぞれ走査し、現在の走査対象が参照する移動対象のオブジェクトの前記ヘッダ内に前記スレッドの識別子がある場合、該スレッドの識別子が識別するスレッドを実行するプロセッサを含むノードを前記プロセッサの情報から求め、該ノードに割り当てられた前記ヒープ内の前記サブ領域に前記移動対象のオブジェクトを移動させ、および現在の走査対象が参照する移動対象のオブジェクトの前記ヘッダ内に前記スレッドの識別子がない場合、現在の走査対象であるオブジェクトの移動先のローカル・メモリを含むノードに割り当てられたいずれかのサブ領域に前記移動対象のオブジェクトを移動させるメモリ管理部と、
を含む最適配置装置。
【請求項２】
前記ロック管理部は更に、スレッドからロックの要求を受けるごとに、該スレッドに対し前記スレッド管理部が取得した前記プロセッサの情報である該プロセッサを含むノードの識別子を、前記ロック対象の前記オブジェクト内のまたは該オブジェクト内のポインタが指す所定の位置に上書きし、前記メモリ管理部は、前記移動対象のオブジェクトの前記ヘッダ内の前記スレッドの識別子の代わりに、前記移動対象のオブジェクト内のまたは該オブジェクト内のポインタが指す前記所定の位置にある前記ノードの識別子を使用して、前記移動対象のオブジェクトの移動先を決定する、請求項１に記載の最適配置装置。
【請求項３】
前記ロック管理部は更に、スレッドからロックの要求を受けるごとに、該スレッドの識別子を、前記ロック対象の前記オブジェクト内のまたは該オブジェクト内のポインタが指す所定の位置に上書きし、前記メモリ管理部は、前記移動対象のオブジェクトの前記ヘッダ内の前記スレッドの識別子の代わりに、前記移動対象のオブジェクト内のまたは該オブジェクト内のポインタが指す前記所定の位置にある前記スレッドの識別子を使用して、前記移動対象のオブジェクトの移動先を決定する、請求項１に記載の最適配置装置。
【請求項４】
前記メモリ管理部は、前記オブジェクト参照のグラフの走査の結果、到達しなかった１以上のオブジェクトのヒープ内の領域を再利用するガーベッジ・コレクタであり、かつ、前記オブジェクト参照のグラフの走査は、前記ヒープに利用可能な空き領域がなくなったことに応答して実行されるGCと平行してまたはその前後に行われる、請求項１に記載の最適配置装置。
【請求項５】
前記オブジェクト内の前記所定の位置は、前記オブジェクト内のロックワード内の位置である、請求項２または３に記載の最適配置装置。
【請求項６】
前記スレッド管理部は、複数のスレッドの各々について、該スレッドを実行するプロセッサの情報として該プロセッサを含むノードの識別子を取得し、該ノードの識別子を前記スレッドのスレッド構造体に書き込み、前記メモリ管理部は、前記現在の走査対象が参照する前記移動対象のオブジェクトの前記ヘッダ内に前記スレッドの識別子がある場合、該スレッドの識別子が識別するスレッドの前記スレッドの構造体に書き込まれた前記ノードの識別子を取得し、該ノードの識別子が識別するノードに割り当てられたサブ領域に前記移動対象のオブジェクトを移動する、請求項１に記載の最適配置装置。
【請求項７】
１以上のプロセッサとローカル・メモリとを含むノードを複数有する非均一メモリ・アクセス（NUMA)コンピュータ・システム上に構築される仮想マシン環境におけるオブジェクトの最適配置方法であって、前記仮想マシン環境は、複数のサブ領域を含むヒープであって、各サブ領域は該サブ領域をローカル・メモリの少なくとも一部とする前記ノードに割り当てられる前記ヒープと、各々対応するスレッドに割り当てられた複数のスタックとを含み、前記最適配置方法は、
スレッド管理モジュールを呼び出すスレッドを実行するプロセッサが、複数のスレッドの各々について、該スレッドを実行するプロセッサを含むノードの識別子を取得して前記スレッドのスレッド構造体に格納するステップと、
ロック管理モジュールを呼び出すスレッドを実行するプロセッサが、前記ヒープ内のオブジェクトのロックを要求するスレッドから、ロックの対象であるオブジェクトの識別子を取得し、前記オブジェクトの識別子が識別するオブジェクト内に、前記ロックを要求する前記スレッドのスレッド構造体から読み出した前記ノードの識別子を書き込むステップと、
メモリ管理モジュールを呼び出すスレッドを実行するプロセッサが、前記ヒープ内の各オブジェクトをグラフノード、該オブジェクトから前記ヒープ内の他のオブジェクトへの参照をエッジ、および各スレッドに割り当てられたスタックをルート・ノードとする複数のオブジェクト参照のグラフを、前記ルート・ノードを出発点としてそれぞれ走査し、現在の走査対象が参照する移動対象のオブジェクト内に前記ノードの識別子がある場合、該ノードの識別子が識別するノードに割り当てられた前記ヒープ内のサブ領域に前記移動対象のオブジェクトを移動させ、現在の走査対象が参照する移動対象のオブジェクト内に前記ノードの識別子がない場合、現在の走査対象であるオブジェクトの移動先のローカル・メモリを含むノードに割り当てられたいずれかのサブ領域に前記移動対象のオブジェクトを移動させるステップと、
を含む最適配置方法。
【請求項８】
１以上のプロセッサとローカル・メモリとを含むノードを複数有する非均一メモリ・アクセス（NUMA)コンピュータ・システム上に構築される仮想マシン環境におけるオブジェクトの最適配置プログラムであって、前記仮想マシン環境は、複数のサブ領域を含むヒープであって、各サブ領域は該サブ領域をローカル・メモリの少なくとも一部とする前記ノードに割り当てられる前記ヒープと、各々対応するスレッドに割り当てられた複数のスタックとを含み、前記最適配置プログラムは、
スレッド管理モジュールを呼び出すスレッドを実行するプロセッサに、複数のスレッドの各々について、該スレッドを実行するプロセッサを含むノードの識別子を取得して前記スレッドのスレッド構造体に格納させ、
ロック管理モジュールを呼び出すスレッドを実行するプロセッサに、前記ヒープ内のオブジェクトのロックを要求するスレッドから、前記ロックの対象である前記オブジェクトの識別子を取得し、該オブジェクトの識別子が識別する前記オブジェクト内に、前記ロックを要求する前記スレッドのスレッド構造体から読み出した前記ノードの識別子を書き込ませ、
メモリ管理モジュールを呼び出すスレッドを実行するプロセッサに、前記ヒープ内の各オブジェクトをグラフノード、該オブジェクトから前記ヒープ内の他のオブジェクトへの参照をエッジ、および各スレッドに割り当てられたスタックをルート・ノードとする複数のオブジェクト参照のグラフを、前記ルート・ノードを出発点としてそれぞれ走査し、現在の走査対象が参照する移動対象のオブジェクト内に前記ノードの識別子がある場合、該ノードの識別子が識別するノードに割り当てられた前記ヒープ内の前記サブ領域に前記移動対象のオブジェクトを移動させ、現在の走査対象が参照する移動対象のオブジェクト内に前記スレッドの識別子がない場合、現在の走査対象であるオブジェクトの移動先のローカル・メモリを含むノードに割り当てられたいずれかのサブ領域に前記移動対象のオブジェクトを移動させる、最適配置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、非均一メモリ・アクセス（NUMA)コンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置する技術に関する。
【背景技術】
【０００２】
近年プロセッサは非均一メモリ・アクセス（Non-Uniform Memory Access, 以下単にNUMAという)の構成を取っており、今後もこの傾向は続いていく。代表的なプロセッサに、IBM社のPOWER6（登録商標）、AMD社のOpteron（登録商標）、Sun Microsystems社のT2plus、Intel社のNehalemがある。こうしたプロセッサでは、マルチコアで急増するプロセッサ速度とメモリ速度のギャップを減らすために、プロセッサにメモリが直接接続される。このようなプロセッサ（複数可）とメモリの対（以下、ノードという）を複数有し、ノード間をインターコネクトで接続するNUMAコンピュータ・システムでは、メモリへのアクセスはノード間で非対称となる。即ち、あるノードのプロセッサが別のノード内のメモリ（以下、リモート・メモリという）にアクセスするレイテンシは、それ自体のノード内のメモリ（以下、ローカル・メモリという）にアクセスするレイテンシよりも大きい（典型的な例では２倍）。そのためNUMAコンピュータ・システムではデータをどのメモリに配置するかがその性能を左右する。
【０００３】
NUMAコンピュータ・システムにおいてJava(登録商標）で書かれたアプリケーションを実行させる場合、上記問題は、Java仮想マシン（以下、VMという）がオブジェクトを、その割当時とガーベッジ・コレクション（以下、GCという）時とでそれぞれどこに配置するかという２種類の最適化問題になる。割当時にどこに配置するかという問題に対しては、従来、スレッド固有の割当バッファをローカル・メモリから割り当てる手法が知られている（例えば、非特許文献１参照）。該手法は、例えばSunMicrosystems社が提供するHotSpot（商標） VMにおいて採用されている。
【０００４】
しかし上記手法を採用するだけでは以下で述べるようなアプリケーションに対して十分ではない。マルチスレッド化されたアプリケーションでは、オブジェクトを作成するスレッドとオブジェクトをアクセスするスレッドが異なる場合がある。例えば制御スレッド１つに対しワーカースレッドが多数存在する場合のように、異なるスレッドによるオブジェクトへのアクセスが多い場合、割当時のローカル・メモリへのオブジェクトの配置は適切ではない。
【０００５】
この問題に対し非特許文献１は、メモリアクセスのプロファイルを基にしたGCによるオブジェクト配置を提案する。具体的には、アクセスされたメモリのアドレスとアクセスしたプロセッサのチップのペアをハードウェアによりサンプル収集し、トレースを保存する。またGCで生き残ったオブジェクトの割当の全プロファイルを収集し、トレースを保存する。そしてこれらトレースをマージすることにより、オブジェクトごとに最もアクセスしたプロセッサチップを推奨位置（preferred location)として計算し保存する。最後にGC時において、生きているオブジェクトを推奨位置に移動する。
【０００６】
なお、アプリケーションの実行性能を高めるために改善されたGCを開示する従来技術として、例えば特許文献１がある。特許文献１は、プログラムのデータフロー解析を行い、オブジェクトが参照される区間を調べ、オブジェクトの参照区間の最後にオブジェクト開放命令を挿入する技術を開示する。
【０００７】
また他の従来技術として特許文献２がある。特許文献２は、GCなどによる移動が少ないデータをあらかじめ判別して所定の記憶領域に記憶させることで、データの移動を少なくしてGCなどによる負荷を減らす技術、また、寿命の長いデータと寿命の短いデータを、データの種別によってあらかじめ区別し、異なる場所に記憶領域を確保することにより、GCを行なう際の計算量を減らして移動させるデータの量を減らす技術を開示する。
【０００８】
更に他の従来技術として特許文献３がある。特許文献３は、フリー領域または使用領域の量に応じてＧＣの手順を切り替える技術、また、メモリのヒープ領域内のどのオブジェクトからも参照されないオブジェクトを検出し、当該オブジェクトのメモリ領域を他のオブジェクトのメモリ割り当て可能なフリー領域として解放する手順の異なる複数通りのガベージコレクションスレッドの中から、１つの手順のガベージコレクションスレッドを、フリー領域またはオブジェクトの使用領域の量に基づいて選択する技術を開示する。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０００―１３２４０６号公報
【特許文献２】特開２００７―４５０６号公報
【特許文献３】特開２００６―１７２４９５号公報
【非特許文献】
【００１０】
【非特許文献１】M. M. Tikir, J. K. Hollingsworth, “NUMA-AwareJava Heaps for Server Applications”, Parallel and Distributed ProcessingSymposium, 2005, Proceedings, 19the IEEE International Publication, pp.108b.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、非特許文献１が開示する上記アプローチには、GCコストを大きく増加させるという問題がある（Tikirらが開示する例では３倍）。このGCコスト増加の原因は、当該アプローチに本質的なものであると推測される。即ち、上記アプローチは、例えばハッシュマップのようにGC時に引くことができるような形で、移動前のオブジェクトのメモリ位置とオブジェクトを移動させるべき推奨位置との対の情報を保持することを要求する。このことは、オブジェクトの移動ごとにペアの情報を引くコストが追加されることを意味し、この追加コストがGCコスト全体に影響する。
【００１２】
非特許文献１が開示する上記アプローチにはまた、GC時に生きていないオブジェクトへのアクセスサンプルが無駄となり、効率のよいサンプリングを行うことができないという問題、更に、何千万個のオブジェクトが移動対象であるところ、オーバヘッドなくサンプル取得できるのはごく一部のオブジェクトについてのみであり、十分な数のオブジェクトを最適配置できないという問題も有する。
【００１３】
なお、上記特許文献１〜３により開示されるいずれのGC技術も、NUMAコンピュータ・システム上に構築される仮想マシン環境を前提としておらず、またそのような環境について考慮していない。そのため、これらGC技術によってNUMAコンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置することはできない。
【００１４】
この発明は、上記の問題点を解決するためになされたものであって、NUMAコンピュータ・システム上に構築される仮想マシン環境において、GCコストを増加させることなくまた効率的にオブジェクトを最適配置する技術を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本願発明者は、NUMAコンピュータ・システム上に構築される仮想マシン環境において効率的にオブジェクトを最適配置するための方法を研究し、最適配置するべき重要なオブジェクトは、スレッドから専ら排他的にアクセスされるオブジェクトであることを見出した。そのようなオブジェクトに対して最適配置を行うためには、理想的にはスレッドがクリティカルセッションで排他的にアクセスするオブジェクト全てに対して、最適配置位置の情報として上記スレッドが動作するプロセッサまたは該プロセッサを含むノードの識別子を残さなければならない。しかしメモリアクセスの度にそのような識別子を記録することは、ソフトウェア実装でも専用ハードウェア実装でも実行時間へのオーバヘッドが大きく、性能的な観点から現実的ではない。  
【００１６】
そこで本願発明者は更に研究を進め、その結果、排他的制御が必要なオブジェクトにアクセスする際には、そのオブジェクトのロックが取得されること、またそのロックによるクリティカルセッション内でアクセスされる他のオブジェクトは、ロックされたオブジェクトからポインタ経由で辿れることが多いことに着目して、オブジェクトのロックの際に該ロックを要求したスレッドが動作するプロセッサに関する情報をロック対象のオブジェクト内に記録し、該オブジェクトが参照する他のオブジェクトには記録したプロセッサに関する情報を承継させるというアイデアに想到した。
【００１７】
即ち、上記課題を解決するために本発明は、１以上のプロセッサとローカル・メモリとを含むノードを複数有する非均一メモリ・アクセス（NUMA)コンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置する最適配置装置を提供する。この最適配置装置は、複数のサブ領域を含むヒープであって、各サブ領域は該サブ領域をローカル・メモリの少なくとも一部とする前記ノードに割り当てられる、前記ヒープと、各々対応するスレッドに割り当てられた複数のスタックと、複数のスレッドの各々について、該スレッドを実行するプロセッサの情報を取得するスレッド管理部と、前記ヒープ内のオブジェクトのロックを要求するスレッドから、ロック対象の前記オブジェクトの識別子を取得し、前記オブジェクトの識別子が識別する前記オブジェクトのヘッダ内に前記スレッドの識別子を書き込むロック管理部と、前記ヒープ内の各オブジェクトをグラフノード、該オブジェクトから前記ヒープ内の他のオブジェクトへの参照をエッジ、および各スレッドに割り当てられたスタックをルート・ノードとする複数のオブジェクト参照のグラフを、前記ルート・ノードを出発点としてそれぞれ走査し、現在の走査対象が参照する移動対象のオブジェクトの前記ヘッダ内に前記スレッドの識別子がある場合、該スレッドの識別子が識別するスレッドを実行するプロセッサを含むノードを前記プロセッサの情報から求め、該ノードに割り当てられた前記ヒープ内の前記サブ領域に前記移動対象のオブジェクトを移動させ、現在の走査対象が参照する移動対象のオブジェクトの前記ヘッダ内に前記スレッドの識別子がない場合、現在の走査対象であるオブジェクトの移動先のローカル・メモリを含むノードに割り当てられたいずれかのサブ領域に前記移動対象のオブジェクトを移動させるメモリ管理部とを含む。
【００１８】
好ましくは、前記ロック管理部は更に、スレッドからロックの要求を受けるごとに、該スレッドの識別子、または該スレッドに対し前記スレッド管理部が取得した前記プロセッサの情報である該プロセッサを含むノードの識別子を、前記オブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に上書きする。そして前記メモリ管理部は、前記移動対象のオブジェクトの前記ヘッダ内のスレッドの識別子の代わりに、前記移動対象のオブジェクト内の所定の位置または該オブジェクト内のポインタが指す前記所定の位置にある前記スレッドの識別子または前記ノードの識別子を使用して、前記移動対象のオブジェクトの移動先を決定する。
【００１９】
また好ましくは、前記メモリ管理部は、前記オブジェクト参照のグラフの走査の結果、到達しなかった１以上のオブジェクトのヒープ内の領域を再利用するガーベッジ・コレクタである。そして前記オブジェクト参照のグラフの走査は、前記ヒープに利用可能な空き領域がなくなったことに応答して実行されるGCと平行してまたはその前後に行われる。
【００２０】
また好ましくは、前記オブジェクト内の前記所定の位置は、前記オブジェクト内のロックワード内の位置である。
【００２１】
好ましくは、前記スレッド管理部は、複数のスレッドの各々について、該スレッドを実行するプロセッサの情報として該プロセッサを含むノードの識別子を取得し、該ノードの識別子を前記スレッドのスレッド構造体に書き込む。そして前記メモリ管理部は、前記現在の走査対象が参照する前記移動対象のオブジェクトの前記ヘッダ内にスレッドの識別子がある場合、該スレッドの識別子が識別するスレッドの前記スレッドの構造体に書き込まれた前記ノードの識別子を取得し、該ノードの識別子が識別するノードに割り当てられたサブ領域に前記移動対象のオブジェクトを移動させる。
【００２２】
以上、NUMAコンピュータ・システム上に構築される仮想マシン環境においてオブジェクトを最適配置する最適配置装置として本発明を説明したが、本発明は、NUMAコンピュータ・システムにより実施される、仮想マシン環境においてオブジェクトを最適配置する最適配置方法および最適配置プログラムとして把握することもできる。
【発明の効果】
【００２３】
本願発明によれば、スレッドがクリティカルセッションで排他的にアクセスしたオブジェクトについて最適配置を行うので、本発明によれば、NUMAコンピュータ・システム上に構築される仮想マシン環境において、無駄や漏れのない効率的なオブジェクトの最適配置が可能となる。また、オブジェクトのロック時に最適配置位置に関する情報を取得してオブジェクト内に記録するので、GC時に最適配置位置情報を取得するためのコストが発生せず、GCコストを増加させることなくオブジェクトを最適配置することが可能となる。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００２４】
【図１】図１（ａ）は、本発明を適用可能なNUMAコンピュータ・システムの主要構成要素を示す上位レベルの構成図である。図１（ｂ）は、図１（ａ）に示すNUMAコンピュータ・システムの典型的ノードの主要ハードウェア構成要素を示す構成図である。
【図２】図２は、本発明の実施形態に係るJava実行時環境の機能ブロック図である。
【図３】図３（ａ）は、ヒープの一例を示す図である。図３（ｂ）は、オブジェクト参照グラフとスタックの関係の一例を示す図である。
【図４】図４は、本発明の実施形態に係るメモリ管理部２３８によるオブジェクトの最適配置処理の流れの一例を示すフローチャートである。
【図５】図５（ａ）は、本発明の実施形態による、アプリケーション実行時間におけるオブジェクト参照グラフ内のオブジェクトのロック状態の一例を示す図である。図５（ｂ）は、最適配置位置情報の承継関係の一例を示す図である。
【発明を実施するための形態】
【００２５】
以下、本発明を実施するための形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２６】
図１（ａ）は、本発明の実施形態によるNUMAコンピュータ・システム１００の主要構成要素を示す上位レベルの構成図である。コンピュータ・システム１００は複数のノード１０２、１０４、１０６、および１０８を含む。なお、図１のシステムの例には４つのノードを示すが、ノード数は異なることもあることを理解されたい。各ノードは、任意のノードを他の任意のノードとやりとりできるようにする、ノード間通信ネットワーク１１０によって接続される。ノード間通信ネットワーク１１０の目的は、各装置がノード境界をまたいで通信できるようにすること、具体的には、任意のノード中のプロセッサが、他の任意のノード中にあるメモリにアクセスできるようにすることである。
【００２７】
好ましい実施形態では、ノード間通信ネットワーク１１０は、ファブリックバスであってよい。これに代えてノード間通信ネットワーク１１０として、既存の、または今後開発される様々な代替手段を使用することもできることは言うまでもない。
【００２８】
図１（ｂ）は、好ましい実施形態による、NUMAコンピュータ・システム１００の典型的ノードの主要ハードウェア構成要素の一例を示す構成図である。本明細書に含まれる記述の一貫性を保つために、ノードを総称して参照番号１０２とするが、これはノード１０２、１０４、１０６、および１０８のいずれでもあり得ることを理解されたい。ノード１０２は、分散メイン・メモリからの命令および他のデータに基づいて基本的な機械処理機能を実施する複数の中央処理装置（CPU）１２０および１２４を含む。なお本明細書では、プロセッサという用語はCPUと同義であるとしてこれらを区別せずに使用する。各CPU１２０および１２４は、データおよび命令の一時的記憶のためにそれぞれのキャッシュ１２２および１２６を含み、あるいはそれを制御する。
【００２９】
大規模なマルチプロセッサ・コンピュータ・システムでは、通常キャッシュは、複数のレベルで複数の構造として存在する。例えばCPUは、そのCPUで実行される命令の記憶専用のレベル１キャッシュ（Ｌ１命令キャッシュ）、そのCPUによって操作される命令以外のデータの記憶専用の、物理的に別個のレベル１キャッシュ（L1データ・キャッシュ）、および命令と他のデータの両方を記憶し、L1命令キャッシュおよびL1データ・キャッシュに補給するために使用されるレベル２キャッシュ（L2キャッシュ）を含むことができる。図２では、この１つまたは複数のキャッシュ構造は、それぞれのプロセッサごとに単一ブロック１２２および１２６として単純化した形で表されている。本発明のためには、各プロセッサでのキャッシュの正確な実装の詳細は重要ではない。他の多くの変形形態が可能であり、本発明は、どんな具体的なキャッシュ設計にも限られるものではなく、必ずしもキャッシュの使用を必要とするとは限らない。  
【００３０】
NUMAコンピュータ・システム１００は、分散メイン・メモリを利用し、ノード１０２ごとに別個のローカル・メモリ１２８を含む。NUMAコンピュータ・システム１００内のアドレス指定可能なメイン・メモリの合計は、各ノード中のアドレス指定可能なローカル・メモリ１２８の総和である。NUMAコンピュータ・システム１００全体のすべてのＣＰＵは、同じアドレス指定可能な分散メイン・メモリを共用する。したがって、分散メイン・メモリの実アドレス空間は、NUMAコンピュータ・システム１００全体で一定であり、ローカル・メモリ１２８中の任意のメモリ位置は、すべてのプロセッサおよびすべてのノードにとって同じ、一意の実アドレスを持つ。  
【００３１】
ノード間インターフェイス・ユニット１３０は、ノード１０２をノード間通信ネットワーク１１０に接続し、それによってノード１０２がNUMAコンピュータ・システム１００内の他のノードとやりとりできるようにする。ノード間インターフェイス・ユニット１３０は、ノード間で渡されるデータの一時記憶のためのキャッシュまたはバッファを含んでよい。
【００３２】
入出力インターフェイス・ユニット１３２は、１以上の入出力バスを介した１以上の入出力装置（図（ｂ）では記憶装置１３４）への通信を提供する。入出力バスは、直接アクセス記憶装置（ＤＡＳＤ）、テープ装置、ワークステーション、印刷装置、および専用の通信線またはネットワークを介した遠隔装置または他のコンピュータ・システムとの通信のための遠隔通信アダプタなど、従来の入出力装置との
通信に適したどんなタイプのものでもよい。例えば、入出力バスは、業界標準のＰＣＩバスとすることもできる。なお、すべてのノード１０２が入出力インターフェイス・ユニット１３２や接続された入出力装置を含む必要はないことを理解されたい。
【００３３】
内部ノード・バス１３６は、ノード１０２の各種構成要素間の通信を提供する。具体的には、内部ノード・バス１３６は、ＣＰＵ１２０および１２４によって発せられたメモリ・アクセスに応答して、ローカル・メモリ１２８とそれぞれのＣＰＵ１２０および１２４のキャッシュ１２２および１２６との間でデータを転送する。ローカル・メモリ１２８でのロジックを監視して、ノード間インターフェイス・ユニット１３０、または内部ノード・バス１３６自体、あるいはその両方は、メモリ・アクセスで要求された個々の実アドレスが、ノード１０２のローカル・メモリ１２８に含まれているか、それとも別の（遠隔）ノードのローカル・メモリに含まれているか判定し、場合に応じて、そのメモリ・アクセスを、ローカル・メモリ１２８、または遠隔ノードとの通信のためのノード間インターフェイス・ユニット１３０に送る。
【００３４】
ローカル・メモリ１２８内の実アドレスへのメモリ・アクセスは内部ノード・バス１３６を横切り、比較的短いマシン・サイクル数で戻る。その一方遠隔ノードのローカル・メモリ内の実アドレスへのメモリ・アクセスは、要求側ノードの内部ノード・バス１３６、要求側ノードのノード間インターフェイス・ユニット１３０、ノード間通信ネットワーク１１０、応答側ノードのノード間インターフェイス・ユニット１３０、および応答側ノードの内部ノード・バス１３６を横切ってなされる。その結果、遠隔ノードへのメモリ・アクセスは、一般に、相対的に多数のサイクルを必要とする。
【００３５】
図１（ａ）には４つのノードを備えるNUMAコンピュータ・システム１００が示されており、図１（ｂ） には２つのＣＰＵ および他の各種装置を備える典型的ノードが示されているが、図１（ａ）および図１（ｂ）は、NUMAコンピュータ・システムの１つの可能な構成の単純化した一例を示すためのものにすぎず、そうした構成での可能な装置の数およびタイプは異なることがあり、NUMAコンピュータ・システム１００が、しばしば、図示しないその他の装置も含むことがあることを理解されたい。さらに、すべてのノードが同一であることも、すべてのノードが同数のＣＰＵまたは同量のアドレス指定可能なローカル・メモリを備えることも必要とされないことも理解されたい。
【００３６】
図２は、本発明の実施形態による実行時環境の機能ブロック図である。本発明に係る実行時環境は、図１を参照して説明したNUMAコンピュータ・システムとしてのハードウェア２０５を用いて実施される。なお図２には、Java実行時環境を示し、以下ではJava実行時環境を例に説明するが、本発明は、Common  LanguageRuntime(CLR）等、プラットフォーム間の違いを吸収し、クラス・ライブラリやGC等のサービスを提供する他の共通実行時環境について適用可能なことを理解されたい。
【００３７】
Java言語は、Sun Microsystems社によって作成された言語である。Javaソフトウェア・ツールおよびJava開発者ツールに関する情報は、オンラインＵＲＬ http://www.sun.com/javaで入手できる。Javaの使用とJavaアプリケーションおよびJavaアプレットの作成は、当技術分野において公知であるため本明細書では詳細な説明を省略する。ソフトウェア開発者によって書かれたJavaソース・コードは、特定のプラットフォーム用に設計されたフォーマットにコンパイルされるのではなく、実行時環境を有するすべてのシステムで実行できるバイト・コードという中間形式にコンパイルされる。Javaバイト・コードは後述するクラスファイル２０２として、入出力インターフェイス・ユニット１３２を介して、ローカル・ハード・ディスク（図１（ｂ）の記憶装置１３４を参照）や他のコンピュータ・システムからJava仮想マシン２２０へ移される。
【００３８】
Java仮想マシン２２０は、JavaアプリケーションまたはJavaアプレットの場合にはウェブ・ブラウザが、オペレーティング・システム２１０とその下層のハードウェア２０５に無関係に全てのシステムで走行できるようにするプラットフォームである。Java仮想マシン２２０は、マシンに依存しない命令であるJavaバイト・コードによって表現されるプログラムを受け取って、これをマシンに依存するネイティブの命令に変換する。そしてJava仮想マシン２２０は、変換したネイティブの命令を、図１（ｂ）を参照して上述したいずれかのノード内のプロセッサで直接またはオペレーティング・システム２１０を介して実行する。そのようなオペレーティング・システム２１０としては、例えばAIX(登録商標）オペレーティング・システムやLinux(商標）等オペレーティング・システムがある。
【００３９】
Javaのソース・コードから生成されたJavaバイト・コードは、１つまたは複数のクラスに編成される。このクラスは、仮想マシン２２０ によるコンピュータ・プログラムの実行中に割り振られ、使用されるオブジェクトのテンプレートを表す。クラスは、実行可能バイト・コードとそのような実行可能バイト・コードが頼るデータの両方を含むクラスファイル２０２に編成され、該クラスファイル２０２はオブジェクトに関する他の情報を含んでもよい。このようなクラスファイル２０２は、Javaソース・コードに基づきJavaコンパイラによって生成される。Javaソース・コード、Javaコンパイラ、およびクラスファイルは当技術分野において公知であるため本明細書では詳細な説明を省略する。
【００４０】
クラスローダ２２２は、クラスファイル２０２内のJavaバイト・コードによって指定される所与の動作のために、クラス・ライブラリ２２４から１以上のJavaクラス・ライブラリを取り出す。そして、クラスローダ２２２は、クラスファイル２０２と取り出した１以上のJavaクラス・ライブラリを、実行エンジン２２８のメモリ２３０へ格納することにより動的にロードする。なおクラスローダ２２２は、メモリ２３０へ格納する前に、当技術分野で既知の方法によりクラス検証を実行して、Javaセキュリティに合致することを検証してもよい。
【００４１】
インタープリタ２３２は、クラスローダ２２２によるクラスファイル２０２のロードに応答して、各クラスファイル２０２に含まれるJavaバイト・コードを１つ１つ解釈しそれぞれに対応する動作を行う。これにより、１以上のスレッドがノード１０２内のプロセッサにより実行されることになる。
【００４２】
なお、インタープリタ２３２によるJava バイト・コードの解釈と実行は、当技術分野で公知の動作であるため本明細書では詳細な説明を省略する。また実行エンジン２２８は、インタープリタ２３２に加えて、ジャストインタイム（JIT)・コンパイラ（図示しない）を含むとしてもよい。JITコンパイラは、実行前に一連のJavaバイト・コードをまとめて変換することで実行時のオーバヘッドをなくし、実行速度を向上させる。JITコンパイラもまた、当技術分野で公知の動作であるため本明細書では詳細な説明を省略する。
【００４３】
メモリ２３０は、インタープリタ２３２によるJavaバイト・コードの実行のため、スタックとヒープに大別される定義された複数の記憶領域を含む。スタックは、マルチ・スレッドをサポートするために、スレッドが起動するたびにスレッドごと割り当てられる記憶領域である。メモリ２３０はまた、プログラムカウンタ（PC)レジスタも含む。
【００４４】
一般に、Java仮想マシン２２０のスタックは、後入れ先出し(LIFO:Last-In-First-Out) のデータ構造を実装する。スタック上のデータの単位はフレームと呼ばれ、スレッドが実行するメソッドのローカル変数の配列や、処理対象のデータを保持するスタック (Operand Stack)、当該メソッドのクラスの実行時コンスタント・プールへの参照を保持する。スレッドによりメソッドが起動されると、スタック上にフレームが積み上げられ、呼び出されたメソッドがアクティブになる。メソッドの処理が終了すると、対応するフレームは削除され、呼び出し元のメソッドが再びアクティブになる。  
【００４５】
ヒープは、仮想マシン２２０の起動時に割り当てられる、全てのスレッドから共有される記憶領域である。ヒープは、オブジェクトのインスタンスのような GC 対象となる動的なデータを格納する領域と、クラス構造などの静的なデータを格納するメソッド・エリア (Method Area)と呼ばれる領域とを含む。本発明ではヒープ内のGC 対象となる記憶領域は複数のサブ領域を含み、各サブ領域は該サブ領域をローカル・メモリ１２８の少なくとも一部とするノード１０２に割り当てられる。なお、サブ領域の位置、サイズ、および数は、オペレーティング・システム２１０やJava仮想マシン２２０に依存し、１つのノード１０２に複数のサブ領域が割り当てられる場合もある。
【００４６】
スレッド管理部２３４は、複数のスレッドの各々について、該スレッドを実行するプロセッサの情報を取得する。好ましくは、スレッド管理部２３４は複数のスレッドの各々について、該スレッドを実行するプロセッサの情報として該プロセッサを含むノードの識別子を取得し、該ノードの識別子を上記スレッドのスレッド構造体に書き込む。なお、各スレッドのスレッド構造体の格納場所は、オペレーティング・システム２１０やJava仮想マシン２２０に依存する。
【００４７】
ノードの識別子の取得には、マシン命令がサポートされている場合にはマシン命令を利用してよい。そのようなマシン命令を利用できない場合、システムコールによりプロセッサIDを取得し、取得したプロセッサIDを対応表によりノード識別子に変換する。コストの観点から、システムコールは一定の間隔をあけて行うのが好ましい。一例としてシステムコールは、safe pointとよばれる時々実行されるコード地点の実行の際、あるいは、オブジェクト割当バッファをスレッドが割り当てる際に行ってよい。
【００４８】
スレッド管理部２３４はまた、並列に実行される複数のスレッドをサポートしてもよい。具体的にはスレッド管理部２３４はスレッドのオブジェクトを生成し、生成したスレッドのstartメソッドを呼び出してスレッドを実行することによりスレッドの生成を管理してよい。更にスレッド管理部２３４は、優先レベルを利用することによって、スレッドの優先実行をサポートしてもよい。
【００４９】
ロック管理部２３６は、２以上のスレッドが同一のオブジェクトにアクセスを試みる結果生ずるコンフリクトを解決するために各オブジェクトが所有するロックの管理を行う。ロック管理部２３６によるロックの管理により、あるスレッドがロックを獲得しているとき、他のスレッドが同じロックを獲得しようとするとそのスレッドはブロックされる。また、ロックを獲得していたスレッドがロックを解放したときに、ブロックしていたスレッドが同じロックを獲得することが可能になる。
【００５０】
一般に、共有リソースの排他制御を実現するためには、ロックとクリティカルリージョンの概念が利用される。クリティカルリージョンとは、スレッド間で共有するリソース（例えばオブジェクト）が利用される実行コードの部分をいう。各スレッドは、クリティカルリージョンに入る前にロックを獲得し、コードの実行を行い、クリティカルリージョンから出るときにロックを解放する。このようにしてロックは、同時にはただ1つのスレッドのみが獲得できる。
【００５１】
Javaソース・コードでは、クリティカルリージョンはsynchronized修飾子を使用して指定される。そしてJavaソース・コードに含まれるsynchronized修飾子は、バイト・コードに変換される。具体的には、Javaソース・コードに含まれるsynchronized修飾子は、オブジェクトに対しそのロックを取得するためにmonitorenterバイト・コードに変換される。あるいはJavaソース・コードに含まれるsynchronized修飾子は、monitorenter命令により取得されたロックを解放するためにmonitorexitバイト・コードに変換される。但し、monitorenterバイト・コードおよびmonitorexitバイト・コードの実装について定義はされていない。
【００５２】
ロック管理部２３６は、monitorenterバイト・コードおよびmonitorexitバイト・コードの実装として、以下に説明する処理を行う。即ち、ロック管理部２３６はmonitorenterバイト・コードの実装として、ヒープ内のオブジェクトのロックを要求するスレッドから、該スレッドの識別子及びロック対象のオブジェクトの識別子を取得し、該オブジェクトの識別子が識別するオブジェクトのヘッダ内にスレッドの識別子を書き込む。具体的には、ロック管理部２３６はcompare-and-swap(CAS)命令を使用してオブジェクトのヘッダ内のロックワード内にスレッドの識別子を書き込む。
【００５３】
ロック管理部２３６はまたmonitorexitバイト・コードの実装として、ヒープ内のオブジェクトのロックの解放を要求するスレッドから、ロック対象のオブジェクトの識別子を取得し、該オブジェクトの識別子が識別するオブジェクトのヘッダ内に書き込まれたスレッドの識別子をクリアする。具体的には、ロック管理部２３６はCAS命令を使用してオブジェクトのヘッダ内のロックワード内に書き込まれたスレッドの識別子をクリアする。
【００５４】
ロック管理部２３６はまた、ロック予約をサポートしてもよい。ここでロック予約とは、頻繁にロックが要求される場合にオブジェクトの所有者をあるスレッドに固定することをいう。ロック予約の場合ロック管理部２３６は、ロック予約対象のオブジェクトに対し、そのロックワード内にスレッドの識別子を書き込むことに加えて、ロック予約がなされたことを示す予約ビットをセットする。そして該オブジェクトに対しロック要求がなされると、ロック管理ブ２３６は、ロックワード内のスレッド識別子および予約ビットをチェックする。CAS命令を省略できるこのロック予約はロックのコストを下げる効果を有する。なお、ロック予約は既知の技術であるため（例えば、Kiyokuni Kawachiya, Akira Koseki, and Tamiya Onodera, "LockReservation: Java Locks Can Mostly Do Without Atomic Operations," ACMConference on Object-Oriented Programming, Systems, Languages, and Applications(OOPSLA 2002), pp. 130-141, November 4-8, 2002.を参照）、より詳細な説明はここでは省略する。
【００５５】
ロック管理部２３５によりオブジェクトのヘッダ内に書き込まれたスレッドの識別子は、スレッド管理部２３４によりスレッド構造体に書き込まれたプロセッサの情報（好ましくは該プロセッサを含むノードの識別子）を取得するために、後述するメモリ管理部２３８により利用される。しかしオブジェクトのロックワード内に書き込まれるスレッドの識別子は、上述したようにロックの解放によりクリアされるので、そのような場合メモリ管理部２３８はプロセッサの情報を取得できない。これに対しロック予約されるオブジェクトについては、ロックワード内に書き込まれたスレッドの識別子は比較的長い間クリアされずに残る。しかし突出してホットなコードがないFlat profileなアプリケーションでは、ロック予約が起きない可能性がある。
【００５６】
そこで好ましくは、ロック管理部２３５は、スレッドからロックの要求を受けるごとに、該スレッドの識別子、または該スレッドに対してスレッド管理部２３４が取得したプロセッサの情報（好ましくは該プロセッサを含むノードの識別子）を、ロック対象のオブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に上書きする。プロセッサの情報を書き込む場合、ロック管理部２３５は、ロックを要求するスレッドのスレッド識別子からそのスレッド構造体を特定し、特定したスレッド構造体からスレッド管理部２３４が格納したプロセッサの情報を読み取る。
【００５７】
ここでオブジェクト内の所定の位置はオブジェクトのヘッダ内であってよい。ロックワード内にスレッドの識別子またはノード識別子を記録する領域（8ノードの場合は３ビットの領域）を確保できる場合、ロック管理部２３５はCAS命令によりロックワード内にスレッドの識別子またはノード識別子を書き込む。そのような領域がロックワード内に確保できない場合、ロック管理部２３５はCAS命令とは別の命令によりロックワード外にスレッドの識別子またはノード識別子を書き込む。なお、ロック対象のオブジェクト内のポインタが指す所定の位置とは、例えば、fatlockと呼ばれるmonitor enterの一実装において利用されるmonitor構造体のように、オブジェクトと独立して存在し、オブジェクトからポインタでさされている領域内の空き領域内の位置であってよい。  
【００５８】
なお上述したように、オブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に書き込まれるスレッドの識別子またはノード識別子は、該オブジェクトに対してロック要求がなされるたび上書きされる。言い換えると、オブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に書き込まれるスレッドの識別子またはノード識別子はロックの解放によりクリアされない。そのため、後述するメモリ管理部２３８は常にオブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に書き込まれたスレッドの識別子またはノード識別子を取得でき、該オブジェクトに最後にアクセスしたプロセッサを含むノードを知ることができる。
【００５９】
メモリ管理部２３８は、オブジェクト参照グラフを走査して、オブジェクトの最適配置を行う。ここでメモリ管理部２３８は、オブジェクト参照のグラフの走査の結果、到達しなかった１以上のオブジェクトのヒープ内の領域を再利用するガーベッジ・コレクタであってよい。この場合、メモリ管理部２３８は、ヒープ内に利用可能な空き領域がなくなったことに応答して実行されるGCのタイミングで、オブジェクトの最適配置を行ってよい。本実施例ではガーベッジ・コレクタの一機能として実装されるメモリ管理部２３８を説明する。なお、ガーベッジ・コレクタは、メモリ上のヒープ内で不要なった領域を再利用可能にするプロセスである。
【００６０】
このようなメモリ管理部２３８はまた、ヒープ内の各サブ領域を対応するノードにマッピングしてもよい。上述したように本発明では、ヒープ内のGC 対象となる記憶領域は複数のサブ領域に分割され、各サブ領域は、該サブ領域をローカル・メモリ１２８の少なくとも一部とするノード１０２に割り当てられる。メモリ管理部２３８はこのサブ領域とノード間のマッピングを行ってよい。そしてメモリ管理部２３８は、あるノードのメモリを要求されると、該ノードに割り当てられたサブ領域から空きブロックを見つけてこれを返してよい。
【００６１】
図３（ａ）は、サブ領域３０２〜３０８に分割された、ヒープ内のGC 対象となる記憶領域３００の一例を示す。空きブロックの管理は従来のメモリ管理方法を用いてよい。従来の基本的なメモリ管理方法として、例えば参照カウント法、マーク＆ スイープ法、および複写法がある。これらメモリ管理は、サブ領域ごとに独立して行うのではなく、GC 対象となるヒープ全体に対して行ってよい。
【００６２】
カウント法では、各オブジェクトは、他のオブジェクトからの参照数を示すカウンタをもつ。各オブジェクトのカウンタは、参照される度にその値を１増分され、参照が終わる度その値を１減算される。カウンタが０になると、これは該カウンタをもつオブジェクトがどこからも参照されない、即ち不用になったことを示すため、そのカウンタをもつオブジェクトを解放する。
【００６３】
マーク＆ スイープ法では、ヒープ内のオブジェクトにそれぞれ対応する複数の領域を含むマークテーブルを用意し、最初マークテーブル上の各領域をクリアして初期化する。各領域は、対応するオブジェクトが他のオブジェクトから参照されるとマークされ、参照が終わるとマークがクリアされる。ヒープ内に空き領域がなくなると、マークテーブルがチェックされ、マークのない領域に対応するオブジェクトが解放される。
【００６４】
複写法では、ヒープ内の領域をFrom領域とTo領域に分ける。From領域内の残すべきオブジェクトは、To領域に複写する。これによりTo領域には生き残った（不要となっていない）オブジェクトだけが存在することになる。次回は現在のFrom領域をTo領域とし、To領域をFrom領域として、その操作を交互に繰り返す。
【００６５】
なお、空きブロックの管理方法は上記説明した基本的アルゴリズムに限定されず、例えばオブジェクトの寿命に見られる傾向を利用した世代別GC等、他の応用アルゴリズムも利用してよい。ただし本発明においてメモリ管理部２３８は、不要となったメモリ領域を見つけるために行うオブジェクト参照グラフの走査において、走査の出発点であるルート・ノードとして各スレッドに割り当てられたスタックを優先して走査し、その走査においてオブジェクトの最適配置を行う。
【００６６】
具体的には、メモリ管理部２３８は、最適配置を行うために各スレッドに割り当てられたスタックをルート・ノードとするオブジェクト参照のグラフを走査する際に、現在の走査対象が参照するオブジェクトである移動対象オブジェクトのヘッダ内にスレッドの識別子があるか否かを判定する。スレッドの識別子がある場合、メモリ管理部２３８は、該スレッドの識別子が識別するスレッドを実行するプロセッサを含むノードの情報をプロセッサの情報から求め、該ノードに割り当てられたサブ領域に移動対象オブジェクトを移動させる。一方、移動対象オブジェクトのヘッダ内にスレッドの識別子がない場合、メモリ管理部２３８は、現在の走査対象オブジェクトの移動先のローカル・メモリを含むノードにマップされたいずれかのサブ領域に移動対象オブジェクトを移動させる。なお、現在の走査対象オブジェクトがルート・ノードのスタックである場合におけるその移動先とは、該スタックを割り当てられたスレッドを実行するプロセッサを含むノードに割り当てられたサブ領域である。
【００６７】
ここで最適配置を行うために走査されるオブジェクト参照のグラフは、ヒープ内の各オブジェクトをグラフノード、該オブジェクトから前記ヒープ内の他のオブジェクトへの参照をエッジ、および各スレッドに割り当てられたスタックをルート・ノードとするグラフである。このようなオブジェクト参照のグラフは、各オブジェクトが保持する参照情報を基に作成してよい。各オブジェクトはそのヘッダに該オブジェクトのクラス情報を識別できる情報を有し、クラス情報にはそのような参照情報の格納場所に関する情報が含まれる。
【００６８】
本発明では、このような複数のオブジェクト参照のグラフの各々を、ルート・ノードを出発点としてそれぞれ走査し、その走査においてオブジェクトの最適配置を行う。ここで図３（ｂ）に、オブジェクト参照のグラフ３１８とスタック３１０および３１４との関係の一例を示す。図３（ｂ）に示すスタック３１０、３１４には、それぞれフレームが積み上げられており、フレーム３１２、３１６には、図中矢印で示すように、スタック上のローカル変数からオブジェクト参照のグラフ３１８上のオブジェクトへの参照関係が含まれている。このようにスタックはヒープ内のオブジェクトを参照するローカル変数を含み、本発明ではスタックをルート・ノードとするオブジェクト参照グラフを走査して最適配置を行う。
【００６９】
上述したようにスレッド管理部２３４がプロセッサの情報として該プロセッサを含むノードの識別子を対応するスレッドのスレッド構造体に格納する場合、メモリ管理部２３８は次のように最適配置を行う。即ちメモリ管理部２３８は、現在の走査対象が参照する移動対象オブジェクトのヘッダ内にスレッドの識別子がある場合、該スレッドの識別子が識別するスレッドのスレッド構造体からノード識別子を取得する。そしてメモリ管理部２３８は、ノードの識別子が識別するノードに割り当てられたサブ領域に移動対象オブジェクトを移動させる。現在の走査対象が参照する移動対象オブジェクトのヘッダ内にスレッドの識別子がない場合、メモリ管理部２３８は、現在の走査対象の移動先を承継させて移動対象オブジェクトを移動させる。即ち、メモリ管理部２３８は、現在の走査対象の移動先のローカル・メモリを含むノードに割り当てられたいすれかのサブ領域に移動対象オブジェクトを移動させる。
【００７０】
また上述したようにロック管理部２３６が更に、スレッドからロックの要求を受けるごとに、該スレッドの識別子、または該スレッドに対しスレッド管理部２３４が取得したプロセッサの情報としてのノードの識別子を、ロック対象のオブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置に上書きする場合、メモリ管理部２３８は次のように最適配置を行う。即ちメモリ管理部２３８は、現在の走査対象が参照する移動対象オブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置にスレッド識別子またはノード識別子がある場合、ノードの識別子が識別するノードに割り当てられたサブ領域に移動対象オブジェクトを移動させる（所定の位置にスレッドの識別子がある場合は上述したようにスレッド構造体からノード識別子を取得する）。移動対象オブジェクト内の所定の位置または該オブジェクト内のポインタが指す所定の位置にスレッド識別子およびノード識別子のいずれもない場合、メモリ管理部２３８は、現在の走査対象の移動先を承継させて移動対象オブジェクトを移動させる。即ち、メモリ管理部２３８は、現在の走査対象の移動先のローカル・メモリを含むノードに割り当てられたいすれかのサブ領域に移動対象オブジェクトを移動させる。
【００７１】
なお、メモリ管理部２３８は、NUMAコンピュータ・システム１００内のいずれかのノードのいずれかのCPU上で動作し、かつメモリ管理モジュールを呼び出すスレッドによって実現される。同様に、ロック管理部２３６は、NUMAコンピュータ・システム１００内のいずれかのノードのいずれかのCPU上で動作し、かつロック管理モジュールを呼び出すスレッドによって実現される。スレッド管理部２３４もまた、NUMAコンピュータ・システム１００内のいずれかのノードのいずれかのCPU上で動作し、かつスレッド管理モジュールを呼び出すスレッドによって実現される。
【００７２】
次に図４に示すフローチャートを参照して、本発明の実施の形態に係るメモリ管理部２３８によるオブジェクトの最適配置処理の流れを説明する。なお、図４に示す最適配置処理は、GCが発生するタイミングで（同時であっても、その前後であってもよい）、GCが発生する都度行われる。従って、最適配置処理が開始される時点において、複数のスレッドの各々は、スレッド管理２３４の処理により、そのスレッド構造体に、該スレッドを実行するプロセッサに関する情報、好適には該プロセッサを含むノードの識別子を有する。またヒープ内の複数のオブジェクトの各々は、スレッドのロック対象となった場合、そのヘッダ内にロックを要求したスレッドの識別子または上記プロセッサに関する情報を有する。
【００７３】
図４において、処理はステップ４００から開始し、メモリ管理部２３８は、NUMAコンピュータ・システム１００内の各プロセッサにより実行される複数のスレッドの中に、未だ最適配置処理の対象となっていない未処理のスレッドがあるか否かを判定する。未処理のスレッドがある場合（ステップ４００：YES)、メモリ管理部２３８は、未処理のスレッドT1を取得して、該スレッドT1に割り当てられたスタックS1を、オブジェクト参照グラフのルート・ノード、即ち走査の出発点とする（ステップ４０５）。
【００７４】
続いてメモリ管理部２３８は、スレッドT1のスレッド構造体に格納されるプロセッサ情報から、スレッドT1を実行するプロセッサを含むノードの識別子を取得し、これを親オブジェクトの移動先を承継させるために使用する変数である現在のノードIDとする（ステップ４１０）。またメモリ管理部２３８は、スタックS1を現在の走査対象Oとする（ステップ４１５）。
【００７５】
続いてメモリ管理部２３８は、現在の走査対象Oの中に未だその処理対象としていない未処理のオブジェクト参照rがあるか否かを判定する（ステップ４２０）。未処理のオブジェクト参照rがある場合（ステップ４２０：YES)、メモリ管理部２３８は未処理のオブジェクト参照rにより参照されるオブジェクトを、現在の移動対象Tとする（ステップ４２５）。そしてメモリ管理部２３８は、移動対象Tのオブジェクトのヘッダ内にスレッドの識別子またはプロセッサの情報（好ましくはノードID）があるか否かを判定する（ステップ４３０）。
【００７６】
ヘッダ内にスレッドの識別子またはプロセッサの情報（好ましくはノードID）がある場合（ステップ４３０：YES)、メモリ管理部２３８は、ヘッダ内のスレッドの識別子またはプロセッサの情報（好ましくはノードID）を基に、上述した方法によりスレッド識別子が識別するスレッドを実行するプロセッサを含むノードを求め、該ノードに割り当てられたサブ領域へ移動対象Tのオブジェクトを移動させる（ステップ４３５）。
【００７７】
一方、ヘッダ内にスレッドの識別子またはプロセッサの情報（好ましくはノードID）がない場合（ステップ４３０：NO)、メモリ管理部２３８は、現在のノードIDが識別するノードに割り当てられたサブ領域へ移動対象Tのオブジェクトを移動させる（ステップ４４０）。ステップ４３５またはステップ４４０から処理はステップ４４５へ進み、メモリ管理部２３８は、移動対象Tのオブジェクトと、ある場合そのノードID（ステップ４３５において求められるノードID)を移動対象Tのオブジェクトに関連付けて、作業領域Wに保存する（ステップ４４５）。そして処理はステップ４２０へ戻る。
【００７８】
ステップ４２０において現在の走査対象Oの中に未処理のオブジェクト参照rがない場合、メモリ管理部２３８は、作業領域Wに格納された、未だ走査対象Oとされていないオブジェクトを現在の走査対象Oとする。また作業領域W内に現在の走査対象Oに関連付けてノードIDが保存されている場合、該ノードIDを新たに現在のノードIDとする（ステップ４５０）。そしてメモリ管理部２３８は、走査対象Oが空であるか否か判定する（ステップ４５５）。
【００７９】
走査対象Oが空でない場合（ステップ４５５：NO）、処理はステップ４２０へ戻る。一方、走査対象Oが空である場合（ステップ４５５：YES）、処理は最初のステップ４００へ戻る。但しステップ４５５において走査対象Oが空であっても、作業領域Wに未だ走査対象Oとなっていない他のオブジェクトが残っている場合は、該オブジェクトに対しステップ４５０および４５５を繰り返す。ステップ４５５から最初のステップ４００に戻り未処理のスレッドがない場合、処理は終了する。
【００８０】
次に図５に示す具体例を用いて、メモリ管理部２３８によるオブジェクトの最適配置処理を説明する。図５（ａ）は、オブジェクトの最適配置処理前のアプリケーション実行時間におけるオブジェクト参照グラフ内のオブジェクトのロック状態の一例を示す。図５（ａ）において参照番号５００、５０２、および５０４により参照される矩形は各々、CPU0、CPU1、CPU 2により各々実行されるスレッド0、スレッド1、スレッド2に割り当てられたスタックを示す。また各グラフはオブジェクト参照グラフを示し、アルファベットaからアルファベットiの各円形はオブジェクトであるノードを示し、実線の矢印は始点のスタック／オブジェクトから終点のオブジェクトへの参照を示す。
【００８１】
図５（ａ）において、ノードcのオブジェクトは、CPU0上で動作するスレッド0によりロックされている。そのためノードcのオブジェクトのヘッダにはスレッド0の識別子が格納される。これに加えてノードcのオブジェクトのヘッダにはCPU0を含むノードのノード識別子が格納されていてもよい。またノードg のオブジェクトは、CPU1上で動作するスレッド1によりロックされている。そのためノードgのオブジェクトのヘッダにはスレッド1の識別子が格納される。これに加えてノードgのオブジェクトのヘッダにはCPU1を含むノードのノード識別子が格納されていてもよい。
【００８２】
このようなロック状態にあるときに、あるノードに割り当てられた１以上のサブ領域のいずれにも空き領域がなくなり、メモリ管理部２３８がオブジェクトの最適配置処理を実行するとする。上述したようにオブジェクトの最適配置処理のために走査されるオブジェクト参照グラフは、各スレッドに割り当てられたスタックをルート・ノードとする。即ち、メモリ管理部２３８は、図５（ｂ）に示すように３つのオブジェクト参照グラフ５０６、５０８、および５１０を、それぞれのルート・ノードであるスタック５００、５０２、５０４を出発点として走査する。なお、ここではオブジェクト参照グラフ５０６、５０８、５１０の順に走査を行うとする。
【００８３】
オブジェクト参照グラフ５０６を走査するメモリ管理部２３８は、まず、スタック５００を現在の走査対象とし、親オブジェクトの移動先を承継させるために使用する変数である現在のノードIDを、スタック５００を割り当てられたスレッド0を実行するCPU0を含むノードのIDとする。次にメモリ管理部２３８は、スタック５００が参照するオブジェクトである移動対象のオブジェクトaのヘッダにスレッドの識別子またはノードの識別子が格納されているか否かを判定する。オブジェクトaはロックの対象となっていないため、そのヘッダにスレッドの識別子またはノードの識別子はない。そこでメモリ管理部２３８は、オブジェクトaを、現在のノードIDが識別するノードに割り当てられたサブ領域へ移動させる。この際メモリ管理部２３８は、オブジェクトaを作業領域Wに保存する。
【００８４】
スタック５００が参照するオブジェクトは他にないため走査は進み、メモリ管理部２３８は作業領域Wから未だ走査対象とされていないオブジェクトaを取り出し、オブジェクトaを現在の走査対象として同様の処理を繰り返す。オブジェクトaが参照するオブジェクトは２つあり、そのうちオブジェクトbはロックの対象ではないため、そのヘッダにスレッドの識別子またはノードの識別子はない。そこでメモリ管理部２３８は、オブジェクトbにその親であるオブジェクトaの移動先即ち最適配置位置を承継させ、オブジェクトbを、現在のノードIDが識別するノードに割り当てられたサブ領域へ移動させる。この際メモリ管理部２３８は、オブジェクトbを作業領域Wに保存する。
【００８５】
一方現在の走査対象オブジェクトaが参照するもう１つのオブジェクトであるオブジェクトcは図５（ａ）に示すようにロックの対象であり、そのヘッダにスレッドの識別子を有し、好適にはノードの識別子も含む。そこでメモリ管理部２３８は、このヘッダ内のスレッドの識別子またはノードの識別子を基に、オブジェクトcをロックしたスレッド0を実行するCPU0を含むノードを求め、該ノードに割り当てられたサブ領域へオブジェクトcを移動させる。この際メモリ管理部２３８は、オブジェクトc とCPU0を含むノードのノードIDを、互いに関連付けて作業領域Wに保存する。
【００８６】
その後オブジェクトaが参照するオブジェクトは他にないため走査はさらに進み、メモリ管理部２３８は、作業領域Wから未だ走査対象とされていないオブジェクトbを取り出し、オブジェクトbを現在の走査対象として同様の処理を繰り返す。しかしオブジェクトbは他のオブジェクトを参照しない空のオブジェクトであるため、続いてメモリ管理部２３８は、作業領域Wから未だ走査対象とされていないオブジェクトcと対応するノードIDを取り出し、それぞれ現在の走査対象および現在のノードIDとする。
【００８７】
そしてメモリ管理部２３８は、オブジェクトcが参照するオブジェクトである移動対象のオブジェクトdのヘッダにスレッドの識別子またはノードの識別子が格納されているか否かを判定する。オブジェクトdはロックの対象となっていないため、そのヘッダにスレッドの識別子またはノードの識別子はない。そこでメモリ管理部２３８は、オブジェクトdにその親であるオブジェクトcの移動先即ち最適配置位置を承継させ、オブジェクトdを、現在のノードIDが識別するノードに割り当てられたサブ領域へ移動させる。オブジェクトcに他に参照するオブジェクトはなく、またオブジェクトdも空のオブジェクトであるため、メモリ管理部２３８による処理はここで終了する。
【００８８】
オブジェクト参照グラフ５０８および５１０について、同様にしてオブジェクトの最適配置を行うと、最終的に図５（ｂ）において点線の矢印で示すような最適配置位置の親オブジェクトから子オブジェクトへの承継が決定する。即ち、ロック対象となったオブジェクトcとオブジェクトgを除いては、各オブジェクトは、親オブジェクトの最適配置位置を承継して親オブジェクトと同じノードのローカル・メモリへ移動する。一方、ロック対象となったオブジェクトcとオブジェクトgは、それぞれ、該オブジェクトに対し最後にロックを要求したスレッドが動作するプロセッサを含むノードに割り当てられたサブ領域へ移動する。
【００８９】
なお、本発明を８ノード（チップ）構成の4.7GHz POWER6（登録商標）に適用し、GCへの追加コストと性能向上を評価したところ、GCの追加コストを増やすことなく、性能向上を確認できた。なお、実験には業界標準のSPECpower_ssj2008ベンチマークを用いた。
【００９０】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図１】
2011081610.tif 000003
【図２】
2011081610.tif 000004
【図３】
2011081610.tif 000005
【図４】
2011081610.tif 000006
【図５】
2011081610.tif 000007