(57)【要約】【課題】  カラーリング作業に遺伝的アルゴリズムを適用することで自動化を図り、ソフトウェア処理性能の向上を図る。【解決手段】  リンクファイル生成部１１は、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成し、初期世代集団を形成する。適合度算出部１２ａは、処理性能測定値からリンクファイルの適合度を求める。選択部１２ｂは、適合度にもとづき、次世代に残すべきリンクファイルを選択する。遺伝子コード操作部１２ｃは、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進める。処理性能測定部１３は、対象のモジュールでプログラムを実行して、処理性能測定値を求める。適合度判定部１４は、適合度の目標値をクリアしたリンクファイルがあるか否かを判定する。【選択図】  図１
2005157926.tif 000002
【特許請求の範囲】
【請求項１】
関数の最適なリンクを求めるためのカラーリングを行うカラーリング装置において、
プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成し、初期世代の集団を形成するリンクファイル生成部と、
処理性能測定値からリンクファイルの適合度を求める適合度算出部と、適合度にもとづき、次世代に残すべきリンクファイルを選択する選択部と、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進める遺伝子コード操作部と、から構成されて、初期世代から第Ｎ世代の間で、適合度の目標値をクリアしたリンクファイルが生成されるまで、遺伝的アルゴリズムを用いて関数のリンクを変化させる関数リンク制御部と、
前記関数リンク制御部によって生成されたリンクファイルからプログラムを生成し、対象のモジュールでプログラムを実行して、前記処理性能測定値を求める処理性能測定部と、
適合度の目標値をクリアしたリンクファイルがあるか否かを判定し、目標値をクリアしたリンクファイルがあれば前記リンクファイルを採用決定とする適合度判定部と、
を有することを特徴とするカラーリング装置。
【請求項２】
前記処理性能測定部は、リンクファイルから生成されたプログラムの処理を実行したときに要するサイクル数を処理性能測定値とし、前記適合度算出部は、前記サイクル数に対応する適合度を求めることを特徴とする請求項１記載のカラーリング装置。
【請求項３】
前記選択部は、リンクファイル群の中で適合度の高いリンクファイルは無条件に次世代に残すエリート戦略を行い、前記遺伝子コード操作部は、リンクファイル同士の関数の一部を組み替える交配、またはリンクファイルの中のある関数を他の関数に置き換える突然変異の少なくとも一方の遺伝子コード操作を行って、関数のリンクを変化させて、あらたなリンクファイルを生成することを特徴とする請求項１記載のカラーリング装置。
【請求項４】
遺伝的アルゴリズムを用いて関数の最適なリンクを求めるためのカラーリングを行うカラーリング方法において、
リンクファイル生成部によって、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成して、初期世代の集団を形成し、
処理性能測定値からリンクファイルの適合度を適合度算出部で求め、
適合度にもとづき、次世代に残すべきリンクファイルを選択部で選択し、
遺伝子コード操作部により、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進め、
初期世代から第Ｎ世代の間で、適合度の目標値をクリアしたリンクファイルが生成されるまで、前記適合度算出部、前記選択部、前記遺伝子コード操作部により、関数のリンクを変化させ、
処理性能測定部によって、リンクファイルからプログラムを生成し、前記処理性能測定値として、対象のモジュールでプログラムを実行したときに要するサイクル数を求め、
適合度判定部により、適合度の目標値をクリアしたリンクファイルがあるか否かを判定し、目標値をクリアしたリンクファイルがあれば前記リンクファイルを採用決定とすることを特徴とするカラーリング方法。
【請求項５】
前記選択部は、リンクファイル群の中で適合度の高いリンクファイルは無条件に次世代に残すエリート戦略を行い、前記遺伝子コード操作部は、リンクファイル同士の関数の一部を組み替える交配、またはリンクファイルの中のある関数を他の関数に置き換える突然変異の少なくとも一方の遺伝子コード操作を行って、関数のリンクを変化させて、あらたなリンクファイルを生成することを特徴とする請求項４記載のカラーリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はカラーリング装置に関し、特にソフトウェア実行時のキャッシュヒット率を上げるための、関数の最適なリンクを求めるカラーリング（coloring）を、遺伝的アルゴリズム（Genetic Algorithm ：ＧＡ）を用いて行うカラーリング装置に関する。
【背景技術】
【０００２】
近年、情報通信技術の発展に伴い、ＭＰＥＧ（Moving Picture Expert Group）４などのマルチメディア処理関連の市場要求が高まっている。ＭＰＥＧ４は、動画の再生や記録に関する動画圧縮伸張技術の規格であり、カメラ付き携帯電話機やデジタルビデオカメラなどに幅広く使用されている。
【０００３】
ＭＰＥＧでは、映像と音声のマルチメディア信号を効率よく圧縮・伝送するために高能率符号化が行われるが、高能率符号化において高画質、高音質を実現するためには、マルチメディア信号のエンコード、デコードを行うコーデックのソフトウェア処理の性能が重要な鍵となる。
【０００４】
通常、ソフトウェアの高速化処理には、プロセッサと主記憶装置（メインメモリ）との間に、小容量で高速のキャッシュメモリ（cache memory）を配置し、使用頻度が高いデータや命令をキャッシュメモリに一旦格納しておいて、プロセッサがキャッシュメモリから情報を取り出すようにして、高速アクセスを実現している。
【０００５】
プロセッサがアクセスしたいデータがキャッシュメモリ空間にある場合を、“キャッシュにヒットする”といい（キャッシュにない場合はミスヒット）、必要なデータがキャッシュメモリにある確率をヒット率（キャッシュヒット率）と呼ぶ。
【０００６】
図２２はキャッシュメモリを含むプロセッサ周辺部の概念図である。プロセッサ５１、メインメモリ５３は、外部バス５４と接続して、低速のデータ転送を行う。プロセッサ５１は、数バイト〜数十バイト単位のデータのまとまり（ブロック）をメインメモリ５３から取り出し、キャッシュメモリ５２へ格納する。
【０００７】
キャッシュメモリ５２は、命令を格納する命令キャッシュ５２ａと情報データを格納するデータキャッシュ５２ｂから構成されており、プロセッサ５１とキャッシュメモリ５２間は、バイト単位でデータを高速にやりとりして、プロセッサ５１が、キャッシュメモリ５２から必要なデータを取り出してソフトウェア処理を実行する。
【０００８】
プロセッサ５１がソフトウェア処理を実行する際は、最初にキャッシュメモリ５２にアクセスしにいく。そして、キャッシュメモリ５２に必要なデータがあれば、そのまま読み出して処理を実行するが、必要なデータがない場合には、メインメモリ５３から該当データのブロックを読み出して、キャッシュメモリ５２に対して格納する処理が発生する。
【０００９】
ここで、メインメモリ５３とキャッシュメモリ５２間のブロック入れ替え処理が頻繁に起きてしまうと、プロセッサ５１は自身の処理能力のほとんどをブロック入れ替え処理に割いてしまい、プロセッサ５１が本来のソフトウェア処理を実行できなくなってしまう。この現象はスラッシング（thrashing）と呼ばれ、スラッシングが発生すると、実際的にプロセッサが停止した状態に見えてしまう。
【００１０】
また、メインメモリ５３に配置されたプログラム（関数）は、その配置位置によりキャッシュメモリ５２への格納位置が決定されるので、スラッシング発生頻度は関数のリンク（並び）に大きく影響を受ける。
【００１１】
このため、ソフトウェア設計評価時においては、ソフトウェアが最も効率よく動作するように調整するための最適化作業としてカラーリングを行って、スラッシングの回数を低減して、処理性能の向上を図っている。カラーリングとは、スラッシングを抑制して、キャッシュヒット率を向上させるために、関数の並びであるリンクをうまく調整する最適化手法の１つである。
【００１２】
従来のカラーリング作業では、オペレータがキャッシュプロファイラというツールを用いてキャッシュラインの解析を行い、解析結果をもとに、リンクを指定していた。なお、キャッシュラインとは、キャッシュ動作で扱うキャッシュ上のメモリ単位領域のことである。１ラインは通常、３２バイトであり、３２バイトのラインが例えば、１２８個または２５６個から構成されて、小容量のキャッシュメモリを構成する。
【００１３】
図２３は従来のカラーリング作業フローを示す図である。
〔Ｓ２１〕キャッシュプロファイラを用いてキャッシュラインの解析を行う。キャッシュラインの解析とは、該当関数のラインに何回ヒットして、何回ミスヒットしたかの統計処理を行って、プログラムのどこで時間が費やされているかを解析するものである。
【００１４】
〔Ｓ２２〕リンカ（linker）を設定する。リンカ設定とは、複数のソースプログラム（関数）をコンパイルしてできたファイルを、１つの実行可能なプログラム形式に作成することである（例えば、関数ａ、ｂ、ｃ、ｄがあって、ａｂｃｄの順に並べた関数群を含む１つのファイルを、１つの実行プログラムとする）。ここでは、ステップＳ２１で解析したヒット率にもとづいて、ミスヒットが少なくなるように、複数の関数の並び替えを行った後、実行プログラムを生成する。
【００１５】
〔Ｓ２３〕ステップＳ２２で配置した関数のリンク順による実行プログラムで、対象のモジュール（例えば、ＣＰＵボードやコーデック等）の処理を実行して、サイクル数（処理に要した時間）を測定する。
【００１６】
〔Ｓ２４〕測定値があらかじめ定めた目標値をクリアしているか否かを判断する。目標値をクリアしていない場合は、ステップＳ２１に戻り、再びカラーリング作業を行う。なお、目標値にはキャッシュヒット率が用いられる。
【００１７】
一方、キャッシュヒット率の向上を図った従来技術としては、関数の呼出回数情報にもとづいて関数のメモリ配置を最適化して、キャッシュコンフリクトの回数を低減させた技術が提案されている（例えば、特許文献１）。
【特許文献１】特開２００１−２８２５４７号公報（段落番号〔００４５〕〜〔０１０６〕，第１図）
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかし、上記で説明したような、従来のカラーリング作業は、作業者によってマニュアルで行われており、キャッシュヒット率は高い目標値が設定されるので、目標値を達成するまでの一連のカラーリング作業は、非常に多くの工数（時間）を費やすといった問題があった。
【００１９】
特にキャッシュラインの解析には、キャッシュプロファイラの出力結果の解析が難しいなどの理由により、最も多くの工数がかかる。さらに、カラーリング担当者には、キャッシュを意識してソフトウェア設計をできるだけのキャッシュメモリの知識（メモリ管理、メモリ制御等）が必要である。このように、カラーリング作業は、評価作業の中でも非常に負担の重いものであった。
【００２０】
本発明はこのような点に鑑みてなされたものであり、カラーリング作業に遺伝的アルゴリズムを適用することで自動化を図り、人手による作業時間を大幅に削減して、ソフトウェア処理性能の向上を図ったカラーリング装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明では上記課題を解決するために、図１に示すような、関数の最適なリンクを求めるためのカラーリングを行うカラーリング装置１０において、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成し、初期世代の集団を形成するリンクファイル生成部１１と、処理性能測定値からリンクファイルの適合度を求める適合度算出部１２ａと、適合度にもとづき、次世代に残すべきリンクファイルを選択する選択部１２ｂと、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進める遺伝子コード操作部１２ｃと、から構成されて、初期世代から第Ｎ世代の間で、適合度の目標値をクリアしたリンクファイルが生成されるまで、遺伝的アルゴリズムを用いて関数のリンクを変化させる関数リンク制御部１２と、関数リンク制御部１２によって生成されたリンクファイルからプログラムを生成し、対象のモジュール２０でプログラムを実行して、処理性能測定値を求める処理性能測定部１３と、適合度の目標値をクリアしたリンクファイルがあるか否かを判定し、目標値をクリアしたリンクファイルがあればそのリンクファイルを採用決定とする適合度判定部１４と、を有することを特徴とするカラーリング装置１０が提供される。
【００２２】
ここで、リンクファイル生成部１１は、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成し、初期世代の集団を形成する。適合度算出部１２ａは、処理性能測定値からリンクファイルの適合度を求める。選択部１２ｂは、適合度にもとづき、次世代に残すべきリンクファイルを選択する。遺伝子コード操作部１２ｃは、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進める。処理性能測定部１３は、関数リンク制御部１２によって生成されたリンクファイルからプログラムを生成し、対象のモジュール２０でプログラムを実行して、処理性能測定値を求める。適合度判定部１４は、適合度の目標値をクリアしたリンクファイルがあるか否かを判定し、目標値をクリアしたリンクファイルがあればそのリンクファイルを採用決定とする。
【発明の効果】
【００２３】
本発明のカラーリング装置は、関数のリンクを遺伝子コードで表現したリンクファイルを生成し、適合度にもとづき、次世代に残すべきリンクファイルを選択する。そして、選択されたリンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進めて、適合度の目標値をクリアしたリンクファイルが生成されるまで、関数のリンクを変化させて最適なリンクファイルを生成する構成とした。このように、遺伝的アルゴリズムを適用したカラーリングを行うことで、従来マニュアルで行われていたカラーリング作業を自動化することができ、人手による作業時間を大幅に削減して、キャッシュヒット率を含むソフトウェア処理性能の向上を図ることが可能になる。
【発明を実施するための最良の形態】
【００２４】
以下、本発明の実施の形態を図面を参照して説明する。図１は本発明のカラーリング装置の原理図である。本発明のカラーリング装置１０は、リンクファイル生成部１１、関数リンク制御部１２、処理性能測定部１３、適合度判定部１４から構成され、関数の最適なリンクを求めるためのカラーリングを、遺伝的アルゴリズムを用いて自動的に行う装置である。なお、関数のリンクとは、プログラムを構成する複数の関数の並びのことである。
【００２５】
リンクファイル生成部１１は、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現して、遺伝子コードを持つ個体となるリンクファイルを生成し、初期世代集団を形成する。
【００２６】
関数リンク制御部１２は、適合度算出部１２ａ、選択部１２ｂ、遺伝子コード操作部１２ｃから構成される。適合度算出部１２ａは、処理性能測定部１３から送信された処理性能測定値から、リンクファイルの適合度を求める。
【００２７】
選択部１２ｂは、適合度にもとづき、次世代に残すべきリンクファイルを選択する。遺伝子コード操作部１２ｃは、選択されたリンクファイルの遺伝子コードに対して、交配や突然変異といった生殖処理の操作を施して、次世代のリンクファイルの進化を進める。関数リンク制御部１２では、これらの構成要素を用いて、初期世代から第Ｎ世代の間で、適合度の目標値をクリアしたリンクファイルが生成されるまで、関数のリンクを変化させる。
【００２８】
処理性能測定部１３は、関数リンク制御部１２によって生成されたリンクファイルからプログラムを生成し、このプログラムを対象モジュール２０で実際に実行させ、該当プログラムの処理性能測定値を求める。具体的には、該当プログラムが何サイクル要したかを示すサイクル数が処理性能測定値とすることができる。
【００２９】
適合度判定部１４は、適合度の目標値をクリアしたリンクファイルがあるか否かを判定する。目標値をクリアしたリンクファイルがあれば、このリンクファイルは、対象モジュール２０で動かすプログラムの最適なリンクファイルであるものとして採用を決定する。なお、各構成要素の詳細動作については図５以降で後述する。
【００３０】
次に本発明の詳細を説明する前にキャッシュメモリのマッピング方式とスラッシングについて説明する。キャッシュメモリとメインメモリの間でやりとりされるデータをブロックと呼ぶが、メインメモリから持ってきたブロックをキャッシュメモリのどこに配置するかを決めるやり方がマッピングである。マッピングには数種類あるが、最も単純な構成のダイレクトマッピング方式について説明する。
【００３１】
図２はダイレクトマッピング方式を示す概念図である。ダイレクトマッピング方式は、メインメモリ空間のあるブロックが、キャッシュメモリの特定のブロックに対応付けられる方式である。図の場合、メインメモリ５３は６つのブロックからなり、キャッシュメモリ５２は３つのブロックからなる。
【００３２】
ここで、メインメモリ５３のブロックＢｒ１、Ｂｒ４とキャッシュメモリ５２のブロックｂｒ１とが対応し、メインメモリ５３のブロックＢｒ２、Ｂｒ５とキャッシュメモリ５２のブロックｂｒ２とが対応し、メインメモリ５３のブロックＢｒ３、Ｂｒ６とキャッシュメモリ５２のブロックｂｒ３とが対応する。したがって、ダイレクトマッピングでは、例えば、ブロックＢｒ１に格納されたデータが、キャッシュメモリ５２に書き込まれるときは、ブロックｂｒ１のみに書き込まれ、他の領域に書き込まれることはない。
【００３３】
このために、関数ａ、ｂ、ｃ、ｄ、ｅ、ｆがこの順番の並びで、メインメモリ５３のブロックＢｒ１〜Ｂｒ６に格納されているならば、これらの関数がキャッシュメモリ５２上へ書き込まれる際は、関数ａ及び関数ｄの格納対象ブロックはブロックｂｒ１となり、関数ｂ及び関数ｅの格納対象ブロックはブロックｂｒ２となり、関数ｃ及び関数ｆの格納対象ブロックはブロックｂｒ３となる。
【００３４】
次にスラッシングについて説明する。図２の例からわかるように、ダイレクトマッピング方式では、メインメモリとキャッシュメモリが多対１の対応となるので、キャッシュメモリ空間の１つのブロック位置に書き込まれるブロックがメインメモリには多数存在することになる。
【００３５】
このため、プロセッサがキャッシュメモリの同一ブロックに対応付けられた関数にアクセスを繰り返すと、キャッシュにヒットせず、キャッシュメモリの書き換え動作が頻繁に生じ、本来実行すべき処理のスピードが低下（または停止）してしまう。
【００３６】
図３はスラッシングを説明するための図である。メインメモリ５３ａは９個のブロックＢｒ１〜Ｂｒ９を持ち、キャッシュメモリ５２は３つのブロックｂｒ１〜ｂｒ３を持つ。そして、メインメモリ５３ａのブロックとして、（Ｂｒ１，Ｂｒ２，Ｂｒ３）、（Ｂｒ４，Ｂｒ５，Ｂｒ６）、（Ｂｒ７，Ｂｒ８，Ｂｒ９）が、キャッシュメモリ５２のブロック（ｂｒ１，ｂｒ２，ｂｒ３）にそれぞれマッピング（対応付け）されている。また、メインメモリ５３ａのブロックＢｒ１〜Ｂｒ９に関数ｆ１〜ｆ９がこのリンクで格納されている。
【００３７】
ここで、関数ｆ２、ｆ５、ｆ８で処理を行うプログラムがあるとする。これらの関数はメインメモリ５３ａからキャッシュメモリ５２上の空間へ移動しておくことになるが、上記の関数のリンク（f1,f2,f3,f4,f5,f6,f7,f8,f9）では、関数ｆ２、ｆ５、ｆ８はキャッシュメモリ５２のブロックｂｒ２を同一格納領域とするため、キャッシュコンフリクトが生じることになる。
【００３８】
したがって、プロセッサは、最初の関数ｆ２についてはヒットするが、次の関数ｆ５ではミスヒットとなるので、関数ｆ５をメインメモリ５３ａから読み出してキャッシュメモリ５２のブロックｂｒ２に上書きする処理が発生する。関数ｆ５の次の関数ｆ８の場合も同様である。このように、同一ブロックに対応付けられた関数にアクセスを繰り返すような場合には、ブロック入れ替え処理が連続して発生することになる。
【００３９】
図４はカラーリング後の関数のリンク例を示す図である。図３のような状況で、関数ｆ２、ｆ５、ｆ８のファイルの処理を行うプログラムに対して、スラッシングを抑制する場合には、図のように例えば、ブロックＢｒ１〜Ｂｒ３に関数ｆ２、ｆ５、ｆ８を配置しておけばよい。すなわち、関数のリンクを（f2,f5,f8,f1,f3,f4,f6,f7,f9）にしておけば、関数ｆ２、ｆ５、ｆ８はそれぞれブロックｂｒ１、ｂｒ２、ｂｒ３にそれぞれ格納しておくことができるので、スラッシングをなくすことが可能になる。
【００４０】
従来、このような関数のリンクを最適化するためのカラーリング作業は、人手によって行われていたので非常に工数がかかり、また定量性にも欠けていた。本発明では、生物の進化過程を問題解決のために応用したアルゴリズムである遺伝的アルゴリズムをカラーリングに応用して、カラーリング作業を自動化して精度を上げ、人手による作業時間を大幅に削減して、ソフトウェア処理性能の向上を図るものである。
【００４１】
次に本発明のカラーリング装置１０の動作について説明する。なお、以降では遺伝的アルゴリズムをＧＡ、遺伝的アルゴリズムを用いた本発明のカラーリングをＧＡカラーリングとも呼ぶ。最初にリンクファイル生成部１１について説明する。
【００４２】
リンクファイル生成部１１は、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現する。プログラムの関数のリンクを遺伝子コードで表現したファイルをリンクファイル（ＧＡでは個体に該当する）と呼ぶ。ここで、関数ａ、ｂ、ｃ、ｄ、ｅの５個の関数を含み、ａ→ｃ→ｅ→ｄ→ｂのリンクで１つの実行プログラムＡが形成されるものとして、このａｃｅｄｂのリンクを遺伝子コードで表す場合について図５を用いて説明する。
【００４３】
図５はリンクする関数と遺伝子との対応関係を示す図である。
〔Ｓ１〕最初に、関数のリンクをａｂｃｄｅと仮に設定して、ａｂｃｄｅのそれぞれに、１、２、３、４、５と順番を付ける。このときａｃｅｄｂのリンクに対して、関数ａはａｂｃｄｅの並びの中で１番目なので遺伝子を１とする。
【００４４】
〔Ｓ２〕ａｂｃｄｅの順番からａを削除し、残るｂｃｄｅに１２３４とそれぞれ番号を付ける。ａｃｅｄｂのリンクに対して、関数ｃは、あらたなｂｃｄｅの並びのなかで、２番目に位置するので、関数ｃの遺伝子を２とする。
【００４５】
〔Ｓ３〕ｂｃｄｅの順番からｃを削除し、残るｂｄｅに１２３とそれぞれ番号を付ける。ａｃｅｄｂのリンクに対して、関数ｅは、あらたなｂｄｅの並びのなかで、３番目に位置するので、関数ｅの遺伝子を３とする。
【００４６】
〔Ｓ４〕ｂｄｅの順番からｅを削除し、残るｂｄに１２とそれぞれ番号を付ける。ａｃｅｄｂのリンクに対して、関数ｄは、あらたなｂｄの並びのなかで、２番目に位置するので、関数ｄの遺伝子を２とする。
【００４７】
〔Ｓ５〕ｂｄの順番からｄを削除し、残るｂに１と番号を付ける。ａｃｅｄｂのリンクに対して、関数ｂは、１番目に位置するので、関数ｂの遺伝子コードを１とする。したがって、ａｃｅｄｂのリンクを遺伝子コードで表すと、１２３２１と表現されることになる。なお、１２３２１の各数字を遺伝子、遺伝子が集まった１２３２１を遺伝子コード（または染色体）と呼ぶ。
【００４８】
ここで、本発明のＧＡカラーリングは、複数の関数からなるプログラムに対し、そのプログラムを実行したときに、最もサイクル数が短くなるように（すなわち、最もキャッシュヒット率が高くなるように）、それら複数個の関数の最適なリンクを決定するものである。
【００４９】
例えば、プログラムＡが関数ａ、ｂ、ｃ、ｄ、ｅを持つ場合には、プログラムＡが高速処理可能となるような、関数ａ〜関数ｅのリンク（メインメモリからキャッシュメモリへ書き込まれた際に、プロセッサがキャッシュメモリにアクセスしたときにスラッシングが起きないようなメインメモリ上での関数の並び）を最適に決めることになる。この場合、まず、リンクファイル生成部１１では、関数ａ〜関数ｅのリンクを何通りか最初にランダムに設定して、それらのリンクの遺伝子コードをそれぞれ求めて、複数のリンクファイルを作成しておく。
【００５０】
このようにして、関数のリンクが遺伝子という形に置き換えられて作成されたリンクファイルを初期世代集団として用意しておき、初期世代集団の中のリンクファイルに対して、後述する交配や突然変異といった遺伝子操作を施すことで、最適解（最適なリンク）を求めていく。
【００５１】
なお、図５の説明では、プログラムＡは、関数のリンクがａｃｅｄｂで実行されるものであって、ａｃｅｄｂを遺伝子コード１２３２１と表現する過程を示したが、この場合ＧＡでは、ａｃｅｄｂの側をＰＴＹＰＥ（phenotype）または表現型（現実の問題に対する解の形）、１２３２１の側をＧＴＹＰＥ（genotype）または遺伝子型（ＧＡによって操作することができる解の形）と呼んでいる。
【００５２】
次に適合度算出部１２ａと処理性能測定部１３について説明する。処理性能測定部１３は、リンクファイルを一旦プログラム形式に書き直して、測定対象のモジュール２０に変換後のプログラムを与える。そして、対象モジュール２０においてプログラム処理が実行されることになるが、処理性能測定部１３は、このときに要する実行処理のサイクル数を測定して、リンクファイル毎の測定結果を適合度算出部１２ａに通知する。その後、適合度算出部１２ａは、サイクル数に対応する適合度を求める。適合度とは解の評価値のことであり、適合度が高いほど最適解に近いということになる。
【００５３】
なお、リンクファイル生成部１１によって生成された初期世代集団の中のリンクファイルの適合度を求める場合には（一番最初の適合度を求める場合には）、関数リンク制御部１２での処理は行わずに、直接、処理性能測定部１３において、初期世代集団のリンクファイルのプログラム処理を行ってサイクル数を測定し、適合度算出部１２ａは適合度を求め、その後に関数リンク制御部１２による処理が行われることになる。
【００５４】
次に選択部１２ｂについて説明する。選択部１２ｂは、適合度にもとづき、次世代に残すべきリンクファイルの選択処理（並び替えも含む）を行う。選択方法としては、本発明では、エリート戦略を用いる。エリート戦略とは、個体群の中で適合度の高い個体（リンクファイル）は無条件に次世代に残す方法のことである。本発明では、適合度の高いリンクファイルを選択してこれを次世代に残すことになる。
【００５５】
図６はエリート戦略の様子を示す図である。リンクファイルＬ１〜Ｌ６があり、これらの適合度を順に１、３、２、５．２、５．５、５．３とする（適合度の数値が低いほど、適合度が高く、評価が良好だとする）。これらリンクファイルＬ１〜Ｌ６の中から４つのリンクファイルを選択する場合を考える。ここでは、適合度の高い上位３個体をエリート戦略で選ぶものとすると、適合度の数値が１、２、３であるリンクファイルＬ１、Ｌ３、Ｌ２が選択されることになる。また、残りの１つは、適合度の低い下位３個体からランダムに１つを選ぶ。図では適合度５．３のリンクファイルＬ６を選択している。
【００５６】
このように、次世代に残す個体を選択する際に、適合度の高い個体を選択することで、良好な個体が増加することになり、最適解を探索する能力が向上することになる。なお、エリート戦略は、選択部１２ｂだけで行われる処理ではなく、適合度の高い個体はそのまま次世代にコピーしていくという点で、後述の遺伝子コード操作部１２ｃにおいても行われる処理である。
【００５７】
次に遺伝子コード操作部１２ｃについて説明する。上記のエリート戦略だけを行って、適合度の高い個体を次世代に残していっても、進化は進まないので、遺伝子コード操作部１２ｃでは、リンクファイルの遺伝子コードを操作して、次世代のリンクファイルの進化を進める。
【００５８】
リンクファイルの進化を進めるとは、交配や突然変異といった生殖処理を行って（交配、突然変異は、交配オペレータ、突然変異オペレータとも呼ばれ、遺伝的アルゴリズムを特徴づけるものとして、双方を総称してＧＡオペレータとも呼ばれる）、遺伝子コードの形を変化させる（関数のリンクを変化させる）ということである。
【００５９】
図７は交配の様子を示す図である。交配（crossover）は、親の個体の遺伝子コードを一部組み替えて新しい個体を生成する処理である。図の場合、親Ａの遺伝子コードはａｂｃｄｅｆであり、親Ｂの遺伝子コードは１２３４５６である。これらの遺伝子コードに対して、一点交配（交配点を１箇所選んで、その前と後で、遺伝子を入れ替える方法）を施すと、点線で示す交配点の後ろ部分を互いに組み替えることで、遺伝子コードがａｂ３４５６となる子ａと、遺伝子コードが１２ｃｄｅｆとなる子ｂが生成される。このような操作を行って進化を進めることで、より最適な解が得られる可能性が高くなる。
【００６０】
図８は突然変異の様子を示す図である。突然変異（mutation）は、遺伝子コードの一部をある確率で変化させて、新しい個体を生成する処理である。図の場合、親Ｃの遺伝子コードはａｂｃｄｅｆであり、変異点をｂとすると、ｂがＢに突然変異することで、遺伝子コードがａＢｃｄｅｆの子ｃが生成されている。このような操作を行って進化を進めることで、より最適な解が得られる可能性が高くなる。
【００６１】
ここで、遺伝子コードの操作として、交配だけを行っていたのでは、十分な進化が得られない場合が多い。なぜなら、交配によって生じる個体は、結局、親の一部のコピーであるから、交配だけを繰り返していると、狭い範囲の局所的な解に落ち着いてしまうからである。したがって、突然変異の処理を行うことで、新しい遺伝子コードを生成して、局所解に陥りにくくするものである（または、局所解へ陥っても、そこから脱出する効果がある）。
【００６２】
図９は突然変異による局所解からの脱出を説明するための図である。横軸に探索空間、縦軸に適合度をとり、遺伝子コード操作により個体（リンクファイル）の遺伝子が変化する状態をグラフで示している。
【００６３】
遺伝子コードの操作を行う最初のリンクファイルを、リンクファイルＬ１ａとする。そして、リンクファイルＬ１ａに遺伝子コード操作として、交配のみを施したとする。
このとき、リンクファイルＬ１ａに交配を施してリンクファイルＬ１ｂとなり、リンクファイルＬ１ｂに交配を施してリンクファイルＬ１ｃとなって、次第に局所解ｓ１に近づいていく（遺伝子コード操作を行えば、必ず解に近づいていくのではなく、遠ざかる場合も当然あるが、図を簡単にするため、解に近づいていく場合のみ示す）。しかし、このような交配処理のみを行っていると、実際には、最適解ｓ０があるにもかかわらず、局所解ｓ１が存在する山の付近だけで移動を繰り返すことになり、最適解ｓ０に一向に近づくことができない。
【００６４】
したがって、このようなことがないように、突然変異を行って解が存在する山を移動させてやる（局所解ｓ１が存在する山から脱出させる）。例えば、リンクファイルＬ１ｃに突然変異を施して、リンクファイルＬ２ａに変化したとする。すると、この場合、最適解ｓ０が存在する山に移動したことになるので、その後、リンクファイルＬ２ａに交配を施すことでリンクファイルＬ２ｂとなり、次第に最適解ｓ０に近づいていくことができる。このように、遺伝子コード操作として、交配だけでなく、突然変異も行うことで、より広い範囲で最適な解を探すことが可能になる。
【００６５】
このように、選択、交配、突然変異といった処理により、適合度の低いリンクファイルは順次淘汰される仕組みになっているため、結果的に、良好な適合度を持ったリンクファイルが生き残ってくることになる。
【００６６】
次に本発明のＧＡカラーリング処理の流れについて図１０〜図１７を用いて説明する。なお、適合度が５サイクル未満のリンクファイルの探索を行うものとする。図１０は初期世代集団を示す図である。リンクファイル生成部１１の処理によって、リンクファイルＬ１〜Ｌ３の遺伝子コードＧ１〜Ｇ３で初期世代集団が生成されている。リンクファイルＬ１〜Ｌ３は、関数ａ、ｂ、ｃ、ｄ、ｅを有する。
【００６７】
リンクファイルＬ１の関数ａ〜関数ｅのリンクは、ａ→ｂ→ｃ→ｅ→ｄであり、この遺伝子コードＧ１は１１１２１となる（図５で上述した手順を行えば１１１２１となることがわかる。生成手順の説明は省略する）。また、遺伝子コードＧ１を親Ａとも呼ぶ。
【００６８】
また、リンクファイルＬ２の関数ａ〜関数ｅのリンクは、ａ→ｃ→ｅ→ｄ→ｂであり、この遺伝子コードＧ２は１２３２１となる。また、遺伝子コードＧ２を親Ｂとも呼ぶ。さらに、リンクファイルＬ３の関数ａ〜関数ｅのリンクは、ａ→ｂ→ｃ→ｄ→ｅであり、この遺伝子コードＧ３は１１１１１となる。また、遺伝子コードＧ３を親Ｃとも呼ぶ。
【００６９】
図１１は適合度が算出されたリンクファイルを示す図である。ここでは、説明を簡単にするため、適合度＝サイクル数とする。したがって、適合度の値が小さいほどキャッシュヒット率が高く、良好な評価値ということになる。適合度算出部１２ａにより、リンクファイルＬ１〜Ｌ３のそれぞれの適合度は５、１０、８サイクルと認識されたとする。
【００７０】
図１２は適合度の高い順に並び替えられたリンクファイルを示す図である。親Ａは適合度５サイクル、親Ｂは適合度１０サイクル、親Ｃは適合度８サイクルであるから、選択部１２ｂにより、適合度の高い順に親Ａ、親Ｃ、親Ｂと並び替えられる。
【００７１】
図１３は交配したリンクファイルを示す図である。遺伝子コード操作部１２ｃは、適合度の最も高い親Ａをエリート戦略により残し、残りの親Ｂ、Ｃを交配させてあらたな遺伝子コードを生成するようにする。ここでは、遺伝子コードＧ３、Ｇ２に対し、図に示す交配点Ｐ１から前後組み替える。
【００７２】
生成された子ｃの遺伝子コードＧ４は１２１１１となり、これは関数のリンクがａ→ｃ→ｂ→ｄ→ｅのリンクファイルＬ４となる。また、子ｂの遺伝子コードＧ５は１１３２１となり、これは関数のリンクがａ→ｂ→ｅ→ｄ→ｃのリンクファイルＬ５となる。なお、子ｃ、子ｄのリンクファイルＬ４、Ｌ５の適合度についてはこの時点では算出されていない。
【００７３】
図１４は突然変異したリンクファイルを示す図である。遺伝子コード操作部１２ｃは、ランダムに選んだ個体に突然変異を行う。ここでは、親Ｂの一番左の遺伝子に突然変異を行って、遺伝子を１→２へ変化させる。すると、突然変異後の親Ｂ１の遺伝子コードＧ２−１は、２２３２１となり、これは関数のリンクがｂ→ｃ→ｅ→ｄ→ａのリンクファイルＬ２−１となる。なお、親Ｂ１のリンクファイルＬ２−１の適合度についてはこの時点では算出されていない。
【００７４】
図１５は適合度が算出されたリンクファイルを示す図である。適合度算出部１２ａにより、リンクファイルＬ２−１、Ｌ４、Ｌ５のそれぞれの適合度は７、４、６サイクルと認識されたとする。図１６は適合度の高い順に並び替えられたリンクファイルを示す図である。選択部１２ｂにより、適合度の高い順に子ｃ、親Ａ、子ｂ、親Ｂ１、親Ｃと並び替える。
【００７５】
図１７は採用決定されたリンクファイルを示す図である。適合度判定部１４は、適合度が５未満のリンクファイルを採用決定するので、ここでは、子ｃの遺伝子コードＧ４のリンクファイルＬ４が適合度＝４サイクルで、目標値をクリアしているので、リンクファイルＬ４を採用決定としてＧＡカラーリングを終了する。
【００７６】
次にＧＡカラーリング処理をフローチャートで説明する。図１８はＧＡカラーリング処理を示すフローチャートである。
〔Ｓ１１〕リンクファイル生成部１１は、プログラムを構成する関数に対し、関数のリンクを遺伝子コードで表現し、遺伝子コードを持つ個体となるリンクファイルを生成して、初期世代集団を形成する。
【００７７】
〔Ｓ１２〕適合度算出部１２ａは、リンクファイルの適合度を求める。例えば、処理サイクル数を適合度とする。
〔Ｓ１３〕選択部１２ｂは、適合度にもとづき、次世代に残すべきリンクファイルを選択する。
【００７８】
〔Ｓ１４〕遺伝子コード操作部１２ｃは、選択されたリンクファイルの遺伝子に交配、突然変異の遺伝子コードを操作して、次世代のリンクファイルの進化を進める。
〔Ｓ１５〕処理性能測定部１３は、リンクファイルからプログラムを生成し（リンカ設定）、対象モジュールでプログラムを実行して、処理性能測定値を求める。
【００７９】
〔Ｓ１６〕適合度判定部１４は、適合度の目標値をクリアしたリンクファイルがあるか否かを判定し、目標値をクリアしたリンクファイルがあればリンクファイルを採用決定とする。
【００８０】
次に本発明のＧＡカラーリングを、ＭＰＥＧ４エンコーダの実際のカラーリング処理に適用した場合の測定結果について説明する。図１９は測定環境を示す図である。測定端末１００には、本発明のカラーリング装置１０が含まれる。測定端末１００では、ＧＡカラーリングによって生成されるリンクファイルをプログラムに直して、エンコーダ・ボード２０ａに渡す。エンコーダ・ボード２０ａは、与えられたプログラムを実行し、測定端末１００ではそのプログラムの実行サイクル数を測定し、適合度を算出する。
【００８１】
図２０は測定結果を示す図である。測定は１フレームごとの処理時間（ｍｓ）を比較し、カラーリング実施前の処理時間（ｍｓ）とカラーリング実施後の処理時間（ｍｓ）と比較している。比較した結果は、判定（％）の項目に示された値が小さいほど処理時間が少ないことを示す。また、図２１は処理時間の遷移グラフを示す図である。横軸はフレーム数、縦軸は処理に要した測定時間（ｍｓ）であり、図２０の測定結果を処理時間の遷移グラフで示したものである。
【００８２】
ここで、図２０の１フレーム目を見ると、カラーリングを行う前の処理時間は３０．６８ｍｓである。この１フレーム目に従来のカラーリングを施した場合は２９．５４５ｍｓであるが、本発明のＧＡカラーリングを行うと２８．５１４ｍｓとなり、１．０３１ｍｓ時間が短縮されている。また、判定（％）で見ると、従来のカラーリングでは、（２９．５４５／３０．６８）×１００≒９６．３０１％であり、本発明のＧＡカラーリングでは、（２８．５１４／３０．６８）×１００≒９２．９４０％であり、従来よりも本発明は小さい数値を示しているので、本発明のＧＡカラーリングの方が良好な評価値が得られている（２フレーム目以降もＧＡカラーリングの方が良好な評価値が得られている）。
【００８３】
さらに、最大負荷の処理時間同士を比較すると、従来のカラーリングを１００％とした時に、ＧＡカラーリングは９３．４９１％となり約６．５％向上し、これはフレームレートでは、２フレーム分の処理に相当するものである。
【００８４】
本発明のＧＡカラーリングでは、従来のカラーリング作業よりも良好な数値を得ており、ＧＡカラーリングの有効性を確かめることができた。また、図２０、図２１の測定においては、従来のカラーリングは、手動で約５日の作業時間に対して、ＧＡカラーリングは自動で約２日〜３日の実施時間であった。このように、作業効率の点に関しても、本発明の方が優れていることがわかる。
【００８５】
以上説明したように、本発明によれば、 カラーリング作業がすべて自動化されるので、キャッシュプロファイラの出力結果を作業者が解析するなどの作業が必要なくなり、人手による負担が大幅に削減されるので、作業時間の短縮化が可能になり、利便性の向上を図ることが可能になる。
【００８６】
なお、交配オペレータの精度を向上させるために、スキーマ定理などを取り入れ、適合度の高い染色体の遺伝子パターンを残すように改良することが考えられる。また、本発明の交配オペレータでは、一点交配を用いているが、多点交配や一様交配を用いて探索能力を強化し、より局所解の回避を行う確率を高めるようにすることも可能である。
【図面の簡単な説明】
【００８７】
【図１】本発明のカラーリング装置の原理図である。
【図２】ダイレクトマッピング方式を示す概念図である。
【図３】スラッシングを説明するための図である。
【図４】カラーリング後の関数のリンク例を示す図である。
【図５】リンクする関数と遺伝子との対応関係を示す図である。
【図６】エリート戦略の様子を示す図である。
【図７】交配の様子を示す図である。
【図８】突然変異の様子を示す図である。
【図９】突然変異による局所解からの脱出を説明するための図である。
【図１０】初期世代集団を示す図である。
【図１１】適合度が算出されたリンクファイルを示す図である。
【図１２】適合度の高い順に並び替えられたリンクファイルを示す図である。
【図１３】交配されたリンクファイルを示す図である。
【図１４】突然変異したリンクファイルを示す図である。
【図１５】適合度が算出されたリンクファイルを示す図である。
【図１６】適合度の高い順に並び替えられたリンクファイルを示す図である。
【図１７】採用決定されたリンクファイルを示す図である。
【図１８】ＧＡカラーリング処理を示すフローチャートである。
【図１９】測定環境を示す図である。
【図２０】測定結果を示す図である。
【図２１】処理時間の遷移グラフを示す図である。
【図２２】キャッシュメモリを含むプロセッサ周辺部の概念図である。
【図２３】従来のカラーリング作業フローを示す図である。
【符号の説明】
【００８８】
１０  カラーリング装置
１１  リンクファイル生成部
１２  関数リンク制御部
１２ａ  適合度算出部
１２ｂ  選択部
１２ｃ  遺伝子コード操作部
１３  処理性能測定部
１４  適合度判定部
２０  対象モジュール
【図１】
2005157926.tif 000003
【図２】
2005157926.tif 000004
【図３】
2005157926.tif 000005
【図４】
2005157926.tif 000006
【図５】
2005157926.tif 000007
【図６】
2005157926.tif 000008
【図７】
2005157926.tif 000009
【図８】
2005157926.tif 000010
【図９】
2005157926.tif 000011
【図１０】
2005157926.tif 000012
【図１１】
2005157926.tif 000013
【図１２】
2005157926.tif 000014
【図１３】
2005157926.tif 000015
【図１４】
2005157926.tif 000016
【図１５】
2005157926.tif 000017
【図１６】
2005157926.tif 000018
【図１７】
2005157926.tif 000019
【図１８】
2005157926.tif 000020
【図１９】
2005157926.tif 000021
【図２０】
2005157926.tif 000022
【図２１】
2005157926.tif 000023
【図２２】
2005157926.tif 000024
【図２３】
2005157926.tif 000025