【誤訳訂正書】
【提出日】平成18年1月30日(2006.1.30)
【誤訳訂正１】
【訂正対象書類名】明細書
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【書類名】    明細書
【発明の名称】    スケーラブル・メモリの効率的なスレッドローカル・オブジェクト割り当て方法
【特許請求の範囲】
【請求項１】  メモリを割り当てる方法であって、
複数のメモリ空間を備えるメモリ・プールを保持するステップと、
スレッドが実行可能な状態に移行する場合に、前記スレッドにメモリ空間を割り当てるステップと、
前記スレッドがブロックされた状態に移行する場合に、前記メモリ・プールに前記メモリ空間を割り当てるステップと
を備えることを特徴とするメモリを割り当てる方法。
【請求項２】  前記スレッドに割り当てるための前記複数のメモリ空間が不足している場合、前記スレッドをブロック化された状態へ移行させるステップと、
前記スレッドに割り当てるための前記複数のメモリ空間が足りている場合、前記スレッドを実行可能状態へ移行させるステップと
をさらに備える事を特徴とする請求項１に記載の方法。
【請求項３】  実行可能状態にある複数のスレッドに割り当てるための前記複数のメモリ空間が足りているかどうかを判断するステップと、
前記複数のメモリ空間のうち少なくとも１つのサイズを変更するステップと
をさらに備える事を特徴とする請求項１に記載の方法。
【請求項４】  実行可能状態にある複数のスレッドに割り当てるための前記複数のメモリ空間が足りているかどうかを判断するステップと、
少なくとも１つの追加のメモリ空間を生成するステップと
をさらに備える事を特徴とする請求項１に記載の方法。
【請求項５】  オブジェクト指向プログラミング言語で実行される事を特徴とする、請求項１に記載の方法。
【請求項６】  前記オブジェクト指向プログラミング言語がＪａｖａ（登録商標）であることを特徴とする、請求項５に記載の方法。
【請求項７】  メモリを割り当てるための装置であって、
マイクロプロセッサと、
前記マイクロプロセッサ上で実行可能なプログラムを備え、
前記マイクロプロセッサは、複数のメモリ空間を有するメモリ・プールを保持し、
スレッドが実行可能な状態に移行する場合に、前記スレッドにメモリ空間を割り当て、
前記スレッドがブロック化状態に移行する場合に、前記メモリ・プールに前記メモリ空間を割り当てる
ことを特徴とするメモリを割り当てるための装置。
【請求項８】  前記スレッドに割り当てるための前記複数のメモリ空間が不足している場合、前記プログラムがさらに前記スレッドをブロック化された状態へ移行させ、
前記スレッドに割り当てるための前記複数のメモリ空間が足りている場合、前記プログラムがさらに前記スレッドを実行可能状態へ移行させる
事を特徴とする請求項７に記載の装置。
【請求項９】  前記プログラムがさらに、実行可能状態にある複数のスレッドに割り当てるための前記複数のメモリ空間が足りているかどうかを判断し、
前記複数のメモリ空間のうち少なくとも１つのサイズを変更する
事を特徴とする請求項７に記載の方法。
【請求項１０】  前記プログラムがさらに、実行可能状態にある複数のスレッドに割り当てるための前記複数のメモリ空間が足りているかどうかを判断し、
少なくとも１つの追加のメモリ空間を生成する
事を特徴とする請求項７に記載の装置。
【請求項１１】  前記プログラムが、オブジェクト指向プログラミング言語で実行される事を特徴とする、請求項７に記載の装置。
【請求項１２】  前記オブジェクト指向プログラミング言語がＪａｖａ（登録商標）であることを特徴とする、請求項１１に記載の装置。
【請求項１３】  複数のマイクロプロセッサを備え、
前記プログラムは、前記マイクロプロセッサの中の任意の１個のマイクロプロセッサ上で実行可能である
ことを特徴とする請求項７に記載の装置。
【請求項１４】  ネットワークサーバである事を特徴とする請求項７に記載の装置。
【請求項１５】  メモリを割り当てるための装置であって、
複数のメモリ空間を保持する手段と、
スレッドが実行可能な状態に移行する場合に、スレッドにメモリ空間を割り当てるための手段と、
スレッドがブロック化状態に移行する場合に、スレッドへのメモリ空間の割り当てを解除するための手段と
を備えることを特徴とするメモリを割り当てるための装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ・メモリの割り当て方法に関し、より詳細には、スレッドローカル・オブジェクトの割り当てのスケーラブルな方法に関する。
【０００２】
【従来の技術】
従来、並列的なオブジェクト指向プログラミング言語（例えばＪａｖａ（登録商標））のメモリ割り当て、および順次プログラミング言語（例えばＣ）の並行演算への拡張は、「共有ヒープ」割り当て方式、あるいは「スレッドローカル」割り当て方式のいずれかによって達成され、各々に長所および短所が有る。
【０００３】
共有ヒープメモリ割り当て方式は、一般にヒープと称される汎用エリアを保持し、そこからメモリが割り当てられる。ヒープは、割り当てられていないメモリを格納するために管理された領域である。名称が示すように、ヒープは複数のスレッドで共有される。ヒープは、相互排他プリミティブにより保護される。これは、或る時間帯において、アプリケーション中の１個のスレッド、若しくは１個の論理単位のみがメモリにアクセスできると言う動作である。ヒープは共有リソースであるため、安定した動作を保証するためには相互排他プリミティブが必要となる。
【０００４】
共有ヒープ割り当て方式は、特にサーバーのようなマルチプロセッサアプリケーションにおいて性能面におけるいくつかの悪影響を及ぼす。特に、マルチプロセッサの性能（スケーラビリティ）は、不必要な順次化によって低下する。順次化とは、並行演算可能な操作を順次的に実行させる要求である。更なる問題は、キャッシュミスに起因するバス・トラフィックである。キャッシュミスとは、要求されたデータがキャッシュ内に存在しないことをハードウェア・キャッシュが認識し、ハードディスク・ドライブからデータを取得しなければならない場合に発生する。これらのキャッシュミスは、アトミックなメモリ操作、および偽共有によって大概は引き起こされる。共有ヒープ割り当てに関する最後の問題は、相互排他によって要求された命令のための余剰なサイクルである。
【０００５】
先行技術におけるＪａｖａ（登録商標）環境（例えばサン・マイクロシステムズのホット・スポット・パフォーマンス・エンジン）は、相互排他メカニズムの最適化に焦点を当てている。これによって、命令の総数を低減させることより割り当て効率を改善しているが、これらはマルチプロセッサにおけるスケーラビリティの課題を無視している。このスケーラビリティの課題とは、バス・トラフィックの減少、および個々のスレッドのワーキングセット中におけるオブジェクトのコロケーションと言う課題を含む。
【０００６】
スレッドローカルのメモリ割り当て方式においては、割り当てられたメモリ空間を専用のスレッドリソースとみなす。各スレッドがそれ自身に与えられたメモリ割り当て空間、即ち「ヒープレット」を有するので、相互排他が保証される。その結果、「キャッシュの揺れ動き」は縮小される。このキャッシュの揺れ動きとは、キャッシュレジスタ中の値がマルチプロセッサ環境中の別のキャッシュ中に急速に移動する場合に生じる。さらに、「局所性」が向上する。局所性の向上とは、同一スレッドによりほぼ同時刻に作成されたオブジェクトは、ほぼ同じ位置に配置されるということである。
【０００７】
【発明が解決しようとする課題】
しかしながら、スレッドローカル方式は、高度に並行的なマルチプロセッサアプリケーション中に使用する場合に大きな困難を伴う。この方式は、非常に大きなメモリ割り当て空間を必要とする。例えば、１個のスレッド当たりに１メガバイトのメモリ空間を割り当てられた１０００個のスレッドを作成するアプリケーションは、メモリ・プール全体のために１ギガバイトの空間が必要である。メモリのフラグメント、および頻繁な「ガーベジ・コレクション」もまた重要な問題である。ガーベジ・コレクション（ＧＣ）とは、割り当て空間の生成およびサイズの変更をすることである。これはプロセッサの自動機能であり、したがって、プログラマはこれらのタスクを明示して実行させる必要が無い。通常のＧＣを実行する前には、全てのスレッドが停止した状態である事が必要である。占有されたヒープレットの数が増加するのに対応して、全てのスレッドが停止する時間が増加する。
【０００８】
【課題を解決するための手段】
或る形態によると、本発明はメモリを割り当てる方法に関し、複数のメモリ空間を備えるメモリ・プールを保持するステップと、スレッドが実行可能な状態に移行する場合に、スレッドにメモリ空間を割り当てるステップと、スレッドがブロックされた状態に移行する場合に、メモリ・プールにメモリ空間を割り当てるステップとを備える。
【０００９】
他の形態によると、本発明はメモリを割り当てるための装置に関し、マイクロプロセッサと、マイクロプロセッサ上で実行可能なプログラムを備え、このマイクロプロセッサは、複数のメモリ空間を有するメモリ・プールを保持し、スレッドが実行可能な状態に移行する場合に、スレッドにメモリ空間を割り当て、スレッドがブロック化状態に移行する場合に、メモリ・プールにメモリ空間を割り当てる。
【００１０】
他の形態によると、本発明はメモリを割り当てるための装置に関し、複数のメモリ空間を保持する手段と、スレッドが実行可能な状態に移行する場合に、スレッドにメモリ空間を割り当てるための手段と、スレッドがブロック化状態に移行する場合に、スレッドへのメモリ空間の割り当てを解除するための手段とを備える。
【００１１】
本発明は少なくとも、要求されるメモリ・プール割り当て空間の低減、メモリ・フラグメントの減少、およびガーベジ・コレクション処理の頻度の減少と言う効果を備える。これらの効果により、特にマルチプロセッサ環境中の高度に並行化された演算において、より高速で、より安定したオペレーションが可能になる。
【００１２】
【発明の実施の形態】
例示される本発明の実施形態は、添付図面を参照して記述される。図面中の類似した要素は同一の参照番号で示される。
【００１３】
多くのアプリケーションでは、どの時間帯においても、ほとんど全てのスレッドはブロックされた状態にあり、オブジェクトの割り当てが不可能である。例えば、多くのサーバー側のベンチマーク・アプリケーションにおいて、実行可能な状態にあるスレッドは、常に平均してスレッド全体の３〜８％にしか過ぎない。割り当て空間のマッチング数を保持することが可能であれば、要求される割り当て領域およびメモリのフラグメントを大幅に縮小させつつ、スレッドローカル割り当ての効果を達成し得る。
【００１４】
図１は、本発明の１つの実施例を示すフローチャート（ステップ１０）である。最初に、メモリ空間のプールはシステムによって保持される（ステップ１２）。スレッドが実行可能な状態へ移行し（ステップ１４）、そのスレッドをサポートするのに足りるメモリ空間がメモリ・プールにおいて使用可能な場合（ステップ１６）、占有可能なメモリ空間がスレッドに割り当てられる（ステップ２０）。スレッドをサポートするのに足りる空間がメモリ・プール中に無い場合、スレッドは一時的にブロック状態に移行する（ステップ１８）。十分なメモリがプールにおいて使用可能になるまで、本スレッドは停止状態のまま保持される。十分なメモリが使用可能になった際、スレッドは実行可能な状態に移行し、メモリ空間を割り当てられる。メモリ空間は永続的に各スレッドに割り当てられるわけではない。メモリ空間を割り当てられたスレッドがブロック状態に移行する場合（ステップ２２）、割り当てられたメモリ空間はメモリ・プールに返還され（ステップ２４）、実行可能な状態にある別のスレッドへ割り当てることが可能である。ブロック化状態への移行は、同期や、入出力における待機等に起因し得る。
【００１５】
図１に示される実施形態は、スレッドローカル割り当ての利点と、共有ヒープ割り当て方法のメモリ効率とを組み合わせたメモリ割り当て方法を示す。単純なスレッドローカル割り当てのように、実行される各スレッドはそれ自身の割り当て空間を保持し、オブジェクトをロック無しで割り当てる。しかしながら、割り当てられた専用メモリ空間は、永続的にスレッドに占有されるわけではない。どの実行可能スレッドも専用の割り当て空間を常に保持しているのに対し、実行可能スレッドと割り当て空間との間の関係が、スレッドのライフタイムを変更し得る。新しいオブジェクトの作成をしない状態にあるスレッドは（例：リソース上での待機）専用の割り当て空間を必要としない。これらのブロック状態にあるスレッドは、割り当てられた空間をメモリ・プールに開放し、実行可能な状態にあるスレッドの使用のために空間を提供する。
【００１６】
メモリ・プールの使用可能な空間が、実行可能な状態のスレッドへの割り当ての際に不足する場合がある。その場合は、空間が使用可能になるまで、一時的にスレッドはブロック状態に移行させられる。使用可能な空間は、実行可能な状態に無いスレッドから開放された割り当て空間によって、またはガーベジ・コレクション処理によって確保し得る。
【００１７】
図２は、本発明の実施形態中で使用され得るガーベジ・コレクション処理（ステップ３０）の例を示すフローチャートである。最初に、全ての実行可能スレッドにメモリ空間を割り当てるのに足りる空間が確保可能かどうかを判定する（ステップ３２）。空間が足りない場合、ガーベジ・コレクション処理が開始される（ステップ３４）。次に、実行可能スレッドの数およびそれぞれのスレッドに対する必要メモリ空間を決定する（ステップ３６）。その後、実行可能スレッドの要求を満たすために、必要に応じて、メモリ・プール中のヒープレットのサイズ変更および／または作成がおこなわれる（ステップ３８）。ガーベジ・コレクションのための処理は、自動的に実行されるメカニズムであり得る。本処理は、プール中の割り当て空間が不足することによってマシン・ロードがある閾値以下に低下した場合に実行される。
【００１８】
本発明は、オブジェクト指向プログラミング言語で実行される事を意図している。そのような言語として、Ｊａｖａ（登録商標）、Ｃ＋＋およびＳｍａｌｌｔａｌｋを含み得るが、それらに限定されるものではない。さらに、本発明の実施形態は、ネットワークサーバのようなマルチプロセッサ環境での使用のために説明されている。マルチプロセッサ環境４０の１つの実施形態の例が、図３に示される。本実施形態は、マイクロプロセッサ（ＣＰＵ）４２の列を備え、ＣＰＵ４２のそれぞれがメモリ４４へのアクセスを備える。３個のみのＣＰＵが図示されているが、当業者にとって公知となっている構成の範囲内で、任意の数のＣＰＵを使用し得る。さらに、本発明の実施形態は、シングルプロセッサ環境中においても、同様に効果的に使用し得る。
【００１９】
開示された本発明は、要求されるメモリ・プール割り当て空間の低減、メモリ・フラグメントの減少、およびガーベジ・コレクション処理の頻度の減少のうち、１つ以上の効果を備える。これらの効果により、特にマルチプロセッサ環境中の高度に並行化された演算において、より高速で、より安定したオペレーションが可能になる。
【００２０】
【発明の効果】
本発明は実施形態中のある特定の例に関して開示されているが、多くの変更および修正がなされ得る。したがって、本発明は、本明細書の記載に限定されるものでは無く、添付の特許請求の範囲に限定される事を意図するものである。
【図面の簡単な説明】
【図１】
本発明の１つの実施形態を示すフローチャートである。
【図２】
本発明における「ガーベジ・コレクション」方法の１つの実施形態を示すフローチャートである。
【図３】
マルチプロセッサ環境を示す図である。
【誤訳訂正２】
【訂正対象書類名】図面
【訂正対象項目名】図１
【訂正方法】変更
【訂正の内容】
【図１】
2004515838.tif 000001
【誤訳訂正３】
【訂正対象書類名】図面
【訂正対象項目名】図２
【訂正方法】変更
【訂正の内容】
【図２】
2004515838.tif 000002