(57)【要約】【課題】  キャッシュ間転送が行われるケースのメモリアクセス性能を向上させることができるマルチプロセッサシステムを提供する。【解決手段】  メモリを共有する複数のＣＰＵと一貫性制御装置１０２を有するセル１０４ａ〜１０４ｄをネットワークで接続したマルチプロセッサシステムであり、一貫性制御装置１０２が、アクセス要求と投機アクセス要求を発行する要求手段１０７と、各セルの要求手段からアクセス要求を受けるホーム手段１０８と、各セルの要求手段から投機アクセス要求を受ける所有者手段１０９を有し、要求手段はさらに、要求されたデータを保持しているセルを予測する所有者決定手段１１０と、予測に基づく処理を行うかどうかを判定する判定手段１１１を備える。【選択図】  図２
2005189928.tif 000002
【特許請求の範囲】
【請求項１】
メモリを共有する複数のＣＰＵと一貫性制御装置を有するセルをネットワークで接続したマルチプロセッサシステムであって、
前記一貫性制御装置が、
アクセス要求と投機アクセス要求を発行する要求手段と、
各セルの前記要求手段からアクセス要求を受けるホーム手段と、
各セルの前記要求手段から投機アクセス要求を受ける所有者手段を有し、
前記要求手段はさらに、要求されたデータを保持している前記セルを予測して決定する所有者決定手段と、予測に基づく処理を行うかどうかを判定する判定手段を備える
ことを特徴とするマルチプロセッサシステム。
【請求項２】
前記所有者手段は、投機アクセス要求を受けて、投機アクセス応答を発行し、
前記要求手段は、各セルの所有者手段から投機アクセス応答を受ける機能を有することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項３】
前記ホーム手段は、アクセス要求を受けて一貫性要求を発行し、
前記所有者手段は、各セルのホーム手段から一貫性要求を受ける機能を有することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項４】
前記ホーム手段はさらに、アクセス要求を受けて一時応答を発行し、
前記要求手段はさらに、各セルのホーム手段から一時応答を受ける機能を有することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項５】
前記所有者手段はさらに、投機アクセス要求を受けて、投機一貫性応答を発行し、
前記ホーム手段はさらに、各セルの所有者手段から投機一貫性応答を受ける機能を有することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項６】
前記ホーム手段はさらに、投機一貫性応答を受けた時点で該当するアクセス要求を受け取っていない場合、投機アクセス応答無効化要求を発行し、
前記要求手段はさらに、各セルのホーム手段から投機アクセス応答無効化要求を受ける機能を有することを特徴とする請求項５に記載のマルチプロセッサシステム。
【請求項７】
前記要求手段はさらに、各セルのホーム手段から投機アクセス応答無効化要求を受けて、所有者手段からの該当する投機アクセス応答を無効化する機能を有することを特徴とする請求項６に記載のマルチプロセッサシステム。
【請求項８】
前記一貫性制御装置は、要求フィルタテーブルを備え、
前記所有者手段が最近受けた要求でキャッシュに存在しないアドレスを前記要求フィルタテーブルに登録し、前記所有者手段が要求を受けたときに、前記要求フィルタテーブルに一致するエントリが存在する場合に、ＣＰＵに問い合わせを行わずに要求メッセージの処理を行うことを特徴とする請求項３に記載のマルチプロセッサシステム。
【請求項９】
前記判定手段が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によって予測動作を行うかどうかを決定することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項１０】
前記判定手段が、乱数的にあるいは一定の規則性を持って予測動作を有無を示す値を発生する判定値発生回路を有し、該判定値発生回路が出力する値によって予測動作を行うかどうかを決定することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項１１】
前記所有者決定手段が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によってどのセルに対して投機アクセス要求を発行するかを決定することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項１２】
前記所有者決定手段が、乱数的にあるいは一定の規則性を持ってセルの番号を示す値を発生するセル番号発生回路を有し、
該セル番号発生回路が出力する値によってどのセルに対して投機アクセス要求を発行するかを決定することを特徴とする請求項１に記載のマルチプロセッサシステム。
【請求項１３】
前記ネットワークが、１つ以上のチャネルを有し、
前記チャネルは、そのチャネルを流れるメッセージに関して、送信元セルと送信先セルの組が同一のメッセージ間の到着順序のみを保障し、異なる組のメッセージ間の到着順序は保障しない構成であることを特徴とする請求項１から請求項１２の何れか１項に記載のマルチプロセッサシステム。
【請求項１４】
メモリを共有する複数のＣＰＵと一貫性制御装置を有するセルをネットワークで接続したマルチプロセッサシステムにおける一貫性制御方法であって、
前記一貫性制御装置が、アクセス要求と投機アクセス要求を発行するステップと、
各セルの前記一貫性制御装置からアクセス要求を受けるステップと、
各セルの前記一貫性制御装置から投機アクセス要求を受けるステップを有し、
前記要求ステップはさらに、要求されたデータを保持している前記セルを予測し、予測に基づく処理を行うかどうかを判定するステップを有することを特徴とするマルチプロセッサシステムにおける一貫性制御方法。
【請求項１５】
前記一貫性制御装置が、
投機アクセス要求を受けて、投機アクセス応答を発行し、
各セルの前記一貫性制御装置から投機アクセス応答を受けるステップを実行することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項１６】
前記一貫性制御装置が、
アクセス要求を受けて一貫性要求を発行し、
各セルの前記一貫性制御装置から一貫性要求を受けるステップを実行することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項１７】
前記一貫性制御装置が、
アクセス要求を受けて一時応答を発行し、
各セルの前記一貫性制御装置から一時応答を受けるステップを実行することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項１８】
前記一貫性制御装置が、
投機アクセス要求を受けて、投機一貫性応答を発行し、
各セルの前記一貫性制御装置から投機一貫性応答を受けるステップを実行することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項１９】
前記一貫性制御装置が、
投機一貫性応答を受けた時点で該当するアクセス要求を受け取っていない場合、投機アクセス応答無効化要求を発行し、
各セルの前記一貫性制御装置から投機アクセス応答無効化要求を受けるステップを実行することを特徴とする請求項１８に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２０】
前記一貫性制御装置が、
各セルの前記一貫性制御装置から投機アクセス応答無効化要求を受けて、該当する投機アクセス応答を無効化するステップを実行することを特徴とする請求項１９に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２１】
前記一貫性制御装置は、要求フィルタテーブルを備え、
最近受けた要求でキャッシュに存在しないアドレスを前記要求フィルタテーブルに登録し、要求を受けたときに、前記要求フィルタテーブルに一致するエントリが存在する場合に、ＣＰＵに問い合わせを行わずに要求メッセージの処理を行うステップを有することを特徴とする請求項１６に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２２】
前記一貫性制御装置が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によって予測動作を行うかどうかを決定するステップを有することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２３】
前記一貫性制御装置が、乱数的にあるいは一定の規則性を持って予測動作を有無を示す値を発生するステップと、
発生する値によって予測動作を行うかどうかを決定するステップを有することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２４】
前記一貫性制御装置が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によってどのセルに対して投機アクセス要求を発行するかを決定するステップを有することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２５】
前記所有者決定手段が、乱数的にあるいは一定の規則性を持ってセルの番号を示す値を発生させるステップと、
発生する値によってどのセルに対して投機アクセス要求を発行するかを決定するステップを有することを特徴とする請求項１４に記載のマルチプロセッサシステムにおける一貫性制御方法。
【請求項２６】
メモリを共有する複数のＣＰＵと一貫性制御装置を有するセルをネットワークで接続したマルチプロセッサシステムの前記一貫性制御装置であって、
アクセス要求と投機アクセス要求を発行する要求手段と、
各セルの前記要求手段からアクセス要求を受けるホーム手段と、
各セルの前記要求手段から投機アクセス要求を受ける所有者手段を有し、
前記要求手段はさらに、要求されたデータを保持している前記セルを予測する所有者決定手段と、予測に基づく処理を行うかどうかを判定する判定手段を備える
ことを特徴とするマルチプロセッサシステムの一貫性制御装置。
【請求項２７】
前記所有者手段は、投機アクセス要求を受けて、投機アクセス応答を発行し、
前記要求手段は、各セルの所有者手段から投機アクセス応答を受ける機能を有することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項２８】
前記ホーム手段は、アクセス要求を受けて一貫性要求を発行し、
前記所有者手段は、各セルのホーム手段から一貫性要求を受ける機能を有することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項２９】
前記ホーム手段はさらに、アクセス要求を受けて一時応答を発行し、
前記要求手段はさらに、各セルのホーム手段から一時応答を受ける機能を有することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３０】
前記所有者手段はさらに、投機アクセス要求を受けて、投機一貫性応答を発行し、
前記ホーム手段はさらに、各セルの所有者手段から投機一貫性応答を受ける機能を有することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３１】
前記ホーム手段はさらに、投機一貫性応答を受けた時点でまだ該当するアクセス要求を受け取っていなかった場合、投機アクセス応答無効化要求を発行し、
前記要求手段はさらに、各セルのホーム手段から投機アクセス応答無効化要求を受ける機能を有することを特徴とする請求項３０に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３２】
前記要求手段はさらに、各セルのホーム手段から投機アクセス応答無効化要求を受けて、所有者手段からの該当する投機アクセス応答を無効化する機能を有することを特徴とする請求項３１に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３３】
前記一貫性制御装置は、要求フィルタテーブルを備え、
前記所有者手段が最近受けた要求でキャッシュに存在しないアドレスを前記要求フィルタテーブルに登録し、前記所有者手段が要求を受けたときに、前記要求フィルタテーブルに一致するエントリが存在する場合に、ＣＰＵに問い合わせを行わずに要求メッセージの処理を行うことを特徴とする請求項２８に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３４】
前記判定手段が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によって予測動作を行うかどうかを決定することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３５】
前記判定手段が、乱数的にあるいは一定の規則性を持って予測動作を有無を示す値を発生する判定値発生回路を有し、該判定値発生回路が出力する値によって予測動作を行うかどうかを決定することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３６】
前記所有者決定手段が、セル内のＣＰＵ番号をキーとするテーブルを備え、
前記テーブルに格納されているＣＰＵ番号の値によってどのセルに対して投機アクセス要求を発行するかを決定することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【請求項３７】
前記所有者決定手段が、乱数的にあるいは一定の規則性を持ってセルの番号を示す値を発生するセル番号発生回路を有し、
該セル番号発生回路が出力する値によってどのセルに対して投機アクセス要求を発行するかを決定することを特徴とする請求項２６に記載のマルチプロセッサシステムの一貫性制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリを共有する密結合型のマルチプロセッサシステムでの一貫性制御装置及び一貫性制御方法に関する。
【背景技術】
【０００２】
メモリを共有する密結合型のマルチプロセッサシステムにおける従来の一貫性制御方法に関する技術が非特許文献１に開示されている。以降、図を参照しながら当該従来技術を説明する。
【０００３】
一貫性制御が適用される従来のマルチプロセッサシステムの構成を図１に示す。複数のＣＰＵ１０１と一貫性制御装置１０２と共有メモリ１０３を含む複数のセル１０４がネットワーク１０５で接続される。各ＣＰＵ１０１は、キャッシュ１０６を保持し、キャッシュ１０６に共有メモリ１０３のデータを一時的に保持することで、データ・アクセスの高速化を実現している。
【０００４】
一方、複数のＣＰＵ１０１のキャッシュ１０６が共有メモリ１０３上の同じデータをアクセスしてそれぞれのキャッシュ１０６に保持するため、それらコピーの一貫性を維持する機能（一貫性制御）が必要となり、そのための手段として一貫性制御装置１０２を備えている。
【０００５】
図１３に、この一貫性制御を担う一貫性制御装置１０２の構成を示す。一貫性制御装置１０２は、要求手段１０７、ホーム手段１０８、所有者手段１０９を含んで構成される。データの一貫性制御は、複数のセル１０４の一貫性制御装置１０２のこれら要求手段１０７、ホーム手段１０８、所有者手段１０９間で要求や応答メッセージをやり取りすることによって実現される。
【０００６】
図１４と図１５に、ＣＰＵ１０１がキャッシュ１０６にないデータをアクセスした場合に発行するアクセス要求を一貫性制御装置１０２が受けた場合における、要求手段１０７、ホーム手段１０８、所有者手段１０９間でのメッセージの流れを示す。
【０００７】
以下においては、例として、セル１０４−ａにおいて、ＣＰＵ１０１がキャッシュ１０６にないデータをアクセスした場合に、セル１０４−ａの一貫性制御装置１０２からセル１０４−ｂの一貫性制御装置１０２にアクセス要求を発行した場合について説明する。
【０００８】
図１４の（ａ）と図１５の（ａ）は、アクセス要求されたセル１０４−ｂの共有メモリ１０３に最新のデータが存在する場合の動作を示している。この場合、まずセル１０４−ａの一貫性制御装置１０２の要求手段１０７は、セル１０４−ｂの一貫性制御装置１０２のホーム手段１０８にアクセス要求を発行する。セル１０４−ｂのホーム手段１０８は、ネットワーク１０５経由でセル１０４−ａの要求手段１０７からのアクセス要求を受けて共有メモリ１０３からデータを読み出し、要求元のセル１０４−ａの要求手段１０７に対してアクセス応答する。
【０００９】
図１４の（ｂ）と図１５の（ｂ）は、セル１０４−ａの一貫性制御装置１０２からセル１０４−ｂの一貫性制御装置１０２にアクセス要求した場合に、セル１０４−ｃ内ののキャッシュ１０６に最新のデータが存在する場合の動作を示している。セル１０４−ａの一貫性制御装置１０２の要求手段１０７は、セル１０４−ｂの一貫性制御装置１０２のホーム手段１０８にアクセス要求を発行する。セル１０４−ｂのホーム手段１０８は、ネットワーク１０５経由でアクセス要求を受け、キャッシュ１０６内に最新のデータのコピーを保持するＣＰＵ１０１を含むセル１０４−ｃの所有者手段１０９に一貫性要求を発行する。
【００１０】
ネットワーク１０５経由で一貫性要求を受けたセル１０４−ｃの所有者手段１０９は、該ＣＰＵ１０１のキャッシュ１０６からデータを読み出し、セル１０４−ａの要求手段１０７に対してアクセス応答を、セル１０４−ｂのホーム手段１０８に対して一貫性応答を行う。
【００１１】
一般に、図１４の（ｂ）、図１５の（ｂ）のようなケースは、最新のデータを保持するキャッシュ１０６から要求を出したＣＰＵ１０１のキャッシュ１０６にデータが転送されることから、キャッシュ間転送のケースと呼ばれる。
【００１２】
このキャッシュ間転送のケースにおける性能を改善するための従来技術が、例えば非特許文献２に開示されている。以降、図を参照しながら当該従来技術を説明する。
【００１３】
図１６に、要求手段１０７の構成を示す。要求手段１０７は、所有者決定手段１１０と判定手段１１１を含む。
【００１４】
所有者決定手段１１０は、ＣＰＵ１０１からのアクセス要求を入力とし、どのセル１０４が最新のデータを保持しているかを予測して出力する。
【００１５】
判定手段１１１はＣＰＵ１０１からのアクセス要求を入力とし、予測に基づく処理を行うかどうかを判定し、その判定結果を出力する。
【００１６】
判定手段１１１が予測に基づく動作を指示しなかった場合においては、図１４、図１５に示した従来技術の動作と同じ動作を行う。
【００１７】
判定手段１１１が予測に基づく動作を指示した場合、図１７に示す動作を行う。
【００１８】
ここでは、セル１０４−ａのＣＰＵ１０１がキャッシュ１０６にないデータをアクセスした場合に、予測したセル１０４−ｂにアクセス要求を行う場合を想定して説明する。
【００１９】
図１７の（ａ）は予測したセル１０４−ｂがデータを保持していた場合の動作である。セル１０４−ａの要求手段１０７は、所有者決定手段１１０が予測したセル１０４−ｂの所有者手段１０９に投機アクセス要求を発行する。該所有者手段１０９は投機アクセス要求を受けて、キャッシュ１０６からデータを読み出し、セル１０４−ａの要求手段１０７にアクセス応答を、ホーム手段１０８に一貫性応答を行う。
【００２０】
一方、図１７の（ｂ）は予測したセル１０４−ｂがデータを保持していなかった場合の動作である。セル１０４−ａの要求手段１０７は、所有者決定手段１１０が予測したセル１０４−ｂの所有者手段１０９に投機アクセス要求を発行する。
【００２１】
セル１０４−ｂの該所有者手段１０９は、投機アクセス要求を受けるが、データを保持していないので投機失敗応答を要求元のセル１０４−ａのホーム手段１０８に発行する。セル１０４−ａのホーム手段１０８は投機失敗応答を受けて、データを保持するセル（例えば、セル１０４−ｃ）の所有者手段１０９に一貫性要求を発行する。一貫性要求を受けたセル（セル１０４−ｃ）の所有者手段１０９は、キャッシュ１０６からデータを読み出し、要求元のセル１０４−ａの要求手段１０７に対してアクセス応答を、ホーム手段１０８に対して一貫性応答を行う。
【００２２】
また、従来の判定手段１１１及び所有者決定手段１１０の構成を図１８及び図１９に示す。
【００２３】
判定手段１１１は、プログラムカウンタ（ＰＣ）１１３をキーとする判定情報テーブル１１４を保持し、ＣＰＵ１０１がアクセス要求を発行したときのＰＣ１１３の値から判定情報テーブル１１４を検索し、その内容を判定回路１１５で受けて、予測に基づく動作を行うかどうかを決定する。
【００２４】
所有者決定手段１１０は、ＰＣ１１３とアクセス要求のアドレス１１６からキー作成回路１１７にてキーを作成し、そのキーをインデックスとする予測セル情報テーブル１１８を保持する。要求発行回路１１９は、予測したセルの所有者手段１０９に投機アクセス要求を発行する。
【非特許文献１】James Laudon and Daniel Leonski, ”The SGI Origin: A ccNUMA Highly Scalable Server”, Proceedings of the 24th annual international symposium on Computer architecture, 1997, pp241-251
【非特許文献２】Manuel E. Acacio, Jose Gonzalez, Jose M. Garcia and Jose Duato, ”Owner Prediction for Accelerating Cache-to-Cache Transfer Misses in a cc-NUMA Architecture”, Proceedings of SC2002
【発明の開示】
【発明が解決しようとする課題】
【００２５】
上述した従来の技術には、以下に述べるような問題点があった。
【００２６】
第１の問題点は、キャッシュミス時に十分なメモリアクセス性能が得られないことである。
【００２７】
その理由は、前記非特許文献１で開示されている技術では、キャッシュ間転送時のメモリアクセスレイテンシが大きいからである。また前記非特許文献２で開示されている技術では、予測によりキャッシュ間転送時のメモリアクセスレイテンシの改善を図っており、予測が当たった場合は確かに性能を改善しているが、予測が外れた場合前期非特許文献１よりもさらに悪化しており、全体としては性能改善がうまく図れていないからである。
【００２８】
第２の問題点は、非特許文献２の技術を用いた場合、判定手段や所有者決定手段のために多くのハードウェア量を必要とすることである。
【００２９】
その理由は、以下のとおりである。判定情報テーブル１１４及び予測セル情報テーブル１１８には、以前そのＰＣ１１３及びアドレス１１６で（実際には同じキーを持つ複数の組）行われたアクセスの履歴情報が保持される。この履歴情報を正確なものとするには、判定情報テーブル１１４については、ＣＰＵ１０１が出力するアクセス要求で異なるＰＣ１１３の値を持つものは、判定情報テーブル１１４の同一のエントリをなるべく利用しないようにする必要がある。予測セル情報テーブル１１８についても、ＣＰＵ１０１が出力するアクセス要求で異なるＰＣ１１３及びアドレス１１６の値を持つものは、予測セル情報テーブル１１８の同一のエントリをなるべく利用しないようにする必要がある。そのため、開示されている非特許文献２では、前者を２Ｋエントリ、後者を１６Ｋエントリのメモリで構成していた。
【００３０】
本発明の第１の目的は、キャッシュ間転送が行われるケースのメモリアクセス性能を向上させることができるマルチプロセッサシステム、マルチプロセッサシステムにおける一貫性制御装置及び一貫性制御方法を提供することにある。
【００３１】
本発明の第２の目的は、一貫性制御のために必要なハードウェア量をより削減することができるマルチプロセッサシステム、マルチプロセッサシステムにおける一貫性制御装置及び一貫性制御方法を提供することにある。
【課題を解決するための手段】
【００３２】
本発明は、メモリを共有する複数のＣＰＵと一貫性制御装置を有するセルをネットワークで接続したマルチプロセッサシステムであって、一貫性制御装置が、アクセス要求と投機アクセス要求を発行する要求手段と、各セルの前記要求手段からアクセス要求を受けるホーム手段と、各セルの前記要求手段から投機アクセス要求を受ける所有者手段を有し、前記要求手段はさらに、要求されたデータを保持している前記セルを予測する所有者決定手段と、予測に基づく処理を行うかどうかを判定する判定手段を備える。
【発明の効果】
【００３３】
本発明の第１の効果は、キャッシュ間転送が行われるケースのメモリアクセス性能を向上させることが可能となる。
【００３４】
その理由は、データを所有するセルの予測を行い、ホーム手段と所有者手段にアクセス要求と投機アクセス要求を発行することにより、予測が当たった場合のメモリアクセス性能を改善でき、外れた場合でも従来と同じレイテンシを実現することができるからである。
【００３５】
本発明の第２の効果は、一貫性制御のための要求手段に必要なハードウェア量を削減することができる点にある。
【００３６】
その理由は、判定手段で保持する判定情報テーブルを、セル内のＣＰＵ番号をキーとするテーブルとして構成するからである。また、所有者決定手段で保持する所有者セル情報テーブルを、セル内のＣＰＵ番号をキーとするテーブルとして構成するからである。
【００３７】
さらに、判定手段で判定情報テーブルの代わりに判定値発生回路を保持し、テーブルを不要とし、所有者決定手段で所有者セル情報テーブルの代わりにセル番号発生回路を保持する構成とすることにより、一貫性制御のための要求手段に必要なハードウェア量をさらに削減することが可能となる。
【実施例１】
【００３８】
次に、本発明の好適な実施例について図面を参照して詳細に説明する。
【００３９】
本発明の第１の実施例によるマルチプロセッサシステムの構成は、図１に示した従来の構成と同じであり、複数のＣＰＵ１０１と一貫性制御装置１０２と共有メモリ１０３を含む複数のセル１０４（１０４−ａ〜１０４−ｄ）がネットワーク１０５で接続される。各ＣＰＵ１０１はキャッシュ１０６を備え、キャッシュ１０６に共有メモリ１０３のデータを一時的に保持することで、データ・アクセスの高速化を実現している。
【００４０】
ここで、ネットワーク１０５は、１以上のチャネルを有し、チャネルは送信元セル１０４と送信先セル１０４の組が一致するメッセージ間の順序のみを保障するものであればよい。また、ネットワーク１０５としては、バス等の全メッセージ間の順序が保障されたネットワークにも適用可能である。
【００４１】
第１の実施例による一貫性制御装置１０２の構成を図３に示す。一貫性制御装置１０２は、要求手段１０７、ホーム手段１０８、所有者手段１０９と要求フィルタテーブル１１２とを有する。
【００４２】
データの一貫性制御は、複数のセル１０４（１０４−ａ〜１０４−ｄ）のこれら要求手段１０７、ホーム手段１０８、所有者手段１０９間で要求や応答メッセージをやり取りすることによって実現される。
【００４３】
要求フィルタテーブル１１２は、ＣＰＵ１０１に問い合わせを行うことなしに、要求手段１０７から受けた要求メッセージの処理を所有者手段１０９が行えるようにするために用いられる。
【００４４】
要求手段１０７の構成は、従来の技術で説明した図１６に示す通りである。この要求手段１０７は、所有者決定手段１１０と判定手段１１１を含む。
【００４５】
所有者決定手段１１０は、ＣＰＵ１０１からのアクセス要求を入力とし、何れのセル１０４（セル１０４−ａ〜１０４−ｄ）が最新のデータを保持しているか（最新のデータを所有するセル）を予測して出力する。
【００４６】
判定手段１１１は、ＣＰＵ１０１からのアクセス要求を入力とし、所有者決定手段１１０による予測に基づく処理を行うかどうかを判定し、その判定結果を出力する。
【００４７】
図４及び図５は、本実施例による上記所有者決定手段１１０及び判定手段１１１の構成を示す図である。
【００４８】
判定手段１１１は、セル（セル１０４−ａ〜１０４−ｄ）内に存在するＣＰＵ１０１を識別するセル内ＣＰＵ番号１２０をキーとする判定情報テーブル１２１と判定回路１２２を備える。
【００４９】
所有者決定手段１１０も同様に、セル内ＣＰＵ番号１２０をキーとする予測セル情報テーブル１２３と要求発行回路１２４を備える。
【００５０】
本発明の第１の実施例によるマルチプロセッサシステムの要求手段１０７、ホーム手段１０８、所有者手段１０９の動作について図２を用いて説明する。
【００５１】
図２の（ａ）は予測したセル１０４がデータを保持していた場合の動作である。ここでは、例として、セル１０４−ａから予測したセル１０４−ｂに対してアクセス要求を発行する場合について説明する。
【００５２】
セル１０４−ａの要求手段１０７は、ホーム手段１０８にアクセス要求を発行し、所有者決定手段１１０が予測したセル１０４−ｂの所有者手段１０９に対して投機アクセス要求を発行する。
【００５３】
予測したセル１０４−ｂの所有者手段１０９は、投機アクセス要求を受けて、キャッシュ１０６からデータを読み出し、セル１０４−ａの要求手段１０７に対して投機アクセス応答を、ホーム手段１０８に対して投機一貫性応答を行う。
【００５４】
また、アクセス要求を受けたセル１０４−ａのホーム手段１０８は、一時応答を要求手段１０７に、一貫性要求を所有者手段１０９に発行する。セル１０４−ａの要求手段１０７は、一時応答と投機アクセス応答の両方を受けてＣＰＵ１０１にデータを渡す。
【００５５】
図２の（ｂ）は予測したセル１０４がデータを保持していなかった場合の動作である。
【００５６】
セル１０４−ａの要求手段１０７は、ホーム手段１０８にアクセス要求を、所有者決定手段１１０が予測したセル１０４−ｂの所有者手段１０９に対して投機アクセス要求を発行する。
【００５７】
該所有者手段１０９は投機アクセス要求を受けるが、データを保持していないので投機アクセス要求を破棄する。アクセス要求を受けたホーム手段１０８は、データを保持するセル１０４（例えば、セル１０４−ｃ）の所有者手段１０９に一貫性要求を、セル１０４−ａの要求手段１０７に一時応答を発行する。
【００５８】
一貫性要求を受けたセル１０４−ｃの所有者手段１０９は、キャッシュ１０６からデータを読み出し、セル１０４−ａの要求手段１０７にアクセス応答を、ホーム手段１０８に一貫性応答を行う。セル１０４−ａの要求手段１０７は、アクセス応答を受けてＣＰＵ１０１にデータを渡す。
【００５９】
また、図２の（ｃ）は、（ａ）に示すケースでセル１０４−ａのホーム手段１０８がセル１０４−ｂの所有者手段１０９からの投機一貫性応答を受けた時点でまだ要求手段１０７からのアクセス要求を受け取っていなかった場合の動作である。
【００６０】
セル１０４−ａのホーム手段１０８は、投機一貫性応答を受けて要求手段１０７に投機アクセス応答無効化要求を発行する。
【００６１】
投機アクセス応答無効化要求を受けたセル１０４−ａの要求手段１０７は、セル１０４−ｂの所有者手段１０９から受け取るあるいは受け取った投機アクセス応答を破棄する。これにより、複数のセル１０４からのアクセスが競合した場合でもデータの一貫性を維持することができる。
【００６２】
上述した本実施例による方式では、予測したセル（上記の例ではセル１０４−ｂ）の所有者手段１０９は、要求手段１０７からの投機アクセス要求とホーム手段１０８からの一貫性要求の両方を受け取って処理する必要がある。
【００６３】
図６は、所有者手段１０９における上記処理を効率化するために設けた要求フィルタテーブル１１２による動作を説明する図である。以降順に動作を説明する。
【００６４】
所有者手段１０９は、アドレスＡを指定する投機アクセス要求（Ａ）を受けると、要求フィルタテーブル１１２を検査する。図６の（ａ）に示すように、該当するアドレスに一致するエントリが存在しない場合、ＣＰＵ１０１に対して問い合わせを行い、その応答にしたがって処理を行う。ここで、該投機アクセス要求によってアドレスＡのデータが無効化されたとする。
【００６５】
アドレスＡが無効化された場合、図６の（ｂ）に示すように、要求フィルタテーブル１１２にアドレスＡが登録される。アドレス登録時に空きエントリがなく、置き換えの必要が生じた場合、あるエントリが選択されてそのエントリにアドレスＡが上書きされる。上書きされる前に登録されていたアドレスに関して、ＣＰＵ１０１への問い合わせやホーム手段１０８へのメッセージ転送が行われることはない。
【００６６】
次に、所有者手段１０９は、アドレスＡの一貫性要求を受けると、要求フィルタテーブル１１２を検査する。図６の（ｂ）に示すように、該当するアドレスに一致するエントリが存在するので、ＣＰＵ１０１に対して問い合わせを行わず、キャッシュ１０６にはデータが存在しないものとして処理を行う。
【００６７】
次に、要求手段１０７がアドレスＡのアクセス要求をＣＰＵ１０１から受けると、要求フィルタテーブル１１２を検査する。図６の（ｂ）に示すように、該当するアドレスに一致するエントリが存在するので、図６の（ｃ）に示すように該エントリのデータを無効化する。
【００６８】
ここで、要求フィルタテーブル１１２のエントリの無効化は、要求手段１０７がアクセス要求を受け取ったときに加えて、所有者手段１０９が要求フィルタテーブル１１２を検査してアドレスが一致するエントリが存在した時に行うようにしても良い。
【００６９】
最後に、判定手段１１１及び所有者決定手段１１０の動作について説明する。図７に示すプログラムは、プログラムのある箇所でアドレスＡに対する書き込みを行い、続いてアドレスＢに対する書き込み、最後にアドレスＣに対する書き込みを行うことを示すものである。
【００７０】
最初に、図８に示すように、セル１０４−ｊにおいて図７に示すプログラムが実行され、セル１０４−ｊのキャッシュ１０６にアドレスＡ，Ｂ，Ｃのデータが保持されているものとする（図１の構成では、セル１０４−ｉと１０４−ｊは、セル１０４−ａ、１０４−ｂ、１０４−ｃ、１０４−ｄの何れか）。次に、同じプログラムがセル１０４−ｉのＣＰＵ１０１で実行されたものとする。
【００７１】
図９は、セル１０４内に４個（０番から３番）のＣＰＵ１０１が存在し、上記プログラムが０番のＣＰＵ１０１で実行された場合の、判定情報テーブル１２１及び、所有者セル情報テーブル１２３の状態の遷移を示したものである。
【００７２】
両テーブル１２１、１２３とも４エントリのテーブルで構成される。また、判定情報テーブル１２１には「０」あるいは「１」が格納され、「０」は予測動作をしない、「１」は予測動作をすることを示すものとする。判定情報テーブル１２１の各エントリは、セル内のＣＰＵ１０１の番号に対応している。また、所有者セル情報テーブル１２３にはセル１０４を識別する番号が格納されるものとする。
【００７３】
以降、このケースのセル１０４−ｉにおける判定手段１１１及び所有者決定手段１１０の動作を順に説明する。
【００７４】
初期状態では、判定情報テーブル１２１には全て「０」（予測動作をしないことを示す値）が格納されている。０番目のＣＰＵ１０１が図７に示すプログラムを実行し、アドレスＡに対する書き込みを行ったとする。
【００７５】
この書き込みによりアクセス要求が該セル１０４−ｉの要求手段１０７に対して発行される。セル１０４−ｉの要求手段１０７は０番のＣＰＵ１０１からアドレスＡのアクセス要求を受けて、判定手段１１１に対してセル内ＣＰＵ番号１２０として「０」を出力する。
【００７６】
判定手段１１１は、セル内ＣＰＵ番号１２０である「０」を受けて判定情報テーブル１２１の０番のＣＰＵに対応する０番目のエントリの値「０」を読み出す（図９の（ａ）参照）。この読み出された内容「０」は判定回路１２２に渡され、判定回路１２２でその値が判別されて予測動作なしという判定結果が要求手段１０７に渡される。セル１０４−ｉの要求手段１０７は、非特許文献１で示した従来技術と同様にアクセス要求の処理を行うことにより、セル１０４−ｊからデータを受け取る。
【００７７】
セル１０４−ｉの要求手段１０７は、データを受け取ると、該アクセスがキャッシュ間転送を行ったケースであるので、判定情報テーブル１２１の０番のエントリを値「１」（予測動作をすることを示す内容）に、所有者セル情報テーブル１２３の０番エントリの内容を「ｊ」に更新する（図９の（ｂ）参照）。
【００７８】
次に、アドレスＢに対する書き込みが行われる。この書き込みによりアクセス要求が要求手段１０７に対して発行される。
【００７９】
セル１０４−ｉの要求手段１０７は、０番のＣＰＵ１０１からアドレスＢのアクセス要求を受けて、判定手段１１１にセル内ＣＰＵ番号１２０として「０」を出力する。判定手段１１１は、セル内ＣＰＵ番号１２０の「０」を受けて判定情報テーブル１２１の０番目のエントリの内容「１」を読み出す（図９の（ｂ）参照）。
【００８０】
この値「１」が判定回路１２２に渡されて判別されることにより、予測動作ありという判定結果が要求手段１０７に渡される。要求手段１０７は、次にセル内ＣＰＵ番号１２０である値「０」を所有者決定手段１１０に出力する。
【００８１】
所有者決定手段１１０は、セル内ＣＰＵ番号１２０の値「０」を受けて所有者セル情報テーブル１２３の０番エントリの内容「ｊ」を読み出す（図９の（ｂ）参照）。この予想するセルの番号を示す情報「ｊ」は要求発行回路１２４に渡され、要求発行回路１２４はセル１０４−ｊに対して投機アクセス要求を発行する旨を要求手段１０７に伝える。
【００８２】
要求手段１０７は、この通知を受けて図２に示す動作を行い、所有者決定手段１１０から通知されたセル１０４−ｊの所有者手段１０９に対して投機アクセス要求を発行する。セル１０４−ｊの所有者手段１０９は、投機アクセス要求を受け、キャッシュ１０６からデータを読み出し、要求元のセル１０４−ｉの要求手段１０７に対してデータを投機アクセス応答により渡す。
【００８３】
要求手段１０７は、データを受け取ると、該アクセスがキャッシュ間転送を行ったケースであるので、判定情報テーブル１２１の０番エントリの内容を「１」に、所有者セル情報テーブル１２３の０番目のエントリの内容を「ｊ」に更新する。
【００８４】
次に、アドレスＣに対する書き込みが行われる。この書き込みによるアクセス要求もアドレスＢの上記処理と同様の処理が行われる。
【００８５】
このように、始めのアドレスＡに関しては予測動作が行われないものの、続くアドレスＢ及びＣに関しては予測動作が行われると共に、予測した内容（予想したセル）が的中した結果となる。
【００８６】
一方、従来のようにＰＣ（プログラムカウンタ）及びアドレスから作成したキーによるテーブルを用いる方式では、上記の場合、アドレスＡ、Ｂ、Ｃについてそれぞれ異なるキーが作成される可能性が高く、全く予測動作が行われない場合も起こる。
【００８７】
上記した第１の実施例によれば、データを所有するセルの予測を行い、ホーム手段と所有者手段にアクセス要求と投機アクセス要求を発行することにより、予測が当たった場合のメモリアクセス性能を改善し、外れた場合でも従来と同じレイテンシを実現することができるようになる。
【００８８】
なお、投機アクセス要求は、複数の所有者手段１０９に対して発行しても良い。また、要求手段１０７は、複数の判定手段１１１と所有者決定手段１１０を有しても良い。
【００８９】
また、上記実施例の構成では、要求手段１０７が判定手段１１１と所有者決定手段１１０を備える場合を示したが、ＣＰＵ１０１が判定手段１１１と所有者決定手段１１０を備え、アクセス要求と投機アクセス要求を要求手段１０７に発行し、それを受けた要求手段は、アクセス要求をホーム手段１０８に、投機アクセス要求を指定されたセルの所有者手段１０９に発行するようにしてもよい。ただし、これはＣＰＵ１０１に一貫性制御装置１０２の機能の一部を割り振っただけであり、マルチプロセッサシステムの各セルが有する機能そのものについて変更はない。
【００９０】
図２の（ｂ）のケースで、投機アクセス要求を受けた所有者手段１０９は、要求手段１０７に対して投機アクセス失敗応答を行っても良い。
【実施例２】
【００９１】
なお、第２の実施例としては、判定手段１１１について、図１０に示すように、値「０」あるいは「１」をランダムにあるいは一定の規則性を持って出力する判定値発生回路１２５を有し、予測動作を行うかどうかをランダムに、あるいは規則的に決定するようにしてもよい。
【実施例３】
【００９２】
同様に、第３の実施例としては、所有者決定手段１１０は、図１１に示すように、セル番号をランダムにあるいは一定の規則を持って出力するセル番号発生回路１２６を有し、ランダムにあるいは規則性を持って所有者となるセルを決定しても良い。
【００９３】
このセル番号発生回路１２６では、ランダムにセルの番号を出力してもよいし、特定のセルどうしの番号を予め組み合わせ、あるセルからの要求に対してどのセル番号を出力するかを決めてあってもよいし、また、一定の規則で順番にセル番号を出力するものであってもよい。
【００９４】
図１０、図１１に示すように判定手段１１１と所有者決定手段１１０を構成することで、上記説明した実施例のようなセル内ＣＰＵ番号１２０をキーとして判定情報テーブル１２１及び予測セル情報テーブル１２３が必要なくなり、ハードウェア量を極力少なくすることができる。
【００９５】
特に、マルチプロセッサシステムを構成するセル数が少ない場合には、上記のような判定値発生回路１２５やセル番号発生回路１２６を備える構成でも、メモリアクセス性能の向上が十分に達成される。
【００９６】
また、図１２に示すように、上記第１の実施例に示した所有者決定手段１１０が、第３の実施例である図１１に示したセル番号発生回路１２６を備える構成とすることもできる。この場合、所有者決定手段１１０が複数のセル番号を出力し、複数の所有者手段１０９に対して投機アクセス要求を発行する。
【００９７】
判定手段１１１について、第１の実施例と図１０の第２の実施例の構成を組み合わせることも可能である。
【００９８】
さらに、判定手段１１１と所有者決定手段１１０の他の実施例としては、図１８と図１９に示した従来の構成と本実施例の構成を組み合わせて構成することも可能である。このように組み合わせることで、マルチプロセッサシステムの内容に応じてより効果的な組み合わせを選択することができる。
【００９９】
以上、好ましい実施の形態をあげて本発明を説明したが、本発明は必ずしも上記実施の形態に限定されるものではない。本発明の要旨を逸脱しない範囲内において種々の変形が可能であることは言うまでもない。
【０１００】
なお、一貫性制御装置１０２の各機能は、例えばコンピュータ装置に上述した機能を持たせることによって実現することができる。具体的には、ＣＰＵ１０１で上記一貫性制御装置の機能をソフトウェア的に達成するプログラムを実行することで実現してもよい。
【０１０１】
一貫性制御装置１０２の機能をソフトウェア的に実現する場合には、プログラム制御可能なコンピュータ処理装置（ＣＰＵ）上で、各一貫性制御装置の機能を実現するプログラムをロードして実行する。このプログラムは、磁気ディスク、半導体メモリその他の記録媒体に格納され、その記録媒体からコンピュータ処理装置にロードされ、ＣＰＵの動作を制御することにより、各装置としての固有の機能を達成する。
【産業上の利用可能性】
【０１０２】
本発明は、ハードウェア制御の共有メモリ型マルチプロセッサシステムのみならず、ソフトウェア制御の共有メモリ型マルチプロセッサシステムといった用途にも適用することができる。また、大規模ディスクアレイ装置のディスクキャッシュの一貫性制御にも適用することが出来る。
【図面の簡単な説明】
【０１０３】
【図１】本発明及び従来のマルチプロセッサシステムの構成を示す図である。
【図２】本発明の第１の実施例による一貫性制御装置の動作を示す図である。
【図３】本発明の第１の実施例による一貫性制御装置の構成を示す図である。
【図４】本発明の第１の実施例による判定手段の構成を示す図である。
【図５】本発明の第１の実施例による所有者決定手段の構成を示す図である。
【図６】本発明の第１の実施例による要求フィルタテーブルの動作を示す図である。
【図７】本発明の判定手段及び所有者決定手段の動作説明に用いるプログラム例を示す図である。
【図８】本発明の判定手段及び所有者決定手段の動作説明に用いるマルチプロセッサシステムの状態を示す図である。
【図９】本発明の判定手段及び所有者決定手段に含まれるテーブルの状態を示す図である。
【図１０】本発明の第２の実施例による判定手段の構成を示す図である。
【図１１】本発明の第３の実施例による所有者決定手段の構成を示す図である。
【図１２】本発明のさらに他の実施例による所有者決定手段の構成を示す図である。
【図１３】従来の一貫性制御装置の構成を示す図である。
【図１４】従来の一貫性制御装置の動作を示す図である。
【図１５】従来の一貫性制御装置の動作を説明するための図である。
【図１６】本発明及び従来の要求手段の構成を示す図である。
【図１７】従来の一貫性制御装置の動作を示す図である。
【図１８】従来の判定手段の構成を示す図である。
【図１９】従来の所有者決定手段の構成を示す図である。
【符号の説明】
【０１０４】
１０１：ＣＰＵ
１０２：一貫性制御装置
１０３：共有メモリ
１０４−ａ〜１０４−ｄ：セル
１０５：ネットワーク
１０６：キャッシュ
１０７：要求手段
１０８：ホーム手段
１０９：所有者手段
１１０：所有者決定手段
１１１：判定手段
１１２：要求フィルタテーブル
１１３：ＰＣ（プログラムカウンタ）
１１４：判定情報テーブル
１１５：判定回路
１１６：アドレス
１１７：キー作成回路
１１８：予測セル情報テーブル
１１９：要求発行回路
１２０：セル内ＣＰＵ番号
１２１：判定情報テーブル
１２２：判定回路
１２３：予測セル情報テーブル
１２４：要求発行回路
１２５：判定値発生回路
１２６：セル番号発生回路
【図１】
2005189928.tif 000003
【図２】
2005189928.tif 000004
【図３】
2005189928.tif 000005
【図４】
2005189928.tif 000006
【図５】
2005189928.tif 000007
【図６】
2005189928.tif 000008
【図７】
2005189928.tif 000009
【図８】
2005189928.tif 000010
【図９】
2005189928.tif 000011
【図１０】
2005189928.tif 000012
【図１１】
2005189928.tif 000013
【図１２】
2005189928.tif 000014
【図１３】
2005189928.tif 000015
【図１４】
2005189928.tif 000016
【図１５】
2005189928.tif 000017
【図１６】
2005189928.tif 000018
【図１７】
2005189928.tif 000019
【図１８】
2005189928.tif 000020
【図１９】
2005189928.tif 000021