(57)【要約】【課題】マルチプロセッサシステムにあって装置構成を大きくすることがなく、あるいは消費電力を高めることがなく、プロセッサ間でデータのコヒーレンシを動作効率よく保つことができ、さらにプロセッサによるアクセス効率が高いキャッシュメモリを提供する。【解決手段】複数のプロセッサによってデータがキャッシュされ、キャッシュされたデータをプロセッサに読み出すと共にプロセッサからデータを書き出すキャッシュメモリを、キャッシュされたデータを保存するデータメモリ４０４、保存されているデータを、読み出したプロセッサごとに管理するタグメモリ及び入出力制御部４０１で構成する。そして、プロセッサ１によってアクセスされたデータがプロセッサ２に対応して管理されている場合、入出力制御部４０１は、アクセスされたデータをプロセッサ１に供給する。【選択図】図４
2007156963.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサによって記憶装置から読み出されたデータの少なくとも一部をキャッシュしておき、キャッシュされたデータを前記プロセッサに読み出すと共に前記プロセッサからデータを書き出すデータ授受手段を備えたキャッシュメモリであって、
複数のプロセッサによってキャッシュされたデータを保存するデータ保存手段と、
前記データ保存手段に保存されているデータを、該データを前記記憶装置から読み出したプロセッサごとに管理するデータ管理手段と、を備え、
第１のプロセッサによって供給を要求されたデータが前記データ管理手段において第２のプロセッサに対応して管理されている場合、前記データ授受手段は、供給を要求された第２のプロセッサに対応して管理されているデータを前記第１のプロセッサに供給することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項２】
前記データ管理手段は、プロセッサに対応して管理されているデータを前記データ保存手段に保存する保存優先度を、当該データに対する読出しの要求の状態に基づいて決定することを特徴とする請求項１に記載のキャッシュメモリ。
【請求項３】
前記データ管理手段は、前記データ保存手段のアドレスを複数のウェイとして管理すると共に、前記データ保存手段に保存されているデータの保存優先度を前記ウェイごとに決定することを特徴とする請求項１または２に記載のキャッシュメモリ。
【請求項４】
前記データ管理手段は、第２のプロセッサに対応して管理されているデータが第１のプロセッサによって読み出し及び書き込みされた場合、第２のプロセッサに対応して管理されているデータの保存優先度を変更することを特徴とする請求項１から３のいずれか１項に記載のキャッシュメモリ。
【請求項５】
前記データ管理手段は、第２のプロセッサに対応して管理されているデータが第１のプロセッサによって読み出し及び書き込みされた場合、第２のプロセッサに対応して管理されているデータの保存優先度を保存することを特徴とする請求項１から３のいずれか１項に記載のキャッシュメモリ。
【請求項６】
前記データ保存手段が、キャッシュされたデータを、データを読み出したプロセッサごとに保存する複数のデータメモリであって、前記データ管理手段は、複数の前記データメモリの各々とシングルポートによって接続されることを特徴とする請求項１から５のいずれか１項に記載のキャッシュメモリ。
【請求項７】
記憶装置から読み出されたデータの少なくとも一部をキャッシュしておき、キャッシュされたデータを前記プロセッサに読み出すと共に前記プロセッサからデータを書き出すデータ授受手段を備えたキャッシュメモリと接続するマルチプロセッサシステムであって、
前記キャッシュメモリが、
複数のプロセッサによってキャッシュされたデータを保存するデータ保存手段と、
前記データ保存手段に保存されているデータの書出し優先度を、当該データに対するプロセッサの供給要求の状態に基づいてプロセッサごとに決定するデータ管理手段と、を備え、
第１のプロセッサによって供給を要求されたデータが前記データ管理手段において第２のプロセッサに対応して管理されている場合、供給を要求されたデータを前記供給手段が前記第１のプロセッサに供給し、前記データ管理手段は、前記第２のプロセッサに対応して管理されているデータを前記データ保存手段に保存する保存優先度を決定することを特徴とするマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュメモリ及びマルチプロセッサシステムに係り、特にマルチプロセッサ等の複数の処理を並列に実行するマルチプロセッサシステムに用いられるキャッシュメモリ及びこのようなキャッシュメモリを使って動作するマルチプロセッサシステムに関する。
【背景技術】
【０００２】
近年、複数のスレッドやタスク（実施形態１ではスレッドに統一して記す）を並列に実行するマルチプロセッサ（マルチコア）、あるいはマルチスレッドプロセッサが注目されている。このようなプロセッサは、総称してマルチプロセッサシステムとも呼ばれる。マルチプロセッサシステムでは、データ等が蓄積されている外部メモリへのアクセスを効率化するため、外部メモリからいったん読み出されたデータのうちの処理に使用される可能性のあるデータを保存しておくキャッシュメモリを備えるマルチプロセッサシステムがある。このような構成の従来技術として、例えば、特許文献１が掲げられる。
【０００３】
また、特許文献１に示したようなキャッシュメモリを備えたマルチプロセッサでは、複数のプロセッサ間で処理に使用されるデータの一致性（コヒーレンシ）を保つことが必要である。従来のプロセッサでは、データのコヒーレンシを保つためにバス・スヌープが多く採用されている。バス・スヌープとは、各プロセッサ間で共有されるメモリインターフェイスバス上のトランザクションを観察し、自身に割り当てられているキャッシュメモリ上にあるデータに係るトランザクションが発生したか否かを検出する機能である。
【０００４】
自身に割り当てられたキャッシュメモリ上にあるデータのトランザクションが発生した場合、プロセッサは、キャッシュメモリの該当するエントリを更新し、マルチプロセッサシステムにおける各プロセッサのキャッシュメモリ領域等に保存されているデータの内容を統一する。バス・スヌープには多くの実装法があり、例えばライトワンスやバークレイプロトコルがある。
【特許文献１】特開２００４−１７８５７１
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記した特許文献１の発明は、キャッシュメモリの記憶領域をスレッドごとの独立の領域に分割し、マルチプロセッサシステムで同時に実行されるスレッドごとに割り当てている。このような特許文献１によれば、キャッシュメモリに必要とされるデータが保存されていて、このデータに対するアクセスの成功（ヒット）の割合（ヒット率）が低下するという不具合がある。
【０００６】
また、特許文献１に記した構成でバス・スヌープの機能を用いコヒーレンシを保持する場合、バスをモニタする回路によってマルチプロセッサシステムのハードウェア構成が大規模化する。また、バスを常時モニタするために消費電力が高まり、キャッシュメモリの独立した各領域に各々アクセスしてデータを書き換えるため、コヒーレンシ保持の動作効率が低いという課題が生じる。
【０００７】
さらに、マルチプロセッサシステムにおいて、プロセッサごとにキャッシュメモリを独立して設ける構成ものがある。このような構成は、複数のデータプログラムを１つのプロセッサに取り込む場合のキャッシュメモリへのアクセス効率を充分高めることができない。
本発明は、上記した点に鑑みてなされたものであって、マルチプロセッサシステムにあって装置構成を大きくすることがなく、あるいは消費電力を高めることがなく、プロセッサ間でデータのコヒーレンシを動作効率よく保つことができ、さらにプロセッサによるアクセス効率が高いキャッシュメモリ及びこのキャッシュメモリを備えたマルチプロセッサシステムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
以上の課題を解決するため、本発明のキャッシュメモリは、複数のプロセッサによって記憶装置から読み出されたデータの少なくとも一部をキャッシュしておき、キャッシュされたデータを前記プロセッサに読み出すと共に前記プロセッサからデータを書き出すデータ授受手段を備えたキャッシュメモリであって、複数のプロセッサによってキャッシュされたデータを保存するデータ保存手段と、前記データ保存手段に保存されているデータを、該データを前記記憶装置から読み出したプロセッサごとに管理するデータ管理手段と、を備え、第１のプロセッサによって供給を要求されたデータが前記データ管理手段において第２のプロセッサに対応して管理されている場合、前記データ授受手段は、供給を要求された第２のプロセッサに対応して管理されているデータを前記第１のプロセッサに供給することを特徴とする。
【０００９】
このような発明によれば、複数のプロセッサによってキャッシュされたデータを保存しておき、第１のプロセッサによって供給を要求されたデータが第２のプロセッサに対応して管理されている場合、供給を要求されたデータを前記第１のプロセッサに供給することができる。
このため、複数のプロセッサのいずれかに対応して管理されているデータを、どのプロセッサにも供給することが可能となり、スヌープを用いることなくプロセッサ間でデータのコヒーレンシを保つことができる。スヌープを用いないことから、マルチプロセッサシステムにあって装置構成を大きくすることがなく、あるいは消費電力を高めることがなく、プロセッサ間でデータのコヒーレンシを一致させることが可能になる。
【００１０】
また、複数のプロセッサのいずれもが他のプロセッサに対応してキャッシュされているデータの提供を受けることができるので、キャッシュメモリのプロセッサによるアクセス効率を高めることができる。
また、本発明のキャッシュメモリは、前記データ管理手段は、プロセッサに対応して管理されているデータを前記データ保存手段に保存する保存優先度を、当該データに対する読出しの要求の状態に基づいて決定することを特徴とする。
【００１１】
このような発明によれば、他のプロセッサによるデータ要求をも考慮してデータの保存優先度を決定することができるので、プロセッサの要求に応じて必要なデータをキャッシュメモリから書き出さず、キャッシュしておくことができる。このような構成によれば、キャッシュメモリのプロセッサによるアクセス効率をいっそう高めることができる。
また、本発明のキャッシュメモリは、前記データ管理手段が、前記データ保存手段のアドレスを複数のウェイとして管理すると共に、前記データ保存手段に保存されているデータの保存優先度を前記ウェイごとに決定することを特徴とする。
【００１２】
このような発明によれば、キャッシュメモリが複数ウェイを持つ場合にも、より正確にデータ保存手段に保存すべきデータの優先度を決定することができる。
また、本発明のキャッシュメモリは、前記データ管理手段が、第２のプロセッサに対応して管理されているデータが第１のプロセッサによって読み出し及び書き込みされた場合、第２のプロセッサに対応して管理されているデータの保存優先度を変更することを特徴とする。
【００１３】
このような発明によれば、他のプロセッサによるデータ要求に応じて書出しの優先度が変更されるので、マルチプロセッサ等、複数のプロセッサ全体で要求される頻度の低いデータを優先して書出し、データのヒット効率を高めることができる。
また、本発明のキャッシュメモリは、前記データ管理手段が、第２のプロセッサに対応して管理されているデータが第１のプロセッサによって読み出し及び書き込みされた場合、第２のプロセッサに対応して管理されているデータの保存優先度を保存することを特徴とする。
【００１４】
このような発明によれば、他のプロセッサによるデータ要求があった場合にはデータ保存手段に保存する優先度が維持されるので、マルチプロセッサ等に含まれる各プロセッサによって要求される頻度の高いデータを優先して保存することによってプロセッサの独立性を確保し、対応するプロセッサとデータ同士のデータのヒット効率を高めることができる。
【００１５】
また、本発明のキャッシュメモリは、前記データ保存手段が、キャッシュされたデータを、データを読み出したプロセッサごとに保存する複数のデータメモリであって、前記データ管理手段は、複数の前記データメモリの各々とシングルポートによって接続されることを特徴とする。
このような発明によれば、データメモリに比較的安価なシングルポートメモリを用いることが可能になって、本発明のキャッシュメモリの製造コストを抑えることができる。
【００１６】
また、本発明のマルチプロセッサシステムは、記憶装置から読み出されたデータの少なくとも一部をキャッシュしておき、キャッシュされたデータを前記プロセッサに読み出すと共に前記プロセッサからデータを書き出すデータ授受手段を備えたキャッシュメモリと接続するマルチプロセッサシステムであって、前記キャッシュメモリが、複数のプロセッサによってキャッシュされたデータを保存するデータ保存手段と、前記データ保存手段に保存されているデータの書出し優先度を、当該データに対するプロセッサの供給要求の状態に基づいてプロセッサごとに決定するデータ管理手段と、を備え、第１のプロセッサによって供給を要求されたデータが前記データ管理手段において第２のプロセッサに対応して管理されている場合、供給を要求されたデータを前記供給手段が前記第１のプロセッサに供給し、前記データ管理手段は、前記第２のプロセッサに対応して管理されているデータを前記データ保存手段に保存する保存優先度を決定することを特徴とする。
【００１７】
このような発明によれば、複数のプロセッサのうちのいずれもが、他のプロセッサに対応して管理されているデータの供給を受けることが可能となり、スヌープを用いることなくプロセッサ間でデータのコヒーレンシを保つことができる。スヌープを用いないことから、マルチプロセッサシステムの装置構成を大きくすることがなく、あるいは消費電力を高めることがなく、プロセッサ間でデータのコヒーレンシを一致させることが可能になる。
【００１８】
また、複数のプロセッサのいずれもが他のプロセッサに対応してキャッシュされているデータの提供を受けることができるので、キャッシュメモリのプロセッサによるアクセス効率を高めることができる。
さらに、本発明のマルチプロセッサシステムは、他のプロセッサによるデータ要求をも考慮してデータの保存優先度を決定することができるので、プロセッサの要求に応じて必要なデータをキャッシュメモリから書き出さず、キャッシュしておくことができる。このような構成によれば、キャッシュメモリのプロセッサによるアクセス効率をいっそう高めることができる。
【発明を実施するための最良の形態】
【００１９】
以下、本発明のキャッシュメモリ及びこのキャッシュメモリを備えたマルチプロセッサシステムの実施形態１、実施形態２について説明する。
（実施形態１）
図１は、本発明のキャッシュメモリ１０９及びキャッシュメモリ１０９を使って動作するマルチプロセッサシステム（以下単にマルチプロセッサと記す）１０５を示した実施形態１、実施形態２に共通の図である。図示した構成は、マルチプロセッサ１０５、キャッシュメモリ１０９、メモリ１０３を有している。メモリ１０３には、マルチスレッドＯＳ１０７及びアプリケーション１０８からプログラムやデータがローダ１０６によって転送されてくるものとする。
【００２０】
キャッシュメモリ１０９は、キャッシュメモリ部１０２と、キャッシュメモリ部１０２を制御するキャッシュ制御部１０１とでなる。キャッシュメモリ部１０２には、外部メモリであるメモリ１０３よりもマルチプロセッサ１０５が高速にアクセスできる構成のメモリが採用される。
なお、キャッシュメモリの方式には種々のものがあるが、セット・アソシアティブ方式が一般的であるため、実施形態１では２ウェイ（ウェイＡ，Ｂ）のセット・アソシアティブ方式のキャッシュメモリを例に挙げて説明する。なお、セット・アソシアティブ方式とは、キャッシュメモリを複数の領域（ウェイ）に分割し、それぞれのウェイに、メモリデバイス上の異なるアドレスのデータを格納しておくことにより、ヒット率を向上させることができる方式である。
【００２１】
マルチプロセッサ１０５は、複数のプロセッサを結合して構成されるマルチプロセッサシステムの１つである。マルチプロセッサシステムのプロセッサの結合の例を図２（ａ）、（ｂ）に示す。図２（ａ）、（ｂ）に示した構成のうち、一般的に図２（ａ）に示した構成をマルチプロセッサといい、（ｂ）に示した構成をマルチスレッドプロセッサという。図２（ａ）、（ｂ）のいずれに示した構成も、４つのプロセッサ０〜プロセッサ３が結合してメモリを共有するものである。
【００２２】
マルチスレッドプロセッサは、演算器をも結合する点でマルチプロセッサよりも結合が密であるとされている。このようなマルチスレッドプロセッサを密結合ともいい、これに対してマルチプロセッサを疎結合ともいう。
ここでは、実施形態１のプロセッサをマルチプロセッサ１０５として構成した。マルチプロセッサ１０５は、図２（ｂ）に示したように、プロセッサ０、プロセッサ１、プロセッサ２、プロセッサ３の４つのプロセッサを有している。キャッシュメモリ１０９は、マルチプロセッサ１０５の複数のプロセッサによって、メモリ１０３から読み出されたデータの少なくとも一部をキャッシュしておき、キャッシュされたデータの少なくとも一部をプロセッサに供給するキャッシュメモリである。
【００２３】
ただし、実施形態１はマルチプロセッサを用いた構成に限定されるものでなく、複数のプロセッサがメモリを共有して結合する構成であればよく、例えば、図２（ｂ）に示したマルチスレッドプロセッサとして構成することも可能である。
マルチプロセッサ１０５は、キャッシュメモリ１０９と接続し、キャッシュメモリ１０９を介してメモリ１０３からデータを読み出す。読み出されたデータは、キャッシュメモリ１０９に保存（キャッシュ）される。また、マルチプロセッサ１０５は、読み出されたデータを使って実行した演算の結果を、キャッシュメモリ１０９あるいはメモリ１０３に書込んでいる。
【００２４】
この動作により、マルチプロセッサ１０５は、メモリ１０３にアクセスすることなくキャッシュメモリ１０９にキャッシュされたデータを取得することができる。そして、前記したように、キャッシュメモリ１０９はメモリ１０３より高速にアクセスできるから、図１に示した構成は、マルチプロセッサ１０５のデータの読出し及び書込みを高速化することができる。さらに、メモリ１０３に対するアクセス回数を低減し、マルチプロセッサ１０５の処理速度及び処理効率を高めることができる。
【００２５】
さらに、実施形態１では、キャッシュメモリ１０９に対し、いわゆるＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ  ａｌｇｏｒｉｔｈｍ）方式を採用している。ＬＲＵとは、キャッシュされているデータのうち、最後にプロセッサからアクセスされたデータをメモリ１０３に書出し、書き出された領域に新たに必要なデータをキャッシュする方式をいう。このような方式によれば、常にプロセッサの要求頻度が多いデータをデータメモリ４０４にキャッシュしておくことができ、キャッシュメモリを採用した構成の処理効率を高めることができる。
【００２６】
また、マルチスレッドプロセッサＯＳ１０７によって動作するマルチプロセッサ１０５は、複数のスレッドと、スレッドの実行に使用されるプロセッサとを一対一に割り付けるものでなく、複数のプロセッサの各々が、スレッドごとに処理を実行すると共に、処理の実行中に実行されているスレッドを他のスレッドと変更し得る。このようなマルチプロセッサ１０５は、マルチスレッドＯＳによって動作するものである。このような動作を図３に例示する。図３に示した例では、いずれのプロセッサもスレッドの実行中に優先度がより高いスレッドに実行権が移り、優先度がより高いスレッドに処理を切り換えている。
【００２７】
図４は、図１に示したキャッシュメモリ１０９の構成をより詳細に示した図である。キャッシュメモリ１０９は、図１に示したように、キャッシュ制御部１０１と、キャッシュメモリ部１０２とを備えている。
キャッシュメモリ部１０２は、タグメモリ４０３とデータメモリ４０４とを有している。データメモリ４０４は、メモリ１０３から読み出されたデータがキャッシュされるメモリであって、タグメモリ４０３は、データメモリ４０４にキャッシュされたデータを取り出すための情報（タグ情報）をプロセッサ０〜３ごとに管理するメモリである。なお、図４に示した構成では、タグメモリ４０３、データメモリ４０４をマルチポートメモリとして構成した。
【００２８】
より具体的には、タグメモリ４０３は、データメモリ４０４にキャッシュされているデータに付されたアドレスを含む情報をタグ情報として保持し、プロセッサの読み出し、書込み処理に対してデータメモリ４０４、メモリ１０３へのアクセスの管理や調整を行っている。タグメモリ４０３は、タグ情報を、データをキャッシュしたプロセッサごとに管理し、アクセスするプロセッサごとにデータメモリ４０４、メモリ１０３へのアクセスを調整する。
【００２９】
実施形態１において、データメモリ４０４は、複数のプロセッサによって読み出されたデータを保存（キャッシュ）するデータ保存手段となる。また、タグメモリ４０３は、データメモリ４０４にキャッシュされているデータを、データをメモリ１０３から読み出したプロセッサごとに管理するための管理データを記憶している。
なお、実施形態１では、タグメモリ４０３が、データのアドレスの他、状態（ステータス）をも管理するためのデータを記憶しておる。ここでいうステータスとは、データのアクセス履歴、データの有効、無効やダーティ（データがメモリ１０３から読み出された後に変更されたことを意味する）であるか否か等を示す情報である。データのアクセス履歴を管理することにより、タグメモリ４０３に記憶されているデータによれば、データに対するアクセス状態を管理することができる。
【００３０】
入出力制御部４０１は、タグメモリ４０３とデータメモリ４０４とに対するアクセスを制御する。入出力制御部４０１では、タグメモリ４０３及びデータメモリ４０４へのアクセスが実際に生じるときだけ、メモリアクセスのクロックを供給するなどの方法によって消費電力を低減することも可能である。
ヒット検出部４０２は、プロセッサによって供給を要求されたデータのアドレスをタグメモリ４０３で管理されているアドレスと照合し、データメモリ４０４に対して供給を要求された有効なデータがある（ヒット）か、有効なデータがないか（ミスヒット）を検出する構成である。
【００３１】
具体的には、プロセッサ０〜３は、キャッシュメモリ１０９にアクセスしてデータを検索する際、タグメモリ４０３に制御信号を入力する。制御信号は、データメモリ４０４のライン単位のアドレスの下位の何ビットか（インデックス）を含んでいて、インデックスによってタグメモリ４０３のタグ情報が引き出される。プロセッサ０〜３が検索するアドレスからインデックスを除いた上位ビットは、タグ情報と比較される。比較の結果、両者が一致した場合、指定されたアドレスのデータがキャッシュされていることになる。一方、タグ情報と制御信号とが一致しなかった場合、プロセッサ０〜３によってメモリ１０３がアクセスされる。
【００３２】
データがキャッシュされていた場合、タグメモリ４０３は、一致したアドレスについてデータのステータスを示すステータス信号をヒット検出部４０２に出力する。ヒット検出部４０２は、ステータス信号が有効であることを示す場合、キャッシュヒットを検出する。そして、キャッシュヒットを示すキャッシュヒット信号を入出力制御部４０１に出力する。なお、キャッシュヒット信号には、ヒットしたデータのアドレス、ウェイ及びエントリを示す情報が含まれている。
【００３３】
また、ヒット検出部４０２は、タグ情報と制御信号とが一致しない、または一致した場合であっても、一致した結果得られたアドレスに保存されているデータが無効である場合にはキャッシュミスヒットを検出する。そして、キャッシュミスヒットを示すキャッシュミスヒット信号を入出力制御部４０１に出力する。
以上の構成において、データメモリ４０４は、複数のプロセッサによってキャッシュされたデータを保存するデータ保存手段となる。また、入出力制御部４０１は、タグメモリ４０３と共に、データメモリ４０４に保存されているデータをメモリ１０３から読み出したプロセッサ０〜３ごとに管理する管理手段となる。実施形態１では、入出力制御部４０１が、データメモリ４０４に保存されているデータの書出し優先度を、このデータに対するプロセッサの供給要求（アクセス）状態に基づいて決定している。
【００３４】
また、プロセッサ０〜４の１つ（第１プロセッサ）によってアクセスされたデータがデータメモリ４０４において他のプロセッサ（第２プロセッサ）に対応して管理されている場合、入出力制御部４０１は、このデータを第１プロセッサに供給すると共に、タグメモリ４０３において第２プロセッサに対応して管理されているデータの書出し優先度を更新する。入出力制御部４０１によるこのような動作は後に詳述する。
【００３５】
なお、実施形態１では、データメモリ４０４にキャッシュされたデータが、キャッシュされたプロセッサ０〜４のいずれかに対応して管理されているものとする。
次に、実施形態１のタグメモリ４０３及びデータメモリ４０４の構成を詳細に説明する。図５（ａ）、（ｂ）、（ｃ）は、タグメモリ４０３、データメモリ４０４に記憶されるデータの構造を説明するための図である。（ａ）は、タグメモリ４０３によって管理されるステータスのフラグを示している
フラグは、プロセッサ０〜３の各々ごとにタグメモリ４０３に保存されていて、実施形態１では、データのステータスをＶａｌｉｄ  ｆｌａｇ、Ｄｉｒｔｙ  ｆｌａｇ、Ｕｓｅｄ  ｆｌａｇの３つのフラグによって示している。Ｖａｌｉｄ  ｆｌａｇは、データの有効性を示すフラグである。Ｄｉｒｔｙ  ｆｌａｇは、キャッシュされているデータとメモリ１０３に保存されているデータとの不一致の状態を示し、Ｕｓｅｄ  ｆｌａｇは、書出しの優先度を示している。
【００３６】
図５（ｂ）は、タグメモリ４０３のデータ構造を説明するための図である。また、図５（ｃ）は、データメモリ４０４のデータ構造を説明するための図である。２ウェイのセット・アソシアティブ方式を採用した実施形態１では、プロセッサ０（図中Ｐ０と記す）〜プロセッサ３（図中Ｐ３と記す）の各々について、ウェイＵ０、ウェイＵ１を持っていて、タグメモリ４０３、データメモリ４０４の同じエントリに２つのデータを記憶させることができる。
【００３７】
図６（ａ）、（ｂ）は、実施形態１のＬＲＵの処理を説明するための図である。実施形態１のプロセッサは、ＬＲＵによって書き出されるデータの優先順位を図６に示したＵｓｅｄテーブルによって管理している。なお、実施形態１では、Ｕｓｅｄテーブルをタグメモリ４０３に保存し、入出力制御部４０１によって更新するものとした。
プロセッサ０〜３によって読み出されたデータは、データメモリ４０４のウェイＵ０またはウェイＵ１にキャッシュされる。ウェイＵ０、ウェイＵ１においてキャッシュ可能な数のデータがキャッシュされた後、さらに他のデータをキャッシュする必要がある場合、入出力制御部４０１は、現在ウェイＵ０またはウェイＵ１にキャッシュされているデータの１つをメモリ１０３に書き出す。そして、プロセッサが要求するデータを書き戻されたデータがキャッシュされていた領域に保存する。
【００３８】
２ウェイのキャッシュメモリを持つ実施形態１では、２ウェイセットアソシアティブの例において、ウェイＵ０とウェイＵ１において、プロセッサがアクセスした後最も長い時間が経過したものをキャッシュメモリから取り除く方法（ＬＲＵ）によりデータに対するプロセッサの供給要求の状態に基づいて決定している。
なお、実施形態１では、データに対するアクセス時間経過が長いウェイを他方に優先してデータを書き出す対象とした。
【００３９】
書出しの優先順位は、図６（ａ）、（ｂ）の表中にＬＲＵ順位としてＵｓｅｄテーブルに記録されている。実施形態１でいうＬＲＵは、０または１の数値によって表されていて、数値が０，１の順で最近アクセスされたことを示す。つまり、ＬＲＵ値０のウェイのデータが保持され、ＬＲＵ値１のウェイのデータが更新される。
また、実施形態１では、書出しの優先順位を、プロセッサごとに決定している。すなわち、入出力制御部４０１が、キャッシュされたデータと、データをキャッシュしたプロセッサとを対応付けて管理し、このプロセッサによってウェイＵ０にキャッシュされたデータ、ウェイＵ１にキャッシュされたデータの２つのデータの間のみで優先順位を決定している。このような構成は、各プロセッサが実行する処理の種別や特性に応じて頻繁にアクセスされるデータを優先的にキャッシュし、いずれのプロセッサにおけるキャッシュヒット率をも高めることができる。
【００４０】
図６（ａ）は、プロセッサ２が要求したデータがデータメモリ４０４にミスヒットした場合のＬＲＵ順位の決定について説明するための図である。プロセッサ２が要求したデータがプロセッサ２に対応して管理されるデータにないため、プロセッサ２は、メモリ１０３にアクセスしてデータを読み出し、データメモリ４０４にキャッシュする。この際、入出力制御部４０１は、Ｕｓｅｄテーブルを参照し、ウェイＵ０にキャッシュされているデータとウェイＵ１にキャッシュされているデータとのＬＲＵ順位を参照する。
【００４１】
図６（ａ）の場合、ウェイＵ１のＬＲＵ順位が０、ウェイＵ０のＬＲＵ順位が１であるから、入出力制御部４０１は、プロセッサ２のウェイＵ０がキャッシュされて最もアクセス時間が経過したと判定し、ウェイU0のデータを書出し、新たなデータをウェイU0に格納する。そして、ウェイ０のＬＲＵを０に、ウェイＵ１のＬＲＵを１にする。
また、図６（ｂ）は、プロセッサ２が要求したデータがデータメモリ４０４のプロセッサ２に対応して管理されているデータにヒットした場合のＬＲＵの決定について説明するための図である。プロセッサ２が要求したデータがプロセッサ２のウェイ１のデータにヒットした場合、プロセッサ２は、このデータを読み出してプロセッサ２に供給する。このとき、データの書出しは必要なく、ＬＲＵの値はウェイＵ１がアクセスの前後で共に最近アクセスされたデータであることを示している。
【００４２】
図７は、以上の動作を説明するためのフローチャートである。入出力制御部４０１は、プロセッサからデータアクセスの要求を受け、タグメモリ４０３に要求されたデータがヒットするか否かを検出する（Ｓ７０１）。プロセッサに対応して管理されているデータにヒットしたか否か判断し（Ｓ７０２）、ヒットが検出された場合には（Ｓ７０２：Ｙｅｓ）、アクセスがデータの書出しを要求するものか否か判断する（Ｓ７０７）。データの書出しが要求された場合（Ｓ７０７：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ７１０）。
【００４３】
また、ステップＳ７０７において、アクセスがデータの書出しを目的とするものでないと判断された場合（Ｓ７０７：Ｎｏ）、Ｗａｙ（ｎ）にキャッシュされているデータを読み出し、アクセスしたプロセッサに供給する（Ｓ７０８）。そして、入出力制御部４０１は、ＬＲＵにしたがってこのデータのアクセス履歴等を示す情報をタグメモリ４０３において更新する（Ｓ７０９）。
【００４４】
一方、ステップＳ７０２において、データがヒットしないと判断された場合（Ｓ７０２：Ｎｏ）、入出力制御部４０１は、ウェイ（Ｗａｙ（ｎ））においてアクセス後に最も長い期間使用されていないデータをＬＲＵのアルゴリズムによって検出する（Ｓ７０３）。そして、検出されたデータがダーティデータであるか否か判断する（Ｓ７０４）。データがダーティデータである場合（Ｓ７０４：Ｙｅｓ）、このデータをデータメモリ４０４から書出し（Ｓ７０５）、書き出された領域にメモリ１０３からデータを読み出す（Ｓ７０６）。その後の動作は、S７０２においてヒットした場合と同様である。
【００４５】
図８（ａ）、（ｂ）は、実施形態１のＬＲＵの処理を説明するための他の図である。図８は、プロセッサ２が供給を要求したデータが、プロセッサ３のウェイＵ１にヒットした場合の例を示していて、このような場合、入出力制御部４０１は、プロセッサ３のウェイＵ１として管理されているデータをプロセッサ２に供給する。
図８に示した例では、入出力制御部４０１が、プロセッサ３（第２のプロセッサ）に対応して管理されているデータがプロセッサ２（第１のプロセッサ）に供給された場合、プロセッサ３に対応して管理されているデータの書出し優先度を変更する。図８（ａ）はデータアクセス前のＬＲＵ順位を示し、（ｂ）は更新後のＬＲＵ順位を示している。
【００４６】
図示したように、データがヒットしたプロセッサ３のウェイＵ１では、ＬＲＵ順位が１から０に変更されている。この変更により、プロセッサ３で次回キャッシュミスヒットが発生した場合、次回ウェイＵ０のデータが書出しの対象となる。このようにした場合、データヒットがないウェイのデータがヒットがあったウェイに優先して書き出され、プロセッサに必要とされるデータを優先的にキャッシュしておくことができる。
【００４７】
また、このように、実施形態１は、マルチプロセッサに含まれるプロセッサに対応して管理されているデータをどのプロセッサからも読み出すことが可能である。このような実施形態１は、外部メモリであるメモリ１０３に対するアクセス回数が低減でき、より高速に動作することができる。また、キャッシュされているデータを複数のプロセッサで共用できるため、プロセッサ間でデータのコヒーレンシを保つことができる。
【００４８】
図９は、図８に示した処理のうち、入出力制御部４０１によってなされるキャッシュの制御を説明するためのフローチャートである。入出力制御部４０１は、プロセッサからデータアクセスの要求を受け、タグメモリ４０３に要求されたデータがヒットするか否かを検出する（Ｓ９０１）。そして、データを要求したプロセッサに対応して管理されているデータにヒットしたか否か判断し（Ｓ９０２）、ヒットが検出された場合には（Ｓ９０２：Ｙｅｓ）、アクセスがデータの書出しを要求するものか否か判断する（Ｓ９０３）。
【００４９】
なお、上記した動作において、データを要求したプロセッサ（例えばプロセッサｋ）に対応して管理されているデータが保存されているデータメモリ４０４の領域をプロセッサｋのキャッシュといい、プロセッサｋによってアクセスされるデータがプロセッサｋのキャッシュにあったことを、「自分のキャッシュにヒットした」ともいう。また、プロセッサｋによってアクセスされるデータがプロセッサｋのキャッシュになく、他のプロセッサのキャッシュあったことを、「他のキャッシュにヒットした」ともいう。
【００５０】
データの書出しが要求された場合（Ｓ９０３：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ９０４）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ９０５）。
また、ステップＳ９０３において、アクセスがデータの書出しを目的とするものでないと判断された場合（Ｓ９０３：Ｎｏ）、Ｗａｙ（ｎ）を読み出してアクセスしたプロセッサに供給する（Ｓ９０８）。そして、入出力制御部４０１は、ＬＲＵにしたがってこのデータのアクセス履歴等を示す情報をタグメモリ４０３において更新する（Ｓ９０７）。
【００５１】
一方、ステップＳ９０２において、データがヒットしないと判断された場合（Ｓ９０２：Ｎｏ）、入出力制御部４０１は、他のプロセッサにキャッシュされ、このプロセッサに対応して管理されているデータにヒットしたか否か判断する（Ｓ９０８）。ヒットが検出された場合（Ｓ９０８：Ｙｅｓ）、アクセスがデータの書出しを要求するものか否か判断する（Ｓ９０９）。
【００５２】
データの書出しが要求された場合（Ｓ９０９：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ９１０）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ９１１）。一方、アクセスがデータの書出しを目的とするものでない場合（Ｓ９０９：Ｎｏ）、Ｗａｙ（ｎ）を読み出してアクセスしたプロセッサに供給する（Ｓ９１２）。そして、入出力制御部４０１は、Ｕｓｅｄテーブルに記録されているＬＲＵ順位を示すフラグを更新する（Ｓ９１３）。
【００５３】
また、ステップＳ９０８において、他のプロセッサによってキャッシュされたデータにもヒットしなかったと判断された場合（Ｓ９０８：Ｎｏ）、Ｗａｙ（ｎ）においてアクセス回数が最も少ないデータをＬＲＵのアルゴリズムによって検出する（Ｓ９１４）。そして、検出されたデータがダーティデータであるか否か判断する（Ｓ９１５）。データがダーティデータである場合（Ｓ９１５：Ｙｅｓ）、このデータをデータメモリ４０４から書出し（Ｓ９１６）、書き出された領域にメモリ１０３からデータを読み出す（Ｓ９１７）。
【００５４】
そして、さらに、入出力制御部４０１は、アクセスがデータの書出しを要求するものか否か判断する（Ｓ９１８）。データの書出しが要求された場合（Ｓ９１８：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ９１９）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ９２０）。
また、ステップＳ９１８において、アクセスがデータの書出しを目的とするものでないと判断された場合（Ｓ９１８：Ｎｏ）、Ｗａｙ（ｎ）にキャッシュされていたデータを読み出し、アクセスしたプロセッサに供給する（Ｓ９２１）。そして、入出力制御部４０１は、ＬＲＵにしたがってこのデータのアクセス履歴等を示す情報をタグメモリ４０３において更新する（Ｓ９２２）。
【００５５】
図１０は、図８に示した処理のうち、ＵｓｅｄテーブルのＬＲＵ順位を変更するための処理を説明するためのフローチャートである。入出力制御部４０１は、プロセッサによって要求されたデータをタグメモリ４０３に照会し、要求されたデータが要求したプロセッサのキャッシュのいずれかのウェイにヒットしたか否か判断する（Ｓ１００１）。ヒットしたと判断された場合（Ｓ１００１：Ｙｅｓ）、プロセッサのヒットしたウェイのＬＲＵ順位を０に更新する（Ｓ１００２）。
【００５６】
次に、入出力制御部４０１は、変数ｓを０に設定し（Ｓ１００３）、複数のプロセッサの各ウェイのＬＲＵ順位ｓを順次ｓ+１に更新する（Ｓ１００４）。この更新は、更新後のＬＲＵ順位が、ヒットしたプロセッサのウェイのヒット直前のＬＲＵ順位に達するまで行われる（Ｓ１００５）。
一方、プロセッサｋが要求したデータが自キャッシュにヒットしないとき（Ｓ１００１：Ｎｏ）、入出力制御部４０１は、他のプロセッサのキャッシュのウェイにヒットしたか否か判断する（Ｓ１００６）。ヒットした場合（Ｓ１００６：Ｙｅｓ）、キャッシュのヒットしたウェイのＬＲＵ順を０に更新する（Ｓ１００７）。そして、変数ｓを０に設定し（Ｓ１００８）、複数のプロセッサの各ウェイのＬＲＵ順位ｓを順次ｓ+１に更新する（Ｓ１００９）。この更新は、更新後のＬＲＵ順位が、ヒットしたプロセッサのウェイのヒット直前のＬＲＵ順位に達するまで行われる（Ｓ１０１０）。
【００５７】
また、他のプロセッサのキャッシュにもヒットしなかった場合（Ｓ１００６：Ｎｏ）、自キャッシュの最もＬＲＵ順位が低いウェイのＬＲＵ順位を０に更新する（Ｓ１０１１）。そして、変数ｓを０に設定し（Ｓ１０１２）、複数のプロセッサの各ウェイのＬＲＵ順位ｓを順次ｓ+１に更新する（Ｓ１０１３）。この更新は、更新後のＬＲＵ順位が、ヒットしたプロセッサの全てのウェイが更新されるまで行われる（Ｓ１０１４）。
【００５８】
以上述べたように、実施形態１は、キャッシュメモリにキャッシュされているデータを、マルチプロセッサのどのプロセッサにも供給することができるので、スヌープを用いることがなく、比較的省電力かつ小型な構成でありながらプロセッサ間でデータのコヒーレンシを一致させることができる。また、複数のプロセッサのいずれもが他のプロセッサに対応してキャッシュされているデータの提供を受けることができるので、キャッシュメモリのプロセッサによるアクセス効率を高めることができる。
【００５９】
また、実施形態１は、キャッシュメモリが複数のウェイでなる場合、ウェイごとに書出しの優先順位を付しておく。そして、一のプロセッサがキャッシュメモリにデータを要求したとき、このデータが他のプロセッサのキャッシュにあってもデータを要求したプロセッサに供給することができるので、キャッシュされているデータを有効に活用してプロセッサのメモリ１０３へのアクセス回数を低減することができる。
【００６０】
また、他のプロセッサにデータがアクセスされた場合にもアクセスの状態に応じてデータの書出しの優先度を決定することができるので、他のプロセッサによるアクセスをも考慮してデータの書出し優先度を決定することができる。
すなわち、他のプロセッサによってアクセスされたデータの優先度を変更する場合、複数のプロセッサでアクセスされる頻度が多いデータを優先してキャッシュしておくことができ、プロセッサ全体の動作効率を高めることができる。また、他のプロセッサによるアクセスがあった場合にはデータの優先度を保存する場合、データとデータを読み出したプロセッサとの間のデータヒット回数が高まって、各プロセッサの動作効率を高めることができる。
【００６１】
なお、以上述べた実施形態１では、キャッシュにデータがヒットした場合、このキャッシュの２つのウェイの優先度を直ちに変更しているが、本発明は、このような構成に限定されるものではない。例えば、プロセッサの特性や処理内容に応じ、複数の所定回数データヒットがあった場合にはデータのＬＲＵ順位を変更し、データヒットが所定の回数の達しない間はＬＲＵ順位を保存するものであってもよい。
【００６２】
さらに、データヒットが連続して所定の回数起こった場合にＬＲＵ順位を変更する、あるいはデータヒットが所定の頻度（単位時間当たりのデータヒット回数）に達した場合にＬＲＵ順位を変更することも考えられる。
（実施形態２）
次に、本発明の実施形態２について説明する。実施形態２のキャッシュメモリ及びマルチプロセッサシステムは、入出力制御部４０１が、一のプロセッサ（第２のプロセッサ）に対応して管理されているデータが他のプロセッサ（第１のプロセッサ）に供給された場合、第２のプロセッサに対応して管理されているデータの書出し優先度を保存する点で、書出し優先度を変更する実施形態１と相違するものである。
【００６３】
図１１は、（ａ）、（ｂ）は、実施形態２のＬＲＵの処理を説明するための図である。図１１は、プロセッサ２が供給を要求したデータが、プロセッサ３のウェイＵ１にヒットした場合の例を示していて（図１１（ａ））、このような場合、入出力制御部４０１は、プロセッサ３のウェイＵ１として管理されているデータをプロセッサ２に供給する。実施形態２では、プロセッサ３に対応して管理されているデータの書出し優先度は、データヒットの有無とは無関係に保存される（図１１（ｂ））。
【００６４】
このような実施形態２は、マルチプロセッサ１０５に備えられる複数のプロセッサが各々異なる処理を実行するマルチプロセッサにおいて、各プロセッサの独立性を保つことに有利である。すなわち、実施形態１のように、他プロセッサのアクセスによってＬＲＵ順位を変更すると、各プロセッサのＬＲＵ処理に他のプロセッサが干渉することになる。実施形態２では、この点に鑑み、キャッシュされているデータに対する他のプロセッサのアクセスは許可するものの、ＬＲＵ順位は保存して各プロセッサの独立性を保っている。
【００６５】
図１２は、図１１に示した処理のうち、入出力制御部４０１によってなされるキャッシュの制御を説明するためのフローチャートである。入出力制御部４０１は、プロセッサからデータアクセスの要求を受け、タグメモリ４０３に要求されたデータがヒットするか否かを検出する（Ｓ１２０１）。そして、データを要求したプロセッサに対応して管理されているデータにヒットしたか否か判断し（Ｓ１２０２）、ヒットが検出された場合には（Ｓ１２０２：Ｙｅｓ）、アクセスがデータの書出しを要求するものか否か判断する（Ｓ１２０３）。
【００６６】
データの書出しが要求された場合（Ｓ１２０３：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ１２０４）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ１２０５）。
また、ステップＳ１２０３において、アクセスがデータの書出しを目的とするものでないと判断された場合（Ｓ１２０３：Ｎｏ）、Ｗａｙ（ｎ）を読み出してアクセスしたプロセッサに供給する（Ｓ１２０８）。そして、入出力制御部４０１は、ＬＲＵにしたがってこのデータのアクセス履歴等を示す情報をタグメモリ４０３において更新する（Ｓ１２０７）。
【００６７】
一方、ステップＳ１２０２において、データがヒットしないと判断された場合（Ｓ１２０２：Ｎｏ）、入出力制御部４０１は、他のプロセッサにキャッシュされ、このプロセッサに対応して管理されているデータにヒットしたか否か判断する（Ｓ１２０８）。ヒットが検出された場合（Ｓ１２０８：Ｙｅｓ）、アクセスがデータの書出しを要求するものか否か判断する（Ｓ１２０９）。
【００６８】
データの書出しが要求された場合（Ｓ１２０９：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ１２１０）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ１２１１）。一方、アクセスがデータの書出しを目的とするものでない場合（Ｓ１２０９：Ｎｏ）、Ｗａｙ（ｎ）を読み出してアクセスしたプロセッサに供給する（Ｓ１２１２）。
【００６９】
なお、実施形態２では、ステップＳ１２１２の処理の後、Ｕｓｅｄテーブルに記録されている他のプロセッサのキャッシュのＬＲＵ順位を示すフラグを更新することなく処理を終了する。このような動作により、実施形態２は、対応するプロセッサ以外のプロセッサによってアクセスされたウェイのＬＲＵ順位が保存される。
また、ステップＳ１２０８において、他のプロセッサによってキャッシュされたデータにもヒットしなかったと判断された場合（Ｓ１２０８：Ｎｏ）、Ｗａｙ（ｎ）においてアクセス後に最も長い期間使用されていないデータをＬＲＵのアルゴリズムによって検出する（Ｓ１２１３）。そして、検出されたデータがダーティデータであるか否か判断する（Ｓ１２１４）。データがダーティデータである場合（Ｓ１２１４：Ｙｅｓ）、このデータをデータメモリ４０４から書出し（Ｓ１２１５）、書き出された領域にメモリ１０３からデータを読み出す（Ｓ１２１６）。
【００７０】
そして、さらに、入出力制御部４０１は、アクセスがデータの書出しを要求するものか否か判断する（Ｓ１２１７）。データの書出しが要求された場合（Ｓ１２１７：Ｙｅｓ）、データメモリのタグに対応するウェイ（Ｗａｙ（ｎ））へデータを書き込む（Ｓ１２１８）。そして、書き込まれたデータのフラグをダーティフラグに更新する（Ｓ１２１９）。
【００７１】
また、ステップＳ１２１７において、アクセスがデータの書出しを目的とするものでないと判断された場合（Ｓ１２１７：Ｎｏ）、Ｗａｙ（ｎ）にキャッシュされていたデータを読み出し、アクセスしたプロセッサに供給する（Ｓ１２２０）。そして、入出力制御部４０１は、ＬＲＵにしたがってこのデータのアクセス履歴等を示す情報をタグメモリ４０３において更新する（Ｓ１２２１）。
【００７２】
図１３は、図１１に示した処理のうち、ＵｓｅｄテーブルのＬＲＵ順位を変更するための処理を説明するためのフローチャートである。入出力制御部４０１は、プロセッサによって要求されたデータをタグメモリ４０３に照会し、要求されたデータが要求したプロセッサのキャッシュのいずれかのウェイにヒットしたか否か判断する（Ｓ１３０１）。ヒットしたと判断された場合（Ｓ１３０１：Ｙｅｓ）、プロセッサのヒットしたウェイのＬＲＵ順位を０に更新する（Ｓ１３０２）。
【００７３】
次に、入出力制御部４０１は、変数ｓを０に設定し（Ｓ１３０３）、複数のプロセッサの各ウェイのＬＲＵ順位ｓを順次ｓ+１に更新する（Ｓ１３０４）。この更新は、更新後のＬＲＵ順位が、ヒットしたプロセッサのウェイのヒット直前のＬＲＵ順位に達するまで行われる（Ｓ１３０５）。
一方、プロセッサｋが要求したデータが自キャッシュにヒットしないとき（Ｓ１３０１：Ｎｏ）、入出力制御部４０１は、他のプロセッサのキャッシュのウェイにヒットしたか否か判断する（Ｓ１３０６）。ヒットした場合（Ｓ１３０６：Ｙｅｓ）、実施形態２ではＬＲＵ順位を変更することなく処理を終了する。
【００７４】
また、ステップＳ１３０６において、他のプロセッサのキャッシュにもヒットしなかったと判断された場合（Ｓ１３０６：Ｎｏ）、自キャッシュの最もＬＲＵ順位が低いウェイのＬＲＵ順位を０に更新する（Ｓ１３０７）。そして、変数ｓを０に設定し（Ｓ１３０８）、複数のプロセッサの各ウェイのＬＲＵ順位ｓを順次ｓ+１に更新する（Ｓ１３０９）。この更新は、更新後のＬＲＵ順位が、ヒットしたプロセッサの全てのウェイが更新されるまで行われる（Ｓ１３１０）。
【００７５】
以上述べたように、実施形態２は、実施形態１と同様に、一のプロセッサが他のプロセッサのキャッシュメモリにデータを要求したとき、このデータを要求したプロセッサに供給することができる。このため、キャッシュされているデータを有効に活用してプロセッサのメモリ１０３へのアクセス回数を低減することができる。
また、他のプロセッサによるデータアクセスがあった場合、アクセスされたキャッシュの書出しの優先度を変更することなく保存する。このため、キャッシュされたデータを共用しながらもマルチプロセッサ等の各プロセッサの独立性を保つことができる。
【００７６】
なお、本発明は、以上述べた実施形態に限定されるものではない。すなわち、実施形態１、実施形態２で説明したキャッシュメモリは、いずれもデータメモリをマルチポートメモリとしているが、データメモリはマルチポートメモリに限定されるものでなく、シングルポートメモリとして構成することが可能である。
図１４は、図４で示したマルチポートメモリのデータメモリ４０４をシングルポートのデータメモリ４０４ａ〜４０４ｄとした構成を説明するための図である。データメモリ４０４ａ〜４０４ｄは、キャッシュされたデータを、データを読み出したプロセッサごとに保存する複数のデータメモリである。入出力制御部１４０１は、複数のデータメモリ４０４ａ〜４０４ｄの各々とシングルポートによって接続されている。
【００７７】
また、複数のデータメモリ４０４ａ〜４０４ｄと入出力制御部１４０１とを接続した場合、プロセッサ０〜３によるデータメモリ４０４ａ〜４０４ｄへのアクセスの競合が発生する。プロセッサ０〜３によるアクセスを時分割で処理するため、入出力制御部１４０１は、競合制御部１４０５を備えている。
図１４に示した構成によれば、マルチポートメモリより安価なシングルポートメモリを使用して本発明の構成を実現することができる。このため、本発明のキャッシュメモリ及びマルチポートメモリシステムを低コストで市場に提供し、キャッシュメモリ及びマルチポートメモリの普及を促進させることができる。
【図面の簡単な説明】
【００７８】
【図１】本発明の実施形態１、実施形態２のキャッシュメモリ及びキャッシュメモリを使って動作するマルチプロセッサシステムの構成を説明するための図である。
【図２】マルチプロセッサシステムのプロセッサの結合の例を説明するための図である。
【図３】一般的なマルチプロセッサの動作を説明するための図である。
【図４】図１に示したキャッシュメモリの構成をより詳細に示した図である。
【図５】図４に示したタグメモリ、データメモリに記憶されるデータの構造を説明するための図である。
【図６】実施形態１のＬＲＵの処理を説明するための図である。
【図７】本発明の実施形態１のキャッシュメモリの動作を説明するためのフローチャートである。
【図８】本発明の実施形態１のＬＲＵの処理を説明するための他の図である。
【図９】図８に示した処理のうち、入出力制御部によってなされるキャッシュの制御を説明するためのフローチャートである。
【図１０】図８に示した処理のうち、ＵｓｅｄテーブルのＬＲＵ順位を変更するための処理を説明するためのフローチャートである。
【図１１】本発明の実施形態２のＬＲＵの処理を説明するための図である。
【図１２】図１１に示した処理のうち、入出力制御部によってなされるキャッシュの制御を説明するためのフローチャートである。
【図１３】図１１に示した処理のうち、ＵｓｅｄテーブルのＬＲＵ順位を変更するための処理を説明するためのフローチャートである。
【図１４】図４で示したマルチポートメモリのデータメモリをシングルポートのデータメモリとした構成を説明するための図である。
【符号の説明】
【００７９】
１０１  キャッシュ制御部、１０２  キャッシュメモリ部、１０３  メモリ、１０５  マルチプロセッサ、１０６  ローダ、１０８  アプリケーション、１０９  キャッシュメモリ、４０１  入出力制御部、４０２  ヒット検出部、４０３  タグメモリ、４０４、４０４ａ〜ｄ  データメモリ
【図１】
2007156963.tif 000003
【図２】
2007156963.tif 000004
【図３】
2007156963.tif 000005
【図４】
2007156963.tif 000006
【図５】
2007156963.tif 000007
【図６】
2007156963.tif 000008
【図７】
2007156963.tif 000009
【図８】
2007156963.tif 000010
【図９】
2007156963.tif 000011
【図１０】
2007156963.tif 000012
【図１１】
2007156963.tif 000013
【図１２】
2007156963.tif 000014
【図１３】
2007156963.tif 000015
【図１４】
2007156963.tif 000016