(57)【要約】【課題】非均一メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムでタスクをディスパッチする方法および装置【解決手段】非均一メモリ・アクセス・コンピュータ・システム用のディスパッチャは、どのＣＰＵ（２０１〜２０４）にも関連づけられていない共通実行可能待ち行列（３０５）からスレッドをディスパッチするが、メモリ・アクセス時間がより短いＣＰＵへのスレッドのディスパッチを優先する。好ましくは、このシステムは、それぞれがローカル・メモリ（２０５）および１つまたは複数のＣＰＵを備える、複数の個別ノード（１０１〜１０４）を含む。システム・メイン・メモリは、ローカル・メモリの合併を含む分散メモリである。それぞれの優先ＣＰＵおよび優先ノードは、各スレッドに関連づけることができる。ＣＰＵが使用可能になると、ディスパッチャは、その使用可能なＣＰＵと同じノード中に優先ＣＰＵを持つスレッドを、異なるノード中に優先ＣＰＵを持つスレッドに、少なくとも相対的に多少優先させる（７１４〜７１７；８０１〜８０４）。この優先は相対的なものであり、枯渇その他の問題を回避するためにそのディスパッチがその優先を指定変更するのを妨げない。【選択図】図２
2005508545.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システムで中央処理装置（ＣＰＵ）にスレッドをディスパッチする方法であって、前記コンピュータ・システムは複数のＣＰＵ（２０１〜２０４）および複数の個別サブセットに分割可能なメモリ（２１０）を備え、
（ａ）目標ＣＰＵを識別するステップと、
（ｂ）どのＣＰＵにもＣＰＵグループにも関連づけられていない共通実行可能待ち行列（３０５）上で待機する、前記目標ＣＰＵ上で実行するのに適した１組のスレッドを識別するステップ（７０１）と、
（ｃ）前記１組のスレッドのそれぞれのスレッドごとに前記複数の個別メモリ・サブセットのうち少なくとも１つの目標サブセットを識別するステップであって、各目標サブセットは、前記目標ＣＰＵによる前記目標サブセット内の位置へのメモリ・アクセスのためのそれぞれの待ち時間を持ち、前記メモリ・アクセスのためのそれぞれの待ち時間はすべて同一ではないステップと、
（ｄ）前記目標ＣＰＵ上で実行するために前記１組のスレッドから１つのスレッドを選択するステップ（７１０〜７２５）であって、少なくとも一部は各目標サブセットの前記それぞれの待ち時間に基づくものであるステップと
を含む方法。
【請求項２】
前記複数のＣＰＵの各ＣＰＵが前記複数の個別メモリ・サブセットのそれぞれのサブセットに関連づけられ、前記複数の個別メモリ・サブセットのうち少なくとも１つの目標サブセットを識別する前記ステップが、前記１組のスレッドの各スレッドを実行するためにそれぞれの優先ＣＰＵを指定することを含み、前記複数の個別メモリ・サブセットの前記目標サブセットが前記優先ＣＰＵに関連づけられたメモリ・サブセットである、請求項１に記載のスレッドをディスパッチする方法。
【請求項３】
複数のＣＰＵが前記複数の個別メモリ・サブセットのそれぞれのサブセットごとに関連づけられた、請求項１ないし２のいずれかに記載のスレッドをディスパッチする方法。
【請求項４】
実行するために前記１組のスレッドから１つのスレッドを選択する前記ステップが、そのための前記指定された優先ＣＰＵが前記目標ＣＰＵであるスレッドに第１の相対的優先度を割り振ること（７１４〜７１５）、そのための前記指定された優先ＣＰＵが前記目標ＣＰＵと同じメモリ・サブセットに関連づけられているスレッドに第２の相対的優先度を割り振ること（７１６〜７１７）、およびそのための前記指定された優先ＣＰＵが前記目標ＣＰＵと同じメモリ・サブセットに関連づけられていないスレッドに第３の相対的優先度を割り振ることを含み、前記第１の相対的優先度は前記第２の相対的優先度より大きく、前記第２の相対的優先度は前記第３の相対的優先度より大きい、請求項１ないし２のいずれかに記載のスレッドをディスパッチする方法。
【請求項５】
前記コンピュータ・システムが複数の個別ノード（１０１〜１０４）を含み、各ノードは少なくとも１つのＣＰＵ、および前記複数の個別メモリ・サブセットのそれぞれのサブセットを含み、それぞれのスレッドごとに前記複数の個別メモリ・サブセットのうち少なくとも１つの目標サブセットを識別する前記ステップが、それぞれのスレッドごとに少なくとも１つの目標ノードを識別すること（６０５）を含む、請求項１ないし４のいずれかに記載のスレッドをディスパッチする方法。
【請求項６】
それぞれのスレッドごとに少なくとも１つの目標ノードを識別する前記ステップが、前記１組のスレッドの各スレッドを実行するためにそれぞれの優先ＣＰＵを指定するステップ（６１５）を含み、前記目標ノードが、前記優先ＣＰＵが位置するノードである、請求項１ないし５のいずれかに記載のスレッドをディスパッチする方法。
【請求項７】
前記１組のスレッドの各スレッドを実行するためにそれぞれの優先ＣＰＵを指定する前記ステップが、前記スレッドが生成されたとき（６１０）に実施される、請求項２ないし６のいずれかに記載のスレッドをディスパッチする方法。
【請求項８】
請求項１ないし７のいずれかの方法を実施するための命令と、
前記命令を記録するための信号搬送媒体と
を含むコンピュータ・プログラム製品。
【請求項９】
各ノードが１つまたは複数の中央処理装置（ＣＰＵ）（２０１〜２０４）およびローカル・メモリ（２１０）を含む複数の個別ノード（１０１〜１０４）であって、前記複数の個別ノード中のすべてのローカル・メモリのセットが、前記コンピュータ・システムの分散メイン・メモリを含む複数の個別ノードと、
前記複数のノード間のデータ通信を提供するインターフェイス・ネットワーク（１０５）と、
どの個々のＣＰＵにもＣＰＵグループにも関連づけられていない、前記コンピュータ・システム上で実行可能な状態の複数のスレッドを保持する共通実行可能待ち行列（３０５）と、
前記ＣＰＵ上で実行するために前記共通実行可能待ち行列からスレッドをディスパッチするスレッド・ディスパッチャ（３０４）であって、スレッドをディスパッチするときにＣＰＵのノード位置を考慮すると共に、そのノードのローカル・メモリにスレッドが必要とするデータの相対的に大きい部分を含む可能性の高いノード中のＣＰＵへのスレッドのディスパッチを優先するスレッド・ディスパッチャと
を含む非均一メモリ・アクセス・コンピュータ・システム。
【請求項１０】
ページインされたデータを記憶するために前記分散メイン・メモリ中の位置を選択するページャ（３０３）であって、ページ不在を生じさせたスレッド、および前記ページ不在を生じさせた前記スレッドを実行していたＣＰＵのうち少なくとも１つによって決定されたノードのローカル・メモリにページインされたデータを記憶するページャをさらに含む、請求項９に記載の非均一メモリ・アクセス・コンピュータ・システム。
【請求項１１】
各ノードが複数のＣＰＵを含む、請求項９ないし１０のいずれかに記載の非均一メモリ・アクセス・コンピュータ・システム。
【請求項１２】
前記ディスパッチャが、目標ＣＰＵ上で実行するために複数の実行可能なスレッドの中から１つのスレッドを選択する、請求項９ないし１１のいずれかに記載の非均一メモリ・アクセス・コンピュータ・システム。
【請求項１３】
前記ディスパッチャが、実行可能なスレッドを実行するのに適した複数のＣＰＵの中から１つのＣＰＵを選択する、請求項９ないし１１のいずれかに記載の非均一メモリ・アクセス・コンピュータ・システム。
【請求項１４】
それぞれの優先ノードが、そのスレッドが生成された時点で少なくともいくつかのスレッドに関連づけられており、前記スレッド・ディスパッチャが、そのスレッドの優先ノード中のＣＰＵへのスレッドのディスパッチを優先する、請求項９ないし１３のいずれかに記載の非均一メモリ・アクセス・コンピュータ・システム。
【請求項１５】
複数の中央処理装置（ＣＰＵ）（２０１〜２０４）を備える非均一メモリ・アクセス・コンピュータ・システムのためのスレッド・ディスパッチ機構であって、
どのＣＰＵにもＣＰＵセットにも関連づけられていない共通実行可能待ち行列中の複数のスレッドの各スレッドに関して、前記スレッドによって必要とされるデータへのメモリ・アクセス時間がより短い可能性の高い、それぞれが少なくとも１つのＣＰＵを含むＣＰＵセットを判定する手段と、
スレッドおよび前記スレッドを実行するためのＣＰＵを優先的に選択する、スレッドおよび前記スレッドを実行するためのＣＰＵを選択する手段（６１０〜６１５）であって、前記スレッドを実行するための前記ＣＰＵは、前記スレッドによって必要とされるデータへのメモリ・アクセス時間がより短い可能性の高い前記ＣＰＵセットのメンバである手段と
を含むスレッド・ディスパッチ機構。
【請求項１６】
前記非均一メモリ・アクセス・コンピュータ・システムが複数の個別ノード（１０１〜１０４）を含み、各ノードが少なくとも１つのＣＰＵおよび前記複数の個別メモリ・サブセットのそれぞれのサブセット（２１０）を含み、各スレッドに関して、前記スレッドによって必要とされるデータへのメモリ・アクセスがより短い可能性の高いＣＰＵセットを判定する前記手段が、各スレッドに関して、前記それぞれのスレッドによって必要とされるデータを含む可能性の高いノード中のＣＰＵセットを識別する手段を含む、請求項１５に記載のスレッド・ディスパッチ機構。
【請求項１７】
前記選択する手段が、前記スレッドが生成されたときに前記スレッドを優先的に選択する、請求項１５ないし１６のいずれかに記載のスレッド・ディスパッチ機構。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチタスク・コンピュータ・システムに関し、詳細には、複数の中央処理装置および非均一メモリ・アクセスを備えるシステムでのタスクまたはスレッドのディスパッチに関する。
【背景技術】
【０００２】
現代のコンピュータ・システムは、通常、中央処理装置（ＣＰＵ）、および通信バスやメモリなど、情報を記憶し、取り出し、転送するのに必要な支援ハードウェアを含む。また、入出力制御装置や記憶制御装置、ならびにキーボード、モニタ、テープ・ドライブ、ディスク・ドライブ、ネットワークに結合された通信線といった、それらに接続された装置など、外部とやりとりするのに必要なハードウェアも含む。ＣＰＵはシステムの核心である。それは、コンピュータ・プログラムを含む命令を実行し、他のシステム構成要素の動作を指図する。
【０００３】
コンピュータ・ハードウェアの観点からいえば、大部分のシステムは基本的に同じ方式で動作する。プロセッサは、算術、論理比較や、データのある場所から別の場所への移動など、非常に単純な演算の小規模のセットを実施することができる。しかし、各演算は非常に敏速に行われる。大量のこうした単純な演算を実施するようコンピュータに指図するプログラムは、コンピュータが何か高度なことを行っているという幻想を与える。ユーザがコンピュータ・システムの新規の、または改善された機能であると認めるものは、本質的に、同じ非常に単純な演算のセットを実施することによって、しかしそれをはるかに高速に実施することによって可能になる。したがって、コンピュータ・システムを改善し続けるには、これらのシステムを絶えずより高速にすることが必要とされる。
【０００４】
コンピュータ・システムの全体的速度（スループットとも呼ばれる）は、おおよそ、単位時間当たりに実施される演算数として測定することができる。概念的には、システム速度へのすべての可能な改善のうち最も単純なものは、種々の構成要素のクロック速度、具体的にはプロセッサのクロック速度を上げることである。例えば、あらゆるものが２倍の速度で動作するが、速度以外は全く同様に機能する場合、システムは所与のタスクを半分の時間で実施することになる。初期のコンピュータ・プロセッサは多くの個別部品から構築されていたので、部品サイズを縮小し、部品数を削減し、遂にはプロセッサ全体を単一チップ上に集積回路としてパッケージすることにより大幅な速度の向上が可能であった。サイズの縮小により、プロセッサのクロック速度の増大、したがって、システム速度の増大が可能になった。
【０００５】
集積回路から大幅な速度の向上が得られたが、より高速のコンピュータ・システムは引き続き求められている。ハードウェア設計者は、より大規模な集積（すなわち単一チップにパックする回路数を増やすこと）、回路サイズのさらなる縮小、および他の様々な技術によって、より一層の速度向上の実現を可能にしてきた。しかし、物理サイズの縮小を無限に続けることはできず、プロセッサのクロック速度を増大し続ける能力には限界があることを設計者は理解している。したがって、コンピュータ・システムのスループットのさらなる向上のための他の手法に関心が向けられている。
【０００６】
クロック速度を変更せずに、複数のプロセッサを使用することによってシステム・スループットを向上させることができる。この手法が実際的なのは、集積回路チップ上にパッケージされた個々のプロセッサのコストが小さいためである。しかし、システムのスループットは、プロセッサを１つから２つにすることによって単純に２倍にはならない。システムに複数のプロセッサを導入すると、多くのアーキテクチャ上の問題が生じる。例えば、複数のプロセッサは、通常、（各プロセッサはそれ自体のキャッシュを持つことはできるが）同じメイン・メモリを共用することになる。したがって、メモリ・アクセスの競合を回避し、キャッシュ中のデータの余分なコピーが一貫して追跡されることを保証する機構を案出する必要がある。さらに、各プロセッサは、記憶装置、入出力、メモリ、および特に、様々な構成要素を接続する通信バスなど、システムのその他の構成要素にその他の要求を出す。より多くのプロセッサが導入されるほど、こうしたアーキテクチャ上の問題はますます複雑になり、拡張がより困難になって、プロセッサが、別のプロセッサによって使用されている何らかのリソースを待つのに多大な時間を費やすことになる可能性がより高くなる。
【０００７】
上記その他の問題はすべてシステム設計者には知られており、それらにどうにかして対応している。完全な解決策はないが、この分野での改善は続けられている。
【０００８】
近年支持を得ているアーキテクチャ上の一手法が、プロセッサおよび関連するメモリの個別ノードを備えるコンピュータ・システムの設計であり、分散共用メモリ・コンピュータ・システムまたは非均一メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムとも呼ばれている。従来の対称的なマルチ・プロセッサ・システムでは、メイン・メモリは、システム中のすべてのＣＰＵから対等にアクセスすることのできる、単一の大規模なデータ記憶エンティティとして設計される。ＣＰＵの数が増えるにつれて、バス、およびそうしたメイン・メモリへのアクセス機構でのボトルネックがより大きくなる。ＮＵＭＡシステムは、メイン・メモリを、その各々がそれぞれのＣＰＵ、より一般的にはそれぞれのＣＰＵグループに物理的に関連づけられた個別のサブセットに分割することによってこの問題に対処する。メモリおよび関連するＣＰＵその他のハードウェアのサブセットは「ノード」と呼ばれることもある。ノードは、通常、ＣＰＵからそのノード内のローカル・メモリへの直接アクセスを提供する内部メモリ・バスを備える。ノード境界にまたがってメモリにアクセスするために、より低速な間接機構が存在する。したがって、どのＣＰＵも任意のメモリ位置にアクセスできるが、ＣＰＵは、そのノードの外部のアドレスよりも、それ自体のノード内のアドレスの方がより高速にアクセスすることができる（そのため、「非均一メモリ・アクセス」という用語で呼ばれる）。ノードの内部メモリ・バス上の装置数を限定することにより、多数のＣＰＵを備えるシステムであっても、それらのＣＰＵの大部分は異なるノードにあることになるので、バス調停機構およびバス・トラフィックを処理可能なレベルに保持することができる。ハードウェアの関連からいえば、これは、ＮＵＭＡシステム・アーキテクチャが拡張性増大の利点をもつ可能性があることを意味する。
【０００９】
ＮＵＭＡシステムはノード間アクセスを提供し、それによって、各位置が固有のアドレスを有する単一の論理メイン・メモリを備える。しかし、ノード間アクセスは比較的低速で、ある種のシステム・リソースの負担になる。ＮＵＭＡシステムが効率よく機能するためには、一般に、ＣＰＵが必要とするデータを同じノードの実メモリに記憶する必要がある。過度に厳格な制約条件を課すことなく、これがいつもそうなることを保障するのは実際的ではない。ノード間メモリ・アクセスの必要を少なくするメモリ割り振りの機構が望ましい。
【００１０】
マルチタスク・システム・コンピュータ・システムでは、オペレーティング・システムは、通常、ある種のシステム・リソースの割り振り、具体的には、タスク（またはスレッド）のＣＰＵへのディスパッチおよびメモリの割り振りを扱う。そうしたシステムでは、複数のスレッドが同時にアクティブになる。普通、アクティブなスレッドの数は、システムのＣＰＵの数を超える。所与のスレッドは、通常、ＣＰＵで若干のサイクル数の間実行され、次いで、それが終了しなくても、一時的に停止されて待ち行列に入れられ、後刻続行される。スレッドは、それが制限時間に達したため、より優先度の高いスレッドにとって代わられたため、記憶アクセスやロック解除など何らかの待ち時間イベントを待つ必要があるため、あるいは他の理由で停止されることがある。最初のスレッドが待機している間に別のスレッドを実行させることによって、ＣＰＵリソースがより完全に利用される。ＣＰＵが上記その他の理由でスレッドを実行できるようになると、オペレーティング・システム内のディスパッチャは、通常、複数の待機中スレッドのうちのどれを実行するためにその使用可能なＣＰＵにディスパッチするか決定する。
【００１１】
従来のディスパッチャは、普通、すべてのＣＰＵからメモリに対等にアクセス可能な、対称的マルチプロセッサ・コンピュータ・システム用に設計されるが、タスク・ディスパッチ時に非均一メモリ・アクセスの影響を最適に考慮することができない、例えば、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ  ２０００（登録商標）オペレーティング・システムで使用されるディスパッチャでは、事前に割り当てられた優先度、待ち行列での時間の長さ、同じＣＰＵ上で最後に実行されたスレッドかどうか、そのＣＰＵがそのスレッドの優先プロセッサに指定されているかどうか、および他の要因を含む様々な考慮事項に従って、スレッドがディスパッチのために選択される。これらの要因は、ＣＰＵ利用を最適化するためのものであり、それはもちろん、通常は望ましいものである。しかし、ＣＰＵのノード位置はこのディスパッチャによって考慮されず、ＣＰＵを高度に利用することはできても、不必要に多いノード間メモリ・アクセス数が原因でシステム・スループットが損なわれることがある。
【００１２】
一部のディスパッチャは、スレッドまたはタスクのＣＰＵへの割り振りの際に厳格な制約条件を強制して、個々のスレッドが常に同じＣＰＵ上、または同じノード内で実行されるようにすることができる。システム・リソースを個別サブセットに分割し、それぞれのサブセットにプロセスを割り当てるコンピュータ・システムの論理区画化も同様の効果を実現することができる。場合によっては、これらの効果が意図的に得られることがある（例えば、あるプロセス・グループが、他のプロセスからの妨害を受けずに一定量のリソースを保証される）。しかし、これは、一部のＣＰＵの過小利用または過剰利用されたＣＰＵでのボトルネックあるいはその両方を生じることがある。
【００１３】
ＮＵＭＡプラットフォーム用に設計された１つの公知のオペレーティング・システムが、シーケント・コンピュータ（Sequent Computers）によるＰＴＸオペレーティング・システムである。ＰＴＸは各ＣＰＵに１つずつ、複数の実行待ち行列を提供し、任意のＣＰＵグループに追加の実行待ち行列を定義できる機能をユーザに提供する。プロセスが開始されると、それは実行待ち行列の１つに割り当てられ、実行を待つ間、そのプロセスによって生成されるすべてのスレッドがその実行待ち行列に配置される。その後このオペレーティング・システムは、そのプロセスのスレッドをその割り当てられた実行待ち行列の１つまたは複数のＣＰＵに優先的にディスパッチし、優先度が多少低い場合には、その割り当てられた実行待ち行列の１つまたは複数のＣＰＵと同じシステム・ノード内のＣＰＵにディスパッチする。このオペレーティング・システムは、進行に従って、各ＣＰＵごとのＣＰＵ利用度および各ノードごとのメモリ利用度を監視する機能をさらに含む。個々のノードでのＣＰＵ利用度またはメモリ利用度あるいはその両方が十分に高い場合は、オペレーティング・システムは、その１つまたは複数の優先ＣＰＵを含むノード以外のノードにスレッドをディスパッチすることもできる。このように、ＰＴＸはＮＵＭＡアーキテクチャをうまく利用するが、リソース利用の大きな不均衡を生じる可能性のあるスレッド・ディスパッチ時の厳格な制約条件を回避する。
【非特許文献１】
ＩＥＥＥ標準１５９６−１９９２（１９９３年８月３日）
【非特許文献２】
「ポイントツーポイント・リングを用いた相互接続トポロジ（InterconnectTopologies with Point-To-Point Rings）」、ロス・イー・ジョンソン（Ross E. Johnson）およびジェームズ・イー・グッドマン（JamesE. Goodman）、１９９１年１２月、コンピュータ・サイエンス・テクニカル・レポート＃１０５８（Computer Sciences TechnicalReport #1058）、ウィスコンシン−マディソン大学（University of Wisconsin-Madison）
【発明の開示】
【発明が解決しようとする課題】
【００１４】
スレッドをディスパッチする際に様々なＣＰＵのノード位置を考慮に入れ、したがって、ノード間メモリ・アクセスの回数を減らすというＰＴＸの著しい利点を持つが、より単純なオペレーティング・システム、具体的には、複数の実行待ち行列およびＣＰＵ／メモリ利用度監視をサポートしないオペレーティング・システムに適合させることのできる、ＮＵＭＡシステム用の改善されたディスパッチャが求められている。
【課題を解決するための手段】
【００１５】
本発明によれば、非均一メモリ・アクセス・コンピュータ・システム用のディスパッチャは、どのＣＰＵにもＣＰＵグループにも優先的に関係付けられていない、単一の共通実行可能待ち行列（実行待ち行列ともいう）からのすべてのスレッドをディスパッチする。このディスパッチャは、スレッドをディスパッチする際にＣＰＵの物理的配置を考慮し、具体的には、スレッドが必要とするデータの比較的大きい部分を含む可能性の高いメモリ・サブセットにアクセスするために、メモリ・アクセス時間がより短いＣＰＵへのスレッドのディスパッチを優先する。
【００１６】
好ましい実施形態では、ＮＵＭＡシステムは、それぞれがローカル・メモリ、１つまたは複数のＣＰＵ，内部ノード・バス、および他のノードとやりとりするためのインターフェイスを備える複数の個別ノードのシステムとして設計される。システムのメイン・メモリは、各ノードのローカル・メモリの合併を含む分散メモリである。プロセッサのノード内の位置へのメモリ・アクセスは、ノード境界を越えるメモリ・アクセスより高速である。
【００１７】
好ましい実施形態では、各スレッドにそれぞれの優先ＣＰＵを関連づけることができる。ＣＰＵが使用可能になると、ディスパッチャは、その使用可能なＣＰＵと同じノード中に優先ＣＰＵを持つスレッドを、異なるノード中に優先ＣＰＵを持つスレッドより、少なくとも多少は相対的に優先する。これは、相対的優先であって、絶対的制約条件ではない。そのスレッドの優先ＣＰＵと同じノード中にないＣＰＵへのディスパッチのためにスレッドを選択すること、したがって、スレッド・ディスパッチの選択を厳格に制約しすぎることから生じ得る枯渇その他の問題を回避することも依然として可能である。
【００１８】
好ましい実施形態では、「理想ノード」と呼ばれる優先ノードは、一般に、ユーザ・プロセスに割り当てられる。プロセスがスレッドを生成するとき、そのスレッドはそのプロセスの理想ノードを継承する。さらに、その理想ノード中のＣＰＵがそのスレッドの「理想プロセッサ」として選択される。１つのプロセスによって生成される諸スレッドでの理想プロセッサの選択は、一般に、ラウンドロビン法によって循環させる。他の選択基準が等しい場合は、スレッドは、まず、理想プロセッサに優先的にディスパッチされ、次いで理想ノードにディスパッチされる。ディスパッチャは、状況に応じて、プロセッサに異なる理想ノードを持つスレッドをディスパッチせずに、それを遊ばせておくことも、そうしたスレッドをディスパッチすることもできる。
【００１９】
非均一メモリ・アクセスであるとみなされる様々な代替ディスパッチ技法が可能である。一代替方法では、ＣＰＵが使用可能になると、ディスパッチは、その使用可能ＣＰＵと同じノード中のＣＰＵで最後に実行されたスレッドを、異なるノード中で最後に実行されたスレッドより、少なくとも多少は相対的に優先する。
【００２０】
すべてのスレッドに、どの個々のＣＰＵにもＣＰＵグループにも関連づけられていない、単一の共通実行可能待ち行列を使用すれば、様々な非ＮＵＭＡオペレーティング・システムとも整合性がとれる。本明細書で述べる本発明の実施形態による、同じノードにスレッドをディスパッチするための緩やかで相対的な優先に従うことによって、スレッドは同じノード中で実行されやすくなり、そのノードの実メモリに、そのスレッドが必要とするデータの比較的大きな部分が蓄積されやすくなる。その結果、ノード間メモリ・アクセスの回数は、スレッドのディスパッチに際してノード配置を考慮に入れないシステムでの回数より少なくなる。同時に、厳格なノード制約条件が回避され、システム全体の利用が可能になり、枯渇その他の問題が回避される。
【００２１】
本発明の他の特徴および利点は、以下の、本発明の現時点での好ましい実施形態の詳細な説明を、添付の図面と併せて読めば明らかになるであろう。
【発明を実施するための最良の形態】
【００２２】
概要
本明細書で述べるように、マルチプロセッサ、非均一メモリ・アクセス（ＮＵＭＡ）コンピュータ・システム用のディスパッチャは、単一の汎用実行可能待ち行列にスレッドをディスパッチし、様々なプロセッサにディスパッチするためのスレッドまたはタスクを選択する際に、ノードの類縁性を考慮に入れるため、各スレッドは一貫したノードで実行されやすく、そのスレッドが必要とするメモリ・ページがそのノードのローカル実メモリに蓄積されやすい。一貫性を保つために、本明細書では、「スレッド」という用語を使用して、ディスパッチャによってディスパッチされるエンティティである、それ自体の状態を有する一連のコンピュータ実行可能命令のインスタンスを表す。環境によっては、それは「タスク」と呼ばれるが、本明細書では、「スレッド」と「タスク」を区別しない。「スレッド」という用語を使用して、プロセスが単一のプログラムから複数の同時に実行可能なスレッドを作成することを示唆する場合もある。しかし、本明細書で使用する場合、そうした限定を示唆する必要はなく、プロセスは、単一の実行スレッドだけを生成することも、複数のスレッドを生成することもできる。
【００２３】
ＮＵＭＡシステム・ハードウェア
図１は、本発明の好ましい実施形態による、マルチノード、マルチプロセッサ・コンピュータ・システム１００の主要ハードウェア構成要素を示す上位レベルの構成図である。コンピュータ・システム１００は、分散共用メモリ（ＤＳＭ）に基づくコンピュータ・アーキテクチャを使用する、ＮＵＭＡシステムである。コンピュータ・システム１００は複数のノード１０１〜１０４を含み、図１のシステムの例にはそのうちの４つが示されているが、ノード数は異なることもあることを理解されたい。各ノードは、任意のノードを他の任意のノードとやりとりできるようにする、ノード間通信ネットワーク１０５によって接続される。ノード間通信ネットワークの目的は、各装置がノード境界をまたいで通信できるようにすること、具体的には、任意のノード中のプロセッサが、他の任意のノード中にあるメモリにアクセスできるようにすることである。好ましい実施形態では、ノード間ネットワーク１０５は、ＩＥＥＥ１５９６−１９９２標準に準拠したスケーラブル・コヒーレント・インタフェース（ＳＣＩ）相互接続機構を使用する、スイッチ・ベースのネットワークである。ＳＣＩは、個々のポイントツーポイント相互接続上でパケットを送信すると共に、そのシステム全体でのキャッシュ一貫性を提供するポンプ式バスによって実現される高帯域幅相互接続ネットワークである。ＳＣＩに関する詳細情報は、参照によって本明細書に組み込まれるＩＥＥＥ標準１５９６−１９９２（１９９３年８月３日）で参照することができる。
【００２４】
ノード間ネットワーク１０５は好ましくはＳＣＩ準拠の通信媒体であるが、既存の、または今後開発される様々な代替手段のどれを使用することもできるであろう。このノード間通信媒体は、好ましくは、高帯域幅および短い待ち時間を実現すると共に、より多くのノードの追加を許容するために拡張性を有する必要がある。それに適した媒体には、データ・スループットの高い（例えば１ギガバイト／秒以上の）ポイントツーポイント相互接続リンクが含まれる。このリンクは、リング・トポロジ、スイッチを介した任意のトポロジ、あるいはその両者の組み合わせなど、何通りの適切な方式で構成することもできる。このリンクは、システム性能の必要に応じて、有線でも無線でもよい（光、無線周波数など）。その他のトポロジの例が、参照によって本明細書に組み込まれる、「ポイントツーポイント・リングを用いた相互接続トポロジ（Interconnect Topologies with Point-To-Point Rings）」、ロス・イー・ジョンソン（RossE. Johnson）およびジェームズ・イー・グッドマン（James E. Goodman）、１９９１年１２月、コンピュータ・サイエンス・テクニカル・レポート＃１０５８（ComputerSciences Technical Report #1058）ウィスコンシン−マディソン大学（University of Wisconsin-Madison）に記載されているが、そこに記載されている例は、必ずしも、適切なネットワークのすべてのタイプを網羅しているとは限らないことを理解されたい。
【００２５】
図２は、好ましい実施形態による、コンピュータ・システム１００の典型的なノード１０１の主要ハードウェア構成要素を示す構成図である。本明細書に含まれる記述の一貫性を保つために、ノードを総称して参照番号１０１とするが、これはノード１０１〜１０４のいずれでもあり得ることを理解されたい。ノード１０１は、分散メイン・メモリからの命令および他のデータに基づいて基本的な機械処理機能を実施する複数の中央処理装置（ＣＰＵ）２０１〜２０４を含む。各ＣＰＵ２０１〜２０４は、データおよび命令の一時的記憶のためにそれぞれのキャッシュ２０５〜２０８を含み、あるいはそれを制御する。大規模な、マルチプロセッサ・コンピュータ・システムでは、キャッシュは、通常、複数のレベルで複数の構造として存在する。例えば、ＣＰＵは、そのＣＰＵで実行される命令の記憶専用のレベル１キャッシュ（Ｌ１命令キャッシュ）、そのＣＰＵによって操作される命令以外のデータの記憶専用の、物理的に別個のレベル１キャッシュ（Ｌ１データ・キャッシュ）、および命令と他のデータの両方を記憶し、Ｌ１命令キャッシュおよびＬ１データ・キャッシュに補給するために使用されるレベル２キャッシュ（Ｌ２キャッシュ）を含むことができる。この１つまたは複数のキャッシュ構造は、図２では、それぞれのプロセッサごとに単一ブロック２０５〜２０８として、単純化した形で表されている。本発明のためには、各プロセッサでのキャッシュの正確な実装の詳細は、重要ではない。他の多くの変形形態が可能であり、本発明は、どんな具体的なキャッシュ設計にも限られるものではなく、必ずしもキャッシュの使用を必要とするとは限らない。
【００２６】
コンピュータ・システム１００は、分散メイン・メモリを利用し、各ノード１０１ごとに別個のローカル・メモリ２１０を含む。システム１００内のアドレス指定可能なメイン・メモリの合計は、各ノード中のアドレス指定可能なローカル・メモリ２１０の総和である。システム全体のすべてのＣＰＵは、同じアドレス指定可能な分散メイン・メモリを共用する。したがって、メイン・メモリの実アドレス空間は、そのシステム全体で一定であり、ローカル・メモリ２１０中の任意のメモリ位置は、すべてのプロセッサおよびすべてのノードにとって同じ、一意の実アドレスを持つ。
【００２７】
ノード間インターフェイス・ユニット２１５は、ノード１０１をノード間ネットワーク１０５に接続し、それによってノード１０１がシステム１００内の他のノードとやりとりできるようにする。インターフェイス・ユニット２１５は、通常、ノード間で渡されるデータの一時記憶のためのキャッシュまたはバッファを含む。
【００２８】
入出力バス・インターフェイス・ユニット２２０は、１つまたは複数の入出力バス２２１〜２２２を介した１つまたは複数の入出力装置への通信を提供する。入出力バス２２１〜２２２は、直接アクセス記憶装置（ＤＡＳＤ）２２４、テープ装置、ワークステーション２２５、印刷装置、および専用の通信線またはネットワークを介した遠隔装置または他のコンピュータ・システムとの通信のための遠隔通信アダプタなど、従来の入出力装置との通信に適したどんなタイプのものでもよい。例えば、入出力バス２２１は、業界標準のＰＣＩバスとすることもできる。図２には２本の入出力バスおよび２台の入出力装置が示されているが、そうしたバスおよび装置の数は異なることがあり、すべてのノード１０１が入出力インターフェイス・ユニット２２０や接続された入出力装置を含む必要はないことを理解すべきである。
【００２９】
内部ノード・バス２１２は、ノード１０１の各種構成要素間の通信を提供する。具体的には、バス２１２は、ＣＰＵによって発せられたメモリ・アクセスに応答して、ローカル・メモリ２１０とそれぞれのＣＰＵ２０１〜２０４のキャッシュ２０５〜２０８との間でデータを転送する。ローカル・メモリ２１０でのロジックを監視して、ノード間インターフェイス２１４、またはバス２１２自体、あるいはその両方は、メモリ・アクセスで要求された個々の実アドレスが、ノード１０１のローカル・メモリ２１０に含まれているか、それとも別の（遠隔）ノードのローカル・メモリに含まれているか判定し、場合に応じて、そのメモリ・アクセスを、ローカル・メモリ２１０、または遠隔ノードとの通信のためのノード間インターフェイス２１５に送る。ローカル・メモリ２１０内の実アドレスへのメモリ・アクセスはバス２１２を横切り、比較的短いマシン・サイクル数で戻るが、遠隔ノードのローカル・メモリ内の実アドレスへのメモリ・アクセスは、少なくともいくつかの場合には、要求側ノードのノード・バス２１２、要求側ノードのノード間インターフェイス２１５、ノード間ネットワーク１０５、応答側ノードの対応するノード間インターフェイス２１５、および応答側ノードの対応するノード・バスを横切って、データが存在する応答側ノードのローカル・メモリに到達することになることが認められるであろう（この動作は、要求されたデータがインターフェイス・キャッシュの１つにあった場合には、短縮されることもある）。その結果、遠隔ノードへのメモリ・アクセスは、一般に、相対的に多数のサイクルを必要とする。
【００３０】
図１には４つのノードを備えるシステムが示されており、図２には４つのＣＰＵおよび他の各種装置を備える典型的ノードが示されているが、図１および図２は、ＮＵＭＡシステムの１つの可能な構成の単純化した一例を示すためのものにすぎず、そうした構成での可能な装置の数およびタイプは異なることがあり、システムが、しばしば、図示しないその他の装置も含むことがあることを理解すべきである。さらに、すべてのノードが同一であることも、すべてのノードが同数のＣＰＵまたは同量のアドレス指定可能なローカル・メモリを備えることも必要とされないことも理解すべきである。
【００３１】
オペレーティング・システムの概要
図３は、コンピュータ・システム１００における異なる抽象化レベルでのハードウェアおよびソフトウェア機能の分割を示す概念図である。周知のように、コンピュータ・システムはプロセスを実施する、順次的状態マシンである。これらのプロセスは、様々な抽象化レベルで表すことができる。上位の抽象化レベルでは、ユーザがプロセスおよび入力を指定し、出力を受け取る。下位レベルに進むにしたがって、これらのプロセスが何らかのプログラミング言語で書かれた命令のシーケンスであり、下位に進むにつれて、より下位レベルの命令シーケンスに変換され、オペレーティング・システム・コードを介して最終的にはデータ・ビットに変換され、それがマシンのレジスタに入力されて一定の動作を引き起こすことがわかる。非常に下位のレベルでは、電位を変化させることによって、様々なトランジスタをオンおよびオフにする。図３では、「上位」の抽象化レベルが図の上部に向かって表され、下位レベルが図の下部に向かって表されている。
【００３２】
図３に示すハードウェア・レベル３０１は、命令を実行させる、物理的なプロセッサ、メモリ、バスその他の構成要素を表す。本明細書で使用する際、ハードウェア・レベル３０１は、図１および図２に示さない他のハードウェアも含めて、図１および図２に示す（各装置に記憶されたデータに対して）物理装置の集合体を表す。
【００３３】
ハードウェアの真上にあるのは、下位オペレーティング・システム・レベル３０２であり、オペレーティング・システムによっては、「カーネル」と呼ばれる。物理的な意味では、オペレーティング・システムは符号、すなわち命令の形のデータであり、様々なメモリ位置に記憶され、１つまたは複数のプロセッサ上で実行されて必要な機能を果たす。下位オペレーティング・システムは、システム・リソースを共用し、メモリを割り振り、セキュリティを実施するなどのために必要とされるある種の基本的なオペレーティング・システム機能を提供する。下位オペレーティング・システム３０２によって提供される機能の中には、ページング機能３０３およびディスパッチ機能３０４がある。ページャ３０３は、実行スレッドが、現在システムの分散メイン・メモリ内にないデータにアクセスしようとするとき、すなわちそのデータが各種ノード中のローカル・メモリ２１０のどこにもないときに呼び出される。その場合、ページャ３０３は、必要とされるデータを記憶装置（回転磁気ディスク・ドライブ記憶装置など）から取り出させ、それをローカル・メモリ２１０の１つに入れさせる。ディスパッチャ３０４は、本明細書でより詳細に説明するように、実行されるのを待つスレッドを実行するためにプロセッサにディスパッチする。ディスパッチ実行可能待ち行列構造３０５は、ディスパッチャ３０４によるディスパッチを待つスレッドを含む。
【００３４】
下位オペレーティング・システム・レベル３０２の上には、様々なユーザ・プロセス３１０〜３１２（すなわちユーザ・アプリケーション・コードおよびデータ）、およびその他の上位オペレーティング・システム機能３０８がある。一般に、上位オペレーティング・システム機能３０８は、それへのアクセスを希望するユーザに追加の能力および機能を提供するが、ユーザ・プロセスは、実行のために下位オペレーティング・システム３０２に直接アクセスすることができる。
【００３５】
好ましい実施形態では、オペレーティング・システムがＭｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ  ２０００（登録商標）オペレーティング・システムであり、そのタスク・ディスパッチャおよびページャは、ＣＰＵおよびメモリのノード配置を考慮するために本明細書で述べるように変更されている。しかし、実際上は、今後開発されるオペレーティング・システムを含めて、様々なＵＮＩＸ（登録商標）ベースのオペレーティング・システム、ＩＢＭ  ＡＳ／４００（登録商標）オペレーティング・システムなど、そこからタスクがディスパッチされる単一の共通実行可能待ち行列を備える、どんなマルチタスク・オペレーティング・システムも、本明細書で述べる諸機能に適合させることができるであろう。
【００３６】
典型的なコンピュータ・システム設計では、上位レベルにあるエンティティに下位レベルのエンティティの実装詳細を知られないようにすることが望ましい。ＮＵＭＡシステムのハードウェアの設計の場合には、これは、オペレーティング・システムおよび上位レベルのソフトウェアが、好ましくは、ＮＵＭＡの特性の知識を持つことを必要とされないことを意味する。したがって通常、ＮＵＭＡシステムは、オペレーティング・システムが、その分散メイン・メモリを、データ要求に対して、データが存在する場合は要求されたデータを返しそれが存在しない場合はページ不在を生成することによって応答する、単なる１つのモノリシック・エンティティであるとみなすことができるように設計される。同様に、オペレーティング・システムは、ノードおよびプロセッサの集合体を、そのすべてがどのプロセスを実行するのにも使用可能な、単なるプロセッサの１つの大規模なプールであるとみなすことができる。これは、すべてのプロセッサが所与のタスクを同じ時間で実行することも、すべてのメモリ・アクセスが同じ時間で完了することも意味しない。そうならないのは前述した理由によるものである。しかし、それは、要求されたメモリが同じノード中にあるか否かにかかわらず、メモリ・アクセスがエラーなしで完了することを意味する。したがって、オペレーティング・システムは、プロセッサが位置するノードを考慮せずにスレッドをディスパッチすることができる。
【００３７】
ＮＵＭＡシステム・ハードウェアは、標準の下位オペレーティング・システム機能と共に機能するように設計されるが、下位オペレーティング・システムがハードウェア設計をより意識している場合、具体的には、スレッドをディスパッチする際にプロセッサのノード位置が考慮される場合は、コンピュータ・システムはより効率よく動作するであろう。
【００３８】
ディスパッチおよびページング機能
本明細書で述べるスレッド・ディスパッチャは、スレッドが一貫したノードで実行される場合、スレッドが必要とするデータは通常の実行ノードに蓄積されやすくなり、したがって、ノード間メモリ・アクセスの回数が減少するという原理に基づいて動作する。これが当てはまるのは、メモリ・ページング機構自体が何らかの配置の局所性を示す場合、すなわちページャ３０３が要求されたページを何らかの特定のローカル・ノードに入れる可能性が無作為より高い場合だけである。
【００３９】
配置の局所性を示すページャを実装する単純で直接的な方法は、ページ配置を要求側プロセッサのノードに限定することであり、これが好ましい実施形態で使用される方法である。すなわち、ページ不在が発生した場合は、ページャ３０３は、常に、そのページ不在を発生させたメモリ・アクセス要求を出したプロセッサを含むノードのローカル・メモリに新しいページを入れる。ページャ３０３は、そのノードのローカル・メモリの使用可能なページからページ・アウトするための最善の候補を選択する。ページャを実装する一代替方法は、ページの配置を要求側プロセスの理想ノードに限定することである。すなわち、（本明細書でより詳細に説明するように）各プロセスに理想ノードが関連づけられており、ページは常に、それがそのメモリ・アクセスを発したプロセッサと同じノードでない場合でも、そのページ不在を発生させたプロセスに関連づけられた理想ノードのローカル・メモリに入れられる。この代替方法の根拠は、プロセスによって生成されたスレッドが異なるノードで実行されることがあっても、ページは一貫したローカル・ノードに入れられるというものである。しかし、ページャが用いることのできる可能な技法はこれら２つの代替方法だけに限らず、様々な代替基準または基準の組み合わせを使用してページ配置のある程度の局所性を達成することができるはずであることが理解されるであろう。
【００４０】
スレッド・ディスパッチは、そのスレッドの状態および優先度に依存する。任意の瞬間において、スレッドはいくつかの状態のうちの１つの状態にある。例えば、スレッドは、それがプロセッサ上で実行されている実行状態、何らかの外部イベントが発生するまでそれを実行することができず、したがって、そのイベントが発生するのを待っている、イベント待機状態、あるいはそのスレッドが実行可能な状態であり、使用可能なプロセッサを待つだけの実行可能状態にあることができる。オペレーティング・システムによっては、その他の状態または上記の状態の細分化が定義されることもある。さらに、各スレッドに実行の優先度が関連づけられる。当分野で知られているまたは今後開発される様々な優先度割り当て方式のどれでも使用することができる。優先度は、通常、ユーザ、システム管理者、またはオペレーティング・システム自体によって割り当てられる。例えば、ユーザ・アプリケーション・プロセスの優先度は、しばしば、オペレーティング・システムによって指定され、ユーザによって指定変更されるユーザ・プロセスのデフォルトの優先度であることがある。この優先度は、そのスレッドの存続期間中だけ固定することもでき、そのスレッドが実行可能待ち行列中で待機していた時間の長さなど、様々な要因に応じて調整することもできる。本明細書での規則では、より大きい数がより大きい優先度を示すが、代替として、優先度を逆の数値順序にすることもできるであろう。
【００４１】
ディスパッチャ３０４は、スレッド実行可能待ち行列構造３０５からディスパッチするためのスレッドを選択する。図４に実行可能待ち行列構造３０５をより詳細に示す。図４に示すように、実行可能待ち行列構造は、制御ブロック４１０〜４１２の複数のリスト４０１〜４０３を含み、図４には例としてそのうち３つのリストを示すが、実際の数は異なることもあることを理解されたい。各制御ブロック４０１〜４０３は、先入れ先出し順で配置される。所与のリストの制御ブロック４１０〜４１２は、実行可能で実行されるのを待っている、指定された優先度に関連づけられたスレッドを表す。すなわち、制御ブロック・リスト４０１〜４０３は、実行可能状態のスレッド、すなわち実行可能であり、使用可能なプロセッサを待つだけのスレッドを含む。スレッドが実行可能状態に入ると、その制御ブロックは、そのスレッドに関連づけられた優先度を持つリストの末尾に配置される。その制御ブロックは、通常、ディスパッチャ３０４がそれを実行のためにＣＰＵにディスパッチするときに、リストから除かれる。
【００４２】
好ましい実施形態では、システム１００には１つの実行可能待ち行列構造３０５だけが存在し、実行可能なすべてのスレッドは、そのスレッドの優先度に対応する実行可能待ち行列構造３０５中のリスト４０１〜４０３に入れられる。この実行可能待ち行列は、どのＣＰＵにもＣＰＵグループ（ノードなど）にも関連づけられておらず、これは、本明細書で使用される場合は、どのＣＰＵもＣＰＵグループもこの実行可能待ち行列からタスクの優先的ディスパッチを受け取らないことを意味する。この実行可能待ち行列はメモリ構造であり、通常、ノードの１つに記憶され、ディスパッチャは、通常、そのノード中のＣＰＵ上で実行されるが、これは、本明細書で「ＣＰＵまたはＣＰＵグループに関連づけられる」が意味する内容ではない。
【００４３】
各制御ブロック４１０〜４１２は、アクティブなスレッドに関するある状態情報を含み、ディスパッチャ３０４はその一部を使用してディスパッチのためのスレッドを選択する。図５に、ディスパッチャによって使用される典型的な制御ブロック４１０からのあるスレッド別情報を示す。図５に示すように、この制御ブロックは、優先度５０１、類縁性マスク５０２、理想ノード・マスク５０３、理想プロセッサ５０４、最後に実行されたプロセッサ５０５、および待ち行列時間５０６を含む。優先度フィールド５０１は、そのスレッドの指定された優先度数値を含む。類縁性マスク５０２は、ユーザまたはシステム管理者が、その類縁性マスクによって指定された、そのシステム上で使用可能なＣＰＵのサブセット上だけでプロセスを実行できるように要求するための、それぞれのＣＰＵに対応する一連のマスク・ビットである。ほとんどの場合、ユーザは実行を制限せず、類縁性マスクは、すべてのＣＰＵを使用可能にするように設定される。理想ノード・マスク５０３は、本明細書で述べるように、実行のための１つまたは複数の優先ノードを指定するための、それぞれのノードに対応する１組のマスク・ビットである。理想プロセッサ・フィールド５０４はそのスレッドを実行するための１つの優先ＣＰＵの数値指定である。最後に実行されたプロセッサ・フィールド５０５は、そこでそのスレッドが直前に実行されたＣＰＵの数値指定である。待ち行列時間フィールド５０６は、そのスレッドが実行可能待ち行列中にあった時間の長さを示す値を含む。例えば、この値は、そのスレッドがいつその待ち行列に入ったかを記録するタイムスタンプとすることができるが、それは、ある種のイベントの発生時に増分されるカウンタや他の値とすることもできるであろう。
【００４４】
図４および図５に、例として単純化した形で実行可能待ち行列および制御ブロックを示すが、これらは、ディスパッチャによって使用されるデータ構造の形式の正確な青写真を提供するためのものではない。実行可能待ち行列は、リンクされたリスト配列に複数の制御ブロック４１０〜４１２を含み、各ブロック４１０〜４１２が単一のそれぞれのスレッドに対応し、すべての必要な状態情報を含むものとして示されている。しかし、この待ち行列データ構造の正確な構造の詳細は異なることもあり、アレイまたは他の形のデータ構造として実装することもできるであろう。さらに、制御ブロック４１０〜４１２は、それぞれのスレッドごとに完全な状態情報を含むものとして示されているが、この待ち行列中のレコードは、ディスパッチャが必要とする一部の情報だけを含んでいても、単に、必要なデータを見つけられる位置への１つまたは複数のポインタまたは他の指標だけを含んでいてもよい。制御ブロックは、ディスパッチャまたは他の機能によって使用される、他のおよび追加の状態情報を含むこともできる。
【００４５】
ディスパッチ選択を制御する制御ブロック中のある種の値は、プロセスがスレッドを生成したときに初期設定され、それをプロセス開始時に生成された値から継承することもできる。図６は、スレッド制御値を初期設定するためにオペレーティング・システムが行う各ステップを上位レベルで示す流れ図である。図６に示すように、任意の従来方式でプロセスを開始し、ある種のデータ構造を生成、初期設定させる。具体的には、図５に示す値を保持する制御ブロックまたは類似の構造を作成させる。さらに、このプロセスに優先度およびプロセッサ類縁性を割り当てる。これらのステップは、上位レベルではステップ６０１として一括して表される。
【００４６】
以下のように理想ノードをプロセスに関連づける。プロセスがシステム・プロセスであり、またはそれに特定のプロセッサ類縁性が割り当てられている場合は、ステップ６０２から「Ｙｅｓ」分岐を選択し、理想ノードをすべてに設定する（６０３）。すなわち、そのプロセスに関連づけられた理想ノード・マスクですべてのノードが「オン」に設定され、これは事実上、理想ノード選択が行われていないことを意味する。システム・プロセスは、すべてのノードで実行するための、様々な指定されたオペレーティング・システム・プロセスのいずれかである。プロセッサ類縁性は、ユーザまたはシステム管理者によって指定され、使用可能なＣＰＵの個々のサブセットで実行されるプロセスを限定する。プロセッサ類縁性が指定されることはまれであるが、そうした類縁性が指定されたときには、それはシステム割り当ての「理想ノード」を指定変更すべきものと想定され、したがって、その場合は理想ノード割り当ては使用されない。
【００４７】
プロセスがシステム・プロセスでもなく、特定のプロセッサ類縁性も持たない（すなわち、どのプロセッサ上でも実行できる）場合は、ステップ６０２から「Ｎｏ」分岐を選択する。その場合、オペレーティング・システムはラウンドロビン法を使用して理想ノードを割り当てる。すなわち、直前にプロセスに割り当てられたノードの番号を増分し（６０４）、このノードをそのプロセスの理想ノードとして割り当てる（ステップ６０５）。割り当て動作は、選択された理想ノードに対応する理想ノード・マスクにビットを設定することによって行う。
【００４８】
ノード・マスクは、単一ノードでも、すべてのノードでも、あるいは任意のノード・サブセットでも理想ノードに指定できるように、柔軟性を最大にするために使用される。オペレーティング・システムは、デフォルトでは、前述のようにほとんどのユーザ・プロセスに単一ノードを選択する。しかし、ユーザが、特別な関数呼出しによってこの選択を指定変更することも可能であろう。この関数は、オペレーティング・システムによって行われるリソース均衡化を妨げやすいので、まれにしか使用されないと思われるが、それを正当化する特別な状況もあり得る。
【００４９】
デフォルトでは、単純なラウンドロビン法を使用して使用可能なノード間でプロセスを対等に分配し、したがって、リソース利用度を均衡化する。しかし、オペレーティング・システムは、優先ノードを割り当てる代替方法をいくつでも使用することができるであろう。例えば、各ノード中のプロセッサの数が同一でない場合は、しかるべく割り当てに重みづけすることが望ましいとも考えられる。あるいは、最近のＣＰＵ利用度に関する統計を取り、最近のＣＰＵ利用度が最低のノードにプロセスを割り当てることもできるであろう。
【００５０】
ステップ６１０で表すように、ある時点で、プロセスはスレッドを生成する。プロセスは、１つのスレッドを生成することも、複数のスレッドを生成することもあるが、図６では例として１つだけを示してある。特に、スレッドの生成は、そのスレッドに１つまたは複数の状態レコード（制御ブロック４１０など）が作成され、ある値に初期設定されることを意味する。プロセスを開始する場合のように、スレッドの生成は、当分野で知られているように、多数のステップを含むことがあるが、本明細書ではそれを詳細に説明せず、ステップ６１０によって上位レベルで表すだけにする。スレッド優先度値５０１、類縁性マスク５０２、および理想ノード・マスク５０３は、そのスレッドを生成したプロセスの同様の値から継承される（ステップ６１１）。これは、プロセス値がスレッド制御ブロックにコピーされることを意味することも、スレッド制御ブロックが単にプロセス値を参照することを意味することもある。
【００５１】
実行のための優先ＣＰＵ（「理想ＣＰＵ」と呼ばれる）は、理想ノード中のランダムなＣＰＵから開始し、理想ＣＰＵ割り当てをラウンドロビン法で循環させることによって、各スレッドに割り当てられる。すなわち、生成されるスレッドが、プロセスによって生成される最初のスレッドである場合は、ステップ６１２から「Ｙｅｓ」分岐を選択し、（そのスレッドの理想ノード・マスクによって指定された）その１つまたは複数の理想ノード内のＣＰＵをランダムに選択する（ステップ６１３）。生成されるスレッドが最初のスレッドでない場合は、ステップ６１２から「Ｎｏ」分岐を選択し、オペレーティング・システムは、その１つまたは複数の理想ノード内のＣＰＵの間での事前に定められた順序関係に従って、最後に生成されたスレッドに割り当てられたＣＰＵの番号を増分し（ステップ６１４）、新規に生成されたスレッドにこの次のＣＰＵを割り当てる（ステップ６１５）。
【００５２】
図６は、ディスパッチャによって使用されるある種の変数の初期設定を例示するためのプロセスおよびスレッドの初期設定の非常に単純化した流れ図であり、プロセスを開始し、またはスレッドを生成するために行われるステップの網羅的表現を目的とするものではないことが理解されるであろう。
【００５３】
次に、スレッド・ディスパッチャ３０４の動作を、実行可能待ち行列３０５および制御ブロック４１０に含まれる情報と併せて説明する。一般に、ディスパッチャは、新規スレッドをディスパッチする必要がある、またはディスパッチできることを示す外部イベントに応答し、ディスパッチされるスレッドまたはそのスレッドを実行するＣＰＵあるいはその両方を決定する。第１のモード（図７および図８に示す）では、ＣＰＵがスレッドを実行できるようになると、実行可能待ち行列３０５から使用可能なスレッドを選択するためにディスパッチャが呼び出される。これは、例えば、以前にそのＣＰＵ上で実行されていたスレッドが待ち時間の長いイベント（記憶アクセスやリソース上のロックなど）に遭遇したため、以前に実行されていたスレッドが時間切れになったため、以前に実行されていたスレッドが中断されたため、あるいはスレッドの実行が終了したためなどの理由で行われる。第２のモード（図９に示す）では、スレッドが実行可能状態になった（例えば、新規スレッドが生成された、またはスレッドが待ち続けていた外部イベントが発生した、あるいはスレッドを実行可能にする他のイベントが発生した）ために、使用可能なプロセッサを選択するためにディスパッチャが呼び出される。オペレーティング・システムの設計に応じて、ディスパッチャが他の理由で呼び出されることもあることが理解されるであろう。
【００５４】
ディスパッチャの核心は、ディスパッチのためのスレッドを選択する、スレッド選択機構である。スレッドは、使用可能なＣＰＵに最もマッチするものとして選択され、したがって、スレッド選択関数が呼び出されたときは、そのスレッドをディスパッチするための目標ＣＰＵが検討される。好ましい実施形態では、この目標ＣＰＵは、一般に、使用可能になったばかりの、そのディスパッチ関数を呼び出させたＣＰＵである。
【００５５】
図７および図８は、ディスパッチ３０４内のスレッド選択関数の動作を示す流れ図である。このスレッド選択関数は、目標ＣＰＵ（Ｐと呼ぶ）にスレッドを選択するために呼び出される。前述したように、このＣＰＵは一般に、使用可能になったばかりのＣＰＵである。スレッド選択関数は、適当なスレッドが見つかるまで、実行可能待ち行列３０５中の様々な制御ブロック・リスト４０１〜４０３を、優先度が最大のものから優先度が最低のものまで探索する。図７および図８に示すように、スレッド選択関数は、まず、探索するリストを選択する（ステップ７１０）。最初に選択される制御ブロック・リストは優先度が最高のリストであり、以降、このメイン・ループを反復するたびに、ステップ７０１では、まだ考察されていないリストのうち優先度が最高のリストを選択する。変数ｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔおよびｉｄｅａｌ＿ＣＰＵ＿ｈｉｔをヌル値に設定する（ステップ７０２）。さらに、ディスパッチャは、選択された制御ブロック・リスト中のスレッドの最大待ち時間（ｗｍａｘ）を決定する（やはりステップ７０２）。最大待ち時間は各リストごとに異なり、優先度の高いリストほど短く、優先度の低いリストほど長い。したがって、考察される各選択リストごとにｗｍａｘの値をリセットする必要がある。
【００５６】
次いで、スレッド選択関数は、ステップ７１０〜７１８を含むループとして図７に示すように、一致が見つかるまで、またはリストの末尾に達するまで、選択された制御ブロック・リスト中の各スレッドを順に考察する。リストからスレッド（ｔ）を選択する（ステップ７１０）。このスレッドは、最初は、リスト中の最初のスレッド、すなわち、その制御ブロックがそのリストに最も長く存在しているスレッドであり、その後は、まだ選択されていないスレッドの中で最も長くそのリストに存在しているスレッドである。次いで、スレッド選択関数は、Ｐがスレッドｔのプロセッサ類縁中のＣＰＵの１つであるかどうか（ステップ７１１）、すなわち、プロセッサＰに対応するビットがスレッドｔのプロセッサ類縁性マスク５０２に設定されているかどうか判定する。そうでない場合、スレッドｔはプロセッサＰ上での実行から除外され、スレッド選択関数はステップ７１８に進んで次のスレッドを考察する。
【００５７】
Ｐがｔのプロセッサ類縁中にある場合（ステップ７１１からの「Ｙｅｓ」分岐）は、スレッド選択関数は、ｔが即時選択の基準を満たすかどうか判定する（ステップ７１２）。ステップ７１２で実施されるテストは論理的には以下のように表すことができる。
（ｔはリアルタイム優先リストにある）または    （１）
（ｔはｗｍａｘより長い間待機している）または    （２）
（（Ｐ＝ｌａｓｔ＿ＣＰＵ）かつ（Ｐ＝ｉｄｅａｌ＿ＣＰＵ））または    （３）
（（Ｐ＝ｌａｓｔ＿ＣＰＵ）かつ（Ｐはｔの理想ノード中にある））または    （４）
（（Ｐ＝ｌａｓｔ＿ＣＰＵ）かつ（ｉｄｅａｌ＿ＣＰＵはｔの類縁に含まれない））または    （５）
（（理想ノードがない）かつ（Ｐ＝ｉｄｅａｌ＿ＣＰＵ））    （６）
条件（１）および（２）では、スレッドｔのディスパッチが急を要するときは、通常のノード・マッチングの考慮事項に優先する。リアルタイム優先リストは、事実上ｗｍａｘが０の、特別な最優先制御ブロック・リストであり、そのため、そのリストで待機するどのスレッド制御ブロックもその最大待機期間を超過している。他のすべての制御ブロック・リストでは、スレッドｔがすでに、ｔが待機しているリストに定められた最大期間ｗｍａｘより長く待機している場合は、ｔはディスパッチのために直ちに選択される。条件（３）では、そのスレッドが（ｌａｓｔ＿ＣＰＵフィールド５０５で指定されるように）Ｐ上で最後に実行され、かつＰがｉｄｅａｌ＿ＣＰＵフィールド５０４で指定されたそのスレッドの理想ＣＰＵである場合に、スレッドを選択する。条件（４）は（３）と同様であるが、理想の概念を、ｔの理想ノードすなわちｔの理想ノード・マスク５０３によって指定されたノード中の任意のプロセッサに拡張する。条件（５）は、スレッドｔの類縁に理想ＣＰＵがない特殊な場合を扱う。これが起こるのは、ＡＰＩ呼出しによる場合のように、プロセス開始後に何らかの値（類縁性など）が変更された場合だけである。その場合、スレッドｔの理想ＣＰＵを見つけるのは不可能になり、したがって、最後に使用されたＣＰＵが可能な最善のＣＰＵである。条件（６）は、マスク５０３で理想ノードが指定されていない特殊な場合を扱い、その場合、理想ＣＰＵが優先される。
【００５８】
上記の即時選択の基準が満たされた場合は、ステップ７１２から「Ｙｅｓ」分岐を選択し、スレッドｔを選択されたスレッドに指定し（ステップ７１３）、スレッド選択関数は残りのスレッドをそれ以上考察せずに戻る。そうでない場合は、「Ｎｏ」分岐を選択する。その場合、Ｐがｉｄｅａｌ＿ＣＰＵフィールド５０４で指定された理想ＣＰＵであり、かつそれが最初に遭遇したそうしたスレッドであった場合（すなわちｉｄｅａｌ＿ＣＰＵ＿ｈｉｔ＝ヌル）は、ステップ７１４から「Ｙｅｓ」分岐を選択し、ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔをｔに設定する（ステップ７１５）。ステップ７１４から「Ｎｏ」分岐を選択した場合に、Ｐが理想ノード・マスク５０３で指定された理想ノード中にあり、かつそれが最初に遭遇したそうしたスレッドであった場合（すなわちｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔ＝ヌル）は、ステップ７１６から「Ｙｅｓ」分岐を選択し、ｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔをｔに設定する（ステップ７１７）。選択された制御ブロック・リストに次のスレッドが残っている場合（ステップ７１８）は、スレッド選択関数はステップ７１０に戻ってリスト中の次のスレッドを選択しそれを考察する。選択されたリスト中のすべてのスレッドの考察を完了したときは、ステップ７１８から「Ｎｏ」分岐を選択し、スレッド選択関数はステップ７２０に進む。
【００５９】
その制御ブロック・リスト全体を探索し終えて、ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔがヌルでなかった場合は、ステップ７２０から「Ｎｏ」分岐を選択し、ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔによって指定されたスレッドを選択されたスレッドに指定し（ステップ７２１）、関数はそれ以上のリストを考察せずに戻る。ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔがヌルであった場合は、ステップ７２０から「Ｙｅｓ」分岐を選択する。その場合、ｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔがヌルでなかった場合は、ステップ７２２から「Ｎｏ」分岐を選択し、ｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔによって指定されたスレッドを選択されたスレッドに指定し、関数はそれ以上のリストを考察せずに戻る。ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔもｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔもヌルであった場合は、スレッド選択関数はステップ７２４に進む。考察すべき次の制御ブロック・リストが残っている場合は、「Ｙｅｓ」分岐を選択し、優先度が現在のリストの次のリストを考察するために選択する。すべてのリストを考察し終えた場合は、ステップ７２４から「Ｎｏ」分岐を選択し、選択されたスレッドとしてヌル値を指定し（ステップ７２５）、スレッド選択関数は戻る。
【００６０】
スレッドが実行可能になると、可能な場合は、そのスレッドを実行するのに適したＣＰＵを選択するためにディスパッチャが呼び出される。図７および図８のスレッド選択プロセスと異なり、特定の目標スレッド（ｔとする）が与えられると、複数の可能なＣＰＵ候補の中からＣＰＵを選択するために、ＣＰＵ選択プロセスが呼び出される。このプロセスを図９に示す。
【００６１】
ＣＰＵ選択関数は、まず、スレッドｔの類縁に理想ＣＰＵが存在し、かつそれが現在使用されていないかどうか判定する（ステップ８０１）。使用されていない場合は、ステップ８０１から「Ｙｅｓ」を選択して、この理想ＣＰＵを選択し（ステップ８０２）、スレッド選択関数は戻る。そうでない場合は、ステップ８０１から「Ｎｏｔ」分岐を選択する。
【００６２】
スレッドｔの類縁内に少なくとも１つの使用されていないＣＰＵがあり、かつスレッドｔの理想ノードが存在する場合でそのＣＰＵがそのノード中にある場合（すなわち、理想ノードが存在しない場合には、テストは単にスレッドｔの類縁内に少なくとも１つの使用されていないＣＰＵがあるかどうかだけになる）は、ステップ８０３から「Ｙｅｓ」分岐を選択する。その場合は、そうした１つのＣＰＵを選択する（ステップ８０４）。ステップ８０３の基準を満たす複数の使用されていないＣＰＵがある場合は、ＣＰＵ選択関数は、それが基準を満たすＣＰＵの１つである場合には、スレッドｔによって最後に使用されたＣＰＵを選択し、そうでない場合には、デフォルトの選択論理に基づいてそうしたＣＰＵの１つを選択する。次いでスレッド選択関数は戻る。ステップ８０３で上記の基準を満たすＣＰＵが見つからなかった場合は、「Ｎｏ」分岐を選択して、使用中の若干のプロセッサを考察する。
【００６３】
スレッドｔの類縁中にある使用されていないＣＰＵが存在する場合は、ステップ８０５から「Ｙｅｓ」分岐を選択し、この使用されていないＣＰＵを候補ＣＰＵとして仮に選択する（ステップ８０６）。この場合、このＣＰＵは必ず使用中である。さもなければこれはステップ８０１で選択されていたはずである。ステップ８０５から「Ｎｏ」分岐を選択した場合で、スレッドｔの類縁内にあって、理想ノードが存在する場合には、スレッドｔの理想ノード中にもあるＣＰＵが存在する場合（すなわち、理想ノードがない場合は、テストはスレッドｔの類縁内にＣＰＵがあるかどうかだけになる）は、ステップ８０７から「Ｙｅｓ」分岐を選択し、そうした１つのＣＰＵを仮に選択する（ステップ８０８）。そうしたＣＰＵが複数ある場合は、ＣＰＵ選択関数は、それが基準を満たすＣＰＵの１つである場合には、スレッドｔによって最後に使用されたＣＰＵを仮に選択し、そうでない場合には、デフォルトの選択論理に基づいてそうしたＣＰＵの１つを仮に選択する。ステップ８０７から「Ｎｏ」分岐を選択した場合は、ＣＰＵ選択関数は、デフォルトの選択論理を使用してスレッドｔの類縁中のＣＰＵを仮に選択する（ステップ８０９）。
【００６４】
ステップ８０６、８０８または８０９で候補ＣＰＵを仮に選択した場合は、その候補プロセッサで現在実行されているスレッドの優先度をスレッドｔの優先度と比較する（ステップ８１０）。ｔの優先度の方が大きい場合は、ステップ８１０から「Ｎｏ」分岐を選択し、その候補ＣＰＵを選択されたＣＰＵであると確認する（ステップ８１１）。その場合、使用中のＣＰＵを選択すると、現在実行中のスレッドが切り替えられる。ｔの優先度が実行中のスレッドの優先度以下である場合は、ステップ８１０から「Ｙｅｓ」分岐を選択し、選択されたＣＰＵをヌルに設定する。いずれの場合も、次いでＣＰＵ選択関数は戻る。ＣＰＵ選択関数が選択が空白のまま戻った場合、それはスレッドｔの即時ディスパッチに適したＣＰＵを見つけられなかったのであり、したがって、スレッドｔは実行可能待ち行列に入れられて、前述のスレッド選択関数によって選択されたときにその待ち行列から最終的にディスパッチされるのを待つ。したがってＣＰＵ選択関数は、スレッド選択関数と同様に、ＣＰＵを選択せずにスレッドｔを最終的には実行可能待ち行列に入れることになっても、非理想ノード中の使用されていないＣＰＵを選択するのを拒むことができることが認められる。
【００６５】
一般に、本発明の例示の実施形態を実装するために実行されるルーチンは、オペレーティング・システムの一部として実装されようとも、あるいは特定のアプリケーション、プログラム、オブジェクト、モジュールまたは命令のシーケンスとして実装されようとも、本明細書では「コンピュータ・プログラム」または単に「プログラム」と呼ぶことができる。このコンピュータ・プログラムは、通常、本発明によるコンピュータ・システムにおける装置またはシステム中の１つまたは複数のプロセッサによって読み取られ、実行されたときに、それらの装置またはシステムに、本発明の様々な態様を実施するステップを実行させ、または要素を生成させるのに必要なステップを実施させる命令を含む。さらに、以上、本発明を完全に機能するコンピュータ・システムの状況で説明し、以下においてもその状況で説明するが、本発明の様々な実施形態を様々な形のプログラム製品として配布することもでき、本発明は、実際にその配布を実行するために使用される信号搬送媒体の個々のタイプにかかわらず、同等に適用されるものである。信号搬送媒体の例には、それだけに限らないが、揮発性および不揮発性メモリ装置、フレキシブル・ディスク、ハードディスク・ドライブ、ＣＤ−ＲＯＭ、ＤＶＤ、磁気テープなどの記録可能型媒体、および無線通信リンクを含む、ディジタルおよびアナログ通信リンクなどの伝送型媒体が含まれる。信号搬送媒体の例が、図２に、メモリ２１０および記憶装置２２４として示されている。
【産業上の利用可能性】
【００６６】
前述のスレッド選択アルゴリズムの挙動について、いくつかの知見を述べることができる。前述のディスパッチャは、どのＣＰＵやＣＰＵグループにも関連づけられていない単一の実行可能待ち行列がある場合であっても、ＮＵＭＡを意識した挙動を実現する。（１つの指定理想ノードおよび１つの指定理想ＣＰＵを持つ）ほとんどのスレッドでは、一般に、プロセッサＰが少なくともそのスレッドの理想ノード中にない限り、そのスレッドがディスパッチのために選択されることはない。理想ノード内では、Ｐをその理想プロセッサとするスレッドが、Ｐがその理想ノード中にあるがその理想プロセッサではないスレッドにわずかに優先される。Ｐがそのスレッドがそこで実行された最後のプロセッサであり、かつ他の一定の条件が満たされた場合（ステップ７１２の（３）〜（５）参照）は、それ以上その待ち行列を考察せずに、スレッドが理想候補として直ちに選択される。最後のプロセッサが有意なのは、そのノードのローカル・メモリのみならず、そのプロセッサのキャッシュにも有用なデータが存在し得るからである。プロセッサＰが、そのスレッドがそこで実行された最後のプロセッサではないが、その理想ノード中にあり、またはその理想プロセッサである場合は、ｉｄｅａｌ＿ＣＰＵ＿ｈｉｔおよびｉｄｅａｌ＿ｎｏｄｅ＿ｈｉｔ変数によって仮の選択を行い、その待ち行列を探索している間に、より良い候補が見つかった場合は、それを指定変更する。このスレッド選択アルゴリズムは、スレッドが待ち行列上で待機している場合であっても、必ずしもスレッドを選択するとは限らない。最後に、待ち行列上で待機するスレッドは、Ｐがそのスレッドの理想ノードまたは理想プロセッサとマッチしなくとも、結局は、ディスパッチのために選択される。
【００６７】
理想ノードを指定した結果として、スレッドは、その理想プロセッサが使用可能でない場合でも、同じノードで実行されやすくなる。ページャは、そのページ要求を生成したプロセッサのノードのローカル・メモリにページングされたデータをロードし、したがって、そのスレッドが必要とするデータは、指定された理想ノードのローカル実メモリに蓄積されやすくなる。その結果、ノード配置を考慮に入れない同様のタスク・ディスパッチャを用いた場合よりも、あるＣＰＵからそのシステムの分散実メモリへのメモリ・アクセスのより大きな部分が、ノード境界をまたいだメモリ・アクセスではなく、そのＣＰＵのノードにあるローカル実メモリにアクセスすることになる。ノード内メモリ・アクセスの割合が増加すれば、メモリ・アクセス時間が短縮され、ノード間通信媒体上のトラフィックが減少することによって、システム・スループットが向上する。
【００６８】
その他の代替実施形態
以上、ＮＵＭＡシステムでスレッドをディスパッチするための具体的なアルゴリズムを、好ましい一実施形態として詳細に説明してきた。しかし、前述のアルゴリズムでは多くの変形形態が可能であることが理解されるであろう。選択される正確なアルゴリズムは、しばしば、それを設計する対象となるコンピュータ・システムに特有の様々なハードウェア的およびソフトウェア的考慮事項に左右される。一般に、待ち時間の長い実メモリ・アクセスを減らすために、分散メモリ・システムのサブセットに関してプロセッサの物理的配置を考慮に入れる、共通実行可能待ち行列からのスレッド・ディスパッチ・アルゴリズムであればどれでも使用できるであろう。最も自明の代替実施形態は、好ましい実施形態に関して本明細書で述べた１つまたは複数の条件を取り除くこと、または本明細書で述べたアルゴリズムに何らかの条件を付加することであろう。その他の変形形態のいくつかの具体例を以下に示すが、それらは例として言及されるものにすぎず、可能な代替形態の網羅的リストとみなすべきではないことを理解されたい。
【００６９】
一代替形態では、理想プロセッサも理想ノードも指定する必要がない。プロセスまたはスレッドを最初に実行するプロセッサは、ランダムに決定することができる。スレッド選択アルゴリズムは、単に、目標プロセッサ上または同じノード中の別のプロセッサ上で最後に実行されたスレッドを優先する。同じノード中のプロセッサが優先されるので、そのスレッドは、理想指定がないにもかかわらず、一貫したノードで実行されやすくなる。
【００７０】
別の代替形態では、前述の論理とは対照的に、数学的評価関数によってスレッドを選択することができる。この評価関数は、待ち行列中の各スレッドごとに評価スコアを提供し、最適スコアを持つスレッドがディスパッチのために選択される。そうした評価関数は例えば、以下の形のものとすることができる。
Ｆ１（ｗａｉｔ＿ｔｉｍｅ）＋Ｆ２（ノード）＋Ｆ３（ＣＰＵ）＋Ｆ４（優先度）＋．．．
式中、ＦＮは、それぞれの独立変数の数値関数である。もちろん、そうした評価関数はより複雑なものとすることもできる。
【００７１】
前述の好ましい実施形態では、ＮＵＭＡコンピュータ・システムを、アーキテクチャ的には、それぞれが内部バス、プロセッサ、ローカル・メモリなどを備え、ノード間通信媒体によって相互に結合された、半独立ノードの集合体として設計される。この設計手法の利点の中には、拡張性およびモジュール性が含まれる。さらに、そうしたＮＵＭＡシステム・アーキテクチャのいくつかの例が構築され、公開されており、したがって、この手法に関する若干の実際的な経験がすでに得られている。しかし、本発明によるＮＵＭＡシステムは、必ずしもそうしたノード・モデル上で設計される必要はないはずである。スレッドまたはタスクを実行するプロセッサを選択する際に非均一メモリ・アクセスを考慮するディスパッチャは、そのシステムが、本明細書で述べたノード・システム以外の何らかの設計モデルに基づくものであったとしても、どんなＮＵＭＡシステムにおいても価値がある可能性がある。したがって、非均一メモリ・アクセスの特徴を示す、現在知られている、または今後開発される、どんな代替のシステム・アーキテクチャも使用できると考えられる。そうした代替アーキテクチャの一例として、ＮＵＭＡシステムは、メモリ・バスがインターフェイスによってリンクされたバス・セグメントの連結網を含み、一部のメモリ・アクセスは１つのバス・セグメントだけを必要とするが、他のメモリ・アクセスは複数のセグメントを横断し、したがって、より長時間を必要とする、複雑なメモリ・バス構造を持つシステムとすることもできる。他の代替形態も可能であろう。さらに、好ましい実施形態では、メモリ・アクセスが２つのクラス（ノード内およびノード間）に分けられるが、システムは、各クラスが異なるそれぞれのアクセス時間を必要とする、３つ以上のメモリ・アクセスのクラスを持つこともできる。
【００７２】
以上、本明細書では例として、本発明の具体的な実施形態について説明してきたが、本発明の精神および範囲から逸脱することなく、様々な変更を加えることもできることが理解されるであろう。したがって、本発明の保護の範囲は、添付の特許請求の範囲およびその均等物によってのみ限定されるものである。
【図面の簡単な説明】
【００７３】
【図１】本発明の好ましい実施形態による、マルチノード、マルチプロセッサ・コンピュータ・システムの主要構成要素を示す上位レベルの構成図である。
【図２】好ましい実施形態による、マルチノード・コンピュータ・システムの典型的ノードの主要ハードウェア構成要素を示す構成図である。
【図３】好ましい実施形態１００による、マルチノード・コンピュータ・システムにおける、異なる抽象化レベルでのハードウェアおよびソフトウェア機能の分割を示す概念図である。
【図４】好ましい実施形態による、ディスパッチャによって使用される、使用可能プロセッサを待つスレッドの実行可能待ち行列の構造を示す図である。
【図５】好ましい実施形態による、ディスパッチャによって使用される実行可能待ち行列からのあるスレッド別情報を示す図である。
【図６】好ましい実施形態による、ある種のスレッド制御値の初期設定を示す上位レベルの流れ図である。
【図７】図８と合わせて、好ましい実施形態による実行のためのスレッドの選択を示す流れ図である。
【図８】図７と合わせて、好ましい実施形態による実行のためのスレッドの選択を示す流れ図である。
【図９】好ましい実施形態による、新規に実行可能になったスレッドを実行するためのＣＰＵの選択を示す流れ図である。
【図１】
2005508545.tif 000003
【図２】
2005508545.tif 000004
【図３】
2005508545.tif 000005
【図４】
2005508545.tif 000006
【図５】
2005508545.tif 000007
【図６】
2005508545.tif 000008
【図７】
2005508545.tif 000009
【図８】
2005508545.tif 000010
【図９】
2005508545.tif 000011
【国際公開パンフレット】
2005508545.tif 000012
2005508545.tif 000013
2005508545.tif 000014
2005508545.tif 000015
2005508545.tif 000016
2005508545.tif 000017
2005508545.tif 000018
2005508545.tif 000019
2005508545.tif 000020
2005508545.tif 000021
2005508545.tif 000022
2005508545.tif 000023
2005508545.tif 000024
2005508545.tif 000025
2005508545.tif 000026
2005508545.tif 000027
2005508545.tif 000028
2005508545.tif 000029
2005508545.tif 000030
2005508545.tif 000031
2005508545.tif 000032
2005508545.tif 000033
2005508545.tif 000034
2005508545.tif 000035
2005508545.tif 000036
2005508545.tif 000037
2005508545.tif 000038
2005508545.tif 000039
2005508545.tif 000040
2005508545.tif 000041
2005508545.tif 000042
2005508545.tif 000043
2005508545.tif 000044
2005508545.tif 000045
2005508545.tif 000046
2005508545.tif 000047
2005508545.tif 000048
2005508545.tif 000049
2005508545.tif 000050
2005508545.tif 000051
【国際調査報告】
2005508545.tif 000052