コンピュータの動作制御方法、プログラム及びシステム
【課題】 Fork-Joinのフレームワークにおいて、fork()やjoin()の処理があった際に、スタック割当可能な場合を適切に見極める処理を提供すること。
【解決手段】 Fork-Joinのフレームワークにおいて、次のような判断をする処理が実装される。
− タスク・オブジェクトをワーク・スチーリングのキューに入れる処理では、エスケープしないものとみなす。この処理とは例えば、fork()により行われるものである。
− キューに入れたタスク・オブジェクトの終了を待機する処理では、エスケープしないものとみなす。この処理とは例えば、join()により行われるものである。
− 上記以外でタスク・オブジェクトがエスケープする場合は、エスケープしないものとみなす。
エスケープしないものとみなされると、そのタスク・オブジェクトは、スタック割付される。
【解決手段】 Fork-Joinのフレームワークにおいて、次のような判断をする処理が実装される。
− タスク・オブジェクトをワーク・スチーリングのキューに入れる処理では、エスケープしないものとみなす。この処理とは例えば、fork()により行われるものである。
− キューに入れたタスク・オブジェクトの終了を待機する処理では、エスケープしないものとみなす。この処理とは例えば、join()により行われるものである。
− 上記以外でタスク・オブジェクトがエスケープする場合は、エスケープしないものとみなす。
エスケープしないものとみなされると、そのタスク・オブジェクトは、スタック割付される。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンピュータ・システムにおいて、エスケープ解析(escape analysis)の結果に基づき、スタック割当てを行う技法に関する。
【背景技術】
【０００２】
従来より、コンピュータ・システムにおいて、エスケープ解析の結果に基づき、タスク・オブジェクトを、ヒープでなくスタックに割り当てる処理が行われている。すなわち、可能なら、ヒープでなくスタックにオブジェクトを割当てることによって、ガベージ・コレクションやもヒープ割当てのコストを低減することができる。
【０００３】
ところで、Java(R) 7のJSR 166には、Doug Leaが提案したFork-Joinのフレームワークが提供される。このFork-Joinのフレームワークについては、Doug Lea, "A Java fork/join framework", Java Grande Conference archive, Proceedings of the ACM 2000 conference on Java Grande table of contents, Pages: 36 - 43, 2000を参照されたい。
【０００４】
すなわち、Fork-Joinのフレームワークとは、タスク用のオブジェクト（タスク・オブジェクト）を生成し、fork()やjoin()を利用して、分割統治を実現する仕組みである。すなわち、タスクを、単純且つ短い順次的なメソッドで解決するに十分な小ささまで、再帰的にサブタスクに分割する。
【０００５】
fork()とは、タスクを開始する機能である。実行するスレッドは、forkを呼んだスレッド以外のこともある。join()とは、forkしたタスクが終了するまで待機する機能である。なお、以降、タスクを実行するスレッドを、Workerと呼ぶ。
【０００６】
Java(R) 7の実装では、上記フレームワークの実装に、ワークスティーリング(workstealing)の仕組みが利用されている。すなわち、各WorkerにはWorker固有のタスク・キューが割り当てられる。ある関数内で生成したタスク・オブジェクトを、fork()を利用してタスクを開始する際、タスク・オブジェクトは一旦、fork()を実行したWorkerのタスク・キューに入れられる。また、タスク・オブジェクトに対してfork()を実行したWorkerが、join()を利用してタスク・オブジェクトの終了を待つ際、まだ他Workerによって処理されていない場合は当該Workerが処理し、他Workerが処理している場合はその処理の終了を待機する。各Workerは、処理中のタスクを全て処理した場合、割り当てられたタスク・キュー内のタスクを取り出してタスクの処理を開始し、当該タスク・キュー内の全てのタスクの処理が終了している場合（アイドル状態）、他のWorkerのタスク・キューからタスクを取り出し（スティール）、タスクの処理を行う。各Workerが、割り当てられたタスク・キュー以外のタスク・キュー内のタスクを処理することを、ワークスティーリングと呼ぶ。
【０００７】
以下に、ワークスティーリングを実装した並列実行プログラムの実行の例を示す。
class Fib extends ForkJoinTask {
Integer r;
Fib(int r) { this.r = r; }
protected boolean exec() {
if (r < 2) return true;
Fib f1 = new Fib(r - 1);
Fib f2 = new Fib(r - 2);
f1.fork(); f2.fork();
f2.join(); f1.join();
r = f1.r + f2.r;
return true;
}
}
void main() {
pool.invoke(new Fib(5));
}
【０００８】
このプログラムの実行処理は、次のようになる。
１．Fib f1 = new Fib(r - 1)及びFib f2 = new Fib(r - 2)によって、タスク・オブジェクト（ForkJoinTask)を生成する。
２．f1.fork()、 f2.fork()によって、タスク・オブジェクトのfork()を呼ぶ。このとき、fork()を呼び出したWorker固有のタスク・キューに、タスク・オブジェクトを入れる。その際、他のWorkerがアイドル状態の場合、キューからタスク・オブジェクトがスティールされる。
３．f2.join()、f1.join()によって、タスク・オブジェクトのjoin()を呼び、終了を待つ。このとき、タスク・オブジェクトがスティールされていない場合は、join()内でjoin()を呼び出したWorker固有のタスク・キューからタスク・オブジェクトを取り出し、タスクの処理（exec()）を実行する。タスク・オブジェクトがスティールされている場合は、タスク・オブジェクトの処理（exec()）の終了を待機する。
【０００９】
このような処理の問題点は、粒度の細かい並列性を実現しようとすると、大量のタスク・オブジェクトが生成されることである。また、タスク・オブジェクトのフィールド経由のみから指されるオブジェクトも、同様に大量に生成される。
【００１０】
すると、タスク・オブジェクトをヒープに割り当てるコスト、及びそれに伴うガベージ・コレクションのコストが増えるので、ランタイムのコストが大きくなってしまう、という問題点がある。
【００１１】
この問題点を解決するには、タスク・オブジェクトを、スタック割当てすればよい。しかし、タスク・オブジェクトは、fork()の処理内でヒープ上のキューに配置される。ヒープ上のオブジェクトは、基本的に他のスレッドから参照（エスケープ）可能なため、通常のエスケープ解析では、スタック割当て可能とは判断されない。
【００１２】
特開２００３−１５８７６号公報は、部分コンパイル環境において、オブジェクトをメソッドの呼び出しスタックに割り当てることのできるシステムと方法に関し、Java(R)において、動的にクラスをロードする際に、ロード済みのクラスの情報のみで、エスケープ解析を行う技法を開示する。
【００１３】
特開２００３−２１６４４２号公報は、処理対象である実行プログラムのソースコードに基づいて機械語コードを生成するコード変換部と、この機械語コードによる実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトがエスケープしていない範囲を求める最適化範囲決定部と、このオブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うスカラーリプレイスメント実行部とを備え、エスケープ解析をする対象を限定する技法を開示する。
【００１４】
特開２００８−３３９３２号公報は、ＮＵＭＡコンピュータシステムにおいてコードを再コンパイルするための改良されたシステムに関し、エスケープ解析で、スタック割当て可能と判断したとしたオブジェクトを、ＮＵＭＡでローカルアクセスできる領域に配置する技法を開示する。
【００１５】
しかし、エスケープしたオブジェクトをスタック割当てすることは、これらの従来技術に、示唆も開示もない。
【００１６】
Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, "Escape analysis for Java", Proceeding OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM SIGPLAN Notices Homepage archive Volume 34 Issue 10, Oct. 1999(http://portal.acm.org/citation.cfm?id=320386)は、一般的なエスケープ解析で、スタック割当てを行う手法を記述する。しかし、ここに記述されている技術では、複数のWorkerにアクセスされるオブジェクトは、スタック割当てされない。
【００１７】
Erik Corry, "Optimistic stack allocation for java-like languages", Proceeding ISMM '06 Proceedings of the 5th international symposium on Memory management 2006 (http://portal.acm.org/citation.cfm?id=1133956.1133978)は、投機的にオブジェクトをスタック割当てし、フレームが終了した時点でエスケープしていれば、ヒープに移動する手法を記述する。しかし、ここに記述されている技術では、他のWorkerがアクセス可能になった時点でヒープに移動されるため、全てのタスク・オブジェクトはヒープに移動される。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００３−１５８７６号公報
【特許文献２】特開２００３−２１６４４２号公報
【特許文献３】特開２００８−３３９３２号公報
【非特許文献】
【００１９】
【非特許文献１】Doug Lea, "A Java fork/join framework", Java Grande Conference archive, Proceedings of the ACM 2000 conference on Java Grande table of contents, Pages: 36 - 43, 2000
【非特許文献２】Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, "Escape analysis for Java", Proceeding OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM SIGPLAN Notices Homepage archive Volume 34 Issue 10, Oct. 1999
【非特許文献３】Erik Corry, "Optimistic stack allocation for java-like languages", Proceeding ISMM '06 Proceedings of the 5th international symposium on Memory management 2006
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従って、この発明の目的は、Fork-Joinのフレームワークにおいて、生成されるタスク・オブジェクトに対し、fork()やjoin()の処理があった際に、スタック割当可能な場合を適切に見極める処理を提供することにある。
【課題を解決するための手段】
【００２１】
本発明によれば、Fork-Joinのフレームワークにおいて、次のような判断をする処理が実装される。
− タスク・オブジェクトをワークスティーリングのキューに入れる処理では、エスケープしないものとみなす。この処理とは例えば、fork()により行われるものである。
− キューに入れたタスク・オブジェクトの終了を待機する処理では、エスケープしないものとみなす。この処理とは例えば、join()により行われるものである。
− 上記以外でタスク・オブジェクトがエスケープする場合は、エスケープしないものとみなす。
【００２２】
さらに本発明に従う処理は、タスク・オブジェクトの実行中に、タスク・オブジェクトがエスケープしていないかどうかを解析する。そして、この解析において、エスケープしないと解析されたタスク・オブジェクトを生成したフレーム内で、タスク・オブジェクトをワークスティーリングのキューに入れる処理の後に、タスク・オブジェクトの終了を待機する処理を必ず行っている場合、そのタスク・オブジェクトを、スタックに配置する。
【００２３】
本願発明の知見によれば、タスク・オブジェクトがforkメソッドの実行中、あるいはjoinメソッドの実行中にエスケープしたとしても、joinの処理が終了した時点で、他のWorkerがタスク・オブジェクトにアクセスしないことが保障される場合があることが分かった。説明を補足すると、タスク・オブジェクトに対するjoin()の処理は、任意のWorkerがタスク・オブジェクトのタスクを終了し終わった時点で終了する。つまり、任意のWorkerがタスク・オブジェクトのタスクを処理中に、タスク・オブジェクトをエスケープしない限り、join()の処理後もエスケープしていない状態となる。すなわち、当該の条件では、従来、タスク・オブジェクトをスタック割当てできないと見なされていたところ、本願発明の知見に従うと、安全にタスク・オブジェクトをスタック割当てできると判断してよいことになる。
【発明の効果】
【００２４】
この発明によれば、従来ではタスク・オブジェクトをスタック割当てできないと見なされていた場合でも、実際には安全にタスク・オブジェクトをスタック割当てできるという場合を見出すことができ、これによって、ガベージ・コレクションや、オブジェクトをヒープ割当てするコストが減少するので、結果的に、コンピュータ・システムの処理速度を向上することができるという効果が得られる。
【図面の簡単な説明】
【００２５】
【図１】本発明を実施するためのハードウェアの一例のブロック図である。
【図２】処理環境の機能ブロックのレイヤを示す図である。
【図３】従来技術において、Workerが、タスクをforkする際、タスクをWorkerのキューに入れる様子を示す図である。
【図４】従来技術において、Workerが、新たなタスクをforkする際、タスクをキュー内の前回入れたタスクの次の場所に入れる様子を示す図である。
【図５】従来技術において、Workerが、最後の入れたタスクのjoinを呼び出した際、そのタスクがキューに残っていれば、そのタスクのexecを実行する様子を示す図である。
【図６】従来技術において、他Workerがアイドルになった場合、タスクがキューされているタスクがキューされているWorkerから、タスクをスティールする様子を示す図である。
【図７】従来技術において、Workerがjoinを呼び出したタスクがキューにない場合は、そのタスクが終了するまでWorkerが待機する示す図である。
【図８】エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックまたはヒープに割り当てる処理のフローチャートを示す図である。
【図９】ワークスティーリングのキュー内のタスク・オブジェクトを取得するメソッドを実行する処理のフローチャートを示す図である。
【図１０】従来技術と、本実施例の間の、タスク・オブジェクトの扱いの違いを説明するための図である。
【発明を実施するための形態】
【００２６】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２７】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・バス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(商標)4、インテル社のCore(商標) 2 DUO、Xeon(商標)、AMD社のAthlon(商標)などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量、より好ましくは、４ＧＢ以上の容量をもつものである。
【００２８】
ハードディスク・ドライブ１０８には、オペレーティング・システム２０２（図２）が、格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows XP(商標)、Windows(商標)2003サーバ、アップルコンピュータのMac OS(商標)などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２９】
ハードディスク・ドライブ１０８にはまた、好適にはApacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存され、システムの起動時に、主記憶１０６にロードされる。
【００３０】
ハードディスク・ドライブ１０８にはさらに、Java(R)仮想マシン（ＪＶＭ）２０４（図２）を実現するためのJava(R) Runtime Environmentプログラムが保存され、システムの起動時に、主記憶１０６にロードされる。ＪＶＭ２０４は、本発明に係るヒープ・オブジェクト化の機能を実装する。
【００３１】
ハードディスク・ドライブ１０８にはさらに、アプリケーション・プログラムのバイトコード２０６（図２）が保存されている。
【００３２】
キーボード１１０及びマウス１１２は、オペレーティング・システム２０２が提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ１１４に表示されたアイコン、タスクバー、ウインドウなどのグラフィック・オブジェクトを操作するために使用される。
【００３３】
ディスプレイ１１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。ディスプレイ１１４は、アプリケーション・プログラムの挙動を必要に応じて表示するために使用される。
【００３４】
通信インターフェース１１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース１１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、あるいは処理結果を、クライアント・コンピュータ（図示しない）に返す。
【００３５】
図２は、ソフトウェアのレイヤを示す図である。図２において、最下層は、オペレーティング・システム２０２である。
【００３６】
オペレーティング・システム２０２の上では、オペレーティング・システム２０２に適合するＪＶＭ２０４が動作する。オペレーティング・システム２０２は、システムの起動時に、主記憶１０６に、スタック領域と、ヒープ領域を確保する。スタック領域では、アプリケーションにおいて、関数がコールされる度に、スタック・フレームがスタック領域に積まれ、関数がリターンすると、そのスタック・フレームが、削除される。
【００３７】
ＪＶＭ２０４上では、アプリケーション２０６のバイトコードが動作する。アプリケーション２０６が動作する間に、ＪＶＭ２０４はシステムの状態を監視し、スタックのサイズ圧縮、あるいはワークスティーリングの処理を行い、所定の基準に従い、エスケープ解析を行って、特定の条件を満たす場合に、タスク・オブジェクトを、スタックに割り当てる。
【００３８】
本発明の特徴は、エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックに割り当ててよいかどうかを判断する、判断ルーチンの基準を与える機能にある。この実施例では、そのような判断ルーチンは、ＪＶＭ２０４に含まれている。
【００３９】
本発明のエスケープ解析の判断ルーチンの基準について説明する前に、従来技術におけるFork-Joinフレームワークの振る舞いについて説明する。本発明は、これには限定されないが、科学技術計算のアプリケーション・プログラムに適用することで、特に大きい効果を奏する。
【００４０】
このとき、下記のような、ワークスティーリングを実装した並列実行プログラムを実行するものとする。これは、フィボナッチ数列の計算Fib()の例である。
class Fib extends ForkJoinTask {
Integer r;
Fib(int r) { this.r = r; }
protected boolean exec() {
if (r < 2) return true;
Fib f1 = new Fib(r - 1);
Fib f2 = new Fib(r - 2);
f1.fork(); f2.fork();
f2.join(); f1.join();
r = f1.r + f2.r;
return true;
}
}
void main() {
pool.invoke(new Fib(5));
}
【００４１】
図３は、Workerが、コードにおけるf1.fork()によって、タスクをforkする際、タスクをWorkerのキューに入れる様子を示す図である。すなわち、メイン・スレッドがFib(5)をグローバルのキューに入れる。次にWorker1が、グローバルのキューからFib(5)を取得する。次にWorker1が、Fib(5)のexec()を実行し、タスクFib(4)をWorker1のキューに入れる。
【００４２】
図４は、Workerが、コードにおけるf2.fork()によって、新たなタスクをforkする際、タスクをキュー内の前回入れたタスクの次の場所に入れる様子を示す図である。すなわち、Worker1が、Fib(5)のexec()を実行し、タスクFib(3)をWorker1のキューに入れる。Fib(3)はFib(4)の次に配置される。
【００４３】
図５は、Workerが、f2.join()によって、最後の入れたタスクのjoinを呼び出した際、そのタスクがキューに残っていれば、そのタスクのexecを実行する様子を示す図である。すなわち、Worker1がFib(3)のjoin()を実行し、タスクFib(3)の終了を待つ。その際、Fib(3)は自身のキューに残っているため、キューからFib(3)を取り出し、exec()を実行する。
【００４４】
図６は、他Workerがアイドルになった場合、タスクがキューされているタスクがキューされているWorkerから、タスクをスティールする様子を示す図である。すなわち、アイドルなWorker2が、Worker1のキューからFib(4)をスティールし、exec()を実行する。
【００４５】
図７は、Workerがjoinを呼び出したタスクがキューにない場合は、そのタスクが終了するまでWorkerが待機する示す図である。すなわち、Worker1が、Worker2にスティールされたFib(4)のjoin()、すなわちf1.join()を呼び出し、Worker2がFib(4)のexec()を終了するまで待機する。
【００４６】
このような従来技術におけるFork-Joinフレームワークの挙動から、本願発明者は、次のことを見出した。
・join()が終了した時点では、タスクはキューから削除されている。
・join()が終了した時点で、スティールしたWorkerは、タスクの参照をもっていない場合がある。このとき、exec()内でthisがエスケープしていない。
【００４７】
そこで、fork()、join()内でのエスケープは無視し、exec()内でエスケープしているかどうかを、エスケープ解析内で解析するようにした。
【００４８】
そして、以下の条件が満たされる場合、タスク・オブジェクトへのjoin()が終了した時点で、タスク・オブジェクトへの参照が、他スレッドに存在しないと言えることが分った。
− タスク・オブジェクトを生成するメソッド・フレーム内で、fork()、join()メソッドが呼ばれている。
− 上記メソッド・フレーム内で、上記タスク・オブジェクトが、fork()、join()以外でエスケープしていない。
− 上記タスク・オブジェクトのexec()メソッド内で、thisが他のスレッドにエスケープしていない。
本発明に従うＪＶＭ２０４は、これらの条件を満たしている場合、タスク・オブジェクトはエスケープしていないものとみなし、スタックに割り当てる。
【００４９】
次に、図８のフローチャートを参照して、ＪＶＭ２０４が、エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックまたはヒープに割り当てる処理を説明する。
【００５０】
図８において、ステップ８０２で、ＪＶＭ２０４は、生成したタスク・オブジェクトをワークスティーリングのキューに挿入しているかどうかを判断する。そして、もしそうでないなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５１】
ステップ８０２で、ＪＶＭ２０４が、生成したタスク・オブジェクトをワークスティーリングのキューに挿入していると判断したなら、ＪＶＭ２０４はステップ８０４で、ワークスティーリングのキューに挿入後、タスクの終了を必ず待機しているかどうか判断する。そして、もしそうでないなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５２】
ステップ８０４で、ＪＶＭ２０４が、ワークスティーリングのキューに挿入後、タスクの終了を必ず待機していると判断したなら、ＪＶＭ２０４はステップ８０６で、ワークスティーリングのキューへの挿入、タスクの終了待機以外に、生成したタスク・オブジェクトがエスケープしているかどうかを判断する。そして、もしそうなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５３】
ステップ８０６で、ＪＶＭ２０４が、ワークスティーリングのキューへの挿入、タスクの終了待機以外に、生成したタスク・オブジェクトがエスケープしていないと判断したなら、ＪＶＭ２０４はステップ８０８で、生成したタスク・オブジェクトのタスク処理中に、そのタスク・オブジェクトがエスケープしているかどうかを判断し、もしそうなら、ステップ８１０に進んで、タスクをヒープ上に生成し、もしそうでないなら、ステップ８１２に進んで、タスクをスタック上に生成する。
【００５４】
次に図９のフローチャートを参照して、ＪＶＭ２０４が、ワークスティーリングのキュー内のタスク・オブジェクトを取得するメソッドを実行する時の挙動の例を説明する。すなわち、ステップ９０２で、ＪＶＭ２０４は、実行しようとするメソッドが、生成したタスク・オブジェクトをワークスティーリングのキューに挿入する歳にのみ使用するメソッドかどうか判断し、もしそうでないなら、ステップ９０６に進んで、取得したタスク・オブジェクトがスタック上に配置されている場合、ヒープに移動する処理を行う。
【００５５】
ステップ９０２で、ＪＶＭ２０４が、実行しようとするメソッドが、生成したタスク・オブジェクトをワークスティーリングのキューに挿入する歳にのみ使用するメソッドであると判断したなら、ステップ９０４に進んで、ワークスティーリングのキューに挿入後、タスクの終了を待機する際のみに使用するメソッドかどうかを判断する。もしそうでないなら、ステップ９０６に進んで、取得したタスク・オブジェクトがスタック上に配置されている場合、ヒープに移動する処理を行う。一方、もしそうなら、ステップ９０８で特に何もしない。
【００５６】
図１０は、図３〜図７で示した従来技術の例に、本発明を適用した結果を示す図である。すなわち、この例では、本発明に従うエスケープ解析の結果、Fib(3)とFib(4)が、ヒープでなく、スタックに割り当てられる。この例では、Worker2は、Worker1のスタックに割り当てられたオブジェクトを直接触ることになる。
【００５７】
なお、ＪＶＭではなく、図８及び図９を実装するコードをＪＩＴコンパイラにより生成することにより、本発明を実施してもよい。
【００５８】
さらに、エスケープ解析とそれに基づくスタック割当て処理は、ＪＶＭなどの仮想マシン環境でなく、オペレーティング・システムが直接実行するようにしてもよい。
【００５９】
以上、本発明を、Fork-Joinフレームワークにおけるfork()、join()の呼び出しに関連して説明してきたが、本発明はこれには限定されず、より一般的に、タスクをオブジェクトとしてあらわしており、タスクをバックグラウンドで処理する命令と、タスクの処理終了まで待機する命令とをもち、タスクの実行後は、処理系内でタスクへの参照を持たない任意の処理系に適用可能である。このような処理系の例として、これには限定されないが、例えば、並列分散プログラミング用の処理系であるX10がある。
【符号の説明】
【００６０】
１０２ システム・バス
１０４ ＣＰＵ
１０６ 主記憶
１０８ ハードディスク・ドライブ
２０２ オペレーティング・システム
２０４ ＪＶＭ
２０６ バイトコード
【技術分野】
【０００１】
この発明は、コンピュータ・システムにおいて、エスケープ解析(escape analysis)の結果に基づき、スタック割当てを行う技法に関する。
【背景技術】
【０００２】
従来より、コンピュータ・システムにおいて、エスケープ解析の結果に基づき、タスク・オブジェクトを、ヒープでなくスタックに割り当てる処理が行われている。すなわち、可能なら、ヒープでなくスタックにオブジェクトを割当てることによって、ガベージ・コレクションやもヒープ割当てのコストを低減することができる。
【０００３】
ところで、Java(R) 7のJSR 166には、Doug Leaが提案したFork-Joinのフレームワークが提供される。このFork-Joinのフレームワークについては、Doug Lea, "A Java fork/join framework", Java Grande Conference archive, Proceedings of the ACM 2000 conference on Java Grande table of contents, Pages: 36 - 43, 2000を参照されたい。
【０００４】
すなわち、Fork-Joinのフレームワークとは、タスク用のオブジェクト（タスク・オブジェクト）を生成し、fork()やjoin()を利用して、分割統治を実現する仕組みである。すなわち、タスクを、単純且つ短い順次的なメソッドで解決するに十分な小ささまで、再帰的にサブタスクに分割する。
【０００５】
fork()とは、タスクを開始する機能である。実行するスレッドは、forkを呼んだスレッド以外のこともある。join()とは、forkしたタスクが終了するまで待機する機能である。なお、以降、タスクを実行するスレッドを、Workerと呼ぶ。
【０００６】
Java(R) 7の実装では、上記フレームワークの実装に、ワークスティーリング(workstealing)の仕組みが利用されている。すなわち、各WorkerにはWorker固有のタスク・キューが割り当てられる。ある関数内で生成したタスク・オブジェクトを、fork()を利用してタスクを開始する際、タスク・オブジェクトは一旦、fork()を実行したWorkerのタスク・キューに入れられる。また、タスク・オブジェクトに対してfork()を実行したWorkerが、join()を利用してタスク・オブジェクトの終了を待つ際、まだ他Workerによって処理されていない場合は当該Workerが処理し、他Workerが処理している場合はその処理の終了を待機する。各Workerは、処理中のタスクを全て処理した場合、割り当てられたタスク・キュー内のタスクを取り出してタスクの処理を開始し、当該タスク・キュー内の全てのタスクの処理が終了している場合（アイドル状態）、他のWorkerのタスク・キューからタスクを取り出し（スティール）、タスクの処理を行う。各Workerが、割り当てられたタスク・キュー以外のタスク・キュー内のタスクを処理することを、ワークスティーリングと呼ぶ。
【０００７】
以下に、ワークスティーリングを実装した並列実行プログラムの実行の例を示す。
class Fib extends ForkJoinTask {
Integer r;
Fib(int r) { this.r = r; }
protected boolean exec() {
if (r < 2) return true;
Fib f1 = new Fib(r - 1);
Fib f2 = new Fib(r - 2);
f1.fork(); f2.fork();
f2.join(); f1.join();
r = f1.r + f2.r;
return true;
}
}
void main() {
pool.invoke(new Fib(5));
}
【０００８】
このプログラムの実行処理は、次のようになる。
１．Fib f1 = new Fib(r - 1)及びFib f2 = new Fib(r - 2)によって、タスク・オブジェクト（ForkJoinTask)を生成する。
２．f1.fork()、 f2.fork()によって、タスク・オブジェクトのfork()を呼ぶ。このとき、fork()を呼び出したWorker固有のタスク・キューに、タスク・オブジェクトを入れる。その際、他のWorkerがアイドル状態の場合、キューからタスク・オブジェクトがスティールされる。
３．f2.join()、f1.join()によって、タスク・オブジェクトのjoin()を呼び、終了を待つ。このとき、タスク・オブジェクトがスティールされていない場合は、join()内でjoin()を呼び出したWorker固有のタスク・キューからタスク・オブジェクトを取り出し、タスクの処理（exec()）を実行する。タスク・オブジェクトがスティールされている場合は、タスク・オブジェクトの処理（exec()）の終了を待機する。
【０００９】
このような処理の問題点は、粒度の細かい並列性を実現しようとすると、大量のタスク・オブジェクトが生成されることである。また、タスク・オブジェクトのフィールド経由のみから指されるオブジェクトも、同様に大量に生成される。
【００１０】
すると、タスク・オブジェクトをヒープに割り当てるコスト、及びそれに伴うガベージ・コレクションのコストが増えるので、ランタイムのコストが大きくなってしまう、という問題点がある。
【００１１】
この問題点を解決するには、タスク・オブジェクトを、スタック割当てすればよい。しかし、タスク・オブジェクトは、fork()の処理内でヒープ上のキューに配置される。ヒープ上のオブジェクトは、基本的に他のスレッドから参照（エスケープ）可能なため、通常のエスケープ解析では、スタック割当て可能とは判断されない。
【００１２】
特開２００３−１５８７６号公報は、部分コンパイル環境において、オブジェクトをメソッドの呼び出しスタックに割り当てることのできるシステムと方法に関し、Java(R)において、動的にクラスをロードする際に、ロード済みのクラスの情報のみで、エスケープ解析を行う技法を開示する。
【００１３】
特開２００３−２１６４４２号公報は、処理対象である実行プログラムのソースコードに基づいて機械語コードを生成するコード変換部と、この機械語コードによる実行プログラム中のメソッドに関して、このメソッド内で作成されたオブジェクトがエスケープしていない範囲を求める最適化範囲決定部と、このオブジェクトがエスケープしていない範囲内でスカラーリプレイスメントを行うスカラーリプレイスメント実行部とを備え、エスケープ解析をする対象を限定する技法を開示する。
【００１４】
特開２００８−３３９３２号公報は、ＮＵＭＡコンピュータシステムにおいてコードを再コンパイルするための改良されたシステムに関し、エスケープ解析で、スタック割当て可能と判断したとしたオブジェクトを、ＮＵＭＡでローカルアクセスできる領域に配置する技法を開示する。
【００１５】
しかし、エスケープしたオブジェクトをスタック割当てすることは、これらの従来技術に、示唆も開示もない。
【００１６】
Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, "Escape analysis for Java", Proceeding OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM SIGPLAN Notices Homepage archive Volume 34 Issue 10, Oct. 1999(http://portal.acm.org/citation.cfm?id=320386)は、一般的なエスケープ解析で、スタック割当てを行う手法を記述する。しかし、ここに記述されている技術では、複数のWorkerにアクセスされるオブジェクトは、スタック割当てされない。
【００１７】
Erik Corry, "Optimistic stack allocation for java-like languages", Proceeding ISMM '06 Proceedings of the 5th international symposium on Memory management 2006 (http://portal.acm.org/citation.cfm?id=1133956.1133978)は、投機的にオブジェクトをスタック割当てし、フレームが終了した時点でエスケープしていれば、ヒープに移動する手法を記述する。しかし、ここに記述されている技術では、他のWorkerがアクセス可能になった時点でヒープに移動されるため、全てのタスク・オブジェクトはヒープに移動される。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００３−１５８７６号公報
【特許文献２】特開２００３−２１６４４２号公報
【特許文献３】特開２００８−３３９３２号公報
【非特許文献】
【００１９】
【非特許文献１】Doug Lea, "A Java fork/join framework", Java Grande Conference archive, Proceedings of the ACM 2000 conference on Java Grande table of contents, Pages: 36 - 43, 2000
【非特許文献２】Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, Sam Midkiff, "Escape analysis for Java", Proceeding OOPSLA '99 Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, ACM SIGPLAN Notices Homepage archive Volume 34 Issue 10, Oct. 1999
【非特許文献３】Erik Corry, "Optimistic stack allocation for java-like languages", Proceeding ISMM '06 Proceedings of the 5th international symposium on Memory management 2006
【発明の概要】
【発明が解決しようとする課題】
【００２０】
従って、この発明の目的は、Fork-Joinのフレームワークにおいて、生成されるタスク・オブジェクトに対し、fork()やjoin()の処理があった際に、スタック割当可能な場合を適切に見極める処理を提供することにある。
【課題を解決するための手段】
【００２１】
本発明によれば、Fork-Joinのフレームワークにおいて、次のような判断をする処理が実装される。
− タスク・オブジェクトをワークスティーリングのキューに入れる処理では、エスケープしないものとみなす。この処理とは例えば、fork()により行われるものである。
− キューに入れたタスク・オブジェクトの終了を待機する処理では、エスケープしないものとみなす。この処理とは例えば、join()により行われるものである。
− 上記以外でタスク・オブジェクトがエスケープする場合は、エスケープしないものとみなす。
【００２２】
さらに本発明に従う処理は、タスク・オブジェクトの実行中に、タスク・オブジェクトがエスケープしていないかどうかを解析する。そして、この解析において、エスケープしないと解析されたタスク・オブジェクトを生成したフレーム内で、タスク・オブジェクトをワークスティーリングのキューに入れる処理の後に、タスク・オブジェクトの終了を待機する処理を必ず行っている場合、そのタスク・オブジェクトを、スタックに配置する。
【００２３】
本願発明の知見によれば、タスク・オブジェクトがforkメソッドの実行中、あるいはjoinメソッドの実行中にエスケープしたとしても、joinの処理が終了した時点で、他のWorkerがタスク・オブジェクトにアクセスしないことが保障される場合があることが分かった。説明を補足すると、タスク・オブジェクトに対するjoin()の処理は、任意のWorkerがタスク・オブジェクトのタスクを終了し終わった時点で終了する。つまり、任意のWorkerがタスク・オブジェクトのタスクを処理中に、タスク・オブジェクトをエスケープしない限り、join()の処理後もエスケープしていない状態となる。すなわち、当該の条件では、従来、タスク・オブジェクトをスタック割当てできないと見なされていたところ、本願発明の知見に従うと、安全にタスク・オブジェクトをスタック割当てできると判断してよいことになる。
【発明の効果】
【００２４】
この発明によれば、従来ではタスク・オブジェクトをスタック割当てできないと見なされていた場合でも、実際には安全にタスク・オブジェクトをスタック割当てできるという場合を見出すことができ、これによって、ガベージ・コレクションや、オブジェクトをヒープ割当てするコストが減少するので、結果的に、コンピュータ・システムの処理速度を向上することができるという効果が得られる。
【図面の簡単な説明】
【００２５】
【図１】本発明を実施するためのハードウェアの一例のブロック図である。
【図２】処理環境の機能ブロックのレイヤを示す図である。
【図３】従来技術において、Workerが、タスクをforkする際、タスクをWorkerのキューに入れる様子を示す図である。
【図４】従来技術において、Workerが、新たなタスクをforkする際、タスクをキュー内の前回入れたタスクの次の場所に入れる様子を示す図である。
【図５】従来技術において、Workerが、最後の入れたタスクのjoinを呼び出した際、そのタスクがキューに残っていれば、そのタスクのexecを実行する様子を示す図である。
【図６】従来技術において、他Workerがアイドルになった場合、タスクがキューされているタスクがキューされているWorkerから、タスクをスティールする様子を示す図である。
【図７】従来技術において、Workerがjoinを呼び出したタスクがキューにない場合は、そのタスクが終了するまでWorkerが待機する示す図である。
【図８】エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックまたはヒープに割り当てる処理のフローチャートを示す図である。
【図９】ワークスティーリングのキュー内のタスク・オブジェクトを取得するメソッドを実行する処理のフローチャートを示す図である。
【図１０】従来技術と、本実施例の間の、タスク・オブジェクトの扱いの違いを説明するための図である。
【発明を実施するための形態】
【００２６】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００２７】
図１を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図１において、システム・バス１０２には、ＣＰＵ１０４と、主記憶（ＲＡＭ）１０６と、ハードディスク・ドライブ（ＨＤＤ）１０８と、キーボード１１０と、マウス１１２と、ディスプレイ１１４が接続されている。ＣＰＵ１０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(商標)4、インテル社のCore(商標) 2 DUO、Xeon(商標)、AMD社のAthlon(商標)などを使用することができる。主記憶１０６は、好適には、２ＧＢ以上の容量、より好ましくは、４ＧＢ以上の容量をもつものである。
【００２８】
ハードディスク・ドライブ１０８には、オペレーティング・システム２０２（図２）が、格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows XP(商標)、Windows(商標)2003サーバ、アップルコンピュータのMac OS(商標)などの、ＣＰＵ１０４に適合する任意のものでよい。
【００２９】
ハードディスク・ドライブ１０８にはまた、好適にはApacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存され、システムの起動時に、主記憶１０６にロードされる。
【００３０】
ハードディスク・ドライブ１０８にはさらに、Java(R)仮想マシン（ＪＶＭ）２０４（図２）を実現するためのJava(R) Runtime Environmentプログラムが保存され、システムの起動時に、主記憶１０６にロードされる。ＪＶＭ２０４は、本発明に係るヒープ・オブジェクト化の機能を実装する。
【００３１】
ハードディスク・ドライブ１０８にはさらに、アプリケーション・プログラムのバイトコード２０６（図２）が保存されている。
【００３２】
キーボード１１０及びマウス１１２は、オペレーティング・システム２０２が提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ１１４に表示されたアイコン、タスクバー、ウインドウなどのグラフィック・オブジェクトを操作するために使用される。
【００３３】
ディスプレイ１１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。ディスプレイ１１４は、アプリケーション・プログラムの挙動を必要に応じて表示するために使用される。
【００３４】
通信インターフェース１１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース１１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、あるいは処理結果を、クライアント・コンピュータ（図示しない）に返す。
【００３５】
図２は、ソフトウェアのレイヤを示す図である。図２において、最下層は、オペレーティング・システム２０２である。
【００３６】
オペレーティング・システム２０２の上では、オペレーティング・システム２０２に適合するＪＶＭ２０４が動作する。オペレーティング・システム２０２は、システムの起動時に、主記憶１０６に、スタック領域と、ヒープ領域を確保する。スタック領域では、アプリケーションにおいて、関数がコールされる度に、スタック・フレームがスタック領域に積まれ、関数がリターンすると、そのスタック・フレームが、削除される。
【００３７】
ＪＶＭ２０４上では、アプリケーション２０６のバイトコードが動作する。アプリケーション２０６が動作する間に、ＪＶＭ２０４はシステムの状態を監視し、スタックのサイズ圧縮、あるいはワークスティーリングの処理を行い、所定の基準に従い、エスケープ解析を行って、特定の条件を満たす場合に、タスク・オブジェクトを、スタックに割り当てる。
【００３８】
本発明の特徴は、エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックに割り当ててよいかどうかを判断する、判断ルーチンの基準を与える機能にある。この実施例では、そのような判断ルーチンは、ＪＶＭ２０４に含まれている。
【００３９】
本発明のエスケープ解析の判断ルーチンの基準について説明する前に、従来技術におけるFork-Joinフレームワークの振る舞いについて説明する。本発明は、これには限定されないが、科学技術計算のアプリケーション・プログラムに適用することで、特に大きい効果を奏する。
【００４０】
このとき、下記のような、ワークスティーリングを実装した並列実行プログラムを実行するものとする。これは、フィボナッチ数列の計算Fib()の例である。
class Fib extends ForkJoinTask {
Integer r;
Fib(int r) { this.r = r; }
protected boolean exec() {
if (r < 2) return true;
Fib f1 = new Fib(r - 1);
Fib f2 = new Fib(r - 2);
f1.fork(); f2.fork();
f2.join(); f1.join();
r = f1.r + f2.r;
return true;
}
}
void main() {
pool.invoke(new Fib(5));
}
【００４１】
図３は、Workerが、コードにおけるf1.fork()によって、タスクをforkする際、タスクをWorkerのキューに入れる様子を示す図である。すなわち、メイン・スレッドがFib(5)をグローバルのキューに入れる。次にWorker1が、グローバルのキューからFib(5)を取得する。次にWorker1が、Fib(5)のexec()を実行し、タスクFib(4)をWorker1のキューに入れる。
【００４２】
図４は、Workerが、コードにおけるf2.fork()によって、新たなタスクをforkする際、タスクをキュー内の前回入れたタスクの次の場所に入れる様子を示す図である。すなわち、Worker1が、Fib(5)のexec()を実行し、タスクFib(3)をWorker1のキューに入れる。Fib(3)はFib(4)の次に配置される。
【００４３】
図５は、Workerが、f2.join()によって、最後の入れたタスクのjoinを呼び出した際、そのタスクがキューに残っていれば、そのタスクのexecを実行する様子を示す図である。すなわち、Worker1がFib(3)のjoin()を実行し、タスクFib(3)の終了を待つ。その際、Fib(3)は自身のキューに残っているため、キューからFib(3)を取り出し、exec()を実行する。
【００４４】
図６は、他Workerがアイドルになった場合、タスクがキューされているタスクがキューされているWorkerから、タスクをスティールする様子を示す図である。すなわち、アイドルなWorker2が、Worker1のキューからFib(4)をスティールし、exec()を実行する。
【００４５】
図７は、Workerがjoinを呼び出したタスクがキューにない場合は、そのタスクが終了するまでWorkerが待機する示す図である。すなわち、Worker1が、Worker2にスティールされたFib(4)のjoin()、すなわちf1.join()を呼び出し、Worker2がFib(4)のexec()を終了するまで待機する。
【００４６】
このような従来技術におけるFork-Joinフレームワークの挙動から、本願発明者は、次のことを見出した。
・join()が終了した時点では、タスクはキューから削除されている。
・join()が終了した時点で、スティールしたWorkerは、タスクの参照をもっていない場合がある。このとき、exec()内でthisがエスケープしていない。
【００４７】
そこで、fork()、join()内でのエスケープは無視し、exec()内でエスケープしているかどうかを、エスケープ解析内で解析するようにした。
【００４８】
そして、以下の条件が満たされる場合、タスク・オブジェクトへのjoin()が終了した時点で、タスク・オブジェクトへの参照が、他スレッドに存在しないと言えることが分った。
− タスク・オブジェクトを生成するメソッド・フレーム内で、fork()、join()メソッドが呼ばれている。
− 上記メソッド・フレーム内で、上記タスク・オブジェクトが、fork()、join()以外でエスケープしていない。
− 上記タスク・オブジェクトのexec()メソッド内で、thisが他のスレッドにエスケープしていない。
本発明に従うＪＶＭ２０４は、これらの条件を満たしている場合、タスク・オブジェクトはエスケープしていないものとみなし、スタックに割り当てる。
【００４９】
次に、図８のフローチャートを参照して、ＪＶＭ２０４が、エスケープ解析の結果に基づき、タスク・オブジェクトを、スタックまたはヒープに割り当てる処理を説明する。
【００５０】
図８において、ステップ８０２で、ＪＶＭ２０４は、生成したタスク・オブジェクトをワークスティーリングのキューに挿入しているかどうかを判断する。そして、もしそうでないなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５１】
ステップ８０２で、ＪＶＭ２０４が、生成したタスク・オブジェクトをワークスティーリングのキューに挿入していると判断したなら、ＪＶＭ２０４はステップ８０４で、ワークスティーリングのキューに挿入後、タスクの終了を必ず待機しているかどうか判断する。そして、もしそうでないなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５２】
ステップ８０４で、ＪＶＭ２０４が、ワークスティーリングのキューに挿入後、タスクの終了を必ず待機していると判断したなら、ＪＶＭ２０４はステップ８０６で、ワークスティーリングのキューへの挿入、タスクの終了待機以外に、生成したタスク・オブジェクトがエスケープしているかどうかを判断する。そして、もしそうなら、ステップ８１０に進んで、タスクをヒープ上に生成する。
【００５３】
ステップ８０６で、ＪＶＭ２０４が、ワークスティーリングのキューへの挿入、タスクの終了待機以外に、生成したタスク・オブジェクトがエスケープしていないと判断したなら、ＪＶＭ２０４はステップ８０８で、生成したタスク・オブジェクトのタスク処理中に、そのタスク・オブジェクトがエスケープしているかどうかを判断し、もしそうなら、ステップ８１０に進んで、タスクをヒープ上に生成し、もしそうでないなら、ステップ８１２に進んで、タスクをスタック上に生成する。
【００５４】
次に図９のフローチャートを参照して、ＪＶＭ２０４が、ワークスティーリングのキュー内のタスク・オブジェクトを取得するメソッドを実行する時の挙動の例を説明する。すなわち、ステップ９０２で、ＪＶＭ２０４は、実行しようとするメソッドが、生成したタスク・オブジェクトをワークスティーリングのキューに挿入する歳にのみ使用するメソッドかどうか判断し、もしそうでないなら、ステップ９０６に進んで、取得したタスク・オブジェクトがスタック上に配置されている場合、ヒープに移動する処理を行う。
【００５５】
ステップ９０２で、ＪＶＭ２０４が、実行しようとするメソッドが、生成したタスク・オブジェクトをワークスティーリングのキューに挿入する歳にのみ使用するメソッドであると判断したなら、ステップ９０４に進んで、ワークスティーリングのキューに挿入後、タスクの終了を待機する際のみに使用するメソッドかどうかを判断する。もしそうでないなら、ステップ９０６に進んで、取得したタスク・オブジェクトがスタック上に配置されている場合、ヒープに移動する処理を行う。一方、もしそうなら、ステップ９０８で特に何もしない。
【００５６】
図１０は、図３〜図７で示した従来技術の例に、本発明を適用した結果を示す図である。すなわち、この例では、本発明に従うエスケープ解析の結果、Fib(3)とFib(4)が、ヒープでなく、スタックに割り当てられる。この例では、Worker2は、Worker1のスタックに割り当てられたオブジェクトを直接触ることになる。
【００５７】
なお、ＪＶＭではなく、図８及び図９を実装するコードをＪＩＴコンパイラにより生成することにより、本発明を実施してもよい。
【００５８】
さらに、エスケープ解析とそれに基づくスタック割当て処理は、ＪＶＭなどの仮想マシン環境でなく、オペレーティング・システムが直接実行するようにしてもよい。
【００５９】
以上、本発明を、Fork-Joinフレームワークにおけるfork()、join()の呼び出しに関連して説明してきたが、本発明はこれには限定されず、より一般的に、タスクをオブジェクトとしてあらわしており、タスクをバックグラウンドで処理する命令と、タスクの処理終了まで待機する命令とをもち、タスクの実行後は、処理系内でタスクへの参照を持たない任意の処理系に適用可能である。このような処理系の例として、これには限定されないが、例えば、並列分散プログラミング用の処理系であるX10がある。
【符号の説明】
【００６０】
１０２ システム・バス
１０４ ＣＰＵ
１０６ 主記憶
１０８ ハードディスク・ドライブ
２０２ オペレーティング・システム
２０４ ＪＶＭ
２０６ バイトコード
【特許請求の範囲】
【請求項１】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行する方法であって、
前記コンピュータが、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てするステップを実行する、
コンピュータの動作制御方法。
【請求項２】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおすステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項２に記載の方法。
【請求項４】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項２に記載の方法。
【請求項５】
前記ステップが、Java(R) VMによって実行される、請求項２に記載の方法。
【請求項６】
前記ステップが、ＪＩＴコンパイラによって生成されたコードによって実行される、請求項２に記載の方法。
【請求項７】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行するプログラムであって、
前記コンピュータに、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てするステップを実行させる、
プログラム。
【請求項８】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおすステップをさらに有する、請求項７に記載のプログラム。
【請求項９】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項８に記載のプログラム。
【請求項１０】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項８に記載のプログラム。
【請求項１１】
前記ステップが、Java(R) VMによって実行される、請求項８に記載のプログラム。
【請求項１２】
前記ステップが、ＪＩＴコンパイラによって生成されたコードによって実行される、請求項８に記載のプログラム。
【請求項１３】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行するシステムであって、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てする手段を有する、
システム。
【請求項１４】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおす手段をさらに有する、請求項１３に記載のシステム。
【請求項１５】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項１４に記載のシステム。
【請求項１６】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項１４に記載のシステム。
【請求項１７】
前記各手段が、Java(R) VMによって実行される、請求項１４に記載のシステム。
【請求項１８】
前記各手段が、ＪＩＴコンパイラによって生成されたコードを含む、請求項１４に記載のシステム。
【請求項１】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行する方法であって、
前記コンピュータが、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てするステップを実行する、
コンピュータの動作制御方法。
【請求項２】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおすステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項２に記載の方法。
【請求項４】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項２に記載の方法。
【請求項５】
前記ステップが、Java(R) VMによって実行される、請求項２に記載の方法。
【請求項６】
前記ステップが、ＪＩＴコンパイラによって生成されたコードによって実行される、請求項２に記載の方法。
【請求項７】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行するプログラムであって、
前記コンピュータに、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てするステップを実行させる、
プログラム。
【請求項８】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおすステップをさらに有する、請求項７に記載のプログラム。
【請求項９】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項８に記載のプログラム。
【請求項１０】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項８に記載のプログラム。
【請求項１１】
前記ステップが、Java(R) VMによって実行される、請求項８に記載のプログラム。
【請求項１２】
前記ステップが、ＪＩＴコンパイラによって生成されたコードによって実行される、請求項８に記載のプログラム。
【請求項１３】
コンピュータの処理によりスタック割当ての可否を判定するステップを実行するシステムであって、
(a) オブジェクトを生成しているメソッド・フレーム内で、当該オブジェクトをエスケープする可能性がある第１の命令と、前記第１の命令によるオブジェクトのエスケープ状態を解消する第２の命令が呼ばれていることと、
(b) 前記オブジェクトが第１の命令によってエスケープ状態となり、第２の命令によりエスケープ状態でなくなった場合、エスケープ状態でなくなった時点で当該オブジェクトがエスケープしたスレッド以外のスレッドにエスケープしていないことと、
(c) 前記第１の命令が第２の命令の前で呼ばれることと、及び
(d) 前記メソッド・フレーム内で、前記第１の命令内で前記オブジェクトがエスケープしているかどうかに拘らず、前記第１の命令以外でエスケープしていないことに応答して、前記オブジェクトをスタック割当てする手段を有する、
システム。
【請求項１４】
前記第２の命令によってキャンセルされない、オブジェクトのエスケープを発生させる可能性のある第３の命令があることを検出することに応答して、当該第１の命令が呼ばれた後、第２の命令が呼ばれる前に、第３の命令が呼ばれた場合に、スタックに割り当てたオブジェクトをヒープに割り当てしなおす手段をさらに有する、請求項１３に記載のシステム。
【請求項１５】
前記コンピュータが、Fork-Joinフレームワークで動作し、前記第１の命令がfork()であり、前記第２の命令がjoin()である、請求項１４に記載のシステム。
【請求項１６】
前記第３の命令は、タスク・オブジェクトをワークスティーリングのキューに挿入する際にのみ使用するメソッド及び、タスク・オブジェクトをワークスティーリングのキューに挿入する後、タスクの終了を待機する際にのみ使用するメソッド以外である、請求項１４に記載のシステム。
【請求項１７】
前記各手段が、Java(R) VMによって実行される、請求項１４に記載のシステム。
【請求項１８】
前記各手段が、ＪＩＴコンパイラによって生成されたコードを含む、請求項１４に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１５０７１６（Ｐ２０１２−１５０７１６Ａ）
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願番号】特願２０１１−９９６８（Ｐ２０１１−９９６８）
【出願日】平成２３年１月２０日（２０１１．１．２０）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【公開日】平成２４年８月９日（２０１２．８．９）
【国際特許分類】
【出願日】平成２３年１月２０日（２０１１．１．２０）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
[ Back to top ]