(57)【要約】      （修正有）【課題】動的コンパイラを備えるVLIW型マイクロプロセッサにおいて、オーバーヘッドを低減することや、スケジューリング後のオブジェクト・コードを格納するためのメモリ容量を抑えること。【解決手段】動的コンパイラを備えるVLIW型マイクロプロセッサに関するものであり、より効率的に命令の処理を行うことにより、マイクロプロセッサの演算性能を改善するものである。具体的には、動的コンパイラを備えるVLIW型マイクロプロセッサにおける命令の処理において、遺伝的アルゴリズム（ＧＡ）を用いることにより、動的コンパイラの実行に伴うオーバーヘッドの低減や、内部命令のスケジューリング後のオブジェクト・コードを格納するためのメモリ容量を抑えることを特徴とする。【選択図】図１
2005032018.tif 000002
【特許請求の範囲】
【請求項１】
ハードウェア部分、およびソフトウェア部分を含むマイクロプロセッサにおいて、
前記ソフトウェア部分に遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサ。
【請求項２】
請求項１において、
前記ソフトウェア部分に動的コンパイラを含み、前記動的コンパイラの処理に遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサ。
【請求項３】
請求項１において、
前記ソフトウェア部分に含まれる動的コンパイラは、命令分岐予測、命令パスの選択、内部命令のスケジューリング、および最適化を含む複数の処理を行い、前記複数の処理のうち少なくとも１つに遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサ。
【請求項４】
請求項１乃至請求項３のいずれか一において、
前記ソフトウェア部分に動的コンパイラ、遺伝的アルゴリズムエンジンを備えることを特徴とするマイクロプロセッサ。
【請求項５】
請求項４において、
前記遺伝的アルゴリズムエンジンは、前記動的コンパイラの一部に含まれることを特徴とするマイクロプロセッサ。
【請求項６】
請求項４または請求項５において、
前記遺伝的アルゴリズムエンジンは、
初期集団を決定する手段と、
前記初期集団を評価する手段と、
評価対象を評価の適応度に応じて選択する手段と、
交叉、突然変異といった遺伝的な操作を行う手段と、
再度評価して、前記一連の処理を継続するか否かの評価を行う手段を少なくとも備えたことを特徴とするマイクロプロセッサ。
【請求項７】
ハードウェア部分、およびソフトウェア部分を含むVLIW型マイクロプロセッサにおいて、
前記ソフトウェア部分に遺伝的アルゴリズムを用いることを特徴とするVLIW型マイクロプロセッサ。
【請求項８】
請求項７において、
前記ソフトウェア部分に動的コンパイラを含み、前記動的コンパイラの処理に遺伝的アルゴリズムを用いることを特徴とするVLIW型マイクロプロセッサ。
【請求項９】
請求項７において、
前記ソフトウェア部分に含まれる動的コンパイラは、命令分岐予測、命令パスの選択、内部命令のスケジューリング、および最適化を含む複数の処理を行い、前記複数の処理のうち少なくとも１つに遺伝的アルゴリズムを用いることを特徴とするVLIW型マイクロプロセッサ。
【請求項１０】
請求項７乃至請求項９のいずれか一において、
前記ソフトウェア部分に動的コンパイラ、遺伝的アルゴリズムエンジンを備えることを特徴とするVLIW型マイクロプロセッサ。
【請求項１１】
請求項１０において、
前記遺伝的アルゴリズムエンジンは、前記動的コンパイラの一部に含まれることを特徴とするVLIW型マイクロプロセッサ。
【請求項１２】
請求項１０または請求項１１において、
前記遺伝的アルゴリズムエンジンは、
初期集団を決定する手段と、
前記初期集団を評価する手段と、
評価対象を評価の適応度に応じて選択する手段と、
交叉、突然変異といった遺伝的な操作を行う手段と、
再度評価して、前記一連の処理を継続するか否かの評価を行う手段を少なくとも備えたことを特徴とするマイクロプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的コンパイラを備えるVLIW型マイクロプロセッサにおいて、その処理効率を向上させる技術に関する。
【背景技術】
【０００２】
２０００年１月に米Transmeta社のx86互換プロセッサCrusoeについてのニュースが世界中に伝えられたことによって、その後のプロセッサアーキテクチャの流れは、それまでの、CISC(Complex Instruction Set computer)からRISC(Reduced Instruction Set Computer)へのアーキテクチャ移行以来の大きな流れが登場することになった。
【０００３】
それまで多く使われていたx86互換プロセッサは、Out-of-Order型スーパースカラー・アーキテクチャである。ここで、Out-of-Orderとは、オブジェクト・コードで記述された命令の実行順序にかかわりなく命令を実行する機能であって、命令間に依存関係がないことを検証する機能、及び、実行済み命令の演算結果をオブジェクト・コードで記述された順番に並び直す機能を必要とする。また、スーパースカラーとは、２個以上の命令を同時に実行する機能。１サイクルで実行する平均命令数が多くなるので、１命令しか実行しないマイクロプロセッサに比べて、同じ動作周波数でも高い演算機能を発揮することが可能となる。
【０００４】
Crusoeのプロセッサアーキテクチャは、VLIW(Very Long Instruction Word)を採用して、x86互換性をCode Morphing Softwareと呼ばれるランタイム・ソフトウェアプログラムによりX86オブジェクト・コードを実行時にVLIWコードに変換し、VLIWプロセッサでエミュレーションすることを特徴としている。これに、付随する特徴としては、低消費電力性がある。複雑な、Out-of-Order型スーパースカラ・アーキテクチャから単純なVLIWアーキテクチャにしたことで、必要とするトランジスタ数を半減することに加えて、Transmeta社で"LongRun Technology"と呼ぶ動的電源電圧最適化を採用している。
【０００５】
ここで、VLIW技術とは、128ビット、或いは、256ビットといった長いフォーマットの命令で、複数の演算ユニットを使った処理を並列に記述するアーキテクチャであり、例えば、１命令で、32ビット命令を４個分、或いは、８個分の処理が可能となる。この技術は、Josh Fisherが、1978年に初めて発表した技術である。
【０００６】
さて、上記で述べた要素技術であるVLIW技術やソフトウェアを用いたコード変換技術は、注目には値するが、個々の技術そのものは、それほど目新しい技術ではない。Crusoeで注目されている技術的価値は、動的コンパイラを備えたVLIW型マイクロプロセッサであることが、重要である。なぜならば、VLIW技術とコード変換技術の単なる組み合わせを行う場合には、技術的問題点を抱えることになる。問題点とは、コード変換の時間的、及び、空間的オーバーヘッドである。時間的オーバーヘッドとは、例えば、x86オブジェクト・コードをネイティブのVLIWコードに変換するのに要する時間であり、空間的オーバーヘッドとは、コード変換ソフト自身が主記憶に占める大きさ、及び、変換後のVLIWコードを主記憶上にキャッシングするのに要するメモリサイズである。特に、時間的オーバーヘッドの問題は重要であり、せいぜい直接実行するプロセッサの数十％の性能しか出ないのが、通常である。
【０００７】
Transmeta社は、動的バイナリー・コード変換技術を採用することによって、これらのオーバーヘッドの問題解決をはかっている。これらの動的コンパイラ技術は、従来の静的コンパイラ技術による最適化を補完するものである。動的コンパイラ技術とは、あるプログラムのオブジェクト・コードに命令スケジューリングを施すことで、特定のマイクロプロセッサに対して最適化したオブジェクト・コードに変換するソフトウェアを呼ぶ。
【０００８】
ハードウェアのボトルネックをソフトウェアで解消するこれらの技術について、より具体的に図１を用いて説明する。図１（a）のスーパースカラー型マイクロプロセッサでは、命令スケジューリングがハードウェアで構成されており、ボトルネックとなっていた。それに対して、図１（b）の様な動的コンパイラを備えたVLIW型プロセッサは、ソフトウェアで内部命令のスケジューリングを担っているので、ハードウェアで内部命令のスケジューリングを行う回路は、不要になる。ハードウェアとしては、その分回路が単純となり、動作周波数を上げることが容易となる。ちなみにプロセッサの演算性能は、次式（１）で表現される。
〔式１〕
演算性能＝動作周波数×１サイクルに実行する命令の平均数
【０００９】
１サイクルに実行する命令の平均数が減らせるという観点からも、動的コンパイラを備えたVLIW型プロセッサは、より優れている。最大の利点は、スケジューリングの自由度が大きいことである。このことを図２を用いて説明する。
【００１０】
図２（a）の様に、スーパースカラー型マイクロプロセッサでは、主記憶からフェッチした命令をリオーダ・バッファと呼ばれるバッファにいったん格納する。Out-of-order実行機能によって、格納した命令の中から同時に実行できるものを選択して演算ユニットに送り込む。ところが、リオーダ・バッファに格納できる命令数は、数十個〜百数十個程度しかないので、同時に実行出来る命令を見つけにくい。すなわち、ハードウェアによるスケジューリングでは、マイクロプロセッサに集積可能なリオーダ・バッファの容量によってスケジューリングの自由度が制限されてしまう。
【００１１】
これに対して、図２（b）の様に、主記憶に格納した多くの命令の中から同時に実行できる命令を選択する動的コンパイラならば、同時に実行出来る命令を発見する確率が高くなる。すなわち、同じオブジェクト・コードを実行する場合、スーパースカラー型マイクロプロセッサに比べて、動的コンパイラを備えたVLIWマイクロプロセッサでは、１サイクルに実行する命令の平均数を増やすことが可能となる。１サイクルに実行する命令の平均数は、次式（２）の様に、IPC、TCM、DCOによって表現されるが、上記で述べたことは、IPCの低減を意味する。ここで、IPCとは１命令の実行に必要なサイクル数、TCMとはトランスレーション・キャッシュのミス率、DCOとは動的コンパイラのオーバーヘッドを意味する。
〔式２〕
１サイクルに実行する命令の平均数＝１/(IPC＋TCM×DCO)
【００１２】
TCMは、キャッシュ容量の増大で低減可能である。DCOの低減も動的コンパイラにとって、有利なところである。プログラムの実行状況に応じて、繰り返し実行する命令パスを検出し、その部分を重点的にスケジューリングして最適化することで、動的コンパイラのオーバーヘッドを低減できる。しかも、一度最適化したオブジェクト・コードをキャッシュに蓄えることを行えば、次に実行する時には、動的コンパイラも使う必要が無くなり、その後のオーバーヘッドを激減することが可能となり、Crusoeでは、この辺りも考慮されている。Crusoeでは、更に、動的コンパイラの効率を上げるために幾つかのハードウェアの補助機能を追加している。シャドウ・レジスタ機能とゲート付きストア・バッファ機能である。これにより、スペキュレーション処理時の例外を正確に行うことが可能となる。詳細は、米国特許番号：６，０３１，９９２等に記載されている。また、エイリアス・ディテクションのメカニズムやトランスレイティド・ビットをもっている。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上記で述べた様に、Crusoeに代表される動的コンパイラを備えるVLIW型マイクロプロセッサにおいて、動的コンパイラは、大分工夫がされており、オーバーヘッドの低減への努力が試みられているが、スーパースカラー型マイクロプロセッサに置き換わるだけの効率には至っていない。つまり、現状の動的コンパイラには、なお、多くの課題を残しているのである。
【００１４】
ここで、解決しようとする課題は、更に、動的コンパイラの実行に伴うオーバーヘッドを低減することや、スケジューリング後のオブジェクト・コードを格納するためのメモリ容量を抑えることである。結果として、１サイクルに実行する命令の平均数を増加させることによって、マイクロプロセッサの演算性能を上げることにある。
【課題を解決するための手段】
【００１５】
本発明は、動的コンパイラを備えるVLIW型マイクロプロセッサに関するものであり、より効率的に命令の処理を行うことにより、マイクロプロセッサの演算性能を改善するものである。具体的には、動的コンパイラを備えるVLIW型マイクロプロセッサにおける命令の処理において、遺伝的アルゴリズム（ＧＡ）を用いることにより、動的コンパイラの実行に伴うオーバーヘッドの低減や、内部命令のスケジューリング後のオブジェクト・コードを格納するためのメモリ容量を抑えることを特徴とする。
【００１６】
従って、本発明の構成は、ハードウェア部分、およびソフトウェア部分を含むマイクロプロセッサにおいて、前記ソフトウェア部分に遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサである。
【００１７】
また、上記構成において、
前記ソフトウェア部分に動的コンパイラを含み、前記動的コンパイラの処理に遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサである。
【００１８】
また、上記構成において、
前記ソフトウェア部分に含まれる動的コンパイラは、命令分岐予測、命令パスの選択、内部命令のスケジューリング、および最適化を含む複数の処理を行い、前記複数の処理のうち少なくとも１つに遺伝的アルゴリズムを用いることを特徴とするマイクロプロセッサである。
【００１９】
なお、上記構成において、
前記ソフトウェア部分に動的コンパイラ、遺伝的アルゴリズムエンジンを備えており、前記遺伝的アルゴリズムエンジンが、前記動的コンパイラの一部に含まれる場合も本発明の構成に含めることとする。
【００２０】
また、前記遺伝的アルゴリズムエンジンは、初期集団を決定する手段と、前記初期集団を評価する手段と、評価対象を評価の適応度に応じて選択する手段と、交叉、突然変異といった遺伝的な操作を行う手段と、再度評価して、前記一連の処理を継続するか否かの評価を行う手段を少なくとも備えたことを特徴とする。
【００２１】
遺伝的アルゴリズム（Genetic Algorithm；GA）とは、生物の進化の過程をまねることでソフトウェアの最適化を図る手法である。考え方としては、遺伝と、自然淘汰を繰り返すことによって、より優秀な遺伝子を導き出そうというものである。遺伝的アルゴリズムは、はじめに異なった遺伝子を持ついくつかの初期集団を用意し、そのなかで、選択（selection）、交叉（crossover）、突然変異（mutation）の３つのプロセスを行う。選択とは、集団の中から優秀なものを選び出すことである。交叉とは、選び出された集団のなかでランダムに遺伝子の一部に交換を行うことである。突然変異とは、低い確率で起こり、遺伝子情報の一部をランダムに書き換えることである。具体的には、以下のような流れになる。
１．もとになるアルゴリズムをいくつか用意する。
２．個体ごとに適応度を計算する。
３．条件に合えば終了。合わなければ４へ進む。
４．優秀な個体の集団の中でランダムに選んだ個体の遺伝子の交叉を行う。
５．突然変異が起きるか判定を行い、それに従って突然変異を行う。
６．２へ戻る。
【００２２】
つまり、初期の集団から自然淘汰と生殖活動を行うことにより、より優秀な遺伝子を持つ個体だけを選び出していくわけである。工学的には最適解をランダムかつ速やかに探索する手法となる。遺伝的アルゴリズムの応用範囲は非常に広く、広い範囲における探索、最適化問題、機械の学習問題など実に多岐にわたる。また、他の様々な手法とも相性もよく組み合わせて使うこともできる。
【発明の効果】
【００２３】
本発明は、ハードウェアとソフトウェアから構成された動的コンパイラを備えるVLIW型マイクロプロセッサにおいて、遺伝的アルゴリズムの手法を用いて、命令分岐予測や内部命令のスケジューリングを含めた最適化を行うことによって、動的コンパイラのオーバーヘッドを低減させる効果がある。また、遺伝的アルゴリズムの学習機能も併用することによって、オーバーヘッドを低減することやキャッシュの内容や容量を最適化することが可能となる。
【発明を実施するための最良の形態】
【００２４】
まず、本発明の動的コンパイラを備えたVLIW型マイクロプロセッサの構成について説明する。図３に本発明のマイクロプロセッサを含む周辺の構成図を示す。
【００２５】
図３（ａ）（ｂ）に示すように、本発明のマイクロプロセッサ３３は、ハードウェア部分（ＰＨＷ）３１とソフトウェア部分（ＰＳＷ）３２からなっており、ハードウェア部分は、VLIWアーキテクチャ構造を有している。ソフトウェア部分に、動的コンパイラ部分を含んでおり、本発明の主要な部分である。ソフトウェア部分の上に、オペレーションシステム（ＯＳ）３４が存在し、その上に一般のアプリケーション（ＡＰ）３５が存在する。場合によっては、図３（ｂ）の様に、直接オペレーションシステムが、ハードウェア部分をアクセスする場合も考えられる。
【００２６】
マイクロプロセッサの基本的な動作は、一般的に、（１）Fetch；命令の読み込み、（２）Decode；命令の解析、（３）Execution；演算実行、（４）Memory；メモリの参照、（５）Write；演算結果の書き込みの５ステージ（段階）に分けられる。しかし、全ての動作が終了するまで次の命令を実行しないというのでは非効率なので、各動作に対して次々に命令を投入することによって、効率をあげることが可能である。これが、図４に示す様なパイプライン方式である。図中で、「Ｆ」は命令の読み込み、「Ｄ」は命令の解析、「Ｅ」は演算実行、「Ｍ」はメモリの参照、「Ｗ」は演算結果の書き込みを意味している。マイクロプロセッサのパイプラインを止めないためには、クロックサイクル毎に１命令をフェッチしなければならない。しかし、このパイプラインの流れを止めてしまう制御ハザードが存在する。その制御ハザードの一つに分岐に起因するものがある。なぜならば、分岐命令が実行される場合、その分岐が成立するか否かは、パイプラインでいうメモリの参照（図５中の「Ｍ」動作）のステージになるまでわからないからである。
【００２７】
図５では、分岐命令があったときのパイプラインの流れを示している。ここでは、３クロックのストール（図中斜線部分がストール）が発生してしまっていることがわかる。ここで、図５の例のように、分岐が完了するまでパイプラインをストールさせては速度が遅くなりすぎるので、予め分岐の結果を予測して、後続命令の実行を継続させる。予測の結果が外れれば、途中まで進めた命令をフラッシュし、命令をフェッチし直さなければならない。こうした制御ハザードのコストを低減させるためには、分岐予測の精度を高める必要があり、動的コンパイラのオーバーヘッド低減に直結する。
【００２８】
また、ほとんどのプログラムでは、オブジェクト・コードを構成する命令のうち実際にマイクロプロセッサで実行する命令はわずかであり、これら実際の命令から成っている命令パスを見つけ出し最適化することが、動的コンパイラのオーバーヘッドの低減につながる。図６に、選択した命令パスの一例を示す。図中のノードにおいて、６１の部分は基本ブロックを、６２の部分は命令分岐を意味している。
【００２９】
動的コンパイラは、上記の分岐予測や命令パスの選択以外に、より広範な命令スケジューリングや最適化を行っている。更には、レジスタの割当やデータアドレスの割り当てなど多くの処理をつかさどっている。
【００３０】
本発明では、遺伝的アルゴリズム（ＧＡ）という手法を用いて、分岐予測や命令スケジューリング等の効率を上げて、動的コンパイルのオーバーヘッドの低減を図る。具体的には、図７に示す様に、マイクロプロセッサのソフトウェア部分の中は構成されている。図７中の７１は、図３中の３２と同じＰＳＷを示しており、７２の動的コンパイラや７４で表現されているそれ以外から構成されているが、遺伝的アルゴリズムのエンジンは、動的コンパイラの外側（図７（ａ））にあっても、内側（図７（ｂ））にあってもよい。
【００３１】
前述したが、遺伝的アルゴリズム（ＧＡ）とは、ある問題に対する最適な解を求めるための手法である。この手法はもともと、John H. Hollandらによって提唱された生物の世界にある遺伝の法則をまねて作られたもので、複数の解を、遺伝的に変化させながら、より良い解を求めていくものである。
【００３２】
ＧＡでは解を遺伝子という形で表現する。これは解の持つ特徴を一定のルールに従って記述したもので、このルールを決めて遺伝子を決定することをコーディングと呼び、抱える問題をどう表現をするかという観点から重要な作業である。 コーディングに誤りがあったり、問題に適していなかったりした場合には、効果のある結果を望めない場合もある。通常、コーディングした遺伝子表現として、バイナリー・コードが使われることも多い。本発明においては、ターゲットなる問題、及び、メモリ低減の要請から、まさに、コーディングされた形態は、バイナリーライクなものが適している。
【００３３】
図８に、基本的なＧＡのフローチャートの例を示す。ただし、これは一例であり必ずしもこの通りである必要はない。フローの最初で、まず、初期集団を用意する。初期集団とは、解の集団、つまり、コーディングされた遺伝子表現の集まりであり、ＧＡではこれを個体群と呼ぶ。初期集団となる個体群は、決まったデータでは無く、ランダムに作り出したものであったり、何らかのデータが用意されている場合もある。ただ、一つ言えることは初期集団には多様性があったほうが良い。つまり、遺伝的操作によって最適解を求めることが目的であるため、なるべくいろいろなパターンを用意すれば、それだけ調べられる可能性も広い、つまり、ローカル解に陥ることが無いというわけである。次に評価を行う。現在の個体群の中に条件を満たす解が含まれているなど、一定の条件を満たしたときに、ＧＡは終了する。終了条件として、解とＧＡの世代（計算回数）を用意しておくと、解の判定用の条件が厳しすぎたときにＧＡが終わらなくなるのを防ぐことが可能である。
【００３４】
選択では、個体群の全ての個体（解）について適合度を求めて、この適合度に基づき次の世代に残す個体を決定する。適合度というのは、解の評価の高さを示すものである。問題によって求め方は変化するが、良い解ほど高い適合度が得られるように評価関数を設定する。また、選択の方法についてもさまざまな手法が存在する。問題によって適したものを選ぶことが望まれる。一般に、解を表現型に直すと評価しやすいと思われる。交叉（crossover）と突然変異（mutation）はＧＡオペレータと呼ばれ、ＧＡを特徴づけるものである。ともに、遺伝の法則をヒントに作られたもので、交叉では複数の親（一般には二つ）から遺伝子を受け継ぐ新しい個体（子）を作ります。突然変異では、低い確率で起き、遺伝子の一部が変化を受ける。
【００３５】
図９に交叉の概念図を示す。一般には、１点交叉を行う場合が多いが、図９（ｂ）の様に、Ｎ点交叉（Ｎは正整数）がありえる。また、図１０に突然変異の例を示す。
【００３６】
ここで、交叉の目的は、両方の親から別々の良い形質を受け継ぐことにより、より良い遺伝子を作り出すことであり、突然変異の目的は遺伝子が局所的な最適解に落ち着いてしまうことを防ぎ、より広い範囲で最適な解を探すことにある。交叉と突然変異を繰り返すだけでは、遺伝子をいろいろ変化させるだけであるが、選択により適合度の低い個体は順次淘汰される仕組みになっているため、結果的には良い方向に変化をした個体が生き残っていくことになる。まさしく、自然界における生き物の進化と同じ様な淘汰が起きているわけである。
【００３７】
前述した遺伝的アルゴリズムを用いて、マイクロプロセッサのソフトウェア部分ＰＳＷにおける動的コンパイラのオーバーヘッドを低減する仕組みとしては、図７の様な構成を示したが、ソース・コードが実行ユニットへオブジェクト・コード変換される具体的なフローとしては、図１１の様になる。図中１１１と１１２は、オブジェクト・コードを生成するが、本発明で特に重要なのは１１２の方で、最適化されたオブジェクト・コードを実行状況をフィードバックしながら生成する。この場合に遺伝的アルゴリズムが用いられるが、そのエンジンは、動的コンパイラ内に存在しても良いし、図中の１１３の様に外側にあって、サポート機能として扱われても良い。
【００３８】
ここで、遺伝的アルゴリズムを用いて最適化を行う以外に、重要な機能を付加することも可能である。遺伝的アルゴリズムは、学習機能も有することが可能であり。この機能を利用することによって、個々のユーザーに適合した、または、個々の時期に適合した命令パスの選択や命令スケジューリングを行う学習機能を付加することも可能となる。
【００３９】
これらの機能は、図１２で示される様な、変換後のオブジェクト・コードをキャッシュに置く機能を有する場合にも適用することが可能である。変換後のオブジェクト・コードをキャッシュに置く基準や消し去る基準を決める手法として、遺伝的アルゴリズムを用いるわけである。更には、キャッシュの容量がアプリケーションによってことなる場合に遺伝的アルゴリズムを用いることによって最適な基準を選択することが可能となる。図１２の様なキャッシュ機能は、オーバーヘッド低減には非常に有効な機能であり、マイクロプロセッサの性能を格段に向上させる。
【実施例１】
【００４０】
本実施例では、本発明の図７や図１１の遺伝的アルゴリズムエンジン（ＧＡＥ）について説明する。
【００４１】
図７は、本発明のマイクロプロセッサのソフトウェア部分について示してある。図７中の７１は、図３中の３２と同じＰＳＷを示しており、７２の動的コンパイラや７４で表現されているそれ以外から構成されているが、遺伝的アルゴリズムエンジン７３は、動的コンパイラ７２の外側（図７（ａ）にあっても、内側（図７（ｂ））にあってもよい。また、図１１は、ソース・コードが実行ユニットへオブジェクト・コード変換される具体的な動的コンパイラと遺伝的アルゴリズムエンジンの関係を示している。遺伝的アルゴリズムエンジンのフローチャートは、代表的には、図８の様に示される。但し、遺伝的アルゴリズムは、図８がもっとも単純なアルゴリズムではあるが、多少アレンジすることによって、最適解の得られるまでの収束時間や正当性を高めている。
【００４２】
図８のフローについて、命令スケジューリングを行う場合を例として述べる。まず、初期集団を決める必要がある。いわゆるコーディングの作業である。命令列をプログラム内での処理に適した形に変換して、これをもとに遺伝的表現を生成する。遺伝的表現として決めた命令列を実際に実行して、その時間を評価対象とすることとした。選択で、評価した命令列の適応度に応じて優先順位を決める。交叉、突然変異といった遺伝的なオペレートを行った後に、再度実行時間を評価して、新しい命令列に世代交代させる。世代交代では古い世代でも実行時間の短いものだけは次世代にも継続して残し、それ以外はすべて新世代の個体に置き換えることとする。この後に、再びこの新世代の命令列に対して選択と遺伝的なオペレートを施す。この遺伝的なオペレートは、収束条件を満たすまで繰り返し行う。収束条件としては、あらかじめ実行時間を設定しておく場合、或いは、世代交代数を設定しておく場合がある。収束条件を満たした後に、これによって生成された命令列群中の中から実行時間のもっとも短いものを目的とする命令列とする。ここでの、フローは、最も単純な場合なので、必ずしもこの様なフローである必要はない。
【実施例２】
【００４３】
遺伝的アルゴリズムを用いた動的コンパイルを備えたマイクロプロセッサは、低消費電力化にも適しているため、パーソナルコンピュータをはじめとして、様々な携帯電子機器に用いることができる。
【００４４】
本発明のマイクロプロセッサを用いた電子機器として、ビデオカメラ、デジタルカメラ、ゴーグル型ディスプレイ（ヘッドマウントディスプレイ）、ナビゲーションシステム、音響再生装置（カーオーディオ、オーディオコンポ等）、ノート型パーソナルコンピュータ、ゲーム機器、携帯情報端末（モバイルコンピュータ、携帯電話、携帯型ゲーム機または電子書籍等）、記録媒体を備えた画像再生装置（具体的にはＤＶＤ：Digital Versatile Disc）等の記録媒体を再生し、その画像を表示しうるディスプレイを備えた装置などが挙げられる。特に、携帯情報端末は、個々のユーザーによって使い勝手が決まってくるので、個々のユーザーに合わせて進化する動的コンパイラの仕組みは、重要視される。それら電子機器の具体例を図１３に示す。
【００４５】
図１３（Ａ）は携帯情報端末であり、本体３００１、表示部３００２、操作キー３００３、モデム３００４等を含む。図１３（Ａ）ではモデム３００４が取り外し可能な形態の携帯情報端末を示しているが、モデムが本体３００１に内蔵されていても良い。本発明のマイクロプロセッサは、本体内部に構成部品として用いることができる。
【００４６】
図１３（Ｂ）は携帯電話であり、本体３１０１、表示部３１０２、音声入力部３１０３、音声出力部３１０４、操作キー３１０５、外部接続ポート３１０６、アンテナ３１０７等を含む。なお、表示部３１０２は黒色の背景に白色の文字を表示することで携帯電話の消費電流を抑えることができる。本発明のマイクロプロセッサは、本体内部に構成部品として用いることができる。
【００４７】
図１３（Ｃ）は電子カードであり、本体３２０１、表示部３２０２、接続端子３２０３等を含む。本発明のプロセッサは、本体内部に構成部品として用いることができる。なお図１３（Ｃ）では接触型の電子カードを示しているが、非接触型の電子カードや、接触型と非接触型の機能を持ち合わせた電子カードにも、本発明のマイクロプロセッサを用いることができる。
【００４８】
図１３（Ｄ）は電子ブックであり、本体３３０１、表示部３３０２、操作キー３３０３等を含む。またモデムが本体３３０１に内蔵されていても良い。本発明のマイクロプロセッサは、本体内部に構成部品として用いることができる。
【００４９】
図１３（Ｅ）はシート型のパーソナルコンピュータであり、本体３４０１、表示部３４０２、キーボード３４０３、タッチパッド３４０４、外部接続ポート３４０５、電源プラグ３４０６等を含む。本発明のマイクロプロセッサは、本体内部に構成部品として用いることができる。
【００５０】
以上の様に、本発明の適用範囲は極めて広く、あらゆる分野の電子機器に用いることが可能である。
【図面の簡単な説明】
【００５１】
【図１】スーパースカラー型と動的コンパイラを備えたVLIW型マイクロプロセッサに関するハードウェア構成の比較。
【図２】スーパースカラー型と動的コンパイラを備えたVLIW型マイクロプロセッサに関する命令スケジューリングの比較。
【図３】動的コンパイラを備えたVLIW型マイクロプロセッサ、及び、その周辺の構成図。
【図４】パイプライン方式を示す概念図。
【図５】分岐命令を有する場合のパイプライン方式の流れを示す概念図。
【図６】プログラム中の命令パスの選択例を示す図。
【図７】プロセッサのソフトウェア部分の構成を示す図。
【図８】基本的な遺伝的アルゴリズムのフローチャート図。
【図９】遺伝的アルゴリズムの交叉の例を示す図。
【図１０】遺伝的アルゴリズムの突然変異の例を示す図。
【図１１】ソース・コードが実行ユニットへオブジェクト・コード変換されるフローチャート。
【図１２】変換後のオブジェクト・コードのキャッシュ格納に関するフローチャート。
【図１３】本発明のマイクロプロセッサを用いた電子機器の図。
【図１】
2005032018.tif 000003
【図２】
2005032018.tif 000004
【図３】
2005032018.tif 000005
【図４】
2005032018.tif 000006
【図５】
2005032018.tif 000007
【図６】
2005032018.tif 000008
【図７】
2005032018.tif 000009
【図８】
2005032018.tif 000010
【図９】
2005032018.tif 000011
【図１０】
2005032018.tif 000012
【図１１】
2005032018.tif 000013
【図１２】
2005032018.tif 000014
【図１３】
2005032018.tif 000015