データフローグラフ生成装置、設定データ生成装置、処理装置、及びデータフローグラフ生成方法
【課題】多倍長演算が可能なリコンフィギュラブルプロセッサに対応したデータフローグラフを自動的に生成する。
【解決手段】リコンフィギュラブル回路の論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、演算に対応するノードを生成するノード生成部を備え、前記ノード生成部は、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【解決手段】リコンフィギュラブル回路の論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、演算に対応するノードを生成するノード生成部を備え、前記ノード生成部は、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、機能の変更が可能な論理回路の複数の集合体と、それぞれの集合体の間に設けられて集合体間の論理回路の接続を選択的に確立可能な接続部を備えるリコンフィギュラブル回路に提供するデータフローグラフを生成するデータフローグラフ生成装置に関する。特に多倍長演算が可能なリコンフィギュラブル回路に対応したデータフローグラフの自動生成に関する。
【背景技術】
【０００２】
近年、ＡＬＵ(Arithmetic Logic Unit)と呼ばれる基本演算機能を複数持つ多機能素子を多段に並べたＡＬＵアレイを用いたリコンフィギュラブルプロセッサの検討が行われている（例えば、特許文献１）。リコンフィギュラブルプロセッサでは、設定データが設定されることにより、ＡＬＵ回路の演算機能構成と接続部が制御され、全体として所期の演算処理回路を実現することができる。設定データは、一般にＣ言語などの高級プログラム言語で記述されたソースプログラムからＤＦＧ（Data Flow Graph、データフローグラフ）と呼ばれるデータフローを作成し、その情報をもとに作成される。ＤＦＧは、入力される変数や定数の演算の流れを、段階的にグラフ構造で表現したものである。
【特許文献１】特開２００５−２７５６９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
リコンフィギュラブルプロセッサは、ＡＬＵの演算ビット幅を超える演算を複数のＡＬＵを用いて処理するような、多倍長演算も可能なものもある。多倍長演算とは、例えば、演算ビット幅が16ビットのＡＬＵを備えたプロセッサにより、32ビットの演算を行うことをいう。しかし、従来の方法により生成されるＤＦＧ生成は、上記のような多倍長演算対応のプロセッサでの演算に対応しない。
【０００４】
例えば、図１６（ａ）のプログラムで記述される演算を行うＤＦＧの生成を考える。このプログラムは、short型（16ビット）の変数ｘと、int型（32ビット）の変数ｙを入力変数とし、int型の変数yを出力変数とした、関数func0(x,*y)の行う演算を示したものである。この関数func0(x,*y)では、まず「x+=1」において、入力変数ｘに１を加算し、加算した結果をｘに置き換える。そして次の、「*y=-x」では、入力変数であるｙからｘを減算し、減算結果をｙに置き換えて、出力する。このような関数func0(x,*y)の演算を行うＤＦＧを従来の方法により生成すると、図１６（ｂ）のようになる。演算ノードn01では、ｘと１の加算を行い、その結果（n01outとする）を演算ノードn0へ出力する。演算ノードn02では、yからn01outを減算し、その結果を出力する。このＤＦＧにより正しい演算を行うには、演算子が32ビットのＡＬＵを備えたプロセッサを用いる必要があり、ＡＬＵの演算ビット幅が32ビット未満の多倍長演算対応のプロセッサでの演算に対応しない。
【０００５】
そこで、本発明は上記の事情に鑑み、リコンフィギュラブル回路を用いて多倍長演算を行うためのデータフローグラフを自動的に生成する装置、或いは方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のある態様は、演算機能の変更が可能なリコンフィギュラブル回路の動作設定に必要なデータフローグラフであって、前記論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成装置に関する。この態様のデータフローグラフ生成装置は、前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、演算に対応するノードを生成するノード生成部を備える。前記ノード生成部は、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【０００７】
例えば、演算ビット数決定手段にて決定された演算ビット数が32ビットであって、リコンフィギュラブル回路の論理回路により演算可能な演算ビット数が16ビットであるような場合、１つの演算を２つの演算ノードに分けて行うようなＤＦＧを生成する。
【０００８】
係るＤＦＧ生成装置によれば、演算のビット数がリコンフィギュラブル回路の論理回路により演算可能なビット数よりも大きいときは演算を複数の演算ノードに分けて行うＤＦＧを生成する。これにより、リコンフィギュラブル回路による倍長演算が可能となる。
【０００９】
上記のデータフローグラフ生成装置は、動作を示した記述（例えば、Ｃ言語等で記述されたプログラム）に基づいてデータフローグラフを生成する。或いは、上記データフローグラフ生成装置は、既に生成されたデータフローグラフを、リコンフィギュラブル回路の演算ビット数に合うように再構成するものであっても良い。例えば、32ビット対応の論理回路を有するリコンフィギュラブル回路を想定して生成した32ビット演算を行うＤＦＧを、16ビット対応の論理回路を有するリコンフィギュラブル回路での演算用に再構成するものであっても良い。
【００１０】
好ましくは、前記演算ビット数決定部は、演算の入力データのビット数に基づいて前記演算ビット数を決定する。また、前記入力データのビット数が前記出力データのビット数よりも大きいとき、前記演算ビット数を出力データのビット数と等しく設定した場合と、前記出力データのビット数よりも大きく設定した場合の演算結果を比較し、比較した演算結果が等しいとき、出力データのビット数を演算ビット数と決定しても良い。
【００１１】
演算の入力データのビット数と出力データのビット数から、演算に必要最小限な演算ビット数を決定する。これにより、ＤＦＧの小型化が図れ、その結果、演算に使用するリコンフィギュラブル回路を少なくすることができる。
【００１２】
好ましくは、前記ノード生成部は、１つの演算に対して複数の演算ノードが生成されたとき、前記演算の入力、及び/又は出力データを、それぞれの演算ノードの入力、及び/又は出力に対応させるための変換を行う入出力変換部を備える。
【００１３】
例えば、前記入出力変換部は、入力データのビット数が前記論理回路の入力ビット数よりも大きいとき、前記入力データを複数の入力データに分割して、それぞれの演算ノードの入力に対応させるようなデータフローグラフを生成する。
【００１４】
或いは、前記入出力変換部は、出力データのビット数が前記論理回路の出力ビット数よりも大きいとき、前記出力データを複数の出力データに分割して、それぞれの演算ノードの出力に対応させるようなデータフローグラフを生成する。
【００１５】
また、前記ノード生成部は、演算の入力データのビット数が前記演算のノードに対応した１以上の前記論理回路で入力可能な総ビット数よりも小さいとき、前記入力データのビット拡張用ノードを生成し、前記入力データを生成したビット拡張用ノードの入力に対応させるようなデータフローグラフを生成してもよい。
【００１６】
前記ノード生成部は、演算の出力データのビット数が前記演算のノードに対応した１以上の前記論理回路で出力可能な総ビット数よりも大きいとき、前記出力データの出力用ノードを生成してもよい。
【００１７】
本発明の設定データ生成装置は、上記のいずれかのデータフローグラフ生成装置と、データフローグラフ生成装置で生成されたデータフローグラフをリコンフィギュラブル回路に供給するための設定データに変換するデータ変換部を備える。
【００１８】
本発明の処理装置は、設定データに従って動作するリコンフィギュラブル回路と、上記設定データ生成装置で生成された設定データを前記リコンフィギュラブル回路に順次供給する制御部を備えることを特徴とする。
【００１９】
本発明のデータフローグラフ生成方法は、演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成方法において、前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定ステップと、演算に対応するノードを生成するノード生成ステップによりデータフローグラフを生成し、前記ノード生成ステップでは、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【発明の効果】
【００２０】
この発明によれば、リコンフィギュラブル回路を用いて多倍長演算を行うためのデータフローグラフを自動的に生成することができる。
【発明を実施するための最良の形態】
【００２１】
図１は、実施の形態に係る処理装置１０、設定データ生成装置３０の構成を示す図である。
【００２２】
＜処理装置１０の構成＞
処理装置１０は、演算機能を有し、回路構成が再構成可能である。この処理装置１０は、１チップとして構成される集積回路からなり、リコンフィギュラブル回路１２、設定部１４、制御部１８、入力回路２０、出力回路２２を備える。
【００２３】
リコンフィギュラブル回路１２は、機能の変更が可能なＡＬＵによる論理回路の集合体を複数備えた構造を有する。リコンフィギュラブル回路１２は、後述する設定部１４から供給される設定データに従って動作する演算回路として機能する。即ち、入力回路２０からの入力データに対して、設定データに従った演算を行い、演算結果を出力回路２０へ出力する。。このリコンフィギュラブル回路１２の構成については後で詳しく説明する。
【００２４】
設定部１４は、リコンフィギュラブル回路１２に所期の演算回路を構成するための設定データを供給する。設定部１４から設定データを供給することにより、リコンフィギュラブル回路１２は所期の演算回路として再構成される。この設定データは後述する設定データ生成装置２０で生成される。
【００２５】
制御部１８は、処理装置１０の各部、即ち、リコンフィギュラブル回路１２、設定部１４、入力回路２０、出力回路２２を制御する。また、クロック機能を有し、クロック信号を、リコンフィギュラブル回路１２、入力回路２０、出力回路２２に供給する。
【００２６】
入力回路２０は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成される。入力回路２０は、外部から入力されたデータを、リコンフィギュラブル回路１２での演算タイミングに同期するように、リコンフィギュラブル回路１２へ入力させる。
【００２７】
出力回路２２は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２から出力されるデータを所期のタイミングで外部に出力する。
【００２８】
＜設定データ生成装置３０の構成＞
設定データ生成装置３０は、データフローグラフ生成部３２、設定データ生成部３４、記憶部３６を備える。
【００２９】
記憶部３６には、プログラム３８、データフローグラフ４０、設定データ４２などが記憶されている。記憶部３６に記憶されるプログラムは、リコンフィギュラブル回路１２で実現されるべき処理の動作をＣ言語などの高級言語で記述したものである。
【００３０】
データフローグラフ生成部３２は、このプログラムを解析し、リコンフィギュラブル回路を動作設定するためのデータフローグラフ４０に変換して記憶部３６に格納する。ＤＦＧとは、回路における演算間の実行順序の依存関係を表現したものであり、入力変数および定数の演算の流れをグラフ構造で示したものである。一般に、ＤＦＧは、上から下に向かって演算が進むように作成される。
【００３１】
設定データ生成部３４は、データフローグラフ生成部３２で生成されたデータフローグラフ４０から設定データ４２を生成する。設定データ４２は、データフローグラフ４０をリコンフィギュラブル回路１２にマッピングするためのデータであり、リコンフィギュラブル回路１２における論理回路の機能や論理回路間の接続関係を定める。設定データ生成部３４により生成された設定データ４０は、設定部１４を介してリコンフィギュラブル回路１２へ供給される。
【００３２】
なお、設定データを複数のリコンフィギュラブル回路に分けて供給したり、１つのリコンフィギュラブル回路に複数回に分けて供給したりする場合等においては、１つのプログラムから複数の設定データを生成しても良い。
【００３３】
＜リコンフィギュラブル回路１２の構成＞
図２は、リコンフィギュラブル回路１２の構成の一部を示すものである。
【００３４】
図２のように、リコンフィギュラブル回路１２では、演算器（ＡＬＵ）、ＭＵＸ、及び２つのＤＦＦからなる論理回路（同図ではＬ１１、Ｌ１２、Ｌ２１、…、Ｌ４２として示している）がアレイ状に配列される。各論理回路の演算器は、演算機能を選択的に実行可能な構成となっている。各演算器には、設定部１４から演算器の機能を制御する命令セットが設定される。演算器には予め論理和、論理積、ビットシフトなどを行う演算回路が実装されており、命令セットによってどの演算を行うかが選択される。
【００３５】
上記の命令セット、接続データセットからなる構成情報は、一般にＣ言語などの高品位言語で記述されたプログラムから作成される。Ｃ言語のプログラムは、データフローグラフ生成部３２によってＤＦＧへ変換される。そして、設定データ生成部３４は、このＤＦＧから演算器の命令と演算器間の接続を決定し、これらの情報からリコンフィギュラブル回路１２への構成情報に変換する。
【００３６】
論理回路間の接続には一定の制限が課されている。即ち、上段の論理回路から下段算ユニットへの接続は、同じ列か、隣接する左右の列へのものに制限されており、論理回路段の間で物理的に近接して配列された論理回路同士を接続可能とするように構成される。例えば、論理回路Ｌ２１からの出力は、Ｌ１２、Ｌ２２、及びＬ３２の３つの論理回路にのみ接続されるような配線構造となっている。
【００３７】
各論理回路において、演算器（ＡＬＵ）での演算結果は、ＭＵＸ（選択器）へ出力される。また、各演算器の演算結果は、ＤＦＦ（Ｄ型フリップフロップ）を介して、同列次段の論理回路内のＭＵＸへも出力される（遅延データ出力）。例えば、論理回路Ｌ１１の演算器による演算結果は、Ｌ１１のＭＵＸだけでなく、Ｌ１１のＤＦＦ２を介してＬ１２のＭＵＸへも出力される。ＭＵＸは、演算器からの出力と、前段の演算器からの出力（遅延データ入力）を選択して出力する。例えば、論理回路Ｌ１２のＭＵＸは、Ｌ１２の演算器からの出力と、Ｌ１１の演算器からの出力を選択して出力する。
【００３８】
なお、上記説明したリコンフィギュラブル回路１２は、本願出願人が開発した接続制限付きのリコンフィギュラブル回路（特開２００５−１８２６５４号公報の図９参照）を改良したものである。リコンフィギュラブル回路１２は、各論理回路からの出力が左下段、下段、右下段の３つの論理回路のみに接続配線される構成である点については、上記公報に記載のリコンフィギュラブル回路と共通している。しかし、演算器からの出力と、前段の演算器からの出力（遅延データ入力）を選択して出力するＭＵＸを備える点（言い換えれば、演算器の出力が次段の論理回路の演算器だけでなく、２段下の論理回路の演算器にも接続可能である）点に、リコンフィギュラブル回路１２は新規性を有する。
【００３９】
なお、図２は、リコンフィギュラブル回路１２の構成の一部分を示したものであり、実際には８つの論理回路だけでなく、それ以上に多数の論理回路を備えている。
【００４０】
次に、このようなリコンフィギュラブル回路１２を用いて倍長演算を行う例を図３を参照して説明する。ここで、リコンフィギュラブル回路１２の各論理回路の演算器の演算ビット幅が16ビットであると仮定し、32ビット変数同士の加算A+Bを行う場合を説明する。この様子を示すのが図３である。いま、32ビット変数Ａの上位16ビットをAH、下位16ビットをAL、32ビット変数Ｂの下位16ビットをBL、上位16ビットをBHとしたとき、A+Bの演算は、下位ビット同士の加算AL+BLと、上位ビット同士の加算AH+BHとに分けて行われる。
【００４１】
まず、同図の論理回路Ｌ１１中の演算器ａ１からALが遅延出力データとして出力され、ＤＦＦ（ｄ１２）を介して論理回路Ｌ１２の選択器（ＭＵＸ（ｍ２））でこのデータが選択されて出力される。これにより、論理回路Ｌ１１の出力は、あたかも論理回路Ｌ１２の出力であるかのように利用することができる。同様に論理回路Ｌ２１の出力も、あたかも論理回路Ｌ２２の出力であるかのように利用できる。そして、論理回路Ｌ１３中の演算器ａ３（演算器（+L））は、論理回路Ｌ１１の出力と、論理回路Ｌ２１の出力を入力して処理することで、ALとBLの和を処理することができる。更に同様にして、論理回路Ｌ１４の演算器ａ６（演算器（+H））は、論理回路Ｌ１２の出力と論理回路Ｌ２２の出力を入力して処理することで、AHとBHの和を処理することができる。
【００４２】
なお、図示していないが、演算器（+L）で計算された加算におけるキャリーは、次段の演算器（+H）に入力されることで、倍長の加算処理が正しく実行される。また、リコンフィギュラブル回路１２は、図２及び図３では図示省略しているが、符号拡張を行うための演算回路を備えていても良い。この符号拡張については、図１０、図１２などの実施例を用いて後で詳しく説明する。
【００４３】
このように、リコンフィギュラブル回路１２では、選択器における選択を切り替えることで、単精度と倍精度の両方の演算が実現できる。
【００４４】
＜データフローグラフ生成部３２が行う処理＞
データフローグラフ生成部３２は、プログラムを解析して、ＤＦＧを生成する。このデータフローグラフ生成部３２は、Ｃ言語等で記述されたプログラム（例えば、図４(a) のプログラム）から演算ビット数を判定する処理（ステップＳ１００、図４参照）を行う。次に、ステップＳ１００で判定された演算ビット数に基づいてＤＦＧを生成する処理（ステップＳ２００）を行う。ステップＳ１００の処理は図５を参照して、ステップＳ２００の処理は図６を参照して説明する。以下では、まず、手順の概略を簡単に説明し、その後、実際の演算例を用いて詳しく説明する。
【００４５】
（演算ビット数判定処理：ステップＳ１００）
図５は、演算ビット数を判定する処理（ステップＳ１００）のフローチャートである。この処理では、プログラムから抽出した各演算において、演算の入出力のビット数から演算のビット数を決定する。
【００４６】
ステップＳ１０１では、プログラムから抽出した演算数を変数ｍに格納する。続くステップＳ１０２では、iに１を代入する。ステップＳ１０３では、i番目の演算の入力データのうち最大のビット数ａを取得する。ステップＳ１０４では、i番目の演算の出力データのうち最大のビット数ｂを取得する。
【００４７】
ステップＳ１０５では、ａとｂの大小比較を行い、aがbよりも大きければステップＳ１０６へ進む。aがbよりも大きくない場合、ステップＳ１０７へ進む。ステップＳ１０６では、演算ビット数をａとした場合とｂとした場合の演算結果を比較する。そして、演算結果が変わらなければステップＳ１０８へ進む。演算結果が異なるときステップＳ１０７へ進む。
【００４８】
ステップＳ１０８へ進んだ場合、演算のビット数をｂとする。ステップＳ１０７へ進んだ場合、演算のビット数をａとする。そして、ステップＳ１０９では、iとmを比較し、これらが一致すれば終了する。一致しない場合は、ステップＳ１１０へ進む。ステップＳ１１０へ進んだ場合、iに１を加えたのち、ステップＳ１０３へ戻る。
【００４９】
以上の処理結果から、入出力ビット数と、演算ビット数が確定した中間ＤＦＧ（例えば、図４（ｂ）に示すようなもの）を生成できる。
【００５０】
（ＤＦＧ生成処理：ステップＳ２００）
図６は、ＤＦＧを生成する処理（ステップＳ２００）のフローチャートである。ここでは、図５の演算ビット数判定処理の結果に基づいてＤＦＧを生成する。
【００５１】
ステップＳ２０１では、演算数をｍに格納する。続くステップＳ２０２では、iに１を代入する。ステップＳ２０３では、ａにi番目の演算の演算ビット数を代入する。この場合の「演算ビット数」とは、図５のステップＳ１０７又はＳ１０８で決定された演算ビット数のことである。
【００５２】
ステップＳ２０４では、ａとｒの大小比較を行う。ここで、ｒとはリコンフィギュラブル回路１２の1個のＡＬＵで処理可能なビット数であり、本実施形態では16ビットである。ａの方が大きければステップＳ２０５へ進み、そうでなければステップＳ２０６へ進む。
【００５３】
ステップＳ２０５では、生成すべきノードの数を判定する。一例として、上記のａがｒのｎ倍のとき、生成すべきノード数はｎ個であると判定する。このｎをｂとする。一方、ステップＳ２０６へ進んだ場合は、ｂを１とする。即ち、生成すべきノード数は１個であると判断する。
【００５４】
ステップＳ２０７では、上記ステップＳ２０５又はＳ２０６で判定したｂ個のノードを生成する。
【００５５】
ステップＳ３００では、入力変換処理を行う。この処理については、図７を用いて後で説明する。
【００５６】
ステップＳ４００では、出力変換処理を行う。この処理については、図８を用いて後で説明する。
【００５７】
ステップＳ２０８ではiとｍを比較し、一致すればステップＳ２１０へ進みＤＦＧを生成する。一致しなければステップＳ２０９へ進み、iに１を加えて、再びステップＳ２０３へ戻る。
【００５８】
（入力変換処理：ステップＳ３００）
図７を参照して、ステップＳ３００で行われる入力変換処理の手順を説明する。ここでは、ノード以外から入力データを演算ノードに対応するように変換する。
【００５９】
ステップＳ３０１では、m1に入力数を格納する。ここで「入力数」とは、演算の入力データの数のことである。ステップＳ３０２ではi1に１を代入する。
【００６０】
ステップＳ３０３では、i1番目の入力データの解析を行う。具体的には、入力データのビット数や、入力データがノードからの入力か否か、などを解析する。
【００６１】
入力データがノードからの入力であれば、ステップＳ３０４でyesと判定し、ステップＳ３１５へ進む。ノード以外からの入力であればステップＳ３０５へ進む。ステップＳ３０５からステップＳ３１４までが、このステップＳ３００の入力変換処理の主要な部分に相当する。
【００６２】
ステップＳ３０５では、入力データのビット数をa1に格納する。ステップＳ３０６では、入力データのビット数a1と、リコンフィギュラブル回路１２のＡＬＵの入力ビット数r1を比較する。本実施形態ではr1は１６である。a1の方が大きい場合、ステップＳ３０７へ進み、そうでない場合はステップＳ３０８へ進む。Ｓ３０７へ進んだ場合、入力データの分割を行い、分割された入力データの数をb1へ代入する。例えば、a1がr1の２倍であれば、入力データを２つに分割（上位データと下位データに分割）する。Ｓ３０８へ進んだ場合、入力データの分割は行わずに、b1に１を代入する。
【００６３】
ステップＳ３０９では、b1がs未満かどうかを判定する。sとは演算のノード数のことであり、図６のステップＳ２０７で生成されたノードの数である。b1がｓ未満の場合、ステップＳ３１０へ進み、そうでない場合ステップＳ３１４へ進む。
【００６４】
ステップＳ３１０では、入力が定数かどうかを判定し、定数の場合ステップＳ３１３へ進み、定数でない場合はステップＳ３１１へ進む。ステップＳ３１１では、入力データのビット拡張用ノードを生成する。ステップＳ３１２では、b1個に分割した入力データを対応するビット拡張用ノードの入力に割り当てる。ステップＳ３１３では、符号ビットを拡張して分割数をｓ個にする。
【００６５】
ステップＳ３１４では、分割した入力データの下位側のｓ個を対応する演算ノードの入力に割り当てる。
【００６６】
ステップＳ３１５では、i1とm1が一致するかどうかを判定し、一致する場合は終了して（図６の）ステップＳ４００へ進む。一致しない場合は、ステップＳ３１６でiに１が加算されてステップＳ３０３へ戻る。
【００６７】
（出力変換処理：ステップＳ４００）
図８を参照して、ステップＳ４００で行われる出力変換処理の手順を説明する。
【００６８】
ステップＳ４０１では、m2に出力数を格納する。ここで「出力数」とは、演算の出力データの数のことである。ステップＳ４０２ではi2に１を代入する。
【００６９】
ステップＳ４０３では、i1番目の出力データの解析を行う。具体的には、出力データのビット数や、出力データの出力先がノードか否か、などを解析する。
【００７０】
出力データがノードへの出力であれば、ステップＳ４０４でyesと判定し、ステップＳ４１３へ進む。ノード以外への出力であればステップＳ４０５へ進む。
【００７１】
ステップＳ４０５では、出力データのビット数を判定し、判定結果をa2に格納する。ステップＳ４０６では、出力データのビット数a2と、リコンフィギュラブル回路１２のＡＬＵの出力ビット数r2を比較する。本実施形態ではr2は１６である。a2の方が大きい場合、ステップＳ４０７へ進み、そうでない場合はステップＳ４０８へ進む。Ｓ４０７へ進んだ場合、出力データの分割を行い、分割された出力データの数をb2へ代入する。例えば、a2がr2の２倍であれば、出力データを２つに分割（上位データと下位データに分割）する。Ｓ４０８へ進んだ場合、出力データの分割は行わずに、b2に１を代入する。
【００７２】
ステップＳ４０９では、b2がｓより大きいかどうかを判定する。ｓとは演算のノード数のことであり、図６のステップＳ２０７で生成されたノードの数である。b2がｓより大きい場合、ステップＳ４１０へ進み、そうでない場合ステップＳ４１２へ進む。
【００７３】
ステップＳ４１０では、出力データのビット拡張用ノードを生成する。ステップＳ４１１では、b2個に分割した出力データを、対応するビット拡張用ノードの出力に割り当てる。ステップＳ４１２へ進んだ場合、分割した出力データを対応する演算ノードの出力に割り当てる。
【００７４】
ステップＳ４１３では、i2とm2が一致するかどうかを判定し、一致する場合は終了して（図６の）ステップＳ２０８へ進む。一致しない場合は、ステップＳ４１４でiに１が加算されてステップＳ４０３へ戻る。
【００７５】
（ＤＦＧ生成例１）
以下では、図４（ａ）のプログラムから図４（ｃ）のＤＦＧを生成する例について説明する。
【００７６】
このプログラムは、「x +=1」と、「*y -= x」の２つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。図５を参照して、ステップＳ１０１では、演算数は２であるから、ｍに２が代入される。１番目の演算「x +=1」（x = x +1 と同義）の入力データはｘと１であり、ｘは16ビット変数なのでａは16ビットとなる（Ｓ１０３）。また、出力データであるｘも16ビットなので、ｂも16ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、１番目の演算ビット数を16と判定する（Ｓ１０７）。
【００７７】
再びＳ１０３へ戻り、２番目の演算「*y -= x」（y = y - x と同義）の入力データはｙとｘであり、ｘが16ビットに対し、ｙが32ビットなのでaは32ビットとなる。また、出力データであるｙも32ビットなので、ｂも32ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、２番目の演算ビット数を３２と判定する（Ｓ１０７）。
【００７８】
以上の処理により、図４（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。なお、この中間ＤＦＧにおいては、１番目の演算ノードn01は16ビットの加算を行い、２番目の演算ノードn02は32ビットの減算を行うものである。
【００７９】
次に、Ｓ２００（図６）へ進む。演算数ｍは２であり（Ｓ２０１）、１番目の演算（上記中間ＤＦＧのノードn01の演算に対応）のビット数ａは16である（Ｓ２０３）。a=r=16であるから、b=1となり、１個の加算ノード（図４（ｃ）のノードn11）が生成される（Ｓ２０７）。
【００８０】
そして、Ｓ３００（図７）へ進む。１番目の演算の入力はｘと１であり（ノードn01への入力に対応）、m1は２である（Ｓ３０１）。このうちの１番目の入力データであるｘは16ビットなのでa1は16であり（Ｓ３０５）、r1と等しいのでb1は１となる（Ｓ３０８）。Ｓ２０７で生成されたノード数sとb1は等しいので、ｘがそのまま演算ノードn11の入力となる（Ｓ３１４）。そして、Ｓ３０３へ戻り、２番目の入力である「１」は、ビット数が２であり（符号ビット付）、b1=1となる（Ｓ３０８）。そして、１がそのまま演算ノードn11の入力となる（Ｓ３１４）。
【００８１】
そして、Ｓ４００（図８）へ進む。１番目の演算の出力は、図４（ｂ）のノードn01からの出力に対応するが、これは、図４（ｂ）の中間ＤＦＧのノードn02への出力となるから、Ｓ４０４ではＹｅｓと判定され、結局、実質的に何の処理も行われないままＳ４００の処理が完了する。
【００８２】
再び図６を参照して、この後、Ｓ２０８、Ｓ２０９を経て、再びＳ２０３へ進む。２番目の演算（上記中間ＤＦＧのノードn02の演算に対応）のビット数ａは32であり、a>rなので、Ｓ２０５へ進む。そして、Ｓ２０５、Ｓ２０７を経て２個の減算ノード（図４（ｃ）のノードn12、n13）が生成される。
【００８３】
そして、Ｓ３００（図７）へ進む。２番目の演算の入力はｙとノード（中間ＤＦＧのノードn01）からの入力の２つでり、m1は２である（Ｓ３０１）。１番目の入力データであるｙは32ビットなのでa1は３２であり（Ｓ３０５）、r1(=16)よりも大きいのでＳ３０７へ進む。そして、yは、上位データy(H)と、下位データy(L)の２つに分割される。続くＳ３０９では、b1=s==2だから、Ｓ３１４へ進み、y(L)をn12の入力として、y(H)をn13の入力としてそれぞれ割り当てる。その後、Ｓ３１５、Ｓ３１６を経て、Ｓ３０３で２番目の入力データが解析されるが、これは中間ＤＦＧのノードn01からの入力であるから、そのまま終了する。
【００８４】
そして、Ｓ４００（図８）へ進む。２番目の演算の出力は、図４（ｂ）のノードn02からの出力に対応し、出力データｙは32ビットであり、a2は３２となる（Ｓ４０５）。このa2はr2よりも大きく、Ｓ４０７で出力データがy(L)、y(H)の２つに分割される。b2=s==2なので、Ｓ４１２へ進み、２個に分割されたy(L)、y(H)のそれぞれがノードn12、n13の出力として割り当てられる。
【００８５】
そして、図４（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【００８６】
（ＤＦＧ生成例２）
以下では、図９（ａ）のプログラムから図９（ｃ）のＤＦＧを生成する例について説明する。
【００８７】
このプログラムは、「y = x + 1」の１つの演算を行うものであり、ｘはint型の32ビットの変数、ｙはshort型の16ビットの変数である。図５を参照して、演算数は１なのでｍに１が代入される（Ｓ１０１）。入力データはｘと１なのでａは32ビットとなる（Ｓ１０３）。出力データであるyは16ビットなので、ｂは16ビットとなる（Ｓ１０４）。ａ＞ｂなのでＳ１０６へ進む。
【００８８】
Ｓ１０６では、演算のビット数がa(=32)ビットの場合と、b(=16)ビットの場合で、「y = x + 1」の演算が同じ結果になるかどうか判定する。ここでは、出力ｙが16ビットであるから、16ビット演算した場合と、32ビット演算して16ビットに変換した結果とでは同じである。従って演算ビット数は16ビットで十分（32ビットも必要ない）と判断する（Ｓ１０８）。
【００８９】
以上の処理により、図９（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。即ち、int型の変数ｘと１（符号付の2ビット変数）がshort型の演算ノードへ入力され、これらの加算結果をshort型の変数yとして出力する演算を行うＤＦＧが生成される。
【００９０】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは16である（Ｓ２０３）。a=r=16であるから、b=1となり、１個の加算ノード（図９（ｃ）の演算ノードn21）が生成される（Ｓ２０７）。
【００９１】
そして、Ｓ３００（図７）へ進む。入力はｘと１であるので入力数m1は２である。i1番目のデータはｘであり、a1は32である（Ｓ３０５）。r1=16であるから、a1＞r1となるので、Ｓ３０６ではyesと判定されて、Ｓ３０７へ進み、入力データであるｘがx(H)とx(L)に分割される。b1=2であるのに対し演算ノード数s=1である（演算ノードｎ２１）から、b1>sなのでＳ３０９ではNoと判断されてＳ３１４へ進む。そして、Ｓ３１４では分割した入力データの下位側のs個（１個）、即ちx(L)を対応する演算ノードn21の入力に割り当てる。
【００９２】
次に2番目のデータ「１」のa1は２ビット（符号付変数と仮定）であるから、a1<r1なので、Ｓ３０６でNoと判断されるので、ステップＳ３０７でb1=1となる。b1=s1=1であるから、Ｓ３０９ではyesと判断される。入力は定数であるから、Ｓ３１０ではyesと判断されてＳ３１３へ進み、Ｓ３１３を経てＳ３１４において、「１」が演算ノードn21の入力として割り当てられる（Ｓ３１４）。
【００９３】
そして、Ｓ４００（図８）へ進む。演算の出力は、short型変数のｙであり、a2=16である（Ｓ４０５）。a2=r2=16だから、b2=s==1となり、１個の出力データが対応する演算ノードn21の出力に割り当てられる。
【００９４】
そして、図６へ戻り、図９（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【００９５】
（ＤＦＧ生成例３）
以下では、図１０（ａ）のプログラムから図１０（ｃ）のＤＦＧを生成する例を説明する。
【００９６】
このプログラムは、「y = x + 0x000fffff」という１つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。また、0x000fffffは32ビットである。図５を参照して、入力データはｘと0x000fffffなのでａは32ビットとなる（Ｓ１０３）。出力データであるyは32ビットなので、ｂは32ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、演算ビット数は32となる。
【００９７】
以上の処理により、図１０（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。
【００９８】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは32である（Ｓ２０３）。r=16であるから、a>rであり、Ｓ２０５を経て、２個の加算ノード（図１０（ｃ）のノードn32、及びノードn33）が生成される（Ｓ２０７）。
【００９９】
そして、Ｓ３００（図７）へ進む。入力はｘと0x000fffffであるので、入力数m1は２である。１番目のデータはｘであり、a1は16である（Ｓ３０５）から、b1=1となる。一方、Ｓ２０７で生成されたノード数sは２だから、b<sなのでＳ３１０へ進む。ｘは定数ではないからＳ３１１へ進む。
【０１００】
Ｓ３１１では、入力データのビット拡張用ノード（図１０（ｃ）のmovノードn31）が生成される。即ち、入力データｘは16ビットであるので、32ビットの下位の演算ノード「+L」（ノードn32）のみの入力にしか対応しておらず、上位の演算ノード「+H」（ノードn33）に入力するｘの上位16ビットのデータを生成する必要がある。movノードは、この上位16ビットの入力データを生成するための処理を行うものである。そして、ｘがこのmovノードへの入力に割り当てられる（Ｓ３１２）。
【０１０１】
次に２番目のデータ「0x000fffff」のa1は32ビットであるから、このデータは下位16ビットの「0xffff」と上位16ビットの「0x000f」に分割され（Ｓ３０７）b1=2となる。Ｓ３０９では、b1=s=2であるから、Ｓ３０９からＳ３１４へ進み、分割した入力データ「0xffff」「0x000f」のそれぞれを演算ノードn32、n33の入力へ割り当てる。
【０１０２】
そして、Ｓ４００（図８）へ進む。演算の出力は、int型変数のｙであり、a2=32である（Ｓ４０５）。r2=16であるから、a2>r2となるので、Ｓ４０７へ進み、出力データがy(L)とy(H)の２つに分割される。b2=s=2であるから、Ｓ４０９からＳ４１２へ進み、分割された出力データy(L)、y(H)のそれぞれが演算ノードn32、n33の出力に割り当てられる。
【０１０３】
そして、図６へ戻り、図１０（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【０１０４】
（ＤＦＧ生成例４）
以下では、図１１（ａ）のプログラムから図１１（ｃ）のＤＦＧを生成する例を説明する。
【０１０５】
このプログラムは、「y = x + 1」という１つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。図５を参照して、入力データはｘと1なのでａは16ビットとなる（Ｓ１０３）。出力データであるyは32ビットなので、ｂは32ビットとなる（Ｓ１０４）。a < bなのでＳ１０７へ進み、演算ビット数は16となる。
【０１０６】
以上の処理により、図１１（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。
【０１０７】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは16である（Ｓ２０３）。r=16であるから、a = rであり、Ｓ２０６でb=1となるので、１個の加算ノード（図１１（ｃ）の加算ノードn41）が生成される（Ｓ２０７）。
【０１０８】
そして、Ｓ３００（図７）へ進む。入力はｘと１であるので、入力数m1は２である。i1番目のデータはｘであり、a1は16である（Ｓ３０５）から、a1=r1=16なので、b1=1となる。Ｓ２０７で生成されたノード数sは１だから、b=sなのでＳ３１４へ進む。そして、ｘが加算ノードn41への入力に割り当てられる（Ｓ３１４）。
【０１０９】
次に2番目のデータ「１」のa1は２ビット（符号付変数であると仮定）であるから、b1=1となる。そして、同様にして、「１」が加算ノードn41の他の入力となる（Ｓ３１４）。
【０１１０】
そして、Ｓ４００（図８）へ進む。演算の出力はint型変数のｙであり、a2=32である（Ｓ４０５）。a2>r2であるから、Ｓ４０７へ進む。Ｓ４０７では、出力データが２つ（y(L)とy(H)）に分割される。そして、b2=2に対しs=1であるからＳ４１０へ進む。
【０１１１】
出力データｙは32ビットであるため、16ビットの加算ノードからは出力データｙの上位16ビットであるy(H)を出力できない。そこで、加算ノードの結果をビット拡張し、出力データの上位16ビットのy(H)を生成し出力する必要がある。そこで、Ｓ４１０では、出力データのビット拡張用mov(mov L, mov H)ノードn42が生成される。そして、生成したビット拡張用ノード(mov L, mov H)に出力データy(L)とy(H)がそれぞれ割り当てられる（Ｓ４１１）。
【０１１２】
そして、図６へ戻り、図１１（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【０１１３】
（ＤＦＧの割り当て例）
上記の方法で生成したＤＦＧをリコンフィギュラブル回路１２に実際にマッピングした場合の様子を説明する。
【０１１４】
図４（ｃ）のＤＦＧをリコンフィギュラブル回路１２に割り当てた場合、図１２のようになる。
【０１１５】
上記で示した処理を実現することにより、多倍長演算のような処理が可能なリコンフィギュラブル回路に対応したＤＦＧを自動的に生成することができる。また、これにより実行プログラムから実行設定データの生成までの時間が短縮できるため、リコンフィギュラブル回路に所望の処理を実行させるための開発期間を短縮させることができる。
【０１１６】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【０１１７】
例示した図では、多倍長演算のノードを縦に並べた構成になっているが、これはリコンフィギュラブル回路の処理に依存するものであり、この構成に限定されるものではない。例えば、横に並ぶ等、様々な構成がありえる。
【０１１８】
また、上記では、２倍長演算を例に説明したが、本発明の概念は３以上の多倍長演算を行うためのＤＦＧの生成にも適用できる。例えば、図１３に示すような３倍長演算を行うＤＦＧの生成にも適用できる。
【０１１９】
なお、上記ではステップＳ１００により中間ＤＦＧを生成するものとして説明しているが、実際に中間ＤＦＧを生成することなく、演算ビット数、入出力ビット数の情報を、続くステップＳ２００で利用できるよう格納しておくようにしても良い。
【図面の簡単な説明】
【０１２０】
【図１】実施の形態に係る処理装置１０の構成図である。
【図２】リコンフィギュラブル回路１２の構成を示す図である。
【図３】リコンフィギュラブル回路１２を用いて倍長演算を行う例を説明する図である。
【図４】ＣソースプログラムからＤＦＧを生成する第１の例である。
【図５】演算ビット数を判定する処理（ステップＳ１００）のフローチャートである。
【図６】ＤＦＧを生成する処理（ステップＳ２００）のフローチャートである。
【図７】入力変換処理（ステップＳ３００）のフローチャートである。
【図８】出力変換処理（ステップＳ４００）のフローチャートである。
【図９】ＣソースプログラムからＤＦＧを生成する第２の例を示す図である。
【図１０】ＣソースプログラムからＤＦＧを生成する第３の例を示す図である。
【図１１】ＣソースプログラムからＤＦＧを生成する第４の例を示す図である。
【図１２】図４（ｃ）のＤＦＧをリコンフィギュラブル回路１２に割り当てた後の状態である。
【図１３】３倍長演算を行う場合のＤＦＧを示す図である。
【図１４】従来の方法で生成したＤＦＧを説明する図である。
【符号の説明】
【０１２１】
１０ 処理装置
１２ リコンフィギュラブル回路
１４ 設定部
１８ 制御部
３０ コンパイル部
３２ 設定データグラフ処理部
【技術分野】
【０００１】
この発明は、機能の変更が可能な論理回路の複数の集合体と、それぞれの集合体の間に設けられて集合体間の論理回路の接続を選択的に確立可能な接続部を備えるリコンフィギュラブル回路に提供するデータフローグラフを生成するデータフローグラフ生成装置に関する。特に多倍長演算が可能なリコンフィギュラブル回路に対応したデータフローグラフの自動生成に関する。
【背景技術】
【０００２】
近年、ＡＬＵ(Arithmetic Logic Unit)と呼ばれる基本演算機能を複数持つ多機能素子を多段に並べたＡＬＵアレイを用いたリコンフィギュラブルプロセッサの検討が行われている（例えば、特許文献１）。リコンフィギュラブルプロセッサでは、設定データが設定されることにより、ＡＬＵ回路の演算機能構成と接続部が制御され、全体として所期の演算処理回路を実現することができる。設定データは、一般にＣ言語などの高級プログラム言語で記述されたソースプログラムからＤＦＧ（Data Flow Graph、データフローグラフ）と呼ばれるデータフローを作成し、その情報をもとに作成される。ＤＦＧは、入力される変数や定数の演算の流れを、段階的にグラフ構造で表現したものである。
【特許文献１】特開２００５−２７５６９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
リコンフィギュラブルプロセッサは、ＡＬＵの演算ビット幅を超える演算を複数のＡＬＵを用いて処理するような、多倍長演算も可能なものもある。多倍長演算とは、例えば、演算ビット幅が16ビットのＡＬＵを備えたプロセッサにより、32ビットの演算を行うことをいう。しかし、従来の方法により生成されるＤＦＧ生成は、上記のような多倍長演算対応のプロセッサでの演算に対応しない。
【０００４】
例えば、図１６（ａ）のプログラムで記述される演算を行うＤＦＧの生成を考える。このプログラムは、short型（16ビット）の変数ｘと、int型（32ビット）の変数ｙを入力変数とし、int型の変数yを出力変数とした、関数func0(x,*y)の行う演算を示したものである。この関数func0(x,*y)では、まず「x+=1」において、入力変数ｘに１を加算し、加算した結果をｘに置き換える。そして次の、「*y=-x」では、入力変数であるｙからｘを減算し、減算結果をｙに置き換えて、出力する。このような関数func0(x,*y)の演算を行うＤＦＧを従来の方法により生成すると、図１６（ｂ）のようになる。演算ノードn01では、ｘと１の加算を行い、その結果（n01outとする）を演算ノードn0へ出力する。演算ノードn02では、yからn01outを減算し、その結果を出力する。このＤＦＧにより正しい演算を行うには、演算子が32ビットのＡＬＵを備えたプロセッサを用いる必要があり、ＡＬＵの演算ビット幅が32ビット未満の多倍長演算対応のプロセッサでの演算に対応しない。
【０００５】
そこで、本発明は上記の事情に鑑み、リコンフィギュラブル回路を用いて多倍長演算を行うためのデータフローグラフを自動的に生成する装置、或いは方法を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のある態様は、演算機能の変更が可能なリコンフィギュラブル回路の動作設定に必要なデータフローグラフであって、前記論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成装置に関する。この態様のデータフローグラフ生成装置は、前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、演算に対応するノードを生成するノード生成部を備える。前記ノード生成部は、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【０００７】
例えば、演算ビット数決定手段にて決定された演算ビット数が32ビットであって、リコンフィギュラブル回路の論理回路により演算可能な演算ビット数が16ビットであるような場合、１つの演算を２つの演算ノードに分けて行うようなＤＦＧを生成する。
【０００８】
係るＤＦＧ生成装置によれば、演算のビット数がリコンフィギュラブル回路の論理回路により演算可能なビット数よりも大きいときは演算を複数の演算ノードに分けて行うＤＦＧを生成する。これにより、リコンフィギュラブル回路による倍長演算が可能となる。
【０００９】
上記のデータフローグラフ生成装置は、動作を示した記述（例えば、Ｃ言語等で記述されたプログラム）に基づいてデータフローグラフを生成する。或いは、上記データフローグラフ生成装置は、既に生成されたデータフローグラフを、リコンフィギュラブル回路の演算ビット数に合うように再構成するものであっても良い。例えば、32ビット対応の論理回路を有するリコンフィギュラブル回路を想定して生成した32ビット演算を行うＤＦＧを、16ビット対応の論理回路を有するリコンフィギュラブル回路での演算用に再構成するものであっても良い。
【００１０】
好ましくは、前記演算ビット数決定部は、演算の入力データのビット数に基づいて前記演算ビット数を決定する。また、前記入力データのビット数が前記出力データのビット数よりも大きいとき、前記演算ビット数を出力データのビット数と等しく設定した場合と、前記出力データのビット数よりも大きく設定した場合の演算結果を比較し、比較した演算結果が等しいとき、出力データのビット数を演算ビット数と決定しても良い。
【００１１】
演算の入力データのビット数と出力データのビット数から、演算に必要最小限な演算ビット数を決定する。これにより、ＤＦＧの小型化が図れ、その結果、演算に使用するリコンフィギュラブル回路を少なくすることができる。
【００１２】
好ましくは、前記ノード生成部は、１つの演算に対して複数の演算ノードが生成されたとき、前記演算の入力、及び/又は出力データを、それぞれの演算ノードの入力、及び/又は出力に対応させるための変換を行う入出力変換部を備える。
【００１３】
例えば、前記入出力変換部は、入力データのビット数が前記論理回路の入力ビット数よりも大きいとき、前記入力データを複数の入力データに分割して、それぞれの演算ノードの入力に対応させるようなデータフローグラフを生成する。
【００１４】
或いは、前記入出力変換部は、出力データのビット数が前記論理回路の出力ビット数よりも大きいとき、前記出力データを複数の出力データに分割して、それぞれの演算ノードの出力に対応させるようなデータフローグラフを生成する。
【００１５】
また、前記ノード生成部は、演算の入力データのビット数が前記演算のノードに対応した１以上の前記論理回路で入力可能な総ビット数よりも小さいとき、前記入力データのビット拡張用ノードを生成し、前記入力データを生成したビット拡張用ノードの入力に対応させるようなデータフローグラフを生成してもよい。
【００１６】
前記ノード生成部は、演算の出力データのビット数が前記演算のノードに対応した１以上の前記論理回路で出力可能な総ビット数よりも大きいとき、前記出力データの出力用ノードを生成してもよい。
【００１７】
本発明の設定データ生成装置は、上記のいずれかのデータフローグラフ生成装置と、データフローグラフ生成装置で生成されたデータフローグラフをリコンフィギュラブル回路に供給するための設定データに変換するデータ変換部を備える。
【００１８】
本発明の処理装置は、設定データに従って動作するリコンフィギュラブル回路と、上記設定データ生成装置で生成された設定データを前記リコンフィギュラブル回路に順次供給する制御部を備えることを特徴とする。
【００１９】
本発明のデータフローグラフ生成方法は、演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成方法において、前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定ステップと、演算に対応するノードを生成するノード生成ステップによりデータフローグラフを生成し、前記ノード生成ステップでは、前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する。
【発明の効果】
【００２０】
この発明によれば、リコンフィギュラブル回路を用いて多倍長演算を行うためのデータフローグラフを自動的に生成することができる。
【発明を実施するための最良の形態】
【００２１】
図１は、実施の形態に係る処理装置１０、設定データ生成装置３０の構成を示す図である。
【００２２】
＜処理装置１０の構成＞
処理装置１０は、演算機能を有し、回路構成が再構成可能である。この処理装置１０は、１チップとして構成される集積回路からなり、リコンフィギュラブル回路１２、設定部１４、制御部１８、入力回路２０、出力回路２２を備える。
【００２３】
リコンフィギュラブル回路１２は、機能の変更が可能なＡＬＵによる論理回路の集合体を複数備えた構造を有する。リコンフィギュラブル回路１２は、後述する設定部１４から供給される設定データに従って動作する演算回路として機能する。即ち、入力回路２０からの入力データに対して、設定データに従った演算を行い、演算結果を出力回路２０へ出力する。。このリコンフィギュラブル回路１２の構成については後で詳しく説明する。
【００２４】
設定部１４は、リコンフィギュラブル回路１２に所期の演算回路を構成するための設定データを供給する。設定部１４から設定データを供給することにより、リコンフィギュラブル回路１２は所期の演算回路として再構成される。この設定データは後述する設定データ生成装置２０で生成される。
【００２５】
制御部１８は、処理装置１０の各部、即ち、リコンフィギュラブル回路１２、設定部１４、入力回路２０、出力回路２２を制御する。また、クロック機能を有し、クロック信号を、リコンフィギュラブル回路１２、入力回路２０、出力回路２２に供給する。
【００２６】
入力回路２０は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成される。入力回路２０は、外部から入力されたデータを、リコンフィギュラブル回路１２での演算タイミングに同期するように、リコンフィギュラブル回路１２へ入力させる。
【００２７】
出力回路２２は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２から出力されるデータを所期のタイミングで外部に出力する。
【００２８】
＜設定データ生成装置３０の構成＞
設定データ生成装置３０は、データフローグラフ生成部３２、設定データ生成部３４、記憶部３６を備える。
【００２９】
記憶部３６には、プログラム３８、データフローグラフ４０、設定データ４２などが記憶されている。記憶部３６に記憶されるプログラムは、リコンフィギュラブル回路１２で実現されるべき処理の動作をＣ言語などの高級言語で記述したものである。
【００３０】
データフローグラフ生成部３２は、このプログラムを解析し、リコンフィギュラブル回路を動作設定するためのデータフローグラフ４０に変換して記憶部３６に格納する。ＤＦＧとは、回路における演算間の実行順序の依存関係を表現したものであり、入力変数および定数の演算の流れをグラフ構造で示したものである。一般に、ＤＦＧは、上から下に向かって演算が進むように作成される。
【００３１】
設定データ生成部３４は、データフローグラフ生成部３２で生成されたデータフローグラフ４０から設定データ４２を生成する。設定データ４２は、データフローグラフ４０をリコンフィギュラブル回路１２にマッピングするためのデータであり、リコンフィギュラブル回路１２における論理回路の機能や論理回路間の接続関係を定める。設定データ生成部３４により生成された設定データ４０は、設定部１４を介してリコンフィギュラブル回路１２へ供給される。
【００３２】
なお、設定データを複数のリコンフィギュラブル回路に分けて供給したり、１つのリコンフィギュラブル回路に複数回に分けて供給したりする場合等においては、１つのプログラムから複数の設定データを生成しても良い。
【００３３】
＜リコンフィギュラブル回路１２の構成＞
図２は、リコンフィギュラブル回路１２の構成の一部を示すものである。
【００３４】
図２のように、リコンフィギュラブル回路１２では、演算器（ＡＬＵ）、ＭＵＸ、及び２つのＤＦＦからなる論理回路（同図ではＬ１１、Ｌ１２、Ｌ２１、…、Ｌ４２として示している）がアレイ状に配列される。各論理回路の演算器は、演算機能を選択的に実行可能な構成となっている。各演算器には、設定部１４から演算器の機能を制御する命令セットが設定される。演算器には予め論理和、論理積、ビットシフトなどを行う演算回路が実装されており、命令セットによってどの演算を行うかが選択される。
【００３５】
上記の命令セット、接続データセットからなる構成情報は、一般にＣ言語などの高品位言語で記述されたプログラムから作成される。Ｃ言語のプログラムは、データフローグラフ生成部３２によってＤＦＧへ変換される。そして、設定データ生成部３４は、このＤＦＧから演算器の命令と演算器間の接続を決定し、これらの情報からリコンフィギュラブル回路１２への構成情報に変換する。
【００３６】
論理回路間の接続には一定の制限が課されている。即ち、上段の論理回路から下段算ユニットへの接続は、同じ列か、隣接する左右の列へのものに制限されており、論理回路段の間で物理的に近接して配列された論理回路同士を接続可能とするように構成される。例えば、論理回路Ｌ２１からの出力は、Ｌ１２、Ｌ２２、及びＬ３２の３つの論理回路にのみ接続されるような配線構造となっている。
【００３７】
各論理回路において、演算器（ＡＬＵ）での演算結果は、ＭＵＸ（選択器）へ出力される。また、各演算器の演算結果は、ＤＦＦ（Ｄ型フリップフロップ）を介して、同列次段の論理回路内のＭＵＸへも出力される（遅延データ出力）。例えば、論理回路Ｌ１１の演算器による演算結果は、Ｌ１１のＭＵＸだけでなく、Ｌ１１のＤＦＦ２を介してＬ１２のＭＵＸへも出力される。ＭＵＸは、演算器からの出力と、前段の演算器からの出力（遅延データ入力）を選択して出力する。例えば、論理回路Ｌ１２のＭＵＸは、Ｌ１２の演算器からの出力と、Ｌ１１の演算器からの出力を選択して出力する。
【００３８】
なお、上記説明したリコンフィギュラブル回路１２は、本願出願人が開発した接続制限付きのリコンフィギュラブル回路（特開２００５−１８２６５４号公報の図９参照）を改良したものである。リコンフィギュラブル回路１２は、各論理回路からの出力が左下段、下段、右下段の３つの論理回路のみに接続配線される構成である点については、上記公報に記載のリコンフィギュラブル回路と共通している。しかし、演算器からの出力と、前段の演算器からの出力（遅延データ入力）を選択して出力するＭＵＸを備える点（言い換えれば、演算器の出力が次段の論理回路の演算器だけでなく、２段下の論理回路の演算器にも接続可能である）点に、リコンフィギュラブル回路１２は新規性を有する。
【００３９】
なお、図２は、リコンフィギュラブル回路１２の構成の一部分を示したものであり、実際には８つの論理回路だけでなく、それ以上に多数の論理回路を備えている。
【００４０】
次に、このようなリコンフィギュラブル回路１２を用いて倍長演算を行う例を図３を参照して説明する。ここで、リコンフィギュラブル回路１２の各論理回路の演算器の演算ビット幅が16ビットであると仮定し、32ビット変数同士の加算A+Bを行う場合を説明する。この様子を示すのが図３である。いま、32ビット変数Ａの上位16ビットをAH、下位16ビットをAL、32ビット変数Ｂの下位16ビットをBL、上位16ビットをBHとしたとき、A+Bの演算は、下位ビット同士の加算AL+BLと、上位ビット同士の加算AH+BHとに分けて行われる。
【００４１】
まず、同図の論理回路Ｌ１１中の演算器ａ１からALが遅延出力データとして出力され、ＤＦＦ（ｄ１２）を介して論理回路Ｌ１２の選択器（ＭＵＸ（ｍ２））でこのデータが選択されて出力される。これにより、論理回路Ｌ１１の出力は、あたかも論理回路Ｌ１２の出力であるかのように利用することができる。同様に論理回路Ｌ２１の出力も、あたかも論理回路Ｌ２２の出力であるかのように利用できる。そして、論理回路Ｌ１３中の演算器ａ３（演算器（+L））は、論理回路Ｌ１１の出力と、論理回路Ｌ２１の出力を入力して処理することで、ALとBLの和を処理することができる。更に同様にして、論理回路Ｌ１４の演算器ａ６（演算器（+H））は、論理回路Ｌ１２の出力と論理回路Ｌ２２の出力を入力して処理することで、AHとBHの和を処理することができる。
【００４２】
なお、図示していないが、演算器（+L）で計算された加算におけるキャリーは、次段の演算器（+H）に入力されることで、倍長の加算処理が正しく実行される。また、リコンフィギュラブル回路１２は、図２及び図３では図示省略しているが、符号拡張を行うための演算回路を備えていても良い。この符号拡張については、図１０、図１２などの実施例を用いて後で詳しく説明する。
【００４３】
このように、リコンフィギュラブル回路１２では、選択器における選択を切り替えることで、単精度と倍精度の両方の演算が実現できる。
【００４４】
＜データフローグラフ生成部３２が行う処理＞
データフローグラフ生成部３２は、プログラムを解析して、ＤＦＧを生成する。このデータフローグラフ生成部３２は、Ｃ言語等で記述されたプログラム（例えば、図４(a) のプログラム）から演算ビット数を判定する処理（ステップＳ１００、図４参照）を行う。次に、ステップＳ１００で判定された演算ビット数に基づいてＤＦＧを生成する処理（ステップＳ２００）を行う。ステップＳ１００の処理は図５を参照して、ステップＳ２００の処理は図６を参照して説明する。以下では、まず、手順の概略を簡単に説明し、その後、実際の演算例を用いて詳しく説明する。
【００４５】
（演算ビット数判定処理：ステップＳ１００）
図５は、演算ビット数を判定する処理（ステップＳ１００）のフローチャートである。この処理では、プログラムから抽出した各演算において、演算の入出力のビット数から演算のビット数を決定する。
【００４６】
ステップＳ１０１では、プログラムから抽出した演算数を変数ｍに格納する。続くステップＳ１０２では、iに１を代入する。ステップＳ１０３では、i番目の演算の入力データのうち最大のビット数ａを取得する。ステップＳ１０４では、i番目の演算の出力データのうち最大のビット数ｂを取得する。
【００４７】
ステップＳ１０５では、ａとｂの大小比較を行い、aがbよりも大きければステップＳ１０６へ進む。aがbよりも大きくない場合、ステップＳ１０７へ進む。ステップＳ１０６では、演算ビット数をａとした場合とｂとした場合の演算結果を比較する。そして、演算結果が変わらなければステップＳ１０８へ進む。演算結果が異なるときステップＳ１０７へ進む。
【００４８】
ステップＳ１０８へ進んだ場合、演算のビット数をｂとする。ステップＳ１０７へ進んだ場合、演算のビット数をａとする。そして、ステップＳ１０９では、iとmを比較し、これらが一致すれば終了する。一致しない場合は、ステップＳ１１０へ進む。ステップＳ１１０へ進んだ場合、iに１を加えたのち、ステップＳ１０３へ戻る。
【００４９】
以上の処理結果から、入出力ビット数と、演算ビット数が確定した中間ＤＦＧ（例えば、図４（ｂ）に示すようなもの）を生成できる。
【００５０】
（ＤＦＧ生成処理：ステップＳ２００）
図６は、ＤＦＧを生成する処理（ステップＳ２００）のフローチャートである。ここでは、図５の演算ビット数判定処理の結果に基づいてＤＦＧを生成する。
【００５１】
ステップＳ２０１では、演算数をｍに格納する。続くステップＳ２０２では、iに１を代入する。ステップＳ２０３では、ａにi番目の演算の演算ビット数を代入する。この場合の「演算ビット数」とは、図５のステップＳ１０７又はＳ１０８で決定された演算ビット数のことである。
【００５２】
ステップＳ２０４では、ａとｒの大小比較を行う。ここで、ｒとはリコンフィギュラブル回路１２の1個のＡＬＵで処理可能なビット数であり、本実施形態では16ビットである。ａの方が大きければステップＳ２０５へ進み、そうでなければステップＳ２０６へ進む。
【００５３】
ステップＳ２０５では、生成すべきノードの数を判定する。一例として、上記のａがｒのｎ倍のとき、生成すべきノード数はｎ個であると判定する。このｎをｂとする。一方、ステップＳ２０６へ進んだ場合は、ｂを１とする。即ち、生成すべきノード数は１個であると判断する。
【００５４】
ステップＳ２０７では、上記ステップＳ２０５又はＳ２０６で判定したｂ個のノードを生成する。
【００５５】
ステップＳ３００では、入力変換処理を行う。この処理については、図７を用いて後で説明する。
【００５６】
ステップＳ４００では、出力変換処理を行う。この処理については、図８を用いて後で説明する。
【００５７】
ステップＳ２０８ではiとｍを比較し、一致すればステップＳ２１０へ進みＤＦＧを生成する。一致しなければステップＳ２０９へ進み、iに１を加えて、再びステップＳ２０３へ戻る。
【００５８】
（入力変換処理：ステップＳ３００）
図７を参照して、ステップＳ３００で行われる入力変換処理の手順を説明する。ここでは、ノード以外から入力データを演算ノードに対応するように変換する。
【００５９】
ステップＳ３０１では、m1に入力数を格納する。ここで「入力数」とは、演算の入力データの数のことである。ステップＳ３０２ではi1に１を代入する。
【００６０】
ステップＳ３０３では、i1番目の入力データの解析を行う。具体的には、入力データのビット数や、入力データがノードからの入力か否か、などを解析する。
【００６１】
入力データがノードからの入力であれば、ステップＳ３０４でyesと判定し、ステップＳ３１５へ進む。ノード以外からの入力であればステップＳ３０５へ進む。ステップＳ３０５からステップＳ３１４までが、このステップＳ３００の入力変換処理の主要な部分に相当する。
【００６２】
ステップＳ３０５では、入力データのビット数をa1に格納する。ステップＳ３０６では、入力データのビット数a1と、リコンフィギュラブル回路１２のＡＬＵの入力ビット数r1を比較する。本実施形態ではr1は１６である。a1の方が大きい場合、ステップＳ３０７へ進み、そうでない場合はステップＳ３０８へ進む。Ｓ３０７へ進んだ場合、入力データの分割を行い、分割された入力データの数をb1へ代入する。例えば、a1がr1の２倍であれば、入力データを２つに分割（上位データと下位データに分割）する。Ｓ３０８へ進んだ場合、入力データの分割は行わずに、b1に１を代入する。
【００６３】
ステップＳ３０９では、b1がs未満かどうかを判定する。sとは演算のノード数のことであり、図６のステップＳ２０７で生成されたノードの数である。b1がｓ未満の場合、ステップＳ３１０へ進み、そうでない場合ステップＳ３１４へ進む。
【００６４】
ステップＳ３１０では、入力が定数かどうかを判定し、定数の場合ステップＳ３１３へ進み、定数でない場合はステップＳ３１１へ進む。ステップＳ３１１では、入力データのビット拡張用ノードを生成する。ステップＳ３１２では、b1個に分割した入力データを対応するビット拡張用ノードの入力に割り当てる。ステップＳ３１３では、符号ビットを拡張して分割数をｓ個にする。
【００６５】
ステップＳ３１４では、分割した入力データの下位側のｓ個を対応する演算ノードの入力に割り当てる。
【００６６】
ステップＳ３１５では、i1とm1が一致するかどうかを判定し、一致する場合は終了して（図６の）ステップＳ４００へ進む。一致しない場合は、ステップＳ３１６でiに１が加算されてステップＳ３０３へ戻る。
【００６７】
（出力変換処理：ステップＳ４００）
図８を参照して、ステップＳ４００で行われる出力変換処理の手順を説明する。
【００６８】
ステップＳ４０１では、m2に出力数を格納する。ここで「出力数」とは、演算の出力データの数のことである。ステップＳ４０２ではi2に１を代入する。
【００６９】
ステップＳ４０３では、i1番目の出力データの解析を行う。具体的には、出力データのビット数や、出力データの出力先がノードか否か、などを解析する。
【００７０】
出力データがノードへの出力であれば、ステップＳ４０４でyesと判定し、ステップＳ４１３へ進む。ノード以外への出力であればステップＳ４０５へ進む。
【００７１】
ステップＳ４０５では、出力データのビット数を判定し、判定結果をa2に格納する。ステップＳ４０６では、出力データのビット数a2と、リコンフィギュラブル回路１２のＡＬＵの出力ビット数r2を比較する。本実施形態ではr2は１６である。a2の方が大きい場合、ステップＳ４０７へ進み、そうでない場合はステップＳ４０８へ進む。Ｓ４０７へ進んだ場合、出力データの分割を行い、分割された出力データの数をb2へ代入する。例えば、a2がr2の２倍であれば、出力データを２つに分割（上位データと下位データに分割）する。Ｓ４０８へ進んだ場合、出力データの分割は行わずに、b2に１を代入する。
【００７２】
ステップＳ４０９では、b2がｓより大きいかどうかを判定する。ｓとは演算のノード数のことであり、図６のステップＳ２０７で生成されたノードの数である。b2がｓより大きい場合、ステップＳ４１０へ進み、そうでない場合ステップＳ４１２へ進む。
【００７３】
ステップＳ４１０では、出力データのビット拡張用ノードを生成する。ステップＳ４１１では、b2個に分割した出力データを、対応するビット拡張用ノードの出力に割り当てる。ステップＳ４１２へ進んだ場合、分割した出力データを対応する演算ノードの出力に割り当てる。
【００７４】
ステップＳ４１３では、i2とm2が一致するかどうかを判定し、一致する場合は終了して（図６の）ステップＳ２０８へ進む。一致しない場合は、ステップＳ４１４でiに１が加算されてステップＳ４０３へ戻る。
【００７５】
（ＤＦＧ生成例１）
以下では、図４（ａ）のプログラムから図４（ｃ）のＤＦＧを生成する例について説明する。
【００７６】
このプログラムは、「x +=1」と、「*y -= x」の２つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。図５を参照して、ステップＳ１０１では、演算数は２であるから、ｍに２が代入される。１番目の演算「x +=1」（x = x +1 と同義）の入力データはｘと１であり、ｘは16ビット変数なのでａは16ビットとなる（Ｓ１０３）。また、出力データであるｘも16ビットなので、ｂも16ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、１番目の演算ビット数を16と判定する（Ｓ１０７）。
【００７７】
再びＳ１０３へ戻り、２番目の演算「*y -= x」（y = y - x と同義）の入力データはｙとｘであり、ｘが16ビットに対し、ｙが32ビットなのでaは32ビットとなる。また、出力データであるｙも32ビットなので、ｂも32ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、２番目の演算ビット数を３２と判定する（Ｓ１０７）。
【００７８】
以上の処理により、図４（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。なお、この中間ＤＦＧにおいては、１番目の演算ノードn01は16ビットの加算を行い、２番目の演算ノードn02は32ビットの減算を行うものである。
【００７９】
次に、Ｓ２００（図６）へ進む。演算数ｍは２であり（Ｓ２０１）、１番目の演算（上記中間ＤＦＧのノードn01の演算に対応）のビット数ａは16である（Ｓ２０３）。a=r=16であるから、b=1となり、１個の加算ノード（図４（ｃ）のノードn11）が生成される（Ｓ２０７）。
【００８０】
そして、Ｓ３００（図７）へ進む。１番目の演算の入力はｘと１であり（ノードn01への入力に対応）、m1は２である（Ｓ３０１）。このうちの１番目の入力データであるｘは16ビットなのでa1は16であり（Ｓ３０５）、r1と等しいのでb1は１となる（Ｓ３０８）。Ｓ２０７で生成されたノード数sとb1は等しいので、ｘがそのまま演算ノードn11の入力となる（Ｓ３１４）。そして、Ｓ３０３へ戻り、２番目の入力である「１」は、ビット数が２であり（符号ビット付）、b1=1となる（Ｓ３０８）。そして、１がそのまま演算ノードn11の入力となる（Ｓ３１４）。
【００８１】
そして、Ｓ４００（図８）へ進む。１番目の演算の出力は、図４（ｂ）のノードn01からの出力に対応するが、これは、図４（ｂ）の中間ＤＦＧのノードn02への出力となるから、Ｓ４０４ではＹｅｓと判定され、結局、実質的に何の処理も行われないままＳ４００の処理が完了する。
【００８２】
再び図６を参照して、この後、Ｓ２０８、Ｓ２０９を経て、再びＳ２０３へ進む。２番目の演算（上記中間ＤＦＧのノードn02の演算に対応）のビット数ａは32であり、a>rなので、Ｓ２０５へ進む。そして、Ｓ２０５、Ｓ２０７を経て２個の減算ノード（図４（ｃ）のノードn12、n13）が生成される。
【００８３】
そして、Ｓ３００（図７）へ進む。２番目の演算の入力はｙとノード（中間ＤＦＧのノードn01）からの入力の２つでり、m1は２である（Ｓ３０１）。１番目の入力データであるｙは32ビットなのでa1は３２であり（Ｓ３０５）、r1(=16)よりも大きいのでＳ３０７へ進む。そして、yは、上位データy(H)と、下位データy(L)の２つに分割される。続くＳ３０９では、b1=s==2だから、Ｓ３１４へ進み、y(L)をn12の入力として、y(H)をn13の入力としてそれぞれ割り当てる。その後、Ｓ３１５、Ｓ３１６を経て、Ｓ３０３で２番目の入力データが解析されるが、これは中間ＤＦＧのノードn01からの入力であるから、そのまま終了する。
【００８４】
そして、Ｓ４００（図８）へ進む。２番目の演算の出力は、図４（ｂ）のノードn02からの出力に対応し、出力データｙは32ビットであり、a2は３２となる（Ｓ４０５）。このa2はr2よりも大きく、Ｓ４０７で出力データがy(L)、y(H)の２つに分割される。b2=s==2なので、Ｓ４１２へ進み、２個に分割されたy(L)、y(H)のそれぞれがノードn12、n13の出力として割り当てられる。
【００８５】
そして、図４（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【００８６】
（ＤＦＧ生成例２）
以下では、図９（ａ）のプログラムから図９（ｃ）のＤＦＧを生成する例について説明する。
【００８７】
このプログラムは、「y = x + 1」の１つの演算を行うものであり、ｘはint型の32ビットの変数、ｙはshort型の16ビットの変数である。図５を参照して、演算数は１なのでｍに１が代入される（Ｓ１０１）。入力データはｘと１なのでａは32ビットとなる（Ｓ１０３）。出力データであるyは16ビットなので、ｂは16ビットとなる（Ｓ１０４）。ａ＞ｂなのでＳ１０６へ進む。
【００８８】
Ｓ１０６では、演算のビット数がa(=32)ビットの場合と、b(=16)ビットの場合で、「y = x + 1」の演算が同じ結果になるかどうか判定する。ここでは、出力ｙが16ビットであるから、16ビット演算した場合と、32ビット演算して16ビットに変換した結果とでは同じである。従って演算ビット数は16ビットで十分（32ビットも必要ない）と判断する（Ｓ１０８）。
【００８９】
以上の処理により、図９（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。即ち、int型の変数ｘと１（符号付の2ビット変数）がshort型の演算ノードへ入力され、これらの加算結果をshort型の変数yとして出力する演算を行うＤＦＧが生成される。
【００９０】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは16である（Ｓ２０３）。a=r=16であるから、b=1となり、１個の加算ノード（図９（ｃ）の演算ノードn21）が生成される（Ｓ２０７）。
【００９１】
そして、Ｓ３００（図７）へ進む。入力はｘと１であるので入力数m1は２である。i1番目のデータはｘであり、a1は32である（Ｓ３０５）。r1=16であるから、a1＞r1となるので、Ｓ３０６ではyesと判定されて、Ｓ３０７へ進み、入力データであるｘがx(H)とx(L)に分割される。b1=2であるのに対し演算ノード数s=1である（演算ノードｎ２１）から、b1>sなのでＳ３０９ではNoと判断されてＳ３１４へ進む。そして、Ｓ３１４では分割した入力データの下位側のs個（１個）、即ちx(L)を対応する演算ノードn21の入力に割り当てる。
【００９２】
次に2番目のデータ「１」のa1は２ビット（符号付変数と仮定）であるから、a1<r1なので、Ｓ３０６でNoと判断されるので、ステップＳ３０７でb1=1となる。b1=s1=1であるから、Ｓ３０９ではyesと判断される。入力は定数であるから、Ｓ３１０ではyesと判断されてＳ３１３へ進み、Ｓ３１３を経てＳ３１４において、「１」が演算ノードn21の入力として割り当てられる（Ｓ３１４）。
【００９３】
そして、Ｓ４００（図８）へ進む。演算の出力は、short型変数のｙであり、a2=16である（Ｓ４０５）。a2=r2=16だから、b2=s==1となり、１個の出力データが対応する演算ノードn21の出力に割り当てられる。
【００９４】
そして、図６へ戻り、図９（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【００９５】
（ＤＦＧ生成例３）
以下では、図１０（ａ）のプログラムから図１０（ｃ）のＤＦＧを生成する例を説明する。
【００９６】
このプログラムは、「y = x + 0x000fffff」という１つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。また、0x000fffffは32ビットである。図５を参照して、入力データはｘと0x000fffffなのでａは32ビットとなる（Ｓ１０３）。出力データであるyは32ビットなので、ｂは32ビットとなる（Ｓ１０４）。ａ=ｂなのでＳ１０７へ進み、演算ビット数は32となる。
【００９７】
以上の処理により、図１０（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。
【００９８】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは32である（Ｓ２０３）。r=16であるから、a>rであり、Ｓ２０５を経て、２個の加算ノード（図１０（ｃ）のノードn32、及びノードn33）が生成される（Ｓ２０７）。
【００９９】
そして、Ｓ３００（図７）へ進む。入力はｘと0x000fffffであるので、入力数m1は２である。１番目のデータはｘであり、a1は16である（Ｓ３０５）から、b1=1となる。一方、Ｓ２０７で生成されたノード数sは２だから、b<sなのでＳ３１０へ進む。ｘは定数ではないからＳ３１１へ進む。
【０１００】
Ｓ３１１では、入力データのビット拡張用ノード（図１０（ｃ）のmovノードn31）が生成される。即ち、入力データｘは16ビットであるので、32ビットの下位の演算ノード「+L」（ノードn32）のみの入力にしか対応しておらず、上位の演算ノード「+H」（ノードn33）に入力するｘの上位16ビットのデータを生成する必要がある。movノードは、この上位16ビットの入力データを生成するための処理を行うものである。そして、ｘがこのmovノードへの入力に割り当てられる（Ｓ３１２）。
【０１０１】
次に２番目のデータ「0x000fffff」のa1は32ビットであるから、このデータは下位16ビットの「0xffff」と上位16ビットの「0x000f」に分割され（Ｓ３０７）b1=2となる。Ｓ３０９では、b1=s=2であるから、Ｓ３０９からＳ３１４へ進み、分割した入力データ「0xffff」「0x000f」のそれぞれを演算ノードn32、n33の入力へ割り当てる。
【０１０２】
そして、Ｓ４００（図８）へ進む。演算の出力は、int型変数のｙであり、a2=32である（Ｓ４０５）。r2=16であるから、a2>r2となるので、Ｓ４０７へ進み、出力データがy(L)とy(H)の２つに分割される。b2=s=2であるから、Ｓ４０９からＳ４１２へ進み、分割された出力データy(L)、y(H)のそれぞれが演算ノードn32、n33の出力に割り当てられる。
【０１０３】
そして、図６へ戻り、図１０（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【０１０４】
（ＤＦＧ生成例４）
以下では、図１１（ａ）のプログラムから図１１（ｃ）のＤＦＧを生成する例を説明する。
【０１０５】
このプログラムは、「y = x + 1」という１つの演算を行うものであり、ｘはshort型の16ビットの変数、ｙはint型の32ビットの変数である。図５を参照して、入力データはｘと1なのでａは16ビットとなる（Ｓ１０３）。出力データであるyは32ビットなので、ｂは32ビットとなる（Ｓ１０４）。a < bなのでＳ１０７へ進み、演算ビット数は16となる。
【０１０６】
以上の処理により、図１１（ｂ）のような入出力ビット数と、演算ビット数が確定した中間ＤＦＧを生成することができる。
【０１０７】
次に、Ｓ２００（図６）へ進む。演算のビット数ａは16である（Ｓ２０３）。r=16であるから、a = rであり、Ｓ２０６でb=1となるので、１個の加算ノード（図１１（ｃ）の加算ノードn41）が生成される（Ｓ２０７）。
【０１０８】
そして、Ｓ３００（図７）へ進む。入力はｘと１であるので、入力数m1は２である。i1番目のデータはｘであり、a1は16である（Ｓ３０５）から、a1=r1=16なので、b1=1となる。Ｓ２０７で生成されたノード数sは１だから、b=sなのでＳ３１４へ進む。そして、ｘが加算ノードn41への入力に割り当てられる（Ｓ３１４）。
【０１０９】
次に2番目のデータ「１」のa1は２ビット（符号付変数であると仮定）であるから、b1=1となる。そして、同様にして、「１」が加算ノードn41の他の入力となる（Ｓ３１４）。
【０１１０】
そして、Ｓ４００（図８）へ進む。演算の出力はint型変数のｙであり、a2=32である（Ｓ４０５）。a2>r2であるから、Ｓ４０７へ進む。Ｓ４０７では、出力データが２つ（y(L)とy(H)）に分割される。そして、b2=2に対しs=1であるからＳ４１０へ進む。
【０１１１】
出力データｙは32ビットであるため、16ビットの加算ノードからは出力データｙの上位16ビットであるy(H)を出力できない。そこで、加算ノードの結果をビット拡張し、出力データの上位16ビットのy(H)を生成し出力する必要がある。そこで、Ｓ４１０では、出力データのビット拡張用mov(mov L, mov H)ノードn42が生成される。そして、生成したビット拡張用ノード(mov L, mov H)に出力データy(L)とy(H)がそれぞれ割り当てられる（Ｓ４１１）。
【０１１２】
そして、図６へ戻り、図１１（ｃ）のようなＤＦＧが生成される（Ｓ２１０）。
【０１１３】
（ＤＦＧの割り当て例）
上記の方法で生成したＤＦＧをリコンフィギュラブル回路１２に実際にマッピングした場合の様子を説明する。
【０１１４】
図４（ｃ）のＤＦＧをリコンフィギュラブル回路１２に割り当てた場合、図１２のようになる。
【０１１５】
上記で示した処理を実現することにより、多倍長演算のような処理が可能なリコンフィギュラブル回路に対応したＤＦＧを自動的に生成することができる。また、これにより実行プログラムから実行設定データの生成までの時間が短縮できるため、リコンフィギュラブル回路に所望の処理を実行させるための開発期間を短縮させることができる。
【０１１６】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【０１１７】
例示した図では、多倍長演算のノードを縦に並べた構成になっているが、これはリコンフィギュラブル回路の処理に依存するものであり、この構成に限定されるものではない。例えば、横に並ぶ等、様々な構成がありえる。
【０１１８】
また、上記では、２倍長演算を例に説明したが、本発明の概念は３以上の多倍長演算を行うためのＤＦＧの生成にも適用できる。例えば、図１３に示すような３倍長演算を行うＤＦＧの生成にも適用できる。
【０１１９】
なお、上記ではステップＳ１００により中間ＤＦＧを生成するものとして説明しているが、実際に中間ＤＦＧを生成することなく、演算ビット数、入出力ビット数の情報を、続くステップＳ２００で利用できるよう格納しておくようにしても良い。
【図面の簡単な説明】
【０１２０】
【図１】実施の形態に係る処理装置１０の構成図である。
【図２】リコンフィギュラブル回路１２の構成を示す図である。
【図３】リコンフィギュラブル回路１２を用いて倍長演算を行う例を説明する図である。
【図４】ＣソースプログラムからＤＦＧを生成する第１の例である。
【図５】演算ビット数を判定する処理（ステップＳ１００）のフローチャートである。
【図６】ＤＦＧを生成する処理（ステップＳ２００）のフローチャートである。
【図７】入力変換処理（ステップＳ３００）のフローチャートである。
【図８】出力変換処理（ステップＳ４００）のフローチャートである。
【図９】ＣソースプログラムからＤＦＧを生成する第２の例を示す図である。
【図１０】ＣソースプログラムからＤＦＧを生成する第３の例を示す図である。
【図１１】ＣソースプログラムからＤＦＧを生成する第４の例を示す図である。
【図１２】図４（ｃ）のＤＦＧをリコンフィギュラブル回路１２に割り当てた後の状態である。
【図１３】３倍長演算を行う場合のＤＦＧを示す図である。
【図１４】従来の方法で生成したＤＦＧを説明する図である。
【符号の説明】
【０１２１】
１０ 処理装置
１２ リコンフィギュラブル回路
１４ 設定部
１８ 制御部
３０ コンパイル部
３２ 設定データグラフ処理部
【特許請求の範囲】
【請求項１】
演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成装置において、
前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、
演算に対応するノードを生成するノード生成部を備え、
前記ノード生成部は、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する、データフローグラフ生成装置。
【請求項２】
前記演算ビット数決定部は、演算の入力データのビット数に基づいて前記演算ビット数を決定する、請求項１記載のデータフローグラフ生成装置。
【請求項３】
前記演算ビット数決定部は、
前記入力データのビット数が前記出力データのビット数よりも大きいとき、前記演算ビット数を出力データのビット数と等しく設定した場合と、前記出力データのビット数よりも大きく設定した場合の演算結果を比較し、
比較した演算結果が等しいとき、出力データのビット数を演算ビット数と決定する、請求項２記載のデータフローグラフ生成装置。
【請求項４】
前記ノード生成部は、
１つの演算に対して複数の演算ノードが生成されたとき、前記演算の入力、及び/又は出力データを、それぞれの演算ノードの入力、及び/又は出力に対応させるための変換を行う入出力変換部を備える、請求項１ないし３のいずれかに記載のデータフローグラフ生成装置。
【請求項５】
前記入出力変換部は、
入力データのビット数が前記論理回路の入力ビット数よりも大きいとき、前記入力データを複数の入力データに分割して、それぞれの演算ノードの入力に対応させるようなデータフローグラフを生成する、請求項４記載のデータフローグラフ生成装置。
【請求項６】
前記入出力変換部は、
出力データのビット数が前記論理回路の出力ビット数よりも大きいとき、前記出力データを複数の出力データに分割して、それぞれの演算ノードの出力に対応させるようなデータフローグラフを生成する、請求項４記載のデータフローグラフ生成装置。
【請求項７】
前記ノード生成部は、
演算の入力データのビット数が前記演算のノードに対応した１以上の前記論理回路で入力可能な総ビット数よりも小さいとき、前記入力データのビット拡張用ノードを生成し、前記入力データを生成したビット拡張用ノードの入力に対応させるようなデータフローグラフを生成する、請求項１ないし６のいずれかに記載のデータフローグラフ生成装置。
【請求項８】
前記ノード生成部は、
演算の出力データのビット数が前記演算のノードに対応した１以上の前記論理回路で出力可能な総ビット数よりも大きいとき、前記出力データの出力用ノードを生成する、請求項１ないし６のいずれかに記載のデータフローグラフ生成装置。
【請求項９】
前記演算ビット数決定部は、所期の演算を記述したプログラムから演算に必要な演算ビット数を決定する、請求項１ないし８の何れかに記載のデータフローグラフ生成装置。
【請求項１０】
請求項１ないし９の何れかに記載のデータフローグラフ生成装置と、
前記データフローグラフ生成装置で生成されたデータフローグラフを、前記リコンフィギュラブル回路に供給するための設定データに変換するデータ変換部を備えた、設定データ生成装置。
【請求項１１】
設定データに従って動作するリコンフィギュラブル回路と、
請求項１０に記載の設定データ生成装置で生成された設定データを前記リコンフィギュラブル回路に供給する設定部を備えた処理装置。
【請求項１２】
演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成方法において、
前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定ステップと、
演算に対応するノードを生成するノード生成ステップによりデータフローグラフを生成し、
前記ノード生成ステップでは、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する、データフローグラフ生成方法。
【請求項１】
演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成装置において、
前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定部と、
演算に対応するノードを生成するノード生成部を備え、
前記ノード生成部は、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する、データフローグラフ生成装置。
【請求項２】
前記演算ビット数決定部は、演算の入力データのビット数に基づいて前記演算ビット数を決定する、請求項１記載のデータフローグラフ生成装置。
【請求項３】
前記演算ビット数決定部は、
前記入力データのビット数が前記出力データのビット数よりも大きいとき、前記演算ビット数を出力データのビット数と等しく設定した場合と、前記出力データのビット数よりも大きく設定した場合の演算結果を比較し、
比較した演算結果が等しいとき、出力データのビット数を演算ビット数と決定する、請求項２記載のデータフローグラフ生成装置。
【請求項４】
前記ノード生成部は、
１つの演算に対して複数の演算ノードが生成されたとき、前記演算の入力、及び/又は出力データを、それぞれの演算ノードの入力、及び/又は出力に対応させるための変換を行う入出力変換部を備える、請求項１ないし３のいずれかに記載のデータフローグラフ生成装置。
【請求項５】
前記入出力変換部は、
入力データのビット数が前記論理回路の入力ビット数よりも大きいとき、前記入力データを複数の入力データに分割して、それぞれの演算ノードの入力に対応させるようなデータフローグラフを生成する、請求項４記載のデータフローグラフ生成装置。
【請求項６】
前記入出力変換部は、
出力データのビット数が前記論理回路の出力ビット数よりも大きいとき、前記出力データを複数の出力データに分割して、それぞれの演算ノードの出力に対応させるようなデータフローグラフを生成する、請求項４記載のデータフローグラフ生成装置。
【請求項７】
前記ノード生成部は、
演算の入力データのビット数が前記演算のノードに対応した１以上の前記論理回路で入力可能な総ビット数よりも小さいとき、前記入力データのビット拡張用ノードを生成し、前記入力データを生成したビット拡張用ノードの入力に対応させるようなデータフローグラフを生成する、請求項１ないし６のいずれかに記載のデータフローグラフ生成装置。
【請求項８】
前記ノード生成部は、
演算の出力データのビット数が前記演算のノードに対応した１以上の前記論理回路で出力可能な総ビット数よりも大きいとき、前記出力データの出力用ノードを生成する、請求項１ないし６のいずれかに記載のデータフローグラフ生成装置。
【請求項９】
前記演算ビット数決定部は、所期の演算を記述したプログラムから演算に必要な演算ビット数を決定する、請求項１ないし８の何れかに記載のデータフローグラフ生成装置。
【請求項１０】
請求項１ないし９の何れかに記載のデータフローグラフ生成装置と、
前記データフローグラフ生成装置で生成されたデータフローグラフを、前記リコンフィギュラブル回路に供給するための設定データに変換するデータ変換部を備えた、設定データ生成装置。
【請求項１１】
設定データに従って動作するリコンフィギュラブル回路と、
請求項１０に記載の設定データ生成装置で生成された設定データを前記リコンフィギュラブル回路に供給する設定部を備えた処理装置。
【請求項１２】
演算機能の変更が可能なリコンフィギュラブル回路の演算動作を記述するものとして、前記リコンフィギュラブル回路の論理回路の演算機能をノードとして表現し入力データから出力データにいたるデータの流れをノードの接続で表現するデータフローグラフを生成するデータフローグラフ生成方法において、
前記論理回路で行う演算に必要な演算ビット数を決定する演算ビット数決定ステップと、
演算に対応するノードを生成するノード生成ステップによりデータフローグラフを生成し、
前記ノード生成ステップでは、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも小さい又は等しいとき、前記１つの演算に対応する１つのノードを生成し、
前記必要な演算ビット数が前記演算可能な演算ビット数よりも大きいとき、前記１つの演算に対応して複数のノードを生成する、データフローグラフ生成方法。
【図２】
【図１２】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１３】
【図１４】
【図１２】
【図１】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１３】
【図１４】
【公開番号】特開２００９−４３０２７（Ｐ２００９−４３０２７Ａ）
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願番号】特願２００７−２０７３３８（Ｐ２００７−２０７３３８）
【出願日】平成１９年８月９日（２００７．８．９）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
【公開日】平成２１年２月２６日（２００９．２．２６）
【国際特許分類】
【出願日】平成１９年８月９日（２００７．８．９）
【出願人】（０００００１８８９）三洋電機株式会社 (18,308)
【Ｆターム（参考）】
[ Back to top ]