(57)【要約】【解決手段】本発明は、アトミック機能キャッシュライトバック状態マシンを管理する技術を提供する。まずライトバックを選択し、アトミック機能データアレイにおいて予約ラインを示す予約ポインタを設置し、次のライトバックを選択し、そのライトバック選択の予約ポイント用のエントリを消去する。これで有効な予約ラインがライトバック用に選ばれることが防止され、変更命令が無効にされるのを回避する。【選択図】図２
2008503821.tif 000002
【特許請求の範囲】
【請求項１】
アトミック機能データアレイにおいて予約されたラインを示す予約ポインタを設置するステップと、
ライトバック選択をするステップと、
予約ラインがライトバック用に選択されるのを防止するためにライトバック選択の予約ポイント用のエントリを消去するステップと、
を備えることを特徴とするアトミック機能キャッシュライトバックコントローラ管理方法。
【請求項２】
前記ライトバック選択をするステップは、ビクティムエントリ選択機能を使用することを特徴とする請求項１に記載のアトミック機能キャッシュライトバックコントローラ管理方法。
【請求項３】
前記ビクティムエントリ選択機能は、ＬＲＵ（Least Recently Used）アルゴリズムで構成されることを特徴とする請求項２に記載のアトミック機能キャッシュライトバックコントローラ管理方法。
【請求項４】
アトミック機能キャッシュデータアレイを有するアトミック機能キャッシュと、
アトミック機能キャッシュデータアレイにおいて予約されたラインを示すように構成される予約ポインタと、
次のライトバック選択をするように構成されたビクティムエントリ選択機構と、
を備え、
前記ビクティムエントリ選択機構は、有効なライトバックエントリが選択されているときに予約ラインがライトバック用に選択されることを防止するように構成されることを特徴とするキャッシュライトバック実行システム。
【請求項５】
アトミック機能キャッシュライトバックコントローラを管理するコンピュータプログラム製品であって、そのコンピュータプログラム製品はコンピュータプログラムが格納された媒体を有し、前記コンピュータプログラムは、
アトミック機能データアレイにおいて予約されたラインを示す予約ポインタを設置するためのプログラムコードと、
ライトバック選択をするためのコンピュータプログラムコードと、
有効な予約ラインがライトバック用に選択されることを防止するように前記ライトバック選択用の予約ポイントのエントリを消去するためのコンピュータプログラムコードと、
を備えることを特徴とするコンピュータプログラム製品。
【請求項６】
アトミック機能キャッシュライトバックコントローラを管理するプロセッサであって、そのプロセッサが含むコンピュータプログラムは、
アトミック機能データアレイにおいて予約されたラインを示す予約ポインタを設置するためのプログラムコードと、
ライトバック選択をするためのコンピュータプログラムコードと、
有効な予約ラインがライトバック用に選択されることを防止するように前記ライトバック選択用の予約ポイントのエントリを消去するためのコンピュータプログラムコードと、
を備えることを特徴とするプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全体としてコンピュータシステムの分野に関し、とくにマイクロプロセッサにおける小容量キャッシュシステムに関する。
【背景技術】
【０００２】
高性能演算処理システムは、処理対象のデータを素早く得られるよう、高速なメモリアクセスと低メモリ遅延が要求される。システムメモリは、プロセッサへデータを供給するのに時間がかかる場合があるため、キャッシュを設けることによってデータをプロセッサの近くに保持してデータへのアクセスタイムをより短くする設計がなされる。キャッシュ容量を大きくした場合、システムの性能は全体的に向上するものの、小容量のキャッシュと比べて待ち時間の長期化や設計の複雑化を招いてしまう場合もある。通常、キャッシュをより小容量に設計するのは、システムアプリケーションレベル、とくに通信処理やグラフィクス処理における他のプロセッサとの同期や通信を高速化する手段をプロセッサに与えたい場合である。
【０００３】
プロセッサは、メモリとの間でロード（Ｌｏａｄ）命令とストア（Ｓｔｏｒｅ）命令によってデータの送出と取り出しをする。キャッシュはシステムメモリからのデータで一杯になる。プロセッサによりアクセスされるデータの大部分または全部がキャッシュの中にあるという状態が望ましい。その状態は、アプリケーションデータサイズがキャッシュ容量と同じか小さければ起こり得る。一般に、キャッシュ容量は、設計の都合によりあるいは技術的な理由により通常は制限され、アプリケーションデータ全体を格納することはできない。これは、プロセッサがキャッシュにない新たなデータにアクセスし、その新たなデータを格納できるキャッシュスペースがなくなったときに問題となる。それゆえ、キャッシュコントローラは、メモリから新たなデータが送られてきたときにそのデータのための適当なスペースをキャッシュ内に見つけ出す必要がある。
【０００４】
こうした状況を処理するため、キャッシュコントローラはＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）アルゴリズムを用いる。ＬＲＵアルゴリズムは、新たなデータをのためにどの場所を使うかについてデータアクセスの履歴情報に基づいて決定する。ＬＲＵが、システムメモリと一致の取れているライン、例えば共有（Ｓｈａｒｅｄ）状態のラインを選んだ場合、新しいデータはその場所に上書きされる。変更（Ｍｏｄｉｆｉｅｄ、そのデータがシステムメモリと一致が取れておらずキャッシュにだけ存在するという意味）状態とマークされたラインをＬＲＵが選んだときは、キャッシュコントローラがこの場所にある「Ｍｏｄｉｆｉｅｄ」のデータをシステムメモリに書き戻す。この動作はライトバック（ｗｒｉｔｅ−ｂａｃｋ、書き戻し）またはキャストアウト（ｃａｓｔｏｕｔ、追い出し）と呼ばれ、そのライトバックデータを含んだキャッシュの場所はビクティムキャッシュライン（Ｖｉｃｔｉｍ  Ｃａｃｈｅ  Ｌｉｎｅ）と呼ばれる。
【０００５】
バスエージェント（キャッシュへのバスコマンドを処理するバスインタフェースユニット）は、バス操作を通じてシステムメモリにデータを送ることによってライトバック操作をできるだけ早く完了するよう試みる。ライトバック（「ＷＢ」とも呼ぶ）は、そのデータがメインメモリに送られるので待ち時間の長いバス操作である。
【０００６】
キャッシュ制御スキームには２つの異なる種類がある。コヒーレント（整合的）キャッシュスキームとノンコヒーレント（非整合的）キャッシュスキームである。ノンコヒーレントの場合、それぞれのキャッシュはそのデータの唯一のコピーを持つとともに、他のキャッシュは同じデータを持たない。この手法は、比較的簡単に実現できる。しかし、マルチプロセッサシステムの全体にデータが配信されなければならないことが多いので効率的ではない。そこで、コヒーレントキャッシュスキームが用いられ、そのスキームの下で、最新データが使用または配信され、それ以外のときは有効なデータとしてマークされることが保証される。
【０００７】
整合性を強める一つの従来技術は、変更（Ｍｏｄｉｆｉｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）、無効（Ｉｎｖａｌｉｄ）のＭＥＳＩシステムである。ＭＥＳＩでは、データ整合性を保証するために、マルチプロセッサシステムにおけるキャッシュ内のデータが上記のいずれかの状態にマークされる。そのマーキングは、ハードウェアであるメモリフローコントローラによってなされる。
【０００８】
スヌーピングはプロセスであり、そのプロセスによってスレーブキャッシュがシステムバスを監視し、転送されたアドレスをキャッシュディレクトリのアドレスと比較することでキャッシュ整合性を保つ。マッチしたデータが見つかった場合には、追加操作を実行できる。バススヌーピングという用語とバス監視という用語は同義である。
【０００９】
スヌープ命令の一部として使われる無効化命令は、他のキャッシュに対してそのデータがもはや有効でないことを伝えてそのラインに無効のマークをするために発行される。言い換えれば、無効な状態とは、そのキャッシュのラインがそのキャッシュにおいて無効であること、または、このラインがもはや利用できないことを示す。したがって、そのキャッシュの範囲内では、このデータラインは他のデータ転送によって自由に上書きできる。
【００１０】
マルチプロセッサシステムにおいて、テストアンドセット命令、コンペアアンドスワップ命令、フェッチアンドインクリメント命令やフェッチアンドデクリメント命令といった複数操作は、不可分的に処理される必要がある。すなわち、これら複数操作の合間に同じアドレスへのストアが発生してはならない。これら複数操作は、いわゆるアトミック操作と呼ばれる。一般に、これらの操作はロック獲得やセマフォー操作に使われる。しかし、さらに機能的な操作を構築するためにＬＬ（Ｌｏａｄ−Ｌｏｃｋｅｄ）およびＳＣ（Ｓｔｏｒｅ−Ｃｏｎｄｉｔｉｏｎａｌ、ストアコンディショナル）のような小さな構造ブロックだけを提供する実装もある。また、これら二つの操作（ＬＬとＳＣ）をアトミックに結束させるため（すなわち、ＬＬはロック値のための予約を設定し、ＳＣはその予約が残っていればストアに成功する。同じアドレスへのストア操作はいずれも予約フラグをリセットできる。）に予約フラグを導入するプロセッサもある。
【００１１】
一般に、アトミック機能はスヌープキャッシュのような整合ポイントに実装される。スヌープキャッシュは、他のプロセッサのストア操作をスヌープするとともに、ロックラインをキャッシュすることで性能を向上させる。アトミックラインのデータリクエストを実行しているとき、異なるコマンドはたくさんある。一つは、ロードアンドリザーブ指令である。ロードアンドリザーブは、ソースプロセッサにより発行され、リクエストされたデータをそのキャッシュが持っているかどうかを判定するために関連するキャッシュを参照する。目標のキャッシュがデータを持っていた場合、そのキャッシュに「予約」を示すフラグが立てられる。予約フラグは、プロセッサがそのラインについてロック獲得のために予約することを意味する。言い換えれば、メインメモリにおけるひとかたまりのデータのロック獲得（独占的な所有権の獲得）は、まずロードアンドリザーブを使用して予約してからＳＣ命令を通じてその所有権を示すために予約したラインを変更することで達成される。ＳＣ命令は、予約フラグがまだアクティブであることを条件とする。予約が消去されるのは、他のプロセッサがＳＣ命令または予約を消すタイプのスヌープ命令を同じライン上で実行して同様のロック獲得を要求したときである。プロセッサは、それからロードアンドリザーブを処理するためにその予約情報をキャッシュからプロセッサへコピーする。基本的に、プロセッサは、ＳＣ命令の実行によりロックを完了できるよう、予約したライン上でロックがかかってないデータパターンがないか探している。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかし、その情報をキャッシュが持っていない場合、その情報獲得を試行するためにバスコマンドが発せられる。もしその情報を持つキャッシュがなかった場合、そのデータはメインメモリから取り出される。データを受け取れば、予約フラグが立てられる。
【００１３】
アトミック操作の狭いループの特性により、また、通常のプログラミングで同じロックを再度使用する可能性の高さにより、最初のロック獲得ループからの予約ラインはその後のロック獲得にも必要となる。ロードアンドリザーブからのこの予約データは、同じデータの所有権を次のロック獲得ループが必要とするので、メインメモリへライトバックしてはならない。予約ラインのライトバックやメインメモリからの同じデータの再読込がなくなる分、性能は向上する。
【００１４】
以上により、従来のアトミック予約における種々の問題に対処するためには、アトミック機能が必要となる。
【課題を解決するための手段】
【００１５】
本発明は、アトミック機能キャッシュライトバックコントローラの管理技術を提供する。アトミック機能キャッシュデータアレイにおいて予約ラインを示す予約ポインタが設置される。ライトバックを選択するための予約ポイントのエントリを消去することにより、有効な予約ラインがライトバック用に選択されることを防止する。ある態様においては、ＬＲＵアルゴリズムを使用してライトバックの選択を実現する。別の態様においては、予約ポイントについてライトバックの選択を実行する。
【発明を実施するための最良の形態】
【００１６】
以下、発明の理解を十分なものとする目的で多数の具体的な詳述をしている。しかし、当業者であればそこまで具体的な詳述がなくとも本発明を実施できることは十分に理解されるところである。別の例では、周知な構成についても模式図やブロック図のかたちで描いているが、これは本発明が不明確とならないよう必要な範囲を超えて詳述しているためである。なお、ネットワーク通信や電磁信号の技術などに関しては、そのような記載が本発明を完全に理解するのに必要とされない限り、また、関連技術の当業者が理解できる範囲にある限り、大半の箇所でその詳述を省略する。
【００１７】
さらに付け加えるならば、プロセッシングユニット（ＰＵ）は装置内の計算のための単一プロセッサであってもよい。この場合のＰＵは、一般的にはＭＰＵ（メインプロセッシングユニット）と呼ぶ。プロセッシングユニットはまた、計算装置における何らかの方法論やアルゴリズムにしたがった計算負荷を分担する多数のプロセッシングユニットのうちの１つであってもよい。以下の詳細な説明でプロセッサについて言及するときは、特に明記しない限りは、ＭＰＵが装置における単一の計算素子かどうかや、ＭＰＵが他のＭＰＵと計算素子を共有しているかどうかは問わず、すべてＭＰＵという用語を用いる。
【００１８】
特に断らない限り、以下に述べられる機能はすべてハードウェアやソフトウェア、あるいはそれらの組み合わせによって実現される。しかし、これらの機能は、特に断らない限り、コンピュータまたは電子データプロセッサのようなプロセッサにより、コンピュータプログラムコードのようなコード、ソフトウェア、および／または、そうした機能を実現するようコード化された集積回路にしたがって実現されるのが好ましい。
【００１９】
図１は、マルチプロセッサシステム１００について開示する。このマルチプロセッサシステム１００は、一般的な中央演算処理装置（ＭＰＵ１）１１０、中央演算処理装置（ＭＰＵ２）１１１とともに開示され、命令ユニット、命令キャッシュ、データキャッシュ、固定小数点ユニット、浮動小数点ユニット、ローカルストレージなどを含み得る。各プロセッサは、アトミック機能（ＡＦ）と呼ばれる、より下位レベルのキャッシュへ接続される。アトミック機能（ＡＦ１キャッシュ）１２０、アトミック機能（ＡＦ２キャッシュ）１２１は、順番にシステムバス１４０に繋がったバスインタフェースユニット（バスＩＦ）１３０，１３１に接続される。他のプロセッサのキャッシュは、プロセッサ間通信をするためにバスインタフェースユニットを介してシステムバスに接続される。プロセッサに加えて、メモリコントローラ（ＭｅｍＣｔｒｌ）１５０がシステムバス１４０へ同様に取り付けられる。システムメモリ１５１は、マルチプロセッサが共有する共通ストレージ用のメモリコントローラへ接続される。
【００２０】
全体として、マルチプロセッサシステム１００は、ロック獲得のソフトウェアループのロードアンドリザーブ命令から予約されたラインにおいてライトバック操作を無効にする機構を提供する。ロードアンドリザーブ命令から予約されたラインは、このロック獲得ループにおける次のＳＣ命令において使用される。よって、メモリにライトバックしてまた戻す代わりにキャッシュのラインを予約されたままにしておけば性能向上につながる。種々のポインタを用いることにより、ライトバック用のビクティムラインがＬＲＵアルゴリズムによって選択されるとともに、このポインタをスキップすることにより予約ラインは選択されない。
【００２１】
図２は、アトミック機能１４２（以下、適宜、単に「アトミック機能」や「ＡＦ１４２」とも呼ぶ）をより詳細に示す。アトミック機能は、データアレイおよびその制御ロジック用のデータアレイ回路１４６を含む。制御ロジックは、ディレクトリ１４７と、プロセッサコアからの命令を処理するＲＣ（リードアンドクレイム）有限状態マシン１４３と、ライトバックを処理するライトバック状態マシン１４４と、スヌープ状態マシン１４５と、を含む。ディレクトリ１４７は、キャッシュタグとその状態を保持する。
【００２２】
ＲＣ有限状態マシン１４３は、コールされたアトミック命令、ロードアンドリザーブ命令、プロセス間同期用のＳＣ命令を実行する。この一連の命令が目的とするところの一つは、マルチプロセッサシステムにおいて、共通データの所有権をあるプロセッサに付与することによって、プロセッサ間で操作を同期させることである。
【００２３】
全体として、一連の命令の目的は、マルチプロセッサシステムにおいて一度に一つのプロセッサにデータの所有権を付与することにより、プロセッサ間で操作を同期させることである。ライトバック状態マシン１４４は、ＭＰＵが発したロード命令やストア命令にキャッシュミスが生じたときや、アトミック機能（ＡＦ）キャッシュが一杯でありビクティムエントリが「変更」の状態となっているときに、ＲＣ有限状態マシン１４３に対応するライトバックを処理する。スヌープ状態マシン１４５は、システム全体にわたってメモリ整合性を維持するためにシステムバスから送られたスヌープ操作を処理する。
【００２４】
図３は、マルチプロセッサシステムにおいて二つのプロセッサ間でロック獲得をするシナリオの例を示す。ロック獲得操作は、ロードアンドリザーブアトミック命令およびＳＣアトミック命令の２つのメインアトミック命令を必要とする。
【００２５】
ＭＰＵ１にてロック獲得するシナリオは、まず、解除されたロックデータパターン（説明を簡単にするためゼロとする）がロードされるまで命令Ａでのロードアンドリザーブでループすることとする。この命令の間、ＲＣ有限状態マシン１４３の予約アドレスに予約フラグが立てられる。他のプロセッサによりロックが解除されると、命令ＡでＳＣと呼ばれる次の命令に続く。これは、そのプロセッサＩＤをアドレスＡのアトミックラインにストアすることによりそのロックを完成させるステップである。しかし、このストアは、予約フラグがまだアクティブであることを条件とする。さもなくば、他方のプロセッサは、このＳＣ命令の直前に同じロック獲得のためのストア命令を発行できてしまう。
【００２６】
アトミック機能キャッシュにはキャッシュ整合プロトコルが採用されるので、このストアは同じロックラインアドレス上のキャッシュラインキル命令または現在の予約をキルする読出専用スヌープ命令を受け取ることによりスヌープされることがある。
【００２７】
ＳＣの成功によりそのロックが達成されると、予約フラグはリセットされる。ロック獲得が成功しなかった場合、ロードアンドリザーブからやり直される。したがって、その作業をするためにプロセッサは共通ストレージ領域の全面的な所有権をもつ。この間、他のプロセッサは共通領域へのアクセスが一切できないようロックアウトされる。作業が完了したら、アドレスＡに「０」をストアすることによってロックを解除する。このとき、第２のプロセッサであるＭＰＵ２は、ロードアンドリザーブ命令がゼロデータパターンを参照できるよう最新の「Ａ」データを必要とするときにロックを獲得できる。第２のプロセッサは、第１のプロセッサ上で上述のとおりロックを完成させるためにＳＣ命令を続ける。
【００２８】
ロック獲得はループ構造においてなされることが多いため、ソフトウェアは同じロックラインを何度も再利用する傾向がある。同期の性能はマルチプロセッサ通信にとって重要であり、ロックラインがローカルキャッシュから無効にされればアトミック命令に必ず重大な性能低下を招くため、前の予約ラインを保存することはいずれにしても有益となる。
【００２９】
図４は、ライトバック操作の一実施態様となる方法４００を例示する。全体として、方法４００はライトバックが必要かどうかについての意思決定プロセスを記すものである。全体的に、この実施態様は、たとえばアトミック機能（ＡＦ１４２）が単一のライトバック（ＷＢ）マシンであるような場合の例である。
【００３０】
ライトバックリクエストは、ロードアンドストア命令およびディレクトリ探索が起こったときにリードアンドクレイム（ＲＣ）マシンによってディスパッチされる。ステップ４０２において、ＤＩＲ（ディレクトリ）探索にＲＣの実行ミスがあるかどうか、および、ＡＦに空きスペースがないかどうかが判定される。「ない」と判定したときは、ステップ４０７へ進んでライトバックは必要でないと判定し、この意思決定プロセスを終了する。
【００３１】
ステップ４０３において、ＲＣは、ＤＩＲ探索３０１をし、データアレイに空スペースがないミス（３０２および３０３）を発見した直後に、ＷＢマシンをディスパッチする。空スペースがデータアレイにある場合、ライトバックは必要でない。空スペースがない場合、ステップ４０４を実行する。
【００３２】
ステップ４０４において、ビクティムエントリがＬＲＵアルゴリズムにより選択される。指定するＬＲＵのビクティムライン４０４が変更される場合、ＷＢはＡＦにスペースを設けるために、変更ライン４０５をメモリに書き戻さなければならない。
【００３３】
ステップ４０５において、ビクティムエントリが変更されているかどうかが判断される。変更されていない場合はステップ４０７を実行し、ライトバックは必要でないとみなす。変更されている場合は、ＷＢマシンはＬＲＵアルゴリズムによりビクティムエントリを選び、予約エントリをスキップする。ライトバック操作４０６を完成させる処理が、メモリへのビクティムエントリのストアとともに続く。
【００３４】
図５は、アトミック機能１２０を管理するシステム５００を示す。予約のあるアトミック機能データキャッシュには、キュッシュラインを示すポインタがある。ビクティムポインタは、アトミック命令からのミスがあるときに、変更されたエントリをライトバックするのに用いられる。ただし、そのビクティムポインタは、ミスしたデータが再読込されるときに、どの情報がアトミックキャッシュからライトバックされるべきかを意味する。ＬＲＵアルゴリズムはビクティムポインタとして予約ポインタを選択しないため、ロードアンドリザーブのデータはメモリにライトバックされず、次のＳＣ命令に用いられる。したがって、この特性は、アトミック機能キャッシュにおけるすべてのアトミック操作の性能を向上させる。
【００３５】
本発明に多くの形式や実施態様を適用し得ることは十分理解されるところである。したがって、上述の内容において本発明の趣旨や範囲を逸脱しない限り種々の変形例が形成されてもよい。本願明細書において、ここに述べる特性は、種々のプログラミングモデルの可能性も考慮する。この開示は、特定のプログラミングモデルに偏ったような読まれ方をされてはならない代わりにその潜在的な仕組みの部分に向けられて書かれており、その仕組みの上にこれらのプログラミングモデルが構築される。
【００３６】
このようにその好適な態様のいくつかを参照することにより本発明を説明したが、その態様の開示内容はあくまでも例示であって制約的な意味をもつものではない。また、上述の開示内容は広範囲の変形、修正、変更、置換を意図しており、たとえば本発明の特徴には他の特徴との組合せを必須としないものもある。そうした多くの変形例は、当業者であれば上述した実施態様の説明に基づいて十分に考えつくところである。したがって、特許請求の範囲は発明の思想と矛盾しない範囲で広く解釈されるべきである。
【図面の簡単な説明】
【００３７】
【図１】マルチプロセッシングシステムを模式的に表す図である。
【図２】アトミック機能キャッシュを模式的に表す図である。
【図３】ロック獲得命令の例を模式的に表す図である。
【図４】ライトバック操作のフローチャートを示す図である。
【図５】アトミック機能キャッシュの例を示すブロック図である。
【符号の説明】
【００３８】
１００  マルチプロセッサシステム、  １４０  システムバス、  １４２  アトミック機能、  １４３  ＲＣ有限状態マシン、  １４４  ライトバック状態マシン、  １４５  スヌープ状態マシン、  １４６  データアレイ回路、  １４７  ディレクトリ、  １５１  システムメモリ、  ３０１  ＤＩＲ検索、  ５００  システム。
【図１】
2008503821.tif 000003
【図２】
2008503821.tif 000004
【図３】
2008503821.tif 000005
【図４】
2008503821.tif 000006
【図５】
2008503821.tif 000007