(57)【要約】【課題】メモリのアクセスに対応したＤＦＧ（データフローグラフ）を短時間で生成する。【解決手段】ＤＦＧ処理部は、データメモリ部へのアクセスに対応していない原ＤＦＧを分割することによって複数のサブＤＦＧを生成するＤＦＧ分割部と、複数のＤＦＧを適切に配置結合することによってデータメモリ部へのアクセスに対応した結合ＤＦＧを生成するＤＦＧ結合部を有する。ＤＦＧ分割部は、夫々のサブＤＦＧの各段におけるデータメモリ部へのアクセス数が、リコンフィギュラブル装置において許容されたデータメモリ部へのアクセスの上限数よりも小さくなるように、原ＤＦＧを分割する。【選択図】図９
2012068801.tif 000002
【特許請求の範囲】
【請求項１】
機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、
原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段を備え、
前記分割手段は、夫々のサブデータフローグラフの各段における前記メモリへのアクセス数が前記リコンフィギュラブル装置における前記メモリへのアクセス可能上限数よりも小さくなるように、前記原データフローグラフの分割を行う
ことを特徴とするデータフローグラフ処理装置。
【請求項２】
前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段を更に備え、
前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置と前記原データフローグラフ上におけるサブデータフローグラフの配置位置とを互いに異ならせる
ことを特徴とする請求項１に記載のデータフローグラフ処理装置。
【請求項３】
前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理と、前記適合可否の判定以外の配置結合条件の充足判定を行う処理とを実行し、前記配置結合条件の充足が確認された後に前記適合可否の判定を行う
ことを特徴とする請求項２に記載のデータフローグラフ処理装置。
【請求項４】
前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を暫定的に定めた状態において当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定し、その判定結果が適合不可である場合、前記結合データフローグラフ上における当該サブデータフローグラフの配置位置を変更する
ことを特徴とする請求項２または請求項３に記載のデータフローグラフ処理装置。
【請求項５】
前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理を実行し、
前記適合可否を判定する処理には、生成中の結合データフローグラフの各段における前記メモリへのアクセス数が前記アクセス可能上限数以下であるかを判定する処理が含まれる
ことを特徴とする請求項２〜請求項４の何れかに記載のデータフローグラフ処理装置。
【請求項６】
前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理を実行し、
前記適合可否を判定する処理には、生成中の結合データフローグラフの入力又は出力データを前記メモリに格納可能であるかを判定する処理が含まれる
ことを特徴とする請求項２〜請求項５の何れかに記載のデータフローグラフ処理装置。
【請求項７】
機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、
原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段と、
前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段と、を備え、
前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置と前記原データフローグラフ上におけるサブデータフローグラフの配置位置とを互いに異ならせる
ことを特徴とするデータフローグラフ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リコンフィギュラブル装置等に利用されるデータフローグラフを処理する技術に関する。
【背景技術】
【０００２】
近年、演算機能の変更が可能なＡＬＵ（Arithmetic and Logic Unit）を多段配置することで構成されたＡＬＵアレイ回路が開発されている。ＡＬＵアレイ回路では、各ＡＬＵで実際に実行される演算内容やＡＬＵ間の接続関係をコマンドデータにより自由に設定することができ、このようなＡＬＵアレイ回路は一般にリコンフィギュラブル回路と呼ばれる。或いは、このようなＡＬＵアレイ回路を含む装置はリコンフィギュラブル装置と呼ばれる。
【０００３】
リコンフィギュラブル装置の利用者は、Ｃ言語等の高級プログラム言語を用いてソースプログラムを作成することができる。コマンドデータは、一般に、そのソースプログラムをコンパイルすることで得たデータフローグラフ（以下、ＤＦＧと表記することがある）を元に生成される。ＤＦＧは、ＡＬＵアレイ回路にて実現されるべき演算処理の内容をグラフ構造にて表現したものであり、ＤＦＧによって、ＡＬＵアレイ回路にて実行されるべき複数の演算の内容、ＡＬＵアレイ回路にて実行されるべき複数の演算間の実行順序及びＡＬＵアレイ回路内におけるデータの流れなどが規定される。ＤＦＧではノードとも呼ばれる演算命令が多段配列されており、ＤＦＧをＡＬＵアレイ回路にマッピングすることによって、ソースソースプログラムに従った演算処理をＡＬＵアレイ回路に行わせることができる。ＤＦＧを生成するデータフローグラフ処理装置は、ＤＦＧが定義される空間上に必要な演算命令を配置してゆくことでＤＦＧを生成することができる。
【０００４】
尚、本出願人は、効率良くＤＦＧを処理する装置として、“機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル回路の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、データフローグラフがリコンフィギュラブル回路の論理回路の数に対応しない場合、論理回路の数に対応した複数のサブデータフローグラフに分割する第１分割手段と、サブデータフローグラフを変形して他のサブデータフローグラフ間に配置結合することにより、前記論理回路の数に対応した結合データフローグラフを生成する結合手段と、を備えることを特徴とするデータフローグラフ処理装置”を提案している（特許文献１参照）。
【０００５】
ところで、リコンフィギュラブル装置において、ＡＬＵに入力されるべきデータ及びＡＬＵから出力されるべきデータを格納するためのデータメモリの個数は有限であるため、ＤＦＧを生成する際、メモリ割り当てを考慮して演算命令を配置する必要がある。即ち、各データに実際にメモリを割り当てることができるのか否かを考慮して、演算命令の配置位置を決定する必要がある。このようなメモリ割り当て可否の判定処理には、比較的多くの時間がかかることが知られている。尚、データメモリの個数を増大させれば、メモリ割り当ての制約が緩和されるが、データメモリの個数増大はコストアップ等を招くため、なるだけ避けられるべきである。
【０００６】
メモリ割り当てを考慮した命令スケジューリング方法（換言すれば、メモリ割り当てを考慮したＤＦＧの生成方法）として、演算命令を配置する度にメモリ割り当ての可否を判定する第１従来方法、メモリ割り当てを行った後に各演算命令を配置する第２従来方法、及び、各演算命令の配置を行った後にメモリ割り当てを行う第３従来方法が存在する（例えば、下記特許文献２参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第４２７５０１３号公報
【特許文献２】特許２０００−２８４９６８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、第１従来方法では、処理時間の長いメモリ割り当て判定処理が配置の度に実行されるため、ＤＦＧ生成に関わる全体処理時間が長くなるという課題がある。第２従来方法では、命令の効率的な実行順序を考慮することなくメモリ割り当てを先に行うため、生成されるＤＦＧの実行段数が必要以上に多くなることがある。第３従来方法では、メモリ割り当ての可否に関わらず各演算命令の配置が成されるため、演算命令の配置後にメモリ割り当てが不可能であることが判明することがある。この場合、演算命令の再配置が必要となり、結果的にＤＦＧ生成に関わる全体処理時間が長くなる。更に、演算命令の再配置時に遅延用命令が増加することによりＤＦＧの実行段数が増大することもある。
【０００９】
そこで本発明は、データフローグラフを効率的に処理しうるデータフローグラフ処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る第１のデータフローグラフ処理装置は、機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段を備え、前記分割手段は、夫々のサブデータフローグラフの各段における前記メモリへのアクセス数が前記リコンフィギュラブル装置における前記メモリへのアクセス可能上限数よりも小さくなるように、前記原データフローグラフの分割を行うことを特徴とする。  
【００１１】
これにより、サブデータフローグラフを元にしてメモリのアクセスに対応したデータフローグラフを効率よく生成することが可能となる。
【００１２】
具体的には例えば、第１のデータフローグラフ処理装置に、前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段を更に設けておくとよい。そして例えば、前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置と前記原データフローグラフ上におけるサブデータフローグラフの配置位置とを互いに異ならせる。
【００１３】
そして例えば、前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理と、前記適合可否の判定以外の配置結合条件の充足判定を行う処理とを実行し、前記配置結合条件の充足が確認された後に前記適合可否の判定を行う。
【００１４】
これにより、処理時間の比較的長いアクセス適合可否判定の実行回数を低減させることができ、結果、データフローグラフの処理に関わる全体的な時間を短縮化することが可能となる。
【００１５】
また例えば、前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を暫定的に定めた状態において当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定し、その判定結果が適合不可である場合、前記結合データフローグラフ上における当該サブデータフローグラフの配置位置を変更する。
【００１６】
また例えば、前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理を実行し、前記適合可否を判定する処理には、生成中の結合データフローグラフの各段における前記メモリへのアクセス数が前記アクセス可能上限数以下であるかを判定する処理が含まれる。
【００１７】
また例えば、前記結合手段は、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を決定する際、当該サブデータフローグラフの前記メモリへのアクセスの適合可否を判定する処理を実行し、前記適合可否を判定する処理には、生成中の結合データフローグラフの入力又は出力データを前記メモリに格納可能であるかを判定する処理が含まれる。
【００１８】
機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段と、前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段と、を備え、前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置と前記原データフローグラフ上におけるサブデータフローグラフの配置位置とを互いに異ならせることを特徴とする。
【００１９】
これにより、メモリのアクセスに対応したデータフローグラフを効率よく生成することが可能となる。
【発明の効果】
【００２０】
本発明によれば、データフローグラフを効率的に処理しうるデータフローグラフ処理装置を提供することが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施形態に係るリコンフィギュラブル装置の概略内部ブロック図である。
【図２】図１に示されるＡＬＵアレイ回路の内部構成図である。
【図３】本発明の実施形態に係り、コマンドデータの生成に関与する部位のブロック図である。
【図４】図３に示されるＤＦＧ処理部の内部ブロック図である。
【図５】図１に示されるデータメモリ部１２の内部構成図である。
【図６】第１処理具体例に係る原ＤＦＧ及びサブＤＦＧを示す図である。
【図７】第１処理具体例に係るサブＤＦＧ及び結合ＤＦＧを示す図である。
【図８】原ＤＦＧの分割時において禁止される方法を示す図である。
【図９】本発明の実施形態に係るＤＦＧ結合処理の手順を表すフローチャートである。
【図１０】仮想ＤＦＧ空間上に複数のサブＤＦＧが配置結合される様子を示した図である。
【図１１】第１処理具体例に係り、データメモリ部に対してデータが割り当てられる様子を示した図である。
【図１２】結合ＤＦＧの生成過程において検討される暫定結合ＤＦＧ（調査用ＤＦＧ）を示した図である。
【図１３】ＡＬＵ間の接続制限を説明するための図である。
【図１４】第１処理具体例に関するメモリ割り当ての変形例を示す図である。
【図１５】第２処理具体例に係る原ＤＦＧ及びサブＤＦＧを示す図である。
【図１６】第２処理具体例に係るサブＤＦＧ及び結合ＤＦＧを示す図である。
【図１７】図１５の原ＤＦＧに対してメモリ割り当てを行おうとした場合に想定されるメモリ割り当て例を示す図である。
【図１８】第２処理具体例に関するメモリ割り当て例を示す図である。
【図１９】サブＤＦＧが変形される様子を示す図である。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態の例を、図面を参照して具体的に説明する。参照される各図において、同一の部分には同一の符号を付し、同一の部分に関する重複する説明を原則として省略する。
【００２３】
図１は、本発明の実施形態に係るリコンフィギュラブル装置１０の概略内部ブロック図である。リコンフィギュラブル装置１０には、ＡＬＵアレイ回路１１、データメモリ部１２及び制御部１３が備えられている。
【００２４】
図２に、ＡＬＵアレイ回路１１の内部構成を示す。ＡＬＵアレイ回路１１は、演算機能の変更が可能な論理回路を複数個備えて構成される。より具体的には、ＡＬＵアレイ回路１１は、複数種類の演算を選択的に実行可能な論理回路を複数段に分けて配列させた構成を有し、更に前段の論理回路列の出力と後段の論理回路列の入力との接続関係を自由に設定可能な接続部を備える。接続部は、前段の論理回路列の出力を保持する機能も備える。各演算回路にて選択的に実行可能な複数種類の演算には、例えば、四則演算や論理演算が含まれる。各論理回路にて実際に実行される演算の内容と、接続部を介した論理回路間の接続関係は、制御部１３より供給されるコマンドデータに基づき設定される。コマンドデータによりＡＬＵアレイ回路１１の内部回路の再構成が可能であるため、ＡＬＵアレイ回路１１をリコンフィギュラブル回路と呼ぶこともできる。
【００２５】
ＡＬＵアレイ回路１１の内部構成の詳細について説明を加える。ＡＬＵアレイ回路１１では、論理回路としてＡＬＵ（Arithmetic and Logic Unit）が設けられている。以下の説明におけるＡＬＵとは、特に記述なき限り、ＡＬＵアレイ回路１１内のＡＬＵを指す。ＡＬＵアレイ回路１１において、ＡＬＵはＸ列Ｙ行の行列状に配置される。Ｘ及びＹは２以上の整数である。Ｘ列Ｙ行の行列において、ｘ列目且つｙ行目に相当する位置を（ｘ，ｙ）にて表す。ｘ及びｙは、１≦ｘ≦Ｘ且つ１≦ｙ≦Ｙを満たす整数である。そして、ＡＬＵアレイ回路１１において、位置（ｘ，ｙ）に配置されたＡＬＵを特にＡＬＵ［ｘ，ｙ］と表記する。尚、ｙ行目をｙ段目とも呼ぶ。
【００２６】
１≦ｙ≦Ｙ−１とした場合、ＡＬＵアレイ回路１１には、ｙ段目のＡＬＵと（ｙ＋１）段目のＡＬＵを接続することでｙ段目のＡＬＵの出力データを（ｙ＋１）段目のＡＬＵに入力する接続部ＣＮ［ｙ］、即ち、接続部ＣＮ［１］〜ＣＮ［Ｙ−１］が備えられている。更に、ｙ段目のＡＬＵの出力データを他の回路に与えるための接続部ＣＮ［Ｙ］と、１段目のＡＬＵへ入力データを与えるための接続部ＣＮ［０］も、ＡＬＵアレイ回路１１に備えられている。ｙ段目のＡＬＵの出力データを接続部ＣＮ［Ｙ］及びＣＮ［０］を介して１段目のＡＬＵに入力することも可能である。
【００２７】
接続部ＣＮ［１］〜ＣＮ［Ｙ］には、夫々、１〜Ｙ段目のＡＬＵの出力データを保持するための保持回路（Ｄ型フリップフロップ等）が設けられている。リコンフィギュラブル装置１０において所定のクロック周期を有する矩形波状のクロック信号が生成されており、該クロック信号は接続部ＣＮ［１］〜ＣＮ［Ｙ］を含む、リコンフィギュラブル装置１０内の任意の部位に供給される。接続部ＣＮ［１］〜ＣＮ［Ｙ］における各保持回路は、クロック信号がローレベルからハイレベルに変化するタイミング又はクロック信号がハイレベルからローレベルに変化するタイミングにおいて、自身が保持しているデータを自身の出力側に接続されているＡＬＵに出力する。従って、ＡＬＵ［ｘ，ｙ］の出力が接続部ＣＮ［ｙ］を介してＡＬＵ［ｘ，ｙ＋１］の入力に接続されている場合、第ｉのクロック期間においてＡＬＵ［ｘ，ｙ］から出力されたデータは、第（ｉ＋１）のクロック期間においてＡＬＵ［ｘ，ｙ＋１］に入力される。ｉは整数である。クロック期間とは１クロック周期分の時間長さを有する単位期間である。第ｉ及び第（ｉ＋１）のクロック期間は連続する期間であると共に、第（ｉ＋１）のクロック期間は第ｉのクロック期間の次のクロック期間である。
【００２８】
データメモリ部１２は、ランダムアクセスメモリ等から成り、ＡＬＵの入力データ及びＡＬＵの出力データを記録する。尚、ＡＬＵの入力データとは、ＡＬＵが他の回路に入力するデータを意味するのでなく、ＡＬＵへ入力されるデータを意味する。ＡＬＵの入力データ及び出力データを、コマンドデータと区別するべく、総称して、演算データと呼ぶこともできる。
【００２９】
制御部１３は、ランダムアクセスメモリ等から成るコマンドメモリ部１４を有し、コマンドメモリ部１４に格納されているコマンドデータをＡＬＵアレイ回路１１に供給することで、ＡＬＵアレイ回路１１内にコマンドデータに応じた所望回路を形成させる。
【００３０】
図３に、コマンドデータの生成に関与する部位のブロック図を示す。コンパイル部２１、ＤＦＧ処理部２２及びコマンドデータ生成部２３を、リコンフィギュラブル装置１０内に（例えば、制御部１３内）に設けておくことができる。記録部２５も、リコンフィギュラブル装置１０内に設けておくことができる。記録部２５に、プログラム２６、データフローグラフ（以下、ＤＦＧと表記する）２７及びコマンドデータ２８を記憶させることができる。プログラム２６は、ＡＬＵアレイ回路１１にて実現されるべき演算処理の内容を、Ｃ言語などの高級プログラム言語を用いて記述したものである。コンパイル部２１は、プログラム２６をコンパイルすることによりプログラム２６をＤＦＧ２７に変換する。１つのプログラムから複数のＤＦＧが生成されることもある。尚、コンパイル部２１、ＤＦＧ処理部２２及びコマンドデータ生成部２３の内の全部又は一部は、リコンフィギュラブル装置１０の外部に設けられていても良いし、ソフトウェアにて構成されていても良い。記録部２５も、リコンフィギュラブル装置１０の外部に設けられていても良い。
【００３１】
ＤＦＧ２７は、ＡＬＵアレイ回路１１にて実現されるべき演算処理の内容をグラフ構造にて表現したものであり、ＤＦＧ２７によって、ＡＬＵアレイ回路１１にて実行されるべき複数の演算の内容、ＡＬＵアレイ回路１１にて実行されるべき複数の演算間の実行順序及びＡＬＵアレイ回路１１内におけるデータの流れなどが規定される。任意のＤＦＧにおいて、１クロック期間中に１つの論理回路（ＡＬＵ）にて実行されるべき単位演算命令はノードと呼ばれ、異なるノード間はエッジにて接続される。エッジは、ノード間におけるデータの入出力関係や各ノードの実行順序を規定する。ＤＦＧを図示する後述の図面（例えば、図６）において、楕円はノードを表しており、矢印はエッジに対応している。一般に、ＤＦＧ上の上方側から下方側に向かって演算が進行するようにＤＦＧは形成される。
【００３２】
図３のＤＦＧ処理部２２は、プログラム２６をコンパイルすることで得られたＤＦＧ２７に対してＤＦＧ処理を実行する。このＤＦＧ処理によってＤＦＧ２７は変形されうる。コマンドデータ生成部２３は、ＤＦＧ処理後のＤＦＧ２７をＡＬＵアレイ回路１１に対するコマンドデータ２８に変換する。制御部１３は、必要なタイミングにおいてコマンドデータ２８をＡＬＵアレイ回路１１に送る。これにより、コマンドデータ２８に応じて、各ＡＬＵにて実際に実行される演算の内容、ＡＬＵ間の接続関係及びＡＬＵの入力データなどが決定され、ＤＦＧ処理後のＤＦＧ２７が指し示す演算処理がＡＬＵアレイ回路１１にて実現される。このように、ＤＦＧ処理部２２は、リコンフィギュラブル装置１０（換言すれば、リコンフィギュラブル回路としてのＡＬＵアレイ回路１１）の動作の設定に必要なＤＦＧを処理するデータフローグラフ処理装置として機能する。
【００３３】
図４に示す如く、ＤＦＧ処理部２２にはＤＦＧ分割部３１（以下、分割部３１と略記することがある）及びＤＦＧ結合部３２（以下、結合部３２と略記することがある）が設けられており、分割部３１及び結合部３２によってＤＦＧ処理が成される。分割部３１にはＤＦＧ処理前のＤＦＧ２７が原ＤＦＧ（原データフローグラフ）として入力される。原ＤＦＧを初期ＤＦＧ（初期データフローグラフ）と読み替えることもできる。分割部３１は、原ＤＦＧの各段におけるデータメモリ部１２へのアクセス数が規定値を超える場合などにおいて、原ＤＦＧを複数のサブＤＦＧ（サブデータフローグラフ）に分割する。複数のサブＤＦＧが生成されると、結合部３２は、その複数のサブＤＦＧを適切に結合することにより結合ＤＦＧ（結合データフローグラフ）を生成する。結合ＤＦＧは、コマンドデータ２８の元となる、ＤＦＧ処理後のＤＦＧ２７に相当する。結合ＤＦＧは最終ＤＦＧとしてＤＦＧ処理部２２から出力される。コマンドデータ生成部２３は、最終ＤＦＧからコマンドデータ２８を生成する。
【００３４】
分割部３１による原ＤＦＧから複数のサブＤＦＧを生成する処理をＤＦＧ分割処理と呼び、結合部３２による複数のサブＤＦＧから結合ＤＦＧを生成する処理をＤＦＧ結合処理と呼ぶ。尚、原ＤＦＧによっては、ＤＦＧ分割処理が不要な場合もあり、その場合には、原ＤＦＧがそのまま最終ＤＦＧとして出力される。
【００３５】
ＤＦＧ分割処理及びＤＦＧ結合処理の詳細を説明する前に、それらの説明を具体化するため、データメモリ部１２の具体的構成例を説明する。ここでは、図５に示す如く、データメモリ部１２が３つの単位メモリＭ１〜Ｍ３から成る場合を考える。即ち、データメモリ部１２におけるメモリ数は３である。各単位メモリは、１クロック期間につき、１入力又は１出力が可能であり、２以上の入力又は２以上の出力は不可能である。即ち、単位メモリＭ１は、１クロック期間につき１つのデータの入力を受けることが可能であるが２つ以上のデータの入力を受けることは不可能であり、また、１クロック期間につき１つのデータを出力することが可能であるが２つ以上のデータを出力することは不可能である。単位メモリＭ２及びＭ３についても同様である。単位メモリがデータの入力を受けるとは、当該データを単位メモリが自身の記録領域に格納する（即ち記録する）ことを意味する。単位メモリがデータを出力するとは、単位メモリが自身の記録領域に格納された当該データを外部に出力することを意味する。
【００３６】
１段目のＡＬＵ列（即ち、ＡＬＵ［１，１］〜ＡＬＵ［Ｘ，１］から成るＡＬＵ列）は、第１のクロック期間において１段目のＡＬＵ列が成すべき演算を実行し、２段目のＡＬＵ列（即ち、ＡＬＵ［１，２］〜ＡＬＵ［Ｘ，２］から成るＡＬＵ列）は、第２のクロック期間において２段目のＡＬＵ列が成すべき演算を実行する。３段目以降のＡＬＵ列も同様である。従って、１段目のＡＬＵ列は全体としてデータメモリ部１２に対し３回までアクセスすることができ、２段目のＡＬＵ列も全体としてデータメモリ部１２に対し３回までアクセスすることができる。３段目以降のＡＬＵ列も同様である。アクセスとは、データメモリ部１２内の単位メモリからデータを読み出すこと（換言すれば、データメモリ部１２内の単位メモリからデータの入力を受けること）、又は、データメモリ部１２内の単位メモリにデータを書き込むこと（換言すれば、データメモリ部１２内の単位メモリにデータを出力すること）を意味する。
【００３７】
１クロック期間あたりのアクセスの上限数をアクセス可能上限数と呼ぶ。図５の例において、データメモリ部１２へデータを入力する動作におけるアクセス可能上限数及びデータメモリ部１２からデータを出力する動作におけるアクセス可能上限数は共に３である。
【００３８】
図６及び図７を参照し、原ＤＦＧ２００がＤＦＧ処理部２２に与えられたことを想定して、ＤＦＧ処理部２２の動作を説明する。図６及び図７の例では、原ＤＦＧ２００からサブＤＦＧ２０１〜２０５が生成された後、サブＤＦＧ２０１〜２０５から結合ＤＦＧ２１０が生成されている。ＤＦＧを示す図面において、楕円は上述したようにノードを表しており、四角形はデータメモリ部１２の入力データ又は出力データを表している。但し、サブＤＦＧを示す図面中の四角形の一部（例えば、図６のデータＤｋに対応する四角形）は、データメモリ部１２の入力及び出力データ以外の中間生成データを表している。原ＤＦＧ２００を含む任意のＤＦＧ又は後述の仮想ＤＦＧ空間において、ノードは行列状に配置される。ＡＬＵアレイ回路１１と同様、ＤＦＧの行列又は仮想ＤＦＧ空間においても、ｘ列目且つｙ行目に相当する位置を（ｘ，ｙ）にて表す。また、ＡＬＵアレイ回路１１と同様、ＤＦＧの行列又は仮想ＤＦＧ空間においても、ｙ行目をｙ段目とも呼ぶ。また、ＤＦＧの行列又は仮想ＤＦＧ空間において、１列目側が左側であってＸ列目側が右側であるとする（ＡＬＵアレイ回路１１においても同様）。
【００３９】
原ＤＦＧ２００は、４行３列のＤＦＧであって、９つのノードＮ１〜Ｎ９を含む。原ＤＦＧ２００において、１段目の位置である位置（１，１）、（２，１）及び（３，１）に夫々ノードＮ１、Ｎ２及びＮ３が配置されており、２段目の位置である位置（１，２）、（２，２）及び（３，２）に夫々ノードＮ４、Ｎ５及びＮ６が配置されており、３段目の位置である位置（１，３）及び（２，３）に夫々ノードＮ７及びＮ８が配置されており、４段目の位置である位置（２，４）にノードＮ９が配置されている。位置（ｘ，ｙ）に配置されたノードは、ＡＬＵ［ｘ，ｙ］が成すべき演算の内容を表している。
【００４０】
任意のＤＦＧにおいて、ｙ段目に配置されたノードの演算は、第ｙのクロック期間に実行されることが要求される。従って、原ＤＦＧ２００は、１段目に配置されたノードＮ１〜Ｎ３の演算が第１のクロック期間に実行されるべきこと、２段目に配置されたノードＮ４〜Ｎ６の演算が第２のクロック期間に実行されるべきこと、３段目に配置されたノードＮ７及びＮ８の演算が第３のクロック期間に実行されるべきこと、４段目に配置されたノードＮ９の演算が第４のクロック期間に実行されるべきことを規定している。
【００４１】
また、原ＤＦＧ２００は、何れかのノードに対して互いに異なるデータＤａ、Ｄｂ、Ｄｃ、Ｄｄ、Ｄｅ及びＤｆがデータメモリ部１２より入力されるべきことを規定している。具体的には、データメモリ部１２から、ノードＮ１に対してデータＤａ及びＤｂが入力され、且つ、ノードＮ２に対してデータＤｃ及びＤｄが入力され、且つ、ノードＮ３に対してデータＤｄ及びＤｆが入力され、且つ、ノードＮ４に対してデータＤｅが入力され、且つ、ノードＮ５に対してデータＤｃが入力され、且つ、ノードＮ６に対してデータＤｆが入力され、且つ、ノードＮ７に対してデータＤｅが入力されるべきことが、原ＤＦＧ２００に規定されている。
【００４２】
更に、原ＤＦＧ２００において、ノードＮ１、Ｎ２及びＮ３の出力データは夫々ノードＮ４、Ｎ５及びＮ６に入力され、ノードＮ４の出力データはノードＮ７及びＮ８に共通に入力され、ノードＮ５の出力データはノードＮ８に入力され、ノードＮ６及びＮ８の出力データはノードＮ９に入力されている。
【００４３】
分割部３１は、原ＤＦＧの分割によって複数のサブＤＦＧを生成する際、夫々のサブＤＦＧの各段におけるデータメモリ部１２へのアクセス数が、１クロック期間中にＡＬＵアレイ回路１１の各段がデータメモリ部１２にアクセスできる数、即ちアクセス可能上限数よりも小さくなるように原ＤＦＧを分割する。具体的には、１クロック期間につきＡＬＵアレイ回路１１の各段がデータメモリ部１２との間で最大３つのデータの入力又は出力を行うことができることを考慮しつつ、分割部３１は、原ＤＦＧの各段におけるデータメモリ部１２へのアクセス数（データメモリ部１２に入力又はデータメモリ部１２から出力されるデータの数）を調べ、調べたアクセス数が３以上になる段が原ＤＦＧに含まれている場合には、サブＤＦＧにおいて各段のアクセス数が２以下となるように原ＤＦＧを分割する。
【００４４】
“夫々のサブＤＦＧの各段におけるデータメモリ部１２へのアクセス数がアクセス可能上限数よりも小さい”という条件を、便宜上、分割条件ＣＡと呼ぶ。図６の原ＤＦＧ２００では、１段目のノードＮ１〜Ｎ３に対して計６個のデータがデータメモリ部１２から入力されており、且つ、２段目のノードＮ４〜Ｎ６に対して計３個のデータがデータメモリ部１２から入力されている。従って、ＤＦＧ分割処理により、データメモリ部１２から各段への入力データ数が２以下となるように原ＤＦＧ２００が分割される。例えば、図６に示す如く、ＤＦＧ分割処理によって、原ＤＦＧ２００から５つのサブＤＦＧ２０１〜２０５が生成される。サブＤＦＧ２０１〜２０５の夫々は原ＤＦＧ２００の一部に相当し、サブＤＦＧ２０１〜２０５は互いに重複するノードを含まない。
【００４５】
サブＤＦＧ２０１は、ノードＮ１及びＮ４を含む、２行１列のＤＦＧである。サブＤＦＧ２０１において、位置（１，１）及び（１，２）に夫々ノードＮ１及びＮ４が配置されており、且つ、データメモリ部１２からのデータＤａ及びＤｂがノードＮ１に入力されていると共にデータメモリ部１２からのデータＤｅがノードＮ４に入力されており、且つ、ノードＮ１の出力データはノードＮ４に入力されており、且つ、ノードＮ４から中間生成データＤｋが出力されている。
サブＤＦＧ２０２は、ノードＮ２及びＮ５を含む、２行１列のＤＦＧである。サブＤＦＧ２０２において、位置（１，１）及び（１，２）に夫々ノードＮ２及びＮ５が配置されており、且つ、データメモリ部１２からのデータＤｃ及びＤｄがノードＮ２に入力されていると共にデータメモリ部１２からのデータＤｃがノードＮ５に入力されており、且つ、ノードＮ２の出力データはノードＮ５に入力されており、且つ、ノードＮ５から中間生成データＤｍが出力されている。
サブＤＦＧ２０３は、ノードＮ３及びＮ６を含む、２行１列のＤＦＧである。サブＤＦＧ２０３において、位置（１，１）及び（１，２）に夫々ノードＮ３及びＮ６が配置されており、且つ、データメモリ部１２からのデータＤｄ及びＤｆがノードＮ３に入力されていると共にデータメモリ部１２からのデータＤｆがノードＮ６に入力されており、且つ、ノードＮ３の出力データはノードＮ６に入力されており、且つ、ノードＮ６から中間生成データＤｎが出力されている。
サブＤＦＧ２０４は、ノードＮ７を含む、１行１列のＤＦＧである。サブＤＦＧ２０４において、位置（１，１）にノードＮ７が配置されており、且つ、ノードＮ７にはデータメモリ部１２からのデータＤｅが入力されていると共にサブＤＦＧ２０１からの中間生成データＤｋが入力されている。
サブＤＦＧ２０５は、ノードＮ８及びＮ９を含む、２行１列のＤＦＧである。サブＤＦＧ２０５において、位置（１，１）及び（１，２）に夫々ノードＮ８及びＮ９が配置されており、且つ、ノードＮ８にはサブＤＦＧ２０１からの中間生成データＤｋが入力されていると共にサブＤＦＧ２０２からの中間生成データＤｍが入力されており、且つ、ノードＮ９にはサブＤＦＧ２０３からの中間生成データＤｎが入力されており、且つ、ノードＮ８の出力データはノードＮ９に入力されている。
【００４６】
サブＤＦＧ２０１の１段目に属するノードがデータメモリ部１２にアクセスするデータ（即ち、データＤａ及びＤｂ）の総数は２である。即ち、サブＤＦＧ２０１の１段目におけるデータメモリ部１２へのアクセス数（換言すれば、サブＤＦＧ２０１の１段目のノードに対するデータメモリ部１２からの入力データ数）は２である。サブＤＦＧ２０１の２段目に属するノードがデータメモリ部１２にアクセスするデータ（即ち、データＤｅ）の総数は１である。即ち、サブＤＦＧ２０１の２段目におけるデータメモリ部１２へのアクセス数（換言すれば、サブＤＦＧ２０１の２段目のノードに対するデータメモリ部１２からの入力データ数）は１である。故に、サブＤＦＧ２０１の各段におけるデータメモリ部１２へのアクセス数はアクセス可能上限数（本例において３）よりも小さい。サブＤＦＧ２０２〜２０５についても同様である。従って、サブＤＦＧ２０１〜２０５を得るＤＦＧ分割処理は、上記の分割条件ＣＡを満たしている。
【００４７】
尚、ここでは、サブＤＦＧの各段におけるデータメモリ部１２へのアクセス数を２までに制限しているが、この制限数はアクセス可能上限数よりも小さければよく、１でも良い。
【００４８】
また、分割部３１は、分割条件ＣＡだけでなく他の分割条件をも満たすようにＤＦＧ分割処理を行っても良い。例えば、任意の２つのサブＤＦＧ間においてデータの入力とデータの出力が双方向に発生することがないようにＤＦＧ分割処理を行うことができる。即ち例えば、図８に示すような分割が発生しないようにＤＦＧ分割処理を行うことができる。
図８の例では、第１のサブＤＦＧに属するノードの出力データが第２のサブＤＦＧに属するノードに入力される同時に第２のサブＤＦＧに属するノードの出力データが第１のサブＤＦＧに属するノードに入力されているが、このようなサブＤＦＧが生成されないように上記他の分割条件を定めても良い。
【００４９】
結合部３２は、特許文献１と同様、ＡＬＵアレイ回路１１の列数Ｘと同じ列数を有すると共に無限の段数を有する仮想ＤＦＧ空間（特許文献１における仮想的なノード空間）を想定し、仮想ＤＦＧ空間上に、原ＤＦＧに基づく複数のサブＤＦＧを順次配置して結合することにより結合ＤＦＧを生成する。但し、この際、データメモリ部１２におけるアクセス数制限及びメモリ割り当てを考慮される。図９に、結合部３２によるＤＦＧ結合処理のフローチャートを示す。特に記述なき限り、図９に示される各ステップの処理は結合部３２にて実行される。
【００５０】
後に図６及び図７の例を当てはめたときの図９の具体的動作を説明するが、まず、図６及び図７の例に限らない、図９の各ステップの処理内容を説明する。
【００５１】
ＤＦＧ結合処理が開始されると、まずステップＳ１１〜Ｓ１６の処理が、この順番で順次実行されてゆく。最初にステップＳ１１において、サブＤＦＧ間の接続関係を調査し、その調査結果を利用して各サブＤＦＧの結合順番を決定する。即ち、サブＤＦＧごとにサブＤＦＧが何番目に仮想ＤＦＧ空間上で配置結合されるのかを決定する。この決定方法として、特許文献１に記載の方法を利用することができる。例えば、サブＤＦＧ間の入出力依存関係を調べ、上流のサブＤＦＧから結合されるように各サブＤＦＧの結合順番を決定する。尚、ステップＳ１１の段階では、仮想ＤＦＧ空間にノードは一切配置されていない。
【００５２】
ステップＳ１２では変数ｉに１が代入される。ステップＳ１３において、結合部３２は、ｉ番目の結合順番を有するサブＤＦＧを結合対象ＤＦＧに設定し、結合対象ＤＦＧの左上隅のノード、即ち、結合対象ＤＦＧ上の位置（１，１）に配置されているノードをＮＯＤＥ０に設定する。次に、ステップＳ１４において変数ｙに１が代入され、続くステップＳ１５において変数ｘに１が代入される。その後、ステップＳ１６において、結合部３２は、仮想ＤＦＧ空間上における位置（ｘ，ｙ）にＮＯＤＥ０以外のノードが既に配置されているか否かを判断し、位置（ｘ，ｙ）にＮＯＤＥ０以外のノードが既に配置されていればステップＳ１６からステップＳ２０に移行する一方で、そうでなければ（Ｓ１６のＮ）ステップＳ１６からステップＳ１７に移行する。
【００５３】
ステップＳ１７において、結合部３２は、仮想ＤＦＧ空間上における位置（ｘ，ｙ）にＮＯＤＥ０を配置すると仮定したときに、結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間上に配置可能であるか否かを調査する。この調査には、アクセス数制限条件の判定と、アクセス数制限条件以外の条件である接続条件の判定と、が含まれる。これらの条件の意義については後述される。アクセス数制限条件及び接続条件の双方が満たされているときにのみ、結合対象ＤＦＧの全ノードが仮想ＤＦＧ空間上に配置可能であると判断されて、処理はステップＳ１７に続くステップＳ１８を介してステップＳ２３に移行し、アクセス数制限条件及び接続条件の内、少なくとも一方が満たされていない場合は、ステップＳ１８を介してステップＳ１９に移行する。尚、アクセス数制限条件の判定と接続条件の判定の内、接続条件の判定を先に実行するようにし、接続条件の充足が確認された後にアクセス数制限条件の判定を行うようにしても良い。この場合において、接続条件の未充足が確認されたならば、アクセス数制限条件の充足／不充足の判定を行うことなく、ステップＳ１７からステップＳ１９に進むと良い。
【００５４】
ステップＳ１９では、ステップＳ１７の調査結果を利用して結合対象ＤＦＧの配置段の変更が必要であるか否かを判断し、その変更が必要な場合には処理をステップＳ１９からステップＳ２２へと進める一方で、その変更が不要な場合にはステップＳ１９からステップＳ２０に移行する。アクセス数制限条件が満たされていないとき、配置段の変更が必要と判断される。ステップＳ２０では、変数ｘの値が所定値ｘｍａｘと一致しているか否かを判断し、それらが一致している場合、処理をステップＳ２０からステップＳ２２へと移行させる一方、それらが不一致である場合、処理をステップＳ２０からステップＳ２１へと移行させる。ｘｍａｘは、ＡＬＵアレイ回路１２の列数、即ち、Ｘである。ここでは、ｘｍａｘが３以上であるものとする。ステップＳ２１では変数ｘに１が加算され、その後、ステップＳ１６に戻ってステップＳ１６及びそれ以降の処理が再度実行される。ステップＳ２２では変数ｙに１が加算され、その後、ステップＳ１５に戻ってステップＳ１５及びそれ以降の処理が再度実行される。
【００５５】
仮想ＤＦＧ空間におけるサブＤＦＧの配置位置を全て確定させ、仮想ＤＦＧ空間上に全てのサブＤＦＧを実際に配置して結合することにより最終ＤＦＧとしての結合ＤＦＧが形成される。全てのサブＤＦＧの配置位置が未だ確定していない状態における、仮想ＤＦＧ空間上の結合ＤＦＧを、生成中の結合ＤＦＧ、又は、暫定結合ＤＦＧと呼ぶ。例えば、図１０に示す如く、サブＤＦＧ２０１〜２０５の内、サブＤＦＧ２０１〜２０４のみを配置して結合させた状態における結合ＤＦＧは、結合ＤＦＧ２１０の生成過程において形成される暫定結合ＤＦＧの一種である。尚、仮想ＤＦＧ空間上の位置（ｘ，ｙ）と結合ＤＦＧ又は暫定結合ＤＦＧ上の位置（ｘ，ｙ）は一致している。
【００５６】
ステップＳ２３において、結合部３２は、結合対象ＤＦＧに対してメモリ割り当ての可否を判定する。具体的には、仮想ＤＦＧ空間上における位置（ｘ，ｙ）にＮＯＤＥ０を配置した状態で結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間に暫定的に配置することにより暫定結合ＤＦＧを形成し、その上で、暫定結合ＤＦＧがデータメモリ部１２にアクセスするデータの全てをデータメモリ部１２に割り当て可能であるかを判定する。換言すれば、データメモリ部１２から暫定結合ＤＦＧに入力されるべきデータ又は暫定結合ＤＦＧがデータメモリ部１２に出力すべきデータを、データメモリ部１２に全て格納可能かを判定する。当然ではあるが、ステップＳ２３の判定は、各単位メモリが１クロック期間につき１入力又は１出力が可能であるが２以上の入力又は２以上の出力は不可能であるという条件の下で成される。
【００５７】
結合対象ＤＦＧについてメモリ割り当てが可能であると判断された場合（ステップＳ２４のＹ）には、ステップＳ２３に続くステップＳ２４を介して処理はステップＳ２５へと進むが、そのメモリ割り当てが不可能であると判断された場合には（ステップＳ２４のＮ）にはステップＳ２４を介して処理はステップＳ２２へと移行する。ステップＳ２５において、結合部３２は、結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間上に実際に配置する。この際、仮想ＤＦＧ空間上に他のサブＤＦＧが既に配置されているならば、ステップＳ１１にて調査したサブＤＦＧ間の接続関係に基づき、既に配置されている他のサブＤＦＧに結合対象ＤＦＧを接続する。即ち例えば、既に配置されている他のサブＤＦＧの出力データが結合対象ＤＦＧに入力されるべきであるならば、その入力が実現されるようにそれらを結合する。
【００５８】
ステップＳ２５の処理後、ステップＳ２６にて変数ｉが所定値ｉｍａｘと一致しているか否かを判断し、それらが不一致である場合（ステップＳ２６のＮ）、変数ｉに１を加算してから（ステップＳ２７）ステップＳ１３に戻り、ステップＳ１３及びそれ以降の処理が再度実行される。一方、ｉ＝ｉｍａｘである場合には図９に示すＤＦＧ結合処理を終了する。サブＤＦＧの総数がｉｍａｘに代入されている。従って、図６及び図７の例では、ｉｍａｘ＝５である。
【００５９】
［第１処理具体例］
図６及び図７に対応するＤＦＧ処理の具体例を第１処理具体例と呼ぶ。第１処理具体例の動作の流れを、図９に沿って説明する。図１１（ｃ）は、図７の結合ＤＦＧ２１０に対応する、データメモリ部１２のメモリ割り当ての様子を示している。図１１（ｃ）のメモリ割り当て例では、単位メモリＭ１、Ｍ２及びＭ３の第１アドレスに夫々データＤａ、Ｄｂ及びＤｅが割り当てられ、単位メモリＭ１、Ｍ２及びＭ３の第２アドレスに夫々データＤｃ、Ｄｄ及びＤｆが割り当てられている。
【００６０】
図９のＤＦＧ結合処理によって、原ＤＦＧ２００に基づくサブＤＦＧ２０１〜２０５から結合ＤＦＧ２１０が生成される。ステップＳ１１において、サブＤＦＧ２０１、２０２、２０３、２０４及び２０５の結合順番が、夫々、１、２、３、４及び５番目に決定されたものとする。
【００６１】
そうすると、１回目のステップＳ１３では、ｉ＝１であるため、１番目の結合順番を有するサブＤＦＧ２０１が結合対象ＤＦＧに設定され、更に、結合対象ＤＦＧであるサブＤＦＧ２０１の左上隅ノード、即ちノードＮ１がＮＯＤＥ０に設定される。次に、変数ｙ及びｘに１が代入された後（ステップＳ１４及びＳ１５）、仮想ＤＦＧ空間における位置（ｘ，ｙ）、即ち位置（１，１）にＮＯＤＥ０以外の他のノードが既に配置されているか否かが判断される。このとき、位置（１，１）にＮＯＤＥ０以外の他のノードは配置されていないため（ステップ１６のＮ）、ステップＳ１７に進む。ステップＳ１７では、仮想ＤＦＧ空間の位置（１，１）にＮＯＤＥ０（即ち、サブＤＦＧ２０１のノードＮ１）を配置した上で結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間に配置可能か否かを調査する。
【００６２】
この調査の際、仮想ＤＦＧ空間上の位置（１，１）にＮＯＤＥ０（即ち、サブＤＦＧ２０１のノードＮ１）を配置した上でサブＤＦＧ２０１の全ノードを仮想ＤＦＧ空間に配置させ、これによって得られる仮想ＤＦＧ空間上のＤＦＧを調査用ＤＦＧ２２１Ａ（図１２（ａ）参照）として想定する。調査用ＤＦＧ２２１Ａでは、位置（１，１）及び（１，２）に夫々ノードＮ１及びＮ４が配置されることになる。調査用ＤＦＧは、上述の暫定結合ＤＦＧの一種である。
【００６３】
ステップＳ１７にて想定された調査用ＤＦＧについて、アクセス数制限条件及び接続条件の双方が満たされているときのみ、結合対象ＤＦＧの全ノードが仮想ＤＦＧ空間上に配置可能であると判断される。調査用ＤＦＧの各段におけるデータメモリ部１２へのアクセス数が上記のアクセス可能上限数（即ち３）以下であるとき、アクセス数制限条件は満たされると判断され、そうでないとき、アクセス数制限条件は満たされていないと判断される。調査用ＤＦＧにおいて、データメモリ部１２へのアクセス数がアクセス可能上限数を超える段が１つでも存在すれば、アクセス数制限条件は不充足である。
【００６４】
調査用ＤＦＧ２２１Ａにおいて、１段目のデータメモリ部１２へのアクセス数は２であり、２段目のデータメモリ部１２へのアクセス数は１である。故に、調査用ＤＦＧ２２１Ａはアクセス数制限条件を充足している。
【００６５】
更に、調査用ＤＦＧ２２１Ａが接続条件を満たしている否かも判定される。接続条件に、例えば、特許文献１の図５に示されているような、ＡＬＵ間の三方向の接続制限条件を含めることができる。即ち例えば、図１３に示す如く、ＡＬＵ［ｘ，ｙ］の出力は、接続部ＣＮ［ｙ］を介してＡＬＵ［ｘ−１，ｙ＋１］、ＡＬＵ［ｘ，ｙ＋１］及びＡＬＵ［ｘ＋１，ｙ＋１］のみにしか接続できないという接続制限を課し、この接続制限が満たされる場合に限って接続条件が満たされると判断するようにする。この他の接続制限を、ステップＳ１７における接続条件の判定に利用しても良い。第１処理具体例では、説明の簡略化上、全ての調査用ＤＦＧに対して接続条件が満たされているものとする（後述の他の処理具体例についても同様）。従って、ｘ＝１且つｙ＝１の状態でサブＤＦＧ２０１の全ノードが配置可能であると判断されて（ステップＳ１８のＹ）、ステップＳ２３に進む。
【００６６】
ステップＳ２３では、アクセス数制限条件及び接続条件の双方を満たすと判断された調査用ＤＦＧが暫定結合ＤＦＧとして捉えられた上で、即ち、調査用ＤＦＧ２２１Ａが暫定結合ＤＦＧとして捉えられた上でメモリ割り当て可否が判定される。調査用ＤＦＧ２２１Ａと一致する暫定結合ＤＦＧに対しては、図１１（ａ）に示すようなメモリ割り当てが可能である。即ち例えば、データメモリ部１２から第１段目への入力データＤａ及びＤｂを単位メモリＭ１及びＭ２の第１アドレスに割り当て、且つ、データメモリ部１２から第２段目への入力データＤｅを単位メモリＭ３の第１アドレスに割り当てることが可能である（ここでは、単位メモリＭ１、Ｍ２及びＭ３の第１アドレスに夫々データＤａ、Ｄｂ及びＤｅが割り当てられることが確定したものとする）。従って、ステップＳ２４において割り当て可能であると判断されてステップ２５に進み、ステップＳ２５において、調査用ＤＦＧ２２１Ａに対応するようにサブＤＦＧ２０１の全ノードを実際に仮想ＤＦＧ空間に配置する。この状態における仮想ＤＦＧ空間上のＤＦＧは、図１２（ａ）の調査用ＤＦＧ２２１Ａと同じである。
【００６７】
尚、ステップＳ２３及びＳ２４の処理の実行段階において、データメモリ部１２にデータを実際に割り当てながらメモリ割り当て可否を判定することができる。但し、ステップＳ２３及びＳ２４の処理の実行段階においては、グラフ彩色アルゴリズム等を用いてメモリ割り当てが可能かどうかだけを判断するようにし、データメモリ部１２へのデータの実際の割り当ては、後で行うようにしても良い。後者の方法の方が調査に必要な時間が少なくて済むため、ＤＦＧ結合処理の全体の処理時間が短くなる。
【００６８】
次に、ｉ＝１且つｉｍａｘ＝５であるため変数ｉに１が加算された後（ステップＳ２６及びＳ２７）、２番目の結合順番を有するサブＤＦＧ２０２が結合対象ＤＦＧに設定され（ステップＳ１３）、ｉ＝１のときと同様の処理が実行される。まず、結合対象ＤＦＧであるサブＤＦＧ２０２の左上隅ノード、即ちノードＮ２がＮＯＤＥ０に設定される。次に、変数ｙ及びｘに１が代入された後（ステップＳ１４及びＳ１５）、仮想ＤＦＧ空間における位置（ｘ，ｙ）、即ち位置（１，１）にＮＯＤＥ０以外の他のノードが既に配置されているか否かが判断される。このとき、仮想ＤＦＧ空間の位置（１，１）には、既にノードＮ１が配置されているためステップＳ１６からステップＳ２０へ進む。このとき、変数ｘは所定値ｘｍａｘと等しくないため（ステップ２０のＮ）変数ｘに１が加算されてから（ステップＳ２１）ステップＳ１６に戻る。この段階では（ｘ，ｙ）＝（２，１）である。仮想ＤＦＧ空間の位置（２，１）には他のノードが配置されていないため、ステップＳ１７に進み、仮想ＤＦＧ空間の位置（２，１）にＮＯＤＥ０（即ち、サブＤＦＧ２０２のノードＮ２）を配置した上で結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間に配置可能か否かを調査する。
【００６９】
この調査の際、仮想ＤＦＧ空間上の位置（２，１）にＮＯＤＥ０（即ち、サブＤＦＧ２０２のノードＮ２）を配置した上でサブＤＦＧ２０２の全ノードを仮想ＤＦＧ空間に配置させ、これによって得られる仮想ＤＦＧ空間上のＤＦＧを調査用ＤＦＧ２２２Ａ（図１２（ｂ）参照）として想定する。但し、ステップＳ２５の処理を１回以上実行した後に想定される調査用ＤＦＧには、ステップ２５にて既に配置されたノードが含まれているものとする。従って、図１２（ｂ）に示す如く、調査用ＤＦＧ２２２Ｂでは、位置（１，１）、（２，１）、（１，２）及び（２，２）に、夫々、ノードＮ１、Ｎ２、Ｎ４及びＮ５が配置されることになる。そうすると、調査用ＤＦＧ２２２Ａにおいてデータメモリ部１２から１段目への入力は、データＤａ、Ｄｂ、Ｄｃ及びＤｄの４種類となる。即ち、調査用ＤＦＧ２２２Ａにおいて、１段目のデータメモリ部１２へのアクセス数は４である。故に、調査用ＤＦＧ２２２Ａはアクセス数制限条件を充足しておらず、ノードＮ２を位置（２，１）に配置することができないため（ステップＳ１８のＮ）ステップＳ１９に進む。
【００７０】
アクセス数制限条件の未充足によってノードＮ２を１段目に配置できないのであるから、ステップ１９では配置段の変更が必要と判断され（ステップＳ１９のＹ）ステップＳ２２に進み、変数ｙに１が加算されてからステップＳ１５に戻って再度ステップＳ１６に至る。この段階では（ｘ，ｙ）＝（１，２）である。位置（１，２）には既にノードＮ４が配置されているため（ステップＳ１６のＹ）、ステップＳ２０及びＳ２１を介して（ｘ，ｙ）＝（２，２）となる。仮想ＤＦＧ空間の位置（２，２）には他のノードが配置されていないため、ステップＳ１７に進み、仮想ＤＦＧ空間の位置（２，２）にＮＯＤＥ０（即ち、サブＤＦＧ２０２のノードＮ２）を配置した上で結合対象ＤＦＧの全ノードを仮想ＤＦＧ空間に配置可能か否かを調査する。この調査の際、仮想ＤＦＧ空間上の位置（２，２）にＮＯＤＥ０（即ち、サブＤＦＧ２０２のノードＮ２）を配置した上でサブＤＦＧ２０２の全ノードを仮想ＤＦＧ空間に配置させ、これによって得られる仮想ＤＦＧ空間上のＤＦＧを調査用ＤＦＧ２２２Ｂとして想定する。
【００７１】
図１２（ｃ）に示す如く、調査用ＤＦＧ２２２Ｂでは、位置（１，１）、（１，２）、（２，２）及び（２，３）に、夫々、ノードＮ１、Ｎ４、Ｎ２及びＮ５が配置されることになる。調査用ＤＦＧ２２２Ｂにおいて、１段目に属するノードがデータメモリ部１２にアクセスするデータ（即ち、データＤａ及びＤｂ）の総数は２であり、２段目に属するノードがデータメモリ部１２にアクセスするデータ（即ち、データＤｅ、Ｄｃ及びＤｄ）の総数は３であり、３段目に属するノードがデータメモリ部１２にアクセスするデータ（即ち、データＤｃ）の総数は１である。即ち、調査用ＤＦＧ２２２Ｂにおいて、１段目のデータメモリ部１２へのアクセス数は２であり、２段目のデータメモリ部１２へのアクセス数は３であり、３段目のデータメモリ部１２へのアクセス数は１である。故に、調査用ＤＦＧ２２２Ｂはアクセス数制限条件を充足している。従って、ｘ＝２且つｙ＝２の状態でサブＤＦＧ２０２の全ノードが配置可能であると判断されて（ステップＳ１８のＹ）、ステップＳ２３に進む。
【００７２】
ステップＳ２３では、アクセス数制限条件及び接続条件の双方を満たすと判断された調査用ＤＦＧが暫定結合ＤＦＧとして捉えられた上で、即ち、調査用ＤＦＧ２２２Ｂが暫定結合ＤＦＧとして捉えられた上でメモリ割り当て可否が判定される。この際、過去のステップＳ２３において既にメモリ割り当て可能と判断されたメモリ割り当て状態は保持される。即ち、単位メモリＭ１、Ｍ２及びＭ３の第１アドレスに夫々データＤａ、Ｄｂ及びＤｅが割り当てられるという前提の下で（図１１（ａ）参照）、暫定結合ＤＦＧに対するメモリ割り当て可否が判定される。調査用ＤＦＧ２２２Ｂと一致する暫定結合ＤＦＧに対しては、図１１（ｂ）に示すようなメモリ割り当てが可能である。即ち、データＤｃ及びＤｄを、夫々、単位メモリＭ１及びＭ２の第２アドレスに割り当てることが可能である（ここでは、単位メモリＭ１及びＭ２の第２アドレスに夫々データＤｃ及びＤｄが割り当てられることが確定したものとする）。従って、ステップＳ２４において割り当て可能であると判断されてステップ２５に進み、ステップＳ２５において、調査用ＤＦＧ２２２Ｂに対応するようにサブＤＦＧ２０２の全ノードを実際に仮想ＤＦＧ空間に配置する。この状態における仮想ＤＦＧ空間上のＤＦＧは、図１２（ｃ）の調査用ＤＦＧ２２２Ｂと同じである。尚、メモリ割り当てでは、既に割り当てられたデータの割り当て状態を変更するようにしてもよい。即ち、“過去のステップＳ２３において既にメモリ割り当て可能と判断されたメモリ割り当て状態は保持される”と上述したが、この保持を行わずに、ステップＳ２３におけるメモリ割り当て可否を判断するようにしても良い。これにより、メモリ割り当て可能と判断される可能性が高くなるが、上記保持を行う場合と比べて、メモリ割り当てに関わる処理時間が長くなる。
【００７３】
サブＤＦＧ２０３に対しても同様の処理が成され、結果、図７に示す如くサブＤＦＧ２０３のノードＮ３及びＮ６は夫々位置（３，３）及び（３，４）に配置され、且つ、図１１（ｃ）に示す如くデータＤｆは単位メモリＭ３の第２アドレスに割り当てられる。
【００７４】
続いて、サブＤＦＧ２０４に対して同様の処理を行っていくと、次のことが分かる。
ノードＮ７を位置（１，３）に配置したならば、データメモリ部１２から３段目へ入力されるデータがＤｅ、Ｄｃ、Ｄｄ及びＤｆの４種類となり、アクセス数制限条件が不充足となる。尚、データメモリ部１２を介さずにノードＮ４の出力をノードＮ７に接続することで中間生成データＤｋはメモリアクセスの必要なデータではなくなる。
ノードＮ７を位置（１，４）に配置したならば、アクセス数制限条件は満たされる。しかし、データＤｅ及びＤｆが共に単位メモリＭ３に割り当てられているため、ノードＮ７を位置（１，４）に配置すると、４段目においてデータＤｅ及びＤｆをデータメモリ部１２から同時に読み出さなければならないにも関わらず、その同時読み出しを実行できない。つまり、これまでに配置結合したサブＤＦＧ（即ち、サブＤＦＧ２０１〜２０３）の配置段を変更しないならば、データＤｅ及びＤｆを異なる単位メモリに割り当てることは不可能である。
【００７５】
このため、サブＤＦＧ２０４のノードＮ７を位置（１，４）を配置したのでは、メモリ割り当てが不可能であると判断され（ステップＳ２４のＮ）、ステップＳ２２において変数ｙが４から５に変更される（即ち、配置段の変更が成される）。以降、同様の処理を行うことで、図７に示す如くサブＤＦＧ２０４のノードＮ７は位置（１，５）に配置される。図７の結合ＤＦＧ２１０では、ノードＮ４及びＮ７間を接続するために、位置（１，３）及び（１，４）の夫々にスルーノードｍｏｖを配置しているが、ノードＮ４の出力データＤｋをデータメモリ部１２を介してノードＮ７に入力することができる場合には、結合ＤＦＧ２１０からスルーノードｍｏｖを削除して、ノードＮ４の出力データＤｋをデータメモリ部１２を介してノードＮ７に入力するようにしても良い。スルーノードｍｏｖは、自身への入力データをそのまま自身の出力データとして送出するノードである。第１ノードの出力データを第２ノードに入力する必要がある場合において、第１ノードの出力を第２ノードの入力に直接接続できないとき、第１ノードの出力及び第２ノードの入力間にスルーノードｍｏｖを挿入するという第１選択肢、或いは、第１ノードの出力データをデータメモリ部１２を介して第２ノードに入力するという第２選択肢を選ぶことができる。ノードの密集度合いや、どちらの選択肢を選んだときに第１及び第２ノードを含む演算処理をより短時間で完了できるのか等を選択指標として、どちらかの選択肢を選ぶことができる。例えば、第１選択肢を選んだ方が、第２選択肢を選んだ場合との比較において、第２ノードがより上方側の段に配置されるのであれば、第１選択肢を選んだ方が良いと言える（演算処理の短時間化が見込まれるため）。
【００７６】
最後に、サブＤＦＧ２０５に対しても同様の処理を行うことで、図７の結合ＤＦＧ２１０が完成する。サブＤＦＧ２０５のノードＮ８及びＮ９を夫々位置（２，４）及び（２，５）に配置する際、ノードＮ５の出力をノードＮ８の入力に直接接続すると共にノードＮ４の出力を位置（１，３）のスルーノードｍｏｖを介してノードＮ８の入力に接続し、且つ、ノードＮ６の出力をノードＮ９の入力に直接接続することにより、中間生成データＤｋ、Ｄｍ及びＤｎは結合ＤＦＧ２１０においてメモリアクセスデータではなくなる。
【００７７】
結合ＤＦＧ２１０が得られると、図３のコマンドデータ生成部２３は、結合ＤＦＧ２１０の位置（ｘ，ｙ）におけるノードの機能がＡＬＵ［ｘ，ｙ］にて実現されるように、結合ＤＦＧ２１０からコマンドデータを生成する。
【００７８】
このように、各結合対象ＤＦＧの配置結合時において、各結合対象ＤＦＧをアクセス数制限（アクセス可能上限数）及びメモリ割り当てに適合させることで、それらの適合を確保しながらノードの並列度を高めることができるため、効率的な結合ＤＦＧを生成することができる。結果、リコンフィギュラブル装置１０における演算時間の短縮化、ひいては消費電力の削減が図られる。また、メモリ割り当て可否の判定には比較的多くの時間が必要となるため、図９の動作では、メモリ割り当て可否以外の条件が全て満たされた後に（即ち、ステップＳ１６の判定結果が“Ｎ”であって且つステップＳ１８の判定結果が“Ｙ”になった後に）メモリ割り当て可否の判定を行うようにしている。この結果、メモリ割り当て可否判定の必要実行回数が最小化され、ＤＦＧ処理の全体処理時間を短縮化することができる。
【００７９】
結合部３２で成されるべきメモリ割り当てと同様のメモリ割り当てをＤＦＧ分割部３１にて成すことも可能ではある。但し、データメモリ部１２にアクセスされるべきデータはサブＤＦＧの結合後にしか確定できないため、ＤＦＧ分割部３１にてメモリ割り当てを成すと、メモリ割り当ての回数が必要以上に多くなり、ＤＦＧ処理の全体処理時間が長くなることがある。即ち例えば、ＤＦＧ分割部３１にてメモリ割り当てを行う場合、ノードＮ４及びＮ７の直接接続によってデータＤｋをメモリアクセスデータから除外することが可能であるにも関わらす、ＤＦＧ分割処理の段階では、その除外の可否が不明であるために、データＤｋに対してもメモリ割り当てを実行する必要が生じる。このようなデータＤｋに対するメモリ割り当ては、図９を参照して上述した方法によれば割愛される。つまり、ＤＦＧ分割部３１においてはメモリ割り当てを実行せずに分割条件ＣＡを満たすように原ＤＦＧの分割だけを行い、メモリ割り当てをＤＦＧ結合部３２に任せることで全体の処理時間を短縮している。
【００８０】
結合部３２では、メモリ割り当てに適合しない場合（図９のステップＳ２４の判定結果が“Ｎ”の場合）、現在の結合対象ＤＦＧに対してのみ配置位置の変更を行う。これにより、再配置されるべきノードが結合対象ＤＦＧのノードのみに限定され、既に配置結合されたサブＤＦＧをも含めて配置位置の変更を行う方法と比べて、再配置の処理時間が短縮される。更に、図９の動作によれば、結合対象ＤＦＧのメモリ割り当て可否を判定する際、結合対象ＤＦＧに設定されているサブＤＦＧ（例えば、サブＤＦＧ２０２）の出力先のサブＤＦＧ（例えば、サブＤＦＧ２０４）は未だ仮想ＤＦＧ空間に配置されていないため、結合対象ＤＦＧの配置位置検討に出力先のノード配置を考慮する必要がない。よって、既に配置結合されたサブＤＦＧをも含めて再配置を行う場合よりも、図９の方法による結合対象ＤＦＧの再配置は処理量が少なくて済み、ＤＦＧ処理の全体処理時間の短縮化が図られる。
【００８１】
尚、上述の例では、サブＤＦＧ２０４のノードＮ７を位置（１，４）を配置した場合、メモリ割り当てが不可能であると判断されているが、仮に、図１４に示すようなメモリ割り当てを許容すれば、サブＤＦＧ２０４のノードＮ７を位置（１，４）に配置することも可能ではある。結合ＤＦＧの４段目に対して単位メモリＭ１及びＭ３からデータＤｅ及びＤｆを入力することが可能になるからである。図１４のメモリ割り当てでは、単位メモリＭ１、Ｍ２及びＭ３の第１アドレスに夫々データＤａ、Ｄｂ及びＤｅが割り当てられ且つ単位メモリＭ１、Ｍ２及びＭ３の第２アドレスに夫々データＤｃ、Ｄｄ及びＤｆが割り当てられているのに加えて、単位メモリＭ１の第３アドレスにデータＤｅが再度割り当てられている。
【００８２】
しかし、図１４のメモリ割り当てを採用すると、図１１（ｃ）のメモリ割り当てと比較してメモリの必要容量が大きくなる。また、単位メモリＭ１に対するデータＤｅの書き込みと単位メモリＭ１に対するデータＤａ又はＤｃの書き込みが同時に発生することを防止するための調停処理が別途必要になる。故に、図７の結合ＤＦＧ２１０が得られるように、同一のデータを複数の単位メモリに共通に割り当てる（図１４の例において、データＤｅを単位メモリＭ１及びＭ３に共通に割り当てる）ことを制限することが望ましい（この制限の下でステップＳ２３のメモリ割り当て可否を判定することが望ましい）。
【００８３】
［第２処理具体例］
次に、第２処理具体例を説明する。図１５及び図１６には、第２処理具体例における原ＤＦＧ３００、サブＤＦＧ３０１〜３０４及び結合ＤＦＧ３１０が示されている。
【００８４】
原ＤＦＧ３００は、４行３列のＤＦＧであって、８つのノードＮ１〜Ｎ８を含む。原ＤＦＧ３００において、１段目の位置である位置（１，１）及び（２，１）に夫々ノードＮ１及びＮ２が配置されており、２段目の位置である位置（１，２）及び（３，２）に夫々ノードＮ３及びＮ４が配置されており、３段目の位置である位置（１，３）、（２，３）及び（３，３）に夫々ノードＮ５、Ｎ６及びＮ７が配置されており、４段目の位置である位置（２，４）にノードＮ８が配置されている。
また、原ＤＦＧ３００は、何れかのノードに対して互いに異なるデータＤａ、Ｄｂ、Ｄｃ及びＤｄがデータメモリ部１２より入力されるべきことを規定している。具体的には、データメモリ部１２から、ノードＮ１に対してデータＤａ及びＤｂが入力され、且つ、ノードＮ２に対してデータＤｃが入力され、且つ、ノードＮ４に対してデータＤｃ及びＤｄが入力され、且つ、ノードＮ６に対してデータＤａ及びＤｂが入力され、且つ、ノードＮ７に対してデータＤｄが入力されるべきことが、原ＤＦＧ３００に規定されている。
更に、原ＤＦＧ３００において、ノードＮ１及びＮ２の出力データはノードＮ３に入力され、ノードＮ３及びＮ４の出力データは夫々ノードＮ５及びＮ７に入力され、ノードＮ５、Ｎ６及びＮ７の出力データはノードＮ８に入力されている。
【００８５】
原ＤＦＧ３００では、全ての段においてデータメモリ部１２へのアクセス数が３以下である。従って、メモリ割り当てを考慮しない従来のＤＦＧ処理では、原ＤＦＧ３００がそのまま最終ＤＦＧとなる。また、実際とは異なるが、“原ＤＦＧの各段におけるデータメモリ部１２へのアクセス数がアクセス可能上限数以下であれば原ＤＦＧの分割が不要である”と分割部３１に判断させる場合においても、原ＤＦＧ３００がそのまま最終ＤＦＧとなる。
【００８６】
但し、この原ＤＦＧ３００に対してメモリ割り当てを行おうとすると、データＤｄの割り当てが不可能となる。図１７（ａ）〜（ｃ）を参照し、これについて説明を加える。原ＤＦＧ３００の初段に注目したとき、図１７（ａ）に示す如く、入力データＤａ、Ｄｂ及びＤｃを夫々単位メモリＭ１、Ｍ２及びＭ３に割り当てることができる。原ＤＦＧ３００の２段目に対してはデータメモリ部１２からデータＤｃ及びＤｄが入力されるため、データＤｄを図１７（ｂ）に示す如く単位メモリＭ１又は図１７（ｃ）に示す如く単位メモリＭ２に割り当てる必要がある。次に、原ＤＦＧ３００の３段目に注目すると、データメモリ部１２から原ＤＦＧ３００の３段目に対してデータＤａ、Ｄｂ及びＤｄを入力する必要があるが、図１７（ｂ）及び図１７（ｃ）のどちらを採用しても、データＤａ、Ｄｂ及びＤｄを同時にデータメモリ部１２から読み出すことはできない。故に、原ＤＦＧ３００をそのまま最終ＤＦＧにするとデータＤｄの割り当てが不可能となる。
【００８７】
これを考慮し、分割部３１は、原ＤＦＧ３００の各段におけるデータメモリ部１２へのアクセス数（データメモリ部１２に入力又はデータメモリ部１２から出力されるデータの数）を調べ、調べたアクセス数が３以上になる段が原ＤＦＧ３００に含まれている場合には、サブＤＦＧにおいて各段のアクセス数が２以下となるように原ＤＦＧを分割する。この結果、図１５の例では、原ＤＦＧ３００からサブＤＦＧ３０１〜３０４が生成されている。サブＤＦＧ３０１〜３０４の夫々は原ＤＦＧ３００の一部に相当し、サブＤＦＧ３０１〜３０４は互いに重複するノードを含まない。図１５に示す如く、サブＤＦＧ３０１はノードＮ１を含み、サブＤＦＧ３０２はノードＮ２、Ｎ３及びＮ５を含み、サブＤＦＧ３０３はノードＮ４及びＮ７を含み、サブＤＦＧ３０４はノードＮ６及びＮ８を含む。
【００８８】
得られたサブＤＦＧ３０１〜３０４に対して、図９に示される上述のＤＦＧ結合処理を実行することにより、図１６の結合ＤＦＧ３１０が得られる。図１８には、結合ＤＦＧ３１０に対するメモリ割り当ての様子が示されている。即ち、結合ＤＦＧ３１０について、単位メモリＭ１、Ｍ２及びＭ３の第１アドレスに夫々データＤａ、Ｄｂ及びＤｃが割り当てられ、単位メモリＭ１の第２アドレスにデータＤｄが割り当てられている。原ＤＦＧ３００及び結合ＤＦＧ３１０間においてノードＮ１〜Ｎ５及びＮ７の配置位置は同じであるが、原ＤＦＧ３００と異なり結合ＤＦＧ３１０では、位置（２，４）及び（２，５）に夫々ノードＮ６及びＮ８が配置され且つ位置（１，４）及び（３，４）にスルーノードｍｏｖが配置されている。この結果、図１８に示すようなメモリ割り当てが可能となる。
【００８９】
結合ＤＦＧ３１０が得られると、図３のコマンドデータ生成部２３は、結合ＤＦＧ３１０の位置（ｘ，ｙ）におけるノードの機能がＡＬＵ［ｘ，ｙ］にて実現されるように、結合ＤＦＧ３１０からコマンドデータを生成する。
【００９０】
［ＤＦＧ処理の内容の表現例］
本実施形態に係るＤＦＧ処理を以下のように表現することもできる。
【００９１】
分割部３１は、原ＤＦＧの各段におけるデータメモリ部１２へのアクセス数と所定のアクセス可能上限数とに基づき原ＤＦＧの分割要否を判断し、原ＤＦＧがデータメモリ部１２へのアクセスに対応していない場合、原ＤＦＧの分割が必要と判断して原ＤＦＧを複数のサブＤＦＧに分割する。原ＤＦＧがデータメモリ部１２へのアクセスに対応している場合には、原ＤＦＧの分割が不要と判断され原ＤＦＧがそのまま最終ＤＦＧとなる。
【００９２】
分割部３１は、原ＤＦＧの各段におけるデータメモリ部１２へのアクセス数（データメモリ部１２に入力又はデータメモリ部１２から出力されるデータの数）を調べることができる。そして、分割部３１は、調べたアクセス数がアクセス可能上限数よりも大きい段が原ＤＦＧに含まれている場合、原ＤＦＧがデータメモリ部１２へのアクセスに対応していないと判断することができる。或いは、調べたアクセス数がアクセス可能上限数以上となる段が原ＤＦＧに含まれている場合、原ＤＦＧがデータメモリ部１２へのアクセスに対応していないと判断することができる。また、第２処理具体例の原ＤＦＧ３００のように、データメモリ部１２から原ＤＦＧに入力されるべきデータ及び原ＤＦＧからデータメモリ部１２に出力されるべきデータの中に、データメモリ部１２に割り当てることのできないデータが存在している場合にも、原ＤＦＧがデータメモリ部１２へのアクセスに対応していないと判断することができる。
【００９３】
結合部３２は、複数のサブＤＦＧを互いに結合することによりデータメモリ部１２へのアクセスに対応した結合ＤＦＧを生成する。結合ＤＦＧの各段におけるデータメモリ部１２へのアクセス数がアクセス可能上限数以下であって、且つ、データメモリ部１２から結合ＤＦＧに入力されるべきデータ及び結合ＤＦＧからデータメモリ部１２に出力されるべきデータが全てデータメモリ部１２に割り当て可能であるとき、結合ＤＦＧはデータメモリ部１２へのアクセスに対応していると言え、そうでないとき、結合ＤＦＧはデータメモリ部１２へのアクセスに対応していないと言える。
【００９４】
複数のサブＤＦＧからデータメモリ部１２へのアクセスに対応した結合ＤＦＧが生成される場合、サブＤＦＧの配置位置の全部又は一部は（換言すれば、サブＤＦＧのノードの配置位置の全部又は一部）は、原ＤＦＧ及び結合ＤＦＧ間で互いに異なる。第１処理具体例の場合、例えば、原ＤＦＧ２００上におけるサブＤＦＧ２０２のノードＮ２の配置位置は（２，１）であるが、結合ＤＦＧ２１０上におけるサブＤＦＧ２０２のノードＮ２の配置位置は（２，２）である。
【００９５】
また、特許文献１に示す如く、全部又は一部のサブＤＦＧを必要に応じて変形し、変形後のサブＤＦＧを仮想ＤＦＧ空間上に配置することで結合ＤＦＧに形成するようにしても良い。サブＤＦＧを変形する際、特許文献１に示されるように、当該サブＤＦＧ内のノードの依存関係（接続関係）を維持したまま当該サブＤＦＧの変形を行ってもよい。サブＤＦＧを形成する複数のノード間の位置関係を変更することは、サブＤＦＧの変形に含まれる。例えば、図１９に示す如く、当初においては位置（１，１）、（２，１）及び（１，２）に夫々ノードＮ１、Ｎ２及びＮ３が配置されていたサブＤＦＧについて、ノードＮ３の配置位置を位置（１，２）から位置（２，２）に変更することは、サブＤＦＧの変形に含まれる。
【００９６】
また、結合部３２は、複数のサブＤＦＧの夫々を個別に結合対象ＤＦＧとして設定し、結合ＤＦＧが形成されるべき仮想ＤＦＧ空間上において結合対象ＤＦＧの配置位置を決定する、即ち結合ＤＦＧ上における結合対象ＤＦＧの配置位置を決定する。この際、結合部３２は、結合対象ＤＦＧのデータメモリ部１２へのアクセスの適合可否を判定する第１判定処理（換言すれば、結合対象ＤＦＧがデータメモリ部１２へのアクセスに適合しているか否かを判定する第１判定処理）と、その適合可否判定以外の配置結合条件の充足判定を行う第２判定処理と、を実行する。ここで、配置結合条件の充足が確認された後に第１判定処理を実行するようにすると良い。
【００９７】
第１判定処理におけるアクセスの適合可否の判定には、少なくとも、図９のステップＳ２３におけるメモリ割り当て可否の判定が含まれる。換言すれば、第１判定処理には、生成中の結合ＤＦＧとも言うべき暫定結合ＤＦＧの入力データ又は出力データをデータメモリ部１２に格納可能であるかを判定する処理ＰＲＣＡが、少なくとも含まれる。ここにおける暫定結合ＤＦＧの入力データとは、データメモリ部１２から暫定結合ＤＦＧのノードに入力されるべきデータを指し、ここにおける暫定結合ＤＦＧの出力データとは、暫定結合ＤＦＧのノードからデータメモリ部１２に出力されるべきデータを指す。ステップＳ２３においてメモリ割り当てが可能と判定される状態は、結合対象ＤＦＧのデータメモリ部１２へのアクセスが適合している状態に相当し、ステップＳ２３においてメモリ割り当てが不可能と判定される状態は、結合対象ＤＦＧのデータメモリ部１２へのアクセスが適合していない状態に相当する。上述したように、メモリ割り当て可否判定には比較的大きな時間が必要となるため、メモリ割り当ての可否判定以外の条件の充足判定後にメモリ割り当ての可否判定を行うようにすることで、メモリ割り当て可否判定の必要実行回数が最小化され、ＤＦＧ処理の全体処理時間を短縮化することができる。
【００９８】
第１判定処理におけるアクセスの適合可否の判定に、図９のステップＳ１７におけるアクセス制限条件の判定も更に含まれていると考えても良い。換言すれば、暫定結合ＤＦＧ（調査用ＤＦＧ）の各段におけるデータメモリ部１２へのアクセス数がアクセス可能条件数以下であるかを判定する処理ＰＲＣＢが、第１判定処理に更に含まれていると考えても良い。
【００９９】
第１判定処理に上記の処理ＰＲＣＡ及びＰＲＣＢが含まれている場合、第２判定処理には、図９のステップＳ１７における処理ＰＲＣＢ以外の処理ＰＲＣＣと、図９のステップＳ１６における処理ＰＲＣＤと、が含まれる。処理ＰＲＣＤは、仮想ＤＦＧ空間上における位置（ｘ，ｙ）にＮＯＤＥ０以外のノードが既に配置されているか否かを判断する処理である。処理ＰＲＣＣには、図９のステップＳ１７における接続条件の充足／不充足を判定する処理が含まれる。第１判定処理に処理ＰＲＣＢが含まれていないと考える場合には、第２判定処理に処理ＰＲＣＢ、ＰＲＣＣ及びＰＲＣＤが含まれている、と考えることができる。
【０１００】
結合部３２は、結合ＤＦＧ上における結合対象ＤＦＧの配置位置を暫定的に定めた状態において（即ち、結合対象ＤＦＧの左上隅のノードであるＮＯＤＥ０を仮想ＤＦＧ空間上の位置（ｘ，ｙ）に暫定的に配置した状態において）、結合対象ＤＦＧのデータメモリ部１２へのアクセスの適合可否を判定し、その判定結果が適合不可である場合、結合ＤＦＧ上における結合対象ＤＦＧの配置位置を変更する。この配置位置を変更する処理は、ステップＳ２３及びＳ２４を介して実行されるステップＳ２２の処理を含み、更に、ステップＳ１７〜Ｓ１９を介して実行されるステップＳ２２の処理を含みうる。
【０１０１】
＜＜変形等＞＞
本発明の実施形態は、特許請求の範囲に示された技術的思想の範囲内において、適宜、種々の変更が可能である。以上の実施形態は、あくまでも、本発明の実施形態の例であって、本発明ないし各構成要件の用語の意義は、以上の実施形態に記載されたものに制限されるものではない。上述の実施形態に適用可能な注釈事項として、以下に、注釈１〜注釈５を記す。各注釈に記載した内容は、矛盾なき限り、任意に組み合わせることが可能である。
【０１０２】
［注釈１］
上述の説明文中に示した具体的な数値は、単なる例示であって、当然の如く、それらを様々な数値に変更することができる。例えば、データメモリ部１２に含まれる単位メモリの個数は３以外であっても良い。
【０１０３】
［注釈２］
上述の第１及び第２処理具体例では、データメモリ部１２へのアクセスがデータメモリ部１２からＤＦＧへのデータ入力である場合について説明したが、データメモリ部１２へのアクセスがＤＦＧからデータメモリ部１２へのデータ出力である場合、及び、データメモリ部１２へのアクセスがＤＦＧからデータメモリ部１２へのデータ出力を含んでいる場合も、上述と同様に処理できる。
【０１０４】
各単位メモリは、１クロック期間につき１入力及び１出力の双方が可能な２ポートメモリであっても良いし、１クロック期間につき１入力及び１出力のどちらかしかできない１ポートメモリであっても良い。
【０１０５】
各単位メモリが２ポートメモリである場合を考える。この場合、各単位メモリはデータの入力とデータの出力を同一のクロック期間中に成すことができるため、メモリアクセスに関する判定を、データの入力及びデータの出力に対して別個に行うことができる。具体的には、上述の例の如く単位メモリの個数が３である場合、サブＤＦＧの各段におけるデータメモリ部１２からの入力データ数及びデータメモリ部１２への出力データ数が各々２以下となるように分割処理を成すことができる。また、結合処理では、調査用ＤＦＧの各段におけるデータメモリ部１２からの入力データ数及びデータメモリ部１２への出力データ数を個別にアクセス可能上限数（即ち３）と比較することができ、双方がアクセス可能上限数以下であるとき、アクセス数制限条件が満たされると判断することができる。
【０１０６】
各単位メモリが１ポートメモリである場合を考える。この場合には、入力と出力を合わせて考慮して、メモリアクセスに関する判定を行う必要がある。この際、データの遅延も考慮する必要がある。具体的には、上述の例の如く単位メモリの個数が３である場合、サブＤＦＧの各段におけるデータメモリ部１２からの入力データ数と、その入力と同時に成されるデータメモリ部１２へのデータの出力数との和が２以下となるように、分割処理を成すことができる。また、結合処理では、調査用ＤＦＧの各段におけるデータメモリ部１２からの入力データ数と、その入力と同時に成されるデータメモリ部１２へのデータの出力数との和が３以下であるならば、アクセス数制限条件が満たされると判断することができる。ＡＬＵ及びデータメモリ部１２間に保持回路（Ｄ型フリップフロップ等）が設けられている場合には、ＡＬＵからデータが出力されてデータメモリ部１２に入力されるまでの間に遅延が存在するため、この遅延も考慮される。即ち例えば、第１処理具体例の説明とは異なるが、図６のサブＤＦＧ２０２におけるノードＮ５の出力データＤｍがデータメモリ部１２に出力されると仮定したならば、ノードＮ５がデータＤｍを出力してから１クロック期間分の遅延後にデータＤｍが実際にデータメモリ部１２に入力されるため、そのような遅延を考慮して、メモリ割り当てを含むＤＦＧ処理が成されるべきである。
【０１０７】
［注釈３］
ＡＬＵアレイ回路１１の段数を表すＹは２以上であって且つ変数ｙは“１≦ｙ≦Ｙ”を満たすと上述したが、Ｙは１以上の整数であっても良く、またＡＬＵアレイ回路１１の最下段のＡＬＵの出力を最上段のＡＬＵに渡すことができるため、ＤＦＧにおいては“ｙ≦Ｙ”が満たされる必要はない。ｙ＞Ｙ−１のとき、ＤＦＧの位置（ｘ，ｙ）に配置されたノードは、ＡＬＵ［ｘ，（（ｙ−１）％Ｙ）＋１］にて実現される。ここで、（ｙ−１）％Ｙは、（ｙ−１）をＹにて割ったときの余りを示す。
【０１０８】
［注釈４］
リコンフィギュラブル装置１０は、任意の機器（携帯電話機などの携帯端末）に搭載されるものであっても良い。
【０１０９】
［注釈５］
図１のリコンフィギュラブル装置１０を、ハードウェアによって、或いは、ハードウェアとソフトウェアの組み合わせによって構成することができる。
【符号の説明】
【０１１０】
１０  リコンフィギュラブル装置
１１  ＡＬＵアレイ回路
１２  データメモリ部
１３  制御部
１４  コマンドメモリ部
２２  ＤＦＧ処理部
３１  ＤＦＧ分割部
３２  ＤＦＧ結合部
Ｍ１〜Ｍ３  単位メモリ
【図１】
2012068801.tif 000003
【図２】
2012068801.tif 000004
【図３】
2012068801.tif 000005
【図４】
2012068801.tif 000006
【図５】
2012068801.tif 000007
【図６】
2012068801.tif 000008
【図７】
2012068801.tif 000009
【図８】
2012068801.tif 000010
【図９】
2012068801.tif 000011
【図１０】
2012068801.tif 000012
【図１１】
2012068801.tif 000013
【図１２】
2012068801.tif 000014
【図１３】
2012068801.tif 000015
【図１４】
2012068801.tif 000016
【図１５】
2012068801.tif 000017
【図１６】
2012068801.tif 000018
【図１７】
2012068801.tif 000019
【図１８】
2012068801.tif 000020
【図１９】
2012068801.tif 000021
【手続補正書】
【提出日】平成22年10月7日(2010.10.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２
【補正方法】変更
【補正の内容】
【請求項２】
前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段を更に備え、
前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を前記原データフローグラフ上におけるサブデータフローグラフの配置位置と異ならせることを特徴とする請求項１に記載のデータフローグラフ処理装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項７
【補正方法】変更
【補正の内容】
【請求項７】
機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、
原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段と、
前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段と、を備え、
前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を前記原データフローグラフ上におけるサブデータフローグラフの配置位置と異ならせることを特徴とするデータフローグラフ処理装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
具体的には例えば、第１のデータフローグラフ処理装置に、前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段を更に設けておくとよい。そして例えば、前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を前記原データフローグラフ上におけるサブデータフローグラフの配置位置と異ならせる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
機能の変更が可能な複数の論理回路を備えたリコンフィギュラブル装置の動作設定に必要なデータフローグラフを処理するデータフローグラフ処理装置であって、原データフローグラフが前記論理回路の入力又は出力データを格納するメモリへのアクセスに対応していない場合、前記原データフローグラフを複数のサブデータフローグラフに分割する分割手段と、前記複数のサブデータフローグラフを互いに結合することにより、前記メモリへのアクセスに対応した結合データフローグラフを生成する結合手段と、を備え、前記結合手段は、前記結合データフローグラフが前記メモリへのアクセスに対応するように、前記結合データフローグラフ上におけるサブデータフローグラフの配置位置を前記原データフローグラフ上におけるサブデータフローグラフの配置位置と異ならせることを特徴とする。