データ処理装置、履歴保存装置、データ処理方法およびプログラム
【課題】値再利用（メモ化：Memoization）の際、実行結果を保存しておくメモリから実行結果を退避させることにより、値再利用の効率を改善させる。
【解決手段】履歴メモリ４３０は、実行結果が再び利用される再利用区間の実行結果を実行履歴として保持する。主記憶部１３０は、再利用区間のうち実行が反復される反復再利用区間の実行結果を退避履歴として保持する。履歴制御部５１０は、反復再利用区間の実行結果であるループ個別履歴に基づいて、退避履歴およびループ代表履歴を生成する。これにより、反復再利用区間の実行結果を退避履歴として主記憶部１３０に退避するとともに、その実行結果を含むループ個別履歴の代わりにループ代表履歴を履歴メモリ４３０に登録する。
【解決手段】履歴メモリ４３０は、実行結果が再び利用される再利用区間の実行結果を実行履歴として保持する。主記憶部１３０は、再利用区間のうち実行が反復される反復再利用区間の実行結果を退避履歴として保持する。履歴制御部５１０は、反復再利用区間の実行結果であるループ個別履歴に基づいて、退避履歴およびループ代表履歴を生成する。これにより、反復再利用区間の実行結果を退避履歴として主記憶部１３０に退避するとともに、その実行結果を含むループ個別履歴の代わりにループ代表履歴を履歴メモリ４３０に登録する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置に関し、特に実行結果が再利用される命令区間を実行するデータ処理装置、履歴保存装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。
【背景技術】
【０００２】
プログラムの処理速度を高速化するために種々の技術が開発されている。近年、その技術を用いた装置の一つとして、値再利用（メモ化：Memoization）と呼ばれる命令区間の実行結果を再利用する技法を用いた区間再利用装置が提案されている（例えば、特許文献１参照。）。この区間再利用装置は、プログラムの所定の命令区間における入力値および実行結果を保存しておくことによって、同じ命令区間を再び実行する際に入力値が一致する場合には、保存していた実行結果である出力値を出力する装置である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００４−２５８９０５号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術では、同じ命令区間を再び実行して実行結果を出力する際に、それ以前に保存していた実行結果を出力することによって、その命令区間の実行時間を削減することができる。
【０００５】
しかしながら、このような区間再利用装置では、実行結果を保存しておくメモリが満杯の場合には新たな実行履歴を登録するために古い実行結果を削除することから、その削除された実行結果の再利用ができないという問題が生じる。すなわち、このような区間再利用装置では、実行結果を保存しておくメモリから実行結果が削除されることに起因する値再利用の効率の低下が生じる場合が考えられる。
【０００６】
そこで、本発明はこのような状況に鑑みてなされたものであり、値再利用（メモ化）を行う際、実行結果を保存しておくメモリから実行結果を退避させることにより、値再利用の効率を改善することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、命令区間を実行して実行結果を出力する実行部と、上記命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、上記保持した実行結果が再び利用される場合には上記区間識別情報および上記入力値に基づいて上記実行履歴が検索される履歴メモリと、上記再利用区間のうち実行が反復される反復再利用区間の各回の上記実行結果を上記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と、上記反復再利用区間の上記実行履歴に基づいて上記退避履歴を上記退避履歴保持部に供給し、上記退避履歴の供給の際に上記退避履歴の基となった上記実行履歴を上記履歴メモリから消去して上記退避履歴を指し示す情報を含む代表履歴を上記履歴メモリに保持させる履歴制御部とを備えるデータ処理装置およびその処理方法ならびに当該方法をコンピュータに実行させるプログラムである。これにより、再利用区間の実行が反復される反復再利用区間の実行結果を履歴メモリから退避履歴保持部に退避させるという作用をもたらす。
【０００８】
また、この第１の側面において、上記履歴制御部は、上記履歴メモリに保持させる新たな上記実行履歴のデータ量が上記履歴メモリの空き容量よりも大きい場合には上記退避履歴を上記退避履歴保持部に供給するようにしてもよい。これにより、実行履歴のデータ量が履歴メモリの空き容量よりも大きい場合には、反復再利用区間の実行結果を履歴メモリから退避履歴保持部に退避させるという作用をもたらす。
【０００９】
また、この第１の側面において、上記退避履歴および上記代表履歴に基づいて上記実行履歴を上記履歴メモリに復元する履歴復元部と、上記区間識別情報および上記入力値に基づいて上記復元された上記実行履歴を上記履歴メモリから検索した場合には上記復元された上記実行履歴に基づいて上記実行結果を出力する履歴検索部とをさらに備えるようにしてもよい。これにより、退避履歴および代表履歴に基づいて復元した実行履歴を用いて実行結果を再利用させるという作用をもたらす。この場合において、上記履歴検索部は、上記区間識別情報および上記入力値に基づいて検索された上記実行履歴が上記代表履歴であった場合には上記復元部に上記実行履歴の復元を開始させるようにしてもよい。これにより、履歴検索部において代表履歴が検索された場合には、復元部に反復再利用区間の実行履歴を復元させるという作用をもたらす。この場合において、上記履歴制御部は、上記退避履歴の個数を示す退避カウントをさらに含む上記代表履歴を生成し、上記履歴復元部は、上記代表履歴における上記退避履歴を指し示す情報および上記退避カウントに基づいて上記退避履歴を上記退避履歴保持部から抽出して上記実行履歴を復元させるようにしてもよい。これにより、代表履歴における退避履歴を指し示す情報および退避カウントに基づいて退避履歴を退避履歴保持部から抽出させるという作用をもたらす。
【００１０】
また、この第１の側面において、上記実行部は、上記再利用区間の上記実行結果を供給する場合には上記反復再利用区間の上記実行履歴と上記反復再利用区間以外の上記実行履歴と上記代表履歴とを識別するための識別子をさらに出力し、上記履歴メモリは、上記識別子を上記実行履歴としてさらに保持し、上記履歴制御部は、上記識別子を用いて識別した上記実行履歴に基づいて上記退避履歴を供給し、上記識別子をさらに含む上記代表履歴を生成させるようにしてもよい。これにより、識別子を用いて実行履歴を識別させるという作用をもたらす。
【００１１】
また、この第１の側面において、上記反復再利用区間はサブルーチンであり、上記実行部は、上記サブルーチンの開始アドレスを上記区間識別情報として出力するようにしてもよい。これにより、サブルーチンの開始アドレスを区間識別情報として出力させるという作用をもたらす。
【００１２】
また、この第１の側面において、上記反復再利用区間はループであり、上記実行部は、上記ループの開始アドレスを上記区間識別情報として出力するようにしてもよい。これにより、ループの開始アドレスを上記区間識別情報として出力させるという作用をもたらす。この場合において、上記実行部は、上記反復再利用区間の上記実行結果を出力する場合には何回目の実行による上記実行結果であるかを示すカウンタ値をさらに出力し、上記履歴メモリは、上記カウンタ値を上記実行履歴としてさらに保持し、上記履歴制御部は、上記カウンタ値を含む上記退避履歴を出力するようにしてもよい。これにより、カウンタ値を含む実行履歴および退避履歴を保持させるという作用をもたらす。
【００１３】
また、本発明の第２の側面は、実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、上記保持した実行結果が再び利用される場合には上記区間識別情報および上記入力値に基づいて上記実行履歴が検索される履歴メモリと、上記再利用区間のうち実行が反復される反復再利用区間の各回の上記実行結果を退避履歴として上記履歴メモリから外部の記憶部に退避させ、上記退避の際に上記退避履歴の基となった上記実行履歴を上記履歴メモリから消去して上記退避履歴を指し示す情報を含む代表履歴を上記履歴メモリに保持させる履歴制御部とを備える履歴保存装置である。これにより、実行が反復される反復再利用区間の実行結果を履歴メモリから外部の記憶部に退避させるという作用をもたらす。
【発明の効果】
【００１４】
本発明によれば、値再利用（メモ化）を行う際、実行結果を保存しておくメモリから実行結果を退避させることにより、値再利用の効率を改善することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態におけるデータ処理装置１００の構成例を示すブロック図である。
【図２】本発明の実施の形態におけるプロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例を示すブロック図である。
【図３】本発明の実施の形態における履歴制御部５１０の構成例を示すブロック図である。
【図４】本発明の実施の形態における退避履歴生成部６００の構成例を示すブロック図である。
【図５】本発明の実施の形態における履歴復元部５２０の構成例を示すブロック図である。
【図６】本発明の実施の形態における関数履歴、ループ個別履歴、ループ代表履歴および退避履歴のデータ構造例を示す模式図である。
【図７】本発明の実施の形態における入力値リンクおよび実行結果リンクのデータ構造例を示す概念図である。
【図８】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。
【図９】本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。
【図１０】本発明の実施の形態における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示す図である。
【図１１】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避処理の処理手順例を示すフローチャートである。
【図１２】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の連履歴探索退避処理（ステップＳ９３０）の処理手順例を示すフローチャートである。
【図１３】本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元処理の処理手順例を示すフローチャートである。
【図１４】本発明の実施の形態における実行結果登録処理（ステップＳ９７０）の処理手順例を示すフローチャートである。
【図１５】本発明の実施の形態における実行結果出力処理（ステップＳ９８０）の処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．データ処理装置の構成例（値再利用制御：反復再利用区間の実行履歴を退避する例）
２．履歴情報のフィールド構成例（値再利用制御：関数履歴、ループ個別履歴、ループ代表履歴および退避履歴の例）
３．履歴メモリに保持される履歴情報および主記憶部に保持される退避履歴の一例（値再利用制御：ループ個別履歴例を退避および復元させる例）
４．データ処理装置の処理手順例（値再利用制御：ループ個別履歴例を退避および復元させる例）
【００１７】
＜１．データ処理装置の構成例＞
［データ処理装置１００の構成例］
図１は、本発明の実施の形態におけるデータ処理装置１００の構成例を示すブロック図である。このデータ処理装置１００は、バス１２０を介して主記憶部１３０と相互に接続されている。また、ここでは、データ処理装置１００が処理を実行する命令区間は関数またはループであることを想定する。
【００１８】
データ処理装置１００は、プログラムにおける各処理を実行するものである。このデータ処理装置１００は、例えば、一般的なコンピュータにおいてはＣＰＵ（Central Processing Unit）により実現される。このデータ処理装置１００は、一次キャッシュ２００と、プロセッサコア３００と、履歴管理部４００と、履歴変換部５００とを備える。
【００１９】
一次キャッシュ２００は、プロセッサコア３００がバス１２０を介して扱う情報を一時的に保持するものである。この一次キャッシュ２００は、命令キャッシュ２１０およびデータキャッシュ２２０を備える。
【００２０】
命令キャッシュ２１０は、プロセッサコア３００において実行される命令を一時的に保持するものである。この命令キャッシュ２１０は、プロセッサコア３００が頻繁に実行する命令を一時的に保持することによって、プロセッサコア３００から主記憶部１３０へのアクセスを軽減させ、プロセッサコア３００におけるデータの入力待ち時間を軽減させることができる。この命令キャッシュ２１０は、主記憶部１３０から供給された再利用命令をプロセッサコア３００に供給する。ここにいう再利用命令とは、命令区間のうち実行結果が再び利用される再利用区間を再び利用されない区間と区別することによって、再利用区間が呼出された際に実行結果を再利用するための処理をデータ処理装置に行わせる命令である。
【００２１】
データキャッシュ２２０は、プロセッサコア３００の入力データおよび出力データを一時的に保持するものである。このデータキャッシュ２２０は、使用頻度の高いプロセッサコア３００の入力データを一時的に保持することによりプロセッサコア３００から主記憶部１３０へのアクセスを軽減させて、プロセッサコア３００におけるデータの入力待ち時間を軽減させる。このデータキャッシュ２２０は、主記憶部１３０から供給された関数またはループの入力値および開始アドレスをプロセッサコア３００に出力する。なお、ここで、入力値とは、関数またはループの実行に必要な値として渡される値の引数で構成される値であり、例えば、３つの変数を引数とする関数の場合には、この３つの変数の値およびその変数のアドレスである。
【００２２】
プロセッサコア３００は、プログラムの命令に従って演算を実行するものである。このプロセッサコア３００は、例えば、ＭＩＰＳ（Microprocessor without Interlocked Pipeline Stages）プロセッサにより実現される。プロセッサコア３００は、例えば、データキャッシュ２２０から供給される関数またはループの入力値および開始アドレスに基づいて、命令キャッシュ２１０から入力される関数またはループの区間における命令を実行し、その実行の結果を実行結果として出力する。このプロセッサコア３００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部４００から実行結果が供給されないときには、この命令を実行した結果である実行結果をデータキャッシュ２２０および履歴管理部４００に出力する。
【００２３】
また、プロセッサコア３００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部４００から実行結果が供給されたときには、再利用区間における処理を中止して、この再利用区間を呼び出したルーチンに戻って実行を継続する。
【００２４】
履歴管理部４００は、再利用区間の実行結果を保持して管理するものである。この履歴管理部４００は、プロセッサコア３００から供給された再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持する。ここでいう区間識別情報とは、再利用区間を特定するための情報であり、例えば、関数またはループの開始アドレスである。すなわち、この履歴管理部４００は、区間識別情報、入力値、および、実行結果として、関数またはループの開始アドレス、入力値、および、実行結果を保持する。また、この履歴管理部４００は、プロセッサコア３００から関数またはループの開始アドレスおよび入力値が供給された場合には、この開始アドレスおよび入力値が含まれる実行履歴を検索する。
【００２５】
履歴変換部５００は、履歴管理部４００により管理されている実行履歴を変換するものである。この履歴変換部５００は、履歴管理部４００に登録されている再利用区間のうち実行が反復される反復再利用区間の実行履歴を、主記憶部１３０において保持される退避履歴に変換する。ここで、退避履歴とは、反復再利用区間の実行履歴の実行結果を主記憶部１３０に退避させるためのデータである。また、この履歴変換部５００は、主記憶部１３０において保持された退避履歴に基づいて実行履歴を復元する。この履歴変換部５００は、その退避履歴を主記憶部１３０に保持させ、退避履歴を生成する基となった実行履歴を履歴管理部４００から消去し、退避履歴を指し示す情報を保持する代表履歴を履歴管理部４００に登録する。
【００２６】
また、この履歴変換部５００は、その退避履歴に含まれる実行結果を再利用する場合には、退避履歴から実行履歴を復元するとともに代表履歴を消去し、履歴管理部４００に復元した実行履歴を登録する。
【００２７】
バス１２０は、データ処理装置１００の各部と主記憶部１３０との間を相互に接続するバスである。
【００２８】
主記憶部１３０は、データ処理装置１００が動作するために必要なデータを保持するものである。この主記憶部１３０は、履歴変換部５００から供給された退避履歴を保持する。また、この主記憶部１３０は、データ処理装置１００に処理を実行させるためのプログラムを記憶する。この主記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）などが考えられる。この主記憶部１３０は、記憶しているデータを、バス１２０を介してデータ処理装置１００に出力する。なお、主記憶部１３０は、特許請求の範囲に記載の退避履歴保持部の一例である。
【００２９】
［プロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例］
図２は、本発明の実施の形態におけるプロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例を示すブロック図である。ここでは、プロセッサコア３００と履歴管理部４００と履歴変換部５００とに加えて、バス１２０を介して履歴変換部５００と接続される主記憶部１３０も示されている。ここでは、プロセッサコア３００と履歴管理部４００と履歴変換部５００と主記憶部１３０との機能は、図１と同様のものであるため、同一の符号を付してここでの詳細な説明を省略する。
【００３０】
また、これ以降の説明では、便宜上、繰り返し実行される区間である反復再利用区間はループであり、反復再利用区間以外の再利用区間は関数であることを想定する。この反復再利用区間以外の再利用区間は、関数再利用区間と表現することとする。そして、ループの実行結果をループ個別履歴と表現し、関数の実行結果を関数履歴と表現することとする。さらに、退避履歴を指し示す代表履歴は、ループ代表履歴と表現する。
【００３１】
プロセッサコア３００は、フェッチ部３１０と、命令デコーダ３２０と、実行部３３０と、レジスタファイル３４０とを備える。
【００３２】
フェッチ部３１０は、命令キャッシュ２１０または主記憶部１３０からの命令を読み出すものである。このフェッチ部３１０は、その読み出した命令を一時的に保持して、その保持されている命令のうち、実行部３３０に実行させるための命令を命令デコーダ３２０に供給する。このフェッチ部３１０は、例えば、一時的に保持している命令のうち、実行部３３０において実行される再利用命令を命令デコーダ３２０に供給する。このフェッチ部３１０は、例えば、主記憶部１３０に記憶された再利用命令を命令デコーダ３２０に供給する。
【００３３】
命令デコーダ３２０は、フェッチ部３１０から供給された命令を解読（デコード）することによって、プロセッサコア３００における構成部位を制御する制御信号を生成するものである。この命令デコーダ３２０は、例えば、命令を解読することによって実行部３３０およびレジスタファイル３４０を制御する制御信号を生成して、その生成された制御信号を実行部３３０およびレジスタファイル３４０に供給する。
【００３４】
この命令デコーダ３２０は、フェッチ部３１０から再利用命令が供給された場合には、その再利用命令を解析することによって、実行部３３０およびレジスタファイル３４０の各々を制御する制御信号を実行部３３０およびレジスタファイル３４０に供給する。
【００３５】
実行部３３０は、命令デコーダ３２０から供給された制御信号に基づいて、命令デコーダ３２０において解析した命令を実行するものである。この実行部３３０は、命令デコーダ３２０が再利用命令をデコードした場合、再利用命令が指定する再利用区間の処理を開始する。また、この再利用区間の処理の開始とともに、実行部３３０は、レジスタファイル３４０から取得した再利用区間の区間識別情報を、信号線３０９を介して履歴管理部４００に出力する。そして、実行部３３０は、レジスタファイル３４０から供給される再利用区間の入力値に基づいて再利用区間における処理を実行するとともに、再利用区間の入力値を、信号線３０９を介して履歴管理部４００に出力する。
【００３６】
また、実行部３３０は、履歴管理部４００から再利用区間の実行結果が供給された場合には、再利用区間の処理を中止するとともに、その実行結果を履歴管理部４００から供給された旨を通知する信号をフェッチ部３１０に供給する。この時、実行部３３０は、実行結果をレジスタファイル３４０に出力する。
【００３７】
一方、実行部３３０は、履歴管理部４００から再利用区間の実行結果が供給されない場合には、再利用区間の処理を最後まで実行して、その実行結果を履歴管理部４００およびレジスタファイル３４０に出力する。さらに、この実行部３３０は、反復再利用区間の実行結果が供給されない場合には、何回目の実行による実行結果であるのかを示すループカウンタ値を実行結果とともに履歴管理部４００に出力する。なお、ループカウンタ値は、特許請求の範囲に記載のカウンタ値の一例である。
【００３８】
レジスタファイル３４０は、データキャッシュ２２０から供給されたデータおよび実行部３３０から供給された実行結果を一時的に保持するものである。このレジスタファイル３４０は、例えば、命令デコーダ３２０から再利用命令に基づく制御信号が供給された場合には、再利用区間の入力値を実行部３３０に供給する。
【００３９】
履歴管理部４００は、再利用区間の実行結果を保持して管理するものであり、履歴対象データ保持部４１０と、履歴検索部４２０と、履歴メモリ４３０と、履歴登録部４４０と、履歴メモリ容量管理部４５０と、消去部４６０とを備える。
【００４０】
履歴対象データ保持部４１０は、実行部３３０から供給されたデータを一時的に保持するものである。この履歴対象データ保持部４１０は、実行部３３０から区間識別情報および入力値が供給された際には、これらを検索要求として履歴検索部４２０に供給する。この履歴対象データ保持部４１０は、例えば、実行部３３０において関数再利用区間が実行された場合には、実行部３３０から供給された関数の開始アドレスおよび入力値を、検索要求として履歴検索部４２０に供給する。また、履歴対象データ保持部４１０は、実行部３３０において反復再利用区間が実行された場合には、実行部３３０から供給されたループの開始アドレス、入力値およびループカウンタ値を検索要求として履歴検索部４２０に供給する。
【００４１】
また、この履歴対象データ保持部４１０は、実行部３３０から区間識別情報と、入力値と、実行結果とが供給された場合には、実行履歴を登録する条件が整うため、これらを実行履歴として履歴登録部４４０に供給する。例えば、履歴対象データ保持部４１０は、実行部３３０において関数再利用区間が実行された場合には、実行部３３０から供給された関数の開始アドレスと入力値と実行結果とを実行履歴として履歴登録部４４０に供給する。また、履歴対象データ保持部４１０は、実行部３３０において反復再利用区間が実行された場合には、ループの開始アドレスと入力値と実行結果とループカウンタ値とを実行履歴として履歴登録部４４０に供給する。
【００４２】
履歴検索部４２０は、履歴対象データ保持部４１０から供給された検索要求に基づいて実行履歴を検索するものである。この履歴検索部４２０は、検索要求入力部４２１および実行結果出力部４２２を備える。
【００４３】
検索要求入力部４２１は、履歴対象データ保持部４１０から供給された検索要求に基づいて履歴メモリ４３０から実行履歴を検索するものである。この検索要求入力部４２１は、例えば、反復再利用区間を指定する命令が命令デコーダ３２０において解析された場合には、この命令により指定されたループの開始アドレス、入力値およびループカウンタ値を履歴メモリ４３０に供給する。これにより、実行履歴の検索を開始する。
【００４４】
実行結果出力部４２２は、履歴メモリ４３０において実行履歴が検索された場合に実行結果を履歴メモリ４３０から抽出して、その抽出した実行結果を実行部３３０に出力するものである。この実行結果出力部４２２は、その抽出した実行結果を、信号線４０９を介して実行部３３０に供給する。
【００４５】
また、この実行結果出力部４２２は、履歴メモリ４３０においてループ代表履歴が実行履歴として検索された場合には、退避履歴を指し示す退避履歴位置情報を、実行結果の代わりに履歴メモリ４３０から抽出する。そして、その抽出した退避履歴に関する情報を履歴変換部５００に出力し、実行履歴の復元を開始させる。
【００４６】
履歴メモリ４３０は、履歴登録部４４０から供給された実行履歴を保持するものである。この履歴メモリ４３０は、例えば、履歴検索部４２０から検索要求が供給された場合において、この検索要求と一致する実行履歴を保持しているときは、この実行履歴の実行結果を実行結果出力部４２２に供給する。また、この履歴メモリ４３０は、履歴検索部４２０から検索要求が供給された場合において、この検索要求と一致するループ代表履歴を保持しているときは、このループ代表履歴の退避履歴位置情報を実行結果出力部４２２に供給する。さらに、この履歴メモリ４３０は、履歴登録部４４０から実行履歴が供給された場合には、この実行履歴を保持する。
【００４７】
また、この履歴メモリ４３０は、履歴メモリ４３０の使用状況に関する情報を履歴メモリ容量管理部４５０に供給する。さらにこの履歴メモリ４３０は、保持している実行履歴およびループ代表履歴を履歴変換部５００に供給する。この履歴メモリ４３０は、例えば、連想メモリ（ＣＡＭ：Content Addressable Memory）により実現される。
【００４８】
履歴登録部４４０は、履歴対象データ保持部４１０から供給された実行履歴を履歴メモリ４３０に保持させるためのデータ構造に変換して、その変換された実行履歴を履歴メモリ４３０に登録するものである。この履歴登録部４４０は、例えば、履歴検索部４２０により関数履歴が検索されない場合には、関数の開始アドレス、入力値および実行結果を、実行履歴として履歴メモリ４３０に登録する。また、この履歴登録部４４０は、例えば、履歴検索部４２０によりループ個別履歴が検索されない場合には、ループの開始アドレス、入力値、実行結果およびループカウンタ値を実行履歴として履歴メモリ４３０に登録する。
【００４９】
また、この履歴登録部４４０は、履歴メモリ容量管理部４５０から供給される履歴メモリ４３０の空き容量に比べて新たに登録する実行履歴のデータ量の方が大きい場合には、登録を一時中断する。そして、この履歴登録部４４０は、既に登録されている実行履歴のうち、前回の使用からの未使用期間が最も長い実行履歴を消去させるための消去開始情報を消去部４６０に供給する。
【００５０】
履歴メモリ容量管理部４５０は、履歴メモリ４３０の空き容量を管理するものである。この履歴メモリ容量管理部４５０は、例えば、履歴メモリ４３０に新たな実行履歴が登録される度に、履歴メモリ４３０の空き容量を測定する。さらに、この履歴メモリ容量管理部４５０は、履歴メモリ４３０から実行履歴が消去される度に、履歴メモリ４３０の空き容量を測定する。この履歴メモリ容量管理部４５０は、履歴メモリ４３０の空き容量に関する情報を履歴登録部４４０に供給する。
【００５１】
消去部４６０は、履歴登録部４４０から消去開始情報が供給された場合には、前回の使用からの未使用期間が最も長い実行履歴を消去するものである。
【００５２】
履歴変換部５００は、履歴管理部４００により管理されている実行履歴を退避履歴に変換して主記憶部１３０に保持させるものであり、履歴制御部５１０と、履歴復元部５２０と、退避領域管理部５３０とを備える。
【００５３】
履歴制御部５１０は、履歴メモリ４３０に保持されているループ個別実行履歴から退避履歴を生成して、主記憶部１３０に退避するものである。この履歴制御部５１０は、例えば、履歴メモリ４３０から反復再利用区間の実行履歴を、信号線４９０を介して抽出し、その実行履歴と、退避領域管理部５３０から供給される主記憶部１３０のアドレス情報とに基づいて退避履歴を主記憶部１３０に退避させる。また、この履歴制御部５１０は、例えば、履歴メモリ４３０に保持させる新たな実行履歴のデータ量が履歴メモリ４３０の空き容量より大きい場合に退避履歴の退避を開始する。
【００５４】
そして、この履歴制御部５１０は、退避履歴の基となったループ個別履歴を履歴メモリ４３０から消去し、退避履歴位置情報を含むループ代表履歴をループ個別履歴の代わりに履歴メモリ４３０に登録する。なお、ここでいう退避履歴位置情報とは、例えば、退避履歴の主記憶部１３０における格納位置を指し示す主記憶部１３０のアドレスである。このように、履歴制御部５１０は、生成した退避履歴を、信号線５０９を介して主記憶部１３０に供給する。また、履歴制御部５１０は、生成したループ代表履歴を、信号線５９０を介して履歴メモリ４３０に供給する。なお、履歴制御部５１０および履歴メモリ４３０から構成される装置は、特許請求の範囲に記載の履歴保存装置の一例である。
【００５５】
履歴復元部５２０は、実行結果出力部４２２から供給された退避履歴位置情報に基づいて主記憶部１３０から退避履歴を抽出して、その退避履歴に基づいて実行履歴を復元するものである。この履歴復元部５２０は、例えば、主記憶部１３０に退避した退避履歴の実行結果を再利用する場合には、実行結果出力部４２２から供給された退避履歴の情報に基づいて主記憶部１３０から信号線１３９を介して退避履歴を抽出する。そして、この履歴復元部５２０は、履歴メモリ４３０から抽出したループ代表履歴と、主記憶部１３０から抽出した退避履歴とに基づいて実行履歴を復元する。その後、この履歴復元部５２０は、履歴メモリ４３０に保持されているループ代表履歴を消去し、さらに履歴メモリ４３０における退避履歴を保持する容量を確保した後に、復元した実行履歴を履歴メモリ４３０に登録する。
【００５６】
このように、この履歴復元部５２０は、復元した実行履歴を、信号線５８０を介して履歴メモリ４３０に供給する。
【００５７】
退避領域管理部５３０は、主記憶部１３０における退避履歴が保持される領域を管理するものである。この退避領域管理部５３０は、例えば、退避履歴が保持される領域を主記憶部１３０に確保し、履歴制御部５１０が退避履歴を生成した場合には、主記憶部１３０におけるその退避履歴の退避先のアドレスを履歴制御部５１０に信号線５３９を介して供給する。
【００５８】
主記憶部１３０は、この構成図においては退避履歴を保持するものである。なお、主記憶部１３０は、特許請求の範囲に記載の退避履歴保持部の一例である。
【００５９】
このように、本発明の実施の形態では、プロセッサコア３００と履歴管理部４００と履歴変換部５００とを設けることによって、反復再利用区間の実行履歴を主記憶部１３０に退避させることができる。
【００６０】
なお、ここでは、反復再利用区間がループである場合について説明したが、これに限定されるものではない。例えば、ループ以外の反復再利用区間として、再帰呼び出し（リカーシブコール）を伴うサブルーチンなどが考えられる。
【００６１】
［履歴制御部５１０の構成例］
図３は、本発明の実施の形態における履歴制御部５１０の構成例を示すブロック図である。履歴制御部５１０は、退避履歴生成部６００と、ループ個別履歴消去部５１２と、ループ代表履歴登録部５１３とを備える。
【００６２】
退避履歴生成部６００は、ループ個別履歴に基づいて退避履歴を生成するものである。この退避履歴生成部６００は、例えば、ループの反復された実行による実行結果を含むループ個別履歴を履歴メモリ４３０から信号線４９０を介して取得して、その取得したループ個別履歴に基づいて退避履歴を生成する。この時、この退避履歴生成部６００は、主記憶部１３０におけるその退避履歴の退避先のアドレスを退避領域管理部５３０から信号線５３９を介して受け取る。そして、この退避履歴生成部６００は、その生成した退避履歴を、信号線５０９を介して主記憶部１３０に退避させる。
【００６３】
また、この退避履歴生成部６００は、退避履歴位置情報を含むループ代表履歴を生成し、信号線６０８を介してループ代表履歴登録部５１３に供給する。さらに、この退避履歴生成部６００は、退避履歴の基となったループ個別履歴を、信号線６０９を介してループ個別履歴消去部５１２に供給する。
【００６４】
ループ個別履歴消去部５１２は、退避履歴の基となった実行履歴を消去するものである。このループ個別履歴消去部５１２は、退避履歴生成部６００から供給された退避履歴の基となったループ個別履歴に基づいて、このループ個別履歴を履歴メモリ４３０から信号線５９２を介して消去する。また、このループ個別履歴消去部５１２は、そのループ個別履歴の消去を通知する情報をループ代表履歴登録部５１３に供給する。
【００６５】
ループ代表履歴登録部５１３は、ループ代表履歴を履歴メモリ４３０に登録するものである。このループ代表履歴登録部５１３は、例えば、退避履歴生成部６００からループ代表履歴が供給された場合に、ループ個別履歴消去部からループ個別履歴の消去を通知する情報が供給されたときは、ループ代表履歴を履歴メモリ４３０に信号線５９３を介して登録する。
【００６６】
［退避履歴生成部６００の構成例］
図４は、本発明の実施の形態における退避履歴生成部６００の構成例を示すブロック図である。退避履歴生成部６００は、先頭探索部６１０と、連続探索部６２０と、ループ個別履歴取得部６３０と、退避履歴転送部６４０と、ループ代表履歴生成部６５０とを備える。
【００６７】
先頭探索部６１０は、反復再利用区間の１回目の実行に関するループ個別履歴を、履歴メモリ４３０から信号線４９１を介して探索するものである。この先頭探索部６１０は、ループ個別履歴を探索した場合には、一旦動作を停止してその後のループ個別履歴の探索を連続探索部６２０に処理させる。この先頭探索部６１０は、その探索したループ個別履歴に関する位置情報を連続探索部６２０に供給する。
【００６８】
連続探索部６２０は、先頭探索部６１０から供給された反復再利用区間の１回目の実行に関するループ個別履歴の位置情報に基づいて、２回目以降の実行に関するループ個別履歴を、信号線４９２を介して探索するものである。この連続探索部６２０は、例えば、５０回反復されたループにおいて、１回目のループ個別履歴の位置情報が先頭探索部６１０から供給された場合には、２回目から５０回目までのループ個別履歴を探索する。そして、この連続探索部６２０は、５１回目の実行履歴が探索されなかったときに、その５０個のループ個別履歴を取得するための位置情報をループ個別履歴取得部６３０に供給する。
【００６９】
また、この連続探索部６２０は、２回目以降のループ個別履歴が探索されなかった場合には、反復再利用区間は反復して実行されなかったと判断して、退避履歴の生成を中止する。そして、この連続探索部６２０は、一端動作を停止して先頭探索部６１０に反復再利用区間の１回目の実行に関するループ個別履歴の探索を再開させる。
【００７０】
ループ個別履歴取得部６３０は、連続探索部６２０から供給されたループ個別履歴を取得するための位置情報に基づいて、ループ個別履歴を、信号線４９３を介して履歴メモリ４３０から取得するものである。このループ個別履歴取得部６３０は、例えば、連続探索部６２０から５０回反復された反復再利用区間における５０個のループ個別履歴に関する位置情報が供給された場合には、その５０個のループ個別履歴を履歴メモリ４３０から取得する。また、このループ個別履歴取得部６３０は、その取得したループ個別履歴を、信号線６３８および信号線６０９を介して退避履歴転送部６４０、ループ代表履歴生成部６５０およびループ個別履歴消去部５１２に供給する。
【００７１】
退避履歴転送部６４０は、ループ個別履歴取得部６３０から供給されたループ個別履歴に基づいて退避履歴を生成して、その生成された退避履歴を主記憶部１３０に転送するものである。この退避履歴転送部６４０は、例えば、５０回反復された反復再利用区間の５０個のループ個別履歴が供給された場合には、５０個の退避履歴を生成する。この退避履歴転送部６４０は、退避領域管理部５３０から信号線５３９を介して供給される主記憶部１３０のアドレスに基づいて退避履歴を主記憶部１３０に退避させる。この退避履歴転送部６４０は、生成した退避履歴を、信号線５０９を介して主記憶部１３０に転送する。
【００７２】
ループ代表履歴生成部６５０は、ループ個別履歴取得部６３０から供給されたループ個別履歴に基づいてループ代表履歴を生成するものである。このループ代表履歴生成部６５０は、退避領域管理部５３０から信号線５３９を介して供給される主記憶部１３０のアドレスに基づいて、退避履歴位置情報が含まれるループ代表履歴を生成する。このループ代表履歴生成部６５０は、その生成したループ代表履歴を、信号線６０８を介してループ代表履歴登録部５１３に供給する。
【００７３】
［履歴復元部５２０の構成例］
図５は、本発明の実施の形態における履歴復元部５２０の構成例を示すブロック図である。履歴復元部５２０は、退避履歴取得部５２１と、ループ個別履歴生成部５２２と、登録領域確保部５２３と、ループ個別履歴登録部５２４とを備える。
【００７４】
退避履歴取得部５２１は、実行結果出力部４２２から供給された退避履歴位置情報に基づいて主記憶部１３０から退避履歴を取得するものである。この退避履歴取得部５２１は、例えば、反復して５０回実行された反復再利用区間の退避履歴を取得する場合には、実行結果出力部４２２から信号線４０８を介して供給された退避履歴位置情報に基づいて、その５０個の退避履歴を主記憶部１３０から取得する。この退避履歴取得部５２１は、その取得した退避履歴をループ個別履歴生成部５２２に供給する。
【００７５】
ループ個別履歴生成部５２２は、退避履歴からループ個別履歴を生成するものである。このループ個別履歴生成部５２２は、信号線４０８を介して供給された退避履歴位置情報に基づいて、その退避履歴位置情報を含むループ代表履歴を履歴メモリ４３０から信号線４８０を介して取得する。そして、このループ個別履歴生成部５２２は、その取得したループ代表履歴と、退避履歴取得部５２１から供給された退避履歴とに基づいて、ループ個別履歴を生成する。
【００７６】
このループ個別履歴生成部５２２は、その生成したループ個別履歴をループ個別履歴登録部５２４に供給する。また、このループ個別履歴生成部５２２は、ループ代表履歴と、ループ個別履歴のデータ量とを登録領域確保部５２３に供給する。
【００７７】
登録領域確保部５２３は、ループ個別履歴を登録するために履歴メモリ４３０の空き領域を確保するものである。この登録領域確保部５２３は、ループ個別履歴生成部５２２から供給されたループ代表履歴を、履歴メモリ４３０から信号線５８３を介して消去する。そして、この登録領域確保部５２３は、ループ個別履歴生成部５２２から供給されたループ個別履歴のデータ量に基づいて、履歴メモリ４３０に全てのループ個別履歴を登録する空き容量があるか否か判断する。この登録領域確保部５２３は、履歴メモリ４３０にその空き容量が不足している場合には、信号線５８３を介して空き容量を確保する。例えば、この登録領域確保部５２３は、前回の使用からの未使用期間が最も長い実行履歴を消去して履歴メモリ４３０における必要な空き容量を確保する。
【００７８】
この登録領域確保部５２３は、履歴メモリ４３０における空き容量に関する情報をループ個別履歴登録部５２４に供給する。
【００７９】
ループ個別履歴登録部５２４は、ループ個別履歴生成部５２２から供給されたループ個別履歴を、信号線５８４を介して履歴メモリ４３０に登録するものである。このループ個別履歴登録部５２４は、ループ個別履歴生成部５２２から供給されたループ個別履歴を、登録領域確保部５２３から供給された情報が指し示す履歴メモリ４３０の空き容量に登録する。
【００８０】
このように、本発明の実施の形態では、データ処理装置１００に履歴管理部４００および履歴変換部５００を設けることによって、実行が反復される反復再利用区間の実行履歴を退避履歴として主記憶部１３０に退避することができる。
【００８１】
＜２．履歴情報のフィールド構成例＞
［実行履歴、ループ個別履歴および退避履歴のフィールド構成例］
図６は、本発明の実施の形態における履歴メモリ４３０に保持される関数履歴、ループ個別履歴およびループ代表履歴と、主記憶部１３０に保持される退避履歴とのフィールド構成例を示す模式図である。
【００８２】
図６（ａ）には、関数再利用区間の実行履歴である関数履歴７１０のフィールド構成例が示されている。この関数履歴７１０は、識別子フィールド７１１と、開始アドレスフィールド７１２と、入力値リンクフィールド７１３と、実行結果リンクフィールド７１７とから構成される。
【００８３】
識別子フィールド７１１は、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するためのフィールドである。この識別子フィールド７１１には、関数履歴であることを示す２ビット（００）が格納される。また、この識別子フィールド７１１は、関数履歴７１０における先頭のフィールドであり、例えば、その関数履歴７１０の開始アドレスに保持されるフィールドである。
【００８４】
開始アドレスフィールド７１２は、関数の開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７１２に格納される関数の開始アドレスは、検索要求入力部４２１により実行履歴が検索される場合には、検索要求の開始アドレスと比較される。
【００８５】
入力値リンクフィールド７１３は、リンク構造を用いて格納されている関数の入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７１３には、検索要求入力部４２１により実行履歴が検索されて検索要求の開始アドレスが開始アドレスフィールド７１２の開始アドレスと一致したときに、検索要求の入力値と比較される入力値を保持するアドレスが格納される。この入力値リンクフィールド７１３には、例えば、３つの引数を入力値とする関数の場合には、３つの関数のうち１番目の引数の値である第１引数値が保持されているアドレスが格納される。
【００８６】
実行結果リンクフィールド７１７は、リンク構造を用いて格納されている関数の実行結果のアドレスを格納するためのフィールドである。この実行結果リンクフィールド７１７には、検索要求入力部４２１により実行履歴が検索されて開始アドレスおよび入力値が一致したときに、実行結果として出力される関数の実行結果が保持されているアドレスが格納される。例えば、３つの変数を出力値とする関数の場合には、３つの変数のうち１番目の変数の値が保持されているアドレスが実行結果リンクフィールド７１７に格納される。
【００８７】
図６（ｂ）には、反復再利用区間の実行履歴であるループ個別履歴７２０のフィールド構成例が示されている。このループ個別履歴７２０は、識別子フィールド７２１と、開始アドレスフィールド７２２と、入力値リンクフィールド７２３と、ループカウンタ値フィールド７２４と、実行結果リンクフィールド７２７とから構成される。
【００８８】
識別子フィールド７２１は、図６（ａ）において示した識別子フィールド７１１と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するための識別子を格納するフィールドである。この識別子フィールド７２１には、ループ個別履歴であることを示す２ビット（０１）が格納される。また、この識別子フィールド７２１は、ループ個別履歴７２０における先頭のフィールドであり、例えば、そのループ個別履歴７２０の開始アドレスに保持されるフィールドである。
【００８９】
開始アドレスフィールド７２２は、ループの開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７２２に格納されるループの開始アドレスは、検索要求入力部４２１により実行履歴が検索される場合には、検索要求の開始アドレスと比較される。
【００９０】
入力値リンクフィールド７２３は、リンク構造を用いて格納されているループの入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７２３の機能は、図６（ａ）において示した入力値リンクフィールド７１３と同様のものであるので、ここでの詳細な説明を省略する。
【００９１】
ループカウンタ値フィールド７２４は、ループの何回目の実行による実行結果であるのかを示す値を格納するためのフィールドである。このループカウンタ値フィールド７２４には、検索要求入力部４２１により実行履歴が検索されて開始アドレスおよび入力値が一致したときに、検索要求のループカウンタ値と比較されるループカウンタ値が格納される。
【００９２】
実行結果リンクフィールド７２７は、リンク構造を用いて格納されているループの実行結果のアドレスを格納するフィールドである。この実行結果リンクフィールド７２７には、検索要求入力部４２１により実行履歴が検索されて開始アドレス、入力値、およびループカウンタ値が一致したときに、実行結果として出力されるループの実行結果が保持されているアドレスが格納される。
【００９３】
図６（ｃ）には、反復再利用区間の代表履歴であるループ代表履歴７３０のフィールド構成例が示されている。このループ代表履歴７３０は、識別子フィールド７３１と、開始アドレスフィールド７３２と、入力値リンクフィールド７３３と、退避カウントフィールド７３５と、退避履歴アドレスフィールド７３６とから構成される。
【００９４】
識別子フィールド７３１は、図６（ａ）において示した識別子フィールド７１１と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するためのフィールドである。この識別子フィールド７３１には、ループ代表履歴であることを示す２ビット（１０）が格納される。また、この識別子フィールド７３１は、ループ代表履歴７３０における先頭のフィールドであり、例えば、そのループ代表履歴７３０の開始アドレスに保持されるフィールドである。
【００９５】
開始アドレスフィールド７３２は、図６（ｂ）において示した開始アドレスフィールド７２２と同様に、ループの開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７３２の機能は、図６（ｂ）の開始アドレスフィールド７２２と同様のものであるのでここでの詳細な説明を省略する。
【００９６】
入力値リンクフィールド７３３は、図６（ｂ）において示した入力値リンクフィールド７２３と同様に、リンク構造を用いて格納されているループの入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７３３の機能は、図６（ｂ）において示した入力値リンクフィールド７２３と同様のものであるのでここでの詳細な説明を省略する。
【００９７】
退避カウントフィールド７３５は、主記憶部１３０に退避された退避履歴の個数を示す値を格納するためのフィールドである。この退避カウントフィールド７３５には、実行履歴が検索されて検索要求の開始アドレスおよび入力値がループ代表履歴の開始アドレスおよび入力値と一致したときに、履歴復元部５２０に退避履歴位置情報として供給される退避履歴の個数が格納される。
【００９８】
退避履歴アドレスフィールド７３６は、退避履歴アドレスを格納するためのフィールドである。ここでいう退避履歴アドレスとは、主記憶部１３０に退避された退避履歴が格納されているアドレスである。この退避履歴アドレスフィールド７３６には、実行履歴が検索されて検索要求の開始アドレスおよび入力値が、ループ代表履歴の開始アドレスおよび入力値と一致したときに、履歴復元部５２０に退避履歴位置情報として供給される退避履歴アドレスが格納される。例えば、この退避履歴アドレスフィールド７３６には、反復再利用区間の複数の退避履歴を連続したアドレスに保存した場合において、最初の退避履歴の開始アドレスが格納される。
【００９９】
図６（ｄ）には、反復再利用区間の退避履歴７４０のフィールド構成例が示されている。この退避履歴７４０は、ループカウンタ値フィールド７４４および実行結果リンクフィールド７４７から構成される。
【０１００】
ループカウンタ値フィールド７４４は、図６（ｂ）において示したループカウンタ値フィールド７２４と同様に、ループの何回目の実行による実行結果であるのかを示す値を格納するためのフィールドである。このループカウンタ値フィールド７４４には、履歴復元部５２０によりループ個別履歴が復元されるときに、ループカウンタ値フィールド７２４となる値が格納される。
【０１０１】
実行結果リンクフィールド７４７は、図６（ｂ）において示した実行結果リンクフィールド７２７と同様に、リンク構造を用いて格納されているループの実行結果のアドレスを格納するフィールドである。この実行結果リンクフィールド７４７には、履歴復元部５２０によりループ個別履歴が復元されるときに、実行結果リンクフィールド７２７となる値が格納される。
【０１０２】
なお、ここでは、実行履歴およびループ代表履歴のデータ長を固定長にして履歴メモリ４３０における実行履歴およびループ代表履歴の登録や消去を容易にするために、また、実行履歴のデータ量を少なくするために、入力値および実行結果をリンク構造にした。しかしながら、関数履歴、ループ個別履歴、ループ代表履歴および退避履歴のデータ構造はこれに限定されるものではない。例えば、入力値および実行結果をリンク構造にしないで、関数履歴、ループ個別履歴、ループ代表履歴および退避履歴にそのまま保持させるようにしてもよい。
【０１０３】
［入力値リンクおよび実行結果リンクのデータ構造例］
図７は、本発明の実施の形態における入力値リンクおよび実行結果リンクのデータ構造例を示す概念図である。
【０１０４】
ここでは、図６（ａ）において示した入力値リンクフィールド７１３と、入力値を格納する入力値格納領域７６０のデータ構造とが示されている。この例では、３つの引数が入力値である関数を想定する。また、ここでは、入力値格納領域７６０は、関数履歴、ループ個別履歴およびループ個別履歴が保存される領域とは異なる履歴メモリ４３０の領域であることとする。
【０１０５】
入力値格納領域７６０は、関数履歴およびループ個別履歴の入力値を保持する領域である。この入力値格納領域７６０には、３つの引数として、第１引数値７６１、第２引数値７６３および第３引数値７６５が左側のカラムに示されている。そして、この入力値格納領域７６０の右側のカラムには、その３つの引数とともに保存されるリンクアドレス７６２、７６４および７６６が示されている。
【０１０６】
第１引数値７６１、第２引数値７６３および第３引数値７６５は、入力値リンクフィールド７１３が指定する入力値である３つの引数の引数値がそれぞれ保持される領域である。すなわち、第１引数値７６１には、第１番目とされた引数の引数値が保持され、第２引数値７６３には、第２番目とされた引数の引数値が保持され、第３引数値７６５には、第３番目とされた引数の引数値が保持される。例えば、第１引数値７６１には関数再利用区間において１番最初に使用された引数が保持され、第２引数値７６３には２番目に使用された引数が保持され、第３引数値７６５には３番目に使用された引数が保持される。また、第１引数値７６１のアドレスは、入力値リンクフィールド７１３に格納されるアドレスである。
【０１０７】
リンクアドレス７６２、リンクアドレス７６４およびリンクアドレス７６６は、第１引数値７６１、第２引数値７６３および第３引数値７６５にそれぞれ連結して保存され、次の引数のアドレスを格納する領域である。例えば、第１引数値７６１に連結して保存されるリンクアドレス７６２は、第２引数値７６３のアドレスを格納する。また、リンクアドレス７６２、リンクアドレス７６４およびリンクアドレス７６６は、次の引数が無い場合には、リンク先が無いことを示す「０」が格納される。例えば、第３引数値７６５に連結して保存されるリンクアドレス７６６は、第４番目の引数が無いため「０」が格納される。
【０１０８】
このように、入力値格納領域７６０には、実行履歴の入力値が引数毎に次の引数の保存場所を指定するリンクアドレスが保持される。実行履歴の検索のときには、検索要求の開始アドレスと関数履歴７１０の開始アドレスが一致した場合に入力値リンクフィールド７１３が参照されて、第１引数値７６１から順に引数毎に検索要求の入力値の引数と比較される。そして、第３引数値７６５まで一致するとリンクアドレス７６６の「０」により検索を終了し、実行結果の出力過程に移行する。
【０１０９】
このように、本発明の実施の形態では、実行履歴の入力値をリンク構造で保存することにより、記憶領域の無駄な領域を減少させて効率よく入力値を保持させることができる。なお、入力値リンクフィールド７２３および入力値リンクフィールド７３３に関しては、入力値リンクフィールド７１３と同様にリンク構造を用いて入力値が保存されるため説明を省略する。また、実行結果リンクフィールド７１７、実行結果リンクフィールド７２７および実行結果リンクフィールド７４７に関しても、入力値リンクフィールド７１３と同様にリンク構造を用いて実行結果が保存されるためｈ説明を省略する。
【０１１０】
なお、ここでは、３つの引数が入力値である関数を想定したが、引数の値が最大３つに限定されるものではない。リンクを繋げることで３つ以上の引数および変数に対応することができる。また、ここでは、入力値格納領域７６０は、検索を高速にするために履歴メモリ４３０における領域であることを想定したが、これに限定されるものではない。例えば、主記憶部１３０に入力値格納領域７６０を確保することにより、より多くの実行履歴およびループ個別履歴を履歴メモリ４３０に保持させることができる。
【０１１１】
＜３．履歴メモリに保持される履歴情報および主記憶部に保持される退避履歴の一例＞
［ループ個別履歴の退避の具体例］
図８は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。ここでは、履歴メモリ４３０における関数履歴、ループ個別履歴およびループ代表履歴を登録する領域は、データ量と無関係に１０個の履歴が格納できる容量であることを想定する。さらにここでは、主記憶部１３０における退避履歴を保持させる領域は、データ量と無関係に６個の退避履歴を退避できる容量であることとする。また、これ以降の説明では、便宜上、関数再利用区間の実行履歴である関数履歴、反復再利用区間の実行履歴であるループ個別履歴、および、反復再利用区間の代表履歴であるループ代表履歴の３つの履歴を履歴情報と表現することとする。
【０１１２】
図８（ａ）は、履歴制御部５１０が動作する前の履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の一例である。ここには、実行履歴表８１１および退避履歴表８１２が示されている。
【０１１３】
実行履歴表８１１は、履歴メモリ４３０に登録されている履歴情報を表すものである。この実行履歴表８１１における左側のカラムには、履歴メモリ４３０に登録された順序を示す順位が「１」から「１０」まで順に例示されている。この順位は、数値が小さいものほど先に履歴メモリ４３０に登録されたことを示すものとする。
【０１１４】
実行履歴表８１１における右側のカラムには、履歴メモリ４３０に登録されている履歴情報が示されている。ここには、図６（ａ）乃至（ｄ）において示した識別子と、その履歴情報の基となった関数またはループとが示されている。また、ループ個別履歴の場合には、そのループ個別履歴が反復された実行において何回目の実行であるのかを示す値がさらに示されている。
【０１１５】
例えば、順位が「１」の履歴情報（００（ｆｕｎｃＡ））は、関数Ａ（ｆｕｎｃＡ）の関数履歴（００）を示している。また、「７」の順位の履歴情報（０１（ｌｏｏｐＦ（１）））は、ループＦ（ｌｏｏｐＦ）の１回目（１）の実行に関するループ個別履歴（０１）を示している。また、「８」の順位の履歴情報（０１（ｌｏｏｐＦ（２）））は、反復して実行されたループＦ（ｌｏｏｐＦ）の２回目（２）の実行に関するループ個別履歴（０１）を示している。
【０１１６】
退避履歴表８１２は、主記憶部１３０に退避された退避履歴を表すものである。この退避履歴表８１２における順位には、主記憶部１３０に登録された順序を示す順位が示されており、ここでは、「１」から「６」までの順位が例示されている。この順位は、数値が少ないものほど古く、早い時点で登録されたことを意味している。
【０１１７】
退避履歴表８１２における退避履歴には、主記憶部１３０に退避された退避履歴が示されている。ここでは、主記憶部１３０に退避履歴は１つも退避されていないことが示されている。
【０１１８】
この様な場合において、履歴制御部５１０は、履歴メモリ４３０に新たな実行履歴を登録する空き容量が無いことを検出すると、履歴メモリ４３０から反復して実行された反復再利用区間のループ個別履歴の退避を開始する。
【０１１９】
図８（ｂ）は、履歴制御部５１０が動作した後の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８２１および退避履歴表８２２が示されている。
【０１２０】
実行履歴表８２１は、図８（ａ）で示した実行履歴表８１１におけるループ個別履歴が退避された後の履歴メモリ４３０における履歴情報を表すものである。
【０１２１】
実行履歴表８２１では、実行履歴表８１１の「７」の順位のループ個別履歴（０１（ｌｏｏｐＦ（１））と、「８」の順位のループ個別履歴（０１（ｌｏｏｐＦ（２））と、「９」の順位のループ個別履歴（０１（ｌｏｏｐＦ（３））とが削除されている。そして、その３つのループ個別履歴の代わりとして、ループ代表履歴（１０（ｌｏｏｐＦ））が「７」の順位に示されている。
【０１２２】
また、その３つのループ個別履歴がループ代表履歴（１０（ｌｏｏｐＦ））に代わったことにより、図８（ａ）の実行履歴表８１１における「１０」の順位で示した関数Ｂの関数履歴（００（ｆｕｎｃＢ））の順位が「８」に繰り上げられている。そして、実行履歴表８２１における順位が「９」乃至「１０」の実行履歴は存在しないことを意味する。
【０１２３】
退避履歴表８２２は、履歴制御部５１０が動作した後の主記憶部１３０に退避された退避履歴を表すものである。
【０１２４】
この退避履歴表８２２の「１」の順位には、実行履歴表８１１の「７」の順位のループ個別履歴（０１（ｌｏｏｐＦ（１）））に基づいて生成された、反復して実行されたループＦの１回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（１））が示されている。「２」の順位には、実行履歴表８１１の「８」の順位において示したループ個別履歴（０１（ｌｏｏｐＦ（２）））に基づいて生成された、反復して実行されたループＦの２回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（２））が示されている。
【０１２５】
そして、「３」の順位には、実行履歴表８１１の「９」の順位において示したループ個別履歴（０１（ｌｏｏｐＦ（３）））に基づいて生成された、反復されたループＦの３回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（３））が示されている。
【０１２６】
このように、本発明の実施の形態では、履歴制御部５１０を設けることによって、反復して実行されるループのループ個別履歴の実行結果を主記憶部１３０に退避させることができる。
【０１２７】
［ループ個別履歴の復元の具体例］
図９は、本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。ここでは、履歴メモリ４３０および主記憶部１３０は、図８において示した履歴メモリ４３０および主記憶部１３０と同様の機能であることを想定する。また、ここでは、空き容量が無い履歴メモリ４３０に新たな実行履歴を登録する場合には、前回の使用からの未使用期間が最も長い実行履歴を削除する（ＬＲＵ：Least Recently Used）ことにより空き容量を確保することとする。さらに、ここでは、実行履歴は登録されてから一度も使用されていないことを想定し、ＬＲＵにより削除される実行履歴は、順序が最も若い実行履歴であることとする。
【０１２８】
図９（ａ）は、退避履歴に基づいてループ個別履歴が復元される前の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８３１および退避履歴表８３２が示されている。
【０１２９】
実行履歴表８３１は、履歴復元部５２０がループ個別履歴を復元する前の履歴メモリ４３０に登録されている履歴情報を示すものである。この実行履歴表８３１には、図８（ｂ）において示した実行履歴表８２１の空き容量に新たな実行履歴が格納された状態が示されている。この新たな実行履歴として、「９」の順位には関数Ｃの関数履歴００（ｆｕｎｃＣ）が登録され、「１０」の順位には関数Ｄの関数履歴００（ｆｕｎｃＤ）が格納されている。
【０１３０】
退避履歴表８３２は、図８（ｂ）において示した退避履歴表８２２と同様に、主記憶部１３０に退避された退避履歴を表すものである。
【０１３１】
この様な場合において、履歴検索部４２０により履歴メモリ４３０からループＦに関するループ代表履歴が検索されると、履歴復元部５２０は退避履歴からループ個別履歴の復元を開始する。
【０１３２】
図９（ｂ）は、履歴復元部５２０により退避履歴からループ個別履歴が復元された後の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８４１および退避履歴表８４２が示されている。
【０１３３】
実行履歴表８４１は、履歴復元部５２０がループ個別履歴を復元した後の履歴メモリ４３０に登録されている履歴情報を示すものである。この実行履歴表８４１には、図９（ａ）で示した退避履歴表８３２の退避履歴からループ個別履歴が復元されて実行履歴表８３１の実行履歴に加えられた状態が示されている。
【０１３４】
この実行履歴表８４１では、実行履歴表８３１における順位「１」および「２」に対応する実行履歴００（ｆｕｎｃＡ）および０１（ｌｏｏｐＡ（１））が消去されて、「３」乃至「６」の実行履歴の順序が「１」乃至「４」に繰り上がっている。
【０１３５】
そして、「５」の順位では、退避履歴表８３２の「１」の順位の退避履歴（ｌｏｏｐＦ（１））の基となった実行履歴０１（ｌｏｏｐＦ（１））が復元されて登録されている。「６」および「７」の順位でも「５」と同様に、実行履歴０１（ｌｏｏｐＦ（２））および０１（ｌｏｏｐＦ（３））が復元されて登録されている。
【０１３６】
退避履歴表８４２は、ループ個別履歴が復元された後の主記憶部１３０に登録された退避履歴を示すものである。この退避履歴表８４２には、退避履歴表８３２において示した退避履歴は全て復元されて主記憶部１３０から削除され、退避履歴は１つも退避されていないことが示されている。
【０１３７】
このように、本発明の実施の形態では、履歴復元部５２０を設けることによって、主記憶部１３０に退避履歴として退避されたループ個別履歴を履歴メモリ４３０に復元することができる。
【０１３８】
［本発明の実施の形態における新たな実行履歴の登録例］
図１０は、本発明の実施の形態における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示す図である。ここでは、履歴メモリ４３０は、データ量と無関係に１２個の履歴情報が登録できる容量であることを想定する。
【０１３９】
また、ここでは、空き容量が無い履歴メモリ４３０に新たな実行履歴を登録したい場合には、前回の使用からの未使用期間が最も長い実行履歴を削除する（ＬＲＵ）ことができることとする。さらにここでは、実行履歴は登録されてから一度も使用されていないことを想定し、ＬＲＵにより削除される実行履歴は、履歴メモリ４３０に最も早くに登録された実行履歴であることとする。
【０１４０】
図１０（ａ）は、新たに登録される実行履歴を示した模式図である。ここには、新たに登録される実行履歴が登録履歴表８６１に示されている。なお、図１０では、登録履歴表８６１に記されている実行履歴のうち、上方に記されている実行履歴から順に履歴メモリ４３０に登録されることを想定する。
【０１４１】
図１０（ｂ）は、従来技術を用いたデータ処理装置１００における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示したものである。ここには、実行履歴表８７１と、実行履歴表８７２と、消去履歴表８７３とが示されている。
【０１４２】
実行履歴表８７１は、登録履歴表８６１において示した新たな実行履歴が登録される前の履歴メモリ４３０における実行履歴を表したものである。また、この実行履歴表８７１では、上方に記されている実行履歴から順に履歴メモリ４３０に登録されたことを想定する。
【０１４３】
実行履歴表８７２は、登録履歴表８６１において示した新たな実行履歴が登録された後の履歴メモリ４３０における実行履歴を示すものである。この実行履歴表８７２には、実行履歴表８７１の実行履歴に登録履歴表８６１で示した新たな実行履歴が登録された状態が示されている。
【０１４４】
この実行履歴表８７２では、実行履歴表８７１における上から１番目乃至５番目（００（ｆｕｎｃＥ）、０１（ｌｏｏｐＢ（１））乃至０１（ｌｏｏｐＢ（４））の実行履歴が消去されている。そして、実行履歴表８７１における上から６番目乃至１２番目の実行履歴が、実行履歴表８７２の１番目乃至７番目に示されている。さらに、この実行履歴表８７２では、登録履歴表８６１で示した新たな実行履歴が８番目乃至１２番目に示されている。
【０１４５】
消去履歴表８７３は、登録履歴表８６１で示した新たな実行履歴の登録により履歴メモリ４３０から消去された実行履歴を表したものである。この消去履歴表８７３では、実行履歴表８７１における上から１番目乃至５番目の実行履歴が示されている。
【０１４６】
このように、従来技術を用いたデータ処理装置１００では、履歴制御部５１０を備えていないため、実行履歴の実行結果を主記憶部１３０に退避させることができない。これにより、新たな実行履歴を履歴メモリ４３０に登録する場合には、前回の使用から最も未使用期間が長い実行履歴を履歴メモリ４３０から削除して、その代わりに新たな実行履歴を登録しなければならない。
【０１４７】
図１０（ｃ）は、本発明の実施の形態におけるデータ処理装置１００において新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示したものである。ここには、実行履歴表８８１と、退避履歴表８８２と、実行履歴表８８３と、退避履歴表８８４とが示されている。ここでは、主記憶部１３０の退避履歴を退避させる領域は、データ量と無関係に８個の退避履歴が退避できる容量であることを想定する。
【０１４８】
実行履歴表８８１は、登録履歴表８６１において示した新たな実行履歴が登録される前の履歴メモリ４３０における実行履歴を表したものである。この実行履歴表８８１は、図１０（ｂ）の実行履歴表８７１と同様のものを示しているため、詳細な説明を省略する。
【０１４９】
退避履歴表８８２は、登録履歴表８６１において示した新たな実行履歴が登録される前の主記憶部１３０における退避履歴を表したものである。この退避履歴表８８２では、主記憶部１３０に退避履歴は１つも退避されていないことが示されている。
【０１５０】
実行履歴表８８３は、登録履歴表８６１において示した新たな実行履歴が登録された後の履歴メモリ４３０における履歴情報を示すものである。この実行履歴表８８３には、実行履歴表８８１の実行履歴に登録履歴表８６１で示した新たな実行履歴が登録された状態が示されている。
【０１５１】
この実行履歴表８８３では、実行履歴表８８１における上から２番目乃至５番目のループＢのループ個別履歴（０１（ｌｏｏｐＢ（１））乃至０１（ｌｏｏｐＢ（４））が履歴メモリ４３０から削除されている。そして、その削除されたループＢのループ個別履歴の代わりに、ループ代表履歴（１０（ｌｏｏｐＢ））が実行履歴表８８３における上から２番目に示されている。また、実行履歴表８８１における上から６番目乃至９番目の実行履歴が、この実行履歴表８８３では３番目乃至６番目に示されている。
【０１５２】
さらに、この実行履歴表８８３では、実行履歴表８８１における上から１０番目乃至１２番目のループＣのループ個別履歴（０１（ｌｏｏｐＣ（１））乃至０１（ｌｏｏｐＣ（３））が履歴メモリ４３０から削除されている。そして、その削除されたループＣのループ個別履歴の代わりに、ループ代表履歴（１０（ｌｏｏｐＣ））が上から７番目に示されている。そして、この実行履歴表８８３では、登録履歴表８６１で示した新たな実行履歴が、８番目乃至１２番目に記されている。
【０１５３】
退避履歴表８８４は、登録履歴表８６１において示した新たな実行履歴が登録された後の主記憶部１３０における退避履歴を示すものである。この退避履歴表８８４では、上から１番目乃至４番目にループＢに関する退避履歴（ｌｏｏｐＢ（１）乃至ｌｏｏｐＢ（４））が示されている。さらに、ここでは、上から５番目乃至７番目にループＣに関する退避履歴（ｌｏｏｐＣ（１）乃至ｌｏｏｐＣ（３））が示されている。
【０１５４】
このように、本発明の実施の形態におけるデータ処理装置１００では、履歴制御部５１０を備えているため、退避履歴を主記憶部１３０に退避させ、退避履歴の基となったループ個別履歴の代わりにループ代表履歴を履歴メモリ４３０に登録することができる。これにより、新たな実行履歴を履歴メモリ４３０に登録する場合には、ループ個別履歴に基づいて退避履歴を退避させ、そしてループ個別履歴をループ代表履歴に置き換えることで履歴メモリ４３０空き容量を生成することができる。すなわち、本発明の実施の形態によれば、従来技術を用いたデータ処理装置１００と比較して履歴メモリ４３０に保持される実行履歴の数を増やすことができる。
【０１５５】
＜４．データ処理装置の処理手順例＞
［本発明の実施の形態における履歴制御部５１０の動作例］
次に、本発明の実施の形態における履歴制御部５１０の処理について図面を参照して説明する。
【０１５６】
図１１は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避処理の処理手順例を示すフローチャートである。なお、ここでは、関数履歴と、ループ個別履歴と、ループ代表履歴と、退避履歴とは、それぞれ固定長のデータであることを想定する。また、ここでは、履歴メモリ４３０では、関数履歴と、ループ個別履歴と、ループ代表履歴とは連続するアドレスに登録された順に格納されるものとする。さらに、主記憶部１３０では、退避履歴は連続するアドレスに退避された順に格納されるものとする。
【０１５７】
まず、先頭探索部６１０において、探索アドレス（ｒａｄｒ）が「０」に設定される（ステップＳ９１１）。これにより、履歴メモリ４３０の履歴情報が登録される領域の先頭のデータから退避履歴の探索が開始されるようになる。
【０１５８】
次に、先頭探索部６１０において、探索アドレス（ｒａｄｒ）から識別子が読み出される（ステップＳ９１２）。そして、読み出された識別子が、ループ個別履歴を指し示す「０１」であるか否かが判断される（ステップＳ９１３）。そして、識別子が「０１」でないと判断された場合には、識別子が関数履歴を指し示す「００」であるか否かが判断される（ステップＳ９１４）。
【０１５９】
そして、識別子が「００」でないと判断された場合には、解析対象の履歴情報は識別子が「１０」のループ代表履歴であると判定される。続いて、ループ代表履歴のデータ長から算出されたループ代表履歴が保持されているアドレスの個数である代表履歴アドレス数（ｘ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１５）。これにより、探索アドレス（ｒａｄｒ）は、次に解析する履歴情報における識別子を指し示すアドレスとなる。
【０１６０】
一方、ステップＳ９１４の処理において、識別子が「００」であると判断された場合には、その識別子を示す履歴情報が関数履歴であると判定される。そして、関数履歴のデータ長から算出された関数履歴が保持されているアドレスの個数である関数履歴アドレス数（ｙ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１６）。
【０１６１】
一方、ステップＳ９１３の処理において、識別子が「０１」であると判断された場合には、その識別子を示す履歴情報がループ個別履歴であると判定される。そして、ループ個別履歴のデータ長から算出されたループ個別履歴が保持されているアドレスの個数である個別履歴アドレス数（ｚ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１７）。
【０１６２】
次に、連続探索部６２０において、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）が、ステップＳ９１３で検出されたループ個別履歴における反復再利用区間の開始アドレスに設定される（ステップＳ９１８）。さらに、退避履歴開始アドレス（ｍａｄｒ）が、退避領域管理部５３０から供給された最初の退避履歴を格納する開始アドレスである退避開始アドレスに設定される（ステップＳ９１９）。
【０１６３】
さらに、ループの回数をカウントするための連続カウンタ（ｒｃｎｔ）が「１」に設定される（ステップＳ９２０）。また、ループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）が、ステップＳ９１３で検出されたループ個別履歴の開始アドレスに設定される（ステップＳ９２１）。このステップＳ９１８乃至Ｓ９２１の一連の処理により、ステップＳ９３０における処理の準備が完了する。
【０１６４】
そして、ステップＳ９１３で検出されたループ個別履歴が、反復される反復再利用区間の１番目の実行結果なのか否かが判断され、反復されている場合にはループ個別履歴の実行結果を主記憶部１３０に退避される実行結果退避処理が行われる（ステップＳ９３０）。
【０１６５】
ステップＳ９１５、Ｓ９１６およびＳ９３０の後に、探索アドレス（ｒａｄｒ）が履歴メモリ４３０の使用領域最終アドレスを超えたか否かが判断される（ステップＳ９２３）。ここでいう使用領域最終アドレスは、履歴メモリ４３０の履歴情報が登録される領域において、連続するアドレスに登録された順に格納された履歴情報のうち最後に登録された履歴情報が記録されている最後のアドレスである。
【０１６６】
そして、探索アドレス（ｒａｄｒ）が、使用領域の最終アドレスを超えていない場合には、ステップＳ９１２に戻り処理が繰り返される。一方、最終アドレスを超えている場合には、ループ個別履歴の退避処理は終了する。
【０１６７】
図１２は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の実行結果退避処理（ステップＳ９３０）の処理手順例を示すフローチャートである。
【０１６８】
まず、連続探索部６２０において、探索アドレス（ｒａｄｒ）が履歴メモリ４３０の使用領域最終アドレスを超えたか否かが判断される（ステップＳ９３１）。そして、探索アドレス（ｒａｄｒ）が使用領域の最終アドレスを超えていない場合には、探索アドレス（ｒａｄｒ）から識別子が読み出される（ステップＳ９３２）。続いて、読み出された識別子が、ループ個別履歴を指し示す「０１」であるか否かが判断される（ステップＳ９３３）。そして、識別子が「０１」でないと判断された場合には、ステップＳ９３８に進む。
【０１６９】
一方、識別子が「０１」であると判断された場合には、そのループ個別履歴に含まれる開始アドレスと、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）とが同一であるか否かが判断される（ステップＳ９３４）。そして、開始アドレスが同一でないと判断された場合には、ステップＳ９３８に進む。
【０１７０】
一方、開始アドレスが同一である場合には、ループ個別履歴のループカウンタ値が、連続カウンタ（ｒｃｎｔ）に「１」を加算した値（ｒｃｎｔ＋１）と同じ値であるか否かが判断される（ステップＳ９３５）。そして、ループカウンタ値と「ｒｃｎｔ＋１」とが同一でないと判断された場合には、ステップＳ９３８に進む。
【０１７１】
これらステップＳ９３４およびステップＳ９３５により、ステップＳ９３３で検出されたループ個別履歴は、図１１のステップＳ９１３において検出されたループ個別履歴を１回目のループとするループ個別履歴であるか否かが判定される。
【０１７２】
例えば、ステップＳ９３４において、ループ個別履歴に含まれる開始アドレスと、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）とが異なる場合には、異なる反復再利用区間のループ個別履歴が連続していると判断される。
【０１７３】
また、ステップＳ９３５において、ループ個別履歴に含まれるループカウンタ値が「ｒｃｎｔ＋１」とは異なっている場合には、同じ反復再利用区間が反復ではなく新たに１回目から実行されたと判断される。このステップＳ９３５の一例として、ループカウンタ値が「１」であり、「ｒｃｎｔ＋１」が「５」である場合を説明する。この場合には、図１１のステップＳ９１３で検出されたループ個別履歴の開始アドレスが指し示す反復再利用区間は、反復されて５回実行された後に、ステップＳ９３３で検出されたループ個別履歴の基となった実行から新たな反復になったと判断される。
【０１７４】
一方、ステップＳ９３５において、ループカウンタ値と「ｒｃｎｔ＋１」とが同一であると判断された場合には、連続カウンタ（ｒｃｎｔ）に「１」が加算される（ステップＳ９３６）。そして、（個別履歴アドレス数（ｙ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９３７）。その後、ステップＳ９３７の処理が終わると、ステップＳ９３１に戻り処理が繰り返される。
【０１７５】
一方、ステップＳ９３１において、探索アドレス（ｒａｄｒ）が使用領域最終アドレスよりも大きな値のアドレスであると判断された場合には、連続カウンタ（ｒｃｎｔ）の値が「１」より大きいか否かが判断される（ステップＳ９３８）。これにより、図１１のステップＳ９１３で検出されたループ個別履歴は、反復された実行の一回目のループ個別履歴なのか、単独の実行のループ個別履歴なのかが判断される。そして、連続カウンタ（ｒｃｎｔ）の値が「１」以下であると判断された場合には、図１１のステップＳ９１３で検出されたループ個別履歴は単独の実行のループ個別履歴と判定し、実行結果退避処理を終了する。
【０１７６】
一方、連続カウンタ（ｒｃｎｔ）の値が「１」より大きいと判断された場合には、ループ個別履歴が履歴メモリ４３０から取得される（ステップＳ９３９）。このステップＳ９３９では、ループ個別履歴取得部６３０により、ループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）を最初のループ個別履歴の登録開始始点として連続カウンタ（ｒｃｎｔ）個のループ個別履歴が履歴メモリ４３０から取得される。
【０１７７】
続いて、退避履歴転送部６４０により、ループ個別履歴に基づいて退避履歴が生成され、その生成された退避履歴が主記憶部１３０に退避履歴開始アドレス（ｍａｄｒ）を始点として記憶される（ステップＳ９４０）。なお、ステップＳ９４０は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１７８】
次に、ループ個別履歴消去部５１２により、退避履歴の基となったループ個別履歴が履歴メモリから消去される（ステップＳ９４１）。なお、ステップＳ９４１は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１７９】
そして、ループ代表履歴登録部５１３により、ループ代表履歴がループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）に基づいて履歴メモリ４３０に登録される（ステップＳ９４２）。そして、実行結果退避処理は終了する。なお、ステップＳ９４２は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１８０】
このように、本発明の実施の形態では、反復再利用区間のループ個別履歴のうち反復された実行に関するループ個別履歴のみを主記憶部１３０に退避させることができる。
【０１８１】
［本発明の実施の形態における履歴復元部５２０の動作例］
次に、本発明の実施の形態における履歴復元部５２０の処理について図面を参照して説明する。
【０１８２】
図１３は、本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元処理の処理手順例を示すフローチャートである。なお、ここでは、図１１および図１２と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴と、退避履歴とは、それぞれ固定長のデータであることを想定する。また、ここでは、図１１および図１２と同様に、履歴メモリ４３０では、関数履歴と、ループ個別履歴と、ループ代表履歴とは連続するアドレスに登録された順に格納されるものとする。さらに、主記憶部１３０では、退避履歴は連続するアドレスに退避された順に格納されるものとする。また、ここでは、プログラムの実行の開始をフローチャートの開始とし、プログラムの実行の終了をフローチャートの終了とする。
【０１８３】
まず、フェッチ部３１０およびレジスタファイル３４０に、関数を参照する命令およびその関数の入力値が読み出される（ステップＳ９５１）。次に、命令デコーダ３２０によって、関数を参照する命令がデコードされる（ステップＳ９５２）。続いて、解読（デコード）した命令が再利用命令か否かが判断される（ステップＳ９５３）。そして、デコードした命令が再利用命令でないと判断された場合には、実行部３３０によって、レジスタファイル３４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９５４）。なお、ステップＳ９５４は、特許請求の範囲に記載の実行手順の一例である。
【０１８４】
一方、ステップＳ９５３の処理において、命令が再利用命令であると解読された場合には、検索要求入力部４２１によって、再利用区間の開始アドレスおよび入力値を用いて履歴メモリ４３０に履歴情報があるか否かが判断される（ステップＳ９５５）。このとき、再利用区間が反復再利用区間である場合には、開始アドレスおよび入力値に加えてループカウンタ値も用いて履歴メモリ４３０に履歴情報があるか否か探索される。
【０１８５】
そして、履歴情報が履歴メモリ４３０にないと判断された場合には、履歴登録部４４０によって、実行結果登録処理が行われる（ステップＳ９７０）。これにより、履歴メモリ４３０に実行履歴が登録される。
【０１８６】
一方、履歴情報が履歴メモリ４３０にあると判断された場合には、実行結果出力部４２２および履歴復元部５２０によって、実行結果出力処理が行われる（ステップＳ９８０）。これにより、実行している再利用区間の実行結果が履歴メモリ４３０から出力される。
【０１８７】
そして、ステップＳ９５４、Ｓ９７０およびＳ９８０の処理の後に、実行結果がレジスタファイル３４０に書き戻される（ステップＳ９５６）。続いて、プログラムの実行が終了したか否かが判断される（ステップＳ９５７）。そして、プログラムの実行が終了していないと判断された場合には、ステップＳ９５１に戻り処理が繰り返される。
【０１８８】
一方、プログラムの実行が終了したと判断された場合には、履歴復元部５２０によるループ個別履歴の復元処理が終了される。
【０１８９】
図１４は、本発明の実施の形態における実行結果登録処理（ステップＳ９７０）の処理手順例を示すフローチャートである。
【０１９０】
まず、実行部３３０によって、レジスタファイル３４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９７１）。次に、履歴登録部４４０によって、出力された実行結果を含む実行履歴を登録するための空き容量が履歴メモリ４３０にあるか否かが判断される（ステップＳ９７２）。なお、ステップＳ９７１は、特許請求の範囲に記載の実行手順の一例である。
【０１９１】
そして、実行履歴を登録するための空き容量が履歴メモリ４３０にないと判断された場合には、消去部４６０によって、前回の使用からの未使用期間が最も長い実行履歴が履歴メモリ４３０から１つ削除される（ステップＳ９７３）。そして、ステップＳ９７２に戻り処理が繰り返される。
【０１９２】
一方、実行履歴を登録するための空き容量が履歴メモリ４３０にあると判断された場合には、履歴登録部４４０により実行履歴が履歴メモリ４３０に登録される（ステップＳ９７４）、実行結果登録処理は終了する。
【０１９３】
図１５は、本発明の実施の形態における実行結果出力処理（ステップＳ９８０）の処理手順例を示すフローチャートである。なお、ここでは、関数履歴の実行結果と、ループ個別履歴の実行結果と、ループ代表履歴の退避履歴位置情報とを検索出力情報と表現することとする。
【０１９４】
まず、実行結果出力部４２２において、履歴メモリ４３０から図１３のステップＳ９５５で検索された履歴情報の検索出力情報が取得される（ステップＳ９８１）。次に、取得された検索出力情報がループ代表履歴の退避履歴位置情報であるか否かが判断される（ステップＳ９８２）。そして、取得された検索出力情報がループ代表履歴の退避履歴位置情報でないと判断された場合には、ステップＳ９９０に進む。
【０１９５】
一方、取得された検索出力情報がループ代表履歴の退避履歴位置情報であると判断された場合には、退避履歴取得部５２１によって、退避履歴位置情報が指し示す退避履歴が主記憶部１３０から取得される（ステップＳ９８３）。続いて、ループ個別履歴生成部５２２によって、退避履歴およびループ代表履歴に基づいてループ個別履歴が復元される（ステップＳ９８４）。次に、登録領域確保部５２３によって、履歴メモリ４３０からループ代表履歴が消去される（ステップＳ９８５）。その後、登録領域確保部５２３によって、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にあるか否かが判断される（ステップＳ９８６）。そして、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にないと判断された場合には、登録領域確保部５２３によって、前回の使用からの未使用期間が最も長い実行履歴が履歴メモリ４３０から１個削除される（ステップＳ９８７）。そして、ステップＳ９８６に戻り、処理が繰り返される。
【０１９６】
一方、ステップＳ９８６の処理において、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にあると判断された場合には、ループ個別履歴登録部５２４によって、復元されたループ個別履歴が履歴メモリ４３０に登録される（ステップＳ９８８）。続いて、実行結果出力部４２２によって、復元されたループ個別履歴が検索される（ステップＳ９８９）。
【０１９７】
その後、検索された実行結果に基づいて実行結果が出力される（ステップＳ９９０）。そして、実行結果出力処理は終了する。
【０１９８】
このように、本発明の実施の形態では、主記憶部１３０に退避履歴として退避されたループ個別履歴を履歴メモリ４３０に復元して、その復元したループ個別履歴の実行結果を再利用することができる。
【０１９９】
これまでに示してきたように、本発明の実施の形態によれば、反復再利用区間のループ個別履歴の実行結果を主記憶部１３０に退避させることができる。これにより、実行結果を退避させない従来技術の場合と比べて履歴メモリ４３０に保持される履歴情報の数を増やすことができる。また、退避させた実行結果も実行結果の検索対象とすることができるため、その退避させた実行結果を用いて実行結果の再利用をすることができる。
【０２００】
また、本発明の実施の形態によれば、従来技術によるデータ処理装置１００と比較して、履歴メモリ４３０から有効な実行履歴が削除されることによる値再利用の効率の低下を防止することができる。さらに、本発明の実施の形態によれば、従来技術と比較して少ない容量の履歴メモリ４３０でも同等の効果が生じるため、履歴メモリ４３０を大きい容量とすることに伴う実行履歴の検索時間の増加による値再利用の効率の低下を防止することができる。
【０２０１】
また、本発明の実施の形態は、従来技術と比べて履歴メモリ４３０に保持される履歴情報の数を増やすことができるため、プログラムの投機実行などの場合において、特に顕著な効果が得られると考えられる。
【０２０２】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２０３】
例えば、本発明の実施の形態においては、主記憶部１３０に退避された実行結果を再利用する際に、退避履歴からループ個別履歴を復元して履歴メモリ４３０に登録し、その登録されたループ個別履歴から実行結果を出力する例を説明した。しかしながら、これに限定されるものではなく、主記憶部１３０に退避された実行結果を再利用する際に、ループ履歴を復元しないで実行結果を再利用する場合も考えられる。
【０２０４】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０２０５】
１００ データ処理装置
１２０ バス
１３０ 主記憶部
２００ 一次キャッシュ
２１０ 命令キャッシュ
２２０ データキャッシュ
３００ プロセッサコア
３１０ フェッチ部
３２０ 命令デコーダ
３３０ 実行部
３４０ レジスタファイル
４００ 履歴管理部
４１０ 履歴対象データ保持部
４２０ 履歴検索部
４２１ 検索要求入力部
４２２ 実行結果出力部
４３０ 履歴メモリ
４４０ 履歴登録部
４５０ 履歴メモリ容量管理部
４６０ 消去部
５００ 履歴変換部
５１０ 履歴制御部
５１２ ループ個別履歴消去部
５１３ ループ代表履歴登録部
５２０ 履歴復元部
５２１ 退避履歴取得部
５２２ ループ個別履歴生成部
５２３ 登録領域確保部
５２４ ループ個別履歴登録部
５３０ 退避領域管理部
６００ 退避履歴生成部
６１０ 先頭探索部
６２０ 連続探索部
６３０ ループ個別履歴取得部
６４０ 退避履歴転送部
６５０ ループ代表履歴生成部
【技術分野】
【０００１】
本発明は、データ処理装置に関し、特に実行結果が再利用される命令区間を実行するデータ処理装置、履歴保存装置、および、これらにおける処理方法ならびに当該方法をコンピュータに実行させるプログラムに関する。
【背景技術】
【０００２】
プログラムの処理速度を高速化するために種々の技術が開発されている。近年、その技術を用いた装置の一つとして、値再利用（メモ化：Memoization）と呼ばれる命令区間の実行結果を再利用する技法を用いた区間再利用装置が提案されている（例えば、特許文献１参照。）。この区間再利用装置は、プログラムの所定の命令区間における入力値および実行結果を保存しておくことによって、同じ命令区間を再び実行する際に入力値が一致する場合には、保存していた実行結果である出力値を出力する装置である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００４−２５８９０５号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記の従来技術では、同じ命令区間を再び実行して実行結果を出力する際に、それ以前に保存していた実行結果を出力することによって、その命令区間の実行時間を削減することができる。
【０００５】
しかしながら、このような区間再利用装置では、実行結果を保存しておくメモリが満杯の場合には新たな実行履歴を登録するために古い実行結果を削除することから、その削除された実行結果の再利用ができないという問題が生じる。すなわち、このような区間再利用装置では、実行結果を保存しておくメモリから実行結果が削除されることに起因する値再利用の効率の低下が生じる場合が考えられる。
【０００６】
そこで、本発明はこのような状況に鑑みてなされたものであり、値再利用（メモ化）を行う際、実行結果を保存しておくメモリから実行結果を退避させることにより、値再利用の効率を改善することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、命令区間を実行して実行結果を出力する実行部と、上記命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、上記保持した実行結果が再び利用される場合には上記区間識別情報および上記入力値に基づいて上記実行履歴が検索される履歴メモリと、上記再利用区間のうち実行が反復される反復再利用区間の各回の上記実行結果を上記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と、上記反復再利用区間の上記実行履歴に基づいて上記退避履歴を上記退避履歴保持部に供給し、上記退避履歴の供給の際に上記退避履歴の基となった上記実行履歴を上記履歴メモリから消去して上記退避履歴を指し示す情報を含む代表履歴を上記履歴メモリに保持させる履歴制御部とを備えるデータ処理装置およびその処理方法ならびに当該方法をコンピュータに実行させるプログラムである。これにより、再利用区間の実行が反復される反復再利用区間の実行結果を履歴メモリから退避履歴保持部に退避させるという作用をもたらす。
【０００８】
また、この第１の側面において、上記履歴制御部は、上記履歴メモリに保持させる新たな上記実行履歴のデータ量が上記履歴メモリの空き容量よりも大きい場合には上記退避履歴を上記退避履歴保持部に供給するようにしてもよい。これにより、実行履歴のデータ量が履歴メモリの空き容量よりも大きい場合には、反復再利用区間の実行結果を履歴メモリから退避履歴保持部に退避させるという作用をもたらす。
【０００９】
また、この第１の側面において、上記退避履歴および上記代表履歴に基づいて上記実行履歴を上記履歴メモリに復元する履歴復元部と、上記区間識別情報および上記入力値に基づいて上記復元された上記実行履歴を上記履歴メモリから検索した場合には上記復元された上記実行履歴に基づいて上記実行結果を出力する履歴検索部とをさらに備えるようにしてもよい。これにより、退避履歴および代表履歴に基づいて復元した実行履歴を用いて実行結果を再利用させるという作用をもたらす。この場合において、上記履歴検索部は、上記区間識別情報および上記入力値に基づいて検索された上記実行履歴が上記代表履歴であった場合には上記復元部に上記実行履歴の復元を開始させるようにしてもよい。これにより、履歴検索部において代表履歴が検索された場合には、復元部に反復再利用区間の実行履歴を復元させるという作用をもたらす。この場合において、上記履歴制御部は、上記退避履歴の個数を示す退避カウントをさらに含む上記代表履歴を生成し、上記履歴復元部は、上記代表履歴における上記退避履歴を指し示す情報および上記退避カウントに基づいて上記退避履歴を上記退避履歴保持部から抽出して上記実行履歴を復元させるようにしてもよい。これにより、代表履歴における退避履歴を指し示す情報および退避カウントに基づいて退避履歴を退避履歴保持部から抽出させるという作用をもたらす。
【００１０】
また、この第１の側面において、上記実行部は、上記再利用区間の上記実行結果を供給する場合には上記反復再利用区間の上記実行履歴と上記反復再利用区間以外の上記実行履歴と上記代表履歴とを識別するための識別子をさらに出力し、上記履歴メモリは、上記識別子を上記実行履歴としてさらに保持し、上記履歴制御部は、上記識別子を用いて識別した上記実行履歴に基づいて上記退避履歴を供給し、上記識別子をさらに含む上記代表履歴を生成させるようにしてもよい。これにより、識別子を用いて実行履歴を識別させるという作用をもたらす。
【００１１】
また、この第１の側面において、上記反復再利用区間はサブルーチンであり、上記実行部は、上記サブルーチンの開始アドレスを上記区間識別情報として出力するようにしてもよい。これにより、サブルーチンの開始アドレスを区間識別情報として出力させるという作用をもたらす。
【００１２】
また、この第１の側面において、上記反復再利用区間はループであり、上記実行部は、上記ループの開始アドレスを上記区間識別情報として出力するようにしてもよい。これにより、ループの開始アドレスを上記区間識別情報として出力させるという作用をもたらす。この場合において、上記実行部は、上記反復再利用区間の上記実行結果を出力する場合には何回目の実行による上記実行結果であるかを示すカウンタ値をさらに出力し、上記履歴メモリは、上記カウンタ値を上記実行履歴としてさらに保持し、上記履歴制御部は、上記カウンタ値を含む上記退避履歴を出力するようにしてもよい。これにより、カウンタ値を含む実行履歴および退避履歴を保持させるという作用をもたらす。
【００１３】
また、本発明の第２の側面は、実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、上記保持した実行結果が再び利用される場合には上記区間識別情報および上記入力値に基づいて上記実行履歴が検索される履歴メモリと、上記再利用区間のうち実行が反復される反復再利用区間の各回の上記実行結果を退避履歴として上記履歴メモリから外部の記憶部に退避させ、上記退避の際に上記退避履歴の基となった上記実行履歴を上記履歴メモリから消去して上記退避履歴を指し示す情報を含む代表履歴を上記履歴メモリに保持させる履歴制御部とを備える履歴保存装置である。これにより、実行が反復される反復再利用区間の実行結果を履歴メモリから外部の記憶部に退避させるという作用をもたらす。
【発明の効果】
【００１４】
本発明によれば、値再利用（メモ化）を行う際、実行結果を保存しておくメモリから実行結果を退避させることにより、値再利用の効率を改善することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態におけるデータ処理装置１００の構成例を示すブロック図である。
【図２】本発明の実施の形態におけるプロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例を示すブロック図である。
【図３】本発明の実施の形態における履歴制御部５１０の構成例を示すブロック図である。
【図４】本発明の実施の形態における退避履歴生成部６００の構成例を示すブロック図である。
【図５】本発明の実施の形態における履歴復元部５２０の構成例を示すブロック図である。
【図６】本発明の実施の形態における関数履歴、ループ個別履歴、ループ代表履歴および退避履歴のデータ構造例を示す模式図である。
【図７】本発明の実施の形態における入力値リンクおよび実行結果リンクのデータ構造例を示す概念図である。
【図８】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。
【図９】本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。
【図１０】本発明の実施の形態における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示す図である。
【図１１】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避処理の処理手順例を示すフローチャートである。
【図１２】本発明の実施の形態における履歴制御部５１０によるループ個別履歴の連履歴探索退避処理（ステップＳ９３０）の処理手順例を示すフローチャートである。
【図１３】本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元処理の処理手順例を示すフローチャートである。
【図１４】本発明の実施の形態における実行結果登録処理（ステップＳ９７０）の処理手順例を示すフローチャートである。
【図１５】本発明の実施の形態における実行結果出力処理（ステップＳ９８０）の処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．データ処理装置の構成例（値再利用制御：反復再利用区間の実行履歴を退避する例）
２．履歴情報のフィールド構成例（値再利用制御：関数履歴、ループ個別履歴、ループ代表履歴および退避履歴の例）
３．履歴メモリに保持される履歴情報および主記憶部に保持される退避履歴の一例（値再利用制御：ループ個別履歴例を退避および復元させる例）
４．データ処理装置の処理手順例（値再利用制御：ループ個別履歴例を退避および復元させる例）
【００１７】
＜１．データ処理装置の構成例＞
［データ処理装置１００の構成例］
図１は、本発明の実施の形態におけるデータ処理装置１００の構成例を示すブロック図である。このデータ処理装置１００は、バス１２０を介して主記憶部１３０と相互に接続されている。また、ここでは、データ処理装置１００が処理を実行する命令区間は関数またはループであることを想定する。
【００１８】
データ処理装置１００は、プログラムにおける各処理を実行するものである。このデータ処理装置１００は、例えば、一般的なコンピュータにおいてはＣＰＵ（Central Processing Unit）により実現される。このデータ処理装置１００は、一次キャッシュ２００と、プロセッサコア３００と、履歴管理部４００と、履歴変換部５００とを備える。
【００１９】
一次キャッシュ２００は、プロセッサコア３００がバス１２０を介して扱う情報を一時的に保持するものである。この一次キャッシュ２００は、命令キャッシュ２１０およびデータキャッシュ２２０を備える。
【００２０】
命令キャッシュ２１０は、プロセッサコア３００において実行される命令を一時的に保持するものである。この命令キャッシュ２１０は、プロセッサコア３００が頻繁に実行する命令を一時的に保持することによって、プロセッサコア３００から主記憶部１３０へのアクセスを軽減させ、プロセッサコア３００におけるデータの入力待ち時間を軽減させることができる。この命令キャッシュ２１０は、主記憶部１３０から供給された再利用命令をプロセッサコア３００に供給する。ここにいう再利用命令とは、命令区間のうち実行結果が再び利用される再利用区間を再び利用されない区間と区別することによって、再利用区間が呼出された際に実行結果を再利用するための処理をデータ処理装置に行わせる命令である。
【００２１】
データキャッシュ２２０は、プロセッサコア３００の入力データおよび出力データを一時的に保持するものである。このデータキャッシュ２２０は、使用頻度の高いプロセッサコア３００の入力データを一時的に保持することによりプロセッサコア３００から主記憶部１３０へのアクセスを軽減させて、プロセッサコア３００におけるデータの入力待ち時間を軽減させる。このデータキャッシュ２２０は、主記憶部１３０から供給された関数またはループの入力値および開始アドレスをプロセッサコア３００に出力する。なお、ここで、入力値とは、関数またはループの実行に必要な値として渡される値の引数で構成される値であり、例えば、３つの変数を引数とする関数の場合には、この３つの変数の値およびその変数のアドレスである。
【００２２】
プロセッサコア３００は、プログラムの命令に従って演算を実行するものである。このプロセッサコア３００は、例えば、ＭＩＰＳ（Microprocessor without Interlocked Pipeline Stages）プロセッサにより実現される。プロセッサコア３００は、例えば、データキャッシュ２２０から供給される関数またはループの入力値および開始アドレスに基づいて、命令キャッシュ２１０から入力される関数またはループの区間における命令を実行し、その実行の結果を実行結果として出力する。このプロセッサコア３００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部４００から実行結果が供給されないときには、この命令を実行した結果である実行結果をデータキャッシュ２２０および履歴管理部４００に出力する。
【００２３】
また、プロセッサコア３００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部４００から実行結果が供給されたときには、再利用区間における処理を中止して、この再利用区間を呼び出したルーチンに戻って実行を継続する。
【００２４】
履歴管理部４００は、再利用区間の実行結果を保持して管理するものである。この履歴管理部４００は、プロセッサコア３００から供給された再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持する。ここでいう区間識別情報とは、再利用区間を特定するための情報であり、例えば、関数またはループの開始アドレスである。すなわち、この履歴管理部４００は、区間識別情報、入力値、および、実行結果として、関数またはループの開始アドレス、入力値、および、実行結果を保持する。また、この履歴管理部４００は、プロセッサコア３００から関数またはループの開始アドレスおよび入力値が供給された場合には、この開始アドレスおよび入力値が含まれる実行履歴を検索する。
【００２５】
履歴変換部５００は、履歴管理部４００により管理されている実行履歴を変換するものである。この履歴変換部５００は、履歴管理部４００に登録されている再利用区間のうち実行が反復される反復再利用区間の実行履歴を、主記憶部１３０において保持される退避履歴に変換する。ここで、退避履歴とは、反復再利用区間の実行履歴の実行結果を主記憶部１３０に退避させるためのデータである。また、この履歴変換部５００は、主記憶部１３０において保持された退避履歴に基づいて実行履歴を復元する。この履歴変換部５００は、その退避履歴を主記憶部１３０に保持させ、退避履歴を生成する基となった実行履歴を履歴管理部４００から消去し、退避履歴を指し示す情報を保持する代表履歴を履歴管理部４００に登録する。
【００２６】
また、この履歴変換部５００は、その退避履歴に含まれる実行結果を再利用する場合には、退避履歴から実行履歴を復元するとともに代表履歴を消去し、履歴管理部４００に復元した実行履歴を登録する。
【００２７】
バス１２０は、データ処理装置１００の各部と主記憶部１３０との間を相互に接続するバスである。
【００２８】
主記憶部１３０は、データ処理装置１００が動作するために必要なデータを保持するものである。この主記憶部１３０は、履歴変換部５００から供給された退避履歴を保持する。また、この主記憶部１３０は、データ処理装置１００に処理を実行させるためのプログラムを記憶する。この主記憶部１３０は、例えば、ＲＡＭ（Random Access Memory）などが考えられる。この主記憶部１３０は、記憶しているデータを、バス１２０を介してデータ処理装置１００に出力する。なお、主記憶部１３０は、特許請求の範囲に記載の退避履歴保持部の一例である。
【００２９】
［プロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例］
図２は、本発明の実施の形態におけるプロセッサコア３００と履歴管理部４００と履歴変換部５００との構成例を示すブロック図である。ここでは、プロセッサコア３００と履歴管理部４００と履歴変換部５００とに加えて、バス１２０を介して履歴変換部５００と接続される主記憶部１３０も示されている。ここでは、プロセッサコア３００と履歴管理部４００と履歴変換部５００と主記憶部１３０との機能は、図１と同様のものであるため、同一の符号を付してここでの詳細な説明を省略する。
【００３０】
また、これ以降の説明では、便宜上、繰り返し実行される区間である反復再利用区間はループであり、反復再利用区間以外の再利用区間は関数であることを想定する。この反復再利用区間以外の再利用区間は、関数再利用区間と表現することとする。そして、ループの実行結果をループ個別履歴と表現し、関数の実行結果を関数履歴と表現することとする。さらに、退避履歴を指し示す代表履歴は、ループ代表履歴と表現する。
【００３１】
プロセッサコア３００は、フェッチ部３１０と、命令デコーダ３２０と、実行部３３０と、レジスタファイル３４０とを備える。
【００３２】
フェッチ部３１０は、命令キャッシュ２１０または主記憶部１３０からの命令を読み出すものである。このフェッチ部３１０は、その読み出した命令を一時的に保持して、その保持されている命令のうち、実行部３３０に実行させるための命令を命令デコーダ３２０に供給する。このフェッチ部３１０は、例えば、一時的に保持している命令のうち、実行部３３０において実行される再利用命令を命令デコーダ３２０に供給する。このフェッチ部３１０は、例えば、主記憶部１３０に記憶された再利用命令を命令デコーダ３２０に供給する。
【００３３】
命令デコーダ３２０は、フェッチ部３１０から供給された命令を解読（デコード）することによって、プロセッサコア３００における構成部位を制御する制御信号を生成するものである。この命令デコーダ３２０は、例えば、命令を解読することによって実行部３３０およびレジスタファイル３４０を制御する制御信号を生成して、その生成された制御信号を実行部３３０およびレジスタファイル３４０に供給する。
【００３４】
この命令デコーダ３２０は、フェッチ部３１０から再利用命令が供給された場合には、その再利用命令を解析することによって、実行部３３０およびレジスタファイル３４０の各々を制御する制御信号を実行部３３０およびレジスタファイル３４０に供給する。
【００３５】
実行部３３０は、命令デコーダ３２０から供給された制御信号に基づいて、命令デコーダ３２０において解析した命令を実行するものである。この実行部３３０は、命令デコーダ３２０が再利用命令をデコードした場合、再利用命令が指定する再利用区間の処理を開始する。また、この再利用区間の処理の開始とともに、実行部３３０は、レジスタファイル３４０から取得した再利用区間の区間識別情報を、信号線３０９を介して履歴管理部４００に出力する。そして、実行部３３０は、レジスタファイル３４０から供給される再利用区間の入力値に基づいて再利用区間における処理を実行するとともに、再利用区間の入力値を、信号線３０９を介して履歴管理部４００に出力する。
【００３６】
また、実行部３３０は、履歴管理部４００から再利用区間の実行結果が供給された場合には、再利用区間の処理を中止するとともに、その実行結果を履歴管理部４００から供給された旨を通知する信号をフェッチ部３１０に供給する。この時、実行部３３０は、実行結果をレジスタファイル３４０に出力する。
【００３７】
一方、実行部３３０は、履歴管理部４００から再利用区間の実行結果が供給されない場合には、再利用区間の処理を最後まで実行して、その実行結果を履歴管理部４００およびレジスタファイル３４０に出力する。さらに、この実行部３３０は、反復再利用区間の実行結果が供給されない場合には、何回目の実行による実行結果であるのかを示すループカウンタ値を実行結果とともに履歴管理部４００に出力する。なお、ループカウンタ値は、特許請求の範囲に記載のカウンタ値の一例である。
【００３８】
レジスタファイル３４０は、データキャッシュ２２０から供給されたデータおよび実行部３３０から供給された実行結果を一時的に保持するものである。このレジスタファイル３４０は、例えば、命令デコーダ３２０から再利用命令に基づく制御信号が供給された場合には、再利用区間の入力値を実行部３３０に供給する。
【００３９】
履歴管理部４００は、再利用区間の実行結果を保持して管理するものであり、履歴対象データ保持部４１０と、履歴検索部４２０と、履歴メモリ４３０と、履歴登録部４４０と、履歴メモリ容量管理部４５０と、消去部４６０とを備える。
【００４０】
履歴対象データ保持部４１０は、実行部３３０から供給されたデータを一時的に保持するものである。この履歴対象データ保持部４１０は、実行部３３０から区間識別情報および入力値が供給された際には、これらを検索要求として履歴検索部４２０に供給する。この履歴対象データ保持部４１０は、例えば、実行部３３０において関数再利用区間が実行された場合には、実行部３３０から供給された関数の開始アドレスおよび入力値を、検索要求として履歴検索部４２０に供給する。また、履歴対象データ保持部４１０は、実行部３３０において反復再利用区間が実行された場合には、実行部３３０から供給されたループの開始アドレス、入力値およびループカウンタ値を検索要求として履歴検索部４２０に供給する。
【００４１】
また、この履歴対象データ保持部４１０は、実行部３３０から区間識別情報と、入力値と、実行結果とが供給された場合には、実行履歴を登録する条件が整うため、これらを実行履歴として履歴登録部４４０に供給する。例えば、履歴対象データ保持部４１０は、実行部３３０において関数再利用区間が実行された場合には、実行部３３０から供給された関数の開始アドレスと入力値と実行結果とを実行履歴として履歴登録部４４０に供給する。また、履歴対象データ保持部４１０は、実行部３３０において反復再利用区間が実行された場合には、ループの開始アドレスと入力値と実行結果とループカウンタ値とを実行履歴として履歴登録部４４０に供給する。
【００４２】
履歴検索部４２０は、履歴対象データ保持部４１０から供給された検索要求に基づいて実行履歴を検索するものである。この履歴検索部４２０は、検索要求入力部４２１および実行結果出力部４２２を備える。
【００４３】
検索要求入力部４２１は、履歴対象データ保持部４１０から供給された検索要求に基づいて履歴メモリ４３０から実行履歴を検索するものである。この検索要求入力部４２１は、例えば、反復再利用区間を指定する命令が命令デコーダ３２０において解析された場合には、この命令により指定されたループの開始アドレス、入力値およびループカウンタ値を履歴メモリ４３０に供給する。これにより、実行履歴の検索を開始する。
【００４４】
実行結果出力部４２２は、履歴メモリ４３０において実行履歴が検索された場合に実行結果を履歴メモリ４３０から抽出して、その抽出した実行結果を実行部３３０に出力するものである。この実行結果出力部４２２は、その抽出した実行結果を、信号線４０９を介して実行部３３０に供給する。
【００４５】
また、この実行結果出力部４２２は、履歴メモリ４３０においてループ代表履歴が実行履歴として検索された場合には、退避履歴を指し示す退避履歴位置情報を、実行結果の代わりに履歴メモリ４３０から抽出する。そして、その抽出した退避履歴に関する情報を履歴変換部５００に出力し、実行履歴の復元を開始させる。
【００４６】
履歴メモリ４３０は、履歴登録部４４０から供給された実行履歴を保持するものである。この履歴メモリ４３０は、例えば、履歴検索部４２０から検索要求が供給された場合において、この検索要求と一致する実行履歴を保持しているときは、この実行履歴の実行結果を実行結果出力部４２２に供給する。また、この履歴メモリ４３０は、履歴検索部４２０から検索要求が供給された場合において、この検索要求と一致するループ代表履歴を保持しているときは、このループ代表履歴の退避履歴位置情報を実行結果出力部４２２に供給する。さらに、この履歴メモリ４３０は、履歴登録部４４０から実行履歴が供給された場合には、この実行履歴を保持する。
【００４７】
また、この履歴メモリ４３０は、履歴メモリ４３０の使用状況に関する情報を履歴メモリ容量管理部４５０に供給する。さらにこの履歴メモリ４３０は、保持している実行履歴およびループ代表履歴を履歴変換部５００に供給する。この履歴メモリ４３０は、例えば、連想メモリ（ＣＡＭ：Content Addressable Memory）により実現される。
【００４８】
履歴登録部４４０は、履歴対象データ保持部４１０から供給された実行履歴を履歴メモリ４３０に保持させるためのデータ構造に変換して、その変換された実行履歴を履歴メモリ４３０に登録するものである。この履歴登録部４４０は、例えば、履歴検索部４２０により関数履歴が検索されない場合には、関数の開始アドレス、入力値および実行結果を、実行履歴として履歴メモリ４３０に登録する。また、この履歴登録部４４０は、例えば、履歴検索部４２０によりループ個別履歴が検索されない場合には、ループの開始アドレス、入力値、実行結果およびループカウンタ値を実行履歴として履歴メモリ４３０に登録する。
【００４９】
また、この履歴登録部４４０は、履歴メモリ容量管理部４５０から供給される履歴メモリ４３０の空き容量に比べて新たに登録する実行履歴のデータ量の方が大きい場合には、登録を一時中断する。そして、この履歴登録部４４０は、既に登録されている実行履歴のうち、前回の使用からの未使用期間が最も長い実行履歴を消去させるための消去開始情報を消去部４６０に供給する。
【００５０】
履歴メモリ容量管理部４５０は、履歴メモリ４３０の空き容量を管理するものである。この履歴メモリ容量管理部４５０は、例えば、履歴メモリ４３０に新たな実行履歴が登録される度に、履歴メモリ４３０の空き容量を測定する。さらに、この履歴メモリ容量管理部４５０は、履歴メモリ４３０から実行履歴が消去される度に、履歴メモリ４３０の空き容量を測定する。この履歴メモリ容量管理部４５０は、履歴メモリ４３０の空き容量に関する情報を履歴登録部４４０に供給する。
【００５１】
消去部４６０は、履歴登録部４４０から消去開始情報が供給された場合には、前回の使用からの未使用期間が最も長い実行履歴を消去するものである。
【００５２】
履歴変換部５００は、履歴管理部４００により管理されている実行履歴を退避履歴に変換して主記憶部１３０に保持させるものであり、履歴制御部５１０と、履歴復元部５２０と、退避領域管理部５３０とを備える。
【００５３】
履歴制御部５１０は、履歴メモリ４３０に保持されているループ個別実行履歴から退避履歴を生成して、主記憶部１３０に退避するものである。この履歴制御部５１０は、例えば、履歴メモリ４３０から反復再利用区間の実行履歴を、信号線４９０を介して抽出し、その実行履歴と、退避領域管理部５３０から供給される主記憶部１３０のアドレス情報とに基づいて退避履歴を主記憶部１３０に退避させる。また、この履歴制御部５１０は、例えば、履歴メモリ４３０に保持させる新たな実行履歴のデータ量が履歴メモリ４３０の空き容量より大きい場合に退避履歴の退避を開始する。
【００５４】
そして、この履歴制御部５１０は、退避履歴の基となったループ個別履歴を履歴メモリ４３０から消去し、退避履歴位置情報を含むループ代表履歴をループ個別履歴の代わりに履歴メモリ４３０に登録する。なお、ここでいう退避履歴位置情報とは、例えば、退避履歴の主記憶部１３０における格納位置を指し示す主記憶部１３０のアドレスである。このように、履歴制御部５１０は、生成した退避履歴を、信号線５０９を介して主記憶部１３０に供給する。また、履歴制御部５１０は、生成したループ代表履歴を、信号線５９０を介して履歴メモリ４３０に供給する。なお、履歴制御部５１０および履歴メモリ４３０から構成される装置は、特許請求の範囲に記載の履歴保存装置の一例である。
【００５５】
履歴復元部５２０は、実行結果出力部４２２から供給された退避履歴位置情報に基づいて主記憶部１３０から退避履歴を抽出して、その退避履歴に基づいて実行履歴を復元するものである。この履歴復元部５２０は、例えば、主記憶部１３０に退避した退避履歴の実行結果を再利用する場合には、実行結果出力部４２２から供給された退避履歴の情報に基づいて主記憶部１３０から信号線１３９を介して退避履歴を抽出する。そして、この履歴復元部５２０は、履歴メモリ４３０から抽出したループ代表履歴と、主記憶部１３０から抽出した退避履歴とに基づいて実行履歴を復元する。その後、この履歴復元部５２０は、履歴メモリ４３０に保持されているループ代表履歴を消去し、さらに履歴メモリ４３０における退避履歴を保持する容量を確保した後に、復元した実行履歴を履歴メモリ４３０に登録する。
【００５６】
このように、この履歴復元部５２０は、復元した実行履歴を、信号線５８０を介して履歴メモリ４３０に供給する。
【００５７】
退避領域管理部５３０は、主記憶部１３０における退避履歴が保持される領域を管理するものである。この退避領域管理部５３０は、例えば、退避履歴が保持される領域を主記憶部１３０に確保し、履歴制御部５１０が退避履歴を生成した場合には、主記憶部１３０におけるその退避履歴の退避先のアドレスを履歴制御部５１０に信号線５３９を介して供給する。
【００５８】
主記憶部１３０は、この構成図においては退避履歴を保持するものである。なお、主記憶部１３０は、特許請求の範囲に記載の退避履歴保持部の一例である。
【００５９】
このように、本発明の実施の形態では、プロセッサコア３００と履歴管理部４００と履歴変換部５００とを設けることによって、反復再利用区間の実行履歴を主記憶部１３０に退避させることができる。
【００６０】
なお、ここでは、反復再利用区間がループである場合について説明したが、これに限定されるものではない。例えば、ループ以外の反復再利用区間として、再帰呼び出し（リカーシブコール）を伴うサブルーチンなどが考えられる。
【００６１】
［履歴制御部５１０の構成例］
図３は、本発明の実施の形態における履歴制御部５１０の構成例を示すブロック図である。履歴制御部５１０は、退避履歴生成部６００と、ループ個別履歴消去部５１２と、ループ代表履歴登録部５１３とを備える。
【００６２】
退避履歴生成部６００は、ループ個別履歴に基づいて退避履歴を生成するものである。この退避履歴生成部６００は、例えば、ループの反復された実行による実行結果を含むループ個別履歴を履歴メモリ４３０から信号線４９０を介して取得して、その取得したループ個別履歴に基づいて退避履歴を生成する。この時、この退避履歴生成部６００は、主記憶部１３０におけるその退避履歴の退避先のアドレスを退避領域管理部５３０から信号線５３９を介して受け取る。そして、この退避履歴生成部６００は、その生成した退避履歴を、信号線５０９を介して主記憶部１３０に退避させる。
【００６３】
また、この退避履歴生成部６００は、退避履歴位置情報を含むループ代表履歴を生成し、信号線６０８を介してループ代表履歴登録部５１３に供給する。さらに、この退避履歴生成部６００は、退避履歴の基となったループ個別履歴を、信号線６０９を介してループ個別履歴消去部５１２に供給する。
【００６４】
ループ個別履歴消去部５１２は、退避履歴の基となった実行履歴を消去するものである。このループ個別履歴消去部５１２は、退避履歴生成部６００から供給された退避履歴の基となったループ個別履歴に基づいて、このループ個別履歴を履歴メモリ４３０から信号線５９２を介して消去する。また、このループ個別履歴消去部５１２は、そのループ個別履歴の消去を通知する情報をループ代表履歴登録部５１３に供給する。
【００６５】
ループ代表履歴登録部５１３は、ループ代表履歴を履歴メモリ４３０に登録するものである。このループ代表履歴登録部５１３は、例えば、退避履歴生成部６００からループ代表履歴が供給された場合に、ループ個別履歴消去部からループ個別履歴の消去を通知する情報が供給されたときは、ループ代表履歴を履歴メモリ４３０に信号線５９３を介して登録する。
【００６６】
［退避履歴生成部６００の構成例］
図４は、本発明の実施の形態における退避履歴生成部６００の構成例を示すブロック図である。退避履歴生成部６００は、先頭探索部６１０と、連続探索部６２０と、ループ個別履歴取得部６３０と、退避履歴転送部６４０と、ループ代表履歴生成部６５０とを備える。
【００６７】
先頭探索部６１０は、反復再利用区間の１回目の実行に関するループ個別履歴を、履歴メモリ４３０から信号線４９１を介して探索するものである。この先頭探索部６１０は、ループ個別履歴を探索した場合には、一旦動作を停止してその後のループ個別履歴の探索を連続探索部６２０に処理させる。この先頭探索部６１０は、その探索したループ個別履歴に関する位置情報を連続探索部６２０に供給する。
【００６８】
連続探索部６２０は、先頭探索部６１０から供給された反復再利用区間の１回目の実行に関するループ個別履歴の位置情報に基づいて、２回目以降の実行に関するループ個別履歴を、信号線４９２を介して探索するものである。この連続探索部６２０は、例えば、５０回反復されたループにおいて、１回目のループ個別履歴の位置情報が先頭探索部６１０から供給された場合には、２回目から５０回目までのループ個別履歴を探索する。そして、この連続探索部６２０は、５１回目の実行履歴が探索されなかったときに、その５０個のループ個別履歴を取得するための位置情報をループ個別履歴取得部６３０に供給する。
【００６９】
また、この連続探索部６２０は、２回目以降のループ個別履歴が探索されなかった場合には、反復再利用区間は反復して実行されなかったと判断して、退避履歴の生成を中止する。そして、この連続探索部６２０は、一端動作を停止して先頭探索部６１０に反復再利用区間の１回目の実行に関するループ個別履歴の探索を再開させる。
【００７０】
ループ個別履歴取得部６３０は、連続探索部６２０から供給されたループ個別履歴を取得するための位置情報に基づいて、ループ個別履歴を、信号線４９３を介して履歴メモリ４３０から取得するものである。このループ個別履歴取得部６３０は、例えば、連続探索部６２０から５０回反復された反復再利用区間における５０個のループ個別履歴に関する位置情報が供給された場合には、その５０個のループ個別履歴を履歴メモリ４３０から取得する。また、このループ個別履歴取得部６３０は、その取得したループ個別履歴を、信号線６３８および信号線６０９を介して退避履歴転送部６４０、ループ代表履歴生成部６５０およびループ個別履歴消去部５１２に供給する。
【００７１】
退避履歴転送部６４０は、ループ個別履歴取得部６３０から供給されたループ個別履歴に基づいて退避履歴を生成して、その生成された退避履歴を主記憶部１３０に転送するものである。この退避履歴転送部６４０は、例えば、５０回反復された反復再利用区間の５０個のループ個別履歴が供給された場合には、５０個の退避履歴を生成する。この退避履歴転送部６４０は、退避領域管理部５３０から信号線５３９を介して供給される主記憶部１３０のアドレスに基づいて退避履歴を主記憶部１３０に退避させる。この退避履歴転送部６４０は、生成した退避履歴を、信号線５０９を介して主記憶部１３０に転送する。
【００７２】
ループ代表履歴生成部６５０は、ループ個別履歴取得部６３０から供給されたループ個別履歴に基づいてループ代表履歴を生成するものである。このループ代表履歴生成部６５０は、退避領域管理部５３０から信号線５３９を介して供給される主記憶部１３０のアドレスに基づいて、退避履歴位置情報が含まれるループ代表履歴を生成する。このループ代表履歴生成部６５０は、その生成したループ代表履歴を、信号線６０８を介してループ代表履歴登録部５１３に供給する。
【００７３】
［履歴復元部５２０の構成例］
図５は、本発明の実施の形態における履歴復元部５２０の構成例を示すブロック図である。履歴復元部５２０は、退避履歴取得部５２１と、ループ個別履歴生成部５２２と、登録領域確保部５２３と、ループ個別履歴登録部５２４とを備える。
【００７４】
退避履歴取得部５２１は、実行結果出力部４２２から供給された退避履歴位置情報に基づいて主記憶部１３０から退避履歴を取得するものである。この退避履歴取得部５２１は、例えば、反復して５０回実行された反復再利用区間の退避履歴を取得する場合には、実行結果出力部４２２から信号線４０８を介して供給された退避履歴位置情報に基づいて、その５０個の退避履歴を主記憶部１３０から取得する。この退避履歴取得部５２１は、その取得した退避履歴をループ個別履歴生成部５２２に供給する。
【００７５】
ループ個別履歴生成部５２２は、退避履歴からループ個別履歴を生成するものである。このループ個別履歴生成部５２２は、信号線４０８を介して供給された退避履歴位置情報に基づいて、その退避履歴位置情報を含むループ代表履歴を履歴メモリ４３０から信号線４８０を介して取得する。そして、このループ個別履歴生成部５２２は、その取得したループ代表履歴と、退避履歴取得部５２１から供給された退避履歴とに基づいて、ループ個別履歴を生成する。
【００７６】
このループ個別履歴生成部５２２は、その生成したループ個別履歴をループ個別履歴登録部５２４に供給する。また、このループ個別履歴生成部５２２は、ループ代表履歴と、ループ個別履歴のデータ量とを登録領域確保部５２３に供給する。
【００７７】
登録領域確保部５２３は、ループ個別履歴を登録するために履歴メモリ４３０の空き領域を確保するものである。この登録領域確保部５２３は、ループ個別履歴生成部５２２から供給されたループ代表履歴を、履歴メモリ４３０から信号線５８３を介して消去する。そして、この登録領域確保部５２３は、ループ個別履歴生成部５２２から供給されたループ個別履歴のデータ量に基づいて、履歴メモリ４３０に全てのループ個別履歴を登録する空き容量があるか否か判断する。この登録領域確保部５２３は、履歴メモリ４３０にその空き容量が不足している場合には、信号線５８３を介して空き容量を確保する。例えば、この登録領域確保部５２３は、前回の使用からの未使用期間が最も長い実行履歴を消去して履歴メモリ４３０における必要な空き容量を確保する。
【００７８】
この登録領域確保部５２３は、履歴メモリ４３０における空き容量に関する情報をループ個別履歴登録部５２４に供給する。
【００７９】
ループ個別履歴登録部５２４は、ループ個別履歴生成部５２２から供給されたループ個別履歴を、信号線５８４を介して履歴メモリ４３０に登録するものである。このループ個別履歴登録部５２４は、ループ個別履歴生成部５２２から供給されたループ個別履歴を、登録領域確保部５２３から供給された情報が指し示す履歴メモリ４３０の空き容量に登録する。
【００８０】
このように、本発明の実施の形態では、データ処理装置１００に履歴管理部４００および履歴変換部５００を設けることによって、実行が反復される反復再利用区間の実行履歴を退避履歴として主記憶部１３０に退避することができる。
【００８１】
＜２．履歴情報のフィールド構成例＞
［実行履歴、ループ個別履歴および退避履歴のフィールド構成例］
図６は、本発明の実施の形態における履歴メモリ４３０に保持される関数履歴、ループ個別履歴およびループ代表履歴と、主記憶部１３０に保持される退避履歴とのフィールド構成例を示す模式図である。
【００８２】
図６（ａ）には、関数再利用区間の実行履歴である関数履歴７１０のフィールド構成例が示されている。この関数履歴７１０は、識別子フィールド７１１と、開始アドレスフィールド７１２と、入力値リンクフィールド７１３と、実行結果リンクフィールド７１７とから構成される。
【００８３】
識別子フィールド７１１は、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するためのフィールドである。この識別子フィールド７１１には、関数履歴であることを示す２ビット（００）が格納される。また、この識別子フィールド７１１は、関数履歴７１０における先頭のフィールドであり、例えば、その関数履歴７１０の開始アドレスに保持されるフィールドである。
【００８４】
開始アドレスフィールド７１２は、関数の開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７１２に格納される関数の開始アドレスは、検索要求入力部４２１により実行履歴が検索される場合には、検索要求の開始アドレスと比較される。
【００８５】
入力値リンクフィールド７１３は、リンク構造を用いて格納されている関数の入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７１３には、検索要求入力部４２１により実行履歴が検索されて検索要求の開始アドレスが開始アドレスフィールド７１２の開始アドレスと一致したときに、検索要求の入力値と比較される入力値を保持するアドレスが格納される。この入力値リンクフィールド７１３には、例えば、３つの引数を入力値とする関数の場合には、３つの関数のうち１番目の引数の値である第１引数値が保持されているアドレスが格納される。
【００８６】
実行結果リンクフィールド７１７は、リンク構造を用いて格納されている関数の実行結果のアドレスを格納するためのフィールドである。この実行結果リンクフィールド７１７には、検索要求入力部４２１により実行履歴が検索されて開始アドレスおよび入力値が一致したときに、実行結果として出力される関数の実行結果が保持されているアドレスが格納される。例えば、３つの変数を出力値とする関数の場合には、３つの変数のうち１番目の変数の値が保持されているアドレスが実行結果リンクフィールド７１７に格納される。
【００８７】
図６（ｂ）には、反復再利用区間の実行履歴であるループ個別履歴７２０のフィールド構成例が示されている。このループ個別履歴７２０は、識別子フィールド７２１と、開始アドレスフィールド７２２と、入力値リンクフィールド７２３と、ループカウンタ値フィールド７２４と、実行結果リンクフィールド７２７とから構成される。
【００８８】
識別子フィールド７２１は、図６（ａ）において示した識別子フィールド７１１と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するための識別子を格納するフィールドである。この識別子フィールド７２１には、ループ個別履歴であることを示す２ビット（０１）が格納される。また、この識別子フィールド７２１は、ループ個別履歴７２０における先頭のフィールドであり、例えば、そのループ個別履歴７２０の開始アドレスに保持されるフィールドである。
【００８９】
開始アドレスフィールド７２２は、ループの開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７２２に格納されるループの開始アドレスは、検索要求入力部４２１により実行履歴が検索される場合には、検索要求の開始アドレスと比較される。
【００９０】
入力値リンクフィールド７２３は、リンク構造を用いて格納されているループの入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７２３の機能は、図６（ａ）において示した入力値リンクフィールド７１３と同様のものであるので、ここでの詳細な説明を省略する。
【００９１】
ループカウンタ値フィールド７２４は、ループの何回目の実行による実行結果であるのかを示す値を格納するためのフィールドである。このループカウンタ値フィールド７２４には、検索要求入力部４２１により実行履歴が検索されて開始アドレスおよび入力値が一致したときに、検索要求のループカウンタ値と比較されるループカウンタ値が格納される。
【００９２】
実行結果リンクフィールド７２７は、リンク構造を用いて格納されているループの実行結果のアドレスを格納するフィールドである。この実行結果リンクフィールド７２７には、検索要求入力部４２１により実行履歴が検索されて開始アドレス、入力値、およびループカウンタ値が一致したときに、実行結果として出力されるループの実行結果が保持されているアドレスが格納される。
【００９３】
図６（ｃ）には、反復再利用区間の代表履歴であるループ代表履歴７３０のフィールド構成例が示されている。このループ代表履歴７３０は、識別子フィールド７３１と、開始アドレスフィールド７３２と、入力値リンクフィールド７３３と、退避カウントフィールド７３５と、退避履歴アドレスフィールド７３６とから構成される。
【００９４】
識別子フィールド７３１は、図６（ａ）において示した識別子フィールド７１１と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴とを識別するためのフィールドである。この識別子フィールド７３１には、ループ代表履歴であることを示す２ビット（１０）が格納される。また、この識別子フィールド７３１は、ループ代表履歴７３０における先頭のフィールドであり、例えば、そのループ代表履歴７３０の開始アドレスに保持されるフィールドである。
【００９５】
開始アドレスフィールド７３２は、図６（ｂ）において示した開始アドレスフィールド７２２と同様に、ループの開始アドレスを格納するためのフィールドである。この開始アドレスフィールド７３２の機能は、図６（ｂ）の開始アドレスフィールド７２２と同様のものであるのでここでの詳細な説明を省略する。
【００９６】
入力値リンクフィールド７３３は、図６（ｂ）において示した入力値リンクフィールド７２３と同様に、リンク構造を用いて格納されているループの入力値のアドレスを格納するためのフィールドである。この入力値リンクフィールド７３３の機能は、図６（ｂ）において示した入力値リンクフィールド７２３と同様のものであるのでここでの詳細な説明を省略する。
【００９７】
退避カウントフィールド７３５は、主記憶部１３０に退避された退避履歴の個数を示す値を格納するためのフィールドである。この退避カウントフィールド７３５には、実行履歴が検索されて検索要求の開始アドレスおよび入力値がループ代表履歴の開始アドレスおよび入力値と一致したときに、履歴復元部５２０に退避履歴位置情報として供給される退避履歴の個数が格納される。
【００９８】
退避履歴アドレスフィールド７３６は、退避履歴アドレスを格納するためのフィールドである。ここでいう退避履歴アドレスとは、主記憶部１３０に退避された退避履歴が格納されているアドレスである。この退避履歴アドレスフィールド７３６には、実行履歴が検索されて検索要求の開始アドレスおよび入力値が、ループ代表履歴の開始アドレスおよび入力値と一致したときに、履歴復元部５２０に退避履歴位置情報として供給される退避履歴アドレスが格納される。例えば、この退避履歴アドレスフィールド７３６には、反復再利用区間の複数の退避履歴を連続したアドレスに保存した場合において、最初の退避履歴の開始アドレスが格納される。
【００９９】
図６（ｄ）には、反復再利用区間の退避履歴７４０のフィールド構成例が示されている。この退避履歴７４０は、ループカウンタ値フィールド７４４および実行結果リンクフィールド７４７から構成される。
【０１００】
ループカウンタ値フィールド７４４は、図６（ｂ）において示したループカウンタ値フィールド７２４と同様に、ループの何回目の実行による実行結果であるのかを示す値を格納するためのフィールドである。このループカウンタ値フィールド７４４には、履歴復元部５２０によりループ個別履歴が復元されるときに、ループカウンタ値フィールド７２４となる値が格納される。
【０１０１】
実行結果リンクフィールド７４７は、図６（ｂ）において示した実行結果リンクフィールド７２７と同様に、リンク構造を用いて格納されているループの実行結果のアドレスを格納するフィールドである。この実行結果リンクフィールド７４７には、履歴復元部５２０によりループ個別履歴が復元されるときに、実行結果リンクフィールド７２７となる値が格納される。
【０１０２】
なお、ここでは、実行履歴およびループ代表履歴のデータ長を固定長にして履歴メモリ４３０における実行履歴およびループ代表履歴の登録や消去を容易にするために、また、実行履歴のデータ量を少なくするために、入力値および実行結果をリンク構造にした。しかしながら、関数履歴、ループ個別履歴、ループ代表履歴および退避履歴のデータ構造はこれに限定されるものではない。例えば、入力値および実行結果をリンク構造にしないで、関数履歴、ループ個別履歴、ループ代表履歴および退避履歴にそのまま保持させるようにしてもよい。
【０１０３】
［入力値リンクおよび実行結果リンクのデータ構造例］
図７は、本発明の実施の形態における入力値リンクおよび実行結果リンクのデータ構造例を示す概念図である。
【０１０４】
ここでは、図６（ａ）において示した入力値リンクフィールド７１３と、入力値を格納する入力値格納領域７６０のデータ構造とが示されている。この例では、３つの引数が入力値である関数を想定する。また、ここでは、入力値格納領域７６０は、関数履歴、ループ個別履歴およびループ個別履歴が保存される領域とは異なる履歴メモリ４３０の領域であることとする。
【０１０５】
入力値格納領域７６０は、関数履歴およびループ個別履歴の入力値を保持する領域である。この入力値格納領域７６０には、３つの引数として、第１引数値７６１、第２引数値７６３および第３引数値７６５が左側のカラムに示されている。そして、この入力値格納領域７６０の右側のカラムには、その３つの引数とともに保存されるリンクアドレス７６２、７６４および７６６が示されている。
【０１０６】
第１引数値７６１、第２引数値７６３および第３引数値７６５は、入力値リンクフィールド７１３が指定する入力値である３つの引数の引数値がそれぞれ保持される領域である。すなわち、第１引数値７６１には、第１番目とされた引数の引数値が保持され、第２引数値７６３には、第２番目とされた引数の引数値が保持され、第３引数値７６５には、第３番目とされた引数の引数値が保持される。例えば、第１引数値７６１には関数再利用区間において１番最初に使用された引数が保持され、第２引数値７６３には２番目に使用された引数が保持され、第３引数値７６５には３番目に使用された引数が保持される。また、第１引数値７６１のアドレスは、入力値リンクフィールド７１３に格納されるアドレスである。
【０１０７】
リンクアドレス７６２、リンクアドレス７６４およびリンクアドレス７６６は、第１引数値７６１、第２引数値７６３および第３引数値７６５にそれぞれ連結して保存され、次の引数のアドレスを格納する領域である。例えば、第１引数値７６１に連結して保存されるリンクアドレス７６２は、第２引数値７６３のアドレスを格納する。また、リンクアドレス７６２、リンクアドレス７６４およびリンクアドレス７６６は、次の引数が無い場合には、リンク先が無いことを示す「０」が格納される。例えば、第３引数値７６５に連結して保存されるリンクアドレス７６６は、第４番目の引数が無いため「０」が格納される。
【０１０８】
このように、入力値格納領域７６０には、実行履歴の入力値が引数毎に次の引数の保存場所を指定するリンクアドレスが保持される。実行履歴の検索のときには、検索要求の開始アドレスと関数履歴７１０の開始アドレスが一致した場合に入力値リンクフィールド７１３が参照されて、第１引数値７６１から順に引数毎に検索要求の入力値の引数と比較される。そして、第３引数値７６５まで一致するとリンクアドレス７６６の「０」により検索を終了し、実行結果の出力過程に移行する。
【０１０９】
このように、本発明の実施の形態では、実行履歴の入力値をリンク構造で保存することにより、記憶領域の無駄な領域を減少させて効率よく入力値を保持させることができる。なお、入力値リンクフィールド７２３および入力値リンクフィールド７３３に関しては、入力値リンクフィールド７１３と同様にリンク構造を用いて入力値が保存されるため説明を省略する。また、実行結果リンクフィールド７１７、実行結果リンクフィールド７２７および実行結果リンクフィールド７４７に関しても、入力値リンクフィールド７１３と同様にリンク構造を用いて実行結果が保存されるためｈ説明を省略する。
【０１１０】
なお、ここでは、３つの引数が入力値である関数を想定したが、引数の値が最大３つに限定されるものではない。リンクを繋げることで３つ以上の引数および変数に対応することができる。また、ここでは、入力値格納領域７６０は、検索を高速にするために履歴メモリ４３０における領域であることを想定したが、これに限定されるものではない。例えば、主記憶部１３０に入力値格納領域７６０を確保することにより、より多くの実行履歴およびループ個別履歴を履歴メモリ４３０に保持させることができる。
【０１１１】
＜３．履歴メモリに保持される履歴情報および主記憶部に保持される退避履歴の一例＞
［ループ個別履歴の退避の具体例］
図８は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。ここでは、履歴メモリ４３０における関数履歴、ループ個別履歴およびループ代表履歴を登録する領域は、データ量と無関係に１０個の履歴が格納できる容量であることを想定する。さらにここでは、主記憶部１３０における退避履歴を保持させる領域は、データ量と無関係に６個の退避履歴を退避できる容量であることとする。また、これ以降の説明では、便宜上、関数再利用区間の実行履歴である関数履歴、反復再利用区間の実行履歴であるループ個別履歴、および、反復再利用区間の代表履歴であるループ代表履歴の３つの履歴を履歴情報と表現することとする。
【０１１２】
図８（ａ）は、履歴制御部５１０が動作する前の履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の一例である。ここには、実行履歴表８１１および退避履歴表８１２が示されている。
【０１１３】
実行履歴表８１１は、履歴メモリ４３０に登録されている履歴情報を表すものである。この実行履歴表８１１における左側のカラムには、履歴メモリ４３０に登録された順序を示す順位が「１」から「１０」まで順に例示されている。この順位は、数値が小さいものほど先に履歴メモリ４３０に登録されたことを示すものとする。
【０１１４】
実行履歴表８１１における右側のカラムには、履歴メモリ４３０に登録されている履歴情報が示されている。ここには、図６（ａ）乃至（ｄ）において示した識別子と、その履歴情報の基となった関数またはループとが示されている。また、ループ個別履歴の場合には、そのループ個別履歴が反復された実行において何回目の実行であるのかを示す値がさらに示されている。
【０１１５】
例えば、順位が「１」の履歴情報（００（ｆｕｎｃＡ））は、関数Ａ（ｆｕｎｃＡ）の関数履歴（００）を示している。また、「７」の順位の履歴情報（０１（ｌｏｏｐＦ（１）））は、ループＦ（ｌｏｏｐＦ）の１回目（１）の実行に関するループ個別履歴（０１）を示している。また、「８」の順位の履歴情報（０１（ｌｏｏｐＦ（２）））は、反復して実行されたループＦ（ｌｏｏｐＦ）の２回目（２）の実行に関するループ個別履歴（０１）を示している。
【０１１６】
退避履歴表８１２は、主記憶部１３０に退避された退避履歴を表すものである。この退避履歴表８１２における順位には、主記憶部１３０に登録された順序を示す順位が示されており、ここでは、「１」から「６」までの順位が例示されている。この順位は、数値が少ないものほど古く、早い時点で登録されたことを意味している。
【０１１７】
退避履歴表８１２における退避履歴には、主記憶部１３０に退避された退避履歴が示されている。ここでは、主記憶部１３０に退避履歴は１つも退避されていないことが示されている。
【０１１８】
この様な場合において、履歴制御部５１０は、履歴メモリ４３０に新たな実行履歴を登録する空き容量が無いことを検出すると、履歴メモリ４３０から反復して実行された反復再利用区間のループ個別履歴の退避を開始する。
【０１１９】
図８（ｂ）は、履歴制御部５１０が動作した後の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８２１および退避履歴表８２２が示されている。
【０１２０】
実行履歴表８２１は、図８（ａ）で示した実行履歴表８１１におけるループ個別履歴が退避された後の履歴メモリ４３０における履歴情報を表すものである。
【０１２１】
実行履歴表８２１では、実行履歴表８１１の「７」の順位のループ個別履歴（０１（ｌｏｏｐＦ（１））と、「８」の順位のループ個別履歴（０１（ｌｏｏｐＦ（２））と、「９」の順位のループ個別履歴（０１（ｌｏｏｐＦ（３））とが削除されている。そして、その３つのループ個別履歴の代わりとして、ループ代表履歴（１０（ｌｏｏｐＦ））が「７」の順位に示されている。
【０１２２】
また、その３つのループ個別履歴がループ代表履歴（１０（ｌｏｏｐＦ））に代わったことにより、図８（ａ）の実行履歴表８１１における「１０」の順位で示した関数Ｂの関数履歴（００（ｆｕｎｃＢ））の順位が「８」に繰り上げられている。そして、実行履歴表８２１における順位が「９」乃至「１０」の実行履歴は存在しないことを意味する。
【０１２３】
退避履歴表８２２は、履歴制御部５１０が動作した後の主記憶部１３０に退避された退避履歴を表すものである。
【０１２４】
この退避履歴表８２２の「１」の順位には、実行履歴表８１１の「７」の順位のループ個別履歴（０１（ｌｏｏｐＦ（１）））に基づいて生成された、反復して実行されたループＦの１回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（１））が示されている。「２」の順位には、実行履歴表８１１の「８」の順位において示したループ個別履歴（０１（ｌｏｏｐＦ（２）））に基づいて生成された、反復して実行されたループＦの２回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（２））が示されている。
【０１２５】
そして、「３」の順位には、実行履歴表８１１の「９」の順位において示したループ個別履歴（０１（ｌｏｏｐＦ（３）））に基づいて生成された、反復されたループＦの３回目の実行の実行結果を含む退避履歴（ｌｏｏｐＦ（３））が示されている。
【０１２６】
このように、本発明の実施の形態では、履歴制御部５１０を設けることによって、反復して実行されるループのループ個別履歴の実行結果を主記憶部１３０に退避させることができる。
【０１２７】
［ループ個別履歴の復元の具体例］
図９は、本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元の際の、履歴メモリ４３０および主記憶部１３０における実行履歴、ループ代表履歴および退避履歴の具体例を示す図である。ここでは、履歴メモリ４３０および主記憶部１３０は、図８において示した履歴メモリ４３０および主記憶部１３０と同様の機能であることを想定する。また、ここでは、空き容量が無い履歴メモリ４３０に新たな実行履歴を登録する場合には、前回の使用からの未使用期間が最も長い実行履歴を削除する（ＬＲＵ：Least Recently Used）ことにより空き容量を確保することとする。さらに、ここでは、実行履歴は登録されてから一度も使用されていないことを想定し、ＬＲＵにより削除される実行履歴は、順序が最も若い実行履歴であることとする。
【０１２８】
図９（ａ）は、退避履歴に基づいてループ個別履歴が復元される前の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８３１および退避履歴表８３２が示されている。
【０１２９】
実行履歴表８３１は、履歴復元部５２０がループ個別履歴を復元する前の履歴メモリ４３０に登録されている履歴情報を示すものである。この実行履歴表８３１には、図８（ｂ）において示した実行履歴表８２１の空き容量に新たな実行履歴が格納された状態が示されている。この新たな実行履歴として、「９」の順位には関数Ｃの関数履歴００（ｆｕｎｃＣ）が登録され、「１０」の順位には関数Ｄの関数履歴００（ｆｕｎｃＤ）が格納されている。
【０１３０】
退避履歴表８３２は、図８（ｂ）において示した退避履歴表８２２と同様に、主記憶部１３０に退避された退避履歴を表すものである。
【０１３１】
この様な場合において、履歴検索部４２０により履歴メモリ４３０からループＦに関するループ代表履歴が検索されると、履歴復元部５２０は退避履歴からループ個別履歴の復元を開始する。
【０１３２】
図９（ｂ）は、履歴復元部５２０により退避履歴からループ個別履歴が復元された後の履歴メモリ４３０および主記憶部１３０における履歴情報および退避履歴の一例である。ここには、実行履歴表８４１および退避履歴表８４２が示されている。
【０１３３】
実行履歴表８４１は、履歴復元部５２０がループ個別履歴を復元した後の履歴メモリ４３０に登録されている履歴情報を示すものである。この実行履歴表８４１には、図９（ａ）で示した退避履歴表８３２の退避履歴からループ個別履歴が復元されて実行履歴表８３１の実行履歴に加えられた状態が示されている。
【０１３４】
この実行履歴表８４１では、実行履歴表８３１における順位「１」および「２」に対応する実行履歴００（ｆｕｎｃＡ）および０１（ｌｏｏｐＡ（１））が消去されて、「３」乃至「６」の実行履歴の順序が「１」乃至「４」に繰り上がっている。
【０１３５】
そして、「５」の順位では、退避履歴表８３２の「１」の順位の退避履歴（ｌｏｏｐＦ（１））の基となった実行履歴０１（ｌｏｏｐＦ（１））が復元されて登録されている。「６」および「７」の順位でも「５」と同様に、実行履歴０１（ｌｏｏｐＦ（２））および０１（ｌｏｏｐＦ（３））が復元されて登録されている。
【０１３６】
退避履歴表８４２は、ループ個別履歴が復元された後の主記憶部１３０に登録された退避履歴を示すものである。この退避履歴表８４２には、退避履歴表８３２において示した退避履歴は全て復元されて主記憶部１３０から削除され、退避履歴は１つも退避されていないことが示されている。
【０１３７】
このように、本発明の実施の形態では、履歴復元部５２０を設けることによって、主記憶部１３０に退避履歴として退避されたループ個別履歴を履歴メモリ４３０に復元することができる。
【０１３８】
［本発明の実施の形態における新たな実行履歴の登録例］
図１０は、本発明の実施の形態における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示す図である。ここでは、履歴メモリ４３０は、データ量と無関係に１２個の履歴情報が登録できる容量であることを想定する。
【０１３９】
また、ここでは、空き容量が無い履歴メモリ４３０に新たな実行履歴を登録したい場合には、前回の使用からの未使用期間が最も長い実行履歴を削除する（ＬＲＵ）ことができることとする。さらにここでは、実行履歴は登録されてから一度も使用されていないことを想定し、ＬＲＵにより削除される実行履歴は、履歴メモリ４３０に最も早くに登録された実行履歴であることとする。
【０１４０】
図１０（ａ）は、新たに登録される実行履歴を示した模式図である。ここには、新たに登録される実行履歴が登録履歴表８６１に示されている。なお、図１０では、登録履歴表８６１に記されている実行履歴のうち、上方に記されている実行履歴から順に履歴メモリ４３０に登録されることを想定する。
【０１４１】
図１０（ｂ）は、従来技術を用いたデータ処理装置１００における新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示したものである。ここには、実行履歴表８７１と、実行履歴表８７２と、消去履歴表８７３とが示されている。
【０１４２】
実行履歴表８７１は、登録履歴表８６１において示した新たな実行履歴が登録される前の履歴メモリ４３０における実行履歴を表したものである。また、この実行履歴表８７１では、上方に記されている実行履歴から順に履歴メモリ４３０に登録されたことを想定する。
【０１４３】
実行履歴表８７２は、登録履歴表８６１において示した新たな実行履歴が登録された後の履歴メモリ４３０における実行履歴を示すものである。この実行履歴表８７２には、実行履歴表８７１の実行履歴に登録履歴表８６１で示した新たな実行履歴が登録された状態が示されている。
【０１４４】
この実行履歴表８７２では、実行履歴表８７１における上から１番目乃至５番目（００（ｆｕｎｃＥ）、０１（ｌｏｏｐＢ（１））乃至０１（ｌｏｏｐＢ（４））の実行履歴が消去されている。そして、実行履歴表８７１における上から６番目乃至１２番目の実行履歴が、実行履歴表８７２の１番目乃至７番目に示されている。さらに、この実行履歴表８７２では、登録履歴表８６１で示した新たな実行履歴が８番目乃至１２番目に示されている。
【０１４５】
消去履歴表８７３は、登録履歴表８６１で示した新たな実行履歴の登録により履歴メモリ４３０から消去された実行履歴を表したものである。この消去履歴表８７３では、実行履歴表８７１における上から１番目乃至５番目の実行履歴が示されている。
【０１４６】
このように、従来技術を用いたデータ処理装置１００では、履歴制御部５１０を備えていないため、実行履歴の実行結果を主記憶部１３０に退避させることができない。これにより、新たな実行履歴を履歴メモリ４３０に登録する場合には、前回の使用から最も未使用期間が長い実行履歴を履歴メモリ４３０から削除して、その代わりに新たな実行履歴を登録しなければならない。
【０１４７】
図１０（ｃ）は、本発明の実施の形態におけるデータ処理装置１００において新たな実行履歴が登録されるときの履歴メモリ４３０における履歴情報と主記憶部１３０における退避履歴との具体例を示したものである。ここには、実行履歴表８８１と、退避履歴表８８２と、実行履歴表８８３と、退避履歴表８８４とが示されている。ここでは、主記憶部１３０の退避履歴を退避させる領域は、データ量と無関係に８個の退避履歴が退避できる容量であることを想定する。
【０１４８】
実行履歴表８８１は、登録履歴表８６１において示した新たな実行履歴が登録される前の履歴メモリ４３０における実行履歴を表したものである。この実行履歴表８８１は、図１０（ｂ）の実行履歴表８７１と同様のものを示しているため、詳細な説明を省略する。
【０１４９】
退避履歴表８８２は、登録履歴表８６１において示した新たな実行履歴が登録される前の主記憶部１３０における退避履歴を表したものである。この退避履歴表８８２では、主記憶部１３０に退避履歴は１つも退避されていないことが示されている。
【０１５０】
実行履歴表８８３は、登録履歴表８６１において示した新たな実行履歴が登録された後の履歴メモリ４３０における履歴情報を示すものである。この実行履歴表８８３には、実行履歴表８８１の実行履歴に登録履歴表８６１で示した新たな実行履歴が登録された状態が示されている。
【０１５１】
この実行履歴表８８３では、実行履歴表８８１における上から２番目乃至５番目のループＢのループ個別履歴（０１（ｌｏｏｐＢ（１））乃至０１（ｌｏｏｐＢ（４））が履歴メモリ４３０から削除されている。そして、その削除されたループＢのループ個別履歴の代わりに、ループ代表履歴（１０（ｌｏｏｐＢ））が実行履歴表８８３における上から２番目に示されている。また、実行履歴表８８１における上から６番目乃至９番目の実行履歴が、この実行履歴表８８３では３番目乃至６番目に示されている。
【０１５２】
さらに、この実行履歴表８８３では、実行履歴表８８１における上から１０番目乃至１２番目のループＣのループ個別履歴（０１（ｌｏｏｐＣ（１））乃至０１（ｌｏｏｐＣ（３））が履歴メモリ４３０から削除されている。そして、その削除されたループＣのループ個別履歴の代わりに、ループ代表履歴（１０（ｌｏｏｐＣ））が上から７番目に示されている。そして、この実行履歴表８８３では、登録履歴表８６１で示した新たな実行履歴が、８番目乃至１２番目に記されている。
【０１５３】
退避履歴表８８４は、登録履歴表８６１において示した新たな実行履歴が登録された後の主記憶部１３０における退避履歴を示すものである。この退避履歴表８８４では、上から１番目乃至４番目にループＢに関する退避履歴（ｌｏｏｐＢ（１）乃至ｌｏｏｐＢ（４））が示されている。さらに、ここでは、上から５番目乃至７番目にループＣに関する退避履歴（ｌｏｏｐＣ（１）乃至ｌｏｏｐＣ（３））が示されている。
【０１５４】
このように、本発明の実施の形態におけるデータ処理装置１００では、履歴制御部５１０を備えているため、退避履歴を主記憶部１３０に退避させ、退避履歴の基となったループ個別履歴の代わりにループ代表履歴を履歴メモリ４３０に登録することができる。これにより、新たな実行履歴を履歴メモリ４３０に登録する場合には、ループ個別履歴に基づいて退避履歴を退避させ、そしてループ個別履歴をループ代表履歴に置き換えることで履歴メモリ４３０空き容量を生成することができる。すなわち、本発明の実施の形態によれば、従来技術を用いたデータ処理装置１００と比較して履歴メモリ４３０に保持される実行履歴の数を増やすことができる。
【０１５５】
＜４．データ処理装置の処理手順例＞
［本発明の実施の形態における履歴制御部５１０の動作例］
次に、本発明の実施の形態における履歴制御部５１０の処理について図面を参照して説明する。
【０１５６】
図１１は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の退避処理の処理手順例を示すフローチャートである。なお、ここでは、関数履歴と、ループ個別履歴と、ループ代表履歴と、退避履歴とは、それぞれ固定長のデータであることを想定する。また、ここでは、履歴メモリ４３０では、関数履歴と、ループ個別履歴と、ループ代表履歴とは連続するアドレスに登録された順に格納されるものとする。さらに、主記憶部１３０では、退避履歴は連続するアドレスに退避された順に格納されるものとする。
【０１５７】
まず、先頭探索部６１０において、探索アドレス（ｒａｄｒ）が「０」に設定される（ステップＳ９１１）。これにより、履歴メモリ４３０の履歴情報が登録される領域の先頭のデータから退避履歴の探索が開始されるようになる。
【０１５８】
次に、先頭探索部６１０において、探索アドレス（ｒａｄｒ）から識別子が読み出される（ステップＳ９１２）。そして、読み出された識別子が、ループ個別履歴を指し示す「０１」であるか否かが判断される（ステップＳ９１３）。そして、識別子が「０１」でないと判断された場合には、識別子が関数履歴を指し示す「００」であるか否かが判断される（ステップＳ９１４）。
【０１５９】
そして、識別子が「００」でないと判断された場合には、解析対象の履歴情報は識別子が「１０」のループ代表履歴であると判定される。続いて、ループ代表履歴のデータ長から算出されたループ代表履歴が保持されているアドレスの個数である代表履歴アドレス数（ｘ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１５）。これにより、探索アドレス（ｒａｄｒ）は、次に解析する履歴情報における識別子を指し示すアドレスとなる。
【０１６０】
一方、ステップＳ９１４の処理において、識別子が「００」であると判断された場合には、その識別子を示す履歴情報が関数履歴であると判定される。そして、関数履歴のデータ長から算出された関数履歴が保持されているアドレスの個数である関数履歴アドレス数（ｙ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１６）。
【０１６１】
一方、ステップＳ９１３の処理において、識別子が「０１」であると判断された場合には、その識別子を示す履歴情報がループ個別履歴であると判定される。そして、ループ個別履歴のデータ長から算出されたループ個別履歴が保持されているアドレスの個数である個別履歴アドレス数（ｚ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９１７）。
【０１６２】
次に、連続探索部６２０において、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）が、ステップＳ９１３で検出されたループ個別履歴における反復再利用区間の開始アドレスに設定される（ステップＳ９１８）。さらに、退避履歴開始アドレス（ｍａｄｒ）が、退避領域管理部５３０から供給された最初の退避履歴を格納する開始アドレスである退避開始アドレスに設定される（ステップＳ９１９）。
【０１６３】
さらに、ループの回数をカウントするための連続カウンタ（ｒｃｎｔ）が「１」に設定される（ステップＳ９２０）。また、ループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）が、ステップＳ９１３で検出されたループ個別履歴の開始アドレスに設定される（ステップＳ９２１）。このステップＳ９１８乃至Ｓ９２１の一連の処理により、ステップＳ９３０における処理の準備が完了する。
【０１６４】
そして、ステップＳ９１３で検出されたループ個別履歴が、反復される反復再利用区間の１番目の実行結果なのか否かが判断され、反復されている場合にはループ個別履歴の実行結果を主記憶部１３０に退避される実行結果退避処理が行われる（ステップＳ９３０）。
【０１６５】
ステップＳ９１５、Ｓ９１６およびＳ９３０の後に、探索アドレス（ｒａｄｒ）が履歴メモリ４３０の使用領域最終アドレスを超えたか否かが判断される（ステップＳ９２３）。ここでいう使用領域最終アドレスは、履歴メモリ４３０の履歴情報が登録される領域において、連続するアドレスに登録された順に格納された履歴情報のうち最後に登録された履歴情報が記録されている最後のアドレスである。
【０１６６】
そして、探索アドレス（ｒａｄｒ）が、使用領域の最終アドレスを超えていない場合には、ステップＳ９１２に戻り処理が繰り返される。一方、最終アドレスを超えている場合には、ループ個別履歴の退避処理は終了する。
【０１６７】
図１２は、本発明の実施の形態における履歴制御部５１０によるループ個別履歴の実行結果退避処理（ステップＳ９３０）の処理手順例を示すフローチャートである。
【０１６８】
まず、連続探索部６２０において、探索アドレス（ｒａｄｒ）が履歴メモリ４３０の使用領域最終アドレスを超えたか否かが判断される（ステップＳ９３１）。そして、探索アドレス（ｒａｄｒ）が使用領域の最終アドレスを超えていない場合には、探索アドレス（ｒａｄｒ）から識別子が読み出される（ステップＳ９３２）。続いて、読み出された識別子が、ループ個別履歴を指し示す「０１」であるか否かが判断される（ステップＳ９３３）。そして、識別子が「０１」でないと判断された場合には、ステップＳ９３８に進む。
【０１６９】
一方、識別子が「０１」であると判断された場合には、そのループ個別履歴に含まれる開始アドレスと、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）とが同一であるか否かが判断される（ステップＳ９３４）。そして、開始アドレスが同一でないと判断された場合には、ステップＳ９３８に進む。
【０１７０】
一方、開始アドレスが同一である場合には、ループ個別履歴のループカウンタ値が、連続カウンタ（ｒｃｎｔ）に「１」を加算した値（ｒｃｎｔ＋１）と同じ値であるか否かが判断される（ステップＳ９３５）。そして、ループカウンタ値と「ｒｃｎｔ＋１」とが同一でないと判断された場合には、ステップＳ９３８に進む。
【０１７１】
これらステップＳ９３４およびステップＳ９３５により、ステップＳ９３３で検出されたループ個別履歴は、図１１のステップＳ９１３において検出されたループ個別履歴を１回目のループとするループ個別履歴であるか否かが判定される。
【０１７２】
例えば、ステップＳ９３４において、ループ個別履歴に含まれる開始アドレスと、連続探索対象ループ開始アドレス（ｅｘ＿ａｄｒ）とが異なる場合には、異なる反復再利用区間のループ個別履歴が連続していると判断される。
【０１７３】
また、ステップＳ９３５において、ループ個別履歴に含まれるループカウンタ値が「ｒｃｎｔ＋１」とは異なっている場合には、同じ反復再利用区間が反復ではなく新たに１回目から実行されたと判断される。このステップＳ９３５の一例として、ループカウンタ値が「１」であり、「ｒｃｎｔ＋１」が「５」である場合を説明する。この場合には、図１１のステップＳ９１３で検出されたループ個別履歴の開始アドレスが指し示す反復再利用区間は、反復されて５回実行された後に、ステップＳ９３３で検出されたループ個別履歴の基となった実行から新たな反復になったと判断される。
【０１７４】
一方、ステップＳ９３５において、ループカウンタ値と「ｒｃｎｔ＋１」とが同一であると判断された場合には、連続カウンタ（ｒｃｎｔ）に「１」が加算される（ステップＳ９３６）。そして、（個別履歴アドレス数（ｙ）が探索アドレス（ｒａｄｒ）に足されることによって、探索アドレス（ｒａｄｒ）が更新される（ステップＳ９３７）。その後、ステップＳ９３７の処理が終わると、ステップＳ９３１に戻り処理が繰り返される。
【０１７５】
一方、ステップＳ９３１において、探索アドレス（ｒａｄｒ）が使用領域最終アドレスよりも大きな値のアドレスであると判断された場合には、連続カウンタ（ｒｃｎｔ）の値が「１」より大きいか否かが判断される（ステップＳ９３８）。これにより、図１１のステップＳ９１３で検出されたループ個別履歴は、反復された実行の一回目のループ個別履歴なのか、単独の実行のループ個別履歴なのかが判断される。そして、連続カウンタ（ｒｃｎｔ）の値が「１」以下であると判断された場合には、図１１のステップＳ９１３で検出されたループ個別履歴は単独の実行のループ個別履歴と判定し、実行結果退避処理を終了する。
【０１７６】
一方、連続カウンタ（ｒｃｎｔ）の値が「１」より大きいと判断された場合には、ループ個別履歴が履歴メモリ４３０から取得される（ステップＳ９３９）。このステップＳ９３９では、ループ個別履歴取得部６３０により、ループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）を最初のループ個別履歴の登録開始始点として連続カウンタ（ｒｃｎｔ）個のループ個別履歴が履歴メモリ４３０から取得される。
【０１７７】
続いて、退避履歴転送部６４０により、ループ個別履歴に基づいて退避履歴が生成され、その生成された退避履歴が主記憶部１３０に退避履歴開始アドレス（ｍａｄｒ）を始点として記憶される（ステップＳ９４０）。なお、ステップＳ９４０は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１７８】
次に、ループ個別履歴消去部５１２により、退避履歴の基となったループ個別履歴が履歴メモリから消去される（ステップＳ９４１）。なお、ステップＳ９４１は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１７９】
そして、ループ代表履歴登録部５１３により、ループ代表履歴がループ個別履歴開始アドレス（ｓｔａｒｔ＿ａｄｒ）に基づいて履歴メモリ４３０に登録される（ステップＳ９４２）。そして、実行結果退避処理は終了する。なお、ステップＳ９４２は、特許請求の範囲に記載の履歴制御手順の一例である。
【０１８０】
このように、本発明の実施の形態では、反復再利用区間のループ個別履歴のうち反復された実行に関するループ個別履歴のみを主記憶部１３０に退避させることができる。
【０１８１】
［本発明の実施の形態における履歴復元部５２０の動作例］
次に、本発明の実施の形態における履歴復元部５２０の処理について図面を参照して説明する。
【０１８２】
図１３は、本発明の実施の形態における履歴復元部５２０によるループ個別履歴の復元処理の処理手順例を示すフローチャートである。なお、ここでは、図１１および図１２と同様に、関数履歴と、ループ個別履歴と、ループ代表履歴と、退避履歴とは、それぞれ固定長のデータであることを想定する。また、ここでは、図１１および図１２と同様に、履歴メモリ４３０では、関数履歴と、ループ個別履歴と、ループ代表履歴とは連続するアドレスに登録された順に格納されるものとする。さらに、主記憶部１３０では、退避履歴は連続するアドレスに退避された順に格納されるものとする。また、ここでは、プログラムの実行の開始をフローチャートの開始とし、プログラムの実行の終了をフローチャートの終了とする。
【０１８３】
まず、フェッチ部３１０およびレジスタファイル３４０に、関数を参照する命令およびその関数の入力値が読み出される（ステップＳ９５１）。次に、命令デコーダ３２０によって、関数を参照する命令がデコードされる（ステップＳ９５２）。続いて、解読（デコード）した命令が再利用命令か否かが判断される（ステップＳ９５３）。そして、デコードした命令が再利用命令でないと判断された場合には、実行部３３０によって、レジスタファイル３４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９５４）。なお、ステップＳ９５４は、特許請求の範囲に記載の実行手順の一例である。
【０１８４】
一方、ステップＳ９５３の処理において、命令が再利用命令であると解読された場合には、検索要求入力部４２１によって、再利用区間の開始アドレスおよび入力値を用いて履歴メモリ４３０に履歴情報があるか否かが判断される（ステップＳ９５５）。このとき、再利用区間が反復再利用区間である場合には、開始アドレスおよび入力値に加えてループカウンタ値も用いて履歴メモリ４３０に履歴情報があるか否か探索される。
【０１８５】
そして、履歴情報が履歴メモリ４３０にないと判断された場合には、履歴登録部４４０によって、実行結果登録処理が行われる（ステップＳ９７０）。これにより、履歴メモリ４３０に実行履歴が登録される。
【０１８６】
一方、履歴情報が履歴メモリ４３０にあると判断された場合には、実行結果出力部４２２および履歴復元部５２０によって、実行結果出力処理が行われる（ステップＳ９８０）。これにより、実行している再利用区間の実行結果が履歴メモリ４３０から出力される。
【０１８７】
そして、ステップＳ９５４、Ｓ９７０およびＳ９８０の処理の後に、実行結果がレジスタファイル３４０に書き戻される（ステップＳ９５６）。続いて、プログラムの実行が終了したか否かが判断される（ステップＳ９５７）。そして、プログラムの実行が終了していないと判断された場合には、ステップＳ９５１に戻り処理が繰り返される。
【０１８８】
一方、プログラムの実行が終了したと判断された場合には、履歴復元部５２０によるループ個別履歴の復元処理が終了される。
【０１８９】
図１４は、本発明の実施の形態における実行結果登録処理（ステップＳ９７０）の処理手順例を示すフローチャートである。
【０１９０】
まず、実行部３３０によって、レジスタファイル３４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９７１）。次に、履歴登録部４４０によって、出力された実行結果を含む実行履歴を登録するための空き容量が履歴メモリ４３０にあるか否かが判断される（ステップＳ９７２）。なお、ステップＳ９７１は、特許請求の範囲に記載の実行手順の一例である。
【０１９１】
そして、実行履歴を登録するための空き容量が履歴メモリ４３０にないと判断された場合には、消去部４６０によって、前回の使用からの未使用期間が最も長い実行履歴が履歴メモリ４３０から１つ削除される（ステップＳ９７３）。そして、ステップＳ９７２に戻り処理が繰り返される。
【０１９２】
一方、実行履歴を登録するための空き容量が履歴メモリ４３０にあると判断された場合には、履歴登録部４４０により実行履歴が履歴メモリ４３０に登録される（ステップＳ９７４）、実行結果登録処理は終了する。
【０１９３】
図１５は、本発明の実施の形態における実行結果出力処理（ステップＳ９８０）の処理手順例を示すフローチャートである。なお、ここでは、関数履歴の実行結果と、ループ個別履歴の実行結果と、ループ代表履歴の退避履歴位置情報とを検索出力情報と表現することとする。
【０１９４】
まず、実行結果出力部４２２において、履歴メモリ４３０から図１３のステップＳ９５５で検索された履歴情報の検索出力情報が取得される（ステップＳ９８１）。次に、取得された検索出力情報がループ代表履歴の退避履歴位置情報であるか否かが判断される（ステップＳ９８２）。そして、取得された検索出力情報がループ代表履歴の退避履歴位置情報でないと判断された場合には、ステップＳ９９０に進む。
【０１９５】
一方、取得された検索出力情報がループ代表履歴の退避履歴位置情報であると判断された場合には、退避履歴取得部５２１によって、退避履歴位置情報が指し示す退避履歴が主記憶部１３０から取得される（ステップＳ９８３）。続いて、ループ個別履歴生成部５２２によって、退避履歴およびループ代表履歴に基づいてループ個別履歴が復元される（ステップＳ９８４）。次に、登録領域確保部５２３によって、履歴メモリ４３０からループ代表履歴が消去される（ステップＳ９８５）。その後、登録領域確保部５２３によって、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にあるか否かが判断される（ステップＳ９８６）。そして、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にないと判断された場合には、登録領域確保部５２３によって、前回の使用からの未使用期間が最も長い実行履歴が履歴メモリ４３０から１個削除される（ステップＳ９８７）。そして、ステップＳ９８６に戻り、処理が繰り返される。
【０１９６】
一方、ステップＳ９８６の処理において、ループ個別履歴を登録するための空き容量が履歴メモリ４３０にあると判断された場合には、ループ個別履歴登録部５２４によって、復元されたループ個別履歴が履歴メモリ４３０に登録される（ステップＳ９８８）。続いて、実行結果出力部４２２によって、復元されたループ個別履歴が検索される（ステップＳ９８９）。
【０１９７】
その後、検索された実行結果に基づいて実行結果が出力される（ステップＳ９９０）。そして、実行結果出力処理は終了する。
【０１９８】
このように、本発明の実施の形態では、主記憶部１３０に退避履歴として退避されたループ個別履歴を履歴メモリ４３０に復元して、その復元したループ個別履歴の実行結果を再利用することができる。
【０１９９】
これまでに示してきたように、本発明の実施の形態によれば、反復再利用区間のループ個別履歴の実行結果を主記憶部１３０に退避させることができる。これにより、実行結果を退避させない従来技術の場合と比べて履歴メモリ４３０に保持される履歴情報の数を増やすことができる。また、退避させた実行結果も実行結果の検索対象とすることができるため、その退避させた実行結果を用いて実行結果の再利用をすることができる。
【０２００】
また、本発明の実施の形態によれば、従来技術によるデータ処理装置１００と比較して、履歴メモリ４３０から有効な実行履歴が削除されることによる値再利用の効率の低下を防止することができる。さらに、本発明の実施の形態によれば、従来技術と比較して少ない容量の履歴メモリ４３０でも同等の効果が生じるため、履歴メモリ４３０を大きい容量とすることに伴う実行履歴の検索時間の増加による値再利用の効率の低下を防止することができる。
【０２０１】
また、本発明の実施の形態は、従来技術と比べて履歴メモリ４３０に保持される履歴情報の数を増やすことができるため、プログラムの投機実行などの場合において、特に顕著な効果が得られると考えられる。
【０２０２】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２０３】
例えば、本発明の実施の形態においては、主記憶部１３０に退避された実行結果を再利用する際に、退避履歴からループ個別履歴を復元して履歴メモリ４３０に登録し、その登録されたループ個別履歴から実行結果を出力する例を説明した。しかしながら、これに限定されるものではなく、主記憶部１３０に退避された実行結果を再利用する際に、ループ履歴を復元しないで実行結果を再利用する場合も考えられる。
【０２０４】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０２０５】
１００ データ処理装置
１２０ バス
１３０ 主記憶部
２００ 一次キャッシュ
２１０ 命令キャッシュ
２２０ データキャッシュ
３００ プロセッサコア
３１０ フェッチ部
３２０ 命令デコーダ
３３０ 実行部
３４０ レジスタファイル
４００ 履歴管理部
４１０ 履歴対象データ保持部
４２０ 履歴検索部
４２１ 検索要求入力部
４２２ 実行結果出力部
４３０ 履歴メモリ
４４０ 履歴登録部
４５０ 履歴メモリ容量管理部
４６０ 消去部
５００ 履歴変換部
５１０ 履歴制御部
５１２ ループ個別履歴消去部
５１３ ループ代表履歴登録部
５２０ 履歴復元部
５２１ 退避履歴取得部
５２２ ループ個別履歴生成部
５２３ 登録領域確保部
５２４ ループ個別履歴登録部
５３０ 退避領域管理部
６００ 退避履歴生成部
６１０ 先頭探索部
６２０ 連続探索部
６３０ ループ個別履歴取得部
６４０ 退避履歴転送部
６５０ ループ代表履歴生成部
【特許請求の範囲】
【請求項１】
命令区間を実行して実行結果を出力する実行部と、
前記命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御部と
を備えるデータ処理装置。
【請求項２】
前記履歴制御部は、前記履歴メモリに保持させる新たな前記実行履歴のデータ量が前記履歴メモリの空き容量よりも大きい場合には前記退避履歴を前記退避履歴保持部に供給する請求項１記載のデータ処理装置。
【請求項３】
前記退避履歴および前記代表履歴に基づいて前記実行履歴を前記履歴メモリに復元する履歴復元部と、
前記区間識別情報および前記入力値に基づいて前記復元された前記実行履歴を前記履歴メモリから検索した場合には前記復元された前記実行履歴に基づいて前記実行結果を出力する履歴検索部と
をさらに備える請求項１記載のデータ処理装置。
【請求項４】
前記履歴検索部は、前記区間識別情報および前記入力値に基づいて検索された前記実行履歴が前記代表履歴であった場合には前記復元部に前記実行履歴の復元を開始させる請求項３記載のデータ処理装置。
【請求項５】
前記履歴制御部は、前記退避履歴の個数を示す退避カウントをさらに含む前記代表履歴を生成し、
前記履歴復元部は、前記代表履歴における前記退避履歴を指し示す情報および前記退避カウントに基づいて前記退避履歴を前記退避履歴保持部から抽出して前記実行履歴を復元する
請求項３記載のデータ処理装置。
【請求項６】
前記実行部は、前記再利用区間の前記実行結果を供給する場合には前記反復再利用区間の前記実行履歴と前記反復再利用区間以外の前記実行履歴と前記代表履歴とを識別するための識別子をさらに出力し、
前記履歴メモリは、前記識別子を前記実行履歴としてさらに保持し、
前記履歴制御部は、前記識別子を用いて識別した前記実行履歴に基づいて前記退避履歴を供給し、前記識別子をさらに含む前記代表履歴を生成する
請求項１記載のデータ処理装置。
【請求項７】
前記反復再利用区間はサブルーチンであり、前記実行部は、前記サブルーチンの開始アドレスを前記区間識別情報として出力する請求項１記載のデータ処理装置。
【請求項８】
前記反復再利用区間はループであり、前記実行部は、前記ループの開始アドレスを前記区間識別情報として出力する請求項１記載のデータ処理装置。
【請求項９】
前記実行部は、前記反復再利用区間の前記実行結果を出力する場合には何回目の実行による前記実行結果であるかを示すカウンタ値をさらに出力し、
前記履歴メモリは、前記カウンタ値を前記実行履歴としてさらに保持し、
前記履歴制御部は、前記カウンタ値を含む前記退避履歴を出力する
請求項８記載のデータ処理装置。
【請求項１０】
実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を退避履歴として前記履歴メモリから外部の記憶部に退避させ、前記退避の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御部と
を備える履歴保存装置。
【請求項１１】
命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と
を備えるコンピュータにおけるデータ処理方法であって、
前記命令区間を実行して実行結果を出力する実行手順と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に
供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御手順と
を備えるデータ処理方法。
【請求項１２】
命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と
を備えるコンピュータにおけるプログラムであって、
前記命令区間を実行して実行結果を出力する実行手順と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に
供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御手順と
をコンピュータに実行させるプログラム。
【請求項１】
命令区間を実行して実行結果を出力する実行部と、
前記命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御部と
を備えるデータ処理装置。
【請求項２】
前記履歴制御部は、前記履歴メモリに保持させる新たな前記実行履歴のデータ量が前記履歴メモリの空き容量よりも大きい場合には前記退避履歴を前記退避履歴保持部に供給する請求項１記載のデータ処理装置。
【請求項３】
前記退避履歴および前記代表履歴に基づいて前記実行履歴を前記履歴メモリに復元する履歴復元部と、
前記区間識別情報および前記入力値に基づいて前記復元された前記実行履歴を前記履歴メモリから検索した場合には前記復元された前記実行履歴に基づいて前記実行結果を出力する履歴検索部と
をさらに備える請求項１記載のデータ処理装置。
【請求項４】
前記履歴検索部は、前記区間識別情報および前記入力値に基づいて検索された前記実行履歴が前記代表履歴であった場合には前記復元部に前記実行履歴の復元を開始させる請求項３記載のデータ処理装置。
【請求項５】
前記履歴制御部は、前記退避履歴の個数を示す退避カウントをさらに含む前記代表履歴を生成し、
前記履歴復元部は、前記代表履歴における前記退避履歴を指し示す情報および前記退避カウントに基づいて前記退避履歴を前記退避履歴保持部から抽出して前記実行履歴を復元する
請求項３記載のデータ処理装置。
【請求項６】
前記実行部は、前記再利用区間の前記実行結果を供給する場合には前記反復再利用区間の前記実行履歴と前記反復再利用区間以外の前記実行履歴と前記代表履歴とを識別するための識別子をさらに出力し、
前記履歴メモリは、前記識別子を前記実行履歴としてさらに保持し、
前記履歴制御部は、前記識別子を用いて識別した前記実行履歴に基づいて前記退避履歴を供給し、前記識別子をさらに含む前記代表履歴を生成する
請求項１記載のデータ処理装置。
【請求項７】
前記反復再利用区間はサブルーチンであり、前記実行部は、前記サブルーチンの開始アドレスを前記区間識別情報として出力する請求項１記載のデータ処理装置。
【請求項８】
前記反復再利用区間はループであり、前記実行部は、前記ループの開始アドレスを前記区間識別情報として出力する請求項１記載のデータ処理装置。
【請求項９】
前記実行部は、前記反復再利用区間の前記実行結果を出力する場合には何回目の実行による前記実行結果であるかを示すカウンタ値をさらに出力し、
前記履歴メモリは、前記カウンタ値を前記実行履歴としてさらに保持し、
前記履歴制御部は、前記カウンタ値を含む前記退避履歴を出力する
請求項８記載のデータ処理装置。
【請求項１０】
実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を退避履歴として前記履歴メモリから外部の記憶部に退避させ、前記退避の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御部と
を備える履歴保存装置。
【請求項１１】
命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と
を備えるコンピュータにおけるデータ処理方法であって、
前記命令区間を実行して実行結果を出力する実行手順と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に
供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御手順と
を備えるデータ処理方法。
【請求項１２】
命令区間のうち実行結果が再び利用される再利用区間の区間識別情報と入力値と実行結果とを実行履歴として保持し、前記保持した実行結果が再び利用される場合には前記区間識別情報および前記入力値に基づいて前記実行履歴が検索される履歴メモリと、
前記再利用区間のうち実行が反復される反復再利用区間の各回の前記実行結果を前記履歴メモリから退避させるための退避履歴を保持する退避履歴保持部と
を備えるコンピュータにおけるプログラムであって、
前記命令区間を実行して実行結果を出力する実行手順と、
前記反復再利用区間の前記実行履歴に基づいて前記退避履歴を前記退避履歴保持部に
供給し、前記退避履歴の供給の際に前記退避履歴の基となった前記実行履歴を前記履歴メモリから消去して前記退避履歴を指し示す情報を含む代表履歴を前記履歴メモリに保持させる履歴制御手順と
をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１１−３９８５９（Ｐ２０１１−３９８５９Ａ）
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願番号】特願２００９−１８７６２５（Ｐ２００９−１８７６２５）
【出願日】平成２１年８月１３日（２００９．８．１３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願日】平成２１年８月１３日（２００９．８．１３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]