(57)【特許請求の範囲】
【請求項１】
システムメモリと、
前記システムメモリと通信を行う第１のバスであって、前記第１のバスに接続され、前記システムメモリから取得した複数のデータ値を格納するように構成され、かつ前記データ値についてのキャッシュコヒーレンス情報を第１の一組のコヒーレンスステートと一緒に維持するように構成された少なくとも１つのキャッシュメモリを有する、第１のバスと、
前記第１のバスと通信を行うタグメモリであって、前記データ値に関連したコヒーレンスステータスを維持するように構成された、タグメモリと、
バストランザクションを送信することができ、前記システムメモリと通信を行う第２のバスと、
前記第２のバスおよび前記コヒーレンスステータスと通信を行うコヒーレンスフィルタであって、前記第１のバスと接続されておらず、前記第２のバス情報の前記バストランザクションを監視し、前記コヒーレンスステータスにもとづいて、前記第２のバスから前記第１のバスへのクロスバストランザクションを抑制し、クロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記コヒーレンスステータスが示す場合前記クロスバストランザクションを抑制することを含む、ように構成された、コヒーレンスフィルタと、
を備えることを特徴とするマルチバス多重処理システム。
【請求項２】
第１のバスに接続されたキャッシュユニットに存在する第１の複数のデータ値に関連したキャッシュステータス情報を維持し、
前記第１の複数のデータ値に関連し、第１バスコヒーレンスステータスを維持し、
前記第１のバスのバストランザクションを第１のコヒーレンスフィルタで監視し、
第２のバスのバストランザクションを第２のコヒーレンスフィルタで監視し、
バストランザクションを第２のバスで送信し、
クロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことが前記第１バスコヒーレンスステータスによって示される場合に、前記第２のバスから前記第１のバスへの前記クロスバストランザクションを前記第２のコヒーレンスフィルタで抑制する、
ことを含む、マルチバスシステムにおいてキャッシュコヒーレンスを維持するための方法。
【請求項３】
システムメモリと、
前記システムメモリと通信を行うシステムバスであって、前記システムバスに接続され、前記システムメモリから取得した複数のデータ値を格納するように構成された少なくとも１つのキャッシュメモリを有し、多重バストランザクションを送信することができる、システムバスと、
前記システムバスと通信を行うタグメモリであって、前記データ値に関連したシステムバスコヒーレンスステータスを維持するように構成された、タグメモリと、
多重バストランザクションを送信することができ、前記システムメモリと通信を行う入力／出力バスと、
前記入力／出力バスおよび前記タグメモリと通信を行う入力／出力コヒーレンスフィルタであって、前記入力／出力バス上のバストランザクションを監視するが、前記システムバス上のバストランザクションを監視しないように構成され、さらに、前記システムバスコヒーレンスステータスにもとづいて、前記入力／出力バスから前記システムバスへのクロスバストランザクションを抑制し、クロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記システムバスコヒーレンスステータスが示す場合前記クロスバストランザクションを抑制することを含む、ように構成された、入力／出力コヒーレンスフィルタと、
を備えることを特徴とするマルチバス多重処理システム。
【請求項４】
システムバスに接続されたキャッシュユニットに存在する第１の複数のデータ値に関連したキャッシュステータス情報であって、第１の一組のコヒーレンスステートにもとづくキャッシュステータス情報を維持し、
前記第１の複数のデータ値に関連するコヒーレンスステータスを維持し、
前記システムバス上のバストランザクションを第１のコヒーレンスフィルタで監視し、
入力／出力バス上のバストランザクションを第２のコヒーレンスフィルタで監視し、
バストランザクションを前記入力／出力バス上に送信し、
前記クロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記コヒーレンスステータスが示す場合に、前記入力／出力バスから前記システムバスへの前記クロスバストランザクションを前記第２のコヒーレンスフィルタで抑制する、
ことを含む、マルチバスシステムにおいてキャッシュコヒーレンスを維持するための方法。
【請求項５】
システムメモリと、
前記システムメモリと通信を行う第１のシステムバスおよび第２のシステムバスであって、前記第１のシステムバスに接続され、および、前記第２のシステムバスに接続され、前記システムメモリから取得した複数のデータ値を格納するように構成された少なくとも１つのキャッシュメモリを有する、第１のシステムバスおよび第２のシステムバスと、
前記第１のシステムバスと通信を行う第１のタグメモリであって、前記第１のシステムバスに接続された前記キャッシュユニット内の前記データ値に関連した第１のコヒーレンスステータスを維持するように構成された、第１のタグメモリと、
前記第２のシステムバスと通信を行う第２のタグメモリであって、前記第２のシステムバスに接続された前記キャッシュメモリにおける前記データ値に関連した第２のコヒーレンスステータスを維持するように構成された、第２のタグメモリと、
前記第１のシステムバスおよび前記第２のタグメモリと通信を行う第１のコヒーレンスフィルタであって、前記第１のシステムバス上のバストランザクションを監視し、前記第２のコヒーレンスステータスにもとづいて、前記第１のシステムバスから前記第２のシステムバスへのクロスバストランザクションを抑制し、第１のクロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記第２のコヒーレンスステータスが示す場合前記第１のシステムバスから第２のシステムバスへの前記第１のクロスバストランザクションを抑制することを含む、ように構成された、第１のコヒーレンスフィルタと、
前記第２のシステムバスおよび前記第１のタグメモリと通信を行う第２のコヒーレンスフィルタであって、前記第２のシステムバス上のバストランザクションを監視し、前記第１のコヒーレンスステータスにもとづいて、前記第２のシステムバスから前記第１のシステムバスへのクロスバストランザクションを抑制する、第２のコヒーレンスフィルタと、
を備えることを特徴とするマルチバス多重処理システム。
【請求項６】
システムメモリと、
前記システムメモリと通信を行う第１のバスおよび第２のバスであって、前記第１のバスに接続され、および、前記第２のバスに接続され、前記システムメモリから取得した複数のデータ値を格納するように構成され、かつ、前記データ値についてのキャッシュコヒーレンス情報を維持するように構成された少なくとも１つのキャッシュメモリを有する、第１のバスおよび第２のバスと、
前記第１のバスに関連した前記データ値の第１のコヒーレンスステータスを維持するための第１のタグメモリ手段と、
前記第２のバスに関連した前記データ値の第２のコヒーレンスステータスを維持するための第２のタグメモリ手段と、
前記第１のバス上のバストランザクションを監視し、前記第２のコヒーレンスステータスにもとづいて前記第１のバスから前記第２のバスへのクロスバストランザクションを抑制し、第１のクロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記第２のコヒーレンスステータスが示す場合前記第１のバスから第２のバスへの前記第１のクロスバストランザクションを抑制する、第１のコヒーレンスフィルタ手段と、
前記第２のバス上のバストランザクションを監視し、前記第１のコヒーレンスステータスにもとづいて前記第１のバスから前記第２のバスへのクロスバストランザクションを抑制するための第２のコヒーレンスフィルタ手段と、
を備えることを特徴とするマルチバス多重処理システム。
【請求項７】
システムメモリと、
前記システムメモリと通信を行う第１のバスであって、前記第１のバスに接続され、前記システムメモリから取得した複数のデータ値を格納するように構成され、かつ、前記データ値についてのコヒーレンスステータス情報を維持するように構成された少なくとも１つのキャッシュメモリを有する、第１のバスと、
前記第１のバスと通信を行うタグメモリであって、前記データ値に関連したコヒーレンスステータスを、第１の一組のコヒーレンスステートとは異なる第２の一組のコヒーレンスステートと一緒に維持するように構成された、タグメモリと、
バストランザクションを送信することができ、前記システムメモリと通信を行う第２のバスと、
前記第２のバスおよび前記タグメモリと通信を行うコヒーレンスフィルタであって、前記第１のバス上のバストランザクションは監視しないが、前記第２のバス上のバストランザクションを監視するように構成され、さらに、前記コヒーレンスステータスにもとづいて、前記第２のバスから前記第１のバスへのクロスバストランザクションを抑制し、第１のクロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記コヒーレンスステータスが示す場合前記第２のバスから第１のバスへの前記第１のクロスバストランザクションを抑制することを含む、ように構成された、コヒーレンスフィルタと、
を備えることを特徴とするマルチバス多重処理システム。
【請求項８】
第１のバスに接続されたキャッシュユニットに存在する第１の複数のデータ値に関連したキャシュステータス情報であって、
第１の一組のコヒーレンスステートにもとづくキャッシュステータス情報を維持し、
前記データ値に関連し、前記第１の一組のコヒーレンスステートとは異なる第２の一組のコヒーレンスステートにもとづくコヒーレンスステータスを維持し、
前記第１のバス上のバストランザクションを、第１のコヒーレンスフィルタで監視し、
第２のバス上のバストランザクションを、第２のコヒーレンスフィルタで監視し、
バストランザクションを前記第２のバス上に送信し、
前記クロスバストランザクションの抑制がメモリのインコヒーレンスを生じないことを前記コヒーレンスステータスが示す場合に、前記第２のバスから前記第１のバスへの前記クロスバストランザクションを前記第２のコヒーレンスフィルタで抑制する、
ことを含む、マルチバスシステムにおいてキャッシュコヒーレンスを維持するための方法。
【発明の詳細な説明】
発明の背景
１つしか中央処理装置を持たないコンピュータのパフォーマンスを改善するために、コンピュータ設計者らは多くの中央処理装置を備えたコンピュータを開発している。多くの場合、このような多重処理コンピュータの中央処理装置は、１本の共通バスを介して互いに接続され、システムの主記憶装置にも接続されている。しかしながら、近年になって中央処理装置のパフォーマンスが改善され、バスパフォーマンステクノロジよりも高速化している。内部の中央処理装置のパフォーマンスの方が高速になることで、さらに外側の帯域幅を使わなければならなくなる。すなわち、共通バスで送信されるデータ量を多くして、中央処理パフォーマンスの向上分をカバーしなければならない。この結果、中央処理装置をサポートするのに必要な帯域幅と共通バスの全帯域幅とによって、共通バスに接続できる中央処理装置の数が制約されてしまうことになる。
多重処理システムにおける各プロセッサによって必要とされるバス帯域幅を減らす方法の１つは、各プロセッサと共通バスとの間にキャッシュユニットを設けることである。キャッシュユニットに接続されたプロセッサにデータをいったんロードしてしまえば、プロセッサは共通バスを使用しなくてもキャッシュユニット内にあるデータにアクセスすることができる。通常、プロセッサがそのキャッシュユニットからデータを取得すれば、共通バスの限られた帯域幅を使って送信されるデータ量は少なくなる。
多くの場合、プロセッサは特定のデータ値を何度も変更するため、データ値が変更されるたびにそのデータ値を主記憶装置に書き戻す必要が生じる。しかしながら、変更後のデータ値を主記憶装置に書き戻すことで、プロセッサをサポートするのに必要なバス帯域幅の量は多くなる。したがって、書込み動作回数を減らすことができれば、プロセッサをサポートするために必要なバス帯域幅も狭くすることができる。
書込み動作回数を減らす一種のキャッシュユニットは、「ライトバック」キャッシュと呼ばれている。ライトバックキャッシュは変更後のデータ値を一時的に格納することで、データ値を主記憶装置に書き戻すのに必要なバストランザクション数を削減している。例えば、プロセッサは、データを主記憶装置に書き戻すことなくライトバックキャッシュ内のデータ値を何度も変更することができる。ライトバックキャッシュによって、変更後のデータを最終的に主記憶装置に書き戻せばよいことになる。
ライトバックキャッシュは多重処理システムで必要とされるバスの全帯域幅の削減には極めて有効なものとなり得るが、残念なことにライトバックキャッシュを用いるとメモリコヒーレンスの問題が生じる。例えば、各ライトバックキャッシュはそれぞれ独自にデータ値のコピーを含む。このような状況で、２つ以上のプロセッサが独立にデータ値を変更すると、２つ以上のライトバックキャッシュに同一のデータ値に対して異なるバージョンが存在してしまう可能性がある。これによって誤った動作が発生することもあり、結果として、全てのプロセッサが常に全てのデータ値を一貫して見ている形を必須とするメカニズムがでてくる。
例えば、プロセッサがデータ値を変更すると、変更後のデータ値は主記憶装置に書き戻されるまではライトバックキャッシュ内に存在する。この例では、ライトバックキャッシュが変更後のデータ値を主記憶装置に書き戻すまで、主記憶装置および他のキャッシュユニットではデータ値の古いコピーを持っている。しかしながら、データの完全性を維持するためには、他のプロセッサでそのデータ値を要求する際には古いデータ値ではなく最新バージョンのデータ値を入手できなければならない。
全てのプロセッサが全てのデータ値を一貫して見るように保証するプロセスは、キャッシュコヒーレンスと呼ばれている。キャッシュコヒーレンスを達成するための評判が良く成功している方法の組み合わせの１つでは、「スヌーピング動作」と呼ばれるものに依存している。スヌーピング動作には様々なものが存在するが、基本的に、キャッシュユニットにおけるスヌーピング動作では、共通バスでのバストランザクションを監視している。スヌーピング動作は、どのトランザクションがキャッシュユニットの中身に影響するか、あるいはどのトランザクションがキャッシュユニット内に存在する変更後のデータと関連しているかを識別する。一般に、スヌーピング動作を行うには、全てのプロセッサおよびこれに接続されたキャッシュユニットが共通バスを共有している必要がある。共通バスを共有することで、キャッシュユニットはバストランザクションを監視して、特定のキャッシュユニットが変更後のデータ値を含む場合に潜在的にバストランザクションを妨害することができる。
キャッシュコヒーレンス方法では一般に、キャッシュユニット内の特定のデータ値が、無効、変更、共有、排他所有などステートか否かを示すコヒーレンスステータス情報も利用している。多くのキャッシュコヒーレンス方法が存在するが、一般的な２つのバージョンとしてＭＥＳＩキャッシュコヒーレンスプロトコルおよびＭＯＥＳＩキャッシュコヒーレンスプロトコルが挙げられる。ＭＥＳＩの頭文字は、変更（Ｍｏｄｉｆｉｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）および無効（Ｉｎｖａｌｉｄ）ステータスを示し、ＭＯＥＳＩの頭文字は、変更（Ｍｏｄｉｆｉｅｄ）、所有（Ｏｗｎｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）および無効（Ｉｎｖａｌｉｄ）ステートを意味する。
ステートの意味は実施の仕方によって様々である。概して、変更ステートは、通常は特定のキャッシュユニットに変更された特定のデータ値があることを意味する。排他ステートおよび所有ステートは、通常は特定のキャッシュユニットがデータ値のコピーを変更できることを意味する。共有ステートは通常、データ値のコピーが異なるキャッシュユニットに存在することを意味し、無効ステートはキャッシュユニット内のデータ値が無効であることを意味する。
動作時、キャッシュユニットはバスの動作をスヌープし、コヒーレンスステータス情報を使用してキャッシュコヒーレンスを保証する。例えば、第１のキャッシュユニットを有する第１のプロセッサが特定のデータ値を得ることを望んでいると仮定する。さらに、第２のキャッシュユニットを有する第２のプロセッサが、そのデータ値の変更後のバージョンを有していると仮定する（コヒーレンスステータス情報は第２のキャッシュユニット内のデータ値が変更ステートであることを示している）。
この例では、第１のプロセッサがリードバスリクエストを開始してデータ値を取得する。第２のキャッシュユニットは、リードバスリクエストをスヌープし、これがデータ値の変更後のバージョンを含むか否かを判断する。次に、第２のキャッシュユニットが介在し、変更後のデータ値を共通バス経由で第１のプロセッサに送信する。システムによって、変更後のデータ値を同時に主記憶装置に書き込むことができる場合とそうでない場合とがある。
もう１つの例では、第１のプロセッサが特定のデータ値を独占所有することを望んでいると仮定する。さらに、第２のキャッシュユニットが、データ値の未変更共有のコピーを持っていると仮定する（コヒーレンスステータス情報は、第２のキャッシュユニット内のデータ値が共有ステートであることを示している）。この例では、第１のプロセッサがリードバスリクエストを開始し、データの独占使用を要求する。
第２のキャッシュユニットはリードバスリクエストをスヌープし、データ値の共有のコピーが含まれていると判断する。次に、第２のキャッシュユニットは、データ値のコヒーレンスステータス情報を無効ステートに変えることでその共有のデータ値を無効にする。データ値のコヒーレンスステータスを無効ステートにすると、第２のキャッシュユニット内のデータ値は無効になる。次に、第１のプロセッサがリードバスリクエストを完了し、独占使用するために主記憶装置からデータ値のコピーを取得する。
スヌーピング動作では、１本の共通バスを有する多重処理システムのキャッシュコヒーレンスが維持されるが、さらに強力なコンピュータでは、各々主記憶装置と複数のプロセッサとを相互接続するバスが２本以上含まれている。しかしながら、共通バスではサポートできるプロセッサの数の制約が次第に大きくなってきているため、マルチバスシステムで所望のパフォーマンスレベルを達成する必要が生じることがある。複数のバスに関連した問題は、１つのバス上のプロセッサでは、他のバス上のプロセッサによって開始されたトランザクションを監視できないということである。この結果、スヌーピング動作によってマルチバスコンピュータでのメモリコヒーレンスを維持することはできなくなる。
マルチバスシステムにおいてキャッシュコヒーレンスを維持する方法の１つに、各バスが開始したバストランザクションを他の全てのバスに同報通信するものがある。残念なことに、この手法では、各バスに送信される全てのバスのバス帯域幅負荷が一緒になってしまう。当然ながら、これによってシステムパフォーマンスは大幅に落ち、複数のバスを用いることによる利点はなくなってしまう。
第２の方法は、いわゆるディレクトリベースのキャッシュコヒーレンス方法と呼ばれるものに基づいている。ＩＥＥＥ  Ｓｃａｌｅａｂｌｅ  Ｃｏｈｅｒｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔがマルチバスディレクトリベースのキャッシュコヒーレンスシステムの一例である。ディレクトリスキームでは、プロセッサはバストランザクションのスヌープを行わない。代わりに、主記憶装置のサブシステムが実データと一緒に付加情報を格納することによってメモリコヒーレンスを維持する。
主記憶装置サブシステム内の付加情報は一般に、１）どのプロセッサ（単数又は複数）がデータ値を取得したかということと、２）データ値のコヒーレンスステータスとを示している。例えば、２つ以上のプロセッサが同一のデータ値を共有していることを付加情報によって示すことができる。さらに他の例では、特定のデータ値を変更するのに適したプロセッサは１つしかないことを付加情報によって示すことができる。
プロセッサがデータ値を要求すると、主記憶装置サブシステムはそれが最新バージョンのデータ値であるか否かを判断する。最新バージョンではない場合には、主記憶装置サブシステムは、最新のデータ値を持っているプロセッサから要求を出しているプロセッサにこの最新のデータ値を転送する。あるいは、主記憶装置は要求を出しているプロセッサに対して他のプロセッサのうちどれが最新のデータ値を持っているか示すこともできる。
各データ値の最新バージョンの位置に関する情報が主記憶装置サブシステムによって維持されているため、プロセッサではバストランザクションを「スヌープ」する必要がない。しかしながら、このようなディレクトリを維持することで、各データ値について主記憶装置に保持しなければならない追加情報が出てくるため、システムに多額なコストが上乗せになる可能性がある。さらに、各データ値について主記憶装置内にディレクトリを維持することで、要求されたデータの位置を見極め、要求を出しているプロセッサに対してこれを転送するのに必要な時間が原因でシステムパフォーマンスが落ちる可能性もある。
ディレクトリベースのシステムに代わるものの１つが、実際にはキャッシュユニットに格納されているデータ値に関連するコヒーレンスステータス情報を格納するバス相互接続である。このように、（ディレクトリベースのスキームのように）主記憶装置も比例的に増大させる形の格納方法をとるのではなく、サイズがかなり小さいキャッシュユニットの組み合わせにのみ格納量を関連させる。しかしながら、この方法では、各キャッシュユニット内の全てのデータ値に関連するコヒーレンスステータス情報の複製をマルチバスシステムに格納する必要がある。
例えば、サンマイクロシステムのＵｌｔｒａＳｐａｒｃシステムでは、複数のバスを相互接続するためのバススイッチを利用している。このシステムでは、各バスが内部キャッシュユニットを有するプロセッサと通信を行う。バススイッチは、キャッシュユニット内の全てのデータ値に関連したコヒーレンスステータス情報の複製を維持する。ＵｌｔｒａＳｐａｒｃシステムでは、ＵｌｔｒａＳｐａｒｃシステムのプロセッサがそのデータ値が置き換えられたかに関する正確な情報を提供し、外部キャッシュタグを維持できるように構成されているため、バススイッチでコヒーレンスステータス情報の複製を維持することができる。
しかしながら、このようなバススイッチは、多くの既成プロセッサでは実現することができない。これらのプロセッサは正確なキャッシュデータ置き換え情報を出力しないためである。例えば、多くの従来のプロセッサは正確なコヒーレンスステータス情報を自己の内部キャッシュユニット内でのみ維持する。このため、その他の装置では内部キャッシュユニットからデータ値が削除されるのがいつであるかを判断することはできない。内部キャッシュユニット内のコヒーレンスステータス情報についての正確な情報がなければ、バススイッチはコヒーレンスステータス情報の複製を維持することができない。
発明の開示
本発明によれば、シングルバスシステムのプロセッサの全パフォーマンス制限を効率的に増やすキャッシュコヒーレントなマルチバスシステムが得られる。本発明では、マルチバス式多重処理システムは、１）複数のシステムバスおよび複数のＩ／Ｏ装置を共有の主記憶装置に相互接続し、２）システム内での待ち時間および全帯域幅に対する影響を最小限に抑えつつキャッシュコヒーレンスを効果的に維持する、待ち時間が少なく帯域幅の広いシステムを必要とすると考えている。本発明では、クロスバストラフィックにおけるオーバーヘッドを減らしながらキャッシュのメモリコヒーレンスを維持するような形でバス対バスの通信のコーディネートを可能にする「コヒーレンスフィルタ」を用いて上記の問題に取り組む。
本発明の好ましい実施の形態では、システムバス、Ｉ／Ｏバスおよび記憶素子をマルチポートバススイッチ経由で接続する。このバススイッチは、あらゆるシステムバスまたはＩ／Ｏバスとあらゆるメモリユニットとを接続するだけでなく、クロスバストラフィックもハンドリングする。また、好ましいバススイッチは、バストランザクションに応答するのに必要な１つまたは複数の動作を判断するバスインタフェース論理を含む。しかしながら、本発明はこのようなマルチポートバススイッチに限定されるものではなく、異なるデータパス用に別々のバスブリッジが存在する場合など、様々な他のバス相互接続においても利用可能である。
マルチバス多重処理システムにおけるキャッシュコヒーレンスを保証するために、キャッシュをサポートする各バスが割り当てられたコヒーレンスフィルタを有する。各コヒーレンスフィルタは、タグコントローラと、サイクルエンコーダと、ルールテーブルとを含む。また、各コヒーレンスフィルタはタグメモリに接続されている。一般的に、各タグコントローラは全てのタグメモリとの間をインタフェースする。各サイクルエンコーダは、どのような種類のバストランザクションがサイクルエンコーダの割り当てられたバスにおいて発生しているかを判断し、キャッシュコヒーレンスを維持するために必要なバストランザクションがどれであるのかの判断は各ルールテーブルによって行われる。
ここで、タグメモリに注目すると、各タグメモリは、１）タグメモリの割り当てられたバスに接続されたキャッシュユニット内に位置しているデータ値のアドレスと、２）データ値に関連したキャッシュコヒーレンスステータスのレコードを維持する。周知のように、主記憶装置内の各データ値は、対応するメモリアドレスによって識別される。好ましい実施の形態では、タグメモリはデータ値のアドレスを格納し、実データ値ではなくこのアドレスによってデータ値を識別する。データ値のアドレスを格納することに加え、好ましいタグメモリはデータ値のアドレスに関連したコヒーレンスステータス情報も格納する。
例えば、第１のコヒーレンスフィルタおよび第１のタグメモリが第１のバスに割り当てられていると仮定する。さらに、第１のバス上の第１のプロセッサが主記憶装置からのデータ値を要求すると仮定する。第１のコヒーレンスフィルタは、第１のタグメモリ内のメモリアドレスのレコードを維持する。さらに、第１のコヒーレンスフィルタは、第１のタグメモリ内のメモリアドレスに関連したコヒーレンスステータス情報を格納する。
メモリトランザクションにおいてアクセスされるデータ量はシステムごとに異なる。従来の大半のシステムでは、プロセッサがメモリリードトランザクションを実施する際に、このプロセッサが自プロセッサの内部キャッシュメモリの一部を埋めるのに十分なメモリにアクセスする。通常、内部キャッシュメモリはいわゆるキャッシュラインと呼ばれている部分に複数のデータ値を格納する。
周知のように、従来のコンピュータ処理システムのメモリは、８ビットの量（バイト）、１６ビットの量（ワード）および３２ビットの量（ダブルワード）に分割されている。現在の多くの３２ビットプロセッサでは、主記憶装置はダブルワード（３２ビット）の境界に編成されている。大半の３２ビットプロセッサでは、各キャッシュラインは複数のダブルワードを保持することができる。
一般に、プロセッサがデータ値を要求すると、このプロセッサは全体のキャッシュラインを埋めるのに十分なデータを取得する。例えば、Ｐｅｎｔｉｕｍ  Ｐｒｏプロセッサでは、各内部データ値の大きさは様々であるが、この大きさが６４ビットを超えることはない。しかしながら、Ｐｅｎｔｉｕｍ  Ｐｒｏのキャッシュラインでは３２バイトのデータ（２５６ビット）を保持している。Ｐｅｎｔｉｕｍ  Ｐｒｏプロセッサで主記憶装置からデータ値を取得したい場合、そのキャッシュラインのうちの１本を埋めるのに必要な８つのデータ値（２５６ビット）を取得するのが普通である。
従来のシステムでは、各キャッシュラインはキャッシュラインアドレスによって識別されている。例えば、Ｐｅｎｔｉｕｍ  Ｐｒｏシステムでは、キャッシュラインはキャッシュライン内の最下位のデータ値のメモリアドレスと同一のキャッシュラインアドレスを有する。しかしながら、各キャッシュラインは３２バイトのデータを含むため、各キャッシュラインのキャッシュラインアドレスの方が短く、下位５つのアドレスビットが含まれない。好ましい実施の形態では、特定のバスに割り当てられた各タグメモリがキャッシュラインアドレスを格納する。
キャッシュラインアドレスを格納することに加え、各タグメモリはキャッシュラインアドレスに関連したコヒーレンスステータスも格納する。コヒーレンスステータスは、キャッシュユニットにおけるキャッシュラインのステータスに関するものである。好ましい実施の形態では、コヒーレンスステータスは３種類のコヒーレンスステートすなわち、無効ステート、共有ステートまたは所有ステートを含む。
無効ステートは、キャッシュラインが無効であり、キャッシュラインを格納するキャッシュエントリが空で新たなキャッシュラインを格納できることを意味する。共有ステートは、プロセッサがキャッシュラインのコピーを持っているが、変更権はないことを意味する。共有キャッシュラインは、例えば、変更されないプログラム指示または殆どの場合が読み込みだけであるデータ項目などであることが多い。所有ステートは、キャッシュラインを取得したプロセッサによってこのキャッシュラインを変更可能であることを意味する。
しかしながら、キャッシュラインのコヒーレンスステータスは、無効、共有および所有プロトコルに限定されるものではないことは、当業者であれば明らかであろう。実際に、当業者であれば、変更（Ｍｏｄｉｆｉｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）、および無効（Ｉｎｖａｌｉｄ）（ＭＥＳＩ）プロトコル、変更（Ｍｏｄｉｆｉｅｄ）、所有（Ｏｗｎｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）および無効（Ｉｎｖａｌｉｄ）（ＭＯＥＳＩ）プロトコル、変更（Ｍｏｄｉｆｉｅｄ）、共有（Ｓｈａｒｅｄ）、無効（Ｉｎｖａｌｉｄ）（ＭＳＩ）プロトコル、二ステート無効および所有プロトコル、Ｂｅｒｋｅｌｅｙプロトコル、イリノイ大学コヒーレンスプロトコル、Ｄｉｇｉｔａｌ  Ｅｑｕｉｐｍｅｎｔ’ｓ  Ｆｉｒｅｆｌｙプロトコル、Ｘｅｒｏｘ  Ｄｒａｇｏｎプロトコルなどの様々なコヒーレンスプロトコルでコヒーレンスステータスを実施できることは理解できよう。好ましい実施の形態では、無効、共有および所有を利用する。これは、ＭＥＳＩプロトコルを利用しているＰｅｎｔｉｕｍ  Ｐｒｏプロセッサと効率的にインタフェースする機能を有しているためである。
従来の多くのプロセッサでは、プロセッサは、内部キャッシュユニット内に格納されたキャッシュラインに関しての正確なコヒーレンスステータス情報を出力しない内部キャッシュユニットを有する。例えば、内部キャッシュユニットは、変更されていないキャッシュラインをそのキャッシュラインが放棄されたことを信号通知せずにこれを放棄することができる。もう１つの例では、内部キャッシュユニットは、キャッシュユニットが変更を行わない変更特権を有するキャッシュラインを取得できる。この例では、キャッシュユニットは、キャッシュラインが放棄されたことを信号通知せずにそのキャッシュラインを放棄することができる。この結果、キャッシュユニットを監視しているデバイスは、キャッシュラインが実際には放棄されたものである場合にキャッシュユニットはそれをキャッシュラインの変更されたコピーであると誤解する。しかしながら、本発明の好ましい実施の形態では、各タグメモリを独自に適合させ、現在のコヒーレンスステータス情報を出力しない内部キャッシュユニット用のキャッシュコヒーレンスを保証する。
本発明の重要な態様は、内部キャッシュユニットに現在保持されている可能性があるキャッシュラインアドレスの上位集合を維持することによって、各タグメモリがキャッシュコヒーレンスを保証することである。このように、キャッシュユニットが実際に放棄されたキャッシュラインを有する場合に、タグメモリにおけるキャッシュラインアドレスの上位集合によってキャッシュユニット内の特定のキャッシュラインが共有ステートであることを示すことができる。他の場合においては、キャッシュユニットが実際に主記憶装置に書き戻されたキャッシュラインを有する場合に、タグメモリにおけるキャッシュラインアドレスの上位集合によってキャッシュユニット内の特定のキャッシュラインが変更されたステートであることを示すことができる。
キャッシュラインアドレスの上位集合を維持するために、好ましいコヒーレンスフィルタではいわゆるインクルージョンルールと呼ばれているものを利用している。インクルージョンルールは、特定のバスに接続されたキャッシュユニットに格納されたキャッシュラインアドレスが常にそのバスに割り当てられたタグメモリのキャッシュラインアドレスの上位集合であることを保証する。各コヒーレンスフィルタは自己と接続されたバスによってアクセスされる全てのキャッシュラインを監視しているため、アクセスされた各キャッシュラインに関連したアドレスは、バスに割り当てられたタグメモリ内に維持される。キャッシュラインアドレスを複数のタグメモリのうちの１つから削除しなければならない場合、インクルージョンルールでは関連したキャッシュユニットに対して自己のキャッシュメモリからそのキャッシュラインを削除するように指示をする。
例えば、タグメモリが新たなキャッシュラインアドレスを保持するだけのメモリ容量を持たない場合、タグメモリから既存のキャッシュラインアドレス（古いキャッシュラインアドレス）のうちの１つを追い出してタグメモリに新たなキャッシュラインアドレス用の空間を作成しなければならない。古いキャッシュラインアドレスが無効ステートであれば、バスに接続されたキャッシュユニットは、古いキャッシュアドレス）に関連したキャッシュラインをもう使用してはおらず、タグメモリに割り当てられたコヒーレンスフィルタは単に古いキャッシュラインアドレスを新たなキャッシュラインアドレスで置き換えるのみである。
しかしながら、古いキャッシュラインアドレスが共有または所有ステートである場合には、コヒーレンスフィルタはキャッシュユニットが古いキャッシュラインアドレスを無効にするまでは古いキャッシュラインアドレスをタグメモリから追い出すことができない。上述したように、好ましいタグメモリはキャッシュラインアドレスの上位集合を維持するため、キャッシュユニットにおいて古いキャッシュラインアドレスをまず無効にし、その後であれば古いキャッシュラインアドレスを新たなキャッシュラインアドレスで置き換えることができる。
コヒーレンスフィルタは、無効バストランザクションを行ってキャッシュユニット内の古いキャッシュラインアドレスを無効にする。無効バストランザクションは、バスに接続されたキャッシュユニットに最初に古いキャッシュラインアドレスおよびこれに接続されたキャッシュラインを無効にするように指示する。
例えば、第１のキャッシュユニットを有する第１のプロセッサおよび第２のキャッシュユニットを有する第２のプロセッサが、割り当てられたコヒーレンスフィルタおよびタグメモリを有する第１のバスに接続されていると仮定する。さらに、第１のキャッシュユニットが共有ステートで第１のキャッシュラインを含むと仮定する。この例では、タグメモリは第１のキャッシュラインアドレスおよび共有ステータス情報を含む。また、第２のプロセッサが、第２のキャッシュラインを要求するリードバストランザクションを開始すると仮定する。最後に、タグメモリには第２のキャッシュラインアドレスにあてるだけのメモリ容量がないと仮定する。
この例では、コヒーレンスフィルタは第１のキャッシュラインアドレスを追い出して第２のキャッシュラインアドレス用の空間を確保する必要がある。しかしながら、コヒーレンスフィルタが第１のキャッシュラインアドレスを追い出すことができるようになる前に、コヒーレンスフィルタは第１のキャッシュユニット内にある第１のキャッシュラインアドレスを無効にするバストランザクションを行わなければならない。第１のキャッシュアドレス線を無効にするために、コヒーレンスフィルタは無効バストランザクションを行い、第１のキャッシュユニットに対して第１のキャッシュラインアドレスに関連したキャッシュラインを無効にするよう指示をする。
無効バストランザクションを行っている間、コヒーレンスフィルタは第２のキャッシュラインアドレスに対するリードバストランザクションを一時停止する。第１のキャッシュラインアドレスが共有ステートにある（第１のキャッシュラインは変更されていない）ため、第１のキャッシュユニットは無効バストランザクションに応答し、第１のキャッシュラインを無効にする。無効バストランザクションの終了後、コヒーレンスフィルタはタグメモリ内の第１のキャッシュラインアドレスを第２のキャッシュラインアドレスと置き換える。
しかしながら、場合によっては、第１のキャッシュユニットによって第１のキャッシュラインを変更（すなわち、第１のキャッシュラインが所有ステートにある）されている可能性もある。第１のキャッシュラインが所有ステートにある場合、第１のコヒーレンスフィルタはここでも無効バストランザクションを行い、第１のキャッシュラインを無効にする。しかしながら、第１のキャッシュユニットが第１のキャッシュラインを変更していた場合、第１のキャッシュユニットは、変更された第１のキャッシュラインを主記憶装置に書き戻すライトバストランザクションを行って無効バストランザクションに応答する。
変更後の第１のキャッシュラインを主記憶装置に書き戻した後、第１のキャッシュユニットが第１のキャッシュラインを無効にする。次にコヒーレンスフィルタがタグメモリ内の第１のキャッシュラインアドレスを第２のキャッシュラインアドレスと置き換える。このため、場合によっては、キャッシュラインアドレスの上位集合をタグメモリ内に維持するためにキャッシュユニットで変更後のデータを主記憶装置に書き戻した後で、タグメモリ内のキャッシュラインを無効にしなければならないこともある。
好ましい実施の形態では、各コヒーレンスフィルタがダイレクトマッピング手法を用いてタグメモリにキャッシュラインアドレスを格納する。ダイレクトマッピング手法は、各キャッシュラインアドレスをタグメモリ内の特定のタグエントリにマッピングするよう指定する。好ましい実施の形態ではダイレクトマッピング手法を用いるが、様々な異なる手法を用いてタグメモリ内にキャッシュラインアドレスを編成できることは当業者であれば理解できよう。例えば、ダイレクトマッピング手法の代わりに、タグメモリで完全アソシアティブ方式のマッピング手法を用いることもできる。完全アソシアティブ方式のシステムでは、任意のキャッシュラインアドレスを任意のタグエントリに存在させることができる。他の実施の形態では、各キャッシュラインアドレスを格納することができるのは２つの異なるタグエントリのうち１つのみである（２ウェイセットアソシアティブ）か、または異なる４つのタグエントリのうちの１つ（４ウェイセットアソシアティブ）などである。
ここで、好ましい実施の形態のダイレクトマッピング手法に注目すると、各キャッシュラインアドレスを特定のタグエントリの識別用インデックスとして用いる。好ましい実施の形態では、１つのタグメモリにおけるエントリ数がいわゆるタグページと呼ばれているものの大きさを規定する。好ましくは、各システムバスに接続されたタグメモリのタグページサイズは同一である。タグページサイズは、プロセッサのキャッシュ内の全キャッシュメモリ量と関連している。さらに、一般にはＩ／Ｏブリッジに接続されているキャッシュユニットが小さいため、Ｉ／Ｏバスに接続されたタグメモリの方が小さい。
タグページは主記憶装置のページと混同されてはならない。従来技術において周知のように、コンピュータの物理的なメモリアドレス空間はメモリページと呼ばれる複数のセクションに概念的に編成可能である。この場合、各メモリページが複数のキャッシュラインを含む。メモリページは処理システムによって定義され、タグページからは独立している。
好ましい実施の形態では、キャッシュラインアドレスは、１）キャッシュラインアドレスを含むタグページおよび２）キャッシュラインアドレスのタグページ内での位置を識別する。特に、キャッシュラインアドレスの上位側のビットによってタグページを識別し、下位側のビットによってタグページ内のキャッシュラインアドレスの位置を識別する。
一般に、下位ビットによってキャッシュラインアドレスのタグページ内での位置を識別するため、下位ビットはインデックスと呼ばれる。例えば、第１のタグページ内の第１のキャッシュラインアドレスについてみると、上位アドレスビットによって第１のタグページが識別され、下位アドレスビットによって第１のタグページ内の第１のキャッシュラインアドレス位置が識別される。
好ましい実施の形態では、コヒーレンスフィルタ内のタグコントローラが、キャッシュラインアドレスをタグメモリ内に直接マッピングする。例えば、第１のバスに接続されたプロセッサがバストランザクションを開始して特定のキャッシュラインアドレスを要求すると、第１のタグコントローラはこのキャッシュラインアドレスを評価する。第１のタグコントローラは、第１のタグメモリ内の特定のタグエントリを識別するためのインデックスとして下位アドレスビットを使用する。次に、第１のタグコントローラが上位側のビット（タグページ）を識別されたタグエントリに格納する。
好ましい実施の形態では、タグメモリはスタティックメモリで実現される。スタティックメモリで実現することで、各タグコントローラがバストランザクションの際に各タグメモリに迅速にアクセスできるようになる。本発明はスタティックメモリにおいて実現されているが、当業者であれば異なるタイプの格納メカニズムを利用してタグメモリを実現してもよいことは理解できよう。好ましくは、異なる種類の格納メカニズムによってメモリアクセス速度をバスのクロックレートと釣り合わせ、パフォーマンスを最適化する。
２つのキャッシュラインアドレスが同一のタグエントリにマッピングされた場合には、タグコントローラは前のキャッシュラインアドレスを追い出して新たなキャッシュラインアドレス用の空間を確保する。上述したように、古いキャッシュラインアドレスが無効になるまで、上記のプロセスによって新たなキャッシュラインアドレスに関連したバストランザクションが一時中断される場合がある。さらに、古いキャッシュラインアドレスを無効にするためには別のバストランザクションを用いて、タグメモリがキャッシュユニット内に存在するキャッシュラインアドレスの上位集合を維持するように保証しなければならない可能性もある。
本発明の一実施の形態では、各コヒーレンスフィルタがさらに、新たなキャッシュラインアドレスに関連したバストランザクションを一時中断させずに古いキャッシュラインアドレスおよび新たなキャッシュラインアドレスを保持する無効待ち行列を含む。これによって、システムのパフォーマンスを改善することができる。古いキャッシュラインを無効にする無効バストランザクションを後で行うことができるためである。
複数のバスにおいてキャッシュコヒーレンスを維持することに注目すると、好ましいコヒーレンスフィルタは、割り当てられたバスでのバストランザクションを監視することによって、クロスバストランザクションが必要になる時を判断する。特に、各コヒーレンスフィルタ内のサイクルエンコーダが、コヒーレンスフィルタの割り当てられたバスで生じている各バストランザクションを監視する。好ましい実施の形態では、サイクルエンコーダは、バス制御線を監視する周知のバス監視ロジックを利用する。サイクルエンコーダは次に１）そのタイプのバストランザクションおよび２）バストランザクションに関連したタグメモリ内のキャッシュステータス情報をコヒーレンスルールテーブルに送信する。
ここで、ルールテーブルに注目すると、ルールテーブルはキャッシュコヒーレンスを維持するためにクロスバストランザクションを実施する時を判断する。好ましい実施の形態では、ルールテーブルが、タグメモリ内のコヒーレンスステータス情報を一部利用して、クロスバストランザクションを実施するか否かを判断する。例えば、第１のバスでのバスリードトランザクションが特定のキャッシュラインアドレスを示す場合、第１のバスに割り当てられたルールテーブルが、他のバスに割り当てられたタグメモリ（リモートタグメモリ）内のキャッシュラインアドレスのコヒーレンスステータスを評価する。
リモートタグメモリから得られるコヒーレンスステータス情報を用いて、ルールテーブルは、キャッシュコヒーレンスを保証するためにリモートバストランザクションが必要であるか否かを判断する。下記においてより詳細に説明するように、特定のコヒーレンスフィルタでは、タグコントローラがリモートタグメモリにアクセスしてキャッシュステータスをルールテーブルに入力する。また、サイクルエンコーダがバストランザクションのタイプを判断し、バストランザクション情報をルールテーブルに入力する。
好ましい実施の形態では、ルールテーブルは大きな真理値表として作用する。バストランザクション情報およびリモートタグメモリ情報を利用して、ルールテーブルは、キャッシュコヒーレンスの維持にはいずれのクロスバストランザクションまたはいづれの組のバストランザクションが必要であるかを判断する。
例えば、プロセッサがリードバストランザクションを第１のバスで開始すると仮定する。この例では、バストランザクションを開始する第１のバスをローカルバスと呼び、多重バスシステムにおけるその他のバスをリモートバスと呼ぶ。リードバストランザクションでは、ローカルバス（ローカルコヒーレンスフィルタ）に割り当てられたコヒーレンスフィルタに所望のキャッシュラインアドレスを送信する。次に、リモートバス（リモートタグメモリ）に割り当てられたタグメモリにキャッシュラインアドレスが存在するか否かをローカルコヒーレンスフィルタで評価する。
この例のリモートタグメモリは、所望のキャッシュラインアドレスのコヒーレンスステータスが無効ステートにあることを示す。このような状況では、リモートバス内のキャッシュラインアドレスは無効であるため、クロスバストランザクションを行ってキャッシュコヒーレンスを維持する必要はない。したがって、ローカルコヒーレンスルールテーブルはバストランザクションをローカルバスおよび主記憶装置に制限し、リモートバスでのバストランザクションを発生させない。バストランザクションをローカルバスに制限することで、クロスバストラフィックが削減される。
しかしながら、クロスバストランザクションが要求されていることがリモートタグメモリによって示されている場合には、ルールテーブルは、キャッシュコヒーレンスを保証するのに必要な適切なクロスバストランザクションまたは一組のトランザクションを判断する。例えば、複数のリモートタグメモリのうち１つによって、キャッシュラインアドレスが所有ステートであることが示されている場合には、リモートバスに接続されたキャッシュユニットはキャッシュライン変更後のバージョンを有している可能性がある。キャッシュラインアドレスが所有ステートにあることがリモートタグメモリによって示されている場合には、ローカルルールテーブルは、リモートバスに接続されたバスマスタ論理がリモートバスでバスリードコマンドを実行してキャッシュコヒーレンスを保証する必要があることを示している。
バスリードコマンドがリモートバス上で実行されると、リモートキャッシュユニットはバスリードコマンドをスヌープし、これが所望のキャッシュラインの変更後のバージョンを有しているか否かを判断する。リモートバス上の複数のリモートキャッシュユニットのうちの１つがキャッシュラインの変更後のバージョンを返してきた場合には、ルールテーブルはローカルバス上の要求を出しているプロセッサにこのキャッシュラインを転送する。
しかしながら、リモートバス上のいずれのキャッシュユニットでもキャッシュラインが変更されていない場合には、キャッシュユニットはバスリードコマンドに応答しない。次に、ルールテーブルは最新のキャッシュラインが主記憶装置内にあると判断する。したがって、本発明では、ローカルバス上の要求を出しているプロセッサに主記憶装置内の最新のキャッシュラインを送信する。このように、本発明の好ましい実施の形態では、タグメモリにおけるキャッシュラインアドレスの上位集合を使用し、クロスバストランザクションが必要である時を判断してキャッシュコヒーレンスを維持する。
本発明のもう１つの態様は入力／出力デバイスとのインタフェース専用の第３のバスを含む。好ましい実施の形態では、この第３のバスを入力／出力（Ｉ／Ｏ）バスと呼ぶ。好ましいＩ／Ｏバスは、他のプロセッサバスと同一のタイプのバスである。しかしながら、Ｉ／Ｏバスおよび他のプロセッサバスの各々で異なるバスプロトコルを利用してもよいことは当業者であれば明らかであろう。
好ましいＩ／Ｏバスは、他のプロセッサバスと同様に動作する。ハイパフォーマンスコンピュータにおけるＩ／Ｏ転送の大半はダイレクトメモリアクセス（ＤＭＡ）転送によって行われる。ＤＭＡ転送は、通常は中央処理装置が直接関与することなく主記憶装置とＩ／Ｏ装置との間でデータを直接移動させるＩ／Ｏ装置によって開始される。Ｉ／Ｏバスで発生するＩ／Ｏトランザクションでのメモリコヒーレンスを維持することによって、各ＤＭＡ転送の前後にキャッシュユニットにおいてキャッシュラインのフラッシュが回避される。
もう１つのタイプのＩ／Ｏ転送では、プロセッサによってＩ／Ｏデータに対してダイレクトプログラムアクセスすることを必要とする。好ましい実施形態では、バススイッチはダイレクトＩ／Ｏ転送をＩ／Ｏバスに、メモリマッピングＩ／Ｏ転送として主記憶装置アドレス空間へのアクセス以外の全てのメモリアクセスをＩ／Ｏバスに転送する。このようなＩ／Ｏ転送はキャッシュコヒーレンスを必要とせず、下記においてより詳細に説明するように、１つのバスから他のバスに独自の方法で送信される。
好ましいＩ／Ｏバスは、Ｉ／Ｏコヒーレンスフィルタと、複数のシステムバスにわたるＩ／Ｏマッピングを改善し、かつＩ／Ｏデータ処理を改善してシステムバスの複雑さを軽減するＩ／Ｏバスインタフェースとを含む。バスにおいて生じるＩ／Ｏデータトランザクションは、自動的にＩ／Ｏバスに転送される。また、Ｉ／Ｏバス上にて開始されるトランザクションは、バストランザクションを他のバスに同報通信するのではなく宛先バスに送信される。
本発明のさらに他の態様では、複数のバス間での通信を最適化する。従来のバススイッチは、例えば、異なるバスを独立接続パスで相互接続する。このため、従来のマルチバスシステムでは、通常は第１のバスおよび第２のバスが１本の独立接続パスで相互接続され、第１のバスおよび第３のバスが他の独立接続パスで相互接続され、第２のバスおよび第３のバスがさらに他の独立接続パスで相互接続されている。予想通り、このような独立接続パスによってバススイッチを実現する上での複雑さが増すことになる。
例えば、第１のバスが第１のバストランザクションを第２のバスに送ることを望む場合、第１のバスは第１のバストランザクションを第１の待ち行列におき、これによって第１のバスと第２のバスとがリンクされる。次に、第２のバスが第１の待ち行列の出力から第１のバストランザクションを取得する。同様に、第２のバスが第２のバストランザクションを第１のバスに送ることを望む場合、第２のバスは第２のバストランザクションを第２の待ち行列におき、これによって第２のバスと第１のバスとがリンクされる。次に、第１のバスが第２の待ち行列の出力から第２のバストランザクションを取得する。
したがって、２本のバスで２つの待ち行列が必要になる。さらに他のバスを相互接続するのであれば、さらに多くの待ち行列が必要になる。例えば、３バスシステムでは、バスとバスとの間の各接続に２つの待ち行列が必要である。結果として、３バスシステムでは６つの待ち行列が必要になる。
しかしながら、好ましい実施の形態においてバススイッチを実現するための独自の方法では、すべてのバスからアクセス可能なメモリセルのマルチポートプールを用いて、このようなシステムの複雑性を減少する必要がある。独自のバススイッチを用いれば、場合によっては同時に発生することもある他のデータ転送に干渉することなく、どのバスから他のどのバスにでもデータを流すことができる。下記においてより詳細に説明するように、各バスからのバス転送はメモリセルの共通のプールに入力される。次に、メモリの共通のプールにおけるバストランザクションが、それぞれの宛先のバスに送られる。有利なことに、バスは独立接続パスを使用せずに他のいずれのバスに対しても読出しまたは書込みを行うことができる。
好ましい実施の形態では、各バストランザクションに関連した情報を、データセル、リクエストセル、アドレスセルと呼ばれる３つの異なるメモリセルに格納する。データセルは、バストランザクションに関連したデータを格納する。リクエストセルは、宛先のバスに送られるバストランザクションのタイプを定義するバストランザクション情報を含む。最後に、アドレスセルは、バストランザクションに関連したアドレス情報およびコヒーレンスステータス情報を含む。
好ましい実施の形態では、各データセル、各リクエストセルおよび各アドレスセルの間に１対１の対応が存在する。このため、各データセル、リクエストセルまたはアドレスセル、またはこれらのセルの任意の組み合わせで、特定のバストランザクションについての情報を含むことができる。好ましい実施の形態では３つのメモリセルを用いてバストランザクション情報を保持しているが、このバストランザクション情報は３個未満または４個以上のメモリセルに存在させることもできる。
概念的に、データセル、リクエストセルおよびアドレスセルは、マルチポートメモリの１つのプールに存在するかのように見せることができる。好ましい実施の形態では、データセル、リクエストセルおよびアドレスセルは異なるコンポーネントに位置しているが、依然として１対１の対応を維持し続けている。好ましい実施の形態では、データインタフェースバッファがデータセルを含み、システムアクセスコントローラがアドレスセルおよびリクエストセルを含む。
ここで、好ましいデータインタフェースバッファに注目すると、データインタフェースバッファにおける各データセルはマルチポートであり、全てのバスからアクセス可能である。各データセルは、特定のバストランザクションに関連したデータを含む。有利なことに、データインタフェースバッファにおけるデータセルのプールは、バスデータパス同士を相互接続する。
ここで、好ましいシステムアクセスコントローラに注目すると、システムコントローラは、中央リクエストリストと、バッファマネージャと、複数のバスマスタおよび複数のバススレーブとを含む。従来技術において周知のように、各バスマスタは、複数のバスのうちの１本でバストランザクションを開始し、各バススレーブはこの１つのバスに接続された他のデバイスによって開始されたバストランザクションを受信する。中央リクエストリストはリクエストセルのプールを維持し、バッファマネージャはアドレスセルのプールを維持する。
中央リクエストリスト内のリクエストセルは各々マルチポートであり、全てのバスからアクセス可能である。各リクエストセルは、ターゲットバス識別子と、バストランザクションコードとも言われるアクションコードと、オーナーバス識別子とを含む。ターゲットバス識別子は、特定の宛先のバスを識別し、バストランザクションコードは特定のバストランザクションを識別し、オーナーバス識別子は開始バスを識別する。
ここで、バッファマネージャにおけるアドレスセルのプールに注目すると、各アドレスセルはマルチポートであり、「使用中」情報と、メモリアドレスおよびデータセルステータス情報とを含む。アドレスセルにおける使用中情報はアドレスセルが利用できるか否かを示している。好ましい実施の形態では、使用中情報は、アドレスセルが使用中であるかフリーであるかを示すように設定された使用中ビットを有している。場合によっては、使用中ビットがフリーに設定されているときにデータセルに有効データを存在させることもできる。これによって、フリーのデータセル内の有効データを再利用する最適化が可能になる。
一方、メモリアドレスはバストランザクションに関連したメモリアドレスを含み、データセルステータスはデータセルにおけるデータのステータスを示している。アドレスセルのプールに加え、バッファマネージャは、アドレスセルプライオリティエンコーダと、複数のファーストインファーストアウト（ＦＩＦＯ）メモリと、複数のアドレス比較器とを有している。アドレスセルのプライオリティエンコーダは、どのアドレスセルが使用中でどのアドレスセルが新たなバストランザクション情報を受信できるフリーなものであるかを判断する。好ましい実施の形態では、アドレスセルのプライオリティエンコーダは、各アドレスセル内の使用中情報を評価することによってどのアドレスセルがフリーであるかを判断する。
アドレスセルのプライオリティエンコーダは、どのアドレスセルがフリーであるかを判断するだけでなく、異なるバスにフリーのアドレスセルを割り当てる。好ましくは、アドレスセルのプライオリティエンコーダがフリーのアドレスセルを異なるバスに割り当てる。フリーのアドレスセルをバスに割り当てた後、アドレスプライオリティエンコーダは使用中ビットを設定し、そのアドレスセルがフリーではないことを示す。例えば、３バスシステムにおける例であると仮定すると、プライオリティエンコーダは３つのアドレスセルがフリーであることを判断する。好ましいプライオリティエンコーダは、第１のフリーアドレスセルを第１のバスに割り当て、第２のフリーアドレスセルを第２のバスに割り当て、第３のフリーアドレスセルを第３のバスに割り当てる。
４番目のアドレスセルがフリーになると、アドレスセルのプライオリティエンコーダは第１のバスに戻り、この４番目のアドレスセルを第１のバスに割り当てる。好ましいアドレスセルのプライオリティエンコーダではこのような手法を用いてフリーのアドレスセルを異なるバスに割り当てているが、アドレスセルのプライオリティエンコーダを様々なアロケーションスキームに利用して、フリーアドレスセルを異なるバスに割り当てできることは、当業者であれば理解できよう。
ここで、バッファマネージャにおけるＦＩＦＯメモリに注目すると、ＦＩＦＯメモリは、割り当てられたアドレスセルをこれがバスで必要になるまで一時的に格納する。好ましい実施の形態では、ＦＩＦＯメモリは、割り当てられたアドレスセルを識別するアドレスセル識別子を格納する。アドレスセル識別子は、割り当てられたアドレスセルのメモリ位置を含むデータ変数である。バスは、アドレスセル識別子を利用して、アドレスセル識別子によって識別されたアドレスセルメモリ位置にアクセスする。
好ましい実施の形態では、各ＦＩＦＯメモリが特定のバスに割り当てられている。さらに、各ＦＩＦＯメモリが、各ＦＩＦＯメモリと同一のバスに割り当てられた複数のコヒーレンスフィルタのうちの１つと複数のバススレーブのうちの１つとに接続されている。複数のバススレーブのうちの１つまたは複数のコヒーレンスフィルタのうちの１つでバストランザクションを他のバスに送信したい場合、自己が割り当てられたＦＩＦＯメモリからアドレスセル識別子の１つを取得する。
例えば、第１のバス上の第１のプロセッサが第２のバス上の第２のＩ／Ｏ装置にデータ値を送信したいと仮定する。この例では、第１のバススレーブが第１のバスに接続されている。第１のプロセッサがバストランザクションを開始してデータ値を第２のＩ／Ｏ装置に送信すると、バストランザクションは第１のバススレーブによって受信される。次いで、第１のバススレーブが、バストランザクションを第２のバスに転送する必要があることを判断する。
したがって、第１のバススレーブがバッファマネージャにおける第１のＦＩＦＯメモリにアクセスし、アドレスセル識別子を取得する。アドレスセル識別子を利用して、第１のバススレーブが識別されたアドレスセルにアクセスし、データ値アドレスを格納し、必要があれば、データ値のコヒーレンスステータスをそのアドレスセルに格納する。対応するリクエストセルでは、第１のバススレーブがターゲットバス識別子における第２のバスを指定し、アクションコード（バストランザクションコードとも呼ぶ）におけるバストランザクションコードを指定し、オーナーバス識別子における第１のバスを指定する。さらに、第１のバススレーブは、バストランザクションに関連したデータ値を対応するデータセルに格納する。
別の例では、キャッシュラインアクセスがキャッシュコヒーレンスを保証するために第２のバスでのバストランザクションを要求していることを第１のバスに割り当てられた第１のキャッシュコヒーレンスフィルタが判断すると仮定する。この例では、第１のキャッシュコヒーレンスフィルタがバッファマネージャにおける第１のＦＩＦＯメモリにアクセスし、アドレスセル識別子を取得する。
第１のコヒーレンスフィルタは、アドレスセル識別子を用いて識別されたアドレスセルにアクセスする。第１のコヒーレンスフィルタは次に、キャッシュラインアドレスおよびコヒーレンスステータス情報をアドレスセルに格納する。また、リクエストセルでは、第１のコヒーレンスフィルタがターゲットバス識別子における第２のバスを指定し、バス識別子において適当なバストランザクションコードおよび第１のバスを指定する。しかしながら、この例では、キャッシュコヒーレンスを保証する上でキャッシュラインデータは必要ないため対応するデータセルは空のままである。バストランザクション情報を一度セルに追加すると、適切なバスでバストランザクション情報を取得して所望のバストランザクションを実行しなければならない。
好ましい実施の形態では、中央リクエストリストにおける複数のバスプライオリティエンコーダがリクエストセルに接続されている。上述したように、リクエストセルにおけるターゲットバス識別子が宛先のバスを識別する。一般的に、バスプライオリティエンコーダがリクエストセルにおけるターゲットバス識別子を評価し、どのバスでバストランザクションを行うべきであるかを判断する。
例えば、リクエストセルにおけるターゲットバス識別子が第１のバスおよび第２のバスを指定すると仮定する。この例では、第１のバスプライオリティエンコーダがリクエストセルにおけるターゲットバス識別子を評価してどのリクエストセルが第１のバス用のものであるかを識別し、第２のバスプライオリティエンコーダがターゲットバス識別子を評価してどのリクエストセルが第２のバス用のものであるかを識別する。
また、宛先のバスを識別するために、各バスプライオリティエンコーダは、特定のバスに関連したバスリクエストセルのうち、どのバスリクエストセルの優先度が最も高いかを判断する。好ましい実施の形態では、各バスプライオリティエンコーダは、総当たり手法を用いて優先度が最も高いバスリクエストセルを判断する。総当たり手法では、各バスプライオリティエンコーダがバスリクエストセルに対して連続的に最も高い優先度を割り当てることができる。
各バスプライオリティエンコーダは、優先度が最も高いバスリクエストセルを複数のバスマスタのうちの１つに転送する。上述したように、バス識別子を持っていることに加えて、リクエストセルはバストランザクションコードも含む。次に、リクエストセルにおいて識別されたバストランザクションをバスマスタが行う。場合によっては、下記においてより詳細に説明するように、トランザクションを実行するバスは、バストランザクションを開始したバスにデータを書き戻さなければならないこともある。このような場合には、バスマスタはデータセルを用いてライトバックデータを格納し、リクエストセルを再度利用して開始したバスと通信を行う。上述したように、最初のバスはリクエストセル内に存在するオーナーバス識別子によって識別される。しかしながら、バストランザクションの終了時には、バスマスタは、アドレスセル５００、リクエストセル６００およびデータセル７００をフリーに設定する。
バスマスタがバストランザクションを行っている間、バスプライオリティエンコーダは、そのバスに割り当てられて次に優先度の高いリクエストセルを識別し、そのリクエストセルをバスマスタに転送する。バスプライオリティエンコーダがそのバスに割り当てられた最後のバスリクエストセルに達した場合には、バスプライオリティエンコーダは、そのバスに割り当てられた第１のバスリクエストセルに戻る。総当たり的に各バスリクエストセルに対して最も高い優先度を割り当てることで、各バスリクエストセルを最終的にバスに転送することが保証される。新たなリクエストセルが中央リクエストリストに追加されると、各バスプライオリティエンコーダは新たなリクエストセルへの即時のアクセス権を取得し、よって最も高い優先度が割り当てられる。
本発明の他の態様では、バッファマネージャは、アドレス衝突を識別する複数のアドレス比較器を含む。一般に、アドレス衝突は２つの異なるバストランザクションが同一のデータ値に関連し、同時に発生した時に生じる。このような状況では、同一のデータに対する２つのバストランザクションを同時に、アドレスセル、リクエストセルおよびデータセルに存在させようとする可能性がある。予想通り、このようなアドレス衝突によって誤った結果が生じることがある。
好ましい実施の形態では、一組のアドレス比較器が各バスに割り当てられている。アドレス比較器の各組は、複数のコヒーレンスフィルタのうちの１つと、複数のバススレーブのうちの１つと、バッファマネージャ内のすべてのアドレスセルとに接続されている。各バストランザクションについて、そのバスに割り当てられた一組のアドレス比較器がバストランザクションアドレスとアドレスセル内の全てのアドレスとを比較する。アドレス衝突が検出されると、適切な動作を保証するために、以下に詳細に説明するようなアクションを適宜とらなければならない。
【図面の簡単な説明】
本発明の上記の態様および他の態様、利点、新規な特徴は、以下の詳細な説明を読み、添付の図面を参照することで明らかになろう。
図１は、好ましい多重処理マルチバスシステムのブロック図である。
図２は、好ましいシステムアクセスコントローラのブロック図である。
図３は、好ましいコヒーレンスフィルタおよびタグメモリのブロック図である。
図４は、好ましいキャッシュラインアドレスおよび好ましいタグメモリのブロック図である。
図５Ａおよび図５Ｂは、好ましいバッファマネージャのブロック図である。
図６は、好ましい中央リクエストリストのブロック図である。
図７は、好ましいデータインタフェースバッファのブロック図である。
図８は、バスリードコマンドの間にメモリコヒーレンスを維持するのに好ましい方法を示しているフローチャートである。
図９は、バス無効コマンドの間にメモリコヒーレンスを維持するのに好ましい方法を示しているフローチャートである。
図１０は、本発明の他の実施の形態における無効待ち行列のブロック図である。
これらの図面において、３桁の参照符号の１桁目の数字は、その要素が最初に出てきた図面の番号を示している。例えば、参照符号４０２が付された要素は、最初に図４に出てくる。また、図面全体を通して構成要素間の対応を示すために同様の参照符号を用いている。
好ましい実施の形態の詳細な説明
好ましい実施の形態では、１）複数のシステムバスとＩ／Ｏバスとを共有の主記憶装置に相互接続し、２）待ち時間およびシステム内の全帯域幅に対する影響を最小限に抑えつつキャッシュコヒーレンスを効果的に維持する、キャッシュコヒーレントなマルチバスシステムが得られる。特に、本発明は、少ない量のクロスバストラフィックでキャッシュメモリコヒーレンスを維持するような形でバス対バス通信をコーディネートするコヒーレンスフィルタを含む。
ここでは好ましいバスシステムに鑑みて本発明を説明するが、本発明はこれに限定されるものではなく、様々な他のマルチバス背景においても使用可能である。本発明の完全な理解を容易にするために、詳細な説明の残りの部分を以下のようなセクションおよびサブセクションに分けて構成する。
Ｉ．  用語および略語一覧
ＩＩ．  好ましいマルチバスシステムの概要
ＩＩＩ．  システムアクセスコントローラ
Ａ．  コヒーレンスフィルタ
１．  タグメモリ
２．  タグコントローラ
３．  サイクルエンコーダ
４．  ルールテーブル
Ｂ．  バッファマネージャ
Ｃ．  中央リクエストリスト
ＩＶ．  データインタフェースバッファ
Ｖ．  キャッシュコヒーレンス維持
Ａ．  バスリードラインコマンド処理
Ｂ．  バスリード無効ラインコマンド処理
ＶＩ．  他の実施の形態
ＶＩＩ．  結論
Ｉ．  用語および略語一覧
ＡＳＩＣ  Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ（特定用途向け集積回路）。
ＢＲＬコマンド  Ｂｕｓ  Ｒｅａｄ  Ｌｉｎｅ（バスリードライン）コマンド。バスリードラインコマンドは、バス上のキャッシュラインを読み出す。
ＢＲＩＬコマンド  Ｂｕｓ  Ｒｅａｄ  Ｉｎｖａｌｉｄａｔｅ  Ｌｉｎｅ（バスリード無効ライン）コマンド。バスリード無効ラインコマンドは、バス上のキャッシュラインを読み出し、無効にする。
バスマスタ  特定のバストランザクションを制御する制御ロジック。２つ以上のデバイスが共通バスを共有しているシステムによっては、各デバイスがバスマスタとなるための内部ロジックを有している。バスマスタがバストランザクションを行った後、バスマスタは他のデバイスがバスマスタになれるようにそのバスを放棄する。このようなデバイスとしては、プロセッサ、Ｉ／Ｏ装置、メモリコントローラなどが挙げられる。
バススレーブ  バスマスタからバストランザクションを受信する制御ロジック。
バススヌーピング  キャッシュメモリを有するプロセッサが、他のプロセッサによって行われるメモリトランザクションを監視するために用いる手法。
ＤＩＢ  Ｄａｔａ  Ｉｎｔｅｒｆａｃｅ  Ｂｕｆｆｅｒ（データインタフェースバッファ）。
ＤＥＦＥＲ＃信号  ＤＥＦＥＲ＃信号はバストランザクションを遅延する。好ましいＰｅｎｔｉｕｍ  Ｐｒｏバスでは、ＤＥＦＥＲ＃信号は１つの信号ではなく、ＤＥＦＥＲ＃信号の意味を示す制御信号の独自の符号化である。
ＤＥＮ＃信号  ＤＥＮ＃信号は、バストランザクションをいつ遅延できるかを示している。遅延されたバストランザクションは、順不同で実行される。すなわち、第１のバストランザクションが遅延されると、第２のバストランザクションの方が遅延されている第１のバストランザクションよりも前に終了する。バストランザクションを発行するプロセッサは、そのバストランザクションがＤＥＮ＃信号のアサートによって遅延できるものであるか否かを示している。
ＦＩＦＯ  ｆｉｒｓｔ−ｉｎ，ｆｉｒｓｔ−ｏｕｔ（ファーストイン、ファーストアウト）メモリ。ＦＩＦＯはアイテムが入力されるとそのままの順序でアイテムを出力するメモリ待ち行列である。すなわち、第１のアイテムが入ると同じ第１のアイテムが出てくる。
ＨＩＴ＃信号  好ましい実施の形態では、各プロセッサはバス上で一緒に配線されてＯＲが得られるＨＩＴ＃信号を有している。プロセッサはＨＩＴ＃信号を生成してデータ値が共有されていることを示す。例えば、第１のプロセッサがデータ値を要求すると、第２のプロセッサがバストランザクションを監視して、第２のプロセッサが要求されたデータ値のコピーを持った時にＨＩＴ＃信号を生成する。
ＨＩＴＭ＃信号  好ましい実施の形態では、各プロセッサはＨＩＴＭ＃信号を有している。プロセッサは、変更後のデータ値がプロセッサのキャッシュメモリに存在することがバススヌープ動作によって示されるとＨＩＴＭ＃信号をアサートする。
Ｉ／Ｏ  Ｉｎｐｕｔ／Ｏｕｔｐｕｔ（入力／出力）。入力／出力デバイスを用いた一般に入力／出力トランザクションを示す。
ＰＣＩバス  Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（周辺コンポーネント相互接続）バス。
プロセッサ  詳細な説明全体にわたって、プロセッサは計算または制御ユニットを意味する。プロセッサはバストランザクションを介して主記憶装置と通信し、中央処理装置、マイクロプロセッサ、スマート入力／出力デバイス、その他情報を格納、処理または転送するあらゆるデバイスを含むことができる。
ＲＡＭ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ランダムアクセスメモリ）。
ＳＲＡＭ  Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（スタティックランダムアクセスメモリ）。
ＳＤＲＡＭ  Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（同期ダイナミックランダムアクセスメモリ）。
スヌープヒット  スヌープヒットは、特定のメモリトランザクションにおいて要求されたデータが自己のキャッシュメモリにあることをプロセッサが検出すると発生する。
ＩＩ．  好ましいマルチバスシステムの概要
図１に示されるように、好ましいマルチバスシステム１００は、３つのシステムバスすなわち第１のシステムバス１０２と、第２のシステムバス１０４と、第３のシステムバス１０６とを有している。各システムバス１０２、１０４および１０６はさらに、一組のアドレスおよび制御線１０８ａ、１０８ｂおよび１０８ｃならびに一組のデータ線１１０ａ、１１０ｂおよび１１０ｃを備えている。アドレス線および制御線をアドレスおよび制御線１０８と総称する。データ線１１０ａ、１１０ｂおよび１１０ｃをデータ線１１０と総称する。本詳細な説明全体を通して、第１のシステムバス１０２は左側のバス１０２とも呼ばれ、第２のシステムバス１０４は右側のバス１０４とも呼ばれ、第３のシステムバス１０６はＩ／Ｏバス１０６とも呼ばれる。
好ましい実施の形態では、各システムバス１０２、１０４および１０６は、Ｉｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎによって定義されたＰｅｎｔｉｕｍ  Ｐｒｏシステムバスである。Ｐｅｎｔｉｕｍ  Ｐｒｏシステムバスは、３６ビットのアドレスと、６４ビットのデータと、様々な制御信号および誤差補正信号を提供する。好ましい実施の形態ではＰｅｎｔｉｕｍ  Ｐｒｏバスを利用しているが、スヌーピングキャッシュコヒーレンスプロトコルを実現する様々なシステムバスに本発明を適用可能であることは当業者であれば理解できよう。さらに、１つのバスのフォーマットが他のバスのフォーマットとは異なっていてもよい。
左側のバス１０２に接続されているのは、複数のプロセッサ１１２ａ、１１２ｂなどである。右側のバス１０４に接続されているのは、複数のプロセッサ１１２ｃ、１１２ｄなどである。プロセッサ１１２ａ、１１２ｂ、１１２ｃおよび１１２ｄをプロセッサ１１２と総称する。好ましい実施の形態では、各プロセッサ１１２は内部キャッシュユニット１１４を有する。４つのプロセッサ１１２を図示してあるが、各バス１０２および１０４をさらに他のプロセッサ１１２に接続することも可能である。好ましい実施の形態では、プロセッサ１１２はＩｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＰｅｎｔｉｕｍ  Ｐｒｏプロセッサである。本発明の好ましい実施の形態ではＰｅｎｔｉｕｍ  Ｐｒｏプロセッサを利用しているが、本発明は特定のシステムバスと互換性のある様々なプロセッサ１１２に本発明を適用可能であることは当業者であれば理解できよう。
プロセッサ１１２内のキャッシュメモリ１１４は、データをローカルに格納することによって処理パフォーマンスを改善する。一般に、キャッシュメモリ１１４によって、少ないバス帯域幅でプロセッサ１１２がデータ値にアクセスすることが可能になる。好ましい実施の形態におけるキャッシュメモリ１１４は、データ値をキャッシュラインに構成し、各キャッシュラインが３２バイトのデータを含む。
好ましい実施の形態における第３のシステムバス１０６は、入力／出力（Ｉ／Ｏ）トランザクションを複数のＩ／Ｏブリッジ１２０と主記憶装置１３２との間で送信し、よってＩ／Ｏバス１０６と呼ばれる。好ましいＩ／Ｏブリッジ１２０は、Ｉｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎ製の８２４５０ＧＸ  ＰＣＩｓｅｔ  Ｏｒｉｏｎ  ＰＣＩ  Ｂｒｉｄｇｅである。好ましい実施の形態では、Ｉ／Ｏブリッジ１２０がＰＣＩバスを使用してＩ／ＯトランザクションをＩ／Ｏバス１０６から複数のＩ／Ｏ装置１２２に転送する。しかしながら、Ｉ／Ｏブリッジ１２０は様々なＩ／Ｏ装置１２２に対してアクセスする様々なデバイスで実現可能であることは当業者であれば理解できよう。また、Ｉ／Ｏブリッジ１２０は任意のものでり、互換性のあるＩ／Ｏ装置１２２をＩ／Ｏバス１０６に直接取り付けてもよい。
好ましいマルチバスシステム１００には、奇数主記憶装置モジュール１３２ａおよび偶数主記憶装置モジュール１３２ｂと、データインタフェースバッファ１３４も含まれている。好ましい実施の形態では、奇数主記憶装置モジュール１３２ａおよび偶数主記憶装置モジュール１３２ｂを総称して主記憶装置１３２と呼ぶ。好ましい奇数メモリモジュール１３２ａおよび好ましい偶数メモリモジュール１３２ｂは、３２メガバイトから３２ギガバイトまでの範囲でサイズを変えることのできる同期ダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）を備えている。ＳＤＲＡＭは、データの高速バーストを提供する同期パイプラインインタフェースを使用している。
好ましいマルチバスシステムには、システムアクセスコントローラ１３０およびデータインタフェースバッファ１３４も含まれている。概して、システムアクセスコントローラはマルチバスシステムの動作を制御する。システムアクセスコントローラは、各バス１０２、１０４および１０６についてアドレスおよび制御線１０８ａ、１０８ｂおよび１０８ｃに接続されている。また、システムアクセスコントローラ１３０は一組の奇数メモリアドレスおよび制御線１３８ａと、一組の偶数メモリアドレスおよび制御線１３８ｂと、一組のデータインタフェースバッファ（ＤＩＢ）制御線１４０とにも接続されている。
一方、データインタフェースバッファ１３４は、異なるバス１０２、１０４および１０６と主記憶装置１３２との間のデータパスを提供する。データインタフェースバッファ１３４は、各バス１０２、１０４および１０６についてのデータ線１１０ａ、１１０ｂおよび１１０ｃに接続されている。また、データインタフェースバッファ１３４は一組の主記憶装置データ線１４２にも接続されている。
プロセッサ１１２は、主記憶装置１３２からデータを読み込むことによって、自己のキャッシュメモリ１１４を充填する。最新のデータをキャッシュメモリ１１４内に維持するために、特定のバス上のプロセッサ１１２内のキャッシュメモリ１１４は、自己が関連したバス１０２、１０４または１０６上で発生する主記憶装置のバストランザクションをスヌープする。これをバススヌーピングと呼ぶ。
キャッシュメモリ１１４がバストランザクションによって識別されたキャッシュラインと同一のキャッシュラインを含む場合には、スヌープヒットが起こる。スヌープヒットが起こると、データ値の共有コピーを持っている１つのプロセッサ１１２または複数のプロセッサ１１２がＨＩＴ＃信号をアサートする。ＨＩＴ＃信号は、複数のアドレスおよび制御線１０８のうちの１本である。ＨＩＴ＃信号は、他のプロセッサ１１２に、メモリトランザクションに関連したデータをプロセッサ１１２と共有していることを通知する。好ましい実施の形態では、他のプロセッサ１１２のいずれもＨＩＴ＃信号をアサートしない場合には、要求を出したプロセッサが所望のデータ値のコヒーレンスステータスを所有ステートに設定する。
他の場合には、プロセッサ１１２は自己のキャッシュメモリ１１４におけるキャッシュラインを変更することができる。しかしながら、バストラフィックを軽減するために、他のプロセッサ１１２が同一のキャッシュラインを主記憶装置１３２から要求するまでは、キャッシュメモリ１１４によって変更後のキャッシュラインを主記憶装置１３２に返送しなくてもよい。例えば、プロセッサ１１２がキャッシュラインを更新した時に、他のプロセッサ１１２がこのキャッシュラインのコピーを持っていないかまたは同一のキャッシュラインの取得を望むことがある。このような場合には、最新のキャッシュラインを有するプロセッサ１１２は最新のキャッシュラインを主記憶装置１３２に書き戻すのではなく、プロセッサ１１２が最新のキャッシュラインを自己のキャッシュメモリ１１４内に保持する。
好ましい実施の形態では、バススヌープ動作によって変更後のキャッシュラインがプロセッサのキャッシュメモリ１１４内に存在することが示されると、複数のプロセッサ１１２のうちの１つがＨＩＴＭ＃信号をアサートする。ＨＩＴＭ＃信号は、複数のアドレスおよび制御線１０８のうちの１つであり、最新のキャッシュラインを有しているプロセッサ１１２がキャッシュラインを主記憶装置１３２に書き戻す必要があることを示している。例えば、好ましい実施の形態において、左側のバス１０２上の第１のプロセッサ１１２ａが変更後のキャッシュラインを自己のキャッシュメモリ１１４内に保持している仮定する。左側のバス１０２上の第２のプロセッサ１１２ｂが同一のキャッシュラインのコピーを取得することを望むと、第２のプロセッサ１１２ｂは左側のバス１０２を制御し、主記憶装置１３２に対するメモリトランザクションを実行して所望のキャッシュラインを識別する。次に、第１のプロセッサ１１２はメモリトランザクションをスヌープし、自己が所望のキャッシュラインの変更後のバージョンを含むと判断する。
これに応答して、第１のプロセッサ１１２は、自分がキャッシュラインの変更後のバージョンを含むことを示すＨＩＴＭ＃信号をアサートする。第１のプロセッサ１１２が左側のバス１０２の指揮をとり、変更後のキャッシュラインを主記憶装置１３２に書き戻す。第１のプロセッサ１１２ａが変更後のキャッシュラインを主記憶装置１３２に書き戻した後、第２のプロセッサ１１２ｂが主記憶装置のトランザクションを再開し、最新のキャッシュラインを取得する。
好ましいプロセッサ１１２は、バストランザクションが遅延可能なものであるか否かを示すことができる。バストランザクションを発行するプロセッサ１１２は、そのバストランザクションが遅延可能であるか否かをＤＥＮ＃信号によって示す。ＨＩＴＭ＃信号をアサートするプロセッサがトランザクション応答を制御する。プロセッサがＨＩＴＭ＃信号をアサートしたら、そのプロセッサは、（メモリが有している）順にバストランザクションを実行するか、またはトランザクションが遅延可能であれば、システムアクセスコントローラ１３０はバストランザクションを遅延するＤＥＦＥＲ＃信号をアサートする。ＤＥＦＥＲ＃信号は特定の制御線１０８の符号化である。
ＩＩＩ．  システムアクセスコントローラ
ここで、システムアクセスコントローラ１３０に注目すると、図２に示されるように、好ましいシステムアクセスコントローラ１３０を特定用途向け集積回路（ＡＳＩＣ）として実現する。概して、システムアクセスコントローラ１３０は、マルチバスシステム１００におけるキャッシュコヒーレンスを維持しつつ３本のバス１０２、１０４および１０６および主記憶装置１３２を制御する。
好ましくは、システムアドレスコントローラ１３０は、左側のコヒーレンスフィルタ２００ａと、右側のコヒーレンスフィルタ２００ｂと、Ｉ／Ｏコヒーレンスフィルタ２００ｃとを含む。本詳細な説明全体を通して、左側のコヒーレンスフィルタ２００ａ、右側のコヒーレンスフィルタ２００ｂおよびＩ／Ｏコヒーレンスフィルタ２００ｃをコヒーレンスフィルタ２００と呼ぶ。システムアクセスコントローラ１３０はまた、左側のバスマスタ２０２ａと、右側のバスマスタ２０２ｂと、Ｉ／Ｏバスマスタ２０２ｃとを含む。本詳細な説明全体を通して、左側のバスマスタ２０２ａ、右側のバスマスタ２０２ｂおよびＩ／Ｏバスマスタ２０２ｃをバスマスタ２０２と総称する。
また、システムアクセスコントローラ１３０は、左側のバススレーブ２０４ａと、右側のバススレーブ２０４ｂと、Ｉ／Ｏバススレーブ２０４ｃとを含む。本詳細な説明全体を通して、左側のバススレーブ２０４ａ、右側のバススレーブ２０４ｂおよびＩ／Ｏバススレーブ２０４ｃをバススレーブ２０４と総称する。さらに、システムアクセスコントローラ１３０は、奇数メモリコントローラ２０６ａおよび偶数メモリコントローラ２０６ｂを含む。本詳細な説明全体を通して、奇数メモリコントローラ２０６ａおよび偶数メモリコントローラ２０６ｂをメモリコントローラ２０６と総称する。
システムアクセスコントローラ１３０は、中央リクエストリスト２０８およびバッファマネージャ２１０を含む。最後に、システムアクセスコントローラ１３０は外部の左側のタグメモリ２１２ａと、外部の右側のタグメモリ２１２ｂと、内部のＩ／Ｏタグメモリ２１２ｃとに接続されている。本詳細な説明全体を通して、左側のタグメモリ２１２ａ、右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃをタグメモリ２１２と総称する。
好ましい実施の形態では、左側のタグメモリ２１２ａ、左側のコヒーレンスフィルタ２００ａ、左側のバスマスタ２０２ａおよび左側のバススレーブ２０４ａを左側のバス１０２に割り当てる。右側のタグメモリ２１２ｂ、右側のコヒーレンスフィルタ２００ｂ、右側のバスマスタ２０２ｂおよび右側のバススレーブ２０４ｂを右側のバス１０４に割り当てる。Ｉ／Ｏタグメモリ２１２ｃ、Ｉ／Ｏコヒーレンスフィルタ２００ｃ、Ｉ／Ｏバスマスタ２０２ｃおよびＩ／Ｏバススレーブ２０４ｃをＩ／Ｏバス１０６に割り当てる。
ここで、システムアクセスコントローラ１３０の相互接続に注目すると、左側のコヒーレンスフィルタ２００ａは、左側のバスアドレスおよび制御線１０８ａ、左側のタグメモリ２１２ａ、右側のタグメモリ２１２ｂ、Ｉ／Ｏタグメモリ２１２ｃ、バッファマネージャ２１０および中央リクエストリスト２０８と通信を行う。右側のコヒーレンスフィルタ２００ｂは、右側のバスアドレスおよび制御線１０８ｂ、左側のタグメモリ２１２ａ、右側のタグメモリ２１２ｂ、Ｉ／Ｏタグメモリ２１２ｃ、バッファマネージャ２１０および中央リクエストリスト２０８と通信を行う。Ｉ／Ｏコヒーレンスフィルタ２００ｃは、Ｉ／Ｏバスアドレスおよび制御線１０８ｃ、左側のタグメモリ２１２ａ、右側のタグメモリ２１２ｂ、Ｉ／Ｏタグメモリ２１２ｃ、バッファマネージャ２１０および中央リクエストリスト２０８と通信を行う。
左側のバスマスタ２０２は、左側のバスアドレスおよび制御線１０８ａおよび中央リクエストリスト２０８と通信を行う。右側のバスマスタ２０２ｂは、右側のバスアドレスおよび制御線１０８ｂおよび中央リクエストリスト２０８と通信を行う。Ｉ／Ｏバスマスタ２０２ｃは、Ｉ／Ｏバスアドレスおよび制御線１０８ｃおよび中央リクエストリスト２０８と通信を行う。
左側のバススレーブ２０４ａは、左側のバスアドレスおよび制御線１０８ａ、奇数メモリコントローラ２０６ａ、偶数メモリコントローラ２０６ｂおよびバッファマネージャ２１０と通信を行う。右側のバススレーブ２０４ｂは、右側のバスアドレスおよび制御線１０８ｂ、奇数メモリコントローラ２０６ａ、偶数メモリコントローラ２０６ｂおよびバッファマネージャ２１０と通信を行う。Ｉ／Ｏバススレーブ２０４ｃは、Ｉ／Ｏバスアドレスおよび制御線１０８ｃ、奇数メモリコントローラ２０６ａ、偶数メモリコントローラ２０６ｂおよびバッファマネージャ２１０と通信を行う。
したがって、中央リクエストリストは、左側のコヒーレンスフィルタ２００ａ、右側のコヒーレンスフィルタ２００ｂ、Ｉ／Ｏコヒーレンスフィルタ２００ｃ、左側のバスマスタ２０２ａ、右側のバスマスタ２０２ｂおよびＩ／Ｏバスマスタ２０２ｃと通信を行う。バッファマネージャ２１０は、左側のコヒーレンスフィルタ２００ａ、右側のコヒーレンスフィルタ２００ｂ、Ｉ／Ｏコヒーレンスフィルタ２００ｃ、左側のバスマスタ２０２ａ、右側のバスマスタ２０２ｂ、Ｉ／Ｏバスマスタ２０２ｃ、左側のバススレーブ２０４ａ、右側のバススレーブ２０４ｂ、Ｉ／Ｏバススレーブ２０４ｃ、奇数メモリコントローラ２０６ａおよび偶数メモリコントローラ２０６ｂと通信を行う。
ここで、バスマスタ２０２に注目すると、バスマスタ２０２は、自己が割り当てられたバス１０２、１０４および１０６上のバストランザクションを制御する。例えば、左側のバスマスタ２０２ａは左側のバス１０２上のバストランザクションを開始する。バスマスタ２０２が１つまたは複数のバストランザクションを行った後、バスマスタ２０２はそのバスを放棄し、他のデバイスがバスマスタになれるようにする。バスマスタ２０２を実現するための制御ロジックは当業者間で周知である。
ここで、バススレーブ２０４に注目すると、バススレーブ２０４は、自己が割り当てられたバス１０２、１０４および１０６上のプロセッサ１１２またはＩ／Ｏブリッジ１２０のうちの１つによって開始されたバストランザクションを受信する。例えば、複数のプロセッサ１１２のうちの１つによって、主記憶装置１３２の特定のデータ値に対するリードバストランザクションを開始することができる。バススレーブ２０４は、バストランザクションを受信し、要求されたデータ値を主記憶装置１３２から取得する。バススレーブ２０４を実現するための制御ロジックは当業者間で周知である。
奇数メモリコントローラ２０６ａおよび偶数メモリコントローラ２０６ｂは、それぞれ奇数主記憶装置モジュール１３２ａおよび偶数主記憶装置モジュール１３２ｂへのアクセスを制御する。奇数メモリコントローラ２０６ａおよび偶数メモリコントローラ２０６ｂは、当業者間で周知のメモリ制御手法を用いて奇数主記憶装置モジュール１３２ａおよび偶数主記憶装置モジュール１３２ｂを制御する。
Ａ．  コヒーレンスフィルタ
ここで、好ましいコヒーレンスフィルタ２００に注目すると、各コヒーレンスフィルタ２００は、キャッシュコヒーレンスを維持するためにはどのバストランザクションまたはバストランザクションの組が必要であるかを判断する。好ましい実施の形態では、各コヒーレンスフィルタ２００は、キャッシュコヒーレンスを維持するのにクロスバストランザクションが必要ない場合には、クロスバストラフィックを制限することによってマルチバスシステム２００におけるパフォーマンスを改善する。
上述したように、左側のコヒーレンスフィルタ２００ａは左側のバスアドレスおよび制御線１０８ａを監視し、右側のコヒーレンスフィルタ２００ｂは右側のバスアドレスおよび制御線１０８ｂを監視し、Ｉ／Ｏコヒーレンスフィルタ２００ｃはＩ／Ｏアドレスおよび制御線１０８ｃを監視する。図３に示されるように、各コヒーレンスフィルタ２００は、タグコントローラ３００と、サイクルエンコーダ３０２と、ルールテーブル３０４とを含む。また、各コヒーレンスフィルタ２００は、複数のタグメモリ２１２のうちの１つに割り当てられている。
１．  タグメモリ
好ましくは、各タグメモリ２１２は、システムアクセスコントローラ１３０の外部に位置するスタティックランダムアクセスメモリ（ＳＲＡＭ）に格納されている。左側のタグメモリ２１２ａおよび右側のタグメモリ２１２ｂは同一のサイズであると好ましく、Ｉ／Ｏタグメモリの方はＩ／Ｏブリッジ１２０などに一般に接続されている小さなキャッシュユニットゆえにサイズは小さい。特定のバスに割り当てられたタグメモリ２１２は、１）その割り当てられたバスに接続されたキャッシュメモリ１１４に位置するキャッシュライン、２）キャッシュラインのキャッシュステータスの上位集合レコードを維持する。好ましい実施の形態では、キャッシュステータスは、キャッシュメモリ１１４内のキャッシュコヒーレンスステートよりも少数のステートを有する一組のキャッシュコヒーレンスステートで表される。
周知のように、主記憶装置における各キャッシュラインは、キャッシュラインアドレスで識別される。キャッシュラインのサイズはマルチバスシステム１００ごとに異なる。好ましい実施の形態では、キャッシュラインは、３２個の８ビットデータ値（２５６ビット）を含む。各タグメモリ２１２は、実際のキャッシュラインではなく、キャッシュラインを識別するキャッシュラインアドレスを格納する。キャッシュラインアドレスを格納することに加え、各タグメモリ２１２はそのキャッシュラインアドレスに関連したコヒーレンスステータス情報も格納する。このように、各タグメモリ２１２は、タグメモリの割り当てられたバスに接続されたキャッシュメモリ１１４にキャッシュされたデータの考え得る内容およびステータスに関する情報を維持する。
例えば、左側のバス１０２上のプロセッサ１１２ａが、主記憶装置１３２内のキャッシュラインにアクセスするリードバストランザクションを生成すると、プロセッサ１１２ａは所望のキャッシュラインアドレスを左側のバスアドレスおよび制御線１０８ａ上に置く。以下においてより詳細に説明するように、左側のコヒーレンスフィルタ２００ａは所望のキャッシュラインアドレスを受信し、このキャッシュラインアドレスを左側のタグメモリ２１２ａに格納する。また、左側のコヒーレンスフィルタ２００ａは、左側のタグメモリ２１２ａのキャッシュラインアドレスに関連したコヒーレンスステータスを格納する。
各キャッシュラインアドレスに関連したコヒーレンスステータスは、キャッシュメモリ１１４内のキャッシュラインのステータスに関連している。好ましい実施の形態では、コヒーレンスステータスは、３種類のコヒーレンスステートすなわち、無効ステート、共有ステートまたは所有ステートを含む。無効ステートは、キャッシュラインが無効であり、プロセッサ１１２はこれを使用すべきでないことを意味する。共有ステートは、プロセッサ１１２がキャッシュラインを変更できないことを意味する。例えば、共有キャッシュラインは変更されないプログラム指示などであることが多い。所有ステートは、キャッシュラインを所有しているプロセッサ１１２によってキャッシュラインを変更可能であることを意味する。好ましい実施の形態では、Ｐｅｎｔｉｕｍ  Ｐｒｏプロセッサ１１２が採用しているＭＥＳＩプロトコルをはじめとする様々なキャッシュコヒーレンスプロトコルに対する適応性がゆえに無効（Ｉｎｖａｌｉｄ）、共有（Ｓｈａｒｅｄ）および所有（Ｏｗｎｅｄ）プロトコルを利用する。
しかしながら、キャッシュラインのコヒーレンスステータスは、無効、共有および所有プロトコルに限定されないことは当業者であれば明らかであろう。特に、変更（Ｍｏｄｉｆｉｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）および無効（Ｉｎｖａｌｉｄ）（ＭＥＳＩ）プロトコル、変更（Ｍｏｄｉｆｉｅｄ）、所有（Ｏｗｎｅｄ）、排他（Ｅｘｃｌｕｓｉｖｅ）、共有（Ｓｈａｒｅｄ）および無効（Ｉｎｖａｌｉｄ）（ＭＯＥＳＩ）プロトコル、変更（Ｍｏｄｉｆｉｅｄ）、共有（Ｓｈａｒｅｄ）、無効（Ｉｎｖａｌｉｄ）（ＭＳＩ）プロトコル、Ｂｅｒｋｅｌｅｙプロトコル、イリノイ大学コヒーレンスプロトコルなどの様々なコヒーレンスプロトコルを用いてコヒーレンスステータスを実現できることは、当業者であれば理解できよう。
コヒーレンスステータスは、２ステート無効および所有プロトコルなどの２ステートコヒーレンスプロトコルを用いて実現することもできる。デュアルバスシステムの２ステートコヒーレンスプロトコルでは、全てのバスは全てのキャッシュラインの共有コピーを有していると仮定される。全てのキャッシュラインが共有されているかのように扱われ、コヒーレンスメモリが維持する必要があるのは無効および所有ステートにあるデータ値に関連したレコードのみであるため、これによってコヒーレンスメモリのサイズが削減されることが多い。有利なことに、バスが共有データに対して標準的なリードトランザクションを行うと、共有ステータス情報はコヒーレンスメモリには格納されない。これによって、コヒーレンスメモリ内のコヒーレンスステータス情報の上位集合の維持に関する問題が少なくなる。
しかしながら、このような２ステートシステムでは、全ての排他リードトランザクションまたは無効トランザクションにおいては、１つまたは複数のクロスバストランザクションを行ってキャッシュコヒーレンスを保証する必要がある。このようなクロスバストランザクションは、無効コマンドの排他リードトランザクションに関連したデータの共有バージョンを他のバスが実際に含んでいるか否かを知るために必要である。デュアルバスシステムでは、３本以上のバスの場合よりも２ステートプロトコルによって全体のパフォーマンスが高くなることがあるが、２ステートプロトコルの利点は作業負荷特性に大きく依存する。
好ましいＰｅｎｔｉｕｍ  Ｐｒｏプロセッサ１１２は、自己の内部キャッシュメモリ１１４に格納されたキャッシュラインについての正確なコヒーレンスステータス情報を出力はしない。例えば、内部キャッシュメモリ１１４は、変更されていないキャッシュラインをそのキャッシュラインが放棄されたことを信号通知せずにこれを放棄することができる。本発明の好ましい実施の形態では、各タグメモリ２１２を独自に適合させ、現在のコヒーレンスステータス情報を出力しない内部キャッシュメモリ１１４用のキャッシュコヒーレンスを保証する。
特定のバスに接続された内部キャッシュメモリ１１４に現在保持されている可能性があるキャッシュラインアドレスの上位集合を維持することによって、各タグメモリ２１２がキャッシュコヒーレンスを保証する。例えば、左側のタグメモリ２１２は、プロセッサ１１２ａおよびプロセッサ１１２ｂの内部キャッシュメモリ１１４に保持されている可能性のあるキャッシュラインアドレスの上位集合を維持する。キャッシュラインアドレスの上位集合は必ずしも正確なタグステータス情報を含むとは限らないため、キャッシュメモリ１１４が実際に放棄されたキャッシュラインを有する場合に、タグメモリ２１２によってキャッシュメモリ１１４内の特定のキャッシュラインが共有ステートであることを示すことができる。他の場合においては、キャッシュメモリ１１４が実際に主記憶装置１３２に書き戻されたキャッシュラインを有する場合に、タグメモリ２１２におけるキャッシュラインアドレスの上位集合によってキャッシュメモリ１１４内の特定のキャッシュラインが変更されたステートであることを示すことができる。
キャッシュラインアドレスの上位集合を維持するために、好ましいタグメモリ２１２ではいわゆるインクルージョンルールと呼ばれているものを利用している。インクルージョンルールは、特定のバスに接続されたキャッシュメモリ１１４に格納されたキャッシュラインアドレスが常にそのバスに割り当てられたタグメモリのキャッシュラインアドレスの上位集合であることを保証する。キャッシュラインアドレスを複数のタグメモリ２１２のうちの１つから削除する場合、インクルージョンルールでは関連したキャッシュメモリ１１４に対して自己のキャッシュメモリにおいてそのキャッシュラインを無効にするように指示をする。
例えば、左側のタグメモリ２１２ａがメモリ容量を持たないかまたは新たなキャッシュアドレスを保持する連帯性を持たない場合、左側のタグメモリ２１２ａから既存のキャッシュラインアドレス（古いキャッシュラインアドレス）のうちの１つを追い出して左側のタグメモリ２１２ａに新たなキャッシュラインアドレス用の空間を作成しなければならない。古いキャッシュラインアドレスが無効ステートであれば、バスに接続されたキャッシュメモリ１１４は、古いキャッシュアドレスに関連したキャッシュラインをもう使用してはおらず、単に古いキャッシュラインアドレスを新たなキャッシュラインアドレスで置き換えるのみである。
しかしながら、古いキャッシュラインアドレスが共有または所有ステートにある場合には、キャッシュメモリ１１４が古いキャッシュラインアドレスを無効にするまでは左側のコヒーレンスフィルタ２００によって古いキャッシュラインアドレスを左側のタグメモリ２１２ａから追い出すことができない。上述したように、左側のタグメモリ２１２ａは左側のバス１０２に接続されたキャッシュメモリ１１４内のキャッシュラインアドレスの上位集合を維持しなければならないため、まずキャッシュメモリ１１４で古いキャッシュラインアドレスを無効にし、その後で左側のタグメモリ２１２ａが古いキャッシュラインアドレスを新たなキャッシュラインアドレスに置き換えることができる。
下記においてより詳細に説明するように、左側のコヒーレンスフィルタ２００ａは、無効バストランザクションを行って、左側のバス１０２に接続されたキャッシュメモリ１１４内の古いキャッシュラインアドレスを無効にする。無効バストランザクションは、キャッシュメモリ１１４に最初に古いキャッシュラインアドレスを無効にするように指示する左側のバスで起こる。
しかしながら、場合によっては古いキャッシュラインが所有ステートにあり、複数のキャッシュメモリ１１４のうちの１つによって古いキャッシュラインが変更されている可能性もある。キャッシュメモリ１１４が古いキャッシュラインを変更した可能性がある場合、バスリード無効ライン（ＢＲＩＬ）トランザクションが行われる。キャッシュメモリ１１４が変更済の古いキャッシュラインを有している場合、バスリード無効ライントランザクションの間、キャッシュメモリ１１４はバストランザクションに対して指令権を持ち、古いキャッシュラインアドレスに対応する変更後のキャッシュラインを主記憶装置１３２に書き戻す。変更後のキャッシュラインを主記憶装置に書き戻した後、左側のコヒーレンスフィルタ２００ａは左側のタグメモリ２１２ａ内の古いキャッシュラインアドレスを新たなキャッシュラインアドレスと置き換える。このように、キャッシュラインアドレスの上位集合をタグメモリ２１２において維持するためには、場合によっては、古いキャッシュラインを置き換えることができるようになる前に、キャッシュメモリ１１４によって変更後のデータを主記憶装置１３２に書き戻さなければならないこともある。
キャッシュラインアドレス４００および各タグメモリ２１２のフォーマットを図４に示す。キャッシュラインアドレス４００は、概念的に２つの部分に分割される。第１の部分はタグページアドレス４０２を含み、第２の部分はオフセットアドレス４０４を含む。好ましい実施の形態では、タグメモリ２１２におけるタグエントリ４１０の数がいわゆるタグページと呼ばれているものの大きさを規定する。好ましくは、タグメモリ２１２は各々この数のタグエントリ４１０を有し、よってタグページサイズは同一である。
好ましい実施の形態では、タグページアドレス４０２は、キャッシュラインアドレス４００を含むタグページを識別し、オフセットアドレス４０４は、キャッシュラインアドレス４００のタグページ内での位置を識別する。特に、キャッシュラインアドレス４００の上位側のビットによってタグページアドレスを識別し、下位側のビットによってオフセットアドレス４０４を識別する。
一般に、下位ビットによってキャッシュラインアドレスのタグページ内での位置を識別するので、下位ビットはインデックスと呼ばれる。例えば、第１のキャッシュラインアドレス４００についてみると、上位アドレスビットによってタグページアドレス４０２が識別され、下位アドレスビットによってタグページ内のキャッシュアドレス線４００の位置が識別される。
タグページのサイズは変更可能であるため、タグページアドレス４０２およびオフセットアドレス４０４に割り当てられるビット数も変わる。好ましい実施の形態では、左側のタグメモリ２１２ａおよび右側のタグメモリ２１２ｂが２16個のエントリを含む場合、オフセットアドレス４０４はキャッシュラインアドレス４００の下位１６ビットであり、タグページアドレス４０２はキャッシュラインアドレス４００の上位１５ビットである。上述したように、Ｉ／Ｏタグメモリ２１２ｃの方がサイズが小さいため、含んでいるエントリ数も少ない。好ましい実施の形態では、Ｉ／Ｏタグメモリ２１２は３２個のエントリを含む。
以下の表は、様々なサイズのタグメモリ２１２と、キャッシュラインアドレス４００でのおよび対応するタグページアドレス４０２およびオフセットアドレス４０４のサイズを示している。
0004316016.tif 000002
好ましい実施の形態では、コヒーレンスフィルタ２００は、ダイレクトマッピング手法を用いてキャッシュラインアドレス４００をタグメモリ２００に格納する。ダイレクトマッピングは、各キャッシュラインアドレス４００が１つの特定のタグエントリ４１０にマッピングされることを意味する。図４は、２16個のタグエントリ４１０からなる好ましいタグメモリ２１２を示している。各タグエントリ４１０は、キャッシュラインアドレス４００のタグページアドレス４０２を含む。また、各タグエントリ４１０は、コヒーレンスステータスビット４１２およびパリティビット４１４を含む。パリティビット４１４は、周知のパリティエラー検出用のものである。
プロセッサ１１２がキャッシュラインアドレス４００にアクセスすると、コヒーレンスフィルタ２００はオフセットアドレス４０４を使用して特定のタグエントリ４１０を識別する。次に、コヒーレンスフィルタ２００がタグページアドレス４０２を識別されたタグエントリ４１０に格納する。例えば、左側のバス１０２上の第１のプロセッサ１１２ａが第１のタグページ内の第１のキャッシュラインアドレス４００にアクセスすると、左側のコヒーレンスフィルタ２００ａはキャッシュラインオフセットアドレス４０４を使用して第１のタグエントリ４１０を左側のタグメモリ２１２ａに配置する。次に、左側のコヒーレンスフィルタ２１２ａがタグページアドレス４０２を左側のタグメモリ２１２ａの第１のタグエントリ４１０に格納する。
キャッシュラインアドレス４００のタグページアドレス４０２を格納することに加え、タグエントリ４１０はキャッシュラインアドレス４００についての一組のコヒーレンスステータスビット４１２も格納する。好ましくは、タグエントリ４１０におけるコヒーレンスステータスビット４１２は好ましい３つのコヒーレンスステートすなわち、無効ステート、共有ステートまたは所有ステートを含む。これら３つのコヒーレンスステートは、２つのコヒーレンスステータスビット４１２で表される。以下の表に、コヒーレンスステータスビット４１２に割り当てられるコヒーレンスステートを定義する。
0004316016.tif 000003
２．  タグコントローラ
キャッシュラインアドレス４００をタグメモリ２１２に直接マッピングするための制御ロジックは、タグコントローラ３００内に設けられている。左側のバス１０２に割り当てられたタグコントローラ３００を左側のタグコントローラ３００ａと呼ぶ。右側のバス１０４に割り当てられたタグコントローラ３００を右側のタグコントローラ３００ｂと呼ぶ。Ｉ／Ｏバス１０６に割り当てられたタグコントローラ３００をＩ／Ｏタグコントローラ３００ｃと呼ぶ。例えば、左側のタグコントローラ３００は、キャッシュラインアドレス４００を左側のタグメモリ２１２ａに直接マッピングするダイレクトマッピングロジックを含む。
タグコントローラ３００における制御ロジックは、キャッシュラインをキャッシュメモリ１１４に直接マッピングするのに用いられる制御ロジックと同様である。このように、タグコントローラ３００は当業者らに周知のダイレクトマッピングロジックを利用する。しかしながら、これは４ウェイセットアソシアティブマッピングを用いている好ましいＰｅｎｔｉｕｍ  Ｐｒｏプロセッサ１１２のキャッシュ制御ロジックとは異なる。
下記においてより詳細に説明するように、コヒーレンスフィルタ２００は、タグメモリ２１２内のコヒーレンスステータス情報を一部利用して、クロスバストランザクションを実施するか否かを判断する。好ましい実施の形態では、各タグコントローラ３００は自己所有タグメモリ２１２および他のバスに割り当てられたタグメモリ２１２にも接続されている。各タグコントローラ３００はタグメモリ２１２のタグエントリ４１０にアクセスすることができるが、各タグコントローラ３００は自己に割り当てられたタグメモリ２１２のタグエントリを変更するのみである。例えば、左側のタグコントローラ３００ａは左側のタグメモリ２１２ａ、右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃのタグエントリ４１０にアクセスすることができるが、左側のタグコントローラ３００は左側のタグメモリ２１２ａのタグエントリ４１０のみ変更する。
例えば、左側のバス１０２が特定のキャッシュラインアドレス４００についてのバストランザクションを送信すると、左側のタグコントローラ３００ａはキャッシュラインアドレス４００を用いて対応するコヒーレンスステータスビット４１２を右側のタグメモリ２１２ａおよびＩ／Ｏタグメモリ２１２ｂから取得する。この例では、右側のコヒーレンスステータスビットを取得するために、キャッシュラインアドレス４００が右側のタグメモリ２１２ｂに直接マッピングされる。また、Ｉ／Ｏコヒーレンスステータスビット４１２を取得するために、キャッシュラインアドレスがＩ／Ｏタグメモリ２１２ｃに直接マッピングされる。本詳細な説明全体を通して、他のバスに割り当てられた他のタグメモリ２１２から取得したコヒーレンスステータスビット４１２を、リモートコヒーレンスステータスビット４１２と呼ぶ。左側のタグコントローラ３００ａがリモートコヒーレンスステータスビット４１２を取得すると、左側のタグコントローラ３００ａはこのリモートコヒーレンスステータスビット４１２をサイクルエンコーダ３０２に転送する。
３．  サイクルエンコーダ
各サイクルエンコーダ３０２は、バス１０２、１０４または１０６のうちの１本においてどのような種類のバストランザクションが発生しているかを判断する。左側のバス１０２を監視するために割り当てられたサイクルエンコーダ３０２を左側のサイクルエンコーダ３０２ａと呼ぶ。右側のバス１０４を監視するために割り当てられたサイクルエンコーダ３０２を右側のサイクルエンコーダ３０２ｂと呼ぶ。Ｉ／Ｏバス１０２を監視するために割り当てられたサイクルエンコーダ３０２をＩ／Ｏサイクルエンコーダ３０２ｃと呼ぶ。このように、各サイクルエンコーダ３０２は、自己が割り当てられたバス１０２、１０４または１０６に接続されたアドレスおよび制御線１０８を監視する。
好ましくは、サイクルエンコーダ３０２は、バス１０２、１０４および１０６で実現される特定のバスプロトコルに関連した周知の手法を利用してバス制御線を監視し、バストランザクションが主記憶装置１３２からデータを読み出しているかそれに対してデータを書き込んでいるかを判断する。好ましい実施の形態では、サイクルエンコーダ３０２は、周知の手法を用いてどのＰｅｎｔｉｕｍ  Ｐｒｏバストランザクションが主記憶装置１３２からデータを読み出しているかそれに対してデータを書き込んでいるかを判断する。サイクルエンコーダ３０２が自己に割り当てられたバスで発生しているバストランザクションのタイプを判断したら、サイクルエンコーダ３０２はそのバスサイクルのタイプをルールテーブル３０４に送信する。
４．  ルールテーブル
ここで、図３に示すルールテーブル３０４に注目すると、ルールテーブルはキャッシュコヒーレンスを維持するためにクロスバストランザクションを実施する時を判断する。好ましい実施の形態では、左側のバス１０２に割り当てられたルールテーブル３０４を左側のルールテーブル３０４ａと呼ぶ。右側のバス１０２に割り当てられたルールテーブル３０４を右側のルールテーブル３０４ｂと呼ぶ。Ｉ／Ｏバスに割り当てられたルールテーブル３０４をＩ／Ｏルールテーブル３０４ｃと呼ぶ。
各ルールテーブル３０４は、サイクルエンコーダ３０２から得られるバストランザクションタイプ情報およびリモートコヒーレンスステータスビット４１２を評価する。好ましい実施の形態では、各ルールテーブル３０４は、スタティックランダムアクセスメモリ（ＳＲＡＭ）内に保持された大きな真理値表である。各ルールテーブルのメモリ位置に格納されているのは、キャッシュコヒーレンスを保証するために実行する必要があるクロスバストランザクションおよびローカルバストランザクションのタイプである。
また、ルールテーブル３０４は、スヌープアクションも行う。好ましい実施の形態では、キャッシュラインのコピーを共有していることがリモートタグメモリによって示されると、ルールテーブル３０４はＨＩＴ＃信号をアサートする。ＨＩＴ＃信号をアサートすることで、リモートバス上の１つまたは複数のキャッシュメモリがキャッシュラインのコピーを共有していることが示される。ルールテーブル３０４はまた、他のバスでの以後のコードリードトランザクションによってクロスバストラフィックが生成されないように、コードリードトランザクションを強制的に共有ステートにするためにＨＩＴ＃信号もアサートする。
キャッシュコヒーレンスを保証するのに必要な特定のクロスバストランザクションコードが、システムアクセスコントローラ１３０の制御下でルールテーブル３０４にロードされる。好ましいマルチバスシステム１００は、システムの初期化中にクロスバストランザクションコードをルールテーブル３０４にロードする。クロスバストランザクションコードは変更可能なものであるため、クロスバストランザクションは異なるマルチバスシステム１００に対して柔軟になることができる。
Ｂ．  バッファマネージャ
図１および図２に示すようなバッファマネージャ２１０、中央リクエストリスト２０８およびデータインタフェースバッファ１３４は、複数のバス間での通信を最適化する。好ましい実施の形態では、中央リクエストリスト２０８、バッファマネージャ２１０およびデータインタフェースバッファ１３４は、バス１０２、１０４および１０６のいずれからもアクセス可能なメモリセルのマルチポートプール（図示せず）を含む。有利なことに、バス１０２、１０４または１０６はいずれも、独立接続パスを使用せずに他のバス１０２、１０４または１０６に対して読み書きを行うことができる。
好ましい実施の形態では、各バストランザクションに関連した情報はさらに３つの部分に区分けされ、アドレスセル、リクエストセルおよびデータセルと呼ばれる３つの異なるメモリセルに格納されている。したがって、各データセル、各リクエストセルおよび各アドレスセルの間に１対１の対応が存在する。下記においてより詳細に説明するように、アドレスセルはバッファマネージャ２１０内に、リクエストセルは中央リクエストリスト２０８内に、データセルはデータインタフェースバッファ１３４内に設けられている。
好ましいバッファマネージャ２１０を図５Ａおよび図５Ｂに示す。図５Ａに注目すると、バッファマネージャ２１０は、アドレスセル５００のプールと、アドレスセルのプライオリティエンコーダ５０４と、左側のファーストインファーストアウト（ＦＩＦＯ）メモリ５０６ａと、Ｉ／Ｏ  ＦＩＦＯ５０６ｂと、右側のＦＩＦＯ５０６ｃとを備えている。各アドレスセル５００はマルチポートであり、アドレスセルのプライオリティエンコーダ５０４、バスマスタ２０２、バススレーブ２０４、メモリコントローラ２０６と通信を行う他、図５Ｂに示されるように、比較器５１０とも通信を行う。
好ましいバッファマネージャ２１０は、６４個のアドレスセル５００を含む。図５Ａに示されるように、各アドレスセル５００は、「使用中」ビット５０２、メモリアドレス５０４および一組のデータセルステータスビット５０５を含む。使用中ビット５０２は、特定のアドレスセル５００が利用できるか否かを示している。好ましい実施の形態では、使用中ビット５０２は、アドレスセル５００が使用中であるかフリーであるかを示すように設定されている。メモリアドレス５０４はメモリアドレス５０４を含み、データセルステータスビット５０５はバストランザクションのタイプを含む。特に、データセルステータスビット５０５は、無効バストランザクションが行われるか否かを判断する。
ここで、アドレスセルのプライオリティエンコーダ５０４に注目すると、アドレスセルのプライオリティエンコーダ５０４は、どのアドレスセル５００が使用中で、どのアドレスセル５００がフリーであるかを判断し、新たなバストランザクション情報を受信する。好ましい実施の形態では、アドレスセルのプライオリティエンコーダ５０４におけるロジックが、各アドレスセル５００における使用中ビット５０２を評価することによってどのアドレスセル５００がフリーであるかを判断する。使用中ビット５０２が設定されている場合には、そのアドレスセル５００は使用中である。使用中ビット５０２が設定されていなければ、そのアドレスセルはフリーである。フリーのセルは総当たり式に選択される。
アドレスセルのプライオリティエンコーダ５０４は、どのアドレスセル５００がフリーであるかを判断するだけでなく、異なるバス１０２、１０４および１０６にフリーのアドレスセル５００を割り当てる。好ましくは、アドレスセルのプライオリティエンコーダ５０４がフリーのアドレスセル５００を総当たり式に異なるバス１０２、１０４および１０６に割り当てる。下記においてより詳細に説明するように、バストランザクション情報がフリーアドレスセル５００に格納されている場合、使用中ビット５０２が設定され、アドレスセル５００がフリーではないことが示される。
例えば、第１、第２および第３のアドレスセル５００がフリーであると仮定する。好ましいプライオリティエンコーダ５０４は、第１、第２および第３のアドレスセル５００がフリーであると判断し、第１のアドレスセル５００を左側のバス１０２に、第２のアドレスセル５００を右側のバス１０４に、第３のアドレスセル５００をＩ／Ｏバス１０６に割り当てる。４番目のアドレスセル５００がフリーになると、アドレスセルのプライオリティエンコーダ５０４は左側のバス１０２に戻り、この第４のアドレスセル５００を左側のバス５００に割り当てる。好ましいアドレスセルのプライオリティエンコーダ５０４はフリーのアドレスセルを異なるバスに割り当てるが、アドレスセルのプライオリティエンコーダ５０４を様々なアロケーションスキームに利用してフリーのアドレスセル５００を異なるバス１０２、１０４および１０６に割り当てることも可能であるのは当業者であれば理解できよう。
ここで、バッファマネージャにおけるＦＩＦＯメモリ５０６に注目すると、ＦＩＦＯメモリ５０６は、割り当てられたアドレスセル５００を識別するアドレスセル識別子を一時的に格納する。アドレスセル識別子は、割り当てられたアドレスセル５００のメモリ位置を含むデータ変数である。好ましい実施の形態では、アドレスセル識別子は６４個のアドレスセル５０４を識別する。以下においてより詳細に説明するように、バスマスタ２０２はＦＩＦＯメモリ５０６内のアドレスセル識別子を利用して、このアドレスセル識別子によって識別されたアドレスセルメモリ位置にアクセスする。
好ましい実施の形態では、各ＦＩＦＯメモリ５０６はバススレーブ２０４およびコヒーレンスフィルタ２００に対して出力を行う。このように、左側のＦＩＦＯメモリ５０６ａは左側のバススレーブ２０４ａおよび左側のコヒーレンスフィルタ２００ａに対して出力を行う。右側のＦＩＦＯメモリ５０６ｂは、右側のバススレーブ２０４ｂおよび右側のコヒーレンスフィルタ２００ｂに対して出力を行う。Ｉ／Ｏ  ＦＩＦＯメモリ５０６ｃは、Ｉ／Ｏバススレーブ２０４ｃおよびＩ／Ｏコヒーレンスフィルタ２００ｃに対して出力を行う。複数のバススレーブ２０４のうちの１つまたは複数のコヒーレンスフィルタ２００のうちの１つでバストランザクションを他のバスに送信したい場合、自己が接続されたＦＩＦＯメモリ５０６からアドレスセル識別子を１つ取得する。
このように、好ましいバッファマネージャ２１０は、全てのバス１０２、１０４および１０６を相互接続するアドレスセル５００のプールを提供する。バスのパスを別々にするのではなくアドレスセル５００の上記のようなプールを提供することで、システムの複雑さが少なくなる。さらに、アドレスセルプライオリティエンコーダ５０４およびＦＩＦＯメモリ５０６によって、フリーアドレスセル５００がバス１０２、１０４および１０６に等しく分配されることが保証される。
図５Ｂに示す本発明の他の態様において、好ましいバッファマネージャ２１０は、アドレス衝突を識別する複数のアドレス比較器５１０を含む。一般に、アドレス衝突は、２つの異なるバストランザクションが同一のデータ値に関連し、同時に発生した時に生じる。このような状況では、２つのアドレスセル５００が、２つの異なるバストランザクションについてアドレスセル５００に同一のメモリアドレス５０４を含む可能性がある。このような状況では、不適切なバストランザクションが起こり得る。
複数のバススレーブ２０４のうち１つがバストランザクションを受信すると、バススレーブ２０４はそのバストランザクションに関連したアドレスを、バススレーブ２０４と同一のバスに割り当てられたアドレス比較器５１０に転送する。アドレス比較器５１０は、新たなメモリアドレス５０４と使用中アドレスセル５００内の全てのメモリアドレス５０４とを比較する。使用中アドレスセル５００において同一のメモリアドレスが検出されると、アドレス比較器５１０はバススレーブ２０４にアドレス衝突が存在することを通知する出力を生成する。これを受けて、バススレーブ２０４は、アドレス衝突を生み出したバストランザクションを開始したプロセッサ１１２にリトライ信号を送信する。よって、プロセッサ１１２はバストランザクションを後で開始する。
好ましい実施の形態では、各バスに一組のアドレス比較器５１０が割り当てられている。このように、左側のアドレス比較器５１０ａの組は左側のバス１０２に割り当てられている。右側のアドレス比較器５１０ｃの組は右側のバス１０４に割り当てられている。Ｉ／Ｏアドレス比較器５１０の組はＩ／Ｏバス１０６に割り当てられてる。バススレーブ２０４が新たなメモリアドレス５０４を受信すると、バススレーブ２０４が新たなメモリアドレス５０４をアドレス比較器５１０に転送する。次に、アドレス比較器５０１が使用中アドレスセル５００に存在するメモリアドレス５０４を評価し、アドレス衝突が存在するか否かを判断する。
例えば、右側のバススレーブ２０２ｂはＩ／Ｏトランザクションを受信し、これをＩ／Ｏバス１０６上のＩ／Ｏブリッジ１２０のうちの１つに送る。Ｉ／Ｏトランザクションに関連したメモリアドレスの受信時、右側のバススレーブ２０２ｂはこのメモリアドレスを右側のアドレス比較器５１０ｃに転送する。右側のアドレス比較器５１０ｃは、このメモリアドレスと使用中アドレスセル５００内の既存のメモリアドレス５０４とを比較する。メモリアドレスのコピーが使用中アドレスセル５００に存在すると、アドレス比較器はアドレス衝突が存在する右側のバススレーブ２０２ｂに信号を返送する。この例では、右側のバススレーブ２０２ｂはプロセッサ１１２ｃまたは１１２ｄに対してＩ／Ｏトランザクションを後でリトライするように指示をする。
複数のタグメモリ２１２のうちの１つでエントリを無効にする無効バストランザクションを行う必要がある場合、バスが使用中ではなくなるまで無効動作を先送りして遅らせると望ましい。１つの方法として、古いキャッシュラインアドレス（無効にされるキャッシュラインアドレス）をバッファマネージャに格納することが挙げられる。好ましい実施の形態では、バッファマネージャ２１０におけるアドレスセル５００は、キャッシュラインに接続されたタグページアドレス４０２およびオフセットアドレス４０４を含むキャッシュラインのメモリアドレス全体を含む。古いキャッシュラインアドレスを複数のアドレスセル５００のうちの１つに加えることで、古いキャッシュラインアドレスが実際には無効になっていなくても、新たなバストランザクションでマルチバスシステム１００を進めることができる。
もう１つのバストランザクションがバッファマネージャ２１０内に存在する古いキャッシュラインアドレス４００に関連していると仮定する。複数のバススレーブ２０４のうちの１つがバストランザクションを受信すると、バススレーブ２０４はこのバストランザクションに関連したアドレスをアドレス比較器５１０に転送する。アドレス比較器５１０は、バストランザクションに関連したオフセットアドレス４０４と古いキャッシュラインアドレスのオフセットアドレス４０４とを比較する。アドレス衝突が存在する場合には、比較器はデータセルのステータスビット５０５を評価する。データセルのステータスビット５０５によって古いキャッシュラインアドレスを無効にする必要があることが示されると、古いキャッシュラインアドレス４００を無効にできるようになるまで新たなバストランザクションが強制的にリトライされる。この方法の他の実施の形態については、「他の実施の形態」のセクションで後述する。
Ｃ．  中央リクエストリスト
ここで、図６に示されるような好ましい中央リクエストリスト２０８に注目すると、中央リクエストリスト２０８は、リクエストセル６００のプールと、左側のバスプライオリティエンコーダ６０２ａと、右側のバスプライオリティエンコーダ６０２ｂと、Ｉ／Ｏバスプライオリティエンコーダ６０２ｃとを含む。各リクエストセル６００はマルチポートであり、アドレスセルのプライオリティエンコーダ６０２の各々と通信を行う。好ましい中央リクエストリスト２０８には、６４個のリクエストセル６００がある。さらに、６４個のアドレスセル５００と６４個のリクエストセル６００との間には１対１の対応が存在する。
各リクエストセル６００は、ターゲットバス識別子６０４と、バストランザクションコード６０６と、オーナーバス識別子６０８とを含む。ターゲットバス識別子６０４は、宛先のバス１０２、１０４または１０６を識別する。下記においてより詳細に説明するように、バス識別子６０４は予め規定されているのではなく、好ましい実施の形態では必要に応じてバス識別子６０４を設定し、右側のバス１０２、左側のバス１０４またはＩ／Ｏバス１０６のいずれかを識別する。例えば、ターゲットバス識別子６０４は、バストランザクションコード６０６が右側のバス１０４用であると指定することができる。一方、バストランザクションコードは、宛先のバスで行うバストランザクションのタイプを識別する。好ましい実施の形態では、バストランザクションコード６０６によって識別されたバストランザクションをバスマスタ２０２が行う。オーナーバス識別子６０８は開始したバスを識別する。例えば、オーナーバス識別子６０４は、左側のバス１０２で開始されたバストランザクションコード６０６を示すことができる。
バスプライオリティエンコーダは、各リクエストセル６００のターゲットバス識別子６０４を評価し、どのリクエストセルが異なるバスを指定しているかを判断する。次に、これらのバス１０２、１０４または１０６のうちの１本に関連したバスマスタ２０２が、特定のリクエストセル６００において識別されたバストランザクションを行う。例えば、左側のバスプライオリティエンコーダ６０２ａは全てのターゲットバス識別子６０４を評価して、どのリクエストセル６００が左側のバス１０２用のものか判断する。右側のバスプライオリティエンコーダ６０２ｂは、全てのターゲットバス識別子６０４を評価して、どのリクエストセル６００が右側のバス１０４用のものか判断する。Ｉ／Ｏバスプライオリティエンコーダ６０２ｃは、全てのターゲットバス識別子６０４を評価して、どのリクエストセル６００がＩ／Ｏバス１０６用のものか判断する。
また、宛先のバス１０２、１０４および１０６を識別することに加えて、各バスプライオリティエンコーダ６０２は、特定のバス１０２、１０４または１０６に関連したバスリクエストセル５００のうち、どのバスリクエストセルの優先度が最も高いかを判断する。好ましい実施の形態では、各バスプライオリティエンコーダ６０２は、総当たりロジックを用いて優先度が最も高いバスリクエストセル６００を判断する。各バスプライオリティエンコーダ６０２が自己に割り当てられたバスに優先度の最も高いリクエストセル６００を転送すると、各バスプライオリティエンコーダ６０２は優先度の割り当てを各リクエストセル６００に対してローテーションする。総当たりロジックでは、各バスプライオリティエンコーダ６０２が全てのバスリクエストセル６００に対して連続的に最も高い優先度を割り当てることができる。このような総当たりロジックは当業者間で周知である。
例えば、複数のリクエストセル６００のうちの２つが右側のバス１０４用のものであることを右側のバスプライオリティエンコーダ６０２ｂが識別したと仮定する。右側のバスプライオリティエンコーダ６０２ｂは、第１のリクエストセル６００に最も高い優先度を割り当て、第１のリクエストセル識別子を右側のバスマスタ２０２ｂに送る。次に、右側のバスプライオリティエンコーダ６０２ｂは第２のリクエストセル６００に最も高い優先度を割り当て、第２のリクエストセル識別子を右側のバスマスタ２０２ｂに送る。右側のバスプライオリティエンコーダ６０２ｂが右側のバス１０４に割り当てられたリクエストセル６００の最後に達すると、右側のバスプライオリティエンコーダはリクエストセル５００のプールの先頭に戻る。
このように、中央リクエストリスト２０８は、全てのバス１０２、１０４および１０６を相互接続するリクエストセル６００のプールを提供する。このようなリクエストセル６００のプールは、バス接続パスを分離する場合と比べて、システムの複雑さを軽減する。さらに、中央リクエストリスト２０８におけるバスプライオリティエンコーダ６０２において、リクエストセルにおける各バストランザクションがバス１０２、１０４および１０６によって行うことができる。
ＩＶ．  データインタフェースバッファ
ここで、図７に示されるような好ましいデータインタフェースバッファ１３４に注目すると、データインタフェースバッファ１３４は、データセル７００のプールと、制御およびインデックス作成メカニズム７０２とを含む。各リクエストセル６００はマルチポートであり、奇数主記憶装置モジュール１３２ａおよび偶数主記憶装置モジュール１３２ｂに接続されたデータ線データ線１１０ａ、１１０ｂと１１０ｃ及び１４２ａと１４２ｂと通信を行う。好ましい中央リクエストリスト２０８には、６４個のデータセル７００がある。さらに、６４個のデータセル７００と、６４個のリクエストセル６００と、６４個のアドレスセル５００との間には１対１の対応が存在する。各データセル７００は、バストランザクションに関連したデータ値を含む。
制御およびインデックス作成メカニズム７０２は、バススレーブ２０４からＤＩＢ制御線１４０を受け取る。ＤＩＢ制御線１４０は、特定のデータセル７００およびバス１０２、１０４または１０６のうちの１本を識別する。例えば、Ｉ／Ｏバススレーブ２０４が新たなバストランザクションを複数のアドレスセル５００のうちの１つと複数のリクエストセル６００のうちの１つに加えると、Ｉ／Ｏバススレーブ２０４もその新たなバストランザクションに関連したデータを対応するデータセル７００に加える。この例では、Ｉ／Ｏバススレーブ２０４はＤＩＢ制御線をアサートし、適切なデータセル７００を識別する。制御およびインデックス作成メカニズム７０２は次に、適切なデータセル７００をイネーブルにしてＩ／Ｏデータ線１１０ｃからデータを受信する。
このように、データインタフェースバッファは、全てのバス１０２、１０４または１０６からアクセス可能なデータセル７００のプールを提供する。バスを別々に相互接続するのではなくデータセル７００の上記のようなプールを提供することで、システムの複雑さが少なくなり、パフォーマンスが改善される。
Ｖ．  キャッシュコヒーレンス維持
コヒーレンスフィルタ２００によって監視されるバストランザクションは、バスリードラインコマンドおよびバスリード無効コマンドを含む。バスリードライン（ＢＲＬ）コマンドは、インストラクションコードまたはデータのキャッシュラインを主記憶装置１３２から読み出して無効にする。バスリード無効ライン（ＢＲＩＬ）コマンドは、キャッシュラインを無効にする。好ましいルールテーブル３０４ではこれらのバスコマンドに適応しているが、ルールテーブル３０４は他の異なるバスコマンドにも適応可能であり、好ましい実施の形態のバスコマンドに限定されないことは当業者であれば理解できよう。
Ａ．  バスリードラインコマンド処理
図８は、バス１０２、１０４または１０６のうちの１本がバスリードライン（ＢＲＬ）コマンドを実行する際にキャッシュコヒーレンスを維持するためのフローチャートを示している。スタートブロック８００から開始して、複数のプロセッサ１１２のうちの１つがＢＲＬコマンドを実行する。ＢＲＬコマンドの実行中、プロセッサ１１２が、所望のキャッシュラインのキャッシュラインアドレス４００を自己が割り当てられたコヒーレンスフィルタ２００およびバススレーブ２０４に送信する。
バススレーブ２０４がキャッシュラインアドレスを受信すると、バススレーブ２０４はこのキャッシュラインアドレスを同一のバスに割り当てられたアドレス比較器５１０に転送する。アドレス比較器５１０は、オフセットアドレス４０４と、使用中アドレスセル５００に存在するメモリアドレス５０４のオフセット部分とを比較し、アドレス衝突の可能性があるか否かを判断する。アドレス比較器５１０はまた、データセルのステータスビット５０５を評価し、アドレス衝突を生成したアドレスセル５００が無効トランザクションに関連しているか否か確認する。関連している場合には、アドレス比較器５１０はアドレス衝突信号をバススレーブ２０４に送信する。次に、バススレーブ２０４が要求を出したプロセッサ１１２に対してＢＲＬコマンドを先送りしてリトライするよう指示する。
アドレス衝突が存在することがアドレス比較器によって示されなかった場合には、好ましい実施の形態はブロック８０２に進み、バス１０２、１０４または１０６がＢＲＬコマンドを実行していることをサイクルエンコーダ３０２が判断する。また、バス１０２、１０４または１０６に割り当てられたタグコントローラ３００がＢＲＬコマンドにおいて識別されたキャッシュラインアドレス４００を使用し、他のバス１０２、１０４および１０６（リモートタグメモリ２１２）に割り当てられたタグメモリ２１２内のキャッシュラインアドレス４００にアクセスする。リモートタグメモリ２１２は、リモートキャッシュラインアドレス４００が無効ステート、共有ステートまたは所有ステートのいずれにあるかを示すリモートコヒーレンスステータスビット４１２を返送する。
特定のキャッシュラインアドレスを所有ステートで含むリモートタグメモリ２１２は１つしかない。しかしながら、２つ以上のリモートタグメモリ２１２が特定のキャッシュラインアドレスを共有または無効ステートで含んでもよい。１つのリモートタグメモリ２１２がキャッシュラインアドレスのコピーを共有ステートで含み、別のリモートタグメモリ３００が同一のキャッシュラインアドレスのコピーを無効ステートで含む場合には、共有ステートにあるコヒーレンスステータスビット４１２が指揮をとる。下記においてより詳細に説明するように、２つ以上のリモートタグメモリ３００が特定のキャッシュラインアドレスのコピーを共有ステートで含む場合には、コヒーレンスルール３０４は２つ以上のリモートバス１０２、１０４または１０６においてリモートバストランザクションを行い、キャッシュコヒーレンスを保証することができる。また、リモートタグメモリ３００の中には特定のキャッシュラインアドレス４００を含むものが存在しない場合には、キャッシュラインアドレス４００に関連したリモートコヒーレンスステータスビット４１２が無効ステートであるかのように扱われる。
例えば、左側のバス１０２上の第１のプロセッサ１１２ａがブロック８０２における特定のキャッシュラインアドレス４００についてのＢＲＬコマンドを生成し、左側のサイクルエンコーダ３０２ａは左側のバスでＢＲＬコマンドが実行されていると判断する。また、左側のタグコントローラ３００がキャッシュラインアドレス４００を用いて右側のリモートタグメモリ２１２ｂおよびリモートＩ／Ｏタグメモリ２１２ｃにアクセスする。タグコントローラ３００は、右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃから、キャッシュラインアドレス４００が右側のタグメモリ２１２ｂにあるか否か、Ｉ／Ｏタグメモリ２１２ｃが無効ステート、共有ステートまたは所有ステートのいずれであるかを示すリモートコヒーレンスステータスビット４１２を取得する。右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃのいずれもキャッシュラインアドレス４００を含んでいない場合には、左側のタグコントローラ３００ａがリモートコヒーレンスステータスビット４１２を無効ステートであるかのように扱う。
ここで、ローカルおよびリモート指定を用いている時の好ましいルールテーブル３０４の動作に注目すると、ローカルバス１０２、１０４または１０６に接続されたサイクルエンコーダ３０２は、ローカルルールテーブル３０４にバストランザクション（ＢＲＬコマンド）のタイプおよびリモートキャッシュステータスビット４１２のステータスを送信する。リモートキャッシュラインアドレス４００が無効ステートにあることがリモートコヒーレンスステータスビット４１２によって示されると、ローカルルールテーブル３０４はブロック８０４に進む。好ましい実施の形態では、リモートコヒーレンスステータスビット４１２が無効ステートにあると、ローカルルールテーブル３０４はリモートバス１０２、１０４または１０６のいずれでもＢＲＩＬクロスバストランザクションを生成しない。代わりに、ローカルルールテーブル３０４はキャッシュラインアドレスの上位集合４００をローカルタグメモリ３００において維持する。
ブロック８０４に進むと、ローカルプロセッサ１１２は、自己の内部キャッシュメモリ１１４に対して問い合わせを行い、ローカルプロセッサ１１２の中に所望のキャッシュラインのコピーを持っているものがあるか否かを判断する。好ましい実施の形態では、複数のプロセッサ１１２のうちの１つは、変更後のキャッシュラインがプロセッサのキャッシュメモリ１１４に存在することがバススヌープ動作によって示されるとＨＩＴＭ＃信号をアサートする。ＨＩＴＭ＃信号は複数のアドレスおよび制御線１０８のうちの１本であり、最新のキャッシュラインを有するプロセッサ１１２はキャッシュラインを主記憶装置１３２に書き戻す必要があるということを示している。
ブロック８０６では、変更後のキャッシュラインを有するローカルプロセッサ１１２がバストランザクションに応答し、同時に変更後のキャッシュラインを主記憶装置１３２に書き戻すことによって主記憶装置１３２を更新する。ブロック８０８に進むと、ローカルルールテーブル３０４はローカルタグコントローラ３００に対して、ローカルタグメモリ２１２内のコヒーレンスステータスビット４１２を共有ステートに設定するよう指示する。次に、ローカルルールテーブル３０４はＥＮＤブロック８１０に進む。
ブロック８０４に戻り、ローカルプロセッサ１１２がキャッシュラインの変更後のコピーを含まない場合には、ルールテーブル３０４はブロック８１２に進む。ブロック８１２では、ローカルルールテーブル３０４は、ローカルバス１０２、１０４または１０６上のＨＩＴ＃信号を評価する。上述したように、ローカルプロセッサ１１２は、ローカルプロセッサ１１２が自己のキャッシュメモリ１１４内に未変更のキャッシュラインのコピーを含んでいる場合にＨＩＴ＃信号を生成する。ローカルプロセッサ１１２が未変更のキャッシュラインのコピーを確かに含んでいる場合には、ローカルルールテーブル３０４はブロック８１４に進む。
ブロック８１４では、ローカルバススレーブ２０４が主記憶装置１３２からキャッシュラインを取得する。キャッシュラインアドレスが奇数である場合には、ローカルバススレーブ２０４は奇数主記憶装置１３２ａからキャッシュラインを取得する。キャッシュラインアドレスが偶数である場合には、ローカルバススレーブ２０４は偶数主記憶装置モジュール１３２ｂからキャッシュラインを取得する。ローカルバススレーブ２０４は次に要求を出しているプロセッサ１１２にキャッシュラインを送信する。
ブロック８０８に進み、ローカルルールテーブル３０４はローカルタグコントローラ３００に対してローカルタグメモリ３００内のコヒーレンスステータスビット４１２を共有ステートに設定するよう指示する。ローカルルールテーブル３０４は次に、ＥＮＤブロック８１０に進む。
ブロック８１２に戻り、ローカルプロセッサ１１２がＨＩＴ＃信号またはＨＩＴＭ＃信号をアサートしないと、ブロック８１６によって示されるようにキャッシュラインはローカルプロセッサ１１２には存在しない。ブロック８１８に進み、ローカルタグメモリ２１２がキャッシュラインアドレス４００のコピーを含まない場合、ルールテーブル３０４はこのキャッシュラインアドレス４００をローカルタグメモリ２１２に加える。上述したように、ローカルタグメモリは既存のキャッシュラインアドレスをローカルタグメモリから追い出して新たなキャッシュラインアドレスのために空間を確保する必要がある場合がある。そのような場合には、古いキャッシュラインアドレスをまず無効にし、その後で新たなキャッシュラインアドレスをローカルタグメモリに追加する。次に左側のバススレーブが主記憶装置１３２から所望のキャッシュラインを取得し、要求を出しているプロセッサ１１２にこれを送信する。
ローカルルールテーブル３０４はブロック８２２に進み、ローカルタグコントローラ３００にローカルタグメモリ２１２のキャッシュラインのコヒーレンスステータスビット４１２を所有ステートに設定するよう指示する。しかしながら、ローカルバス上のローカルプロセッサ１１２のうちの１つがＨＩＴ＃信号をアサートすると、ローカルタグメモリ２１２は共有に設定される。また、ＢＲＬコマンドがコード用でリモートステータスが所有されていない場合には、ルールテーブル３０４はＨＩＴ＃信号をアサートする。そのときにＨＩＴＭ＃が検出されなければ、ＢＲＬコマンドを開始したプロセッサは自己の内部キャッシュステータスを共有にマークする。ＨＩＴＭ＃信号がアサートされると、内在的な書き戻しが行われ、ローカルタグメモリ２１２が共有に設定される。ローカルルールテーブル３０４はＥＮＤブロック８１０に進む。
ブロック８０２に戻り、以下、リモートタグメモリ３００によって、リモートキャッシュラインアドレス４００が共有ステートにあることが示された場合に何が起こるかについて的を絞って説明する。リモートコヒーレンスステータスビット４１２によってキャッシュラインアドレス４００が共有ステートにあることが示されると、ローカルルールテーブル３０４はリモートバス１０２、１０４または１０６上にＢＲＬクロスバストランザクションを生成しない。代わりに、ローカルルールテーブル３０４は主記憶装置１３２から所望のキャッシュラインを取得し、ローカルタグメモリ３００を更新する。
ブロック８３０に進み、コードリードのために、ローカルルールテーブル３０４は、ローカルバス１０２、１０４または１０６にＨＩＴ＃信号をアサートする。次に、ローカルルールテーブル３０４はブロック８３２に進む。ブロック８３２では、ローカルルールテーブル３０４は主記憶装置１３２から所望のキャッシュラインを取得する。所望のキャッシュラインアドレスがローカルタグメモリ２１２内に存在しない場合には、タグコントローラは新たなキャッシュラインアドレス４００をローカルタグメモリ２１２に追加する。上述したように、タグコントローラ３００は古いキャッシュラインアドレス４００のうちの１つを追い出して新たなキャッシュラインアドレス４００のために空間を確保する場合もある。
８０８が十分に満足されるように進み、ローカルルールテーブル３０４はキャッシュラインのコヒーレンスステータスビット４１２を共有に設定してＥＮＤブロック６１０に進む。
ブロック８０２に戻り、以下、複数のリモートタグメモリ２１２のうちの１つによって、複数のリモートキャッシュラインアドレス４００のうちの１つが所有ステートにあることが示された場合に何が起こるかについて的を絞って説明する。リモートコヒーレンスステータスビット４１２によってリモートキャッシュラインアドレス４００のうちの１つが所有ステートにあることが示されると、リモートバスは所望のキャッシュラインの最新バージョンを有しているため、最新のキャッシュラインをリモートバスから取得しなければならない。ブロック８０２では、ルールテーブル３０４がキャッシュコヒーレンスを保証するのに必要なＢＲＬクロスバストランザクションを生成する。好ましい無効、共有および所有プロトコルでは、特定の時点で時を違えずキャッシュラインを所有できるバスは１本のみである。このように、リモートキャッシュラインを異なるコヒーレンスステートに変更しなければならない。
ブロック８４０に進み、ローカルルールテーブル３０４は、ローカルＢＲＬコマンドを遅延にできるか否かを判断する。ローカルＢＲＬコマンドを遅延することで、ローカルバスがバストランザクションの送信を続けることができる。上述したように、バストランザクションを発行するプロセッサ１０４は、そのＤＥＮ＃信号をアサートすることによってバストランザクションが遅延可能なものであるか否かを示す。ＤＥＮ＃信号がアサートされると、ローカルルールテーブル３０４はブロック８４２に進み、ローカルバススレーブ２０４に対してローカルＢＲＬコマンドを遅延するよう指示する。ブロック８４４に進み、ローカルルールテーブル３０４は次に、ＢＲＬコマンドをリモートバス１０２、１０４または１０６のうちの１本で行うよう本発明に指示する。
ブロック８４０に戻り、バストランザクションを遅延できない場合には、ローカルルールテーブル３０４はブロック８４６に進み、ローカルバススレーブ２０４に対してローカルＢＲＬコマンドを引きとめるよう指示する。ブロック８４４に進み、ローカルルールテーブル３０４は次に、リモートバス１０２、１０４または１０６のうちの１本でＢＲＬコマンドを実行するよう本発明に対して指示する。
ブロック８４４では、バッファマネージャ２１０および中央リクエストリスト２０８がＢＲＬコマンドを所望のバスに転送する。例えば、左側のバス１０２の第１のプロセッサ１１２ａが特定のキャッシュラインアドレスに対するＢＲＬコマンドを実行すると仮定する。さらに、キャッシュラインアドレス４００に対して右側のバスコヒーレンスステータスビット４１２がキャッシュラインアドレス４００が所有ステートであることを示す。
この例では、キャッシュコヒーレンスを保証するためには右側のバス１０４上のＢＲＬコマンドが必要であると左側のルールテーブル３０４ａが判断する。左側のルールテーブル３０４ａは次に、左側のＦＩＦＯ５０６ａからフリーアドレスセル識別子を取得する。左側のルールテーブル３０４ａは、アドレスセル識別子によって識別されるアドレスセル５０６ａにアクセスし、キャッシュラインアドレス４００をメモリアドレス５０４に入力する。また、左側のルールテーブル３０４ａが対応するリクエストセル６００にアクセスし、右側のバス識別子をターゲットバス識別子６０４に格納し、ＢＲＬコマンドをバストランザクションコード６０６に格納し、左側のバス識別子をオーナーバス識別子６０８に格納する。
右側のバスプライオリティエンコーダ６０２ｂがリクエストセル６００に対して最も高い優先度を割り当てたら、右側のバスマスタ２０２ｂは右側のバス１０４上でＢＲＬコマンドを実行する。ブロック８４８に進み、右側のプロセッサが右側のバス１０４上のＢＲＬコマンドに応答する。ブロック８４８では、右側のプロセッサが、自己のキャッシュメモリ１１４内にあるキャッシュラインアドレスのステータスを評価する。右側のプロセッサが所望のキャッシュラインアドレスのコピーを有していなければ、右側のプロセッサはＨＩＴ＃およびＨＩＴＭ＃信号をアサートしない。
ブロック８５０に進み、右側のタグコントローラ３００ｂが、右側のタグメモリ２１２ｂ内のコヒーレンスステータスビット４１２を無効ステートに設定する。ローカルバストランザクションが遅延されている場合には、左側のバススレーブ２０２ａが左側のバス１０２上に遅延リプライトランザクションを発行する。ブロック８１８に進み、左側のバススレーブ２０２ａが主記憶装置１３２から所望のキャッシュラインを取得し、左側のバス１０２上の要求を出しているプロセッサ１１２にこれを送信する。左側のルールテーブル３０４ａは次に、ブロック８２２または８２４を介して進み、上述したようにしてＥＮＤブロック８１０に達する。
さて、ブロック８４８に戻り、右側のプロセッサ１１２ｃまたは１１２ｄがキャッシュラインの未変更コピーを含む場合には、これらのプロセッサは右側のＨＩＴ＃信号をアサートし、本発明はブロック８５２に進む。ブロック８５２では、右側のタグコントローラ３００ｂが右側のタグメモリ２１２ｂ内のコヒーレンスステータスビット４１２を共有ステートに設定する。
ブロック８５４に進み、左側のタグメモリ２１２ｂがキャッシュラインアドレス４００のコピーを有していない場合には、左側のルールテーブル３０４は左側のタグコントローラ３００ａに対してこのキャッシュラインアドレス４００を左側のタグメモリ２１２ａに追加するよう指示する。上述したように、ローカルタグメモリは既存のキャッシュラインアドレス４００を左側のタグメモリから追い出し、新たなキャッシュラインアドレスのために空間を確保しなければならない場合がある。このような場合には、古いキャッシュラインアドレスをまず無効にした上で、新たなキャッシュラインアドレスを左側のタグメモリに追加する。
ブロック８５２にいる間に、左側のバススレーブが主記憶装置１３２から所望のキャッシュラインを取得し、左側のバス１０２上で要求を出しているプロセッサ１１２ａにこれを送信する。ブロック８０８に進み、左側のルールテーブル３０４ａは左側のタグコントローラ３００ａに対して左側のタグメモリ２１２ａ内のコヒーレンスステータスビット４１２を共有に設定するよう指示し、ＥＮＤブロック８１０に進む。
ここで、ブロック８４８に戻り、右側のプロセッサ１１２ｃまたは１１２ｄのうちの一方が自己のキャッシュメモリ１１４にキャッシュラインの変更されたコピーを有する場合には、右側のプロセッサ１１２ｃまたは１１２ｄは右側のＨＩＴＭ＃信号をアサートする。ブロック８５６に進み、変更後のキャッシュラインを左側のバス１０２に供給する。特に、変更後のキャッシュラインをデータインタフェースバッファ１３４内の対応するデータセル７００にロードし、続いてオーナーバス識別子６０８によって識別される左側のバス１０２に送信する。次に、（オリジナルのバストランザクションが遅延可能である場合には遅延されたレスポンスと一緒に）変更後のキャッシュラインを左側のバス１０２に送信する左側のバススレーブ２０４ａがデータセル７００にアクセスする。また、右側のタグコントローラ３００ｂが右側のタグメモリ内のコヒーレンスステータスビットを共有ステートに設定する。
ステート８５８に進み、応答の一部として、変更後のキャッシュラインが主記憶装置１３２に書き戻される。次に、本発明は上述したようにブロック８５２、８５４、ブロック８０８およびＥＮＤブロック８１０に進む。このように、本発明は、キャッシュコヒーレンスを維持するために必要な可能性がある場合にＢＲＬクロスバストランザクションを行う。上記の例は左側のバス１０２がＢＲＬコマンドを開始するプロセスについて述べたものであるが、右側のバス１０４またはＩ／Ｏバス１０６がＢＲＬコマンドを開始しても同様のプロセスが起こる。
Ｂ．  バスリード無効ラインコマンド処理
図９は、バス１０２、１０４または１０６のうちの１本がバスリード無効ライン（ＢＲＩＬ）コマンドを実行する際にキャッシュコヒーレンスを維持するためのフローチャートを示している。スタートブロック９００から開始して、複数のプロセッサ１１２のうちの１つがＢＲＩＬコマンドを実行する。ＢＲＩＬコマンドの実行中、複数のプロセッサ１１２のうちの１つが、所望のキャッシュラインアドレス４００を自己が割り当てられたコヒーレンスフィルタ２００に送信する。
ブロック９０２に進み、バス１０２、１０４または１０６がＢＲＩＬコマンドを実行していることをサイクルエンコーダ３０２が判断する。また、割り当てられたタグコントローラ３００がＢＲＩＬコマンドにおいて識別されたキャッシュラインアドレス４００を使用し、リモートタグメモリ２１２内のキャッシュラインアドレス４００にアクセスする。リモートタグメモリ２１２がキャッシュラインアドレス４００を含む場合、これらのメモリはリモートキャッシュラインアドレス４００が無効ステート、共有ステートまたは所有ステートにあることを示すリモートコヒーレンスステータスビット４１２を返送する。
上述したように、特定のキャッシュラインアドレスを所有ステートで含むリモートタグメモリ２１２は１つしかない。しかしながら、２つ以上のリモートタグメモリ２１２が特定のキャッシュラインアドレスを共有または無効ステートで含んでもよい。１つのリモートタグメモリ２１２がキャッシュラインアドレスのコピーを共有ステートで含み、別のリモートタグメモリ３００が同一のキャッシュラインアドレスのコピーを無効ステートで含む場合には、共有ステートにあるコヒーレンスステータスビット４１２が指揮をとる。下記においてより詳細に説明するように、２つ以上のリモートタグメモリ３００が特定のキャッシュラインアドレスのコピーを共有ステートで含む場合には、コヒーレンスルール３０４は２つ以上のリモートバス１０２、１０４または１０６においてリモートバストランザクションを行い、キャッシュコヒーレンスを保証することができる。また、リモートタグメモリ３００の中には特定のキャッシュラインアドレス４００を含むものが存在しない場合には、キャッシュラインアドレス４００に関連したリモートコヒーレンスステータスビット４１２が無効ステートであるかのように扱われる。
例えば、左側のバス１０２上のプロセッサ１１２ａがブロック９０２における特定のキャッシュラインアドレス４００についてのＢＲＩＬコマンドを生成すると、左側のサイクルエンコーダ３０２ａが左側のバス１０２でＢＲＩＬコマンドが実行されていると判断する。また、左側のタグコントローラ３００ａがキャッシュラインアドレス４００を用いて右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃにアクセスする。タグコントローラ３００は、右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃから、キャッシュラインアドレス４００が右側のタグメモリ２１２ｂにあるか否か、Ｉ／Ｏタグメモリ２１２ｃが無効ステート、共有ステートまたは所有ステートのいずれであるかを示すリモートコヒーレンスステータスビット４１２を取得する。右側のタグメモリ２１２ｂおよびＩ／Ｏタグメモリ２１２ｃのいずれもキャッシュラインアドレス４００を含んでいない場合には、左側のタグコントローラ３００ａがリモートコヒーレンスステータスビット４１２を無効ステートであるかのように扱う。
ここで、好ましいルールテーブル３０４の動作およびローカルおよびリモート指定を使用することに注目すると、ローカルバス１０２、１０４または１０６に関連するサイクルエンコーダ３０２は、ローカルルールテーブル３０４にバストランザクション（ＢＲＩＬコマンド）のタイプおよびリモートコヒーレンスステータスビット４１２のステータスを送信する。リモートキャッシュラインアドレス４００が無効ステートにあることがリモートコヒーレンスステータスビット４１２によって示されると、ローカルルールテーブル３０４はブロック９０４に進む。好ましい実施の形態では、リモートコヒーレンスステータスビット４１２が無効ステートにあると、ローカルルールテーブル３０４はリモートバス１０２、１０４または１０６のいずれでもＢＲＩＬクロスバストランザクションを生成しない。代わりに、ローカルルールテーブル３０４はキャッシュラインアドレスの上位集合４００をローカルタグメモリ３００において維持する。
ブロック９０４に進むと、ローカルプロセッサ１１２は、自己の内部キャッシュメモリ１１４に対して問い合わせを行い、ローカルプロセッサ１１２の中に所望のキャッシュラインのコピーを持っているものがあるか否かを判断する。好ましい実施の形態では、複数のプロセッサ１１２のうちの１つは、変更後のキャッシュラインがプロセッサのキャッシュメモリ１１４に存在することがバススヌープ動作によって示されるとＨＩＴＭ＃信号をアサートする。ＨＩＴＭ＃信号は、複数のアドレスおよび制御線１０８のうちの１本であり、最新のキャッシュラインを有するプロセッサ１１２はキャッシュラインを主記憶装置１３２に書き戻す必要があるということを示している。
ブロック９０６では、ローカルプロセッサ１１２がバストランザクションに応答し、同時に変更後のキャッシュラインを主記憶装置１３２に書き戻すことによって主記憶装置１３２を更新する。ブロック９０８に進むと、ローカルルールテーブル３０４はローカルタグコントローラ３００に対して、ローカルタグメモリ２１２内のコヒーレンスステータスビット４１２を所有ステートに設定するよう指示する。次に、ローカルルールテーブル３０４はＥＮＤブロック９１０に進む。
ブロック９０４に戻り、ローカルプロセッサ１１２がキャッシュラインの変更後のコピーを含まない場合には、ローカルルールテーブル３０４はブロック９１２に進む。上述したように、ローカルタグメモリ２１２がキャッシュラインアドレス４００のコピーを含まない場合、ローカルルールテーブル３０４はこのキャッシュラインアドレス４００をローカルタグメモリ３０４に加える。このように、ローカルタグメモリは既存のキャッシュラインアドレスをローカルタグメモリから追い出して新たなキャッシュラインアドレスのために空間を確保する必要がある場合がある。そのような場合には、古いキャッシュラインアドレスをまず無効にし、その後で新たなキャッシュラインアドレスをローカルタグメモリに追加する。ブロック９１２において、左側のバススレーブも主記憶装置１３２から所望のキャッシュラインを取得し、要求を出しているプロセッサ１１２にこれを送信する。
ブロック９０２に戻り、以下、リモートタグメモリ３００によって、リモートキャッシュラインアドレス４００が共有または所有ステートにあることが示された場合に何が起こるかについて的を絞って説明する。リモートコヒーレンスステータスビット４１２によってリモートキャッシュラインアドレス４００が共有または所有ステートにあることが示されると、ローカルルールテーブル３０４は、キャッシュコヒーレンスを保証するのに必要なＢＲＩＬクロスバストランザクションを生成する。
ブロック９２０に進み、ローカルルールテーブル３０４は、ローカルＢＲＩＬコマンドを遅延できるか否かを判断する。上述したように、バストランザクションを発行するプロセッサ１０４は、そのＤＥＮ＃信号をアサートすることによってバストランザクションが遅延可能なものであるか否かを示す。ＤＥＮ＃信号がアサートされると、ローカルルールテーブル３０４はブロック９２２に進み、ローカルバススレーブ２０４に対してローカルＢＲＩＬコマンドを遅延するよう指示する。ブロック９２４に進み、ローカルルールテーブル３０４は次に、ＢＲＬコマンドをリモートバス１０２、１０４または１０６のうちの１本で行うよう本発明に指示する。
ブロック９２０に戻り、バストランザクションを遅延できない場合には、ローカルルールテーブル３０４はブロック９２６に進み、ローカルバススレーブ２０４に対してローカルＢＲＩＬコマンドを引きとめるよう指示する。ブロック９２４に進み、ローカルルールテーブル３０４は次に、リモートバス１０２、１０４または１０６のうちの１本でリモートＢＲＩＬコマンドを実行するよう本発明に対して指示する。
ブロック９２４では、ブロック８４４で上述したように、バッファマネージャ２１０および中央リクエストリスト２０８がＢＲＩＬコマンドを所望のリモートバス１０２、１０４または１０５に転送する。ブロック９２８に進み、リモートバス１０２、１０４および１０６上でＢＲＩＬコマンドが実行される。ブロック９２８では、リモートプロセッサが、自己のキャッシュメモリ１１４内にあるキャッシュラインアドレスのステータスを評価する。リモートプロセッサが所望のキャッシュラインアドレス４００のコピーを有していなければ、右側のプロセッサはＨＩＴ＃またはＨＩＴＭ＃信号をアサートしない。
ブロック９３０に進み、リモートタグコントローラ３００が、リモートタグメモリ２１２内のコヒーレンスステータスビット４１２を無効ステートに設定する。ブロック９３２に進み、左側のバススレーブが主記憶装置１３２から所望のキャッシュラインを取得し、左側のバス１０２上の要求を出しているプロセッサ１１２にこれを送信する。さらに、キャッシュラインアドレス４００がローカルタグメモリ２１２に存在しない場合には、ローカルルールテーブル３０４がローカルタグコントローラ３００に対して新たなキャッシュラインアドレス４００をローカルタグメモリに追加するよう指示する。上述したように、これには既存のキャッシュラインアドレスを無効にする必要がある場合もある。ブロック９０８に進み、ローカルタグコントローラ３００がローカルタグメモリ２１２におけるコヒーレンスステータスビットを所有に設定し、ＥＮＤブロック９１０に進む。
さて、ブロック９２８に戻り、リモートプロセッサ１１２がキャッシュラインの未変更コピーを含む場合には、これらのプロセッサはリモートＨＩＴ＃信号をアサートし、本発明は上述したようにブロック９３０、ブロック９３２、ブロック９０８およびＥＮＤブロック９１０に進む。再びブロック９２８に戻り、複数のリモートプロセッサ１１２のうちの１つが自己のキャッシュメモリ１１４にキャッシュラインの変更後のコピーを含んでいる場合、リモートプロセッサ１１２はリモートＨＩＴＭ＃信号をアサートする。
ブロック９３４に進み、変更後のキャッシュラインをローカルバス１０２、１０４または１０６に供給する。特に、変更後のキャッシュラインをデータインタフェースバッファ１３４内の適切なデータセル７００にロードし、オーナーバス識別子６０８によって識別されるバスに返信する。次に、ローカルバススレーブ２０４が（オリジナルのバストランザクションが遅延可能である場合には遅延されたレスポンスと一緒に）変更後のキャッシュラインを左側のローカルバス１０２で送信する。また、リモートタグコントローラ３００がリモートタグメモリ内のリモートコヒーレンスステータスビットを無効ステートに設定する。応答の一部として、変更後のキャッシュラインが主記憶装置１３２に書き戻される。
次に、本発明は上述したようにブロック９０８およびＥＮＤブロック９１０に進む。このように、本発明は、キャッシュコヒーレンスを維持するために必要な可能性がある場合にＢＲＩＬクロスバストランザクションを行う。
ＶＩ．  他の実施の形態
本発明の他の実施の形態は、いわゆる無効待ち行列と呼ばれるものを実現し、これを含む。ここで、図１０に示す無効待ち行列１０００に注目すると、各バスは割り当てられた無効待ち行列１０００を有する。無効待ち行列１０００は、比較的少数の待ち行列エントリ１００２を含む。各待ち行列エントリ１００２は、複数のキャッシュラインアドレス４００のうちの１つに対するタグページアドレス４０２と、オフセットアドレス４０４と、コヒーレンスステータスビット４１２と、パリティビット４１４とを格納する。
好ましい実施の形態では、好ましいタグメモリ２１２が主記憶装置１３２よりも小さい。このため、時々２つ以上のキャッシュラインアドレス４００が同一のタグエントリ４１０にマッピングされる。キャッシュラインが占有されたタグエントリ４１０にマッピングされると、タグコントローラ３００は占有されているタグエントリ４１０をタグメモリ２１２から追い出さなければならない。すなわち、占有されているタグエントリ４１０の既存のキャッシュラインを無効にし、タグコントローラ３００が新たなキャッシュラインアドレス４００をタグエントリ４１０に格納できるようにする。
また、２つのプロセッサ１１２が同一のタグエントリ４１０にマッピングされる２本のキャッシュラインにアクセスしようとした場合、コヒーレンスフィルタ２００が第１のキャッシュラインアドレス４００を無効にし、これを第２のキャッシュラインアドレス４００と置き換える。コヒーレンスフィルタ２００は次に第２のキャッシュラインアドレス４００を無効にし、これを第１のキャッシュラインアドレス４００と置き換える。このようなピンポン作用はタグメモリスラッシングと呼ばれている。さらに大きなタグメモリ２１２を用いてタグメモリスラッシングを最小限にすることは可能であるが、この方法ではタグメモリ２１２にかかるコストが大幅に増す可能性がある。有利なことに、無効待ち行列１０００は、メモリにかかる追加コストを最小限に抑えたままタグメモリスラッシングを大幅に減らす。
さらに、古いキャッシュラインアドレスを無効にしなければならない場合、古いキャッシュラインを無効にする処理が終了するまで新たなキャッシュラインアドレスに関連したバストランザクションを遅延させなければならない。好ましい無効待ち行列１００では、新たなバストランザクションを進めることができる。その後でバスがフリーになるまで先送りして古いキャッシュラインアドレスを無効にすることができる。
複数のコヒーレンスフィルタ２００のうちの１つでタグエントリ４１０をそのタグメモリ２１２から追い出す必要が生じると、タグエントリ４１０はコヒーレンスフィルタの無効待ち行列１００２に格納される。好ましい無効待ち行列１０００は最大で８個の追い出されたタグエントリ４１０を格納することができるが、無効待ち行列１００２は様々な数の追い出されたタグエントリ４１０を含むことができる。複数のコヒーレンスフィルタ２００のうち１つで９個以上のタグエントリ４１０を追い出す場合は、無効待ち行列１０００は最も後にアクセスされたタグエントリ４１０を保持し、フラッシュしたタグエントリ４１０を無効にする。
無効待ち行列１０００は、タグメモリ２１２内のタグエントリ４１０とは異なるフォーマットで待ち行列エントリ１００２を格納する。特に、好ましい待ち行列エントリ１００２は、タグメモリ２１２から追い出されたタグエントリ４１０のタグページアドレス４０２と、オフセットアドレス４０４と、コヒーレンスステータスビット４１２と、パリティビット４１４とを含む。どのようなキャッシュラインアドレス４００であっても任意の待ち行列エントリ１００２に存在することができるため、各無効待ち行列１０００は完全アソシアティブ方式であると言われる。
各無効待ち行列１０００が比較的少数の無効待ち行列エントリ１００２を含むため、各無効待ち行列１０００はタグメモリ２１２のサイズを大きくするための低コストの選択肢を提供する。好ましい実施の形態では、無効待ち行列１０００は、システムアクセスコントローラ１３０内に存在するスタティックランダムアクセスメモリで実現される。
ＶＩＩ．  結論
以上、本発明の好ましい実施の形態を説明したが、これらの実施の形態は一例として挙げられたものであり、本発明の範囲を限定することを意味するものではない。例えば、本願明細書では３バスシステム１００に鑑みて本発明を説明したが、本発明ではさらに多くの本数のバスを含むこともできる。さらに、本発明は様々な多重処理システムで実現可能である。したがって、本発明の趣旨および範囲は以下の請求の範囲およびこれと等価なものによって規定されるべきものである。
【図１】
0004316016.tif 000004
【図２】
0004316016.tif 000005
【図３】
0004316016.tif 000006
【図４】
0004316016.tif 000007
【図５Ａ】
0004316016.tif 000008
【図５Ｂ】
0004316016.tif 000009
【図６】
0004316016.tif 000010
【図７】
0004316016.tif 000011
【図８】
0004316016.tif 000012
【図９】
0004316016.tif 000013
【図１０】
0004316016.tif 000014