(57)【要約】【課題】リコンフィギュラブル回路の回路面積を低減し、処理速度を平滑化したい。【解決手段】リコンフィギュラブル回路をＡＬＵアレイで構成するが、乗算器は実装しない。乗算はシフト演算に置き換え、データフローグラフを生成する。シフト数は固定とし、バレルシフタのような大きな回路の実装を回避する。シフト演算で表記された乗算をデータフローグラフに表し、対応する演算とその流れをリコンフィギュラブル回路にロードする。【選択図】        図５
2004220377.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが複数の算術論理機能を選択的に実行可能な論理回路のアレイと、
前記論理回路の間の接続関係を保持する接続部と、
を備え、前記論理回路のいずれかに、乗算器に替えてビットシフタを実装したことを特徴とするリコンフィギュラブル回路。
【請求項２】
前記ビットシフタによるシフト数を固定として構成したことを特徴とする請求項１に記載のリコンフィギュラブル回路。
【請求項３】
前記論理回路のいずれかに、減算器を実装したことを特徴とする請求項１または２に記載のリコンフィギュラブル回路。
【請求項４】
所望の乗算をミニマル表現したうえでこの乗算に相当する演算を前記ビットシフタを用いることにより前記アレイ内に構成したことを特徴とする請求項１から３のいずれかに記載のリコンフィギュラブル回路。
【請求項５】
それぞれが複数の算術論理機能を選択的に実行可能な論理回路のアレイと、前記論理回路の間の接続関係を保持する接続部とを備えたリコンフィギュラブル回路と、
前記リコンフィギュラブル回路における各論理回路の機能と論理回路間の入出力の接続関係を設定するための設定データを記憶する記憶部と、
前記記憶部から前記設定データを読み込み、前記リコンフィギュラブル回路にロードする設定部とを含み、
前記リコンフィギュラブル回路において、前記論理回路のいずれかに、乗算器に替えてビットシフタを実装したことを特徴とする集積回路装置。
【請求項６】
前記設定データは、実行すべき乗算のデータフローを表すグラフを、乗算に替えてビットシフトを用いる表現に対応するデータであることを特徴とする請求項５に記載の集積回路装置。
【請求項７】
リコンフィギュラブル回路に所期の処理を実行せしめる設定データを生成する装置であって、
前記リコンフィギュラブル回路において実行すべき乗算を、乗算を含まず、かつビットシフトを含む形式に変換するコンパイル部を備えることを特徴とするデータ変換装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、集積回路技術に関し、特にリコンフィギュラブル回路、およびそれを利用可能な集積回路装置とデータ変換装置に関する。
【０００２】
【従来の技術】
最近、携帯電話、ＧＰＳ、ＶＩＣＳなど、無線通信が広く普及し、無線機の種類も増えている。これらの無線機またはその機能をすべてハードウエアで実装すると、コストや実装面積が嵩む。そこで、ハードウエアとしては汎用的な能力を有する回路を搭載しておき、それにロードするソフトウエアを切り替えることで多様な機能を実現する「ソフトウエア無線機」という考え方がある。
【０００３】
ソフトウエア無線機を実現する回路として、ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）やＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）がある。特許文献１には、ＦＰＧＡを動的に再構成することで、回路構成の再利用を図る方法が提案されている。動的変更が可能なタイプの回路を以下リコンフィギュラブル回路ともいう。
【０００４】
【特許文献１】
特開平１０−２５６３８３号公報  （全文、第１−４図）
【０００５】
【発明が解決しようとする課題】
ＦＰＧＡをベースとすれば、論理回路の真理値表を格納するためのルックアップテーブル（ＬＵＴ）を使っていろいろな論理を実現できるが、一般には論理素子の単位が小さく、所期の機能の実現に多くのＬＵＴと配線リソースが必要となる。その結果、通常のＬＳＩと比べると、一般に実装面積が大きく、コスト高になる。また、回路を書き換えるためのプログラム時間がある程度長く、リアルタイムの機能切替に適さないことが多い。
【０００６】
本発明はこうした現状に鑑みてなされたものであり、その目的は、コスト面、書換速度面などにおいて有利なリコンフィギュラブル回路とそれを用いた集積回路装置を提供することにある。
【０００７】
【課題を解決するための手段】
本発明のある態様は、リコンフィギュラブル回路に関する。この回路は、それぞれが複数の算術論理機能を選択的に実行可能なＡＬＵその他の論理回路のアレイと、それら論理回路の間の接続関係を保持する接続部とを備え、論理回路のいずれかに、乗算器に替えてビットシフタを実装したものである。このため、乗算器に必要な回路部分を削減でき、また処理時間を削減できる。乗算自体はビットシフト演算で代替する。接続部は、論理回路の出力を他の論理回路の入力に接続するためのスイッチおよび接続用結線を有してもよく、その場合、設定により特定の接続関係にある結線を有効にすることができる。
【０００８】
この構成において、ビットシフタによるシフト数を固定としてもよい。バレルシフタのように、シフト数を可変にすると、回路規模が大きくなるので、その事態を回避する趣旨である。
【０００９】
さらに、論理回路のいずれかに、減算器を実装してもよい。その場合、乗算をビットシフトだけでなく、減算器も利用して実現でき、所望の機能の実現に要する回路規模を低減しうる。
【００１０】
また、所望の乗算をミニマル表現したうえでこの乗算に相当する演算を、前述のビットシフタを用いることによりアレイ内に構成してもよい。ミニマル表現であるから、当然それを実現する回路規模、具体的には、必要な論理回路の数を減らすことができる。
【００１１】
本発明の別の態様は、集積回路装置に関する。この装置は、それぞれが複数の算術論理機能を選択的に実行可能な論理回路のアレイと、それら論理回路の間の接続関係を保持する接続部とを備えたリコンフィギュラブル回路と、このリコンフィギュラブル回路における各論理回路の機能と論理回路間の入出力の接続関係を設定するための設定データを記憶する記憶部と、この記憶部から設定データを読み込み、リコンフィギュラブル回路にロードする設定部とを含み、リコンフィギュラブル回路において、論理回路のいずれかに、乗算器に替えてビットシフタを実装したものである。この構成により、前述のリコンフィギュラブル回路に関するメリットを集積回路装置全体で享有でき、当該装置のコストダウンや回路規模の削減が実現する。
【００１２】
なお、前述の設定データは、実行すべき乗算のデータフローを表すグラフを乗算に替えてビットシフトを用いる表現に対応するデータであってもよい。この場合、乗算をビットシフトで実現できる。
【００１３】
本発明のさらに別の態様は、リコンフィギュラブル回路に所期の処理を実行せしめる設定データを生成する装置であって、リコンフィギュラブル回路において実行すべき乗算を、乗算を含まず、かつビットシフトを含む形式に変換するコンパイル部を備える。このデータ変換装置は、リコンフィギュラブル回路が搭載される装置にオンボードで搭載されてもよいし、逆に、リコンフィギュラブル回路にロードすべき設定データをオフボードで生成するものであってもよい。なお、コンパイル部は、ミニマル表現となるよう設定データを生成してもよい。このデータ変換装置は、生成した設定データをリコンフィギュラブル回路へロードする設定部またはその制御部を備えてもよい。
【００１４】
以上いずれの場合も、論理回路のアレイは、横方向に並べられた論理回路の列が縦方向に複数段組み合わされた配列であり、横方向の論理回路間の接続用結線はなく、各段の論理回路列の出力と直後の段の論理回路列の入力との間に接続用結線が設けられた構造であってもよい。
【００１５】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムとして表現したものもまた、本発明の態様として有効である。
【００１６】
【発明の実施の形態】
実施の形態は、ＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ  Ｌｏｇｉｃ  Ｕｎｉｔ）アレイを基本素子とするリコンフィギュラブル回路に関する。このタイプの回路は、ひとつのＡＬＵがひとつの論理単位を構成し、この論理単位が複数の算術演算を選択的に実行できるため、回路構成が簡単であり、後述のデータフローグラフを直接的にマッピング可能なため、コンフィグレーションにかかる時間も節約できる。マッピングとは、リコンフィギュラブル回路で実行すべきプログラムの命令セットと、それを実現するためにリコンフィギュラブル回路内で必要な接続データセットをＡＬＵアレイにロードして設定することをいう。
【００１７】
実施の形態に特徴的なのは、ＡＬＵに内蔵すべき算術演算回路の中から、あえて乗算器を外し、乗算をシフト演算で代用せしめたことにある。一般に、ＡＬＵにおいて乗算器の占める面積は非常に大きく、すべてのＡＬＵに乗算器を内蔵するとすれば、リコンフィギュラブル回路全体の面積が非常に大きくなり、コスト面と機能面で有利ではない。また、プログラムをロードしたとき、利用されない乗算器が多数存在するであろうから、回路利用効率面でも改善の余地がある。さらに、乗算は処理時間が長く、乗算器を経由するパスによって処理が律速され、回路の全体設計が難しくなる。処理負荷を平滑化する意味でも、シフト演算は有利である。ただし、シフト演算でも、バレルシフタのように可変長のビット対応であれば、やはり回路規模が大きくなりがちである。したがって、実施の形態では、シフト数を１または２に限る。
【００１８】
乗算をシフトで代用できるためには、乗数または被乗数の少なくとも一方が定数でなければならない。そこで実施の形態では、そのような乗算を後述のコンパイル部で検出し、これを乗算器のないＡＬＵへ割り当てるものとする。変数どおしの乗算は乗算器のあるＡＬＵへ割り当てればよく、適宜、２種類のＡＬＵを組み合わせればよい。以下、乗算器のないＡＬＵとそれに対するプログラムのロードを中心に述べる。
【００１９】
図１は、実施の形態に係る集積回路装置１０および外部制御装置２４の構成図である。外部制御装置２４は、集積回路装置１０の回路構成を設定するためのデータを作成して、集積回路装置１０に供給するものであり、とくにコンパイル部２０、またはそれを含む外部制御装置２４全体は、設定データを作成するデータ変換装置として把握することができる。
【００２０】
集積回路装置１０は、リコンフィギュラブル回路１２と、リコンフィギュラブル回路１２を再構成するための設定データ１７を格納する設定データ記憶部１６と、リコンフィギュラブル回路１２に設定データ１７をロードする設定部１４とを含む。外部制御装置２４は、制御部１８と、コンパイル部２０と、プログラム記憶部２２とを含む。
【００２１】
外部制御装置２４のプログラム記憶部２２は、集積回路装置１０が実行すべき各種のプログラム１９を保持する。コンパイル部２０はプログラム記憶部２２に格納されたプログラム１９をコンパイルして、データフローグラフ２１に変換してプログラム記憶部２２に格納する。データフローグラフ２１は、後述のように、入力変数および定数の演算の流れをグラフ構造で示したものである。
【００２２】
データフローグラフ２１は、リコンフィギュラブル回路１２の回路構成にマッピングするための設定データ１７に変換され、制御部１８を介して、集積回路装置１０の設定部１４に供給され、設定データ記憶部１６に格納される。設定データ記憶部１６には、処理すべき演算のデータフローグラフ２１に対応して複数の設定データ１７があらかじめ格納される。設定部１４は、設定データ記憶部１６から適宜設定データ１７を読み出し、リコンフィギュラブル回路１２にロードすることで、リコンフィギュラブル回路１２を再構成する。再構成されたリコンフィギュラブル回路１２は、ロードされた設定データ１７にもとづいた演算を行う。
【００２３】
図２は、リコンフィギュラブル回路１２の構成図である。リコンフィギュラブル回路１２は、設定データをロードするためのデータ入力部４０と、複数のＡＬＵの列が複数段にわたって配列されたＡＬＵアレイ４２を含み、アレイの各段に設けられた接続スイッチ４４と接続結線３０によって、前段のＡＬＵ列の出力と後段のＡＬＵ列の入力が設定により任意に接続可能となっている。接続スイッチ４４によって接続結線３０が選択されるが、以降、「接続結線３０による設定」とも略記する。各ＡＬＵは、上述のごとく、少なくとも加算器、減算器、シフタを内蔵しているが、乗算器は有さない。シフタは１ビットまたは２ビットシフトに限定した構成とし、回路規模を縮小している。
【００２４】
同図のように、横方向にはＹ個、縦方向にはＸ個のＡＬＵが配置されており、第１段のＡＬＵ１１、ＡＬＵ１２、・・・、ＡＬＵ１Ｙには、入力変数や定数が入力され、設定により所定の演算がなされる。演算結果の出力は、第１段の接続結線３０に設定された接続にしたがって、第２段のＡＬＵ２１、ＡＬＵ２２、・・・、ＡＬＵ２Ｙに入力される。第１段の接続結線３０は、第１段のＡＬＵ配列の出力と第２段のＡＬＵ配列の入力の間の任意の接続関係を実現できるように結線が構成されており、設定により特定の結線が有効となる。以下、第（Ｘ−１）段の接続結線３０まで、同様の構成であり、最終段である第Ｘ段のＡＬＵ列は演算の最終結果を出力する。なお、各ＡＬＵは、後述のｍｏｖ演算を実行するために、入力をそのまま出力するパス（図示せず）を有する。
【００２５】
データフローグラフ２１をリコンフィギュラブル回路１２にマッピングするための設定データ１７には、各ＡＬＵの演算を選択する情報、ＡＬＵ列間の接続結線を選択する情報、第１段のＡＬＵ列に入力される変数と定数の値が含まれる。
【００２６】
いま、以下の実行対象プログラムを考える。
2004220377.tif 000003
図３は上記プログラムに対応するデータフローグラフを示す。図中、定数、変数および演算子は丸で囲まれ、ｍｕｌは乗算、ａｄｄは加算を示す。これをそのままリコンフィギュラブル回路１２へマッピングすると、図４の状態になる。しかし、本実施の形態では乗算器がないため、乗算をシフタで実現する。
【００２７】
ｘ＝２×ａ、ｙ＝５×ｂは、それぞれビットシフトを用いると、
ｘ＝ａ＜＜１、ｙ＝ｂ＋（ｂ＜＜２）
と表記できる。ここで、「＜＜」は左ビットシフトである。図５はこの表記に対応するデータフローグラフ、図６は図５をもとにマッピングされたリコンフィギュラブル回路１２を示す。同図において、ｍｏｖは前述のＮＯＰ演算である。データフローグラフから実際に回路をマッピングする方法は以下のとおりである。
【００２８】
１．データフローグラフの入力端に存在する変数および定数はデータ入力部４０へアサインする。
２．データフローグラフで入力端から数えてｉ番目の→の先にある演算は、第ｉ＋１段目のＡＬＵにアサインする。
３．２．の例外として、ある演算に到達する複数のパスにおける→の数がｉ、ｊのごとく違う場合、多いほうに合わせる。いま、ｉ＜ｊのとき、当該演算を第ｊ＋１段目にアサインする。
４．３．のとき、段数を合わせるために、ｉの側のパスに、ＮＯＰに相当するｍｏｖ演算を（ｊ−ｉ）個挿入する。
【００２９】
このように、本実施の形態では、まず定数×変数の形の乗算をビットシフトと加算へ変換し、これをデータフローグラフへ変換してリコンフィギュラブル回路１２へマッピングする。これにより、乗算器が存在しなくても処理時間の短いシフタで乗算が実行できる。以下、データフローグラフから回路をマッピングする方法は同様なので、以降、データフローグラフだけで説明をする。
【００３０】
つぎに、以下のプログラムの実行を考える。
2004220377.tif 000004
８×ａ＝ａ＜＜３であるから、これをデータフローグラフに表すと図７となる。しかし、３ビットシフトは本実施の形態ではひとつのＡＬＵでは実行できないため、図７のデータフローグラフを図８のごとく変換し、２ビット以下のシフト演算へ分解する。この配慮により、ＡＬＵに実装すべき命令数が減る意味でも回路規模の縮小効果がある。
【００３１】
つづいて、以下のプログラムの実行を考える。
2004220377.tif 000005
１０×ａ＝（ａ＜＜１）＋（ａ＜＜１＜＜２）であり、そのデータフローグラフは図９となる。ここで、太線で囲んだふたつの演算５０は、入力ａに対して同じ回数だけ左シフトを行うことを示しているので、図１０のようにマージし、処理を簡素化する。
【００３２】
つづいて、以下のプログラムの実行を考える。
2004220377.tif 000006
１５×ａ＝（ａ＜＜３）＋（ａ＜＜２）＋（ａ＜＜１）＋ａであり、そのデータフローグラフは図１１となる。しかしここで、二進数表現をしたときに最もゼロが多くなる、いわゆるミニマル表現をすると、１５は以下のようになる。
１５＝（１１１１）２＝（１０００Ｎ１）２
ただし、「Ｎ１」は−１を表す。したがって、上記プログラムをビットシフトで示すと、以下のとおりである。
１５×ａ＝（ａ＜＜４）−ａ
図１２はこの式に対応するデータフローグラフであり、ｓｕｂは減算を示す。このように、ミニマル表現と必要に応じて減算器を利用することにより、処理をさらに簡素化することができ、利用すべきＡＬＵを減らすことができる。
【００３３】
図１３は、以上の処理を一般化し、定数×変数の乗算をシフタによるミニマル表現の処理へ変換する手順を示す。処理は４つの段階に大別され、図１３は主に第１段階の処理を示す。
【００３４】
［第１段階］  乗算→１ビットシフタ変換
乗算ノードを１ビットシフタ、加算および符号逆転ノードへ変換する。符号逆転ノードは一時的に使用するが、第４段階で減算ノードへ変換される。一般に整数はＡ＝ｓ・ΣＮｋ−１ａｋ・２ｋと表される。ただし、ｓ＝１または−１、ａｋ＝０のたは１である。ここでは、初期値としてＡ≠０とする。以下の手順において、とくに指示がなければ直下のステップへ進む。図１３では、ＳｔｅｐをＳと略記している。
【００３５】
Ｓｔｅｐ１  以下の変数に初期値を設定する。
ｃ←０、ｃｎｔ←０、ｎ←０、ｆｌａｇ←０、ノード配列：ＮＬ←空
ｃは処理中利用するキャリービット、ｃｎｔはカウンタ、ＮＬはノードに演算を割り当てるための配列、ｎはＮＬへのポインタ、ｆｌａｇは状態フラグである。
【００３６】
Ｓｔｅｐ２  Ａ＝０かつｃ＝０ならば、処理を終了する。
Ｓｔｅｐ３  ａ０＝ｃならば、Ｓｔｅｐ１１へ進む。
Ｓｔｅｐ４  ｃｎｔ≠０ならばＳｔｅｐ６へ進む。
Ｓｔｅｐ５  ＮＬ［ｎ］に入力が変数のｍｏｖノードを作成する。また、ｎ←ｎ＋１としてＳｔｅｐ７へ進む。
【００３７】
Ｓｔｅｐ６  ＮＬ［ｎ］〜ＮＬ［ｎ＋ｃｎｔ−１］にｃｎｔ個の連続した１ビットシフタノードを作成する。ＮＬ［ｎ］の入力は変数、それ以外のノードの入力は、前のシフタノードの出力とする。また、ｎ←ｎ＋ｃｎｔとする。
Ｓｔｅｐ７  ａ１＝０かつＳ＝−１、または、ａ１≠０かつＳ＝１ならば、ＮＬ［ｎ］に符号逆転ノードを作成し、ｎ←ｎ＋１とする。
Ｓｔｅｐ８  ｆｌａｇ＝０ならばｆｌａｇ←１とし、Ｓｔｅｐ１０へ進む。
Ｓｔｅｐ９  ＮＬ［ｎ］に、ＮＬ［ｎｏｌｄ−１］の出力とＮＬ［ｎ−１］の出力を入力とする加算ノードを作成する。また、ｎ←ｎ＋１とする。
【００３８】
Ｓｔｅｐ１０  ｎｏｌｄ←ｎとする。
Ｓｔｅｐ１１  ａ０＋ａ１＋ｃ≧２ならばｃ←１とし、そうでなければ、ｃ←０とする。
Ｓｔｅｐ１２  ａ０←ａ１、ａ１←ａ２、・・・、ａＮ−１←ａＮ、ａＮ←０とし、ｃｎｔ←ｃｎｔ＋１とする。
Ｓｔｅｐ１３  Ｓｔｅｐ２へ戻る。
【００３９】
［第２段階］  同入力、同命令ノードのマージ
ｎ個のノード配列ＮＬに対して、入力が同じ値でかつ、命令が同じノードが２つ以上あれば、１つにまとめる。
【００４０】
［第３段階］  ビットシフタのマージ
連続する１ビットシフタを固定長ｎビットシフタ（ｎ≧２）へまとめる。
【００４１】
［第４段階］  減算ノードへのマージ
符号逆転ノードから加算ノードへ接続する処理を減算ノードへまとめる。加算式を式（１）のように表す。
【００４２】
ｏｕｔｐｕｔ  ＝  ｉｎｐｕｔ１  ＋  ｉｎｐｕｔ２        （１）
ｉ）加算ノードへの入力のうちの１つが符号逆転ノードの場合
ｉｎｐｕｔ１  ＝  −ｉｎｐｕｔ１’
ここで、式（１）は
2004220377.tif 000007
式（２）より、減算ノードへ変換を行う。
ｉｉ）加算ノードへの入力が共に符号逆転ノードの場合
ｉｎｐｕｔ１  ＝  −ｉｎｐｕｔ１’
ｉｎｐｕｔ２  ＝  −ｉｎｐｕｔ２’
ここで、式（１）は
2004220377.tif 000008
式（３）より、加算ノードと符号逆転ノードへ変換を行う。
【００４３】
以下に、上記の手順による乗算からシフタへの変換の実例を示す。ここでは、ａ×２３を想定する。２３は２進数表現で（１０１１１）２である。以下、煩瑣を避け、ｎの値に応じた配列ＮＬの状態を示すに留める。
【００４４】
［第１段階］  乗算→１ビットシフタ変換
ｎ＝０でスタートし、ｍｏｖノードが作成される（Ｓ５）。図１４はＮＬ［０］を示す。この後、ｎがインクリメントされる。
ｎ←１の後、符号逆転（ｎｅｇ）ノードが作成される（Ｓ７）。図１５はＮＬ［１］が追加された状態を示す。この後、
ｎ←２、ｆｌａｇ←１、Ｎｏｌｄ←２、ｃ←１、Ａ←（１０１１）２、ｃｎｔ←１
となり、シフタノードが作成される（Ｓ６）。つぎのループで、
ｎ←３、ｃ←１、Ａ←（１０１）２、ｃｎｔ←２
となり、同様にシフタノードが作成される（Ｓ６）。さらにつぎのループで、
ｎ←４、ｃ←１、Ａ←（１０）２、ｃｎｔ←３
となり、同様にシフタノードが作成される（Ｓ６）。シフタは１ビットシフタである。この時点で配列は図１６の状態になる。
【００４５】
ｎ←５とされた後、符号逆転（ｎｅｇ）ノードが作成される（Ｓ７）。この時点で、配列は図１７の状態になる。
ｎ←６の後、ａｄｄノードが作成される（Ｓ９）。配列は図１８になる。
ｎ←７の後、Ｎｏｌｄ←７、ｃ←１、Ａ←（１）２、ｃｎｔ←４となり、シフタノードが作成される（Ｓ６）。
ｎ←８の後、ｃ←１、Ａ←（０）２、ｃｎｔ←５となり、シフタノードが作成される（Ｓ６）。以下、ｎ＝９，１０，１１でも同様にシフタノードが作成される（Ｓ６）。これで配列は図１９の状態になる。
【００４６】
ｎ←１２の後、ａｄｄノードが作成される（Ｓ９）。これで配列は図２０の状態になる。この後、ｎ←１３、Ｎｏｌｄ←１３、ｃ←０、Ａ←（０）２、ｃｎｔ←６となり、処理を終える。
【００４７】
［第２段階］  同入力、同命令ノードのマージ
図２０において、ＮＬ［２］とＮＬ［７］、すなわち、ｎ＝２と７の行が同入力で同命令である。この状態を検出し、マージすると、図２１となる。さらに図２１においてＮＬ［３］とＮＬ［８］が同入力で同命令であるのでマージすると図２２が得られる。同様に繰り返しマージすると図２３の状態が得られる。以上のマージ処理もコンパイル部２０でなされる。
【００４８】
［第３段階］  ビットシフタのマージ
図２３より、連続する１ビットシフタを検出し、２ビットシフタへ置き換える。但し、シフタ２は２ビットシフタを表す。この結果、図２４の状態になる。
【００４９】
［第４段階］  減算ノードへのマージ
図２４において、ＮＬ［６］＝ＮＬ［１］＋ＮＬ［５］  ＝−ＮＬ［０］−ＮＬ［４］＝−（ＮＬ［０］＋ＮＬ［４］）であるから、ａｄｄ命令→ｎｅｇ命令へ変換すると図２５の状態となる。ここでは、ｎｅｇ命令のあるｎ＝１と５の行、すなわちＮＬ［１］とＮＬ［５］を消去するために、これらを入力とする行、すなわちＮＬ［６］を検出し、つづいてＮＬ［１］とＮＬ［５］をそれぞれそれらの入力へさかのぼり、ｎｅｇ命令を消す。
【００５０】
この後、まだｎｅｇ命令がＮＬ［７］にあるため、それを入力とするＮＬ［１２］を検出し、ＮＬ［７］を同様に入力へたどってＮＬ［６］で表す。すなわち、ＮＬ［１２］＝ＮＬ［７］＋ＮＬ［１０］＝−ＮＬ［６］＋ＮＬ［１０］＝ＮＬ［１０］−ＮＬ［６］であるから、ｎｅｇ命令は結果として減算（ｓｕｂ）命令に変換でき、図２６の状態になる。以上で処理を完了し、結果として、ａ×２３は図２７に示すデータフローグラフとなる。あとは、このデータフローグラフを回路へマッピングすればよい。
【００５１】
以上述べたリコンフィギュラブル回路１２では、基本セルとして高性能の演算能力のあるＡＬＵを用いることができ、その際コンフィグレーションは１クロックの設定動作で可能であり、設定データ１７のロードにより、瞬時に回路を再構成することができる。
【００５２】
本実施の形態では、ＡＬＵは乗算器を持たないとしたが、当然、乗算器を備えたＡＬＵと混在させてリコンフィギュラブル回路１２を構成してもよい。その場合、変数×変数タイプの乗算は乗算器で実行し、定数×変数タイプの乗算をシフト演算で実行すればよい。
【００５３】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５４】
【発明の効果】
本発明によれば、性能面で改善されたリコンフィギュラブル回路とそれを搭載する集積回路装置、およびリコンフィギュラブル回路にデータを設定するためのデータ変換装置を提供できる。
【図面の簡単な説明】
【図１】実施の形態に係る集積回路装置および外部制御装置の構成図である。
【図２】図１のリコンフィギュラブル回路の構成図である。
【図３】あるプログラムの処理を表したデータフローグラフを示す図である。
【図４】図３のデータフローグラフに対応してマッピングされたリコンフィギュラブル回路の構成図である。
【図５】別のプログラムの処理を表したデータフローグラフを示す図である。
【図６】図５のデータフローグラフに対応してマッピングされたリコンフィギュラブル回路の構成図である。
【図７】さらに別のプログラムの処理を表したデータフローグラフを示す図である。
【図８】図７のデータフローグラフを一部書き換えたデータフローグラフを示す図である。
【図９】さらに別のプログラムの処理を表したデータフローグラフを示す図である。
【図１０】図９のデータフローグラフの重複処理を統合して得られるデータフローグラフを示す図である。
【図１１】さらに別のプログラムの処理を表したデータフローグラフを示す図である。
【図１２】図１１のデータフローグラフをミニマル表現に変更して得られるデータフローグラフを示す図である。
【図１３】データフローグラフをミニマル表現に変換するための処理を示すフローチャートである。
【図１４】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図１５】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図１６】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図１７】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図１８】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図１９】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図２０】図１３のフローチャートによって、ＡＬＵに割り当てるべき演算を示す配列が形成される途中状態を示す図である。
【図２１】図２０において、同入力、同命令ノードをマージして得られる配列を示す図である。
【図２２】図２１において、同入力、同命令ノードをマージして得られる配列を示す図である。
【図２３】図２２において、同入力、同命令ノードをマージして得られる配列を示す図である。
【図２４】図２３において、ビットシフタのマージをマージして得られる配列を示す図である。
【図２５】図２４において、ｎｅｇノードを消去する途上の配列を示す図である。
【図２６】図２５において、ｎｅｇノードを消去した結果得られた配列を示す図である。
【図２７】ａ×２３をミニマル表現するデータフローグラフを示す図である。
【符号の説明】
１０  集積回路装置、  １２  リコンフィギュラブル回路、  １４  設定部、１６  設定データ記憶部、  １７  設定データ、  １８  制御部、  １９  プログラム、  ２０  コンパイル部、  ２１  データフローグラフ、  ２２  プログラム記憶部、２４  外部制御装置、３０  接続結線、  ４０  データ入力部、４２  ＡＬＵアレイ、  ４４  接続スイッチ。
【図１】
2004220377.tif 000009
【図２】
2004220377.tif 000010
【図３】
2004220377.tif 000011
【図４】
2004220377.tif 000012
【図５】
2004220377.tif 000013
【図６】
2004220377.tif 000014
【図７】
2004220377.tif 000015
【図８】
2004220377.tif 000016
【図９】
2004220377.tif 000017
【図１０】
2004220377.tif 000018
【図１１】
2004220377.tif 000019
【図１２】
2004220377.tif 000020
【図１３】
2004220377.tif 000021
【図１４】
2004220377.tif 000022
【図１５】
2004220377.tif 000023
【図１６】
2004220377.tif 000024
【図１７】
2004220377.tif 000025
【図１８】
2004220377.tif 000026
【図１９】
2004220377.tif 000027
【図２０】
2004220377.tif 000028
【図２１】
2004220377.tif 000029
【図２２】
2004220377.tif 000030
【図２３】
2004220377.tif 000031
【図２４】
2004220377.tif 000032
【図２５】
2004220377.tif 000033
【図２６】
2004220377.tif 000034
【図２７】
2004220377.tif 000035