(57)【要約】      （修正有）【課題】キャッシュのムーブイン要求の発行性能を向上する演算処理装置を提供する。【解決手段】メモリアクセス要求がキャッシュミスした場合にデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、ムーブイン要求の情報が登録される複数のムーブインバッファとを有する。ムーブインバッファ制御ユニットは、空きムーブインバッファがあるとメモリアクセス要求のためにムーブインバッファを確保し、メモリアクセス要求と同一インデックスを有するムーブイン要求が複数のムーブインバッファのいずれにも登録中でないと、ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、登録中であって、複数のムーブインバッファのいずれかに登録中の同一インデックスを有するムーブイン要求が全てのWAYを使用中でないと、ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行する。【選択図】図４
2019053390.tif 000002
【特許請求の範囲】
【請求項１】
メモリアクセス要求を発行するメモリアクセス要求発行部と、
タグメモリとデータメモリを有し、前記タグメモリとデータメモリ内の前記メモリアクセス要求のインデックスと一致するブロックにデータの状態とデータが登録されるキャッシュメモリと、前記メモリアクセス要求がキャッシュミスした場合に前記メモリアクセス要求のデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、前記ムーブイン要求の情報が登録される複数のムーブインバッファとを有するキャッシュとを有し、
前記ムーブインバッファ制御ユニットは、前記キャッシュミスしたメモリアクセス要求の入力に応答して、
（ａ）前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、
（ｂ）前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｃ）前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であることを検出し、更に、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全てのWAYを使用中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｄ）前記全てのWAYを使用中であることを検出すると、前記確保したムーブインバッファを解放し、前記ムーブイン要求の発行を抑止する、演算処理装置。
【請求項２】
前記ムーブインバッファ制御ユニットは、前記入力されたキャッシュミスしたメモリアクセス要求をクロックに同期して処理するパイプライン回路を有し、前記（ａ）、（ｂ）、（ｃ）、（ｄ）を順次実行する、請求項１に記載の演算処理装置。
【請求項３】
前記複数のムーブインバッファのそれぞれには、前記ムーブイン要求の情報として、有効ビットと、前記メモリアクセス要求のインデックスと、前記ムーブイン要求に応答して返信されるデータ応答のデータを登録する前記キャッシュメモリ内のWAYと、前記データ応答のデータが記憶される、請求項２に記載の演算処理装置。
【請求項４】
前記ムーブインバッファ制御ユニットは、前記複数のムーブインバッファ内に前記有効ビットが無効状態である前記空きムーブインバッファがあるか否かを判定する空き判定回路を有し、
前記空き判定回路が前記空きムーブインバッファを検出するとき、前記ムーブインバッファ制御ユニットは、前記空きムーブインバッファの前記有効ビットを有効にして前記メモリアクセス要求のためにムーブインバッファを確保し、さらに、確保したムーブインバッファに前記メモリアクセス要求のインデックスを登録する、請求項３に記載の演算処理装置。
【請求項５】
前記ムーブインバッファ制御ユニットは、前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中か否かを判定するインデックスマッチ回路を有し、
前記インデックスマッチ回路が、前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行する、請求項３に記載の演算処理装置。
【請求項６】
前記ムーブインバッファ制御ユニットは、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全WAYを使用中か否か判定し、更に全WAYを使用中でない場合未使用のWAYを検出するリプレースWAY検出回路を有し、
前記リプレースWAY検出回路が、前記全WAYを使用中でないことを検出すると、前記ムーブインバッファ制御ユニットは、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、前記未使用のWAYを前記確保したムーブインバッファに登録し、
前記リプレースWAY検出回路が、前記全WAYを使用中であることを検出すると、前記ムーブインバッファ制御ユニットは、前記確保したムーブインバッファを解放する、請求項３に記載の演算処理装置。
【請求項７】
メモリアクセス要求を発行するメモリアクセス要求発行部と、
タグメモリとデータメモリを有し、前記タグメモリとデータメモリ内の前記メモリアクセス要求のインデックスと一致するブロックにデータの状態とデータが登録されるキャッシュメモリと、前記メモリアクセス要求がキャッシュミスした場合に前記メモリアクセス要求のデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、前記ムーブイン要求の情報が登録される複数のムーブインバッファとを有するキャッシュとを有する演算処理装置の制御方法であって、
前記ムーブインバッファ制御ユニットは、前記キャッシュミスしたメモリアクセス要求の入力に応答して、
（ａ）前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、
（ｂ）前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｃ）前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であることを検出し、更に、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全てのWAYを使用中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｄ）前記全てのWAYを使用中であることを検出すると、前記確保したムーブインバッファを解放し、前記ムーブイン要求の発行を抑止する、処理を有する演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，演算処理装置及び演算処理装置の制御方法に関する。
【背景技術】
【０００２】
演算処理装置（プロセッサ、CPU（Central Processing Unit））は、外部に設けられた主記憶装置（メインメモリ）へのアクセスに要する長いレイテンシを回避するために、内部にキャッシュメモリを有する。キャッシュメモリには、プロセッサがメモリアクセス命令を実行したときにメインメモリから読み出したデータが記憶される。そして、プロセッサが同じアドレスについて再度メモリアクセス命令を実行するとき、キャッシュメモリ（以下、「キャッシュ」と呼ぶことがある）からデータを読み出すことで、メインメモリへのアクセス動作を回避する。
【０００３】
プロセッサの命令発行部がロード命令やストア命令を発行すると、メモリアクセス要求がキャッシュに投入される。そして、キャッシュがアクセスアドレスのデータがキャッシュメモリに保持、または登録、されているか否かのキャッシュ判定を実行する。この判定がキャッシュヒットの場合、キャッシュはキャッシュメモリ内のデータを命令発行部にデータ応答（データ付の応答）する。一方、キャッシュミスの場合、キャッシュは、メインメモリにより近い下位レベルのキャッシュに、またはメモリ制御回路にムーブイン要求を発行する。
【０００４】
ムーブイン要求とは、あるレベルのキャッシュが、メインメモリにより近い下位レベルのキャッシュにまたはメモリ制御回路に、アクセスアドレスのデータを応答することを求める要求であり、一種のメモリアクセス要求である。ムーブイン要求はキャッシュミスが発生したキャッシュが発行する。
【０００５】
ムーブイン要求については、以下の特許文献に記載されている。
【０００６】
ムーブイン要求の発行からデータ応答まで長時間を要する場合があるため、例えばＬ１キャッシュとＬ２キャッシュとの間に（またはＬ２キャッシュとＬ３キャッシュとの間に）、ムーブイン要求中の情報を登録できるムーブインバッファが配置される。そして、Ｌ１キャッシュがムーブイン要求を発行するとき、ムーブインバッファを獲得し、そこに、ムーブイン要求の情報である、キャッシュミスしたキャッシュメモリのインデックス情報（インデックスアドレス）と、データ応答後に応答データをキャッシュ登録するキャッシュのＷＡＹ情報とを登録する。
【０００７】
そして、Ｌ２キャッシュがＬ１キャッシュに登録中の古いデータの追い出し要求を発行し、Ｌ１キャッシュからＬ２キャッシュにデータを追い出した後に、Ｌ１キャッシュは、Ｌ２キャシュからのデータ応答を受信し、対応するムーブインバッファのデータ領域に新しいデータを格納する。そして、Ｌ１キャッシュは、ムーブインバッファに登録していたインデックス情報とＷＡＹ情報に基づいて、応答されたデータをＬ１キャッシュメモリに登録するとともに、命令発行部（またはメインメモリからより遠い上位レベルのキャッシュ）にデータ応答する。データ応答されると、ムーブイン要求の情報を登録していたムーブインバッファは解放される。ムーブインバッファに複数のムーブイン要求情報を登録することで、先行するムーブイン要求に対するデータ応答を受信する前に、次のムーブイン要求を発行する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開第２００７／０８８５９１号
【特許文献２】特開２００１−５１８９９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
キャッシュは、同一のインデックス且つ同一のリプレースWAYを持つ複数のムーブイン要求を同時期に発行することを抑止することが必要である。その理由は、例えば、後続のムーブイン要求に対するリプレースWAY内のデータの追い出し要求とデータ応答が、先行のムーブイン要求に対するデータ応答を追い越す可能性があるからである。追い越しが発生すると、同一のキャッシュブロック（同一のインデックス且つ同一のWAYのブロック）に対して、後続のムーブイン要求のデータ追い出し及びデータ応答に伴うキャッシュ登録後に、先行ムーブイン要求の応答データのキャッシュ登録が行われる。このような動作は、L1キャッシュとL2キャッシュ間でキャッシュコヒーレンシを維持できず、キャッシュでのプロトコルエラーとなる。
【００１０】
一方、上記の同じキャッシュブロック（同じインデックスアドレス、同じWAY）で競合するムーブイン要求の発行を抑止するためには、キャッシュミス発生時に、ムーブインバッファ内を検索して、キャッシュミスしたメモリアクセス要求と同じインデックス及びWAYを有する実行中またはムーブインバッファに登録中のムーブイン要求があるか否かの判定を行う必要がある。
【００１１】
しかし、この判定は一定の処理サイクルを必要とするので、高周波クロックで動作するムーブインバッファ制御ユニット内のパイプライン回路は、連続して発生するキャッシュミスしたメモリアクセス要求を短いクロックサイクルで効率よく処理することが困難である。
【００１２】
そのため、一部のプロセッサでは、同一リプレースWAYか否かの判定を省略し、キャッシュミスしたメモリアクセス要求と同じインデックスを持つムーブイン要求がムーブインバッファ内に登録中であれば、そのメモリアクセス要求に対するムーブイン要求の発行を抑止し、メモリアクセス要求をアボートしリクエストポートに差し戻している。このようなプロセッサは、連続するメモリアクセス要求に対するムーブインバッファ制御ユニットの処理効率は上がるが、インデックスで競合するムーブイン要求をリプレース可能なWAY数まで複数発行できず、性能低下を招く。
【００１３】
そこで，本実施の形態の第1の側面の目的は，キャッシュのムーブイン要求の発行性能を向上した演算処理装置及び演算処理装置の制御方法を提供することにある。
【課題を解決するための手段】
【００１４】
本実施の形態の第１の側面は，メモリアクセス要求を発行するメモリアクセス要求発行部と、
タグメモリとデータメモリを有し、前記タグメモリとデータメモリ内の前記メモリアクセス要求のインデックスと一致するブロックにデータの状態とデータが登録されるキャッシュメモリと、前記メモリアクセス要求がキャッシュミスした場合に前記メモリアクセス要求のデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、前記ムーブイン要求の情報が登録される複数のムーブインバッファとを有するキャッシュとを有し、
前記ムーブインバッファ制御ユニットは、前記キャッシュミスしたメモリアクセス要求の入力に応答して、
（ａ）前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、
（ｂ）前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｃ）前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であることを検出し、更に、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全てのWAYを使用中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｄ）前記全てのWAYを使用中であることを検出すると、前記確保したムーブインバッファを解放し、前記ムーブイン要求の発行を抑止する、演算処理装置である。
【発明の効果】
【００１５】
第１の側面によれば，キャッシュのムーブイン要求の発行性能を向上することができる。
【図面の簡単な説明】
【００１６】
【図１】本実施の形態の演算処理装置（プロセッサ）の構成を示す図である。
【図２】本実施の形態におけるL1キャッシュとL2キャッシュの組み合わせの構成を示す図である。
【図３】キャッシュメモリの構成例を示す図である。
【図４】L1キャッシュの動作を示すフローチャート図である。
【図５】L1キャッシュの動作を示すシーケンス図である。
【図６】ムーブインバッファ制御ユニットとリプレースWAY選択ユニットの構成例を示す図である。
【図７】ムーブインバッファ制御ユニット内のMIB空き判定回路の一例を示す図である。
【図８】ムーブインバッファ制御ユニット内のインデックスマッチ判定回路IDX_MCH_JDGとリプレースWAY選択ユニット内の同一インデックスのムーブイン要求のWAY使用状態判定回路WAY_JDGの回路例を示す図である。
【図９】インデックスマッチ判定回路IDX_MCH_JDGのより詳細な回路の一例を示す図である。
【図１０】リプレースWAY選択ユニット内の全WAY使用判定回路ALL_WAY_JDGと、リプレースWAY選択回路RPL_WAY_SELの回路例を示す図である。
【図１１】リプレースWAY選択ユニットに関する動作を示すフローチャート図である。
【図１２】リプレースWAY選択回路の真理値表を示す図である。
【図１３】本実施の形態におけるL1キャッシュのムーブインバッファ制御ユニットによるムーブインバッファ制御を示すタイミングチャート図である。
【図１４】連続する命令の処理を説明する図である。
【発明を実施するための形態】
【００１７】
［演算処理装置（プロセッサ）］
図１は、本実施の形態の演算処理装置（プロセッサ）の構成を示す図である。プロセッサ１は、例えばプロセッサ回路を集積したCPUチップであり、DRAMなどの主記憶装置（メインメモリ）４０にアクセス可能である。プロセッサ１とメインメモリ４０によりコンピュータなどの情報処理装置が構成される。
【００１８】
プロセッサ１は、例えば複数のCPUコアCR_0, CR_1を有する。各CPUコアは、例えば演算器２、ロード命令やストア命令を処理する命令発行部３、第１レベルのキャッシュ（L1 CACHE）１０、第２レベルのキャッシュ（L2 CACHE）２０を有する。さらに、プロセッサ１は、複数のCPUコア内のL2キャッシュ２０で共用される第３レベルのキャッシュ（L3 CACHE）３０と、メインメモリへのアクセスを制御するメモリアクセスコントローラMACと、CPUチップの外部に設けられたハードディスク等との入出力を行う入出力回路IOとを有する。
【００１９】
本実施の形態におけるムーブインバッファを有するキャッシュは、例えばL1キャッシュ１０、L2キャッシュ２０、L3キャッシュ３０のいずれにも適用できる。但し、以下の実施の形態の説明ではL1キャッシュ１０に適用した例で説明する。
【００２０】
いずれかのCPUコアにて、命令発行部３がロード命令やストア命令を発行すると、ロード命令またはストア命令に対するメモリアクセス要求を発行し、L1キャッシュ１０に投入される。したがって、命令発行部３はメモリアクセス要求を発行する要求発行部でもある。以下の説明ではメモリアクセス命令がロード命令（メインメモリのデータ読み出し命令）の例で説明する。
【００２１】
L1キャッシュ１０は、メモリアクセス要求のアクセスアドレスに基づいてタグメモリを検索しキャッシュ判定しキャッシュヒットするとL1キャッシュ内のデータを命令発行部３に応答する。一方、キャッシュミスすると、L1キャッシュ１０は、L2キャッシュ２０にムーブイン要求を発行する。ムーブイン要求は、メモリアクセス要求のデータをL1キャッシュメモリに登録することを求める要求である。そして、L1キャッシュ１０は、L2キャッシュからデータ応答を受信すると、そのデータをキャッシュに登録し、データを命令発行部３に応答する。
【００２２】
L2キャッシュ２０が、L1キャッシュ１０が発行したムーブイン要求（一種のメモリアクセス要求）についてキャッシュミスすると、上記と同様にL3キャッシュ３０にムーブイン要求を発行する。同様に、L3キャッシュが、L2キャッシュからのムーブイン要求についてキャッシュミスすると、メモリアクセスコントローラMACにムーブイン要求と同等のアクセス要求を発行する。つまり、あるレベルのキャッシュが、受信したメモリアクセス要求についてキャッシュミスすると、よりメインメモリに近いレベルのキャッシュまたはメモリコントローラにムーブイン要求を発行する。
【００２３】
各キャッシュは、メインメモリ側のキャッシュまたはメモリアクセスコントローラとの間に、ムーブイン要求の情報を登録する複数のムーブインバッファ（図示せず）を有する。キャッシュに複数のムーブインバッファを設けることで、キャッシュは複数のムーブイン要求の情報を登録することができ、短時間の間に複数のムーブイン要求を並行に発行することができる。
【００２４】
[キャッシュの構成]
図２は、本実施の形態におけるL1キャッシュとL2キャッシュの組み合わせの構成を示す図である。L2キャッシュとL3キャッシュの組み合わせの構成も同様である。また、L3キャッシュとメモリアクセスコントローラMACの組み合わせの構成も、メモリアクセスコントローラMACにキャッシュメモリDATA_RAM,TAG_RAMがないことを除いて、同様である。
【００２５】
L1キャッシュ１０は、命令発行部３からのメモリアクセス要求MA_RQや滞留したメモリアクセス要求RQ_STYなどを格納する複数のリクエストポート１１と、複数のリクエストポート内の要求を、所定の優先度に基づいて選択する要求選択回路RQ_SELとを有する。要求選択回路RQ_SELは選択したメモリアクセス要求をL1キャッシュ１０内のキャッシュパイプラインに投入または入力する。
【００２６】
キャッシュパイプラインは、TLB（Translation Lookaside Buffer）、キャッシュメモリを構成するデータメモリDATA_RAM及びタグメモリTAG_RAMと、ムーブインバッファ制御ユニットMIB_CNと、LRU回路LRUと、リプレースWAY選択ユニットRPL_SELなどで構成される。
【００２７】
TLBはメモリアクセス要求MA_RQの論理アドレスを物理アドレスに変換する。タグメモリTAG_RAMにはキャッシュ登録されているデータの有効性、状態情報、WAY情報、アドレス情報等が登録され、メモリアクセス要求のキャッシュヒット判定で参照される。そして、タグメモリは、キャッシュヒットの場合にそのWAY情報HIT_WAYをLRU回路LRUに出力し、キャッシュミスの場合にキャッシュミスMISSをムーブインバッファ制御ユニットMIB_CNに出力する。
【００２８】
ムーブインバッファ制御ユニットMIB_CNは、キャッシュミスしたメモリアクセス要求の入力に応答して一つのムーブインバッファMIBを獲得し、ムーブイン要求MI_RQの情報をムーブインバッファMIBに登録し、ムーブイン要求MI_RQをL2キャッシュ２０に発行する。
【００２９】
LRU回路は、キャッシュヒットしたWAY情報HIT_WAYとムーブインバッファMIB内のムーブイン要求のWAY情報MI_WAYに基づいて、キャッシュメモリ（DATA_RAM, TAG_RAM）の各WAYへのアクセスの古さを判定し、最もアクセスが古いWAYを示すLRU情報LRU_INFを出力する。
【００３０】
リプレースWAY選択ユニットRPL_SELは、LRU回路からのLRU情報LRU_INFに基づいて、ムーブイン要求に対する応答データをキャッシュメモリのどのウエイに登録するかを示すリプレースウエイRPL_WAYを選択する。
【００３１】
［ムーブインバッファMIB］
ムーブインバッファMIBは、同時期に複数のムーブイン要求を発行可能にするために、複数有する。各ムーブインバッファMIBは、ムーブインバッファのエントリとも称することができる。
【００３２】
各ムーブインバッファMIBには、前述のとおり、有効ビットVALID、インデックスアドレスIDX_ADD、リプレースWAY番号WAY、データDATAをそれぞれ記憶する。有効ビットVALIDは、例えば、ムーブインバッファが獲得されると有効「１」になり、そのムーブイン要求がデータ応答の受信により完了すると無効「０」となり、ムーブインバッファが開放される。
【００３３】
また、インデックスアドレスIDX_ADDにはメモリアクセス要求のインデックスアドレスADD_2が記憶される。したがって、ムーブインバッファ制御ユニットMIB_CNが、キャッシュミスしたメモリアクセス要求に対してあるムーブインバッファを確保すると、そのムーブインバッファの有効ビットVALIDを「１」に変更し、インデックスアドレスIDX_ADDにキャッシュミスしたメモリアクセス要求のインデックスアドレスIDX_ADDを登録する。
【００３４】
一方、ムーブインバッファを登録した段階では、未だ、ムーブイン要求に対するデータ応答のデータを登録するWAYは決定されていないので、ムーブインバッファ内のリプレースWAY番号WAYは未登録である。そして、ムーブインバッファを確保した後、ムーブインバッファ制御ユニットは、ムーブインバッファ内に同一インデックスのムーブイン要求が登録されていないことを検出し、または同一インデックスのムーブイン要求が登録されているが、全てWAYが使用中でないことを検出すると、リプレースWAY選択ユニットが選択したWAY番号をムーブインバッファに登録する。
【００３５】
さらに、ムーブイン要求に対するデータ応答を受信すると、ムーブインバッファ制御ユニットは、応答データをムーブインバッファのデータDATAに記憶する。
【００３６】
前述したリプレースWAY選択ユニットRPL_SELは、ムーブインバッファに登録中である同一インデックスのムーブイン要求のWAY以外のWAYから、同一インデックスのメモリアクセス要求に対して発行するムーブイン要求のリプレースWAYを選択する。そのために、リプレースWAY選択ユニットには、ムーブインバッファに登録されているムーブイン要求のWAY情報MI_WAYが供給される。
【００３７】
また、リプレースWAY選択ユニットには、ムーブインバッファ制御ユニットに設けられた、メモリアクセス要求のインデックスと、ムーブインバッファに登録中のムーブイン要求のインデックスとが一致するか否かを判定するインデックスマッチ判定回路の一致結果も供給される。この一致結果と、ムーブイン要求のWAY情報MI_WAYとから、ムーブインバッファに登録中である同一インデックスのムーブイン要求のWAYの情報を得る。
【００３８】
詳細は後述するが、リプレースWAY選択ユニットは、タグメモリTAG_RAMの同一インデックスの各WAYの有効ビットも供給される。そして、タグメモリの同一インデックスの４つのWAYで有効ビットが無効のWAYが、ムーブインバッファに登録されているムーブイン要求のWAY以外のWAYに該当する場合、LRU情報に基づくことなく、それらのWAYから所定のWAYをリプレースWAYに選択する。後述するケース１の場合である。
【００３９】
リプレースWAY選択ユニットは、LRU情報LRU_INFも供給され、ムーブインバッファに登録中である同一インデックスのムーブイン要求のWAY以外のWAYから、LRU情報に基づいてリプレースWAYを選択する。後述するケース２の場合である。
【００４０】
図２内には、L1キャッシュのパイプライン回路の各パイプラインステージＰ，Ｔ，Ｍ，Ｓ，Ｂ，Ｂ１，Ｂ２，Ｂ３，Ｂ４の位置が示される。このステージについては、後述するL1キャッシュの動作説明で詳述する。
【００４１】
［キャッシュメモリの構成］
図３は、キャッシュメモリの構成例を示す図である。図３のキャッシュメモリは４WAYセットアソシエティブの例である。キャッシュメモリを構成するタグメモリTAG_RAMとデータメモリDATA_RAMは、ｎ＋１個のインデックス０〜ｎのキャッシュラインまたはキャッシュブロックを有する。そして、メモリアクセス要求のアクセスアドレスA_ADDの下位の一部のアドレスADD_2がインデックスアドレスとして、図示しないデコーダに入力され、インデックスアドレスに対応する一つのインデックスが選択される。また、アクセスアドレスA_ADDの上位アドレスADD_1（論理アドレスをTLBにより変換した物理アドレスの上位アドレス）は、タグメモリTAG_RAMに記憶される。つまり、タグメモリTAG_RAMには、有効ビットValidと上位アドレスADD_1が記憶される。
【００４２】
そして、４つの比較器CMPが、インデックスアドレスADD_2で選択されたタグメモリのインデックスの４つのウエイWAY内のアドレスADD_1それぞれと、アクセスアドレスA_ADDの上位アドレスADD_1（論理アドレスをTLBにより変換した物理アドレスの上位アドレス）とを、それぞれの比較し、一致ならヒットWAY情報W0-W3を「１」（キャッシュヒットを示す）にする。キャッシュヒットの場合、一つの比較器がヒットWAY情報W0-W3を「１」にし、キャッシュミスの場合、４つの比較器CMP全てがヒットWAY情報W0-W3を「０」にする。
【００４３】
また、ウエイセレクタWAY_SELが、データメモリDATA_RAMからインデックスアドレスADD_2により選択された４つのWAYのデータDATAのうち、ヒットWAY情報W0-W3に基づいて、一致したウエイのデータを選択する。
【００４４】
このように、セットアソシエティブのキャッシュメモリは、インデックスアドレスADD_2で選択されるインデックス毎にキャッシュブロックにまとめ、そのブロック内のデータをまとめて記憶する。また、キャッシュメモリは、同じインデックスアドレスADD_2に対して、最大でWAY数分（図３ではWAY数＝４）のメモリブロックのデータDATAを登録する。なお、アクセスアドレスA_ADDの下位アドレスADD_3は、図示しないが、選択されたキャッシュブロックからアクセス先データを選択するために使用される。
【００４５】
上記の通り、キャッシュメモリのインデックスはインデックスアドレスADD_2により選択され、インデックスアドレスが同一なら選択されるインデックスも同一である。以下の説明では、メモリアクセス要求のインデックスアドレスADD_2を便宜的にインデックスと称し、ムーブインバッファに記憶されている要求中のムーブイン要求のインデックスアドレスIDX_ADDを便宜的にインデックスと称する。
【００４６】
［ムーブインバッファ制御ユニット及びリプレースWAY選択ユニットの構成とキャッシュの動作］
図４は、L1キャッシュの動作を示すフローチャート図である。また、図５は、L1キャッシュの動作を示すシーケンス図である。いずれの図にも、キャッシュのパイプラインステージＰ，Ｔ，Ｍ，Ｓ，Ｂ，Ｂ１，Ｂ２，Ｂ３，Ｂ４が示される。
【００４７】
さらに、図６は、ムーブインバッファ制御ユニットとリプレースWAY選択ユニットの構成例を示す図である。ムーブインバッファ制御ユニットMIB_CNは、MIBパイプライン制御回路MIB_PIPE_CNと、ムーブインバッファ空き判定回路INV_MIB_JDGと、インデックスマッチ判定回路IDX_MCH_JDGと、MI要求発行回路MI_RQ_ISSUとを有する。また、リプレースWAY選択ユニットRPL_SELは、同一インデックスのムーブイン要求のWAY使用状態判定回路WAY_JDGと、全WAY使用判定回路ALL_WAY_JDGと、リプレースWAY選択回路RPL_WAY_SELとを有する。
【００４８】
図６にも、ムーブインバッファ制御ユニットとリプレースWAY選択ユニットのパイプラインステージＢ，Ｂ１，Ｂ２，Ｂ３，Ｂ４が示されている。
【００４９】
MIB制御ユニットのMIB空き判定回路はステージＢに配置され、ムーブインバッファMIBの有効ビットValidを入力し、有効ビットが無効のムーブインバッファが存在するか否かを判定し、全有効ムーブインバッファ信号ALL_VAL_MIBを出力する。
【００５０】
インデックスマッチ判定回路はステージＢ，Ｂ１に配置され、メモリアクセス要求のインデックスアドレスADD_2とムーブインバッファに登録されているムーブイン要求のインデックスIDX_MIBのいずれかが一致するか否か判定し、インデックスマッチ信号IDX_MCHを出力する。そして、ムーブイン要求発行回路は、ステージＢ２とＢ４でムーブイン要求MI_RQを発行している。
【００５１】
一方、リプレースWAY選択ユニットの同一インデックスのムーブイン要求のWAY使用状態判定回路は、Ｂ２ステージに配置され、インデックスマッチ判定回路が生成する各ムーブインバッファMIB0-nについてのインデックスマッチ信号IDX_MCH0-nがマッチ「１」になるムーブイン要求によるWAYの使用状態を判定する。
【００５２】
全WAY使用判定回路は、Ｂ３ステージに配置され、同一インデックスのムーブイン要求のWAY使用状態に基づいて、全WAYが使用中か否かを判定し、全WAY使用信号ALL_WAYを出力する。
【００５３】
また、リプレースWAY選択回路は、Ｂ３ステージに配置され、同一インデックスのムーブイン要求のWAY使用状態等に基づいて、新たに発行されるムーブイン要求が使用するWAYを選択し、リプレースWAY信号RPL_WAYを出力する。選択したWAYにデータが登録済みの場合、そのWAYのデータがムーブイン要求に対して獲得されるデータでリプレースされる。
【００５４】
各キャッシュパイプラインステージと、ムーブインバッファ制御ユニット内のパイプラインステージは、以下に説明する通りである。各ステージの処理を説明した後に、図４、図５を参照してL1キャッシュでの動作を説明する。したがって、図４，５によるL1キャッシュでの動作を読みながら、以下の各ステージの処理内容を参照すると、その動作を良く理解できる。
【００５５】
［各ステージの処理内容］
Ｐステージ：パイプラインに命令を投入するか否かを決定する。
Ｔステージ：TLBでアドレス変換（論理アドレスから物理アドレスへ変換）し、TAGメモリ、DATAメモリにアクセスする。
【００５６】
Ｍステージ：キャッシュヒット判定を行う。キャッシュヒット判定では、図３に示したとおり、キャッシュパイプライン回路が、メモリアクセス要求のインデックスアドレスADD_2でキャッシュタグTAG_RAMを検索し、インデックスアドレスに対応するキャッシュタグ内の全てのWAYのアドレスと、メモリアクセス要求のアドレスADD_1とが一致するかの判定を行う。
【００５７】
Ｂステージ：（１）キャッシュヒットの場合、キャッシュパイプライン回路が、４つのWAYのデータを読み出し、アドレスADD_1が一致したWAY番号のデータを選択して出力する。（２）キャッシュミスの場合、図６のムーブインバッファ制御ユニットMIB_CNのMIB空き判定回路INV_MIB_JDGが、ムーブインバッファに空きがあるかの判定を行う。
【００５８】
Ｂ１ステージ：（１）キャッシュヒットの場合、キャッシュヒットしたデータメモリのデータを命令発行部に応答し、メモリアクセス要求の処理を完了する。（２）キャッシュミスの場合、ムーブインバッファに空きがあることが判定されれば、ムーブインバッファ制御ユニットが、ムーブインバッファ確保要求MIB_ENSを発行してムーブインバッファMIBを確保する。また、ムーブインバッファ制御ユニットのインデックスマッチ回路IDX_MCH_JDGは、メモリアクセス要求のインデックスと同一インデックスのムーブイン要求が、ムーブインバッファ内に登録中か否かの判定を開始する。
【００５９】
Ｂ２ステージ：（２）キャッシュミスの場合、（２−１）同一インデックスのムーブイン要求がムーブインバッファに登録中でなければ、ムーブインバッファ制御ユニットのムーブイン要求発行回路MI_RQ_ISSUは、ムーブイン要求を発行する。（２−２）同一インデックスのムーブイン要求がムーブインバッファに登録中であれば、リプレースWAY選択ユニットRPL_SEL内のWAY使用状態判定回路WAY_JDGが、ムーブインバッファ確保中の同一インデックスのムーブイン要求のWAY情報WAY（MI_WAY）を読み出す。
【００６０】
Ｂ３：(２)キャッシュミスの場合、（２−１）同一インデックスのムーブイン要求が登録中でなければ、リプレースWAY選択ユニット内のリプレースWAY選択回路RPL_WAY_SELがムーブイン要求のデータを登録するWAY番号RPL_WAYを出力する。（２−２）同一インデックスのムーブイン要求が登録中であれば、リプレースWAY選択ユニット内の全WAY使用判定回路ALL_WAY_JDGが同一インデックスのムーブイン要求が全WAYを使用中か否かの判定結果ALL_WAYを出力する。そして、全WAYが使用中であれば、次のＢ４ステージで、MIBパイプライン制御回路がムーブインバッファ解放要求MIB_RLを発行し確保されているムーブインバッファMIBを解放する。全WAYが使用中でなければ、リプレースWAY選択回路RPL_WAY_SELがムーブイン要求のデータを登録するWAY番号RPL_WAYを出力する。
【００６１】
Ｂ４：（２）キャッシュミスの場合、全WAYが使用中でなければ、MIBパイプライン制御回路がムーブイン要求の発行要求MI_ISSU_RQを発行し、ムーブインバッファ制御ユニット内のムーブイン要求発行回路がムーブイン要求MI_RQを発行する。
【００６２】
［L1キャッシュの動作］
次に、L1キャッシュの動作を図４、図５を参照して説明する。まず、命令発行部（または要求発行部）が発行したメモリアクセス要求（ロード要求）が要求選択回路RQ_SELによりリクエストポートからキャッシュパイプラインに投入される（Pステージ）。そして、TLBでメモリアクセス要求の論理アドレスが物理アドレスに変換される（Tステージ）。さらに、タグメモリTAG_RAMでキャッシュヒット判定が行われる（S1,Mステージ）。そこで、キャッシュミスが発生すると、ムーブインバッファ制御ユニットMIB_CNはL1キャッシュミスMISSを受信する。
【００６３】
L1キャッシュミスの受信に応答して、ムーブインバッファ制御ユニットMIB_CNのMIB空き判定回路INV_MIB_JDGは、空きムーブインバッファ（InvalidなMIB）があるか否かを判定する（S2,Bステージ）。この判定は、後述する空き判定回路に示されるとおり、全ムーブインバッファMIBの有効ビットをチェックすることで行われる。
【００６４】
空きムーブインバッファがない場合（S2のNO）、ムーブインバッファを確保できないので、キャッシュミスしたメモリアクセス要求に対してムーブイン要求を発行できない。そのため、ムーブインバッファ制御ユニットは、キャッシュミスしたメモリアクセス要求をリクエストポート１１に差し戻し（S3）、メモリアクセス要求を滞留させる。このメモリアクセス要求は次の機会までキャッシュパイプラインへの投入が抑止される。
【００６５】
さらに、ムーブインバッファ制御ユニットのインデックスマッチ判定回路IDX_MCH_JDGは、メモリアクセス要求のインデックスアドレスADD_2に対するインデックスと同一インデックスのムーブイン要求がムーブインバッファMIB内に登録中か否かを判定する（S4,B,B1ステージ）。この判定は、後述するインデックスマッチ判定回路に示されるとおり、ムーブインバッファMIB内の全てのインデックスアドレスIDX_ADDそれぞれと、メモリアクセス要求のインデックスアドレスADD_2との一致（マッチ）をそれぞれ検出する。
【００６６】
ムーブインバッファ制御ユニットは、空きムーブインバッファが存在する場合、インデックスマッチ判定回路の判定結果IDX_MCHに係らず、ムーブインバッファ確保MIB_ENSを発行し、キャッシュミスしたメモリアクセス要求に空きムーブインバッファのいずれかのムーブインバッファを確保（ensure）する（S6,B7,B2ステージ）。ムーブインバッファ制御ユニットは、このムーブインバッファの確保処理で、空きムーブインバッファの有効ビットを有効「１」に変更し、メモリアクセス要求のインデックスアドレスIDX_ADD（ADD_2）をそのムーブインバッファに記憶する。
【００６７】
上記の投機的なムーブインバッファMIBの確保により、同一インデックスのムーブインバッファが登録中でない場合のムーブイン要求MI_RQを、B2ステージで発行することができ（S6,B2ステージ）、ムーブインバッファ制御回路のパイプライン回路の処理効率を高めることができる。
【００６８】
インデックスマッチ判定結果IDX_MCHが同一インデックスのムーブイン要求がいずれかのムーブインバッファMIBに登録中でないことを検出すると、ムーブインバッファ制御ユニットのMIBパイプライン制御回路MIB_PIPE_CNは、ムーブイン要求発行回路MI_RQ_ISSUにムーブイン要求MI_RQを発行させる（S6,B2ステージ）。
【００６９】
しかし、同一インデックスのムーブイン要求が登録中の場合、MIBパイプライン制御回路MIB_PIPE_CNは、リプレースWAY選択ユニットRPL_SEL内のMI_RQのWAY使用状態判定回路WAY_JDGと、全WAY使用判定回路ALL_WAY_JDGと、リプレースWAY選択回路RPL_WAY_SELの出力を待つ。
【００７０】
すなわち、図６に示されるとおり、MI_RQのWAY使用状態判定回路WAY_JDGは、インデックスマッチ判定回路IDX_MCH_JDGの各ムーブインバッファのインデックスアドレスIDX_ADDとのマッチ判定結果IDX_MCH0-ｎと、ムーブインバッファ内の全てのWAY情報MI_WAYとを入力し、同一インデックスのムーブイン要求によるWAY使用状態の判定（４つのWAYのMI_RQによる使用、不使用の判定）を実行する。
【００７１】
また、全WAY使用判定回路ALL_WAY_JDGは、WAY使用状態に基づいて、４つのWAY全てが使用中か否かの判定を行い、全WAY使用中判定ALL_WAYを出力する（S8,B3ステージ）。
【００７２】
MIBパイプライン制御回路MIB_PIPE_CNは、全WAY使用中判定ALL_WAYが全WAY使用中でなければ、ムーブイン要求発行リクエストMI_ISSU_RQを発行し、ムーブイン要求発行回路MI_RQ_ISSUにムーブイン要求MI_RQを発行させる（S11,B4ステージ）。更に、リプレースWAY選択回路RPL_WAY_SELがムーブイン要求MI_RQのデータを登録するWAY（リプレースWAY）を選択し（S10,B3ステージ）、選択したリプレースWAY（RPL_WAY）を出力し、ムーブインバッファにWAYを登録する（S12,B4ステージ）。
【００７３】
MIBパイプライン制御回路MIB_PIPE_CNは、全WAY使用中の場合、ムーブインバッファMIBに対して確保したムーブインバッファを解放するMIB解放要求MI_RLを発行する（S9）。この結果、キャシュミスしたメモリアクセス要求MA_RQは、ムーブインバッファを確保できず、リクエストポート１１に差し戻され（S3）、メモリアクセス要求は滞留する。
【００７４】
上記の通り、メモリアクセス要求のインデックスと同一インデックスを有するムーブイン要求が登録中か否かのインデックスマッチ判定回路の判定処理と、そのインデックスマッチ判定結果に基づく、同一インデックスのムーブイン要求のWAY使用状態判定回路及び全WAY使用判定回路の判定処理は、いずれも所定の処理時間を要する。そのため、高周波数のクロックに同期して動作するパイプライン回路の動作は、複数クロックサイクルを要する。
【００７５】
そこで、本実施の形態のL1キャッシュは、最初に、Bサイクルでムーブインバッファに空きがあることが分かれば、次のB1サイクルで、投機的にムーブインバッファを確保（secure）する。これにより、B1サイクルで、同一インデックスのムーブイン要求がムーブインバッファに未登録であることが分かれば、次のB2サイクルでムーブイン要求MI_RQを発行できる。
【００７６】
また、同一インデックスのムーブイン要求がムーブインバッファに登録中であれば、L1キャッシュは、同一インデックスのムーブイン要求が全WAY使用中か否かの判定を待ち、全WAY使用中でないことが判明した後に、B4ステージでムーブイン要求を発行する。リプレースWAY選択回路により選択されたリプレースWAYのムーブインバッファへの登録は、ムーブイン要求発行後に行われる。
【００７７】
一方、全WAYが使用中の場合は、キャッシュミスしたメモリアクセス要求は、同一インデックスの全てのWAYで登録中のムーブイン要求と競合することになる。したがって、そのように競合する場合は、L1キャッシュは、投機的に確保（secure）したムーブインバッファMIBを解放する（MIB_RL）。
【００７８】
図５に示すとおり、やがて、L2キャッシュ制御部は、ムーブイン要求MI_RQを処理して、要求されたデータを取得する。そして、L2キャッシュ制御部は、L1キャッシュにデータ応答する（S13）。L1キャッシュのムーブインバッファ制御ユニットは、L2キャッシュ制御部からデータ応答を受信すると、応答されたデータを、ムーブイン要求MI_RQが登録されているムーブインバッファMIBのデータ領域DATAにストアする。さらに、L1キャッシュは、ムーブインバッファに登録されているインデックスアドレスIDX_ADDとリプレースWAYに基づいて、L1キャッシュメモリのデータメモリDATA_RAMのリプレース対象のブロックに、データ応答のデータを登録し、タグメモリTAG_RAMのリプレース対象ブロックに対応するインデックス及びWAYに、メモリアクセス要求のアドレスADD_1とデータ状態を登録する（S14）。キャッシュへの登録後、ムーブインバッファ制御ユニットは、確保していたムーブインバッファの有効ビットをインバリッド（無効）にして、ムーブインバッファを解放する（S15）。
【００７９】
なお、図５に示すとおり、キャッシュメモリのリプレースWAYに有効なデータが登録されている場合、L2キャッシュは、データ応答する前に、そのキャッシュメモリのインデックスのリプレースWAYのデータをL2キャッシュメモリに追い出すオーダEJ_ODを発行する。キャッシュメモリからデータの追い出しが完了した後、L2キャッシュからの応答データがリプレースWAYにキャッシュ登録される。最後に、L1キャッシュ１０は、命令発行部３にデータ応答する。
【００８０】
［ムーブインバッファ制御ユニット内のMIB制御UNITとRPL_WAY選択UNITの回路］
図７は、ムーブインバッファ制御ユニット内のMIB空き判定回路の一例を示す図である。MIB空き判定回路は、全ムーブインバッファMIBの有効ビットの論理積（AND）をムーブインバッファ空き判定信号ALL_VAL_MIBとして出力するANDゲートである。ムーブインバッファが確保されると有効ビットは「１」に変更されるので、全ムーブインバッファが確保されて空きムーブインバッファが存在しない場合、MIB空き判定回路は、MIB空き判定信号（全有効MIB信号）ALL_VAL_MIBを「１」にする。つまり、MIB空き判定信号ALL_VAL_MIB＝１の場合は空きMIBがないことを意味し、ALL_VAL_MIB＝０の場合は空きMIBが存在することを意味する。有効ビットのAND論理を求めるだけであるので、MIB空き判定回路は、1クロックサイクル内でMIB空き判定信号ALL_VAL_MIBを出力する。
【００８１】
したがって、図６に示したとおり、MIBパイプライン制御回路MIB_PIPE_CNは、MIB空き判定信号ALL_VAL_MIB＝０の場合は、空きムーブインバッファが存在するので、次のB1サイクルで、ムーブインバッファMIBにムーブインバッファ確保要求MIB_ENSを発行する。これにより、有効ビットがinvalidのムーブインバッファの有効ビットがvalidに変更され、メモリアクセス要求のインデックスアドレスIDX_ADDがそのムーブインバッファに書き込まれる。
【００８２】
図８は、ムーブインバッファ制御ユニット内のインデックスマッチ判定回路IDX_MCH_JDGとリプレースWAY選択ユニット内の同一インデックスのムーブイン要求のWAY使用状態判定回路WAY_JDGの回路例を示す図である。
【００８３】
インデックスマッチ判定回路IDX_MCH_JDGは、n+1個のインデックスマッチ判定回路IDX_MCH0-nと、その出力の論理和を出力する論理OR回路OR0とを有する。n+1個のインデックスマッチ判定回路IDX_MCH0-nは、キャッシュミスしたメモリアクセス要求MA_RQのインデックスアドレスADD_2と、ムーブインバッファMIB内のすべてのインデックスアドレスIDX_ADDそれぞれとの一致（マッチ）をそれぞれ判定する。論理OR回路OR0は、インデックスマッチ判定回路の出力IDX_MCH_JDG0-n（一致で「１」不一致で「０」）の論理和であるインデックスマッチ（一致）出力IDX_MCHを出力する。ムーブインバッファ制御ユニットMIB_CNは、このインデックスマッチ判定回路IDX_MCH_JDGのインデックスマッチ出力IDX_MCHにより、キャッシュミスしたメモリアクセス要求のインデックスアドレスADD_2と同一インデックスのムーブイン要求MI_RQがムーブインバッファMIB内に登録中か否かの判定（図４のS4）を行う。
【００８４】
図９は、インデックスマッチ判定回路IDX_MCH_JDGのより詳細な回路の一例を示す図である。図中、ムーブインバッファMIB_0についてインデックスマッチ判定を行うインデックスマッチ判定回路IDX_MCH0の詳細な構成が示される。インデックスマッチ判定回路IDX_MCH0は、ムーブインバッファMIB_0のインデックスアドレスIDX_ADDと、キャッシュミスしたメモリアクセス要求MA_RQのインデックスアドレスIDX_ADD(ADD_2)との各ビットの一致を判定するフルビットマッチ回路５０と、フルビットマッチ回路５０の出力とムーブインバッファMIB_0の有効ビットとの論理積を出力する論理積ゲート５２とを有する。
【００８５】
この回路により、ムーブイン要求が登録されているムーブインバッファのインデックスアドレスIDX_ADDとメモリアクセス要求MA_RQのインデックスアドレスIDX_ADDとが一致するか否かが判定される。フルビットマッチ回路５０は、例えば、２つの入力の対応するビットの排他的論理和（EOR）を出力するビット数分のEOR回路と、さらに、そのEOR回路の出力の論理積を出力するAND回路で構成される。したがって、フルビットマッチ回路５０の処理時間が相対的に長くなり、インデックスマッチ判定回路の判定結果が出力されるのに、図６の例では、２クロックサイクルを要している。
【００８６】
［リプレースWAY選択ユニット内のWAY使用状態判定回路WAY_JDG、全WAY使用判定回路ALL_WAY_JDG、リプレースWAY選択回路RPL_WAY_SEL］
図８のリプレースWAY選択ユニットRPL_SEL内のWAY使用状態判定回路WAY_JDGは、全ムーブインバッファMIBに登録中のムーブイン要求MI_RQのWAY（MI_WAY）をそれぞれデコードするn+1個のデコーダDECと、各インデックスマッチ判定回路IDX_MCH0-nの出力と各デコーダDECの出力それぞれの論理積を出力するAND回路AND0-nとを有する。
【００８７】
デコーダDECは、４つのWAYのWAY番号（二進数で00-11）をデコードして、４ビットのデコード信号を出力する。すなわち、デコーダDECは、リプレースWAY番号が「10」の場合に３番目がリプレースWAYであることを示すコード[0100]に変換する。したがって、４ビットのコードの「１」の位置がリプレースWAYの位置であることを示す。
【００８８】
次に、AND回路AND0-nは、各インデックスマッチ判定回路の判定出力IDX_MCH_JDG0-nが一致「１」であればデコーダDECの４ビット出力をそのまま出力し、不一致「０」であれば４ビット全て０のコード[0000]を出力する。
【００８９】
そして、WAY使用状態判定回路WAY_JDGは、1+n個のAND回路の４ビット出力それぞれの論理和を出力する論理OR回路WAY0-WAY3を有する。各論理OR回路WAY#は、AND回路の４ビット出力の対応するビットをn+1個入力し、それぞれの論理和であるWAY使用状態判定信号WAY_JDG_0−WAY_JDG_3を出力する。WAY使用状態判定信号WAY_JDG_0-WAY_JDG_3が「０」であれば未使用状態、「１」であれば使用状態であることを意味する。
【００９０】
図１０は、リプレースWAY選択ユニット内の全WAY使用判定回路ALL_WAY_JDGと、リプレースWAY選択回路RPL_WAY_SELの回路例を示す図である。
【００９１】
全WAY使用判定回路ALL_WAY_JDGは、図８のWAY使用状態判定回路WAY_JDGの４つの出力である、WAY使用状態判定信号WAY_JDG_0-WAY_JDG_3の論理積を全WAY使用判定信号ALL_WAYとして出力する論理積回路AND_10である。WAY使用状態判定回路WAY_JDGの４つの出力、WAY使用状態判定信号WAY_JDG_0-WAY_JDG_3が全て使用中「１」であれば、全WAY使用判定信号ALL_WAYは「１」となり、登録中のムーブイン要求が全WAYを使用中であることを示す判定結果が出力される。
【００９２】
リプレースWAY選択回路RPL_WAY_SELは、WAY使用状態判定回路WAY_JDGの４つの出力、WAY使用状態判定信号WAY_JDG_0-WAY_JDG_3と、LRU情報LRU_INFと、ムーブイン要求のインデックスに対応するタグメモリの４つのWAYの有効ビットValidと、全WAY使用判定信号ALL_WAYとを入力し、所定の論理演算により、リプレースWAYの番号RPL_WAYを出力する。
【００９３】
図１１は、リプレースWAY選択ユニットに関する動作を示すフローチャート図である。リプレースWAY選択ユニットRPL_SELは、LRU回路からLRU情報LRU_INFを入力し、タグメモリTAG_RAMからWAYの有効ビットを入力する（S20）。LRU回路は、各インデックスにおける４つのWAYのアクセス履歴に基づいて最も古くアクセスされたWAY番号をLRU情報として出力する。また、タグメモリは、４つのWAYそれぞれにキャッシュ登録されているか否かを有効ビットを有する。また、リプレースWAY選択ユニットは、ムーブインバッファから同一インデックスのムーブイン要求のWAY情報MI_WAYを入力する（S21）。
【００９４】
そして、全WAY使用判定回路ALL_WAY_JDGによる全WAY使用信号ALL_WAYが「１」の場合、同一インデックスのムーブイン要求が全WAYを使用中であり新たにムーブイン要求を発行できない。したがって、ムーブインバッファパイプライン制御回路がムーブインバッファ解放要求MIB_RLを発行し、確保されているムーブインバッファを解放する（S23）。
【００９５】
全WAY使用信号ALL_WAYが「０」で全WAYが使用中でない場合、リプレースWAY選択回路RPL_WAY_SELは、LRU情報LRU_INF、WAY使用状態判定信号WAY_JDG_0-3（W0-W3）、有効ビットValidから、新たに発行されるムーブイン要求が使用するWAY（リプレースWAY）を選択する（S24）。そして、リプレースWAY選択ユニットは、選択したリプレースWAYをムーブイン要求を登録するムーブインバッファMIBのWAYに登録し、L2キャッシュにリプレースWAY情報RPL_WAYを通知する（S25）。
【００９６】
［リプレースWAY選択ユニット内のリプレースWAY選択回路の真理値表］
図１２は、リプレースWAY選択回路の真理値表を示す図である。リプレースWAY選択ユニットRPL_SEL内のリプレースWAY選択回路RPL_WAY_SELは、前述のとおり、LRU情報LRU_INF、WAY使用状態判定信号WAY_JDG_0-3（W0-W3）、有効ビットValidを入力する。
【００９７】
そして、リプレースWAY選択回路は、第1に、L1キャッシュのTAGメモリの同一インデックスに無効なWAYがあり（有効ビットValid＝０）、ムーブインバッファを確保中のムーブイン要求が使用しないWAY（WAY使用状態判定信号WAY_JDG_0-3＝０）の場合、図中のケース１に示される真理値表に基づいてリプレースWAY（RPL_WAY）を選択する。
【００９８】
ケース１には、４つのWAY（W0,W1,W2,W3）について、TAGメモリの同一のインデックスで無効のWAYであり、且つムーブインバッファを確保中のムーブイン要求が使用しない獲得していないWAYという２つの条件を満たすWAYの組み合わせ（パターン１−１〜１−４）が示され、それぞれのパターンに対するリプレースWAY（RPL_WAY）が示される。
【００９９】
ケース１の真理値表に基づき、リプレースWAY選択回路は、２つの条件が満たされるWAYのうちいずれかのWAYをリプレースWAY（RPL_WAY）に選択する。TAGメモリで無効のWAYが存在しているので、LRU情報に基づく選択は行っていない。
【０１００】
なお、図中のケース１の真理値表は、若い番号のWAYを優先して選択している。例えば、パターン１−１では、２つの条件を満たすWAYがW0の場合、他のWAY（W1,W2,W3）にかかわらずリプレースWAYにW0を選択する。パターン１−２では、W0が２つの条件を満たさず、W1が満たす場合、他のWAY(W2,W3)にかかわらずリプレースWAYにW1を選択する。そして、ケース１−３，１−４も同様である。但し、大きい番号のWAYを優先して選択してもよいし、ランダムに選択しても良い。
【０１０１】
ケース１の場合、TAGメモリの無効なWAYには有効なデータが登録されていないので、L1キャッシュに対してそのデータをL2キャッシュに追い出すための追い出しオーダを実行する必要がない。したがって、２つの条件を満たすWAYは、ムーブイン要求がリプレースを行うことなく使用できるので、正確にはリプレースWAYではない。
【０１０２】
ケース１で２つの条件を満たすWAYをリプレースWAYに選択する理由は次のとおりである。同一のインデックスについてTAGメモリでは無効なWAYでも、ムーブインバッファでは発行中のムーブイン要求のWAYとして登録されている場合がある。例えば、TAGメモリでは無効なWAYが存在するが、先行するキャッシュミスしたメモリアクセス要求が同じWAYについてムーブインバッファを獲得済みの場合である。この場合、そのWAYをリプレースWAYには選択しない。
【０１０３】
第２に、L1キャッシュのTAGメモリの同一インデックスに無効なWAYがない場合、リプレースWAY選択回路は、図中ケース２に示される真理値表に基づいて、リプレースWAYを選択する。ケース２では、L1キャッシュのTAGメモリの同一インデックスの全てのWAYが有効データを登録している。したがって、リプレースWAYに対して追い出しオーダを実行する必要がある。そこで、ケース２では、リプレースWAY選択回路は、ムーブインバッファに登録中の同一インデックスのムーブイン要求が使用するWAY以外のWAY(ムーブインバッファを確保中のWAY以外のWAY)の中から、LRU情報に基づき最もアクセスが古いWAYをリプレースWAYに選択する。ムーブインバッファに登録中の同一インデックスのムーブイン要求が使用するWAY（ムーブインバッファを確保中のWAY）は、WAY使用状態判定信号WAY_JDG_0-3（W0-W3）が「１」のWAYである。
【０１０４】
ケース２では、４つのWAYについてムーブインバッファを確保中のWAYの１５種類の組み合わせ（パターン２−１〜２−１５）それぞれについて、参照すべきLRU真理値表[1]〜[11]（パターン２−１〜２−１１）、またはリプレースWAY（パターン２−１２〜２−１５）が示される。真理値表には、ムーブインバッファを獲得中のWAYは「１」で示され、WAY使用状態判定信号WAY_JDG_0-3（W0-W3）が「１」と同じである。したがって、ムーブインバッファを確保していないWAYは「０」で示される。
【０１０５】
パターン２−１〜２−１１は、ムーブインバッファを確保していないWAY「０」が複数個（３個または２個）あるケースである。この場合、リプレースWAY選択回路は、それぞれのLRU真理値表[1]〜[11]に示されるとおり、ムーブインバッファ未確保WAYのうち最もアクセスが古いWAY（LRUのWAY）をリプレースWAY（RPL_WAY）に選択する。一方、パターン２−１２〜２−１５は、ムーブインバッファ未確保WAYは1個しかないので、リプレースWAY選択回路は、LRU情報にかかわらず、ムーブインバッファ未確保WAYをリプレースWAYに選択する。
【０１０６】
パターン２−１６は、４つのWAY全てがムーブインバッファ確保中であり、この場合、全WAY使用判定回路ALL_WAY_JDGが全WAY使用信号ALL_WAYを出力する。
【０１０７】
［ムーブインバッファの制御例］
図１３は、本実施の形態におけるL1キャッシュのムーブインバッファ制御ユニットによるムーブインバッファ制御を示すタイミングチャート図である。図１３の前提として、全ての命令１−１１のインデックスアドレスADD_2はＡまたはＢであり、WAY数は４、L1キャッシュのTAGメモリには同一のインデックスにおいて無効のWAYは存在しておらず、ムーブインバッファMIBは１０個である。
【０１０８】
図１３には、２サイクル毎にL1キャッシュに投入される命令１−９と、その後４サイクル毎にL1キャッシュに投入される命令１０−１１が示される。命令発行部が発行する命令はロード命令であり、それに対応してメモリアクセス要求がL1キャッシュに投入される。また、図１３には、ムーブインバッファを確保した命令とWAY番号が示される。
【０１０９】
最初に、インデックスＡの命令１に対して、サイクル４でBステージに達し、MIB空き判定回路が空きムーブインバッファがあることを検出し、MIBパイプライン制御回路が、サイクル５のB1ステージでムーブインバッファ確保要求MIB_ENSを発行し、命令１に対して番号０のムーブインバッファMIBを確保する。さらに、同一インデックスＡのムーブイン要求はムーブインバッファに未登録であるので、B1ステージでムーブイン要求MI_RQがL2キャッシュに発行されている。このムーブイン要求の発行タイミングはムーブインバッファ制御ユニットに投入されてから２サイクル後と早い。さらに、番号０のムーブインバッファMIBにWAY=0が登録される。
【０１１０】
次のインデックスＢの命令２に対して、サイクル６でBステージに達し、MIB空き判定回路が空きムーブインバッファがあることを検出し、MIBパイプライン制御回路が、サイクル７のB1ステージでムーブインバッファ確保要求MIB_ENSを発行し、命令２に対して番号１のムーブインバッファMIBを確保する。さらに、同一インデックスＢのムーブイン要求はムーブインバッファに未登録であるので、B1ステージでムーブイン要求MI_RQがL2キャッシュに発行され、番号１のムーブインバッファMIBにWAY=0が登録される。命令２は、命令１のインデックスＡとは異なるインデックスＢであるので、命令２に対するムーブイン要求が使用するWAYを命令１と同じWAY=0としても問題はない。
【０１１１】
以下同様にして、インデックスＡの命令３，５，７は、番号２，４，６のムーブインバッファMIBを確保し、ムーブイン要求が使用するWAYはWAY=1,2,3となる。一方、インデックスＢの命令４，６，８は、番号３，５，７のムーブインバッファMIBを確保し、ムーブイン要求が使用するWAYはWAY=1,2,3となる。上記のインデックスＡの命令３，５，７は、既に同一のインデックスＡのムーブイン要求がムーブインバッファに登録済みであるので、それぞれのB4サイクルでムーブイン要求MI_RQが発行されている。インデックスＢの命令４，６，８も同様に、B4サイクルでムーブイン要求MI_RQが発行されている。
【０１１２】
次のインデックスＡの命令９は、一旦サイクル２１のB1ステージでムーブインバッファ確保要求MIB_ENSにより番号８のムーブインバッファMIBを確保する。ただし、同じインデックスＡのムーブイン要求が使用中のWAYが全WAYに達した為、サイクル２３のB3ステージで全WAY使用信号ALL_WAY=1となり、次のサイクル２４のB4ステージでムーブインバッファ解放要求MIB_RLにより、命令９が確保したムーブインバッファは解放される。
【０１１３】
次のインデックスＢの命令１０も、命令９と同様にして、一旦ムーブインバッファを確保するが、その後解放される。
【０１１４】
そして、インデックスＡの命令１１は、命令１が確保していた番号０のムーブインバッファが解放されたため、確保したムーブインバッファを解放されずにムーブイン要求が使用するWAYにWAY=0を選択されている。
【０１１５】
図１４は、連続する命令の処理を説明する図である。図１４の水平方向はクロックサイクル０−８を、垂直方向は連続する命令１−５を示し、各セル内には各命令のパイプラインステージB〜B4が示される。図１４により、図１３で命令１〜８が２クロックサイクル毎に処理された理由を説明する。
【０１１６】
命令１は、サイクル０で投入され、図６で説明したとおり、BステージでMIBの空き判定がされ、B1ステージでインデックスマッチ判定がされ、B2ステージでリプレース選択ユニットが、ムーブインバッファMIBからWAY情報MI_WAYを読み出し、B3ステージでリプレースWAY（RPL_WAY）を選択しムーブインバッファに登録される。したがって、ムーブインバッファは、B4ステージ以降に、B3で登録したリプレースWAY情報RPL_WAYが参照可能になる。
【０１１７】
命令２は、命令１の投入に続いてサイクル１で投入される。そのため、命令２のムーブインバッファからWAY情報MI_WAYを読み出すB2サイクルでは、命令１のリプレースWAY（RPL_WAY）のムーブインバッファへの登録は完了していない。そのため、命令２のB2ステージでムーブインバッファから読み出されるWAY情報MI_WAYには、命令１のリプレースWAYの登録が反映されていない。
【０１１８】
そこで、ムーブインバッファ制御ユニットは、命令２のB2ステージが命令１のB3ステージにあることを理由に、命令２をアボートしてリクエストポートに差し戻し滞留させる。これが、図１３で命令１〜９が２クロックサイクル毎に表示されている理由である。図１３において、先行する命令の１クロックサイクル後に投入された命令は、上記のとおりアボートされ滞留されるのである。
【０１１９】
上記の通り、本実施の形態によれば、キャッシュミスが発生すると、ムーブインバッファ制御ユニットが、Bステージで空きムーブインバッファが存在していれば、B1ステージでキャッシュミスしたメモリアクセス要求に投機的にムーブインバッファを確保する。そして、同一インデックスのムーブイン要求がムーブインバッファに登録中でなければ、B2ステージでムーブイン要求を発行する。これにより、同一のインデックスのムーブイン要求が登録中でない場合、短サイクルでムーブイン要求を発行できる。
【０１２０】
一方、同一インデックスのムーブイン要求がムーブインバッファに登録中であれば、同一インデックスのムーブイン要求が全てのWAYを使用中であるか否かの判定を待って、全てのWAYを使用中でなければ、B4ステージでムーブイン要求を発行する。ムーブイン要求が使用するWAYの選択がその後行われると、確保したムーブインバッファにその選択したWAY（リプレースWAY）を登録する。
【０１２１】
本実施の形態によれば、L1キャッシュミスしたメモリアクセス要求と同一インデックスのムーブイン要求がムーブインバッファに登録中であっても、同一インデックスのムーブイン要求が全てのWAYを使用中でなければ、未使用のWAYを使用するムーブイン要求をムーブインバッファに登録し、L2キャッシュに発行する。これにより、同時期に発行できるムーブイン要求の数を増やし、ムーブイン要求の処理を効率的に行うことができる。
【０１２２】
さらに、登録中のムーブイン要求と異なるインデックスのメモリアクセス要求に対しては、ムーブインバッファ制御ユニットへの投入後２クロック後のB2ステージでムーブイン要求を発行する。一方、登録中のムーブイン要求と同一のインデックスのメモリアクセス要求は、B4ステージでムーブイン要求を発行する。これにより、パイプラインステージを制御するクロック周波数を高くすることができる。前者のムーブイン要求の発行タイミングを早めることができる。
【０１２３】
以上の実施の形態をまとめると，次の付記のとおりである。
【０１２４】
（付記１）
メモリアクセス要求を発行するメモリアクセス要求発行部と、
タグメモリとデータメモリを有し、前記タグメモリとデータメモリ内の前記メモリアクセス要求のインデックスと一致するブロックにデータの状態とデータが登録されるキャッシュメモリと、前記メモリアクセス要求がキャッシュミスした場合に前記メモリアクセス要求のデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、前記ムーブイン要求の情報が登録される複数のムーブインバッファとを有するキャッシュとを有し、
前記ムーブインバッファ制御ユニットは、前記キャッシュミスしたメモリアクセス要求の入力に応答して、
（ａ）前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、
（ｂ）前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｃ）前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であることを検出し、更に、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全てのWAYを使用中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｄ）前記全てのWAYを使用中であることを検出すると、前記確保したムーブインバッファを解放し、前記ムーブイン要求の発行を抑止する、演算処理装置。
【０１２５】
（付記２）
前記ムーブインバッファ制御ユニットは、前記入力されたキャッシュミスしたメモリアクセス要求をクロックに同期して処理するパイプライン回路を有し、前記（ａ）、（ｂ）、（ｃ）、（ｄ）を順次実行する、付記１に記載の演算処理装置。
【０１２６】
（付記３）
前記複数のムーブインバッファのそれぞれには、前記ムーブイン要求の情報として、有効ビットと、前記メモリアクセス要求のインデックスと、前記ムーブイン要求に応答して返信されるデータ応答のデータを登録する前記キャッシュメモリ内のWAYと、前記データ応答のデータが記憶される、付記２に記載の演算処理装置。
【０１２７】
（付記４）
前記ムーブインバッファ制御ユニットは、前記複数のムーブインバッファ内に前記有効ビットが無効状態である前記空きムーブインバッファがあるか否かを判定する空き判定回路を有し、
前記空き判定回路が前記空きムーブインバッファを検出するとき、前記ムーブインバッファ制御ユニットは、前記空きムーブインバッファの前記有効ビットを有効にして前記メモリアクセス要求のためにムーブインバッファを確保し、さらに、確保したムーブインバッファに前記メモリアクセス要求のインデックスを登録する、付記３に記載の演算処理装置。
【０１２８】
（付記５）
前記ムーブインバッファ制御ユニットは、前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中か否かを判定するインデックスマッチ回路を有し、
前記インデックスマッチ回路が、前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行する、付記３に記載の演算処理装置。
【０１２９】
（付記６）
前記ムーブインバッファ制御ユニットは、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全WAYを使用中か否か判定し、更に全WAYを使用中でない場合未使用のWAYを検出するリプレースWAY検出回路を有し、
前記リプレースWAY検出回路が、前記全WAYを使用中でないことを検出すると、前記ムーブインバッファ制御ユニットは、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、前記未使用のWAYを前記確保したムーブインバッファに登録し、
前記リプレースWAY検出回路が、前記全WAYを使用中であることを検出すると、前記ムーブインバッファ制御ユニットは、前記確保したムーブインバッファを解放する、付記３に記載の演算処理装置。
【０１３０】
（付記７）
前記ムーブインバッファ制御ユニットは、前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であるか否かに係らず、前記メモリアクセス要求のためにムーブインバッファを確保する、付記１に記載の演算処理装置。
【０１３１】
（付記８）
メモリアクセス要求を発行するメモリアクセス要求発行部と、
タグメモリとデータメモリを有し、前記タグメモリとデータメモリ内の前記メモリアクセス要求のインデックスと一致するブロックにデータの状態とデータが登録されるキャッシュメモリと、前記メモリアクセス要求がキャッシュミスした場合に前記メモリアクセス要求のデータを要求するムーブイン要求を発行するムーブインバッファ制御ユニットと、前記ムーブイン要求の情報が登録される複数のムーブインバッファとを有するキャッシュとを有する演算処理装置の制御方法であって、
前記ムーブインバッファ制御ユニットは、前記キャッシュミスしたメモリアクセス要求の入力に応答して、
（ａ）前記複数のムーブインバッファに空きムーブインバッファがあることを検出すると、前記メモリアクセス要求のためにムーブインバッファを確保し、
（ｂ）前記メモリアクセス要求と同じインデックスである同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれにも登録中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｃ）前記同一インデックスを有するムーブイン要求が前記複数のムーブインバッファのいずれかに登録中であることを検出し、更に、前記複数のムーブインバッファのいずれかに登録中の前記同一インデックスを有するムーブイン要求がリプレースWAYとして全てのWAYを使用中でないことを検出すると、前記ムーブインバッファを確保したメモリアクセス要求のムーブイン要求を発行し、
（ｄ）前記全てのWAYを使用中であることを検出すると、前記確保したムーブインバッファを解放し、前記ムーブイン要求の発行を抑止する、処理を有する演算処理装置の制御方法。
【符号の説明】
【０１３２】
１０：Ｌ１キャッシュ
２０：Ｌ２キャッシュ
３：命令発行部
１１：リクエストポート
TLB：トランスレーション・ルックアサイド・バッファ
DATA_RAM, TAG_RAM：キャッシュメモリ
DATA RAM：データメモリ
TAG RAM：タグメモリ
LRU：LRU回路
MIB_CN：ムーブインバッファ制御ユニット
MIB：ムーブインバッファ
VALID:有効ビット
IDX_ADD：インデックスアドレス
DATA：データ
MA_RQ：メモリアクセス要求
MI_RQ：ムーブイン要求
IDX_MCH_JDG：インデックス判定回路
RPL_SEL：リプレースWAY選択ユニット
RPL_WAY_SEL：リプレースWAY選択回路
RPL_WAY：リプレースWAY
DATA_RSP：データ応答
EJ_OD：追い出しオーダ
WAY：ウエイ
【図１】
2019053390.tif 000003
【図２】
2019053390.tif 000004
【図３】
2019053390.tif 000005
【図４】
2019053390.tif 000006
【図５】
2019053390.tif 000007
【図６】
2019053390.tif 000008
【図７】
2019053390.tif 000009
【図８】
2019053390.tif 000010
【図９】
2019053390.tif 000011
【図１０】
2019053390.tif 000012
【図１１】
2019053390.tif 000013
【図１２】
2019053390.tif 000014
【図１３】
2019053390.tif 000015
【図１４】
2019053390.tif 000016