(57)【要約】【課題】効率的な乗算手法を提供する。【解決手段】本発明の乗算方法は、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの被乗数ｘとｎビットの乗数ｙの積を乗算演算する乗算方法である。この乗算方法は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割して、複数の分割乗数を生成するステップと、複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を、ｋビット演算器を用いて実行するステップと、分割乗数のそれぞれと被乗数ｘとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するステップとを含む。【選択図】図２３
2010086041.tif 000002
【特許請求の範囲】
【請求項１】
ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの被乗数ｘとｎビットの乗数ｙの積を乗算演算する乗算方法であって、
ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割して、複数の分割乗数を生成するステップと、
複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を、ｋビット演算器を用いて実行するステップと、
分割乗数のそれぞれと被乗数ｘとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するステップと、
を含む乗算方法。
【請求項２】
分割乗数を生成するステップは、
（条件１）Ｄ×ｍ＋ｎ＜＝Ｄ×ｋ（なおＤは分割する個数）
が成立する場合に、乗数ｙをＤ個に分割することを特徴とする請求項１に記載の乗算方法。
【請求項３】
分割乗数を生成するステップは、
（条件２）ｍ＋ｎ＞ｋ
がさらに成立する場合に、乗数ｙをＤ個に分割することを特徴とする請求項２に記載の乗算方法。
【請求項４】
分割乗数を生成するステップは、分割乗数が（ｋ−ｍ）ビット以下となるように、ｎビットの乗数ｙを分割することを特徴とする請求項１から３のいずれかに記載の乗算方法。
【請求項５】
複数の分割乗数のそれぞれと被乗数ｘの乗算演算を実行するステップは、それぞれの乗算演算を並列に実行することを特徴とする請求項１から４のいずれかに記載の乗算方法。
【請求項６】
ｋビットの演算器は、部分積の和を導出する演算器であることを特徴とする請求項１から５のいずれかに記載の乗算方法。
【請求項７】
複数の分割乗数のそれぞれと被乗数ｘの乗算演算を実行するステップは、ｋビット演算器を複数個または複数回使用して、乗算演算を実行することを特徴とする請求項１から６のいずれかに記載の乗算方法。
【請求項８】
ｋビット演算器は、ａ、ｂを入力とすると、
入力ｂを１ビット右シフトした第１の値と、ｂの最下位ビットが０であれば０でありまた入力ｂの最下位ビットが１であればａである第２の値との加算値を出力する
ことを特徴とする請求項１から７のいずれかに記載の乗算方法。
【請求項９】
ｋビット演算器は、ａ、ｂ、ｚｉを入力とすると、
入力ａを、入力ｂの最下位ビット値と入力ｂの最下位ビットの１つ隣のビット値を（−２）倍した値と入力ｚｉ値との加算値倍した第１の値と、入力ｂを２ビット右シフトした第２の値との加算値を第１出力として出力し、ｂの最下位ビットの１つ隣のビット値を第２出力として出力する
ことを特徴とする請求項１から７のいずれかに記載の乗算方法。
【請求項１０】
第２出力は、次段の演算器の入力ｚｉに接続されることを特徴とする請求項９に記載の乗算方法。
【請求項１１】
ｍビットの被乗数ｘとｎビットの乗数ｙを乗算演算する処理装置であって、
複数の演算器で構成されるリコンフィギュラブル回路と、
前記リコンフィギュラブル回路に、設定データを供給して、前記リコンフィギュラブル回路の機能を変更する設定部と、を備え、
前記リコンフィギュラブル回路は、
設定データを受けて、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を形成し、ｋビットの演算器を用いて、ｎビットの乗数ｙを分割して生成される複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を実行し、
分割乗数のそれぞれと被乗数ｘとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出することを特徴とする処理装置。
【請求項１２】
被乗数と乗数の乗算演算において部分積の和を導出する演算器であって、ａ、ｂを入力とした場合に、
入力ｂを１ビット右シフトした第１の値と、ｂの最下位ビットが０であれば０でありまた入力ｂの最下位ビットが１であればａである第２の値との加算値を出力することを特徴とする演算器。
【請求項１３】
被乗数と乗数の乗算演算において部分積の和を導出する演算器であって、ａ、ｂ、ｚｉを入力とした場合に、
入力ａを、入力ｂの最下位ビット値と入力ｂの最下位ビットの１つ隣のビット値を（−２）倍した値と入力ｚｉ値との加算値倍した第１の値と、入力ｂを２ビット右シフトした第２の値との加算値を第１出力として出力し、ｂの最下位ビットの１つ隣のビット値を第２出力として出力する
ことを特徴とする演算器であることを特徴とする演算器。
【請求項１４】
ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの被乗数ｘとｎビットの乗数ｙの積を乗算演算する乗算方法であって、
ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｍビットの被乗数ｘを分割して、複数の分割被乗数を生成するステップと、
複数の分割被乗数のそれぞれと、乗数ｙの乗算演算を、ｋビット演算器を用いて実行するステップと、
分割被乗数のそれぞれと乗数ｙとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するステップと、
を含む乗算方法。
【請求項１５】
ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの数ｘとｎビットの数ｙの積を乗算演算する乗算方法であって、
ｍ、ｎ、ｋの間に
（条件１）Ｄ×ｍ＋ｎ＜＝Ｄ×ｋ（なおＤは分割する個数）
（条件２）Ｄ×ｎ＋ｍ＜＝Ｄ×ｋ
（条件３）ｍ＜ｎ
の条件が成立する場合に、ｍビットの数ｘをＤ個に分割して、複数の分割数を生成するステップと、
Ｄ個の分割数のそれぞれと、数ｙの乗算演算を、ｋビット演算器を用いて実行するステップと、
Ｄ個の分割数のそれぞれと数ｙとの乗算結果をもとに、数ｘと数ｙの乗算結果を導出するステップと、
を含む乗算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乗算処理を行う技術に関し、たとえば機能の変更が可能なリコンフィギュラブル回路を用いて乗算処理を行う技術に関する。
【背景技術】
【０００２】
近年、アプリケーションに応じてハードウェアの動作を変更可能なリコンフィギュラブルプロセッサの開発が進められている。リコンフィギュラブルプロセッサを実現するためのアーキテクチャとしては、ＤＳＰ(Digital Signal Processor)や、ＦＰＧＡ(Field Programmable Gate Array)を用いる方法が存在する。
【０００３】
ＦＰＧＡ（Field Programmable Gate Array）はＬＳＩ製造後に回路データを書き込んで比較的自由に回路構成を設計することが可能であり、専用ハードウエアの設計に利用されている。ＦＰＧＡは、論理回路の真理値表を格納するためのルックアップテーブル（ＬＵＴ）と出力用のフリップフロップからなる基本セルと、その基本セル間を結ぶプログラマブルな配線リソースとを含む。ＦＰＧＡでは、ＬＵＴに格納するデータと配線データを書き込むことで目的とする論理演算を実現できる。しかし、ＦＰＧＡでＬＳＩを設計した場合、ＡＳＩＣ（Application Specific IC）による設計と比べると、実装面積が非常に大きくなり、コスト高になる。そこで、ＦＰＧＡを動的に再構成することで、回路構成の再利用を図る方法が提案されている（例えば、特許文献１参照）。
【０００４】
近年、ＡＬＵ(Arithmetic Logic Unit)と呼ばれる基本演算機能を複数持つ多機能素子を多段に並べたＡＬＵアレイの検討が行われるようになった。ＡＬＵアレイでは、処理が上段から下段の一方向に流れるので、水平方向のＡＬＵを結ぶ配線は基本的には不要である。そのため、ＦＰＧＡと比較して回路規模を小さくすることが可能となる（例えば、特許文献２参照）。
【０００５】
ＡＬＵアレイでは、コマンドデータによりＡＬＵ回路の演算機能構成と前後段のＡＬＵを接続する接続部の配線が制御され、所期の演算処理を実行することができる。コマンドデータは、一般にＣ言語等の高級プログラム言語で記述されたソースプログラムからデータフローグラフ（ＤＦＧ：Data Flow Graph）を作成し、その情報をもとに作成される。
【０００６】
ＡＬＵは、加算演算やシフト演算などの演算機能をそれぞれ実行する複数の基本演算素子を備えて構成される。ＡＬＵが基本演算素子を多く持つことは、それだけＡＬＵアレイの演算能力を高め、演算処理の汎用性を高めることができる。一方で、ＡＬＵの基本演算素子の数を増やすことは、それだけＡＬＵの回路規模が大きくなるという欠点もある。
【特許文献１】特開平１０−２５６３８３号公報
【特許文献２】特開２００５−２７５６９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
例えば、乗算演算機能を実行する基本演算素子をＡＬＵに作りこんだ場合、その基本演算素子の回路規模が大きくなるため、ＡＬＵアレイ全体の回路規模が増大する。一方、乗算演算素子を有しないＡＬＵアレイで乗算演算を実行する場合、加算演算やシフト演算などを組み合わせたＤＦＧを作成して、ＡＬＵアレイにマッピングすることになる。この場合、ＤＦＧが非常に大きくなり、乗算処理に時間がかかり、処理の高速性が損なわれるとともに、ＡＬＵアレイの消費電力が増加する。したがって、乗算演算機能を効率的に実行できるＤＦＧを生成することが好ましい。また、乗算結果がＡＬＵで構成される演算器のビット幅を超える場合においても、効率的に乗算できる手法を提供できることが好ましい。
【０００８】
本発明はこうした状況に鑑みてなされたもので、その目的は、効率的な乗算処理を行う技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明のある態様の乗算方法は、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの被乗数ｘとｎビットの乗数ｙの積を乗算演算する乗算方法に関する。この乗算方法は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割して、複数の分割乗数を生成するステップと、複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を、ｋビット演算器を用いて実行するステップと、分割乗数のそれぞれと被乗数ｘとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するステップとを含む。
【００１０】
本発明の別の態様は、処理装置である。この装置は、ｍビットの被乗数ｘとｎビットの乗数ｙを乗算演算する処理装置であって、複数の演算器で構成されるリコンフィギュラブル回路と、前記リコンフィギュラブル回路に、設定データを供給して、前記リコンフィギュラブル回路の機能を変更する設定部とを備える。リコンフィギュラブル回路は、設定データを受けて、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を形成し、ｋビットの演算器を用いて、ｎビットの乗数ｙを分割して生成される複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を実行し、分割乗数のそれぞれと被乗数ｘとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出する。
【００１１】
本発明のさらに別の態様は、被乗数と乗数の乗算演算において部分積の和を導出する演算器であって、ａ、ｂを入力とした場合に、入力ｂを１ビット右シフトした第１の値と、ｂの最下位ビットが０であれば０でありまた入力ｂの最下位ビットが１であればａである第２の値との加算値を出力する演算器である。
【００１２】
また本発明のさらに別の態様は、被乗数と乗数の乗算演算において部分積の和を導出する演算器であって、ａ、ｂ、ｚｉを入力とした場合に、入力ａを、入力ｂの最下位ビット値と入力ｂの最下位ビットの１つ隣のビット値を（−２）倍した値と入力ｚｉ値との加算値倍した第１の値と、入力ｂを２ビット右シフトした第２の値との加算値を第１出力として出力し、ｂの最下位ビットの１つ隣のビット値を第２出力として出力する演算器である。
【００１３】
本発明のさらに別の態様は、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの被乗数ｘとｎビットの乗数ｙの積を乗算演算する乗算方法に関する。この乗算方法は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｍビットの被乗数ｘを分割して、複数の分割被乗数を生成するステップと、複数の分割被乗数のそれぞれと、乗数ｙの乗算演算を、ｋビット演算器を用いて実行するステップと、分割被乗数のそれぞれと乗数ｙとの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するステップとを含む。
【００１４】
また本発明のさらに別の態様は、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの数ｘとｎビットの数ｙの積を乗算演算する乗算方法に関する。この乗算方法は、ｍ、ｎ、ｋの間に
（条件１）Ｄ×ｍ＋ｎ＜＝Ｄ×ｋ（なおＤは分割する個数）
（条件２）Ｄ×ｎ＋ｍ＜＝Ｄ×ｋ
（条件３）ｍ＜ｎ
の条件が成立する場合に、ｍビットの数ｘをＤ個に分割して、複数の分割数を生成するステップと、Ｄ個の分割数のそれぞれと、数ｙの乗算演算を、ｋビット演算器を用いて実行するステップと、Ｄ個の分割数のそれぞれと数ｙとの乗算結果をもとに、数ｘと数ｙの乗算結果を導出するステップとを含む。
【００１５】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、装置、システム、コンピュータプログラムとして表現したものもまた、本発明の態様として有効である。
【発明の効果】
【００１６】
本発明によれば、効率的な乗算演算を行う技術を提供することができる。
【発明を実施するための最良の形態】
【００１７】
図１は、実施の形態に係る処理装置１０の構成図である。処理装置１０は、回路構成を再構成可能とする機能を有する集積回路装置２６を備える。集積回路装置２６は１チップとして構成され、リコンフィギュラブル回路１２、設定部１４、制御部１８、内部状態保持回路２０、出力回路２２、第１フィードバック経路２４、遅延保持回路２７および第２フィードバック経路２９を備える。リコンフィギュラブル回路１２は複数の演算器で構成され、設定を変更することにより、機能の変更を可能とする。リコンフィギュラブル回路１２は組合せ回路または順序回路等の論理回路として構成される。第１フィードバック経路２４および第２フィードバック経路２９は、フィードバックパスとして機能し、リコンフィギュラブル回路１２の出力を、リコンフィギュラブル回路１２の入力に接続する。
【００１８】
リコンフィギュラブル回路１２は、それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、前段の論理回路の出力と後段の論理回路の入力の接続関係を設定可能な接続部とを備える。構造的には、複数の論理回路列の間に、論理回路列間の接続用結線を設定する接続部が設けられる。リコンフィギュラブル回路１２は、複数段に配列された各論理回路の機能、および論理回路間の接続を任意に設定することで、機能の変更を可能とする。本実施の形態における論理回路は、演算機能のそれぞれを実行する基本演算素子の複数個を所定の規則の下で接続する組合せ用結線を有して構成される。
【００１９】
設定部１４は、リコンフィギュラブル回路１２に所期の回路ないしは演算器を構成するための設定データ４０を供給する。設定部１４は、プログラムカウンタのカウント値に基づいて記憶したデータを出力するコマンドメモリとして構成されてもよい。この場合、制御部１８がプログラムカウンタの出力を制御する。この場合、設定データ４０はコマンドメモリから出力されるコマンドデータであってよい。
【００２０】
内部状態保持回路２０は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２の出力を受け付ける。内部状態保持回路２０は第１フィードバック経路２４に接続されており、リコンフィギュラブル回路１２の出力を直接リコンフィギュラブル回路１２の入力にフィードバックさせる。また内部状態保持回路２０は、リコンフィギュラブル回路１２の出力を遅延保持回路２７に供給する。内部状態保持回路２０は選択器を有し、選択器は、制御部からの選択指示をもとに、第１フィードバック経路２４に送り出すデータ、および遅延保持回路２７に供給するデータを選択する。なお、選択器は、同一のデータを第１フィードバック経路２４および遅延保持回路２７の双方に送り出してもよい。
【００２１】
遅延保持回路２７はメモリであって、リコンフィギュラブル回路１２から出力される出力データを格納するための複数のＲＡＭにより構成される。遅延保持回路２７は、リコンフィギュラブル回路１２の出力データを任意の時間遅延させる機能をもつ。この例では、遅延保持回路２７が、内部状態保持回路２０から出力されるデータを格納しているが、リコンフィギュラブル回路１２から直接出力されるデータを格納してもよい。遅延保持回路２７は、制御部１８からのＷ／Ｒイネーブル信号およびアドレス信号に基づいて、データの書込／読出を行う。遅延保持回路２７は第２フィードバック経路２９に接続されており、制御部１８からの読出指示に基づいて、所期のタイミングでデータをリコンフィギュラブル回路１２の入力にフィードバックさせる。なお、設定部１４がコマンドメモリとして構成されている場合、コマンドメモリから供給されるコマンドデータで、遅延保持回路２７のデータの書込／読出を行ってもよい。
【００２２】
出力回路２２は、例えばデータフリップフロップ（ＤＦＦ）などの順序回路として構成され、リコンフィギュラブル回路１２から出力されるデータを外部に出力する。この例では、出力回路２２が、遅延保持回路２７から出力されるデータを受け付けているが、リコンフィギュラブル回路１２から直接出力されるデータを受け付けてもよく、また内部状態保持回路２０から出力されるデータを受け付けてもよい。
【００２３】
処理装置１０においては、リコンフィギュラブル回路１２の出力をリコンフィギュラブル回路１２の入力にフィードバックする経路が、第１フィードバック経路２４および第２フィードバック経路２９の２系統存在する。第１フィードバック経路２４は、遅延保持回路２７を介さないために、リコンフィギュラブル回路１２の出力データを高速にフィードバック処理することが可能である。一方、第２フィードバック経路２９は、制御部１８からの指示により所期のタイミングでデータ信号をリコンフィギュラブル回路１２に供給することができる。このように、第１フィードバック経路２４または第２フィードバック経路２９は、リコンフィギュラブル回路１２上に再構成する回路に応じて適宜使い分けられる。
【００２４】
リコンフィギュラブル回路１２は、機能の変更が可能な論理回路を有して構成される。複数の論理回路は、マトリックス状に配置された構造をとってもよい。各論理回路の機能と、論理回路間の接続関係は、設定部１４により供給される設定データ４０に基づいて設定される。また、論理回路内において、基本演算素子同士を接続する組合せ用結線も、設定データ４０に基づいて設定される。設定データ４０は、以下の手順で生成される。
【００２５】
集積回路装置２６により実現されるべきプログラム３６が、記憶部３４に保持されている。プログラム３６は、回路における処理の動作を記述した動作記述を示し、信号処理回路または信号処理アルゴリズムなどをＣ言語などの高級言語で記述したものである。コンパイル部３０は、記憶部３４に格納されたプログラム３６をコンパイルし、データフローグラフ（ＤＦＧ）３８に変換して記憶部３４に格納する。データフローグラフ３８は、回路における演算間の実行順序の依存関係を表現し、入力変数および定数の演算の流れをグラフ構造で示したものである。一般に、データフローグラフ３８は、上から下に向かって演算が進むように作成される。
【００２６】
本実施の形態では、論理回路が複数の基本演算素子を有して、それぞれの演算機能を実行する。一般的に用いる演算としては、加算演算や減算演算など様々なものをあげることができるが、そのうちの一つに乗算演算がある。リコンフィギュラブル回路１２の汎用性という観点からは、各論理回路が乗算を実行する基本演算素子を備えることが好ましいが、実際には乗算用の演算素子は、他の加算演算などの演算素子と比較すると、回路規模が非常に大きい。そのため、論理回路は、乗算用の基本演算素子を持たずに構成され、データフローグラフ３８中の乗算演算は、筆算アルゴリズムやＢｏｏｔｈアルゴリズムなどを用いて加算やビットシフトなどで演算できる形態に展開する必要がある。乗算演算の展開は、コンパイル部３０により実行される。
【００２７】
データフローグラフ処理部３１は、コンパイル部３０により生成されたデータフローグラフ３８から、所定の規則を有するデータフローの一群を探索する。このデータフローの一群は、演算ノード間に所定の接続関係を有するノードの集合であって、予め記憶部３４において登録されている。データフローグラフ処理部３１は、所定のデータフローの一群を探索して、その一群を構成するノード数よりも少ない数のノードに置換する。このとき、ノード数を減らす観点から、１つのノードに置換することが好ましい。
【００２８】
なお、データフローの一群から置換されたノードは、リコンフィギュラブル回路１２の論理回路で処理可能なノードである必要がある。これに対応して、論理回路は、置換されたノードを処理するために、自身のもつ複数の基本演算素子を所定の順序で組み合わせるための組合せ用結線を有して構成される。これにより、論理回路は基本演算素子の数を増やすことなく、組合せ用結線をもつことで、複数の基本演算素子により実行される新たな演算機能をもつことができる。言い換えると、論理回路における複数の基本演算素子の可能な組合せに応じて、所定の規則を有するデータフローの一群を予め登録し、データフローグラフ処理部３１が、１つの論理回路において実行可能なデータフローの一群を探索して、１つのノードに置換するすることが可能となる。
【００２９】
設定データ生成部３２は、データフローグラフ３８から設定データ４０を生成する。設定データ４０は、データフローグラフ３８をリコンフィギュラブル回路１２にマッピングするためのデータであり、リコンフィギュラブル回路１２における論理回路の機能や論理回路間の接続関係を定める。設定データ生成部３２が、１つの生成すべき回路を分割してできる複数の回路の設定データ４０を生成してもよい。
【００３０】
図２は、１つの生成すべきターゲット回路４２を分割してできる複数の回路の設定データ４０について説明するための図である。１つのターゲット回路４２を分割して生成される回路を、「分割回路」と呼ぶ。この例では、１つのターゲット回路４２が、４つの分割回路、すなわち分割回路Ａ、分割回路Ｂ、分割回路Ｃ、分割回路Ｄに分割されている。ターゲット回路４２は、データフローグラフ３８における演算の流れにしたがって分割される。データフローグラフ３８において、上から下に向かう方向に演算の流れが表現される場合、そのデータフローグラフ３８を上から所定の間隔で切り取り、その切り取った部分を分割回路として設定する。流れにしたがって切り取る間隔は、リコンフィギュラブル回路１２における論理回路の段数以下に定められる。ターゲット回路４２は、データフローグラフ３８の横方向で分割されてもよい。横方向に分割する幅は、リコンフィギュラブル回路１２における論理回路の１段当たりの個数以下に定められる。
【００３１】
特に、生成すべきターゲット回路４２がリコンフィギュラブル回路１２よりも大きい場合に、設定データ生成部３２は、リコンフィギュラブル回路１２にマッピングできる大きさになるように、ターゲット回路４２を分割することが好ましい。リコンフィギュラブル回路１２へのマッピングは、一度に、例えば１回のクロックで実行することができる。したがって、この場合、４つの分割回路は、４クロックで生成することができる。設定データ生成部３２は、リコンフィギュラブル回路１２における論理回路の配列構造とデータフローグラフ３８によって、ターゲット回路４２の分割方法を定める。リコンフィギュラブル回路１２の配列構造は、制御部１８から設定データ生成部３２に伝えられてもよく、また予め記憶部３４に記録されていてもよい。また、制御部１８が、ターゲット回路４２の分割方法を設定データ生成部３２に指示してもよい。
【００３２】
以上の手順を実行することにより、記憶部３４は、リコンフィギュラブル回路１２を所期の回路として構成するための複数の設定データ４０を記憶する。複数の設定データ４０は、分割回路Ａを構成するための設定データ４０ａ、分割回路Ｂを構成するための設定データ４０ｂ、分割回路Ｃを構成するための設定データ４０ｃ、および分割回路Ｄを構成するための設定データ４０ｄである。既述のごとく、複数の設定データ４０は、１つのターゲット回路４２を分割した複数の分割回路をそれぞれ表現したものである。各設定データ４０を供給することにより、リコンフィギュラブル回路１２上に分割回路を１クロックで構成することができる。このように、リコンフィギュラブル回路１２の回路規模に応じて、生成すべきターゲット回路４２の設定データ４０を生成することにより、汎用性の高い処理装置１０を実現することが可能となる。別の視点からみると、実施の形態の処理装置１０によれば、回路規模の小さいリコンフィギュラブル回路１２を用いて、所望の回路を再構成することが可能となる。
【００３３】
図３は、リコンフィギュラブル回路１２の構成の一例を示す。リコンフィギュラブル回路１２は、それぞれが複数の演算機能を選択的に実行可能な論理回路の多段配列と、前段の論理回路の出力と後段の論理回路の入力の接続関係を任意に設定可能な接続部５２とを備える。リコンフィギュラブル回路１２では、論理回路の多段配列構造により、上段から下段に向かって演算が進められる。なお、本明細書において「多段」とは、複数の段を意味する。
【００３４】
リコンフィギュラブル回路１２は、論理回路としてＡＬＵ(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を改良したノードmult、およびノードbooth2を提案する。この場合は、コンパイル部３０が、ノードmultまたはノードbooth2となるノード群がＤＦＧに含まれるようにコンパイル処理を行う。ノードmul_tについて説明したように、ノード群探索部６０は、コンパイル部３０により生成されたＤＦＧからノード群を探索し、ノード置換部６１が、ノード群をノードmult、ノードbooth2などに置換し、ＤＦＧ再構成部６２がＤＦＧを再構成する。
【００６６】
以下、特開２００５−２７５６９８号公報の図２４に示される８ビットの被乗数×８ビットの乗数の乗算演算について説明する。
図１７は、ノードmul_tを利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す。図１７において、ｎｏｐ（信号スルー）ノードの表記は省略している。図示されるように、従来のノードmul_tを利用した８ビットの被乗数×８ビットの乗数の乗算演算では、計１１段のＡＬＵ列が使用される。
【００６７】
図示されるように、図１７に示すＤＦＧによると、第２段で１ビット左シフトが実行され、最終段で１ビット右シフトする演算が必要となる。したがって、被乗数と乗数のビット数をそれぞれｍビット、ｎビットとし、ＡＬＵにノードmul_tを実行する演算器がｋビットで構成される場合、ｍ＋ｎ＜＝ｋ−１の関係が成立すれば、直列接続するｋビット演算器を用いて乗算演算が実行可能であるが、ｍ＋ｎ＝ｋの関係が成立する場合には、ｋビット演算器を用いた乗算演算が実行不能となる問題があった。したがって、８ビット×８ビットの乗算演算は、１６ビット演算器では実行できず、少なくとも１７ビット以上の演算器でないと実行することができない。したがって、この場合は、ノードmul_tが、１７ビット以上の演算器として構成される必要があった。
【００６８】
＜改良した筆算アルゴリズムによるノード接続＞
以上の問題を解決するべく、以下において、新たなノードmultを提案する。
図１８は、ノードmultの演算処理を表現する。ノードmultは、ａ、ｂを入力として、ＯＵＴを出力する演算として定義される。演算出力ＯＵＴは、
（ｂ＞＞１）＋ｂ［０］＊ａ
で示される値である。なお、ｂ［０］は、ｂの最下位ビット値を表現する。演算出力ＯＵＴは、ｂ［０］が１の場合は、ｂを１ビット右シフトした値と、ａを加算したものとなり、ｂ［０］が０の場合は、ｂを１ビット右シフトした値となる。
【００６９】
ノードmultは、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器として構成される。ノードmultとして形成されるｋビット演算器は、リコンフィギュラブル回路１２が筆算アルゴリズムを用いてｐビットの値とｑビットの値の積を演算する際に、部分積の和を導出する。なおノードmultは、任意ビット同士の演算を可能であってもよい。本実施例において、ノードmultはＡＬＵ上に構成される。
【００７０】
このｋビット演算器の回路構成について説明する。図１８に示すｋビット演算器は、ａ、ｂを入力とし、筆算アルゴリズムを実現する回路において、部分積の和を導出するように動作する。ｋビット演算器は、ａ、ｂを入力とすると、入力ｂを１ビット右シフトした第１の値と、ｂの最下位ビットが０であれば０でありまた入力ｂの最下位ビットが１であればａである第２の値との加算値を出力する。
【００７１】
第１の値は、１ビットシフタにより出力されてもよいが、ＡＬＵにおける結線により入力ｂを１ビットだけ右シフトして出力されてもよい。第２の値は、たとえばｂの最下位ビットの値に応じて０またはａを選択する選択出力回路により出力されてもよい。このように部分積の和を導出するｋビット演算器は、乗算演算器を用いることなく、簡易な回路の組み合わせにより部分積の和を導出することができる。
【００７２】
図１９は、ノードmultを利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す。図１９において、ｎｏｐ（信号スルー）ノードの表記は省略している。図示されるように、ノードmultを利用した８ビットの被乗数×８ビットの乗数の乗算演算では、計９段のＡＬＵ列が使用され、図１７に示す従来のＤＦＧと比較すると、１ビット左シフトおよび１ビット右シフトの演算処理が省略されて、乗算演算処理に必要な段数が減っていることが分かる。
【００７３】
また、被乗数と乗数のビット数をそれぞれｍビット、ｎビットとし、演算器がｋビットで構成される場合、ｍ＋ｎ＜＝ｋの関係が成立すれば、直列接続したｋビット演算器を用いた乗算演算が実行可能となる。すなわち、ｍ＋ｎ＝ｋの関係が成立する場合にも、ｋビット演算器を用いた乗算演算が可能となり、したがって８ビット×８ビットの乗算演算を、１６ビット演算器で処理できる。
【００７４】
このように、図１８に示すノードmultをＡＬＵに構成して、このＡＬＵを複数個または複数回使用することで、乗算処理を従来と比較して高速に実行できる。たとえばノードmultをリコンフィギュラブル回路１２上に複数構成し、それらを直列に接続することで、乗算処理を実行できる。またリコンフィギュラブル回路１２上にノードmultが構成されたＡＬＵを、ループバックにより複数回使用することによっても、乗算処理を実行できる。上記したように、ＡＬＵにノードmultを実行するｋビット演算器が構成される場合に、ｍビット×ｎビット（ｍ＋ｎ＝ｋ）の乗算演算を処理することが可能である。
【００７５】
＜２次のブース法を利用した乗算アルゴリズムによるノード接続＞
以下において、２次のブース法を利用した乗算アルゴリズムを説明する。この乗算アルゴリズムでは、ノードbooth2を使用する。
図２０は、ノードbooth2の演算処理を表現する。ノードbooth2は、ａ、ｂ、ｚｉを入力として、ＯＵＴおよびｚｏを出力する演算として定義される。演算出力ＯＵＴは、
（ｂ＞＞２）＋（−２＊ｂ［１］＋ｂ［０］＋ｚｉ）＊ａ
で示される値である。なお、ｂ［０］は、ｂの最下位ビット値を表現し、ｂ［１］は、ｂの最下位ビットの１つ隣のビット値を表現する。演算出力ＯＵＴは、入力ａを（入力ｂの最下位ビット値＋入力ｂの最下位ビットの１つ隣のビット値を（−２）倍した値＋入力ｚｉ値）倍した第１の値と、入力ｂを２ビット右シフトした第２の値との加算値となる。出力ｚｏは、ｂの最下位ビットの１つ隣のビット値となる。
【００７６】
ノードbooth2は、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器として構成される。ノードbooth2として形成されるｋビット演算器は、リコンフィギュラブル回路１２が２次のブース法を用いてｐビットの値とｑビットの値の積を演算する際に、部分積の和を導出する。なおノードbooth2は、任意ビット同士の演算を可能であってもよい。本実施例において、ノードbooth2はＡＬＵ上に構成される。
【００７７】
このｋビット演算器の回路構成について説明する。図２０に示すｋビット演算器は、ａ、ｂ、ｚｉを入力とし、２次のブース法を利用した乗算アルゴリズムを実現する回路において、部分積の和を導出するように動作する。ｋビット演算器は、ａ、ｂ、ｚｉを入力とすると、入力ａを、入力ｂの最下位ビット値と入力ｂの最下位ビットの１つ隣のビット値を（−２）倍した値と入力ｚｉ値との加算値倍した第１の値と、入力ｂを２ビット右シフトした第２の値との加算値を第１出力ＯＵＴとして出力し、ｂの最下位ビットの１つ隣のビット値を第２出力ｚｏとして出力する。
【００７８】
このｋビット演算器は、入力ｂの最下位ビット値、入力ｂの最下位ビットの１つ隣のビット値、入力ｚｉの値の３ビットの８種類のパターンに応じて、−２ａ−１、−ａ−１、０、ａ、２ａのいずれかを出力する第１選択出力回路と、入力ｂの最下位ビット値、入力ｂの最下位ビットの１つ隣のビット値、入力ｚｉの値の３ビットの８種類のパターンに応じて、１または０のいずれかを出力する第２選択出力回路とを備え、第１選択出力回路の出力と、第２選択出力回路の出力と、入力ｂを右に２ビットシフトしたものの３つの値の加算値を第１出力ＯＵＴとするように構成されてもよい。第２出力ｚｏは、次段のｋビット演算器の入力ｚｉに接続される。このように部分積の和を導出するｋビット演算器は、乗算演算器を用いることなく、簡易な回路の組み合わせにより部分積の和を導出することができる。
【００７９】
図２１は、２次のブース法を説明するための図である。ｘ×ｙの乗算演算において、ｙが６ビットであるとき、ｘ×ｙは、図示のように展開される。２次のブース法は、図２１に示す法則性を利用して乗算演算を行うアルゴリズムである。図２１において、ｙ０、ｙ１、ｙ２、ｙ３、ｙ４、ｙ５は、それぞれ６ビットのｙの第１ビット（最下位ビット）、第２ビット、第３ビット、第４ビット、第５ビット、第６ビットである。
【００８０】
図２２は、ノードbooth2を利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す。図２２において、ｎｏｐ（信号スルー）ノードの表記は省略している。ノードbooth2同士の接続では、ノードbooth2から出力されるｚｏを、次段のノードbooth2の入力ｚｉに接続し、最上段のノードbooth2の入力ｚｉには、０を入力する。このようにノードbooth2を直列に接続することで、図２１に示す乗算の法則性を利用した２次のブース法の乗算アルゴリズムをリコンフィギュラブル回路１２上に展開することができる。
【００８１】
このように、図２０に示すノードbooth2をＡＬＵに構成して、このＡＬＵを複数個または複数回使用することで、乗算処理を従来と比較して高速に実行できる。たとえばノードbooth2をリコンフィギュラブル回路１２上に複数構成し、それらを直列に接続することで、乗算処理を実行できる。またリコンフィギュラブル回路１２上にノードbooth2が構成されたＡＬＵを、ループバックにより複数回使用することによっても、乗算処理を実行できる。上記したように、ＡＬＵにノードbooth2を実行するｋビット演算器が構成される場合に、ｍビット×ｎビット（ｍ＋ｎ＝ｋ）の乗算演算を処理することが可能である。
【００８２】
以上のように、従来のノードmul_tを使用した乗算演算と比較すると、それを改良したノードmultまたはノードbooth2を採用することで、乗算演算を高速に実行することが可能となり、また、ＡＬＵに構成されるｋビット演算器を用いて、ｍビット×ｎビット（ｍ＋ｎ＝ｋ）の乗算演算を処理することが可能となる。
以下では、新規に提案するノードmultおよびノードbooth2を用いて、効率的な乗算演算を実行する例について説明する。
【００８３】
＜分割手法を用いた乗算アルゴリズム＞
たとえばＡＬＵが２４ビットの演算器を構成する場合に、ノードmultおよびノードbooth2を用いると、１２ビット×１２ビットの乗算演算を処理できることは既述のとおりであるが、１６ビット×１６ビットの乗算演算を２４ビット演算器で処理することはできない。そこで、本実施例の処理装置１０は、被乗数ないしは乗数を分割して、ビット幅を小さくすることで、乗算演算を効率よく実行できるようにする。以下において、乗数を分割する例について説明する。
【００８４】
図２３は、ノードmultを利用した１６ビットの被乗数ｘと１６ビットの乗数ｙとの乗算のＤＦＧを示す。ここでは、ノードmultが２４ビット演算器として構成されることを前提とする。この分割手法では、１６ビットの乗数ｙを上位８ビットと下位８ビットの２つに分割し、それぞれをmult演算器により並列処理する。これにより、ノードmultの接続段数は８段となり、乗算演算を高速化できる。なお、最下段の加算演算と、最下段から２つめの８ビット右シフト演算は、３２ビット以上の演算器により処理される。
【００８５】
乗数ｙの上位８ビットをｙｈとし、下位８ビットをｙｌとすると、
ｙ＝２８×ｙｈ＋ｙｌ
と表される。よって、
ｘ×ｙ＝ｘ×（２８×ｙｈ＋ｙｌ）＝（ｘ×ｙｈ）×２８＋ｘ×ｙｌ
となる。図２３のＤＦＧでは、左側のmultの列でｘ×ｙｈを計算し、右側のmultの列でｘ×ｙｌを計算している。
【００８６】
仮に、ＡＬＵが３２ビット演算器を構成できる場合には、１６ビット×１６ビットの乗算演算は、ノードmultを１６段直列に接続することで処理できるが、図２３に示すＤＦＧの方が段数は８段と少なく、分割することで高速化が実現できている。また、消費電力の観点からいえば、４８ビット演算器よりも２４ビット演算器の方が少ない電力で駆動できるため、効率的である。
【００８７】
コンパイル部３０は、記憶部３４に格納されたプログラム３６をコンパイルし、データフローグラフ（ＤＦＧ）３８に変換する。このとき、コンパイル部３０は、プログラム３６において、ｍビットの被乗数ｘとｎビットの乗数ｙの乗算演算を検出すると、ＡＬＵに構成可能な演算器のビット数（ｋ）との関係から、ｎビットの乗数ｙを分割するか判断する。コンパイル部３０は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割して、複数の分割乗数（ｙ１、ｙ２・・・）を生成する。
【００８８】
本実施形態においては、以下の条件を満足する場合に、乗数ｙの分割処理が実行される。
（条件１）Ｄ×ｍ＋ｎ＜＝Ｄ×ｋ（なおＤは分割する個数）
（条件２）ｍ＋ｎ＞ｋ
上述した例でいえば、ｍ＝ｎ＝１６、ｋ＝２４である場合に、
１６＋１６＞２４  であるため、（条件１）が成立し、
１６＋２×１６＜＝２×２４  であるため、（条件２）が成立する。
【００８９】
この条件が成立すると、ｎビットの乗数ｙは、最下位ビットよりｎ／Ｄビットずつ複数（Ｄ個）の分割乗数に分割される。分割個数Ｄは、リコンフィギュラブル回路１２において並列処理可能な数に応じて定められてよい。たとえば、図３に示すリコンフィギュラブル回路１２は、６列の構成を有しており、ノードmultは、２つの入力列を必要とするため、最大の分割個数は３となる。
【００９０】
このようにコンパイル部３０は、リコンフィギュラブル回路１２におけるＡＬＵの列数をもとに乗数ｙの分割個数Ｄを決定し、上記の例では、最大分割個数３の範囲内で、分割個数Ｄを決定する。たとえばコンパイル部３０は、分割した乗数が（ｋ−ｍ）ビット以下となるように、ｎビットの分割個数を決定してもよい。なおこのときコンパイル部３０は、分割乗数が（ｋ−ｍ）ビットとなるように、ｎビットの乗数ｙを分割してもよい。これにより、ｋビット演算器を効率的に利用することができ、全体の消費電力を下げることが可能となる。
【００９１】
なお、条件２が成立しない場合であっても、条件１さえ成立すれば、分割処理が実行されてよい。条件２が成立しない場合であっても、分割することで並列処理が可能となるため、処理時間を短縮できる。
【００９２】
コンパイル部３０は、複数の分割乗数のそれぞれと、被乗数ｘの乗算演算を実行し、それぞれの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出するＤＦＧを生成する。
【００９３】
図２３に示すＤＦＧは、リコンフィギュラブル回路１２上に展開されて、１６ビット×１６ビットの乗算処理を行う処理装置１０が実現される。処理装置１０は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割し、分割した乗数のそれぞれと被乗数ｘの乗算をｋビット演算器を用いて実行し、それぞれの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出する乗算器として動作する。分割した乗数のそれぞれと被乗数ｘの乗算を並列に実行することで、乗算処理の高速化を実現できる。
【００９４】
図２４は、ノードbooth2を利用した１６ビットの被乗数ｘと１６ビットの乗数ｙとの乗算のＤＦＧを示す。ここでは、ノードbooth2が２４ビット演算器として構成されることを前提とする。この分割手法では、１６ビットの乗数ｙを上位８ビットと下位８ビットに分割し、それぞれをbooth2演算器により並列処理する。ノードmultの場合と同様に、並列処理することで、ノードbooth2を直列接続するときと比較して、ノードbooth2の接続段数を少なくできる。
【００９５】
なお、第３段のノードbooth2において、０を入力するのは、次のbooth2に、ｚｉとしてｙ［７］を入力し、また入力ｂとして乗数ｙの１６ビット中の上位８ビットを入力するためである。このように構成することで、ｚｉへの入力に特別な回路を用意する必要がなく、回路規模を削減できる。
【００９６】
図２４に示すＤＦＧは、図２３に示すＤＦＧと同様に、リコンフィギュラブル回路１２上に展開されて、２次のブース法を用いて１６ビット×１６ビットの乗算処理を行う処理装置１０が実現される。処理装置１０は、ｍ、ｎ、ｋの間に所定の条件が成立する場合に、ｎビットの乗数ｙを分割し、分割した乗数のそれぞれと被乗数ｘの乗算をｋビット演算器を用いて実行し、それぞれの乗算結果をもとに、被乗数ｘと乗数ｙの乗算結果を導出する乗算器として動作する。分割した乗数のそれぞれと被乗数ｘの乗算を並列に実行することで、乗算処理の高速化を実現できる。
【００９７】
以上、本発明を実施の形態をもとに説明した。実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００９８】
実施の形態では、乗数ｙを分割する例を説明したが、被乗数ｘを分割してもよい。具体的には、以下の条件を満足する場合に、被乗数ｘの分割処理が実行される。
（条件３）Ｄ×ｎ＋ｍ＜＝Ｄ×ｋ（なおＤは分割する個数）
（条件４）ｍ＋ｎ＞ｋ
たとえばｍ＝ｎ＝１６、ｋ＝２４であるとき、
１６＋１６＞２４  であるため、（条件３）が成立し、
１６＋２×１６＜＝２×２４  であるため、（条件４）が成立する。
【００９９】
この条件が成立した場合に、ｍビットの被乗数ｘは、最下位ビットよりｍ／Ｄビットずつ複数（Ｄ個）の分割被乗数に分割されてよい。分割個数Ｄは、リコンフィギュラブル回路１２において並列処理可能な数に応じて定められてよい。
【０１００】
コンパイル部３０は、リコンフィギュラブル回路１２におけるＡＬＵの列数をもとに被乗数ｘの分割個数Ｄを決定し、上記の例では、最大分割個数３の範囲内で、分割個数Ｄを決定する。たとえばコンパイル部３０は、分割した被乗数が（ｋ−ｎ）ビット以下となるように、ｍビットの分割個数を決定してもよい。なおこのときコンパイル部３０は、分割被乗数が（ｋ−ｎ）ビットとなるように、ｍビットの被乗数ｘを分割してもよい。これにより、ｋビット演算器を効率的に利用することができ、全体の消費電力を下げることが可能となる。
【０１０１】
なお、条件４が成立しない場合であっても、条件３さえ成立すれば、被乗数ｘの分割処理が実行されてよい。条件４が成立しない場合であっても、分割することで並列処理が可能となるため、処理時間を短縮できる。
【０１０２】
なお、分割する数を以下のように定めることが可能である。前提として、ｐ＋ｑ＝ｋ（ｐ、ｑは自然数）を満たすｐ、ｑの２つ以上の組み合わせに対して、ｐビットの値とｑビットの値の積の演算に使用可能なｋビットの演算器を用いて、ｍビットの数ｘとｎビットの数ｙの積を乗算演算する乗算方法であることに変わりはない。
【０１０３】
このときｍ、ｎ、ｋの間に
（条件ａ）Ｄ×ｍ＋ｎ＜＝Ｄ×ｋ（なおＤは分割する個数）
（条件ｂ）Ｄ×ｎ＋ｍ＜＝Ｄ×ｋ
（条件ｃ）ｍ＜ｎ
の条件が成立する場合に、より少ないビット数の数ｘをＤ個に分割して、複数の分割数を生成する。続いて、Ｄ個の分割数のそれぞれと、数ｙの乗算演算を、ｋビット演算器を用いて実行し、Ｄ個の分割数のそれぞれと数ｙとの乗算結果をもとに、数ｘと数ｙの乗算結果を導出することで、乗算方法が実現される。
【０１０４】
条件ａは、実施の形態において説明した、乗数ｙを分割するときに用いられる条件１と同じである。したがって条件ａが成立すれば、数ｙを分割できることとなる。条件ｂについてみれば、条件ｂは、数ｘを分割可能であることを判定するための条件であり、条件３と同じである。つまり条件ａ、条件ｂが成立すると、数ｘ、数ｙのいずれも分割可能であることが判定される。条件ｃは、数ｘ、数ｙのうち、より少ないビット数の数ｘを分割対象として選択するための条件として用いられる。
【０１０５】
例えば、２４ビットの演算器で１２ビットの数ｘと１８ビットの数ｙの積を求める場合に、分割個数を２とすれば、
（条件ａ）２×１２＋１８＜＝２×２４
（条件ｂ）２×１８＋１２＜＝２×２４
のそれぞれの条件を満たすので、数ｘと数ｙのどちらを分割しても乗算演算が可能である。この場合、よりビット数の少ない数ｘを分割することによって、数ｙを分割した場合に比べ、multやbooth2の使用回数、たとえば接続段数を減らすことができ、処理時間を短縮することができる。
【０１０６】
リコンフィギュラブル回路１２におけるＡＬＵの配列は、縦方向にのみ接続を許した多段配列に限らず、横方向の接続も許した、メッシュ状の配列であってもよい。また、上記の説明では、段を飛ばして論理回路を接続する接続用結線は設けられていないが、このような段を飛ばす接続用結線を設ける構成としてもよい。
【０１０７】
なお、実施の形態では、ノードmult、ノードbooth2で表現される演算器がリコンフィギュラブル回路１２のＡＬＵに形成される例について説明したが、これらの演算器は、回路上に作り込まれてもよい。たとえば、基本演算器としてノードmultを回路上に形成し、ノードmultをサイクリックに使用することで、乗算機能が実現されてもよい。この場合であっても、回路規模を小さくできるため、消費電力の観点からも効果が高い。
【０１０８】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０１０９】
【図１】実施の形態に係る処理装置の構成図である。
【図２】１つの生成すべきターゲット回路を分割してできる複数の回路の設定データについて説明するための図である。
【図３】リコンフィギュラブル回路の構成の一例を示す図である。
【図４】データフローグラフの構造を説明するための図である。
【図５】前後７点を利用する７タップからなるＦＩＲフィルタ回路を示す図である。
【図６】図５で示すＦＩＲフィルタ回路を置き換えた回路を示す図である。
【図７】図６で示すＦＩＲフィルタ回路をさらに置き換えた回路を示す図である。
【図８】図７に示すＦＩＲフィルタ回路をコンパイルして作成したデータフローグラフを示す図である。
【図９】リコンフィギュラブル回路の一例を示す図である。
【図１０】図８に示すデータフローグラフを、図９のリコンフィギュラブル回路を用いて実現する例を示す図である。
【図１１】ｍビットの被乗数ｘとｎビットの乗数ｙの筆算アルゴリズムのフローチャートを示す図である。
【図１２】筆算アルゴリズムを用いて２４ビットの被乗数×４ビットの乗数の計算をするＤＦＧを示す図である。
【図１３】図１２に示すデータフローグラフにおいて、所定の規則を有するデータフローの一群を点線で囲った図を示す図である。
【図１４】図１３に示すノード群のＤＦＧを示す図である。
【図１５】データフローグラフ処理部の構成を示す図である。
【図１６】ノードmul_tの演算処理を表現する図である。
【図１７】ノードmul_tを利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す図である。
【図１８】ノードmultの演算処理を表現する図である。
【図１９】ノードmultを利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す図である。
【図２０】ノードbooth2の演算処理を表現する図である。
【図２１】２次のブース法を説明するための図である。
【図２２】ノードbooth2を利用した８ビットの被乗数×８ビットの乗数の乗算のＤＦＧを示す図である。
【図２３】ノードmultを利用した１６ビットの被乗数ｘと１６ビットの乗数ｙとの乗算のＤＦＧを示す図である。
【図２４】ノードbooth2を利用した１６ビットの被乗数ｘと１６ビットの乗数ｙとの乗算のＤＦＧを示す図である。
【符号の説明】
【０１１０】
１０・・・処理装置、１２・・・リコンフィギュラブル回路、１４・・・設定部、１８・・・制御部、２６・・・集積回路装置、３０・・・コンパイル部、３１・・・データフローグラフ処理部、３２・・・設定データ生成部、３４・・・記憶部、３６・・・プログラム、３８・・・データフローグラフ、４０・・・設定データ、５２・・・接続部、５３・・・ＡＬＵ列、６０・・・ノード群探索部、６１・・・ノード置換部、６２・・・ＤＦＧ再構成部、７０・・・ノード群。
【図１】
2010086041.tif 000003
【図２】
2010086041.tif 000004
【図３】
2010086041.tif 000005
【図４】
2010086041.tif 000006
【図５】
2010086041.tif 000007
【図６】
2010086041.tif 000008
【図７】
2010086041.tif 000009
【図８】
2010086041.tif 000010
【図９】
2010086041.tif 000011
【図１０】
2010086041.tif 000012
【図１１】
2010086041.tif 000013
【図１２】
2010086041.tif 000014
【図１３】
2010086041.tif 000015
【図１４】
2010086041.tif 000016
【図１５】
2010086041.tif 000017
【図１６】
2010086041.tif 000018
【図１７】
2010086041.tif 000019
【図１８】
2010086041.tif 000020
【図１９】
2010086041.tif 000021
【図２０】
2010086041.tif 000022
【図２１】
2010086041.tif 000023
【図２２】
2010086041.tif 000024
【図２３】
2010086041.tif 000025
【図２４】
2010086041.tif 000026