(57)【要約】【課題】命令プリフェッチのためのネクストライン・プリフェッチによるペナルティを平均化して、スループットを改善する。【解決手段】実行対象となっている命令を含むキャッシュライン（現ライン）の実行中に、それに続くキャッシュライン（ネクストライン）および現ラインに含まれる分岐命令の分岐先命令を含むキャッシュライン（分岐先ライン）の両者を命令キャッシュにプリフェッチする。分岐先ラインは、命令キャッシュにおける衝突を避けるため、ネクストラインと異なるラインアドレスになるように配置される。また、現ラインの分岐命令は、両ラインのプリフェッチを完了させるまでの余裕をもたせるため、現ラインの後半部分に配置される。【選択図】図３０
2011209903.tif 000002
【特許請求の範囲】
【請求項１】
実行対象となる命令のアドレスを管理するプログラムカウンタと、
命令キャッシュのキャッシュラインにおける所定の範囲の命令アドレスを前記プログラムカウンタが示す場合に前記命令キャッシュへの命令のプリフェッチタイミングを検出するプリフェッチタイミング検出部と、
前記プリフェッチタイミングが検出されると前記プログラムカウンタが示すキャッシュラインの次のキャッシュラインであるネクストキャッシュラインおよび予め定められた他のキャッシュラインの両方をプリフェッチするプリフェッチ部と
を具備する命令フェッチ装置。
【請求項２】
前記他のキャッシュラインは、前記ネクストキャッシュラインとは異なるラインアドレスを有する請求項１記載の命令フェッチ装置。
【請求項３】
前記他のキャッシュラインは、前記プログラムカウンタが示すキャッシュラインに含まれる分岐命令の分岐先命令を含む請求項２記載の命令フェッチ装置。
【請求項４】
前記他のキャッシュラインの先頭の命令アドレスを保持するプリフェッチアドレスレジスタをさらに具備する請求項３記載の命令フェッチ装置。
【請求項５】
実行対象となる命令のアドレスを管理するプログラムカウンタと、
命令キャッシュのキャッシュラインにおける所定の範囲の命令アドレスを前記プログラムカウンタが示す場合に前記命令キャッシュへの命令のプリフェッチタイミングを検出するプリフェッチタイミング検出部と、
前記プリフェッチタイミングが検出されると前記プログラムカウンタが示すキャッシュラインの次のキャッシュラインであるネクストキャッシュラインおよび予め定められた他のキャッシュラインの両方をプリフェッチするプリフェッチ部と、
前記ネクストキャッシュラインおよび前記他のキャッシュラインの何れか一方に含まれる命令を実行する実行部と
を具備するプロセッサ。
【請求項６】
前記他のキャッシュラインを保持するプリフェッチキューをさらに具備し、
前記実行部は、前記他のキャッシュラインに分岐する際には前記プリフェッチキューから命令を読み出して実行する
請求項５記載のプロセッサ。
【請求項７】
記録媒体に保持されたプログラムの中から分岐命令を抽出する分岐命令抽出部と、
前記抽出された分岐命令をキャッシュラインの後半に配置する分岐命令配置部と、
前記抽出された分岐命令の分岐先命令を前記キャッシュラインの次のキャッシュラインとは異なるラインアドレスを有する他のキャッシュラインに配置する分岐先命令配置部と、
前記分岐命令および前記分岐先命令を含む命令列を記録媒体に出力する命令列出力部と
を具備するプログラム変換装置。
【請求項８】
前記分岐命令配置部は、前記抽出された分岐命令をキャッシュラインの最後尾に配置する請求項７記載のプログラム変換装置。
【請求項９】
記録媒体に保持されたプログラムの中から分岐命令を抽出する分岐命令抽出手順と、
前記抽出された分岐命令をキャッシュラインの後半に配置する分岐命令配置手順と、
前記抽出された分岐命令の分岐先命令を前記キャッシュラインの次のキャッシュラインとは異なるラインアドレスを有する他のキャッシュラインに配置する分岐先命令配置手順と、
前記分岐命令および前記分岐先命令を含む命令列を記録媒体に出力する命令列出力手順と
を具備するプログラム変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、命令フェッチ装置に関し、特に分岐命令を含む命令列をプリフェッチするための命令フェッチ装置、プロセッサ、プログラム変換装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。
【背景技術】
【０００２】
パイプライン化されたＣＰＵ（Central Processing Unit：プロセッサ）の処理能力を最大限に引き出すためには、パイプライン内の命令を滞らないよう流れ続けさせることが理想的である。この理想状態を保つためには、次に処理されるべき命令が格納されているメモリから命令を予めＣＰＵまたは命令キャッシュにフェッチしておく必要がある。しかし、プログラムに分岐命令が含まれる場合、分岐命令の次に実行すべき命令の番地が分岐命令実行時まで確定しない。そのため、命令フェッチが待たされてパイプラインストールが発生し、命令実行のスループットが低下する。そのため、分岐による不確定要素がありながらプリフェッチを行って、パイプラインストールの発生を抑えるために工夫をしているＣＰＵが多くある。
【０００３】
単純なハードウェアにより実現できるものとして典型的なプリフェッチがネクストライン・プリフェッチである（例えば、特許文献１参照。）。これは、プログラムの順番通りに命令をプリフェッチしてくる手法である。プロセッサの命令フェッチでは、連続的に番地が増加する方向にメモリをアクセスするというのが基本的なメモリアクセスパターンである。このため、ハードウェアによるプリフェッチは、ある番地の命令をキャッシュに格納した後に、その次のキャッシュラインも使われるという見込みのもとに、自動的に次のキャッシュラインも格納するという方法である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４３２７２３７号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述のネクストライン・プリフェッチは、単純なハードウェア構成で実現できる反面、分岐しないことを前提としてプリフェッチをするため、多くの場合で無駄なプリフェッチ、すなわちプリフェッチミスが生じてしまう。このようなプリフェッチミスが起こるとプリフェッチしておいた命令を破棄して、再度正しい分岐先の命令をフェッチするため、ＣＰＵが待たされるという時間面のデメリットがある。それに加えて、余分なデータの読み書きを行うため、メモリアクセスが増加し、電力面でのロスも生じる。さらに、頻繁なプリフェッチや無駄なプリフェッチはデータパスのトラフィックを混雑させるという問題もある。
【０００６】
プリフェッチミスを減らす他の試みとして、分岐予測を用いるものがある。ネクストライン・プリフェッチは常に分岐しないことを予測してネクストラインをプリフェッチしているが、過去の履歴から分岐方向を予測して、予測した方の番地をプリフェッチするという方法である。分岐予測は複雑であり、履歴テーブルなどの回路面積の大きなハードウェアが必要である。しかし、分岐予測によって達成される性能利益は、予測アルゴリズムの効率に依存し、その予測アルゴリズムの多くは、相対的に大容量の記憶装置と、複雑なハードウェアとで実装する必要がある。分岐予測も予測が外れた場合にはネクストライン・プリフェッチと同様なペナルティが発生する。実際のプログラムの大半では、ループ処理や例外処理など各分岐先への分岐比率は偏りが大きいため、分岐予測によるメリットがデメリットを上回ることが多い。しかし、アプリケーションによってはどのような予測アルゴリズムを用いたとしても予測性能を上げることが困難なものがあり、特にコーデックではループ以外の予測が当たりにくい傾向がある。予測のヒット率は向上させなければならないが、そのための機構は複雑かつ大規模になる反面、必ずしも回路規模に見合う性能改善が得られるとは限らない。
【０００７】
一方向のみのプリフェッチを行う上述の方法と違って、予測をせず、分岐先の両方向をプリフェッチしておいてプリフェッチミスを解消する手法も考えられている。この場合、分岐予測の手法に比べ、少ないハードウェア構成追加でパイプラインストールを解消することができる。しかし、プリフェッチのための格納データ量が単純に倍増するだけでなく、不要なデータを必ず読むことになり、データパス混雑度が高まることによる悪影響や、冗長回路追加による複雑化や、電力面のロスも無視できない。
【０００８】
以上のように、どのようにプリフェッチをするか、それぞれデメリット（ＣＰＵ実装コスト、分岐予測処理のオーバーヘッド）とメリット（期待されるスループット向上）があり、コストと性能のトレードオフが存在する。
【０００９】
本発明はこのような状況に鑑みてなされたものであり、分岐命令に関する情報を利用して、命令プリフェッチを制御することを目的とする。
【００１０】
本発明はこのような状況に鑑みてなされたものであり、命令プリフェッチのためのネクストライン・プリフェッチによるペナルティを平均化して、スループットを改善することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、実行対象となる命令のアドレスを管理するプログラムカウンタと、命令キャッシュのキャッシュラインにおける所定の範囲の命令アドレスを上記プログラムカウンタが示す場合に上記命令キャッシュへの命令のプリフェッチタイミングを検出するプリフェッチタイミング検出部と、上記プリフェッチタイミングが検出されると上記プログラムカウンタが示すキャッシュラインの次のキャッシュラインであるネクストキャッシュラインおよび予め定められた他のキャッシュラインの両方をプリフェッチするプリフェッチ部とを具備する命令フェッチ装置である。これにより、命令キャッシュラインの所定の範囲の命令アドレスの命令が実行されるタイミングにおいてネクストキャッシュラインおよび他のキャッシュラインの両方をプリフェッチするという作用をもたらす。
【００１２】
また、この第１の側面において、上記他のキャッシュラインは、上記ネクストキャッシュラインとは異なるラインアドレスを有するキャッシュラインとすることができる。これにより、命令キャッシュにおける衝突を回避させるという作用をもたらす。
【００１３】
また、この第１の側面において、上記他のキャッシュラインは、上記プログラムカウンタが示すキャッシュラインに含まれる分岐命令の分岐先命令を含んでもよい。これにより、ネクストキャッシュラインおよび分岐先のキャッシュラインの両方をプリフェッチするという作用をもたらす。
【００１４】
また、この第１の側面において、上記他のキャッシュラインの先頭の命令アドレスを保持するプリフェッチアドレスレジスタをさらに具備してもよい。これにより、プリフェッチアドレスレジスタに示されるキャッシュラインおよびネクストキャッシュラインの両方をプリフェッチするという作用をもたらす。
【００１５】
また、本発明の第２の側面は、実行対象となる命令のアドレスを管理するプログラムカウンタと、命令キャッシュのキャッシュラインにおける所定の範囲の命令アドレスを上記プログラムカウンタが示す場合に上記命令キャッシュへの命令のプリフェッチタイミングを検出するプリフェッチタイミング検出部と、上記プリフェッチタイミングが検出されると上記プログラムカウンタが示すキャッシュラインの次のキャッシュラインであるネクストキャッシュラインおよび予め定められた他のキャッシュラインの両方をプリフェッチするプリフェッチ部と、上記ネクストキャッシュラインおよび上記他のキャッシュラインの何れか一方に含まれる命令を実行する実行部とを具備するプロセッサである。これにより、命令キャッシュラインの所定の範囲の命令アドレスの命令が実行されるタイミングにおいてネクストキャッシュラインおよび他のキャッシュラインの両方をプリフェッチして、何れか一方に含まれる命令を実行するという作用をもたらす。
【００１６】
また、この第２の側面において、上記他のキャッシュラインを保持するプリフェッチキューをさらに具備し、上記実行部は、上記他のキャッシュラインに分岐する際には上記プリフェッチキューから命令を読み出して実行するようにしてもよい。これにより、命令パイプラインをストールさせることなく、命令を発行するという作用をもたらす。
【００１７】
また、本発明の第３の側面は、記録媒体に保持されたプログラムの中から分岐命令を抽出する分岐命令抽出部と、上記抽出された分岐命令をキャッシュラインの後半に配置する分岐命令配置部と、上記抽出された分岐命令の分岐先命令を上記キャッシュラインの次のキャッシュラインとは異なるラインアドレスを有する他のキャッシュラインに配置する分岐先命令配置部と、上記分岐命令および上記分岐先命令を含む命令列を記録媒体に出力する命令列出力部とを具備するプログラム変換装置およびそのプログラム変換方法である。これにより、ネクストキャッシュラインおよび他のキャッシュラインの両方のプリフェッチに対して衝突を発生させないという作用をもたらす。
【００１８】
また、この第３の側面において、上記分岐命令配置部は、上記抽出された分岐命令をキャッシュラインの最後尾に配置するようにしてもよい。これにより、ネクストキャッシュラインおよび他のキャッシュラインの両方のプリフェッチのための時間的余裕をもたせるという作用をもたらす。
【発明の効果】
【００１９】
本発明によれば、命令プリフェッチのためのネクストライン・プリフェッチによるペナルティを平均化して、スループットを改善することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施の形態におけるプロセッサのパイプライン構成例を示す図である。
【図２】本発明の第１の実施の形態におけるプロセッサのブロック構成例を示す図である。
【図３】本発明の第１の実施の形態における命令パケット３００の構造例を示す図である。
【図４】本発明の第１の実施の形態における命令ヘッダ３１０のフィールド構成例を示す図である。
【図５】本発明の第１の実施の形態で用いられる分岐予測フラグ３１１の設定例を示す図である。
【図６】本発明の第１の実施の形態で用いられる命令辞書テーブル参照型圧縮の適用例を示す図である。
【図７】本発明の第１の実施の形態における命令辞書テーブル参照型圧縮による分岐予測フラグ３１１の変更例を示す図である。
【図８】本発明の第１の実施の形態における命令パケット生成のための機能構成例を示す図である。
【図９】本発明の第１の実施の形態における命令パケット生成のための処理手順例を示す図である。
【図１０】本発明の第１の実施の形態における命令実行のための機能構成例を示す図である。
【図１１】本発明の第１の実施の形態における命令実行のための処理手順例を示す図である。
【図１２】本発明の第１の実施の形態における命令ヘッダ３１０のフィールド構成の変形例を示す図である。
【図１３】本発明の第２の実施の形態における分岐命令の配置と命令プリフェッチ開始位置との関係例を示す図である。
【図１４】本発明の第２の実施の形態におけるプリフェッチ開始アドレス設定レジスタを用いた構成例を示す図である。
【図１５】本発明の第２の実施の形態における命令ヘッダ３１０の命令プリフェッチタイミングフィールド３１２を用いた構成例を示す図である。
【図１６】本発明の第２の実施の形態において所定回数の命令実行をプリフェッチタイミングに利用する構成例を示す図である。
【図１７】本発明の第２の実施の形態において命令ヘッダ３１０に命令タイプおよび実行回数を設定した例を示す図である。
【図１８】本発明の第２の実施の形態における命令実行のための機能構成例を示す図である。
【図１９】本発明の第２の実施の形態における命令実行のための処理手順例を示す図である。
【図２０】本発明の第３の実施の形態におけるプログラムカウンタの加算制御処理の機能構成例を示す図である。
【図２１】本発明の第３の実施の形態における加算制御レジスタ６４０の構成例を示す図である。
【図２２】本発明の第３の実施の形態における２方向分岐による命令の処理態様例を示す図である。
【図２３】本発明の第３の実施の形態における多方向分岐による命令の処理態様例を示す図である。
【図２４】本発明の第３の実施の形態における加算制御レジスタ６４０に値を設定するための命令セットの一例を示す図である。
【図２５】本発明の第３の実施の形態において条件分岐命令により加算制御レジスタ６４０に値を設定した場合の例を示す図である。
【図２６】本発明の第３の実施の形態において制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥにより加算制御レジスタ６４０に値を設定した場合の例を示す図である。
【図２７】本発明の第３の実施の形態における命令実行のための処理手順例を示す図である。
【図２８】本発明の第４の実施の形態におけるプロセッサのパイプライン構成例を示す図である。
【図２９】本発明の第４の実施の形態におけるプロセッサのブロック構成例を示す図である。
【図３０】本発明の第４の実施の形態における分岐命令とキャッシュラインの関係を示す図である。
【図３１】本発明の第４の実施の形態における命令配置の変更の一態様を示す図である。
【図３２】本発明の第４の実施の形態における命令配置のための機能構成例を示す図である。
【図３３】本発明の第４の実施の形態における命令配置のための処理手順例を示す図である。
【図３４】本発明の第４の実施の形態におけるプリフェッチアドレスレジスタの設定例を示す図である。
【図３５】本発明の第４の実施の形態における命令実行のための機能構成例を示す図である。
【図３６】本発明の第４の実施の形態における命令実行のための処理手順例を示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（分岐予測情報を利用した命令プリフェッチの抑止制御）
２．第２の実施の形態（命令プリフェッチのタイミング制御）
３．第３の実施の形態（命令を混合配置することによる命令プリフェッチのペナルティ平均化）
４．第４の実施の形態（分岐先キャッシュラインの配置を固定化することによるキャッシュライン衝突回避）
５．各実施の形態の組合せ
【００２２】
＜１．第１の実施の形態＞
［プロセッサの構成］
図１は、本発明の第１の実施の形態におけるプロセッサのパイプライン構成例を示す図である。この例では、命令フェッチステージ（ＩＦ）１１と、命令デコードステージ（ＩＤ）２１と、レジスタフェッチステージ（ＲＦ）３１と、実行ステージ（ＥＸ）４１と、メモリアクセスステージ（ＭＥＭ）５１の５段階のパイプラインを想定している。各パイプラインは、それぞれラッチ１９、２９、３９および４９によって区切られており、クロックに同期してパイプライン処理が行われる。
【００２３】
命令フェッチステージ（ＩＦ：Instruction Fetch）１１では、命令フェッチ処理が行われる。この命令フェッチステージ１１では、プログラムカウンタ（ＰＣ）１８が加算部１２により逐次加算され、このプログラムカウンタ１８に示される命令が次の命令デコードステージ２１に供給されていく。また、この命令フェッチステージ１１では、後述する命令キャッシュを含み、この命令キャッシュへの命令プリフェッチを行う。ネクストラインプリフェッチ部１３は、現在実行対象となっている命令を含むキャッシュラインの次のキャッシュラインであるネクストラインのプリフェッチを行うためのものである。
【００２４】
命令デコードステージ（ＩＤ：Instruction Decode）２１では、命令フェッチステージ１１から供給された命令のデコード処理が行われる。この命令デコードステージ２１においてデコードされた結果は、レジスタフェッチステージ（ＲＦ）３１に供給される。また、分岐命令の場合、その分岐先アドレスがプログラムカウンタ（ＰＣ）１８に供給される。
【００２５】
レジスタフェッチステージ（ＲＦ：Register Fetch）３１では、命令実行に必要なオペランドのフェッチ処理が行われる。パイプライン型のプロセッサではオペランドアクセス対象はレジスタファイルに限定されることが多い。このレジスタフェッチステージ３１において取得されたオペランドデータは、実行ステージ（ＥＸ）４１に供給される。
【００２６】
実行ステージ（ＥＸ：EXecute）４１では、オペランドデータを用いて命令実行が行われる。例えば、算術論理演算や分岐判定処理などが行われる。この実行ステージ（ＥＸ）４１において得られた実行結果データはレジスタファイルに格納される。また、ストア命令の場合には、メモリアクセスステージ（ＭＥＭ）５１においてメモリへの書込みが行われる。
【００２７】
メモリアクセスステージ（ＭＥＭ：Memory）５１では、メモリへのアクセスが行われる。ロード命令の場合にはメモリからのリードアクセスが行われ、ストア命令の場合にはメモリへのライトアクセスが行われる。
【００２８】
図２は、本発明の第１の実施の形態におけるプロセッサのブロック構成例を示す図である。このプロセッサは、プロセッサコア１１０と、命令キャッシュ１２０と、データキャッシュ１３０と、ネクストラインプリフェッチ部１５０と、パケットデマルチプレクサ１６０とを備えている。また、このプロセッサは、さらに、プリフェッチキュー１７０と、命令キュー１８０と、命令辞書インデックス１９１と、命令辞書テーブル１９２とを備えている。また、このプロセッサには、システムメモリ１４０が接続される。
【００２９】
プロセッサコア１１０は、命令フェッチ機能を除くプロセッサとしての主機構を備えるものであり、プログラムカウンタ１１１と、命令レジスタ１１２と、命令デコーダ１１３と、実行部１１４と、レジスタファイル１１５とを備えている。プログラムカウンタ１１１は、命令実行対象となる命令のアドレスを逐次計数するカウンタである。命令レジスタ１１２は、プログラムカウンタ１１１によって示される命令実行対象となる命令を保持するレジスタである。命令デコーダ１１３は、命令レジスタ１１２に保持された命令をデコードするデコーダである。実行部１１４は、命令デコーダ１１３によってデコードされた命令を実行するものである。レジスタファイル１１５は、実行部１１４における命令実行に必要なオペランド等を保持する記憶領域である。
【００３０】
命令キャッシュ１２０は、システムメモリ１４０に記憶されている命令のコピーを保持するキャッシュメモリである。プロセッサコア１１０から命令をアクセスする際、システムメモリ１４０よりも命令キャッシュ１２０の方が高速にアクセス可能であるため、可能な限り前もって命令キャッシュ１２０に命令を保持しておくことが望ましい。必要な命令が命令キャッシュ１２０に保持されている場合にはヒット、保持されていない場合にはミスヒットと呼ばれる。
【００３１】
データキャッシュ１３０は、システムメモリ１４０に記憶されているデータのコピーを保持するキャッシュメモリである。プロセッサコア１１０からデータをアクセスする際、システムメモリ１４０よりもデータキャッシュ１３０の方が高速にアクセス可能であるため、可能な限り前もってデータキャッシュ１３０に命令を保持しておくことが望ましい。命令キャッシュ１２０の場合と同様に、必要なデータがデータキャッシュ１３０に保持されている場合にはヒット、保持されていない場合にはミスヒットと呼ばれる。命令キャッシュ１２０の場合と異なり、ライトアクセスの際にもデータキャッシュ１３０は用いられる。
【００３２】
ネクストラインプリフェッチ部１５０は、予め必要となることが予想される命令として、次のキャッシュラインであるネクストラインをシステムメモリ１４０から命令キャッシュ１２０にプリフェッチするためのものである。このネクストラインプリフェッチ部１５０は、パイプライン構成におけるネクストラインプリフェッチ部１３に相当するものであり、命令フェッチステージ（ＩＦ）１１に属する。このネクストラインプリフェッチ部１５０は、プログラムカウンタ１１１の状態を監視して、適切なタイミングにより命令キャッシュ１２０のキャッシュラインのプリフェッチリクエストをシステムメモリ１４０に発行する。
【００３３】
パケットデマルチプレクサ１６０は、システムメモリ１４０から読み出された命令パケットを命令ヘッダと命令ペイロードとに分離するものである。この命令パケットの構造については後述するが、命令のキャッシュラインは命令ペイロードに含まれている。
【００３４】
プリフェッチキュー１７０は、命令ペイロードに含まれる命令のキャッシュラインを保持する待ち行列である。このプリフェッチキュー１７０に保持されたキャッシュラインは、先頭から順に命令キャッシュ１２０に保持される。
【００３５】
命令キュー１８０は、プログラムカウンタ１１１に従って命令キャッシュ１２０から読み出された命令のキャッシュラインを保持する待ち行列である。
【００３６】
命令辞書インデックス１９１および命令辞書テーブル１９２は、命令辞書テーブル参照型の圧縮命令を実装するためのものである。出現頻度の高い一連の命令マクロが最初に出現したときにその命令マクロを命令辞書登録命令によって登録しておいて、次回出現したときに命令辞書参照命令に対して一連の命令マクロを１命令で置き換えていく。命令辞書テーブル１９２は一連の命令マクロを保持するものであり、命令辞書インデックス１９１は、この命令辞書テーブル１９２をアクセスするためのインデックスとしての機能を有するものである。この命令辞書テーブル参照型の圧縮命令の利用法については後述する。
【００３７】
システムメモリ１４０は、命令実行対象となる命令およびその命令の実行に必要となるデータを記憶するメモリである。プロセッサコア１１０からシステムメモリ１４０に対してリードまたはライトのアクセスがリクエストされるが、命令キャッシュ１２０またはデータキャッシュ１３０にヒットしている限りは実際にはリクエストは発生しない。なお、このシステムメモリ１４０は、特許請求の範囲に記載の命令パケット保持部の一例である。
【００３８】
このブロック構成例において、プログラムカウンタ１１１、命令キャッシュ１２０、ネクストラインプリフェッチ部１５０、パケットデマルチプレクサ１６０、プリフェッチキュー１７０、命令キュー１８０は図１の命令フェッチステージ（ＩＦ）１１に属する。また、命令レジスタ１１２、命令辞書インデックス１９１および命令辞書テーブル１９２についても命令フェッチステージ（ＩＦ）１１の一部と考えることができる。同様に、命令デコーダは命令デコードステージ（ＩＤ）２１に属する。また、レジスタファイル１１５はレジスタフェッチステージ（ＲＦ）３１に属する。また、実行部１１４は実行ステージ（ＥＸ）４１に属する。データキャッシュ１３０およびシステムメモリ１４０はメモリアクセスステージ（ＭＥＭ）５１に属する。
【００３９】
［命令パケットの構造］
図３は、本発明の第１の実施の形態における命令パケット３００の構造例を示す図である。この命令パケット３００は、命令ヘッダ３１０と、命令ペイロード３２０とから構成される。命令ペイロード３２０は、１つ以上の命令キャッシュラインを格納する領域である。この例では、１２８バイトの命令キャッシュラインをｎ個（ｎは１以上の整数）ずつ格納するものとする。命令ヘッダ３１０は、命令ペイロード３２０に付与されるヘッダであり、その命令ペイロード３２０に関する情報を保持する。
【００４０】
図４は、本発明の第１の実施の形態における命令ヘッダ３１０のフィールド構成例を示す図である。この命令ヘッダ３１０の第１の構成例は、分岐予測フラグ３１１、命令プリフェッチタイミング３１２、命令ペイロード圧縮フラグ３１３、命令ペイロード長３１４、および、プリフェッチ設定３１５の各フィールドを備えている。この例では、命令ヘッダ３１０として３２ビットを想定し、ＬＳＢ側から第０ビットに分岐予測フラグ３１１、第１および２ビットに命令プリフェッチタイミング３１２、第３ビットに命令ペイロード圧縮フラグ３１３をそれぞれ割り当てている。また、第４乃至第７ビットに命令ペイロード長３１４、第８乃至１１ビットにプリフェッチ設定３１５をそれぞれ割り当てている。残りの第１２乃至３１ビットの２０ビットの未使用領域３１６は、後述のように他の用途に用いることができる。
【００４１】
分岐予測フラグ３１１は、命令ペイロード３２０内に分岐命令が存在し、かつ、その分岐先として命令ペイロード３２０内または次の命令ペイロード以外に分岐する可能性が高いことを示すフィールドである。すなわち、ネクストラインプリフェッチをそのまま実行してしまうと無駄になる可能性が高い場合に分岐予測フラグ３１１は例えば「１」を示し、それ以外の場合には例えば「０」を示す。なお、この分岐予測フラグ３１１は、特許請求の範囲に記載の分岐予測情報の一例である。
【００４２】
命令プリフェッチタイミング３１２は、命令プリフェッチを実行するタイミングを示すフィールドである。この命令プリフェッチタイミング３１２については第２の実施の形態において説明する。なお、命令プリフェッチタイミング３１２は、特許請求の範囲に記載のプリフェッチタイミング情報の一例である。
【００４３】
命令ペイロード圧縮フラグ３１３は、命令ペイロード３２０についてロスレス圧縮を施しているか否かを示すフィールドである。ロスレス圧縮とはデータの欠落が発生しない可逆圧縮であり、命令ペイロード３２０のビット列全体を圧縮するものである。このロスレス圧縮の方式としては、ハフマン符号、算術符号、ＬＺ符号などが広く知られている。命令ペイロード３２０についてロスレス圧縮を施している場合には、それを伸張しなければ命令デコードを実行することはできない。したがって、命令ペイロード圧縮フラグ３１３が「１」を示す場合には、いったん伸張処理を行った上で命令デコードが行われる。１つの命令キャッシュラインをロスレス圧縮してもフェッチされるデータ量は少なくならないため効果はなく、ある程度長いビット列でないと符号化効率は上がらない。また、分岐命令を含む場合には基本ブロック毎に命令パケットを区切って分ける必要がある。
【００４４】
命令ペイロード長３１４は、命令ペイロード３２０のサイズを示すフィールドである。例えば、命令キャッシュライン数を単位として、命令ペイロード３２０のサイズを示すことができる。上述の例では、命令ペイロード３２０に１２８バイトの命令キャッシュラインをｎ個ずつ格納することを想定しており、この場合には値ｎが命令ペイロード長３１４に設定される。
【００４５】
プリフェッチ設定３１５は、プリフェッチ対象となるアドレスを予め設定するためのフィールドである。このプリフェッチ設定３１５については第４の実施の形態において説明する。
【００４６】
［分岐予測フラグ］
図５は、本発明の第１の実施の形態で用いられる分岐予測フラグ３１１の設定例を示す図である。この例では、命令パケット＃１の命令ペイロード内に分岐命令＄１が含まれ、命令パケット＃２および＃３には分岐命令が含まれないことを想定している。そして、分岐命令＄１の分岐先は命令パケット＃３の命令ペイロード内の命令アドレスとなっており、その分岐確率は高いものと予測されている。したがって、この場合には、命令パケット＃１の命令ヘッダの分岐予測フラグ３１１は「１」に設定される。一方、命令パケット＃２および＃３には分岐命令が含まれないため、命令パケット＃２および＃３の命令ヘッダの分岐予測フラグ３１１は「０」に設定される。この分岐予測フラグ３１１は、後述するように、プロファイル等に基づいてコンパイル時に静的に設定されることを想定している。ここでは、命令パケット＃１から見ると、命令パケット＃２に含まれるのがネクストラインであり、命令パケット＃３に含まれるのが分岐先ラインである。
【００４７】
このようにして設定された分岐予測フラグ３１１は、命令プリフェッチの際に参照され、「１」に設定されている場合にはネクストキャッシュラインのプリフェッチを中止する。これにより、無駄になることが予想される命令プリフェッチを回避することができる。
【００４８】
一方、分岐予測フラグ３１１が「１」に設定されるケースが連続すると、命令プリフェッチが行われず、命令プリフェッチ機構を有効利用できなくなるおそれが生じ得る。そこで、分岐予測フラグ３１１が「１」に設定されるケースが連続しないように、分岐命令の間の命令を命令辞書テーブル参照型圧縮処理により圧縮することを考える。なお、この命令辞書テーブル参照型圧縮処理は、命令ペイロード圧縮フラグ３１３に関するロスレス圧縮とは別個のものである。
【００４９】
［命令辞書テーブル参照型圧縮］
図６は、本発明の第１の実施の形態で用いられる命令辞書テーブル参照型圧縮の適用例を示す図である。同図左側の非圧縮コードでは、圧縮されていない命令列３３１乃至３３５が配置されている。ここで、命令列３３１、３３２および３３５は同一のコードであることを想定する。同様に、命令列３３３および３３４は同一のコードであることを想定する。
【００５０】
同図中央の圧縮コードでは、命令列３３１の直後に命令辞書登録命令％１が配置される。これにより、命令辞書テーブル１９２の領域％１（３５１）には命令列３３１の内容が登録される。その後、命令辞書参照命令％１（３４２）が実行されると、命令辞書テーブル１９２の領域％１（３５１）が参照され、命令列３３２に相当する内容が伸張されて命令キュー１８０に供給される。
【００５１】
また、圧縮コードでは、命令列３３３の直後に命令辞書登録命令％２が配置される。これにより、命令辞書テーブル１９２の領域％２（３５２）には命令列３３３の内容が登録される。その後、命令辞書参照命令％２（３４４）が実行されると、命令辞書テーブル１９２の領域％２（３５２）が参照され、命令列３３４に相当する内容が伸張されて命令キュー１８０に供給される。
【００５２】
また、さらに命令辞書参照命令％１（３４５）が実行されると、命令辞書テーブル１９２の領域％１（３５１）が参照され、命令列３３５に相当する内容が伸張されて命令キュー１８０に供給される。
【００５３】
このように、命令辞書テーブル１９２を使用することにより、命令列の圧縮処理が実現される。そこで、これを利用して、以下のように分岐予測フラグ３１１の設定を変更することができる。
【００５４】
図７は、本発明の第１の実施の形態における命令辞書テーブル参照型圧縮による分岐予測フラグ３１１の変更例を示す図である。同図左側のように命令パケット＃１および＃２において分岐予測フラグ３１１が「１」に設定されている場合、連続して命令プリフェッチが行われなくなってしまう。そこで、上述の命令辞書テーブル１９２を用いた命令圧縮を行うことにより、分岐予測フラグ３１１が連続して「１」に設定されることを解消することを試みる。
【００５５】
すなわち、同図右側のように、命令辞書テーブル１９２を用いて分岐命令＄１と＄２との間の命令を圧縮することにより、命令パケット＃２に含まれていた分岐命令＄２を命令パケット＃１'に移動させる。これにより、命令パケット＃２に分岐命令＄２が存在しなくなることによって、命令パケット＃２'の分岐予測フラグ３１１を「０」に設定することができるようになる。
【００５６】
なお、一般に、命令辞書テーブル参照型の圧縮命令は、通常の命令よりデコードに多くのサイクル数を必要とすることがあるため、全ての命令に適用してしまうと却って処理性能を劣化させるおそれがある。しかし、出現頻度の高い命令マクロが存在するケースにおいては、高い圧縮効率が得られ、効果を発揮する。
【００５７】
［命令パケット生成処理］
図８は、本発明の第１の実施の形態における命令パケット生成のための機能構成例を示す図である。この例は、プログラム保持部４１１と、分岐プロファイル保持部４１２と、命令パケット生成部４２０と、分岐予測フラグ設定部４３０と、命令圧縮部４４０と、命令パケット保持部４１３とを備えている。この命令パケットの生成は、コンパイル時またはリンク時に行うことが適している。リロケータブルなＯＳにおいてダイナミックリンクが行われる場合には実行時でも可能である。
【００５８】
プログラム保持部４１１は、命令パケットを生成する対象となるプログラムを保持するものである。分岐プロファイル保持部４１２は、プログラム保持部４１１に保持されたプログラムに含まれる分岐命令の分岐プロファイルを保持するものである。この分岐プロファイルは、予めプログラムを解析し、または、実行することにより得られるものである。無条件分岐命令であれば分岐するか否かはプログラムを解析することにより判断できることが多い。また、条件分岐命令であっても、プログラムを実行させることにより統計的に分岐する確率を判断することができる。
【００５９】
命令パケット生成部４２０は、プログラム保持部４１１に保持されたプログラムを固定サイズにより区切って命令ペイロード３２０を生成し、それぞれに命令ヘッダ３１０を付することにより命令パケット３００を生成する。命令ペイロード３２０のサイズとしては、上述のように１２８バイトの命令キャッシュラインをｎ個ずつ格納することを想定することができる。
【００６０】
分岐予測フラグ設定部４３０は、命令パケット生成部４２０によって生成された命令ヘッダ３１０における分岐予測フラグ３１１を設定するものである。この分岐予測フラグ設定部４３０は、分岐プロファイル保持部４１２に保持された分岐プロファイルを参照することにより、命令ペイロード３２０に含まれる分岐命令の分岐先およびその分岐確率を予測して、分岐予測フラグ３１１を設定する。命令ペイロード３２０内に分岐命令が存在し、かつ、その分岐先として命令ペイロード３２０内または次の命令ペイロード以外に分岐する可能性が高い場合には分岐予測フラグ３１１に「１」が設定され、それ以外の場合には「０」が設定される。なお、この分岐予測フラグ設定部４３０は、特許請求の範囲に記載の分岐予測情報設定部の一例である。
【００６１】
命令圧縮部４４０は、命令ペイロード３２０に含まれる命令を圧縮するものである。命令辞書テーブル１９２を用いた命令圧縮を行う場合には、出現頻度の高い命令マクロを検出して、最初に出現した際にその命令マクロを命令辞書登録命令によって登録する。そして、次回出現したときに命令辞書参照命令に対して一連の命令マクロを１命令で置き換えていく。その結果、分岐命令の配置が変更された場合には、あらためて分岐予測フラグ３１１を設定し直す。また、命令ペイロード３２０全体に対してロスレス圧縮を行った場合には、命令ヘッダ３１０における命令ペイロード圧縮フラグ３１３を「１」に設定する。
【００６２】
命令パケット保持部４１３は、命令圧縮部４４０から出力された命令パケット３００を保持するものである。
【００６３】
図９は、本発明の第１の実施の形態における命令パケット生成のための処理手順例を示す図である。
【００６４】
まず、命令パケット生成部４２０によって、プログラム保持部４１１に保持されたプログラムが固定サイズに区切られて命令ペイロード３２０を生成され、それぞれに命令ヘッダ３１０が付されることにより命令パケット３００が生成される（ステップＳ９１１）。そして、分岐予測フラグ設定部４３０によって、命令ペイロード３２０内に分岐命令が存在し、かつ、その分岐先として命令ペイロード３２０内または次の命令ペイロード以外に分岐する可能性が高いか否かが判断される（ステップＳ９１２）。その結果、そのような分岐が発生する可能性が高いと判断された場合には分岐予測フラグ３１１に「１」が設定され（ステップＳ９１３）、それ以外の場合には「０」が設定される。
【００６５】
また、連続する命令パケット３００において分岐予測フラグ３１１に「１」が設定されている場合には（ステップＳ９１４）、命令圧縮部４４０によって命令ペイロード３２０内の命令が命令辞書テーブル１９２を用いて圧縮される（ステップＳ９１５）。なお、命令ペイロード３２０全体に対してロスレス圧縮を行うことも可能であり、その場合には命令ヘッダ３１０における命令ペイロード圧縮フラグ３１３が「１」に設定される。
【００６６】
［命令実行処理］
図１０は、本発明の第１の実施の形態における命令実行のための機能構成例を示す図である。この例は、命令パケット保持部４１３と、命令パケット分離部４５０と、分岐予測フラグ判定部４６０と、命令プリフェッチ部４７０と、命令伸張部４８０と、命令実行部４９０とを備えている。
【００６７】
命令パケット分離部４５０は、命令パケット保持部４１３に保持されていた命令パケット３００を命令ヘッダ３１０と命令ペイロード３２０とに分離するものである。
【００６８】
分岐予測フラグ判定部４６０は、命令ヘッダ３１０の分岐予測フラグ３１１を参照して、命令キャッシュ１２０に対して次のキャッシュラインのプリフェッチを行うべきか否かを判定するものである。プリフェッチを行うべきと判定した場合には、分岐予測フラグ判定部４６０は命令プリフェッチ部４７０に対して命令プリフェッチを要求する。なお、この分岐予測フラグ判定部４６０は、特許請求の範囲に記載の分岐予測情報判定部の一例である。
【００６９】
命令プリフェッチ部４７０は、分岐予測フラグ判定部４６０から命令プリフェッチが要求されると、システムメモリ１４０に対して次のキャッシュラインのリクエストを発行するものである。プリフェッチされた命令は、命令キャッシュ１２０に保持され、そのまま命令の流れに変化が生じなければ命令実行部４９０に供給される。
【００７０】
命令伸張部４８０は、命令ヘッダ３１０の命令ペイロード圧縮フラグ３１３が「１」に設定されている場合には、ロスレス圧縮されている命令ペイロード３２０を伸張して、デコード可能な命令列を得るものである。命令ペイロード圧縮フラグ３１３が「１」に設定されていない場合には、命令伸張部４８０は命令ペイロード３２０内の命令をそのまま出力する。
【００７１】
命令実行部４９０は、命令伸張部４８０から出力された命令列を実行するものである。命令辞書テーブル参照型の圧縮を施された命令列については、命令辞書登録命令および命令辞書参照命令を実行することにより各命令を伸張する。これに対し、ロスレス圧縮については、そのままではデコードすることができないため、命令伸張部４８０において命令伸張が行われる。
【００７２】
図１１は、本発明の第１の実施の形態における命令実行のための処理手順例を示す図である。
【００７３】
まず、命令パケット保持部４１３に保持されていた命令パケット３００が命令パケット分離部４５０によって命令ヘッダ３１０と命令ペイロード３２０とに分離される（ステップＳ９２１）。そして、命令ヘッダ３１０の分岐予測フラグ３１１が分岐予測フラグ判定部４６０によって判定される（ステップＳ９２２）。分岐予測フラグ３１１に「１」が設定されていれば命令プリフェッチは抑止され（ステップＳ９２３）、「０」が設定されていれば命令プリフェッチ部４７０によって命令プリフェッチが実行される（ステップＳ９２４）。
【００７４】
また、命令ヘッダ３１０の命令ペイロード圧縮フラグ３１３が「１」に設定されている場合には（ステップＳ９２５）、命令伸張部４８０がロスレス圧縮されている命令ペイロード３２０を伸張する（ステップＳ９２６）。
【００７５】
そして、得られた命令が命令実行部４９０によって実行される（ステップＳ９２７）。このとき、命令辞書テーブル参照型の圧縮を施された命令列については、命令実行部４９０によって命令辞書登録命令および命令辞書参照命令が実行されることにより、各命令が伸張されていく。
【００７６】
なお、ステップＳ９２１は、特許請求の範囲に記載の命令パケット分離手順の一例である。また、ステップＳ９２２は、特許請求の範囲に記載の分岐予測情報判定手順の一例である。また、ステップＳ９２３およびＳ９２４は、特許請求の範囲に記載の命令プリフェッチ手順の一例である。
【００７７】
このように、本発明の第１の実施の形態によれば、予め分岐予測フラグ３１１を設定しておくことにより、無駄な命令プリフェッチを抑止することができる。
【００７８】
［変形例］
図１２は、本発明の第１の実施の形態における命令ヘッダ３１０のフィールド構成の変形例を示す図である。図４のフィールド構成例では第１２乃至３１ビットの２０ビットを未使用領域３１６としたが、この変形例では、この２０ビットの領域３１７に命令ペイロードの先頭命令を保持することとしている。この第１の実施の形態では、３２ビット長命令の命令セットを想定しているが、命令フィールドの未使用部分やオペランドを減らす等の工夫を施すことにより２０ビットの短縮命令とし、領域３１７に埋め込んでいる。この場合、先頭命令が領域３１７に埋め込まれるため、命令ペイロード３２０のサイズは１命令分、すなわち３２ビットを削減することができる。
【００７９】
なお、ここでは先頭命令を２０ビットに短縮することとしたが、この短縮命令のビット幅はこれに限定されるものではなく、他のフィールドとの関係から適宜定めることができる。
【００８０】
＜２．第２の実施の形態＞
上述の第１の実施の形態ではプログラムを命令パケットにより管理することを前提としていたが、この第２の実施の形態では必ずしもそのような管理は必要ではない。そこで、最初に命令パケットによらない命令プリフェッチ制御について説明し、その後で命令パケットを利用した命令プリフェッチ制御について説明する。なお、この第２の実施の形態では、パイプライン構成およびブロック構成については上述の第１の実施の形態と同様であるため、説明を省略する。
【００８１】
［分岐命令の配置と命令プリフェッチ開始位置］
図１３は、本発明の第２の実施の形態における分岐命令の配置と命令プリフェッチ開始位置との関係例を示す図である。キャッシュライン＃１に存在する分岐命令＄１の分岐先は、キャッシュライン＃３に含まれる。したがって、この分岐命令＄１を実行した結果、分岐することとなった場合、キャッシュライン＃１に続くネクストラインとしてキャッシュライン＃２をプリフェッチしたとしても無駄になってしまう。
【００８２】
このとき、プリフェッチ開始位置Ａからキャッシュライン＃２のプリフェッチを開始したとすると、その時点では分岐命令＄１の実行結果は不明であり、キャッシュライン＃２のプリフェッチが無駄になる可能性がある。一方、プリフェッチ開始位置Ｂからキャッシュライン＃２のプリフェッチを開始することとすると、その時点で分岐命令＄１の実行結果は判明しており、キャッシュライン＃２の無駄なプリフェッチを抑止することが可能である。
【００８３】
このように、プリフェッチ開始位置は、ネクストラインプリフェッチの抑止の可否に影響を与える。上述の例からすると、プリフェッチ開始位置が遅いほど分岐命令の実行結果を知ることができて、プリフェッチ抑止には有利である。一方、プリフェッチ開始位置が遅過ぎるとプリフェッチが間に合わなくなり、命令パイプラインにおいて命令待ちが生じてしまうおそれがある。そこで、本発明の第２の実施の形態では、予め設定された任意のタイミングにより命令プリフェッチを行う機構を設ける。
【００８４】
［プリフェッチ開始アドレス設定レジスタにタイミングを設定する場合］
図１４は、本発明の第２の実施の形態におけるプリフェッチ開始アドレス設定レジスタを用いた構成例を示す図である。図１４（ａ）に示すように、この構成例は、ネクストラインプリフェッチ部１５０における構成として、プリフェッチ開始アドレス設定レジスタ１５３と、アドレス比較部１５４とを備える。
【００８５】
プリフェッチ開始アドレス設定レジスタ１５３は、各キャッシュラインにおいてネクストラインプリフェッチを開始するアドレスを設定するレジスタである。このプリフェッチ開始アドレス設定レジスタ１５３に設定されるアドレスは、キャッシュライン内における相対アドレスで足りる。このアドレスの設定は、プログラムにおける分岐命令の頻度などに基づいてコンパイル時に定めることを想定する。なお、このプリフェッチ開始アドレス設定レジスタ１５３は、特許請求の範囲に記載のアドレス設定レジスタの一例である。
【００８６】
アドレス比較部１５４は、プリフェッチ開始アドレス設定レジスタ１５３に設定されたアドレスと、プログラムカウンタ１１１の内容とを比較するものである。キャッシュライン内における相対アドレスについて一致が検出されると、アドレス比較部１５４はネクストラインプリフェッチリクエストを発行する。
【００８７】
この構成例によれば、キャッシュライン内の任意の位置においてプリフェッチ開始アドレスをプリフェッチ開始アドレス設定レジスタ１５３に設定しておいて、アドレス比較部１５４により一致を検出することができる。
【００８８】
図１４（ｂ）は、具体的な設定アドレスの例を示すものである。キャッシュラインにおいてプリフェッチ開始位置を４個所程度設けることを想定する。キャッシュラインが１２８バイトとすると、３２バイトずつに区切って、先頭（０バイト）、３２バイト、６４バイト（中央）、９６バイトの各位置を設定することが考えられる。４バイト（３２ビット）長命令の命令セットを想定すると、命令アドレスを２進数表記した下位２ビットは無視することができる。したがって、この場合、下位３ビットから下位７ビットの５ビット分をアドレス比較部１５４によって比較対象とすればよいことがわかる。
【００８９】
［命令ヘッダの利用］
図１５は、本発明の第２の実施の形態における命令ヘッダ３１０の命令プリフェッチタイミングフィールド３１２を用いた構成例を示す図である。この構成例では、第１の実施の形態において説明した命令パケットを前提として、命令ヘッダ３１０の命令プリフェッチタイミング３１２のフィールドを利用する。そして、ネクストラインプリフェッチ部１５０における構成として、図１４（ａ）のプリフェッチ開始アドレス設定レジスタ１５３およびアドレス比較部１５４に加えて、設定ステップアドレスレジスタ１５１と、乗算部１５２とを備える。
【００９０】
設定ステップアドレスレジスタ１５１は、プリフェッチ開始アドレスを設定する際の粒度をステップ値として保持するレジスタである。例えば、上述の例のように３２バイトをステップ値として、キャッシュラインの先頭（０バイト）、３２バイト、６４バイト、または、９６バイトの各位置をプリフェッチ開始として設定する場合には、「３２」が設定ステップアドレスレジスタ１５１に保持される。
【００９１】
乗算部１５２は、命令プリフェッチタイミング３１２のフィールドの値と、設定ステップアドレスレジスタ１５１に保持されたステップ値との乗算を行うものである。上述のように命令プリフェッチタイミング３１２のフィールドは２ビット幅であるため、これを補うために命令プリフェッチタイミング３１２にはステップ数を保持し、設定ステップアドレスレジスタ１５１に示されるステップ値を乗じるように構成している。したがって、命令ヘッダ３１０の命令プリフェッチタイミング３１２には、キャッシュラインの先頭（０バイト）であれば「００」、３２バイトであれば「０１」、６４バイトであれば「１０」、９６バイトであれば「１１」を設定することになる。この乗算部１５２による乗算結果は、プリフェッチ開始アドレス設定レジスタ１５３に保持される。
【００９２】
これ以外の構成は図１４（ａ）と同様であり、プリフェッチ開始アドレス設定レジスタ１５３に保持されたアドレスと、プログラムカウンタ１１１の内容とがアドレス比較部１５４によって比較される。キャッシュライン内における相対アドレスについて一致が検出されると、アドレス比較部１５４はネクストラインプリフェッチリクエストを発行する。
【００９３】
なお、乗算部１５２における乗算、または、アドレス比較部１５４におけるアドレス比較を容易にするためには、ステップ値は２のべき乗であることが望ましい。
【００９４】
この構成例によれば、命令ヘッダ３１０の命令プリフェッチタイミング３１２のフィールドを利用して、プリフェッチ開始アドレスをプリフェッチ開始アドレス設定レジスタ１５３に設定することができる。
【００９５】
［所定回数の命令実行をプリフェッチタイミングに利用する場合］
図１６は、本発明の第２の実施の形態において所定回数の命令実行をプリフェッチタイミングに利用する構成例を示す図である。図１４および図１５の構成例ではキャッシュライン内の固定位置をプリフェッチタイミングとして設定していたが、この構成例では特定の命令タイプの命令が所定回数実行されたときをプリフェッチタイミングとする。この構成例は、ネクストラインプリフェッチ部１５０における構成として、命令タイプ設定レジスタ１５５と、実行回数設定レジスタ１５６と、命令タイプ比較部１５７と、実行回数カウンタ１５８と、実行回数比較部１５９とを備える。
【００９６】
命令タイプ設定レジスタ１５５は、実行回数を計数する対象となる命令の命令タイプを設定するレジスタである。この場合の命令タイプとしては、例えば、除算命令やロード命令などの比較的レイテンシの長い命令、または、分岐命令などを想定することができる。レイテンシの長い命令については、後続の命令を多少遅らせたとしても全体の実行に影響はないからである。また、分岐命令については、図１３により説明したように、後続の命令を決定するために分岐命令の実行を待った方がよい場合があるからである。
【００９７】
実行回数設定レジスタ１５６は、命令タイプ設定レジスタ１５５に設定された命令タイプに該当する命令について、その命令が実行される回数を設定するレジスタである。この実行回数設定レジスタ１５６に設定された回数の命令実行が行われると、ネクストラインプリフェッチリクエストが発行される。
【００９８】
なお、これら命令タイプおよび実行回数の設定は、プロファイルデータに含まれる出現頻度に基づいてコンパイル時に静的に、または、実行時に動的に決定することができる。
【００９９】
命令タイプ比較部１５７は、命令レジスタ１１２に保持される命令の命令タイプと、命令タイプ設定レジスタ１５５に設定された命令タイプとを比較して、一致を検出するものである。この命令タイプ比較部１５７において一致が検出されるたびに、実行回数カウンタ１５８に対して計数のトリガが出力される。
【０１００】
実行回数カウンタ１５８は、命令タイプ設定レジスタ１５５に設定された命令タイプに該当する命令の実行回数を計数するカウンタである。この実行回数カウンタ１５８は、加算部１５８１と、カウント値レジスタ１５８２とを備える。加算部１５８１は、カウント値レジスタ１５８２の値に「１」を加算するものである。カウント値レジスタ１５８２は、実行回数カウンタ１５８としてのカウント値を保持するレジスタである。このカウント値レジスタ１５８２は、命令タイプ比較部１５７から計数のトリガが出力されるたびに、加算部１５８１の出力を保持する。これにより、実行回数の計数が行われる。
【０１０１】
実行回数比較部１５９は、カウント値レジスタ１５８２の値と実行回数設定レジスタ１５６の値とを比較して、一致を検出するものである。この実行回数比較部１５９において一致が検出されると、ネクストラインプリフェッチリクエストが発行される。
【０１０２】
なお、命令タイプ設定レジスタ１５５と実行回数設定レジスタ１５６の組は、複数設けることができる。この場合、実行回数カウンタ１５８も別個に設ける必要がある。これにより、何れかの組について一致が検出されると、ネクストラインプリフェッチリクエストが発行される。
【０１０３】
［命令ヘッダの利用］
図１７は、本発明の第２の実施の形態において命令ヘッダ３１０に命令タイプおよび実行回数を設定した例を示す図である。図１６の構成例では命令タイプ設定レジスタ１５５および実行回数設定レジスタ１５６に命令タイプおよび実行回数をそれぞれ設定していたが、これらの値は命令ヘッダ３１０に設定することも可能である。
【０１０４】
この例では、命令ヘッダ３１０の第１２ビット目から第２５ビット目の１４ビットの領域３１８に命令タイプを設定し、第２６ビット目から第３１ビット目の６ビットの領域３１９に実行回数を設定している。したがって、領域３１８の値を命令タイプ比較部１５７の一方の入力とし、領域３１９の値を実行回数比較部１５９の一方の入力とすることにより、特別な設定レジスタを設けることなく、所定回数の命令実行をプリフェッチタイミングに利用することができる。
【０１０５】
［命令実行処理］
図１８は、本発明の第２の実施の形態における命令実行のための機能構成例を示す図である。この例は、プログラム実行状態生成部５１０と、検出状態設定部５２０と、命令プリフェッチタイミング検出部５３０と、命令プリフェッチ部５７０と、命令実行部５９０とを備えている。
【０１０６】
プログラム実行状態生成部５１０は、現在のプログラムの実行状態を生成するものである。このプログラム実行状態生成部５１０では、現在のプログラムの実行状態として、例えば、現在実行中の命令アドレスを保持するプログラムカウンタ１１１の値を生成することができる。また、例えば、実行回数カウンタ１５８に保持された所定の命令タイプの現在の実行回数を生成することができる。
【０１０７】
検出状態設定部５２０は、命令プリフェッチタイミングを検出すべきプログラムの実行状態を設定するものである。この検出状態設定部５２０では、プログラムの実行状態として、例えば、命令プリフェッチタイミングを検出すべき命令アドレスの少なくとも一部をプリフェッチ開始アドレス設定レジスタ１５３に設定することができる。また、例えば、所定の命令タイプの実行回数を実行回数設定レジスタ１５６に設定することができる。
【０１０８】
命令プリフェッチタイミング検出部５３０は、現在のプログラムの実行状態と検出状態設定部５２０に設定されたプログラムの実行状態とを比較して、両者が一致した場合に命令プリフェッチタイミングを検出するものである。この命令プリフェッチタイミング検出部５３０として、アドレス比較部１５４または実行回数比較部１５９を利用することができる。
【０１０９】
命令プリフェッチ部５７０は、命令プリフェッチタイミング検出部５３０によって命令プリフェッチタイミングが検出されると、ネクストラインの命令プリフェッチを実行するものである。
【０１１０】
命令実行部５９０は、命令プリフェッチ部５７０により取得された命令を実行するものである。この命令実行部５９０による実行の結果、プログラム実行状態生成部５１０によって生成される現在のプログラムの実行状態に影響を与える。すなわち、プログラムカウンタ１１１の値や実行回数カウンタ１５８の値が更新され得る。
【０１１１】
図１９は、本発明の第２の実施の形態における命令実行のための処理手順例を示す図である。
【０１１２】
まず、検出状態設定部５２０に、命令プリフェッチタイミングを検出すべきプログラムの実行状態が設定される（ステップＳ９３１）。例えば、命令プリフェッチタイミングを検出すべき命令アドレスや、所定の命令タイプの実行回数が設定される。
【０１１３】
そして、命令実行部５９０により命令実行が行われ（ステップＳ９３２）、命令プリフェッチタイミング検出部５３０によって命令プリフェッチタイミングが検出される（ステップＳ９３３）。例えば、設定された命令アドレスがプログラムカウンタ１１１と一致した場合や、設定された所定の命令タイプの実行回数が実行回数カウンタ１５８の値と一致した場合に、命令プリフェッチタイミングが検出される。命令プリフェッチタイミング検出部５３０によって命令プリフェッチタイミングが検出されると、命令プリフェッチ部５７０によって命令プリフェッチが行われる（ステップＳ９３４）。
【０１１４】
このように、本発明の第２の実施の形態によれば、命令プリフェッチを行うタイミングを予め設定しておくことにより、命令プリフェッチのタイミングを制御することができる。
【０１１５】
＜３．第３の実施の形態＞
上述の第１および第２の実施の形態ではネクストラインプリフェッチの抑止制御に関するものであったが、以下の第３および第４の実施の形態ではネクストラインおよび分岐先ラインの両者をプリフェッチすることを想定する。なお、本発明の第３の実施の形態では、パイプライン構成およびブロック構成については上述の第１の実施の形態と同様であるため、説明を省略する。
【０１１６】
［プログラムカウンタの加算制御処理］
図２０は、本発明の第３の実施の形態におけるプログラムカウンタの加算制御処理の機能構成例を示す図である。この構成例は、命令フェッチ部６１０と、命令デコード部６２０と、命令実行部６３０と、加算制御レジスタ６４０と、加算制御部６５０と、プログラムカウンタ６６０とを備えている。
【０１１７】
命令フェッチ部６１０は、プログラムカウンタ６６０の値に従って、実行対象となる命令をフェッチするものであり、命令フェッチステージ１１に相当する。この命令フェッチ部６１０によってフェッチされた命令は命令デコード部６２０に供給される。
【０１１８】
命令デコード部６２０は、命令フェッチ部６１０によってフェッチされた命令をデコードするものであり、命令デコードステージ２１に相当する。
【０１１９】
命令実行部６３０は、命令デコード部６２０によってデコードされた命令を実行するものであり、命令実行ステージ４１に相当する。なお、ここではオペランドアクセスについては省略している。
【０１２０】
加算制御レジスタ６４０は、プログラムカウンタ６６０の加算制御を行うためのデータを保持するものである。この加算制御レジスタ６４０の構成例については後述する。
【０１２１】
加算制御部６５０は、加算制御レジスタ６４０に保持されたデータに基づいてプログラムカウンタ６６０の加算制御を行うものである。
【０１２２】
プログラムカウンタ６６０は、実行対象となる命令のアドレスを計数するものであり、プログラムカウンタ（ＰＣ）１８に相当する。このプログラムカウンタ６６０は、プログラムカウンタ値保持部６６１と、加算部６６２とを備えている。プログラムカウンタ値保持部６６１は、プログラムカウンタの値を保持するレジスタである。加算部６６２は、プログラムカウンタ値保持部６６１の値を加算する処理を行うものである。
【０１２３】
図２１は、本発明の第３の実施の形態における加算制御レジスタ６４０の構成例を示す図である。この加算制御レジスタ６４０は、増分語数（ｉｎｃｒ）６４１と、増分回数（ｃｏｎｔｉ）６４２とを保持している。
【０１２４】
増分語数６４１は、加算部６６２においてプログラムカウンタ値保持部６６１の値を加算する際の増分語数を保持するものである。この第４の実施の形態では３２ビット（４バイト）長命令の命令セットを想定しているため、１語は４バイトになる。プログラムカウンタ６６０においてアドレスの下位２ビットを省略して語単位のアドレスを保持しているものとすると、従来の方式では増分値「１」が毎回加算されることになる。これに対し、この第４の実施の形態では、増分値として増分語数６４１の値が加算されていく。増分語数６４１に「１」を設定すると従来通りの動作となるが、「２」以上の整数値を設定した場合には命令を間引きながら実行できるようになる。具体例については後述する。なお、増分語数６４１は、特許請求の範囲に記載の増分値レジスタの一例である。
【０１２５】
増分回数６４２は、加算部６６２において増分語数６４１に従った加算を行う回数を保持するものである。通常は従来の方式と同様に増分値「１」を加算するが、増分回数６４２において「１」以上の整数値が設定されている場合には増分語数６４１に従った加算を行う。この増分回数６４２は、図示しない減算部によって、命令が実行されるたびに「０」になるまで「１」を減算するように構成してもよく、また、別途カウンタを設けてそのカウンタの値が「０」になるまで「１」を減算するように構成してもよい。何れの場合であっても、増分回数６４２に指定された回数の加算が増分語数６４１に従って行われた後には、通常通り増分値「１」の加算に戻る。なお、この増分回数６４２は、特許請求の範囲に記載の変更指示レジスタの一例である。
【０１２６】
［命令の実行態様］
図２２は、本発明の第３の実施の形態における２方向分岐による命令の処理態様例を示す図である。２方向分岐を行う分岐命令のアドレスを「Ａ」とすると、分岐が生じなかった場合の命令列は、「Ａ＋４」、「Ａ＋１２」、「Ａ＋２０」、「Ａ＋２８」、「Ａ＋３６」、「Ａ＋４４」、「Ａ＋５２」、「Ａ＋６０」...に配置される。一方、分岐が生じた場合の命令列は、「Ａ＋８」、「Ａ＋１６」、「Ａ＋２４」、「Ａ＋３２」、「Ａ＋４０」、「Ａ＋４８」、「Ａ＋５６」、「Ａ＋６４」...に配置される。すなわち、分岐が生じなかった場合の命令列と分岐が生じた場合の命令列とが交互に配置されることになる。
【０１２７】
この２方向分岐の場合、各命令列の先頭の命令が実行されると、増分語数６４１には「２」が、増分回数６４２には各命令列の命令数が、それぞれ設定される。これにより、交互に配置された各命令列の一方のみを実行していくことができる。
【０１２８】
図２３は、本発明の第３の実施の形態における多方向分岐による命令の処理態様例を示す図である。ここでは、３方向分岐の例について説明するが、４方向以上に分岐する場合も同様の手法により適用可能である。３方向分岐を行う分岐命令のアドレスを「Ａ」とすると、第１の命令列は、「Ａ＋４」、「Ａ＋１６」、「Ａ＋２８」、「Ａ＋４０」、「Ａ＋５２」、「Ａ＋６４」、「Ａ＋７６」...に配置される。また、第２の命令列は、「Ａ＋８」、「Ａ＋２０」、「Ａ＋３２」、「Ａ＋４４」、「Ａ＋５６」、「Ａ＋６８」、「Ａ＋８０」...に配置される。また、第３の命令列は、「Ａ＋１２」、「Ａ＋２４」、「Ａ＋３６」、「Ａ＋４８」、「Ａ＋６０」、「Ａ＋７２」、「Ａ＋８４」...に配置される。すなわち、第１乃至第３の命令列が１命令ずつ順番に配置されることになる。
【０１２９】
この３方向分岐の場合、各命令列の先頭の命令が実行されると、増分語数６４１には「３」が、増分回数６４２には各命令列の命令数が、それぞれ設定される。これにより、１命令ずつ順番に配置された各命令列の一つのみを実行していくことができる。
【０１３０】
［加算制御レジスタへの設定］
図２４は、本発明の第３の実施の形態における加算制御レジスタ６４０に値を設定するための命令セットの一例を示す図である。図２４（ａ）は、本発明の第３の実施の形態における命令フォーマットの例である。この命令フォーマットは、６ビットのオペコード（ＯＰＣＯＤＥ）、５ビットの第１ソースオペランド（ｒｓ）、５ビットの第２ソースオペランド（ｒｔ）、５ビットのデスティネーションオペランド（ｒｄ）、１１ビットの即値フィールド（ｉｍｍ）を備えている。
【０１３１】
図２４（ｂ）は、本発明の第３の実施の形態におけるオペコード一覧の例を示している。縦方向にオペコードの上位３ビット、横方向にオペコードの下位３ビットを配している。以下では、オペコード一覧の右下の条件分岐命令、および、オペコード「１００１１１」の制御レジスタ変更命令に着目して説明する。
【０１３２】
図２４（ｃ）は、条件分岐命令の命令フォーマットの例である。この条件分岐命令としては、ここでは、ＢＥＱｆｐ、ＢＮＥｆｐ、ＢＬＥｆｐ、ＢＧＴＺｆｐ、ＢＬＴＺｆｐ、ＢＧＥＺｆｐ、ＢＬＴＺＡＬｆｐ、ＢＧＥＺＡＬｆｐを挙げている。分岐（Branch）を表す「Ｂ」に続く「ＥＱ」は両ソースオペランドの値が等しい（EQual）こと（ｒｓ＝ｒｔ）を分岐条件とすることを表す。また、「ＮＥ」は両ソースオペランドの値が等しくない（Not Equal）こと（ｒｓ≠ｒｔ）を分岐条件とすることを表す。また、「ＬＥ」は第１ソースオペランドが第２ソースオペランド以下である（Less than or Equal）こと（ｒｓ≦ｒｔ）を分岐条件とすることを表す。また、「ＧＴＺ」は第１ソースオペランドがゼロより大きい（Greater Than Zero）こと（ｒｓ＞０）を分岐条件とすることを表す。また、「ＬＴＺ」は第１ソースオペランドがゼロより小さい（Less Than Zero）こと（ｒｓ＜０）を分岐条件とすることを表す。また、「ＧＥＺ」は第１ソースオペランドがゼロ以上である（Greater than or Equal Zero）こと（ｒｓ≧０）を分岐条件とすることを表す。また、それらに続く「ＡＬ」は、分岐の際に戻り番地を保存すること（branch And Link）を意味する。また、それらに続く「ｆｐ」は両ソースオペランドの値が浮動小数点数（floating point number）を表すことを意味する。デスティネーションオペランドとして示される増分語数ｉｎｃｒは、プログラムカウンタ６６０の値を加算する際の増分語数である。即値フィールドとして示される増分回数ｃｏｎｔｉは、プログラムカウンタ６６０において増分語数ｉｎｃｒに従った加算を行う回数である。これら条件分岐命令が実行されると、加算制御レジスタ６４０の増分語数６４１には増分語数ｉｎｃｒが設定され、増分回数６４２には増分回数ｃｏｎｔｉが設定される。
【０１３３】
図２４（ｄ）は、制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥの命令フォーマットの例である。この制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥは、プログラムカウンタ６６０の増分モードを加算制御レジスタ６４０に設定する命令である。この制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥが実行されると、加算制御レジスタ６４０の増分語数６４１には増分語数ｉｎｃｒが設定され、増分回数６４２には増分回数ｃｏｎｔｉが設定される。この制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥは、条件分岐命令とは別個の命令であり、実際には条件分岐命令とともに使用される。
【０１３４】
図２５は、本発明の第３の実施の形態において条件分岐命令により加算制御レジスタ６４０に値を設定した場合の例を示す図である。この例では、条件分岐命令ＢＥＱｆｐにおいて、分岐条件「ｒｓ＝ｒｔ」、増分語数「２」、増分回数「Ｌ／２」が指定されている。この条件分岐命令ＢＥＱｆｐの命令語アドレスをｍとする。このとき、分岐条件「ｒｓ＝ｒｔ」が成立した場合には、命令ｍ＋２、命令ｍ＋４、命令ｍ＋６の順に、命令ｍ＋Ｌまで、増分語数「２」により実行が行われる。一方、分岐条件「ｒｓ＝ｒｔ」が成立しなかった場合には、命令ｍ＋１、命令ｍ＋３、命令ｍ＋５の順に、命令ｍ＋（Ｌ−１）まで、増分語数「２」により実行が行われる。
【０１３５】
図２６は、本発明の第３の実施の形態において制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥにより加算制御レジスタ６４０に値を設定した場合の例を示す図である。この例では、加算制御レジスタ６４０への設定を行わない通常の条件分岐命令の次に、制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥが配置されている。そして、制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥにおいて、増分語数「２」、増分回数「Ｌ／２」が指定されている。制御レジスタ変更命令ＰＣＩＮＣＭＯＤＥの命令語アドレスをｍとする。このとき、条件分岐命令において分岐条件が成立した場合には、命令ｍ＋２、命令ｍ＋４、命令ｍ＋６の順に、命令ｍ＋Ｌまで、増分語数「２」により実行が行われる。一方、条件分岐命令において分岐条件が成立しなかった場合には、命令ｍ＋１、命令ｍ＋３、命令ｍ＋５の順に、命令ｍ＋（Ｌ−１）まで、増分語数「２」により実行が行われる。
【０１３６】
［命令実行処理］
図２７は、本発明の第３の実施の形態における命令実行のための処理手順例を示す図である。ここでは、上述の条件分岐命令や制御レジスタ変更命令などによって、加算制御レジスタ６４０への増分語数および増分回数の設定が予め完了していることを想定している。
【０１３７】
加算制御レジスタ６４０の増分回数６４２がゼロより大きい場合（ステップＳ９４１）、プログラムカウンタ６６０において増分語数６４１に「４」を乗じた値が加算部６６２によってプログラムカウンタ値保持部６６１に加算される（ステップＳ９４２）。また、この場合、加算制御レジスタ６４０の増分回数６４２が「１」減算される（ステップＳ９４３）。一方、加算制御レジスタ６４０の増分回数６４２がゼロより大きくない場合には（ステップＳ９４１）、通常通り、プログラムカウンタ６６０において値「４」が加算部６６２によってプログラムカウンタ値保持部６６１に加算される（ステップＳ９４４）。これらの処理は繰り返し行われる。なお、ステップＳ９４２は、特許請求の範囲に記載の変更増分加算手順の一例である。また、ステップＳ９４４は、特許請求の範囲に記載の通常増分加算手順の一例である。
【０１３８】
このように、本発明の第３の実施の形態によれば、分岐後の複数の命令列を命令単位で順番に混在して配置しておいて、分岐条件に合わせてプログラムカウンタの加算を制御することにより、適切な命令列の命令を実行することができる。これにより、ネクストラインおよび分岐先ラインを混在して配置することが可能となり、命令プリフェッチのペナルティを平均化することができる。
【０１３９】
＜４．第４の実施の形態＞
［プロセッサの構成］
図２８は、本発明の第４の実施の形態におけるプロセッサのパイプライン構成例を示す図である。基本的なパイプライン構成は、第１の実施の形態において説明したものと同様の５段階のパイプラインを想定している。
【０１４０】
上述の第１の実施の形態ではネクストラインプリフェッチ部１３においてネクストラインのプリフェッチを行っていたが、この第４の実施の形態ではネクストライン分岐先ラインプリフェッチ部１４がネクストラインおよび分岐先ラインのプリフェッチを行う。すなわち、現在実行対象となっている命令を含むキャッシュラインの次のキャッシュラインであるネクストラインのみならず、分岐先の命令を含むキャッシュラインである分岐先ラインのプリフェッチも行われる。ネクストライン分岐先ラインプリフェッチ部１４によってプリフェッチされた分岐先ラインは、プリフェッチキュー１７に保持される。このプリフェッチキュー１７に保持された分岐先ラインは、次の命令デコードステージ（ＩＤ）２１に供給される場合に用いられる。なお、ネクストラインについては命令キャッシュから直接供給されるため、プリフェッチキュー１７を介する必要はない。
【０１４１】
図２９は、本発明の第４の実施の形態におけるプロセッサのブロック構成例を示す図である。基本的なブロック構成は、第１の実施の形態において説明したものと同様である。
【０１４２】
上述の第１の実施の形態ではネクストラインプリフェッチ部１５０においてネクストラインのプリフェッチを行っていたが、この第４の実施の形態ではネクストライン分岐先ラインプリフェッチ部２５０がネクストラインおよび分岐先ラインのプリフェッチを行う。また、プリフェッチキュー１７１を命令キャッシュ１２０と並列に配置して、プリフェッチキュー１７１から命令レジスタ１１２へ直接、分岐先ラインを供給できるようにしている。すなわち、分岐が発生した場合には、命令キャッシュ１２０から供給しかけた命令に代えて、プリフェッチキュー１７１からの命令をバイパスして供給する。これにより、パイプラインをストールさせることなく、命令を発行し続けることができる。なお、ネクストライン分岐先ラインプリフェッチ部２５０は、特許請求の範囲に記載のプリフェッチ部の一例である。また、プリフェッチキュー１７１は、特許請求の範囲に記載のプリフェッチキューの一例である。
【０１４３】
なお、この第４の実施の形態では、命令パケットに分けることは必須ではないため、このブロック構成からは除外している。また、命令辞書テーブルによる圧縮についても、この第４の実施の形態では必須ではないため、ブロック構成から除外している。これらは適宜、組み合わせて実施することも可能である。
【０１４４】
［分岐命令とキャッシュラインの関係］
図３０は、本発明の第４の実施の形態における分岐命令とキャッシュラインの関係を示す図である。
【０１４５】
現在実行対象となっている命令を含むキャッシュラインを現ラインと呼称し、それに続くキャッシュラインをネクストラインと呼称する。また、現ラインに含まれる分岐命令の分岐先命令を含むキャッシュラインを分岐先ラインと呼称する。この例では、現ラインの最後に分岐命令が配置されている。これは、現ラインの先頭の命令が実行されるタイミングからネクストラインおよび分岐先ラインのプリフェッチを開始することによって、分岐命令の実行までに両ラインのプリフェッチを完了させるまでの余裕をもたせるためである。したがって、必ずしも現ラインの最後に分岐命令が配置されている必要はなく、現ラインの少なくとも後半部分に配置されていれば、場合によってはプリフェッチの完了に間に合わせることは可能であると考えられる。
【０１４６】
現ラインの最後に分岐命令を配置した場合、分岐命令における分岐条件が成立せずに分岐が発生しない場合にはネクストラインが必要となる、分岐条件が成立して分岐が発生する場合には分岐先ラインが必要となる。したがって、分岐条件の成否に関わらずプリフェッチを成功させるためには、ネクストラインおよび分岐先ラインの両ラインをプリフェッチすることが望ましい。本発明の第４の実施の形態では、ネクストライン分岐先ラインプリフェッチ部２５０によって両ラインをプリフェッチすることにより、分岐条件の成否に左右されずに命令実行を継続することを可能とする。この場合、両ラインをプリフェッチするためには、スループットは通常の２倍あることが望ましいが、必ずしも必須要件ではない。
【０１４７】
各キャッシュラインの命令キャッシュ１２０上での衝突を考慮すると、分岐先ラインの配置には制限を設けることが望ましい。例えば、命令キャッシュ１２０がダイレクトマッピング方式であった場合、ラインアドレスが同じキャッシュライン同士は同時には格納することができずに衝突を起こす。この場合、ネクストラインをプリフェッチした直後に同じラインアドレスを有する分岐先ラインをプリフェッチすると、ネクストラインは命令キャッシュ１２０から追い出されてしまう。２ｗａｙセットアソシアティブ方式であれば、衝突を起こす可能性は低くなるが、格納状態によっては他のキャッシュラインに影響を与える場合は生じ得る。したがって、この第４の実施の形態では、最も厳しい条件としてダイレクトマッピング方式の命令キャッシュを想定し、ネクストラインと分岐先ラインとが同じラインアドレスにならないように、コンパイラまたはリンカにおいて分岐先ラインの配置を調整する。
【０１４８】
コンパイラまたはリンカにおいて命令のアドレス配置を変更するためには、例えば次のような手法を用いることができる。まず、以下のような命令列を想定する。なお、「０ｘ」に続く数字は十六進数を表す。
０ｘ００００：命令Ａ
０ｘ０００４：命令Ｂ
０ｘ０００８：命令Ｃ
このとき、命令の配置を全体的に４バイト後方にずらしたい場合には、以下のようにＮＯＰ（No-OPeration）命令を挿入する手法が考えられる。
０ｘ００００：ＮＯＰ命令
０ｘ０００４：命令Ａ
０ｘ０００８：命令Ｂ
０ｘ０００Ｃ：命令Ｃ
【０１４９】
また、命令Ａが複数のオペレーションを行う命令である場合、以下のように命令Ａを命令ＡＡと命令ＡＢの２命令に分けることができれば、同様に命令の配置を全体的に４バイト後方にずらすことができる。
０ｘ００００：命令ＡＡ
０ｘ０００４：命令ＡＢ
０ｘ０００８：命令Ｂ
０ｘ０００Ｃ：命令Ｃ
【０１５０】
図３１は、本発明の第４の実施の形態における命令配置の変更の一態様を示す図である。ここでは、図３１（ａ）のように命令列Ａと命令列Ｂの後方に分岐命令Ｃがあり、命令列Ｄと命令列Ｅの何れかの処理を行い、その後、命令列Ｆを処理するというプログラムを想定する。このとき、命令列Ｂの結果が分岐命令Ｃの分岐条件に影響を与えない場合には、図３１（ｂ）のように分岐命令Ｃを命令列Ａの直後に移動させ、さらに命令列Ｂを分岐先にも配置することにより、実行結果に影響を与えることなく命令配置を変更することができる。
【０１５１】
［命令配置処理］
図３２は、本発明の第４の実施の形態における命令配置のための機能構成例を示す図である。この構成例では、プログラム保持部７０１に保持されたプログラムからオブジェクトコードを生成して、オブジェクトコード保持部７０２に保持させることを想定している。この構成例は、分岐命令抽出部７１０と、分岐命令配置部７２０と、分岐先命令配置部７３０と、オブジェクトコード生成部７４０とを備えている。
【０１５２】
分岐命令抽出部７１０は、プログラム保持部７０１に保持されたプログラムの中から分岐命令を抽出するものである。この分岐命令抽出部７１０は、抽出した分岐命令のプログラムにおけるアドレスを把握して分岐命令配置部７２０に供給する。また、この分岐命令抽出部７１０は、抽出した分岐命令の分岐先アドレスを把握して分岐先命令配置部７３０に供給する。
【０１５３】
分岐命令配置部７２０は、分岐命令抽出部７１０によって抽出された分岐命令をキャッシュライン（現ライン）の後半部分に配置するものである。キャッシュラインの後半部分に配置するのは、上述のように、プリフェッチを完了させるまでの余裕をもたせるためである。したがって、この観点からは、キャッシュラインの最後に分岐命令を配置することが最も望ましいことになる。
【０１５４】
分岐先命令配置部７３０は、分岐命令抽出部７１０によって抽出された分岐命令の分岐先命令を、次のキャッシュライン（ネクストライン）とは異なるラインアドレスを有する他のキャッシュライン（分岐先ライン）に配置するものである。ネクストラインと分岐先ラインとを異なるラインアドレスのキャッシュラインに配置するのは、上述のように、命令キャッシュ１２０における衝突を避けるためである。
【０１５５】
オブジェクトコード生成部７４０は、分岐命令配置部７２０および分岐先命令配置部７３０によって配置された分岐命令および分岐先命令を含む命令列についてオブジェクトコードを生成するものである。このオブジェクトコード生成部７４０によって生成されたオブジェクトコードは、オブジェクトコード保持部７０２に保持される。なお、このオブジェクトコード生成部７４０は、特許請求の範囲に記載の命令列出力部の一例である。
【０１５６】
図３３は、本発明の第４の実施の形態における命令配置のための処理手順例を示す図である。
【０１５７】
まず、分岐命令抽出部７１０によって、プログラム保持部７０１に保持されたプログラムの中から分岐命令が抽出される（ステップＳ９５１）。そして、分岐命令抽出部７１０によって抽出された分岐命令が、分岐命令配置部７２０によってキャッシュライン（現ライン）の後半部分に配置される（ステップＳ９５２）。また、分岐命令抽出部７１０によって抽出された分岐命令の分岐先命令が、分岐先命令配置部７３０によって次のキャッシュライン（ネクストライン）とは異なるラインアドレスを有する他のキャッシュライン（分岐先ライン）に配置される（ステップＳ９５３）。そして、分岐命令配置部７２０および分岐先命令配置部７３０によって配置された分岐命令および分岐先命令を含む命令列について、オブジェクトコード生成部７４０によってオブジェクトコードが生成される（ステップＳ９５４）。
【０１５８】
なお、ステップＳ９５１は、特許請求の範囲に記載の分岐命令抽出手順の一例である。また、ステップＳ９５２は、特許請求の範囲に記載の分岐命令配置手順の一例である。また、ステップＳ９５３は、特許請求の範囲に記載の分岐先命令配置手順の一例である。また、ステップＳ９５４は、特許請求の範囲に記載の命令列出力手順の一例である。
【０１５９】
［プリフェッチアドレスの設定］
図３４は、本発明の第４の実施の形態におけるプリフェッチアドレスレジスタの設定例を示す図である。上述のように、分岐先ラインはネクストラインとは異なるラインアドレスに配置される。分岐先ラインをプリフェッチする際には、現ラインからの相対位置により常に固定的にプリフェッチするようにしてもよいが、以下のように自動的にプリフェッチする分岐先アドレスをその都度、任意に設定するようにしてもよい。
【０１６０】
図３４（ａ）は、プリフェッチアドレスレジスタ（ＰＲＡＤＤＲ：PRefetch ADDress Register）７９０の構成例を示す図である。このプリフェッチアドレスレジスタ７９０は、分岐先ラインとして命令キャッシュ１２０へのプリフェッチ対象となるプリフェッチアドレスを設定するレジスタである。このプリフェッチアドレスは、プリフェッチアドレスレジスタ７９０の下位１２ビットに保持される。
【０１６１】
図３４（ｂ）は、プリフェッチアドレスレジスタ７９０に対する値の設定を行うＭＴＳＩ＿ＰＲＡＤＤＲ（Move To Special register Immediate - PRADDR）命令の命令フォーマットを示す図である。このＭＴＳＩ＿ＰＲＡＤＤＲ命令は、特殊（ＳＰＥＣＩＡＬ）命令の一つであり、特定のレジスタ（ここではプリフェッチアドレスレジスタ７９０）に即値を設定する命令である。この命令の第１７乃至第２１ビットがプリフェッチアドレスレジスタＰＲＡＤＤＲを表している。この命令の第１１乃至第８ビットがプリフェッチアドレスレジスタ７９０の第１１乃至第８ビットに設定される。これにより、プリフェッチ対象となる分岐先ラインのアドレスが設定される。なお、ここでは、命令キャッシュ１２０の仕様として、４Ｋバイトの２ｗａｙセットアソシアティブ方式、１ｗａｙ当り８ラインの計１６ライン、エントリサイズ２５６バイトを想定している。
【０１６２】
また、他の例として、第１の実施の形態において説明した命令パケット３００に区分けして、命令ヘッダ３１０のプリフェッチ設定フィールド３１５を利用することが考えられる。この場合、図４の命令ヘッダ３１０の第１１乃至第８ビットのプリフェッチ設定フィールド３１５が、プリフェッチアドレスレジスタの第１１乃至第８ビットに設定される。これにより、特殊命令を用いることなく、プリフェッチ対象となる分岐先ラインのアドレスを設定することができる。
【０１６３】
［命令実行処理］
図３５は、本発明の第４の実施の形態における命令実行のための機能構成例を示す図である。この構成例では、プログラムカウンタ１１１の状態を検知して、命令キャッシュ１２０およびプリフェッチキュー１７１へプリフェッチを行うことを想定している。この構成例は、プリフェッチタイミング検出部７５０と、ネクストラインプリフェッチ部７６０と、分岐先ラインプリフェッチ部７７０とを備えている。これらの構成は、ブロック構成のネクストライン分岐先ラインプリフェッチ部２５０に相当するものである。
【０１６４】
プリフェッチタイミング検出部７５０は、プログラムカウンタ１１１の状態を参照して、命令プリフェッチのタイミングを検出するものである。この第４の実施の形態では、ネクストラインおよび分岐先ラインの両方向をプリフェッチするため、早期にプリフェッチを開始することが望ましい。したがって、例えばキャッシュラインの先頭の命令が実行開始された時点で命令プリフェッチのタイミングを検出することが考えられる。
【０１６５】
ネクストラインプリフェッチ部７６０は、ネクストラインをプリフェッチするものである。システムメモリ１４０からプリフェッチされたネクストラインは、命令キャッシュ１２０に格納される。
【０１６６】
分岐先ラインプリフェッチ部７７０は、分岐先ラインをプリフェッチするものである。分岐先ラインは、現ラインからの相対位置のキャッシュラインを固定的に使用するようにしてもよく、また、上述のプリフェッチアドレスレジスタ７９０に設定されたアドレスを使用するようにしてもよい。システムメモリ１４０からプリフェッチされた分岐先ラインは、命令キャッシュ１２０およびプリフェッチキュー１７１に格納される。
【０１６７】
図３６は、本発明の第４の実施の形態における命令実行のための処理手順例を示す図である。
【０１６８】
まず、プリフェッチタイミング検出部７５０においてキャッシュラインの先頭の命令が実行開始されたことが検知されると（ステップＳ９６１）、ネクストラインプリフェッチ部７６０によってネクストラインがプリフェッチされる（ステップＳ９６２）。また、分岐先ラインプリフェッチ部７７０によって分岐先ラインがプリフェッチされる（ステップＳ９６３）。以下、これらの処理が繰り返される。これにより、ネクストラインおよび分岐先ラインの両方向の命令列がプリフェッチされる。
【０１６９】
このように、本発明の第４の実施の形態によれば、分岐先ラインをネクストラインとは異なるラインアドレスなるよう配置しておいて、ネクストラインおよび分岐先ラインの両方向の命令列をプリフェッチすることにより、スループットを改善することができる。
【０１７０】
＜５．各実施の形態の組合せ＞
ここまでは、本発明の第１乃至第４の実施の形態について別々に説明したが、これらの実施の形態は適宜組み合わせて実施することが可能である。
【０１７１】
［第１の実施の形態と第２の実施の形態の組合せ］
本発明の第１の実施の形態では、命令ヘッダ３１０の分岐予測フラグ３１１に従ってプリフェッチの有無を決定していたが、その予測が外れることを回避するために本発明の第２の実施の形態を組み合わせることが有効である。すなわち、第２の実施の形態によりプリフェッチの判断を遅らせることによって、分岐の有無を先に確定させることができ、正しいキャッシュラインをプリフェッチすることができる。
【０１７２】
［第１または第２の実施の形態と第３の実施の形態の組合せ］
本発明の第３の実施の形態では、両方向のプリフェッチを行うため、アドレスが離れた分岐先への分岐命令や、ｅｌｓｅ節のないｉｆ文の場合には適用が困難なことがある。例えば、多方向分岐の全てのケースが同じ命令数でない場合には命令数が同じ数になるまでＮＯＰ命令を挿入する必要がある。また、ある程度長い命令例になってしまうと命令実行のスループットとキャッシュの利用効率が低下してしまう。これに対して、第１の実施の形態の分岐予測フラグ３１１を利用して、離れたアドレスへ分岐する可能性が高い場合には両方向のプリフェッチを行わないようにすることにより、第３の実施の形態のデメリットを回避することができる。また、第２の実施の形態のように命令プリフェッチタイミングを遅らせることにより分岐の有無を先に確定させ、無駄なプリフェッチを行わないようにすることにより、第３の実施の形態のデメリットを回避することができる。
【０１７３】
［第１または第２の実施の形態と第４の実施の形態の組合せ］
本発明の第４の実施の形態では、ネクストラインおよび分岐先ラインを常にプリフェッチするようにしていたが、現ラインに分岐命令を含まない場合は分岐先ラインのプリフェッチが無駄になってしまうというデメリットがある。そこで、第１の実施の形態の分岐予測フラグ３１１を利用して、ネクストラインを実行する可能性が高いと判断した場合にはネクストラインのみをプリフェッチすることにより、第４の実施の形態のデメリットを回避することができる。また、第２の実施の形態のように命令プリフェッチタイミングを遅らせることにより分岐の有無を先に確定させ、無駄なプリフェッチを行わないようにすることにより、第４の実施の形態のデメリットを回避することができる。
【０１７４】
［第３の実施の形態と第４の実施の形態の組合せ］
本発明の第４の実施の形態では、ネクストラインおよび分岐先ラインの２方向のプリフェッチを対象としていたが、第３の実施の形態を適用することにより、３方向以上の多方向分岐にも適用が可能となる。すなわち、複数の命令列が混在したキャッシュラインを２方向プリフェッチすることにより、多方向分岐への適用が可能となる。
【０１７５】
このとき、ラインサイズ程度の範囲内の小さな分岐については第３の実施の形態を適用して、より広範囲への分岐については第４の実施の形態を適用するように使い分けることにより、両者のデメリットを回避することができる。すなわち、第４の実施の形態では、実行のスループットが低下しない一方で、命令キャッシュの利用効率は常に半分になるというデメリットがある。また、第３の実施の形態では、広範囲への分岐に適用してもあまり効果が得られないというデメリットがある。両者を組み合わせることにより、互いのデメリットを回避することができる。
【０１７６】
［その他の組合せ］
ここで挙げた以外の組合せについても可能であり、互いの効果をより向上させることができる。例えば、第１または第２の実施の形態と、第３の実施の形態と、第４の実施の形態とを組み合わせることにより、上述したそれぞれの効果を互いにより向上させることができる。
【０１７７】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０１７８】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０１７９】
１１  命令フェッチステージ
１２  加算部
１３  ネクストラインプリフェッチ部
１４  ネクストライン分岐先ラインプリフェッチ部
１７、１７０、１７１  プリフェッチキュー
１８、１１１  プログラムカウンタ
２１  命令デコードステージ
３１  レジスタフェッチステージ
４１  命令実行ステージ
１１０  プロセッサコア
１１２  命令レジスタ
１１３  命令デコーダ
１１４  実行部
１１５  レジスタファイル
１２０  命令キャッシュ
１３０  データキャッシュ
１４０  システムメモリ
１５０  ネクストラインプリフェッチ部
１５１  設定ステップアドレスレジスタ
１５２  乗算部
１５３  プリフェッチ開始アドレス設定レジスタ
１５４  アドレス比較部
１５５  命令タイプ設定レジスタ
１５６  実行回数設定レジスタ
１５７  命令タイプ比較部
１５８  実行回数カウンタ
１５９  実行回数比較部
１６０  パケットデマルチプレクサ
１８０  命令キュー
１９１  命令辞書インデックス
１９２  命令辞書テーブル
２５０  ネクストライン分岐先ラインプリフェッチ部
３２０  命令ペイロード
４１１  プログラム保持部
４１２  分岐プロファイル保持部
４１３  命令パケット保持部
４２０  命令パケット生成部
４３０  分岐予測フラグ設定部
４４０  命令圧縮部
４５０  命令パケット分離部
４６０  分岐予測フラグ判定部
４７０  命令プリフェッチ部
４８０  命令伸張部
４９０  命令実行部
５１０  プログラム実行状態生成部
５２０  検出状態設定部
５３０  命令プリフェッチタイミング検出部
５７０  命令プリフェッチ部
５９０  命令実行部
６１０  命令フェッチ部
６２０  命令デコード部
６３０  命令実行部
６４０  加算制御レジスタ
６５０  加算制御部
６６０  プログラムカウンタ
７０１  プログラム保持部
７０２  オブジェクトコード保持部
７１０  分岐命令抽出部
７２０  分岐命令配置部
７３０  分岐先命令配置部
７４０  オブジェクトコード生成部
７５０  プリフェッチタイミング検出部
７６０  ネクストラインプリフェッチ部
７７０  分岐先ラインプリフェッチ部
７９０  プリフェッチアドレスレジスタ
【図１】
2011209903.tif 000003
【図２】
2011209903.tif 000004
【図３】
2011209903.tif 000005
【図４】
2011209903.tif 000006
【図５】
2011209903.tif 000007
【図６】
2011209903.tif 000008
【図７】
2011209903.tif 000009
【図８】
2011209903.tif 000010
【図９】
2011209903.tif 000011
【図１０】
2011209903.tif 000012
【図１１】
2011209903.tif 000013
【図１２】
2011209903.tif 000014
【図１３】
2011209903.tif 000015
【図１４】
2011209903.tif 000016
【図１５】
2011209903.tif 000017
【図１６】
2011209903.tif 000018
【図１７】
2011209903.tif 000019
【図１８】
2011209903.tif 000020
【図１９】
2011209903.tif 000021
【図２０】
2011209903.tif 000022
【図２１】
2011209903.tif 000023
【図２２】
2011209903.tif 000024
【図２３】
2011209903.tif 000025
【図２４】
2011209903.tif 000026
【図２５】
2011209903.tif 000027
【図２６】
2011209903.tif 000028
【図２７】
2011209903.tif 000029
【図２８】
2011209903.tif 000030
【図２９】
2011209903.tif 000031
【図３０】
2011209903.tif 000032
【図３１】
2011209903.tif 000033
【図３２】
2011209903.tif 000034
【図３３】
2011209903.tif 000035
【図３４】
2011209903.tif 000036
【図３５】
2011209903.tif 000037
【図３６】
2011209903.tif 000038