(57)【特許請求の範囲】
【請求項１】
複数の関数からなるプログラムをコンピュータにより実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報をコンピュータが生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をコンピュータがメモリ空間に配置する
各段階を含み、
該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値である
ことを特徴とするキャッシュカラーリング方法。
【請求項２】
複数の関数からなるプログラムをコンピュータにより実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報をコンピュータが生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をコンピュータがメモリ空間に配置する
各段階を含み、
該関数強度情報は、マトリクス情報ｎ１（ｉ，ｊ）＝ｋｉｎｄ（ｉ，ｊ）×ｎ（ｉ，ｊ）として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、ｋｉｎｄ（ｉ，ｊ）は、前記関数ｊ（≠ｉ）を少なくとも１回参照する区間全体における関数（関数ｉを除く）の種類の数であることを特徴とするキャッシュカラーリング方法。
【請求項３】
複数の関数からなるプログラムをコンピュータにより実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報をコンピュータが生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をコンピュータがメモリ空間に配置する
各段階を含み、
該関数強度情報は、マトリクス情報ｎ２（ｉ，ｊ）＝Ｋ（ｉ）×ｎ（ｉ，ｊ）として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｋ（ｉ）は、該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間の全体において出現する関数（関数ｉを除く）の種類の数であることを特徴とするキャッシュカラーリング方法。
【請求項４】
複数の関数からなるプログラムをコンピュータにより実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報をコンピュータが生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をコンピュータがメモリ空間に配置する
各段階を含み、
該関数強度情報は、マトリクス情報ｎ３（ｉ，ｊ）＝Σ（ｒｋｉｎｄ（ｉ，ｊ））として表現され、ｒｋｉｎｄ（ｉ，ｊ）は、該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間の中で関数ｊ（≠ｉ）を少なくとも１回参照する区間毎の関数（関数ｉを除く）の種類の数であり、シグマ記号Σは、ｒｋｉｎｄ（ｉ，ｊ）を前記関数ｊ（≠ｉ）を少なくとも１回参照する区間の全てについて累積することを特徴とするキャッシュカラーリング方法。
【請求項５】
前記Ｘ（ｉ，ｊ）は、関数ｉ又は関数ｊの命令キャッシュ活性度又は関数ｉ及びｊの間の相互の結合度合いの何れかを反映する値であることを特徴とする請求項１記載のキャッシュカラーリング方法。
【請求項６】
前記Ｘ（ｉ，ｊ）は、静的構文解析により求めた関数の複雑度に応じた命令キャッシュの活性度、動的実行解析により求めた関数内の分岐数に応じた命令キャッシュの活性度、動的実行解析により求めた関数内の分岐間の距離に応じた命令キャッシュの活性度の何れかを反映する値であることを特徴とする請求項５記載のキャッシュカラーリング方法。
【請求項７】
前記Ｘ（ｉ，ｊ）は、共用する外部変数の数に応じた結合度合い、プログラム呼出し回数に応じた結合度合い、プログラム階層構造に応じた結合度合いの何れかを反映する値であることを特徴とする請求項５記載のキャッシュカラーリング方法。
【請求項８】
キャッシュカラーリング用プログラム及び複数の関数からなるプログラムを格納するメモリと、
該メモリに格納された該キャッシュカラーリング用プログラムを実行することで該メモリに格納された該複数の関数からなるプログラムに対してキャッシュカラーリングを実行する演算処理ユニットを含み、該演算処理ユニットは、該キャッシュカラーリング用プログラムを実行することにより、
該複数の関数からなるプログラムを実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報を生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をメモリ空間に配置する
各段階を実行し、
該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値である
ことを特徴とするキャッシュカラーリング装置。
【請求項９】
複数の関数からなるプログラムをコンピュータに実行させることにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、
該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報を生成し、
該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をメモリ空間に配置する
各段階をコンピュータに実行させる命令コードを含み、
該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値である
ことを特徴とするキャッシュカラーリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に関数のメモリ空間への配置方法に関し、詳しくはキャッシュ競合を少なくするように関数をメモリ空間に配置するキャシュカラーリング方法に関する。
【背景技術】
【０００２】
コンピュータシステムにおいては一般に、主記憶メモリとは別に小容量で高速なキャッシュメモリが設けられる。主記憶メモリに記憶される情報の一部をキャッシュにコピーしておくことで、この情報をアクセスする場合には主記憶メモリからではなくキャッシュから読み出すことで、高速な情報の読み出しが可能となる。
【０００３】
キャシュは主記憶メモリに比較して高速でコスト高であるために、その記憶容量は非常に小さい。キャシュは複数のキャッシュラインを含み、外部メモリ（主記憶メモリ）からキャシュへの情報のコピーはキャシュライン単位で実行される。このために、外部メモリのメモリ空間をキャッシュライン単位で分割し、分割されたメモリ領域を順番にキャッシュラインに割当てておく。キャッシュの容量は外部メモリの容量よりも小さいので、外部メモリのメモリ領域を繰り返して同一のキャッシュラインに割当てることになる。
【０００４】
関数プログラムの実行において、外部メモリの異なるアドレスに配置された異なる関数プログラムが同一のキャッシュラインに割当てられている場合、これらの関数が交互に読み出されるたびに、関数プログラムをキャシュにコピーする必要が生じる。これをキャシュ競合という。キャシュ競合が頻繁に起こるとプログラムの実行速度が遅くなるという問題がある。この問題を解決するために、同時期に動作する可能性の高い関数同士は同一のキャシュラインに載らないよう配置する方法が研究されている。
【０００５】
キャッシュ競合の問題を解決するために、関数間の呼出し回数や特定の関数呼出しパターンの呼出し回数を示す関数強度を定義し、関数強度が高い（即ち互いに読み出す可能性が高い）関数同士が同一のキャッシュラインに割当てられないように設定する方法が従来からある。キャッシュ競合を少なくし命令キャシュミスを少なくすることを目的として、関数単位にリンク順番を設定・変更することをキャシュカラーリングと呼ぶ。
【０００６】
本願の出願人が提案しているキャッシュカラーリング方式（特許文献１参照）では、プログラム実行時の関数の呼出し関係のトレース等により生成された実行時の関数間の呼出し関係を時系列として表現した動的関数フローに基づいて、全ての関数間の実行時の呼出し関係についての情報を含む関数強度情報を生成する。この関数強度情報は、従来では不可能であった関数間の相互情報（任意関数とその他全関数との関係）を表現するものであり、これを用いることで命令キャシュミス数を最小限にするような最適な関数配置を実現することができる。この特許文献１のキャッシュカラーリング方式では、関数強度情報の具体的な定義として、４つの異なる関数強度情報を提案している。
【０００７】
一般に、ある特定の関数強度情報に基づいてキャッシュカラーリングを実行した場合、キャッシュミスの削減の効果は、個々のプログラムにより差が生じる場合がある。即ち、あるプログラムに対しては十分にキャッシュミス削減の効果が得られるが、他のプログラムに対しては十分なキャッシュミス削減の効果が得られない場合がある。この場合、使用した関数強度情報の定義が十分に汎用性のあるものではないことになる。従って、個々のプログラムの違いに影響されることなく、汎用的にキャッシュミスを削減できるような関数強度情報の定義が必要である。
【特許文献１】特開２００５−２６６９４１号公報
【特許文献２】特開２００３−２７１３９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
以上を鑑みて本発明は、汎用的にキャッシュミスを削減できるような関数強度情報の定義に基づいたキャッシュカラーリング方式を提供することを目的とする。
【課題を解決するための手段】
【０００９】
キャッシュカラーリング方法は、複数の関数からなるプログラムをコンピュータにより実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報をコンピュータが生成し、該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をコンピュータがメモリ空間に配置する各段階を含み、該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値であることを特徴とする。
【００１０】
キャッシュカラーリング装置は、キャッシュカラーリング用プログラム及び複数の関数からなるプログラムを格納するメモリと、該メモリに格納された該キャッシュカラーリング用プログラムを実行することで該メモリに格納された該複数の関数からなるプログラムに対してキャッシュカラーリングを実行する演算処理ユニットを含み、該演算処理ユニットは、該キャッシュカラーリング用プログラムを実行することにより、該複数の関数からなるプログラムを実行することにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報を生成し、該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をメモリ空間に配置する各段階を実行し、該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値であることを特徴とする。
【００１１】
キャッシュカラーリングプログラムは、複数の関数からなるプログラムをコンピュータに実行させることにより該プログラム実行時における該複数の関数の呼出し順を時系列として表現した動的関数フローを生成し、該動的関数フローに基づいて、該複数の関数のうちの任意の関数と他の全ての関数との実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報を生成し、該関数強度情報に基づいて命令キャッシュ競合が少なくなるように該複数の関数をメモリ空間に配置する各段階をコンピュータに実行させる命令コードを含み、該関数強度情報は、Ｘ（ｉ，ｊ）とｎ（ｉ，ｊ）とを積算することにより求められるマトリクス情報として表現され、ｎ（ｉ，ｊ）は該動的関数フローにおける関数ｉの参照からその後最初に参照された関数ｉまでの区間である全ての区間のうちで関数ｊ（≠ｉ）を少なくとも１回参照する区間の数であり、且つｉ＝ｊの場合には関数ｉの総参照回数であり、Ｘ（ｉ，ｊ）は関数ｉと関数ｊとの少なくとも１つにより定まる属性値であることを特徴とする。
【発明の効果】
【００１２】
本発明においては、プログラム実行時の関数の呼出し関係のトレース等により生成された実行時の関数間の呼出し関係を時系列として表現した動的関数フローに基づいて、全ての関数間の実行時の呼出し関係についての情報及びキャッシュミス発生確度の情報を含む関数強度情報を生成する。この関数強度情報は、従来では不可能であった関数間の相互情報（任意関数とその他全関数との関係）を表現するともに、更にキャッシュミス発生確度の情報を反映するものであり、これを用いることで汎用的にキャッシュミスを削減するような最適な関数配置を実現することができる。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【００１４】
図１は、本発明によるキャッシュカラーリング方法の実施例を示すフローチャートである。
【００１５】
図１のステップＳ１において、キャッシュカラーリングの対象となるプログラムをシミュレータ等により実行する。ステップＳ２で、関数の入口／出口をトレースすることにより、関数の動的フロー１０を生成する。ここでいう動的関数フロー１０とは、プログラム実行時に呼び出された関数を呼び出された順番（実行された順番）に時系列として並べたものであり、実行時の関数の呼出し関係をそのまま反映した情報である。動的関数フロー１０の生成については、後程詳細に説明する。
【００１６】
ステップＳ３において、動的関数フロー１０に基づいて関数強度情報１１を作成する。この関数強度情報１１は、従来の関数強度に含まれる呼出し回数や呼出し順の情報に加え、全ての関数に対する時系列的な情報を含むものである。関数強度情報１１の作成については、後程詳細に説明する。
【００１７】
ステップＳ４において、関数強度情報１１を参照したカラーリングに基づいて、命令キャッシュミスを最小にするようなリンク文字列を生成する。リンク文字列の生成については、後程詳細に説明する。ステップＳ５では、リンカが、生成されたリンク文字列に基づいて各関数を記憶空間に割当ててリンクすることにより、実行形式モジュールを生成する。ステップＳ６において、生成された実行モジュールを実行してカラーリング後のプログラムを実行する。
【００１８】
このように本発明においては、プログラムの実行時に関数の呼出し関係をトレースすることにより、実行時の関数間の呼出し関係を時系列として表現した動的関数フロー１０を生成し、この動的関数フロー１０に基づいて、全ての関数間の実行時の呼出し関係についての情報を含む関数強度情報１１を生成する。この関数強度情報１１は、従来では不可能であった関数間の相互情報（任意関数とその他全関数との関係）を表現するものであり、また更に、キャッシュミス発生確度を考慮することにより汎用性を有するものとなっている。この関数強度情報１１を用いることで命令キャシュミス数を最小限にするような最適な関数配置を実現することができる。
【００１９】
なお以降の説明においては、ダイレクト方式はキャシュｗａｙが１のセットアソシエイティブ方式とみなすことができるので、ダイレクト方式を含んだセットアソシエイティブ方式を例として用いる。
【００２０】
まず動的関数フロー１０の抽出について説明する。
【００２１】
対象となるプログラムが関数Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦからなるとして、このプログラムをシミュレータで実行する。各関数Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦの入口／出口をトレースすることにより、プログラムの実行開始から終了まで、呼び出された全ての関数を順番に記録することで関数の時系列を生成する。図２は、関数Ａ、Ｂ、Ｃ、Ｄ、Ｅ、及びＦからなるプログラムを実行した場合の動的関数フロー１０の一例を示す図である。最初に関数Ａが実行され、関数Ａが関数Ｂを呼び出すことで関数Ｂが実行され、以降順番に関数Ｃ、Ｄ、Ｃ、Ｄ、Ｃ、Ｂ、・・・と呼び出し・実行されている。
【００２２】
次に動的関数フロー１０に基づく関数強度情報１１の生成について説明する。
【００２３】
まず関数強度情報１１の基本となる基本関数強度について説明する。
【００２４】
ある関数ｉの参照から、その後、最初に参照された関数ｊまでの区間（ｉを含みｊを含まず）の集合をＲｉｊとする。動的関数フローから、Ｒｉｉである全ての区間のうちで、関数ｊを少なくとも１回参照するような区間の数としてｎ（ｉ，ｊ）を求める。ここでｉ＝ｊの場合には、ｎ（ｉ，ｊ）を関数ｉの総参照回数とする。このようにして求めたｎ（ｉ，ｊ）を基本関数強度と定義する。
【００２５】
ｎ（ｉ，ｊ）は、関数ｉと関数ｊ（≠ｉ）が同じキャシュラインに配置された場合にキャシュミスを発生させる回数（キャシュミス数）に等しい。つまりｎ（ｉ，ｊ）は、キャシュ競合の大小により関数強度を定義したものである。基本関数強度ｎ（ｉ，ｊ）が大きいほどキャッシュへの影響が大きいので、基本関数強度ｎ（ｉ，ｊ）の大きい関数同士を同じキャシュラインに配置せず、ｎ（ｉ，ｊ）の小さい関数同士を同じキャシュラインに配置するようにすれば、キャッシュ競合を少なくすることができる。
【００２６】
図３は、図２の動的関数フロー１０について基本関数強度ｎ（Ｂ，Ｄ）について説明するための図である。図３においてそれぞれ異なる下線で示すように、５つの関数Ｂの区間ＲＢＢ（次の関数Ｂまでの区間）が存在する。この５つの区間ＲＢＢのうちで、少なくともＤを１回参照する区間の数は３つである。したがってｎ（Ｂ，Ｄ）は３となる。同様に全ての関数の組み合せについて強度関数を求めると、図４に示すようなマトリクスが得られる。
【００２７】
以下に、基本関数強度ｎ（ｉ，ｊ）に対して更にキャッシュミス発生確度を考慮することにより関数強度情報１１を生成する方法について説明する。
【００２８】
上記説明した基本関数強度ｎ（ｉ，ｊ）は、関数ｉを２回参照する間に関数ｊを少なくとも１回参照する区間数を意味し、関数ｉと関数ｊ（≠ｉ）が同じキャシュラインに配置された場合のキャシュミス回数に相当する。しかし厳密に言えば、関数ｉと関数ｊとが同一のキャッシュラインに配置されていてもキャッシュミスが発生する確率は１ではなく、同一のキャッシュラインに割り当てられている関数ｉのプログラム命令部分と関数ｊのプログラム命令部分とが両方とも実行されたときに初めてキャッシュミスが発生する。従って、関数強度情報１１の定義としては、このようなキャッシュミス発生確度を反映するような定義であることが好ましい。
【００２９】
キャッシュミス発生確度に影響を及ぼす要素としては、Ｒｉｉに属する区間内に呼び出される関数（関数ｉ以外の関数）の数（種類の数）が挙げられる。関数強度情報１１の第１の実施例は、この関数ｉ以外の関数の種類の数を用いて求められる。
【００３０】
図５は、関数ｊを少なくとも１回参照する区間の例を示す図である。図５のケースＩａにおいてはＲｉｉに属する１つの区間において関数ｊ（≠ｉ）が例えば一回参照されている。またケースＩｂにおいても同様に、Ｒｉｉに属する１つの区間において関数ｊ（≠ｉ）が例えば一回参照されている。それぞれのケースにおいて、"・・・"は関数ｉ及び関数ｊ以外の他の関数を意味する。図５に示す例では、ケースＩｂの方がケースＩａよりも関数の呼び出しの数が多い。
【００３１】
関数が均一にキャッシュラインに配置されるとすると、着目区間で呼び出されている関数の数が多いほど、これらの関数のうちで関数ｉと同一のキャッシュラインに配置される関数の数が確率的に多くなる。また、関数ｉと同一のキャッシュラインに配置される関数の数が多いほど、キャッシュミスの回数は確率的に多くなる。
【００３２】
図６は、同一のキャッシュラインに配置される関数の数が多いほどキャッシュミスの回数が確率的に多くなることを説明するための図である。図６に示される例では、６つの関数３１乃至３６が同一のキャッシュラインＬ１を含むメモリ空間上に割り当てられている。各関数３１乃至３６において矢印で示すプログラム命令部分が、例えば図５のケースＩｂに示す区間において実行される部分に相当する。この例では、関数３１と関数３３とにおいて、キャッシュラインＬ１に割り付けられているプログラム命令部分が実行される。即ち、関数３１と関数３３との間でキャッシュラインＬ１についてキャッシュ競合が生じ、例えば関数３１の後に関数３３を実行する場合、関数３３の実行時にキャッシュミスが発生する。
【００３３】
このように同一のキャッシュラインＬ１に割り当てられている関数の数が多いほど、関数実行時にキャッシュラインＬ１に配置された命令の実行される確率が高くなる。即ち、同一のキャッシュラインＬ１に割り当てられている関数の数が多いほどキャッシュミス発生確率が高くなる。また上述のように、着目区間で呼び出されている関数の数が多いほど、これらの関数のうちで同一のキャッシュラインＬ１に配置されている関数の数が確率的に多くなる。従って、着目区間で呼び出されている関数の数が多いほど、キャッシュミス発生確率が高くなる。即ち、図５の例では、ケースＩａよりもケースＩｂの方が、キャッシュミス発生確率が高いことになる。
【００３４】
以上を鑑みて、関数強度情報１１の第１の実施例では、Ｒｉｉに属する区間の関数ｊ（≠ｉ）について、キャッシュミス発生確度を考慮した関数強度情報ｎ１（ｉ，ｊ）として、
ｎ１（ｉ，ｊ）＝ｋｉｎｄ（ｉ，ｊ）×ｎ（ｉ，ｊ）
を定義する。ここでｋｉｎｄ（ｉ，ｊ）は、Ｒｉｉに属する区間の中で関数ｊ（≠ｉ）を少なくとも１回参照する区間全体における関数（関数ｉを除く）の種類の数である。例えば、図２に示される動的関数フロー１０の場合、図３に示されるように５つの関数Ｂの区間ＲＢＢが存在する。この５つの区間ＲＢＢのうちで、少なくともＤを１回参照する区間の数は３つである。したがってｎ（Ｂ，Ｄ）は３となる。またこれらの３つの区間の全体において、関数Ｂ以外に現れる関数の種類は関数Ｃ及び関数Ｄである。従ってこれら３つの区間全体における関数の種類の数ｋｉｎｄ（Ｂ，Ｄ）は２である。以上から、ｎ１（ｉ，ｊ）＝３×２＝６となる。同様にして各ｎ１（ｉ，ｊ）を求めると、図７に示すようなマトリクスが得られる。このマトリクスに示すのが第１の実施例による関数強度情報ｎ１（ｉ，ｊ）である。
【００３５】
図４の基本関数強度ｎ（ｉ，ｊ）と図７の関数強度情報ｎ１（ｉ，ｊ）とを比較すると、例えば図４においてｎ（Ａ，Ｆ）及びｎ（Ｅ，Ｆ）は共に１であるのに対して、図７においてｎ（Ｅ，Ｆ）は１のままであるがｎ１（Ａ，Ｆ）は５になっている。この差異について以下に簡単に説明する。
【００３６】
まず図４の基本関数強度ｎ（ｉ，ｊ）を図２の動的関数フロー１０で見てみると、区間ＲＡＡは図２の動的関数フロー１０の全体に等しく、この１つの区間において関数Ｆが出現している。従ってｎ（Ａ，Ｆ）＝１である。また区間ＲＥＥは図２の動的関数フロー１０の終わり近くで２回出現し、このうちの１つの区間（"ＥＦＥ"）において関数Ｆが出現している。従ってｎ（Ｅ，Ｆ）＝１である。従って、基本関数強度ｎ（ｉ，ｊ）を見る限りでは、関数Ａと関数Ｆとを同一のキャッシュラインに配置したときのキャッシュミスの起こりやすさと、関数Ｅと関数Ｆとを同一のキャッシュラインに配置したときのキャッシュミスの起こりやすさとには、何ら違いがないことになってしまう。しかし現実には、上記区間ＲＡＡでキャッシュミスが発生する確度は、上記区間ＲＥＥでキャッシュミスが発生する確度よりも高いと考えられる。
【００３７】
図７の関数強度情報ｎ１（ｉ，ｊ）では、区間ＲＡＡと区間ＲＥＥとのキャッシュミス発生確度の違いが反映されている。即ち、ｎ１（Ａ，Ｆ）＝５とすることにより、区間ＲＡＡでのキャッシュミス発生確度の高さを反映させている。なおこの際、区間ＲＡＡには関数Ｆだけではなく関数Ｂ乃至Ｅも全て含むので、ｎ１（Ａ，Ｆ）だけではなくｎ１（Ａ，Ｂ）乃至ｎ１（Ａ，Ｅ）も全て同様に値が５になる。即ち、ここで考慮するキャッシュミス発生確度は、区間ＲＡＡにおいて出現するある１つの関数（例えば関数Ｆ）と関数Ａとのキャッシュ競合だけを考慮しているのではなく、区間ＲＡＡにおいて出現する関数全てと関数Ａとのキャッシュ競合を考慮しているので、ｎ１（Ａ，Ｆ）だけではなくｎ１（Ａ，Ｂ）乃至ｎ１（Ａ，Ｅ）についても大きな値となる。
【００３８】
以下に、関数強度情報１１の第２の実施例について説明する。関数強度情報１１の第２の実施例では、Ｒｉｉに属する区間の関数ｊ（≠ｉ）について、キャッシュミス発生確度を考慮した関数強度情報ｎ２（ｉ，ｊ）として、
ｎ２（ｉ，ｊ）＝Ｋ（ｉ）×ｎ（ｉ，ｊ）
を定義する。ここでＫ（ｉ）は、Ｒｉｉに属する区間全体において出現する関数（関数ｉを除く）の種類の数である。例えば、図２に示される動的関数フロー１０の場合、図３に示されるように５つの関数Ｂの区間ＲＢＢが存在する。この５つの区間ＲＢＢの全体において、関数Ｂ以外に現れる関数の種類は関数Ｃ，Ｄ，Ｅ，Ｆの４種類である。従ってＫ（Ｂ）は４である。以上から、図４に示す関数Ｂの行の各要素ｎ（Ｂ，＊）には４が掛け算されることになる。従って、関数Ｂの行の各要素の値０，６，３，３，２，１は、それぞれ０，２４，１２，１２，８，４となる。これらの値が関数強度情報ｎ２（Ｂ，＊）となる。同様にして各ｎ２（ｉ，ｊ）を求めると、図８に示すようなマトリクスが得られる。このマトリクスに示すのが第２の実施例による関数強度情報ｎ２（ｉ，ｊ）である。
【００３９】
以下に、関数強度情報１１の第３の実施例について説明する。関数強度情報１１の第３の実施例では、Ｒｉｉに属する区間の関数ｊ（≠ｉ）について、キャッシュミス発生確度を考慮した関数強度情報ｎ３（ｉ，ｊ）として、
ｎ３（ｉ，ｊ）＝Σ（ｒｋｉｎｄ（ｉ，ｊ））
を定義する。ここでｒｋｉｎｄ（ｉ，ｊ）は、Ｒｉｉに属する区間の中で関数ｊ（≠ｉ）を少なくとも１回参照する区間毎の関数（関数ｉを除く）の種類の数である。シグマ記号は、ｒｋｉｎｄ（ｉ，ｊ）をＲｉｉに属する区間の中で関数ｊ（≠ｉ）を少なくとも１回参照する区間の全てについて累積する。例えば、図２に示される動的関数フロー１０の場合、図３に示されるように５つの関数Ｂの区間ＲＢＢが存在する。この５つの区間ＲＢＢのうちで、少なくともＤを１回参照する区間の数は３つである。これら３つの区間のそれぞれにおいて、関数Ｂ以外に現れる関数の種類の数は、２種類、２種類、２種類である。従ってこれら３つの区間について累積すると、ｎ３（Ｂ，Ｄ）は６（＝２＋２＋２）となる。同様にして各ｎ３（ｉ，ｊ）を求めると、図９に示すようなマトリクスが得られる。このマトリクスに示すのが第３の実施例による関数強度情報ｎ３（ｉ，ｊ）である。
【００４０】
以下に、関数強度情報１１の第４の実施例について説明する。関数強度情報１１の第４の実施例では、Ｒｉｉに属する区間の関数ｊ（≠ｉ）について、キャッシュミス発生確度を考慮した関数強度情報ｎ４（ｉ，ｊ）として、
ｎ４（ｉ，ｊ）＝Ｘ（ｉ，ｊ）×ｎ（ｉ，ｊ）
を定義する。ここでＸ（ｉ，ｊ）は、関数ｉと関数ｊとの少なくとも１つにより定まる属性値である。関数強度情報ｎ４（ｉ，ｊ）は、この属性値Ｘ（ｉ，ｊ）と基本関数強度ｎ（ｉ，ｊ）との演算により求められる。上式においてこの演算は積算として示されるが、積算に限られることなく、減算、加算、除算、或いは他の何らかの演算であってよい。演算が積算であり、Ｘ（ｉ，ｊ）がＲｉｉに属する区間の中で関数ｊ（≠ｉ）を少なくとも１回参照する区間全体における関数（関数ｉを除く）の種類の数であるとすると、第１の実施例の場合と同等になる。またＸ（ｉ，ｊ）が関数ｊとは無関係に関数ｉのみにより定まる値であり、Ｒｉｉに属する区間全体において出現する関数（関数ｉを除く）の種類の数であるとすると、第２の実施例の場合と同等になる。このように、第４の実施例による関数強度情報ｎ４（ｉ，ｊ）は、種々の場合を包括可能な関数強度情報として定義されている。
【００４１】
属性Ｘ（ｉ，ｊ）は、関数ｉ又は関数ｊの命令キャッシュ活性度又は、関数ｉ及びｊの間の相互の結合度合いの何れかを反映した値として定義することができる。関数ｉ又は関数ｊの命令キャッシュ活性度としては、静的構文解析による関数の複雑度による命令キャッシュの活性度、動的実行解析による関数内の分岐数による命令キャッシュの活性度、動的実行解析による関数内の分岐間の距離による命令キャッシュの活性度等が使用できる。また関数iと関数jとの相互結合度合いとしては、共用する外部変数の数による結合度合い、プログラム呼出し回数による結合度合い、プログラム階層構造による結合度合い等を使用することができる。
【００４２】
まず第１の例として、関数の言語記述の構文情報から求めた複雑度により、関数iの属性を定義する場合を以下に説明する。この場合、関数のプログラムの文の種類ごとに重み付けを定義し、更に各文の出現回数を計数する。各文の出現回数と重み付けとの積を、全ての文の種類について足し合わせることにより求めた総和を、複雑度として定義する。
【００４３】
例えば、分岐文の重み付けをc1、for等の繰り返し文の重み付けをc2、転記文の重み付けをc3とする。また分岐文の出現回数がn1、for等の繰り返し文の出現回数がn2、転記文の出現回数がn3とする。この場合、関数iにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝c1×n1＋c2×n2＋c3×n3
となる。なおこのようにして求めた属性値を関数ｉのサイズで除算することにより、関数の単位大きさあたりの属性値Ｘｕｎｉｔ（ｉ，ｊ）を求めて、これを複雑度として定義してもよい。
【００４４】
Ｘｕｎｉｔ（ｉ，ｊ）＝(c1×n1＋c2×n2＋c3×n3)/関数iのサイズ
このようにして求めた複雑度Ｘ（ｉ，ｊ）又はＸｕｎｉｔ（ｉ，ｊ）は、関数ｉの実行中に命令アドレスが順番にインクリメントするだけでなくジャンプ等により頻繁に動きまわり、その動きが複雑である度合いを示している。この複雑度が大きくなるほど、命令キャッシュのより多くのエントリをより頻繁に使用する結果となり、キャッシュミス発生確度が高くなると考えることができる。
【００４５】
第２の例として、関数の分岐数から求めた複雑度により、関数iの属性を定義する場合を以下に説明する。まずシミュレータ等により関数ごとにプログラムを実行させて、各分岐命令毎の分岐数を求める。例えば分岐命令１の分岐数がc1であり、分岐命令２の分岐数がc2であり、以下同様にして分岐命令ｎの分岐数がcnであるとする。この場合、関数iにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝c1＋c2＋…＋cn
となる。また前記の例と同様に、関数の単位大きさあたりの属性値Ｘｕｎｉｔ（ｉ，ｊ）を求めて、これを複雑度として定義してもよい。
【００４６】
第３の例として、関数内の分岐間の距離から求めた複雑度により、関数iの属性を定義する場合を以下に説明する。まずシミュレータ等により関数ごとにプログラムを実行させて、関数の各分岐命令毎にその実行回数を求める。また各分岐命令毎に分岐の距離（分岐元の命令アドレスと分岐先の命令アドレスとの差分）を求める。例えば分岐命令１の実行回数がc1で分岐距離がl1であり、分岐命令２の実行回数がc2で分岐距離がl2であり、以下同様にして分岐命令３の実行回数がcnで分岐距離がlnであるとする。この場合、関数iにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝c1×l1 ＋c2×l2＋…cn×ln
となる。また前記の例と同様に、関数の単位大きさあたりの属性値Ｘｕｎｉｔ（ｉ，ｊ）を求めて、これを複雑度として定義してもよい。
【００４７】
第４の例として、関数ｉと関数ｊとが共用する外部変数の数から求めた相互結合度により、関数i及び関数ｊの相互属性を定義する場合を以下に説明する。この相互結合度の値が大きいほど、関数強度が強く、キャッシュミスに影響を及ぼす確度が高いと判断する。例えば関数ｉと関数ｊとが共用する外部変数の定義数をｄｆとし、更に実行回数等の適当な指標を重み付けｃとして用いる。この場合、関数i及び関数ｊにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝df×c
となる。
【００４８】
第５の例として、関数ｉと関数ｊとの呼び出し回数から求めた相互結合度により、関数i及び関数ｊの相互属性を定義する場合を以下に説明する。この相互結合度の値が大きいほど、関数強度が強く、キャッシュミスに影響を及ぼす確度が高いと判断する。例えば関数ｉ及び関数ｊの呼出し回数をcとする。この場合、関数i及び関数ｊにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝c
となる。
【００４９】
第６の例として、関数ｉと関数ｊとの階層関係から求めた相互結合度により、関数i及び関数ｊの相互属性を定義する場合を以下に説明する。この例では、プログラム実行時においてある関数が他の関数を呼び出す場合に、呼び出し側の関数を親関数、呼び出される側の関数を子関数として、関数間の関係を階層構造化する。
【００５０】
図１０は、関数の階層構造における関数間の関係の例を示す図である。（ａ）では、関数ｉ及び関数ｊは親子関係にある。（ｂ）では、関数ｉ及び関数ｊは先祖と子孫との関係にある。（ｃ）では、関数ｉ及び関数ｊは兄弟関係にある。それぞれの関係について関数間の結合強度を定義する。例えば親子関係なら結合強度が１、直系の先祖と子孫との関係であれば結合強度がn2（<１）、兄弟関係であれば結合強度がn3（<１）であるとする。実行回数等の適当な指標を重み付けｃとして用いる。例えば親子関係の実行回数がc1、直系子孫の実行回数がc2、兄弟関係の実行回数がc3とする。この場合、関数i及び関数ｊにより定まる属性値Ｘ（ｉ，ｊ）は、
Ｘ（ｉ，ｊ）＝c1×1+c2×n2+c3×n3
となる。
【００５１】
第７の例として、他の関数強度情報から求めた相互結合度により、関数i及び関数ｊの相互属性を定義する場合を以下に説明する。本願の出願人により出願された特開２００５−２６６９４１号公報には、関数強度情報ｎ＋（ｉ，ｊ）、ｎ＋＋（ｉ，ｊ）、ｎ＃（ｉ，ｊ）が定義されている。これらの関数強度情報と適当な閾値cとの大小関係により、Ｘ（ｉ，ｊ）の値を定義することができる。例えば関数強度情報ｎ＋（ｉ，ｊ）を用いて、
n+(i,j)>c    ：    X(i,j)=1
n+(i,j)≦c    ：    X(i,j)=p  (0≦p<1)
として適当な値ｐを用いてＸ（ｉ，ｊ）を定義する。関数強度情報ｎ＋（ｉ，ｊ）の代わりにｎ＋＋（ｉ，ｊ）又はｎ＃（ｉ，ｊ）を用いてもよいし、或いはこれらの関数強度情報を組み合わせて使用してもよい。
【００５２】
なお関数強度情報ｎ＋（ｉ，ｊ）は、
ｎ＋（ｉ，ｊ）＝Σ（１×Ｒｅｆ（ｋ）／Ｒ（ｋ））
Ｒ（ｋ）：区間ｋ∈Ｒｉｉの全関数の参照回数
Ｒｅｆ（ｋ）：区間ｋ∈Ｒｉｉ≠ｊの関数ｊの参照回数
である。また関数強度情報ｎ＋＋（ｉ，ｊ）は、
ｎ＋＋（ｉ，ｊ）＝Σ（１×Ｒｅｆ（ｋ））
Ｒｅｆ（ｋ）：区間ｋ∈Ｒｉｉ≠ｊの関数ｊの参照回数
である。また更に関数強度情報ｎ＃（ｉ，ｊ）は、
ｎ＃（ｉ，ｊ）＝Σ（１／Ｌｅｎ（ｋ））
Ｌｅｎ（ｋ）：区間ｋ∈Ｒｉｉ≠ｊの関数ｊの最初の参照までの距離（≠0）
である。
【００５３】
以上のようにして求めた関数強度情報ｎ１（ｉ，ｊ）乃至ｎ４（ｉ，ｊ）の何れかに基づいて、キャッシュミスが少なくなるように関数をメモリ空間に配置する。以下にこの方法について説明する。なお以下の全ての例において、関数強度情報ｎ１（ｉ，ｊ）を用いた場合について説明するが、関数強度情報ｎ２（ｉ，ｊ）乃至ｎ４（ｉ，ｊ）の何れを用いた場合についても同様である。
【００５４】
図１１は、関数配置方法の第１の実施例を示すフローチャートである。この第１の実施例では、関数強度情報が大きい順番に関数を配置する。
【００５５】
ステップＳ１において、関数ｉと関数ｊの関数強度情報を示す行列ｎ１（ｉ，ｊ）から関数ｉに対する行を選択する。初回の関数ｉは行の先頭関数とする。
【００５６】
ステップＳ２において、関数ｉの総和（関数Ｍ（ｉ））に初期値０を入れる。
【００５７】
ステップＳ３において、関数強度情報ｎ１（ｉ，ｊ）を示す行列から関数ｉ行の列要素関数ｊを選択（初回は先頭列：但しｉ≠ｊ）し、関数ｉの総和（関数Ｍ（ｉ））に加算する。
【００５８】
ステップＳ４において、選択した関数ｊが最終列を超えたか否かを判断する。超えればステップＳ６に進み、超えない場合にはステップＳ５に進む。
【００５９】
ステップＳ５において、次の列要素の関数ｊを求める。その後ステップＳ３に戻り、以降の処理を繰り返す。
【００６０】
ステップＳ６において、関数ｉの総和（関数Ｍ（ｉ））が求まる。
【００６１】
ステップＳ７において、選択した関数ｉは最終行を超えたか否かを判断する。超えればステップＳ８に進む。超えない場合にはステップＳ１に戻り、次行の関数ｉに対して同様の処理を実行する。
【００６２】
以上の処理が終了した段階で、図１２に示すように、図７の関数強度情報１１に対応した関数Ｍ（ｉ）（各関数ｉに対する関数強度情報１１の総和）が求められる。この関数Ｍ（ｉ）は、関数ｉについて他の関数が同一のキャッシュラインに配置された場合のキャッシュミス数の総和に相当する。
【００６３】
次にステップＳ８において、行要素（関数ｉ：ｉ＝１、２、・・・）の総和Ｍ（ｉ）の大きい値の順に対応する関数を抽出して、リンク文字列を作成する。即ち、Ｍ（ｉ）の大きい順に関数を配置する。図１３は、図７の関数強度情報１１の場合に関数配置方法の第１の実施例に従い配置された関数の列を示す図である。
【００６４】
この関数配置方法の第１の実施例では、関数強度情報１１の強い関数同士が同一キャシュライン（異なる論理アドレスを占める同一のキャシュライン）に配置されることを防ぐことができる。即ち、同一のキャシュラインはメモリ空間の連続するアドレス上でキャシュサイズ分だけ離れて周期的に割当てられているので、関数強度情報１１の大きな関数を優先して先に配置していくことで、関数強度情報１１の大きな関数を次の同一キャシュラインが現れるより前に割当てることができる。これにより、キャシュ競合が発生しないようにすることが可能である。
【００６５】
以下に、関数強度情報１１に基づいて関数をメモリ空間に配置する方法の第２の実施例について説明する。
【００６６】
図１４は、関数配置方法の第２の実施例を示すフローチャートである。この第２の実施例では、総和ではなく関数個々の関数強度情報ｎ１（ｉ，ｊ）に着目して、最も頻繁にキャシュミスが発生する関数同士を、互いに隣接して配置することでキャシュミスの競合をなくすようにしている。
【００６７】
図１４のステップＳ１において、関数強度情報ｎ１（ｉ，ｊ）が最も大きい関数の組（関数ｉ、関数ｊ）を選択する。選択された関数の組の左側の関数ｉを起点関数として、リンク文字列に関数ｉ、関数ｊの順番に関数を配置する。
【００６８】
ステップＳ２において、起点関数を関数ｊとし関数強度情報ｎ１（ｊ，ｋ）が最も大きくなる関数ｋを求める。この際、既にリンク文字列として選択済の関数を除いた残りの関数中から関数ｋを選択する。リンク文字列の終端に求めた関数ｋを追加する。
【００６９】
ステップＳ３において、起点関数を関数ｋとして、同様に繰り返す。
【００７０】
ステップＳ４において、起点関数が存在しない（リンク文字列にすべての関数を抽出済）であるか否かを判断する。起点関数がまだ存在する場合には、ステップＳ２に戻り以降の処理を繰り返す。
【００７１】
ステップＳ５において、リンク文字列が求まる。
【００７２】
図７の関数強度情報１１の例では、強度情報の最大はｎ１（Ｄ，Ｃ）であるので、まず起点関数をＤとして、最も強度情報の大きい関数Ｃを選択する。次に起点関数をＣとして、最も強度情報の大きい関数Ｂを選択する（関数Ｄは既抽出のために除く）。同様に起点関数をＢとして、最も強度情報の大きい関数Ｅを選択する。次に起点関数をＥとして、最も強度情報の大きい関数Ｆを選択する。最後に関数Ｆを起点関数として、残りの関数Ａを選択する。図１５は、図７の関数強度情報１１の場合に関数配置方法の第２の実施例に従い配置された関数の列を示す図である。
【００７３】
なお関数強度情報が同じ関数が複数存在する場合、何れの関数を選択するかにより以降の関数配置が大きく変わる可能性がある。そこで関数強度情報が同じ場合について、関数を選択する基準を規定しておいてもよい。例えば、ユーザによる関数配置の指定、関数サイズが小さい関数優先、呼出し数が大きい関数優先等である。
【００７４】
上記関数配置方法の第２の実施例では、強度情報の大きさだけでなく、更に関数サイズを考慮するようにしてもよい。即ち、関数サイズが小さいものほど近くに配置すべきであるという考えに基づいて、（強度情報／サイズ）の値を定義して、この値が大きい関数を配置関数として順次選択して配置するようにしてもよい。
【００７５】
以上説明した関数配置方法においては、メモリ空間上のキャッシュラインについては特に意識することなく、関数を所定の順番で配置している。これに対して、以下に説明する関数配置方法の第３の実施例では、関数強度情報１１を利用してキャッシュライン毎に関数を配置する。
【００７６】
図１６は、関数配置方法の第３の実施例を示すフローチャートである。第３の実施例では、関数強度情報１１に基づいて選択したキャシュミス数の少ないラインから順次関数を配置していく。
【００７７】
図１６のステップＳ１において、配置関数の順番を一意に決定する。配置順番としては、例えば、関数配置方法の第１の実施例と同様に、キャシュミス数の総和に相当するＭ（ｉ）の大きい順としてよい。この順番は一意であればよく、特に限定されるものではない。例えば、自関数の呼出し回数ｎ１（ｉ，ｉ）の大きい順としてもよい。ステップＳ２において、上記の順番に従って、関数（まだ選択されていない）を一つ選択する。
【００７８】
ステップＳ３において、メモリ空間に割当てられたキャッシュラインを走査し、既に配置されている関数と選択した関数との間で発生するキャッシュミス数（ｎ１（ｉ，ｊ））を、関数強度情報１１に基づいてキャッシュライン毎に算出する。ステップＳ４において、ステップＳ３で算出したキャシュミス数が最も少ないキャシュラインに、ステップＳ２で選択した関数を配置する。このステップＳ３及びステップＳ４の処理については後程詳細に説明する。
【００７９】
ステップＳ５において、全ての関数が配置されたか否かを判定する。全ての関数が配置された場合には、処理はステップＳ６に進む。まだ配置されていない関数が存在する場合には、ステップＳ２に戻り、以降の処理を繰り返す。
【００８０】
ステップＳ５において、キャシュライン毎に関数を配置するリンク文字列を作成する。これにより、キャッシュラインを考慮しながら全ての関数をメモリ空間に配置する処理が終了する。
【００８１】
図１７は、図１６のステップＳ３及びＳ４において、キャッシュミス数をキャッシュライン毎に算出し関数を配置する処理を示すフローチャートである。なおキャッシュラインは、Ｌ１乃至Ｌｚのｚ個が割当てられているとする。
【００８２】
ステップＳ１において、選択した関数ｘが占めることになるキャシュラインの数ｍを関数サイズに基づいて求める。
【００８３】
ステップＳ２において、各キャシュラインＬｎ（ｎ＝１〜ｚ）に配置されている関数を全て抽出する。具体的には、関数配置時に使用キャシュラインの情報が内部テーブルに格納されるので、各キャシュラインＬｎについて既に配置済みの関数の情報が記録されている。この情報に基づいて、各キャシュラインＬｎ（ｎ＝１〜ｚ）に配置されている関数を全て抽出することができる。キャシュラインＬｎに配置されている関数を（Ｌｎ−ｆ１，Ｌｎ−ｆ２，Ｌｎ−ｆ３，・・・Ｌｎ−ｆ）と表記する。
【００８４】
ステップＳ３において、関数ｘを配置するときに、各キャシュラインＬｎ（ｎ＝１〜ｚ）に配置されている関数とキャシュミスを起こす回数を関数強度情報から算出する。ここでキャシュラインＬｎでのキャシュミス数Ｍ（Ｌｎ）は、
Ｍ（Ｌｎ）＝ ｎ１（ｘ，Ｌｎ＿ｆ１）＋ｎ１（Ｌｎ＿ｆ１，ｘ）
＋ｎ１（ｘ，Ｌｎ＿ｆ２）＋ｎ１（Ｌｎ＿ｆ２，ｘ）
＋・・・＋ｎ１（ｘ，Ｌｎ＿ｆ）＋ｎ１（Ｌｎ＿ｆ，ｘ）
として求められる。
【００８５】
ステップＳ４において、連続するキャシュラインをキャシュラインＬ０からm個選択してキャシュミスの総和（Ｍ（Ｌ０）＋Ｍ（Ｌ１）＋…＋Ｍ（Ｌｍ））を求め、キャシュラインＬ１からｍ個選択してキャシュミスの総和（Ｍ（Ｌ１）＋Ｍ（Ｌ２）＋…＋Ｍ（Ｌｍ＋１））を求め、以下同様に各ｍ個のキャッシュラインについてキャッシュミスの総和を求め、最後にキャシュラインＬｚ（最終キャシュライン）からｍ個選択してキャシュミスの総和（Ｍ（Ｌｚ）＋Ｍ（Ｌ０ ）＋…＋Ｍ（Ｌｍ−１））を求める。なお最終キャシュラインＬｚの後は先頭キャシュラインＬ０に戻ることになる。
【００８６】
ステップＳ５において、ステップＳ４で求めたキャッシュミスの総和が最小となるｍ個のキャッシュラインのセットを選択する。ステップＳ６において、選択されたｍ個の連続するキャッシュラインに関数ｘを配置する。
【００８７】
上記のキャッシュライン毎の配置方法により、関数Ｂ、Ｃ、Ｄ、Ａ、Ｅ、及びＦの全てについて、キャシュラインへの配置が決定される。このキャシュラインへの配置においては、キャシュライン単位に関数を配置しているだけであるので、リンク時において論理アドレスを指定する必要がある。
【００８８】
以下に、キャッシュラインへの関数配置情報に基づいて論理アドレスを求める方法について説明する。
【００８９】
図１８は、キャッシュラインへの関数配置から各関数の論理アドレスを求める方法を示すフローチャートである。
【００９０】
ステップＳ１において、連続するキャシュライン番号を、関数強度情報を使用したキャシュラインごとの配置方法により求める。即ち各関数に対して、関数を配置するキャッシュラインを求める。
【００９１】
ステップＳ２において、キャシュライン番号に対応する最初の論理アドレスとして、論理アドレスのタグ領域にキャシュライン番号を格納しそれ以外はゼロに設定することで論理アドレスを算出する。
【００９２】
図１９は、論理アドレスの構成及びキャッシュライン番号から論理アドレスへの変換テーブルを示す図である。図１９（ａ）に示されるように、例えば８つのキャッシュラインが論理アドレスの第４ビット〜第６ビット（タグ領域）で指定される。図１９（ｂ）に示されるように、例えばキャッシュラインＬ０は、この第４ビット〜第６ビットが０である論理アドレスに割当てられる。また例えばキャッシュラインＬ１は、この第４ビット〜第６ビットが１である論理アドレスに割当てられる。上記図１８のステップＳ２においては、タグ領域である第４ビット〜第６ビットにキャッシュライン番号を格納し、それ以外のビットにはゼロを設定することで、各キャッシュラインＬ０〜Ｌ７に対するベースとなる論理アドレス（最初の論理アドレス）を設定する。
【００９３】
図１８のステップＳ３において、同じキャシュライン番号となる２回目以降の論理アドレスとして、前回求めた論理アドレスにキャッシュサイズを加算する。例えば同一キャッシュライン番号に対応する２回目の論理アドレスは、上記のベースとなる論理アドレスからキャシュサイズだけ離れたアドレスとなる。従って、ベースとなる論理アドレスにキャシュサイズを加算することで２回目の論理アドレスを求めることができる。３回目以降の論理アドレスについても同様に、前回求めた論理アドレスにキャシュサイズを加算することで対応するアドレスを求める。
【００９４】
ステップＳ４において、指定したキャシュラインに対応する論理アドレスを求める。即ち、各関数に対して、その関数の配置先として指定されるキャッシュラインに対応する論理アドレスを求める。
【００９５】
以上の処理により、各関数を配置する論理アドレスを決定することができる。
【００９６】
図２０は、本発明によるキャッシュカラーリングを実行する装置の構成を示す図である。
【００９７】
図２０に示されるように、本発明によるキャッシュカラーリング方法を実行する装置は、例えばパーソナルコンピュータやエンジニアリングワークステーション等のコンピュータにより実現される。図２０の装置は、コンピュータ５１０と、コンピュータ５１０に接続されるディスプレイ装置５２０、通信装置５２３、及び入力装置よりなる。入力装置は、例えばキーボード５２１及びマウス５２２を含む。コンピュータ５１０は、ＣＰＵ５１１、ＲＡＭ５１２、ＲＯＭ５１３、ハードディスク等の二次記憶装置５１４、可換媒体記憶装置５１５、及びインターフェース５１６を含む。
【００９８】
キーボード５２１及びマウス５２２は、ユーザとのインターフェースを提供するものであり、コンピュータ５１０を操作するための各種コマンドや要求されたデータに対するユーザ応答等が入力される。ディスプレイ装置５２０は、コンピュータ５１０で処理された結果等を表示すると共に、コンピュータ５１０を操作する際にユーザとの対話を可能にするために様々なデータ表示を行う。通信装置５２３は、遠隔地との通信を行なうためのものであり、例えばモデムやネットワークインターフェース等よりなる。
【００９９】
本発明によるキャッシュカラーリング方法は、コンピュータ５１０が実行可能なコンピュータプログラムとして提供される。このコンピュータプログラムは、可換媒体記憶装置５１５に装着可能な記憶媒体Ｍに記憶されており、記憶媒体Ｍから可換媒体記憶装置５１５を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。或いは、このコンピュータプログラムは、遠隔地にある記憶媒体（図示せず）に記憶されており、この記憶媒体から通信装置５２３及びインターフェース５１６を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。
【０１００】
キーボード５２１及び／又はマウス５２２を介してユーザからプログラム実行指示があると、ＣＰＵ５１１は、記憶媒体Ｍ、遠隔地記憶媒体、或いは二次記憶装置５１４からプログラムをＲＡＭ５１２にロードする。ＣＰＵ５１１は、ＲＡＭ５１２の空き記憶空間をワークエリアとして使用して、ＲＡＭ５１２にロードされたプログラムを実行し、適宜ユーザと対話しながら処理を進める。なおＲＯＭ５１３は、コンピュータ５１０の基本動作を制御するための制御プログラムが格納されている。
【０１０１】
上記コンピュータプログラムを実行することで、上記各実施例で説明されたようにキャッシュカラーリング方法を実行する。またこのキャッシュカラーリング方法実行環境が、キャッシュカラーリング装置である。
【０１０２】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【図面の簡単な説明】
【０１０３】
【図１】本発明によるキャッシュカラーリング方法の実施例を示すフローチャートである。
【図２】動的関数フローの一例を示す図である。
【図３】動的関数フローに基づく関数強度について説明するための図である。
【図４】基本関数強度のマトリクスを示す図である。
【図５】関数ｊを少なくとも１回参照する区間の例を示す図である。
【図６】同一のキャッシュラインに配置される関数の数が多いほどキャッシュミスの回数が確率的に多くなることを説明するための図である。
【図７】第１の実施例による関数強度情報のマトリクスを示す図である。
【図８】第２の実施例による関数強度情報のマトリクスを示す図である。
【図９】第３の実施例による関数強度情報のマトリクスを示す図である。
【図１０】関数の階層構造における関数間の関係の例を示す図である。
【図１１】関数配置方法の第１の実施例を示すフローチャートである。
【図１２】図７の関数強度情報に対応した関数Ｍ（ｉ）を示す図である。
【図１３】図７の関数強度情報の場合に関数配置方法の第１の実施例に従い配置された関数の列を示す図である。
【図１４】関数配置方法の第２の実施例を示すフローチャートである。
【図１５】図７の関数強度情報の場合に関数配置方法の第２の実施例に従い配置された関数の列を示す図である。
【図１６】関数配置方法の第３の実施例を示すフローチャートである。
【図１７】キャッシュミス数をキャッシュライン毎に算出し関数を配置する処理を示すフローチャートである。
【図１８】キャッシュラインへの関数配置から各関数の論理アドレスを求める方法を示すフローチャートである。
【図１９】論理アドレスの構成及びキャッシュライン番号から論理アドレスへの変換テーブルを示す図である。
【図２０】本発明によるキャッシュカラーリングを実行する装置の構成を示す図である。
【符号の説明】
【０１０４】
１０  動的関数フロー
１１  関数強度情報
５１０  コンピュータ
５１１  ＣＰＵ
５１２  ＲＡＭ
５１３  ＲＯＭ
５１４  二次記憶装置
５１５  可換媒体記憶装置
５１６  インターフェース
５２０  ディスプレイ装置
５２３  通信装置
【図１】
0005272346.tif 000002
【図２】
0005272346.tif 000003
【図３】
0005272346.tif 000004
【図４】
0005272346.tif 000005
【図５】
0005272346.tif 000006
【図６】
0005272346.tif 000007
【図７】
0005272346.tif 000008
【図８】
0005272346.tif 000009
【図９】
0005272346.tif 000010
【図１０】
0005272346.tif 000011
【図１１】
0005272346.tif 000012
【図１２】
0005272346.tif 000013
【図１３】
0005272346.tif 000014
【図１４】
0005272346.tif 000015
【図１５】
0005272346.tif 000016
【図１６】
0005272346.tif 000017
【図１７】
0005272346.tif 000018
【図１８】
0005272346.tif 000019
【図１９】
0005272346.tif 000020
【図２０】
0005272346.tif 000021