(57)【特許請求の範囲】
【請求項１】
コンピュータ・システム上で実行されるプロセスにおいて前記コンピュータ・システムがスケジューラを作成するステップであって、前記スケジューラは、
前記スケジューラに割り当てられる複数の処理リソースのうちの各々の処理リソースについて対応するタスクの局所的集合を有し、前記複数の処理リソースのうち第１の処理リソースに関連付けられる第１の局所的集合を含む、複数の局所的集合と、
第１のタスクを含む少なくとも１つのタスクの汎用的集合と
を含む、ステップと、
前記コンピュータ・システムが、前記第１のタスクが複数の処理リソースのうち前記第１の処理リソース上で実行されている第２のタスクによって非ブロック化されたことを検出するステップと、
前記コンピュータ・システムが、前記非ブロック化された第１のタスクを、前記第１の局所的集合に割り当てるステップと、
前記コンピュータ・システムが、前記複数の局所的集合のうち前記第１の局所的集合が満杯であることを検出することに応答して、前記第１のタスクを前記複数の局所的集合のうち前記第１の局所的集合に割り当てる際に、前記複数の局所的集合のうち前記第１の局所的集合内の第３のタスクを汎用的集合に割り当てるステップと
を含むことを特徴とする方法。
【請求項２】
第４のタスクが前記スケジューラに割り当てられた前記複数の処理リソースのうち第２の処理リソース上で実行されている第５のタスクによって非ブロック化されたことを検出するステップと、
前記第４のタスクを、前記複数の処理リソースのうち前記第２の処理リソースに関連付けられた前記複数の局所的集合のうち第２の局所的集合に割り当てるステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第３のタスクは前記複数の局所的集合のうち前記第１の局所的集合内の最も過去に追加されたタスクであることを特徴とする請求項１の方法。
【請求項４】
前記複数の処理リソースのうち前記第１の処理リソースが利用可能となったときに、前記第１のタスクが前記複数の局所的集合のうち前記第１の局所的集合内で直近に追加されたタスクである場合に、前記第１のタスクを前記複数の処理リソースのうち前記第１の処理リソースで実行するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の処理リソースのうち第２の処理リソースが利用可能となったときに、前記第１のタスクが前記複数の局所的集合のうち前記第１の局所的集合内で最も過去に追加されたタスクである場合に、前記第１のタスクを前記複数の処理リソースのうち前記第２の処理リソースで実行するステップをさらに含む、請求項１に記載の方法。
【請求項６】
コンピュータ・システムによって実行されたとき、
前記コンピュータ・システム上で実行されているプロセス内に、スケジューラであって、待機依存実行コンテキストの第１のタスクを含む少なくとも１つのタスクの汎用的集合および複数の処理リソースのうち第１の処理リソースに関連付けられる第１の局所的集合を含む、前記スケジューラに割り当てられた複数の処理リソースの各々についての別個のタスクの局所的集合を有する、スケジューラを作成するステップと、
前記複数の処理リソースのうち前記第１の処理リソースが前記第１のタスクを非ブロック化させることに応答して、前記非ブロック化された第１のタスクを前記第１の局所的集合に割り当てるステップと、
前記複数の処理リソースのうち前記第１の処理リソースに対応する前記第１の局所的集合が満杯であることを検出することに応答して、前記非ブロック化された第１のタスクを前記第１の局所的集合から前記汎用的集合へ移動するステップと
を含む方法を前記コンピュータ・システムに実行させるコンピュータ実行可能命令を記録したことを特徴とするコンピュータ読取可能記録媒体。
【請求項７】
前記方法は、前記複数の処理リソースのうち第２の処理リソースが第２のタスクを非ブロック化させることに応答して、前記非ブロック化された第２のタスクをランナブルとさせた前記複数の処理リソースのうち前記第２の処理リソースに対応する第２の局所的集合に、前記非ブロック化された第２のタスクを割り当てるステップをさらに含むことを特徴とする請求項６に記載のコンピュータ読取可能記録媒体。
【請求項８】
前記方法は、前記スケジューラが受け取った新しいタスクを前記汎用的集合に割り当てるステップをさらに含むことを特徴とする請求項６に記載のコンピュータ読取可能記録媒体。
【請求項９】
前記方法は、前記複数の処理リソースのうち前記第１の処理リソースが利用可能となったときに、前記非ブロック化された第１のタスクが前記複数の処理リソースのうち第１の処理リソースに対応する前記第１の局所的集合内で直近に追加されたタスクである場合に、前記非ブロック化された第１のタスクを前記複数の処理リソースのうち前記第１の処理リソースで実行するステップをさらに含むことを特徴とする請求項６に記載のコンピュータ読取可能記録媒体。
【請求項１０】
前記方法は、前記複数の処理リソースのうち前記第１の処理リソースが利用可能となったときに、前記非ブロック化された第１のタスクが前記複数の処理リソースのうち前記第１の処理リソースに対応する前記第１の局所的集合内で直近に追加されたタスクではない場合に、前記複数の処理リソースのうち前記第１の処理リソースに対応する前記第１の局所的集合内に直近に追加された非ブロック化された第２のタスクを前記複数の処理リソースのうち前記第１の処理リソースで実行するステップをさらに含むことを特徴とする請求項６に記載のコンピュータ読取可能記録媒体。
【請求項１１】
前記方法は、前記複数の処理リソースのうち第２の処理リソースが利用可能となったときに、前記非ブロック化された第１のタスクが前記複数の処理リソースのうち前記第１の処理リソースに対応する前記第１の局所的集合内で最も過去に追加されたタスクである場合に、前記第１のタスクを前記複数の処理リソースのうち前記第２の処理リソースで実行するステップをさらに含むことを特徴とする請求項６に記載のコンピュータ読取可能記録媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
コンピュータ・システムにおいて実行されるプロセスには、そのコンピュータ・システムにおいて実行するためにプロセスのタスクをスケジュールするタスク・スケジューラが含まれることがある。これらのスケジューラは、プロセスのタスクをどのように実行すべきかを決定する様々なアルゴリズムで動作することができる。しかし、それらのアルゴリズムは、根底にあるコンピュータ・システムのハードウェア・トポロジを完全に利用することができていない。例えば、それらのアルゴリズムは、メモリ階層とマルチ・プロセッサを有するコンピュータ・システムにおけるメモリの位置関係から生じる効果（memory locality effects）を完全に利用できていない。その結果、スケジューラはコンピュータ・システムにおけるプロセスの実行を最適化することができない。
【発明の概要】
【０００２】
本概要は選択した概念を簡潔な形で導入するために与える。これらの概念は以下の「発明を実施するための形態」でさらに詳細に説明する。本概要は、特許請求の範囲に記載の主題の重要な特徴または本質的な特徴を特定することを意図していない。また、この概要は、特許請求の範囲に記載の主題の範囲を限定することを意図するものでもない。
【０００３】
コンピュータ・システムのプロセス内のスケジューラが、そのスケジューラに割り当てられた処理リソースごとのタスクの局所的集合（local collection of tasks）と、少なくとも１つの、タスクの汎用的集合（general collection of tasks）を含む。スケジューラは、非ブロック化となった各タスクを、そのタスクを非ブロック化にした処理リソースに対応する局所的集合に割り当てる。処理リソースが利用可能となったとき、その処理リソースは対応する局所的集合に直近に追加されたタスクを実行することを試みる。対応する局所的集合にタスクがない場合は、その利用可能な処理リソースは、汎用的集合から、または別の処理リソースの局所的集合から、タスクを実行することを試みる。
【０００４】
添付の図面は、実施形態をさらに理解させるために含めたものであり、本明細書に組み込まれ、本明細書の一部を構成する。図面は実施形態を例示するものであり、明細書の記載とともに実施形態の原理を説明する役割を果たす。他の実施形態、および、実施形態の意図した利点の多くは、後の発明を実施するための形態を参照することにより、容易に理解され、より良く理解されよう。図面の要素は、互いに対して必ずしも正しい縮尺とはなっていない。同じ参照番号は対応する同じ部分を指す。
【図面の簡単な説明】
【０００５】
【図１】ランタイム環境においてタスクの局所的集合を有するスケジューラの実施形態を示すブロック図である。
【図２】スケジューラ内で実行コンテキストを割り当てるための方法の実施形態を示す流れ図である。
【図３】実行用の実行コンテキストを選択するための方法の実施形態を示す流れ図である。
【図４】スケジューラ内で使用するためのスケジュール・グループの実施形態を示すブロック図である。
【図５Ａ】タスクの局所的集合を有するスケジューラ内の実行コンテキストを実行する実施形態を示すブロック図である。
【図５Ｂ】タスクの局所的集合を有するスケジューラ内の実行コンテキストを実行する実施形態を示すブロック図である。
【図６Ａ】タスクの局所的集合を有するスケジューラを含むランタイム環境を実装するように構成されたコンピュータ・システムの実施形態を示すブロック図である。
【図６Ｂ】タスクの局所的集合を有するスケジューラを含むランタイム環境を実装するように構成されたコンピュータ・システムの実施形態を示すブロック図である。
【発明を実施するための形態】
【０００６】
以下の「発明を実施するための形態」では、添付の図面を参照する。添付の図面は、本明細書の一部を構成し、図面においては本発明を実施できる具体的な実施形態が例として示されている。この点において、説明される図（複数可）の向きを参照しながら、「上部」、「下部」、「前部」、「後部」、および「先頭」「末尾」等の方向の用語が使用される。実施形態の構成を、幾つかの異なる向きに配置できるので、上記の方向の用語は、例示のために使用されており、決して限定ではない。他の実施形態を利用してもよく、本発明の範囲から逸脱しない構造的変更または論理的変更を加えてもよいことは理解されよう。したがって、後の詳細な説明は限定的な意味で捉えられるべきではなく、本発明の範囲は添付の特許請求の範囲によって定義される。
【０００７】
特に断らない限り、本明細書で説明した様々な例示的な実施形態の特徴を互いに組み合わせてもよいことは理解されよう。
【０００８】
図１は、ランタイム環境１０のプロセス１２内のタスク・スケジューラ２２の実施形態を示すブロック図である。スケジューラ２２は、一組の仮想プロセッサ３２（１）〜３２（Ｎ）を、対応するタスクの局所的集合４４（１）〜４４（Ｎ）とともに、含む。ここで、Ｎは、後に詳述するように、２以上の整数であり、Ｎ番目の仮想プロセッサ３２またはＮ番目の局所的集合４４を表す。
【０００９】
ランタイム環境１０は、図６Ａおよび６Ｂで示し後に詳述するコンピュータ・システム１００の実施形態１００Ａおよび１００Ｂのような、コンピュータ・システム内のオペレーションのランタイムモードを表し、そこではコンピュータ・システムが命令を実行している。コンピュータ・システムは、図６Ａに示し後に詳述するランタイム・プラットフォーム１２２のようなランタイム・プラットフォームからランタイム環境１０を生成する。
【００１０】
ランタイム環境１０は、少なくとも１つの起動されたプロセス（invoked process）１２、リソース管理層１４、および一組のハードウェア・スレッド１６（１）〜１６（Ｍ）を含む。ここで、Ｍは１以上の整数であって、Ｍ番目のハードウェア・スレッド１６を表す。ランタイム環境１０は、リソース管理層１４とハードウェア・スレッド１６（１）〜１６（Ｍ）を用いて、プロセス１２と共存する他の任意のプロセス（図示せず）からのタスクとともに、プロセス１２からのタスクを実行できるようにする。ランタイム環境１０は、リソース管理層１４と協働して、プロセス１２がコンピュータ・システムのプロセッサおよび他のリソース（例えばハードウェア・スレッド１６（１）〜１６（Ｍ））を取得できるように動作する。
【００１１】
ランタイム環境１０はスケジューラ２２を生成するスケジューラ機能を含む。一実施形態では、スケジューラ機能は、スケジューラＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）として実装される。他の実施形態では、スケジューラ機能を、他の適切なプログラミング構造を用いて実装してもよい。起動されると、スケジューラ機能はプロセス１２内にスケジューラ２２を作成し、スケジューラ２２は、１つまたは複数のハードウェア・スレッド１６（１）〜１６（Ｍ）による実行のためにプロセス１２のタスク（tasks）をスケジュールするように動作する。ランタイム環境１０は、アプリケーション開発者またはライブラリ開発者が、スケジューラ機能が提供する機能を認識している付属のツールを用いて自身のプログラム（例えば、プロセス１２）において表現する粒度の細かい並列性（concurrency）を利用してもよい。
【００１２】
プロセス１２は、１つまたは複数の実行コンテキスト（つまり、スレッド）をホストする処理リソースおよびその他のリソースの割当てを含む。プロセス１２は、コンピュータ・システム内での処理リソースおよび他のリソース（例えば、ハードウェア・スレッド１６（１）〜１６（Ｍ））へのアクセスをリソース管理層１４から取得する。その処理リソースおよび他のリソースを用いて、プロセス１２はタスクを実行させる。
【００１３】
プロセス１２は可変長のタスク内にワークを生成し、この場合、各タスクはスケジューラ２２内の実行コンテキストに関連付けられる。各タスクは、コンピュータ・システムによって実行されると一単位のワークを実行する一連の指示を含む。各実行コンテキストは、割り当てられた処理リソース上で関連するタスクを実行するスレッドを形成する。各実行コンテキストはプログラムの状態情報とマシンの状態情報を含む。実行すべきタスクがもう残っていない場合、実行コンテキストは終了することができる。タスクごとに、ランタイム環境１０および／またはプロセス１２は、実行のためにスケジュールすべきタスクをスケジューラ２２に割り当てて実行を計画するか、さもなければ、スケジューラ２２を用いずにタスクを実行させる。
【００１４】
プロセス１２を、スタック・モデルまたはインタプリタ・モデルのような任意の適切な実行モデルに基づいて、コンピュータ・システムで動作するように構成することができ、プロセス１２はアプリケーション、ライブラリ関数、またはオペレーティング・システム・サービスのような任意の適切な種類のコードを表すことができる。プロセス１２は、定義されたメモリ・アドレス空間を含む一組の割り当てられたリソースに関連付けられたプログラム状態およびマシン状態を有する。プロセス１２は、ランタイム環境１０において共存する任意のプロセスから自律してまたはほぼ自律して実行する。従って、プロセス１２は、共存するプロセスのプログラム状態を不利に（adversely）変更することはなく、共存するプロセスに割り当てた任意のリソースのマシン状態を不利に変更することもない。同様に、共存するプロセスは、プロセス１２のプログラム状態を不利に変更することはなく、プロセス１２に割り当てた任意のリソースのマシン状態を不利に変更することもない。
【００１５】
リソース管理層１４は、１つまたは複数のハードウェア・スレッド１６をプロセス１２に割り当てることにより、処理リソースをプロセス１２に割り当てる。リソース管理層１４は、図１の実施形態において、コンピュータ・システムのオペレーティング・システム（図１には図示せず）とは別に存在する。他の実施形態では、リソース管理層１４またはその機能の一部もしくは全部をオペレーティング・システムに含めてもよい。
【００１６】
ハードウェア・スレッド１６は、コンピュータ・システムの一組のプロセッサ・パッケージまたは１つもしくは複数のプロセッサ・パッケージ（例えば、図６に示し後に詳述するプロセッサ・パッケージ１０２）の実行コアに存在する。各ハードウェア・スレッド１６は、他の実行コアから独立してまたはほぼ独立して命令を実行するように構成され、マシン状態を含む。ハードウェア・スレッド１６を単一のプロセッサ・パッケージに含めてもよく、または、複数のプロセッサ・パッケージにわたって分散させてもよい。プロセッサ・パッケージ内の各実行コアは、１つまたは複数のハードウェア・スレッド１６を含んでもよい。
【００１７】
プロセス１２は、ランタイム環境１０が提供するスケジューラ機能を介して、暗示的または明示的にスケジューラ２２を作成させる。プロセス１２がコンピュータ・システム内またはプログラミング言語機能内で利用できるＡＰＩを用いる場合、スケジューラ・インスタンス２２を暗示的に作成することができる。ＡＰＩまたはプログラミング言語機能に応答して、ランタイム環境１０はデフォルトのポリシでスケジューラ２２を作成する。スケジューラ２２を明示的に作成するため、プロセス１２は、ランタイム環境１０によって提供されるスケジューラ機能を起動し、スケジューラ２２に対してポリシを指定することができる。
【００１８】
スケジューラ２２は、リソース管理層１４と対話して、プロセス１２に対して透過的にコンピュータ・システムの処理リソースと他のリソースを交渉する。リソース管理層１４は、需給、スケジューラ２２の任意のポリシに基づいて、ハードウェア・スレッド１６をスケジューラ２２に割り当てる。
【００１９】
図１に示す実施形態では、スケジューラ２２は、潜在的な（underlying）ハードウェア・スレッド１６の抽象化（abstraction）を形成する仮想プロセッサ３２を作成することによって、処理リソースを管理する。スケジューラ２２は、一組の仮想プロセッサ３２（１）〜３２（Ｎ）を含む。スケジューラ２２は、各仮想プロセッサ３２を１つのハードウェア・スレッド１６と対応させることにより、仮想プロセッサ３２をハードウェア・スレッド１６に多重化する。スケジューラ２２は、２つ以上の仮想プロセッサ３２を特定のハードウェア・スレッド１６に対応付けることができるが、各仮想プロセッサ３２にはハードウェア・スレッド１６を１つだけ対応付ける。他の実施形態では、スケジューラ２２は他の適切な方法で処理リソースを管理して、プロセス１２の命令をハードウェア・スレッド１６によって実行させる。
【００２０】
スケジューラ２２は、タスクの汎用的集合３７およびタスクの局所的集合４４（１）〜４４（Ｎ）を含み、局所的集合４４（１）〜４４（Ｎ）は各仮想プロセッサ３２（１）〜３２（Ｎ）に対応している。汎用的集合３７を、任意の適切な種類のタスクの部分集合、任意の数のタスクの部分集合および／または任意のタスクの部分集合の組合せに編成してもよい。一実施形態では、汎用的集合３７は、図４の実施形態において示し後に詳述する一組のスケジュール・グループ８０または１つもしくは複数のスケジュール・グループ８０を含むことができる。他の実施形態では、汎用的集合３７を他の適切な方法で編成してもよい。
【００２１】
スケジューラ２２内の一組の実行コンテキストには、各仮想プロセッサ３２（１）〜３２（Ｎ）が実行しているそれぞれの関連タスク３６（１）〜３６（Ｎ）に関する一組の実行コンテキスト３４（１）〜３４（Ｎ）、一組の０以上のランナブル（ｒｕｎｎａｂｌｅ）実行コンテキスト３８、および一組の０以上のブロック化（すなわち、待機依存（ｗａｉｔ−ｄｅｐｅｎｄｅｎｔ））実行コンテキスト４０が含まれる。各実行コンテキスト３４、３８、および４０は、実行コンテキスト３４、３８、および４０が実行中であるか、（例えば、非ブロック化となったこと、または、スケジューラ２２に追加されたこと、に応じて）実行可能であるか、またはブロック化であるか、を示す状態情報を含む。実行中の実行コンテキスト３４は、仮想プロセッサ３２に結合されており、現在実行中である。ランナブルである実行コンテキスト３８は関連タスク３９を含み、利用可能な仮想プロセッサ３２によって実行される準備が整っている。ブロック化という実行コンテキスト４０は、関連タスク４１を含み、データ、メッセージ、または、生成中であるかまたは別の実行コンテキスト３４、３８、もしくは４０によって将来生成されるイベントを待っている。
【００２２】
スケジューラ２２内の一組の実行コンテキストは、また、各局所的集合４４（１）〜４４（Ｎ）内の複数の組のランナブル実行コンテキスト４６（１）〜４６（Ｎ）を含む。各実行コンテキスト４６は、タスク３６の実行により非ブロック化された関連タスク４７を有し、この場合、タスク３６は、実行コンテキスト４６を含む局所的集合４４に対応する仮想プロセッサ３２上で実行されたかまたは現在実行されている。
【００２３】
仮想プロセッサ３２上で実行されている各実行コンテキスト３４は、その実行の過程で、追加タスク４２を生成することができ、それら追加タスク４２は任意の適切な方法で編成される（例えば、ワーク・キュー（図１では図示せず）に追加される）。一実施形態では、ワークを、ランタイム環境１０が提供するＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）またはプログラミング言語機能および対応するツールのいずれかを用いて生成することができる。処理リソースがスケジューラ２２に利用可能である場合は、タスクは、新たなタスクをピックアップする前に仮想プロセッサ３２上でそのタスクを実行して完了させる実行コンテキスト３４または３８に割り当てられる。仮想プロセッサ３２上で実行されている実行コンテキスト３４は、また、データ、メッセージ、または別の実行コンテキスト４０によって将来使用されるイベントを生成することによって、他の実行コンテキスト４０を非ブロック化することができる。
【００２４】
スケジューラ２２内に各タスクが実現され得る（例えば、実現タスク３６および３９）。これは実行コンテキスト３４または３８がそのタスクに付加されているかまたは将来付加されること、およびそのタスクの実行の準備ができていることを示している。実現タスクは、一般に、非ブロック化実行コンテキストとスケジュールされたエージェントとを含む。実現されていないタスクを非実現と称する。子タスクが親タスクの実行によって生成される際に非実現タスク（例えば、タスク４２）を生成することができ、非実現タスクを並列化構成子（例えば、ｐａｒａｌｌｅｌ、ｐａｒａｌｌｅｌ  ｆｏｒ、ｂｅｇｉｎ、ｆｉｎｉｓｈ）により生成することができる。後述する図４の実施形態で示すように、スケジューラ２２を、実行コンテキストを伴う論理的に独立したタスク（すなわち、実現タスク）のための同期集合（synchronized collection）（例えば、スタックおよび／またはキュー）と依存タスク（すなわち、非実現タスク）に対するワーク・スティーリング・キューのリストとともに編成することができる。
【００２５】
仮想プロセッサ３２において実行コンテキスト３４が完了し、ブロッキングが発生し、または他の中断（例えば、明示的な譲渡（yielding）または強制的なプリエンプション）が発生すると、仮想プロセッサ３２は、別の実現タスク３９または非実現タスク４２を実行するために利用可能となる。スケジューラ２２は、ランナブル実行コンテキスト３８または非実現タスク４２を検索して、任意の適切な方法で実行のために、その利用可能な仮想プロセッサ３２にアタッチする。例えば、スケジューラ２２は、実行する非実現タスク４２を探す前に先ず実行するランナブル実行コンテキスト３８を探してもよい。スケジューラ２２は、スケジューラ２２の実行コンテキスト３８がすべて実行されるまでの実行の間、利用可能な仮想プロセッサ３２に実行コンテキスト３８をアタッチし続ける。
【００２６】
局所的集合４４によって、スケジューラ２２は、ハードウェア・スレッド１６で生じうるメモリ局所性の効果を利用することができる。プロセス１２を実行する際に、スケジューラ２２は、非ブロック化されたタスク４１を伴う各待機依存実行コンテキスト４０を、タスク４１を非ブロック化させた処理リソース（例えば、仮想プロセッサ３２とハードウェア・スレッド１６の組合せ）に対応する局所的集合４４に割り当てる。関連実行コンテキスト４０を有する非ブロック化タスク４１は、局所的集合４４に追加されたことに応答して、関連実行コンテキスト４６を有するランナブル・タスク４７となる。
【００２７】
処理リソース（例えば、仮想プロセッサ３２）が利用可能となったとき、その処理リソースは、対応する局所的集合４４内の実行コンテキスト４６に関連付けられた直近に追加されたタスク４７（すなわち、その処理リソースによって非ブロック化された直近のタスク４７）を実行することを試みる。そうすることにより、スケジューラ２２は、各非ブロック化タスク４７が、タスク４７を非ブロック化した処理リソースのメモリ階層の上位に格納されたデータを利用できる可能性を高める。その結果、非ブロック化タスク４７を、かかるメモリ階層の上位に格納されたデータをまだ含んでいない別の処理リソースにおいて実行するよりも、処理リソースにおいてより効率的に実行することができる。
【００２８】
例えば、実行コンテキスト３４（１）上のタスク３６（１）が、仮想プロセッサ３２（１）を介してハードウェア・スレッド１６（１）上で実施されている間に実行コンテキスト４０を有するタスク４１を非ブロック化する場合、実行コンテキスト３４（１）はタスク４１が消費する少なくともいくつかのデータを生成する可能性が高い。実行コンテキスト３４（１）がデータを生成することによってタスク４１が非ブロック化される可能性が高いため、データがハードウェア・スレッド１６（１）のメモリ階層の上位にある（例えば、ハードウェア・スレッド１６（１）にアクセスできる１つまたは複数の上位キャッシュ内でデータがホットである）可能性が高い。この例では、スケジューラ２２が、非ブロック化タスク４１と関連実行コンテキスト４０を局所的集合４４（１）に割り当てて、非ブロック化タスク４１が（仮想プロセッサ３２（１）を介して）同一のハードウェア・スレッド１６（１）によって実行される可能性を高める。
【００２９】
一実施形態では、後でさらに詳しく説明するように、局所的集合４４をワーク・スティーリング・キューとしてそれぞれ実装することにより、処理リソースが、ランナブル実行コンテキスト４６を有するタスク４７を他の処理リソースの局所的集合４４から取得する（steal）ことができる。この実施形態では、処理リソースは、処理リソースに対応する局所的集合４４にアクセスする場合、直近に追加されたタスク４７と関連実行コンテキスト４６を取り入れる（pop）。別の処理リソースに対応する局所的集合４４にアクセスする場合は、処理リソースは、実行用に最も過去に追加されたタスク４７と関連実行コンテキスト４６を取得する。そうすることにより、スケジューラ２２は、局所的集合４４をロックすることなく、または局所的集合４４の最小限のロックで、局所的集合４４が操作されるようにできる。他の実施形態では、局所的集合４４を他種の集合として実装してもよい。
【００３０】
図２は、スケジューラ２２において待機依存実行コンテキスト４０を割り当てるための方法の実施形態を示す流れ図である。図２の方法を、図１のスケジューラ２２の実施形態を参照して説明する。
【００３１】
ブロック５２で示すように、スケジューラ２２は、待機依存実行コンテキスト４０を伴うタスク４１が非ブロック化されたかどうかを判定する。スケジューラ２２は、プロセス１２を実行させている間にこの機能を断続的に実施することができる。判定を行うために、スケジューラ２２は、データ、１つもしくは複数のメッセージ、および／または実行コンテキスト４０を非ブロック化する１つもしくは複数のイベントが、実行コンテキスト３４を実行する仮想プロセッサ３２によって生成されたことを検出する。スケジューラ２２は、また、実行コンテキスト３８を非ブロック化させた仮想プロセッサ３２を特定する。
【００３２】
ブロック５４で示すように、待機依存実行コンテキスト４０を伴うタスク４１が非ブロック化となると判定したことに応答して、スケジューラ２２は、実行コンテキスト４０を非ブロック化とさせた仮想プロセッサ３２に対応する局所的集合４４が満杯であるかどうかを判定する。スケジューラ２２は、各局所的集合４４の大きさを制限してもしなくともよい。例えば、スケジューラ２２は、各局所的集合４４内に格納された実行コンテキスト４６の数を４に制限してもよい。
【００３３】
ブロック５６で示すように、いま局所的集合４４が最大数の実行コンテキスト４６を格納している（すなわち、局所的集合４４が満杯である）場合、スケジューラ２２は、最も過去に追加されたタスク４７と関連実行コンテキスト４６を局所的集合４４から汎用的集合３７へ（例えば、一組の実行コンテキスト３８へ）移動させる。スケジューラ２２は、最も過去に追加された実行コンテキスト４６を局所的集合４４から削除し、その実行コンテキスト４６を汎用的集合３７に追加して、新たに非ブロック化となった実行コンテキスト４０のための場所を空ける。実行コンテキスト４６を局所的集合４４から汎用的集合３７へ移す（spill）とき、スケジューラ２２は、局所的集合４４をＦＩＦＯ  （ｆｉｒｓｔ−ｉｎ−ｆｉｒｓｔ  ｏｕｔ）バッファとして動作させて、局所的集合４４内の最も過去に追加された実行コンテキスト４６を汎用的集合３７に移す。
【００３４】
他の実施形態では、スケジューラ２２は、局所的集合４４が満杯である場合に非ブロック化タスク４１と関連実行コンテキスト４０を汎用的集合３７に追加してもよい。
【００３５】
汎用的集合３７に２つ以上の部分集合が含まれる実施形態では、スケジューラ２２は、実行コンテキスト４６を削除した局所的集合４４に対応する仮想プロセッサ３２に関連付けられた部分集合に、実行コンテキスト４６を追加することができる。直近にアクセスされた部分集合にランナブル実行コンテキスト３８を取得させることによって、仮想プロセッサ３２を部分集合に関連付けることができる。
【００３６】
ブロック５８に示すように、非ブロック化タスク４１のための空間を局所的集合４４内に確保した後、スケジューラ２２は、非ブロック化タスク４１と関連実行コンテキスト４０を、タスク４１を非ブロック化した仮想プロセッサ３２に対応する局所的集合４４へ割り当てる。スケジューラ２２は、タスク４１と関連実行コンテキスト４０を、タスク４１と関連実行コンテキスト４０が一組のタスク４７のうち直近に追加したものと関連実行コンテキスト４６となるように局所的集合４４へ追加する。
【００３７】
図３は、実行用の実行コンテキストを選択するための方法の実施形態を示す流れ図である。図３の方法を、図１のスケジューラ２２の実施形態を参照して説明する。
【００３８】
ブロック６２に示すように、スケジューラ２２は、仮想プロセッサ３２が利用可能であるかどうかを判定する。スケジューラ２２は、プロセス１２を実行させている間にこの機能を断続的に実施することができる。仮想プロセッサ３２上で実行されている実行コンテキスト３４が完了し、ブロッキングが発生し、または他の中断（例えば、明示的な譲渡または強制的なプリエンプション）が発生すると、仮想プロセッサ３２は、別の実行コンテキスト３８もしくは実行コンテキスト４６および／または別のタスク４２を実行できるようになる。
【００３９】
仮想プロセッサ３２が利用可能となったとスケジューラ２２が判定した場合、スケジューラ２２は、利用可能な仮想プロセッサ３２にアタッチして実行するためのランナブル実行コンテキストを探し始める。ブロック６４に示すように、スケジューラ２２は先ず、ランナブル実行コンテキスト４６を、利用可能な仮想プロセッサ３２に対応する局所的集合４４内で探す。
【００４０】
ブロック６６に示すように、ランナブル実行コンテキスト４６が局所的集合４４内に存在する場合は、スケジューラ２２は、局所的集合４４内の直近に追加された実行コンテキスト４６を、仮想プロセッサ３２によって実行させる。ランナブル実行コンテキスト４６が局所的集合４４に存在する場合、スケジューラ２２はＬＩＦＯ（ｌａｓｔ−ｉｎ−ｆｉｒｓｔ−ｏｕｔ)バッファとして局所的集合４４を動作させて、直近に追加された実行コンテキスト４６を実行のために除去する。ランナブル実行コンテキスト４６は、局所的集合４４に直近に追加された実行コンテキスト４６であり、仮想プロセッサ３２上で実行されている実行コンテキスト３４によって非ブロック化されたものである。その結果、ランナブル実行コンテキスト４６が、仮想プロセッサ３２に対応するハードウェア・スレッド１６にアクセス可能なメモリ階層内に、待機依存に関するデータを有する可能性が最も高い。
【００４１】
ブロック６８に示すように、ランナブル実行コンテキスト４６が局所的集合４４に存在しない場合は、スケジューラ２２は、汎用的集合３７内でランナブル実行コンテキスト３８を探すことを試みる。
【００４２】
汎用的集合３７が２つ以上の部分集合を含む実施形態においては、スケジューラ２２は、利用可能な仮想プロセッサ３２が直近にランナブル実行コンテキスト３８を取得した部分集合内でランナブル実行コンテキスト３８を探すことを試みることができる。
【００４３】
ブロック７０に示すように、ランナブル実行コンテキスト３８が汎用的集合３７に存在する場合、スケジューラ２２によって、汎用的集合３７からランナブル実行コンテキスト３８を仮想プロセッサ３２によって実行させる。
【００４４】
ブロック７２に示すように、ランナブル実行コンテキスト３８が汎用的集合３７に存在しない場合は、スケジューラ２２は、スケジューラ２２の別の仮想プロセッサ３２に対応する局所的集合４４内でランナブル実行コンテキスト４６を探すことを試みる。一実施形態では、スケジューラ２２は、ランナブル実行コンテキスト４６が見つかるまで、ラウンド・ロビン方式で他の仮想プロセッサ３２に対応する局所的集合４４にアクセスする。他の実施形態では、スケジューラ２２は、他の適切な順序で他の仮想プロセッサ３２に対応する局所的集合４４にアクセスする。
【００４５】
ブロック７４に示すように、ランナブル実行コンテキスト４６がスケジューラ２２の別の仮想プロセッサ３２の局所的集合に存在する場合、スケジューラ２２は、他の仮想プロセッサ３２の局所的集合４４内の最も過去に追加された実行コンテキスト４６を、利用可能な仮想プロセッサ３２によって実行させる。ランナブル実行コンテキスト４６が別の局所的集合４４において見つかった場合、スケジューラ２２は、他の局所的集合４４をＦＩＦＯバッファとして動作させて、その最も過去に追加された実行コンテキスト４６を実行のために除去する。その結果、スケジューラ２２は局所的集合４４内の最も過去に追加された実行コンテキスト４６を取得し、スケジューラ２２の局所的集合４４内の実行コンテキスト４６に対する公正さと前進（ｆａｉｒｎｅｓｓ  ａｎｄ  ｆｏｒｗａｒｄ  ｐｒｏｇｒｅｓｓ）のための機構を提供する。さらに、スケジューラ２２は、実行のための最も過去に追加された実行コンテキスト４６を取り入れることによって、他の仮想プロセッサ３２上で実行されることから生ずる可能性が最も高い実行コンテキスト４６での割り込みを最小化する。
【００４６】
ブロック７６に示すように、ランナブル実行コンテキスト４６がスケジューラ２２の他の仮想プロセッサ３２の何れの局所集合４４にも存在しない場合は、スケジューラ２２は、他所にあるランナブル実行コンテキストを探すことができる。例えば、汎用的集合３７が２つ以上の部分集合を含む実施形態においては、スケジューラ２２は、汎用的集合３７の他の部分集合をラウンド・ロビン方式で検索することにより、ランナブル実行コンテキスト３８を探すことを試みることができる。別の例として、スケジューラ２２は、汎用的集合３７の１つまたは複数の部分集合の１つまたは複数のワーク・スティーリング・キュー（図示せず）を探して、実行可能でありうる非実現タスク４２を発見することができる。ランナブル実行コンテキストまたは他の実行可能タスク４２が見つかると、スケジューラ２２はランナブル実行コンテキストまたは他の実行可能タスク４２を、利用可能な仮想プロセッサ３２によって実行させる。
【００４７】
次に、図４を参照して汎用的集合３７の部分集合の一実施形態を説明する。図４は、ランタイム環境１０によってスケジューラ２２内で使用するためのスケジュール・グループ８０（１）〜８０（Ｐ）として構成された部分集合の実施形態を示すブロック図である。
【００４８】
プロセス１２は、関連する実行コンテキストまたはタスクのグルーピングを各スケジュール・グループ８０が含むように、および、各スケジュール・グループ８０が、ワーク、公正さ、および／または前進の局所性に対する構造を提供するために使用されるように、タスクをスケジュール・グループ８０（１）〜８０（Ｐ）にグループ分けすることができる。論理的に関連するワーク（例えば、共通のルート・タスクの子孫であるタスクの集合）、ハードウェア・トポロジ（例えば、ＮＵＭＡ（ｎｏｎ−ｕｎｉｆｏｒｍ  ｍｅｍｏｒｙ  ａｒｃｈｉｔｅｃｔｕｒｅ）、またはそれらの組合せに起因してグルーピングを行ってもよい。スケジュール・グループ８０により、スケジューラ２２は、拡張性、局所性、および公正を改善することができる。
【００４９】
各スケジュール・グループ８０は、ランナブル集合８２、ワーク・キュー８４、および一組の１つ以上のワーク・スティーリング・キュー８６を含む。各ランナブル集合８２はランナブル実行コンテキスト３８のリストを含む。スケジューラ２２は、新しいランナブル実行コンテキストがプロセス１２によってスケジューラ２２に提示されるとき、または、上述したようにランナブル実行コンテキスト４６が局所的集合４４から汎用的集合３７への移動したとき、実行コンテキストをランナブル集合８２に追加する。ワーク・キュー８４は、矢印８８で示すようにワーク・スティーリング・キュー８６のリストを含み、ワーク・スティーリング・キュー８６からのタスク４２を実行している実行コンテキスト３４を追跡する。各ワーク・スティーリング・キュー８６は１つまたは複数の非実現タスク４２を含む。
【００５０】
次に、図５Ａ〜５Ｂの例を参照して、図１の実施形態におけるスケジュール・グループ８０の使用を説明する。図５Ａ〜５Ｂは、局所的集合４４を有するスケジューラ２２内の実行コンテキストを実行する実施形態を示すブロック図である。
【００５１】
図５Ａの例では、矢印９０（１）および９０（２）がそれぞれ示すように、仮想プロセッサの３２（１）と３２（２）は、現在、スケジュール・グループ８０（１）からの実行コンテキスト３４（１）と３４（２）をそれぞれ実行している。スケジュール・グループ８０（１）は、箱９２に示すように、１０個の待機依存実行コンテキスト４０（１）〜４０（１０）、すなわち、コンテキストＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｖ、Ｗ、Ｘ、Ｙ、およびＺを含む。
【００５２】
実行コンテキスト３４（１）は、５個の実行コンテキスト４０（１）〜４０（５）、すなわち、コンテキストＡ、Ｂ、Ｃ、Ｄ、およびＥを、データ、１つもしくは複数のメッセージ、またはブロック化実行コンテキスト４０（１）〜４０（５）に対する１つもしくは複数のイベントを生成する関数を実施することによって、非ブロック化する。関数Ａ．ＰＲＯＤＵＣＥ（）はブロック化実行コンテキストＡに対するデータまたはメッセージを生成し、Ｂ．ＰＲＯＤＵＣＥ（）はブロック化実行コンテキストＢに対するデータまたはメッセージを生成する、等である。
【００５３】
同様に、実行コンテキスト３４（２）は、５個の実行コンテキスト４０（６）〜４０（１０）、すなわち、コンテキストＶ、Ｗ、Ｘ、Ｙ、およびＺを、ブロック化実行コンテキスト４０（６）〜４０（１０）に対するデータまたはメッセージを生成する関数を実行することにより非ブロック化する。関数Ｖ．ＰＲＯＤＵＣＥ（）はブロック化実行コンテキストＶに対するデータまたはメッセージを生成し、Ｗ．ＰＲＯＤＵＣＥ（）はブロック化実行コンテキストＷに対するデータまたはメッセージを生成する、等である。
【００５４】
図２を参照して上述したように、スケジューラは、仮想プロセッサ３２（１）によって非ブロック化された各実行コンテキスト４０（１）〜４０（５）を、局所的集合４４（１）上および一組のランナブル実行コンテキスト４６（１）内に、図５Ｂに示すように非ブロック化の順で追加する。同様に、スケジューラは、仮想プロセッサ３２（２）によって非ブロック化された各実行コンテキスト４０（６）〜４０（１０）を、局所的集合４４（２）上および一組のランナブル実行コンテキスト４６（２）内に、非ブロック化の順でプッシュする。
【００５５】
図５Ｂの例では、局所的集合４４（１）および４４（２）の各々は、４個までの実行コンテキスト４６を格納するように構成されている。局所的集合４４に４個の実行コンテキスト４６が既に存在して、５個目の実行コンテキスト４０が非ブロック化されると、スケジューラ２２は、最も過去に追加された実行コンテキスト４６をスケジュール・グループ８０（１）のランナブル集合８２（１）に移す。図５Ｂの例では、スケジューラ２２は、矢印９４で示すように実行コンテキストＡを局所的集合４４（１）からランナブル集合８２（１）に移して、実行コンテキストＥを局所的集合４４（１）に追加できるようにする。同様に、スケジューラ２２は、矢印９６で示すように実行コンテキストＶを局所的集合４４（２）からランナブル集合８２（１）に移して、実行コンテキストＺを局所的集合４４（２）に追加できるようにする。
【００５６】
矢印９８は、時刻ｔ１が時刻ｔ２より前に発生（すなわち、ｔ１＜ｔ２）する場合に、実行コンテキスト４６（１）および４６（２）が夫々の局所的集合４４（１）および４４（２）に追加された順番を示す。さらに、矢印９９は、実行コンテキスト４６（１）および４６（２）に対応するホット・データが、各仮想プロセッサ３２（１）および３２（２）に対応するハードウェア・スレッド１６（１）および１６（２）のメモリ階層にどのように存在するかの尤度スペクトルを示す。
【００５７】
仮想プロセッサ３２（１）および３２（２）が利用可能となると、仮想プロセッサ３２（１）および３２（２）は、先ず、図３を参照して上述したように、各ランナブル実行コンテキスト４６（１）および４６（２）を各局所的集合４４（１）および４４（２）内で探すことを試みる。図５Ｂの例では、仮想プロセッサ３２（１）は実行コンテキストＥ（すなわち、直近に追加された実行コンテキスト４６（１））を移動（remove）して実行し、仮想プロセッサ３２（２）は実行コンテキストＺ（すなわち、直近に追加された実行コンテキスト４６（２））を移動して実行する。矢印９９により示すように、実行コンテキストＥおよびＺが、各ハードウェア・スレッド１６（１）および１６（２）の各メモリ階層中に最もホットなデータを有する可能性が最も高い。例えば、上記の実行コンテキスト３４、４０、４６が大規模な数値行列に対して動作する場合、実行コンテキストＥおよびＺに関連付けられた大量の行列データが、各ハードウェア・スレッド１６（１）および１６（２）にアクセス可能な各メモリ階層の上位にある（例えば、各ハードウェア・スレッド１６（１）および１６（２）にアクセス可能な各キャッシュにおいて非常にホットである）可能性が高い。
【００５８】
最終的に、局所的集合４４（１）および４４（２）内のランナブル実行コンテキスト４６（１）および４６（２）は、仮想プロセッサ３２（１）、３２（２）によって、および／または、図３を参照して上述したように実行コンテキスト４６（１）および／または４６（２）を局所的集合４４（１）および／または４４（２）から取得する他の仮想プロセッサ３２によって、実行される。
【００５９】
利用可能な仮想プロセッサ３２が対応する局所的集合４４内でランナブル実行コンテキスト４６を探すことができないとき、仮想プロセッサ３２は、ランナブル実行コンテキストが見つかるまで次の順序でランナブル実行コンテキストを探すことを試みる。仮想プロセッサ３２は、ランナブル実行コンテキストを、対応するスケジュール・グループ８０内のランナブル集合８２内で探し、次に他の仮想プロセッサ３２の局所的集合４４を介してラウンド・ロビンし、次に残りのスケジュール・グループ８０内のランナブル集合８２を介してラウンド・ロビンする。
【００６０】
ランナブル実行コンテキストがスケジューラ２２内で見つからなかった場合は、仮想プロセッサ３２は非実現タスク４２をワーク・スティーリング・キュー８６から取得（steal）することを試みる。従って、スケジューラ２２は、対応する局所的集合４４、対応するスケジュール・グループ８０、他の局所的集合４４、および残りのスケジュール・グループ８０内でランナブル実行コンテキストを見つけられなかった後にのみ、汎用化されたスティール（ｇｅｎｅｒａｌｉｚｅｄ  ｓｔｅａｌ）を試みる。
【００６１】
図５Ａ〜５Ｂの例では、局所的集合４４（３）（図示せず）または対応するスケジュール・グループ８０（２）のランナブル集合８２（２）内でランナブル実行コンテキストを見つけられなかった利用可能な仮想プロセッサ３２（３）（図５Ａ〜５Ｂには図示せず）は、実行コンテキストＢ（すなわち、最も過去に追加された実行コンテキスト４６（１））を局所的集合４４（１）から取得するか、または、実行コンテキストＷ（すなわち、最も過去に追加された実行コンテキスト４６（２））を局所的集合４４（２）から取得することができる。局所的集合４４（１）および４４（２）ならびに残りの局所的集合４４が空であった場合は、仮想プロセッサ３２（３）は実行コンテキストＶを対応するスケジュール・グループ８０（１）のランナブル集合８２（１）から取得することができる。
【００６２】
図６Ａ〜６Ｂは、それぞれ、局所的集合４４（１）〜４４（Ｎ）を有するスケジューラ２２を含むランタイム環境１０を実装するように構成されたコンピュータ・システム１００の実施形態１００Ａと実施形態１００Ｂを示すブロック図である。
【００６３】
図６Ａに示すように、コンピュータ・システム１００Ａは、１つまたは複数のプロセッサ・パッケージ１０２、メモリ・システム１０４、１つ以上の入出力装置１０６、１つ以上の表示装置１０８、１つ以上の周辺装置１１０、および１つ以上のネットワーク装置１１２を備える。プロセッサ・パッケージ１０２、メモリ・システム１０４、入出力装置１０６、表示装置１０８、周辺装置１１０、およびネットワーク装置１１２は、任意の適切な種類、数、および構成のコントローラ、バス、インタフェース、および／または他の有線接続もしくは無線接続を備える一組の相互接続１１４を用いて通信する。
【００６４】
コンピュータ・システム１００Ａは、汎用目的または特殊目的向けに構成された任意の適切な処理装置を表す。コンピュータ・システム１００Ａの例には、サーバ、パーソナル・コンピュータ、ラップトップ・コンピュータ、タブレット・コンピュータ、ＰＤＡ（ｐｅｒｓｏｎａｌ  ｄｉｇｉｔａｌ  ａｓｓｉｓｔａｎｔ）、携帯電話、およびオーディオ／ビデオ装置が含まれる。コンピュータ・システム１００Ａの構成要素（すなわち、プロセッサ・パッケージ１０２、メモリ・システム１０４、入出力装置１０６、表示装置１０８、周辺装置１１０、ネットワーク装置１１２、および相互接続１１４）を、共通筐体（図示せず）に、または任意の適切な数の別個の筐体（図示せず）に含めてもよい。
【００６５】
プロセッサ・パッケージ１０２はハードウェア・スレッド１６（１）〜１６（Ｍ）を含む。プロセッサ・パッケージ１０２内の各ハードウェア・スレッド１６は、メモリ・システム１０４に格納された命令にアクセスし、その命令を実行するように構成される。その命令には、ＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ  ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）またはファームウェア（図示せず）、ＯＳ（ｏｐｅｒａｔｉｎｇ  ｓｙｓｔｅｍ）１２０、ランタイム・プラットフォーム１２２、アプリケーション１２４、およびリソース管理層１４（図１にも図示されている）を含めてもよい。各ハードウェア・スレッド１６は、入出力装置１０６、表示装置１０８、周辺装置１１０、および／またはネットワーク装置１１２から受け取った情報と関連して、またはその情報に応答して、命令を実行することができる。
【００６６】
コンピュータ・システム１００ＡはＯＳ１２０をブートして実行する。ＯＳ１２０は、コンピュータ・システム１００Ａの構成要素を管理しアプリケーション１２４がその構成要素にアクセスしてその構成要素を使用できるようにする一組の関数を提供するための、ハードウェア・スレッド１６によって実行可能な命令を含む。一実施形態では、ＯＳ１２０はＷｉｎｄｏｗｓ（登録商標）オペレーティング・システムである。他の実施形態では、ＯＳ１２０は、コンピュータ・システム１００Ａとの使用に適した別のオペレーティング・システムである。
【００６７】
リソース管理層１４は、図１を参照して上述したように、ハードウェア・スレッド１６を含むコンピュータ・システム１００Ａのリソースを割り当てるための、ＯＳ１２０と関連して実行可能な命令を含む。リソース管理層１４を、１つまたは複数のアプリケーション１２４に利用可能な関数ライブラリとして、またはＯＳ１２０の統合部分として、コンピュータ・システム１００Ａに含めてもよい。
【００６８】
ランタイム・プラットフォーム１２２は、ランタイム環境１０を生成しランタイム関数をアプリケーション１２４に提供するための、ＯＳ１２０とリソース管理層１４と関連して実行可能な命令を含む。これらのランタイム機能には、図１を参照して上でさらに詳述したスケジューラ関数が含まれる。ランタイム関数を、アプリケーション１２４の一部として、１つまたは複数のアプリケーション１２４に利用できる関数ライブラリとして、またはＯＳ１２０および／またはリソース管理層１４の統合部分として、コンピュータ・システム１００Ａに含めてもよい。
【００６９】
各アプリケーション１２４は、所望の操作をコンピュータ・システム１００Ａによって実行させるための、ＯＳ１２０、リソース管理層１４、および／またはランタイム・プラットフォーム１２２と関連して実行可能な命令を含む。各アプリケーション１２４は、上述のプロセス１２のような、ランタイム・プラットフォーム１２２によって提供された局所的集合４４（１）〜４４（Ｎ）を使用するスケジューラ２２で実行可能な１つまたは複数のプロセスを表す。
【００７０】
メモリ・システム１０４は、命令およびデータを格納するように構成された任意の適切な種類、数、および構成の揮発性記憶装置または不揮発性記憶装置を備える。メモリ・システム１０４の記憶装置は、ＯＳ１２０、リソース管理層１４、ランタイム・プラットフォーム１２２、およびアプリケーション１２４を含むコンピュータ実行可能命令を記憶するコンピュータ読取可能記憶媒体を表す。この命令は、本明細書で説明したＯＳ１２０、リソース管理層１４、ランタイム・プラットフォーム１２２、およびアプリケーション１２４の関数とメソッドを実行するためにコンピュータ・システムにより実行可能である。メモリ・システム１０４内の記憶装置の例には、ハード・ディスク・ドライブ、ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、ＲＯＭ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）、フラッシュ・メモリ・ドライブおよびカード、ならびに磁気ディスクおよび光ディスクが含まれる。
【００７１】
メモリ・システム１０４は、プロセッサ・パッケージ１０２、入出力装置１０６、表示装置１０８、周辺装置１１０、およびネットワーク装置１１２から受け取った命令とデータを格納する。メモリ・システム１０４は、格納された命令とデータを、プロセッサ・パッケージ１０２、入出力装置１０６、表示装置１０８、周辺装置１１０、およびネットワーク装置１１２に提供する。
【００７２】
入出力装置１０６は、命令またはデータをユーザからコンピュータ・システム１００Ａに入力し命令またはデータをコンピュータ・システム１００Ａからユーザに出力するように構成された、任意の適切な種類、数、および構成の入出力装置を含む。入出力装置１０６の例には、キーボード、マウス、タッチパッド、タッチスクリーン、ボタン、ダイアル、ノブ、およびスイッチが含まれる。
【００７３】
表示装置１０８は、テキスト情報および／またはグラフィカル情報をコンピュータ・システム１００Ａのユーザへ出力するように構成された、任意の適切な種類、数、および構成の表示装置を含む。表示装置１０８の例には、モニタ、ディスプレイ・スクリーン、およびプロジェクタが含まれる。
【００７４】
周辺装置１１０は、汎用的なまたは固有な処理関数を実行するためのコンピュータ・システム１００Ａ内の１つまたは複数の他のコンポーネントと動作するように構成された任意の適切な種類、数、および構成の周辺装置を含む。
【００７５】
ネットワーク装置１１２は、コンピュータ・システム１００Ａが１つまたは複数のネットワーク（図示せず）にわたって通信できるように構成された、任意の適切な種類、数、および構成のネットワーク装置を含む。ネットワーク装置１１２は、コンピュータ・システム１００Ａによって情報をネットワークに送信しまたはコンピュータ・システム１００Ａによって情報をネットワークから受信できるようにするための任意の適切なネットワーキング・プロトコルおよび／または構成に従って動作することができる。
【００７６】
図６Ｂは、コンピュータ・システム１００の実施形態１００Ｂを示すブロック図である。コンピュータ・システム１００Ｂは、また、少なくともプロセッサ・パッケージ１０２とメモリ・システム１０４を備える。プロセッサ・パッケージ１０２はプロセッサ・パッケージ１０２（１）〜１０２（Ｒ）を含み、メモリ・システム１０４はメモリ装置１２８（１）〜１２８（Ｒ）を含む。ここで、Ｒは２以上の整数であり、Ｒ番目のプロセッサ・パッケージ１０２とＲ番目のメモリ装置１２８を表す。ＯＳ１２０、ランタイム・プラットフォーム１２２、アプリケーション１２４、およびリソース管理層１４を、夫々、メモリ装置１２８（１）〜１２８（Ｒ）のうち任意の適切なメモリ装置に格納することができる。
【００７７】
図６Ｂの実施形態では、各プロセッサ・パッケージ１０２（１）〜１０２（Ｒ）および各メモリ装置１２８（１）〜１２８（Ｒ）はノードを形成する。それらのノードは、任意の適切な種類、数、および／または組合せのノード相互接続１３０で相互接続される。
【００７８】
各プロセッサ・パッケージ１０２は一組のハードウェア・スレッド１６（１）〜１６（４）を含む。ここで、各ハードウェア・スレッドはＬ１（レベル１）キャッシュ（図示せず）を含む。各プロセッサ・パッケージ１０２は、また、各ハードウェア・スレッド１６（１）（１）〜１６（１）（４）に対応する一組のＬ２（レベル２）キャッシュ１３２（１）〜１３２（４）を含む。各プロセッサ・パッケージ１０２は、さらに、一組のハードウェア・スレッド１６（１）〜１６（４）が利用できるＬ３（レベル３）キャッシュ、システム・リソース・インタフェース１３６、クロスバー・スイッチ１３８、メモリ・コントローラ１４０、およびノード・インターフェース１４２を含む。システム・リソース・インタフェース１３６はノード・リソース（図示せず）に対するアクセスを提供する。クロスバー・スイッチ１３８は、システム・リソース・インタフェース１３６をメモリ・コントローラ１４０とノード・インターフェース１４２とに相互接続する。メモリ・コントローラ１４０はメモリ装置１２８に接続する。ノード・インターフェース１４２は１つまたは複数のノード相互接続１３０に接続する。
【００７９】
図１〜５Ｂで上述した実施形態を参照すると、スケジューラ２２は、局所的集合４４を用いてコンピュータ・システム１００Ｂ内のメモリの位置関係から生じる効果を利用することを試みることができる。例えば、仮想プロセッサ３２（１）を介してハードウェア・スレッド１６（１）（１）上の実行コンテキスト３４で実行されているタスク３６が実行コンテキスト４０を有するタスク４１を非ブロック化するとき、タスク４１が消費するであろう少なくとも幾つかのデータは、プロセッサ・パッケージ１０２（１）のＬ１キャッシュ（図示せず）、Ｌ２キャッシュ１３２（１）（１）、および／またはＬ３キャッシュ１３４（１）内にある可能性が高い。非ブロック化タスク４１を局所的集合４４（１）に割り当てることにより、スケジューラ２２は、タスク４１が仮想プロセッサ３２（１）を介してハードウェア・スレッド１６（１）（１）によって実行され、タスク４１がＬ１キャッシュ（図示せず）、Ｌ２キャッシュ１３２（１）（１）、および／またはＬ３キャッシュ１３４（１）内のホット・データを利用する可能性を高める。
【００８０】
上述したスケジューラ内の局所的集合の利用により、待機依存実行コンテキストの実行を重み付けする能力をスケジューラに提供し、待機依存実行コンテキスト間のメモリの位置関係から生じる効果を最大化することができる。その結果、スケジューラは、待機依存実行コンテキストが同一のハードウェア・リソース上で実行される可能性を高めることができる。
【００８１】
さらに、精選されたワーク・スティーリング概念を上述の実施形態に含めることによって、スケジューラは実行コンテキスト間の公正さと前進を保存することができる。
【００８２】
局所的集合は、また、実行するための実行コンテキストを探している処理リソース間の衝突を削減することができる。その結果、スケジューラを、多数の処理リソースを有するコンピュータ・システムに拡張することもできる。
【００８３】
本明細書では特定の実施形態を例示および説明したが、図示および説明したその特定の実施形態を、本発明の範囲から逸脱しない様々な代替的なおよび／または均等な実装形態で置き換えてもよいことは当業者には理解されよう。本出願は、本明細書で論じた特定の実施形態に関する任意の適合化または変形を網羅しようとするものである。従って、本発明は特許請求の範囲およびその均等物によってのみ限定されることが意図されている。
【図１】
0005643190.tif 000002
【図２】
0005643190.tif 000003
【図３】
0005643190.tif 000004
【図４】
0005643190.tif 000005
【図５Ａ】
0005643190.tif 000006
【図５Ｂ】
0005643190.tif 000007
【図６Ａ】
0005643190.tif 000008
【図６Ｂ】
0005643190.tif 000009