TOP > 国内特許検索 > 多段論理回路の再構成装置及び再構成方法、論理回路修正装置、並びに再構成可能な多段論理回路 > 明細書

明細書 :多段論理回路の再構成装置及び再構成方法、論理回路修正装置、並びに再構成可能な多段論理回路

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4742281号 (P4742281)
登録日 平成23年5月20日(2011.5.20)
発行日 平成23年8月10日(2011.8.10)
発明の名称または考案の名称 多段論理回路の再構成装置及び再構成方法、論理回路修正装置、並びに再構成可能な多段論理回路
国際特許分類 G06F   7/00        (2006.01)
H03K  19/173       (2006.01)
FI G06F 7/00 204
H03K 19/173 101
請求項の数または発明の数 11
全頁数 40
出願番号 特願2008-508466 (P2008-508466)
出願日 平成19年3月2日(2007.3.2)
国際出願番号 PCT/JP2007/054100
国際公開番号 WO2007/113964
国際公開日 平成19年10月11日(2007.10.11)
優先権出願番号 2006101107
優先日 平成18年3月31日(2006.3.31)
優先権主張国 日本国(JP)
審査請求日 平成21年7月3日(2009.7.3)
特許権者または実用新案権者 【識別番号】504174135
【氏名又は名称】国立大学法人九州工業大学
発明者または考案者 【氏名】笹尾 勤
個別代理人の代理人 【識別番号】100121371、【弁理士】、【氏名又は名称】石田 和人
審査官 【審査官】緑川 隆
参考文献・文献 特開平06-004266(JP,A)
特開平09-297776(JP,A)
Hui Qin,Tsutomu Sasao,Jon.T.Butler,Implementation of LPM address generatorson FPGAs,Reconfigurable Computing: Architectures and Applications. SecondInternational Workshop, ARC 2006. (Lecture Notes in Computer Science Vol. 3985),2006年 3月 3日,p.170-181,URL,http://www.lsi-cad.com/sasao/Papers/files/ARC2006_qin.pdf
調査した分野 G06F 7/00
H03K 19/173
特許請求の範囲 【請求項1】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする多段論理回路の再構成装置。
【請求項2】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする多段論理回路の再構成装置。
【請求項3】
入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、
前記修正用ベクトルPiは、対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)との排他論理和が、前記修正出力ベクトルQ'(bi)となる値に設定され、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し、それ以外の場合は0を出力するものであり、
前記修正手段は、前記補助メモリの出力値と前記主論理回路との排他論理和演算を行うEXORゲートであることを特徴とする論理回路修正装置。
【請求項4】
入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、前記入力変数Xに対して、当該入力変数Xの値がいずれの前記対象入力ベクトルbiとも等しくない場合には、無効値を出力するものであり、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し
前記修正手段は、前記主論理回路及び前記補助メモリの出力段にそれぞれ設けられたトライ・ステート・バッファであり、
前記主論理回路の出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となり、
前記補助メモリの出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となることを特徴とする論理回路修正装置。
【請求項5】
前記補助メモリは、前記アドレス生成回路の最終段のpq素子であることを特徴とする請求項3又は4記載の論理回路修正装置。
【請求項6】
前記アドレス生成回路において、入力ベクトルbに対する前記アドレス生成関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする請求項3乃至5の何れか一記載の論理回路修正装置。
【請求項7】
前記アドレス生成回路において、前記アドレス生成関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする請求項3乃至5の何れか一記載の論理回路修正装置。
【請求項8】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択ステップと、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査ステップと、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正ステップと、
を繰り返し実行することを特徴とする多段論理回路の再構成方法。
【請求項9】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択ステップと、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付ステップと、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正ステップと、を繰り返し実行することを特徴とする多段論理回路の再構成方法。
【請求項10】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、
を備えたことを特徴とする再構成可能な多段論理回路。
【請求項11】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、
を備えていることを特徴とする再構成可能な多段論理回路。
発明の詳細な説明 【技術分野】
【0001】
本発明は、論理関数の関数分解を繰り返して論理設計される多段論理回路の再構成を行う再構成装置と、それを用いた論理回路修正装置に関する。
【背景技術】
【0002】
一般に、論理回路は専用のLSI(ASIC:Application Specific Integrated Circuit)を用いて構成されることが多い。しかしながら、ASICの開発コストは高価であり、その修正や費用にも時間がかかる。一方、論理構成の容易なFPGA(Field Programmable Gate Array)も存在するが、現状では消費電力や性能の点で問題がある。
【0003】
そこで、通常、ASICは、修正を可能とする余分な論理回路をあらかじめ組み込んだ状態に設計される。これにより、軽微な機能変更にある程度柔軟に対応させることが可能となる。
【0004】
軽微な機能変更を行う論理回路修正装置としては、例えば、特許文献1に記載のものが公知である。特許文献1に記載の論理回路修正装置は、CPUで実行するプログラムが記憶されたROMの出力値を修正するためのものであり、FPGAを用いて構成されている。
【0005】
図20は、特許文献1に記載の論理回路修正装置103の構成を示す図である。ROM101には、CPU102で実行するプログラムが格納されている。CPU102は、ROM101に対してアドレスバス104を介してアドレスを送る。ROM101は、当該アドレスに対し、第1のデータバス106にデータを出力する。
【0006】
論理回路修正装置103には、アドレスバス104からアドレスが入力され、それに対するデータが第1のデータバス106から入力される。論理回路修正装置103内の修正アドレス記憶部111には、修正を行うべきデータが格納されたROM101のアドレスが登録されている。比較回路113は、修正アドレス記憶部111に記憶されたアドレス値にアドレスバス104から入力されるアドレス値に一致するものがあるか否かを判定し、一致するものがある場合は一致信号を、一致するものがない場合には不一致信号を出力する。一致信号又は不一致信号は、データ選択回路114に出力される。
【0007】
一方、修正データ格納部112には、修正アドレス記憶部111に登録された各アドレス値に対応して、修正を行うべきデータが登録されている。データ選択回路114は、比較回路113から一致信号が入力された場合には、修正データ格納部112から読み出したデータを第2のデータバス105に出力する。一方、不一致信号が入力された場合には、データ選択回路114は、第1のデータバス106から入力されるデータを第2のデータバス105に出力する。第2のデータバス105に出力されたデータは、読み出しデータとしてCPU102に入力される。
【0008】
このようにして、修正したいROM101のアドレスを修正アドレス記憶部111に登録するとともに、修正したいデータを修正データ格納部112に登録することによって、ROM101の内容の軽微な修正が行われる。

【特許文献1】特開2002-297408号公報
【特許文献2】特開2004-258799号公報
【非特許文献1】T. Sasao and M. Matsuura, "BDD representation for incompletely specified multiple-output logic functions and its applications to functional decomposition," Design Automation Conference, Anaheim, CA, June 13-17, 2005, pp.373-378.
【発明の開示】
【発明が解決しようとする課題】
【0009】
ところで、設計段階においては、もとの論理回路のどの部分の修正が必要となるのかは分からない。従って、論理回路修正装置は、もとの論理回路の任意の出力に対して修正が可能であることが求められる。そのためには、回路の論理構成を自在に変更できることが必要である。
【0010】
一方で、論理回路修正装置は、論理回路の修正がない限り、本来の論理回路の動作には関係しない余分な回路である。従って、論理回路修正装置は、その実装面積ができる限り小さく、その消費電力も可能な限り小さいことが好ましい。
【0011】
上記従来の論理回路修正装置は、回路に汎用性を持たせるためにFPGAを用いて構成されている。そのため、広い配線領域が必要とされ、論理回路修正装置の実装に比較的大きなチップ面積が必要であるという問題がある。
【0012】
また、FPGAの再構成を行う場合、一般に、配線の変更がなされる。従って、配線遅延の影響なども考慮に入れた変更が必要とされる。また、変更を誤ると、最悪の場合には回路を破損するおそれがあり、回路変更には十分な注意が必要とされる。更に、配線の変更を伴うことから、回路の変更は、論理回路の動作の停止中に行う必要がある。従って、論理回路の動作期間中にリアルタイムで動的な変更が要求されるような用途(例えば、辞書やニューラル・ネットワーク等における学習に伴う論理回路構成の変更。)に適用することは困難である。
【0013】
ところで、論理構造の再構成が可能な論理回路として、LUTカスケード論理回路が知られている(特許文献2,非特許文献1参照)。LUTカスケード論理回路は、二分決定グラフ(BDD:binary decision diagram)を用いて目的論理関数を入出力関係が直列状態となる複数の部分関数に関数分解し、各部分関数をLUTとしてメモリで実現したものである。LUTカスケード論理回路は、殆どがメモリにより構成されるため、高集積化が容易であり実装面積を小さくできる。
【0014】
しかしながら、LUTカスケード論理回路の再構成を行う場合、従来は、多くの計算処理が必要とされていた。再構成を行う場合、まず、目的論理関数のBDDを作成し、BDDの分割と再構成を繰り返すことによって最適な関数分解方法を探索する。そして、その結果得られる部分関数をLUT化してメモリに格納する。目的論理関数の入力変数が多い場合、この処理には大容量メモリを備えたコンピュータで長時間かけて行う必要がある。そのため、簡易な書き換えが必要とされる論理回路修正装置にLUTカスケード論理回路を適用することは、従来行われていない。
【0015】
しかしながら、LUTカスケード論理回路の論理構成の再構築を簡易化し、軽微な論理の修正を容易に行う手段があれば、論理回路修正装置をLUTカスケード論理回路に適用すれば、小実装面積化と低消費電力化のアプローチと成り得ると考えられる。
【0016】
そこで、本発明の目的は、上記LUTカスケード論理回路と類似のLUT型の再構成可能な論理回路を用いて、回路の論理構成の変更の自由度を維持しつつ、従来に比べて実装面積を縮小することができ、消費電力も小さい論理回路修正装置を提供することにある。また、論理回路の動作期間中にリアルタイムで動的な修正を可能とする論理回路修正装置を提供することにある。
【0017】
また、本発明の他の目的は、上記論理回路修正装置などにおいて使用される、論理変更が可能で且つ小実装面積・低消費電力の多段論理回路の再構成を簡易に行うことが可能な多段論理回路の再構成装置を提供することにある。
【0018】
また、本発明の他の目的は、論理関数の軽微な再構成を容易に行うことができ、論理回路の動作期間中にリアルタイムで動的な再構成を実行することを可能とする再構成可能多段論理回路を提供することも目的としている。
【課題を解決するための手段】
【0019】
〔1〕用語の説明及び本発明の原理的背景
まず、本明細書において使用される主な用語の定義を行い、本発明に関するいくつかの理論的背景について説明する。
【0020】
〔定義1〕(アドレス生成関数,アドレス生成論理関数)
関数F(X):Bn→{0,1,…,k}(Xはn次元ベクトル, B={0,1})においてk個の異なる登録ベクトル(registered vector)ai∈Bn(i=1,2,…,k)に対して、F(ai)=i(i=1,2,…,k)が成立し、それ以外の(2n-k)個の入力ベクトルに対しては、F=0が成立するとき、F(X)を重みkのアドレス生成関数(address generation function)という。アドレス生成関数は、k個の異なる2値ベクトルに対して、1からkまでの固有アドレスを生成する。アドレス生成関数の出力値を2進数で表現する多出力論理関数をアドレス生成論理関数(address generation logic function)という。
(定義終り)
本明細書においては、kの値は入力ベクトルの組み合わせ総数2に比べて十分に小さい(k<<2)と仮定する。
【0021】
〔定義2〕(アドレス検出関数)
関数f(X):Bn→{0,1,…,k}(Xはn次元ベクトル)においてk個の異なる登録ベクトルai∈Bn(i=1,2,…,k)に対してf(ai)=1(i=1,2,…,k)が成立し、それ以外の(2n-k)個の入力ベクトルに対しては、f=0が成立するとき、f(X)を重みkのアドレス検出関数(address detection function)という。
(定義終り)
【0022】
〔定義3〕(アドレス表,アドレス生成回路)
アドレス生成論理関数F(X):Bn→{0,1,…,k}のk個の登録ベクトル{ai| i=1,2,…,k; ai∈Bn}に対し、出力ベクトルF(ai)(∈Bm)を対応させた表をアドレス表(address table)という。アドレス表を実現する回路をアドレス生成回路(address generation circuit)という。
(定義終り)
【0023】
〔定義4〕(分割)
入力ベクトルをX=(x,x,…,x)とする。Xの変数の集合を{X}で表す。{X}∪{X}={X}且つ{X}∩{X}=φのとき、X=(X,X)をXの分割(partition)という。ここで、φは空集合を表す。
(定義終り)
【0024】
〔定義5〕(分解表,基本分解表,列複雑度)
完全定義関数f(X):B→B(B={0,1},X=(x,x,…,x),n,q∈自然数)が与えられているとする。(X,X)をXの分割とする。Xの次元(変数の個数)をd(X)と記す。関数f(X)及びXの分割X=(X,X)に対して、以下の(1)~(3)の条件を満たす表をfの分解表(decomposition chart)という。
(1)2nL列2nH行の表である。ここで、n=d(X),n=d(X)とする。
(2)各行,各列に2進符号のラベルを持ち、列及び行のラベルの集合は、それぞれn,nビットのすべてのパターンを要素とする。
(3)表の各要素が、その要素に対応する列及び行のラベルの組み合わせ(X,X)に対するfの真理値f(X,X)である。
を束縛変数(bound variables)、Xを自由変数(free variables)という。分解表の異なる列パターンの個数を分解表の列複雑度(column multiplicity)といい、μと記す。分解表の特別な場合として、X=X,X=φの場合も考える。
また、関数fの分解表のうちで、X=(x,x,…,xnL)且つX=(xnL+1,xnL+2,…,x)となるものを基本分解表(standard decomposition chart)という。
(定義終り)
【0025】
(例1)
(表1)の分解表では、n=3,n=2である。また、分解表の列パターンは、(0110)と(1101)の2つなのでμ=2である。
(例終り)
【0026】
【表1】
JP0004742281B2_000002t.gif

【0027】
〔補題1〕
重みkのアドレス生成(検出)関数の分解表の列複雑度は高々k+1である。
(補題終り)
【0028】
〔補題2〕
Fがアドレス生成関数のとき、次式(1)の関係を満たす二つのアドレス生成関数GとHは存在し、Fの重みとGの重みは等しい。
【0029】
【数1】
JP0004742281B2_000003t.gif
(補題終り)
【0030】
(証明)
X1を束縛変数、X2を自由変数とする分解表を考える。分解表の各列の値の最大値の順位(最大値が0のときは、順位を0とする。)をH(Xi)の値とするアドレス生成関数Hを考える。このとき、関数Gでは、出力値がすべて零の列のみが縮約される。そのため、Gの非零出力の個数は、Fの非零出力の個数と等しい。また、Gもアドレス生成関数になっている。
(証明終り)
【0031】
(例2)
(表2)に示す5変数のアドレス生成関数F(X)の分解表を考える(図1参照)。いま、関数F(X)をF(X1,X2)=G(H(X1), X2)と分解する。ここで、X1=(x1,x2,x3,x4),X2=(x5)である。このとき、(表2)の列複雑度は7である。Hは(表3)に示す4入力3出力関数であり、重み6のアドレス生成論理関数となっている。また、関数Gの分解表を(表4)に示す。このように、重み7のアドレス生成関数Fを分解して得られる関数Gもまた、重み7のアドレス生成関数となる。
(例終り)
【0032】
【表2】
JP0004742281B2_000004t.gif

【0033】
【表3】
JP0004742281B2_000005t.gif

【0034】
【表4】
JP0004742281B2_000006t.gif

【0035】
〔補題3〕
fがアドレス検出関数のとき、下式(2)の関係を満たす、アドレス検出関数gとアドレス生成関数Hが存在し、gの重みはfの重みを超えない。
【0036】
【数2】
JP0004742281B2_000007t.gif
(補題終り)
これは、補題2と同様に証明できる。アドレス検出関数は単一出力であり、対応するアドレス生成回路よりも複雑になることはない。
【0037】
〔定義6〕(pq素子)
pq素子(pq-element)とは、任意のp入力q出力論理関数を実現するメモリであり、そのメモリ量(memory size)は2pqである。
(定義終り)
【0038】
〔定理1〕
重みkのアドレス生成論理関数は、pq素子を下式(3)で表される個数だけ用いて合成可能である。
【0039】
【数3】
JP0004742281B2_000008t.gif
(定理終り)
【0040】
(証明)
重みkのアドレス生成論理関数Fは、下式(4)のように関数分解が可能である。
【0041】
【数4】
JP0004742281B2_000009t.gif
このとき、補題1より、G(X1',X2)も重みkのアドレス生成関数であり、入力数はn-(p-q)に減っている。この操作を
【0042】
【数5】
JP0004742281B2_000010t.gif
繰り返すことにより、入力数をqまで削減することが可能である。従って、pq素子のみを用いて、アドレス生成回路を構成することが可能である。
(証明終り)
【0043】
(例3)
(表2)に示した5変数のアドレス生成関数F(X)の非零出力数は、k=7である。従って、式(6)となり、図1に示すように、4入力3出力素子で実現可能である。
【0044】
【数6】
JP0004742281B2_000011t.gif
(例終り)
【0045】
pq素子を用いて回路合成をする際、pを大きくすると、回路を実現するために必要なpq素子の数は減るが、総メモリ量は増える。一方、pを小さくすると、総メモリ量は減るが、pq素子数は増える。アドレス生成回路をpq素子で合成する場合、総メモリ量を増やさずに素子数を最小化するようなpの決定方法は、次の定理により示される。
【0046】
〔定理2〕
アドレス生成論理関数をpq素子の多段論理回路として実現する場合、総メモリ量の上限は、p-q=1又はp-q=2のときに最小となる。
(定理終り)
【0047】
(証明)
アドレス生成回路をpq素子を用いて関数分解する場合、1回分解する毎に、回路の入力線をr=p-q本削減することができる。n本の入力線をq本まで削減するためには、
【0048】
【数7】
JP0004742281B2_000012t.gif
の関数分解が必要である。また、回路実現のためには、s個のpq素子が必要である。従って必要な総メモリ量は、
【0049】
【数8】
JP0004742281B2_000013t.gif
となる。nが十分に大きい場合には、
【0050】
【数9】
JP0004742281B2_000014t.gif
と近似できる。nとpは与えられた問題により固定されているので、rのみを変化させることができる。2r/rは、r=1又はr=2のとき最小値をとる。従って、上記定理が証明される。
(証明終り)
【0051】
通常は、回路の段数は少ない方が望ましいので、r=p-q=2として回路を構成する。(定理1)は、関数分解を繰り返すことにより、アドレス生成回路をpq素子の多段論理回路として合成可能であることを示している。次に示す(例3)は、関数分解の方法によって、LUTカスケード論理回路を含む、種々の多段論理回路を合成することが可能であることを示している。
【0052】
(例4)
入力数n=48、重みk=255のアドレス生成回路を構成する。
【0053】
【数10】
JP0004742281B2_000015t.gif
である。これより、メモリ量を最小にし, 段数も減らすpの値はp=10である。pq素子1個に対して、入力線数が2減るので、pq素子を20個用いることで、入力数を8まで削減できる. 20個のpq素子で, 例えば, 図2のようなアドレス生成回路を実現可能である。この場合、段数は10段, メモリ量は160kbitである。
【0054】
また、入力数の大きい素子を用いることにより、素子数と遅延時間を削減することができる。図3はp=11,q=8の例である。この場合、素子数は(48-8)/(11-8)=14、段数は8段、メモリ量は212kbitである。また、図4は、p=12,q=8の例である。この場合、素子数は(48-8)/(12-8)=10、段数は5段、メモリ量は320kbitである。
(例終り)
【0055】
定理2は、一般のアドレス生成関数を実現する際、総メモリ量の上限を最小とする条件を示している。特定のアドレス生成関数に対しては、p-q=2以外の場合に、総メモリ量が最小になることもある。
【0056】
次に、アドレス生成関数のアドレス表を変化させた場合におけるpq素子の多段論理回路の再構成方法について説明する。多段論理回路の修正は、
(1)登録ベクトルの除去
(2)登録ベクトルの追加
の2つの基本操作に分解することができる。そこで、以下は上記(1)(2)の場合について考察する。
【0057】
また、上述したように、pq素子の多段論理回路は、目的論理関数Fに対して関数分解を繰り返したものである。従って、目的論理関数Fのアドレス表を変化させた場合に、関数分解F(X1,X2)=G(H(X1),X2)において、関数Hと関数Gの修正法を示せば十分である。
【0058】
尚、以下の説明において、「入力変数(input variable)」,「出力変数(output variable)」というときは、値がまだ決まっていない場合をいう。また、「入力ベクトル(input vector)」,「出力ベクトル(output vector)」というときは、入力変数,出力変数の具体的に決まった値をいう。
【0059】
(1)登録ベクトルの除去
入力変数X(∈Bn)の分割をX=(X1,X2)とおく。アドレス生成関数F(X)の関数分解をF(X1,X2)=G(H(X1),X2)と記す。ベクトルa(∈Bn)はアドレス生成関数F(X)の登録ベクトルであるとする。また、入力変数の分割X=(X1,X2)に対応するベクトルaの分割をa=(a1,a2)と記す。
【0060】
アドレス生成関数F(X)のアドレス表から登録ベクトルaを除去する場合を考える。尚、以下ではアドレス表がLUTカスケード論理回路で実現されている場合について考える。
【0061】
アドレス表からベクトルaを除去した場合、F(a)=0となる。従って、G(H(a1),a2)=0である。
【0062】
一方、部分関数G(Y1,X2)の一方の変数Y1を固定値H(a1)として変数X2を変化させた場合、X2=a2以外にG(H(a1),X2)≠0となる変数X2が存在しない場合、もとのアドレス表においてベクトルa以外の登録ベクトルの出力ベクトルは、部分関数の値H(a1)には依存しない。従って、この場合、H(a1)は無効な値であるためH(a1)=0としてもよい。
【0063】
以上より、アドレス表からの登録ベクトルaの除去に伴うLUTカスケード論理回路の修正は、次のようなアルゴリズムに従って行うことができる。
【0064】
(アルゴリズム1)
(Step 1) 未修正のpq素子のうち、最も出力側に近いものを選択する。選択されたpq素子をEGと記す。pq素子EGにより表される部分関数をG(H(X1),X2)とする。ここで、(X1, X2)⊆XかつX1∩X2=φである。(X1,X2)に対する入力ベクトルを(a1, a2)とする。但し、pq素子EGが最も出力側から遠い場合はX1=φ, H(X1)=φとする。
【0065】
(Step 2) pq素子EGに記憶されたLUTの出力ベクトルのうち、入力ベクトル(H(a1),a2)に対応する出力ベクトルをG(H(a1),a2)=0とする。pq素子EGを修正済とする。
【0066】
(Step 3) 出力ベクトルG(H(a1),X2)が非零となる部分変数X2に対する入力ベクトルa0が存在するか検査する。
【0067】
(Step 4)a0が存在しない場合、Step1に戻る。そうでなければ、処理を終了する。
(アルゴリズム終り)
【0068】
上記アルゴリズムを一般のpq素子の多段論理関数の場合に拡張するのは容易である。一般のpq素子の多段論理関数の場合は次のようになる。
【0069】
(アルゴリズム2)
(Step 1) 素子数がsのpq回路網は、関数分解をs-1回繰り返し適用して構成できる。各関数分解で、入力側から順にpq素子を抽出し、各pq素子に1からsまでの番号を付与する。出力のpq素子の番号はsである。番号1の素子E1は、出力から最も離れている。
【0070】
(Step 2) pq素子の集合をpとし、初期値をp={Es}とする。
【0071】
(Step 3) 多段論理回路において、pの要素とそれ以外の素子で構成された回路の関数分解G(H1(Y1), H2(Y2),…, Hm(Ym))を考える。ここで、Yiは中間変数で、特別な場合としてHk(Yk)=Ykも考える。
【0072】
(Step 4) G(H1(a1), H2(a2),…, H2(a2))=0とする。ここで、a=(a1,a2,…,am)は、中間変数のベクトルである。Hi(ai)=d≠0のとき、他の登録ベクトルbに対して、Hi(ai)=dとなるものが存在しないとき、Hi(ai)=0とする。
【0073】
(Step 5) pq素子の集合pの要素数がs-1ならば処理を終了する。そうでなければ、pに素子番号が最も大きい素子を追加して、Step3に戻る。
(アルゴリズム終り)
【0074】
(2)登録ベクトルの追加
次に、アドレス生成関数F(X)のアドレス表に登録ベクトルaを追加する場合を考える。新たに追加する登録ベクトルaに対する出力ベクトルをcとする。尚、以下ではアドレス表がLUTカスケード論理回路で実現されている場合について考える。
【0075】
アドレス表にベクトルaを追加した場合、F(a)=cとなる。従って、G(H(a1),a2)=cである。
【0076】
ここで、登録ベクトルaに対してF(a)の値を一対一に対応させるためには、部分関数H(a1)の値は0であってはならない。そこで、もし部分関数H(a1)の出力ベクトルが0となっている場合には0以外の値に修正する必要がある。この際、他の登録ベクトルの出力に影響を及ぼさないようにする必要があるため、部分関数H(a1)の出力ベクトルは未使用の値に変更する。例えば、部分関数H(X1)の非零出力の最大値よりも大きい未使用の値のうち、最小のものを選択することができる。
【0077】
以上より、アドレス表への登録ベクトルaの追加に伴うLUTカスケード論理回路の修正は、次のようなアルゴリズムに従って行うことができる。
【0078】
(アルゴリズム3)
(Step 1) 未修正のpq素子のうち、最も出力側から遠いものを選択する。選択されたpq素子をEGと記す。pq素子EGにより表される部分関数をG(H(X1),X2)とする。ここで、(X1, X2)⊆XかつX1∩X2=φである。(X1,X2)に対する入力ベクトルを(a1, a2)とする。但し、pq素子EGが最も出力側から遠い場合は、X1=φ, H(X1)=φとする。
【0079】
(Step 2) e0=G(H(a1), a2)とする。pq素子EGが最も出力側の場合、e=c。そうでない場合、e0 ≠ 0ならばe=e0、e0=0ならばpq素子EGで可能な出力値のうち、未使用の正の出力値で、最小のものをeとする。
【0080】
(Step 3) pq素子EGに記憶されたLUTの出力ベクトルのうち、入力ベクトル(H(a1), a2)に対応する出力ベクトルをG(H(a1),a2)=eとする。
【0081】
(Step 4) 未修正のpq素子が残っていれば、Step 1に戻る。そうでなければ、処理を終了する。
(アルゴリズム終り)
【0082】
上記アルゴリズムを一般のpq素子の多段論理関数の場合に拡張するのは容易である。一般のpq素子の多段論理関数の場合は次のようになる。
【0083】
(アルゴリズム4)
(Step 1) 素子数がsのpq回路網は、関数分解をs-1回繰り返し適用して構成できる。各関数分解で、入力側から順にpq素子を抽出し、素子に1からrまで番号を付与する。出力の素子の番号はsである。番号1の素子E1は、出力から最も離れている。入力変数Xに対する入力ベクトルをaとする。番号1のpq素子E1をEGとする。

【0084】
(Step 2) 多段論理回路に入力ベクトルaを入力する。このときのEGの出力ベクトルをe0とする。
【0085】
(Step 3) pq素子EGが最も出力側の場合、e=c。そうでない場合、e0≠0ならばe=e0、e0=0ならばpq素子EGで可能な出力値のうち、未使用の正の出力値で、最小のものをeとする。
【0086】
(Step 4) pq素子EGに記憶されたLUTの出力ベクトルのうち、入力ベクトルaに対応する出力ベクトルをeとする。
【0087】
(Step 5) EGが最も出力側のpq素子ならば、処理を終了する。そうでなければ、Step 1で順序づけた、EGの次のpq素子をEGとして、Step 2に戻る。
(アルゴリズム終り)
【0088】
以上のような登録ベクトルの削除と登録ベクトルの追加を行うことにより、アドレス生成関数のアドレス表を変化させた場合におけるpq素子の多段論理回路の再構成が可能となる。pq素子の多段論理回路がLUTカスケードの場合、セル数及び登録ベクトル数(アドレス数)に比例する時間で、アドレス表のアドレスの追加及び除去が可能となる。
【0089】
〔2〕本発明の構成及び作用
本発明に係る多段論理回路の再構成装置の第1の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。
【0090】
この構成によれば、
(1)まず、素子選択手段は未修正のpq素子のうち出力側に最も近いpq素子EGから順次選択する。
(2)次に、対応検査手段は、pq素子EGの入力ベクトルbに対する出力ベクトルcが入力ベクトルbと一対一対応か否かを検査する。
(3)次に、入力ベクトルbが前記出力ベクトルcに一対一に対応する場合には、削除修正手段は、pq素子EGのLUTにおいて、入力ベクトルbに対する出力値を無効値に書き換え、当該pq素子EGを修正済みとする。
【0091】
以上のような(1)~(3)の処理を繰り返すことにより、上述のアルゴリズム1又は2で説明したように、pq素子の多段論理回路において、入力ベクトルbに対する出力ベクトルF(b)を無効値に変更する論理変更を行うことができる。
【0092】
ここで、「多段論理回路」とは、上述したような複数のpq素子がカスケード状又は樹形状に接続した論理回路であり、LUTカスケード論理回路も含まれる。「無効値」とは、出力ベクトルF(b)が無効であることを表す値であり、通常は0とされるが、必ずしもそれに限られるものではない。
【0093】
本発明に係る多段論理回路の再構成装置の第2の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。
【0094】
この構成によれば、
(1)まず、素子選択手段は、未修正のpq素子のうち出力側から最も遠いpq素子EGから順次選択する。
(2)次に、素子選択手段が選択したpq素子EGが最も出力側ではない場合には、対応付手段は、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する。
(3)一方、素子選択手段が選択したpq素子EGが最も出力側の場合、追加修正手段は、pq素子EGのLUTにおいて、入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする。
以上のような(1)~(3)の処理を繰り返すことにより、上述のアルゴリズム3又は4で説明したように、pq素子の多段論理回路において、入力ベクトルbに対する出力ベクトルaを追加する論理変更を行うことができる。
【0095】
本発明に係る論理回路修正装置の第1の構成は、入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力することを特徴とする。
【0096】
この構成によれば、まず、主論理回路に入力変数Xとして入力ベクトルbが入力された場合、主論理回路は目的論理関数を演算し、出力ベクトルQ(b)を出力する。一方、アドレス生成回路は、入力ベクトルbに対してアドレス生成関数F(b)を演算する。入力ベクトルbが対象入力ベクトルbiであれば、アドレス生成回路は、アドレスAiを出力する。このアドレスAiは、補助メモリに入力される。補助メモリは、アドレスAiに対して修正用ベクトルPiを出力する。そして、修正手段は、修正用ベクトルPiと出力ベクトルQ(bi)に基づいて、修正出力ベクトルQ'(bi)を出力する。これにより、目的論理関数の出力値の変更が行われる。尚、入力ベクトルbが対象入力ベクトルbi以外の場合には、アドレス生成回路は、アドレスAiを出力しないため、補助メモリは修正用ベクトルPiを出力しない。従って、修正手段は、出力ベクトルQ(bi)の修正を行うことなく、出力ベクトルQ(bi)がそのまま出力される。
【0097】
本発明においては、アドレス生成回路としてpq素子の多段論理回路を使用するため、上に説明したように少ないメモリ容量でアドレス生成回路を実現することが可能である。従って、論理回路修正装置の実装面積を小さくでき、省電力化も図られる。また、上述したアルゴリズム1,2及びアルゴリズム3,4により、アドレス生成回路の論理変更も可能であり、要求に応じて主論理回路の出力を自在に修正することができる。
【0098】
また、本発明に係る論理回路修正装置の場合、アドレス生成回路の再構成を行う際に、pq素子(メモリ)の内容を書き換えるのみであり、配線経路の変更は行う必要がない。従って、配線遅延の影響などを考慮する必要がなく容易にアドレス生成回路の変更を行うことができる。更に、配線の変更を伴わないことから、主論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。
【0099】
本発明に係る論理回路修正装置の第2の構成は、前記第1の構成において、前記修正用ベクトルPiは、対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)との排他論理和が、前記修正出力ベクトルQ'(bi)となる値に設定され、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し、それ以外の場合は0を出力するものであり、
前記修正手段は、前記補助メモリの出力値と前記主論理回路との排他論理和演算を行うEXORゲートであることを特徴とする。
【0100】
本発明に係る論理回路修正装置の第3の構成は、前記第1の構成において、前記修正手段は、前記主論理回路及び前記補助メモリの出力段にそれぞれ設けられたトライ・ステート・バッファであり、
前記アドレス生成回路は、前記入力変数Xに対して、当該入力変数Xの値がいずれの前記対象入力ベクトルbiとも等しくない場合には、無効値を出力するものであり、
前記主論理回路の出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となり、
前記補助メモリの出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となることを特徴とする。
【0101】
本発明に係る論理回路修正装置の第4の構成は、前記第1乃至3の何れか一の構成において、前記補助メモリは、前記アドレス生成回路の最終段のpq素子であることを特徴とする。但し、最終段の素子の出力数は、q以上になってもよいと考える。
【0102】
本発明に係る論理回路修正装置の第5の構成は、前記第1乃至4の何れか一の構成において、前記アドレス生成回路において、入力ベクトルbに対する前記アドレス生成関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。
【0103】
本発明に係る論理回路修正装置の第6の構成は、前記第1乃至4の何れか一の構成において、前記アドレス生成回路において、前記アドレス生成関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。
【0104】
本発明に係る多段論理回路の再構成方法の第1の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択ステップと、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査ステップと、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正ステップと、
を繰り返し実行することを特徴とする。
【0105】
本発明に係る多段論理回路の再構成方法の第2の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択ステップと、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付ステップと、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正ステップと、を繰り返し実行することを特徴とする。
【0106】
本発明に係る再構成可能多段論理回路の第1の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記pq素子のうち出力側に最も近いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記pq素子EGを修正済みとするとともに、当該pq素子EGのLUTにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。
【0107】
この構成により、上述したとおり、再構成回路はpq素子(メモリ)の内容を書き換えるのみで、容易に目的論理関数F(X)の出力ベクトルF(b)を削除することができる。また、配線の変更を伴わないことから、論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。
【0108】
本発明に係る再構成可能多段論理回路の第1の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶された複数のpq素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能多段論理回路であって、
前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記pq素子のうち出力側から最も遠いpq素子EGから順次選択する素子選択手段と、
前記pq素子EGが最も出力側ではない場合において、当該pq素子EGを修正済みとするとともに、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記pq素子EGが最も出力側の場合において、前記pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該pq素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。
【0109】
この構成により、上述したとおり、再構成回路はpq素子(メモリ)の内容を書き換えるのみで、容易に目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更を行うことができる。また、配線の変更を伴わないことから、論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。
【発明の効果】
【0110】
以上のように、本発明に係る多段論理回路の再構成装置によれば、pq素子で構成される多段論理回路の論理変更に伴う再構成を、短時間に行うことができる。また、再構成処理は少ない計算量で短時間に行うことができ、再構成計算に必要とされるメモリ容量も小さいため、チップ内に専用回路として組み込むことが可能である。
【0111】
また、本発明に係る論理回路修正装置によれば、アドレス生成回路としてpq素子の多段論理回路を使用するため、上述したように少ないメモリ容量でアドレス生成回路を実現することが可能である。従って、論理回路修正装置の実装面積を小さくでき、省電力化も図られる。また、アドレス生成回路の論理変更も可能であり、要求に応じて主論理回路の出力を自在に修正することができる。
【図面の簡単な説明】
【0112】
【図1】アドレス生成論理関数Fの関数分解を示す図である。
【図2】pq素子によるアドレス生成回路(p=10)の例を示す図である。
【図3】pq素子によるアドレス生成回路(p=11)の例を示す図である。
【図4】pq素子によるアドレス生成回路(p=12)の例を示す図である。
【図5】本発明の実施例1に係る再構成可能な多段論理回路の構成を表す図である。
【図6】s個のpq素子E(1), E(2), …, E(s)が直列に接続されたカスケード論理回路を示す図である。
【図7】再構成装置1による目的論理関数F(X)の登録ベクトルの削除処理を表すフローチャートである。
【図8】再構成装置1による目的論理関数F(X)の登録ベクトルの追加処理を表すフローチャートである。
【図9】例5のアドレス生成関数F(X)を実現するLUTカスケード論理回路である。
【図10】本発明の実施例2に係る論理回路修正装置20の構成を示す図である。
【図11】本発明の実施例3に係る論理回路修正装置20の構成を示す図である。
【図12】本発明の実施例4に係る再構成可能な多段論理回路の構成を表す図である。
【図13】Xilinx社のFPGAで用いられている4入力LUTである。
【図14】4入力LUTを3個用いた12入力1出力の回路である。
【図15】LUTカスケード論理回路を一般的に表したものである。
【図16】参照テーブル9のテーブルの例である。
【図17】インデックス・テーブルの例である。
【図18】実施例4に係る再構成可能な多段論理回路の登録ベクトルの追加処理のフローチャートである。
【図19】実施例4に係る再構成可能な多段論理回路の登録ベクトルの削除処理のフローチャートである。
【図20】特許文献1に記載の論理回路修正装置103の構成を示す図である。
【符号の説明】
【0113】
1,1’ 再構成回路
2 素子選択手段
3 素子選択手段
4 対応検査手段
5 削除修正手段
6 対応付手段
7 追加修正手段
8 インデックス・テーブル
9 参照テーブル
10 多段論理回路
11 入力データバス
12 出力データバス
13 pq素子
20 論理回路修正装置
21 アドレス生成回路
22 補助メモリ
23 修正回路
24 EXORゲート
30 主論理回路
31 入力バス
32 出力バス
41_0~41_15 Dフリップ・フロップ(DFF)
42 マルチプレクサ(MUX)
43 クロック線
44 登録値入力線
44 データ入力線
【発明を実施するための最良の形態】
【0114】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例1】
【0115】
図5は、本発明の実施例1に係る再構成可能な多段論理回路の構成を表す図である。この再構成可能な多段論理回路は、多段論理回路10と再構成装置1とが組み合わされたシステムとして構成されている。再構成回路1は、多段論理回路10の論理変更に伴い、多段論理回路10の再構成を行う装置である。
【0116】
多段論理回路10は、入力変数をXとする目的論理関数F(X)の演算を行う論理回路である。この多段論理回路10は、複数のpq素子13を備えている。各pq素子13には、目的論理関数F(X)を関数分解して得られる部分関数のLUTが記憶されている。また、それぞれのpq素子13は、各部分関数の入出力の接続関係に従って回路的に接続されている。多段論理回路10の構造としては、LUTカスケードや図2~図4に示したようなpq回路網などを用いることができる。
【0117】
入力変数Xはn次元の2値ベクトルの変数である。目的論理関数F(X)の出力変数Yはm次元の2値ベクトルの変数である。入力変数Xは2個の値を取り得る。そのうちのk個(k<2)の入力ベクトルを「登録ベクトル(registered vector)」と呼ぶ。それ以外のベクトルを「無効ベクトル(invalid vector)」と呼ぶ。
【0118】
多段論理回路10の入力データバス11からは、入力変数Xとして入力ベクトルbが入力される。また、多段論理回路10の出力データバス12からは、出力変数Y=F(X)として出力ベクトルaが出力される。
【0119】
再構成回路1は、素子選択手段2,3、対応検査手段4、削除修正手段5、対応付手段6、追加修正手段7、及び多段論理回路10を備えている。
【0120】
目的論理関数F(X)の入力ベクトルbに対する出力ベクトルF(b)を無効値にする論理変更に伴い、削除処理が実行され、多段論理回路10の再構成が行われる。この削除処理において、素子選択手段2は、未修正の前記pq素子13を、出力側に最も近いpq素子EGから、順次選択する。対応検査手段4は、pq素子EGのLUTにおいて、入力ベクトルbが出力ベクトルcに一対一に対応しているか否か検査する。削除修正手段5は、pq素子EGのLUTにおいて、入力ベクトルbが出力ベクトルcに一対一に対応している場合に、入力ベクトルbに対する出力値を無効値に書き換え、当該pq素子EGを修正済みとする。
【0121】
一方、目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、追加処理が実行され、多段論理回路10の再構成が行われる。この追加処理において、素子選択手段3は、未修正のpq素子13を、出力側から最も遠いpq素子EGから、順次選択する。対応付手段6は、pq素子EGが最も出力側ではない場合、当該pq素子EGを修正済みとする。更にこの場合において、対応付手段6は、当該pq素子EGのLUTの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値ならば、当該出力ベクトルcを、当該pq素子の出力ベクトルとして使用していないベクトル値に変更する。追加修正手段7は、pq素子EGが最も出力側の場合、pq素子EGのLUTの入力ベクトルbに対する出力値を出力ベクトルaに書き換え、当該pq素子EGを修正済みとする。
【0122】
以上のように構成された本実施例1に係る多段論理回路の再構成回路1について、以下その動作を説明する。
【0123】
尚、以下の説明において、多段論理回路10は、図6に示したようなs個のpq素子E(1), E(2), …, E(s)が直列に接続されたカスケード論理回路とする。各pq素子は、入力側からE(1), E(2), …, E(s)の順に接続されている。
【0124】
入力変数をXとする。入力変数Xの分割をX=(X1,X2,…,Xs)とする。また、入力変数Xに対する目的論理関数F(X)の出力変数をY=F(X)とする。目的論理関数F(X)を次式(11)のように部分関数G1,G2,…,Gsに関数分解する。式(11)においてUi(i=1,2,…,s-1)は中間変数である。
【0125】
【数11】
JP0004742281B2_000016t.gif

【0126】
pq素子E(i)(i=1,2,…,s)には、中間関数GiのLUTが記憶されている。pq素子E(1)は、入力変数X1が入力される。それに対し、pq素子E(1)は出力変数U1=G1(X1)を出力する。pq素子E(i)(i=2,3,…,s)は、前段のpq素子E(i-1)の出力変数Ui-1と入力変数Xiが入力される。それに対し、pq素子E(i)は出力変数Ui=Gi(Xi, Ui-1)を出力する。また、pq素子E(s)の出力変数Usは出力変数Yである。
【0127】
最初に、目的論理関数F(X)の登録ベクトルの削除処理について説明する。図7は、再構成回路1による目的論理関数F(X)の登録ベクトルの削除処理を表すフローチャートである。
【0128】
ここでは、目的論理関数F(X)の登録ベクトルbを削除する論理変更に伴う、多段論理回路10の再構成について説明する。尚、入力変数Xの部分変数Xiに対応する入力ベクトルbの部分値をbiと記す。
【0129】
まず、ステップS1において、削除する登録ベクトルbが入力されると、素子選択手段2はインデックスiをsに設定する。インデックスiはpq素子の選択番号を示すインデックスである。これにより、最も出力側のpq素子E(s)が選択される。
【0130】
次に、ステップS2において、素子選択手段2は、pq素子E(i)のLUTを読み出す。
【0131】
次に、ステップS3において、削除修正手段5は、読み出されたLUTにおいて、入力ベクトルbに対応する出力ベクトルui(b)を0とする。入力ベクトルbに対応する出力ベクトルui(b)は、前段のpq素子E(i-1)の出力ベクトルui-1(b)及び部分値biに対応する出力ベクトルである。前段のpq素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路10に入力ベクトルbを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。
【0132】
次に、ステップS4において、修正されたLUTをpq素子E(i)に書き込むことにより、pq素子E(i)を更新する。
【0133】
次に、ステップS5において、素子選択手段2は、インデックスiが2以上であるか否かを判定する。インデックスiが1の場合には、登録ベクトルの削除処理を終了する。そうでない場合には、次のステップS6に移行する。
【0134】
ステップS6において、素子選択手段2は、選択番号を示すインデックスiを1だけデクリメントする。
【0135】
次に、ステップS7において、素子選択手段2は、pq素子E(i)のLUTを読み出す。
【0136】
次に、ステップS8において、対応検査手段4は、pq素子E(i)の入力ベクトルbに対する出力ベクトルui(b)を抽出する。入力ベクトルbに対応する出力ベクトルui(b)は、前段のpq素子E(i-1)の出力ベクトルui-1(b)及び部分値bi(i=1の場合は、部分値bi)に対応する出力ベクトルである。前段のpq素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路10に入力ベクトルbを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。
【0137】
次に、ステップS9において、対応検査手段4は、出力ベクトルui(b)に対応する入力ベクトルが、入力ベクトルb以外にもあるか否かを判定する。これは、LUTの出力値を調べ、出力ベクトルui(b)と同じ値が2個以上あるか否かを検査すればよい。対応する入力ベクトルが2個以上あった場合には、登録ベクトルの削除処理を終了する。そうでない場合には、次のステップS3に戻る。
【0138】
以上の一連の処理により、目的論理関数F(X)の登録ベクトルbを削除する論理変更に伴う多段論理回路10の再構成を行うことができる。この処理は、各pq素子E(i)のLUTの読み出しと書き換えのみであり、高速に実行することができる。また、複雑な演算処理も必要としないため、素子選択手段2、対応検査手段4、及び削除修正手段5は簡単な回路で実現することができる。
【0139】
次に、目的論理関数F(X)の登録ベクトルの追加処理について説明する。図8は、再構成回路1による目的論理関数F(X)の登録ベクトルの追加処理を表すフローチャートである。
【0140】
ここでは、目的論理関数F(X)の登録ベクトルbを追加する論理変更に伴い、多段論理回路10の再構成を行う。登録ベクトルbに対応する目的論理関数F(X)の出力ベクトルをaとする。尚、入力変数Xの部分変数Xiに対応する入力ベクトルbの部分値をbiと記す。
【0141】
まず、ステップS11において、追加する登録ベクトルb及び出力ベクトルをaが入力されると、素子選択手段3は、pq素子の選択番号を示すインデックスiを1に設定する。これにより、最も入力側のpq素子E(1)が選択される。
【0142】
次に、ステップS12において、素子選択手段3は、pq素子E(i)のLUTを読み出す。
【0143】
次に、ステップS13において、対応付手段6は、インデックスiが最大値sか否かを検査する。i=sの場合にはステップS20に移行し、そうでない場合には次のステップS14に移行する。
【0144】
ステップS14において、対応付手段6は、読み出されたLUTにおいて、入力ベクトルbに対応する出力ベクトルui(b)を計算する。入力ベクトルbに対応する出力ベクトルui(b)は、前段のpq素子E(i-1)の出力ベクトルui-1(b)及び部分値bi(i=1の場合は、部分値bi)に対応する出力ベクトルである。前段のpq素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路10に入力ベクトルbを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。
【0145】
次に、ステップS15において、対応付手段6は、出力ベクトルui(b)が0か否かを検査する。ui(b)≠0の場合には、ステップS19に移行する。s=0の場合には、次のステップS16に移行する。
【0146】
ステップS16において、対応付手段6は、pq素子E(i)のLUTの出力ベクトルを検査し、出力ベクトルとして未使用の値のうち最小の値(ベクトル)eを抽出する。
【0147】
次に、ステップS17において、対応付手段6は、pq素子E(i)のLUTの入力ベクトルbに対応する出力ベクトルui(b)をeに変更する。
【0148】
次に、ステップS18において、対応付手段6は、pq素子E(i)に、更新したLUTを書き込むことにより、pq素子E(i)を更新する。
【0149】
次に、ステップS19において、素子選択手段3は、選択番号を示すインデックスiを1だけインクリメントし、ステップS12に戻る。
【0150】
一方、ステップS13においてi=sの場合、ステップS20において、追加修正手段7は、pq素子E(i)のLUTの入力ベクトルbに対応する出力ベクトルui(b)を出力ベクトルaに変更する。
【0151】
そして、ステップS21において、追加修正手段7は、pq素子E(i)に、更新したLUTを書き込むことにより、pq素子E(i)を更新する。
【0152】
以上の一連の処理により、目的論理関数F(X)の登録ベクトルbを追加する論理変更に伴う多段論理回路10の再構成を行うことができる。この処理は、各pq素子E(i)のLUTの読み出しと書き換えのみであり、高速に実行することができる。また、複雑な演算処理も必要としないため、素子選択手段2及び削除修正手段5は簡単な回路で実現することができる。
【0153】
また、本実施例の多段論理回路10では、再構成はメモリの書き換えのみによって実行される。すなわち、多段論理回路10の再構成に伴う配線構造の変更はない。従って、再構成にあたり配線遅延の影響などをする必要がなく、容易に実行することができる。さらには、論理回路の動作期間中にリアルタイムで動的に論理回路の再構成を行うことも可能である。
【0154】
(例5)
(表5)に示したような5変数のアドレス生成関数F(X)を考える。
【0155】
【表5】
JP0004742281B2_000017t.gif

【0156】
入力変数Xの分割X=(X1,X2), X1=(x5, x4, x3, x2), X2=(x1)について関数分解F(X)=G(H(X1), X2)を行い、図9に示したような2つのpq素子から成るLUTカスケード論理回路によりアドレス生成関数F(X)を実現する。このとき、部分関数H, Gの真理値表は(表6),(表7)のようになる。入力側のpq素子には(表6)の部分関数Hの真理値表がLUTとして格納される。また、出力側のpq素子には(表7)の部分関数Gの真理値表がLUTとして格納される。(表6)(表7)の各行の左側に付された数字は、その行に対応する登録ベクトルのインデックスを表す。
【0157】
【表6】
JP0004742281B2_000018t.gif

【0158】
【表7】
JP0004742281B2_000019t.gif

【0159】
このアドレス生成関数F(X)について、登録ベクトルb7=(x5 x4 x3 x2 x1)=(11001)を追加する。(表8)は、登録ベクトルb7の真理値表を表す。登録ベクトルb7に対する出力ベクトルには(111)を割り当てることとする。
【0160】
【表8】
JP0004742281B2_000020t.gif

【0161】
次に、図8のフローチャートに示した方法に従って、各pq素子のLUTの書き換えを行う。まず、入力側のpq素子に格納された部分関数Hの入力ベクトルbに対応する出力ベクトルは、(表6)の(x5 x4 x3 x2)=(1100)の欄を参照すると、(h1, h2, h3)=(110)である。これは0ではないため、部分関数HのLUTは変化させない。このとき、入力ベクトルbは(表9)に示したように、(x5 x4 x3 x2)=(1100)の欄に対応付けられる。
【0162】
【表9】
JP0004742281B2_000021t.gif

【0163】
次に、出力側のpq素子に格納された部分関数Gについて考えると、入力ベクトルbに対応する部分関数Gの入力ベクトルは(h1, h2, h3 x1)=(1101)である。従って、(表10)に示したように、部分関数GのLUTに、(h1, h2, h3 x1 f1 f2 f3)=(1101111)を追加する。これにより、登録ベクトルb7の追加に伴う各pq素子の再構成が完了する。
【0164】
【表10】
JP0004742281B2_000022t.gif

【0165】
次に、登録ベクトルの削除に伴う各pq素子の再構成について考える。例として、(表5)のアドレス表に登録された登録ベクトルから、登録ベクトルb3=(01100)を削除する場合について考える。
【0166】
図7のフローチャートに示した方法に従って、まず出力側のpq素子のLUTの書き換えを行う。(表10)を参照すると、登録ベクトルb3に対する部分関数Gの入力ベクトルは、(h1, h2, h3 x1)=(0110)である。これに対応する出力ベクトルを(000)に変更し、出力側のpq素子のLUTを(表11)に示したように書き換える。
【0167】
【表11】
JP0004742281B2_000023t.gif

【0168】
次に、入力側のpq素子について考える。この場合、更新前の部分関数Gの真理値表(表10)を参照すると、前段のLUTの出力ベクトル(h1, h2, h3)が登録ベクトルb3に対する出力ベクトル(011)と同じで、非零の出力を持つ登録ベクトルとして、b3の他にb4=(01111)が存在する。従って、入力側のpq素子についてはLUTの書き換えは行われない。以上により、登録ベクトルb3の削除に伴う各pq素子の再構成が完了する。
【0169】
次に、さらに登録ベクトルb4=(01101)を削除する場合について考える。図7のフローチャートに示した方法に従って、まず出力側のpq素子のLUTの書き換えを行う。(表9)を参照すると、登録ベクトルb4に対する部分関数Gの入力ベクトルは、(h1, h2, h3 x1)=(0111)である。これに対応する出力ベクトルを(000)に変更し、出力側のpq素子のLUTを(表12)に示したように書き換える。
【0170】
【表12】
JP0004742281B2_000024t.gif

【0171】
次に、入力側のpq素子について考える。この場合、更新前の部分関数Gの真理値表(表11)を参照すると、前段のLUTの出力ベクトル(h1, h2, h3)が登録ベクトルb4に対する出力ベクトル(011)と同じで、非零の出力を持つ登録ベクトルは存在しない。従って、入力側のpq素子について、登録ベクトルb4に対応する部分関数Hの入力ベクトル(x5 x4 x3 x2)=(0111)に対する出力ベクトル(h1, h2, h3)= (100)を(000)に変更する。従って、入力側のpq素子のLUTは(表13)のように更新される。これにより、登録ベクトルb4の削除に伴う各pq素子の再構成が完了する。
【0172】
【表13】
JP0004742281B2_000025t.gif

(例終り)
【実施例2】
【0173】
図10は、本発明の実施例2に係る論理回路修正装置20の構成を示す図である。図10において、主論理回路30は、論理修正の対象となる論理回路であり、専用のLSI(ASIC)として構成されたメモリ、CPU等である。主論理回路30の入力変数をX=(x1 x2 … xn)(∈Bn, B={0,1})、出力変数をQ=Q(X)=(q1 q2 … qm)(∈Bm)とし、論理回路修正装置20により修正された出力変数をQ'=(q1' q2' … qm')(∈Bm)とする。主論理回路30は、入力変数Xに対して目的論理関数Q(X)を演算する。
【0174】
論理回路修正装置20は、入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路30の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する。論理回路修正装置20は、アドレス生成回路21、補助メモリ22、修正回路23、及び再構成回路1を備えている。尚、再構成回路1は、実施例1において説明した多段論理回路の再構成回路1と同様のものである。
【0175】
補助メモリ22は、各対象入力ベクトルbiに対応して、各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPi=(pi1 pi2 … pim)が所定のアドレスAiに登録されるメモリである。補助メモリ22は、修正用ベクトルPiが登録されたアドレスAiが入力された場合には、修正用ベクトルPiを出力し、それ以外の場合は、無効値として0を出力する。
【0176】
修正回路23は、補助メモリ22が出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び主論理回路30が出力する出力ベクトルQ(bi)に基づいて、修正出力ベクトルQi'を出力する。ここで、本実施例2においては、修正回路23は、主論理回路30の各出力線に対応して設けられたEXORゲート24により構成されている。各EXORゲート24は、出力ベクトルQの各成分q1 q2 … qmと、修正用ベクトルPiの各成分pi1 pi2 … pimとの排他論理和により、修正出力ベクトルQi'=(qi1' qi2' … qim')の演算を行う。
【0177】
【数12】
JP0004742281B2_000026t.gif

【0178】
従って、修正用ベクトルPiの値は、上記式(12)により目的とする修正出力ベクトルQi'が得られるような値に設定される。
【0179】
アドレス生成回路21は、入力変数Xとして入力される各入力ベクトルbに対して補助メモリ22のアドレスを出力する回路である。ここで、アドレス生成回路21は、各対象入力ベクトルbiに対しては修正用ベクトルPiが登録されたアドレスAiを出力し、それ以外の入力ベクトルbに対しては無効値(0)を出力するようなアドレス生成関数F(X)の演算を行う。
【0180】
また、アドレス生成回路21は、上述したようなpq素子を多段に結合して構成された多段論理回路によって構成されている。
【0181】
再構成回路1は、アドレス生成回路21が演算するアドレス生成関数F(X)の修正に伴い、アドレス生成回路21の各pq素子のLUTの再構成を行う。尚、再構成の方法に関しては、実施例1において述べた通りである。
【0182】
以上のように構成された本実施例2の論理回路修正装置20について、以下その動作を説明する。
【0183】
まず、入力変数Xとして、対象入力ベクトルbi以外の入力ベクトルbが入力された場合、アドレス生成回路21は出力ベクトルaとして0(無効値)を出力する。従って、補助メモリ22は、修正用ベクトルPとして0を出力する。各EXORゲート24は、主論理回路30の出力値qjと0との排他論理和、すなわち出力値qjを出力する。従って、この場合は出力ベクトルQは修正されず、そのまま出力されることになる。
【0184】
一方、入力変数Xとして、対象入力ベクトルbiが入力された場合、アドレス生成回路21は出力ベクトルaとして、修正用ベクトルPiが格納された補助メモリ22のアドレス値Aiを出力する。従って、補助メモリ22は、修正用ベクトルPとして修正用ベクトルPiを出力する。各EXORゲート24は、主論理回路30の出力値qjと修正用ベクトルの成分pijとの排他論理和qij'を出力する。これにより、出力ベクトルの修正が行われる。
【0185】
本実施例においては、アドレス生成回路21としてpq素子を多段に結合して構成された多段論理回路を使用したことで、論理回路修正装置20の実装面積を小さくすることが可能となる。また、論理変更が追加して行われた場合にも、再構成回路1を用いて容易にアドレス生成回路21の再構成を行うことができる。
【実施例3】
【0186】
図11は、本発明の実施例3に係る論理回路修正装置20の構成を示す図である。図11において、再構成回路1、アドレス生成回路21、補助メモリ22、及び主論理回路30は、図10と同様のものである。本実施例においては、補助メモリ22には、各対象入力ベクトルbiに対して修正出力ベクトルQi'がそのまま格納されている。また、補助メモリ22及び主論理回路30の出力段には、修正手段としてトライ・ステート・バッファ(図示せず)が設けられている。
【0187】
アドレス生成回路21は、入力バス31から入力される入力変数Xに対して、当該入力変数Xの値がいずれの対象入力ベクトルbiとも等しくない場合には、無効値を出力する。主論理回路30の出力段のトライ・ステート・バッファは、アドレス生成回路21の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となる。また、補助メモリ22の出力段のトライ・ステート・バッファは、アドレス生成回路21の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となる。
【0188】
これにより、入力変数Xの値が対象入力ベクトルbi以外の場合には、出力バス32には、主論理回路30の出力ベクトルが出力され、入力変数Xの値が対象入力ベクトルbiの場合には、出力バス32には、補助メモリ22の出力ベクトルが出力される。
【実施例4】
【0189】
図12は、本発明の実施例4に係る再構成可能な多段論理回路の構成を表す図である。図12において、図5と同様な構成部分については、同符号を付す。
【0190】
本実施例の再構成可能な多段論理回路においては、再構成回路1’に新たに、インデックス・テーブル8と参照テーブル9とが追加されている。
【0191】
多段論理回路10は、実施例1において説明したとおり、入力変数をXとする目的論理関数F(X)の演算を行う論理回路である。多段論理回路10は、複数のpq素子13が多段に接続された論理回路である。この、多段論理回路10の具体的な構造としては、複数のpq素子13がカスケード状に接続されたLUTカスケード論理回路(図6,図15参照)や、複数のpq素子13が樹形状に接続されたLUTツリー論理回路(図2~4参照)を用いることができる。
【0192】
再構成回路1は、この多段論理回路10の論理変更に伴って、多段論理回路10の再構成を行う回路である。再構成回路1は、素子選択手段2,素子選択手段3,対応検査手段4,削除修正手段5,対応付手段6,追加修正手段7,インデックス・テーブル8,及び参照テーブル9を備えている。素子選択手段2,素子選択手段3,対応検査手段4,削除修正手段5,追加修正手段7,及び対応付手段6については、実施例1で既に説明をした通りであるので、説明は省略する。
【0193】
尚、pq素子13は、必ずしもメモリを用いて構成する必要はなく、メモリと同様の機能を有する回路であればどのような回路を用いてもよい。
【0194】
例えば、図13は、Xilinx社のFPGAで用いられている4入力LUTである。この4入力LUTは、16個の同期型のDフリップ・フロップ41_0~41_15と、1つの16入力1出力のマルチプレクサ42を備えている。
【0195】
この4入力LUTでは、モードを切り替えることで、シフトレジスタとして使用でき、書き換えが可能である。
【0196】
図13(a)はSRL16モードであり、このモードではクロック線43から各DFF41_0~41_15にクロックが入力される。従って、DFF41_0~41_15はシフトレジスタとして機能する。この状態で登録値入力線44から登録データをシリアルに入力することにより、各DFF41_0~41_15に登録データが記憶される。
【0197】
一方、図13(b)は4入力LUTモードであり、このモードではクロック線43にクロックの入力はなく、この回路はLUTとして機能する。データ入力線45からMUX42に4ビットのデータが入力されると、MUX42は、その入力データに応じてDFF41_0~41_15の何れか一つを選択し、選択したDFFに記憶されたデータを出力する。従って、この回路は4入力1出力のLUTとして機能する。
【0198】
図14に、4入力LUTを3個用いた12入力1出力の回路を示す。図14に示すように、FPGA内部のマルチプレクサと組み合わせることで、複数のLUT の出力の論理積を計算できる。尚、この回路は1出力なので、複数ビットの出力を得たい場合には、図14の回路を必要なビット数だけ並列に並べればよい。
【0199】
pq素子13としては、図13に示したようなLUTを使用することも可能である。
【0200】
参照テーブル9は、各pq素子13毎に割り当て済みのレイル・ベクトル(rail vector)を保持するテーブルである。
【0201】
ここで、「レイル(rail)」とは、複数のpq素子が多段に接続された多段論理回路において、前段のpq素子の出力線のうち、後段のpq素子の入力に接続された接続線をいう。
【0202】
図15は、LUTカスケード論理回路を一般的に表したものである。図15のpq素子E(1)の出力線のうちpq素子E(2)の入力に接続されたものがレイルである。また、pq素子E(2)の出力線のうちpq素子E(3)の入力に接続されたものがレイルである。以下同様である。図2~4のLUTツリー論理回路についても、同様にレイルが定義される。
【0203】
また、「レイル・ベクトル」とは、あるpq素子の出力側のレイルに出力される出力変数のベクトルをいう。
【0204】
参照テーブル9の例を図16に示す。参照テーブル9は、多段論理回路10の各pq素子毎につずつ設けられる。1つのpq素子に対する参照テーブル9は、そのpq素子の各レイル・ベクトルとそれに対応する参照ベクトル数とのテーブルとで構成される。尚、「参照ベクトル数」とは、そのレイル・ベクトルを参照する登録ベクトルの個数である。
【0205】
インデックス・テーブル8は、ベクトルが登録済みであるか否かを記憶するテーブルである。インデックス・テーブル8は、1つだけ設けられる。図17に、インデックス・テーブルの例を示す。インデックス・テーブル9は、登録可能な各ベクトルに割り当てられたインデックスと、そのインデックスに対応する登録ベクトルが登録済み(使用されている)か否かを示す登録済フラグとで構成される。
【0206】
以上のように構成された本実施例に係る再構成可能な多段論理回路について、以下その登録ベクトルの追加・削除の動作について説明する。
【0207】
尚、ここでは説明を分かりやすくするため、多段論理回路10として、図6に示したようなLUTカスケード論理回路が用いられていることとする。
【0208】
(1)登録ベクトルの追加
本実施例の再構成可能な多段論理回路では、登録ベクトルを新たに追加する場合は、インデックス・テーブル8及び参照テーブル9を使用し、処理時間の短縮が図られる。
【0209】
図18は、実施例4に係る再構成可能な多段論理回路の登録ベクトルの追加処理のフローチャートである。
【0210】
まず、ステップS31において、登録する入力ベクトルbが、再構成回路1’に入力される。
【0211】
次に、ステップS32において、追加修正手段7は、インデックス・テーブル8を参照し、入力ベクトルbは多段論理回路10に登録済みか否かを検査する。ここで、インデックス・テーブル8の入力ベクトルbに対する登録済フラグが1の場合には終了する。
【0212】
次に、ステップS33において、素子選択手段3は、選択素子の番号を表すインデックスiを1に設定する。
【0213】
次に、ステップS34において、対応付手段6は、多段論理回路10に入力ベクトルbを入力し、pq素子E(i)の出力ベクトルu(b)を読み出す。
【0214】
次に、ステップS35において、対応付手段6は、出力ベクトルu(b)が0か否かを判定する。0の場合には、ステップS38に移行し、0以外の場合には次のステップS36に移行する。
【0215】
次に、ステップS36において、対応付手段6は、pq素子E(i)に対応する参照テーブル9を検索し、未参照のレイル・ベクトルaを1つ索出する。そして、ステップS36において、追加修正手段7は、pq素子E(i)の出力ベクトルu(b)がレイル・ベクトルaとなるようにpq素子E(i)のメモリ内容の書き換えを行う。
【0216】
ステップS38において、対応付手段6は、pq素子E(i)に対応する参照テーブルの登録ベクトルu(b)の参照ベクトル数を1だけインクリメントする。
【0217】
次に、ステップS39において、素子選択手段3は、選択素子の番号を表すインデックスiを1だけインクリメントする。
【0218】
次に、ステップS40において、素子選択手段3は、i=sか否かを判定する。i<sならばステップS34に戻り、i=sならば次のステップS41に進む。
【0219】
ステップS41において、追加修正手段7は、pq素子E(s)の出力ベクトルu(b)をF(b)とばるように、pq素子E(s)のメモリ内容の書き換えを行う。
【0220】
最後に、ステップS42において、追加修正手段7は、インデックス・テーブル8の登録ベクトルbに対する登録済フラグを1に設定して、登録ベクトル追加処理を終了する。
【0221】
(2)登録ベクトルの削除
図19は、実施例4に係る再構成可能な多段論理回路の登録ベクトルの削除処理のフローチャートである。
【0222】
まず、ステップS51において、削除する入力ベクトルbが、再構成回路1’に入力される。
【0223】
次に、ステップS52において、削除修正手段5は、インデックス・テーブル8を参照し、入力ベクトルbは多段論理回路10に登録済みであるか否かを検査する。インデックス・テーブル8の入力ベクトルbに対する登録済フラグが0の場合は、登録ベクトルの削除処理を終了する。
【0224】
次に、ステップS53において、素子選択手段2は、選択素子の番号を表すインデックスiをsに設定する。
【0225】
次に、ステップS54において、対応検査手段4は、多段論理回路10に入力ベクトルbを入力し、pq素子E(i)の出力ベクトルu(b)を読み出す。
【0226】
次に、ステップS55において、対応検査手段4は、pq素子E(i)に対応する参照テーブルの登録ベクトルu(b)の参照ベクトル数を1だけデクリメントする。但し、このとき登録ベクトルu(b)の参照ベクトル数が0の場合には、登録ベクトルu(b)の参照ベクトル数は0のままとする。
【0227】
次に、ステップS56において、削除修正手段5は、登録ベクトルu(b)の参照ベクトル数が0か否かを判定する。登録ベクトルu(b)の参照ベクトル数が0でないならばステップS58に戻り、0ならば次のステップS57に進む。
【0228】
ステップS57において、削除修正手段5は、pq素子E(i)の出力ベクトルu(b)が0となるように、pq素子E(i)のメモリ内容の書き換えを行う。
【0229】
ステップS58において、素子選択手段2は、選択素子の番号を表すインデックスiを1だけデクリメントする。
【0230】
次に、ステップS59において、素子選択手段2は、i=0か否かを判定する。i>0ならばステップS54に戻り、i=0ならば次のステップS60に進む。
【0231】
ステップS60において、削除修正手段5は、インデックス・テーブル8の登録ベクトルbに対する登録済フラグを0に設定して、登録ベクトル削除処理を終了する。
【0232】
以上の処理によって、多段論理回路10に登録ベクトルを1つ追加するのに必要なステップ数は、以下の式で見積もることができる。
【0233】
【数13】
JP0004742281B2_000027t.gif

【0234】
ここで、OP.CasはLUTカスケードにアクセスするために必要なステップ数、Acc.Memは参照テーブルにアクセスするために必要なステップ数、sはセル数、kは登録ベクトル数を示す。第1項は、上記登録ベクトルの追加処理のうちステップS31~S34の処理を行うのに必要なステップ数の見積りを示し、第2項はそれ以外の処理を行うのに必要なステップ数の見積りを示す。
【0235】
同様に、多段論理回路10から登録ベクトルを1つ削除するのに必要なステップ数は以下の式で見積もることができる。
【0236】
【数14】
JP0004742281B2_000028t.gif

【0237】
第1項は上記登録ベクトルの削除処理のうちステップS51~S54の処理を行うのに必要なステップ数の見積りを示し、第2項はそれ以外の処理を行うのに必要なステップ数の見積りを示す。
【0238】
式(13),(14)より、多段論理回路10がLUTカスケード論理回路の場合、登録ベクトルの追加に要するステップ数はsとkに、削除に要するステップ数はsにほぼ比例する事が分かる。
図面
【図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