(57)【要約】データプロセッサは、命令に関する部分的な分岐ターゲット情報を記憶する分岐ターゲットメモリを備えている。分岐ターゲット情報は、分岐のターゲットアドレスの高度な決定のために使用され、これによって、ターゲットアドレスで命令をプリフェッチすることができる。部分的な分岐ターゲット情報は、現在の命令アドレスに関して規定された命令アドレス空間の一部における期待される分岐ターゲットアドレスの位置を示す。命令アドレス空間の関連する部分は、現在の命令アドレスを含むページであり、部分的な分岐ターゲット情報は、分岐ターアゲットアドレスの重要でない部分だけを与える。【特許請求の範囲】
【請求項１】
命令メモリと、
命令メモリからの命令を実行するための命令実行ユニットと、
実行の前に命令をアドレス指定するために命令メモリに接続される命令アドレス出力部を有する命令プリフェッチユニットと、
を備え、
命令プリフェッチユニットは、
−命令のための部分的な分岐ターゲット情報を記憶する分岐ターゲットメモリであって、アドレス入力部を有するとともに、第１の命令アドレスを供給して第１の命令アドレスに関する部分的な分岐ターゲット情報を検索するためにアドレス入力部にプリフェッチユニットの命令アドレス出力部が接続される分岐ターゲットメモリと、
−プログラムフローの分岐変化が期待される場合に、第１の命令アドレスに対して規定された命令アドレス空間の一部における第２の命令アドレスの位置を示す検索された部分的な分岐ターゲット情報を使用して、命令出力部に与えるための第２の命令アドレスを選択するために設けられた命令アドレス選択ユニットと、
を備えるデータプロセッサ。
【請求項２】
命令アドレス空間の前記一部は、第１の命令アドレスから決定されたより重要な部分と、第２の命令アドレスの重要でない部分を供給する更新値とを有する命令アドレスの空間である請求項１に記載のデータプロセッサ。
【請求項３】
分岐ターゲットメモリは、命令アドレス空間の前記一部を使用して、あるいは、分岐ターゲットメモリ内に記憶された情報によって規定される更なるアドレス空間を使用して、第２の命令アドレスが決定されなければならないか否かの指示を記憶し、第２の命令アドレス選択ユニットは、記憶場所がアドレス指定される時に、前記指示にしたがって命令アドレスを選択する請求項１に記載のデータプロセッサ。
【請求項４】
分岐ターゲットメモリが複数の記憶場所を有し、各記憶場所は、第１の命令アドレスの異なる値に関する部分的な分岐ターゲット情報の記憶に適しており、少なくとも、分岐ターゲットメモリ内に記憶された情報によって規定される更なるアドレス空間を使用して第２の命令アドレスが決定されなければならないことを指示が示す時、分岐ターゲトメモリは、第１の命令アドレスによってアドレス指定される第１の記憶場所の内容と、第１の記憶場所に対して所定の相対位置を有する記憶場所の内容とを命令アドレス選択ユニットに出力し、部分的な分岐ターゲット情報および更なるアドレス空間を規定する情報は、その位置が互いに所定の相対位置を有するそれぞれの記憶場所に記憶される請求項３に記載のデータプロセッサ。
【請求項５】
各記憶場所は、複数のタグを記憶するための空間を備え、各タグは、第１の命令アドレスに関する部分的な分岐ターゲット情報の位置を定めるために使用される記憶場所に部分的な分岐ターゲット情報を記憶する命令アドレスの少なくとも一部を示し、前記空間は、更なるアドレス空間を使用して第２の命令アドレスが決定されなければならないことを指示が示す時に、タグの代わりの更なるアドレス空間を規定する情報を、各記憶場所の少なくとも１つに記憶する請求項４に記載のデータプロセッサ。
【請求項６】
データプロセッサによって命令を実行する方法において、先の命令アドレスから現在の命令アドレスを決定することを備え、前記決定することは、
−先の命令アドレスについて記憶された情報を検索し、前記情報は、
−先の命令アドレスで命令を実行した後に、プログラムフローの分岐変化が期待されるか否か
−分岐変化に対応する更新値
を示し、
−プログラムフローの分岐変化が期待されることを指示が示す時、先の命令アドレスに関して規定された領域における現在の命令アドレスの位置を示す指標として、更新値を使用して、現在の命令アドレスを選択する、
ことを備えている方法。
【請求項７】
前記領域は、先の命令アドレスと同じ重要な部分を有する命令アドレスの領域であり、更新値は、現在の命令アドレスの重要でない部分を供給する請求項６に記載の方法。
【請求項８】
先の命令アドレスについて記憶された情報は、更新値が領域における位置または現在の命令アドレスの絶対値を示すか否かの指示を備え、それに応じて現在の命令アドレスが選択される請求項６に記載の方法。
【請求項９】
前記情報は、先の命令アドレスと関連付けてアドレス指定される場所のメモリ内に記憶され、方法は、更新値が領域における位置を示しているか否か、あるいは、現在の命令アドレスの絶対値が現在の命令アドレスを決定するために使用されるべきか否かの指示を記憶することを備え、絶対値は、少なくとも２つの前記記憶場所にわたって割り当てられて記憶される請求項６に記載の方法。
【発明の詳細な説明】
【０００１】
本発明の分野は、データ処理であり、特に、プログラムフローの分岐変化が生じるか否かを決定するために先の命令を判断することが可能となる前に命令をプリフェッチするデータ処理に関する。
【０００２】
命令メモリ内の命令をアドレス指定することと、命令メモリからアドレス指定された命令を受けることとの間での遅れは、データプロセッサによる命令の実行速度を低減させる可能性のある要因である。この遅れを低減させるために、命令をプリフェッチすることが好ましい。すなわち、先の命令のアドレスを与えた後、先の命令の実行が完了する前であって、先の命令がデコードされる極力前に、できる限り早く、現在の命令のアドレスが発行されるのが好ましい。
【０００３】
これにより、先の命令が分岐命令である場合、誤った命令をプリフェッチする可能性がある。このような問題を防止するため、分岐命令の命令アドレスを用いてアドレス指定できる「分岐ターゲットバッファ」（ＢＴＢ）と称されるメモリ内に分岐命令のターゲットアドレスを記憶することが知られている。現在の命令の命令アドレスを決定しなければならない場合、ＢＴＢをアドレス指定するために、先の命令のアドレスが使用される。ＢＴＢが先の命令のアドレスに関して分岐ターゲットのアドレスを記憶する場合、分岐ターゲットのそのアドレスは、現在の命令をプリフェッチするために、現在の命令アドレスとして使用されても良い。したがって、そこから現在の命令がプリフェッチされる現在の命令アドレスを、先の命令がデコードされる前に決定することができる。無論、このようにして決定される現在の命令アドレスは、単なる予測である。このようにして誤った命令がプリフェッチされたことが分かったら、その後、正しい命令が取ってこられる。
【０００４】
１９９５年１１月２９日〜１２月１日にミシガン州のアナーバにおいて行なわれたマイクロアーキテクチャの第２８回年次国際シンポジウムの議事録の１９３頁〜１９８頁で公表され且つ「分岐ターゲットバッファにおける部分解能（Ｐａｒｔｉａｌ　ｒｅｓｏｌｕｔｉｏｎ）」と題されたＢａｒｒｙ　ＦａｇｉｎおよびＫａｔｈｒｙｎ　Ｒｕｓｓｅｌの論文から、分岐ターゲットバッファ（ＢＴＢ）を使用することが知られている。
【０００５】
分岐ターゲットバッファは、非常に速いメモリでなければならず、あらゆる命令サイクルにおいてアクセスされる。その結果、分岐ターゲットバッファは、かなりの電力を消費する。この電力消費量を低減することが望ましく、これは、ＢＴＢで使用されるメモリのサイズを減少することができる場合に達成することができる。Ｆａｇｉｎ等による論文から、ＢＴＢの関連分解能（ａｓｓｏｃｉａｔｉｖｅ　ｒｅｓｏｌｕｔｉｏｎ）の低減、ＢＴＢのサイズを減少することが知られている。すなわち、この場合、先の命令のアドレスの最も重要でない部分だけを用いてＢＴＢがアドレス指定される。
【０００６】
本発明の目的は、分岐ターゲットバッファのサイズを減少させることである。
【０００７】
本発明に係るデータ処理回路が請求項１に示されており、また、そのようなデータ処理回路を動作させる方法が請求項６に記載されている。本発明に係る回路および方法において、分岐ターゲットバッファは、全分岐ターゲットアドレスを記憶する必要がない。これは、分岐ターゲットアドレスに必要な記憶量を減少させる。本発明によれば、全分岐ターゲットアドレスよりも小さい更新値だけが記憶される。プログラムフローの分岐変化が期待される時に、先の命令アドレスに関して規定された領域における現在の命令アドレスの位置を示す指標として、更新値を使用して、現在の命令アドレスが選択される。無論、このようにして、長い長さに及ぶ分岐の分岐ターゲットを記憶することはできない。しかしながら、そのような長さが長い分岐は比較的稀に生じることが分かった。そのような長い長さの分岐は、長さが長い分岐に関して全分岐ターゲットアドレスを記憶することにより、あるいは、先の命令の実行が要求される分岐ターゲットアドレスを与えるまで待つことにより扱われても良い。
【０００８】
好ましい実施例において、更新値は、現在の命令アドレスの重要でない部分だけを与え、先の命令アドレスは、現在の命令アドレスの重要な部分を与える。変形例として、先の命令アドレスに更新値を数学的に加算することにより、現在の命令アドレスが得られても良い。後者は、命令アドレスの重要な部分が変化する境界と分岐が交差する（これは、分岐において任意の長さにわたって生じ得る）ように働くという点で、前者を超える利点を有している。しかしながら、この変形例は、更新値を検索するために既に必要とされる時間の後、加算を実行するための時間を必要とする。これによって、現在の命令をアドレス指定する時間が遅れ、したがって、実行速度が低下する。この遅れを低減するために、好ましい実施例は、現在の命令アドレスの重要でない部分だけを更新値に与え、先の命令アドレスは、現在の命令アドレスの重要な部分を与える。
【０００９】
実施例においては、分岐命令の絶対分岐ターゲットアドレスおよび更新値の両方が、現在の命令アドレスを決定するために使用される分岐ターゲットバッファ内に記憶される。情報のタイプに応じて、先の命令アドレスに関して分岐ターゲットバッファから情報が検索される場合、情報は、現在の命令アドレスとして使用され、あるいは、更新値および先の命令アドレスを使用して現在の命令アドレスを選択するために使用される。
【００１０】
分岐ターゲットバッファは、更新値を記憶するのに適したサイズ、すなわち、絶対ターゲットアドレスを記憶するために必要なサイズよりも小さいサイズを有する記憶場所を有し、絶対アドレスは、分岐ターゲットバッファ内に記憶される時に、更新値を記憶するための少なくとも２つの記憶場所にわたって割り当てられることが好ましい。
【００１１】
以下、図面を参照しながら、本発明に係る回路および方法のこれらの形態並びに他の有利な形態について詳細に説明する。
【００１２】
図１は、データ処理回路を示している。データ処理回路は、命令実行ユニット１０と、命令メモリ１２と、命令プリフェッチユニット１４とを有している。命令プリフェッチユニット１４は、命令メモリ１２のアドレス入力部および実行ユニット１０に接続された命令アドレス出力部を有している。命令メモリ１２は、命令実行ユニット１０の命令入力部に接続された命令出力部を有している。実行ユニット１０は、命令プリフェッチユニット１４に接続された制御出力部を有している。
【００１３】
動作時、命令プリフェッチユニット１４は、命令メモリ１２に対して連続的に命令アドレスを与える。命令メモリ１２は、命令アドレスによってアドレス指定された命令を受けるとともに、これらの命令を実行ユニット１０に供給する。実行ユニット１０は、プログラムフローによって要求されている限り、命令を実行する。命令実行ユニット１０は、実行されるべき命令のアドレスが命令プリフェッチユニット１４によって与えられた命令アドレスと等しくないことを検知すると、修正信号を命令プリフェッチユニット１４に送信して、命令アドレスを修正する。
【００１４】
命令プリフェッチユニット１４は、分岐ターゲット構成要素を有しており、また、分岐ヒストリー構成要素を有していても良い。分岐ターゲット構成要素は、命令メモリ１２内の分岐命令が分岐する命令アドレスについての情報を記憶する。分岐ヒストリー構成要素は、分岐命令がとられそうか否かを示す情報を記憶する。分岐ターゲットアドレスに関する情報が利用可能で且つ分岐がとられそうである場合、命令プリフェッチユニット１４は、分岐ターゲットアドレスからの命令をプリフェッチする。分岐ヒストリー構成要素は、本発明において必要不可欠のものではなく、したがって、図示せず、これ以上説明しない。
【００１５】
メモリ内のロードデータと記憶データとに関する関係は、本発明を理解するために必要ではないため、図１に示されていない。実行中、実行ユニット１０は、データメモリからのデータ値を要求しても良い。この目的のため、それ自身のアドレスと実行ユニット１０へのデータ接続とを有する別個のデータメモリ（図示せず）が設けられても良く、あるいは、命令メモリ１２が、命令取出しとの複合で調子を合わせて、データメモリとして使用されても良い。
【００１６】
命令プリフェッチユニット１４は、２つの部分１４０ａ，１４０ｂで示されるＮビット命令アドレスレジスタ１４０ａ，１４０ｂを有している。第１の部分１４０ａは、Ｎ−Ｍビットのより重要な命令アドレス部分を記憶するためのものであり、第２の部分１４０ｂは、Ｍビットのより重要でない命令アドレス部分を記憶するためのものである（０＜Ｍ＜Ｎ）。命令アドレスレジスタの第１および第２の部分１４０ａ，１４０ｂのアドレス出力部１４１ａ，１４１ｂは、命令メモリ１４のアドレス入力部に接続されている。また、命令プリフェッチユニットは、第１および第２の部分１４２ａ，１４２ｂから成るアドレスマルチプレクサ１４２とアドレス増加ユニット１４２とを備えている。アドレスレジスタ１４０ａ，１４０ｂのアドレス出力部１４１ａ，１４１ｂは、増加されたアドレスのより重要でない部分およびより重要な部分のそれぞれのための第１および第２の出力部を有する増加ユニット１４２に接続されるとともに、アドレスマルチプレクサの第１および第２の部分１４３ａ，１４３ｂのそれぞれの第１の入力部に接続されている。アドレスマルチプレクサの第１および第２の部分１４３ａ，１４３ｂは、アドレスレジスタの第１および第２の部分１４０ａ，１４０ｂにそれぞれ接続される出力部を有している。
【００１７】
命令プリフェッチユニット１４はメモリ１４８を有している。メモリ１４８は、命令アドレスレジスタ１４０ａ，１４０ｂのアドレス出力部１４１ａ，１４１ｂに接続されるアドレス入力部（好ましくは、アソシエイティブアドレス入力部）と、アドレスマルチプレクサの第１および第２の部分１４３ａ，１４３ｂの制御入力部に接続される「ヒット」信号出力部と、アドレスマルチプレクサの第２の部分１４３ｂの第２の入力部に接続される分岐ターゲット情報出力部とを有している。命令アドレスレジスタの第１の部分１４０ａのアドレス出力部１４１ａは、アドレスマルチプレクサの第１の部分１４３ａ第２の入力部に接続されている。メモリ１４８は、命令実行ユニット１０に接続される内容更新入力部を有している。実行ユニット１０は、第１および第２のアドレスマルチプレクサ１４３ａ，１４３ｂの第３の入力部に接続されるアドレス修正出力部と、アドレスマルチプレクサの第１および第２の部分１４３ａ，１４３ｂの更なる制御入力部に接続されるマルチプレクサ制御出力部とを有している。
【００１８】
動作時、命令プリフェッチユニット１４は、命令サイクルクロック（図示せず）の制御下で、命令実行ユニット１０による命令実行と同期して動作する。メモリ１４８は、命令メモリ１２内の分岐命令のターゲットアドレスに関する情報を記憶する。この情報は、利用可能である場合、分岐命令の命令アドレスをメモリ１４８に与えることによって検索することができる。メモリ１４８はアソシエイティブ（セット・アソシエイティブ）であることが好ましい。
【００１９】
メモリ１４８は、命令アドレスレジスタ１４０から受けた命令アドレスによってアドレス指定された分岐ターゲット情報を検索する。メモリ１４８が「ヒット」（命令アドレスに関する分岐ターゲット情報の存在）を示す場合には、これが信号としてアドレスマルチプレクサ１４３ａ，１４３ｂに送られる。アドレスマルチプレクサ１４３ａ，１４３ｂは、これに応答して、命令アドレスレジスタの第１の部分１４０ａからのより重要なＮ−Ｍビットの命令アドレスを命令アドレスレジスタの第１の部分１４０ａに戻す。また、命令アドレスマルチプレクサの第２の部分１４３ｂは、ヒットの検知に応答して、メモリ１４８から検索された分岐ターゲット情報を命令レジスタの第２の部分１４０ｂに送る。
【００２０】
メモリ１４８がヒットを伝えない場合、命令アドレスマルチプレクサ１４３ａ，１４３ｂは、アドレス増加ユニット１４２の出力部のより重要でないＭビット部分およびより重要なＮ−Ｍビット部分を命令アドレスレジスタ１４０ａ，１４０ｂに送る。したがって、次の命令アドレスは、命令メモリ１２内の先の命令に従う命令のアドレスである。
【００２１】
これに対し、メモリ１４８がヒットを伝える場合、次の命令アドレスは、メモリ１４８から検索されたより重要でないＭビットおよび先の命令アドレスのより重要なＮ−Ｍビットを含む命令アドレスレジスタ１４０ａ，１４０ｂ内にロードされる。したがって、先の命令アドレスと同じより重要なＮ−Ｍビットを有する命令アドレスだけをロードできる。メモリ１４８は、多くの命令アドレスのためのアドレスの計算に必要なより重要でないＭビットだけを記憶する。したがって、メモリは、同じ数の命令アドレスのためのＮビット分岐ターゲットアドレス全てを記憶するために必要なメモリよりも小さい。重要でないビットの正確な数Ｍは、全ての可能な分岐ターゲットアドレス値をこのようにして表わすことができないため、小さなメモリサイズの利点とターゲットアドレス予測能力の損失と兼ね合いによって決まる。Ｍ＝１０あるいはそれよりも更に少ないビットの分岐ターゲットアドレスをメモリ１４８内に記憶すると、分岐ターゲットアドレスを記憶する良好（８６％よりも良好）な能力が得られることが、実用的な基準から見出された。そのため、命令アドレスレジスタの第２の部分１４０ｂよびアドレスマルチプレクサの第２の部分１４３ｂは、Ｍ＝１０ビットもしくはそれ以上であることが好ましい。
【００２２】
無論、このようにして計算される次の命令アドレスが誤っている場合がある。これは、例えば、分岐命令がとられないため、あるいは、分岐命令の分岐ターゲットに関する情報が存在しないためである。実行ユニット１０は、命令プリフェッチユニット１４によって与えられる命令アドレスと命令実行の結果として計算された命令アドレスとを比較することにより、これを検知する。等しくない場合、実行ユニット１０は、命令実行中に計算した正しい命令アドレスをアドレスマルチプレクサ１４３ａ，１４３ｂに出力するとともに、修正されたアドレスを命令レジスタ１４０ａ，１４０ｂに出力するようにアドレスマルチプレクサ１４３ａ，１４３ｂに命令する。
【００２３】
幾つかのプロセッサは、命令メモリをアドレス指定する２つの基本単位から成る能力である命令サイズを有している。例えば、ＭＩＰＳプロセッサは、４バイトの命令を有している。この場合、最も重要でないビットの命令アドレスは、常に、同じ値を有している。無論、この場合、これらの最も重要でないビットは、メモリ１４８内に記憶され或はメモリ１４８をアドレスするために使用される命令アドレス内に記憶されるより重要でないＭビットとともに含まれる必要はない。また、ＭＩＰＳプロセッサのような幾つかのプロセッサは、分岐命令を遅らせた。この場合、メモリ内の分岐命令に従う１または複数の命令は、命令アドレス上で分岐が行なわれる前に実行される。この場合、メモリ１４８は、遅延した分岐命令の命令アドレスを受けた後、対応する数の命令サイクルによって、分岐ターゲットアドレスの重要でない部分およびヒットを示す信号の出力を遅らせても良い。すなわち、メモリ１４８によって出力される分岐ターゲットアドレスは、先の命令の予想される分岐ターゲットであるが、必ずしも直前の命令に関するものではない。また、実行ユニットが遅延された分岐を有していない場合であっても、例えばメモリ１４８が分岐ターゲット情報を検索できる時間を与えるために、分岐命令前に１つの命令をアドレス指定する先の命令アドレスによってアドレスがとられるメモリ１４８内に分岐命令に関する分岐ターゲット情報を記憶することが望ましい。
【００２４】
図１は、命令レジスタの第１の部分１４０ａからの命令アドレスのより重要な部分を、次の命令アドレスのより重要な部分として使用することを示している。本発明から逸脱することなく、命令レジスタ１４０ａ内の先の命令アドレスに対して所定の関係を有する次の命令アドレスの他の重要な部分が使用されても良い。例えば、以下の条件下で、すなわち、
−より重要な部分が変化する境を越える第１の閾値よりも先の命令アドレスが少ない場合（より重要でない部分が０または１）
−分岐ターゲット情報がより重要でない部分に関して、所定の第２の閾値を超える１つの値（例えば、１に等しい最も重要なビットを有する値）を与える
といった条件下で、１つの命令によって減少される先の命令アドレスのより重要な部分のバージョンを、次の命令アドレスのために使用しても良い。したがって、境界の交差に起因する誤予想の頻度を減らすことができる。これは、先の命令アドレスの出力が次の命令アドレスの直前に命令メモリ１２に与えられる命令アドレスでない場合にも、もたらされる。
【００２５】
他の例として、次の命令アドレスのために、増加ユニット１４２からの増加された命令アドレスのより重要なビットを使用しても良い。すなわち、命令レジスタの第１の部分１４０ａからの命令アドレスのより重要な部分をマルチプレクサの第１の部分１４３ａに対して供給することを省いても良い。メモリ１４８から検索される命令アドレスの重要でない部分が十分に大きい場合、この全ては、実行速度に関して比較的僅かな差を形成する。これは、命令アドレスのより重要なビットが命令アドレス増加に起因して稀に変化するためである。命令アドレスレジスタの第１の部分１４０ａからのより重要なビットをカップリングバックする代わりに、メモリ１４９がヒットを伝える時に命令アドレスレジスタの第１の部分１４０ａの更新を無効にしても良い。これによって、電力の消費が節約され、回路の複雑さが低減する。
【００２６】
メモリ１４８は、完全なアソシエイティブメモリ（連想記憶メモリ）、セット・アソシエイティブメモリまたはダイレクトメモリであることが好ましい。ダイレクトメモリにおいて、アドレス出力部１４１ａ，１４１ｂから受けた命令アドレスの一部は、メモリ１４８をアドレス指定するために使用され、メモリは、アドレス出力部１４１ａ，１４１ｂからの命令アドレスの他の部分および分岐ターゲットアドレスに関する情報に対応する「タグ」を記憶する。タグは、メモリ１４８に与えられる命令アドレスの対応する部分と比較される。それらが等しい場合には、ヒットが伝えられる。セット・アソシエイティブアドレスにおいて、一組のタグおよび分岐ターゲット情報項目は、アドレス出力部１４１ａ，１４１ｂから受けた命令アドレスの一部によってアドレス指定される場所に記憶される。そのタグがアドレス出力部１４１ａ，１４１ｂから受けた命令アドレスの対応する部分と等しいか否かに応じて、これらの記憶場所のうちの１つが選択され、あるいは、これらの記憶場所のいずれも選択されない。完全なアソシエイティブメモリにおいては、命令アドレスに関する分岐ターゲット情報をメモリ１４８内の任意の場所に記憶することができ、全命令アドレスがタグとして使用される。
【００２７】
メモリ１４８のメモリサイズを更に減少させるために、完全アソシエイティブメモリ、セット・アソシエイティブメモリ、またはダイレクトメモリ内にタグの部分だけのための記憶スペースを設けても良い。メモリから命令アドレスを検索するために、命令アドレスのタグの記憶された部分だけが、アドレス出力部１４１ａ，１４１ｂから受けた先の命令アドレスの対応される部分と比較される。これらの部分が等しい場合、「ヒット」が伝えられ、メモリ１４８を使用して次の命令アドレスが決定される。これによって、分岐ターゲット予測の信頼性が低下する。これは、比較されない命令アドレスの残りの部分が一致しないといった事態が生じる場合があるためである。しかし、予測信頼性の低下に起因する実行速度の損失がかなり小さいことが分かった。１２８個または５１２個の記憶場所を有するメモリにおいて、満足のいく信頼性を得るために、８以上のタグビットが見出された。
【００２８】
プログラムフローの実行中に、メモリ１４８の内容が更新されることが好ましい（あるいは、プログラム実行前に、頻繁に実行されることが期待される分岐命令に関する所定の内容をロードしても良い）。この更新の目的のため、実行ユニット１０は、メモリ１４８の更新入力部に接続される出力部を有している。
【００２９】
図２は、メモリ１４８を更新するためのフローチャートを示している。第１のステップ２１において、実行ユニット１０は、命令メモリ１２のアドレスＡ（ｎ）から取り出された命令Ｉ（Ａ（ｎ））を処理し始める（この説明において、ｎは、命令サイクルを示すために使用される指標；ｎは、実行ユニット１０によって決定される必要がない：Ａ（ｎ）は、現在の命令の単なるアドレス、Ａ（ｎ＋１）は、次の命令等のアドレスである）。第２のステップ２２において、実行ユニット１０は、命令Ｉ（Ａ（ｎ））が分岐命令であるか否かを決定する。分岐命令でない場合、フローチャートは、次の命令サイクルのために繰り返す（ｎが１だけ増加される）。命令Ｉ（Ａ（ｎ））が分岐命令である場合、実行ユニット１０は、分岐命令Ｉ（Ａ（ｎ））後に実行されるべき命令のアドレスＡ（ｎ＋１）および分岐命令Ｉ（Ａ（ｎ））のアドレスの付与後に命令プリフェッチユニット１４によって与えられる命令アドレスのアドレスＦ（ｎ＋１）を決定する。第３のステップにおいて、実行ユニット１０は、Ａ（ｎ＋１）がＦ（ｎ＋１）と等しいか否かを検知する。等しい場合、分岐ターゲットが正確に予測され、次の命令のためにフローチャートが繰り返される（ｎが１だけ増加される）。
【００３０】
Ａ（ｎ＋１）がＦ（ｎ＋１）と等しくない場合、実行ユニット１０は、第４のステップ１４を実行する。このステップでは、分岐命令Ｉ（Ａ（ｎ））がとられると、分岐ターゲットのアドレスＡ（ｎ＋１）の重要でないＭビットが、分岐命令Ｉ（Ａ（ｎ））のアドレスＡ（ｎ）によってアドレス指定されるメモリ１４８の記憶場所に記憶される。メモリ１４８はアソシエイティブメモリであることが好ましいため、Ａ（ｎ＋１）を記憶するための記憶場所を選択して、これにより、その記憶場所の内容を上書きすることが必要な場合もある。記憶場所は、ＬＲＵ（Ｌｅａｓｔ　Ｒｅｃｅｎｔｌｙ　Ｕｓｅｄ）アルゴリズム等の既知のキャッシュ交換アルゴリズムにしたがって選択されても良い。Ａ（ｎ＋１）がＦ（ｎ＋１）と等しくなく且つ分岐命令Ｉ（Ａ（ｎ））がとられていない場合、これは、Ａ（ｎ）によってアドレス指定されるメモリ１４８内の記憶場所に分岐ターゲットアドレスＦ（ｎ＋１）が既に存在していることを意味する。この場合、実行ユニット１０は、このアドレスＦ（ｎ＋１）をその後の使用のためにそのままにしておくことが好ましい。第４のステップ２４の後、フローチャートは、次の命令へと進む（ｎが１だけ増加される）。
【００３１】
無論、図２に示されるアルゴリズムに関しては、多くの変形例が考えられる。例えば、バックワード分岐が頻繁にとられることが期待されるため（例えば、ループ分岐バック）、フォワード分岐のためでなく、バックワード分岐のためだけの分岐ターゲット情報を記憶しても良い。したがって、メモリ１４８内でこれらの分岐のターゲットが早期に交換されるといった危険性を低減する最も実行される（バックワード分岐）のために、より多くの記憶場所が利用可能となる。
【００３２】
実行ユニット１０は、与えられたアドレスＦ（ｎ＋１）が結局のところ実行されるべき命令のアドレスＡ（ｎ＋１）と異なり且つ命令Ｉ（Ａ（ｎ））が分岐命令ではなく或は予測されないアドレスに分岐するためにとられた分岐命令である時に、与えられたアドレスＦ（ｎ＋１）を用いて命令レジスタ１４０ａ，１４０ｂの内容を更新するためにその分岐ターゲット情報を使用する場合には、分岐ターゲット情報を無効にしても良い。このことは、メモリ１４８から情報を検索するために一部のタグのみが使用される実施例において特に有用であることが分かった。その場合、メモリ１４８は、分岐ターゲット情報がメモリ１４８内に記憶される部分的なタグとたまたま同じ部分的なタグ（および、ダイレクトメモリまたはセット・アソシエイティブメモリの場合に、メモリ１４８の記憶場所をアドレス指定するために使用されるアドレスの一部）を有する誤った命令アドレスに関して「ヒット」を形成しても良い。無論、次のヒットが誤っていないことを期待して、そのような情報をメモリ１４８内で有効なままにしておいても良いが、そのような情報を無効にした場合にプログラムの実行が速くなることが分かった。
【００３３】
図１に示される例においては、Ｎビット分岐ターゲットアドレスの重要でないＭビットだけがメモリ１４８内に記憶される。しかしながら、重要でないＭビットアドレス部分だけを記憶する代わりの手段として、分岐ターゲットアドレスの全てあるいは分岐ターゲットアドレスの大部分を記憶できるようにすることが好ましい。したがって、少なくとも２つの情報形式、すなわち、重要でないＭビットの情報、または、分岐ターゲットアドレスの大部分に関する情報、または、全分岐ターゲットアドレスに関する情報でさえ記憶することができる。実行ユニット１０は、分岐ターゲットを予測するために十分な最小形式の情報を記憶する。例えば、アドレスＡでの命令Ｉが分岐ターゲットＴを有し且つアドレスＡのより重要なＮ−ＭビットとターゲットＩとが等しい場合、Ｍビットの小さい形式が記憶されても良く、より重要なＮ−Ｍビットが異なる場合には、情報の大きい形式、例えば全分岐ターゲットアドレスが記憶されても良い。
【００３４】
図３は、大形式の分岐ターゲット情報を記憶して使用する命令プリフェッチユニットを示している。命令プリフェッチユニットは、２つの部分から成る命令アドレスレジスタ３０ａ，３０ｂと、１つのアドレス増加ユニット３２と、２つの部分から成るアドレスマルチプレクサ３３ａ，３３ｂと、１つのメモリ３８とを備えている。命令アドレスレジスタ３０ａ，３０ｂの命令アドレス出力部３１ａ，３１ｂは、増加ユニット３２およびメモリ３８の入力部に接続されている。アドレスマルチプレクサの第１の部分３３ａは、命令プリフェッチユニット（図示せず）に接続される第１の入力部（ｃ）と、増加ユニット３２の出力部に接続される第２の入力部（ａ）と、命令アドレスレジスタの第１の部分３０ａのアドレス出力部３１ａに接続される第３の入力部と、メモリ３８の第１の出力部３９ａに接続される第４の入力部とを有している。アドレスマルチプレクサの第２の部分３３ｂは、命令プリフェッチユニット（図示せず）に接続される第１の入力部（ｄ）と、増加ユニット３２の出力部に接続される第２の入力部（ｂ）と、メモリ３８の第２の出力部３９ｂに接続される第３および第４の入力部とを有している。マルチプレクサ３３ａ，３３ｂは、命令プリフェッチユニット（図示せず）の（ｅ）およびメモリ３８に接続される制御入力部を有している。メモリ３８は、命令実行ユニット（図示せず）に接続される制御入力部（ｆ）を有している。
【００３５】
動作時、図３の命令プリフェッチユニットは、メモリ３８のオプションによって命令アドレスレジスタ３０ａ，３０ｂがメモリ３８からＮビットの次の全命令アドレスまたは減少された命令アドレス（Ｍビット）、次の命令アドレスの重要でない部分をロードすることを除き、図１の命令プリフェッチユニットと同様に機能する。メモリ２８は、命令アドレスレジスタ３０ａ，３０ｂの出力部３１ａ，３１ｂから先の命令アドレスを受ける。メモリ３８は、この先の命令アドレスに応答して、ヒットがあったか否かを示し且つヒットが全分岐ターゲットアドレスに関するものであったか或は分岐ターゲットアドレスの重要でない部分のみに関するものであったかを示す制御信号をアドレスマルチプレクサ３３ａ，３３ｂに出力する。また、メモリ３８は、全分岐ターゲットアドレスまたは重要でない部分も出力する。
【００３６】
図３のアドレスマルチプレクサ３３ａ，３３ｂは、メモリ３８がヒットの信号を送信する時、ヒットが全分岐ターゲットアドレスに関するものであったか或は分岐ターゲットアドレスの重要でない部分のみに関するものであったかどうかに応じて、アドレスマルチプレクサの第１の部分３３ａが命令アドレスレジスタ３０ａの第１の部分からの先の命令アドレスの重要なＮ−Ｍビット部分またはメモリ３８からの重要なＮ−Ｍビット部分を送出することを除いて、図１のアドレスマルチプレクサ１４３ａ，１４３ｂと同様に機能する。
【００３７】
メモリ３８は、分岐ターゲットアトレスの重要でないＭビット部分、並びに、全分岐ターゲットアドレスが記憶されたか否かを示すための情報、を記憶するための記憶場所を有していることが好ましい。後者の場合、分岐ターゲットアドレスのビットは、２つの局所的に隣接する記憶場所にわたって割り当てられる。メモリ３８は、先の命令アドレスを受け取ってヒットを検知すると、ヒットが検知されたメモリの第１の記憶場所の内容の一部をメモリの第２の出力部３９ｂから出力するとともに、第１の記憶場所に隣接する第１の出力部３９ａの第２の記憶場所から情報を出力する。全分岐ターゲットアドレスが使用される情報を第１の記憶場所が含んでいる場合、メモリ３８は、これを信号としてマルチプレクサ３３ａ，３３ｂに送信する。したがって、全分岐ターゲットが必要とされる場合、メモリ３８から２つの記憶場所が使用されるとともに。重要でない部分だけが必要とされる場合には、１つの記憶場所が使用される。
【００３８】
分岐ターゲット情報が記憶される命令アドレスを確認するためにメモリ３８が（部分的な）タグを使用する場合、この部分的なタグは、第２の記憶場所のために必要ではない。第２の記憶場所のタグを記憶するためのメモリ空間は、分岐ターゲットアドレスのビットを記憶するために使用されても良い。これらのビットとメモリ３８に供給される命令アドレスとの一致に起因する誤ったヒットが、例えばタグ情報が記憶されたか否かを示すための第２の記憶場所のビットを使用することによって、あるいは、この目的のために隣接する第１の記憶場所から全アドレス分岐ターゲットアドレスが記憶されたか否かを示すための情報を調べることによって抑制されても良い。
【００３９】
セットアソシエイティブメモリ３８の場合、第１および第２の記憶場所は、同じセットからのものであることが好ましい。したがって、１つのセットだけが同時に読み込まれる必要がある。
【００４０】
本発明から逸脱することなく、必要に応じて全分岐ターゲットアドレスを記憶するために、２以上の記憶場所が使用されても良く、あるいは、メモリ３８は、２以上の他の長さの分岐ターゲット情報間で選択するというオプションを有していても良い。例えば、４つの異なる長さのＭ，２Ｍ，３Ｍビットの重要でない分岐ターゲットアドレスの部分および全分岐ターゲットアドレスが、択一的に記憶されて、適宜に命令アドレスレジスタ３０ａ，３０ｂに供給されても良い。
【００４１】
また、記憶場所同士の間に所定の関係がある限り、あるいは、異なる部分が見出され得る場所を示すために情報が記憶場所に記憶される場合、分岐ターゲットアドレスの一部を記憶するために、論理的に隣り合う記憶場所を使用する必要はない。
【００４２】
実行ユニット（図示せず）は、先の命令アドレスの十分な数の重要なビットと分岐ターゲットアドレスとが等しいか否かに応じて、いずれの長さの分岐ターゲット情報がメモリ３８内に記憶されるかをメモリ３８に送信する。
【図面の簡単な説明】
【図１】
データ処理回路を示す図。
【図２】
分岐ターゲット情報を記憶するためのフトーチャートを示す図。
【図３】
命令プリフェッチユニットを示す図。
【国際公開パンフレット】
2004505345.tif 000002
2004505345.tif 000003
2004505345.tif 000004
2004505345.tif 000005
2004505345.tif 000006
2004505345.tif 000007
2004505345.tif 000008
2004505345.tif 000009
2004505345.tif 000010
2004505345.tif 000011
2004505345.tif 000012
2004505345.tif 000013
2004505345.tif 000014
2004505345.tif 000015
2004505345.tif 000016
2004505345.tif 000017
2004505345.tif 000018
2004505345.tif 000019
2004505345.tif 000020
【国際調査報告】
2004505345.tif 000021
2004505345.tif 000022