【０００１】[0001]
【産業上の利用分野】本発明は論理回路を設計する論理
合成システムに関し、特に、簡潔なルール記述でルール
を定義できる論理合成システムに関する。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a logic synthesis system for designing a logic circuit, and more particularly to a logic synthesis system capable of defining rules with a simple rule description.
【０００２】[0002]
【従来の技術】論理回路の合成には、回路変換ルールを
備えたルールベースの論理合成システムがよく用いられ
ている。従来から、このルールベースの論理合成システ
ムでは、人手でルールを作成し登録することにより、ル
ールベースを構築してきた。ルールの作成方法は主に、
ブール代数の公式などをもとに容易に簡単化できる小規
模な回路を人手で見つけ出し、その回路を人手で簡単化
して、簡単化前後の回路パターンの組からルールを作成
するという手順からなる。ルールの適用順序の指定も人
手でおこなってきた。2. Description of the Related Art A rule-based logic synthesis system having circuit conversion rules is often used for synthesis of logic circuits. Conventionally, in this rule-based logic synthesis system, a rule base has been constructed by manually creating and registering rules. The rule creation method is mainly
The procedure consists of manually finding a small-scale circuit that can be easily simplified based on the Boolean algebra formula, simplifying the circuit manually, and creating a rule from a set of circuit patterns before and after the simplification. We have also manually specified the application order of rules.
【０００３】[0003]
【発明が解決しようとする課題】ルールベースの論理合
成システムの性能をあげるには、多数のルールを登録す
る必要がある。しかしながら、ルール記述が複雑である
と一般のユーザが自由にルールを作成できないという問
題点がある。また、ルール数が多くなると、ルールの適
用順序の決定、ルールの管理などが困難になる。さら
に、回路規模の大きなルールを作成しようとすると、適
当な回路を見つけ出したり、人手で簡単化を行なうとい
うような作業が困難になり、人手でルールを作成してい
くにも限度がある。In order to improve the performance of the rule-based logic synthesis system, it is necessary to register a large number of rules. However, if the rule description is complicated, there is a problem that general users cannot freely create rules. Also, when the number of rules increases, it becomes difficult to determine the order of application of rules and manage the rules. Furthermore, when trying to create a rule with a large circuit scale, it becomes difficult to find an appropriate circuit or manually perform simplification, and there is a limit to manually creating a rule.
【０００４】また、従来のルールは実際の回路に対して
どの程度有用であるか、実際の論理合成の過程でどの程
度の頻度で用いられるものであるか等はほとんど考慮さ
れずに作成されている。このため、ともすればルールの
数が多いにもかかわらず性能があまりよくなかったり、
ルール選択時の効率の低下にもつながるという問題点が
あった。Further, the conventional rule is created without taking into consideration how useful it is for an actual circuit and how often it is used in an actual logic synthesis process. There is. For this reason, even if there are many rules, performance is not very good,
There was a problem that it also led to a decrease in efficiency when selecting rules.
【０００５】本発明は前述のような問題点を考慮してな
されたものであり、その目的とするところは、実際の回
路に対して有効であるようなルールを効率よく生成、適
用することができる論理合成システムを提供することに
ある。The present invention has been made in consideration of the above problems, and an object thereof is to efficiently generate and apply a rule that is effective for an actual circuit. It is to provide a logic synthesis system that can do it.
【０００６】[0006]
【課題を解決するための手段】上記目的を達成するた
め、第１の発明の特徴は、論理簡単化の対象となる簡単
化前の論理回路と、簡単化後の論理回路とを対にして表
記した簡潔な表現による回路変換の簡単化規則（ルー
ル）の記述を用いることである。To achieve the above object, a feature of the first invention is that a logic circuit before simplification, which is a target of logic simplification, and a logic circuit after simplification are paired. It is to use the description of the simplification rule (rule) of the circuit conversion by the described simple expression.
【０００７】また、第２の発明の特徴は、回路変換ルー
ルを生成する機能をかねそなえたルールベース部と、こ
のルールベース部にて生成された回路変換ルールを用い
て機能記述をテクノロジ依存の論理回路に変換する論理
合成エンジン部とを備えた論理合成システムにおいて、
前記ルールベース部は、ルールの変換前回路として所望
の初期回路を生成する初期回路提供部と、前記初期回路
提供部から出力された初期回路を簡単化し、簡単化回路
を出力する論理簡単化部と、前記初期回路提供部から出
力された初期回路及び論理簡単化部から出力された簡単
化回路を入力し、前記初期回路と前記簡単化回路とを対
にして表記したルール記述を生成するルール記述生成部
と、このルール記述生成部で生成されたルール記述より
このルールに対応する回路変換プログラムコードを生成
するルール生成部と、このルール生成部にて生成された
前記ルールを逐次保持するルール記憶部とを備えること
である。The second aspect of the present invention is characterized in that a rule base part having a function of generating a circuit conversion rule and a circuit description rule generated by the rule base part are used to make a functional description dependent on technology. In a logic synthesis system including a logic synthesis engine unit for converting into a logic circuit,
The rule base unit is an initial circuit providing unit that generates a desired initial circuit as a pre-conversion circuit, and a logic simplification unit that simplifies the initial circuit output from the initial circuit providing unit and outputs a simplified circuit. And a rule that inputs the initial circuit output from the initial circuit providing unit and the simplification circuit output from the logic simplification unit and generates a rule description in which the initial circuit and the simplification circuit are paired and described. A description generation unit, a rule generation unit that generates a circuit conversion program code corresponding to this rule from the rule description generated by this rule description generation unit, and a rule that sequentially holds the rules generated by this rule generation unit And a storage unit.
【０００８】また、第３の発明の特徴は、回路変換ルー
ルを生成する機能をかねそなえたルールベース部と、こ
のルールベース部にて生成された回路変換ルールを用い
て機能記述をテクノロジ依存の論理回路に変換する論理
合成エンジン部とを備えた論理合成システムにおいて、
前記ルールベース部は、ルール作成の変換前回路として
所望の初期回路を生成する初期回路提供部と、前記初期
回路提供部から出力された初期回路を簡単化し、簡単化
回路を出力する論理簡単化部と、この論理簡単化部にて
出力された簡単化回路が簡単化されたか否かを判定し、
この判定結果信号を出力する簡単化判定部と、前記初期
回路提供部から出力された初期回路及び論理簡単化部か
ら出力された簡単化回路を入力し、前記初期回路と前記
簡単化回路とを対にして表記したルール記述を、前記簡
単化判定部にて出力された判定結果信号により生成する
ルール記述生成部と、このルール記述生成部で生成され
たルール記述よりルールに対応する回路変換プログラム
コードを生成するルール生成部と、このルール生成部に
て生成された前記ルールを逐次保持するルール記憶部と
を備え、ルールを自動生成することである。The third aspect of the present invention is characterized in that a rule base part having a function of generating a circuit conversion rule and a function description using a circuit conversion rule generated by the rule base part are technology-dependent. In a logic synthesis system including a logic synthesis engine unit for converting into a logic circuit,
The rule base unit simplifies an initial circuit providing unit that generates a desired initial circuit as a pre-conversion circuit for rule creation, and an initial circuit output from the initial circuit providing unit, and a logic simplification that outputs a simplified circuit. Section and whether or not the simplification circuit output by this logic simplification section is simplified,
The simplification determination unit that outputs the determination result signal, the initial circuit output from the initial circuit providing unit, and the simplification circuit output from the logic simplification unit are input, and the initial circuit and the simplification circuit are connected. A rule description generation unit that generates a rule description expressed as a pair based on the determination result signal output by the simplification determination unit, and a circuit conversion program corresponding to a rule from the rule description generated by the rule description generation unit A rule generation unit that generates a code and a rule storage unit that sequentially holds the rules generated by this rule generation unit are provided to automatically generate rules.
【０００９】また、第４の発明の特徴は、回路変換ルー
ルを生成する機能をかねそなえたルールベース部と、こ
のルールベース部にて生成された回路変換ルールを用い
て機能記述をテクノロジ依存の論理回路に変換する論理
合成エンジン部とを備え、論理簡単化の対象となる簡単
化前の論理回路と、簡単化後の論理回路とを対にして表
記した回路変換の簡単化規則（ルール）を用いて論理合
成を行う論理合成システムであって、前記ルールベース
部は、前記回路変換ルールを記憶するルール記憶部と、
このルール記憶部に記憶されたルールの適用頻度の情報
を保持するルール適用頻度記憶部と、このルール適用頻
度記憶部に保持された適用頻度を入力し、ルール記憶部
に記憶された適用頻度の少ないルールの抹消を行うこと
を特徴とするルール記憶部操作部とを備えることであ
る。The fourth aspect of the present invention is characterized in that a rule base part having a function of generating a circuit conversion rule and a circuit description rule generated by the rule base part are used to make a functional description dependent on technology. A circuit conversion simplification rule (rule) that includes a logic synthesis engine unit for converting into a logic circuit and describes a logic circuit before simplification that is a target of logic simplification and a logic circuit after simplification A logic synthesis system for performing logic synthesis using, the rule base unit, a rule storage unit that stores the circuit conversion rule,
The rule application frequency storage unit that holds information on the application frequency of rules stored in this rule storage unit and the application frequency stored in this rule application frequency storage unit are input, and the application frequency of the application frequency stored in the rule storage unit is input. The rule storage unit operation unit is characterized by erasing a small number of rules.
【００１０】さらに第５の発明の特徴は、回路変換ルー
ルを生成する機能をかねそなえたルールベース部と、こ
のルールベース部にて生成された回路変換ルールを用い
て機能記述をテクノロジ依存の論理回路に変換する論理
合成エンジン部とを備え、論理簡単化の対象となる簡単
化前の論理回路と、簡単化後の論理回路とを対にして表
記した回路変換の簡単化規則（ルール）を用いて論理合
成を行う論理合成システムであって、前記ルールベース
部は、前記回路変換ルールを記憶するルール記憶部と、
複数のルールを統合して新たにルールを作成するルール
統合化部とを備えることである。Further, a feature of the fifth invention is that a rule base portion having a function of generating a circuit conversion rule and a circuit description rule generated by the rule base portion are used to make a function description into a technology-dependent logic. Equipped with a logic synthesis engine unit for converting into a circuit, the simplification rules (rules) for circuit conversion are described by pairing a logic circuit before simplification, which is the target of logic simplification, and a logic circuit after simplification. A logic synthesis system that performs logic synthesis using the rule base unit, a rule storage unit that stores the circuit conversion rule,
A rule integration unit that integrates a plurality of rules to create a new rule.
【００１１】ここで、所望の回路最適にアルゴリズムの
該簡単化規則を逐次実行することにより、所望の回路最
適化アルゴリズムの動作と同等の動作を行うことも可能
である。Here, it is also possible to perform the same operation as that of the desired circuit optimization algorithm by sequentially executing the simplification rule of the algorithm for the desired circuit optimization.
【００１２】[0012]
【作用】上記第１及び第２の発明によれば、簡単化前後
の論理回路を対にして表記した簡単化規則を用いること
により、簡単なルール記述でルールを定義できるためル
ール管理やルール作成が容易になる。According to the first and second aspects of the present invention, the rule can be defined by a simple rule description by using the simplification rule in which the logic circuits before and after the simplification are described as a pair, so that rule management and rule creation can be performed. Will be easier.
【００１３】また、第３の発明によれば、ルールを自動
生成することで、人手では実質不可能な、ルール数の多
い巨大なルールベースを効率的に構築することができる
ようになるのである。According to the third invention, by automatically generating the rules, it becomes possible to efficiently construct a huge rule base having a large number of rules, which is virtually impossible by hand. .
【００１４】また、第４の発明によれば、ルール記憶部
操作部にて適用頻度の少ないルールの抹消を行うこと
で、いたずらにルールベースが巨大化していくことを防
ぐことができ、ルール選択時の処理効率の向上、ルール
ベースの占めるメモリ量の削減につながる。According to the fourth aspect of the present invention, the rule base operating section deletes the rule with a low frequency of application, whereby the rule base can be prevented from becoming huge and the rule selection can be prevented. This will improve the processing efficiency in time and reduce the amount of memory occupied by the rule base.
【００１５】また、第５の発明によれば、ルールを関連
づけておくことで処理の効率化を図ることができるので
ある。According to the fifth aspect of the invention, the efficiency of the processing can be improved by associating the rules with each other.
【００１６】[0016]
【実施例】以下、本発明に係る論理合成システムについ
て図面を参照しながら説明する。図１は本発明に係る論
理合成システムのルールベース部の構成を示したブロッ
ク図である。この論理合成システムは、回路変換ルール
を生成してルールを保持するルールベース部１と、この
ルールベース部１にて生成された回路変換ルールを用い
て機能記述をテクノロジ依存の論理回路に変換する論理
合成エンジン部１９とを備えており、ルールベース部１
は、初期回路提供部５、論理簡単化部７、簡単化判定部
９、ルール記述生成部１１、ルール生成部１３からなる
ルール生成系の各部と、ルール記憶部１７、ルール適用
頻度記憶部２１、ルール記憶部操作部２３からなるルー
ル操作系の各部と、ルールを統合するルール合成部２５
と、の３つ部分を備えている。以下、これら３つの部分
に分け、まず初めに、ルール生成系の各部について説明
する。この説明には理解の容易のため、適宜、具体的な
回路例を用いて説明することにする。DESCRIPTION OF THE PREFERRED EMBODIMENTS A logic synthesis system according to the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing the configuration of the rule base unit of the logic synthesis system according to the present invention. This logic synthesis system converts a functional description into a technology-dependent logic circuit by using a rule base unit 1 that generates a circuit conversion rule and holds the rule, and a circuit conversion rule generated by the rule base unit 1. The rule base unit 1 including the logic synthesis engine unit 19
Is a rule generation system including an initial circuit providing unit 5, a logic simplification unit 7, a simplification determination unit 9, a rule description generation unit 11, and a rule generation unit 13, a rule storage unit 17, and a rule application frequency storage unit 21. , A rule synthesizing unit 25 that integrates rules with each unit of the rule operating system including the rule storage unit operating unit 23.
And three parts. Below, these are divided into three parts, and first, each part of the rule generation system will be described. For ease of understanding, this description will be made using specific circuit examples as appropriate.
【００１７】図１において、ルール作成用回路の情報が
ルール用回路保持部３に記憶されている。このルール用
回路保持部３は図５に示す回路の情報を保持しているも
のとし、この回路情報は初期回路提供部５により読み込
まれる。ルール用回路としては、ベンチマークデータ、
実回路など、任意の適当な回路を与えることができる。
なお、本実施例においては、ルール用回路保持部３に予
め保持された回路の情報を用いたが、必要に応じてユー
ザにより回路情報を作成して、その作成された回路情報
を初期回路提供部５に読み込ませてもよい。In FIG. 1, information on the rule forming circuit is stored in the rule circuit holding section 3. It is assumed that the rule circuit holding unit 3 holds the information of the circuit shown in FIG. 5, and the circuit information is read by the initial circuit providing unit 5. As a rule circuit, benchmark data,
Any suitable circuit can be provided, such as a real circuit.
In the present embodiment, the circuit information held in advance in the rule circuit holding unit 3 is used, but the circuit information is created by the user as necessary, and the created circuit information is provided to the initial circuit. It may be read by the unit 5.
【００１８】次に、初期回路提供部５は、ユーザが与え
た条件（入力数、段数など）を満たす論理回路を生成す
るか、ユーザが与えた条件を満たす回路部分を別の与え
られた論理回路中から抽出することにより、ルールの変
換前回路となる初期回路を提供する。本実施例において
は、予めルール用回路保持部３の所定の部分に保持され
ていた図５に示す回路から３段で分岐収れんすることを
条件とし、図６（ａ）と図６（ｂ）の二つの回路を抽出
するものとする。この場合の初期回路提供部５の処理は
次のような手順で実現できる。まず、与えられた回路の
ある素子に注目する。図５におけるＸ1に注目したとす
る。次に、Ｘ1から入力側に検索して距離３までの素子
を素子集合とし、素子集合に属する素子間の接続を枝集
合として、部分回路を抽出する。この部分回路の距離３
の素子に複数の出力があるとき、さらにその部分回路か
ら、非可分成分（少なくとも一つの閉路に含まれる枝と
素子）だけを取り出す。これにより、図６（ａ）の回路
が抽出できる。これを与えられた回路の全ての素子に対
して行う。距離３の素子がない場合、距離３の素子に複
数の出力がない場合、非可分成分がない場合には、部分
回路は抽出されない。以上のようにして、図５の回路か
ら、図６（ａ）及び図６（ｂ）の二つの部分回路が抽出
できる。Next, the initial circuit providing unit 5 generates a logic circuit satisfying the condition (number of inputs, number of stages, etc.) given by the user, or a circuit portion satisfying the condition given by the user is given another logic. By extracting from the circuit, an initial circuit to be a pre-conversion circuit of the rule is provided. In the present embodiment, the circuit shown in FIG. 5, which is held in a predetermined portion of the rule circuit holding unit 3 in advance, is branched and converged in three stages, and FIG. 6A and FIG. Two circuits of are to be extracted. The processing of the initial circuit providing unit 5 in this case can be realized by the following procedure. First, pay attention to an element having a given circuit. It is assumed that attention is paid to X1 in FIG. Next, a partial circuit is extracted by searching for elements from X1 to the input side up to a distance of 3 as an element set, and connecting the elements belonging to the element set as a branch set. Distance 3 of this partial circuit
When the element of has multiple outputs, only the non-divisible component (branch and element included in at least one closed circuit) is taken out from the partial circuit. As a result, the circuit shown in FIG. 6A can be extracted. This is done for all elements of the given circuit. If there is no element at the distance 3, if there are no multiple outputs at the element at the distance 3, or if there is no non-divisible component, then the partial circuit is not extracted. As described above, the two partial circuits of FIGS. 6A and 6B can be extracted from the circuit of FIG.
【００１９】本実施例では、初期回路提供部５について
このような手順を用いたが、例えば、素子の出力側の検
索、深さ優先の検索、若しくは、段数でなく素子数を制
約とする等さまざまな手順での実現方法が考えられ、状
況に応じて使い分けてもよい。In the present embodiment, such a procedure is used for the initial circuit providing section 5. However, for example, the output side of the element is searched, the depth is prioritized, or the number of elements is restricted instead of the number of stages. A variety of procedures can be considered for implementation, and different methods may be used depending on the situation.
【００２０】次に、初期回路提供部５にて抽出された回
路は、論理簡単化部７に入力される。この論理簡単化部
７では、ＭＩＳ（R.K.Brayton, R.Rudell,, A.Sangiova
nni-Vincentelli, "MIS:A Multiple-Level Logic Optim
ization System", IEEE Trans. on C.A.D. Nov. 1987）
などのアルゴリズムを用いて、初期回路提供部５から提
供された回路を簡単化する。本実施例の具体的な回路例
で説明すると、図６（ａ）の回路は図７のように簡単化
される。一方、図６（ｂ）の回路はこれ以上簡単にはで
きない回路であり、論理簡単化部７は図６（ｂ）と同じ
回路を出力する。Next, the circuit extracted by the initial circuit providing unit 5 is input to the logic simplifying unit 7. In this logic simplification unit 7, MIS (RK Braton, R. Rudell ,, A. Sangiova
nni-Vincentelli, "MIS: A Multiple-Level Logic Optim
Systemization, "IEEE Trans. on CAD Nov. 1987)
The circuit provided from the initial circuit providing unit 5 is simplified by using the algorithm described above. Explaining with a concrete circuit example of this embodiment, the circuit of FIG. 6A is simplified as shown in FIG. On the other hand, the circuit of FIG. 6B is a circuit that cannot be further simplified, and the logic simplification unit 7 outputs the same circuit as that of FIG. 6B.
【００２１】本実施例において論理簡単化部７ではＭＩ
Ｓを例として挙げたが、他の手法を取り入れてもよく、
さらには、複数の簡単化手段を用いてその結果を比較し
て、最もよいものを選ぶというような構成にすることも
可能である。In this embodiment, the logic simplification unit 7 uses MI.
Although S is given as an example, other methods may be adopted,
Furthermore, it is also possible to adopt a configuration in which the results are compared using a plurality of simplification means and the best one is selected.
【００２２】簡単化判定部９は、初期回路提供部５が与
えた変換前回路の評価値と、その変換前回路を論理簡単
化部７が簡単化した変換後回路の評価値を比較して、実
際に簡単化されたか否かを判定する。評価値としてリテ
ラル数を考える。図６（ａ）の回路のリテラル数は９
で、図７の回路のリテラル数は８なので、この回路に対
しては簡単化されたと判定する。簡単化されたと判定さ
れた場合には、簡単化信号がルール記述生成部に出力さ
れる。The simplification judging section 9 compares the evaluation value of the pre-conversion circuit provided by the initial circuit providing section 5 with the evaluation value of the post-conversion circuit obtained by simplifying the pre-conversion circuit by the logic simplification section 7. , Determine whether or not it has been simplified. Consider the literal number as the evaluation value. The number of literals in the circuit of FIG. 6A is 9
Since the number of literals in the circuit of FIG. 7 is 8, it is determined that this circuit is simplified. If it is determined that the rule has been simplified, the simplified signal is output to the rule description generation unit.
【００２３】本実施例では、簡単化判定部９の判定にお
ける評価値としてリテラル数を採用し、簡単化の判定に
リテラル数減少の有無を用いたが、設計対象の制約や特
徴に応じて、ゲート数、ファンアウト数などを評価値と
したり、簡単化の判定基準も、評価値が変化の有無だけ
ではなく必要に応じて一定値を越えて変化した場合な
ど、状況に応じて設定を変えてもよい。In this embodiment, the number of literals is adopted as the evaluation value in the judgment of the simplification judging unit 9 and whether or not the number of literals is decreased is used for the simplification judgment. However, depending on the constraints and characteristics of the design target, The number of gates, the number of fan-outs, etc. can be used as the evaluation value, and the judgment criteria for simplification can also be changed according to the situation, such as when the evaluation value changes beyond a certain value as necessary, not only whether the evaluation value has changed May be.
【００２４】次に、ルール記述生成部１１では、変換前
回路と変換後回路を解析し、それぞれの回路において簡
単化に本質的な部分のみを抽出し、その本質的な変換前
後の回路パターンを作成しそれに対応するルール記述を
出力する。即ち、論理簡単部７にて変換される前後の回
路パターンのルール記述をペアで作成する。また、簡単
化判定部９からの簡単化信号が入力されなかった場合に
は、ルール記述は作成されない。ルール記述生成部１１
の処理フローを図４に示す。まず、変換前後の回路にお
いて、全ての入力が外部入力と接続している素子の関数
を求め、同じ関数を表す素子の組を作る（ステップＳ４
１）。そして、組ごとにそれぞれの素子がもとの回路か
ら除去できるかを調べる（ステップＳ４４）。除去可能
かどうかの判断は、それらの素子を除去しても変換前後
の回路が等価であるかどうかで行なう。除去可能であれ
ばそれらの素子に除去可能マークを設定する（ステップ
Ｓ４５）。そして、除去可能マークのついた素子の出力
側の素子に対して関数を求め、同様に同じ関数を表す素
子の組をつくり、除去可能かどうかを判定する（ステッ
プＳ４６）。これらの処理を等価な素子の組がなくなる
まで調べる。最後に、除去可能マークの設定された素子
を除去し（ステップＳ４７）、変換前後回路からルール
を作成する（ステップＳ４８）。Next, the rule description generation unit 11 analyzes the pre-conversion circuit and the post-conversion circuit, extracts only the essential parts for simplification in each circuit, and extracts the essential circuit patterns before and after conversion. Create and output the corresponding rule description. That is, the rule description of the circuit pattern before and after the conversion by the logic simplification unit 7 is created in pairs. If no simplification signal is input from the simplification determination unit 9, no rule description is created. Rule description generation unit 11
The processing flow of the above is shown in FIG. First, in the circuits before and after the conversion, the function of the element in which all the inputs are connected to the external input is obtained, and a set of elements representing the same function is created (step S4).
1). Then, it is checked for each set whether or not each element can be removed from the original circuit (step S44). Whether or not the elements can be removed is determined based on whether or not the circuits before and after conversion are equivalent even if these elements are removed. If removable, a removable mark is set to those elements (step S45). Then, a function is obtained for the element on the output side of the element with the removable mark, and similarly, a group of elements representing the same function is formed to determine whether or not the element can be removed (step S46). These processes are examined until there is no equivalent set of elements. Finally, the element with the removable mark set is removed (step S47), and a rule is created from the pre- and post-conversion circuits (step S48).
【００２５】全てのルールが、最大２段先までしか回路
探索を行なわないようなルールベースである場合、図５
の論理回路はこれ以上簡単化できない。しかしこのよう
に３段先まで回路探索をするようなルールを追加すれ
ば、簡単化できる可能性が出てくる。また、他の回路例
に対しても効果はある。When all the rules are rule-based so that the circuit search is performed only up to two steps ahead, the case shown in FIG.
The logic circuit of can not be simplified any more. However, the possibility of simplification comes out by adding a rule such that a circuit search is performed up to three steps ahead. It is also effective for other circuit examples.
【００２６】以下、本実施例の具体的な回路を用いて、
このルール生成部１３の処理を説明する。具体的な回路
を用いてルール生成部１３の処理を説明するならば、簡
単化されたと判定された図６（ｂ）と図７の回路を比較
し、簡単化に本質的な部分を抽出し、ルールを作成す
る、ということができる。この処理を図４に示したフロ
ーに従って説明する。まず、全ての入力端子が直接外部
入力と接続している素子の関数を求め、同一の関数を表
す素子を対応付ける。この対応の組を集合とする（ステ
ップＳ４１）。この例では、（ｇ２，ｇ１´），（ｇ
３，ｇ２´），（ｇ４，ｇ３´）が対応の組の集合とす
る。集合が空でないので（ステップＳ４２）、対応の組
を一つ取り出す。ここではまず（ｇ２，ｇ１´）を取り
出したとする（ステップＳ４３）。ｇ２，ｇ１をそれぞ
れの回路から削除すると、両回路は等価ではなくなるの
で（ステップＳ４４）、ｇ２，ｇ１´は除去不可能であ
り何もせず、次の組（ｇ３，ｇ２´）を取り出す。ｇ３
とｇ２´をそれぞれの回路から削除しても両回路は等価
であるので、ｇ３とｇ２´の除去可能マークを設定する
（ステップＳ４５）。ｇ３の出力に接続するｇ５とｇ２
´の出力に接続するｇ４´に関してそれらが同一の関数
を表しているかどうか調べる。この場合、ｇ３とｇ２´
は等価であるので、ｇ５とｇ４´は同一の関数を表して
いる。従って、（ｇ５，ｇ４´）は等価であるので対応
の組の集合に新たに追加する（ステップＳ４６）。この
ように等価な素子の組を順次見つけては除去可能である
かを、等価な素子の組がなくなるまで繰り返す。本実施
例では、（ｇ７，ｇ２´），（ｇ５，ｇ４´）が削除可
能であるので、これらの素子を図５（ａ）と図７から削
除した回路を作成する（ステップＳ４７）。それらの回
路を図８に示す。図９に示したような回路変換をルール
としてルール記憶部１７へと登録する。Hereinafter, using the specific circuit of this embodiment,
The processing of the rule generator 13 will be described. To explain the process of the rule generation unit 13 using a specific circuit, the circuit of FIG. 6B which is determined to be simplified and the circuit of FIG. 7 are compared to extract the essential part for simplification. You can say, create a rule. This processing will be described according to the flow shown in FIG. First, the function of the element in which all the input terminals are directly connected to the external input is obtained, and the elements representing the same function are associated with each other. The corresponding set is set as a set (step S41). In this example, (g2, g1 '), (g
3, g2 ') and (g4, g3') are a set of corresponding sets. Since the set is not empty (step S42), one corresponding set is extracted. Here, it is assumed that (g2, g1 ') is taken out first (step S43). If g2 and g1 are deleted from the respective circuits, the two circuits are not equivalent (step S44), so g2 and g1 'cannot be removed and nothing is done, and the next set (g3, g2') is taken out. g3
Even if g2 'and g2' are deleted from the respective circuits, the two circuits are equivalent to each other, so that the removable marks of g3 and g2 'are set (step S45). g5 and g2 connected to the output of g3
Check if they represent the same function for g4 'connected to the output of'. In this case, g3 and g2 '
Are equivalent, g5 and g4 'represent the same function. Therefore, since (g5, g4 ') is equivalent, it is newly added to the set of the corresponding set (step S46). In this way, it is repeated until the equivalent element set can be removed by sequentially finding the equivalent element set until there is no equivalent element set. In this embodiment, since (g7, g2 ') and (g5, g4') can be deleted, a circuit is created by removing these elements from FIGS. 5A and 7 (step S47). Those circuits are shown in FIG. The circuit conversion as shown in FIG. 9 is registered in the rule storage unit 17 as a rule.
【００２７】ルールの記述形式としては、図９のような
フォーマットで表すことができる。図９のフォーマット
では、Ｆｒｏｍのフィールドに変換前の回路パターン
が、Ｔｏのフィールドに変換後の回路パターンが記述さ
れている。本実施例のルールでは、変換前後の回路パタ
ーンのみが記述されているが、状況に応じて、ルールの
適用条件、回路の付加的情報、ルールの属性、組み込み
関数の呼び出しなどを記述できるように変更してもよ
い。このようなルール記述は図２のような処理で回路変
換プログラムコードが生成される。The description format of the rule can be represented by the format shown in FIG. In the format of FIG. 9, the circuit pattern before conversion is described in the From field, and the circuit pattern after conversion is described in the To field. In the rule of this embodiment, only the circuit pattern before and after the conversion is described, but depending on the situation, it is possible to describe the application condition of the rule, the additional information of the circuit, the attribute of the rule, the call of the built-in function, etc. You may change it. In such rule description, the circuit conversion program code is generated by the processing as shown in FIG.
【００２８】ルール生成部１３では、図２に示す処理を
行う。まず、与えられたルール記述を解析し（ステップ
Ｓ２１）、変換前回路パターンを検索するマッチング部
分のプログラムコードを生成し（ステップＳ２２）、変
換前回路を削除するプログラムコードを生成し（ステッ
プＳ２３）、変換後回路を挿入するプログラムコードを
生成することによりルールを生成する（ステップＳ２
４）。生成された回路変換プログラムコードはルール記
憶部１７に記憶される。The rule generator 13 performs the processing shown in FIG. First, the given rule description is analyzed (step S21), the program code of the matching portion for searching the circuit pattern before conversion is generated (step S22), and the program code for deleting the circuit before conversion is generated (step S23). , A rule is generated by generating a program code for inserting the converted circuit (step S2).
4). The generated circuit conversion program code is stored in the rule storage unit 17.
【００２９】次に、このルール生成系の全体について、
回路例からルールを自動的に作成する処理フローを図３
に示す。初期回路提供部は複数の初期回路を提供する場
合があるが、そのときは図３の処理を初期回路の個数分
繰り返す。生成された回路変換プログラムコードはルー
ル記憶部１７に記憶される。論理合成エンジンがそれを
実行することによりルールが実行される。Next, regarding the entire rule generation system,
Figure 3 shows the process flow for automatically creating rules from circuit examples.
Shown in The initial circuit providing unit may provide a plurality of initial circuits, in which case the process of FIG. 3 is repeated for the number of initial circuits. The generated circuit conversion program code is stored in the rule storage unit 17. The rule is executed by the logic synthesis engine executing it.
【００３０】以上、ルール生成系の各部の説明から明ら
かなように、新たに作成し登録されたルールにより、図
５の回路は簡単化されるようになり、さらに同様の回路
パターンを含む今まで簡単化されなかった回路も簡単化
されるようになる。このようなルールの作成処理を繰り
返すことにより、ルールベースシステムの性能を向上さ
せることができる。As is apparent from the description of each part of the rule generation system, the newly created and registered rule simplifies the circuit of FIG. 5 and further includes a similar circuit pattern until now. Circuits that have not been simplified will also be simplified. By repeating such rule creation processing, the performance of the rule-based system can be improved.
【００３１】また、初期回路として、多くの回路例に対
してルールを作成することにより、さまざまな種類の有
効なルールをもったルールベースシステムを構築するこ
とができる。また、ルール記述生成部１１で生成された
ルール記述をルール記述保持部１５にて保持させてもよ
い。このルール記述は前述のように図９に示す如く文字
コードであるため、ユーザがどのようなルールが生成さ
れたかを検証等することができる。By creating rules for many circuit examples as the initial circuit, it is possible to construct a rule-based system having various kinds of effective rules. Further, the rule description generated by the rule description generation unit 11 may be held in the rule description holding unit 15. Since this rule description is a character code as shown in FIG. 9 as described above, the user can verify what kind of rule was generated.
【００３２】また、ルール記述として条件判定用の記述
部分を有してもよいし実行可能プログラムを呼び出せる
ようにしてもよい。あるいは、外部入力、外部出力、内
部変数が定義できる宣言部を備えてもよい。Further, the rule description may have a description part for condition determination, or an executable program may be called. Alternatively, a declarative unit that can define external input, external output, and internal variable may be provided.
【００３３】次に、ルール操作系の各部について説明す
る。ルール記憶部１７は、前述したルール生成部１３に
て生成された回路変換ルールを逐次保持する。このルー
ルの保持にはルールの種類ごとに分類し、グループ分け
することが検索の迅速性等の点で好ましい。Next, each part of the rule operation system will be described. The rule storage unit 17 sequentially holds the circuit conversion rules generated by the rule generation unit 13 described above. In order to retain the rules, it is preferable to classify them according to the types of rules and divide them into groups in terms of speed of search and the like.
【００３４】また、ルールは、部分論理回路の割り当て
ルール、面積最適化ルール、タイミング最適化ルール、
消費電力最適化ルール等であってもよい。Further, the rules include allocation rules of partial logic circuits, area optimization rules, timing optimization rules,
It may be a power consumption optimization rule or the like.
【００３５】論理合成エンジン部１９は、実行可能プロ
グラムを解読し実行するためのものであり、所望のルー
ルをルール記憶部１７から検索し、適用する。The logic synthesis engine unit 19 is for decoding and executing an executable program, and retrieves a desired rule from the rule storage unit 17 and applies it.
【００３６】論理合成エンジン部１９は論理合成の任意
の段階で任意ルールを適用することが可能である。The logic synthesis engine unit 19 can apply an arbitrary rule at an arbitrary stage of logic synthesis.
【００３７】ルール適用頻度記憶部２１では、回路を合
成するたびに各ルールの適用されたルールの履歴をとり
各ルールの適用頻度を集計し、それまで記憶していたル
ール適用の頻度の情報を更新する。The rule application frequency storage unit 21 collects the history of rules applied to each rule each time a circuit is synthesized, collects the application frequency of each rule, and stores the information of the rule application frequency stored until then. Update.
【００３８】ルール記憶部操作部２３では、ルール適用
頻度記憶部２１に保持されている情報をもとに、適用頻
度の低いルールを見つけ出しルール記憶部から抹消す
る。同時に、ルール適用頻度記憶部２１からもそのルー
ルのデータを抹消する。ルールを抹消するかどうかの判
定基準としては、適用回数が指定された値より少ない場
合、全ルールの適用回数に対する適用頻度の割合が指定
された値より低い場合、ある期間そのルールが一度も適
用されなかった場合など、さまざまな場合が考えられ、
状況に応じてそれを採用してもよい。また、複数の判定
基準を組み合わせてもよい。このように、適用頻度の低
いルールを抹消していくことにより、実際に有用なルー
ルが残ることにより、いたずらにルールベースが巨大化
していくことを防ぐことができ、ルール選択時の処理効
率の向上、ルールベースの占めるメモリ量の削減につな
がる。The rule storage unit operation unit 23 finds a rule with a low application frequency based on the information stored in the rule application frequency storage unit 21 and deletes it from the rule storage unit. At the same time, the data of the rule is deleted from the rule application frequency storage unit 21. As a criterion for erasing a rule, if the number of times of application is less than the specified value, or if the ratio of application frequency to the number of times of application of all rules is less than the specified value, the rule is applied for a certain period of time. There are various cases, such as when it was not done,
It may be adopted depending on the situation. Also, a plurality of determination criteria may be combined. In this way, by deleting the rules that are applied infrequently, it is possible to prevent the rule base from becoming huge due to the fact that useful rules actually remain, and to improve the processing efficiency when selecting rules. It leads to improvement and reduction of the amount of memory occupied by the rule base.
【００３９】次に、ルール統合部２５について図面を用
いて説明する。図１０はルール統合化部２５が複数のル
ールの合成前の回路の共通部分を共通化し、統合化した
ルールを作成する例を示している。この例では、説明の
ためルール記述の形式で記載してある。図面左上は、回
路Ａと回路Ｂからなる回路に対しては回路Ｘに簡単化さ
れるルールであるルール１（rule1 ）を示しており、ま
た、図面右上部は、回路Ａと回路Ｃからなる回路に対し
ては回路Ｙに簡単化されるルールであるルール２（rule
2 ）を示している。従って、これらのルールが適用され
る簡単化前には回路Ａという共通部分を有している。こ
れらルール１及びルール２をルール統合部２５にてルー
ルを統合した場合には、図面下部に示すような新たなル
ール１＋２が作成される。このルール１＋２は、回路Ａ
が存在した場合には、その回路Ａの付近に回路Ｂが存在
するか若しくは回路Ｃが存在するかを探索した上でルー
ルを適用する。ルール統合化部は新たに作成したルール
を評価し、そのルールが有用であればルール記憶部に登
録するというようなルール評価、ルール管理機能をもつ
ようにしてもよい。Next, the rule integration section 25 will be described with reference to the drawings. FIG. 10 shows an example in which the rule unifying unit 25 creates a unified rule by unifying the common parts of the circuits before combining the plurality of rules. In this example, a rule description format is used for the sake of explanation. The upper left part of the drawing shows rule 1 (rule1) which is a rule simplified to the circuit X for the circuit composed of the circuit A and the circuit B, and the upper right part of the drawing consists of the circuit A and the circuit C. For circuits, rule 2 (rule
2) is shown. Therefore, there is a common part of the circuit A before simplification to which these rules are applied. When the rules 1 and 2 are integrated by the rule integration unit 25, a new rule 1 + 2 as shown in the lower part of the drawing is created. This rule 1 + 2 is circuit A
If there is, the rule is applied after searching whether the circuit B or the circuit C exists near the circuit A. The rule integration unit may have a rule evaluation and rule management function of evaluating a newly created rule and registering it in the rule storage unit if the rule is useful.
【００４０】一般に、複数のルールからなる場合（図面
上部）にはいずれか一方のルールが先に適用されるた
め、他のルールを適用した場合の方が良い結果を得るこ
とができたとしても先に一方のルールが適用されてしま
うが、ルール統合部によれば、ルールを関連づけておく
ことで回路変換効率の良い結果を得ることができる。In general, when a plurality of rules are included (the upper part of the drawing), one of the rules is applied first, so that even if the other rule is applied, a better result can be obtained. Although one of the rules is applied first, the rule integrating unit can obtain a result with good circuit conversion efficiency by associating the rules with each other.
【００４１】また、合成後の回路の共通部分を共通化
し、新たに統合化されたルールを作成することもでき
る。統合化されて新たに作成されたルール記述も、ルー
ル生成部のプログラムコード生成を修正することによ
り、容易に実行プログラムに変換できる。It is also possible to make the common part of the circuit after synthesis common and create a new integrated rule. The integrated and newly created rule description can be easily converted into an execution program by modifying the program code generation of the rule generation unit.
【００４２】[0042]
【発明の効果】以上説明してきたように、本発明によれ
ば簡単化前後の論理回路を対にして表記した簡単化規則
を用いることにより、ルール管理やルール作成が容易に
なるため、簡単なルール記述でルールを定義することが
できるので、回路変換ルールを効率良く生成、適用する
ことができるようになるのである。また、回路変換ルー
ルを自動作成することにより、人手では実質不可能であ
った膨大なルール数のルールベースシステムを効率よく
構築することができる。As described above, according to the present invention, by using the simplification rule in which the logic circuits before and after the simplification are described as a pair, the rule management and the rule creation are facilitated. Since the rule can be defined by the rule description, the circuit conversion rule can be efficiently generated and applied. In addition, by automatically creating the circuit conversion rule, it is possible to efficiently construct a rule-based system with a huge number of rules, which was virtually impossible by hand.
【００４３】また、簡単化できなかった回路をルール作
成用の回路として与えることにより、少なくともその回
路は簡単化できるようなルールを作成し登録することが
できる。これを繰り返すことにより、実回路で使用され
る実用的なルールを増やすことになる。Further, by giving a circuit that could not be simplified as a circuit for rule creation, it is possible to create and register a rule that can simplify the circuit at least. By repeating this, the practical rules used in the actual circuit will be increased.
【００４４】さらに、適用頻度の少ないルールを抹消す
る機能も付け加えることにより、ルールベースの質の向
上につながる。Furthermore, the quality of the rule base can be improved by adding a function of deleting rules that are less frequently applied.
【図１】本発明に係る論理合成システムの構成を示すブ
ロック図である。FIG. 1 is a block diagram showing a configuration of a logic synthesis system according to the present invention.
【図２】ルール生成部の処理フローを示す図である。FIG. 2 is a diagram showing a processing flow of a rule generation unit.
【図３】回路例からルールを自動作成する処理のフロー
を示す図である。FIG. 3 is a diagram showing a flow of processing for automatically creating a rule from a circuit example.
【図４】ルール記述生成部の処理フローを示す図であ
る。FIG. 4 is a diagram showing a processing flow of a rule description generation unit.
【図５】ルール作成用に与えられた論理回路の一例を示
す図である。FIG. 5 is a diagram showing an example of a logic circuit provided for rule creation.
【図６】（ａ）は抽出された部分回路１（変換前回路）
を示す図であり、（ｂ）は抽出された部分回路２を示す
図である。FIG. 6A is an extracted partial circuit 1 (pre-conversion circuit).
FIG. 3B is a diagram showing the extracted partial circuit 2.
【図７】変換後回路を示す図である。FIG. 7 is a diagram showing a circuit after conversion.
【図８】（ａ）は、変換化前の回路を示し、（ｂ）は作
成された変換後の回路を示す図である。FIG. 8A is a diagram showing a circuit before conversion, and FIG. 8B is a diagram showing a created circuit after conversion.
【図９】ルール記述の例を示す図である。FIG. 9 is a diagram showing an example of a rule description.
【図１０】ルール統合の例を示す図である。FIG. 10 is a diagram showing an example of rule integration.
１ 論理合成システムのルールベース部 ３ ルール用回路保持部 ５ 初期回路提供部 ７ 論理簡単化部 ９ 簡単化判定部 １１ ルール記述生成部 １３ ルール生成部 １５ ルール記述保持部 １７ ルール記憶部 １９ 論理合成エンジン部 ２１ ルール適用頻度記憶部 ２３ ルール記憶部操作部 ２５ ルール統合部 ２７ 合成対象回路保持部 1 rule base part of logic synthesis system 3 rule circuit holding part 5 initial circuit providing part 7 logic simplification part 9 simplification determination part 11 rule description generation part 13 rule generation part 15 rule description holding part 17 rule storage part 19 logic synthesis Engine unit 21 Rule application frequency storage unit 23 Rule storage unit operation unit 25 Rule integration unit 27 Synthesis target circuit holding unit
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7048590AJPH08249358A (en) | 1995-03-08 | 1995-03-08 | Logic synthesis system |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7048590AJPH08249358A (en) | 1995-03-08 | 1995-03-08 | Logic synthesis system |
| Publication Number | Publication Date |
|---|---|
| JPH08249358Atrue JPH08249358A (en) | 1996-09-27 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7048590APendingJPH08249358A (en) | 1995-03-08 | 1995-03-08 | Logic synthesis system |
| Country | Link |
|---|---|
| JP (1) | JPH08249358A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001027944A (en)* | 1999-07-14 | 2001-01-30 | Fujitsu Ltd | Device with menu interface and program recording medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2001027944A (en)* | 1999-07-14 | 2001-01-30 | Fujitsu Ltd | Device with menu interface and program recording medium |
| Publication | Publication Date | Title |
|---|---|---|
| US5197016A (en) | Integrated silicon-software compiler | |
| US5150308A (en) | Parameter and rule creation and modification mechanism for use by a procedure for synthesis of logic circuit designs | |
| JP4463431B2 (en) | Method for extracting information from a database | |
| JPH07120276B2 (en) | Simulation program generation method | |
| JP2788850B2 (en) | Optimal menu inquiry method and editing method of structural data by hierarchical menu inquiry | |
| CN106844380A (en) | A kind of database operation method, information processing method and related device | |
| JPH08101861A (en) | Logic circuit synthesizer | |
| CN105138335A (en) | Function call path extracting method and device based on control flow diagram | |
| US6477689B1 (en) | Architectural structure of a process netlist design tool | |
| US7447617B2 (en) | Data processing device designing method, data processing device designing apparatus, program and computer readable information recording medium | |
| CN113569524A (en) | Method for extracting clock tree based on comprehensive netlist in chip design and application | |
| CN108228187A (en) | A kind of global optimization method of mathematical program | |
| JPH06290086A (en) | Structure data processor | |
| CN117573316A (en) | Optimization method, processing method, system and storage medium of business calculation graph | |
| Calderón | Formalizing constructive projective geometry in Agda | |
| JPH08249358A (en) | Logic synthesis system | |
| CN117203647A (en) | Processor and method for tensor network contraction in quantum simulators | |
| Rundensteiner et al. | Component synthesis from functional descriptions | |
| US5801957A (en) | Implicit tree-mapping technique | |
| CN115146485A (en) | Radio frequency link simulation method based on GPU acceleration | |
| JP2853649B2 (en) | How to create a logic simulation model | |
| JP2824482B2 (en) | Variable order decision method of binary decision diagram | |
| JP2009544091A (en) | Electronic circuit synthesis | |
| CN116661793B (en) | Method for generating hardware description language supporting machine learning and compiling tool chain | |
| US8392889B2 (en) | Methods, systems, and computer program products for real time configuration and analysis of network based algorithmic service objectives |