(57)【特許請求の範囲】
【請求項１】
第１〜第３の構成メモリを含む構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）及び第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図１，図６）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）に基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力する第１のマルチプレクサ回路（１５）とを備えたベース部（１）であって、上記第２の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）に対して正転又は反転し、もしくは所定の定数を出力する複数の第１のプログラマブルナンドゲート回路（２２）と、
複数のマルチプレクサ（２１）を備えて構成され、上記複数の第１のプログラマブルナンドゲート回路（２２）からの複数の出力データに基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力する第２のマルチプレクサ回路（２５）と、
第３の構成メモリ（Ｍ１，Ｍ２）に格納された第３の構成データに基づいて、上記第２のマルチプレクサ回路（２５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力する第２のプログラマブルナンドゲート回路（２３）とを備えたことを特徴とするプログラマブル論理回路（図１，図６）。
【請求項２】
第１〜第３の構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）、第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）及び第３の入力データ（図２のＩｎ３；図４ＢのＩｎ２）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図２，図４Ｂ）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第３の入力データ（図２のＩｎ３；図４ＢのＩｎ２）に基づいて上記複数の第１の構成データのうちの複数の出力データを選択して出力する第１のマルチプレクサ回路（１５の最上段）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）に基づいて上記第１のマルチプレクサ回路（１５の最上段）から出力される複数のデータのうちの１つの出力データを選択して出力する第２のマルチプレクサ回路（１５の２段目〜最下段）とを備えたベース部（１）であって、上記第２及び第３の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する第１の出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）に対して正転又は反転し、もしくは所定の定数を出力する少なくとも１つの第１のプログラマブルナンドゲート回路（２２）と、
少なくとも１つのマルチプレクサ（２１）を備えて構成され、上記各第１のプログラマブルナンドゲート回路（２２）からの出力データに基づいて、上記第１のマルチプレクサ回路（１５の最上段）から出力される複数の出力データのうちの１つの出力データを選択して出力する第３のマルチプレクサ回路（２５）と、
第３の構成メモリ（Ｍ１，Ｍ２）に格納された第３の構成データに基づいて、上記各第３のマルチプレクサ回路（２５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力する第２のプログラマブルナンドゲート回路（２３）とを備えたことを特徴とするプログラマブル論理回路（図２，図４Ｂ）。
【請求項３】
第１〜第２の構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）及び第２の入力データ（Ｉｎ１〜Ｉｎ２）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図４Ａ）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（Ｉｎ１〜Ｉｎ２）に基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力するマルチプレクサ回路（１５）とを備えたベース部（１）であって、上記第２の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記マルチプレクサ回路（１５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力するプログラマブルナンドゲート回路（２３）を備えたことを特徴とするプログラマブル論理回路（図４Ａ）。
【請求項４】
請求項２記載のプログラマブル論理回路（図２，図４Ｂ）である拡張ベース部（５）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数の一部を示す論理回路を構成する拡張付加ルックアップテーブル部（４）と、
第４の入力データ（図５のＩｎ０）に基づいて、上記拡張ベース部（５）からの出力データと、上記拡張付加ルックアップテーブル部（４）からの出力データとのうちの１つの出力データを選択して出力する第２の出力選択部（３）とを備えたプログラマブル論理回路（図５）であって、
上記拡張付加ルックアップテーブル部（４）は、
第４の構成メモリ（Ｍ１，Ｍ２）に格納された第４の構成データに基づいて、上記第１の入力データ（図５のＩｎ１）に対して正転又は反転、もしくは所定の定数を出力する第３のプログラマブルナンドゲート回路（４２）と、
マルチプレクサ（４１）を備えて構成され、上記第３のプログラマブルナンドゲート回路（４２）からの出力データに基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する第３のマルチプレクサ回路（４５）と、
第５の構成メモリ（Ｍ１，Ｍ２）に格納された第５の構成データに基づいて、上記第３のマルチプレクサ回路（４５）からの出力データに対して正転又は反転、もしくは所定の定数を出力する第４のプログラマブルナンドゲート回路（４３）とを備えたことを特徴とするプログラマブル論理回路（図５）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構成データに基づいてプログラマブルに論理回路を構成することができるプログラマブル論理回路及びその構成方法に関する。
【背景技術】
【０００２】
ＦＰＧＡ（Field Programmable Gate Array）は安価で低リスクという特徴から、大規模化、複雑化が進むシステムの実装デバイスとして注目を浴びている。一方でＦＰＧＡは専用回路に比べ面積、動作速度等の面で劣っているため、性能の改善が求められている。商用ＦＰＧＡで用いられる基本論理セルの大半はルックアップテーブル（以下、ＬＵＴという。）である。
【０００３】
一般には、ＬＵＴの入力数を増やすに従い、ＦＰＧＡの動作速度改善が期待できる。しかし、商用ＦＰＧＡには４入力から６入力、又はそれらをベースとしたアダプティブＬＵＴが用いられており、７入力以上のＬＵＴは使われていない。これは、ＬＵＴの入力数ｎに対して回路リソースが２ｎのオーダーで増加するためである。すなわち７入力以上のＬＵＴは速度向上よりも面積増加のデメリットの方が大きい。
【０００４】
一方でＬＵＴとは対照的に、頻出論理のサブセットから成る論理セルが存在する（例えば、非特許文献１参照）。これらは論理セルの論理表現能力を絞ることで、論理セル単位の小型化を図っている。非特許文献１では、ＡＮＤ−Ｉｎｖｅｒｔｅｒグラフの特徴を利用した小面積ＬＵＴが提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第４７０６２１６号明細書
【特許文献２】米国特許第４８７０３０２号明細書
【特許文献３】特表平１０−５０７６０５号公報
【特許文献４】特開２００３−２７３７２７号公報
【特許文献５】特開２００７−１６６５７９号公報
【特許文献６】特開２０１２−４４６１８号公報
【特許文献７】特開２０１２−１４２６６２号公報
【非特許文献】
【０００６】
【非特許文献１】Jason H. Anderson et al., "Area-Efficient FPGA Logic Elements: Architecture and Synthesis", Proceedings of the 16th Asia and South Pacific Design Automation Conference (ASP-DAC), pp.369-375, 2011.
【非特許文献２】D. Chai et al., "`Building a Better Boolean Matcher and Symmetry Detector", Proceedings of DATE 2006, pp.1079-1084, 2006.
【非特許文献３】K. McElvain, "IWLS'93 Benchmark Set: Version 4.0", Distributed as part of the MCNC International Workshop on Logic Synthesis '93 benchmark distribution, 1993.
【非特許文献４】V. Bets, "175.vpr SPEC CPU2000 Benchmark Description File", ［平成２５年８月２日検索］、インターネット<URL: http://www.spec.org/osg/cpu2000/CINT2000/175.vpr/docs/175.vpr.html>
【非特許文献５】A. Mishchenko et al., "Combinational and Sequential Mapping with Priority Cuts", Proceedings of ICCAD, pp.354-361, 2007.
【非特許文献６】Berkeley Logic Synthesis and Verification Group, "ABC: A System for Sequential Synthesis and Verification", ［平成２５年８月２日検索］、インターネット<URL: http://www.eecs.berkeley.edu/~alanmi/abc/>
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１では評価の最終結果が示されておらず、その効果は十分に立証されていない。
【０００８】
特許文献１及び２において開示されたＬＵＴは、構成メモリに論理回路の出力値を保持させ、それらをデコードすることで論理回路を実装している。しかし、任意の論理を実装可能であるという柔軟性を持っているが、表現に冗長性があり、回路リソース量（コンフィグレーションメモリ、構成トランジスタ数など）が多くなる傾向があるという問題点があった。
【０００９】
特許文献３において開示されたプログラマブル論理のモジュールでは、マルチプレクサベースの８入力論理セルであり、一部の組み合わせ論理を実現している。しかし、論理セル単体の面積はＬＵＴよりも小さいが、配線リソースを多く必要とする傾向があるという問題点があった。
【００１０】
例えば特許文献６において、本発明者らは、コンパクトに構成された一般的な再構成可能な素子論理セル（ＣＯＧＲＥ（Compactly Organized Generic Reconfigurable Element）論理セル）を提案している。ＣＯＧＲＥ論理セルはＮＰＮ同値類（例えば、非特許文献６参照）を利用しており、ＭＣＮＣ（Microelectronics Center of north Carolina）ベンチマークセット（例えば、非特許文献２参照）の頻出論理を効率よくカバーする構成となっている。しかしながら、ＭＣＮＣ以外のベンチマーク回路の実装効率は悪く、論理セルとしての汎用性は高くない。また、７入力及び８入力のＣＯＧＲＥ論理セルは同入力数のＬＵＴに比べて性能改善が得られていない。
【００１１】
本発明の目的は以上の問題点を解決し、従来技術に比較して、必要なメモリ数を大幅に削減でき、従来技術に係るＬＵＴと同程度の機能を保持しつつ小さい面積で実現し、消費電力を小さくすることができるプログラマブル論理回路とその構成方法を提供することにある。
【課題を解決するための手段】
【００１２】
第１の発明に係るプログラマブル論理回路は、
第１〜第３の構成メモリを含む構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）及び第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図１，図６）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）に基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力する第１のマルチプレクサ回路（１５）とを備えたベース部（１）であって、上記第２の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記第２の入力データ（図１のＩｎ１〜Ｉｎｍ；図６のＩｎ１〜Ｉｎ４）に対して正転又は反転し、もしくは所定の定数を出力する複数の第１のプログラマブルナンドゲート回路（２２）と、
複数のマルチプレクサ（２１）を備えて構成され、上記複数の第１のプログラマブルナンドゲート回路（２２）からの複数の出力データに基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力する第２のマルチプレクサ回路（２５）と、
第３の構成メモリ（Ｍ１，Ｍ２）に格納された第３の構成データに基づいて、上記第２のマルチプレクサ回路（２５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力する第２のプログラマブルナンドゲート回路（２３）とを備えたことを特徴とする。
【００１３】
第２の発明に係るプログラマブル論理回路は、
第１〜第３の構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）、第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）及び第３の入力データ（図２のＩｎ３；図４ＢのＩｎ２）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図２，図４Ｂ）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第３の入力データ（図２のＩｎ３；図４ＢのＩｎ２）に基づいて上記複数の第１の構成データのうちの複数の出力データを選択して出力する第１のマルチプレクサ回路（１５の最上段）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）に基づいて上記第１のマルチプレクサ回路（１５の最上段）から出力される複数のデータのうちの１つの出力データを選択して出力する第２のマルチプレクサ回路（１５の２段目〜最下段）とを備えたベース部（１）であって、上記第２及び第３の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する第１の出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記第２の入力データ（図２のＩｎ１〜Ｉｎ２；図４ＢのＩｎ１）に対して正転又は反転し、もしくは所定の定数を出力する少なくとも１つの第１のプログラマブルナンドゲート回路（２２）と、
少なくとも１つのマルチプレクサ（２１）を備えて構成され、上記各第１のプログラマブルナンドゲート回路（２２）からの出力データに基づいて、上記第１のマルチプレクサ回路（１５の最上段）から出力される複数の出力データのうちの１つの出力データを選択して出力する第３のマルチプレクサ回路（２５）と、
第３の構成メモリ（Ｍ１，Ｍ２）に格納された第３の構成データに基づいて、上記各第３のマルチプレクサ回路（２５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力する第２のプログラマブルナンドゲート回路（２３）とを備えたことを特徴とする。
【００１４】
第３の発明に係るプログラマブル論理回路は、
第１〜第２の構成メモリ（１０，Ｍ１，Ｍ２）に格納される複数の構成データに基づいて、プログラマブルに回路構成されたプログラマブル論理回路であり、第１の入力データ（Ｉｎ０）及び第２の入力データ（Ｉｎ１〜Ｉｎ２）を含む入力データに対して所定の論理演算を行うプログラマブル論理回路（図４Ａ）であって、
複数の第１の構成データを格納する第１の構成メモリ（１０）と、複数のマルチプレクサ（１１）を備えて構成されかつ上記第２の入力データ（Ｉｎ１〜Ｉｎ２）に基づいて、上記複数の第１の構成データのうちの１つの出力データを選択して出力するマルチプレクサ回路（１５）とを備えたベース部（１）であって、上記第２の入力データを変数とする論理関数をシャノン展開により展開されて生成された２つの部分論理関数のうちの一方の部分論理関数を示す論理回路を構成するベース部（１）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数を示す論理回路を構成する付加ルックアップテーブル部（２）と、
上記第１の入力データ（Ｉｎ０）に基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する出力選択部（３）とを備え、
上記付加ルックアップテーブル部（２）は、
第２の構成メモリ（Ｍ１，Ｍ２）に格納された第２の構成データに基づいて、上記マルチプレクサ回路（１５）からの出力データに対して正転又は反転し、もしくは所定の定数を出力するプログラマブルナンドゲート回路（２３）を備えたことを特徴とする。
【００１５】
第４の発明に係るプログラマブル論理回路は、第２の発明に係るプログラマブル論理回路（図２，図４Ｂ）である拡張ベース部（５）と、
上記展開されて生成された２つの部分論理関数のうちの他方の部分論理関数の一部を示す論理回路を構成する拡張付加ルックアップテーブル部（４）と、
第４の入力データ（図５のＩｎ０）に基づいて、上記拡張ベース部（５）からの出力データと、上記拡張付加ルックアップテーブル部（４）からの出力データとのうちの１つの出力データを選択して出力する第２の出力選択部（３）とを備えたプログラマブル論理回路（図５）であって、
上記拡張付加ルックアップテーブル部（４）は、
第４の構成メモリ（Ｍ１，Ｍ２）に格納された第４の構成データに基づいて、上記第１の入力データ（図５のＩｎ１）に対して正転又は反転、もしくは所定の定数を出力する第３のプログラマブルナンドゲート回路（４２）と、
マルチプレクサ（４１）を備えて構成され、上記第３のプログラマブルナンドゲート回路（４２）からの出力データに基づいて、上記ベース部（１）からの出力データと、上記付加ルックアップテーブル部（２）からの出力データとのうちの１つの出力データを選択して出力する第３のマルチプレクサ回路（４５）と、
第５の構成メモリ（Ｍ１，Ｍ２）に格納された第５の構成データに基づいて、上記第３のマルチプレクサ回路（４５）からの出力データに対して正転又は反転、もしくは所定の定数を出力する第４のプログラマブルナンドゲート回路（４３）とを備えたことを特徴とする。
【発明の効果】
【００１８】
本発明に係るプログラマブル論理回路とその構成方法によれば、従来技術に比較して、必要なメモリ数を大幅に削減でき、従来技術に係るＬＵＴと同程度の機能を保持しつつ小さい面積で実現し、消費電力を小さくすることができる。また、拡張付加ＬＵＴ部を備えることにより、上記プログラマブル論理回路の入力数を拡張できる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施形態に係るプログラマブル論理回路の一般例Ｋ−ＳＬＭ（ｍ，ｎ）を示すブロック図である。
【図２】本発明の実施形態に係るプログラマブル論理回路の構成例４−ＳＬＭ（３，２）を示すブロック図である。
【図３Ａ】実施形態及び実施例に係るプログラマブル論理回路において用いるプログラマブルナンドゲート回路２２，２３，４２，４３の構成を示す回路図である。
【図３Ｂ】図３Ａのプログラマブルナンドゲート回路２２，２３，４２，４３の真理値表を示す図である。
【図３Ｃ】図３Ａのプログラマブルナンドゲート回路２２，２３，４２，４３のブロック図を示す図である。
【図４Ａ】実施形態に係るプログラマブル論理回路（３−ＳＬＭ）において用いる０入力付加ＬＵＴ部（０−ＬＵＴ＋ＰＮ）２の構成を示すブロック図である。
【図４Ｂ】実施形態に係るプログラマブル論理回路（３−ＳＬＭ）において用いる１入力付加ＬＵＴ部（１−ＬＵＴ＋ＰＮ）２の構成を示すブロック図である。
【図５】本発明の変形例に係るプログラマブル論理回路（５−ＳＬＭ（３，２，１））の構成を示すブロック図である。
【図６】本発明の実施例１に係るプログラマブル論理回路（５−ＳＬＭ（４，４））の構成を示すブロック図である。
【図７】本発明の実施例２に係るプログラマブル論理回路（５−ＳＬＭ（４，３））の構成を示すブロック図である。
【図８】本発明の実施例３に係るプログラマブル論理回路（５−ＳＬＭ（４，２））の構成を示すブロック図である。
【図９】本発明の実施例４に係るプログラマブル論理回路（５−ＳＬＭ（４，１））の構成を示すブロック図である。
【図１０】本発明の実施例５に係るプログラマブル論理回路（５−ＳＬＭ（４，０））の構成を示すブロック図である。
【図１１】本発明の実施例６に係るプログラマブル論理回路（６−ＳＬＭ（４，２，１））の構成を示すブロック図である。
【図１２】本発明の実施例６に係るプログラマブル論理回路（６−ＳＬＭ（４，２，０））の構成を示すブロック図である。
【図１３】本発明に係る実施形態及び実施例に対する評価で使用するクラスタアーキテクチャの構成を示すブロック図である。
【図１４】本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する評価の手順を示すフローチャートである。
【図１５】本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する実装面積の評価結果を示すグラフである。
【図１６】本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対するクリティカルパス遅延の評価結果を示すグラフである。
【図１７】本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する面積遅延積の評価結果を示すグラフである。
【図１８】本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する構成メモリ数の評価結果を示すグラフである。
【図１９】本発明に係る実施例に係るプログラマブル論理回路（８−ＳＬＭ）の各構成例に対する８入力論理カバー率の評価結果を示すグラフである。
【図２０】本発明に係る実施例に係るプログラマブル論理回路（７−ＳＬＭ）の各構成例に対する７入力論理カバー率の評価結果を示すグラフである。
【図２１】本発明に係る実施例に係るプログラマブル論理回路（６−ＳＬＭ）の各構成例に対する６入力論理カバー率の評価結果を示すグラフである。
【図２２】本発明に係る実施例に係るプログラマブル論理回路（５−ＳＬＭ）の各構成例に対する５入力論理カバー率の評価結果を示すグラフである。
【発明を実施するための形態】
【００２０】
以下、本発明に係る実施形態について図面を参照して説明する。なお、以下の各実施形態において、同様又は対応する構成要素については同一の符号を付している。
【００２１】
１．実施形態の特徴等
本実施形態では、２種類のベンチマークセットの頻出論理に対し、シャノン展開後の部分関数間に見られる共通の特徴を明らかにする。また、得られた特徴に基づいた論理セルアーキテクチャ−スケーラビリティ論理モジュール（ＳＬＭ（Scalability Logic Module））にてなるプログラマブル論理回路を提案する。ＳＬＭはＬＵＴをベース部とした構成をとっているが、同入力数のＬＵＴよりも小面積、少構成メモリ数であるという特有の効果を有する。加えて、面積を大きく増やすことなく７入力、８入力、もしくはそれ以上の入力数へ拡張できるという特有の効果を有する。
【００２２】
本実施形態の面積削減手法は特許文献６と同じく、ベンチマークセットの頻出回路を利用するものである。ただし先行研究での結果を踏まえ、本実施形態では２種類のベンチマークセットを利用する。また、特許文献６が頻出論理の特徴に着目したのに対し、本実施形態では頻出論理のシャノン展開後の特徴に着目することを特徴としている。以下、本実施形態の詳細について説明する。
【００２３】
２．実装回路に出現する論理の特徴
以下では、２種類のベンチマークセットにおける頻出論理の調査を行う。続いて、それらの論理をシャノン展開して得られた部分関数間の特徴について述べる。
【００２４】
２−１．論理出現率の調査
ベンチマーク回路として２０種のＭＣＮＣベンチマーク回路（例えば、非特許文献３参照）及び、１３種のＶＰＲ（Versatile Place and Route）ベンチマーク回路（例えば、非特許文献４参照）を用いた調査を行った。ＭＣＮＣベンチマークは、論理合成後のＢｌｉｆ形式で提供されている。一方、ＶＰＲベンチマークはＨＤＬ形式で提供されており、算術演算回路が多く含まれているのが特徴である。また、ＭＣＮＣベンチマーク中の回路と比較して、ＶＰＲベンチマーク中の回路は大規模なものが多い。
【００２５】
これらのベンチマーク回路に対して５入力ＬＵＴを対象としてテクノロジマッピングを行い、得られた各ＬＵＴの論理を集計した。テクノロジマッピングにはＵＣＢ（University of California, Berkeley）で開発されたプライオリティカットベースのツール（例えば、非特許文献５参照）を用いた。このテクノロジマッピングツールは論理回路用の合成、検証プラットフォームであるＡＢＣ（例えば、非特許文献６参照）上に実装されている。また、論理の集計方法に関しては（例えば、特許文献６参照）と同様にＮＰＮ同値類（例えば、非特許文献２参照）を用いた分類を行う。論理関数ｆのＮＰＮ同値類とは、論理関数ｆに入出力の反転、入力順番の入れ替えを施して得られる論理の集合である。
【００２６】
表１にそれぞれのベンチマークセットにて出現率の高い論理を示す。表１中のＡ、Ｂ、Ｃ、Ｄ及びＥは５入力論理関数の入力を表している。また、表１で表記している論理はＮＰＮ同値類の１つである。
【００２７】
【表１】
0005937550.tif 000002
【００２８】
表１を見ると、ＭＣＮＣベンチマーク回路では単純なＡＮＤ−ＯＲ演算が上位を占めている。それに対してＶＰＲベンチマークでは、多数決回路やＸＯＲ演算といった論理が上位を占めている。このように両ベンチマーク回路の出現論理は傾向が大きく異なっていることが分かる。
【００２９】
２−２．頻出論理に共通する特徴
上述したように、両ベンチマーク間での頻出論理は一見すると傾向が大きく異なっている。そこで、得られた論理に対しシャノン展開を行うことで、ある共通の特徴が得られることに着目する。シャノン展開とは論理関数の分解や解析を行うための最も基本的な論理式変形法の一つである。以下にシャノン展開の定義を示す。
【００３０】
【数１】
0005937550.tif 000003
【００３１】
シャノン展開後に生成された論理関数を元の論理関数に対する部分関数と呼ぶ。ここで、以下の特徴に注目する。ある論理関数ｆに対し任意の入力ｘでシャノン展開する。すると次式で表される。
【００３２】
【数２】
0005937550.tif 000004
【００３３】
ここで、部分関数ｆ（ｘ＝０）又はｆ（ｘ＝１）のいずれか片方にだけ以下の操作を加えることで、
ｆ（ｘ＝０）＝ｆ（ｘ＝１）      （３）
が成立する入力変数ｘが存在するとき、部分関数ｆは入力ｘについて部分関数間の変換が可能である。
【００３４】
（Ａ）任意の入力変数を正転し又は反転し、もしくは所定の定数を代入する操作。
（Ｂ）出力を正転し又は反転し、もしくは所定の定数を出力する操作。
【００３５】
例として、ＭＣＮＣベンチマーク出現率が１位の論理のシャノン展開を以下に示す。
【００３６】
ｆ＝Ａ・Ｂ・Ｃ・Ｄ・Ｅ      （４）
【００３７】
Ａについてシャノン展開を行い、得られた部分関数ｆ（Ａ＝０），ｆ（Ａ＝１）はそれぞれ以下のようになる。
【００３８】
ｆ（Ａ＝０）＝０      （５）
ｆ（Ａ＝１）＝Ｂ・Ｃ・Ｄ・Ｅ      （６）
【００３９】
ここでｆ（Ａ＝１）の出力を定数０とすると以下のようになる。
【００４０】
ｆ（Ａ＝１）＝０＝ｆ（Ａ＝０）      （７）
【００４１】
次に、ＶＰＲベンチマーク出現率１位の論理のシャノン展開を以下に示す。
【００４２】
ｇ＝Ａ・（Ｃ・Ｄ＋Ｄ・Ｅ＋Ｃ・Ｅ）
＋Ａ・Ｂ＋Ｂ・（Ｃ・Ｄ＋Ｄ・Ｅ＋Ｃ・Ｅ）      （８）
【００４３】
Ａについてシャノン展開を行い、得られた部分関数ｇ（Ａ＝０），ｇ（Ａ＝１）はそれぞれ以下のようになる。
【００４４】
ｇ（Ａ＝０）＝Ｂ・（Ｃ・Ｄ＋Ｄ・Ｅ＋Ｃ・Ｅ）      （９）
ｇ（Ａ＝１）＝Ｂ＋（Ｃ・Ｄ＋Ｄ・Ｅ＋Ｃ・Ｅ）      （１０）
【００４５】
ここで、ｇ（Ａ＝０）の入力変数Ｂ、Ｃ、Ｄ、Ｅと出力を反転する。すると次式を得る。
【００４６】
【数３】
0005937550.tif 000005
【００４７】
上述した例より、各論理とも部分関数間の変換が可能であることが分かる。
【００４８】
次いで、表２に、部分関数間の変換が可能な論理の割合を示す。
【００４９】
【表２】
0005937550.tif 000006
【００５０】
この表２は２つのベンチマーク回路の出現論理のうち、部分関数間の変換が可能なものの割合を示している。ここでの出現論理とは、Ｋ入力ＬＵＴでテクノロジマッピングを行った際に出現するＫ入力論理のことである。表２を見ると明らかなように、両ベンチマークとも大多数の論理が、部分関数間の変換が可能である。
【００５１】
３．実施形態に係るプログラマブル論理回路のアーキテクチャ
以下では、部分関数間の特徴に基づいたアーキテクチャＳＬＭ（Scalability Logic Module）にてなるプログラマブル論理回路について述べる。
【００５２】
上記で得られた特徴より、片方の部分関数の入出力を反転することで、もう片方の部分関数が得られることがわかった。このことは、従来のＬＵＴと比較して半分の構成メモリで表現できることを意味する。ここで提案するＳＬＭは上記で得られた特徴を持つ論理を実装可能であり、かつＬＵＴよりも小面積、少構成メモリ数である。表２に示したように、出現論理の多くは部分関数間の変換ができ、ＳＬＭで実装することが可能である。
【００５３】
図１は本発明の実施形態に係るプログラマブル論理回路の一般例Ｋ−ＳＬＭ（ｍ，ｎ）を示すブロック図である。また、図２は本発明の実施形態に係るプログラマブル論理回路の構成例４−ＳＬＭ（３，２）を示すブロック図である。
【００５４】
本実施形態に係るプログラマブル論理回路であるＳＬＭは、図１に示すように主に、ベース部１と、ＬＵＴを改変した回路である付加ＬＵＴ部２と、ベース部１と付加ＬＵＴ部の出力を選択する出力選択部３とを備えて構成される。ここで、ＳＬＭは同じ入力数であっても、付加ＬＵＴ部２の入力数によって複数の組み合わせが存在する。また、ベース部１の入力数がｍのとき、付加ＬＵＴ部２の入力数ｎの範囲は０≦ｎ≦ｍである。このとき、「Ｋ入力ＳＬＭ」を「Ｋ−ＳＬＭ（ｍ，ｎ）」で表す。ここで、括弧内の最左要素がベース部１の入力数、続いて付加ＬＵＴ部２の入力数を表す。図２はベース部１が３ＬＵＴであり、付加ＬＵＴ部２の入力数が２である４−ＳＬＭ（３，２）である。
【００５５】
図１及び図２において、ベース部１は変換元になる部分関数が実装される。ベース部１は、実際にはＬＵＴもしくは少入力のＳＬＭより構成され、機能を決めるための構成メモリ１０を有する。
【００５６】
具体的には、図１のＫ−ＳＬＭ（ｍ，ｎ）において、ベース部１は、
（１）２ｍビットの構成メモリ１０と、
（２）構成メモリ１０から出力される２ｍビットの構成データを、ｍ個の入力データＩｎ１〜Ｉｎｍに基づいて１個の出力データを選択して出力する、２ｍ−１個のマルチプレクサ１１からなるマルチプレクサ回路１５とを備えて構成される。
【００５７】
また、図２の４−ＳＬＭ（３，２）において、べース部１は、
（１）８（＝２３）ビット構成メモリ１０と、
（２）構成メモリ１０から出力される８ビットの構成データを、３個の入力データＩｎ１〜Ｉｎ３に基づいて１個の出力データを選択して出力する、７個のマルチプレクサ１１からなるマルチプレクサ回路１５とを備えて構成される。
【００５８】
なお、本実施形態において、構成メモリ１０の各メモリに格納されるデータは２値データであって、各入力データ及び各出力データも２値データである。また、本実施形態に係るマルチプレクサ１１，２１，３１，４１，５３は、切り換え信号である入力データに基づいて、入力データが０であれば、第１の入力端子（図面において「０」と図示）を選択して出力する一方、入力データが１であれば、第２の入力端子（図面において「１」と図示）を選択して出力する。
【００５９】
図１及び図２において、付加ＬＵＴ部２は、ベース部１に実装された部分関数に対し、入出力操作を行うことでもう片方の部分関数への変換を行う回路であって、付加ＬＵＴ部２は入力数に応じたＬＵＴ（ベース部１と共用する構成メモリ１０と、複数個のマルチプレクサ２１からなるマルチプレクサ回路２５とからなる）と、入出力のプログラマブルナンドゲート回路２２，２３とを備えて構成される。
【００６０】
図３Ａは実施形態及び実施例に係るプログラマブル論理回路において用いるプログラマブルナンドゲート回路２２，２３，４２，４３の構成を示す回路図である。また、図３Ｂは図３Ａのプログラマブルナンドゲート回路２２，２３，４２，４３の真理値表を示す図である。さらに、図３Ｃは図３Ａのプログラマブルナンドゲート回路２２，２３，４２，４３のブロック図を示す図である。当該プログラマブルナンドゲート回路２２，２３，４２，４３は、
（１）２ビットの構成メモリＭ１，Ｍ２と、
（２）入力データＩｎと、構成メモリＭ１からの入力データと対してナンド演算を行って演算結果の出力データを出力するナンドゲート５１と、
（３）ナンドゲート５１からの出力データを反転して出力するインバータ５２と、
（４）構成メモリＭ２からの出力データに基づいて、ナンドゲート５１からの出力データと、インバータ５２からの出力データとのうちの１つの出力データを選択して出力データＯｕｔとして出力するマルチプレクサ５３とを備えて構成される。
【００６１】
当該プログラマブルナンドゲート回路２２，２３，４２，４３は、２ビットの構成メモリＭ１，Ｍ２を用いて入力データを正転し又は反転し、もしくは０又は１の定数として出力し（本実施形態において、以下、「プログラマブルナンド演算」という。）、これにより上述の部分関数間の変換を行う。
【００６２】
次いで、付加ＬＵＴ部２の具体例を図１及び図２を参照して以下に説明する。
【００６３】
図１のＫ−ＳＬＭ（ｍ，ｎ）において、付加ＬＵＴ部２は、
（１）入力データＩｎ１〜Ｉｎｍに対して、それぞれプログラマブルナンド演算を行って演算結果の出力データをマルチプレクサ回路２５内の各対応するマルチプレクサ２１に出力する、ｎ個の入力プログラマブルナンドゲート回路２２と、
（２）構成メモリ１０から出力される２ｍビットの構成データを、ｎ個のプログラマブルナンドゲート回路２２からのｍ個のデータに基づいて１個の出力データを選択して出力する、２ｎ−１個のマルチプレクサ２１からなるマルチプレクサ回路２５と、
（３）マルチプレクサ回路２５から出力される出力データに対してプログラマブルナンド演算を行って、演算結果の出力データを出力する出力プログラマブルナンドゲート回路２３とを備えて構成される。
【００６４】
また、図２の４−ＳＬＭ（３，２）において、付加ＬＵＴ部２は、
（１）入力データＩｎ１〜Ｉｎ２に対して、それぞれプログラマブルナンド演算を行って演算結果の出力データをマルチプレクサ回路２５内の各対応するマルチプレクサ２１に出力する、２個の入力プログラマブルナンドゲート回路２２と、
（２）構成メモリ１０から出力される８ビットの構成データを、２個のプログラマブルナンドゲート回路２２からの２個のデータに基づいて１個の出力データを選択して出力する、３個のマルチプレクサ２１からなるマルチプレクサ回路２５と、
（３）マルチプレクサ回路２５から出力される出力データに対してプログラマブルナンド演算を行って、演算結果の出力データを出力する出力プログラマブルナンドゲート回路２３とを備えて構成される。
【００６５】
以上のように構成された付加ＬＵＴ部２によれば、当該付加ＬＵＴ部２の内部に設けられたＬＵＴはベース部１内のＬＵＴがもつ構成メモリ１０を共有するため、ＳＬＭ全体では構成メモリ数を半分にできる。付加ＬＵＴ部２の入力数ｎは部分関数間の変換の際、操作可能な入力数を表す。このため、付加ＬＵＴ部２の入力数が大きくなるに従ってＳＬＭの論理表現能力は高くなるが、面積は増加する。また、付加ＬＵＴ部２の入力が０の場合、ベース部１からの出力データの反転もしくは定数の代入のみを行う。
【００６６】
図４Ａは実施形態に係るプログラマブル論理回路（３−ＳＬＭ）において用いる０入力付加ＬＵＴ部（０−ＬＵＴ＋ＰＮ）２の構成を示すブロック図である。また、図４Ｂは実施形態に係るプログラマブル論理回路（３−ＳＬＭ）において用いる１入力付加ＬＵＴ部（１−ＬＵＴ＋ＰＮ）２の構成を示すブロック図である。図４Ａ及び図４Ｂでは、ベース部１を２−ＬＵＴとしている。図４Ａにおいて、０入力の場合は、ベース部１からの出力データに対し、正転又は反転並びに定数代入を行う。図４Ｂにおいて、１入力の場合は、ベース部１からの出力データから１つ前の段の部分関数を共有し、変換を行う。
【００６７】
次いで、出力選択部３について以下に説明する。図１及び図２において、出力選択部３は、
（１）構成メモリ３０と、
（２）入力データＩｎ０を構成メモリ３０からの構成データに基づいて正転し又は反転するプログラマブルインバータ３２と、
（３）インバータ３２からの切り換え信号であるデータに基づいて、ベース部１からの出力データと、付加ＬＵＴ部２からの出力データとのうち１つの出力データを選択して出力データＯｕｔとして出力するマルチプレクサ３１とを備えて構成される。
【００６８】
部分関数間で変換可能な論理の中には、部分関数ｆ（ｘ＝０）を部分関数ｆ（ｘ＝１）に変換可能なケースと、その逆のケースがある。出力選択部３のプログラマブルインバータ３２はそれら２つのケースに対応するためのものである。
【００６９】
ＳＬＭをベース部１とするＬＵＴは少入力であるほど小面積となる反面、論理の柔軟性は低くなる。Ｋ−ＳＬＭ（ｍ，ｎ）に対し、ｍ＝Ｋ−１となる場合が最も大きな入力のＬＵＴをベースとして使用することを意味する。一方、ｍ＜Ｋ−１の場合、付加ＬＵＴ部２をＫ−ｍ回追加する必要がある。ただし、この際、追加される付加ＬＵＴ部２の入力は０入力もしくは１入力となる（図４Ａ及び図４Ｂ参照）。
【００７０】
図５は本発明の変形例に係るプログラマブル論理回路（５−ＳＬＭ（３，２，１））の構成を示すブロック図である。当該５−ＳＬＭ（３，２，１）は、５入力のＳＬＭに対し、３−ＬＵＴをベース部１に構成した例である。ここでは、３入力のベース部１と、２入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成された４−ＳＬＭ（３，２）である拡張ベース部５に対し、部分論理関数の一部を表す１入力の拡張付加ＬＵＴ部４を追加することで５入力のＳＬＭを実現している。
【００７１】
ここで、拡張付加ＬＵＴ部４は、１個のマルチプレクサ４１からなるマルチプレクサ回路４５と、入力プログラマブルナンドゲート回路４２と、出力プログラマブルナンドゲート回路４３とを備えて構成される。また、拡張付加ＬＵＴ部４のマルチプレクサ４１の各入力端子はそれぞれ、拡張ベース部５内のベース部１の最終３段目のマルチプレクサ１１の出力端子、並びに付加ＬＵＴ部２の出力プログラマブルナンドゲート回路２３の出力端子に接続されている。当該５−ＳＬＭ（３，２，１）の全体の出力選択部３は、拡張ベース部５からの出力データと、拡張付加ＬＵＴ部４からの出力データとのうち１つの出力データを、入力データＩｎ０に基づいて生成された切り換えデータに基づいて選択して出力する。追加した拡張付加ＬＵＴ部４の入力数は、ＳＬＭの表記において、括弧内の最右要素に追加する。従って、この際のプログラマブル論理回路を５−ＳＬＭ（３，２，１）で表す。
【００７２】
４．実施例に係る各種のプログラマブル論理回路（ＳＬＭ）
次いで、本発明の各実施例に係るプログラマブル論理回路（ＳＬＭ）について以下に説明する。
【実施例１】
【００７３】
図６は本発明の実施例１に係るプログラマブル論理回路（５−ＳＬＭ（４，４））の構成を示すブロック図である。図６において、５−ＳＬＭ（４，４）は、４入力のベース部１と、４入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成される。ここで、付加ＬＵＴ部２の初段目の８個のマルチプレクサ２１の各入力端子はそれぞれ構成メモリ１０の各出力端子に接続されている。
【実施例２】
【００７４】
図７は本発明の実施例２に係るプログラマブル論理回路（５−ＳＬＭ（４，３））の構成を示すブロック図である。図７において、５−ＳＬＭ（４，３）は、４入力のベース部１と、３入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成される。ここで、付加ＬＵＴ部２の初段目の４個のマルチプレクサ２１の各入力端子はそれぞれベース部１の初段目の各マルチプレクサ１１の各出力端子に接続されている。
【実施例３】
【００７５】
図８は本発明の実施例３に係るプログラマブル論理回路（５−ＳＬＭ（４，２））の構成を示すブロック図である。図８において、５−ＳＬＭ（４，２）は、４入力のベース部１と、２入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成される。ここで、付加ＬＵＴ部２の初段目の２個のマルチプレクサ２１の各入力端子はそれぞれベース部１の２段目の各マルチプレクサ１１の各出力端子に接続されている。
【実施例４】
【００７６】
図９は本発明の実施例４に係るプログラマブル論理回路（５−ＳＬＭ（４，１））の構成を示すブロック図である。図９において、５−ＳＬＭ（４，１）は、４入力のベース部１と、１入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成される。ここで、付加ＬＵＴ部２のマルチプレクサ２１の各入力端子はそれぞれベース部１の３段目の各マルチプレクサ１１の各出力端子に接続されている。
【実施例５】
【００７７】
図１０は本発明の実施例５に係るプログラマブル論理回路（５−ＳＬＭ（４，０））の構成を示すブロック図である。図１０において、５−ＳＬＭ（４，０）は、４入力のベース部１と、プログラマブルナンドゲート回路２３のみからなる０入力の付加ＬＵＴ部２と、出力選択部３とを備えて構成される。ここで、付加ＬＵＴ部２のプログラマブルナンドゲート回路２３の入力端子はベース部１の最終４段目のマルチプレクサ１１の各出力端子に接続されている。
【実施例６】
【００７８】
図１１は本発明の実施例６に係るプログラマブル論理回路（６−ＳＬＭ（４，２，１））の構成を示すブロック図である。図１１において、６−ＳＬＭ（４，２，１）は、
（１）４入力のベース部１と、２入力の付加ＬＵＴ部２と、出力選択部３とを備えた拡張ベース部５と、
（２）１入力の拡張付加ＬＵＴ部４と、
（３）当該プログラマブル論理回路全体の出力選択部３とを備えて構成される。
ここで、拡張付加ＬＵＴ部４のマルチプレクサ４１の各入力端子はそれぞれベース部１の最終段目のマルチプレクサ１１の出力端子、並びに、付加ＬＵＴ部２の出力プログラマブルナンドゲート回路２３の出力端子に接続されている。
【実施例７】
【００７９】
図１２は本発明の実施例６に係るプログラマブル論理回路（６−ＳＬＭ（４，２，０））の構成を示すブロック図である。図１２において、６−ＳＬＭ（４，２，０）は、
（１）４入力のベース部１と、２入力の付加ＬＵＴ部２と、出力選択部３とを備えた拡張ベース部５と、
（２）０入力の拡張付加ＬＵＴ部４と、
（３）当該プログラマブル論理回路全体の出力選択部３とを備えて構成される。
ここで、拡張付加ＬＵＴ部４のプログラマブルナンドゲート回路４３の入力端子は拡張ベース部５の出力端子に接続されている。
【００８０】
５．ＳＬＭ向け実装ツールの開発
回路実装を行うためのクラスタリング、配置、配線ツールについては既存のＬＵＴ向けのツールが使用可能である。しかしながら、ＳＬＭはＬＵＴとは実装可能な論理が異なるため、ＬＵＴ向けのマッピングツールをそのまま利用することはできない。そこで、本発明者らはＳＬＭ向けのマッピングツールを開発した。このマッピングツールはプライオリティカットベースのマッピングツール（例えば、非特許文献６参照）をベースとしており、ＳＬＭで実装可能な論理のみが生成されるように制約を加えてある。マッピング時に実装できない論理が出現した場合は通常のＬＵＴと同様に入力数を分解することで実装を行う。その際、Ｋ−ＳＬＭ（ｍ，ｎ）はｍ−ＬＵＴを有しているため、ｍ入力以下の任意の論理を実装可能である。
【００８１】
６．評価
本評価では、実装面積、クリティカルパス遅延及び総使用構成メモリ数の観点から、ＳＬＭとＬＵＴとの比較を行う。評価対象のＳＬＭアーキテクチャの入力数Ｋの範囲は５≦Ｋ≦８である。また、ベース部１となるＬＵＴの入力数ｍの範囲は４≦ｍ≦７、付加ＬＵＴ部２の入力数ｎの範囲は０≦ｎ≦２とする。さらに、ＳＬＭが含む付加ＬＵＴ部２の数は最大２つまでとする。また、本評価では多くのＦＰＧＡで採用されているクラスタサイズが４のアーキテクチャを想定する。
【００８２】
図１３は本発明に係る実施形態及び実施例に対する評価で使用するクラスタアーキテクチャの構成を示すブロック図である。図１３において、当該クラスタアーキテクチャは、入力データ、出力データ及び接地信号データのうちの１つを選択する４個の入力選択マルチプレクサ６１と、各入力選択マルチプレクサ６１にそれぞれ接続されたクラスタである基礎論理素子（以下、ＢＬＥ（Basic Logic Element）という。）６２とを備えて構成される。各ＢＬＥ６２は、Ｋ入力論理セルであるＳＬＭ７１と、遅延型フリップフロップ７２と、ＳＬＭ７１からの出力データと遅延型フリップフロップ７２からの出力データとのうちの１つを選択する出力選択マルチプレクサ７３とを備えて構成される。
【００８３】
また、クラスタ入力数Ｉは次式により決定される。
【００８４】
【数４】
0005937550.tif 000007
【００８５】
ここで、Ｋは論理セルの入力数であり、Ｎはクラスタサイズである。また、ＳＬＭは論理実装に定数割り当てを必要とするため、入力選択マルチプレクサ６１で接地信号も選択可能な構成を有する。
【００８６】
図１４は本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する評価の手順を示すフローチャートである。この評価フローではベンチマーク回路として上記と同じくＭＣＮＣとＶＰＲベンチマークセットを使用する。図１４において、ベンチマーク回路に対してテクノロジマッピング（Ｓ１）を行ってマッピング結果を得る。ここで、テクノロジマッピング（Ｓ１）ツールは上述したプライオリティカットベースのマッピングツールを用いる。さらに、マッピング結果に対してクラスタリング、配置、及び配線（Ｓ２）の処理を行ってチャネル幅、アレイサイズ及びクリティカルパス遅延を計算する。ここで、当該処理では、公知のＶＰＲ６．０を使用する。一方、本評価ではＶＰＲに必要な物理パラメータを得るために、ＣＭＯＳ６５ｎｍライブラリを用いてシノプシス・デザイン・コンパイラー（Synopsys Design Compiler）Y-2006.06-SP6-2（Ｓ３）にてＳＬＭとＬＵＴの面積、遅延を算出した。
【００８７】
表３に、各ＳＬＭの論理合成により得られたＢＬＥ面積及び遅延と、必要な構成メモリ数を示す。
【００８８】
【表３】
0005937550.tif 000008
また、本評価ではメモリ面積にはラッチを用いる。評価を行う実装面積は論理面積と配線面積を加算することで算出する。
論理面積はクラスタの面積とＶＰＲより得られたアレイサイズとの積で算出し、配線面積はＶＰＲより得られたアレイサイズとチャネル幅から算出する。ただし、全ての配線は単方向配線であり、長さ１のセグメントのみから構成される場合を想定する。
【００８９】
図１５は本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する実装面積の評価結果を示すグラフである。図１５のグラフの結果は全てのベンチマーク回路の実装結果を４−ＬＵＴの結果で正規化し、それらを平均化したものである。図１５から明らかなように、ＳＬＭは同じ入力数のＬＵＴよりも少ない面積で回路を実装できている。ＬＵＴは入力数が多いものほど、実装面積も上がる傾向にある。一方、ＳＬＭは高い入力数においても、入力数の少ないＬＵＴと同等の面積で回路実装が可能である。
６−ＬＵＴの実装面積は４−ＬＵＴの１．０９倍であるのに対して、７−ＳＬＭ（５，２，１）は４−ＬＵＴの１．０６倍である。
【００９０】
図１６は本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対するクリティカルパス遅延の評価結果を示すグラフである。図１６から明らかなように、ＳＬＭのクリティカルパス遅延は同入力数のＬＵＴより悪化する傾向にある。８−ＳＬＭ（６，１，１）のクリティカルパス遅延は８−ＬＵＴと比較して、５％の遅延悪化が見られる。悪化の原因として、テクノロジマッピング時に実装できずに分解された論理がクリティカルパスの段数を増加させていることが考えられる。
【００９１】
図１７は本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する面積遅延積の評価結果を示すグラフである。図１７から明らかなように、ＬＵＴの中で最も結果が良いのは６−ＬＵＴであり、その面積遅延積は４−ＬＵＴの０．８８倍である。これに対してＳＬＭの中で最も結果が良いのは、７−ＳＬＭ（５，２，１）であり、その面積遅延積は４−ＬＵＴの０．８１倍である。この結果から、ＳＬＭがＬＵＴよりも高い性能を持つということが分かる。
【００９２】
図１８は本発明に係る実施形態及び実施例に係る各プログラマブル論理回路に対する構成メモリ数の評価結果を示すグラフである。ここで、総使用構成メモリ数はアレイサイズと論理ブロックと配線領域の総使用構成メモリ数の積で表される。図１８から明らかなように、ＳＬＭは全ての入力数において、同入力数のＬＵＴより使用メモリ数が少ないことが分かる。７−ＳＬＭ（５，１，１）の構成メモリ数は７−ＬＵＴと比較して３１％、８−ＳＬＭ（６，２，１）の構成メモリ数は８−ＬＵＴと比較して４２％のメモリ数を削減した。
【００９３】
次いで、実装回路に出現する論理のうち論理セルが実装可能なものの割合である論理カバー率の評価について以下に説明する。
【００９４】
図１９は本発明に係る実施例に係るプログラマブル論理回路（８−ＳＬＭ）の各構成例に対する８入力論理カバー率の評価結果を示すグラフである。また、図２０は本発明に係る実施例に係るプログラマブル論理回路（７−ＳＬＭ）の各構成例に対する７入力論理カバー率の評価結果を示すグラフである。さらに、図２１は本発明に係る実施例に係るプログラマブル論理回路（６−ＳＬＭ）の各構成例に対する６入力論理カバー率の評価結果を示すグラフである。またさらに、図２２は本発明に係る実施例に係るプログラマブル論理回路（５−ＳＬＭ）の各構成例に対する５入力論理カバー率の評価結果を示すグラフである。
【００９５】
図１９〜図２２はＭＣＮＣベンチマーク回路２０種、ＶＰＲベンチマーク回路１３種をＬＵＴでテクノロジマッピングした際に使用された論理関数のうち、本実施形態に係るプログラマブル論理回路で実装可能なものの割合を示している。例として、図１９では８−ＬＵＴでテクノロジマッピングした際に使用された８入力論理のうち、本実施形態に係るプログラマブル論理回路で実装可能なものの割合を示している。それぞれの入力数に共通する特徴として、入力数１の付加ＬＵＴ部２が含まれているプログラマブル論理回路ではカバー率が急激に下がっているが、それ以外では大きな差が見られない。従って、入力数０および１の付加ＬＵＴ部２付近では小面積と高カバー率を両立しており、これらのプログラマブル論理回路は高い実装効率が期待できる。
【００９６】
以上説明したように、図１５より、ＬＵＴは入力数を増やした際の配線面積の減少よりも、論理面積の増大の方がはるかに大きい。８−ＬＵＴは７−ＬＵＴよりも配線面積が１１％減少しているが、論理面積は４２％増加している。これに対し７−ＬＵＴと８−ＳＬＭ（７，２）を比較した場合、配線面積の削減率は３％であるが、論理面積の増加を６％にまで抑えている。このことからＳＬＭの持つ論理の表現能力は、面積削減に対して有効であることが分かる。さらに、ＳＬＭ同士で比較すると、０入力の付加ＬＵＴ部２を含むアーキテクチャは性能が低い。このことから、０入力の付加ＬＵＴ部２は小面積ではあるが、性能が改善できるほどの論理表現能力を持っていないということが分かる。
【００９７】
以上説明したように、本実施形態では、ＦＰＧＡの小面積化を目的として、シャノン展開された部分関数間の特徴を元にＳＬＭアーキテクチャを提案した。ＳＬＭは同入力数のＬＵＴと比較して半分以下の構成メモリ数で実装可能である。評価結果より、７−入力ＳＬＭにおいて、７−ＬＵＴと比較して平均で１８％の実装面積削減を実現した。同様に、８−ＳＬＭは８−ＬＵＴと比較して２８％の実装面積を削減することができた。また、面積遅延積においても、７−ＳＬＭは４入力から８入力までのＬＵＴより良い結果となった。
【００９８】
従って、本発明の実施形態によれば、従来技術に比較して、必要なメモリ数を大幅に削減でき、従来技術に係るＬＵＴと同程度の機能を保持しつつ小さい面積で実現し、消費電力を小さくすることができるプログラマブル論理回路とその構成方法を提供することができる。また、拡張付加ＬＵＴ部４を備えることにより、上記プログラマブル論理回路の入力数を拡張できる。
【００９９】
７．関連する特許文献との相違点
【０１００】
７−１．特許文献６との相違点
特許文献６では、少数のナンドゲート及びプログラマブルインバータのみによる構造で論理セルの小面積化を実現しており、ＭＣＮＣベンチマークにおいて出現率の高い論理を実装可能である。特許文献６では、ナンドゲートとプログラマブルインバータのみを利用して論理セルを構成している。一方、本発明に係る実施形態では、ＬＵＴベースで論理セルを構成している。
【０１０１】
７−２．特許文献７との相違点
特許文献７では、一部の論理回路のみを実装可能な構造にすることで、少メモリ数、小面積な論理セルを実現しており、入力の入れ替えによって得られる回路を同一とみなし、ＬＵＴの論理表現における冗長性を削減している。
一方、本発明の実施形態では、シャノン展開、ナンドゲート、インバータを用いて部分論理関数の真理値表の変換を行なっており、少ない追加リソースによって論理セルの入力数を拡張可能である。
【産業上の利用可能性】
【０１０２】
以上詳述したように、本発明によれば、従来技術に比較して、必要なメモリ数を大幅に削減でき、従来技術に係るＬＵＴと同程度の機能を保持しつつ小さい面積で実現し、消費電力を小さくすることができるプログラマブル論理回路とその構成方法を提供することができる。
【符号の説明】
【０１０３】
１…ベース部、
２…付加ＬＵＴ部、
３…出力選択部、
４…拡張付加ＬＵＴ部、
５…拡張ベース部、
１０…構成メモリ、
１１，２１，３１，４１…マルチプレクサ、
１５，２５，４５…マルチプレクサ回路、
２２，２３，４２，４３…プログラマブルナンドゲート回路、
３０…メモリ、
３２…プログラマブルインバータ、
５１…ナンドゲート、
５２…インバータ、
５３…マルチプレクサ、
６１…入力選択マルチプレクサ、
６２…基礎論理素子（ＢＳＥ）、
７１…スケーラビリティ論理モジュール（ＳＬＭ）、
７２…遅延型フリップフロップ、
７３…出力選択マルチプレクサ、
Ｍ１，Ｍ２…構成メモリ。
【図１】
0005937550.tif 000009
【図２】
0005937550.tif 000010
【図３Ａ】
0005937550.tif 000011
【図３Ｂ】
0005937550.tif 000012
【図３Ｃ】
0005937550.tif 000013
【図４Ａ】
0005937550.tif 000014
【図４Ｂ】
0005937550.tif 000015
【図５】
0005937550.tif 000016
【図６】
0005937550.tif 000017
【図７】
0005937550.tif 000018
【図８】
0005937550.tif 000019
【図９】
0005937550.tif 000020
【図１０】
0005937550.tif 000021
【図１１】
0005937550.tif 000022
【図１２】
0005937550.tif 000023
【図１３】
0005937550.tif 000024
【図１４】
0005937550.tif 000025
【図１５】
0005937550.tif 000026
【図１６】
0005937550.tif 000027
【図１７】
0005937550.tif 000028
【図１８】
0005937550.tif 000029
【図１９】
0005937550.tif 000030
【図２０】
0005937550.tif 000031
【図２１】
0005937550.tif 000032
【図２２】
0005937550.tif 000033