(57)【要約】共有メモリ型マルチプロセッサシステムのスケーラビリティを向上させると共にハードウェアとソフトウェアのコストを抑えてコストパフォーマンスを向上させるキャッシュコヒーレンシ制御を実現する。キャッシュおよびTLBを有する複数のプロセッサがシステムメモリを共有するマルチプロセッサシステムのキャッシュコヒーレンシを制御するシステムでは、プロセッサが、TLB検索を実行するTLB検索部とTLB検索でヒットせずTLB割り込みを生じたときにTLBの登録情報処理を実行するコヒーレンシハンドラとを有するTLB制御部を含む。コヒーレンシハンドラは、システムメモリのページテーブルの検索およびTLBの登録情報置換を実行するTLBリプレースメントハンドラと、TLB割り込みがページフォールトではないときに、TLBにアドレスのマッチする登録情報が存在しない場合であるTLBミス割り込みを処理するTLBミス例外処理部と、TLBにアドレスのマッチする登録情報は存在するがアクセス権限が違反している場合であるストレージ割り込みを処理するストレージ例外処理部とを含む。
2012070291.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュおよびTLBを有する複数のプロセッサがシステムメモリを共有するマルチプロセッサシステムのキャッシュコヒーレンシを制御する方法であって、プロセッサが、
TLB検索でTLB割り込みを生じてページフォールトではないと判定したときに、TLBにアドレスのマッチする登録情報が存在しない場合であるTLBミス割り込みを処理するTLBミス例外処理ステップ、または、TLBにアドレスのマッチする登録情報は存在するがアクセス権限が違反している場合であるストレージ割り込みを処理するストレージ例外処理ステップ、
を実行することを含む、キャッシュコヒーレンシ制御の方法。
【請求項２】
前記TLBミス例外処理ステップは、TLBリプレースメントを実行した時に、エビクションされて破棄されるビクティムTLBエントリがカバーする物理ページに属するキャッシュのデータキャッシュラインをフラッシュするステップを含む、請求項１に記載の方法。
【請求項３】
前記TLBミス例外処理ステップまたは前記ストレージ例外処理ステップは、
前記TLBミス割り込みまたは前記ストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定するステップと、
前記メモリアクセスがデータアクセスであると判定したときに、当該アクセスについて置換または更新されるTLBエントリによりカバーされる物理ページに関する書き込み、読み出しおよび実行の権限に、他のプロセッサのTLBに設けられた当該物理ページのアクセス権限に対して排他的となる制約を加える処理ステップと、
を含む、請求項２に記載の方法。
【請求項４】
前記排他的となる制約を加える処理ステップは、書き込み時無効化方式の制約を加える処理ステップを含む、請求項３に記載の方法。
【請求項５】
前記書き込み時無効化方式の制約を加える処理ステップは、MESIプロトコルの制約を加えるMESIエミュレーション処理ステップを含む、請求項４に記載の方法。
【請求項６】
前記MESIエミュレーション処理ステップは、
前記メモリアクセスがデータ書き込みか読み出しかを判定するステップと、
前記読み出しと判定したときに、前記プロセッサのTLBと前記複数のプロセッサのTLBの登録情報を保持するTLBディレクトリメモリとにおける、当該アクセスの物理ページについての読み出しの属性をオンにするステップと、
前記TLBディレクトリメモリを当該アクセスの物理ページについて検索して、他のプロセッサのTLBが当該アクセスの物理ページについての書き込みの権限を持っているか否かを判定するステップと、
前記書き込みの権限を持っているときに、前記他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、前記他のプロセッサに当該アクセスの物理ページへの書き込みの権限をクリアにさせるステップと、
前記TLBディレクトリメモリでの前記他のプロセッサのTLBに関する当該アクセスの物理ページについての書き込みの属性をクリアにするステップと、
を含む、請求項５に記載の方法。
【請求項７】
前記他のプロセッサに前記アクセスの物理ページへの書き込みの権限をクリアにさせるステップは、前記他のプロセッサが、データキャッシュをコピーバックして、当該プロセッサのTLBにおける前記アクセスの物理ページについての書き込みの属性をディスエーブルにするステップを含む、請求項６に記載の方法。
【請求項８】
前記MESIエミュレーション処理ステップは、
前記書き込みと判定したときに、前記プロセッサのTLBと前記TLBディレクトリメモリとにおける、前記アクセスの物理ページについての書き込みの属性をオンするステップと、
前記TLBディレクトリメモリを前記アクセスの物理ページについて検索して、前記他のプロセッサのTLBが前記アクセスの物理ページについての読み出し、書き込みまたは実行の権限を持っているか否かを判定するステップと、
前記読み出し、書き込みまたは実行の権限を持っているときに、前記他のプロセッサに対しフラッシュコマンドをプロセッサ間割り込みで通知して、前記他のプロセッサに前記アクセスの物理ページへの読み出し、書き込みおよび実行の権限をクリアにさせるステップと、
前記TLBディレクトリメモリでの前記他のプロセッサのTLBに関する前記アクセスの物理ページについての読み出し、書き込みおよび実行の属性をクリアにするステップと、
を含む、請求項６または７に記載の方法。
【請求項９】
前記他のプロセッサに前記アクセスの物理ページへの読み出し、書き込みおよび実行の権限をクリアにさせるステップは、前記他のプロセッサが、データキャッシュをコピーバックして無効化し、当該プロセッサのTLBにおける前記アクセスの物理ページについての読み出し、書き込みおよび実行の属性をディスエーブルにするステップを含む、請求項８に記載の方法。
【請求項１０】
前記TLBミス例外処理ステップまたは前記ストレージ例外処理ステップは、
前記TLBミス割り込みまたは前記ストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定するステップと、
前記メモリアクセスが命令アクセスであると判定したときに、
命令フェッチで前記TLBミス割り込みを起こした物理ページについて前記システムメモリのページテーブルのエントリがユーザー書き込み許可の権限を持つかを判定するステップと、
前記ページテーブルのエントリがユーザー書き込み許可の権限を持つときは、当該物理ページについて他のプロセッサのTLBがユーザー書き込み許可の権限を持つかを判定するステップと、
前記他のプロセッサのTLBがユーザー書き込み許可の権限を持つときは、前記他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、前記他のプロセッサに当該ユーザー書き込み許可の権限をクリアにさせるステップと、
を含む、請求項２に記載の方法。
【請求項１１】
前記TLBミス例外処理ステップまたは前記ストレージ例外処理ステップは、前記他のプロセッサのTLBがユーザー書き込み許可の権限を持たないとき、または、前記他のプロセッサに前記ユーザー書き込み許可の権限をクリアにさせるステップの後に、前記アクセスをしたプロセッサの命令キャッシュを無効化するステップを含む、請求項１０に記載の方法。
【請求項１２】
前記TLBミス例外処理ステップまたは前記ストレージ例外処理ステップは、前記ページテーブルのエントリがユーザー書き込み許可の権限を持たないとき、または、前記アクセスをしたプロセッサの命令キャッシュを無効化するステップの後に、前記アクセスをしたプロセッサのTLBと前記複数のプロセッサのTLBの登録情報を保持するTLBディレクトリメモリとにおける、前記命令フェッチでTLBミス割り込みを起こした物理ページについての実行の属性をオンにするステップを含む、請求項１０または１１に記載の方法。
【請求項１３】
前記MESIエミュレーション処理ステップは、前記TLBディレクトリメモリを前記アクセスの物理ページについて検索するときにセマフォを使用して逐次アクセスを行うステップを含む、請求項６または８に記載の方法。
【請求項１４】
プロセッサに、請求項１〜１３のいずれか１項に記載の方法の各ステップを実行させるコンピュータプログラム。
【請求項１５】
キャッシュおよびTLBを有する複数のプロセッサがシステムメモリを共有するマルチプロセッサシステムのキャッシュコヒーレンシを制御するシステムであって、
プロセッサが、TLB検索を実行するTLB検索部と前記TLB検索でヒットせずTLB割り込みを生じたときにTLBの登録情報処理を実行するコヒーレンシハンドラとを有するTLB制御部を含み、
前記コヒーレンシハンドラが、システムメモリのページテーブルの検索およびTLBの登録情報置換を実行するTLBリプレースメントハンドラと、前記TLB割り込みがページフォールトではないときに、TLBにアドレスのマッチする登録情報が存在しない場合であるTLBミス割り込みを処理するTLBミス例外処理部と、TLBにアドレスのマッチする登録情報は存在するがアクセス権限が違反している場合であるストレージ割り込みを処理するストレージ例外処理部とを含む、
キャッシュコヒーレンシ制御のシステム。
【請求項１６】
前記TLBミス例外処理部は、TLBリプレースメントが実行された時に、エビクションされて破棄されるビクティムTLBエントリがカバーする物理ページに属するキャッシュのデータキャッシュラインをフラッシュする、請求項１５に記載のシステム。
【請求項１７】
前記TLBミス例外処理部および前記ストレージ例外処理部は、それぞれ、
前記TLBミス割り込みおよび前記ストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定し、
前記メモリアクセスがデータアクセスであると判定したときに、当該アクセスについて置換または更新されるTLBエントリによりカバーされる物理ページに関する書き込み、読み出しおよび実行の権限に、他のプロセッサのTLBに設けられた当該物理ページのアクセス権限に対して排他的となる制約を加える処理を実行する、請求項１６に記載のシステム。
【請求項１８】
前記TLBミス例外処理部および前記ストレージ例外処理部は、それぞれ、
前記TLBミス割り込みおよび前記ストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定し、
前記メモリアクセスが命令アクセスであると判定したときに、
命令フェッチで前記TLBミス割り込みを起こした物理ページについて前記システムメモリのページテーブルのエントリがユーザー書き込み許可の権限を持つかを判定し、
前記ページテーブルのエントリがユーザー書き込み許可の権限を持つときは、当該物理ページについて他のプロセッサのTLBがユーザー書き込み許可の権限を持つかを判定し、
前記他のプロセッサのTLBがユーザー書き込み許可の権限を持つときは、前記他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、前記他のプロセッサに当該ユーザー書き込み許可の権限をクリアにさせる、
請求項１６に記載のシステム。
【請求項１９】
さらに、前記複数のプロセッサのTLBの登録情報を保持して前記複数のプロセッサからは物理ページについての検索がなされるTLBディレクトリメモリを含む、請求項１５〜１８のいずれか１項に記載のシステム。
【請求項２０】
前記マルチプロセッサシステムは複数のノードからなり、当該各ノードは、それぞれ、前記複数のプロセッサと、コヒーレント共有バスにより前記複数のプロセッサに接続された前記システムメモリと、ブリッジ機構により前記コヒーレント共有バスに接続された前記TLBディレクトリメモリおよび前記複数のプロセッサの前記TLBディレクトリメモリへのセマフォによる逐次アクセスのためのセマフォハンドラとを含んで、NCC-NUMA機構により相互に接続される、請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュコヒーレンシの制御に関し、特に、共有メモリ型マルチプロセッサのキャッシュコヒーレンシを制御する方法、システムおよびプログラムに関する。
【背景技術】
【０００２】
マルチプロセッサシステムは、複数のタスクまたはプロセス（以下、「プロセス」と記す）を同時に実行する。これら複数のプロセスは、それぞれ通常、そのプロセスの実行に利用される仮想アドレス空間を持つ。そのような仮想アドレス空間内の位置は、システムメモリ内の物理アドレスにマップされるアドレスを含む。システムメモリ内の単一の空間がマルチプロセッサシステム内の複数の仮想アドレスにマップされることは珍しくない。複数のプロセスがそれぞれ仮想アドレスを使用する場合、これらのアドレスをシステムメモリ内の物理アドレスに変換して、プロセスを処理するプロセッサのキャッシュに適切な命令またはデータがなければ、それらをシステムメモリから取り出しキャッシュに格納する。【０００３】
マルチプロセッサシステム内の仮想アドレスをシステムメモリ内の物理アドレスに迅速に変換して適切な命令またはデータを取得するために、キャッシュに関連したいわゆる「変換索引バッファ」（Translation Look-aside Buffer、以下、「TLB」と記す）を使用する。TLBは、仮想アドレスと変換アルゴリズムを使用して生成された物理アドレスの間の変換関係を含むバッファである。TLBを使用するとかなり効率的なアドレス変換が提供されるが、対称型マルチプロセッシング（Symmetric Multi Processing、以下、「SMP」と記す）システムでそのようなバッファを使用すると、インコヒーレンシの問題が発生する。複数のプロセッサが共通のシステムメモリに対して読み取りおよび書き込みを行えるデータ処理システムでは、メモリシステムがコヒーレントに動作するよう配慮しなければならない。即ち、複数のプロセッサによるプロセス処理の結果としてメモリシステムがインコヒーレントになることは許されない。そのようなマルチプロセッサシステム内の各プロセッサは、通常、キャッシュに関連したアドレス変換用のTLBを含み、そのようなシステム内でのメモリの共用態様では、コヒーレンシを維持するために、マルチプロセッサシステムにおける１つのプロセッサのTLBに対する変更を、その他の各プロセッサのTLBに慎重にかつ矛盾なくマップする必要がある。【０００４】
マルチプロセッサシステムでは、TLBのコヒーレンシの維持は、例えば、すべてのTLBの修正にプロセッサ間割り込み（IPI：Inter-Processor Interrupt）およびソフトウェア同期化を使用することによって実現される。これらの方法を使用すれば、マルチプロセッサシステム全体にわたってメモリのコヒーレンシを確保することができる。マルチプロセッサシステム内の各TLBの内容は、通常、ページメモリシステムでは、システムメモリ内に維持されるページテーブルの内容のうちキャッシュに関連した部分を反映したものとなる。ページテーブルは、一般に、仮想アドレスあるいはそれらのセグメントとそれらのアドレスに関連する物理アドレスとを含むメモリマップテーブルである。ページ保護ビット、有効エントリビットおよび様々なアクセス制御ビットを含む他の様々な管理データも、通常、そのようなページテーブル内に含まれる。管理データとして、例えば、コヒーレンシの必要を明示するビット（memory coherence required属性）を定義して、コヒーレントが本当に必要なページであるかどうかを予め設定することができる。しかしながら、そのようなビットを予め設定しなければならない上に、しかもシステムメモリ全体に予めビットを設定する以外にないので、この事前ビット設定方法の有効利用は、キャッシュをソフトウェア制御するように書き換えることが許される一部の特殊なプログラムに限られる。【０００５】
近年、複数のCPUを有するデスクトップPCやSMP-Linux（Linuxは米国およびその他の国においてLinus Torvaldsが所有する商標）が普及し、多くのアプリケーションプログラムは、共有メモリ型マルチプロセッサ、即ち、SMPシステムに対応するようになった。それ故、システムのプロセッサの数を増やせば、アプリケーションプログラムのスループットは、ソフトウェアを書き換えることなく向上する。そこで、SMP対応を進める汎用OS、例えばSMP-Linuxは、1024以上のプロセッサを制御できるまでスケールアップしてきた。ソフトウェアを書き換えることなくプロセッサの数に応じてスループットを向上できるというSMPの特徴は、メッセージパッシング（message passing）プログラミングを用いるクラスタのようにメモリを共有しないマルチプロセッサシステムにはない利点である。従って、SMPは、ソフトウェア資産を保護するには望ましいマルチプロセッサシステムである。【０００６】
しかしながら、メッセージパッシングを前提としたクラスタに比べると、SMPシステムのスケーラビリティは低い。これは、スケーラビリティを上げるためにSMPシステムのプロセッサの数を増やせば増やすほど、キャッシュコヒーレンシをサポートするハードウェアのコストが飛躍的に高まるためである。SMPシステムに関するキャッシュコヒーレンシのハードウェアサポートの例は、デスクトップPCの共有バスで使われる安価なハードウェアによるMESI（Modified, Exclusive, Shared, Invalid）スヌープ（snoop：監視）プロトコルから、大規模な分散共有メモリ（DSM：Distributed Shared Memory）システムのキャッシュコヒーレント不均一メモリアクセス（Cache Coherent,Non-Uniform Memory Access、以下、「CC-NUMA」と記す）で用いられる、例えばプロトコルプロセッサ、ディレクトリメモリとの特殊なノード間接続を集積するような高価なハードウェアによるディレクトリベースのプロトコルまで挙げることができる。CC-NUMAを使ってプロセッサの数を増やすとハードウェアコストが増大するため、プロセッサの数が増えるにつれてマルチプロセッサのコストパフォーマンスは低下する。即ち、CC-NUMAの経済的なスケーラビリティは低い。これに対し、クラスタは標準部品で構成可能であるため、プロセッサあたりのハードウェアコストは専用部品の必要なCC-NUMAに比べて安価である。特に、プロセッサあたりのハードウェアコストが一定のクラスタでは、メッセージパッシングインタフェースを使って、高い並列性を有するアプリケーション（embarrassingly parallel application）プログラムを書き直せば、大規模並列処理（massively parallel processing）が可能である。【０００７】
非特許文献１には、SMPシステムのスケーラビリティとコストパフォーマンスを改善させるために、プロセッサが持つメモリ管理ユニット（Memory Management Unit、以下、「MMU」と記す）のハードウェアを利用する、VM（Virtual Memory）ベース共有メモリ（based shared memory）技術が示されている。この技術は、クラスタのハードウェアと同じくらいに安いハードウェアを使用することができる、非特許文献２に示された非キャッシュコヒーレント不均一メモリアクセス（Non-Cache Coherent, NUMA、以下、「NCC-NUMA」と記す）に適用された。VMベース共有メモリ技術は、同一プロセスのキャッシュコヒーレンシを扱うが、異なるプロセス同士のキャッシュコヒーレンシを扱えない。特に、仮想アドレスをサポートし、コピーオンライト（Copy-On-Write）技術を使ってメモリ管理を行う汎用OSでは、同じ物理ページを複数のプロセスへマッピングすることが普通であるため、VMベース共有メモリ技術が適用できるデータは、アプリケーションプログラムが異なるプロセスと共有されないことを保証するデータに限定され、アプリケーションプログラムから透過的なキャッシュコヒーレンシを実装することができない。つまり、複数のプロセッサの間で共有される同じ仮想アドレス空間のデータを明示する必要が生じ、既存ソフトウェアに適用しようとすれば、アプリケーションプログラムを書き換えなければならず、それに伴うソフトウェアコストが発生する。従って、VMベース共有メモリ技術は、汎用コンピュータではなく、プログラムを新規設計することが許される特定用途や科学技術計算に応用が限られる。【０００８】
特許文献１には、主記憶共有型のマルチプロセッサにおいて、物理ページマップテーブルを設けることによる少ないハードウェア量の追加で、ページテーブル書き換え時にTLBの一貫性制御のためにTLBパージトランザクションをブロードキャストする必要を無くしあるいは大幅に削減し、ネットワークおよびノード内のバスのトラフィックおよびTLBパージ処理に伴うプロセッサのパイプラインストールを無くすあるいは大幅に削減できることが、記載されている。【０００９】
特許文献２には、キャッシュメモリ（CACHE-M）やアドレス変換バッファ（TLB）等の連想メモリをMOV命令等のデータ転送命令でアクセスしてエントリの無効化等の操作を行えるようにすることが、記載されている。【００１０】
特許文献３には、ソフトウェアによりアドレス変換対等の変換情報をTLBに直接挿入できるようにする一組のソフトウェア命令が導入され、ページフォルトハンドラは、変換情報をページディレクトリに挿入するだけでなく、その情報をTL Bに挿入できるようになり、ページフォルトハンドラルーチンの実行が完了すると、次に同じ仮想アドレスが与えられたときTLBミスとはならないでTLBヒツトになるのを保証することが、記載されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２０００−６７００９号公報
【特許文献２】特開平８−３２０８２９号公報
【特許文献３】特開昭６２−３３５７号公報
【非特許文献】
【００１２】
【非特許文献１】Karin Petersen and Kai Li, “Cache Coherence for Shared Memory Multiprocessors Based on Virtual Memory Support” In Proceedings of the Seventh International Parallel Processing Symposium, Newport Beach, CA, April 1993, pp. 1-18
【非特許文献２】Leonidas Kontothanassis, et al., “Shared Memory Computing on Clusters with Symmetric Multiprocessors and System Area Networks” ACM Transactions on Computer Systems (TOCS) Vol. 23, No. 3, August 2005, pp. 301-335
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、共有メモリ型マルチプロセッサシステムのスケーラビリティを向上させると共にハードウェアとソフトウェアのコストを抑えてコストパフォーマンスを向上させるキャッシュコヒーレンシ制御の実現を目的とする。本発明の目的には、そのようなキャッシュコヒーレンシ制御を実現する方法、システムおよびプログラムを提供することが含まれる。また、本発明の目的には、キャッシュコヒーレンシ制御を廉価なハードウェア構成によりソフトウェアで実現することが含まれる。さらに、本発明の目的には、キャッシュコヒーレンシ制御をソフトウェアでアプリケーションプログラムから透過的に、即ちアプリケーションプログラムを書き換えることなく実現することが含まれる。
【課題を解決するための手段】
【００１４】
本発明による１実施態様のキャッシュコヒーレンシ制御の方法は、キャッシュおよびTLBを有する複数のプロセッサがシステムメモリを共有するマルチプロセッサシステムのキャッシュコヒーレンシを制御し、プロセッサが、TLB検索でTLB割り込みを生じてページフォールトではないと判定したときに、TLBにアドレスのマッチする登録情報が存在しない場合であるTLBミス割り込みを処理するTLBミス例外処理ステップ、または、TLBにアドレスのマッチする登録情報は存在するがアクセス権限が違反している場合であるストレージ割り込みを処理するストレージ例外処理ステップを実行することを含む。TLBミス例外処理ステップは、TLBリプレースメントを実行した時に、エビクションされて破棄されるビクティムTLBエントリがカバーする物理ページに属するキャッシュのデータキャッシュラインをフラッシュするステップを含む。TLBミス例外処理ステップまたはストレージ例外処理ステップは、TLBミス割り込みまたはストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定するステップと、メモリアクセスがデータアクセスであると判定したときに、当該アクセスについて置換または更新されるTLBエントリによりカバーされる物理ページに関する書き込み、読み出しおよび実行の権限に、他のプロセッサのTLBに設けられた当該物理ページのアクセス権限に対して排他的となる制約を加える処理ステップとを含む。【００１５】
好ましくは、排他的となる制約を加える処理ステップは、書き込み時無効化方式の制約を加える処理ステップを含む。書き込み時無効化方式の制約を加える処理ステップは、MESIプロトコルの制約を加えるMESIエミュレーション処理ステップを含む。【００１６】
好ましくは、MESIエミュレーション処理ステップは、メモリアクセスがデータ書き込みか読み出しかを判定するステップと、読み出しと判定したときに、プロセッサのTLBと複数のプロセッサのTLBの登録情報を保持するTLBディレクトリメモリとにおける、当該アクセスの物理ページについての読み出しの属性をオンにするステップと、TLBディレクトリメモリを当該アクセスの物理ページについて検索して、他のプロセッサのTLBが当該アクセスの物理ページについての書き込みの権限を持っているか否かを判定するステップと、書き込みの権限を持っているときに、他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、他のプロセッサに当該アクセスの物理ページへの書き込みの権限をクリアにさせるステップと、TLBディレクトリメモリでの他のプロセッサのTLBに関する当該アクセスの物理ページについての書き込みの属性をクリアにするステップとを含む。他のプロセッサにアクセスの物理ページへの書き込みの権限をクリアにさせるステップは、他のプロセッサが、データキャッシュをコピーバックして、当該プロセッサのTLBにおけるアクセスの物理ページについての書き込みの属性をディスエーブルにするステップを含む。【００１７】
好ましくは、MESIエミュレーション処理ステップは、書き込みと判定したときに、プロセッサのTLBとTLBディレクトリメモリとにおける、アクセスの物理ページについての書き込みの属性をオンするステップと、TLBディレクトリメモリをアクセスの物理ページについて検索して、他のプロセッサのTLBがアクセスの物理ページについての読み出し、書き込みまたは実行の権限を持っているか否かを判定するステップと、読み出し、書き込みまたは実行の権限を持っているときに、他のプロセッサに対しフラッシュコマンドをプロセッサ間割り込みで通知して、他のプロセッサにアクセスの物理ページへの読み出し、書き込みおよび実行の権限をクリアにさせるステップと、TLBディレクトリメモリでの他のプロセッサのTLBに関するアクセスの物理ページについての読み出し、書き込みおよび実行の属性をクリアにするステップとを含む。他のプロセッサにアクセスの物理ページへの読み出し、書き込みおよび実行の権限をクリアにさせるステップは、他のプロセッサが、データキャッシュをコピーバックして無効化し、当該プロセッサのTLBにおけるアクセスの物理ページについての読み出し、書き込みおよび実行の属性をディスエーブルにするステップを含む。【００１８】
好ましくは、TLBミス例外処理ステップまたはストレージ例外処理ステップは、TLBミス割り込みまたはストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定するステップと、メモリアクセスが命令アクセスであると判定したときに、命令フェッチでTLBミス割り込みを起こした物理ページについてシステムメモリのページテーブルのエントリがユーザー書き込み許可の権限を持つかを判定するステップと、ページテーブルのエントリがユーザー書き込み許可の権限を持つときは、当該物理ページについて他のプロセッサのTLBがユーザー書き込み許可の権限を持つかを判定するステップと、他のプロセッサのTLBがユーザー書き込み許可の権限を持つときは、他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、他のプロセッサに当該ユーザー書き込み許可の権限をクリアにさせるステップとを含む。TLBミス例外処理ステップまたはストレージ例外処理ステップは、他のプロセッサのTLBがユーザー書き込み許可の権限を持たないとき、または、他のプロセッサにユーザー書き込み許可の権限をクリアにさせるステップの後に、アクセスをしたプロセッサの命令キャッシュを無効化するステップを含む。TLBミス例外処理ステップまたはストレージ例外処理ステップは、ページテーブルのエントリがユーザー書き込み許可の権限を持たないとき、または、アクセスをしたプロセッサの命令キャッシュを無効化するステップの後に、アクセスをしたプロセッサのTLBと複数のプロセッサのTLBの登録情報を保持するTLBディレクトリメモリとにおける、命令フェッチでTLBミス割り込みを起こした物理ページについての実行の属性をオンにするステップを含む。【００１９】
好ましくは、MESIエミュレーション処理ステップは、TLBディレクトリメモリをアクセスの物理ページについて検索するときにセマフォを使用して逐次アクセスを行うステップを含む。【００２０】
本発明の１実施態様により、プロセッサに上記方法の各ステップを実行させるキャッシュコヒーレンシ制御のコンピュータプログラムが提供される。【００２１】
本発明による１実施態様のキャッシュコヒーレンシ制御のシステムは、キャッシュおよびTLBを有する複数のプロセッサがシステムメモリを共有するマルチプロセッサシステムのキャッシュコヒーレンシを制御する。プロセッサは、TLB検索を実行するTLB検索部とTLB検索でヒットせずTLB割り込みを生じたときにTLBの登録情報処理を実行するコヒーレンシハンドラとを有するTLB制御部を含む。コヒーレンシハンドラは、システムメモリのページテーブルの検索およびTLBの登録情報置換を実行するTLBリプレースメントハンドラと、TLB割り込みがページフォールトではないときに、TLBにアドレスのマッチする登録情報が存在しない場合であるTLBミス割り込みを処理するTLBミス例外処理部と、TLBにアドレスのマッチする登録情報は存在するがアクセス権限が違反している場合であるストレージ割り込みを処理するストレージ例外処理部とを含む。TLBミス例外処理部は、TLBリプレースメントが実行された時に、エビクションされて破棄されるビクティムTLBエントリがカバーする物理ページに属するキャッシュのデータキャッシュラインをフラッシュする。TLBミス例外処理部およびストレージ例外処理部は、それぞれ、TLBミス割り込みおよびストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定し、メモリアクセスがデータアクセスであると判定したときに、当該アクセスについて置換または更新されるTLBエントリによりカバーされる物理ページに関する書き込み、読み出しおよび実行の権限に、他のプロセッサのTLBに設けられた当該物理ページのアクセス権限に対して排他的となる制約を加える処理を実行する。【００２２】
TLBミス例外処理部およびストレージ例外処理部は、それぞれ、TLBミス割り込みおよびストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定し、メモリアクセスが命令アクセスであると判定したときに、命令フェッチでTLBミス割り込みを起こした物理ページについてシステムメモリのページテーブルのエントリがユーザー書き込み許可の権限を持つかを判定し、ページテーブルのエントリがユーザー書き込み許可の権限を持つときは、当該物理ページについて他のプロセッサのTLBがユーザー書き込み許可の権限を持つかを判定し、他のプロセッサのTLBがユーザー書き込み許可の権限を持つときは、他のプロセッサに対しクリーンコマンドをプロセッサ間割り込みで通知して、他のプロセッサに当該ユーザー書き込み許可の権限をクリアにさせる。【００２３】
キャッシュコヒーレンシ制御のシステムは、さらに、複数のプロセッサのTLBの登録情報を保持して複数のプロセッサからは物理ページについての検索がなされるTLBディレクトリメモリを含む。【００２４】
好ましくは、マルチプロセッサシステムは複数のノードからなり、当該各ノードは、それぞれ、複数のプロセッサと、コヒーレント共有バスにより複数のプロセッサに接続されたシステムメモリと、ブリッジ機構によりコヒーレント共有バスに接続されたTLBディレクトリメモリおよび複数のプロセッサのTLBディレクトリメモリへのセマフォによる逐次アクセスのためのセマフォハンドラとを含んで、NCC-NUMA機構により相互に接続される。
【発明の効果】
【００２５】
本発明によれば、共有メモリ型マルチプロセッサシステムのスケーラビリティを向上させると共にハードウェアとソフトウェアのコストを抑えてコストパフォーマンスを向上させるキャッシュコヒーレンシ制御が実現される。特に、そのようなキャッシュコヒーレンシ制御を実現する方法、システムおよびプログラムが提供され、キャッシュコヒーレンシ制御を廉価なハードウェア構成によりソフトウェアで実現することができ、さらに、アプリケーションプログラムを書き換えることなく実現することができる。
【図面の簡単な説明】
【００２６】
【図１】本発明によるキャッシュコヒーレンシ制御の実施に使用できるマルチプロセッサシステムを概略的に示すブロック図である。
【図２】本発明の１実施形態に係るキャッシュコヒーレンシ制御のシステムを有するプロセッサを概略的に示すブロック図である。
【図３】TLBディレクトリメモリの概略構成図である。
【図４】本発明の１実施形態に係るキャッシュコヒーレンシ制御の方法を概略的に示すフローチャート図である。
【図５】コヒーレンシハンドラのTLBミス例外処理およびストレージ例外処理のサブルーチンにおけるビクティムTLBエントリのエビクション処理を示すフローチャート図である。
【図６】コヒーレンシハンドラのTLBミス例外処理およびストレージ例外処理のサブルーチンにおけるMESIエミュレーション処理を示すフローチャート図である。
【図７】コヒーレンシハンドラのTLBミス例外処理およびストレージ例外処理のサブルーチンにおける命令キャッシュコヒーレンシ処理を示すフローチャート図である。
【図８】セマフォの使用を示すコヒーレンシハンドラの入口と出口のフロー図である。
【図９】SMPとNCC-NUMAのハイブリッドシステムへ拡張したコヒーレントな共有メモリ型マルチプロセッサシステムの概略構成図である。
【図１０】LSM 用のローカルのTLBディレクトリメモリの概略構成図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための最良の形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。本発明は多くの異なる態様で実施することが可能であり、記載された実施形態の内容に限定して解釈されるべきではない。なお、実施形態の説明の全体を通じて同じ構成部分乃至構成要素には同じ番号を付している。
【００２８】
図１は、本発明によるキャッシュコヒーレンシ制御の実施に使用できるマルチプロセッサシステム１００を概略的に示すブロック図である。マルチプロセッサシステム１００では、複数のプロセッサ１０１がそれぞれメモリバス１０２でシステムメモリ１０３に結合されている。各プロセッサ１０１にはCPU１０４、MMU１０５およびキャッシュ１０６があり、MMU１０５にはTLB１０７がある。各プロセッサ１０１のキャッシュ１０６にシステムメモリ１０３の内容の一部が保持される。マルチプロセッサシステム１００等のSMPシステムでは、各プロセッサ１０１はシステムメモリ１０３に対して読み取りまたは書き込みを行うことができるので、システムメモリ１０３およびキャッシュ１０６内のデータおよび命令がコヒーレントになるようにする必要がある。システムメモリ１０３内にページテーブル１０８を提供するのが好ましく、ページテーブル１０８内の複数のエントリ、即ち登録情報を使用して、仮想アドレスをシステムメモリ１０３内の物理アドレスに効率的にマップすることができる。システムメモリ１０３は、メモリコントローラ１０９を有し、接続され外部記憶装置１２０との間でも記憶情報に関するやり取り、即ち読み出しおよび書き込みを行う。各プロセッサ１０１では、TLB１０７を使用して、ページテーブル１０８の各エントリに含まれる情報を複製することにより、命令またはデータの仮想アドレスをシステムメモリ１０３内の物理アドレスに変換することができる。TLB１０７がメモリ空間のアドレス情報を提供するので、TLB１０７の正確な動作を確保するために、マルチプロセッサシステム１００内の各TLB１０７間でコヒーレンシを維持するよう制御することが重要である。
【００２９】
図２は、本発明の１実施形態に係るキャッシュコヒーレンシ制御のシステムを有するプロセッサ１０１を概略的に示すブロック図である。プロセッサ１０１のキャッシュ１０６は、命令キャッシュ１０６’およびデータキャッシュ１０６’’を含む。プロセッサ１０１は、メモリバス１０２の他には、すべてのプロセッサ１０１がアクセスできるように設けられたTLBディレクトリメモリ１２１に接続される。TLBディレクトリメモリ１２１は、ローカルのプロセッサ１０１がプロセッサ間割り込みを使ってリモートのプロセッサ１０１を割り込むことなくリモートのプロセッサ１０１のTLB１０７の内容を調べることができるようにするために、すべてのプロセッサ１０１のTLB１０７が保持する物理ページ番号、読み取り／書き込み／実行のアクセス権限および有効（Valid）ステータスの各情報を複製して、すべてのプロセッサ１０１のCPU１０４が参照できるようなグローバルアドレスにマップしたものである。CPU１０４はAP（Application Program）処理１２２を実行する動作モード（ユーザモード）と、OSカーネル処理１２４を実行する動作モード（スーパバイザモード）と、割り込みハンドラを実行する動作モードとを持つ。コヒーレンシハンドラ１２６は、第３の動作モードで実行される。TLB制御部１２３は、AP処理１２２のキャッシュ１０６へのアクセス時またはOSカーネル処理１２４のキャッシュ１０６へのアクセス時にTLB検索を実行するTLB検索部１２５と、TLB検索を実行してヒットせずTLB割り込みを生じたときにTLB１０７の登録情報処理を実行するコヒーレンシハンドラ１２６とを含む。コヒーレンシハンドラ１２６は、図２に示されるように、ページフォールトを処理するOSカーネル処理１２４の外に位置する。
【００３０】
TLB検索部１２５は、TLB検索を実行してヒットしたときにキャッシュタグを検索するキャッシュタグ検索部１２７を含む。キャッシュタグ検索部１２７は、キャッシュタグ検索でヒットしたときには、AP処理１２２によるキャッシュ１０６へのアクセスを指示する。また、キャッシュタグ検索部１２７は、キャッシュタグ検索でヒットせずキャッシュタグミスを生じたときには、キャッシュ１０６ではなくて、AP処理１２２によるシステムメモリ１０３へのアクセスを指示する。
【００３１】
コヒーレンシハンドラ１２６は、TLBリプレースメントハンドラ１２８、TLBミス例外処理部１２９およびストレージ例外処理部１３０を含む。TLBリプレースメントハンドラ１２８は、ページテーブル検索部１３１とページフォールト判定部１３２を含む。ページテーブル検索部１３１は、TLB検索部１２５でTLB割り込みとなったときにシステムメモリ１０３にあるページテーブル１０８の検索を処理する。ページフォールト判定部１３２は、ページテーブル検索部１３１の検索処理からページフォールトか否かを判定する。ページフォールト判定部１３２がページテーブル検索部１３１の検索処理からページフォールトでない、即ちページテーブル１０８にTLBエントリのページがあると判定したときは、TLBミス例外処理部１２９またはストレージ例外処理部１３０がコヒーレンシ制御を実行する。ところで、ページテーブル１０８にTLBエントリのページがありページフォールトではないが、しかしTLB検索でヒットせずに生じるTLB割り込みに関して、アドレスのマッチするエントリ、即ち登録情報がTLBに存在しない場合を「TLBミス割り込み」と称し、アドレスのマッチするエントリ、即ち登録情報はTLBに存在するがアクセス権限が違反している場合を「ストレージ割り込み」と称することにする。TLBミス例外処理部１２９はTLBミス割り込みを処理し、ストレージ例外処理部１３０はストレージ割り込みを処理する。コヒーレンシハンドラ１２６は、ページフォールトではないときにコヒーレンシ制御を実行するので、ページフォールトであるときにコヒーレンシ処理を行うVMベース共有メモリ技術と異なる。
【００３２】
OSカーネル処理１２４は、メモリ管理部１３３を含む。ページフォールト判定部１３２がページテーブル検索部１３１の検索処理からページフォールトであると判定したとき、TLBリプレースメントハンドラ１２８はページフォールト割り込みを発生し、OSカーネル処理１２４のメモリ管理部１３３がページフォールトの処理を実行する。
【００３３】
コヒーレンシハンドラ１２６のTLBミス例外処理部１２９およびストレージ例外処理部１３０は、ローカルのプロセッサ１０１のTLB１０７のエントリに登録している物理ページだけがキャッシュ１０６に保持されるように、コヒーレンシ制御を実行する。そのために、コヒーレンシハンドラ１２６がTLBリプレースメントを実行する時、ビクティム（victim：犠牲）としてエビクション（eviction：追い出し）されて破棄されるTLBエントリ、即ち登録情報がカバーする物理ページはキャッシュからフラッシュ（FLUSH）、即ちコピーバックと無効化をする。さらに、追加されるTLBエントリ、即ち登録情報によりカバーされる物理ページの書き込み／読み出し／実行の権限に、リモートのプロセッサ１０１のTLB１０７に設けられたその物理ページのアクセス権限に対して排他的となる制約を加える。排他的制約の例としては、書き込み時無効化方式、特にはMESIプロトコルの制約を挙げることができる。MESIプロトコルは、書き込み−無効化（Write Invalidate）型に分類されるコヒーレンシプロトコルであるが、この他に、書き込み−更新（Write Update）型があり、どちらを採用しても構わない。MESIプロトコルの制約については後で言及する。その制約を加えれば、TLBミスを起こさない限り、コヒーレンシを処理する必要が生じない。VMベース共有メモリ技術では、ページテーブルに保持される論理ページを排他的にキャッシュさせるため、同じ物理ページを複数の異なる論理ページへマッピングする場合には、コヒーレンシについては対応できない。
【００３４】
TLBミス割り込みおよびストレージ割り込みのときにTLBエントリ、即ち登録情報を入れ替えたり、即ち置換したり更新したりする場合、MESIプロトコルの制約に従った読み出し／書き込み／実行の権限が与えられる。ページテーブルの検索をハードウェアによりアシストするプロセッサでは、TLBはページテーブルの一部をキャッシュしたものに過ぎないが、図２に示されたキャッシュコヒーレンシ制御では、ソフトウェアで制御されるTLBを利用して、ページテーブルに記録されたアクセス権限のうちでMESIプロトコルの排他制約に合致するアクセス権限だけをTLB１０７に設定する。従って、TLB１０７に記録されるアクセス権限は、システムメモリ１０３のページテーブル１０８に記録されるアクセス権限と同じか制約の加えられたものとなる。
【００３５】
TLBミス割り込みまたはストレージ割り込みのとき、ローカルのプロセッサ１０１は、TLBディレクトリメモリ１２１を参照することにより、MESIプロトコルの排他制約に合致させるために更新する必要があるリモートのプロセッサ１０１のTLBエントリ、即ち登録情報を検索する。複数のプロセッサ１０１がTLBディレクトリメモリ１２１を同時に更新することから保護するため、TLBディレクトリメモリ１２１へのアクセスは、セマフォを使って逐次アクセスにすると良い。また、TLBディレクトリメモリ１２１は、連想メモリ（CAM：Content Addressable Memory）により実装すると良い。CAM使用の場合、検索ワードに物理ページ番号、書き込み／読み出し／実行のアクセス許可ビットが含まれ、プロセッサIDとTLBエントリ番号を連結したものをCAMのアドレス入力とする。CAMアクセスに使用するバスは、メモリバスと独立でCPU専用であることが望ましい。そのようなバスの例には、デバイスコントロールレジスタ（DCR：Device Control Register）バスがある。
【００３６】
図３に、TLBディレクトリメモリ１２１の構成を概略的に示す。各プロセッサ１０１のTLB１０７のエントリ、即ち登録情報を保持するTLBディレクトリメモリ１２１を設けて、各プロセッサ１０１がプロセッサ間割り込みを使わなくても他のプロセッサ１０１のTLB１０７のエントリ、即ち登録情報をトラッキングできるようにしてある。また、各プロセッサ１０１のTLB１０７に登録されたエントリ、即ち登録情報のページのみがキャッシングを許されるようにキャッシングを制御して、それらのTLB１０７を検索すれば各キャッシュのページの利用状況が判断できるようにしてある。TLBディレクトリメモリ１２１は、全てのプロセッサ１０１がアクセスできるようグローバルアドレス空間にマップされる。TLBディレクトリメモリ１２１の各エントリは、VS（Valid Status）と記された有効ステータス情報３００、PPN（Physical PageNumber）と記された物理ページ番号情報３０１およびR/W/E P（Read/Write/Execute Protection）と記された読み取り／書き込み／実行のアクセス権限保護情報３０２を含む。これらは、すべてのプロセッサ１０１のTLB１０７が保持するそれらの情報から複製したものである。左端には、TLBディレクトリメモリ１２１のアドレスがプロセッサIDとTLBエントリ番号の組み合わせからできることを示し、右端には、各エントリのグループがそれぞれプロセッサ０からプロセッサＮまでに対応することを示す。TLBディレクトリメモリ１２１を用いて各プロセッサ１０１のTLB１０７にある物理ページ番号を検索するようにして、異なるプロセス同士のコヒーレンシを扱うことができるようにしてある。好ましい態様として、TLBディレクトリメモリ１２１をCAMにより実装して高速化し、次の２つの検索操作ができるようにする。１つは、書き込み許可があって物理ページ番号のマッチするページの検索であり、もう１つは、読み出し、書き込みまたは実行の許可があって物理ページ番号のマッチするページの検索である。CAMの検索ワード入力に物理ページ番号とページへのアクセス許可を含め、CAMのアドレス入力にプロセッサIDとTLBエントリ番号を連結させたものを入力して検索する。CAMをアクセスするバスは、DCRバスのようにプロセッサが占有するバスが適している。
【００３７】
図４は、本発明の１実施形態に係るキャッシュコヒーレンシ制御の方法を概略的に示すフローチャート（４００）図である。この方法は、図２に示されたようなTLBがソフトウェアにより制御されるプロセッサ１０１で実施できる。アプリケーションプログラムがキャッシュへアクセスすると開始し（ステップ４０１）、プロセッサ１０１はTLB検索を実行する（ステップ４０２）。TLB検索を実行してヒットしたときには、プロセッサ１０１はヒットしたTLBエントリのキャッシュタグを検索する（ステップ４０３）。キャッシュタグ検索でヒットしたときには、プロセッサ１０１は、キャッシュへのアクセスを指示し、キャッシュへのアクセスを実行する（ステップ４０４）。キャッシュタグ検索でヒットせずキャッシュタグミスを生じたときには、プロセッサ１０１は、システムメモリへのアクセスを指示し、システムメモリへのアクセスを実行する（ステップ４０５）。TLB検索を実行してヒットせずTLB割り込みを生じたときには（ステップ４０２）、プロセッサ１０１はTLB割り込みがページフォールトであるか否かを判定する（ステップ４０６）。「いいえ」と記された、TLB割り込みがページフォールトでない、即ちページテーブルにTLBエントリ、即ち登録情報のページがあると判定したときは、プロセッサ１０１はコヒーレンシハンドラによりTLBミス例外処理またはストレージ例外処理のサブルーチンを実行する（ステップ４０７）。「はい」と記された、ページフォールトであると判定したときは、プロセッサ１０１はページフォールト割り込みを発生し、OSカーネル処理メモリ管理部によりページフォールト処理のサブルーチンを実行する（ステップ４０８）。
【００３８】
図５は、コヒーレンシハンドラのTLBミス例外処理およびストレージ例外処理のサブルーチン（図４のステップ４０７参照）におけるビクティムTLBエントリ、即ち登録情報のエビクション処理を示すフローチャート（５００）図である。コヒーレンシハンドラのTLBミス例外処理およびストレージ例外処理のサブルーチンは、それぞれTLBミス例外処理入口（ステップ５０１）およびストレージ例外処理入口（ステップ５０２）から開始する。TLBミス例外処理では、アドレスのマッチするエントリ、即ち登録情報がTLB１０７には存在しないので、プロセッサ１０１は、ページテーブル１０８からマッチするエントリ、即ち登録情報をTLB１０７に取り込むTLBリプレースメントを実行する（ステップ５０３）。この時、TLBディレクトリメモリ１２１ではエントリ、即ち登録情報の更新が行われる。TLBリプレースメントを実行した時、プロセッサ１０１は、エビクションされて破棄されるビクティムTLBエントリ、即ち登録情報がカバーする物理ページに属するローカルのデータキャッシュラインをフラッシュ（コピーバックおよび無効化）する（ステップ５０４）。これにより、ローカルのプロセッサではTLBに登録されるエントリ、即ち登録情報のページだけが確実にキャッシュされているので、コヒーレンシ制御が必要であるかどうかは、TLBミス割り込みまたはストレージ割り込みの時にリモートのプロセッサのTLBを調べるだけで判定することができる。その後、プロセッサ１０１は、TLBミス割り込みまたはストレージ割り込みを生じたメモリアクセスがデータアクセスであるか命令アクセスであるかを判定する（ステップ５０５）。プロセッサ１０１は、データアクセスであるときには、MESIエミュレーション処理のサブルーチン５０６へ進み、命令アクセスであるときには、命令キャッシュコヒーレンシ処理のサブルーチン５０７へ進む。
【００３９】
先に少し言及したが、TLBミス割り込みおよびストレージ割り込みの両方の場合でTLBエントリ、即ち登録情報を入れ替えたり更新したりする時に、ローカルのTLBとリモートのTLBの間で、排他的制約、例えば、書き込み時無効化方式である次のようなMESIプロトコルの制約に従った読み出し・書き込み・実行の権限を設定する。
・リードオンリーデータの共有
複数のプロセッサは、同じ物理ページへの読み出しと実行の権限を共有可能にする。データ読み出しまたは命令フェッチでTLB割り込みを生じ、リモートのプロセッサがその物理ページへ書き込みの権限を持つ場合は、そのリモートのプロセッサに対して、クリーン（CLEAN）コマンドをプロセッサ間割り込み（IPI）で通知して、リモートのプロセッサにその物理ページへの書き込みの権限をクリアにさせる。
・書き込みデータの排他制御
あるプロセッサが書き込みの権限を持つ物理ページに対し、他のプロセッサはどのようなアクセス権限も持たないようにする。つまり、ローカルのTLBに書き込みの権限が存在する物理ページには、リモートのTLBにどのようなアクセス権限も与えない。従って、書き込みアクセスがTLBミス割り込みまたはストレージ割り込みを起こしたときに、リモートのプロセッサがその物理ページへのアクセス権を持っているかどうかリモートのTLBを調べ、持っていれば、プロセッサ間割り込み（IPI）を使って、リモートのプロセッサにその物理ページのデータをリモートのキャッシュからフラッシュ（FLUSH）させる。
【００４０】
図６に、ソフトウェアの制御でMESIプロトコルの制約を設ける１例として、MESIエミュレーション処理のフローチャート（６００）を示す。プロセッサ１０１は、図５でデータアクセスであると判定したとき（ステップ５０５）、MESIエミュレーション処理のサブルーチン５０６へ進み、その処理を開始する（ステップ６０１）。先ず、プロセッサ１０１は、TLB割り込みを生じた誤アクセスがデータ書き込みか読み出しかを判定する（ステップ６０２）。誤アクセスが読み出しの場合、プロセッサ１０１は、ローカルのTLB１０７とTLBディレクトリメモリ１２１における、誤アクセスの物理ページに対応するエントリ、即ち登録情報のR（Read：読み出し）の属性（attribute）を、ページテーブル１０８のPTE（Page Table Entry：ページテーブルエントリ）のUR（User Readonly：ユーザーリードオンリー）およびSR（Supervisor Read only：スーパーバイザーリードオンリー）のビットによりマスクされて、オンにする（ステップ６０３）。次に、プロセッサ１０１は、TLBディレクトリメモリ１２１を誤アクセスの物理ページについて検索して、リモートのTLBがその物理ページについてのW（Write：書き込み）の権限を持っているか否かを判定する（ステップ６０４）。「いいえ」と記された、Wの権限を持っていないときは、終了する（ステップ６０５）。「はい」と記された、Wの権限を持っているときは、プロセッサ１０１は、リモートのプロセッサに対して、クリーンコマンドをプロセッサ間割り込み（IPI）で通知して、リモートのプロセッサにその物理ページへの書き込みの権限をクリアにさせる。即ち、リモートのプロセッサは、データキャッシュをコピーバックして、リモートのTLBにおけるその物理ページに対応するエントリ、即ち登録情報のWの属性をディスエーブルにする（ステップ６０６）。リモートのTLBのそのエントリに論理から物理へのアドレス変換は残る。続いて、プロセッサ１０１は、TLBディレクトリメモリ１２１でのリモートのTLBに関するその物理ページに対応するエントリ、即ち登録情報のWの属性をクリアにし（ステップ６０７）、そして、終了する（ステップ６０８）。
【００４１】
一方、誤アクセスが書き込みの場合（ステップ６０２）、プロセッサ１０１は、ローカルのTLB１０７とTLBディレクトリメモリ１２１における、誤アクセスの物理ページに対応するエントリ、即ち登録情報のWの属性を、ページテーブル１０８のPTEのUW（User Write：ユーザー書き込み）およびSW（Supervisor Write：スーパーバイザー書き込み）のビットによりマスクされて、オンにする（ステップ６０９）。次に、プロセッサ１０１は、TLBディレクトリメモリ１２１を誤アクセスの物理ページについて検索して、リモートのTLBがその物理ページについてのR、WまたはX（eXecute：実行）の権限を持っているか否かを判定する（ステップ６１０）。「いいえ」と記された、R、WまたはX の権限を持っていないときは、終了する（ステップ６０５）。「はい」と記された、R、WまたはX の権限を持っているときは、プロセッサ１０１は、リモートのプロセッサに対して、フラッシュコマンドをプロセッサ間割り込み（IPI）で通知して、リモートのプロセッサにその物理ページへのアクセス権限を与えずにその物理ページのデータをリモートのキャッシュからフラッシュさせる。即ち、リモートのプロセッサは、データキャッシュをコピーバックして無効化し、リモートのTLBにおけるその物理ページに対応するエントリ、即ち登録情報のR、W、Xの属性をディスエーブルにする（ステップ６１１）。リモートのTLBのそのエントリに論理から物理へのアドレス変換は残る。続いて、プロセッサ１０１は、TLBディレクトリメモリ１２１でのリモートのTLBに関するその物理ページに対応するエントリ、即ち登録情報のR、W、Xの属性をクリアにし（ステップ６１２）、そして、終了する（ステップ６０８）。
【００４２】
このように、MESIプロトコルの制約に従った読み出し・書き込み・実行の権限設定によるTLB使用のスヌープフィルタリング、即ちスヌープの削減が行われる。ハードウェアでMESIプロトコルを実施するときに問題となるスヌープ要求のブロードキャストは、そのデータをカバーする物理ページがリモートのTLBにも登録されている場合に限定する、という判断ステップが加えられる。従って、ソフトウェアの制御でMESIプロトコルの制約を設けるMESIエミュレーション処理の方が、ハードウェアでMESIプロトコルを実施するよりも、スケーラビリティを高めることができる。
【００４３】
本発明の１実施形態に係るキャッシュコヒーレンシ制御のコヒーレンシハンドラにより、データキャッシュ同士のコヒーレンシだけでなく、命令キャッシュとデータキャッシュのコヒーレンシを制御することができる。それは、書き込み許可の権限を持つ書き込み可能なページへの命令フェッチでTLBミス割り込みを起こしたとき、その命令キャッシュラインを無効化させることにより実現される。Linuxのように、ダイナミックリンクライブラリ等をサポートするには、命令キャッシュがデータキャッシュにコヒーレントである必要があるが、Linuxでは、ユーザスペースで書き込み可能なページをフェッチしたときにだけ、命令キャッシュを無効化すれば良い。
【００４４】
図７に、ソフトウェアの制御による命令キャッシュコヒーレンシ処理のフローチャート（７００）を示す。プロセッサ１０１は、図５で命令アクセスであると判定したとき（ステップ５０５）、命令キャッシュコヒーレンシ処理のサブルーチン５０７へ進み、その処理を開始する（ステップ７０１）。先ず、プロセッサ１０１は、命令フェッチでTLBミス割り込みを起こした物理ページについて、ページテーブル１０８のPTEがユーザー書き込み許可の権限を持つかを判定する（ステップ７０２）。「はい」と記された、そのPTEがユーザー書き込み許可の権限を持つときは、プロセッサ１０１は、その物理ページについてリモートのTLBがユーザー書き込み許可の権限を持つかを判定する（ステップ７０３）。「はい」と記された、そのTLBがユーザー書き込み許可の権限を持つときは、プロセッサ１０１は、リモートのプロセッサに対して、クリーンコマンドをプロセッサ間割り込み（IPI）で通知して、リモートのプロセッサにユーザー書き込み許可の権限をクリアにさせる。即ち、リモートのプロセッサは、データキャッシュについてdcbst（data cache block store）命令を出してデータキャッシュラインを格納し、リモートのTLBにおけるWの属性をディスエーブルにする（ステップ７０４）。リモートのTLBのそのエントリにおいて論理から物理へのアドレス変換は残る。次に、プロセッサ１０１は、ステップ７０３での判定で「いいえ」と記された、そのTLBがユーザー書き込み許可の権限を持たないときと同様に、命令キャッシュ合同クラスを無効にするiccci（instruction cache congruence class invalidate）により、ローカルの命令キャッシュを無効化する（ステップ７０５）。続いて、プロセッサ１０１は、ステップ７０２での判定で「いいえ」と記された、そのPTEがユーザー書き込み許可の権限を持たないときと同様に、ローカルのTLB１０７とTLBディレクトリメモリ１２１における、命令フェッチでTLBミス割り込みを起こした物理ページに対応するエントリ、即ち登録情報のXの属性を、そのPTEのUX（User eXecute：ユーザー実行）およびSX（Supervisor eXecute：スーパーバイザー実行）のビットによりマスクされて、オンにし（ステップ７０６）、そして、終了する（ステップ７０７）。
【００４５】
TLBディレクトリメモリ１２１にはセマフォを使って逐次にアクセスする。これにより、複数のプロセッサ１０１がTLBディレクトリメモリ１２１を同時に更新することからTLBディレクトリメモリ１２１は保護される。図８に、セマフォの使用をコヒーレンシハンドラの入口と出口のフロー（８００）にて示す。コヒーレンシハンドラの入口では、開始（ステップ８０１）し、セマフォを取得して（ステップ８０２）、終了する（ステップ８０３）。コヒーレンシハンドラの出口では、開始（ステップ８０４）し、セマフォを通知して（ステップ８０５）、終了する（ステップ８０６）。TLBディレクトリメモリ１２１全体を１つのセマフォで排他的にアクセスすることもできるが、より好ましい実装態様としては、複数のプロセッサがスケーラビリティを良くしてTLBディレクトリメモリ１２１を同時にアクセスできるように、複数のグループに分割された物理ページのグループ毎にセマフォを分割して割り当てる。例えば、物理ページ番号をＳで割った剰余系をセマフォＩＤとしながら、Ｓ個のセマフォを生成し、分割された物理ページをグループ毎独立に保護する。ここで、
セマフォＩＤ＝ｍｏｄ（物理ページ番号、Ｓ）  （ｍｏｄ（ａ，ｂ）はａをｂで割った余りを表す）
である。この考え方を分散共有メモリシステムであるNUMAに適用するならば、異なるセマフォをNUMAノード毎に割り当てることができる。そうすると、リモートアクセスの行われる時にだけ、リモートのTLBディレクトリメモリの参照とそのセマフォの獲得がなされ、そうでなければ、ローカルのTLBディレクトリメモリの参照とそのセマフォの獲得をするだけで良い。
【００４６】
NUMAシステムでは、ローカルのシステムメモリへのアクセス頻度がリモートのシステムメモリへのアクセス頻度よりも高くなるよう、ジョブのプロセッサと物理メモリへの割り付けは最適化される。そのようなNUMAシステムに適用する場合、好ましい態様として、TLBディレクトリメモリとセマフォの両方をNUMAノードへ分散させる。分散されたTLBディレクトリメモリは、ローカルのシステムメモリの物理ページ番号と、それをキャッシュするプロセッサのIDを記録し、分散されたセマフォに、対応して分散したTLBディレクトリメモリを保護させる。結果として、リモートのTLBディレクトリメモリとリモートのセマフォは、リモートアクセスが生じた時にだけ参照される。それ以外のローカルのアクセスは、ローカルのTLBディレクトリメモリとローカルのセマフォだけを使って処理することができる。
【００４７】
コヒーレンシのハードウェアサポートのコストは、ローカルのシステムメモリへのアクセスでは安価であるが、リモートのシステムメモリへのアクセスでは高価である。そこで、ローカルのシステムメモリへのアクセスには安価なスヌープバスを用い、リモートのシステムメモリへのアクセスには本発明に係るキャッシュコヒーレンシ制御を適用するという、SMPとNCC-NUMAのハイブリッドシステムへ拡張することができる。つまり、ローカルのシステムメモリへのアクセスにコヒーレンシのハードウェアサポートがあり、リモートのシステムメモリへのアクセスには本発明に係るキャッシュコヒーレンシのソフトウェア制御を使って、全体としてコヒーレントな共有メモリ型マルチプロセッサシステムを構成することができる。図９に、そのようなSMPとNCC-NUMAのハイブリッドシステムへ拡張した構成の１例として、コヒーレントな共有メモリ型マルチプロセッサシステム９００を示す。各ノードは、複数のプロセッサ９０１と、コヒーレント共有バス、即ち共有バスコヒーレントSMP９０２により各プロセッサ９０１に接続されたシステムメモリ９０３と、ブリッジ機構９０４により共有バスコヒーレントSMP９０２に接続されたTLBディレクトリメモリ９０５およびセマフォハンドラ９０６とを含む。セマフォハンドラ９０６は、複数のプロセッサ９０１がTLBディレクトリメモリ９０５にセマフォによって逐次アクセスするために設けられる。また、各ノードは、NCC-NUMA機構９０７により相互に接続される。各ノードが安価なNCC-NUMA機構９０７により相互に接続されるので、共有メモリ型マルチプロセッサシステム９００は、ハードウェアのコストを抑えてノードの数を増大させる、即ちスケーラビリティを向上させることができる。
【００４８】
TLBディレクトリメモリのエントリ数に制約なく、ローカルのシステムメモリでもリモートのシステムメモリでも自由に対応付けできるとすると、TLBディレクトリメモリのサイズはプロセッサの数に比例して増える。例えば、１０２４のプロセッサがそれぞれ１０２４のエントリのTLBを持ち、１エントリにつき４バイトであれば、次の計算より、
（１０２４プロセッサ）＊（１０２４エントリ）＊（４バイト）＝４Ｍバイト
TLBディレクトリメモリのサイズは４Ｍバイトである。
そこで、TLBディレクトリメモリのサイズを節約するために、例えばNUMAシステムに適用する場合、図１０に示すように、個々のプロセッサ１００１がリモートのシステムメモリRSM（Remote System Memory）に割り当てるRSM 用のTLBエントリ１００２の数に制約を加えて、残りをローカルのシステムメモリLSM（Local System Memory）に割り当てるLSM 用のTLBエントリ１００３として用いる。そうすると、LSM 用のローカルのTLBディレクトリメモリ１０００は、TLBエントリの数が制約された、リモートのプロセッサRP（Remote Processor）用のTLBディレクトリを複製したエントリと、残りのTLBエントリの数が割り当てられた、ローカルのプロセッサLP（Local Processor）用のTLBディレクトリを複製したエントリとで構成され、その容量を削減することができる。特に、NUMAノードの数をＮ、CPUあたりのTLBエントリ数をＥ, そのうち、リモートのシステムメモリに割り当てるエントリ数をＲとすれば、ローカルのシステムメモリへ割り当てられるTLBエントリの数はＥ−Ｒになるので、ノード当たりTLBディレクトリメモリのエントリ数は、Ｅ＊Ｎから（Ｎ−１）＊Ｒ＋１＊（Ｅ−Ｒ）に削減される。上記の例では、１０２４のプロセッサが２５６のNUMAノードに分散し、ノード内は４−ｗａｙのSMPである構成で、リモートのTLBに割り当てるTLBエントリの数を１６に制約を加えれば、TLBディレクトリメモリのサイズは、次の計算より、８１．４Ｋバイトになる。
（１０２０プロセッサ）＊（１６エントリ）＊（４バイト）＋（４プロセッサ）＊（１００８エントリ）＊（４バイト）＝８１．４Ｋバイト
それをCAMに実装すると、４５ｎｍの半導体テクノロジでは、TLBディレクトリメモリに要する領域面積はわずか１ｍｍ２である。
【００４９】
上記説明のとおり、本発明によるソフトウェアでのキャッシュコヒーレンシの制御を実施すれば、共有メモリ型マルチプロセッサシステムを汎用部品のような廉価な部品で構成できるので、ハードウェアコストをクラスタ並みに抑えてスケーラビリティを向上させることができる。また、各プロセッサのTLB情報だけを管理する小規模なTLBディレクトリメモリで物理ページの検索を行うことにより、複数のプロセスを扱えるようにするばかりでなく、アプリケーションプログラムの変更をも不要にして、ソフトウェアコストを生じずにスケーラビリティを向上させることができる。
【００５０】
以上、実施態様を用いて本発明の説明をしたが、本発明の技術的範囲は実施態様について記載した範囲には限定されない。実施態様に種々の変更又は改良を加えることが可能であり、そのような変更又は改良を加えた態様も当然に本発明の技術的範囲に含まれる。
【図１】
2012070291.tif 000003
【図２】
2012070291.tif 000004
【図３】
2012070291.tif 000005
【図４】
2012070291.tif 000006
【図５】
2012070291.tif 000007
【図６】
2012070291.tif 000008
【図７】
2012070291.tif 000009
【図８】
2012070291.tif 000010
【図９】
2012070291.tif 000011
【図１０】
2012070291.tif 000012
【国際調査報告】
2012070291.tif 000013
2012070291.tif 000014
2012070291.tif 000015
2012070291.tif 000016