(57)【要約】【課題】共有キャッシュメモリを有するマルチプロセッサにおいてプロセッサ間のデータの受け渡しを効率良く行う。【解決手段】キャッシュメモリのタグ記憶部２２０の各エントリにおいて、タグアドレス２２１、バリッド２２２、ダーティ２２３に加えて、参照回数２２４を記憶する。参照回数２２４はデータライト時に設定され、リードアクセスの度にデクリメントされる。参照回数２２４が「１」から「０」になると、そのエントリはライトバックされることなく無効化される。このキャッシュメモリをマルチプロセッサシステムにおけるプロセッサ間通信に利用すると、共有ＦＩＦＯとして機能し、使用済データは自動的に削除される。【選択図】図５
2011150684.tif 000002
【特許請求の範囲】
【請求項１】
アクセスアドレスの第１のアドレス部分によってタグアドレスおよび残り参照回数を含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、
前記複数のエントリに対応するデータを記憶するデータ記憶部と、
前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたエントリに含まれる前記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して前記一致したエントリに含まれる前記残り参照回数が残り１回である旨を表示している場合には前記リードアクセスの後に当該エントリをライトバックせずに無効化し、前記残り参照回数が残り１回よりも大きい数を表示している場合には前記残り参照回数を１回分減らすタグ制御部と、
前記リードアクセスに対して前記一致したエントリに対応するデータを前記データ記憶部から選択するデータ制御部と
を具備するキャッシュメモリ。
【請求項２】
前記タグ制御部は、ライトアクセスに対して前記第１のアドレス部分に対応する前記タグ記憶部のエントリの前記残り参照回数が何れもゼロより大きい数を表示している場合には前記タグ記憶部および前記データ記憶部にアクセスせずに前記ライトアクセスに係るデータおよび参照回数を外部のメモリに退避するように制御する
請求項１記載のキャッシュメモリ。
【請求項３】
前記データ記憶部に空き容量が存在する場合に前記退避されたデータおよび参照回数を前記メモリからそれぞれ前記データ記憶部および前記タグ記憶部にプリフェッチするよう制御するプリフェッチ制御部をさらに具備する請求項２記載のキャッシュメモリ。
【請求項４】
メモリ上の特定の領域を指定する領域指定レジスタをさらに具備し、
前記タグ制御部は、前記アクセスアドレスが前記領域に含まれる場合においてライトアクセスに対して前記第１のアドレス部分に対応する前記タグ記憶部のエントリの前記残り参照回数が何れもゼロより大きい数を表示しているときには前記タグ記憶部および前記データ記憶部にアクセスせずに前記ライトアクセスに係るデータを外部のメモリに退避するように制御する
請求項１記載のキャッシュメモリ。
【請求項５】
前記データ記憶部に空き容量が存在する場合に前記退避されたデータを前記メモリから前記データ記憶部にプリフェッチするとともに前記タグ記憶部における残り参照回数を１回に設定するよう制御するプリフェッチ制御部をさらに具備する請求項４記載のキャッシュメモリ。
【請求項６】
アクセスアドレスの第１のアドレス部分によってタグアドレスおよび残り参照回数を含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、
前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたエントリに含まれる前記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して前記一致したエントリに含まれる前記残り参照回数が残り１回である旨を表示している場合には前記リードアクセスの後に当該エントリをライトバックせずに無効化し、前記残り参照回数が残り１回よりも大きい数を表示している場合には前記残り参照回数を１回分減らすタグ制御部と
を具備するキャッシュメモリ制御装置。
【請求項７】
アクセスアドレスの第１のアドレス部分によってタグアドレスおよび寿命付きか否かを示す寿命フラグを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、
前記複数のエントリに対応するデータを記憶するとともに前記寿命フラグが寿命付きである旨を示している場合には残り参照回数を記憶するデータ記憶部と、
前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたエントリに含まれる前記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して前記一致したエントリに含まれる前記寿命フラグが寿命付きである旨を示している場合には対応する前記残り参照回数が残り１回である旨を表示しているときには前記リードアクセスの後に当該エントリをライトバックせずに無効化するタグ制御部と、
前記リードアクセスに対して前記一致したエントリに対応するデータを前記データ記憶部から選択するとともに、前記一致したエントリに含まれる前記寿命フラグが寿命付きである旨を示している場合には対応する前記残り参照回数が残り１回よりも大きい数を表示しているときには前記残り参照回数を１回分減らすデータ制御部と
を具備するキャッシュメモリ。
【請求項８】
前記タグ制御部は、ライトアクセスに対して前記第１のアドレス部分に対応する前記データ記憶部のエントリの前記残り参照回数が何れもゼロより大きい数を表示している場合には前記タグ記憶部および前記データ記憶部にアクセスせずに前記ライトアクセスに係るデータおよび参照回数を外部のメモリに退避するように制御する
請求項７記載のキャッシュメモリ。
【請求項９】
前記データ記憶部に空き容量が存在する場合に前記退避されたデータおよび参照回数を前記メモリから前記データ記憶部にプリフェッチするよう制御するプリフェッチ制御部をさらに具備する請求項８記載のキャッシュメモリ。
【請求項１０】
メモリ上の特定の領域を指定する領域指定レジスタをさらに具備し、
前記タグ制御部は、前記アクセスアドレスが前記領域に含まれる場合においてライトアクセスに対して前記第１のアドレス部分に対応する前記データ記憶部のエントリの前記残り参照回数が何れもゼロより大きい数を表示しているときには前記タグ記憶部および前記データ記憶部にアクセスせずに前記ライトアクセスに係るデータを外部のメモリに退避するように制御する
請求項７記載のキャッシュメモリ。
【請求項１１】
前記データ記憶部に空き容量が存在する場合に前記退避されたデータを前記メモリから前記データ記憶部にプリフェッチするとともに前記データ記憶部における残り参照回数を１回に設定するよう制御するプリフェッチ制御部をさらに具備する請求項１０記載のキャッシュメモリ。
【請求項１２】
アクセスアドレスの第１のアドレス部分によってタグアドレスおよびデータ量フィールドを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、
前記複数のエントリに対応するデータを記憶するデータ記憶部と、
前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたエントリに含まれる前記タグアドレスとを比較して一致したエントリを検出し、ライトアクセスの場合は前記一致したエントリに含まれる前記データ量フィールドの値に基づいて空き容量が確保されるまで待機して、前記ライトアクセス後は前記データ量フィールドに前記ライトアクセスに係るデータ量を加算し、リードアクセスの場合は前記一致したエントリに含まれる前記データ量フィールドの値に基づいて前記リードアクセスの対象となるデータ量が確保されるまで待機して、前記リードアクセス後は前記データ量フィールドから前記リードアクセスに係るデータ量を減算するタグ制御部と、
前記ライトアクセスに対して前記ライトアクセスに係るデータを前記データ記憶部の前記一致したエントリに書き込み、前記リードアクセスに対して前記一致したエントリに対応するデータを前記データ記憶部から選択するデータ制御部と
を具備するキャッシュメモリ。
【請求項１３】
前記タグ制御部は、前記ライトアクセス後に所定数のエントリについてライトアクセスが実行された遅延タイミングで前記データ量の加算を行うモードを備える請求項１２記載のキャッシュメモリ。
【請求項１４】
前記タグ制御部は、前記遅延タイミングによる前記データ量の加算を行うモードにおいて、フラッシュ指示を受けると速やかに前記データ量の加算を行う請求項１３記載のキャッシュメモリ。
【請求項１５】
前記タグ記憶部は、前記エントリに当該エントリがロックされているか否かを示すロックビットを含み、
前記タグ制御部は、前記ライトアクセスの際に前記一致したエントリに含まれる前記ロックビットをロックし、前記リードアクセスの際に前記一致したエントリに含まれる前記ロックビットをアンロックする
請求項１２記載のキャッシュメモリ。
【請求項１６】
前記タグ制御部は、前記ライトアクセス後に所定数のエントリについてライトアクセスが実行された遅延タイミングで前記ロックビットのロックを行うモードを備える請求項１５記載のキャッシュメモリ。
【請求項１７】
前記タグ制御部は、前記遅延タイミングによる前記ロックビットのロックを行うモードにおいて、フラッシュ指示を受けると速やかに前記ロックビットのアンロックを行う請求項１６記載のキャッシュメモリ。
【請求項１８】
前記タグ制御部は、前記ライトアクセスに対して前記第１のアドレス部分に対応する前記タグ記憶部のエントリの前記データ量フィールドが何れもゼロより大きい数を表示している場合または前記ロックビットが何れもロックされている場合には前記タグ記憶部および前記データ記憶部にアクセスせずに前記ライトアクセスに係るデータおよびライトデータ量を外部のメモリに退避するように制御する
請求項１５記載のキャッシュメモリ。
【請求項１９】
アクセスアドレスの第１のアドレス部分によってタグアドレスおよびデータ量フィールドを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、
前記第１のアドレス部分とは異なる前記アクセスアドレスの第２のアドレス部分と前記索引されたエントリに含まれる前記タグアドレスとを比較して一致したエントリを検出し、ライトアクセスの場合は前記一致したエントリに含まれる前記データ量フィールドの値に基づいて空き容量が確保されるまで待機して、前記ライトアクセス後は前記データ量フィールドに前記ライトアクセスに係るデータ量を加算し、リードアクセスの場合は前記一致したエントリに含まれる前記データ量フィールドの値に基づいて前記リードアクセスの対象となるデータ量が確保されるまで待機して、前記リードアクセス後は前記データ量フィールドから前記リードアクセスに係るデータ量を減算するタグ制御部と
を具備するキャッシュメモリ制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリに関し、特に共有ＦＩＦＯ（First-In First-Out）として利用可能なキャッシュメモリに関する。
【背景技術】
【０００２】
マルチプロセッサシステムにおいては、処理過程においてプロセッサ間でデータの受け渡しが必要となる場合がある。共有キャッシュメモリを有するマルチプロセッサシステムでは、共有キャッシュメモリを介して共有ＦＩＦＯとして利用することにより、データの受け渡しを行うことが考えられる。共有キャッシュメモリに関する従来の制御手法としては、Ｍ（Modified：変更）、Ｅ（Exclusive：排他）、Ｓ（Shared：共有）、Ｉ（Invalid：無効）の４状態によるＭＥＳＩプロトコルが知られている。すなわち、各キャッシュラインについて上の４状態の何れであるかを管理することにより、メインメモリへのライトバックの必要性を判断できるようにしている。この種の従来技術として、例えば、ＭＥＳＩプロトコルを用いた複数のコアキャッシュ・クラスタ間の包括的供給キャッシュが提案されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−０３７６１５号公報（表１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述の従来技術では、共有キャッシュメモリを介してプロセッサ間でデータの受け渡しが行われた後、同じエントリを用いて他のデータの受け渡しを行うためには、最初のデータをメインメモリにライトバックするか、無効化する必要がある。前者の場合にはライトバック処理のためにメインメモリに接続するバスを占有するため、他のプロセッサにも影響を与えるおそれがある。また、後者の場合には、明示的に無効化命令を共有キャッシュメモリに発行する必要があり、プロセッサにおける処理サイクル数が増大するという問題がある。
【０００５】
また、上述の従来技術では、共有キャッシュメモリを介してプロセッサ間でデータの受け渡しを行う際、プロセッサ間の同期を別途実行する必要がある。すなわち、ライト側のプロセッサからライトされたデータをリード側プロセッサがリードする際、ライトされた以上のサイズをリードしないようにリード側の追い越しを防止しなければならない。
【０００６】
本発明はこのような状況に鑑みてなされたものであり、共有キャッシュメモリを有するマルチプロセッサにおいてプロセッサ間のデータの受け渡しを効率良く行うことを目的とする。また、本発明は、マルチプロセッサにおいてプロセッサ間のデータの受け渡しを行う際、共有キャッシュメモリにより同期を実現することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、アクセスアドレスの第１のアドレス部分によってタグアドレスおよび残り参照回数を含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、上記複数のエントリに対応するデータを記憶するデータ記憶部と、上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたエントリに含まれる上記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して上記一致したエントリに含まれる上記残り参照回数が残り１回である旨を表示している場合には上記リードアクセスの後に当該エントリをライトバックせずに無効化し、上記残り参照回数が残り１回よりも大きい数を表示している場合には上記残り参照回数を１回分減らすタグ制御部と、上記リードアクセスに対して上記一致したエントリに対応するデータを上記データ記憶部から選択するデータ制御部とを具備するキャッシュメモリである。これにより、残り参照回数に相当する回数分リードされた後にそのデータを無効化させるという作用をもたらす。
【０００８】
また、この第１の側面において、上記タグ制御部は、ライトアクセスに対して上記第１のアドレス部分に対応する上記タグ記憶部のエントリの上記残り参照回数が何れもゼロより大きい数を表示している場合には上記タグ記憶部および上記データ記憶部にアクセスせずに上記ライトアクセスに係るデータおよび参照回数を外部のメモリに退避するように制御するようにしてもよい。これにより、キャッシュメモリの容量を超えるサイズのデータを外部のメモリに退避して、その後の受け渡しを継続させるという作用をもたらす。また、この場合において、上記データ記憶部に空き容量が存在する場合に上記退避されたデータおよび参照回数を上記メモリからそれぞれ上記データ記憶部および上記タグ記憶部にプリフェッチするよう制御するプリフェッチ制御部をさらに具備してもよい。これにより、メモリからキャッシュメモリへのデータ転送を促すという作用をもたらす。
【０００９】
また、この第１の側面において、メモリ上の特定の領域を指定する領域指定レジスタをさらに具備し、上記タグ制御部は、上記アクセスアドレスが上記領域に含まれる場合においてライトアクセスに対して上記第１のアドレス部分に対応する上記タグ記憶部のエントリの上記残り参照回数が何れもゼロより大きい数を表示しているときには上記タグ記憶部および上記データ記憶部にアクセスせずに上記ライトアクセスに係るデータを外部のメモリに退避するように制御するようにしてもよい。これにより、キャッシュメモリの容量を超えるサイズのデータを領域指定レジスタにより指定されるメモリ領域に退避して、その後の受け渡しを継続させるという作用をもたらす。また、この場合において、上記データ記憶部に空き容量が存在する場合に上記退避されたデータを上記メモリから上記データ記憶部にプリフェッチするとともに上記タグ記憶部における残り参照回数を１回に設定するよう制御するプリフェッチ制御部をさらに具備してもよい。これにより、メモリからキャッシュメモリへのデータ転送を促すという作用をもたらす。
【００１０】
また、本発明の第２の側面は、アクセスアドレスの第１のアドレス部分によってタグアドレスおよび残り参照回数を含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたエントリに含まれる上記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して上記一致したエントリに含まれる上記残り参照回数が残り１回である旨を表示している場合には上記リードアクセスの後に当該エントリをライトバックせずに無効化し、上記残り参照回数が残り１回よりも大きい数を表示している場合には上記残り参照回数を１回分減らすタグ制御部とを具備するキャッシュメモリ制御装置である。これにより、残り参照回数に相当する回数分リードされた後にそのデータを無効化させるという作用をもたらす。
【００１１】
また、本発明の第３の側面は、アクセスアドレスの第１のアドレス部分によってタグアドレスおよび寿命付きか否かを示す寿命フラグを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、上記複数のエントリに対応するデータを記憶するとともに上記寿命フラグが寿命付きである旨を示している場合には残り参照回数を記憶するデータ記憶部と、上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたエントリに含まれる上記タグアドレスとを比較して一致したエントリを検出し、リードアクセスに対して上記一致したエントリに含まれる上記寿命フラグが寿命付きである旨を示している場合には対応する上記残り参照回数が残り１回である旨を表示しているときには上記リードアクセスの後に当該エントリをライトバックせずに無効化するタグ制御部と、上記リードアクセスに対して上記一致したエントリに対応するデータを上記データ記憶部から選択するとともに、上記一致したエントリに含まれる上記寿命フラグが寿命付きである旨を示している場合には対応する上記残り参照回数が残り１回よりも大きい数を表示しているときには上記残り参照回数を１回分減らすデータ制御部とを具備するキャッシュメモリである。これにより、残り参照回数に相当する回数分リードされた後にそのデータを無効化させるという作用をもたらす。
【００１２】
また、この第３の側面において、上記タグ制御部は、ライトアクセスに対して上記第１のアドレス部分に対応する上記データ記憶部のエントリの上記残り参照回数が何れもゼロより大きい数を表示している場合には上記タグ記憶部および上記データ記憶部にアクセスせずに上記ライトアクセスに係るデータおよび参照回数を外部のメモリに退避するように制御するようにしてもよい。これにより、キャッシュメモリの容量を超えるサイズのデータを外部のメモリに退避して、その後の受け渡しを継続させるという作用をもたらす。また、この場合において、上記データ記憶部に空き容量が存在する場合に上記退避されたデータおよび参照回数を上記メモリから上記データ記憶部にプリフェッチするよう制御するプリフェッチ制御部をさらに具備してもよい。これにより、メモリからキャッシュメモリへのデータ転送を促すという作用をもたらす。
【００１３】
また、この第３の側面において、メモリ上の特定の領域を指定する領域指定レジスタをさらに具備し、上記タグ制御部は、上記アクセスアドレスが上記領域に含まれる場合においてライトアクセスに対して上記第１のアドレス部分に対応する上記データ記憶部のエントリの上記残り参照回数が何れもゼロより大きい数を表示しているときには上記タグ記憶部および上記データ記憶部にアクセスせずに上記ライトアクセスに係るデータを外部のメモリに退避するように制御するようにしてもよい。これにより、キャッシュメモリの容量を超えるサイズのデータを領域指定レジスタにより指定されるメモリ領域に退避して、その後の受け渡しを継続させるという作用をもたらす。また、この場合において、上記データ記憶部に空き容量が存在する場合に上記退避されたデータを上記メモリから上記データ記憶部にプリフェッチするとともに上記データ記憶部における残り参照回数を１回に設定するよう制御するプリフェッチ制御部をさらに具備してもよい。これにより、メモリからキャッシュメモリへのデータ転送を促すという作用をもたらす。
【００１４】
また、本発明の第４の側面は、アクセスアドレスの第１のアドレス部分によってタグアドレスおよびデータ量フィールドを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、上記複数のエントリに対応するデータを記憶するデータ記憶部と、上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたエントリに含まれる上記タグアドレスとを比較して一致したエントリを検出し、ライトアクセスの場合は上記一致したエントリに含まれる上記データ量フィールドの値に基づいて空き容量が確保されるまで待機して、上記ライトアクセス後は上記データ量フィールドに上記ライトアクセスに係るデータ量を加算し、リードアクセスの場合は上記一致したエントリに含まれる上記データ量フィールドの値に基づいて上記リードアクセスの対象となるデータ量が確保されるまで待機して、上記リードアクセス後は上記データ量フィールドから上記リードアクセスに係るデータ量を減算するタグ制御部と、上記ライトアクセスに対して上記ライトアクセスに係るデータを上記データ記憶部の上記一致したエントリに書き込み、上記リードアクセスに対して上記一致したエントリに対応するデータを上記データ記憶部から選択するデータ制御部とを具備するキャッシュメモリである。これにより、データ量フィールドの値に基づいてライトアクセスの際の空き待ちおよびリードアクセスの際のデータ待ちを調整させるという作用をもたらす。
【００１５】
また、この第４の側面において、上記タグ制御部は、上記ライトアクセス後に所定数のエントリについてライトアクセスが実行された遅延タイミングで上記データ量の加算を行うモードを備えてもよい。これにより、データ量フィールドの更新を遅延させ、データの再書込みを許容させるという作用をもたらす。また、それに拘らず、上記タグ制御部は、上記遅延タイミングによる上記データ量の加算を行うモードにおいて、フラッシュ指示を受けると速やかに上記データ量の加算を行うようにしてもよい。
【００１６】
また、この第４の側面において、上記タグ記憶部は、上記エントリに当該エントリがロックされているか否かを示すロックビットを含み、上記タグ制御部は、上記ライトアクセスの際に上記一致したエントリに含まれる上記ロックビットをロックし、上記リードアクセスの際に上記一致したエントリに含まれる上記ロックビットをアンロックするようにしてもよい。これにより、使用中のエントリが他のアクセスにより追い出されることを防止させるという作用をもたらす。この場合において、上記タグ制御部は、上記ライトアクセス後に所定数のエントリについてライトアクセスが実行された遅延タイミングで上記ロックビットのロックを行うモードを備えてもよい。これにより、ロックビットの更新を遅延させ、データの再読出しを許容させるという作用をもたらす。また、それに拘らず、上記タグ制御部は、上記遅延タイミングによる上記ロックビットのロックを行うモードにおいて、フラッシュ指示を受けると速やかに上記ロックビットのアンロックを行うようにしてもよい。
【００１７】
また、この第４の側面において、上記タグ制御部は、上記ライトアクセスに対して上記第１のアドレス部分に対応する上記タグ記憶部のエントリの上記データ量フィールドが何れもゼロより大きい数を表示している場合または上記ロックビットが何れもロックされている場合には上記タグ記憶部および上記データ記憶部にアクセスせずに上記ライトアクセスに係るデータおよびライトデータ量を外部のメモリに退避するように制御するようにしてもよい。これにより、キャッシュメモリの容量を超えるサイズのデータを外部のメモリに退避して、その後の受け渡しを継続させるという作用をもたらす。
【００１８】
また、本発明の第５の側面は、アクセスアドレスの第１のアドレス部分によってタグアドレスおよびデータ量フィールドを含む複数のエントリのうち少なくとも一つが索引されるタグ記憶部と、上記第１のアドレス部分とは異なる上記アクセスアドレスの第２のアドレス部分と上記索引されたエントリに含まれる上記タグアドレスとを比較して一致したエントリを検出し、ライトアクセスの場合は上記一致したエントリに含まれる上記データ量フィールドの値に基づいて空き容量が確保されるまで待機して、上記ライトアクセス後は上記データ量フィールドに上記ライトアクセスに係るデータ量を加算し、リードアクセスの場合は上記一致したエントリに含まれる上記データ量フィールドの値に基づいて上記リードアクセスの対象となるデータ量が確保されるまで待機して、上記リードアクセス後は上記データ量フィールドから上記リードアクセスに係るデータ量を減算するタグ制御部と
を具備するキャッシュメモリ制御装置である。これにより、データ量フィールドの値に基づいてライトアクセスの際の空き待ちおよびリードアクセスの際のデータ待ちを調整させるという作用をもたらす。
【発明の効果】
【００１９】
本発明によれば、共有キャッシュメモリを有するマルチプロセッサにおいてプロセッサ間のデータの受け渡しを効率良く行うことができるという優れた効果を奏し得る。また、  本発明によれば、マルチプロセッサにおいてプロセッサ間のデータの受け渡しを行う際、共有キャッシュメモリにより同期を実現することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施の形態における情報処理システムの一構成例を示す図である。
【図２】本発明の実施の形態における共有キャッシュ２００の機能構成例を示す図である。
【図３】本発明の実施の形態における共有キャッシュ２００の回路構成例を示す図である。
【図４】本発明の実施の形態におけるデータ記憶部２４０とメインメモリ３００との対応関係の例を示す図である。
【図５】本発明の第１の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。
【図６】本発明の第１の実施の形態におけるタグ記憶部２２０の更新に関する構成例を示す図である。
【図７】本発明の第１の実施の形態におけるメインメモリ３００とＦＩＦＯ記憶領域３１０の関係の第１の例を示す図である。
【図８】本発明の第１の実施の形態における共有キャッシュ２００のライト時の処理手順を示す図である。
【図９】本発明の第１の実施の形態における共有キャッシュ２００のリード時の処理手順を示す図である。
【図１０】本発明の第１の実施の形態におけるプロセッサ間のデータ受け渡しシーケンスの第１の例を示す図である。
【図１１】本発明の第１の実施の形態におけるプロセッサ間のデータ受け渡しシーケンスの第２の例を示す図である。
【図１２】本発明の第１の実施の形態による情報処理システムにおいてプリフェッチ機能を設けた構成例を示す図である。
【図１３】本発明の第１の実施の形態におけるプリフェッチ制御部４００の一構成例を示す図である。
【図１４】本発明の第１の実施の形態におけるプリフェッチ制御部４００の状態遷移の一例を示す図である。
【図１５】本発明の第１の実施の形態におけるメインメモリ３００とＦＩＦＯ記憶領域３１０の関係の第２の例を示す図である。
【図１６】本発明の第１の実施の形態においてＦＩＦＯ記憶領域の指定を行った際の共有キャッシュ２００のリード時の処理手順を示す図である。
【図１７】本発明の第２の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。
【図１８】本発明の第２の実施の形態におけるデータ記憶部２４０のフィールド構成例を示す図である。
【図１９】本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュラインライト時の処理手順を示す図である。
【図２０】本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュラインリード時の処理手順を示す図である。
【図２１】本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュライン置換時の処理手順を示す図である。
【図２２】本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインリード時の処理手順を示す図である。
【図２３】本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインライトバック時の処理手順を示す図である。
【図２４】本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインフェッチ時の処理手順を示す図である。
【図２５】本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインライト時の処理手順を示す図である。
【図２６】本発明の第２の実施の形態における共有キャッシュ２００へのデータライトシーケンスの例を示す図である。
【図２７】本発明の第２の実施の形態における共有キャッシュ２００からのデータリードシーケンスの例を示す図である。
【図２８】本発明の第３の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。
【図２９】本発明の第３の実施の形態における共有キャッシュ２００のライト時の処理手順を示す図である。
【図３０】本発明の第３の実施の形態における共有キャッシュ２００のリード時の処理手順を示す図である。
【図３１】本発明の第３の実施の形態における利用可能量２２７の遅延設定機構の態様を示す図である。
【図３２】本発明の第３の実施の形態におけるロック２２６の遅延解除機構の態様を示す図である。
【図３３】本発明の第３の実施の形態における遅延更新機構を利用したデータ順序入れ換えの一例を示す図である。
【図３４】本発明の第３の実施の形態における遅延更新機構を利用したデータサイズ圧縮の一例を示す図である。
【図３５】一般的なコーデックにおけるＩＤＣＴ係数デコード処理アルゴリズムを示す図である。
【図３６】一般的なコーデックにおけるＩＤＣＴ係数のジグザグスキャンの態様を示す図である。
【図３７】従来手法により最適化されたコーデックのＩＤＣＴ係数デコード処理アルゴリズムを示す図である。
【図３８】本発明の第３の実施の形態における遅延更新機構を利用したコーデックのＩＤＣＴ係数デコード処理アルゴリズムを示す図である。
【図３９】本発明の実施の形態の応用例としてのデジタルテレビ放送システムの一例を示す図である。
【図４０】本発明の実施の形態の応用例におけるインターリーバ６１０の一構成例を示す図である。
【図４１】本発明の実施の形態の応用例におけるデインターリーバ６３０の一構成例を示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（参照回数フィールドをタグ記憶部に設けた例）
２．第２の実施の形態（参照回数フィールドをデータ記憶部に設けた例）
３．第３の実施の形態（利用可能量フィールドおよびロックフィールドをタグ記憶部に設けた例）
４．応用例（デジタルテレビ放送システムへの適用例）
５．変形例
【００２２】
＜１．第１の実施の形態＞
［情報処理システムの構成］
図１は、本発明の実施の形態における情報処理システムの一構成例を示す図である。この情報処理システムは、ｐ個（ｐは１以上の整数）のプロセッサ１００−１乃至１００−ｐ（以下、これらをまとめてプロセッサ１００と呼称する場合がある。）と、共有キャッシュ（二次キャッシュ）２００と、メインメモリ３００とを備える。プロセッサ１００−１乃至１００−ｐと共有キャッシュ２００との間は、システムバス１９０により相互に接続されている。
【００２３】
プロセッサ１００は、それぞれ内部に一次キャッシュ１１０−１乃至１１０−ｐ（以下、これらをまとめて一次キャッシュ１１０と呼称する場合がある。）を備える。これにより、プロセッサ１００は、一次キャッシュ１１０にヒットしている限りにおいては一次キャッシュ１１０を用いてデータアクセスを行うが、一次キャッシュ１１０においてミスヒットとなった場合には共有キャッシュ２００にアクセスを行う。また、プロセッサ１００は、一次キャッシュ１１０でミスヒットとなった際、共有キャッシュ２００にヒットしている限りにおいては共有キャッシュ２００を用いてデータアクセスを行う。一方、共有キャッシュ２００においてミスヒットとなった場合にはメインメモリ３００にアクセスを行う。
【００２４】
このように、本発明の実施の形態においては、プロセッサ１００のそれぞれに対応する一次キャッシュ１１０、共有キャッシュ（二次キャッシュ）２００、メインメモリ３００という３階層の記憶構造となっている。
【００２５】
［共有キャッシュ２００の構成］
図２は、本発明の実施の形態における共有キャッシュ２００の機能構成例を示す図である。この共有キャッシュ２００は、調停部２１０と、タグ記憶部２２０と、タグ制御部２３０と、データ記憶部２４０と、データ制御部２５０と、応答部２６０とを備えている。
【００２６】
調停部２１０は、プロセッサ１００−１乃至１００−ｐおよびメインメモリ３００からのアクセスを調停して、何れかにアクセス許可を付与するものである。この調停部２１０における調停としては、例えば、ラウンドロビン方式によりプロセッサ１００−１乃至１００−ｐおよびメインメモリ３００に順次割り当てていくことが考えられる。許可されたアクセスは、タグ制御部２３０に供給される。
【００２７】
タグ記憶部２２０は、複数のエントリからなるメモリであり、各エントリにタグアドレス等を保持するものである。タグアドレスは、後述するように、アクセスされたアドレスの一部を示すものである。タグ記憶部２２０の各エントリは、アクセスされたアドレスの他の一部により索引される。
【００２８】
タグ制御部２３０は、アクセスされたアドレスに基づいて、タグ記憶部２２０においてアクセスすべきエントリを選択して制御するものである。このタグ制御部２３０により選択されたエントリは、データ制御部２５０に通知される。
【００２９】
データ記憶部２４０は、タグ記憶部２２０の各エントリに対応するデータを記憶するものである。このデータ記憶部２４０に記憶されるデータはキャッシュライン毎に管理され、メインメモリ３００やプロセッサ１００との間の転送もキャッシュライン毎に行われる。
【００３０】
データ制御部２５０は、タグ制御部２３０において選択されたエントリに応じて、データ記憶部２４０に記憶されたデータ（キャッシュライン）にアクセスするものである。リードアクセスやライトバック動作の場合には、データ記憶部２４０から読み出されたデータは応答部２６０に供給される。ライトアクセスの場合には、データ記憶部２４０から読み出されたデータの中の対応する位置にライトデータが埋め込まれて、再びデータ記憶部２４０に記憶される。
【００３１】
応答部２６０は、データ制御部２５０から供給されたデータをプロセッサ１００−１乃至１００−ｐまたはメインメモリ３００に出力するものである。プロセッサ１００からのリードアクセスに対する応答であれば、データはアクセスしたプロセッサ１００に出力される。メインメモリ３００へのライトバック動作であれば、データはメインメモリ３００に出力される。
【００３２】
図３は、本発明の実施の形態における共有キャッシュ２００の回路構成例を示す図である。ここでは、共有キャッシュ２００として、ライン数１２８、ラインサイズ６４Ｂ（バイト）の２ウェイ・セット・アソシアティブ・キャッシュを想定する。すなわち、同一インデックスアドレスに対して最大２つのキャッシュラインを記憶可能であり、各キャッシュラインに対応するデータのサイズは６４バイトとなる。
【００３３】
メインメモリ３００の領域を２５６ＭＢとすると、必要なアドレスは２８ビットとなる。ブロックサイズが６４バイトであるため、アクセスアドレスの第０乃至５ビットの計６ビットがライン内アドレスに割り当てられる。また、ライン数が１２８であることから、タグ記憶部２２０のエントリを索引するためのインデックスアドレスは、アクセスアドレスの第６乃至１２ビットの計７ビットに割り当てられる。したがって、タグアドレスは、アクセスアドレスの第１３乃至２７ビットの計１５ビットに割り当てられる。アクセスアドレスのうちタグアドレスは信号線２０１を介して、インデックスアドレスは信号線２０２を介して、ライン内アドレスは信号線２０３を介して、それぞれ共有キャッシュ２００に供給される。
【００３４】
タグ記憶部２２０は、それぞれ１２８個のエントリから成る２つのウェイ（ｗａｙ）＃０および＃１を備える。タグ記憶部２２０の各ウェイは、信号線２０２を介して供給されるインデックスアドレスによって索引される。したがって、この例では、２つのエントリが索引されることになる。
【００３５】
タグ制御部２３０は、比較器２３１および２３２と、論理和演算器２３３とを備え、タグ記憶部２２０において索引されたエントリのうちタグアドレスが一致するものを検出する。比較器２３１は、タグ記憶部２２０のウェイ＃０において索引されたエントリに含まれるタグアドレスと、信号線２０１を介して供給されたタグアドレスとを比較して一致を検出するものである。同様に、比較器２３２は、タグ記憶部２２０のウェイ＃１において索引されたエントリに含まれるタグアドレスと、信号線２０１を介して供給されたタグアドレスとを比較して一致を検出するものである。これら比較器２３１および２３２における比較結果は、論理和演算器２３３およびデータ制御部２５０に供給される。論理和演算器２３３は、比較器２３１または２３２の何れかで一致が検出された場合に、ヒットした旨を、信号線２９８を介して出力するものである。ただし、後述するように、対応するエントリのバリッドビットが無効である旨を示している場合には、ミスヒットとして判定される。
【００３６】
データ記憶部２４０は、それぞれ１２８個のキャッシュラインから成る２つのウェイ＃０および＃１を備え、タグ記憶部２２０の各エントリに対応するデータを記憶する。このデータ記憶部２４０もタグ記憶部２２０と同様に信号線２０２を介して供給されるインデックスアドレスによって索引される。これにより、２つの６４バイトのラインデータがデータ制御部２５０に供給される。
【００３７】
データ制御部２５０は、選択器２５１および２５２を備える。選択器２５１は、データ記憶部２４０から供給された２つの６４Ｂデータの何れか一方を選択するものである。すなわち、比較器２３１において一致が検出された場合にはデータ記憶部２４０のウェイ＃０のラインデータが選択され、比較器２３２において一致が検出された場合にはデータ記憶部２４０のウェイ＃１のラインデータが選択される。ただし、後述するように、一致が検出されたエントリのバリッドビットが無効である旨を示している場合にはそのキャッシュラインのデータは選択されない。比較器２３１および２３２の何れにおいても一致が検出されない場合には、何れのキャッシュラインのデータも選択されない。
【００３８】
選択器２５２は、選択されたラインデータのうちライン内アドレスとして指定された位置のデータを選択するものである。ライン内アドレスは、信号線２０３を介して供給される。ただし、この選択器２５２の機能はプロセッサ１００側に備えるようにしてもよい。何れの場合も、ラインデータ全体またはその一部は信号線２９９を介して応答部２６０に出力される。
【００３９】
図４は、本発明の実施の形態におけるデータ記憶部２４０とメインメモリ３００との対応関係の例を示す図である。ここでは、図３の例と同様に、共有キャッシュ２００として、ライン数１２８、ブロックサイズ６４バイトの２ウェイ・セット・アソシアティブ・キャッシュを想定する。
【００４０】
データ記憶部２４０の各キャッシュラインは、上述のようにインデックスアドレスにより索引される。第０ラインのインデックスアドレスは「０」、第１ラインのインデックスアドレスは「１」であり、同様にして、第１２７ラインのインデックスアドレスは「１２７」である。
【００４１】
データ記憶部２４０の第０ラインには、アドレスの下位１３ビットが「０ｂ０００００００００００００」（「０ｂ」は、続く数字が２進数であることを意味する。以下同様。）であるラインが記憶される。データ記憶部２４０の第１ラインには、アドレスの下位１３ビットが「０ｂ００００００１００００００」であるラインが記憶される。データ記憶部２４０の第２ラインには、アドレスの下位１３ビットが「０ｂ０００００１０００００００」であるラインが記憶される。データ記憶部２４０の第３ラインには、アドレスの下位１３ビットが「０ｂ０００００１１００００００」であるラインが記憶される。データ記憶部２４０の第４ラインには、アドレスの下位１３ビットが「０ｂ００００１００００００００」であるラインが記憶される。同様に、データ記憶部２４０の第１２７ラインには、アドレスの下位１３ビットが「０ｂ１１１１１１１００００００」であるラインが記憶される。
【００４２】
すなわち、この例では、あるインデックスアドレスに対して共有キャッシュ２００に記憶可能なキャッシュラインは２つに限定されている。したがって、既に２つのキャッシュラインが占有されているセットに新たなデータを記憶するためには、何れかのキャッシュラインを追い出して置換（リプレース）する必要がある。置換すべきキャッシュライン候補を選択する手法として、例えば、最も近い時期に使用されていないキャッシュラインを追い出す手法（ＬＲＵ法）が知られている。
【００４３】
［タグ記憶部２２０の構成と機能］
図５は、本発明の第１の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。タグ記憶部２２０の各エントリは、タグアドレス２２１、バリッド２２２、ダーティ２２３、および、参照回数２２４の各フィールドを備える。
【００４４】
タグアドレス２２１は、そのエントリに対応するキャッシュラインのタグアドレス（アドレスの上位１５ビット）を記憶するものである。図中では、このタグアドレス２２１を「ＴＡＧ」と略している。
【００４５】
バリッド２２２は、そのエントリの有効性を示すバリッドビット（Ｖａｌｉｄ）を記憶するものである。このバリッド２２２が「１」を示していればそのエントリに対応するキャッシュラインのデータは有効であり、「０」を示していれば比較器２３１または２３２において一致が検出されたとしてもヒットとは判定されない。図中では、このバリッド２２２を「Ｖ」と略している。
【００４６】
ダーティ２２３は、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータとが一致していないことを示すダーティービット（Ｄｉｒｔｙ）を記憶するものである。このダーティ２２３が「１」を示している場合には、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータは一致しておらず、共有キャッシュ２００のデータが最新のデータであることを意味する。一方、ダーティ２２３が「０」を示している場合には、そのエントリに対応するキャッシュラインのデータとメインメモリ３００のデータは一致していることを意味する。図中では、このダーティ２２３を「Ｄ」と略している。
【００４７】
参照回数２２４は、そのエントリに対応するキャッシュラインが参照されるべき残り参照回数（Ｒｅｆｅｒｅｎｃｅ  ｎｕｍｂｅｒ）を記憶するものである。図中では、この参照回数２２４を「Ｒ」と略している。この参照回数２２４は、受け渡し対象となるデータがキャッシュラインにライトされた際に、同時に設定される。この参照回数２２４が「２」以上を示している場合にリードアクセスが行われた際には、参照回数２２４に記憶される値から「１」減算（デクリメント）される。そして、参照回数２２４が「１」を示している場合にリードアクセスが行われた際には、そのリードアクセスの後にそのキャッシュラインは無効化される。その際、メインメモリ３００へのライトバックは行われない。
【００４８】
なお、参照回数２２４が「０」を示している場合には、リードアクセスが行われてもその値に変化はない。これにより、通常のキャッシュアルゴリズムに沿った動作を行わせることができる。すなわち、何度リードアクセスが行われてもキャッシュヒットである限り無効化は行われず、必要になったときにはメインメモリ３００へのライトバックが行われる。
【００４９】
図６は、本発明の第１の実施の形態におけるタグ記憶部２２０の更新に関する構成例を示す図である。ここでは、タグ記憶部２２０またはタグ制御部２３０に、比較器５１１、減算器５１２および比較器５１３を備えることを想定する。
【００５０】
リードアクセスの際、対象となるキャッシュラインの参照回数２２４が読み出され、比較器５１１において参照回数２２４が「２」以上を示している旨が検出されると、その参照回数２２４は減算器５１２によって「１」減算（デクリメント）される。また、リードアクセスの際、対象となるキャッシュラインの参照回数２２４が読み出され、比較器５１３において参照回数２２４が「１」を示している旨が検出されると、そのキャッシュラインの無効化が行われる。すなわち、バリッド２２２およびダーティ２２３がゼロクリアされる。
【００５１】
これにより、各プロセッサ１００間で共有キャッシュ２００を共有ＦＩＦＯとして利用してデータの受け渡しを行うことができる。その際、受け渡しの済んだデータはライトバックされずに無効化されるため、共有キャッシュ２００には残存しない。
【００５２】
［キャッシュ容量を超えるサイズのデータ受け渡し］
共有キャッシュ２００の容量を越えるサイズのデータをプロセッサ１００間で転送するためには、共有キャッシュ２００を使用しないアンキャッシュ経路と、データ制御部２５０において以下のような制御機能とを追加することが有用である。
【００５３】
例えば、プロセッサ１００−１が参照回数を伴ったデータを共有キャッシュ２００にライトすることを想定する。ライトされたデータの量がある一定量（例えば、共有キャッシュ２００の容量）を越えた段階で、タグ制御部２３０においてライトアクセスに対するタグ一致検出の結果、全てのウェイにおいて参照回数２２４が既に設定されている事象が発生する。この場合、共有キャッシュ２００をスルーし、アンキャッシュの経路を用いてメインメモリ３００へデータを直接格納する。このとき、ライトデータに付随する参照回数もメインメモリ３００へ退避する。
【００５４】
その後、例えば、プロセッサ１００−２が共有キャッシュ２００からデータを読み出し、参照回数２２４が「１」から「０」に変化したキャッシュラインを無効化する。そして、引き続きプロセッサ１００−２からリードアクセス要求があると、メインメモリ３００から共有キャッシュ２００へデータがフィルされる。このとき、退避されていた参照回数も参照回数２２４に設定される。これにより、プロセッサ１００−２からのリードアクセスが可能となる。
【００５５】
図７は、本発明の第１の実施の形態におけるメインメモリ３００とＦＩＦＯ記憶領域３１０の関係の第１の例を示す図である。プロセッサ１００間で共有されるＦＩＦＯ記憶領域３１０として使用されるのは、メインメモリ３００の連続空間である。したがって、このＦＩＦＯ記憶領域３１０は、開始アドレスとサイズによって特定される。この例では、ＦＩＦＯ記憶領域３１０は規定値として予め定められているものとしている。このＦＩＦＯ記憶領域３１０には、上述のように全てのウェイにおいて参照回数２２４が既に設定されている場合、共有キャッシュ２００をスルーして、ライトデータが退避される。
【００５６】
また、メインメモリ３００には、ＦＩＦＯ記憶領域３１０以外に、参照回数を退避するための参照回数記憶領域３２０が割り当てられる。この参照回数記憶領域３２０には、上述のように全てのウェイにおいて参照回数２２４が既に設定されている場合、共有キャッシュ２００をスルーして、ライトデータに付随する参照回数が退避される。
【００５７】
［共有キャッシュ２００の動作］
図８は、本発明の第１の実施の形態における共有キャッシュ２００のライト時の処理手順を示す図である。
【００５８】
タグ制御部２３０における比較の結果、キャッシュヒットが検出されると（ステップＳ９１０）、そのキャッシュラインのダーティ２２３に「１」が設定され、ライトデータに付随する参照回数が参照回数２２４に設定される（ステップＳ９１８）。そして、ライトデータがデータ記憶部２４０に書き込まれる（ステップＳ９１９）。
【００５９】
一方、ミスヒットが検出された場合（ステップＳ９１０）、未使用となっているウェイが存在すれば（ステップＳ９１１）、キャッシュラインが追加され（ステップＳ９１２）、そのキャッシュラインのバリッド２２２に「１」が設定される（ステップＳ９１７）。そして、そのキャッシュラインのダーティ２２３に「１」が設定され、ライトデータに付随する参照回数が参照回数２２４に設定される（ステップＳ９１８）。そして、ライトデータがデータ記憶部２４０に書き込まれる（ステップＳ９１９）。
【００６０】
ミスヒットが検出された場合において（ステップＳ９１０）、全てのウェイが使用中であって（ステップＳ９１１）、かつ、全ウェイの参照回数２２４にゼロより大きい値が設定されていれば（ステップＳ９１３）、共有キャッシュ２００をスルーする。すなわち、アンキャッシュの経路を用いて、メインメモリ３００へデータおよび参照回数を退避する（ステップＳ９１５、Ｓ９１６）。また、ミスヒットが検出された場合において、全てのウェイが使用中であって（ステップＳ９１１）、かつ、何れかのウェイの参照回数２２４にゼロが設定されていれば（ステップＳ９１３）、そのキャッシュラインを置換する（ステップＳ９１４）。キャッシュライン置換後の動作は、キャッシュライン追加時の動作と同様である（ステップＳ９１７乃至Ｓ９１９）。
【００６１】
図９は、本発明の第１の実施の形態における共有キャッシュ２００のリード時の処理手順を示す図である。
【００６２】
タグ制御部２３０における比較の結果、ミスヒットが検出されると（ステップＳ９２１）、キャッシュラインが確保され（ステップＳ９２２）、そのキャッシュラインのバリッド２２２に「１」が設定される（ステップＳ９２３）。このとき、ダーティ２２３に「０」が設定され、メインメモリ３００の参照回数記憶領域３２０に退避されていた参照回数が参照回数２２４に設定される（ステップＳ９２３）。そして、データ記憶部２４０にはメインメモリ３００のＦＩＦＯ記憶領域３１０からデータがフィルされる（ステップＳ９２４）。その後、そのキャッシュラインのデータ記憶部２４０からデータが読み出される（ステップＳ９２５）。
【００６３】
タグ制御部２３０における比較の結果、キャッシュヒットが検出されると（ステップＳ９２１）、そのキャッシュラインのデータ記憶部２４０からデータが読み出される（ステップＳ９２６）。このとき、そのキャッシュラインの参照回数２２４の値が「１」であれば（ステップＳ９２７）、バリッド２２２が「０」に設定され、無効化される（ステップＳ９２８）。参照回数２２４の値が「２」以上であれば（ステップＳ９２７）、参照回数２２４の値は「１」減算（デクリメント）される（ステップＳ９２９）。なお、参照回数２２４の値が「０」であれば（ステップＳ９２７）、参照回数２２４の値は変化しない。
【００６４】
図１０は、本発明の第１の実施の形態におけるプロセッサ間のデータ受け渡しシーケンスの第１の例を示す図である。この例は、共有キャッシュ２００に十分な容量が備わっている場合の例である。
【００６５】
プロセッサ１００−１がライトデータおよび参照回数を含むライトリクエストを発行すると（ステップＳ９５０）、共有キャッシュ２００はキャッシュラインを確保してそのエントリにライトデータおよび参照回数を書き込む（ステップＳ９５１）。
【００６６】
その後、プロセッサ１００−２がリードリクエストを発行すると（ステップＳ９５２）、共有キャッシュ２００はタグ制御部２３０において比較を行い（ステップＳ９５３）、キャッシュヒットするとプロセッサ１００−２にデータを出力する（ステップＳ９５４）。このとき、参照回数２２４の値が「２」以上であると仮定して、「１」が減算される（ステップＳ９５５）。
【００６７】
プロセッサ１００−２が何回目かのリードリクエストを発行した際（ステップＳ９５６）、キャッシュヒットして（ステップＳ９５７）、プロセッサ１００−２にデータが出力される（ステップＳ９５８）。このとき、参照回数２２４の値が「１」であったと仮定すると、そのキャッシュラインはライトバックされることなく無効化される（ステップＳ９５９）。
【００６８】
図１１は、本発明の第１の実施の形態におけるプロセッサ間のデータ受け渡しシーケンスの第２の例を示す図である。この例は、共有キャッシュ２００の容量を超えたサイズのデータを受け渡す場合の例である。
【００６９】
プロセッサ１００−１がライトリクエストを発行した際（ステップＳ９６０）、共有キャッシュ２００にキャッシュラインを確保できずにスルーされ（ステップＳ９６１）、メインメモリ３００にデータおよび参照回数が退避されたと仮定する（ステップＳ９６２）。
【００７０】
その後、プロセッサ１００−２によって他のデータに関するリードリクエストが発行され（ステップＳ９６３）、キャッシュヒットして（ステップＳ９６４）、プロセッサ１００−２にデータが出力される（ステップＳ９６５）。このとき、参照回数２２４の値が「１」であったと仮定すると、そのキャッシュラインはライトバックされることなく無効化される（ステップＳ９６６）。
【００７１】
その次に、退避されていたデータに関するリードリクエストがプロセッサ１００−２によって発行されると（ステップＳ９６７）、ミスヒットとなり、共有キャッシュ２００からメインメモリ３００にフィル要求が発行される（ステップＳ９６８）。メインメモリ３００に退避されていたデータおよび参照回数が共有キャッシュ２００に出力されると（ステップＳ９６９）、共有キャッシュ２００はキャッシュラインのエントリに書き込む（ステップＳ９７０）。これにより、退避されていたデータの共有キャッシュ２００からの読み出しが可能となり、プロセッサ１００−２にデータが出力される（ステップＳ９７１）。
【００７２】
このような仕組みを利用すれば、読出し側からのアクセスによってキャッシュミスを発生させることにより、その都度、共有キャッシュ２００にデータをフィルすることができる。しかしながら、リードアクセスを待ってデータフィルを起動していたのでは高速な動作を行えなくなるおそれがある。そこで、以下では、メインメモリ３００から共有キャッシュ２００へのプリフェッチを実現するための構成例について説明する。
【００７３】
［共有キャッシュ２００へのプリフェッチ］
図１２は、本発明の第１の実施の形態による情報処理システムにおいてプリフェッチ機能を設けた構成例を示す図である。この構成例では、プロセッサ１００−１乃至ｐと共有キャッシュ２００との間にプリフェッチ制御部４００が接続されている。このプリフェッチ制御部４００は、プロセッサ１００からのリードアクセスに先行して、共有キャッシュ２００にリードリクエストを発行し、プリフェッチを行わせるものである。すなわち、このプリフェッチは、メインメモリ３００から共有キャッシュ２００へのデータ転送を促すものである。
【００７４】
図１３は、本発明の第１の実施の形態におけるプリフェッチ制御部４００の一構成例を示す図である。このプリフェッチ制御部４００は、プリフェッチアドレスレジスタ４１０と、ＦＩＦＯ容量レジスタ４２０と、共有キャッシュ容量カウンタ４３０と、メインメモリ容量カウンタ４４０と、バスインターフェース４５０と、制御部４９０とを備えている。
【００７５】
プリフェッチアドレスレジスタ４１０は、共有キャッシュ２００に対してリードリクエストを発行するためのプリフェッチアドレスを保持するレジスタである。このプリフェッチアドレスレジスタ４１０の値は、逐次更新されて、次のプリフェッチに備えるよう制御される。
【００７６】
ＦＩＦＯ容量レジスタ４２０は、共有ＦＩＦＯとして使用される共有キャッシュ２００およびメインメモリ３００の容量の総和を保持するレジスタである。共有キャッシュ容量カウンタ４３０は、共有キャッシュ２００に格納されているデータサイズを保持するカウンタである。メインメモリ容量カウンタ４４０は、メインメモリ３００に格納されている受け渡し対象データのサイズを保持するカウンタである。
【００７７】
バスインターフェース４５０は、共有キャッシュ２００側のシステムバス１９０に対するバスインターフェースである。制御部４９０は、プリフェッチ制御部４００の全体の制御を司るものである。
【００７８】
共有キャッシュ２００をＦＩＦＯ用途で使用し、プロセッサ１００−１からプロセッサ１００−２にデータを受け渡そうとする場合、まずＦＩＦＯとして扱う容量をＦＩＦＯ容量レジスタ４２０に設定する。次に、プロセッサ１００−１が最初のデータを転送すべくデータのライトを行う。このとき、プロセッサ１００−１からのライトアドレスに、増加する共有キャッシュ容量カウンタ４３０の値を加えたものがプリフェッチアドレスレジスタ４１０に格納される。このプリフェッチアドレスレジスタ４１０の値がプリフェッチ要求を出す可能性のあるアドレスを意味する。
【００７９】
それ以降は、プロセッサ１００−１からのライトによる共有キャッシュ容量カウンタ４３０の増加分だけプリフェッチアドレスレジスタ４１０を加算していく。そして、後述のプリフェッチ発生条件を満たした際にプリフェッチアドレスレジスタ４１０に保持されているアドレスに対してプリフェッチ要求が発行される。ＦＩＦＯ用途として一連のデータ送受信が終了すると、ＦＩＦＯ容量レジスタ４２０を設定し直し、または、クリアする。これをトリガとしてプリフェッチアドレスレジスタ４１０もクリアされる。
【００８０】
図１４は、本発明の第１の実施の形態におけるプリフェッチ制御部４００の状態遷移の一例を示す図である。プリフェッチ制御部４００は、エンプティ状態１０、Ｌ２限定状態２１、Ｌ２フル／メイン退避状態２２、Ｌ２ノンフル／メイン退避状態２３、フル状態３０の５つの状態のうちの何れかになる。なお、この図において、共有キャッシュ容量カウンタ４３０の値をｃｎｔ、メインメモリ容量カウンタ４４０の値をｅｘｃｎｔ、ＦＩＦＯ容量レジスタ４２０の値をｓｉｚｅ、共有キャッシュ２００の総容量をＬ２ｓｉｚｅと表記する。また、各データの参照回数は１回とする。
【００８１】
エンプティ状態１０は、受け渡し対象となるデータが共有キャッシュ２００およびメインメモリ３００の何れにも格納されていない状態である。すなわち、ｃｎｔ＝０、かつ、ｅｘｃｎｔ＝０である。
【００８２】
Ｌ２限定状態２１は、共有キャッシュ２００のみに受け渡し対象となるデータが格納されている状態である。すなわち、ｃｎｔ≠０、かつ、ｅｘｃｎｔ＝０である。
【００８３】
Ｌ２フル／メイン退避状態２２は、共有キャッシュ２００の全てに受け渡し対象となるデータが格納されており（全ウェイの参照回数２２４の値が全て「１」以上）、さらにメインメモリ３００にも格納されている状態である。すなわち、ｃｎｔ＝Ｌ２ｓｉｚｅ、かつ、ｅｘｃｎｔ≠０である。
【００８４】
Ｌ２ノンフル／メイン退避状態２３は、共有キャッシュ２００に参照回数２２４の値が「０」のキャッシュラインがあるが、受け渡し対象となるデータがメインメモリ３００にも格納されている状態である。すなわち、ｃｎｔ≠Ｌ２ｓｉｚｅ、かつ、ｅｘｃｎｔ≠０である。
【００８５】
フル状態３０は、受け渡し対象となるデータが共有ＦＩＦＯとして使用される容量に達してしまった状態である。すなわち、ｃｎｔ＋ｅｘｃｎｔ＝ｓｉｚｅである。
【００８６】
このような５つ状態間で、以下のような遷移が行われる。なお、ここでは、プロセッサ１００−１からプロセッサ１００−２にデータが受け渡されることを想定する。
【００８７】
まず、エンプティ状態１０においてプロセッサ１００−１が受け渡し対象となるデータを共有キャッシュ２００にライトすると、共有キャッシュ容量カウンタ４３０が「１」加算（インクリメント）され、Ｌ２限定状態２１へ遷移する。共有キャッシュ容量カウンタ４３０の加算および状態遷移のタイミングは、プリフェッチ制御部４００と共有キャッシュ２００との間におけるトランザクション完了時である。また、以下の説明においても、共有キャッシュ容量カウンタ４３０およびメインメモリ容量カウンタ４４０の更新および状態遷移のタイミングは、プリフェッチ制御部４００と共有キャッシュ２００との間におけるトランザクション完了時である。
【００８８】
Ｌ２限定状態２１において、プロセッサ１００−２が共有キャッシュ２００からリードを行うと、共有キャッシュ容量カウンタ４３０が「１」減算（デクリメント）される。その際に共有キャッシュ容量カウンタ４３０の値が「１」から「０」に減算されたのであれば、エンプティ状態１０に遷移する。Ｌ２限定状態２１において、プロセッサ１００−１が共有キャッシュ２００にライトを行うと、共有キャッシュ容量カウンタ４３０が「１」加算（インクリメント）される。その際に共有キャッシュ容量カウンタ４３０の値がＬ２ｓｉｚｅに達し、さらにライト動作のみがされると、メインメモリ容量カウンタ４４０が「０」から「１」に加算され、Ｌ２フル／メイン退避状態２２に遷移する。その際、データは共有キャッシュ２００ではなく、メインメモリ３００に直接格納される。
【００８９】
Ｌ２フル／メイン退避状態２２において、プロセッサ１００−２が共有キャッシュ２００からリードを行うと、共有キャッシュ容量カウンタ４３０が「１」減算（デクリメント）され、Ｌ２ノンフル／メイン退避状態２３に遷移する。このときのリードデータは、共有キャッシュ２００に格納されているデータであり、上述のように参照回数は１回を想定しているため、リード後のキャッシュラインは無効化される。Ｌ２フル／メイン退避状態２２において、プロセッサ１００−１がライトを行う際にはメインメモリ３００に直接ライトが行われ、メインメモリ容量カウンタ４４０が「１」加算（インクリメント）される。その際ｃｎｔ＋ｅｘｃｎｔ＝ｓｉｚｅ−１であれば、フル状態３０に遷移する。
【００９０】
フル状態３０においては、ライト動作のみの場合はブロックされ、状態遷移も生じない。フル状態３０において、プロセッサ１００−２が共有キャッシュ２００からリードを行うと、共有キャッシュ容量カウンタ４３０が「１」減算（デクリメント）され、Ｌ２ノンフル／メイン退避状態２３に遷移する。また、フル状態３０において、共有キャッシュ２００には受け渡し対象となるデータが格納されず、全てがメインメモリ３００に格納されている場合が生じ得る。この場合、メインメモリ３００から共有キャッシュ２００にプリフェッチが行われ、共有キャッシュ容量カウンタ４３０が「１」加算され、メインメモリ容量カウンタ４４０が「０」から「１」に減算され、Ｌ２ノンフル／メイン退避状態２３に状態が遷移する。
【００９１】
Ｌ２ノンフル／メイン退避状態２３において、プロセッサ１００−１がライトを行い、その際ｃｎｔ＋ｅｘｃｎｔ＝ｓｉｚｅ−１であれば、フル状態３０に遷移する。Ｌ２ノンフル／メイン退避状態２３では、プリフェッチ制御部４００から共有キャッシュ２００に対して自動的にプリフェッチ要求が発行される。その後、共有キャッシュ２００からのプリフェッチ完了通知を受けると、共有キャッシュ容量カウンタ４３０は「１」加算（インクリメント）され、メインメモリ容量カウンタ４４０は「１」減算（デクリメント）される。また、プロセッサ１００−１がライトを行った際には、メインメモリ容量カウンタ４４０が「１」加算（インクリメント）され、メインメモリへ直接データを格納する。プロセッサ１００−２が共有キャッシュ２００からリードを行った際には、共有キャッシュ容量カウンタ４３０は「１」減算（デクリメント）される。ただし、リードを行う際に共有キャッシュ容量カウンタ４３０の値が「０」のときは、プリフェッチの完了を待つ。プリフェッチ動作後、メインメモリ容量カウンタ４４０の値が「０」となった場合には、Ｌ２限定状態２１に遷移する。
【００９２】
このように、５つの状態による状態遷移において、Ｌ２ノンフル／メイン退避状態２３にあるとき、または、フル状態３０であってかつ受け渡し対象となるデータが全てメインメモリ３００に格納されているとき、プリフェッチ発生条件を満たす。そして、プリフェッチが行われることにより、メインメモリ３００から共有キャッシュ２００にデータがフィルされる。
【００９３】
［ＦＩＦＯ記憶領域の指定］
上述の、キャッシュ容量を超えるサイズのデータ受け渡しを実現する他の手法として、ＦＩＦＯ記憶領域の指定について説明する。この手法では、参照回数は１回であることが前提となる。
【００９４】
図１５は、本発明の第１の実施の形態におけるメインメモリ３００とＦＩＦＯ記憶領域３１０の関係の第２の例を示す図である。この例では、共有キャッシュ２００内にＦＩＦＯ用途として使用される記憶領域を指定するため、先頭アドレスを保持する先頭アドレスレジスタ５２１と、サイズを保持するサイズレジスタ５２２とを備える。なお、先頭アドレスレジスタ５２１およびサイズレジスタ５２２は、特許請求の範囲に記載の領域指定レジスタの一例である。
【００９５】
タグ制御部２３０における比較の結果、全てのウェイにおいて参照回数２２４に「０」以外の値が設定されている場合、アンキャッシュ経路を用いてメインメモリ３００へデータが直接格納される。第１の例ではその際に参照回数も退避していたが、この第２の例では参照回数をメインメモリ３００に退避する必要はない。
【００９６】
この第２の例では、プロセッサからのリード要求によって、メインメモリ３００から共有キャッシュ２００へデータフィルが発生した場合、そのアドレスが指定された記憶領域内にあれば、データフィルの際に参照回数２２４を「１」に設定する。通常のＦＩＦＯでは一度読み出したデータは不要であり、参照回数が１回であることは問題なく、さらにメインメモリ３００へ参照回数を退避する必要がなくなり、その分ＬＳＩ上の面積を削減することができる。
【００９７】
この第２の例では、ライト時の処理手順は図８により説明したものと同様であるため説明を省略し、リード時の処理手順について以下に説明する。
【００９８】
図１６は、本発明の第１の実施の形態においてＦＩＦＯ記憶領域の指定を行った際の共有キャッシュ２００のリード時の処理手順を示す図である。
【００９９】
タグ制御部２３０における比較の結果、キャッシュヒットが検出された際（ステップＳ９３１）の動作は、図９により説明した処理手順（ステップＳ９２６乃至Ｓ９２９）と同様である（ステップＳ９３６乃至Ｓ９３９）。
【０１００】
また、ミスヒットが検出された際（ステップＳ９３１）の動作も、図９により説明した処理手順（ステップＳ９２２乃至Ｓ９２５）とほぼ同様である（ステップＳ９３２乃至Ｓ９３５）。ただし、この例では、ステップＳ９３３において参照回数２２４が「１」に設定される点が異なる。これにより、参照回数記憶領域３２０に参照回数を退避することを不要にすることができる。
【０１０１】
［第１の実施の形態の効果］
このように、本発明の第１の実施の形態によれば、リードアクセスの度にタグ記憶部２２０の参照回数２２４を減算し、「１」から「０」に変化した際にキャッシュラインを無効化することができる。これにより、キャッシュメモリをプロセッサ間の共有ＦＩＦＯとして動作させることが可能となる。
【０１０２】
＜２．第２の実施の形態＞
上述の第１の実施の形態では、タグ記憶部２２０内に参照回数２２４フィールドを設けたが、この第２の実施の形態ではデータ記憶部２４０内に参照回数を記憶する。前提とする情報処理システムおよび共有キャッシュの構成は図１乃至図４により説明した第１の実施の形態と同様であるため、ここでは説明を省略する。
【０１０３】
［タグ記憶部２２０の構成］
図１７は、本発明の第２の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。タグ記憶部２２０の各エントリは、タグアドレス２２１、バリッド２２２、ダーティ２２３、および、寿命付き２２５の各フィールドを備える。タグアドレス２２１、バリッド２２２およびダーティ２２３については、図５により説明した第１の実施の形態のフィールドと同様であるため、ここでは説明を省略する。
【０１０４】
寿命付き２２５は、そのエントリに対応するキャッシュラインが寿命付きであるか否かを示す寿命付きフラグ（Ｔｉｍｅ  ｌｉｍｉｔｅｄ）を記憶するものである。図中では、この寿命付き２２５を「Ｔ」と略している。この寿命付き２２５が寿命付きである旨を示しているキャッシュラインのデータ記憶部２４０には、後述するように参照回数が記憶される。
【０１０５】
なお、このタグ記憶部２２０の各フィールドの値は、キャッシュミス発生に伴うキャッシュミスへの対処処理時に設定され、その後の処理過程において適宜更新される。
【０１０６】
［データ記憶部２４０の構成］
図１８は、本発明の第２の実施の形態におけるデータ記憶部２４０のフィールド構成例を示す図である。上述のように、データ記憶部２４０は、それぞれ１２８個のキャッシュラインから成る２つのウェイ＃０および＃１を備え、それぞれ６４バイトのラインデータを保持している。６４バイトのラインデータのうち上位１バイトは参照回数２４２であり、下位６３バイトがデータ２４１である。なお、この１バイトと６３バイトの割り当ては一例であり、適宜変更してもよい。
【０１０７】
参照回数２４２は、そのエントリに対応するキャッシュラインが参照されるべき残り参照回数（Ｒｅｆｅｒｅｎｃｅ  Ｎｕｍｂｅｒ）を記憶するものであり、この例では「０」から「２５５」の整数値が格納される。図中では、この参照回数２４２を「ＲＮ」と略している。この参照回数２４２は、対応するキャッシュラインの寿命付き２２５が「１」を示しているときのみ有効である。寿命付き２２５が「０」を示しているときには、参照回数２４２は特別な意味を有するものではなく、６４バイトのラインデータ全体がデータとして取り扱われる。すなわち、寿命付き２２５の値に応じて、キャッシュラインとして２種類の何れかの構成を有する。
【０１０８】
この参照回数２４２は、受け渡し対象となるデータがデータ２４１としてキャッシュラインにライトされた際に、同時に設定される。この参照回数２４２が「２」以上を示している場合にリードアクセスが行われた際には、参照回数２２４に記憶される値から「１」減算（デクリメント）される。そして、参照回数２２４が「１」を示している場合にリードアクセスが行われた際には、そのリードアクセスの後にそのキャッシュラインは無効化される。その際、メインメモリ３００へのライトバックは行われない。
【０１０９】
［共有キャッシュ２００の動作］
本発明の第２の実施の形態では、共有キャッシュ２００の動作について、タグ制御部２３０とデータ制御部２５０に分けて説明する。
【０１１０】
図１９は、本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュラインライト時の処理手順を示す図である。
【０１１１】
タグ制御部２３０は、プロセッサ１００からキャッシュラインライトの要求を受信すると（ステップＳ８１１）、それに含まれるキャッシュラインのアドレスに基づいてタグ記憶部２２０を読み出して、キャッシュヒットまたはミスヒットの判定を行う。なお、このキャッシュラインライトの要求には、キャッシュラインのアドレスと種類の指定が含まれる。
【０１１２】
キャッシュヒットであれば（ステップＳ８１２）、タグ制御部２３０は、タグ記憶部２２０に格納されているヒットしたキャッシュラインのタグ情報を更新する（ステップＳ８１６）。更新されるキャッシュラインにおいて、バリッド２２２は「１」に設定される。そして、タグ制御部２３０は、ヒットしたキャッシュラインのデータ記憶部２４０における格納位置をデータ制御部２５０に通知して、キャッシュラインライトを指示する（ステップＳ８１８）。
【０１１３】
キャッシュミスであれば（ステップＳ８１２）、タグ制御部２３０は、ミスしたキャッシュラインをデータ記憶部２４０に追加可能であるか否かを判断する。
【０１１４】
ミスしたキャッシュラインのデータ記憶部２４０への追加が可能であれば（ステップＳ８１３）、タグ制御部２３０は、ミスしたキャッシュラインのタグ情報をタグ記憶部２２０に追加する（ステップＳ８１５）。追加されるキャッシュラインにおいて、バリッド２２２は「１」に設定され、ダーティ２２３は「１」に設定される。また、寿命付き２２５はキャッシュラインの要求に含まれる種類に応じて、寿命付きであれば「１」に、寿命付きでなければ「０」に設定される。そして、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０における格納位置をデータ制御部２５０に通知して、キャッシュラインライトを指示する（ステップＳ８１８）。
【０１１５】
ミスしたキャッシュラインのデータ記憶部２４０への追加が不可能であれば（ステップＳ８１３）、キャッシュラインの置換処理を行うことによりキャッシュラインの追加領域を確保する（ステップＳ８１４）。そして、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０における格納位置をデータ制御部２５０に通知して、キャッシュラインライトを指示する（ステップＳ８１８）。
【０１１６】
図２０は、本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュラインリード時の処理手順を示す図である。
【０１１７】
タグ制御部２３０は、プロセッサ１００からキャッシュラインリードの要求を受信すると（ステップＳ８２１）、それに含まれるキャッシュラインのアドレスに基づいてタグ記憶部２２０を読み出して、キャッシュヒットまたはミスヒットの判定を行う。このキャッシュラインリードの要求には、キャッシュラインのアドレスと種類の指定が含まれる。タグアドレス２２１が一致し、バリッド２２２が「１」であり、寿命付き２２５が要求に含まれる種類と合致していればキャッシュヒットと判定され、それ以外であればキャッシュミスと判定される。
【０１１８】
キャッシュヒットであれば（ステップＳ８２２）、タグ制御部２３０は、ヒットしたキャッシュラインのデータ記憶部２４０における格納位置と、キャッシュラインの種類と、キャッシュラインの供給先とをデータ制御部２５０に通知する。これにより、キャッシュラインリードを要求する（ステップＳ８２８）。
【０１１９】
キャッシュミスであれば（ステップＳ８２２）、タグ制御部２３０は、ミスしたキャッシュラインをデータ記憶部２４０に追加可能であるか否かを判断する。
【０１２０】
ミスしたキャッシュラインの追加が可能であれば（ステップＳ８２３）、タグ制御部２３０は、ミスしたキャッシュラインのタグ情報をタグ記憶部２２０に追加する（ステップＳ８２５）。追加されるキャッシュラインにおいて、タグアドレス２２１にはミスしたキャッシュラインのアドレスから算出されるタグが格納される。バリッド２２２は「１」に設定され、ダーティ２２３は「０」に設定される。また、寿命付き２２５はキャッシュラインの要求に含まれる種類に応じて、寿命付きであれば「１」に、寿命付きでなければ「０」に設定される。その後、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０での格納先位置と、メインメモリ３００におけるアドレスとをデータ制御部２５０に通知し、キャッシュラインフェッチを要求する（ステップＳ８２７）。そして、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０における格納位置と、キャッシュラインの種類と、キャッシュラインの供給先とをデータ制御部２５０に通知して、キャッシュラインリードを要求する（ステップＳ８２８）。
【０１２１】
ミスしたキャッシュラインの追加が不可能であれば（ステップＳ８２３）、タグ制御部２３０は、キャッシュラインの置換処理の実行によりキャッシュラインの追加領域を確保する（ステップＳ８２４）。そして、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０での格納先位置と、メインメモリ３００におけるアドレスとをデータ制御部２５０に通知し、キャッシュラインフェッチを要求する（ステップＳ８２７）。そして、タグ制御部２３０は、ミスしたキャッシュラインのデータ記憶部２４０における格納位置と、キャッシュラインの種類と、キャッシュラインの供給先とをデータ制御部２５０に通知して、キャッシュラインリードを要求する（ステップＳ８２８）。
【０１２２】
図２１は、本発明の第２の実施の形態におけるタグ制御部２３０のキャッシュライン置換時の処理手順を示す図である。この処理は、図１９におけるステップＳ８１４または図２０におけるステップＳ８２４に相当するものである。
【０１２３】
タグ制御部２３０は、キャッシュミスによりキャッシュラインを追加する必要が発生したとき、データ記憶部２４０にキャッシュラインを追加可能であるか否かを判断する。このとき、追加不可能であれば、現在保持している何れかのキャッシュラインを選択して、そのキャッシュラインをメインメモリ３００に書き戻すことにより空き領域を確保して、そこに新たなキャッシュラインを格納する。これがキャッシュラインの置換処理である。
【０１２４】
タグ制御部２３０は、キャッシュラインの置き換えが必要になると、タグ記憶部２２０のタグ情報を参照して、メインメモリ３００へ書き戻すキャッシュラインを選択する（ステップＳ８３１）。このキャッシュラインの選択には、上述のように、最も近い時期に使用されていないキャッシュラインを追い出す手法（ＬＲＵ法）を用いることができる。
【０１２５】
次に、タグ制御部２３０は、選択したキャッシュラインのタグ記憶部２２０における格納位置と、キャッシュラインの種類と、キャッシュラインのメインメモリ３００への書き戻し先アドレスとをデータ制御部２５０に通知する。これにより、キャッシュラインライトバックを要求する（ステップＳ８３２）。
【０１２６】
そして、タグ制御部２３０は、選択したキャッシュラインのタグ情報を、ミスしたキャッシュラインのタグ情報に置き換える（ステップＳ８３３）。置換後のタグ情報において、タグアドレス２２１にはミスしたキャッシュラインのアドレスから算出されるタグが格納される。バリッド２２２は「１」に設定される。ダーティ２２３には、キャッシュミスがライトアクセスによるものであれば「１」が、リードアクセスによるものであれば「０」が格納される。また、寿命付き２２５はキャッシュラインの要求に含まれる種類に応じて、寿命付きであれば「１」に、寿命付きでなければ「０」に設定される。
【０１２７】
図２２は、本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインリード時の処理手順を示す図である。
【０１２８】
データ制御部２５０は、タグ制御部２３０からキャッシュラインリードの指示を受信すると（ステップＳ８４１）、タグ制御部２３０から指定されたデータ記憶部２４０における位置のキャッシュラインを読み出す（ステップＳ８４２）。タグ制御部２３０のリード指示の対象が寿命付きキャッシュラインであれば（ステップＳ８４３）、データ制御部２５０は、読み出した参照回数２４２の値を「１」減算して（ステップＳ８４４）、データ記憶部２４０に書き戻す（ステップＳ８４５）。そして、データ制御部２５０は、この寿命付きキャッシュラインをプロセッサ１００側に出力する（ステップＳ８４６）。タグ制御部２３０のリード指示の対象が通常のキャッシュラインであれば（ステップＳ８４３）、データ制御部２５０はタグ制御部２３０から指定されたデータ記憶部２４０における位置から読み出したキャッシュラインを出力する（ステップＳ８４６）。
【０１２９】
図２３は、本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインライトバック時の処理手順を示す図である。
【０１３０】
データ制御部２５０は、タグ制御部２３０からキャッシュラインライトバック指示を受信すると（ステップＳ８５１）、タグ制御部２３０から指定されたデータ記憶部２４０における位置のキャッシュラインを読み出す（ステップＳ８５２）。タグ制御部２３０のライトバック指示の対象が寿命付きキャッシュラインであれば（ステップＳ８５３）、データ制御部２５０はデータ記憶部２４０から読み出した参照回数２４２の値を確認する。そして、参照回数２４２の値がゼロであればキャッシュラインライトバック処理を一旦終了する（ステップＳ８５４）。参照回数２４２の値がゼロでなければ（ステップＳ８５４）、データ制御部２５０はこの寿命キャッシュラインとタグ制御部２３０から指定されたアドレスとをメインメモリ３００側へ出力する（ステップＳ８５５）。これにより、メインメモリ３００の指定されたアドレスへこの寿命付きキャッシュラインが書き込まれる。
【０１３１】
図２４は、本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインフェッチ時の処理手順を示す図である。
【０１３２】
データ制御部２５０は、タグ制御部２３０からキャッシュラインフェッチ指示を受信すると（ステップＳ８６１）、タグ制御部２３０から指定されたアドレスをメインメモリ３００側に出力する。これにより、指定されたアドレスからのキャッシュラインサイズ分のデータをメインメモリ３００から読み出すよう要求する（ステップＳ８６２）。
【０１３３】
要求したキャッシュラインの転送が開始されると、データ制御部２５０は、転送されるキャッシュラインを受信し（ステップＳ８６３）、受信したキャッシュラインをタグ制御部２３０から指定されたデータ記憶部２４０における位置に書き込む（ステップＳ８６４）。
【０１３４】
図２５は、本発明の第２の実施の形態におけるデータ制御部２５０のキャッシュラインライト時の処理手順を示す図である。
【０１３５】
データ制御部２５０は、タグ制御部２３０からキャッシュラインライト指示を受信すると（ステップＳ８７１）、プロセッサ１００の一次キャッシュ１１０側からキャッシュラインを受信する（ステップＳ８７２）。そして、データ制御部２５０は、受信したキャッシュラインを、タグ制御部２３０から指定されたデータ記憶部２４０における位置に書き込む（ステップＳ８７３）。
【０１３６】
図２６は、本発明の第２の実施の形態における共有キャッシュ２００へのデータライトシーケンスの例を示す図である。
【０１３７】
プロセッサ１００−１は、一次キャッシュ１１０−１のキャッシュラインにおいて、上位１バイトに参照回数として１回を表す「１」をライトし、下位６３バイトにプロセッサ１００−２に対して受け渡すデータをライトする（ステップＳ８８１）。そして、一次キャッシュ１１０−１に、この作業領域を寿命付きキャッシュラインとして共有キャッシュ２００にライトするよう指示する（ステップＳ８８２）。
【０１３８】
一次キャッシュ１１０−１は、共有キャッシュ２００に対して、キャッシュラインの種類として寿命付きキャッシュラインを指定して、キャッシュラインのライトを要求する（ステップＳ８８３）。共有キャッシュ２００は、ライト要求を受信すると（ステップＳ８８４）、キャッシュヒットまたはミスヒットの判定と、必要に応じてキャッシュラインの置き換えとを実行する（ステップＳ８８５）。そして、寿命付きキャッシュラインを受信して、受信した寿命付きキャッシュラインをデータ記憶部２４０に格納する（ステップＳ８８６）。
【０１３９】
一次キャッシュ１１０−１は、寿命付きキャッシュラインの送信が完了すると（ステップＳ８８７）、プロセッサ１００−１に寿命付きキャッシュラインのライト完了を報告する（ステップＳ８８８）。プロセッサ１００−１がこの報告を受信することによりライト処理は終了する（ステップＳ８８９）。
【０１４０】
図２７は、本発明の第２の実施の形態における共有キャッシュ２００からのデータリードシーケンスの例を示す図である。
プロセッサ１００−２は、プロセッサ１００−１がライトしたデータを参照するために、一次キャッシュ１１０−２に対してキャッシュラインをリードするよう指示する（ステップＳ８９０）。一次キャッシュ１１０−２は、共有キャッシュ２００に対して、キャッシュラインの種類として寿命付きキャッシュラインを指定して、キャッシュラインのリードを要求する（ステップＳ８９１）。
【０１４１】
共有キャッシュ２００は、一次キャッシュ１１０−２からのリード要求を受信すると（ステップＳ８９２）、キャッシュヒットまたはミスヒットの判定を行う（ステップＳ８９３）。そして、ヒットした寿命付きキャッシュラインをデータ記憶部２４０から読み出して、参照回数２４２の値を「１」減算するとともに（ステップＳ８９４）、その寿命付きキャッシュラインを一次キャッシュ１１０−２に送信する（ステップＳ８９５）。
【０１４２】
一次キャッシュ１１０−２は、寿命付きキャッシュラインの受信が完了すると（ステップＳ８９６）、プロセッサ１００−２に寿命付きキャッシュラインのリード完了を報告する（ステップＳ８９７）。プロセッサ１００−２は、一次キャッシュ１１０−２から寿命付きキャッシュラインのリード完了報告を受信すると（ステップＳ８９８）、共有データのリード処理を開始する（ステップＳ８９９）。
【０１４３】
ステップＳ８９４において、参照回数２４２がゼロとなった寿命付きキャッシュラインは、今後参照されることのない不要なキャッシュラインであり、将来的にはタグ制御部２３０によって置換対象キャッシュラインとして選択される。ただし、本発明の実施の形態によれば、参照回数２４２の値がゼロになったことにより、データ制御部２５０によってメインメモリ３００へはライトバックされず、そのまま破棄される。
【０１４４】
［変形例］
この第２の実施の形態においても、上述の第１の実施の形態において説明した、キャッシュ容量を超えるサイズのデータ受け渡し、プリフェッチ、ＦＩＦＯ記憶領域の指定といった変形例を適宜適用することができる。
【０１４５】
［第２の実施の形態の効果］
このように、本発明の第２の実施の形態によれば、リードアクセスの度にデータ記憶部２４０の参照回数２４２を減算し、「１」から「０」に変化した際にキャッシュラインを無効化することができる。これにより、キャッシュメモリをプロセッサ間の共有ＦＩＦＯとして動作させることが可能となる。
【０１４６】
＜３．第３の実施の形態＞
上述の第１の実施の形態では、タグ記憶部２２０内に参照回数２２４フィールドを設けたが、この第３の実施の形態ではタグ記憶部２２０内に利用可能量およびロックビットを記憶する。前提とする情報処理システムおよび共有キャッシュの構成は図１乃至図４により説明した第１の実施の形態と同様であるため、ここでは説明を省略する。
【０１４７】
［タグ記憶部２２０の構成］
図２８は、本発明の第３の実施の形態におけるタグ記憶部２２０のフィールド構成例を示す図である。タグ記憶部２２０の各エントリは、タグアドレス２２１、バリッド２２２、ダーティ２２３、ロック２２６、および、利用可能量２２７の各フィールドを備える。タグアドレス２２１、バリッド２２２およびダーティ２２３については、図５により説明した第１の実施の形態のフィールドと同様であるため、ここでは説明を省略する。
【０１４８】
ロック２２６は、そのエントリが置換対象とならないようにロックをかけるためのロックビットを記憶するものである。このロック２２６があるプロセッサによってロック状態（例えば「１」）に設定された場合、そのエントリは無関係な他のプロセッサからのアクセスによっては置換されない。すなわち、ライト側プロセッサが新規のキャッシュラインを必要とする際にロック２２６をロック状態とし、リード側プロセッサにおいてそのキャッシュラインが不要になった際にロック２２６をアンロック状態とする。図中では、このロック２２６を「Ｌ」と略している。
【０１４９】
利用可能量２２７は、そのエントリのデータ記憶部２４０において利用可能なデータの量（Ｕｓａｂｌｅ  ａｍｏｕｎｔ）を記憶するものである。データ量の単位としては、統一されていれば任意の単位を使用できるが、例えばバイトやブロック（４バイトまたは８バイト）を単位とすることができる。１バイトを単位とする場合には、この利用可能量２２７で６４バイト分を表現するために、６ビット幅を割り当てる必要がある。図中では、この利用可能量２２７を「Ｕ」と略している。
【０１５０】
なお、利用可能量２２７は、ロック２２６と併用することなく単独で使用可能であるが、ロック２２６と併用することにより、後述の遅延機構を有効に利用することができるようになる。
【０１５１】
［共有キャッシュ２００の動作］
図２９は、本発明の第３の実施の形態における共有キャッシュ２００のライト時の処理手順を示す図である。
【０１５２】
タグ制御部２３０における比較の結果、キャッシュヒットが検出されると（ステップＳ７１０）、そのキャッシュラインにデータをライトする余裕があるか否かが判断される（ステップＳ７１８）。具体的には、ラインサイズ（６４バイト）から利用可能量２２７を減算した値がライトデータ量に足りない場合には、ライト動作は待機される。一方、ラインサイズから利用可能量２２７を減算した値がライトデータ量以上であれば、ライトデータがデータ記憶部２４０に書き込まれる（ステップＳ７１９）。その際、利用可能量２２７にはそのライトデータ量が加算される（ステップＳ７２０）。
【０１５３】
一方、ミスヒットが検出された場合（ステップＳ７１０）、未使用となっているウェイが存在すれば（ステップＳ７１１）、キャッシュラインが追加され（ステップＳ７１２）、そのキャッシュラインのバリッド２２２に「１」が設定される（ステップＳ７１７）。以降の動作はキャッシュヒット時と同様である（ステップＳ７１８乃至Ｓ７２０）。
【０１５４】
ミスヒットが検出された場合（ステップＳ７１０）、以下のように処理される。全てのウェイが使用中であって（ステップＳ７１１）、かつ、全ウェイのロック２２６がロックされているか利用可能量２２７にゼロより大きい値が設定されていれば（ステップＳ７１３）、共有キャッシュ２００をスルーする。すなわち、アンキャッシュの経路を用いて、メインメモリ３００へデータおよびライトデータ量を退避する（ステップＳ７１５、Ｓ７１６）。メインメモリ３００上の退避領域は、図７により説明した第１の実施の形態と同様であり、ＦＩＦＯ記憶領域３１０の他に、（図示しない）ライトデータ量の記憶領域が確保される。全てのウェイが使用中であって、かつ、何れかのウェイのロック２２６がアンロックされているか利用可能量２２７にゼロより大きい値が設定されていないキャッシュラインがあれば（ステップＳ７１３）、そのキャッシュラインを置換する（ステップＳ７１４）。キャッシュライン置換後の動作は、キャッシュライン追加時の動作と同様である（ステップＳ７１７乃至Ｓ７２０）。
【０１５５】
図３０は、本発明の第３の実施の形態における共有キャッシュ２００のリード時の処理手順を示す図である。
【０１５６】
タグ制御部２３０における比較の結果、キャッシュヒットが検出されると（ステップＳ７２１）、そのキャッシュラインからデータをリード可能であるか否かが判断される（ステップＳ７２５）。具体的には、利用可能量２２７の値がリードデータ量に足りない場合には、リード動作は待機される。一方、利用可能量２２７の値がリードデータ量以上であれば、そのキャッシュラインのデータ記憶部２４０からリードデータが読み出される（ステップＳ９２６）。その際、利用可能量２２７からそのリードデータ量が減算され（ステップＳ７２７）、ロック２２６が「０」にアンロックされる（ステップＳ７２８）。
【０１５７】
タグ制御部２３０における比較の結果、ミスヒットが検出されると（ステップＳ７２１）、キャッシュラインが確保され（ステップＳ７２２）、そのキャッシュラインのバリッド２２２に「１」が設定される（ステップＳ７２３）。このとき、ダーティ２２３に「０」が設定され、ロック２２６が「１」（ロック）に設定され、退避されていたライトデータ量が利用可能量２２７に設定される（ステップＳ７２３）。そして、データ記憶部２４０にはメインメモリ３００のＦＩＦＯ記憶領域からデータがフィルされる（ステップＳ７２４）。以降の動作はキャッシュヒット時と同様である（ステップＳ７２５乃至Ｓ７２８）。
【０１５８】
［遅延更新機構］
図３１は、本発明の第３の実施の形態における利用可能量２２７の遅延設定機構の態様を示す図である。新規にキャッシュラインが必要となって割り当てを行う際に、利用可能量２２７の更新タイミングをＮライン分遅らせる機構を追加することを想定する。このような機構を、利用可能量２２７の遅延設定機構と称する。この遅延設定機構により、最終ライト位置からＮライン以内のデータが再書込み可能になる。この図では、２ライン分の遅延を想定した例を示している。
【０１５９】
この遅延設定機構を実現するために、ライトラインポインタレジスタ５８１、および、複数のライトデータ量レジスタ５８２が設けられる。ライトラインポインタレジスタ５８１は、現在ライトアクセスを行っているキャッシュラインがどこまで進んでいるかを記憶するレジスタである。ライトデータ量レジスタ５８２は、遅延対象となったキャッシュラインの利用可能量２２７を確定する際に、それまでのライトデータ量を記憶するレジスタである。
【０１６０】
この図では、ライトラインポインタレジスタ５８１が第５番目のキャッシュラインを指し示しており、第３番目のキャッシュラインの利用可能量２２７が確定したことを表している。第５番目のキャッシュラインをライトした直後は、第４番目および第５番目のキャッシュラインの利用可能量２２７には設定がされていないため、対応するキャッシュラインは再書込み可能である。第４番目および第５番目のキャッシュラインの利用可能量２２７に設定すべきライトデータ量は、ライトデータ量レジスタ５８２に記憶されており、ライトラインポインタレジスタ５８１の変化に合わせて参照されていく。
【０１６１】
図３２は、本発明の第３の実施の形態におけるロック２２６の遅延解除機構の態様を示す図である。リードされたキャッシュラインが不要になりアンロックする際に、そのアンロックのタイミングをＮライン分遅らせる機構を追加することを想定する。このような機構を、ロック２２６の遅延解除機構と称する。この遅延解除機構により、最終リード位置からＮライン以内のデータが再読出し可能になる。この図では、２ライン分の遅延を想定した例を示している。
【０１６２】
この遅延解除機構を実現するために、リードラインポインタレジスタ５９１が設けられる。このリードラインポインタレジスタ５９１は、現在リードアクセスを行っているキャッシュラインがどこまで進んでいるかを記憶するレジスタである。
【０１６３】
この図では、リードラインポインタレジスタ５９１が第５番目のキャッシュラインを指し示しており、第３番目のキャッシュラインのロック２２６のアンロック状態が確定したことを表している。第５番目のキャッシュラインをリードした直後は、第４番目および第５番目のロック２２６はロック状態が解除されていないため、対応するキャッシュラインは再読出し可能である。
【０１６４】
図３３は、本発明の第３の実施の形態における遅延更新機構を利用したデータ順序入れ換えの一例を示す図である。それぞれ実行される命令と、仮想的なＦＩＦＯの状態とを組にして示している。仮想的なＦＩＦＯの実体は共有キャッシュ２００に記憶される。ここでは、８つのキャッシュラインに相当するＦＩＦＯを示している。
【０１６５】
図３３（ａ）はライト側プロセッサにより実行される命令と実行直後の状態を示している。ライト側プロセッサがＦＩＦＯに対して左から順次ライトを行っているものとする。その過程において、データＤ２のキャッシュラインをライトした直後に、一つ前のキャッシュラインに戻ってデータＤ１をライトした様子を示している。通常は、データＤ１をライトしようとしても、利用可能量２２７が確定しているとリード側プロセッサがリードするまでデータをライトできなくなってしまうが、利用可能量２２７の設定を遅延することによりデータＤ１のライトが可能になる。
【０１６６】
図３３（ｂ）はリード側プロセッサにより実行される命令と実行直後の状態を示している。リード側プロセッサでは、ＦＩＦＯに対して左から順次リードを行っている。その結果、データＤ１を先にリードし、次にデータＤ２をリードすることができる。すなわち、ライト側プロセッサのライト順序とは異なり、データＤ１とＤ２とを入れ換えてリードすることが可能となる。これにより、ライト側プロセッサまたはリード側プロセッサにおいてメモリに保存してデータを入れ換えるコストを削減することができる。
【０１６７】
図３４は、本発明の第３の実施の形態における遅延更新機構を利用したデータサイズ圧縮の一例を示す図である。それぞれ実行される命令と、仮想的なＦＩＦＯの状態とを組にして示している。仮想的なＦＩＦＯの実体は共有キャッシュ２００に記憶される。ここでは、キャッシュラインにおける８バイト分に相当するＦＩＦＯを示している。
【０１６８】
図３４（ａ）は遅延更新機構を利用しない場合のライト側プロセッサにより実行される命令と実行直後の状態を示している。まず、１バイトデータＤ１がＦＩＦＯの第０バイト目にライトされる。次に、２バイトデータＤ２がＦＩＦＯの第２乃至３バイト目にライトされる。このとき、利用可能量２２７がキャッシュライン内の最終位置を記憶するものとすると、次の１バイトデータＤ３は第４バイト目にライトされることになる。
【０１６９】
図３４（ｂ）は遅延更新機構を利用した場合のライト側プロセッサにより実行される命令と実行直後の状態を示している。この場合、データＤ１およびＤ２がライトされた際に利用可能量２２７が確定していないため、１バイトデータＤ３は第１バイト目にライトすることが可能となる。このように、複数のデータサイズが混在している場合であってもＦＩＦＯ内の空き領域を利用することができる。これにより、データアラインメントのための未使用領域を削減することができる。
【０１７０】
なお、ここでは、利用可能量２２７の遅延設定機構を利用してライト側プロセッサにおけるライト順序の入れ換えを行う例について説明したが、同様の手法によりロック２２６の遅延解除機構を利用してリード順序の入れ換えを行うことも可能である。
【０１７１】
［遅延更新機構のコーデックへの適用例］
以下では、ここまでに説明した遅延更新機構をコーデックのアルゴリズムに適用して最適化を行う適用例について説明する。
【０１７２】
図３５は、一般的なコーデックにおけるＩＤＣＴ（Inverse Discrete Cosine Transform：逆離散コサイン変換）係数デコード処理アルゴリズムを示す図である。この原アルゴリズムでは、ビットストリームから８画素×８画素ブロックのＩＤＣＴ係数を取得し、取得したＩＤＣＴ係数を図３６のようにジグザグスキャンして、１次元の係数列としてＦＩＦＯに出力している。このような手法は、ＭＰＥＧ（Moving Picture Experts Group）やＪＰＥＧ（Joint Photographic Experts Group）においても利用されている。
【０１７３】
図３７は、従来手法により最適化されたコーデックのＩＤＣＴ係数デコード処理アルゴリズムを示す図である。このアルゴリズムでは、ジグザグスキャンをＩＤＣＴ係数デコードと同時に実行することにより、最適化を行っている。ただし、この手法を採用した場合、ジグザグスキャン後の係数列をＦＩＦＯに出力する際に順序を入れ換える必要があり、中間結果を保持するバッファＱＦを設ける必要が生じる。
【０１７４】
図３８は、本発明の第３の実施の形態における遅延更新機構を利用したコーデックのＩＤＣＴ係数デコード処理アルゴリズムを示す図である。このアルゴリズムでは、ジグザグスキャンをＩＤＣＴ係数デコードと同時に実行し、中間結果を保持するバッファを設けることなくＦＩＦＯに出力している。すなわち、初期化データを一旦ＦＩＦＯに出力した後に、非ゼロ係数のみを再度ＦＩＦＯに書き込むことができることから、中間結果を保持するバッファを省くことが可能となっている。
【０１７５】
ＩＤＣＴ係数は、１２８バイト（８画素×８画素×２バイト）であり、キャッシュラインサイズが６４バイトの場合、２ライン分を使用する。本発明の第３の実施の形態による遅延更新機構によれば、２ライン内における任意の場所に複数回ライトすることができるため、アルゴリズムの最適化を柔軟に行うことができる。
【０１７６】
［キャッシュ容量を超えるサイズのデータ受け渡し］
この第３の実施の形態においても、共有キャッシュ２００の容量を越えるサイズのデータをプロセッサ１００間で転送することが可能である。すなわち、第１の実施の形態の場合と同様に、共有キャッシュ２００を使用しないアンキャッシュ経路と、データ制御部２５０において以下のような制御機能とを追加することが有用である。
【０１７７】
例えば、プロセッサ１００−１がデータを共有キャッシュ２００にライトすることを想定する。ライトされたデータの量がある一定量を越えた段階で、タグ制御部２３０においてライトアクセスに対するタグ一致検出の結果、全てのウェイにおいて利用可能量２２７およびロック２２６が既に設定されている事象が発生する。この場合、共有キャッシュ２００をスルーし、アンキャッシュの経路を用いてメインメモリ３００へデータを直接格納する。このとき、ライトデータに付随してライトデータ量もメインメモリ３００へ退避する。
【０１７８】
その後、例えば、プロセッサ１００−２が共有キャッシュ２００からデータを読み出し、メインメモリ３００から共有キャッシュ２００へデータがフィルされる。このとき、退避されていたライトデータ量も利用可能量２２７に設定される。これにより、プロセッサ１００−２からのリードアクセスが可能となる。
【０１７９】
このとき、遅延更新機構が利用されている場合、アンキャッシュの経路が用いられるようになった際には、更新が遅延されていた利用可能量２２７およびロック２２６を確定する必要がある。すなわち、利用可能量２２７の遅延設定機構では、後からライト動作が行われないと利用可能量２２７が確定せず、同様に、ロック２２６の遅延解除機構では、後からリード動作が行われないとロック２２６が確定しないことになる。したがって、キャッシュ容量を超えた際だけでなく、通常のアクセスにおいても最後のＮライン分は強制的に利用可能量２２７およびロック２２６を確定させる必要がある。そのため、以下のようなフラッシュ機能を設ける。
【０１８０】
［フラッシュ機能］
遅延更新機構を備える共有キャッシュ２００においては、利用可能量２２７およびロック２２６を確定させるためのフラッシュ機能を設ける。ライト動作に関してフラッシュの指示があった場合、ライトデータ量レジスタ５８２に保持されたライトデータ量を利用可能量２２７に設定して確定させるとともに、未確定となっていたロック２２６をロック状態に確定させる。リード動作に関してフラッシュの指示があった場合、全ての利用可能量２２７を「０」に設定するとともに、全てのロック２２６をアンロックに設定して、キャッシュラインを解放する。
【０１８１】
［変形例］
この第３の実施の形態においても、上述の第１の実施の形態において説明した、プリフェッチ、ＦＩＦＯ記憶領域の指定といった変形例を適宜適用することができる。
【０１８２】
［第３の実施の形態の効果］
このように、本発明の第３の実施の形態によれば、利用可能量２２７に対して、ライトアクセスの度に加算し、リードアクセスの度に減算することにより、共有ＦＩＦＯとして動作させた際のデータの追い越しを防止することができる。また、ライトアクセスの際にロック２２６をロック状態にして、リードアクセスの際にアンロック状態にすることにより、第三者によるキャッシュラインの追い出しを防止することができる。また、これら利用可能量２２７およびロック２２６について遅延更新機構を設けることにより、共有ＦＩＦＯとして利用する際にデータを入れ換えることが可能となる。
【０１８３】
＜４．応用例＞
上述のように、本発明の実施の形態によれば、キャッシュメモリ上に共有ＦＩＦＯを実現することができる。そこで、次に共用ＦＩＦＯを利用した応用例として、デジタルテレビ放送システムについて説明する。
【０１８４】
図３９は、本発明の実施の形態の応用例としてのデジタルテレビ放送システムの一例を示す図である。このデジタルテレビ放送システムでは、送信機６０１から受信機６０３に対して、チャネル６０２を介してデジタルテレビ放送信号が伝送される。送信機６０１は、トランスポートストリームのストリームデータを送信する。受信機６０３は、送信機６０１から送信されたトランスポートストリームのストリームデータを受信する。
【０１８５】
ここで、このデジタルテレビ放送システムは、伝送トランスポートストリームパケットに対して、バイトインターリーブを行うこと想定する。インターリーブの深さは１２バイトとし、同期バイトの次のバイトは遅延の無い基準パスを通過するものとする。このバイトインターリーブを実現するために、送信機６０１はインターリーバ６１０を備え、受信機６０３はデインターリーバ６３０を備えるものとする。
【０１８６】
なお、デジタルテレビ放送ではチャネル６０２に相当する部分において様々な処理が行われるが、ここでは説明の便宜上、簡略化している。
【０１８７】
図４０は、本発明の実施の形態の応用例におけるインターリーバ６１０の一構成例を示す図である。このインターリーバ６１０は、１２個のパス＃０乃至＃１１を有しており、何れかのパスを通過するようにスイッチ６１１および６１３が同時に切り替わるようになっている。バイトインターリーバ６１０においては、１バイト毎に異なるパスを通過するように切り替えられる。すなわち、パス＃０から順に、パス＃１、パス＃２と切り替わり、パス＃１１の次は再びパス＃０に切り替わる。
【０１８８】
このインターリーバ６１０では、１２個のパス＃０乃至＃１１のうちパス＃１乃至＃１１において、ＦＩＦＯ６１２−１乃至１１を備えている。ＦＩＦＯ６１２−１乃至１１はバイト単位のシフトレジスタであり、それぞれ異なる長さを有している。例えば、パス＃１上のＦＩＦＯ６１２−１は１７バイト長、パス＃２上のＦＩＦＯ６１２−２は３４（＝１７×２）バイト長、パス＃３上のＦＩＦＯ６１２−３は５１（＝１７×３）バイト長を有している。
【０１８９】
図４１は、本発明の実施の形態の応用例におけるデインターリーバ６３０の一構成例を示す図である。このデインターリーバ６３０は、インターリーバ６１０と同様に、１２個のパス＃０乃至＃１１を有しており、何れかのパスを通過するようにスイッチ６３１および６３３が同時に切り替わるようになっている。デバイトインターリーバ６３０においては、インターリーバ６１０と同様に、１バイト毎に異なるパスを通過するように切り替えられる。すなわち、パス＃０から順に、パス＃１、パス＃２と切り替わり、パス＃１１の次は再びパス＃０に切り替わる。
【０１９０】
このデインターリーバ６３０では、１２個のパス＃０乃至＃１１のうちパス＃０乃至＃１０において、ＦＩＦＯ６３２−０乃至１０を備えている。ＦＩＦＯ６３２−０乃至１０はバイト単位のシフトレジスタであり、それぞれ異なる長さを有している。例えば、パス＃０上のＦＩＦＯ６３２−０は１８７（＝１７×１１）バイト長、パス＃１上のＦＩＦＯ６３２−１は１７０（＝１７×１０）バイト長、パス＃２上のＦＩＦＯ６３２−２は１５３（＝１７×９）バイト長を有している。
【０１９１】
これらインターリーバ６１０およびデインターリーバ６３０におけるＦＩＦＯ６１２および６３２には、ダミーのデータが満たされているものとして処理が行われる。したがって、処理の最初の段階では、ダミーデータを押し出すための処理が必要になる。
【０１９２】
インターリーバ６１０とデインターリーバ６３０とを比較すると分かるように、両者のパスにおけるＦＩＦＯの長さは対になるように設定されており、何れのパスも両者を合わせると１８７バイト分の長さを有するように構成されている。したがって、インターリーバ６１０の入力とデインターリーバ６３０の出力とでは、データの並びが一致するようになっている。その一方で、チャネル６０２上ではデータの並びが散らばることにより、バーストエラーが生じた場合でも、受信機６０３における誤り訂正符号による誤り訂正にとって都合のよい状態となる。
【０１９３】
なお、このようなＦＩＦＯによる並び替えは、デジタルテレビ放送においては他に時間インターリーブなどの畳込みインターリーブに適用することができる。
【０１９４】
これらインターリーバ６１０およびデインターリーバ６３０におけるＦＩＦＯ６１２および６３２を、上述の本発明の実施の形態における共有ＦＩＦＯとして実現することが可能である。ＦＩＦＯ６１２および６３２は、必ずしも全てをキャッシュメモリ上に格納する必要はないため、処理の状況に応じてキャッシュメモリを利用することができる。すなわち、ＦＩＦＯ以外の用途で用いられているキャッシュラインが多い場合にはメインメモリへの退避が行われ、逆の場合にはキャッシュライン上にＦＩＦＯのデータが乗り切った状態が維持される。したがって、少ないキャッシュ容量によって効率良く処理を行うことができる。
【０１９５】
＜５．変形例＞
以上、本発明の実施の形態について説明したが、本発明はこれらの実施の形態に限定されるものではない。例えば、本発明の実施の形態においては、共有キャッシュ２００のキャッシュラインサイズを６４バイトと想定したが、本発明はこれに限定されるものではない。また、本発明の実施の形態においては、共有キャッシュ２００と一次キャッシュ１１０のキャッシュラインサイズを同じ６４バイトと想定したが、本発明はこれに限定されるものではなく、異なるキャッシュラインサイズの組合せであってもよい。
【０１９６】
また、本発明の実施の形態においては、共有キャッシュ２００をライトバック方式のキャッシュメモリと想定したが、本発明はこれに限定されるものではなく、ライトスルー方式など他の方式であってもよい。
【０１９７】
また、本発明の実施の形態においては、一次キャッシュ１１０と共有キャッシュ２００との間のデータ転送は、キャッシュラインサイズ単位で行うことを想定したが、本発明はこれに限定されるものではなく、任意のサイズによる転送を行えるようにしてもよい。
【０１９８】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１９９】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０２００】
１０  エンプティ状態
２１  Ｌ２限定状態
２２  Ｌ２フル／メイン退避状態
２３  Ｌ２ノンフル／メイン退避状態
３０  フル状態
１００  プロセッサ
１１０  一次キャッシュ
１９０  システムバス
２００  共有キャッシュ（二次キャッシュ）
２１０  調停部
２２０  タグ記憶部
２３０  タグ制御部
２３１、２３２  比較器
２３３  論理和演算器
２４０  データ記憶部
２５０  データ制御部
２５１、２５２  選択器
２６０  応答部
３００  メインメモリ
３１０  ＦＩＦＯ記憶領域
３２０  参照回数記憶領域
４００  プリフェッチ制御部
４１０  プリフェッチアドレスレジスタ
４２０  ＦＩＦＯ容量レジスタ
４３０  共有キャッシュ容量カウンタ
４４０  メインメモリ容量カウンタ
４５０  バスインターフェース
４９０  制御部
５１１、５１３  比較器
５１２  減算器
５２１  先頭アドレスレジスタ
５２２  サイズレジスタ
５８１  ライトラインポインタレジスタ
５８２  ライトデータ量レジスタ
５９１  リードラインポインタレジスタ
６０１  送信機
６０２  チャネル
６０３  受信機
６１０  インターリーバ
６３０  デインターリーバ
【図１】
2011150684.tif 000003
【図２】
2011150684.tif 000004
【図３】
2011150684.tif 000005
【図４】
2011150684.tif 000006
【図５】
2011150684.tif 000007
【図６】
2011150684.tif 000008
【図７】
2011150684.tif 000009
【図８】
2011150684.tif 000010
【図９】
2011150684.tif 000011
【図１０】
2011150684.tif 000012
【図１１】
2011150684.tif 000013
【図１２】
2011150684.tif 000014
【図１３】
2011150684.tif 000015
【図１４】
2011150684.tif 000016
【図１５】
2011150684.tif 000017
【図１６】
2011150684.tif 000018
【図１７】
2011150684.tif 000019
【図１８】
2011150684.tif 000020
【図１９】
2011150684.tif 000021
【図２０】
2011150684.tif 000022
【図２１】
2011150684.tif 000023
【図２２】
2011150684.tif 000024
【図２３】
2011150684.tif 000025
【図２４】
2011150684.tif 000026
【図２５】
2011150684.tif 000027
【図２６】
2011150684.tif 000028
【図２７】
2011150684.tif 000029
【図２８】
2011150684.tif 000030
【図２９】
2011150684.tif 000031
【図３０】
2011150684.tif 000032
【図３１】
2011150684.tif 000033
【図３２】
2011150684.tif 000034
【図３３】
2011150684.tif 000035
【図３４】
2011150684.tif 000036
【図３５】
2011150684.tif 000037
【図３６】
2011150684.tif 000038
【図３７】
2011150684.tif 000039
【図３８】
2011150684.tif 000040
【図３９】
2011150684.tif 000041
【図４０】
2011150684.tif 000042
【図４１】
2011150684.tif 000043