(57)【要約】【課題】  機能の変更が可能なリコンフィギュラブル回路を有する処理装置を提供する。【解決手段】  本発明の処理装置は、データフローグラフを処理するデータフローグラフ処理部３１を備える。データフローグラフ処理部３１において、ノード群探索部６０が、データフローグラフに含まれる所定の規則を有するデータフローの一群を探索し、ノード置換部６１が、その一群を１つのノードに置換する。ＤＦＧ再構成部６２は、置換されたノードをもとにデータフローグラフを再構成する。【選択図】図１７
2005275698.tif 000002
【特許請求の範囲】
【請求項１】
機能の変更が可能なリコンフィギュラブル回路の動作設定に必要なデータフローグラフを処理する方法であって、
処理の動作を記述した動作記述をもとに、演算間の実行順序の依存関係を表現するデータフローグラフを生成するステップと、
データフローグラフに含まれる所定の規則を有するデータフローの一群を、所定数のノードに置換するステップと、
を備えることを特徴とするデータフローグラフ処理方法。
【請求項２】
置換するステップは、リコンフィギュラブル回路における基本演算で構成されるデータフローの一群を１つのノードに置換することを特徴とする請求項１に記載のデータフローグラフ処理方法。
【請求項３】
置換するデータフローの一群に含まれるノードと同一段に位置するノードに演算が割り当てられていない場合に、同一段に位置するノードを削除するステップをさらに備えることを特徴とする請求項１または２に記載のデータフローグラフ処理方法。
【請求項４】
データフローグラフを生成するステップは、乗算演算のデータフローグラフを生成することを特徴とする請求項１から３のいずれかに記載のデータフローグラフ処理方法。
【請求項５】
乗算演算を、所定の桁で分割するステップをさらに含むことを特徴とする請求項４に記載のデータフローグラフ処理方法。
【請求項６】
分割するステップは、乗数を２進表示した場合の乗算演算を奇数桁と偶数桁に分割することを特徴とする請求項５に記載のデータフローグラフ処理方法。
【請求項７】
それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、
前段の論理回路の出力と後段の論理回路の入力の接続関係を設定可能な接続部とを備えたリコンフィギュラブル回路であって、
前記論理回路は、演算機能のそれぞれを実行する基本演算素子の複数個を所定の規則の下で接続する組合せ用結線を有することを特徴とするリコンフィギュラブル回路。
【請求項８】
前記組合せ用結線により複数の基本演算素子を接続することで、当該論理回路が、複数の基本演算素子を組み合わせた、単独の基本演算素子とは異なる演算機能を実行可能とすることを特徴とする請求項７に記載のリコンフィギュラブル回路。
【請求項９】
機能の変更が可能なリコンフィギュラブル回路と、
前記リコンフィギュラブル回路に、データフローグラフに含まれる所定の規則を有するデータフローの一群を所定数のノードに置換して生成された設定データを供給する設定部と、
前記リコンフィギュラブル回路に複数の設定データを順次供給するように前記設定部を制御する制御部と、
を備えることを特徴とする処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、機能の変更が可能なリコンフィギュラブル回路に関し、特にリコンフィギュラブル回路の動作設定に必要なデータフローグラフを処理する技術に関する。
【背景技術】
【０００２】
近年、アプリケーションに応じてハードウェアの動作を変更可能なリコンフィギュラブルプロセッサの開発が進められている。リコンフィギュラブルプロセッサを実現するためのアーキテクチャとしては、ＤＳＰ(Digital Signal Processor)や、ＦＰＧＡ(Field Programmable Gate Array)を用いる方法が存在する。
【０００３】
ＦＰＧＡ（Field Programmable Gate Array）はＬＳＩ製造後に回路データを書き込んで比較的自由に回路構成を設計することが可能であり、専用ハードウエアの設計に利用されている。ＦＰＧＡは、論理回路の真理値表を格納するためのルックアップテーブル（ＬＵＴ）と出力用のフリップフロップからなる基本セルと、その基本セル間を結ぶプログラマブルな配線リソースとを含む。ＦＰＧＡでは、ＬＵＴに格納するデータと配線データを書き込むことで目的とする論理演算を実現できる。しかし、ＦＰＧＡでＬＳＩを設計した場合、ＡＳＩＣ（Application Specific IC）による設計と比べると、実装面積が非常に大きくなり、コスト高になる。そこで、ＦＰＧＡを動的に再構成することで、回路構成の再利用を図る方法が提案されている（例えば、特許文献１参照。）。
【特許文献１】特開平１０−２５６３８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
例えば衛星放送では、季節などにより、放送モードを切り替えて画質の調整などを行うこともある。受信機では、放送モードごとに複数の回路を予めハードウェア上に作り込んでおき、放送モードに合わせて選択器で回路を切り替えて受信している。したがって、受信機の他の放送モード用の回路はその間、遊んでいることになる。モード切り替えのように、複数の専用回路を切り替えて使用し、その切り替え間隔が比較的長い場合、複数の専用回路を作り込む代わりに、切り替え時にＬＳＩを瞬時に再構成することにすれば、回路構造をシンプルにして汎用性を高め、同時に実装コストを抑えることができる。このようなニーズに応えるべく、動的に再構成可能なＬＳＩに製造業界の関心が集まっている。特に、携帯電話やＰＤＡ（Personal Data Assistance）などのモバイル端末に搭載されるＬＳＩは小型化が必須であり、ＬＳＩを動的に再構成し、用途に合わせて適宜機能を切り替えることができれば、ＬＳＩの実装面積を抑えることができる。
【０００５】
ＦＰＧＡは回路構成の設計自由度が高く、汎用的である反面、全ての基本セル間の接続を可能とするため、多数のスイッチとスイッチのＯＮ／ＯＦＦを制御するための制御回路を含む必要があり、必然的に制御回路の実装面積が大きくなる。また、基本セル間の接続に複雑な配線パターンをとるため、配線が長くなる傾向があり、さらに１本の配線に多くのスイッチが接続される構造のため、遅延が大きくなる。そのため、ＦＰＧＡによるＬＳＩは、試作や実験のために利用されるにとどまることが多く、実装効率、性能、コストなどを考えると、量産には適していない。さらに、ＦＰＧＡでは、多数のＬＵＴ方式の基本セルに構成情報を送る必要があるため、回路のコンフィグレーションにはかなりの時間がかかる。そのため、瞬時に回路構成の切り替えが必要な用途にはＦＰＧＡは適していない。
【０００６】
それらの課題を解決するため、近年、ＡＬＵ(Arithmetic Logic Unit)と呼ばれる基本演算機能を複数持つ多機能素子を多段に並べたＡＬＵアレイの検討が行われるようになった。ＡＬＵアレイでは、処理が上段から下段の一方向に流れるので、水平方向のＡＬＵを結ぶ配線は基本的には不要である。そのため、ＦＰＧＡと比較して回路規模を小さくすることが可能となる。
【０００７】
ＡＬＵアレイでは、コマンドデータによりＡＬＵ回路の演算機能構成と前後段のＡＬＵを接続する接続部の配線が制御され、所期の演算処理を実行することができる。コマンドデータは、一般にＣ言語等の高級プログラム言語で記述されたソースプログラムからデータフローグラフ（ＤＦＧ：Data Flow Graph）を作成し、その情報をもとに作成される。
【０００８】
ＡＬＵは、加算演算やシフト演算などの演算機能をそれぞれ実行する複数の基本演算素子を備えて構成される。ＡＬＵが基本演算素子を多く持つことは、それだけＡＬＵアレイの演算能力を高め、演算処理の汎用性を高めることができる。一方で、ＡＬＵの基本演算素子の数を増やすことは、それだけＡＬＵの回路規模が大きくなるという欠点もある。
【０００９】
例えば、乗算演算機能を実行する基本演算素子をＡＬＵに作りこんだ場合、その基本演算素子の回路規模が大きくなるため、ＡＬＵアレイ全体の回路規模が増大する。一方、乗算演算素子を有しないＡＬＵアレイで乗算演算を実行する場合、加算演算やシフト演算などを組み合わせたＤＦＧを作成して、ＡＬＵアレイにマッピングすることになる。この場合、ＤＦＧが非常に大きくなり、乗算処理に時間がかかり、処理の高速性が損なわれるとともに、ＡＬＵアレイの消費電力が増加する。
【００１０】
本発明はこうした状況に鑑みてなされたもので、その目的は、効率よくデータフローグラフを作成し、また効率よくデータフローグラフを実行するリコンフィギュラブル回路および処理装置に関する技術を提供することにある。
【課題を解決するための手段】
【００１１】
上記課題を解決するために、本発明のある態様は、機能の変更が可能なリコンフィギュラブル回路の動作設定に必要なデータフローグラフを処理する方法に関する。このデータフローグラフ処理方法は、処理の動作を記述した動作記述をもとに、演算間の実行順序の依存関係を表現するデータフローグラフを生成するステップと、データフローグラフに含まれる所定の規則を有するデータフローの一群を、所定数のノードに置換するステップとを備える。この態様のデータフローグラフ処理方法によると、データフローの一群を所定数のノードに置換することで、もとのデータフローグラフよりも小さいデータフローグラフを再構成することが可能となる。
【００１２】
本発明の別の態様は、それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、前段の論理回路の出力と後段の論理回路の入力の接続関係を設定可能な接続部とを備えたリコンフィギュラブル回路に関する。この態様のリコンフィギュラブル回路において、論理回路は、演算機能のそれぞれを実行する基本演算素子の複数個を所定の規則の下で接続する組合せ用結線を有して構成される。この態様のリコンフィギュラブル回路によると、１つの論理回路が、複数の基本演算素子を組み合わせた演算機能を実行することが可能となる。
【００１３】
本発明のさらに別の態様は、機能の変更が可能なリコンフィギュラブル回路と、リコンフィギュラブル回路に、データフローグラフに含まれる所定の規則を有するデータフローの一群を所定数のノードに置換して生成された設定データを供給する設定部と、リコンフィギュラブル回路に複数の設定データを順次供給するように前記設定部を制御する制御部とを備える処理装置を提供する。
論理回路は、複数種類の多ビット演算を選択的に実行可能な算術論理回路であってよい。
【００１４】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムとして表現したものもまた、本発明の態様として有効である。
【発明の効果】
【００１５】
本発明によれば、リコンフィギュラブル回路の動作設定に必要なデータフローグラフを効率的に処理する技術、さらにはデータフローグラフを実行するリコンフィギュラブル回路および処理装置を提供することができる。
【発明を実施するための最良の形態】
【００１６】
図１は、実施の形態に係る処理装置１０の構成図である。処理装置１０は、回路構成を再構成可能とする機能を有する集積回路装置２６を備える。集積回路装置２６は１チップとして構成され、リコンフィギュラブル回路１２、設定部１４、制御部１８、内部状態保持回路２０、出力回路２２、第１フィードバック経路２４、遅延保持回路２７および第２フィードバック経路２９を備える。リコンフィギュラブル回路１２は設定を変更することにより、機能の変更を可能とする。リコンフィギュラブル回路１２は組合せ回路または順序回路等の論理回路として構成される。第１フィードバック経路２４および第２フィードバック経路２９は、フィードバックパスとして機能し、リコンフィギュラブル回路１２の出力を、リコンフィギュラブル回路１２の入力に接続する。
【００１７】
リコンフィギュラブル回路１２は、それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、前段の論理回路の出力と後段の論理回路の入力の接続関係を設定可能な接続部とを備える。構造的には、複数の論理回路列の間に、論理回路列間の接続用結線を設定する接続部が設けられる。リコンフィギュラブル回路１２は、複数段に配列された各論理回路の機能、および論理回路間の接続を任意に設定することで、機能の変更を可能とする。本実施の形態における論理回路は、演算機能のそれぞれを実行する基本演算素子の複数個を所定の規則の下で接続する組合せ用結線を有して構成される。
【００１８】
設定部１４は、リコンフィギュラブル回路１２に所期の回路を構成するための設定データ４０を供給する。設定部１４は、プログラムカウンタのカウント値に基づいて記憶したデータを出力するコマンドメモリとして構成されてもよい。この場合、制御部１８がプログラムカウンタの出力を制御する。この場合、設定データ４０はコマンドメモリから出力されるコマンドデータであってよい。
【００１９】
内部状態保持回路２０は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２の出力を受け付ける。内部状態保持回路２０は第１フィードバック経路２４に接続されており、リコンフィギュラブル回路１２の出力を直接リコンフィギュラブル回路１２の入力にフィードバックさせる。また内部状態保持回路２０は、リコンフィギュラブル回路１２の出力を遅延保持回路２７に供給する。内部状態保持回路２０は選択器を有し、選択器は、制御部からの選択指示をもとに、第１フィードバック経路２４に送り出すデータ、および遅延保持回路２７に供給するデータを選択する。なお、選択器は、同一のデータを第１フィードバック経路２４および遅延保持回路２７の双方に送り出してもよい。
【００２０】
遅延保持回路２７はメモリであって、リコンフィギュラブル回路１２から出力される出力データを格納するための複数のＲＡＭにより構成される。遅延保持回路２７は、リコンフィギュラブル回路１２の出力データを任意の時間遅延させる機能をもつ。この例では、遅延保持回路２７が、内部状態保持回路２０から出力されるデータを格納しているが、リコンフィギュラブル回路１２から直接出力されるデータを格納してもよい。遅延保持回路２７は、制御部１８からのＷ／Ｒイネーブル信号およびアドレス信号に基づいて、データの書込／読出を行う。遅延保持回路２７は第２フィードバック経路２９に接続されており、制御部１８からの読出指示に基づいて、所期のタイミングでデータをリコンフィギュラブル回路１２の入力にフィードバックさせる。なお、設定部１４がコマンドメモリとして構成されている場合、コマンドメモリから供給されるコマンドデータで、遅延保持回路２７のデータの書込／読出を行ってもよい。
【００２１】
出力回路２２は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２から出力されるデータを外部に出力する。この例では、出力回路２２が、遅延保持回路２７から出力されるデータを受け付けているが、リコンフィギュラブル回路１２から直接出力されるデータを受け付けてもよく、また内部状態保持回路２０から出力されるデータを受け付けてもよい。
【００２２】
処理装置１０においては、リコンフィギュラブル回路１２の出力をリコンフィギュラブル回路１２の入力にフィードバックする経路が、第１フィードバック経路２４および第２フィードバック経路２９の２系統存在する。第１フィードバック経路２４は、遅延保持回路２７を介さないために、リコンフィギュラブル回路１２の出力データを高速にフィードバック処理することが可能である。一方、第２フィードバック経路２９は、制御部１８からの指示により所期のタイミングでデータ信号をリコンフィギュラブル回路１２に供給することができる。このように、第１フィードバック経路２４または第２フィードバック経路２９は、リコンフィギュラブル回路１２上に再構成する回路に応じて適宜使い分けられる。
【００２３】
リコンフィギュラブル回路１２は、機能の変更が可能な論理回路を有して構成される。複数の論理回路は、マトリックス状に配置された構造をとってもよい。各論理回路の機能と、論理回路間の接続関係は、設定部１４により供給される設定データ４０に基づいて設定される。また、論理回路内において、基本演算素子同士を接続する組合せ用結線も、設定データ４０に基づいて設定される。設定データ４０は、以下の手順で生成される。
【００２４】
集積回路装置２６により実現されるべきプログラム３６が、記憶部３４に保持されている。プログラム３６は、回路における処理の動作を記述した動作記述を示し、信号処理回路または信号処理アルゴリズムなどをＣ言語などの高級言語で記述したものである。コンパイル部３０は、記憶部３４に格納されたプログラム３６をコンパイルし、データフローグラフ（ＤＦＧ）３８に変換して記憶部３４に格納する。データフローグラフ３８は、回路における演算間の実行順序の依存関係を表現し、入力変数および定数の演算の流れをグラフ構造で示したものである。一般に、データフローグラフ３８は、上から下に向かって演算が進むように作成される。
【００２５】
本実施の形態では、論理回路が複数の基本演算素子を有して、それぞれの演算機能を実行する。一般的に用いる演算としては、加算演算や減算演算など様々なものをあげることができるが、そのうちの一つに乗算演算がある。リコンフィギュラブル回路１２の汎用性という観点からは、各論理回路が乗算を実行する基本演算素子を備えることが好ましいが、実際には乗算用の演算素子は、他の加算演算などの演算素子と比較すると、回路規模が非常に大きい。そのため、論理回路は、乗算用の基本演算素子を持たずに構成され、データフローグラフ３８中の乗算演算は、筆算アルゴリズムやBoothアルゴリズムなどを用いて加算やビットシフトなどで演算できる形態に展開する必要がある。乗算演算の展開は、コンパイル部３０により実行される。
【００２６】
データフローグラフ処理部３１は、コンパイル部３０により生成されたデータフローグラフ３８から、所定の規則を有するデータフローの一群を探索する。このデータフローの一群は、演算ノード間に所定の接続関係を有するノードの集合であって、予め記憶部３４において登録されている。データフローグラフ処理部３１は、所定のデータフローの一群を探索して、その一群を構成するノード数よりも少ない数のノードに置換する。このとき、ノード数を減らす観点から、１つのノードに置換することが好ましい。
【００２７】
なお、データフローの一群から置換されたノードは、リコンフィギュラブル回路１２の論理回路で処理可能なノードである必要がある。これに対応して、論理回路は、置換されたノードを処理するために、自身のもつ複数の基本演算素子を所定の順序で組み合わせるための組合せ用結線を有して構成される。これにより、論理回路は基本演算素子の数を増やすことなく、組合せ用結線をもつことで、複数の基本演算素子により実行される新たな演算機能をもつことができる。言い換えると、論理回路における複数の基本演算素子の可能な組合せに応じて、所定の規則を有するデータフローの一群を予め登録し、データフローグラフ処理部３１が、１つの論理回路において実行可能なデータフローの一群を探索して、１つのノードに置換するすることが可能となる。
【００２８】
設定データ生成部３２は、データフローグラフ３８から設定データ４０を生成する。設定データ４０は、データフローグラフ３８をリコンフィギュラブル回路１２にマッピングするためのデータであり、リコンフィギュラブル回路１２における論理回路の機能や論理回路間の接続関係を定める。設定データ生成部３２が、１つの生成すべき回路を分割してできる複数の回路の設定データ４０を生成してもよい。
【００２９】
図２は、１つの生成すべきターゲット回路４２を分割してできる複数の回路の設定データ４０について説明するための図である。１つのターゲット回路４２を分割して生成される回路を、「分割回路」と呼ぶ。この例では、１つのターゲット回路４２が、４つの分割回路、すなわち分割回路Ａ、分割回路Ｂ、分割回路Ｃ、分割回路Ｄに分割されている。ターゲット回路４２は、データフローグラフ３８における演算の流れにしたがって分割される。データフローグラフ３８において、上から下に向かう方向に演算の流れが表現される場合、そのデータフローグラフ３８を上から所定の間隔で切り取り、その切り取った部分を分割回路として設定する。流れにしたがって切り取る間隔は、リコンフィギュラブル回路１２における論理回路の段数以下に定められる。ターゲット回路４２は、データフローグラフ３８の横方向で分割されてもよい。横方向に分割する幅は、リコンフィギュラブル回路１２における論理回路の１段当たりの個数以下に定められる。
【００３０】
特に、生成すべきターゲット回路４２がリコンフィギュラブル回路１２よりも大きい場合に、設定データ生成部３２は、リコンフィギュラブル回路１２にマッピングできる大きさになるように、ターゲット回路４２を分割することが好ましい。リコンフィギュラブル回路１２へのマッピングは、一度に、例えば１回のクロックで実行することができる。したがって、この場合、４つの分割回路は、４クロックで生成することができる。設定データ生成部３２は、リコンフィギュラブル回路１２における論理回路の配列構造とデータフローグラフ３８によって、ターゲット回路４２の分割方法を定める。リコンフィギュラブル回路１２の配列構造は、制御部１８から設定データ生成部３２に伝えられてもよく、また予め記憶部３４に記録されていてもよい。また、制御部１８が、ターゲット回路４２の分割方法を設定データ生成部３２に指示してもよい。
【００３１】
以上の手順を実行することにより、記憶部３４は、リコンフィギュラブル回路１２を所期の回路として構成するための複数の設定データ４０を記憶する。複数の設定データ４０は、分割回路Ａを構成するための設定データ４０ａ、分割回路Ｂを構成するための設定データ４０ｂ、分割回路Ｃを構成するための設定データ４０ｃ、および分割回路Ｄを構成するための設定データ４０ｄである。既述のごとく、複数の設定データ４０は、１つのターゲット回路４２を分割した複数の分割回路をそれぞれ表現したものである。各設定データ４０を供給することにより、リコンフィギュラブル回路１２上に分割回路を１クロックで構成することができる。このように、リコンフィギュラブル回路１２の回路規模に応じて、生成すべきターゲット回路４２の設定データ４０を生成することにより、汎用性の高い処理装置１０を実現することが可能となる。別の視点からみると、実施の形態の処理装置１０によれば、回路規模の小さいリコンフィギュラブル回路１２を用いて、所望の回路を再構成することが可能となる。
【００３２】
図３は、リコンフィギュラブル回路１２の一般的な構成を示す。リコンフィギュラブル回路１２は、それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、前段の論理回路の出力と後段の論理回路の入力の接続関係を任意に設定可能な接続部５２とを備える。リコンフィギュラブル回路１２では、論理回路の多段配列構造により、上段から下段に向かって演算が進められる。なお、本明細書および特許請求の範囲において「多段」とは、複数の段を意味する。
【００３３】
リコンフィギュラブル回路１２は、論理回路としてＡＬＵ(Arithmetic Logic Unit)を有している。ＡＬＵは、複数種類の多ビット演算を選択的に実行可能な算術論理回路であって、論理和、論理積、ビットシフト、加算、減算などの複数種類の多ビット演算を設定により選択的に実行できる。各ＡＬＵは、複数の演算機能を設定するためのセレクタを有して構成されている。実施の形態において、ＡＬＵは、乗算を実行する機能は有していない。乗算用の演算素子の回路規模が大きいためであり、したがって、乗算演算は、加算やビットシフト、ビット積演算などを組み合わせることで処理されることになる。図示の例では、ＡＬＵが、２つの入力端子と１つの出力端子を有して構成される。
【００３４】
リコンフィギュラブル回路１２は、縦方向にＸ個、横方向にＹ個のＡＬＵが配置されたＸ段Ｙ列のＡＬＵアレイとして構成される。ここでは、縦方向に３個、横方向に６個のＡＬＵが配置された３段６列のＡＬＵアレイを示している。リコンフィギュラブル回路１２は、接続部５２およびＡＬＵ列５３を備える。ＡＬＵ列５３は複数段に設けられ、接続部５２は前後段のＡＬＵ列５３の間に設けられて、前段のＡＬＵの出力と後段のＡＬＵの入力の接続関係を設定する。
【００３５】
図３に示す例では、第１段のＡＬＵ列５３ａと第２段のＡＬＵ列５３ｂの間に、第２段を構成する接続部５２ｂが設けられ、第２段のＡＬＵ列５３ｂと第３段のＡＬＵ列５３ｃの間に、第３段を構成する接続部５２ｃが設けられる。なお、第１段を構成する接続部５２ａは、第１段のＡＬＵ列５３ａの上側に設けられる。
【００３６】
第１段のＡＬＵ１１、ＡＬＵ１２、・・・、ＡＬＵ１６には、入力変数や定数が入力され、設定された所定の演算がなされる。演算結果の出力は、第２段の接続部５２ｂに設定された接続にしたがって、第２段のＡＬＵ２１、ＡＬＵ２２、・・・、ＡＬＵ２６に入力される。第２段の接続部５２ｂにおいては、第１段のＡＬＵ列５３ａの出力と第２段のＡＬＵ列５３ｂの入力の間で任意の接続関係、あるいは予め定められた接続関係の組合せの中から選択された接続関係を実現できるように接続用結線が構成されており、設定により所期の結線が有効となる。第２段のＡＬＵ２１、ＡＬＵ２２、・・・、ＡＬＵ２６には、ＡＬＵ列５３ａの出力が入力され、設定された所定の演算がなされる。演算結果の出力は、第３段の接続部５２ｃの接続用結線において設定された接続にしたがって、第３段のＡＬＵ３１、ＡＬＵ３２、・・・、ＡＬＵ３６に入力される。
【００３７】
最終段となる第３段のＡＬＵ列５３ｃからの出力データは、内部状態保持回路２０に出力される。内部状態保持回路２０および／または遅延保持回路２７は、第１フィードバック経路２４および／または第２フィードバック経路２９を介して、出力データを接続部５２ａに入力する。接続部５２ａは、接続用結線を設定し、第１段のＡＬＵ１１、ＡＬＵ１２、・・・、ＡＬＵ１６にデータを供給する。
【００３８】
図４は、データフローグラフ３８の構造を説明するための図である。データフローグラフ３８においては、入力される変数や定数の演算の流れが段階的にグラフ構造で表現されている。図中、演算子は丸印で示されている。“＞＞”は右へのビットシフトを示し、“＜＜”は左へのビットシフトを示し、“＋”は加算を示し、“−”は減算を示す。設定データ生成部３２は、このデータフローグラフ３８をリコンフィギュラブル回路１２にマッピングするための設定データ４０を生成する。特にデータフローグラフ３８をリコンフィギュラブル回路１２にマッピングしきれない場合に、データフローグラフ３８を複数の領域に分割して、分割回路の設定データ４０を生成する。データフローグラフ３８による演算の流れを回路上で実現するべく、設定データ４０は、演算機能を割り当てる論理回路を特定し、また論理回路間の接続関係を定め、さらに入力変数や入力定数などを定義したデータとなる。したがって、設定データ４０は、各論理回路の機能を選択するセレクタに供給する選択情報、接続部５２の結線を設定する接続情報、必要な変数データや定数データなどを含んで構成される。
【００３９】
なお、本実施の形態においては、複数の演算機能を選択的に実行可能な論理回路が、乗算演算を実行するための基本演算素子を有していないため、乗算演算は、コンパイル部３０により、論理回路が有する基本演算素子で処理できる加算、ビットシフトなどの演算に展開されて、設定データ４０が生成されることになる。
【００４０】
図１に戻って、回路の構成時、制御部１８は、１つのターゲット回路４２を構成するための複数の設定データ４０を記憶部３４から選択して読み出す。ここでは制御部１８が、図２に示すターゲット回路４２を構成するための設定データ４０、すなわち分割回路Ａの設定データ４０ａ、分割回路Ｂの設定データ４０ｂ、分割回路Ｃの設定データ４０ｃおよび分割回路Ｄの設定データ４０ｄを記憶部３４から読み出し、設定部１４に供給する。設定部１４は、各設定データ４０を格納する。
【００４１】
設定部１４がコマンドメモリとして構成されている場合、制御部１８は設定部１４に対してプログラムカウンタ値を与え、設定部１４は、そのカウンタ値に応じて格納した設定データを、コマンドデータとしてリコンフィギュラブル回路１２に設定する。なお、設定部１４は、キャッシュメモリや他の種類のメモリを有して構成されてもよい。なお、本例においては、制御部１８が記憶部３４から設定データ４０を受けて、その設定データを設定部１４に供給する構成について説明するが、制御部１８を介さずに、予め設定部１４に設定データを格納しておいてもよい。この場合、制御部１８は、設定部１４に予め格納された複数の設定データの中からターゲット回路４２に応じた設定データがリコンフィギュラブル回路１２に供給されるように、設定部１４のデータ読出しを制御する。
【００４２】
設定部１４は、設定データ４０をリコンフィギュラブル回路１２に設定し、リコンフィギュラブル回路１２に回路を逐次再構成させる。これにより、リコンフィギュラブル回路１２は、所期の演算を実行できる。リコンフィギュラブル回路１２は、基本セルとして高性能の演算能力のあるＡＬＵを用いており、またリコンフィギュラブル回路１２および設定部１４を１チップ上に構成することから、コンフィグレーションを高速に、例えば１クロックで実現することができる。制御部１８はクロック機能を有し、クロック信号は、出力回路２２および遅延保持回路２７に供給される。また制御部１８は４進カウンタを含み、カウント信号を設定部１４に供給してもよい。
【００４３】
＜リコンフィギュラブル回路の動作の説明＞
以下では、図５から図１０を用いて、リコンフィギュラブル回路１２による回路構成機能の基本動作の説明を行う。以下に示すリコンフィギュラブル回路１２の基本動作を前提として、かかるリコンフィギュラブル回路１２の動作設定に必要なデータフローグラフの処理方法を図１１以降の図面を用いて説明する。
【００４４】
図５は、前後７点を利用する７タップからなるＦＩＲフィルタ回路を示す。以下、このＦＩＲ（Finite Impulse Response）フィルタ回路を、実施の形態における処理装置１０で実現する具体例を示す。このＦＩＲフィルタ回路の係数は、図５の例では、対称に設定されている。
【００４５】
図６は、図５で示すＦＩＲフィルタ回路を置き換えた回路を示す。回路の置き換えは、フィルタ係数の対称性を利用している。
【００４６】
図７は、図６で示すＦＩＲフィルタ回路をさらに置き換えた回路を示す。ここでは、フィルタ係数に着目した置き換えを行っている。具体的には、係数1/16を1/2×1/2×1/2×1/2に、2/16を1/2×1/2×1/2に、8/16を1/2に置き換えている。係数1/2の演算はデータを右に１ビットシフトすることで実現できる。１ビットシフタは、複数ビットシフタと比べて、ＡＬＵ内において非常に小さいスペースで形成することができる。
【００４７】
図８は、図７に示すＦＩＲフィルタ回路をコンパイルして作成したデータフローグラフ３８ａを示す。図中、“＋”は加算を示し、“＞＞１”は１ビットのシフトを示し、“ＭＯＶ”はスルー用のパスを示す。図示のごとく、データフローグラフ３８ａは、７段の演算子で構成される。
【００４８】
図９は、リコンフィギュラブル回路１２の一例を示す。このリコンフィギュラブル回路１２は、２段４列のＡＬＵを含んで構成される。
【００４９】
図１０は、図８に示すデータフローグラフ３８ａを、図９のリコンフィギュラブル回路１２を用いて実現する例を示す。データフローグラフ３８ａが７段４列で構成され、リコンフィギュラブル回路１２が２段で構成されていることから、データフローグラフ３８ａは、上下方向に４つに分割される。なお、左右方向については、リコンフィギュラブル回路１２の列数が、データフローグラフ３８ａの列数以下であるため、分割する必要はない。なお、ここではリコンフィギュラブル回路１２の列数とデータフローグラフ３８ａの列数とが等しい場合が示されている。分割したデータフローグラフは、リコンフィギュラブル回路１２上に１クロックで構成されることが可能である。
【００５０】
まず、設定部１４が、データフローグラフ３８ａの第１段および第２段の内容を、設定データ４０ａによりリコンフィギュラブル回路１２上に構成する。これにより、第１分割回路がリコンフィギュラブル回路１２に構成される。続いて、設定部１４が、データフローグラフ３８ａの第３段および第４段の内容を、設定データ４０ｂによりリコンフィギュラブル回路１２上に構成する。これにより、第２分割回路がリコンフィギュラブル回路１２に構成される。続いて、設定部１４が、データフローグラフ３８ａの第５段および第６段の内容を、設定データ４０ｃによりリコンフィギュラブル回路１２上に構成する。これにより、第３分割回路がリコンフィギュラブル回路１２に構成される。最後に、設定部１４が、データフローグラフ３８ａの第７段および第８段（ＭＯＶ）の内容を、設定データ４０ｄによりリコンフィギュラブル回路１２上に構成する。これにより、第４分割回路がリコンフィギュラブル回路１２に構成される。第１分割回路から第３分割回路における出力結果は、次の分割回路の入力としてフィードバックされる。
【００５１】
この例において、ＡＬＵは、“＋”、“＞＞１”、“ＭＯＶ”の３種類のみで実現することができる。複数ビットのシフトを、１ビットシフタを複数回利用することにより表現することとしたため、必要とされるＡＬＵの機能を非常に少なくすることができる。これにより、リコンフィギュラブル回路１２の回路規模を小さくできる。なお、当然のことながら、図７に示すデータフローグラフをリコンフィギュラブル回路１２上に構成することも可能である。以上が、リコンフィギュラブル回路１２の基本動作である。
【００５２】
＜データフローグラフの処理機能の説明＞
以下では、乗算演算を実行する場合の実施の形態にかかる処理装置１０の処理について説明する。既述したように、本実施の形態の処理装置１０では、ＡＬＵに乗算用の基本演算素子を持たせるのではなく、乗算演算を、もともとＡＬＵに基本演算素子として組み込まれている加算演算やビットシフト演算などのノードに展開することで、乗算演算用のデータフローグラフ（ＤＦＧ）を実行する。本実施の形態では、複数のノードからなるデータフローの一群を１つのノードに置換することで、ＤＦＧの大きさを小さくし、リコンフィギュラブル回路１２における演算処理を効率よく実行することが可能となり、回路規模の削減および低消費電力化を実現することが可能となる。
【００５３】
乗算のアルゴリズムとして代表的なものに、筆算アルゴリズムやＢｏｏｔｈアルゴリズムがある。以下では、乗算用のプログラム３６が、筆算アルゴリズムで作成されている場合を例にとる。
【００５４】
図１１は、ｍビットの被乗数ｘとｎビットの乗数ｙの筆算アルゴリズムのフローチャートを示す。ここでは、乗数ｙが正の場合を想定する。この演算処理を実行するために、ｍビットの被乗数レジスタ、ｎビットの乗数レジスタ、ｍ＋ｎビットの積レジスタが存在するものとする。演算前に乗数ｙの符号を判定し、正ならば積レジスタの右ｎビット分に乗数ｙを設定し、左ｍビット分に０を初期値として設定する。乗数ｙが負ならば絶対値を乗数ｙとする。
【００５５】
繰返し回数ｒを初期値０に設定して（Ｓ１０）、積レジスタのＬＳＢ（Least Significant Bit）が１であるかどうかを判定する（Ｓ１１）。積レジスタのＬＳＢが１の場合（Ｓ１１のＹ）、被乗数ｘを積レジスタの左ｍビット分に加算して、その加算結果を積レジスタの左ｍビット分に格納し（Ｓ１２）、積レジスタを１ビット右にシフトする（Ｓ１３）。これにより、乗数ｙのＬＳＢについての乗算処理を実行する。なお、積レジスタのＬＳＢが０の場合（Ｓ１１のＮ）、同様に積レジスタを１ビット右にシフトする（Ｓ１３）。ＬＳＢが０の場合は、乗数ｙのＬＳＢと被乗数との乗算結果が０となるため、単に積レジスタを１ビット右シフトするだけでよい。このとき、積レジスタのＭＳＢ（Most Significant Bit）には、１ビット右シフトする前のＭＳＢと同じ数値を入れる。繰返し回数ｒを１インクリメントし（Ｓ１４）、ｒがｎに等しくなったかどうかを判定する（Ｓ１５）。ｒがｎに等しくなるとは、乗数ｙの全ビットについての筆算を完了した場合である。ｒがｎ未満である場合（Ｓ１５のＮ）、Ｓ１１からＳ１４のステップを繰り返し、積レジスタのＬＳＢの乗算処理を逐次実行していく。右に１ビットシフトを行うことは（Ｓ１３）、乗数ｙのビットをＬＳＢから順次ずらしながら、下位のビットから逐次乗算を行っていくことに相当する。ｒがｎに等しくなった場合（Ｓ１５のＹ）、積レジスタに格納された値が乗算結果となり、本フローを終了する。なお、乗数ｙが負の場合は、このフローを（ｎ−１）回、つまり（乗数ｙのビット数−１）回繰り返し、最後に被乗数ｘの符号反転した値を積レジスタの左ｍビット分に加算する。この時オーバーフロー分は切り捨てて、積レジスタの左ｍビット分に格納し、次に積レジスタを１ビット右シフトする。
【００５６】
図１２は、２進数表示した４ビット×４ビットの具体的な処理動作の一例を示す。この処理動作は、図１１に示すフローチャートに基づいている。図１２では、乗数ｙが正である場合を示し、被乗数ｘを１０１１（１０進表示では−５）、乗数ｙを０１１１（１０進表示では７）とする。初期設定として、積レジスタａｎｓに０００００１１１を設定すると、図１２に示すように筆算アルゴリズムにより乗算結果を得ることができる。
【００５７】
図１３は、２進数表示した４ビット×４ビットの具体的な処理動作の別の例を示す。この処理動作は、図１１に示すフローチャートに基づいている。図１３では、乗数ｙが負である場合を示し、被乗数ｘを１０１１（１０進表示では−５）、乗数ｙを１１１１（１０進表示では−１）とする。初期設定として、積レジスタａｎｓに００００１１１１を設定すると、図１２に示すように筆算アルゴリズムにより乗算結果を得ることができる。なお、乗数ｙが負であるため、Ｓ１１〜Ｓ１３の処理を３回繰り返した後、所定の負符号処理を実行することで、乗算演算が終了する。
【００５８】
図１４は、筆算アルゴリズムを用いて被乗数２４ビット×乗数４ビットの計算をするＤＦＧを示す。このＤＦＧは、ＡＬＵに含まれる基本演算素子（基本演算ノード）で実行できるようにコンパイル部３０により展開されたものである。図１４の中の最上段における「１：_Ghissann_ver3_9_1_0_0.y」は乗数４ビットの入力（ｙ系統）を示し、「2：_Ghissann_ver3_9_1_0_0.x」は被乗数２４ビットの入力（ｘ系統）を示す。また最終段における「_Ghissann_ver3_9_1_0_0.ans」は乗算結果を示す。図１４の中の「ａｄｄ」ノードは加算演算、「bgt」ノードは大小比較演算（＜）で、１段目の「1:bgt:20」は「y＜0」を表している。「neg」ノードは符号反転演算、「lsl」は左シフト演算で、１段目の「6:lsl:20」は４ビット左シフト「＜＜4」を表している。「mbgt」ノードは「bgt」ノードの条件により２入力のどちらか一方を選択する選択演算で、破線が条件データを表している。「asr」ノードは右シフト演算、「bne」ノードは等価比較演算（!=）、「mbne」ノードは「bne」ノードの条件により２入力のどちらか一方を選択する選択演算（マージ演算）で、破線が条件データを表している。「nop」ノードは演算を行わない、データスルーのためのノードである。図１４より２４ビット×４ビットの計算には、ノードが２０段必要であり、また、基本演算ノードの数は６５個必要なことがわかる。
【００５９】
図１５は、図１４に示すデータフローグラフにおいて、所定の規則を有するデータフローの一群を点線で囲った図を示す。このＤＦＧにおいては、所定の規則にしたがって配列されたノード群７０が４つ存在している。このデータフローの一群、すなわちノードの一群は、使用する複数の演算機能が同一であり、且つ、演算機能の実行順序も等しいという性質を有している。データフローグラフ処理部３１（図１参照）が、図１５に示すＤＦＧから、所定の規則を有するノード群を探索する。
【００６０】
図１６は、図１５に示すノード群７０のＤＦＧを示す。既述したように、このノード群７０は、乗算演算の過程において用いられる。図１６に示すＤＦＧは、右１ビットシフト演算、加算演算、ｎｏｐ（信号スルー）、１とのビット積演算、１との等価比較演算とマージ演算とから構成されている。本実施の形態では、このノード群７０を、１つの新たなノード「mul_t」として置き換える。したがって、ノードmul_tは、複数の基本演算で構成されたノードとなる。図１５に示すように、被乗数２４ビット×乗数４ビットの乗算のＤＦＧには、ノードmul_tの構造を有するＤＦＧが４つ存在する。
【００６１】
なお、ノードmul_tは、１つのＡＬＵにおいて演算処理することが可能である。そのために、ＡＬＵでは、右ビットシフト演算素子、加算演算素子、ビット積演算素子、等価比較演算素子とマージ演算素子の複数の基本演算素子を、ノード群７０の配置関係を実現するように接続する組合せ用結線が設けられる。この組合せ用結線は、既存の基本演算素子を接続するだけであるため、回路規模はそれほど大きくならない。ＡＬＵが、例えば加算演算のみを実行する場合には、ＡＬＵ内のセレクタにより加算演算素子が選択されるが、ノードmul_tの演算を実行する場合には、ＡＬＵ内の組合せ用結線で必要な複数の基本演算素子をリンクすることで、ノード群７０の演算処理を実行することになる。
【００６２】
図１７は、データフローグラフ処理部３１の構成を示す。データフローグラフ処理部３１は、ノード群探索部６０、ノード置換部６１およびＤＦＧ再構成部６２を備える。実施の形態におけるデータフローグラフ処理機能は、処理装置１０において、ＣＰＵ、メモリ、メモリにロードされたＤＦＧ処理用プログラムなどによって実現され、ここではそれらの連携によって実現される機能ブロックを描いている。ＤＦＧ処理用プログラムは、処理装置１０に内蔵されていてもよく、また記録媒体に格納された形態で外部から供給されるものであってもよい。したがってこれらの機能ブロックがハードウエアのみ、ソフトウエアのみ、またはそれらの組合せによっていろいろな形で実現できることは、当業者に理解されるところである。
【００６３】
ノード群探索部６０は、コンパイル部３０により生成されたＤＦＧから、所定の規則を有するデータフローの一群、すなわち所定の規則を有するノード群７０を探索する。図１５の例では、点線で囲ったノード群に所定の規則性が認められるため、ノード群探索部６０は、４つのノード群７０をＤＦＧから見つけることになる。
【００６４】
ノード置換部６１は、探索したノード群７０を所定数のノードに置換する。置換するノードの数および段数は、ノード群７０に含まれるノード数よりも少なく、且つ、ノード群７０の段数よりも少なくすることが好ましい。上記したように、本実施の形態では、ノード置換部６１が、ノード群７０を、１つのノードmul_tに置換する。
【００６５】
図１８は、ノードの置換を行った後のＤＦＧを示す。４段にて構成されていたノード群７０（図１６参照）が、１つのノードmul_tに置き換えられている状態が示される。
【００６６】
ＤＦＧ再構成部６２は、置換されたノードmul_tを用いて、ＤＦＧを再構成する。ＤＦＧ再構成部６２は、ノード群７０に含まれるノードと同一段に位置するノードに演算が割り当てられていない場合、すなわちｎｏｐノードが割り当てられている場合に、同一段に位置するｎｏｐノードを削除する。これにより、ＤＦＧを小さく再構成することができる。さらに、ＤＦＧ再構成部６２は、ｘ入力系統の符号反転ノードの入れ替えを行い、２系統あるｘ入力系統を１系統に統合する。これにより、ＤＦＧをさらに小さく再構成することができる。
【００６７】
図１９は、ノード群７０に含まれるノードと同一段に位置するｎｏｐノードを削除したＤＦＧを示す。４段分のノード群７０を１つのノードmul_tに置換したため、被乗数であるｘ入力系統のｎｏｐノードが１つのノードmul_tにつき３段分余ることになる。図１８と比較すると、１０段分のｎｏｐノードを削除することができ、ＤＦＧを小さくすることができる。
【００６８】
図２０は、ｘ入力系統の２系統のうちの１つに存在する符号反転ノード（−１×）を、同じ系統の最後に配置されているｎｏｐノードと入れ替えた状態を示す。
【００６９】
ｘ入力系統の右側の系統の２段目にある４ビット左シフト演算を同じ系統の１段目のｎｏｐノードと入れ替えるか、または左側の系統の１段目にある４ビット左シフト演算を同じ系統の２段目のｎｏｐノードと入れ替えると、２つの系統において、符号反転ノード（−１×）より上のノードのシーケンスが全く同じになることがわかる。
【００７０】
図２１は、右側の系統の２段目にある４ビット左シフト演算を同じ系統の１段目のｎｏｐノードと入れ替えた後のＤＦＧを示す。図２１より、２系統あるｘ入力系統を１系統に統合可能であることがわかる。
【００７１】
図２２は、ｘ入力系統を１系統に統合した後のＤＦＧを示す。図２２より、ノードmul_tを使用すると被乗数２４ビット×乗数４ビットの乗算を、８段のＡＬＵ列で実行できる。図１４のＤＦＧでは２０段必要であったことと比較すると、段数は、０．４（＝８／２０）倍で済むことになる。また、図２２より、ノードの数は１５個となり、図１４のＤＦＧでは６５個必要であったことと比較すると、０．２３（＝１５／６５）倍のノード数で済む。これにより、ＤＦＧの段数を減らすことができ、リコンフィギュラブル回路１２における回路再構成回数を少なくできるとともに、回路再構成にともなう消費電力を低減することが可能となる。
【００７２】
図２３は、図２２のｙ系統の上２段分の条件処理部分をビット積演算ノードに置き換えた状態を示す。ビット積演算は、乗数ｙに対して、ビットが全て１の値を用いる。例えば、ｙ＝３の場合、図２２の条件処理部分ではｙが正数なのでＦ（false）となり「３＝0011」がマージノードから出力される。図２３のビット積演算では「（３＝0011）＆（1111）＝0011」となり、結果として図２２の条件処理部分からの出力と同じとなる。また、ｙ＝−３の場合、図１３の条件処理部分ではｙが負数なのでＴ（true）となり「１６＋（−３）＝１３＝1101」がマージノードから出力される。図２３のビット積演算では「（−３＝1101）＆（1111）＝1101」となり、結果として図２２の条件処理部分からの出力と同じとなる。ビット積演算ノードを用いることで、図２２のｙ系統の上２段分の条件処理をしているＤＦＧに比べてＤＦＧの段数を１段減らすことができる。
【００７３】
図２４は、被乗数８ビット×乗数８ビットの乗算のＤＦＧを示す。この場合は、８つのmul_tが必要となる。なお、図２３に示したＤＦＧと同様に、ｙ系統の上２段分の条件処理部分を、ビット積演算ノードに置換することは可能である。
【００７４】
図２５は、被乗数４ビット×乗数２４ビットの乗算のＤＦＧを示す。この場合は、２４個のmul_tが必要となり、また、１段目の加算で２の２４乗を加えることになる。以上のＤＦＧから、ノードmul_tは乗数の数だけ必要であることが分かる。被乗数と乗数とを入れ替えることによって、被乗数２４ビット×乗数４ビットと、被乗数４ビット×乗数２４ビットの演算結果は同じになるが、乗数のビット数が小さい方が効率的にＤＦＧを作成することができる。このように、乗数のビット数が被乗数のビット数よりも大きい場合には、乗数と被乗数とを入れ替えて、ＤＦＧを作成することが好ましい。
【００７５】
図２６は、筆算アルゴリズムの別の例を示す。図２６では、１例として４ビット（２進表示で１０１１）×４ビット（２進表示で１１１１）の乗算を示す。十進表示では１１×１５である。この例では、乗算演算を所定の桁で分割して、分割した桁ごとに並列処理を行うこととを目的とする。乗算演算を並列で処理することにより、ＤＦＧの段数を少なくすることができ、効率的な演算処理を実現することが可能となる。以下では、乗数を２進表示した場合の乗算演算を奇数桁と偶数桁に分割する。乗数ｙの奇数ビットの乗算と偶数ビットの乗算を並列に行い、最後にそれらの乗算結果を加算しても演算結果は同じとなることを利用している。
【００７６】
図２７は、偶数桁と奇数桁に分割した場合のノード群７０のＤＦＧを示す。図２７に示すＤＦＧは、右２ビットシフト演算、加算演算、ｎｏｐ（信号スルー）、１とのビット積演算、１との等価比較演算とマージ演算とから構成されている。以下では、このノード群７０を、１つの新たなノード「mul_t2」として置き換える。したがって、ノードmul_t2は、上記した複数の基本演算で構成されたノードとなる。
【００７７】
ノードmul_t2は、図１６に示すノードmul_tと同様に、１つのＡＬＵにおいて演算処理することが可能である。そのために、ＡＬＵでは、右２ビットシフト演算素子、加算演算素子、ビット積演算素子、等価比較演算素子とマージ演算素子の複数の基本演算素子を、ノードmul_t2の配置関係を実現するように接続する組合せ用結線が設けられる。この組合せ用結線は、既存の基本演算素子を接続するだけであるため、回路規模はそれほど大きくならない。ノードmul_t2の演算を実行する場合には、ＡＬＵ内の組合せ用結線で必要な複数の基本演算素子をリンクすることで、ノード群７０の演算処理を実行することになる。
【００７８】
図２８は、乗算演算をmul_tで実現したＤＦＧを示す。被乗数ｘを１０ビット、乗数ｙを１０ビットとする。ＤＦＧをmul_tで実現した場合、ノード数が３７個、段数は１９段となる。
【００７９】
図２９は、乗算演算をmul_t2で実現したＤＦＧを示す。図２８との比較のため、被乗数ｘを１０ビット、乗数ｙを１０ビットとする。ＤＦＧをmul_t2で実現した場合、ノード数が３４個、段数は１３段となる。したがって、１０ビット×１０ビットの乗算演算の場合は、mul_t2で乗算演算を実現することで、ＤＦＧの規模を小さくすることが可能となる。
【００８０】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００８１】
例えば、実施の形態では乗算演算を処理する例について説明したが、それ以外に、よく用いられる除算演算についても、同様に処理することが可能である。このように、ＤＦＧ上によく出現する演算であって、且つその演算を単独で実行する演算素子の回路規模が大きいものについては、所定の規則をもつノード群を別のノードに置換することで、ＤＦＧを小さくし、処理装置１０の処理高速性を実現することが可能である。
【００８２】
リコンフィギュラブル回路１２におけるＡＬＵの配列は、縦方向にのみ接続を許した多段配列に限らず、横方向の接続も許した、メッシュ状の配列であってもよい。また、上記の説明では、段を飛ばして論理回路を接続する接続用結線は設けられていないが、このような段を飛ばす接続用結線を設ける構成としてもよい。
【００８３】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【００８４】
【図１】実施の形態に係る処理装置の構成図である。
【図２】生成すべきターゲット回路を分割してできる複数の回路の設定データについて説明するための図である。
【図３】リコンフィギュラブル回路の一般的な構成を示す図である。
【図４】データフローグラフの構造を説明するための図である。
【図５】前後７点を利用する７タップからなるＦＩＲフィルタ回路を示す図である。
【図６】図５で示すＦＩＲフィルタ回路を置き換えた回路を示す図である。
【図７】図６で示すＦＩＲフィルタ回路をさらに置き換えた回路を示す図である。
【図８】図７に示すＦＩＲフィルタ回路をコンパイルして作成したデータフローグラフを示す図である。
【図９】リコンフィギュラブル回路の一例を示す図である。
【図１０】図８に示すデータフローグラフを、図９のリコンフィギュラブル回路を用いて実現する例を示す図である。
【図１１】ｍビットの被乗数ｘとｎビットの乗数ｙの筆算アルゴリズムのフローチャートを示す図である。
【図１２】２進数表示した４ビット×４ビットの具体的な処理動作の一例を示す図である。
【図１３】２進数表示した４ビット×４ビットの具体的な処理動作の別の例を示す図である。
【図１４】筆算アルゴリズムを用いて被乗数２４ビット×乗数４ビットの計算をするＤＦＧを示す図である。
【図１５】図１４に示すデータフローグラフにおいて、所定の規則を有するデータフローの一群を点線で囲った図である。
【図１６】図１５に示すノード群のＤＦＧを示す図である。
【図１７】データフローグラフ処理部の構成を示す図である。
【図１８】ノードの置換を行った後のＤＦＧを示す図である。
【図１９】ノード群に含まれるノードと同一段に位置するｎｏｐノードを削除したＤＦＧを示す図である。
【図２０】ｘ入力系統の２系統の１つにある符号反転ノード（−１×）を、同じ系統の最後に配置されているｎｏｐノードと入れ替えた状態を示す図である。
【図２１】右側の系の２段目にある４ビット左シフト演算を同じ系の１段目のｎｏｐノードと入れ替えた後のＤＦＧを示す図である。
【図２２】ｘ入力系統を１系統に統合した後のＤＦＧを示す図である。
【図２３】図２２のｙ系統の上２段分の条件処理部分をビット積演算ノードに置き換えた状態を示す図である。
【図２４】被乗数８ビット×乗数８ビットの乗算のＤＦＧを示す図である。
【図２５】被乗数４ビット×乗数２４ビットの乗算のＤＦＧを示す図である。
【図２６】筆算アルゴリズムの別の例を示す図である。
【図２７】偶数桁と奇数桁に分割した場合のノード群のＤＦＧを示す図である。
【図２８】乗算演算をmul_tで実現したＤＦＧを示す図である。
【図２９】乗算演算をmul_t2で実現したＤＦＧを示す図である。
【符号の説明】
【００８５】
１０・・・処理装置、１２・・・リコンフィギュラブル回路、１４・・・設定部、１８・・・制御部、２６・・・集積回路装置、３０・・・コンパイル部、３１・・・データフローグラフ処理部、３２・・・設定データ生成部、３４・・・記憶部、３６・・・プログラム、３８・・・データフローグラフ、４０・・・設定データ、５２・・・接続部、５３・・・ＡＬＵ列、６０・・・ノード群探索部、６１・・・ノード置換部、６２・・・ＤＦＧ再構成部、７０・・・ノード群。
【図１】
2005275698.tif 000003
【図２】
2005275698.tif 000004
【図３】
2005275698.tif 000005
【図４】
2005275698.tif 000006
【図５】
2005275698.tif 000007
【図６】
2005275698.tif 000008
【図７】
2005275698.tif 000009
【図８】
2005275698.tif 000010
【図９】
2005275698.tif 000011
【図１０】
2005275698.tif 000012
【図１１】
2005275698.tif 000013
【図１２】
2005275698.tif 000014
【図１３】
2005275698.tif 000015
【図１４】
2005275698.tif 000016
【図１５】
2005275698.tif 000017
【図１６】
2005275698.tif 000018
【図１７】
2005275698.tif 000019
【図１８】
2005275698.tif 000020
【図１９】
2005275698.tif 000021
【図２０】
2005275698.tif 000022
【図２１】
2005275698.tif 000023
【図２２】
2005275698.tif 000024
【図２３】
2005275698.tif 000025
【図２４】
2005275698.tif 000026
【図２５】
2005275698.tif 000027
【図２６】
2005275698.tif 000028
【図２７】
2005275698.tif 000029
【図２８】
2005275698.tif 000030
【図２９】
2005275698.tif 000031