(57)【特許請求の範囲】
【請求項１】
情報を処理するためのコンピュータシステムにおけるオンチップ・キャッシュであって：
ヒットしたレコード・アドレスに応答して、少なくとも１つのキャッシュ出力レコードを、クロックサイクル数Ｌのアイドル期間の後で供給する多段式パイプライン・キャッシュを備え；
ヒットした非逐次レコード・アドレスに応答して少なくとも１つのレコードをアイドル期間中に供給する分岐目標キャッシュ（ＢＴＣ）を備え；
アイドル期間に先立つゼロサイクル中に、非逐次レコード・アドレス及びルックアヘッド・アドレスを、前記パイプライン・キャッシュに供給するルックアヘッド回路を備え、前記パイプライン・キャッシュでヒットした非逐次レコード・アドレス及びルックアヘッド・アドレスにそれぞれ応答して非逐次レコード及びルックアヘッド・レコードが、前記パイプライン・キャッシュからアイドル期間の後でそれぞれ出力され、前記ルックアヘッド・アドレスは、非逐次レコード・アドレスをＡ，イシュー幅をＷとして、Ａ＋（Ｌ×Ｗ）で示され；
非逐次アドレスがＢＴＣでミスであると前記パイプライン・キャッシュからの非逐次レコードを、非逐次アドレスがＢＴＣでヒットであるとルックアヘッド・レコードを、オンチップ・キャッシュの出力として選択するマルチプレクサを備えている、
ことを特徴とするオンチップ・キャッシュ。
【請求項２】
請求項１に記載のオンチップ・キャッシュにおいて、
ゼロサイクルの後に前記ルックアヘッド回路は、非逐次アドレスがＢＴＣでヒットであるときには、前記ルックアヘッド・アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、非逐次アドレスがＢＴＣでミスであるときには、前記非逐次アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、
前記パイプライン・キャッシュにおいて、前記ルックアヘッド回路から供給されてヒットした少なくとも１つの逐次レコード・アドレスに応じて、前記パイプライン・キャッシュは少なくとも１つのレコードを供給する
ことを特徴とするオンチップ・キャッシュ。
【請求項３】
情報を処理するためのコンピュータシステムにおけるオンチップ・キャッシュであって：
ヒットしたレコード・アドレスに応答して、少なくとも１つのキャッシュ出力レコードを、クロックサイクル数Ｌのアイドル期間の後で供給する多段式パイプライン・キャッシュを備え；
ヒットした非逐次レコード・アドレスに応答して少なくとも１つのレコードをアイドル期間中に供給する分岐目標キャッシュ（ＢＴＣ）を備え；
ルックアヘッド回路を備え、そのルックアヘッド回路は、非逐次レコード・アドレスがＢＴＣでヒットであればアイドル期間に先立つゼロサイクルにおいて、前記パイプライン・キャッシュにルックアヘッド・アドレスを供給し、前記パイプライン・キャッシュでヒットしたルックアヘッド・アドレスに応じてルックアヘッド・レコードが、当該アイドル期間の後に、前記パイプライン・キャッシュから供給され、そして、前記ルックアヘッド回路は、非逐次レコード・アドレスがＢＴＣでミスであればアイドル期間に先立つゼロサイクルにおいて、前記パイプライン・キャッシュに非逐次レコード・アドレスを供給し、前記パイプライン・キャッシュでヒットした非逐次レコード・アドレスに応じて非逐次レコードが、当該アイドル期間の後に、前記パイプライン・キャッシュから供給され、前記ルックアヘッド・アドレスは、非逐次レコード・アドレスをＡ，イシュー幅をＷとして、Ａ＋（Ｌ×Ｗ）で示され；
非逐次アドレスがＢＴＣでミスであると前記パイプライン・キャッシュからの非逐次レコードを、非逐次アドレスがＢＴＣでヒットであるとルックアヘッド・レコードを、オンチップ・キャッシュの出力として選択するマルチプレクサを備えている、
ことを特徴とするオンチップ・キャッシュ。
【請求項４】
請求項３に記載のオンチップ・キャッシュにおいて、
ゼロサイクルの後に前記ルックアヘッド回路は、非逐次アドレスがＢＴＣでヒットであるときには、前記ルックアヘッド・アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、非逐次アドレスがＢＴＣでミスであるときには、前記非逐次アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、
前記パイプライン・キャッシュにおいて、前記ルックアヘッド回路から供給された少なくとも１つの逐次レコード・アドレスに応じて、前記パイプライン・キャッシュは少なくとも１つのレコードを供給する
ことを特徴とするオンチップ・キャッシュ。
【請求項５】
コンピュータ・システムであって、
情報を処理するためのプロセッサと、
上記プロセッサに接続されたメモリ・デバイスと、
上記プロセッサに接続されたオンチップ・キャッシュと
を備え、このオンチップ・キャッシュは：
ヒットしたレコード・アドレスに応答して、少なくとも１つのキャッシュ出力レコードを、クロックサイクル数Ｌのアイドル期間の後で供給する多段式パイプライン・キャッシュを備え；
ヒットした非逐次レコード・アドレスに応答して少なくとも１つのレコードをアイドル期間中に供給する分岐目標キャッシュ（ＢＴＣ）を備え；
アイドル期間に先立つゼロサイクル中に、非逐次レコード・アドレス及びルックアヘッド・アドレスを、前記パイプライン・キャッシュに供給するルックアヘッド回路を備え、前記パイプライン・キャッシュでヒットした非逐次レコード・アドレス及びルックアヘッド・アドレスにそれぞれ応答して非逐次レコード及びルックアヘッド・レコードが、前記パイプライン・キャッシュからアイドル期間の後でそれぞれ出力され、前記ルックアヘッド・アドレスは、非逐次レコード・アドレスをＡ，イシュー幅をＷとして、Ａ＋（Ｌ×Ｗ）で示され；
非逐次アドレスがＢＴＣでミスであると前記パイプライン・キャッシュからの非逐次レコードを、非逐次アドレスがＢＴＣでヒットであるとルックアヘッド・レコードを、オンチップ・キャッシュの出力として選択するマルチプレクサを備えている
ことを特徴とする、コンピュータ・システム。
【請求項６】
請求項５に記載のコンピュータ・システムにおいて、
ゼロサイクルの後に前記ルックアヘッド回路は、非逐次アドレスがＢＴＣでヒットであるときには、前記ルックアヘッド・アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、非逐次アドレスがＢＴＣでミスであるときには、前記非逐次アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、
前記パイプライン・キャッシュにおいて、前記ルックアヘッド回路から供給されてヒットした少なくとも１つの逐次レコード・アドレスに応じて、前記パイプライン・キャッシュは少なくとも１つのレコードを供給する
ことを特徴とするコンピュータ・システム。
【請求項７】
コンピュータ・システムであって、
情報を処理するためのプロセッサと、
上記プロセッサに接続されたメモリ・デバイスと、
上記プロセッサに接続されたオンチップ・キャッシュと
を備え、このオンチップ・キャッシュは：
ヒットしたレコード・アドレスに応答して、少なくとも１つのキャッシュ出力レコードを、クロックサイクル数Ｌのアイドル期間の後で供給する多段式パイプライン・キャッシュを備え；
ヒットした非逐次レコード・アドレスに応答して少なくとも１つのレコードをアイドル期間中に供給する分岐目標キャッシュ（ＢＴＣ）を備え；
ルックアヘッド回路を備え、そのルックアヘッド回路は、非逐次レコード・アドレスがＢＴＣでヒットであればアイドル期間に先立つゼロサイクルにおいて、前記パイプライン・キャッシュにルックアヘッド・アドレスを供給し、前記パイプライン・キャッシュでヒットしたルックアヘッド・アドレスに応じてルックアヘッド・レコードが、当該アイドル期間の後に、前記パイプライン・キャッシュから供給され、そして、前記ルックアヘッド回路は、非逐次レコード・アドレスがＢＴＣでミスであればアイドル期間に先立つゼロサイクルにおいて、前記パイプライン・キャッシュに非逐次レコード・アドレスを供給し、前記パイプライン・キャッシュでヒットした非逐次レコード・アドレスに応じて非逐次レコードが、当該アイドル期間の後に、前記パイプライン・キャッシュから供給され、前記ルックアヘッド・アドレスは、非逐次レコード・アドレスをＡ，イシュー幅をＷとして、Ａ＋（Ｌ×Ｗ）で示され；
非逐次アドレスがＢＴＣでミスであると前記パイプライン・キャッシュからの非逐次レコードを、非逐次アドレスがＢＴＣでヒットであるとルックアヘッド・レコードを、オンチップ・キャッシュの出力として選択するマルチプレクサを備えている、
ことを特徴とするコンピュータ・システム。
【請求項８】
請求項７に記載のコンピュータ・システムにおいて、
ゼロサイクルの後に前記ルックアヘッド回路は、非逐次アドレスがＢＴＣでヒットであるときには、前記ルックアヘッド・アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、非逐次アドレスがＢＴＣでミスであるときには、前記非逐次アドレスに続く少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給し、
前記パイプライン・キャッシュにおいて、前記ルックアヘッド回路から供給された少なくとも１つの逐次レコード・アドレスに応じて、前記パイプライン・キャッシュは少なくとも１つのレコードを供給する
ことを特徴とするコンピュータ・システム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、キャッシュメモリを使用するデータ処理システムに関し、より詳しく、キャッシュの非逐次アクセスの実効待ち時間を短縮する技術に関する。
【０００２】
【従来の技術】
キャッシュは、主メモリに記憶された命令またはデータにプロセッサがアクセスするのに必要な実効時間を短くするために様々な形で使用される。キャッシュの理論は、大容量の比較的遅い主メモリと共に、非常に速いメモリの小さい部分をキャッシュとして使用することによって、コンピュータシステムはより高い処理速度を達成することができるというものである。キャッシュメモリは、動作上、データ処理装置と主メモリとの間に置かれる。プロセッサは、主メモリにアクセスする必要があるとき、まずキャッシュメモリを検索して、必要とする情報がキャッシュで利用可能可能かどうかを判断する。データ及びまたは命令を主メモリから取り出すときは、それらの情報は、主メモリの連続した記憶場所から取り出される情報ブロックの一部（キャッシュラインとして知られる）としてキャッシュに格納される。その後同じアドレスへのメモリアクセスを行うときは、プロセッサは、主メモリよりむしろ高速キャッシュメモリとやり取りする。統計的には、情報を主メモリの特定のブロックにアクセスして取り出したときは、次のアクセスではその同じブロックから情報を呼び出すことになる確立が非常に高い。このメモリー参照の局所性という性質があるために、平均メモリ・アクセスタイムは大幅に短縮される。
【０００３】
キャッシュの設計には、互いに相容れない主要な目標が２つのある。第１には、キャッシュ・サイズは、キャッシュミスの場合のオフチップメモリ・アクセスが最小限となるように、十分大きいことが望ましい。第２には、プロセッサが高速化するにつれて、システム全体の性能が遅くならないように命令及びデータをプロセッサへリターンすることができるよう、キャッシュを十分高速に設計することが特に重要になる。不都合なことに、キャッシュメモリは、大きくなるほど、寄生キャパシタンスの増加のために遅くなる。
【０００４】
これらの２つの目標を調和させるために、従来多くの技術が用いられている。キャッシュをあるタイプのデータ専用にすることによって、キャッシュに要求される相対的なサイズを小さくすることができる。例えば、多くのプロセッサには、命令キャッシュとデータキャッシュが別個に組み込まれている。さらに、命令キャッシュ用のアクセスのパターンは通常逐次式であるため、ヒット／ミス比が比較的高い。従って、命令を検索するのにオフチップにアクセスする必要が少なくなり、性能が高くなる。
【０００５】
キャッシュの速度の大きさには２つの要素が関与する。キャッシュの待ち時間は、キャッシュに対するアドレスの呈示と要求されたデータのキャッシュからの受取りとの間の遅延時間（通常プロセッサ・サイクルで測定される）である。キャッシュのスループットは、ある一定時間で実行することができるメモリアクセス動作の回数の尺度である。待ち時間中は、キャッシュは、アドレスに応答してキャッシュからデータがリターンされないアイドル期間を持っていると見なすことができる。アイドル期間の持続時間Ｌは、待ち時間より１サイクル短い。
【０００６】
パイプライン・メモリシステムでは、先取り法を用いてスループットを高くすることができるということは、当技術分野においては周知である。カリフォルニア州サンタクララのインテル社（Ｉｎｔｅｌ  Ｃｏｒｐｏｒａｔｉｏｎ  ｏｆ  Ｓａｎｔａ  Ｃｌａｒａ，  Ｃａｌｉｆｏｒｎｉａ）のＩｎｔｅｌ  ｉ９６０ＣＡTM及びｉ９６０ＣＦTMプロセッサは、パイプライン・メモリシステムをサポートするプロセッサの例である。特に、命令キャッシュは、例えば２段パイプライン・キャッシュとして実施することが可能である。パイプラインの第１段においては、命令アドレス（命令ポインタ）がキャッシュのタグアレイに呈示される。その結果は１サイクル間ラッチされ、第２段においては、ヒットの場合はキャッシュの命令アレイラインにアクセスし、キャッシュミスの場合はメモリにアクセスすることによりメモリアクセスが続けられる。言い換えると、例えば命令アドレスをサイクル１で呈示すると、キャッシュはサイクル２では待ち状態を取り、命令アドレスがキャッシュでヒットすれば、その命令がサイクル３でリターンされる。
【０００７】
上記のパイプライン・キャッシュの待ち時間は２サイクルである。しかしながら、実効待ち時間は、アイドル・サイクルの間に後続の逐次アドレスから命令を先取りすることによって１サイクル短縮することができる。サイクル２においては、命令シーケンサ（プログラムカウンタ）がフェッチすべき次の命令を指示するための命令ポインタをインクリメントし、そのポインタ・アドレスをキャッシュに呈示する。その結果、サイクル１で呈示されたアドレスで見付かった命令がサイクル３でリターンされ、次の命令はサイクル４でリターンされる。このようにして、キャッシュのスループットは、１サイクルおきに１命令から１サイクルごとに１命令へ１００パーセントの増加が達成されている。
【０００８】
当業者であれば、パイプライン・キャッシュの段数はシステムの要求に対応して広い範囲を取り得るということは理解できよう。さらに、当業者ならば、命令ポインタが各パイプライン段の間にインクリメントされる数は、プロセッサがスーパースカラ型（１サイクルにつき複数の命令を出す）であるかどうか、とりわけパイプライン段数によって変化するということは理解できよう。唯一必要なのは、前のサイクルでフェッチされた最後の命令の直後の命令を指示するように命令ポインタをインクリメントすることである。
【０００９】
パイプライン・キャッシュからの命令を逐次先取りする方法を用いると、命令スループットを比較的高く保つことが可能である。しかしながら、非逐次メモリアクセスになると、パイプライン・キャッシュは性能的な不利を被る。非逐次アクセスには、命令フローの変化の中でも、とりわけ分岐コール（呼出し）及び割込みなどがある。上に述べたように、命令シーケンサは、命令ポインタを逐次インクリメントすることによって命令を先取りさせる。しかしながら、分岐命令に遭遇すると、命令フローは、その分岐命令によって指定された目標アドレスへ転向されなければならない。プロセッサは、分岐命令を解読して分岐命令に遭遇したことを検知し、命令フローを継続する分岐目標アドレスを決定するために多くのサイクル数を必要とする。この期間中に、パイプライン・キャッシュは、分岐命令の直後の逐次命令フロー中にある先取りされた命令をリターンする。分岐が検出された後は、これらの先取りされた命令は、洗い流す、すなわち実行せずにパイプラインから排出しなければならず、かつ命令フローを分岐目標アドレスへ転向しなければならない。
【００１０】
分岐目標アドレスがパイプライン・キャッシュに呈示されると、そのアドレスにある命令がパイプライン・キャッシュの待ち時間に等しい期間後にリターンされる。典型的なコンピュータプログラムにおいては、おおよそ５命令毎に１つの割合で分岐命令が発生するので、この遅延は、命令スループットを大きく低下させる。このスループットの低下は、各待ち時間サイクルが１命令だけではなく多数の命令の遅延を表すスーパースカラ・マシンにおいては一層ひどくなる。
【００１１】
【発明が解決しようとする課題】
従って、非逐次メモリアクセスによって生じる実効待ち時間を短縮することによってパイプライン・キャッシュの性能を向上させることが要望されている。
【００１２】
【課題を解決するための手段】
上記目的達成のため、本発明は、非逐次メモリアクセスにおける実効待ち時間を短縮するための方法及び装置を提供するものである。本発明のキャッシュは、パイプライン・キャッシュでのレコード・アドレスのヒットに応答して少なくとも１つのキャッシュ出力レコードが得られる多段式パイプライン・キャッシュを有する。このパイプライン・キャッシュは、出力レコードを全く出さないＬクロックサイクルのアイドル期間後にレコードを出力する。本発明は、分岐目標キャッシュ（ＢＴＣ）でヒットした非逐次レコード・アドレスに応答してアイドル期間中に少なくとも１つのレコードを出すＢＴＣを設けることによってパイプライン・キャッシュの実効待ち時間を短縮するものである。このキャッシュは、さらに、アイドル期間に先行するゼロサイクルの間に非逐次レコード・アドレス（Ａ）及びルックアヘッド・アドレス（Ａ＋（Ｌ×Ｗ）、Ｗはレコードが出されるイシュー幅を示す）をパイプライン・キャッシュに供給するルックアヘッド回路を有する。パイプライン・キャッシュは、それぞれ、パイプライン・キャッシュでヒットした非逐次レコード・アドレス及びルックアヘッド・アドレスに応答して、アイドル期間の後にルックアヘッド・アドレスに応じてルックアヘッド・レコード及び非逐次レコードを出力する。非逐次レコードがＢＴＣでキャッシュミスになると、マルチプレクサが、パイプライン・キャッシュ中から出力として非逐次レコードを選択する。非逐次アドレスがＢＴＣでヒットしすると、マルチプレクサはルックアヘッド・レコードを出力として選択する。
【００１３】
もう一つの実施態様においては、ＢＴＣのタグヒット論理装置が十分に速い場合、非逐次アドレスがＢＴＣでヒットすると、ルックアヘッド回路はそのゼロサイクル中にルックアヘッド・アドレスのみをパイプライン・キャッシュに供給する。その場合、パイプライン・キャッシュは、パイプライン・キャッシュでヒットしたルックアヘッド・アドレスに応答して、アイドル期間の後にルックアヘッド・アドレスからルックアヘッド・レコードを出力する。一方、非逐次アドレスがＢＴＣでキャッシュミスを起こすと、ルックアヘッド回路は、そのゼロサイクル中に非逐次レコード・アドレスをパイプライン・キャッシュに供給する。パイプライン・キャッシュでヒットした非逐次アドレスに応答して、パイプライン・キャッシュは、アイドル期間の後にで非逐次レコードを出力する。
【００１４】
上記のどちらの態様においても、非逐次アドレスがＢＴＣでヒットすると、ルックアヘッド回路は、そのゼロサイクルの後に、ルックアヘッド・アドレスに続いて少なくとも１つの逐次レコード・アドレスをパイプライン・キャッシュに供給する。しかしながら、ＢＴＣで非逐次アドレスのキャッシュミスが起こると、ルックアヘッド回路は、そのゼロサイクルの後に、非逐次アドレスに続いて少なくとも１つの逐次レコードアドレスをパイプライン・キャッシュに供給する。ルックアヘッド回路によって供給された逐次レコード・アドレスのパイプライン・キャッシュでのヒットに応答して、パイプライン・キャッシュは、少なくとも１つのレコードを供給する。
【００１５】
マルチサイクル・アイドル期間の場合は、ＢＴＣは、アイドル期間の第１のサイクル中に、非逐次レコード・アドレスによって指定された非逐次レコードを出力する。アイドル期間の残りのサイクルにおいては、ＢＴＣは、非逐次レコード・アドレスに続く逐次レコード・アドレスから逐次レコードを出力する。イシュー幅Ｗを有するスーパースカラ・システムの場合は、ＢＴＣは、アイドル期間の各サイクル中にＷ個のレコードを出力する。
【００１６】
アイドル期間の後、パイプライン・キャッシュは、前のサイクル中にＢＴＣによって出された最後のレコードのレコード・アドレスに続く逐次レコード・アドレスから少なくとも１つの逐次レコードを出力する。しかしながら、ＢＴＣがアイドル期間中にレコードを出力しないと、パイプライン・キャッシュは、パイプライン・キャッシュでヒットした非逐次レコード・アドレスに応答して、アイドル期間の後に非逐次レコードを出力する。
【００１７】
好ましくは、キャッシュに記憶されるレコードは命令を表すレコードとする。非逐次レコード・アドレスは、例えば、分岐命令の目標アドレス、割込みハンドラの開始アドレス、あるいはサブルーチンのコールまたは戻りアドレス（復帰アドレス）である。
【００１８】
以下、本発明を実施例について図面を参照しつつ詳細に説明する。
【００１９】
【実施例】
本発明によれば、非逐次アクセスにおける実効待ち時間が短いパイプライン・キャッシュシステムが得られる。以下の説明においては、本発明の完全な理解を図るために、詳細な事項が特定的に記載してある。しかしながら、本発明がこれらの詳細な事項の記載なしで実施可能なことは当業者にとって明白であろう。また、その他の場合においては、前記シーケンサ、その他の周知の素子、装置、プロセス・ステップ等は、本発明が不明確になるのを避けるため、詳細な記載は省略した。
【００２０】
図１は、本発明のパイプライン・キャッシュのアーキテクチャを示すブロック図である。プロセッサチップ１００は、ＣＰＵコア１０２及び本発明のオンチップ命令キャッシュ１０４を有する。
【００２１】
命令キャッシュ１０４は、メモリバス１０８を介してメモリデバイス１０６に接続されている。当業者であれば、発明の説明が不必要に複雑になるのを避けるために、図１ではバスコントローラやデータキャッシュのような多数の接続や構成部品が省略されているということは理解できよう。命令キャッシュ１０４は、ルックアヘッド制御回路１１０、分岐目標命令キャッシュ１１２、パイプライン・キャッシュ１１４及びマルチプレクサ（ＭＵＸ）１１６を有する。パイプライン・キャッシュ１１４は、ＣＰＵコア１０２によって使用されるレコードの一種である命令を記憶する。このキャッシュは何段にでもパイプライン化することができる。分岐目標命令キャッシュ（ＢＴＩＣ）１１２は、分岐、コール、リターン及びその他の非逐次アクセスのために専用に用いられる小さな高速キャッシュである。このＢＴＩＣは、これらの１つの動作から生じるアドレスがプロセッサコア１０２によって送られたときだけアクティブになる。このＢＴＩＣの目的は、非逐次アクセスのためにパイプライン・キャッシュに生じる待ち時間を埋めることにある。
【００２２】
ルックアヘッド制御（ＬＡＣ）回路１１０は、パイプライン・キャッシュ１１４に与えるアドレスを制御する。ＣＰＵコア１０２は、非逐次アクセスを実行しようとするとき、アドレスを命令キャッシュ１０４に呈示する。他のサイクル中に、アイドル期間中にＣＰＵコア１０２により消費された命令語の数だけ前回の命令ポインタをインクリメントして、前記キャッシュに対するアドレスがＬＡＣ１１０から生成される（ワード・バイ・ワードアドレス指定であると仮定した場合）。非逐次アクセスに遭遇すると、ＣＰＵコア１０２からのブランチ・アドレスがＢＴＩＣ１１２に与えられて、分岐目標アドレスの命令がＢＴＩＣ１１２に格納されているかどうかの判断が行われる。同時に、ルックアヘッド制御装置１１０は、分岐目標アドレスＡとルックアヘッド・アドレスＡ＋Ｎを共にパイプライン・キャッシュ１１４に与える。数Ｎは、ＣＰＵコア１０２がアイドル期間中に消費する命令の数によって決まる。例えば、パイプライン・キャッシュ１１４が２サイクルの待ち時間（すなわち、アイドル期間Ｌ＝１サイクル）で、ＣＰＵコア１０２がイシュー幅（issue width ）Ｗが３のスーパースカラ・プロセッサであるとすると、ルックアヘッド装置１１０はＮ＝３命令だけ先取りする。一般に、アイドル期間中にＢＴＩＣ１１２によってＣＰＵコア１０２に与えられる「充填（fill-in ）」命令の数Ｎは、次式に従って計算される。
Ｎ＝Ｌ×Ｗ
【００２３】
ＢＴＩＣ１１２は、ヒットすると、ＣＰＵコア１０２が必要とする命令をアイドル期間中に出力する。アイドル期間に続いて、パイプライン・キャッシュ１１４は後続の命令を出す（それらがパイプライン・キャッシュ１１４中にある場合）。一方、ＢＴＩＣ１１２でキャッシュミスが起こると、ＢＴＩＣ１１２によっては命令が全く与えられず、プロセッサはそのアイドル期間にわたって立ち往生（機能停止）する。アイドル期間が終わった後、分岐目標アドレスの命令がパイプライン・キャッシュ１１４によってＣＰＵコア１０２に供給され、ＢＴＩＣ１１２に格納される。これはそれらの命令がパイプライン・キャッシュ１１４に格納されている場合である。一方、命令がパイプライン・キャッシュ１１４にない場合は、それらの命令は外部メモリ１０６からＣＰＵコア１０２に供給され、ＢＴＩＣ１１２及びパイプライン・キャッシュ１１４に格納される。本発明は、分岐目標アドレスに関連して説明するが、当業者であれば、本発明の動作はサブルーチンコール及び戻りアドレス、割込みハンドラ・アドレス及びその他の非逐次アクセス・アドレスにも同様に適用であるということは理解できよう。さらに、本発明は、命令キャッシュばかりでなく、あらゆる形の情報レコードを保持するキャッシュに適用することができる。
【００２４】
以下、本発明の命令キャッシュの動作を、図２及び３のタイミング図を参照しつつさらに詳細に説明する。図２及び３に例示するシステムにおいては、この実施例は、スカラ・プロセッサにおける２段パイプライン・キャッシュであると仮定する（イシュー幅は１に等しい）。図２に示すように、ＣＰＵコア１０２とキャッシュ１０４の間では多数の信号がやり取りされる。分岐信号（能動ハイ）は、ＣＰＵコア１０２が非逐次アクセスを要求していることを示す。また、ＣＰＵコア１０２は、非逐次アクセス、例えば分岐の目標アドレスＡをルックアヘッド制御装置１１０及び分岐目標命令キャッシュ１１２に与える。ＣＰＵ＿ＲＥＡＤＹ信号は、それがハイのとき、ＣＰＵが情報を処理することができる状態にあるということを示し、逆に、ＣＰＵ＿ＲＥＡＤＹ信号がローに落ちたときは、ＣＰＵが機能停止しなければならないということを示す。
【００２５】
図２に示すように、ＣＰＵコア１０２は、サイクル０で分岐目標アドレスＡを出している。パイプライン・キャッシュ１１４は２サイクルの待ち時間を呈するので、ルックアヘッド制御回路１１０は、アドレスＡ及びルックアヘッド・アドレスＡ＋Ｎ＝Ａ＋（Ｌ×Ｗ）＝Ａ＋（１×１）＝Ａ＋１（ＬＡＣ＿ＯＵＴ）を出す。図２の例においては、サイクル０におけるハイのＢＴＩＣ＿ＨＩＴ線によって示されるように、アドレスＡがＢＴＩＣ１１２でヒットする。ＢＴＩＣ１１２は比較的高速のパイプライン・キャッシュであるため、サイクル１でアドレスＡの命令Ｉ［Ａ］をリターンする。このようにして、ＢＴＩＣ１１２は、サイクル１においてパイプライン・キャッシュ１１４のアイドル期間を埋める。
【００２６】
ＢＴＩＣヒットに応答して、ＭＵＸ１１６は、命令Ｉ［Ａ］を選択し、ＣＰＵコア１０２へ出力する（ＭＵＸ＿ＯＵＴ）。パイプライン・キャッシュ１１４はデュアルポートであるため、２つのアドレスを与えられると、２つの対応する命令を出力することができるようになっている。この例の場合、サイクル２において、パイプライン・キャッシュ１１４（ＰＣ＿ＯＵＴ）は、ＬＡＣ１１０によりサイクル０で呈示されたアドレスに応答して、２サイクルの待ち時間後にアドレスＡ及びＡ＋１の命令をリターンする。サイクル２においては、前のサイクルでＢＴＩＣヒットが検出されているので、ＭＵＸ１１６は、パイプライン・キャッシュ１１４の出力からアドレスＡ＋１の命令のみを選択する。サイクル０の後の各サイクルについてはこの例の場合、ＣＰＵコア１０２は他に分岐目標アドレスを呈示していない。このように、これら後続のサイクルにおいては、ＬＡＣ１１０は、通常のように動作して、Ａ＋２、Ａ＋３等の逐次ルックアヘッド・アドレスを出力する。通常の２サイクルの待ち時間の後、パイプライン・キャッシュ１１４は、ＬＡＣ１１０によってアドレスＡ＋２を呈示されてからそのアドレスの命令を出力する（パイプライン・キャッシュ１１４でヒットした場合）。命令が通常のように逐次処理される間は、ＭＵＸ１１６は、パイプライン・キャッシュ１１４の出力を選択して、命令をＣＰＵコア１０２に供給する。ここで、ＣＰＵ＿ＲＥＡＤＹの線がローになって、ＣＰＵ機能停止を示していることが図から分かる。この場合、ＣＰＵコア１０２は命令処理を延期しなければならない。このようにして、パイプライン・キャッシュ１１４は、アドレスＡ＋２の命令の出力を続け、ＬＡＣ１１０は、サイクル４で機能停止が解除されるまでＡ＋３のルックアヘッド・アドレスを出し続ける。
【００２７】
図３は、ＢＴＩＣミスの場合を示す。キャッシュミスが起こった場合、ＢＴＩＣ１１２は、サイクル１にアドレスＡからの命令を入れることができない。その代りに、２サイクルの待ち時間の後、ＭＵＸ１１６は、パイプライン・キャッシュ１１４の出力から命令Ｉ［Ａ］を選択する（パイプライン・キャッシュでヒットした場合）。パイプライン・キャッシュ１１４が命令をリターンするとき、その命令はＣＰＵコア１０２に供給されるばかりでなく、以後におけるメモリアクセスのためにＢＴＩＣ１１２にも格納される。また、ＬＡＣ１１０は、サイクル０でキャッシュミスが検出されると、これに応答して、サイクル１でルックアヘッド・アドレスＡ＋１を繰り返し、その結果、パイプライン・キャッシュ１１４はアドレスＡ＋１の命令をリターンする（パイプライン・キャッシュ１１４でヒットが起こった場合）。また、図３には、図２と同様の機能停止の効果も示されている。
【００２８】
もう一つの実施例においては、ＢＴＩＣ１１２のタグヒット論理装置は、ルックアヘッド制御１１０の動作を変えるのに十分な速度で反応することができる。例えば、図２においては、ＬＡＣ１１０は、パイプライン・キャッシュ１１４に分岐目標アドレスＡ及びルックアヘッド・アドレスＡ＋１を共に出力しなければならない。サイクル０では、ＬＡＣ１１０は、ＢＴＩＣでヒットが生じるか（パイプライン・キャッシュはＩ［Ａ＋１］のみ出力すればよい）、キャッシュミスが起こるか（この場合パイプライン・キャッシュ１１４はＩ［Ａ］とＩ［Ａ＋１］を共に出力する必要がある）が不確かである。しかしながら、ＢＴＩＣ１１２がルックアヘッド制御回路１１０にサイクル０でのヒットを通知するのに十分速ければ、ＬＡＣ１１０は、分岐アドレスとルックアヘッド・アドレスを両方とも出力すべきかどうか、あるいはルックアヘッド・アドレスだけ出力すべきかを決定することができるはずである。ヒットの場合は、Ｉ［Ａ］がＢＴＩＣ１１２中にあることが分かり、従ってアドレスＡをパイプライン・キャッシュ１１４に呈示する必要がない。そして、ＬＡＣ１１０は、ルックアヘッド・アドレスＡ＋１のみをパイプライン・キャッシュ１１４に呈示する。このような高速のＢＴＩＣは、例えば、図２において、ＢＴＩＣ＿ＨＩＴ信号を左へ移動させ、ＬＡＣ＿ＯＵＴ信号がアサートされる（立ち上がる）前に論理ハイレベルに達するようにすることにより表すことができる。
【００２９】
同様にＢＴＩＣでキャッシュミスが起こった場合は、パイプライン・キャッシュ１１４がＢＴＩＣ１１２の代りにサイクル２でＩ［Ａ］を出力する動作を受け持つことになるから、ＬＡＣ１１０は分岐目標アドレスＡをパイプライン・キャッシュ１１４に呈示しさえすればよいということが分かる。以後のサイクルでは、非逐次アクセスがなければ、通常の逐次動作が続けられる。
【００３０】
以上の説明では、パイプライン・キャッシュ１１４は何らかのアドレスが呈示されたとき、これに応答して生じたヒットを記録するものと仮定した。もちろん、アドレスがＢＴＩＣ１１２でもパイプライン・キャッシュ１１４でもキャッシュミスになった場合は、プロセッサは所望の命令が主メモリ１０６からリターンされるまで不定数の待ち状態を経る必要がある。その命令は、リターンされると同時にパイプライン・キャッシュ１１４にもＢＴＩＣ１１２にも格納される。
【００３１】
図４及び５は、スカラ・プロセッサ１００で実施された４段パイプライン・キャッシュ１１４（アイドル時間＝３サイクル）の場合のＢＴＩＣのヒットとＢＴＩＣのキャッシュミスの結果をそれぞれ示すタイミング図である。サイクル０においては、ルックアヘッド制御回路１１０が分岐目標アドレスＡ及びルックアヘッド・アドレスＡ＋Ｎ（ただしＮ＝３）をパイプライン・キャッシュ１１４に呈示する。ルックアヘッド・アドレスＡ＋３＝Ａ＋（Ｌ×Ｗ）＝Ａ＋（３×１）（スカラ・プロセッサの場合）＝Ａ＋３。あるいは、図２と３に関連して説明したしように、ＬＡＣ１１０がルックアヘッド・アドレスをパイプライン・キャッシュ１１４へ出力する前にヒットかキャッシュミスかをルックアヘッド制御回路１１０に示すことができるほどＢＴＩＣのタグヒット論理装置が十分高速であれば、ルックアヘッド制御回路１１０はＢＴＩＣヒットの場合はルックアヘッド・アドレスのみ、ＢＴＩＣミス（キャッシュミス）の場合は分岐目標アドレスのみを出力するだけでよい。
【００３２】
この例においては、アイドル期間は３サイクルであり、このことは、パイプライン・キャッシュ１１４は、サイクル０で呈示されたアドレスに応答してサイクル１、２または３中に命令をリターンするということを行わないということを意味する。パイプライン・キャッシュ１１４の性能は、このアイドル期間にＢＴＩＣ１１２によって供給される命令を充填することによって強化することができる。この場合、ＢＴＩＣヒットが起こると、ＢＴＩＣ１１２は、ＣＰＵコア１０２から受け取った分岐目標アドレスに応答してサイクル１、２と３中に命令Ｉ［Ａ］、Ｉ［Ａ＋１］とＩ［Ａ＋２］をそれぞれ出力する。マルチプレクサ１１６は、ＢＴＩＣヒットが起こった場合の３サイクルのアイドル期間中はＢＴＩＣ１１２の命令出力を選択する。アイドル期間が経過した後は、マルチプレクサ１１６はパイプライン・キャッシュ１１４の出力を選択する。
【００３３】
分岐目標アドレスＡがＢＴＩＣ１１２でキャッシュミスになると、４サイクル待ち時間のために、そのアドレスの命令は、サイクル４まではパイプライン・キャッシュ１１４によってリターンされない（パイプライン・キャッシュでヒットした場合）。
【００３４】
本発明は、通常アイドル期間になるような処理時間を埋めるための非逐次アクセス専用に用いられる小さな高速キャッシュを使用する。この性能強化は、各アイドル・サイクルで、１つの命令だけではなく、多くの命令を出す機会が失われるスーパースカラ・システムにおいてとりわけ有用である。そのようなアイドル時間によって通常生じる性能の低下は、１サイクルより長い待ち時間を有する多段式のパイプライン・キャッシュを使用する場合にさらに顕著になる。従って、このようなアイドル時間を全て埋めることができる本発明は、従来技術に対して著しい改善効果をもたらすものである。
【００３５】
以上、本発明を特定実施例により詳細に説明したが、当業者にとって、発明の要旨及び範囲を逸脱することなく、様々な修正態様及び変更態様が可能なことは明白であろう。特に、上記説明から、本発明は任意の範囲のイシュー幅を有するスカラのプロセッサでもスーパースカラでも動作する任意の段数を有するパイプライン・キャッシュに適用可能であるということは明らかであろう。
【００３６】
【発明の効果】
本発明によれば、非逐次メモリアクセスによって生じる実効待ち時間を短縮することによってパイプライン・キャッシュの性能を向上させることができる。
【図面の簡単な説明】
【図１】  本発明のキャッシュを組み込んだコンピュータシステムを示すブロック図である。
【図２】  本発明をスカラ・プロセッサにおける２段パイプライン・キャッシュに適用した場合に、非逐次レコード・アクセスが分岐目標キャッシュでヒットした場合の一例の動作を説明するためのタイミング図である。
【図３】  本発明をスカラ・プロセッサにおける２段パイプライン・キャッシュに適用した場合に、非逐次レコード・アクセスが分岐目標キャッシュでキャッシュミスを起こした場合の一例の動作を説明するためのタイミング図である。
【図４】  本発明をスカラ・プロセッサにおける４段パイプライン・キャッシュに適用した場合に、非逐次レコード・アクセスが分岐目標キャッシュでヒットした場合の動作を説明するためのタイミング図である。
【図５】  本発明をスカラ・プロセッサにおける４段パイプライン・キャッシュに適用した場合に、非逐次レコード・アクセスが分岐目標キャッシュでキャッシュミスを起こした場合の一例の動作を説明するためのタイミング図である。
【符号の説明】
１００…プロセッサチップ、１０２…ＣＰＵコア、１０４…命令キャッシュ、１０６…メモリデバイス、１０８…メモリバス、１１０…ルックアヘッド制御回路、１１２…分岐目標命令キャッシュ、１１４…パイプライン・キャッシュ、１１６…マルチプレクサ。
【図１】
0003732555.tif 000002
【図２】
0003732555.tif 000003
【図３】
0003732555.tif 000004
【図４】
0003732555.tif 000005
【図５】
0003732555.tif 000006