(57)【要約】ハードウェア上の完全進化アルゴリズムを実行するために構成されている、コンフィギュラブルハードウェアロジックデバイスであって、前記コンフィギュラブルハードウェアロジックデバイスは、個体の初期集団を作成する集団作成手段と、個体の初期集団に関する適合テストを実行する適応度評価手段と、適応度テストの結果に基づく初期集団に対して単一個体と複数個体を選択するセレクター手段と、選択された単一個体または複数個体から個体のさらなる集団を作り出す増殖手段と、（f） 個体のさらなる集団から単一の優先選択された個体を供給するためにさらなる調整を行う適応度評価手段とを備えている、上記手段の動作を実行する方法である。
2004533672.tif 000002
【特許請求の範囲】
【請求項１】
完全進化アルゴリズムを実装するために設定される際の汎用コンフィギュラブルハードウェアロジックデバイスであって、前記設定されたハードウェアロジックデバイスは、
（ａ）出力を備えている、前記出力で個体の初期集団を生成するために配置されている集団生成手段と、
（ｂ）入力と第一の出力と第二の出力とを備えている適応度評価手段であって、
前記適応度評価手段の前記入力に連結されている前記集団生成手段の前記出力と、
前記個体の初期集団に関する適応度テストを実行すること、及び前記適応度テストの結果と前記適応度評価手段の前記第一の出力における各々の個体とを提供することのために配置されている前記適応度評価手段と、
（ｃ）入力と出力とを備えている、適応度テストの結果に基づいた初期集団の単一個体と複数個体とを選択するために配置されているセレクター手段であって、
各々の個体が、前記適応度評価手段の前記出力から前記セレクター手段の前記入力へ連結されており、前記セレクター手段の前記出力で選択された単一個体または複数個体を提供するために配置されている前記セレクター手段と、
（ｄ）前記セレクター手段の前記出力へ連結されている入力を備えており、
選択された単一個体または複数個体からさらなる複数個体の集団を増殖するために配置されている増殖手段であって、
前記適応度評価手段の前記入力に対して、さらなる複数個体の集団を連結している出力を備えている前記増殖手段と、
（ｅ）前記第二の出力そのものにおけるさらなる複数個体の集団から単一の好ましい選択された個体を提供するために、さらに配置されている前記適応度評価手段とを備えている前記コンフィギュラブルハードウェアロジックデバイス。
【請求項２】
請求項１のように設定される時、その中で、進化アルゴリズムが遺伝的プログラミングである汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項３】
請求項１または２で請求したように設定される時、その中で、前記汎用コンフィギュラブルハードウェアロジックデバイスが、フィールドプログラマブルゲートアレイ（FPGA）である汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項４】
請求項１または２または３で請求したように設定される時、複数の並列ステップにおいて、選択された１つのステップまたは複数ステップを実行するために設定されている汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項５】
請求項１から４のいずれか１つの請求項で請求したように設定される時、その中で、前記設定がハードウェアコンパイルシステムに対してハイレベルな言語の手段によるものである汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項６】
請求項５で請求したように設定される時、その中で、ハードウェアコンパイルシステムに対するハイレベル言語がHandel-Cである汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項７】
先のいずれか１つの請求項で請求したように設定される時、その中で、前記汎用コンフィギュラブルハードウェアロジックデバイスが、変更可能である汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項８】
先のいずれか１つの請求項で請求したように設定される時、その中で、前記汎用コンフィギュラブルハードウェアロジックデバイスが、ランダムアクセスメモリを含んでいるか、あるいはそれに対して接続されている汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項９】
先のいずれか１つの請求項で請求したように設定される時、その中で、前記汎用コンフィギュラブルハードウェアロジックデバイスが、ランダムナンバージェネレータとして設定された部分を含んでいる汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項１０】
スカラーデータに関して動作するように設定される時、先のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項１１】
ベクトルデータに関して動作するように設定される時、請求項１から９のいずれかの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項１２】
サブマシンコードに関して動作するように設定される時、請求項１から９のいずれかの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイス。
【請求項１３】
（ａ）個体の初期集団を創造すること
（ｂ）前記個体の初期集団の適応度を評価すること
（ｃ）前記初期集団そのものから一つあるいは二つ以上の個体を選択すること
（ｄ）選択された一つまたは二つ以上の個体からさらなる個体の集団を増殖させること
（ｅ）前記さらなる個体の集団の適応度を評価すること
（ｆ）前記さらなる個体の集団の適応度に基づいたさらなる個体の集団の好ましい一つを選択すること
のステップを実行するために汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項１４】
請求項１３で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、前記進化アルゴリズムが遺伝的プログラミングである完全進化アルゴリズムを実装する方法。
【請求項１５】
請求項１３または１４で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、前記汎用ハードウェアロジックデバイスがフィールドプログラマブルゲートアレイ（FPGA）であるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項１６】
汎用ハードウェアロジックデバイスを含んでいる請求項１３または１４または１５で請求したようなハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、選択された１つのステップまたは複数ステップ各々が複数の並列ステップで実行されているハードウェアで完全進化アルゴリズムを実装する方法。
【請求項１７】
請求項１３または１４または１５または１６で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、前記設定がハードウェアコンパイルシステムに対してハイレベル言語の利用によるものであるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項１８】
請求項１７で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、ハードウェアコンパイルシステムに対するハイレベル言語がHandel-Cであるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項１９】
請求項１３から１８のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、前記汎用コンフィギュラブルハードウェアロジックデバイスが変更可能であるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項２０】
請求項１３から１９のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、その中で、データがランダムアクセスメモリに蓄積されるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項２１】
請求項１３から２０のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、ランダムナンバージェネレータを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法。
【請求項２２】
請求項１３から２１のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、スカラーデータについて動作するハードウェアで完全進化アルゴリズムを実装する方法。
【請求項２３】
請求項１３から２１のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、ベクトルデータについて動作するハードウェアで完全進化アルゴリズムを実装する方法。
【請求項２４】
請求項１３から２１のいずれか１つの請求項で請求したような汎用コンフィギュラブルハードウェアロジックデバイスを設定することを含んでいるハードウェアで完全進化アルゴリズムを実装する方法であって、サブマシンコードについて動作するハードウェアで完全進化アルゴリズムを実装する方法。
【発明の詳細な説明】
【背景技術】
【０００１】
遺伝的プログラミング (GP)は、通常、一般目的のコンピュータで動作するプログラムとして実現されている。本研究は、問題がますます難しいものとなってきているために、従来のコンピュータのパフォーマンスが、激しく拡大されているということに注目したことが動機となった。この状況は、最新CPUのパフォーマンスが向上し続け、そしてGPを並列処理できるという事実を活かすマルチプロセッサーを利用していることにかかわらず継続している。目的は、ハードウェアで直接的にGPシステムを実装することによって、パフォーマンスを向上することであり、これは、より困難な問題に取り組めるようにするには十分に大きな要素である。
【０００２】
本発明は、GPシステムがハードウェアコンパイル技術を用いているハードウェアでどのように実装されるかを示す。まず初めに、ハードウェアの記述とハードウェアコンパイル言語がある。これは、一般に、GPシステムの記述とデザイン決定の審議を経て進められ、前記デザインは、首尾よくGPシステムをフィールドプログラマブルゲートアレイ (FPGA)に適合するために作られなければならない。これは、いくつかの例題を選択し、実装することを経て進められる。システムを動作した結果と従来の実装との比較を以下に示して行く。
【０００３】
以下の節では、一般のFPGAについて簡単に述べる。次に、ハードウェアコンパイルシステムに対するハイレベル言語を説明する。これは、ツールの完全な説明を意図しているものではなく、もっとも重要な特徴を述べるものであり、特に、後述されるデザイン決定に影響を与える部分について述べるものである。
【０００４】
ここでの概論は、FPGAについての経験がほとんど無いか、または未経験の方にとってより容易に理解できるように、以下のいくつかの議論をすることを意図されている。より包括的なデータは、さまざまな製造業者のウェブサイトで示されている。
【０００５】
FPGAは、プログラマブルなハードウェアデバイスの部類であり、コンフィギュラブルロジックブロック(CLBs)とコンフィギュラブルな接続から成る。一般的なモデルを図１に示す。
【０００６】
各々のCLBは、二つのファンクションジェネレータ(F & G)と、二つのフリップフロップ(FF)から成る。内部キャリーとコントロールロジック(H)は、前記ファンクションジェネレータと前記フリップフロップに接続されている。CLBの一般的なモデルを図２に示す。
【０００７】
これらのデバイスの構成は、構成ビットパターンをロードすることによって達せられる。Xlinx XCV4000 FPGAは、この中に用いられる一例のデバイスであるが、このデバイス上におけるビットパターンは、チップ上でスタティックRAMの中にプログラムされる。これは、チップが電源を投入される度に、行われなければならない。前記構成ビットパターンは、構成情報のハイレベルな記述を取るソフトウェアツールを用いて発生させられる。
【０００８】
Handel-Cは、ハードウェア翻訳システムに対するハイレベルな言語であり、同期式のハードウェアに対してCライク言語で書かれたプログラムをコンパイルして設計される。Handel-Cからの出力は、FPGAのための構成データを作るのに用いられるファイルである。Handel-Cは、Celoxica社によって作成されている[www.celoxica.com]。
【０００９】
Handel-Cは、Cライクな構文法を備えている。これにより、ハードウェアの未経験者であるソフトウェアエンジニアにそのツールがうけており、前記Handel-Cは、FPGAについて、詳細には、VHDLを学ばなければならないということは無く、ハードウェアに向けてソフトウェアアルゴリズムを素早く翻訳することが可能である。VHDLは、標準ハードウェア設計言語である。VHDLは、VHSICハードウェア設計言語である。VHSICそれ自体は、Very High Speed Integrated Circuitのことである。
【００１０】
ハードウェアを用いることの優位性の一つとして、直接的に、並列に利用することができることが挙げられる。これは、タイムスライシングを使って達成されるシングルCPUコンピュータ上で見出されるシミュレートしたソフトウェア並列と対照になるものである。Handel-Cは、並列コードをサポートする付加的な構成を備えている。
そのブロックは、
2004533672.tif 000003
シングルクロックのサイクルでａに対して値１０を、ｂに対して値２０を指定するハードウェアを発生させる。ファンクションの並列を利用すること、あるいは、直列形のコードを発生させることにより、並列で実行する大きなブロックの機能性が発生し得る。
【００１１】
ハードウェアは、その構成を利用して繰り返すことが可能である。
2004533672.tif 000004
上記構成は、結果として、１０個の並列指定動作をする。
【００１２】
ハードウェアの効果的な利用をするためには、Handel-Cは、全てのデータ幅を宣言するプログラマを必要とする。例えば、
int 5 count;
これは、５ビット幅である符号付き整数であり、−１５と１５の間の値を表現することができる。
【００１３】
Handel-Cは、単一の整数データ型をサポートしている。
【００１４】
ハードウェアと外部の世界との通信は、インターフェースを用いて実行される。これらは、入力または出力、そして、インターフェースからの読み出し、または、インターフェースへの書き込みが、１クロックのサイクルに指定される仕様となることもあり得る。前記言語によって、設計者は、特定のハードウェアを目標にすること、入出力ピンを指定すること、信号のタイミングを指定すること、一般的に、詳細を連結しているローレベルのハードウェアをコントロールすることを許される。マクロは、目標となる特定デバイスの手助けとして利用できる。
【００１５】
Handel-Cの文書によると、ステートメントのタイミングについての単純な命令は、“代入は１クロックのサイクルがかかり、残りはかからない”ということがある。これは、表現が組合せ論理を用いて構成されていることを意味し、データは、代入が実行された時のみ、クロック動作となる。例えば、Handel-Cは、単一クロックのサイクルで実行される以下のステートメントに対してハードウェアを発生させる。
Y=((x*x)+3*x);
この特徴は、クロックサイクルに関してパフォーマンスを予測し易くする。しかしながら、表現を複雑にすればするほど、ロジックが表現をより深く実装する必要があることが不利な点である。これは、次に、深いロジックに協働する伝播遅延のためにデザインが動作できる最大クロック速度を制限する。実際上は、これは、設計者がクロック速度に対してクロックのサイクルをトレードする必要があることを意味しており、典型的には、反復処理のことである。
【００１６】
なぜならば、Handel-Cは、ハードウェアをターゲットとしており、伝統的なANSI-Cコンパイラと比較すると、いくつかのプログラミング上の制約がある。これらは、Handel-Cでコンパイルされるコードを設計する時、考慮しなければならない。特に、これらの制約な中には、GPシステムの構築に影響を及ぼすものもある。
【００１７】
第一に、スタックが利用できないため、そのため、再帰的ファンクションは直接的に言語によってサポートされない。これは、次の多量に再帰を当てにしている標準GPは、いくつかの変更無しでは、実装され得ないことを意味する。第二に、FPGAの標準ロジックセルを用いて実装されるメモリサイズには制限があるが、これは、メモリの実装は、シリコンの実際の情況の点からみると高価であるためである。しかしながら、いくつかのFPGAは、Handel-Cによって利用される内部RAMを備えている。例えば、Xilinx Virtex and Spartan seriesは、Handel-Cによって、ユーザがRAMまたはROMとして宣言することを許す内部メモリをサポートしている。例えば、定義である、
ram int 8 mem[128];
は、通常の配列としてアクセス可能な１２８のセル、各８ビット幅のRAMブロックを宣言する。
【００１８】
RAMまたはROMの利用の制限が、１クロックのサイクルに２回以上アクセスされないということであるので、それにアクセスするコードの並列実効の可能性を制限される。
【００１９】
第三に、表現は、副作用を持つことを許されない。単一サイクルの指定の命令を壊すことになるからである。それゆえ、次のようなコード、
a=++b;
は、許可されず、次のように書き直される必要がある。
b=b+1;
a=b;
Handel-Cは、二つの目的をサポートしている。一つ目は、ハードウェアを使うことなくコードの開発とテストが行えるシミュレータの目的である。これは、デバッガと他のツールによってサポートされる。二番目の目的は、プレイスアンドルートツールに対する入力するためのネットリストの合成である。ネットリストは、ゲートとその接続の公式記述である。プレイスアンドルートは、ハードウェアのレイアウトへネットリストを翻訳するという処理である。これは、そのデザインが、特定のチップ用の構成データへ翻訳されることを許す。処理の概観を図４に示す。サイクル数の分析は、シミュレータから利用でき、ゲート数の見積もりは、Handel-Cコンパイラによって発生させられる。最終的なタイミング情報と実際のハードウェア使用法を得るためには、プレイスアンドルートツールを起動させる必要がある。
【００２０】
【非特許文献１】
FPGAはGPシステムの一部を実行するのに用いられてきている。“FPGAコンピューティングプラットフォーム上におけるレジスタに基づいたGenetic Programming”(M I Heywood and A N Zincir-Heywood; Genetic Programming, Proceeding of Euro GP 2000 Volume 1802 0f LNCS, pages 44-59, Edinburgh 15-16 April 2000; Springer-Verlag)に記述されているシステムは、より伝統的なFPGAツールを用いてシミュレートされている。その研究における提案は、個体の評価及び、変種と交差の実行のためにのみFPGAを用いることであった。
【非特許文献２】
Koza et alは、ネットワークのソート“Evolving sorting netwaoks using genetic programming and the rapidly configurable Xilinx 6216 field-programmable gate array”(John R Koza et al; Proceedings of the 31st Asilomar Conference on Signals, Systems and Computers; IEEE Press, 1997)の適応度評価のスピードを向上するためにFPGAを用いた。この研究において、前記FPGAは、単に、適応度評価の実行に用いられた。最初の集団は、ホストコンピュータによって作られ、それから、個体は前記FPGAへダウンロードされ、前記FPGAは、個体の適応度を評価するように指令を受けていた。その後の選択及び増殖は、再度、ホストコンピュータによって、実行されていた。
【００２１】
次節では、ハードウェアでGPを実装するために取られている一般的なデザインの決定について述べる。
【発明の開示】
【発明が解決しようとする課題】
【００２２】
目的は、ハードウェア上で完全GPシステムを実現することである。それは、最初の個体発生、適応度評価、増殖、及び最終結果の配信である。これは、遺伝的プログラミングでFPGAを利用している他の例全てと対照的である。このハイレベルな目的が、後に続く多くのデザイン決定を導いた。
【００２３】
Handel-Cを利用すると、ビルトインスタックの欠乏により、再帰的ファンクションの使用が困難になる。アルゴリズムから再帰を取り除くよく知られている方法があるが、それでも、いくつかのフォームのスタックが、中間結果を蓄積するのに必要とされる。内部の表現の詳細は、ワードサイズ、ファンクションの数、及び用いられるターミナルの数次第であり、これらは、取り組まれている問題次第である。本研究では、レジスタマシンが、その簡単のために選択させる。命令の一般的なレイアウトを表１に示す。各プログラムは、いくつかのコントロール情報を含んでいる命令の配列である。プログラムの操作を単純化するために、各プログラムは、固定された最大サイズであり、それに対して蓄積された最大の実行中の長さを備えている。プログラムの表現は、表２に示されている。
【００２４】
表１：命令の一般的なレイアウト
2004533672.tif 000005
【００２５】
表２：個体の一般的なレイアウト
2004533672.tif 000006
【課題を解決するための手段】
【００２６】
本発明によると、完全進化アルゴリズムを実装するために設定される際の汎用コンフィギュラブルハードウェアロジックデバイスであって、前記設定されたハードウェアロジックデバイスは、
（ａ）出力を備えている、前記出力で個体の初期集団を生成するために配置されている集団生成手段と、
（ｂ）入力と第一の出力と第二の出力とを備えている適応度評価手段であって、
前記適応度評価手段の前記入力に連結されている前記集団生成手段の前記出力と、
前記個体の初期集団に関する適応度テストを実行すること、及び前記適応度テストの結果と前記適応度評価手段の前記第一の出力における各々の個体とを提供することのために配置されている前記適応度評価手段と、
（ｃ）入力と出力とを備えている、適応度テストの結果に基づいた初期集団の単一個体と複数個体とを選択するために配置されているセレクター手段であって、
各々の個体が、前記適応度評価手段の前記出力から前記セレクター手段の前記入力へ連結されており、前記セレクター手段の前記出力で選択された単一個体または複数個体を提供するために配置されている前記セレクター手段と、
（ｄ）前記セレクター手段の前記出力へ連結されている入力を備えており、
選択された単一個体または複数個体からさらなる複数個体の集団を増殖するために配置されている増殖手段であって、
前記適応度評価手段の前記入力に対して、さらなる複数個体の集団を連結している出力を備えている前記増殖手段と、
前記第二の出力そのものにおけるさらなる複数個体の集団から単一の好ましい選択された個体を提供するために、さらに配置されている前記適応度評価手段とを備えている前記コンフィギュラブルハードウェアロジックデバイスを提供する。
【００２７】
さらに、ハードウェアで完全進化アルゴリズムを実装する方法が提供されており、
（ｅ）個体の初期集団を創造すること
（ｆ）前記個体の初期集団の適応度を評価すること
（ｇ）前記初期集団そのものから一つあるいは二以上の個体を選択すること
（ｈ）選択された一つまたは二つ以上の個体からさらなる個体の集団を増殖させること
（ｉ）前記個体の集団の適応度を評価すること
（ｊ）前記個体の集団の適応度に基づいたさらなる固体の集団の好ましい一つを選択すること
以上のステップを実行するために、ハードウェアは、汎用コンフィギュラブルハードウェアロジックデバイスを設定している。
【００２８】
今、本発明について、添付図を参照し、具体例を使って述べる。
図１は、FPGAの一般的なモデルを示す。
図２は、CLBの一般的なモデルを示す。
図３は、線形フィードバックシフトレジスタランダムナンバージェネレータ（Linear Feedback Shift Register Random Number Generator）の一覧図を示す。
図４は、ハードウェアへコードを翻訳する処理の概観を示す。
図５は、集団に対する一つの適応度ファンクション評価を実行するサイクル数を説明する。
図６は、問題に対する全サイクル数を説明する。
図７は、並列適応度評価の数の増加に対して見積られたNANDゲート数を説明する。
【００２９】
本研究と他の研究との違いの鍵となるのは、マイクロプロセッサーの設計者が実装するために適合を判断するというファンクション設定を強いられないことである。すなわち、ファンクションは、機械命令よりも高いレベルの抽象概念を持って設定することができる。問題例としては、前記ファンクションの設定が、高いレベルの抽象概念で表現されている所では、ファンクションと端末設定を実行するために数ステップが必要となるということである。RISCまたはCISCアーキテクチャを利用して実装する場合ならば、各ステップは、実行するのにいくつかのRISC命令を必要とするだろう。Handel-Cがあれば、前記ファンクションは、効果的に簡潔にエンコードされ得る。
【００３０】
ハードウェアについて鍵となる優位性の一つは、忠実に並列機構を設計することが可能であるということである。利用可能なシリコンをもっとも効果的に利用するためには、どの部分に並列を作るかということの選択に対して、いくつかの注意を要する。GPの三つの主要な段階は、初期集団の創造、全個体の適応度評価、及び新世代の増殖である。第一段は、一度だけの実行であるため、この段階の速度を上げるのに過度のシリコンリソースを消費することはほとんど優位性をもたらさない。適応度評価は、リソースを処理する点でもっとも高価であるとして例証されているので、これは、並列段階を作成するための第一候補である。増殖段階は、一般的に、重要度としては適応度評価以下であるが、重大な個所にこの並列を作成することだけで、多少の優位性があるだろう。
【発明を実施するための最良の形態】
【００３１】
本研究で用いられるデザインは、可能な所で簡単な全てのステートメントの並列実行が活かされている。これは、並列に二つの代入の実行は、損失が生じないので、GPの段階に関わり無く並列となっている。つまり、ハードウェアでは、各代入が離れて発生させられることになる。これは、ファンクションの始まりで、変数を初期化する時にとりわけ有用である。
【００３２】
適応度評価段階は、同時に多くの評価を実行することによる並列可能性を活かしている。問題が、全集団サイズPを持つならば、その時、サイズの部分集団S=P/nの個体は並列で評価される。これを出来る限り効果的なものにするためには、また、ハードウェアを最大限利用するためには、全パラメータ設定は、2の累乗である。P=16、n=4、その時、S=4である。評価の並列化は、Handel-Cの直列形のキーワードによって実装される。これにより、必要に応じて、ハードウェアの多くのコピーが発生させられることになる。
【００３３】
ランダムナンバージェネレータ（RNG）は、GPにおいて大きなステップの内の２個所で利用されている。第一に、初期集団の創造中、第二に、増殖段階中である。Handel-Cを用いる時、標準乗算機と除算命令の使用が、深いロジックを発生させるためにシリコンの関係で不十分である。通常の線形コングルエンシャルジェネレータは、一般的に、これが見受けられるという理由で、拒絶された。代わりに、線形フィードバックシフトレジスタ（LFSR）デザインが利用された。６４というワードサイズが選択されたが、これは標準的な最新CPUに関して効果的に実装することができるためであり、LFSRが、ANSI-Cに対して容易にポートされ得るからである。タップ数が効果的に最小限に保たれている間は、RNGが最も効果的な連続2n-1のランダム数を発生できることを確かめるために有効な多項式を選択することが重要である。６４ビットのワードでは、多項式x64+x4+x3+x2+x1+x0が、用いられる（図３は多項式からの４項を示す；６４ビットのワードから５項；x0は、常に１なので無視される）。LFSRのブロック図を図３に示す。
【００３４】
前記RNGは、ランダムナンバーが１サイクルで発生するように設計されている。必要とされるビットナンバーが、ランダムナンバーを与えるビット１で始まり、６４ビットレジスタから読み出される。例えば、システムが８命令を持っているとすると、命令を符号化するのに３ビットが必要とされる。初期プログラム作成中、ランダムな命令選択は、下位３ビットを用いる。Handel-Cによって十分なビット動作が許されると、３ビットを選択するコードは、以下の通りである。
unsigned int 3 instruction;
instruction = randReg[2:0];
ここで、randRegは、シフトレジスタ変数である。
【００３５】
RNGのシーディングは、初期段階で６４ビットのポートを読み出すことによって行われる。これは、RNGがデイクロックの時間あるいはノイズ源のような外部ソースからシードされるのを許す。それは、特別な結果を再生するためにRNGが既知のシードに対して前もってセットされることを許す。
【００３６】
ジェネレータの現在の実装の制限は、並列実行ブロックが、ランダムナンバーを発生させることを許可するのは不可能であるということである。なぜならば、これは、ファンクションの単一のインスタンスが並列ブロックから呼び出されないということを言及しているHandel-Cの状況を乱すことがあるからである。これは、初期プログラムの発生と増殖段階が、並列化し得ないということを意味する。これは、重複したジェネレータを実装することによって完成される間に、適応度評価段階へリソースを専用させることがより重要であると考えられる。
【００３７】
メモリを節約して使うために、着実な状態である増殖手段が利用される。集団のサイズPにとっては、あらゆる世代Pの集団がランダムに選択され、動作が個体に適用される。もし、前記動作が交差やコピーであるならば、これは、二つの個体が処理されたとしてカウントされる。トーナメント選択方式が二つのトーナメントサイズで用いられる。より大きいトーナメント選択方式は、とても小さな集団ではほとんど意味をなさない。
【００３８】
前記動作は、次の確率を用いて選択された。突然変異10％、交差70％、コピー20％。
【００３９】
突然変異動作は、初期プログラム作成中、プログラムノードを発生させるファンクションを再利用することによって働く。これは、第一に、ハードウェアを節約することを行う。その結果は、突然変異が０、１、またはそれ以上の命令の詳細を変化させるということである。
【００４０】
線形プログラムで表現する交差は、大きなブロックメモリ転送を実行することを避けたいという点で、いくつかの問題を引き起こす。本研究は、固定された最大プログラムサイズを維持し、一つのプログラムから他へセグメントをコピーする。ハードウェアの並列性質を活かすことによって、ブロックメモリコピーを実行する影響が許容できるレベルを引き下げられる。
【００４１】
再度、ハードウェアの並列性質を活かすことによって、長さｌの個体のコピーはｌ＋ｋクロックのサイクルを必要とする。ここで、ｋはコピーを設定するための小さな付加部分を表す。
【実施例１】
【００４２】
次の節では、Handel-Cを用いているGPの実装をテストするために選択された問題と実験で用いられる環境について述べる。
【００４３】
実験を行う目的は４つある。
１．限定されたGPシステムが、選択された問題を解くことができるかどうかを決定すること。
２．Handel-Cを用いてシステムが実装されるかを決定すること、及びデザインがFPGAに関して適合していることを検証すること。
３．伝統的なＣでの実装とハードウェアでの実装との間でいくつか示すパフォーマンスの比較を得ること。
４．ハードウェアとしてデザインが実現可能かどうかを決定すること、及びハードウェアでデザインを実装すること。
【００４４】
二つの問題は、Handel-Cを用いているハードウェア上のGPの一般的な概念を実証している。選択された二つの問題は、回帰問題とブール論理問題であった。選択された問題は、x = a+2bである。ブール論理問題は、２ビットXORファンクション、
2004533672.tif 000007
である。
【００４５】
両方の問題で、原適応度は、100％正確なプログラムでゼロであるように調整されており、それくらい、ロジック量の削減することが適応度テストを行うためには必要とされた。
【００４６】
両方の問題で、100％正確なプログラムであると見受けられて、世代の最大数が評価されるならば、動作は終了した。
【００４７】
上記目的を満たすために、前記問題は、五つの異なる環境を用いて動作させた。第一に、標準ＣアプリケーションとしてLinux下で動作する。これは、初期プログラム動作を証明することであり、前記アプリケーションが標準GNUツールを用いてデバッグすることを可能にした。前記プログラムは、gcc v2.95.2を用いてコンパイルし、200MHz AMD K6 PCでLinuxを動作させて実行した。
【００４８】
第二に、前記プログラムは、Handel-Cを用いてコンパイルした。ロジックの深さとゲート数とを限定するために、そして並列化を増大させるために、最適化がコードに対して行った。
【００４９】
第三に、Handel-Cの実装は、Handel-Cシミュレータを用いて行った。これは、前記プログラムを実行するために必要とされるクロックのサイクル数を与えた。
【００５０】
第四に、前記Cのコードは、クロスコンパイラを用いてコンパイルし、Motorola Power-PCアーキテクチャのための命令シミュレータで実行した。これは、最新プロセッサで必要とされる命令とメモリのサイクル数を得るために行った。本研究でのPowerPCの選択は、PowerPCのためのシミュレータが難なく利用できるということを基本とした。Power-PCシミュレーションは、慣行上"eabi"と呼んでいるものを使ってPower-PCクロスコンパイラとして構成されるgcc 2.95.2を用いることによって実行した。スタートアップオーバーヘッドを最小にするために、また任意のI/Oを利用しないようにするために、前記プログラムのバージョンを最適化した。それゆえ、パフォーマンスの意味のある比較が可能となり、可能な限りFPGAプログラムに近づく。前記シミュレータそれ自体は、GNUデバッガ（gdb）の中へ組み込まれているpsimを使った。psimはまた、スタンドアロンのアプリケーションとして動作可能である。
【００５１】
最後に、Handel-Cからの出力は、デザインが実行される最大クロック周波数を与えるプレイスアンドルートツールに対するハードウェアレイアウトと必要とされるFPGAのリソースの指示とを発生するのに用いられる。
【００５２】
Handel-Cシミュレーションとハードウェア実装のために、最大最適化を利用しているHandel-C v3.0を用いて、前記コードをコンパイルした。最終FPGA構成データは、Celoxica RC1000開発ボード上に集結されたXlinx Design Manager version 3.1i for a Xlinx Virtex XCV1000-6チップを用いて作った。
【００５３】
FPGAデザインは、一連の鍵となるデータペアとして16ビット出力ポートへその出力を書き込んだ。このデータを読み出し、後の分析のためにディスクファイルへ保存した。逆アセンブラは、分析のために出力データをデコードし、書き込んだ。
【００５４】
Handel-CシミュレーションとPower-PCシミュレーションの両方のクロック数を計測する時、前記コードは、最大数の発生に向けて実行するように変更した。それらはまた、両方が、同じランダムナンバーシードを用いた。これは、比較が同一条件を用いて行われたかを確かめるために行った。
【００５５】
８つの命令が、回帰問題のために選択され、その命令は、３ビットを必要とした。各命令は、利用可能な４つのレジスタの内、２つのレジスタまで指定することができ、それぞれ２ビットを必要としている。
【００５６】
それゆえ、各命令は、7ビットのストレージを必要とする。この問題に対する命令は、以下の通りである。
・add(Rn,Rm)は、Rmの内容をRnの内容に加算し、結果をRnへ戻す。
・sub(Rn,Rm)は、Rnの値からRmの値を引き算し、結果をRnへ戻す。
・shl(Rn)は、Rnの内容を左に１ビットシフトし、結果をRnにそのまま残す。
・shrは、類似した型であるが、右に１ビットシフトする。
・nopは、動作なしのファンクションである。これは、命令の数を２の累乗にすることを含んでいる。
・haltは、評価を終了させ、Rnにその値を戻す。
・ldim(Rn,Kn)は、定数KnをRnに置く。
・jmpifz(Rn,Rm)は、値がゼロならば、Rnの値をテストし、その時、プログラムサイズを除いてRmの位置にジャンプする。
【００５７】
プログラム終了は、次の状況を引き起こす。
１．halt命令に遭遇する。
２．プログラムにおける最後の命令が実行される。
３．jmpifz命令により、ループが作成され、予定されるループの数が実行される。
【００５８】
これらの命令を実行する機械は、フェッチ、デコード、オペランドアドレス評価とオペランドリード/ライトの命令を含んで、２クロックのサイクル毎に１命令を実行することができる。これをさらに速度アップするために、１命令につき１サイクルを削減して、パイプラインを造ることが可能である。
【００５９】
４つのランダム定数が各個体に対して利用できる。これらは、個体の建造中に一度造られる。
【００６０】
文献上の回帰の多くの例では、掛け算と除算のファンクションが含まれている。これらの２つのファンクションは、デフォルトのHandel-C動作を使ってとても深いロジックを発生させた後に、これらは、より浅いがゆえの速いロジックを発生して、それぞれ２を掛けたり、２で割ったりする、単一左ビットシフト及び右ビットシフト動作に取って代わられる。
【００６１】
回帰問題のためのパラメータのフルセットを表３に示す。入力値ａとｂは、適応度評価の前にレジスタR0とR1に置かれ、プログラムが終了するか、あるいは、Rnの値がHalt命令によって終了するならば、結果xは、レジスタR0から読まれる。適応度データは、プログラムの最初で一度事前に見積られており、適応度評価の全コピーに対して利用される。
【００６２】
表３：回帰問題のためのパラメータ
2004533672.tif 000008
【００６３】
XORファンクションは、４つの基本的なロジック要素AND、OR、NOR、及びNANDを利用している。これらのファンクションのそれぞれは、２つのレジスタRnとRmを持つ。結果は、Rnに置かれる。これらは、ブールXOR問題を解くには十分であることが示されている。実行は、プログラム上の最後の命令が実行された時に終了する。
【００６４】
２つの入力ａとｂは、適応度評価の前にR1とR2に書き込まれ、結果xは、適応度評価後にR0から読まれる。パラメータのフルセットを表４に示す。この問題には、４つだけのファンクションを持ち、各命令は６ビットを必要とする。
【００６５】
表４：XOR問題のためのパラメータ
2004533672.tif 000009
【００６６】
回帰問題に対するシミュレータからの結果を表５に示す。PowerPCの数字は、コマンドラインから直接psimを実行し、cpuのサイクルのトータル数を得るためのIswitchを特定し、その出力から取られる。サイクルの縦列は、パイプライン機能停止と分岐予測の失敗を考慮しているが、任意のメモリサブシステムの遅延は考慮していない。
【００６７】
表５：回帰問題の実行結果
2004533672.tif 000010
【００６８】
速度アップの要素は、２つの状況、つまりプログラムの実行にかかるサイクル数と実時間で与えられている。１番目は、クロックサイクルの関係で参照される。これは、それらがまるで同じクロック周波数で動作しているかのように、２つのインプリメンテーションを処理する。２番目は、PPCのための典型的なクロック速度とFPGAがプレイスアンドルートツールによってレポートされている動作可能な最速周波数とを用いて参照される。速度アップ要素は、Speedupcycle=Cyclesppc/CyclesFPGAと、時間的な速度アップ要素は、Speeduptime=Speedupcycle*Freqppc/FreqFPGA。
【００６９】
１回の実行の内、世代１６で見受けられるこの問題からの例題プログラム（注釈付き）は以下の通りである。
2004533672.tif 000011
【００７０】
XOR問題は、回帰問題と同様な環境を用いて実行される。結果を表６に示す。
表６：XOR問題の実行結果
2004533672.tif 000012
【００７１】
１つの実行の内、世代８６で見受けられるこの問題からの例題プログラム（注釈付き）は以下の通りである。
【００７２】
2004533672.tif 000013
【００７３】
並列化を利用する効果は、異なる部分集団サイズを用いて、Handel-Cシミュレータで問題を実行し、XOR問題を実装することによって測定した。１個体毎の４つのノードの最大値と一緒に、全体集団サイズ８を選択した。これらの低い数は、プログラムが妥当な時間でコンパイルされるように選択した。部分集団の数は、可変として１、２、４、８を用いた。データは、初期集団作成を実行するためのサイクル数と、最初の世代を評価するためのサイクル数と、最初の世代に関する増殖動作を実行するためにサイクル数とを集めた。これらを表７に示す。
【００７４】
表７：GPと異なる部分集団のさまざまな段階に対するサイクルカウントとゲート見積もり
2004533672.tif 000014
【００７５】
図５に、異なる部分集団のサイズに対する適応度評価のサイクル数の影響を示す。並列適応度評価の数が増加するにつれて利益が消失しているということが、この図から分かる。これは、適応度評価の設定に協働して、一定のオーバーヘッドがあるためである。この影響は、集団サイズが、より大きくなるならば、そのようにはならないだろう。
【００７６】
前記問題に対する全サイクル数を図６に示す。前記問題は、１６世代まで実行される。ここでは、増殖段階の効果が見られる。４から８へ並列適応度評価の数を倍増することから得られる利益は、必要とされるサイクルを18％下げる。８つの並列評価が実行される時、初期集団の寄与は、全サイクルの約7.5％である。
【００７７】
最後に、必要とされるハードウェアリソース上で並列適応度評価の数が増加する影響を計測した。これは、図７に示される。これは、必要とされるハードウェアリソースのサイズが線形的な増加を示している。
【００７８】
先の節で議論したXOR問題はまた、PPCシミュレータを用いて実行した。Handel-Cバージョンは部分集団サイズ８を用いた。その結果を表８に示す。FPGAの最大周波数は、67MHzであった。
表８：完全並列のHandel-CプログラムとPPCシミュレータとの比較
2004533672.tif 000015
【００７９】
ここで、GPを用いて解かれた多くの問題と比較すると、FPGAで実行することができるGPシステムを作るためにHandel-Cを用いるという一般的な概念を証明したが、２つの問題が浮上した。Cライク言語の利用は、いくつかの価値のある特性を持っている。もっとも重要であるのは、GPアルゴリズムを伝統的なソフトウェアツールを使って開発でき、テストできるということである。これは、ハードウェアデザインに関して熟達する必要がない点でソフトウェア技術にとっては重要だと考えるべきところである。
【００８０】
上記で示した結果は、今回の実装を利用して、並列適応度評価の数が４よりも大きくなると、増加する利益が低下するということを明確に示している。これは、適応度評価と比較すると、増殖段階が、サイクルの重要な部分を担っているためである。
【００８１】
GPに関して、XOR問題にとって１９の速度増加（Speeduptime）は、より難しいGP問題に対処するために高い貢献度を有する。FPGAがより速く利用できるようになればなるほど、この要素は、さらに活かされる。最新では、Xilinxは、450MHzの最大クロック速度を備えているVirtex II seriesを提供している。
【００８２】
クロックのサイクルの関係で速度アップが相当なものである一方、本研究は、スカラーデータに関して動作する伝統的な命令が実装されることに影響を与えるということを覚えておかなければならない。より大きなゲインのために、ベクトルデータ、例えば画像を動作させることによって、FPGAは使われている。ベクトルデータを使うと、ファンクションセットは、本研究で述べられている問題よりも大きな範囲に対してハードウェアの並列化を活かすように適合させられる。
【００８３】
ブール論理問題として明示され得る問題を考慮すると、サブマシンコードGPの技術は、重要な２つの命令のパフォーマンスを改善することを示す。FPGAを用いる時、可能なワードサイズは、利用できるCLBによってのみ制限される。それゆえ、サブマシンコードGPととても長いワード長を用いることにより、より大きなパフォーマンスゲインの可能性が広がる。
【００８４】
入出力は、ファンクションセットに対して直接的にエンコードされ、プログラムの適合を評価している間、GPシステムを組み込み、ハードウェアを直接制御する。この例は、FPGA上のいくつかのI/Oピンを使って直接的にセンサ入力を読み込み、自動装置に対して直接的に制御信号を発生させる機械的な制御であるだろう。FPGAは、多くのサポートを必要としないので、コントローラのような回路要素は、最も小さい自動装置にでさえ、直接的に組み込まれる。
【産業上の利用可能性】
【００８５】
これまで与えた２つの例題（回帰問題とXOR問題）は、本システムを使って解決される小さな問題を示している。大きな問題を解決するためには、１つかまたは２つ以上の以下のパラメータを増加する必要がある。
１．実行中の世代番号
２．集団のサイズ
３．個体のノード番号
ここまで述べられたシステムは、いずれの変化も伴わず、世代の数の増加に適応させることができたが、集団における個体の数と個体のサイズの両方、もしくはどちらか一方を増加するためには、いくつかの変化が必要とされる。
【００８６】
FPGAシステムにおいて、ランダムアクセスメモリを実現する３つの方法がある。第一に、メモリは、各CLBにおける単一ビットストレージ要素を利用することによって合成され得る。これは、結果として、並列ハードウェアによってアクセスされる高速メモリを生ずる。第二に、FPGAの中には、Handel-Cプログラムによって使用可能であるオンチップRAMを利用できるものがある。これは、結果として、高速メモリを生ずる。これは、１クロックのサイクル毎に１度だけアクセスが可能であるが、それゆえ、並列マシンでメモリにアクセスする時、その有用性を制限してしまう。最後に、外部オフチップRAMが、入出力ピンの中で利用できるものを使って、FPGAに対して接続し得る。これは、容量的に、数ギガバイトのRAMを与えることになるが、アクセス速度の損失がある。
【００８７】
より大きな集団サイズとより大きな個体を取り扱うシステムに拡張することは、集団が、高速システム設計メモリで占められるアクティブな部分集団と、より低速なオンチップRAMまたはオフチップRAMで占められる非アクティブな部分集団に分離されることが必要となる。個体は、低速な非アクティブ部分集団と高速なアクティブ部分集団との間で移動させられる。主評価と増殖段階を並列に実行されるための個体の移動を調節することによって、低速な非アクティブ部分集団にアクセスすることによって負わされる遅延が、最小限に抑えられ得る。
【図面の簡単な説明】
【００８８】
【図１】FPGAの一般的なモデルを示す。
【図２】CLBの一般的なモデルを示す。
【図３】線形フィードバックシフトレジスタランダムナンバージェネレータ（Linear Feedback Shift Register Random Number Generator）の一覧図を示す。
【図４】ハードウェアへコードを翻訳する処理の概観を示す。
【図５】集団に対する一つの適応度ファンクション評価を実行するサイクル数を説明する。
【図６】問題に対する全サイクル数を説明する。
【図７】並列適応度評価の数の増加に対して見積られたNANDゲート数を説明する。
【図２】
2004533672.tif 000016
【図３】
2004533672.tif 000017
【図４】
2004533672.tif 000018
【図５】
2004533672.tif 000019
【図６】
2004533672.tif 000020
【図７】
2004533672.tif 000021
【国際公開パンフレット】
2004533672.tif 000022
2004533672.tif 000023
2004533672.tif 000024
2004533672.tif 000025
2004533672.tif 000026
2004533672.tif 000027
2004533672.tif 000028
2004533672.tif 000029
2004533672.tif 000030
2004533672.tif 000031
2004533672.tif 000032
2004533672.tif 000033
2004533672.tif 000034
2004533672.tif 000035
2004533672.tif 000036
2004533672.tif 000037
2004533672.tif 000038
2004533672.tif 000039
2004533672.tif 000040
2004533672.tif 000041
2004533672.tif 000042
2004533672.tif 000043
2004533672.tif 000044
2004533672.tif 000045
2004533672.tif 000046
2004533672.tif 000047
2004533672.tif 000048
2004533672.tif 000049
2004533672.tif 000050
2004533672.tif 000051
2004533672.tif 000052
2004533672.tif 000053
2004533672.tif 000054
2004533672.tif 000055
2004533672.tif 000056
2004533672.tif 000057
2004533672.tif 000058
2004533672.tif 000059
2004533672.tif 000060
2004533672.tif 000061
【国際公開パンフレット（コレクトバージョン）】
2004533672.tif 000062
2004533672.tif 000063
【国際調査報告】
2004533672.tif 000064
2004533672.tif 000065
2004533672.tif 000066