(57)【特許請求の範囲】
【請求項１】
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能をマッピングする演算マッピング方法であって、
前記所期の演算機能の入力の有効ビット数を指定するビット数指定手段に基づいて、前記所期の演算機能の入力の有効ビット数を判定する有効ビット数判定ステップと、
前記有効ビット数判定ステップで判定された有効ビット数に基づいて、前記所期の演算機能を前記リコンフィギュラブル回路にマッピングするマッピングステップと、
を備えることを特徴とする演算マッピング方法。
【請求項２】
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能をマッピングする演算マッピング方法であって、
前記所期の演算機能の入力の符号を指定する符号指定手段に基づいて、前記所期の演算機能の入力の符号を判定する符号判定ステップと、
前記符号判定ステップで判定された符号に基づいて、前記所期の演算機能を前記リコンフィギュラブル回路にマッピングするマッピングステップと、
を備えることを特徴とする演算マッピング方法。
【請求項３】
前記所期の演算機能は、除算又は剰余算を含み、
前記マッピングステップは、前記除算又は剰余算を、前記除算又は剰余算の被除数の有効ビット数分の減算の繰り返しを含む処理にマッピングする、
ことを特徴とする請求項１に記載の演算マッピング方法。
【請求項４】
前記所期の演算機能の入力の有効ビット数を指定するビット数指定手段は、前記所期の演算機能をプログラム言語で表現したソースプログラムであることを特徴とする請求項１又は３に記載の演算マッピング方法。
【請求項５】
前記有効ビット数判定ステップは、前記ソースプログラムのコメントの記載に基づいて、入力の有効ビット数を判定することを特徴とする請求項４に記載の演算マッピング方法。
【請求項６】
前記所期の演算機能の入力の符号を指定する符号指定手段は、前記所期の演算機能をプログラム言語で表現したソースプログラムであることを特徴とする請求項２に記載の演算マッピング方法。
【請求項７】
前記符号判定ステップは、前記ソースプログラムのコメントの記載に基づいて、入力の符号を判定することを特徴とする請求項６に記載の演算マッピング方法。
【請求項８】
請求項１乃至７のいずれかに記載の演算マッピング方法の結果から得られたデータにしたがって動作することを特徴とするリコンフィギュラブル回路。
【請求項９】
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能の動作を設定するために必要なデータフローグラフであって、
前記所期の演算機能が、該演算の入力のビット数に応じた繰り返し演算に分解される場合に、前記所期の演算機能をプログラム言語で表現したソースプログラムに基づいて判定される、前記所期の演算機能の入力の有効ビット数に対応して、前記繰り返し演算の繰り
返し回数を削減したことを特徴とするデータフローグラフ。
【請求項１０】
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能の動作を設定するために必要なデータフローグラフであって、
前記所期の演算機能の入力の符号が正負いずれの場合にも対応して処理されるように、前記所期の演算機能が前記入力の符号判定処理を含む場合に、前記所期の演算機能をプログラム言語で表現したソースプログラムに基づいて判定される、前記所期の演算機能の入力の符号に対応して、前記符号判定処理を省略したことを特徴とするデータフローグラフ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リコンフィギュラブル回路への演算マッピング方法、リコンフィギュラブル回路、及びリコンフィギュラブル回路の動作を設定するために必要なデータフローグラフに関する。
【背景技術】
【０００２】
最近、携帯電話、ＧＰＳ、ＶＩＣＳなど、無線通信が広く普及し、無線機の種類も増えている。これらの無線機またはその機能をすべてハードウエアで実装すると、コストや実装面積が嵩む。そこで、ハードウエアとしては汎用的な能力を有する回路を搭載しておき、それにロードするソフトウエアを切り替えることで多様な機能を実現する「ソフトウエア無線機」という考え方がある。
【０００３】
ソフトウエア無線機を実現する回路として、ＦＰＧＡ（Field Programmable Gate Array）やＤＳＰ（Digital Signal Processor）がある。特許文献１には、ＦＰＧＡを動的に
再構成することで、回路構成の再利用を図る方法が提案されている。動的変更が可能なタイプの回路を以下リコンフィギュラブル回路という。
【０００４】
ＦＰＧＡはＬＳＩ製造後に回路データを書き込んで比較的自由に回路構成を設計することが可能であり、専用ハードウェアの設計に利用されている。ＦＰＧＡは、論理回路の真理値表を格納するためのルックアップテーブル（ＬＵＴ）と出力用のフリップフロップからなる基本セルと、その基本セル間を結ぶプログラマブルな配線リソースとを含む。ＦＰＧＡでは、ＬＵＴに格納するデータと配線データを書き込むことで目的とする論理演算を実現できる。しかし、ＦＰＧＡでＬＳＩを設計した場合、ＡＳＩＣ（Application Specific IC）による設計と比べると、実装面積が非常に大きくなり、コスト高になる。そこで
、ＦＰＧＡを動的に構成することによって、回路構成の再利用を計る方法が提案されている（例えば、特許文献１参照）。 
【特許文献１】特開平１０−２５６３８３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
例えば衛星放送では、季節などにより、放送モードを切り替えて画質の調整などを行うことがある。衛星放送受信機では、放送モードごとに複数の回路を予めハードウェア上に作り込んでおき、放送モードに合わせて選択器で回路を切り替えて受信している。従って、受信機の他の放送モード用の回路はその間遊んでいることになる。モード切替のように、複数の専用回路を切り替えて使用し、その切替間隔が比較的長い場合、複数の専用回路を作り込む代わりに、切替時にＬＳＩを瞬時に再構成することにすれば、回路構造を簡単にして汎用性を高め同時に実装コストを抑えることができる。このようなニーズに応えるべく、動的に再構成可能なＬＳＩに製造業界の関心が高まってきている。特に、携帯電話やＰＤＡ（Personal Digital Assistant）などのモバイル端末に搭載されるＬＳＩは小型化が必要であり、ＬＳＩを動的に再構成し、用途に合わせて適宜機能を切り替えることができれば、ＬＳＩの実装面積を小さく抑えることができる。
【０００６】
ＦＰＧＡは回路構成の設計自由度が高く、汎用的である反面、全ての基本セル間の接続を可能とするため、多数のスイッチとスイッチのＯＮ／ＯＦＦを制御するための制御回路を含む必要があり、必然的に制御回路の実装面積が大きくなる。また、基本セル間の接続に複雑な配線パターンをとるため、配線が長くなる傾向がある。さらに１本の配線に多く
のスイッチが接続される構造であるため、遅延が大きくなる。そのため、ＦＰＧＡによるＬＳＩは、試作や実験のために利用されるにとどまることが多く、実装効率、性能コストなどを考えると、量産には適していない。さらに、ＦＰＧＡによるＬＳＩでは、多数のＬＵＴ方式の基本セルに設定データを送る必要があるため、回路のコンフィギュレーションにはかなりの時間を要する。そのため、瞬時に回路構成の切替が必要な用途にはＦＰＧＡによるＬＳＩは適していない。
【０００７】
それらの課題を解決するため、近年、ＡＬＵ（Arithmetic Logic Unit）と呼ばれる基
本演算機能を複数有する多機能素子を用いたリコンフィギュラブルプロセッサの開発が進められている。リコンフィギュラブルプロセッサでは、コマンドデータが設定されることにより、ＡＬＵ回路の演算機能構成と接続部が制御され、全体として所期の演算処理回路を実現することが可能となる。コマンドデータは、一般にＣ言語等の高級プログラム言語で記述されたソースプログラムからＤＦＧ（Data Flow Graph）と呼ばれるデータフロー
を作成し、その情報をもとに作成される。
【０００８】
しかし、従来のデータフロー作成方法では、演算を汎用に行うことを想定しており、１つの演算が必要とするＡＬＵの数が多く、回路規模が大きくなり、それだけ回路の処理時間が長くなるという問題があった。
【０００９】
本発明はこうした状況に鑑みてなされたものであり、リコンフィギュラブル回路において、回路規模の縮小化と処理時間の短縮化等に貢献するリコンフィギュラブル回路への演算マッピング方法と、それを利用したリコンフィギュラブル回路を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明の第１の観点に係るリコンフィギュラブル回路への演算マッピング方法は、
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能をマッピングする演算マッピング方法であって、
前記所期の演算機能の入力の有効ビット数を指定するビット数指定手段に基づいて、前記所期の演算機能の入力の有効ビット数を判定する有効ビット数判定ステップと、
前記有効ビット数判定ステップで判定された有効ビット数に基づいて、前記所期の演算機能を前記リコンフィギュラブル回路にマッピングするマッピングステップと、
を備えることを特徴とする。
【００１１】
本発明の第２の観点に係るリコンフィギュラブル回路への演算マッピング方法は、
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能をマッピングする演算マッピング方法であって、
前記所期の演算機能の入力の符号を指定する符号指定手段に基づいて、前記所期の演算機能の入力の符号を判定する符号判定ステップと、
前記符号判定ステップで判定された符号に基づいて、前記所期の演算機能を前記リコンフィギュラブル回路にマッピングするマッピングステップと、
を備えることを特徴とする。
【００１２】
好ましくは、前記所期の演算機能の入力の有効ビット数を指定するビット数指定手段及び入力の符号を指定する符号指定手段に基づいて、前記所期の演算機能の入力の有効ビット数を判定する有効ビット数判定ステップと、前記所期の演算機能の入力の符号を判定する符号判定ステップとを備え、
前記マッピングステップは、前記有効ビット数判定ステップで判定された有効ビット数及び前記符号判定ステップで判定された符号に基づいて、前記所期の演算機能を前記リコンフィギュラブル回路にマッピングする、
ことを特徴とする。
【００１３】
特に、前記所期の演算機能は、除算又は剰余算を含み、
前記マッピングステップは、前記除算又は剰余算を、前記除算又は剰余算の被除数の有効ビット数分の減算の繰り返しを含む処理にマッピングする、
ことを特徴とする。
【００１４】
好ましくは、前記所期の演算機能の入力の有効ビット数を指定するビット数指定手段は、前記所期の演算機能をプログラム言語で表現したソースプログラムである。
【００１５】
なお、前記有効ビット数判定ステップは、前記ソースプログラムのコメントの記載に基づいて、入力の有効ビット数を判定することを特徴とする。
【００１６】
好ましくは、前記所期の演算機能の入力の符号を指定する符号指定手段は、前記所期の演算機能をプログラム言語で表現したソースプログラムである。
【００１７】
なお、前記符号判定ステップは、前記ソースプログラムのコメントの記載に基づいて、入力の符号を判定することを特徴とする。
【００１８】
本発明の第３の観点に係るリコンフィギュラブル回路は、
前記第１の観点に係るいずれかのリコンフィギュラブル回路への演算マッピング方法、又は前記第２の観点に係るいずれかのリコンフィギュラブル回路への演算マッピング方法の結果から得られたデータにしたがって動作することを特徴とする。
【００１９】
本発明の第４の観点に係るデータフローグラフは、
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能の動作を設定するために必要なデータフローグラフであって、
前記所期の演算機能が、該演算の入力のビット数に応じた繰り返し演算に分解される場合に、前記所期の演算機能をプログラム言語で表現したソースプログラムに基づいて判定される、前記所期の演算機能の入力の有効ビット数に対応して、前記繰り返し演算の繰り返し回数を削減したことを特徴とする。
【００２０】
本発明の第５の観点に係るデータフローグラフは、
それぞれが複数の算術論理演算機能を選択的に実行可能な複数の論理回路から構成される演算部と、前記複数の論理回路の間の接続関係を保持する接続部と、を備えるリコンフィギュラブル回路に、所期の演算機能の動作を設定するために必要なデータフローグラフであって、
前記所期の演算機能の入力の符号が正負いずれの場合にも対応して処理されるように、前記所期の演算機能が前記入力の符号判定処理を含む場合に、
前記所期の演算機能をプログラム言語で表現したソースプログラムに基づいて判定される、前記所期の演算機能の入力の符号に対応して、前記符号判定処理を省略したことを特徴とする。
【発明の効果】
【００２１】
本発明のリコンフィギュラブル回路への演算マッピング方法によれば、従来、演算を汎
用の処理にマッピングしていたために無効になっていた演算回路を削減することができるため、同じ演算処理を行う回路規模を小型化でき、消費電力を削減するとともに、演算処理を高速化することができる。
【発明を実施するための最良の形態】
【００２２】
本発明に係るリコンフィギュラブル回路への演算マッピング方法と、リコンフィギュラブル回路の一実施の形態について、図を参照して説明する。図１は、本発明の一実施の形態に係るリコンフィギュラブル回路を含む処理装置の構成を示すブロック図である。図１に示すように、処理装置１０は、集積回路装置２６を備える。集積回路装置２６は、回路構成を再構成可能とする機能を有する。集積回路装置２６は１チップとして構成され、リコンフィギュラブル回路１、設定部１４、制御部１８、内部状態保持回路２０、出力回路２２および経路部２４を備える。リコンフィギュラブル回路１は、設定を変更することにより、機能の変更を可能とする。
【００２３】
設定部１４は、第１設定部１４ａ、第２設定部１４ｂ、第３設定部１４ｃ、第４設定部１４ｄおよび選択器１６を有し、リコンフィギュラブル回路１に所期の回路を構成するための設定データ４０を供給する。経路部２４は、フィードバックパスとして機能し、リコンフィギュラブル回路１の出力を、リコンフィギュラブル回路１の入力に接続する。内部状態保持回路２０および出力回路２２は、例えばデータフリップフロップ（Ｄ−ＦＦ）などの順序回路あるいはメモリで構成され、リコンフィギュラブル回路１の出力を受ける。内部状態保持回路２０は経路部２４に接続されている。リコンフィギュラブル回路１は組合せ回路、またはＤ−ＦＦのような状態保持を含む順序回路として構成される。
【００２４】
図２は、ＡＬＵアレイを用いたリコンフィギュラブル回路１の構成例を示す図である。図２に示すように、リコンフィギュラブル回路１は、機能の変更が可能なＡＬＵ（算術論理演算ユニット）などを含む演算部である論理回路２の集合体を複数備えた構造を有し、また、それぞれの集合体の間に設けられて、集合体間の論理回路２の接続を選択的に確立可能な少なくとも１つの接続部３を有する。
【００２５】
リコンフィギュラブル回路１において、演算機能を選択的に実行可能な複数の論理回路２がマトリックス状に配列されて、図２の例では、Ｘ段Ｙ列のＡＬＵアレイを構成し、各段に配列された複数の論理回路２が集合体を構成して、前段の集合体における処理結果が、接続部３において選択的に確立される接続にしたがって後段の集合体に引き渡される。上段から下段への論理回路間のデータ渡しは、論理回路間の接続切替を行う接続スイッチに接続データセットを設定することで、下段のどの論理回路２にデータを渡すかが定められる。動作時には、構成情報に従って演算処理し、結果を出力する。
【００２６】
各論理回路２の機能と、論理回路２間の接続関係は、図１に示す設定部１４により供給される設定データ４０に基づいて設定される。設定データ４０は、以下の手順で生成される。
【００２７】
集積回路装置２６により実現されるべき演算機能を記載したソースプログラム３６が、記憶部３４に保持されている。ソースプログラム３６は、信号処理回路または信号処理アルゴリズムなどをＣ言語などの高級言語で記述したものである。コンパイル部３０は、記憶部３４に格納されたソースプログラム３６をコンパイルし、データフローグラフ（ＤＦＧ）３８に変換して記憶部３４に格納する。データフローグラフ３８は、入力変数および定数による入力データから出力データに至る演算ないしはデータの流れをグラフ構造で表現したものである。ここで、コンパイル部３０は、リコンフィギュラブル回路１における論理回路２の集合体の接続制限に応じて、データフローグラフ３８を生成する。
【００２８】
設定データ生成部３２は、データフローグラフ３８から設定データ４０を生成する。設定データ４０は、データフローグラフ３８をリコンフィギュラブル回路１にマッピングするためのデータであり、リコンフィギュラブル回路１における論理回路２の機能や論理回路間の接続関係を定める。
【００２９】
リコンフィギュラブル回路１は、論理回路２をマトリクス状に配列した汎用のプロセッサと見ることができる。データフローグラフ３８及び設定データ４０は、プロセッサに指令するプログラム等の一種に相当すると考えられる。
【００３０】
（実施の形態１）
実施の形態１では、除算を例にとって、本発明のリコンフィギュラブル回路１への演算マッピング方法を説明する。図３は、実施の形態に係るマッピング方法の例として、除算のソースプログラム３６の一例を示す。
【００３１】
除算を論理演算回路で実現する一つの方法として、論理回路に除算機能を組み込み、除算命令を論理回路に与えて除算を行う方法がある。しかし、除算は回路規模が大きく、例えば、全ての論理回路に除算機能を備えると回路規模が膨大となるとともに、一つの演算手段の信号遅延が大きくなり、結果としてリコンフィギュラブル回路全体の回路規模の増大と、演算速度の低下につながる。
【００３２】
これを解決する方法として、除算をいわゆる筆算の計算方法に分解し、一つの論理回路には簡単な命令のみ持たせて除算を実現する方法がある。但し、この場合は必要な論理回路の段数が多くなる。また、筆算の計算方法による除算の規則性を利用して、一定パターンの演算を一つの演算手段に割り当てる方法が考えられる。
【００３３】
図４は、多段の減算で構成する筆算の演算方法に除算を分解したときの、減算一段の処理を表すデータグラフの例である。図４等においては、データフローグラフ３８を視覚的に理解しやすいように、丸や四角及びその中の記号と矢印線を用いて図面として表しているが、処理装置１０の内部では、データフローグラフ３８は、論理回路２を表すノードの番号とその演算処理内容、及びノード間の入出力関係などを示すデータ形式で表現される。
【００３４】
図４（ａ）において、入力Ｐで表される変数ｘは被除数であり、入力Ｑで表される変数ｙは除数である。変数ｘ及びｙは２進数表示の整数であり、２の補数で表現されている。変数ｘ及びｙは正数であることが条件となっている。また、出力Ｒで表される変数ｒｅｔは減算一段の処理結果であり、次の減算一段の被除数となる数と、最下位ビットに、この桁の除算結果が記録される。
【００３５】
除算を構成する減算一段は次のように行われる。まず、被除数ｘを１ビット左にシフトする（ステップＡ１）。１ビットシフトした被除数から除数ｙを減算する（ステップＡ２）。減算した結果に１（入力Ａ７）を加える（ステップＡ５）。その間に、１ビット左にシフトした被除数はそのまま保持される（ステップＡ３、ステップＡ４）。ｍｏｖ命令は、入力をそのまま出力に伝える演算（保持回路）である。
【００３６】
ステップＡ２の結果はまた、ステップＡ６に入力される。ステップＡ６では、「０」（入力Ａ８）より大きいかどうかを判断する。ステップＡ２の結果が正であればステップＡ６の結果は真であり、ステップＡ２の結果が正でなければステップＡ６の結果は偽である。ステップＡ６の出力の破線は、その値が真理値であることを表す。
【００３７】
ステップＡ９の「ｍｅｒｇｅ」は、破線入力の真偽に応じて、２つの実線入力のいずれ
かを選択する論理演算を表す。破線入力が真の場合は、実線入力のうちＴで示される入力を選択する。
【００３８】
ステップＡ９では、ステップＡ６の結果によって、ステップＡ４の結果かステップＡ５の結果を選択する。ステップＡ６の結果が真であれば、ステップＡ５の結果、すなわち１ビットシフトした被除数から除数ｙを減算して１を加えた数を選択する。ステップＡ６の結果が偽であれば、ステップＡ４の結果、すなわち１ビットシフトした被除数を選択する。
【００３９】
被除数を１ビット左にシフトした値から除数を減算した結果が正であれば（除数を引くことができれば）、最下位ビットに１が記録され、その上位ビットには除数を減算した結果が残っている。被除数を１ビット左にシフトした値から除数を減算した結果が正でなければ、１ビット左にシフトした被除数が出力Ｒとなり、最下位ビットは０である。したがって、出力Ｒの最下位ビットがその段の商であり、上位ビットには次の段の被除数が残っており、図４（ａ）は筆算の演算方法に除算を分解したときの、減算一段の処理を表している。
【００４０】
図４（ｂ）は、図４（ａ）の処理をまとめてｄｉｖ＿ｘ（ステップＢ１）で表すことを示す。ｄｉｖ＿ｘは図４（ａ）のステップＡ１〜Ａ９に分解されることを表す。
【００４１】
図３にもどって、このソースプログラム３６の１行目は、コメント欄である。２行目は、被除数ｘを除数ｙで除した商を、変数ｒｅｔに代入することを表す。１行目のコメントは、２行目の除算において、被除数が正で有効ビット数が５であり、除数が負で有効ビット数が６であることを表す。
【００４２】
図３は、除算における被除数と除数の有効ビット数及び符号を表す例である。ソースプログラム３６において、被除数と除数の有効ビット数及び符号をどのように表すかは任意である。例えば、変数の型宣言文の変数の後に／と符号つき整数を追加することによって、変数の有効ビット数と符号を表現することができる。
【００４３】
処理装置１０のコンパイル部３０は、例えば図３に示すソースプログラム３６のコメント欄に記載された情報を読み取って、除算における被除数と除数の有効ビット数及び符号を判断する。そして、被除数と除数の有効ビット数及び符号に応じたデータフローグラフ（ＤＦＧ）３８を生成する。
【００４４】
その他、コンパイル部３０は、例えば前述の変数の型宣言文の変数の後に追加された情報を読み取って、除算における被除数と除数の有効ビット数及び符号を判断してもよい。また、コンパイル部３０がソースプログラム３６をコンパイルするときに、有効ビット数又は符号によってデータフローグラフ３８の構成が変わる可能性のある変数について、その変数の有効ビット数又は符号の情報をオペレータに入力させ、入力された情報に基づいてその変数の有効ビット数又は符号を判断するように構成してもよい。あるいは、その変数の有効ビット数又は符号の情報を、ソースプログラム３６とは別のファイルから読み込むように構成することもできる。その場合、ファイルから読み込む変数の有効ビット数又は符号の情報は、コンパイル部３０に与える指示の一種で、広い意味でソースプログラム３６の一部とも考えられる。
【００４５】
図５は、除算における被除数の有効ビット数を考慮して、除算の処理を展開したフローチャートである。図５において、ｘ＿ＢＩＴが被除数ｘの有効ビット数を表す。図５のフローチャートの各変数は、図３のソースプログラム３６に対応している。図６は、図５のフローチャートにおける変数の内容の例を示す。図６では、例として被除数を２９、除数
を−５としている。図６のステップは、図５のステップ（Ｃ１等）に対応している。また、十進数であることを示すｄを付した数以外は二進数表示である。図６では、被除数ｘと除数ｙは８ビットである。内部変数＄ｘ及び＄ｙは１６ビットであるが、図６では上位のビットを省略して記載している。
【００４６】
入力である被除数ｘと除数ｙを倍精度の変数＄ｘ及び＄ｙに代入し、商の符号を定める変数＄ｓｉｇｎをまず１（正）とする（ステップＣ１）。図６の例では、＄ｘが１１１０１（十進数の２９）、＄ｙが１１１１１０１１（十進数の−５）である。被除数ｘが正であるか否かを判定し（ステップＣ２）、被除数ｘが正でなければ（ステップＣ２；Ｎｏ）、＄ｘを−ｘにし（すなわち正に反転し）、商の符号＄ｓｉｇｎを−１（負）に設定する（ステップＣ３）。被除数が正であれば（ステップＣ２；Ｙｅｓ）、ステップＣ１の設定のままである。図６の例では、ｘが正なのでステップＣ３は実行されない。
【００４７】
次に、除数ｙが正であるか否かを判定し（ステップＣ４）、除数ｙが正でなければ（ステップＣ４；Ｎｏ）、＄ｙを−ｙ（すなわち正に反転）し、商の符号＄ｓｉｇｎを反転する（ステップＣ５）。図６の例では、ｙが十進数の−５なので、＄ｙは１０１（十進数の５）となり、＄ｓｉｇｎは−１となる。ステップＣ３で＄ｓｉｇｎを負にしている場合は、被除数及び除数が負であるから商は正であり、＄ｓｉｇｎを正（＋１）とする。除数が正であれば（ステップＣ４；Ｙｅｓ）、＄ｙ及び＄ｓｉｇｎの符号反転は行わない。
【００４８】
次に、変数＄ｘを１ビット左にシフトし、商の符号＄ｓｉｇｎが負ならば、１を加える（ステップＣ６）。これは、最終的に変数＄ｘの下位ビットにセットされる商と被除数（の余り）とを隔てる１ビットを空けて、そのビットに商の符号を設定するものである。図６では、商と被除数（の余り）とを隔てる１ビットをＳで表す。商が正の場合はＳは０であり、商が負の場合はＳは１に設定される。図６の例では、商は負なのでＳは１である。図６では、見やすいようにＳのまま表示している。
【００４９】
ついで、変数＄ｘと桁を合わせるために、変数＄ｙを被除数ｘの有効ビット数＋１ビットだけ左にシフトする（ステップＣ７）。図６の例ではｘの有効ビット数が５なので、＄ｙは６ビット左にシフトされて、０１０１００００００となる。
【００５０】
次に、ステップＣ９を被除数ｘの有効ビット数だけ繰り返す（ステップＣ８、Ｃ９、Ｃ１０）。ステップＣ９は、＄ｘを被除数、＄ｙを除数として、図４（ｂ）に示すｄｉｖ＿ｘの処理を行う。図６の例では、ｄｉｖ＿ｘの処理を５回繰り返す。図６のステップＣ８、Ｃ９、Ｃ１０の（１）〜（５）に、各回のステップＣ９の処理における＄ｘの結果が示されている。各欄の上段は、ｄｉｖ＿ｘの入力＄ｘを１ビット左にシフトした状態を示す。各欄の下段は、除数＄ｙを引いて、１を加えた結果を示す。下段の空欄は、＄ｙを引いた結果が正でないことを示す。その場合は、ｄｉｖ＿ｘの入力＄ｘを１ビット左にシフトした値がそのまま、次の回の処理に渡される。
【００５１】
ｄｉｖ＿ｘ（ステップＣ９）の１回目と２回目では、＄ｘは＄ｙより小さいので、それぞれ１ビット左にシフトされた＄ｘがそのまま、次の処理に渡される。３回目では、＄ｘは＄ｙより大きくなり、＄ｙを減算した残りに１を加えた値が次の処理に渡される。４回目では、＄ｘは＄ｙより小さく、＄ｘは１ビット左にシフトされただけとなる。５回目では、＄ｘは＄ｙより大きくなり、＄ｙを減算した残りに１を加えた値が出力される。ｄｉｖ＿ｘを５回繰り返した結果、＄ｘの下位５ビット（Ｓの右）は００１０１となり、商の絶対値（２９／５＝５）となっている。なお、記号Ｓの左側には除算の余りが示されている。
【００５２】
＄ｘから除算の商だけを取り出すために、２x_BIT−１とビットごとの論理積（＆）を
とって変数ｒｅｔに代入する（ステップＣ１１）。変数ｒｅｔは、被除数ｘ及び除数ｙと同じ精度（図６の例では８ビット）である。図６の例ではｘ＿ＢＩＴは５なので、２５−１（十進）＝１１１１１（二進）となって、＄ｘの下位５ビット（００１０１）を取り出すことになる。
【００５３】
また、＄ｘに設定した商の符号を取り出して、＄ｓｉｇｎとする（ステップＣ１１）。Ｓのビット位置は、下位からｘ＿ＢＩＴ＋１ビット目になっているので、＄ｘと２x_BIT
との論理和をとれば、商の符号を表すビットを取り出すことができる。
【００５４】
最後に、商の符号＄ｓｉｇｎが０でない（商が負である）場合は（ステップＣ１２；Ｎｏ）、変数ｒｅｔの符号を反転する（ステップＣ１３）。＄ｓｉｇｎが０の（商が正である）場合は（ステップＣ１２；Ｙｅｓ）、商ｒｅｔの符号は反転しない。図６の例では、＄ｓｉｇｎは１なので、ｒｅｔは符号反転されて１１１１１０１１（十進数の−５）となる。
【００５５】
以上、説明したように、被除数の有効ビット数を考慮すると、除算を筆算に分解した減算処理の繰り返し数を、有効ビット数分だけに削減することができる。有効ビット数を考慮しない場合には、例えば被除数及び除数が８ビットとすると、除数を８ビットシフトして、最大の７回の減算処理を繰り返す必要がある（最上位ビットは符号を表すので、最大有効ビットは７である）。
【００５６】
図６の例では、理解を容易にするため、被除数及び除数を８ビットとしたが、例えば、被除数が１６ビットあるいは３２ビットの場合には、減算の繰り返し数が最大１７又は３１となって、有効ビット数を考慮した場合との減算繰り返し数の差が大きく、演算を実効する回路規模と処理時間の差が大きいものとなる。
【００５７】
図７は、図５のフローチャートで表される処理を、図３の例に適用した場合のデータフローグラフ３８の例を示す。図７において、入力Ｐ、Ｐ１、Ｐ２は被除数ｘを表す。入力Ｑ、Ｑ１、Ｑ２は除数ｙを表す。出力Ｒは除算の商ｒｅｔを表す。処理の途中の定数や、一時記憶なども、演算と同じＤを付した番号で示す。以下、定数等も含めてステップと呼ぶ。
【００５８】
図７のステップＤ１〜Ｄ１１は、商の符号（図５では＄ｓｉｇｎ）を決定する処理を表す。入力Ｐ２（被除数ｘ）の符号判定（ステップＤ３、Ｄ４）の結果に応じて、１（ステップＤ５）か−１（ステップＤ１、Ｄ２）を選択する（ステップＤ６）。そして、入力Ｑ２（除数ｙ）の符号判定（ステップＤ９、Ｄ１０）の結果に応じて、ステップＤ６の結果（ステップＤ８）か、その符号反転（ステップＤ７）を選択する（ステップＤ１１）。ステップＤ１１の結果は、入力Ｐ２及びＱ２が同符号の場合は１、異符号（又はいずれかが０）の場合は−１となる。
【００５９】
ステップＤ１２〜Ｄ１４は、被除数を正にする処理である。入力Ｐ２の符号判定（ステップＤ３、Ｄ４）の結果（ステップＤ１２）に応じて、入力Ｐ又は入力Ｐ１の符号反転（ステップＤ１３）を選択する（ステップＤ１４）。
【００６０】
ステップＤ１５、Ｄ１６（及びＤ１０）は、除数を正にする処理である。入力Ｑ２の符号判定（ステップＤ１０）の結果に応じて、入力Ｑ又は入力Ｑ１の符号反転（ステップＤ１５）を選択する（ステップＤ１６）。
【００６１】
ステップＤ１７〜Ｄ２３は、被除数を１ビット左にシフトして、最下位ビットに商の符号を設定する処理である。正数にされた被除数を１ビット左にシフトする（ステップＤ１
７）。＄ｓｉｇｎが１の場合は（ステップＤ１８、Ｄ１９；真）、その数を選択する（ステップＤ２３；Ｔ）。＄ｓｉｇｎが−１の場合は（ステップＤ１９；偽）、ステップＤ１７の結果に１を加えた（最下位ビットを１にした）数（ステップＤ２１）を選択する（ステップＤ２３）。ここでは、図６のＳで表される符号は、商が正の場合は０、商が負の場合は１に設定される。
【００６２】
その間に、除数を被除数の有効ビット数＋１ビットだけ左にシフトする（ステップＤ２４、Ｄ２５）。図３の例では、被除数の有効ビット数が５であるから、６ビット左にシフトする。図７では、４ビット左シフト（ステップＤ２４）と、２ビット左シフト（ステップＤ２５）の２ステップで行っている。これは、シフトビット数が２のべき乗であるという論理回路の特性によるものである。
【００６３】
そして、ｄｉｖ＿ｘの処理を被除数の有効ビット数分繰り返し実行する（ステップＤ２６〜Ｄ３５）。ステップＤ２５の結果を一旦Ｂ（ステップＤ２８）に出力し、ステップＤ３４の入力Ｂ（ステップＤ３５）としているが、ステップＤ３２の下にもう一段ｍｏｖ演算を加えた構成でもよく、除算の結果は同じである。
【００６４】
最後のｄｉｖ＿ｘ（ステップＤ３４）の結果から商となる部分を取り出す（ステップＤ３６、Ｄ３７）。この例では、有効ビット数が５なので、２５−１＝３１とのビットごとの論理積をとる。その間に、商の符号を表すビット（図６のＳ）を演算結果から取り出す（ステップＤ３８、Ｄ３９）。商の符号を表すビットが０（商が正）である場合は（ステップＤ４２；真）、ステップＤ３７の結果をそのまま（ステップＤ４１）選択する（ステップＤ４４；Ｔ）。商の符号を表すビットが１（商が負）の場合は（ステップＤ４２；偽）、ステップＤ３７の結果を符号反転した（ステップＤ４０）値を選択する。
【００６５】
以上、説明したとおり、ソースプログラム３６に記載された被除数の有効ビット数を判定し、有効ビット数を減算の繰り返し数に反映して、ｄｉｖ＿ｘの繰り返し数を削減したデータフローグラフ３８を生成することができる。この有効ビット数を反映したデータフローグラフ３８を用いて、リコンフィギュラブル回路１に演算をマッピングすることによって、その演算に使用されるリコンフィギュラブル回路１の規模を縮小し、同時に処理速度を向上し、消費電力も低減できる。
【００６６】
さらに、被除数及び除数の符号を判定して、データフローグラフ３８に反映する場合について説明する。図８は、除算における被除数と除数の有効ビット数及び符号を考慮して、除算の処理を展開したフローチャートである。図５のフローチャートに比べて、被除数及び除数の符号判定と、それぞれの正数への変換、及び商の符号設定と符号判定の処理が省略されている。図８のフローチャートは図３のソースプログラム３６に基づいている。図８のフローチャートでは、被除数は正数で有効ビット数が５、除数は負数で有効ビット数が６である。
【００６７】
図３のソースプログラム３６の例では、１行目のコメント欄の記載から、被除数は正数で有効ビット数が５、除数は負数で有効ビット数が６であることを、コンパイル部３０が判断できる。そこで、図８のフローチャートで示すように、初めからｘを１ビット左にシフトして１を加えた値を＄ｘに代入し、ｙを符号反転して被除数の有効ビット数＋１ビットだけ左にシフトした値を＄ｙに代入することができる（ステップＥ１）。
【００６８】
本実施の形態の方法によれば、被除数と除数の符号を指定するので、商の符号をｄｉｖ＿ｘの結果から取り出す処理と、商の符号を判定する処理を省略することができる。その結果図８のフローチャートは、図５のステップＣ１１の後半とステップＣ１２に相当する処理がない。図８のステップＥ２〜Ｅ４は、図５のステップＣ８〜Ｃ１０と同じである。
また、図８のステップＥ５は、図５のステップＣ１１の前半と同じであり、ステップＥ６は、図５のステップＣ１３と同じである。
【００６９】
図９は、図８のフローチャートで表される処理を、図３の例に適用した場合のデータフローグラフ（ＤＦＧ）３８の例を示す。図９のＤＦＧ３８は、図７のＤＦＧ３８に比べて、被除数及び除数の符号判定と、商の符号設定及び商の符号判定処理が省略されている。
【００７０】
被除数ｘは、１ビット左にシフトされて（ステップＦ１）、商の符号を表すビットとして１が加算される（ステップＦ２、Ｆ３）。除数ｙは、符号反転されて（ステップＦ４）、被除数の有効ビット数＋１ビット（６ビット）だけ左にシフトされる（ステップＦ５）。
【００７１】
ステップＦ６〜Ｆ１５は、図７のステップＤ２６〜Ｄ３５と同様である。最後のｄｉｖ＿ｘ（ステップＦ１４）の結果から商となる部分を取り出す（ステップＦ１６、Ｆ１７）。この例では、有効ビット数が５なので、２５−１＝３１とのビットごとの論理積をとる。商が負であることが分かっているので、ステップＦ１７の結果を符号反転して（ステップＦ１８）除算の商ｒｅｔを得る。
【００７２】
以上、説明したとおり、被除数及び除数の符号をソースプログラム３６の記載から判定して、データフローグラフ３８に反映することによって、さらに論理回路の規模を縮小し、処理時間を短縮することができ、消費電力も低減できる。
【００７３】
（実施の形態２）
実施の形態２では、剰余算を例にとって、本発明のリコンフィギュラブル回路１への演算マッピング方法を説明する。図１０は、実施の形態２に係るマッピング方法の例として、剰余算のソースプログラム３６の一例を示す図である。
【００７４】
剰余算についても筆算の計算方法に分解し、一つの論理回路には簡単な命令のみ持たせて剰余算を実現する方法がある。また、筆算の計算方法による除算の規則性を利用して、一定パターンの演算を一つの演算手段に割り当てる方法が考えられる。
【００７５】
図１１は、多段の減算で構成する筆算の演算方法に剰余算を分解したときの、減算一段の処理を表すデータグラフの例である。図１１（ａ）において、入力Ｐで表される変数ｘは被除数であり、入力Ｑで表される変数ｙは除数である。変数ｘ及びｙは２進数表示の整数であり、２の補数で表現されている。変数ｘ及びｙは正数であることが条件となっている。また、出力Ｒで表される変数ｒｅｔは減算一段の処理結果であり、次の減算一段の被除数となる数（この段における剰余）が格納される。
【００７６】
剰余算を構成する減算一段は次のように行われる。まず、被除数ｘをステップＧ３、Ｇ４、Ｇ５の３つの論理回路に入力する（ステップＧ１）。また除数ｙをステップＧ４およびＧ５の２つの論理回路に入力する（ステップＧ２）。ステップＧ３では、入力をそのまま保持してステップＧ６の入力とする。ステップＧ４では、被除数ｘから除数ｙを減算する。ステップＧ５では、被除数ｘと除数ｙの大小を比較する。被除数ｘが除数ｙより大きければ、ステップＧ５の結果は真であり、被除数ｘが除数ｙ以下であれば偽である。ステップＧ５の出力の破線は、その値が真理値であることを表す。
【００７７】
ステップＧ６では、ステップＧ５の判定結果に応じてステップＧ３の出力（被除数ｘ）とステップＧ４の出力（被除数ｘから除数ｙを減算した結果）のいずれかを選択して出力Ｒとする。ステップＧ６の「ｍｅｒｇｅ」は、破線入力の真偽に応じて、２つの実線入力のいずれかを選択する論理演算を表す。破線入力が真の場合は、実線入力のうちＴで示さ
れる入力を選択する。
【００７８】
剰余算を構成する減算一段の処理では、被除数ｘが除数ｙより大きければ、被除数ｘから除数ｙを減算し、被除数ｘが除数ｙ以下であれば、被除数ｘがそのまま出力される。次の減算一段に入力する前に、除数ｙを１ビット右にシフトする（図１１には現れない）。
【００７９】
図１１（ｂ）は、図１１（ａ）の処理をまとめてｍｏｄ＿ｙ（ステップＨ１）で表すことを示す。ｍｏｄ＿ｙは図１１（ａ）のステップＧ１〜Ｇ６に分解されることを表す。
【００８０】
図１０にもどって、このソースプログラム３６の１行目は、コメント欄である。２行目は、被除数ｘを除数ｙで除した剰余を、変数ｒｅｔに代入することを表す。１行目のコメントは、２行目の剰余算において、被除数が正で有効ビット数が５であり、除数が負で有効ビット数が６であることを表す。
【００８１】
図１０は、剰余算における被除数と除数の有効ビット数及び符号を表す例である。ソースプログラム３６において、被除数と除数の有効ビット数及び符号をどのように表すかは任意である。例えば、変数の型宣言文の変数の後に／と符号つき整数を追加することによって、変数の有効ビット数と符号を表現することができる。
【００８２】
処理装置１０のコンパイル部３０は、例えば図１０に示すソースプログラム３６のコメント欄に記載された情報を読み取って、剰余算における被除数と除数の有効ビット数及び符号を判断する。そして、被除数と除数の有効ビット数及び符号に応じたデータフローグラフ（ＤＦＧ）３８を生成する。
【００８３】
図１２は、剰余算における被除数の有効ビット数を考慮して、剰余算の処理を展開したフローチャートである。図１２において、ｘ＿ＢＩＴが被除数ｘの有効ビット数を表す。図５のフローチャートの各変数は、図１０のソースプログラム３６に対応している。図１３は、図１２のフローチャートにおける変数の内容の例を示す。図１３では、例として被除数を２９、除数を−５としている。図１３のステップは、図１２のステップ（Ｊ１等）に対応している。また、十進数であることを示すｄを付した数以外は二進数表示である。図１３では、被除数ｘと除数ｙは８ビットである。内部変数＄ｘ及び＄ｙは１６ビットであるが、図１３では上位のビットを省略して記載している。図１３の例では、除数の絶対値が小さく被除数の有効ビット数が５で、除数を左にビットシフトしても８ビットに収まっているが、一般には除数が８ビットであると、演算の変数としては最大１５ビット必要である。
【００８４】
倍精度の変数＄ｙに除数ｙの値を代入する（ステップＪ１）。除数ｙの符号を判断し（ステップＪ２）、除数ｙが正でなければ（ステップＪ２；Ｎｏ）、変数＄ｙを−ｙとする（ステップＪ３）。除数ｙが正ならば（ステップＪ２；Ｙｅｓ）、変数＄ｙはｙのままである。図１３の例では、変数＄ｙに十進数の−５が代入され（ステップＪ１）、変数ｙが負なので、符号反転されて十進数の５になっている（ステップＪ３）。図１３では、被除数ｘを表すために、ステップＪ１の行に変数＄ｘとして十進数の２９が記されている。
【００８５】
被除数ｘを１ビット左にシフトして、倍精度の変数＄ｘに代入する（ステップＪ４）。除算の場合と同様に、＄ｘの最下位ビットは剰余の符号を表す。剰余の符号は、剰余が０である場合（すなわち割り切れる場合）を除いて、被除数の符号と同じである。変数＄ｘの符号を判断し（ステップＪ５）、変数＄ｘが正でなければ（ステップＪ５；Ｎｏ）、＄ｘの符号を反転し、＄ｘに１を加算する（ステップＪ６）。すなわち、被除数を正にして、剰余の符号が負であることを示すために、最下位ビットを１にする。変数＄ｘが正であれば（ステップＪ５；Ｙｅｓ）、＄ｘは被除数を１ビット左にシフトした値のままで、最
下位ビットは０である。図１３では、被除数ｘは正なので、符号反転は行われていない。また、被除数の範囲を見やすくするために、＄ｘの最下位ビットをＳとして記載している。この場合、Ｓは０である。
【００８６】
変数＄ｘと桁を合わせるために、変数＄ｙを被除数ｘの有効ビット数（ｘ＿ＢＩＴ）左にシフトする（ステップＪ７)。図１３の例では、被除数の有効ビット数が５なので、＄
ｙは５ビット左にシフトされている（ステップＪ７）。
【００８７】
次に、ステップＪ９を被除数ｘの有効ビット数−１だけ繰り返す（ステップＪ８、Ｊ９、Ｊ１０）。ステップＪ９は、＄ｘを被除数、＄ｙを除数として、図１１に示すｍｏｄ＿ｙの処理を行った後、＄ｙを１ビット右にシフトする。
【００８８】
図１３の例では、ｍｏｄ＿ｙの処理を４回繰り返す。図１３のステップＪ８、Ｊ９、Ｊ１０の（１）〜（４）に、各回のステップＪ９の処理における＄ｘの結果が示されている。各欄の上段は、ｍｏｄ＿ｙの入力＄ｘと＄ｙを示す。各欄の下段は、被除数＄ｘから除数＄ｙを減算した場合はその結果を示す。＄ｘの下段の空欄は、＄ｘから＄ｙを減算した結果が正でないことを示す。その場合は、＄ｘの値がそのまま、次の回の処理に渡される。また、＄ｙを１ビット右にシフトした結果を下段に示す。
【００８９】
ｍｏｄ＿ｙ（ステップＪ９）の１回目と２回目では、＄ｘは＄ｙより小さいので、＄ｘがそのまま、次回の処理に渡される。３回目では、＄ｘは＄ｙより大きくなり、＄ｙを減算した値が次の処理に渡される。４回目では、＄ｘは＄ｙより小さく、＄ｘはそのままとなる。
【００９０】
さらに、もう一度ｍｏｄ＿ｙの処理を行って、＄ｘを１ビット右にシフトした値を変数ｒｅｔとする（ステップＪ１１）。また、変数＄ｘの最下位ビットを取り出して、変数＄ｓｉｇｎとする（ステップＪ１１）。
【００９１】
図１３の例では、ステップＪ１１（ｍｏｄ＿ｙの５回目）では、＄ｘは＄ｙより大きくなり、＄ｙを減算した値が＄ｘとなる。ｍｏｄ＿ｙを５回繰り返した結果、＄ｘの剰余の符号の上位ビット（Ｓの左）は００００１００（十進数の４）となり、剰余となっている（２９／（−５）＝−５余り４）。ｒｅｔは＄ｘの結果を１ビット右にシフトした値０００００１００（十進数の４）となる。また、＄ｓｉｇｎは０である。
【００９２】
最後に、剰余の符号＄ｓｉｇｎが０でない（剰余が負である）場合は（ステップＪ１２；Ｎｏ）、変数ｒｅｔの符号を反転する（ステップＪ１３）。＄ｓｉｇｎが０の（剰余が正である）場合は（ステップＪ１２；Ｙｅｓ）、変数ｒｅｔの符号は反転しない。図６の例では、＄ｓｉｇｎは０なので、ｒｅｔは符号反転されない。
【００９３】
以上、説明したように、被除数の有効ビット数を考慮すると、剰余算を筆算に分解した減算処理の繰り返し数を、有効ビット数分だけに削減することができる。有効ビット数を考慮しない場合には、被除数及び除数が８ビットとすると、除数を７ビットシフトして、最大の７回の減算処理を繰り返す必要がある（最上位ビットは符号を表すので、最大有効ビットは７である）。
【００９４】
図１３の例では、理解を容易にするため、被除数及び除数を８ビットとしたが、例えば、被除数が１６ビットあるいは３２ビットの場合には、減算の繰り返し数が最大１７又は３１となって、有効ビット数を考慮した場合との減算繰り返し数の差が大きく、演算を実効する回路規模と処理時間の差が大きいものとなる。
【００９５】
図１４は、図１２のフローチャートで表される処理を、図１０の例に適用した場合のデータフローグラフ３８の例を示す。図１４において、入力Ｐは被除数ｘを表す。入力Ｑ、Ｑ１、Ｑ２は除数ｙを表す。出力Ｒは除算の剰余ｒｅｔを表す。処理の途中の定数や、一時記憶なども、演算と同じＫを付した番号で示す。以下、定数等も含めてステップと呼ぶ。
【００９６】
図１４のステップＫ１〜Ｋ３は、除数を正にする処理である。入力Ｑ２の符号判定（ステップＫ２）の結果に応じて、入力Ｑ又は入力Ｑ１の符号反転（ステップＫ１）を選択する（ステップＫ３）。
【００９７】
ステップＫ４〜Ｋ１２は、被除数を正にして、剰余の符号を決定する処理を表す。入力Ｐ（被除数ｘ）を１ビット左にシフトして（ステップＫ４）、ステップＫ５とＫ６に入力する。ステップＫ５では符号を反転し、１を加える（ステップＫ７、Ｋ９）。ステップＫ６では値を保持して、ステップＫ１０とＫ１１に入力する。ステップＫ１０はその値を保持する。ステップＫ１１は被除数の符号を判定する。符号判定（ステップＫ８、Ｋ１１）の結果に応じて、入力Ｐを１ビット左にシフトした値（ステップＫ４、Ｋ６、Ｋ１０）か、符号を反転して１を加えた値（ステップＫ５、Ｋ９）を選択する（ステップＫ１２）。ステップＫ１２の結果は、入力Ｐが正の場合は１ビット左にシフトした値で最下位ビットが０、入力Ｐが正でない場合は１ビット左にシフトして符号反転し、最下位ビットを１にした値となる。
【００９８】
その間に、除数を被除数の有効ビット数だけ左にシフトする（ステップＫ１３、Ｋ１４）。図１０の例では、被除数の有効ビット数が５であるから、５ビット左にシフトする。図１４では、４ビット左シフト（ステップＫ１３）と、１ビット左シフト（ステップＫ１４）の２ステップで行っている。これは、シフトビット数が２のべき乗であるという論理回路の特性によるものである。
【００９９】
そして、ｍｏｄ＿ｙの処理と、同時に除数を１ビット右にシフトする処理を被除数の有効ビット数−１だけ繰り返す（ステップＫ１５〜Ｋ２２）。さらに１回、ｍｏｄ＿ｙの処理を行う（ステップＫ２３）。
【０１００】
最後のｍｏｄ＿ｙ（ステップＫ２３）の結果から剰余となる部分を取り出す（ステップＫ２５〜Ｋ３１）。ステップＫ２３の結果を１ビット右にシフトし（ステップＫ２６）、その値と（ステップＫ２９）、その値を符号反転した値（ステップＫ３０）を用意する。その間にステップＫ２３の結果の最下位ビットを取り出して（ステップＫ２５）、その値が０であるか否かを判定する（ステップＫ２７）。そして、ステップＫ２７の結果が真（剰余が正）ならば、ステップＫ２９の出力を選択し、ステップＫ２７の結果が偽（剰余が負）ならば、ステップＫ３０の出力を選択して、剰余ｒｅｔ（出力Ｒ）とする（ステップＫ３１）。
【０１０１】
以上、説明したとおり、ソースプログラム３６に記載された被除数の有効ビット数を判定し、有効ビット数を減算の繰り返し数に反映して、ｍｏｄ＿ｙの繰り返し数を削減したデータフローグラフ３８を生成することができる。この有効ビット数を反映したデータフローグラフ３８を用いて、リコンフィギュラブル回路１に演算をマッピングすることによって、その演算に使用されるリコンフィギュラブル回路１の規模を縮小し、同時に処理速度を向上し、消費電力も低減できる。
【０１０２】
さらに、被除数及び除数の符号を判定して、データフローグラフ３８に反映する場合について説明する。図１５は、剰余算における被除数と除数の有効ビット数及び符号を考慮して、剰余算の処理を展開したフローチャートである。図１２のフローチャートに比べて
、被除数及び除数の符号判定と、それぞれの正数への変換、及び剰余の符号設定と符号判定の処理が省略されている。図１５のフローチャートは図１０のソースプログラム３６に基づいている。図１５のフローチャートでは、被除数は正数で有効ビット数が５、除数は負数で有効ビット数が６である。
【０１０３】
図１０のソースプログラム３６の例では、１行目のコメント欄の記載から、被除数は正数で有効ビット数が５、除数は負数で有効ビット数が６であることを、コンパイル部３０が判断できる。そこで、図１５のフローチャートで示すように、初めから除数ｙを符号反転して＄ｙに代入し（ステップＬ１）、被除数ｘを１ビット左にシフトした値を＄ｘに代入する（ステップＬ２）。＄ｘの符号判定と符号反転処理（図１２のステップＪ５、Ｊ６）は省略されている。＄ｙを被除数の有効ビット数だけ左にシフトする処理から、ｍｏｄ＿ｙ及び＄ｙの１ビット右シフトを繰り返す処理（ステップＬ３〜Ｌ６）は、図１２のステップＪ７〜Ｊ１０と同じである。
【０１０４】
図１０の例では、剰余は正であることが分かっているので、最後にｍｏｄ＿ｙの処理のもう１回行い、結果を１ビット右にシフトして剰余ｒｅｔを得る（ステップＬ７）。
【０１０５】
本実施の形態の方法によれば、被除数と除数の符号を指定するので、剰余の符号をｍｏｄ＿ｙの結果から取り出す処理と、剰余の符号を判定する処理を省略することができる。その結果図１５のフローチャートは、図１２のステップＪ１１の３行目からステップＪ１３に相当する処理がない。
【０１０６】
図１６は、図１５のフローチャートで表される処理を、図１０の例に適用した場合のデータフローグラフ（ＤＦＧ）３８の例を示す。図１６のＤＦＧ３８は、図１４のＤＦＧ３８に比べて、被除数及び除数の符号判定と、剰余の符号設定及び剰余の符号判定処理が省略されている。
【０１０７】
除数ｙは負数なので、符号反転されて（ステップＭ１）、被除数の有効ビット数（５ビット）だけ左にシフトされる（ステップＭ２）。被除数ｘは、１ビット左にシフトされる（ステップＭ３）。被除数ｘは正数で、剰余の符号を表すビットは０なので、そのままｍｏｄ＿ｙの処理（ステップＭ５）に入力される。被除数ｘが負数の場合は、１ビット左シフトした後に、符号反転及び１を加算する処理が加わる。
【０１０８】
ステップＭ４〜Ｍ１２は、図１４のステップＫ１５〜Ｋ２３と同様である。最後のｍｏｄ＿ｙ（ステップＭ１２）の結果を１ビット右にシフトして（ステップＭ１３）除算の剰余ｒｅｔを得る。この例では、図１４のステップＫ２４、Ｋ２５及びＫ２７〜Ｋ３１は不要である。剰余の符号が負である場合は、剰余の符号反転処理が加わる。
【０１０９】
以上、説明したとおり、被除数及び除数の符号をソースプログラム３６の記載から判定して、データフローグラフ３８に反映することによって、さらに論理回路の規模を縮小し、処理時間を短縮することができ、消費電力も低減できる。
【０１１０】
実施の形態１では除算を例に、実施の形態２では剰余算を例にして本発明の演算マッピング方法について説明したが、本発明の演算マッピング方法は、除算又は剰余算に限られず、演算数の有効ビット数又は符号を利用して、リコンフィギュラブル回路１にマッピングするデータフローを縮小できる演算に適用することができる。例えば、乗算を筆算に分解した加算処理の繰り返し数を、有効ビット数分だけに削減することができる。また、乗算についても符号の判定と符号反転処理を削減することができる。
【０１１１】
なお、上記の例では、整数型の変数について説明したが、浮動小数点型の変数について
も、その仮数部の有効ビット数又は符号をソースプログラム３６の記載から判定し、それに基づいてリコンフィギュラブル回路１にマッピングする演算処理を削減することができる。
【０１１２】
また、上記の例では、入力の有効ビット数、又は有効ビット数及び符号を判定する場合について説明したが、入力の符号のみを判定して、演算処理の符号判定及び符号反転などの処理を削減したデータフローグラフ３８を生成してもよい。
【０１１３】
その他、前記のハードウエア構成やフローチャートは一例であり、任意に変更及び修正が可能である。
【図面の簡単な説明】
【０１１４】
【図１】本発明の実施の形態に係るリコンフィギュラブル回路を備える処理装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係るリコンフィギュラブル回路の構成の例を示すブロック図である。
【図３】本発明の演算マッピング方法の説明に用いる除算のソースプログラムの一例を示す図である。
【図４】多段の減算で構成する筆算の演算方法に除算を分解したときの、減算一段の処理を表すデータグラフの例である。
【図５】除算における被除数の有効ビット数を考慮して、除算の処理を展開したフローチャートである。
【図６】図５のフローチャートにおける変数の内容の例を示す図である。
【図７】図５のフローチャートで表される処理を、図３の例に適用した場合のデータフローグラフの例を示す図である。
【図８】除算における被除数と除数の有効ビット数及び符号を考慮して、除算の処理を展開したフローチャートである。
【図９】図８のフローチャートで表される処理を、図３の例に適用した場合のデータフローグラフの例を示す図である。
【図１０】本発明の演算マッピング方法の説明に用いる剰余算のソースプログラムの一例を示す図である。
【図１１】多段の減算で構成する筆算の演算方法に剰余算を分解したときの、減算一段の処理を表すデータグラフの例である。
【図１２】剰余算における被除数の有効ビット数を考慮して、剰余算の処理を展開したフローチャートである。
【図１３】図１２のフローチャートにおける変数の内容の例を示す図である。
【図１４】図１２のフローチャートで表される処理を、図１０の例に適用した場合のデータフローグラフの例を示す図である。
【図１５】剰余算における被除数と除数の有効ビット数及び符号を考慮して、剰余算の処理を展開したフローチャートである。
【図１６】図１５のフローチャートで表される処理を、図１０の例に適用した場合のデータフローグラフの例を示す図である。
【符号の説明】
【０１１５】
１    リコンフィギュラブル回路
２    論理回路
３    接続部
１０    処理装置
３０    コンパイル部
３２    設定データ生成部
３４    記憶部
３６    ソースプログラム
３８    データフローグラフ
４０    設定データ
【図１】
0004597075.tif 000002
【図２】
0004597075.tif 000003
【図３】
0004597075.tif 000004
【図４】
0004597075.tif 000005
【図５】
0004597075.tif 000006
【図６】
0004597075.tif 000007
【図７】
0004597075.tif 000008
【図８】
0004597075.tif 000009
【図９】
0004597075.tif 000010
【図１０】
0004597075.tif 000011
【図１１】
0004597075.tif 000012
【図１２】
0004597075.tif 000013
【図１３】
0004597075.tif 000014
【図１４】
0004597075.tif 000015
【図１５】
0004597075.tif 000016
【図１６】
0004597075.tif 000017