JPH0728858A - 論理回路合成装置 - Google Patents

Abstract

(57)【要約】 【目的】 合成後の回路面積を最小化し、かつ入力ゲー
トの出力時間を最小化する。 【構成】 入力された回路の中の２段にまたがる同一の
ゲートを１つにまとめる手段４と、ゲート抽出手段５で
抽出した各ゲートで入力回路を分割した際の回路面積を
計算しその値が最小となるゲートを抽出する手段６と、
入力信号の到着時間の早いものから順に整列２分木デー
タ構造を構成する手段７と、この整列２分木データ構造
から到着時間のもっとも早い信号を抽出してデータから
削除する手段８と、この削除した信号からゲート抽出手
段６で抽出したゲートを作成する手段９と、このゲート
作成手段９で作成したゲートの遅延を算出し新たに整列
２分木データ構造に追加する手段１０と、回路分割後マ
ッピングを行なう手段１１とを備えた論理回路合成装置
である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は論理回路設計における論
理回路の自動合成に関するものである。

【０００２】

【従来の技術】従来の論理回路の自動合成装置は、図９
に示すように構成されていた。すなわち、処理部３０ｄ
は複数段の論理式またはテクノロジ独立な回路図で記述
された組合せ回路情報９１と、入力信号の到着時間を含
む遅延制約情報９２と、各ゲートの機能ゲート遅延時間
を含むテクノロジライブラリ９３を入力し、分割する回
路と同種のファンイン制限を満たすゲートをライブラリ
から抽出する手段９４と、抽出したゲートを階段状に並
べる手段９５と、入力信号到着時間の最も遅い信号を抽
出し後段のゲートに入力して、回路を分割する手段９６
から構成されていた。

【０００３】

【発明が解決しようとする課題】しかしながら上記のよ
うな構成では、合成した回路の面積／消費電力について
考慮していないので、合成後の回路面積／消費電力が大
きくなるという問題点を有していた。

【０００４】従って本発明は上記問題点に鑑み、合成後
の回路面積を最小化あるいは消費電力を最小化し、かつ
入力ゲートの出力時間を最小化する論理回路合成装置を
提供することを第１の目的とする。

【０００５】さらに本発明は分割要求の優先度を指定
し、それを満たした範囲で入力ゲートの出力時間を最小
化する論理回路合成装置を提供することを第２の目的と
する。

【０００６】

【課題を解決するための手段】本発明の第一の発明の論
理回路合成装置は、論理式または回路情報から論理回路
を合成する装置において、複数段の論理式またはテクノ
ロジ独立な回路図で記述された組合せ回路情報と、入力
信号の到着時間を含む遅延制約情報と、各ゲートの機能
および面積およびゲート遅延時間を含むテクノロジライ
ブラリを処理部に入力し、前記処理部は入力された回路
の中の２段にまたがる同一のゲートを１つにまとめる手
段と、対象テクノロジライブラリから入力ゲートと同種
のゲートを抽出する手段と、抽出した各ゲートで入力回
路を分割した際の回路面積または消費電力を計算し、そ
の値が最小となるゲートを抽出する手段と、入力信号の
到着時間の早いものから順に整列２分木データ構造を構
成する手段と、この整列２分木データ構造から到着時間
のもっとも早い信号を抽出してデータから削除する手段
と、この削除した信号からゲート抽出手段で抽出したゲ
ートを作成する手段と、このゲート作成手段で作成した
ゲートの遅延を算出し新たに整列２分木データ構造に追
加する手段と、回路分割後マッピングを行なう手段とを
備えた構成により、第１の目的は達成できる。

【０００７】上記問題点を解決するために本発明の第二
の発明の論理回路合成装置は、本発明の第一の発明に追
加して、面積や消費電力等の優先する要求項目を選択で
きる手段を備えた構成により、第２の目的は達成でき
る。

【０００８】

【作用】本発明は上記した構成によって、ライブラリ中
から分割対象回路と同種のセルを抽出し、そのセルを用
いて回路を分割した場合の回路面積／消費電力を算出し
て比較し、面積／消費電力値が最小となるセルを用いて
回路分割を行なうことにより、分割後の回路面積／消費
電力を最小にすることができる。

【０００９】さらに、面積／消費電力が最小となるセル
を用いて回路分割する際、入力信号の到着時間により、
遅い信号は少ない段数で、また早い信号は多い段数で出
力に到達するように分割することにより、面積／消費電
力最小かつ入力ゲートの出力時間を最小にすることがで
きる。

【００１０】また、優先する要求の項目を指定すること
も可能である。

【００１１】

【実施例】以下本発明の一実施例の論理回路合成装置に
ついて、図面を参照しながら説明する。

【００１２】（実施例１）図１は本発明の第１の実施例
における論理回路合成装置の処理フローを表す図であ
る。

【００１３】図１において、１は分割対象の多入力ゲー
トを示す論理回路情報、２は分割対象の多入力ゲートの
入力信号の到着時間を表す遅延制約情報、３は各ゲート
の機能／面積／ゲート遅延時間を示す情報を持つテクノ
ロジライブラリである。

【００１４】処理部３０ａは、論理回路情報１から２段
に跨る同一ゲートを１つにまとめる手段４と、テクノロ
ジライブラリ３から手段４でまとめたゲートと同種のゲ
ートを抽出する手段５と、手段５で抽出したゲートを用
いて、手段４でまとめた分割対象ゲートを分割した場合
の回路面積を算出し、手段５で抽出したゲートが複数あ
る場合は、算出した面積の中でその面積が最小となるゲ
ートを抽出する手段６と、遅延制約情報２の入力信号の
到着時間から入力信号の整列２分木データ構造を作成す
る手段７と、手段７で作成した整列２分木データ構造か
ら到着時間の最も早い信号を抽出／削除する手段８と、
手段８で抽出した信号を用いて、手段６で抽出したゲー
トを作成する手段９と、手段９で作成したゲートの出力
時間を算出し、その出力信号と出力時間を整列２分木デ
ータ構造に追加する手段１０と、手段８、９、１０を繰
り返し、分割したゲートに対してテクノロジマッピング
を行なう手段１１から構成される。

【００１５】以上のように構成された論理回路合成装置
について、以下図１及び図２〜６を用いてその動作を説
明する。

【００１６】まず、分割対象多入力ゲートの論理回路情
報１とその入力信号の遅延制約情報２とテクノロジライ
ブラリ３を入力する。

【００１７】次に入力された多入力ゲートを１つにまと
める手段４を用い、多入力ゲートを１つにまとめる。図
２はこの様子と示すものである。

【００１８】次にこうして１つにまとめられたゲートと
同種のゲートをテクノロジライブラリ３から抽出する手
段５を用いて、該当するゲートを抽出する。本実施例で
は、テクノロジライブラリからここで対象となるゲート
として、AND2、AND3、AND4の３種を抽出したとする。

【００１９】次に回路面積が最小となるゲート抽出手段
６を用いて、手段５で抽出したAND2、AND3、AND4を用い
て回路分割した場合の面積を算出する。今、AND2の面積
を7.2、AND3の面積を9.4、AND4の面積を14.3とする。X
入力の多入力ゲートをY入力のゲートで分割する場合の
必要セル数F(X,Y)の関数は、（数１）であるので、抽出
した各セルを用いて回路分割した場合のセル数は、AND2
の場合6セル、AND3の場合3セル、AND4の場合2セルであ
る。回路面積を(セル数)×(セル面積)とした場合、各セ
ルを用いて回路分割すると分割後の面積は、AND2の場合
43.2、AND3の場合28.2、AND4の場合28.6であり、以上の
ことから、本実施例の場合、分割後回路面積を最小にす
るためには、AND3を用いて回路分割する必要がある。

【００２０】

【数１】

【００２１】次に整列２分木データ構造を作成する手段
７を用いて、遅延制約情報２に含まれる入力信号の到着
情報を参照して、到着時間が最も早い信号から上位にく
るような図３に示す整列２分木データ構造を構成する。
例えば、図３の"i2,8"は、i2の到着時間が8であること
を示す。

【００２２】次に整列２分木データ構造から到着時間の
最も早い信号を抽出し削除する手段８を用いて該当する
信号を削除する。本実施例の場合、到着時間の最も早い
信号はi2であり、これを削除して、再度整列２分木デー
タ構造を構成し直す。この処理を３度繰り返す。

【００２３】次にゲート作成手段９を用いて、手段８に
より抽出した３つの信号から手段６で抽出したゲートを
作成する。図４はゲート作成の様子を示す。

【００２４】次に作成したゲートの出力時間を算出す
る。出力時間は入力信号のうち最も到着時間の遅い信号
の到着時間にゲートの遅延時間を加えた値となる。今、
AND3のゲート遅延時間を8とすると、出力時間は、max
(8,10,12)+8=20である。そして手段９により作成したゲ
ートの出力信号をJ1とすると、整列２分木データ構造追
加手段１０を用いて、この出力信号を整列２分木データ
構造に追加する。図５は出力信号を追加している様子を
示す。

【００２５】整列２分木データ構造の要素が１つになる
まで手段８から１０を繰り返すと図６に示す回路が作成
される。

【００２６】以上のように本実施例によれば、入力され
た回路の中の２段にまたがる同一のゲートを１つにまと
める手段４と、対象テクノロジライブラリから入力ゲー
トと同種のゲートを抽出する手段５と、ゲート抽出手段
５で抽出した各ゲートで入力回路を分割した際の回路面
積を計算しその値が最小となるゲートを抽出する手段６
と、入力信号の到着時間の早いものから順に整列２分木
データ構造を構成する手段７と、整列２分木データ構造
から到着時間のもっとも早い信号を抽出してデータから
削除する手段８と、ここで削除した信号からゲート抽出
手段６で抽出したゲートを作成する手段９と、ゲート作
成手段９で作成したゲートの遅延を算出し新たに整列２
分木データ構造に追加する手段１０と、回路分割後マッ
ピングを行なう手段１１を設けることにより、合成後の
回路面積を最小化し、かつ入力ゲートの出力時間を最小
化することができる。

【００２７】（実施例２）図７は本発明の第２の実施例
における論理回路合成装置の処理フローを表す図であ
る。

【００２８】第１の実施例における処理フローを表す図
１の、回路面積が最小となるゲート抽出手段６に代え
て、消費電力が最小となるゲート抽出手段１６を備え
る。

【００２９】実施例１と同様に入力論理回路情報から２
段にまたがる同一のゲートを１つにまとめ、対象テクノ
ロジライブラリから入力ゲートと同種のゲートを抽出す
る。

【００３０】次に抽出したそれぞれのゲートで回路分割
した際の消費電力を算出し最小となるゲートを抽出す
る。X入力の多入力ゲートをY入力のゲートで分割する場
合の必要セル数の関係は、（数１）であるので、抽出し
た各セルを用いて回路分割した場合のセル数が算出され
る。また、テクノロジライブラリから各セルの消費電力
を抽出し、回路消費電力を(セル数)×(セル消費電力)と
すると、回路消費電力が算出される。こうして算出した
消費電力が最小になるセルを抽出し実施例１と同様に入
力回路を分割する。

【００３１】以上のように本実施例によれば、第１の実
施例における面積を算出し最小となるゲートの抽出手段
の面積を消費電力に代えて、消費電力を算出し最小とな
るゲートを抽出する手段を設けることにより、合成後の
回路消費電力を最小化し、かつ入力ゲートの出力時間を
最小化することができる。

【００３２】（実施例３）図８は本発明の第３の実施例
における論理回路合成装置の処理フローを表す図であ
る。

【００３３】第１の実施例における処理フローを表す図
１に加えて、回路分割の際の要求の優先する項目を入力
する手段２７を備える。

【００３４】実施例１と同様に入力論理回路情報から２
段にまたがる同一のゲートを１つにまとめ、対象テクノ
ロジライブラリから入力ゲートと同種のゲートを抽出す
る。

【００３５】次に手段２７より入力された、分割の際に
優先する要求項目について、手段２６は抽出したそれぞ
れのゲートで回路分割した際の値を算出し、その要求を
満たすゲートを抽出する。要求を満たすゲートを抽出す
る方法の一例としては一次線形式を利用する。要求項目
が３種ある場合、一次線形式をAx+By+Czとし、この式の
係数 A、B、Cで各要求項目x、y、zに対する重みづけを
行ない、この値が最小となるゲートを抽出する。これは
要求項目が一つの場合でも良い。その場合要求項目xの
係数Aのみを１とし、他の項目y、zの係数B、Cを０とす
る。このようにして抽出したゲートを用いて実施例１と
同様に入力回路を分割する。

【００３６】以上のように本実施例によれば、第１,第
２の実施例に追加して、面積や消費電力等の優先する要
求項目を選択できる手段２７を設けることにより、合成
後の回路に対して要求する項目を最小化し、かつ入力ゲ
ートの出力時間を最小化することができる。

【００３７】

【発明の効果】以上のように本発明は、論理式または回
路情報から論理回路を合成する装置において、複数段の
論理式またはテクノロジ独立な回路図で記述された組合
せ回路情報と、入力信号の到着時間を含む遅延制約情報
と、各ゲートの機能および面積およびゲート遅延時間を
含むテクノロジライブラリを入力し、入力された回路の
中の２段にまたがる同一のゲートを１つにまとめる手段
と、対象テクノロジライブラリから入力ゲートと同種の
ゲートを抽出する手段と、ゲート抽出手段で抽出した各
ゲートで入力回路を分割した際の回路面積または消費電
力を計算しその値が最小となるゲートを抽出する手段
と、入力信号の到着時間の早いものから順に整列２分木
データ構造を構成する手段と、整列２分木データ構造か
ら到着時間のもっとも早い信号を抽出してデータから削
除する手段と、ここで削除した信号からゲート抽出手段
で抽出したゲートを作成する手段と、ゲート作成手段で
作成したゲートの遅延を算出し新たに整列２分木データ
構造に追加する手段と、回路分割後マッピングを行なう
手段を設けることにより、合成後の回路面積／消費電力
を最小化し、かつ入力ゲートの出力時間を最小化するこ
とができる。

【００３８】また、面積や消費電力等の優先する要求項
目を選択できる手段を設けることにより、合成後の回路
に対して要求する項目を最小化し、かつ入力ゲートの出
力時間を最小化することができる。

【図面の簡単な説明】

【図１】本発明の第一の実施例における論理回路合成装
置の構成図

【図２】同実施例におけるゲートをまとめる様子を示す
図

【図３】同実施例における整列２分木データ構造を示す
図

【図４】同実施例におけるゲートの作成を示す図

【図５】同実施例における整列２分木データ構造への追
加を示す図

【図６】同実施例における分割後の回路図

【図７】本発明の第二の実施例における論理回路合成装
置の構成図

【図８】本発明の第三の実施例における論理回路合成装
置の構成図

【図９】従来の論理回路合成装置を示す構成図

【符号の説明】

４ 同一のゲートを１つにまとめる手段 ５ 対象ゲート抽出手段 ６ 回路面積が最小となるゲートを抽出する手段 ７ 整列２分木データ構造を構成する手段 ３０ 処理部

Claims (2)

【特許請求の範囲】
1. 【請求項１】論理式または回路情報から論理回路を合成
   する装置において、複数段の論理式またはテクノロジ独
   立な回路図で記述された組合せ回路情報と、入力信号の
   到着時間を含む遅延制約情報と、各ゲートの機能および
   面積およびゲート遅延時間を含むテクノロジライブラリ
   を処理部に入力し、 前記処理部は、 入力された回路の中の２段に跨る同一のゲートを１つに
   まとめる手段と、 対象テクノロジライブラリから入力ゲートと同種のゲー
   トを抽出する手段と、 このゲート抽出手段で抽出した各ゲートで入力回路を分
   割した際の回路面積または消費電力を計算し、その値が
   最小となるゲートを抽出する手段と、 入力信号の到着時間の早いものから順に整列２分木デー
   タ構造を構成する手段と、 この整列２分木データ構造から到着時間のもっとも早い
   信号を抽出してデータから削除する手段と、 この削除した信号から前記ゲート抽出手段で抽出したゲ
   ートを作成する手段と、 このゲート作成手段で作成したゲートの遅延を算出し新
   たに整列２分木データ構造に追加する手段と、 回路分割後マッピングを行なう手段とを備えた論理回路
   合成装置。
2. 【請求項２】面積や消費電力等の優先する要求項目を選
   択する手段を設けた請求項１記載の論理回路合成装置。