(57)【要約】【課題】より簡易な構成でローカル・スラックの予測を行うことのできるローカル・スラックの予測方法、及びローカル・スラック予測機構を提供する。【解決手段】プロセッサで実行される命令ｉ０を、その命令ｉ０の予測スラックの値分だけその実行レイテンシを増加させて実行するとともに、予測スラックがターゲット・スラックに到達したと推定される命令実行時の振る舞いが観測されるまで命令ｉ０の実行毎に徐々に予測スラックを増加させていき、最終的に予測スラックをターゲット・スラックに一致させることで、ローカル・スラックを予測する。【選択図】図１
2007249710.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサで実行される命令を、その命令のローカル・スラックの予測値である予測スラックの値分だけその実行レイテンシを増加させて実行するとともに、
前記命令の実行時の振る舞いに基づいて、現状におけるローカル・スラックの適正値であるターゲット・スラックに前記予測スラックが到達したか否かを推定し、
到達したとの推定がなされるまで前記予測スラックを前記命令の実行毎に徐々に増加させていく
ことを特徴とするローカル・スラックの予測方法。
【請求項２】
前記予測スラックが前記ターゲット・スラックに到達したとの推定の成立条件として、
（Ａ）当該命令の実行時に分岐予測ミスが発生したこと、
（Ｂ）当該命令の実行時にキャッシュ・ミスが発生したこと、
（Ｃ）後続命令に対するオペランド・フォワーディングが発生したこと、
（Ｄ）後続命令に対するストア・データ・フォワーディングが発生したこと、
（Ｅ）当該命令が命令ウィンドウに存在する命令の中で最も古い命令となっていること、
（Ｆ）当該命令がリオーダ・バッファに存在する命令の中で最も古い命令となっていること、
（Ｇ）当該命令が、前記命令ウィンドウに存在する命令の中で最も古い命令に実行結果を渡す命令となっていること、
（Ｈ）当該命令が、同一のサイクルに実行される命令の中で最も多くの後続命令に実行結果を渡す命令となっていること、
（Ｉ）当該命令の実行結果を渡すことで、実行可能な状態となる後続命令の数が、予め定められた判定値以上となっていること、
のうちのいずれかを含む
ことを特徴とする請求項１に記載のローカル・スラックの予測方法。
【請求項３】
前記予測スラックが前記ターゲット・スラックに到達したとの推定がなされたときには同予測スラックを減少させる
ことを特徴とする請求項１又は２に記載のローカル・スラックの予測方法。
【請求項４】
前記予測スラックの増加は、前記予測スラックが前記ターゲット・スラックに到達したとの推定の成立条件の不成立回数が規定の回数となったことを条件に行われ、前記予測スラックの減少は、前記成立条件の成立回数が規定の回数となったことを条件に行われる
ことを特徴とする請求項３に記載のローカル・スラックの予測方法。
【請求項５】
前記予測スラックを増加させるために必要な前記成立条件の不成立回数を、同予測スラックを減少させるために必要な前記成立条件の成立回数よりも大きく設定する
ことを特徴とする請求項４に記載のローカル・スラックの予測方法。
【請求項６】
前記予測スラックの増加は、前記予測スラックが前記ターゲット・スラックに到達したとの推定の成立条件の不成立回数が規定の回数となったことを条件に行われ、前記予測スラックの減少は、前記成立条件の成立を条件に行われる
ことを特徴とする請求項３に記載のローカル・スラックの予測方法。
【請求項７】
前記規定の回数を、命令の種別により異ならせた
請求項４〜６のいずれか１項に記載のローカル・スラックの予測方法。
【請求項８】
命令の種別により、１回当たりの前記予測スラックの更新量を異ならせた
請求項１〜７のいずれか１項に記載のローカル・スラックの予測方法。
【請求項９】
前記予測スラックの上限値を、命令の種別により異ならせた
請求項１〜８のいずれか１項に記載のローカル・スラックの予測方法。
【請求項１０】
ロード命令、ストア命令、分岐命令及びその他命令の４つのカテゴリに前記命令の種別を行った
請求項７〜９のいずれか１項に記載のローカル・スラックの予測方法。
【請求項１１】
当該命令の実行に至るプログラムの分岐パターンの別に前記予測スラックを個別に設定する
請求項１〜１０のいずれか１項に記載のローカル・スラックの予測方法。
【請求項１２】
プロセッサで実行される命令のローカル・スラックを予測するローカル・スラック予測機構において、
各命令のローカル・スラックの予測値である予測スラックが記録保持されるスラック表と、
命令の実行に際して前記スラック表を参照してその命令の前記予測スラックを取得するとともに、その取得した予測スラックの分だけ実行レイテンシを増加させる実行レイテンシ設定手段と、
前記命令の実行時の振る舞いに基づき、同命令の現状のローカル・スラックの適正値であるターゲット・スラックに前記予測スラックが到達したか否かを推定する推定手段と、
前記推定手段により前記予測スラックが前記ターゲット・スラックに到達したとの推定がなされるまで、前記予測スラックを前記命令の実行毎に徐々に増加させる予測スラック更新手段と、
を備えることを特徴とするローカル・スラック予測機構。
【請求項１３】
前記推定手段は、
（Ａ）当該命令の実行時に分岐予測ミスが発生したこと、
（Ｂ）当該命令の実行時にキャッシュ・ミスが発生したこと、
（Ｃ）後続命令に対するオペランド・フォワーディングが発生したこと、
（Ｄ）後続命令に対するストア・データ・フォワーディングが発生したこと、
（Ｅ）当該命令が命令ウィンドウに存在する命令の中で最も古い命令となっていること、
（Ｆ）当該命令がリオーダ・バッファに存在する命令の中で最も古い命令となっていること、
（Ｇ）当該命令が、前記命令ウィンドウに存在する命令の中で最も古い命令に実行結果を渡す命令となっていること、
（Ｈ）当該命令が、同一のサイクルに実行される命令の中で最も多くの後続命令に実行結果を渡す命令となっていること、
（Ｉ）当該命令の実行結果を渡すことで、実行可能な状態となる後続命令の数が、予め定められた判定値以上となっていること、
のうちのいずれかを前記推定の成立条件として、前記ターゲット・スラックへの前記予測スラックの到達を推定する
ことを特徴とする請求項１２に記載のローカル・スラック予測機構。
【請求項１４】
前記予測スラックが前記ターゲット・スラックに到達したとの推定の成立条件が成立となったときにそのカウンタ値が増加／減少され、前記推定の成立条件が不成立となったときにそのカウンタ値が減少／増加される信頼性カウンタを設けるとともに、
前記予測スラック更新手段は、前記信頼性カウンタのカウンタ値が増加判定値となったことを条件に前記予測スラックを増加させ、同信頼性カウンタのカウンタ値が減少判定値となったことを条件に前記予測スラックを減少させる
ことを特徴とする請求項１２又は１３に記載のローカル・スラック予測機構。
【請求項１５】
前記信頼性カウンタでの前記推定の成立条件の成立時における前記カウンタ値の増加／減少量は、同推定の成立条件の不成立時における同カウンタ値の減少／増加量よりも大きく設定されてなる
ことを特徴とする請求項１４に記載のローカル・スラック予測機構。
【請求項１６】
前記カウンタ値の増加量及び減少量は、命令の種別により異ならされてなる
請求項１４又は１５に記載のローカル・スラック予測機構。
【請求項１７】
前記更新手段による各命令の前記予測スラックの１回当たりの更新量は、その命令の種別によって異ならされてなる
ことを特徴とする請求項１２〜１６のいずれか１項に記載のローカル・スラック予測機構。
【請求項１８】
前記更新手段によって更新される各命令の前記予測スラックには上限値が設定されるとともに、その上限値は命令の種別によって異ならされてなる
請求項１２〜１７のいずれか１項に記載のローカル・スラック予測機構。
【請求項１９】
前記命令は、ロード命令、ストア命令、分岐命令及びその他命令の４つのカテゴリに種別されてなる
請求項１６〜１８のいずれか１項に記載のローカル・スラック予測機構。
【請求項２０】
プログラムの分岐履歴が記録される分岐履歴レジスタを備えるとともに、
前記スラック表には、前記分岐履歴レジスタを参照して得られる分岐パターンの別に同命令の予測スラックを個別に記録されてなる
請求項１２〜１９のいずれか１項に記載のローカル・スラック予測機構。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プロセッサで実行される命令のローカル・スラックを予測する方法、及びその予測を行う機構に関する。
【背景技術】
【０００２】
近年、クリティカル・パスに関する情報を用いて命令の実行のスケジューリングを行うことで、マイクロプロセッサの高速化や消費電力の削減を図る技術の研究が数多く行われている。クリティカル・パスとは、たとえ１サイクルでもそのパス上の命令の実行レイテンシ、すなわち命令の実行開始からその結果が利用可能となるまでのサイクル数を増加させるとプログラム全体の実行サイクル数が増加してしまう命令列であり、プログラムの実行時間に決定的な影響を与える。しかしながら、クリティカル・パス情報によっては、クリティカル・パス上に在るか否かの２通りに命令を分類することしかできない。またクリティカル・パス上に存在する命令の数は、そうでない命令の数よりも通常は絶対的に少ないものとなっている。そのため、クリティカル・パス情報を用いて命令を分類し、分類したカテゴリの別で命令の処理系を分けた場合、処理系間の負荷バランスが悪くなってしまうことになる。
【０００３】
そこでクリティカル・パス情報の代りに、命令のスラック情報を用いることが考えられている。命令のスラックとは、プログラム全体の実行サイクル数を増加させることなく増加可能な命令の実行レイテンシのサイクル数を意味している。
【０００４】
ここで図１２を用いて、命令のスラックについて説明する。同図（ｂ）は、同図（ａ）に例示したプログラムの実行態様を示している。このプログラムは、命令ｉ０〜ｉ６の７つの命令からなっている。なお、「ｉ０」〜「ｉ６」は、各命令に対応したプログラム・カウンタの値を示している。同図において各命令ｉ０〜ｉ６に対応したノードの長さは、その命令の実行レイテンシを表しており、同図での実行レイテンシは、命令ｉ１，ｉ４が２サイクルと、その他の命令が１サイクルとなっている。また矢印は、命令間の依存関係を示しており、例えば命令ｉ３は、命令ｉ０と命令ｉ２とに依存している。ちなみに、命令ｉ１→ｉ２→ｉ４→ｉ６は、クリティカル・バスとなっている。
【０００５】
ここで命令ｉ０のスラックを考える。命令ｉ０の実行レイテンシを３サイクル増加させると、それに直接的、間接的にそれぞれ依存する命令ｉ３及び命令ｉ５の実行がそれぞれ１サイクルずつ遅れることになる。しかしながら、その場合にも、命令ｉ５は、プログラム中、もっとも最後に実行される命令ｉ６と同時刻に実行されることになり、プログラム全体の実行サイクル数は増加しない。ただし、命令ｉ０の実行レイテンシをそれ以上増加させると、命令ｉ５の実行が命令ｉ６よりも遅れてしまうようになる。したがって命令ｉ０のスラックは、「０〜３」である。一方、命令ｉ３の実行レイテンシ、或いは命令ｉ５の実行レイテンシのいずれかを、それ単独で１サイクル増加させてもプログラム全体の実行サイクル数は増加せず、２サイクル増加させればプログラム全体の実行サイクル数が増加するため、これら命令ｉ３，ｉ５のスラックは「０〜１」となる。なおクリティカル・パス上の命令ｉ１，ｉ２，ｉ４，ｉ６のスラックは、当然ながらいずれも「０」となる。
【０００６】
こうした命令のスラックが分かれば、プログラム全体の実行時間に影響を与えることなく、その命令の実行レイテンシをどの程度まで増加させられるかが分かるため、許容可能な各命令の実行レイテンシの増加度合に応じて、命令をより細かく分類することが可能となる。例えばスラックの最大値が「０」の命令、「１〜２」の命令、「３」以上の命令といった分類によって、命令を３つのカテゴリに分類することができる。
【０００７】
また命令を２つのカテゴリに分ける場合にせよ、例えばスラックの最大値が「０〜２」の命令と「３」以上の命令といったような分類の仕方も可能であるため、上記クリティカル・パスを用いる場合のようなカテゴリ間の命令数の偏りを緩和することが可能にもなる。
【０００８】
こうしたスラック情報を最大限に利用するには、各命令のスラックの最大値、すなわちグローバル・スラックを知る必要がある。しかしながら、グローバル・スラックは、依存する命令の実行レイテンシの増加により、動的に変化してしまう。例えば上述した命令ｉ５のグローバル・スラックは、図１２（ｂ）の状態では「１」となっている。ところが、命令ｉ０の実行レイテンシを３サイクル増加させれば、命令ｉ５の実行レイテンシが１サイクルでも増加すればプログラム全体の実行サイクル数の増加を招くようになる。よって、このときの命令ｉ５のグローバル・スラックは「０」となってしまう。またグローバル・スラックを判定するには、命令の実行レイテンシの増加がプログラムの最終的な実行サイクル数に与える影響をそのプログラムを実行している間に調べなければならない。そのため、グローバル・スラックの利用は、その実現が非常に困難となっている。
【０００９】
そこで、命令のグローバル・スラックではなく、ローカル・スラックを利用することが考えられている。命令のローカル・スラックとは、プログラム全体の実行サイクル数だけではなく、後続命令の実行にも影響を与えないスラックの最大値を意味している。例えば図１２（ｂ）の状態では、グローバル・スラックが「３」である命令ｉ０の実行レイテンシを３サイクル増加させても、プログラム全体の実行サイクル数は増加しないが、それに依存する命令ｉ３，ｉ５の実行が遅延してしまう。一方、命令ｉ０の実行レイテンシを２サイクル増加させても、後続の命令ｉ３，ｉ５の実行に遅れは生じない。よって、命令ｉ０のローカル・スラックは「２」となる。こうした命令のローカル・スラックであれば、その命令の実行レイテンシの増加が、その命令に依存する後続命令に与える影響に着目するだけで求めることができる。
【００１０】
従来、こうした命令のローカル・スラックの予測手法として、ある命令がレジスタ・データ或いはメモリ・データを定義した時刻と、その定義されたデータを最初に参照した時刻の差から、そのときの当該命令のローカル・スラックを求め、それを次回の同命令の実行時のローカル・スラックの予測値とする手法が提案されている。
【００１１】
図１３は、こうした従来の予測手法を実現するためのローカル・スラック予測機構のハードウェア構成を示している。同図に示すように、この予測機構を採用するプロセッサ５０は、フェッチ・ユニット１１、デコード・ユニット１２、命令ウィンドウ（Ｉ−ｗｉｎ）１３、レジスタ・ファイル（ＲＦ）１４、実行ユニット（ＥＵ）１５及びリオーダ・バッファ（ＲＯＢ）１６を備えて構成されている。一方、ローカル・スラック予測機構として、命令がレジスタ・データ及びメモリ・データを定義した時刻がそれぞれ記憶保持されるレジスタ定義表５１及びメモリ定義表５２と、求められた各命令のローカル・スラックの予測値を記憶保持するためのスラック表５３とが設けられている。レジスタ定義表５１は、物理レジスタ番号をインデクスとし、各インデクスにはその物理レジスタ番号に対応するレジスタにデータを定義した命令（命令のアドレスのインデクス部）とその定義の時刻とが記録保持される。またメモリ定義表５２は、メモリの参照アドレスをインデクスとし、各インデクスにはその参照アドレスにデータを定義した命令（命令のアドレスのインデクス部）とその定義の時刻が記録保持される。スラック表５３は、命令のアドレスをインデクスとし、各インデクスには、先の実行時における命令のローカル・スラックの演算値が記憶保持される。これら表に加え、予測機構には、データの定義時刻と参照時刻との差を求めるための演算器５４が設けられてもいる。
【００１２】
ここで図１２（ｂ）の命令ｉ０を例に、こうした従来の予測機構のローカル・スラックの予測動作を説明する。命令ｉ０がレジスタ（メモリ）にデータを書き込みを行うとき、レジスタ定義表５１（メモリ定義表５２）には「ｉ０」自身（命令のアドレス・インデクス）と共に現在の時刻「０」が記録される。その後、そのデータを命令ｉ３が使用するとき、レジスタ定義表５１（メモリ定義表５２）から、そのデータを定義した命令ｉ０とそのデータの定義された時刻「０」とが読み出される。そして現在時刻「３」と読み出されたデータの定義時刻「０」との差分が演算器５４により求められ、更にその値から「１」を引いた「２」が、先の実行時の命令ｉ０のローカル・スラックとしてスラック表５３に記憶される。そして、再び命令ｉ０がフェッチされたとき、スラック表５３が参照され、ｉ０に対応するエントリに記憶された「２」が同命令ｉ０のローカル・スラックの予測値として使用される。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
こうした従来の予測手法によれば、ある程度正確なローカル・スラックの予測が確かに可能ではあるが、スラック表に加え、２つの定義表と演算器とが必要であり、予測機構のハードウェア・コストは極めて高いものとなる。またプログラムの実行と並行して、定義表の参照／更新、時刻の引き算を高速度で行わなければならず、予測機構の動作による消費電力の増大が無視し難いものとなる虞もある。
【００１４】
本発明は、こうした実状に鑑みてなされたものであり、その解決しようとする課題は、より簡易な構成でローカル・スラックの予測を行うことのできるローカル・スラック予測方法及び予測機構を提供することにある。
【課題を解決するための手段】
【００１５】
上記課題を解決するため、本発明の請求項１に係るローカル・スラックの予測方法では、プロセッサで実行される命令を、その命令のローカル・スラックの予測値である予測スラックの値分だけその実行レイテンシを増加させて実行するとともに、前記命令の実行時の振る舞いに基づいて、現状におけるローカル・スラックの適正値であるターゲット・スラックに前記予測スラックが到達したか否かを推定し、到達したとの推定がなされるまで前記予測スラックを前記命令の実行毎に徐々に増加させていくようにしている。
【００１６】
上記予測方法では、命令のローカル・スラックの予測値（予測スラック）がその実行毎に徐々に増加されていく。こうして予測スラックを増加していけば、その値はやがては、現状のローカル・スラックの適正値（ターゲット・スラック）に到達するようになる。一方、命令の実行時のプロセッサの振る舞いから、予測スラックのターゲット・スラックへの到達を推定するとともに、その到達したとの推定が成立した時点で、予測スラックの増加が止められる。その結果、予測スラックを直接的に計算せずとも、ローカル・スラックを予測することができるようになる。
【００１７】
なお、上記のようなターゲット・スラックへの予測スラックの到達の推定は、請求項２に記載のように、その推定の成立条件として、
（Ａ）当該命令の実行時に分岐予測ミスが発生したこと、
（Ｂ）当該命令の実行時にキャッシュ・ミスが発生したこと、
（Ｃ）後続命令に対するオペランド・フォワーディングが発生したこと、
（Ｄ）後続命令に対するストア・データ・フォワーディングが発生したこと、
（Ｅ）当該命令が命令ウィンドウに存在する命令の中で最も古い命令となっていること、
（Ｆ）当該命令がリオーダ・バッファに存在する命令の中で最も古い命令となっていること、
（Ｇ）当該命令が、前記命令ウィンドウに存在する命令の中で最も古い命令に実行結果を渡す命令となっていること、
（Ｈ）当該命令が、同一のサイクルに実行される命令の中で最も多くの後続命令に実行結果を渡す命令となっていること、
（Ｉ）当該命令の実行結果を渡すことで、実行可能な状態となる後続命令の数が、予め定められた判定値以上となっていること、のうちのいずれかを含めるようにしている。
【００１８】
ここで上記（Ａ）、（Ｂ）の振る舞いは、予測スラックがターゲット・スラックを上回り、後続命令の実行が遅延した状態で観測される。また上記（Ｃ）、（Ｄ）の振る舞いは、予測スラックがターゲット・スラックと一致したときに観測される。よってこれらの振る舞いが観測されたときには、予測スラックがターゲット・スラックに到達したと推定することができる。
【００１９】
一方、上記（Ｅ）〜（Ｉ）の振る舞いは、従来より、命令がクリティカル・パス上にあるか否かの判定条件として用いられている。予測スラックがターゲット・スラックに到達すると、命令の実行レイテンシをそれ以上１サイクルでも増加させると後続命令の実行に遅延が生じるという、クリティカル・パス上の命令と似た状況となるため、上記到達の推定条件としても用いることが可能である。
【００２０】
なお、それまで予測スラックがターゲット・スラックに一致した状況となっているときにターゲット・スラックが動的に減少すると、予測スラックがターゲット・スラックを上回ってしまい、後続命令の実行が遅延されるという予測ミスのペナルティが発生してしまう。その点、請求項３に記載のように、予測スラックがターゲット・スラックに到達したとの推定がなされたときには同予測スラックを減少させるようにすれば、そうしたターゲット・スラックの動的な減少にも対応することができるようになる。
【００２１】
上記推定の成立、不成立をもって直ちに予測スラックを増加・減少させると、ターゲット・スラックが頻繁に増減を繰り返す場合に予測ミスのペナルティの発生頻度が高くなる虞がある。そうした場合にも、請求項４に記載のように、予測スラックがターゲット・スラックに到達したとの推定の成立条件の不成立回数が規定の回数となったことを条件に予測スラックを増加させ、同成立条件の成立回数が規定の回数となったことを条件に予測スラックを減少させるようにすれば、ターゲット・スラックが頻繁に増減したときの予測ミス・ペナルティの頻度の増加を抑えることができる。
【００２２】
この場合、請求項５に記載のように、予測スラックを増加させるために必要な成立条件の不成立回数を、同予測スラックを減少させるために必要な成立条件の成立回数よりも大きく設定すれば、予測スラックの増加は慎重に、その減少は迅速に行われるようになる。そのため、ターゲット・スラックが頻繁に増減を繰り返したときの予測ミス・ペナルティの頻度の増加を効果的に抑制することができる。こうした効果は、請求項６に記載のように、予測スラックがターゲット・スラックに到達したとの推定の成立条件の不成立回数が規定の回数となったことを条件に予測スラックを増加させる一方、予測スラックの減少は、成立条件の成立を条件に行うようにしても、同様に得ることができる。
【００２３】
なお命令の種別によっては、動的な変化度合やその変化の頻度などのローカル・スラックの挙動に違いがある。そこでローカル・スラックをより精度良く予測するには、請求項８や請求項９に記載のように、予測スラックの上限値や、その１回当たりの更新量（増加量や減少量）を、命令の種別毎に異ならせることが望ましい。また請求項４〜６の予測方法のように、上記推定の成立条件の成立回数、又は不成立回数が規定の回数となったことを条件に予測スラックを更新する場合には、請求項７に記載のように、そうした規定の回数を命令の種別毎に異ならせることで、より高い精度で予測を行うことができるようになる。ちなみに、そうした命令の種別としては、例えば請求項１０に記載のように、ロード命令、ストア命令、分岐命令及びその他命令の４つのカテゴリに分けることが考えられる。
【００２４】
ところで命令のローカル・スラックは、その命令の実行に至るまでのプログラムの分岐経路によって大きく変化することがある。その点、請求項１１に記載のように、当該命令の実行に至るプログラムの分岐パターンの別に予測スラックを個別に設定するようにすれば、命令の実行に至るまでのプログラムの分岐経路毎に個別にローカル・スラックが予測されることとなり、ローカル・スラックをより高い精度で予測することができるようになる。
【００２５】
一方、上記課題を解決するため、本発明の請求項１２に係るローカル・スラック予測機構では、プロセッサで実行される命令のローカル・スラックを予測する機構として、各命令のローカル・スラックの予測値である予測スラックが記録保持されるスラック表と、命令の実行に際して前記スラック表を参照してその命令の前記予測スラックを取得するとともに、その取得した予測スラックの分だけ実行レイテンシを増加させる実行レイテンシ設定手段と、前記命令の実行時の振る舞いに基づき、同命令の現状のローカル・スラックの適正値であるターゲット・スラックに前記予測スラックが到達したか否かを推定する推定手段と、前記推定手段により前記予測スラックが前記ターゲット・スラックに到達したとの推定がなされるまで、前記予測スラックを前記命令の実行毎に徐々に増加させる予測スラック更新手段と、を備えるようにしている。
【００２６】
上記構成では、予測スラック更新手段によって命令の予測スラックが、その命令の実行毎に徐々に増加され、実行レイテンシ設定手段によってその命令の実行レイテンシもその実行毎に同様に徐々に増加される。こうして予測スラックがターゲット・スラックに到達すると、命令の実行時のプロセッサの振る舞いがそれを示すものとなり、推定手段によりその旨の推定がなされ、その結果、上記予測スラック更新手段による予測スラックの増加が止められるようになる。そして以上により、直接計算することなく、予測スラックが求められる。
【００２７】
なお、推定手段によるターゲット・スラックへの予測スラックの到達の推定は、例えば請求項１３に記載のように、上記（Ａ）〜（Ｉ）のいずれか１つ、あるいはそのうちの複数をその推定の成立条件とすることで行うことができる。
【００２８】
また請求項１４に記載のように、予測スラックがターゲット・スラックに到達したとの推定の成立条件が成立となったときにそのカウンタ値が増加／減少され、推定の成立条件が不成立となったときにそのカウンタ値が減少／増加される信頼性カウンタを設けるとともに、前記信頼性カウンタのカウンタ値が増加判定値となったことを条件に前記予測スラックを増加させ、同信頼性カウンタのカウンタ値が減算判定値となったことを条件に前記予測スラックを減少させるように予測スラック更新手段をすれば、ターゲット・スラックが頻繁に増減を繰り返したときの予測ミス・ペナルティの発生頻度の増加を好適に抑制することができる。なお、そうした状態での予測ミス・ペナルティの発生頻度の増大をより効果的に抑制するには、請求項１５に記載のように、信頼性カウンタでの推定の成立条件の成立時におけるカウンタ値の増加／減少量を、同推定の成立条件の不成立時における同カウンタ値の減少／増加量よりも大きく設定することが望ましい。
【００２９】
更に命令の種別によるローカル・スラックの動的変化の様相の差違に対応してより精度良くローカル・スラックの予測を行うには、例えば請求項１７に記載のように、更新手段による各命令の予測スラックの１回当たりの更新量（増加量、減少量）を、その命令の種別によって異ならせることが望ましい。また更新手段によって更新される各命令の前記予測スラックには上限値を設定する場合には、請求項１８に記載のようにその上限値を命令の種別によって異ならせることも有効である。更には、請求項１４や請求項１５に記載の信頼性カウンタが設けられる場合には、請求項１６に記載のように、カウンタ値の増加量及び減少量を命令の種別により異ならせることが有効である。ちなみに命令の種別としては、例えば請求項１９に記載のように、ロード命令、ストア命令、分岐命令及びその他命令の４つのカテゴリに分類することが考えられる。
【００３０】
また請求項２０に記載のように、プログラムの分岐履歴を記録する分岐履歴レジスタを設けるとともに、その分岐履歴レジスタを参照して得られる分岐パターンの別に命令の予測スラックをスラック表に個別に記録するようにすることも、予測精度の向上には有効である。
【発明の効果】
【００３１】
本発明のローカル・スラックの予測方法及び予測機構では、命令のローカル・スラックの予測値（予測スラック）を計算で直接的に求めるのではなく、命令の実行時の振る舞いを観測しながら、適正値に到達するまで予測スラックを徐々に増加させることで求めている。そのため、予測スラックの直接演算に要する複雑な機構は不要であり、より簡易な構成でローカル・スラックの予測を行うことができる。
【発明を実施するための最良の形態】
【００３２】
以下、本発明を具体化した一実施形態を図１〜図１１を参照して詳細に説明する。
まず、本実施形態におけるローカル・スラックの予測方法の基本動作を説明する。本予測方法では、命令実行時のプロセッサの振る舞いを観測しつつ、命令のローカル・スラックの予測値の値を増加又は減少させるように更新していくことで、その予測値をローカル・スラックの実際の値に近づけていくようにしている。なお、以下の説明では、命令のローカル・スラックの予測値を「予測スラック」と記載し、命令のローカル・スラックの実際の値を「ターゲット・スラック」と記載する。
【００３３】
こうした本予測方法の基本動作を説明する。本予測方法ではまず、命令のフェッチに際してその命令の予測スラックを取得し、その取得した予測スラックの分だけその命令の実行レイテンシを増加させる。例えば実行レイテンシが本来「１サイクル」の命令について、その予測スラックが「２」であったときには、その命令の実行レイテンシは「３サイクル」に増加させる。なお、何れの命令についても、プログラムの開始後にその命令が始めてフェッチされたときには、そのローカル・スラックは「０」と予測する。すなわち、すべての命令についてその予測スラックの初期値は「０」に設定されている。その後、実行時における命令の振る舞いを観測し、予測スラックがターゲット・スラックに到達したと推定されるまで、予測スラックを徐々に増加させていく。
【００３４】
予測スラックがターゲット・スラックに到達したか否かの判定は、以下の態様で行われる。予測スラックを増加させていった結果、その値がターゲット・スラックに一致した値に達した状況では、その命令の実行レイテンシを更に１サイクルでも増加させると、それに依存する後続命令の実行に遅延が生じてしまう状態となっている。また予測スラックがターゲット・スラックを上回った状況では、既に後続命令の実行に遅延が生じた状態となっている。こうした状態では、実行時に命令は、（Ａ）分岐予測ミス、（Ｂ）キャッシュ・ミス、（Ｃ）後続命令に対するオペランド・フォワーディング、（Ｄ）後続命令に対するストア・データ・フォワーディング、などの振る舞いを示すと考えられる。これらの命令の振る舞い（Ａ）〜（Ｄ）について、以下に説明する。
【００３５】
まず上記（Ａ）の分岐予測ミスについて説明する。パイプライン処理を行なうプロセッサは、多数の命令を流れ作業的に同時に実行するため、分岐命令で以後に実行される命令列が変更されると、既に処理を開始した後続命令をすべて破棄しなくてはならず、処理効率が低下する。これを防ぐため、以前に当該分岐命令が実行されたときの分岐の発生状況から命令が分岐するか否かを予測し、その予測結果に従って分岐予測先の命令を投機実行するようにしている。ここで予測スラックがターゲット・スラックを上回った状況を考える。こうした状況では、先行命令の実行レイテンシが過剰に増加されて、それに依存する後続命令の実行に遅延が生じる。このような場合、適正な分岐予測ができなくなり、分岐の予測結果を誤り易くなる。そのため、分岐予測ミスが発生したときには、予測スラックがターゲット・スラックを上回ってしまっている可能性が高いと考えることができる。
【００３６】
次に、上記（Ｂ）のキャッシュ・ミスについて説明する。多くのプロセッサでは、使用頻度の高いデータ等を、高速なキャッシュ・メモリに蓄積しておくことで、低速な記憶装置へのアクセスを低減し、プロセッサの処理を高速化するようにしている。先行命令の予測スラックがターゲット・スラックを上回った状態となると、こうしたキャッシュ動作を適正に行うことができなくなり、キャッシュ・ミスが発生し易くなる。したがって、キャッシュ・ミスが発生したときにも、予測スラックがターゲット・スラックを上回ってしまっている可能性が高いと考えることができる。
【００３７】
続いて上記（Ｃ）及び（Ｄ）の後続命令に対するオペランド・フォワーディング及びストア・データ・フォワーディングについて説明する。先行命令とその先行命令の定義したデータを参照する後続命令との実行間隔が短いと、データの書き込み完了前に後続命令がそのデータを読み込もうとしてデータ・ハザードが発生してしまうことがある。そのため、多段パイプラインを有するプロセッサの多くでは、バイパス回路を設けて、書き込み前のデータを後続命令に直接与えるオペランド・フォワーディングやストア・データ・フォワーディングを行うことで、そうしたデータ・ハザードを回避するようにしている。こうしたフォワーディングは、先行命令の定義したデータを参照する後続命令が、先行命令の直後に連続して実行されるときに発生する。したがって、オペランド・フォワーディングやストア・データ・フォワーディングが発生したときには、予測スラックがターゲット・スラックと一致していると判断することができる。
【００３８】
本予測方法では、命令実行時の振る舞いが，上記（Ａ）〜（Ｄ）のいずれかに該当するとき、予測スラックがターゲット・スラックに到達したと推定し，そうでないときには未到達であると判定するようにしている。こうした予測スラックがターゲット・スラックに到達したとの推定の成立条件を上記（Ａ）〜（Ｄ）の論理和条件とし、ターゲット・スラック到達条件と記載する。なお上記（Ａ）〜（Ｄ）のような命令実行時の振る舞いを検出する機構は、分岐予測、キャッシュ、フォワーディングを行うプロセッサであれば、通常、元より備えられている。そのため、ローカル・スラック予測のためにそうした検出機構を新規追加せずとも、上記到達条件の成立の有無を確認することが可能である。
【００３９】
図１に、こうした本予測方法の基本動作に基づいて、先の図１２（ａ）のプログラムを繰り返し実行する過程を示す。図１（ａ）〜（ｃ）は、プログラムの１〜３回目の実行時の様子をそれぞれ示している。なお、ここでは、命令ｉ０のみをローカル・スラックの予測対象とし、その予測スラックを１回につき「１」ずつ増加させるものとしている。
【００４０】
さてプログラムの１回目の実行では、命令ｉ０の予測スラックは初期値「０」であり、ターゲット・スラック「２」に未到達であるため、命令ｉ０の予測スラックが「１」増加される。その結果、同図（ｂ）に示すように、２回目のプログラムの実行では、命令ｉ０の予測スラックは「１」となり、実行レイテンシが１サイクル分増加された状態で命令ｉ０が実行される。このときにも、予測スラックはターゲット・スラックに未到達であるため、予測スラックは更に「１」増加される。これにより、３回目のプログラムの実行では、命令ｉ０の予測スラックは「２」ととなり、同命令ｉ０に引き続き後続の命令ｉ３が実行されるようになる。そしてその結果、後続の命令ｉ３の実行に際しては、オペランド・フォワードが行われるようになり、上記ターゲット・スラック到達条件を満たすようになるため、命令ｉ０の予測スラックはそれ以上増加されずに「２」のまま維持される。以上のように、命令実行時の振る舞いからターゲット・スラックへの到達が確認されるまで、予測スラックを徐々に増加させることで、命令ｉ０のローカル・スラックを予測することができる。
【００４１】
（予測スラックの減少）
上記のような本予測方法の基本動作は、ターゲット・スラックが静的に一定の値に維持されているという前提であれば、それだけでも十分に機能する。ただし、命令のターゲット・スラックは、動的にその値が増減する。ターゲット・スラック到達後、そのターゲット・スラックがより大きい値に変化した場合には、上記到達条件が再び不成立となり、予測スラックは変化後のターゲット・スラックに向けて再び増加するようになるため、特に問題は生じない。一方、ターゲット・スラックが予測スラックよりも小さい値に変化してしまった場合には、上記基本動作だけでは予測スラックをその変化に追従させることができなくなってしまう。
【００４２】
この上記基本動作の問題を、図２（ａ）に基づき説明する。図２（ａ）には、ある命令の予測スラックがターゲット・スラックに一旦到達した後の時刻ｔ１において、ターゲット・スラックが予測スラックを下回る値に減少したときの予測スラック及びターゲット・スラックの推移が示されている。同図に示すように、プログラムの開始後、予測スラックは、ターゲット・スラックに到達するまで増加され、その到達後は到達時の値に維持される。この状態で時刻ｔ１においてターゲット・スラックが減少すると、予測スラックは、ターゲット・スラックを上回るようになる。しかしながら、上記基本動作では、そうした状態となっても予測スラックは、その後も更新されずに現状の値に維持される。そして予測スラックがターゲット・スラックを上回った分、後続命令の実行が遅延されてしまうようになり、プロセッサの処理に悪影響を与えるようになる。
【００４３】
こうした問題は、ターゲット・スラックが予測スラックを下回ったときには予測スラックを減少させることで解決可能である。こうした予測スラックの減少を実現する手法としては、スラック予測を行わなかったときの後続命令の実行時刻を利用する方法が考えられる。すなわち、後続命令が本来実行される筈だった時刻と実際に実行された時刻との差を求めれば、先行命令のスラック予測のミスによる後続命令の実行時刻の遅延量が分かり、その分、先行命令の予測スラックを減少させれば、予測スラックとターゲット・スラックを一致させることができるようになる。また、ターゲット・スラックを直接計算し、現状の予測スラックと比較するといった方法も考えられる。しかしながら、これらの手法では、資源制約、データ依存、制御依存等の命令の実行時刻を決定する様々な要素を考慮して、後続命令の本来の実行時刻やターゲット・スラックを計算しなければならず、容易に実現することはできないものとなっている。
【００４４】
そこでここでは、上述のターゲット・スラック到着条件を利用して予測スラックがターゲット・スラックを上回っている（厳密には、予測スラックがターゲット・スラックと一致する場合も含む）か否かを判定し、ターゲット・スラックを下回るようになるまで予測スラックを減少させるという手法を採用する。こうした手法では、命令の本来の実行時刻やターゲット・スラックそのものの計算のような複雑な計算等を行わずとも、極めて容易にターゲット・スラックの動的な減少に対応することができる。
【００４５】
図２（ｂ）に、こうした手法を採用した場合のローカル・スラックの動的な減少に対する予測スラックの推移を示す。この場合にも、プログラムの開始後、予測スラックは、ターゲット・スラックに到達するまで増加される。ただし、この場合には、ターゲット・スラックに到達すると予測スラックは、一旦は減少されるが、それによりターゲット・スラックを下回るようになるため、即座に増加に転じ、再びターゲット・スラックに到達するようになる。したがってこの場合には、ターゲット・スラックに一旦到達した後、予測スラックは、小幅な増減を繰り返しながら、ターゲット・スラックの直下を推移することになる。その後、時刻ｔ１において、ターゲット・スラックが予測スラックを下回る値に減少すると、予測スラックは、その減少したターゲット・スラックを下回るまで減少していく。そしてターゲット・スラックを下回った後は、ターゲット・スラックの直下において再び小幅な増減を繰り返すようになる。
【００４６】
このように上記手法を採用すれば、ローカル・スラックの動的な減少にも対応することが可能となる。
（信頼性の導入）
上記のような予測スラックの減少手法の採用により、ローカル・スラックの動的な減少にも予測スラックを追従させることができる。ただし、図３（ａ）のようにターゲット・スラックが頻繁に増加と減少とを繰り返す場合には、予測ミスのペナルティが頻繁に発生しまうようになる。すなわち、上述の予測スラックの減少手法をそのまま採用した場合、ターゲット・スラックに未到達であれば、予測スラックは即座に増加される。ところが、その直後にターゲット・スラックが減少すると、予測スラックはターゲット・スラックを上回ってしまうことになる。そしてターゲット・スラックが増減を繰り返すと、予測スラックはそれに連動して増減し、ターゲット・スラックが減少する度に後続命令の実行の遅延が発生するようになる。
【００４７】
そこでここでは、ターゲット・スラック到達条件の判定に基づく予測スラックの増減操作に、信頼性という概念を導入する。すなわち、上記到達条件の単一の判定結果に応じて直ちに予測スラックを増減するのではなく、同到達条件の成立回数・不成立回数がある規定の回数となったときに始めて実際に予測スラックを増減させるようにする。具体的には、命令の予測スラック毎に信頼性カウンタを設け、そのカウンタ値を、命令がターゲット・スラック到達条件を満たしていれば減少させ、満たしていなければ増加させるようにする。そして、そのカウンタ値が「０」（減少判定値）となったら予測スラックを減少させ、ある閾値（増加判定値）を越えたら予測スラックを増加させるようにする。なお予測スラックの増加を慎重に行うため、予測スラックを増加させたときには、信頼性カウンタのカウンタ値は「０」にリセットすることとする。こうした信頼性カウンタを用いた予測スラックの増減を行えば、予測スラックの増加は、上記到達条件の連続した不成立回数が規定の回数となったことを条件に行われ、予測スラックの減少は、同到達条件の連続した成立回数が規定の回数となったことを条件に行われるようになる。
【００４８】
もっとも、予測スラックがローカル・スラックを上回ったときの後続命令の実行の遅延発生を回避する上では、予測スラックの増加は慎重に、予測スラックの減少は迅速に行うことが望ましい。そのためには、上記達成条件成立時のカウンタ値の減少量を、不成立時の同カウンタ値の増加量よりも大きくすればよい。あるいは、命令がターゲット・スラック到達条件を満たしていれば、カウンタ値を「０」にリセットし、１度の到達条件の成立で強制的に予測スラックを減少させるようにしてもよい。
【００４９】
図３（ｂ）に、信頼性を導入したときの予測カウンタの推移を示す。ここでは、到達条件成立時に信頼性カウンタを「０」にリセットするようにしている。この場合、予測スラックは、ターゲット・スラックに向けて、信頼性を導入しない場合に比して緩やかに増加していく。一方、ターゲット・スラックに到達する、あるいはそれを越えると、予測スラックは、即座に減少する。その結果、同図のようにターゲット・スラックが頻繁に増減を繰り返しても、予測スラックがターゲット・スラックを超過する頻度は低減されるようになる。
【００５０】
（ローカル・スラック予測機構の構成）
次に、上述した予測方法を実現する、本実施形態のローカル・スラック予測機構について説明する。図４は、本実施形態のローカル・スラック予測機構のハードウェア構成を説明する。
【００５１】
同図４に示すように、本実施形態のローカル・スラック予測機構の適用されたプロセッサ１０は、フェッチ・ユニット１１、デコード・ユニット１２、命令ウィンドウ（Ｉ−ｗｉｎ）１３、レジスタ・ファイル（ＲＦ）１４、実行ユニット（ＥＵ）１５及びリオーダ・バッファ（ＲＯＢ）１６を備えて構成されている。このプロセッサ１０を構成する各ユニットの機能は次の通りとなっている。フェッチ・ユニット１１は、主記憶装置からの命令の読み込みを行う。デコード・ユニット１２は、読み込まれた命令の内容の解析（デコード）し、命令ウィンドウ１３及びリオーダ・バッファ１６にそれぞれ格納する。命令ウィンドウ１３は、実行前の命令を一時的に格納するバッファであり、プロセッサの制御回路は、このバッファから命令を取り出して、実行ユニット１５に順次投入する。一方、リオーダ・バッファ１６は、命令を格納するＦＩＦＯ式のスタックであり、格納された命令の中で格納の順が最も早い命令の実行が終了すると、その命令が取り出される（コミットされる）。なおレジスタ・ファイル１４は、命令の実行に必要なデータや命令の実行結果、実行中、実行予定の命令のアドレス・インデクス等をそれぞれ格納する各種レジスタの実体となっている。
【００５２】
さて本実施形態のローカル・スラック予測機構は、予測スラックを記憶保持するスラック表２０によって構成されている。このスラック表は、命令のＰＣ（その命令を格納する主記憶装置のメモリ・アドレス）をインデクスとし、対応する命令の予測スラックと、信頼性カウンタのカウンタ値とがエントリとして記憶保持される。
【００５３】
フェッチ・ユニット１１は、命令のフェッチ時に、その命令のＰＣをインデクスとしてスラック表２０を参照し、該当命令の予測スラックを取得するとともに、その取得した予測スラックの分、該当命令の実行レイテンシを増加させる。そして命令のコミット時に、実行時の命令の振る舞いに基づき、その命令に対応したスラック表２０の各エントリの値の更新が行われる。なお、スラック表２０の各エントリの更新に関して、次のパラメータが定数として予め設定されている。
・Ｖｍａｘ：予測スラックの最大値、
・Ｖｍｉｎ：予測スラックの最小値（＝０）、
・Ｖｉｎｃ：予測スラックの１回あたりの増加量、
・Ｖｄｅｃ：予測スラックの１回あたりの減少量、
・Ｃｍａｘ：信頼性カウンタのカウンタ値の最大値、
・Ｃｍｉｎ：信頼性カウンタのカウンタ値の最小値（＝０）、
・Ｃｔｈ：信頼性カウンタの閾値（増加判定値）、
・Ｃｉｎｃ：信頼性カウンタのカウンタ値の１回あたりの増加量、
・Ｃｄｅｃ：信頼性カウンタのカウンタ値の１回あたりの減少量。
【００５４】
スラック表２０のエントリの更新の態様を説明する。上述したターゲット・スラック到達条件が成立していれば、信頼性カウンタのカウンタ値を「０」にリセットし，そうでなければ増加量Ｃｉｎｃだけ同カウンタ値を増加させる。ここでカウンタ値が閾値Ｃｔｈ以上になったら、予測スラックを上記増加量Ｖｉｎｃだけ増加させるとともに、カウンタ値を「０」にリセットする。一方、信頼性カウンタのカウンタ値が「０」となったら、予測スラックを上記減少量Ｖｄｅｃだけ減少させる。なお本実施形態では、ターゲット・スラック到達条件が成立すれば信頼性を「０」にリセットするようにしており、上記カウンタ値の減少量Ｃｄｅｃを上記閾値Ｃｔｈと同値としている。また本実施形態では、予測スラックを増加させる際に、信頼性カウンタのカウンタ値が「０」にリセットされるため、カウンタ値の最大値Ｃｍａｘは、上記閾値Ｃｔｈと同値となっている。
【００５５】
（ローカル・スラック予測機構の評価）
続いて、以上説明した本実施形態のローカル・スラック予測機構の評価結果について説明する。発明者等は、スーパスカラ・プロセッサ用のシミュレータ（Simple Scalar Tool Set）を用いて、上記スラック表２０のエントリの更新に係る各パラメータを変化させながら、表１に示される測定条件で予測機構の評価を行っている。この評価には、「MIPS R100000」の拡張命令セットである「Simple Scalar/PISA」が使用されている。またこの評価には、ベンチマーク・プログラムとして、「SPECint2000 」の「bzip2 」、「gcc 」、「gzip」、「mcf 」、「paser 」、「perl」、「votex 」、及び「vpr 」の８つのプログラムが使用されている。
【００５６】
【表１】
2007249710.tif 000003
【００５７】
なお、スラック表２０の各エントリの更新に関するパラメータのうち、変更可能なものは、予測スラックの最大値Ｖｍａｘ、予測スラックの１回あたりの増加量Ｖｉｎｃ、減少量Ｖｄｅｃ、信頼性カウンタの閾値Ｃｔｈ、及び信頼性カウンタのカウンタ値の１回あたりの増加量Ｃｉｎｃ、減少量Ｃｄｅｃの６つである。ただし、これらのすべてを可変値とすると、組合せは膨大な数になるため、幾つかのパラメータをある値に固定して評価を行っている。まず増加量Ｃｉｎｃと閾値Ｃｔｈとの両パラメータの値が変わっても、それらの比が変わらなければ予測スラックの増加の頻度は同じであるため、増加量Ｃｉｎｃは「１」に固定し、閾値Ｃｔｈのみを可変とした。また予測スラックをできる限りターゲット・スラックに近づけるため、予測スラックの１回当たりの増加量Ｖｉｎｃは「１」に固定した。さらに予測スラックを可能な限り迅速に減少させるため、予測スラックの１回当たりの減少量Ｖｄｅｃを同予測スラックの最大値Ｖｍａｘと同値に固定した。したがって、この評価での可変パラメータは、予測スラックの最大値Ｖｍａｘと信頼性カウンタの閾値Ｃｔｈの２つとなっている。
【００５８】
こうした評価においては、スラック命令の数、予測スラックの総積算値、ＩＰＣ（Instruction Per Clock ：１サイクル当たりの命令実行数）が評価値として測定されている。ここでのスラック命令とは、予測スラックに基づいて実行レイテンシが１サイクル以上増加された命令である。なおＩＰＣは、プロセッサの処理性能を測る指標値となる。
【００５９】
図５は、評価におけるスラック命令数とＩＰＣの測定結果を示している。同図の縦軸は、最大値Ｖｍａｘ及び閾値Ｃｔｈの値の各組合せにおける、全実行命令数に対するスラック命令数の比率と、スラック予測を一切行わなかったときのＩＰＣに対する測定ＩＰＣの比率とを示している。また最大値Ｖｍａｘの各値（「１」，「５」，「１０」，「１５」）のそれぞれにおける４本組の縦棒は、図中左側からそれぞれ閾値Ｃｔｈが「１」，「５」，「１０」，「１５」の場合での測定結果をそれぞれ表すものとなっている。
【００６０】
同図に示されるように、閾値Ｃｔｈを増加させるとスラック命令数は減少する。これは閾値Ｃｔｈの増加により、予測スラックの増加条件が厳しくなり、予測スラックの増加頻度が低くなるためである。ただし、閾値Ｃｔｈを増加すれば、予測スラックがターゲット・スラックを上回る頻度が低くなるため、ＩＰＣは向上するようになる。この結果から、上記信頼性の導入によって、上記スラック予測ミスのペナルティによる命令処理性能の低下を抑えられることが確認された。一方、予測スラックの最大値Ｖｍａｘを増加させると、予測スラックがより大きい値を取ることが可能となるため、スラック予測ミスのペナルティが大きくなり、処理性能（ＩＰＣ）は低下するようになる。
【００６１】
図６に、上記測定結果での予測スラックとＩＰＣとの関係を示す。なお同図の縦軸は、パラメータ（Ｖｍａｘ，Ｃｔｈ）＝（１，１）の場合を基準（１００％）とした予測スラックの総積算値のベンチマーク平均値の比率を、横軸は、スラック予測を一切行わなかったときを基準（１００％）としたＩＰＣのベンチマーク平均値の比率をそれぞれ示している。なお、同図の各点に付された数字は、閾値Ｃｔｈの値を示している。
【００６２】
同図に示されるように、予測スラックの最大値Ｖｍａｘを増加させると、処理性能は低下するが、予測スラックは大幅に増大する。また最大値Ｖｍａｘとともに閾値Ｃｔｈを増加させることで、ＩＰＣがほとんど低下せずに、予測スラックが増加するパラメータの組合せも幾つか確認された。例えばパラメータ（Ｖｍａｘ，Ｃｔｈ）＝（１，１）の場合に対して、（５，１５）の場合には、ＩＰＣの低下をわずか０．３％に留めながらも、予測スラックは約２．２倍となっている。
【００６３】
以上の結果から明らかなように、処理性能は、スラック命令数や予測スラックとトレード・オフの関係にあり、適用対象での要求に応じて、各パラメータの最適値は異なることとなる。
【００６４】
（機能ユニットの消費電力の削減）
次に、以上説明した本実施形態のローカル・スラック予測機構の応用例として、その予測結果の利用によりプロセッサの機能ユニット（実行ユニット）の消費電力を削減する手法について説明する。
【００６５】
図７は、ローカル・スラックの予測結果を利用して機能ユニットの消費電力を削減可能に構成したプロセッサの一例を示している。同図に例示したプロセッサでは、消費電力は高いものの高速動作する実行ユニット１５ａと、動作は遅いものの消費電力は低い実行ユニット１５ｂとの２種類の実行ユニットを備えている。そして、予測スラックの小さい命令は高速の実行ユニット１５ａに、予測スラックの大きい命令は低速の実行ユニット１５ｂにと、命令を実行させるユニットを振り分けることで、処理性能を低下させずに機能ユニットの消費電力を削減することができる。
【００６６】
発明者等は、こうした応用例の評価を行っている。この評価には、整数演算用の機能ユニット（ｉＡＬＵ）として、高速・高電力消費のユニットと低速・低電力消費のユニットとの２種類をユニットを備えるプロセッサのモデルが用いられている。両ユニットの電源電圧はそれぞれ「１．１Ｖ」、「０．７Ｖ」となっており、実行レイテンシはそれぞれ「１サイクル」、「２サイクル」となっている。そして予測スラックが「１」の命令を低速なｉＡＬＵに、予測スラックが「０」の命令を高速なｉＡＬＵにそれぞれ振り分けるようにした。ただし、命令の実行時に、低速なｉＡＬＵに空きが無ければ高速なｉＡＬＵに、高速なｉＡＬＵに空きが無ければ高速なｉＡＬＵに、予測スラックに拘わらず、命令を割り当てることとした。
【００６７】
またこの評価では、パラメータ（Ｖｍａｘ，Ｃｔｈ）＝（１，１５）として、スラック表のエントリの変更に係るすべてのパラメータを固定した条件で、全６個のｉＡＬＵのうち、高速なｉＡＬＵの数と低速なｉＡＬＵの数との比率を変更しながら、ＩＰＣ及び
ｉＡＬＵ全体のエネルギ遅延積（ＥＤＰ：Energy Delay Product）を測定した。ＥＤＰは、機能ユニットの電力消費量を測る指標値となっている。なお、以下では、高速なｉＡＬＵをｎ個有する、すなわち低速なｉＡＬＵをｍ（＝６−ｎ）個有するモデルを、（ｎｆ，ｍｓ）モデルと記載する。
【００６８】
図８及び図９に、各モデルでの各ベンチマークでのＩＰＣ及びＥＤＰの測定結果を示す。図８の縦軸は、（６ｆ，０ｓ）モデル（全ｉＡＬＵが高速なモデル）でのＩＰＣを基準（１００％）としたＩＰＣの比率を、図９の縦軸は、同じく（６ｆ，０ｓ）モデル（全ｉＡＬＵが高速なモデル）でのＥＤＰを基準（１００％）としたＥＤＰの比率をそれぞれ示している。また両図における各ベンチマーク・プログラムにおける６本組の縦棒は、図中左側から（５ｆ，１ｓ）、（４ｆ，２ｓ）、（３ｆ，３ｓ）、（２ｆ，４ｓ）、（１ｆ，５ｓ）、（０ｆ，６ｓ）の各モデルでの測定結果をそれぞれ表すものとなっている。
【００６９】
両図に示されるように、いずれのベンチマーク・プログラムでも、同様の傾向が見られる。すなわち、高速なｉＡＬＵの数の減少させると、ほとんどの場合、ＥＤＰは単調に減少していくようになる。ただし、ローカル・スラックの予測結果に基づいて命令の振り分けを行ったことで、高速なｉＡＬＵの数の減少に伴うＩＰＣの低下は好適に抑制されている。例えば（０ｆ，６ｓ）モデル、すなわち全ｉＡＬＵが低速なモデルでは、ベンチマーク平均のＩＰＣの低下が「２０．２％」、ＥＤＰの削減率は「４１．６％」となっている。これに対して（１ｆ，６ｓ）モデルでは、ＥＤＰの削減率が「３４．５％」もあるにも拘わらず、ＩＰＣの低下は「１０．５％」に留まっている。更に（３ｆ、３ｓ）モデルでは、ＩＰＣの低下をわずか「３．８％」としながらも、ＥＤＰの削減率は「２０．３％」にもなる。
【００７０】
なお上記評価では、機能ユニットの消費電力のみに着目しており、スラック表の動作に要する消費電力については全く考慮していないため、プロセッサ全体の消費電力の削減効果は上記の結果よりは低くなる。ただし、スラック表の動作に要する消費電力を十分に低く抑えることさえできれば、プロセッサ全体の消費電力の削減にも十分な効果を期待することができる。もっとも、機能ユニットはチップ上における代表的なホットスポットの一つであり、たとえプロセッサ全体の消費電力の削減が適わずとも、機能ユニットの消費電力が抑えられれば、チップ上のホットスポットの分散させることができるという効果は得ることができる。
【００７１】
なお、本実施形態のローカル・スラック予測機構では、フェッチ・ユニット１１は、上記実行レイテンシ設定手段としての機能も兼ねている。またスラック表２０（厳密にはそのエントリの更新に係る動作回路）が、上記推定手段及び予測スラック更新手段としての機能も兼ね備えるようにしている。
【００７２】
以上説明した本実施形態のローカル・スラックの予測方法、及びローカル・スラック予測機構によれば、次の効果を奏することができる。
（１）予測スラックを計算で直接的に求めるのではなく、命令の実行時の振る舞いを観測しながら、ターゲット・スラックに到達するまで予測スラックを徐々に増加させることで求めているため、予測スラックの直接演算に要する複雑な機構は不要であり、より簡易な構成でローカル・スラックの予測を行うことができる。
【００７３】
（２）プロセッサが元より備える検出機構で検出可能な上記条件（Ａ）〜（Ｄ）の命令実行時の振る舞いをローカル・スラック到達条件としたため、ローカル・スラック予測のために格別な検出機構を追加設置せずとも、予測スラックのターゲット・スラックへの到達を確認することができる。
【００７４】
（３）ターゲット・スラック到達条件の成立をもって、予測スラックを減少させるようにしているため、予測スラックの過剰評価による後続命令の実行遅延の発生を好適に抑制することができる。
【００７５】
（４）信頼性カウンタを設置し、予測スラックの増加は慎重に、減少は迅速に行うようにしているため、ターゲット・スラックが頻繁に増減を繰り返す場合にも、予測スラックの過剰評価による後続命令の実行遅延が発生する頻度を低く抑えることができる。
【００７６】
続いて、上記ローカル・スラックの予測方法、及び予測機構の更なる機能の拡張について説明する。
（スラック表のインデクス手法の拡張）
プログラム内の分岐命令の振る舞いは多くの場合、その分岐を実行するまでに、どのような関数や命令を実行してきたか（これ以降、制御フローと呼ぶ）に依存する。この性質を利用して、分岐命令の結果をより高い精度で予測する手法が提案されている。従来、こうした分岐予測手法は、命令の投機実行の精度向上に利用されているが、ローカル・スラックの予測においても、同様の原理を導入することで、予測精度の更なる向上を期待できる。以下、制御フローを考慮して、スラック予測を更に精度良く行う手法について説明する。
【００７７】
プログラムは、分岐命令を用いて、どのような関数や命令を実行するのかを決定しているため、プログラム中の分岐条件に着目することで制御フローを単純化することが可能である。具体的には、分岐条件が成立したなら「１」、成立しなかったら「０」として、プログラム中の分岐条件の成立、不成立の履歴（分岐履歴）を記録する。例えば分岐条件がフェッチ順に、成立（１）→成立（１）→不成立（０）→成立（１）であったときの分岐履歴は、新しいもの程下位に記録した場合に「１１０１」と表される。分岐履歴をスラック予測に利用するために、分岐履歴とその命令のＰＣとからスラック表へのインデクスを生成する。このようにすれば、ＰＣと制御フローの双方を考慮して、スラックを予測することができるようになる。例えば、ＰＣが同じでも、制御フローが異なれば、スラック表の別々のエントリを使用するので、制御フローに応じた予測ができるようになる。
【００７８】
図１０に、制御フローを考慮したスラック予測を行うローカル・スラック予測機構のハードウェア構成の一例を示す。この構成では、図４に例示のものに加え、更に分岐履歴レジスタ２１Ａ、分岐履歴レジスタ２１Ｂ、及び２つのインデクス生成回路２２Ａ，２２Ｂが新たに追加されている。分岐履歴レジスタ２１Ａ及び分岐履歴レジスタ２１Ｂは、分岐履歴を記録するレジスタとなっている。
【００７９】
また両インデクス生成回路２２Ａ，２２Ｂは、入力の違いを除いて同一の回路構成とされている。命令のフェッチ時には、分岐履歴レジスタ２１Ａとその命令のＰＣとを入力として、インデクス生成回路２２Ａがスラック表２０へのインデクスを生成し、スラック表２０の参照を行う。一方、命令のコミット時には、分岐履歴レジスタ２１Ｂとその命令のＰＣとを入力として、インデクス生成回路２２Ｂがスラック表２０へのインデクスを生成し、スラック表２０のエントリの更新を行う。以下、これら分岐履歴レジスタ２１Ａ，２１Ｂ及びインデクス生成回路２２Ａ，２２Ｂについて更に詳細に説明する。
【００８０】
まず分岐履歴レジスタ２１Ａ，２１Ｂの分岐履歴の更新動作について説明する。
分岐履歴レジスタ２１Ａは、プロセッサの分岐予測結果に基づき分岐履歴を記録する。具体的な更新動作は、分岐命令がフェッチされると分岐履歴レジスタ２２Ａの保持する値を１ビット左にシフトするとともに、フェッチ・ユニット１１においてその分岐命令の分岐条件が成立と予測されていれば「１」を、不成立と予測されていれば「０」を、分岐履歴レジスタ２１Ａの最下位ビットに書き込む、という手順で行われる。
【００８１】
一方、分岐履歴レジスタ２１Ｂは、プロセッサの分岐実行結果をもとにして、分岐履歴を記録する。具体的な更新動作は、分岐命令がコミットされると、分岐履歴レジスタ２１Ｂの保持する値を１ビット左にシフトし、その分岐命令の分岐条件が成立したならば「１」を、不成立ならば「０」を、分岐履歴レジスタ２１Ｂの最下位ビットに書き込む、という手順で行われる。
【００８２】
このように、分岐履歴の取り方が２通り存在する理由は、スラックの参照をフェッチ時に行い、スラック表の更新をコミット時に行うという、両分岐履歴レジスタ２１Ａ，２１Ｂの分岐履歴を利用する時期の違いにある。フェッチ時には、分岐命令は未だ実行されておらず、プロセッサは、分岐条件が成立するかしないかを予測して、命令をメモリから読みだしている。そのため、フェッチ時に使用される分岐履歴レジスタ２１Ａには、分岐予測に基づいて分岐履歴を記録していくしかない。一方、コミット時には、分岐命令は既に実行されており、実行結果に基づいて分岐の履歴を記録することができる。
【００８３】
次に、図１１を参照して、インデクス生成回路２２Ａ，２２Ｂによるインデクス生成態様の詳細を説明する。図１１（ａ）は、上記実施形態でのインデクス生成、すなわち命令のＰＣのみを使用したインデクス生成手法を示している。この場合、ＰＣの一部のビットを切り出して、それをスラック表２０へのインデクスとして使用するようにしている。
【００８４】
図１１（ｂ）は、分岐履歴とＰＣとを使用したインデクス生成の一例を、図１１（ｃ）は、同じく分岐履歴とＰＣとを使用したインデクス生成のもう一つの例を、それぞれ示している。なお実際のプロセッサへの搭載に際しては、双方のインデクス生成回路２２Ａ，２２Ｂで共通のインデクス生成手法を採用する必要がある。その理由は、双方のインデクス生成回路２２Ａ，２２Ｂで別々のインデクス生成手法を採用すると、スラック表２０の更新時と参照時で別々のインデクスが生成されてしまい、スラックを正しく予測できないためである。
【００８５】
図１１（ｂ）の場合には、分岐履歴のｉ個のビットとＰＣから切り出したｊ個のビットとを連結して、インデクスを生成するようにしている。一方、図１１（ｃ）の場合には、分岐履歴のｉ個のビットとＰＣから切り出した同数（ｉ個）のビットとの排他論理和（ｅｘｃｌｕｓｉｖｅ  ｏｒ）をビット毎に取るとともに、そのビット列とＰＣから更に切り出したｊ個のビットとを連結して、インデクスを生成するようにしている。
【００８６】
なお図１１（ｃ）のように、分岐履歴が単調な場合（全て成立、あるいは、全て不成立）でも、ＰＣから切り出したビットとの排他的論理和を取ることで、インデクスの上位ビットが単調とはならないようにすることができ、スラック表２０のエントリを有効に活用できるようになる。
【００８７】
例えば図１１（ｂ）及び（ｃ）に示されるように、分岐履歴を４ビットとし、ＰＣから切り出す下位ビットを２ビットとする場合で、ＰＣから切り出す下位２ビットだけが同じとなる２つの命令（命令１、命令２）のスラックを更新する場合を考えてみる。なお、以下の説明では、命令１及び命令２のＰＣのうち、インデクスの生成に関係ないビットを省略して表し、また省略しないビットのうちの上位４ビットと下位２ビットとをスペースで区切って表示する。ここで命令１のＰＣが「・・・００１１  ０１・・・」であり、命令２のＰＣが「・・・１１００  ０１・・・」であったとする。命令１と命令２の分岐履歴がいずれも全て成立（１１１１）となった場合、図１１（ｂ）の手法では、スラック表２０へのインデクスが、両命令で同じ値（１１１１  ０１）となってしまう。一方、図１１（ｃ）の手法では、スラック表２０へのインデクスは、命令１では「１１００  ０１」と、命令２では「００１１  ０１」と、この場合にも異なった値となる。
【００８８】
このように図１１（ｃ）の手法の方が、エントリを有効活用する上で有利ではあるが、余分な計算が必要されるため、スラック表への要求、すなわちスラック予測のより高い精度を所望するか、機構の簡易さを所望するかによって採用する手法を選択する。いずれにせよ、制御フローを考慮した分岐パターン別の予測スラックを個別記録を行えば、スラック予測の精度を更に向上可能となる。
【００８９】
（ターゲット・スラック到達条件の拡張）
ターゲット・スラック到達条件として使用可能な命令実行時の振る舞いとしては、上述した（Ａ）〜（Ｄ）以外にも、例えば以下に列記する（Ｅ）〜（Ｉ）が考えられる。これらの一部又は全部を、ターゲット・スラック到達条件に追加することで、スラックの予測をより正確に行える可能性がある。
（Ｅ）当該命令が、命令ウィンドウ１３（図４、図１０参照）において最も古い命令となる（当該命令が命令ウィンドウ１３内に最も長い間、留まっている）こと。
（Ｆ）リオーダ・バッファ１６（図４、図１０参照）において最も古い命令となる（当該命令がＲＯＢ内に最も長い間、留まっている）こと。
（Ｇ）当該命令が、前記命令ウィンドウに存在する命令の中で最も古い命令に実行結果を渡す命令となっていること。
（Ｈ）当該命令が、同一のサイクルに実行される命令の中で最も多くの後続命令に実行結果を渡す命令となっていること。例えば同一のサイクルに２つの命令が実行され、そのうちの一方が２つの後続命令に実行結果を渡し、残りが５つの後続命令に実行結果を渡したのであれば、後者の命令がターゲット・スラック到達条件を満たしていると判定される。
（Ｉ）当該命令の実行結果を渡すことで、実行可能な状態となる後続命令の数が、予め定められた判定値以上となっていること。ここでの実行可能な状態とは、入力データが揃い、いつでも実行を開始できる状態をいう。
【００９０】
これら（Ｅ）〜（Ｉ）について次の命令ｉ１〜ｉ６、すなわち、
・命令ｉ１：  Ａ  ＝  ５  ＋  ３  ；
・命令ｉ２：  Ｂ  ＝  ８  −  ３  ；
・命令ｉ３：  Ｃ  ＝  ３  ＋  Ａ  ；
・命令ｉ４：  Ｄ  ＝  Ａ  ＋  Ｃ  ；
・命令ｉ５：  Ｅ  ＝  ９  ＋  Ｂ  ；
・命令ｉ６：  Ｆ  ＝  ７  −  Ｂ  ；
を実行する場合を例に説明する。
【００９１】
まず最初のサイクルで命令ｉ１と命令ｉ２とが同時に実行されたとすると、命令ｉ１は命令ｉ３と命令ｉ４に実行結果を渡し、命令ｉ２は命令ｉ５と命令ｉ６に実行結果を渡す。そのため、実行結果を渡す後続命令数はどちらも２つとなるが、命令ｉ４は未だ入力データが揃っていないので、命令ｉ１の実行結果によって実行可能な状態になった命令数は１つ、命令ｉ２の実行結果によって実行可能な状態になった命令数は２つである。なお、上記条件（Ｉ）での判定値が「１」であれば、同条件（Ｉ）を満たすのは命令ｉ１と命令ｉ２、判定値が「２」であれば、命令ｉ２のみとなる。
【００９２】
これらの条件（Ｅ）〜（Ｉ）は、従来、クリティカル・パスを検出するための条件としての使用が提案されたものであるが、ローカル・スラック到達条件としても、十分に利用可能なものである。
【００９３】
（スラック表の更新に関するパラメータの拡張）
上記実施形態では、スラック表の更新に係るパラメータのうち、予測スラック及び信頼性カウンタの１回あたりの減少量Ｖｄｅｃ，Ｃｄｅｃをそれぞれ予測スラックの最大値Ｖｍａｘ及び閾値Ｃｔｈと同値に固定していた。また予測スラック及び信頼性カウンタの１回あたりの増加量Ｖｉｎｃ，Ｃｉｎｃを共に「１」に固定するようにしていた。しかしながら、性能低下を抑えることが重要な場合や、予測できるスラックの量をできるだけ大きくしたい場合など、状況に応じて上記パラメータの最適値は変わる。そのため、必ずしも上記のようにパラメータを固定する必要はなく、スラック予測の適用される分野に応じて適宜決定することが望ましい。
【００９４】
上記実施形態では、上記スラック表の更新に係る各パラメータはそれぞれ、命令の種別に依らず、一律の値とされていた。例えば、ロード命令であっても、分岐命令であっても、信頼性の閾値Ｃｔｈには同じ値が用いられている。
【００９５】
しかしながら、実際には、命令の種別によっては、動的な変化度合やその変化の頻度などのローカル・スラックの挙動に違いがある。典型的な例として分岐命令をあげることができる。分岐命令は、他の命令と比べ、ローカル・スラックの変化する量が非常に激しい。分岐予測が成功したときには、後続命令への影響は非常に小さく、ローカル・スラックは大きくなる傾向にあるが、分岐予測が失敗したときには、誤って実行してしまった命令は全て破棄され、非常に大きなペナルティを被るため、ローカル・スラックが「０」となる。これは、分岐予測の成功と失敗が入れ替わると、ローカル・スラックが急激に変化することを意味する。したがって、分岐命令の場合、信頼性カウンタの閾値Ｃｔｈや１回当たりの減少量Ｃｄｅｃは他の命令よりも大きくすることが望ましい。
【００９６】
また分岐命令以外の種別に属する命令においても、プロセッサ内での動作に特徴があれば、その特徴に適したパラメータの適正値が種別毎にそれぞれ存在すると考えられる。そこで、命令をいくつかのカテゴリにわけ、カテゴリ毎にスラック表の更新に係るパラメータを個別に設定することで、予測精度が更に向上する可能性がある。例えば、プロセッサ内での動作の違いに着目すると、命令を次の４つのカテゴリ、すなわちロード命令のカテゴリ、ストア命令のカテゴリ、分岐命令のカテゴリ、及びその他命令のカテゴリ、に分類することができる。
【００９７】
こうして分類した命令の各カテゴリについて、それぞれパラメータを個別に設定する。更新時にはまず、その命令がどのカテゴリに属するかを判定する。この判定は、命令のオペコードを見れば容易に行うことができる。そして、その命令が属するカテゴリの固有のパラメータを用いて、スラック表を更新する。なお、命令のカテゴリの分類態様としては、ロード命令とストア命令とを同じカテゴリとしたり、加算と減算を別々のカテゴリに分けるようにしたり、といった態様も考えられる。命令のどの様に分類するかは、スラック予測の適用される範囲によって変わってくる。なお、このように命令の種別毎に個別のパラメータを使用することとすると、ローカル・スラック予測機構の構成が複雑化するため、これを抑えるには、カテゴリの数を必要最小限まで減らす必要がある。
【図面の簡単な説明】
【００９８】
【図１】（ａ）〜（ｃ）本発明の一実施形態に係るローカル・スラックの予測方法の基本動作を説明するためのタイミングチャート。
【図２】（ａ）上記基本動作及び（ｂ）その基本動作に予測スラックを減少させる改良動作を加えた場合のそれぞれにおけるローカル・スラックの動的減少に対する予測スラックの推移を各示すグラフ。
【図３】（ａ）信頼性の導入前と（ｂ）導入後のそれぞれにおけるローカル・スラックの増減の繰り返しに対する予測スラックの推移をそれぞれ示すグラフ。
【図４】本発明の一実施形態に係るローカル・スラック予測機構の構成を模式的に示すブロック図。
【図５】同予測機構の評価におけるスラック命令数とＩＰＣの測定結果を示すグラフ。
【図６】上記測定結果での予測スラックとＩＰＣとの関係を示すグラフ。
【図７】上記予測機構の予測結果を利用して機能ユニットの消費電力を削減可能に構成したプロセッサの構成を模式的に示すブロック図。
【図８】同プロセッサの各モデルにおける各ベンチマークのＩＰＣの測定結果を示すグラフ。
【図９】同プロセッサの各モデルにおける各ベンチマークのＥＤＰの測定結果を示すグラフ。
【図１０】制御フローを考慮したスラック予測を行うローカル・スラック予測機構の構成を模式的に示すブロック図。
【図１１】（ａ）制御フローを考慮せずにスラック予測を行う予測機構及び（ｂ）（ｃ）制御フローを考慮したスラック予測を行う予測機構のそれぞれにおけるスラック表のインデクス生成動作を模式的に示すブロック図。
【図１２】（ａ）ローカル・スラックの説明に用いるプログラムの命令の一覧、及び（ｂ）その実行態様を示すタイミングチャートを併せ示す図。
【図１３】従来のローカル・スラック予測機構の構成を模式的に示すブロック図。
【符号の説明】
【００９９】
１０…プロセッサ、１１…フェッチ・ユニット、１２…デコード・ユニット、１３…命令ウィンドウ、１４…レジスタ・ファイル、１５，１５Ａ，１５Ｂ…実行ユニット、１６…リオーダ・バッファ、２０，５３…スラック表、２１Ａ，２１Ｂ…分岐履歴レジスタ、２２Ａ，２２Ｂ…インデクス生成回路、５１…レジスタ定義表、５２…メモリ定義表、５４…演算器。
【図１】
2007249710.tif 000004
【図２】
2007249710.tif 000005
【図３】
2007249710.tif 000006
【図４】
2007249710.tif 000007
【図５】
2007249710.tif 000008
【図６】
2007249710.tif 000009
【図７】
2007249710.tif 000010
【図８】
2007249710.tif 000011
【図９】
2007249710.tif 000012
【図１０】
2007249710.tif 000013
【図１１】
2007249710.tif 000014
【図１２】
2007249710.tif 000015
【図１３】
2007249710.tif 000016