リコンフィギュラブルロジックブロック、並びに、これを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法
【課題】デバイスの小面積化と低消費電力化を実現することが可能なリコンフィギュラブルロジックブロック、並びにこれを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法を提供する。
【解決手段】最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブル１と、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブル２と、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路３と、組み合わせ回路３の出力に応じて第１ルックアップテーブル１と第２ルックアップテーブル２のいずれか一方を選択するセレクタ４と、を有する。
【解決手段】最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブル１と、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブル２と、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路３と、組み合わせ回路３の出力に応じて第１ルックアップテーブル１と第２ルックアップテーブル２のいずれか一方を選択するセレクタ４と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リコンフィギュラブルロジックブロック（以下、ＲＬＢ［Reconfigurable Logic Block］と呼ぶ）、並びに、これを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法に関するものである。
【背景技術】
【０００２】
近年、ハードウェア記述言語 （ＨＤＬ［Hardware Description Language］）を用いたプログラミングにより、半導体装置に集積化された内部論理回路を現場で自由に再構築することが可能なプログラマブル論理回路装置（ＰＬＤ［Programmable Logic Device］、ＦＰＧＡ［Field Programmable Gate Array］、ＤＡＰ／ＤＮＡ［Digital Application Processor/Distributed Network Architecture］、ＤＲＰ［Dynamically Reconfigurable Processor］など）が種々実用化されている。
【０００３】
なお、上記に関連する従来技術の一例としては、特許文献１〜特許文献７、及び、非特許文献１を挙げることができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第４，７０６，２１６号明細書
【特許文献２】米国特許第４，８７０，３０２号明細書
【特許文献３】米国特許第６，９９８，８７２号明細書
【特許文献４】米国特許出願公開第２００７／０２２２４７７号明細書
【特許文献５】特開２００３−１８０００号公報
【特許文献６】特開２００４−２４８２９３号公報
【特許文献７】特開２００７−１６６５７９号公報
【０００５】
【非特許文献１】(Vaughn Betz, Jonathan Rose, and Alexander Marquardt)著、「Architecture and CAD for Deep-Submicron FPGAs (The Springer International Series in Engineering and Computer Science) 」、Springer出版
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＦＰＧＡなどのプログラマブル論理回路装置では、所望の論理回路を実現するための基本素子としてルックアップテーブル（以下、ＬＵＴ［Look-Up Table］と呼ぶ）が用いられている。ＬＵＴは、真理値表の出力値をコンフィギュレーションメモリに１対１で保持しており、それらを複数のマルチプレクサによりデコードすることで、所望の論理回路を実現することが可能である。Ｋ入力のＬＵＴ（以下、Ｋ−ＬＵＴと呼ぶ）を用いれば、Ｋ入力以下の論理回路を全て実装することができる。しかしながら、従来のＬＵＴでは、入力数を増やすほど遅延性能が高くなる（遅延が小さくなる）が、使用されないメモリ数が増えて実装面積（ＬＵＴのサイズ）が大きくなる、言い換えれば、ＬＵＴの使用メモリ数（ＬＵＴのサイズ）と遅延性能がトレードオフの関係にある、という問題があった（例えば、特許文献１や特許文献２を参照）。
【０００７】
なお、従来より、ＬＵＴの使用メモリ数を減らす工夫として、図２７で示すようなアダプティブＬＵＴが提案されている（例えば、特許文献３や特許文献４を参照）。これは、入力数の多いＬＵＴを分割することで、入力数の少ないＬＵＴを複数個使用できるようにし、メモリ数を削減する技術である。確かに、入力数の多いアダプティブＬＵＴを使用して論理回路を実装すれば、入力数の少ないＬＵＴを多数使用して論理回路を実装する場合よりも、遅延性能を高めることが可能である。しかしながら、従来のアダプティブＬＵＴでは、入力数の多いＬＵＴを分割せずに用いた場合、ＬＵＴの使用メモリ数（消費電力）が多くなる、という問題があった。
【０００８】
また、従来より、図２８で示すようなクラスタベース論理ブロックの構成手法が提案されている（例えば、非特許文献１を参照）。これば、入力数の少ないＬＵＴを多数クラスタリングすることにより、ＬＵＴのメモリ使用率を下げずに性能を改善する技術である。しかしながら、従来のクラスタベース論理ブロックでは、論理ブロック内でＬＵＴ同士を接続するためにマルチプレクサとメモリが多数必要となるため、配線に必要なハードウェアリソースが増加する、という問題があった。
【０００９】
図２９は、上記した従来技術の特徴をまとめた一覧表である。従来のＬＵＴ（例えば、４−ＬＵＴ）は、論理ブロックのサイズが小さいので、構成メモリ数は少なくて済むが、遅延性能は低く、また、同一回路を実装したときの論理ブロックの使用数は多くなる。これに対して、従来のアダプティブＬＵＴ（例えば、アダプティブ６−ＬＵＴ）やクラスタベース論理ブロック（例えば、４−ＬＵＴ×８）は、遅延性能が高く、また、同一回路を実装したときの論理ブロックの使用数は少なくて済むが、論理ブロックのサイズが大きいので、構成メモリ数が多くなる。
【００１０】
また、その他の従来技術として、特許文献５では、Ｍ入力Ｎ出力のルックアップテーブルであって、複数のＬＵＴユニットと、前記複数のＬＵＴユニットによる内部構成を制御する内部構成制御手段と、を備えるルックアップテーブルが開示されている。この従来技術によれば、例えば、６入力３出力の場合、２−ＬＵＴを３つ、３ＬＵＴ−を２つ、または、６−ＬＵＴを１つといったように、モードを切り替えることで面積効率を向上させることが可能である。しかしながら、この従来技術では、６入力の論理回路を実装するためには６４ビットのメモリが必要であるため、テクノロジマッピングで６入力の論理回路が多数出てきた場合には、使用メモリ数が多くなっていた。また、出力線が従来のＬＵＴよりも多いので、配線領域が増加するという懸念もあった。
【００１１】
また、特許文献６では、６つの２−ＬＵＴから構成されており、完全な４−ＬＵＴと、一般的に用いられる６入力の論理関数を比較的高い割合で実装することが可能な不完全ルックアップテーブルが提案されている。この従来技術によれば、構成可能論理回路は６入力全ての論理関数のサブセットしか実行できないため、構成可能論理回路がＦＰＧＡ内で占めるシリコン領域を大幅に減少することが可能である。しかしながら、この従来技術では、論理セルからの出力線が２本あるので、６入力のサブセットとして使用した場合、配線領域が増加してしまう。また、セル内のコンフィギュレーションメモリ数については、さらなる削減の余地があった。
【００１２】
また、特許文献７では、演算回路を構成する第１の回路、および、該演算回路外の回路を構成する第２の回路を備えるリコンフィギュラブルロジックブロックであって、前記第１および第２の回路における所定の信号の設定を変化させることにより、異なる回路を構成するようにしたリコンフィギュラブルロジックブロックが提案されている。この従来技術によれば、算術演算と論理演算を効率良く実装し、また、論理演算においては、少ないＢＬＥ［Basic Logic Element］数で一部の論理回路を実装することが可能である。しかしながら、この従来技術において、実装可能な一部の論理回路は、その出現確率を考慮したものではなく、効率的な論理回路の実装については、さらなる改善の余地があった。
【００１３】
本発明は、本願の発明者らにより見出された上記の問題点に鑑み、デバイスの小面積化と低消費電力化を実現することが可能なリコンフィギュラブルロジックブロック、並びにこれを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明に係るリコンフィギュラブルロジックブロックは、最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロックであって、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブルと、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブルと、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路と、前記組み合わせ回路の出力に応じて前記第１ルックアップテーブルと前記第２ルックアップテーブルのいずれか一方を選択するセレクタと、を有する構成（第１の構成）とされている。
【００１５】
なお、上記第１の構成から成るリコンフィギュラブルロジックブロックは、複数の論理回路を各々表現した真理値表を比較して、同一パターンが連続している部分を前記第２ルックアップテーブルで実装し、残りの部分を前記第１ルックアップテーブルで実装する構成（第２の構成）にするとよい。
【００１６】
また、上記第２の構成から成るリコンフィギュラブルロジックブロックにおいて、前記複数の論理回路は、Ｋ入力のルックアップテーブルでマッピングされた論理回路のうち、出現確率の高いものを含む構成（第３の構成）にするとよい。
【００１７】
また、本発明に係るプログラマブル論理回路装置は、上記第３の構成から成るリコンフィギュラブルロジックブロックを有する構成（第４の構成）とされている。
【００１８】
また、本発明に係るテクノロジマッピング方法は、上記第４の構成から成るプログラマブル論理回路装置を対象としたものであって、入力数ｊとして前記リコンフィギュラブルロジックブロックの最大入力数Ｋを設定してフローを第２ステップに進める第１ステップと；カバリングされていないノードを探索してフローを第３ステップに進める第２ステップと；ｊ入力のカットがあるか否かを判定し、カットがあればフローを第４ステップに進め、カットがなければフローを第１０ステップに進める第３ステップと；ｊ入力の部分回路にカットしてフローを第５ステップに進める第４ステップと；ｊがｍよりも大きいか否かを判定し、大きければフローを第６ステップに進め、大きくなければフローを第８ステップに進める第５ステップと；前記部分回路のＰ代表元を算出してフローを第７ステップに進める第６ステップと；前記Ｐ代表元に基づいて前記部分回路が前記リコンフィギュラブルロジックブロックで実装可能か否かを判定し、実装可能であればフローを第８ステップに進め、実装不可能であればフローを第３ステップに進める第７ステップと；前記リコンフィギュラブルロジックブロックでノードのカバリングを行い、フローを第９ステップに進める第８ステップと；全てのノードがカバリング済みであるか否かを判定し、カバリング済みであれば一連のフローを終了させ、カバリング済みでなければフローを第２ステップに進める第９ステップと；入力数ｊを一つデクリメントさせてフローを第２ステップに進める第１０ステップと；を有する構成（第５の構成）とされている。
【発明の効果】
【００１９】
本発明によれば、デバイスの小面積化と低消費電力化を実現することが可能なリコンフィギュラブルロジックブロック、並びに、これを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法を提供することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係るプログラマブル論理回路装置の全体構成例を示すブロック図
【図２】３入力論理回路の一実装例を示す図
【図３】本発明に係るリコンフィギュラブルロジックブロックの概念的構成を示す図
【図４】メモリの一使用例を示す真理値表
【図５】リコンフィギュラブルロジックブロックの第１構成例を示す図
【図６】第１構成例における入力条件とメモリとの関係を示す図
【図７】６−ＬＵＴでマッピングした回路のメモリパターン（Ｐ同値類）を示す図
【図８】６入力のテクノロジマッピング方法を示すフローチャート
【図９】本発明に係るテクノロジマッピング方法の全体像を示すフローチャート
【図１０】リコンフィギュラブルロジックブロックの第２構成例を示す図
【図１１】リコンフィギュラブルロジックブロックの第３構成例を示す図
【図１２】リコンフィギュラブルロジックブロックの第４構成例を示す図
【図１３】リコンフィギュラブルロジックブロックの第５構成例を示す図
【図１４】リコンフィギュラブルロジックブロックの第６構成例を示す図
【図１５】リコンフィギュラブルロジックブロックの第７構成例を示す図
【図１６】リコンフィギュラブルロジックブロックの第８構成例を示す図
【図１７】リコンフィギュラブルロジックブロックの第９構成例を示す図
【図１８】リコンフィギュラブルロジックブロックの第１０構成例を示す図
【図１９】リコンフィギュラブルロジックブロックの第１１構成例を示す図
【図２０】リコンフィギュラブルロジックブロックの第１２構成例を示す図
【図２１】リコンフィギュラブルロジックブロックの第１３構成例を示す図
【図２２】リコンフィギュラブルロジックブロックの第１４構成例を示す図
【図２３】リコンフィギュラブルロジックブロックの第１５構成例を示す図
【図２４】リコンフィギュラブルロジックブロックの第１６構成例を示す図
【図２５】各構成例におけるＬＵＴの形成方法とメモリの集約状態を示す図
【図２６】各構成例における論理回路のカバー率を示す図
【図２７】アダプティブＬＵＴの一従来例を示すブロック図
【図２８】クラスタベース論理ブロックの一従来例を示すブロック図
【図２９】従来技術の特徴をまとめた一覧表
【発明を実施するための形態】
【００２１】
＜プログラマブル論理回路装置＞
図１は、本発明に係るプログラマブル論理回路装置の全体構成例を示すブロック図である。本構成例のプログラマブル論理回路装置１００は、Ｉ／Ｏブロック１０１と、リコンフィギュラブルロジックブロック１０２（以下、ＲＬＢ［Reconfigurable Logic Block］１０２と略称する）と、コネクションブロック１０３（以下、ＣＢ［Connection Block］１０３と略称する）と、スイッチブロック１０４（以下、ＳＷ［Switch Block］１０４と略称する）と、配線１０５と、を有する。
【００２２】
Ｉ／Ｏブロック１０１は、外部との信号授受を行う。ＲＬＢ１０２は、マトリクス状に複数配列されており、論理回路を実現するための演算素子として使用される。ＣＢ１０３は、ＲＬＢ１０２と配線１０５とを結合する。ＳＢ１０４は、配線１０５のクロスポイントとなる。
【００２３】
プログラマブル論理回路装置１００の性能を改善するためには、新しいＲＬＢ１０２が必要であり、本発明は、主としてＲＬＢ１０２の新規な構成に関するものである。
【００２４】
＜本発明に至った経緯＞
論理回路を従来のＬＵＴで表現する場合、同じ論理関数を異なるＬＵＴのメモリパターン（構成情報）で実現しているものが多く見られる。また、ＬＵＴのメモリパターンには同じデータの繰り返し部分が多数存在する。すなわち、一般に用いられている従来のＬＵＴによる回路表現は、真理値表をそのままコンフィギュレーションデータとして表現したものであり、同じ論理回路でも複数の実装が存在する。そのため、入力信号の入れ替えによって得られる論理回路を同一とみなせば、ＬＵＴによる回路表現は本質的に冗長であると言える。以下では、ＬＵＴの冗長性について、３入力の論理回路を例示して説明する。
【００２５】
図２は、３入力論理回路の一実装例を示す図である。図２に示すように、関数ｆと関数ｇの真理値表は、一部のパターンが異なっているが、入力ｂと入力ｃを入れ替えれば、関数ｆと関数ｇを同一とみなすことができる。このとき、関数ｆを実現するための論理回路と、関数ｇを実現するための論理回路は、同じＰ［Permutation］同値類に属する。すなわち、関数ｆが関数ｇの入力順序を入れ替えることによって得られるならば、関数ｆと関数ｇは、同じＰ同値類に属すると言える。
【００２６】
本願の発明者らは、上記考察から、ＬＵＴによる回路表現の冗長性を除くことにより、従来のＬＵＴより少ないコンフィギュレーションメモリ数でも、従来と同等の論理回路を実装可能な論理セルを実現することができる、との着想を得て本発明に至った。
【００２７】
＜リコンフィギュラブルロジックブロック＞
図３は、本発明に係るリコンフィギュラブルロジックブロックの概念的構成を示す図である。本発明に係る最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただし、ｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブル１と、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただし、ｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブル２と、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただし、ｐはＫよりも小さくｃはｘに属する）の組み合わせ回路３と、組み合わせ回路３の出力に応じて第１ルックアップテーブル１と第２ルックアップテーブル２のいずれか一方を選択するセレクタ４と、を有する。
【００２８】
また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、アプリケーションの実装に必要な複数の論理回路を各々表現した真理値表を比較したとき、同一パターンが連続している部分（例えば、図４の破線で囲まれた部分を参照）については第２ルックアップテーブル２で実装し、残りの部分（例えば、図４の実線で囲まれた部分を参照）については第１ルックアップテーブル１で実装している。
【００２９】
また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）において、前記複数の論理回路としては、Ｋ−ＬＵＴでマッピングされた論理回路のうち、出現確率の高いものが含まれている。なお、上記マッピングに際しては、同一パターンが多く出現するように（できるだけ同じ値の出力値が並ぶように）、入力変数の入れ替えを行うことが望ましい。
【００３０】
上記の構成を採用することにより、アプリケーションの実装に必要な論理回路を従来のＫ−ＬＵＴよりも少ないコンフィギュレーションメモリ数で実現することが可能となる。より具体的に述べると、Ｋ入力の論理回路を実装する場合、従来のＫ−ＬＵＴでは２Ｋ個のメモリ数が必要であるのに対して、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば（２ｍ＋２ｎ）個のメモリ数で足りる。
【００３１】
このように、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、より少ないメモリ数で従来のＫ−ＬＵＴと同程度の機能を維持することができるので、プログラマブル論理回路装置の小面積化と低消費電力化を実現することが可能となる。また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、従来のＫ−ＬＵＴと入出力線の本数が変わらないので、配線領域の増加を防ぐことも可能となる。
【００３２】
なお、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、複数の出力値を少ないメモリに集約し、様々な入力数（最大Ｋ入力）の論理回路に対応可能であることから、本明細書中では、Ｋ−Ａ２ＬＵＴ［Abridged Adaptive LUT］と名付けられている。
【００３３】
＜本発明のポイント＞
本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）のポイントをまとめて述べる。まず、第１のポイントは、入力数がｍよりも大きい論理回路（最大Ｋ入力）の一部を実装することが可能であり、入力数がｍ以下である論理回路の全てを実装することが可能な構造とされている点である。第２のポイントは、入力数がｍよりも大きい論理回路のうち、実装可能な一部の論理回路としては、出現確率の高いものが優先的に含まれている点、言い換えれば、実装可能な一部の論理回路の数を効率良く制限することで構成メモリ数が削減されている点である。第３のポイントは、入力の入れ替えによって互いに置換可能な論理回路が同一（Ｐ同値類）とみなされている点である。
【００３４】
＜第１構成例＞
図５は、本発明に係るリコンフィギュラブルロジックブロックの第１構成例を示す図であり、最大入力数Ｋ＝６とした場合の回路構成を示している。
【００３５】
第１構成例のリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）は、第１ブロックＡ（メモリ［０］〜［７］を用いた３−ＬＵＴ（Ａ））と、第２ブロックＢ（メモリ［１０］〜［１７］を用いた３−ＬＵＴ（Ｂ））と、２ビットのメモリ［８］及び［９］と、セレクタＳＥＬ０〜ＳＥＬ２と、組み合わせ回路ＣＭＢと、を有する。
【００３６】
第１ブロックＡは、入力信号ｉｎ１〜ｉｎ３に応じてメモリ［０］〜［７］の格納データのいずれか一つを出力する。第２ブロックＢは、入力信号ｉｎ１〜ｉｎ３に応じてメモリ［１０］〜［１７］の格納データのいずれか一つを出力する。セレクタＳＥＬ０は入力信号ｉｎ０に応じてセレクタＳＥＬ１の出力データとセレクタＳＥＬ２の出力データの一方を出力信号ｏｕｔとして選択する。セレクタＳＥＬ１は、組み合わせ回路ＣＭＢの出力に応じて第１ブロックＡの出力データとメモリ［８］の格納データの一方を選択する。セレクタＳＥＬ２は、組み合わせ回路ＣＭＢの出力に応じて第２ブロックＢの出力データとメモリ［９］の格納データの一方を選択する。
【００３７】
組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５に応じてセレクタＳＥＬ１及びＳＥＬ２の切替信号を生成する。第１構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ１と、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ２と、ＮＯＲゲートＧ１の出力とＡＮＤゲートＧ２の出力との論理和演算を行うＯＲゲートＧ３と、を有する。
【００３８】
なお、第１ブロックＡ、第２ブロックＢ、及び、セレクタＳＥＬ０によって４入力（ｉｎ０〜ｉｎ３）のルックアップテーブルが形成されており、これは図３の第１ルックアップテーブル１（ｍ＝４）に相当する。また、２ビットのメモリ［８］及び［９］とセレクタＳＥＬ０によって１入力（ｉｎ０）のルックアップテーブルが形成されており、これは図３の第２ルックアップテーブル２（ｎ＝１）に相当する。また、組み合わせ回路ＣＭＢは、図３の組み合わせ回路３に相当する。また、セレクタＳＥＬ１及びＳＥＬ２は、図３のセレクタ４に相当する。
【００３９】
従来の６−ＬＵＴでは、２６＝６４ビットのメモリが必要であるのに対して、第１構成例のリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）は、２４＋２１＝１８ビットのメモリで構成されている。
【００４０】
図６は、第１構成例における入力条件とメモリとの関係を示す図であり、図７は、６−ＬＵＴでマッピングした論理回路のメモリパターン（Ｐ同値類）を出現確率の高い順に第１位〜第７位まで示した図である。なお、図７のメモリパターンは、６−ＬＵＴの出力データＯ０〜Ｏ６３を６４ビットの２進数値として表記したものである。
【００４１】
図７から分かるように、第１位〜第７位のメモリパターン全てにおいて、第５ビット目〜第２８ビット目（Ｏ４〜Ｏ２７）と、第３７ビット目〜第６０ビット目（Ｏ３６〜Ｏ５９）は全て０か１の連続である。そこで、第１構成例では、同一値が連続している上記部分のうち、前者が１ビットのメモリ［８］に集約され、後者が１ビットのメモリ［９］に集約されている。また、残りの部分のうち、第１ビット目〜第４ビット目（Ｏ０〜Ｏ３）と第２９ビット目〜第３２ビット目（Ｏ２８〜Ｏ３１）が第１ブロックＡで実現されており、第３３ビット目〜第３６ビット目（Ｏ３２〜Ｏ３５）と第６１ビット目〜第６４ビット目（Ｏ６０〜Ｏ６３）が第２ブロックＢで実現されている。
【００４２】
具体的に述べると、第１構成例では、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，１，１｝（ただし「−」は０または１）に対応する出力データＯ０〜Ｏ３及びＯ２８〜Ｏ３１が第１ブロックＡのメモリ［０］〜［７］に保持されており、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，１，１｝に対応する出力データＯ３２〜Ｏ３５及びＯ６０〜Ｏ６３が第２ブロックＢのメモリ［１０］〜［１７］に保持されている。また、上記以外の出力データＯ４〜Ｏ２７及びＯ３６〜Ｏ５９がメモリ［８］及び［９］に集約されている。
【００４３】
そして、図６に示した通り、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，１，１｝のときには第１ブロックＡの出力データが出力信号ｏｕｔとして用いられ、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，１，１｝のときには第２ブロックＢの出力データが出力信号ｏｕｔとして用いられる。また、入力信号の組み合わせが上記以外であるときには、メモリ［８］または［９］の格納データが出力信号ｏｕｔとして用いられる。
【００４４】
ネットリストを６−Ａ２ＬＵＴ（１８ビット）で実装すれば、従来の６−ＬＵＴ（６４ビット）で実装する場合と比べて、１セル当たりのメモリ数を４６ビット削減することが可能となる。また、第１構成例の６−Ａ２ＬＵＴであれば、６−ＬＵＴで利用されるメモリパターンの約５２％、５−ＬＵＴで利用されるメモリパターンの約４７％を実現することができるので、従来よりも少ないメモリ数で論理回路を実装することが可能となる。また、従来の４−ＬＵＴで実装する場合と比べて、より少ないセル数で論理回路を実装することが可能となる。
【００４５】
＜テクノロジマッピング方法＞
図８は、６入力のテクノロジマッピング方法を示すフローチャートである。
【００４６】
ステップＳ１０１では、入力となるネットリストに対してカバリングされていないノードの探索が行われて、フローがステップＳ１０２に進められる。
【００４７】
ステップＳ１０２では、６入力のカットがあるか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ１０２に進められ、ノー判定が下された場合にはフローがステップＳ１０８に進められる。
【００４８】
ステップＳ１０３では、６入力のカットが部分回路として切り出されて、フローがステップＳ１０４に進められる。
【００４９】
ステップＳ１０４では、ステップＳ１０３でカットされた部分回路のＰ代表元が算出されて、フローがステップＳ１０５に進められる。なお、Ｐ代表元とは、Ｐ同値類中の関数を２進数値とみなした場合に最小のものを言う。
【００５０】
ステップＳ１０５では、ステップＳ１０４で算出されたＰ代表元に基づいて、ステップＳ１０３でカットされた部分回路が６−Ａ２ＬＵＴで実装可能か否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ１０６に進められ、ノー判定が下された場合にはフローがステップＳ１０２が戻されて、別のカットが探索される。
【００５１】
ステップＳ１０６では、６−Ａ２ＬＵＴでノードのカバリングが行われて、フローがステップＳ１０７に進められる。
【００５２】
ステップＳ１０７では、全てのノードがカバリング済みが否かの判定が行われる。ここで、イエス判定が下された場合には上記一連のフローが終了され、ノー判定が下された場合にはフローがステップＳ１０１に戻される。
【００５３】
ステップＳ１０８では、６−Ａ２ＬＵＴで実装可能な６入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていないことから、入力数が１つ下げられて、５入力のテクノロジマッピングが行われる。５入力のテクノロジマッピングについては、上記で説明した入力数をいずれも「６」から「５」に読み替えれば足りる。
【００５４】
その後、６−Ａ２ＬＵＴで実装可能な５入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていない場合、残りのノードについては、いずれも４入力以下の部分回路にカットされてノードのカバリングが行われる。なお、６−Ａ２ＬＵＴは４入力以下の論理回路を全て実装することができるので、Ｐ代表元の算出を行うためのステップＳ１０４や６−Ａ２ＬＵＴによる実装可能性を検証するためのステップＳ１０５はもはや必要なくなる。
【００５５】
図９は、本発明に係るテクノロジマッピング方法の全体像を示すフローチャートであって、先出の図８で説明したフローチャートをより一般化したものである。なお、本フローチャートは、Ｋ−Ａ２ＬＵＴでｍ入力以下の論理回路を全て実装することが可能であること、及び、Ｋ入力以下に分解されたゲートレベルのブーリアンネットワークを入力とすることを前提とする。
【００５６】
ステップＳ２０１では、入力数ｊとしてＫ−Ａ２ＬＵＴの最大入力数Ｋが設定されて、フローがステップＳ２０２に進められる。
【００５７】
ステップＳ２０２では、入力となるネットリストに対してカバリングされていないノードの探索が行われて、フローがステップＳ２０３に進められる。
【００５８】
ステップＳ２０３では、ｊ入力のカットがあるか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０４に進められ、ノー判定が下された場合にはフローがステップＳ２１０に進められる。
【００５９】
ステップＳ２０４では、ｊ入力のカットが部分回路として切り出されて、フローがステップＳ２０５に進められる。
【００６０】
ステップＳ２０５では、ｊがｍよりも大きいか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０６に進められ、ノー判定が下された場合にはフローがステップＳ２０８に進められる。
【００６１】
ステップＳ２０６では、ステップＳ２０４でカットされた部分回路のＰ代表元が算出されて、フローがステップＳ２０７に進められる。
【００６２】
ステップＳ２０７では、ステップＳ２０６で算出されたＰ代表元に基づいて、ステップＳ２０４でカットされた部分回路が６−Ａ２ＬＵＴで実装可能か否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０８に進められ、ノー判定が下された場合にはフローがステップＳ２０３が戻されて、別のカットが探索される。
【００６３】
ステップＳ２０８では、６−Ａ２ＬＵＴでノードのカバリングが行われて、フローがステップＳ２０９に進められる。
【００６４】
ステップＳ２０９では、全てのノードがカバリング済みが否かの判定が行われる。ここで、イエス判定が下された場合には上記一連のフローが終了され、ノー判定が下された場合にはフローがステップＳ２０２に戻される。
【００６５】
ステップＳ１０８では、６−Ａ２ＬＵＴで実装可能なｊ入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていないことから、入力数ｊを一つデクリメントさせて、フローがステップＳ２０２に戻される。
【００６６】
上記のように入力数ｊを一つずつデクリメントさせながらノードのカバリングを繰り返し、６−Ａ２ＬＵＴで実装可能な（ｍ＋１）入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていない場合、残りのノードについては、いずれもｍ入力以下の部分回路にカットされてノードのカバリングが行われる。なお、６−Ａ２ＬＵＴはｍ入力以下の論理回路を全て実装することができるので、Ｐ代表元の算出を行うためのステップＳ２０６や６−Ａ２ＬＵＴによる実装可能性を検証するためのステップＳ２０７はもはや必要なくなる。そこで、ｊ＝ｍとなりステップＳ２０５でノー判定が下された場合には、フローがステップＳ２０８にジャンプされる。
【００６７】
先出の図３で示したように、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力の第１ルックアップテーブル１とｎ入力の第２ルックアップテーブル２によって構成されており、ｍ＞ｎとしたときには、ｍ入力以下の論理回路を全て実装することが可能である。従って、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、与えられたブーリアンネットワークをＫ−ＬＵＴよりも少ないメモリ数でテクノロジマッピングすることが可能である。
【００６８】
＜第２構成例〜第１６構成例＞
出現確率の高いＰ代表元について、先出の第１構成例（図５を参照）とは異なる入力の入れ替えを行い、それぞれＰ同値類に変換した結果、０または１が連続している部分を２ビットのメモリ［８］及び［９］に集約し、残りの部分を第１ブロックＡ及び第２ブロックＢで実現した下記の第２構成例〜第１６構成例では、組み合わせ回路ＣＭＢが第１構成例と異なる回路構造となる。
【００６９】
図１０は、リコンフィギュラブルロジックブロックの第２構成例を示す図である。第２構成例では、Ｏ４〜Ｏ１５とＯ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ４７とＯ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第２構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５の否定論理和演算を行うＮＯＲゲートＧ４のみを有する。
【００７０】
図１１は、リコンフィギュラブルロジックブロックの第３構成例を示す図である。第３構成例では、Ｏ４〜Ｏ２３とＯ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ５５とＯ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第３構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ５と、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ６と、ＮＯＲゲートＧ５の出力とＮＯＲゲートＧ６の出力との論理和演算を行うＯＲゲートＧ７と、を有する。
【００７１】
図１２は、リコンフィギュラブルロジックブロックの第４構成例を示す図である。第４構成例では、Ｏ４〜Ｏ１９とＯ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ５１とＯ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第４構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の論理積演算を行うＡＮＤゲートＧ８と、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ９と、ＡＮＤゲートＧ８の出力とＮＯＲゲートＧ９の出力との論理和演算を行うＯＲゲートＧ１０とを有する。
【００７２】
図１３は、リコンフィギュラブルロジックブロックの第５構成例を示す図である。第５構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ１５、及び、Ｏ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ４７、及び、Ｏ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第５構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１１と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１２と、ＮＯＲゲートＧ１１の出力とＮＯＲゲートＧ１２の出力との論理和演算を行うＯＲゲートＧ１３と、を有する。
【００７３】
図１４は、リコンフィギュラブルロジックブロックの第６構成例を示す図である。第６構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ１５、及び、Ｏ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ４７、及び、Ｏ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第６構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１５と、ＮＯＲゲートＧ１４の出力とＮＯＲゲートＧ１５の出力との論理和演算を行うＯＲゲートＧ１６と、を有する。
【００７４】
図１５は、リコンフィギュラブルロジックブロックの第７構成例を示す図である。第７構成例では、Ｏ０〜Ｏ１１とＯ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３とＯ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１９が第１ブロックＡで実現されており、Ｏ４４〜Ｏ５１が第２ブロックＢで実現されている。なお、第７構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１８と、ＮＯＲゲートＧ１７の出力とＮＯＲゲートＧ１８の出力との論理和演算を行うＯＲゲートＧ１９と、を有する。
【００７５】
図１６は、リコンフィギュラブルロジックブロックの第８構成例を示す図である。第８構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第８構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５（ただし、入力信号ｉｎ５については反転入力）の論理積演算を行うＡＮＤゲートＧ２０のみを有する。
【００７６】
図１７は、リコンフィギュラブルロジックブロックの第９構成例を示す図である。第９構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第９構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２１と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２２と、ＮＯＲゲートＧ２１の出力とＮＯＲゲートＧ２２の出力との論理和演算を行うＯＲゲートＧ２３と、を有する。
【００７７】
図１８は、リコンフィギュラブルロジックブロックの第１０構成例を示す図である。第１０構成例では、Ｏ０〜Ｏ７とＯ１２〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ３９とＯ４４〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１０構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ２４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２５と、ＡＮＤゲートＧ２４の出力とＮＯＲゲートＧ２５の出力との論理和演算を行うＯＲゲートＧ２６と、を有する。
【００７８】
図１９は、リコンフィギュラブルロジックブロックの第１１構成例を示す図である。第１１構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第１１構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の論理積演算を行うＡＮＤゲートＧ２８と、ＮＯＲゲートＧ２７の出力とＡＮＤゲートＧ２８の出力との論理和演算を行うＯＲゲートＧ２９と、を有する。
【００７９】
図２０は、リコンフィギュラブルロジックブロックの第１２構成例を示す図である。第１２構成例では、Ｏ０〜Ｏ１１、Ｏ１６〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３、Ｏ４８〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第１２構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３０と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３１と、ＮＯＲゲートＧ３０の出力とＮＯＲゲートＧ３１の出力との論理和演算を行うＯＲゲートＧ３２と、を有する。
【００８０】
図２１は、リコンフィギュラブルロジックブロックの第１３構成例を示す図である。第１３構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第１３構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５（ただし、入力信号ｉｎ４については反転入力）の論理積演算を行うＡＮＤゲートＧ３３のみを有する。
【００８１】
図２２は、リコンフィギュラブルロジックブロックの第１４構成例を示す図である。第１４構成例では、Ｏ０〜Ｏ３とＯ８〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ３５とＯ４０〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１４構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ３４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３５と、ＡＮＤゲートＧ３４の出力とＮＯＲゲートＧ３５の出力との論理和演算を行うＯＲゲートＧ３６と、を有する。
【００８２】
図２３は、リコンフィギュラブルロジックブロックの第１５構成例を示す図である。第１５構成例では、Ｏ０〜Ｏ１１、Ｏ１６〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３、Ｏ４８〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第１５構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３８と、ＮＯＲゲートＧ３７の出力とＮＯＲゲートＧ３８の出力との論理和演算を行うＯＲゲートＧ３９と、を有する。
【００８３】
図２４は、リコンフィギュラブルロジックブロックの第１６構成例を示す図である。第１６構成例では、Ｏ０〜Ｏ１１とＯ１６〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ４３とＯ４８〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１６構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５の論理積演算を行うＡＮＤゲートＧ４０のみを有する。
【００８４】
図２５は、第１〜第１６構成例におけるＬＵＴの形成方法とメモリの集約状態を示す図である。なお、符号「Ａ」は出力データが第１ブロックＡ（メモリ［０］〜［７］）に各々保持されていることを示しており、符号「Ｂ」は出力データが第２ブロックＢ（メモリ［１０］〜［１７］）に各々保持されていることを示している。また、符号「８」は出力データがメモリ［８］に集約されていることを示しており、符号「９」は出力データがメモリ［９］に集約されていることを示している。
【００８５】
例えば、第２構成例の場合、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，０，０｝のときには第１ブロックＡの出力データが出力信号ｏｕｔとして用いられ、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，０，０｝のときには第２ブロックＢの出力データが出力信号ｏｕｔとして用いられる。また、入力信号の組み合わせが上記以外であるときには、メモリ［８］または［９］の格納データが出力信号ｏｕｔとして用いられる。
【００８６】
図２６は、第１〜第１６構成例における論理回路のカバー率（６入力論理回路のカバー率、５入力論理回路のカバー率、及び、４入力以下も含めた全ての論理回路のカバー率）を示す図である。この表は、ＭＣＮＣ［Microelectronics Center of North Carolina］ ベンチマーク回路（１１７種類）をＥＭａｐによってテクノロジマッピングを行った場合において、使用された論理回路のうち、本発明に係るリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）で実装可能であったものの割合を示している。なお、ＥＭａｐとは、ＵＢＣ［University of British Columbia］で開発された電力最適化を目的としたテクノロジマッピングツールである。
【００８７】
本発明に係るリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）であれば、従来の６−ＬＵＴと比較して、約３分の１のメモリ数で図２６に示したカバー率を実現することが可能である。
【００８８】
＜その他の変形例＞
なお、本発明の構成は、上記実施形態のほか、発明の主旨を逸脱しない範囲で種々の変更を加えることが可能である。すなわち、上記実施形態は、全ての点で例示であって、制限的なものではないと考えられるべきであり、本発明の技術的範囲は、上記実施形態の説明ではなく、特許請求の範囲によって示されるものであり、特許請求の範囲と均等の意味及び範囲内に属する全ての変更が含まれると理解されるべきである。
【産業上の利用可能性】
【００８９】
本発明は、例えば、ＦＰＧＡの小面積化と低消費電力化を実現する上で有用に利用することが可能な技術である。
【符号の説明】
【００９０】
１００ プログラマブル論理回路装置（ＦＰＧＡ）
１０１ Ｉ／Ｏブロック
１０２ リコンフィギュラブルロジックブロック（ＲＬＢ）
１０３ コネクションブロック（ＣＢ）
１０４ スイッチブロック（ＳＢ）
１０５ 配線
１ 第１ルックアップテーブル（ｍ−ＬＵＴ）
２ 第２ルックアップテーブル（ｎ−ＬＵＴ）
３ 組み合わせ回路
４ セレクタ
Ａ 第１ブロック（３−ＬＵＴ）
Ｂ 第２ブロック（３−ＬＵＴ）
ＳＥＬ０、ＳＥＬ１、ＳＥＬ２ セレクタ
ＣＭＢ 組み合わせ回路
Ｇ（１、４、５、６、９、１１、１２、１４、１５、１７、１８、２１、２２、２５、２７、３０、３１、３５、３７、３８） ＮＯＲゲート
Ｇ（２、８、２０、２４、２８、３３、３４、４０） ＡＮＤゲート
Ｇ（３、７、１０、１３、１６、１９、２３、２６、２９、３２、３６、３９） ＯＲゲート
【技術分野】
【０００１】
本発明は、リコンフィギュラブルロジックブロック（以下、ＲＬＢ［Reconfigurable Logic Block］と呼ぶ）、並びに、これを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法に関するものである。
【背景技術】
【０００２】
近年、ハードウェア記述言語 （ＨＤＬ［Hardware Description Language］）を用いたプログラミングにより、半導体装置に集積化された内部論理回路を現場で自由に再構築することが可能なプログラマブル論理回路装置（ＰＬＤ［Programmable Logic Device］、ＦＰＧＡ［Field Programmable Gate Array］、ＤＡＰ／ＤＮＡ［Digital Application Processor/Distributed Network Architecture］、ＤＲＰ［Dynamically Reconfigurable Processor］など）が種々実用化されている。
【０００３】
なお、上記に関連する従来技術の一例としては、特許文献１〜特許文献７、及び、非特許文献１を挙げることができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第４，７０６，２１６号明細書
【特許文献２】米国特許第４，８７０，３０２号明細書
【特許文献３】米国特許第６，９９８，８７２号明細書
【特許文献４】米国特許出願公開第２００７／０２２２４７７号明細書
【特許文献５】特開２００３−１８０００号公報
【特許文献６】特開２００４−２４８２９３号公報
【特許文献７】特開２００７−１６６５７９号公報
【０００５】
【非特許文献１】(Vaughn Betz, Jonathan Rose, and Alexander Marquardt)著、「Architecture and CAD for Deep-Submicron FPGAs (The Springer International Series in Engineering and Computer Science) 」、Springer出版
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＦＰＧＡなどのプログラマブル論理回路装置では、所望の論理回路を実現するための基本素子としてルックアップテーブル（以下、ＬＵＴ［Look-Up Table］と呼ぶ）が用いられている。ＬＵＴは、真理値表の出力値をコンフィギュレーションメモリに１対１で保持しており、それらを複数のマルチプレクサによりデコードすることで、所望の論理回路を実現することが可能である。Ｋ入力のＬＵＴ（以下、Ｋ−ＬＵＴと呼ぶ）を用いれば、Ｋ入力以下の論理回路を全て実装することができる。しかしながら、従来のＬＵＴでは、入力数を増やすほど遅延性能が高くなる（遅延が小さくなる）が、使用されないメモリ数が増えて実装面積（ＬＵＴのサイズ）が大きくなる、言い換えれば、ＬＵＴの使用メモリ数（ＬＵＴのサイズ）と遅延性能がトレードオフの関係にある、という問題があった（例えば、特許文献１や特許文献２を参照）。
【０００７】
なお、従来より、ＬＵＴの使用メモリ数を減らす工夫として、図２７で示すようなアダプティブＬＵＴが提案されている（例えば、特許文献３や特許文献４を参照）。これは、入力数の多いＬＵＴを分割することで、入力数の少ないＬＵＴを複数個使用できるようにし、メモリ数を削減する技術である。確かに、入力数の多いアダプティブＬＵＴを使用して論理回路を実装すれば、入力数の少ないＬＵＴを多数使用して論理回路を実装する場合よりも、遅延性能を高めることが可能である。しかしながら、従来のアダプティブＬＵＴでは、入力数の多いＬＵＴを分割せずに用いた場合、ＬＵＴの使用メモリ数（消費電力）が多くなる、という問題があった。
【０００８】
また、従来より、図２８で示すようなクラスタベース論理ブロックの構成手法が提案されている（例えば、非特許文献１を参照）。これば、入力数の少ないＬＵＴを多数クラスタリングすることにより、ＬＵＴのメモリ使用率を下げずに性能を改善する技術である。しかしながら、従来のクラスタベース論理ブロックでは、論理ブロック内でＬＵＴ同士を接続するためにマルチプレクサとメモリが多数必要となるため、配線に必要なハードウェアリソースが増加する、という問題があった。
【０００９】
図２９は、上記した従来技術の特徴をまとめた一覧表である。従来のＬＵＴ（例えば、４−ＬＵＴ）は、論理ブロックのサイズが小さいので、構成メモリ数は少なくて済むが、遅延性能は低く、また、同一回路を実装したときの論理ブロックの使用数は多くなる。これに対して、従来のアダプティブＬＵＴ（例えば、アダプティブ６−ＬＵＴ）やクラスタベース論理ブロック（例えば、４−ＬＵＴ×８）は、遅延性能が高く、また、同一回路を実装したときの論理ブロックの使用数は少なくて済むが、論理ブロックのサイズが大きいので、構成メモリ数が多くなる。
【００１０】
また、その他の従来技術として、特許文献５では、Ｍ入力Ｎ出力のルックアップテーブルであって、複数のＬＵＴユニットと、前記複数のＬＵＴユニットによる内部構成を制御する内部構成制御手段と、を備えるルックアップテーブルが開示されている。この従来技術によれば、例えば、６入力３出力の場合、２−ＬＵＴを３つ、３ＬＵＴ−を２つ、または、６−ＬＵＴを１つといったように、モードを切り替えることで面積効率を向上させることが可能である。しかしながら、この従来技術では、６入力の論理回路を実装するためには６４ビットのメモリが必要であるため、テクノロジマッピングで６入力の論理回路が多数出てきた場合には、使用メモリ数が多くなっていた。また、出力線が従来のＬＵＴよりも多いので、配線領域が増加するという懸念もあった。
【００１１】
また、特許文献６では、６つの２−ＬＵＴから構成されており、完全な４−ＬＵＴと、一般的に用いられる６入力の論理関数を比較的高い割合で実装することが可能な不完全ルックアップテーブルが提案されている。この従来技術によれば、構成可能論理回路は６入力全ての論理関数のサブセットしか実行できないため、構成可能論理回路がＦＰＧＡ内で占めるシリコン領域を大幅に減少することが可能である。しかしながら、この従来技術では、論理セルからの出力線が２本あるので、６入力のサブセットとして使用した場合、配線領域が増加してしまう。また、セル内のコンフィギュレーションメモリ数については、さらなる削減の余地があった。
【００１２】
また、特許文献７では、演算回路を構成する第１の回路、および、該演算回路外の回路を構成する第２の回路を備えるリコンフィギュラブルロジックブロックであって、前記第１および第２の回路における所定の信号の設定を変化させることにより、異なる回路を構成するようにしたリコンフィギュラブルロジックブロックが提案されている。この従来技術によれば、算術演算と論理演算を効率良く実装し、また、論理演算においては、少ないＢＬＥ［Basic Logic Element］数で一部の論理回路を実装することが可能である。しかしながら、この従来技術において、実装可能な一部の論理回路は、その出現確率を考慮したものではなく、効率的な論理回路の実装については、さらなる改善の余地があった。
【００１３】
本発明は、本願の発明者らにより見出された上記の問題点に鑑み、デバイスの小面積化と低消費電力化を実現することが可能なリコンフィギュラブルロジックブロック、並びにこれを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、本発明に係るリコンフィギュラブルロジックブロックは、最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロックであって、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブルと、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブルと、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路と、前記組み合わせ回路の出力に応じて前記第１ルックアップテーブルと前記第２ルックアップテーブルのいずれか一方を選択するセレクタと、を有する構成（第１の構成）とされている。
【００１５】
なお、上記第１の構成から成るリコンフィギュラブルロジックブロックは、複数の論理回路を各々表現した真理値表を比較して、同一パターンが連続している部分を前記第２ルックアップテーブルで実装し、残りの部分を前記第１ルックアップテーブルで実装する構成（第２の構成）にするとよい。
【００１６】
また、上記第２の構成から成るリコンフィギュラブルロジックブロックにおいて、前記複数の論理回路は、Ｋ入力のルックアップテーブルでマッピングされた論理回路のうち、出現確率の高いものを含む構成（第３の構成）にするとよい。
【００１７】
また、本発明に係るプログラマブル論理回路装置は、上記第３の構成から成るリコンフィギュラブルロジックブロックを有する構成（第４の構成）とされている。
【００１８】
また、本発明に係るテクノロジマッピング方法は、上記第４の構成から成るプログラマブル論理回路装置を対象としたものであって、入力数ｊとして前記リコンフィギュラブルロジックブロックの最大入力数Ｋを設定してフローを第２ステップに進める第１ステップと；カバリングされていないノードを探索してフローを第３ステップに進める第２ステップと；ｊ入力のカットがあるか否かを判定し、カットがあればフローを第４ステップに進め、カットがなければフローを第１０ステップに進める第３ステップと；ｊ入力の部分回路にカットしてフローを第５ステップに進める第４ステップと；ｊがｍよりも大きいか否かを判定し、大きければフローを第６ステップに進め、大きくなければフローを第８ステップに進める第５ステップと；前記部分回路のＰ代表元を算出してフローを第７ステップに進める第６ステップと；前記Ｐ代表元に基づいて前記部分回路が前記リコンフィギュラブルロジックブロックで実装可能か否かを判定し、実装可能であればフローを第８ステップに進め、実装不可能であればフローを第３ステップに進める第７ステップと；前記リコンフィギュラブルロジックブロックでノードのカバリングを行い、フローを第９ステップに進める第８ステップと；全てのノードがカバリング済みであるか否かを判定し、カバリング済みであれば一連のフローを終了させ、カバリング済みでなければフローを第２ステップに進める第９ステップと；入力数ｊを一つデクリメントさせてフローを第２ステップに進める第１０ステップと；を有する構成（第５の構成）とされている。
【発明の効果】
【００１９】
本発明によれば、デバイスの小面積化と低消費電力化を実現することが可能なリコンフィギュラブルロジックブロック、並びに、これを用いたプログラマブル論理回路装置、及び、テクノロジマッピング方法を提供することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係るプログラマブル論理回路装置の全体構成例を示すブロック図
【図２】３入力論理回路の一実装例を示す図
【図３】本発明に係るリコンフィギュラブルロジックブロックの概念的構成を示す図
【図４】メモリの一使用例を示す真理値表
【図５】リコンフィギュラブルロジックブロックの第１構成例を示す図
【図６】第１構成例における入力条件とメモリとの関係を示す図
【図７】６−ＬＵＴでマッピングした回路のメモリパターン（Ｐ同値類）を示す図
【図８】６入力のテクノロジマッピング方法を示すフローチャート
【図９】本発明に係るテクノロジマッピング方法の全体像を示すフローチャート
【図１０】リコンフィギュラブルロジックブロックの第２構成例を示す図
【図１１】リコンフィギュラブルロジックブロックの第３構成例を示す図
【図１２】リコンフィギュラブルロジックブロックの第４構成例を示す図
【図１３】リコンフィギュラブルロジックブロックの第５構成例を示す図
【図１４】リコンフィギュラブルロジックブロックの第６構成例を示す図
【図１５】リコンフィギュラブルロジックブロックの第７構成例を示す図
【図１６】リコンフィギュラブルロジックブロックの第８構成例を示す図
【図１７】リコンフィギュラブルロジックブロックの第９構成例を示す図
【図１８】リコンフィギュラブルロジックブロックの第１０構成例を示す図
【図１９】リコンフィギュラブルロジックブロックの第１１構成例を示す図
【図２０】リコンフィギュラブルロジックブロックの第１２構成例を示す図
【図２１】リコンフィギュラブルロジックブロックの第１３構成例を示す図
【図２２】リコンフィギュラブルロジックブロックの第１４構成例を示す図
【図２３】リコンフィギュラブルロジックブロックの第１５構成例を示す図
【図２４】リコンフィギュラブルロジックブロックの第１６構成例を示す図
【図２５】各構成例におけるＬＵＴの形成方法とメモリの集約状態を示す図
【図２６】各構成例における論理回路のカバー率を示す図
【図２７】アダプティブＬＵＴの一従来例を示すブロック図
【図２８】クラスタベース論理ブロックの一従来例を示すブロック図
【図２９】従来技術の特徴をまとめた一覧表
【発明を実施するための形態】
【００２１】
＜プログラマブル論理回路装置＞
図１は、本発明に係るプログラマブル論理回路装置の全体構成例を示すブロック図である。本構成例のプログラマブル論理回路装置１００は、Ｉ／Ｏブロック１０１と、リコンフィギュラブルロジックブロック１０２（以下、ＲＬＢ［Reconfigurable Logic Block］１０２と略称する）と、コネクションブロック１０３（以下、ＣＢ［Connection Block］１０３と略称する）と、スイッチブロック１０４（以下、ＳＷ［Switch Block］１０４と略称する）と、配線１０５と、を有する。
【００２２】
Ｉ／Ｏブロック１０１は、外部との信号授受を行う。ＲＬＢ１０２は、マトリクス状に複数配列されており、論理回路を実現するための演算素子として使用される。ＣＢ１０３は、ＲＬＢ１０２と配線１０５とを結合する。ＳＢ１０４は、配線１０５のクロスポイントとなる。
【００２３】
プログラマブル論理回路装置１００の性能を改善するためには、新しいＲＬＢ１０２が必要であり、本発明は、主としてＲＬＢ１０２の新規な構成に関するものである。
【００２４】
＜本発明に至った経緯＞
論理回路を従来のＬＵＴで表現する場合、同じ論理関数を異なるＬＵＴのメモリパターン（構成情報）で実現しているものが多く見られる。また、ＬＵＴのメモリパターンには同じデータの繰り返し部分が多数存在する。すなわち、一般に用いられている従来のＬＵＴによる回路表現は、真理値表をそのままコンフィギュレーションデータとして表現したものであり、同じ論理回路でも複数の実装が存在する。そのため、入力信号の入れ替えによって得られる論理回路を同一とみなせば、ＬＵＴによる回路表現は本質的に冗長であると言える。以下では、ＬＵＴの冗長性について、３入力の論理回路を例示して説明する。
【００２５】
図２は、３入力論理回路の一実装例を示す図である。図２に示すように、関数ｆと関数ｇの真理値表は、一部のパターンが異なっているが、入力ｂと入力ｃを入れ替えれば、関数ｆと関数ｇを同一とみなすことができる。このとき、関数ｆを実現するための論理回路と、関数ｇを実現するための論理回路は、同じＰ［Permutation］同値類に属する。すなわち、関数ｆが関数ｇの入力順序を入れ替えることによって得られるならば、関数ｆと関数ｇは、同じＰ同値類に属すると言える。
【００２６】
本願の発明者らは、上記考察から、ＬＵＴによる回路表現の冗長性を除くことにより、従来のＬＵＴより少ないコンフィギュレーションメモリ数でも、従来と同等の論理回路を実装可能な論理セルを実現することができる、との着想を得て本発明に至った。
【００２７】
＜リコンフィギュラブルロジックブロック＞
図３は、本発明に係るリコンフィギュラブルロジックブロックの概念的構成を示す図である。本発明に係る最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただし、ｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブル１と、ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただし、ｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブル２と、ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただし、ｐはＫよりも小さくｃはｘに属する）の組み合わせ回路３と、組み合わせ回路３の出力に応じて第１ルックアップテーブル１と第２ルックアップテーブル２のいずれか一方を選択するセレクタ４と、を有する。
【００２８】
また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、アプリケーションの実装に必要な複数の論理回路を各々表現した真理値表を比較したとき、同一パターンが連続している部分（例えば、図４の破線で囲まれた部分を参照）については第２ルックアップテーブル２で実装し、残りの部分（例えば、図４の実線で囲まれた部分を参照）については第１ルックアップテーブル１で実装している。
【００２９】
また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）において、前記複数の論理回路としては、Ｋ−ＬＵＴでマッピングされた論理回路のうち、出現確率の高いものが含まれている。なお、上記マッピングに際しては、同一パターンが多く出現するように（できるだけ同じ値の出力値が並ぶように）、入力変数の入れ替えを行うことが望ましい。
【００３０】
上記の構成を採用することにより、アプリケーションの実装に必要な論理回路を従来のＫ−ＬＵＴよりも少ないコンフィギュレーションメモリ数で実現することが可能となる。より具体的に述べると、Ｋ入力の論理回路を実装する場合、従来のＫ−ＬＵＴでは２Ｋ個のメモリ数が必要であるのに対して、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば（２ｍ＋２ｎ）個のメモリ数で足りる。
【００３１】
このように、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、より少ないメモリ数で従来のＫ−ＬＵＴと同程度の機能を維持することができるので、プログラマブル論理回路装置の小面積化と低消費電力化を実現することが可能となる。また、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、従来のＫ−ＬＵＴと入出力線の本数が変わらないので、配線領域の増加を防ぐことも可能となる。
【００３２】
なお、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、複数の出力値を少ないメモリに集約し、様々な入力数（最大Ｋ入力）の論理回路に対応可能であることから、本明細書中では、Ｋ−Ａ２ＬＵＴ［Abridged Adaptive LUT］と名付けられている。
【００３３】
＜本発明のポイント＞
本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）のポイントをまとめて述べる。まず、第１のポイントは、入力数がｍよりも大きい論理回路（最大Ｋ入力）の一部を実装することが可能であり、入力数がｍ以下である論理回路の全てを実装することが可能な構造とされている点である。第２のポイントは、入力数がｍよりも大きい論理回路のうち、実装可能な一部の論理回路としては、出現確率の高いものが優先的に含まれている点、言い換えれば、実装可能な一部の論理回路の数を効率良く制限することで構成メモリ数が削減されている点である。第３のポイントは、入力の入れ替えによって互いに置換可能な論理回路が同一（Ｐ同値類）とみなされている点である。
【００３４】
＜第１構成例＞
図５は、本発明に係るリコンフィギュラブルロジックブロックの第１構成例を示す図であり、最大入力数Ｋ＝６とした場合の回路構成を示している。
【００３５】
第１構成例のリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）は、第１ブロックＡ（メモリ［０］〜［７］を用いた３−ＬＵＴ（Ａ））と、第２ブロックＢ（メモリ［１０］〜［１７］を用いた３−ＬＵＴ（Ｂ））と、２ビットのメモリ［８］及び［９］と、セレクタＳＥＬ０〜ＳＥＬ２と、組み合わせ回路ＣＭＢと、を有する。
【００３６】
第１ブロックＡは、入力信号ｉｎ１〜ｉｎ３に応じてメモリ［０］〜［７］の格納データのいずれか一つを出力する。第２ブロックＢは、入力信号ｉｎ１〜ｉｎ３に応じてメモリ［１０］〜［１７］の格納データのいずれか一つを出力する。セレクタＳＥＬ０は入力信号ｉｎ０に応じてセレクタＳＥＬ１の出力データとセレクタＳＥＬ２の出力データの一方を出力信号ｏｕｔとして選択する。セレクタＳＥＬ１は、組み合わせ回路ＣＭＢの出力に応じて第１ブロックＡの出力データとメモリ［８］の格納データの一方を選択する。セレクタＳＥＬ２は、組み合わせ回路ＣＭＢの出力に応じて第２ブロックＢの出力データとメモリ［９］の格納データの一方を選択する。
【００３７】
組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５に応じてセレクタＳＥＬ１及びＳＥＬ２の切替信号を生成する。第１構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ１と、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ２と、ＮＯＲゲートＧ１の出力とＡＮＤゲートＧ２の出力との論理和演算を行うＯＲゲートＧ３と、を有する。
【００３８】
なお、第１ブロックＡ、第２ブロックＢ、及び、セレクタＳＥＬ０によって４入力（ｉｎ０〜ｉｎ３）のルックアップテーブルが形成されており、これは図３の第１ルックアップテーブル１（ｍ＝４）に相当する。また、２ビットのメモリ［８］及び［９］とセレクタＳＥＬ０によって１入力（ｉｎ０）のルックアップテーブルが形成されており、これは図３の第２ルックアップテーブル２（ｎ＝１）に相当する。また、組み合わせ回路ＣＭＢは、図３の組み合わせ回路３に相当する。また、セレクタＳＥＬ１及びＳＥＬ２は、図３のセレクタ４に相当する。
【００３９】
従来の６−ＬＵＴでは、２６＝６４ビットのメモリが必要であるのに対して、第１構成例のリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）は、２４＋２１＝１８ビットのメモリで構成されている。
【００４０】
図６は、第１構成例における入力条件とメモリとの関係を示す図であり、図７は、６−ＬＵＴでマッピングした論理回路のメモリパターン（Ｐ同値類）を出現確率の高い順に第１位〜第７位まで示した図である。なお、図７のメモリパターンは、６−ＬＵＴの出力データＯ０〜Ｏ６３を６４ビットの２進数値として表記したものである。
【００４１】
図７から分かるように、第１位〜第７位のメモリパターン全てにおいて、第５ビット目〜第２８ビット目（Ｏ４〜Ｏ２７）と、第３７ビット目〜第６０ビット目（Ｏ３６〜Ｏ５９）は全て０か１の連続である。そこで、第１構成例では、同一値が連続している上記部分のうち、前者が１ビットのメモリ［８］に集約され、後者が１ビットのメモリ［９］に集約されている。また、残りの部分のうち、第１ビット目〜第４ビット目（Ｏ０〜Ｏ３）と第２９ビット目〜第３２ビット目（Ｏ２８〜Ｏ３１）が第１ブロックＡで実現されており、第３３ビット目〜第３６ビット目（Ｏ３２〜Ｏ３５）と第６１ビット目〜第６４ビット目（Ｏ６０〜Ｏ６３）が第２ブロックＢで実現されている。
【００４２】
具体的に述べると、第１構成例では、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，１，１｝（ただし「−」は０または１）に対応する出力データＯ０〜Ｏ３及びＯ２８〜Ｏ３１が第１ブロックＡのメモリ［０］〜［７］に保持されており、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，１，１｝に対応する出力データＯ３２〜Ｏ３５及びＯ６０〜Ｏ６３が第２ブロックＢのメモリ［１０］〜［１７］に保持されている。また、上記以外の出力データＯ４〜Ｏ２７及びＯ３６〜Ｏ５９がメモリ［８］及び［９］に集約されている。
【００４３】
そして、図６に示した通り、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，１，１｝のときには第１ブロックＡの出力データが出力信号ｏｕｔとして用いられ、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，１，１｝のときには第２ブロックＢの出力データが出力信号ｏｕｔとして用いられる。また、入力信号の組み合わせが上記以外であるときには、メモリ［８］または［９］の格納データが出力信号ｏｕｔとして用いられる。
【００４４】
ネットリストを６−Ａ２ＬＵＴ（１８ビット）で実装すれば、従来の６−ＬＵＴ（６４ビット）で実装する場合と比べて、１セル当たりのメモリ数を４６ビット削減することが可能となる。また、第１構成例の６−Ａ２ＬＵＴであれば、６−ＬＵＴで利用されるメモリパターンの約５２％、５−ＬＵＴで利用されるメモリパターンの約４７％を実現することができるので、従来よりも少ないメモリ数で論理回路を実装することが可能となる。また、従来の４−ＬＵＴで実装する場合と比べて、より少ないセル数で論理回路を実装することが可能となる。
【００４５】
＜テクノロジマッピング方法＞
図８は、６入力のテクノロジマッピング方法を示すフローチャートである。
【００４６】
ステップＳ１０１では、入力となるネットリストに対してカバリングされていないノードの探索が行われて、フローがステップＳ１０２に進められる。
【００４７】
ステップＳ１０２では、６入力のカットがあるか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ１０２に進められ、ノー判定が下された場合にはフローがステップＳ１０８に進められる。
【００４８】
ステップＳ１０３では、６入力のカットが部分回路として切り出されて、フローがステップＳ１０４に進められる。
【００４９】
ステップＳ１０４では、ステップＳ１０３でカットされた部分回路のＰ代表元が算出されて、フローがステップＳ１０５に進められる。なお、Ｐ代表元とは、Ｐ同値類中の関数を２進数値とみなした場合に最小のものを言う。
【００５０】
ステップＳ１０５では、ステップＳ１０４で算出されたＰ代表元に基づいて、ステップＳ１０３でカットされた部分回路が６−Ａ２ＬＵＴで実装可能か否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ１０６に進められ、ノー判定が下された場合にはフローがステップＳ１０２が戻されて、別のカットが探索される。
【００５１】
ステップＳ１０６では、６−Ａ２ＬＵＴでノードのカバリングが行われて、フローがステップＳ１０７に進められる。
【００５２】
ステップＳ１０７では、全てのノードがカバリング済みが否かの判定が行われる。ここで、イエス判定が下された場合には上記一連のフローが終了され、ノー判定が下された場合にはフローがステップＳ１０１に戻される。
【００５３】
ステップＳ１０８では、６−Ａ２ＬＵＴで実装可能な６入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていないことから、入力数が１つ下げられて、５入力のテクノロジマッピングが行われる。５入力のテクノロジマッピングについては、上記で説明した入力数をいずれも「６」から「５」に読み替えれば足りる。
【００５４】
その後、６−Ａ２ＬＵＴで実装可能な５入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていない場合、残りのノードについては、いずれも４入力以下の部分回路にカットされてノードのカバリングが行われる。なお、６−Ａ２ＬＵＴは４入力以下の論理回路を全て実装することができるので、Ｐ代表元の算出を行うためのステップＳ１０４や６−Ａ２ＬＵＴによる実装可能性を検証するためのステップＳ１０５はもはや必要なくなる。
【００５５】
図９は、本発明に係るテクノロジマッピング方法の全体像を示すフローチャートであって、先出の図８で説明したフローチャートをより一般化したものである。なお、本フローチャートは、Ｋ−Ａ２ＬＵＴでｍ入力以下の論理回路を全て実装することが可能であること、及び、Ｋ入力以下に分解されたゲートレベルのブーリアンネットワークを入力とすることを前提とする。
【００５６】
ステップＳ２０１では、入力数ｊとしてＫ−Ａ２ＬＵＴの最大入力数Ｋが設定されて、フローがステップＳ２０２に進められる。
【００５７】
ステップＳ２０２では、入力となるネットリストに対してカバリングされていないノードの探索が行われて、フローがステップＳ２０３に進められる。
【００５８】
ステップＳ２０３では、ｊ入力のカットがあるか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０４に進められ、ノー判定が下された場合にはフローがステップＳ２１０に進められる。
【００５９】
ステップＳ２０４では、ｊ入力のカットが部分回路として切り出されて、フローがステップＳ２０５に進められる。
【００６０】
ステップＳ２０５では、ｊがｍよりも大きいか否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０６に進められ、ノー判定が下された場合にはフローがステップＳ２０８に進められる。
【００６１】
ステップＳ２０６では、ステップＳ２０４でカットされた部分回路のＰ代表元が算出されて、フローがステップＳ２０７に進められる。
【００６２】
ステップＳ２０７では、ステップＳ２０６で算出されたＰ代表元に基づいて、ステップＳ２０４でカットされた部分回路が６−Ａ２ＬＵＴで実装可能か否かの判定が行われる。ここで、イエス判定が下された場合にはフローがステップＳ２０８に進められ、ノー判定が下された場合にはフローがステップＳ２０３が戻されて、別のカットが探索される。
【００６３】
ステップＳ２０８では、６−Ａ２ＬＵＴでノードのカバリングが行われて、フローがステップＳ２０９に進められる。
【００６４】
ステップＳ２０９では、全てのノードがカバリング済みが否かの判定が行われる。ここで、イエス判定が下された場合には上記一連のフローが終了され、ノー判定が下された場合にはフローがステップＳ２０２に戻される。
【００６５】
ステップＳ１０８では、６−Ａ２ＬＵＴで実装可能なｊ入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていないことから、入力数ｊを一つデクリメントさせて、フローがステップＳ２０２に戻される。
【００６６】
上記のように入力数ｊを一つずつデクリメントさせながらノードのカバリングを繰り返し、６−Ａ２ＬＵＴで実装可能な（ｍ＋１）入力の部分回路を全てカバリングしても、未だ全てのノードがカバリングされていない場合、残りのノードについては、いずれもｍ入力以下の部分回路にカットされてノードのカバリングが行われる。なお、６−Ａ２ＬＵＴはｍ入力以下の論理回路を全て実装することができるので、Ｐ代表元の算出を行うためのステップＳ２０６や６−Ａ２ＬＵＴによる実装可能性を検証するためのステップＳ２０７はもはや必要なくなる。そこで、ｊ＝ｍとなりステップＳ２０５でノー判定が下された場合には、フローがステップＳ２０８にジャンプされる。
【００６７】
先出の図３で示したように、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）は、ｍ入力の第１ルックアップテーブル１とｎ入力の第２ルックアップテーブル２によって構成されており、ｍ＞ｎとしたときには、ｍ入力以下の論理回路を全て実装することが可能である。従って、本発明に係るリコンフィギュラブルロジックブロック（Ｋ−Ａ２ＬＵＴ）であれば、与えられたブーリアンネットワークをＫ−ＬＵＴよりも少ないメモリ数でテクノロジマッピングすることが可能である。
【００６８】
＜第２構成例〜第１６構成例＞
出現確率の高いＰ代表元について、先出の第１構成例（図５を参照）とは異なる入力の入れ替えを行い、それぞれＰ同値類に変換した結果、０または１が連続している部分を２ビットのメモリ［８］及び［９］に集約し、残りの部分を第１ブロックＡ及び第２ブロックＢで実現した下記の第２構成例〜第１６構成例では、組み合わせ回路ＣＭＢが第１構成例と異なる回路構造となる。
【００６９】
図１０は、リコンフィギュラブルロジックブロックの第２構成例を示す図である。第２構成例では、Ｏ４〜Ｏ１５とＯ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ４７とＯ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第２構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５の否定論理和演算を行うＮＯＲゲートＧ４のみを有する。
【００７０】
図１１は、リコンフィギュラブルロジックブロックの第３構成例を示す図である。第３構成例では、Ｏ４〜Ｏ２３とＯ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ５５とＯ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第３構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ５と、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ６と、ＮＯＲゲートＧ５の出力とＮＯＲゲートＧ６の出力との論理和演算を行うＯＲゲートＧ７と、を有する。
【００７１】
図１２は、リコンフィギュラブルロジックブロックの第４構成例を示す図である。第４構成例では、Ｏ４〜Ｏ１９とＯ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３６〜Ｏ５１とＯ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ０〜Ｏ３とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ３２〜Ｏ３５とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第４構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の論理積演算を行うＡＮＤゲートＧ８と、入力信号ｉｎ３〜ｉｎ５の否定論理和演算を行うＮＯＲゲートＧ９と、ＡＮＤゲートＧ８の出力とＮＯＲゲートＧ９の出力との論理和演算を行うＯＲゲートＧ１０とを有する。
【００７２】
図１３は、リコンフィギュラブルロジックブロックの第５構成例を示す図である。第５構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ１５、及び、Ｏ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ４７、及び、Ｏ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第５構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１１と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１２と、ＮＯＲゲートＧ１１の出力とＮＯＲゲートＧ１２の出力との論理和演算を行うＯＲゲートＧ１３と、を有する。
【００７３】
図１４は、リコンフィギュラブルロジックブロックの第６構成例を示す図である。第６構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ１５、及び、Ｏ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ４７、及び、Ｏ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ１６〜Ｏ１９が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ４８〜Ｏ５１が第２ブロックＢで実現されている。なお、第６構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１５と、ＮＯＲゲートＧ１４の出力とＮＯＲゲートＧ１５の出力との論理和演算を行うＯＲゲートＧ１６と、を有する。
【００７４】
図１５は、リコンフィギュラブルロジックブロックの第７構成例を示す図である。第７構成例では、Ｏ０〜Ｏ１１とＯ２０〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３とＯ５２〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１９が第１ブロックＡで実現されており、Ｏ４４〜Ｏ５１が第２ブロックＢで実現されている。なお、第７構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３については反転入力）の否定論理和演算を行うＮＯＲゲートＧ１８と、ＮＯＲゲートＧ１７の出力とＮＯＲゲートＧ１８の出力との論理和演算を行うＯＲゲートＧ１９と、を有する。
【００７５】
図１６は、リコンフィギュラブルロジックブロックの第８構成例を示す図である。第８構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第８構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５（ただし、入力信号ｉｎ５については反転入力）の論理積演算を行うＡＮＤゲートＧ２０のみを有する。
【００７６】
図１７は、リコンフィギュラブルロジックブロックの第９構成例を示す図である。第９構成例では、Ｏ０〜Ｏ７、Ｏ１２〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３９、Ｏ４４〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第９構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２１と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２２と、ＮＯＲゲートＧ２１の出力とＮＯＲゲートＧ２２の出力との論理和演算を行うＯＲゲートＧ２３と、を有する。
【００７７】
図１８は、リコンフィギュラブルロジックブロックの第１０構成例を示す図である。第１０構成例では、Ｏ０〜Ｏ７とＯ１２〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ３９とＯ４４〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ８〜Ｏ１１とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ４０〜Ｏ４３とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１０構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ２４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２５と、ＡＮＤゲートＧ２４の出力とＮＯＲゲートＧ２５の出力との論理和演算を行うＯＲゲートＧ２６と、を有する。
【００７８】
図１９は、リコンフィギュラブルロジックブロックの第１１構成例を示す図である。第１１構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第１１構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ２７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の論理積演算を行うＡＮＤゲートＧ２８と、ＮＯＲゲートＧ２７の出力とＡＮＤゲートＧ２８の出力との論理和演算を行うＯＲゲートＧ２９と、を有する。
【００７９】
図２０は、リコンフィギュラブルロジックブロックの第１２構成例を示す図である。第１２構成例では、Ｏ０〜Ｏ１１、Ｏ１６〜Ｏ２３、及び、Ｏ２８〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３、Ｏ４８〜Ｏ５５、及び、Ｏ６０〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２４〜Ｏ２７が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ５６〜Ｏ５９が第２ブロックＢで実現されている。なお、第１２構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３０と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ４については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３１と、ＮＯＲゲートＧ３０の出力とＮＯＲゲートＧ３１の出力との論理和演算を行うＯＲゲートＧ３２と、を有する。
【００８０】
図２１は、リコンフィギュラブルロジックブロックの第１３構成例を示す図である。第１３構成例では、Ｏ０〜Ｏ３、Ｏ８〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ３５、Ｏ４０〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第１３構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５（ただし、入力信号ｉｎ４については反転入力）の論理積演算を行うＡＮＤゲートＧ３３のみを有する。
【００８１】
図２２は、リコンフィギュラブルロジックブロックの第１４構成例を示す図である。第１４構成例では、Ｏ０〜Ｏ３とＯ８〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ３５とＯ４０〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ４〜Ｏ７とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ３６〜Ｏ３９とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１４構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５の論理積演算を行うＡＮＤゲートＧ３４と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３５と、ＡＮＤゲートＧ３４の出力とＮＯＲゲートＧ３５の出力との論理和演算を行うＯＲゲートＧ３６と、を有する。
【００８２】
図２３は、リコンフィギュラブルロジックブロックの第１５構成例を示す図である。第１５構成例では、Ｏ０〜Ｏ１１、Ｏ１６〜Ｏ１９、及び、Ｏ２４〜Ｏ３１がメモリ［８］に集約され、Ｏ３２〜Ｏ４３、Ｏ４８〜Ｏ５１、及び、Ｏ５６〜Ｏ６３がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２０〜Ｏ２３が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ５２〜Ｏ５５が第２ブロックＢで実現されている。なお、第１５構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ４及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３７と、入力信号ｉｎ３〜ｉｎ５（ただし、入力信号ｉｎ３及びｉｎ５については反転入力）の否定論理和演算を行うＮＯＲゲートＧ３８と、ＮＯＲゲートＧ３７の出力とＮＯＲゲートＧ３８の出力との論理和演算を行うＯＲゲートＧ３９と、を有する。
【００８３】
図２４は、リコンフィギュラブルロジックブロックの第１６構成例を示す図である。第１６構成例では、Ｏ０〜Ｏ１１とＯ１６〜Ｏ２７がメモリ［８］に集約され、Ｏ３２〜Ｏ４３とＯ４８〜Ｏ５９がメモリ［９］に集約されている。また、Ｏ１２〜Ｏ１５とＯ２８〜Ｏ３１が第１ブロックＡで実現されており、Ｏ４４〜Ｏ４７とＯ６０〜Ｏ６３が第２ブロックＢで実現されている。なお、第１６構成例において、組み合わせ回路ＣＭＢは、入力信号ｉｎ４及びｉｎ５の論理積演算を行うＡＮＤゲートＧ４０のみを有する。
【００８４】
図２５は、第１〜第１６構成例におけるＬＵＴの形成方法とメモリの集約状態を示す図である。なお、符号「Ａ」は出力データが第１ブロックＡ（メモリ［０］〜［７］）に各々保持されていることを示しており、符号「Ｂ」は出力データが第２ブロックＢ（メモリ［１０］〜［１７］）に各々保持されていることを示している。また、符号「８」は出力データがメモリ［８］に集約されていることを示しており、符号「９」は出力データがメモリ［９］に集約されていることを示している。
【００８５】
例えば、第２構成例の場合、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛０，−，−，０，０，０｝及び｛０，−，−，１，０，０｝のときには第１ブロックＡの出力データが出力信号ｏｕｔとして用いられ、｛ｉｎ０，ｉｎ１，ｉｎ２，ｉｎ３，ｉｎ４，ｉｎ５｝＝｛１，−，−，０，０，０｝及び｛１，−，−，１，０，０｝のときには第２ブロックＢの出力データが出力信号ｏｕｔとして用いられる。また、入力信号の組み合わせが上記以外であるときには、メモリ［８］または［９］の格納データが出力信号ｏｕｔとして用いられる。
【００８６】
図２６は、第１〜第１６構成例における論理回路のカバー率（６入力論理回路のカバー率、５入力論理回路のカバー率、及び、４入力以下も含めた全ての論理回路のカバー率）を示す図である。この表は、ＭＣＮＣ［Microelectronics Center of North Carolina］ ベンチマーク回路（１１７種類）をＥＭａｐによってテクノロジマッピングを行った場合において、使用された論理回路のうち、本発明に係るリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）で実装可能であったものの割合を示している。なお、ＥＭａｐとは、ＵＢＣ［University of British Columbia］で開発された電力最適化を目的としたテクノロジマッピングツールである。
【００８７】
本発明に係るリコンフィギュラブルロジックブロック（６−Ａ２ＬＵＴ）であれば、従来の６−ＬＵＴと比較して、約３分の１のメモリ数で図２６に示したカバー率を実現することが可能である。
【００８８】
＜その他の変形例＞
なお、本発明の構成は、上記実施形態のほか、発明の主旨を逸脱しない範囲で種々の変更を加えることが可能である。すなわち、上記実施形態は、全ての点で例示であって、制限的なものではないと考えられるべきであり、本発明の技術的範囲は、上記実施形態の説明ではなく、特許請求の範囲によって示されるものであり、特許請求の範囲と均等の意味及び範囲内に属する全ての変更が含まれると理解されるべきである。
【産業上の利用可能性】
【００８９】
本発明は、例えば、ＦＰＧＡの小面積化と低消費電力化を実現する上で有用に利用することが可能な技術である。
【符号の説明】
【００９０】
１００ プログラマブル論理回路装置（ＦＰＧＡ）
１０１ Ｉ／Ｏブロック
１０２ リコンフィギュラブルロジックブロック（ＲＬＢ）
１０３ コネクションブロック（ＣＢ）
１０４ スイッチブロック（ＳＢ）
１０５ 配線
１ 第１ルックアップテーブル（ｍ−ＬＵＴ）
２ 第２ルックアップテーブル（ｎ−ＬＵＴ）
３ 組み合わせ回路
４ セレクタ
Ａ 第１ブロック（３−ＬＵＴ）
Ｂ 第２ブロック（３−ＬＵＴ）
ＳＥＬ０、ＳＥＬ１、ＳＥＬ２ セレクタ
ＣＭＢ 組み合わせ回路
Ｇ（１、４、５、６、９、１１、１２、１４、１５、１７、１８、２１、２２、２５、２７、３０、３１、３５、３７、３８） ＮＯＲゲート
Ｇ（２、８、２０、２４、２８、３３、３４、４０） ＡＮＤゲート
Ｇ（３、７、１０、１３、１６、１９、２３、２６、２９、３２、３６、３９） ＯＲゲート
【特許請求の範囲】
【請求項１】
最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロックであって、
ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブルと、
ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブルと、
ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路と、
前記組み合わせ回路の出力に応じて前記第１ルックアップテーブルと前記第２ルックアップテーブルのいずれか一方を選択するセレクタと、
を有することを特徴とするリコンフィギュラブルロジックブロック。
【請求項２】
複数の論理回路を各々表現した真理値表を比較して、同一パターンが連続している部分を前記第２ルックアップテーブルで実装し、残りの部分を前記第１ルックアップテーブルで実装することを特徴とする請求項１に記載のリコンフィギュラブルロジックブロック。
【請求項３】
前記複数の論理回路は、Ｋ入力のルックアップテーブルでマッピングされた論理回路のうち出現確率の高いものを含むことを特徴とする請求項２に記載のリコンフィギュラブルロジックブロック。
【請求項４】
請求項３に記載のリコンフィギュラブルロジックブロックを有することを特徴とするプログラマブル論理回路装置。
【請求項５】
請求項４に記載のプログラマブル論理回路装置を対象としたテクノロジマッピング方法であって、
入力数ｊとして前記リコンフィギュラブルロジックブロックの最大入力数Ｋを設定してフローを第２ステップに進める第１ステップと；
カバリングされていないノードを探索してフローを第３ステップに進める第２ステップと；
ｊ入力のカットがあるか否かを判定し、カットがあればフローを第４ステップに進め、カットがなければフローを第１０ステップに進める第３ステップと；
ｊ入力の部分回路にカットしてフローを第５ステップに進める第４ステップと；
ｊがｍよりも大きいか否かを判定し、大きければフローを第６ステップに進め、大きくなければフローを第８ステップに進める第５ステップと；
前記部分回路のＰ代表元を算出してフローを第７ステップに進める第６ステップと；
前記Ｐ代表元に基づいて前記部分回路が前記リコンフィギュラブルロジックブロックで実装可能か否かを判定し、実装可能であればフローを第８ステップに進め、実装不可能であればフローを第３ステップに進める第７ステップと；
前記リコンフィギュラブルロジックブロックでノードのカバリングを行い、フローを第９ステップに進める第８ステップと；
全てのノードがカバリング済みであるか否かを判定し、カバリング済みであれば一連のフローを終了させ、カバリング済みでなければフローを第２ステップに進める第９ステップと；
入力数ｊを一つデクリメントさせてフローを第２ステップに進める第１０ステップと；
を有することを特徴とするテクノロジマッピング方法。
【請求項１】
最大Ｋ入力（ｘ［０］〜ｘ［Ｋ−１］）のリコンフィギュラブルロジックブロックであって、
ｍ入力（ｙ［０］〜ｙ［ｍ−１］、ただしｍはＫよりも小さくｙはｘに属する）の第１ルックアップテーブルと、
ｎ入力（ｚ［０］〜ｚ［ｎ−１］、ただしｎはＫよりも小さくｚはｘに属する）の第２ルックアップテーブルと、
ｐ入力（ｃ［０］〜ｃ［ｐ−１］、ただしｐはＫよりも小さくｃはｘに属する）の組み合わせ回路と、
前記組み合わせ回路の出力に応じて前記第１ルックアップテーブルと前記第２ルックアップテーブルのいずれか一方を選択するセレクタと、
を有することを特徴とするリコンフィギュラブルロジックブロック。
【請求項２】
複数の論理回路を各々表現した真理値表を比較して、同一パターンが連続している部分を前記第２ルックアップテーブルで実装し、残りの部分を前記第１ルックアップテーブルで実装することを特徴とする請求項１に記載のリコンフィギュラブルロジックブロック。
【請求項３】
前記複数の論理回路は、Ｋ入力のルックアップテーブルでマッピングされた論理回路のうち出現確率の高いものを含むことを特徴とする請求項２に記載のリコンフィギュラブルロジックブロック。
【請求項４】
請求項３に記載のリコンフィギュラブルロジックブロックを有することを特徴とするプログラマブル論理回路装置。
【請求項５】
請求項４に記載のプログラマブル論理回路装置を対象としたテクノロジマッピング方法であって、
入力数ｊとして前記リコンフィギュラブルロジックブロックの最大入力数Ｋを設定してフローを第２ステップに進める第１ステップと；
カバリングされていないノードを探索してフローを第３ステップに進める第２ステップと；
ｊ入力のカットがあるか否かを判定し、カットがあればフローを第４ステップに進め、カットがなければフローを第１０ステップに進める第３ステップと；
ｊ入力の部分回路にカットしてフローを第５ステップに進める第４ステップと；
ｊがｍよりも大きいか否かを判定し、大きければフローを第６ステップに進め、大きくなければフローを第８ステップに進める第５ステップと；
前記部分回路のＰ代表元を算出してフローを第７ステップに進める第６ステップと；
前記Ｐ代表元に基づいて前記部分回路が前記リコンフィギュラブルロジックブロックで実装可能か否かを判定し、実装可能であればフローを第８ステップに進め、実装不可能であればフローを第３ステップに進める第７ステップと；
前記リコンフィギュラブルロジックブロックでノードのカバリングを行い、フローを第９ステップに進める第８ステップと；
全てのノードがカバリング済みであるか否かを判定し、カバリング済みであれば一連のフローを終了させ、カバリング済みでなければフローを第２ステップに進める第９ステップと；
入力数ｊを一つデクリメントさせてフローを第２ステップに進める第１０ステップと；
を有することを特徴とするテクノロジマッピング方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【公開番号】特開２０１２−１４２６６２（Ｐ２０１２−１４２６６２Ａ）
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願番号】特願２０１０−２９２０２４（Ｐ２０１０−２９２０２４）
【出願日】平成２２年１２月２８日（２０１０．１２．２８）
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（０００１１６０２４）ローム株式会社 (3,539)
【Ｆターム（参考）】
【公開日】平成２４年７月２６日（２０１２．７．２６）
【国際特許分類】
【出願日】平成２２年１２月２８日（２０１０．１２．２８）
【出願人】（５０４１５９２３５）国立大学法人 熊本大学 (314)
【出願人】（０００１１６０２４）ローム株式会社 (3,539)
【Ｆターム（参考）】
[ Back to top ]