(57)【特許請求の範囲】
【請求項１】
（ａ）各命令が、複数の命令のうちの１つが実行された後に実行すべき予測される次の命令を識別する内部に埋め込まれた履歴データを含む、複数の命令を記憶するメモリと、
（ｂ）メモリと結合され、メモリに記憶されている第１の命令を実行するように構成された、少なくとも１つの実行ユニットと、
（ｃ）実行ユニットによって第１の命令が実行されるのと並行して、第１の命令の履歴データによって識別される予測される次の命令の、メモリからの検索を開始するように構成されたプリフェッチ回路とを備え、
（ｄ）各命令についての履歴アドレス・インデックスが命令の最後のパーセルに記憶され、
（ｅ）複数の命令がそれぞれ、複数のパーセルを含むVery Long Word Instruction（ＶＬＩＷ）であり、この命令に関する履歴データが少なくとも１つのパーセルに記憶され、
（ｆ）複数の命令内の各命令が、その最後のパーセルとして、ＮＯＯＰパーセルと分岐パーセルの一方を含み、
（ｇ）最後のパーセルとして分岐パーセルを有する場合の任意の命令が第２の分岐パーセルを含み、任意の所与の命令中の分岐パーセルが、メモリ内の同じキャッシュ・ラインに分岐する分岐先アドレスを含み、それによって、最後のパーセル中の分岐パーセル用の分岐先アドレスがその履歴アドレス・インデックスで置き換えられる、回路。
【請求項２】
メモリが一次命令キャッシュおよび二次命令キャッシュを含み、プリフェッチ回路が、第１の命令中の履歴アドレス・インデックスを使用して二次キャッシュにアドレスすることにより、第１の命令の履歴データによって識別される予測される次の命令の検索を開始するように構成され、二次命令キャッシュが、履歴アドレス・インデックスを受け取ったことに応答して、一次命令キャッシュのアクセス時間よりも長いＮサイクルのアクセス時間を有する請求項１に記載の回路。
【請求項３】
第１の命令に関する履歴データが、第１の命令からＮサイクル後に実行すべき第２の命令の予測される次の命令を識別する請求項２に記載の回路。
【請求項４】
プリフェッチ回路がさらに、実行ユニットによる予測される次の命令の実行を開始するように構成され、回路がさらに、
（ａ）第２の命令の後で実行される予測される次の命令および実際の次の命令のアドレスを比較し、予測される次の命令のアドレスと実際の次の命令のアドレスが一致しない場合に実行ユニットによる予測される次の命令の実行を終了するように構成された予測検証回路と、
（ｂ）第２の命令の後で実行される実際の次の命令のアドレスに関連付けされたアドレス・インデックスを第１の命令に関する履歴データとして記憶するように構成された履歴更新回路とを備える請求項３に記載の回路。
【請求項５】
実行ユニットが、複数の段を備える実行パイプを備え、一次命令キャッシュが、データ入力に供給されたアドレス・インデックスをアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路が、実行パイプの複数の段のうちの１つの段内の命令レジスタを書込みアクセス・ポートのデータ入力と電気的に結合する１組のデータ線と、実行パイプの複数の段のうちの他の段内のアドレス・レジスタを書込みアクセス・ポートのアドレス入力と電気的に結合する１組のアドレス線とを備え、１組のデータ線が結合される段が、１組のアドレス線が結合される段からＮサイクルだけずれる請求項４に記載の回路。
【請求項６】
実行ユニットが、複数の段を備える実行パイプを備え、一次命令キャッシュが、データ入力に供給されたアドレス・インデックスをアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路がさらに、実行パイプと一次命令キャッシュの間に挿入されたセレクタ回路を備え、セレクタ回路が、書込みアクセス・ポートのデータ入力とアドレス入力の少なくとも一方を実行パイプの様々な段と選択的に結合し、セレクタ入力に応答して、第２の命令の予測される次の命令を命令履歴キャッシュ内で命令１個分以上、制御可能にずらすように構成される請求項４に記載の回路。
【請求項７】
一次キャッシュ内の各命令に、その命令に関連する履歴データが変更されたかどうかを示す変更インディケータが関連付けられ、回路がさらに、予測される次の命令のアドレスと実際の次の命令が一致しない場合に第１の命令用の変更インディケータをセットするように構成されたアドレス比較ブロックを備える請求項４に記載の回路。
【請求項８】
さらに、一次命令キャッシュおよび二次命令キャッシュと結合されたキャストアウト・コントローラを備え、キャストアウト・コントローラが、第１の命令用の変更インディケータがセットされたときに一次命令キャッシュ内の第１の命令のコピーが置き換えられることに応答して二次命令キャッシュ内の第１の命令のコピーに関する履歴データを更新するように構成される請求項７に記載の回路。
【請求項９】
請求項１の回路を備えるデータ処理システム。
【請求項１０】
請求項１の回路を構成させるため、ハードウェアを制御して前記回路として機能させるプログラムを記録した、コンピュータ読取可能な記録媒体。
【請求項１１】
命令を推測的に取り出す方法であって、
（ａ）複数の命令のうちの１つが実行された後に実行すべき予測される次の命令を識別する内部に埋め込まれた履歴データを含む、メモリに記憶されている複数の命令のうちの第１の命令を実行するステップと、
（ｂ）第１の命令を実行することに並行して、第１の命令の履歴データによって識別される予測される次の命令のメモリからの検索を開始するステップとを含み、
（ｃ）各命令についての履歴アドレス・インデックスが命令の最後のパーセルに記憶させるステップと、
（ｄ）複数の命令それぞれを、複数のパーセルを含むVery Long Word Instruction（ＶＬＩＷ）とし、この命令に関する履歴データが少なくとも１つのパーセルに記憶させるステップと、
（ｅ）複数の命令内の各命令に対して、その最後のパーセルとして、ＮＯＯＰパーセルと分岐パーセルの一方を含ませるステップと、
（ｆ）最後のパーセルとして分岐パーセルを有する場合の任意の命令が第２の分岐パーセルを含ませるステップと、
（ｇ）任意の所与の命令中の分岐パーセルに対して、メモリ内の同じキャッシュ・ラインに分岐する分岐先アドレスを含ませるステップと、
（ｈ）最後のパーセル中の分岐パーセル用の分岐先アドレスがその履歴アドレス・インデックスで置き換えるステップと
により生成させる、命令を推測的に取り出す方法。
【請求項１２】
請求項１１の方法をコンピュータに対して実行させるためのコンピュータ実行可能なプログラムを記憶したコンピュータ読取可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全般的には集積回路デバイスのアーキテクチャおよび設計に関し、詳細にはプロセッサ集積回路デバイスにおける分岐予測に関する。
【０００２】
【従来の技術】
コンピュータなどのデータ処理システムのユーザは、ますます複雑にかつ困難になるタスクを処理するために、引き続きこのようなシステムにより高い性能を要求している。このようなシステムを操作するプロセッサのより高い性能は、クロック速度を高め、それによって個々の命令をより高速に処理することによって得ることができる。しかし、複数の命令を互いに並列に実行することによって比較的高い性能利得が達成されている。
【０００３】
「パイプライン処理」と呼ばれる並列処理方法があり、この方法では、命令は、それを並列に処理する必要のある様々な動作を実行するプロセッサ内の実行ユニット用のパイプラインに供給される。たとえば、典型的な命令を処理する場合、パイプラインは、メモリから命令を取り出し、命令を実行し、命令の結果を再びメモリに書き込む別々の段を含むことができる。したがって、命令シーケンスがパイプラインに順次供給される場合、第１の命令の結果がパイプラインの第３段によって再びメモリに書き込まれるときに、次の命令が第２段によって実行され、しかも次の命令が第１段によって取り出される。個々の各命令を処理するのに数クロック・サイクルかかることがあるが、他の命令も同時に処理されるので、プロセッサの全体的なスループットはずっと高くなる。
【０００４】
プロセッサ内で複数の実行ユニットを使用して複数の命令を並列に実行することを試みることによって、より高度な並列処理を実行することもできる。複数の実行ユニットを含むプロセッサをしばしば「スーパースカラ」プロセッサと呼び、このようなプロセッサはスケジューリング回路を含む。スケジューリング回路は、できるだけ多くの命令が同時に処理されるように命令を様々な実行ユニットに効率的にディスパッチすることを試みる。しかし、１つの命令を、別の命令が完了するまで処理できないことが多いので、多くの場合、比較的複雑な意思決定回路が必要とされる。たとえば、第１の命令がメモリからの値をレジスタにロードし、第２の命令がレジスタの内容に一定の数を加える場合、第２の命令は通常、第１の命令の実行が完了するまで実行できない。
【０００５】
比較的複雑なスケジューリング回路を使用すると、集積回路デバイス上の顕著な量の回路が占有され、プロセッサの全体的な実行速度が低下する可能性がある。このため、ＶＬＩＷプロセッサに対して顕著な開発作業が実施されている。このようなプロセッサでは、どの命令が並列に処理できるかに関する決定は、実行中ではなくプログラムの作成時に下される。ＶＬＩＷプロセッサは通常、複数の実行ユニットを含み、各ＶＬＩＷ命令は、パーセルと呼ばれる複数のプリミティブ命令を含み、パーセルは互いに同じ時間に実行できることが知られている。したがって、ＶＬＩＷ内の各プリミティブ命令は、スケジューリングに関連する余分なオーバヘッドなしに１つの実行ユニットに直接ディスパッチすることができる。ＶＬＩＷプロセッサは、コンピュータ・ユーザによって書かれたコンピュータ・プログラム用の適切なＶＬＩＷ命令を生成するために、コンパイラと呼ばれる高度なコンピュータ・プログラムを利用する。ＶＬＩＷプロセッサは通常、命令の実行のスケジューリングに関連するオーバヘッドがない場合、スーパースカラ・プロセッサよりも簡単で効率的である。
【０００６】
プロセッサの種類にかかわらず、コンピュータの性能に関する他の問題は、プロセッサとメモリの間の情報の転送に関する問題である。特に、処理速度は、メイン・メモリの速度よりもずっと早いペースで高められている。そのため、多くのこのようなシステムでは、比較的費用効果の高い形で性能を向上させるためにしばしばキャッシュ・メモリまたはキャッシュが使用される。
【０００７】
キャッシュは通常、比較的高速のメモリであり、１つまたは複数のプロセッサと、特に揮発性メモリ装置または非揮発性メモリ装置、大容量記憶装置、および／または外部ネットワーク記憶装置に実装されるような比較的低速のメモリとの間に結合される。キャッシュは、プロセッサによる選択されたメモリ・アドレスへのアクセス要求がキャッシュによって処理されるように、選択されたメモリ・アドレスに記憶されている情報のコピーを維持することによって、アクセスの速度を高める。キャッシュに記憶されていないメモリ・アドレスに関するアクセス要求を受け取ると必ず、キャッシュは通常、その情報をメモリから検索し、プロセッサへ転送する。さらに、キャッシュが満杯である場合、通常、最初に使用されたメモリ・アドレスに関する情報が破棄されるか、あるいはメモリに戻され、最後にアクセスされたメモリ・アドレスに関する情報のための空間が設けられる。
【０００８】
キャッシュの利益が最大になるのは、「キャッシュ・ヒット」と呼ばれるキャッシュされているメモリ・アドレスへのアクセス要求の数が、「キャッシュ・ミス」と呼ばれるキャッシュされていないメモリ・アドレスへのアクセス要求の数に対して最大であるときである。通常キャッシュ・ミスの結果として起こる追加のオーバヘッドにもかかわらず、キャッシュ・ヒットの割合が高いかぎり、システムの全体的なアクセス速度は高くなる。
【０００９】
しかし、オペレーティング・システム・コードなど、多くの商用プログラム・コードを用いた場合、コードが再使用されることがなく、かつ命令に指定された条件または試験の結果に基づいてプロセッサに様々な命令経路を選択させるために使用される多数の分岐命令が存在するため、キャッシュ内の命令のミス率は比較的高いことが多いことが判明している。また、多くのオペレーティング・システム・コードはエラーおよび例外の処理に使用され、したがってほとんど実行されず、したがって、キャッシュはしばしば、実行されることのない顕著な数の命令を一時的に記憶する。
【００１０】
さらに、ＶＬＩＷプロセッサの場合、コンピュータ・プログラムをＶＬＩＷ互換フォーマットにコンパイルすると通常、プログラム・コードが２倍ないし４倍に拡大するので、多くの場合、ミス率がずっと高くなることが判明している。また、ＶＬＩＷプログラム・コード中の分岐命令の相対頻度はずっと高く、通常、命令３つごとに分岐が２つある。これに対して、スーパースカラ・プロセッサを用いた場合、分岐は命令５個ないし６個ごとに１つである。
【００１１】
キャッシュのヒット率を高める１つの方法は、キャッシュのサイズを大きくすることである。しかし、キャッシュ・メモリは、多くの場合比較的高価であり、特に、キャッシュを同じ集積回路デバイス上のプロセッサと一体化する場合、設計上の制約によって制限されることが多い。プロセッサと一体化された内部キャッシュは通常、独立の回路に実装される外部キャッシュよりも高速である。一方、設計およびコスト上の制約のために、内部キャッシュは通常、外部キャッシュよりもサイズがずっと小さい。
【００１２】
１つの費用効果の高い代替策は、比較的小形であるがより高速な一次キャッシュが比較的大形であるがより低速な二次キャッシュと連鎖するように、様々な速度の複数のキャッシュを連鎖させることである。命令およびデータを別々のデータ・キャッシュと命令キャッシュに分離することもできる。たとえば、命令については、いくつかのプロセッサは、比較的小形の内部レベル１（Ｌ１）命令キャッシュを実装し、Ｌ１命令キャッシュとメイン・メモリ記憶域との間に追加の外部レベル２（Ｌ２）命令キャッシュが結合される。通常、Ｌ１命令キャッシュのアクセス時間は１クロック・サイクルであり、したがって、プロセッサによって命令を処理するのとほぼ同じ速度でプロセッサにデータを供給することができる。一方、外部Ｌ２命令キャッシュのアクセス時間は多くの場合、少なくとも５クロック・サイクルであり、したがって、プロセッサがＬ２命令キャッシュへのメモリ・アクセスを大幅に利用する必要がある場合、プロセッサはしばしば停止し、キャッシュによってデータが検索されるのを待ち、したがって、プロセッサの性能が著しく低下する。
【００１３】
メモリからの命令の検索に関連する遅延を最小限に抑えるための試みとして、多くのプロセッサはプリフェッチ回路を含む。プリフェッチ回路は、ただちに実行する必要のあるのはどの命令かを「予測」し、次いでプロセッサがこの命令を必要とする前にこの命令をメモリから推測的に検索することを試みる。分岐命令は命令をプリフェッチするうえで最大の障害になり、そのため、プリフェッチ回路は通常、「分岐予測」と呼ばれる動作を実行し、分岐命令の後で特定の命令経路が選択されるかどうかを推測的に判定することを試みる。
【００１４】
１つの分岐予測方法は、すでに実行された分岐命令によってある分岐が選択されたかどうかについての履歴（ヒストリー）を維持する分岐履歴テーブルまたは分岐履歴キャッシュを利用するものである。特に、多くの場合、ある分岐命令が実行されるたびに同じ命令経路が選択されることが判明している。次に特定の分岐命令が実行されるときに同じ経路が選択されると予測することによって、この予測は通常、成功する。
【００１５】
従来型の分岐履歴テーブルは通常、特定の分岐命令が最後に実行されたときにその命令に関する条件が満たされたかどうかの表示を記憶する。しかし、従来型の分岐履歴テーブルを用いた場合、テーブルにアクセスして、ある分岐が選択されたかどうかを判定し、その後で次の命令用のアドレスを生成し、次いで、生成されたアドレスに記憶されている命令を取り出さなければならないことが多い。生成されたアドレスにある命令が一次キャッシュにはない場合、プロセッサは停止し、二次キャッシュがフェッチ要求を処理するのを待つ。
【００１６】
したがって、従来型の分岐履歴テーブルは、分岐命令に関連するオーバヘッドを低減するが、多くの場合、依然としてある程度のオーバヘッドが存在する。そのため、プロセッサ性能が悪影響を受ける。さらに、ＶＬＩＷプログラム・コードを用いた場合、分岐命令により頻繁に出会うので、プロセッサ性能に対する分岐命令の悪影響はずっと大きくなる。
【００１７】
【発明が解決しようとする課題】
したがって、本発明の目的は、分岐命令に関連するオーバヘッドを最小限に抑え、特にＶＬＩＷプロセッサやスーパースカラ・プロセッサのプロセッサ性能を最大にする改良された分岐予測方法を提供することである。
【００１８】
【課題を解決するための手段】
本発明は、プロセッサによって実行される命令に関連する履歴データに基づいてこのような命令を推測的に取り出すデータ処理システム、回路構成、集積回路デバイス、プログラム製品、およびそのような独自のプリフェッチ回路構成を利用する方法を提供することによって、従来技術に関連するこれらおよびその他の問題に対処する。具体的には、所与の命令に関する履歴データが、この所与の命令から１サイクルまたは複数サイクル後に実行された他の命令を識別する。命令ストリームが多くの場合、同じ経路をたどる傾向があるという認識に基づいて、過去の次の命令に関する履歴情報が、推測的命令取出しのための信頼できる予測値であることが判明している。
【００１９】
本発明の一態様によれば、一次命令キャッシュおよび二次命令キャッシュを含むメモリに記憶されている複数の命令の予測される次の命令を表す履歴データを記憶するために命令履歴キャッシュが使用される。予測される次の命令と実際の次の命令がプリフェッチ回路構成によって並列に検索できるように、この命令履歴キャッシュはメモリ内の二次命令キャッシュと並行して操作される。プリフェッチ回路構成はさらに、命令履歴キャッシュから得た予測される次の命令を実行ユニットに供給し、この命令が、実行ユニットによって第１の命令が実行された後に実行されるように構成される。また、実行ユニットと結合された予測検証回路構成は、予測される次の命令と実際の次の命令が一致しない場合に、実行ユニットによる予測される次の命令の実行を終了するように構成される。
【００２０】
特定の分岐が選択されたかどうかを示す従来型の分岐予測キャッシュとは異なり、本発明による命令履歴キャッシュは、分岐命令およびその他の命令の後で実行された実際の命令の履歴を記憶する。そのため、ある分岐が選択されたかどうかについての表示に基づいてアドレスを算出し命令取出しを開始することに関連する呼出し時間が回避され、多くの場合、命令スループットが著しく向上する。
【００２１】
さらに、前述の構成を用いた場合、予測される次の命令が実際に、実行すべき正しい命令であることを検証する前に、この命令を推測的に取り出して実行することができる。したがって、一次命令キャッシュでは行うことのできない命令取出しの場合、この命令取出しが単に二次命令キャッシュによって行われる場合と比べて、命令を検索するのに必要な時間を短縮することができる。
【００２２】
本発明の他の態様によれば、命令履歴キャッシュは、予測される次の命令を表す履歴データを記憶するためにも使用される。しかし、予測される次の命令はそれぞれ、メモリ内の特定の命令が実行されてから少なくとも２サイクル後に実行すべき予測される命令を表す。少なくとも１つの実行ユニットは、メモリから得た第１の命令の実行を開始し、その後、メモリから得た第２の命令の実行を開始するように構成される。さらに、プリフェッチ回路構成は、実行ユニットによって第１の命令が実行されるのと並行して、命令履歴キャッシュから得た第２の命令の予測される次の命令をプリフェッチするように構成される。
【００２３】
言い換えれば、所与の命令に関連する履歴データは、この命令の後で次に実行すべき命令を予測しない。履歴データは、所与の命令に対する将来の命令が実行された後に次に実行すべき命令を予測する。言い換えれば、所与の命令に関連する履歴データは、この所与の命令から２サイクル以上後に実行すべき命令を予測する。多くの実施態様では、命令履歴キャッシュから命令を推測的に検索すると、命令履歴キャッシュのアクセス時間のために遅延が生じることが判明している。したがって、予測される次の次の命令またはそれよりも先の予測される他の命令を推測的に検索することによって、このような命令の検索に関連する呼出し時間をさらに短縮することができる。
【００２４】
本発明の他の態様によれば、次の命令を予測する際に使用される履歴データは、メモリに記憶されている命令内に埋め込むことができる。この場合、実行ユニットとプリフェッチ回路構成は互いに並行して動作することができ、実行ユニットが、メモリに記憶されている命令を実行し、同時にプリフェッチ回路構成が、このような命令の履歴データによって識別される予測される次の命令のメモリからの検索を開始することができる。
【００２５】
履歴データを命令内に埋め込むことによって、多くの場合、独立の命令履歴キャッシュの必要がなくなり、それによって回路構成の複雑さおよび構成要素の数が低減される。さらに、多くの実施態様、たとえばＶＬＩＷプロセッサなどでは、履歴データが追加された場合に、命令自体に必要なメモリ記憶域を超えた追加のメモリ記憶域が必要とされることのないように、履歴データをＶＬＩＷ命令の未使用部分に埋め込めることが多い。
【００２６】
【発明の実施の形態】
本明細書に記載された本発明の様々な実施形態は一般に、命令を推測的に取り出し実行するために使用される命令履歴データをキャッシュすることによって動作する。通常、命令を推測的に取り出し、そのような命令を１つまたは複数の実行ユニットへ転送し、それらの実行ユニットによって実行させるために、プリフェッチ回路構成が使用される。さらに、通常、履歴データに基づいて予測を検証し、必要に応じて、誤って予測された命令の実行を終了するために、予測検証回路構成が使用される。
【００２７】
いくつかの実施態様では、履歴データが独立の命令履歴キャッシュにキャッシュされる。命令履歴キャッシュは内部キャッシュでも、あるいは外部キャッシュでもよく、このキャッシュは予測される次の命令のアドレスではなく、このような命令自体を記憶し、このような命令の検索に関連する呼出し時間を短縮するために使用される。
【００２８】
他の実施態様では、履歴データは、通常は次の命令を識別するアドレス、または次の命令のアドレスを生成できるアドレス・インデックスの形で、命令自体内に埋め込まれる。ＶＬＩＷプロセッサなどの場合、この特徴によりしばしば、追加のメモリ記憶域要件なしに命令の未使用部分に履歴データを記憶することが可能になる。したがって、キャッシュ空間にコストがかかることが多い場合、このような実施態様に関連する記憶域に対する悪影響はない。
【００２９】
さらに、以下でより明らかになるように、所与の命令に関連する履歴データを使用して、この命令を実行した直後に次に実行すべき次の命令を表すことができるが、多くの実施態様では、別の命令用の履歴データを所与の命令と関連付け、この命令用の履歴データが、他の命令が実行された直後に実行すべき次の命令を表すようにすると有益である。言い換えれば、ある命令の直後に実行すべき次の命令に関する履歴データを、メモリ内でこの命令からずらすことができる。
【００３０】
本発明は、ＶＬＩＷプロセッサ、および縮小命令セット・コンピュータ（ＲＩＳＣ）プロセッサや複雑命令セット・コンピュータ（ＣＩＳＣ）プロセッサなどのスーパースカラ・プロセッサを含め、様々なプロセッサ・アーキテクチャと共に使用するのに適している。以下の議論は、本発明とＶＬＩＷベースのアーキテクチャとの併用に焦点を当てているが、当業者には、本明細書の内容を読めば、非ＶＬＩＷ環境での本発明の様々な態様および特徴の実施態様が明らかになろう。
【００３１】
本発明では、回路構成とは、全体的に１つの集積回路デバイスに実装されるか、あるいは１つまたは複数の回路板を介して互いに電気的に結合された複数の集積回路デバイスに実装されるかにかかわらず、導電トレースまたはワイヤあるいはその両方を介して互いに電気的に結合されたアナログまたはデジタルあるいはその両方の電子構成要素の構成である。さらに、通常は、ハードウェア定義プログラムと呼ばれ、デバイス上の回路構成のレイアウトを定義する、１つまたは複数のコンピュータ・データ・ファイルを使用して、集積回路デバイスが設計され製造されることを認識されたい。これらのプログラムは通常、設計ツールによって既知の方法で生成され、その後製造時に、半導体ウェハに適用される回路構成を画定するレイアウト・マスクを作製するために使用される。通常、これらのプログラムは、ＶＨＤＬ、verilog、ＥＤＩＦなどのハードウェア定義言語（ＨＤＬ）を使用して定義済みのフォーマットで生成される。したがって、完全に機能する集積回路デバイスに実装された回路構成に関して本発明を説明し、以下でも説明するが、当業者には、本発明による回路構成を様々な形態のプログラム製品として配給することができ、本発明が、この配給を実際に実施するために使用される信号保持媒体の特定の種類にかかわらず同様に適用されることが理解されよう。信号保持媒体の例には、特に揮発性メモリ装置や非揮発性メモリ装置、フロッピィ・ディスク、ハード・ディスク・ドライブ、ＣＤ−ＲＯＭ、ＤＶＤなどの記録可能型媒体と、デジタル通信リンクやアナログ通信リンクなどの伝送型媒体が含まれるが、これらに限らない。
【００３２】
例示的なデータ処理システム環境
次に図面を参照すると、これらの図面で、同じ番号はいくつかの図全体にわたって同じ部品を示す。図１は、本発明による例示的なデータ処理システム１０を示す。一般に、データ処理システム１０は、メモリ１４と結合された１つまたは複数のプロセッサ１２を含み、メモリ１４は、プロセッサによって処理される命令およびデータを与える。メモリ１４は通常、メモリ階層を形成するようにいくつかのレベルに区分される。たとえば、最大容量のメモリは通常、入出力（Ｉ／Ｏ）サブシステム２０を介してメイン・メモリまたは主記憶装置１８と結合された直接アクセス記憶装置（ＤＡＳＤ）１６などの大容量記憶サブシステムによって代表される。主記憶装置１８は通常、ダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）など比較的大きな揮発性メモリ・バンクである。メモリ用の比較的大きなアドレス空間を設けるには、入出力サブシステム２０、たとえば様々なローカル・エリア・ネットワークや、ワイド・エリア・ネットワークや、その他の通信設備を介して他の外部記憶域形態にアクセスすることができる。システム間相互接続２２を介し、たとえば光ファイバ通信リンクまたはシリアル通信リンクを介してデータ処理システム１０と追加の外部情報を相互接続することができる。
【００３３】
プロセッサ１２と主記憶装置１８の間に、１つまたは複数のレベルのキャッシュ・メモリ、たとえば、レベル３（Ｌ３）キャッシュ２４、レベル２（Ｌ２）キャッシュ２６、およびレベル１（Ｌ１）キャッシュ（この場合、データキャッシュ２８と命令キャッシュ３０に区分される）が設けられる。図１に表わすように、キャッシュ２８、３０と同様に、プロセッサ１２内部の同じ集積回路デバイス上にキャッシュ階層の任意のレベルを実装することができる。別法として、Ｌ２キャッシュ２６、Ｌ３キャッシュ２４と同様に、キャッシュ階層の任意のレベルをプロセッサ１２の外部に実装し、別々の集積回路デバイス上に配設することができる。さらに、たとえばＬ３キャッシュ２４で表されるように、任意の所与のキャッシュが複数のプロセッサのために働くことができる。一般に、プロセッサから始まるメモリ階層内の各レベルは通常、プロセッサから外された次のレベルよりも記憶容量が小さいがアクセス時間は高速であることも理解されたい。したがって、頻繁に使用されるデータをプロセッサのできるだけ近くに維持し、メモリ・システムの効率を最大にすることが望ましい。
【００３４】
図１のプロセッサ１２は、様々な種類のプロセッサに共通するいくつかの構成要素を含む一般的なプロセッサ・アーキテクチャを表す。データは主としていくつかのレジスタ・ファイル３２を介して処理され、演算は、１つまたは複数の演算論理ユニット（ＡＬＵ）３４によってレジスタ・ファイル上で実行される。浮動小数点演算を１つまたは複数の浮動小数点演算ユニット（ＦＰＵ）３６によって処理することもできる。一般に、当技術分野でよく知られているように、ＡＬＵおよびＦＰＵ３６はそれぞれ、実行ユニットとみなすことができる。
【００３５】
プロセッサ１２は、レジスタ・ファイル内のデータを処理するために、復号論理３８および分岐ユニット４０を使用して、Ｌ１命令キャッシュ（Ｉキャッシュ）３０に記憶されている様々な命令を処理する。復号論理３８および分岐ユニット４０はそれぞれ、当技術分野で一般的に理解されており、使用される特定のアーキテクチャに応じて異なる。図の実施形態では、たとえば、プロセッサ１２はＶＬＩＷプロセッサであり、各命令は、プロセッサ内の複数の実行ユニットによって並列に実行される複数のパーセルを含む。たとえば、特にスーパースカラＲＩＳＣアーキテクチャやスーパースカラＣＩＳＣアーキテクチャなど、他のアーキテクチャをサポートできることを理解されたい。この後者のアーキテクチャを用いた場合、様々な実行ユニットに適切な命令を経路指定して最適な性能を得るためにＬ１  Ｉキャッシュ３０と復号論理３８の間に追加の論理が必要になることを理解されたい。当業者には他の修正形態および変形形態が明らかであろう。
【００３６】
命令履歴キャッシュ実施態様
図１に示すように、本発明による方法で使用される履歴データを記憶するために使用される内部命令履歴キャッシュまたは外部命令履歴キャッシュ（ＩＨＣ）４２とプロセッサ１２を相互接続することもできる。ＩＨＣ４２は特に、他のＶＬＩＷ命令の後で実行すべき複数のＶＬＩＷ命令を記憶する。ＶＬＩＷ命令を推測的に検索する場合に様々なキャッシュ・レベルへの追加のアクセスが必要とされないように、ＩＨＣ４２は、このようなＶＬＩＷ命令のアドレスではなくこのようなＶＬＩＷ命令自体のコピーを記憶する。
【００３７】
図の実施形態では、ＶＬＩＷ命令の長さは、１６個の３２ビット・パーセルを含む６４バイトである。ＩＨＣ４２のキャッシュ・ライン長は１ＶＬＩＷ命令、または６４バイトである。通常、ＩＨＣ４２は直接マップされ、したがって、ディレクトリは不要になる。ＩＨＣは、プロセッサ１２内部に実装することができ、あるいは図１に最もよく示すように外部キャッシュでよい。
【００３８】
図２は、プロセッサ１２とＬ２キャッシュ２６と命令履歴キャッシュ４２との間の命令およびデータのフローを詳しく示す。この実施形態で、Ｌ２キャッシュ２６は、キャッシュ・ライン・サイズが１ＫＢまたは１６ＶＬＩＷの外部３２ＭＢ  ４ウェイ・アソシエーティブ・キャッシュとして実装される。このため、Ｌ２キャッシュ２６は、４４で識別されたディレクトリも含む。命令およびデータは、プロセッサ１２とＬ２キャッシュ２６と命令履歴キャッシュ４２との間で６４バイト幅バス４６を介して渡される。Ｌ２キャッシュ２６およびＬ２ディレクトリ４４にはアドレス線４７を介して４４ビット実アドレスが供給される。この実施態様では、Ｌ２キャッシュが実アドレスを介してアドレスされ、したがって、以下でより明らかになるように、プロセッサ１２で仮想／有効アドレスを実アドレスに変換する必要がある。Ｌ２キャッシュの外部性、キャッシュにアクセスするのに必要なアドレス変換、およびキャッシュのマルチウェイ・セット・アソシアティビティのために、この実施態様のＬ２キャッシュは５サイクル・アクセス時間を有するものと仮定される。他のＬ２キャッシュは本発明よりも短いか、あるいは長いアクセス時間を有することができることを理解されたい。
【００３９】
Ｌ２キャッシュ２６に供給されるアドレスは、「分岐先」アドレスとも呼ばれ、現在実行されているＶＬＩＷ命令から決定される実際の次の命令情報を表わす。次の命令予測が正しいことを検証するには、、このアドレス、あるいはより具体的にはこのアドレスに記憶されている命令と、命令履歴キャッシュから推測的に検索された命令が一致しなければならない。さらに、Ｌ２ディレクトリ４４は、線４７から供給された実アドレスに応答して、特に、キャッシュ・ヒットが起こったかどうかと、そうである場合に、４つのセットのうちのどれに、要求されたキャッシュ・ラインが収納されているかとを示す２４ビット・ディレクトリ・エントリを出力する。
【００４０】
命令履歴キャッシュ４２はＩＨＣアドレス線４８によって駆動され、このアドレス線には、キャッシュにアドレスするために使用される１７ビット命令アドレス・レジスタ（ＩＡＲ）インデックスが与えられる。この実施態様の命令履歴キャッシュ４２は８ＭＢ直接マップ・キャッシュとして実装される。したがって、通常、命令履歴キャッシュのアクセス時間をディレクトリ・ベースのＬ２キャッシュと比べて短縮する、独立のディレクトリは必要とされない。この実施態様では、ＩＨＣ４２のアクセス時間は３サイクルと仮定され、それに対してＬ２キャッシュ２６のアクセス時間は５サイクルである。
【００４１】
命令履歴キャッシュ４２に与えられるＩＨＣアドレスは、予測される次の命令を検索するために使用される実行中の現在の命令のアドレスであるので、「分岐元」アドレスを表す。
【００４２】
プロセッサ１２内のＬＩ  Ｉキャッシュ３０は６４ＫＢ直接マップ・キャッシュとして実装される。図の実施態様では、ＬＩ  Ｉキャッシュ３０のキャッシュ・ライン・サイズは１ＫＢ（または１６ＶＬＩＷ）であり、アクセス時間は１サイクルである。
【００４３】
各キャッシュ２６、３０、および４２に交互全体的サイズまたはキャッシュ・ライン・サイズあるいはその両方を使用することができ、かつこれらのキャッシュのそれぞれに他のアソシアティビティを使用できることを理解されたい。したがって、本発明は、本明細書に開示した特定の実施態様に限るべきではない。
【００４４】
図３は、プロセッサ５２、Ｌ２キャッシュ５４、および命令履歴キャッシュ５６、およびＬ１  Ｉキャッシュ５８を使用する他のデータ処理システム５０を示し、これらのプロセッサおよびキャッシュは、図１および図２のデータ処理システム１０とほぼ同様に構成される。図３に示すように、Ｌ２キャッシュ５４は５サイクル・アクセス時間を有し、命令履歴キャッシュ５６は３サイクル・アクセス時間を有する。
【００４５】
ＩＨＣがプロセッサを停止せずに所与の命令の予測される次の命令を使用できるようにするために、データ処理システム５０は、ＩＨＣの３サイクル・アクセス時間に対処するように所与の命令に関する履歴データを命令２つ分だけオフセットするように構成される。すなわち、ＶＬＩＷ命令Ｎ−２、Ｎ−１、Ｎ、Ｎ＋１、Ｎ＋２、およびＮ＋３がすでに順次実行され、これらの命令に関する履歴データがＩＨＣ５６に記憶されているものと仮定すると、ＶＬＩＷ命令Ｎに関する履歴データはＶＬＩＷ命令Ｎ−２に関連付けされ、ＶＬＩＷ命令Ｎ＋１に関する履歴データはＶＬＩＷ命令Ｎ−１に関連付けされ、以下同様である。簡単に言えば、所与のＶＬＩＷ命令に関連する履歴データは、この所与の命令の後で実行すべき予測される３つ後の命令である。
【００４６】
この関連付けは、図の実施態様では、２サイクル前に実行された命令のアドレスを命令履歴キャッシュへのインデックスとして使用して、所与の命令に関する履歴データ、すなわち、この所与の命令の後で実行すべき予測される次の命令を記憶することによって処理される。この場合、２サイクル前に実行された命令のアドレスを使用してこの命令をＬ１  ＩキャッシュまたはＬ２キャッシュから検索するとき、同時にこのアドレスがＩＨＣに与えられ、この命令の予測される次の命令の検索が開始される。したがって、ＩＨＣから取り出すのに必要な追加の２サイクルを用いて、予測される次の命令が適切な時間にＩＨＣから返される。
【００４７】
言い換えれば、所与のＶＬＩＷ命令Ｎの場合、この命令の予測される次の命令ＶＬＩＷ  Ｎ＋１は、ＶＬＩＷ  Ｎ−２のアドレスを使用してＩＨＣに記憶される。次いで、Ｌ１  ＩキャッシュまたはＬ２キャッシュからのＶＬＩＷ  Ｎ−２の検索を試みると、同時にＶＬＩＷ  Ｎ−２のアドレスがＩＨＣに与えられ、ＩＨＣからのＶＬＩＷ  Ｎ＋１の検索が開始される。次の２サイクルでＶＬＩＷ  Ｎ−１およびＶＬＩＷ  Ｎが順次取り出されるものと仮定すると、次のサイクルで、ＩＨＣはＶＬＩＷ  Ｎ＋１をＶＬＩＷ  Ｎの直後に実行できるようにする。したがって、Ｌ１  ＩキャッシュがＶＬＩＷ  Ｎ＋１に対してミスした場合でも、ＩＨＣは依然として、他の場合にはこの命令をＬ２キャッシュから取り出すのに必要になる遅延なしに、この命令を使用することができる。さらに、ＩＨＣに履歴データが記憶されるオフセットが与えられた場合、ＩＨＣアクセスを実際上２サイクル早く開始することによって、他の場合には、予測される次の命令をＩＨＣから検索するのに必要になる余分の２サイクルが回避される。
【００４８】
この関係を一般化すると、図の実施形態では通常、所与の命令に関する履歴データを追加のｘ−１サイクルだけオフセットすることが好ましい。この場合、ｘはＩＨＣのアクセス時間である。言い換えれば、所与の命令に関する履歴データとして、ｘサイクル後に実行すべき予測される命令を記憶することが望ましい。
【００４９】
したがって、この実施態様では、命令履歴キャッシュ５６は、命令アドレス・レジスタ（ＩＡＲ）５９で表される次に実行すべき命令として取り出されている命令のアドレスでインデックス付けされる。同時に、ＩＡＲ５９内の指定されたアドレスもＬ１  Ｉキャッシュ５８に供給されると共に、変更索引バッファ（ＴＬＢ）９０を介してＬ２キャッシュ５４に供給される。変更索引バッファ９０は、ＩＡＲ５９に記憶されている仮想アドレスを、Ｌ２キャッシュにアクセスする際に使用される実アドレスに変換する。仮想アドレス指定を使用しない場合は、プロセッサ５２とＬ２キャッシュ５４の間でＴＬＢまたは他の変換機構を使用しなくてもよいことを理解されたい。
【００５０】
通常、アドレス可能なメモリ空間のサブセットのみがキャッシュに記憶される場合、命令アドレス・レジスタ全体ではなく、インデックスがＩＨＣ５６に与えられる。８ＭＢ命令履歴キャッシュの場合、現在のアドレスから得た１７ビット・インデックス、たとえば、６４ビット・アドレスのビット４１〜５７を使用することができる。しかし、後述の予測検証回路構成を介して正しい命令予測の検証が行われるので、命令履歴キャッシュ５６用のディレクトリは必要とされない。
【００５１】
同様に、Ｌ１  Ｉキャッシュ５８の場合、ＩＡＲ５９から１０ビット・アドレス・インデックスを与え、このキャッシュにインデックス付けすることができる。Ｌ１キャッシュ５８が、Ｌ１キャッシュ・ヒットが生じたかどうかを検証するためのディレクトリ（図示せず）も含むことを理解されたい。このようなディレクトリの使用法および構成は当技術分野でよく知られており、したがって、本明細書で詳しく説明する必要はない。
【００５２】
ＩＡＲ５９は、プロセッサ５２内の１つまたは複数の実行ユニットを表す実行パイプ６０の第１段を形成する。たとえば、ＶＬＩＷプロセッサの場合、複数の実行ユニットは通常、並列に動作し、各ＶＬＩＷ命令中の様々なパーセルを別々に処理する。各実行ユニットは通常、１つまたは複数の別々のパイプを有するが、機能的に見ると、このような複数の実行ユニット用のパイプを、図３に表わす単一のパイプとみなすことができる。したがって、本発明によるデータ処理システムでは任意の数の実行パイプまたはユニットあるいはその両方を使用することができ、このような他のパイプおよびユニットの実施態様が、本明細書で開示する内容の利益を有する当業者の能力の範囲内であることを理解されたい。
【００５３】
パイプ６０の各段は、命令アドレス、ならびにこのアドレスによって指定されるＶＬＩＷ命令用の記憶域を含む。パイプ６０は６段パイプラインであり、パイプの段２ないし６用の命令アドレスはそれぞれ、命令アドレス・レジスタ６２、６４、６６、６８、および７０に記憶され、このようなアドレスによって指定される命令はそれぞれ、命令レジスタ（ＩＲＥＧ）７４、７６、７８、８０、および８２に記憶される。パイプの第１段は、第２段ＩＲＥＧへの命令取出し段であるので、第１段に独立のＩＲＥＧは使用されない。パイプ６０について適切に言い換えると、このパイプは、ＩＡＲ６２とＩＲＥＧ７４がパイプの第１段を形成しＩＡＲ５９がパイプから除外された５段パイプである。
【００５４】
パイプの様々な段は、現在の命令Ｎに対する段としても識別され、命令Ｎ−ｘは、現在の命令からｘサイクル前に処理される命令を表し、命令Ｎ＋ｙは、現在の命令からｙサイクル後に処理される命令を表す。
【００５５】
パイプの段１は命令取出し段（ＩＦＥＴＣＨ）であり、この間にメモリ（通常はＬ１  ＩキャッシュまたはＬ２キャッシュ）から命令が取り出される。パイプの段２は汎用レジスタ・ファイル読取りアクセス段（ＧＰＲ）である。パイプの段３は有効アドレス生成段（ＡＧＥＮ）である。パイプの段４はＬ１データ・キャッシュ（Ｄキャッシュ）アクセス段（ＤＣＡＣＨＥ）であり、段５は、あるデータ・フォーマットのデータ・バス段（ＤＡＴＡＢＵＳ）である。パイプ内の段６は汎用レジスタ・ファイル書込みアクセス段（ＧＰＲ  ＷＲＴ）であり、この段では、命令実行の結果が再び汎用レジスタ・ファイルに書き込まれるか、あるいは一般的には他の構成のレジスタ・ビットに書き込まれる。これらの段中に実行される動作は、周知のプロセッサ動作であり、本発明の理解に関連するものではない。したがって、本明細書ではこれらの段についてこれ以上は説明しない。
【００５６】
さらに、本発明による他の実施態様では、追加の段、すなわち、いくつかの段および段構成を使用することができる。たとえば、スーパースカラ・プロセッサの場合、実行パイプはＩＦＥＴＣＨの前に分岐アドレス生成段を含むこともできる。一方、命令が命令キャッシュ内で整列され、命令を実行する前に順序付けしておく必要がないので、ＶＬＩＷベースのアーキテクチャは通常、分岐アドレス生成段を必要としない。
【００５７】
それぞれ履歴キャッシュ５６およびＬ２キャッシュ５４からの予測される次の命令および実際の次の命令の検索を開始するためにプリフェッチ回路構成８５が使用される。予測される３つ後の命令とも呼ばれる３サイクル後に実行すべき命令の検索は、ＩＡＲ５９から得たアドレス・インデックスに基づいて線８５ａを介して実行される。Ｌ２キャッシュからの実際の次の命令の検索は、パイプの段２中のＩＲＥＧ７４に記憶されている命令に指定された「分岐先」アドレスに基づいて線８５ｂを介して実行される。Ｌ２キャッシュにアクセスするために、線８５ｂ上の分岐先アドレスはＴＬＢ９０によって実アドレスに変換される。たとえば、レジスタ７４に記憶されている命令８６で表されるように、分岐先アドレスは通常、この命令中の分岐条件（ＢＣ）パーセル８８で指定される。
【００５８】
Ｌ２キャッシュおよび命令履歴キャッシュに命令取出しが発行されると、各キャッシュは、それに与えられたアドレスに記憶されている命令を適切な時間に出力する。Ｌ２キャッシュ５４の場合、出力命令は、「ＶＬＩＷ」として表される実際の次の命令である。命令履歴キャッシュ５６の場合、命令出力は、「ＶＬＩＷ'」として表される予測される次の命令である。予測検証回路構成９１はＶＬＩＷおよびＶＬＩＷ'を受け取る。さらに、ＶＬＩＷ'は直接、第２段ＩＲＥＧ７４に与えられ、予測される次の命令の実行が開始される。
【００５９】
予測検証回路構成９１は、Ｌ２キャッシュ５４からのＶＬＩＷ出力が命令履歴キャッシュ５６からのＶＬＩＷ'出力と一致するかどうかを判定する比較ブロック９２を含む。命令履歴キャッシュ５６が３サイクル・アクセス時間を有し、Ｌ２キャッシュ５４が５サイクル・アクセス時間を有するので、ＶＬＩＷ'はＶＬＩＷよりも２サイクル前に回路構成９１に出力される。したがって、ＶＬＩＷ'をＶＬＩＷと整列させるために、命令バッファ・レジスタ９４、９６を含む２段バッファが、命令履歴キャッシュ５６と比較ブロック９２の間に挿入される。キャッシュ５４とキャッシュ５６の間のアクセス時間の差に応じて、命令履歴キャッシュ５６と比較ブロック９２の間に任意の数の段を挿入する必要があることを理解されたい。
【００６０】
比較ブロック９２は、それぞれＬ１  Ｉキャッシュ５８用のディレクトリおよびＬ２キャッシュ５４用のディレクトリからＬ１ミス信号およびＬ２ヒット信号を受け取るＡＮＤゲート９３によってイネーブルされる。比較ブロック９２は、イネーブルされると、禁止信号ＩＨＣ／Ｌ２ＣＯＭＰを出力する。この信号は、ＶＬＩＷ'がＶＬＩＷと一致しないときにはいつでもアサートされる。この禁止信号の結果として、この点で実行パイプ６０の段６  ＩＲＥＧ８２に記憶されているＶＬＩＷ'が「中断」され、したがって、この命令の実行結果が実際上、破棄される。
【００６１】
図の実施態様では、汎用レジスタ・ファイルまたは他の構造のレジスタ・ビットへのライトバックは通常、命令の実行結果として実行された最後の動作なので、ＶＬＩＷ'の結果の破棄は、この命令を無効化して実行パイプの段６でのＧＰＲ  ＷＲＴ動作の実行を禁止することによって実行される。この技法は通常、他の場合に、パイプ内で命令を実際上、中断または停止するために従来型のプロセッサによって使用される。他の実施態様では、ＶＬＩＷ'の実行を他の方法で終了することが望ましい。たとえば、単に命令を無効化するのではなく、命令を完了させ、次いで命令を実行する前のレジスタの状態を表すバックアップ・コピーを用いて汎用レジスタ・ファイルを復元することによって結果を「アンドゥ」することが望ましいこともある。
【００６２】
Ｌ２キャッシュ５４からＶＬＩＷが返されるまでパイプが停止するように、Ｌ２キャッシュ５４の出力を実行パイプ用の状態マシンおよび命令バッファ（図示せず）と結合することが望ましいこともある。このパイプ停止の目的は、Ｌ２キャッシュに対してミスする命令取出しに対処することである。これは、このようなミスがＬ３キャッシュまたは主記憶装置あるいはその両方へのアクセスを必要とし、５サイクルを超えるアクセス時間を必要とするからである。
【００６３】
図４は、図３に示す動作の相対的タイミングを示す。まず、ＩＦＥＴＣＨ状況、ＧＰＲ状況、ＡＧＥＮ状況、ＤＣＡＣＨＥ状況、ＤＡＴＡＢＵＳ状況、およびＧＰＲ  ＷＲＴ状況を含む実行パイプが示されている。２サイクル後に実行すべき命令の次の命令に関する命令履歴キャッシュ・アクセスは、実行パイプと並列に行われ、３アクセス・サイクルと、その後に続く予測検証回路９１内の２つのバッファ段を占めるアクセスとして示されている。キャッシュにアクセスするのに必要な２サイクルと、その後に続き、キャッシュが結果を処理し出力する３アレイ・サイクルとを含むＬ２キャッシュ・アクセスも並行して示されている。Ｌ２ディレクトリへのアクセスは、Ｌ２キャッシュ・アクセスと並列に行われるアクセスとしても示されている。Ｌ２ディレクトリがＬ２キャッシュによる次の命令の前のＬ２ヒットまたはＬ２ミスを示すことにも留意されたい。比較イネーブル信号は、Ｌ２ヒットから生成され、Ｌ１ミスが生じたときにＬ２取出しが完了するまでパイプを選択的に停止しておくために使用される。比較ブロックは、Ｌ２取出しが完了してから半サイクル後に動作するブロックとして示されており、禁止信号は、ＩＨＣ／Ｌ２ＣＯＭＰとして示されており、比較イネーブル信号がアサートされてから半サイクル後に出力される。したがって、実行パイプのＧＰＲ  ＷＲＴ段に到達すると、禁止信号を使用してＧＲＰファイルへの結果のライトバックを許可または禁止することができる。禁止が示された場合、ＧＰＲ  ＷＲＴ動作がバイパスされ、命令の結果が実際上、破棄される。
【００６４】
図５は、命令履歴キャッシュ５６で履歴データを動的に更新するための命令履歴キャッシュ５６への履歴データのライトバックで使用される構成要素を示す。Ｌ２キャッシュ５４は、この更新動作には関連しておらず、話を簡単にするために図から省略されている。
【００６５】
再び命令履歴キャッシュ５６に情報を記憶するために、命令履歴キャッシュに独立の書込みアクセス・ポートが設けられる。キャッシュへの別々の読取りアクセス・ポートおよび書込みアクセス・ポートの使用法および構成は当技術分野でよく知られている。所与の命令の実際の次の命令に関するデータを記憶するための所望のオフセットは、命令履歴キャッシュに書き込むべき命令と、この命令を書き込むアドレスまたはインデックスを、実行パイプの別々の段から取り出すことによって与えられる。図の実施態様では、２段差分が使用され、命令は、第４段ＩＡＲ６６によって指定されるＩＨＣ内の位置に記憶されている実行パイプの第２段ＩＲＥＧ７４に記憶される。この第１段差分は、所与の命令の実際の次の命令を記憶する必要がある場合に対処し、第２段差分は、ＩＨＣ内の履歴データの、この所与の命令からの所望の１サイクル・オフセットに対処する差分である。言い換えれば、２段差分は実際上、所与の命令に関連するＩＨＣ内の位置に３つ後の実際の命令を記憶する。
【００６６】
実行パイプ６０内の様々な段、たとえば、段３および５、または段４および６などからアドレスおよび命令を取り出すことによってオフセットを得ることもできることを理解されたい。さらに、様々なオフセットを得るために、様々なレジスタの出力も使用できることを理解されたい。
【００６７】
図４を参照すると、ライトバック動作の相対的タイミングが詳しく示されている。具体的には、第４の（ＤＣＡＣＨＥ）で、ＶＬＩＷ  Ｎ＋１のアドレスを表すＩＡＲレジスタ６６の値が、Ｌ１  ＩキャッシュおよびＩＨＣへの書込みアドレスとして与えられ、それに対して、ＶＬＩＷ  Ｎ＋３を表す第２段にあるＩＲＥＧ７４の値が、Ｌ１  ＩキャッシュおよびＩＨＣに書き込むべきデータとして与えられる。次いで次のサイクルで、Ｌ２ディレクトリがヒットした場合、前述のアドレスおよびデータを使用してＬ１  ＩキャッシュおよびＩＨＣが書き込まれ、それによって、実際に次に実行される命令を反映するように履歴データが更新される。
【００６８】
図６は、データ処理システム５０によって実行される命令取出し動作１２０を示し、Ｌ１  Ｉキャッシュ、Ｌ２キャッシュ、またはＩＨＣで命令取出しがヒットするかどうかに基づいて実行される異なるプログラム・フローを示す。まず、論理ブロック１２２で、ＩＡＲ５９（図３）に記憶されているＶＬＩＷ  Ｎ＋４の内容がＬ１  Ｉキャッシュ、Ｌ２キャッシュ、およびＩＨＣへ同時に転送される。次に、論理ブロック１２４で（かつ通常は１サイクル未満で）、Ｌ１  Ｉキャッシュ・ディレクトリがヒット／ミス表示を返す。ヒットが起こった場合、論理ブロック１２６に示すように通常どおりに動作が実行され、次のサイクルでＬ１  Ｉキャッシュによって命令取出しが行われる。また、この時点でＩＨＣを更新することが望ましく、あるいはＩＨＣ内の履歴データに変更があるかどうかを検査し、変更が行われた場合にかぎりＩＨＣを更新し、ＩＨＣへのトラフィックを最小限に抑えることが望ましい。
【００６９】
Ｌ１  Ｉキャッシュでキャッシュ・ミスが起こった場合、フローは論理ブロック１２８に進み、次のサイクルにＩＨＣから出力された予測されるＶＬＩＷ信号が、実行のためにパイプに供給される。予測されるＶＬＩＷを検索するためのＩＨＣへのアクセスが２サイクル早く、すなわち、論理ブロック１２２でのＶＬＩＷ  Ｎ＋２のアドレスのディスパッチ中に行われることに留意されたい。
【００７０】
次いで、Ｌ２ヒット／ミスの表示が、論理ブロック１３０で表されたＬ２キャッシュのディレクトリから返されるまで、予測されるＶＬＩＷが１サイクル以上にわたってパイプを通過しながら実行される。ミスが起こった場合、要求された実際の命令がＬ２キャッシュで見つからなかったために予測されるＶＬＩＷが正しくない場合には、論理ブロック１３２で実行される動作が実行される。具体的には、当技術分野で知られている任意の数の方法で、パイプが停止され、パイプの段２内の（図３のＩＲＥＧ７４に記憶されているＶＬＩＷ  Ｎ＋３として示された）ＶＬＩＷが中断される。要求された命令をメモリ階層内のより高いレベルから検索するために主記憶装置アクセスも開始され、要求された命令が返された後、Ｌ２キャッシュが更新され、正しいＶＬＩＷがパイプにディスパッチされ、ＩＨＣが更新され、Ｌ１  Ｉキャッシュが更新され、パイプが復元される。パイプを復元するには、パイプのクロッキングを再開するだけでよく、あるいは場合によっては、パイプが望ましい点を越えている場合にはパイプを前の状態に復元する必要があることもある。
【００７１】
論理ブロック１３０に戻るとわかるように、Ｌ２が命令取出し時にヒットした場合、論理ブロック１３４で、Ｌ２ＭＲＵ予測が正しかったかどうかが判定される。論理ブロック１３４は、アソシエーティブ・キャッシュの場合にのみ実行され、直接マップＬ２キャッシュの場合には省略することができる。ＭＲＵ予測が正しくない場合、論理ブロック１３６で実行される動作が実行される。具体的には、当技術分野で知られている任意の数の方法で、パイプが停止され、パイプの段２内の（図３のＩＲＥＧ７４に記憶されているＶＬＩＷ  Ｎ＋３として示された）ＶＬＩＷが中断される。ディレクトリ参照に基づいてＬ２キャッシュから正しいＶＬＩＷが取り出され、この正しいＶＬＩＷがパイプへ送られ、ＩＨＣが更新される。Ｌ１  ＩキャッシュおよびＬ２ＭＲＵアレイも更新され、前述の方法でパイプが復元される。
【００７２】
論理ブロック１３４に戻るとわかるように、ＭＲＵ予測が正しかった場合、次に論理ブロック１３８で、（すなわち、図３の比較ブロック９２を介して）ＩＨＣ予測が正しかったかどうかが判定される。そうである場合、停止なしで実行が継続し、論理ブロック１４０に示すように、適切な時間にＬ２キャッシュによってＬ１  Ｉキャッシュが更新される。しかし、予測が正しくない場合、パイプの段２内の誤って予測されたＶＬＩＷが、論理ブロック１４２で前述のように中断される。次に、論理ブロック１４４で、Ｌ２キャッシュから取り出されたＶＬＩＷがパイプにディスパッチされ、ＩＨＣおよびＬ１が前述のように更新される。
【００７３】
図７は、マルチチップ集積Ｌ２／命令履歴キャッシュ実施態様を示す他のデータ処理システム１５０を示す。データ処理システム１５０はプロセッサ１５２を含み、プロセッサ１５２内部にＬ１  Ｉキャッシュ１５４および少なくとも１つの実行パイプ１５６が配設される。プロセッサ１５２に命令／データ・バス１６０を介して集積Ｌ２／命令履歴キャッシュ１５８が結合される。キャッシュ１５８は、複数のメモリ・チップ、たとえば、チップ１６２、１６４、１６６、１６８、１７０、１７２、１７４、および１７６を使用して実装される。各メモリ・チップは、Ｌ２キャッシュ区画および命令履歴キャッシュ区画、たとえば、チップ１７６の場合の区画１７８、１８０に論理的に区分される。各区画ごとに別々のアクセス・ポートが設けられ、Ｌ２キャッシュのアクセス・ポートはプロセッサ１５２からのアドレス線１８２と結合され、プロセッサ１５２からのアドレス線１８２は、Ｌ２キャッシュにアクセスするための実アドレスを供給する。線１８２はＬ２ディレクトリ・チップ１８４にも与えられ、Ｌ２ディレクトリ・チップ１８４は、プロセッサからのアクセス要求がＬ２キャッシュでヒットするかどうかを示すＬ２ヒット信号を生成するディレクトリ・エントリを返す。
【００７４】
独立のポートが、命令履歴キャッシュを制御し、プロセッサ１５２からのアクセス線１８６を介して制御される。命令履歴キャッシュは、前述のデータ処理システム１０の場合と同様に、キャッシュにアクセスするための命令アドレス・レジスタ・インデックス値を受け取る。
【００７５】
キャッシュ５８は、たとえば、各メモリ装置がバス１６０を介して８バイト、または６４バイトＶＬＩＷの８分の１を供給する８つの１ＭＢ  ＳＲＡＭメモリ装置または１ＭＢ  ＤＲＡＭメモリ装置を使用して実装される。４ウェイ・アソシエーティブ実施態様を仮定すると、各セットは１／４ＭＢに区分され、最後に使用された区画が命令履歴キャッシュとしても機能する。ＩＨＣ区画をＬ２キャッシュから除外することもできる。ただし、１つの区画をＩＨＣとＬ２キャッシュの両方として機能させることによって、追加のメモリなしでＩＨＣを実装することができる。様々な代替キャッシュ・サイズ、区画サイズ、および／またはチップ数を使用することもできる。
【００７６】
共通の１組の集積回路デバイスまたはチップを使用してＬ２キャッシュおよび命令履歴キャッシュを実装することによって得ることのできる１つの利点は、予測検証機能を実行するのに必要な処理回路の多くをプロセッサから、キャッシュを実装するチップにシフトできることである。たとえば、予測検証回路構成は複数の部分的比較ブロックを含むことができ、たとえば、チップ１７６の場合のブロック１８８のように、各部分的比較ブロックを１つのチップ内に配設することができる。各比較ブロック内で、命令履歴区画から出力された予測される次の命令の８バイト部分が、Ｌ２区画から出力された実際の次の命令の８バイト部分と比較され、Ｌ２区画および命令履歴区画によって出力される８バイト部分中の各ビットが、８バイト比較ブロック１９０を使用して比較される。前述と同じアクセス時間の差を仮定すると、予測される次の命令部分と実際の次の命令部分を整列させるために１対の命令バッファ１９２、１９４が必要になる。次いで、比較ブロック１９０は、予測される次の命令の８バイト部分と実際の次の命令の８バイト部分が一致するかどうかを示す部分的ＩＨＣ／Ｌ２ＣＯＭＰ信号を出力する。次いで、部分的比較ブロックは部分的比較信号を出力し、マスタ比較ブロックとして働くプロセッサ１５２内のＡＮＤブロック１９６で、この信号と他の部分的比較信号との論理積がとられる。論理ブロック１９６の出力は全体的なＩＨＣ／Ｌ２ＣＯＭＰ禁止信号を形成し、この信号は、誤って予測された命令を選択的に禁止または終了するために使用される。
【００７７】
他の実施態様では、プリフェッチ回路構成および予測検証回路構成内の様々な機能をシステム内の様々な集積回路デバイスに割り付けられることを理解されたい。したがって、本明細書で論じる特定の実施態様に本発明を限定すべきではない。
【００７８】
埋込み命令履歴実施態様
本発明のある実施形態では、独立の命令履歴キャッシュを不要にし、それによってプロセッサの命令取出し機構の設計を簡略化することが望ましい。具体的には、多くの実施態様では、命令自体内、通常は命令内の未使用ビット内に履歴データを埋め込み、履歴データの追加によるプログラム・コードの展開を最小限に抑えることが可能であることが判明している。このことは、命令履歴キャッシュの機能を組み込んだＬ２キャッシュの効果を有する。
【００７９】
大多数のＶＬＩＷ命令にいくらかの未使用空間が組み込まれている場合、ＶＬＩＷベースのアーキテクチャは、ＶＬＩＷ命令内に履歴データを埋め込むのに特に適している。ＶＬＩＷによっていくつかの規則が遵守されるかぎり、ＶＬＩＷプログラムの記憶要件にほとんどあるいはまったく影響を与えずに履歴データを埋め込むことが可能であることが判明している。
【００８０】
通常、メモリに記憶されているＶＬＩＷ命令のうちの１つに続いて実行すべき次の命令を表す履歴データは、このような命令のアドレスを得ることのできる識別子で表される。しかし、Ｌ２キャッシュに対するミスが起こった場合に、主記憶域から次の命令を検索することが必要になり、予測される命令アドレスの無効性が未決定になるために、通常、Ｌ２キャッシュにアドレスするのに必要なビット量だけで履歴データが得られる場合、次の命令の完全なアドレスは通常必要とされない。
【００８１】
たとえば、６４ビット・アドレス指定方式を有するシステムに実装される４ＭＢ  Ｌ２キャッシュの場合、通常、２２ビット・アドレス・インデックスだけでキャッシュ内の所与のバイトにアドレスすることができる。さらに、６４バイト・キャッシュ・ライン命令サイズを用い、キャッシュ・ラインおよび命令を適切に整列させた場合、２２ビット・アドレス・インデックスの最下位６ビット（ＬＳＢ）は０であることがわかっており、したがって、１６ビットだけで４ＭＢ  Ｌ２キャッシュ内の所与のキャッシュ・ラインにアクセスすることができる。
【００８２】
アドレス・インデックスを命令内に記憶することのできる１つの方法は、ある数のビットを未使用にして履歴データ用に予約しておくことである。たとえば、ＶＬＩＷ命令の場合、このような命令は通常、様々な実行ユニットによって互いに並列に実行される複数のパーセルを含む。ＶＬＩＷコンパイラは通常、命令の利用可能なスロットにできるだけ多くのパーセルを配置することによってＶＬＩＷ命令をアセンブルする。したがって、命令中の履歴データ用に適切な自由空間が割り付けられるように、コンパイラに命令の１つのスロットを履歴データ用に予約させることができる。
【００８３】
大多数のＶＬＩＷ命令は完全に満杯になることがないにもかかわらず、ＶＬＩＷ命令の１つのスロットを常にブランクにしておくことは、追加のパーセルで命令を満杯にすることができたにもかかわらず、命令に履歴データが追加される場合に、プロセッサ性能に悪影響を与える。しかし、追加のコンパイラ規則を実現することによって、プロセッサ性能に対して比較的小さな影響しか与えずに、ＶＬＩＷ命令にある量の自由空間を残すことができる。
【００８４】
具体的には、ＶＬＩＷコンパイラに、同じキャッシュ・ライン内のアドレスへの分岐を有する分岐命令のみを所与のＶＬＩＷ命令にアセンブルさせることが望ましい。この場合、分岐パーセル以外のパーセルを有するこのようなＶＬＩＷ命令の場合、複数の分岐命令のアドレス・フィールドへの分岐が冗長になり、このようなフィールドのうちの１つを使用して、命令内のパーセルの全体的な密度にはほとんどあるいはまったく影響を与えずに履歴データを記憶することができる。大多数のＶＬＩＷ命令は複数の分岐パーセルを有する傾向があるので、この規則はコンパイラ性能にほとんど影響を及ぼさないと考えられる。
【００８５】
たとえば、ＶＬＩＷプロセッサ・アーキテクチャ用の命令フォーマットには、３２ビットPowerPC互換命令を実現する３２ビット・パーセルを組み込むことができる。PowerPCアーキテクチャによれば、分岐命令の１６ビットが分岐アドレス・フィールドに割り当てられ、この分岐アドレス・フィールドから、所定の条件を満たしたことに応答して、分岐先へのアドレスが生成される。６４ビット・アドレス指定を仮定すると、すべての分岐命令が１ＭＢアドレス空間内で分岐する必要があり、（６４ビット命令サイズが与えられた場合）１６ビット分岐アドレス・フィールドと連結され、６つのゼロが後に続く、命令アドレス・レジスタの最上位４２ビット（ＭＳＢ）を使用して６４ビット分岐先アドレスが生成される。
【００８６】
上記で定義したアドレス指定方式を仮定すると、最小限のプログラム・コード展開で任意の命令中の一定数のビットを履歴データに割り付けるＶＬＩＷコンパイラを作成することができる。たとえば、パーセルをＶＬＩＷ命令にアセンブルする際に以下の規則を遵守することによって、任意の命令の１６ＬＳＢを履歴データに割り付けるようにコンパイラを構成することができる。
【００８７】
Ｉ．ＶＬＩＷ命令が満杯でない場合、命令の最後のスロットにＮＯＯＰ演算を挿入する。
【００８８】
ＩＩ．ＶＬＩＷ命令が満杯であり、少なくとも１つのパーセルがＮＯＯＰ演算である場合、命令の最後のスロットにＮＯＯＰ演算を配置する。
【００８９】
ＩＩＩ．ＶＬＩＷ命令が非ＮＯＯＰ演算で満杯であり、２つ以上の分岐パーセルが命令中に存在する場合、命令の最後のスロットに１つの分岐パーセルを配置する（かつ、すべての分岐パーセル用の共通の分岐アドレスが常に同じスロットに位置するように、任意選択で、命令の終了位置の近くでかつ最後のスロットよりも前に他のすべての分岐パーセルを配置する）。
【００９０】
ＩＶ．ＶＬＩＷ命令が非ＮＯＯＰ演算で満杯であるが、命令中に存在する分岐パーセルが２つよりも少ない場合、パーセルを近くの命令で置き換えて追加の分岐パーセルまたはＮＯＯＰパーセルを命令に追加することを試みる。
【００９１】
Ｖ．ＶＬＩＷ命令が非ＮＯＯＰ演算で満杯であり、分岐パーセルが２つよりも少ないが、命令のパーセルをスワップできない場合、命令の最後のスロットにＮＯＯＰパーセルを挿入し、１つのパーセルを次の命令に移動する。
【００９２】
大部分のＶＬＩＷ命令の７５％以上が完全には充填されず、残りの命令のうちの、約１０％を除くすべての命令が複数の分岐パーセルを含むことに基づいて、上記の規則が、大部分のプログラム・コードを約１％未満しか展開しない傾向を示すことが予測される。
【００９３】
他の実施態様では、ＶＬＩＷ命令に未使用空間を位置させる他の方法を使用することができる。たとえば、いくつかの実施態様では、ＶＬＩＷ命令に対してある事前復号が行われ、パーセルが比較的大きなコードに展開される。いくつかの実施態様では、１６個の３２ビット・パーセルを含む６４バイトＶＬＩＷ命令の場合、実行ユニットの必要とする追加のビットを含む６４ビット・コードにパーセルを展開することができる。さらに、多くの場合、特に分岐命令は常に４８ビット未満にしか展開しないことが判明している。したがって、ＶＬＩＷ命令がパーセルで満杯であり、上記の規則Ｉ〜ＩＶのどれかを満たさない場合でも、多くの場合、パーセルをコードに展開した後に命令の未使用部分に履歴データを埋め込むことができる。したがって、展開されたコードを記憶するメモリ階層の任意のレベル内、たとえば、プリデコーダがＬ２キャッシュと主記憶装置の間に配設される場合にはＬ２キャッシュ内に履歴データを維持することができる。このような例では通常、Ｌ２キャッシュ・ラインおよびＶＬＩＷ命令は１２８バイトに展開され、したがって、少なくともＬ２キャッシュには、履歴データを記憶するのに適した未使用空間が存在する。たとえば、オペランド命令またはマスク・フィールド中の未使用ビットを使用する、未使用空間を見つける他の方法を使用することもできる。
【００９４】
図８は、３２ビット・パーセルを含む６４バイトＶＬＩＷ命令２００を示す。命令２００は複数の分岐パーセルを有する命令として示されており、上記の規則に従って、（パーセル１４および１５用の）最後の２つのスロットにはこのような分岐パーセルが充填されている。パーセル１４および１５は２０２および２０４で詳しく示されており、各パーセルは一般的なPowerPC命令フォーマットに従い、各パーセルの最初の６ビットが演算フィールド（たとえば、パーセル２０２の場合はフィールド２０６）に割り当てられ、次の２組の５ビットはビット・イン（ＢＩ）フィールドおよびビット・アウト（ＢＯ）フィールド（たとえば、パーセル２０２の場合はフィールド２０８、２１０）に割り当てられる。パーセル１４と１５は分岐パーセルなので、各パーセルの残り１６ビットは分岐パーセル・フィールド（たとえば、パーセル２０２の場合はフィールド２１２）に割り当てられる。しかし、すべての分岐命令が同じキャッシュ・ラインに分岐することを必要とする所与のＶＬＩＷ命令内で分岐アドレス・フィールドが冗長である場合、パーセル２０４の分岐先アドレス・フィールド２１４を使用してこのフィールドに履歴データを記憶することができる。
【００９５】
パーセル１５は、ＮＯＯＰ演算フィールド２１８および未使用フィールド２１９を有するＮＯＯＰパーセル２１６でもよく、未使用フィールド２１９内に、ＶＬＩＷ命令に関する同じ履歴データを記憶することができる。様々な代替ビット・マッピングを使用することもできることを理解されたい。
【００９６】
図９は、前述のようにフォーマットされた所与のＶＬＩＷ命令内に履歴データを記憶し維持するように構成された他のデータ処理システム２２０を示す。独立の命令履歴キャッシュ４２を除いて、システム２２０内の残りの構成要素を図１のデータ処理システム１０と同様に構成できることを理解されたい。図９に戻るとわかるように、システム２２０は、６つの段を備える実行パイプ２２２を有するプロセッサ２２１を含む。それぞれ、パイプの６つの段内に配設された、アドレス・レジスタ（ＩＡＲ）２５０、２２４、２２６、２２８、２３０、および２３２のシーケンスに命令アドレス情報が維持される。また、パイプの段２ないし６に関するＶＬＩＷ命令は、命令レジスタ（ＩＲＥＧ）２３６、２３８、２４０、２４２、および２４４に記憶される。Ｌ１  Ｉキャッシュ２４８は６４バイト・キャッシュ・ライン・サイズで示されており、ＩＡＲ２５０に記憶されている命令アドレスを介してアクセスされる。Ｌ１  Ｉキャッシュ２４８内にＶＬＩＷ命令２５２が示されており、この命令は、上記で定義したコンパイラ規則を満たす。具体的には、最後から２番目のスロットに、定義された分岐先アドレス・フィールド２５６を有する分岐パーセル２５４が充填され、最後のスロットに、履歴アドレス・インデックス（ＨＡＸ）フィールド２６０を有する分岐パーセルまたはＮＯＯＰパーセル２５８が充填され、履歴アドレス・インデックスフィールド内に、命令に関連する履歴データが記憶される。
【００９７】
この実施態様では、ＩＲＥＧ２３６に記憶されている命令の分岐先アドレス・フィールドで表される実際の次の命令が、ＩＡＲ２２８の出力（具体的には、分岐先アドレス・フィールド中の同じ１６ビットに対応する、この出力のビット４２〜５７）で表される２サイクルだけずれた予測される次の命令と、比較ブロック２６２を使用して比較される。
【００９８】
また、ＩＲＥＧ２３６で示すように、２サイクル後に実行すべき命令の予測される次の命令を検索するために、ＩＲＥＧの履歴アドレス・インデックス・フィールドを使用して、各サイクルでＬ２キャッシュ２６４がアクセスされる。この場合、Ｌ２キャッシュ２６４は、履歴ベースのアクセス用の３サイクル・アクセス時間を有するように構成される。これを実現するには、たとえば、仮想アドレス実アドレス変換およびディレクトリ・アクセスをバイパスするＬ２キャッシュの独立の履歴読取りアクセス・ポートを使用し、それによって基本的に、Ｌ２キャッシュをこのポートを通して、命令履歴キャッシュとほぼ同様に動作する直接マップ・キャッシュとして構成することができる。メモリ内の隣接ブロック内に所与のプログラム用のすべてのＶＬＩＷ命令を記憶することにより、変換のために所与のブロック内のビットが変更されることがなくなる（たとえば、隣接する位置合わせされた１６ＭＢブロック内にプログラムを維持する場合、通常、変換の結果として２４ＬＳＢが変更されることはない）ので、履歴アクセスによる変換を回避できることが多い。また、ディレクトリにアクセスする必要なしに履歴アクセスに応答して検索すべき正しいセットを選択するために、Ｌ２キャッシュに関するＭＲＵ予測が使用される。前述の機能を実現するための多重アドレス入力Ｌ２キャッシュの使用法および構成は、当業者の能力の範囲内であり、したがって、本明細書で詳しく論じる必要はない。
【００９９】
ＶＬＩＷ命令を新しい履歴アドレス情報で更新する場合、ＩＲＥＧ２３６に記憶されている命令の分岐先アドレス・フィールドと、２サイクル前のＶＬＩＷ命令用のＩＡＲ２２８に記憶されているアドレスがそれぞれ、Ｌ１  Ｉキャッシュ２４８に書き込まれるデータおよびアドレスとして与えられる。実際の分岐命令を２サイクル前のＶＬＩＷ命令アドレスと共に記憶することによって、命令レジスタ２３６に記憶されているＶＬＩＷの実際の次の命令を用いて履歴データが更新される。したがって、この実施態様では、ＶＬＩＷ命令内に履歴データを埋め込むことによってプロセッサ・アーキテクチャが著しく簡略化され、独立の命令履歴キャッシュと同じ機能が実行され、同時にこのようなキャッシュが不要になる。
【０１００】
ＶＬＩＷコンパイラでの前述のコンパイラ規則の実現が、本明細書の内容を読むことに基づいてコンパイラ当業者の能力の範囲内で行われることが理解されよう。さらに、他の数組のコンパイラ規則と、ＶＬＩＷ命令の他の構成およびマッピングを使用して、本発明によって命令内に履歴データを埋め込むことができることを理解されたい。さらに、本明細書に記載された他の実施形態によるこのような変形形態の実施態様も当業者に明らかであることが理解されよう。
【０１０１】
図９の実施態様の場合、多くの例で、Ｌ１  Ｉキャッシュに記憶されている命令がしばしば比較的高速にキャッシュ・アウトされ、したがって、このキャッシュに記憶されている履歴データの時間的な持続が制限される場合、多くの例では、Ｌ１  Ｉキャッシュ２４８に記憶されている履歴データをメモリ階層の他のレベルに維持することが望ましいと考えられる。したがって、ＶＬＩＷ命令をそれに関連する履歴データと共にメモリ階層の他のレベルにコピーすることによって、履歴データとこの命令との関連付けを維持することが望ましいことがある。通常、多くのプロセッサ実施態様における命令キャッシング階層は、所与のキャッシュ・レベルからキャッシュ・アウトされた命令を破棄するに過ぎない。これは、この命令が通常、下位のキャッシュでは修正されず、したがってキャッシュ同士の間のコヒーレンシが問題にならないからである。したがって、履歴データを複数のキャッシュ・レベルで維持することを可能にするには、多くの点で、マルチレベル・データ・キャッシング階層内のデータの処理と同様に、命令が所与のキャッシュからキャッシュ・アウトされる際にこの命令を上位のキャッシュにコピーするように命令キャッシング機構を修正するだけでよい。
【０１０２】
しかし、この手法の１つの欠点として、命令が再びこのようなキャッシュに書き込まれる際に上位キャッシュへのアクセス回数が増加し、それによってキャッシュの全体的な性能が低下する。この問題を軽減するには、ある命令に関する履歴データが変更されたときに上位キャッシュに情報をコピーするのみに留めることが望ましい。
【０１０３】
たとえば、図１０はデータ処理システム２７０を示し、このシステムは、所与のキャッシュによってキャスト・アウトされているＶＬＩＷ命令が再び上位メモリに書き込まれる頻度を減少するためにキャッシュに記憶されている各命令に関連付けされた変更ビットを実装する。所与のキャッシュから所与の命令をキャッシュ・アウトするときに、この命令を再び上位キャッシュに書き込んで履歴データとこの命令との関連付けを維持すべきかどうかが、この変更ビットを使用して判定される。この方式は多くの点で、データ・キャッシュなどでの「ダーティ」ビットの使用と類似している。
【０１０４】
データ処理システム２７０は、（本明細書では命令キャッシュとして実装される）Ｌ２キャッシュ２７４およびＬ３キャッシュ２７６と結合されたプロセッサ２７２を含む。プロセッサ２７２は実行パイプ２７８を含み、このパイプのうちの最初の４段のみが図示されている。残りの２つの段は、本明細書で開示する他の実施形態のパイプと同様に構成されるものと仮定する。したがって、パイプライン２７８は、パイプの最初の４段に対応する少なくとも４つの命令アドレス・レジスタ２９４、２８０、２８２、および２８４と、パイプの段２ないし４に対応する命令レジスタ２８６、２８８、および２９０とを含む。
【０１０５】
レベル１  Ｉキャッシュ２９２が示されており、命令アドレス・レジスタ２９４から供給されるアドレスに基づいてこのキャッシュから命令が取り出される。複数の命令、たとえば、２つの分岐パーセル２９８、３０２を含む命令２９６がＩキャッシュ２９２内に配設され、分岐パーセル２９８は分岐先アドレス・フィールド３００を含み、パーセル３０２は履歴アドレス・インデックス・フィールド３０４を含む。プロセッサ２７２にはＬ１  Ｉキャッシュ２９２用のディレクトリ３０６も示されており、このディレクトリは複数のディレクトリ・エントリ、たとえば、命令２９６に対応するエントリ３０８を含む。Ｌ１命令ディレクトリ３０６は従来型の命令キャッシュ・ディレクトリと同様に構成される。ただし、このディレクトリは、変更ビット、たとえば、ディレクトリ・エントリ３０８の場合は変更ビット３１２の追加フィールド３１０も含む。
【０１０６】
データ処理システム２７０で実行されるプリフェッチ動作および予測検証動作は図９のシステム２２０と同一である。履歴データも、上記で図９に関して論じたのと同様に更新され、すなわち、前の前の命令２８４に記憶されているアドレスを使用してＬ１  Ｉキャッシュがインデックス付けされ、Ｌ１  Ｉキャッシュに記憶すべき実際の次の命令のアドレスが、ＩＲＥＧ２８６内の命令の分岐先アドレス・フィールドから検索される。
【０１０７】
また、論理ブロック３１３で、実際の次の命令と、ＩＲＥＧ２９０内の命令に記憶されている予測される次の命令とが比較され、履歴情報が変更されているかどうかが判定される。そうである場合、ＶＬＩＷ命令の対応するディレクトリ・エントリ用の変更ビットが、この命令がＬ１  Ｉキャッシュにキャッシュされてから履歴データが更新されたことを示すようにセットされる。
【０１０８】
様々なキャッシュ・レベルの間、たとえば、Ｌ１キャッシュとＬ２キャッシュの間のコヒーレンシを維持するために、プロセッサ２７２でキャストアウト・コントローラ３１４が使用される。コントローラ３１４の基本動作を図１１に３２０で示す。コントローラ３１４は一般に、データ・キャッシュ用のキャストアウト・コントローラと同様に動作し、特定のキャッシュから得た情報を、下位キャッシュから削除する際に上位レベルに記憶しなければならないかどうかを判定する。
【０１０９】
コントローラ３１４は原則的に、論理ブロック３２２ですべてのＬ１命令アクセスをスヌープし、そのようなアクセスによってＬ１ミスが生じるかどうかを判定する（論理ブロック３２４）ことによって動作する。Ｌ１ミスが起こると、論理ブロック３２６で、最後に使用された（ＬＲＵ）キャッシュ・ラインの変更ビットがセットされているかどうかが判定される。変更ビットがセットされている場合、制御が論理ブロック３２８に渡され、Ｌ２キャッシュ内のＬＲＵ  ＶＬＩＷ命令のコピーに関する履歴データが更新され、Ｌ２キャッシュ２７４（図２）のディレクトリ３１６用のディレクトリ・エントリ中の変更ビットも、Ｌ２キャッシュが現在、ＶＬＩＷ命令の更新済みコピーを含むことを示すように更新される。これらの動作は、図１０にそれぞれ、１Ａおよび１Ｂとして示された矢印で表されている。
【０１１０】
Ｌ２キャッシュ内のＶＬＩＷ命令およびディレクトリ情報が更新された後、制御が論理ブロック３３０に渡され、Ｌ１  Ｉキャッシュ内の最後に使用されたキャッシュ・ラインに、（変更ビットを含め）Ｌ２キャッシュから得たこのキャッシュ・ライン用の新しいＶＬＩＷ情報およびディレクトリ・エントリがリロードされる。これらの動作は、図１０に矢印２Ａおよび２Ｂで表されている。
【０１１１】
論理ブロック３２６に戻るとわかるように、Ｌ１キャッシュ内の最後に使用されたキャッシュ・ラインの変更ビットがセットされていない場合、論理ブロック３２８がバイパスされ、論理ブロック３３０で実行されるリロード動作の結果として、このキャッシュ・ライン内の情報が破棄される。
【０１１２】
図１０に戻るとわかるように、履歴データが更新されていないかぎり、キャスト・アウト・キャッシュ・ラインのＬ２キャッシュへのライト・バック動作が回避され、それによってＬ２キャッシュへのアクセス回数が減少し、Ｌ２キャッシュの性能が向上する。特に、所与の分岐が、将来の実行で常に同じ経路をたどる可能性が高いことに基づいて、履歴データがある期間の後に安定化する傾向がある場合、履歴データはそれほど頻繁には変更されず、したがって、Ｌ２アクセスの回数は最小限に抑えられる。
【０１１３】
同様な動作を実行し、すなわち、前述のアルゴリズムを使用してＬ２キャッシュ２７４およびＬ３キャッシュ２７６用のディレクトリ３１６および３１８を更新することにより、必要に応じて、Ｌ２キャッシュとＬ３キャッシュの間のコヒーレンスを維持できることを理解されたい。さらに、このような動作を処理するためにプロセッサ２７２に追加のキャスト・アウト・コントローラを実装することが必要になることがある。キャスト・アウト動作を独立の構成要素にオフロードして同じ機能を実行することもできる。
【０１１４】
次に図１２を参照すると、追加の特徴を示すためにデータ処理システム３４０が提示されている。この特徴によって、プロセッサ３４１が様々な種類のＬ２キャッシュと共に動作することを可能にするように履歴データに可変オフセットを設けることができる。たとえば、履歴データの可用性に対してそれぞれの異なるアクセス時間を有するＬ２キャッシュを含む複数の実施態様で所与のプロセッサ・コア設計を使用することができる。したがって、上記で図９および図１０に関して説明した実施形態と同様に一定の２サイクル・オフセットを維持するのではなく、必要に応じて任意の数のオフセット、たとえば、２つ、３つ、４つ、あるいは５つのオフセットを許容することが望ましい。プロセッサ３４１の場合、これは、実行パイプ３４２の様々な段から取り出すべきＬ１  Ｉキャッシュ用のライトバック・アドレスを供給する多重化方式を使用することによって実現される。
【０１１５】
パイプ３４２は、ＩＡＲ３７０、３４４、３４６、３４８、３５０、および３５２と、ＩＲＥＧ３５６、３５８、３６０、３６２、および２６４とを使用する６つの段を含むパイプとして示されている。レベル１  Ｉキャッシュ３６８はＩＡＲ３７０からアクセスされ、比較ブロック３７２は、履歴データに基づいて行われた予測を検証するために使用される。図９に関して説明した実施態様と同様に、ＩＲＥＧ３５６に記憶されている命令の分岐先アドレスは、新しい履歴情報および実（正しい）アドレスとして使用され、この実アドレスが、予測されるアドレスと比較される。しかし、命令アドレス・レジスタの出力をパイプ３４２の１段のみから取り出すのではなく、ＩＲＥＧ３４４、３４６、３４８、および３５０から出力される別々のアドレス線が選択ブロック３７４に与えられ、選択ブロック３７４の出力が、比較ブロック３７２およびＬ１  Ｉキャッシュ３６８用の書込みアドレスに供給される。
【０１１６】
選択ブロック３７４はデコーダ３７６によって制御され、デコーダ３７６は、Ｎビット・レジスタ３７８によって選択された状態を有する。この実施態様では、論理ブロック３７４から４つの可能なアドレスを出力する場合、２ビット・レジスタを使用することができる。通常、立上げ時にレジスタ３７８をロードし、装置が動作している間一定数のサイクルを維持することが望ましい。図１２に示す構成を用いた場合、Ｎ値０は１サイクル・オフセットを表し、Ｎ値１、２、および３はそれぞれ、２サイクル・オフセット、３サイクル・オフセット、および４サイクル・オフセットを表す。このため、データ処理システム３４０のプロセッサ３４１は様々な応用例で使用することができる。
【０１１７】
本発明の趣旨および範囲から逸脱せずに図の実施形態に様々な追加の修正を加えることができる。たとえば、履歴アドレス・インデックスを命令中の履歴データとして記憶する際、順次動作が行われることが検出されたとき、すなわち、所与の命令が実行された後に分岐が行われないことが検出されたときにＬ２キャッシュへのアクセスを禁止することが望ましい。これによって、Ｌ２キャッシュへのアクセス回数がさらに減少し、それによってＬ２キャッシュの相対的な性能が向上する。
【０１１８】
また、他の実施態様では、履歴が比較的頻繁に変更される場合、履歴データの最後の変更が有用であったことを示す追加の確認ビットを含めることが望ましい。したがって、比較が行われたときはいつでも、確認ビットを使用して最後の変更が肯定的なものであったことを示すことができる。
【０１１９】
まとめとして、本発明の構成に関して以下の事項を開示する。
【０１２０】
（１）（ａ）複数の命令を記憶し、一次命令キャッシュおよび二次命令キャッシュを含み、二次命令キャッシュが、一次命令キャッシュよりも長いアクセス時間を有する、メモリと、
（ｂ）複数の予測される次の命令を記憶し、各命令が、メモリに記憶されている命令の後に実行すべき予測される命令を表す、命令履歴キャッシュと、
（ｃ）メモリ内の複数の命令のうちの第１の命令を実行するように構成された少なくとも１つの実行ユニットと、
（ｄ）それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、第１の命令の後に実行すべき予測される次の命令および実際の次の命令の検索を開始するように構成され、さらに、予測される次の命令が、第１の命令が実行された後に実行ユニットによって実行されるように、予測される次の命令を実行ユニットに供給するように構成された、プリフェッチ回路と、
（ｅ）それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、予測される次の命令および実際の次の命令を受け取り、予測される次の命令と実際の次の命令が一致しない場合に実行ユニットによる予測される次の命令の実行を終了するように構成された予測検証回路とを備える回路。
（２）複数の命令がVery Long Word Instruction（ＶＬＩＷ）である上記（１）に記載の回路。
（３）一次キャッシュがレベル１命令キャッシュを含み、二次キャッシュがレベル２キャッシュを含む上記（１）に記載の回路。
（４）さらに、実際の次の命令を第１の命令の予測される次の命令として記憶するように構成された履歴更新回路を備える上記（１）に記載の回路。
（５）実際の次の命令が、予測される次の命令と異なる場合にのみ、実際の次の命令を予測される次の命令として記憶するように履歴更新回路が構成される上記（４）に記載の回路。
（６）命令履歴キャッシュがＮサイクルのアクセス時間を有し、履歴更新回路が、第１の命令からＮ−１サイクル前に実行される第２の命令のアドレスを介して命令履歴キャッシュ内で、第１の命令の予測される次の命令がアクセスされるように、第１の命令の予測される次の命令を命令履歴キャッシュ内で命令Ｎ−１個分ずらすように構成される上記（４）に記載の回路。
（７）実行ユニットが、複数の段を備える実行パイプを備え、命令履歴キャッシュが、データ入力に供給された命令をアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路が、実行パイプの複数の段のうちの１つの段内の命令レジスタを書込みアクセス・ポートのデータ入力と電気的に結合する１組のデータ線と、実行パイプの複数の段のうちのもう１つの段内のアドレス・レジスタを書込みアクセス・ポートのアドレス入力と電気的に結合する１組のアドレス線とを備え、１組のデータ線が結合される段が、１組のアドレス線が結合される段からＮ−１サイクルだけずれる上記（６）に記載の回路。
（８）実行ユニットが、複数の段を備える実行パイプを備え、命令履歴キャッシュが、データ入力に供給された命令をアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路がさらに、実行パイプと命令履歴キャッシュの間に挿入されたセレクタ回路を備え、セレクタ回路が、書込みアクセスポートのデータ入力とアドレス入力の少なくとも一方を実行パイプの様々な段と選択的に結合し、セレクタ入力に応答して、第１の命令の予測される次の命令を命令履歴キャッシュ内で命令１個分以上、制御可能にずらすように構成される上記（６）に記載の回路。
（９）予測検証回路が、それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、予測される次の命令および実際の次の命令を受け取り、これらの命令が一致しないことに応答して、実行ユニットに禁止信号を出力し、予測される次の命令の実行を終了するように構成された比較ブロックを含む上記（１）に記載の回路。
（１０）実行ユニットが、予測される次の命令の実行結果を記憶するレジスタ書込み段を有する実行パイプを含み、実行ユニットが、比較ブロックからの禁止信号に応答して、予測される次の命令のレジスタ書込み段を禁止するように構成される上記（９）に記載の回路。
（１１）比較ブロックが、一次キャッシュからのミス信号および二次キャッシュからのヒット信号によってイネーブルされるように構成される上記（９）に記載の回路。
（１２）二次キャッシュが、命令履歴キャッシュよりもＭサイクルだけ長いアクセス時間を有し、予測検証回路がさらに、命令履歴キャッシュと比較ブロックの間に挿入されたＭ段バッファを備える上記（９）に記載の回路。
（１３）実行ユニットが、一次キャッシュ、二次キャッシュ、および命令履歴キャッシュにアドレスを出力し、一次キャッシュ、二次キャッシュ、および命令履歴キャッシュへの並行アクセス動作を並行して開始するように構成される上記（１）に記載の回路。
（１４）実行ユニットが第１の集積回路デバイス内に配設され、回路がさらに、第１の集積回路デバイスと結合された複数のメモリ装置を備え、複数のメモリ装置がそれぞれ、二次キャッシュおよび命令履歴キャッシュのそれぞれ用のアドレス空間の一部を含み、各メモリ装置が、予測される次の命令および実際の次の命令のそれぞれの一部を記憶し、予測検証回路が、
（ａ）それぞれ、複数のメモリ装置内に配設され、関連するメモリ装置に記憶されている予測される次の命令の一部および実際の次の命令の一部を受け取り、これらの部分が一致しないことに応答して第１の集積回路デバイスに部分比較信号を出力するように構成された、複数の部分比較ブロックと、
（ｂ）第１の集積回路デバイス内に配設され、複数の部分比較ブロックからの部分比較信号を組み合わせ、部分比較信号のうちのどれかが、予測される次の命令と実際の次の命令との間の不一致を示す場合に、予測される次の命令の実行を選択的に終了する禁止信号を生成するように構成された、マスタ比較ブロックとを備える上記（１）に記載の回路。
（１５）上記（１）の回路を備えるデータ処理システム。
（１６）上記（１）の回路を定義するハードウェア定義プログラムと、ハードウェア定義プログラムを保持する信号保持媒体とを備えるプログラム製品。
（１７）信号保持媒体が、伝送型媒体と記憶可能媒体のうちの少なくとも一方を含む上記（１６）に記載のプログラム製品。
（１８）（ａ）複数の命令が記憶された主記憶装置と、
（ｂ）主記憶装置と結合され、複数の命令の少なくとも第１の部分を記憶する二次キャッシュと、
（ｃ）各命令が、複数の命令のうちの１つの後で実行すべき予測される命令を表す、複数の予測される次の命令が記憶された命令履歴キャッシュと、
（ｄ）二次キャッシュおよび命令履歴キャッシュと結合されたプロセッサとを備え、プロセッサが、
（１）二次キャッシュと結合され、複数の命令の少なくとも第２の部分を記憶し、二次命令キャッシュが、一次命令キャッシュよりも長いアクセス時間を有する、一次命令キャッシュと、
（２）複数の命令のうちの第１の命令を実行するように構成された少なくとも１つの実行ユニットと、
（３）それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、第１の命令の後で実行すべき予測される次の命令および実際の次の命令の検索を開始するように構成され、さらに、予測される次の命令が、第１の命令が実行された後で実行ユニットによって実行されるように、予測される次の命令を実行ユニットに供給するように構成された、プリフェッチ回路と、
（４）それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、予測される次の命令および実際の次の命令を受け取り、予測される次の命令と実際の次の命令が一致しない場合に実行ユニットによる予測される次の命令の実行を終了するように構成された予測検証回路とを備えるデータ処理システム。
（１９）二次命令キャッシュが一次命令キャッシュよりも長いアクセス時間を有する、一次命令キャッシュおよび二次命令キャッシュを含むメモリと結合された実行ユニットによって実行される命令を推測的に取り出す方法であって、
（ａ）命令履歴キャッシュおよび二次命令キャッシュから、実行ユニットによる第１の命令の実行後で実行すべき予測される次の命令および実際の次の命令の検索を並行して開始するステップと、
（ｂ）予測される次の命令を、命令履歴キャッシュから受け取り、実行ユニットによって実行されるようにこの実行ユニットに供給するステップと、
（ｃ）命令履歴キャッシュから受け取った予測される次の命令と、二次キャッシュから受け取った実際の次の命令を比較し、予測される次の命令と実際の次の命令が一致しない場合に実行ユニットによる予測される次の命令の実行を終了するステップとを含む方法。
（２０）（ａ）複数の命令が記憶されたメモリと、
（ｂ）各命令が、メモリ内のある命令が実行されてから少なくとも２サイクル後に実行すべき予測される命令を表す、複数の予測される次の命令が記憶された命令履歴キャッシュと、
（ｃ）メモリからの第１の命令の実行を開始し、その後でメモリからの第２の命令の実行を開始するように構成された少なくとも１つの実行ユニットと、
（ｄ）実行ユニットによって第１の命令が実行されるのと並行して、命令履歴キャッシュから得た第２の命令の予測される次の命令をプリフェッチするように構成されたプリフェッチ回路とを備える回路。
（２１）メモリが一次命令キャッシュおよび二次命令キャッシュを含み、二次命令キャッシュが一次命令キャッシュよりも長いアクセス時間を有し、プリフェッチ回路がさらに、予測される次の命令がプリフェッチされるのと並行して、二次命令キャッシュからの第２の命令の実際の次の命令の検索を開始し、予測される次の命令が、第１の命令が実行された後に実行ユニットによって実行されるように、予測される次の命令を実行ユニットに供給するように構成され、回路がさらに、それぞれ、命令履歴キャッシュおよび二次命令キャッシュから、予測される次の命令および実際の次の命令を受け取り、予測される次の命令と実際の次の命令が一致しない場合に実行ユニットによる予測される次の命令の実行を終了するように構成された予測検証回路を備える上記（２０）に記載の回路。
（２２）さらに、第２の命令から少なくとも２サイクル後に実際に実行される命令を第２の命令の予測される次の命令として記憶するように構成された履歴更新回路を備える上記（２０）に記載の回路。
（２３）命令履歴キャッシュがＮサイクルのアクセス時間を有し、履歴更新回路が、第２の命令からＮ−１サイクル前に実行される第３の命令のアドレスを介して命令履歴キャッシュ内で、第２の命令の予測される次の命令がアクセスされるように、第２の命令の予測される次の命令を命令履歴キャッシュ内で命令Ｎ−１個分ずらすように構成される上記（２２）に記載の回路。
（２４）実行ユニットが、複数の段を備える実行パイプを備え、命令履歴キャッシュが、データ入力に供給された命令をアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路が、実行パイプの複数の段のうちの１つの段内の命令レジスタを書込みアクセス・ポートのデータ入力と電気的に結合する１組のデータ線と、実行パイプの複数の段のうちの他の段内のアドレス・レジスタを書込みアクセス・ポートのアドレス入力と電気的に結合する１組のアドレス線とを備え、１組のデータ線が結合される段が、１組のアドレス線が結合される段からＮ−１サイクルだけずれる上記（２３）に記載の回路。
（２５）上記（２０）の回路を備えるデータ処理システム。
（２６）上記（２０）の回路を定義するハードウェア定義プログラムと、ハードウェア定義プログラムを保持する信号保持媒体とを備えるプログラム製品。
（２７）メモリと結合された実行ユニットによって実行される命令を推測的に取り出す方法であって、
（ａ）実行ユニットによるメモリからの第１の命令の実行を開始するステップと、
（ｂ）第１の命令の実行を開始した後、実行ユニットによるメモリからの第２の命令の実行を開始するステップと、
（ｃ）実行ユニットによって第１の命令が実行されるのと並行して、命令履歴キャッシュからの第２の命令の予測される次の命令をプリフェッチするステップとを含み、命令履歴キャッシュが、各命令が、メモリ内のある命令が実行されてから少なくとも２サイクル後に実行すべき予測される命令を表す、内部に記憶された複数の予測される次の命令を有する方法。
（２８）（ａ）各命令が、複数の命令のうちの１つが実行された後に実行すべき予測される次の命令を識別する内部に埋め込まれた履歴データを含む、複数の命令を記憶するメモリと、
（ｂ）メモリと結合され、メモリに記憶されている第１の命令を実行するように構成された、少なくとも１つの実行ユニットと、
（ｃ）実行ユニットによって第１の命令が実行されるのと並行して、第１の命令の履歴データによって識別される予測される次の命令の、メモリからの検索を開始するように構成されたプリフェッチ回路とを備える回路。
（２９）複数の命令がそれぞれ、複数のパーセルを含むVery Long Word Instruction（ＶＬＩＷ）であり、この命令に関する履歴データが少なくとも１つのパーセルに記憶される上記（２８）に記載の回路。
（３０）各命令についての履歴アドレス・インデックスが命令の最後のパーセルに記憶される上記（２９）に記載の回路。
（３１）複数の命令内の各命令が、その最後のパーセルとして、ＮＯＯＰパーセルと分岐パーセルの一方を含む上記（３０）に記載の回路。
（３２）最後のパーセルとして分岐パーセルを有する任意の命令が第２の分岐パーセルを含み、任意の所与の命令中の分岐パーセルが、メモリ内の同じキャッシュ・ラインに分岐する分岐先アドレスを含み、それによって、最後のパーセル中の分岐パーセル用の分岐先アドレスがその履歴アドレス・インデックスで置き換えられる上記（３１）に記載の回路。
（３３）メモリが一次命令キャッシュおよび二次命令キャッシュを含み、プリフェッチ回路が、第１の命令中の履歴アドレス・インデックスを使用して二次キャッシュにアドレスすることにより、第１の命令の履歴データによって識別される予測される次の命令の検索を開始するように構成され、二次命令キャッシュが、履歴アドレス・インデックスを受け取ったことに応答して、一次命令キャッシュのアクセス時間よりも長いＮサイクルのアクセス時間を有する上記（２９）に記載の回路。
（３４）第１の命令に関する履歴データが、第１の命令からＮサイクル後に実行すべき第２の命令の予測される次の命令を識別する上記（３３）に記載の回路。
（３５）プリフェッチ回路がさらに、実行ユニットによる予測される次の命令の実行を開始するように構成され、回路がさらに、
（ａ）第２の命令の後で実行される予測される次の命令および実際の次の命令のアドレスを比較し、予測される次の命令のアドレスと実際の次の命令のアドレスが一致しない場合に実行ユニットによる予測される次の命令の実行を終了するように構成された予測検証回路と、
（ｂ）第２の命令の後で実行される実際の次の命令のアドレスに関連付けされたアドレス・インデックスを第１の命令に関する履歴データとして記憶するように構成された履歴更新回路とを備える上記（３４）に記載の回路。
（３６）実行ユニットが、複数の段を備える実行パイプを備え、一次命令キャッシュが、データ入力に供給されたアドレス・インデックスをアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路が、実行パイプの複数の段のうちの１つの段内の命令レジスタを書込みアクセス・ポートのデータ入力と電気的に結合する１組のデータ線と、実行パイプの複数の段のうちの他の段内のアドレス・レジスタを書込みアクセス・ポートのアドレス入力と電気的に結合する１組のアドレス線とを備え、１組のデータ線が結合される段が、１組のアドレス線が結合される段からＮサイクルだけずれる上記（３５）に記載の回路。
（３７）実行ユニットが、複数の段を備える実行パイプを備え、一次命令キャッシュが、データ入力に供給されたアドレス・インデックスをアドレス入力に供給されたアドレスに記憶するように構成された書込みアクセス・ポートを含み、履歴更新回路がさらに、実行パイプと一次命令キャッシュの間に挿入されたセレクタ回路を備え、セレクタ回路が、書込みアクセス・ポートのデータ入力とアドレス入力の少なくとも一方を実行パイプの様々な段と選択的に結合し、セレクタ入力に応答して、第２の命令の予測される次の命令を命令履歴キャッシュ内で命令１個分以上、制御可能にずらすように構成される上記（３５）に記載の回路。
（３８）一次キャッシュ内の各命令に、その命令に関連する履歴データが変更されたかどうかを示す変更インディケータが関連付けられ、回路がさらに、予測される次の命令のアドレスと実際の次の命令が一致しない場合に第１の命令用の変更インディケータをセットするように構成されたアドレス比較ブロックを備える上記（３５）に記載の回路。
（３９）さらに、一次命令キャッシュおよび二次命令キャッシュと結合されたキャストアウト・コントローラを備え、キャストアウト・コントローラが、第１の命令用の変更インディケータがセットされたときに一次命令キャッシュ内の第１の命令のコピーが置き換えられることに応答して二次命令キャッシュ内の第１の命令のコピーに関する履歴データを更新するように構成される上記（３８）に記載の回路。
（４０）上記（２８）の回路を備えるデータ処理システム。
（４１）上記（２８）の回路を定義するハードウェア定義プログラムと、ハードウェア定義プログラムを保持する信号保持媒体とを備える製品。
（４２）命令を推測的に取り出す方法であって、
（ａ）複数の命令のうちの１つが実行された後に実行すべき予測される次の命令を識別する内部に埋め込まれた履歴データを含む、メモリに記憶されている複数の命令のうちの第１の命令を実行するステップと、
（ｂ）第１の命令を実行することに並行して、第１の命令の履歴データによって識別される予測される次の命令のメモリからの検索を開始するステップとを含む方法。
【図面の簡単な説明】
【図１】本発明による命令履歴を使用するＶＬＩＷデータ処理システムのブロック図である。
【図２】図１のプロセッサと命令履歴キャッシュとＬ２キャッシュとの間の相互接続を示すブロック図である。
【図３】ＶＬＩＷ命令を推測的に検索する際に使用される構成要素を示す、本発明による命令履歴キャッシュを使用する他のＶＬＩＷデータ処理システム用の命令キャッシング階層のブロック図である。
【図４】図３および図５のＶＬＩＷデータ処理システムにおいてＶＬＩＷ命令を検索し履歴データを更新する間に実行される命令のシーケンスのタイミングを示すタイミング図である。
【図５】命令履歴キャッシュ内の履歴データを更新する際に使用される構成要素を示す、図３の命令キャッシング階層のブロック図である。
【図６】図３および図５のデータ処理システムを用いて命令を取り出す間に実行される動作を示すフローチャートである。
【図７】図７は、一体化された外部Ｌ２／命令履歴キャッシュを実現する、本発明による他のＶＬＩＷデータ処理システムのブロック図である。
【図８】本発明による方法で命令内に履歴データを埋め込むのに適したＶＬＩＷ命令用のビット・マッピングのブロック図である。
【図９】推測的にＶＬＩＷ命令を検索しＶＬＩＷ命令内に埋め込まれた履歴データを更新する際に使用される構成要素を示す、本発明による他のＶＬＩＷデータ処理システムのブロック図である。
【図１０】ＶＬＩＷ命令を様々なキャッシュ階層レベルでキャッシュする際にこの命令に埋込み履歴データを維持するのに適したマルチレベル・キャッシュ階層を示す、本発明による他のＶＬＩＷデータ処理システムのブロック図である。
【図１１】図１０のＬ１／Ｌ２キャストアウト・コントローラによって使用されるキャストアウト・アルゴリズムのフローチャートである。
【図１２】制御可能なずれをもつ履歴データ更新機構を示す、本発明による他のＶＬＩＷデータ処理システムのブロック図である。
【符号の説明】
１２  プロセッサ
１８  主記憶装置
２０  入出力サブシステム
２２  システム相互接続
２４  Ｌ３キャッシュ
２６  Ｌ２キャッシュ
２８  Ｌ１  Ｄキャッシュ
３０  Ｌ１  Ｉキャッシュ
３２  レジスタ・ファイル
３８  復号論理
４０  分岐ユニット
４２  命令履歴キャッシュ
４４  Ｌ２ディレクトリ
４８  ＩＡＲインデックス
５２  プロセッサ
５４  Ｌ２キャッシュ
５６  命令履歴キャッシュ
５８  Ｌ１  Ｉキャッシュ
９２  比較ブロック
【図１】
0003659340.tif 000002
【図２】
0003659340.tif 000003
【図３】
0003659340.tif 000004
【図４】
0003659340.tif 000005
【図５】
0003659340.tif 000006
【図６】
0003659340.tif 000007
【図７】
0003659340.tif 000008
【図８】
0003659340.tif 000009
【図９】
0003659340.tif 000010
【図１０】
0003659340.tif 000011
【図１１】
0003659340.tif 000012
【図１２】
0003659340.tif 000013