(57)【要約】【課題】処理中のプログラムへのアクセスの高速化が望まれている。【解決手段】メインメモリ２０には、プログラムを分割したキャッシュブロック４２を格納する。各キャッシュブロック４２の他のキャッシュブロック４２への分岐位置には、分岐先のキャッシュブロック４２のロード等の処理を行う分岐解決ルーチンを起動する命令を埋め込む。ローカルメモリ１６にはキャッシュブロック４２単位でロードを行い、格納領域の区画である第１バンク３０ａ〜第ｎバンク３０ｎに順次格納する。ローカルメモリ１６内でのアドレス管理、キャッシュブロックのコピー３２の破棄時の処理等はアドレス変換テーブル３４、バンク間参照テーブル３８、世代番号テーブル３９を参照して行う。【選択図】図２
2008234490.tif 000002
【特許請求の範囲】
【請求項１】
一のプログラムを分割して得られた複数のプログラムブロックを格納したメインメモリと、
前記複数のプログラムブロックのうち少なくとも一のプログラムブロックのコピーを格納したローカルメモリと、
前記プログラムブロックの単位で前記メインメモリからロードを行うことにより前記ローカルメモリに格納したプログラムブロックのコピーを参照して処理を実行するプロセッサと、
を備え、
前記プロセッサは、実行中の前記プログラムブロックのコピーにおいて別のプログラムブロックに記述された命令へ分岐する必要が生じた際、前記ローカルメモリ内に分岐先のプログラムブロックのコピーが存在するか否かを判定し存在しなければ前記メインメモリから当該分岐先のプログラムブロックをロードする分岐解決ルーチンを実行して、前記分岐先のプログラムブロックのコピーを前記ローカルメモリに格納することを特徴とする情報処理装置。
【請求項２】
前記プロセッサは、実行中の前記プログラムブロックに記述された前記分岐解決ルーチンを起動する命令に従い前記分岐解決ルーチンを起動することにより、前記分岐解決ルーチンを実行することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記プロセッサは、前記分岐解決ルーチンを実行して前記分岐先のプログラムブロックのコピーを前記ローカルメモリへ格納した後、実行中のプログラムブロックに、前記分岐先のプログラムブロックのコピーに記述された命令へ分岐する分岐命令を書き込み、前記分岐命令を参照して分岐処理を実行することを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記ローカルメモリは、前記ローカルメモリにコピーされたプログラムブロックの前記メインメモリにおける格納領域の先頭アドレスと、前記ローカルメモリにおける当該プログラムブロックのコピーの格納領域の先頭アドレスとを対応づけたアドレス変換テーブルをさらに格納し、
前記プロセッサは、前記分岐解決ルーチンにおいて前記分岐先のプログラムブロックの前記メインメモリにおける格納領域の先頭アドレスに基づき前記アドレス変換テーブルを検索することにより、前記ローカルメモリ内に前記分岐先のプログラムブロックのコピーが存在するか否かを判定するとともに、存在した場合に前記分岐先のプログラムブロックのコピーの前記ローカルメモリにおける格納領域の先頭アドレスを取得することを特徴とする請求項１または２に記載の情報処理装置。
【請求項５】
前記プロセッサは、前記プログラムブロックを前記ローカルメモリにロードする際、当該プログラムブロックにおいて必要な別のプログラムブロックに記述された命令への分岐ごとに、分岐先のプログラムブロックの前記メインメモリ内の格納領域の先頭アドレスを記録した分岐先テーブルを共にロードし、
前記分岐解決ルーチンを実行する際、前記分岐先テーブルを参照して前記分岐先のプログラムブロックの前記メインメモリ内の格納領域の先頭アドレスを取得し、前記アドレス変換テーブルを検索することを特徴とする請求項４に記載の情報処理装置。
【請求項６】
前記アドレス変換テーブルは、前記ローカルメモリに格納された前記プログラムブロックのコピーの格納順序をさらに記録し、
前記プロセッサは、前記分岐解決ルーチンにおいて、前記分岐先のプログラムブロックを前記ローカルメモリにロードする際、前記ローカルメモリの未使用領域が不足している場合は、前記アドレス変換テーブルを参照して、最前に前記ローカルメモリに格納されたプログラムブロックのコピーから順に破棄していくことにより前記分岐先のプログラムブロックのコピーを格納する領域を確保することを特徴とする請求項４または５に記載の情報処理装置。
【請求項７】
前記分岐先テーブルは、前記プログラムブロックにおいて必要な別のプログラムブロックに記述された命令への分岐ごとに、前記分岐先のプログラムブロックの前記メインメモリ内の格納領域の先頭アドレスと当該分岐先のプログラムブロックに記述された分岐先の命令のアドレスとの差分であるオフセット値をさらに記録し、
前記プロセッサは、前記アドレス変換テーブルから取得した前記ローカルメモリにおける前記分岐先のプログラムブロックのコピーの格納領域の先頭アドレスと、前記分岐先テーブルから取得した前記オフセット値とに基づき、前記ローカルメモリ内の分岐先の命令のアドレスを算出し、前記別のプログラムブロックに記述された命令へ分岐する分岐命令を実行中のプログラムブロックのコピーに書き込むことを特徴とする請求項５に記載の情報処理装置。
【請求項８】
前記別のプログラムブロックに記述された命令への分岐が、当該別のプログラムブロックに記述された関数の呼び出しであった場合に、前記関数を呼び出すごとに、呼び出し元のプログラムブロックのコピー内の戻り先アドレスを順次記録したスタックを格納したレジスタをさらに備え、
前記プロセッサは、分岐先のプログラムブロックのコピーから呼び出し元のプログラムブロックのコピーへ戻る分岐を行う際、前記スタックを参照して前記戻り先アドレスを取得することにより分岐処理を実行することを特徴とする請求項１または２に記載の情報処理装置。
【請求項９】
前記プロセッサは、前記別のプログラムブロックのコピーに記述された関数を処理中に、前記スタックに記録された戻り先アドレスを含む前記呼び出し元のプログラムブロックのコピーのいずれかを破棄する必要が生じた際、前記スタックの該当戻り先アドレスを所定の無効アドレスに書き換え、
呼び出し元のプログラムブロックのコピーへ戻る分岐を行う際、前記スタックに前記無効アドレスが記録されていたら、前記ローカルメモリ内に前記呼び出し元のプログラムブロックのコピーが存在するか否かを判定し、存在しなければ前記メインメモリから前記呼び出し元のプログラムブロックをロードすることを特徴とする請求項８に記載の情報処理装置。
【請求項１０】
ローカルメモリに格納した、プログラムの一部であるプログラムブロックを参照して処理を実行するステップと、
前記実行するステップにおいて別のプログラムブロックに記述された命令へ分岐する必要が生じた際、前記別のプログラムブロックが前記ローカルメモリに格納されているか否かを判定し、格納されていなければメインメモリから前記別のプログラムブロックをロードするステップと、
ロードした前記別のプログラムブロックへ処理を分岐するステップと、
を含むことを特徴とする情報処理方法。
【請求項１１】
前記分岐するステップは、ロードした前記別のプログラムブロックに記述された命令へ分岐する分岐命令を、実行中の前記プログラムブロックに書き込むステップと、
前記分岐命令を参照して分岐処理を実行するステップと、
を含むことを特徴とする請求項１０に記載の情報処理方法。
【請求項１２】
ローカルメモリにロードした、アプリケーションプログラムの一部であるプログラムブロックを参照して処理を実行中、別のプログラムブロックに記述された命令へ分岐する必要が生じた際、前記別のプログラムブロックが前記ローカルメモリに格納されているか否かを判定し、格納されていなければメインメモリから前記別のプログラムブロックをロードする機能と、
ロードした前記別のプログラムブロックに記述された命令へ分岐する分岐命令を、実行中の前記プログラムブロックに書き込む機能と、
をコンピュータに実現させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理技術に関し、階層構造をなすメモリを備えた情報処理装置およびそれに適用される情報処理方法に関する。
【背景技術】
【０００２】
近年の情報処理技術の発展により、ＣＤ−ＲＯＭなどの記録媒体に記録されたソフトウェアやネットワーク上のサーバからダウンロードしたソフトウェアなどを起動させることにより、一の情報処理装置に対して多種多様な機能を発揮させることが容易にできるようになった。そのような状況において、いかに効率よく高速にプログラムを処理していくかは常に重要な課題となってきた。
【０００３】
処理を高速化させるためには、単にプロセッサの処理能力を向上させるばかりでなく、プロセッサユニット間、プロセッサユニットとメモリ間など、情報処理装置内での各ユニット間のデータ転送速度を向上させる必要がある。プロセッサがメモリに格納されたデータやプログラムに高速にアクセスするための技術のひとつがキャッシュメモリによるメモリの階層化である。キャッシュメモリは一般に、メインメモリより容量が小さくアクセスを高速に行うことのできるメモリである。キャッシュメモリにアクセス頻度の高いデータを格納しておくことにより、メインメモリへのアクセス回数を減らし、全体としてデータアクセスに要する時間を削減することができる。複数のプロセッサを備えたマルチプロセッサシステムにおいても、プロセッサごとにローカルメモリを設けることにより、より多くのデータに対する高速なアクセスを可能にしている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
プロセッサがプログラムを高速処理するためには、そのマシンコードに対しても高速にアクセスする必要がある。ところが高速アクセスが可能なメモリ、すなわち高速メモリは一般的にその容量が小さいため、プログラムの規模によってはその全体を高速メモリに格納することができない場合も多い。この場合、プログラマは手作業でプログラムを複数のモジュールに分割し、さらに、これらのモジュールを適当なタイミングでメインメモリから高速メモリにロードするためのプログラムを記述する必要があった。
【０００５】
本発明はこのような課題に鑑みてなされたものであり、その目的は、プログラムへの高速アクセスの効率化を可能にする技術を提供することにある。
【課題を解決するための手段】
【０００６】
本発明のある態様は情報処理装置に関する。この情報処理装置は、一のプログラムを分割して得られた複数のプログラムブロックを格納したメインメモリと、複数のプログラムブロックのうち少なくとも一のプログラムブロックのコピーを格納したローカルメモリと、プログラムブロックの単位でメインメモリからロードを行うことによりローカルメモリに格納したプログラムブロックのコピーを参照して処理を実行するプロセッサと、を備え、プロセッサは、実行中のプログラムブロックのコピーにおいて別のプログラムブロックに記述された命令へ分岐する必要が生じた際、ローカルメモリ内に分岐先のプログラムブロックのコピーが存在するか否かを判定し存在しなければメインメモリから当該分岐先のプログラムブロックをロードする分岐解決ルーチンを実行して、分岐先のプログラムブロックのコピーをローカルメモリに格納することを特徴とする。
【０００７】
本発明の別の態様は情報処理方法に関する。この情報処理方法は、ローカルメモリに格納した、プログラムの一部であるプログラムブロックを参照して処理を実行するステップと、実行するステップにおいて別のプログラムブロックに記述された命令へ分岐する必要が生じた際、前記別のプログラムブロックが前記ローカルメモリに格納されているか否かを判定し、格納されていなければメインメモリから別のプログラムブロックをロードするステップと、ロードした別のプログラムブロックへ処理を分岐するステップと、を含むことを特徴とする。
【０００８】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【０００９】
本発明によれば、プログラムへのアクセスの高速化を容易に実現することができる。
【発明を実施するための最良の形態】
【００１０】
図１は本実施の形態における情報処理装置の構造を示している。情報処理装置１０は、プロセッサ１４、ローカルメモリ１６、レジスタ１８を含むプロセッサユニット１２、メインメモリ２０、記憶装置２２、および入出力装置２４を含み、それぞれがバス２８を介して互いにデータの送受を行う。プロセッサユニット１２は接続したＭＦＣ（Memory Flow Controller）のＤＭＡ（Direct Memory Access）を起動させることによりデータの転送を実現させてもよいが、ここではその図示を省略する。
【００１１】
同図ではプロセッサユニット１２が２つ示されているが、その数は２つに限られず、１つまたは３つ以上でもよい。また各プロセッサ１４が対等の機能を発揮することにより複数のプロセスまたはスレッドを並列処理してもよいし、グラフィックプロセッサ、Ｉ／Ｏプロセッサなど特定の機能を発揮するものが含まれていてもよい。
【００１２】
プロセッサユニット１２のプロセッサ１４はユーザが起動したアプリケーションソフトウェアなどのプログラムを実行する。ローカルメモリ１６は例えばプロセッサ１４と同一のチップまたは近隣に配置された高速アクセスが可能なＳＲＡＭ（Static Random Access Memory）などで構成され、メインメモリ２０にロードされたアプリケーションプログラムの一部や、処理に必要なデータ、処理結果のデータなどが適宜格納される。レジスタ１８はプロセッサ１４における処理で必要な値を一時的に保持する一般的なレジスタで構成してよい。本実施の形態では特に、ローカルメモリ１６に格納されたプログラムを管理するためのデータ、スタックなども格納する。
【００１３】
メインメモリ２０は例えばＤＲＡＭ（Dynamic Random Access Memory）などで構成され、ユーザが起動したアプリケーションなどのプログラム全体を格納する。メインメモリ２０はその他にも複数のプロセッサユニット１２間でデータをやりとりするための共有メモリやＯＳを動作させるためのシステムメモリなどの機能を果たしてもよい。記憶装置２２はハードディスク装置、ＣＤ−ＲＯＭなどの記録媒体とその読み取り装置など一般的に用いられる記憶装置のいずれかまたは組み合わせでよく、アプリケーションプログラムと処理に必要なデータ、処理の途中や終了時などに保存すべきデータなどを記憶する。入出力装置２４はアプリケーションの起動をはじめとして情報処理装置１０に対しユーザが行う指示入力や処理結果の出力などを行い、キーボード、コントローラ、ポインティングデバイスなどの入力装置、表示装置、スピーカー、プリンターなどの出力装置のいずれかまたは組み合わせでよい。
【００１４】
本実施の形態では、記憶装置２２に記憶されたプログラムなどを、まずメインメモリ２０にロードし、各プロセッサユニット１２において実行される処理に応じてプログラムの一部をメインメモリ２０からローカルメモリ１６にロードする。これにより、プロセッサ１４はプログラムの進捗ごとにメインメモリ２０にアクセスし直す必要がなくなる。アクセスを可能な限りプロセッサユニット１２内で閉じることよって、ソフトウェアの処理を高速化する。このような場合、従来の手法では、あらかじめプログラムを記述する段階で、ローカルメモリ１６に格納できる大きさのモジュールに分割しておくとともに、それらのモジュールをローカルメモリ１６にロードするためのプログラムを記述しておく必要があった。
【００１５】
そのため、ゲームやシミュレーションのソフトウェアなど、高度な機能を提供する、長大で複雑なプログラムを作成したりデバッグしたりする際は特に、その効率化が望まれていた。そこで本実施の形態では、コンパイラによって自動的に命令をキャッシュできるようにする。これによりプログラム記述時にはローカルメモリ１６へのロード操作について考慮せずに済み、プログラマの負担も軽減させることができる。具体的には、ローカルメモリ１６内に存在しない命令までプログラムの実行が進んだとき、コンパイラの実行時ルーチンが自動的に以下の処理を行う。
（１）不要な命令を予測してローカルメモリ１６から削除する。
（２）必要な命令をメインメモリ２０からローカルメモリ１６にロードする。
【００１６】
図２はローカルメモリ１６とメインメモリ２０に格納されるデータの構成を模式的に示している。まずメインメモリ２０には、本実施の形態におけるコンパイラによってコンパイルされたプログラムが記憶装置２２からロードされる。本実施の形態におけるコンパイラはプログラムのコンパイルを行う際、所定の基準でプログラムを分割しプログラムのブロックを形成する。メインメモリ２０からローカルメモリ１６へのプログラムのロードはこのブロック単位で行う。ブロックのデータサイズは当然、ローカルメモリ１６の容量以下とする。以後、このブロックをキャッシュブロック４２と呼ぶ。従ってメインメモリ２０には図２に示すように、プログラムとして複数のキャッシュブロック４２が格納される。
【００１７】
１つのキャッシュブロック４２を構成するプログラムは、例えば連続したプログラムを、所定のサイズの範囲に入るように、分割可能な位置で分割したものでもよいし、集中して連続的に参照される関数群を経験則などから導出してあらかじめ設定しておき、コンパイル時にプログラムから抽出するようにしてもよい。あるいは関数より大きな単位でまず基本的なブロックに分割し、それをサイズや処理内容などに鑑みまとめ直すことによりキャッシュブロック４２としてもよい。ここで基本ブロックとは、分割可能な最小単位である関数などを処理内容などに応じてまとめたものでよい。いずれにしてもコンパイラが自動的にキャッシュブロックを形成することが望ましいが、プログラマがあらかじめ設定した関数、分割位置などを呼び出すことによってキャッシュブロックの範囲を手動で指定できるようにして、一部、プログラマの意思を反映できるようにしてもよい。
【００１８】
ローカルメモリ１６には前述のとおり、メインメモリ２０からロードされた少なくとも１つのキャッシュブロック４２、すなわちキャッシュブロックのコピー３２が格納される。キャッシュブロックのコピー３２はプログラムの一部であるため、あるキャッシュブロックのコピー３２を参照して処理を行っている途中で別のキャッシュブロックのコピー３２中の命令へ分岐したり関数を呼び出したりする必要が生じる。このとき分岐先のキャッシュブロックのコピー３２がローカルメモリ１６に存在しなければ、コンパイラが提供するルーチンによってメインメモリ２０より該当するキャッシュブロック４２を特定しローカルメモリ１６にコピーする。このような処理を行うルーチンを分岐解決ルーチンと呼ぶ。分岐解決ルーチンの具体的な処理手順は後に説明する。
【００１９】
ローカルメモリ１６には第１バンク３０ａ、第２バンク３０ｂ、・・・、第ｎバンク３０ｎという区分けされたｎ個の記憶領域を設け、メインメモリ２０からロードしたキャッシュブロックのコピー３２は第１バンク３０ａの先頭アドレスから順に格納していく。格納が進み、未使用領域が不足したら、すなわち、新たなキャッシュブロックのコピー３２が最終のバンクである第ｎバンク３０ｎに収まらなくなったら、第１バンク３０ａに以前格納したキャッシュブロックのコピー３２を全て破棄し（以後、バンクの無効化と呼ぶ）、新たなキャッシュブロックのコピー３２を順次格納していく。以後、第２バンク３０ｂから第ｎバンク３０ｎまでを順次無効化して再利用する。
【００２０】
図２に示すように、ローカルメモリ１６は、キャッシュブロックのコピー３２以外にアドレス変換テーブル３４、バンク間参照テーブル３８、世代番号テーブル３９を格納する。アドレス変換テーブル３４は、あるキャッシュブロック４２を格納したメインメモリ２０内のアドレスと、そのコピーを格納したローカルメモリ１６内のアドレスとを対応づけたテーブルであり、プロセッサ１４が分岐先のキャッシュブロックのコピー３２を参照するためにローカルメモリ１６内のアドレスを特定したり、必要なキャッシュブロックのコピー３２がローカルメモリ１６内に存在するか否かを判断するために参照される。
【００２１】
バンク間参照テーブル３８は第１バンク３０ａ、第２バンク３０ｂ、・・・、第ｎバンク３０ｎのそれぞれに対応して１つずつ用意され、別のバンク、例えば第ｎバンク３０ｎに格納されたキャッシュブロックのコピー３２が、自らのバンク、例えば第２バンク３０ｂに格納されたキャッシュブロックのコピー３２へ分岐している場合に、その分岐元のキャッシュブロックのコピー３２に記述された分岐命令列の位置を記録したテーブルである。世代番号テーブル３９はバンクごとに世代番号と呼ばれる番号を保持し、各世代番号は対応するバンクが無効化されるごとにインクリメントされる。バンク間参照テーブル３８と世代番号テーブル３９を参照することにより、分岐先のキャッシュブロックのコピー３２を格納したバンクが無効化され、それまで分岐先として使用していたローカルメモリ１６内のアドレスがもはや無効であることが認識できる。
【００２２】
図３はメインメモリ２０にロードされるキャッシュブロックを形成するとともに分岐解決ルーチンを実行するコンパイラの構造を示している。図３において、様々な処理を行う機能ブロックとして記載される各要素は、ハードウェア的には、ＣＰＵ、メモリ、その他のＬＳＩで構成することができ、ソフトウェア的にはプログラムなどによって実現される。したがって、これらの機能ブロックがハードウェアのみ、ソフトウェアのみ、またはそれらの組合せによっていろいろな形で実現できることは当業者には理解されるところであり、いずれかに限定されるものではない。例えばコンパイラ１００は対応するソフトウェアをロードした情報処理装置１０の一部によって実現してもよい。
【００２３】
コンパイラ１００はプログラムからキャッシュブロック４２を形成するコンパイル部１０２と、分岐解決ルーチンを実行する分岐解決ルーチン実行部１１０とを含む。コンパイル部１０２は、上述のような所定の規則でプログラムを分割するプログラム分割部１０４と、別のキャッシュブロック４２へ処理を分岐するに当たり分岐解決ルーチンを起動する命令などをプログラムに埋め込む命令埋め込み部１０６と、各分岐処理において分岐解決ルーチンを実行するために必要な、分岐先のキャッシュブロック４２に係る情報を、分岐元のキャッシュブロックに付加する分岐先情報付加部１０８と、を含む。分岐先情報付加部１０８によって付加される情報については後述する。
【００２４】
分岐解決ルーチン実行部１１０は命令埋め込み部１０６によって埋め込まれた命令によって起動される分岐解決ルーチンを実行する。分岐解決ルーチン実行部１１０はユーザが情報処理装置１０において起動したプログラムの実行中に動作するため、その実体はプロセッサ１４であってよい。
【００２５】
次に図２で示したキャッシュブロック４２、アドレス変換テーブル３４、バンク間参照テーブル３８、世代番号テーブル３９の構成について詳述する。図４はメインメモリ２０に格納された２つのキャッシュブロック４２ａ、４２ｂの構造を模式的に示している。ここでキャッシュブロック４２ａ中の処理はキャッシュブロック４２ｂ中の処理に分岐するとする。
【００２６】
コンパイラ１００が生成するキャッシュブロック４２ａは、プログラム分割部１０４が分割したプログラム本体４４と、コンパイラ１００の分岐先情報付加部１０８が付加した情報である分岐先テーブル４６とで構成される。この構成はどのキャッシュブロック４２についても同様である。分岐先テーブル４６はプログラム本体４４に記述されたプログラムが別のキャッシュブロック４２への分岐を含むとき、その情報を記録したテーブルであり、１つの分岐に対し１つのエントリが記述される。
【００２７】
分岐先テーブル４６の各エントリは、分岐先キャッシュブロックアドレス欄５２、分岐先キャッシュブロックサイズ欄５４、分岐先命令オフセット欄５６、分岐種別欄５８を含む。分岐先キャッシュブロックアドレス欄５２には分岐先の命令が格納されているキャッシュブロック４２ｂのメインメモリ２０内の先頭アドレス、図４の例では「Ｘ」が記録される。分岐先キャッシュブロックサイズ欄５４には当該キャッシュブロック４２ｂのデータサイズ、図４の例では「Ｓ」が記録される。以後、場合によってメインメモリ２０内のアドレスはメインアドレス、ローカルメモリ１６内のアドレスはローカルアドレスと呼んで区別する。
【００２８】
分岐先命令オフセット欄５６には、分岐先の命令が記述されたメインアドレスの、当該キャッシュブロック４２ｂの先頭メインアドレスからのオフセット値が記録される。図４の例で分岐先の命令がメインアドレス「Ｙ」の破線５０で示された位置に記述されていたとすると、オフセット値は「Ｙ−Ｘ」となる。分岐種別欄５８には当該分岐が単なる分岐か関数呼び出しか、の分岐の種別を識別する情報が記録される。図４の例では「０」か「１」かで識別するとして、「０」が記録されている。
【００２９】
さらにコンパイラ１００の命令埋め込み部１０６は上述のとおり、あるキャッシュブロック４２ａのプログラム本体４４において他のキャッシュブロック４２ｂへの分岐命令があった場合、当該分岐処理をローカルメモリ１６内で実現するための命令列４８を生成して埋め込む。命令列４８は、分岐先テーブル４６のうち対応する分岐を示すエントリが記述されたローカルメモリ１６内のアドレス、すなわちローカルアドレスをレジスタに格納する命令列と、前述の分岐解決ルーチンを起動する命令列とを含む。図４では前者は「ｒｘ ＝ ＰＣ ＋ Ｂ − Ａ」、後者は「ｃａｌｌ ｒｕｎｔｉｍｅ ｒｏｕｔｉｎｅ」なる命令列で記述されている。
【００３０】
ここで「ｒｘ」はレジスタの値、「ＰＣ」はローカルメモリ１６内にキャッシュブロック４２ａがコピーされたときの命令列４８のローカルアドレスである。命令列４８のローカルアドレス「ＰＣ」に、生成した命令列のメインアドレス「Ａ」から分岐先テーブル４６の該当エントリのメインアドレス「Ｂ」へのオフセット値「Ｂ−Ａ」を加算することによって、ローカルメモリ１６内での分岐先テーブルのエントリのアドレスを得ることができる。
【００３１】
命令列４８はその他に、関数呼び出しから戻る際に、ローカルメモリ１６において戻る先のキャッシュブロックのコピー３２が破棄されていた場合の処理を行う命令などを含んでよい。当該処理については後に述べる。
【００３２】
なお上述のとおりキャッシュブロック４２を、元のプログラムに含まれる関数、または元のプログラムを分割してなる基本ブロックを寄せ集めた集合体とした場合、一のキャッシュブロック４２内に分岐元、分岐先の双方が存在する場合がある。この場合、分岐先情報付加部１０８は当該分岐については分岐先テーブル４６に対するエントリを行わなくてよい。そして命令埋め込み部１０６は、命令列４８として、分岐先テーブル４６のローカルアドレスをレジスタに格納する命令列や分岐解決ルーチンを起動する命令列を埋め込まず、単に分岐先のローカルアドレスへ分岐する命令を埋め込む。これは例えば、分岐先までのメインアドレスのオフセット値に命令列４８のローカルアドレス「ＰＣ」を加算したアドレスへの分岐命令によって実現できる。
【００３３】
図５は、図４に示したメインメモリ２０内の２つのキャッシュブロック４２ａ、４２ｂのローカルメモリ１６内のコピーであるキャッシュブロックのコピー３２ａ、３２ｂと、アドレス変換テーブル３４の構造を模式的に示している。アドレス変換テーブル３４は、アドレス変換テーブルヘッダ部３４ａと、アドレス変換テーブルエントリ部３４ｂ、３４ｃとで構成される。後述するようにメインメモリ２０からローカルメモリ１６にキャッシュブロック４２ａ、４２ｂをロードする場合は、まずキャッシュブロックのコピー３２ａ、３２ｂを格納する領域を確保し、その先頭領域にアドレス変換テーブルエントリ部３４ｂ、３４ｃを書き込み、その直後の領域にキャッシュブロックのコピー３２ａ、３２ｂを格納するようにする。
【００３４】
本実施の形態ではキャッシュブロック４２ａ、４２ｂのメインメモリ２０内でのアドレスをキーに、キャッシュブロックのコピー３２ａ、３２ｂのローカルアドレスを効率よく特定するために、アドレス変換テーブル３４をハッシュテーブルとして構造化する。したがってアドレス変換テーブルヘッダ部３４ａは、メインメモリ内のアドレス、またはその一部をインデックスとして、所望のキャッシュブロックのコピー３２ａ、３２ｂに対応するアドレス変換テーブルエントリ部３４ｂ、３４ｃへのポインタを格納する。この場合のアドレス変換テーブル３４については図６で詳述するが、メインメモリ２０のアドレスからローカルメモリ１６のアドレスを特定できるテーブルであればハッシュテーブルの構造でなくてもよい。
【００３５】
キャッシュブロックのコピー３２ａもプログラム本体６２と分岐先テーブル６４を含み、保持するデータ内容はメインメモリ２０におけるキャッシュブロック４２ａとほぼ同じである。ただし分岐先のキャッシュブロック４２ｂのロードが完了し、キャッシュブロックのコピー３２ｂのローカルメモリ１６内での格納領域が確定した時点で、分岐解決ルーチンは自らのルーチンを呼び出した命令列４８を、分岐先の命令への分岐命令列６６に置き換える。図５において、分岐先のキャッシュブロックのコピー３２ｂにおける分岐先の命令が記述されたアドレスが「Ｙ'」であるとき、分岐元のキャッシュブロックのコピー３２ａにおける命令列６６では「Jump to Y'」なる命令に置き換えられる。このようにすることで、以後の処理で同じ分岐命令に到達した際は、分岐解決ルーチンの介在なく適したアドレスへの分岐処理を行うことができる。
【００３６】
図６はアドレス変換テーブル３４の構造を模式的に示している。アドレス変換テーブル３４は前述のとおり、アドレス変換テーブルヘッダ部３４ａとアドレス変換テーブルエントリ部３４ｂ〜３４ｈとを含む。アドレス変換テーブル３４は分岐解決ルーチンが実行され新たなキャッシュブロック４２がローカルメモリ１６にロードされる際、その格納領域の確保とともに更新される。またロードされたキャッシュブロックのコピー３２が破棄される際も更新される。
【００３７】
アドレス変換テーブルヘッダ部３４ａは例えばメインメモリ２０内のキャッシュブロック４２の格納領域におけるアドレスの下位数ビットごとに欄を設ける。そして各欄に該当するメインメモリ２０内のアドレスのいずれかに格納されたキャッシュブロック４２をローカルメモリ１６にロードするときに、生成したアドレス変換テーブルエントリ部３４ｂのローカルアドレスをアドレス変換テーブルヘッダ部３４ａの対応する欄に書き込む。
【００３８】
アドレス変換テーブルヘッダ部３４ａの各欄は、メインメモリ２０内のアドレスの一部に対応するため、図６のアドレス変換テーブルエントリ部３４ｂ、３４ｃのように、同じ欄に対応するメインメモリ２０内の複数のアドレスに格納された複数のキャッシュブロック４２がロードされる場合がある。そのため各アドレス変換テーブルエントリ部３４ｂ〜３４ｈにはそれぞれ、自らに対応するキャッシュブロック４２のメインメモリ内２０でのアドレスとともに、同図の実線矢印７０、７２、破線矢印７４で示したように、別のアドレス変換テーブルエントリ部３４ｂ〜３４ｈのローカルアドレスへのポインタも格納する。
【００３９】
すなわちアドレス変換テーブルエントリ部３４ｆには、自らに対応するキャッシュブロック４２のメインメモリ２０内でのアドレスと、実線矢印７０のようにアドレス変換テーブルヘッダ部３４ａに対し後ろに接続したアドレス変換テーブルエントリ部３４ｇのローカルアドレスと、実線矢印７２のように前に接続したアドレス変換テーブルエントリ部３４ｅのローカルアドレスと、破線矢印７４のように時系列順に次にロードされたキャッシュブロック４２のアドレス変換テーブルエントリ部３４ｄのローカルアドレスとが保持される。アドレス変換テーブルヘッダ部３４ａ、アドレス変換テーブルエントリ部３４ｂ〜３４ｈのいずれも、該当する接続エントリがなければアドレス以外の定数を代入しておく。
【００４０】
このようなテーブルとすることで、メインメモリ２０内のアドレスに基づき、ローカルメモリ１６内の所望のキャッシュブロックのコピー３２を効率よく特定することができる。アドレス変換テーブル３４に新たなアドレス変換テーブルエントリ部を追加する際の詳細な処理手順は、ハッシュテーブルにエントリを追加するための一般的な手法を用いてよい。
【００４１】
次にこれまで述べた装置およびデータの構造を用いて行われる分岐解決ルーチンの実行について説明する。図７は分岐解決ルーチンの処理手順を示すフローチャートである。前段として、ユーザは入出力装置２４などによりあるソフトウェアの起動を情報処理装置１０に指示し、当該ソフトウェアに対応するキャッシュブロック４２がメインメモリ２０にロードされ、そのうち１つ以上のキャッシュブロック４２がローカルメモリ１６にロードされ、それを参照しながらプロセッサ１４が処理を進捗させているものとする。
【００４２】
ここで処理がキャッシュブロックのコピー３２における分岐解決ルーチンの呼び出し命令まで進捗し、分岐解決ルーチンが呼び出されると、分岐解決ルーチン実行部１１０の実体であるプロセッサ１４は、直前の命令列でレジスタ１８に格納されたアドレスに基づき分岐先テーブル６４内の該当エントリを参照し、分岐先のキャッシュブロック４２のメインメモリ２０内での先頭アドレス、サイズ、分岐先命令までのオフセット値、分岐の種類を取得する（Ｓ２０）。次にプロセッサ１４は、アドレス変換テーブル３４を参照し、当該メインメモリ２０内のアドレスを保持するエントリが存在するか確認する（Ｓ２２）。存在していなければ（Ｓ２２のＮ）、当該キャッシュブロックのコピー３２はローカルメモリ１６内にないものとし、ロードの処理を開始する。
【００４３】
具体的には、まず最後にロードしたキャッシュブロックのコピー３２と同じバンク、例えば第１バンク３０ａに、新たなキャッシュブロックのコピー３２およびアドレス変換テーブルエントリ部、例えばアドレス変換テーブルエントリ部３４ｂを格納できる未使用領域が十分にあるか確認する（Ｓ２４）。この際、次に使用するバンクである第２バンク３０ｂが未使用であれば未使用領域が十分であると判断する。十分でなかった場合（Ｓ２４のＮ）、すなわち次のバンクである第２バンク３０ｂに格納されたキャッシュブロックのコピー３２を破棄して新たなキャッシュブロックのコピー３２を格納しなければならない場合は、当該第２バンク３０ｂの無効化処理を行う（Ｓ２６）。無効化処理については後に詳述する。
【００４４】
新たなキャッシュブロックのコピー３２を格納する領域が確保できたら（Ｓ２４のＹまたはＳ２６）、アドレス変換テーブルエントリ部３４ｂを作成し当該領域の先頭に書き込むとともに、アドレス変換テーブルヘッダ部３４ａを更新することにより、アドレス変換テーブル３４にエントリを追加する（Ｓ２８）。そしてＳ２０で取得したメインメモリ２０内のアドレスに基づき、メインメモリ２０からローカルメモリ１６の確保した領域にキャッシュブロック４２をロードする（Ｓ３０）。
【００４５】
そして、元に処理されていた分岐元のキャッシュブロックのコピー３２内の、分岐解決ルーチンを呼び出した命令列を、新たにロードしたキャッシュブロックのコピー３２内の命令への分岐命令に置き換える（Ｓ３２）。このとき、ロードしたキャッシュブロックのコピー３２の先頭ローカルアドレス（図５の「Ｘ'」）にＳ２０で取得した命令列までのオフセット値を加算することにより、分岐先命令列のローカルメモリ１６内でのアドレス（図５の「Ｙ'」）が得られる。そして当該キャッシュブロックのコピー３２内の分岐先の命令へ処理を分岐する（Ｓ３４）。
【００４６】
Ｓ２２においてアドレス変換テーブル３４に該当エントリが存在する場合は（Ｓ２２のＹ）、分岐先のキャッシュブロックのコピー３２がローカルメモリ１６内に存在するため、アドレス変換テーブル３４からアドレス変換テーブルエントリ部３４ｂのローカルアドレスを取得し、Ｓ３２、Ｓ３４の処理を行う。分岐解決ルーチンにおいて分岐先のキャッシュブロックのコピー３２がローカルメモリ１６内に存在する状態は、以前に別の命令列の分岐解決ルーチンによって当該キャッシュブロックのコピー３２がローカルメモリ１６に格納されている場合に発生する。
【００４７】
次にローカルメモリ１６においてキャッシュブロックのコピー３２を格納する第１バンク３０ａ〜第ｎバンク３０ｎの管理手法について説明する。図８は第１バンク３０ａ、第２バンク３０ｂ、第３バンク３０ｃ、第４バンク３０ｄと、それぞれに対応づけられたバンク間参照テーブル３８ａ、３８ｂ、３８ｃ、３８ｄ、および世代番号テーブル３９との関係を模式的に示している。同図に表された矢印はそれぞれの対応関係を示している。
【００４８】
上述のとおり本実施の形態では、プログラムの実行中、分岐先のキャッシュブロック４２を次々とローカルメモリ１６にロードする。そのためプログラムの実行に必要なコードの量がローカルメモリ１６の容量、厳密にはキャッシュブロックのコピー３２を格納することのできる容量を超えている場合は、いつかはロード済みのキャッシュブロックのコピー３２を破棄し、その領域を新たなキャッシュブロックのコピー３２の格納領域として再利用する必要が生じる。
【００４９】
ここで問題となるのは、破棄されるキャッシュブロックのコピー３２への分岐命令が、ローカルメモリ１６内の全キャッシュブロックのコピー３２に散在しうることである。このような分岐命令に含まれる分岐先のローカルメモリ１６内でのアドレスは、分岐先のキャッシュブロックが破棄された時点で無効となるから、分岐元のキャッシュブロックのコピー３２において図７のＳ３２で置き換えた分岐命令を、分岐解決ルーチン起動命令へ戻す必要がある。この処理を効率的に行うために、キャッシュブロックのコピー３２を格納する領域を第１バンク３０ａ〜第ｎバンク３０ｎのｎ個のバンクに分割し、バンクごとにキャッシュブロックのコピー３２の有効、無効を管理する。このときバンク間参照テーブル３８ａ、３８ｂ、３８ｃ、３８ｄは、対応するバンクが無効化されたとき、分岐元のキャッシュブロックのコピー３２において分岐解決ルーチン起動命令へ戻すべき分岐命令のアドレスを特定するために使用される。
【００５０】
なお図８では第１バンク３０ａ〜第４バンク３０ｄの４個のバンクのみ示しているが、バンクの数がそれ以外でも同様の構成で実現される。バンク間参照テーブル３８ａ〜３８ｄはそれぞれ、分岐命令アドレス欄７２および世代番号下位ビット欄７４を含む。分岐命令アドレス欄７２には、対応するバンクに格納されたキャッシュブロックのコピー３２へ分岐する命令が記述された、分岐元のキャッシュブロックのコピー３２における命令列のローカルアドレスが記録される。当該ローカルアドレスに記述された命令列は、当該バンクを無効化した際、分岐解決ルーチンに置き換えるべき命令列である。
【００５１】
世代番号下位ビット欄７４には、分岐命令が記述された命令列を含むキャッシュブロックのコピー３２を格納したバンクの世代番号の最下位ビットが記録される。ここで記録される世代番号は、当該エントリをバンク間参照テーブル３８ａ〜３８ｄに登録した時点での分岐元のバンクの世代番号である。以後この世代番号を「エントリの世代番号」と呼ぶ。あるキャッシュブロックのコピー３２において分岐解決ルーチンが起動し、対応するバンクに格納されたキャッシュブロックのコピー３２への分岐命令への置き換えが行われるとき、当該分岐解決ルーチンによってバンク間参照テーブル３８ａ〜３８ｄのエントリが追加登録される。
【００５２】
なお、同一のバンク内に分岐元のキャッシュブロックのコピー３２と分岐先のキャッシュブロックのコピー３２とがある場合は、それらが同じタイミングで無効化されるため、バンク間参照テーブル３８ａ〜３８ｄに分岐元のアドレスをエントリする必要がない。したがって分岐元で起動した分岐解決ルーチンは、分岐先のキャッシュブロックのコピー３２が異なるバンクに存在するときのみ、当該バンクのバンク間参照テーブル３８ａ〜３８ｄに追加登録を行う。
【００５３】
世代番号テーブル３９は第１バンク３０ａ〜第４バンク３０ｄにそれぞれ対応する欄を含み、それぞれのバンクの現在の世代番号が記録される。世代番号には対応するバンクが無効化されるたびに１が加算される。図８の例では、第１バンク３０ａおよび第２バンク３０ｂの世代番号は「３」、第３バンク３０ｃおよび第４バンク３０ｄの世代番号は「２」である。また同図に示すように、第２バンク３０ｂ内のアドレス「Ｘ」に分岐する分岐命令が、第３バンク３０ｃ内のローカルアドレス「Ａ」と第４バンク３０ｄ内のローカルアドレス「Ｂ」に記述されているとすると、第２バンク３０ｂに対応するバンク間参照テーブル３８ｂの分岐命令アドレス欄７２には「Ａ」および「Ｂ」が記録され、世代番号下位ビット欄７４には、ローカルアドレス「Ａ」を含む第３バンク３０ｃおよびローカルアドレス「Ｂ」を含む第４バンク３０ｄの世代番号「２」の最下位ビットである「０」が記録される。
【００５４】
バンク間参照テーブル３８ａ〜３８ｄに記録される各エントリは、対応する第１バンク３０ａ〜第４バンク３０ｄのいずれかを無効化するときに、分岐元のキャッシュブロックのコピー３２の分岐命令を分岐解決ルーチン起動命令に置き換えるためのものである。しかし対応するバンクを無効化する以前に当該分岐元のキャッシュブロックのコピー３２を格納したバンクがすでに無効化されているときは、そのエントリ自体が意味をなさない、すなわちエントリが無効である。このようにバンク間参照テーブル３８ａ〜３８ｄに記録された各エントリの有効、無効を判断するために、世代番号下位ビット欄７４を用いる。
【００５５】
バンク間参照テーブル３８ａ〜３８ｄにおける各エントリの世代番号が、そのエントリの分岐命令が存在する、あるいは存在したバンクの現在の世代番号と等しければそのエントリは有効であり、等しくなければ当該命令列を含むキャッシュブロックのコピー３２が破棄されており、当該エントリは無効である。本実施の形態では後に述べるように、エントリの世代番号と現在の世代番号とをそれらの最下位ビットの値で比較する。
【００５６】
次に、バンク間参照テーブル３８ａ〜３８ｄへのエントリ追加登録を含む、図７のＳ３２の分岐解決ルーチン起動命令置き換え処理の手順について説明する。図９は分岐解決ルーチン起動命令置き換え処理の手順を示すフローチャートである。まず、分岐先のキャッシュブロックのコピー３２を異なるバンクに新たに格納した場合など、異なるバンクへ分岐する場合（Ｓ６８のＹ）、当該バンク（以後、分岐先バンクと呼ぶ）、例えば図８の第２バンク３０ｂ、に対応するバンク間参照テーブル３８ｂから、無効となっているエントリを検索する（Ｓ７０）。無効になっているエントリがあればそれを上書きして新たなエントリを追加するためである。なお分岐先のキャッシュブロックのコピー３２が同じバンクにある場合（Ｓ６８のＮ）、バンク間参照テーブルの更新は必要ないためＳ７０〜Ｓ７６の処理は行わない。
【００５７】
エントリの有効、無効は基本的には上述したように、エントリの世代番号と当該エントリの分岐命令が属するバンクの現在の世代番号とを比較することにより判定する。判定に際して本実施の形態では、バンク間参照テーブル３８の世代番号下位ビット欄７４に記録された、各エントリの世代番号の最下位ビットと、当該エントリの分岐命令が属するバンク（以後、分岐元バンクと呼ぶ）の第１から第ｎの番号とを利用する。ここでバンクの番号は、各エントリの分岐命令アドレス欄７２に記録された分岐命令のローカルアドレスから計算できる。
【００５８】
まず、現在新たなキャッシュブロックのコピー３２の格納先となっているバンクを基準バンクとする。各バンクは無効化される際にその世代番号に１が加算されるため、基準バンクは、第１バンク３０ａ〜第ｎバンク３０ｎのうち最後に世代番号が増加したバンクである、。例えば図８の世代番号テーブル３９が保持する値を例にとると、第２バンク３０ｂが基準バンクである。このとき基準バンクである第２バンク３０ｂより上流にある、すなわちバンクの番号が小さい第１バンク３０ａの世代番号は、基準バンクである第２バンク３０ｂの世代番号と同一であり、下流にある、すなわちバンクの番号が大きい第３バンク３０ｃ、第４バンク３０ｄの世代番号は、基準バンクである第２バンク３０ｂの世代番号よりひとつ小さい。
【００５９】
この性質を利用すると、もしバンク間参照テーブル３８にエントリされた分岐元バンクの番号が基準バンクの番号以下であれば、そのバンクの現在の世代番号は基準バンクの世代番号と同じであるため、世代番号下位ビット欄７４に記録された値と、基準バンクの世代番号の最下位ビットが一致するエントリは有効であり、一致しなければ無効であると判断できる。また、もし分岐元バンクの番号が分岐先バンクの番号より大きければ、そのバンクの現在の世代番号は基準バンクの世代番号より一つ小さいため、世代番号下位ビット欄７４に記録された値と、基準バンクの世代番号の最下位ビットが一致しないエントリは有効であり、一致すれば無効であると判断できる。
【００６０】
これらの判定処理を、無効エントリが検出されるまでエントリごとに繰り返す。これにより、エントリの世代番号とそのエントリに対応するバンクの現在の世代番号とを、世代番号テーブル３９を検索せずに、基準バンクの世代番号とエントリの世代番号の最下位ビットのみで比較することができる。一方、各エントリに対応するバンクの現在の世代番号を世代番号テーブル３９から検索して、世代番号下位ビット欄７４に記録された値と直接比較してもよい。なお同一のバンク間参照テーブル３８ｂについて前回検出された無効エントリの次のエントリから検索を行うことにより、検索処理を効率化することができる。
【００６１】
無効エントリが検出されたら（Ｓ７２のＹ）、そのエントリの分岐命令アドレス欄７２および世代番号下位ビット欄７４を、現在実行中の分岐解決ルーチン起動命令が記述されているアドレスと、当該分岐解決ルーチン起動命令を含むキャッシュブロックのコピー３２が格納されたバンクの現在の世代番号とでそれぞれ上書きすることによりバンク間参照テーブル３８に登録する（Ｓ７６）。無効エントリが検出されなかったら（Ｓ７２のＮ）、今回追加するエントリを優先させ、登録済みのエントリのうちのいずれかを選択して上書きする。これに先立ち、選択したエントリの分岐命令アドレス欄７２に記録されたアドレスに記述された分岐命令を分岐解決ルーチン起動命令に置き換える（Ｓ７４）。そして新たなエントリをバンク間参照テーブル３８に登録する（Ｓ７６）。
【００６２】
続いて図７のＳ２０において取得した、分岐先テーブル６４の分岐種別欄５８に記録された分岐の種別の識別情報に基づき、置き換える命令が分岐命令か関数呼び出し命令かを判断する（Ｓ７８）。分岐命令であったら（Ｓ７８のＮ）、分岐解決ルーチン起動命令を分岐命令に置き換える（Ｓ８０）。関数呼び出し命令であったら（Ｓ７８のＹ）、分岐解決ルーチン起動命令を関数呼出し命令に置き換える（Ｓ８２）。関数呼び出し命令については次に説明する。以上の処理により、新たなキャッシュブロックのコピー３２をあるバンク、第２バンク３０ｂなどに格納した際のバンク間参照テーブル３８ｂなどへの追加登録と、当該キャッシュブロックのコピー３２への分岐命令への置き換えが実現される。
【００６３】
関数呼び出しは単なる分岐と異なり、元のプログラムへ戻る必要がある処理である。そのため図９のＳ８２において分岐解決ルーチンを関数呼び出し命令に置き換えた場合、図７のＳ３４において分岐先の命令へ分岐する処理は、分岐する直前に、関数から戻る先の命令列が存在する、呼び出し元のキャッシュブロック４２のメインメモリ２０内の格納領域の先頭アドレス、サイズ、戻る先の命令が記述されたアドレスの先頭アドレスからのオフセット値をレジスタ１８に格納する処理を伴う。従って図９のＳ８２で置き換える関数呼出し命令にはこれらの処理を実行する命令も含まれる。これらの値はキャッシュブロックのコピー３２の分岐先テーブル６４を参照することにより取得できる。
【００６４】
一方、呼び出した関数から処理を戻す分岐は、当該関数の呼び出し元が１つに定まらないため、これまで説明した分岐処理のように分岐先のローカルメモリ内でのアドレスを指定した分岐命令に置き換えることができない。関数から処理を戻す分岐ごとに、レジスタ１８に格納した戻る先のキャッシュブロック４２のメインメモリ２０内のアドレスに基づきアドレス変換テーブル３４を検索し、ローカルメモリ１６内でのアドレスを取得してもよいが、本実施の形態ではリンクスタックを導入して処理効率を向上させる。すなわちリンクスタックは、関数呼び出し時に、分岐先のキャッシュブロックのコピー３２から元のキャッシュブロックのコピー３２内のローカルアドレスへ処理を戻すために参照されるスタックである。
【００６５】
また本実施の形態では、分岐先での処理中、戻る先の命令列を含むキャッシュブロックのコピー３２が破棄されたりまた別の領域にロードしなおされている場合がある。このような場合、リンクスタックに格納した該当アドレスを無効化することにより、処理を戻す際に認識できるようにする。
【００６６】
図１０は関数呼び出しおよび戻り処理時のリンクスタックの様子を模式的に示している。リンクスタック３６ａ〜３６ｅは、レジスタ１８に格納される１つのリンクスタックの時系列変化を示している。キャッシュブロックのコピー３２ｃ〜３２ｅは、関数呼び出しによって順次処理されるキャッシュブロックのコピー３２であり、キャッシュブロックのコピー３２ｃからキャッシュブロックのコピー３２ｄ、キャッシュブロックのコピー３２ｅの順に呼び出される。なおリンクスタックは情報処理装置１０で処理されるスレッドごとに生成してよいが、ここでは１つのリンクスタックのみ示している。
【００６７】
まずリンクスタック３６ａを初期状態とする。ここでは図示しないキャッシュブロックのコピー３２内の、戻り先のアドレスが「Ｅ４」、「Ｅ３」、「Ｅ２」、「Ｅ１」の順で格納されている。この状態においてキャッシュブロック３２ｃの処理を実行し、「ｃａｌｌ  Ｃ１」なる命令によりキャッシュブロック３２ｄのアドレス「Ｃ１」へ分岐する際（Ｓ１０）、キャッシュブロック３２ｃの戻り先のアドレス「Ｒ１」がリンクスタック３６ａに追加される（リンクスタック３６ｂ）。続いてキャッシュブロック３２ｄの処理を実行し、「ｃａｌｌ  Ｃ２」なる命令によりキャッシュブロック３２ｅのアドレス「Ｃ２」へ分岐する際は（Ｓ１２）、キャッシュブロック３２ｄの戻り先のアドレス「Ｒ２」がリンクスタック３６ｂに追加される（リンクスタック３６ｃ）。
【００６８】
次にキャッシュブロック３２ｅの処理を実行し、「ｒｅｔｕｒｎ」なる命令によりキャッシュブロック３２ｄに戻る際は（Ｓ１４）、リンクスタック３６ｃを参照し、先頭のエントリから戻り先のアドレス「Ｒ２」を取得する。結果としてリンクスタック３６ｄの状態になるため、キャッシュブロック３２ｄの処理を実行し、「ｒｅｔｕｒｎ」なる命令によりキャッシュブロック３２ｃに戻る際は（Ｓ１６）、リンクスタック３６ｄを参照することによって先頭のエントリから戻り先のアドレス「Ｒ１」を取得できる。同図に示すように、リンクスタック３６ａ〜３６ｅの容量が不足した場合は、最も古いエントリを削除していく。
【００６９】
このような分岐処理中に、破棄されるキャッシュブロックのコピー３２のアドレスがリンクスタック３６ａ〜３６ｅ中にある場合は、当該アドレスに無効アドレスを代入する。ここで無効アドレスは命令が配置されることがない任意の値である。例えばキャッシュブロックのコピー３２ｅを実行中に、戻り先のキャッシュブロックのコピー３２ｄを破棄する場合、リンクスタック３６ｃの先頭エントリにある「Ｒ２」を「０」などとする。これにより、戻り先のアドレスを含むキャッシュブロックのコピー３２が破棄されたことを識別できる。
【００７０】
戻り先のキャッシュブロックのコピー３２が破棄された場合は、分岐解決ルーチンを起動することにより、関数呼び出し前にレジスタ１８に格納した情報に基づきメインメモリ２０から再ロードを行う。また、リンクスタックに無効アドレスを代入する代わりに、分岐解決ルーチンを格納したメインメモリ２０内またはローカルメモリ１６内のアドレスを代入してもよい。そして処理を当該アドレスに分岐させることにより、分岐解決ルーチンを直接起動する。これにより無効アドレスか否かによってキャッシュブロックのコピー３２の破棄の判定を行う処理を省略することができる。
【００７１】
図１１は上述のようなリンクスタック３６ａ〜３６ｅを用いて呼び出した関数から戻る処理手順を示すフローチャートである。まず図１０に示すように、例えばリンクスタック３６ｃの先頭エントリを取得する（Ｓ４０）。このとき、取得した先頭エントリがローカルメモリ１６内のキャッシュブロックのコピー３２が格納されるアドレス範囲にあるか否かを確認する（Ｓ４２）。アドレス範囲にあれば（Ｓ４２のＹ）、戻り先の命令列を含むキャッシュブロックのコピー３２が破棄されていなかったとして、取得したアドレスに記述された戻り先の命令へ分岐する（Ｓ４４）。
【００７２】
先頭エントリが「０」などアドレス範囲になければ（Ｓ４２のＮ）、まず該当するキャッシュブロックのコピー３２がローカルメモリ１６に存在するかどうかを、レジスタ１８に格納したメインメモリ２０内のアドレスに基づきアドレス変換テーブル３４を検索することにより確認する（Ｓ４６）。アドレス範囲になくても、一度破棄されたキャッシュブロックのコピー３２が再度ロードされている場合や、リンクスタックの容量不足でエントリが削除されてしまったが実体のキャッシュブロックのコピー３２は存在する場合があるためである。このようにアドレス変換テーブル３４に該当エントリが存在する場合は（Ｓ４８のＹ）、アドレス変換テーブル３４から当該キャッシュブロックのコピー３２のローカルメモリ１６内のアドレスを取得し、レジスタ１８に記録したオフセット値に基づき戻り先の命令へ分岐する（Ｓ５０）。
【００７３】
アドレス変換テーブル３４に該当エントリが存在しない場合は（Ｓ４８のＮ）、当該キャッシュブロックのコピー３２は破棄され、再ロードもされていないと判断し、ロード処理を開始する。具体的には図７のＳ２４、Ｓ２６、Ｓ２８、Ｓ３０、Ｓ３４と同様、バンクの未使用領域の容量確認（Ｓ５２）、必要に応じてバンクの無効化処理（Ｓ５４）、アドレス変換テーブル３４への登録（Ｓ５６）、キャッシュブロック４２のロード（Ｓ５８）、戻り先の命令への分岐（Ｓ６０）を行う。これにより、戻り先の命令を含むキャッシュブロックのコピー３２が一旦破棄されていても、効率的に検索を行い必要な場合にのみロード処理を行うことができる。
【００７４】
図１２はあるバンク、例えば第２バンク３０ｂの無効化処理を行う手順を示すフローチャートである。まず無効化する第２バンク３０ｂのバンク間参照テーブル３８ｂにおいて有効なエントリを抽出し、分岐命令アドレス欄７２に記録されたアドレスに記述された分岐命令を分岐解決ルーチン起動命令に置き換える（Ｓ９０）。エントリの有効、無効の判断は図９で説明したのと同様の原理で行うことができる。次に当該バンク間参照テーブル３８ｂの全エントリの分岐命令アドレス欄７２と世代番号下位ビット欄７４に、第２バンク３０ｂ内の任意のアドレスと世代番号の最下位ビットをそれぞれ書き込むことにより、全エントリを無効化する（Ｓ９２）。
【００７５】
さらに、アドレス変換テーブル３４において、破線矢印７４で示した、ロードされた順番によるエントリの連結を辿り、無効化する第２バンク３０ｂに含まれるキャッシュブロックのコピー３２を示すエントリを削除する（Ｓ９４）。具体的には、削除するエントリへのポインタを保持するエントリにおいて、当該ポインタをアドレス以外の定数とする。そして世代番号テーブル３９の第２バンク３０ｂに対応する欄の世代番号を１つ増加させる（Ｓ９６）。最後に、リンクスタック３６ａ〜３６ｅ中に無効化する第２バンク３０ｂ内のアドレスが含まれるときは、上述のようにそのアドレスを「０」などとして無効化する（Ｓ９８）。以上の処理により第２バンク３０ｂの無効化を分岐解決ルーチンに反映させることができる。
【００７６】
以上述べた本実施の形態によれば、プログラムをローカルメモリに一度にロードする単位であるキャッシュブロックに分割し、プロセッサはローカルメモリに格納されたキャッシュブロックを参照することにより処理を実行する。これによりメインメモリに格納されたプログラムへアクセスするより高速にプログラムを参照することができ、全体的な処理時間を削減することができる。
【００７７】
プログラムの分割は、サイズや使用頻度などに基づきコンパイラが自動で行う。またコンパイル時に、キャッシュブロック間の分岐をローカルメモリ内で実現するための分岐解決ルーチン起動命令を埋め込む。そしてプログラムの実行時には当該分岐解決ルーチンを起動させることにより、必要に応じてキャッシュブロックをメインメモリからロードし、ローカルメモリ内のアドレスで分岐命令を生成して書き込む。これらの処理がコンパイラによって行われるため、プログラムをモジュールに分割したり、各モジュールをローカルメモリにロードするためのプログラムを用意したりするプログラマの手間を省略でき、少ない労力でプログラムへの高速アクセスを実現できる。
【００７８】
さらに本実施の形態では、バンクごとにキャッシュブロックの破棄管理を行う。新たなキャッシュブロックをロードするためにあるバンクを無効化する際は、バンク間参照テーブルを利用することにより、無効化されるバンクに格納されたキャッシュブロックへ分岐する分岐元のキャッシュブロックの分岐命令の位置を全て特定し、それを再度分岐解決ルーチン起動命令に戻す。キャッシュラインに格納したデータに相互関係のない通常のキャッシュメモリと異なり、本実施のローカルメモリに格納されるキャッシュブロックは、相互に複雑な前後関係を有する。そして一度ロードしたキャッシュブロックを破棄することは、ローカルメモリ内で一度確立した前後関係を壊すことであり、前後に処理されるキャッシュブロックのプログラム自体に影響を与える。キャッシュブロックを世代番号という観点からバンクごとに管理することにより、そのような複雑な状況を効率よく制御することができる。
【００７９】
また、キャッシュブロックには必ず、当該キャッシュブロックに含まれる分岐処理の分岐先のキャッシュブロックの情報である分岐先テーブルを添付する。分岐先テーブルには分岐先のキャッシュブロックのメインメモリ内での格納アドレスが含まれる。そしてメインメモリ内でのアドレスとローカルメモリ内でのコピーのアドレスとの対応を示すアドレス変換テーブルをローカルメモリ内に用意することにより、メインメモリ内でのアドレスをキャッシュブロックの識別情報として、常時ローカルメモリ内でのコピーの有無や格納領域を特定することができる。アドレス変換テーブルはハッシュテーブルの構造をとることにより、より効率のよい検索が可能となる。また当該ハッシュテーブル構造によって、ローカルメモリにロードした順序を容易に辿ることができ、無効化したバンクに格納されたキャッシュブロックのエントリを効率的に削除することができる。
【００８０】
さらに関数呼び出し処理において関数の処理から元の処理へ戻る際は、分岐解決ルーチンを分岐命令に置き換える処理に代え、スタックを利用する。これにより戻る先を固定できない関数呼び出し処理においても、プログラムの自動的な分割、ローカルメモリへのロード処理などを他の分岐処理と同様に行うことができ、上述のような効果を得ることができる。
【００８１】
以上、本発明を実施の形態をもとに説明した。上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００８２】
例えば本実施の形態では、プログラムを分割したキャッシュブロックをメインメモリからローカルメモリにロードする態様を示したが、前後関係や依存関係を伴い参照されるデータであればプログラムでなくてもよく、一連のデータストリームのセグメントや、フレーム間予測符号化された動画像データの各フレームデータなどでもよい。
【図面の簡単な説明】
【００８３】
【図１】本実施の形態における情報処理装置の構造を示す図である。
【図２】本実施の形態においてローカルメモリとメインメモリに格納されるデータの構成を模式的に示す図である。
【図３】本実施の形態においてキャッシュブロックを形成するとともに分岐解決ルーチンを実行するコンパイラの構造を示す図である。
【図４】本実施の形態においてメインメモリに格納された２つのキャッシュブロックの構造を模式的に示す図である。
【図５】本実施の形態においてローカルメモリに格納された２つのキャッシュブロックのコピーとアドレス変換テーブルの構造を模式的に示す図である。
【図６】本実施の形態におけるアドレス変換テーブルの構造を模式的に示す図である。
【図７】本実施の形態における分岐解決ルーチンの処理手順を示すフローチャートである。
【図８】本実施の形態における第１バンク、第２バンク、第３バンク、第４バンク、バンク間参照テーブル、および世代番号テーブルの関係を模式的に示す図である。
【図９】本実施の形態における分岐解決ルーチン起動命令置き換え処理の手順を示すフローチャートである。
【図１０】本実施の形態における関数呼び出しおよび戻り処理時のリンクスタックの様子を模式的に示す図である。
【図１１】本実施の形態の関数呼び出し処理において呼び出した関数から戻る処理手順を示すフローチャートである。
【図１２】本実施の形態においてバンクの無効化処理を行う手順を示すフローチャートである。
【符号の説明】
【００８４】
１０  情報処理装置、  １２  プロセッサユニット、  １４  プロセッサ、  １６  ローカルメモリ、  １８  レジスタ、  ２０  メインメモリ、  ２２  記憶装置、  ２４  入出力装置、  ３０ａ  第１バンク、  ３０ｂ  第２バンク、  ３０ｃ  第３バンク、  ３０ｄ  第４バンク、  ３２  キャッシュブロックのコピー、  ３４  アドレス変換テーブル、  ３６ａ  リンクスタック、  ３８  バンク間参照テーブル、  ３９  世代番号テーブル、  ４２  キャッシュブロック、  ４６  分岐先テーブル、  １００  コンパイラ、  １０２  コンパイル部、  １０４  プログラム分割部、  １０６  命令埋め込み部、  １０８  分岐先情報付加部、  １１０  分岐解決ルーチン実行部。
【図１】
2008234490.tif 000003
【図２】
2008234490.tif 000004
【図３】
2008234490.tif 000005
【図４】
2008234490.tif 000006
【図５】
2008234490.tif 000007
【図６】
2008234490.tif 000008
【図７】
2008234490.tif 000009
【図８】
2008234490.tif 000010
【図９】
2008234490.tif 000011
【図１０】
2008234490.tif 000012
【図１１】
2008234490.tif 000013
【図１２】
2008234490.tif 000014