(57)【特許請求の範囲】
【請求項１】
入力されるデジタルデータに対して数値演算または論理演算を実行し、数値演算または論理演算の出力信号を出力する、複数の演算素子と、
前記演算素子の入力側に接続されるネットワーク出力端子と、
前記演算素子の出力信号または前記演算素子の出力信号以外の外部信号が入力されるネットワーク入力端子と、
前記ネットワーク入力端子をネットワーク出力端子に接続するネットワーク部と備え、
前記ネットワーク部は、
第１のネットワーク入力端子を第１のネットワーク出力端子に接続したときに、第２のネットワーク入力端子をいずれかの第２のネットワーク出力端子にさらに接続することができない、そのようなネットワーク入力端子とネットワーク出力端子との組合せに対する制約が存在する閉塞ネットワーク網を構成し、
前記ネットワーク出力端子間の距離ＬＴ（ｉ，ｊ）を以下の式により定義したときに、
ネットワーク出力端子の２つの組み（Ｔｉ、Ｔｊ）を前記距離ＬＴ（ｉ，ｊ）にしたがって分類したネットワーク出力端子ＴｉのグループＧｉと、ネットワーク出力端子ＴｊのグループＧｊとの間で、互いに距離ＬＴ（ｉ，ｊ）が最も小さくなるように前記ネットワーク出力端子が分類されており、
前記演算素子の２つの入力端子をそれぞれ異なるグループＧｉ，Ｇｊに含まれるネットワーク出力端子Ｔｉ，Ｔｊに接続し、
前記グループＧｉにおいては、ネットワーク出力端子の２つの組み（Ｔｉ、Ｔｊ）を前記距離ＬＴ（ｉ，ｊ）にしたがって分類したネットワーク出力端子Ｔｉのサブグループｇｉｉと、ネットワーク出力端子Ｔｊのサブグループｇｉｊとの間で、互いに距離ＬＴ（ｉ，ｊ）が最も小さくなるように前記ネットワーク出力端子が分類されており、同一種類の複数の演算素子の入力端子をそれぞれ異なるサブグループｇｉｉ，ｇｉｊに含まれるネットワーク出力端子Ｔｉ，Ｔｊに接続し、
前記グループＧｊにおいては、ネットワーク出力端子の２つの組み（Ｔｉ、Ｔｊ）を前記距離ＬＴ（ｉ，ｊ）にしたがって分類したネットワーク出力端子Ｔｉのサブグループｇｊｉと、ネットワーク出力端子Ｔｊのサブグループｇｊｊとの間で、互いに距離ＬＴ（ｉ，ｊ）が最も小さくなるように分類されており、同一種類の複数の演算素子の入力端子をそれぞれ異なるグループｇｊｉ，ｇｊｊに含まれるネットワーク出力端子Ｔｉ，Ｔｊに接
続した回路。
（式１）
ＬＴ（ｉ，ｊ） ＝ ネットワーク出力端子ＴｉおよびＴｊが同時に接続することができないネットワーク入力端子数；
【請求項２】
さらに、前記演算素子のうち、同一種類の演算を実行する複数の演算素子に接続される出力端子間の制約強度のすべての演算素子の種類についての合計が最小となるように、前記演算素子とネットワーク出力端子とを接続した請求項１に記載の回路。
【請求項３】
前記ネットワーク出力端子が接続される演算素子ＰｋおよびＰｌの間の制約強度ＬＰ（ｋ，ｌ）を以下の（式２）により定義したときに、２つの関数Ｆ１（）およびＦ２（）がそれぞれ最小となるように前記演算素子とネットワーク出力端子とを接続する請求項２に記載の回路。
（式２）
ＬＰ（ｋ， ｌ） ＝ ΣＬＴ（ｉ， ｊ）； 
Ｔｉの接続先∈Ｐｋ，Ｔｊの接続先∈Ｐｌ
Ｆ１（）＝Σ（ ΣＬＴ（ｉ， ｊ） ）；
ｋはすべての演算素子 Ｔｉ，Ｔｊの接続先∈Ｐｋ
Ｆ２（）＝Σ（ ΣＬＰ（ｋ，ｌ） ）；
すべての演算素子の種類 Ｐｋ、Ｐｌは同一種類の演算素子
【請求項４】
前記演算素子は、複数のグループに分離され、異なるグループに属する演算素子間で信号が授受されており、
前記ネットワーク部は、第１のネットワーク部と第２のネットワーク部とを有し、
前記第１のネットワーク部は、第１のグループの演算素子ないし第２のグループの演算素子の一部の出力信号を入力し、第１のグループの演算素子に出力信号を出力し、
前記第２のネットワーク部は、第１のグループの演算素子ないし第２のグループの演算素子の一部の出力信号を入力し、第２のグループの演算素子に出力信号を出力する請求項１から３のいずれかに記載の回路。
【請求項５】
前記第１のネットワーク部は、前記第１のグループの演算素子と第２のグループの演算素子の出力端子と、前記第１のグループの演算素子の入力端子との間を接続し、
第２のネットワーク部は、前記第１のグループの演算素子と第２のグループの演算素子の出力端子と、前記第２のグループの演算素子の入力端子との間を接続する請求項４に記載の回路。
【請求項６】
前記第１のネットワーク部と第２のネットワーク部とは、互いに直列に前記第１のグループの演算素子の出力端子と第２のグループの演算素子の入力端子との間、および前記第２のグループの演算素子の出力端子と第１のグループの演算素子の入力端子との間を接続する請求項４に記載の回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、演算素子間を接続するネットワーク技術に関する。
【背景技術】
【０００２】
粗粒度リコンフィギュラブル回路は、様々な機能を備えた複数のプロセッシングエレメント（ＰＥ）とＰＥ間を接続する内部接続ネットワークで構成され、内部接続ネットワークの経路を設定する接続情報を変更することにより任意のＰＥ間におけるデータ転送を実現する。ここで、粗粒度とは、ワード単位での演算を基本命令としたプロセッシングエレメント間で構成したリコンフィギュラブル回路をいう。
【０００３】
ネットワークとしては、任意のデータ経路を設定でき、使用する回路数が少なく、かつ経路の回路段数が少ないネットワークが理想であり、様々なネットワークが提案されている。任意に選択された入力元からいずれの出力先に対しても経路が存在するネットワークは、（１）ある経路を設定した場合にそれが他の経路の邪魔をする、すなわち、他の経路による他の入力元と出力先との接続を阻害する閉塞ネットワークと、（２）ある経路を設定した場合にそれが他の経路の邪魔にならない、すなわち、他の経路による接続を阻害しない非閉塞ネットワークに分類できる。リコンフィギュラブル回路では、複数のエレメントから同時に信号が出力されるため、データ転送の点からは非閉塞ネットワークが理想である。
【０００４】
しかしながら、非閉塞ネットワークでは、多くの配線が必要となり回路が大規模となる。例えば、ｎ入力ｎ出力のネットワークに対し、クロスバースイッチネットワークではｎ２のスイッチが必要となる。
【０００５】
図１に非閉塞ネットワークの１つである、３段のＣｌｏｓネットワークの例を示す。図１に示す３段のＣｌｏｓネットワークでは、３ｎ１．５のスイッチが必要となる。図１において、８入力８出力のクロスバースイッチブロックが、１段当たり８個組合せを構成し、そのような組合せが３段設けられている。
【０００６】
この場合、入力の数ｎ＝６４、出力の数ｎ＝６４であり、ｎ0.5＝８となる。１個のク
ロスバースイッチブロックのスイッチ数は、８×８＝ｎ0.5×ｎ0.5   であり、このよう
なクロスバースイッチブロックが３段×８個＝３×ｎ0.5個設けられている。したがって
、図１を一般化すれば、スイッチの数は、３ｎ１．５となる。
【０００７】
一般に、閉塞ネットワークでは、回路を小型化することができ、代表的なオメガ網やベースライン網などでは２ｎ・ｌｏｇ（ｎ）の回路規模で実現できるが、１つの経路の設定によりブロッキングされる経路があるため、同時に実現できない経路がでてくる。
【特許文献１】特公平７−７１３５３号公報
【特許文献２】特許第２７８６２４６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
粗粒度リコンフィギュラブル回路は、小型化が重要な課題であり、面積の点においては閉塞ネットワークが望ましい。しかしながら、閉塞ネットワークを適用する場合には、粗粒度リコンフィギュラブル回路では、接続されるプロセッシングエレメントの種類が異なるため、プロセッシングエレメントの組合せによっては１つの構造では実現できない処理がでてくる。このような実現できない処理が発生することをブロッキング特性と呼ぶ。
【０００９】
例えば、基本閉塞網の１つである８入力８出力の間接バイナリ３キューブネットワーク（ｉｎｄｉｒｅｃｔ  ｂｉｎａｒｙ  ３−ｃｕｂｅ  ｎｅｔｗｏｒｋ、以下ＩＢ３Ｃ網）を考える（図２参照）。
【００１０】
図２のネットワークは、２つのブロッキング特性がある。ここで、ネットワークを構成する各クロスバースイッチブロックは、図３（Ａ）〜（Ｄ）のような３種類の接続（ストレート、交差、分岐）を設定することができる。                    
【００１１】
第１のブロッキング特性として、図２の回路の第３段目（図２で最上部のクロスバースイッチブロックの行）を構成する各クロスバースイッチブロックに着目する。第３段目のそれぞれのクロスバースイッチブロックの２つの出力端子（図２におけるＺ１とＺ２、Ｚ３とＺ４、Ｚ５とＺ６、およびＺ７とＺ８のそれぞれの組）は、そのクロスバースイッチブロックの入力端子の１つから遡ってつながっているネットワーク入力端子の組（図２におけるＸ１〜Ｘ４の組またはＸ５〜Ｘ７の組）の中の異なる２つのネットワーク入力端子に同時に接続することはできない（図４（Ａ）参照）。すなわち、図４（Ａ）において、×印でマークされる入力端子がつながっている入力端子Ｘ５〜Ｘ８に対して、出力端子Ｚ７，Ｚ８を同時に接続することはできない。
【００１２】
第２のブロッキング特性として、第１段目（図２で最下部のクロスバースイッチブロックの行）を構成する各クロスバースイッチブロックに着目する。第１段目のそれぞれクロスバースイッチブロックの１つ出力端子から到達可能な第３段目の出力端子の組（図２におけるＺ１〜Ｚ４の組またはＺ５〜Ｚ７の組）は、その第１段目のクロスバースイッチブロックの異なる２つ入力端子（図２におけるＸ１とＸ２、Ｘ３とＸ４、Ｘ５とＸ６、およびＸ７とＸ８のそれぞれの組）に同時に接続することはできない（図４（Ｂ））。すなわち、図４（Ｂ）において、×印でマークされる出力端子につながっている第３段目の出力端子の組Ｚ１〜Ｚ４に対して、入力端子Ｘ１、Ｘ２を同時に接続することはできない。
【００１３】
そのため、２つの乗算器、２つの加算器、２つのレジスタ、２つの外部入力からなるリコンフィギュラブル回路（図５参照）の内部ネットワークに図２のＩＢ３Ｃ網を適用して図４のような回路構造にしたとすると、図６のようなアプリケーションの実装しようとしたときに、外部入力２から乗算器への経路と、乗算器から加算器までの経路の２箇所において経路がブロッキングされてしまい、実装することができない（図７参照）。
【００１４】
本発明は、閉塞ネットワークを利用したリコンフィギュアラブル回路において、ブロッキング特性が極力少ない回路構成を提案する。本発明の目的は、そのような回路により極力多くのアプリケーションの実装を可能にすることにある。
【課題を解決するための手段】
【００１５】
本発明は前記課題を解決するために、以下の手段を採用した。すなわち、本発明は、入力されるデジタルデータに対して数値演算または論理演算を実行し、数値演算または論理演算の出力信号を出力する、そのような１以上の演算素子と、前記演算素子の入力側に接続されるネットワーク出力端子と、前記演算素子の出力信号または前記演算素子の出力信号以外の外部信号が入力されるネットワーク入力端子と、前記ネットワーク入力端子をネットワーク出力端子に接続するネットワーク部と備え、前記ネットワーク部は、第１のネ
ットワーク入力端子を第１のネットワーク出力端子に接続したときに、第２のネットワーク入力端子をいずれかの第２のネットワーク出力端子にさらに接続することができない、そのようなネットワーク入力端子とネットワーク出力端子との組合せに対する制約が存在する閉塞ネットワーク網を構成し、前記ネットワーク出力端子のうちの２つのネットワーク出力端子が同時に接続することができないネットワーク入力端子の組に含まれるネットワーク入力端子数として定義される制約強度について、同一の演算素子に入力される複数の出力端子間の制約強度が最小となるように、前記演算素子とネットワーク出力端子とを接続した回路である。
【００１６】
前記回路は、さらに、前記演算素子のうち、互換性のある複数の演算素子に接続されるネットワーク出力端子間の制約強度が最小となるように、前記演算素子とネットワーク出力端子とを接続してもよい。
【発明の効果】
【００１７】
本発明によれば、閉塞ネットワークを利用した回路において、従来よりも多くのアプリケーションを実装することができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面を参照して本発明を実施するための最良の形態（以下、実施形態という）に係るリコンフィギュラブル回路について説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１９】
《発明の骨子》
本リコンフィギュラブル回路は、プロセッシングエレメント（本発明の演算素子に相当）として互換性のない複数種類のプロセッシングエレメントを接続したネットワークを想定する。そこで、本実施形態では、プロセッシングエレメントの入力の論理的互換性、およびプロセッシングエレメント間の論理的互換性を考慮して、基本閉塞ネットワーク網で接続することにより、一度に搭載できるアプリケーションの対象を拡大する回路構造を提案する。ここで、基本閉塞ネットワーク網は、ベースライン網や3キューブネットワーク
網といった３段のｎ×mのクロスバースイッチングブロック（以下、単にスイッチブロッ
クともいう）で構成したネットワークを想定する。
【００２０】
本リコンフィギュラブル回路は、２つの端子間における制約の強さを距離として表現すると、以下の２つの評価基準を達成するようにプロセッシングエレメントを接続する。
（評価基準１）各プロセッシングエレメントの入力端子間における距離が最小になるように接続する。なお、本実施形態では、各プロセッシングエレメントの入力端子間の代わりにその入力端子が接続されるネットワーク側の出力端子を用いて計算する場合がある。その場合に、上記評価基準１は、「各プロセッシングエレメントの入力端子に接続されるネットワーク側出力端子間における距離が最小になるように接続する。」と言い換えることができる。すなわち、本実施形態では、各プロセッシングエレメントの入力端子とその入力端子に接続されるネットワーク側の出力端子とは、等価なものとして取り扱う。
（評価基準２）互換性のあるプロセッシングエレメントの入力端子間の距離が最小になるように接続する。この評価基準２は、「互換性のあるプロセッシングエレメントの入力端子に接続されるネットワーク側出力端子間の距離が最小になるように接続する」と言い換えることができる。
【００２１】
ここで、２つの最終段スイッチブロックの出力端子（または、その出力端子に接続されるプロセッシングエレメントの入力端子）ＴｉおよびＴｊの制約の強さを表す距離ＬＴ（ｉ，ｊ）を以下のように定義する。距離ＬＴ（ｉ，ｊ）が、本発明の制約強度に相当する。
【００２２】
ＬＴ（i,j）＝ＴｉおよびＴｊが同時に接続することができないネットワークの入力端
子数；
またプロセッシングエレメントＰｋおよびＰｌの間の距離ＬＰ（ｋ，ｌ）を以下のように定義する。
【００２３】
ＬＰ（k,l）＝ΣＬＴ（i,j）；
Tiの接続先∈Pk,Tjの接続先∈Pl
これらの定義により、先ほどの評価基準１、２を表すと、以下の２つの関数がそれぞれ最小となるように接続することになる。優先度は、上から順に高いとする。
【００２４】
F1()=Σ（                ΣＬＴ(i, j)        ）;
kはすべての演算素子  Ti,Tjの接続先∈Pk
F2()=Σ（                  ΣＬＰ(k, l)        ）;
すべての演算素子の種類  Pk,Plは同一種類の演算素子
《第１実施例》
実施例として、図２の８入力８出力の間接バイナリ３キューブネットワークを例にとる。このネットワークでは、端子間の距離は以下のようになる。
【００２５】
ＬＴ(i,j)＝４；（ＴｉおよびＴｊが図２の第３段目の同じクロスバースイッチブロッ
クの出力端子である場合）
ＬＴ(i,j)＝２；（ＴｉおよびＴｊが図２の第１段目のいずれかの１つのクロスバース
イッチブロックの１つの出力端子から到達可能な第３段目のクロスバースイッチブロックの出力端子である場合）；
ＬＴ(i,j)＝０；（上記以外の場合）
このような基本閉塞ネットワークを使用して、加算器２個（２入力１出力）、乗算器２個（２入力１出力）、外部入力２つ、レジスタ２つを接続する場合を考える。
【００２６】
今、図２において、Ｚ１からＺ４の出力端子グループをＧ１、Ｚ５からＺ８の出力端子グループをＧ２とする。評価基準１にしたがって、関数Ｆ１が最小となるためには、加算器および乗算器のそれぞれの入力端子は別々のグループになるのがよい。
【００２７】
なぜなら、図４（Ｂ）に示したように、例えば、１つの加算器の２つの入力端子Ｔｉ，ＴｊがそれぞれＧ１、Ｇ２に割り当てられた場合には、これら２つの入力端子間の距離は、０となる。同様に、１つの乗算器の２つの入力端子Ｔｉ，ＴｊがそれぞれＧ１、Ｇ２に割り当てられた場合には、これら２つの入力端子間の距離は、０となる。
【００２８】
したがって、この例では、Ｇ１に４つの入力端子（４つのプロセッシングエレメントの入力端子Ｔｉ，Ｔｊのいずれか一方）、Ｇ２に４つの入力端子（４つのプロセッシングエレメントの入力端子Ｔｉ，Ｔｊの残りの他方）が割り当てられる。この場合、Ｆ１（  ）は０である。
【００２９】
次に、さらに、出力端子を分類し、Ｚ１とＺ２をｇ１、  Ｚ３とＺ４をｇ２、Ｚ５とＺ６をｇ３、Ｚ７とＺ８をｇ４の各グループとする（図４（Ａ）参照）。
【００３０】
２入力１出力のプロセッシングエレメントの入力端子（Ｔｉ，Ｔｊ）が接続されるグループの組合せのうち、同一プロセッシングエレメントの入力端子の距離が最小となる組み合わせは、（ｇ１，ｇ３），  （ｇ１，ｇ４），  （ｇ２，ｇ３），  （ｇ２，ｇ４）となる。
【００３１】
この場合において、上記評価基準２にしたがって２入力１出力のプロセッシングエレメントの入力端子の割り当てを進める。今、２つのプロセッシングエレメントが上記いずれかの組合せで接続しているとすると、そのプロセッシングエレメント間の距離は、図８のようになる。図８において、例えば、ＰＥ１は、１つ目の加算器であり、ＰＥ２は、２つ目の加算器である。あるいは、ＰＥ１は、１つの乗算器であり、ＰＥ２は、２つ目の乗算器である。
【００３２】
したがって、加算器２個（および乗算器２個）の入力を（ｇ１，ｇ３）と（ｇ２，ｇ４）にするか、または（ｇ１，ｇ４）と（ｇ２，ｇ３）にすると、２つの加算器の入力端子間の距離の和は、４となり、２つの乗算器の入力端子間の距離の和は、４となる。
【００３３】
次に、このような手順によって設定されるネットワークが実装可能なアプリケーションの割合（以下、実装率という）を求めてみる。ここでは、乗算器２個、加算器２個が接続される出力に対して、８つの出力信号を割り当てる場合の実装率を求める。
【００３４】
なお、図２のネットワークにおいて、各入力端子（Ｘ１〜Ｘ８）に入ってくる信号が、いずれかのプロセッシングエレメントの入力端子に入力するとして、その組合せ数は８８＝１６７７７２１６通りである。
【００３５】
図９に、本実施形態によるネットワークの構成例を示す。また、図１０に、端子間の依存を考慮しない、すなわち、上記（評価基準１）（評価基準２）を考慮しないネットワークの接続例を示す。
【００３６】
図９に示したように、各入力端子に０００〜１１１の３ビットの識別情報を割り当てる。また、各出力端子に０００〜１１１の３ビットの識別情報を割り当てる。
【００３７】
ここで、入力端子番号、出力端子番号、ネットワークパターンを以下のように定義する。
Ak（ｋ＝０〜７）：３ビットで表現される入力端子の番号であり、図９の０００〜１１１である。
Bk（ｋ＝０〜７）：３ビットで表現される出力端子の番号であり、図９の０００〜１１１である。
Pk（ｋ＝０〜７）：２４ビットで表されるネットワークパターンの数値表現である。Pkの３ｋビット目から３ｋ+2ビット目までの３ビットp3k+2p3k+1p3kはBkの出力端子に接続す
る入力端子の番号を示す。ここで、kは３ビットごとのビット位置を示す番号である。
【００３８】
このような出力端子と入力端子の定義に対して、２つの乗算器と２つの加算器を出力端子に接続する回路の実装率を算出する計算プログラムの処理を説明する。このプログラムは、ＣＰＵ、メモリ、表示手段（ディスプレイ）、および入力手段（キーボード、マウス等）等を備えた一般的なコンピュータで実行可能である。
図１１に計算プログラムのフローチャートを示す。
【００３９】
まず、コンピュータは、未実装ネットワークパターン数を示すC0と実装可能なネットワークパターン数を示すC1を0に初期化する（Ｓ１）。
【００４０】
次に、コンピュータは、16777216（＝224）通りのネットワークパターンから順次１つ
を選んで（Ｓ２）、実装の可能性を検証する（Ｓ３）。まず、P0=00000000(8)（添え字の(8)は8進数であることを示す）を選択したとする。これは、すべての出力端子に0(8)=000(2)の番号の入力端子を接続するパターンである。実装性の検証は以下の２つの閉塞規則
にしたがってチェックする。
【００４１】
（閉塞規則１）Bkに接続する入力端子p3k+2p3k+1p3kと、Bk+1に接続する入力端子p3k+5p3k+4p3k+3とについて、上位１ビット（p3k+2とp3k+5）が同じで、かつ下位２ビット（p3k+1p3kとp3k+4p3k+3）が異なる場合には実装できない。
【００４２】
この規則は、図４（Ａ）に示す第１のブロッキング特性「第３段目のそれぞれのスイッ
チブロックの２つの出力端子（図２におけるＺ１とＺ２、Ｚ３とＺ４、Ｚ５とＺ６、およびＺ７とＺ８のそれぞれの組）は、そのスイッチブロックの入力端子の１つにつながっているネットワーク入力端子の組（図２におけるＸ１〜Ｘ４の組またはＸ５〜Ｘ７の組）の中の異なる２つのネットワーク入力端子に同時に接続することはできない」を出力端子Bkに接続されるビットパターンで表現したものである。
【００４３】
（閉塞規則２）Bk、Bk+1、Bk+2およびBk+３に接続する入力端子であるp3k+2p3k+1p3k、p3k+5p3k+4p3k+3、p3k+8p3k+7p3k+6およびp3k+11p3k+10p3k+9において、上位２ビットが
同じで、かつ下位１ビット異なるものが存在する場合には実装できない。
【００４４】
この規則は、図４（Ｂ）に示す第２のブロッキング特性「第１段目のそれぞれスイッチブロックの１つ出力端子に接続されている第３段目の出力端子の組（図２におけるＺ１〜Ｚ４の組またはＺ５〜Ｚ８の組）は、その第１段目のスイッチブロックの異なる２つ入力端子（図２におけるＸ１とＸ２、Ｘ３とＸ４、Ｘ５とＸ６、およびＸ７とＸ８のそれぞれの組）に同時に接続することはできない」を出力端子Bk、Bk+1、Bk+2およびBk+３に接続
されるビットパターンで表現したものである。
【００４５】
この検証によって、上記閉塞規則１および閉塞規則２のいずれにも該当しない場合、コンピュータは、実装可と判定する。そこで、コンピュータは、実装可能なネットワークパターン数を示すC1をインクリメントする（Ｓ７）。
【００４６】
一方、上記閉塞規則１および閉塞規則２のいずれかに該当する場合、コンピュータは、同一プロセッシングエレメントの互換性のある入力端子への接続の入れ替えを実施し（Ｓ４）、再度上記閉塞規則１および閉塞規則２による検証を再度実行する（Ｓ３）。これは、同一プロセッシングエレメントの入力端子へのネットワーク側出力端子の入れ替えによって、ブロッキング特性を解消し、実装できなかったアプリケーションが実装できるようになる場合もあるからである。このようにして、アプリケーションの実装が可能と判定された場合、コンピュータは、Ｓ７に処理を進める。
【００４７】
一方、このようにしてすべての入れ替え可能な組合せに対して検証が修了すると、コンピュータは、同一プロセッシングエレメントの入力端子へのネットワーク側出力端子の入れ替えによっては、アプリケーションの実装ができないと判定する。そして、コンピュータは、処理をＳ５に進める。
【００４８】
そして、同一のタイプの他のプロセッシングエレメント（例えば、加算器１と加算器２、乗算器１と乗算器２等）との間で接続の入れ替えを実施し（Ｓ５）、再度上記閉塞規則１および閉塞規則２による検証を再度実行する（Ｓ３）。これは、同一のタイプのプロセッシングエレメントの入力端子へのネットワーク側出力端子の入れ替えによって、ブロッキング特性を解消し、実装できなかったアプリケーションが実装できるようになる場合もあるからである。このようにして、アプリケーションの実装が可能と判定された場合、コンピュータは、Ｓ７に処理を進める。
【００４９】
一方、このようにしてすべての入れ替え可能な組合せに対して検証が修了すると、コンピュータは、同一種類のプロセッシングエレメントの入力端子へのネットワーク側出力端子の入れ替えによっては、アプリケーションの実装ができないと判定する。そして、コンピュータは、処理をＳ６に進める。コンピュータは、未実装ネットワークパターン数を示すC0をインクリメントする（Ｓ６）。
【００５０】
例えば、P0=00000000(8)のパターンは上記２つの規則に当てはまる組合せはないため実装可能となる。それに対し、P4196672=10004500(8)ではB４とB5とへの接続入力端子は4=1
00(2)と5=101(2)であり、閉塞規則１に該当するため実装できない。しかしながら、図９
では、B0とB4は乗算器１の入力端子であるため、交換可能である。そこで、フローチャートの「同一プロセッシングエレメントの互換性のある入力端子への接続の入れ替え」を実施し、再度実装性について検証すると、実装可能であることが判明する。なぜなら、B0へ接続される入力端子は１＝001(2)であり、B5への接続入力端子5=101(2)とは、閉塞規則１に該当しないからである。これによりP4196672=10004500(8)と互換性のある回路の実装が可能であることがわかる。
【００５１】
このようにしてすべてのパターンについて検証後、コンピュータは、実装可能なパターン数を全ネットワークパターン数（８８＝１６７７７２１６）で除算する（Ｓ８）。以上の処理により、与えられた演算子による回路の実装率を計算することができる。
【００５２】
図１２に、各方式に対して実装率を求めた結果を示す。この数値は、図１１の処理を実行するコンピュータプログラムにより求めた値である。図１２において、「互換性を未考慮」とは、プロセッシングエレメントの端子間および同一タイプのプロセッシングエレメントの端子間の互換性を一切考慮せずに接続する場合、すなわち図１０のネットワークでの実装率である。
【００５３】
また、図１２の「PEの入力を交換」とは、図７のように１つのプロセッシングエレメント、例えば、加算器１の２つの入力端子を同一のクロスバースイッチブロックから接続せず、隣接するクロスバースイッチブロックに割り当てた場合である。
【００５４】
また、「提案法に基づく接続」とは、上記評価基準１および評価基準２にしたがって、構成した場合、すなわち図９のネットワークでの実装率である。
【００５５】
図１２に示すように、図１０のようなプロセッシングエレメントの互換性を考慮しない場合には、８個の入力を乗算器２個および加算器２に接続する間接バイナリ３キューブネットワークによるアプリケーションの実装率は、非閉塞ネットワークによる全接続数１６７７７２１６通りの１２．９パーセントである。また、図７に示すようなプロセッシングエレメントの入力を交換した間接バイナリ３キューブネットワークでは、実装率は、１９．９パーセントである。
【００５６】
一方、図９に示すようなプロセッシングエレメントの互換性を考慮し、（評価基準１）および（評価基準２）にしたがって、ネットワークを構成した場合には、実装率は、６２．８パーセントに高まる。これは、（評価基準１）および（評価基準２）によって１つのプロセッシングエレメント内および同一種類のプロセッシングエレメント間の制約が少なくなるようにネットワークが構成される結果、図１１の実装率算出のフローにおいて同一のプロセッシングエレメントの入力端子間あるいは同一種類のプロセッシングエレメント間の入力端子間で入れ替えにより実装可能な組合せが増加するからである。
《第２実施例》
他の例として４入力４出力のクロスバースイッチを基本ブロックとし、それらを３段接続して構成した６４入力６４出力の間接３キューブネットワークを例に本発明を適用した例を説明する。図１３は、４入力４出力のクロスバースイッチによる６４入力６４出力の間接３キューブネットワークの例である。
【００５７】
このネットワークでは、３段目の基本ブロックの出力端子は、その基本ブロック１つの入力端子につながる１６のネットワーク入力端子（例えば、ライン１００につながる基本ブロックＭa００〜Ｍa０３の入力端子）の中から１つにしか接続できない。
【００５８】
また、１段目の基本ブロックの１つの出力（例えば、ライン１０１につながる出力）は
１６のネットワーク出力端子（例えば、Ｍa２０〜Ｍa２３の１６個の出力端子）につながっているため、これらの１６のネットワーク出力端子は、１段目の各基本ブロックの４つの入力端子から１つしか選択することはできない。
【００５９】
すなわち、図１３では、３段目のＭｘ２０からＭｘ２３（ｘは、ａ，ｂ，ｃ，ｄのいずれか）のグループが、１段目の基本ブロックの１つの出力端子から接続しているグループである。また、一段目のＭｘ００からＭｘ０３（ｘは、ａ，ｂ，ｃ，ｄのいずれか）のグループが、３段目の基本ブロックの１つの入力端子に接続されている基本ブロックである。これにより、端子間の距離は以下のようになる。
【００６０】
ＬＴ(i,j)＝１６；（ＴｉおよびＴｊが図１３の第３段目のいずれかの基本ブロックの
２つの出力端子である場合）
ＬＴ(i,j)＝４；（ＴｉおよびＴｊが図１３の第１段目のいずれかの基本ブロックの１
つの出力端子から到達可能な第３段目の基本ブロックの出力端子である場合）；
ＬＴ(i,j)＝０；（上記以外の場合）
今、このネットワークに対してＡＬＵ（２入力１出力）１４個、乗算器（２入力１出力）４個、内部メモリ（２入力１出力）４個、レジスタファイル４個（４入力８出力）、外部出力４、外部入力４をつなげる場合を考える。
【００６１】
Ｍｘ２０からＭｘ２３（ｘは、ａ，ｂ，ｃ，ｄ）の出力端子のグループをＧｘとし、基本ブロック１個であるＭｘ２ｙ（ｘは、ａ，ｂ，ｃ，ｄのいずれか、ｙは０から３のいずれか）の出力端子のグループをｇｘｙと表す。
【００６２】
まず４入力レジスタファイルについて考える。レジスタファイルの入力端子間の距離が最小になるためには、それぞれの入力端子がグループＧａからＧｄに１個づつ割り当てられればよい。つまり４個のレジスタファイルについてそれぞれの入力端子を（Ｇ１，Ｇ２，Ｇ３，Ｇ４）という組に分散して割り当てることになる。
【００６３】
次に２入力プロセッシングエレメント（乗算器、内部メモリ、ＡＬＵ（加算器））について考える。入力端子を割り当てる組合せは（Ｇ１，Ｇ２），（Ｇ１，Ｇ３），（Ｇ１，Ｇ４），（Ｇ２，Ｇ３），（Ｇ２，Ｇ４），（Ｇ３，Ｇ４）の６つがある。これらの組合せに対する入力端子間の最小距離を図１４に示す。
【００６４】
この図は、２入力のプロセッシングエレメントの入力端子を図１３のネットワークの出力端子に割り当てる場合の距離を示している。２つの入力端子をグループＧ１とＧ２との間、Ｇ３とＧ４の間、Ｇ１とＧ３の間、Ｇ２とＧ４の間、Ｇ１とＧ４の間およびＧ２とＧ３に割り当てた場合には、それぞれ距離が０であることを示している。
【００６５】
また、同一種類の２個のプロセッシングエレメントの４つの入力端子がすでに（Ｇ１、Ｇ２）の組、および（Ｇ３、Ｇ４）の組に接続されている場合に、さらに、同一種類の２入力のプロセッシングエレメントを１個割り当てる場合を考える。この場合、そのプロセッシングエレメントの２つの入力端子を他のいかなる組合せのグループの組（Ｇ１、Ｇ３）（Ｇ２、Ｇ４）（Ｇ１、Ｇ４）（Ｇ２、Ｇ３）の組に割り当てたとしても、距離４の制約が発生することを示している。
【００６６】
また、例えば、すでに、プロセッシングエレメントの２つの入力端子が（Ｇ１、Ｇ２）の組に接続されている場合に、さらに、同一種類のプロセッシングエレメントの２つの入力端子を同一の組（Ｇ１、Ｇ２）に割り当てた場合には、距離８の制約が発生することを示している。これは、他の組（Ｇ３，Ｇ４）、（Ｇ１，Ｇ３），（Ｇ１，Ｇ４），（Ｇ２，Ｇ３），（Ｇ３，Ｇ４）についても同様である。
【００６７】
この図から、互いの端子間の距離が短くなるように、接続するには、（Ｇ１，Ｇ２）⇒（Ｇ３，Ｇ４）⇒（Ｇ１，Ｇ３）⇒（Ｇ２，Ｇ４）⇒（Ｇ１，Ｇ４）⇒（Ｇ２，Ｇ３）⇒（Ｇ１，  Ｇ２）⇒・・・と順番に繰り返し割り当てるのがよい。これにしたがって、乗算器、内部メモリ、ＡＬＵ（加算器）をそれぞれ割り当てる。
【００６８】
次に各グループＧ１〜Ｇ４に割り当てられた４個のレジスタファイルの入力端子をグループｇｘｙへの割り当てを考える。このとき、各レジスタファイルの入力を異なるｇｘｙに割り当てると、各ｇｘｙのうち、同一のグループＧ１〜Ｇ４に属する入力端子は、距離が４であり、このような入力端子が各グループに４つあり、４グループあるので、それぞれのレジスタファイル間の距離は、４×４×４＝６４で最小となる。
【００６９】
また、乗算器（２入力端子×４個＝８入力端子）は、１つのグループＧｘ内に高々２つとなるような割り当てが可能なので、グループｇｘｙを分けることができる。内部メモリ（２入力端子×４個＝８入力端子）についても同様である。そのため、同じグループＧｘに割り当てられたＲＡＭまたは乗算器については、最大距離を４（同一のグループＧ１〜Ｇ４に属するので距離４）とすることができる。
【００７０】
一方、ＡＬＵ（２入力端子×１４個＝２８入力端子）については、同じグループに平均６個程度（２８／４）の端子が割り当てられるため、少なくとも２つの端子は同じｇｘｙに割り当てる必要がある。そこで、ＡＬＵについては、１つのｇｘｙに割り当てられる端
子数が１ないし２となるように割り当てればよい。
このようにして、各プロセッシングエレメントの入力端子を図１３のネットワークの出力端子にアサインした例を図１５に示す。
【００７１】
ここで、Ｒ１−１〜Ｒ１−４は、レジスタファイルＲ１の入力端子１〜４を示している。したがって、図１５では、Ｇ１〜Ｇ４の各グループにレジスタファイルＲ１の入力端子１〜４がそれぞれ配分され、ｇｘ０（ｘ＝ａ〜ｄ）に接続されることを示している。Ｒｋ−１〜Ｒｋ−４（ｋ＝２〜４）も同様である。また、ＡＬＵｋ−ＡおよびＡＬＵｋ−Ｂ（ｋ＝１〜１４）は、１４個のＡＬＵのそれぞれの２つの入力端子を示している。また、ＭＵＬｋ−ＡおよびＭＵＬｋ−Ｂ（ｋ＝１〜４）は、４個の乗算器のそれぞれの２つの入力端子を示している。また、ＲＡＭｋ−ＡおよびＲＡＭｋ−Ｂ（ｋ＝１〜４）は、４個の内部メモリのそれぞれの２つの入力端子を示している。さらに、ＥＯｋ（ｋ＝１〜４）は、外部出力である。
【００７２】
このような手順により、４入力４出力のクロスバースイッチを３段接続して構成した６４入力６４出力の間接３キューブネットワークに対しても、制約を最小限とする構成を実現できる。
【００７３】
すなわち、評価基準１および２は、基本ブロックであるクロスバースイッチブロックの端子数に限定なく適用でき、間接バイナリキューブ以外のネットワークについても、評価基準１および２にしたがってネットワークを構成することで、アプリケーションの実装率を改善できる。
【００７４】
《変形例》
上記第１実施形態および第２実施形態では、いずれも基本ブロックの行を３段組み合わせて構成されるネットワークの３段目の出力端子に異なる種類のプロセッシングエレメントを接続する場合において、アプリケーションの実装率を改善できる構成を説明した。しかし、本発明の実施は、そのような構成には、限定されない。
【００７５】
例えば、プロセッシングエレメントを複数独立のグループに区分し、それぞれのグループ（例えば、第１グループと第２グループ）ごとにネットワークを構成し、それらの複数のグループのネットワークの組合せからなるアプリケーションについても本発明を実施できる。すなわち、個々のグループごとに上記評価基準１および２を適用し、個々のグループの実装率を改善することで、複数グループのネットワークからなるアプリケーションの実装率を改善できる。そのようなネットワークの構成例を図１６および図１７に示す。
【００７６】
図１６は、複数のグループからなるプロセッシングエレメントの各々のグループを並列に接続しネットワーク（第１列のネットワークおよび第２列のネットワーク）を構成している。図１６では、第１のグループ〜第２のグループのプロセッシングエレメントが図示されている。
【００７７】
図１６では、第１のネットワークは、第１のグループと第２のグループのプロセッシングエレメントを入力とし、第１のグループのプロセッシングエレメントを出力として接続している。また、第２のネットワークは、第１のグループと第２のグループのプロセッシングエレメントを入力とし第２のグループのプロセッシングエレメントを出力として接続している。
【００７８】
このような場合でも、第１のネットワーク、第２のネットワークそれぞれにおいて、評価基準１および評価基準２を満足するように、ネットワークを構成することで、アプリケーションの実装率を向上できる。３以上のネットワークを並列に接続する構成でも構わないし、他のネットワークと並列に接続する構成でも構わない。
【００７９】
図１７は、複数のグループからなるプロセッシングエレメントの各々のグループ（第１段目のネットワークおよび第２段目のネットワーク）を直列にネットワークを構成している。図１７では、第１のグループ、第２のグループのプロセッシングエレメントが図示されている。
【００８０】
図１７では、第１段目のネットワークは、第１のグループのプロセッシングエレメントと第２のグループのプロセッシングエレメントを接続している。また、第２段目のネットワークは、第２のグループのプロセッシングエレメントと第１のグループのプロセッシングエレメントを接続している。この場合、第１段目のネットワーク、第２段目のネットワークそれぞれにおいて、評価基準１および評価基準２を満足するように、ネットワークを構成することで、アプリケーションの実装率を向上できる。
【００８１】
なお、図１７のように直列に接続する場合に、第１段目のネットワークと第２段目のネットワークの間に、他のネットワークが介在してもよい。すなわち、第１段目のネットワークが、第１のグループのプロセッシングエレメントと第２のグループのプロセッシングエレメントを接続し、第２段目のネットワークが、第３のグループのプロセッシングエレメントと第１のグループのプロセッシングエレメントを接続し、さらに、第２のグループと第３のグループの間に他のネットワークが存在しても構わない。また、３以上のネットワークを直列に接続する構成でも構わない。
【図面の簡単な説明】
【００８２】
【図１】３段のＣｌｏｓネットワークの例
【図２】８入力８出力の間接バイナリ３キューブネットワークの例
【図３】クロスバースイッチブロックの接続設定例
【図４】ブロッキング特性の例
【図５】間接バイナリ３キューブネットワークを適用したリコンフィギュラブル回路の例
【図６】アプリケーションにおけるブロッキング特性の例
【図７】間接バイナリ３キューブネットワークを適用したアプリケーションにおけるブロッキング特性の例
【図８】第１実施形態の場合のプロセッシングエレメント間の距離の計算例
【図９】プロセッシングエレメント間の互換性を考慮した間接バイナリ３キューブネットワークの例
【図１０】プロセッシングエレメント間の互換性を考慮しない間接バイナリ３キューブネットワークの例
【図１１】回路の実装率を算出する計算プログラムの処理を示すフローチャート
【図１２】実装率算出結果の例
【図１３】４入力４出力のクロスバースイッチによる６４入力６４出力の間接３キューブネットワークの例
【図１４】プロセッシングエレメント間の最低距離を示す図
【図１５】４入力４出力のクロスバースイッチによる６４入力６４出力の間接３キューブネットワークにプロセッシングエレメントを割り当てた例
【図１６】複数のグループからなるプロセッシングエレメントの各々のグループを並列に接続するネットワーク（第１のネットワークおよび第２のネットワーク）の構成例
【図１７】複数のグループからなるプロセッシングエレメントの各々のグループを直列に接続するネットワークの構成例
【図１】
0004804829.tif 000002
【図２】
0004804829.tif 000003
【図３】
0004804829.tif 000004
【図４】
0004804829.tif 000005
【図５】
0004804829.tif 000006
【図６】
0004804829.tif 000007
【図７】
0004804829.tif 000008
【図８】
0004804829.tif 000009
【図９】
0004804829.tif 000010
【図１０】
0004804829.tif 000011
【図１１】
0004804829.tif 000012
【図１２】
0004804829.tif 000013
【図１３】
0004804829.tif 000014
【図１４】
0004804829.tif 000015
【図１５】
0004804829.tif 000016
【図１６】
0004804829.tif 000017
【図１７】
0004804829.tif 000018