Top > Search of Japanese Patents > (In Japanese)プログラマブル論理デバイス

(In Japanese)プログラマブル論理デバイス

Patent code P140011055
File No. 2013-P11
Posted date Oct 30, 2014
Application number P2005-504294
Patent number P4246200
Date of filing Mar 31, 2004
Date of registration Jan 16, 2009
International application number JP2004004752
International publication number WO2004088500
Date of international filing Mar 31, 2004
Date of international publication Oct 14, 2004
Priority data
  • P2003-093922 (Mar 31, 2003) JP
  • P2003-105762 (Apr 9, 2003) JP
Inventor
  • (In Japanese)笹尾 勤
  • (In Japanese)井口 幸洋
Applicant
  • (In Japanese)学校法人明治大学
Title (In Japanese)プログラマブル論理デバイス
Abstract (In Japanese)目的論理関数に応じ、論理関数メモリ間の入力線数、レイル数を変化させ、メモリ容量を必要最小限に抑えて最適化設計できるプログラマブル論理デバイスである。論理関数メモリ(4)を直列に順序配列し、LUTを記憶させる。外部入力線から、各論理関数メモリ(4)への入力変数を入力する。二つの論理関数メモリ(4)間において、接続メモリ(6)が記憶する接続情報に従って、接続回路(5)が前段の論理関数メモリ(4)の出力線又は外部入力線と後段の論理関数メモリ(4)の入力線との接続を行う。目的論理関数に合わせて、接続情報を書き換えれば、接続回路を再構成し、入力線数、レイル数を変化させることができる。レイル数と入力線数の比を論理関数に合わせて最適化し、メモリ容量を必要最小限に抑えることが可能となる。
Outline of related art and contending technology (In Japanese)

近年、論理回路の設計においては、フィールド・プログラマブル・ゲートアレイ(Field Programmable Gate Array。以下、「FPGA」という。)が広く用いられるようになっている(引用文献[1])。FPGAは、マトリックス状に配列された複数の論理セル(Configurable Logic Block;以下、「CLB」という。)の内容と論理セル間の配線の接続とをメモリの書き換えによって変更することが可能なプログラマブル論理デバイスである。FPGAは、プログラムに従ってソフトウェア的に演算を行うマイクロ・プロセッサ(Micro Processing Unit;以下、「MPU」という。)とは異なり、ハードウェア的に演算を行う。従って、論理関数の演算実行速度が速いという特徴を有する。

一方、FPGAは、各CLB間の物理的な配線の引き回しをプログラムにより変更する。そのため、配線遅延をできる限り小さくするように考慮した配置配線設計が必要とされ、設計に長時間を要する。また、各CLB間の配線の引き回し方に依存して、配線遅延時間が変化する。そのため、設計時において論理回路の演算時間の予測が困難である。

また、2次元的に配列されたCLB間の配線を、再構成可能なように自在に接続切り替えを行うことから、チップ内における配線領域の割合が非常に大きくなる。また、接続部にパス・トランジスタを使用する、ため配線部分の遅延が非常に大きい。

そこで、上記FPGAの欠点をカバーするプログラム可能な論理回路として、LUTカスケード(LUT cascade)が提案されている(引用文献[2],[3]参照)。LUTカスケードとは、LUTを直列接続したものであり、演算処理を行う論理関数(目的論理関数)を関数分解して得られる複数の分解関数のLUTを直列接続した形で表現できる。FPGAは、論理回路をそのまま2次元的なCLBのネットワークとして実現するのに対し、LUTカスケードは、目的論理関数を1次元的に直列接続したLUTで実現する点において異なる。

つまり、FPGAで用いられる各CLBは、基本的な論理ゲートを実現するものである。そして、これらの基本論理ゲートを配線により結合することで、複雑な論理回路を実現することに基本的な設計思想がある。従って、必然的に、FPGAをチップ上にレイアウトする場合、2次元的に配置されたCLB間を自在に配線接続するための配線ネットワークを構成する必要がある。そのため、論理領域のほかに広い配線領域が必要となり、レイアウト面積が大きくなりがちである。

それに対し、LUTカスケードにおいては、一般に、多入力多出力の複雑な論理関数を表現するLUTを、直列的(1次元的)に接続して、複雑な論理回路を実現することに基本的な設計思想がある。そのため、各LUTの出力と入力は、一般に複数の配線により接続される。そして、2次元的な配線ネットワークは不要であるため、一般に配線領域は少なく、チップ面積の殆どがLUTを格納するためのメモリ領域となる。

また、配線のための、チップ面積や、配線部分の遅延時間もFPGAに比べて少ない。

以下、LUTカスケードの一設計法について簡単に説明する。第52図はLUTカスケードの原理を表す図である。なお、ここでは簡単のため、中間出力のないLUTカスケードについて説明を行う。

LUTカスケードにおいて論理関数の演算を行う場合、まず、演算を行う論理関数(目的論理関数)f(X)をs個(s≧2)の分解関数{fi(Xi);i=0,…,s-1}に関数分解する。ここで、X=(x0,…,xn-1)は入力変数を表す。また、入力変数の集合を{X}で表す。ここで、{X}={X0}∪…∪{Xs-1},{Xi}∩{Xj}=φ(i≠j;i,j∈{0,…,s-1})である。各分解関数fiの出力変数(一般に、ベクトル)をYi+1で表す。以下、X,Yの変数の個数を|X|,|Y|のように表すこととし、特に、|X|=n,|Xi|=ni,|Yi|=uiと表記する。

任意の目的論理関数fは、n0=k(kは分解関数f0の入力変数の数)、ni=k-ui(0<i<s-1),ns-1=k-us-1-t(0≦t≦k-2)となるように関数分解することが可能である(引用文献[2],[3]参照)。そこで、目的論理関数fをs-1個のk入力の分解関数fj(j∈{0,…,s-2})と1個のk-t入力の分解関数fs-1とに分解する。そして、各分解関数fr(r∈{0,…,s-1})を分解表により表し、これをLUT(look up table)とする。ここで、目的論理関数fr(Xr)の分解表(decomposition chart)とは、2|Xr|列2|fr|行の表で、各行、各列に2進符号のラベルをもち、その要素がfrの対応する真理値であるような表をいう。

第52図において、s個のLUT(LUT0~LUTs-1)は、それぞれ、分解関数{fi;i=0,…,s-1}を表現したものである。それぞれのLUT(LUTr)は、k入力ur+1出力のメモリ(以下、「論理関数メモリ」という。)を用いて実現することができる。このような論理関数メモリを、第52図に示すようにカスケード接続することにより、LUTカスケードが実現される。

LUTカスケードでは、目的論理関数fの入出力変数の個数が大きい場合には、多数のLUTをカスケード接続する必要がある。そのため、最適化されたFPGAに比べれば演算速度は遅くなる場合もある。しかし、LUTカスケードでは、各分解関数の演算は、論理関数メモリを用いて高速に行われる。そのため、MPU上で動くプログラムに比べると演算速度を高速化することができる。

そして、LUTの段数によって、一義的に演算速度が定まる。そのため、論理回路の設計時に目的論理関数の演算時間を正確に予測することが容易である。また、LUTカスケードでは、互いに隣接する論理関数メモリ間でのみ配線を行えばよい。そのため、論理回路の設計時には配線遅延等の影響を考慮する必要がない。従って、LUTカスケードはFPGAに比べると論理回路設計が格別に容易になる。

しかしながら、実際に第52図に示したようなLUTカスケードにより目的論理関数の演算を行う場合には、目的論理関数を関数分解して得られる分解関数のLUT間のレイル数(二つのLUT間の線数(中間変数の数))や各LUTの入力変数の個数が目的論理関数により異なる。そのため、種々の目的論理関数を論理回路で実現しようとした場合、入力変数の個数及びレイル数が異なる種々のLUTカスケードの論理回路が必要となり、実用性に欠ける。

そこで、多様な目的論理関数に対応可能なプログラマブル論理デバイスとするためには、各論理関数メモリの入力のビット数に余裕をもたせるべく、あらかじめビット数を十分大きくとっておくことが考えられる。しかし、論理関数メモリのメモリ容量は、論理関数メモリの入力が1増加するごとに2倍に増大する。従って、入力のビット数に余裕をもたせる場合、使用されないメモリ領域が増大しメモリ領域の無駄が多くなる。また、メモリ容量の増大に伴いメモリのレイアウト面積が増大する。そのため、回路の高集積化が困難となり、回路消費電力も大きくなる。

そこで、本発明の目的は、目的論理関数に応じて、各論理関数メモリ間の入力変数の入力線数とレイル数とを柔軟に変化させることが可能で、論理関数メモリの入力数、延いては論理関数メモリのメモリ容量を必要最小限に抑えて設計することが可能なプログラマブル論理デバイスを提供することにある。

〔引用文献〕

[1] 米国再発行特許Re.34,363号明細書

[2] 笹尾勤,松浦宗寛,井口幸洋,“多出力関数のカスケード実現と再構成可能ハードウェアによる実現”,電子情報通信学会FTS研究会,FTS2001-8,pp.57-64,三重大学(2001-04).

[3] T.Sasao,M.Matsuura,and Y.Iguchi,″A cascade realization of multiple-output function for reconfigurable hardware,″International Workshop on Logic and Synthesis(IWLS01),Lake Tahoe,CA,June 12-15,2001.pp.225-230.

Field of industrial application (In Japanese)

本発明は、プログラム可能な論理デバイス(programmable logic device)に係り、特に、目的論理関数を、順序づけられた複数の分解関数に関数分解し、それら分解関数を分解表として表現したルックアップ・テーブル・カスケード(look up table cascade;以下「LUTカスケード」という。)の演算を行うためのプログラマブル論理デバイスに関する。

Scope of claims (In Japanese)
【請求項1】
 
以下の構成を含むプログラマブル論理デバイス(programmable logic device):
論理関数のLUT(look up table)を記憶するための、直列に順序づけて配列された論理関数メモリ;
前記各論理関数メモリに対する入力変数が入力される複数の外部入力線;
二つの前記論理関数メモリ間において、前段の前記論理関数メモリの出力線又は前記外部入力線のうち後段の前記論理関数メモリの各入力線に接続されるものを選択するための接続情報を記憶する接続メモリ;
二つの前記論理関数メモリ間において、前記接続メモリの出力に従って、前段の前記論理関数メモリの出力線又は前記外部入力線と後段の前記論理関数メモリの入力線との接続関係の再構成を行うことが可能な接続回路。

【請求項2】
 
以下の構成を含むプログラマブル論理デバイス:
論理関数のLUTを記憶するための、リング状に配列された論理関数メモリ;
前記各論理関数メモリに対する入力変数が入力される複数の外部入力線;
二つの前記論理関数メモリ間において、前段の前記論理関数メモリの出力線又は前記外部入力線のうち後段の前記論理関数メモリの各入力線に接続されるものを選択するための接続情報を記憶する接続メモリ;
二つの前記論理関数メモリ間において、前記接続メモリの出力に従って、前段の前記論理関数メモリの出力線又は前記外部入力線と後段の前記論理関数メモリの入力線との接続関係の再構成を行うことが可能な接続回路。

【請求項3】
 
論理関数の演算結果を外部回路に出力するための外部出力線を備え;
前記接続メモリは、二つの前記論理関数メモリ間において、前段の前記論理関数メモリの出力線のうち前記外部出力線に接続されるものを選択するための接続情報をも記憶するものであり;
前記接続回路は、二つの前記論理関数メモリ間において、前記接続メモリの出力に従って、前段の前記論理関数メモリの出力線と前記外部出力線との接続をも行うものである;
ことを特徴とする請求の範囲第1項又は第2項記載のプログラマブル論理デバイス。

【請求項4】
 
論理関数メモリのメモリ領域を指定する領域指定変数を記憶する領域指定記憶手段を備え;
前記接続回路は、二つの前記論理関数メモリ間において、領域指定記憶手段の出力に従って、
前段の前記論理関数メモリの出力及び外部入力線からの入力変数が、領域指定変数により特定される後段の前記論理関数メモリのメモリ領域に入力されるように、
又は、領域指定変数により特定される前段の前記論理関数メモリのメモリ領域からの出力及び外部入力線からの入力変数が、後段の前記論理関数メモリに入力されるように、
前段の前記論理関数メモリの出力線、外部入力線、及び領域指定記憶手段の出力線と、後段の前記論理関数メモリの入力線との接続を行うものである;
ことを特徴とする請求の範囲第1項乃至第3項の何れか一記載のプログラマブル論理デバイス。

【請求項5】
 
前記論理関数メモリの入力側又は出力側に設けられ、外部から入力されるデータ・ストローブ信号に従って、前記論理関数メモリへの入力又は前記論理関数メモリの出力を取り込んで一時的に保持する中間変数レジスタ;
を備えていることを特徴とする請求の範囲第1項乃至第4項の何れか一記載のプログラマブル論理デバイス。

【請求項6】
 
前記中間変数レジスタと並列に接続されたバイパス線;
及び、前記中間変数レジスタの出力側に設けられ、前記中間変数レジスタの出力線又は前記バイパス線の何れか一方を選択し、選択された線の信号を出力するバイパス選択回路;
を備えていることを特徴とする請求の範囲第1項乃至第5項の何れか一記載のプログラマブル論理デバイス。

【請求項7】
 
前記データ・ストローブ信号を計数し、演算を実行する前記論理関数メモリの番号を特定する論理関数メモリ特定手段;
を備えていることを特徴とする請求の範囲第5項又は第6項記載のプログラマブル論理デバイス。

【請求項8】
 
演算処理を実行させる前記論理関数メモリを通常動作状態とし、それ以外の前記論理関数メモリを低消費電力状態とする制御を行う電源制御手段;
を備えている請求の範囲第5項乃至第7項の何れか一記載のプログラマブル論理デバイス。

【請求項9】
 
前記各論理関数メモリの一部の入力線は、前記接続回路を介すことなく前記外部入力線に直接接続されていることを特徴とする請求の範囲第1項乃至第8項の何れか一記載のプログラマブル論理デバイス。

【請求項10】
 
前記各論理関数メモリの一部の出力線は、前記接続回路を介すことなくその後段の論理関数メモリの一部の入力線に直接接続されていることを特徴とする請求の範囲第1項乃至第9項の何れか一に記載のプログラマブル論理デバイス。

【請求項11】
 
前記接続回路は、複数のセレクタ回路を含み;
前記各セレクタ回路は、前記接続メモリの出力値に従って、前段の前記論理関数メモリの出力線と前記外部入力線とのうち何れか一つ、又は、前段の前記論理関数メモリの出力線と前記外部入力線と領域指定記憶手段の出力線とのうち何れか一つを選択して後段の前記論理関数メモリの入力線に接続するものであること;
を特徴とする請求の範囲第1項乃至第10項の何れか一記載のプログラマブル論理デバイス。

【請求項12】
 
前記接続回路は、前記接続メモリの出力値に従って、前段の前記論理関数メモリの出力線の接続順序をシフトして後段の前記論理関数メモリの入力線に接続するシフタ回路を含むことを特徴とする請求の範囲第1項乃至第11項の何れか一記載のプログラマブル論理デバイス。

【請求項13】
 
前記接続回路は、複数のマルチプレクサを含み;
前記マルチプレクサは、前記接続メモリの出力値に従って、前段の前記論理関数メモリの複数の出力線及び複数の前記外部入力線のうちの何れか一本を選択して後段の前記論理関数メモリの入力線に接続するものであること;
を特徴とする請求の範囲第1項乃至第12項の何れか一記載のプログラマブル論理デバイス。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2005504294thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent.


PAGE TOP

close
close
close
close
close
close
close