(57)【特許請求の範囲】
【請求項１】
ネットリストの生成中に、要求されたシーケンシャル・セルを候補セルから推論するためのシステムであって；
ａ）前記被要求セルを、数学的表現で表すための手段と；
ｂ）前記候補セルを、数学的表現で表すための手段と；
ｃ）少なくとも一つの値を戻すために、前記候補セルの表現とともに、前記被要求セルの表現でオペレーションを実行するための手段と；
ｄ）戻された各値に対応する規則を供給するための手段と；および
ｅ）戻された各値に対応する各規則を実行することによって、前記候補セルを、前記被要求セルに変換するための手段と
を具備する前記システム。
【請求項２】
前記候補セルおよび前記被要求セルの数学的表現は、ポリノミアルであることを特徴とする、請求項１に記載のシステム。
【請求項３】
実行される前記オペレーションは、前記候補セルの前記ポリノミアル表現を、前記被要求セルの前記ポリノミアル表現で割るステップを具備することを特徴とする、請求項２に記載のシステム。
【請求項４】
前記ポリノミアルは、論理エレメントに対応する一つ以上のマルチノムを具備することを特徴とする、請求項３に記載のシステム。
【請求項５】
前記マルチノムは、Ｒｓｔ、Ｌｒ、Ｓｔ、Ｌｓ、Ｓｃ、Ｍｕ、Ｒｅ、Ｌｒｅ、およびＴを含むグループから選択されることを特徴とする、請求項４に記載のシステム。
【請求項６】
前記ポリノミアル表現を割るための手段は、必要な抑止、変換および推論に対応する少なくとも一つのマルチノムを戻すことを特徴とする、請求項３に記載のシステム。
【請求項７】
前記各手段は、コンピュータによって実行されることを特徴とする、請求項１に記載のシステム。
【請求項８】
ネットリストを生成中に、要求されたシーケンシャル・セルを候補セルから推論するためのシステムであって；
ａ）前記被要求セルを、最低次数のマルチノムを有するＰｒｅｑポリノミアルとして表すための手段と；
ｂ）前記候補セルを、Ｐｃａｎｄポリノミアルとして表すための手段と；
ｃ）ＰｒｅｑもＰｃａｎｄも、０に等しくない場合には、マルチノムＺｒｅｑを、Ｐｒｅｑの最低次数のマルチノムに等しく設定し、およびＰｒｅｑかＰｃａｎｄのいずれかが０に等しい場合は、ｆ）の関数を開始し；
ｄ）ＰｃａｎｄがＺｒｅｑによって割ることができるマルチノムを具備するか決定し、もしそうであれば、ＺｃａｎｄをＺｒｅｑで割ることができるＰｃａｎｄの最低次数マルチノムに等しく設定し、そうでなければ、ポリノミアルＰｉｎｈｉｂを、Ｐｃａｎｄに設定し、それからＰｃａｎｄを０に等しく設定し、およびステップｃ）を実行するための手段と；
ｅ）Ｚｃａｎｄよりも小さい次数を有するＰｃａｎｄマルチノムを、Ｐｉｎｈｉｂに加え、ＺｃａｎｄをＰｃａｎｄから減じ、ＺｒｅｑをＰｒｅｑから減じ、Ｚｒｅｑで割ったＺｃａｎｄのポリノミアルの商を、ポリノミアル  Ｐｔｒａｎｓｆｏｒｍに加え、および手段ｃ）の関数を開始するための手段と；および
ｆ）Ｐｒｅｑが０に等しい場合、ＰｃａｎｄをＰｉｎｈｉｂに加え、およびＰｃａｎｄが０に等しい場合、ＰｒｅｑをポリノミアルＰｉｎｆｅｒに加えるための手段と
を具備する前記システム。
【請求項９】
前記ポリノミアルＰｉｎｈｉｂ、Ｐｔｒａｎｓｆｅｒ、およびＰｉｎｆｅｒは、マルチノムを具備することを特徴とする、請求項８に記載のシステムであって、さらに、Ｐｉｎｈｉｂ、ＰｔｒａｎｓｆｅｒおよびＰｉｎｆｅｒのマルチノムに対応する規則を供給し、および前記候補セルを、前記被要求セルに変換するために、前記規則を前記候補セルに適用するための手段を具備する、前記システム。
【請求項１０】
前記ポリノミアルＰｃａｎｄならびにＰｒｅｑ、およびマルチノムＺｃａｎｄならびにＺｒｅｑは、メジャーならびにマイナー・マルチノムを具備し、および手段ｄ）はさらに、Ｚｒｅｑに存在するメジャー・マルチノムが、Ｐｃａｎｄにも存在するかを決定するための手段を具備することを特徴とする、請求項９に記載のシステム。
【請求項１１】
前記マルチノムＺｒｅｑおよびＺｃａｎｄは次数を有し、および前記ポリノミアルの商は、ＺｒｅｑならびにＺｃａｎｄの次数を１に設定し、それからＺｃａｎｄをＺｒｅｑで割ることによって得られることを特徴とする、請求項１０に記載のシステム。
【請求項１２】
前記各手段は、コンピュータによって実行されることを特徴とする、請求項８に記載のシステム。
【請求項１３】
前記被要求セルは、第一の位置に第一の同期関数エレメントを有するフリップフロップを具備し、および要求されたセルをＰｒｅｑポリノミアルで表すための前記手段は、Ｐｒｅｑを、前記第一のエレメントに対応するマルチノムに等しく設定し、ならびに前記マルチノムに次数１を与えるための手段を具備することを特徴とする、請求項８に記載のシステム。
【請求項１４】
前記被要求セルは、ある位置に第二の関数エレメントを具備し、および要求されたセルをＰｒｅｑポリノミアルで表すための前記手段は、前記第一のエレメントに対応するマルチノムを、前記第二のエレメントに対応するマルチノムと合計するための手段を具備し、前記第二のエレメント・マルチノムは、前記第二のエレメント位置に対応する次数を有することを特徴とする、請求項１３に記載のシステム。
【発明の詳細な説明】
【０００１】
（技術分野）
本発明は、電子設計自動化（electronic design automation）（ＥＤＡ）の分野に関し、特定的には、所望の回路に、ネットリスト（netlist）を生成するために、シーケンシャル論理エレメントを、統括的に推論するためのシステムおよび方法に関する。
【０００２】
（背景技術）
ＥＤＡは一般的に、設計者が、ハードウェア記述言語（Hardware Description Language）（ＨＤＬ）を用いて、抽象的、関数レベル、レジスタ・トランスファー・レベル（Register Transfer Level）（ＲＴＬ）で、所望のデジタル回路を記述することができるようにする、パワフルな処理を意味する。前記設計の関数は、回路シミュレーションを通して、数学的に検査することができる。論理合成は、自動的に、ＲＴＬ記述をゲートレベル・ネットリスト（gate-level netlist）に変換する。その次のステップは、チップ・フロア（chip floor）に前記ゲートを配置するように、前記ネットリストをパーズ（解析）する。最後に、ルーティング（routing）処理は、ゲート間に必要な接続を作成するために必要な物理的レイアウトを決定する。前記物理的レイアウトから、その結果物である集積回路のためのシリコンが製造されうる。
【０００３】
論理合成ステップは、予め定義されたシーケンシャル・セルのライブラリ、または論理関数のブロックと同様に、所望の回路のＲＴＬ表現も必要とする。シーケンシャル・インフェラー（sequential inferrer）は、シーケンシャル・セルを、ＲＴＬ記述の関数を有する、相互接続されたセルのネットリストへと組み立てる。特に、シーケンシャル・セル・サーバは、前記処理に、所望の関数を達成するために必要な特定のセルを供給する。前記サーバは、前記ライブラリから直接、被要求セルを得るか、またはより重要なことに、それは、一つ以上の関数を、前記ライブラリにおける基本セルから結合することによって、被要求セルを生成する。推論されたセルが必要である時、前記セル・サーバは、被要求セルのコンポーネント・パーツ（component parts）を、利用可能なセルのライブラリと比較する。前記セルは、出力部分、入力部分、クロック部分、および同期部分に分解することができる。被要求セルの出力、クロック、および同期部分に匹敵する候補セルは、前記ライブラリから選択される。それから前記サーバは、各候補セルの入力関数が、被要求セルのそれと適合するように、抑止、変換、または結合推論を介して変換されることができるか、決定する。適切な候補が選択されると、前記セルは、ネットリストへと変換され、および統合される。通常、一つ以上の候補セルが、所望の関数を達成するために、変換されうる。そのために、うまくいった候補セルは、さらに、サイズ、電力消費、信号完全性、ルーティング制約等、他の必要な基準を最適化するために、選別されうる。
【０００４】
従来の論理合成の一例は、完全なルール・ベース変換を使用する。上述の通り、変換処理は、シーケンシャル・セルのデータ入力部分に重点を置いている。データ入力関数は、データ入力ターミナルと、クロック介在（clock mediated）フリップフロップまたはラッチ（latch）との間にある。このように、本発明の目的のために、データ入力関数は、常に同期しており、前記関数は、データ入力上で動作する結合エレメントの組を具備する。これらのエレメントは、単なるワイヤか、ＡＮＤゲート（リセット関数のため）、ＯＲゲート（セット関数のため）、マルチプレクサ（multiplexer）（“ＭＵＸ”−選択のため）、またはインバータ（トグルのため）を含むゲートでもよい。前記エレメントは、フリップフロップに最も近いエレメントが、第一の位置になるように、データ入力とフリップフロップとの間の、それらの関係に基づいて、位置を割り当てられる。
【０００５】
前記エレメントの性質によって、結合の可能性をいくらか減少させることができる。例えば、ＴｏｇｇｌｅおよびＭＵＸエレメントは、禁止位置を有し（それらは、関数の最後の位置に設定されなければならない）、およびＴｏｇｇｌｅならびにＭＵＸエレメントは、相互に排他的である（それらは、同じ関数には存在することができない）。使用されるかもしれないエレメントの数を制約することによって、前記処理は、いくらか簡潔にすることができる。例えば、各エレメントが一度だけ推論されるようにすることで、ＭＵＸまたはＴｏｇｇｌｅエレメントがない、２５８の可能な組み合わせ、Ｔｏｇｇｌｅエレメントを伴う２５８の組み合わせ、およびＭＵＸエレメントを伴う１７０の組み合わせ、合計で６８６の異なる関数が生まれる。これらの可能な組み合わせの各々に、完全なルール・ベースの機構を供給することは、合計で４７０，５９６の変換規則を必要とする（６８６の可能な被要求セルに、６８６の可能な候補セルをかける）。前記エレメントが、一回以上現れるようにすることで、問題を悪化させる。例えば、５までの位置を許可することによって、３０００以上の関数が生じ、それに対応して、１０００以上の規則が必要になる。以下で説明されるとおり、この利用可能なシステムは、単純な変換に対応することができるが、より複雑な関数が、前記システムの制約を示している。
【０００６】
第一の例において、被要求セルは、Ｒｅｓｅｔアクティブ・ハイのデータ入力関数を有する。完全なルール・ベース・システムを適用するために、各候補は、それがＲｅｓｅｔエレメントを有するか決定するために、選別される。もしそうであれば、前記インフェラー（推論機）は、同期リセット・ターミナルでの極性を確認し、およびＳｃａｎ、ＳｃａｎＭｕｘまたはＳｅｔ等、他のエレメントを抑止し（単純な接続と取替え）なければならない。前記候補が、Ｒｅｓｅｔエレメントを含まない場合、Ｓｃａｎエレメントは、それを変換するために定数に設定されることができ、ＭＵＸおよびＳｅｔエレメントは抑止されることができ、またはＳｃａｎが存在しない場合は、同期Ｒｅｓｅｔが推論される。この例には、たったいくつかの規則だけが必要なので、ルール・ベース変換は、Ｓｅｔ、ＲｅｓｅｔまたはＳｃａｎ等、比較的単純な関数には十分であろう。
【０００７】
アクティブ・ハイ同期Ｓｅｔ  Ｒｅｓｅｔ関数を有する被要求セルは、より複雑な例を示す。単純なフリップフロップ候補セルに関して、完全なルール・ベース・システムは、適切なＡＮＤおよびＯＲゲートの追加を必要とする。前記候補が、アクティブ・ローなＳｃａｎフリップフロップである場合、アクティブ・ローなＳｃａｎは、Ｒｅｓｅｔに変換されなければならず、およびＯＲゲートが加えられなければならない。一方で、前記候補が、アクティブ・ハイなＳｃａｎＭｕｘフリップフロップである場合、アクティブ・ハイなＳｃａｎは、Ｒｅｓｅｔに変換され、およびＭＵＸはＳｅｔに変換される。最後に、前記候補がアクティブ・ハイＲｅｓｅｔハイ再循環フリップフロップである場合、
Ｒｅｓｅｔは維持され、再循環エレメントは抑止され、およびＯＲゲートが加えられる。この例は、ＳｃａｎまたはＳｃａｎＭｕｘが利用可能であるか等のパラメータによって、各種の候補セルに特定の規則が必要とされることを示す。従って、上述された可能な組み合わせの数は、完全なルール・ベース・システムが、Ｓｃａｎ  Ｓｅｔ  Ｒｅｓｅｔ関数等、より複雑なデータ入力関数に関して、基本的に管理不可能であることを示す。
【０００８】
他の従来技術のシーケンシャル・インフェラーは、ブール・マッチング・システム（Boolean matching system）を利用する。Ｓ．Ｋｒｉｓｈｎａｍｏｏｒｔｈｙ，Ｆ．Ｍａｉｈｌｏｔの、“シーケンシャル・エレメントのブール・マッチング”、第３１回設計自動化会議、１９９４年、において、シーケンシャル・セルは、被要求セルが、ライブラリに対して選別されるようにするブール表現に類推される。この教示は、シーケンシャル推論および論理合成の開示のために、それへの参照によって、その全体がここに統合されている。しかしながら、このシステムは、被要求セルが、ライブラリに正確な適合を見つけた場合にのみ動作する。それは、ライブラリの基本セルを、適合しない被要求セルに変換するための手段を供給しない。さらに、前記システムは、適合だけが識別され、適合に変換されうる候補は識別されないので、候補の数を最大化しない。上述のとおり、他の基準の最適化を許可するために、可能なかぎり多くの候補を識別することが重要である。
【０００９】
このように、被要求セルに変換されてもよい候補セルを効率的に識別することができるセル・サーバを有する、シーケンシャル・インフェラーに対する必要性が存在する。また、複数のエレメントを具備する複雑な論理関数およびセルを変換することができるインフェラーに対する必要性も存在する。同様に、一定のライブラリからの適した候補セルの数を最大化するインフェラーに対する必要性が存在する。さらに、その結果の回路の、正確なコスト評価を可能にするシーケンシャル・インフェラーに対する必要性が存在する。候補セルを、被要求セルに変換するのに必要な、様々な変換を供給するために、最小数の規則を使用するインフェラーに対する必要性も存在する。本発明は、これらの、および他の必要性を満足させる。
【００１０】
（発明の開示）
本発明は、回路のＲＴＬ記述からのネットリストの生成中に、候補セルのライブラリから被要求セルを推論するための方法を含む。前記方法は、一般的に、被要求セルおよび候補セルを、数学的表現で表すこと：少なくとも一つの値を戻すために、候補セル表現とともに、要求セル表現でオペレーションを実行し；戻された各値に対応する規則を供給し；および戻された各値に対応する各規則を実行することによって、前記候補セルを前記被要求セルに変換することを含む。
【００１１】
好ましくは、候補セルおよび被要求セルは、関数同期エレメントを表すマルチノム(multinom:多項)を具備するポリノミアル(polynomial:多項式)として表される。さらに、被要求セル・ポリノミアルを候補セル・ポリノミアルで割ることにより、抑止、転換および推論ポリノミアルが戻される。被要求セルの関数を与えるために、抑止、転換および推論ポリノミアルの各マルチノムに対応する規則が、候補セルに適用される。
【００１２】
本発明のポリノミアル表現が引き出されるマルチノムは、メジャーまたはマイナーで階級付けされてもよく、マイナー・モノム(monom:単項)は１を割ることができるが、メジャー・モノムはできない。除数に存在するすべてのメジャー・モノムが、被除数にも存在する場合、一定のポリノミアル表現は、他の表現で割ることができる。
【００１３】
抑止、転換および推論ポリノミアルのすべての可能な値に関する規則の表は、簡単に決定することができる。一般的に、必要とされる規則の数は、大変管理しやすく、および完全なルール・ベース推論処理を採用する利用可能なシステムに対して、顕著に有利な点を呈する。好ましくは、前記方法は、ＥＤＡ処理を簡単にするために、コンピュータにおいて実行される。
【００１４】
（発明を実施するための最良の形態）
定義
シーケンシャル・セル‐データ入力ターミナルとフリップフロップまたはラッチとの間に配置される一つ以上の同期関数を有するフリップフロップまたはラッチであり、および非同期関数を具備してもよい；
データ入力部分‐クロックによって制御された関数、すなわち同期関数に接続されたシーケンシャル・セル・ターミナルのセット；
非同期部分‐クロックによって制御せず、およびクリア（clear）やプリセット（preset）等、出力への直接的影響を有する関数に接続されたシーケンシャル・セル・ターミナルのセット；
出力部分‐Ｑ、ＱｂａｒならびにＱｚ等、同期関数によって生成され、およびフリップフロップに記憶された値を戻す、シーケンシャル・セル・ターミナルのセット；
クロック部分‐ＣｌｏｃｋおよびＣｌｏｃｋＥｎａｂｌｅ等、フリップフロップを起動するためのクロック信号を伝送するセル入力ターミナル；
エレメント‐Ｓｅｔ、Ｒｅｓｅｔ、Ｍｕｘ、Ｓｃａｎ、Ｒｅｃｉｒｃ、およびＴｏｇｇｌｅを含み、ＡＮＤ、ＯＲ、ＭＵＸまたはＩＮＶで実行される、同期サブ関数；
関数‐要求される関数を供給する、データ入力ターミナルに接続された一つ以上のエレメント；
位置‐データ入力ターミナルとフリップフロップとの間の、エレメントの接続の順番であり、フリップフロップに隣接するエレメントは、第一の位置を有する；
ライブラリ‐推論処理のために直接利用可能な、シーケンシャル・セルの現存するセット；
被要求セル‐ＲＴＬの翻訳中に、インフェラーによって決定されるシーケンシャル・セル；
候補セル‐抑止、変換または結合推論等の処理の後に、被要求セルの関数に潜在的に適合するライブラリにおける利用可能なセル；
シーケンシャル・セル・サーバ‐ライブラリ・セルを相互接続することによって、インフェラーによって要求されるセルを生成するツールであって、前記サーバは、直接、ライブラリからのセルを、被要求セルに照合するか、またはライブラリ・セルを処理することによって、被要求セルを構築する；
変換機構‐要求された関数を与えるために、候補セルに適用するために必要な特定の抑止、変換および推論オペレーションを含む、候補セルが被要求セルに変換される処理；
抑止‐候補セルの処理であって、一定のエレメントが、コネクションに（connection）よって置き換えられる；
変換‐候補セルの処理であって、一定のエレメントが、他のエレメントへと変えられる；
結合推論‐候補セルの処理であって、一定のエレメントが加えられる；
【００１５】
方法論
本発明は、被要求セルの関数を生成するために、識別された候補セルを変換するための方法を供給する。被要求セルは、ポリノミアル表現に変換され、それから候補セルのポリノミアル表現で割られる。前記除法の結果は、候補セルを被要求セルに変換するための、必要な抑止、変換および推論ステップを示す。
【００１６】
後述のとおり、ポリノミアル理論の概念は、シーケンシャル・セルに適用されてもよい。ポリノミアルは、様々な次数になじむモノム（monom）の和を含む。例えば、Ｐ＝Ｘ＾３＋４Ｘ＋７というポリノミアルにおいて、Ｘはそれぞれ、３、１および０の次数のモノムである。マルチノムは、異なるモノムの積であり、そのすべては、１、０または−１の次数を有する。モノムは、退化したマルチノムと考えられてもよい。実数の集合において、Ｘ＾０＝１なので、１のみがマルチノムである。これらの概念は、以下の例で実証される：
【００１７】
Ｘ＾１＝Ｘ
Ｘ＾０＝１
Ｘ＾−１＝１／Ｘ
Ｘ，ＹおよびＷがモノムである場合、
ＸＹＷはマルチノムであり、
ＹＷはマルチノムであり、
Ｘはマルチノムであり、
Ｗ（Ｘ＾−１）はマルチノムであり、
１はマルチノムであり、
（Ｙ＾２）Ｗはマルチノムではなく、
（Ｘ＾３）（Ｙ＾−３）はマルチノムではなく、および
４はマルチノムではない。
【００１８】
モノムはさらに、メジャーかマイナーに分類されてもよい。メジャー・モノムは、１を割ることができず、マイナー・モノムは：
１／Ｘ＝Ｘ＾−１ができる。
【００１９】
シーケンシャル・セルのポリノミアル表現の除法を統括する、二つの主な規則がある。第一は、ＺｔｙｐｅおよびＺｒｅｆがマルチノムである場合、
Ｚｒｅｆのメジャー・モノムがＺｔｙｐｅにも存在すれば、ＺｔｙｐｅはＺｒｅｆで割ることができる。例えば：
Ｓ、Ｏ、Ｒ、ＲｅおよびＴがメジャー・モノムであり、Ｘ、ＹおよびＮがマイナー・モノムである場合、
ＳＯＲはＲで割ることができ、
ＳＯＲはＯＹで割ることができ、
ＲｅはＲｅＮで割ることができ、
ＳＯＲＸＹはＲｅＮで割ることができず、
ＯはＳＯＲで割ることができず、および
ＴはＲＸで割ることができない。
【００２０】
第二に、除法の前に、マルチノムの次数が１に設定される。すると：
（（ＳＯＲ）＾３）／（ＯＹ）＝ＳＯＲ／ＯＹ＝ＳＲ／Ｙ
（（ＳＯＲＸＹ）＾３）／（ＳＯＲ）＾２）＝ＳＯＲＸＹ／ＳＯＲ＝ＸＹ
である。
【００２１】
ポリノミアルに関する上述の規則および定義は、シーケンシャル・データ入力関数に適用することができる。一定のセルに関して、各エレメントは、前記セルにおけるエレメントの位置に対応する次数を有するマルチノムである。メジャー・モノムＲｓｔ、Ｓｔ、Ｓｃ、ＲｅならびにＴ、およびマイナー・モノムＬｒ、Ｌｓ、ＭｕならびにＬｒｅを使用する。従って、各エレメントは、以下のマルチノムで記述することができる：
Ｒｓｔ：Ｒｅｓｅｔアクティブ・ハイ
ＲｓｔＬｒ：Ｒｅｓｅｔアクティブ・ロー
Ｓｔ：Ｓｅｔアクティブ・ハイ
ＳｔＬｓ：Ｓｅｔアクティブ・ロー
ＳｃＳｔＲｓｔ：Ｓｃａｎアクティブ・ハイ
ＳｃＳｔＬｓＲｓｔＬｒ：Ｓｃａｎアクティブ・ロー
ＭｕＳｃＳｔＲｓｔ：Ｍｕｘ  ａｆｔｅｒ  Ｓｃａｎ
Ｒｅ：Ｒｅｃｉｒｃｕｌａｔｉｎｇアクティブ・ハイ
ＲｅＬｒｅ：Ｒｅｃｉｒｃｕｌａｔｉｎｇアクティブ・ロー
Ｔ：Ｔｏｇｇｌｅ
【００２２】
例えば、図１は、アクティブ・ハイ同期Ｒｅｓｅｔ１４およびＳｅｔ１６を伴うフリップフロップ１２を具備するシーケンシャル・セル１０を図で表したものである。Ｒｅｓｅｔ１４は、フリップフロップ１２の隣にあるので、位置（および次数）１を有する。同様に、Ｓｅｔ１６エレメントは、位置２にある。従って、セル１０を表すポリノミアルは、Ｒｓｔ＋Ｓｔ＾２である。図２は、ＳｃａｎＭｕｘフリップフロップ・アクティブ・ロー１８、すなわち、Ｓｃａｎアクティブ・ロー２２およびＭｕｘ２４を伴うフリップフロップ２０を図で表したものであり、およびそのポリノミアル表現は、ＳｃＳｔＬｓＲｓｔＬｒ＋（ＭｕＳｃＳｔＲｓｔ）＾２である。図３は、Ｔｏｇｇｌｅフリップフロップ２６を図で表したものである。Ｔｏｇｇｌｅは、逆Ｑ出力を、入力に戻すワイヤ２８である。Ｔｏｇｇｌｅフリップフロップ２６のポリノミアルは、Ｔである。
【００２３】
本発明の転換処理は、図４に記載のフローチャートに要約されている。以下の略語が使用される：
Ｐｒｅｑは、被要求セルのポリノミアルであり、Ｚｒｅｑは、Ｐｒｅｑのマルチノム部分である；
Ｐｃａｎｄは、候補セルのポリノミアルであり、Ｚｃａｎｄは、Ｐｃａｎｄのマルチノム部分である；
Ｐｉｎｈｉｂは、図５に詳細に示されたとおり、候補セルで抑止されるべきエレメントを表すポリノミアルである；
Ｐｔｒａｎｓｆｏｒｍは、図６に詳細に示されたとおり、インバータを加えるか、または入力ターミナルを備えることによって変更するためのエレメントを表すポリノミアルである；および
Ｐｉｎｆｅｒは、図７に詳細に示されたとおり、候補セルにおいて、データ入力ターミナルを推論するためのエレメントを表す。
【００２４】
前記処理はステップ３０において開始し、Ｐｉｎｈｉｂ、Ｐｔｒａｎｓｆｏｒｍ、およびＰｉｎｆｅｒの値は０に設定される。次に、ステップ３２において、ＰｃａｎｄまたはＰｒｅｑのいずれかが０に等しい場合、ステップ３４が実行される。ＰｃａｎｄおよびＰｒｅｑのいずれも０に等しくない場合、ステップ３６が実行され、その場合ＺｒｅｑはＰｒｅｑにおける最小次数のマルチノムに等しく設定され、およびＺｃａｎｄは、Ｐｃａｎｄにおける最小次数のマルチノムに等しく設定され、それはＺｒｅｑによって割ることもできる。ステップ３８は、適切なＺｃａｎｄが見つかったか、すなわち、ＰｃａｎｄがＺｒｅｑで割ることができるマルチノムを有するか、照会する。そうであれば、除法サブルーチン・ステップ４０は、Ｚｃａｎｄより小さいＰｃａｎｄのすべてのマルチノムを、Ｐｉｎｈｉｂに加え、ＺｃａｎｄをＰｃａｎｄから除き、ＺｒｅｑをＰｒｅｑから除き、およびＺｃａｎｄ／Ｚｒｅｑの除法の結果を、Ｐｔｒａｎｓｆｏｒｍに加える。前記処理は、ＰｃａｎｄならびにＰｒｅｑのすべてのマルチノムが指定されたか、調べるために、ステップ３２に戻る。ステップ３８から、ＰｃａｎｄがＺｒｅｑによって割ることができるマルチノムを有しない場合、ステップ４２は、ＰｉｎｈｉｂをＰｃａｎｄに等しくなるように設定し、それからＰｃａｎｄを０に設定する。ステップ４２の後、前記処理はまた、ステップ３８に戻る。ステップ３４は、ＰｃａｎｄかＰｒｅｑのいずれかが、最初に０に等しいか、または前の除法サブルーチン操作によって０まで減った時に、実行される。ステップ３４において、Ｐｒｅｑが０に等しい場合、ＰｃａｎｄはＰｉｎｈｉｂに加えられ、およびＰｃａｎｄ＝０の場合、ＰｃａｎｄはＰｉｎｆｅｒに加えられる。
【００２５】
除法サブルーチン４０は、ポリノミアル除法のための、上述において確立された一般的規則に従う。Ｓｃ、Ｒｓｔ、Ｓｔ、ＲｅおよびＴモノムは、メジャー・モノムであり、それらがＺｒｅｑにある場合は、Ｚｃａｎｄに存在しなければならない。例えば：
ＳｃＳｔＲｓｔは、Ｒｓｔで割ることができる（＝ＳｃＳｔ）；
ＳｃＳｔＲｓｔは、ＳｔＹで割ることができる（＝（ＳｃＲｓｔ）／Ｙ）；
Ｒｅは、ＲｅＬｒｅで割ることができる（＝Ｌｒｅ＾−１）；
ＳｃＳｔＲｓｔＬｒＬｓは、ＲｅＬｒｅで割ることができない（Ｚｃａｎｄは、メジャー・モノムＲｅを有しない）；
Ｓｔは、ＳｃＳｔＲｓｔで割ることができない（Ｚｃａｎｄはメジャー・モノムＳｃおよびＲｓｔを有しない）；および
Ｔは、ＲｓｔＬｒで割ることができない（Ｚｃａｎｄは、メジャー・モノムＲｓｔを有しない）。
さらに、マルチノムＺｒｅｑおよびＺｃａｎｄの次数は、除法のために１に設定される。例えば：
（（ＳｃＳｔＲｓｔ）＾３）／（ＳｔＬｓ）＝ＳｃＳｔＲｓｔ／ＳｔＬｓ＝
ＳｃＲｓｔ／Ｌｓ
である。
【００２６】
図４に記載の処理は、一定のＰｒｅｑおよびＰｃａｎｄに関して、３つのポリノミアルＰｉｎｈｉｂ、Ｐｔｒａｎｓｆｏｒｍ、およびＰｉｎｆｅｒを戻す。候補セルは、抑止ステップ、転換ステップおよび推論ステップを受ける。同時に、抑止、変換および推論ステップは、被要求セルへの、候補セルの変換と考えられる。第一に、Ｐｉｎｈｉｂの各マルチノムに関して、図５に記載の対応する規則は、候補セルに適用される。第二に、図６に記載の変換規則ベースは、Ｐｔｒａｎｓｆｏｒｍによって指示されるとおり適用される。最後に、Ｐｉｎｆｅｒマルチノムは、図７に記載のとおり、候補セルに加えるためのエレメントを決定する。Ｐｉｎｆｅｒマルチノムの次数は、最低次数のマルチノムが最初に推論され、およびフリップフロップまたはラッチに隣接して配置されなければならないように、保存されなければならない。すなわち、上述のとおり、Ｐｉｎｆｅｒへと導くＺｃａｎｄおよびＺｒｅｑの次数は、推論されるエレメントが、他のエレメントとの関係において、ラッチでどこに属するかを決定する。
【００２７】
図８は、上述の、マルチノム除法の、すべての可能な組み合わせを示す表である。列は、除数であり、行は被除数である。前記表は、図６に記載された変換規則ベースが、すべての可能な除法結果を与えることを示す。従って、本発明の処理は、従来の、完全なルール・ベース変換論理合成に対して、顕著な有利性を示す。上述の例において、候補セルおよび被要求セルのすべての組み合わせに関するすべての変換を実行するために、４１の規則のみが必要となる。対照的に、従来のルール・ベース・システムは、匹敵する処理に関して、４７０，５９６の規則を必要とする。このように、本発明のシステムは、大幅に、効率的である。実際問題として、より効率的な変換によって、より多くの候補セルを生成することができ、エリア、電力消費、ルーティング問題等に関してネットリストを最適化する際に、より大きな柔軟性を可能にする。
【００２８】
例
第一の例に関して、被要求セルは、図１に記載の通り、アクティブ・ハイＲｅｓｅｔ  Ｓｅｔフリップフロップである。本発明の処理は、背景において、上述された従来技術の例と比較されてもよい。ポリノミアル表現は、Ｐｒｅｑ＝
Ｒｓｔ＋Ｓｔ＾２である。候補セルが、図９に記載の通り、単純なＤフリップフロップである場合、Ｐｃａｎｄ＝０である。ステップ３２は、ステップ３４につながり、そこではＰｃａｎｄ＝０なので、ＰｒｅｑがＰｉｎｆｅｒに加えられる。ＰｉｎｈｉｂおよびＰｔｒａｎｓｆｏｒｍは、それらの開始値０を維持する。従って、何も抑止されずまたは変換されず、Ｒｓｔ＋Ｓｔ＾２が推論される。Ｒｓｔマルチノムは、最低次数を有するので、それは第一の位置に配置され、Ｓｅｔエレメントは、第二の位置に配置される。
【００２９】
代替的に、図１０に記載の通り、候補セルがアクティブ・ロー・スキャン・フリップフロップである場合、Ｐｃａｎｄ＝ＳｃＳｔＬｓＲｓｔＬｒである。前記処理は、ステップ３６の後であり、そこでは、ＺｒｅｑはＲｓｔに、およびＺｃａｎｄはＳｃＳｔＬｓＲｓｔＬｒに設定される。Ｚｃａｎｄは、Ｚｒｅｑで割ることができるので、ステップ４０は、Ｐｉｎｈｉｂを、Ｚｃａｎｄより小さい次数、ここでは０のＰｃａｎｄマルチノムに設定する。ステップ４０はさらに、ＰｃａｎｄからＺｃａｎｄを減じ、そしてＰｃａｎｄを０に設定し、ＰｒｅｑからＺｒｅｑを減じ、それからＰｒｅｑをＳｔ＾２に設定し、およびＰｔｒａｎｓｆｏｒｍをＺｃａｎｄ／Ｚｒｅｑに、すなわちＳｃＳｔＬｓＬｒに設定する。前記処理は、それからステップ３２に戻り、そこでは、０のＰｃａｎｄ値が、前記処理をステップ３４へ送る。Ｐｃａｎｄは０なので、Ｐｉｎｆｅｒは、ここではＳｔ＾２の値を有するＰｒｅｑに設定される。このように、前記処理の結果は、Ｐｉｎｈｉｂ＝０、Ｐｔｒａｎｓｆｏｒｍ＝ＳｃＳｔＬｓＬｒおよびＰｉｎｆｅｒ＝Ｓｔ＾２である。図５−７から、候補セルで実行される、対応するオペレーションは、何も抑止せず、ＴＩをＶｓｓに設定し、ＴＥを、インバータ（Ｓｃａｎエレメントを、正しい極性でＲｅｓｅｔエレメントに変換する）でＲｅｓｅｔターミナルに接続し、およびＳｅｔを推論する。
【００３０】
最後の例として、候補セルは、図１１に記載の通り、アクティブ・ハイＲｅｓｅｔおよびアクティブ・ハイＲｅｃｉｒｃｕｌａｔｉｎｇを伴うフリップフロップである。このように、ＰｒｅｑはまだＲｓｔ＋Ｓｔ＾２であり、ＰｃａｎｄはＲｓｔ＋Ｒｅ＾２である。ステップ３６は、ＺｒｅｑをＲｓｔに、およびＺｃａｎｄをＲｓｔに設定する。前記除法が可能であるので、ステップ４０は、Ｐｃａｎｄに、より小さい次数のマルチノムがないために、Ｐｉｎｈｉｂに０を加える。次に、Ｒｓｔが、Ｐｃａｎｄから減じられ、Ｒｅ＾２が残り、ＲｓｔがＰｒｅｑから減じられ、Ｓｔ＾２が残る。最後に、Ｚｒｅｑ／Ｚｃａｎｄの値に関して、Ｐｔｒａｎｓｆｏｒｍに１の値が与えられる。ＰｃａｎｄもＰｒｅｑも、もう０ではないので、前記処理は、ステップ３２に戻り、それから３６に戻る。ステップ３６においては、ＺｒｅｑはＳｔ＾２に設定され、ＺｃａｎｄはＲｅ＾２に設定される。ＺｃａｎｄはＺｒｅｑで割ることができないので、ステップ３８は、前記処理をステップ４２に送る。Ｐｃａｎｄ（Ｒｅ＾２）がＰｉｎｈｉｂに加えられ、Ｐｃａｎｄは０に設定される。前記処理はステップ３２に戻り、それから３４に戻る。ここで、Ｐｃａｎｄは０なので、ＰｒｅｑがＰｉｎｆｅｒに加えられ、Ｓｔ＾２の値をそれに与える。このように、Ｐｉｎｈｉｂは、Ｒｅ＾２の値を有し、Ｐｔｒａｎｓｆｏｒｍは値１を有し、およびＰｉｎｆｅｒは値Ｓｔ＾２を有する。このように図５−７から、Ｒｅｃｉｒｃｕｌａｔｉｎｇアクティブ・ハイは抑止され、何も変換されず、Ｓｅｔが推論される。
【００３１】
本発明の処理は、追加のエレメントを与えるように、簡単に適応することができる。専用マルチノムが、新しいエレメントのために加えられ、およびいくつかの追加規則が、抑止、転換および推論規則ベースに加えられる。前記処理は、変わらないままである。例えば、ＪＫエレメントは、たった１０の追加規則を、抑止、変換および推論規則ベースに加えることによって、組み込むことができる。対照的に、ＪＫエレメントを、従来技術のルール・ベース・アプローチで包含すると、必要とされる規則の数に、４の因数をかけることになる。さらに、前記処理は、必要があれば最適化することができる。特定のエレメントはさらに、追加のモノムによって記述することができる。例えば、Ｓｃａｎエレメントが最後の位置にあり、それがＭｕｘと考えられるようにすることを示すために、モノムが使用されうる。
【００３２】
好ましい実施形態がここに記載されているが、本発明に関連する当業者は、関連する代替的な実施形態があることを理解するであろう。
【図面の簡単な説明】
本発明の上述の効果は、その追加的効果と同様に、添付の図面を参照して、好ましい実施形態の詳細な説明の結果として、より完全に理解されるであろう。
【図１】  図１は、アクティブ・ハイ同期Ｓｅｔ  Ｒｅｓｅｔセルの図である。
【図２】  図２は、アクティブ・ローＳｃａｎＭｕｘを伴うフリップフロップの図である。
【図３】  図３は、Ｔｏｇｇｌｅフリップフロップの図である。
【図４】  図４は、本発明の処理を示すフローチャートである。
【図５】  図５は、処理の結果に基づいて適用するための抑止規則の表である。
【図６】  図６は、処理の結果に基づいて適用するための変換規則の表である。
【図７】  図７は、処理の結果に基づいて適用するための推論規則の表である。
【図８】  図８は、マルチノム除法の可能な組み合わせを示す表である。
【図９】  図９は、Ｄ入力フリップフロップ候補セルの図である。
【図１０】  図１０は、アクティブ・ローＳｃａｎフリップフロップ候補セルの図である。
【図１１】  図１１は、アクティブ・ハイＲｅｓｅｔアクティブ・ハイＲｅｃｉｒｃｕｌａｔｉｎｇ候補セルでの図である。
【図１】
0004446265.tif 000002
【図２】
0004446265.tif 000003
【図３】
0004446265.tif 000004
【図４】
0004446265.tif 000005
【図５】
0004446265.tif 000006
【図６】
0004446265.tif 000007
【図７】
0004446265.tif 000008
【図８】
0004446265.tif 000009
【図９】
0004446265.tif 000010
【図１０】
0004446265.tif 000011
【図１１】
0004446265.tif 000012