JP4572169B2 - マルチプロセッサシステム及びその動作方法 - Google Patents

Description

本発明は、複数のセルにより構成される分散共有メモリ型のマルチプロセッサシステムに関する。特に、本発明は、複数のセルを備える分散共有メモリ型マルチプロセッサシステムにおけるコヒーレンシ技術に関する。

コンピュータシステムの分野において、多数のプロセッサによって構成される「マルチプロセッサシステム（Multiprocessor System）」が従来知られている。マルチプロセッサシステムの中でも、複数のセル（あるいは複数のノード）によって構成され、その複数のセル間がバスやスイッチにより結合されたものが知られている。複数のセルはそれぞれ独立にプロセッサとメインメモリを有し、全てのメインメモリによって論理的に「共有メモリ」が構成される（例えば、特許文献１、特許文献２、特許文献３、特許文献４、及び特許文献５を参照）。メモリが分散的に配置され、且つ複数のプロセッサにより共有されるため、そのようなマルチプロセッサシステムは、「分散共有メモリ型（DSM: Distributed Shared Memory）マルチプロセッサシステム」や「分散共有メモリ型アーキテクチャ」と呼ばれることもある。

図１は、分散共有メモリ型マルチプロセッサシステム１の構成を示すブロック図である。図１に示されたマルチプロセッサシステム１は、複数のセルＣ１〜Ｃｎ（ｎはセル数を示す整数）と、それら複数のセルＣ１〜Ｃｎ間を互いに結合するクロスバースイッチ９から構成されている。複数のセルＣ１〜Ｃｎは同一の機能を有している。各々のセルＣｊ（ｊは１以上ｎ以下の整数）は、少なくとも１つのＣＰＵ（マイクロプロセッサ）２−ｊ−１〜２−ｊ−ｍ（ｍは各セル内のＣＰＵ数を示す整数）と、メインメモリ（ローカルメモリ）５−ｊを備えている。それらＣＰＵ２の各々は、少なくとも１つのキャッシュメモリ（ストアインキャッシュ）７を搭載している。分散的に設けられたメインメモリ５−１〜５−ｎの全てによって共有メモリが構成され、その共有メモリは全てのＣＰＵ２によって参照される。

このような分散共有メモリ型マルチプロセッサシステム１においては、ＣＰＵ２のそれぞれがキャッシュ７を駆使しながら、メインメモリ５−１〜５−ｎに格納されたデータにアクセスし、またその更新を行う。データ更新にライトバック（Write Back）方式が用いられる場合、更新されたデータがキャッシュ７に滞留し、メインメモリ５−ｊには最新のデータが存在しない可能性もある。この時、複数のＣＰＵ２が同一の記憶領域を参照／更新しようとすると、データの不整合により正しい結果が得られなくなる。従って、マルチプロセッサシステムにおいては、各ＣＰＵ２が最新のデータにアクセスできるように、データの一貫性（「キャッシュコヒーレンシ：Cache Coherency」と参照される）を保障ことが重要である。ここで、各セルＣｊ内のキャッシュ７間のコヒーレンシを保つだけでなく、複数のセルＣ１〜Ｃｎ間のコヒーレンシも保つ必要があることに留意されるべきである。

キャッシュコヒーレンシの方式としては、「ディレクトリ方式（Directory-based Cache Coherency Protocol）」と「スヌープ方式（Snooping Cache Coherency Protocol）」が知られている。

ディレクトリ方式によれば、メインメモリに格納されたデータに関するキャッシングの状態を管理するテーブル（ディレクトリ）が設けられる。あるＣＰＵがあるデータにアクセスする際、まず、そのディレクトリに格納されたキャッシング状態に関する情報が調べられる。所望の最新データがメインメモリではなく、あるキャッシュにのみ存在することが判明した場合、ＣＰＵはそのキャッシュに対してそのデータのアクセスを行う。

一方、スヌープ方式によれば、あるＣＰＵがあるアクセスアドレスのデータにアクセスする際、全てのキャッシュは、そのアクセスアドレスのデータのコピーを保有しているか否かを調べる。そして、各キャッシュは、必要なときに最新のデータを取得できるように自身の状態（キャッシュステータス）を変更する。例えば、ＭＥＳＩプロトコルによれば、「Ｉ（Ｉｎｖａｌｉｄ；無効）」、「Ｓ（Ｓｈａｒｅｄ；最新データがメインメモリと複数のキャッシュに存在する）」、「Ｅ（Ｅｘｃｌｕｓｉｖｅ；最新データがメインメモリと自キャッシュに存在する）」、「Ｍ（Ｍｏｄｉｆｉｅｄ）；最新データが自キャッシュにのみ存在する」の４つのキャッシュステータスが提供される。

図１に示されたセルＣ１〜Ｃｎのそれぞれには、上述のキャッシュコヒーレンシを実現するために、キャッシュコヒーレンシ回路３−１〜３−ｎ及びディレクトリ４−１〜４−ｎが設けられている。ディレクトリ４−ｊは、ＤＲＡＭ等により実現される記憶領域であり、その中には、自セルＣｊのメインメモリ５−ｊに格納されたデータに関するキャッシングの状態を管理するための情報が格納される。より具体的には、ディレクトリ４−ｊには、自セルＣｊのメインメモリ５−ｊに格納されたデータに関して最新データをキャッシングしているセルを示すテーブルが格納される。最新データをキャッシングしているセルは、自セルである場合もあるし、他のセルである場合もある。キャッシュコヒーレンシ回路３は、ディレクトリ４を参照することにより、セルＣ１〜Ｃｎ間のコヒーレンシを保障するように構成されている。尚、各セル内のキャッシュコヒーレンシは、例えばスヌープ方式により実現される。

特開２０００−６７０２４号公報 特開２０００−２５９５９６号公報 特開平６−１１０８４４号公報 特開平１１−２１９３４３号公報 特開２００３−２１６５９７号公報

あるデータに対するリードリクエストを発行する発行元であるＣＰＵ２を搭載するセルは、以下「リクエストセルＣＲ」と参照される。そのアクセス対象であるデータが格納されたメインメモリ５を搭載するセルは、以下「ホームセルＣＨ」と参照される。また、そのアクセス対象であるデータの最新版（最新データ）をキャッシングしているキャッシュ７を有するセルは、以下「オーナーセルＣＯ」と参照される。本願発明者は、ディレクトリ４を用いるマルチプロセッサシステム１において、それらリクエストセルＣＲ、ホームセルＣＨ、及びオーナーセルＣＯがそれぞれ異なる状態が発生することに着目した。

そのような状態における従来のマルチプロセッサシステムの動作例を、図２を参照して説明する。まず、リクエストセルＣＲのＣＰＵ２は、アクセス対象データが格納されたメインメモリ５を有するホームセルＣＨに、リードリクエストを発行する（ステップＳ１）。ホームセルＣＨは、リードリクエストに応答して、自身のディレクトリ４を検索（索引）する。ディレクトリ４に格納された情報より、ホームセルＣＨは、対象データの最新版がオーナーセルＣＯのキャッシュ７に格納されていることを知る。そこで、ホームセルＣＨは、オーナーセルＣＯにスヌープリクエストを発行する（ステップＳ２）。

オーナーセルＣＯは、スヌープリクエストに応答して、キャッシュ７から最新データを読み出す。そして、オーナーセルＣＯは、その最新データをホームセルＣＨのメインメモリ５に書き戻すために、ホームセルＣＨに対してライトバックを発行する（ステップＳ３）。オーナーセルＣＯがスヌープリクエストに応答して発行するライトバックは、以下、「リプライライトバック」と参照される。このリプライライトバックと同時に、オーナーセルＣＯは、読み出された最新データをリプライデータとしてリクエストセルＣＲに直接送信する（ステップＳ３’）。これにより、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰ（ステップＳ１，Ｓ２，Ｓ３’）で実現することができる（セル間のレイテンシを１ＨＯＰとする）。

リードリクエストを発行したリクエストセルＣＲのＣＰＵ２は、受け取ったリプライデータを自身のキャッシュ７に格納する。その後、そのキャッシュ７のリプライデータがリプレースされた場合などにおいて、リクエストセルＣＲからホームセルＣＨに対するライトバックが発生する可能性がある（ステップＳ３’’）。ＣＰＵ２がキャッシュ７のリプレース等により発行するライトバックは、以下、「リクエストライトバック」と参照される。ここで、上記リプライライトバック（ステップＳ３）とリクエストライトバック（ステップＳ３’’）は異なるパスで行われるため、それらの順序は必ずしも一意に定まらない。もし、ステップＳ３がステップＳ３’’よりも“後に”行われると、ホームセルＣＨのメインメモリ５において、リクエストセルＣＲによって更新された最新のデータが、オーナーセルＣＯからの古いデータによって上書きされてしまう。すなわち、ステップＳ３とステップＳ３’’が異なる場合、コヒーレンシを必ずしも保障できなくなるという問題がある。

このような問題を解決するための動作例を、図３を参照して説明する。まず、リクエストセルＣＲがホームセルＣＨにリードリクエストを発行する（ステップＳ１）。次に、ホームセルＣＨがオーナーセルＣＯにスヌープリクエストを発行する（ステップＳ２）。スヌープリクエストに応答して、オーナーセルＣＯは、キャッシュ７から最新データを読み出し、ホームセルＣＨに対してリプライライトバックを発行する（ステップＳ３）。ここで、オーナーセルＣＯは、リクエストセルＣＲに対して最新データを直接は送信しない。次に、ホームセルＣＨは、リプライライトバックに応答して、最新データで自身のメインメモリ５を更新する。その後、ホームセルＣＨは、その最新データをリプライデータとしてリクエストセルＣＲに送信する（ステップＳ４）。

このような処理によって、図２に示されたステップＳ３とステップＳ３’’の関係の発生が防止され、セル間のコヒーレンシを保障することが可能となる。しかしながら、図３に示された処理の場合、リードリクエストの発行からリプライデータの受け取りまでのレイテンシは４ＨＯＰ（ステップＳ１，Ｓ２，Ｓ３，Ｓ４）となってしまう。このことは、処理速度の低下を意味する。本来、マルチプロセッサシステムにおいて複数のプロセッサが用いられるのは、処理速度を向上させるためであり、上述のような処理速度の低下は重要な問題である。

従って、本発明の目的は、コヒーレンシの保障と処理速度の向上を両立させることである。すなわち、本発明の目的は、セル間のコヒーレンシを保障しつつ、リードリクエストに関するレイテンシを３ＨＯＰ以内に抑えることができる技術を提供することにある。

以下に、［発明を実施するための最良の形態］で使用される番号・符号を用いて、［課題を解決するための手段］を説明する。これらの番号・符号は、［特許請求の範囲］の記載と［発明を実施するための最良の形態］との対応関係を明らかにするために括弧付きで付加されたものである。ただし、それらの番号・符号を、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。

本発明に係るマルチプロセッサシステム（１）は、同一の機能を有する複数のセル（Ｃ１〜Ｃｎ）と、それら複数のセル（Ｃ１〜Ｃｎ）間を接続するネットワーク（９）とを備える。各セル（Ｃｊ）は、プロセッサ（２）、ディレクトリ（４）、キャッシュメモリ（７）、及びメインメモリ（５）を備える。複数のセル（Ｃ１〜Ｃｎ）は、リクエストセル（ＣＲ）と、ホームセル（ＣＨ）と、オーナーセル（ＣＯ）とを含む。ホームセル（ＣＨ）のメインメモリ（５）に記憶された対象データの最新版は、オーナーセル（ＣＯ）のキャッシュメモリ（７）に格納されている。

リクエストセル（ＣＲ）は、その対象データに対するリードリクエストをホームセル（ＣＨ）に発行する。ホームセル（ＣＨ）は、そのリードリクエストに応答して、スヌープリクエストをオーナーセル（ＣＯ）に発行する。オーナーセル（ＣＯ）は、そのスヌープリクエストに応答して、最新データをリクエストセル（ＣＲ）に直接送信する。これにより、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰで実現することが可能となる。

また、オーナーセル（ＣＯ）は、スヌープリクエストに応答して、リプライライトバックをホームセル（ＣＨ）に送信する。リクエストセル（ＣＲ）は、ホームセル（ＣＨ）中の上記対象データと同じアドレスに対してリクエストライトバックを発行する。そのリクエストライトバックは、リクエストセル（ＣＲ）に含まれるキャッシュ（７）のステータスとホームセル（ＣＨ）のディレクトリ（４）のステータスとを整合させるためのディレクトリ更新情報を含む。ホームセル（ＣＨ）は、オーナーセル（ＣＯ）からのリプライライトバックをリクエストセル（ＣＲ）からのリクエストライトバックよりも後に受信した場合、そのリプライライトバックを破棄し、また、ディレクトリ更新情報に基づいてディレクトリ（４）のステータスを更新する。

このような構成により、リクエストセル（ＣＲ）からのリクエストライトバックによって更新されたデータが、オーナーセル（ＣＯ）からのリプライライトバックによる古いデータで上書きされることが防止される。従って、リクエストライトバックとリプライライトバックの経路が異なっていても、コヒーレンシを保障することが可能となる。言い換えれば、オーナーセル（ＣＯ）がリプライデータを直接リクエストセル（ＣＲ）に送信しても、セル間のコヒーレンシが保たれる。

本発明に係るマルチプロセッサシステムによれば、リクエストセルＣＲ、ホームセルＣＨ、及びオーナーセルＣＯがそれぞれ異なる場合においても、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰにすることが可能である。且つ、セル間のコヒーレンシを保障することも可能である。すなわち、コヒーレンシの保障とレイテンシの短縮（処理速度の向上）との両立が実現される。

添付図面を参照して、本発明の実施の形態に係るマルチプロセッサシステムを説明する。

１．概念
図４を参照して、本実施の形態に係るマルチプロセッサシステムの動作を説明する。図４において、リクエストセルＣＲは、リードリクエストを発行する発行元であるＣＰＵを搭載している。ホームセルＣＨは、そのアクセス対象であるデータが格納されたメインメモリを有している。オーナーセルＣＯは、そのアクセス対象であるデータの最新版（最新データ）をキャッシングしているキャッシュを有している。ここでは、リクエストセルＣＲ、ホームセルＣＨ、及びオーナーセルＣＯがそれぞれ異なる場合を考える。

まず、リクエストセルＣＲのＣＰＵは、アクセス対象データを有するホームセルＣＨに、リードリクエストを発行する（ステップＳ１）。ホームセルＣＨは、リードリクエストに応答して、自身のディレクトリを検索（索引）する。ディレクトリに格納された情報により、ホームセルＣＨは、対象データの最新版がオーナーセルＣＯのキャッシュに格納されていることを知る。よって、ホームセルＣＨは、オーナーセルＣＯにスヌープリクエストを発行する（ステップＳ２）。

オーナーセルＣＯは、スヌープリクエストに応答して、キャッシュから最新データを読み出す。そして、オーナーセルＣＯは、その最新データをホームセルＣＨのメインメモリに書き戻すために、ホームセルＣＨに対してリプライライトバックを発行する（ステップＳ３）。このリプライライトバックと同時に、オーナーセルＣＯは、読み出された最新データをリプライデータとしてリクエストセルＣＲに直接送信する（ステップＳ３’）。これにより、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰ（ステップＳ１，Ｓ２，Ｓ３’）で実現することができる。

リードリクエストを発行したリクエストセルＣＲのＣＰＵは、受け取ったリプライデータを自身のキャッシュに格納する。その後、そのキャッシュのデータがリプレースされた場合などにおいて、リクエストセルＣＲは、ホームセルＣＨに対してリクエストライトバックを発行する（ステップＳ３’’）。ここで、上記リプライライトバック（ステップＳ３）とリクエストライトバック（ステップＳ３’’）は異なるパスで行われるため、それらの順序は必ずしも一意に定まらない。

本発明に係るセルは、受け取ったリードリクエストを所定のテーブルに登録しておく機能を有している。また、本発明に係るセルは、登録されたリードリクエストの対象と同じアドレスに対するリクエストライトバックを検出したときに、検出フラグを有効にする機能を有している。更に、本発明に係るセルは、そのリクエストライトバック（ステップＳ３’’）よりも後にリプライライトバック（ステップＳ３）を受け取った場合、上記検出フラグを参照することによって、受け取ったリプライライトバックを“破棄（discard）”する機能を備えている。言い換えれば、本発明に係るセルは、スヌープリクエストの発行（ステップＳ２）からリプライライトバック（ステップＳ３）までの期間にリクエストライトバック（ステップＳ３’’）を検出した場合、リプライライトバックを破棄する機能を備えている。

これにより、ホームセルＣＨにおいて、リクエストセルＣＲからのリクエストライトバックによって更新されたデータが、オーナーセルＣＯからのリプライライトバックによる古いデータで上書きされることが防止される。従って、ステップＳ３とステップＳ３’’が異なっていても、コヒーレンシを保障することが可能となる。言い換えれば、オーナーセルＣＯがリプライデータを直接リクエストセルＣＲに送信しても（ステップＳ３’）、セル間のコヒーレンシが保たれる。逆に言えば、コヒーレンシを保障しつつ、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰで実現することが可能となる。すなわち、コヒーレンシの保障とレイテンシの短縮（処理速度の向上）との両立が実現される。

２．構成
２−１．全体構成
本実施の形態に係る処理を実現するための具体的な構成例を以下に説明する。本実施の形態に係るマルチプロセッサシステムは分散共有メモリ型のマルチプロセッサシステムであり、その全体的な構成は図１に示された構成と同様である。すなわち、本実施の形態に係る分散共有メモリ型マルチプロセッサシステム１は、複数のセル（ノード）Ｃ１〜Ｃｎ（ｎはセル数を示す整数）と、それら複数のセルＣ１〜Ｃｎ間を互いに結合するクロスバースイッチ９を備えている。複数のセルＣ１〜Ｃｎは、共有バスやデータリンク等のネットワークにより互いに結合されていてもよい。

複数のセルＣ１〜Ｃｎは同一の機能を有している。各々のセルＣｊ（ｊは１以上ｎ以下の整数）は、少なくとも１つのＣＰＵ（マイクロプロセッサ）２−ｊ−１〜２−ｊ−ｍ（ｍは各セル内のＣＰＵ数を示す整数）と、メインメモリ（ローカルメモリ）５−ｊを備えている。それらＣＰＵ２の各々は、少なくとも１つのキャッシュメモリ（ストアインキャッシュ）７を搭載している。分散的に設けられたメインメモリ５−１〜５−ｎの全てによって共有メモリが構成され、その共有メモリは全てのＣＰＵ２によって参照される。

１つのセルが複数のＣＰＵ２、すなわち複数のキャッシュ７を有している場合、セル内のローカルなキャッシュコヒーレンシは、例えば「スヌープ方式」により実現される。この場合、各ＣＰＵ２に搭載されるキャッシュ７は、例えばＭＥＳＩプロトコルに基づいてキャッシュステータスを管理する。ＭＥＳＩプロトコルによれば、「Ｍ（Ｍｏｄｉｆｉｅｄ）」、「Ｅ（Ｅｘｃｌｕｓｉｖｅ）」、「Ｓ（Ｓｈａｒｅｄ）」、及び「Ｉ（Ｉｎｖａｌｉｄ）またはＵ（Ｕｎｃａｃｈｅｄ）」の４つのキャッシュステータスが提供される。

Ｍ（Ｍｏｄｉｆｉｅｄ）：当該キャッシュ中のデータは、当該キャッシュ内にのみ存在し、且つ、メインメモリ内のデータとは同一でない。つまり、最新データが自キャッシュにのみ存在する。
Ｅ（Ｅｘｃｌｕｓｉｖｅ）：当該キャッシュ中のデータは、複数のキャッシュのうち当該キャッシュ内にのみ存在し、且つ、メインメモリ内のデータと同一である。つまり、最新データは、自キャッシュとメインメモリに存在する。
Ｓ（Ｓｈａｒｅｄ）：当該キャッシュ中のデータは、自キャッシュ及び他のＣＰＵのキャッシュに存在し、且つ、メインメモリ内のデータと同一である。つまり、最新データは、複数のキャッシュとメインメモリに存在する。
Ｉ（Ｉｎｖａｌｉｄ）、Ｕ（Ｕｎｃａｃｈｅｄ）：当該キャッシュ中のデータは、無効である。つまり、最新データは、自キャッシュに存在せずメインメモリに存在する。

尚、本発明に適用されるキャッシュプロトコルは、上記ＭＥＳＩプロトコルに限られない。キャッシュステータスＭ（Ｍｏｄｉｆｉｅｄ）を提供するプロトコルであれば、如何なるキャッシュプロトコルでも適用され得る。

また、セル内のキャッシュコヒーレンシだけでなく、図１に示された複数のセルＣ１〜Ｃｎ間のキャッシュコヒーレンシも保つ必要がある。本実施の形態によれば、複数のセルＣ１〜Ｃｎの間のキャッシュコヒーレンシは、「ディレクトリ方式」に基づいて制御される。そのため、セルＣ１〜Ｃｎのそれぞれには、キャッシュコヒーレンシ回路３−１〜３−ｎ及びディレクトリ４−１〜４−ｎが設けられている。

ディレクトリ４−ｊは、ＤＲＡＭ等により実現される記憶領域である。ディレクトリ４−ｊには、自セルＣｊのメインメモリ５−ｊに格納されたデータに関するキャッシングの状態を管理するための情報が格納される。より具体的には、ディレクトリ４−ｊには、自セルＣｊのメインメモリ５−ｊに格納された全データのステータスと、そのデータの最新版をキャッシングしているセル（すなわちオーナーセルＣＯ）を示すテーブルが格納される。最新データをキャッシングしているオーナーセルＣＯは、自セルである場合もあるし、他のセルである場合もある。

ディレクトリ４−ｊに格納される情報の一例が、図５に示されている。図５に示されるように、メインメモリ５−ｊのデータアドレス毎に、そのステータス（Ｐ，Ｓ，Ｕ）及びオーナーセル情報が対応付けられている。例えば、データアドレスＡ０に関するステータスは「Ｐ（Ｐｒｉｖａｔｅ）」である。ステータス「Ｐ」は、最新データが唯一のセルのキャッシュ７に登録されている可能性を示している。そのキャッシュ７のキャッシュステータスとしては、「Ｍ」，「Ｅ」，「Ｓ」，及び「Ｉ」の全てが許容される。また、オーナーセル情報としてはオーナーセルＣＯのセル番号が登録される。

また、データアドレスＡ１に関するステータスは「Ｓ」である。ステータス「Ｓ（Ｓｈａｒｅｄ）」は、最新データが複数のセルのキャッシュ７に登録されている可能性を示している。それらキャッシュ７のキャッシュステータスとしては、「Ｓ」及び「Ｉ」が許容される。この場合、オーナーセル情報としては、セルＣ１〜Ｃｎに対応するビットマップが登録される。例として、セル数が３個であり（ｎ＝３）、セルＣ１及びＣ２のキャッシュ７に最新データが格納されている場合を考える。この場合、３ビットのビットマップのうちセルＣ１とセルＣ２に対応するビットが“１”にセットされ、セルＣ３に対応するビットは“０”にセットされる；（セルＣ３，セルＣ２，セルＣ１）＝（０，１，１）。このようなビットマップによりオーナー情報が管理される。

また、データアドレスＡ２に関するステータスは「Ｕ（Ｕｎｃａｃｈｅｄ）」である。ステータス「Ｕ」は、メインメモリ５−ｊ中のデータが最新データであることを示す。この場合、オーナーセル情報としては特に何も登録されない（Ｎ／Ａ：ＮｏｔＡｖａｉｌａｂｌｅ）。以上に示されたステータスＰ，Ｓ，Ｕは、メインメモリ５−ｊに関するキャッシュステータスと言うこともできる。

このようなディレクトリ４−ｊを参照することによって、本実施の形態に係るキャッシュコヒーレンシ回路３−ｊは、セルＣ１〜Ｃｎ間のコヒーレンシ制御を行う。つまり、キャッシュコヒーレンシ回路３−ｊは、ディレクトリ４−ｊを用い、ディレクトリ方式に基づいてキャッシュコヒーレンシを保障する。以下に説明されるように、本発明は特に、このキャッシュコヒーレンシ回路３−ｊに特徴を有している。

２−２．キャッシュコヒーレンシ回路
図６は、本実施の形態に係るセルＣｊのキャッシュコヒーレンシ回路３−ｊの構成を示すブロック図である。セルＣｊにおいて、キャッシュコヒーレンシ回路３−ｊは、複数のＣＰＵ２−ｊ−１〜２−ｊ−ｍ、ディレクトリ４−ｊ、及びメインメモリ５−ｊに接続されている。また、キャッシュコヒーレンシ回路３−ｊは、クロスバースイッチ９を介して他のセルと通信可能に接続されている。図６に示されるように、キャッシュコヒーレンシ回路３−ｊは、ＣＰＵリクエスト制御部１０、クロスバーリクエスト制御部２０、メインパイプ部３０、ディレクトリアクセス制御部４０、メインメモリアクセス制御部５０、及びリプライデータ制御部６０を有している。それらユニットは、互いにデータやリクエストをやりとりできるように構成されている。

リクエストとしては、「リードリクエスト」、「スヌープリクエスト」、「リプライライトバック」、及び「リクエストライトバック」が挙げられる。

リードリクエストには、リード対象アドレス及び当該リードリクエストの発行元が含まれる。本例において、リード対象アドレスは、ホームセルＣＨのメインメモリ５中のアドレスであり、発行元は、リクエストセルＣＲのＣＰＵ２である。つまり、リードリクエストには、少なくともリクエストセルＣＲとホームセルＣＨに関する情報が含まれていると言える。

スヌープリクエストには、リードリクエストの情報がコピーされ、リード対象アドレス及びリードリクエストの発行元が含まれる。

リプライライトバックには、スヌープリクエストの情報がコピーされ、リード対象アドレス及びリードリクエストの発行元が含まれる。更に、リプライライトバックには、ライトバックデータが含まれる。リード対象アドレスは、そのライトバックデータが書き戻されるライトバック対象アドレスでもある。

リクエストライトバックには、ライトバックデータ、ライトバック対象アドレス、当該リクエストライトバックの発行元、及びディレクトリ更新情報が含まれる。本例において、ライトバック対象アドレスは、ホームセルＣＨのメインメモリ５中のアドレスであり、発行元は、リクエストセルＣＲのＣＰＵ２である。ディレクトリ更新情報は、リクエストセルＣＲに含まれるキャッシュ７のキャッシュステータスとホームセルＣＨのディレクトリ４のステータスとを整合させるための情報である。ディレクトリ更新情報には、ホームセルＣＨのディレクトリ４のステータスをどのように更新すればよいか示されている。

ＣＰＵリクエスト制御部１０は、ＣＰＵ２からのリクエストを処理する機能を有する。より具体的には、ＣＰＵリクエスト制御部１０は、ＣＰＵ２が発行するリードリクエストを受信し、そのリードリクエストに含まれるリード対象アドレスに応じて、自セルのメインパイプ部３０又はホームセルＣＨにリードリクエストを転送する。また、ＣＰＵリクエスト制御部１０は、ＣＰＵ２が発行するライトバックを受信し、そのライトバックに含まれるライトバック対象アドレスに応じて、自セルのメインパイプ部３０又はホームセルＣＨにライトバックを転送する。

更に、ＣＰＵリクエスト制御部１０は、ＣＰＵ２に対するスヌープリクエストを処理する機能を有する。より具体的には、ＣＰＵリクエスト制御部１０は、クロスバースイッチ９又はディレクトリアクセス制御部４０から受け取るスヌープリクエストを、ＣＰＵ２に転送する。そして、ＣＰＵリクエスト制御部１０は、スヌープ処理によってＣＰＵ２のキャッシュ７から得られるリプライデータを、リクエストセルＣＲに直接送信する。これにより、リードリクエストの発行からリプライデータの受け取りまでのレイテンシが短縮される。

クロスバーリクエスト制御部２０は、クロスバースイッチ９から受け取るリクエストを処理する機能を有する。より具体的には、クロスバーリクエスト制御部２０は、クロスバースイッチ９より受信するリードリクエスト、リプライライトバック、及びリクエストライトバックをメインパイプ部３０に転送する。

メインパイプ部３０は、ＣＰＵリクエスト制御部１０とクロスバーリクエスト制御部２０から受信したリクエストを調停し、また、ディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に対するリクエストを制御する機能を備える。メインパイプ部３０の詳細な機能は、後の第２−３節において詳しく説明される。

ディレクトリアクセス制御部４０は、ディレクトリ４に対するアクセスを制御する。具体的には、ディレクトリアクセス制御部４０は、メインパイプ部３０から受信するリクエスト（リードリクエスト，リクエストライトバック，リプライライトバック）に応答して、ディレクトリ４の索引（検索）を行う。読み出されたディレクトリ４のステータスによっては、ディレクトリアクセス制御部４０は、スヌープリクエストをオーナーセルＣＯ又は自セルのＣＰＵリクエスト制御部１０に発行する。

また、ディレクトリアクセス制御部４０は、メインパイプ部３０から受信するリクエストに応答して、ディレクトリ４の更新を行う。ディレクトリ４の更新方法は、読み出されるディレクトリ４の状態に応じて異なり、それは所定のルールにより規定されている（図９参照）。ただし、リプライライトバックの場合、ディレクトリ４の更新がその所定のルールと違う方式で行われることがある。そのような場合、ディレクトリアクセス制御部４０は、メインパイプ部３０から「更新リクエスト」を受け取る。そして、ディレクトリアクセス制御部４０は、その更新リクエストが指示するように、ディレクトリ４の更新を行う。

メインメモリアクセス制御部５０は、メインメモリ５に対するアクセスを制御する。具体的には、メインメモリアクセス制御部５０は、メインパイプ部３０から受信したリードリクエストに応答して、メインメモリ５から対象データを読み出す。そして、メインメモリアクセス制御部５０は、読み出されたデータ（読み出しデータ）をリプライデータとしてリクエストセルＣＲ又は自セルのリプライデータ制御部６０に送信する。また、メインメモリアクセス制御部５０は、メインパイプ部３０から受信したリプライライトバック又はリクエストライトバックに応答して、ライトバックデータをメインメモリ５に書き込む。

リプライデータ制御部６０は、メインメモリアクセス制御部５０あるいはクロスバースイッチ９から受け取るリプライデータを、ＣＰＵ２に転送する機能を有している。

２−３．メインパイプ部
図７は、本実施の形態に係るメインパイプ部３０の構成を示すブロック図である。図７に示されるように、メインパイプ部３０は、スヌープ管理テーブル３１、ライトバック検出回路３２、キャンセル判定回路３３、ディスカード判定回路３４、及び調停制御回路３５を有している。

調停制御回路３５は、ＣＰＵリクエスト制御部１０からのリクエストとクロスバーリクエスト制御部２０からのリクエストとの調停を行う。調停を獲得したリクエストは、スヌープ管理テーブル３１、ライトバック検出回路３２、キャンセル判定回路３３、及びディスカード判定回路３４へ転送される。

スヌープ管理テーブル３１は情報が格納されるテーブルであり、そこには複数のエントリが格納される。各エントリは、バリッドビット３１１、アドレス情報３１２、セル情報３１３、及びライトバック検出情報３１４から構成される。図８には、あるセルにおけるスヌープ管理テーブル３１の一例が示されている。バリッド（Ｖ）ビット３１１は、当該エントリが有効エントリ（“１”）か空きエントリ（“０”）かを示す。

アドレス情報３１２としては、リードリクエストが示すリード対象アドレス（例：Ａ０，Ａ１）が格納される。セル情報（リクエストセル情報）３１３としては、そのリードリクエストを発行した発行元のセル（例：Ｃ１，Ｃ３）の番号が格納される。このように、本発明に係るセルは、受け取ったリードリクエストを記憶しておく機能を有している。尚、後述されるように、複数のエントリに対応する複数のリード対象アドレス（Ａ０，Ａ１）は、それぞれ異なるように制御される。つまり、アドレス情報３１２に含まれる“あるリード対象アドレス”の数は、０個か１個である。あるリード対象アドレスに対するリードリクエストが既に登録されている場合、同じリード対象アドレスに対するリードリクエストは登録待機状態になる。

ライトバック検出情報３１４は、検出フラグとディレクトリ更新情報を含む。検出フラグやディレクトリ更新情報は、登録されたアドレス情報３１２及びセル情報３１３と対応付けられている。検出フラグは、リクエストセルＣＲからのライトバック、すなわちリクエストライトバックが検出されたか否かを示すフラグである。検出フラグが有効（“１”）のとき、当該リード対象アドレス（Ａ０）に対するリクエストライトバックが検出されている。一方、ディレクトリ更新情報は、ディレクトリ４がどのステータスに更新されるかを示す情報であり、検出フラグが“１”に設定される時に同時に設定される。後述されるように、このディレクトリ更新情報は、更新リクエストの生成時に用いられる。

図７に戻り、ライトバック検出回路３２は、アドレス情報比較器３２１、セル情報比較器３２２、及びＡＮＤ３２３を有している。このライトバック検出回路３２は、調停制御回路３５から転送されたリクエストを受け取る。そして、ライトバック検出回路３２は、上記スヌープ管理テーブル３１を参照することによって、アドレス情報３１２が示すリード対象アドレスの各々に対する「リクエストライトバック」を検出する。

具体的には、アドレス情報比較器３２１は、ライトバック（リプライライトバック又はリクエストライトバック）が示すライトバック対象アドレスと、上記スヌープ管理テーブル３１中のアドレス情報３１２が示すリード対象アドレスとの比較を行う。そして、アドレス情報比較器３２１は、全てのエントリに関して一致（“１”）／不一致（“０”）を示すビットマップデータ（ビット数＝総エントリ数）を出力する。尚、Ｖビット３１１が無効であるエントリは、自動的に不一致（“０”）と判定される。そのビットマップデータにおいて、全てのビットは“０”、あるいは、１つのビットだけが“１”である。ビットマップデータのうち“１”に対応するエントリは、以下「一致エントリ」と参照される。

一方、セル情報比較器３２２は、リクエストライトバックを受けとった時に、そのリクエストライトバックが示す発行元の番号と、上記スヌープ管理テーブル３１中のセル情報３１３が示すリクエストセルＣＲの番号との比較を行う。そして、セル情報比較器３２２は、全てのエントリに関して一致（“１”）／不一致（“０”）を示すビットマップデータを出力する。尚、Ｖビット３１１が無効であるエントリは、自動的に不一致（“０”）と判定される。

ＡＮＤ３２３は、アドレス情報比較器３２１からのビットマップデータとセル情報比較器３２２からのビットマップデータとの論理積を出力する。出力されるビットマップデータにおいて、全てのビットは“０”、あるいは、１つのビットだけが“１”である。そして、ライトバック検出回路３２は、そのビットマップデータのうち“１”に対応するエントリ（一致エントリ）のライトバック検出情報３１４を変更する。具体的には、ライトバック検出回路３２は、検出フラグを無効（“０”）から有効（“１”）に変更し、また、ディレクトリ変更情報をリクエストライトバックが示すディレクトリ更新情報に設定する。つまり、ディレクトリ更新情報は、有効化された検出フラグと対応づけられてスヌープ管理テーブル３１に格納される。

ＡＮＤ３２３の出力に“１”が含まれていることは、「あるリクエストセルＣＲがあるアドレスに対してリードリクエストを発行し、更に、同じリクエストセルＣＲが同じアドレスに対してリクエストライトバックを発行したこと」を意味する。つまり、ライトバック検出回路３２は、スヌープ管理テーブル３１に登録されたリードリクエストと関連したリクエストライトバックを検出するための回路であると言える。ライトバック検出回路３２は、そのようなリクエストライトバックを検出した場合、当該一致エントリの検出フラグを“１”にセットする。このように、本発明に係るセルは、登録されたリードリクエストの対象と同じアドレスに対するリクエストライトバックを検出したときに、検出フラグを有効にする機能を有している。スヌープ管理テーブル３１に予め格納されるリードリクエストに関する情報（アドレス情報３１２，セル情報３１３）は、後に受け取るかもしれないリクエストライトバックを検出するための情報であると言える。

また、ライトバック検出回路３２は、リプライライトバックを受け取った場合、アドレス情報比較器３２１から出力されるアドレス一致エントリ（ビットマップデータ）をキャンセル判定回路３３及びディスカード判定回路３４に出力する。また、ライトバック検出回路３２は、リプライライトバックを受け取った場合、そのアドレス一致エントリに関するＶビット３１１を無効化（“０”）する。つまり、ライトバック検出回路３２は、リプライライトバックに応答して、そのリプライライトバックに関連するエントリを初期化する。

次に、キャンセル判定回路３３について説明する。上述の通り、スヌープ管理テーブル３１において、あるリード対象アドレスに対するリードリクエストが既に登録されている場合、同じリード対象アドレスに対するリードリクエストは登録待機状態に設定される。そのためにキャンセル判定回路３３が設けられている。キャンセル判定回路３３は、調停制御回路３５からのリードリクエスト、及び上記ライトバック検出回路３２のアドレス情報比較器３２１からの出力を受け取る。アドレス情報比較器３２１からアドレス一致エントリが出力された場合、すなわち、スヌープ管理テーブル３１に既に登録されているリード対象アドレスと同一アドレスへのリードリクエストが検出された場合、キャンセル判定回路３３は、ＣＰＵリクエスト制御部１０又はクロスバーリクエスト制御部２０に対して、リードリクエストの再発行を要求する。そして、スヌープ管理テーブル３１に空きエントリができるまで、同じ動作が繰り返される。これにより、そのリードリクエストは、登録待機状態となる。

ディスカード判定回路３４は、調停制御回路３５から転送されたリクエスト（リードリクエスト，リクエストライトバック，リプライライトバック）を受け取る。受け取ったリクエストがリードリクエストの場合、ディスカード判定回路３４は、そのリードリクエストをディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に出力する。また、そのリクエストがリクエストライトバックの場合、ディスカード判定回路３４は、そのリクエストライトバックをディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に出力する。

また、受け取ったリクエストがリプライライトバックの場合、ディスカード判定回路３４は、アドレス情報比較器３２１からの出力（ビットマップデータ）を受け取り、そのビットマップデータが示すアドレス一致エントリのライトバック検出情報３１４を参照する。参照されたライトバック検出情報３１４の検出フラグが“０”の場合、ディスカード判定回路３４は、リプライライトバックをディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に出力する。一方、検出フラグが“１”の場合、それはリクエストライトバックの後にリプライライトバックが入力されたことを意味する。この場合、ディスカード判定回路３４は、受け取ったリプライライトバックを破棄（ディスカード）する。よって、リプライライトバックは、メインメモリアクセス制御部５０には出力されない。ただし、ディスカード判定回路３４は、ディレクトリ４のステータスを更新するための「更新リクエスト」をディレクトリアクセス制御部４０に発行する。その更新リクエストの指示内容は、参照されたライトバック検出情報３１４中の「ディレクトリ更新情報」によって決定される。

以上に説明されたように、本実施の形態に係るメインパイプ部３０は、（１）リクエストセルＣＲからのリードリクエストを登録する機能、（２）登録されたリードリクエストの対象と同じアドレスに対するリクエストライトバックを検出したときに、その検出を記憶しておく機能、及び（３）ディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に対するリクエストを制御する機能；具体的には、リクエストライトバックよりも後にリプライライトバックを受け取った場合、そのリプライライトバックを破棄し、ディレクトリ４を更新する機能、を備えている。上記（１）の機能は、スヌープ管理テーブル３１により提供される。上記（２）の機能は、ライトバック検出回路３２及びスヌープ管理テーブル３１により提供される。上記（３）の機能は、ディスカード判定回路３４及びスヌープ管理テーブル３１により提供される。これにより、上述の図４に示された動作が実現される。

尚、図９には、各リクエストに対するディレクトリ４の索引時のステータス及び更新後のステータスが要約的に示されている。図９に示された要約は、以下の動作例の説明において適宜参照される。

３．システムの動作例
既出の図６、図７、図９、及び以下に示される図面を参照しながら、本実施の形態に係るマルチプロセッサシステム１の動作例を説明する。本動作例において、リクエストセルＣＲ、ホームセルＣＨ、及びオーナーセルＣＯは互いに異なっているとする。例えば、リクエストセルＣＲはセルＣ１、ホームセルＣＨはセルＣ２、オーナーセルＣＯはセルＣ３である。つまり、リクエストセルＣ１のＣＰＵ２（例えばＣＰＵ２−１−１）による読み出し対象のアドレスは、ホームセルＣ２に搭載されたメインメモリ５−２中のアドレスであり、そのアドレスに対応した最新データは、オーナーセルＣ３に搭載されたＣＰＵ２（例えばＣＰＵ２−３−１）中のキャッシュ７に格納されている。

図１０は、本動作例における処理フローを概念的に示している。また、図１１は、リクエストセルＣ１のＣＰＵ２−１−１のキャッシュステータス、ホームセルＣ２のキャッシュコヒーレンシ回路３−２のスヌープ管理テーブル３１及びディレクトリ４−２の内容、及びオーナーセルＣ３のＣＰＵ２−３−１のキャッシュステータスの遷移を示している。初期状態において、リクエストセルＣ１のＣＰＵ２−１−１のキャッシュステータスは“Ｉ（Ｉｎｖａｌｉｄ）”、オーナーセルＣ３のＣＰＵ２−３−１のキャッシュステータスは“Ｍ（Ｍｏｄｉｆｉｅｄ）”である。また、ホームセルＣ２のディレクトリ４−２において、リード対象アドレスＡ０に対するステータスは“Ｐ”、オーナーセル情報は“セルＣ３”をそれぞれ示すとする。

ステップＳ１１：リクエストセルＣ１：リードリクエストの発行
まず、リクエストセルＣ１のＣＰＵ２−１−１が、ホームセルＣ２のメインメモリ５−２中のアドレスＡ０に対して「リードリクエスト」を発行する。このリードリクエストには、リード対象アドレスＡ０及び発行元（ＣＰＵ２−１−１）が含まれている。ＣＰＵ２−１−１がリードリクエストを発行すると、リクエストセルＣ１のＣＰＵ２−１−１〜ＣＰＵ２−１−ｍのそれぞれにおいてスヌープ処理が実行される。具体的には、ＣＰＵ２−１−１〜ＣＰＵ２−１−ｍのそれぞれのキャッシュ７が、自身がリード対象アドレスＡ０のデータを格納しているかどうか調べる。

キャッシュヒットが無い場合、リードリクエストは、リクエストセルＣ１のキャッシュコヒーレンシ回路３−１に送信される。キャッシュコヒーレンシ回路３−１のＣＰＵリクエスト制御部１０は、ＣＰＵ２−１−１からのリードリクエストを受け取る。そのＣＰＵリクエスト制御部１０は、リードリクエストに含まれるリード対象アドレスＡ０に基づいて、アクセス対象となるホームセルＣ２を判別する。ホームセルＣ２は、リード対象アドレスＡ０により一意に決定される。そして、ＣＰＵリクエスト制御部１０は、クロスバースイッチ９を介してホームセルＣ２にリードリクエストを送信する。

ステップＳ１２：ホームセルＣ２：スヌープ管理テーブル３１の更新
ホームセルＣ２のキャッシュコヒーレンシ回路３−２のクロスバーリクエスト制御部２０は、リクエストセルＣ１からクロスバースイッチ９を通してリードリクエストを受け取る。そして、クロスバーリクエスト制御部２０は、受け取ったリードリクエストをメインパイプ部３０に転送する。メインパイプ部３０の調停制御回路３５は、そのリードリクエストとＣＰＵリクエスト制御部１０からのリクエストとの調停を行う。

クロスバーリクエスト制御部２０からのリードリクエストが調停を獲得すると、そのリードリクエストは、スヌープ管理テーブル３１、ライトバック検出回路３２、キャンセル判定回路３３、及びディスカード判定回路３４に転送される。そして、メインパイプ部３０は、スヌープ管理テーブル３１の空きエントリに、そのリードリクエストを登録する。この場合、図１１に示されるように、リードリクエストが登録されるエントリに関して、Ｖビット３１１は“０”から“１”に変更され、アドレス情報３１２としてリード対象アドレスＡ０が登録され、セル情報３１３としてリクエストセルＣ１の番号が登録され、ライトバック検出情報３１４の検出フラグは“０”にセットされる。

尚、スヌープ管理テーブル３１の有効エントリ（Ｖビット３１１が“１”のエントリ）に同一アドレスＡ０に対するリードリクエストが既に存在する場合、アドレス情報比較器３２１（図７参照）は、アドレス一致エントリを検出する。アドレス一致エントリが検出されると、キャンセル判定回路３３は、クロスバーリクエスト制御部２０にリードリクエストの再発行を要求する。その結果、そのリードリクエストは登録待ち状態になる。これにより、スヌープ管理テーブル３１に同一アドレスに対する複数のリードリクエストが格納されることが防止される。

続いて、メインパイプ部３０（ディスカード判定回路３４）は、ディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０にリードリクエストを送信する。

ステップＳ１３：ホームセルＣ２：ディレクトリアクセス
ホームセルＣ２のディレクトリアクセス制御部４０は、受け取ったリードリクエストに応答して、まずディレクトリ４−２の索引を行う。図１１に示されるように、ディレクトリ４−２において、リード対象アドレスＡ０に対するステータスは“Ｐ”、オーナーセル情報は“セルＣ３”である。この場合、ディレクトリアクセス制御部４０は、クロスバースイッチ９を通してオーナーセルＣ３に「スヌープリクエスト」を発行する。このスヌープリクエストには、リードリクエストの情報がコピーされ、リード対象アドレスＡ０及び当該リードリクエストの発行元（リクエストセルＣ１のＣＰＵ２−１−１）が含まれる。

また、ディレクトリアクセス制御部４０は、リードリクエストに応答して、ディレクトリ４−２の更新を行う。図９を参照して、リードリクエストに対する索引時にステータスが“Ｐ”である場合、ステータスは更新されない（ＮＣ：Ｎｏ Ｃｈａｎｇｅ）。更に、ディレクトリアクセス制御部４０は、メインメモリアクセス制御部５０に、ステータス情報“Ｐ”とオーナーセル情報“Ｃ３”を出力する。

ステップＳ１４：ホームセルＣ２：メモリアクセス
一方、ホームセルＣ２のメインメモリアクセス制御部５０は、受け取ったリードリクエストに応答して、メインメモリ５−２中のリード対象アドレスＡ０からデータを読み出す。そして、メインメモリアクセス制御部５０は、読み出されたデータに、ディレクトリアクセス制御部４０から受け取ったステータス情報“Ｐ”とオーナーセル情報“Ｃ３”を付与することによって、リプライデータＤＲを生成する。メモリアクセス制御部５０は、そのリプライデータＤＲを、クロスバースイッチ９を介してリクエストセルＣ１に送信する。

ステップＳ１５：リクエストセルＣ１：リプライデータＤＲの受信
リクエストセルＣ１のリプライデータ制御部６０は、クロスバースイッチ９からリプライデータＤＲを受け取る。そのリプライデータＤＲには、ステータスが“Ｐ”であることと、オーナーセルがセルＣ３であることが示されている。この場合、リプライデータ制御部６０は、オーナーセルＣ３からのリプライデータを待ち合わせる。

ステップＳ１６：オーナーセルＣ３：スヌープ処理、リプライライトバックの発行
オーナーセルＣ３のＣＰＵリクエスト制御部１０は、ホームセルＣ２が発行したスヌープリクエストを受け取る。そして、ＣＰＵリクエスト制御部１０は、自セルＣ３のＣＰＵ２−３−１〜２−３−ｍにスヌープリクエストを発行する。ＣＰＵ２−３−１〜２−３−ｍのそれぞれのキャッシュ７は、スヌープ処理を実行する。その結果、キャッシュステータスが“Ｍ”であるＣＰＵ２−３−１は、「リプライライトバック」をＣＰＵリクエスト制御部１０に発行する。リプライライトバックには、スヌープリクエストの情報がコピーされ、リード対象アドレスＡ０及びリードリクエストの発行元（リクエストセルＣ１）が含まれる。更に、リプライライトバックには、キャッシュ７から読み出されたデータ（ライトバックデータ）が含まれる。リード対象アドレスＡ０は、そのライトバックデータが書き戻されるライトバック対象アドレスＡ０でもある。また、リプライライトバックの発行に応答して、ＣＰＵ２−３−１のキャッシュ７のキャッシュステータスは、“Ｍ”から“Ｉ”に変更される。

オーナーセルＣ３のＣＰＵリクエスト制御部１０は、ＣＰＵ２−３−１からリプライライトバックを受け取ると、そのリプライライトバックをクロスバースイッチ９を介してホームセルＣ２に送信する（ステップＳ１６−１）。ホームセルＣ２は、ライトバック対象アドレスＡ０により一意に決定される。

更に、オーナーセルＣ３のＣＰＵリクエスト制御部１０は、キャッシュ７から読み出されたデータ（リプライデータＤＲ’）をリクエストセルＣ１へ直接送信する（ステップＳ１６−２）。その送信先（リクエストセルＣ１）は、スヌープリクエストあるいはリプライライトバックに含まれるリードリクエストの発行元情報により決定することができる。

ステップＳ１７：リクエストセルＣ１：リプライデータＤＲ’の受信
リクエストセルＣ１のリプライデータ制御部６０は、オーナーセルＣ３からクロスバースイッチ９を通してリプライデータＤＲ’を直接受け取る。この時、リプライデータ制御部６０は、上記ステップＳ１５で受け取ったリプライデータＤＲを破棄する。そして、リプライデータ制御部６０は、オーナーセルＣ３から受け取ったリプライデータＤＲ’を、リードリクエストの発行元であるＣＰＵ２−１−１に送信する。ＣＰＵ２−１−１は、リプライデータＤＲ’を受け取ると、そのリプライデータＤＲ’を自身のキャッシュ７に登録する。この時、ＣＰＵ２−１−１のキャッシュ７のキャッシュステータスは、“Ｉ”から“Ｅ”に変更される。以上に説明されたように、リードリクエストの発行からリプライデータＤＲ’の受け取りまでが３ＨＯＰで実現される。

ステップＳ１８：リクエストセルＣ１：リクエストライトバックの発行
ステップＳ１７の後、ＣＰＵ２−１−１は、キャッシュ７に格納されたデータを新たなデータで書き換える、すなわち、キャッシュ７に格納されたデータを更新する。この時、そのキャッシュ７のステータスは、“Ｅ”から“Ｍ”に一旦変更される。更に、ＣＰＵ２−１−１は、キャッシュ７のデータ更新に応答して、「リクエストライトバック」をＣＰＵリクエスト制御部１０に発行する。リクエストライトバックの発行に応答して、ＣＰＵ２−１−１のキャッシュ７のキャッシュステータスは、“Ｍ”から“Ｉ”に変更される。このリクエストライトバックには、キャッシュ７に格納された最新データ（ライトバックデータ）、ライトバック対象アドレスＡ０、発行元情報（リクエストセルＣ１のＣＰＵ２−１−１）、及びディレクトリ更新情報が含まれている。キャッシュステータスが“Ｉ”に変更されている場合、ディレクトリ更新情報は「Ｕ更新」に設定される。

参考のため、ＣＰＵ２−１−１のキャッシュ７のステータスが“Ｅ”から“Ｍ”に変更された後、別のＣＰＵ２−１−２がそのデータに対するリードリクエストを発行した場合を考える。この場合、スヌープ処理により、ＣＰＵ２−１−１のキャッシュ７に格納されたデータが、ＣＰＵ２−１−２のキャッシュ７に移動する。ＣＰＵ２−１−１に関するキャッシュステータスは“Ｍ”から“Ｉ”に変更される一方、ＣＰＵ２−１−２に関するキャッシュステータスは“Ｉ”から“Ｅ”に変更される。この場合、セルＣ１におけるキャッシュステータスに“Ｅ”が含まれているため、ＣＰＵ２−１−１が発行するリクエストライトバックのディレクトリ更新情報は「ＮＣ更新」に設定されるとよい。

キャッシュコヒーレンシ回路３−１のＣＰＵリクエスト制御部１０は、ＣＰＵ２−１−１からリクエストライトバック（Ｕ更新）を受け取ると、ライトバック対象アドレスＡ０に基づいて、アクセス先となるホームセルＣ２を判別する。そして、ＣＰＵリクエスト制御部１０は、そのリクエストライトバックをクロスバースイッチ９を介してホームセルＣ２に送信する。

ステップＳ１９：ホームセルＣ２：リクエストライトバックの検出
ホームセルＣ２のキャッシュコヒーレンシ回路３−２のクロスバーリクエスト制御部２０は、リクエストセルＣ１からリクエストライトバックを受け取る。そして、クロスバーリクエスト制御部２０は、受け取ったリクエストライトバックをメインパイプ部３０に転送する。メインパイプ部３０の調停制御回路３５は、そのリクエストライトバックとＣＰＵリクエスト制御部１０からのリクエストとの調停を行う。

クロスバーリクエスト制御部２０からのリクエストライトバックが調停を獲得すると、そのリクエストライトバックは、ライトバック検出回路３２及びディスカード判定回路３４に転送される。ライトバック検出回路３２において、アドレス情報比較器３２１は、図１１に示されたスヌープ管理テーブル３１のアドレス情報３１２（“Ａ０”）と、リクエストライトバックが示すライトバック対象アドレスＡ０とが一致していることを検出する。また、セル情報比較器３２２は、図１１に示されたスヌープ管理テーブル３１のセル情報３１３（“Ｃ１”）と、リクエストライトバックが示す発行元情報（“Ｃ１”）とが一致していることを検出する。そして、ＡＮＤ３２３の演算により、一致エントリが検出される。この場合、ライトバック検出回路３２は、スヌープ管理テーブル３１中の当該一致エントリのライトバック検出情報３１４を更新する。具体的には、当該一致エントリの検出フラグが“１”にセットされる。また、リクエストライトバックに含まれるディレクトリ更新情報（Ｕ更新）に応じて、当該一致エントリのディレクトリ更新情報は「Ｕ」にセットされる。

以上に説明されたように、ホームセルＣ２において、アドレスＡ０に対するリクエストライトバックが検出されたことが記憶される。また、スヌープ管理テーブル３１の更新が行われる。続いて、メインパイプ部３０（ディスカード判定回路３４）は、ディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０にリクエストライトバックを送信する。

ステップＳ２０：ホームセルＣ２：ディレクトリアクセス、メモリアクセス
ホームセルＣ２のメインメモリアクセス制御部５０は、受け取ったリクエストライトバックに応答して、メインメモリ５−２中のライトバック対象アドレスＡ０に、ライトバックデータを書き戻す。

また、ディレクトリアクセス制御部４０は、受け取ったリクエストライトバックに応答して、ディレクトリ４−２の索引・更新を行う。図１１に示されるように、ディレクトリ４−２において、オーナーセル情報は“セルＣ３”である。つまり、ディレクトリ４−２の索引の結果、リクエストライトバックが示す発行元情報（リクエストセルＣ１）はディレクトリ４−２中のオーナーセル情報（オーナーセルＣ３）と異なっていることが分かる。この場合、図９を参照して、ディレクトリアクセス制御部４０は、ディレクトリ４−２のステータス及びオーナーセル情報を更新しない（ＮＣ：Ｎｏ Ｃｈａｎｇｅ）。

ステップＳ２１：ホームセルＣ２：リプライライトバックの破棄
ホームセルＣ２は、ステップＳ１９による「リクエストライトバック」よりも後に、上記ステップＳ１６−１による「リプライライトバック」を受け取るとする。ホームセルＣ２のキャッシュコヒーレンシ回路３−２のクロスバーリクエスト制御部２０は、オーナーセルＣ３からリプライライトバックを受け取る。そして、クロスバーリクエスト制御部２０は、受け取ったリプライライトバックをメインパイプ部３０に転送する。メインパイプ部３０の調停制御回路３５は、そのリプライライトバックとＣＰＵリクエスト制御部１０からのリクエストとの調停を行う。

クロスバーリクエスト制御部２０からのリプライライトバックが調停を獲得すると、そのリプライライトバックは、ライトバック検出回路３２及びディスカード判定回路３４に転送される。ライトバック検出回路３２において、アドレス情報比較器３２１は、リプライライトバックが示すライトバック対象アドレスＡ０とスヌープ管理テーブル３１のアドレス情報３１２との比較を行う。そして、ライトバック検出回路３２は、ライトバック対象アドレスＡ０と一致するアドレス一致エントリを、ディスカード判定回路３４に通知する。

ディスカード判定回路３４は、リプライライトバックを受け取った場合、スヌープ管理テーブル３１中の当該アドレス一致エントリのライトバック検出情報３１４を読み出す。図１１に示されるように、当該アドレス一致エントリの検出フラグは“１”にセットされている。これは、リクエストライトバックが既に行われていることを意味する。これにより、ディスカード判定回路３４は、リプライライトバックよりも前にリクエストライトバックが行われたことを認識する。この場合、ディスカード判定回路３４は、リプライライトバックを破棄（ディスカード）し、メインメモリアクセス制御部５０に対してリプライライトバックを出力しない。その結果、リクエストセルＣＲからのリクエストライトバックによって更新されたデータが、オーナーセルＣＯからのリプライライトバックによる古いデータで上書きされることが防止される。

ステップＳ２２：ホームセルＣ２：ディレクトリの更新
また、ディスカード判定回路３４は、ライトバック検出情報３１４を参照した際、当該アドレス一致エントリのディレクトリ更新情報が「Ｕ」にセットされていることを検知する（図１１参照）。この場合、ディスカード判定回路３４は、ディレクトリアクセス制御部４０に「更新リクエスト（Ｕ更新）」を発行する。ディレクトリアクセス制御部４０は、受け取った更新リクエストに応答して、ディレクトリ４−２の更新を行う。図９に示された規定によるとリプライライトバックの場合は「ＮＣ」であるが、今回の場合、「更新リクエスト（Ｕ更新）」が優先される。よって、ディレクトリアクセス制御部４０は、更新リクエストに応じて、ディレクトリ４−２のステータスを“Ｐ”から“Ｕ”に変更し、オーナーセル情報を消去する。図１１に示されるように、セルＣ１のキャッシュステータス（“Ｉ”）、セルＣ２のディレクトリ４−２のステータス（“Ｕ”）、及びセルＣ３のキャッシュステータス（“Ｉ”）の間に不整合が無いことが分かる。すなわち、セル間のコヒーレンシが保たれている。

尚、リプライライトバックを受け取った場合、ライトバック検出回路３２は、アドレス情報比較器３２１からの出力に基づいて、スヌープ管理テーブル３１中のアドレス一致エントリを初期化する。具体的には、ライトバック検出回路３２は、そのアドレス一致エントリに関するＶビット３１１を“０”に戻す。これにより、一連の処理が終わる。

また、ホームセルＣ２がリプライライトバックをリクエストライトバックよりも前に受け取った場合の処理は、次の通りである。ライトバック検出情報３１４の検出フラグは“０”のままなので、ディスカード判定回路３４は、リプライライトバックをディレクトリアクセス制御部４０及びメインメモリアクセス制御部５０に出力する。これにより、通常通りライトバックが行われ、ライトバックデータがアドレスＡ０に書き戻される。また、図９に示されたルールに従い、ディレクトリ４−２のステータスは“Ｐ”のまま維持され、オーナーセル情報は「セルＣ３」から「セルＣ１（リクエストセル）」に変更される。セルＣ１は、リプライライトバックに含まれる「リクエストセルの発行元情報」により指定される。また、リプライライトバックによって、当該エントリは初期化される。従って、その後にリクエストライトバックが受信されても、ライトバック検出情報３１４の検出フラグは有効化されない。リクエストライトバックがそのまま実行されるのみである。

４．まとめ
以上に説明されたように、本発明によれば、リクエストセルＣＲとホームセルＣＨとオーナーセルＣＯがそれぞれ異なる状態においても、コヒーレンシの保障とレイテンシの短縮が実現される。

リクエストセルＣＲからオーナーセルＣＯのキャッシュ７に対するアクセスが発生した場合、オーナーセルＣＯは、メインメモリ５へのライトバックと同時に、リクエストセルＣＲに最新データを返却する。これにより、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰで実現することが可能となる。

また、セルＣｊに搭載されるキャッシュコヒーレンシ回路３−ｊにスヌープ管理テーブル３１、ライトバック検出回路３２、及びディスカード判定回路３４を設けることにより、各セルＣｊには次の機能が提供される：（１）リクエストセルＣＲからのリードリクエストを登録する機能、（２）登録されたリードリクエストの対象と同じアドレスに対するリクエストライトバックを検出したときに、検出フラグを有効にする機能、（３）そのリクエストライトバックよりも後にリプライライトバックを受け取った場合、上記検出フラグを参照することによって、受け取ったリプライライトバックを破棄する機能、及び（４）リプライライトバックの破棄と共に、ディレクトリを更新する機能。これらの機能により、リクエストセルＣＲからのリクエストライトバックによって更新されたデータが、オーナーセルＣＯからのリプライライトバックによる古いデータで上書きされることが防止される。従って、リクエストライトバックとリプライライトバックの経路が異なっていても、コヒーレンシを保障することが可能となる。言い換えれば、オーナーセルＣＯがリプライデータＤＲ’を直接リクエストセルＣＲに送信しても、セル間のコヒーレンシが保たれる。

以上に説明されたように、本発明によれば、コヒーレンシを保障しつつ、リードリクエストの発行からリプライデータの受け取りまでのレイテンシを３ＨＯＰで実現することが可能となる。すなわち、コヒーレンシの保障とレイテンシの短縮（処理速度の向上）との両立が実現される。本発明は、リクエストセルＣＲとホームセルＣＨ間の距離（ＨＯＰ数）と、ホームセルＣＨとオーナーセルＣＯ間の距離が遠くなるような、大規模なマルチプロセッサシステムにおいては、さらに効果が大きくなる。

図１は、分散共有メモリ型マルチプロセッサシステムの構成を示すブロック図である。 図２は、従来のマルチプロセッサシステムの動作を示す概念図である。 図３は、従来のマルチプロセッサシステムの動作を示す概念図である。 図４は、本発明に係るマルチプロセッサシステムの動作を示す概念図である。 図５は、本発明の実施の形態に係るディレクトリに格納される情報の一例を示すテーブルである。 図６は、本実施の形態に係るキャッシュコヒーレンシ回路の構成を示すブロック図である。 図７は、本実施の形態に係るメインパイプ部の構成を示すブロック図である。 図８は、本実施の形態に係るスヌープ管理テーブルの一例を示すテーブルである。 図９は、本実施の形態に係るディレクトリの更新方法を要約的に示すテーブルである。 図１０は、本実施の形態に係るマルチプロセッサシステムの動作フローの一例を示す図である。 図１１は、キャッシュステータス、スヌープ管理テーブル、及びディレクトリに格納される情報の遷移を示すテーブルである。

符号の説明

１ 分散共有メモリ型マルチプロセッサシステム
２ ＣＰＵ
３ キャッシュコヒーレンシ回路
４ ディレクトリ
５ メインメモリ
７ キャッシュ
９ クロスバースイッチ
Ｃ セル
ＣＲ リクエストセル
ＣＨ ホームセル
ＣＯ オーナーセル
１０ ＣＰＵリクエスト制御部
２０ クロスバーリクエスト制御部
３０ メインパイプ部
３１ スヌープ管理テーブル
３１１ Ｖビット
３１２ アドレス情報
３１３ セル情報
３１４ ライトバック検出情報
３２ ライトバック検出回路
３２１ アドレス情報比較器
３２２ セル情報比較器
３２３ ＡＮＤ
３３ キャンセル判定回路
３４ ディスカード判定回路
３５ 調停制御回路
４０ ディレクトリアクセス制御部
５０ メインメモリアクセス制御部
６０ リプライデータ制御部

Claims (12)

1. 同一の機能を有する複数のセルと、
   前記複数のセル間を接続するネットワークと
   を具備し、
   前記複数のセルの各々は、プロセッサ、キャッシュメモリ、及びメインメモリを備え、
   前記複数のセルは、
   リクエストセルとしての第１セルと、
   ホームセルとしての第２セルと、
   オーナーセルとしての第３セルと
   を含み、
   前記第２セルの前記メインメモリに記憶された対象データの最新版は、前記第３セルの前記キャッシュメモリに格納され、
   前記第１セルは、前記対象データに対するリードリクエストを前記第２セルに発行し、
   前記第２セルは、前記リードリクエストに応答して、スヌープリクエストを前記第３セルに発行し、
   前記第３セルは、前記スヌープリクエストに応答して、前記対象データを前記第１セルに直接送信し、リプライライトバックを前記第２セルに送信し、
   前記第１セルは、前記第２セル中の前記対象データと同じアドレスに対してリクエストライトバックを発行し、
   前記第２セルは、前記第３セルからの前記リプライライトバックを前記第１セルからの前記リクエストライトバックよりも後に受信した場合、前記リプライライトバックを破棄する
   マルチプロセッサシステム。
2. 請求項１に記載のマルチプロセッサシステムであって、
   前記各々のセルは、更にディレクトリを備え、
   前記第１セルが発行する前記リクエストライトバックは、前記第１セルに含まれる前記キャッシュメモリのステータスと前記第２セルの前記ディレクトリのステータスとを整合させるためのディレクトリ更新情報を含み、
   前記第２セルは、前記リプライライトバックを前記リクエストライトバックよりも後に受信した場合、前記リプライライトバックを破棄すると共に、前記ディレクトリ更新情報に基づいて前記ディレクトリのステータスを更新する
   マルチプロセッサシステム。
3. 請求項２に記載のマルチプロセッサシステムであって
   前記各々のセルは、更にスヌープ管理テーブルを備え、
   前記リードリクエストは、当該リクエストの発行元を示すリクエストセル情報と、リード対象アドレスを示すアドレス情報とを含み、
   前記第２セルは、前記リードリクエストに応答して、前記リクエストセル情報と前記アドレス情報を前記スヌープ管理テーブルに登録する
   マルチプロセッサシステム。
4. 請求項３に記載のマルチプロセッサシステムであって、
   前記各々のセルは、更にライトバック検出回路を備え、
   前記スヌープ管理テーブルは、前記登録されたリクエストセル情報及びアドレス情報に対応付けられた検出フラグを有し、
   前記第２セルの前記ライトバック検出回路は、前記登録されたアドレス情報が示す前記リード対象アドレスと同じアドレスに対する前記リクエストライトバックを検出し、前記リクエストライトバックが検出された場合、前記検出フラグを有効にする
   マルチプロセッサシステム。
5. 請求項４に記載のマルチプロセッサシステムであって、
   前記リクエストライトバックは、当該リクエストの発行元を示すリクエストライトバックセル情報と、ライトバック対象アドレスを示すライトバックアドレス情報とを含み、
   前記第２セルの前記ライトバック検出回路は、前記リクエストライトバックセル情報及び前記ライトバックアドレス情報のそれぞれを、前記スヌープ管理テーブルに登録されたリクエストセル情報及びアドレス情報と比較することによって、前記リード対象アドレスと同じアドレスに対する前記リクエストライトバックを検出する
   マルチプロセッサシステム。
6. 請求項４又は５に記載のマルチプロセッサシステムであって、
   前記各々のセルは、更にディスカード判定回路を有し、
   前記第２セルの前記ディスカード判定回路は、前記第３セルからの前記リプライライトバックに応答して前記検出フラグを参照し、前記検出フラグが有効化されている場合、前記リプライライトバックを破棄する
   マルチプロセッサシステム。
7. 請求項６に記載のマルチプロセッサシステムであって、
   前記第２セルの前記ライトバック検出回路は、前記検出フラグを有効にすると共に、前記リクエストライトバックが示す前記ディレクトリ更新情報を、前記有効化された検出フラグと対応づけて前記スヌープ管理テーブルに格納し、
   前記第２セルの前記ディスカード判定回路は、前記第３セルからの前記リプライライトバックに応答して前記検出フラグと前記ディレクトリ更新情報を参照し、前記リプライライトバックを破棄すると共に、前記ディレクトリ更新情報に基づいて前記ディレクトリのステータスを更新させる
   マルチプロセッサシステム。
8. 請求項３乃至７のいずれかに記載のマルチプロセッサシステムであって、
   前記第２セルは、前記リプライライトバックに応答して、前記スヌープ管理テーブル中の前記登録されたリクエストセル情報とアドレス情報に対応するエントリを初期化する
   マルチプロセッサシステム。
9. 請求項２乃至８のいずれかに記載のマルチプロセッサシステムであって、
   前記ディレクトリには、自セルの前記メインメモリの全アドレスのデータに関して、最新のデータを有するセルを示す情報が含まれ、
   前記リードリクエストは、当該リクエストの発行元を示すリクエストセル情報と、リード対象アドレスを示すアドレス情報とを含み、
   前記第２セルは、前記リードリクエストに応答して前記ディレクトリを参照し、前記リード対象アドレスのデータの最新版が前記第３セルに格納されていることを認識し、前記スヌープリクエストを前記第３セルに発行する
   マルチプロセッサシステム。
10. 請求項９に記載のマルチプロセッサシステムであって、
    前記発行されたスヌープリクエストは、前記リードリクエストに含まれる情報を含み、
    前記第３セルは、前記スヌープリクエストに含まれる前記リクエストセル情報に基づいて、前記対象データの送信先が前記第１セルであることを認識し、前記キャッシュメモリから読みだされた前記対象データを前記第１セルに直接送信する
    マルチプロセッサシステム。
11. マルチプロセッサシステムの動作方法であって、
    前記マルチプロセッサシステムは、同一の機能を有する複数のセルを具備し、
    前記複数のセルの各々は、プロセッサ、キャッシュメモリ、及びメインメモリを備え、
    前記複数のセルは、
    リクエストセルとしての第１セルと、
    ホームセルとしての第２セルと、
    オーナーセルとしての第３セルと
    を含み、
    前記第２セルの前記メインメモリに記憶された対象データの最新版は、前記第３セルの前記キャッシュメモリに格納され、
    前記動作方法は、
    （Ａ）前記第１セルが、前記対象データに対するリードリクエストを前記第２セルに発行するステップと、
    （Ｂ）前記第２セルが、前記リードリクエストに応答して、スヌープリクエストを前記第３セルに発行するステップと、
    （Ｃ）前記第３セルが、前記スヌープリクエストに応答して、前記対象データを前記第１セルに直接送信するステップと、
    （Ｄ）前記第３セルが、前記スヌープリクエストに応答して、リプライライトバックを前記第２セルに発行するステップと、
    （Ｅ）前記第１セルが、前記第２セル中の前記対象データと同じアドレスに対してリクエストライトバックを発行するステップと、
    （Ｆ）前記第２セルが、前記第３セルからの前記リプライライトバックを前記第１セルからの前記リクエストライトバックよりも後に受信した場合、前記リプライライトバックを破棄するステップと
    を有する
    マルチプロセッサシステムの動作方法。
12. 請求項１１に記載のマルチプロセッサシステムの動作方法であって、
    前記各々のセルは、更にディレクトリを備え、
    前記（Ｅ）ステップにおいて、前記リクエストライトバックは、前記第１セルに含まれる前記キャッシュメモリのステータスと前記第２セルの前記ディレクトリのステータスとを整合させるためのディレクトリ更新情報を含み、
    前記（Ｆ）ステップにおいて、前記第２セルは、前記リプライライトバックを破棄すると共に、前記ディレクトリ更新情報に基づいて前記ディレクトリのステータスを更新する
    マルチプロセッサシステムの動作方法。

Images