再構成ユニットによる解探索の方法およびデータ処理装置
【課題】遺伝的アルゴリズムにより解を探索するのに適したデータ処理装置を提供する。
【解決手段】回路を再構成可能なＰＥマトリクス１０と、ＰＥの接続情報を含むコンフィグレーションデータ１８により回路を再構成する制御ユニット２ａと、遺伝的アルゴリズムによりヒューリスティックにコンフィグレーションデータ（発見的コンフィグレーションデータ、ＧＣＤ）を生成する生成ユニット２ｂとを有するデータ処理装置５０を提供する。データ処理装置５０は、さらに、発見的なコンフィグレーションデータにより再構成される評価対象回路６１に対し入力データの複数のサンプルを供給するサンプルデータ供給ユニット６２と、評価対象回路６１の出力データの少なくとも一部を用いて評価する評価ユニット６３とを含む。
【解決手段】回路を再構成可能なＰＥマトリクス１０と、ＰＥの接続情報を含むコンフィグレーションデータ１８により回路を再構成する制御ユニット２ａと、遺伝的アルゴリズムによりヒューリスティックにコンフィグレーションデータ（発見的コンフィグレーションデータ、ＧＣＤ）を生成する生成ユニット２ｂとを有するデータ処理装置５０を提供する。データ処理装置５０は、さらに、発見的なコンフィグレーションデータにより再構成される評価対象回路６１に対し入力データの複数のサンプルを供給するサンプルデータ供給ユニット６２と、評価対象回路６１の出力データの少なくとも一部を用いて評価する評価ユニット６３とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路を再構成可能なユニットを用いた解探索方法およびデータ処理装置に関するものである。
【背景技術】
【０００２】
特許文献１には、生物の進化の過程を模倣した最適化手法の１つである遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ）をもとに考案された遺伝的プログラミング（ＧＰ：Ｇｅｎｅｔｉｃ Ｐｒｏｇｒａｍｍｉｎｇ）を画像処理に適用したツリー構造状画像変換自動作成方法を印刷物の文字列抽出方法に用いることが記載されている。
【０００３】
特許文献２には、解探索装置及びその初期値設定方法について開示されている。この方法は、数値計算によって物理化学現象をシミュレーションするソフトウェアに組み込まれた物理化学モデルが用いる複数のパラメータの値が、測定結果の様に外部から与えられたデータとの誤差を最小となる様に、遺伝的アルゴリズムを用いて自動的に探索する計算方法に関するものである。さらに、具体的には、この解探索装置、例えば、半導体回路シミュレータが内蔵するトランジスタモデルが持つ複数のパラメータを実測した電流電圧データ（Ｉ−Ｖデータ）の誤差が小さくなる様に合せ込んだり、半導体プロセスシミュレータが内蔵するイオン注入モデルが持つ複数のパラメータをＳＩＭＳ測定した結果に合せ込んだりして、これらのシミュレータと実測結果の食い違いを抑制する事で、これらのシミュレータの予測性を高める為に用いられるものである。
【０００４】
特許文献３には、コジェネレーションシステムの最適化方法および設備提案システムが記載されている。この最適化方法では，機器構成の最適化と運転パターンの最適化とを交互に繰り返す。そして，機器構成の最適化の際，機器と運転パターンとを１組の機器情報データとし，その機器情報データを基本単位として遺伝子操作中の交叉を行う。また，運転パターンの最適化の際、機器構成を固定し、その機器構成での運転パターンについて遺伝子操作を行う。そして，最適化された機器構成および運転パターンでの評価値を判定する。判定条件を満たしていない場合には，判定条件を満たすまで上記処理を繰り返すことが記載されている。
【０００５】
特許文献４には、画像処理方法として、誤差拡散処理の目標としての２値画像であるターゲット画像を、遺伝的アルゴリズムに基づいて生成しておくことが記載されている。そして、均一輝度画像に対して誤差拡散パラメータを用いた誤差拡散処理を施すことによって比較画像を生成し、該比較画像と前記ターゲット画像の画質の差を評価する画質評価関数を設定し、この画質評価関数による評価値が最小となるように、誤差拡散パラメータを最適化する。
【０００６】
特許文献５には、情報処理機構を用いて運転指向を推定する場合、遺伝的アルゴリズムを用いた情報処理機構で、計算負荷の増加を抑制できる運転指向推定装置を提供することが記載されている。運転指向推定装置は、運転指向によって変化する可能性のある運転操作量を検出する運転操作量検出部と、車両の走行環境に基づいて、前記検出された運転操作量を補正する運転操作量補正部とを備え、補正された運転操作量に基づいて、情報処理機構を用いて運転指向を推定する。走行環境には、道路の勾配及び路面の滑り易さの少なくともいずれか一方が含まれることができる。運転操作量には、アクセル開度、アクセル開度変化量、及びブレーキ踏力の少なくともいずれか一つが含まれることができる。
【０００７】
特許文献６には、計算機を用いて所望の物性値条件を満たす高分子の構造を求める高分子材料設計方法であって、高分子モデルの作成条件および物性値条件を入力するステップと、この作成条件の下でモノマーに基づく構成単位を高分子の設計単位とし、この設計単位を遺伝子として遺伝的アルゴリズムの個体となる高分子モデルを作成するステップと、作成された高分子モデルについて物性値を計算し、前記物性値条件に対する適合度を計算するステップとを有する。そして、遺伝的アルゴリズムを用いて、次世代以降の個体の作成および適合度計算のステップを繰り返し、適合度の大きい高分子の構造を探索することを特徴とする方法が記載されている。
【０００８】
特許文献７には、ロボットの行動学習に有利なセンサの形態を自動的に設計することができるセンサ設計装置が記載されている。初期世代作成部は、センサの形態を特定するための複数の遺伝子型を作成し、各遺伝子型により特定されるセンサの形態を有する複数のロボットを仮想的に作成し、行動学習部は、複数のロボットに仮想的に学習を行わせ、学習結果を基に各ロボットの適応度を算出し、選択部は、各ロボットの適応度を基に親個体となる複数のロボットを選択し、次世代作成部は、選択されたロボットの遺伝子型から遺伝的アルゴリズムに基づき次世代の遺伝子型を作成し、各次世代の遺伝子型により特定されるセンサの形態を有する複数のロボットを仮想的に作成し、行動学習部は、次世代の複数のロボットに仮想的に再度学習を行わせ、選択部、次世代作成部及び行動学習部による処理を所定世代繰り返してセンサの形態を決定することが記載されている。
【０００９】
特許文献８には、２次元以上の空間に複数の要素を最適な状態で配置する要素配置最適化問題において、問題規模の大きい要素配置最適化問題を高速に処理できるようにすることが記載されている。複数の要素の初期配置状態に関する情報がコンピュータに入力されると、遺伝的アルゴリズムをＣＰＵで実行して、初期配置状態にある複数の要素の疎密を解消する第１アルゴリズム実行ステップと、第１アルゴリズム実行ステップにて疎密が解消された後の複数の要素の中間配置状態に関する情報がコンピュータに入力されると、局所的疎密解消アルゴリズムをＣＰＵで実行して、中間配置状態にある複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとを実行することにより、接続関係を維持しながら初期配置状態にある複数の要素の疎密を解消することが記載されている。
【００１０】
特許文献９には、通信システムに応用されるシーケンスの生成方法が記載されている。この方法は、長さの予め設定された複数のシーケンスをランダムに生成するステップ（１）と、各シーケンスの特定のパラメータ値を計算するステップ（２）と、計算により得られた特定のパラメータ値が一定の条件を満たす複数のシーケンスを選択するステップ（３）と、以上の処理により得られたシーケンスに対して適応遺伝変異を行い、適応確率により変異後特定のパラメータ値が最適になったシーケンスを選択するステップ（４）と、予め決めた回数までステップ（２）から（４）を繰り返し、最後に得られた複数のシーケンスから、特定のパラメータ値が最適なシーケンスを選択して出力シーケンスとするステップ（５）とを含む。
【００１１】
特許文献１０には、テンプレート画像を含む画像の検索を高速に高い精度で行うことが記載されている。領域選択受付部からの画像の領域の選択に基づいてテンプレート画像生成部はテンプレート画像を生成する。このテンプレート画像および検索対象になるターゲット画像は、画像縮小部において所定の縮小率に縮小される。個体抽出部において生成されたターゲット画像とテンプレート画像とを照合する領域の情報を有する染色体の適応度が、ターゲット画像準備値テーブルおよびテンプレート画像準備値テーブルに保持された準備値を用いて適応度算出部において算出された後、遺伝的アルゴリズム処理部で選択、交配および突然変異が行われる。以上の処理を所定世代数繰り返した後に、準最適解に対応する適応値が所定の閾値を超えているか否かが類似画像判断部で判断されることが記載されている。
【００１２】
特許文献１１には、周期的に配置されてなるマイクロレンズアレイの形状測定方法が記載されている。この方法では、被測定対象のマイクロレンズアレイに所定波長の入射光を入射させ、透過側又は反射側に生じる回折光の直交する２つの方向に回折される各々複数の回折次数の強度を検出することで、各回折次数の回折効率の実測値を求め、他方、被測定対象のマイクロレンズアレイの各レンズの形状として２次元的なサンプリング点に初期値を与え、その初期値から出発して前記所定波長の入射光を入射させたときに透過側又は反射側に生じる回折光の直交する２つの方向に回折される各々複数の回折次数の強度を厳密な電磁波解析により算出し、順次遺伝的アルゴリズムを適用しながら、その算出値と前記実測値の差をパラメータとする評価関数を用いて、前記初期値の形状を最適化する。
【００１３】
特許文献１２には、マルチビームを用いた電子写真方式の画像形成手段や回転多面鏡による走査光学系を用いた電子写真方式の画像形成手段において発生する画質の劣化を防ぐことが記載されている。そのため、評価手段によりマルチビームの各ビームで発生するドットの出現頻度や回転多面鏡の各反射面によって走査形成されるドットの出現頻度に基づいてディザマトリクスに応じて生成される画像データに対する評価を行ない、この評価結果に基づき求めたディザマトリクスの適応度に基づいて遺伝的アルゴリズム処理手段により遺伝的アルゴリズム処理を実行し、ディザデータ出力手段においては生成した遺伝子情報によりディザマトリクスを出力する。これにより、マルチビームの各ビームで光量に違いがある場合や回転多面鏡の反射面にばらつきがある場合であっても、画質への影響を軽減させることができるので、画質の劣化を防ぐことができることが記載されている。
【００１４】
特許文献１３には、機械本体の複数個所の温度測定に基づいて加工点における熱的な変位量を推定し補正する機能を備えた工作機械における、補正に用いられる所定の関係式に適合する最適な温度測定位置を遺伝的アルゴリズムを用いて求めることが記載されている。
【００１５】
特許文献１４には、適切なパレート最適個体を短時間で効率良く得ることが可能な多目的最適化装置、多目的最適化方法および多目的最適化プログラムを提供することが記載されている。多目的進化型アルゴリズム部は第１、第２および第３の親個体から複数の子個体候補を生成する。次に、適応度推定モジュールは全ての親個体および子個体候補についての真の適応度の推定値を算出する。さらに、多目的進化型アルゴリズム部は、全ての親個体および子個体候補のランキングを行い、最上位ランクの１つの子個体候補を親個体集合に追加して混雑度を算出し、それらの子個体候補を混雑度の良い順にソートし、より良い混雑度を有する所定数の子個体候補を子個体集合として選択する。多目的最適化問題の一例は、エンジンの燃費およびトルクの最適化に適用することである。
【００１６】
特許文献１５には、巡回すべき複数の地点に順序および／または時間的な制約がある場合に、当該制約を満足し得る巡回経路を探索できるようにすることが記載されている。そのため、巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する操作・入力手段と、２地点間の経路を探索する２点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索して記憶し、巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【００１７】
特許文献１６には、車両毎にパラメータ調整を行う必要がなく、車両の運動状態の変化に即応してリアルタイムにコーナリングパワーを推定可能なコーナリングパワー推定装置を提供することが記載されている。このため、コーナリングパワー推定装置は、車両運動モデルに基づいてヨーレートの推定値の演算を行う演算装置と、遺伝的アルゴリズムによる進化計算を行う算出装置とを備えている。
【００１８】
特許文献１７には、所定環境において最適解を求めるにあたり、染色体の初期値を新たに発生させる場合に、探索済み領域以外の領域に発生させ、効率的に最適解を求めることが記載されている。複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、最適解を求める最適解探索装置において、適応度値の変化率と予め定められた変化率とを比較し、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する。その際に、すでに導入されている情報体の分布情報を参照して、情報体密度がより少ない領域に対して新たに情報体を導入する。
【００１９】
特許文献１８には、複数種類のプロセッシングエレメントの機能およびそれらの接続を変えて種々のデータパスを動的に再構成するタイプの集積回路装置が記載されている。
【特許文献１】特開２００４−３６２４４０号公報
【特許文献２】特開２００６−２３８６８号公報
【特許文献３】特開２００６−２６８１０２号公報
【特許文献４】特開２００６−３０３９９９号公報
【特許文献５】特開２００６−３１２４１４号公報
【特許文献６】特開２００７−３１５４１号公報
【特許文献７】特開２００７−４１７２３号公報
【特許文献８】特開２００７−５２７９９号公報
【特許文献９】特開２００７−６８１７４号公報
【特許文献１０】特開２００７−１０２６３４号公報
【特許文献１１】特開２００７−１２１０５７号公報
【特許文献１２】特開２００７−１３７００７号公報
【特許文献１３】特開２００７−１６７９６６号公報
【特許文献１４】特開２００７−１７２３０６号公報
【特許文献１５】特開２００７−１８７５８４号公報
【特許文献１６】特開２００７−１９０９５５号公報
【特許文献１７】特開２００７−１９９９４３号公報
【特許文献１８】特開２００６−２８５３８６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２０】
遺伝的アルゴリズムは、メタヒューリスティック（Ｍｅｔａｈｕｒｉｓｔｉｃ）な解法の一例である。メタヒューリスティクスは、一般的な計算問題を解くためのヒューリスティックな方法（トライアンドエラーにより問題を解く方法）の１つであって、特定の問題に限定されず、どのような問題に対しても汎用的に対応できるように設計された、アルゴリズムの基本的な枠組みを示す。メタヒューリスティクスには、遺伝的アルゴリズムの他に、シミュレーテッドアニーリング法などが含まれる。また、この明細書において遺伝的アルゴリズムとは、遺伝的プログラミング、免疫的アルゴリズムなどのさまざまな拡張手段を含むものである。
【００２１】
遺伝的アルゴリズムは、上記特許文献１−１７に示したように、多種多様な分野において多種多様な問題の解決に用いることが提案されている。遺伝的アルゴリズムを用いて、問題に対する解を見つける際に、一般的に要求されることは、できるだけ複雑な遺伝子を表現できること、できるだけ任意な遺伝子を選択できることである。そして、各遺伝子をできるだけ多くの条件で適正に評価し、世代交代をできるだけ多く繰り返すことにより、最も適応度の高い個体（遺伝子）を「解」として出力することである。しかしながら、世代交代により生み出される各遺伝子を評価するためには、通常、長時間を要する。このため、複雑な表現を持った遺伝子の採用が実際には困難であり、最大世代数も限られてしまうことが多い。さらに、進化に長時間を要するために、遺伝子をリアルタイムに、あるいはリアルタイムに近い状態で進化させて、環境への適応力を高めることも難しい。
【００２２】
このような問題は、遺伝的アルゴリズムを用いた解法に限らず、トライアンドエアーを繰り返し（反復し）、解を発見的に導く、メタヒューリスティックな解法に共通するものである。したがって、複雑な表現を持った遺伝子に代表されるメタヒューリスティクスな解を高速で評価できる手段および方法が求められている。
【課題を解決するための手段】
【００２３】
本発明の一態様は、回路を構成するための複数のエレメントと、複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、内部配線による複数のエレメントの接続を変更すること、および／または複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置である。この制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより、再構成ユニットの少なくとも一部に回路を再構成する。このデータ処理装置は、さらに、発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給するサンプルデータ供給ユニットと、複数のサンプルに基づく評価対象回路の出力データの少なくとも一部を用いて評価対象回路の評価値を得る評価ユニットとを含む。
【００２４】
再構成ユニットに回路を再構成するためのコンフィグレーションデータと、そのコンフィグレーションデータにより再構成される回路とは、基本的に一対一で対応する。したがって、コンフィグレーションデータに何らかの変化があれば、それにより再構成される回路も変化する。回路のそのような変化により、回路の出力に影響があるか否かはケースバイケースである。しかしながら、コンフィグレーションデータを、それにより再構成される回路の出力を用いて評価することが可能であり、最適解として評価されたコンフィグレーションデータにより、同一構成の他の再構成ユニットに回路を再構成すれば、同一の性能を得られる。そして、コンフィグレーションデータの評価は、コンピュータプログラムにより動作する数値的な計算またはシミュレーションではなく、再構成ユニットに再構成された回路を機能させる、すなわち、複数の入力データのサンプルを再構成された回路に供給することで短時間に行えるようになる。
【００２５】
また、複雑な遺伝子に対応するような複雑なコンフィグレーションデータも、それに対応した回路として再構成ユニットに実装される。そのようなコンフィグレーションデータにより再構成される回路は、回路構成が複雑になるかもしれない。しかしながら、回路構成が複雑になることにより処理速度が低下したとしても、その度合いは、プログラムステートメントが増大することによる処理速度の低下とは比較にならないほど小さく、複雑なコンフィグレーションデータであっても短時間で評価できる。さらに、パイプライン処理、並列処理などを併用することにより、より高速な評価が可能となる。したがって、複雑な表現を持った遺伝子に代表されるメタヒューリスティクスな解を高速で評価できる。
【００２６】
サンプルデータ供給ユニットは、評価対象回路においてパイプライン処理が行われる間隔で複数のサンプルを供給し、評価ユニットは、評価対象回路とともに、再構成ユニットに構成されることが好ましい。発見的なコンフィグレーションデータにより、パイプライン処理が行われる評価対象回路が構成されれば、評価ユニットにおける処理も含めてパイプライン処理が可能となる。したがって、複雑なコンフィグレーションデータであっても、実質的に、評価結果を、サンプルの入力データを入力するために要する時間程度の短い間隔で得ることができる。
【００２７】
制御ユニットは、複数セットの発見的なコンフィグレーションデータを出力し、再構成ユニットには、複数セットの発見的なコンフィグレーションデータにより、複数の評価対象回路が再構成され、サンプルデータ供給ユニットは、複数の評価対象回路に対し並列に前記複数のサンプルを供給することが望ましい。複数セットの発見的なコンフィグレーションデータを、複数の評価対象回路により並列に評価できる。したがって、評価結果を短時間に得ることができる。
【００２８】
評価ユニットから得られる評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成し、制御ユニットより使用可能とする生成ユニットをさらに有することが望ましい。評価結果が得られる時間を短縮できるので、世代交代する間隔を短縮でき、最適解を得るための最大世代数を増大できる。
【００２９】
生成ユニットは、再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成する機能を含むことが望ましい。発見的なコンフィグレーションデータにより再構成される評価対象回路は、予め規定される評価ユニットにおいて有意な出力データを出力するとは限らない。テンプレートコンフィグレーションデータを親または現世代として次世代の発見的なコンフィグレーションデータを生成することにより、無駄あるいは評価対象にならない評価対象回路を再構成するような発見的なコンフィグレーションデータが生成される可能性を抑制できる。
【００３０】
複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータであることが望ましい。このようなテンプレートコンフィグレーションから生成される次世代の発見的なコンフィグレーションデータを生成することにより、次世代の発見的なコンフィグレーションデータがパイプライン処理を行う評価対象回路を再構成するものである可能性を向上でき、評価時間を短縮できる可能性が高くなる。
【００３１】
生成ユニットは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、次世代の発見的なコンフィグレーションデータを生成することが望ましい。内部配線による複数のエレメントの接続を変更することも含めて次世代の発見的なコンフィグレーションデータを生成しても良い。複雑で多種多様な遺伝子に相当するコンフィグレーションデータを生成できる。しかしながら、評価対象にならない評価対象回路を再構成するコンフィグレーションデータも生成され易くなる。コンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新して、次世代の発見的なコンフィグレーションデータを生成することにより、評価対象にならない評価対象回路を再構成するコンフィグレーションデータが生成される可能性を低くできる。
【００３２】
テンプレートコンフィグレーションデータが、解を求めようとしているシステムなどに固有の条件を反映するものであっても良い。テンプレートコンフィグレーションデータの、それら固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代の発見的なコンフィグレーションデータを生成するようにしても良い。発見的なコンフィグレーションデータの変化、突然変異の範囲が縮小されるが、システムに適した解を早いタイミングで得ることができる。
【００３３】
本発明の他の態様の１つは、再構成ユニットと、コンフィグレーションデータを出力する制御ユニットとを有するデータ処理装置であって、制御ユニットは、最適解として評価された発見的なコンフィグレーションデータにより回路を再構成する、データ処理装置である。最適解として評価された発見的なコンフィグレーションデータにより、再構成ユニットに、評価対象回路と同一の回路を構成することができ、最適と評価された機能を再構成ユニットにより提供できる。
【００３４】
本発明の他の態様のさらに異なるものは、回路を再構成可能な再構成ユニットを用いた解探索の方法である。再構成ユニットは、複数のエレメントと、複数のエレメントを接続するための内部配線とを含み、内部配線による複数のエレメントの接続を変更すること、および／または、複数のエレメントの機能を変更することにより、回路を再構成可能である。再構成ユニットの回路を再構成するためのコンフィグレーションデータは、複数のエレメントの接続情報および／または複数のエレメントの機能情報を含む。当該方法は、以下の各ステップを有する。
・少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより再構成ユニットの少なくとも一部に回路を再構成すること。
・発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給すること。
・複数のサンプルに基づく評価対象回路の出力データの少なくとも一部を用いて評価対象回路の評価を得ること。
・評価を得ることを繰り返すことにより、評価対象回路を再構成するための発見的なコンフィグレーションデータを解として探索すること。
【００３５】
この方法は、発見的なコンフィグレーションデータを、その発見的なコンフィグレーションデータにより再構成ユニットに再構成される回路により評価できる。したがって、高速で、最適解を探索できる。
【００３６】
サンプルを供給するステップは、評価対象回路においてパイプライン処理が行われる間隔で複数のサンプルを供給することを含み、評価値を得るステップは、評価対象回路とともに、再構成ユニットに構成される回路により評価値を得ることを含むことが望ましい。
【００３７】
再構成するステップは、複数セットの発見的なコンフィグレーションデータにより、再構成ユニットに複数の評価対象回路を再構成することを含み、サンプルを供給するステップは、複数の評価対象回路に対し並列に複数のサンプルを供給することを含むことが望ましい。
【００３８】
評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することをさらに有することが望ましい。そのような発見的なコンフィグレーションデータは、遺伝的アルゴリズムにより生成される遺伝子に対応したコンフィグレーションデータ（遺伝子的コンフィグレーションデータ、遺伝的コンフィグレーションデータ、遺伝子対応コンフィグレーションデータ）となる。次世代の発見的なコンフィグレーションデータは、現世代の発見的なコンフィグレーションデータとして使用され、評価対象回路が再構成される。
【００３９】
上記の生成するステップは、再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４０】
複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータであることがさらに望ましい。
【００４１】
生成するステップは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４２】
テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、生成するステップは、テンプレートコンフィグレーションデータの、固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４３】
また、この方法は、さらに、前世代のコンフィグレーションデータを、内部配線による複数のエレメントの接続を変更することを含めて、遺伝的アルゴリズムにより更新し、再構成ユニットにより評価し、複数のテンプレートコンフィグレーションデータを探索することをさらに含むことが望ましい。あるシステムに対して適当な解が得られそうなテンプレートコンフィグレーションデータは、ヒューリスティックな方法により探索できる。それを、事前に、再構成ユニットを用いて行うことにより、最適解の探索に要する時間を短縮できる。
【発明を実施するための最良の形態】
【００４４】
図１（ａ）に、再構成可能なデバイスの一例を示している。このデバイス１は、本願の出願人が開発したＤＡＰＤＮＡと称する半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、ＤＮＡ３のダイレクト入出力用のインターフェイス４と、ＰＣＩインターフェイス５と、ＳＤＲＡＭインターフェイス６と、ＤＭＡコントローラ７と、その他の周辺デバイス８と、これらを接続するための高速スイッチングバス（内部バス）９とを含む。ＤＡＰ２は、デバッグインターフェイス４２ａと、ＲＩＳＣコア４２ｂと、命令キャッシュ４２ｃと、データキャッシュ４２ｄとを含む。ＤＮＡ３は、３７６個のＰＥ（ＰＥｓ、処理エレメント）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれるＰＥｓの機能および／またはＰＥｓの接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。ＰＥマトリクス１０に配置されるＰＥの数は、上記に限定されるものではない。
【００４５】
コンフィグレーションメモリ１９は、複数バンクの構成になっている。例えば、図１（ｂ）に示すように、ＰＥマトリクス１０には、フォアグラウンドバンクに格納されるコンフィグレーションデータ１８により第１の機能（データフロー、回路デザイン）１７ａが構成される。また、異なるバックグラウンドバンクにそれぞれ格納されるコンフィグレーションデータにより、第２の機能１７ｂおよび第３の機能１７ｃがそれぞれ構成される。メモリ１９のバンクを切り替えることにより、ＰＥマトリクス１０には、第１の機能１７ａに変わって第２の機能１７ｂまたは第３の機能１７ｃが再構成される。ＰＥマトリクス１０の再構成は、例えば、１サイクル（クロックサイクル）でダイナミックに行なわれる。このようにＰＥマトリクス１０は、回路を構成するための複数のエレメントと、これらのエレメントを接続するための内部配線とを含む再構成ユニットであり、内部配線によりエレメントの接続を変えることによりＰＥマトリクス１０に含まれる回路を動的に再構成できる。
【００４６】
図１（ｃ）は、ＰＥマトリクス１０に回路を再構成する一例である。あるアプリケーション、例えばＭＰＥＧデコーダを時分割した複数の機能（サブファンクション）を、ＰＥマトリクス１０に時分割で動的に再構成し、ＭＰＥＧデコーダの機能を専用回路（専用ハードウェア）で提供する。このような使用により、再構成可能なデータ処理装置であるデバイス１を用いて、多くのハードウエア資源を必要とするアプリケーションを、少ないハードウエア資源で実行できる。
【００４７】
図１（ｄ）は、ＰＥマトリクス１０に回路を構成する他の例の一つである。再生方式が異なるアプリケーションを実行するために、複数の機能がそれぞれ実現されるようにＰＥマトリクス１０を再構成できる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。このデバイス１は、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能を切り換えて実装できるので、専用のハードウエアに匹敵する速度で処理を行うことができる。さらに、ＰＥマトリクス１０に含まれるＰＥｓは、クロックにより同期した処理を行うことが可能であり、パイプライン処理に適したデータフロー（データパス）をＰＥマトリクス１０に再構成できる。さらに、多数のＰＥｓにより並列処理を行う複数のデータフローを並列に再構成することも可能である。したがって、ＰＥマトリクス１０に回路を動的に再構成することにより、ハードウエアにより高速処理と、ソフトウエアのような柔軟性とが融合された動作環境および解探索環境を提供できる。
【００４８】
図２に、ＰＥマトリクス１０の配列を拡大して示している。処理エレメントＰＥｓは、全体として、１６×２４のマトリクスを構成するように配置されている。なお、図３に示すように、ＰＥのいくつかは、２個分のＰＥのスペースを占め、全体として３７６個のＰＥがＰＥマトリクス１０に実際には配置されているが、図２には反映していない。これらのＰＥｓは、さらに、それぞれ８×８のＰＥｓからなる６つのグループに区分けされている。これらのグループをセグメントＳと称し、ＰＥマトリクス１０の左上から右下に向かって順番にセグメントＳ０からセグメントＳ５が配置されている。各々のセグメントＳ０〜Ｓ５に含まれるＰＥは、１サイクルの遅延の範囲内でデータを送受信可能なイントラセグメントコネクションで接続されている。また、セグメントＳ０〜Ｓ５の内、隣接するセグメントは、後述するディレイエレメントを介してインターセグメントコネクション２２により接続されている。
【００４９】
図３に、ＰＥマトリクス１０に含まれるＰＥｓの具体的な配置例を示している。図３に示したＰＥのうち、「ＥＸ」で始まるＰＥは、ＥＸＥエレメントと呼ばれ、算術演算、論理演算および２入力の比較機能を含む演算用のエレメントである。「ＥＸＣ」は、ＣＭＰＳＢ命令を搭載し、「ＥＸＦ」は、ＦＦ１命令を搭載し、「ＥＸＭ」は、乗算命令を搭載し、「ＥＸＲ」はＢＲＥＶ命令を搭載し、「ＥＸＳ」は、ＢＳＷＡＰ命令を搭載するというように、タイプ毎に固有の演算機能も含んでいる。
【００５０】
「ＤＬ」で始まるＰＥは、ディレイエレメントであり、１−８クロックの間の遅延をそれぞれ設定できる。「ＤＬＥ」は、セグメント内のデータ遅延用であり、「ＤＬＶ」は縦方向のセグメント間のデータ送受信用であり、「ＤＬＨ」は横方向のセグメント間のデータ送受信用であり、「ＤＬＸ」は縦横方向のセグメント間のデータ送受信用のエレメントである。
【００５１】
「ＲＡＭ」と表示されたＰＥは、ＤＮＡの内部メモリとして使用されるエレメント（メモリエレメント）である。「ＬＤＢ」と表示されたＰＥは、データ入力用のＤＮＡ内部バッファである。「ＳＴＢ」と表示されたＰＥは、データ出力用のＤＮＡ内部バッファである。「Ｃ１６Ｅ」と表示されたＰＥは、ＤＮＡ内部バッファに対するアドレス生成エレメントである。「Ｃ３２Ｅ」と表示されたＰＥは、外部メモリ空間に対するアドレス生成エレメントである。「ＬＤＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏからのデータ入力用エレメントである。「ＳＴＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏへのデータ出力用エレメントである。ＰＥマトリクス１０において、ＬＤＢおよびＬＤＸは、外部からデータを入力するための入力インターフェイスとして使用でき、ＳＴＢおよびＳＴＸは、外部へデータを出力するための出力インターフェイスとして使用できる。
【００５２】
図４に、ＰＥの一例として、ＥＸＥエレメント（「ＥＸＭ」）の概略構成をブロック図により示している。ＥＸＭエレメントは、ＡＬＵ１１ａと、ＭＵＬ（１６×１６）１１ｂと、ＦＦ１１ｃなどを含む。このＥＸＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納されたコンフィグレーションデータ１８に含まれる、ＰＥの機能を設定するための機能情報により、算術演算、論理演算、２入力の比較機能、さらには、乗算のいずれか、または複合した命令を実行するように構成できる。また、複数のＦＦ１１ｃを内蔵しているので、エレメントＰＥに対するデータの入力から出力までのレイテンシを制御することが可能であり、ディレイエレメント（ＤＬＥ）の数が不足する構成では、ディレイエレメントとしての機能をセットすることも可能である。
【００５３】
図５に、ＰＥの他の例として、ＲＡＭエレメント（「ＲＡＭ」）の概略構成をブロック図により示している。このＲＡＭエレメントは、データ格納用メモリエレメントであり、１６ＫＢ（３２ビット×４０９６ワード）のＲＡＭモジュール１２ａと、アドレス入力用のアドレスレジスタ（ＦＦ）１２ｂ、ラッチ１２ｃ、データ入力用のライトデータレジスタ（ＦＦ）１２ｄ、ラッチ１２ｅ、データ出力用のリードデータレジスタ（ＦＦ）１２ｆを含む。ＲＡＭモジュール１２ａのリードとライトの制御は、アドレスデータおよび／またはリードデータとともに入力されるトークンの値により行なわれる。アドレス入力からリードデータの出力までは、ＥＸＥエレメントと同様に３クロックサイクル程度で可能になっており、ＰＥマトリクス１０に含まれる他のタイプのＰＥと同様のレイテンシで、データの入出力が可能である。このＲＡＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納され、それぞれのＰＥに供給されるコンフィグレーションデータ１８に含まれる機能情報により、３２ビットモード、デュアルポート３２ビットモード、ＦＩＦＯモード、１６ビットモード、８ビットモード、さらに、ＦＳＭ（フィードバックステートモード）でデータ入力および／または出力するように構成できる。
【００５４】
ＲＡＭエレメントのアクセスアドレスの生成には、ＥＸＥエレメント、カウンタエレメントであるＣ１６Ｅおよび／またはＣ３２Ｅを使用することができ、ＰＥマトリクス１０のルーティングマトリクス（マトリクスバス）を通じて、ＲＡＭエレメントに入力できる。したがって、ＲＡＭエレメントへの入出力は、ＰＥマトリクス１０に再構成される回路により制御できる。なお、ＲＡＭ、ＥＸ以外のＰＥについても、同様に、それぞれのＰＥに提供されるコンフィグレーションデータ１８に含まれる機能情報により、機能（定数などを含めて）を設定および変更できる。
【００５５】
ＰＥマトリクス１０は、複数のＰＥｓと、それらを接続するためのルーティングマトリクス（内部配線、配線群）２０を含む。ルーティングマトリクス２０は、セグメントＳ内のＰＥを接続するための第１レベルの配線群（第１レベルのルーティングマトリクス、イントラコネクト）２１と、ディレイエレメントを介して隣接するセグメントＳの間を接続するための第２レベルの配線群（第２レベルのルーティングマトリクス、インターコネクト）２２とを含む。ルーティングマトリクス２０によるＰＥｓの接続はコンフィグレーションデータ１８により制御できる。したがって、ＰＥマトリクス１０には、コンフィグレーションデータ１８により、複数のＰＥのそれぞれの機能を変更すること、および／または、ルーティングマトリクス２０の少なくとも一部の接続を変更することにより、異なる回路（データパス、データフロー）を再構成できる。
【００５６】
図６に、セグメントＳの内部のＰＥｓを接続するための第１レベルの配線群２１の構成の一例を示している。第１レベルのルーティングマトリクス２１は、セグメントＳ０に含まれる８×８個のＰＥｓを接続するために、１２８の縦方向のバス２３と、６４の横方向のバス２４とを含む。縦方向のバス２３は、１６のグループに分けられ、それぞれ８のバスを含む２つのＶ−バス２３ｘおよび２３ｙがペアとなり、ＰＥｓの縦の列（コラム）に沿って、その列の両側に配置されている。横方向のバス２４は８のグループに分けられ、それぞれ８のバスを含むＨ−バス２４がＰＥの横方向の行（ライン）に沿って配置されている。Ｖ−バス２３ｘおよび２３ｙには、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２５がそれぞれのＰＥに対応して設けられており、それぞれのＰＥに対してデータの入力を可能としている。
【００５７】
Ｈ−バス２４には、Ｈ−バス２４とＶ−バス２３ｘおよび２３ｙのそれぞれの交差に対応して、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２６が設けられている。したがって、１つのＨ−バス２４から１つのデータセットを、そのＨ−バス２４と交差している１つのＶ−バス２３ｘまたは２３ｙに出力できる。逆も可能である。Ｈ−バス２４に含まれるバスのそれぞれには、そのラインのＰＥｓの出力が接続される。したがって、Ｖ−バス２３ｘおよび２３ｙと、Ｈ−バス２４とを介することにより、セグメントＳに含まれるＰＥｓを接続できる。これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４の接続は、コンフィグレーションデータ１８に含まれる接続情報により制御できる。そして、これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により実現できる接続パターンは膨大であり、基本的には、セグメントＳに含まれる全てのＰＥをフレキシブルに接続できる。したがって、コンフィグレーションデータ１８により、ＰＥｓの接続を、配線資源により制限は受けるとしても、基本的には、自由自在に制御できる。
【００５８】
これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により接続できる範囲、すなわち、各セグメントＳ０〜Ｓ５内のＰＥの間では１サイクル（１クロック）以内にデータを送受信できる。したがって、タイミング的には、例えば、セグメントＳ０に含まれるＰＥｓは、いずれも等価である。このため、同一セグメント内であれば、回路を構成するために、いずれのＰＥを選択して機能を割り付けても、タイミングの検討は不要であり、タイミング的には、セグメント内のＰＥｓを用いて、所定の回路を自由に配置および配線できる。
【００５９】
図７に、第２レベルのルーティングマトリクス２２の構成を示している。図７では、第２レベルのルーティングマトリクス２２により、隣接するセグメントＳ１およびＳ４にそれぞれ含まれている接続用のエレメントＤＬＨを接続している。それぞれのＤＬＨは、それぞれのセグメントＳ１およびＳ４の内部の第１レベルのルーティングマトリクス２１に接続している。したがって、セグメントＳ１に含まれるＰＥと、セグメントＳ４に含まれるＰＥとを第２レベルのルーティングマトリクス２２を介して接続することができる。接続用のディレイエレメントＤＬＨは、第１レベルのルーティングマトリクス２１に含まれるバスのインターフェイスとして機能する。セグメント間の接続も、したがって、ＤＬＨなどのセグメント内における接続用のエレメントと他のＰＥとの接続および接続用エレメントの機能を、コンフィグレーションデータ１８の接続情報および／または機能情報により制御できる。したがって、ＰＥマトリクス１０に含まれるすべてのＰＥｓの接続および機能を、マトリクス１０の全体としても、マトリクス１０の部分に限定的にも、コンフィグレーションデータ１８により制御することができる。
【００６０】
メタヒューリスティクスな方法により生成される発見的なコンフィグレーションデータ（ヒューリスティックに生成されたコンフィグレーションデータ、ヒューリスティックなコンフィグレーションデータ）およびそれによりＰＥマトリクス１０に再構成される回路は、回路から出力される結果が、その処理により得ようとする目的に合致したもの、あるいは目的に合致している確率が高そうなものであれば、意味（たとえば、物理的な内容、統計学的な意味、その他の学術的な意味）が無い、意味が不明または意味を解析するために時間を要するものであっても良い。しかしながら、以下では、説明を簡単にするために、発見的なコンフィグレーションが、評価対象回路として、以下のような適当または任意の多項式を演算するための回路を再構成する場合を想定する。
【００６１】
Σｆｉ（ｘ１，ｘ２・・ｘｎ−１，ｘｎ）＝Ｆｏｕｔ ・・・（１）
上記式（１）において、ｉは１〜ｎまでの整数であり、式（１）の多項式の部分が、変数ｘｉにより与えられる何らかの事象（システム、現象）に対する解に相当する。したがって、以下では、遺伝的アルゴリズムにより、最適解を示す多項式の部分を探索する。そのため、多項式が、遺伝子、すなわち、発見的なコンフィグレーション（遺伝子的コンフィグレーションデータ、遺伝子対応のコンフィグレーションデータ）として生成され、その発見的なコンフィグレーションを、再構成ユニットであるＰＥマトリクス１０にその発見的なコンフィグレーションにより再構成された評価対象回路により評価する。発見的なコンフィグレーションの生成方法によるが、生成された発見的なコンフィグレーションによりＰＥマトリクス１０に再構成される評価対象回路のうち、式（１）として意味のあるものが評価されるということも可能である。さらには、生成された発見的なコンフィグレーションによりＰＥマトリクス１０に再構成される評価対象回路を、式（１）が実装されていると想定して評価するということも可能である。
【００６２】
式（１）の出力Ｆｏｕｔは、評価対象回路の出力に相当する。出力Ｆｏｕｔを得るために、学習データ、教師データなどと称される変数ｘｉの複数セットをサンプルとして入力する。学習データには、変数ｘｉのセットと、そのセット（学習データセット）により得られたい結果とが含まれており、出力Ｆｏｕｔと、結果とを比較することにより、その学習データセットに対する評価対象回路の可否が判断される。そして、複数の学習データセットに対して、良好な結果が得られた発見的なコンフィグレーションを親として、次世代の発見的なコンフィグレーションが生成される。
【００６３】
図８に、コンフィグレーションデータ１８の一例を示している。コンフィグレーションデータ１８は、各ＰＥの機能を記述している機能情報セクション１８ａと、バスセレクタ２５および２６の接続情報を記述している接続情報セクション１８ｂとを含む。セクション１８ａには、各ＰＥを特定するための識別情報（アドレス）１８ｃと、機能の設定内容１８ｄとが含まれている。セクション１８ｂには、バスセレクタ２５および２６を特定するための識別情報（アドレス）１８ｅと、接続の内容１８ｆとが含まれている。以下の例では、同じフォーマットのコンフィグレーションデータ１８であって、含まれている機能情報１８ａおよび／または接続情報１８ｂが異なる複数のデータがヒューリスティックな方法、具体的には、遺伝的アルゴリズムにより、発見的なコンフィグレーションデータ（以降では遺伝子的コンフィグレーションデータあるいは遺伝子対応コンフィグレーションデータ、ＧＣＤ）７１が世代単位で、遺伝子対応コンフィグレーションデータ（ＧＣＤ）のグループあるいはセット７０として生成される。ＧＣＤ７１は、ヒューリスティックに生成される情報を含めばよく、ＰＥマトリクス１０全体がヒューリスティックな情報により再構成される必要はない。ＰＥマトリクス１０に実装（再構成）される回路のうち、評価対象回路に相当する部分の全てまたは一部を再構成するための情報がヒューリスティックな情報であればよい。この明細書において、ヒューリスティックなデータまたは情報とは、少なくとも１部が、ヒューリスティクス（メタヒューリスティクス）な方法により生成されたものを示す。
【００６４】
図９は、本発明の実施形態の一例のデータ処理装置のブロック図である。このデータ処理装置５０は、ＤＡＰＤＮＡ１を用いて実現されている。データ処理装置５０は、再構成ユニット（再構成領域）であるＰＥマトリクス１０を有する。このＰＥマトリクス１０は、上述したように、回路を構成するための複数のエレメント（ＰＥ）と、これらＰＥを接続するための内部配線２０とを含み、内部配線２０による複数のＰＥの接続および／またはＰＥｓのそれぞれの機能を変更することにより、当該再構成ユニット１０に含まれる回路を再構成可能である。さらに、データ処理装置５０は、複数のＰＥの接続情報１８ｂおよび各ＰＥの機能情報１８ａを含む再構成情報（コンフィグレーションデータ）１８を用いて、ＰＥマトリクス１０に回路を再構成する再構成制御ユニット２ａを有する。この例では、再構成制御ユニット２ａとしての機能はＤＡＰ２により提供され、再構成制御ユニット２ａにより回路を再構成するために用いられるコンフィグレーションデータ１８はＧＣＤ７１を含む。
【００６５】
このデータ処理装置５０では、再構成制御ユニット２ａが、コンフィグレーションメモリ１９にＧＣＤ７１をセットし、ＰＥマトリクス１０の一部を用いて、評価対象回路６１を構成する。さらに、再構成制御ユニット２ａは、ＧＣＤ７１とは異なるコンフィグレーションデータ１８をコンフィグレーションメモリ１９にセットし、ＰＥマトリクス１０の残りの部分を用いて、評価対象回路６１を評価するためにサンプルデータ（学習データ）７６を供給するための回路（サンプルデータ供給回路）６２と、評価対象回路６１の出力（この例ではＦｏｕｔ）の評価を行い評価値７８、たとえば出力Ｆｏｕｔの正解率を演算するための回路（評価回路）６３とを構成する。
【００６６】
図１０（ａ）は、ＧＣＤ７１のある世代の群（グループ）７０の一例である。たとえば、１世代の遺伝子データの群７０は、１０００個の遺伝子データ７１を含み、それぞれの遺伝子データはＧＣＤ７１を示している。
【００６７】
図１０（ｂ）は、学習データ７６の一例である。学習データ７６は、１０００個のデータセット７５を含み、それぞれのデータセット７５は、多項式（１）の変数ｘ１〜ｘ５０と、それらの変数により計算される予定の値（予定値）Ｔｓとを含む。学習データ７６は、サンプルデータ供給回路６２により、各々のＧＣＤ７１によりＰＥマトリクス１０に再構成される評価対象回路６１に供給される。これら１０００個のデータセット７５による出力値は、評価回路６３により予定値Ｔｓと比較され、正解率が演算される。図１０（ｃ）に、遺伝子（ＧＣＤ）７１毎の正解率が評価値７８として出力された状態を示している。
【００６８】
図９に示すように、データ処理装置５０は、次世代の遺伝子、すなわち次世代のＧＣＤの群７２を生成するユニット（生成ユニット）２ｂを有する。この例では、生成ユニット２ｂとしての機能はＤＡＰ２により提供される。生成ユニット２ｂは、遺伝的アルゴリズムにより、現世代のＧＣＤ群（遺伝子群）７０から次世代のＧＣＤ群（遺伝子群）７２を生成し、現世代のＧＣＤ群７０を次世代のＧＣＤ群７２により置き換え、再構成制御ユニット２ａが使用できるようにする。より具体的には、生成ユニット２ｂは、評価値７８により、現世代のＧＣＤ７０のそれぞれのＧＣＤ７１の適応度を判断する。そして、ある確率で選択（淘汰、再生）し、交叉、突然変異、コピーを含む遺伝的操作を行い、次世代のＧＣＤ群７２を生成する。選択方法は、ルーレット選択、ランキング選択、トーナメント選択などが知られている。交叉方法は、一点交叉、二点交叉、多点交叉、一様交叉などが知られている。次世代のＧＣＤ群７２は、最適解のＧＣＤ７１ができるだけ早く探索されるように生成することが好ましく、具体的な遺伝子操作の方法は、解を得ようとするシステムの特性などによって選択することができる。
【００６９】
図１１に、あるＧＣＤ７１を含むコンフィグレーションデータ１８によりＰＥマトリクス１０に回路が再構成された状態を示している。この例では、ＧＣＤ７１によりＰＥマトリクス１０に再構成された評価対象回路６１は、４つの演算ブロック６５ａ〜６５ｄを含む。それぞれの演算ブロック６５ａ〜６５ｄに対して、ＰＥマトリクス１０に構成されたサンプル供給ユニット６２は、学習データ７６を並列に供給する。評価対象回路６１の出力は評価回路６３において評価される。サンプル供給回路６２が、たとえば、学習データ７６の１つのセット７５の最後を示すデータを評価対象回路６１に入力し、評価回路６３では、最終のデータがすべての演算ブロック６５ａ〜６５ｄから出力されたことを判定閾値で判定する。そして、そのタイミングで得られた評価対象回路６１の出力を、学習データセット７５に含まれている正解Ｔｓと比較する。学習データ７６に含まれる１０００個の学習データセット７５に対して、評価対象回路６１の出力と正解Ｔｓとを比較することにより、評価値として正解率７８を出力することができる。
【００７０】
図１２に、演算ブロック６５ａの一例を示している。この演算ブロック６５ａに含まれる回路は、ＡＬＵ、セレクタ、ラッチ、ＲＡＭとしての機能を有する各ＰＥの機能を変更するだけで多種多様な多項式を表現することができる構成を備えた回路の一例である。この演算ブロック６５ａの構成を採用することにより、たとえば、ＰＥの１タイプであるＲＡＭエレメントにより、図５に示したようにルックアップテーブル（ＬＵＴ）としての機能を実現でき、三角関数あるいは他の算術関数を含む多項式であっても実装できる。また、図４に示したように、ＰＥの１タイプであるＥＸエレメントは、２入力のＡＬＵとしての機能を備えており、一方の入力を無効にしたり、イミディエイトを代入することなどにより、ＰＥの機能を変更するだけで実質的にＰＥ間の接続も変更することができる。
【００７１】
したがって、生成ユニット２ｂは、現世代のＧＣＤ７１に含まれる複数のＰＥの機能を規定するパラメータ（機能情報）１８ｄを遺伝的アルゴリズムにより更新し、次世代のＧＣＤ群７２を生成する機能を含むことにより、多種多様な遺伝子に対応するＧＣＤを生成することができる。また、コンフィグレーションデータの機能情報１８ｄを更新することにより次世代のＧＣＤ群７２を生成する方法を採用すると、コンフィグレーションデータ１８の接続情報１８ｆは保存される。したがって、現世代のＧＣＤ７１により再構成される評価対象回路６１が、入力から出力までデータフローを形成するように複数のＰＥを接続する接続情報１８ｆを備えていれば、その特性は次世代のＧＣＤ群７２に引き継がれる。
【００７２】
このため、入力から出力まで、すなわち、サンプル供給回路６２から評価回路６３に到達するようなデータフローを形成する接続情報１８ｆを備えた複数のコンフィグレーションデータ（テンプレートコンフィグレーションデータ）７４をテンプレート群７３として用意しておくことは有用である。生成ユニット２ｂは、テンプレート群７３に含まれるコンフィグレーションデータを現世代として、次世代のＧＣＤ群７２を生成することができ、データフローを形成する特性を備えたＧＣＤ７１により評価対象回路６１を再構成できる。したがって、評価回路６３に出力がでないような評価に値しない回路が構成される可能性を低減でき、最適な解、すなわち、最適なＧＣＤに到達する速度を向上できる。
【００７３】
また、図１２に示した回路は、入力される学習データセット７５に含まれる複数の変数ｘｉをパイプライン処理することができる構成である。特に、このデータ処理装置５０に採用されている動的再構成デバイスのＤＡＰＤＮＡにおいては、ＰＥマトリクス１０に含まれる各ＰＥがクロックで同期した処理を行う。このため、連続パイプライン処理を行うデータフロー（データパス）をＰＥマトリクス１０に再構成することができる。
【００７４】
したがって、評価対象回路６１でパイプライン処理を行うことにより、複数の学習データセット７５を連続して、あるいは、演算結果Ｆｏｕｔが収束するために要する若干のクロック（サイクル、インターバル）を開けて連続供給することが可能である。その結果、学習データセット７５の入力に要する時間程度の間隔で評価対象回路６１の出力Ｆｏｕｔを評価回路６３に出力することができる。たとえば、学習データセット７５に含まれる変数を並列に１クロックで入力できるような評価対象回路６１であれば、理想的には１クロック毎に出力Ｆｏｕｔを得ることができる。このため、それぞれのＧＣＤ７１の評価に要する時間を大幅に短縮できる。パイプライン処理を行う回路構成も、たとえば、コンフィグレーションデータの接続情報１８ｆを保持することで、次世代のＧＣＤ７１に伝えることができる。また、テンプレートコンフィグレーションデータ７４も、パイプライン処理を行う回路構成であることが望ましい。また、サンプル供給回路６２は、パイプライン処理が行われることを前提として学習データセット７５を供給することも有効である。パイプライン処理が行われないような評価対象回路６１は、高い評価値を得られないので、パイプライン処理が行われる特性を備えた回路を構成するＧＣＤ７１を選択的に残し、次世代へ繋ぐことが可能となる。
【００７５】
本明細書において、パイプライン処理は、「毎クロック連続してデータ処理を行う」処理を示す。本例の再構成デバイス１は、ＤＮＡというデータフロー型のハードウエアで回路構成をとっており、データをロードするエレメント（ＬＤＢ）により強制的にデータをロードするかぎり必ずパイプライン処理となる。逆にパイプライン処理しない構成をとるためには、アドレス出力用のエレメント（Ｃ１６Ｌ、Ｃ３２Ｌ）およびロードエレメントＬＤＢといった、ＤＲＡＭ６からの処理対象データのロードを制御する機構のパラメータを変更する必要がある。これらのパラメータも、ＧＣＤ７１の遺伝子情報の一部に加えることにより、ＧＣＤ７１によっては「パイプライン処理をしない」という現象を起こすことが可能である。したがって、「非パイプライン処理」があらかじめ劣っているとわかっているのならば、ＧＣＤ７１の遺伝子情報を限定して必ずパイプライン処理になるようにすることが可能である。すなわち、具体的には、特定のエレメント（たとえば、ＬＤＢ、Ｃ１６Ｌ、Ｃ３２Ｌ等）のパラメータは固定にしておく。
【００７６】
また、本例の再構成デバイス１においては、パイプライン処理には、非フィードバック処理のみならず、フィードバック処理を含めることが可能である。フィードバック処理を含めてパイプライン処理する場合は、たとえば、データをＲＡＭエレメントなどにより提供されるＦＦ機能上に蓄積することが要求される。ＲＡＭエレメントおよびその他のエレメントにおいてＦＦ機能が提供されるような初期値も、ＧＣＤ７１の遺伝子情報とすることが可能である。フィードバック処理を含めることにより、ＧＣＤ７１により表現できる回路構成が爆発的に広がる。たとえば、ＦＩＲフィルタに対して、フィードバック付き小規模ＨＷで大規模なフィルタを構成できるＩＩＲフィルタを例として挙げることができる。したがって、フィードバック処理を含むＧＣＤ７１は、このタイプのＧＡＧＰで探索する解の好ましい一例である。
【００７７】
選択的に次世代のＧＣＤ群７０に引き継ぐ特性は上記に限定されない。テンプレート群７３に含まれるテンプレートコンフィグレーションデータ７４を、解を求めようとしているシステム、本例であれば変数ｘｉにより与えられるシステムに固有の条件を反映するように生成し、生成ユニット２ｂは、テンプレートコンフィグレーションデータ７４の固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代のＧＣＤ群７２を生成する機能を含むことが望ましい。コンフィグレーションデータ１８によりＰＥマトリクス１０に構成可能な多様性に富んだ回路と、解を求めようとするシステムの特性との融合を図ることができる。このため、データ処理装置５０により、引用文献１〜１７に示されているような多種多様な用途に対し、メタヒューリスティクスな方法により、典型的には遺伝的アルゴリズム（遺伝的プログラム）により最適解を探索するシステムを提供できる。
【００７８】
テンプレートコンフィグレーションデータ（遺伝子テンプレート）７４による記述を採用することは、次のことを含む。予め単一のＤＮＡコンフィギュレーションにより遺伝子テンプレートを記述し、複数（数個〜数１０個）のＤＮＡコンフィギュレーションを予め用意する。これにより、多様な遺伝子に対応することが可能となる。また、遺伝子テンプレートのパラメータのみを更新することにより無数の遺伝子式を表現することが可能となる。また、複数のテンプレートの中から、テンプレートを選択することにより多様な遺伝子を表現することが可能となる。また、演算器（ＰＥ）を最大限活用し、シストリックアレイ型の多種多様な演算を実現することも可能となる。さらに、１つの遺伝子に対して全学習データを連続してパイプライン処理し、結果（正解数）を短時間で出力することも可能となる。
【００７９】
図１３ないし図１５に、動的再構成デバイス１を用いたデータ処理装置５０により、解を探索する方法の一例を示している。これらの図においては、ＧＣＤを遺伝子と表示し、遺伝的とＧＣＤとの対応関係を示している。
【００８０】
図１３に示す方法８１は、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、生成された次世代のＧＣＤ群７２を現世代の遺伝子に相当するＧＣＤ群７０と置き換えて、その世代のＧＣＤ群７０を評価するステップ８６とを有する。最初のＧＣＤ群を生成するステップ８５では、データ処理装置５０の生成ユニット２ｂが、テンプレート群７３に含まれるテンプレートコンフィグレーションデータ７４を個体としてランダムに選択し、それらの個体から第１世代のＧＣＤ群７０を生成する。
【００８１】
次に、ステップ８６において、再構成制御ユニット２ａは、第１世代のＧＣＤ群７０に含まれるそれぞれのＧＣＤ７１を含むコンフィグレーションデータ１８をコンフィグレーションメモリ１９にセットし、ＰＥマトリクス１０に評価対象回路６１を再構成する。サンプル供給回路６２は、評価対象回路６１に学習データ７６を供給し、評価回路６３により評価値を得る。それぞれのＧＣＤ７１に対応する評価対象回路６１を評価し、第１世代のＧＣＤ群７０に含まれるすべてのＧＣＤ７１の評価が終了すると、ステップ８５に戻って、次世代のＧＣＤ群７２を生成する。
【００８２】
ステップ８５において、生成ユニット２ｂは、現世代（第１世代）のＧＣＤ群７０と、評価データ７８とに基づき、遺伝的アルゴリズムにより次世代（第２世代）のＧＣＤ群７２を生成し、現世代のＧＣＤ群７０と置き換える。ステップ８６において、再構成制御ユニット２ａは、第１世代のＧＣＤに基づきヒューリスティックに生成された第２世代のＧＣＤ群を評価する。
【００８３】
このステップ８６において、さらに具体的には、再構成制御ユニット２ａは、ステップ８７ａにおいて、個々の第２世代のＧＣＤ７１を用いて、ＰＥマトリクス１０に評価対象回路６１を再構成し、ステップ８７ｂにおいて、評価対象回路６１を評価する。このデータ処理装置５０においては、ＰＥマトリクス１０に、典型的には１クロックで回路をダイナミックに再構成することができる。したがって、個々のＧＣＤ７１を評価するのに要する時間のほとんどすべては、評価対象回路６１を評価するための時間となる。
【００８４】
ステップ８７ｂはステップ８８および８９を含む。ステップ８８において、サンプルデータ供給ユニット６２により学習データ７６の各学習データセット７５を評価対象回路６１に供給する。ステップ８８においては、学習データ７６の学習データセット７５に含まれる変数ｘｉが次々とロードされ、評価対象回路６１に供給される。さらに、ステップ８９において、評価対象回路６１が学習データセット７５の演算を終了するのを待って、評価対象回路６１に出力により、評価回路６３が評価対象回路６１を評価する。
【００８５】
図１３に示すように、１つのＧＣＤ７１を評価するために、１００００セットの学習データ７５を供給し、その学習データ７５の演算を待って評価する必要がある。さらに、１世代のＧＣＤ群７０の評価を終了するためには、１０００個のＧＣＤ７１に対して同様の処理を行う必要がある。そして、１００世代のＧＣＤ群７０の評価を繰り返すことにより、ステップ９０において、適切なＧＣＤ７１を、最適解として得ることができる。学習データセット７５の数、一世代に含まれる遺伝子総数（ＧＣＤの総数）、評価世代数は例示に過ぎず、多くても、少なくても良い。メタヒューリスティクスな解法としては、それぞれの数が多い方が、より最適な解が求められることが多い。このケースでは、変数ｘｉ（たとえば、ｉは１〜５０）により与えられる事象に関する最適解を得るために、学習データセット７５による評価（ステップ８８および８９）を１０9回繰り返す。データ処理装置５０においては、ステップ８８および８９を、ＧＣＤ７１により再構成された専用回路（評価対象回路）６１により実行する。したがって、ＣＰＵなどの汎用の回路を用いて、プログラムポインタにしたがってロードを繰り返すソフトウェアプログラムを用いて演算を繰り返すケースと比較し、大幅に最適解を得るまで時間を短縮できる。このため、より多くの学習データセット、遺伝子総数、評価世代数により解を得ることが可能となり、より最適な解を得ることが可能となる。
【００８６】
図１４に示す方法８２も、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、次世代のＧＣＤ群７２を現世代のＧＣＤ群７０と置き換えて、その世代のＧＣＤ群７０を評価するステップ８６とを有する。さらに、ステップ８６のうち、評価対象回路６１を評価するステップ８７ｂにおいて、このデータ処理装置５０は、学習データ７６の各学習データセット７５を評価対象回路６１に供給するステップ８８と、評価対象回路６１が学習データセット７５の演算を終了するのを待って評価回路６３が評価対象回路６１を評価するステップ８９とを、ＤＮＡデバイス１の特性を活かして連続パイプライン処理する。すなわち、評価対象回路６１における演算終了を待たずに、評価対象回路６１の出力に影響を与えない範囲で連続して複数の学習データセット７５を、サンプルデータ供給回路６２により評価対象回路６１に供給する。
【００８７】
それぞれのＧＣＤ７１を評価するステップ８７ｂをパイプライン処理することにより、ステップ８７ｂの処理時間を大幅に短縮できる。上述したように、このケースでは、最適解を得るために、学習データセット７５による評価ステップ８７ｂ（ステップ８８および８９）を１０9回繰り返す。したがって、評価ステップ８７ｂの一回の処理時間の削減効果は、ステップ９０において最適解を得るまでの処理時間に１０9のオーダで反映され、解探索に要する処理時間を大幅に短縮できる。
【００８８】
さらに、それぞれの学習データセット７５を評価対象回路６１に供給するために要する時間を短縮することによりステップ８７ｂの処理時間をさらに短縮できる。たとえば、学習データセット７５に含まれる複数の変数ｘｉがパラレルに入力できるように、サンプルデータ供給回路６２および／または評価対象回路６１を構成することにより、評価対象回路６１から、ほぼ連続して、１クロックまたは数クロック単位で出力を評価回路６３に供給できる。さらに、パイプライン処理を行うことにより、評価対象回路６１の演算時間（処理時間）が、評価するステップ８７ｂに要する時間（評価時間）に与える影響を緩和できる。遺伝子に対応するＧＣＤ７１により再構成される評価対象回路６１としては、できるだけ任意で、できるだけ複雑な回路が構成できることが望ましい。多数のＰＥを含む評価対象回路６１は、処理時間は長くなる。しかしながら、パイプライン処理を採用することにより、個々の評価対象回路６１の処理時間が長くなることは、入力データを供給してから出力が得られるまでのレイテンシが長くなることに影響するだけであり、多数の学習データセット７５の評価間隔には影響を与えない。したがって、このデータ処理装置５０により、複雑な構成の遺伝子に対応するＧＣＤ７１を採用でき、短時間で最適な解を探索できる。
【００８９】
図１５に示す方法８３も、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、生成されたＧＣＤ群７２を現世代のＧＣＤ群７０として評価するステップ８６とを有する。さらに、ある世代のＧＣＤ群７０を評価するステップ８６において、ＧＣＤ群７０に含まれる複数のＧＣＤ７１により複数の評価対象回路６１をＰＥマトリクス１０に再構成し、それら複数の評価対象回路６１を並列に評価する。したがって、各世代のＧＣＤ群７０の評価に要する処理時間を数分の一に短縮することができ、最適解の探索に要する処理時間をさらに短縮できる。図１５に示すパラレル処理により処理時間を短縮する方法８３は、図１４に示したパイプライン処理により処理時間を短縮する方法８２とともに適用することが可能であり、最適解の探索に要する処理時間をさらに短縮できる。
【００９０】
データ処理装置５０に採用されている動的再構成デバイス（ＤＡＰＤＮＡ）１は、ＰＥマトリクス１０の一部だけであっても、動的に回路を再構成することができる。したがって、複数のＧＣＤ７１により複数の評価対象回路６１を再構成する場合も、それら複数の評価対象回路６１を同期して再構成する必要はなく、それぞれの評価対象回路６１の評価に要する時間に応じて、随時、ＰＥマトリクス１０の空いた領域に評価対象回路６１を再構成し、評価することができる。
【００９１】
上記に加え、解を得ようとする事象あるいはシステムの探索に適したテンプレートコンフィグレーション群７３を予め用意し、そのテンプレートコンフィグレーション群７３を初世代として次世代のＧＣＤ群７２を生成することは、短時間に最適な解を得るために有用な１つの方法である。そのようなテンプレートコンフィグレーション７４は、上記と同様に、データ処理装置５０により探索することができる。また、テンプレートコンフィグレーション群７３により探索された解のＧＣＤ７１をテンプレートコンフィグレーション群７３に加えたり、学習データ７６に、探索された解のＧＣＤ７１の適用により得られたデータを加えたりすることは可能である。したがって、探索された解に基づいて、さらにシステムに適した解を再探索したり、変化する事象あるいはシステムに対して最適な解を探索して自律的に適応するような装置を提供することが可能である。
【００９２】
さらに、このデータ処理装置５０は、探索された解、すなわち、探索された最適のＧＣＤ７１を用いて、事象あるいはシステムの入力データに対して出力データを生成し、出力するデータ処理装置としても機能する。したがって、このデータ処理装置５０により探索された解（ＧＣＤ）７０を、同じタイプのデータ処理装置５０に実装することにより、その解（ＧＣＤ）を簡単に利用することができる。また、その解（ＧＣＤ）を同じタイプのデータ処理装置５０に適用するために、その解（ＧＣＤ）の意味あるいはその解の物理的な意義を解釈したり、シミュレーションなどにより求めたりする必要はない。また、データ処理装置５０により得られた解をシミュレーションなどにより分析し、他の装置の制御のために用いることも可能である。
【００９３】
なお、上記では、遺伝的アルゴリズム（ＧＡ）をもとに、メタヒューリスティクスにコンフィグレーションデータを生成する例を説明しているが、メタヒューリスティクスにコンフィグレーションデータを生成する方法は、遺伝的アルゴリズムに限らず、遺伝的アルゴリズムの拡張の１つである免疫的アルゴリズム、さらには、シミュレーテッドアニーリング法などの他のメタヒューリスティクスな最適化手法であっても良い。
【００９４】
また、これらのメタヒューリスティクスな方法により生成されるコンフィグレーションデータによりＰＥマトリクスに再構成可能な回路は、回路として表現できる機能であれば、基本的にどのような機能であっても含めることが可能であり、上述した多項式に限らず、ツリー構造により機能が示される事象（アプリケーション）、その他の構造により機能が示される事象（アプリケーション）、たとえば、引用文献１〜１７に示した用途（技術）に対しても上記のデータ処理装置および解探索方法を適用できる。
【図面の簡単な説明】
【００９５】
【図１】図１（ａ）は、再構成可能なデバイスの一例の概略構成を示し、図１（ｂ）は、ＰＥマトリクスの概略を示し、図１（ｃ）および図１（ｄ）は、ＰＥマトリクスを動的に再構成する様子を示す。
【図２】ＰＥマトリクスの配列を示す図。
【図３】ＰＥマトリクスに配置されたＰＥのタイプを示す図。
【図４】ＰＥの１つのタイプのＥＸＭの構成を示すブロック図。
【図５】ＰＥの１つのタイプのＲＡＭの構成を示すブロック図。
【図６】セグメント内の配線（イントラセグメント配線）を示す図。
【図７】セグメント間の配線（インターセグメント配線）を示す図。
【図８】コンフィグレーションデータのフォーマットの一例を示す図。
【図９】再構成可能な領域を含むデータ処理装置の一例を示すブロック図。
【図１０】図１０（ａ）はコフィグレーションデータ（遺伝子データ）、図１０（ｂ）は学習データ、および図１０（ｃ）は評価データ（正解率）の例を示す。
【図１１】評価対象回路の一例を示すブロック図。
【図１２】演算ブロックの一例を示すブロック図。
【図１３】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【図１４】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【図１５】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【符号の説明】
【００９６】
１ 再構成可能なデバイス
２ａ 再構成制御ユニット、 ２ｂ 生成ユニット
１０ ＰＥマトリクス（再構成ユニット）
５０ データ処理装置
７０、７２、７４ 遺伝的アルゴリズムで生成されたコンフィグレーションデータ（ＧＣＤ）群
【技術分野】
【０００１】
本発明は、回路を再構成可能なユニットを用いた解探索方法およびデータ処理装置に関するものである。
【背景技術】
【０００２】
特許文献１には、生物の進化の過程を模倣した最適化手法の１つである遺伝的アルゴリズム（ＧＡ：Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ）をもとに考案された遺伝的プログラミング（ＧＰ：Ｇｅｎｅｔｉｃ Ｐｒｏｇｒａｍｍｉｎｇ）を画像処理に適用したツリー構造状画像変換自動作成方法を印刷物の文字列抽出方法に用いることが記載されている。
【０００３】
特許文献２には、解探索装置及びその初期値設定方法について開示されている。この方法は、数値計算によって物理化学現象をシミュレーションするソフトウェアに組み込まれた物理化学モデルが用いる複数のパラメータの値が、測定結果の様に外部から与えられたデータとの誤差を最小となる様に、遺伝的アルゴリズムを用いて自動的に探索する計算方法に関するものである。さらに、具体的には、この解探索装置、例えば、半導体回路シミュレータが内蔵するトランジスタモデルが持つ複数のパラメータを実測した電流電圧データ（Ｉ−Ｖデータ）の誤差が小さくなる様に合せ込んだり、半導体プロセスシミュレータが内蔵するイオン注入モデルが持つ複数のパラメータをＳＩＭＳ測定した結果に合せ込んだりして、これらのシミュレータと実測結果の食い違いを抑制する事で、これらのシミュレータの予測性を高める為に用いられるものである。
【０００４】
特許文献３には、コジェネレーションシステムの最適化方法および設備提案システムが記載されている。この最適化方法では，機器構成の最適化と運転パターンの最適化とを交互に繰り返す。そして，機器構成の最適化の際，機器と運転パターンとを１組の機器情報データとし，その機器情報データを基本単位として遺伝子操作中の交叉を行う。また，運転パターンの最適化の際、機器構成を固定し、その機器構成での運転パターンについて遺伝子操作を行う。そして，最適化された機器構成および運転パターンでの評価値を判定する。判定条件を満たしていない場合には，判定条件を満たすまで上記処理を繰り返すことが記載されている。
【０００５】
特許文献４には、画像処理方法として、誤差拡散処理の目標としての２値画像であるターゲット画像を、遺伝的アルゴリズムに基づいて生成しておくことが記載されている。そして、均一輝度画像に対して誤差拡散パラメータを用いた誤差拡散処理を施すことによって比較画像を生成し、該比較画像と前記ターゲット画像の画質の差を評価する画質評価関数を設定し、この画質評価関数による評価値が最小となるように、誤差拡散パラメータを最適化する。
【０００６】
特許文献５には、情報処理機構を用いて運転指向を推定する場合、遺伝的アルゴリズムを用いた情報処理機構で、計算負荷の増加を抑制できる運転指向推定装置を提供することが記載されている。運転指向推定装置は、運転指向によって変化する可能性のある運転操作量を検出する運転操作量検出部と、車両の走行環境に基づいて、前記検出された運転操作量を補正する運転操作量補正部とを備え、補正された運転操作量に基づいて、情報処理機構を用いて運転指向を推定する。走行環境には、道路の勾配及び路面の滑り易さの少なくともいずれか一方が含まれることができる。運転操作量には、アクセル開度、アクセル開度変化量、及びブレーキ踏力の少なくともいずれか一つが含まれることができる。
【０００７】
特許文献６には、計算機を用いて所望の物性値条件を満たす高分子の構造を求める高分子材料設計方法であって、高分子モデルの作成条件および物性値条件を入力するステップと、この作成条件の下でモノマーに基づく構成単位を高分子の設計単位とし、この設計単位を遺伝子として遺伝的アルゴリズムの個体となる高分子モデルを作成するステップと、作成された高分子モデルについて物性値を計算し、前記物性値条件に対する適合度を計算するステップとを有する。そして、遺伝的アルゴリズムを用いて、次世代以降の個体の作成および適合度計算のステップを繰り返し、適合度の大きい高分子の構造を探索することを特徴とする方法が記載されている。
【０００８】
特許文献７には、ロボットの行動学習に有利なセンサの形態を自動的に設計することができるセンサ設計装置が記載されている。初期世代作成部は、センサの形態を特定するための複数の遺伝子型を作成し、各遺伝子型により特定されるセンサの形態を有する複数のロボットを仮想的に作成し、行動学習部は、複数のロボットに仮想的に学習を行わせ、学習結果を基に各ロボットの適応度を算出し、選択部は、各ロボットの適応度を基に親個体となる複数のロボットを選択し、次世代作成部は、選択されたロボットの遺伝子型から遺伝的アルゴリズムに基づき次世代の遺伝子型を作成し、各次世代の遺伝子型により特定されるセンサの形態を有する複数のロボットを仮想的に作成し、行動学習部は、次世代の複数のロボットに仮想的に再度学習を行わせ、選択部、次世代作成部及び行動学習部による処理を所定世代繰り返してセンサの形態を決定することが記載されている。
【０００９】
特許文献８には、２次元以上の空間に複数の要素を最適な状態で配置する要素配置最適化問題において、問題規模の大きい要素配置最適化問題を高速に処理できるようにすることが記載されている。複数の要素の初期配置状態に関する情報がコンピュータに入力されると、遺伝的アルゴリズムをＣＰＵで実行して、初期配置状態にある複数の要素の疎密を解消する第１アルゴリズム実行ステップと、第１アルゴリズム実行ステップにて疎密が解消された後の複数の要素の中間配置状態に関する情報がコンピュータに入力されると、局所的疎密解消アルゴリズムをＣＰＵで実行して、中間配置状態にある複数の要素の疎密を更に解消する第２アルゴリズム実行ステップとを実行することにより、接続関係を維持しながら初期配置状態にある複数の要素の疎密を解消することが記載されている。
【００１０】
特許文献９には、通信システムに応用されるシーケンスの生成方法が記載されている。この方法は、長さの予め設定された複数のシーケンスをランダムに生成するステップ（１）と、各シーケンスの特定のパラメータ値を計算するステップ（２）と、計算により得られた特定のパラメータ値が一定の条件を満たす複数のシーケンスを選択するステップ（３）と、以上の処理により得られたシーケンスに対して適応遺伝変異を行い、適応確率により変異後特定のパラメータ値が最適になったシーケンスを選択するステップ（４）と、予め決めた回数までステップ（２）から（４）を繰り返し、最後に得られた複数のシーケンスから、特定のパラメータ値が最適なシーケンスを選択して出力シーケンスとするステップ（５）とを含む。
【００１１】
特許文献１０には、テンプレート画像を含む画像の検索を高速に高い精度で行うことが記載されている。領域選択受付部からの画像の領域の選択に基づいてテンプレート画像生成部はテンプレート画像を生成する。このテンプレート画像および検索対象になるターゲット画像は、画像縮小部において所定の縮小率に縮小される。個体抽出部において生成されたターゲット画像とテンプレート画像とを照合する領域の情報を有する染色体の適応度が、ターゲット画像準備値テーブルおよびテンプレート画像準備値テーブルに保持された準備値を用いて適応度算出部において算出された後、遺伝的アルゴリズム処理部で選択、交配および突然変異が行われる。以上の処理を所定世代数繰り返した後に、準最適解に対応する適応値が所定の閾値を超えているか否かが類似画像判断部で判断されることが記載されている。
【００１２】
特許文献１１には、周期的に配置されてなるマイクロレンズアレイの形状測定方法が記載されている。この方法では、被測定対象のマイクロレンズアレイに所定波長の入射光を入射させ、透過側又は反射側に生じる回折光の直交する２つの方向に回折される各々複数の回折次数の強度を検出することで、各回折次数の回折効率の実測値を求め、他方、被測定対象のマイクロレンズアレイの各レンズの形状として２次元的なサンプリング点に初期値を与え、その初期値から出発して前記所定波長の入射光を入射させたときに透過側又は反射側に生じる回折光の直交する２つの方向に回折される各々複数の回折次数の強度を厳密な電磁波解析により算出し、順次遺伝的アルゴリズムを適用しながら、その算出値と前記実測値の差をパラメータとする評価関数を用いて、前記初期値の形状を最適化する。
【００１３】
特許文献１２には、マルチビームを用いた電子写真方式の画像形成手段や回転多面鏡による走査光学系を用いた電子写真方式の画像形成手段において発生する画質の劣化を防ぐことが記載されている。そのため、評価手段によりマルチビームの各ビームで発生するドットの出現頻度や回転多面鏡の各反射面によって走査形成されるドットの出現頻度に基づいてディザマトリクスに応じて生成される画像データに対する評価を行ない、この評価結果に基づき求めたディザマトリクスの適応度に基づいて遺伝的アルゴリズム処理手段により遺伝的アルゴリズム処理を実行し、ディザデータ出力手段においては生成した遺伝子情報によりディザマトリクスを出力する。これにより、マルチビームの各ビームで光量に違いがある場合や回転多面鏡の反射面にばらつきがある場合であっても、画質への影響を軽減させることができるので、画質の劣化を防ぐことができることが記載されている。
【００１４】
特許文献１３には、機械本体の複数個所の温度測定に基づいて加工点における熱的な変位量を推定し補正する機能を備えた工作機械における、補正に用いられる所定の関係式に適合する最適な温度測定位置を遺伝的アルゴリズムを用いて求めることが記載されている。
【００１５】
特許文献１４には、適切なパレート最適個体を短時間で効率良く得ることが可能な多目的最適化装置、多目的最適化方法および多目的最適化プログラムを提供することが記載されている。多目的進化型アルゴリズム部は第１、第２および第３の親個体から複数の子個体候補を生成する。次に、適応度推定モジュールは全ての親個体および子個体候補についての真の適応度の推定値を算出する。さらに、多目的進化型アルゴリズム部は、全ての親個体および子個体候補のランキングを行い、最上位ランクの１つの子個体候補を親個体集合に追加して混雑度を算出し、それらの子個体候補を混雑度の良い順にソートし、より良い混雑度を有する所定数の子個体候補を子個体集合として選択する。多目的最適化問題の一例は、エンジンの燃費およびトルクの最適化に適用することである。
【００１６】
特許文献１５には、巡回すべき複数の地点に順序および／または時間的な制約がある場合に、当該制約を満足し得る巡回経路を探索できるようにすることが記載されている。そのため、巡回対象の地点の位置情報および／または巡回対象の地点の制約条件を入力する操作・入力手段と、２地点間の経路を探索する２点間経路探索手段と、複数の巡回対象の地点を巡回する巡回経路を探索する巡回経路探索手段と、を備え、２地点間経路探索手段は、巡回対象の２地点間全ての最短経路を探索して記憶し、巡回経路探索手段は、遺伝アルゴリズムを用いて最適な巡回経路を求める際に、巡回順序に応じた経路コストの和に前記巡回対象の地点の制約条件に応じた制約コストを付加して評価値を算出し、該評価値が既存集団における遺伝子より良い評価値であれば遺伝子集団に加えて、巡回経路探索を進める。
【００１７】
特許文献１６には、車両毎にパラメータ調整を行う必要がなく、車両の運動状態の変化に即応してリアルタイムにコーナリングパワーを推定可能なコーナリングパワー推定装置を提供することが記載されている。このため、コーナリングパワー推定装置は、車両運動モデルに基づいてヨーレートの推定値の演算を行う演算装置と、遺伝的アルゴリズムによる進化計算を行う算出装置とを備えている。
【００１８】
特許文献１７には、所定環境において最適解を求めるにあたり、染色体の初期値を新たに発生させる場合に、探索済み領域以外の領域に発生させ、効率的に最適解を求めることが記載されている。複数の情報体からなる情報体集団に対し、遺伝的アルゴリズムを用いて探索操作を行い、最適解を求める最適解探索装置において、適応度値の変化率と予め定められた変化率とを比較し、前記適応度値の変化率が、前記予め定められた変化率より小さいと判断した場合、新たな情報体を導入する。その際に、すでに導入されている情報体の分布情報を参照して、情報体密度がより少ない領域に対して新たに情報体を導入する。
【００１９】
特許文献１８には、複数種類のプロセッシングエレメントの機能およびそれらの接続を変えて種々のデータパスを動的に再構成するタイプの集積回路装置が記載されている。
【特許文献１】特開２００４−３６２４４０号公報
【特許文献２】特開２００６−２３８６８号公報
【特許文献３】特開２００６−２６８１０２号公報
【特許文献４】特開２００６−３０３９９９号公報
【特許文献５】特開２００６−３１２４１４号公報
【特許文献６】特開２００７−３１５４１号公報
【特許文献７】特開２００７−４１７２３号公報
【特許文献８】特開２００７−５２７９９号公報
【特許文献９】特開２００７−６８１７４号公報
【特許文献１０】特開２００７−１０２６３４号公報
【特許文献１１】特開２００７−１２１０５７号公報
【特許文献１２】特開２００７−１３７００７号公報
【特許文献１３】特開２００７−１６７９６６号公報
【特許文献１４】特開２００７−１７２３０６号公報
【特許文献１５】特開２００７−１８７５８４号公報
【特許文献１６】特開２００７−１９０９５５号公報
【特許文献１７】特開２００７−１９９９４３号公報
【特許文献１８】特開２００６−２８５３８６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２０】
遺伝的アルゴリズムは、メタヒューリスティック（Ｍｅｔａｈｕｒｉｓｔｉｃ）な解法の一例である。メタヒューリスティクスは、一般的な計算問題を解くためのヒューリスティックな方法（トライアンドエラーにより問題を解く方法）の１つであって、特定の問題に限定されず、どのような問題に対しても汎用的に対応できるように設計された、アルゴリズムの基本的な枠組みを示す。メタヒューリスティクスには、遺伝的アルゴリズムの他に、シミュレーテッドアニーリング法などが含まれる。また、この明細書において遺伝的アルゴリズムとは、遺伝的プログラミング、免疫的アルゴリズムなどのさまざまな拡張手段を含むものである。
【００２１】
遺伝的アルゴリズムは、上記特許文献１−１７に示したように、多種多様な分野において多種多様な問題の解決に用いることが提案されている。遺伝的アルゴリズムを用いて、問題に対する解を見つける際に、一般的に要求されることは、できるだけ複雑な遺伝子を表現できること、できるだけ任意な遺伝子を選択できることである。そして、各遺伝子をできるだけ多くの条件で適正に評価し、世代交代をできるだけ多く繰り返すことにより、最も適応度の高い個体（遺伝子）を「解」として出力することである。しかしながら、世代交代により生み出される各遺伝子を評価するためには、通常、長時間を要する。このため、複雑な表現を持った遺伝子の採用が実際には困難であり、最大世代数も限られてしまうことが多い。さらに、進化に長時間を要するために、遺伝子をリアルタイムに、あるいはリアルタイムに近い状態で進化させて、環境への適応力を高めることも難しい。
【００２２】
このような問題は、遺伝的アルゴリズムを用いた解法に限らず、トライアンドエアーを繰り返し（反復し）、解を発見的に導く、メタヒューリスティックな解法に共通するものである。したがって、複雑な表現を持った遺伝子に代表されるメタヒューリスティクスな解を高速で評価できる手段および方法が求められている。
【課題を解決するための手段】
【００２３】
本発明の一態様は、回路を構成するための複数のエレメントと、複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、内部配線による複数のエレメントの接続を変更すること、および／または複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置である。この制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより、再構成ユニットの少なくとも一部に回路を再構成する。このデータ処理装置は、さらに、発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給するサンプルデータ供給ユニットと、複数のサンプルに基づく評価対象回路の出力データの少なくとも一部を用いて評価対象回路の評価値を得る評価ユニットとを含む。
【００２４】
再構成ユニットに回路を再構成するためのコンフィグレーションデータと、そのコンフィグレーションデータにより再構成される回路とは、基本的に一対一で対応する。したがって、コンフィグレーションデータに何らかの変化があれば、それにより再構成される回路も変化する。回路のそのような変化により、回路の出力に影響があるか否かはケースバイケースである。しかしながら、コンフィグレーションデータを、それにより再構成される回路の出力を用いて評価することが可能であり、最適解として評価されたコンフィグレーションデータにより、同一構成の他の再構成ユニットに回路を再構成すれば、同一の性能を得られる。そして、コンフィグレーションデータの評価は、コンピュータプログラムにより動作する数値的な計算またはシミュレーションではなく、再構成ユニットに再構成された回路を機能させる、すなわち、複数の入力データのサンプルを再構成された回路に供給することで短時間に行えるようになる。
【００２５】
また、複雑な遺伝子に対応するような複雑なコンフィグレーションデータも、それに対応した回路として再構成ユニットに実装される。そのようなコンフィグレーションデータにより再構成される回路は、回路構成が複雑になるかもしれない。しかしながら、回路構成が複雑になることにより処理速度が低下したとしても、その度合いは、プログラムステートメントが増大することによる処理速度の低下とは比較にならないほど小さく、複雑なコンフィグレーションデータであっても短時間で評価できる。さらに、パイプライン処理、並列処理などを併用することにより、より高速な評価が可能となる。したがって、複雑な表現を持った遺伝子に代表されるメタヒューリスティクスな解を高速で評価できる。
【００２６】
サンプルデータ供給ユニットは、評価対象回路においてパイプライン処理が行われる間隔で複数のサンプルを供給し、評価ユニットは、評価対象回路とともに、再構成ユニットに構成されることが好ましい。発見的なコンフィグレーションデータにより、パイプライン処理が行われる評価対象回路が構成されれば、評価ユニットにおける処理も含めてパイプライン処理が可能となる。したがって、複雑なコンフィグレーションデータであっても、実質的に、評価結果を、サンプルの入力データを入力するために要する時間程度の短い間隔で得ることができる。
【００２７】
制御ユニットは、複数セットの発見的なコンフィグレーションデータを出力し、再構成ユニットには、複数セットの発見的なコンフィグレーションデータにより、複数の評価対象回路が再構成され、サンプルデータ供給ユニットは、複数の評価対象回路に対し並列に前記複数のサンプルを供給することが望ましい。複数セットの発見的なコンフィグレーションデータを、複数の評価対象回路により並列に評価できる。したがって、評価結果を短時間に得ることができる。
【００２８】
評価ユニットから得られる評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成し、制御ユニットより使用可能とする生成ユニットをさらに有することが望ましい。評価結果が得られる時間を短縮できるので、世代交代する間隔を短縮でき、最適解を得るための最大世代数を増大できる。
【００２９】
生成ユニットは、再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成する機能を含むことが望ましい。発見的なコンフィグレーションデータにより再構成される評価対象回路は、予め規定される評価ユニットにおいて有意な出力データを出力するとは限らない。テンプレートコンフィグレーションデータを親または現世代として次世代の発見的なコンフィグレーションデータを生成することにより、無駄あるいは評価対象にならない評価対象回路を再構成するような発見的なコンフィグレーションデータが生成される可能性を抑制できる。
【００３０】
複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータであることが望ましい。このようなテンプレートコンフィグレーションから生成される次世代の発見的なコンフィグレーションデータを生成することにより、次世代の発見的なコンフィグレーションデータがパイプライン処理を行う評価対象回路を再構成するものである可能性を向上でき、評価時間を短縮できる可能性が高くなる。
【００３１】
生成ユニットは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、次世代の発見的なコンフィグレーションデータを生成することが望ましい。内部配線による複数のエレメントの接続を変更することも含めて次世代の発見的なコンフィグレーションデータを生成しても良い。複雑で多種多様な遺伝子に相当するコンフィグレーションデータを生成できる。しかしながら、評価対象にならない評価対象回路を再構成するコンフィグレーションデータも生成され易くなる。コンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新して、次世代の発見的なコンフィグレーションデータを生成することにより、評価対象にならない評価対象回路を再構成するコンフィグレーションデータが生成される可能性を低くできる。
【００３２】
テンプレートコンフィグレーションデータが、解を求めようとしているシステムなどに固有の条件を反映するものであっても良い。テンプレートコンフィグレーションデータの、それら固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代の発見的なコンフィグレーションデータを生成するようにしても良い。発見的なコンフィグレーションデータの変化、突然変異の範囲が縮小されるが、システムに適した解を早いタイミングで得ることができる。
【００３３】
本発明の他の態様の１つは、再構成ユニットと、コンフィグレーションデータを出力する制御ユニットとを有するデータ処理装置であって、制御ユニットは、最適解として評価された発見的なコンフィグレーションデータにより回路を再構成する、データ処理装置である。最適解として評価された発見的なコンフィグレーションデータにより、再構成ユニットに、評価対象回路と同一の回路を構成することができ、最適と評価された機能を再構成ユニットにより提供できる。
【００３４】
本発明の他の態様のさらに異なるものは、回路を再構成可能な再構成ユニットを用いた解探索の方法である。再構成ユニットは、複数のエレメントと、複数のエレメントを接続するための内部配線とを含み、内部配線による複数のエレメントの接続を変更すること、および／または、複数のエレメントの機能を変更することにより、回路を再構成可能である。再構成ユニットの回路を再構成するためのコンフィグレーションデータは、複数のエレメントの接続情報および／または複数のエレメントの機能情報を含む。当該方法は、以下の各ステップを有する。
・少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより再構成ユニットの少なくとも一部に回路を再構成すること。
・発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給すること。
・複数のサンプルに基づく評価対象回路の出力データの少なくとも一部を用いて評価対象回路の評価を得ること。
・評価を得ることを繰り返すことにより、評価対象回路を再構成するための発見的なコンフィグレーションデータを解として探索すること。
【００３５】
この方法は、発見的なコンフィグレーションデータを、その発見的なコンフィグレーションデータにより再構成ユニットに再構成される回路により評価できる。したがって、高速で、最適解を探索できる。
【００３６】
サンプルを供給するステップは、評価対象回路においてパイプライン処理が行われる間隔で複数のサンプルを供給することを含み、評価値を得るステップは、評価対象回路とともに、再構成ユニットに構成される回路により評価値を得ることを含むことが望ましい。
【００３７】
再構成するステップは、複数セットの発見的なコンフィグレーションデータにより、再構成ユニットに複数の評価対象回路を再構成することを含み、サンプルを供給するステップは、複数の評価対象回路に対し並列に複数のサンプルを供給することを含むことが望ましい。
【００３８】
評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することをさらに有することが望ましい。そのような発見的なコンフィグレーションデータは、遺伝的アルゴリズムにより生成される遺伝子に対応したコンフィグレーションデータ（遺伝子的コンフィグレーションデータ、遺伝的コンフィグレーションデータ、遺伝子対応コンフィグレーションデータ）となる。次世代の発見的なコンフィグレーションデータは、現世代の発見的なコンフィグレーションデータとして使用され、評価対象回路が再構成される。
【００３９】
上記の生成するステップは、再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４０】
複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータであることがさらに望ましい。
【００４１】
生成するステップは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４２】
テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、生成するステップは、テンプレートコンフィグレーションデータの、固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代の発見的なコンフィグレーションデータを生成することを含むことが望ましい。
【００４３】
また、この方法は、さらに、前世代のコンフィグレーションデータを、内部配線による複数のエレメントの接続を変更することを含めて、遺伝的アルゴリズムにより更新し、再構成ユニットにより評価し、複数のテンプレートコンフィグレーションデータを探索することをさらに含むことが望ましい。あるシステムに対して適当な解が得られそうなテンプレートコンフィグレーションデータは、ヒューリスティックな方法により探索できる。それを、事前に、再構成ユニットを用いて行うことにより、最適解の探索に要する時間を短縮できる。
【発明を実施するための最良の形態】
【００４４】
図１（ａ）に、再構成可能なデバイスの一例を示している。このデバイス１は、本願の出願人が開発したＤＡＰＤＮＡと称する半導体集積回路装置である。このデバイス１は、ＤＡＰと呼ばれるＲＩＳＣコアモジュール２と、ＤＮＡと呼ばれるダイナミックリコンフィグラブルデータフローアクセレレータ３とを含む。デバイス１は、ＤＡＰ２およびＤＮＡ３に加え、ＤＮＡ３のダイレクト入出力用のインターフェイス４と、ＰＣＩインターフェイス５と、ＳＤＲＡＭインターフェイス６と、ＤＭＡコントローラ７と、その他の周辺デバイス８と、これらを接続するための高速スイッチングバス（内部バス）９とを含む。ＤＡＰ２は、デバッグインターフェイス４２ａと、ＲＩＳＣコア４２ｂと、命令キャッシュ４２ｃと、データキャッシュ４２ｄとを含む。ＤＮＡ３は、３７６個のＰＥ（ＰＥｓ、処理エレメント）が２次元に配置されたＰＥマトリクス１０と、このＰＥマトリクス１０に含まれるＰＥｓの機能および／またはＰＥｓの接続を変えてＰＥマトリクス１０を再構成するためのコンフィグレーションデータ１８が格納されるコンフィグレーションメモリ１９とを含む。ＰＥマトリクス１０に配置されるＰＥの数は、上記に限定されるものではない。
【００４５】
コンフィグレーションメモリ１９は、複数バンクの構成になっている。例えば、図１（ｂ）に示すように、ＰＥマトリクス１０には、フォアグラウンドバンクに格納されるコンフィグレーションデータ１８により第１の機能（データフロー、回路デザイン）１７ａが構成される。また、異なるバックグラウンドバンクにそれぞれ格納されるコンフィグレーションデータにより、第２の機能１７ｂおよび第３の機能１７ｃがそれぞれ構成される。メモリ１９のバンクを切り替えることにより、ＰＥマトリクス１０には、第１の機能１７ａに変わって第２の機能１７ｂまたは第３の機能１７ｃが再構成される。ＰＥマトリクス１０の再構成は、例えば、１サイクル（クロックサイクル）でダイナミックに行なわれる。このようにＰＥマトリクス１０は、回路を構成するための複数のエレメントと、これらのエレメントを接続するための内部配線とを含む再構成ユニットであり、内部配線によりエレメントの接続を変えることによりＰＥマトリクス１０に含まれる回路を動的に再構成できる。
【００４６】
図１（ｃ）は、ＰＥマトリクス１０に回路を再構成する一例である。あるアプリケーション、例えばＭＰＥＧデコーダを時分割した複数の機能（サブファンクション）を、ＰＥマトリクス１０に時分割で動的に再構成し、ＭＰＥＧデコーダの機能を専用回路（専用ハードウェア）で提供する。このような使用により、再構成可能なデータ処理装置であるデバイス１を用いて、多くのハードウエア資源を必要とするアプリケーションを、少ないハードウエア資源で実行できる。
【００４７】
図１（ｄ）は、ＰＥマトリクス１０に回路を構成する他の例の一つである。再生方式が異なるアプリケーションを実行するために、複数の機能がそれぞれ実現されるようにＰＥマトリクス１０を再構成できる。このような使用により、多くのアプリケーションを共通のハードウエア（デバイス）１を用いて実行できる。このデバイス１は、プログラムレベル（命令レベル）ではなく、データフローレベル（データパスレベル、ハードウエアレベル）で多数の機能を切り換えて実装できるので、専用のハードウエアに匹敵する速度で処理を行うことができる。さらに、ＰＥマトリクス１０に含まれるＰＥｓは、クロックにより同期した処理を行うことが可能であり、パイプライン処理に適したデータフロー（データパス）をＰＥマトリクス１０に再構成できる。さらに、多数のＰＥｓにより並列処理を行う複数のデータフローを並列に再構成することも可能である。したがって、ＰＥマトリクス１０に回路を動的に再構成することにより、ハードウエアにより高速処理と、ソフトウエアのような柔軟性とが融合された動作環境および解探索環境を提供できる。
【００４８】
図２に、ＰＥマトリクス１０の配列を拡大して示している。処理エレメントＰＥｓは、全体として、１６×２４のマトリクスを構成するように配置されている。なお、図３に示すように、ＰＥのいくつかは、２個分のＰＥのスペースを占め、全体として３７６個のＰＥがＰＥマトリクス１０に実際には配置されているが、図２には反映していない。これらのＰＥｓは、さらに、それぞれ８×８のＰＥｓからなる６つのグループに区分けされている。これらのグループをセグメントＳと称し、ＰＥマトリクス１０の左上から右下に向かって順番にセグメントＳ０からセグメントＳ５が配置されている。各々のセグメントＳ０〜Ｓ５に含まれるＰＥは、１サイクルの遅延の範囲内でデータを送受信可能なイントラセグメントコネクションで接続されている。また、セグメントＳ０〜Ｓ５の内、隣接するセグメントは、後述するディレイエレメントを介してインターセグメントコネクション２２により接続されている。
【００４９】
図３に、ＰＥマトリクス１０に含まれるＰＥｓの具体的な配置例を示している。図３に示したＰＥのうち、「ＥＸ」で始まるＰＥは、ＥＸＥエレメントと呼ばれ、算術演算、論理演算および２入力の比較機能を含む演算用のエレメントである。「ＥＸＣ」は、ＣＭＰＳＢ命令を搭載し、「ＥＸＦ」は、ＦＦ１命令を搭載し、「ＥＸＭ」は、乗算命令を搭載し、「ＥＸＲ」はＢＲＥＶ命令を搭載し、「ＥＸＳ」は、ＢＳＷＡＰ命令を搭載するというように、タイプ毎に固有の演算機能も含んでいる。
【００５０】
「ＤＬ」で始まるＰＥは、ディレイエレメントであり、１−８クロックの間の遅延をそれぞれ設定できる。「ＤＬＥ」は、セグメント内のデータ遅延用であり、「ＤＬＶ」は縦方向のセグメント間のデータ送受信用であり、「ＤＬＨ」は横方向のセグメント間のデータ送受信用であり、「ＤＬＸ」は縦横方向のセグメント間のデータ送受信用のエレメントである。
【００５１】
「ＲＡＭ」と表示されたＰＥは、ＤＮＡの内部メモリとして使用されるエレメント（メモリエレメント）である。「ＬＤＢ」と表示されたＰＥは、データ入力用のＤＮＡ内部バッファである。「ＳＴＢ」と表示されたＰＥは、データ出力用のＤＮＡ内部バッファである。「Ｃ１６Ｅ」と表示されたＰＥは、ＤＮＡ内部バッファに対するアドレス生成エレメントである。「Ｃ３２Ｅ」と表示されたＰＥは、外部メモリ空間に対するアドレス生成エレメントである。「ＬＤＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏからのデータ入力用エレメントである。「ＳＴＸ」と表示されたＰＥは、ＤＮＡダイレクトＩ／Ｏへのデータ出力用エレメントである。ＰＥマトリクス１０において、ＬＤＢおよびＬＤＸは、外部からデータを入力するための入力インターフェイスとして使用でき、ＳＴＢおよびＳＴＸは、外部へデータを出力するための出力インターフェイスとして使用できる。
【００５２】
図４に、ＰＥの一例として、ＥＸＥエレメント（「ＥＸＭ」）の概略構成をブロック図により示している。ＥＸＭエレメントは、ＡＬＵ１１ａと、ＭＵＬ（１６×１６）１１ｂと、ＦＦ１１ｃなどを含む。このＥＸＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納されたコンフィグレーションデータ１８に含まれる、ＰＥの機能を設定するための機能情報により、算術演算、論理演算、２入力の比較機能、さらには、乗算のいずれか、または複合した命令を実行するように構成できる。また、複数のＦＦ１１ｃを内蔵しているので、エレメントＰＥに対するデータの入力から出力までのレイテンシを制御することが可能であり、ディレイエレメント（ＤＬＥ）の数が不足する構成では、ディレイエレメントとしての機能をセットすることも可能である。
【００５３】
図５に、ＰＥの他の例として、ＲＡＭエレメント（「ＲＡＭ」）の概略構成をブロック図により示している。このＲＡＭエレメントは、データ格納用メモリエレメントであり、１６ＫＢ（３２ビット×４０９６ワード）のＲＡＭモジュール１２ａと、アドレス入力用のアドレスレジスタ（ＦＦ）１２ｂ、ラッチ１２ｃ、データ入力用のライトデータレジスタ（ＦＦ）１２ｄ、ラッチ１２ｅ、データ出力用のリードデータレジスタ（ＦＦ）１２ｆを含む。ＲＡＭモジュール１２ａのリードとライトの制御は、アドレスデータおよび／またはリードデータとともに入力されるトークンの値により行なわれる。アドレス入力からリードデータの出力までは、ＥＸＥエレメントと同様に３クロックサイクル程度で可能になっており、ＰＥマトリクス１０に含まれる他のタイプのＰＥと同様のレイテンシで、データの入出力が可能である。このＲＡＭエレメントは、ＤＮＡ３のコンフィグレーションメモリ１９に格納され、それぞれのＰＥに供給されるコンフィグレーションデータ１８に含まれる機能情報により、３２ビットモード、デュアルポート３２ビットモード、ＦＩＦＯモード、１６ビットモード、８ビットモード、さらに、ＦＳＭ（フィードバックステートモード）でデータ入力および／または出力するように構成できる。
【００５４】
ＲＡＭエレメントのアクセスアドレスの生成には、ＥＸＥエレメント、カウンタエレメントであるＣ１６Ｅおよび／またはＣ３２Ｅを使用することができ、ＰＥマトリクス１０のルーティングマトリクス（マトリクスバス）を通じて、ＲＡＭエレメントに入力できる。したがって、ＲＡＭエレメントへの入出力は、ＰＥマトリクス１０に再構成される回路により制御できる。なお、ＲＡＭ、ＥＸ以外のＰＥについても、同様に、それぞれのＰＥに提供されるコンフィグレーションデータ１８に含まれる機能情報により、機能（定数などを含めて）を設定および変更できる。
【００５５】
ＰＥマトリクス１０は、複数のＰＥｓと、それらを接続するためのルーティングマトリクス（内部配線、配線群）２０を含む。ルーティングマトリクス２０は、セグメントＳ内のＰＥを接続するための第１レベルの配線群（第１レベルのルーティングマトリクス、イントラコネクト）２１と、ディレイエレメントを介して隣接するセグメントＳの間を接続するための第２レベルの配線群（第２レベルのルーティングマトリクス、インターコネクト）２２とを含む。ルーティングマトリクス２０によるＰＥｓの接続はコンフィグレーションデータ１８により制御できる。したがって、ＰＥマトリクス１０には、コンフィグレーションデータ１８により、複数のＰＥのそれぞれの機能を変更すること、および／または、ルーティングマトリクス２０の少なくとも一部の接続を変更することにより、異なる回路（データパス、データフロー）を再構成できる。
【００５６】
図６に、セグメントＳの内部のＰＥｓを接続するための第１レベルの配線群２１の構成の一例を示している。第１レベルのルーティングマトリクス２１は、セグメントＳ０に含まれる８×８個のＰＥｓを接続するために、１２８の縦方向のバス２３と、６４の横方向のバス２４とを含む。縦方向のバス２３は、１６のグループに分けられ、それぞれ８のバスを含む２つのＶ−バス２３ｘおよび２３ｙがペアとなり、ＰＥｓの縦の列（コラム）に沿って、その列の両側に配置されている。横方向のバス２４は８のグループに分けられ、それぞれ８のバスを含むＨ−バス２４がＰＥの横方向の行（ライン）に沿って配置されている。Ｖ−バス２３ｘおよび２３ｙには、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２５がそれぞれのＰＥに対応して設けられており、それぞれのＰＥに対してデータの入力を可能としている。
【００５７】
Ｈ−バス２４には、Ｈ−バス２４とＶ−バス２３ｘおよび２３ｙのそれぞれの交差に対応して、８−１のバスセレクタ（マルチプレクサ、ＭＵＸ）２６が設けられている。したがって、１つのＨ−バス２４から１つのデータセットを、そのＨ−バス２４と交差している１つのＶ−バス２３ｘまたは２３ｙに出力できる。逆も可能である。Ｈ−バス２４に含まれるバスのそれぞれには、そのラインのＰＥｓの出力が接続される。したがって、Ｖ−バス２３ｘおよび２３ｙと、Ｈ−バス２４とを介することにより、セグメントＳに含まれるＰＥｓを接続できる。これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４の接続は、コンフィグレーションデータ１８に含まれる接続情報により制御できる。そして、これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により実現できる接続パターンは膨大であり、基本的には、セグメントＳに含まれる全てのＰＥをフレキシブルに接続できる。したがって、コンフィグレーションデータ１８により、ＰＥｓの接続を、配線資源により制限は受けるとしても、基本的には、自由自在に制御できる。
【００５８】
これらのＶ−バス２３ｘおよび２３ｙ、およびＨ−バス２４を含む第１レベルのバス２１により接続できる範囲、すなわち、各セグメントＳ０〜Ｓ５内のＰＥの間では１サイクル（１クロック）以内にデータを送受信できる。したがって、タイミング的には、例えば、セグメントＳ０に含まれるＰＥｓは、いずれも等価である。このため、同一セグメント内であれば、回路を構成するために、いずれのＰＥを選択して機能を割り付けても、タイミングの検討は不要であり、タイミング的には、セグメント内のＰＥｓを用いて、所定の回路を自由に配置および配線できる。
【００５９】
図７に、第２レベルのルーティングマトリクス２２の構成を示している。図７では、第２レベルのルーティングマトリクス２２により、隣接するセグメントＳ１およびＳ４にそれぞれ含まれている接続用のエレメントＤＬＨを接続している。それぞれのＤＬＨは、それぞれのセグメントＳ１およびＳ４の内部の第１レベルのルーティングマトリクス２１に接続している。したがって、セグメントＳ１に含まれるＰＥと、セグメントＳ４に含まれるＰＥとを第２レベルのルーティングマトリクス２２を介して接続することができる。接続用のディレイエレメントＤＬＨは、第１レベルのルーティングマトリクス２１に含まれるバスのインターフェイスとして機能する。セグメント間の接続も、したがって、ＤＬＨなどのセグメント内における接続用のエレメントと他のＰＥとの接続および接続用エレメントの機能を、コンフィグレーションデータ１８の接続情報および／または機能情報により制御できる。したがって、ＰＥマトリクス１０に含まれるすべてのＰＥｓの接続および機能を、マトリクス１０の全体としても、マトリクス１０の部分に限定的にも、コンフィグレーションデータ１８により制御することができる。
【００６０】
メタヒューリスティクスな方法により生成される発見的なコンフィグレーションデータ（ヒューリスティックに生成されたコンフィグレーションデータ、ヒューリスティックなコンフィグレーションデータ）およびそれによりＰＥマトリクス１０に再構成される回路は、回路から出力される結果が、その処理により得ようとする目的に合致したもの、あるいは目的に合致している確率が高そうなものであれば、意味（たとえば、物理的な内容、統計学的な意味、その他の学術的な意味）が無い、意味が不明または意味を解析するために時間を要するものであっても良い。しかしながら、以下では、説明を簡単にするために、発見的なコンフィグレーションが、評価対象回路として、以下のような適当または任意の多項式を演算するための回路を再構成する場合を想定する。
【００６１】
Σｆｉ（ｘ１，ｘ２・・ｘｎ−１，ｘｎ）＝Ｆｏｕｔ ・・・（１）
上記式（１）において、ｉは１〜ｎまでの整数であり、式（１）の多項式の部分が、変数ｘｉにより与えられる何らかの事象（システム、現象）に対する解に相当する。したがって、以下では、遺伝的アルゴリズムにより、最適解を示す多項式の部分を探索する。そのため、多項式が、遺伝子、すなわち、発見的なコンフィグレーション（遺伝子的コンフィグレーションデータ、遺伝子対応のコンフィグレーションデータ）として生成され、その発見的なコンフィグレーションを、再構成ユニットであるＰＥマトリクス１０にその発見的なコンフィグレーションにより再構成された評価対象回路により評価する。発見的なコンフィグレーションの生成方法によるが、生成された発見的なコンフィグレーションによりＰＥマトリクス１０に再構成される評価対象回路のうち、式（１）として意味のあるものが評価されるということも可能である。さらには、生成された発見的なコンフィグレーションによりＰＥマトリクス１０に再構成される評価対象回路を、式（１）が実装されていると想定して評価するということも可能である。
【００６２】
式（１）の出力Ｆｏｕｔは、評価対象回路の出力に相当する。出力Ｆｏｕｔを得るために、学習データ、教師データなどと称される変数ｘｉの複数セットをサンプルとして入力する。学習データには、変数ｘｉのセットと、そのセット（学習データセット）により得られたい結果とが含まれており、出力Ｆｏｕｔと、結果とを比較することにより、その学習データセットに対する評価対象回路の可否が判断される。そして、複数の学習データセットに対して、良好な結果が得られた発見的なコンフィグレーションを親として、次世代の発見的なコンフィグレーションが生成される。
【００６３】
図８に、コンフィグレーションデータ１８の一例を示している。コンフィグレーションデータ１８は、各ＰＥの機能を記述している機能情報セクション１８ａと、バスセレクタ２５および２６の接続情報を記述している接続情報セクション１８ｂとを含む。セクション１８ａには、各ＰＥを特定するための識別情報（アドレス）１８ｃと、機能の設定内容１８ｄとが含まれている。セクション１８ｂには、バスセレクタ２５および２６を特定するための識別情報（アドレス）１８ｅと、接続の内容１８ｆとが含まれている。以下の例では、同じフォーマットのコンフィグレーションデータ１８であって、含まれている機能情報１８ａおよび／または接続情報１８ｂが異なる複数のデータがヒューリスティックな方法、具体的には、遺伝的アルゴリズムにより、発見的なコンフィグレーションデータ（以降では遺伝子的コンフィグレーションデータあるいは遺伝子対応コンフィグレーションデータ、ＧＣＤ）７１が世代単位で、遺伝子対応コンフィグレーションデータ（ＧＣＤ）のグループあるいはセット７０として生成される。ＧＣＤ７１は、ヒューリスティックに生成される情報を含めばよく、ＰＥマトリクス１０全体がヒューリスティックな情報により再構成される必要はない。ＰＥマトリクス１０に実装（再構成）される回路のうち、評価対象回路に相当する部分の全てまたは一部を再構成するための情報がヒューリスティックな情報であればよい。この明細書において、ヒューリスティックなデータまたは情報とは、少なくとも１部が、ヒューリスティクス（メタヒューリスティクス）な方法により生成されたものを示す。
【００６４】
図９は、本発明の実施形態の一例のデータ処理装置のブロック図である。このデータ処理装置５０は、ＤＡＰＤＮＡ１を用いて実現されている。データ処理装置５０は、再構成ユニット（再構成領域）であるＰＥマトリクス１０を有する。このＰＥマトリクス１０は、上述したように、回路を構成するための複数のエレメント（ＰＥ）と、これらＰＥを接続するための内部配線２０とを含み、内部配線２０による複数のＰＥの接続および／またはＰＥｓのそれぞれの機能を変更することにより、当該再構成ユニット１０に含まれる回路を再構成可能である。さらに、データ処理装置５０は、複数のＰＥの接続情報１８ｂおよび各ＰＥの機能情報１８ａを含む再構成情報（コンフィグレーションデータ）１８を用いて、ＰＥマトリクス１０に回路を再構成する再構成制御ユニット２ａを有する。この例では、再構成制御ユニット２ａとしての機能はＤＡＰ２により提供され、再構成制御ユニット２ａにより回路を再構成するために用いられるコンフィグレーションデータ１８はＧＣＤ７１を含む。
【００６５】
このデータ処理装置５０では、再構成制御ユニット２ａが、コンフィグレーションメモリ１９にＧＣＤ７１をセットし、ＰＥマトリクス１０の一部を用いて、評価対象回路６１を構成する。さらに、再構成制御ユニット２ａは、ＧＣＤ７１とは異なるコンフィグレーションデータ１８をコンフィグレーションメモリ１９にセットし、ＰＥマトリクス１０の残りの部分を用いて、評価対象回路６１を評価するためにサンプルデータ（学習データ）７６を供給するための回路（サンプルデータ供給回路）６２と、評価対象回路６１の出力（この例ではＦｏｕｔ）の評価を行い評価値７８、たとえば出力Ｆｏｕｔの正解率を演算するための回路（評価回路）６３とを構成する。
【００６６】
図１０（ａ）は、ＧＣＤ７１のある世代の群（グループ）７０の一例である。たとえば、１世代の遺伝子データの群７０は、１０００個の遺伝子データ７１を含み、それぞれの遺伝子データはＧＣＤ７１を示している。
【００６７】
図１０（ｂ）は、学習データ７６の一例である。学習データ７６は、１０００個のデータセット７５を含み、それぞれのデータセット７５は、多項式（１）の変数ｘ１〜ｘ５０と、それらの変数により計算される予定の値（予定値）Ｔｓとを含む。学習データ７６は、サンプルデータ供給回路６２により、各々のＧＣＤ７１によりＰＥマトリクス１０に再構成される評価対象回路６１に供給される。これら１０００個のデータセット７５による出力値は、評価回路６３により予定値Ｔｓと比較され、正解率が演算される。図１０（ｃ）に、遺伝子（ＧＣＤ）７１毎の正解率が評価値７８として出力された状態を示している。
【００６８】
図９に示すように、データ処理装置５０は、次世代の遺伝子、すなわち次世代のＧＣＤの群７２を生成するユニット（生成ユニット）２ｂを有する。この例では、生成ユニット２ｂとしての機能はＤＡＰ２により提供される。生成ユニット２ｂは、遺伝的アルゴリズムにより、現世代のＧＣＤ群（遺伝子群）７０から次世代のＧＣＤ群（遺伝子群）７２を生成し、現世代のＧＣＤ群７０を次世代のＧＣＤ群７２により置き換え、再構成制御ユニット２ａが使用できるようにする。より具体的には、生成ユニット２ｂは、評価値７８により、現世代のＧＣＤ７０のそれぞれのＧＣＤ７１の適応度を判断する。そして、ある確率で選択（淘汰、再生）し、交叉、突然変異、コピーを含む遺伝的操作を行い、次世代のＧＣＤ群７２を生成する。選択方法は、ルーレット選択、ランキング選択、トーナメント選択などが知られている。交叉方法は、一点交叉、二点交叉、多点交叉、一様交叉などが知られている。次世代のＧＣＤ群７２は、最適解のＧＣＤ７１ができるだけ早く探索されるように生成することが好ましく、具体的な遺伝子操作の方法は、解を得ようとするシステムの特性などによって選択することができる。
【００６９】
図１１に、あるＧＣＤ７１を含むコンフィグレーションデータ１８によりＰＥマトリクス１０に回路が再構成された状態を示している。この例では、ＧＣＤ７１によりＰＥマトリクス１０に再構成された評価対象回路６１は、４つの演算ブロック６５ａ〜６５ｄを含む。それぞれの演算ブロック６５ａ〜６５ｄに対して、ＰＥマトリクス１０に構成されたサンプル供給ユニット６２は、学習データ７６を並列に供給する。評価対象回路６１の出力は評価回路６３において評価される。サンプル供給回路６２が、たとえば、学習データ７６の１つのセット７５の最後を示すデータを評価対象回路６１に入力し、評価回路６３では、最終のデータがすべての演算ブロック６５ａ〜６５ｄから出力されたことを判定閾値で判定する。そして、そのタイミングで得られた評価対象回路６１の出力を、学習データセット７５に含まれている正解Ｔｓと比較する。学習データ７６に含まれる１０００個の学習データセット７５に対して、評価対象回路６１の出力と正解Ｔｓとを比較することにより、評価値として正解率７８を出力することができる。
【００７０】
図１２に、演算ブロック６５ａの一例を示している。この演算ブロック６５ａに含まれる回路は、ＡＬＵ、セレクタ、ラッチ、ＲＡＭとしての機能を有する各ＰＥの機能を変更するだけで多種多様な多項式を表現することができる構成を備えた回路の一例である。この演算ブロック６５ａの構成を採用することにより、たとえば、ＰＥの１タイプであるＲＡＭエレメントにより、図５に示したようにルックアップテーブル（ＬＵＴ）としての機能を実現でき、三角関数あるいは他の算術関数を含む多項式であっても実装できる。また、図４に示したように、ＰＥの１タイプであるＥＸエレメントは、２入力のＡＬＵとしての機能を備えており、一方の入力を無効にしたり、イミディエイトを代入することなどにより、ＰＥの機能を変更するだけで実質的にＰＥ間の接続も変更することができる。
【００７１】
したがって、生成ユニット２ｂは、現世代のＧＣＤ７１に含まれる複数のＰＥの機能を規定するパラメータ（機能情報）１８ｄを遺伝的アルゴリズムにより更新し、次世代のＧＣＤ群７２を生成する機能を含むことにより、多種多様な遺伝子に対応するＧＣＤを生成することができる。また、コンフィグレーションデータの機能情報１８ｄを更新することにより次世代のＧＣＤ群７２を生成する方法を採用すると、コンフィグレーションデータ１８の接続情報１８ｆは保存される。したがって、現世代のＧＣＤ７１により再構成される評価対象回路６１が、入力から出力までデータフローを形成するように複数のＰＥを接続する接続情報１８ｆを備えていれば、その特性は次世代のＧＣＤ群７２に引き継がれる。
【００７２】
このため、入力から出力まで、すなわち、サンプル供給回路６２から評価回路６３に到達するようなデータフローを形成する接続情報１８ｆを備えた複数のコンフィグレーションデータ（テンプレートコンフィグレーションデータ）７４をテンプレート群７３として用意しておくことは有用である。生成ユニット２ｂは、テンプレート群７３に含まれるコンフィグレーションデータを現世代として、次世代のＧＣＤ群７２を生成することができ、データフローを形成する特性を備えたＧＣＤ７１により評価対象回路６１を再構成できる。したがって、評価回路６３に出力がでないような評価に値しない回路が構成される可能性を低減でき、最適な解、すなわち、最適なＧＣＤに到達する速度を向上できる。
【００７３】
また、図１２に示した回路は、入力される学習データセット７５に含まれる複数の変数ｘｉをパイプライン処理することができる構成である。特に、このデータ処理装置５０に採用されている動的再構成デバイスのＤＡＰＤＮＡにおいては、ＰＥマトリクス１０に含まれる各ＰＥがクロックで同期した処理を行う。このため、連続パイプライン処理を行うデータフロー（データパス）をＰＥマトリクス１０に再構成することができる。
【００７４】
したがって、評価対象回路６１でパイプライン処理を行うことにより、複数の学習データセット７５を連続して、あるいは、演算結果Ｆｏｕｔが収束するために要する若干のクロック（サイクル、インターバル）を開けて連続供給することが可能である。その結果、学習データセット７５の入力に要する時間程度の間隔で評価対象回路６１の出力Ｆｏｕｔを評価回路６３に出力することができる。たとえば、学習データセット７５に含まれる変数を並列に１クロックで入力できるような評価対象回路６１であれば、理想的には１クロック毎に出力Ｆｏｕｔを得ることができる。このため、それぞれのＧＣＤ７１の評価に要する時間を大幅に短縮できる。パイプライン処理を行う回路構成も、たとえば、コンフィグレーションデータの接続情報１８ｆを保持することで、次世代のＧＣＤ７１に伝えることができる。また、テンプレートコンフィグレーションデータ７４も、パイプライン処理を行う回路構成であることが望ましい。また、サンプル供給回路６２は、パイプライン処理が行われることを前提として学習データセット７５を供給することも有効である。パイプライン処理が行われないような評価対象回路６１は、高い評価値を得られないので、パイプライン処理が行われる特性を備えた回路を構成するＧＣＤ７１を選択的に残し、次世代へ繋ぐことが可能となる。
【００７５】
本明細書において、パイプライン処理は、「毎クロック連続してデータ処理を行う」処理を示す。本例の再構成デバイス１は、ＤＮＡというデータフロー型のハードウエアで回路構成をとっており、データをロードするエレメント（ＬＤＢ）により強制的にデータをロードするかぎり必ずパイプライン処理となる。逆にパイプライン処理しない構成をとるためには、アドレス出力用のエレメント（Ｃ１６Ｌ、Ｃ３２Ｌ）およびロードエレメントＬＤＢといった、ＤＲＡＭ６からの処理対象データのロードを制御する機構のパラメータを変更する必要がある。これらのパラメータも、ＧＣＤ７１の遺伝子情報の一部に加えることにより、ＧＣＤ７１によっては「パイプライン処理をしない」という現象を起こすことが可能である。したがって、「非パイプライン処理」があらかじめ劣っているとわかっているのならば、ＧＣＤ７１の遺伝子情報を限定して必ずパイプライン処理になるようにすることが可能である。すなわち、具体的には、特定のエレメント（たとえば、ＬＤＢ、Ｃ１６Ｌ、Ｃ３２Ｌ等）のパラメータは固定にしておく。
【００７６】
また、本例の再構成デバイス１においては、パイプライン処理には、非フィードバック処理のみならず、フィードバック処理を含めることが可能である。フィードバック処理を含めてパイプライン処理する場合は、たとえば、データをＲＡＭエレメントなどにより提供されるＦＦ機能上に蓄積することが要求される。ＲＡＭエレメントおよびその他のエレメントにおいてＦＦ機能が提供されるような初期値も、ＧＣＤ７１の遺伝子情報とすることが可能である。フィードバック処理を含めることにより、ＧＣＤ７１により表現できる回路構成が爆発的に広がる。たとえば、ＦＩＲフィルタに対して、フィードバック付き小規模ＨＷで大規模なフィルタを構成できるＩＩＲフィルタを例として挙げることができる。したがって、フィードバック処理を含むＧＣＤ７１は、このタイプのＧＡＧＰで探索する解の好ましい一例である。
【００７７】
選択的に次世代のＧＣＤ群７０に引き継ぐ特性は上記に限定されない。テンプレート群７３に含まれるテンプレートコンフィグレーションデータ７４を、解を求めようとしているシステム、本例であれば変数ｘｉにより与えられるシステムに固有の条件を反映するように生成し、生成ユニット２ｂは、テンプレートコンフィグレーションデータ７４の固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、次世代のＧＣＤ群７２を生成する機能を含むことが望ましい。コンフィグレーションデータ１８によりＰＥマトリクス１０に構成可能な多様性に富んだ回路と、解を求めようとするシステムの特性との融合を図ることができる。このため、データ処理装置５０により、引用文献１〜１７に示されているような多種多様な用途に対し、メタヒューリスティクスな方法により、典型的には遺伝的アルゴリズム（遺伝的プログラム）により最適解を探索するシステムを提供できる。
【００７８】
テンプレートコンフィグレーションデータ（遺伝子テンプレート）７４による記述を採用することは、次のことを含む。予め単一のＤＮＡコンフィギュレーションにより遺伝子テンプレートを記述し、複数（数個〜数１０個）のＤＮＡコンフィギュレーションを予め用意する。これにより、多様な遺伝子に対応することが可能となる。また、遺伝子テンプレートのパラメータのみを更新することにより無数の遺伝子式を表現することが可能となる。また、複数のテンプレートの中から、テンプレートを選択することにより多様な遺伝子を表現することが可能となる。また、演算器（ＰＥ）を最大限活用し、シストリックアレイ型の多種多様な演算を実現することも可能となる。さらに、１つの遺伝子に対して全学習データを連続してパイプライン処理し、結果（正解数）を短時間で出力することも可能となる。
【００７９】
図１３ないし図１５に、動的再構成デバイス１を用いたデータ処理装置５０により、解を探索する方法の一例を示している。これらの図においては、ＧＣＤを遺伝子と表示し、遺伝的とＧＣＤとの対応関係を示している。
【００８０】
図１３に示す方法８１は、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、生成された次世代のＧＣＤ群７２を現世代の遺伝子に相当するＧＣＤ群７０と置き換えて、その世代のＧＣＤ群７０を評価するステップ８６とを有する。最初のＧＣＤ群を生成するステップ８５では、データ処理装置５０の生成ユニット２ｂが、テンプレート群７３に含まれるテンプレートコンフィグレーションデータ７４を個体としてランダムに選択し、それらの個体から第１世代のＧＣＤ群７０を生成する。
【００８１】
次に、ステップ８６において、再構成制御ユニット２ａは、第１世代のＧＣＤ群７０に含まれるそれぞれのＧＣＤ７１を含むコンフィグレーションデータ１８をコンフィグレーションメモリ１９にセットし、ＰＥマトリクス１０に評価対象回路６１を再構成する。サンプル供給回路６２は、評価対象回路６１に学習データ７６を供給し、評価回路６３により評価値を得る。それぞれのＧＣＤ７１に対応する評価対象回路６１を評価し、第１世代のＧＣＤ群７０に含まれるすべてのＧＣＤ７１の評価が終了すると、ステップ８５に戻って、次世代のＧＣＤ群７２を生成する。
【００８２】
ステップ８５において、生成ユニット２ｂは、現世代（第１世代）のＧＣＤ群７０と、評価データ７８とに基づき、遺伝的アルゴリズムにより次世代（第２世代）のＧＣＤ群７２を生成し、現世代のＧＣＤ群７０と置き換える。ステップ８６において、再構成制御ユニット２ａは、第１世代のＧＣＤに基づきヒューリスティックに生成された第２世代のＧＣＤ群を評価する。
【００８３】
このステップ８６において、さらに具体的には、再構成制御ユニット２ａは、ステップ８７ａにおいて、個々の第２世代のＧＣＤ７１を用いて、ＰＥマトリクス１０に評価対象回路６１を再構成し、ステップ８７ｂにおいて、評価対象回路６１を評価する。このデータ処理装置５０においては、ＰＥマトリクス１０に、典型的には１クロックで回路をダイナミックに再構成することができる。したがって、個々のＧＣＤ７１を評価するのに要する時間のほとんどすべては、評価対象回路６１を評価するための時間となる。
【００８４】
ステップ８７ｂはステップ８８および８９を含む。ステップ８８において、サンプルデータ供給ユニット６２により学習データ７６の各学習データセット７５を評価対象回路６１に供給する。ステップ８８においては、学習データ７６の学習データセット７５に含まれる変数ｘｉが次々とロードされ、評価対象回路６１に供給される。さらに、ステップ８９において、評価対象回路６１が学習データセット７５の演算を終了するのを待って、評価対象回路６１に出力により、評価回路６３が評価対象回路６１を評価する。
【００８５】
図１３に示すように、１つのＧＣＤ７１を評価するために、１００００セットの学習データ７５を供給し、その学習データ７５の演算を待って評価する必要がある。さらに、１世代のＧＣＤ群７０の評価を終了するためには、１０００個のＧＣＤ７１に対して同様の処理を行う必要がある。そして、１００世代のＧＣＤ群７０の評価を繰り返すことにより、ステップ９０において、適切なＧＣＤ７１を、最適解として得ることができる。学習データセット７５の数、一世代に含まれる遺伝子総数（ＧＣＤの総数）、評価世代数は例示に過ぎず、多くても、少なくても良い。メタヒューリスティクスな解法としては、それぞれの数が多い方が、より最適な解が求められることが多い。このケースでは、変数ｘｉ（たとえば、ｉは１〜５０）により与えられる事象に関する最適解を得るために、学習データセット７５による評価（ステップ８８および８９）を１０9回繰り返す。データ処理装置５０においては、ステップ８８および８９を、ＧＣＤ７１により再構成された専用回路（評価対象回路）６１により実行する。したがって、ＣＰＵなどの汎用の回路を用いて、プログラムポインタにしたがってロードを繰り返すソフトウェアプログラムを用いて演算を繰り返すケースと比較し、大幅に最適解を得るまで時間を短縮できる。このため、より多くの学習データセット、遺伝子総数、評価世代数により解を得ることが可能となり、より最適な解を得ることが可能となる。
【００８６】
図１４に示す方法８２も、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、次世代のＧＣＤ群７２を現世代のＧＣＤ群７０と置き換えて、その世代のＧＣＤ群７０を評価するステップ８６とを有する。さらに、ステップ８６のうち、評価対象回路６１を評価するステップ８７ｂにおいて、このデータ処理装置５０は、学習データ７６の各学習データセット７５を評価対象回路６１に供給するステップ８８と、評価対象回路６１が学習データセット７５の演算を終了するのを待って評価回路６３が評価対象回路６１を評価するステップ８９とを、ＤＮＡデバイス１の特性を活かして連続パイプライン処理する。すなわち、評価対象回路６１における演算終了を待たずに、評価対象回路６１の出力に影響を与えない範囲で連続して複数の学習データセット７５を、サンプルデータ供給回路６２により評価対象回路６１に供給する。
【００８７】
それぞれのＧＣＤ７１を評価するステップ８７ｂをパイプライン処理することにより、ステップ８７ｂの処理時間を大幅に短縮できる。上述したように、このケースでは、最適解を得るために、学習データセット７５による評価ステップ８７ｂ（ステップ８８および８９）を１０9回繰り返す。したがって、評価ステップ８７ｂの一回の処理時間の削減効果は、ステップ９０において最適解を得るまでの処理時間に１０9のオーダで反映され、解探索に要する処理時間を大幅に短縮できる。
【００８８】
さらに、それぞれの学習データセット７５を評価対象回路６１に供給するために要する時間を短縮することによりステップ８７ｂの処理時間をさらに短縮できる。たとえば、学習データセット７５に含まれる複数の変数ｘｉがパラレルに入力できるように、サンプルデータ供給回路６２および／または評価対象回路６１を構成することにより、評価対象回路６１から、ほぼ連続して、１クロックまたは数クロック単位で出力を評価回路６３に供給できる。さらに、パイプライン処理を行うことにより、評価対象回路６１の演算時間（処理時間）が、評価するステップ８７ｂに要する時間（評価時間）に与える影響を緩和できる。遺伝子に対応するＧＣＤ７１により再構成される評価対象回路６１としては、できるだけ任意で、できるだけ複雑な回路が構成できることが望ましい。多数のＰＥを含む評価対象回路６１は、処理時間は長くなる。しかしながら、パイプライン処理を採用することにより、個々の評価対象回路６１の処理時間が長くなることは、入力データを供給してから出力が得られるまでのレイテンシが長くなることに影響するだけであり、多数の学習データセット７５の評価間隔には影響を与えない。したがって、このデータ処理装置５０により、複雑な構成の遺伝子に対応するＧＣＤ７１を採用でき、短時間で最適な解を探索できる。
【００８９】
図１５に示す方法８３も、次世代の遺伝子に相当するＧＣＤ群７２を生成するステップ８５と、生成されたＧＣＤ群７２を現世代のＧＣＤ群７０として評価するステップ８６とを有する。さらに、ある世代のＧＣＤ群７０を評価するステップ８６において、ＧＣＤ群７０に含まれる複数のＧＣＤ７１により複数の評価対象回路６１をＰＥマトリクス１０に再構成し、それら複数の評価対象回路６１を並列に評価する。したがって、各世代のＧＣＤ群７０の評価に要する処理時間を数分の一に短縮することができ、最適解の探索に要する処理時間をさらに短縮できる。図１５に示すパラレル処理により処理時間を短縮する方法８３は、図１４に示したパイプライン処理により処理時間を短縮する方法８２とともに適用することが可能であり、最適解の探索に要する処理時間をさらに短縮できる。
【００９０】
データ処理装置５０に採用されている動的再構成デバイス（ＤＡＰＤＮＡ）１は、ＰＥマトリクス１０の一部だけであっても、動的に回路を再構成することができる。したがって、複数のＧＣＤ７１により複数の評価対象回路６１を再構成する場合も、それら複数の評価対象回路６１を同期して再構成する必要はなく、それぞれの評価対象回路６１の評価に要する時間に応じて、随時、ＰＥマトリクス１０の空いた領域に評価対象回路６１を再構成し、評価することができる。
【００９１】
上記に加え、解を得ようとする事象あるいはシステムの探索に適したテンプレートコンフィグレーション群７３を予め用意し、そのテンプレートコンフィグレーション群７３を初世代として次世代のＧＣＤ群７２を生成することは、短時間に最適な解を得るために有用な１つの方法である。そのようなテンプレートコンフィグレーション７４は、上記と同様に、データ処理装置５０により探索することができる。また、テンプレートコンフィグレーション群７３により探索された解のＧＣＤ７１をテンプレートコンフィグレーション群７３に加えたり、学習データ７６に、探索された解のＧＣＤ７１の適用により得られたデータを加えたりすることは可能である。したがって、探索された解に基づいて、さらにシステムに適した解を再探索したり、変化する事象あるいはシステムに対して最適な解を探索して自律的に適応するような装置を提供することが可能である。
【００９２】
さらに、このデータ処理装置５０は、探索された解、すなわち、探索された最適のＧＣＤ７１を用いて、事象あるいはシステムの入力データに対して出力データを生成し、出力するデータ処理装置としても機能する。したがって、このデータ処理装置５０により探索された解（ＧＣＤ）７０を、同じタイプのデータ処理装置５０に実装することにより、その解（ＧＣＤ）を簡単に利用することができる。また、その解（ＧＣＤ）を同じタイプのデータ処理装置５０に適用するために、その解（ＧＣＤ）の意味あるいはその解の物理的な意義を解釈したり、シミュレーションなどにより求めたりする必要はない。また、データ処理装置５０により得られた解をシミュレーションなどにより分析し、他の装置の制御のために用いることも可能である。
【００９３】
なお、上記では、遺伝的アルゴリズム（ＧＡ）をもとに、メタヒューリスティクスにコンフィグレーションデータを生成する例を説明しているが、メタヒューリスティクスにコンフィグレーションデータを生成する方法は、遺伝的アルゴリズムに限らず、遺伝的アルゴリズムの拡張の１つである免疫的アルゴリズム、さらには、シミュレーテッドアニーリング法などの他のメタヒューリスティクスな最適化手法であっても良い。
【００９４】
また、これらのメタヒューリスティクスな方法により生成されるコンフィグレーションデータによりＰＥマトリクスに再構成可能な回路は、回路として表現できる機能であれば、基本的にどのような機能であっても含めることが可能であり、上述した多項式に限らず、ツリー構造により機能が示される事象（アプリケーション）、その他の構造により機能が示される事象（アプリケーション）、たとえば、引用文献１〜１７に示した用途（技術）に対しても上記のデータ処理装置および解探索方法を適用できる。
【図面の簡単な説明】
【００９５】
【図１】図１（ａ）は、再構成可能なデバイスの一例の概略構成を示し、図１（ｂ）は、ＰＥマトリクスの概略を示し、図１（ｃ）および図１（ｄ）は、ＰＥマトリクスを動的に再構成する様子を示す。
【図２】ＰＥマトリクスの配列を示す図。
【図３】ＰＥマトリクスに配置されたＰＥのタイプを示す図。
【図４】ＰＥの１つのタイプのＥＸＭの構成を示すブロック図。
【図５】ＰＥの１つのタイプのＲＡＭの構成を示すブロック図。
【図６】セグメント内の配線（イントラセグメント配線）を示す図。
【図７】セグメント間の配線（インターセグメント配線）を示す図。
【図８】コンフィグレーションデータのフォーマットの一例を示す図。
【図９】再構成可能な領域を含むデータ処理装置の一例を示すブロック図。
【図１０】図１０（ａ）はコフィグレーションデータ（遺伝子データ）、図１０（ｂ）は学習データ、および図１０（ｃ）は評価データ（正解率）の例を示す。
【図１１】評価対象回路の一例を示すブロック図。
【図１２】演算ブロックの一例を示すブロック図。
【図１３】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【図１４】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【図１５】遺伝子（コンフィグレーションデータ）を評価して解を探索する過程を示す図。
【符号の説明】
【００９６】
１ 再構成可能なデバイス
２ａ 再構成制御ユニット、 ２ｂ 生成ユニット
１０ ＰＥマトリクス（再構成ユニット）
５０ データ処理装置
７０、７２、７４ 遺伝的アルゴリズムで生成されたコンフィグレーションデータ（ＧＣＤ）群
【特許請求の範囲】
【請求項１】
回路を構成するための複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、前記内部配線による前記複数のエレメントの接続を変更すること、および／または前記複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、
前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより前記再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置であって、
前記制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成し、
当該データ処理装置は、さらに、
前記発見的なコンフィグレーションデータにより再構成される評価対象回路に対し入力データの複数のサンプルを供給するサンプルデータ供給ユニットと、
前記複数のサンプルに基づく前記評価対象回路の出力データの少なくとも一部を用いて前記評価対象回路の評価値を得る評価ユニットとを含む、データ処理装置。
【請求項２】
請求項１において、前記サンプルデータ供給ユニットは、前記評価対象回路においてパイプライン処理が行われる間隔で前記複数のサンプルを供給し、
前記評価ユニットは、前記評価対象回路とともに、前記再構成ユニットに構成される、データ処理装置。
【請求項３】
請求項１または２において、前記制御ユニットは、複数セットの発見的なコンフィグレーションデータを出力し、前記再構成ユニットには、前記複数セットの発見的なコンフィグレーションデータにより、複数の評価対象回路が再構成され、
前記サンプルデータ供給ユニットは、前記複数の評価対象回路に対し並列に前記複数のサンプルを供給する、データ処理装置。
【請求項４】
請求項１ないし３のいずれかにおいて、前記評価ユニットから得られる評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成し、前記制御ユニットより使用可能とする生成ユニットをさらに有する、データ処理装置。
【請求項５】
請求項４において、前記生成ユニットは、前記再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項６】
請求項５において、前記複数セットのテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータである、データ処理装置。
【請求項７】
請求項５または６において、前記生成ユニットは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項８】
請求項５ないし７のいずれかにおいて、前記テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、
前記生成ユニットは、前記テンプレートコンフィグレーションデータの、前記固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項９】
回路を構成するための複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、前記内部配線による前記複数のエレメントの接続を変更すること、および／または前記複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、
前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより前記再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置であって、
前記制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成され、最適解として評価された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成する、データ処理装置。
【請求項１０】
回路を再構成可能な再構成ユニットを用いた解探索の方法であって、
前記再構成ユニットは、複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含み、前記内部配線による前記複数のエレメントの接続を変更すること、および／または、前記複数のエレメントの機能を変更することにより、回路を再構成可能であり、前記再構成ユニットの回路を再構成するためのコンフィグレーションデータは、前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含み、
当該方法は、
少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成することと、
前記発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給することと、
前記複数のサンプルに基づく前記評価対象回路の出力データの少なくとも一部を用いて前記評価対象回路の評価を得ることと、
前記評価を得ることの繰り返しにより、前記評価対象回路を再構成するための前記発見的なコンフィグレーションデータを解として探索することとを有する方法。
【請求項１１】
請求項１０において、前記サンプルを供給することは、前記評価対象回路においてパイプライン処理が行われる間隔で前記複数のサンプルを供給することを含み、
前記評価値を得ることは、前記評価対象回路とともに、前記再構成ユニットに構成される回路により評価値を得ることを含む、方法。
【請求項１２】
請求項１０または１１において、前記再構成することは、複数セットの発見的なコンフィグレーションデータにより、前記再構成ユニットに複数の評価対象回路を再構成することを含み、
前記サンプルを供給することは、前記複数の評価対象回路に対し並列に前記複数のサンプルを供給することを含む、方法。
【請求項１３】
請求項１０ないし１２のいずれかにおいて、前記評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することをさらに有する、方法。
【請求項１４】
請求項１３において、前記生成することは、前記再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１５】
請求項１４において、前記複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータである、方法。
【請求項１６】
請求項１４または１５において、前記生成することは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１７】
請求項１４ないし１６のいずれかにおいて、前記テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、
前記生成することは、前記テンプレートコンフィグレーションデータの、前記固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１８】
請求項１４ないし１７のいずれかにおいて、前世代のコンフィグレーションデータを、前記内部配線による前記複数のエレメントの接続を変更することを含めて、遺伝的アルゴリズムにより更新し、前記再構成ユニットにより評価し、前記複数のテンプレートコンフィグレーションデータを探索することをさらに含む、方法。
【請求項１】
回路を構成するための複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、前記内部配線による前記複数のエレメントの接続を変更すること、および／または前記複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、
前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより前記再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置であって、
前記制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成し、
当該データ処理装置は、さらに、
前記発見的なコンフィグレーションデータにより再構成される評価対象回路に対し入力データの複数のサンプルを供給するサンプルデータ供給ユニットと、
前記複数のサンプルに基づく前記評価対象回路の出力データの少なくとも一部を用いて前記評価対象回路の評価値を得る評価ユニットとを含む、データ処理装置。
【請求項２】
請求項１において、前記サンプルデータ供給ユニットは、前記評価対象回路においてパイプライン処理が行われる間隔で前記複数のサンプルを供給し、
前記評価ユニットは、前記評価対象回路とともに、前記再構成ユニットに構成される、データ処理装置。
【請求項３】
請求項１または２において、前記制御ユニットは、複数セットの発見的なコンフィグレーションデータを出力し、前記再構成ユニットには、前記複数セットの発見的なコンフィグレーションデータにより、複数の評価対象回路が再構成され、
前記サンプルデータ供給ユニットは、前記複数の評価対象回路に対し並列に前記複数のサンプルを供給する、データ処理装置。
【請求項４】
請求項１ないし３のいずれかにおいて、前記評価ユニットから得られる評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成し、前記制御ユニットより使用可能とする生成ユニットをさらに有する、データ処理装置。
【請求項５】
請求項４において、前記生成ユニットは、前記再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項６】
請求項５において、前記複数セットのテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータである、データ処理装置。
【請求項７】
請求項５または６において、前記生成ユニットは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項８】
請求項５ないし７のいずれかにおいて、前記テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、
前記生成ユニットは、前記テンプレートコンフィグレーションデータの、前記固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、前記次世代の発見的なコンフィグレーションデータを生成する機能を含む、データ処理装置。
【請求項９】
回路を構成するための複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含む再構成ユニットであって、前記内部配線による前記複数のエレメントの接続を変更すること、および／または前記複数のエレメントのそれぞれの機能を変更することにより、回路を再構成可能な再構成ユニットと、
前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含むコンフィグレーションデータにより前記再構成ユニットの回路を再構成する制御ユニットとを有するデータ処理装置であって、
前記制御ユニットは、少なくとも一部がメタヒューリスティックアルゴリズムにより生成され、最適解として評価された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成する、データ処理装置。
【請求項１０】
回路を再構成可能な再構成ユニットを用いた解探索の方法であって、
前記再構成ユニットは、複数のエレメントと、前記複数のエレメントを接続するための内部配線とを含み、前記内部配線による前記複数のエレメントの接続を変更すること、および／または、前記複数のエレメントの機能を変更することにより、回路を再構成可能であり、前記再構成ユニットの回路を再構成するためのコンフィグレーションデータは、前記複数のエレメントの接続情報および／または前記複数のエレメントの機能情報を含み、
当該方法は、
少なくとも一部がメタヒューリスティックアルゴリズムにより生成された発見的なコンフィグレーションデータにより前記再構成ユニットの少なくとも一部に回路を再構成することと、
前記発見的なコンフィグレーションデータにより再構成される評価対象回路に入力データの複数のサンプルを供給することと、
前記複数のサンプルに基づく前記評価対象回路の出力データの少なくとも一部を用いて前記評価対象回路の評価を得ることと、
前記評価を得ることの繰り返しにより、前記評価対象回路を再構成するための前記発見的なコンフィグレーションデータを解として探索することとを有する方法。
【請求項１１】
請求項１０において、前記サンプルを供給することは、前記評価対象回路においてパイプライン処理が行われる間隔で前記複数のサンプルを供給することを含み、
前記評価値を得ることは、前記評価対象回路とともに、前記再構成ユニットに構成される回路により評価値を得ることを含む、方法。
【請求項１２】
請求項１０または１１において、前記再構成することは、複数セットの発見的なコンフィグレーションデータにより、前記再構成ユニットに複数の評価対象回路を再構成することを含み、
前記サンプルを供給することは、前記複数の評価対象回路に対し並列に前記複数のサンプルを供給することを含む、方法。
【請求項１３】
請求項１０ないし１２のいずれかにおいて、前記評価値に基づいて、遺伝的アルゴリズムにより、次世代の発見的なコンフィグレーションデータを生成することをさらに有する、方法。
【請求項１４】
請求項１３において、前記生成することは、前記再構成ユニットに含まれる複数のエレメントの機能と、それら複数のエレメントを接続するための内部配線の接続とを予め規定した複数セットのテンプレートコンフィグレーションデータの少なくとも一部のセットを親の遺伝子として、遺伝的アルゴリズムにより、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１５】
請求項１４において、前記複数のテンプレートコンフィグレーションデータは、パイプライン処理を行う回路を再構成するためのコンフィグレーションデータである、方法。
【請求項１６】
請求項１４または１５において、前記生成することは、現世代の発見的なコンフィグレーションデータに含まれる複数のＰＥの機能を規定するパラメータを、遺伝的アルゴリズムにより更新し、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１７】
請求項１４ないし１６のいずれかにおいて、前記テンプレートコンフィグレーションデータは、解を求めようとしているシステムに固有の条件を反映するものであり、
前記生成することは、前記テンプレートコンフィグレーションデータの、前記固有の条件に関する部分を変えない範囲で、内部配線による複数のエレメントの接続に関する部分、および／または複数のエレメントのそれぞれの機能に関する部分を、遺伝的アルゴリズムによって変更することにより、前記次世代の発見的なコンフィグレーションデータを生成することを含む、方法。
【請求項１８】
請求項１４ないし１７のいずれかにおいて、前世代のコンフィグレーションデータを、前記内部配線による前記複数のエレメントの接続を変更することを含めて、遺伝的アルゴリズムにより更新し、前記再構成ユニットにより評価し、前記複数のテンプレートコンフィグレーションデータを探索することをさらに含む、方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００９−１０４４０３（Ｐ２００９−１０４４０３Ａ）
【公開日】平成２１年５月１４日（２００９．５．１４）
【国際特許分類】
【出願番号】特願２００７−２７５４９４（Ｐ２００７−２７５４９４）
【出願日】平成１９年１０月２３日（２００７．１０．２３）
【出願人】（５００２３８７８９）アイピーフレックス株式会社 (15)
【Ｆターム（参考）】
【公開日】平成２１年５月１４日（２００９．５．１４）
【国際特許分類】
【出願日】平成１９年１０月２３日（２００７．１０．２３）
【出願人】（５００２３８７８９）アイピーフレックス株式会社 (15)
【Ｆターム（参考）】
[ Back to top ]