Top > Search of Japanese Patents > (In Japanese)グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法

(In Japanese)グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法

Patent code P140011054
File No. 2013-P10
Posted date Oct 30, 2014
Application number P2005-515662
Patent number P4562136
Date of filing Nov 19, 2004
Date of registration Aug 6, 2010
International application number JP2004017263
International publication number WO2005050494
Date of international filing Nov 19, 2004
Date of international publication Jun 2, 2005
Priority data
  • P2003-389264 (Nov 19, 2003) JP
Inventor
  • (In Japanese)笹尾 勤
  • (In Japanese)井口 幸洋
Applicant
  • (In Japanese)学校法人明治大学
Title (In Japanese)グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法
Abstract (In Japanese)多出力論理関数に対し、中間出力を有するLUT論理回路が合成可能な論理回路合成装置を提供する。
多出力論理関数f(X)の特性関数x(X,Y)の特性関数二分決定グラフ節点テーブル記憶手段8と、LUT記憶手段16と、特性関数二分決定グラフを所定の高さlevの分割線で部分グラフB0,B1に分割し短絡除去処理を行う短絡除去手段11と、分割線における幅Wを計測するBDD幅計測手段12と、幅Wに基づき中間変数の個数を算出する中間変数算出手段13と、部分グラフB0につきLUTを生成するLUT生成手段14と、中間変数の個数uと等しい制御入力数を有する二分木を生成し、部分グラフB0を二分木で置き換え、特性関数二分決定グラフを再構成するBDD再構成手段15とを備えた構成とした。
Outline of related art and contending technology (In Japanese)

近年では、種々の電子回路の設計において、LUT型のフィールド・プログラマブル・ゲートアレイ(Field Programmable Gate Array:以下、「FPGA」という。)が広く使用されている(例えば、非特許文献1~3参照)。LUT型FPGAは、多数の再構成可能論理ブロック(Configurable Logic Block:以下、「CLB」という。)が格子状に配列され、各CLBの間に縦横に格子状に配線された複数の接続線(routing line:繞線)を備えた構成からなる。各々の接続線の交点には、再構成可能なスイッチ・ブロック(Switch Block:以下「SB」という。)が配されており、各々の接続線の接続を自由に変更(再構成)することができる。また、各CLBと接続線とは、再構成可能な接続ブロック(Connection Block:以下、「CB」という。)により接続されている。そして、各接続線の終端には、FPGA外部との入出力を行う入出力部(I/O)が設けられている。各CLBは、内部に多入力1出力のLUTやマルチプレクサ(MUX)を1ないし複数個有し、このLUTやMUXにより論理演算が可能である。LUT型FPGAでは、SB、CB及びCLBの内部を再構成することにより、所望の多入力1出力論理関数が格納された複数のLUTの入出力を目的に応じてネットワーク状に順序接続し、様々な組み合わせ論理回路を実現することができる。

一方、FPGAよりも高速な再構成可能論理回路を実現するものとして、LUTカスケード論理回路が提案されている(例えば、非特許文献4,5参照)。LUTカスケード論理回路においては、多入力多出力のLUTがカスケード状に接続された構成からなる。各LUTには、外部からの入力に加えて前段のLUTの出力が入力される。そして、最終段のLUTから1ないし複数の出力変数が出力される。演算を行おうとしている論理関数を複数の多出力論理関数に分解し、各多出力論理関数は各段のLUTに格納される。このようにして、LUTカスケード論理回路においては多出力論理関数の演算を行うことができる。

上記のようなLUT型FPGAやLUTカスケード論理回路を、実際の論理回路設計に適用する場合には、まず、論理回路で実現しようとする論理関数(以下、「目的論理関数」という。)を複数の論理関数に関数分解して合成論理関数とする。ここで、合成論理関数とは、関数分解により得られる複数の論理関数(以下、「分解関数」という。)の結合論理からなる関数をいう。すなわち、目的論理関数をf(X)({X}は入力変数の集合)で表した場合に、この目的論理関数を、f(X1,X2)=g(h(X1),X2)({X1}⊂{X},{X2}⊂{X},{X1}∩{X2}=φ,{X1}∪{X2}={X})の形に関数分解した場合、g(h(X1),X2)をgとhの合成論理関数という。

尚、本明細書において、X,Yと記す場合には、入力変数,出力変数のベクトル又は全順序集合(ordered set)を表し、{X},{Y}と記すときは、入力変数,出力変数の非順序集合(unordered set)を表すものとする。

上記関数分解により、2つの分解関数h(X1),g(h,X2)が得られる。尚、かかる関数分解は常に可能であるとは限らないが、コンピュータ等で使用する制御回路や算術演算回路等の多くの実用的関数は分解可能なものが多い(非特許文献6参照)。また、分解関数g(h,X2)が更に分解可能であれば同様の関数分解を繰り返す。

そして、各分解関数を別々のLUTとして実現し、各LUTを合成論理関数に従ってネットワーク状又はカスケード状に接続する。このようにして、目的論理関数をLUT型FPGAやLUTカスケード論理回路によって実現することができる。

単一出力の目的論理関数を、上記関数分解の手法を用いて、LUTが結合した論理回路により実現することは比較的容易である(例えば、非特許文献4,5参照)。

一方、目的論理関数が多出力である場合において、目的論理関数をLUTが結合した論理回路により実現する論理合成技術としては、現在のところ以下の方法によるものが知られている。
(1)多端子二分決定グラフ(Multi-Terminal Binary Decision Diagram:MTBDD)を用いる方法(非特許文献7,8参照)
(2)出力を幾つかのグループに分割して構成する方法(非特許文献7参照)
(3)分割理論を用いる方法(非特許文献9,10参照)
(4)代入による方法(非特許文献11参照)
(5)Hyper Functionを用いる方法(非特許文献12参照)
(6)非零出力符号化特性関数(Encoded Characteristic Function for Non-zero:ECFN)を用いた時分割実現による方法(非特許文献4,5参照)
(7)以上のうちいくつかの方法の組み合わせによる方法(非特許文献11参照)
【非特許文献1】
S.Brown,R.J.Francis,J.Rose,and Z.G.Vranesic,″Field-Programmable Gate Arrays″,Kluwer Academic Publishers,1992.
【非特許文献2】
P.Chow,S.O.Seo,J.Rose,K.Chung,G.Paez-Monzon,and I.Rahardja,″The design of an SRAM-based field-programmable gate array---Part I:Architecture,″IEEE Transactions on VLSI Systems,vol.7,pp.191-197,June 1999.
【非特許文献3】
Chow,P.,S.Seo,J.Rose,K.Chung,G.Pez-Monzn and I.Rahardja.″The Design of an SRAM-Based Field-Programmable Gate Array,Part II:Circuit Design and Layout″,IEEE Transactions on Very Large Scale Integration(VLSI)Systems,Vol.7 No.3,Sept.1999,pp.321-330.
【非特許文献4】
笹尾勤,松浦宗寛,井口幸洋,“多出力関数のカスケード実現と再構成可能ハードウェアによる実現”,電子情報通信学会FTS研究会,FTS2001-8,pp.57-64,三重大学(2001-04).
【非特許文献5】
T.Sasao,M.Matsuura,and Y.Iguchi,″A cascade realization of multiple-output fulnction for reconfigurable hardware,″International Workshop on Logic and Synthesis(IWLS01),Lake Tahoe,CA,June 12-15,2001.pp.225-230.
【非特許文献6】
T.Sasao and M.Matsuura,″DECOMPOS:An integrated system for functional decomposition″,1998 International Workshop on Logic Synthesis,Lake Tahoe,June 1998.
【非特許文献7】
Y-T.Lai,M.Pedram and S.B.K.Vrudhula,″BDD based decomposition of logic functions with application to FPGA synthesis″,30th ACM/IEEE Design Automation Conference,June 1993.
【非特許文献8】
T.Sasao,″FPGA design by generalized functional decomposition″,In Logic Synthesis and Optimization,Sasao ed.,Kluwer Academic Publisher,pp.233-258,1993.
【非特許文献9】
C.Scholl and P.Molitor,″Communication based FPGA synthesis for multi-output Boolean functions″,Asia and South Pacific Design Automation Conference,pp.279-287,Aug.1995.
【非特許文献10】
B.Wurth,K.Eckl,and K.Anterich,″Functional multiple-output decomposition:Theory and implicit algorithm″,Design Automation Conf.,pp.54-59,June 1995.
【非特許文献11】
H.Sawada,T.Suyama,and A.Nagoya,″Logic synthesis for look-up table based FPGAs using functional decomposition and support minimization″,ICCAD,pp.353-359,Nov.1995.
【非特許文献12】
J.-H.R.Jian,J.-Y.Jou,and J.-D.Huang,″Compatible class encoding in hyper-function decomposition for FPGA synthesis″,Design Automation Conference,pp.712-717,June 1998.
【非特許文献13】
P.Ashar and S.Malik,″Fast functional simulation using branching programs″,Proc.International Conference on Computer Aided Design,pp.408-412,Nov.1995.
【非特許文献14】
C.Scholl,R.Drechsler,and B.Becker,″Functional simulation using binary decision diagram″,ICCAD’97,pp.8-12,Nov.1997.
【非特許文献15】
A.Mishchenko and T.Sasao,″Logic Synthesis of LUT Cascades with Limited Rails″,電子情報通信学会VLSI設計技術研究会,VLD2002-9,琵琶湖(2002-11)
【非特許文献16】
M.R.Garey,D.S.Johnson,″Computers and Intractability:A Guide to the Theory of NP-Completeness″,W.H.Freeman & Co.,New York,1979.

Field of industrial application (In Japanese)

本発明は、ルックアップ・テーブル(以下、「LUT」という。)・カスケード論理回路やLUT型FPGA等において使用される、多出力論理関数f(X)に対応する論理回路を構成するためのデータであるLUTを生成するための論理回路合成技術に関するものである。

Scope of claims (In Japanese)
【請求項1】
 
入力変数をX=(x1,…,xn)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(1)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフ(Binary Decision Diagram for Characteristic Function : BDD for CF)の幅を削減するグラフ幅削減装置であって、以下の構成を備えているグラフ幅削減装置:
多出力論理関数F(X)の特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルを記憶する節点テーブル記憶手段;
前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定手段;
前記節点テーブル記憶手段に記憶された前記節点テーブルから、前記特性関数二分決定グラフを前記分割線設定手段により設定された前記分割の高さlevで分割し関数分解することによって得られる分解表の列を表す関数である列関数を生成する列関数生成手段;
及び、前記列関数生成手段が生成する各列関数のうち、両立する列関数に対してドント・ケアに定数を割り当てることによって同一の列関数(以下「割当列関数」という。)とするとともに、これらの新たな割当列関数を用いて前記特性関数二分決定グラフ再構成し前記節点テーブル記憶手段の節点テーブルを更新する割当BDD再構成手段。
【数1】
 
(省略)
但し、fi_0,fi_1,fi_dは、それぞれ、式(2)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数2】
 
(省略)

【請求項2】
 
前記列関数を節点(以下「関数節点」という。)とするグラフであって、互いに両立する複数の列関数に対応する関数節点同士が枝(以下「両立枝」という。)により連結されたグラフである両立グラフを、前記各関数節点の列関数ラベル及び当該関数節点に連結する両立枝のデータ(以下「関数節点データ」という。)のテーブルとして記憶するための両立グラフ記憶手段;
前記両立グラフ記憶手段に記憶された前記各関数節点データに対する列関数から、両立する列関数の組を選出し、それら両立する列関数に対する関数節点データにそれらの関数節点同士を連結する両立枝を追加して前記両立グラフ記憶手段に記憶された関数節点データの更新を行う両立枝生成手段;
及び、前記両立グラフのすべての節点について、完全部分グラフ(以下「クリーク」という。)による節点被覆を行うことにより、クリークに含まれる関数節点集合であるクリーク・データを生成するクリーク生成手段;
を備え、
前記列関数生成手段は、前記節点テーブル記憶手段に記憶された前記節点テーブルから、前記分割線設定手段により設定された前記分割の高さlevの節点の各枝に対応する列関数を生成し、それら各列関数に対応した列関数ラベルを有する前記関数節点データを生成して前記両立グラフ記憶手段に保存するものであり、
前記割当BDD再構成手段は、前記クリーク生成手段が生成する前記各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数とすることにより、前記特性関数二分決定グラフを再構成し前記節点テーブル記憶手段の前記節点テーブルを更新するものであること
を特徴とする請求項1記載のグラフ幅削減装置。

【請求項3】
 
前記分割線設定手段は、前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフの根節点の子の節点の高さから下位に向かって順次分割の高さlevの設定を行うものであり、
前記割当BDD再構成手段は、前記分割線設定手段が設定する前記各分割の高さlevにおいて逐次前記特性関数二分決定グラフ再構成を行うこと
を特徴とする請求項1又は2記載のグラフ幅削減装置。

【請求項4】
 
入力変数をX=(x1,…,xn)(n∈自然数)とする多出力論理関数F(X)=(f0(X),…,fm-1(X))の特性関数二分決定グラフから、前記多出力論理関数F(X)に対応する論理回路を構成するためのデータであるルックアップ・テーブル(Look-Up Table : LUT)を生成する論理回路合成装置であって、以下の構成を備えている論理回路合成装置:
完全定義関数である前記多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(3)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段;
前記ルックアップ・テーブルを記憶するLUT記憶手段;
前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定手段;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB0,B1に分割したときに根節点を含む側の部分グラフB0に属するものであって、出力を表す変数yr(∈Y)に関わる節点vj及びその親節点vkの節点データについて、当該節点vjの枝e0(vj),e1(vj)の一方ea(vj)がχ(X,Y)=0に関わる終端節点を特定する場合、当該節点vjの親節点vkの枝e0(vk),e1(vk)のうち当該節点vjを特定する枝ec(vk)を、当該節点vjの前記枝ea(vj)以外の枝eb(vj)に置き換える短絡除去処理を行う短絡除去手段;
前記短絡除去手段により短絡除去処理がされた特性関数二分決定グラフの各非終端節点であって前記分割の高さlevより高い高さにある非終端節点に属する枝のうち、前記分割の高さlevより低い高さの非終端節点の子節点を特定するものの個数を計数し(但し、同じ節点を特定するものは1つと数え、定数0に向かう枝は無視する。)、その個数を前記分割の高さlevの分割線における幅Wとして出力するBDD幅計測手段;
前記BDD幅計測手段が出力する幅Wに基づき、式(4)の演算により中間変数の個数uを算出する中間変数算出手段;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB0,B1に分割したときに根節点を含む側の部分グラフB0に属するものについて、ルックアップ・テーブルを生成しそれをLUT記憶手段に格納するLUT生成手段;
及び、前記中間変数算出手段が算出する前記中間変数の個数uと等しい制御入力数を有する二分木(binary tree)を生成するとともに、前記節点テーブル記憶手段に格納されている特性関数二分決定グラフの部分グラフB0に属する非終端節点の節点データを、前記二分木を表す節点データで置き換えることにより、特性関数二分決定グラフを再構成し、この再構成された特性関数二分決定グラフの各非終端節点の節点データにより前記節点テーブル記憶手段に格納された節点テーブルを更新するBDD再構成手段。
【数3】
 
(省略)
【数4】
 
(省略)

【請求項5】
 
前記節点テーブル記憶手段には、出力にドント・ケアを含む不完全定義関数である前記多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(5)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルとして記憶されていること
を特徴とする請求項4記載の論理回路合成装置。
【数5】
 
(省略)
但し、fi_0,fi_1,fi_dは、それぞれ、式(6)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数6】
 
(省略)

【請求項6】
 
請求項1乃至3の何れか一記載のグラフ幅削減装置を備え、
前記短絡除去手段は、前記グラフ幅削減装置によって前記節点テーブル記憶手段に記憶された前記節点テーブルにより表される特性関数二分決定グラフの幅を削減し更新された前記節点テーブルについて短絡除去処理を行うものであることを特徴とする請求項5記載の論理関数合成装置。

【請求項7】
 
前記多出力論理関数F(X)の要素をなす論理関数f0(X),…,fm-1(X)の順序をπ=(π[0], …, π[m-1])(但し、π[i]=jは、fjがi番目であることを表す。)とし、論理関数fj(∈F(X))が依存する入力変数の集合をsupp(fj)としたとき、式(7)で表されるTの値が最小となるように前記多出力論理関数F(X)の要素の順序πを決定する出力変数順序決定手段;
前記各入力変数xi(∈X)及び出力を表す変数yj(∈Y)の順序を、式(8)を満たす順序Pに決定する全変数順序決定手段;
及び、前記全変数順序決定手段で決定された順序Pに従って、特性関数二分決定グラフの節点データを生成し前記節点テーブル記憶手段に格納するBDD生成手段;
を備えていることを特徴とする請求項4乃至6の何れか一記載の論理回路合成装置。
【数7】
 
(省略)
【数8】
 
(省略)

【請求項8】
 
入力変数をX=(x1,…,xn)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(9)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段を備えたシステムにおいて、当該特性関数二分決定グラフの幅を削減するグラフ幅削減方法であって、以下の各ステップを有するグラフ幅削減方法:
前記節点テーブルによって表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定ステップ;
前記節点テーブル記憶手段に記憶された前記節点テーブルから、前記特性関数二分決定グラフを前記分割線設定ステップで設定された前記分割の高さlevで分割し関数分解することによって得られる分解表の列を表す関数である列関数を生成する列関数生成ステップ;
及び、前記列関数生成ステップにおいて生成される各列関数のうち、両立する列関数に対してドント・ケアに定数を割り当てることによって同一の列関数(以下「割当列関数」という。)にするとともに、これらの新たな割当列関数を用いて前記特性関数二分決定グラフ再構成し前記節点テーブル記憶手段の節点テーブルを更新する割当BDD再構成ステップ。
【数9】
 
(省略)
但し、fi_0,fi_1,fi_dは、それぞれ、式(10)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数10】
 
(省略)

【請求項9】
 
前記システムは、前記列関数を節点(以下「関数節点」という。)とするグラフであって、互いに両立する複数の列関数に対応する関数節点同士が枝(以下「両立枝」という。)により連結されたグラフである両立グラフを、前記各関数節点の列関数ラベル及び当該関数節点に連結する両立枝のデータ(以下「関数節点データ」という。)のテーブルとして記憶するための両立グラフ記憶手段を備えており、
前記列関数生成ステップにおいては、前記節点テーブル記憶手段に記憶された前記節点テーブルから、前記分割線設定ステップで設定された前記分割の高さlevの節点の各枝に対応する列関数を生成し、それら各列関数に対応した列関数ラベルを有する前記関数節点データを生成して前記両立グラフ記憶手段に保存するとともに、
前記両立グラフ記憶手段に記憶された前記各関数節点データに対する列関数から、両立する列関数の組を選出し、それら両立する列関数に対する関数節点データにそれらの関数節点同士を連結する両立枝を追加して前記両立グラフ記憶手段に記憶された関数節点データの更新を行う両立枝生成ステップ;
及び、前記両立グラフのすべての節点について、完全部分グラフ(以下「クリーク」という。)による節点被覆を行うことにより、クリークに含まれる関数節点集合であるクリーク・データを生成するクリーク生成ステップ;
を有し、
前記割当BDD再構成ステップにおいては、前記クリーク生成ステップにおいて生成される前記各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数とすることにより、前記特性関数二分決定グラフを再構成し前記節点テーブル記憶手段の前記節点テーブルを更新すること
を特徴とする請求項8記載のグラフ幅削減方法。

【請求項10】
 
前記分割線設定ステップにおける前記分割の高さlevを、前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフの根節点の子の節点の高さから最下位の高さまで順次変更しながら、前記分割線設定ステップ乃至前記割当BDD再構成ステップを実行すること
を特徴とする請求項8又は9記載のグラフ幅削減方法。

【請求項11】
 
入力変数をX=(x1,…,xn)(n∈自然数)とする完全定義関数である多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(11)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段;
及び、ルックアップ・テーブル(Look-Up Table : LUT)を記憶するためのLUT記憶手段;
を備えたシステムにおいて、
前記特性関数二分決定グラフから、前記多出力論理関数F(X)に対応する論理回路を構成するためのデータであるルックアップ・テーブルを合成する論理回路合成方法であって、以下のステップを有する論理回路合成方法:
前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定ステップ;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB0,B1に分割したときに根節点を含む側の部分グラフB0に属するものであって、出力を表す変数yr(∈Y)に関わる節点vj及びその親節点vkの節点データについて、当該節点vjの枝e0(vj),e1(vj)の一方ea(vj)がχ(X,Y)=0に関わる終端節点を特定する場合、当該節点vjの親節点vkの枝e0(vk),e1(vk)のうち当該節点vjを特定する枝ec(vk)を、当該節点vjの前記枝ea(vj)以外の枝eb(vj)に置き換える短絡除去処理を実行する短絡除去ステップ;
前記短絡除去処理がされた特性関数二分決定グラフの各非終端節点であって前記分割の高さlevより高い高さにある非終端節点に属する枝のうち、前記分割の高さlevより低い高さの非終端節点の子節点を特定するものの個数を計数し(但し、同じ節点を特定するものは1つと数え、定数0に向かう枝は無視する。)、その個数を前記分割の高さlevの分割線における幅Wとして出力するBDD幅計測ステップ;
前記幅Wに基づき、式(12)の演算により中間変数の個数uを算出する中間変数算出ステップ;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB0,B1に分割したときに根節点を含む側の部分グラフB0に属するものについて、ルックアップ・テーブルを生成しそれをLUT記憶手段に格納するLUT生成ステップ;
及び、前記中間変数算出ステップにおいて算出された前記中間変数の個数uと等しい制御入力数を有する二分木(binary tree)を生成するとともに、前記節点テーブル記憶手段に格納されている特性関数二分決定グラフの部分グラフB0に属する非終端節点の節点データを、前記二分木を表す節点データで置き換えることにより、特性関数二分決定グラフを再構成し、この再構成された特性関数二分決定グラフの各非終端節点の節点データにより前記節点テーブル記憶手段に格納された節点テーブルを更新するBDD再構成ステップ。
【数11】
 
(省略)
【数12】
 
(省略)

【請求項12】
 
前記節点テーブル記憶手段には、入力変数をX=(x1,…,xn)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f0(X),…,fm-1(X))に対して式(13)により定義される特性関数χ(X,Y)(但し、Y=(y0,…,ym-1)(m≧2, m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点viについて、当該非終端節点に関わる変数zi(zi∈(X∪Y))に付与される変数ラベル並びに当該変数zi(zi∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e0(vi),e1(vi)からなる節点データのテーブルである節点テーブルとして記憶されていること
を特徴とする請求項11記載の論理回路合成方法。
【数13】
 
(省略)
但し、fi_0,fi_1,fi_dは、それぞれ、式(14)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数14】
 
(省略)

【請求項13】
 
前記節点テーブル記憶手段に記憶された前記節点テーブルにより表される特性関数二分決定グラフの幅を、請求項8乃至10の何れかに記載のグラフ幅削減方法によって削減し、前記節点テーブル記憶手段に記憶された前記節点テーブルを更新した後に、前記分割線設定ステップ乃至前記BDD再構成ステップを実行する請求項12記載の論理回路合成方法。

【請求項14】
 
前記多出力論理関数F(X)の要素をなす論理関数f0(X),…,fm-1(X)の順序をπ=(π[0], …, π[m-1])(但し、π[i]=jは、fjがi番目であることを表す。)とし、論理関数fj(∈F(X))が依存する入力変数の集合をsupp(fj)としたとき、式(15)で表されるTの値が最小となるように前記多出力論理関数F(X)の要素の順序πを決定する出力変数順序決定ステップ;
前記各入力変数xi(∈X)及び出力を表す変数yj(∈Y)の順序を、式(16)を満たす順序Pに決定する全変数順序決定ステップ;
及び、前記順序Pに従って、特性関数二分決定グラフの節点データを生成し前記節点テーブル記憶手段に格納するBDD生成ステップ;
を実行した後に、前記分割線設定ステップ乃至前記BDD再構成ステップを実行することを特徴とする請求項11乃至14の何れか一記載の論理回路合成方法。
【数15】
 
(省略)
【数16】
 
(省略)

【請求項15】
 
コンピュータに請求項8乃至10の何れかに記載のグラフ幅削減方法を実行させるプログラム。

【請求項16】
 
コンピュータに請求項11乃至14に何れかに記載の論理回路合成方法を実行させるプログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2005515662thum.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