JP2009069960A - 分岐予測装置、分岐予測方法、及びマイクロプロセッサ - Google Patents

Abstract

【課題】より正確に、且つ、より簡便に分岐予測を行うことができる分岐予測装置、分岐予測方法、及びマイクロプロセッサを提供する。
【解決手段】命令を格納する命令メモリ１から読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測装置３３に、条件分岐命令の分岐条件が成立するか否かについての予測情報を格納する分岐予測エントリ部３４と、条件分岐命令の実行により分岐条件が成立した場合に、分岐方向に基づいて条件分岐命令が次回実行される際の分岐条件の成立可能性を予測し、予測情報を更新するエントリ更新部３６と、を備えた。
【選択図】図１

Description

本発明は、分岐予測装置、分岐予測方法、及びマイクロプロセッサに関し、特に、過去の分岐履歴情報を元に次回の分岐結果を予測する分岐予測装置、分岐予測方法、及びマイクロプロセッサに関する。

近年、ほとんどのマイクロプロセッサでは、パイプライン処理を用いることにより、高速化を図っている。パイプライン処理とは、マイクロプロセッサ内部に搭載された複数の処理ユニットに、複数の命令を同時並行的に実行させる処理である。パイプライン処理では、各処理ユニットがクロックに同期して同時に独立して動作できるように、各命令を少しずつずらして各処理ユニットに実行させている。これにより、各処理ユニットが効率よく動作することができ、マイクロプロセッサの処理速度が向上する。

パイプライン処理による高速化を維持するためには、各処理ユニットが命令を途切れなく実行する必要がある。しかし、各処理ユニットの動作が止まってしまうハザードと呼ばれる現象が生じる場合がある。
例えば、命令の中に条件分岐命令が含まれる場合にハザードが生じることがある。条件分岐命令とは、ある条件を満たした場合に分岐が成立する命令である。従って、処理ユニットが条件分岐命令を実行するまで、分岐が成立するか否かが分からない。そのため、条件分岐命令を実行するまで、各処理ユニットの動作を止める必要がある。このようなハザードを制御ハザードと呼ぶ。

そこで、制御ハザードによる処理速度の低下を防ぐため、マイクロプロセッサに分岐予測を行う分岐予測装置が設けられている。分岐予測装置は、条件分岐命令の実行結果が分岐成立となるか否か、即ち、条件分岐命令の分岐条件が成立するか否か（分岐条件の成立可能性）を予測する。そして、マイクロプロセッサは、分岐予測装置の予測に基づいて、条件分岐命令後の命令を投機的に実行する。予測が正解の場合には、そのまま実行を続ける。予測が不正解の場合には、投機的に実行した処理結果を破棄して、条件分岐命令後の命令の実行をやり直す。
近年のマイクロプロセッサは、性能向上のために、パイプラインの段数を増やして動作周波数を上げている。パイプラインの段数が増加するほど予測が不正解だった場合の処理速度低下が大きくなる。そのため、分岐予測の精度を向上させることが重要な課題となっている。

一般に、条件分岐命令の実行結果には傾向性がある。例えば、前回の実行結果が分岐成立であった条件分岐命令の次回の実行結果も分岐成立である場合が多い。
そこで、非特許文献１には、条件分岐命令の実行結果を予測情報としてＢＴＢ（Ｂｒａｎｃｈ Ｔａｒｇｅｔ Ｂｕｆｆｅｒ）に登録し、ＢＴＢを参照して分岐予測を行う技術が開示されている。
具体的には、分岐予測装置は、条件分岐命令の実行結果が分岐成立である場合にのみ、当該実行結果を予測情報としてＢＴＢに登録する。また、ＢＴＢは、予測情報として、分岐する可能性大（Ｓｔｒｏｎｇｌｙ Ｔａｋｅｎ；以下、ＳＴと称する。）、分岐する可能性小（Ｗｅａｋｌｙ Ｔａｋｅｎ；以下、ＷＴと称する。）、分岐しない可能性小（Ｗｅａｋｌｙ Ｎｏｔ Ｔａｋｅｎ；以下、ＷＮと称する。）、分岐しない可能性大（Ｓｔｒｏｎｇｌｙ Ｎｏｔ Ｔａｋｅｎ；以下、ＳＮと称する。）の４つの値を記憶する。条件分岐命令の実行結果が分岐成立である場合、ＢＴＢに記憶される予測情報は、図６に示すように、ＳＮ→ＷＮ、ＷＮ→ＷＴ、ＷＴ→ＳＴと遷移する。また、条件分岐命令の実行結果が分岐不成立である場合、ＢＴＢに記憶される予測情報は、ＳＴ→ＷＴ、ＷＴ→ＷＮ、ＷＮ→ＳＮと遷移する。そして、分岐予測装置は、予測情報がＳＴ又はＷＴである場合に、分岐すると予測する。また、分岐予測装置は、予測情報がＳＮ又はＷＮである場合に、分岐しないと予測する。また、条件分岐命令が実行されておらず、予測情報が登録されていない場合、分岐予測装置は分岐しないと予測する。

表１に、分岐予測を行う場合と行わない場合の実行サイクル数を示す。表１は、ループ回数が５回のループを２周期実行した場合の実行サイクル数を示している。表１において、Ｔは分岐成立（Ｔａｋｅｎ）、Ｎは分岐不成立（Ｎｏｔ Ｔａｋｅｎ）、Ｍは予測ミス（Ｍｉｓｓ）、Ｈは予測正解（Ｈｉｔ）を示す。
表１では、分岐予測を行わない場合、条件分岐命令の実行結果が分岐成立のときの実行サイクル数は５であり、条件分岐命令の実行結果が分岐不成立のときの実行サイクル数は１である。そして、合計サイクル数は４２となる。
一方、分岐予測を行う場合、予測が正解のときの実行サイクル数は１であり、予測が不正解のときの実行サイクル数は５である。そして、合計サイクル数は２２となる。従って、分岐予測を行うことにより、実行サイクル数が減少し、マイクロプロセッサの処理速度が向上する。

また、特許文献１には、条件分岐命令と過去の分岐履歴とを記憶し、分岐履歴から分岐の偏りを検出する偏向カウンタを設け、当該分岐の偏りから分岐予測を行うことにより、分岐予測の精度を向上させる技術が開示されている。
ｅ２００ｚ６ ＰｏｗｅｒＰＣＴＭ Ｃｏｒｅ Ｒｅｆｅｒｅｎｃｅ Ｍａｎｕａｌ、７．２．１．２節、［ｏｎｌｉｎｅ］、［平成１９年７月３１日検索］、インターネット〈URL : http://www.freescale.com/files/32bit/doc/ref_manual/e200z6RMAD.pdf〉 特開２００２−１８２９０６号公報

しかしながら、非特許文献１では、新たな条件分岐命令が実行された際、条件分岐命令の実行結果が分岐成立の場合にのみ、当該実行結果が予測情報としてＢＴＢに初期登録される。そのため、プログラムによっては、分岐予測を行うことにより実行サイクル数が増えてしまう場合がある。図５に、分岐予測を行うことにより実行サイクル数が増えてしまうプログラム例を示す。図５に示すように、当該プログラムは、Ｉ１、Ｉ２、Ｉ３、Ｉ４の４つの命令を含み、当該Ｉ１〜Ｉ４の命令が複数周期繰り返して実行されるループ構造を有している。そして、ループは、条件分岐命令Ｉ３を有している。また、図５において、Ｎ１の「ｘ４」は、プログラム記述ではないが、Ｉ１〜Ｉ４のループを４回繰り返すことを示している。即ち、条件分岐命令Ｉ３の実行結果は、ループ回数４回目までは不成立であり、ループ回数５回目に成立となる。従って、図５に示すループが実行される回数（ループ回数）は５回である。表２に、図５に示すループを２周期実行した際の実行サイクル数を示す。表２では、分岐予測を行う場合と行わない場合の実行サイクル数を示している。表２に示すように、条件分岐命令の実行結果は、ＮＴ、ＮＴ、ＮＴ、ＮＴ、Ｔとなり、１周期目のループの５回目の実行後初めて、実行結果Ｔが予測情報として登録される。そして、２周期目のループの１回目の実行結果はＮＴだが、予測情報はＴとなっているため、予測が不正解となる。そのため、分岐予測を行う場合の実行サイクル数が分岐予測を行わない場合よりも多くなってしまう。

また、特許文献１では、複数回、同じ条件分岐命令を実行しなければ、分岐の偏りを検出することができない。そのため、条件分岐命令の実行回数が少ない場合には、正確な分岐予測を行うことができない。また、偏向カウンタなどを設けるため、回路構成が複雑になる。

本発明の第１の態様にかかる分岐予測装置は、命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測装置であって、前記条件分岐命令の分岐条件が成立するか否かについての予測情報を格納する分岐予測エントリ部と、前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の分岐条件の成立可能性を予測し、前記予測情報を更新するエントリ更新部と、を備える。

本発明の第２の態様にかかるマイクロプロセッサは、命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測装置を備えるマイクロプロセッサであって、前記分岐予測装置は、前記条件分岐命令の分岐条件が成立するか否かについての予測情報を格納する分岐予測エントリ部と、前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の分岐条件の成立可能性を予測し、前記予測情報を更新するエントリ更新部と、を備える。

本発明の第３の態様にかかる分岐予測方法は、命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測方法であって、前記条件分岐命令の分岐条件が成立するか否かについての予測情報を分岐予測エントリ部に格納し、前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の分岐条件の成立可能性を予測し、前記予測情報を更新する。

本発明においては、分岐方向に基づいて条件分岐命令が次回実行される際の分岐条件の成立可能性を予測するので、従来のように単に前回の条件分岐命令の実行結果に基づいて次回の条件分岐命令の分岐条件の成立可能性を予測する場合に比べて、より正確に分岐予測を行うことができる。
また、特別なカウンタなどを設ける必要がないため、回路構成をより簡便なものとすることができる。また、条件分岐命令の実行回数が少なくても、正確に分岐予測を行うことができる。

本発明により、より正確に、且つ、より簡便に分岐予測を行うことができる。

以下に、本発明を適用可能な実施の形態を説明する。なお、本発明は、以下の実施の形態に限定されるものではない。
図１に、本発明の実施の形態にかかる分岐予測装置３３を備えるマイクロプロセッサ１０を示す。マイクロプロセッサ１０は、図１に示すように、命令メモリ１、実行ユニット２、フェッチアドレス制御ユニット３等を備えて構成されている。

命令メモリ１は、実行ユニット２に実行させる複数の命令を格納している。個々の命令には、当該命令を指定するためのアドレスが付されている。そして、当該アドレスを指定することにより、当該アドレスに対応する命令を指定できる。

実行ユニット２は、命令メモリ１から入力された命令を実行する。実行ユニット２は、複数の処理ユニット（図示省略）を有している。複数の処理ユニットは、同時並行的に命令を実行する。これにより、実行ユニット２は、複数の命令を同時並行的に実行する（パイプライン処理）。
また、実行ユニット２は、実行ＰＣ、実行結果、分岐方向をフェッチアドレス制御ユニット３に入力する。
ここで、実行ＰＣとは、実行する命令が格納されている命令メモリ１上のアドレスである。
また、分岐方向とは、実行結果が分岐成立であった場合に、分岐する方向である。具体的には、分岐方向には、プラス（第１の方向）とマイナス（第２の方向）とがある。プラス方向への分岐とは、条件分岐命令が記憶されている命令メモリ１のアドレス値より増加するアドレス値への分岐を意味し、マイナス方向への分岐とは、条件分岐命令が記憶されている命令メモリ１のアドレス値より減少するアドレス値への分岐を意味する。
また、実行結果は、条件分岐命令の実行結果であり、分岐成立か否かについての情報、分岐先ＰＣ３４２が含まれる。分岐先ＰＣ３４２とは、実行ユニット２が条件分岐命令を実行した結果、分岐成立であった場合に、次に実行する命令のアドレスである。

フェッチアドレス制御ユニット３は、ＰＣ（プログラムカウンタ；アドレス指定部）３０、加算器３１、セレクタ３２、分岐予測装置３３を備えている。

ＰＣ３０は、実行ユニット２が次に実行する命令の命令メモリ１上のアドレスを保持するレジスタである。そして、フェッチアドレス制御ユニット３は、ＰＣ３０に保持されているアドレス（以下、保持アドレス１００と称する。）を命令メモリ１に入力する。そして、命令メモリ１において、当該保持アドレス１００に基づいて命令が読み出される。そして、実行ユニット２が当該命令を命令メモリ１からフェッチして実行する。
また、フェッチアドレス制御ユニット３は、ＰＣ３０に保持されている保持アドレス１００を実行ユニット２に入力する。
また、ＰＣ３０は、保持している保持アドレス１００を分岐予測装置３３及び加算器３１に入力する。

加算器３１は、ＰＣ３０から入力される保持アドレス１００に加算処理を行って、セレクタ３２に入力する。ここで、加算処理とは、具体的には、アドレスのインクリメント処理である。
セレクタ３２は、分岐予測装置３３から入力される予測ＰＣと、加算器３１から入力されるアドレスとの何れか一方を選択してＰＣ３０に入力する。ここで、予測ＰＣとは、分岐予測装置３３によって、次に実行ユニット２により実行される命令であると予測された命令の命令メモリ１上のアドレスである。
また、セレクタ３２には、分岐予測装置３３から、分岐予測した結果が分岐成立か否かを示す成立可否信号２００が入力される。例えば、分岐予測装置３３は、分岐予測した結果が分岐成立であった場合には、成立可否信号２００として、「１」をセレクタ３２に入力する。また、分岐予測装置３３は、分岐予測した結果が分岐不成立であった場合は、成立可否信号２００として、「０」をセレクタ３２に入力する。
そして、セレクタ３２は、分岐予測装置３３が分岐予測を行わない場合、及び、条件分岐命令の分岐条件の成立可能性を予測した結果が不成立であった場合に、加算器３１から入力されるアドレスを選択する。
また、セレクタ３２は、条件分岐命令の分岐条件の成立可能性を予測した結果が成立であった場合に、分岐予測装置３３から入力された予測ＰＣを選択する。

分岐予測装置３３は、分岐予測エントリ部３４（記憶手段）、予測ＰＣ出力部３５、エントリ更新部３６を備えている。
分岐予測エントリ部３４は、分岐予測装置３３が分岐予測を行って得られる予測情報３４３を記憶している。具体的には、分岐予測エントリ部３４は、図２に示すように、エントリ番号、分岐元ＰＣ３４１、分岐先ＰＣ３４２、予測情報３４３を対応付けて記憶している。
具体的には、分岐予測エントリ部３４は、分岐元ＰＣ３４１、分岐先ＰＣ３４２、予測情報３４３をセットとして格納する記憶部である。また、分岐予測エントリ部３４は、ひとつの実施形態としてレジスタで構成されている。そして、分岐予測エントリ部３４は、分岐元ＰＣ３４１、分岐先ＰＣ３４２、予測情報３４３のセットを格納するため、レジスタＮ個（Ｎは整数）で構成されている。また、レジスタにはエントリ番号１からＮが付与されている。そして、エントリ番号を指定することにより、レジスタを指定して、当該レジスタに対して読み書きが行われる。分岐予測エントリ３４に、より多くの上記セットを格納する場合には、分岐予測エントリ３４をメモリにより構成してもよい。その場合には、エントリ番号に代わる番号としてメモリアドレスにより指定が行われることとしてもよい。
また、分岐元ＰＣ３４１とは、分岐予測装置３３が分岐予測を行った条件分岐命令の命令メモリ１上のアドレスである。具体的には、分岐元ＰＣ３４１は、実行ユニット２から入力された実行ＰＣである。
また、分岐先ＰＣ３４２とは、分岐元ＰＣ３４１の条件分岐命令の分岐先の命令のアドレスである。
また、予測情報３４３とは、条件分岐命令の実行結果が分岐成立であるか否かについて分岐予測装置３３が予測した情報である。具体的には、予測情報３４３は、実行ユニット２から入力された実行結果及び分岐方向に基づいて、分岐予測エントリ部３４に記憶される。

予測ＰＣ出力部３５は、分岐予測装置３３により、条件分岐命令の実行結果が分岐成立であると予測された場合に、分岐先ＰＣ３４２を予測ＰＣとしてセレクタ３２に入力する。
また、予測ＰＣ出力部３５は、分岐予測装置３３により、条件分岐命令の実行結果が分岐成立であると予測された場合に、分岐予測した結果が分岐成立である旨を示す成立可否信号２００をセレクタ３２に入力する。
また、予測ＰＣ出力部３５は、分岐予測装置３３により、条件分岐命令の実行結果が分岐不成立であると予測された場合に、分岐予測した結果が分岐不成立である旨を示す成立可否信号２００をセレクタ３２に入力する。
具体的には、予測ＰＣ出力部３５は、ＰＣ３０に保持されている保持アドレス１００が分岐予測エントリ部３４に分岐元ＰＣ３４１として記憶されているか否かを判断する。また、予測ＰＣ出力部３５は、ＰＣ３０に保持されている保持アドレス１００が分岐予測エントリ部３４の分岐元ＰＣ３４１として記憶されていると判断した場合に、当該分岐元ＰＣ３４１と対応する予測情報３４３が分岐成立か否かを判断する。そして、予測ＰＣ出力部３５は、当該分岐元ＰＣ３４１と対応する予測情報３４３が分岐成立であると判断した場合に、当該分岐元ＰＣ３４１と対応する分岐先ＰＣ３４２を予測ＰＣとしてセレクタ３２に入力する。また、予測ＰＣ出力部３５は、当該分岐元ＰＣ３４１と対応する予測情報３４３が分岐成立であると判断した場合に、分岐予測した結果が分岐成立である旨を示す成立可否信号２００（例えば、「１」）をセレクタ３２に入力する。
また、予測ＰＣ出力部３５は、ＰＣ３０に保持されている保持アドレス１００が分岐予測エントリ３４に分岐元ＰＣとして記憶されており、且つ、当該分岐元ＰＣ３４１と対応する予測情報３４３が分岐不成立であると判断した場合に、分岐予測した結果が分岐不成立である旨を示す成立可否信号２００（例えば、「０」）をセレクタ３２に入力する。

エントリ更新部３６は、実行ユニット２から入力される実行ＰＣ、実行結果、分岐方向に基づいて分岐予測エントリ部３４を更新する。
また、エントリ更新部３６は、新たな条件分岐命令が実行ユニット２により実行された場合に、実行ユニット２から入力される実行ＰＣ、実行結果、分岐方向に基づいて、分岐予測エントリ部３４への初期登録を行う。
ここで、実行ＰＣとは、実行ユニット２により実行された条件分岐命令の命令メモリ１上のアドレスである。実行ＰＣは、エントリ更新部３６により、分岐予測エントリ３４へ分岐元ＰＣとして登録される。
また、実行結果は、分岐成立か否かについての情報、分岐先ＰＣ３４２の情報が含まれる。分岐先ＰＣ３４２とは、実行ユニット２が条件分岐命令を実行した結果、分岐成立であった場合に、次に実行する命令の命令メモリ１上のアドレスである。

具体的には、エントリ更新部３６は、実行ユニット２から入力された実行ＰＣが分岐予測エントリ部３４に分岐元ＰＣ３４１として記憶されているか否かを判断する。
そして、エントリ更新部３６は、実行ＰＣが分岐予測エントリ部３４に分岐元ＰＣ３４１として記憶されていないと判断した場合には、実行結果が分岐成立か否かを判断する。
実行結果が分岐不成立である場合には、エントリ更新部３６は、分岐予測エントリ部３４への初期登録を行わない。
また、実行結果が分岐成立である場合には、エントリ更新部３６は、分岐予測エントリ部３４への初期登録を行う。具体的には、まず、エントリ更新部３６は、分岐方向がプラスか否かを判断する。

分岐方向がプラスである場合には、エントリ更新部３６は、分岐不成立を示す予測情報３４３を、当該実行ＰＣと対応付けて、分岐予測エントリ部３４に記憶する。より具体的には、分岐方向がプラスである場合には、エントリ更新部３６は、当該実行ＰＣを分岐元ＰＣ３４１として分岐予測エントリ部３４に記憶する。また、エントリ更新部３６は、分岐不成立を示す予測情報３４３を分岐予測エントリ部３４に記憶する。また、エントリ更新部３６は、実行結果に基づいて、分岐先ＰＣ３４２を分岐予測エントリ部３４に記憶する。

また、分岐方向がマイナスである場合には、エントリ更新部３６は、分岐成立を示す予測情報３４３を、当該実行ＰＣと対応付けて、分岐予測エントリ部３４に記憶する。より具体的には、分岐方向がマイナスである場合には、エントリ更新部３６は、当該実行ＰＣを分岐元ＰＣ３４１として分岐予測エントリ部３４に記憶する。また、エントリ更新部３６は、分岐成立を示す予測情報３４３を分岐予測エントリ部３４に記憶する。また、エントリ更新部３６は、実行結果に基づいて、分岐先ＰＣ３４２を分岐予測エントリ部３４に記憶する。

一方、エントリ更新部３６は、実行ＰＣが分岐予測エントリ部３４に分岐元ＰＣ３４１として記憶されていると判断した場合には、分岐予測エントリ部３４を更新する。
まず、エントリ更新部３６は、実行結果が分岐成立か否かを判断する。実行結果が分岐成立である場合には、エントリ更新部３６は、分岐方向がプラスか否かを判断する。

分岐方向がプラスである場合には、エントリ更新部３６は、分岐不成立を示す予測情報３４３を分岐予測エントリ部３４に記憶する。これにより、分岐予測エントリ部３４が更新される。なお、初期登録において、分岐先ＰＣ３４２は分岐予測エントリ部３４に記憶されているため、更新時においては、エントリ更新部３６は、分岐先ＰＣ３４２を分岐予測エントリ部３４に再登録する処理は行わない。

また、分岐方向がマイナスである場合には、エントリ更新部３６は、分岐成立を示す予測情報３４３を分岐予測エントリ部３４に記憶する。これにより、分岐予測エントリ部３４が更新される。

また、実行結果が分岐不成立である場合には、エントリ更新部３６は、分岐不成立を示す予測情報３４３を分岐予測エントリ部３４に記憶する。これにより、分岐予測エントリ部３４が更新される。

次に、本発明にかかる分岐予測装置３３における分岐予測エントリ部３４の初期登録について図３に示すフローチャートを参照しながら説明する。
まず、実行ユニット２により、命令メモリ１から入力された条件分岐命令が実行される（ステップＳ１）。
次に、エントリ更新部３６は、実行ユニット２から入力された実行結果が分岐成立であるか否かを判断する（ステップＳ２）。

ステップＳ２において、エントリ更新部３６が、実行結果が分岐不成立であると判断した場合には（ステップＳ２；Ｎｏ）、分岐予測装置３３は、初期登録を行わずに処理を終了する。
ステップＳ２において、エントリ更新部３６が、実行結果が分岐成立であると判断した場合には（ステップＳ２；Ｙｅｓ）、エントリ更新部３６は、分岐方向がプラスか否かを判断する（ステップＳ３）。

ステップＳ３において、エントリ更新部３６が、分岐方向がマイナスであると判断した場合には（ステップＳ３；Ｎｏ）、エントリ更新部３６は、分岐予測エントリ部３４への登録を開始する（ステップＳ４）。具体的には、エントリ更新部３６は、実行ユニット２から入力された実行ＰＣを分岐元ＰＣ３４１として分岐予測エントリ部３４に記憶させる。

次いで、エントリ更新部３６は、分岐成立を示す予測情報３４３を分岐予測エントリ部３４に記憶させる（ステップＳ５）。また、エントリ更新部３６は、分岐先の命令の命令メモリ１上のアドレスを分岐先ＰＣ３４２として分岐予測エントリ部３４に記憶させる。

ステップＳ３において、エントリ更新部３６が、分岐方向がプラスであると判断した場合には（ステップＳ３；Ｙｅｓ）、エントリ更新部３６は、分岐予測エントリ部３４への登録を開始する（ステップＳ６）。具体的には、エントリ更新部３６は、実行ユニット２から入力された実行ＰＣを分岐元ＰＣ３４１として分岐予測エントリ部３４に記憶させる。

次いで、エントリ更新部３６は、分岐不成立を示す予測情報３４３を分岐予測エントリ部３４に記憶させる（ステップＳ７）。また、エントリ更新部３６は、分岐先の命令の命令メモリ１上のアドレスを分岐先ＰＣ３４２として分岐予測エントリ部３４に記憶させる。

以上に説明した本発明の実施の形態にかかる分岐予測装置３３、分岐予測方法、及びマイクロプロセッサ１０では、条件分岐命令の分岐条件が成立するか否かについての予測情報３４３を格納する分岐予測エントリ部３４と、条件分岐命令の実行により分岐条件が成立した場合に、分岐方向に基づいて条件分岐命令が次回実行される際の分岐条件の成立可能性を予測し、予測情報３４３を更新するエントリ更新部３６と、を備える。
具体的には、条件分岐命令の実行結果が分岐成立であった際に、分岐方向がプラスである場合に、分岐不成立を示す予測情報３４３を分岐予測エントリ部３４に記憶させ、分岐方向がマイナスである場合に、分岐成立を示す予測情報３４３を分岐予測エントリ部３４に記憶させる。
これにより、本発明の実施の形態にかかる分岐予測装置３３、分岐予測方法、及びマイクロプロセッサ１０では、分岐方向に基づいて前記条件分岐命令が次回実行される際の分岐条件の成立可能性を予測するので、従来のように単に前回の条件分岐命令の実行結果に基づいて次回の条件分岐命令の分岐条件の成立可能性を予測する場合に比べて、より正確に分岐予測を行うことができる。そのため、本発明の実施の形態にかかる分岐予測装置３３を備えたマイクロプロセッサ１０では、実行サイクル数を低減でき、処理速度を向上することができる。
また、特別なカウンタなどを設ける必要がないため、回路構成をより簡便なものとすることができる。
また、条件分岐命令の実行回数が少なくても、正確に分岐予測を行うことができる。条件分岐命令の実行結果が分岐成立であった際に、分岐方向に基づいて次回の条件分岐命令の分岐条件の成立可能性を予測する。分岐方向に基づいて条件分岐命令の分岐条件の成立可能性を予測するので、従来のように単に前回の条件分岐命令の実行結果に基づいて次回の条件分岐命令の分岐条件の成立可能性を予測する場合に比べて、より正確に分岐予測を行うことができる。

また、分岐予測装置３３では、条件分岐命令の分岐条件が不成立であった際に、条件分岐命令の予測情報３４３が分岐予測エントリ部３４に格納されている場合には、不成立を示す予測情報３４３に予測情報を更新する。
これにより、分岐予測エントリ部３４の予測情報３４３に条件分岐命令の実行結果を反映することができる。

さらに、分岐予測装置３３では、分岐方向がプラスかマイナスかによって、分岐予測を行うことにより、複数周期繰り返して実行されるループ内に含まれる条件分岐命令であっても正確に予測することができる。具体的には、複数周期繰り返して実行されるループ内の条件分岐命令の実行結果は、最後のループ回数のみ分岐成立となり、分岐方向がプラスとなる場合がある。その場合に、分岐予測装置３３では、分岐方向がプラスであることを反映して、当該条件分岐命令の予測情報３４３を分岐不成立とする。そのため、次回の最初のループ回数の実行結果が分岐不成立となることを正確に予測することができる。

なお、予測情報３４３は、２ビットのデータから構成されてもよい。そして、分岐予測エントリ部３４に、予測情報３４３として、１１（分岐する可能性大（Ｓｔｒｏｎｇｌｙ Ｔａｋｅｎ））、１０（分岐する可能性小（Ｗｅａｋｌｙ Ｔａｋｅｎ））、０１（分岐しない可能性小（Ｗｅａｋｌｙ Ｎｏｔ Ｔａｋｅｎ））、００（分岐しない可能性大（Ｓｔｒｏｎｇｌｙ Ｎｏｔ Ｔａｋｅｎ））の４つの値が記憶されてもよい。この場合、分岐予測装置３３は、予測情報３４３が１１又は１０のとき分岐成立と判断し、予測情報３４３が０１又は００のとき分岐不成立と判断する。

次に、本発明の実施例１について、比較例１及び比較例２と比較して説明する。実施例１にかかるマイクロプロセッサ１０は、本発明の実施の形態にかかる分岐予測装置３３を有するマイクロプロセッサ１０である。

これに対し、分岐予測装置を持たないマイクロプロセッサを比較例１とする。また、従来の分岐予測装置を有するマイクロプロセッサを比較例２とする。
従来の分岐予測装置では、新たな条件分岐命令が実行された際、条件分岐命令の実行結果が分岐成立の場合にのみ、当該実行結果を予測情報として分岐予測エントリ部に初期登録する。比較例２にかかる分岐予測装置における分岐予測エントリ部の初期登録について図４に示すフローチャートを参照しながら説明する。

まず、比較例２にかかるマイクロプロセッサの実行ユニットにより、命令メモリから入力された条件分岐命令が実行される（ステップＳ１０１）。
次に、分岐予測装置は、実行ユニットから入力された実行結果が分岐成立であるか否かを判断する（ステップＳ１０２）。

ステップＳ１０２において、分岐予測装置が、実行結果が分岐不成立であると判断した場合には（ステップＳ１０２；Ｎｏ）、分岐予測装置は、初期登録を行わずに処理を終了する。
ステップＳ１０２において、分岐予測装置が、実行結果が分岐成立であると判断した場合には（ステップＳ１０２；Ｙｅｓ）、分岐予測装置は、分岐予測エントリ部への登録を開始する（ステップＳ１０３）。

次いで、分岐予測装置は、分岐成立を示す予測情報を分岐予測エントリ部に記憶させる（ステップＳ１０４）。

次に、図５に示すプログラムを実行する場合に、比較例１、比較例２、実施例１において要する実行サイクル数を比較する。
図５に示すように、当該プログラムは、Ｉ１、Ｉ２、Ｉ３、Ｉ４の４つの命令を含み、当該Ｉ１〜Ｉ４の命令が複数周期繰り返して実行されるループ構造を有している。そして、ループは、条件分岐命令Ｉ３を有している。また、図５において、Ｎ１の「ｘ４」は、プログラム記述ではないが、Ｉ１〜Ｉ４のループを４回繰り返すことを示している。即ち、条件分岐命令Ｉ３の実行結果は、ループ回数４回目までは不成立であり、ループ回数５回目に成立となる。従って、図５に示すループが実行される回数（ループ回数）は５回である。
より具体的には、図５において、Ｌ１は、無条件分岐命令であるＩ４の分岐先を表すラベルである。Ｉ１は、加算命令を表す。Ｉ２は、比較命令を表す。Ｉ３は、条件分岐命令を表す。Ｉ３の条件分岐命令では、Ｉ２の比較命令で比較した結果を元に分岐が成立するかどうかが決まる。Ｉ４は無条件分岐命令であり、Ｌ１に分岐することを示す。Ｌ２は、条件分岐命令Ｉ３の分岐先ラベルである。また、ループ回数が５回目の場合に、条件分岐命令Ｉ３の実行結果が分岐成立となって、ループ外の命令（ラベルＬ２に対応する命令）に分岐する。

図５に示すループ回数５回のループを２周期実行した場合に、比較例１、比較例２、実施例１において要する実行サイクル数をそれぞれ表３、表４、表５に示す。表３、表４、表５において、Ｔは分岐成立（Ｔａｋｅｎ）、Ｎは分岐不成立（Ｎｏｔ Ｔａｋｅｎ）を示す。また、表４、表５において、Ｍは予測ミス（Ｍｉｓｓ）、Ｈは予測正解（Ｈｉｔ）を示す。表３、表４、表５に示すように、図５に示すループ回数５回のループを２周期実行した場合、条件分岐命令Ｉ３の実行結果は、ＮＴ、ＮＴ、ＮＴ、ＮＴ、Ｔ（＋）、ＮＴ、ＮＴ、ＮＴ、ＮＴ、Ｔ（＋）となる。ここで、Ｔ（＋）の（＋）は、分岐方向がプラスであることを示す。

表３に示すように、分岐予測を行わない比較例１では、条件分岐命令Ｉ３の実行結果が分岐不成立のときの実行サイクル数は１であり、条件分岐命令Ｉ３の実行結果が分岐成立のときの実行サイクル数は５である。そして、合計サイクル数は１８となる。
一方、表４に示すように、従来の分岐予測を行う比較例２では、１周期目のループにおいて、条件分岐命令Ｉ３の実行結果が分岐成立の場合にのみ、当該実行結果が予測情報として分岐予測エントリ部に初期登録される。即ち、１周期目のループの５回目の実行後初めて、実行結果Ｔが予測情報として登録される。そして、２周期目のループの１回目の実行結果はＮＴだが、予測情報はＴとなっているため、予測が不正解となる。そして、表４に示すように、予測が正解のときの実行サイクル数は１であり、予測が不正解のときの実行サイクル数は５である。そして、合計サイクル数は２２となり、分岐予測を行わない比較例１に比べて実行サイクル数が増えてしまう。

これに対して、本発明にかかる分岐予測を行う実施例１では、１周期目のループの５回目の実行後初めて、分岐方向に基づく予測情報３４３が登録される。具体的には、１周期目のループの５回目の分岐方向はプラスであるため、分岐不成立を示すＮＴが予測情報３４３として分岐予測エントリ部３４に登録される。そして、２周期目のループの１回目の実行結果はＮＴであるので、予測が正解となる。そのため、２周期目のループの１回目の実行サイクル数は１となる。そして、合計サイクル数は１８となり、分岐予測を行わない比較例１と実行サイクル数が同じになる。

以上、説明したように、図５に示すように、複数周期繰り返して実行されるループ内に含まれる条件分岐命令であっても、実施例１では実行サイクル数が増えない。図５に示すように、複数周期繰り返して実行されるループ内に含まれる条件分岐命令は、プログラム中で比較的よく見られる。従って、本発明にかかる実施例１では、図５に示すようなループ内に含まれる条件分岐命令の分岐予測を正確に行うことにより、大幅に実行サイクル数を低減することができる。即ち、本発明にかかる実施例１により、マイクロプロセッサ１０の処理速度を向上させることができる。

本発明の実施の形態にかかるマイクロプロセッサの概略構成を示す回路図である。 本発明の実施の形態にかかる分岐予測エントリ部の一例を示す図である。 本発明の実施の形態にかかる分岐予測装置における初期登録の一例を説明するフローチャートである。 比較例２にかかる分岐予測装置における初期登録を説明するフローチャートである。 条件分岐命令を含み、複数周期繰り返して実行されるループの一例を説明する図である。 従来技術における予測情報の遷移を説明する図である。

符号の説明

１ 命令メモリ
３ フェッチアドレス制御ユニット
３０ ＰＣ（アドレス指定部）
３３ 分岐予測装置
３４ 分岐予測エントリ部
３４３ 予測情報
３５ 予測ＰＣ出力部
３６ エントリ更新部
１０ マイクロプロセッサ

Claims (20)

1. 命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測装置であって、
   前記条件分岐命令の前記分岐条件が成立するか否かについての予測情報を格納する分岐予測エントリ部と、
   前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の前記分岐条件の成立可能性を予測し、前記予測情報を更新するエントリ更新部と、
   を備える分岐予測装置。
2. 前記分岐予測エントリ部は、前記命令メモリに格納された前記条件分岐命令のアドレスと、前記条件分岐命令の前記分岐条件が成立するか否かについての前記予測情報と、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスと、を対応付けて格納する請求項１に記載の分岐予測装置。
3. 前記命令メモリは、複数の前記条件分岐命令を格納し、
   前記分岐予測エントリ部は、前記条件分岐命令毎に、前記条件分岐命令のアドレスと、前記予測情報と、前記分岐先の命令のアドレスと、を格納する請求項１又は２に記載の分岐予測装置。
4. 前記エントリ更新部には、前記条件分岐命令が実行された場合に、前記条件分岐命令のアドレスと、前記条件分岐命令の実行結果と、前記分岐方向と、が入力され、
   前記実行結果は、前記条件分岐命令の前記分岐条件が成立したか否かについての情報と、前記分岐条件が成立した場合の前記分岐先の命令アドレスとを含み、
   前記エントリ更新部は、入力された前記条件分岐命令のアドレスと、前記実行結果と、前記分岐方向と、に基づいて、前記条件分岐命令のアドレスと、前記条件分岐命令の前記予測情報と、前記分岐先の命令のアドレスと、を前記分岐予測エントリ部に出力する請求項２又は３に記載の分岐予測装置。
5. 前記分岐予測装置は、前記命令メモリのアドレスを指定するアドレス指定部に前記予測情報を出力する予測ＰＣ出力部を備え、
   前記予測ＰＣ出力部は、前記分岐予測エントリ部に格納されている前記予測情報が成立である場合に、当該予測情報と対応する前記分岐先の命令のアドレスを前記アドレス指定部に出力する請求項２乃至４の何れか一項に記載の分岐予測装置。
6. 前記エントリ更新部は、前記条件分岐命令が実行された結果、前記分岐条件が不成立であった際に、前記条件分岐命令の前記予測情報が前記分岐予測エントリ部に格納されている場合には、不成立を示す予測情報に前記予測情報を更新する請求項１乃至５の何れか一項に記載の分岐予測装置。
7. 前記分岐方向が第１の方向である場合には、次回の前記条件分岐命令の前記分岐条件が不成立であると予測し、前記分岐方向が第２の方向である場合には、次回の前記条件分岐命令の前記分岐条件が成立であると予測する請求項１乃至６の何れか一項に記載の分岐予測装置。
8. 前記第１の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより増加する分岐方向であり、
   前記第２の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより減少する分岐方向である請求項７に記載の分岐予測装置。
9. 命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測装置を備えるマイクロプロセッサであって、
   前記分岐予測装置は、
   前記条件分岐命令の前記分岐条件が成立するか否かについての予測情報を格納する分岐予測エントリ部と、
   前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の前記分岐条件の成立可能性を予測し、前記予測情報を更新するエントリ更新部と、
   を備えるマイクロプロセッサ。
10. 前記命令メモリは、複数の前記条件分岐命令を格納し、
    前記分岐予測エントリ部は、前記条件分岐命令毎に、前記条件分岐命令のアドレスと、前記予測情報と、前記分岐先の命令のアドレスと、を対応付けて格納し、
    前記分岐予測装置は、
    前記分岐予測エントリ部に格納されている前記予測情報が成立である場合に、前記予測情報と、当該予測情報と対応する前記分岐先の命令のアドレスと、を前記マイクロプロセッサに出力する予測ＰＣ出力部と、を備え、
    前記マイクロプロセッサは、
    命令を実行する実行ユニットと、
    前記実行ユニットに実行すべき命令のアドレスを出力するフェッチアドレス制御ユニットと、
    を備え、
    前記フェッチアドレス制御ユニットは、前記予測情報が成立である場合に、前記分岐先の命令のアドレスを前記実行ユニットに出力し、
    前記実行ユニットは、前記フェッチアドレス制御ユニットから入力された前記分岐先の命令のアドレスに基づいて、前記命令メモリから命令を読み出して実行する請求項９に記載のマイクロプロセッサ。
11. 前記分岐予測装置は、
    前記分岐方向が第１の方向である場合には、次回の前記条件分岐命令の前記分岐条件が不成立であると予測し、前記分岐方向が第２の方向である場合には、次回の前記条件分岐命令の前記分岐条件が成立であると予測する請求項９又は１０に記載のマイクロプロセッサ。
12. 前記第１の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより増加する分岐方向であり、
    前記第２の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより減少する分岐方向である請求項１１に記載のマイクロプロセッサ。
13. 命令を格納する命令メモリから読み出された条件分岐命令の分岐条件の成立可能性を予測する分岐予測方法であって、
    前記条件分岐命令の前記分岐条件が成立するか否かについての予測情報を分岐予測エントリ部に格納し、
    前記条件分岐命令の実行により前記分岐条件が成立した場合に、分岐方向に基づいて前記条件分岐命令が次回実行される際の前記分岐条件の成立可能性を予測し、前記予測情報を更新する分岐予測方法。
14. 前記分岐予測エントリ部は、前記命令メモリに格納された前記条件分岐命令のアドレスと、前記条件分岐命令の前記分岐条件が成立するか否かについての前記予測情報と、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスと、を対応付けて格納する請求項１３に記載の分岐予測方法。
15. 前記命令メモリは、複数の前記条件分岐命令を格納し、
    前記分岐予測エントリ部は、前記条件分岐命令毎に、前記条件分岐命令のアドレスと、前記予測情報と、前記分岐先の命令のアドレスと、を格納する請求項１３又は１４に記載の分岐予測方法。
16. 前記条件分岐命令が実行された場合に、前記条件分岐命令のアドレスと、前記条件分岐命令の実行結果と、前記分岐方向と、が入力され、
    前記実行結果は、前記条件分岐命令の前記分岐条件が成立したか否かについての情報と、前記分岐条件が成立した場合の前記分岐先の命令アドレスとを含み、
    入力された前記条件分岐命令のアドレスと、前記実行結果と、前記分岐方向と、に基づいて、前記条件分岐命令のアドレスと、前記条件分岐命令の前記予測情報と、前記分岐先の命令のアドレスと、を前記分岐予測エントリ部に出力する請求項１４又は１５に記載の分岐予測方法。
17. 前記命令メモリのアドレスを指定するアドレス指定部に前記予測情報を出力し、
    前記分岐予測エントリ部に格納されている前記予測情報が成立である場合に、当該予測情報と対応する前記分岐先の命令のアドレスを前記アドレス指定部に出力する請求項１４乃至１６の何れか一項に記載の分岐予測方法。
18. 前記条件分岐命令が実行された結果、前記分岐条件が不成立であった際に、前記条件分岐命令の前記予測情報が前記分岐予測エントリ部に格納されている場合には、不成立を示す予測情報に前記予測情報を更新する請求項１３乃至１７の何れか一項に記載の分岐予測方法。
19. 前記分岐方向が第１の方向である場合には、次回の前記条件分岐命令の前記分岐条件が不成立であると予測し、前記分岐方向が第２の方向である場合には、次回の前記条件分岐命令の前記分岐条件が成立であると予測する請求項１３乃至１８の何れか一項に記載の分岐予測方法。
20. 前記第１の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより増加する分岐方向であり、
    前記第２の方向とは、前記条件分岐命令の前記分岐条件が成立した場合の分岐先の命令のアドレスが前記条件分岐命令のアドレスより減少する分岐方向である請求項１９に記載の分岐予測方法。

Images