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