(57)【特許請求の範囲】
【請求項１】
少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路をコンピュータが最適化するための論理回路最適化方法であって、
前記コンピュータに含まれる制約値格納手段が、予め、遅延時間の制約値である目標遅延値を定めて格納しておくステップと、
前記コンピュータに含まれるフリップフロップ抽出手段が、前記論理回路に含まれる前記フリップフロップを抽出して該フリップフロップの情報を格納するステップと、
前記コンピュータに含まれている階層変更手段が、格納されている前記フリップフロップの情報を読み出し、前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にした変更後の前記論理回路を格納するステップと、
前記コンピュータに含まれる階層回路マージ手段が、格納されている前記変更後の論理回路を読み出し、同一の前記フリップフロップを含む前記階層回路を結合し、結合後の論理回路を格納するステップと、
前記コンピュータに含まれる論理最適化実行手段が、格納されている前記結合後の論理回路と前記目標遅延値を読み出し、前記遅延時間が前記目標遅延値を満足するように前記各階層回路を最適化し、最適化の結果得られた論理回路を格納するステップを有する論理回路最適化方法。
【請求項２】
少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路を最適化する論理回路最適化装置であって、
予め、遅延時間の制約値である目標遅延値を記憶している制約値格納手段と、
前記論理回路に含まれる前記フリップフロップを抽出するフリップフロップ抽出手段と、
前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にする階層変更手段と、
同一の前記フリップフロップを含む前記階層回路を結合する階層回路マージ手段と、
前記遅延時間が前記目標遅延値を満足するように前記各階層回路を最適化する論理最適化実行手段を有する論理回路最適化装置。
【請求項３】
少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路を最適化するための論理回路最適化プログラムを記録した記録媒体であって、
前記論理回路に含まれる前記フリップフロップを抽出する処理と、
前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にする処理と、
同一の前記フリップフロップを含む前記階層回路を結合する処理と、
前記遅延時間が、予め定められた遅延時間の制約値である目標遅延値を満足するように前記各階層回路を最適化する処理をコンピュータに実行させるための論理回路最適化プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、回路図やハードウェア記述言語で表現された論理回路の最適化方法に関し、特に、階層構造を有する論理回路の最適化方法に関する。
【０００２】
【従来の技術】
ハードウェア記述言語等の情報から論理回路を自動生成する際、遅延時間や最大面積などの制約条件（制約値）を満足するように最適化が行われる。このとき、最適化を行う対象の回路が複数の階層からなる階層構造を有する場合には、最適化において目標とする遅延時間や最大面積等の制約値が与えられる。
【０００３】
従来の論理回路の最適化方法として、目標とする遅延時間を与えて最適化する場合に各階層の入力端子とフリップフロップの間およびフリップフロップと出力端子の間の遅延を考慮して制約値を作成し、作成した制約値を各階層の入力端子および出力端子に与えて各階層毎に最適化処理を行うものがある。これによって各階層の論理回路が最適化されることで全体回路が最適化される。
【０００４】
【発明が解決しようとする課題】
従来の最適化方法は、各階層の中にあるフリップフロップを考慮して遅延時間の制約値を定めている。したがって、階層の中にフリップフロップを介さないパスがあると制約値に意味が無くなり、最適化処理を正常に行うことができない。そのためそのパスに着目して、人手によって階層破壊や制約値の再作成などを行っていた。
【０００５】
本発明の目的は、階層構造を有する論理回路を容易かつ適切に最適化するための論理回路の最適化方法を提供することである。
【０００６】
【課題を解決するための手段】
上記目的を達成するために、本発明の論理回路最適化方法は、少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路をコンピュータが最適化するための論理回路最適化方法であって、前記コンピュータに含まれる制約値格納手段が、予め、遅延時間の制約値である目標遅延値を定めて格納しておくステップと、前記コンピュータに含まれるフリップフロップ抽出手段が、前記論理回路に含まれる前記フリップフロップを抽出して該フリップフロップの情報を格納するステップと、前記コンピュータに含まれている階層変更手段が、格納されている前記フリップフロップの情報を読み出し、前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にした変更後の前記論理回路を格納するステップと、前記コンピュータに含まれる階層回路マージ手段が、格納されている前記変更後の論理回路を読み出し、同一の前記フリップフロップを含む前記階層回路を結合し、結合後の論理回路を格納するステップと、前記コンピュータに含まれる論理最適化実行手段が、格納されている前記結合後の論理回路と前記目標値を読み出し、前記遅延時間が前記目標遅延値を満足するように前記各階層回路を最適化し、最適化の結果得られた論理回路を格納するステップを有している。
【０００９】
また、本発明の論理回路最適化装置は、少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路を最適化する論理回路最適化装置であって、予め、遅延時間の制約値である目標遅延値を記憶している制約値格納手段と、前記論理回路に含まれる前記フリップフロップを抽出するフリップフロップ抽出手段と、前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にする階層変更手段と、同一の前記フリップフロップを含む前記階層回路を結合する階層回路マージ手段と、前記遅延時間が前記目標遅延値を満足するように前記各階層回路を最適化する論理最適化実行手段を有している。
【００１１】
また、本発明の記録媒体は、少なくとも１つのフリップフロップを含み、階層構造に構成された論理回路を最適化するための論理回路最適化プログラムを記録した記録媒体であって、前記論理回路に含まれる前記フリップフロップを抽出する処理と、前記論理回路の階層構造を、前記論理回路の外部出力端子または抽出された前記フリップフロップの入力から、信号の流れの逆方向に前記論理回路の外部入力端子または他の前記フリップフロップに到達するまで前記論理回路をたどり、前記フリップフロップに到達した場合に経由した論理素子および到達した前記フリップフロップで構成される階層回路からなる構造に変更し、前記階層回路内にフリップフロップを経由しないパスが無い状態にする処理と、同一の前記フリップフロップを含む前記階層回路を結合する処理と、前記遅延時間が、予め定められた遅延時間の制約値である目標遅延値を満足するように前記各階層回路を最適化する処理をコンピュータに実行させるための論理回路最適化プログラムを記録している。
【００１２】
【発明の実施の形態】
本発明の実施の形態について図面を参照して詳細に説明する。
【００１３】
まず、本発明の一実施形態の最適化方法を実現する最適化装置の構成について説明する。
【００１４】
図１を参照すると、最適化装置は論理回路格納部１と制約値格納部２とフリップフロップ抽出部３とフリップフロップ格納部４と階層変更部５と階層回路格納部６と階層回路マージ部７とマージ結果格納部８と論理最適化実行部９と最適化結果格納部１０とを有している。
【００１５】
論理回路格納部１は、回路図やハードウェア記述言語で表現された最適化対象の論理回路の情報を記憶する。
【００１６】
制約値格納部２は、遅延時間の制約値である目標遅延値など、論理回路格納部１に記憶された論理回路情報に対する最適化処理における制約値を記憶する。
【００１７】
フリップフロップ抽出部３は、論理回路格納部１の論理回路情報からフリップフロップの情報を抽出してフリップフロップ格納部４に格納する。
【００１８】
フリップフロップ格納部４は、フリップフロップ抽出部３で抽出されたフリップフロップの情報を記憶する。
【００１９】
階層変更部５は、論理回路格納部１に格納されている論理回路情報の階層構造を、フリップフロップ格納部４に格納されているフリップフロップの入力が切り口となるように階層変更することで、階層の回路内にフリップフロップを経由しないパスが無い状態にして階層回路格納部６に格納する。
【００２０】
階層回路格納部６は、階層変更部５で階層変更された論理回路情報を記憶する。
【００２１】
階層回路マージ部７は、階層回路格納部６に格納されている階層回路の中で同じフリップフロップを含む階層回路を抽出し、それらの階層回路を結合（マージ）して１つの階層回路にし、マージ結果格納部８に格納する。階層回路マージ部７の処理によって、論理回路は、フリップフロップの入力端子、論理回路の外部入力端子または論理回路の外部出力端子を切り口とし、それら切り口によって階層回路に分割された階層構造に変更される。また、この階層構造においては複数の階層回路に含まれる部分が論理回路の中に無い状態である。
【００２２】
マージ格納部８は、階層回路マージ部７で必要に応じて階層回路がマージされた論理回路情報を記憶する。
【００２３】
論理最適化実行部９は、マージ結果格納部８に格納された各階層回路の入力端子における到達時間の制約値として“０ｎｓ”を与え、出力端子に制約値格納部２に格納された目標遅延値を与えて最適化処理を実行する。そして、最適化処理の結果得られた論理回路の情報を最適化結果格納部１０に格納する。
【００２４】
最適化結果格納部１０は、最適化された論理回路情報を記憶する。
【００２５】
次に、本実施形態の最適化装置の動作の一例として、図２に示した論理回路を最適化の対象とした場合の動作について説明する。
【００２６】
論理回路格納部１には図２に示した回路の論理回路情報が記憶されている。論理回路は少なくとも１つの階層回路が必要に応じて互いに接続された構成である。また、各階層回路は同期動作するフリップフロップと論理素子とが接続されて構成されている。
【００２７】
図２の例では、階層回路ＳＵＢ１がフリップフロップＦＦ１と論理素子Ｇ１とで構成されている。また、階層回路ＳＵＢ２がフリップフロップＦＦ２，３と論理素子Ｇ２，３，４とで構成されており、階層回路ＳＵＢ３がフリップフロップＦＦ４と論理素子Ｇ５とで構成されている。そして、階層回路ＳＵＢ１，２，３によって全体の論理回路が構成されている。なお、図中で論理素子のブロック内に記載された値（例えば、５ｎｓ（ナノセカンド））はその論理素子の遅延時間を示している。
【００２８】
また、制約値格納部２に記憶された最適化の目標遅延値は、ここでは、一例として“１０ｎｓ”であるとする。
【００２９】
最適化処理が開始されると、まず、フリップフロップ抽出部３が、論理回路格納部１に格納されている論理回路情報からフリップフロップＦＦ１，２，３，４の情報を取り出してフリップフロップ格納部４に格納する。
【００３０】
次に、階層変更部５が、論理回路格納部１に記憶された論理回路において、フリップフロップ格納部４に格納されたフリップフロップＦＦ１，２，３，４の入力（図２中の切り口ＩＦ１，２，３，４）と、外部出力端子ｔ，ｕ（図２中の切り口ＩＦ５，６）を切り口として設定し、各切り口ＩＦ１，２，…，６から信号の流れをさかのぼる方向に、他のフリップフロップの出力端子あるいは論理回路の外部入力端子に辿り着くまで回路を辿る（トレースする）。
【００３１】
フリップフロップの出力端子に辿り着いた場合は、そのフリップフロップとトレースで経由した論理素子とで新たな階層回路を構成する。また、外部入力端子に辿り着いた場合は何もしない。
【００３２】
図２の例では、切り口ＩＦ１と切り口ＩＦ２では、入力信号方向にトレースするとそれぞれ外部入力端子ｒ，ｓに辿り着くため何もしない。
【００３３】
切り口ＩＦ３では、入力信号方向にトレースすると論理素子Ｇ２，１を経由してフリップフロップＦＦ１の出力端子に辿り着くので、フリップフロップＦＦ１と論理素子Ｇ１，２で新たな階層回路ＳＵＢ１′を構成する。また、切り口ＩＦ４では、入力信号方向にトレースすると論理素子Ｇ５，４，２，１を経由して２つのフリップフロップＦＦ１，３の出力端子に辿り着くので、フリップフロップＦＦ１，３と論理素子Ｇ１，２，４，５で新たな階層回路ＳＵＢ２′を構成する。さらに、切り口ＩＦ５では、入力信号方向にトレースすると論理素子Ｇ３を経由してフリップフロップＦＦ２の出力端子に辿り着くので、フリップフロップＦＦ２と論理素子Ｇ３で新たな階層回路ＳＵＢ３′を構成する。切り口ＩＦ６では、入力信号方向にトレースするとフリップフロップＦＦ４の出力端子に辿り着くので、フリップフロップＦＦ４で新たな階層回路ＳＵＢ４′を構成する。
【００３４】
そして、階層変更部５は、上記のようにして構成された図３に示す新たな階層回路ＳＵＢ１′，２′，３′，４′を階層回路格納部６に格納する。
【００３５】
階層回路マージ部７は、階層回路格納部６に記憶された階層回路ＳＵＢ１′，２′，３′，４′のうち、同じフリップフロップを含む階層回路を抽出して、それらを１つの階層回路にマージする。ここでは、階層回路ＳＵＢ１′と階層回路ＳＵＢ２′が共にフリップフロップＦＦ１を含むのでそれらをマージする。階層回路ＳＵＢ１′と階層回路ＳＵＢ２′をマージした結果の階層回路は階層回路ＳＵＢ２′と同じものになる。そして、階層回路マージ部７は階層回路をマージして得られた図４に示す論理回路の情報をマージ結果格納部８に格納する。
【００３６】
論理最適化実行部９は、マージ結果格納部８に記憶された図４の論理回路において、各階層回路ＳＵＢ２′，３′，４′の入力端子ｒ，ｓ，ｃ′，ｄ′に到達時間の制約値として“０ｎｓ”を与える。また、出力端子ａ′，ｂ′，ｔ，ｕに到達期待時間の制約値として、制約値格納部２に格納されている目標遅延値“１０ｎｓ”を与える。そして、階層回路ＳＵＢ２′，３′，４′毎に最適化処理を実行し、その実行結果として得られる図５の論理回路の情報を最適化結果格納部１０に格納して最適化を終了する。
【００３７】
本実施形態によれば、階層構造を有する論理回路の最適化において、最適化の対象である論理回路の階層構造をフリップフロップの入力端子が各階層回路の切り口となるように変更することで、各階層回路の中にフリップフロップを経由しないパスがない状態としてから最適化処理を実行するので、最適化の対象である論理回路の階層回路の中にその入力端子からフリップフロップを経由せずに出力端子に至るパスがあった場合に、階層破壊や制約値再作成など特別な処理をすることなく容易かつ適切に最適化処理を行うことができる。
【００３８】
図８を参照すると、本発明の他の実施形態の最適化装置２０は入力装置２１と出力装置２２と記憶装置２３と記録媒体２４とデータ処理装置２５を有している。
【００３９】
入力装置２１は、最適化装置２０を操作するためのキーボードやマウス等である。
【００４０】
出力装置２２は、最適化装置の処理結果等を表示するためのディスプレイや、印刷するためのプリンタ等である。
【００４１】
記憶装置２３は、図１の論理回路格納部１、制約値格納部２、フリップフロップ格納部４、階層回路格納部６、マージ結果格納部８および最適化結果格納部１０内のデータが記憶される。
【００４２】
記憶媒体２４は、フロッピーディスク、ＣＤ−ＲＯＭ、光磁気ディスク等の記録媒体であり、図１のフリップフロップ抽出部３、階層変更部５、階層回路マージ部７および論理最適化実行部９の処理を有するプログラムが記録されている。
【００４３】
そして、データ処理装置２５は記録媒体２４からプログラムを読み取り、記憶装置２３に格納した後、これを実行する。
【００４４】
【発明の効果】
最適化の対象である論理回路の階層回路の中にその入力端子からフリップフロップを経由せずに出力端子に至るパスがあった場合に、階層破壊や制約値再作成など特別な処理をすることなく容易かつ適切に最適化処理を行うことができる。
【図面の簡単な説明】
【図１】本発明の一実施形態の最適化装置の構成を示すブロック図である。
【図２】図１の最適化装置の動作を説明するための論理回路の一例を示す回路図である
【図３】図１の最適化装置の階層変更部で得られた新たな階層回路を示す回路図である。
【図４】図１の最適化装置の階層回路マージ部で得られた論理回路を示す回路図である。
【図５】図１の最適化装置で最終的に得られた最適化された論理回路を示す回路図である。
【図６】本発明の他の実施形態の最適化装置の構成を示すブロック図である。
【符号の説明】
１    論理回路格納部
２    制約値格納部
３    フリップフロップ抽出部
４    フリップフロップ格納部
５    階層変更部
６    階層回路格納部
７    階層回路マージ部
８    マージ結果格納部
９    論理最適化実行部
１０    最適化結果格納部
２０    最適化装置
２１    入力装置
２２    出力装置
２３    記憶装置
２４    記録媒体
２５    データ処理装置
ＦＦ１〜４    フリップフロップ
Ｇ１〜５    論理素子
ＩＦ１〜６    切り口
ＳＵＢ１〜３，ＳＵＢ１′〜４′，ＳＵＢ２″〜４″    階層回路
【図１】
0003555569.tif 000002
【図２】
0003555569.tif 000003
【図３】
0003555569.tif 000004
【図４】
0003555569.tif 000005
【図５】
0003555569.tif 000006
【図６】
0003555569.tif 000007