(57)【特許請求の範囲】
【請求項１】
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成部と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減するリソース削減部と、を備える、再構成可能回路生成装置。
【請求項２】
前記複数のネットリスト及び前記共用ネットリストは、それぞれ演算ブロックと該演算ブロック間を接続するネットとを含み、
前記共用ネットリストは、前記複数のネットリストの間で共通部分に含まれるネットの数または演算ブロックの数が最大となるように生成したものである、請求項１に記載の再構成可能回路生成装置。
【請求項３】
前記再構成可能回路のリソースは、機能ブロックと該機能ブロック間を接続するルーティングリソースとを含み、
前記リソース削減部は、前記ルーティングリソースを削減する、請求項１又は２に記載の再構成可能回路生成装置。
【請求項４】
前記ネットリスト生成部は、さらに、複数のネットリストを複数のグループに分類する分類部と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして前記複数のグループのそれぞれについて生成する生成部とを備え、
前記リソース削減部は、前記再構成可能回路のリソースのうちの、前記複数のグループのそれぞれに対する共用ネットリストのいずれをも実装するのに必要なリソースのみを用いて、前記複数のグループのそれぞれに対する共用ネットリストを実装する、請求項１ないし３のいずれか１項に記載の再構成可能回路生成装置。
【請求項５】
前記ネットリスト生成部は、さらに、複数のネットリストを複数のグループに分類する分類部と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストとの差分を該共通部分に付加したネットリストを第１の共用ネットリストとして前記複数のグループのそれぞれについて生成する第１の生成部と、
前記複数のグループのそれぞれに対する第１の共用ネットリストの共通部分と該複数の第１の共用ネットリストとの差分を該共通部分に付加したネットリストを第２の共用ネットリストとして生成する第２の生成部とを備え、
前記リソース削減部は、前記再構成可能回路のリソースのうちの、前記第２の共用ネットリストを実装するのに必要なリソースのみを用いて、前記第２の共用ネットリストを実装する、請求項１ないし３のいずれか１項に記載の再構成可能回路生成装置。
【請求項６】
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成工程と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減する工程と、を含む、再構成可能回路生成方法。
【請求項７】
前記複数のネットリスト及び前記共用ネットリストは、それぞれ演算ブロックと該演算ブロック間を接続するネットとを含み、
前記共用ネットリストは、前記複数のネットリストの間で共通部分に含まれるネットの数または演算ブロックの数が最大となるように生成したものである、請求項６に記載の再構成可能回路生成方法。
【請求項８】
前記再構成可能回路のリソースは、機能ブロックと該機能ブロック間を接続するルーティングリソースとを含み、
前記実装工程において、前記ルーティングリソースを削減する、請求項６または７に記載の再構成可能回路生成方法。
【請求項９】
前記ネットリスト生成工程は、さらに、複数のネットリストを複数のグループに分類する工程と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして前記複数のグループのそれぞれについて生成する工程とを含み、
前記実装工程において、前記再構成可能回路のリソースのうちの、前記複数のグループのそれぞれに対する共用ネットリストのいずれをも実装するのに必要なリソースのみを用いて、前記複数のグループのそれぞれに対する共用ネットリストを実装する、請求項６ないし８のいずれか１項に記載の再構成可能回路生成方法。
【請求項１０】
前記ネットリスト生成工程は、さらに、複数のネットリストを複数のグループに分類する工程と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストとの差分を該共通部分に付加したネットリストを第１の共用ネットリストとして前記複数のグループのそれぞれについて生成する工程と、
前記複数のグループのそれぞれに対する第１の共用ネットリストの共通部分と該複数の第１の共用ネットリストのそれぞれとの差分を該共通部分に付加したネットリストを第２の共用ネットリストとして生成する工程とを含み、
前記実装工程において、前記再構成可能回路のリソースのうちの、前記第２の共用ネットリストを実装するのに必要なリソースのみを用いて、前記第２の共用ネットリストを実装する、請求項６ないし８のいずれか１項に記載の再構成可能回路生成方法。
【請求項１１】
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成処理と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減する処理と、をコンピュータに実行させる、プログラム。
【請求項１２】
前記複数のネットリスト及び前記共用ネットリストは、それぞれ演算ブロックと該演算ブロック間を接続するネットとを含み、
前記共用ネットリストは、前記複数のネットリストの間で共通部分に含まれるネットの数または演算ブロックの数が最大となるように生成したものである、請求項１１に記載のプログラム。
【請求項１３】
前記再構成可能回路のリソースは、機能ブロックと該機能ブロック間を接続するルーティングリソースとを含み、
前記実装処理において、前記ルーティングリソースを削減する処理をコンピュータに実行させる、請求項１１または１２に記載のプログラム。
【請求項１４】
前記ネットリスト生成処理において、さらに、複数のネットリストを複数のグループに分類する処理と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして前記複数のグループのそれぞれについて生成する処理とをコンピュータに実行させるとともに、
前記実装処理において、前記再構成可能回路のリソースのうちの、前記複数のグループのそれぞれに対する共用ネットリストのいずれをも実装するのに必要なリソースのみを用いて、前記複数のグループのそれぞれに対する共用ネットリストを実装する処理をコンピュータに実行させる、請求項１１ないし１３のいずれか１項に記載のプログラム。
【請求項１５】
前記ネットリスト生成処理において、さらに、複数のネットリストを複数のグループに分類する処理と、
前記複数のグループのそれぞれに含まれる複数のネットリストの共通部分と該複数のネットリストとの差分を該共通部分に付加したネットリストを第１の共用ネットリストとして前記複数のグループのそれぞれについて生成する処理と、
前記複数のグループのそれぞれに対する第１の共用ネットリストの共通部分と該第１の共用ネットリストのそれぞれとの差分と該共通部分に付加したネットリストを第２の共用ネットリストとして生成する処理とをコンピュータに実行させるとともに、
前記実装処理において、前記再構成可能回路のリソースのうちの、前記第２の共用ネットリストを実装するのに必要なリソースのみを用いて、前記第２の共用ネットリストを実装する処理をコンピュータに実行させる、請求項１１ないし１３のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２００８−３０４１６４号（２００８年１１月２８日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、再構成可能回路を生成する再構成可能回路生成装置、方法およびプログラムに関し、特に、適用範囲を限定した再構成可能回路を生成する再構成可能回路生成装置、方法およびプログラムに関する。
【背景技術】
【０００２】
ＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）やＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）などの再構成可能回路は、きわめて多様な回路を実現できることから広く用いられている。しかしながら、高い柔軟性を実現するために多くのスイッチや配線が使用されており、再構成可能回路は面積が大きく、コストも高いという問題がある。【０００３】
この問題を解決するために、再構成可能回路の適用範囲を限定し、その適用範囲をカバーするのに十分なだけの柔軟性を備えた再構成可能回路（以下、「用途限定再構成可能回路」という。）を用いることができる。用途限定再構成可能回路は、汎用の再構成可能回路と比較して柔軟性は低いものの、大幅に面積を削減することができるという利点がある。例えば、特許文献１および２において、用途限定再構成可能回路の生成方法が記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第７，０５１，３１３号明細書
【特許文献２】米国特許第６，６３１，５１０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
なお、上記特許文献の全開示内容はその引用をもって本書に繰込み記載する。以下の分析は、本発明によって与えられたものである。
図１２は、特許文献１および２に記載された用途限定再構成可能回路の生成方法のフローチャートを概略的に示す。【０００６】
図１２を参照すると、まず、再構成可能回路の初期アーキテクチャを作成する（ステップＳ２１）。次に、その初期アーキテクチャに対応した配置配線ツールを生成する（ステップＳ２２）。次に、配置配線ツールを使って初期アーキテクチャ上に、再構成可能回路に実装すべきアプリケーションに対するネットリストを配置配線する（ステップＳ２３）。さらに、ネットリストの配置配線結果を評価する（ステップＳ２４）。典型的な評価として、例えば、アーキテクチャ上にネットリストの配置配線ができたか否かの評価を行う。【０００７】
複数のアプリケーションを再構成可能回路に実装する場合には、各アプリケーションに対するネットリストについて、配置配線（ステップＳ２３）と評価（ステップＳ２４）を繰り返す。すべてのアプリケーションに対するネットリストの評価が終了した場合には（ステップＳ２５のＹＥＳ）、アーキテクチャ探索を続行するか否かを判定する（ステップＳ２６）。例えば、すべてのアプリケーションを配置配線することができた場合にはアーキテクチャ探索を続行し、それ以外の場合にはアーキテクチャ探索を終了するようにしてもよい。アーキテクチャ探索を続行する場合（ステップＳ２６のＹＥＳ）、再構成可能回路のアーキテクチャを変更して（ステップＳ２７）、再び、ステップＳ２２ないしＳ２５の工程を行う。アーキテクチャ変更として、例えば、再構成可能回路のプログラマブル配線の本数を変更したり、プログラマブルスイッチの数を変更したりしてもよい。【０００８】
以上の工程により、すべてのアプリケーションに対するネットリストを配置配線することができる範囲で再構成可能回路のリソースを削減した、用途限定再構成可能回路を生成することができる。【０００９】
特許文献１、２に記載された、上記の再構成可能回路生成法においては、処理時間が長くなるという問題がある。すべてのアプリケーションに対するネットリストを１つずつ配置配線して評価する場合には、アプリケーションの数に応じて配置配線を繰り返さなければならないからである。【００１０】
さらに、特許文献１、２に記載された再構成可能回路生成法によると、実装すべきネットリストの数が増加した場合に、再構成可能回路の面積を縮小することが難しいという問題がある。ネットリストを個別に配置配線し、すべてのネットリストを配置配線することができる範囲で再構成可能回路のリソースの削減を行っているからである。【００１１】
そこで、短時間で小面積の再構成可能回路を生成する方法を提供することが課題となる。本発明の目的は、かかる課題を解決する再構成可能回路生成装置、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第１の視点に係る再構成可能回路生成装置は、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成するネットリスト生成部と、前記共用ネットリストを実装することができる範囲で前記複数のネットリストを実装すべき再構成可能回路のリソースを削減するリソース削減部とを有する。【００１３】
本発明の第２の視点に係る再構成可能回路生成方法は、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成するネットリスト生成工程と、前記共用ネットリストを実装することができる範囲で前記複数のネットリストを実装すべき再構成可能回路のリソースを削減するリソース削減工程とを含む。【００１４】
本発明の第３の視点に係るプログラムは、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成するネットリスト生成処理と、前記共用ネットリストを実装することができる範囲で前記複数のネットリストを実装すべき再構成可能回路のリソースを削減するリソース削減処理とをコンピュータに実行させる。
本発明の第４の視点に係る再構成可能回路生成装置は、
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成部と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減するリソース削減部と、を備えている。
本発明の第５の視点に係る再構成可能回路生成方法は、
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成工程と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減する工程と、を含む。
本発明の第６の視点に係るプログラムは、
複数のネットリストの共通部分と該複数のネットリストのそれぞれとの差分を該共通部分に付加したネットリストを共用ネットリストとして生成するネットリスト生成処理と、
前記複数のネットリストを実装すべき再構成可能回路のリソースを、前記共用ネットリストが前記再構成可能回路に実装可能であるという条件下で削減する処理と、をコンピュータに実行させる。
【発明の効果】
【００１５】
本発明にかかる再構成可能回路生成装置、方法およびプログラムにより、短時間で小面積の用途限定再構成可能回路を生成することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係る再構成可能回路生成装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態に係る再構成可能回路生成方法のフローチャートである。
【図３】本発明の第３の実施形態に係るプログラムにおける処理を実行させるコンピュータの構成を示すブロック図である。
【図４】典型的な再構成可能回路の構成を示すブロック図である。
【図５】再構成可能回路を構成するセルの典型的な構成を示す回路図である。
【図６】セルを構成するマルチプレクサの典型的な構成を示す回路図である。
【図７】マルチプレクサを構成するスイッチの典型的な構成を示す回路図である。
【図８】本発明の実施例に係る再構成可能回路生成方法のフローチャートである。
【図９】（Ａ）第１のネットリストの例である。（Ｂ）第２のネットリストの例である。（Ｃ）共用ネットリストの例である。
【図１０】（Ａ）第１のネットリストを再構成可能回路に配置配線した結果を示す図である。（Ｂ）第２のネットリストを再構成可能回路に配置配線した結果を示す図である。（Ｃ）共用ネットリストを再構成可能回路に配置配線した結果を示す図である。
【図１１】用途限定再構成可能回路のリソース数のアプリケーション数依存性を示すグラフである。
【図１２】従来の用途限定再構成可能回路生成方法のフローチャートである。
【発明を実施するための形態】
【００１７】
（第１の実施形態）
本発明の実施形態に係る再構成可能回路生成装置について、図面を参照して説明する。図１は本実施形態に係る再構成可能回路生成装置の構成を示すブロック図である。
【００１８】
図１を参照すると、再構成可能回路生成装置６０は、ネットリスト生成部６１およびリソース削減部６２を有する。ネットリスト生成部６１は、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成する。リソース削減部６２は、共用ネットリストを実装することができる範囲で複数のネットリストを実装すべき再構成可能回路のリソースを削減する。
【００１９】
また、複数のネットリスト及び共用ネットリストは、それぞれ演算ブロックと該演算ブロック間を接続するネットとを含んでいてもよい。このとき、共用ネットリストは、複数のネットリストの間で可能な限りネットを共用化したものであることが好ましい。
【００２０】
さらに、再構成可能回路のリソースは、機能ブロックと機能ブロック間を接続するルーティングリソースとを含んでいてもよい。このとき、リソース削減部６２は、ルーティングリソースを削減することが好ましい。
【００２１】
ネットリスト生成部６１は、さらに、複数のネットリストを複数のグループに分類する分類部と、複数のグループのそれぞれに含まれる複数のネットリストの間で共用することができるネットリストを共用ネットリストとして複数のグループのそれぞれについて生成する生成部とを有することが好ましい。このとき、リソース削減部６２は、複数のグループのそれぞれに対する共用ネットリストをいずれも実装することができる範囲で再構成可能回路のリソースを削減することが好ましい。
【００２２】
ネットリスト生成部６１は、さらに、複数のネットリストを複数のグループに分類する分類部と、複数のグループのそれぞれに含まれる複数のネットリストの間で共用することができるネットリストを第１の共用ネットリストとして複数のグループのそれぞれについて生成する第１の生成部と、複数のグループのそれぞれに対する第１の共用ネットリストの間で共用することができるネットリストを第２の共用ネットリストとして生成する第２の生成部とを有することが好ましい。このとき、リソース削減部６２は、第２の共用ネットリストを実装することができる範囲で再構成可能回路のリソースを削減することが好ましい。
【００２３】
（第２の実施形態）
本発明の実施形態に係る再構成可能回路生成方法について、図面を参照して説明する。図２は本実施形態に係る再構成可能回路生成方法のフローチャートである。
【００２４】
図２を参照すると、まず、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成する（ステップＳ３１）。次に、共用ネットリストを実装することができる範囲で複数のネットリストを実装すべき再構成可能回路のリソースを削減する（ステップＳ３２）。
【００２５】
また、複数のネットリスト及び共用ネットリストは、それぞれ演算ブロックと演算ブロック間を接続するネットとを含んでいてもよい。このとき、共用ネットリストは、複数のネットリストの間で可能な限りネットを共用化したものであることが好ましい。
【００２６】
さらに、再構成可能回路のリソースは、機能ブロックと該機能ブロック間を接続するルーティングリソースとを含んでいてもよい。このとき、リソース削減工程（ステップＳ３２）において、ルーティングリソースを削減することが好ましい。
【００２７】
ネットリスト生成工程（ステップＳ３１）は、さらに、複数のネットリストを複数のグループに分類する工程と、複数のグループのそれぞれに含まれる複数のネットリストの間で共用することができる共用ネットリストを複数のグループのそれぞれについて生成する工程とを含むことが好ましい。このとき、リソース削減工程（ステップＳ３２）において、複数のグループのそれぞれに対する共用ネットリストをいずれも実装することができる範囲で再構成可能回路のリソースを削減することが好ましい。
【００２８】
ネットリスト生成工程（ステップＳ３１）は、さらに、複数のネットリストを複数のグループに分類する工程と、複数のグループのそれぞれに含まれる複数のネットリストの間で共通部分を抽出することにより、複数のネットリストを包含する第１の共用ネットリストを複数のグループのそれぞれについて生成する工程と、複数のグループのそれぞれに対する第１の共用ネットリストの間で共用することができるネットリストを第２の共用ネットリストとして生成する工程とを含むことが好ましい。このとき、リソース削減工程（ステップＳ３２）において、第２の共用ネットリストを実装することができる範囲で再構成可能回路のリソースを削減することが好ましい。
【００２９】
（第３の実施形態）
本発明の第３の実施形態に係る再構成可能回路を生成するためのプログラムについて図面を参照して説明する。図３は、本実施形態に係るプログラムにおける処理を実行させるコンピュータの構成を示すブロック図である。図３を参照すると、コンピュータ７０は、ＣＰＵ７１、記憶部７２、入力装置７３および出力装置７４を有する。
【００３０】
再構成可能回路生成プログラムは、共通部分を有する複数のネットリストの間で共用することができるネットリストを共用ネットリストとして生成するネットリスト生成処理と、共用ネットリストを実装することができる範囲で複数のネットリストを実装すべき再構成可能回路のリソースを削減するリソース削減処理とをコンピュータに実行させる。
【００３１】
第１ないし第３の実施形態においては、複数のネットリストが相互に最大限重ね合わせられるようにして、複数のネットリストの間で共用することができるネットリスト（すなわち、共用ネットリスト）を合成することが好ましい。また、この共用ネットリストを配置配線の対象とすることが好ましい。
【００３２】
第１ないし第３の実施形態に係る再構成可能回路生成装置、方法およびプログラムによると、適用範囲を限定した小面積の再構成可能回路を短い時間で生成することができる。その理由は、あらかじめ複数のネットリストの間で共用することができる共用ネットリストを作成し、その共用ネットリストが配置配線できる範囲で再構成可能回路のリソースを削減するからである。なお、複数ネットリストの各々は共用ネットリストの一部をとり除くことによって生成することができる。したがって、再構成可能回路に対して共用ネットリストを配置配線することができる場合には、共用ネットリストを共用する複数のネットリストのいずれも配置配線することができる。
【００３３】
また、複数のネットリストを再構成可能回路に対して個別に配置配線した場合には、ネットリストの数に応じて配置配線を行う必要がある。しかしながら、単一の共用ネットリストを用いる場合には、１回の配置配線によって、すべてのネットリストを再構成可能回路に配置配線できることが検証できる。これにより、特許文献１および２に記載された方法と比較して、用途限定再構成可能回路を短い時間で生成することができる。
【００３４】
さらに、共用ネットリストを用いる場合には、複数のネットリストの共通部分は再構成可能回路における同一のリソースに配置配線される。したがって、複数のネットリストの共通部分による使用リソースのばらつきが抑えられ、より多くのリソース削減が可能となる。ゆえに、共用ネットリストを用いることによって、小面積の用途限定再構成可能回路を実現することができる。
【実施例１】
【００３５】
本発明の第１の実施例について図面を参照して説明する。図４は、典型的な再構成可能回路の構成を示すブロック図である。【００３６】
図４を参照すると、再構成可能回路はセル１ＡＡ〜１ＣＣを有する。図４は、一例として、３行３列のセルアレイを示す。ただし、アレイのサイズは任意である。隣同士のセルは横方向配線３０及び縦方向配線３１で接続される。図４の横方向配線３０は、左右に隣接するセルを接続し、縦方向配線３１は上下に隣接するセルを接続する。図４は、一例として、隣接するセルを接続する配線の本数が２本である場合を示す。ただし、配線の本数は任意である。【００３７】
図５は、再構成可能回路を構成するセルの典型的な構成を示す回路図である。セル１は、縦方向に信号を伝送する配線３１Ａ、３１Ｂ、および横方向に信号を伝送する配線３０Ａ、３０Ｂと、コンフィギュレーションデータに応じて多様な機能を設定することができる機能ブロック５０と、コンフィギュレーションデータに応じて配線群３０Ａ、３０Ｂ、３１Ａ、３１Ｂから機能ブロック５０への入力信号を選択するマルチプレクサ２０Ｅ、２０Ｆと、コンフィギュレーションデータに応じて配線群３０Ａ、３０Ｂ、３１Ａ、３１Ｂの配線間、あるいは機能ブロック５０の出力と配線間を接続するマルチプレクサ２０Ａ、２０Ｂ、２０Ｃ、２０Ｄとを有する。【００３８】
図６は、図５のセル１を構成するマルチプレクサ２０の典型的な構成を示す回路図である。マルチプレクサ２０の複数の入力信号線７は、それぞれスイッチ２Ａないし２Ｄの一端に接続される。スイッチ２Ａないし２Ｄの他端はバッファ８の入力に接続される。バッファ８の出力は出力信号線９に出力される。【００３９】
図７は、図６のマルチプレクサ２０を構成するスイッチ２の典型的な構成を示す回路図である。トランスミッションゲート６の両側の端子８０及び８１の間を接続状態にするか否かは、コンフィギュレーションメモリ５に記録されたコンフィギュレーションデータによって決定される。【００４０】
なお、上記の再構成可能回路の構成は一例に過ぎない。マルチプレクサの入力数は任意である。また、入力数の異なるマルチプレクサが混載されていてもよい。さらに、マルチプレクサの構成としては、上記のもの以外にも多くの構成が知られており、いずれのマルチプレクサを使用してもよい。また、機能ブロックの入力数や、配線の本数、配線の長さも上述した例に限定されない。【００４１】
次に、本発明の実施例について説明する。図８は、本発明の実施例に係る再構成可能回路生成方法のフローチャートである。【００４２】
図８を参照すると、まず、複数のネットリストの共通箇所をできる限り重ね合わせて、複数のネットリストの間で共用することができる共用ネットリストを生成する（ステップＳ１１）。次に、出発点となる再構成可能回路のアーキテクチャ、すなわち初期アーキテクチャを生成する（ステップＳ１２）。初期アーキテクチャは、配線やスイッチなどのルーティングリソースを豊富に備えた再構成可能回路であって、任意のネットリストを実装することができるものである。【００４３】
次に、初期アーキテクチャの構成を考慮した配置配線ツールを生成する（ステップＳ１３）。次に、配置配線ツールを用いて、初期アーキテクチャ上に、ステップＳ１１において生成した共用ネットリストを配置配線する（ステップＳ１４）。次に、共用ネットリストの配置配線結果を評価する（ステップＳ１５）。評価は、例えば、配置配線できたか否かに基づいて行ってもよい。また、評価は、配置配線ができた場合のアプリケーション回路の最大遅延や消費電力、配置配線ができた場合の再構成可能回路のスイッチ数や回路面積、あるいはそれらの組み合わせ（例えば、回路面積と遅延との積）に基づいて行ってもよい。いずれの評価方法を用いるかは、設計者の目的に応じて決められる。【００４４】
次に、評価結果に基づいて、再構成可能回路のアーキテクチャ探索を継続する否かを判定する（ステップＳ１６）。アーキテクチャの探索を継続するか否かは、設計者が決めた条件に従って決定される。例えば、配置配線ができなかった場合、または遅延の改善が見られなくなった場合に、アーキテクチャの探索を終了（ステップＳ１６のＮＯ）するようにしてもよい。【００４５】
アーキテクチャ探索を継続する場合には（ステップＳ１６のＹＥＳ）、再構成可能回路のアーキテクチャを変更した（ステップＳ１７）後、変更後のアーキテクチャを用いて、ステップＳ１３以降の工程を行う。アーキテクチャ変更（ステップＳ１７）として、例えば、図５のマルチプレクサ２０のスイッチ（図６の２Ａないし２Ｄ）の一部を削除し、または図４のセル間を繋ぐ配線の一部を削除してもよい。【００４６】
以上により、すべてのネットリストを配置配線することができる範囲で、可能な限りルーティングリソースを削減した再構成可能回路を生成することができる。【００４７】
図９は、複数のネットリストを重ね合わせて共用ネットリストを生成する方法について説明するための図である。図９（Ａ）は第１のネットリスト１０を示す。図９（Ａ）を参照すると、ネットリスト１０の演算ブロック１０＿１ｉ（ｉは整数）は、それぞれ再構成可能回路の１つのセル１の機能ブロック５０（図５）に割り当てられる。図９（Ａ）において、各演算ブロック１０＿１ｉに付した符号Ａ〜Ｅは、演算の種類を示す。ネット１０＿２ｉ（ｉは整数）は、ネットリスト１０の演算ブロック間を繋ぐ配線、またはネットリスト１０の入出力信号線に対応する。【００４８】
図９（Ｂ）は、第２のネットリスト１１の例である。図９（Ｂ）を参照すると、ネットリスト１１の演算ブロック１１＿１ｉ（ｉは整数）は、それぞれ再構成可能回路の１つのセル１の機能ブロック５０（図５）に割り当てられる。図９（Ｂ）において、各演算ブロック１１＿１ｉに付した符号Ａ〜Ｅは、演算の種類を示す。ネット１１＿２ｉ（ｉは整数）は、ネットリスト１１の演算ブロック間を繋ぐ配線、またはネットリスト１１の入出力信号線に対応する。【００４９】
図９（Ｃ）は、第１のネットリスト１０と第２のネットリスト１１を重ね合わせた共用ネットリスト１２の例である。図９（Ｃ）を参照すると、共用ネットリスト１２の演算ブロック１２＿１ｉ（ｉは整数）は、それぞれ再構成可能回路の１つのセル１の機能ブロック５０（図５）に割り当てられる。ネット１２＿２ｉ（ｉは整数）は、共用ネットリスト１２の演算ブロック間を繋ぐ配線、または共用ネットリスト１２の入出力信号線に対応する。【００５０】
図９（Ｃ）で、演算ブロック１２＿１ｉに付した符合Ｘは、機能ブロック５０において実現することができる任意の演算を意味する。ネットリストが再構成可能回路に配置配線できるか否かを判断する場合、ネットリストの演算ブロックの機能は、再構成可能回路の機能ブロックが実現できる機能であればいずれであってもよい。演算ブロックの機能は、配置配線することができるか否かとは無関係である。【００５１】
共用ネットリスト１２は、第１のネットリスト１０と第２のネットリスト１１を包含している。実際、共用ネットリスト１２から演算ブロック１２＿１５とネット１２＿２８を削除し、各演算ブロックの機能を適宜設定すると、第１のネットリスト１０と等価となる。また、共用ネットリスト１２から演算ブロック１２＿１３とネット１２＿２３、１２＿２５を削除し、各演算ブロックの機能を適宜設定すれば、ネットリスト１１と同等になる。【００５２】
したがって、共用ネットリスト１２を再構成可能回路に配置配線することができる場合には、第１のネットリスト１０と第２のネットリスト１１は、いずれも再構成可能回路に配置配線することができる。【００５３】
ここではネットリストが２つの場合を例として説明したが、ネットリストの個数は任意である。すべてのネットリストを一つの共用ネットリストに重ね合わせ、その共用ネットリストを配置配線対象とすることによって、１回の配置配線で、すべてのネットリストの配置配線可能性を調べることができる。そしてこのような共用ネットリストを用いることによって、再構成可能回路を生成する処理時間が大幅に短縮される。【００５４】
さらに、共用ネットリストを利用することにより、再構成可能回路の面積を縮小する効果が生じる。図９の共用ネットリスト１２の各演算ブロック１２＿１ｉ（ｉは整数）は、ネットリスト１０の演算ブロック１０＿１ｉ、ネットリスト１１の演算ブロック１１＿１ｉにそれぞれ対応する。さらに、図９の共用ネットリスト１２の各ネット１２＿２ｉは、ネットリスト１０のネット１０＿２ｉ、ネットリスト１１の演算ブロック１１＿２ｉにそれぞれ対応する。【００５５】
なお、ｉ＝０、１、２、４の演算ブロック、およびｉ＝０、１、２、４、６、７のネットは、図９（Ａ）、（Ｂ）の両ネットリストに共通に存在し、それらによって形成されるネットワーク構造も両ネットリストにおいて同一である。共用ネットリスト１２は、このように複数のネットリストにおいてネットワーク構造が同じである共通部分をそのまま用いるとともに、複数のネットリストと共通部分との差分を共通部分に対して付加した構造を有する。共用ネットリスト１２から、差分に相当する箇所を削除することにより、複数のネットリストのうちのいずれかのネットリストが得られる。【００５６】
図１０（Ｃ）は図９（Ｃ）の共用ネットリスト１２を図４の再構成可能回路に配置配線した様子を示す。太い矢印はネット１２＿２ｉ（ｉは整数）に対応する。セル１ＡＢ、１ＣＣ、１ＣＡの内側の矢印は、セルの入力（太線）から出力（太線）へ信号を伝送する機能がマッピングされていることを示す。セル内部に符号が付されたセルは、その機能ブロックが使用される（いずれかの演算が行われる）セルである。セル内部に符号が付されていないセルは、その機能ブロックが使用されないセルである。また、細線で示した矢印は未使用の配線を表す。【００５７】
図１０（Ｃ）のセル１ＡＣ、１ＢＣ、１ＢＢ、１ＣＢ、１ＢＡ、１ＣＡは、それぞれ図９（Ｃ）の演算ブロック１２＿１３、１２＿１４、１２＿１１、１２＿１２、１２＿１０、１２＿１５に対応する。【００５８】
図９（Ａ）のネットリスト１０は、図９（Ｃ）の共用ネットリスト１２から演算ブロック１２＿１５とネット１２＿２８を除き、適宜演算ブロックの機能を設定することによって得られる。これに対応して、図１０（Ａ）に示すネットリスト１０の配置配線結果は、図１０（Ｃ）において、セル１ＣＡの機能ブロックとネット３１ＣＡを未使用とし、他のＸ記号が書かれたセルの機能ブロックの機能を適宜設定することによって得られる。【００５９】
図９（Ｂ）のネットリスト１１は、図９（Ｃ）の共用ネットリスト１２から演算ブロック１２＿１３とネット１２＿２３、１２＿２５を除き、適宜演算ブロックの機能を設定することによって得られる。これに対応して、図１０（Ｂ）に示すネットリスト１１の配置配線結果は、図１０（Ｃ）において、セル１ＡＣの機能ブロックとそれに関する入出力経路を未使用にし、他のＸ記号が書かれたセルの機能ブロックの機能を適宜設定することによって得られる。【００６０】
共用ネットリストを用いて各ネットリストの配置配線を求める場合には、ネットリスト間の共通部分はいずれも同一のリソース（セルと配線）に配置配線される。一方、ネットリストを個別に配置配線する場合には、ネットリスト間の共通部分は必ずしも同一のリソースに配置配線されるとは限らない。ネットリスト間の共通部分が同一リソースに配置配線されない場合には、未使用のリソースが減るため、再構成可能回路の面積を縮小することが困難となる。【００６１】
図１１は、ネットリストの数に対する、再構成可能回路のリソース（スイッチや配線）数を示す。ネットリストを個別に配置配線する場合を、従来例として示す。すべてのネットリストの間で共用することができる共用ネットリストを配置配線する場合を、本発明として示す。ネットリストの数が増えるにしたがって、本発明におけるリソース数は、従来例よりも少なくなる。従来例においては、ネットリストの共通部分が同一のリソースに配置配線されず、ばらついて配置配線される影響がネットリストの数が増えるにしたがって大きくなるからである。一方、本発明においては、共用ネットリストを配置配線に使うことにより、共通部分のばらつきがなくなることから、必要なリソース数を削減し、従来よりも小面積の再構成可能回路を生成することができる。【００６２】
ネットリスト間の共通部分が多いほど、再構成可能回路において多くのリソースを削減することができる。したがって、すべてのネットリスト間において、さまざまなマッチングの仕方を試行錯誤し、共通部分が最大となるようなマッチングの仕方を見出すことが好ましい。また、マッチングに際して、ネットリスト間の演算ブロックの機能の相違を無視し、ネットを共用化することができる箇所を探索するようにしてもよい。【００６３】
ネットリスト間の共通部分の大きさを測る尺度として、例えば、共通部分に含まれる演算ブロックの数、ネットの数、もしくは演算ブロックの入出力の数、またはこれらの組み合わせ（例えば、これらの和や積）を用いることができる。この尺度が最大になるようなマッチングの仕方を探索するようにしてもよい。
【実施例２】
【００６４】
また、複数のネットリストを複数のグループに分類し、各グループに対して共通ネットリストを生成するようにしてもよい。この場合、グループの数と同じだけの共通ネットリストが生成される。この場合において、再構成可能回路におけるリソースを削減するときには、すべての共通ネットリストの配置配線が可能であるか否かを評価する必要がある。しかし、すべてのネットリストを個別に配置配線する場合と比較して、配置配線の回数を削減することができることから、リソースを削減した再構成可能回路を生成するための時間を短縮することができる。【００６５】
また、共通ネットリストを配置配線に用いることにより、すべてのネットリストを個別に配置配線する場合と比較して、共通部分のばらつきも抑えることができ、再構成可能回路の面積を削減する効果も生じる。なお、類似の構造又は機能を有するアプリケーションに対するネットリスト同士は同一のグループに属するようにすることで、共用ネットリストの規模を小さくすることができる。
【実施例３】
【００６６】
さらに、上記の実施例２のように複数の共用ネットリストを生成した後、これらの共用ネットリストの間で共用することのできるネットリストをさらに生成するようにしてもよい。多数のネットリストから一度に共用ネットリストを生成する場合には、ネットリスト間のマッチングのために多くの時間を要するおそれがある。このような場合には、ネットリストを複数のグループに分け、各グループに属するネットリストに対する共用ネットリストを生成した後、これらの共用ネットリストの間で共用することのできるネットリストを生成するようにしてもよい。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【００６７】
１、１ＡＡ〜１ＣＣ  セル
２、２Ａ〜２Ｄ  スイッチ
５  コンフィギュレーションメモリ
６  トランスミッションゲート
７  入力信号線
８  バッファ
９  出力信号線
１０、１１  ネットリスト
１２  共用ネットリスト
１０＿１０〜１０＿１４、１１＿１０〜１１＿１２、１１＿１４、１１＿１５、１２＿１０〜１２＿１５  演算ブロック
１０＿２０〜１０＿２７、１１＿２０〜１１＿２２、１１＿２４、１１＿２６〜１１＿２８、１２＿２０〜１２＿２８  ネット
２０、２０Ａ〜２０Ｆ  マルチプレクサ
３０、３０Ａ、３０Ｂ  横方向配線
３１、３１Ａ、３１Ｂ、３１ＣＡ  縦方向配線
５０  機能ブロック
６０  再構成可能回路生成装置
６１  ネットリスト生成部
６２  リソース削減部
７０  コンピュータ
７１  ＣＰＵ
７２  記憶部
７３  入力装置
７４  出力装置
８０、８１  端子
【図１】
0005402940.tif 000002
【図２】
0005402940.tif 000003
【図３】
0005402940.tif 000004
【図４】
0005402940.tif 000005
【図５】
0005402940.tif 000006
【図６】
0005402940.tif 000007
【図７】
0005402940.tif 000008
【図８】
0005402940.tif 000009
【図９】
0005402940.tif 000010
【図１０】
0005402940.tif 000011
【図１１】
0005402940.tif 000012
【図１２】
0005402940.tif 000013