再構成デバイス、処理配置方法及びプログラム
【課題】再構成デバイスの回路構成変更において、機構追加による回路規模を増やすことなく、処理内容に対する依存を回避しつつ回路構成変更期間を短縮する。
【解決手段】外部メモリ１０１は、内部に回路構成情報１０６を保持している。回路構成情報１０６は再構成デバイス１０５を構成する要素を動作させる設定群である。コンフィギュレーションコントローラ１０２は上記メモリ１０１から結線１０４を通じ回路構成情報１０６を取得する。取得した回路構成情報１０６は結線１０３を通じて再構成デバイス１０５へ送られる。
【解決手段】外部メモリ１０１は、内部に回路構成情報１０６を保持している。回路構成情報１０６は再構成デバイス１０５を構成する要素を動作させる設定群である。コンフィギュレーションコントローラ１０２は上記メモリ１０１から結線１０４を通じ回路構成情報１０６を取得する。取得した回路構成情報１０６は結線１０３を通じて再構成デバイス１０５へ送られる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、回路構成を変更することができる再構成デバイス、その処理配置方法等に関する。
【背景技術】
【０００２】
従来から製造後のＬＳＩ回路装置であっても内部の回路構成を変更することで、上記回路が行う処理内容を変更することが可能な再構成デバイスが提案されている。製造後のＬＳＩ回路装置でも処理を変更することが可能であるため、仕様変更などに伴うＬＳＩの作り直しを行わなくて済む。製造コストを抑えることが可能な点や開発期間が短縮可能な点で、現在様々な分野において再構成デバイスが使用されている。
【０００３】
再構成デバイスの構成として、多数のＬＵＴ（Ｌｏｏｋ−Ｕｐ−Ｔａｂｌｅ）を搭載したタイプや多数のプロセッシングエレメントを搭載したタイプが代表的である。また各々のエレメントにはマルチプレクサなどのスイッチングエレメントが接続されている。ここではＬＵＴやプロセッシングエレメント、スイッチングエレメントなどの各構成要素を動作させるための設定を総称し回路構成情報と呼んでいる。回路構成情報の生成方法としては様々あるが、一般に（１）テクノロジーマッピングと呼ばれる論理的な処理の割り当て、（２）各構成要素への物理的な配置、（３）各構成要素の経路決定、の工程に分けられ、順番に行われことが多い。上記三つの工程を経て最終的に回路構成情報が生成される。
【０００４】
（１）論理的な処理の割り当て工程では、処理を構成要素に割り当てることを行う。具体的には、各処理を物理的な構成要素を特定せずに論理的な構成要素に割り当てる。順序変更の指標としては、回路面積、動作速度、消費電力の観点が一般的である。（２）配置工程では、再構成デバイス内のどの構成要素でどの処理を行うかの物理的な割り当てを決定する。データの入出力関係にある処理が配置されているプロセッシングエレメント間の距離によって、データ通信に係るスイッチングエレメント数が異なるため、遅延時間（最大動作周波数）が大きく変化する。そのため、通常は入出力関係のある処理はできる限り近い距離のプロセッシングエレメントに配置させることが遅延時間を短縮する上で重要となる。（３）経路決定の工程では、データ通信の入出力関係にあるプロセッシングエレメント間のデータ通信のため、スイッチングエレメントによる経路を決定する。配置工程と比べ具体的な経路を決定するため、プロセッシングエレメント間の遅延時間を短縮した経路を決定することが重要となってくる。
【０００５】
近年、集積度の向上に伴い、再構成デバイスにおいて実行可能な処理の規模は増えている。しかし、最近ではそれにも増して、処理自体への要求が複雑化・高度化しており、一つの再構成デバイスで全ての処理を一度に行うことは難しい場合がある。これに対して、一つの再構成デバイスにおいて時分割で処理を順々に行う方法がある。より具体的にはまず所望の処理を分割し、分割した処理に対応した回路構成情報を生成する。その後、回路構成情報に基づいた再構成デバイスの回路構成の変更、処理を順々に行っていく。これにより、再構成デバイスで大きな規模の処理を行うことが可能となる。しかしながら、毎回全ての回路構成を変更させていては全体の処理時間が長くなってしまい、速度性能が劣化してしまう。また上記の処理分割数が多い場合も同様に、処理速度の劣化を生じさせてしまう。
【０００６】
この問題を解決するための方法として、マルチコンテキスト型の再構成デバイスがある。コンテキストとは、回路構成情報のことで、マルチコンテキスト型の再構成デバイスとは、複数の回路構成情報を格納するメモリを再構成デバイス内に搭載したものである。回路構成を変更する場合には、上記メモリを切り替えてデバイスを再構成することが可能であり、高速に切り換え可能なことで回路の再構成時間を大幅に短縮することが可能である。しかし、追加で回路構成情報用のメモリを搭載する必要があるため、回路規模が増大する問題がある。
【０００７】
これに対し、特許文献１では、再構成時間を短縮する方法としてスケルトン回路技術に基づいた手法が提案されている。この手法では、先行ベース回路と呼ばれる回路構成情報を、予め再構成デバイスに構成しておく。ここで先行ベース回路とは複数の回路構成情報において全てに共通する共通回路部分と、複数個の回路で互いに共通せず、かつ、再構成デバイス上で回路構成情報を共有しない非排他的独立回路部分からなる回路構成情報のことである。再構成デバイス上において回路の差分のみを部分的に再構成することにより、処理に必要な回路を構成するようにする。この方法は、マルチコンテキスト型に比べ、追加で構成用のメモリを必要としないため回路規模が増大はしない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第３５５８１１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、一般に再構成デバイスでは様々なアプリケーションを実行する可能性があり、アプリケーションによっては共通部分が少なくなる。また、再構成すべき回路構成情報の数もアプリケーションによって異なる。特許文献１で述べられている先行ベース回路部生成において、共通部分が少ないもしくは、回路構成情報の数が多く再構成デバイスの回路規模を大幅に超えてしまう場合には回路構成を変更するための期間を効率的に削減することが難しい。また、上述した処理配置工程においては、回路構成の変更期間を削減することに加え、データ入出力関係にあるプロセッシングエレメント間の距離が近い必要がある。入出力に係るプロセッシングエレメント間の通信距離が遠い場合、データ通信の遅延時間を増やし、結果として処理全体の期間を増大させてしまう。
【００１０】
本発明は上述した問題点に鑑みてなされたものであり、回路構成変更の順序を考慮することで、プロセッシングエレメント間のデータ通信遅延を抑えつつ回路規模を増やすことなく回路変更期間を効率的に削減することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の処理葉位置方法は、複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法であって、少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、再構成デバイスの構成要素の制約を入力する制約ステップと、前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとを有することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、データ通信の遅延時間を抑えつつ再構成に必要な設定数を減らすように回路構成情報を作成することで、回路規模を増やすことなく再構成デバイスの再構成期間を短縮することが可能である。
【図面の簡単な説明】
【００１３】
【図１】再構成デバイスを含む処理装置の構成例を示す図である。
【図２】再構成デバイスの構成例を示す図である。
【図３】再構成デバイスのエレメント間のデータ通信の手順例を示す図である。
【図４】プロセッシングエレメントの構成例を示す図である。
【図５】コンフィギュレーションコマンドのフォーマット例を示す図である。
【図６】プロセッシングエレメントのコンフィギュレーションメモリに格納される設定の概要例を示す図である。
【図７】設定を読み書きする手順を示すフローチャートである。
【図８】スイッチングエレメントの構成例を示す図である。
【図９】スイッチングエレメントのコンフィギュレーションメモリに格納される設定の概要例を示す図である。
【図１０】データフローにおける処理のプロセッシングエレメントへの配置例を示す図である。
【図１１】複数のデータフローを順次処理するタイムチャートである。
【図１２】処理配置に向けたプロセッシングエレメントアレイのモデル例を示す図である。
【図１３】第１の実施形態における複数のデータフローの処理配置を行うための概要例を示す図である。
【図１４】第１の実施形態における処理配置を行うためのフローチャートである。
【図１５】第２の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１６】第３の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１７】第４の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１８】第５の実施形態におけるデータフローの処理配置範囲限定を行うための概要例を示す図である。
【図１９】回路構成情報を作成する装置の構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１５】
先ず、本発明の第１の実施形態について説明する。第１の実施形態に係る再構成デバイスを有するシステムの全体構成の例を図１に示す。外部メモリ１０１は、内部に回路構成情報１０６を保持している。回路構成情報１０６は再構成デバイス１０５を構成する要素を動作させる設定群である。コンフィギュレーションコントローラ１０２は上記メモリ１０１から結線１０４を通じ回路構成情報１０６を取得する。取得した回路構成情報１０６は結線１０３を通じて再構成デバイス１０５へ送られる。ここで再構成デバイス１０５の例としてプロセッシングエレメントアレイとしている。また以下では、具体的にプロセッシングエレメントアレイ内の説明をするが、本発明は下記の各プロセッシングエレメントの構成や経路構成に限定されるものではない。
【００１６】
図２に、本実施形態における再構成デバイスであるプロセッシングエレメントアレイの概要図を示す。再構成デバイスには、８入力８出力の入出力処理手段であるスイッチングエレメント２０１が二次元格子状に配置されている。演算処理手段である４入力４出力のプロセッシングエレメント２０２が、スイッチングエレメント２０１の格子内に配置されている。スイッチングエレメント２０１ａ〜ｉの８入力８出力は１入力１出力を一組としてそれぞれ東西南北（右左下上）方向の、他の４つのスイッチングエレメント２０１と結線２０３ａおよび２０３ｂを介して夫々接続されている。
【００１７】
さらに、北東、南東、南西、北西方向の、それぞれ別の４つのプロセッシングエレメント２０２と結線２０４ａおよび２０４ｂを介して双方向に接続された構成を持つ。またスイッチングエレメント２０１ａ〜２０１ｉおよびプロセッシングエレメント２０２ａ〜２０２ｄは結線２０５で一方向に数珠繋ぎに接続されている。
【００１８】
結線２０３ａ、２０３ｂおよび結線２０４ａ、２０４ｂはスイッチングエレメント２０１やプロセッシングエレメント２０２の間で処理対象データを通信するために接続された結線である。結線２０５は、スイッチングエレメント２０１やプロセッシングエレメント２０２に設定を供給するための結線である。
【００１９】
上述の設定によって、スイッチングエレメント２０１においては処理対象データの入出力先が決定され、プロセッシングエレメント２０２においては処理対象データの入出力先や処理内容が決定される。なお、図２の各結線２０３ａ、２０３ｂ、２０４ａ、２０４ｂ、２０５の矢印の方向はデータの方向を示している。またスイッチングエレメント２０１ａ〜２０１ｉはそれぞれ同じ構成を有し、プロセッシングエレメント２０２ａ〜２０２ｄはそれぞれ同じ構成を有する。
【００２０】
ここで、各結線２０３ａ、２０３ｂ、２０４ａ、２０４ｂ、２０５の通信プロトコルの一例として、Ｖａｌｉｄ信号とＲｅａｄｙ信号による２線ハンドシェークを図３に示す。図３では送信側であるモジュールＡ３０１と受信側であるモジュールＢ３０２間はデータ信号線３０３、Ｖａｌｉｄ信号線３０４およびＲｅａｄｙ信号線３０５が接続されている。Ｖａｌｉｄ信号はＶａｌｉｄ信号線３０４を通じ送信側が受信側に対し送信可能状態を示す信号である。Ｒｅａｄｙ信号はＲｅａｄｙ信号線３０５を通じ受信側が送信側に対しデータ受信可能状態を示す信号である。本プロトコルではモジュールＡ３０１からのＶａｌｉｄ信号線３０４とモジュールＢ３０２のＲｅａｄｙ信号線３０５とが両方有効となるクロック立ち上がりのタイミングでデータ信号線３０３のデータがモジュールＡ３０１からモジュールＢ３０２へと送信される。図３の波形中では３０６ａのタイミングでデータＡが、３０６ｂのタイミングでデータＢが、３０６ｃのタイミングでデータＣ、３０６ｄのタイミングでデータＤがモジュールＡ３０１からモジュールＢ３０２へと転送されている。
【００２１】
プロセッシングエレメント２０２の構成を図４に示す。プロセッシングエレメント２０２は、コンフィギュレーションユニット４０１、インプットユニット４０２、コンピュテーショナルユニット４０３、アウトプットユニット４０４、テンポラリーバッファ４０５で構成されている。前記コンフィギュレーションユニット４０１はプロセッシングエレメント２０２の動作内容を決定するための設定の管理を行う。前記インプットユニット４０２はコンフィギュレーションユニット４０１の設定に基づき、入力処理を行う。コンピュテーショナルユニット４０３はコンフィギュレーションユニット４０１の設定に基づき、演算処理を行う。また、コンピュテーショナルユニット４０３は、再度コンピュテーショナルユニット４０３に入力するためテンポラリーバッファ４０５に処理された結果を保持することが可能である。アウトプットユニット４０４はコンフィギュレーションユニット４０１の設定に基づき、出力処理を行う。
【００２２】
上記プロセッシングエレメント２０２の動作をより具体的に説明する。インプットユニット４０２はコンフィギュレーションユニット４０１から入力先を決定するための設定情報を、結線４０６を通じて取得する。取得した設定情報はどの入力ポートを介して外部接続されているモジュールと通信を行うかが指定されている。その情報を元に、結線２０４ａ−ｎｅ、２０４ａ−ｓｅ、２０４ａ−ｓｗ、２０４ａ−ｎｗ、を通じて処理対象であるデータを取得する。ここで参照符号のｎｅ，ｓｅ、ｓｗ，ｎｗはそれぞれ方向を示しており、結線２０４ａ−ｎｅは北東に配置されたスイッチングエレメントと接続されている。また、２０４ａ−ｓｅは南東に配置されたスイッチングエレメントと接続されている。２０４ａ−ｓｗは南西に配置されたスイッチングエレメントと接続されている。２０４ａ−ｎｗは北西に配置されたスイッチングエレメントと接続されている。取得したデータは、結線４０９を通してコンピュテーショナルユニット４０３に送られる。
【００２３】
コンピュテーショナルユニット４０３は、コンフィギュレーションユニット４０１から処理内容を決定するための設定情報を、結線４０７を通じて取得する。取得した設定情報に基づいてインプットユニット４０２から送られてくるデータを取得し、処理を行う。処理したデータは結線４１０を通じてアウトプットユニット４０４に送られる。
【００２４】
コンピュテーショナルユニット４０３は、少なくとも一つの演算器を保持している。上記演算器は、例えば、加減算器、比較器、乗算器、除算器、論理演算器等の演算器、または、これらの組合せからなる演算器、さらにはこれらと他の演算器の組合せからなる演算器などである。以下では具体的な例として、上記コンピュテーショナルユニット４０３では、積和演算と比較演算処理が行え、一度の演算でどちらかを一方を選択的に行うことができるものとし説明する。積和演算では、ａ・ｂ＋ｃ・ｄの処理を行い、比較演算では、もしａ＞ｂならばｃを出力、そうでなければｄを出力するといった処理を行う。また、コンピュテーショナルユニット４０３は一度の入力に対して、上記演算器を繰り返し使用することが可能な構成となっている。繰り返しで使用する場合は一旦上記演算器で使用された処理結果を、結線４１２を通して、テンポラリーバッファに保存し、その後、結線４１１を通して、再度コンピュテーショナルユニット４０３に入力する。再度入力されたデータに対して、新たに上記演算器にて処理を行う。後で詳細を述べるが、上記設定とは上記演算の種類や繰り返し処理、またそれぞれの処理で必要な変数ａ、ｂ、ｃ、ｄはどの値を参照するか、また固定値ならばその値を指定することを意味する。
【００２５】
アウトプットユニット４０４は、処理したデータの出力先を示す設定情報を結線４０８を通じて取得する。取得した設定情報は、どの出力ポートを介してスイッチングエレメントと通信を行うかが指定されている。その情報を元に、結線２０４ｂ−ｎｅ、２０４ｂ−ｓｅ、２０４ｂ−ｓｗ、２０４ｂ−ｎｗ、を通じてスイッチングエレメントへ出力する。ここで結線２０４ｂ−ｎｅは北東に配置されたスイッチングエレメントと接続されている。また、２０４ｂ−ｓｅは南東に配置されたスイッチングエレメントと接続されている。２０４ｂ−ｓｗは南西に配置されたスイッチングエレメントと接続されている。２０４ｂ−ｎｗは北西に配置されたスイッチングエレメントと接続されている。
【００２６】
次にコンフィギュレーションユニット４０１の動作について説明する。コンフィギュレーションユニット４０１はプロセッシングエレメント２０２毎にユニークなＩＤを保持している。コンフィギュレーションユニットは入力側の結線２０５より送られてくる設定情報を取得し、コンフィギュレーションユニット内で処理し、出力側の結線２０５を通して設定を出力する。コンフィギュレーションユニット４０１は自らのＩＤに対応する設定を格納するためコンフィギュレーションメモリ４１３を有している。
【００２７】
図５にコンフィギュレーションユニットに送受信される、設定のためのコンフィギュレーションコマンド５０１を示す。コンフィギュレーションコマンド５０１はリード／ライトモード５０２、ＩＤ５０３、コンフィギュレーションアドレス５０４、設定値５０５で構成されている。リード／ライトモード５０２はコンフィギュレーションコマンドの読み書きの処理を決定する信号である。ＩＤ５０３は処理対象のプロセッシングエレメント２０２を決める信号である。コンフィギュレーションアドレス５０４はコンフィギュレーションユニット４０１中の設定が保持されているメモリ内の番地を指定する信号である。設定値５０５は実際の設定値を表す信号である。図５中のビット幅を示すＭ、Ｎ、Ｏ、Ｐは実際に構成するアーキテクチャによって決められる値である。以下では上述した構成に基づく設定に関してより具体的に説明する。
【００２８】
図６中の６０１はコンフィギュレーションメモリ４１３のアドレスを示しており、図５のコンフィギュレーションアドレス５０４で指定されるアドレスに相当する。６０２は実際の設定値を示しており、図５の設定値５０５に相当する。本実施形態はこれら一つ一つを設定と読んでいるが、本発明は上述の単位に限るものではない。図ではインプットユニット４０２、コンピュテーショナルユニット４０３、アウトプットユニット４０４に関する設定がコンフィギュレーションメモリ４１３に保持されている例を示している。
【００２９】
アドレス０ｘ００００＿００００（“０ｘ”は１６進数を示している）で示した設定値は、インプットユニット４０２における入力先を決定するための設定情報で、この値に応じて所定の入力先が決まる。アドレス０ｘ００００＿０００４で示したイタレーションナンバーは、コンピュテーショナルユニット４０３における、演算の繰り返し回数を決定するための設定情報で、値に応じて演算の繰り返し回数が決まる。本実施形態では４回までの演算を想定している。
【００３０】
アドレス０ｘ００００＿０００８で示したオペレーションセッティングは１度目の演算で行う、演算の種類を決定するための設定で、値に応じて積和演算か比較演算かが決まる。アドレス０ｘ００００＿０００ｃで示したバリアブルセッティングは１度目の演算で、変数ａの値の参照先を決めるための設定である。参照先としては、入力ポートからの入力値、コンフィギュレーションメモリ４１３に保持されている固定値、以前の計算結果が保持されているテンポラリーバッファの値がある。この値に応じて、上記いずれかの値がこの変数ａに入力される。また０ｘ００００＿０００ｃと同様に、０ｘ００００＿００１０、０ｘ００００＿００１４、０ｘ００００＿００１８で示したバリアブルセッティングはそれぞれ、１度目の演算における変数ｂ、ｃ、ｄの値の参照先を決めるための設定である。
【００３１】
次に０ｘ００００＿００１ｃで示したパラメータは、１度目の演算において０ｘ００００＿０００ｃで指定された参照先が固定値の場合の、変数ａのための固定値である。０ｘ００００＿００１ｃと同様に０ｘ００００＿００２０、０ｘ００００＿００２４、０ｘ００００＿００２８で示した固定値は、それぞれ１度目の演算で変数ｂ、ｃ、ｄ、で使用される場合の値である。
【００３２】
続く０ｘ００００＿００２ｃ〜から０ｘ００００＿００９４は、上記０ｘ００００＿０００８〜０ｘ００００＿００２８で示した１度目の演算に係る設定と同様にそれぞれ、２度目、３度目、４度目の設定値を示している。最後に０ｘ００００＿００９８で示したアウトプットセレクトバリューは、アウトプットユニット４０４における出力先を決定するための設定値で、値に応じて所定の出力先が決まる。
【００３３】
次にコンフィギュレーションユニットで行われる処理フローを図７に示す。ステップＳ７０１では、コンフィギュレーションコマンド５０１を入力する。ステップＳ７０２では、入力されたコンフィギュレーションコマンド５０１で指定されたＩＤ５０３が、コンフィギュレーションユニット４０１の持つ自身のＩＤと一致するかどうかを判断する。もし、ステップＳ７０２で自身のＩＤと違うと判断された場合はステップＳ７１１、７１２で、入力されたコンフィギュレーションコマンド５０１に対して、何も処理せずにそのまま出力する。もし、自身のＩＤと一致する場合は、次にステップＳ７０３でリード／ライトモード５０２の値がリードモードかどうかを判断する。リードモードでなければステップＳ７０７でライトモードかどうかを判断する。いずれのモードでもない場合はステップＳ７１１、７１２で何も処理せずにそのまま出力する。もし、リードモードと判断された場合は、ステップＳ７０４において、コンフィギュレーションメモリ４１３からコンフィギュレーションアドレス５０４で指定されたデータを読み出す。その後、ステップＳ７０５にて、入力されたコンフィギュレーションコマンド５０１の設定値５０５に読み出したデータを書き込み、ステップＳ７０６でそのコンフィギュレーションコマンド５０１を出力する。ライトモードと判断された場合は、ステップＳ７０８にて入力されたコンフィギュレーションコマンド５０１の設定値５０５をコンフィギュレーションアドレス５０４で指定されたコンフィギュレーションメモリ４１３に書き込む。次にステップＳ７０９では、入力されたコンフィギュレーションコマンド５０１の値を変更せず、ステップＳ７１０にて、そのまま出力する。一度のコンフィギュレーションコマンドで一つの設定値５０５を変更することが可能であり、順次コンフィギュレーションコマンドを送信し、必要な設定値を全て変更することで所望の処理を実現する。つまり、この設定数が処理内容の切り替え時間を決めていることとなる。
【００３４】
スイッチングエレメント２０１の構成を図８に示す。スイッチングエレメント２０１は、コンフィギュレーションユニット８０１と、クロスバースイッチ８０２で構成される。コンフィギュレーションユニット８０１はデータを転送する接続先を決定するための設定値の管理をする。クロスバースイッチ８０２はコンフィギュレーションユニット８０１の設定に基づき一対一に入出力を接続する。プロセッシングエレメント２０２のコンフィギュレーションユニット４０１と同様、コンフィギュレーションユニット８０１はスイッチングエレメント２０１毎にユニークなＩＤを保持している。コンフィギュレーションユニットは入力側の結線２０５より送られてくる設定情報を取得し、コンフィギュレーションユニット内で処理を行い、出力側の結線２０５を通して設定値を出力する。コンフィギュレーションユニットは上記取得した設定をコンフィギュレーションメモリ８０４に保持している。コンフィギュレーションユニットのコンフィギュレーションコマンドとその処理フローは、図５に示したフォーマット、および図７に示した処理フローと同様である。クロスバースイッチ８０２はコンフィギュレーションユニット８０１からデータの入出力先を決定する設定情報を、結線８０３を通じて取得する。スイッチングエレメント２０１は取得した設定値に基づき結線２０３ａ−ｗ、−ｓ、２０３ｂ−ｅ、−ｎ、結線２０４ｂ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗを通じてデータを取得する。取得したデータは、接続されている結線２０３ａ−ｅ、−ｎ、２０３ｂ−ｗ、−ｓ、結線２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗを通じて渡す。
【００３５】
ここで結線２０３ａ−ｗ、−ｓはそれぞれ西、南に配置されたスイッチングエレメントと接続されていることを意味する。２０３ｂ−ｅ、−ｎはそれぞれ東、北に配置されたスイッチングエレメントと接続されていることを意味している。
【００３６】
結線２０３ａ−ｅ、−ｎはそれぞれ東、北に配置されたスイッチングエレメントと接続されていることを意味する。２０３ｂ−ｗ、−ｓはそれぞれ西、南に配置されたスイッチングエレメントと接続されていることを意味している。
【００３７】
結線２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗはそれぞれ北東、南東、南西、北西に配置されたスイッチングエレメントと接続されていることを意味している。結線２０４ｂ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗはそれぞれ北東、南東、南西、北西に配置されたスイッチングエレメントと接続されていることを意味している。
【００３８】
図９にコンフィギュレーションメモリ８０４に保持されている、スイッチングエレメント２０１におけるクロスバースイッチ８０２の入出力の接続に関する設定例を示す。９０１はメモリのアドレスを示しており、図５のコンフィギュレーションアドレス５０４で指定されるアドレスに相当する。９０２は設定値を示しており、図５の設定値５０５を示している。アドレス０ｘ００００＿００００で示したコネクション設定は結線２０３ａ−ｗからの入力を２０３ａ−ｅ、ｎ、２０３ｂ−ｗ、−ｓ、２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗのいずれに出力するかを決定するための設定値である。続く、０ｘ００００＿０００４は結線２０３ａ−ｓからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿０００８は結線２０３ｂ−ｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿０００ｃは結線２０３ｂ−ｎからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１０は結線２０４ｂ−ｎｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１４は結線２０４ｂ−ｓｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１８は結線２０４ｂ−ｓｗからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１ｃは結線２０４ｂ−ｎｗからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。
【００３９】
次にデータフローの構成要素への配置の概要について図１０を用いて説明する。ここで、配置とはデータフローの処理を、所定の配置で規定されるプロセッシングエレメントで実行させるかを決定することを意味している。図１０ではデータフロー１００１のノード１００２、１００３、１００４、１００５はそれぞれ一つのプロセッシングエレメントで行われる処理である。これらノード１００２、１００３、１００４、１００５に対応する処理を、再構成デバイス１０５のプロセッシングエレメント２０２−１、−２、−３、−４へ配置する例を示している。設定１００６、１００７、１００８、１００９はそれぞれ１００２、１００３、１００４、１００５の処理内容に対応したアドレス６０１、設定値６０２で構成されている。なお、各ノードで行う処理内容の割り当ては済んでおり、設定１００６、１００７、１００８、１００９は予め決められているものとしている。配置を決定することで、各設定の書き込み先であるプロセッシングエレメントに対応したＩＤ５０３を決定することが可能となる。
【００４０】
上述した再構成デバイスの構成を複数種類変更して所望の処理を実現するためのタイムチャート例を図１１に示す。図１１では同一の再構成デバイスで複数の異なるデータフローＡ〜Ｚを順に実行しているタイムチャートを示している。本実施形態で扱うデータフローとは、再構成デバイスのプロセッシングエレメントに配置可能な単位で構成されたデータフローのことである。各データフローを処理するための設定は予め生成しておく。再構成デバイスに対して予め生成された設定に基づき再構成デバイスを再構成し、その構成のもとで処理をするという一連の処理が、所定の順序で順々に行われる。
【００４１】
以下ではデータフローＡを配置済みとし、データフローＢを配置対象として説明する。具体的には、配置済みのデータフローＡを実行するための設定値を参照し、データフローＢの処理配置を決定する。データフローＡの処理配置を参照しデータフローＢの処理配置を決定した後、次はデータフローＢを配置済みとし、データフローＣを配置対象とする。具体的にはデータフローＢの処理配置を決定した時と同様に、処理配置済みのデータフローＢを実行するための設定値を参照し、データフローＣの処理配置を決定する。上記の手順を順々に繰り返すことでＡからＺまでのデータフローの配置を行うことが可能となる。
【００４２】
一般に、配置問題は配置のみを決定するだけでも解空間が広い。そのため、詳細配線決定を同時に行うと、良い解を算出できないだけでなく、解自体を算出できない可能性が出てくる。そのため本配置方法では詳細な配線情報は決定せず、図１２に示す配置モデルに基づく概略の距離を用いて配置を決定する。本実施形態では配置モデルとしてプロセッシングエレメントアレイをプロセッシングエレメントの位置に基づいたマンハッタンモデルを用いている。プロセッシングエレメント間のマンハッタン距離を指標として解を算出する。ただし、本発明は、概略の距離としてはマンハッタン距離に限定されるものではない。指標として、詳細配線を同時に行うことも可能である。また、本実施形態では配置モデルとしてマンハッタンモデルに基づく配置モデルを用いたが、それに限るものではない。アーキテクチャに依存したモデルやユークリッド空間に基づいたモデルでも良い。
【００４３】
図１２に示すように、スイッチングエレメント２０１とプロセッシングエレメント２０２で構成される再構成デバイス１０５に対し、配置モデル１２０１を定義する。配置モデル１２０１はプロセッシングエレメント２０２のみで構成しており、指標となる距離としては、横方向のプロセッシングエレメント間の距離１２０２と縦方向の距離１２０３で表す。本実施形態では縦横の距離は等しいものとしているが、異なっても良い。また本発明で扱う距離とは、物理的な長さであっても良いし、各エレメント間の通信に要する時間の長さであっても良く、これらに限るものではない。
【００４４】
次に、図１２の配置モデルを用いて、図１１のタイムチャートで示した処理の切り替わりに注目した処理のプロセッシングエレメントへの配置方法について述べる。
【００４５】
図１３では本実施形態における配置の概要を示している。データフローＡはノード１３０１、１３０２、１３０３、１３０４として表される処理で構成されており、設定１３０５、１３０６、１３０７、１３０８はそれぞれのノードで行う処理の設定である。またフロー１３０９はノード１３０１と１３０２間のデータ入出力関係を表している。フロー１３１０はノード１３０１と１３０３間のデータ入出力関係を表している。フロー１３１１はノード１３０２と１３０４間のデータ入出力関係を表している。フロー１３１２はノード１３０３と１３０４間のデータ入出力関係を表している。
【００４６】
データフローＢはノード１３１３、１３１４、１３１５、１３１６として表される処理で構成されており、設定１３１７、１３１８、１３１９、１３２０はそれぞれのノードで行う処理の設定である。またフロー１３２１はノード１３１３と１３１５間のデータ入出力関係を表している。フロー１３２２はノード１３１４と１３１５間のデータ入出力関係を表している。フロー１３２３はノード１３１５と１３１６間のデータ入出力関係を表している。
【００４７】
ここではプロセッシングエレメントアレイの配置モデル１２０１内の領域１３２４に上述のデータフローＡ、Ｂの処理を配置させることを想定している。本実施形態ではプロセッシングエレメントアレイ内の一部への配置について述べるが、それに限られるものではなく、複数の部分や全体への配置でも良い。１３２５は上記の領域１３２４のデータフローＡ向けの処理配置例を表している。１３２６は上記の領域１３２６のデータフローＢ向けの処理配置例を表している。各々の処理配置１３２５、１３２６内のプロセッシングエレメント１３２７、１３２８、１３２９、１３３０はそれぞれ物理的に同じプロセッシングエレメントを表している。処理配置１３２５では、データフローＡにおいてはノード１３０１の処理をプロセッシングエレメント１３２７に配置させている。ノード１３０２の処理をプロセッシングエレメント１３２９に配置させている。ノード１３０３の処理をプロセッシングエレメント１３２８に配置させている。ノード１３０４の処理をプロセッシングエレメント１３３０に配置させている。またプロセッシングエレメント間のデータ通信の距離を、フロー１３０９は距離１３３１、フロー１３１０は距離１３３２、フロー１３１１は距離１３３３、フロー１３１２は距離１３３４として表している。
【００４８】
続いてデータフローＢに関しては、ノード１３１３の処理をプロセッシングエレメント１３２７に配置させている。ノード１３１４の処理をプロセッシングエレメント１３２８に配置させている。ノード１３１５の処理をプロセッシングエレメント１３２９に配置させている。ノード１３１６の処理をプロセッシングエレメント１３３０に配置させている。またプロセッシングエレメント間のデータ通信の距離を、フロー１３２１は距離１３３５、フロー１３２２は距離１３３６および１３３７、フロー１３２３は距離１３３８として表している。
【００４９】
データフローＡからデータフローＢに処理が切り替わる際に、プロセッシングエレメント１３２７においては、設定変更１３３９で示すように設定１３０５から設定１３１７へと設定が変更される。プロセッシングエレメント１３２８においては、設定変更１３４１で示すように設定１３０７から設定１３１８へと設定が変更される。プロセッシングエレメント１３２９においては、設定変更１３３９で示すように設定１３０６から設定１３１９へと設定が変更される。プロセッシングエレメント１３３０においては、設定変更１３３９で示すように設定１３０８から設定１３２０へと設定が変更される。
【００５０】
本実施形態では、配置を行う上で、処理が切り替わる際の設定変更数とデータフローの依存関係に基づく構成要素間の距離の二つの要素に注目する。
【００５１】
本実施形態で用いる図１３の例ではデータフローＡは既に処理配置済みであり、データフローＡに関する各プロセッシングエレメントの各メモリ内の設定値は固定値として与えられるものとする。データフローＢに関しては処理配置対象である。つまりデータフローの処理順序は決まっており、既に配置済みの配置情報をもとに次に処理されるデータフローの配置を決定することを想定している。
【００５２】
図１９は、データフローからデータフローへ処理を切り替えるための回路構成情報１０６を生成するための装置のブロック構成図を示している。図１９において、２５０１は装置全体の制御を司るＣＰＵである。２５０２はブートプログラムやＢＩＯＳを記憶しているＲＯＭである。２５０３はＣＰＵ２５０１のワークエリアとして利用され、且つ、ＯＳ（オペレーティングシステム）、アプリケーションを格納するためのＲＡＭである。２５０４はＯＳ、回路構成情報１０６を作成するためのアプリケーション、ならびに、様々なデータを格納するためのハードディスクドライブ（ＨＤＤ）である。２５０５はキーボード、２５０６はマウスであり、ユーザインタフェースとして機能する。２５０７は内部にビデオメモリ及び表示コントローラを内蔵する表示制御部であり、２５０８は表示制御部２５０７からの映像信号を受信し、表示するための表示装置である。２５０９は各種外部デバイスと通信するインタフェースであり、例えば、図１に示した外部メモリ１０１を接続することで、本装置が作成した回路構成情報１０６をその外部メモリ１０１に書込むことになる。
【００５３】
上記構成において、本装置に電源が投入されると、ＣＰＵ２５０１はＲＯＭ２５０２に格納されたブートプログラムを実行し、ＨＤＤ２５０４に格納されたＯＳをＲＡＭにロードし、その後、回路構成情報１０６を作成するアプリケーションを起動することで、本装置が回路構成情報作成装置として機能することになる。
【００５４】
以下、本発明を実施するための回路構成情報作成装置として機能する本装置の処理を、図１４のフローチャートを用いて説明する。本手順はシミュレーテッドアニーリングに基づく処理配置方法の例を示すが、本発明は上記手法のみに限定されるものではなく、遺伝的アルゴリズムなどのさまざまな近似解法や線形計画法や非線形計画法など数値最適化法でも良い。また、配置する問題の規模に応じて方法を変えてもよい。
【００５５】
図１３に示す各データフローを表すインデックスをｉ、ノードのインデックスをｊ、図６のアドレス６０１や図９で示したアドレス９０１に相当するエレメント内で保持しているメモリのコンフィギュレーションアドレスをｋとする。また、各ノードｊ間のフローに関するインデックスをｌとする。上記より各メモリ内の設定値はｕi,j,kと表すことができる。またｉ番目のデータフローにおける、フローｌの出発側のノードをＳi,l、到着側のノードをｄi,lとする。
【００５６】
また、図１２に示す通り、各プロセッシングエレメントを表すインデックスをｒとする。各データフローｉの各ノードｊの配置位置はｘi,jおよびｙi,jと表すことができる。本実施形態では同じプロセッシングエレメントに同じデータフロー内の異なる処理を配置することはしないため、ｘi,j、ｙi,jは、ノードｊごとに必ず異なる。つまり、同じプロセッシングエレメントに異なる処理を配置しない。
【００５７】
ここで処理配置済みのデータフローをｉ０、処理配置対象のデータフローをｉ１とする。初めに、ステップＳ１４０１では複数のデータフローとその順序関係(ｉの順序)を入力する。処理配置済みのデータフローに関しては、設定値ｕi0,j,kと共に配置情報ｘi0,j、ｙi0,jも入力する。
【００５８】
次に、ステップＳ１４０２で要求仕様とハードウェアの制約の条件を入力する。ここでハードウェア制約条件とは、ヘテロ構成に伴う各プロセッシングエレメントが個別に持つ構成情報や、処理によって発生する発熱量などの制限などハードウェア構成上の制約となりうるものである。また要求仕様とは、プロセッシングエレメント間の距離制限やステップＳ１４０６で後述する設定変更数と距離の要素の優先度合の割合などハードウェア使用上で制限すべき項目である。ただし、本発明は上述の制約のみに限られるものではない。
【００５９】
続いてステップＳ１４０３では対象となるデータフローの処理配置を行う。初期の処理の配置においては、ランダムに配置する、ないしはデータフローの深さ方向とプロセッシングエレメントアレイの入出力方向とを連動させて処理を配置させる方法があるが、これらの方法に限られるものではない。初期の配置でない場合は、シミュレーテッドアニーリングに基づき処理の配置を変更する。本実施形態では、処理配置である対象のデータフローＢに関して初期処理配置、ないしは処理配置変更を行う。処理配置済みのデータフローＡに関しては、制約に基づき処理配置の変更は行わない。
【００６０】
ステップＳ１４０４では、処理配置結果がステップＳ１４０３で入力した要求仕様を満たしているか判断する。以下の式に示すように、制約を満たしていれば、ペナルティ変数ｐ0を０とし、違反している場合はペナルティ変数ｐ0をペナルティ値Ｃp0とする。
【００６１】
【数１】
【００６２】
ここで本実施形態では、違反があった場合に一律Ｃp0は定数値として扱っているが、違反項目に応じた変数値としてもよい。ステップＳ１４０５では、処理配置結果がステップＳ１３０２で入力したハードウェア制約条件を満たしているかを判断する。
【００６３】
以下の式に示すように、制約を満たしていれば、ペナルティ変数ｐ1を０とし、違反している場合はペナルティ変数ｐ1をペナルティ値Ｃp1とする。
【００６４】
【数２】
【００６５】
ここで本実施形態では、違反があった場合に一律Ｃp1は定数値として扱っているが、違反項目に応じた変数値としてもよい。次にステップＳ１４０６では、対象となるデータフロー変更間における設定変更数と配置に基づく距離の算出を行い、評価値を計算する。まず設定変更数の算出について説明する。図１３の例で説明するとの設定変更１３３９、１３４０、１３４１、１３４２の際に変更の必要がある設定数である。
【００６６】
より具体的には、処理配置済みのデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα1を設定変更数に加える。上述の値が一致していれば何も加えない。
【００６７】
ここで、プロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【００６８】
【数３】
【００６９】
ここでα1は通常１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。図７で示した通り、一度のコンフィギュレーションコマンドで一つの設定値を変更することができることから、この数が少なくなれば、処理の切り替え時間を削減することが可能となる。
【００７０】
続いて距離の算出について述べる。距離とは、配置対象であるデータフローＢにおける距離１３３５、１３３６、１３３７、１３３８の合計量である。ステップＳ１４０３での配置とデータフローのデータ入出力関係に基づいて、以下の式で距離を表すことが可能である。
【００７１】
【数４】
【００７２】
ここでκ1l、λ1lはノード間の距離のｘ、ｙ毎の重みであって、ノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本ステップで評価値算出する際の式は上述の式より、以下と定義する。
【００７３】
【数５】
【００７４】
ここで、δはステップＳ１４０２で与えた設定変更数と距離のどちらを優先させるかの割合を表す指標である。つまり、要求仕様とハードウェア制約条件を満たしつつ、また距離が少なく、再構成に必要な設定変更数が少なくなるほど上記評価値は小さくなる。
【００７５】
最後にステップＳ１４０７では、シミュレーテッドアニーリングに基づき目標達成したかを判断し、目標を達成した場合は終了する。目標未達の場合はステップＳ１４０３に戻り、ステップＳ１４０３〜Ｓ１４０７を繰り返し行う。ここで、目標値とは十分良い結果が得られるまで、もしくは予定された計算時間に達するまで繰り返す。
【００７６】
以上の結果、回路構成情報１０６がＨＤＤ２５０４に生成されるので、後はインタフェース２５０９を介して、利用する外部メモリ１０１にそれを書き出し、実製品に搭載すれば良いことになる。
【００７７】
なお、上記実施形態では、回路構成情報１０６を、外部装置（図１７）にて作成する例を示した。これは以降に説明する全実施形態でも同じである。また、コンフィギュレーションコントローラ１０２が外部装置の代わりに、図１３の処理を実行し、回路構成情報１０６を作成しても構わない。例えば、外部メモリ１０１に複数のデータフロー毎の設定（必要なプロセッサ数と各プロセッサの処理パラメータ）を保持させ、コンフィギュレーションコントローラ１０２が複数のデータフローの設定に基づいて回路構成１０６を作成すればよい。係る点も、以降に説明する全実施形態にも適用できることである。
【００７８】
一般的な再構成デバイスにおけるデータフローのプロセッシングエレメントへの処理配置方法では設定変更数を意識しないため、データフローの処理変更間で全ての設定を変更する必要が生じる。
【００７９】
本実施形態では、データフローの処理順に注目し、距離に加え設定変更の合計数が少なくすることで、設定変更数削減を効果的に行うことが可能となる。
【００８０】
次に、本発明の第２の実施形態について説明する。第２の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１５に示す。本実施形態では再構成デバイスの設定を変更において、各データフローの処理内容自体は決まっているが、その変更順序が不定で、状況や入力データなどに応じて変わる場合の処理配置に関する実施形態である。
【００８１】
タイムチャート１５０１における期間１５０２ではデータフローＡに関する処理が行われ、期間１５０４、１５０８ではデータフローＣに関する処理が行われ、期間１５０６ではデータフローＢに関する処理が行われる。期間１５０３ではデータフローＡからデータフローＣの設定変更が行われる。期間１５０５ではデータフローＣからデータフローＢの設定変更が行われる。期間１５０７ではデータフローＢからデータフローＣの設定変更が行われる。本実施形態では、データフローＡ、Ｂ、Ｃの処理変更の順序が一定でないため、それぞれのデータフロー間の全ての設定変更を考慮して処理の配置を行う必要がある。
【００８２】
図中の１５０９、１５２２、１４３１はそれぞれデータフローＡ、Ｂ、Ｃにおけるプロセッシングエレメントの配置例を示しており、ここではこれら全てのデータフローの処理の配置を一度に一括して行う。なお配置例１５０９、１５２２、１５３１中のプロセッシングエレメント１５１０、１５１１、１５１２、１５１３はそれぞれ物理的に同じプロセッシングエレメントを指す。
【００８３】
設定１５１４、１５１５、１５１６、１５１７は、それぞれデータフローＡの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。設定１５２３、１５２４、１５２５、１５２６は、それぞれデータフローＢの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。設定１５３２、１５３３、１５３４、１５３５は、それぞれデータフローＣの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。ここで上記の設定とは実施形態１と同様に、図６で説明した設定のことである。本実施形態では、データフローＡ、Ｂ間、Ｂ、Ｃ間、Ｃ、Ａ間のプロセッシングエレメント１５１０、１５１１、１５１２、１５１３でデータフロー変更に必要な合計の設定変更数と各プロセッシングエレメント間接続の合計距離に注目する。
【００８４】
上記合計数および距離数が図１４で示したフローチャート１４０６で示す評価値に加える設定変更数を後述する評価値として算出することで、距離を考慮した、再構成デバイスの再構成時の設定変更数の削減を行う。
【００８５】
なお、データフローＡ、Ｂ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５３９で表している。またデータフローＢ、Ｃ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５４０で表している。データフローＣ、Ａ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５４１で表している。
【００８６】
本実施形態と第１の実施形態との違いは、同時に複数のデータフローの処理配置を行う点にある。図１４のステップＳ１４０１では、複数のデータフローを入力すると同時に、処理順序が任意であることを入力する。図１４のステップＳ１４０４で行う処理配置では、処理配置対象であるデータフローＡ、Ｂ、Ｃ全てに対して処理配置を行う。図１４のステップＳ１４０６で第１の実施形態に対して以下の違いがある。
【００８７】
処理配置対象のデータフローｉ０における、設定値ｕio,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα2を設定変更数に加える。また、処理配置対象のデータフローｉ１における、設定値ｕi1,j,kと、処理配置対象のデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi2,j,kの値が一致していなければβ2を設定変更数に加える。さらに、処理配置対象のデータフローｉ２における、設定値ｕi2,j,kと、処理配置対象のデータフローｉ０における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi0,j,kの値が一致していなければγ2を設定変更数に加える。上述以外で、設定値が一致していれ場合は何も加えない。
【００８８】
ここで、プロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【００８９】
データフローが切り替わる際に、同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【００９０】
【数６】
【００９１】
ここでα2、β2、γ2は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【００９２】
また距離については以下の違いがある。図１５で示した例では、距離は、距離１５１８、１５１９、１５２０、１５２１、１５２７、１５２８、１５２９、１５３０、１５３６、１５３７、１５３８の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【００９３】
【数７】
【００９４】
ここでκ２i,l、λ２i,lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本実施形態により、全てのデータフロー間を考慮することで、処理の実行順序が不定な場合でも、距離を考慮したうえで平均して設定変更数削減効果が得られる。
【００９５】
次に、本発明の第３の実施形態について説明する。第３の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１６に示す。本実施形態では既に複数のデータフローの処理順序およびそれぞれの処理配置も決まっている場合を想定している。上述の処理順序における任意のデータフローの処理間に、挿入前後の処理配置は変えずに、新たなデータフローに対応した処理を挿入するための処理配置に関する実施形態である。
【００９６】
図１６のタイムチャート１６０１は再構成デバイスで行う処理順序が既に決められ、その処理配置も決められているタイムチャートである。タイムチャート１６０１ではデータフローＡの処理１６０３後、データフローＡの設定からデータフローＣの設定へ変更する期間１６０４を経てデータフローＣの処理１６０５を行っている。このタイムチャート１６０１のデータフローＡとデータフローＣ間に新たにデータフローＢを挿入したタイムチャートがタイムチャート１６０２である。データフローＡの処理１６０３の後にデータフローＡの設定からデータフローＢの設定へ変更する期間１６０６を経て新たに挿入したデータフローＢの処理１６０７が行われる。その後データフローＢの設定からデータフローＣの設定へ変更する期間１６０８を経てデータフローＢの処理１６０５が行われる。この際データフローＡとＣの処理配置は変更せずにデータフローＢの処理配置を決定するため、挿入する前後の既に処理配置済みのデータフロー間の設定変更量を考慮する。
【００９７】
図中の１６０９、１６２２、１６３１はそれぞれデータフローＡ、Ｂ、Ｃにおけるプロセッシングエレメントの配置例を示している。本実施形態ではデータフローＡおよびＣは処理配置済みであり、データフローＢの処理配置を行う。なお配置例１６０９、１６２２、１６３１中のプロセッシングエレメント１６１０、１６１１、１６１２、１６１３はそれぞれ同じプロセッシングエレメントを指す。
【００９８】
設定１６１４、１６１５、１６１６、１６１７は、それぞれデータフローＡの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。設定１６２３、１６２４、１６２５、１６２６は、それぞれデータフローＢの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。設定１６３２、１６３３、１６３４、１６３５は、それぞれデータフローＣの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。ここで上記の設定とは実施形態１と同様に、図６で説明した設定のことである。本実施形態では、データフローＡ、Ｂ間、Ｂ、Ｃ間、Ｃ、Ａ間のプロセッシングエレメント１６１０、１６１１、１６１２、１６１３でデータフロー変更に必要な合計の設定変更数と各プロセッシングエレメント間接続の合計距離に注目する。
【００９９】
なお、新たに挿入するデータフローＢに伴う、データフローＡ、Ｂ間でのプロセッシングエレメント１６１０、１６１１、１６１２、１６１３の設定変更は１６３９で表している。またデータフローＢ、Ｃ間でのプロセッシングエレメント１６１０、１６１１、１６１２、１６１３の設定変更は１６４０で表している。
【０１００】
本実施形態と第１の実施形態との違いは、複数の処理配置済みのデータフローを参照して、対象となるデータフローの処理配置を行う点である。
【０１０１】
図１４のステップＳ１４０３で行う処理配置は、データフローＢのみが対象である。データフローＡ、Ｃは処理配置済みであり、処理配置変更は行わない。図１４のステップＳ１４０６では第一の実施形態に対して以下の違いがある。
【０１０２】
処理配置済みのデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの設定値ｕi1,j,kの値が一致していなければα3を設定変更数に加える。また、処理配置対象のデータフローｉ１における、設定値ｕi1,j,kと、処理配置済みのデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの設定値ｕi2,j,kの値が一致していなければβ3を設定変更数に加える。上述の値が一致していなければ何も加えない。
【０１０３】
ここで、あるプロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【０１０４】
データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【０１０５】
【数８】
【０１０６】
またα3、β3は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【０１０７】
また距離については以下の違いがある。図１６で示した例では、距離は、距離１６１８、１６１９、１６２０、１６２１、１６２７、１６２８、１６２９、１６３０、１６３６、１６３７、１６３８の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【０１０８】
【数９】
【０１０９】
ここでκ３l、λ３lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。新たにデータフロー挿入する場合に、挿入前後のデータフローとの設定変更数の削減に関する効果が得られる。
【０１１０】
次に、本発明の第４の実施形態について説明する。第４の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１７に示す。本実施形態では、ある基準となるデータフローの処理後、その結果に応じて次に行われるデータフローが異なる場合の処理配置に関する実施形態である。
【０１１１】
図１７のタイムチャート１７０１は基準となるデータフローＸの処理を期間１７０２で行った後、その結果に応じて、データフローＸからデータフローＡかＢかＣへの設定変更を期間１７０３で行う。設定完了後、データフローＡかＢかＣの処理が期間１７０４で行われ、再度基準となるデータフローＸの処理を行うため期間１７０５でデータフローＡかＢかＣからデータフローＸへと設定変更を行う。上記順序が繰り返されが、データフローＡかＢかＣのどれが行われるかはデータフローＸの結果に応じて変わる。
【０１１２】
図中の１７０６、１７１９、１７２８、１７３７はそれぞれデータフローＸ、Ａ、Ｂ、Ｃにおける配置例を示している。本実施形態では、データフローＸ、Ａ、Ｂ、Ｃの全てのデータフローの処理配置を行う。なお配置例１７０６、１７１９、１７２８、１７３７中のプロセッシングエレメント１７０７、１７０８、１７０９、１７１０はそれぞれ同じプロセッシングエレメントを指す。
【０１１３】
設定１７１１、１７１２、１７１３、１７１４は、それぞれデータフローＸの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７２０、１７２１、１７２２、１７２３は、それぞれデータフローＡの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７２９、１７３０、１７３１、１７３２は、それぞれデータフローＢの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７３８、１７３９、１７４０、１７４１は、それぞれデータフローＣの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。ここで上記の設定とは第１の実施形態と同様に、図６で説明した設定のことである。
【０１１４】
本実施形態では具体的には、データフローＸ、Ａ、Ｂ、Ｃの処理配置を行う。処理配置に際して、データフローＸ、Ａ間、Ｘ、Ｂ間、Ｘ、Ｃ間のプロセッシングエレメント１７０７、１７０８、１７０９、１７１０でデータフロー変更に必要な設定変更数の合計数と各プロセッシングエレメント間接続の合計距離に注目する。
【０１１５】
なお、データフローＸ、Ａ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４５で表している。データフローＸ、Ｂ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４６で表している。
【０１１６】
データフローＸ、Ｃ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４７で表している。
【０１１７】
本実施形態と第１の実施形態との違いは、処理順序に分岐があり、分岐先と分岐元間のデータフローに対して処理配置を行う点にある。
【０１１８】
図１３のステップＳ１３０１では、複数のデータフローを入力すると同時に、部分的に任意の順序関係を含んだ処理順序を入力する。ここで部分的な任意とは本実施形態では実行順序に分岐があり、分岐元と分岐先の実行順序のみ任意であるということを指す。
【０１１９】
図１４のステップＳ１４０３で行う処理配置は、処理配置対象であるデータフローＸ、Ａ、Ｂ、Ｃの全てに対して処理配置を行う。本実施形態では全てのデータフローを処理配置対象として扱う例を示しているが、それに限ったものではない。本実施形態は処理順序に注目したものであり、少なくとも一つのデータフローが、既に処理配置済みの場合には、それ以外のデータフローの処理配置を行うこととなる。
【０１２０】
図１４のステップＳ１４０６では第１の実施形態に対して以下の違いがある。処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα4を設定変更数に加える。また、処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi2,j,kの値が一致していなければβ4を設定変更数に加える。さらに、処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ３における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi3,j,kの値が一致していなければγ4を設定変更数に加える。上述以外で、設定値が一致している場合は何も加えない。
【０１２１】
ここで、あるプロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表し、データフローｉ３のノードｊ３をｊ３rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【０１２２】
データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【０１２３】
【数１０】
【０１２４】
ここでα4、β4、γ4は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【０１２５】
また距離については以下の違いがある。図１７で示した例では、距離は、距離１７１５、１７１６、１７１７、１７１８、１７２４、１７２５、１７２６、１７２７、１７３３、１７３４、１７３５、１７３６、１７４２、１７４３、１７４４の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【０１２６】
【数１１】
【０１２７】
ここで、κ４i,l、λ４i,lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本実施形態により、複数のデータフローを順々に行う上で、その実行順序に分岐がある場合でも、分岐元となるデータフローと分岐先となる複数の他のデータフローを考慮することで、設定変更数削減効果が得られる。
【０１２８】
次に、本発明の第５の実施形態について説明する。第５の実施形態に係るデータフローと処理配置制限方法に関する概要を図１８に示す。処理配置問題は一般的に難しく解算出のための時間が大きくかかる場合が多い。本発明のように複数のデータフローを同時に配置させる場合はさらに問題が大きくなる。そのため本実施形態では処理の配置可能範囲を制限することで効果的に解算出時間を短縮する。
【０１２９】
データフロー１８１９は複数の処理に対応するノード１８０１〜１８１８で構成されている。また１８２６はプロセッシングエレメントアレイに対する入力装置を１８２０、出力装置を１８２１とし、それらの間にプロセッシングエレメントアレイがある構成となっている。
【０１３０】
本実施形態では、これらをデータフロー１８１９の処理を配置モデル１２０１に配置させる際、データフローの深さ方向とプロセッシングエレメントアレイへの入出力の位置を対応させることで解空間を効率的に狭める。具体的にはノード１８０１から１８０４は１８２１で示した範囲のみ配置可能と設定する。また１８０５から１８１０は１８２２で示した範囲のみ配置可能と設定する。また１８１１から１８１４は１８２２で示した範囲のみ配置可能と設定する。また１８１５から１８１８は１８２３で示した範囲のみ配置可能と設定する。
【０１３１】
これらの制限は図１４のステップＳ１４０２で入力することを想定している。本実施形態では配置可能範囲はデータフローの深さとプロセッシングエレメントアレイの入出力の方向に対応付けさせたが、それに限るものではない。
【０１３２】
上述した実施形態では、ユースケース別に各々の処理配置方法について述べたが、本発明はこれらの方法の組み合わせでも良い。また、再構成デバイスの構成要素としてプロセッシングエレメントを説明したが、これに限るものではなく、ＬＵＴや、それとの組み合わせでも良い。また、設定は、実施形態で示した設定に限るものではなく、ＬＵＴベースの再構成デバイスで使用される設定でも良い。また、実施形態では入力するデータフロー全てに対して処理配置対象としたが、データフローの処理配置対象範囲を指定することで、データフローの一部のみに対して処理配置を行っても良い。また、実施形態ではプロセッシングエレメント数はデータフロー間で同じとしているが、処理を配置するプロセッシングエレメント数が異なっても良い。また、実施形態で示した、距離合計値が少なくなるように記載しているが、各距離の最大値が小さくなるように配置を決定しても良い。また、各距離の平均値が少なくなるように配置を決定しても良い。
【０１３３】
上述した実施形態ではプロセッシングエレメントは格子状に均一に配置され、それぞれのプロセッシングエレメント間の接続距離は一定を前提に記載したが、これに限るものではない。プロセッシングエレメントの接続形態が例えば木構造のように接続されている場合はそれぞれの距離は、木構造に応じて重みづけても良い。つまり、プロセッシングエレメントの接続形態に応じてそれぞれの距離を重みづけても良い。
【０１３４】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【技術分野】
【０００１】
本発明は、回路構成を変更することができる再構成デバイス、その処理配置方法等に関する。
【背景技術】
【０００２】
従来から製造後のＬＳＩ回路装置であっても内部の回路構成を変更することで、上記回路が行う処理内容を変更することが可能な再構成デバイスが提案されている。製造後のＬＳＩ回路装置でも処理を変更することが可能であるため、仕様変更などに伴うＬＳＩの作り直しを行わなくて済む。製造コストを抑えることが可能な点や開発期間が短縮可能な点で、現在様々な分野において再構成デバイスが使用されている。
【０００３】
再構成デバイスの構成として、多数のＬＵＴ（Ｌｏｏｋ−Ｕｐ−Ｔａｂｌｅ）を搭載したタイプや多数のプロセッシングエレメントを搭載したタイプが代表的である。また各々のエレメントにはマルチプレクサなどのスイッチングエレメントが接続されている。ここではＬＵＴやプロセッシングエレメント、スイッチングエレメントなどの各構成要素を動作させるための設定を総称し回路構成情報と呼んでいる。回路構成情報の生成方法としては様々あるが、一般に（１）テクノロジーマッピングと呼ばれる論理的な処理の割り当て、（２）各構成要素への物理的な配置、（３）各構成要素の経路決定、の工程に分けられ、順番に行われことが多い。上記三つの工程を経て最終的に回路構成情報が生成される。
【０００４】
（１）論理的な処理の割り当て工程では、処理を構成要素に割り当てることを行う。具体的には、各処理を物理的な構成要素を特定せずに論理的な構成要素に割り当てる。順序変更の指標としては、回路面積、動作速度、消費電力の観点が一般的である。（２）配置工程では、再構成デバイス内のどの構成要素でどの処理を行うかの物理的な割り当てを決定する。データの入出力関係にある処理が配置されているプロセッシングエレメント間の距離によって、データ通信に係るスイッチングエレメント数が異なるため、遅延時間（最大動作周波数）が大きく変化する。そのため、通常は入出力関係のある処理はできる限り近い距離のプロセッシングエレメントに配置させることが遅延時間を短縮する上で重要となる。（３）経路決定の工程では、データ通信の入出力関係にあるプロセッシングエレメント間のデータ通信のため、スイッチングエレメントによる経路を決定する。配置工程と比べ具体的な経路を決定するため、プロセッシングエレメント間の遅延時間を短縮した経路を決定することが重要となってくる。
【０００５】
近年、集積度の向上に伴い、再構成デバイスにおいて実行可能な処理の規模は増えている。しかし、最近ではそれにも増して、処理自体への要求が複雑化・高度化しており、一つの再構成デバイスで全ての処理を一度に行うことは難しい場合がある。これに対して、一つの再構成デバイスにおいて時分割で処理を順々に行う方法がある。より具体的にはまず所望の処理を分割し、分割した処理に対応した回路構成情報を生成する。その後、回路構成情報に基づいた再構成デバイスの回路構成の変更、処理を順々に行っていく。これにより、再構成デバイスで大きな規模の処理を行うことが可能となる。しかしながら、毎回全ての回路構成を変更させていては全体の処理時間が長くなってしまい、速度性能が劣化してしまう。また上記の処理分割数が多い場合も同様に、処理速度の劣化を生じさせてしまう。
【０００６】
この問題を解決するための方法として、マルチコンテキスト型の再構成デバイスがある。コンテキストとは、回路構成情報のことで、マルチコンテキスト型の再構成デバイスとは、複数の回路構成情報を格納するメモリを再構成デバイス内に搭載したものである。回路構成を変更する場合には、上記メモリを切り替えてデバイスを再構成することが可能であり、高速に切り換え可能なことで回路の再構成時間を大幅に短縮することが可能である。しかし、追加で回路構成情報用のメモリを搭載する必要があるため、回路規模が増大する問題がある。
【０００７】
これに対し、特許文献１では、再構成時間を短縮する方法としてスケルトン回路技術に基づいた手法が提案されている。この手法では、先行ベース回路と呼ばれる回路構成情報を、予め再構成デバイスに構成しておく。ここで先行ベース回路とは複数の回路構成情報において全てに共通する共通回路部分と、複数個の回路で互いに共通せず、かつ、再構成デバイス上で回路構成情報を共有しない非排他的独立回路部分からなる回路構成情報のことである。再構成デバイス上において回路の差分のみを部分的に再構成することにより、処理に必要な回路を構成するようにする。この方法は、マルチコンテキスト型に比べ、追加で構成用のメモリを必要としないため回路規模が増大はしない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第３５５８１１９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、一般に再構成デバイスでは様々なアプリケーションを実行する可能性があり、アプリケーションによっては共通部分が少なくなる。また、再構成すべき回路構成情報の数もアプリケーションによって異なる。特許文献１で述べられている先行ベース回路部生成において、共通部分が少ないもしくは、回路構成情報の数が多く再構成デバイスの回路規模を大幅に超えてしまう場合には回路構成を変更するための期間を効率的に削減することが難しい。また、上述した処理配置工程においては、回路構成の変更期間を削減することに加え、データ入出力関係にあるプロセッシングエレメント間の距離が近い必要がある。入出力に係るプロセッシングエレメント間の通信距離が遠い場合、データ通信の遅延時間を増やし、結果として処理全体の期間を増大させてしまう。
【００１０】
本発明は上述した問題点に鑑みてなされたものであり、回路構成変更の順序を考慮することで、プロセッシングエレメント間のデータ通信遅延を抑えつつ回路規模を増やすことなく回路変更期間を効率的に削減することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の処理葉位置方法は、複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法であって、少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、再構成デバイスの構成要素の制約を入力する制約ステップと、前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとを有することを特徴とする。
【発明の効果】
【００１２】
本発明によれば、データ通信の遅延時間を抑えつつ再構成に必要な設定数を減らすように回路構成情報を作成することで、回路規模を増やすことなく再構成デバイスの再構成期間を短縮することが可能である。
【図面の簡単な説明】
【００１３】
【図１】再構成デバイスを含む処理装置の構成例を示す図である。
【図２】再構成デバイスの構成例を示す図である。
【図３】再構成デバイスのエレメント間のデータ通信の手順例を示す図である。
【図４】プロセッシングエレメントの構成例を示す図である。
【図５】コンフィギュレーションコマンドのフォーマット例を示す図である。
【図６】プロセッシングエレメントのコンフィギュレーションメモリに格納される設定の概要例を示す図である。
【図７】設定を読み書きする手順を示すフローチャートである。
【図８】スイッチングエレメントの構成例を示す図である。
【図９】スイッチングエレメントのコンフィギュレーションメモリに格納される設定の概要例を示す図である。
【図１０】データフローにおける処理のプロセッシングエレメントへの配置例を示す図である。
【図１１】複数のデータフローを順次処理するタイムチャートである。
【図１２】処理配置に向けたプロセッシングエレメントアレイのモデル例を示す図である。
【図１３】第１の実施形態における複数のデータフローの処理配置を行うための概要例を示す図である。
【図１４】第１の実施形態における処理配置を行うためのフローチャートである。
【図１５】第２の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１６】第３の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１７】第４の実施形態におけるデータフローの処理配置を行うための概要例を示す図である。
【図１８】第５の実施形態におけるデータフローの処理配置範囲限定を行うための概要例を示す図である。
【図１９】回路構成情報を作成する装置の構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１５】
先ず、本発明の第１の実施形態について説明する。第１の実施形態に係る再構成デバイスを有するシステムの全体構成の例を図１に示す。外部メモリ１０１は、内部に回路構成情報１０６を保持している。回路構成情報１０６は再構成デバイス１０５を構成する要素を動作させる設定群である。コンフィギュレーションコントローラ１０２は上記メモリ１０１から結線１０４を通じ回路構成情報１０６を取得する。取得した回路構成情報１０６は結線１０３を通じて再構成デバイス１０５へ送られる。ここで再構成デバイス１０５の例としてプロセッシングエレメントアレイとしている。また以下では、具体的にプロセッシングエレメントアレイ内の説明をするが、本発明は下記の各プロセッシングエレメントの構成や経路構成に限定されるものではない。
【００１６】
図２に、本実施形態における再構成デバイスであるプロセッシングエレメントアレイの概要図を示す。再構成デバイスには、８入力８出力の入出力処理手段であるスイッチングエレメント２０１が二次元格子状に配置されている。演算処理手段である４入力４出力のプロセッシングエレメント２０２が、スイッチングエレメント２０１の格子内に配置されている。スイッチングエレメント２０１ａ〜ｉの８入力８出力は１入力１出力を一組としてそれぞれ東西南北（右左下上）方向の、他の４つのスイッチングエレメント２０１と結線２０３ａおよび２０３ｂを介して夫々接続されている。
【００１７】
さらに、北東、南東、南西、北西方向の、それぞれ別の４つのプロセッシングエレメント２０２と結線２０４ａおよび２０４ｂを介して双方向に接続された構成を持つ。またスイッチングエレメント２０１ａ〜２０１ｉおよびプロセッシングエレメント２０２ａ〜２０２ｄは結線２０５で一方向に数珠繋ぎに接続されている。
【００１８】
結線２０３ａ、２０３ｂおよび結線２０４ａ、２０４ｂはスイッチングエレメント２０１やプロセッシングエレメント２０２の間で処理対象データを通信するために接続された結線である。結線２０５は、スイッチングエレメント２０１やプロセッシングエレメント２０２に設定を供給するための結線である。
【００１９】
上述の設定によって、スイッチングエレメント２０１においては処理対象データの入出力先が決定され、プロセッシングエレメント２０２においては処理対象データの入出力先や処理内容が決定される。なお、図２の各結線２０３ａ、２０３ｂ、２０４ａ、２０４ｂ、２０５の矢印の方向はデータの方向を示している。またスイッチングエレメント２０１ａ〜２０１ｉはそれぞれ同じ構成を有し、プロセッシングエレメント２０２ａ〜２０２ｄはそれぞれ同じ構成を有する。
【００２０】
ここで、各結線２０３ａ、２０３ｂ、２０４ａ、２０４ｂ、２０５の通信プロトコルの一例として、Ｖａｌｉｄ信号とＲｅａｄｙ信号による２線ハンドシェークを図３に示す。図３では送信側であるモジュールＡ３０１と受信側であるモジュールＢ３０２間はデータ信号線３０３、Ｖａｌｉｄ信号線３０４およびＲｅａｄｙ信号線３０５が接続されている。Ｖａｌｉｄ信号はＶａｌｉｄ信号線３０４を通じ送信側が受信側に対し送信可能状態を示す信号である。Ｒｅａｄｙ信号はＲｅａｄｙ信号線３０５を通じ受信側が送信側に対しデータ受信可能状態を示す信号である。本プロトコルではモジュールＡ３０１からのＶａｌｉｄ信号線３０４とモジュールＢ３０２のＲｅａｄｙ信号線３０５とが両方有効となるクロック立ち上がりのタイミングでデータ信号線３０３のデータがモジュールＡ３０１からモジュールＢ３０２へと送信される。図３の波形中では３０６ａのタイミングでデータＡが、３０６ｂのタイミングでデータＢが、３０６ｃのタイミングでデータＣ、３０６ｄのタイミングでデータＤがモジュールＡ３０１からモジュールＢ３０２へと転送されている。
【００２１】
プロセッシングエレメント２０２の構成を図４に示す。プロセッシングエレメント２０２は、コンフィギュレーションユニット４０１、インプットユニット４０２、コンピュテーショナルユニット４０３、アウトプットユニット４０４、テンポラリーバッファ４０５で構成されている。前記コンフィギュレーションユニット４０１はプロセッシングエレメント２０２の動作内容を決定するための設定の管理を行う。前記インプットユニット４０２はコンフィギュレーションユニット４０１の設定に基づき、入力処理を行う。コンピュテーショナルユニット４０３はコンフィギュレーションユニット４０１の設定に基づき、演算処理を行う。また、コンピュテーショナルユニット４０３は、再度コンピュテーショナルユニット４０３に入力するためテンポラリーバッファ４０５に処理された結果を保持することが可能である。アウトプットユニット４０４はコンフィギュレーションユニット４０１の設定に基づき、出力処理を行う。
【００２２】
上記プロセッシングエレメント２０２の動作をより具体的に説明する。インプットユニット４０２はコンフィギュレーションユニット４０１から入力先を決定するための設定情報を、結線４０６を通じて取得する。取得した設定情報はどの入力ポートを介して外部接続されているモジュールと通信を行うかが指定されている。その情報を元に、結線２０４ａ−ｎｅ、２０４ａ−ｓｅ、２０４ａ−ｓｗ、２０４ａ−ｎｗ、を通じて処理対象であるデータを取得する。ここで参照符号のｎｅ，ｓｅ、ｓｗ，ｎｗはそれぞれ方向を示しており、結線２０４ａ−ｎｅは北東に配置されたスイッチングエレメントと接続されている。また、２０４ａ−ｓｅは南東に配置されたスイッチングエレメントと接続されている。２０４ａ−ｓｗは南西に配置されたスイッチングエレメントと接続されている。２０４ａ−ｎｗは北西に配置されたスイッチングエレメントと接続されている。取得したデータは、結線４０９を通してコンピュテーショナルユニット４０３に送られる。
【００２３】
コンピュテーショナルユニット４０３は、コンフィギュレーションユニット４０１から処理内容を決定するための設定情報を、結線４０７を通じて取得する。取得した設定情報に基づいてインプットユニット４０２から送られてくるデータを取得し、処理を行う。処理したデータは結線４１０を通じてアウトプットユニット４０４に送られる。
【００２４】
コンピュテーショナルユニット４０３は、少なくとも一つの演算器を保持している。上記演算器は、例えば、加減算器、比較器、乗算器、除算器、論理演算器等の演算器、または、これらの組合せからなる演算器、さらにはこれらと他の演算器の組合せからなる演算器などである。以下では具体的な例として、上記コンピュテーショナルユニット４０３では、積和演算と比較演算処理が行え、一度の演算でどちらかを一方を選択的に行うことができるものとし説明する。積和演算では、ａ・ｂ＋ｃ・ｄの処理を行い、比較演算では、もしａ＞ｂならばｃを出力、そうでなければｄを出力するといった処理を行う。また、コンピュテーショナルユニット４０３は一度の入力に対して、上記演算器を繰り返し使用することが可能な構成となっている。繰り返しで使用する場合は一旦上記演算器で使用された処理結果を、結線４１２を通して、テンポラリーバッファに保存し、その後、結線４１１を通して、再度コンピュテーショナルユニット４０３に入力する。再度入力されたデータに対して、新たに上記演算器にて処理を行う。後で詳細を述べるが、上記設定とは上記演算の種類や繰り返し処理、またそれぞれの処理で必要な変数ａ、ｂ、ｃ、ｄはどの値を参照するか、また固定値ならばその値を指定することを意味する。
【００２５】
アウトプットユニット４０４は、処理したデータの出力先を示す設定情報を結線４０８を通じて取得する。取得した設定情報は、どの出力ポートを介してスイッチングエレメントと通信を行うかが指定されている。その情報を元に、結線２０４ｂ−ｎｅ、２０４ｂ−ｓｅ、２０４ｂ−ｓｗ、２０４ｂ−ｎｗ、を通じてスイッチングエレメントへ出力する。ここで結線２０４ｂ−ｎｅは北東に配置されたスイッチングエレメントと接続されている。また、２０４ｂ−ｓｅは南東に配置されたスイッチングエレメントと接続されている。２０４ｂ−ｓｗは南西に配置されたスイッチングエレメントと接続されている。２０４ｂ−ｎｗは北西に配置されたスイッチングエレメントと接続されている。
【００２６】
次にコンフィギュレーションユニット４０１の動作について説明する。コンフィギュレーションユニット４０１はプロセッシングエレメント２０２毎にユニークなＩＤを保持している。コンフィギュレーションユニットは入力側の結線２０５より送られてくる設定情報を取得し、コンフィギュレーションユニット内で処理し、出力側の結線２０５を通して設定を出力する。コンフィギュレーションユニット４０１は自らのＩＤに対応する設定を格納するためコンフィギュレーションメモリ４１３を有している。
【００２７】
図５にコンフィギュレーションユニットに送受信される、設定のためのコンフィギュレーションコマンド５０１を示す。コンフィギュレーションコマンド５０１はリード／ライトモード５０２、ＩＤ５０３、コンフィギュレーションアドレス５０４、設定値５０５で構成されている。リード／ライトモード５０２はコンフィギュレーションコマンドの読み書きの処理を決定する信号である。ＩＤ５０３は処理対象のプロセッシングエレメント２０２を決める信号である。コンフィギュレーションアドレス５０４はコンフィギュレーションユニット４０１中の設定が保持されているメモリ内の番地を指定する信号である。設定値５０５は実際の設定値を表す信号である。図５中のビット幅を示すＭ、Ｎ、Ｏ、Ｐは実際に構成するアーキテクチャによって決められる値である。以下では上述した構成に基づく設定に関してより具体的に説明する。
【００２８】
図６中の６０１はコンフィギュレーションメモリ４１３のアドレスを示しており、図５のコンフィギュレーションアドレス５０４で指定されるアドレスに相当する。６０２は実際の設定値を示しており、図５の設定値５０５に相当する。本実施形態はこれら一つ一つを設定と読んでいるが、本発明は上述の単位に限るものではない。図ではインプットユニット４０２、コンピュテーショナルユニット４０３、アウトプットユニット４０４に関する設定がコンフィギュレーションメモリ４１３に保持されている例を示している。
【００２９】
アドレス０ｘ００００＿００００（“０ｘ”は１６進数を示している）で示した設定値は、インプットユニット４０２における入力先を決定するための設定情報で、この値に応じて所定の入力先が決まる。アドレス０ｘ００００＿０００４で示したイタレーションナンバーは、コンピュテーショナルユニット４０３における、演算の繰り返し回数を決定するための設定情報で、値に応じて演算の繰り返し回数が決まる。本実施形態では４回までの演算を想定している。
【００３０】
アドレス０ｘ００００＿０００８で示したオペレーションセッティングは１度目の演算で行う、演算の種類を決定するための設定で、値に応じて積和演算か比較演算かが決まる。アドレス０ｘ００００＿０００ｃで示したバリアブルセッティングは１度目の演算で、変数ａの値の参照先を決めるための設定である。参照先としては、入力ポートからの入力値、コンフィギュレーションメモリ４１３に保持されている固定値、以前の計算結果が保持されているテンポラリーバッファの値がある。この値に応じて、上記いずれかの値がこの変数ａに入力される。また０ｘ００００＿０００ｃと同様に、０ｘ００００＿００１０、０ｘ００００＿００１４、０ｘ００００＿００１８で示したバリアブルセッティングはそれぞれ、１度目の演算における変数ｂ、ｃ、ｄの値の参照先を決めるための設定である。
【００３１】
次に０ｘ００００＿００１ｃで示したパラメータは、１度目の演算において０ｘ００００＿０００ｃで指定された参照先が固定値の場合の、変数ａのための固定値である。０ｘ００００＿００１ｃと同様に０ｘ００００＿００２０、０ｘ００００＿００２４、０ｘ００００＿００２８で示した固定値は、それぞれ１度目の演算で変数ｂ、ｃ、ｄ、で使用される場合の値である。
【００３２】
続く０ｘ００００＿００２ｃ〜から０ｘ００００＿００９４は、上記０ｘ００００＿０００８〜０ｘ００００＿００２８で示した１度目の演算に係る設定と同様にそれぞれ、２度目、３度目、４度目の設定値を示している。最後に０ｘ００００＿００９８で示したアウトプットセレクトバリューは、アウトプットユニット４０４における出力先を決定するための設定値で、値に応じて所定の出力先が決まる。
【００３３】
次にコンフィギュレーションユニットで行われる処理フローを図７に示す。ステップＳ７０１では、コンフィギュレーションコマンド５０１を入力する。ステップＳ７０２では、入力されたコンフィギュレーションコマンド５０１で指定されたＩＤ５０３が、コンフィギュレーションユニット４０１の持つ自身のＩＤと一致するかどうかを判断する。もし、ステップＳ７０２で自身のＩＤと違うと判断された場合はステップＳ７１１、７１２で、入力されたコンフィギュレーションコマンド５０１に対して、何も処理せずにそのまま出力する。もし、自身のＩＤと一致する場合は、次にステップＳ７０３でリード／ライトモード５０２の値がリードモードかどうかを判断する。リードモードでなければステップＳ７０７でライトモードかどうかを判断する。いずれのモードでもない場合はステップＳ７１１、７１２で何も処理せずにそのまま出力する。もし、リードモードと判断された場合は、ステップＳ７０４において、コンフィギュレーションメモリ４１３からコンフィギュレーションアドレス５０４で指定されたデータを読み出す。その後、ステップＳ７０５にて、入力されたコンフィギュレーションコマンド５０１の設定値５０５に読み出したデータを書き込み、ステップＳ７０６でそのコンフィギュレーションコマンド５０１を出力する。ライトモードと判断された場合は、ステップＳ７０８にて入力されたコンフィギュレーションコマンド５０１の設定値５０５をコンフィギュレーションアドレス５０４で指定されたコンフィギュレーションメモリ４１３に書き込む。次にステップＳ７０９では、入力されたコンフィギュレーションコマンド５０１の値を変更せず、ステップＳ７１０にて、そのまま出力する。一度のコンフィギュレーションコマンドで一つの設定値５０５を変更することが可能であり、順次コンフィギュレーションコマンドを送信し、必要な設定値を全て変更することで所望の処理を実現する。つまり、この設定数が処理内容の切り替え時間を決めていることとなる。
【００３４】
スイッチングエレメント２０１の構成を図８に示す。スイッチングエレメント２０１は、コンフィギュレーションユニット８０１と、クロスバースイッチ８０２で構成される。コンフィギュレーションユニット８０１はデータを転送する接続先を決定するための設定値の管理をする。クロスバースイッチ８０２はコンフィギュレーションユニット８０１の設定に基づき一対一に入出力を接続する。プロセッシングエレメント２０２のコンフィギュレーションユニット４０１と同様、コンフィギュレーションユニット８０１はスイッチングエレメント２０１毎にユニークなＩＤを保持している。コンフィギュレーションユニットは入力側の結線２０５より送られてくる設定情報を取得し、コンフィギュレーションユニット内で処理を行い、出力側の結線２０５を通して設定値を出力する。コンフィギュレーションユニットは上記取得した設定をコンフィギュレーションメモリ８０４に保持している。コンフィギュレーションユニットのコンフィギュレーションコマンドとその処理フローは、図５に示したフォーマット、および図７に示した処理フローと同様である。クロスバースイッチ８０２はコンフィギュレーションユニット８０１からデータの入出力先を決定する設定情報を、結線８０３を通じて取得する。スイッチングエレメント２０１は取得した設定値に基づき結線２０３ａ−ｗ、−ｓ、２０３ｂ−ｅ、−ｎ、結線２０４ｂ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗを通じてデータを取得する。取得したデータは、接続されている結線２０３ａ−ｅ、−ｎ、２０３ｂ−ｗ、−ｓ、結線２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗを通じて渡す。
【００３５】
ここで結線２０３ａ−ｗ、−ｓはそれぞれ西、南に配置されたスイッチングエレメントと接続されていることを意味する。２０３ｂ−ｅ、−ｎはそれぞれ東、北に配置されたスイッチングエレメントと接続されていることを意味している。
【００３６】
結線２０３ａ−ｅ、−ｎはそれぞれ東、北に配置されたスイッチングエレメントと接続されていることを意味する。２０３ｂ−ｗ、−ｓはそれぞれ西、南に配置されたスイッチングエレメントと接続されていることを意味している。
【００３７】
結線２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗはそれぞれ北東、南東、南西、北西に配置されたスイッチングエレメントと接続されていることを意味している。結線２０４ｂ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗはそれぞれ北東、南東、南西、北西に配置されたスイッチングエレメントと接続されていることを意味している。
【００３８】
図９にコンフィギュレーションメモリ８０４に保持されている、スイッチングエレメント２０１におけるクロスバースイッチ８０２の入出力の接続に関する設定例を示す。９０１はメモリのアドレスを示しており、図５のコンフィギュレーションアドレス５０４で指定されるアドレスに相当する。９０２は設定値を示しており、図５の設定値５０５を示している。アドレス０ｘ００００＿００００で示したコネクション設定は結線２０３ａ−ｗからの入力を２０３ａ−ｅ、ｎ、２０３ｂ−ｗ、−ｓ、２０４ａ−ｎｅ、−ｓｅ、−ｓｗ、−ｎｗのいずれに出力するかを決定するための設定値である。続く、０ｘ００００＿０００４は結線２０３ａ−ｓからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿０００８は結線２０３ｂ−ｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿０００ｃは結線２０３ｂ−ｎからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１０は結線２０４ｂ−ｎｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１４は結線２０４ｂ−ｓｅからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１８は結線２０４ｂ−ｓｗからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。０ｘ００００＿００１ｃは結線２０４ｂ−ｎｗからの入力を０ｘ００００＿００００と同様どの結線に出力するかを決定する設定値である。
【００３９】
次にデータフローの構成要素への配置の概要について図１０を用いて説明する。ここで、配置とはデータフローの処理を、所定の配置で規定されるプロセッシングエレメントで実行させるかを決定することを意味している。図１０ではデータフロー１００１のノード１００２、１００３、１００４、１００５はそれぞれ一つのプロセッシングエレメントで行われる処理である。これらノード１００２、１００３、１００４、１００５に対応する処理を、再構成デバイス１０５のプロセッシングエレメント２０２−１、−２、−３、−４へ配置する例を示している。設定１００６、１００７、１００８、１００９はそれぞれ１００２、１００３、１００４、１００５の処理内容に対応したアドレス６０１、設定値６０２で構成されている。なお、各ノードで行う処理内容の割り当ては済んでおり、設定１００６、１００７、１００８、１００９は予め決められているものとしている。配置を決定することで、各設定の書き込み先であるプロセッシングエレメントに対応したＩＤ５０３を決定することが可能となる。
【００４０】
上述した再構成デバイスの構成を複数種類変更して所望の処理を実現するためのタイムチャート例を図１１に示す。図１１では同一の再構成デバイスで複数の異なるデータフローＡ〜Ｚを順に実行しているタイムチャートを示している。本実施形態で扱うデータフローとは、再構成デバイスのプロセッシングエレメントに配置可能な単位で構成されたデータフローのことである。各データフローを処理するための設定は予め生成しておく。再構成デバイスに対して予め生成された設定に基づき再構成デバイスを再構成し、その構成のもとで処理をするという一連の処理が、所定の順序で順々に行われる。
【００４１】
以下ではデータフローＡを配置済みとし、データフローＢを配置対象として説明する。具体的には、配置済みのデータフローＡを実行するための設定値を参照し、データフローＢの処理配置を決定する。データフローＡの処理配置を参照しデータフローＢの処理配置を決定した後、次はデータフローＢを配置済みとし、データフローＣを配置対象とする。具体的にはデータフローＢの処理配置を決定した時と同様に、処理配置済みのデータフローＢを実行するための設定値を参照し、データフローＣの処理配置を決定する。上記の手順を順々に繰り返すことでＡからＺまでのデータフローの配置を行うことが可能となる。
【００４２】
一般に、配置問題は配置のみを決定するだけでも解空間が広い。そのため、詳細配線決定を同時に行うと、良い解を算出できないだけでなく、解自体を算出できない可能性が出てくる。そのため本配置方法では詳細な配線情報は決定せず、図１２に示す配置モデルに基づく概略の距離を用いて配置を決定する。本実施形態では配置モデルとしてプロセッシングエレメントアレイをプロセッシングエレメントの位置に基づいたマンハッタンモデルを用いている。プロセッシングエレメント間のマンハッタン距離を指標として解を算出する。ただし、本発明は、概略の距離としてはマンハッタン距離に限定されるものではない。指標として、詳細配線を同時に行うことも可能である。また、本実施形態では配置モデルとしてマンハッタンモデルに基づく配置モデルを用いたが、それに限るものではない。アーキテクチャに依存したモデルやユークリッド空間に基づいたモデルでも良い。
【００４３】
図１２に示すように、スイッチングエレメント２０１とプロセッシングエレメント２０２で構成される再構成デバイス１０５に対し、配置モデル１２０１を定義する。配置モデル１２０１はプロセッシングエレメント２０２のみで構成しており、指標となる距離としては、横方向のプロセッシングエレメント間の距離１２０２と縦方向の距離１２０３で表す。本実施形態では縦横の距離は等しいものとしているが、異なっても良い。また本発明で扱う距離とは、物理的な長さであっても良いし、各エレメント間の通信に要する時間の長さであっても良く、これらに限るものではない。
【００４４】
次に、図１２の配置モデルを用いて、図１１のタイムチャートで示した処理の切り替わりに注目した処理のプロセッシングエレメントへの配置方法について述べる。
【００４５】
図１３では本実施形態における配置の概要を示している。データフローＡはノード１３０１、１３０２、１３０３、１３０４として表される処理で構成されており、設定１３０５、１３０６、１３０７、１３０８はそれぞれのノードで行う処理の設定である。またフロー１３０９はノード１３０１と１３０２間のデータ入出力関係を表している。フロー１３１０はノード１３０１と１３０３間のデータ入出力関係を表している。フロー１３１１はノード１３０２と１３０４間のデータ入出力関係を表している。フロー１３１２はノード１３０３と１３０４間のデータ入出力関係を表している。
【００４６】
データフローＢはノード１３１３、１３１４、１３１５、１３１６として表される処理で構成されており、設定１３１７、１３１８、１３１９、１３２０はそれぞれのノードで行う処理の設定である。またフロー１３２１はノード１３１３と１３１５間のデータ入出力関係を表している。フロー１３２２はノード１３１４と１３１５間のデータ入出力関係を表している。フロー１３２３はノード１３１５と１３１６間のデータ入出力関係を表している。
【００４７】
ここではプロセッシングエレメントアレイの配置モデル１２０１内の領域１３２４に上述のデータフローＡ、Ｂの処理を配置させることを想定している。本実施形態ではプロセッシングエレメントアレイ内の一部への配置について述べるが、それに限られるものではなく、複数の部分や全体への配置でも良い。１３２５は上記の領域１３２４のデータフローＡ向けの処理配置例を表している。１３２６は上記の領域１３２６のデータフローＢ向けの処理配置例を表している。各々の処理配置１３２５、１３２６内のプロセッシングエレメント１３２７、１３２８、１３２９、１３３０はそれぞれ物理的に同じプロセッシングエレメントを表している。処理配置１３２５では、データフローＡにおいてはノード１３０１の処理をプロセッシングエレメント１３２７に配置させている。ノード１３０２の処理をプロセッシングエレメント１３２９に配置させている。ノード１３０３の処理をプロセッシングエレメント１３２８に配置させている。ノード１３０４の処理をプロセッシングエレメント１３３０に配置させている。またプロセッシングエレメント間のデータ通信の距離を、フロー１３０９は距離１３３１、フロー１３１０は距離１３３２、フロー１３１１は距離１３３３、フロー１３１２は距離１３３４として表している。
【００４８】
続いてデータフローＢに関しては、ノード１３１３の処理をプロセッシングエレメント１３２７に配置させている。ノード１３１４の処理をプロセッシングエレメント１３２８に配置させている。ノード１３１５の処理をプロセッシングエレメント１３２９に配置させている。ノード１３１６の処理をプロセッシングエレメント１３３０に配置させている。またプロセッシングエレメント間のデータ通信の距離を、フロー１３２１は距離１３３５、フロー１３２２は距離１３３６および１３３７、フロー１３２３は距離１３３８として表している。
【００４９】
データフローＡからデータフローＢに処理が切り替わる際に、プロセッシングエレメント１３２７においては、設定変更１３３９で示すように設定１３０５から設定１３１７へと設定が変更される。プロセッシングエレメント１３２８においては、設定変更１３４１で示すように設定１３０７から設定１３１８へと設定が変更される。プロセッシングエレメント１３２９においては、設定変更１３３９で示すように設定１３０６から設定１３１９へと設定が変更される。プロセッシングエレメント１３３０においては、設定変更１３３９で示すように設定１３０８から設定１３２０へと設定が変更される。
【００５０】
本実施形態では、配置を行う上で、処理が切り替わる際の設定変更数とデータフローの依存関係に基づく構成要素間の距離の二つの要素に注目する。
【００５１】
本実施形態で用いる図１３の例ではデータフローＡは既に処理配置済みであり、データフローＡに関する各プロセッシングエレメントの各メモリ内の設定値は固定値として与えられるものとする。データフローＢに関しては処理配置対象である。つまりデータフローの処理順序は決まっており、既に配置済みの配置情報をもとに次に処理されるデータフローの配置を決定することを想定している。
【００５２】
図１９は、データフローからデータフローへ処理を切り替えるための回路構成情報１０６を生成するための装置のブロック構成図を示している。図１９において、２５０１は装置全体の制御を司るＣＰＵである。２５０２はブートプログラムやＢＩＯＳを記憶しているＲＯＭである。２５０３はＣＰＵ２５０１のワークエリアとして利用され、且つ、ＯＳ（オペレーティングシステム）、アプリケーションを格納するためのＲＡＭである。２５０４はＯＳ、回路構成情報１０６を作成するためのアプリケーション、ならびに、様々なデータを格納するためのハードディスクドライブ（ＨＤＤ）である。２５０５はキーボード、２５０６はマウスであり、ユーザインタフェースとして機能する。２５０７は内部にビデオメモリ及び表示コントローラを内蔵する表示制御部であり、２５０８は表示制御部２５０７からの映像信号を受信し、表示するための表示装置である。２５０９は各種外部デバイスと通信するインタフェースであり、例えば、図１に示した外部メモリ１０１を接続することで、本装置が作成した回路構成情報１０６をその外部メモリ１０１に書込むことになる。
【００５３】
上記構成において、本装置に電源が投入されると、ＣＰＵ２５０１はＲＯＭ２５０２に格納されたブートプログラムを実行し、ＨＤＤ２５０４に格納されたＯＳをＲＡＭにロードし、その後、回路構成情報１０６を作成するアプリケーションを起動することで、本装置が回路構成情報作成装置として機能することになる。
【００５４】
以下、本発明を実施するための回路構成情報作成装置として機能する本装置の処理を、図１４のフローチャートを用いて説明する。本手順はシミュレーテッドアニーリングに基づく処理配置方法の例を示すが、本発明は上記手法のみに限定されるものではなく、遺伝的アルゴリズムなどのさまざまな近似解法や線形計画法や非線形計画法など数値最適化法でも良い。また、配置する問題の規模に応じて方法を変えてもよい。
【００５５】
図１３に示す各データフローを表すインデックスをｉ、ノードのインデックスをｊ、図６のアドレス６０１や図９で示したアドレス９０１に相当するエレメント内で保持しているメモリのコンフィギュレーションアドレスをｋとする。また、各ノードｊ間のフローに関するインデックスをｌとする。上記より各メモリ内の設定値はｕi,j,kと表すことができる。またｉ番目のデータフローにおける、フローｌの出発側のノードをＳi,l、到着側のノードをｄi,lとする。
【００５６】
また、図１２に示す通り、各プロセッシングエレメントを表すインデックスをｒとする。各データフローｉの各ノードｊの配置位置はｘi,jおよびｙi,jと表すことができる。本実施形態では同じプロセッシングエレメントに同じデータフロー内の異なる処理を配置することはしないため、ｘi,j、ｙi,jは、ノードｊごとに必ず異なる。つまり、同じプロセッシングエレメントに異なる処理を配置しない。
【００５７】
ここで処理配置済みのデータフローをｉ０、処理配置対象のデータフローをｉ１とする。初めに、ステップＳ１４０１では複数のデータフローとその順序関係(ｉの順序)を入力する。処理配置済みのデータフローに関しては、設定値ｕi0,j,kと共に配置情報ｘi0,j、ｙi0,jも入力する。
【００５８】
次に、ステップＳ１４０２で要求仕様とハードウェアの制約の条件を入力する。ここでハードウェア制約条件とは、ヘテロ構成に伴う各プロセッシングエレメントが個別に持つ構成情報や、処理によって発生する発熱量などの制限などハードウェア構成上の制約となりうるものである。また要求仕様とは、プロセッシングエレメント間の距離制限やステップＳ１４０６で後述する設定変更数と距離の要素の優先度合の割合などハードウェア使用上で制限すべき項目である。ただし、本発明は上述の制約のみに限られるものではない。
【００５９】
続いてステップＳ１４０３では対象となるデータフローの処理配置を行う。初期の処理の配置においては、ランダムに配置する、ないしはデータフローの深さ方向とプロセッシングエレメントアレイの入出力方向とを連動させて処理を配置させる方法があるが、これらの方法に限られるものではない。初期の配置でない場合は、シミュレーテッドアニーリングに基づき処理の配置を変更する。本実施形態では、処理配置である対象のデータフローＢに関して初期処理配置、ないしは処理配置変更を行う。処理配置済みのデータフローＡに関しては、制約に基づき処理配置の変更は行わない。
【００６０】
ステップＳ１４０４では、処理配置結果がステップＳ１４０３で入力した要求仕様を満たしているか判断する。以下の式に示すように、制約を満たしていれば、ペナルティ変数ｐ0を０とし、違反している場合はペナルティ変数ｐ0をペナルティ値Ｃp0とする。
【００６１】
【数１】
【００６２】
ここで本実施形態では、違反があった場合に一律Ｃp0は定数値として扱っているが、違反項目に応じた変数値としてもよい。ステップＳ１４０５では、処理配置結果がステップＳ１３０２で入力したハードウェア制約条件を満たしているかを判断する。
【００６３】
以下の式に示すように、制約を満たしていれば、ペナルティ変数ｐ1を０とし、違反している場合はペナルティ変数ｐ1をペナルティ値Ｃp1とする。
【００６４】
【数２】
【００６５】
ここで本実施形態では、違反があった場合に一律Ｃp1は定数値として扱っているが、違反項目に応じた変数値としてもよい。次にステップＳ１４０６では、対象となるデータフロー変更間における設定変更数と配置に基づく距離の算出を行い、評価値を計算する。まず設定変更数の算出について説明する。図１３の例で説明するとの設定変更１３３９、１３４０、１３４１、１３４２の際に変更の必要がある設定数である。
【００６６】
より具体的には、処理配置済みのデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα1を設定変更数に加える。上述の値が一致していれば何も加えない。
【００６７】
ここで、プロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【００６８】
【数３】
【００６９】
ここでα1は通常１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。図７で示した通り、一度のコンフィギュレーションコマンドで一つの設定値を変更することができることから、この数が少なくなれば、処理の切り替え時間を削減することが可能となる。
【００７０】
続いて距離の算出について述べる。距離とは、配置対象であるデータフローＢにおける距離１３３５、１３３６、１３３７、１３３８の合計量である。ステップＳ１４０３での配置とデータフローのデータ入出力関係に基づいて、以下の式で距離を表すことが可能である。
【００７１】
【数４】
【００７２】
ここでκ1l、λ1lはノード間の距離のｘ、ｙ毎の重みであって、ノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本ステップで評価値算出する際の式は上述の式より、以下と定義する。
【００７３】
【数５】
【００７４】
ここで、δはステップＳ１４０２で与えた設定変更数と距離のどちらを優先させるかの割合を表す指標である。つまり、要求仕様とハードウェア制約条件を満たしつつ、また距離が少なく、再構成に必要な設定変更数が少なくなるほど上記評価値は小さくなる。
【００７５】
最後にステップＳ１４０７では、シミュレーテッドアニーリングに基づき目標達成したかを判断し、目標を達成した場合は終了する。目標未達の場合はステップＳ１４０３に戻り、ステップＳ１４０３〜Ｓ１４０７を繰り返し行う。ここで、目標値とは十分良い結果が得られるまで、もしくは予定された計算時間に達するまで繰り返す。
【００７６】
以上の結果、回路構成情報１０６がＨＤＤ２５０４に生成されるので、後はインタフェース２５０９を介して、利用する外部メモリ１０１にそれを書き出し、実製品に搭載すれば良いことになる。
【００７７】
なお、上記実施形態では、回路構成情報１０６を、外部装置（図１７）にて作成する例を示した。これは以降に説明する全実施形態でも同じである。また、コンフィギュレーションコントローラ１０２が外部装置の代わりに、図１３の処理を実行し、回路構成情報１０６を作成しても構わない。例えば、外部メモリ１０１に複数のデータフロー毎の設定（必要なプロセッサ数と各プロセッサの処理パラメータ）を保持させ、コンフィギュレーションコントローラ１０２が複数のデータフローの設定に基づいて回路構成１０６を作成すればよい。係る点も、以降に説明する全実施形態にも適用できることである。
【００７８】
一般的な再構成デバイスにおけるデータフローのプロセッシングエレメントへの処理配置方法では設定変更数を意識しないため、データフローの処理変更間で全ての設定を変更する必要が生じる。
【００７９】
本実施形態では、データフローの処理順に注目し、距離に加え設定変更の合計数が少なくすることで、設定変更数削減を効果的に行うことが可能となる。
【００８０】
次に、本発明の第２の実施形態について説明する。第２の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１５に示す。本実施形態では再構成デバイスの設定を変更において、各データフローの処理内容自体は決まっているが、その変更順序が不定で、状況や入力データなどに応じて変わる場合の処理配置に関する実施形態である。
【００８１】
タイムチャート１５０１における期間１５０２ではデータフローＡに関する処理が行われ、期間１５０４、１５０８ではデータフローＣに関する処理が行われ、期間１５０６ではデータフローＢに関する処理が行われる。期間１５０３ではデータフローＡからデータフローＣの設定変更が行われる。期間１５０５ではデータフローＣからデータフローＢの設定変更が行われる。期間１５０７ではデータフローＢからデータフローＣの設定変更が行われる。本実施形態では、データフローＡ、Ｂ、Ｃの処理変更の順序が一定でないため、それぞれのデータフロー間の全ての設定変更を考慮して処理の配置を行う必要がある。
【００８２】
図中の１５０９、１５２２、１４３１はそれぞれデータフローＡ、Ｂ、Ｃにおけるプロセッシングエレメントの配置例を示しており、ここではこれら全てのデータフローの処理の配置を一度に一括して行う。なお配置例１５０９、１５２２、１５３１中のプロセッシングエレメント１５１０、１５１１、１５１２、１５１３はそれぞれ物理的に同じプロセッシングエレメントを指す。
【００８３】
設定１５１４、１５１５、１５１６、１５１７は、それぞれデータフローＡの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。設定１５２３、１５２４、１５２５、１５２６は、それぞれデータフローＢの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。設定１５３２、１５３３、１５３４、１５３５は、それぞれデータフローＣの配置におけるプロセッシングエレメント１５１０、１５１１、１５１２、１５１３への設定を表している。ここで上記の設定とは実施形態１と同様に、図６で説明した設定のことである。本実施形態では、データフローＡ、Ｂ間、Ｂ、Ｃ間、Ｃ、Ａ間のプロセッシングエレメント１５１０、１５１１、１５１２、１５１３でデータフロー変更に必要な合計の設定変更数と各プロセッシングエレメント間接続の合計距離に注目する。
【００８４】
上記合計数および距離数が図１４で示したフローチャート１４０６で示す評価値に加える設定変更数を後述する評価値として算出することで、距離を考慮した、再構成デバイスの再構成時の設定変更数の削減を行う。
【００８５】
なお、データフローＡ、Ｂ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５３９で表している。またデータフローＢ、Ｃ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５４０で表している。データフローＣ、Ａ間でのプロセッシングエレメント１５１０、１５１１、１５１２、１５１３の設定変更は１５４１で表している。
【００８６】
本実施形態と第１の実施形態との違いは、同時に複数のデータフローの処理配置を行う点にある。図１４のステップＳ１４０１では、複数のデータフローを入力すると同時に、処理順序が任意であることを入力する。図１４のステップＳ１４０４で行う処理配置では、処理配置対象であるデータフローＡ、Ｂ、Ｃ全てに対して処理配置を行う。図１４のステップＳ１４０６で第１の実施形態に対して以下の違いがある。
【００８７】
処理配置対象のデータフローｉ０における、設定値ｕio,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα2を設定変更数に加える。また、処理配置対象のデータフローｉ１における、設定値ｕi1,j,kと、処理配置対象のデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi2,j,kの値が一致していなければβ2を設定変更数に加える。さらに、処理配置対象のデータフローｉ２における、設定値ｕi2,j,kと、処理配置対象のデータフローｉ０における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi0,j,kの値が一致していなければγ2を設定変更数に加える。上述以外で、設定値が一致していれ場合は何も加えない。
【００８８】
ここで、プロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【００８９】
データフローが切り替わる際に、同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【００９０】
【数６】
【００９１】
ここでα2、β2、γ2は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【００９２】
また距離については以下の違いがある。図１５で示した例では、距離は、距離１５１８、１５１９、１５２０、１５２１、１５２７、１５２８、１５２９、１５３０、１５３６、１５３７、１５３８の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【００９３】
【数７】
【００９４】
ここでκ２i,l、λ２i,lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本実施形態により、全てのデータフロー間を考慮することで、処理の実行順序が不定な場合でも、距離を考慮したうえで平均して設定変更数削減効果が得られる。
【００９５】
次に、本発明の第３の実施形態について説明する。第３の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１６に示す。本実施形態では既に複数のデータフローの処理順序およびそれぞれの処理配置も決まっている場合を想定している。上述の処理順序における任意のデータフローの処理間に、挿入前後の処理配置は変えずに、新たなデータフローに対応した処理を挿入するための処理配置に関する実施形態である。
【００９６】
図１６のタイムチャート１６０１は再構成デバイスで行う処理順序が既に決められ、その処理配置も決められているタイムチャートである。タイムチャート１６０１ではデータフローＡの処理１６０３後、データフローＡの設定からデータフローＣの設定へ変更する期間１６０４を経てデータフローＣの処理１６０５を行っている。このタイムチャート１６０１のデータフローＡとデータフローＣ間に新たにデータフローＢを挿入したタイムチャートがタイムチャート１６０２である。データフローＡの処理１６０３の後にデータフローＡの設定からデータフローＢの設定へ変更する期間１６０６を経て新たに挿入したデータフローＢの処理１６０７が行われる。その後データフローＢの設定からデータフローＣの設定へ変更する期間１６０８を経てデータフローＢの処理１６０５が行われる。この際データフローＡとＣの処理配置は変更せずにデータフローＢの処理配置を決定するため、挿入する前後の既に処理配置済みのデータフロー間の設定変更量を考慮する。
【００９７】
図中の１６０９、１６２２、１６３１はそれぞれデータフローＡ、Ｂ、Ｃにおけるプロセッシングエレメントの配置例を示している。本実施形態ではデータフローＡおよびＣは処理配置済みであり、データフローＢの処理配置を行う。なお配置例１６０９、１６２２、１６３１中のプロセッシングエレメント１６１０、１６１１、１６１２、１６１３はそれぞれ同じプロセッシングエレメントを指す。
【００９８】
設定１６１４、１６１５、１６１６、１６１７は、それぞれデータフローＡの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。設定１６２３、１６２４、１６２５、１６２６は、それぞれデータフローＢの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。設定１６３２、１６３３、１６３４、１６３５は、それぞれデータフローＣの配置におけるプロセッシングエレメント１６１０、１６１１、１６１２、１６１３への設定を表している。ここで上記の設定とは実施形態１と同様に、図６で説明した設定のことである。本実施形態では、データフローＡ、Ｂ間、Ｂ、Ｃ間、Ｃ、Ａ間のプロセッシングエレメント１６１０、１６１１、１６１２、１６１３でデータフロー変更に必要な合計の設定変更数と各プロセッシングエレメント間接続の合計距離に注目する。
【００９９】
なお、新たに挿入するデータフローＢに伴う、データフローＡ、Ｂ間でのプロセッシングエレメント１６１０、１６１１、１６１２、１６１３の設定変更は１６３９で表している。またデータフローＢ、Ｃ間でのプロセッシングエレメント１６１０、１６１１、１６１２、１６１３の設定変更は１６４０で表している。
【０１００】
本実施形態と第１の実施形態との違いは、複数の処理配置済みのデータフローを参照して、対象となるデータフローの処理配置を行う点である。
【０１０１】
図１４のステップＳ１４０３で行う処理配置は、データフローＢのみが対象である。データフローＡ、Ｃは処理配置済みであり、処理配置変更は行わない。図１４のステップＳ１４０６では第一の実施形態に対して以下の違いがある。
【０１０２】
処理配置済みのデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの設定値ｕi1,j,kの値が一致していなければα3を設定変更数に加える。また、処理配置対象のデータフローｉ１における、設定値ｕi1,j,kと、処理配置済みのデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの設定値ｕi2,j,kの値が一致していなければβ3を設定変更数に加える。上述の値が一致していなければ何も加えない。
【０１０３】
ここで、あるプロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【０１０４】
データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【０１０５】
【数８】
【０１０６】
またα3、β3は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【０１０７】
また距離については以下の違いがある。図１６で示した例では、距離は、距離１６１８、１６１９、１６２０、１６２１、１６２７、１６２８、１６２９、１６３０、１６３６、１６３７、１６３８の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【０１０８】
【数９】
【０１０９】
ここでκ３l、λ３lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。新たにデータフロー挿入する場合に、挿入前後のデータフローとの設定変更数の削減に関する効果が得られる。
【０１１０】
次に、本発明の第４の実施形態について説明する。第４の実施形態に係る処理のタイムチャートおよび、処理配置の概要を図１７に示す。本実施形態では、ある基準となるデータフローの処理後、その結果に応じて次に行われるデータフローが異なる場合の処理配置に関する実施形態である。
【０１１１】
図１７のタイムチャート１７０１は基準となるデータフローＸの処理を期間１７０２で行った後、その結果に応じて、データフローＸからデータフローＡかＢかＣへの設定変更を期間１７０３で行う。設定完了後、データフローＡかＢかＣの処理が期間１７０４で行われ、再度基準となるデータフローＸの処理を行うため期間１７０５でデータフローＡかＢかＣからデータフローＸへと設定変更を行う。上記順序が繰り返されが、データフローＡかＢかＣのどれが行われるかはデータフローＸの結果に応じて変わる。
【０１１２】
図中の１７０６、１７１９、１７２８、１７３７はそれぞれデータフローＸ、Ａ、Ｂ、Ｃにおける配置例を示している。本実施形態では、データフローＸ、Ａ、Ｂ、Ｃの全てのデータフローの処理配置を行う。なお配置例１７０６、１７１９、１７２８、１７３７中のプロセッシングエレメント１７０７、１７０８、１７０９、１７１０はそれぞれ同じプロセッシングエレメントを指す。
【０１１３】
設定１７１１、１７１２、１７１３、１７１４は、それぞれデータフローＸの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７２０、１７２１、１７２２、１７２３は、それぞれデータフローＡの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７２９、１７３０、１７３１、１７３２は、それぞれデータフローＢの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。設定１７３８、１７３９、１７４０、１７４１は、それぞれデータフローＣの配置におけるプロセッシングエレメント１７０７、１７０８、１７０９、１７１０への設定を表している。ここで上記の設定とは第１の実施形態と同様に、図６で説明した設定のことである。
【０１１４】
本実施形態では具体的には、データフローＸ、Ａ、Ｂ、Ｃの処理配置を行う。処理配置に際して、データフローＸ、Ａ間、Ｘ、Ｂ間、Ｘ、Ｃ間のプロセッシングエレメント１７０７、１７０８、１７０９、１７１０でデータフロー変更に必要な設定変更数の合計数と各プロセッシングエレメント間接続の合計距離に注目する。
【０１１５】
なお、データフローＸ、Ａ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４５で表している。データフローＸ、Ｂ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４６で表している。
【０１１６】
データフローＸ、Ｃ間でのプロセッシングエレメント１７０７、１７０８、１７０９、１７１０の設定変更は１７４７で表している。
【０１１７】
本実施形態と第１の実施形態との違いは、処理順序に分岐があり、分岐先と分岐元間のデータフローに対して処理配置を行う点にある。
【０１１８】
図１３のステップＳ１３０１では、複数のデータフローを入力すると同時に、部分的に任意の順序関係を含んだ処理順序を入力する。ここで部分的な任意とは本実施形態では実行順序に分岐があり、分岐元と分岐先の実行順序のみ任意であるということを指す。
【０１１９】
図１４のステップＳ１４０３で行う処理配置は、処理配置対象であるデータフローＸ、Ａ、Ｂ、Ｃの全てに対して処理配置を行う。本実施形態では全てのデータフローを処理配置対象として扱う例を示しているが、それに限ったものではない。本実施形態は処理順序に注目したものであり、少なくとも一つのデータフローが、既に処理配置済みの場合には、それ以外のデータフローの処理配置を行うこととなる。
【０１２０】
図１４のステップＳ１４０６では第１の実施形態に対して以下の違いがある。処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ１における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi1,j,kの値が一致していなければα4を設定変更数に加える。また、処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ２における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi2,j,kの値が一致していなければβ4を設定変更数に加える。さらに、処理配置対象のデータフローｉ０における、設定値ｕi0,j,kと、処理配置対象のデータフローｉ３における、同じ位置に配置されたプロセッシングエレメントの同じ種類の設定値ｕi3,j,kの値が一致していなければγ4を設定変更数に加える。上述以外で、設定値が一致している場合は何も加えない。
【０１２１】
ここで、あるプロセッシングエレメントｒに配置されているデータフローｉ０のノードｊ０をｊ０rと表し、データフローｉ１のノードｊ１をｊ１rと表し、データフローｉ２のノードｊ２をｊ２rと表し、データフローｉ３のノードｊ３をｊ３rと表す。ここでｒは前述したとおり、各プロセッシングエレメントを表すインデックスである。
【０１２２】
データフローが切り替わる際の同じ位置に配置されているノードの処理内容の変更に必要な設定変更数は以下の式で求めることができる。
【０１２３】
【数１０】
【０１２４】
ここでα4、β4、γ4は通常それぞれ１であるが、プロセッシングエレメントのコンフィギュレーションメモリの構造に応じて、各設定が格納されているアドレス毎に重み付けを変更することも可能としている。またデータフロー毎に切り替え時間の優先度をつけるためにデータフロー毎に重みづけることも可能としている。
【０１２５】
また距離については以下の違いがある。図１７で示した例では、距離は、距離１７１５、１７１６、１７１７、１７１８、１７２４、１７２５、１７２６、１７２７、１７３３、１７３４、１７３５、１７３６、１７４２、１７４３、１７４４の合計量として表される。図中のプロセッシングエレメントの配置は一例を示してだけであり、配置を変更することでこれらの距離合計量も変わる。配置後にその配置と、データフローのデータ入出力に基づいて以下の式で距離を表すことが可能である。
【０１２６】
【数１１】
【０１２７】
ここで、κ４i,l、λ４i,lは、データフロー毎のノード間の距離などのアーキテクチャによって重みを一律ないしは別々に変更することも可能である。本実施形態により、複数のデータフローを順々に行う上で、その実行順序に分岐がある場合でも、分岐元となるデータフローと分岐先となる複数の他のデータフローを考慮することで、設定変更数削減効果が得られる。
【０１２８】
次に、本発明の第５の実施形態について説明する。第５の実施形態に係るデータフローと処理配置制限方法に関する概要を図１８に示す。処理配置問題は一般的に難しく解算出のための時間が大きくかかる場合が多い。本発明のように複数のデータフローを同時に配置させる場合はさらに問題が大きくなる。そのため本実施形態では処理の配置可能範囲を制限することで効果的に解算出時間を短縮する。
【０１２９】
データフロー１８１９は複数の処理に対応するノード１８０１〜１８１８で構成されている。また１８２６はプロセッシングエレメントアレイに対する入力装置を１８２０、出力装置を１８２１とし、それらの間にプロセッシングエレメントアレイがある構成となっている。
【０１３０】
本実施形態では、これらをデータフロー１８１９の処理を配置モデル１２０１に配置させる際、データフローの深さ方向とプロセッシングエレメントアレイへの入出力の位置を対応させることで解空間を効率的に狭める。具体的にはノード１８０１から１８０４は１８２１で示した範囲のみ配置可能と設定する。また１８０５から１８１０は１８２２で示した範囲のみ配置可能と設定する。また１８１１から１８１４は１８２２で示した範囲のみ配置可能と設定する。また１８１５から１８１８は１８２３で示した範囲のみ配置可能と設定する。
【０１３１】
これらの制限は図１４のステップＳ１４０２で入力することを想定している。本実施形態では配置可能範囲はデータフローの深さとプロセッシングエレメントアレイの入出力の方向に対応付けさせたが、それに限るものではない。
【０１３２】
上述した実施形態では、ユースケース別に各々の処理配置方法について述べたが、本発明はこれらの方法の組み合わせでも良い。また、再構成デバイスの構成要素としてプロセッシングエレメントを説明したが、これに限るものではなく、ＬＵＴや、それとの組み合わせでも良い。また、設定は、実施形態で示した設定に限るものではなく、ＬＵＴベースの再構成デバイスで使用される設定でも良い。また、実施形態では入力するデータフロー全てに対して処理配置対象としたが、データフローの処理配置対象範囲を指定することで、データフローの一部のみに対して処理配置を行っても良い。また、実施形態ではプロセッシングエレメント数はデータフロー間で同じとしているが、処理を配置するプロセッシングエレメント数が異なっても良い。また、実施形態で示した、距離合計値が少なくなるように記載しているが、各距離の最大値が小さくなるように配置を決定しても良い。また、各距離の平均値が少なくなるように配置を決定しても良い。
【０１３３】
上述した実施形態ではプロセッシングエレメントは格子状に均一に配置され、それぞれのプロセッシングエレメント間の接続距離は一定を前提に記載したが、これに限るものではない。プロセッシングエレメントの接続形態が例えば木構造のように接続されている場合はそれぞれの距離は、木構造に応じて重みづけても良い。つまり、プロセッシングエレメントの接続形態に応じてそれぞれの距離を重みづけても良い。
【０１３４】
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【特許請求の範囲】
【請求項１】
複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法であって、
少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、
再構成デバイスの構成要素の制約を入力する制約ステップと、
前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとを有することを特徴とする処理配置方法。
【請求項２】
前記制約は、データフローの構成と再構成デバイスの構成に合わせてデータフロー内の各処理ごとに配置可能範囲を限定する制約を含むことを特徴とする請求項１に記載の処理配置方法。
【請求項３】
前記設定変更数は、データフロー毎あるいは前記構成要素の処理内容を決定する設定に重み付けられることを特徴とする請求項１に記載の処理配置方法。
【請求項４】
前記構成要素間の接続の距離は前記構成要素に重み付けられることを特徴とする請求項１に記載の処理配置方法。
【請求項５】
複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法をコンピュータに実行させるためのプログラムであって、
少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、
再構成デバイスの構成要素の制約を入力する制約ステップと、
前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとをコンピュータに実行させるためのプログラム。
【請求項６】
請求項１に記載の処理配置方法によって生成された設定情報に基づいて動作する再構成デバイス。
【請求項１】
複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法であって、
少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、
再構成デバイスの構成要素の制約を入力する制約ステップと、
前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとを有することを特徴とする処理配置方法。
【請求項２】
前記制約は、データフローの構成と再構成デバイスの構成に合わせてデータフロー内の各処理ごとに配置可能範囲を限定する制約を含むことを特徴とする請求項１に記載の処理配置方法。
【請求項３】
前記設定変更数は、データフロー毎あるいは前記構成要素の処理内容を決定する設定に重み付けられることを特徴とする請求項１に記載の処理配置方法。
【請求項４】
前記構成要素間の接続の距離は前記構成要素に重み付けられることを特徴とする請求項１に記載の処理配置方法。
【請求項５】
複数の構成要素で構成される再構成デバイスに対し、データフローの各処理を行う構成要素を決定するための処理配置方法をコンピュータに実行させるためのプログラムであって、
少なくとも二つの異なるデータフローと前記データフローの処理順序を入力する入力ステップと、
再構成デバイスの構成要素の制約を入力する制約ステップと、
前記データフローに応じた、前記再構成に必要な設定変更数と前記データフローのデータ入出力の依存関係に基づく構成要素間の距離とを用い、構成要素の配置を決めることで、要求される処理をどの構成要素で実行させるかを決定する決定ステップとをコンピュータに実行させるためのプログラム。
【請求項６】
請求項１に記載の処理配置方法によって生成された設定情報に基づいて動作する再構成デバイス。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２０１２−１８５８０３（Ｐ２０１２−１８５８０３Ａ）
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願番号】特願２０１２−３０３５（Ｐ２０１２−３０３５）
【出願日】平成２４年１月１１日（２０１２．１．１１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
【公開日】平成２４年９月２７日（２０１２．９．２７）
【国際特許分類】
【出願日】平成２４年１月１１日（２０１２．１．１１）
【出願人】（０００００１００７）キヤノン株式会社 (59,756)
【Ｆターム（参考）】
[ Back to top ]