(57)【要約】【課題】OS独立な「シュレッド」をオペレーティング・システムの介入なしにスケジューリングするための方法、装置およびシステムの諸実施形態。【解決手段】少なくとも一つの実施形態については、シュレッドは、オペレーティング・システムではなくスケジューラ・ルーチンによって実行のためにスケジューリングされる。スケジューラ・ルーチンは、有効にされた各シーケンサー上で走りうる。スケジューラは、待ち行列システムからシュレッド記述子を取得しうる。次いでスケジューラに関連付けられたシーケンサーが記述子によって記述されるシュレッドを実行しうる。その他の実施形態も記載され、請求される。【選択図】図５
2011076639.tif 000002
【特許請求の範囲】
【請求項１】
オペレーティング・システムを有するコンピューティング・システムでの同時並行しているスレッドのユーザーレベルのスケジューリングのための方法であって：
ユーザー生成されたスレッド命令を実行する段階であって、スレッド制御命令を生成するライブラリ関数を呼び出すことをさらに含む段階と；
前記ユーザー生成されたスレッド命令に応じて、スレッドを記述する作業記述子を生成する段階と；
前記作業記述子を待ち行列システム内に記憶させる段階と；
前記スレッドの、オペレーティング・システムに不可視なシーケンサー上での実行をスケジューリングする段階と、
ユーザーレベルの同時並行マルチスレッド利用を実行するよう前記オペレーティング・システムに不可視なシーケンサーを初期化する段階であって、ユーザーレベルの分散されたスケジューラの、前記オペレーティング・システムに不可視なシーケンサー上での実行をトリガーする段階を含む段階、
とを有する方法。
【請求項２】
前記待ち行列システムが、第一のシーケンサー型に関連付けられた第一の待ち行列と、第二のシーケンサー型に関連付けられた第二の待ち行列とを含む、
請求項１記載の方法。
【請求項３】
前記第一および第二のシーケンサー型が、コンピューティング上の少なくとも一つの基準に関して非対称的である、
請求項２記載の方法。
【請求項４】
前記コンピューティング上の基準が機能上の基準である、
請求項３記載の方法。
【請求項５】
前記コンピューティング上の基準が電力消費基準である、
請求項３記載の方法。
【請求項６】
前記機能上の基準が、リング0動作を実行する能力である、
請求項４記載の方法。
【請求項７】
前記記憶させる段階が、前記作業記述子を、ユーザーが提供したヒントに基づいて前記第一の待ち行列に記憶させることをさらに含む；
請求項２記載の方法。
【請求項８】
前記ユーザー生成されたスレッド命令が、シュレッド生成命令である、
請求項１記載の方法。
【請求項９】
前記ユーザー生成されたスレッド命令が、シュレッド同期命令である、
請求項１記載の方法。
【請求項１０】
前記ユーザー生成されたスレッド命令が、業界標準準拠のアプリケーション・プログラマ・インターフェースの一部である、
請求項１記載の方法。
【請求項１１】
オペレーティング・システムを有する装置であって、
分散されたオペレーティング・システム独立なスケジューラ・ルーチンの第一の部分を含む第一のスレッド実行ユニットと；
分散されたオペレーティング・システム独立なスケジューラ・ルーチンの第二の部分を含む第二のスレッド実行ユニットとを有する装置であって；
前記第一および第二のスレッド実行ユニットが同時並行のマルチスレッドを利用した実行を提供するよう構成されており；
前記第一および第二の部分がさらに、スレッドを記述する作業記述子を求めて競るために作業待ち行列に問い合わせするよう構成されており；
前記分散されたオペレーティング・システムに不可視なスケジューラ・ルーチンの前記第二の部分が、前記競りに基づいて、オペレーティング・システムには不可視に、前記スレッドを、前記スレッド実行ユニットのうちの選択されたものでの実行のためにスケジューリングする、装置。
【請求項１２】
前記スレッド実行ユニットの少なくとも一つはオペレーティング・システムに可視であり、前記スレッド実行ユニットの少なくとも別の一つはオペレーティング・システムに可視ではない、
請求項１１記載の装置。
【請求項１３】
当該装置が単一コアのプロセッサであり；
前記第一および第二の実行ユニットが論理的なプロセッサである、
請求項１１記載の装置。
【請求項１４】
当該装置がマルチコアのプロセッサであり；
前記第一および第二の実行ユニットがプロセッサ・コアである、
請求項１１記載の装置。
【請求項１５】
前記実行ユニットが機能的に対称的である、
請求項１１記載の装置。
【請求項１６】
前記待ち行列システムが、前記実行ユニットの全部に適用可能な作業記述子を保持するための単一の待ち行列を含む、
請求項１５記載の装置。
【請求項１７】
前記実行ユニットの少なくとも一つが、他の実行ユニットの一つまたは複数とコンピューティング面で非対称的である、
請求項１１記載の装置。
【請求項１８】
前記待ち行列システムが、前記少なくとも一つの非対称的である実行ユニットのための作業記述子を保持するための第一の待ち行列を含み、前記一つまたは複数の他の実行ユニットのための記述子を保持するための第二の待ち行列をも含む、
請求項１７記載の装置。
【請求項１９】
オペレーティング・システムを有するコンピューティング・システムのマルチシーケンサー・マルチスレッド・システムであって：
メモリ・システムと；
第一のシーケンサー型の第一のシーケンサーであって、ここで、前記第一のシーケンサー型はオペレーティング・システムに可視である、第一のシーケンサーと；
第二のシーケンサー型の第二のシーケンサーであって、ここで、前記第二のシーケンサー型はオペレーティング・システムに不可視である、第二のシーケンサーと；
前記メモリ・システムに保存されているソフトウェア・ライブラリであって、実行されたときに作業待ち行列を生成するための一つまたは複数の命令を含むライブラリ、
とを有しており：
前記ライブラリがさらに、前記作業待ち行列からの作業をシーケンサー上での実行のために、ユーザー指令によりスケジューリングすることを実行する分散されたスケジューラを含み、前記分散されたスケジューラが、前記第一および第二のシーケンサーのためのスケジューリング・ループを実行する、
システム。
【請求項２０】
前記作業待ち行列が、ペンディングのソフトウェア・スレッドを記述する一つまたは複数のレコードを保持する、
請求項１９記載のシステム。
【請求項２１】
前記一つまたは複数のレコードが、それぞれ対応するペンディングのソフトウェア・スレッドの開始アドレスを含む、
請求項２０記載のシステム。
【請求項２２】
前記一つまたは複数のレコードが、それぞれ対応するペンディングのソフトウェア・スレッドについてのスタック・ポインタを含む、
請求項２０記載のシステム。
【請求項２３】
前記分散されたスケジューラがさらに、前記作業待ち行列からの作業をシーケンサー上での実行のために、ユーザー指令によりスケジューリングすることを、前記シーケンサーが同時並行してその関連付けられた作業を実行するように実行する、
請求項２０記載のシステム。
【請求項２４】
前記ライブラリがさらに、それぞれ関連付けられたユーザー生成された命令に応じてシュレッド命令を生成する一つまたは複数の関数を含んでおり、前記ユーザー生成された命令は一般的に知られたアプリケーション・プログラマ・インターフェース規格に準拠するものである、
請求項２０記載の方法。
【請求項２５】
マルチスレッド・プロセッサによって実行される、複数のシーケンサーの間でソフトウェア・シュレッドの実行をスケジューリングする方法であって：
ユーザー生成されたスレッド命令に応じて、スレッドを記述するスレッド記述子を生成手段によって生成する段階と；
前記スレッド記述子を待ち行列に入れる段階と；
それぞれが相異なるシーケンサーに関連付けられた複数のユーザーレベルの分散されたスケジューラ・ルーチンを実行手段によって実行する段階であって、前記複数のシーケンサーがオペレーティング・システムに基づくスレッド・スケジューラに従属せず、前記スケジューラ・ルーチンのそれぞれが前記待ち行列内の前記記述子を求めて競るものである、段階と；
前記スレッドを、前記シーケンサーの一つの上での実行のためにスケジューリング手段によってスケジューリングする段階、
とを有する方法。
【請求項２６】
前記ユーザー生成されたスレッド命令が、アプリケーション・プログラマ・インターフェースに含まれている命令である、
請求項２５記載の方法。
【請求項２７】
前記アプリケーション・プログラマ・インターフェースが業界標準に準拠している、
請求項２６記載の方法。
【請求項２８】
複数の機械アクセス可能命令を記憶した機械アクセス可能媒体であって、前記命令はプロセッサによって実行され、前記命令は：
ユーザー生成されたスレッド命令を実行する動作であって、スレッド制御命令を生成するライブラリ関数を呼び出すことをさらに含む動作と；
前記スレッド命令に応じて、スレッドを記述する作業記述子を生成する動作と；
前記作業記述子を待ち行列システム内に記憶させる動作と；
オペレーティング・システムの介入なしに、前記スレッドのシーケンサー上での実行をスケジューリングする動作と、
ユーザーレベルの同時並行マルチスレッド利用を実行するよう前記シーケンサーを初期化する動作であって、ユーザーレベルの分散されたスケジューラの、前記シーケンサー上での実行をトリガーすることをさらに含む動作、
とを提供する、機械アクセス可能媒体。
【請求項２９】
前記待ち行列システムが、第一のシーケンサー型に関連付けられた第一の待ち行列と、第二のシーケンサー型に関連付けられた第二の待ち行列とを含む、
請求項２８記載の機械アクセス可能媒体。
【請求項３０】
前記第一および第二のシーケンサーが、コンピューティング上の少なくとも一つの基準に関して非対称的である、
請求項２９記載の機械アクセス可能媒体。
【請求項３１】
前記コンピューティング上の基準が機能上の基準である、
請求項３０記載の機械アクセス可能媒体。
【請求項３２】
前記コンピューティング上の基準が電力消費基準である、
請求項３０記載の機械アクセス可能媒体。
【請求項３３】
前記機能上の基準が、リング0動作を実行する能力である、
請求項３１記載の機械アクセス可能媒体。
【請求項３４】
前記記憶させる動作を提供する命令が、プロセッサによって実行されたときに、前記作業記述子を、ユーザーが提供したヒントに基づいて前記第一の待ち行列に記憶させる命令をさらに有する；
請求項２９記載の機械アクセス可能媒体。
【請求項３５】
前記スレッド命令が、シュレッド生成命令である、
請求項２８記載の機械アクセス可能媒体。
【請求項３６】
前記スレッド命令が、シュレッド同期命令である、
請求項２８記載の機械アクセス可能媒体。
【請求項３７】
前記スレッド命令が、業界標準準拠のアプリケーション・プログラマ・インターフェースの一部である、
請求項２８記載の機械アクセス可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概括的には情報処理システムに、より詳細にはオペレーティング・システム介入なしにOS隔離シーケンサー（OS-sequestered  sequencers）上でスレッド実行のスケジューリングおよび制御に関する。
【背景技術】
【０００２】
マイクロプロセッサを含む情報処理システムのような、情報処理システムのパフォーマンスを上げるため、ハードウェア技術およびソフトウェア技術の両方が用いられてきた。ハードウェア側では、マイクロプロセッサのパフォーマンスを改善するためのマイクロプロセッサ設計法は、増加したクロック速度、パイプライン処理、分岐予測、スーパースカラー実行、アウト・オブ・オーダ実行およびキャッシュを含んできた。多くのそのようなアプローチはトランジスタ数の増大につながり、場合によってはパフォーマンス向上の割合よりも大きな割合でのトランジスタ数の増加をもたらしていた。
【０００３】
厳密に追加的なトランジスタを通じてパフォーマンス向上を図るのではない、他のパフォーマンス向上は、ソフトウェア技術に関わるものである。プロセッサのパフォーマンスを改善するために用いられてきたソフトウェア・アプローチの一つは、「マルチスレッド（multithreading）」として知られている。ソフトウェア・マルチスレッドにおいては、命令ストリームは、並列に実行できる複数の命令ストリームに分割される。あるいはまた、複数の独立したソフトウェア・ストリームが並列に実行されうる。
【０００４】
タイムスライス・マルチスレッドまたは時間多重（time-multiplex）（「TMUX」）として知られるアプローチでは、単一のプロセッサが、決まった時間期間後にスレッドを切り換える。もう一つのアプローチでは、単一のプロセッサが、長い遅延のキャッシュミス（a  long  latency  cache  miss）といったトリガー・イベントの生起に際してスレッドを切り換える。イベント時切り換えマルチスレッド（switch-on-event  multithreading）（「SoEMT」）として知られるこの後者のアプローチでは、ある所与の時間には高々一つのスレッドしかアクティブでない。
【０００５】
マルチスレッドはますますハードウェアでサポートされつつある。たとえば、あるアプローチでは、チップ・マルチプロセッサ（chip  multiprocessor）（「CMP」）システムのようなマルチプロセッサ・システムにおける各プロセッサは、同時並行して、複数のソフトウェア・スレッドの一つに対して作用しうる。同時マルチスレッド（simultaneous  multithreading）（「SMT」）と称されるもう一つのアプローチでは、単一の物理的なプロセッサが、オペレーティング・システムやユーザー・プログラムには複数の論理的なプロセッサとして見えるようにされる。SMTについては、複数のソフトウェア・スレッドが、切り換えなしに、単一のプロセッサ上で同時にアクティブであり実行されることができる。すなわち、各論理的なプロセッサがアーキテクチャ状態の完全なセットを維持するが、当該物理的なプロセッサの他の多くの資源、たとえばキャッシュ、実行ユニット、分岐予測器、制御論理およびバスは共有される。SMTについては、こうして、複数のソフトウェア・スレッドからの命令が同時並行して各論理的なプロセッサ上で実行される。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
SMTおよび／またはCMPシステムのような複数ソフトウェア・スレッドの同時並行的な実行をサポートするシステムのために、ソフトウェア・スレッドのスケジューリングおよび実行をオペレーティング・システム・アプリケーションが制御しうる。しかし、典型的には、オペレーティング・システム制御はスケーリングがよくなく、オペレーティング・システム・アプリケーションがパフォーマンスに悪影響を与えることなくスレッドをスケジューリングする能力は、普通には、比較的少数のスレッドに限定される。
本発明の諸実施形態は図面を参照しつつ理解されうる。図面では、同様の要素は同様の数字で示される。図面は限定することを意図されてはおらず、OS隔離スレッドを実行のためにスケジューリングする装置、システムおよび方法の選ばれた実施形態を解説するために与えられるものである。
【図面の簡単な説明】
【０００７】
【図１】マルチシーケンサー・システムのための、一般的な並列プログラミングのアプローチの図的な表現を示すブロック図である。
【図２】ユーザーレベルのマルチスレッドの少なくとも一つの実施形態のための、複数のスレッドおよびシュレッドの間で共有されるメモリおよび状態を示すブロック図である。
【図３】マルチシーケンサー・システムのさまざまな実施例を示すブロック図である。
【図４】ユーザーレベルのスレッド制御をサポートするマルチシーケンサー・マルチスレッド・システムのためのスケジューリング機構の少なくとも一つの実施形態を示すデータフロー図である。
【図５】非対称なマルチシーケンサー・マルチスレッド・システムのためのスケジューリング機構の少なくとも一つの実施形態を示すデータフロー図である。
【図６】複数の作業待ち行列を含むスケジューリング機構の少なくとも一つの実施形態を示すデータフロー図である。
【図７】ユーザー駆動でOS独立の、スレッドのスケジューリングのための制御フローの少なくとも一つの実施形態を示すタイミング図である。
【図８】ユーザー駆動でOS独立の、スレッドのスケジューリングのある個別的な例のための制御フローの少なくとも一つの実施形態を示すタイミング図である。
【図９】開示される技法を実行する機能のあるシステムの少なくとも一つの実施形態を示すブロック図である。
【発明を実施するための形態】
【０００８】
以下の議論は、一つまたは複数のOS隔離シーケンサー上の（「シュレッド（shred）」と称される）実行のスレッドをスケジューリングする、および／または他の仕方で制御する方法、システムおよび機構の選ばれた実施形態を記載する。OS隔離シーケンサー（OS-sequestered  sequencers）は本稿では「OS不可視（OS-invisible）」と称されることがある。ここに記載される機構は単一コアまたはマルチコアのマルチスレッド・システムで利用されうる。以下の記述では、本発明のより完全なる理解を提供するために、プロセッサの種類、マルチスレッド環境、システム構成、マルチシーケンサー・システムにおけるシーケンサーの数およびトポロジー、マイクロアーキテクチャ構造および命令命名体系ならびにパラメータといった数多くの個別的な詳細が述べられる。しかしながら、そうした個別的な詳細なしでも本発明が実施されうることは当業者によって理解されるであろう。さらに、いくつかのよく知られた構造、回路などは、本発明を無用に埋没させるのを避けるために詳しく示していない。
【０００９】
共有メモリマルチプロセッシングのパラダイムが、並列プログラミングと称されるアプローチにおいて使用されうる。このアプローチによれば、アプリケーションのプログラマは、ソフトウェア・プログラムについて並列を表現するために、ソフトウェア・プログラム（「アプリケーション」または「プロセス」と称されることもある）を同時並行して実行される複数のタスクに分割しうる。同じソフトウェア・プログラム（「プロセス」）のすべてのスレッドは、メモリについて共通の論理的なビューを共有する。
【００１０】
図１は、マルチシーケンサー・マルチスレッド・システム上での並列プログラミングのアプローチの図的な表現を示すブロック図である。図１は、オペレーティング・システム１４０に見えるプロセス１００、１２０を示している。これらのプロセス１００、１２０は、ワード・プロセッシング・プログラムおよび電子メール管理プログラムといった、異なるソフトウェア・アプリケーション・プログラムであってもよい。普通、各プロセスは異なるアドレス空間内で動作する。
【００１１】
オペレーティング・システム（「OS」）１４０は普通、図１に示されるプロセス１２０のようなプロセスについてユーザー生成のタスクを管理することを担う。したがって、オペレーティング・システム１４０は、プロセス１２０に関連付けられたユーザー定義のタスクのそれぞれについて相異なるスレッド１２５、１２６を生成することができ、スレッド１２５、１２６をスレッド実行資源にマッピングすることができる。（これらの実行資源は図１には示されていないが、のちに詳細に議論する。）OS１４０は普通、これらのスレッド１２５、１２６を実行資源上での実行のためにスケジューリングすることを担う。単一のプロセスに関連付けられた諸スレッドは、典型的には、メモリについて同じビューをもち、互いの仮想アドレス空間に対する可視性をもつ。
【００１２】
スレッドを生成し、マッピングし、スケジューリングすることはOS１４０が担うので、スレッド１２５、１２６はOS１４０に「見える」。さらに、本発明の諸実施形態は、OS１４０には見えない追加的なスレッド１３０〜１３６を包含する。すなわち、これらの追加的なスレッド１３０〜１３６については、OS１４０は生成、管理もしくは他の仕方での認識または制御をしない。OS１４０によって生成も制御もされないこうした追加的なスレッドは、OSに見えるスレッドと区別するため、本稿では時に「シュレッド」１３０〜１３６と称される。シュレッドはユーザーレベルのプログラムによって生成および管理され、オペレーティング・システムからは隔離されているシーケンサー上で走るようスケジューリングされる。OS隔離シーケンサーは、OS可視シーケンサーと同じリング0状態を共有する。このように、シュレッド（shred）は、同じプロセスに関連付けられた諸スレッド（thread）のために生成される同じ実行環境（アドレス・マップ）を共有する（share）。
【００１３】
ここでの用法では、「スレッド」および「シュレッド」の用語は、少なくとも、あるプロセスの他のスレッドおよび／またはシュレッドと同時並行して実行されるべき命令の集合の概念を含む。したがって、スレッドおよび「シュレッド」の用語はいずれも、ソフトウェア命令の集合の概念を包含する。ここでの用法では、どちらも命令のストリームであるスレッド（これはOSに制御される）とシュレッド（これはオペレーティング・システムには見えず、その代わりユーザーによって制御される）とを区別する因子は、スレッドおよびシュレッドの命令ストリームの実行がどのように管理されるかの相違にある。スレッドはOSへのシステムコールに反応して生成される。OSがそのスレッドを生成し、そのスレッドを走らせるために資源を割り当てる。スレッドに割り当てられたそのような資源は、オペレーティング・システムがスレッドを制御およびスケジューリングするために使うデータ構造を含みうる。
【００１４】
これに対し、シュレッドの少なくとも一つの実施例は、ユーザー命令または「プリミティブ」を介して生成される。それがOSが認識しないシュレッドを生成するためのソフトウェア・ライブラリまたはその他のOS独立な機構を呼び出すのである。このように、シュレッドはユーザーレベルのソフトウェア・ライブラリ・コールに反応して生成されうる。
【００１５】
図２は、同じソフトウェア・プログラムまたはプロセスのすべてのスレッドがメモリについて共通の論理的なビューを共有するという、上記の陳述に関するさらなる詳細を図的な形で示すブロック図である。本発明の諸実施形態については、この陳述は、プロセス１００、１２０に関連付けられたシュレッドに関しても真である。ここでは図２について、図１を参照しつつ議論する。
【００１６】
図２は、図１に示されるプロセス１２０、スレッド１２５、１２６およびシュレッド１３０〜１３６の図的な表現である。しかしながら、そのような表現は限定するものと解釈すべきではない。本発明の諸実施形態は必ずしもあるプロセスに関連付けられるスレッドまたはシュレッドの数に上限または下限を課すことはしない。下限に関しては、図１は、所与の時点において走っているあらゆるプロセスが必ずしも何らかのスレッドまたはシュレッドと関連付けられている必要はないことを示している。たとえば、図１に示したプロセス０  １００は、図１に示されている特定の時点ではスレッドもシュレッドもなしに走っていることが示されている。
【００１７】
しかしながら、別のプロセス１２０が、図１に示されるように、一つまたは複数のスレッド１２５、１２６に関連付けられていることがある。さらに、プロセス１２０は追加的に、一つまたは複数のシュレッド１３０〜１３６とも関連付けられていることがある。プロセス１２０についての二つのスレッド１２５、１２６および４つのシュレッド１３０〜１３６の表現はあくまでも例示的なものであって、限定するものと解釈すべきではない。あるプロセスに関連付けられたOS可視スレッドの数はOSプログラムによって限定されうる。しかしながら、プロセスに関連付けられたシュレッドの累積数についての上限は、少なくとも一つの実施例については、実行中のある特定の時点において利用可能なスレッド実行資源の数によってのみ限定される。図２は、プロセス１２０に関連付けられている第二のスレッド１２６が第一のスレッド１２５とは異なる数（n）の関連付けられたスレッドをもちうることを示している。（Nはスレッド１２５、１２６の一方または両方について0であってもよい。）
【００１８】
図２は、ある特定のプロセス１２０に関連付けられたすべてのスレッド１２５、１２６によって共有されるメモリのある特定の論理的なビュー２００を示している。図２は、各スレッド１２５、１２６がそれぞれ独自のアプリケーションおよびシステム状態２０２ａ、２０２ｂを有していることを示している。図２は、スレッド１２５、１２６についての該アプリケーションおよびシステム状態２０２が、その特定のスレッドに関連付けられたすべてのシュレッド（たとえばシュレッド１３０〜１３６）によって共有されることを示している。
【００１９】
したがって、図２は、本発明の少なくとも一つの実施形態についてのシステムが、スレッド１２５のようなOS可視スレッドと、該スレッドに関連付けられたシュレッド１３０〜１３６（これはOSには不可視）との間の一対多の関係をサポートしうることを示している。シュレッドを生成し、同期させ、その動作をその他の仕方で管理および制御するためにOSでなくプログラマがユーザーレベルの技法を用いうるという意味において、シュレッドはOS（図１の１４０参照）に「可視」ではない。OS１４０はスレッドを認識し、管理するものの、OS１４０はシュレッドは認識せず、管理も制御もしない。
【００２０】
こうして、スレッドユニット・ハードウェアとシュレッドとの間のマッピングを管理するためにオペレーティング・システムに頼る代わりに、少なくとも一つの実施例については、ユーザーがそのようなマッピングを直接的に制御でき、シュレッド実行に関連付けられた制御および状態転移を直接的に操作できる。したがって、ここに記載される方法、機構およびシステムの諸実施形態について、スレッドユニットのアーキテクチャのユーザーに見える特徴は、少なくとも、ユーザーにスレッドユニット・ハードウェアの直接操作および制御を許容する正準的な命令セットである。
【００２１】
ここでの用法では、スレッドユニット（ここでは交換可能的に「シーケンサー」とも称される）とは、スレッドまたはシュレッドを実行する機能のある任意の物理的または論理的なユニットでありうる。これは、所与のスレッドまたはシュレッドのために実行されるべき次の命令を決定するための次命令ポインタ論理を含みうる。たとえば、図２に示されるOSスレッド１２５は、図示されないシーケンサー上で実行されうる一方、アクティブなシュレッド１３０〜１３６のそれぞれは、それぞれ他のシーケンサー「seq1」〜「seq4」上で実行されうる。シーケンサーは論理的なスレッドユニットであっても物理的なスレッドユニットであってもよい。論理的なスレッドユニットと物理的なスレッドユニットとの間の区別を図３に示す。
【００２２】
図３は、開示されている技法を実行する機能のあるマルチシーケンサー・システムの実施例３１０、３５０の選ばれたハードウェア特徴を示すブロック図である。図３が示すのは、SMTマルチシーケンサー・マルチスレッド環境３１０の選ばれたハードウェア特徴を示している。図３はまた、複数コアのマルチスレッド環境３５０の選ばれたハードウェア特徴をも示しており、この場合、各シーケンサーは別個の物理的なプロセッサ・コアである。
【００２３】
SMT環境３１０では、単一の物理プロセッサ３０４は、オペレーティング・システムおよびユーザー・プログラムにとっては、複数の論理プロセッサ（図示せず）として見えるようにされる。該複数の論理プロセッサはここではLP1ないしLPnと称される。各論理プロセッサLP1ないしLPnは、それぞれ完全なセットのアーキテクチャ状態AS1〜ASnを含む。アーキテクチャ状態は、少なくとも一つの実施例については、データレジスタ、セグメントレジスタ、制御レジスタ、デバッグ・レジスタおよび大半のモデル固有のレジスタを含む。論理プロセッサLP1〜LPnは、キャッシュ、実行ユニット、分岐予測器、制御論理およびバスといった物理プロセッサ３０４の大半の他の資源を共有する。そのような特徴は共有されうるものの、マルチスレッド環境３１０における各スレッド・コンテキストは、次命令アドレスを独立して生成できる（そしてたとえば命令キャッシュ、実行命令キャッシュまたはトレース・キャッシュからのフェッチを実行できる）。こうして、プロセッサ３０４は、各スレッド・コンテキストについての命令をフェッチするため、論理的に独立な次命令ポインタおよびフェッチ論理３２０を含む。ただし、その複数の論理シーケンサーは単一の物理的なフェッチ／デコード・ユニット３２２において実装してもよいのであるが。SMTまたは実施例については、「シーケンサー」の用語は少なくとも、あるスレッド・コンテキストについての次命令ポインタおよびフェッチ論理３２０を、そのスレッド・コンテキストについての関連付けられたアーキテクチャ状態ASの少なくとも一部とともに包含する。SMTシステム３１０のシーケンサーが対称的である必要はないことも注意しておくべきである。たとえば、同じ物理コアのための二つのSMTシーケンサーは、そのそれぞれが維持するアーキテクチャ状態情報の量において違っていてもよい。
【００２４】
こうして、少なくとも一つの実施例については、マルチシーケンサー・システム３１０は、同時並行マルチスレッドをサポートする単一コアのプロセッサ３０４である。そのような実施形態については、各シーケンサーは、独自の命令次命令ポインタおよびフェッチ論理と独自のアーキテクチャ状態情報とをもつ論理プロセッサであるが、同じ物理プロセッサ・コア３０４がすべてのスレッド命令を実行する。そのような実施形態については、論理プロセッサは、アーキテクチャ状態については独自のバージョンを維持するが、単一のプロセッサ・コアの実行資源は同時実行されるスレッドの間で共有されうる。
【００２５】
図３は、マルチコア・マルチスレッド環境３５０の少なくとも一つの実施形態をも示している。そのような環境３５０は、それぞれが異なるスレッド／シュレッドを実行する機能をもつ二つ以上の別個の物理的プロセッサ３０４ａ〜３０４ｎを含んでおり、該複数の異なるスレッド／シュレッドの少なくとも一部分の実行は同時に進行しうるようになっている。各プロセッサ３０４ａないし３０４ｎは、それぞれのスレッドまたはシュレッドのための命令情報をフェッチするため、物理的に独立なフェッチ・ユニット３２２を含んでいる。各プロセッサ３０４ａ〜３０４ｎが単一のスレッド／シュレッドを実行する実施形態では、フェッチ／デコード・ユニット３２２は単一の次命令ポインタおよびフェッチ論理３２０を実装する。しかしながら、各プロセッサ３０４ａ〜３０４ｎが複数スレッド・コンテキストをサポートする実施形態では、フェッチ／デコード・ユニット３２２は、サポートされるスレッド・コンテキストそれぞれについて相異なる次命令ポインタおよびフェッチ論理３２０を実装する。マルチプロセッサ環境３５０における追加的な次命令ポインタおよびフェッチ論理３２０が任意的であるという性質は、図３で点線によって表されている。
【００２６】
こうして、図３に示されるマルチコア・システム３５０の少なくとも一つの実施例については、シーケンサーのそれぞれは、単一のチップ・パッケージ３６０に複数のコア３０４ａ〜３０４ｎが存在しているプロセッサ・コア３０４でありうる。各コア３０４ａ〜３０４ｎは、単一スレッドまたはマルチスレッドのプロセッサ・コアのいずれでもありうる。図３ではチップ・パッケージ３６０は破線で表されているが、これはマルチコア・システム３５０の図示されている単一チップ実施形態が単に例示的であることを示している。他の実施形態については、マルチコア・システムのプロセッサ・コアは別個のチップ上に存在してもよい。
【００２７】
議論を簡単にするため、以下の議論はマルチコア・システム３５０の諸実施形態に焦点を当てる。しかしながら、この焦点は限定するものと解釈するべきではない。以下に記載される機構は、マルチコアまたは単一コアのマルチシーケンサー環境のいずれにおいて実行されてもよいのである。
【００２８】
図４は、ユーザーレベルのスレッド制御をサポートするマルチシーケンサー・マルチスレッド・システムのためのスケジューリング機構４００の少なくとも一つの実施形態を示すデータフロー図である。図４は、機構４００が作業待ち行列システム４０２を含むことを示している。該機構はまた、スケジューラ・ルーチン４５０をも含むが、これは複数シーケンサー４０３、４０４のそれぞれの上で実行されうる。
【００２９】
作業待ち行列システム４０２は、少なくとも一つの実施例については、実行の順番待ちをしていてしたがって「ペンディング」であるユーザー定義のシュレッドのための記述子を維持しうる。上で述べたように、OSが提供するスケジューリング機構ではないスケジューリング機構４００が用いられうる。各作業記述子は、OS介入とは独立して、OS隔離されたまたはOS可視のシーケンサーのいずれかの上で実行されるべきシュレッドを記述する。
【００３０】
シュレッド記述子は、ユーザーレベルのシュレッド生成命令すなわちプリミティブによって生成されうる。当業者は、プログラマのコードと、シーケンサーにシュレッド記述子の生成および該記述子の作業待ち行列４０２への配置につながる動作を実行させる実際のアーキテクチャ命令との間に、抽象化のいくつかのレベルがありうることを認識する。ここでの用法では、プログラマまたはユーザーによって生成されると述べられる命令は、ユーザー生成されたコードに基づいてアセンブラまたはコンパイラによって、またはアセンブリ言語で作業しているプログラマによって生成されうるアーキテクチャ命令のみならず、最終的にアセンブルまたはコンパイルされてアーキテクチャ上のシュレッド制御命令になる任意の高級プリミティブまたは命令をも包含することが意図されている。アーキテクチャ上のシュレッド制御命令がさらにスレッド実行ユニットによって一つまたはマイクロ演算にデコードされうることも理解されるべきである。
【００３１】
図４は、シーケンサーのそれぞれについてのスケジューラ・ルーチン４５０ａ、４５０ｂが、関連付けられたシーケンサー４０３、４０４上での実行のためにシュレッドを取得するために、作業待ち行列システム４０２にアクセスしうることを示している。このように、図４は、シュレッドのユーザーレベルでのマッピングおよび制御を許容するスケジューリング機構の少なくとも一つの実施形態を示している。該シュレッドは、シュレッドのスケジューリングのためのOS介入なしに、互いに、および／またはOSに制御されるスレッドと同時並行して実行されうる。
【００３２】
図４に示されているシーケンサー４０３、４０４が対称的である必要はなく、その数も限定するものと解釈されるべきではないことを注意しておくべきである。シーケンサーの数に関しては、スケジューリング機構４００はシーケンサーいくつについて利用されてもよい。たとえば、スケジューリング機構は、４個、８個、１６個、３２個またはそれ以上のシーケンサーを含むマルチシーケンサー・システムについて実装されうる。
【００３３】
対称性に関し、シーケンサー４０３、４０４は、計算の品質に影響する諸側面も含め、あらゆる仕方で異なりうる。たとえば、シーケンサーは電力消費、計算実行のスピード、機能上の特徴などに関して異なりうる。例として、ある実施形態については、シーケンサー４０３、４０４は機能性の面で異なりうる。たとえば、一つのシーケンサーは整数および浮動小数点命令を実行する機能をもつが、ストリーミングSIMD拡張３（「SSE3」）のような単一命令多重データ（single  instruction  multiple  data）（「SIMD」）命令セット拡張は実行できないことがありうる。その一方で、別のシーケンサーは第一のシーケンサーが実行できるすべての命令を実行できる上にSSE3命令を実行できることがありうる。
【００３４】
機能上の非対称のもう一つの例として、本発明のある実施形態については、あるシーケンサーはOS（たとえば図１の１４０参照）に可視でもよく、したがってシステムコール、ページフォールトへの対応などを実行するような「リング0」動作を実行する機能をもちうる。他方、別のシーケンサーは、OSから隔離されていて、リング0動作を実行することができないこともありうる。
【００３５】
スケジューリング機構４００が利用されるシステムのシーケンサーも、大きさ、語長および／またはデータ路サイズ、トポロジー、メモリ、電力消費、機能ユニット数、通信アーキテクチャ（マルチドロップかポイントツーポイント相互接続か）または機能性、パフォーマンス、フットプリントなどに関係する他の任意の基準といった、あらゆる仕方で異なりうる。
【００３６】
図５は、非対称なマルチシーケンサー・マルチスレッド・システムのためのスケジューリング機構５００の少なくとも一つの実施形態を示すデータフロー図である。図５は単に非対称の一つの実施形態を示すものであり、第一のシーケンサー５０３はオペレーティング・システム５４０に可視である一方、第二のシーケンサー５０４はオペレーティング・システム５４０から隔離されている。ここでもまた、当業者は、他の型の非対称がシステムに存在していてもよく、三つ以上のシーケンサーがシステムに存在していてもよいことを認識するであろう。
【００３７】
図５は、OS可視シーケンサー５０３および隔離シーケンサー５０４のそれぞれについてのスケジューラ・ルーチン４５０ａ、４５０ｂが、該スケジューラのインスタンス４５０ａ、４５０ｂに対応するシーケンサー５０３、５０４上で実行されるべきシュレッドを求めて作業待ち行列システム５０２を探査することを示している。ここでもまた、そのような機構５００は、オペレーティング・システム５４０の介入なしに、非対称なシーケンサー上でのシュレッドのスケジューリングを提供する。
【００３８】
図６は、非対称なマルチシーケンサー・マルチスレッド・システムのための、スケジューリング機構６００の少なくとも一つの実施形態についてのさらなる詳細を示すデータフロー図である。図６は、作業待ち行列６０２が複数の作業待ち行列６０４、６０６を含みうることを示している。少なくとも一つの実施形態について、複数の作業待ち行列６０４、６０６のそれぞれは、あるシーケンサー型に関連付けられる。図６に示された見本実施形態については、第一の待ち行列６０４は、ここでは「A型」と称される第一の型のシーケンサー６４０の一つまたは複数の集合に関連付けられている。第二の待ち行列６０６は、ここでは「B型」と称される第二の型のシーケンサー６４２の一つまたは複数の集合に関連付けられている。これまでの図に示した他の実施形態の場合と同様、図６に示されるような待ち行列およびシーケンサー型の数ならびに各型のシーケンサーの数は限定するものと解釈すべきではない。
【００３９】
したがって、図６は、少なくとも二つの型の非対称なシーケンサー――A型シーケンサー６４０およびB型シーケンサー６４２――を含むシステムについてのスケジューリング機構６００を示している。待ち行列システム６０２は、シーケンサーの各型に関連付けられた作業待ち行列６０４、６０６を含む。各シーケンサー６４０、６４２は、分散されたスケジューラ・ルーチン４５０の一部分を含む。部分４５０ａ、４５０ｂは互いに同一のコピーであってもよいが、それは必須ではない。
【００４０】
図６は、第一の待ち行列６０４がA型シーケンサー６４０の上で走るシュレッド６２３についてのシュレッド記述子を含みうることを示している。第二の待ち行列６０６がB型シーケンサー６４２の上で走るシュレッド６２４についてのシュレッド記述子を含みうる。A型のシュレッド６２３は、A型シーケンサー６４０によって提供される特定の機能性を利用するためにユーザーによって書かれたソフトウェア・シーケンスでありうる。同様に、B型のシュレッド６２４は、B型シーケンサー６４２によって提供される特定の機能性を利用するためにユーザーによって書かれたソフトウェア・シーケンスでありうる。
【００４１】
少なくとも一つの実施例については、A型およびB型シーケンサーの機能性は互いに排反でありうる。すなわち、たとえば、ある集合の諸シーケンサー６４０は、もう一方の集合の諸シーケンサー６４２がサポートしない、SSE3命令の実行のようなある特定の機能性をサポートできる。その一方、別のある集合の諸シーケンサー６４２は、もう一方の集合の諸シーケンサー６４０がサポートしない、リング0動作のようなある特定の機能性をサポートできる。
【００４２】
そのような実施形態について、スケジューリング機構６００の動作は、第一の型のシュレッド６２３についての記述子はA型シーケンサー６４０上のスケジューラ・ルーチン４５０によって第一の待ち行列６０４から引き出すことができ、その一方、第二の型のシュレッド６２４についての記述子はA型シーケンサー６４０上のスケジューラ・ルーチン４５０によって第一の待ち行列６０４から引き出すことができるようなものである。シュレッドの適切なシーケンサーへのマッピングはユーザーレベルの命令によって指令されうる。
【００４３】
しかしながら、図６で図示した実施形態のような少なくとも一つの他の実施例については、A型シーケンサー６４０とB型シーケンサー６４２の機能性は、互いに排反な機能性の関係ではなく、上位集合―部分集合の機能性関係を表す。すなわち、第一の集合のシーケンサー（A型シーケンサー６４０のような）は、第二の集合のシーケンサー（B型シーケンサー６４２のような）のすべての機能性に加えて、該第二の集合のシーケンサー６４２によって提供されない追加的な機能性をも含む、上位集合の機能性を提供するのである。そのような実施形態については、A型シーケンサー６４０のためのスケジューラ・ルーチン４５０は、任意的に、第二の待ち行列６０６からのシュレッド記述子を取得しうる。この任意的な処理は、たとえばA型シーケンサーのためのすべての記述子が利用不能である（たとえば、第一の待ち行列６０４が空であるような）場合に実行されうる。換言すれば、上位集合の機能性をもつシーケンサーは、そのようなシーケンサーのために特に指定されたシュレッドを実行しうるが、部分集合の機能性のシーケンサーのために指定されたシュレッドをも実行しうるのである。
【００４４】
最後に、図６は、別のシュレッドによって、またはシュレッド認識スレッド（shred-aware  thread）によって実行されたシュレッド生成命令に反応してシュレッド記述子が作業待ち行列システム６０２に入れられ６６０うることを示している。少なくとも一つの実施例については、シュレッド記述子の生成をトリガーする命令は、shred_createのようなAPI様（「アプリケーション・プログラマ・インターフェース［Application  Programmer  Interface］」）スレッド制御プリミティブである。ソフトウェア・ライブラリによって提供されるようなソフトウェアが、shred_createプリミティブに反応して、新たなシュレッドについてのシュレッド記述子を生成することができ、それを作業待ち行列システム６０２に入れることができる。
【００４５】
少なくとも一つの実施例については、シュレッド記述子はこうしてshred_createプリミティブに反応してソフトウェアによって生成され、待ち行列システム７０２に入れられる。シュレッド記述子は、少なくとも一つの実施例については、シュレッドについて少なくとも以下の属性を同定するレコードでありうる：ａ）シュレッドが実行を開始すべきアドレス、およびｂ）スタック記述子。このスタック記述子は、新たなシュレッドが、ローカル変数および戻りアドレスのような一時変数を記憶するために使うメモリ記憶領域（スタック）を同定する。
【００４６】
図７は、図４〜図６に示したいずれかのようなスケジューリング機構の実施形態を利用するための見本系列を示すデータフロー図であり、マルチシーケンサー・システム上での実行のためのシュレッドのユーザーレベルのスケジューリングを実行するためのものである。少なくとも一つの実施例については、方法７００は、シーケンサー７７０上で走っているスレッドTによって実行される。少なくとも一つの実施例については、方法７００は、プログラマのようなユーザーによって生成される命令に反応して実行される。図７については、そのような命令は、スレッドTの命令と称される。もちろん、方法７００の諸ブロックは、図７に示したのとは異なる系列においてユーザーによってプログラムされてもよい。
【００４７】
図７は、シーケンサーが機能上の基準に関して非対称であるマルチシーケンサー・システムの見本実施形態を示している。すなわち、スレッドTが実行されるシーケンサー７７０はOS可視シーケンサーである。よって、シーケンサー７７０は、オペレーティング・システムとの対話を介して、リング0動作（すなわち、ページフォールトへの対応、システムコールの実行など）のような特権動作を実行しうる。これに対し、図７に示した見本実施形態は、OSに可視でない隔離シーケンサー７６０をも含む。よって、隔離シーケンサー７６０は特権動作を実行することはできない。隔離シーケンサーはたとえば、リング3動作を実行するが、リング0動作を実行することはできないように限定されうる。このように、図７は、非対称なシーケンサーを含むマルチシーケンサー・システムの見本実施形態を示しているのである。
【００４８】
図７に示した実施形態については、方法７００はブロック７０１で開始され、ブロック７０４に進む。ブロック７０４では、スレッドTが、該スレッドTに関連付けられた一つまたは複数の同時並行シュレッドのユーザーレベルの制御のために初期化を実行する一つまたは複数の命令を実行する。少なくとも一つの実施例については、そのような初期化７０４は、作業待ち行列システム７０２の一つまたは複数の待ち行列（たとえば図６の６０４および６０６参照）の生成および／または初期化を含みうる。
【００４９】
さらに、図７は、そのような初期化７０４が一つまたは複数の隔離されたシーケンサー７６０を含みうることを示している。もちろん、当業者は、ブロック７０４に示された待ち行列生成およびシーケンサー初期化が必ずしも単一のルーチン、方法または関数によって実行される必要はなく、ここで論じられる逐次順で実行される必要もないことを認識するであろう。たとえば、ある代替的な実施形態では、ブロック７０４で行われる初期化動作は、逆順に実行されてもよいし、あるいは同時並行して実行されてもよい。
【００５０】
ブロック７０４のシーケンサー初期化ブロックは、コンピュータ・プログラマのようなユーザーによってスレッドTについての命令ストリーム中に入れられたユーザー生成のシュレッド生成命令によって指示されるシュレッドを走らせるよう、隔離シーケンサー（単数または複数）７６０を準備するために実行されうるものである。少なくとも一つの実施例については、そのようなシーケンサー初期化は、隔離シーケンサー７６０のそれぞれの上の分散されたスケジューラ・ルーチン４５０の呼び出しを含みうる。のちにさらに詳細に論じるように、スケジューラ・ルーチン４５０の呼び出しは、スケジューリング・ループの実行につながりうる。ここで、分散されたスケジューラの各部分は、対応する隔離シーケンサー７６０によって実行されうる作業について作業待ち行列システム７０２を定期的に検査することを始める。
【００５１】
そのような初期化７０４なしでは、少なくとも一つの実施例については、隔離シーケンサー（単数または複数）７６０がシュレッドを実行するために利用でないことが予期される。少なくとも一つの実施例については、シュレッドを実行するようシーケンサー７６０を準備する初期化７０４は、少なくとも、スケジューラ・ルーチン４５０の呼び出しを含む。初期化７０４は、スレッドTについての命令ストリーム中でユーザーによって指示される各シーケンサーのために実行されうる。少なくとも一つの実施例については、スレッドTによる実行のために初期化されたすべてのシーケンサーは、スレッドTが関連付けられているプロセスのためにオペレーティング・システムが構築した仮想メモリの同じビューを共有する。
【００５２】
処理はブロック７０４からブロック７０６へと進む。ブロック７０６では、スレッドTは、ユーザー定義のmainシュレッド関数で始まる実行のためのシュレッド記述子を生成する。少なくとも一つの実施例については、ユーザー定義のmainシュレッド関数は、伝統的なOS可視のmain()関数を置き換える。図７は、mainシュレッドについてのシュレッド記述子が、作業待ち行列システム７０２に入れられうることを示している。したがって、mainシュレッドは、次の機会に分散されたシュレッド・スケジューラ・ルーチン４５０の一つによって実行のためにスケジューリングされるべく、順番待ちに入れられる。
【００５３】
ブロック７０６から、処理はブロック７０８に進む。ブロック７０８では、OS可視スレッドTが独自のスケジューリング・ループを開始する。したがって、スレッドTは、シーケンサー７７０上のスケジューラ・ルーチン７５０を初期化するために一つまたは複数の命令を実行する。図７は、スケジューラ７５０が、作業を第一のシーケンサー７７０上にスケジューリングするために作業待ち行列システム７０２を参照しうることを示している。このように、図７は、すべてのシュレッド記述子が共通の待ち行列システム７０２に送られる実施形態を示している。すべてのスケジューラ・ルーチン４５０ａ〜４５０ｎ、５５０はその共通の待ち行列システム７０２に作業を要求し、スケジューリングするのである。スケジューリング・ルーチン４５０ａ〜４５０ｎの諸インスタンスは複数の隔離シーケンサーの間に分散されているので、スケジューリング・ルーチン４５０はここでは「分散された」スケジューラと称されうる。
【００５４】
少なくとも一つの実施例については、OS可視シーケンサー７７０（第一の型）は、待ち行列システム７０２の第一の作業待ち行列（たとえば図６の６０４参照）に関連付けられており、一方、隔離シーケンサー（第二の型）は、待ち行列システム７０２の第二の作業待ち行列（たとえば図６の６０６参照）に関連付けられている。図６との関連で先に説明したように、少なくとも一つの実施例については、第一のシーケンサー７７０は、作業待ち行列システム７０２内のどの待ち行列からでも作業を引き出しうる。
【００５５】
このようにして、OS可視シーケンサー７７０および一つもしくは複数の隔離シーケンサー７６０の両方が初期化され７０４、７０６、スケジューリングのような管理をOSに頼るのではなくユーザー生成された命令に基づいてシュレッドを実行できるようになった。図示したように、そのようにする少なくとも一つの機構は、mainシュレッド・ルーチンのためのシュレッド記述子を生成するシーケンサー７７０上のより一般的なOS可視スケジューラ・ルーチン７５０を呼び出すとともに、初期化された（ブロック７０４参照）隔離シーケンサー７６０上のスケジューラ・ルーチン４５０を呼び出すことである（ブロック７０８参照）。ブロック７０８から、処理はブロック７１０に進む。
【００５６】
ブロック７１０では、シーケンサー７７０は、そのスケジューラ７５０によってシーケンサー７７０上にスケジューリングされた命令を実行する。ブロック７１０の性質は、シーケンサー７７０上で複数のシュレッドまたはスレッド部分が逐次的に実行されうるという意味で反復的であってもよい。ブロック７１０が潜在的に反復的であるという性質は、図７では破線で表されている。
【００５７】
シーケンサー７７０は、そのシーケンサー型に関連付けられた作業待ち行列システム７０２の待ち行列においてシュレッド記述子によって指示されるシュレッド命令を実行しうる。そのような命令は、追加的なシュレッド記述子が生成され、作業待ち行列システム７０２に入れられるようにする命令を含みうる。
【００５８】
少なくとも一つの実施例については、シーケンサー７７０によって実行されるシュレッドは、隔離シーケンサー７６０では実行できず、７７０のシーケンサー型によって与えられる機能性を必要とするシュレッドを含みうる。たとえば図７に示した例については、シーケンサー７７０に関連付けられた待ち行列は、リング0動作を要求するシュレッド命令を含みうる。すなわち、OSはOS可視シーケンサーによって発されるシステムコールにしか対応できないので、シュレッドによって実行されるオペレーティング・システム・コールは特別な扱いを要求しうるのである。OS隔離シーケンサー７６０上で走るシュレッドのためのシステムコールは、プロキシ機構を介することでOS可視シーケンサー７７０によって実行されうる。
【００５９】
このプロキシ機構は、OS可視シーケンサーが、特権命令について前進するためにオペレーティング・システムの注意を得るためにシュレッドのなりすましをすることを許容する。プロキシ機構を実装しうる仕方はいくらでもある。たとえば、そのような機構は、隔離シーケンサー７６０が、OS隔離シーケンサー上でシステムコールのような特権命令の実行を試みるときに暗黙的に呼び出されてもよい。試みられたシステムコールは例外の生成を引き起こしうる。例外のハンドラがシュレッド状態を保存し、そのシステムコールについてのシュレッド記述子を生成し、該シュレッド記述子をOS可視シーケンサー７０２に関連付けられた待ち行列に入れることができる。そのような記述子がOS可視シーケンサー７７０上での実行７１０のためにスケジューリングされるとき、シーケンサー７７０は、シュレッドの状態を得てシステムコールを実行する前に、自分自身の状態を保存しうる。そのようなプロキシ実行については、OS可視シーケンサー７７０上での実行は、OS隔離シーケンサー７６０上でのフォールトを引き起こした命令において再開される。その際、シュレッドの状態が保存され、制御はフォールトしたOS隔離シーケンサー７６０に返され、それによりそのシュレッドの実行を続けることができる。
【００６０】
少なくとも一つの他の実施例については、特権命令に対するプロキシ実行はユーザーによって明示的に制御されうる。そのような実施形態については、ユーザーは明示的に、特権命令を含んでいるシュレッドがOS可視シーケンサー７７０上で実行されるべきであることを示しうる。そのような指示は、シュレッド生成プリミティブのパラメータまたは変形として表現されうる。待ち行列選好パラメータを含めること、あるいは特化したシュレッド生成プリミティブを使用することは、ここではいずれもまとめてスケジューリング・ヒントと称される。
【００６１】
シュレッド生成プリミティブ（たとえば「shred_create()」のような）プリミティブはライブラリ関数を呼び出しうる。その関数は、新たなシュレッド記述子の生成を引き起こし、さらにその記述子の、作業待ち行列システム７０２の待ち行列内への配置を引き起こす。標準的なshred_create()プリミティブの任意的なパラメータは、ユーザーがその記述子についての待ち行列型を指定することを許容しうる。あるいはまた、ここではshred_create_affinity()と称される任意的な関数コールが、ユーザーがその特定のシュレッドについての待ち行列選好（preference）を表現するために利用されうる。たとえば、シュレッドが多数のシステムコールを含んでいる場合、ユーザーはリング0動作を実行できるシーケンサー型に関連付けられた作業待ち行列を指定しうる。当業者は、同様のパラメータおよび／または代替パラメータのアプローチが譲歩プリミティブ（a  yield  primitive）とともに利用されてもよいことを認識するであろう。
【００６２】
図７に示したシステムは、システムコールの扱いに関係した追加的な安全措置を含みうる。たとえば、OSコールのまわりのシリアル化を提供するためにミューテックスが利用されうる。ミューテックスは、あるスレッドと一つまたは複数のその関連付けられたシュレッドとがスレッド同期のためにオペレーティング・システムによって提供される同じロックを取得しようと試みる場合に生じうるデッドロックを最小化するために利用されうる。
【００６３】
ブロック７１０で実行されるいかなるシュレッドまたはシュレッド部分についても、シーケンサー７７０は、そのシュレッドの実行を、終了（exit）または譲歩（yield）プリミティブが実行されるまで継続しうる。現在のシュレッドにおいて「終了」プリミティブに遭遇した場合、現在のシュレッドの実行は完了し、スケジューラ７５０は、待ち行列システム７０２の適切な待ち行列をつついて、シーケンサー７７０上での実行のために別の命令シーケンスをスケジュールさせうる。少なくとも一つの実施例については、終了命令はこのようにシュレッドを完了であるとしてマークし、制御はスケジューラ７５０に戻る。
【００６４】
現在のシュレッドにおいて「譲歩」プリミティブに遭遇した場合には、その呼び出しプロセスについてのシュレッド記述子が待ち行列システムに戻されることができ、制御はスケジューラ７５０に戻されることができる。したがって、「譲歩」プリミティブの実行に際しては、現在のシュレッドについての残りのシュレッド命令についてのシュレッド記述子が作業待ち行列システム７０２内に入れられうる。
【００６５】
終了または譲歩のいずれの場合についても、現在のシュレッドの実行がブロック７１０で完了したのち、処理はブロック７１２で終わりになりうる。あるいはまた、新たなスレッドまたはシュレッドが実行のためにスケジューリングされてもよい。したがって、ブロック７１０からブロック７１０に戻るループをなす破線は、シーケンサー７７０によって追加的なスレッドまたはシュレッドが実行されうることを示している。分散されたスケジューラ７５０によってスケジューリングされたすべてのスレッドおよび／またはシュレッド（もしくはシュレッド部分）の実行が完了したのち、処理はブロック７１２で終わりうる。
【００６６】
ブロック７１０の実行後に追加的なシュレッドをスケジューリングすることに関し、譲歩または終了命令が実行されたあと、現在のシーケンサー７７０上の分散スケジューラ７５０によって新たなシュレッドが実行のためにスケジューリングされうる。少なくとも一つの実施例については、そのような動作は、スケジューラ７５０が、自分とは異なるシーケンサー型に関連付けられた作業待ち行列から作業を得る結果として生起する。
【００６７】
あるいはまた、追加的なOS可視命令がブロック７１０のあとに実行されうる。そのような作業は、シーケンサー７７０自身のシーケンサー型に関連付けられた作業待ち行列からスケジューリングされうる。上述したように、少なくとも一つの実施例については、シーケンサー７７０のスケジューラ７５０は、自分の待ち行列が空である場合、もともとOS隔離シーケンサー上で実行されるよう指定されているシュレッドしかスケジューリングしない。
【００６８】
図８は、OS独立なシュレッドのスケジューリングのための制御フローの少なくとも一つの実施形態を示すタイミング図である。解説の目的のため、図８のタイミング図は、図７に示された方法実施形態７００の特定の例についての制御フローを示している。したがって、以下では図８は図７を参照しつつ論じる。図７に示したように、図８に示される方法８００は第一のOS可視シーケンサー（８７０）と第二の隔離されたシーケンサー（８６０）によって実行されうる。
【００６９】
図８は、第一の型の第一のシーケンサー８７０上の初期化７０４（図７参照）の少なくとも一つの実施形態についてのさらなる詳細を示している。少なくとも一つの実施例については、シーケンサー８７０は、機能上の基準に関して第二のシーケンサー８６０と区別される。すなわち、第一のシーケンサー８７０はOS可視である一方、第二のシーケンサー８６０は隔離されている。
【００７０】
図８は、少なくとも二つのユーザー生成命令の実行を含みうる。ここでシュレッド・モニタ（「SEMONITOR」）命令と称される第一の命令は、OS可視シーケンサーとOS隔離シーケンサーとの間の通信のためのチャネルの確立のために使われる。第二の初期化命令は制御移行命令であり、ここではシュレッド移行（「SXFR」）命令と称される。
【００７１】
当業者は、ここに記載されている方法７００、８００およびシステムはシュレッド制御命令についてのいかなる特定の命名体系にも命令セット・アーキテクチャにも限定される必要がないことを認識するであろう。当業者はまた、SEMONITOR型命令およびSXFR型命令が、先に論じたshred_create()、shred_create_affinity()、shred_yield()およびshred_exit()といったプリミティブについてのコンパイラ、アセンブラまたはライブラリ関数の結果として生成されうることも認識するであろう。この意味で、最終的な（ultimate）命令は、より上のレベルのユーザー構築物に反応して生成されたのではあっても、やはりここでは「ユーザー生成」されたと称される。上記のシュレッド・プリミティブの部分的なリストは、限定するものと解釈すべきではない。
【００７２】
当業者はまた、付属の請求項が、最終的なシュレッド制御命令が必ずしもハードウェアにサポートされた命令ではない実施形態をも包含することを認識するはずである。そうではなく、少なくとも一つの実施例については、プリミティブに反応して生成される「命令」は、アーキテクチャ上の命令の代わりに、ハードウェア信号であってもよい。割り込みまたはその他のシーケンサー制御信号のような信号は、SEMONITOR型およびSXFR型の機能性を実装するためにユーザー生成されたプリミティブに反応してソフトウェアまたはファームウェア層によって生成されうる。
【００７３】
代わりに、方法７００、８００は一般的に、シーケンサー８７０、８６０がシュレッドを生成および制御するためのアーキテクチャ上のユーザーレベルの命令をサポートすること、ならびに伝統的なマルチスレッドAPIが正準的なシュレッド命令セットを使って完全に実装されうることを想定する。正準的なシュレッド命令のセットの一つの見本のさらなる議論については、「複数の命令シーケンサー上での、命令セットに基づくスレッド実行のための機構（A  Mechanism  For  Instruction  Set-Based  Thread  Execution  on  a  Plurality  of  Instruction  Sequencers）」と題する、同時係属中の米国特許出願、代理人整理番号42390.P19770を参照されたい。
【００７４】
少なくとも一つの実施例については、シーケンサー８７０、８６０は少なくとも、SEMONITORおよびSXFRに沿った命令を含む正準的なシュレッド命令のセットをサポートすることが想定される。複数シーケンサーの動作を制御し、特に制御のシーケンサー間での移行を実施するためにユーザーがこの型の命令を利用する機能は、ここでは「シーケンサー算術（sequencer  arithmetic）」と称される。シーケンサー算術を提供するシュレッド命令は、少しばかり例を挙げれば分岐（fork）、結合（join）、譲歩（yield）、終了（exit）、ロック（lock）、待機（wait）およびロック解除（unlock）といったより高いレベルのシュレッド・プリミティブを構築するための構成要素として利用されうる。これらのプリミティブは、OSレベルのスケジューリングなしに実行される同時並行の共有メモリのシュレッドのユーザーレベルでの管理を許容するために利用されうる。このようにして、正準的なシュレッド命令は、アーキテクチャ上のシュレッド命令とアプリケーション・ソフトウェアとの間の抽象化の層を築くために利用されうる。よって正準的なシュレッド命令は、レガシー・アプリケーション・プログラム・インターフェースをサポートする抽象化の層を築くために利用されうるのである。
【００７５】
一般に、SXFR型の命令は、第一のシーケンサーによって実行されるとき、該第一のシーケンサーからある第二のシーケンサーに信号を送る。従って、SXFR型の命令は、サービスのためのシュレッド間信号伝達を実行する機構を提供する。SXFR型の命令の作用は同期的である。これは、ユーザーが、SXFR型命令をコード中に巧妙に位置させることによって、シュレッド命令ストリームにおける他の命令の実行に対するSXFR命令の実行のタイミングを制御できるという意味においてである。
【００７６】
これに対し、SEMONITOR型の命令は、非同期的なシーケンサー算術を提供する。SEMONITOR型命令はプログラマによって、第一のシーケンサーからの信号をモニタリングするようある第二のシーケンサーを構成設定するために使用されうる。
【００７７】
図８は、第一の初期化命令、SEMONITOR命令が、指定された目標シーケンサー上に、特定のイベント型へのハンドラ・ルーチンをマッピングすることを示している。すなわち、図８に示されるSEMONITOR命令の実施形態は、特定のルーチンのための開始命令ポインタアドレス（ここでは、分散スケジューラ・ルーチン「Scheduler」の開始）を、指定されたシーケンサーid、1についてのあるイベント型「init」にマッピングする。第一のシーケンサー上でSEMONITOR命令を実行したときの、目標シーケンサーに対する結果は、前記目標シーケンサーが指示されたイベント・インジケータをモニタリングし、指定されたアドレスで前記目標シーケンサーに対する制御のフローを開始するということである。
【００７８】
イベント型は、少なくとも一つの実施例については、インジケータとして実装されうる。たとえば、指定されたイベントが第一のシーケンサーによって指示されるときにアクティブになる信号線である。第一のシーケンサーSID0  ８７０上でのSEMONITOR命令の実行の結果として、SEMONITOR命令のシーケンサー識別子パラメータ「1」によって識別される目標シーケンサーSID1  ８６０は、ポーリングその他により「init」イベント・インジケータをモニタリングする。initインジケータがアクティブになったとき、SID1  ８６０は指定されたアドレスに（つまり、スケジューラ・ルーチンの先頭に）ジャンプし、スケジューラ・コードの実行を開始する。図８ではSchedulerルーチンは単に一例として使われているのであって、当業者は、いかなる適切なイベント・ハンドラ・コードが利用されてもよいことを認識するであろう。こうして、SEMONITOR命令の実行は指定されたシーケンサー上における非同期的な制御移行を設定しうる。
【００７９】
図８に示されているSEMONITOR初期化は図８に示されている例に固有であり、限定するものと解釈すべきではない。代替的な実施形態については、一連のイベント型を特定のハンドラ・ルーチンにマッピングするために、図８に示されたSEMONITOR命令と同様のいくつかの初期化命令の組が実行されうる。図８に示されたSEMONITOR命令の実行後、イベント型「init」が分散スケジューラと関連付けられる。
【００８０】
次いで第二の初期化命令、SXFR命令が第一のシーケンサー８７０によって実行される。SXFR命令の実行は、OS隔離されたシーケンサーSID1上での実行の別個のスレッドを初期化するためのイベントを送る。８０２では、OS隔離されたシーケンサーSID1が「Init」シナリオを含んだ信号を検出するとき、OS隔離されたシーケンサーSID1はスレッドSを開始し、分散スケジューラ（たとえば図７の４５０参照）に対応する命令ストリームの実行を開始する。
【００８１】
図８が示す実施形態のSXFR命令は、以下のパラメータを含む：シーケンサー識別子、イベント型および任意的な同期フラグ。シーケンサー識別子（sequencer  identifier）（「SID」）は、SXFR命令の実行の結果として制御が移行される先のシーケンサーを指定する。図８に示した例では、シーケンサー８７０についてのシーケンサー識別子は「SID0」であり、シーケンサー８６０についてのシーケンサー識別子は「SID1」である。
【００８２】
図８に示されるSXFR命令についてのイベント型パラメータは、「init」イベント型を指示する。図に示したSEMONITOR命令の以前の実行の結果として、「init」イベント型は、SXFR命令が実行される時点には分散スケジューラ（図７、４５０）に関連付けられている。したがって、イベント型パラメータは事実上、移行先シーケンサー（すなわち、SID1  ８６０）に対して、シーケンサー８６０が実行を開始するときには分散スケジューラについてのIPアドレスにおいて実行を開始すべきであることを指示する。
【００８３】
図８に示された見本SXFR命令の最後のパラメータは、任意的な待機／不待機フラグである。「不待機（no  wait）」を指定することにより、この命令は本質的に同時並行的なマルチスレッド状況を開始する――第一のシーケンサー８７０は、移行先のシーケンサー８６０からの同期インジケータを待つ必要がなく、SXFR命令の実行を完了したらすぐ自分の命令ストリームの実行を続けることができるのである。
【００８４】
ここで、SXFR命令はシュレッド生成および制御移行命令である。図８は、第一のシーケンサーによるSXFR命令の実行の結果として、シュレッドSが第二のシーケンサー８６０上で分散ハンドラ・ルーチンの実行を開始することを示している。したがって、SXFR命令の実行後、スレッドTおよびシュレッドSは同時並行して実行されうる。
【００８５】
SID0  ８７０上でのスレッドTの実行は、「不待機」フラグのため、７０４でSXFR命令を実行したあと実行を継続しうる。したがって、スレッドTは先に進んで、「mainシュレッド」プログラムのためのシュレッド記述子を生成７０６し、そのような記述子を作業待ち行列システム７０２に入れる。図７との関連で先に論じたように、mainシュレッド記述子は、待ち行列が隔離されたシーケンサーSID1  ８６０に関連付けられているところで作業待ち行列システム７０２（図２）に入れられうる。
【００８６】
次いでスレッドTはそのOS可視スケジューラ７５０を呼び出し、そのスケジューラ７５０によって指令されるように命令の実行７１０に進む。図７との関係で先に議論したように、スレッドTは任意的に、シュレッド記述子を探してもよく（７０９）、したがって７１０ではシュレッド命令を実行してもよい。これは少なくとも、ａ）OS可視スケジューラがOS隔離されたシーケンサー待ち行列から作業を引き出すことを許すような実施形態か、および／または、ｂ）OS可視シーケンサー８７０上でのシュレッド命令のプロキシ実行をサポートするような実施形態についていえる。命令実行７１０の一回または複数回の反復を実行したのち、スレッドTの処理は７１２で終わりうる。
【００８７】
隔離シーケンサー８６０に関しては、図８は、シュレッドSについて実行されるべき動作の系列の少なくとも一つの実施形態を示している。先に論じたように、OS可視シーケンサーSID８７０上で実行されるOS可視スレッドTによって実行される初期化処理７０４の結果として、シーケンサー８６０上でスケジューリング・ループ（すなわち、分散スケジューラ４５０の実行）が開始されうる。
【００８８】
８０４で、SID1  ８６０上で走っているスケジューラ・ルーチン４５０は、シーケンサー８６０による実行のために入手可能な何らかのシュレッド記述子があるかどうかを判別すべく、作業待ち行列システム７０２に問い合わせをする。図８に示されている見本系列については、シーケンサーSID1  ８６０は、ブロック７０６（前述）がすでにSID0  ８７０によって実行されていれば、ブロック８０６でmainシュレッド記述子に遭遇しうる。
【００８９】
記述子がみつかった場合、シーケンサー８６０は、その記述子によって指示されるシュレッドを実行８０６する。シュレッドは、ａ）完了まで、あるいはｂ）譲歩命令に遭遇するまで実行される。
【００９０】
シュレッドの命令が追加的なシュレッド生成命令を含みうることに注意しておくべきである。すなわち、少なくとも一つの実施例については、シュレッドは、それ自身、少なくとも二つの型のシュレッド動作を実行しうる：シュレッド制御動作（シュレッドの生成および終止に関する）と同期動作（譲歩動作のような）である。（少なくとも一つの実施例については、そのような動作は、シュレッド命令ストリームにおいてユーザーが業界標準準拠のプリミティブを使うことによって呼び出されうる。一つのそのような業界標準はたとえばPOSIX（Portable  Operating  System  Interface）である。）図８において、８０６から作業待ち行列システム７０２への破線は、シュレッドの実行８０６の間に追加的なシュレッド記述子（単数または複数）が生成されうること、および該追加的な記述子（単数または複数）が作業待ち行列システム７０２に入れられうることを示している。
【００９１】
たとえば、譲歩プリミティブは、ユーザーによって、シュレッド命令ストリーム中に入れられうる。そのような譲歩プリミティブは、シーケンサーに、シュレッドの制御を譲らせる。そうする際、シーケンサー８６０は、シュレッド命令の残りのための記述子を、シュレッド実行を終止する前に作業待ち行列システム７０２に戻しておくことができる。譲歩プリミティブは、制御移行を実行する前にスタックをスワップする関数を呼び出してもよい。現在のスレッド・コンテキストがシーケンサーのスケジューラに制御を返す前に保存されるようにするのである。
【００９２】
図８は、SID1  ８６０上でのシュレッドSの実行が、終止（termination）命令（終了、譲歩など）が実行されるときに終止またはサスペンドされることを示している。そのような時点では、分散スケジューラ４５０が任意的に、別のシュレッド記述子がないかどうか作業待ち行列システム７０２を調べてもよい。シーケンサーSID1  ８６０によって実行されうる作業を同定するためである。作業待ち行列システム７０２のそのような任意的な反復的調査は、図８では、８０６から８０４への破線矢印によって示されている。
【００９３】
図８に示した例については、SID0  ８７０上で走っているスケジューラ・ルーチン４５０が作業待ち行列システム７０２を調べる前に、SID1  ８６０上で走っているスケジューラ・ルーチン４５０が、「mainシュレッド」ルーチンのためのシュレッド記述子を見出しそうでありうることも可能であることを注意しておくべきである。そのような場合、シーケンサー８６０、８７０のいずれも「mainシュレッド」ルーチンを実行する機能があるとすると、「mainシュレッド」ルーチンは、たとえその記述子がSID0  ８７０によって生成されたとしても、SID1  ８６０によって実行されうる。
【００９４】
以上の図８の議論から、少なくとも一つの実施例については、二つの例示されたシーケンサー８６０、８７０はいずれも「mainシュレッド」ルーチンを実行する機能があることは明らかであろう。したがって、少なくとも一つの実施例については、シーケンサー８６０、８７０は対称的であると想定されうる。しかし、少なくとも一つの他の実施例については、シーケンサー８６０、８７０は完全に対称的ではないが、それでいて各シーケンサー８６０、８７０はmainシュレッド・ルーチンを実行するために十分な機能をもつ。そのような実施形態は、たとえば、mainシュレッド・ルーチンがリング3の機能しか要求せず、シーケンサーSID1  ８６０がリング3機能を有しており、SID0  ８７０がリング3とリング0の両方の機能を有しているような場合に存しうる。そのような実施形態については、図６に示されるように、作業待ち行列システム７０２は第一の待ち行列（たとえばSID0  ８７０によってしか実行できない記述子についての）およびSID0  ８７０またはSID1  ８６０のいずれによっても実行できる記述子についての第二の待ち行列を含みうる。
【００９５】
分散スケジューラ４５０および作業待ち行列システム７０２に関し、少なくとも一つの実施例については、作業待ち行列システム７０２は、クリティカルセクションによって保護されうる。先に論じたように、各隔離シーケンサー８６０は、事実上、分散スケジューラ・ルーチン４５０の一部分について独自のコピーを実行しており、その対応するシーケンサーを走らせるために次の準備ができた命令を処理するため、タスク待ち行列システム７０２の待ち行列の先頭へのアクセスを競ることを試みることができる。シーケンサー上の一つのタスクがミューテックス、条件変数（conditional  variable）またはセマフォのような同期化変数を待つようなことがあれば、対応するクリティカルセクションにはいったのち、そのタスクはスケジュールから外されて、タスク待ち行列の末尾に付けられてもよい。
【００９６】
図８に示した例が与えられているもとでは、本発明の諸実施形態は、OSを使うことなく、OSから隔離されているシーケンサー上での実行の諸スレッドをスケジューリングできることが見て取れる。こうして、ここに開示される技術のおかげで、OSがサポートできるよりも多くのシーケンサーをもつマルチシーケンサー・システムを築き、OSによってサポートされていないマルチシーケンサー・システムのシーケンサー上でスレッドのユーザーレベルのスケジューリングを許容することが可能である。
【００９７】
上記の機構、システムおよび方法の少なくともいくつかの実施例については、分散スケジューラ４５０はイベント駆動の自己スケジューラとして動作する。そこでは、API様のスレッド制御（shred_create、shred_create_affinityなど）またはスレッド同期（shred_yieldなど）プリミティブの結果として生成される、待ち行列に入れられたスケジューリング・イベントに反応して、シュレッドが生成される。スケジューラおよび諸プリミティブは、POSIX準拠APIのような伝統的な業界標準APIと、マルチシーケンサー・システムのハードウェアとの間の中間的な抽象化層を生成するランタイム・ライブラリの一部として実装されうる。マルチシーケンサー・システムのシーケンサーは、少なくとも、ユーザーレベルのシーケンサー算術を実装する正準的なシュレッド命令のセットをサポートする。ライブラリは、上で論じた分散スケジューラ４５０の実施例のようなスケジューラを含みうる。ランタイム・ライブラリが中間的な抽象化レベルのはたらきをしうるので、プログラマは伝統的なスレッドAPI（たとえばPthreads  APIまたはWin32  Threads  APIのような）をシュレッドをサポートするハードウェアで利用できる。ライブラリは、正準的なシュレッド命令を、ユーザーがプログラムするプリミティブに基づいて透明に呼び出す関数を提供しうる。
【００９８】
ここで議論されたスケジューリング機構および技術は、単一コアSMTシステム（たとえば図３の３１０参照）およびマルチコアシステム（たとえば図３の３５０参照）を含め、いかなるマルチシーケンサー・システム上でも実装されうる。そのようなシステムのさらなる議論について、図９との関連で以下に論じる。
【００９９】
図９は、開示されている諸技法を実行する機能のあるコンピューティング・システム９００の少なくとも一つの見本実施形態を示している。コンピューティング・システム９００は少なくとも一つのプロセッサ・コア９０４およびメモリ・システム９４０を含む。メモリ・システム９４０はより大きな、比較的より遅いメモリ記憶９０２とともに、命令キャッシュ９４４および／もしくはデータキャッシュ９４２のような一つもしくは複数のより小さな比較的高速のキャッシュを含みうる。メモリ記憶９０２は、プロセッサ９０４の動作を制御するための命令９１０およびデータ９１２を保存しうる。命令９１０は分散されたスケジューラ・ルーチン４５０の一つまたは複数のコピーを含みうる。
【０１００】
メモリ・システム９４０はメモリの一般化された表現として意図されており、ハード・ドライブ、CD-ROM、ランダムアクセスメモリ（RAM）、動的ランダムアクセスメモリ（DRAM）、静的ランダムアクセスメモリ（SRAM）、フラッシュメモリおよび関係した回路といった多様な形のメモリを含みうる。メモリ・システム９４０は、プロセッサ９０４によって実行されうるデータ信号によって表現される命令９１０および／またはデータ９１２を保存しうる。命令９１０および／またはデータ９１２は、ここに議論された技術のいずれかまたは全部を実行するためのコードおよび／またはデータを含みうる。たとえば、データ９１２は、上で論じたシュレッド記述子を保存できる待ち行列システム７０２を形成する一つまたは複数の待ち行列を含みうる。あるいはまた、命令９１０が、シュレッド記述子を記憶するための待ち行列システム７０２を生成するための命令を含んでいてもよい。
【０１０１】
プロセッサ９０４は、実行コア９３０に命令情報を供給するフロントエンド９２０を含みうる。フェッチされた命令情報は、実行コア９３０による実行を待つべく、キャッシュ２２５にバッファリングされうる。フロントエンド９２０は、その命令情報をプログラム順に実行コア９３０に供給しうる。少なくとも一つの実施例については、フロントエンド９２０は、実行されるべき次の命令を決めるフェッチ／デコード・ユニット３２２を含む。システム９００の少なくとも一つの実施例については、フェッチ／デコード・ユニット３２２は、単一の次命令ポインタおよびフェッチ論理３２０を含みうる。しかしながら、各プロセッサ９０４が複数スレッド・コンテキストをサポートする実施形態では、フェッチ／デコード・ユニット３２２は、サポートされるスレッド・コンテキストそれぞれについて相異なる次命令ポインタおよびフェッチ論理３２０を実装する。マルチプロセッサ環境における追加的な次命令ポインタおよびフェッチ論理３２０が任意的であるという性質は、図９で点線によって表されている。
【０１０２】
ここに記載される諸方法の実施形態は、ハードウェア、ハードウェア・エミュレーション・ソフトウェアもしくはその他のソフトウェア、ファームウェアまたはそのような実装手法の組み合わせにおいて実装されうる。本発明の実施形態は、少なくとも一つのプロセッサ、データ記憶システム（揮発性および不揮発性のメモリおよび／または記憶要素を含む）、少なくとも一つの入力装置ならびに少なくとも一つの出力装置を有するプログラム可能システムのために実装されうる。本出願の目的のためには、処理システムは、たとえばデジタル信号プロセッサ（DSP）、マイクロコントローラ、特定用途向け集積回路（ASIC）またはマイクロプロセッサといったプロセッサをもつ任意のシステムを含む。
【０１０３】
プログラムは、汎用または特殊目的プログラム可能処理システムによって読み取り可能な記憶媒体またはデバイス（たとえばハードディスク・ドライブ、フロッピー（登録商標）ディスク・ドライブ、読み出し専用メモリ（ROM）、CD-ROMデバイス、フラッシュメモリ・デバイス、デジタル多用途ディスク（DVD）またはその他の記憶デバイス）上に記憶されうる。処理システム中のプロセッサにとってアクセス可能な命令が、該処理システムによって前記記憶媒体またはデバイスが読まれたときに、ここに記載される手順を実行するために、該処理システムを構成設定し、動作させることを提供する。本発明の実施形態は、処理システムとともに使用するよう構成された機械可読記憶媒体として実装されると考えられてもよい。ここで、そのように構成された記憶媒体は、処理システムをして、ここに記載される機能を実行するために特定かつ所定の仕方で動作させる。
【０１０４】
見本システム９００は、インテル社から入手可能なペンティアム（登録商標）、ペンティアム（登録商標）プロ、ペンティアム（登録商標）II、ペンティアム（登録商標）III、ペンティアム（登録商標）4およびアイテニアム（登録商標）およびアイテニアム（登録商標）2といったマイクロプロセッサに基づいた処理システムを表す。ただし、その他のシステム（他のマイクロプロセッサをもつパーソナル・コンピュータ（PC）、エンジニアリング・ワークステーション、携帯情報端末およびその他のハンドヘルド装置、セットトップボックスなどを含む）を使ってもよい。ある実施例については、見本システムはマイクロソフト社から入手可能なウィンドウズ（登録商標）オペレーティング・システムのあるバージョンを実行してもよい。ただし、他のオペレーティング・システムおよびグラフィカルユーザーインターフェースなどを使用してもよい。
【０１０５】
本発明の具体的な実施形態について図示し、記載してきたが、付属の請求項の範囲から外れることなく変更および修正をなすことができることは当業者には明らかであろう。たとえば、作業待ち行列システム７０２は、複数のシーケンサー型によって競られる単一の待ち行列を含んでいてもよい。そのような実施形態については、各シュレッド記述子に資源要求が明示的に含められる。分散されたスケジューラの各シーケンサーの部分は、シュレッドの記述子がシーケンサーによる実行のために作業待ち行列から取り出される前に、そのシーケンサーがそのシュレッドを実行する機能があるかどうかを確かめるための検査を行う。
【０１０６】
もう一つの代替的な実施形態については、作業待ち行列システム７０２においてハイブリッド・アプローチが実装されうる。そのようなハイブリッド・アプローチについては、作業待ち行列システム７０２は複数の待ち行列を含む。それでも、該複数の待ち行列のうち一つまたは複数は複数のシーケンサー型に対応する。そのようなハイブリッド実施形態のためには、二つ以上のシーケンサー型に関連付けられたいかなる待ち行列についても、各シュレッド記述子に明示的な資源指示が含められる。
【０１０７】
上で論じた分散されたスケジューラ・ルーチンは、ラウンドロビン・スケジューリングのアプローチを使ってシュレッド記述子の実行をスケジューリングしうる。しかし、少なくとも一つの代替的な実施形態については、上で論じた分散スケジューラおよび作業待ち行列システムは、優先度に基づいたスケジューリング方式をサポートしうる。また、少なくとも一つの代替的な実施形態については、好まれるシーケンサーによってタスクが実行されるよう、複数待ち行列の待ち行列システム実施形態のための待ち行列選好がユーザーによって、あるいはランタイム・ライブラリによって設定されることができる。たとえば、ある特定のシーケンサーによって譲歩動作前に実行されるシュレッドが、そのシュレッドの残りの命令が実行されるときにその同じ特定のシーケンサーに送り返されることができる。
【０１０８】
作業待ち行列システムへのシュレッド記述子の発送に関し、先に図７との関連で、シュレッド記述子の割り当ては、シュレッドが生成される時点でどの待ち行列に割り当てられるべきかを定義するためにユーザーが特定のパラメータまたは特定の「親和（affinity）」プリミティブを使用することによって静的に明示的に制御されうることを述べた。
【０１０９】
少なくとも一つの代替的な実施形態では、そのような静的な割り当て手法の代わりに、あるいは追加として、動的な割り当てを利用しうる。動的な割り当ては、ミューテックスのようなユーザーレベルの同期オブジェクトを通じて実装されうる。そのようなミューテックスは、シュレッドが、自ら動的に、新生シュレッド（spawnee  shred）を作業待ち行列システムの特定の待ち行列にスケジューリングすることを許容しうる。あるいはまた、動的な割り当ては、分散スケジューラが待ち行列の挙動を観察し、どの待ち行列が記述子を受け取るべきかを動的に選択するよう実装されてもよい。さらにまた、動的な割り当ては、プログラマが、「ロック」および「ロック解除」プリミティブといった同期プリミティブを使うことを通じて実行されてもよい。そのようなプリミティブはOSのミューテックス構造体を利用しうる。ロック・プリミティブの実際に際し、現在のシーケンサーは、譲歩動作を実行し、現在のシュレッドの記述子をそのミューテックスに対応する待ち行列に入れることができる。
【０１１０】
このように、当業者はより広い諸側面における本発明から外れることなく、変更および修正がなし得ることを認識するであろう。付属の請求項の範囲内には、本発明の真の範囲内にはいるそのようなすべての変更および修正が包含される。
【０１１１】
可能な態様のいくつかを記載しておく。
〔態様１〕
同時並行シュレッドのユーザーレベルのスケジューリングのための方法であって：
ユーザー生成されたスレッド・プリミティブを実行する段階であって、スレッド制御命令を生成するライブラリ関数を呼び出すことをさらに含む段階と；
前記スレッド・プリミティブに応じて、スレッドを記述する作業記述子を生成する段階と；
前記作業記述子を待ち行列システム内に記憶させる段階と；
オペレーティング・システムの介入なしに、前記スレッドのOS隔離シーケンサー上での実行をスケジューリングする段階、
とを有する方法。
〔態様２〕
ユーザーレベルの同時並行マルチスレッド利用を実行するよう前記シーケンサーを初期化する段階をさらに有する、
態様１記載の方法。
〔態様３〕
前記初期化する段階がさらに、ユーザーレベルの分散されたスケジューラの、前記シーケンサー上での実行をトリガーする段階を有する、
態様２記載の方法。
〔態様４〕
前記待ち行列システムが、第一のシーケンサー型に関連付けられた第一の待ち行列と、第二のシーケンサー型に関連付けられた第二の待ち行列とを含む、
態様１記載の方法。
〔態様５〕
前記第一および第二のシーケンサーが、コンピューティング上の少なくとも一つの基準に関して非対称的である、
態様４記載の方法。
〔態様６〕
前記コンピューティング上の基準が機能上の基準である、
態様５記載の方法。
〔態様７〕
前記コンピューティング上の基準が電力消費基準である、
態様５記載の方法。
〔態様８〕
前記機能上の基準が、リング0動作を実行する能力である、
態様６記載の方法。
〔態様９〕
前記記憶させる段階が、前記作業記述子を、ユーザーが提供したヒントに基づいて前記第一の待ち行列に記憶させることをさらに含む；
態様４記載の方法。
〔態様１０〕
前記スレッド・プリミティブが、シュレッド生成プリミティブである、
態様１記載の方法。
〔態様１１〕
前記スレッド・プリミティブが、シュレッド同期プリミティブである、
態様１記載の方法。
〔態様１２〕
前記スレッド・プリミティブが、業界標準準拠のアプリケーション・プログラマ・インターフェースの一部である、
態様１記載の方法。
〔態様１３〕
分散されたオペレーティング・システム独立なスケジューラ・ルーチンの第一の部分を含む第一のスレッド実行ユニットと；
分散されたオペレーティング・システム独立なスケジューラ・ルーチンの第二の部分を含む第二のスレッド実行ユニットとを有する装置であって；
前記第一および第二のスレッド実行ユニットが同時並行のマルチスレッドを利用した実行の機能をもち；
前記第一および第二の部分がさらに、スレッドを記述する作業記述子を求めて競るために作業待ち行列に問い合わせし；
前記分散されたスケジューラ・ルーチンが、前記競りに基づいて、オペレーティング・システムの介入なしに、前記スレッドを、前記スレッド実行ユニットのうちの選択されたものでの実行のためにスケジューリングする、装置。
〔態様１４〕
前記スレッド実行ユニットの少なくとも一つはオペレーティング・システムに可視であり、前記スレッド実行ユニットの少なくとも別の一つはオペレーティング・システムに可視ではない、
態様１３記載の装置。
〔態様１５〕
当該装置が単一コアのプロセッサであり；
前記第一および第二の実行ユニットが論理的なプロセッサである、
態様１３記載の装置。
〔態様１６〕
当該装置がマルチコアのプロセッサであり；
前記第一および第二の実行ユニットがプロセッサ・コアである、
態様１３記載の装置。
〔態様１７〕
前記実行ユニットが機能的に対称的である、
態様１３記載の装置。
〔態様１８〕
前記待ち行列システムが、前記実行ユニットの全部に適用可能な作業記述子を保持するための単一の待ち行列を含む、
態様１７記載の装置。
〔態様１９〕
前記実行ユニットの少なくとも一つが、他の実行ユニットの一つまたは複数とコンピューティング面で非対称的である、
態様１３記載の装置。
〔態様２０〕
前記待ち行列システムが、前記少なくとも一つの非対称的である実行ユニットのための作業記述子を保持するための第一の待ち行列を含み、前記一つまたは複数の他の実行ユニットのための記述子を保持するための第二の待ち行列をも含む、
態様１９記載の装置。
〔態様２１〕
メモリ・システムと；
第一のシーケンサー型の第一のシーケンサーと；
第二のシーケンサー型の第二のシーケンサーと；
前記メモリ・システムに保存されているソフトウェア・ライブラリであって、作業待ち行列を生成するための一つまたは複数の命令を含むライブラリ、
とを有するマルチシーケンサー・マルチスレッド・システムであって：
前記ライブラリがさらに、前記作業待ち行列からの作業をシーケンサー上での実行のために、ユーザー指令によりスケジューリングすることを実行する分散されたスケジューラを含む、システム。
〔態様２２〕
前記分散されたスケジューラが、前記第一および第二のシーケンサーのためのスケジューリング・ループを実行する、
態様２１記載のシステム。
〔態様２３〕
前記作業待ち行列が、ペンディングのソフトウェア・スレッドを記述する一つまたは複数のレコードを保持する、
態様２１記載のシステム。
〔態様２４〕
前記一つまたは複数のレコードが、それぞれ対応するペンディングのソフトウェア・スレッドの開始アドレスを含む、
態様２３記載のシステム。
〔態様２５〕
前記一つまたは複数のレコードが、それぞれ対応するペンディングのソフトウェア・スレッドについてのスタック・ポインタを含む、
態様２３記載のシステム。
〔態様２６〕
前記分散されたスケジューラがさらに、前記作業待ち行列からの作業をシーケンサー上での実行のために、ユーザー指令によりスケジューリングすることを、前記シーケンサーが同時並行してその関連付けられた作業を実行するように実行する、
態様２３記載のシステム。
〔態様２７〕
前記ライブラリがさらに、それぞれ関連付けられたユーザー生成されたプリミティブに応じてシュレッド命令を生成する一つまたは複数の関数を含んでおり、前記プリミティブは一般的に知られたアプリケーション・プログラマ・インターフェース規格に準拠するものである、
態様２３記載の方法。
〔態様２８〕
マルチスレッド・プロセッサにおいて、複数のシーケンサーの間でソフトウェア・シュレッドの実行をスケジューリングする方法であって：
ユーザー生成されたスレッド命令に応じて、スレッドを記述するスレッド記述子を生成する段階と；
前記スレッド記述子を待ち行列に入れる段階と；
それぞれが相異なるシーケンサーに関連付けられた複数のスケジューラ・ルーチンを実行する段階であって、前記複数のシーケンサーがオペレーティング・システムに基づくスレッド・スケジューラに従属せず、前記スケジューラ・ルーチンのそれぞれが前記待ち行列内の前記記述子を求めて競るものである、段階と；
前記スレッドを、前記シーケンサーの一つの上での実行のためにスケジューリングする段階、
とを有する方法。
〔態様２９〕
前記ユーザー生成されたスレッド命令が、アプリケーション・プログラマ・インターフェースに含まれているプリミティブである、
態様２８記載の方法。
〔態様３０〕
前記アプリケーション・プログラマ・インターフェースが業界標準に準拠している、
態様２８記載の方法。
〔態様３１〕
複数の機械アクセス可能命令を有する機械アクセス可能媒体を有する物品であって、前記命令はプロセッサによって実行され、前記命令は：
ユーザー生成されたスレッド・プリミティブを実行する動作であって、スレッド制御命令を生成するライブラリ関数を呼び出すことをさらに含む動作と；
前記スレッド・プリミティブに応じて、スレッドを記述する作業記述子を生成する動作と；
前記作業記述子を待ち行列システム内に記憶させる動作と；
オペレーティング・システムの介入なしに、前記スレッドのシーケンサー上での実行をスケジューリングする動作、
とを提供する物品。
〔態様３２〕
プロセッサによって実行されたときに：
ユーザーレベルの同時並行マルチスレッド利用を実行するよう前記シーケンサーを初期化する動作、
を提供する機械アクセス可能命令をさらに有する、態様３１記載の物品。
〔態様３３〕
前記初期化する動作を提供する命令がさらに、プロセッサによって実行されたときに、ユーザーレベルの分散されたスケジューラの、前記シーケンサー上での実行をトリガーする動作を提供する命令をさらに有する、
態様３２記載の物品。
〔態様３４〕
前記待ち行列システムが、第一のシーケンサー型に関連付けられた第一の待ち行列と、第二のシーケンサー型に関連付けられた第二の待ち行列とを含む、
態様３１記載の物品。
〔態様３５〕
前記第一および第二のシーケンサーが、コンピューティング上の少なくとも一つの基準に関して非対称的である、
態様３４記載の物品。
〔態様３６〕
前記コンピューティング上の基準が機能上の基準である、
態様３５記載の物品。
〔態様３７〕
前記コンピューティング上の基準が電力消費基準である、
態様３５記載の物品。
〔態様３８〕
前記機能上の基準が、リング0動作を実行する能力である、
態様３６記載の物品。
〔態様３９〕
前記記憶させる動作を提供する命令が、プロセッサによって実行されたときに、前記作業記述子を、ユーザーが提供したヒントに基づいて前記第一の待ち行列に記憶させる命令をさらに有する；
態様３４記載の物品。
〔態様４０〕
前記スレッド・プリミティブが、シュレッド生成プリミティブである、
態様３１記載の物品。
〔態様４１〕
前記スレッド・プリミティブが、シュレッド同期プリミティブである、
態様３１記載の物品。
〔態様４２〕
前記スレッド・プリミティブが、業界標準準拠のアプリケーション・プログラマ・インターフェースの一部である、
態様３１記載の物品。
【図１】
2011076639.tif 000003
【図２】
2011076639.tif 000004
【図３】
2011076639.tif 000005
【図４】
2011076639.tif 000006
【図５】
2011076639.tif 000007
【図６】
2011076639.tif 000008
【図７】
2011076639.tif 000009
【図８】
2011076639.tif 000010
【図９】
2011076639.tif 000011