(57)【要約】【課題】    実行された命令の履歴を管理して行われるホットパス検出処理等に適合する推定装置等を提供する。【解決手段】    ホットパス推定装置１は、分岐命令を特定する分岐命令特定情報、実行された各分岐命令の分岐先アドレス、分岐回数及び実行頻度情報を１つのエントリとし、各分岐命令特定情報には定められた数のエントリが対応するテーブルと、実行された分岐命令に関する情報がテーブルに格納されていないならば、新たなエントリをテーブルに追加するか、テーブルのエントリの一つを置き換えるか、実行された分岐命令に関する情報をテーブルに格納しないかを選択して処理する履歴管理部１１と、テーブルに基づいてホットパス検索部１３により検索された命令パスが既に検出されたものではないときこの命令パスを外部に出力するホットパスクオリファイ部７と、を備える。【選択図】  図１
2007109116.tif 000002
【特許請求の範囲】
【請求項１】
複数の分岐命令を含む命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、
分岐命令を特定する分岐命令特定情報、実行された各分岐命令の分岐先アドレス、分岐回数及び実行頻度情報を１つのエントリとするテーブルであって、前記各分岐命令特定情報には定められた数のエントリが対応するテーブルと、
分岐命令が実行されると、実行された分岐命令の分岐命令特定情報及び実行された分岐命令の分岐先アドレスが前記分岐命令特定情報に対応するエントリに格納されているか否かを判断して格納されていないならば、前記分岐命令特定情報に対応する各エントリの実行頻度情報に基づいて、前記分岐命令特定情報及び前記分岐先アドレスに関するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記分岐命令特定情報及び前記分岐先アドレスに関するエントリに置き換えるか、又は、前記分岐命令特定情報及び前記分岐先アドレスに関する情報をテーブルに格納しないかを選択して処理する履歴管理手段と、
前記テーブルに格納された情報に基づいて命令パスを検索する検索手段と、
前記検索手段により検索された命令パスが既に検出されたものか否かを判断して既に検出されたものではないときに当該命令パスを外部に出力するクオリファイ手段と、を備える推定装置。
【請求項２】
実行される命令パスの基本ブロックに対して実行された各実行基本ブロック及び前記各実行基本ブロックの次に実行される次基本ブロックに関連する情報である基本ブロック実行順序関連情報を１つのエントリとするテーブルを管理するテーブル管理装置において、
前記テーブルのエントリ数は予め定められた数以下であり、
基本ブロックが実行されると、実行された実行基本ブロック及び前記実行基本ブロックの次に実行される次基本ブロックに関連するエントリが前記テーブルに登録されているか否かを判断して、登録されていないならば、前記テーブルに格納されている情報に基づいて、前記実行基本ブロック及び前記次基本ブロックに関連するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記実行基本ブロック及び前記次基本ブロックに関連するエントリで置き換えるか、又は、前記実行基本ブロック及び前記次基本ブロックに関連する情報を前記テーブルに格納しないかのいずれかを選択して処理を行う履歴管理手段を備えるテーブル管理装置。
【請求項３】
前記基本ブロック実行順序関連情報には実行基本ブロック及び次基本ブロックの実行頻度を示す実行頻度情報が含まれており、
前記履歴管理手段は基本ブロックが実行されると前記テーブルに格納されている実行頻度情報に基づいて処理の選択を行う請求項２記載のテーブル管理装置。
【請求項４】
前記テーブルは、基本ブロック実行順序関連情報を１つのエントリとし、同じインデックスアドレスが与えられた複数のサブテーブルを含み、
前記履歴管理手段は実行基本ブロックを特定する情報に基づいて生成されるインデックスアドレスを用いて前記サブテーブルのエントリにアクセスする、請求項２又は３記載のテーブル管理装置。
【請求項５】
複数の分岐命令を含む命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、
実行された各分岐命令の分岐先アドレス及び前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレス並びに分岐回数及び実行頻度情報を１つのエントリとして格納する複数セットの分岐履歴テーブルであって、同一のインデックスアドレスによりアクセス可能な複数セットの分岐履歴テーブルと、
分岐命令が実行されると、前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレスに基づいて生成されるインデックスアドレスにより前記各分岐履歴テーブルのエントリを読み出し、読み出したエントリが実行された分岐命令の分岐先アドレス及び前記基本ブロック開始アドレスに関連するものであるかの判断をし、いずれかのエントリが関連するならば当該エントリの分岐回数及び実行頻度情報を更新し、いずれのエントリも関連しないならば読み出したエントリの実行頻度情報に基づいてエントリの更新処理を行う分岐履歴管理手段と、
実行された各分岐命令の分岐先アドレス並びに分岐回数及び実行頻度情報を１つのエントリとして格納する複数セットの戻り分岐履歴テーブルであって、同一のインデックスアドレスによりアクセス可能な複数セットの戻り分岐履歴テーブルと、
分岐命令が実行されると、実行された前記分岐命令の分岐先アドレスが前記分岐命令のアドレスよりも小さい場合に、前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレスに基づいて生成されるインデックスアドレスにより前記各戻り分岐履歴テーブルのエントリを読み出し、読み出したエントリが前記分岐先アドレスに関連するものであるかの判断をし、いずれかのエントリが関連するならば当該エントリの分岐回数及び実行頻度情報を更新する処理及び分岐回数が閾値よりも大きいならばパス検索処理の開始を指示する処理を行い、いずれのエントリも関連しないならば読み出したエントリの実行頻度情報に基づいてエントリの更新処理を行う戻り分岐履歴管理手段と、
前記戻り分岐履歴管理手段によりパス検索処理の開始が指示されたならば前記分岐履歴テーブルに格納された情報に基づいて命令パスを検索する検索手段と、
を備えた推定装置。
【請求項６】
検索手段により検索された命令パスを選択して出力する選択装置であって、
検索手段により検索された命令パスを示すパス特定情報を記憶する記憶手段と、
検索手段により命令パスが検索されると、検索された命令パスを特定するパス特定情報と前記記憶手段に記憶されたパス特定情報とを比較する比較手段と、
前記比較手段の比較結果に基づいて前記検索手段により検索された命令パスを外部に出力する出力手段とを備え、
前記検索された命令パスを示すパス特定情報が前記記憶手段に記憶されていないならば前記比較手段は当該パス特定情報を前記記憶手段に記憶させて前記出力手段は前記検索手段により検索された命令パスを外部に出力し、前記検索された命令パスを示すパス特定情報が前記記憶手段に記憶されているならば前記比較手段は当該パス特定情報を前記記憶手段に記憶せず前記出力手段は前記検索手段により検索された命令パスを外部に出力しない、選択装置。
【請求項７】
前記命令パスは分岐命令を含み、
前記パス特定情報は命令パスの分岐命令が分岐する場合と分岐しない場合を区別する情報を含む、請求項６記載の選択装置。
【請求項８】
実行される命令パスの基本ブロックに対して実行された各実行基本ブロック及び前記各実行基本ブロックの次に実行される次基本ブロックに関連する情報である基本ブロック実行順序関連情報を１つのエントリとするテーブルを管理するテーブル管理方法において、
前記テーブルのエントリ数は予め定められた数以下であり、
基本ブロックが実行されると、履歴管理手段が、実行された実行基本ブロック及び前記実行基本ブロックの次に実行される次基本ブロックに関連するエントリが前記テーブルに登録されているか否かを判断して、登録されていないならば、前記テーブルに格納されている情報に基づいて、前記実行基本ブロック及び前記次基本ブロックに関連するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記実行基本ブロック及び前記次基本ブロックに関連するエントリで置き換えるか、又は、前記実行基本ブロック及び前記次基本ブロックに関連する情報を前記テーブルに格納しないかのいずれかを選択して処理を行う履歴管理ステップを含むテーブル管理方法。
【請求項９】
請求項８記載のテーブル管理方法をコンピュータに実行させることが可能なプログラム。
【請求項１０】
請求項９記載のプログラムをコンピュータが実行することが可能にて記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推定装置、テーブル管理装置、選択装置、テーブル管理方法、そのテーブル管理方法をコンピュータに実現させるプログラム、及び、そのプログラムを記録する記憶媒体に関し、特に、複数の分岐命令を含む命令パスのうち実行される頻度が高い命令パスを推定する推定装置等に関する。
【背景技術】
【０００２】
プログラムの実行中に実行頻度の高いループ構造のパス（以下では、「ホットパス」という）を高精度で推定する装置として、例えば特許文献１に記載されたものが知られている。図１３〜図１５を参照して、特許文献１に記載された推定装置の概要を説明する。
【０００３】
図１３は、特許文献１に記載されたホットパス推定装置１０１の概略ブロック図である。ホットパス推定装置１０１は、ハードウェアアシスト部（ＨＷアシスト部）１０５とソフトウェアプロファイラ部（ＳＷプロファイラ部）１０７とバッファ１０９を備える。
【０００４】
ＨＷアシスト部１０５は、テーブルを管理し、ＣＰＵ１０３により分岐命令が実行された場合にテーブルに新たに分岐命令に関するアドレス情報を追加したり分岐命令の実行回数をカウントしたりする。また、テーブルやカウンタがオーバフローした場合には、ＣＰＵ１０３に通知し、ＣＰＵ１０３は、テーブルのバッファ１０９への吐き出し処理を行う。
【０００５】
ＳＷプロファイラ部１０７は、バッファ１０９とテーブルの合算処理を行い、ＢＨ法に基づいて高い頻度で繰り返し実行される命令列（ホットパス）を推定する。このＢＨ法は、分岐命令の実行で、分岐命令のアドレス、分岐先のアドレス、分岐した（あるいは分岐しなかった）回数などの履歴に基づきホットパスの推定を行う手法である。
【０００６】
図１４は、プロセッサコアで実行される基本ブロックの関係と分岐命令の実行回数の一例を示す図である。プログラムを構成する命令列は、プログラム実行の流れを変える分岐命令とその他の命令で構成されている。そして、プログラムは、アドレス順に見て、分岐命令以外の命令と最後の分岐命令で構成されるブロックに区分でき、このブロックは基本ブロックと呼ばれる。図１４において記号Ａ〜Ｇは基本ブロックを示し、数値は分岐命令の分岐回数を示す。図１４の基本ブロックの関係では、基本ブロックＡ、Ｂ、Ｃ、Ｆのループ構造のパスがホットパスとして検出される。
【０００７】
図１５は、基本ブロックが図１４に示される関係にある場合に、図１３のＨＷアシスト部１０５により管理されるテーブルの一例を示す図である。図１５において、ＢＳＡは基本ブロックの開始アドレスである基本ブロック開始アドレスであり、ＢＩＡは分岐命令のアドレスである分岐命令アドレスであり、ＢＴＡは分岐先のアドレスである分岐先アドレスであり、ＣＯＵＮＴは分岐命令の実行回数である。図１３のＳＷプロファイラ部１０７は、図１５に示されるテーブルとバッファ１０９に基づいてホットパスの推定処理を行う。
【０００８】
【特許文献１】特開２００５−９２５３２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、特許文献１に記載されたホットパス推定装置は、テーブルやカウントのオーバフローによりテーブルに格納された情報をバッファ１０９に退避する。そのため、大きな容量のバッファが必要であり、さらに、ＣＰＵ１０３がバッファ１０９への退避処理を行うためにＣＰＵ１０３における処理が中断されることとなる。
【００１０】
また、テーブルの情報はバッファ１０９に退避されるため、同じ分岐命令に関する情報でも、退避前の情報はバッファ１０９で、退避後の情報はテーブルで別々に管理されていたり、退避が複数回行われていればバッファ１０９内の複数の箇所に記憶されている可能性がある。そのため、ＳＷプロファイラ部１０７によりホットパス推定処理が行われる際には、テーブルとバッファ１０９に退避された情報との合算処理が必要であった。
【００１１】
さらに、ＳＷプロファイラ部１０７による処理は複雑なためにハードウェアによる実現は困難であり、ソフトウェアにより実現されていた。この処理はＣＰＵ１０３により実行されることもあり、このような場合には、テーブル合算処理やホットパス推定処理のためにもＣＰＵの処理が中断されることとなる。
【００１２】
さらに、ホットパス推定装置１０１は検出されたホットパスを記憶するが、同じホットパスでも重複して検出されると重複して記憶しており、検出されたホットパスを記憶する記憶領域も膨大に必要であった。
【００１３】
なお、このような課題は、ホットパス推定処理に限らず、他の実行された命令の履歴を管理して行われる処理に関しても存在するものである。
【００１４】
そこで、本発明の目的は、実行された命令の履歴を管理して行われる処理の簡素化に適合する推定装置、テーブル管理装置、選択装置、テーブル管理方法、そのテーブル管理方法をコンピュータに実現させるプログラム、そのプログラムを記録する記憶媒体を提供することにある。
【課題を解決するための手段】
【００１５】
請求項１に係る発明は、複数の分岐命令を含む命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、分岐命令を特定する分岐命令特定情報、実行された各分岐命令の分岐先アドレス、分岐回数及び実行頻度情報を１つのエントリとするテーブルであって、前記各分岐命令特定情報には定められた数のエントリが対応するテーブルと、分岐命令が実行されると、実行された分岐命令の分岐命令特定情報及び実行された分岐命令の分岐先アドレスが前記分岐命令特定情報に対応するエントリに格納されているか否かを判断して格納されていないならば、前記分岐命令特定情報に対応する各エントリの実行頻度情報に基づいて、前記分岐命令特定情報及び前記分岐先アドレスに関するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記分岐命令特定情報及び前記分岐先アドレスに関するエントリに置き換えるか、又は、前記分岐命令特定情報及び前記分岐先アドレスに関する情報をテーブルに格納しないかを選択して処理する履歴管理手段と、前記テーブルに格納された情報に基づいて命令パスを検索する検索手段と、前記検索手段により検索された命令パスが既に検出されたものか否かを判断して既に検出されたものではないときに当該命令パスを外部に出力するクオリファイ手段と、を備えるものである。
【００１６】
請求項２に係る発明は、実行される命令パスの基本ブロックに対して実行された各実行基本ブロック及び前記各実行基本ブロックの次に実行される次基本ブロックに関連する情報である基本ブロック実行順序関連情報を１つのエントリとするテーブルを管理するテーブル管理装置において、前記テーブルのエントリ数は予め定められた数以下であり、基本ブロックが実行されると、実行された実行基本ブロック及び前記実行基本ブロックの次に実行される次基本ブロックに関連するエントリが前記テーブルに登録されているか否かを判断して、登録されていないならば、前記テーブルに格納されている情報に基づいて、前記実行基本ブロック及び前記次基本ブロックに関連するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記実行基本ブロック及び前記次基本ブロックに関連するエントリで置き換えるか、又は、前記実行基本ブロック及び前記次基本ブロックに関連する情報を前記テーブルに格納しないかのいずれかを選択して処理を行う履歴管理手段を備えるものである。
【００１７】
なお、請求項２に係る発明であって、基本ブロック実行順序関連情報は、実行基本ブロックの開始アドレス及び次基本ブロックの開始アドレスを含むものであってもよい。また、基本ブロック実行順序関連情報は次基本ブロックの開始アドレスを含み、基本ブロック実行順序関連情報のエントリは実行基本ブロックの開始アドレスに基づいて生成されるインデックスアドレスによりアクセスされるものであってもよい。
【００１８】
請求項３に係る発明は、請求項２記載のテーブル管理装置であって、前記基本ブロック実行順序関連情報には実行基本ブロック及び次基本ブロックの実行頻度を示す実行頻度情報が含まれており、前記履歴管理手段は基本ブロックが実行されると前記テーブルに格納されている実行頻度情報に基づいて処理の選択を行うものである。
【００１９】
請求項４に係る発明は、請求項２又は３記載のテーブル管理装置であって、前記テーブルは、基本ブロック実行順序関連情報を１つのエントリとし、同じインデックスアドレスが与えられた複数のサブテーブルを含み、前記履歴管理手段は実行基本ブロックを特定する情報に基づいて生成されるインデックスアドレスを用いて前記サブテーブルのエントリにアクセスするものである。
【００２０】
請求項５に係る発明は、複数の分岐命令を含む命令パスのうち実行される頻度が高い命令パスを推定する推定装置において、実行された各分岐命令の分岐先アドレス及び前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレス並びに分岐回数及び実行頻度情報を１つのエントリとして格納する複数セットの分岐履歴テーブルであって、同一のインデックスアドレスによりアクセス可能な複数セットの分岐履歴テーブルと、分岐命令が実行されると、前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレスに基づいて生成されるインデックスアドレスにより前記各分岐履歴テーブルのエントリを読み出し、読み出したエントリが実行された分岐命令の分岐先アドレス及び前記基本ブロック開始アドレスに関連するものであるかの判断をし、いずれかのエントリが関連するならば当該エントリの分岐回数及び実行頻度情報を更新し、いずれのエントリも関連しないならば読み出したエントリの実行頻度情報に基づいてエントリの更新処理を行う分岐履歴管理手段と、実行された各分岐命令の分岐先アドレス並びに分岐回数及び実行頻度情報を１つのエントリとして格納する複数セットの戻り分岐履歴テーブルであって、同一のインデックスアドレスによりアクセス可能な複数セットの戻り分岐履歴テーブルと、分岐命令が実行されると、実行された前記分岐命令の分岐先アドレスが前記分岐命令のアドレスよりも小さい場合に、前回に実行された分岐命令の分岐先アドレスである基本ブロック開始アドレスに基づいて生成されるインデックスアドレスにより前記各戻り分岐履歴テーブルのエントリを読み出し、読み出したエントリが前記分岐先アドレスに関連するものであるかの判断をし、いずれかのエントリが関連するならば当該エントリの分岐回数及び実行頻度情報を更新する処理及び分岐回数が閾値よりも大きいならばパス検索処理の開始を指示する処理を行い、いずれのエントリも関連しないならば読み出したエントリの実行頻度情報に基づいてエントリの更新処理を行う戻り分岐履歴管理手段と、前記戻り分岐履歴管理手段によりパス検索処理の開始が指示されたならば前記分岐履歴テーブルに格納された情報に基づいて命令パスを検索する検索手段と、を備えたものである。
【００２１】
請求項６に係る発明は、検索手段により検索された命令パスを選択して出力する選択装置であって、検索手段により検索された命令パスを示すパス特定情報を記憶する記憶手段と、検索手段により命令パスが検索されると、検索された命令パスを特定するパス特定情報と前記記憶手段に記憶されたパス特定情報とを比較する比較手段と、前記比較手段の比較結果に基づいて前記検索手段により検索された命令パスを外部に出力する出力手段とを備え、前記検索された命令パスを示すパス特定情報が前記記憶手段に記憶されていないならば前記比較手段は当該パス特定情報を前記記憶手段に記憶させて前記出力手段は前記検索手段により検索された命令パスを外部に出力し、前記検索された命令パスを示すパス特定情報が前記記憶手段に記憶されているならば前記比較手段は当該パス特定情報を前記記憶手段に記憶せず前記出力手段は前記検索手段により検索された命令パスを外部に出力しないものである。
【００２２】
請求項７に係る発明は、請求項６記載の選択装置であって、前記命令パスは分岐命令を含み、前記パス特定情報は命令パスの分岐命令が分岐する場合と分岐しない場合を区別する情報を含むものである。
【００２３】
請求項８に係る発明は、実行される命令パスの基本ブロックに対して実行された各実行基本ブロック及び前記各実行基本ブロックの次に実行される次基本ブロックに関連する情報である基本ブロック実行順序関連情報を１つのエントリとするテーブルを管理するテーブル管理方法において、前記テーブルのエントリ数は予め定められた数以下であり、基本ブロックが実行されると、履歴管理手段が、実行された実行基本ブロック及び前記実行基本ブロックの次に実行される次基本ブロックに関連するエントリが前記テーブルに登録されているか否かを判断して、登録されていないならば、前記テーブルに格納されている情報に基づいて、前記実行基本ブロック及び前記次基本ブロックに関連するエントリを前記テーブルに追加するか、前記テーブルのエントリの一つを前記実行基本ブロック及び前記次基本ブロックに関連するエントリで置き換えるか、又は、前記実行基本ブロック及び前記次基本ブロックに関連する情報を前記テーブルに格納しないかのいずれかを選択して処理を行う履歴管理ステップを含むものである。
【００２４】
請求項９に係る発明は、請求項８記載のテーブル管理方法をコンピュータに実行させることが可能なプログラムである。
【００２５】
請求項１０に係る発明は、請求項９記載のプログラムをコンピュータが実行することが可能にて記録した記録媒体である。
【発明の効果】
【００２６】
本願の各請求項に係る発明によれば、処理に用いられる情報が重要と判断されるものに制限されており、実行された命令の履歴を管理して行われる処理の簡素化に適合する。
【００２７】
また、本願の請求項１乃至５並びに請求項８乃至１０に係る発明によれば、テーブルに格納される情報が限られていてバッファへの退避処理が必要でなく、合算処理も必要ではない。そのため、ＣＰＵとは別のハードウェアによる実現が容易となり、ＣＰＵの処理が中断されなくなる。
【００２８】
さらに、本願の請求項１、３、４及び５に係る発明によれば、更新頻度情報を用いてテーブル管理を行うため、重要性の高い情報がテーブルに格納され、テーブルを用いた処理の正確性の向上に適合する。
【００２９】
さらに、本願の請求項１及び４に係る発明によれば、複数のテーブルを用いて処理を行うことにより、例えば各テーブルに対する処理を並列して処理する等により処理時間を短縮することが可能となる。
【００３０】
さらに、本願の請求項１、６及び７に係る発明によれば、検出された命令パスのうち重複して検出されたものを除いて外部に出力するため、転送に関するオーバヘッドが削減され、記憶する記憶領域が削減される。
【発明を実施するための最良の形態】
【００３１】
図１は、本発明の実施の形態に係るホットパス推定装置１の概略ブロック図である。
【００３２】
図１を参照して、ホットパス推定装置１は、ホットパス検出部５とホットパスクオリファイ部７を備える。ホットパス検出部５は、分岐命令選択部９と履歴管理部１１とホットパス検索部１３を有する。履歴管理部１１は、分岐履歴管理部１５と戻り分岐履歴管理部１７を有する。
【００３３】
分岐命令選択部９は、ＣＰＵ３により実行される命令のうち分岐命令を選択し、分岐命令のアドレスである分岐命令アドレス（ＢＩＡ）及び分岐先のアドレスである分岐先アドレス（ＢＴＡ）を取得するものである。
【００３４】
分岐履歴管理部１５は、分岐命令選択部９により取得されたＢＩＡ及びＢＴＡ並びに前回の分岐先アドレスを基本ブロック開始アドレス（ＢＳＡ）として、図２に例示される分岐履歴テーブルを用いて分岐命令の分岐履歴情報の管理を行うものである。
【００３５】
戻り分岐履歴管理部１７は、図５に例示される戻り分岐履歴テーブルを用いて、分岐命令選択部９により取得されたＢＴＡがＢＩＡよりも小さい場合の分岐回数（ＣＯＵＮＴ）等を管理するものである。
【００３６】
ホットパス検索部１３は、図２に例示される分岐履歴テーブルを用いて命令パスを検索するものである。
【００３７】
ホットパスクオリファイ部７は、ホットパス検索部１３により検索されたホットパス情報が重複して検出されたものか否かを判断して、重複して検出されたものでない場合にホットパス情報を外部に出力するものである。
【００３８】
続いて、図２〜図４を参照して、図１の分岐履歴管理部１５について説明する。
【００３９】
図２は、図１の分岐履歴管理部１５により管理される分岐履歴テーブルの一例を示す図である。図２の分岐履歴テーブルの例は、２ｎ個のインデックスアドレスにより、基本ブロック開始アドレス（ＢＳＡ）、分岐命令アドレス（ＢＩＡ）、分岐先アドレス（ＢＴＡ）、分岐回数（ＣＯＵＮＴ）及びミスカウント値（Ｍｉｓｓ  ＣＯＵＮＴ）を１つのエントリとするものである。
【００４０】
続いて、図３と図４を用いて、図１の分岐履歴管理部１５が図２の分岐履歴テーブルを用いて行う分岐履歴管理の例を説明する。
【００４１】
図３は、図１の分岐履歴管理部１５が、図２の分岐履歴テーブルを２セット用いて行う分岐履歴管理の一例の概略を示す図である。図３を参照して、図１の分岐履歴管理部１５が、図２の分岐履歴テーブルを２セット用いて行う分岐履歴管理の一例を説明する。以下では、２セットのテーブルをそれぞれセット０とセット１という。
【００４２】
図３を参照して、図１の分岐履歴管理部１５は、前回のＢＴＡをＢＳＡとし、このＢＳＡ並びに図１の分岐命令選択部９により得られたＢＩＡ及びＢＴＡにより、ＢＳＡとＢＩＡとＢＴＡの組である分岐情報３１を生成する。
【００４３】
次に、図１の分岐履歴管理部１５は、ＢＳＡの下位ｎビットを用いてセット０の分岐履歴テーブル３５をアクセスしてＢＳＡとＢＩＡとＢＴＡの組である分岐情報３３を取得し、同様にセット１の分岐履歴テーブル３９をアクセスしてＢＳＡとＢＩＡとＢＴＡの組である分岐情報３７を取得する。
【００４４】
次に、図１の分岐履歴管理部１５は、分岐情報３１と分岐情報３３及び分岐情報３７とを比較して、分岐情報３１が分岐情報３３と分岐情報３７の一方と一致するならば、一致する分岐情報に対応する分岐回数（ＣＯＵＮＴ）を１増加してミスカウント値を新しい分岐回数から計算された値とする。分岐情報３１が分岐情報３３とも分岐情報３７とも一致しない場合には、対応するミスカウント値が０か否かを判断し、ミスカウント値が０のものがあれば分岐履歴テーブルの対応する行を新しいＢＳＡとＢＩＡとＢＴＡで置き換えてカウント値を０としてミスカウント値を更新し、他のミスカウント値を１減少する。（ミスカウント値が０のものが複数ある場合には、いずれのテーブルも更新可能であり、例えば、一方のテーブルを更新して、他方のテーブルは更新しないとする。）ミスカウント値が０のものがなければ、分岐履歴テーブルのそれぞれで対応するミスカウント値を１減少する。（分岐情報３１は分岐履歴テーブル３５にも分岐履歴テーブル３７にも格納されない。）
【００４５】
以上にあるようにして、図１の分岐履歴管理部１５は、分岐履歴テーブルを２セット用いた場合の分岐履歴の管理を行う。図３の例では、ＢＳＡ（基本ブロック開始アドレス）の下位ｎビットによりインデックスアドレスを生成しており、異なる基本ブロックの開始アドレスが同一のインデックスアドレスに対応する可能性がある。図３の例によれば、同一のインデックスアドレスに対応する分岐命令の分岐先の情報に関して、より頻繁になされる２つのものが、２セットのテーブルの対応するインデックスアドレスにより管理されることが期待される。
【００４６】
続いて、図４を参照して、図１の分岐履歴管理部１５が図２のテーブルを複数用いて行う分岐履歴管理の動作を説明する。図４は、図１の分岐履歴管理部１５が、図２の分岐履歴テーブルを複数セット用いて行う分岐履歴管理の一例を示すフロー図である。
【００４７】
図４を参照して、図１の分岐履歴管理部１５は、図１の分岐命令選択部９により得られたＢＩＡ及びＢＴＡを取得し（図４のステップＳＴＬ１）、図１の分岐履歴管理部１５は、前回のＢＴＡをＢＳＡとし、ＢＳＡとＢＩＡとＢＴＡの分岐情報を生成する（図４のステップＳＴＬ２）。次に、図１の分岐履歴管理部１５は、ＢＳＡに基づくインデックスアドレスにより、分岐履歴テーブルの全セットからＢＳＡとＢＩＡとＢＴＡの分岐情報を読み出す（図４のステップＳＴＬ３）
【００４８】
次に、図４のステップＳＴＬ２で生成されたＢＳＡとＢＩＡとＢＴＡの分岐情報と図４のステップＳＴＬ３で読み出されたＢＳＡとＢＩＡとＢＴＡの分岐情報を比較して（図４のステップＳＴＬ４）、一致するものがあるかどうかの判断を行う（図４のステップＳＴＬ５）。一致するものがあれば、対応する分岐履歴テーブルのカウント値を１増加して対応する分岐履歴テーブルのミスカウント値を新しいカウント値から計算された値に更新して（図４のステップＳＴＬ６）、図４の処理を終了する。一致するものがなければ、ミスカウント値が０のものがあるか否かの判断を行う（図４のステップＳＴＬ７）。ミスカウント値が０のものがあればそれを新しいＢＳＡとＢＩＡとＢＴＡで置き換え、カウント値を１とし、ミスカウント値を更新して（図４のステップＳＴＬ８）、図４の処理を終了する（ミスカウント値が０のものが複数ある場合には、例えば、１つのテーブルを更新し、他のテーブルを更新しない。）。ミスカウント値が０のものがない（すなわち、ミスカウント値が全て正の整数である）ならば、ミスカウント値を１減少して（図４のステップＳＴＬ９）、図４の処理を終了する。
【００４９】
以上にあるようにして、図１の分岐履歴管理部１５は、分岐履歴テーブルを複数用いた場合の分岐履歴の管理を行い、図３の例と同様に、分岐履歴テーブルの同一のインデックスアドレスに対応する分岐命令に関して、より頻繁になされる分岐先の情報が管理されることが期待される。
【００５０】
続いて、図５と図６を参照して、図１の戻り分岐履歴管理部１７について説明する。
【００５１】
図５は、図１の戻り分岐履歴管理部１７により管理される分岐履歴テーブルの一例を示す図である。図５の戻り分岐履歴テーブルの例は、２ｍ個のインデックスアドレスにより、分岐先アドレス（ＢＴＡ）、分岐回数（ＣＯＵＮＴ）及びミスカウント値（Ｍｉｓｓ  ＣＯＵＮＴ）を１つのエントリとするものである。
【００５２】
続いて、図６を参照して、図１の戻り分岐履歴管理部１７が図５のテーブルを複数用いて行う戻り分岐履歴管理の動作を説明する。図６は、図１の戻り分岐履歴管理部１７が、図５の戻り分岐履歴テーブルを複数セット用いて行う分岐履歴管理の一例を示すフロー図である。
【００５３】
図６を参照して、図１の戻り分岐履歴管理部１７は、図１の分岐命令選択部９により得られたＢＩＡ及びＢＴＡを取得する（図６のステップＳＴＲ１）。
【００５４】
次に、図１の戻り分岐履歴管理部１７は、ＢＴＡとＢＩＡを比較して、ＢＴＡがＢＩＡよりも小さい場合（分岐先の基本ブロックが以前に処理をしたものである可能性がある場合）には図６のステップＳＴＲ３の処理を行い、そうでない場合には図６のステップＳＴＲ１の処理に戻る（図６のステップＳＴＲ２）。
【００５５】
図６のステップＳＴＲ３において、図１の戻り分岐履歴管理部１７は、前回のＢＴＡをＢＳＡとし、ＢＳＡに基づくインデックスアドレスにより戻り分岐履歴テーブルの全セットからＢＳＡを読み出す。
【００５６】
次に、図１の戻り分岐履歴管理部１７は、図６のステップＳＴＲ１において得られたＢＴＡと図６のステップＳＴＲ３において読み出されたＢＴＡを比較し（図６のステップＳＴＲ４）、一致するものがあるか否かの判断を行う（図６のステップＳＴＲ５）。一致するものがあれば図６のステップＳＴＲ６の処理を行い、一致するものがなければ図６のステップＳＴＲ７以下の処理を行う。
【００５７】
図６のステップＳＴＲ６において、図１の戻り分岐履歴管理部１７は、対応する戻り分岐履歴テーブルのカウント値を１増加し、カウント値が閾値よりも大きな値の場合には図１のホットパス検索部１３によるホットパス検索処理を開始させてカウント値を０に初期化し、対応する戻り分岐履歴テーブルのミスカウント値を更新する。そして、図６の処理を終了する。
【００５８】
図６のステップＳＴＲ７において、図１の戻り分岐履歴管理部１７は、ミスカウント値が０のものがあるか否かの判断を行う。０のものがあれば新しいＢＴＡで置き換えてカウント値を１としてミスカウント値の更新を行い（図６のステップＳＴＲ８）、図６の処理を終了する。０のものがなければミスカウント値を１引き（図６のステップＳＴＲ９）、図６の処理を終了する。
【００５９】
続いて、図７を参照して、図１のホットパス検索部１３の処理を説明する。図７は、図１のホットパス検索部１３の動作の一例を示すフロー図である。
【００６０】
図７を参照して、図１のホットパス検索部１３は、ホットパス開始アドレスにＢＴＡの値を登録し（図７のステップＳＴＳ１）、ＢＴＡを基にインデックスアドレスを生成して分岐履歴テーブルを読み出す（図７のステップＳＴＳ２）。
【００６１】
図１のホットパス検索部１３は、ＢＴＡと読み出したＢＳＡを比較する（図７のステップＳＴＳ３）。図１のホットパス検索部１３は、一致するものがあれば図７のステップＳＴＳ５以降の処理を行い、一致するものがなければ検索を終了する。
【００６２】
図７のステップＳＴＳ５において、ＢＳＡが複数のセットで一致するか否かの判断を行い、複数のセットで一致するならばカウント値を比較して大きなカウント値に対応するＢＳＡを次の分岐先として選択して（図７のステップＳＴＳ６）、図７のステップＳＴＳ７の処理を行う。複数のセットで一致していない場合には、図７のステップＳＴＳ７の処理を行う。
【００６３】
図７のステップＳＴＳ７において、図１のホットパス検索部１３は、分岐の深さが最大値を超えていないかの判断を行う。ここで、ホットパスはホットパスを構成する分岐命令における分岐先アドレスにより表すことができ、この分岐命令の数がホットパスにおける分岐の深さと呼ばれる。図１のホットパス検索部１３は、分岐の深さが最大値を超えているならば検索を終了し、そうでなければ図７のステップＳＴＳ８の処理を行う。
【００６４】
図７のステップＳＴＳ８において、図１のホットパス検索部１３は、図７のステップＳＴＳ２において読み出された分岐先アドレスＢＴＡがホットパス開始アドレスと一致するか否かの判断を行い（図７のステップＳＴＳ８）、一致しないならば図７のステップＳＴＳ２の処理に戻り、一致するならばホットパスとして図１のホットパスクオリファイ部７に出力して（図７のステップＳＴＳ９）、図７の処理を終了する。
【００６５】
続いて、図８〜図１２を参照して、図１のホットパスクオリファイ部７による重複して検出されるホットパスの検出処理を説明する。
【００６６】
図８は、ghostscriptの実行により検出されたホットパスの例を示すグラフである。ghostscript はプリンタなどの印刷装置で広く使用されているプログラムであり、ポストスクリプトという形式で記述された文字情報や画像情報を入力とし、それぞれの印刷装置で印刷可能な形式の情報への変換を行う。入力される文字情報や画像情報により、プログラムの中で高い頻度で実行される命令列が異なるため、本発明による推定装置により得られる情報をプログラム実行の最適化に利用することが可能となる。図８のグラフにおいて、横軸は命令実行回数を示し、縦軸は検出されたホットパスを示す。図８のグラフにおいて、例えば、実行回数が40,000,000回を超えた場合に、縦軸の値が１５、２０、９０付近のホットパスが繰り返し検出されているように、ホットパスは重複して検出されることがある。図１のホットパスクオリファイ部７が重複して検出されるホットパス情報を検出して外部に転送しないようにすることにより、ホットパス情報の転送に関するオーバヘッドが削減され、ホットパス情報を記憶する記憶領域が削減される。
【００６７】
図９は、図８において検出されたホットパスのうち本発明の実施の形態により検出されたホットパスの例を示すグラフである。図９に示されるように、本発明によれば、重複せずにホットパスを検出することが可能となる。
【００６８】
図１０は、図１のホットパスクオリファイ部７による検出処理に用いられるホットパスパスシグネチャ情報の一例を示す図である。図１０（ａ）にあるように、ホットパスパスシグネチャ情報は、３２ビットのホットパス開始アドレス（ＢＳＡ）と３ビットの分岐の数と８ビットのパスシグネチャを有する。パスシグネチャの各ビットは、例えば、図１０（ｂ）にあるように、分岐命令が分岐しない場合（すなわち、次のアドレスの命令を実行する場合）には０であり、分岐する場合には１である。分岐の数は、パスシグネチャの各ビットのうち、有効なものを示す。このようなパスシグネチャ情報は、ホットパス検出処理において作成されるものとする。
【００６９】
続いて、図１１を参照して、図１０のパスシグネチャの各ビットの示す情報を説明する。図１１は、基本ブロックの分岐命令に対するパスシグネチャの各ビットの割り当ての一例を示す図であり、基本ブロックＡ〜Ｇはアルファベット順にアドレスが割り当てられているものとする。図１１を参照して、パスシグネチャの各ビットは、例えば基本ブロックＡの次に基本ブロックＢが実行される場合には０が、基本ブロックＤが実行される場合には１が割り当てられる。他の基本ブロックについても同様に、アルファベット順で次の基本ブロックが次に実行される場合には０が、他の基本ブロックが実行される場合には１が割り当てられる。このようなパスシグネチャを使用することにより、分岐命令を含む命令パスの特定が可能となる。
【００７０】
続いて、図１２を参照して、図１のホットパスクオリファイ部７の動作の一例を説明する。図１２は、図１のホットパスクオリファイ部７の概略ブロック図である。図１２において、ホットパスクオリファイ部７はパスシグネチャ比較部４１とホットパス情報出力部４３を有し、パスシグネチャ比較部４１は新パスシグネチャ記憶部４５と既出パスシグネチャ記憶部４７を有する。
【００７１】
図１２のパスシグネチャ比較部４１は、ホットパス検出部５により検出されたホットパスに対応するパスシグネチャを新パスシグネチャ記憶部４５に記憶し、新パスシグネチャ記憶部４５に記憶されたパスシグネチャと既出パスシグネチャ記憶部４７に記憶されたパスシグネチャとを比較する。図１２のパスシグネチャ比較部４１は、新パスシグネチャ記憶部４５に記憶されたパスシグネチャが既出パスシグネチャ記憶部４７に記憶されていたものと一致しない場合には、ホットパス情報出力部４３に対してホットパス検出部５により検出されたホットパス情報を出力させ、新パスシグネチャ記憶部４５に記憶されたパスシグネチャを既出パスシグネチャ記憶部４７に記憶する。ここで、既出パスシグネチャ記憶部４７は、予め定めれたエントリ数（例えば１６エントリ）を保持するものであり、新たにパスシグネチャを追加する場合に、既に予め定められたエントリ数のパスシグネチャが記憶されている場合には、最も使われていないエントリと入れ換える等の処理が行われるものとする。図１２のパスシグネチャ比較部４１は、新たなパスシグネチャが既出パスシグネチャ記憶部に記憶されていた場合には、ホットパス情報を外部に出力しないようにする。
【００７２】
以上のようにして、図１２のホットパスクオリファイ部７が重複して検出されるホットパス情報を検出して外部に転送しないようにすることにより、ホットパス情報の転送に関するオーバヘッドが削減され、ホットパス情報を記憶する記憶領域が削減される。
【図面の簡単な説明】
【００７３】
【図１】本発明の実施の形態に係るホットパス推定装置１の概略ブロック図である。
【図２】図１の分岐履歴管理部１５により管理される分岐履歴テーブルの一例を示す図である。
【図３】図１の分岐履歴管理部１５が、図２の分岐履歴テーブルを２セット用いて行う分岐履歴管理の一例の概略を示す図である。
【図４】図１の分岐履歴管理部１５が、図２の分岐履歴テーブルを複数用いて行う分岐履歴管理の一例を示すフロー図である。
【図５】図１の戻り分岐履歴管理部１７により管理される分岐履歴テーブルの一例を示す図である。
【図６】図１の戻り分岐履歴管理部１７の動作の一例を示すフロー図である。
【図７】図１のホットパス検索部１３の動作の一例を示すフロー図である。
【図８】ghostscriptの実行により検出されたホットパスの例を示すグラフである。
【図９】図８において検出されたホットパスのうち本発明の実施の形態により検出されたホットパスの例を示すグラフである。
【図１０】図１のホットパスクオリファイ部７による検出処理に用いられるホットパスパスシグネチャ情報の一例を示す図である。
【図１１】基本ブロックの分岐命令に対するパスシグネチャの各ビットの割り当ての一例を示す図である。
【図１２】図１のホットパスクオリファイ部７の概略ブロック図である。
【図１３】従来のホットパス推定装置１０１の概略ブロック図である。
【図１４】プロセッサコアで実行される基本ブロックの関係と分岐命令の実行回数の一例を示す図である。
【図１５】図１４に示される基本ブロック間の関係の場合に図１３のＨＷアシスト部１０５により管理されるテーブルの一例を示す図である。
【符号の説明】
【００７４】
１  ホットパス推定装置
５  ホットパス検出部
７  ホットパスクオリファイ部
１１  履歴管理部
１３  ホットパス検索部
１５  分岐履歴管理部
１７  戻り分岐履歴管理部
【図１】
2007109116.tif 000003
【図２】
2007109116.tif 000004
【図３】
2007109116.tif 000005
【図４】
2007109116.tif 000006
【図５】
2007109116.tif 000007
【図６】
2007109116.tif 000008
【図７】
2007109116.tif 000009
【図８】
2007109116.tif 000010
【図９】
2007109116.tif 000011
【図１０】
2007109116.tif 000012
【図１１】
2007109116.tif 000013
【図１２】
2007109116.tif 000014
【図１３】
2007109116.tif 000015
【図１４】
2007109116.tif 000016
【図１５】
2007109116.tif 000017