(57)【特許請求の範囲】
【請求項１】
ローカル処理ノードに置かれた装置であって、該ローカル処理ノードはメインメモリのローカル部分を具え、該ローカル処理ノードは１つまたは２つ以上の追加処理ノードを具えたコンピュータ・システムに置かれており、各追加処理ノードはメインメモリのリモート部分を具え、前記装置は前記コンピュータ・システムにおけるメモリ・ページの移動を制御するものにおいて、前記装置は、
前記コンピュータ・システムの各領域のカウントを、メインメモリの前記ローカル部分に置かれている各メモリ・ページごとにストアしておく記憶機構であって、各領域は前記コンピュータ・システムの１つまたは２つ以上の処理ノードを収容している記憶機構と、
メモリ・アクセス要求によってアドレスされたメモリ・ページをメインメモリの該ローカル部分からリクエスタ処理ノードへ移動しておくべきかどうかを決定するページ移動コントローラであって、前記メモリ・アクセス要求は前記リクエスタ処理ノードから出されたものであるページ移動コントローラとを具え、
該ページ移動コントローラは、
前記記憶機構にアクセスして、前記アドレスされたメモリ・ページと該リクエスタ処理ノードに関連づけられた第１カウントと、該アドレスされたメモリ・ページと前記ローカル処理ノードに関連づけられた第２カウントを取得する手段と、
前記リクエスタ処理ノードから発せられる前記メモリ・アクセス要求に応答して前記第１カウントをインクリメントするインクリメンタと、
前記インクリメントされた第１カウントを前記記憶機構にストアする手段と、
前記第２カウントと該インクリメントされた第１カウントとの差が移動しきい値より大であるとき移動信号を発行する移動信号発行手段と
を具えていることを特徴とする装置。
【請求項２】
請求項１に記載の装置において、前記移動信号発行手段は、
前記第２カウントを前記インクリメントされた第１カウントから減算して該第２カウントと該インクリメントされた第１カウントとの差を得るための減算器と、
前記差が前記移動しきい値より大であるかどうかを判定するコンパレータと、
前記差が前記移動しきい値より大であれば前記移動信号を発行するコントローラとを具えていることを特徴とする装置。
【請求項３】
請求項２に記載の装置において、前記ページ移動コントローラは、
前記コンピュータ・システムの各領域ごとに移動しきい値を格納しておく移動しきい値レジスタと、
前記リクエスタ処理ノードが置かれている該コンピュータ・システムの領域に関連づけられた移動しきい値を前記移動しきい値レジスタから取り出す手段と、
前記取り出した移動しきい値を前記コンパレータへ渡す手段と
をさらに具えていることを特徴とする装置。
【請求項４】
請求項１に記載の装置において、前記コンピュータ・システムは、前記移動信号を受けたときにそれに応答して、前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動する手段を含んでいることを特徴とする装置。
【請求項５】
請求項２に記載の装置において、前記コントローラは、前記差が前記移動しきい値より大であるとき前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させることを特徴とする装置。
【請求項６】
請求項１に記載の装置において、前記第１カウントは、前記リクエスタ処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、前記アドレスされたメモリ・ページが何回アクセスされたかを示し、前記第２カウントは、前記ローカル処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、該アドレスされたメモリ・ページが何回アクセスされたかを示していることを特徴とする装置。
【請求項７】
ローカル処理ノードに置かれたページ移動コントローラであって、該ローカル処理ノードはメインメモリのローカル部分を具え、該ローカル処理ノードは１つまたは２つ以上の追加処理ノードを具え、コンピュータ・システムに置かれており、各追加処理ノードはメインメモリのリモート部分を具え、前記ローカル処理ノードは前記コンピュータ・システムの各領域のカウントを、メインメモリの前記ローカル部分に置かれている各メモリ・ページごとにストアしておく記憶機構も具えており、各領域は前記コンピュータ・システムの１つまたは２つ以上の処理ノードを収容しており、前記ページ移動コントローラはメモリ・アクセス要求によってアドレスされたメモリ・ページをメインメモリの前記ローカル部分からリクエスタ処理ノードへ移動しておくべきかどうかを決定し、前記メモリ・アクセス要求は前記リクエスタ処理ノードから出されたものであって、前記ページ移動コントローラは、
前記記憶機構にアクセスして、前記アドレスされたメモリ・ページと該リクエスタ処理ノードに関連づけられた第１カウントと、該アドレスされたメモリ・ページと前記ローカル処理ノードに関連づけられた第２カウントを取得する手段と、
前記リクエスタ処理ノードから発せられる前記メモリ・アクセス要求に応答して前記第１カウントをインクリメントするインクリメンタと、
前記インクリメントされた第１カウントを該記憶機構にストアする手段と、
前記第２カウントと該インクリメントされた第１カウントとの差が移動しきい値より大であるとき移動信号を発行する移動信号発行手段と
を具えていることを特徴とするページ移動コントローラ。
【請求項８】
請求項７に記載のページ移動コントローラにおいて、前記移動信号発行手段は、
前記第２カウントを前記インクリメントされた第１カウントから減算して該第２カウントと該インクリメントされた第１カウントとの差を得るための減算器と、
前記差が前記移動しきい値より大であるかどうかを判定するコンパレータと、
前記差が前記移動しきい値より大であれば前記移動信号を発行するコントローラとを具えていることを特徴とするページ移動コントローラ。
【請求項９】
請求項８に記載のページ移動コントローラにおいて、前記ページ移動コントローラは、
前記コンピュータ・システムの各領域ごとに移動しきい値を格納しておく移動しきい値レジスタと、
前記リクエスタ処理ノードが置かれている該コンピュータ・システムの領域に関連づけられた移動しきい値を前記移動しきい値レジスタから取り出す手段と、
前記取り出した移動しきい値を前記コンパレータへ渡す手段と
をさらに具えていることを特徴とするページ移動コントローラ。
【請求項１０】
請求項７に記載のページ移動コントローラにおいて、前記コンピュータ・システムは、前記移動信号を受けたときにそれに応答して、前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動する手段を含んでいることを特徴とするページ移動コントローラ。
【請求項１１】
請求項８に記載のページ移動コントローラにおいて、前記コントローラは、前記差が前記移動しきい値より大であるとき前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させることを特徴とするページ移動コントローラ。
【請求項１２】
請求項７に記載のページ移動コントローラにおいて、前記第１カウントは、前記リクエスタ処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、前記アドレスされたメモリ・ページが何回アクセスされたかを示し、前記第２カウントは、前記ローカル処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、該アドレスされたメモリ・ページが何回アクセスされたかを示していることを特徴とするページ移動コントローラ。
【請求項１３】
複数の処理ノードを具えたメモリ・コンピュータ・システムであって、各処理ノードは、
複数のメモリ・ページを有するメインメモリのローカル部分と、
前記コンピュータ・システムの各領域のカウントを、メインメモリの前記ローカル部分に置かれている各メモリ・ページごとにストアしておく記憶機構であって、各領域は前記コンピュータ・システムの１つまたは２つ以上の処理ノードを収容している記憶機構と、
メモリ・アクセス要求によってアドレスされたメモリ・ページをメインメモリの該ローカル部分からリクエスタ処理ノードへ移動しておくべきかどうかを決定するページ移動コントローラであって、前記メモリ・アクセス要求は前記リクエスタ処理ノードから出されたものであるページ移動コントローラとを具え、
該ページ移動コントローラは、
前記記憶機構にアクセスして、前記アドレスされたメモリ・ページと該リクエスタ処理ノードに関連づけられた第１カウントと、該アドレスされたメモリ・ページと前記ローカル処理ノードに関連づけられた第２カウントを取得する手段と、
前記リクエスタ処理ノードから発せられる前記メモリ・アクセス要求に応答して前記第１カウントをインクリメントするインクリメンタと、
前記インクリメントされた第１カウントを前記記憶機構にストアする手段と、
前記第２カウントと該インクリメントされた第１カウントとの差が移動しきい値より大であるとき移動信号を発行する移動信号発行手段と
を具えていることを特徴とするメモリ・コンピュータ・システム。
【請求項１４】
請求項１３に記載のメモリ・コンピュータ・システムにおいて、前記移動信号発行手段は、
前記第２カウントを前記インクリメントされた第１カウントから減算して該第２カウントと該インクリメントされた第１カウントとの差を得るための減算器と、
前記差が前記移動しきい値より大であるかどうかを判定するコンパレータと、
前記差が前記移動しきい値より大であれば前記移動信号を発行するコントローラとを具えていることを特徴とするメモリ・コンピュータ・システム。
【請求項１５】
請求項１４に記載のメモリ・コンピュータ・システムにおいて、前記ページ移動コントローラは、
前記コンピュータ・システムの各領域ごとに移動しきい値を格納しておく移動しきい値レジスタと、
前記リクエスタ処理ノードが置かれている該コンピュータ・システムの領域に関連づけられた移動しきい値を前記移動しきい値レジスタから取り出す手段と、
前記取り出した移動しきい値を前記コンパレータへ渡す手段と
をさらに具えていることを特徴とするメモリ・コンピュータ・システム。
【請求項１６】
請求項１３に記載のメモリ・コンピュータ・システムにおいて、前記コンピュータ・システムは、前記移動信号を受けたときにそれに応答して、前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動する手段を含んでいることを特徴とするメモリ・コンピュータ・システム。
【請求項１７】
請求項１４に記載のメモリ・コンピュータ・システムにおいて、前記コントローラは、前記差が前記移動しきい値より大であるとき前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させることを特徴とするメモリ・コンピュータ・システム。
【請求項１８】
請求項１３に記載のメモリ・コンピュータ・システムにおいて、前記第１カウントは、前記リクエスタ処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、前記アドレスされたメモリ・ページが何回アクセスされたかを示し、前記第２カウントは、前記ローカル処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、該アドレスされたメモリ・ページが何回アクセスされたかを示していることを特徴とするメモリ・コンピュータ・システム。
【請求項１９】
メモリ・アクセス要求によってアドレスされたメモリ・ページを、該メモリ・ページがストアされているローカル処理ノードから前記メモリ・アクセス要求が出されたリクエスタ処理ノードへ移動しておくべきかどうかを決定するページ移動コントローラであって、
前記アドレスされたメモリ・ページと該リクエスタ処理ノードに関連づけられた第１カウントと、該アドレスされたメモリ・ページと前記ローカル処理ノードに関連づけられた第２カウントを取得する手段と、
前記リクエスタ処理ノードから発せられる前記メモリ・アクセス要求に応答して前記第１カウントをインクリメントするインクリメンタと、
前記第２カウントと該インクリメントされた第１カウントとの差が移動しきい値より大であるとき移動信号を発行する移動信号発行手段と
を具えていることを特徴とするページ移動コントローラ。
【請求項２０】
請求項１９に記載のページ移動コントローラにおいて、前記移動信号発行手段は、
前記第２カウントを前記インクリメントされた第１カウントから減算して該第２カウントと該インクリメントされた第１カウントとの差を得るための減算器と、
前記差が前記移動しきい値より大であるかどうかを判定するコンパレータと、
前記差が前記移動しきい値より大であれば前記移動信号を発行するコントローラとを具えていることを特徴とするページ移動コントローラ。
【請求項２１】
請求項２０に記載のページ移動コントローラにおいて、前記コントローラは、前記差が前記移動しきい値より大であるとき前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させることを特徴とするページ移動コントローラ。
【請求項２２】
請求項１９に記載のページ移動コントローラにおいて、前記第１カウントは、前記リクエスタ処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、前記アドレスされたメモリ・ページが何回アクセスされたかを示し、前記第２カウントは、前記ローカル処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、該アドレスされたメモリ・ページが何回アクセスされたかを示していることを特徴とするページ移動コントローラ。
【請求項２３】
メモリ・アクセス要求によってアドレスされたメモリ・ページを、該メモリ・ページがストアされているローカル処理ノードから前記メモリ・アクセス要求が出されたリクエスタ処理ノードを移動しておくべきかどうかを決定する、コンピュータで実施される方法であって、
前記アドレスされたメモリ・ページと前記リクエスタ処理ノードに関連づけられた第１カウントと、該アドレスされたメモリ・ページと前記ローカル処理ノードに関連づけられた第２カウントとを取得するステップと、
前記リクエスタ処理ノードから発せられる前記メモリ・アクセス要求に応答して前記第１カウントをインクリメントするステップと、
前記第２カウントと前記インクリメントされた第１カウントとの差が移動しきい値より大であれば、移動信号を出すステップと
を具えたことを特徴とする方法。
【請求項２４】
請求項２３に記載の方法において、
前記移動信号を受けたときにそれに応答して、前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させるステップをさらに具えたことを特徴とする方法。
【請求項２５】
請求項２３に記載の方法において、
前記差が前記移動しきい値より大であれば、前記アドレスされたメモリ・ページを前記ローカル処理ノードから前記リクエスタ処理ノードへ移動させるステップをさらに具えたことを特徴とする方法。
【請求項２６】
請求項２３に記載の方法において、前記第１カウントは、前記リクエスタ処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、前記アドレスされたメモリ・ページが何回アクセスされたかを示し、前記第２カウントは、前記ローカル処理ノードが置かれている領域内のプロセッサによるキャッシュ・ミスを埋め合わす目的で、該アドレスされたメモリ・ページが何回アクセスされたかを示していることを特徴とする方法。
【請求項２７】
請求項１に記載の装置において、前記インクリメンタは、前記第１カウントのスタティスティカル・インクリメント（ｓｔａｔｉｓｔｉｃａｌ  ｉｎｃｒｅｍｅｎｔ）を行うことを特徴とする装置。
【発明の詳細な説明】
発明の背景
発明の分野
本発明は、一般的には、分散メモリを装備するコンピュータ・システムにおけるデータの割振りに関し、具体的には、分散化された非一様ないし不均一メモリ・アクセス（non-uniform memory access-ＮＵＭＡ）コンピュータ・システムにおけるメモリ・ページの移動に関する。
関連技術
分散メモリ・コンピュータ・システムは、各々に１つまたは２つ以上のプロセッサが置かれている。物理的に離散し分離されている複数の処理ノードと、これらのプロセッサのどれからでもアクセスができるメインメモリとから構成されているのが代表的である。メインメモリは処理ノード間で物理的に分散化されている。言い換えれば、各処理ノードはメインメモリの一部を備えている。従って、各プロセッサからは、「ローカル」メインメモリ（つまり、プロセッサと同じ処理ノードに置かれているメインメモリの部分）と「リモート」メインメモリ（つまり、他の処理ノードに置かれているメインメモリの部分）が存在するように見える。
各プロセッサでは、ローカル・メインメモリをアクセスするときに起こるレイテンシ（latency：待ち時間）は、リモート・メインメモリをアクセスするときに起こるレイテンシよりも大幅に小さくなっている。従って、上述した分散メモリ・コンピュータ・システムは不均一メモリ・アクセス（non-uniform memory access-ＮＵＭＡ）コンピュータ・システムとも呼ばれている。
ＮＵＭＡコンピュータ・システムでは、最も頻繁にデータをアクセスするプロセッサと同じ処理ノード（または最も頻繁にデータをアクセスするプロセッサにできる限り近くに置かれた処理ノード）に置かれているメインメモリ部分にデータをストアしておくことが望ましい。言い換えれば、最も頻繁にデータをアクセスするプロセッサが置かれている処理ノードにデータを移しておくことが望ましい。このようにすると、メモリ・アクセス・レイテンシは減少するのでシステム全体のパフォーマンスが向上することになる。
この目標は、１つだけのプロセスによって使用される私有データ（private data）の場合には達成が容易である。この場合には、オペレーティング・システムは、プロセスが実行されようとするプロセッサと同じ処理ノードに置かれているメインメモリ部分にデータを移している。しかし、多数のプロセス（各プロセスは異なる処理ノードで実行されている可能性がある）によってアクセスされる共有データ（shared data）の場合には、オペレーティング・システムはどのプロセスが最も頻繁に共有データをアクセスするかについては知らないのが一般的である。私有データの場合でも、あるプロセスが移動されたとき（つまり、ある処理ノードから別の処理ノードへ転送されたとき）、そのプロセスが最終的には元のノードに戻されることを予想して、最も頻繁に使用されるデータだけを新しいノードに移しておいた方が合理的な場合がある。
キャッシュオンリ・メモリ・アーキテクチャ（cache-only memory architecture-ＣＯＭＡ）は、メモリ・アクセス・レイテンシを低減化するためにＮＵＭＡコンピュータ・システムでデータを移動する１つのハードウェア方式として知られている。ＣＯＭＡは、データをアクセスしようとするプロセッサの近くにデータを移しておく働きをする。ＣＯＭＡでは、メインメモリはキャッシュメモリとして扱われている。ＣＯＭＡは、改良キャッシュ・コヒーレンシ・プロトコル（modified cache coherency protocol）を使用してこの機能性を達成している。従来のキャッシュ・コヒーレンシ・プロトコルと異なり、ＣＯＭＡキャッシュ・コヒーレンシ・プロトコルはメモリ・ブロック置換（memory block replacement）およびマルチレベル・キャッシュ包含（multi-level cache inclusion）の実施という問題を取り扱わなければならない。以上のように、ＣＯＭＡはキャッシュ・コヒーレンシ・プロトコルを複雑化するので、望ましいソリューションではない。
ＣＯＭＡでは、キャッシュ・ミス（cache miss）を処理するとき、ローカル・メインメモリとリモート・メインメモリ（これがダーティである）を順次にアクセスして、ローカル・メインメモリに見つからなかったメモリ・ロケーションをアクセスするようにしている。ＣＯＭＡでは、これらのメモリ・ルックアップ（memory look-up：メモリ参照）を行うためにも、キャッシュ・ミスが満足されたときローカル・メモリの最終的割振りを行うためにも、相対的に大きなメモリ・バンド幅が必要である。従って、ＣＯＭＡアーキテクチャは、一般的に、他のアーキテクチャよりもパフォーマンスが低く、他のアーキテクチャよりもメモリ・レイテンシが高くなっている。
ＣＯＭＡでは、すべてのメモリ・ブロック（３２バイトから１２８バイトのメモリであるのが代表的）にキャッシュ・タグ（cache tag）を付けている。これらのキャッシュ・タグは高価なスタチック・ランダムアクセスメモリ（static random access memory-ＳＲＡＭ）に保存されていることが多い（安価なダイナミックＲＡＭにではなく）。従って、ＣＯＭＡに関連するメモリ・オーバヘッドが大になる潜在性をもっている。
メモリ・アクセス・レイテンシを低減化するためにＮＵＭＡコンピュータ・システムでデータを移動するソフトウェア方式も提案されている。１つの方式では、ソフトウェアは処理ノードごとにメモリ・ページごとのカウンタを維持している。ソフトウェアがキャッシュ・ミスのたびにカウンタを更新していないのは、ソフトウェアをそのように動作させると、重大なシステム・パフォーマンス低下が起こるためである。その代わりに、ソフトウェアはＴＬＢ（translation look-aside buffer：変換索引バッファ）ミスが起こるたびに、ノードのカウンタをインクリメントしている。代表例として、カウンタはＴＬＢ例外ハンドラ（TLB exception handler）によって更新されている。
この公知ソフトウェア方式によると、（キャッシュ・ミスが起こるたびにカウンタを更新する場合に比べて）パフォーマンスに対する影響が低減されるが、それでもなお、オペレーティング・システムの中でパフォーマンス上非常に重要な部分にソフトウェア命令が追加されている。さらに、ＴＬＢミスの数は必ずしもあるページに起こるキャッシュ・ミスの数と相関関係がない。従って、ＴＬＢミスが起こったときページ移動を行うようにすると、該当ノードへのページ移動が著しく遅延したり、ページが誤ってあるノードから別のノードへ移動されるおそれがある。
以上の理由により、メモリ・アクセス・レイテンシを低減化するためにＮＵＭＡコンピュータ・システムでデータを移動する改良システムと方法が要望されている。
発明の概要
本発明は、メインメモリのローカル部分を含んでいるローカル処理ノードにおける装置を提供することを目的としている。ローカル処理ノードは１つまたは２つ以上の追加処理ノードからなるコンピュータ・システムに置かれており、そこでは、各々の追加処理ノードはメインメモリのリモート部分を含んでいる。本装置は、コンピュータ・システムにおけるメモリ・ページの移動（migration of memory pages）を制御するものである。
本装置はコンピュータ・システムの各領域（region）のカウントを、メインメモリのローカル部分に置かれている各メモリ・ページごとにストアしておくアレイ（array：配列）を含んでいる。各領域には、コンピュータ・システムの１つまたは２つ以上の処理ノードが収容されている。また、本装置は、メモリ要求によってアドレスされたメモリ・ページをメインメモリのローカル部分からリクエスタ（要求側）処理ノード（そのメモリ要求がリクエスタ処理ノードから出された場所）へ移動しておくべきかどうかを決定するページ移動コントローラ（page migration controller）も含んでいる。
ページ移動コントローラはアレイをアクセスし、アドレスされたメモリ・ページとリクエスタ処理ノードに関連づけられた第１カウント（first count）と、アドレスされたメモリ・ページとローカル処理ノードに関連づけられた第２カウント（second count）を取得する。第１カウントはインクリメントされ、そのあと第２カウントはインクリメントされた第１カウントから減算されて、第２カウントとインクリメントされた第１カウントとの差が得られる。コンパレータ（比較器）は、その差が移動のしきい値（migration threshold value）より大であるかどうかを決定する。差が移動しきい値より大であれば、移動割込み（migration interrupt）が出される。ソフトウェアはこの移動割込みを受け取り、メモリ・ページを移動すべきかどうかを決定する。
本発明のその他の特徴と利点は、本発明の種々実施例の構造およびオペレーションと共に、添付図面を参照して以下で詳しく説明する。図面において、同一または機能的に類似のエレメントは類似の参照符号を付けて示されている。
【図面の簡単な説明】
以下、添付図面を参照して本発明について説明する。添付図面において、
図１は、不均一メモリ・アクセス（ＮＵＭＡ）コンピュータ・システムを示すブロック図である。
図２Ａは、メインメモリの部分を示すブロック図である。
図２Ｂは、図２Ａのメインメモリ部分に関連するアレイを示すブロック図である。
図３は、図２Ｂのアレイのエントリを示すブロック図である。
図４は、本発明の好適実施例によるページ移動コントローラを示す機能ブロック図である。
図５は、図４のページ移動コントローラのオペレーションを示すフローチャートである。
好適実施例の詳細な説明
本発明は、メモリ・アクセス・レイテンシを低減するためにＮＵＭＡ（不均一メモリ・アクセス）コンピュータ・システムでデータを移動する改良システムおよび方法を提供することを目的としている。本発明は、データ・アイテム（項目）を最も頻繁にアクセスするプロセッサが置かれている処理ノードへ、またはその近くにそのデータ・アイテムを移動する（migrateないしtransfer）ように動作する。
このようなデータ移動はハードウェアとソフトウェアの組合せを通して達成されている。本発明によれば、処理ノード（参照の便宜上ローカル・ノードと呼ぶことにする）内のハードウェアは、ＮＵＭＡコンピュータ・システムの各処理ノードのカウントをローカル・メインメモリ（つまり、ローカル・ノードに置かれているメインメモリ部分）の各ページごとに維持している（代替実施例では、カウントは後述するように、処理ノード群と関連づけられている）。メモリ・アクセス要求（memory access request）があるたびに、ハードウェアはリクエスタ・ノード（つまり、メモリ・アクセス要求を出したプロセッサが置かれている処理ノード）に関連するカウントをインクリメントする。一実施例では、メモリ・アクセス要求の目的はキャッシュ・ミスを埋め合わせる（fill）ことである。その場合には、リクエスタ・ノードはキャッシュ・ミスが起こったプロセッサが置かれている処理ノードである。
ハードウェアはリクエスタ・ノードのカウントをローカル・ノードに関連するカウントと比較する。リクエスタ・ノードのカウントがローカル・ノードのカウントより十分に高ければ、ソフトウェア・プロセスにそのことが通知される（例えば、割込みまたはポーリングを通して）。ソフトウェア・プロセスは特定のメモリ・ページをリクエスタ・ノードに移動させる場合もあれば、そのリクエスタ・ノードの近くに移動させる場合もある。
以下、本発明について詳しく説明する。図１は分散メモリ・コンピュータ・システム１０２、好ましくは、分散化された不均一メモリ・アクセス（ＮＵＭＡ）コンピュータ・システム１０２を示すブロック図である。コンピュータ・システム１０２は複数の処理ノード１０４を含んでおり、これらは物理的に区別され、相互に物理的に分離されている。処理ノード１０４は通身ネットワーク１２０を通して相互に通信している。通信ネットワークとしては、バス、多段相互接続ネットワーク（multistage interconnection network）、ローカルエリア・ネットワーク、広域ネットワークなどの公知のデータ通信手段、またはこれらを任意に組み合わせたものにすることができる。
各処理ノード１０４には、１つまたは２つ以上のコンピューティング・ノード（computing node）１０６が置かれている（好ましくは、処理ノード１０４には２つのコンピューティング・ノード１０６が置かれているが、各処理ノード１０４に置くことができるコンピューティング・ノード１０６の数は２つ以外にすることも可能である）。各コンピューティング・ノード１０６にはプロセッサ１０８とキャッシュ１１０が置かれている。また、各コンピューティング・ノード１０６には、メモリ・コントローラとネットワーク間インタフェース（memory controller and network interface）１１２も置かれている。任意の特定処理ノード１０４内のプロセッサ１０８は、その処理ノード１０４に置かれたメモリ・コントローラとネットワーク間インタフェース１１２を通して通信ネットワーク１２０に接続された他のデバイスと通信する。
各処理ノード１０４には、メインメモリ１１４の部分も置かれている。処理ノード１０４のすべてに置かれているメインメモリ１１４の各部分が集合したものがコンピュータ・システム１０４のメインメモリである。任意の処理ノード１０４内の任意のプロセッサ１０８は、任意の他の処理ノード１０４に置かれているメインメモリ１１４の部分に入っているデータをアクセスすることができる。任意の特定処理ノード１０４のメインメモリ１１４の部分に入っているデータへのアクセスは、その同一処理ノード１０４に置かれているメモリ・コントローラとネットワーク間インタフェース１１２によって制御される。
図２Ａはメインメモリの部分を示す詳細ブロック図である。メインメモリ１１４の各部分には、Ｎ個のメモリ・ページ２０２（各ページには、ページ０，ページ１，...，ページＮのラベルが付いている）が収容されている。好ましくは、各メモリ・ページは４Ｋバイトのサイズになっているが、本発明によれば、他のメモリ・ページ・サイズにしても動作効果は同じである。Ｎの値はどのようにインプリメントするかによって決まる。
図２Ｂは本発明の好適実施例に従って各処理ノード１０４に維持されているアレイ２０４を示すブロック図である。アレイ２０４はメインメモリ１１４の部分に置かれている各メモリ・ページ２０２のエントリ２０６を含んでいる。従って、アレイ２０４はＮ個のエントリ２０６を含んでおり、各エントリにエントリ０，エントリ１，...，エントリＮのラベルが付けられている。エントリ０はメモリ・ページ０に対応し、エントリ１はメモリ・ページ１に対応し、以下同様である。アレイ２０４は好ましくはダイナミック・ランダムアクセスメモリ（ＤＲＡＭ）にストアされている。一実施例では、アレイ２０４はメインメモリ１１４用のキャッシュ・コヒーレント・ディレクトリ部分にストアされている。本発明によれば、アドレスされたページ２０２と、そのアドレスされたページ２０２に関連するアレイ２０４内のエントリ２０６とを同時にアクセスして、取り出すことによってシステム・パフォーマンスを向上させている。
図３はアレイ２０４内のエントリ２０６を示すブロック図である。各エントリ２０６には、Ｎ個のカウント３０４（個々にカウント０，カウント１，...，カウントMのラベルが付いている）がコンピュータ・システム１０２の各領域ごとに１つあて収められている。（従って、アレイ２０４はカウント３０４のバンクを表している。当然に理解されるように、レジスタなどの他の記憶機構を使用してカウント３０４をストアすることも可能である。）コンピュータ・システム１０２にＭ個またはそれ以下の処理ノード１０４がある場合は、領域に単一の処理ノード１０４を置いておくことが好ましく、そうすれば、カウント３０４を単一の処理ノード１０４に対応させることができる。逆に、コンピュータ・システム１０２にＰ個の処理ノード１０４がある場合には、（ただし、ＰはＭより大である）、各領域には複数の処理ノード１０４が置かれることになる。この場合には、各領域にはＱ個の処理ノード１０４を置いておくことが好ましい。ただし、Ｐ／ＱはＭより小か等しい。（当然に理解されるように、どの処理ノード１０４のグループも、領域を表すように設定することができる。）Ｑは８に等しいことが好ましいが、本発明によれば、Ｑが他の値であっても同じ動作効果が得られる。
上述の説明から理解されるように、各カウント３０４は特定の処理ノード１０２に置かれている特定のメモリ・ページ２０２と関連づけられており、コンピュータ・システム１０２の特定の領域とも関連づけられている。カウント３０４は、その領域に置かれているプロセッサ（１つまたは複数）１０８がその特定処理ノード１０２に置かれている、その特定メモリ・ページを何回アクセスしたかを示している。カウント３０４は、本発明によれば、その特定メモリ・ページ２０２をカウント３０４に関連する領域内の処理ノード２０４へ移しておくべきかどうかを判断するために使用される。
図４はページ移動コントローラ４０２を示すブロック図である。ページ移動コントローラ４０２は、好ましくは、メモリ・コントローラとネットワーク間インタフェース１１２の一部として処理ノード１０４に実装されているハードウェア・デバイスになっている。以下では、説明の便宜上、処理ノード１０４Ａのメモリ・コントローラとネットワーク間インタフェース１１２Ａに置かれているページ移動コントローラ４０２について説明することにする（なお、以下の説明はすべてのノード１０４に置かれているページ移動コントローラ４０２にも適用される）。この処理ノード１０４Ａは参照の便宜上ローカル・ノード１０４Ａと呼ぶことにする。ページ移動コントローラ４０２は、ローカル・ノード１０４Ａ側のメモリ・ページをコンピュータ・システム１０２内の他の処理ノード１０４Ｂ，１０４Ｃ（参照の便宜上リモート・ノード１０４Ｂ，１０４Ｃと呼ぶことにする）へ移しておくべきかどうかを決定する。
ページ移動コントローラ４０２内に置かれているコンポーネントはページ移動コントローラ４０２によって実行されるオペレーション（演算、操作など）や機能（function）を表している。ページ移動コントローラ４０２が図４に示され、ここで説明されているオペレーションや機能を実行するようにページ移動コントローラ４０２をどのようにインプリメント（実装）するかは、当該分野の当業者には自明のことである。
以下では、図４を参照して、さらに図５に示す機能フローチャートを参照してページ移動コントローラ４０２のオペレーションについて説明する。なお、理解を容易にするために、以下では、各カウント３０４が単一の処理ノード１０４に対応しているものとして（つまり、各領域には１つの処理ノード１０４が置かれているとして）説明する。しかし、当然に理解されるように、以下の説明は各領域に複数の処理ノード１０４が置かれている場合にも適用される。
ステップ５０６で、ページ移動コントローラ４０２はプロセッサ１０８から出されたメモリ・アクセス要求４50を受け取る。このプロセッサ１０８が置かれている処理ノード１０４は参照の便宜上リクエスタ（要求側）ノード１０４と呼ぶことにする。メモリ・アクセス要求４５０はローカル・ノード１０４Ａに置かれているプロセッサ１０８から出されることもあるが、その場合には、ローカル・ノード１０４Ａはリクエスタ・ノード１０４Ａと同じになっている。また、メモリ・アクセス要求４５０はリモート・ノード１０４Ｂまたは１０４Ｃに置かれているプロセッサ１０８から出されることもあるが、その場合には、ローカル・ノード１０４Ａはリクエスタ・ノード１０４Ｂまたは１０４Ｃと同じになっていない。説明の便宜上、処理ノード１０４Ｃ内のプロセッサ１０８Ｅまたは１０８Ｆがメモリ・アクセス要求を出し、その処理ノード１０４Ｃがリクエスタ・ノード１０４Ｃとなる場合を想定して説明する。
メモリ・アクセス要求４５０には、アクセスしようとするメモリ・ページ２０２を識別する情報が収められている。理解を容易にするために、メモリ・ページ１をアクセスするものとして説明する。また、メモリ・アクセス要求４５０には、リクエスタ・ノード１０４Ｃを指定している情報も収められている。ステップ５０８で、ページ移動コントローラないしカウンタ４０２はメモリ・アクセス要求４５０に入っているこの情報を使用してアレイ２０４をアクセスし、メモリ・ページ１およびリクエスタ・ノード１０４Ｃ（つまり、メモリ・アクセス要求４５０で指定されたメモリ・ページとノード）に関連するカウント３０４を取り出す。
ステップ５１０で、インクリメンタ（増分器）４０４はリクエスタ・ノード１０４Ｃのカウント３０４を１だけインクリメントし、このカウント３０４の新しい値をアレイ２０４にストアする。別の実施例では、統計的インクリメント（statistical increment）が行われるが、このインクリメントでは、リクエスタ・ノードのカウントをインクリメントする確率は１以下になっている。好ましくは、この確率は、Ｎ回のローカル・クロック・サイクルのあと、あるいはＮ個の要求またはＤＲＡＭのリフレッシュ・サイクルのあと各要求をインクリメントするといったように、いくつかの擬似乱数メカニズム（pseudo-random mechanism）の１つによってセットされる。
ステップ５１２から始まるステップのシーケンスおよびステップ５２０から始まるステップのシーケンスはステップ５１０のあとで実行される。具体的には、ステップ５１２から始まるステップのシーケンスはステップ５２０から始まるステップのシーケンスと同時に実行される。まず、ステップ５１２から始まるステップのシーケンスについて説明することにする。
ステップ５１２で、ページ移動コントローラ４０２はアレイ２０４をアクセスし、メモリ・ページ１（つまり、メモリ・アクセス要求４５０で指定された同じメモリ・ページ２０２）とローカル・ノード１０４Ａに関連するカウント３０４を取り出す。
ステップ５１４で、ローカル・ノード１０４Ａのカウント３０４とリクエスタ・ノード１０４Ｃのカウント３０４（インクリメンタ４０４によってインクリメントされている）は減算器（subtractor）４０８に渡される。減算器４０８はローカル・ノード１０４Ａのカウント３０４をリクエスタ・ノード１０４Ｃのカウント３０４から減算し、その差をコンパレータ（比較器）４１２へ送る。減算器４０８とコンパレータ４１２は例えば、演算論理ユニット（arithmetic logic unit-ＡＬＵ）に相当するものとすることも可能である。
ステップ５１６で、コンパレータ４１２は前記の差を移動しきい値レジスタ４１０に格納されている移動しきい値と比較し、差が移動しきい値より大であるかどうかを決定する。この機能の目的は以下で説明する。
メモリ・ページ１をローカル・ノード１０４Ａからリクエスタ・ノード１０４Ｃへ移動するとき若干のシステム・コストが発生する。従って、メモリ・ページ１をリクエスタ・ノード１０４Ｃへ移動するのは、リクエスタ・ノード１０４Ｃによって行われるメモリ・ページ１へのアクセス回数がローカル・ノード１０４Ａによって行われるアクセス回数より十分に大である場合に限るべきである。移動しきい値によって、この移動システム・コストが決まる。差が移動しきい値より大であれば、メモリ・ページ１を移動することが必要である。逆に、差が移動しきい値より小か等しければ、メモリ・ページ１はリクエスタ・ノード１０４Ｃへ移動されない。
移動しきい値はどのようにインプリメントするかによって決まり、コンピュータ・システム１０２のパフォーマンス・パラメータによって決まる。好ましくは、移動しきい値レジスタ４１０に格納される移動しきい値はコンピュータ・システム１０２のすべての領域で同じになっている。別の実施例では、移動しきい値レジスタ４１０はコンピュータ・システム１０２の各領域ごとに移動しきい値を格納している。この別実施例では、移動しきい値は、領域がローカル・ノード１０４Ａからどれだけ離れているか、ページをローカル・ノード１０４Ａから領域へ移動するとき生じる通信コスト、システム負荷量、メモリ・ページの移動ヒストリ（活動記録）などの、いくつかの要因に応じて各領域ごとに指定されている。
移動しきい値はソフトウェアで調整可能であるが、好ましい実施例では、動的に調整されないようになっている。別の実施例では、移動しきい値は各領域ごとに動的に調整されるようになっている。このことは、移動しきい値が１つだけですべての領域に共通している実施例の場合も同じである。このような動的調整はシステム負荷量、実行されるアプリケーションの数とタイプ、ユーザ特性などのいくつかの要因によって決まる。
差が移動しきい値より大でないとステップ５１６において判定されると、ステップ５１２から始まるステップのシーケンスはステップ５１８で示すように完了する。そうでなければ、ステップ５１７が実行される。
ステップ５１７を説明する前に、アレイ２０４のもう１つの特徴を説明しておくことにする。図３に戻って説明すると、すでに説明したように、各エントリ２０６はＭ個のカウント３０４（個別にカウント０，カウント１，...，カウントＭのラベルが付いている）を収めている。本発明の実施例によれば、各エントリ２０６はメモリ・ページ／処理ノード（または領域）別にモードを示しているモード情報も収めている。このモード情報は、好ましくは、オペレーティング・システムによってセットされるが、ユーザ調整可能にすることもできる。本発明によれば、好ましくは、「移動」、「複写」、「移動と複写」、「無視（don't care）」の４つのモードがサポートされている。これらのモードの意味については、以下の説明の中で明らかにする。好ましくは、モード情報は２個のバイナリ・コード化ビットで実現されている。
好ましくは、本発明はページのエントリ２０６で指定されたモードに従って動作する（別の実施例では、本発明はローカル・ノード１０４Ａ全体に対してセットされたモードで動作させることも、あるいはリクエスタ・ノード１０４Ｃのモードで決まるモードで動作させることも可能である）。従って、ステップ５１２（上述した）では、メモリ・ページ１とローカル・ノード１０４Ａに関連するカウント３０４を取り出すほかに、ページ移動コントローラ４０２はアレイ２０４もアクセスして、メモリ・ページ１（つまり、要求されたメモリ・ページ）とローカル・ノード１０４Ａに関連するモード情報を取り出す。
図５に戻って説明すると、ステップ５１７で、ページ移動コントローラ４０２はメモリ・ページ１とローカル・ノード１０４Ａのモードが「移動」または「移動と複写」に等しいかかどうかを決定する。メモリ・ページ１とローカル・ノード１０４Ａのモードが「移動」または「移動と複写」に等しければ、ステップ５２２が実行される。そうでなければ、ステップ５１２から始まるステップのシーケンスはステップ５１８で示すように完了する。
ステップ５２２で、ページ移動コントローラ４０２はメモリ・アクセス要求４５０に入っている情報を、移動／複写候補ページ／ノード・レジスタ４１４に格納する。この情報はアクセスされたページ（つまり、ページ１）とそのページをアクセスしたノード（つまり、リクエスタ・ノード１０４Ｃ）を示している。次に、ページ移動コントローラ４０２は移動割込み４１８を出す（後述するように、ソフトウェア・プロセッサが移動信号を得るためにポーリングする場合には、移動信号を出すことになる）。（別の実施例では、ページ移動コントローラ４０２はステップ５２２でメモリ・ページ１をリクエスタ・ノード１０４Ｃへ移動させる。）
ソフトウェア・プロセス（図示せず）は移動割込み／信号４１８を受信すると、移動／複写候補ページ／ノード・レジスタ４１４にもアクセスして移動ページ／ノード４２０（つまり、メモリ・ページ１とリクエスタ・ノード１０４Ｃを指定している情報）を取得する。ソフトウェア・プロセスは、好ましくは、オペレーティング・システムの一部になっている。ソフトウェア・プロセスはページ１をリクエスタ・ノード１０４Ｃに移動すべきかどうかを決定する。ソフトウェア・プロセスはシステム負荷量、メモリ・ページの移動ヒストリ、ノード・バンド幅アンバランス（imbalance）などの、いくつかの要因を考慮してこの決定を行う。この決定の結果に応じて、ソフトウェア・プロセスはメモリ・ページ１をリクエスタ・ノード１０４Ｃへ移動させることになる。
以下では、ステップ５２０から始まるステップのシーケンスについて説明する。
ステップ５２０で、コンパレータ４５１はリクエスタ・ノード１０４Ｃのカウント３０４を、複写しきい値レジスタ４５２に格納されている複写しきい値と比較する（別の実施例では、リクエスタ・ノード１０４Ｃが置かれている領域に関連するカウントが複写しきい値と比較される）。リクエスタ・ノード１０４Ｃのカウント３０４が複写しきい値より大であれば、メモリ・ページ１をリクエスタ・ノード１０４Ｃに複写することが必要である。従って、ステップ５21が実行されるが、これについては後述する。逆に、リクエスタ・ノード１０４Ｃのカウントが複写しきい値より小か等しければ、メモリ・ページ１はリクエスタ・ノード１０４Ｃに複写されず、処理はステップ５１８で示すように完了する。
ステップ５２１で、ページ移動コントローラ４０２はメモリ・ページ１とローカル・ノード１０４Ａのモードが「複写」または「移動と複写」に等しいかどうかを判断する。メモリ・ページ１とローカル・ノード１０４Ａのモードが「複写」または「移動と複写」に等しければ、ステップ５２２が実行される。そうでなければ、ステップ５２０から始まるステップのシーケンスはステップ５１８で示すように完了する。
ステップ５２２で、ページ移動コントローラ４０２はメモリ・アクセス要求４５０に入っている情報を移動／複写候補ページ／ノード・レジスタ４１４に格納する。この情報はアクセスされたページ（つまり、ページ１）とそのページをアクセスしたノード（つまり、リクエスタ・ノード１０４Ｃ）を示している。そのあと、ページ移動コントローラ４０２は複写割込み４５６を出す（ソフトウェア・プロセスが後述するように複写信号を得るためにポーリングする場合は、複写信号を出す）。（別の実施例では、ページ移動コントローラ４０２はステップ５２２でメモリ・ページ１をリクエスタ・ノード１０４Ｃに複写させる。）
ソフトウェア・プロセス（図示せず）は上述したものと同じソフトウェア・プロセスにすることができるが、複写割込み／信号４５６を受信すると、移動／複写候補ページ／ノード・レジスタ４１４にもアクセスして、複写ページ／ノード４２０（つまり、メモリ・ページ１とリクエスタ・ノード１０４Ｃを指定している情報）を取得する。このソフトウェア・プロセスは好ましくはオペレーティング・システムの一部になっている。ソフトウェア・プロセスはページ１をリクエスタ・ノード１０４Ｃに移動すべきかどうかを判断する。ソフトウェア・プロセスはシステム負荷量、メモリ・ページの移動ヒストリ、ノードバンド幅アンバランスなどの、いくつかの要因を考慮してこの決定を行う。この決定の結果に応じて、ソフトウェア・プロセスはページ１をリクエスタ・ノード１０４Ｃに複写させる。
複写しきい値レジスタ４５２に格納された複写しきい値はノードがメモリ・ページを何回アクセスしたら、メモリ・ページをノードに複写することが有利になるかを示している。移動しきい値に関する考慮事項（上述した）は一般的に複写しきい値にも適用される。
上述したように、ソフトウェア・プロセスは移動割込み４１８（移動割込み４１８が出された場合）および複写割込み４５６（複写割込み４５６が出された場合）を受け取る。また、上述したように、ソフトウェア・プロセスはメモリ・ページをリクエスタ・ノードに移動または複写すべきかどうかを判断するとき、いくつかの要因を考慮する。上述した要因以外にも、考慮される要因がもう１つある。それは、ソフトウェア・プロセスが移動割込み４１８と複写割込み４５６の両方を受け取ったかどうかである。
当然に理解されるように、あるメモリ・ページがローカル・ノードからリクエスタ・ノードへ移動されると、ローカル・ノードに置かれているメモリ・ページのコピーは無効にされる。これに対して、メモリ・ページがリクエスタ・ノードに複写された場合には、ローカル・ノード側のメモリ・ページのコピーは有効になっている（この側面から見た本発明は、主に読取り専用データの場合に効果的であるので、この側面を利用すると、複写する必要のあるページ、つまり、複数のコピーが複数のノードで作成されるようなページを識別することができる）。本発明によれば、メモリ・ページの移動と複写は同時には行われない。
ソフトウェア・プロセスが移動割込み４１８と複写割込み４５６の両方を受け取ると、ソフトウェア・プロセスは移動するのか、複写するのか、どちらも行わないのかを判断する。一実施例では、ソフトウェア・プロセスは複写よりも移動に高い優先度を置いているので、移動割込み４１８と複写割込み４５６の両方を受けたときは、移動が行われるようになっている（ただし、ソフトウェア・プロセスが移動も複写もしないと判断しないことが条件である）。なお、この点におけるソフトウェア・プロセスのオペレーションは、どのようにインプリメントしたかによって決まる。
なお、モードが「無視」のときは、ページ移動コントローラ４０２は移動割込み４１８も複写割込み４５６も出さない。
上述したページ移動コントローラ４０２のオペレーション、具体的には、上述したページ移動コントローラ４０２のコンポーネント間の相互作用は、コントローラ４２２のオペレーションによって達成される。好ましくは、コントローラ４２２は、例えば、ハードウェアのステート・マシン（state machine）でインプリメント（実現）されている。コントローラ４２２をどのようにインプリメントするかは、当該分野の当業者に自明のことである。
また、ページ移動コントローラを実際にどのようにインプリメントするかも、当該分野の当業者に自明のことである。例えば、実用上、ページ移動コントローラ４０２は中間結果を一時的に格納しておく、いくつかのレジスタを装備することが可能である。例えば、あるレジスタをインクリメンタ４０４と減算器４０８の間に置いておくと、減算器４０８の結果を一時的に格納することができる。別のレジスタはアレイ２０４およびインクリメント４０４と減算器４０８の間に置いておくと、アレイ２０４から取り出したカウントを一時的に格納することができる。その他のインプリメントの詳細は当該分野の当業者に自明のことである。
本発明はハードウェアで実現されているので、上述したように、従来のソフトウェアによる手法で起こっていた問題が起こることがない。具体的には、本発明はハードウェアで実現されているので、本発明によれば、各メモリ・アクセスごとにカウントを更新してもシステム・パフォーマンスが低下するおそれがない。従って、本発明によると、ＮＵＭＡコンピュータ・システムにおけるメモリ・ページの移動を効率的かつ効果的に行うことができる。
以上から明らかなように、本発明によれば、キャッシュ・コヒーレント・プロトコルを複雑化しなくてもページ移動を効率的かつ効果的に行うことができる。また、本発明によれば、メモリ・ルックアップ用のメモリ・バンド幅を大きくしなくてもページ移動を行うことができる。さらに、本発明によれば、メモリの各ブロックごとにキャッシュ・タグを関連づける必要がない。本発明のアレイは高価なＳＲＡＭにではなく、安価なＤＲＡＭにストアされることに注目すべきである。従って、本発明によれば、上述したように、従来のハードウェアによる手法で起こっていた問題が起こることはない。
以上、本発明の種々の実施例について説明してきたが、当然に理解されるように、これらの実施例は単なる例示であり、本発明は上述した実施例に限定されるものではない。従って、本発明の技術範囲は上述した実施例のどれによっても制限されるものではなく、請求の範囲に記載されている本発明の範囲によってのみ判断されるべきものである。
【図１】
0003889044.tif 000002
【図２Ａ】
0003889044.tif 000003
【図２Ｂ】
0003889044.tif 000004
【図３】
0003889044.tif 000005
【図４】
0003889044.tif 000006
【図５】
0003889044.tif 000007