TOP > 国内特許検索 > グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法 > 明細書

明細書 :グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4562136号 (P4562136)
登録日 平成22年8月6日(2010.8.6)
発行日 平成22年10月13日(2010.10.13)
発明の名称または考案の名称 グラフ幅削減装置及びグラフ幅削減方法、並びに論理回路合成装置及び論理回路合成方法
国際特許分類 G06F  17/50        (2006.01)
FI G06F 17/50 656A
G06F 17/50 654M
請求項の数または発明の数 16
全頁数 53
出願番号 特願2005-515662 (P2005-515662)
出願日 平成16年11月19日(2004.11.19)
国際出願番号 PCT/JP2004/017263
国際公開番号 WO2005/050494
国際公開日 平成17年6月2日(2005.6.2)
優先権出願番号 2003389264
優先日 平成15年11月19日(2003.11.19)
優先権主張国 日本国(JP)
審査請求日 平成19年10月19日(2007.10.19)
特許権者または実用新案権者 【識別番号】802000031
【氏名又は名称】財団法人北九州産業学術推進機構
発明者または考案者 【氏名】笹尾 勤
【氏名】井口 幸洋
個別代理人の代理人 【識別番号】100121371、【弁理士】、【氏名又は名称】石田 和人
審査官 【審査官】田中 幸雄
参考文献・文献 笹尾勤ほか,多出力関数のカスケード実現と再構成可能ハードウェアによる実現,電子情報通信学会技術研究報告,日本,社団法人電子情報通信学会,2001年 4月 6日,Vol.101 No.3,57-64頁,FTS2001-8
調査した分野 G06F 17/50
特許請求の範囲 【請求項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】
JP0004562136B2_000044t.gif
但し、fi_0,fi_1,fi_dは、それぞれ、式(2)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数2】
JP0004562136B2_000045t.gif

【請求項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】
JP0004562136B2_000046t.gif
【数4】
JP0004562136B2_000047t.gif

【請求項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】
JP0004562136B2_000048t.gif
但し、fi_0,fi_1,fi_dは、それぞれ、式(6)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数6】
JP0004562136B2_000049t.gif

【請求項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】
JP0004562136B2_000050t.gif
【数8】
JP0004562136B2_000051t.gif

【請求項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】
JP0004562136B2_000052t.gif
但し、fi_0,fi_1,fi_dは、それぞれ、式(10)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数10】
JP0004562136B2_000053t.gif

【請求項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】
JP0004562136B2_000054t.gif
【数12】
JP0004562136B2_000055t.gif

【請求項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】
JP0004562136B2_000056t.gif
但し、fi_0,fi_1,fi_dは、それぞれ、式(14)で定義されるOFF関数、ON関数、及びDC関数を表す。
【数14】
JP0004562136B2_000057t.gif

【請求項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】
JP0004562136B2_000058t.gif
【数16】
JP0004562136B2_000059t.gif

【請求項15】
コンピュータに請求項8乃至10の何れかに記載のグラフ幅削減方法を実行させるプログラム。
【請求項16】
コンピュータに請求項11乃至14に何れかに記載の論理回路合成方法を実行させるプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、ルックアップ・テーブル(以下、「LUT」という。)・カスケード論理回路やLUT型FPGA等において使用される、多出力論理関数f(X)に対応する論理回路を構成するためのデータであるLUTを生成するための論理回路合成技術に関するものである。
【背景技術】
【0002】
近年では、種々の電子回路の設計において、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の入出力を目的に応じてネットワーク状に順序接続し、様々な組み合わせ論理回路を実現することができる。
【0003】
一方、FPGAよりも高速な再構成可能論理回路を実現するものとして、LUTカスケード論理回路が提案されている(例えば、非特許文献4,5参照)。LUTカスケード論理回路においては、多入力多出力のLUTがカスケード状に接続された構成からなる。各LUTには、外部からの入力に加えて前段のLUTの出力が入力される。そして、最終段のLUTから1ないし複数の出力変数が出力される。演算を行おうとしている論理関数を複数の多出力論理関数に分解し、各多出力論理関数は各段のLUTに格納される。このようにして、LUTカスケード論理回路においては多出力論理関数の演算を行うことができる。
【0004】
上記のようなLUT型FPGAやLUTカスケード論理回路を、実際の論理回路設計に適用する場合には、まず、論理回路で実現しようとする論理関数(以下、「目的論理関数」という。)を複数の論理関数に関数分解して合成論理関数とする。ここで、合成論理関数とは、関数分解により得られる複数の論理関数(以下、「分解関数」という。)の結合論理からなる関数をいう。すなわち、目的論理関数をf(X)({X}は入力変数の集合)で表した場合に、この目的論理関数を、f(X,X)=g(h(X),X)({X}⊂{X},{X}⊂{X},{X}∩{X}=φ,{X}∪{X}={X})の形に関数分解した場合、g(h(X),X)をgとhの合成論理関数という。
【0005】
尚、本明細書において、X,Yと記す場合には、入力変数,出力変数のベクトル又は全順序集合(ordered set)を表し、{X},{Y}と記すときは、入力変数,出力変数の非順序集合(unordered set)を表すものとする。
【0006】
上記関数分解により、2つの分解関数h(X),g(h,X)が得られる。尚、かかる関数分解は常に可能であるとは限らないが、コンピュータ等で使用する制御回路や算術演算回路等の多くの実用的関数は分解可能なものが多い(非特許文献6参照)。また、分解関数g(h,X)が更に分解可能であれば同様の関数分解を繰り返す。
【0007】
そして、各分解関数を別々のLUTとして実現し、各LUTを合成論理関数に従ってネットワーク状又はカスケード状に接続する。このようにして、目的論理関数をLUT型FPGAやLUTカスケード論理回路によって実現することができる。
【0008】
単一出力の目的論理関数を、上記関数分解の手法を用いて、LUTが結合した論理回路により実現することは比較的容易である(例えば、非特許文献4,5参照)。
【0009】
一方、目的論理関数が多出力である場合において、目的論理関数を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.
【発明の開示】
【発明が解決しようとする課題】
【0010】
上記背景技術に挙げた(1)~(7)の方法による論理合成技術は、何れも多出力論理関数の論理合成の技術としては決定的な方法であるとはいえない。例えば、MTBDDを用いて多出力論理関数の関数分解を行うことは、理論上は可能である。しかしながら、m出力の論理関数の場合、最大で2個の終端節点が存在する。従って、MTBDDを用いて多出力論理関数の関数分解を行った場合には、多くの場合、列複雑度(後述の〔定義6〕参照)が増大し、実用的ではない。また、他の従来の方法に関しても同様なことがいえる。
【0011】
一方、比較器や加算器のように、すべての論理演算が終了しない段階においても、演算を進めるに従って、順次出力変数が決定していくような論理関数も多い。例えば、入力変数P=(p,p,p,p)(P∈B,B={0,1})及びQ=(q,q,q,q)(Q∈B)を加算して出力変数R=(r,r,r,r,cout)(R∈B)を出力するような加算器では、各桁の加算が終了した時点で、すべての桁の演算が終了する前にその桁に対応する出力変数が決定する。このように、すべての論理演算が終了しない段階で決定し出力される出力変数を「中間出力変数」という。
【0012】
目的論理関数が中間出力変数を有する場合、目的論理関数を実現するLUTネットワークやLUTカスケードにおいては、最終段以外の段のLUTにおいて中間出力変数を出力するように構成することにより、各LUTのサイズを小さくするとともに演算速度を向上させることが可能となる。
【0013】
しかしながら、上記背景技術に挙げた論理合成技術では、中間出力変数を有する目的論理関数に対して、中間出力を有するLUTネットワークやLUTカスケードを合成することは困難であった。
【0014】
また、基数変換回路や加算回路などにおいては、各出力値は必ずしもすべての入力に対して定義されておらず、一部の入力変数に対しては出力値が0でも1でもよいようなドント・ケアを含む場合が多い。このようなドント・ケアを含む多出力論理関数をそのままLUTネットワークやLUTカスケードとして合成すると、メモリの冗長性が大きくなる。従って、ドント・ケアを含む多出力論理関数についてはできるだけLUTネットワークやLUTカスケードの冗長性が少なくなる形式に変更することが好ましい。
【0015】
そこで、本発明の第1の目的は、一般的な多出力論理関数に対して汎用的に論理合成が可能であり、また、中間出力を有するLUTネットワークやLUTカスケードを合成することが可能な論理回路合成技術を提供することにある。
【0016】
また、本発明の第2の目的は、ドント・ケアを含む多出力論理関数を、LUTネットワークやLUTカスケードの冗長性が少なくなる形式に変更する一手法であるグラフ幅削減技術を提供することにある。
【課題を解決するための手段】
【0017】
以下の説明では、まず本明細書で使用する主要な用語について定義し、本発明の基本的原理について説明した後、本発明の構成及び作用について説明する。
【0018】
〔1〕用語の定義等
〔定義1〕(サポート変数)
関数Fが変数xに依存するとき、xをFの「サポート変数(support variable)」という。関数Fのサポート変数の集合をsupp(F)と記す。
〔定義終わり〕
【0019】
〔定義2〕(完全定義関数)
ブール変数をxと記し、x全体の集合をB={0,1}と記す。論理変数X(∈B,nは任意の自然数)の関数F(X):B→B(mは任意の自然数)を「完全定義関数(completely specified function)」という。特に、mが2以上の自然数の場合を「完全定義多出力関数(completely specified multiple-output function)」といい、m=1の場合を「完全定義単一出力関数(completely specified single-output function)」という。
〔定義終わり〕
【0020】
〔定義3〕(不完全定義関数)
ある関数f(X)の関数値が0でも1でもよいことを「ドント・ケア(don’t care)」といい、dと記す。論理変数X(∈B,nは任意の自然数)の関数F(X):B→{0,1,d}(mは任意の自然数)を「不完全定義関数(incompletely specified function)」という。特に、mが2以上の自然数の場合を「不完全定義多出力関数(incompletely specified multiple-output function)」といい、m=1の場合を「不完全定義単一出力関数(incompletely specified single-output function)」という。
〔定義終わり〕
【0021】
〔定義4〕(変数の分割)
論理関数の入力変数をX=(x,x,…,x)とする。Xの変数の集合を{X}で表す。{X}∪{X}={X}かつ{X}∩{X}=φのとき、X=(X,X)を「Xの分割(partition)」という。また、Xの変数の個数を|X|で表す。
〔定義終わり〕
【0022】
〔定義5〕(分解表)
論理関数F(X)に対して、Xの分割をX=(X,X)とする。また、|X|=n,|X|=nとする。このとき、2n1列2n2行の表で、各行、各列に2進符号のラベルを持ち、その要素がFの真理値であるような表を、Fの「分解表(decomposition chart)」という。このとき、Xを「束縛変数(bound variable)」、Xを「自由変数(free variable)」という。ここで、分解表の列、行は、それぞれn,nビットのすべてのパターンを有する。
〔定義終わり〕
【0023】
〔定義6〕(列複雑度、列関数)
分解表の異なる列パターンの数を「列複雑度(column multiplicity)」といい、μと記す。列パターンが表す関数を「列関数(column function)」という。
〔定義終わり〕
【0024】
〔例1〕
(表1)に4入力1出力不完全定義関数の分解表を示す。すべての列パターンが異なるので、列複雑度μは4となる。
【0025】
【表1】
JP0004562136B2_000002t.gif
〔例終わり〕
【0026】
〔定義7〕(ON関数、OFF関数、DC関数)
f(X)=0,1,dを満たすすべてのXの集合を、それぞれ、「OFF集合(OFF-set)」、「ON集合(ON-set)」、「DC集合(DC-set)」といい、f-1(0),f-1(1),f-1(d)と記す。論理変数X(∈B)の不完全定義関数をf(X)とする。OFF集合f-1(0)に属するすべてのXに1を対応づけ、それ以外のXに0を対応づける関数を「OFF関数(OFF-function)」といい、f_0と記す。
【0027】
【数1】
JP0004562136B2_000003t.gif

【0028】
ON集合f-1(1)に属するすべてのXに1を対応づけ、それ以外のXに0を対応づける関数を「ON関数(ON-function)」といい、f_1と記す。
【0029】
【数2】
JP0004562136B2_000004t.gif

【0030】
DC集合f-1(d)に属するすべてのXに1を対応づけ、それ以外のXに0を対応づける関数を「DC関数(DC-function)」といい、f_dと記す。
【0031】
【数3】
JP0004562136B2_000005t.gif

【0032】
f(X)が完全定義関数の場合にも、OFF関数f_0,ON関数f_1を同様に定義する。特にf(X)が完全定義単一出力関数の場合、
【0033】
【数4】
JP0004562136B2_000006t.gif
である。
〔定義終わり〕
【0034】
〔定義8〕(完全定義関数の特性関数)
入力変数をX=(x,x,…,x)(∈B)とし、完全定義多出力関数をF(X)=(f(X),f(X),…,fm-1(X))(mは自然数)とする。このとき、以下の式(5)ように定義される関数x(X,Y)を多出力論理関数Fの「特性関数(characteristic function)」という(非特許文献14参照)。ここで、Y=(y,…,ym-1)は出力を表す変数である。
【0035】
【数5】
JP0004562136B2_000007t.gif
〔定義終わり〕
【0036】
n入力m出力関数の特性関数は(n+m)変数の二値論理関数であり、入力変数x(i=1,2,…,n)の他に、各出力f(j=0,1,…,m-1)に対して出力変数yを用いる。B={0,1}とする。X∈BかつF(X)=(f(X),f(X),…,fm-1(X))∈Bとする。いま、Y∈Bとすると、論理関数F(X)の特性関数x(X,Y)の値は式(6)のようになる。
【0037】
【数6】
JP0004562136B2_000008t.gif

【0038】
完全定義多出力関数の特性関数は、入力の組み合わせと出力の組み合わせのうち許されているものを表す。式(7)のようにおくと、特性関数xは式(8)のように表現することができる。
【0039】
【数7】
JP0004562136B2_000009t.gif

【0040】
【数8】
JP0004562136B2_000010t.gif

【0041】
一方、不完全定義関数では、ドント・ケアの場合、その関数値が0でも1でもよい。従って、特性関数では、出力変数yの値が0でも1でも真となる。そこで、ドント・ケアを表現する不定値関数fi_dに対して、次式が成立する。
【0042】
【数9】
JP0004562136B2_000011t.gif

【0043】
式(8)、式(9)より、完全定義多出力関数の特性関数を拡張して、不完全定義関数の特性関数xを次のように定義する。
【0044】
〔定義9〕(不完全定義関数の特性関数)
入力変数X=(x,x,…,x)(∈B)の不完全定義多出力関数をF(X)=(f(X),f(X),…,fm-1(X))とする。このとき、以下の式(10)により定義される関数x(X,Y)を不完全定義多出力関数Fの特性関数という。ここで、Y=(y,…,ym-1)は出力を表す変数である。
【0045】
【数10】
JP0004562136B2_000012t.gif
〔定義終わり〕
【0046】
〔例2〕
(表2)に示した4入力2出力の不完全定義関数を考える。
【0047】
【表2】
JP0004562136B2_000013t.gif
(表2)より、各OFF関数、ON関数、DC関数は次のように記述される。
【0048】
【数11】
JP0004562136B2_000014t.gif
従って、この関数の特性関数は、次式のようになる。
【0049】
【数12】
JP0004562136B2_000015t.gif
〔例終わり〕
【0050】
〔定義10〕(特性関数二分決定グラフ)
多出力論理関数F(X)=(f(X),f(X),…,fm-1(X))の「特性関数二分決定グラフ(Binary Decision Diagram for Characteristic Function:BDD for CF)」とは、多出力論理関数F(X)の特性関数x(X,Y)を表現する二分決定グラフ(Binary Decision Diagram:BDD)をいう。但し、二分決定グラフの変数は、根節点を最上位としたとき、変数yはfに依存する入力変数x∈supp(f)よりも下位に置く。ここに、supp(f)はfの依存変数の集合を表す。(非特許文献13,14参照)
〔定義終わり〕
【0051】
〔例3〕
図1(a)の真理値表によって表現される多出力論理関数の特性関数二分決定グラフは、図1(b)により表される。ここで、○は変数節点を表し、□は特性関数値の節点を表す。
〔例終わり〕
【0052】
〔定義11〕(短絡除去)
特性関数二分決定グラフにおいて、出力を表す節点y(∈Y)から出る枝(edge)のうち、定数0に接続する枝を取り除き、節点yの親節点(parent node)から節点yの定数0以外の子節点(child node)へ直接枝を繋ぐ。この作業を、yを表現する総ての節点に対して実行する操作を、「出力変数yの短絡除去(removal of the output variabley_i by shorting)」という。
〔定義終わり〕
【0053】
具体的に図2を用いて短絡除去の説明をする。図2(a)に示したような出力を表す節点y(∈Y)を考える。節点yの親節点をz、節点yの子節点をzとする。まず、特性関数値0に接続する節点を除去すると、図2(b)のようになる。次に、節点yの親節点zから子節点Zzへ直接枝を繋ぐことにより、図2(c)のようにグラフが変形される。節点yに関する短絡除去では、以上のような操作を、特性関数二分決定グラフの中にある出力を表す節点yのすべてについて行うものである。
【0054】
〔定義12〕(特性関数二分決定グラフの幅)
(zn+m,zn+m-1,…,z)を特性関数二分決定グラフの変数順序とする。ここで、zn+mは、根節点に対応する。特性関数二分決定グラフの高さkでの「幅」とは、変数zと変数zk+1との間の枝の本数をいう。ここで、同じ節点に接続している枝は一つと数え、定数0に向かう枝は無視する。また、特性関数二分決定グラフの高さ0での幅を1と定義する。
〔定義終わり〕
【0055】
変数zの節点の高さ(level)とは、二分決定グラフにおいて順序づけられた変数において、終端節点から数えた順番をいう。但し、終端節点の高さは0とする。すなわち、n+m個の変数{z;i=1,…,n+m}を有する二分決定グラフにおいて根節点から終端節点にかけて順序づけられた変数順序をP=(zn+m,zn+m-1,…,z)とすると、変数zの節点の高さはiとなる。このとき、変数z,zについてi>jのとき、変数zは変数zよりも高位(high level)である(又は変数zは変数zよりも低位である)という。また、高さiでの幅は、変数zと変数zi+1との間の枝の本数である。但し、同じ節点を特定するものは1つと数え、定数0に向かう枝は無視する。
【0056】
〔例4〕
図1(b)の特性関数二分決定グラフにおいては、終端節点(特性関数値がラベル付けられた節点)の高さが0、変数yの高さが1、変数yの高さが2、変数xの高さが3、…、変数xの高さが7となる。また、高さ1での幅は、変数yの節点から変数yの節点へ向かう枝の本数(但し、終端節点0へ向かう枝は無視するものとする。)で2である。また、高さ2での幅は、変数xの節点から変数yの節点へ向かう枝の本数で4である。
〔例終わり〕
【0057】
BDDを用いた関数分解において、BDDの幅は列複雑度μに等しい。(〔注意〕列複雑度を考えるときは、元の多出力関数を考える(表3の分解表参照)。BDDを考えるときは、多出力関数の特性関数を考える。単一出力論理関数の時は、必然的に、出力変数は、一番下に来る。定数1に至るBDDの部分が、もとの関数のBDDと殆ど変わらない。)変数の分割(X,X)において、変数Xの節点に直接接続されている変数Xの節点は、分解表の列パターンに対応する。
【0058】
関数分解では、f(X,X)=g(h(X),X)と表現する。
【0059】
【数13】
JP0004562136B2_000016t.gif
が成立するとき、Xを入力とし列関数の符号を生成するh(X)の回路と、g(h,X)の回路を個別に実現することによって、関数fを実現する(図3参照)。関数分解は分解後の関数gの入力数が少ないほど効果的である。BDDの幅を削減できれば、列複雑度が減り、関数分解の効果が上がる。
【0060】
〔定義13〕(ドント・ケアへの定数の割り当て)
2つの不完全定義列関数をF(1)=(f(1),f(1)…,fm-1(1)),F(2)=(f(2),f(2),…,fm-1(2))とする。このとき、f(1)=d又はf(2)=dであるF(1),F(2)の各要素に対して、次のような論理積演算f(1)・f(2)を行うことを「ドント・ケアへの定数の割り当て(don’t care assignment)」という。
【0061】
【数14】
JP0004562136B2_000017t.gif
〔定義終わり〕
【0062】
〔定義14〕(関数の両立)
二つの不完全定義関数fとfにドント・ケアへの定数の割り当てを行うことで、同じ関数にできる場合、fとfは「両立する(compatible)」といい、f~fと記す。
〔定義終わり〕
【0063】
〔補題1〕
三つの不完全定義関数の特性関数をx,xとする。x~x且つx=xのとき、x~x且っx~xが成立する。
〔補題終わり〕
【0064】
〔例5〕
(表1)の分解表で、列関数の対{Φ,Φ},{Φ,Φ},{Φ,Φ}は両立する。列ΦとΦの論理積をとり、ΦとΦと置き換え、列ΦとΦの論理積をとり、ΦとΦと置き換えると(表3)のようになり、μ=2となる。
【0065】
【表3】
JP0004562136B2_000018t.gif
〔例終わり〕
【0066】
〔定義15〕(両立グラフ)
関数を節点とし、両立する関数同士を枝で接続したグラフを「両立グラフ(compatible graph)」という。
〔定義終わり〕
【0067】
〔2〕本発明の基本的原理
(1)不完全定義多出力論理関数の特性関数二分決定グラフの幅の削減
最初に、不完全定義多出力論理関数を表現する特性関数二分決定グラフの幅を削減する方法について説明する。一つの方法としては、特性関数二分決定グラフの1つの節点に着目し、その節点の2つの子節点が両立する場合、2つの子節点を併合して一つにすることを繰り返し、節点数を削減する方法が考えられる。この方法のアルゴリズムは、以下のアルゴリズム1のようになる。
【0068】
〔アルゴリズム1〕
特性関数二分決定グラフの根節点から、再帰的に以下の処理を行う。
(1)節点vがドント・ケアを含まなければ終了;
(2)節点vの2つの子節点v,vが両立するか調べる;
・両立しなければ、v,vに対して再帰する;
・両立すれば、v,vをvnewに置き換える。vnewに対して再帰する。但し、v,v,vnewを表す特性関数をx,x,xnewとすれば、xnew=x・x
【0069】
〔例6〕
(表4)に4入力2出力不完全定義関数の真理値表を示す。
【0070】
【表4】
JP0004562136B2_000019t.gif

【0071】
(表4)の真理値表によって表される不完全定義多出力関数を特性関数二分決定グラフにより表すと、図4(a)のようになる。図4(a)では、節点1,2が両立する子節点を持っている。この特性関数二分決定グラフに対してアルゴリズム1を適用すると、図4(b)のようになる。この関数では、節点1を置き換える節点と、節点2を置き換える節点が同じになるので、図4(b)では、節点1,2が節点3に置き換えられている。図4の特性関数二分決定グラフの左にあるWidthは、各高さでの幅である。最大幅は8から5に削減され、非終端節点の数は15から12に削減されている。
〔例終わり〕
【0072】
アルゴリズム1のグラフ幅削減方法は、局所的な節点数の削減には効果がある。しかし、一つの節点の子節点同士でしか両立性を考えていないため、全体的な特性関数二分決定グラフの幅の削減にはあまり効果的ではない。そこで、次に、特性関数二分決定グラフの幅を構成するすべての部分関数の両立性を調べ、マッチングを行うことで直接幅を削減するグラフ幅削減方法を示す。
【0073】
関数分解において、すべての列関数の両立性を調べ、両立グラフを作成し、最小数の完全部分グラフ(クリーク)による節点被覆を行うことで、列複雑度μの最小化が可能である。しかしながら、この節点被覆の問題はNP困難であることが知られている(非特許文献16参照)。そこで、ここでは次のアルゴリズム2で表される発見的手法を使用する。
【0074】
〔アルゴリズム2〕(クリーク集合による節点被覆)
与えられた両立グラフのすべての節点の集合をSとする。Cを節点集合の集合とする。枝を持たない節点をSから除去し、要素が1つの節点集合(クリーク)としてCの要素とする。
≠φの間、以下の(1)~(3)の操作を繰り返す:
(1)Sの中で枝数最小の節点を調べ、これをvとする。S←{v}とする。Sの中でvに接続している節点の集合をSとする;
(2)S≠φの間、以下の(a),(b)の操作を繰り返す;
(a)Sの中で枝数最小の節点vを調べ、S←S∪{v},S←S-{v}とする;
(b)vに接続していない節点をSから除去する;
(3)C←C∪{S},S←S-S
【0075】
両立グラフ上におけるクリーク集合による節点被覆を利用して、次のアルゴリズム3により、特性関数二分決定グラフの幅の削減を行うことができる。
【0076】
〔アルゴリズム3〕(特性関数二分決定グラフの幅削減)
与えられた特性関数二分決定グラフの高さをtとし、定数節点の高さを0とする。高さt-1から1までの間、以下の操作を繰り返す:
(1)各高さにおけるすべての列関数の集合を作る;
(2)列関数の集合から両立グラフを作成する;
(3)クリーク集合による節点被覆(例えば、アルゴリズム2)を行う;
(4)各クリークに被覆されているすべての節点に対応する列関数に対して、ドント・ケアへの定数の割り当てを行い、一つの列関数(割当列関数)にする;
(5)各列関数を(4)で作成した割当列関数に置換して、特性関数二分決定グラフを再構成する。
【0077】
このグラフ幅削減方法によれば、特性関数のすべての部分関数の両立性を全体的に評価して最適なドント・ケアへの定数の割り当てができる。従って、特性関数二分決定グラフの幅を効果的に削減することが可能となる。
【0078】
(2)目的論理関数の関数分解とLUT回路の生成
次に、特性関数二分決定グラフからLUT論理回路を合成する手法について、その原理を説明する。本発明におけるLUT論理回路の合成は、特性関数二分決定グラフの分割と短絡除去とを利用して行う。特性関数二分決定グラフを分割して2つの回路を構成した場合、両回路を接続する接続線数は、次の〔定理1〕により算出することができる。
【0079】
〔定理1〕
,Xを入力変数の集合、Y,Yを出力変数の集合とする。特性関数二分決定グラフの変数順序を(X,Y,X,Y)とするとき、特性関数二分決定グラフの高さ|X|+|Y|における幅をWとする。ここで、Wを数える際、出力を表現する変数から、定数0へ向かう枝は無視する。多出力論理関数を図3の回路で実現する場合、二つの回路HとGの間の必要かつ十分な接続線数uは、式(15)により表される。
【0080】
【数15】
JP0004562136B2_000020t.gif
〔定理終わり〕
【0081】
(証明)
特性関数二分決定グラフの構成法から、出力関数YとYが、図3の回路で表現できることは明らかである。特性関数二分決定グラフにおいて、Yの出力を表現する節点を短絡除去すると、Y以外の関数を表現する特性関数二分決定グラフが得られる。また、この操作によって、特性関数二分決定グラフの幅が増えることはない。高さ|X|+|Y|におけるBDDの幅をWとする。いま、関数分解g(h(X),X)の分解表を考えると、その列複雑度はWに等しい。従って、回路Hと回路Gの間の配線数は、
【0082】
【数16】
JP0004562136B2_000021t.gif
だけあれば十分である。また、分解表の列複雑度はWなので、二つのブロック間の配線は少なくとも式(16)の本数だけ必要である。
(証明終わり)
【0083】
特性関数二分決定グラフの分割及び短絡除去と上記〔定理1〕とを利用して、次のように目的論理関数の関数分解が行われる。
【0084】
まず、目的論理関数F=(f,f,…,fm-1)の特性関数二分決定グラフの変数順序が(X,Y,X,Y),Y=(y,y,…,yk-1),Y=(y,yk+1,…,ym-1)であるとする。この場合、y=f(X)(j=0,1,…,k-1)は図3の回路Hで直接実現する。一方、高さ|X|+|Y|における特性関数二分決定グラフの幅をWとする。W本の枝にuビット(uは式(15)により得られる数。)の異なる二進数を割り当てる。二つのブロックH,G間を接続する枝が実現する関数をh,h,…,hとすると、ブロックGの出力関数Yは(h,h,…,h,X)を入力変数とする論理関数として表現可能であり、その特性関数二分決定グラフは図5のようになる。
【0085】
〔例7〕
本例では、2つの2ビットの2進数を加算する回路(ADR2)を、中間出力を有する関数分解を用いて実現する場合について説明する。ADR2の入出力の関係は式(17)のように定義できる。これより、s,s,sは、それぞれ式(18)により表される。また、真理値表は図6(a)により表される。
【0086】
【数17】
JP0004562136B2_000022t.gif

【0087】
【数18】
JP0004562136B2_000023t.gif

【0088】
変数の分割として、X=(a,b),Y=(s),X=(a,b),Y=(s,s)とおく。このとき、変数順序は、(X,Y,X,Y)=(a,b,s,a,b,s,s)となる。従って、ADR2の特性関数二分決定グラフは、図6(b)により表される。Z=(Z,Z),Z=(X,Y),Z=(X,Y)のように分割し、Zを図3の回路H、Zを図3の回路Gにより構成する。このとき、高さ|Z|での特性関数二分決定グラフの幅Wは2となる。従って、回路Hと回路Gとを連結する線は、式(15)より、1本あればよい。出力sは、Xのみの関数として表現することが可能である。
【0089】
また、変数組Zにより構成される特性関数二分決定グラフは、図7(a)のようになる。これは、図6の特性関数二分決定グラフの分割線よりも根節点側(上側)の部分を切り取ったものである。尚、図7(a)では特性関数値0につながる枝は省略してある。回路Hと回路Gとを連結する線は1本なので、図7(a)のグラフの終端節点には、1ビットの中間変数hを導入して、各終端節点に割り当てる。なお、変数hへの符号の割り当ては任意である。この特性関数二分決定グラフは、容易に多端子二分決定グラフ(MTBDD)に変換することができる。図7(a)のグラフを変換することにより得られるMTBDDは、図7(b)のようになる。図7(b)のMTBDDから回路Hに相当するLUTを図7(c)のように生成することができる。
【0090】
次に、図6の特性関数二分決定グラフについて、先に導入した新しい中間変数hを用いて、図6(b)に示した特性関数二分決定グラフの分割線よりも上部を、hを入力変数とする決定木(decision tree)で置き換える。これにより、特性関数二分決定グラフは図8(a)のように変形される。尚、図8(a)でも特性関数値0につながる枝は必要ないので省略してある。この特性関数二分決定グラフは、容易にMTBDDに変換することができる。図8(a)のグラフを変換することにより得られるMTBDDは、図8(b)のようになる。更に、図8(b)のMTBDDから回路Gに相当するLUTを図9(a)のように生成することができる。従って、結局、図9(b)に示したようなLUTカスケードを構成することができる。
〔例終わり〕
【0091】
〔3〕本発明の構成及び作用
本発明に係るグラフ幅削減装置の第1の構成は、入力変数をX=(x,…,x)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(19)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフの幅を削減するグラフ幅削減装置であって、以下の構成を備えていることを特徴とする:
多出力論理関数F(X)の特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルを記憶する節点テーブル記憶手段;
前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定手段;
前記節点データ記憶手段に記憶された前記節点テーブルから、前記特性関数二分決定グラフを前記分割線設定手段により設定された前記分割の高さlevで分割し関数分解することによって得られる分解表の列を表す関数である列関数を生成する列関数生成手段;
及び、前記列関数生成手段が生成する各列関数のうち、両立する列関数に対してドント・ケアに定数を割り当てることによって同一の列関数(以下「割当列関数(assigned column function)」という。)とするとともに、これらの新たな割当列関数を用いて前記特性関数二分決定グラフ再構成し前記節点テーブル記憶手段の節点テーブルを更新する割当BDD再構成手段。
【0092】
【数19】
JP0004562136B2_000024t.gif
但し、fi_0,fi_1,fi_dは、それぞれ、式(20)で定義されるOFF関数、ON関数、及びDC関数を表す。
【0093】
【数20】
JP0004562136B2_000025t.gif

【0094】
この構成により、分割線設定手段が分割の高さlevを設定すると、列関数生成手段が特性関数二分決定グラフを分割の高さlevで分割し関数分解することによって得られる列関数を生成する。そして、割当BDD再構成手段は、各列関数のうち、両立する列関数に対してドント・ケアに定数を割り当てることによって同一の割当列関数とする。それとともに、これらの新たな割当列関数を用いて特性関数二分決定グラフ再構成し節点テーブル記憶手段の節点テーブルを更新する。これにより、分割の高さlevにおける特性関数二分決定グラフの幅が削減される。
【0095】
一般に、二分決定グラフを用いて関数分解を行う場合、二分決定グラフの幅が小さいほど、関数分解後の論理回路も小さくなる。従って、上述のようなドント・ケアへの定数の割り当てを実行することによって、二分決定グラフの幅を削減し、関数分解後の論理回路を小さくすることができる。
【0096】
本発明に係るグラフ幅削減装置の第2の構成は、前記第1の構成において、
前記列関数を節点(以下「関数節点」という。)とするグラフであって、互いに両立する複数の列関数に対応する関数節点同士が枝(以下「両立枝」という。)により連結されたグラフである両立グラフを、前記各関数節点の列関数ラベル及び当該関数節点に連結する両立枝のデータ(以下「関数節点データ」という。)のテーブルとして記憶するための両立グラフ記憶手段;
前記両立グラフ記憶手段に記憶された前記各関数節点データに対する列関数から、両立する列関数の組を選出し、それら両立する列関数に対する関数節点データにそれらの関数節点同士を連結する両立枝を追加して前記両立グラフ記憶手段に記憶された関数節点データの更新を行う両立枝生成手段;
及び、前記両立グラフのすべての節点について、完全部分グラフ(以下「クリーク」という。)による節点被覆を行うことにより、クリークに含まれる関数節点集合であるクリーク・データを生成するクリーク生成手段;
を備え、
前記列関数生成手段は、前記節点データ記憶手段に記憶された前記節点テーブルから、前記分割線設定手段により設定された前記分割の高さlevの節点の各枝に対応する列関数を生成し、それら各列関数に対応した列関数ラベルを有する前記関数節点データを生成して前記両立グラフ記憶手段に保存するものであり、
前記割当BDD再構成手段は、前記クリーク生成手段が生成する前記各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数とすることにより、前記特性関数二分決定グラフを再構成し前記節点テーブル記憶手段の前記節点テーブルを更新するものであることを特徴とする。
【0097】
この構成によれば、列関数生成手段が、節点データ記憶手段に記憶された節点テーブルから、分割の高さlevの節点の各枝に対応する列関数を生成する。そして、それら各列関数に対応した列関数ラベルを有する前記関数節点データを生成して前記両立グラフ記憶手段に保存する。両立枝生成手段は、両立グラフ記憶手段に記憶された各関数節点データに対する列関数から、両立する列関数の組を選出する。そして、選出された両立する列関数に対する関数節点データに、それらの関数節点同士を連結する両立枝を追加して関数節点データの更新を行う。次に、クリーク生成手段は、両立グラフのすべての節点について、最小数のクリークによる節点被覆を行い、クリーク・データを生成する。最後に、割当BDD再構成手段は、各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数とする。そして、割当列関数により、特性関数二分決定グラフを再構成し、節点テーブルを更新する。
【0098】
以上のようにして、上述のアルゴリズム3の(1)~(5)を実行し、列関数の両立グラフのクリーク被覆による特性関数二分決定グラフの幅の削減を行うことができる。本発明によれば、特性関数二分決定グラフの幅を構成するすべての部分関数の両立性を、両立グラフを用いて全体的に評価して、ドント・ケアへの定数の割り当てを行うことができるため、極めて効果的に特性関数二分決定グラフの幅を削減することが可能となる。
【0099】
ここで、クリーク生成手段は、クリークを生成する場合に、両立グラフのすべての節点について、最小数のクリークにより節点被覆を行うことが望ましい。しかしながら、前述したように、最小数のクリークによる節点被覆問題はNP困難であり実用的ではない。従って、実際にはクリーク生成手段は、発見的方法によってできるだけ少ないクリーク数で節点被覆を行うことができるようにクリークを生成するように構成するのがよい。
【0100】
本発明に係るグラフ幅削減装置の第3の構成は、前記第1又は第2の構成において、前記分割線設定手段は、前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフの根節点の子の節点の高さから下位に向かって順次分割の高さlevの設定を行うものであり、前記割当BDD再構成手段は、前記分割線設定手段が設定する前記各分割の高さlevにおいて逐次前記特性関数二分決定グラフ再構成を行うことを特徴とする。
【0101】
この構成によれば、特性関数二分決定グラフの根節点の高さtの子節点の高さt-1から定数節点の上の節点の高さ1まで、上述したアルゴリズム3による特性関数二分決定グラフの幅の削減を行うことができる。従って、多出力論理関数のすべてのサポート変数に対して効果的に特性関数二分決定グラフの幅を削減することが可能となる。
【0102】
本発明に係る論理回路合成装置の第1の構成は、入力変数をX=(x,…,x)(n∈自然数)とする多出力論理関数F(X)=(f(X),…,fm-1(X))の特性関数二分決定グラフから、前記多出力論理関数F(X)に対応する論理回路を構成するためのデータであるルックアップ・テーブルを生成する論理回路合成装置であって、以下の構成を備えていることを特徴とする:
完全定義関数である前記多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(21)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段;
前記ルックアップ・テーブルを記憶するLUT記憶手段;
前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定手段;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB,Bに分割したときに根節点を含む側の部分グラフBに属するものであって、出力を表す変数y(∈Y)に関わる節点v及びその親節点vの節点データについて、当該節点vの枝e(v),e(v)の一方e(v)がx(X,Y)=0に関わる終端節点を特定する場合、当該節点vの親節点vの枝e(v),e(v)のうち当該節点vを特定する枝e(v)を、当該節点vの前記枝e(v)以外の枝e(v)に置き換える短絡除去処理を行う短絡除去手段;
前記短絡除去手段により短絡除去処理がされた特性関数二分決定グラフの各非終端節点であって前記分割の高さlevより高い高さにある非終端節点に属する枝のうち、前記分割の高さlevより低い高さの非終端節点の子節点を特定するものの個数を計数し(但し、同じ節点を特定するものは1つと数え、定数0に向かう枝は無視する。)、その個数を前記分割の高さlevの分割線における幅Wとして出力するBDD幅計測手段;
前記BDD幅計測手段が出力する幅Wに基づき、式(22)の演算により中間変数の個数uを算出する中間変数算出手段;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB,Bに分割したときに根節点を含む側の部分グラフBに属するものについて、ルックアップ・テーブルを生成しそれをLUT記憶手段に格納するLUT生成手段;
及び、前記中間変数算出手段が算出する前記中間変数の個数uと等しい制御入力数を有する二分木(binary tree)を生成するとともに、前記節点テーブル記憶手段に格納されている特性関数二分決定グラフの部分グラフBに属する非終端節点の節点データを、前記二分木を表す節点データで置き換えることにより、特性関数二分決定グラフを再構成し、この再構成された特性関数二分決定グラフの各非終端節点の節点データにより前記節点テーブル記憶手段に格納された節点テーブルを更新するBDD再構成手段。
【0103】
【数21】
JP0004562136B2_000026t.gif

【0104】
【数22】
JP0004562136B2_000027t.gif

【0105】
この構成によれば、
(a)まず、論理回路合成を行う目的論理関数の特性関数二分決定グラフの節点データを節点テーブル記憶手段に格納しておく。短絡除去手段は、節点テーブル記憶手段に格納された節点データで構成される特性関数二分決定グラフについて、所定の高さlevの分割線に対して根節点を含む側の部分グラフBについて短絡除去処理を行う。短絡除去処理については、上記「〔2〕本発明の基本的原理」の欄において説明した通りである。BDD幅計測手段は、上記短絡除去処理が行われた結果得られる特性関数二分決定グラフについて、上記分割線における幅Wを計測する。そして、中間変数算出手段は、式(22)によって中間変数の個数uを算出する。
【0106】
(b)次に、LUT生成手段は、節点テーブル記憶手段に格納された節点データで構成される特性関数二分決定グラフについて、所定の高さlevの分割線に対して根節点を含む側の部分グラフBについて、ルックアップ・テーブルを生成する。この生成方法の原理については、上記「〔1〕本発明の基本的原理」の欄において説明した通りである。このLUTの出力は、部分グラフBに属する出力変数Y=(y,…,yk-1)及びu個の中間変数H=(h,…,h)となる。生成されたルックアップ・テーブルは、LUT記憶手段に格納される。中間変数Hの節点に対しては、適当な符号を割り当てることができる。
【0107】
(c)最後に、BDD再構成手段は、u個の制御入力数を有する二分木を生成し、各制御入力数に対して上記中間変数H=(h,…,h)を対応させる。そして、BDD再構成手段は、この処理により再構成された特性関数二分決定グラフの各節点の節点データを節点テーブル記憶手段に格納し、節点テーブル記憶手段が保持する特性関数二分決定グラフを更新する。
【0108】
以上のような(a)~(c)の処理を繰り返せば、目的論理関数は複数の部分関数に関数分解され、LUTカスケード論理回路が構成される。また、LUT生成手段により生成されるルックアップ・テーブルを特性関数二分決定グラフにして、更に同様の処理によって関数分解を行うことによって、LUTネットワーク論理回路が構成される。
【0109】
本構成による論理回路合成装置では、分割線の位置を、部分グラフBの大きさが過度に大きくならないように適度な高さに決めることで、部分グラフBに関する変数を束縛変数とした分解表の列複雑度が極度に増大することを防止することが可能である。従って、比較的少容量のメモリを用いて論理回路合成装置を実現することが可能である。また、部分グラフBに関する変数を束縛変数とした分解表の列複雑度を抑えることができるため、計算処理量やメモリ・アクセス回数を少なくすることが可能であり、論理関数分解処理の演算処理速度を高速化することができる。
【0110】
尚、短絡除去手段による短絡除去処理において、実際に節点テーブルの構造自体を書き換えることによって短絡除去処理を行ってもよいが、節点テーブルのデータ構造は変化させず、特性関数に分決定グラフを解釈するプログラムにおいて或る節点に短絡処理がなされたものとみなすようにすることもできる。例えば、短絡処理がなされた出力変数の節点については節点ラベルを特定の値に書き換える。そうすることにより、節点ラベルを調べることで、その変数が出力か否かが判定できるようにして、事実上短絡処理がなされたと見なすことができるようにすることができる。
【0111】
本発明に係る論理回路合成装置の第2の構成は、前記第1の構成において、前記節点テーブル記憶手段には、出力にドント・ケアを含む不完全定義関数である前記多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(19)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルとして記憶されていることを特徴とする。
【0112】
この構成により、不完全定義多出力関数についても、完全定義多出力関数と同様、LUTカスケード論理回路やLUTネットワーク論理回路を構成することが可能となる。
【0113】
本発明に係る論理回路合成装置の第2の構成は、前記第2の構成において、前記第1乃至3の何れか一の構成のグラフ幅削減装置を備え、前記短絡除去手段は、前記グラフ幅削減装置によって前記節点テーブル記憶手段に記憶された前記節点テーブルにより表される特性関数二分決定グラフの幅を削減し更新された前記節点テーブルについて短絡除去処理を行うものであることを特徴とする。
【0114】
この構成により、不完全定義関数の特性関数二分決定グラフの幅を削減した上でLUTカスケードの合成を行うため、不完全定義多出力関数の冗長性を削減して、LUTカスケードのメモリ使用効率を改善することができる。
【0115】
本発明に係る論理回路合成装置の第4の構成は、前記第1乃至3の何れか一の構成において、
前記多出力論理関数F(X)の要素をなす論理関数f(X),…,fm-1(X)の順序をπ=(π[0],…,π[m-1])(但し、π[i]=jは、fがi番目であることを表す。)とし、論理関数f(∈F(X))が依存する入力変数の集合をsupp(f)としたとき、式(23)で表されるTの値が最小となるように前記多出力論理関数F(X)の要素の順序πを決定する出力変数順序決定手段;
前記各入力変数x(∈X)及び出力を表す変数y(∈Y)の順序を、式(24)を満たす順序Pに決定する全変数順序決定手段;
及び、前記全変数順序決定手段で決定された順序Pに従って、特性関数二分決定グラフの節点データを生成し前記節点テーブル記憶手段に格納するBDD生成手段;
を備えていることを特徴とする。
【0116】
【数23】
JP0004562136B2_000028t.gif

【0117】
【数24】
JP0004562136B2_000029t.gif

【0118】
実用的な多出力論理関数の特性関数二分決定グラフは、通常はかなりの大きさとなる。そのため、出力を分割する方法が必要である。そこで、上記構成によれば、出力変数順序決定手段が、論理関数f(X),…,fm-1(X)の順序を式(23)で表されるTの値が最小となるように決定することにより、BDD生成手段が生成する特性関数二分決定グラフの節点データの数を削減できる。特性関数二分決定グラフにおいて、各出力変数y=f(X)に対して、その出力変数が依存する入力変数が、その出力変数yよりも上位に置かれるため、依存変数がなるべく増えないような順序に並べられ、一つずつ出力を増やしながら特性関数二分決定グラフが作られる。このようにして、出力を最適に分割する。このとき、特性関数二分決定グラフの節点データの数が削減できるので、その後の論理回路合成に要する処理時間が短縮され、高速な論理回路合成が可能となる。
【0119】
本発明に係るグラフ幅削減方法の第1の構成は、入力変数をX=(x,…,x)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(19)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段を備えたシステムにおいて、当該特性関数二分決定グラフの幅を削減するグラフ幅削減方法であって、以下の各ステップを有することを特徴とする:
前記節点テーブルによって表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定ステップ;
前記節点データ記憶手段に記憶された前記節点テーブルから、前記特性関数二分決定グラフを前記分割線設定ステップで設定された前記分割の高さlevで分割し関数分解することによって得られる分解表の列を表す関数である列関数を生成する列関数生成ステップ;
及び、前記列関数生成ステップにおいて生成される各列関数のうち、両立する列関数に対してドント・ケアに定数を割り当てることによって同一の列関数(以下「割当列関数」という。)にするとともに、これらの新たな割当列関数を用いて前記特性関数二分決定グラフ再構成し前記節点テーブル記憶手段の節点テーブルを更新する割当BDD再構成ステップ。
【0120】
本発明に係るグラフ幅削減方法の第2の構成は、前記第1の構成において、前記システムは、前記列関数を節点(以下「関数節点」という。)とするグラフであって、互いに両立する複数の列関数に対応する関数節点同士が枝(以下「両立枝」という。)により連結されたグラフである両立グラフを、前記各関数節点の列関数ラベル及び当該関数節点に連結する両立枝のデータ(以下「関数節点データ」という。)のテーブルとして記憶するための両立グラフ記憶手段を備えており、
前記列関数生成ステップにおいては、前記節点データ記憶手段に記憶された前記節点テーブルから、前記分割線設定ステップで設定された前記分割の高さlevの節点の各枝に対応する列関数を生成し、それら各列関数に対応した列関数ラベルを有する前記関数節点データを生成して前記両立グラフ記憶手段に保存するとともに、
前記両立グラフ記憶手段に記憶された前記各関数節点データに対する列関数から、両立する列関数の組を選出し、それら両立する列関数に対する関数節点データにそれらの関数節点同士を連結する両立枝を追加して前記両立グラフ記憶手段に記憶された関数節点データの更新を行う両立枝生成ステップ;
及び、前記両立グラフのすべての節点について、完全部分グラフ(以下「クリーク」という。)による節点被覆を行うことにより、クリークに含まれる関数節点集合であるクリーク・データを生成するクリーク生成ステップ;
を有し、
前記割当BDD再構成ステップにおいては、前記クリーク生成ステップにおいて生成される前記各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数とすることにより、前記特性関数二分決定グラフを再構成し前記節点テーブル記憶手段の前記節点テーブルを更新することを特徴とする。
【0121】
本発明に係るグラフ幅削減方法の第3の構成は、前記第1又は第2の構成において、前記分割線設定ステップにおける前記分割の高さlevを、前記節点テーブル記憶手段に記憶された前記節点テーブルにより表現される特性関数二分決定グラフの根節点の子の節点の高さから最下位の高さまで順次変更しながら、前記分割線設定ステップ乃至前記割当BDD再構成ステップを実行することを特徴とする。
【0122】
本発明に係る論理回路合成方法の第1の構成は、入力変数をX=(x,…,x)(n∈自然数)とする完全定義関数である多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(21)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルとして記憶された節点テーブル記憶手段;
及び、ルックアップ・テーブルを記憶するためのLUT記憶手段;
を備えたシステムにおいて、前記特性関数二分決定グラフから、前記多出力論理関数F(X)に対応する論理回路を構成するためのデータであるルックアップ・テーブルを合成する論理回路合成方法であって、以下のステップを有することを特徴とする:
前記節点テーブルにより表現される特性関数二分決定グラフを分割する高さ(以下「分割の高さ」という。)levの設定を行う分割線設定ステップ;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB,Bに分割したときに根節点を含む側の部分グラフBに属するものであって、出力を表す変数y(∈Y)に関わる節点v及びその親節点vの節点データについて、当該節点vの枝e(v),e(v)の一方e(v)がx(X,Y)=0に関わる終端節点を特定する場合、当該節点vの親節点vの枝e(v),e(v)のうち当該節点vを特定する枝e(v)を、当該節点vの前記枝e(v)以外の枝e(v)に置き換える短絡除去処理を実行する短絡除去ステップ;
前記短絡除去処理がされた特性関数二分決定グラフの各非終端節点であって前記分割の高さlevより高い高さにある非終端節点に属する枝のうち、前記分割の高さlevより低い高さの非終端節点の子節点を特定するものの個数を計数し(但し、同じ節点を特定するものは1つと数え、定数0に向かう枝は無視する。)、その個数を前記分割の高さlevの分割線における幅Wとして出力するBDD幅計測ステップ;
前記幅Wに基づき、式(22)の演算により中間変数の個数uを算出する中間変数算出ステップ;
前記節点テーブル記憶手段に格納された非終端節点の節点データのうち、前記特性関数二分決定グラフを前記分割の高さlevの分割線において2つの部分グラフB,Bに分割したときに根節点を含む側の部分グラフBに属するものについて、ルックアップ・テーブルを生成しそれをLUT記憶手段に格納するLUT生成ステップ;
及び、前記中間変数算出ステップにおいて算出された前記中間変数の個数uと等しい制御入力数を有する二分木を生成するとともに、前記節点テーブル記憶手段に格納されている特性関数二分決定グラフの部分グラフBに属する非終端節点の節点データを、前記二分木を表す節点データで置き換えることにより、特性関数二分決定グラフを再構成し、この再構成された特性関数二分決定グラフの各非終端節点の節点データにより前記節点テーブル記憶手段に格納された節点テーブルを更新するBDD再構成ステップ。
【0123】
本発明に係る論理回路合成方法の第2の構成は、前記第1の構成において、前記節点テーブル記憶手段には、入力変数をX=(x,…,x)(n∈自然数)とし出力にドント・ケアを含む不完全定義関数である多出力論理関数F(X)=(f(X),…,fm-1(X))に対して式(19)により定義される特性関数x(X,Y)(但し、Y=(y,…,ym-1)(m≧2,m∈自然数)はF(X)の出力を表す変数。)を表現する特性関数二分決定グラフが、当該特性関数二分決定グラフのそれぞれの非終端節点vについて、当該非終端節点に関わる変数z(z∈(X∪Y))に付与される変数ラベル並びに当該変数z(z∈(X∪Y))の値が0のとき及び1のときに遷移する先の子節点を特定する一対の枝e(v),e(v)からなる節点データのテーブルである節点テーブルとして記憶されていることを特徴とする。
【0124】
本発明に係る論理回路合成方法の第3の構成は、前記第2の構成において、前記節点テーブル記憶手段に記憶された前記節点テーブルにより表される特性関数二分決定グラフの幅を、前記第1乃至3の何れかの構成のグラフ幅削減方法によって削減し、前記節点テーブル記憶手段に記憶された前記節点テーブルを更新した後に、前記分割線設定ステップ乃至前記BDD再構成ステップを実行することを特徴とする。
【0125】
本発明に係る論理回路合成方法の第4の構成は、前記第1乃至3の何れか一の構成において、前記多出力論理関数F(X)の要素をなす論理関数f(X),…,fm-1(X)の順序をπ=(π[0],…,π[m-1])(但し、π[i]=jは、fがi番目であることを表す。)とし、論理関数f(∈F(X))が依存する入力変数の集合をsupp(f)としたとき、式(23)で表されるTの値が最小となるように前記多出力論理関数F(X)の要素の順序πを決定する出力変数順序決定ステップ;
前記各入力変数x(∈X)及び出力を表す変数y(∈Y)の順序を、式(24)を満たす順序Pに決定する全変数順序決定ステップ;
及び、前記順序Pに従って、特性関数二分決定グラフの節点データを生成し前記節点テーブル記憶手段に格納するBDD生成ステップ;
を実行した後に、前記分割線設定ステップ乃至前記BDD再構成ステップを実行することを特徴とする。
【0126】
本発明に係るプログラムの第1の構成は、コンピュータに第1乃至3の何れかの構成のグラフ幅削減方法を実行させることを特徴とする。
【0127】
本発明に係るプログラムの第2の構成は、コンピュータに第1乃至4の何れかの構成の論理回路合成方法を実行させることを特徴とする。
【0128】
本発明に係るプログラマブル論理回路の構成は、第1乃至4の何れかの構成の論理回路合成方法により論理合成されたことを特徴とする。
【発明の効果】
【0129】
以上のように、本発明に係るグラフ幅削減装置及びグラフ幅削減方法によれば、特性関数二分決定グラフの幅を構成するすべての部分関数の両立性を調べてマッチングを行うことができるため、効果的に特性関数二分決定グラフの幅を削減することが可能となる。
また、本発明に係る論理回路合成装置及び論理回路合成方法によれば、特性関数二分決定グラフを分割する分割線の位置を、部分グラフBの大きさが過度に大きくならないように適度な高さに決めることで、部分グラフBに関する変数を束縛変数とする分解表の列複雑度が極度に増大するのを防止することが可能となる。その結果、比較的小容量のメモリを用いて論理回路合成を実現でき、また、論理関数分解処理の演算処理速度を高速化することができる。従って、現在まで有効な論理回路合成手段が知られていなかった、多出力論理関数の分解によるLUT論理回路の生成を、現実的なハードウェアを使用して短時間で実行することが可能となる。また、本発明は、任意の多出力論理関数のLUT論理回路生成に対して汎用的に適用可能である。
【図面の簡単な説明】
【0130】
【図1】特性関数二分決定グラフの一例を示す図である。
【図2】出力変数の短絡除去を説明するための図である。
【図3】多出力論理関数を2つの関数に関数分解した場合の論理回路の構成を表す図である。
【図4】表4の不完全定義関数の特性関数二分決定グラフに対してアルゴリズム1による幅の削減を行う例を表す図である。
【図5】短絡除去を行った後の特性関数二分決定グラフの構成を表す図である。
【図6】ADR2の特性関数二分決定グラフを表す図である。
【図7】ADR2の特性関数二分決定グラフを分割したときの根節点側の部分グラフをLUTに変換する処理を説明するための図である。
【図8】ADR2の特性関数二分決定グラフを短絡除去し、LUTに変換する処理を説明するための図である。
【図9】ADR2の特性関数二分決定グラフを短絡除去し、LUTに変換する処理を説明するための図である。
【図10】本発明の実施例1に係る論理回路合成装置及びその周辺装置の構成を表す図である。
【図11】実施例1における論理回路合成方法の全体の流れを示すフローチャートである。
【図12】変数順序の決定処理の流れを表すフローチャートである。
【図13】節点テーブルのデータ構造を表す図である。
【図14】式(31)の既約な特性関数二分決定グラフ及びその節点テーブルを表す図である。
【図15】式(31)の特性関数二分決定グラフ及びその節点テーブルを表す図である。
【図16】LUTカスケード論理回路の合成処理の流れを表すフローチャートである。
【図17】本発明の論理回路合成方法によるLUTカスケード論理回路の合成についての実験結果を示す図である。
【図18】本発明の実施例2に係る論理回路合成装置及びその周辺装置の構成を表す図である。
【図19】図18のグラフ幅削減装置20の構成を表す図である。
【図20】グラフ幅削減装置20のグラフ幅削減処理の全体の流れを表すフローチャートである。
【図21】クリーク集合による両立グラフの節点被覆処理の流れを表すフローチャートである。
【図22】例10の不完全定義関数の特性関数二分決定グラフの幅削減処理を説明する図である。
【図23】例10の不完全定義関数の特性関数二分決定グラフの幅削減処理を説明する図である。
【図24】例10の不完全定義関数の特性関数二分決定グラフの幅削減処理を説明する図である。
【図25】ベンチマーク関数5-7-11-13 RNSについてLUTカスケード論理回路の合成を行った結果を比較する図である。
【符号の説明】
【0131】
1,1’ 論理回路合成装置
2 論理仕様記憶手段
3 入力装置
4 出力装置
5 出力変数順序決定手段
6 全変数順序決定手段
7 BDD生成手段
8 節点テーブル記憶手段
9 変数順序最適化手段
10 分割線設定手段
11 短絡除去手段
12 BDD幅計測手段
13 中間変数算出手段
14 LUT生成手段
15 BDD再構成手段
16 LUT記憶手段
20 グラフ幅削減装置
21 BDD高さ計測手段
22 分割線設定手段
23 列関数生成手段
24 列関数記憶手段
25 両立枝生成手段
26 両立グラフ記憶手段
27 クリーク生成手段
28 クリーク・データ記憶手段
29 割当BDD再構成手段
【発明を実施するための最良の形態】
【0132】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0133】
図10は本発明の実施例1に係る論理回路合成装置及びその周辺装置の構成を表す図である。実施例1に係る論理回路合成装置1は、論理仕様記憶手段2に格納された論理回路の論理仕様から、LUT論理回路を合成し、出力装置4に出力する。論理仕様記憶手段2には、入力装置3により、目的論理関数がネットリストなど論理仕様データとして格納される。
【0134】
尚、本実施例においては、論理回路設計用のCAD装置において論理回路合成装置1を使用する場合を想定している。論理回路合成装置1は、プログラム形態として提供され、そのプログラムをコンピュータに読み込んで実行することによって、図10に示したような論理回路合成装置1の機能構成がコンピュータで実現される。尚、図10において、入力装置3は、キーボード、マウス、CD-ROMドライブ等の各種データ入力装置を表している。出力装置4は、ディスプレイ、プリンタ、磁気記録装置等の各種データ出力装置を表している。また、出力装置4として、プログラマブル論理回路に生成されたLUT論理回路を直接書き込むためのプログラム書込装置を使用することもできる。
【0135】
論理回路合成装置1は、出力変数順序決定手段5、全変数順序決定手段6、BDD生成手段7、節点テーブル記憶手段8、変数順序最適化手段9、分割線設定手段10、短絡除去手段11、BDD幅計測手段12、中間変数算出手段13、LUT生成手段14、BDD再構成手段15、及びLUT記憶手段16を備えた構成からなる。
【0136】
出力変数順序決定手段5は、多出力論理関数f(X)の要素の順序π=(π[0],…,π[m-1])を決定する。全変数順序決定手段6は、各入力変数x(∈X)及び出力を表す変数y(∈Y)の順序を、所定の順序Pに決定する。BDD生成手段7は、全変数順序決定手段6で決定された順序Pに従って、特性関数二分決定グラフの節点テーブルを生成する。生成された節点テーブルは、節点テーブル記憶手段8に格納される。変数順序最適化手段9は、節点テーブル記憶手段8に格納された節点テーブルの変数順序を更に最適化する。
【0137】
分割線設定手段10は、節点テーブル記憶手段8に格納された特性関数二分決定グラフの節点データに対して、当該特性関数二分決定グラフを分割する分割線の高さlevの決定を行う。短絡除去手段11は、節点テーブル記憶手段8に格納された特性関数二分決定グラフに対し、高さlevの分割線より上の部分グラフの短絡除去処理を行う。BDD幅計測手段12は、短絡除去処理がされた特性関数二分決定グラフの分割線における幅Wとして出力する。中間変数算出手段13は、BDD幅計測手段12が出力する幅Wに基づき中間変数の個数uを算出する。LUT生成手段14は、分割線において2つの部分グラフB,Bに分割したときの根節点を含む側の部分グラフBに属するものについて、LUTを生成しそれをLUT記憶手段16に格納する。BDD再構成手段15は、部分グラフBを中間変数の個数uと等しい制御入力数を有する二分木に置き換えて、特性関数二分決定グラフを再構成し、節点テーブル記憶手段8を更新する。
【0138】
以上のように構成された本実施例に係る論理回路合成装置1について、以下その動作を説明する。
【0139】
図11は実施例1における論理回路合成方法の全体の流れを示すフローチャートである。全体的な処理の流れでは、最初に、出力変数順序決定手段5と全変数順序決定手段6が、論理仕様記憶手段2に格納された論理仕様を読み出す。そして、読み出された論理仕様から、入力変数Xと出力変数Yとを抽出し、これら各変数の初期順序の決定を行う(S1)。次に、BDD生成手段7は、論理仕様記憶手段2から論理仕様データを読み出し、上記決定された変数の初期順序に従って特性関数二分決定グラフの節点テーブルを生成する。生成された節点テーブルは、節点テーブル記憶手段8に格納される(S2)。次に、変数順序最適化手段9は、節点テーブル記憶手段8に格納された節点テーブルにおいて、特性関数二分決定グラフの幅の総和がより小さくなるように、更に変数順序の入れ替えを行い、変数順序を最適化する(S3)。このとき、変数順序の入れ替えは、出力変数の順序集合Y=(y,y,…,ym-1)における出力変数y(j=0,1,…,m-1)に対して、その出力変数yが依存する入力変数x(∈supp(f))は、出力変数yよりも常に高位であるという条件のもとで、変数の入れ替えが行われる。最後に、節点テーブル記憶手段8に格納された特性関数二分決定グラフの節点テーブルに基づいて、LUT論理回路の合成が行われる(S4)。以下、上記各段階での処理について詳述する。
【0140】
(1)変数X,Yの初期順序の決定
図12は変数順序の決定処理の流れを表すフローチャートである。まず、出力変数順序決定手段5は、内部変数i,j,renewを0に初期化する(S10)。i,jは置換する変数のインデックスを表す内部変数であり、renewは順序の置換が行われたことを検出するための更新フラグである。また、出力変数順序決定手段5は、出力変数Yの変数順序を表すm個の要素を持つ順序π=(π[0],π[1],…,π[m-1])を(0,1,…,m-1)に初期化する(S2)。順序πは、出力変数Yの変数順序を表す配列である。出力変数の順序は、順序πにより、式(25)のように順序づけされる。
【0141】
【数25】
JP0004562136B2_000030t.gif

【0142】
次に、出力変数順序決定手段5は、式(26)の演算を行うことにより、順序πに対する出力変数順序評価関数を算出し、これを変数Tminに格納する(S12)。ここで、出力変数順序評価関数とは、式(26)の右辺の関数である。この出力変数順序評価関数は、各出力変数Yの順序πが、依存変数の数の少ない順に出力変数Yを順序づけするものであるときに最小となる。従って、出力変数順序評価関数を最小化することにより、出力変数Yの順序は最適化されることとなる。また、supp(f)は、論理関数f(∈f(X))が依存する入力変数の集合を表す。例えば、f=f(x,x,x,x10)であれば、|supp(f)|=4である。また、|supp(f)|はsupp(f)の変数の個数である(〔定義4〕参照)。
【0143】
【数26】
JP0004562136B2_000031t.gif

【0144】
次に、出力変数順序決定手段5は、i≠jであるかどうかを判定する(S13)。i=jの場合には、ステップS19に行く。これは、i=jの場合には置換が行われないので、i=jの場合を除外する必要があるからである。
【0145】
ステップS13において、i≠jであれば、まず、変数置換後の順序πを初期順序πに初期化した後(S14)、順序πの要素π[i]と要素π[j]との置換を行う(S15)。そして、出力変数順序決定手段5は、式(27)の演算を行うことにより、順序πに対する出力変数順序評価関数Tを算出する(S16)。
【0146】
【数27】
JP0004562136B2_000032t.gif

【0147】
ここで、置換後の出力変数順序評価関数Tが置換前の出力変数順序評価関数Tminよりも小さい(T<Tmin)場合には(S17)、順序πのほうが出力変数の順序としてはより適当であると判断されるため、出力変数順序決定手段5は、順序πをπに更新し、TminをTとする。そして、順序πの更新がされたことを表す更新フラグrenewを1とする(S18)。
【0148】
次に、j<m-1であれば(S19)、jを1だけインクリメントして(S20)、ステップS13に戻り、上記出力変数の順序の最適化処理を繰り返す。
【0149】
ステップS18でj=m-1ならば、i番目の出力変数の順序を固定したときの順序の入れ替えに対する評価がすべて終了したことになるので、jを0に初期化する(S21)。
【0150】
次に、i<m-1であれば(S22)、次の出力変数の順序を固定したときの順序の入れ替えに対する評価を行うべく、iを1だけインクリメントして(S23)、ステップS13に戻る。
【0151】
ステップS22において、i=m-1の場合、i番目の出力変数の順序を固定した場合についての評価は一通り終了したことになる。但し、順序入れ替えの総数は、m!通りであるが、この段階では、順序入れ替えの評価はm×(m-1)通りしか行われていない。そこで、残りの場合についても評価するかどうかを判断するため、上記m×(m-1)通りの評価において順序πの更新が行われたかどうかを判定する。すなわち、変数renewが1であるかどうかを参照する(S24)。ここで、renew=1であれば、iを0、renewを0に初期化して(S25)、再びステップS13の処理に戻る。尚、ステップS24でrenew=0であれば、終了する。
【0152】
以上のようにして、出力変数Yの順序πは、出力変数順序評価関数Tminの値が極小化する順序に最適化される。出力変数順序決定手段5は、出力変数Yの順序を順序πに並べ替えて出力する。
【0153】
尚、上記処理では、順序入れ替えの評価は必ずしもm!回行われないので、必ずしも出力変数順序評価関数Tminの値が最小となるように最適化されるとは限らないことに注意しておく。m!回のすべてについての評価を行わないこととしたのは、処理時間を短縮するためである。しかしながら、上記変数並べ替えのアルゴリズムは一例であり、計算処理速度が十分速い場合や、出力変数及び入力変数の数が比較的少ない場合には、m!回のすべてについて総当たりで評価を行うことにより、出力変数順序評価関数Tminの値が最小となるように最適化してもよい。
【0154】
出力変数の順序が決定された後、全変数順序決定手段6は、入力変数X及び出力変数Yの順序を式(28)の順序Pに従って決定する。
【0155】
【数28】
JP0004562136B2_000033t.gif
ここで、式(28)の条件を満たす限りにおいては、入力変数Xの順序の決め方は任意である。したがって、ここでは、出力変数
【0156】
【数29】
JP0004562136B2_000034t.gif
の前にある入力変数の集合
【0157】
【数30】
JP0004562136B2_000035t.gif
の要素間の順序については、xのインデックスiが小さい順に順序づけることとする。尚、式(30)において(θ[1],θ[2],…,θ[p],θ[p+1]…,θ[p+q-1],…,θ[n])は、入力変数Xの順序を表し、θ[k]=iの場合、xは入力変数のk番目に位置することを表す。
【0158】
(2)特性関数二分決定グラフの節点テーブルの作成
変数X,Yの初期順序Pの決定がされた後、BDD生成手段7は、決定された初期順序Pに従って、論理仕様記憶手段2に記憶された論理仕様に従って、特性関数二分決定グラフの節点テーブルを生成する。この節点テーブルは、節点テーブル記憶手段8に格納される。尚、論理仕様から特性関数二分決定グラフを生成するアルゴリズムに関しては、すでに種々のアルゴリズムが公知であるため、ここでは説明を省略する。
【0159】
図13は節点テーブルのデータ構造を表す図である。1つの節点に対応する節点データは、(変数ラベル,0枝の子節点のアドレス,1枝の子節点のアドレス)の3つのデータ組からなる。変数ラベルには、各節点に対応する入力変数又は出力変数を特定する符号が格納される。通常は、計算処理の便宜のため、m+n個の各変数x,…,x,y,…,ym-1には2進数の符号が割り当てられるが、ここでは説明の都合上、変数x,…,x,y,…,ym-1の記号をそのまま使用する。「0枝」(0-edge)とは、その節点に対応する変数の値(リテラル)が0であるときの節点間の遷移を表す枝(edge)をいい、「1枝」(1-edge)とは、その節点に対応する変数の値(リテラル)が1であるときの節点間の遷移を表す枝をいう。「0枝の子節点」(「1枝の子節点」)とは、その節点に対して0枝(1枝)に沿って遷移した先の節点をいう。「節点のアドレス」とは、節点テーブル記憶手段8において、その節点データが格納されている記憶装置の論理アドレスをいう。
【0160】
従って、ある節点に対応する変数の値が与えられた場合に、その変数値に対する遷移先の節点を参照する場合には、変数値0,1に応じて0枝の子節点のアドレス,1枝の子節点のアドレスを参照すれば、特性関数二分決定グラフの径路(path)を辿ることができる。
【0161】
〔例8〕
入力変数X=(x,x,x)に対して式(31)により表される多出力論理関数f(X)について、変数順序Pは、上記アルゴリズムによってP=(x,x,y,x,y)となる。
【0162】
【数31】
JP0004562136B2_000036t.gif

【0163】
ここで、式(31)の多出力論理関数f(X)の特性関数二分決定グラフは、図14(b)により表される。従って、図14(b)の特性関数二分決定グラフに対応する節点テーブルは、図14(a)のようになる。ここで、終端節点のうち、特性関数値0に対応する終端節点にはアドレス0、特性関数値1に対応する終端節点にはアドレス1が割り当てられる。
〔例終わり〕
【0164】
(3)変数X,Yの順序の最適化
次に、変数X,Yが初期順序により順序づけられた特性関数二分決定グラフの節点テーブルが節点テーブル記憶手段8に格納されると、変数順序最適化手段9は、変数X,Yの間の順序の入れ替えを実行し、変数X,Y間の順序の最適化を行う。このとき、変数Xの順序の入れ替えには式(32)の条件(すなわち、「集合supp(f)に属するすべての入力変数xはyよりも高位である。」という条件)が課される。
【0165】
【数32】
JP0004562136B2_000037t.gif

【0166】
〔例9〕
式(31)の多出力論理関数F(X)で表現される論理仕様に対して、上記の変数順序P=(x,x,y,x,y)による特性関数二分決定グラフの節点テーブルが、図14のように生成され、節点テーブル記憶手段8に格納されているとする。変数順序最適化手段9は、この節点テーブルに対して、上記条件のもとでの変数順序Pの入れ替えを行う。そして、入れ替え後の変数順序P’により、特性関数二分決定グラフの再構築を行い、その結果、特性関数二分決定グラフの幅の総和が小さくなった場合にのみ、変数順序P’の節点テーブルで節点テーブル記憶手段8の内容を更新する。
【0167】
例えば、変数順序最適化手段9が上記の変数順序Pを順序P’=(x,x,x,y,y)のように入れ替えを行った場合、特性関数二分決定グラフは図15(b)のようになる。また、この特性関数二分決定グラフに対応する節点テーブルは図15(b)のようになる。図15(a)の節点テーブルの大きさと図14(a)の節点テーブルの大きさは同じである。従って、この場合、節点テーブル記憶手段8の内容の更新は行われない。
【0168】
このような変数順序の入れ替えによる節点テーブルの再構築を総当たり(又は、適当な条件を課した試行)で試みることにより、変数順序の最適化が行われる。尚、式(31)の多出力論理関数の場合、図14の特性関数二分決定グラフが最小であるため、節点テーブル記憶手段8内の節点テーブルの更新は行われない。
〔例終わり〕
【0169】
(4)LUTカスケード論理回路の合成
以上のように、最適化された特性関数二分決定グラフの節点テーブルが節点テーブル記憶手段8に格納されると、続いてLUTカスケード論理回路の合成処理が行われる。そこで、次に、LUTカスケード論理回路の合成処理について説明する。
【0170】
図16はLUTカスケード論理回路の合成処理の流れを表すフローチャートである。論理回路合成装置1は、分割線の高さを表す内部変数i(i-1が分割線の高さを表す。)をn+m+1(nは入力変数Xの大きさ(n=|X|)、mは出力変数Yの大きさ(m=|Y|)。)とする。また、中間変数の集合Hを空集合φとする。また、分割線より高位の変数の集合Zを空集合φとする。また、関数分解を行う特性関数二分決定グラフBCFcurrentを関数fの特性関数二分決定グラフBCF(f)とし、BCFcurrentに含まれる変数の集合Zを全変数の集合Z(=X∪Y)に初期化する(S30)。
【0171】
次に、分割線設定手段10は、変数iを1だけ減少する(S31)。すなわち、分割線の高さを1だけ下げる。そして、集合ZtempをZ∪{z}とする(S32)。ここで、{z}は高さiの変数zの集合を表す。すなわち、分割線を下げたので、集合{z}を分割線よりも高位の変数の集合Ztempに追加する。
【0172】
次に、分割線設定手段10は、関数分解可能性を判定する(S33)。関数分解の可能性の判定は、分割線で分割した場合の列複雑度μ及び集合Ztempの要素の数とLUTの入力数の最大値kを比較することにより行われる。すなわち、関数分解可能な条件は、式(33)で表される。従って、式(33)の条件を満たすか否かで関数分解の可能性が判定される。
【0173】
【数33】
JP0004562136B2_000038t.gif

【0174】
上記ステップS34の判定の結果、関数分解が可能であれば、次に、変数iが1であるか否かを判定する(S35)。i=1ならば、これ以上関数分解はできないので、LUT生成手段14は関数f(Ztemp)のLUTを生成し、LUT記憶手段16に格納し、終了する(S36)。また、ステップS35において、分割線の高さiが1よりも大きい場合には、分割線設定手段10は、集合Zを集合Ztempに更新して(S37)、ステップS31に戻る。
【0175】
一方、ステップS34において、関数分解が不可能であると判定される場合、分割線設定手段10は、Zの大きさが|Z|=|H|かどうかを判定する(S38)。もし、|Z|=|H|ならば、これ以上分割線を下げても関数分解が可能となる可能性はない。従って、この場合には、分割線設定手段10は、LUT論理回路が実現不可能である旨のメッセージを出力装置4に出力し(S39)、処理を終了する。
【0176】
ステップS38において、|Z|>|H|であれば、短絡除去手段11は、分割線の高さ以下の高さにある変数の集合ZをZ-Zとする(S40)。次に、短絡除去手段11は、分割線よりも高位の部分グラフに対して短絡除去を行う。次いで、BDD幅計測手段12は、短絡除去がされた特性関数二分決定グラフについて、分割線における幅μを計測する。次に、中間変数算出手段13は、レイル数uを式(34)により計算する(S41)。
【0177】
【数34】
JP0004562136B2_000039t.gif

【0178】
次に、LUT生成手段14は、(Z,Z)を変数の分割として、f(Z)=g(h(Z),Z)の形で関数分解したときの関数h(Z)のLUTを生成し、LUT記憶手段16に格納する(S42)。すなわち、上記S41の短絡処理が行われていない特性関数二分決定グラフについて、変数Zに関する部分グラフをB、Zに関わる部分グラフをBとする。また、ステップS41において短絡除去がされた特性関数二分決定グラフについて、X(⊆Z)に関わる部分グラフをB’、Zに関わる部分グラフをBとする。LUT生成手段14は、部分グラフBから、集合Zに属するすべての入力変数x(∈Z)を制御入力とし、集合Zに属するすべての出力変数y(∈Z)を出力するLUTを生成する。次いで、LUT生成手段14は、ステップS41において短絡除去がされた特性関数二分決定グラフについて、部分グラフB’から直接接続される部分グラフB内の節点の各々にuビットの符号(h,…,hua)を割り当てる。この符号(h,…,hua)を中間変数とする。そして、部分グラフB’から、集合Zに属するすべての入力変数X(∈Z)を制御入力とし、中間変数(h,…,hua)を出力するLUTを生成する。そして、これらのLUTをLUT記憶手段16に格納する。
【0179】
次に、BDD再構成手段15は、(Z,Z)を変数の分割として、f(Z)=g(h(Z),Z)の形で関数分解したときの関数g(h,Z)についての特性関数二分決定グラフを生成する(S44)。すなわち、BDD再構成手段15は、ステップS41において短絡除去がされた特性関数二分決定グラフについて、X(⊆Z)に関わる部分グラフを、中間変数(h,…,hua)を制御入力とする二分木に置き換える。
【0180】
次に、中間変数の集合Hを、u個の中間変数(h,…,hua)に更新する。そして、集合Zを集合Zと集合Hとの和集合Z∪Hとする(S44)。
【0181】
次に、|Z|がk以下かどうかを判定する(S45)。|Z|≦kならば、関数gのLUTを生成し、LUT記憶手段16に格納し(S46)、処理を終了する。
【0182】
ステップS44において、|Z|>kならば、分割線の高さiを|Z|+1,BCFcurrentをBCF(g),集合Zを集合Zと集合Hとの和集合Z∪Hとした後(S47)、更に、集合Zを集合H,関数fを関数gとして(S48)、ステップS31に戻る。
【0183】
以上の処理により、論理関数の分解が行われ、LUTカスケード論理回路が構成される。
【0184】
以上のように、本実施例の論理回路合成装置1によれば、比較的少容量のメモリを用いてLUT論理回路の合成を実現できる。また、論理関数分解処理の演算処理速度を高速化することができる。
【0185】
また、現在まで有効な論理回路合成手段が知られていなかった、多出力論理関数の分解による途中出力を有するLUT論理回路の生成を、現実的なハードウェアを使用して短時間で実行することが可能となる。
【0186】
(5)実験結果
最後に、本発明の効果を示すため、実際に幾つかのベンチマーク関数を用いてLUTカスケード論理回路の合成を行った結果を図17に示す。実験は上記実施例1のアルゴリズムをC言語で実装し、MCNC89ベンチマーク関数に適用した。図17は、LUTの入力数kを10に設定した場合の結果である。
【0187】
図17において、「Name」は関数名、「In」は入力数、「Out」は出力数、「LUT」は生成されるLUTの総数、「Cas」はカスケードの個数を表し、「段数」はカスケードの段数を表す。実行環境は、IBM PC/AT互換機,Pentium(登録商標)42.0GHz,メモリ512MByte,OSはWindows(登録商標)2000,cygwin上でgccを用いてコンパイルした。本アルゴリズムでは、出力のグループ分けを行うため、一つずつの出力をグループに加えて特性関数二分決定グラフを構成し、変数順序最適化を行う。kが大きくなると、LUTカスケードに対応する特性関数二分決定グラフが大きくなる。LUTカスケードで構成可能な限り、グループの出力を一つずつ増やしながら変数順序最適化を行うため、大きな特性関数二分決定グラフの変数順序最適化を行う回数が増える。このため、kが大きくなると多くの実行時間が必要となる。実行時間の殆どは、特性関数二分決定グラフの変数順序最適化のための時間である。
【0188】
本発明の効果を確認するため、非特許文献15に記載の方法との比較を行った。非特許文献15の方法は、MTBDDに基づいており、多出力論理関数の出力を幾つかのグループに分割してMTBDDで表現し、LUTカスケードで実現する。MTBDDの幅が大きすぎるため分解不可能な場合は、OR分割を用いてカスケードを分割する。図17では、非特許文献15の方法については、一つのグループの出力数は8として、出力を分割している。
【0189】
非特許文献15の方法では、実現したLUTカスケードのLUTの個数や段数にかかわらず、分割するグループの出力数を固定しているため、カスケードの個数は多くなり、段数は小さくなる傾向にある。一方、本発明に係る方法では、LUTカスケードは可能な限り、一つのグループの出力の個数を増やすので、段数は多くなり、カスケードの個数は少なくなる。
【実施例2】
【0190】
図18は、本発明の実施例2に係る論理回路合成装置及びその周辺装置の構成を表す図である。図18において、論理仕様記憶手段2、入力装置3、出力装置4、出力変数順序決定手段5、全変数順序決定手段6、BDD生成手段7、節点テーブル記憶手段8、変数順序最適化手段9、分割線設定手段10、短絡除去手段11、BDD幅計測手段12、中間変数算出手段13、LUT生成手段14、BDD再構成手段15、及びLUT記憶手段16は、実施例1と同様のものである。本実施例の論理回路合成装置1’は、グラフ幅削減装置20を備えている点を特徴としている。
【0191】
尚、本実施例においても、実施例1と同様、論理回路設計用のCAD装置において論理回路合成装置1’を使用する場合を想定している。論理回路合成装置1’は、プログラム形態として提供され、そのプログラムをコンピュータに読み込んで実行することによって、図18に示したような論理回路合成装置1’の機能構成がコンピュータで実現される。
【0192】
グラフ幅削減装置20は、節点テーブル記憶手段8に記憶された節点テーブルにより表される特性関数が不完全定義関数である場合、その特性関数二分決定グラフの幅の削減を行う。
【0193】
図19は、図18のグラフ幅削減装置20の構成を表す図である。グラフ幅削減装置20は、BDD高さ計測手段21、分割線設定手段22、列関数生成手段23、列関数記憶手段24、両立枝生成手段25、両立グラフ記憶手段26、クリーク生成手段27、クリーク・データ記憶手段28、及び割当BDD再構成手段29を備えている。
【0194】
BDD高さ計測手段21は、節点テーブル記憶手段8に記憶されている節点テーブルによって表現される特性関数二分決定グラフの根節点の高さtを計測する。分割線設定手段22は、高さt-1から1まで、分割の高さlevを順次設定する。
【0195】
列関数生成手段23は、節点データ記憶手段8に記憶された節点テーブルから、分割の高さlevの節点の各枝に対応する列関数を生成し、それら各列関数に対応した列関数ラベルを有する関数節点データを生成して両立グラフ記憶手段26に保存する。列関数記憶手段24は、列関数生成手段23が生成する列関数を一時的に記憶する。
【0196】
両立枝生成手段25は、両立グラフ記憶手段26に記憶された各関数節点データに対する列関数から、両立する列関数の組を選出し、それら両立する列関数に対する関数節点データにそれらの関数節点同士を連結する両立枝を追加して、両立グラフ記憶手段26に記憶された関数データの更新を行う。
【0197】
クリーク生成手段27は、両立グラフ記憶手段26に記憶された両立グラフの全節点について、完全部分グラフ(クリーク)による節点被覆を行う。そして、クリークに含まれる関数節点集合であるクリーク・データを生成し、クリーク・データ記憶手段28に記憶する。
【0198】
割当BDD再構成手段29は、クリーク・データ記憶手段28に記憶された各クリーク・データに対して、当該クリーク・データに含まれる各関数節点に対応する列関数のドント・ケアに定数を割り当てて同一の割当列関数を生成する。そして、当該クリーク・データに含まれる各関数節点の列関数を、割当列関数に置換することによって、特性関数二分決定グラフの再構成を行い、節点テーブル記憶手段8の節点テーブルの更新を行う。尚、割当BDD再構成手段29は、各関数節点に対応する列関数を参照する際、節点テーブル記憶手段8の節点テーブルから必要に応じて列関数を合成するようにしてもよいが、列関数記憶手段24に一時保存されている列関数を参照するようにしてもよい。
【0199】
以上のように構成された本実施例に係る論理回路合成装置1’について、以下その演算処理動作を説明する。
【0200】
全体の流れとしては、最初に、図11のステップS1~S3の処理により、節点データ記憶手段8に、不完全定義関数の特性関数二分決定グラフの節点テーブルが保存される。次に、グラフ幅削減装置20による特性関数二分決定グラフの幅削減処理が実行される。そして、最後に、図11のステップS4のLUT論理回路の合成が行われる。ここで、本実施例の論理回路合成装置1’は、グラフ幅削減装置20による特性関数二分決定グラフの幅削減処理以外の演算処理は、実施例1と同様である。そこで、ここではグラフ幅削減装置20の演算処理についてのみ説明する。
【0201】
図20は、グラフ幅削減装置20のグラフ幅削減処理の全体の流れを表すフローチャートである。最初に、BDD高さ計測手段21が、節点テーブル記憶手段8に記憶された節点テーブルを探索して、特性関数二分決定グラフの根節点の高さtを決定する。根節点の高さtが決定されると、分割線設定手段22は、分割の高さlevをt-1に設定する(S50)。
【0202】
次に、列関数生成手段23は、分割の高さlevにおけるすべての列関数の集合を作成する(S51)。生成された列関数に対しては、関数節点の節点ラベルが付与され、両立グラフ記憶手段26に関数節点データとして保存される。また、特性関数二分決定グラフの大きさが小さい場合には、計算速度を向上させるために、列関数生成手段23が生成した各列関数を、列関数記憶手段24に保存するようにしてもよい。
【0203】
次に、両立枝生成手段25は、列関数生成手段23が生成する各列関数から、両立する列関数の組を選出する。そして、両立グラフ記憶手段26に記憶された両立する列関数に対する関数節点データに、それらの関数節点同士を連結する両立枝を追加する。両立枝が追加された関数節点データは、両立グラフ記憶手段26に保存され、関数節点データの更新が行われる(S52)。この処理は、列関数生成手段23が生成するすべての列関数に対して、すべての2つの列関数組の組み合わせについて実行される。この処理によって、両立グラフ記憶手段26に、両立グラフを表現する関数節点データのテーブルが生成される。
【0204】
次に、クリーク生成手段27は、両立グラフ記憶手段26に記憶された関数節点データのテーブルが表す両立グラフに対して、クリーク集合による節点被覆処理を実行する(S53)。この処理の詳細については後述するが、これによって、両立グラフのすべての節点について、完全部分グラフ(クリーク)による節点被覆が行われ、クリーク・データが生成される。生成されたクリーク・データは、クリーク・データ記憶手段28に保存される。
【0205】
尚、「完全部分グラフ(クリーク)」とは、両立グラフの部分グラフであって、当該部分グラフの任意の一つの節点が他のすべての節点と枝により連結されているものをいう。また、クリーク・データとは、クリークに含まれる関数節点の集合のデータをいう。
【0206】
次に、割当BDD再構成手段29は、節点テーブル記憶手段8に記憶された節点テーブルに基づき、クリーク・データ記憶手段28に記憶された一つのクリーク・データについて、当該クリーク・データに含まれる関数節点に対応する列関数を生成し、列関数記憶手段24に一時的に保存する。そして、当該クリーク・データに属するすべての関数節点に対応する列関数について、ドント・ケアへの定数の割り当てを行い、同一の割当列関数を生成する。そして、当該クリーク・データに属するすべての関数節点に対応する列関数を、生成した割当列関数により置換した特性関数二分決定グラフとなるように、節点テーブル記憶手段8内の節点テーブルの書き換えを行う。この割当列関数を用いた節点テーブルの書き換え処理を、すべてのクリーク・データに対して実行することにより、特性関数二分決定グラフの再構成を行う(S54)。
【0207】
次に、分割線設定手段22は、分割の高さlevを1だけ減少させる(S55)。そして、分割の高さlevが1以上であれば(S56)、ステップS51に戻る。分割の高さlevが0となった場合には(S56)、グラフ幅削減処理を終了する。
【0208】
以上のようなグラフ幅削減処理によって、上述したアルゴリズム3が実行され、効果的な特性関数二分決定グラフの幅の削減が実行される。
【0209】
次に、上記ステップS53におけるクリーク集合による両立グラフの節点被覆処理について説明する。図21は、クリーク集合による両立グラフの節点被覆処理の流れを表すフローチャートである。
【0210】
クリーク生成手段27は、内部変数として、クリーク・データのリストを表す変数C(以下「集合C」という。)、クリーク被覆が行われていない関数節点のリストを表す変数S(以下「節点集合S」という。)、一つのクリークに含まれる関数節点のリストを表す変数S(以下「節点集合S」という。)、及びクリーク変数に追加する関数節点の候補のリストを表す変数S(以下「節点集合S」という。)を有する。
【0211】
まず、クリーク生成手段27は、クリーク・データの集合Cを空集合に初期化する(S60)。そして、両立グラフのすべての関数節点を節点集合Sに追加して初期化を行った後、節点集合Sから枝を持たない関数節点を除去するとともに、これらの関数節点を、要素1のクリーク集合として、集合Cの要素に追加する(S61)。
【0212】
次に、クリーク生成手段27は、節点集合Sが空集合でないか否かを判定する(S62)。
【0213】
節点集合Sが空集合でない場合、クリーク生成手段27は、節点集合Sの中で枝数が最小である関数節点を探索し、これを関数節点vとする(S63)。次に、クリーク生成手段27は、節点集合Sを{v}に初期化する(S64)。そして、節点集合Sの中で関数節点vに接続している関数節点を探索し、これを節点集合Sとする(S65)。
【0214】
次に、クリーク生成手段27は、節点集合Sが空集合か否かを判定する(S66)。節点集合Sが空集合でなければ、節点集合Sに属する関数節点の中で、枝数が最小のものを探索し、これを関数節点vとする。そして、節点集合Sに{v}を追加するとともに、節点集合Sから関数節点vを除去する(S67)。そして、節点集合Sに属する関数節点のうち、関数節点vに接続していない関数節点を節点集合Sから除去する(S68)。そして、ステップS66に戻る。
【0215】
ステップS66において、節点集合Sが空集合の場合、集合Cの要素に節点集合Sをクリークとして追加するとともに、未被覆の節点集合Sから節点集合Sを除去する(S69)。そして、ステップS62に戻る。
【0216】
ステップS62において、未被覆の節点集合Sが空集合となった時点で、集合Cをクリーク・データとしてクリーク・データ記憶手段28に保存し、クリーク集合による両立グラフの節点被覆処理を終了する。
【0217】
以上のような処理によって、両立グラフのすべての関数節点が、クリークにより被覆され、クリーク・データが生成される。
【0218】
〔例10〕
真理値が例6の(表4)により表される4入力2出力不完全定義関数について、特性関数二分決定グラフの幅を削減する。(表4)により表される4入力2出力不完全定義関数の特性関数二分決定グラフは、図4(a)で表される。特性関数二分決定グラフの高さtは6である。これを、本実施例のグラフ幅削減装置20によって特性関数二分決定グラフの幅の削減処理を行う。
【0219】
まず、最初に分割の高さlevはt-1=5、すなわち、変数xの高さに設定される。lev=5において、分解表は(表5)に示したようになる。(表5)の列関数は両立しないため、ドント・ケアへの定数の割り当てはできない。
【0220】
【表5】
JP0004562136B2_000040t.gif

【0221】
次に、分割の高さをlev=4とする(図22(a)参照)。lev=4の分解表は、(表6)のようになる。
【0222】
【表6】
JP0004562136B2_000041t.gif

【0223】
(表6)より、4つの列関数Φ~Φが得られる。列関数Φと列関数Φは両立する。従って、両立グラフは、図22(b)のように表される。図22(b)の両立グラフについて、クリークによる節点被覆処理を行うと、図22(b)の点線で示した3つのクリークS,S,Sが生成される。そこで、クリークSに含まれる2つの列関数Φ,Φに対して定数の割り当てを行うと、(表7)のようになる。これらの列関数から特性関数二分決定グラフを生成すると、図23(a)のようになる。図22(a)のグラフの節点2,4は、図23(a)では、節点11に置き換えられている。
【0224】
【表7】
JP0004562136B2_000042t.gif

【0225】
次に、分割の高さをlev=3(変数yの高さ)とする(図23(a)参照)。図23(a)より、分割の高さをlev=3を横切る各枝に対応して、6つの列関数Φ~Φが得られる。図23(a)では、各列関数Φ~Φの添字に対応して、それぞれの枝に番号が付されている。列関数Φ,Φ、列関数Φ,Φ,Φは両立する。従って、両立グラフは、図23(b)のように表される。図23(b)の両立グラフについて、クリークによる節点被覆処理を行うと、例えば、図23(b)の点線で示した4つのクリークS,S,S,Sが生成される。そこで、クリークSに含まれる2つの列関数Φ,Φに対して定数の割り当てを行い、クリークSに含まれる2つの列関数Φ,Φに対して定数の割り当てを行う。そして、生成された割当列関数を用いて、特性関数二分決定グラフの再構成を行うと、グラフ構造は図24のようになる。図23(a)の節点6,8と節点7,10を、図24では、それぞれ節点12,13で置き換えている。
【0226】
分割の高さをlev=2,1では、各列関数は両立しないので、これ以上特性関数二分決定グラフの再構成は行われない。
【0227】
図22(a)と図24とを比較すると、グラフ幅削減処理の結果、最大幅は8から4に削減され、非終端節点数は15から12に削減されたことが分かる。これを、上述したアルゴリズム1の結果と比較すると、アルゴリズム1を適用した結果(図4(b)参照)に比べ、最大幅がより削減されていることが分かる。
〔例終わり〕
【0228】
最後に、幾つかのベンチマーク関数を用いて、本実施例に係るグラフ幅削減装置1’の性能を試験した結果について説明する。(表8)は、各ベンチマーク関数について、本実施例の論理回路合成装置1’によりLUTカスケード論理回路の合成を行った結果を表す。
【0229】
【表8】
JP0004562136B2_000043t.gif

【0230】
それぞれのベンチマーク関数は以下の通りである。
【0231】
(1)剰余数表現(Residue Number System,RNS)を2進表現に変換する回路(Residue Number to Binary Number Converters)
・5-7-11-13RNS(14-input 13-output,DC 69.5%:4-digit RNS number,where the moduli are 5,7,11,and 13)
・7-11-13-17 RNS(16-input 15-output,DC 74.0%)
・11-13-15-17 RNS(17-input 16-output,DC 72.2%)
【0232】
(2)i桁のk進数を2進数に変換する回路(k-nary to Binary Converters)
・4-digit 11-nary to binary(16-input 14-output,DC 77.7%)
・4-digit 13-nary to binary(16-input 15-output,DC 56.4%)
・5-digit decimal to binary(20-input 17-output,DC 90.5%)
・6-digit 5-nary to binary(18-input 14-output,DC 94.0%)
・6-digit 6-nary to binary(18-input 16-output,DC 82.2%)
・6-digit 7-nary to binary(18-input 17-output,DC 55.1%)
・10-digit ternary to binary(20-input 16-output,DC 94.4%)
【0233】
(3)i桁の10進数の加算回路、乗算回路(Decimal Adders and a Multiplier)
・3-digit decimal adder(24-input 16-output,DC 94.0%)
・4-digit decimal adder(32-input 20-output,DC 97.7%)
・2-digit decimal multiplier(16-input 16-output,DC 84.7%)
【0234】
(表8)において、「DC=0」は、すべてのドント・ケアに0を割り当てた場合を示し、「Alg.3」は、本実施例に係る論理回路合成装置1’によりアルゴリズム3を適用した場合を示している。「#Cells」の欄は、カスケード内のセル数を表す。「#LUTs」の欄は、LUTの出力数の総和を表す。「#Cas」の欄は、カスケードの数を表す。(表8)より、本実施例に係る論理回路合成装置1’により、カスケード内のセル数とLUTの出力数の総和を効果的に削減することが可能であることが分かる。
【0235】
例えば、5-7-11-13 RNSを考える。この関数は、入力の組み合わせに対し69.5%のドント・ケアを含む。この関数についてLUTカスケード論理回路を合成する。条件として、各セルの入力の本数は制限されており、入力数が最大12まで許されるものとする。
【0236】
ドント・ケアに0を割り当ててLUTカスケード論理回路を合成すると、図25(a)のようになる。これに対し、本実施例に係る論理回路合成装置1’によりLUTカスケード論理回路を合成すると、図25(b)のようになる。明らかに、本実施例に係る論理回路合成装置1’によりLUTカスケード論理回路の回路規模を減少させることが可能であることが分かる。
【産業上の利用可能性】
【0237】
本発明は、LUT型の論理回路を自動設計する論理回路設計用のCAD装置、LUT型FPGAの論理合成ツール等に適用することができる。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23
【図25】
24