(57)【要約】【課題】リトライとすべき先行トランザクションが、スヌープの結果リトライできないケースがある。スヌープ結果を待ってからリトライ判定を行うと、レイテンシが伸び、パイプラインが可変長になるため論理が複雑化する。【解決手段】要求発行時にリトライ判定を受けたトランザクションを発行中のトランザクションと区別し、沈み込み保護対象のトランザクションがリトライ判定中のトランザクションと二度続けてアドレス競合した場合に、これを発行することで沈み込みを解消する。【選択図】図１
2006301825.tif 000002
【特許請求の範囲】
【請求項１】
2つ以上のプロセッサとノードコントローラとをプロセッサバスで接続するマルチプロセッサシステムであって、
前記ノードコントローラは前記プロセッサから発行されたトランザクションを受け付けるトランザクション受信キューと、発行されたトランザクションのアドレスを格納するアドレス格納バッファと、競合するアドレスに対する要求のリトライを判定するリトライ判定部と、特定のプロセッサからの要求の沈み込みを回避する沈み込み防止制御部を備え、
前記アドレス格納バッファには、前記リトライ判定部によりリトライと判定されたトランザクションを区別するためのリトライ中ビットを備え、
前記沈み込み防止制御部において沈み込み保護対象のトランザクションとアドレス一致したためにリトライと判定されたトランザクションを前記アドレス格納バッファに格納する場合に前記リトライ中ビットをセットし、
前記沈み込み防止制御部において沈み込み保護対象のトランザクションが、前記リトライ中ビットのセットされたトランザクションと2回続けてアドレス競合した場合に、
前記沈み込み保護対象のトランザクションを発行する機能を備えることを特徴とするマルチプロセッサシステム。
【請求項２】
請求項１記載のプロセッサシステムであって、
前記リトライ判定部は、前記トランザクション受信キューに格納されたトランザクションのアドレスに対して前記沈み込み防止制御部と前記アドレス格納バッファからリトライかどうかの結果を受け取る機能と、前記アドレス格納バッファに当該アドレスを格納し有効ビットをセットする機能と、アドレス競合した場合にはリトライ中ビットをセットし、アドレス競合していない場合にはリトライ中ビットをクリアする機能と、前記プロセッサバスから得られたスヌープ結果を元にして、リトライ中ビットがセットされたトランザクションがリトライできなかった場合にリトライ中ビットをクリアする機能を備え、
前記アドレス格納バッファは、発行されたアドレスに対して、リトライ中ビットのセットされたエントリのみとアドレス競合したことを示す「Weak Retry」と、リトライ中ビットのクリアされたエントリとアドレス競合したことを示す「Retry」と、いずれのエントリともアドレス競合しなかったことを示す「OK」の3つの状態を判定する機能を備え、
前記沈み込み防止制御部は、前記リトライ判定部のリトライ結果を受けてリトライとなったトランザクションのアドレスと発行元識別子を格納する機能と、格納されたエントリうちの一つを保護対象識別子によって示す機能と、トランザクション発行時に保護対象のトランザクションとアドレス競合した場合に、発行元識別子が異なる場合にリトライと判定する機能と、保護対象のトランザクションと同一発行元のトランザクションがリトライとならずに発行された場合に当該トランザクションのエントリを抹消する機能を備え、
さらに前記沈み込み防止制御部には保護対象のトランザクションとアドレス競合するトランザクションがシステムに発行されていないことを示すNOFLIGHTビットと、保護対象のトランザクションが発行できることを示すREADYビットを備え、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Weak Retry」と判定された場合に前記READYビットがクリアされていた場合に前記NOFLIGHTビットをセットする機能と、前記保護対象のトランザクションがスヌープフェーズの結果リトライ可能だった場合に前記NOFLIGHTビットがセットされていた場合に前記READYビットをセットして当該トランザクションをリトライとする機能と、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Weak Retry」と判定された場合に前記READYビットがセットされていた場合に当該トランザクションをリトライではないと判定する機能と、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Retry」と判定された場合に前記NOFLIGHTビットと前記READYビットをクリアする機能を備えることを特徴とする、マルチプロセッサシステム。
【請求項３】
請求項２記載のプロセッサシステムであって、前記ノードコントローラと前記2つ以上のプロセッサが同一チップ上にあるようなマルチプロセッサシステム。
【請求項４】
2つ以上のプロセッサの接続されたプロセッサバスと、1つ以上のIOコントローラと、1つ以上のメモリコントローラと、0以上のシステム結合スイッチとを接続するノードコントローラであって、
前記ノードコントローラは前記プロセッサから発行されたトランザクションを受け付けるトランザクション受信キューと、発行されたトランザクションのアドレスを格納するアドレス格納バッファと、競合するアドレスに対する要求のリトライを判定するリトライ判定部と、特定のプロセッサからの要求の沈み込みを回避する沈み込み防止制御部を備え、
前記アドレス格納バッファには、前記リトライ判定部によりリトライと判定されたトランザクションを区別するためのリトライ中ビットを備え、
前記沈み込み防止制御部において沈み込み保護対象のトランザクションとアドレス一致したためにリトライと判定されたトランザクションを前記アドレス格納バッファに格納する場合に前記リトライ中ビットをセットし、
前記沈み込み防止制御部において沈み込み保護対象のトランザクションが、前記リトライ中ビットのセットされたトランザクションと2回続けてアドレス競合した場合に、前記沈み込み保護対象のトランザクションを前記IOコントローラまたは前記メモリコントローラまたは前記システム結合スイッチへと発行する機能を備えることを特徴とするノードコントローラ。
【請求項５】
請求項４記載のノードコントローラであって、
前記リトライ判定部は、前記トランザクション受信キューに格納されたトランザクションのアドレスに対して前記沈み込み防止制御部と前記アドレス格納バッファからリトライかどうかの結果を受け取る機能と、前記アドレス格納バッファに当該アドレスを格納し有効ビットをセットする機能と、アドレス競合した場合にはリトライ中ビットをセットし、アドレス競合していない場合にはリトライ中ビットをクリアする機能と、前記プロセッサバスから得られたスヌープ結果を元にして、リトライ中ビットがセットされたトランザクションがリトライできなかった場合にリトライ中ビットをクリアする機能を備え、
前記アドレス格納バッファは、発行されたアドレスに対して、リトライ中ビットのセットされたエントリのみとアドレス競合したことを示す「Weak Retry」と、リトライ中ビットのクリアされたエントリとアドレス競合したことを示す「Retry」と、いずれのエントリともアドレス競合しなかったことを示す「OK」の3つの状態を応答する機能を備え、
前記沈み込み防止制御部は、前記リトライ判定部のリトライ結果を受けてリトライとなったトランザクションのアドレスと発行元識別子を格納する機能と、格納されたエントリうちの一つを保護対象識別子によって示す機能と、トランザクション発行時に保護対象のトランザクションとアドレス競合した場合に、発行元識別子が異なる場合にリトライと判定する機能と、保護対象のトランザクションと同一発行元のトランザクションがリトライとならずに発行された場合に当該トランザクションのエントリを抹消する機能を備え、
さらに前記沈み込み防止制御部には保護対象のトランザクションとアドレス競合するトランザクションがシステムに発行されていないことを示すNOFLIGHTビットと、保護対象のトランザクションが発行できることを示すREADYビットを備え、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Weak Retry」と判定された場合に前記READYビットがクリアされていた場合に前記NOFLIGHTビットをセットする機能と、前記保護対象のトランザクションがスヌープフェーズの結果リトライ可能だった場合に前記NOFLIGHTビットがセットされていた場合に前記READYビットをセットして当該トランザクションをリトライとする機能と、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Weak Retry」と判定された場合に前記READYビットがセットされていた場合に当該トランザクションをリトライではないと判定する機能と、保護対象のトランザクションが前記アドレス格納バッファの検索結果で「Retry」と判定された場合に前記NOFLIGHTビットと前記READYビットをクリアする機能を備えることを特徴とする、ノードコントローラ。
【請求項６】
請求項５記載のノードコントローラであって、前記2つ以上のプロセッサの機能を同一チップ上に備えるようなノードコントローラ。
【請求項７】
2つ以上のプロセッサの接続されたプロセッサバスと、1つ以上のIOコントローラと、1つ以上のメモリコントローラと、0以上のシステム結合スイッチとを接続するノードコントローラであって、
前記プロセッサが発行するトランザクション発行要求を前記プロセッサバスを介して受け付ける機能と、前記トランザクションに対する前記プロセッサのスヌープ結果をプロセッサバスを介して受け付ける機能と、プロセッサバスに対してトランザクションが発行できたがどうかの結果を応答する機能を備え、
前記プロセッサバスに対して、前記接続された1つのプロセッサからあるアドレスに対してトランザクション発行要求が行われ、別のプロセッサから同一のアドレスに対してトランザクション発行要求が行われた場合に、前者のトランザクションが完了するまでの間後者のトランザクションに対してプロセッサバスにリトライを応答する機能を備え、
一度あるアドレスに対する要求がリトライとなった場合に当該要求を出した発行元プロセッサを沈み込み保護対象とし、沈み込み保護対象以外のプロセッサから同一のアドレスに対してトランザクション発行要求が行われた場合、プロセッサバスに対してリトライと応答する機能を備え、
沈み込み保護対象以外のプロセッサから同一アドレスに対してトランザクション発行要求が行われ、当該トランザクションに対してリトライを応答する前に沈み込み保護対象のプロセッサから同一アドレスに対してトランザクション発行要求が行われた場合に、一度目は沈み込み保護対象のプロセッサから発行されたトランザクションに対してリトライと応答し、二度目は沈み込み保護対象のプロセッサから発行されたトランザクションを発行する機能を備えることを特徴とする、ノードコントローラ。
【請求項８】
2つ以上のプロセッサの接続されたプロセッサバスと、1つ以上のIOコントローラと、1つ以上のメモリコントローラと、0以上のシステム結合スイッチとを接続するノードコントローラ上におけるアドレス競合判定方法であって、
トランザクションの要求フェーズにおいて、当該トランザクションのアドレスをアドレス格納バッファ中のアドレスと比較し、リトライ中ビットの設定されたエントリとのみアドレス競合していることと、リトライ中ビットの設定されていないエントリとアドレス競合していることを判定するステップと、
沈み込み保護対象のトランザクションとアドレス競合している場合に発行元エージェントが沈み込み保護対象と同一かどうかを判定するステップと、
沈み込み保護対象の発行元エージェントから発行されたトランザクションが、前記アドレス格納バッファ中の前記リトライ中ビットの設定されたエントリとのみアドレス競合していた場合に、それが二度目であるかどうかを判定するステップと、
二度目だった場合に当該トランザクションをリトライではなくシステムに発行するステップを含むことを特徴とする、アドレス競合判定方法。
【請求項９】
請求項8記載のアドレス競合判定方法であって、
沈み込み保護対象の発行元エージェントから発行されたトランザクションが、前記アドレス格納バッファ中の前記リトライ中ビットのセットされたエントリとのみアドレス競合していた場合に、NOFLIGHTビットとREADYビットを判定するステップと、NOFLIGHTビットとREADYビットの両者が1だった場合に当該トランザクションをリトライではなくシステムに発行するステップと、NOFLIGHTビットとREADYビットの両者が1ではなかった場合には当該トランザクションをリトライとし、NOFLIGHTビットを1にセットするステップを含み、
沈み込み保護対象の発行元エージェントから発行されたトランザクションが、前記アドレス格納バッファ中の前記リトライ中ビットのセットされていないエントリとアドレス競合した場合に、NOFLIGHTビットとREADYビットをクリアするステップを含み、
トランザクションがリトライと判定された場合には前記アドレス格納バッファに対してリトライ中ビットをセットしてアドレスを格納し、リトライでないと判定された場合には前記アドレス格納バッファに対してリトライ中ビットをクリアしてアドレスを格納するステップを含み、
トランザクションのスヌープフェーズにおいて、当該トランザクションがスヌープの結果リトライ不可となった場合に、前記要求フェーズにおいてリトライと判定されていた場合、前記アドレス格納バッファの当該エントリのリトライ中ビットをクリアするステップと、
沈み込み保護対象の発行元エージェントから発行され、前記要求フェーズにおいてリトライと判定されたトランザクションが、スヌープの結果リトライ可能な場合に、READYビットを１にセットするステップと、
リトライとなったトランザクションのエントリを前記アドレス格納バッファから抹消するステップを含み、
トランザクションの完了フェーズにおいて、当該トランザクションのエントリを前記アドレス格納バッファから抹消するステップを含むことを特徴とする、アドレス競合判定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチプロセッサシステム及びそののチップセットに関係し、特にアドレス競合および沈み込み防止のためにトランザクションのリトライを判定する技術に関する。
【背景技術】
【０００２】
近年の計算機機能の向上とそれに伴う計算機への要求の増大に伴い、特にサーバの分野では複数のプロセッサを搭載したマルチプロセッサシステムが多く見られるようになってきた。このようなマルチプロセッサシステムでは、並列性の向上のために遅延応答・アウトオブオーダー制御と呼ばれる方法により、一度に複数のトランザクションをシステムに発行し、発行した順序とは異なる順序でトランザクションを完了させることができるようになっている。
【０００３】
アウトオブオーダー制御が有効なのは、複数のトランザクションが互いに実行順序に関係ないケースに限られる。もし同一のアドレスに対するリードとライトあるいは複数のライトが別々のプロセッサから発行された場合、これをアウトオブオーダーに処理してしまっては、処理する順序によって結果が変わってきてしまうからである。従って、このようなマルチプロセッサシステムにおけるチップセットには、アドレス競合(通常はキャッシュライン単位)を判定し、既にシステムに発行されているトランザクションと同一のラインに対する要求は、システムに発行せずにリトライとする機能が必要である。リトライとされたトランザクションは再びプロセッサから発行され、先行するトランザクションが完了した後にシステムへと発行される。
【０００４】
一方、トランザクションをリトライとした場合、トランザクションが発行されるタイミングによっては常に他のプロセッサから発行されたトランザクションによってリトライとなってしまう、いわゆる沈み込み（スタベーション）が起きてしまう可能性がある。例えば4つのプロセッサがあり、1つのプロセッサがライト、残り3つのプロセッサがリードを発行しているようなケースで、最初のライトは常に他のいずれかのリードに邪魔されてリトライとなってしまうような場合である。この場合、他のリードはポーリングによってライトされる結果を待っている可能性があるため、ライトが沈み込んでしまうとプログラムは進まなくなる。（ライブロック）
従って、マルチプロセッサシステムにおけるチップセットには、アドレス競合によるリトライだけでなく沈み込みを防止する機能も必要となる。
【０００５】
特許文献１には沈み込み防止の機能備えたマルチプロセッサシステム用のチップセットが示される。このチップセットには、システムに発行されたトランザクションのアドレスを格納するOut-of-Order Coherencyキュー(OOCキュー)と、スタベーション状態にあるライトトランザクションを1つだけ格納するWrite Starvation Preventionキュー(WSPキュー)がある。トランザクション発行時にはOOCキューの有効なエントリとアドレス比較を行い、競合するエントリがあった場合はリトライとする。ライトトランザクションがリトライとなった場合、WSPキューが空の場合にはWSPキューに当該アドレスが格納される。WSPキューに格納されているアドレスと競合したリードトランザクションはリトライとされる。これにより、ライトトランザクションが優先して発行できるようになるため、スタベーションが起こらないようになっている。
【０００６】
一方、非特許文献１には代表的なプロセッサのバス仕様が紹介される。それによれば、他プロセッサのスヌープフェーズにて、プロセッサバスにＨＩＴＭがアサートされた場合、アサートしたプロセッサのキャッシュから最新データが要求元へ転送されるキャッシュ間通信（Ｃ２Ｃ）が実行されることが記載される。
【０００７】
【特許文献１】米国特許第6738869号公報
【０００８】
【非特許文献１】Intel(R) Itanium(R) 2 Processor Hardware Developer's Manual
【発明の開示】
【発明が解決しようとする課題】
【０００９】
前述のように沈み込み防止は、沈み込み防止保護対象のトランザクションがリトライせずに通れるようになるまでの間、それ以外のアドレス競合するトランザクションをリトライとすることによって実現される。しかしプロセッサバスの仕様によっては、要求フェーズではリトライ可能とされていたトランザクションが、実際には後でリトライ不可能だと判明するケースが存在する。非特許文献１（上掲）のバス仕様を例としてこれを説明する。要求フェーズにおいてトランザクション種別やアドレス等の情報がプロセッサバスに通知される。その後スヌープフェーズにおいて、そのトランザクションに対して他のプロセッサのスヌープ結果が通知される。スヌープ結果は、リードトランザクションに対してクリーンなキャッシュのコピーを持っていることを示すHITという信号と、リードまたはライトトランザクションに対してダーティなキャッシュを持っていることを示すHITMという信号がある（何のコピーも持っていない場合はHITもHITMもアサートされない）。ここでHITMがアサートされた場合、最新のデータがキャッシュ内にあることになるため、メモリからデータを読み出す必要はなく、キャッシュ内の最新データが直接要求元へと転送される。これをキャッシュ間転送(C2C)と呼ぶ。キャッシュ間転送はプロセッサバス上ではトランザクションの完了を意味するので、リトライとすることはできない。一方、チップセットはキャッシュ間転送が起きた場合、最新のデータをメモリに書き戻す必要があるため、システムに対してトランザクションは発行する必要がある。従って、キャッシュ間転送に伴うメモリへの書き戻しトランザクションが完了するまでの間は、後続の同一アドレスに対するトランザクションはリトライとする必要がある。
【００１０】
このように、要求フェーズにおいてはリトライ可能とされていたトランザクションがスヌープフェーズにおいてリトライ不可となるケースが存在する。従って、あるトランザクションが本当にリトライされるかどうかはスヌープフェーズの結果を見るまでは判定できないことになる。しかしスヌープフェーズは要求フェーズからバスサイクルで3サイクル以降と遅く、またスヌープストールによってはさらに遅れることがあり、スヌープフェーズの結果を受けてから判定を行った場合リトライしない場合にトランザクションを発行するまでのレイテンシが伸びてしまうという問題点があった。また、スヌープフェーズ前に判定をしようとすると、同一アドレスの場合に後続トランザクションの競合判定を遅らせる必要があり、パイプラインが可変長となりアドレス競合判定論理が複雑化するという問題点があった。
【００１１】
本発明の目的は、固定長のパイプラインを使って、スヌープフェーズの結果を待たずにアドレス競合沈み込み判定を行い、簡単な論理によって低レイテンシによるトランザクションの発行を実現することにある。
【課題を解決するための手段】
【００１２】
発行中のトランザクションのアドレスを管理するアドレス格納バッファの各エントリに、リトライ判定中のトランザクションを示すリトライ中ビットを設ける。リトライ判定部は、アドレス格納バッファ検索時に、リトライ中ビットのセットされたエントリとのみ競合した場合と、リトライ中ビットのセットされていないエントリと競合した場合と、どのエントリとも競合していない場合の3状態を判定する。
【００１３】
リトライ判定部は、トランザクションがアドレス格納バッファ中のエントリと競合するか、沈み込み防止対象のトランザクションとアドレスが競合して発行元が異なる場合に、当該トランザクションをリトライと判定し、アドレス格納バッファにリトライ中ビットをセットした上でアドレスを格納する。リトライと判定されなかった場合は、リトライ中ビットをクリアしてアドレスを格納する。
【００１４】
沈み込み防止制御部は、沈み込み防止対象のトランザクションの発行元とアドレスを格納するキューと、現在沈み込み防止対象のアドレスに対して発行中のトランザクションが存在しないことを示すNOFLIGHTビットと、リトライ中ビットのセットされていないエントリと競合しなかった場合に沈み込み防止保護対象のトランザクションが発行可能なことを示すREADYビットを設ける。
【００１５】
沈み込み防止制御部は、アドレス格納バッファ検索時に沈み込み防止対象のトランザクションが、リトライ中ビットのセットされたエントリとのみ競合した場合に、NOFLIGHTビットとREADYビットが共に1の場合には当該トランザクションをリトライではなくシステムに発行する。そうでない場合はNOFLIGHTビットを1にセットし、スヌープフェーズの結果リトライ可能だった場合READYビットを1にセットする。一方、アドレス格納バッファ検索時に、沈み込み防止対象のトランザクションが、リトライ中ビットのセットされていないエントリと競合した場合には、NOFLIGHTビットとREADYビットを0にクリアする。
【００１６】
リトライ判定部はまたトランザクションのスヌープ結果を受け、リトライ不可となった場合に、アドレス格納バッファの当該エントリのリトライ中ビットをクリアする。
これら一連の動作により、先行するトランザクションのスヌープ結果を待たずに、沈み込みの防止とアドレス競合によるリトライを実現することができる。
【発明の効果】
【００１７】
本発明により、スヌープ結果を待たずにアドレス競合によるリトライ判定を行うことが可能になる。トランザクションがリトライしなかった場合の発行までのレイテンシを2〜3サイクル短縮することができる。また、アドレス競合判定部を固定サイクルのパイプラインで構成することが可能となる。先行するトランザクションのリトライ結果を待ってからアドレス競合判定を行うための可変長のパイプラインとした場合に比べてゲート規模を小さくできる。
【実施例１】
【００１８】
本発明の第1の実施例を図１〜図３を用いて説明する。
図1は第１の実施例のマルチプロセッサシステムの概略ブロック図であり、実施例の特徴にかかわるアドレス競合判定機能を備えたノードコントローラを主に示している。
プロセッサバス１２０、メモリコントローラ５００、Ｉ／Ｏコントローラ５１０が、システム結合スイッチ５２０が、ノードコントローラ２００を介して相互接続されている。なお、本図には明示的に図示していないが、メモリコントローラ５００の先には主記憶がある。Ｉ／Ｏコントローラ５１０の先にはＩ／Ｏバスがあり、その先には図示していない複数のＩ／Ｏデバイスが接続されている。また、システム結合スイッチ５２０によって複数のノードコントローラが接続される複数ノード構成も可能である。以下の説明はノードの数によって差異を生じない。
【００１９】
プロセッサバス１２０には2つ以上のプロセッサ１００が接続される。プロセッサ１００はキャッシュ１１０を備える。また、ここではプロセッサとしたが、それぞれのプロセッサは１つのプロセッサ内に2つ以上のプロセッサコアを含むマルチコア構成であっても良い。以下の説明はプロセッサをプロセッサコアとして読み替えても差異を生じない。
【００２０】
ノードコントローラ２００内には、プロセッサバス１２０に発行されたトランザクションを格納するトランザクション受信キュー２１０と、発行中のトランザクションのアドレスを格納するアドレス格納バッファ３００と、沈み込み防止を制御する沈み込み防止部４００と、アドレス格納バッファ３００と沈み込み防止制御部４００の結果とプロセッサバス１２０から得たスヌープ結果によってリトライを判定するリトライ判定部２２０と、発行されたトランザクションを管理する発行トランザクション管理キュー２４０と、プロセッサバス１２０に対して応答を返す応答制御部２３０を持つ。
【００２１】
アドレス格納バッファ３００の各エントリは、有効ビット３１０とリトライ中ビット３２０と、アドレス部３３０を持つ。
沈み込み防止制御部４００は、１つ以上のエントリからなる保護対象格納バッファ４７０を持つ。保護対象格納バッファの各エントリは、有効ビット４１０と発行元識別子４２０とアドレス部４３０とから構成されるまた、沈み込み防止制御部４００は、現在の沈み込み防止保護対象を示す保護対象識別子４４０を持つ。保護対象格納バッファ４７０の構造はキュー構成であっても、発行元識別子別のエントリを持つビットマップによる構成であっても構わない。保護対象格納バッファ４７０の構成の違いは、以下の説明には差異を生じない。また沈み込み防止制御部４００は、沈み込み防止保護対象のアドレスに対して現在発行中のトランザクションがいないことを示すＮＯＦＬＩＧＨＴビット４５０と、沈み込み防止保護対象のトランザクションを次の機会に発行できることを示すＲＥＡＤＹビット４６０を持つ。
ここで発行元識別子４２０は、保護対象となるトランザクションを発行したプロセッサだけでなく、発行されたトランザクションの種別（リード／ライト）を区別するためにも使われる。同一のプロセッサから発行されたトランザクションでも、リードとライトでは異なる発行元から発行されたと見做し、別々に保護対象とする。ここでいうライトトランザクションとは、純粋なライトだけでなくキャッシュ上でライトするためのリードトランザクション(リードインバリデートトランザクション)も含む。
【００２２】
以下に図1を用いて第一の実施例の沈み込み防止とアドレス競合判定の動作を説明する。
リセット直後、アドレス格納バッファ３００の有効ビット３１０は全て０に、沈み込み防止制御部４００の保護対象格納バッファ４７０の有効ビット４１０も全て０に初期化される。また沈み込み防止制御部４００のＮＯＦＬＩＧＨＴビット４５０、ＲＥＡＤＹビット４６０は共に０に初期化される。
【００２３】
プロセッサ１００ａがトランザクション発行の要求を行う時、プロセッサバス１２０上で要求フェーズを開始する。これをノードコントローラ２００ではトランザクションの発行要求として受け取り、トランザクション受信キュー２１０に当該トランザクションに関して必要な情報を格納する。ここでトランザクションに必要な情報とは、発行元プロセッサ、アドレス、トランザクション種別、遅延応答ＩＤなどである。
【００２４】
トランザクションを受信したノードコントローラ２００は、アドレス格納バッファ３００に対して当該アドレスが存在するかどうかの検索を行う。ここでアドレス格納バッファ３００の検索は、有効ビット３１０が１であるエントリに対してのみ行われる。有効ビット３１０が１であるエントリのアドレス部３３０とトランザクションのアドレスを比較し、同一のメモリ資源に対するアクセス（通常はキャッシュライン単位で判定する）だった場合にアドレス競合したと判定する。この時、リトライ中ビット３２０がセットされているエントリとのみアドレス競合した場合を「WeakRetry」、リトライ中ビット３２０がセットされていないエントリと１つ以上アドレス競合した場合を「Retry」、１つのエントリともアドレス競合しなかった場合を「OK」とし、アドレス格納バッファ３００はアドレス検索要求に対してこの３つの状態のいずれかを応答する。
【００２５】
沈み込み防止制御部４００に対しても検索を要求する。沈み込み防止制御部４００では、保護対象格納バッファ４７０上に一つ以上の有効ビット４１０がセットされたエントリがあり、保護対象識別子４４０がそのエントリを指している場合、そのアドレスを保護している状態にある。この時受信したトランザクションのアドレスが、沈み込み保護対象のアドレス部４３０とは異なる場合には何も起こらず「ＯＫ」と応答する。もし受信したトランザクションのアドレスが保護対象識別子４４０の指すエントリのアドレス部４３０と同一であった場合、受信したトランザクションの発行元を沈み込み保護対象の発行元識別子４２０と比較する。これが一致した場合、沈み込み保護対象として「ＯＫ」と応答する。一致しなかった場合には「Retry」と応答する。
【００２６】
リトライ判定部２２０は、アドレス格納バッファ３００と沈み込み防止制御部４００の応答結果を受けて、受信したトランザクションをリトライとするかどうかを決める。どちらかの応答が「Retry」だった場合、当該トランザクションはリトライとする。どちらの応答も「ＯＫ」だった場合、当該トランザクションは発行可能とする。当該トランザクションが沈み込み保護対象のトランザクションであり、かつアドレス格納バッファ３００の応答結果が「WeakRetry」だった場合、リトライ判定部２２０はさらに沈み込み防止制御部４００内のＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０の状態をチェックする。もしＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０が共に１である場合、当該トランザクションはリトライではなく発行可能とする。もしどちらかが０であった場合、当該トランザクションはリトライとし、ＮＯＦＬＩＧＨＴビット４５０を１にセットする。
【００２７】
また、沈み込み保護対象のトランザクションが、アドレス格納バッファ３００の応答結果で「Retry」となった場合は、ＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０を０にクリアする。
リトライ判定部２２０は、受信したトランザクションをアドレス格納バッファ３００に登録する。この時リトライと判定された場合、エントリの有効ビット３１０とリトライ中ビット３２０を共に１として登録される。リトライでなく発行可能と判定された場合は、エントリの有効ビット３１０のみ１で、リトライ中ビット３２０は０として登録される。ここまでが要求フェーズにおいてノードコントローラ２００が行う動作である。
【００２８】
次のスヌープフェーズの動作に移る。要求フェーズより数サイクル後、プロセッサバス１２０上の他のプロセッサ１００が、発行されたトランザクション要求に対してスヌープ結果を応答する。ノードコントローラ２００はこのスヌープ結果によって最終的にトランザクションを発行するかリトライとするかを判定する。他のプロセッサ１００ｂがメモリよりも新しいデータをキャッシュ１１０ｂ内に持っていた場合、プロセッサ１００ｂはプロセッサバス１２０に対してＨＩＴＭというスヌープ結果を返す。ＨＩＴＭを受けたノードコントローラ２００では当該トランザクションをキャッシュ間転送によって完了させるために、ＨＩＴＭ応答をプロセッサバス１２０に対して返す必要がある。この時、要求フェーズでリトライと判定されていたトランザクションの場合でも、リトライさせることはできずにＨＩＴＭ応答としなくてはならない。ＨＩＴＭ信号を受けたリトライ判定部２２０では、アドレス格納バッファ３００内の当該トランザクションのエントリのリトライ中ビット３２０をクリアする。当該トランザクションはトランザクション受信キュー２１０からデキューされ、また最新のキャッシュデータをメモリへと書き戻すためのトランザクション（ライトバックトランザクション）をシステムに発行するために、ライトバックトランザクションを発行トランザクション管理キュー２４０へとエンキューする。応答制御部２３０はプロセッサバス１２０に対してＨＩＴＭ応答を返す。当該トランザクションが沈み込み保護対象のトランザクションだった場合、沈み込み防止制御部４００の保護対象格納バッファ４７０の対応するエントリの有効ビット４１０をクリアし、ＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０もクリアする。また、保護対象識別子４４０を保護対象格納バッファ４７０内の別の有効なエントリへと変更する。
【００２９】
スヌープ結果がＨＩＴＭでなかった場合、リトライ判定部２２０がトランザクションをリトライとするかどうかは要求フェーズにおいてリトライと判定したかどうかによる。リトライでないと判定していた場合、当該トランザクションはトランザクション受信キュー２１０からデキューされ、発行トランザクション管理キュー２４０へとエンキューされる。当該トランザクションが沈み込み防止保護対象のトランザクションだった場合、沈み込み防止制御部４００の対応するエントリの有効ビット４１０はクリアされ、ＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０も０にクリアされる。また保護対象識別子４４０を保護対象格納バッファ４７０内の別の有効なエントリへと変更する。応答制御部２３０は、通常応答（遅延応答）をプロセッサバス１２０へと返す。
【００３０】
スヌープ結果がＨＩＴＭでなく、リトライ判定部２２０が要求フェーズでリトライと判定していた場合には、当該トランザクションはリトライされる。リトライ判定部２２０は、アドレス格納バッファ３００中の当該エントリの有効ビット３１０を０にクリアする。沈み込み防止制御部４００に対して、当該発行元識別子が保護対象格納バッファ４７０内に登録されておらず空きエントリがある場合には、当該トランザクションのアドレスと発行元識別子を保護対象格納バッファ４７０へと登録し、当該エントリの有効ビット４１０をセットする。またトランザクションが沈み込み防止保護対象のトランザクションで、ＮＯＦＬＩＧＨＴビット４５０がセットされている場合には、ＲＥＡＤＹビット４６０をセットする。当該トランザクションはトランザクション受信キュー２１０からデキューされる。応答制御部２３０はプロセッサバス１２０に対してリトライ応答を返す。
以上の動作によって、トランザクションの沈み込み防止とアドレス競合判定を可能とする。
【００３１】
続けて図２〜図３で、沈み込み保護対象でないトランザクションと沈み込み保護対象のトランザクションがアドレス競合した場合に、正しく沈み込み防止とリトライ判定ができることを示す。図２〜図３は時刻に従って左から右へと進行するタイムチャートを示している。
【００３２】
図２は沈み込み保護対象以外の発行元から発行された沈み込み保護対象のアドレスとアドレス競合するトランザクション（以下非保護対象）が先行して発行され、沈み込み保護対象の発行元から発行された沈み込み保護対象のトランザクション（以下保護対象）が続いて発行され、先行する非保護対象のトランザクションがＨＩＴＭしないケースを示している。沈み込み防止制御部４００の保護対象識別子４４０はプロセッサ１００ｂのリードを示しているとする。非保護対象のトランザクションはプロセッサ１００ａから、保護対象のトランザクションはプロセッサ１００ｂから発行されるとする。
初めに非保護対象のトランザクションがプロセッサ１００ａから発行される。沈み込み防止制御部４００を検索した結果、保護対象のトランザクションとアドレス一致し、かつ保護対象のトランザクションとは発行元が異なるため、リトライ判定部２２０はリトライと判定し、当該トランザクションをリトライ中ビット３２０ａをセットした状態でアドレス格納バッファ３００へと登録する。
【００３３】
続いて後続の保護対象のトランザクションがプロセッサ１００ｂから発行される。沈み込み防止制御部４００を検索した結果、保護対象のトランザクションであるため、沈み込み防止制御部４００は「ＯＫ」と応答する。しかしアドレス格納バッファ３００を検索した結果、先行するリトライ中ビット３２０ａがセットされたトランザクションとアドレス競合しているため、アドレス格納バッファ３００は「WeakRetry」と応答する。「WeakRetry」の結果を受けたリトライ判定部２２０は、沈み込み防止制御部４００内のＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０をチェックし、これが共に０であることから、当該トランザクションをリトライとする。この際、ＮＯＦＬＩＧＨＴビット４５０を１にセットする。保護対象のトランザクションはリトライ中ビット３２０ｂをセットした状態でアドレス格納バッファ３００へと登録される。
【００３４】
続いて、先行する非保護対象トランザクションのスヌープフェーズとなり、スヌープの結果ＨＩＴＭしなかったことをリトライ判定部２２０は知る。リトライ判定部２２０は要求フェーズでの判定結果通り、このトランザクションをリトライとし、アドレス格納バッファ３００の当該エントリの有効ビット３１０ａを０にクリアする。
続いて、後続の保護対象トランザクションのスヌープフェーズとなり、やはりスヌープの結果ＨＩＴＭしなかったことをリトライ判定部２２０は知る。リトライ判定部２２０は要求フェーズでの判定結果通り、このトランザクションをリトライとし、アドレス格納バッファ３００の当該エントリの有効ビット３１０ｂを０にクリアする。また、当該トランザクションが沈み込み防止保護対象のトランザクションであることから、沈み込み防止制御部４００内のＮＯＦＬＩＧＨＴビット４５０をチェックし、これが１であることを受けてＲＥＡＤＹビット４６０を１にセットする。
【００３５】
両方のトランザクションともリトライとなり、やがて再びプロセッサ１００から要求フェーズが開始される。先行する非保護対象トランザクションがプロセッサ１００ａから発行され、やはりリトライと判定され、リトライ中ビット３２０ｃ（３２０ａと同じでも違っていても良い）がセットされた状態でアドレス格納バッファ３００へと登録される。続いて後続の保護対象トランザクションがプロセッサ１００ｂから発行され、アドレス格納バッファ３００において「WeakRetry」と判定されるところまでは１回目と全く同じである。しかし今回は沈み込み防止制御部４００においてＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０が両方ともセットされており、「WeakRetry」の結果とこの２つのビットが共に１である結果を受けてリトライ判定部２２０は当該トランザクションを発行可能と判定する。これにより、スヌープフェーズの結果を受けた後後続の保護対象トランザクションは発行され、沈み込み防止制御部４００からは当該エントリが抹消される。また、ＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０は０にクリアされる。
以上が先行する非保護対象トランザクションがＨＩＴＭしなかった場合のタイムチャートである。
【００３６】
図３は、図２のケースとほとんど同じであるが、先行する非保護対象トランザクションがＨＩＴＭした場合のタイムチャートを示している。
図２のケースと同様に、沈み込み防止制御部４００の保護対象識別子４４０はプロセッサ１００ｂのリードを示しているとする。非保護対象のトランザクションはプロセッサ１００ａから、保護対象のトランザクションはプロセッサ１００ｂから発行されるとする。
初めに非保護対象のトランザクションがプロセッサ１００ａから発行される。沈み込み防止制御部４００を検索した結果、保護対象のトランザクションとアドレス一致し、かつ保護対象のトランザクションとは発行元が異なるため、リトライ判定部２２０はリトライと判定し、当該トランザクションをリトライ中ビット３２０ａをセットした状態でアドレス格納バッファ３００へと登録する。
【００３７】
続いて後続の保護対象のトランザクションがプロセッサ１００ｂから発行される。沈み込み防止制御部４００を検索した結果、保護対象のトランザクションであるため、沈み込み防止制御部４００は「ＯＫ」と応答する。しかしアドレス格納バッファ３００を検索した結果、先行するリトライ中ビット３２０ａがセットされたトランザクションとアドレス競合しているため、アドレス格納バッファ３００は「WeakRetry」と応答する。「WeakRetry」の結果を受けたリトライ判定部２２０は、沈み込み防止制御部４００内のＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０をチェックし、これが共に０であることから、当該トランザクションをリトライとする。この際、ＮＯＦＬＩＧＨＴビット４５０を１にセットする。保護対象トランザクションはリトライ中ビット３２０ｂをセットした状態でアドレス格納バッファ３００へと登録される。ここまでは図２と全く同じである。
続いて先行する非保護対象トランザクションのスヌープフェーズの結果、ここで図示されていない第３のプロセッサ１００ｃのキャッシュ１１０ｃ内に最新のキャッシュデータが存在したとする。プロセッサ１００ｃはプロセッサ１００ａの要求に対してＨＩＴＭと応答し、ＨＩＴＭしたことをリトライ判定部２２０は知る。この結果、リトライ判定部はこの先行する非保護対象トランザクションに対応するライトバックトランザクションをシステムに発行するために、アドレス格納バッファ３００の対応するエントリのリトライ中ビット３２０ａを０にクリアする。そしてトランザクション受信キュー２１０から当該トランザクションをデキューし、ライトバックトランザクションを発行トランザクションキュー２４０へとエンキューする。応答制御部２３０はプロセッサバス１２０に対してＨＩＴＭ応答を返す。プロセッサバス１２０上では、キャッシュ１１０ｃからキャッシュ１１０ａへとキャッシュ間転送が行われる。
【００３８】
続いて後続の保護対象トランザクションのスヌープ結果はＨＩＴＭでないため、リトライ判定部２２０は要求フェーズでの判定通りにこのトランザクションをリトライとし、アドレス格納バッファ３００の対応する有効ビット３２０ｂを０にクリアする。
その後プロセッサ１００ｂは保護対象トランザクションを再発行する。トランザクションはトランザクション受信キュー２１０に入れられ、アドレス格納バッファ３００が検索される。しかし先ほどとは違い、今度は有効ビット３１０ａが１でリトライ中ビット３２０ａが０であるエントリ（先行する非保護対象トランザクションによって引き起こされたライトバックトランザクション）とアドレス競合しているため、アドレス格納バッファ３００の検索結果は「WeakRetry」ではなく「Retry」となる。このため、沈み込み防止制御部４００のＮＯＦＬＩＧＨＴビット４５０とＲＥＡＤＹビット４６０の値に関わらず、保護対象トランザクションはリトライとなる。
以上の一連の動作により、先行する非保護対象トランザクションがＨＩＴＭとなった場合には、正しく後続の保護対象トランザクションをリトライとできることが示された。
【００３９】
以上の実施例の動作で特徴的なポイントをまとめると以下の通りである。リトライ中ビット３２０のセットされたエントリは、スヌープフェーズの結果リトライされるかＨＩＴＭして出るかのどちらかである。従って、リトライ中ビット３２０がセットされたエントリとのみアドレス競合した「WeakRetry」の時点で、同一アドレスでシステムに発行中のトランザクションは存在していないことが保証される。この時点でＮＯＦＬＩＧＨＴビット４５０をセットする。この時点で、システムに発行される可能性があるのは、先行するトランザクションがＨＩＴＭするケースと、保護対象トランザクション自身がＨＩＴＭするケースのどちらかである。
【００４０】
次に、スヌープ結果がＨＩＴＭでないことを受け、保護対象トランザクション自身がＨＩＴＭする可能性もなくなる。また、スヌープは終わっているため、これ以降発行されるトランザクションがＨＩＴＭする可能性もなくなる。この時点でＲＥＡＤＹビット４６０をセットする。唯一残る可能性は、先行するトランザクションがＨＩＴＭした可能性である。もし先行するトランザクションが仮にＨＩＴＭしていた場合は、保護対象トランザクションが再発行されたときに「WeakRetry」ではなく「Retry」となるはずなので、その場合はリトライとする。もし二度目に発行された時にも「WeakRetry」のままであれば、システムにトランザクションが発行された可能性はなくなる。これによって保護対象のトランザクションをシステムへと発行することが可能となる。
以上が発明の第一の実施の形態例である。
【実施例２】
【００４１】
続いて図４〜図８を使って本発明の第二の実施例を説明する。
（登場するモジュールの説明）
図４は第２の実施例のマルチプロセッサシステムの概略ブロック図である。アドレス競合判定機能を備えたノードコントローラ２００の内部構成図１とほとんど同じであるので省略しており、ノードコントローラ２００とプロセッサバス１２０、およびその入出力を主に示している。プロセッサバス１２０には2つ以上のプロセッサ１００ａ、１００ｂ、１００ｃが接続されており、ノードコントローラ２００を介してメモリコントローラ５００やＩＯコントローラ５１０、システム結合スイッチ５２０と接続されている。
【００４２】
プロセッサバス１２０とノードコントローラ２００の間には、プロセッサ１００ａ〜１００ｃからの要求６００を受け取るための信号、スヌープ結果６１０を受け取るための信号、ノードコントローラ２００からプロセッサバス１２０に対する応答６２０を返すための信号、およびデータ６３０をやり取りするための信号などがある。もちろん、これ以外にもさまざまな信号が存在するが、本発明とは直接関係しないため図示しない。
プロセッサ１００ａ〜１００ｃから発行される要求６００は、図５に示すように、アクセスする対象となるメモリやＩＯを示すアドレス７００、トランザクション種別７１０、発行したプロセッサ１００やスレッドを示す発行元識別子７２０、遅延応答の完了時にトランザクションを識別するために使う遅延応答識別子７３０、などから構成される。
【００４３】
トランザクション種別７１０としてはさまざまな種類があるが、図６にその一部を示す。ライトバックキャッシュを用いてメモリをアクセスする場合、リード時にはＢＲＬ、ライト時にはＢＲＩＬが発行され、キャッシュを追い出される際にＢＷＢＬが発行されてメモリへと書き戻される。トランザクション種別７１０にはこの他にもアクセスするサイズが付加されることが多いが、以下の説明には直接関係しないために省略する。
【００４４】
発行元識別子７２０は、プロセッサ１００の番号の他、マルチコアプロセッサの場合はコアの番号、マルチスレッドの場合にはスレッドの識別子などから構成されることもある。そのようなケースでも以下の説明では差異を生じない。また、効率的な沈み込みの解消のために、同一のプロセッサ１００から発行されたトランザクションであっても、リードとライトでは発行元識別子を区別することも可能である。アドレス７００と発行元識別子７２０の組み合わせにより、同一のトランザクションがリトライによって再発行された場合に、前回発行されたトランザクションと同一であることが識別できるものとする。
【００４５】
スヌープ結果６１０としては、図７に示す種類がある。あるプロセッサ１００からの要求６００に対して、同一キャッシュラインのデータを他のプロセッサが持っていないかまたは捨てた場合にはＯＫ、リード要求に対して書き換えていないキャッシュを持っている場合（Shared）はＨＩＴ、リードまたはライト要求に対して書き換えた最新キャッシュを持っている場合（Modified）にはＨＩＴＭとなる。ＨＩＴＭのケースでは、キャッシュ間転送が起こる。
【００４６】
応答６２０としては、図８に示す種別がある。通常応答は既にデータがある場合にこれを返す。トランザクション種別７１０がＢＲＬやＢＲＩＬの場合、リトライとならなかったケースではデータをメモリに取りに行く必要があるため、遅延応答とし、データが戻ってきてから後で応答する。トランザクション種別７１０がＢＷＢＬの場合は、データを返す必要はないため、データなし応答を使用する。リトライさせる場合にはリトライ応答を返す。リトライ応答を受けたプロセッサ１００は再び要求６００を発行するところからやり直す。スヌープ結果６１０がＨＩＴＭとなった場合はキャッシュ間転送によってトランザクションは完了するため、ＨＩＴＭ応答を使用する。ただし、最新のデータ６３０はメモリへと書き戻す必要があるため、ノードコントローラ２００はライトバックトランザクションを使ってメモリを最新の状態とする。
【００４７】
（先行する非保護対象がHITMしないケース）
以下、プロセッサバス１２０に対する入出力を使って、本発明の動作を説明する。
プロセッサ１００ａからあるアドレス７００ａに対して要求６００ａが発行される。トランザクション種別７１０ａはＢＲＬとする。スヌープ結果６１０ａはＯＫであったとする。ノードコントローラ２００はこれに対して応答６２０ａとして遅延応答を返す。
要求６００ａが完了する前に、プロセッサ１００ｂから同じアドレス７００ａに対して要求６００ｂが発行される。トランザクション種別７１０ｂはやはりＢＲＬとする。スヌープ結果６１０ｂはＯＫであったとする。ノードコントローラ２００は、先行する要求６００ａがまだ完了していないため、応答６２０ｂとしてリトライ応答を返す。
やがて要求６００ａに対するデータが戻り、データ６３０ａが返されて完了する。
【００４８】
次にプロセッサ１００ｃから、同じアドレス７００ａに対して要求６００ｃが発行される。トランザクション種別７１０ｃはやはりＢＲＬとする。さらに続いて、要求６００ｃに対する応答が返る前に、プロセッサ１００ｂから要求６００ｂが再び発行される。要求６００ｃに対するスヌープ結果６１０ｃはプロセッサ６００ａがクリーンなキャッシュを持っているためにＨＩＴとなる。この時点でアドレス７００ａに対してシステムに発行されて完了していないトランザクションは存在しないが、先にリトライとなった要求６００ｂの沈み込みを回避するために、ノードコントローラ２００は、要求６００ｃに対してリトライ応答を返す。
【００４９】
一方、沈み込み回避の保護対象となっている要求６００ｂに対するスヌープ結果６１０ｂはやはりＨＩＴとなる。要求６００ｂが発行された時点で同一のアドレス７００ａに対する要求６００ｃが存在していたため、ノードコントローラ２００はリトライと応答する。しかし結果として要求６００ｃはリトライとなったため、リトライ仕掛かり中のトランザクションとアドレス競合していたことになる。ノードコントローラ２００はこれを記憶しておく。
【００５０】
次にリトライとなった要求６００ｃがプロセッサ１００ｃから再び発行される。さらに続いて要求６００ｃに対する応答が返る前に、プロセッサ１００ｂから要求６００ｂが再び発行される。スヌープ結果６１０ｃ、６１０ｂは共にＨＩＴとなる。要求６００ｃは、要求６００ｂの沈み込みを回避するために、リトライ応答を返される。沈み込み回避の保護対象となっている要求６００ｂは、同一アドレス７００ａに対する要求６００ｃが存在している。しかしノードコントローラ２００は、リトライ仕掛かり中のトランザクションと二度続けてアドレス競合していることにより、要求６００ｂをリトライではなく発行するために遅延応答を返す。こうして沈み込み保護対象となっている要求６００ｂは発行される。
【００５１】
以上の一連の動作により、一度リトライとなった要求６００ｂの沈み込みが回避される。
この発明のポイントは、沈み込み保護対象でないためにリトライされるトランザクションと、沈み込み保護対象のトランザクションとが連続して発行された場合に、沈み込み保護対象のトランザクションを一度目はリトライとし、二度目は発行する、という点である。一度目にリトライとしているのは、先行するリトライされるはずのトランザクションが、ＨＩＴＭによってシステムに発行される可能性を考慮しているためである。もし一度目で発行してしまった場合、ＨＩＴＭによるライトバックトランザクションと、リードトランザクションが同時にシステムに発行され、トランザクションの実行順序が保証できないことがある。
【００５２】
（先行する非保護対象がHITMとなるケース）
次に、沈み込み保護対象の要求の前に発行されたトランザクションが、ＨＩＴＭとなるケースについて説明する。
プロセッサ１００ａからあるアドレス７００ａに対して要求６００ａが発行される。トランザクション種別７１０ａは書き込みのためのリード要求ＢＲＩＬとする。スヌープ結果６１０ａはＯＫであったとする。ノードコントローラ２００はこれに対して応答６２０ａとして遅延応答を返す。
【００５３】
要求６００ａが完了する前に、プロセッサ１００ｂから同じアドレス７００ａに対して要求６００ｂが発行される。トランザクション種別７１０ｂはＢＲＬとする。スヌープ結果６１０ｂはＯＫであったとする。ノードコントローラ２００は、先行する要求６００ａがまだ完了していないため、応答６２０ｂとしてリトライ応答を返す。
やがて要求６００ａに対するデータが戻り、データ６３０ａが返されて完了する。
【００５４】
次にプロセッサ１００ｃから、同じアドレス７００ａに対して要求６００ｃが発行される。トランザクション種別７１０ｃはやはりＢＲＬとする。さらに続いて、要求６００ｃに対する応答が返る前に、プロセッサ１００ｂから要求６００ｂが再び発行される。要求６００ｃに対するスヌープ結果６１０ｃは、プロセッサ６００ａが書き換えたキャッシュを持っているためにＨＩＴＭとなる。本来ならば先にリトライとなった要求６００ｂの沈み込みを回避するために、ノードコントローラ２００は、要求６００ｃに対してリトライ応答を返したいのだが、ＨＩＴＭしてしまった要求６００ｃはリトライできないため、応答６２０ｃとしてＨＩＴＭ応答を返す。
【００５５】
一方、沈み込み回避の保護対象となっている要求６００ｂに対するスヌープ結果６１０ｂはすでにキャッシュ間転送が起こった後なのでＯＫとなる。要求６００ｂが発行された時点で同一のアドレス７００ａに対する要求６００ｃが存在していたため、ノードコントローラ２００はリトライと応答する。要求６００ｂが発行された時点ではまだ先行する要求６００ｃがＨＩＴＭしたかどうかはわかっていないため、ノードコントローラ２００はリトライ仕掛かり中のトランザクションとアドレス競合したとしてこれを記憶しておく。
ＨＩＴＭ応答を返した要求６００ｃはプロセッサバス１２０上の最新のデータ６３０をメモリへと書き戻すためにライトバックトランザクションをシステムへと発行する。
次にプロセッサ１００ｂから要求６００ｂが再び発行される。スヌープ結果６１０ｂは既にプロセッサ１００ｃがクリーンなキャッシュを持っているためにＨＩＴとなる。しかし要求６００ｃのＨＩＴＭ応答に伴い発行されたライトバックトランザクションがまだ完了していないため、ノードコントローラ２００は要求６００ｂに対して再びリトライ応答を返す。こうして沈み込み保護対象となっている要求６００ｂは、先行するライトバックトランザクションが完了するまでの間リトライされ続ける。
【００５６】
以上の一連の動作により、同一のアドレス７００ａに対するトランザクションが、一度に一つしか発行されないことが保証される。
以上が、本発明の第二の実施の形態例である。
【実施例３】
【００５７】
次に本発明の第三の実施例である、マルチプロセッサシステムのノードコントローラにおけるアドレス競合沈み込み防止方法について説明する。図１に示すマルチプロセッサの上でノードコントローラ２００が行う一連の動作を図９〜図１７に示すフローチャートを用いて説明する。また必要に応じて図５〜図８も参照する。
初期状態では、アドレス格納バッファ３００中の全ての有効ビット３１０、沈み込み防止制御部４００の全ての有効ビット４１０、NOFLIGHTビット４５０、READYビット４６０はいずれも０とする。
また、以下の手順で２つのアドレスを比較する場合、特に断りがなければキャッシュライン単位での比較を行うものとする。
【００５８】
（要求フェーズのフローチャート）
図９〜図１３は要求フェーズの手順を示す。
図９は要求フェーズの基本フローチャートである。
ステップ１０００は、要求フェーズの開始で、プロセッサバス１２０を介してプロセッサ１００からの要求６００が到着したことによってスタートする。ノードコントローラ２００は要求６００をトランザクション受信キュー２１０にエンキューし、ステップ１０１０とステップ１０２０を並行に実施する。ここで要求６００は図５に示すようなフィールドから構成されている。
【００５９】
ステップ１０１０はアドレス格納バッファ３００を検索するステップである。検索結果として「OK」「Retry」「WeakRetry」のいずれかを返す。詳細は図１０に示す。ステップ１０３０に進む。
ステップ１０２０は沈み込み防止制御部４００を検索するステップである。検索結果として「OK」「Retry」のいずれかと、「沈み込み保護対象である」か「沈み込み保護対象でない」かのいずれかを返す。詳細は図１１に示す。ステップ１０３０に進む。
ステップ１０３０は、ステップ１０１０とステップ１０２０の検索結果のどちらかで「Retry」となったかどうかを判定するステップである。どちらかで「Retry」となっていた場合はステップ１０５０を実行後、ステップ１０９０へ進む。そうでない場合はステップ１０６０へ進む。
【００６０】
ステップ１０４０はアドレス格納バッファ３００に対して発行すると登録を行うステップである。詳細は図１２に示す。
ステップ１０５０はアドレス格納バッファ３００に対してリトライすると登録を行うステップである。詳細は図１３に示す。
ステップ１０６０は、ステップ１０１０で「WeakRetry」となったかどうかを判定するステップである。「WeakRetry」の場合はステップ１０７０へ、そうでない場合はステップ１０４０へ進む。
【００６１】
ステップ１０７０はステップ１０２０において「沈み込み保護対象である」と判定されたかどうかを判定するステップである。「沈み込み保護対象である」と判定された場合にはステップ１０８０へ、そうでない場合はステップ１０５０を実行し終了する。
ステップ１０８０は、沈み込み回避制御部４００内のREADYビット４６０が１かどうかを判定するステップである。１である場合にはステップ１０４０へ進む。そうでない場合にはステップ１０５０を実行後、ステップ１１１０へ進む。
ステップ１０９０はステップ１０２０において「沈み込み保護対象である」と判定されたかどうかを判定するステップである。「沈み込み保護対象である」と判定された場合にはステップ１１００へ、そうでない場合には終了する。
ステップ１１００はNOFLIGHTビット４５０とREADYビット４６０を０にクリアするステップである。
ステップ１１１０はNOFLIGHTビット４５０を１にセットするステップである。
【００６２】
続いて図１０にて、ステップ１０１０「アドレス格納バッファ３００の検索」の詳細フローチャートを示す。
ステップ１１２０はアドレス格納バッファ３００内の全エントリのアドレス部３３０を要求６００のアドレス７００と比較するステップである。ステップ１１３０へと続く。
ステップ１１３０は発行中（有効ビット３１０＝１、リトライ中ビット＝０）のエントリと一致したかどうかを判定するステップである。一致していればステップ１１６０へ、していなければステップ１１４０へ進む。
ステップ１１４０はリトライ中（有効ビット３１０＝１、リトライ中ビット＝１）のエントリと一致したかどうかを判定するステップである。一致していればステップ１１７０へ、していなければステップ１１５０へ進む。
ステップ１１５０はアドレス格納バッファ３００の検索結果を「OK」とするステップである。
ステップ１１６０はアドレス格納バッファ３００の検索結果を「Retry」とするステップである。
ステップ１１７０はアドレス格納バッファ３００の検索結果を「WeakRetry」とするステップである。
【００６３】
続いて図１１にてステップ１０２０「沈み込み防止制御部４００の検索」の詳細フローチャートを示す。
ステップ１１８０は保護対象識別子４４０の指す保護対象登録バッファ４７０のエントリを調べるステップである。ステップ１１９０へ進む。
ステップ１１９０は有効ビット４１０が１かどうかを判定するステップである。１である場合にはステップ１２００へ進む。
ステップ１２００はアドレス部４３０を要求６００のアドレス７００と一致したかどうかを判定するステップである。一致した場合ステップ１２１０へ、一致しなかった場合はステップ１２２０へと進む。
ステップ１２１０は発行元識別子４２０を要求６００の発行元識別子７１０と一致したかどうかを判定するステップである。一致した場合ステップ１２４０へ、一致しなかった場合ステップ１２３０へと進む。
ステップ１２２０は検索結果を「OK」とし、「沈み込み保護対象でない」とするステップである。
ステップ１２３０は検索結果を「Retry」とし、「沈み込み保護対象でない」とするステップである。
ステップ１２４０は検索結果を「OK」とし、「沈み込み保護対象である」とするステップである。
【００６４】
続いて図１２にてステップ１０４０「発行登録」の詳細フローチャートを示す。
ステップ１２５０は、要求６００を発行中としてアドレス格納バッファ３００に登録するステップである。アドレス格納バッファ３００に、有効ビット３１０＝１、リトライ中ビット３２０＝０、アドレス部３３０＝アドレス７００、というエントリを追加する。
【００６５】
続いて図１３にてステップ１０５０「リトライ登録」の詳細フローチャートを示す。
ステップ１２６０は、要求６００をリトライ中としてアドレス格納バッファ３００に登録するステップである。アドレス格納バッファ３００に、有効ビット３１０＝１、リトライ中ビット３２０＝１、アドレス部３３０＝アドレス７００、というエントリを追加する。
以上が要求フェーズのフローチャートである。
【００６６】
（スヌープフェーズのフローチャート）
続いて図１４〜図１６にてスヌープフェーズの手順を示す。
図１４はスヌープフェーズの基本フローチャートである。
ステップ１２７０はプロセッサバス１２０上にスヌープ結果６１０を受け取り、スヌープフェーズを開始するステップである。スヌープ結果６１０と要求６００との対応は発行された順序でつけられる。ステップ１２８０へ続く。
ステップ１２８０は、スヌープ結果６１０がHITMとなったかどうかを判定するステップである。HITMだった場合にはステップ１３００へ進む。HITMでなかった場合にはステップ１２９０へ進む。
【００６７】
ステップ１２９０は、要求フェーズにおいてリトライ登録されたかどうかを判定するステップである。リトライ登録されていた場合はステップ１３２０へ、そうでない場合はステップ１３１０へ進む。
ステップ１３００は要求フェーズにおいてリトライ登録されたかどうかを判定するステップである。リトライ登録されていた場合はステップ１３６０へ、そうでない場合はステップ１３７０へ進む。
ステップ１３１０は遅延応答するステップである。ノードコントローラ２００の応答制御部２３０は、応答６２０として遅延応答を返す。ステップ１３８０へ進む。
ステップ１３２０はアドレス格納バッファ３００からデキューするステップである。当該エントリの有効ビット３１０を０とする。ステップ１３３０へ進む。
【００６８】
ステップ１３３０は当該要求６００が要求フェーズのステップ１０２０において、沈み込み保護対象であるとされたかどうかを判定するステップである。沈み込み保護対象である場合にはステップ１３４０へ進む。そうでない場合にはステップ１３９０へ進む。
ステップ１３４０は沈み込み防止制御部４００のNOFLIGHTビット４５０が１かどうか判定するステップである。１である場合にはステップ１３５０へ、そうでない場合にはステップ１３９０へ進む。
【００６９】
ステップ１３５０は沈み込み防止制御部４００のREADYビット４６０に１をセットするステップである。ステップ１３９０へ進む。
ステップ１３６０はアドレス格納バッファ３００中の当該エントリを、リトライ中から発行中へと変更するステップである。対応するエントリのリトライ中ビット３２０を１から０へと変更する。ステップ１３７０へ進む。
ステップ１３７０はHITM応答するステップである。ノードコントローラ２００の応答制御部２３０は、応答６２０としてHITM応答を返す。ステップ１３８０へ進む。
ステップ１３８０は発行処理を行うステップである。発行処理の詳細は図１５に示す。
ステップ１３９０はリトライ処理を行うステップである。リトライ処理の詳細は図１６に示す。
【００７０】
続いて図１５にステップ１３８０「発行処理」の詳細フローチャートを示す。
ステップ１４００は沈み込み防止制御部４００から当該要求６００をデキューするステップである。保護対象バッファ４７０中の有効ビット４１０＝１のエントリで、発行元識別子４２０とアドレス部４３０が、要求６００の発行元識別子７２０とアドレス７００と一致している場合、有効ビット４１０を０にする。ステップ１４１０へ進む。
ステップ１４１０は要求フェーズのステップ１０２０で沈み込み保護対象であると判定されたかどうかを判定するステップである。沈み込み保護対象である場合にはステップ１４２０へ進む。沈み込み保護対象でない場合にはステップ１４４０へ進む。
ステップ１４２０は保護対象識別子４４０の指す対象を変更するステップである。保護対象バッファ４７０中に有効ビット４１０＝１となるエントリがある場合、保護対象識別子４４０をそのエントリを指すように変更する。ここで有効ビット４１０＝１となるエントリが複数ある場合、特定のエントリのみが選択されやすいことがないようにするのが望ましい。そのための選択方法としてはラウンドロビンなどの方法が考えられる。ステップ１４３０へ進む。
【００７１】
ステップ１４３０はNOFLIGHTビット４５０とREADYビット４６０をクリアするステップである。ステップ１４４０へと進む。
ステップ１４４０は要求６００をトランザクション受信キュー２１０からデキューし、発行トランザクション管理キュー２４０へとエンキューするステップである。ここでスヌープ結果６１０がHITMとなった場合、トランザクション種別はライトバックへと変更される。以上で発行処理は完了する。
【００７２】
続いて図１６にステップ１３９０「リトライ処理」の詳細フローチャートを示す。
ステップ１４５０はリトライ応答するステップである。ノードコントローラ２００の応答制御部２３０は応答６２０としてリトライ応答を返す。ステップ１４６０へ進む。
ステップ１４６０は保護対象バッファ４７０に当該要求６００を登録するステップである。保護対象バッファ４７０に空きエントリがあり、当該要求６００が登録されていない場合、有効ビット４１０＝１、発行元識別子４２０＝発行元識別子７２０、アドレス部４３０＝アドレス７００、としてエントリを登録する。ステップ１４７０へ進む。
ステップ１４７０は保護対象識別子４４０の指す対象を変更するステップである。保護対象バッファ４７０中に有効ビット４１０＝１となるエントリが１つしかない場合、保護対象識別子４４０をそのエントリを指すように変更する。ステップ１４８０へ進む。
ステップ１４８０はトランザクション受信キュー２１０から当該要求６００をデキューするステップである。以上でリトライ処理は完了する。
以上がスヌープフェーズのフローチャートである。
【００７３】
（完了フェーズのフローチャート）
続いて図１７に完了フェーズのフローチャートを示す。
ステップ１４９０は発行トランザクション管理キュー２４０中のトランザクションが完了したことにより完了フェーズが開始するステップである。完了の通知は、ACKの受信やデータリターンの到着といった手段によって行われる。ステップ１５００へ続く。
ステップ１５００はスヌープフェーズにおいて遅延応答をしたかどうかを判定するステップである。遅延応答をしていた場合ステップ１５１０へ、そうでない場合はステップ１５２０へ進む。
ステップ１５１０は遅延応答によりトランザクションを完了させるステップである。要求６００発行時の遅延応答識別子７３０を使ってデータ６３０がある場合にはデータを返す。ステップ１５２０へ進む。
ステップ１５２０はアドレス格納バッファ３００から当該要求をデキューするステップである。当該エントリの有効ビット３１０を０にクリアする。ステップ１５２０へと進む。
【００７４】
ステップ１５３０は発行トランザクション管理キュー２４０から当該要求をデキューするステップである。以上で完了フェーズは終了する。
以上が完了フェーズのフローチャートである。
【００７５】
以上の一連の動作により、トランザクションの沈み込み防止とアドレス競合判定を可能とする。
以上が本発明の第三の実施の形態例である。
【産業上の利用可能性】
【００７６】
本発明により、スヌープ結果を待たずにアドレス競合によるリトライ判定を行うことが可能になる。トランザクションがリトライしなかった場合の発行までのレイテンシを2〜3サイクル短縮することができる。また、アドレス競合判定部を固定サイクルのパイプラインで構成することが可能となる。先行するトランザクションのリトライ結果を待ってからアドレス競合判定を行うための可変長のパイプラインとした場合に比べてゲート規模を小さくできる。
【図面の簡単な説明】
【００７７】
【図１】本発明の第一・第三の実施例における全体構成図である。
【図２】本発明の第一の実施例において、先行する非保護TxがHITMしないケースのタイムチャートである。
【図３】本発明の第一の実施例において、先行する非保護TxがHITMするケースのタイムチャート
【図４】本発明の第二の実施例における、全体構成図である。
【図５】要求６００の構成を示した図である。
【図６】トランザクション種別７１０の分類を示した表である。
【図７】スヌープ結果６１０の分類を示した表である。
【図８】応答６２０の分類を示した表である。
【図９】本発明の第三の実施例における、要求フェーズの基本フローチャートである。
【図１０】ステップ１０１０「アドレス格納バッファ３００の検索」の詳細フローチャートである。
【図１１】ステップ１０２０「沈み込み防止制御部４００の検索」の詳細フローチャートである
【図１２】ステップ１０４０「発行登録」の詳細フローチャートである
【図１３】ステップ１０５０「リトライ登録」の詳細フローチャートである
【図１４】本発明の第三の実施例における、スヌープフェーズの基本フローチャートである
【図１５】ステップ１３８０「発行処理」の詳細フローチャートである
【図１６】ステップ１３９０「リトライ処理」の詳細フローチャートである
【図１７】本発明の第三の実施例における、完了フェーズの基本フローチャートである
【符号の説明】
【００７８】
100         プロセッサ
110         キャッシュ
120         プロセッサバス
200         ノードコントローラ
210         トランザクション受信キュー
220         リトライ判定部
230         応答制御部
240         発行トランザクション管理キュー
300         アドレス格納バッファ
310         有効ビット
320         リトライ中ビット
330         アドレス部
400         沈み込み防止制御部
410         有効ビット
420         発行元識別子
430         アドレス部
440         保護対象識別子
450         NOFLIGHTビット
460         READYビット
470         保護対象格納バッファ
500         メモリコントローラ
510         I/Oコントローラ
520         システム結合スイッチ
600         要求
610         スヌープ結果
620         応答
630         データ
700         アドレス
710         トランザクション種別
720         発行元識別子
730         遅延応答識別子
1000         要求600を受け取るステップ
1010         アドレス格納バッファ300を検索するステップ
1020         沈み込み防止部400を検索するステップ
1030         Retry判定を受けたかどうか判定するステップ
1040         発行登録するステップ
1050         リトライ登録するステップ
1060         WeakRetry判定を受けたかどうか判定するステップ
1070         沈み込み保護対象かどうか判定するステップ
1080         READYビット460が1かどうか判定するステップ
1090         沈み込み保護対象かどうか判定するステップ
1100         NOFLIGHTビット450とREADYビット460を0にクリアするステップ
1110         NOFLIGHTビット450を1にセットするステップ
1120         全エントリのアドレス部330を要求600のアドレス700と比較するステップ
1130         リトライ中でない有効エントリと一致したか判定するステップ
1140         リトライ中の有効エントリと一致したか判定するステップ
1150         結果をOKとするステップ
1160         結果をRetryとするステップ
1170         結果をWeakRetryとするステップ
1180         保護格納バッファ470中の保護対象識別子440の指すエントリを調べるステップ
1190         有効ビット410が1かどうか判定するステップ
1200         アドレス部430が要求600のアドレス700と一致したか判定するステップ
1210         発行元識別子420が要求600の発行元識別子710と一致したか判定するステップ
1220         結果をOKとし、沈み込み保護対象ではないとするステップ
1230         結果をRetryとし、沈み込み保護対象ではないとするステップ
1240         結果をOKとし、沈み込み保護対象であるとするステップ
1250         アドレス格納バッファ300に当該要求を登録するステップ
1260         アドレス格納バッファ300に当該要求をリトライ中として登録するステップ
1270         スヌープ結果610を受け取るステップ
1280         HITMとなったかどうか判定するステップ
1290         リトライ登録されているかどうか判定するステップ
1300         リトライ登録されているかどうか判定するステップ
1310         遅延応答するステップ
1320         アドレス格納バッファ300から当該要求をデキューするステップ
1330         沈み込み保護対象かどうか判定するステップ
1340         NOFLIGHTビット450が1かどうか判定するステップ
1350         READYビット460に1をセットするステップ
1360         アドレス格納バッファ300中のリトライ中ビット320を0に変更するステップ
1370         HITM応答するステップ
1380         発行処理するステップ
1390         リトライ処理するステップ
1400         保護対象バッファ470から当該要求をデキューするステップ
1410         沈み込み保護対象かどうか判定するステップ
1420         保護対象識別子440の指す対象を変更するステップ
1430         NOFLIGHTビット450とREADYビット460を0にクリアするステップ
1440         発行トランザクション管理キュー240にエンキューするステップ
1450         リトライ応答するステップ
1460         保護対象バッファ470に当該要求を登録するステップ
1470         保護対象識別子440の指す対象を変更するステップ
1480         トランザクション受信キュー210から当該要求をデキューするステップ
1490         発行トランザクション管理キュー240中の要求が完了するステップ
1500         遅延応答をしたかどうか判定するステップ
1510         遅延応答のデータを返すステップ
1520         アドレス格納バッファ300から当該要求をデキューするステップ
1530         発行トランザクション管理キュー240から当該要求をデキューするステップ。
【図１】
2006301825.tif 000003
【図２】
2006301825.tif 000004
【図３】
2006301825.tif 000005
【図４】
2006301825.tif 000006
【図５】
2006301825.tif 000007
【図６】
2006301825.tif 000008
【図７】
2006301825.tif 000009
【図８】
2006301825.tif 000010
【図９】
2006301825.tif 000011
【図１０】
2006301825.tif 000012
【図１１】
2006301825.tif 000013
【図１２】
2006301825.tif 000014
【図１３】
2006301825.tif 000015
【図１４】
2006301825.tif 000016
【図１５】
2006301825.tif 000017
【図１６】
2006301825.tif 000018
【図１７】
2006301825.tif 000019