[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JP2002215711A - Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit - Google Patents

Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit

Info

Publication number
JP2002215711A
JP2002215711A JP2001347206A JP2001347206A JP2002215711A JP 2002215711 A JP2002215711 A JP 2002215711A JP 2001347206 A JP2001347206 A JP 2001347206A JP 2001347206 A JP2001347206 A JP 2001347206A JP 2002215711 A JP2002215711 A JP 2002215711A
Authority
JP
Japan
Prior art keywords
constraint
timing constraint
matrix
row
column
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
JP2001347206A
Other languages
Japanese (ja)
Inventor
Taeko Matsunaga
多苗子 松永
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to JP2001347206A priority Critical patent/JP2002215711A/en
Publication of JP2002215711A publication Critical patent/JP2002215711A/en
Withdrawn legal-status Critical Current

Links

Landscapes

  • Tests Of Electronic Circuits (AREA)

Abstract

PROBLEM TO BE SOLVED: To minimize the number of constraint set as units for subjects for delay inspection, and achieve further efficiency of delay inspection to each path. SOLUTION: A timing constraint matrix b comprising time constraint to each path between start point side/end point side flip-flops in a combinational circuit is formed, from which constraint set capable of simultaneously satisfying all of reaching timing and demanded timing of the start point side/end point side flip flops(FF) based on the time constraint are determined. Rows of the matrix b represent FF0-5 on the start point side, and columns represent FF6-12 on the end point side. There is no time constraint to a path between 0 and 6, and a time constraint between path 0 and 6 is 15. The constraint set of the row b is, for example, an set of the columns 6, 10, 11, and 12 (excluding 0 of the row of ×), and a set of the columns 7, 8, and 9. Before determining the constraint set, contraction and split of the timing constraint matrix are conducted, and minimum covering problems for constraint set candidates are solved.

Description

【発明の詳細な説明】DETAILED DESCRIPTION OF THE INVENTION

【0001】[0001]

【発明の属する技術分野】本発明は、論理回路のタイミ
ング制約生成方式に関し、特に複数のフリップフロップ
(以下、必要に応じて「FF」と表現する。)と組み合
わせ回路からなる論理回路のタイミング制約の生成に関
するものである。
BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a timing constraint generation method for a logic circuit, and more particularly to a timing constraint generation method for a logic circuit comprising a plurality of flip-flops (hereinafter, referred to as "FF" as necessary) and a combinational circuit. Is related to the generation of

【0002】このような論理回路における信号は、FF
のクロックピンまたは外部入力ピンから始まり、FFの
デ−タピンまたは外部出力ピンで終わるパスを伝播す
る。
[0002] The signal in such a logic circuit is FF
From the clock pin or external input pin of the FF and ends at the data pin or external output pin of the FF.

【0003】論理回路が正しく動作するには、それぞれ
のパスにおける伝播信号の遅延時間が、当該パスの始点
および終点の入力側/出力側FFを駆動する各クロック
のタイミング関係などに基づいて規定される制約条件
(パスごとの時間制約)を満たさなければならない。
In order for a logic circuit to operate properly, the delay time of a propagation signal in each path is defined based on the timing relationship between clocks for driving input / output FFs at the start and end of the path. Constraints (time constraints for each pass) must be satisfied.

【0004】そのため、回路設計過程においては、回路
の遅延時間を計算してこれがパスごとの制約条件を満た
しているかどうかの検査を行ない、満たしていないパス
についてはその遅延部分を改善するといったことを繰り
返している。
For this reason, in the circuit design process, the delay time of a circuit is calculated, and it is checked whether or not the delay time satisfies a constraint condition for each path. Repeat.

【0005】この検査の効率化を図る上で、上記制約条
件のすべてを満たす始点側/終点側FFの時刻(後述の
到達時刻および要求時刻)を、現実的な時間オーダで全
体として一意に設定できるようにすることが望ましく、
本発明はこの要請に応えるものである。
[0005] In order to improve the efficiency of this inspection, the times (arrival times and required times described later) of the start point / end point FF satisfying all of the above constraints are uniquely set as a whole in a realistic time order. It is desirable to be able to
The present invention addresses this need.

【0006】[0006]

【従来の技術】図12は、対象とする論理回路やクロッ
ク定義などの説明図である。(a)はFF0〜FF12お
よび組み合わせ回路1で構成された論理回路を示し、
(b)乃至 (d)はこの論理回路に対するクロック定義など
のタイミング制約を示している。
2. Description of the Related Art FIG. 12 is an explanatory diagram of a target logic circuit and a clock definition. (a) shows a logic circuit composed of FF0 to FF12 and the combinational circuit 1,
(b) to (d) show timing constraints such as a clock definition for the logic circuit.

【0007】FF0〜FF12の間には図示の接続関係
が成立し、例えばFF0からはFF6とFF9へのパス
が、またFF1からはFF6とFF7へのパスがそれぞ
れ存在している。
The connection shown in the figure is established between FF0 to FF12. For example, a path from FF0 to FF6 and FF9, and a path from FF1 to FF6 and FF7, respectively.

【0008】なお、説明の便宜上、パスの始点となるフ
リップフロップを6個(FF0〜FF5)とし、終点と
なるフリップフロップを7個(FF6〜FF12)とし
ているが、現実の論理回路における始点FFおよび終点
FFそれぞれの総数は例えば数万,数十万のオーダーで
ある。
For convenience of explanation, the number of flip-flops which are the starting points of the path is six (FF0 to FF5) and the number of the flip-flops which are the ending point is seven (FF6 to FF12). And the total number of the end point FFs is, for example, on the order of tens of thousands or hundreds of thousands.

【0009】図12の論理回路のタイミング制約は、 ・FF0〜FF12は図示のクロックck1,ck2,
ck0の立ち上がりエッジによって駆動され、 ・クロックck1は周期が10nsであり、 ・クロックck2は周期が10nsであってクロックc
k1とは位相が半周期だけずれており、 ・クロックck0は周期が2nsであってクロックck
1,ck2とは同期していない、 ・FF1からFF6へのパスおよびFF5からFF10
へのパスにおける信号伝播はそれぞれ2サイクルで行な
われる、 などである。
The timing constraints of the logic circuit shown in FIG. 12 are as follows: FF0 to FF12 are clocks ck1, ck2,
driven by the rising edge of ck0, clock ck1 has a period of 10 ns, clock ck2 has a period of 10 ns and clock c
The phase of the clock ck0 is shifted by a half cycle from the k1.
1, not synchronized with ck2, the path from FF1 to FF6 and from FF5 to FF10
Signal propagation in the path to each is performed in two cycles, and so on.

【0010】したがって、図12(a) の各パスの時間制
約は、 ・FF0(ck0)からFF6(ck2)へのパスが
「制約なし」 ・FF0(ck0)からFF9(ck0)へのパスが
「2ns」 ・FF1(ck1)からFF6(ck2)へのパス(2
サイクル指定)が「15ns」 ・FF1(ck1)からFF7(ck1)へのパスが
「10ns」 ・FF2(ck1)からFF6(ck2)へのパスが
「5ns」 ・FF2(ck1)からFF7(ck1)へのパスが
「10ns」 ・FF2(ck1)からFF8(ck1)へのパスが
「10ns」 ・FF3(ck1)からFF6(ck2)へのパスが
「5ns」 ・FF3(ck1)からFF7(ck1)へのパスが
「10ns」 ・FF4(ck1)からFF10(ck2)へのパスが
「5ns」 ・FF4(ck1)からFF11(ck2)へのパスが
「5ns」 ・FF5(ck1)からFF10(ck2)へのパス
(2サイクル指定)が「15ns」 ・FF5(ck1)からFF12(ck2)へのパスが
「5ns」 である。
Therefore, the time constraint of each path in FIG. 12A is as follows: The path from FF0 (ck0) to FF6 (ck2) is “no constraint”. The path from FF0 (ck0) to FF9 (ck0) is "2 ns"-The path (2 from FF1 (ck1) to FF6 (ck2)
(Cycle designation) is "15 ns"-The path from FF1 (ck1) to FF7 (ck1) is "10 ns"-The path from FF2 (ck1) to FF6 (ck2) is "5 ns"-FF2 (ck1) to FF7 (ck1) ) Is “10 ns” • The path from FF2 (ck1) to FF8 (ck1) is “10 ns” • The path from FF3 (ck1) to FF6 (ck2) is “5 ns” • FF3 (ck1) to FF7 ( The path from FF4 (ck1) to FF10 (ck2) is "5 ns". The path from FF4 (ck1) to FF11 (ck2) is "5 ns". The path from FF4 (ck1) is "5 ns". The path to (ck2) (2 cycle designation) is “15 ns”. The path from FF5 (ck1) to FF12 (ck2) is “5 ns”.

【0011】FF0からFF6へのパスが「制約なし」
となるのは、FF0の駆動クロックck0とFF6の駆
動クロックck2とが互いに同期していないからであ
る。
The path from FF0 to FF6 is "no constraint"
This is because the driving clock ck0 of the FF0 and the driving clock ck2 of the FF6 are not synchronized with each other.

【0012】上述のように、この種の論理回路において
は各パスの伝播遅延時間がそこでの時間制約を満たすか
どうかの検査を実行している。
As described above, in this type of logic circuit, a check is made as to whether the propagation delay time of each path satisfies the time constraint there.

【0013】従来、検査効率を良くするため例えば複数
のパスの解析を同時に行なう検査手法などが用いられて
いる。
Conventionally, for improving the inspection efficiency, for example, an inspection method for simultaneously analyzing a plurality of paths has been used.

【0014】ここで、検査対象の論理回路において、周
波数や位相が異なる複数のクロック(ck1とck2な
ど)を用いたり、デ−タを受け取るタイミングが2サイ
クル以上のパス(FF1とFF6とのパスなど)が存在
する場合などには、FF間の各パスに対する時間制約が
同一になるとは限らない。各パスの時間制約は複数にな
るのが一般的である。図示の場合は「2」,「5」,
「10」,「15」の四つである。
Here, in the logic circuit to be tested, a plurality of clocks (ck1 and ck2, etc.) having different frequencies and phases are used, or a path for receiving data at least two cycles (a path between FF1 and FF6). ), The time constraints for each path between FFs are not necessarily the same. Generally, there are a plurality of time constraints for each path. In the case shown, "2", "5",
There are four “10” and “15”.

【0015】この場合、複数のパスの時間制約を同時に
扱おうとすると、始点側/終点側FFそれぞれの到達時
刻および要求時刻の全体を任意のFFに対して一意に設
定することができない。
In this case, if the time constraints of a plurality of paths are to be handled at the same time, the entire arrival time and requested time of each of the start-side / end-point FFs cannot be uniquely set for an arbitrary FF.

【0016】例えば図12の論理回路において、FF1
の到達時刻を「0」とした場合、FF6の要求時刻は
「15(=0+15)」で、FF7の要求時刻は「10
(=0+10)」となる。
For example, in the logic circuit shown in FIG.
, The request time of FF6 is “15 (= 0 + 15)”, and the request time of FF7 is “10”.
(= 0 + 10) ".

【0017】次にFF2からFF6へのパスにおいて、
FF6の要求時刻が先の「15」であるとするとFF2
の到達時刻は「10(=15−5)」になる。
Next, in the path from FF2 to FF6,
If the request time of FF6 is "15", FF2
Is "10 (= 15-5)".

【0018】次にこの到達時刻「10」に基づいてFF
2からFF7へのパスを考えると、FF7の要求時刻は
「20(=10+10)」となり、FF7に対して先の
「10」と今回の「20」いう二つの要求時刻が発生し
てしまう。
Next, based on the arrival time “10”, the FF
Considering the path from 2 to FF7, the request time of FF7 is "20 (= 10 + 10)", and two request times of "10" earlier and "20" this time are generated for FF7.

【0019】これを解決する手法として、すべての対象
パスに対する時間的な制約条件を所定の制約集合単位に
分割する、すなわち始点側/終点側FFそれぞれの到達
時刻および要求時刻を両立可能な形で設定可能な制約集
合(Compatible ConstraintSet)の単位に分割するとい
うアプローチが提案されている。以下の説明では、必要
に応じて制約集合を「CCS」と表現する。
As a method for solving this problem, the temporal constraints on all target paths are divided into predetermined constraint set units, that is, the arrival time and the required time of the start / end FFs are compatible. There has been proposed an approach of dividing the data into units of a configurable constraint set (Compatible ConstraintSet). In the following description, the constraint set is expressed as “CCS” as necessary.

【0020】この手法では、すべての対象パスがどれか
の制約集合に含まれることになり、始点側/終点側FF
の到達時刻および要求時刻が制約集合ごとに一意の形で
設定される。
In this method, all target paths are included in any constraint set, and the start-point / end-point FF
Is set in a unique form for each constraint set.

【0021】そして、論理回路の各パスの始点側/終点
側FFについて、この制約集合ごとの到達時刻および要
求時刻を満足するかどうかの遅延検査が行なわれる。
Then, a delay check is performed on the start point / end point FF of each path of the logic circuit to determine whether the arrival time and the required time for each constraint set are satisfied.

【0022】[0022]

【発明が解決しようとする課題】このような制約集合に
より始点側/終点側FFの時間を設定する手法は、周波
数や位相が異なる複数のクロックを用いたり、デ−タを
受け取るタイミングが2サイクル以上のパスが存在する
論理回路の場合にも、すべての対象FFの到達時刻およ
び要求時刻を矛盾なく設定できるといった効果を奏して
いる。
The method of setting the time of the start point / end point FF based on such a constraint set uses a plurality of clocks having different frequencies and phases, or the timing of receiving data is two cycles. Even in the case of a logic circuit having the above paths, there is an effect that arrival times and required times of all target FFs can be set without contradiction.

【0023】一方、制約集合の求め方はいわば試行錯誤
的であるため、その個数の最適性は必ずしも保証されな
い。
On the other hand, the method of obtaining the constraint set is trial and error, so that the optimality of the number is not necessarily guaranteed.

【0024】論理回路全体の遅延検査における要処理時
間や必要メモリ量などは制約集合の個数に依存する。特
に現実の始点側/終点側FFの個数規模では、各パス間
の制約条件が必要以上に多くの制約集合に分割されると
き、遅延計算処理への影響は顕著なものとなる。
The required processing time and the required memory amount in the delay test of the entire logic circuit depend on the number of constraint sets. In particular, in the actual scale of the number of FFs on the start point side / end point side, when the constraint conditions between the paths are divided into an unnecessarily large number of constraint sets, the influence on the delay calculation processing becomes significant.

【0025】上記アプローチは、上述のような優れた効
果を有しているが、論理回路全体の制約集合の総数を少
なくする、望ましくは厳密最小個にするといった点で改
善の余地を残したものである。
Although the above approach has the above-mentioned excellent effects, it leaves room for improvement in that the total number of constraint sets in the entire logic circuit is reduced, and preferably the number is strictly minimized. It is.

【0026】そこで、本発明では、始点側/終点側FF
間の各パスの制約条件を要素とする行列を作成し、この
行列から制約集合CCSを求めていくことにより、論理
回路全体に対する最終的な制約集合の個数の縮減化を積
極的に図り、当該パスの遅延検査を、その要処理時間や
使用メモリ量などの点で効率的に行なうことを目的とす
る。
Therefore, in the present invention, the start point / end point FF
By creating a matrix having the constraint conditions of each path between the elements as elements, and obtaining the constraint set CCS from this matrix, the final reduction of the number of constraint sets for the entire logic circuit is positively achieved. An object of the present invention is to efficiently perform a path delay check in terms of the required processing time and the amount of memory used.

【0027】[0027]

【課題を解決するための手段】本発明では、この課題を
次のようにして解決する。 (1)論理回路を構成する始点側/終点側フリップフロ
ップのそれぞれを行/列とし、かつ当該フリップフロッ
プ間の各パスに対する制約条件を有効要素として示すタ
イミング制約行列を作成する第1の手段(例えば後述の
パス解析・コマンド解析部31, タイミング制約行列作
成部32)と、少なくとも一部の前記有効要素からな
り、それに対応の前記制約条件に基づく前記始点側フリ
ップフロップの到達時刻と前記終点側フリップフロップ
の要求時刻とをすべて同時に満足できる形の制約集合
を、前記タイミング制約行列から求める第2の手段(例
えば後述の縮小処理部33, 分割処理部34, CCS候
補生成部35, 最小被覆問題処理部36)と、前記制約
集合に対応の前記到達時刻および前記要求時刻を算出す
る第3の手段(例えば後述の到達時刻・要求時刻生成部
37)とを設ける。 (2)上記(1)において、第2の手段は、あらかじめ
前記タイミング制約行列の処理対象部分の行および列そ
れぞれの支配関係に基づいてその被支配行および被支配
列を削除する。 (3)上記(1), (2)において、第2の手段は、あ
らかじめ前記タイミング制約行列の処理対象部分を、そ
れぞれが互いに独立して前記到達時刻および前記要求時
刻を算出することが可能な部分行列に分割する。 (4)上記(1), (2), (3)において、第2の手
段は、あらかじめ複数の制約集合候補を対象にした最小
被覆問題を解く。
According to the present invention, this problem is solved as follows. (1) A first means for creating a timing constraint matrix indicating a start point / end point flip-flop constituting a logic circuit as a row / column and a constraint condition for each path between the flip-flops as an effective element ( For example, a path analysis / command analysis unit 31 and a timing constraint matrix creation unit 32), which will be described later, and at least a part of the effective elements, the arrival time of the start flip-flop and the end point based on the corresponding constraint condition Second means (for example, a reduction processing unit 33, a division processing unit 34, a CCS candidate generation unit 35, a minimum coverage problem Processing unit 36) and third means (for example, later) for calculating the arrival time and the request time corresponding to the constraint set The arrival time and the request time generating unit 37) and provided. (2) In the above (1), the second means deletes, in advance, the controlled row and the supported array based on the dominant relation of each row and column of the processing target portion of the timing constraint matrix. (3) In the above (1) and (2), the second means can previously calculate the arrival time and the request time independently of each other on the processing target portion of the timing constraint matrix independently of each other. Divide into submatrices. (4) In the above (1), (2), and (3), the second means solves the minimum covering problem for a plurality of constraint set candidates in advance.

【0028】本発明によれば、上記(1)のように、論
理回路の始点側/終点側フリップフロップ間の各パスに
対する制約条件からなるタイミング制約行列を作成し、
この行列から、この制約条件に基づく始点側/終点側フ
リップフロップの到達時刻および要求時刻をすべて同時
に満足できる形の制約集合を求めることにより、その個
数の最適性化を可能にし、各パスの遅延検査の効率化を
図っている。
According to the present invention, as described in the above (1), a timing constraint matrix comprising constraints on each path between the starting point / ending point flip-flops of the logic circuit is created,
From this matrix, a set of constraints that can simultaneously satisfy the arrival time and the required time of the start-side / end-point flip-flops based on the constraint conditions is obtained, thereby enabling optimization of the number of the flip-flops and delay of each path. We are trying to make inspections more efficient.

【0029】また、上記(2), (3)のように、制約
集合を求めるに先だって、タイミング制約行列の行およ
び列の支配関係や、タイミング制約行列の部分同士にお
ける始点側/終点側フリップフロップの到達時刻・要求
時刻算出の相互依存性に基づく当該行列の縮小・分割を
実行することにより、制約集合作成の効率化を図ってい
る。
Prior to obtaining the constraint set as described in (2) and (3) above, the dominant relationship between the rows and columns of the timing constraint matrix and the start point / end point flip-flops between the parts of the timing constraint matrix. By reducing and dividing the matrix based on the interdependency of the arrival time / request time calculation, the efficiency of constraint set creation is improved.

【0030】また、上記(4)のように、制約集合を求
めるに先だって、その複数の候補を含む部分行列を対象
にした最小被覆問題を解くことにより、制約集合個数の
最小性を保証し、各パスの遅延検査の一層の効率化を図
っている。
Further, as described in (4) above, prior to obtaining the constraint set, the minimum covering problem for the submatrix including the plurality of candidates is solved, thereby guaranteeing the minimum number of constraint sets. The efficiency of the delay test of each path is further improved.

【0031】本発明は、このような特徴を持つ論理回路
のタイミング制約生成方式を対象とし、さらには、この
タイミング制約を生成するためのプログラムや、当該プ
ログラムを記憶したコンピュータ読取り可能な記録媒体
も対象にしている。
The present invention is directed to a method for generating a timing constraint of a logic circuit having such characteristics, and further includes a program for generating the timing constraint and a computer-readable recording medium storing the program. It is targeted.

【0032】[0032]

【発明の実施の形態】図1乃至図11を参照して本発明
の実施の形態を説明する。
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to FIGS.

【0033】図1は、図12に対応のタイミング制約グ
ラフとタイミング制約行列を示している。これは、上述
の各パスの時間制約内容を反映させたものである。
FIG. 1 shows a timing constraint graph and a timing constraint matrix corresponding to FIG. This reflects the contents of the time constraint of each path described above.

【0034】図1(a) のタイミング制約グラフにおけ
る、ノード番号0〜12はそれぞれ図12(a) のFFの
番号を示し、ノード間を結ぶ各エッジの数字は時間制約
を示している。また、「制約なし」のパスに対応する無
効エッジ(ノード0とノード6との間のエッジ)を破線
で表している。
In the timing constraint graph of FIG. 1A, the node numbers 0 to 12 indicate the numbers of the FFs in FIG. 12A, and the numbers of the edges connecting the nodes indicate the time constraints. An invalid edge (an edge between node 0 and node 6) corresponding to the path of "no constraint" is indicated by a broken line.

【0035】図1(b) のタイミング制約行列の、行番号
0〜5および列番号6〜12はそれぞれ図1(a) のFF
の番号を示し、各行列要素の数字はその行番号と列番号
のFF間パスの時間制約を示している。
The row numbers 0 to 5 and the column numbers 6 to 12 of the timing constraint matrix of FIG.
, And the number of each matrix element indicates the time constraint of the inter-FF path of the row number and column number.

【0036】例えば、行番号2,列番号7の要素「1
0」はFF2からFF7へのパスの時間制約が「10n
s」であることを示している。また、「制約なしの要
素」については「×」で、「パスが存在しない要素」に
ついては「−」でそれぞれ表している。
For example, the element “1” of row number 2 and column number 7
"0" indicates that the time constraint of the path from FF2 to FF7 is "10n".
s ". Also, “elements without restrictions” are represented by “x”, and “elements without paths” are represented by “−”.

【0037】このタイミング制約行列Mに関して次の事
項を定義する。 (1) レクトアングル(rectangle) :タイミング制約行列
Mに含まれる部分行列であって、かつ、その要素中に
「×」を含んでいない部分行列P (2) 有効要素:タイミング制約行列Mの「×」,「−」
のいずれでもない要素、すなわち「パスの時間制約値」
を示している要素 (3) 有効な行:レクトアングルのP(i,j1)およびP(i,j
2)がともに有効要素である場合、行iは列j1,j2に
対して有効 (4) 有効な列:レクトアングルのP(i1,j)およびP(i2,
j)がともに有効要素である場合、列jは行i1,i2に
対して有効 (5) 行の距離(distance):レクトアングルの行i1,i
2に対するすべての有効な列それぞれの有効要素の差分
が一定の場合の、当該差分「dist(i1,i2) 」 (6) 列の距離(distance):レクトアングルの列j1,j
2に対するすべての有効な行それぞれの有効要素の差分
が一定の場合の、当該差分「dist(j1,j2) 」 (7) コンパティブルレクトアングル(compatible rectan
gle):後述のように、レクトアングルの各行(または各
列)の時刻を、当該行(または当該列)に対して有効な
列(または行)すべての時刻がどの行(またはどの列)
を用いて計算しても同一になるように設定できる場合
の、当該レクトアングル (8) コンパティブルプライム(compatible prime):ある
コンパティブルレクトアングルがタイミング制約行列M
の(行または列のいずれか一方を基準にして)他のどの
コンパティブルレクトアングルにも厳密に含まれない場
合の、当該コンパティブルレクトアングル (9) 行の支配関係(dominance) :タイミング制約行列M
の行i1,i2のすべての列jに関し、 ・「M(i2,j)=×」→「M(i1,j)=×」 ・「M(i2,j)が有効要素」→「M(i1,j)が有効要素」 ・すべての有効列の距離が一定 の関係が成立する場合の、当該行間の関係(行i1は行
i2を支配) (10)列の支配関係(dominance) :タイミング制約行列M
の列j1,j2のすべての行iに関し、 ・「M(i,j2)=×」→「M(i,j1)=×」 ・「M(i,j2)が有効要素」→「M(i,j1)が有効要素」 ・すべての有効行の距離が一定 の関係が成立する場合の、当該列間の関係(列j1は列
j2を支配)
The following items are defined for the timing constraint matrix M. (1) Rectangle: a sub-matrix P that is a sub-matrix included in the timing constraint matrix M and does not include “x” in its elements. (2) Effective element: “ × ”,“ − ”
Element that is neither of the above, ie, "path time constraint value"
(3) Valid rows: P (i, j1) and P (i, j
If both 2) are valid elements, row i is valid for columns j1 and j2. (4) Valid columns: P (i1, j) and P (i2,
If both j) are valid elements, column j is valid for rows i1 and i2. (5) Row distance (distance): rows i1 and i of the right angle
In the case where the differences of the effective elements of all the effective columns with respect to 2 are constant, the difference “dist (i1, i2)” (6) Distance of the columns: columns j1, j of the right angle
When the difference between the effective elements of all the valid rows for each of the two is constant, the difference “dist (j1, j2)” (7) Compatible rectangle (compatible rectan angle)
gle): As described below, the time of each row (or each column) of the rectoangle is the row (or which column) in which all the times (columns) valid for that row (or that column) are valid
(8) Compatible prime: A compatible compatible angle is a timing constraint matrix M
(9) Dominance of a row when it is not strictly included in any other compatible rectangle (based on either row or column). Constraint matrix M
For all columns j of rows i1 and i2 of the following, "M (i2, j) = ×" → "M (i1, j) = ×" ・ "M (i2, j) is an effective element" → "M ( i1, j) is an effective element. ”• When the relationship between all effective columns is constant, the relationship between the rows (row i1 dominates row i2) (10) Dominance of columns (dominance): timing Constraint matrix M
[M (i, j2) = ×] → [M (i, j1) = ×] ・ [M (i, j2) is an effective element] → [M ( i, j1) is an effective element. ”• Relationship between the columns when the distance between all the effective rows is constant (column j1 dominates column j2)

【0038】コンパティブルプライムに該当するレクト
アングル(部分行列P)をCCS候補としてタイミング
制約行列Mから抽出する。
A rectangle (sub matrix P) corresponding to the compatible prime is extracted from the timing constraint matrix M as a CCS candidate.

【0039】図1(b) のタイミング制約行列の場合、所
定のレクトアングルに対して、例えば、 ・行1は列6および列7に対して有効であり、 ・列7は行1, 行2および行3に対して有効であり、 ・行1と行2との距離「dist(i1,i2) 」は定義できず
(列6の差分は「−10」で列7の差分は「0」とな
り、当該差分が一致しないため)、 ・行2と行3との距離は「dist(i2,i3) =0」と定義で
き、 ・行4と行5との距離は「dist(i4,i5) =10」と定義
でき、 ・列6と列7との距離「dist(j6,j7) 」は定義できず
(行1の差分は「−5」で行2および行3の差分は
「5」となり、当該差分が一致しないため)、 ・列7と列8との距離は「dist(j7,j8) =0」と定義で
き、 ・列10と列11との距離は「dist(j10,j11) =0」と
定義できる。
In the case of the timing constraint matrix of FIG. 1B, for a given rectangle, for example: row 1 is valid for columns 6 and 7; column 7 is rows 1 and 2 And the distance between row 1 and row 2 cannot be defined (dist (i1, i2)) (the difference in column 6 is “−10” and the difference in column 7 is “0” The distance between row 2 and row 3 can be defined as “dist (i2, i3) = 0”. The distance between row 4 and row 5 is “dist (i4, i5 ) = 10 ”. The distance“ dist (j6, j7) ”between column 6 and column 7 cannot be defined (the difference between row 1 is“ −5 ”and the difference between row 2 and row 3 is“ 5 ", And the difference does not match). The distance between column 7 and column 8 can be defined as" dist (j7, j8) = 0 ". The distance between column 10 and column 11 is" dist (j10, j11) = 0 ".

【0040】また、タイミング制約行列において, 例え
ば、 ・行2は行3を支配し、 ・行3は行2を支配せず(列8の要素が上記支配条件を
満足しない)、 ・列7は列8を支配し、 ・列10は列11, 12を支配している。
Also, in the timing constraint matrix, for example: row 2 dominates row 3 row 3 does not dominate row 2 (elements in column 8 do not satisfy the above dominant condition); Column 8 dominates: Column 10 dominates columns 11, 12.

【0041】図1(b) の行2および行3とすべての列集
合からなるレクトアングル、並びに行4および行5とす
べての列集合からなるレクトアングルは、それぞれコン
パティブルレクトアングル(かつ、コンパティブルプラ
イム)に該当する。
In FIG. 1B, the rect angle composed of rows 2 and 3 and all column sets, and the rect angle composed of rows 4 and 5 and all column sets are respectively compatible rect angles (and Compatible Prime).

【0042】それは、例えば行4および行5のレクトア
ングルの場合、行4の時刻を「0」に、行5の時刻を
「−10」にそれぞれ設定することにより、当該行に対
して有効な列10の時刻は行4, 行5のどちらから計算
しても「5(0+5、または、−10+15)」となっ
て、上記(7) の定義に合致するからである。なお、行5
の設定時刻の「−10」は「dist(i4,i5) =10」の正
負の符号を反転させた値である。
For example, in the case of the rectangles of rows 4 and 5, by setting the time of row 4 to “0” and the time of row 5 to “−10”, respectively, This is because the time in column 10 is "5 (0 + 5 or -10 + 15)", whichever is calculated from either row 4 or row 5, which matches the definition of (7). Note that row 5
Is a value obtained by inverting the sign of “dist (i4, i5) = 10”.

【0043】このように行4, 行5における列10の時
刻を同一値に設定できることは、当該各行に対応のFF
および当該列に対応のFFの到達時刻/要求時刻が全体
として矛盾なく一意に設定されることを意味している。
The fact that the time of column 10 in rows 4 and 5 can be set to the same value as described above means that the FF corresponding to each row can be set.
This means that the arrival time / request time of the FF corresponding to the column is uniquely set as a whole without contradiction.

【0044】図2は、タイミング制約行列の生成処理手
順を示しており、その内容は次のようになっている。 (s11) 回路のネットリストを読み込んで回路構造情報と
してワーク領域(図示省略)に保持する。 (s12) ユーザから与えられたタイミング制約(使用クロ
ック情報やマルチサイクル指定など)を読み込んでワー
ク領域に保持する。 (s13) 上記回路構造情報に基づいてネットリストをパス
トレースし、その結果をワーク領域に保持する。このパ
ストレースでは、FFのクロックピンまたは外部入力ピ
ンを始点とし、またFFのデ−タ入力ピンまたは外部出
力ピンを終点とする回路トレースにより、各始点FF/
終点FFの接続関係を調べる。 (s14) このパストレースで得られた各パスの時間制約
を、その始点FFおよび終点FFを駆動する各クロック
情報に基づいて生成し、その結果をワーク領域に保持す
る。この時間制約は、マルチサイクルなどの指定を考慮
に入れたときの、始点側のクロックck1と終点側のク
ロックck2とのクロックエッジの差から求める。 (s15) 各パスの始点FF/終点FFを行/列とし、時間
制約を有効要素とするタイミング制約行列を生成して、
メモリ(図示省略)に保持する。
FIG. 2 shows a procedure for generating a timing constraint matrix, the contents of which are as follows. (s11) The netlist of the circuit is read and held in a work area (not shown) as circuit structure information. (s12) The timing constraints (clock information used, multi-cycle designation, etc.) given by the user are read and held in the work area. (s13) Path trace the netlist based on the circuit structure information, and hold the result in the work area. In this path trace, circuit traces starting from the clock pin or the external input pin of the FF and ending at the data input pin or the external output pin of the FF are used to determine each starting FF /
Check the connection relation of the end point FF. (s14) The time constraint of each path obtained by this path trace is generated based on the clock information for driving the start point FF and the end point FF, and the result is stored in the work area. The time constraint is obtained from the difference between the clock edges of the clock ck1 on the start point side and the clock ck2 on the end point side when the specification of a multi-cycle or the like is taken into consideration. (s15) Generate a timing constraint matrix with the start point FF / end point FF of each path as a row / column and a time constraint as an effective element,
It is stored in a memory (not shown).

【0045】図3は、タイミング制約行列の縮小処理を
示している。この縮小化や図4の分割処理を行なうの
は、CCS候補を求めるといった問題の解の最適性を保
証しながらより現実的な時間で当該問題を解くためであ
る。
FIG. 3 shows a process of reducing the timing constraint matrix. The reduction and the division processing in FIG. 4 are performed in order to solve the problem in a more realistic time while guaranteeing optimality of the solution of the problem such as finding a CCS candidate.

【0046】ここでは、図1(b) のタイミング制約行列
に対して、 (1) 行2に支配される行3を削除した上で当該行間の距
離である「dist(2,3) =0」を保持し〔図3(b) 参
照〕、(2) 列7に支配される列8、および列10に支配
される列11,12をそれぞれ削除した上で当該各列間
の距離「dist(7,8) =0」,「dist(10,11) =0」およ
び「dist(10,12) =−10」を保持し〔図3(c) 参
照〕、(3) 互いに支配関係にたつ行4,行5の任意の一
方、例えば行4を削除した上で当該行間の距離である
「dist(5,4) =−10」を保持することにより、最終的
に図3(d) の縮小行列を求めている。
Here, with respect to the timing constraint matrix shown in FIG. 1B, (1) after deleting row 3 dominated by row 2, the distance between the rows, "dist (2,3) = 0" (See FIG. 3 (b)). (2) The column 8 dominated by the column 7 and the columns 11 and 12 dominated by the column 10 are deleted, and the distance “dist (7,8) = 0, dist (10,11) = 0 and dist (10,12) =-10 (see Fig. 3 (c)), and (3) By deleting any one of the rows 4 and 5, for example, row 4, and retaining the distance “dist (5,4) = − 10” between the rows, finally, FIG. Find the reduced matrix of

【0047】図4は、図3の縮小行列の分割処理を示し
ている。ここでは(a) の(4×4)の縮小行列〔=図3
(d) 〕を(b) の2つの部分行列M1,M2に分割する。
FIG. 4 shows a process of dividing the reduced matrix of FIG. Here, (a) a (4 × 4) reduced matrix [= FIG.
(d)] is divided into two sub-matrices M1 and M2 of (b).

【0048】部分行列M2は(1×1)行列であり、そ
れ自体、行5と列10からなるコンパティブルプライム
のCCS単位を形成している。
The sub-matrix M2 is a (1 × 1) matrix, and itself forms a compatible prime CCS unit consisting of row 5 and column 10.

【0049】部分行列M1については、(1×1)行列
ではないので、図5のCCS候補の生成処理へと移行す
る。
Since the sub-matrix M1 is not a (1 × 1) matrix, the process shifts to a CCS candidate generation process in FIG.

【0050】図5は、CCS候補の生成処理手順を示し
ており、その内容は次のようになっている。 (s21) 図4の部分行列M1の新たな基準行sを選択す
る。どの行を基準行として用いるかは任意であり、例え
ば有効要素の個数が最も多い行を用いる。ここでは行1
を選択する。なお、選択対象となるのは、後述の初期C
CS候補として設定済の要素を除いた部分である。設定
済要素の位置情報はワーク領域(図示省略)などに保持
されている。 (s22) 基準行s、例えば行1の「×」以外の要素からな
る列集合(レクトアングル)を取り出して初期CCS候
補とする。この初期CCS候補はコンパティブルレクト
アングルでもある。 (s23) この初期CCS候補に対し、基準行sの時刻t
(s)を例えば「0」として当該行の各有効要素(列
j)の時刻を「t(j)=t(s)+V(s,j)」の
計算式により求める。なお、V(s,j)は行s, 列j
の要素の値である。 (s24) 初期CCS候補への追加行として未選択の行が部
分行列M1に残っているかどうかを判断して、「 YES 」
の場合は次のステップに進み、「NO」 の場合はステップ
(s30) に進む。 (s25) 新たな追加行を選択する。例えば、部分行列M1
の行2を選択する。なお、上記基準行sに要素「×」が
含まれていた場合、選択行の、当該要素と同じ列の部分
は除外する。選択部分を示す情報はワーク領域などに保
持される。 (s26) この選択行について基準行sと矛盾しない時刻を
設定できるかどうか、すなわち選択行および基準行sに
対して有効な各列の要素の差が一定かどうか(選択行お
よび基準行sのdistanceを定義できるかどうか)を判断
して、「 YES 」 の場合は次のステップに進み、「NO」 の
場合はステップ(s24) に戻る。部分行列M1の場合、行
1と行2に対して有効な各列(列6,列7)の要素の差
が「5」,「0」と異なるので、これらの行のdistance
を定義することはできない。 (s27) この選択行を初期CCS候補に順次追加する。 (s28) ステップ(s26) で定義したdistanceを用いて追加
行の時刻t(a)を設定する。例えば基準行sの時刻に
このdistanceを加える。 (s29) この追加行の各有効要素(各列)の中で時刻未設
定のものについて、その時刻をステップ(s23) と同様の
計算式で求め、ステップ(s24) に戻る。 (s30) ステップ(s21) の基準行として未選択の有効要素
が部分行列M1に残っているかどうかを判断して、「 YE
S 」 の場合はステップ(s21) に戻り、「NO」 の場合は次
のステップに進む。この要素にはステップ(s25) で除外
された部分も含まれる。この未選択部分を示す情報はワ
ーク領域などに保持されている。 (s31) 選択行を追加した後の複数の初期CCS候補(=
コンパティブルレクトアングル)の包含関係をそれぞれ
の行番号, 列番号に基づいて調べることにより、上述の
コンパティブルプライムであるCCS候補[例えば図6
(a) のA,B,C,D]を求める。
FIG. 5 shows a procedure for generating a CCS candidate, the contents of which are as follows. (s21) A new reference row s of the sub-matrix M1 in FIG. 4 is selected. Which row is used as the reference row is arbitrary. For example, a row having the largest number of effective elements is used. Here row 1
Select The selection target is an initial C described later.
This is the part excluding the elements already set as CS candidates. The position information of the set element is held in a work area (not shown) or the like. (s22) A column set (rectangle) including elements other than “x” of the reference row s, for example, row 1, is extracted and set as an initial CCS candidate. This initial CCS candidate is also a compatible rectangle. (s23) For this initial CCS candidate, the time t of the reference row s
(S) is set to, for example, “0”, and the time of each effective element (column j) in the row is obtained by a calculation formula of “t (j) = t (s) + V (s, j)”. Note that V (s, j) is the value of row s, column j
Is the value of the element. (s24) It is determined whether or not an unselected row remains as an additional row to the initial CCS candidate in the sub-matrix M1, and "YES"
If yes, go to next step, if no, go to step
Proceed to (s30). (s25) Select a new additional line. For example, the submatrix M1
Select row 2 When the element “x” is included in the reference row s, the part of the selected row in the same column as the element is excluded. Information indicating the selected portion is held in a work area or the like. (s26) Whether it is possible to set a time consistent with the reference row s for this selected row, that is, whether or not the difference between the elements of each column valid for the selected row and the reference row s is constant (the selected row and the reference row s judge whether the distance can be defined). If “YES”, proceed to the next step. If “NO”, return to step (s24). In the case of the sub-matrix M1, since the difference between the elements of each column (column 6, column 7) effective for row 1 and row 2 is different from “5” and “0”, the distances of these rows are different.
Cannot be defined. (s27) The selected rows are sequentially added to the initial CCS candidates. (s28) The time t (a) of the additional row is set using the distance defined in the step (s26). For example, this distance is added to the time of the reference line s. (s29) Among the effective elements (each column) of this additional row, for which the time is not set, the time is obtained by the same calculation formula as in step (s23), and the process returns to step (s24). (s30) It is determined whether an unselected effective element remains as a reference row in step (s21) in the sub-matrix M1.
In the case of "S", the process returns to step (s21), and in the case of "NO", the process proceeds to the next step. This element includes the part excluded in step (s25). Information indicating the unselected portion is held in a work area or the like. (s31) A plurality of initial CCS candidates (=
By examining the inclusion relationship of the compatible rectangles based on the respective row numbers and column numbers, the CCS candidates that are the compatible primes described above [for example, FIG.
(A, B, C, D) of (a).

【0051】図5では部分行列M1の行を対象にした処
理によりCCS候補を生成しているが、当該部分行列M
1の列を対象としても図6と同様の手順(行と列の記載
を入れ替えた形の手順)により新たなCCS候補が生成
される。
In FIG. 5, CCS candidates are generated by processing on the rows of the sub-matrix M1.
A new CCS candidate is generated for the column 1 by the same procedure as that of FIG. 6 (the procedure in which the description of the rows and columns is replaced).

【0052】図6は、CCS候補に対する最小被覆問題
の解法プロセスを示している。このときの実行主体はC
CS特定用の解法プログラムである。
FIG. 6 shows the process of solving the minimum coverage problem for CCS candidates. The execution subject at this time is C
This is a solution program for CS identification.

【0053】図6(a) のA,B,CおよびDは図5の生
成処理など(部分行列M1の行および列を対象とした処
理)により求めたCCS候補(=コンパティブルプライ
ム)である。また、a,b,c,dおよびeは部分行列
M1の有効要素である。当該有効要素のそれぞれは1つ
または複数のCCS候補に含まれている。
A, B, C and D in FIG. 6 (a) are CCS candidates (= compatible prime) obtained by the generation processing of FIG. 5 or the like (processing on the rows and columns of the partial matrix M1). is there. A, b, c, d and e are effective elements of the submatrix M1. Each of the valid elements is included in one or more CCS candidates.

【0054】ここで、部分行列M1の有効要素a〜eの
行および列は、 ・a=(1,6) ・b=(2,6) ・c=(1,7) ・d=(2,7) ・e=(0,9) である。
Here, the rows and columns of the effective elements a to e of the sub-matrix M1 are as follows: a = (1,6) b = (2,6) c = (1,7) d = (2 , 7) e = (0, 9).

【0055】CCS候補(コンパティブルプライム)A
〜Dのいわばカバー範囲は、 ・A=「行:1,2」「列:6」 ・B=「行:0,1,2」「列:7,9」 ・C=「行:1」「列:6,7,9」 ・D=「行:2」「列:6,7,9」 である。
CCS candidate (compatible prime) A
The so-called cover range of D is as follows: A = “rows: 1, 2” “columns: 6” B = “rows: 0, 1, 2” “columns: 7, 9” C = “rows: 1” “Column: 6, 7, 9” D = “row: 2” and “column: 6, 7, 9”.

【0056】ここでの最小被覆問題の命題は、部分行列
M1の各有効要素a〜eをすべてカバーするCCS候補
の組み合わせの中でその組合わせ数が最も少ないものを
求めることである。
The proposition of the minimum coverage problem here is to find the combination of the CCS candidates which covers all the effective elements a to e of the sub-matrix M1 with the smallest number of combinations.

【0057】図6(b) は、図6(a) の有効要素a〜eを
行に配し、CCS候補A〜Dを列に配した形の被覆表を
示している。
FIG. 6B shows a covering table in which the effective elements a to e of FIG. 6A are arranged in rows and the CCS candidates A to D are arranged in columns.

【0058】この被覆表の作成ルールは、列(CCS候
補)jが行(有効要素)iを被覆する、すなわち有効要
素がCCS候補に含まれる関係にたつときに「(i,
j)=1」とすることである。
The rules for creating this cover table are such that when a column (CCS candidate) j covers a row (valid element) i, that is, when a valid element is in a relationship included in a CCS candidate, “(i,
j) = 1 ".

【0059】例えば、有効要素a(1,6)はCCS候
補A〔「行:1,2」「列:6」〕とCCS候補C
〔「行:1」「列:6,7,9」〕とに含まれているの
で、行aについては列A,Cの要素のみが「1」に設定
される。
For example, the valid element a (1, 6) is a CCS candidate A [“row: 1, 2”, “column: 6”] and a CCS candidate C
[“Row: 1”, “columns: 6, 7, 9”], only the elements of columns A and C are set to “1” for row a.

【0060】同様にして、 ・行bについては列A,Dの要素のみが「1」に設定さ
れ、 ・行cについては列B,Cの要素のみが「1」に設定さ
れ、 ・行dについては列B,Dの要素のみが「1」に設定さ
れ、 ・行eについては列Bの要素のみが「1」に設定され
る。
Similarly, for row b, only the elements in columns A and D are set to “1”; for row c, only the elements in columns B and C are set to “1”; For, only the elements in columns B and D are set to “1”, and for row e, only the elements in column B are set to “1”.

【0061】この被覆表を用いると、タイミング制約行
列の有効要素をカバーする最小のCCS集合を求める問
題は、すべての行がいずれかの列に被覆されるような最
小の列集合を求める問題に帰着する。
Using this coverage table, the problem of finding the smallest CCS set covering the effective elements of the timing constraint matrix is the problem of finding the smallest column set in which all rows are covered by any column. Come back.

【0062】図6(c) 〜図6(e) は、被覆表(b) に基づ
いて最小数のCCS集合を求める過程を示している。
FIGS. 6C to 6E show the process of obtaining the minimum number of CCS sets based on the coverage table (b).

【0063】先ず、必ず解に含めないといけない列(必
須列)を抽出する。この必須列とは、「1」の要素が一
つしかない行における当該要素を含む列のことである。
被覆表(b) では行eに対応の列Bが該当する。
First, a column (essential column) that must be included in the solution is extracted. The required column is a column including the element in a row having only one element of “1”.
In the cover table (b), the column B corresponding to the row e corresponds.

【0064】これは、タイミング制約行列の有効要素e
を被覆するためには列B(CCS候補)を解に含めなけ
ればならないことを意味している。
This is because the effective element e of the timing constraint matrix is
Means that column B (CCS candidate) must be included in the solution to cover.

【0065】列Bを解に含めると、当該列に要素「1」
を持つ他の行(要素)c,dも自動的にこれに含まれる
ので、二つの当該行はともに以後の被覆問題を考える上
での対象から取り除いてもよい。
When column B is included in the solution, the element "1"
Since other rows (elements) c and d having are automatically included in these rows, both of the two rows may be removed from objects in considering the subsequent covering problem.

【0066】図6(d) は、被覆表(b) からこの列Bおよ
び行c,d,eのそれぞれを削除した状態を示してい
る。
FIG. 6D shows a state in which each of the column B and the rows c, d, and e has been deleted from the covering table (b).

【0067】解法プログラムは、被覆表(d) の各列間の
関係を調べることにより列Aが列C,Dの両者を支配し
ていることを確認して、当該列のC,Dを削除する。
The solution program checks the relationship between the columns of the covering table (d), confirms that column A controls both columns C and D, and deletes C and D in that column. I do.

【0068】列Aが列C,Dを支配するとは、列Aを選
べば列C,Dの要素「1」の行がすべて含まれることで
ある。すなわち、列Aを選択することにより残りの有効
要素a,bがともに被覆される。そのため、他の列C,
Dを選ぶときよりも被覆問題の解が少なくなる。
The column A dominates the columns C and D means that if the column A is selected, all the rows of the element "1" of the columns C and D are included. That is, by selecting the column A, both the remaining effective elements a and b are covered. Therefore, the other columns C,
There are fewer solutions to the coverage problem than when D is chosen.

【0069】被覆表(d) から列C,Dを削除すると、列
Aだけが残る。解法プログラムは、この削除後の被覆表
を調べて行a,bの要素「1」は列Aにのみ存在する、
すなわち列Aは必須列であることを判断し、これを解に
含めるとともに、当該列Aおよびこれにカバーされる行
a,bを削除する。
When columns C and D are deleted from the cover table (d), only column A remains. The solution program examines the deleted coverage table and finds that the element “1” in rows a and b exists only in column A.
That is, it is determined that the column A is a required column, and this is included in the solution, and the column A and the rows a and b covered by the column A are deleted.

【0070】これにより被覆表(b) のすべての行(=部
分行列M1の有効要素)が削除されたので、CCS単位
の特定処理を終了する。
As a result, all the rows (= valid elements of the partial matrix M1) of the coverage table (b) have been deleted, and the specific processing in CCS units ends.

【0071】図6(e) は、特定されたCCS単位A,B
と、当該CCS単位のそれぞれに被覆される要素とを示
している。
FIG. 6E shows the specified CCS units A and B.
And elements to be covered by each of the CCS units.

【0072】このような最小被覆問題の解法自体は例え
ば「論理設計スイッチング回路理論(第2版),笹尾勤
著,近代科学社1998年5月1日発行,p66〜p7
3」で示されている。
The solution itself of such a minimum covering problem is described in, for example, “Logic Design Switching Circuit Theory (2nd Edition)”, Tsutomu Sasao, published by Kyushu Kagakusha on May 1, 1998, pp. 66 to p7.
3 ".

【0073】図7は、最小被覆問題の解決処理手順を示
しており、その内容は次のようになっている。
FIG. 7 shows a procedure for solving the minimum covering problem, the contents of which are as follows.

【0074】まず、この解決処理を概観すると次の内容
になる。 (s41) 被覆表の簡約化を行なって、次のステップに進
む。 (s42) この簡約化によって被覆表の行/列が図6のよう
にすべて削除できたかどうか、すなわち被覆表に行/列
が残っているかどうかを判断して、「 YES 」 の場合は次
のステップに進み、「NO」の場合は一連の処理を終了す
る。 (s43) 行/列が残っている被覆表に対してその解を再帰
的に求める。なお、この再帰的処理に際しては、行/列
間の無駄な組み合わせをなるべく検索しないため、枝が
りの処理も実行する。
First, an overview of the solution processing is as follows. (s41) Simplify the coverage table and proceed to the next step. (s42) It is determined whether or not all the rows / columns of the covering table have been deleted as shown in FIG. 6 by this simplification, that is, whether or not the covering table has any remaining rows / columns. The process proceeds to a step, and in the case of “NO”, a series of processing ends. (s43) The solution is recursively obtained for the covering table having the remaining rows / columns. In this recursive process, a branching process is also executed in order to avoid searching for useless combinations between rows and columns as much as possible.

【0075】被覆表の簡約化処理は次の内容になる。 (s41-1) 必須列(CCS)が存在するかどうかを判断し
て、「 YES 」 の場合は次のステップに進み、「NO」 の場
合はステップ(s41-3) に進む。 (s41-2) 必須列を解に含め、被覆表から、この必須列
と、当該列の「1」の要素を持つ各行を削除して、次の
ステップに進む。 (s41-3) 被覆表の列間で支配関係が成立しているかどう
かを判断して、「 YES 」の場合は次のステップに進み、
「NO」 の場合はステップ(s41-5) に進む。 (s41-4) 被覆表から被支配列を削除して、次のステップ
に進む。 (s41-5) 被覆表の行間で支配関係が成立しているかどう
かを判断して、「 YES 」の場合は次のステップに進み、
「NO」 の場合はステップ(s41-7) に進む。 (s41-6) 被覆表から支配行を削除して、次のステップに
進む。 (s41-7) 一連の処理により被覆表の残存行/列が変化し
たかどうかを判断して、「 YES 」 の場合はステップ(s41
-1) に戻り、「NO」 の場合はステップ(s42) に進む。
The process of simplifying the coating table is as follows. (s41-1) It is determined whether or not the required column (CCS) exists. If “YES”, proceed to the next step, and if “NO”, proceed to step (s41-3). (s41-2) The required column is included in the solution, the required column and each row having the element of “1” in the column are deleted from the covering table, and the process proceeds to the next step. (s41-3) It is determined whether or not a dominant relationship is established between columns of the covering table, and if “YES”, proceed to the next step.
If “NO”, proceed to step (s41-5). (s41-4) The supported array is deleted from the covering table, and the process proceeds to the next step. (s41-5) It is determined whether or not the dominant relationship is established between the rows of the covering table, and if “YES”, proceed to the next step,
If “NO”, proceed to step (s41-7). (s41-6) Delete the dominant row from the coverage table and proceed to the next step. (s41-7) It is determined whether or not the remaining rows / columns of the cover table have changed by a series of processing, and if “YES”, the step (s41-7)
Returning to -1), if "NO", proceed to step (s42).

【0076】被覆表の再帰的処理は次の内容になる。 (s43-1) 被覆表の残存行/列から列を一つ選んで、次の
ステップに進む。 (s43-2) 選んだ列(CCS候補)を解に含めるとして、
被覆表から、この列と、当該列にカバーされる行(当該
列の「1」の要素を持つ各行)を削除し、その結果の被
覆表に対して当該フロー(図7の開始から終了まで)を
再帰的に実行し、その解を求める。 (s43-3) 選んだ列(CCS候補)を解に含めないとし
て、被覆表から当該列を削除し、その結果の被覆表に対
して当該フロー(図7の開始から終了まで)を再帰的に
実行し、その解を求める。 (s43-4) ステップ(s43-2) ,(s43-3) で求めた解を比較
して、それぞれに含まれる列数が小さい方を解として取
り上げ、必須列から求めた解にこれを加えて全体の解と
する。
The recursive processing of the cover table is as follows. (s43-1) One column is selected from the remaining rows / columns of the cover table, and the process proceeds to the next step. (s43-2) Assuming that the selected column (CCS candidate) is included in the solution,
This column and the rows covered by the column (each row having an element of “1” in the column) are deleted from the coverage table, and the flow (from the start to the end in FIG. 7) is applied to the resulting coverage table. ) Is performed recursively to find the solution. (s43-3) The selected column (CCS candidate) is not included in the solution, the column is deleted from the coverage table, and the flow (from the start to the end of FIG. 7) is recursively applied to the resulting coverage table. And find the solution. (s43-4) Compare the solutions obtained in steps (s43-2) and (s43-3), take the smaller number of columns included in each as the solution, and add this to the solution obtained from the required columns. The whole solution.

【0077】図8は、CCSに基づく各FFの到達時刻
(ATIME)および要求時刻(RTIME)を示して
いる。
FIG. 8 shows the arrival time (ATIME) and request time (RTIME) of each FF based on the CCS.

【0078】(a) はCCS単位A, M2に対応のCCS
1,(b) はCCS単位Bに対応のCCS2を示し、また
21はCCS単位Aの拡大部分行列,22はCCS単位
M2の拡大部分行列,23はCCS単位Bの拡大部分行
列をそれぞれ示している。CCSの組合せのルールは、
最小被覆問題の解A, Bの一方と、M2とを組み合わせ
ることである。
(A) is a CCS corresponding to CCS units A and M2.
1, (b) indicates CCS2 corresponding to CCS unit B, 21 indicates an expanded sub-matrix of CCS unit A, 22 indicates an expanded sub-matrix of CCS unit M2, and 23 indicates an expanded sub-matrix of CCS unit B. I have. The rules for combining CCS are:
One of the solutions A and B of the minimum covering problem is combined with M2.

【0079】ここで、 ・拡大部分行列21は、CCS単位Aと、行の距離デ−
タ(図3参照)「dist(2,3) =0」とを用いて生成さ
れ、 ・拡大部分行列22は、CCS単位M2と、行の距離デ
−タ(図3参照)「dist(5,4) =−10」および列の距
離デ−タ「dist(10,11) =0,dist(10,12) =−10」
とを用いて生成され、 ・拡大部分行列23は、一次CCS(B)と、行の距離
デ−タ(図3参照)「dist(2,3) =0」および列の距離
デ−タ「dist(7,8) =0」とを用いて生成される。な
お、図1(b) のタイミング制約行列の各有効要素の位置
デ−タはワーク領域などに保持されている。
Here, the expanded sub-matrix 21 is composed of the CCS unit A and the distance data of the row.
The extended sub-matrix 22 is generated using the CCS unit M2 and the row distance data (see FIG. 3) “dist (5, 3) = 0” (see FIG. 3). , 4) =-10 "and the distance data of the column" dist (10,11) = 0, dist (10,12) =-10 "
The expanded sub-matrix 23 is composed of a primary CCS (B), row distance data (see FIG. 3) “dist (2,3) = 0” and column distance data “ dist (7,8) = 0 ". The position data of each effective element of the timing constraint matrix shown in FIG. 1B is held in a work area or the like.

【0080】CCS1の拡大部分行列21の場合、例え
ば行1の到達時刻を「0」に初期設定すると、 ・まず、列6の要求時刻が、初期設定時刻「0」および
有効要素(1,6)の値「15」を用いて「15(=0
+15)」と求まり、以下、 ・行2の到達時刻が、列6の要求時刻「15」および有
効要素(2,6)の値「5」を用いて「10(=15−
5)」と求まり、 ・行3の到達時刻が、行2の到達時刻「10」および
「dist(2,3) =0」を用いて「10(=10−0)」と
求まる。
In the case of the expanded sub-matrix 21 of CCS1, for example, when the arrival time of row 1 is initially set to “0”, first, the request time of column 6 is changed to the initial setting time “0” and the effective element (1, 6 ) Using the value “15” of “
+15) ”, and the arrival time of row 2 is calculated as“ 10 (= 15−) using the request time “15” in column 6 and the value “5” of the effective element (2, 6).
5) ”, and the arrival time of row 3 is obtained as“ 10 (= 10−0) ”using the arrival time“ 10 ”of row 2 and“ dist (2,3) = 0 ”.

【0081】CCS1の拡大部分行列22の場合、例え
ば行5の到達時刻を「0」に初期設定すると、 ・まず、列10の要求時刻が、初期設定時刻「0」およ
び有効要素(5,10)の値「15」を用いて「15
(=0+15)」と求まり、以下、 ・行4の到達時刻が、行5の到達時刻「0」および「di
st(5,4) =−10」を用いて「10〔=0−(−1
0)〕」と求まり、 ・列11の要求時刻が、列10の要求時刻「15」およ
び「dist(10,11) =0」を用いて「15(=15+
0)」と求まり、 ・列12の要求時刻が、列10の要求時刻「15」およ
び「dist(10,12) =−10」を用いて「5〔=15+
(−10)〕」と求まる。
In the case of the expanded sub-matrix 22 of the CCS1, for example, when the arrival time of the row 5 is initialized to “0”, first, the request time of the column 10 is changed to the initialization time “0” and the effective element (5, 10 ) Using the value “15”
(= 0 + 15) ". The arrival time of row 4 is equal to the arrival time“ 0 ”and“ di ”of row 5.
Using st (5,4) =-10, "10 [= 0-(-1
0)], and the request time in column 11 is calculated using the request time “15” in column 10 and “dist (10,11) = 0” as “15 (= 15 +
0) ”, and the request time in column 12 is calculated as“ 5 [= 15 + ”using request time“ 15 ”in column 10 and“ dist (10,12) = − 10 ”.
(−10)] ”.

【0082】また、CCS2の拡大部分行列23の場
合、例えば行1の到達時刻を「0」に初期設定すると、 ・まず、列7の要求時刻が、初期設定時刻「0」および
有効要素(1,7)の値「10」を用いて「10(=0
+10)」と求まり、以下、 ・行2の到達時刻が、列7の要求時刻および有効要素
(2,7)の値「10」を用いて「0(=10−1
0)」と求まり、 ・行3の到達時刻が、行2の到達時刻「0」および「di
st(2,3) =0」を用いて「0(=0−0)」と求まり、 ・列8の要求時刻が、列7の要求時刻「10」および
「dist(7,8) =0」を用いて「10(=10+0)」と
求まる。
In the case of the expanded sub-matrix 23 of CCS2, for example, when the arrival time of row 1 is initially set to “0”, first, the request time of column 7 is changed to the initial setting time “0” and the effective element (1 , 7) using the value “10”, “10 (= 0)
+10) ”, and the arrival time of row 2 is set to“ 0 (= 10−1) using the request time of column 7 and the value “10” of the effective element (2, 7).
0), and the arrival time of row 3 is equal to the arrival time of row 2 “0” and “di”
“0 (= 0−0)” is obtained using st (2,3) = 0, and the request time in column 8 is changed to the request time “10” in column 7 and “dist (7,8) = 0” To obtain “10 (= 10 + 0)”.

【0083】なお、行0の到達時刻および列9の要求時
刻は、それぞれの有効要素が一つだけなので行1などと
は無関係に求めればよい。例えば、行0の到達時刻を
「0」に初期設定すれば列9の要求時刻は「2(=0+
2)」となる。
Note that the arrival time of row 0 and the request time of column 9 need only be determined independently of row 1 and so on, since each has only one valid element. For example, if the arrival time of row 0 is initialized to “0”, the request time of column 9 is “2 (= 0 +
2) ".

【0084】以上の到達時刻および要求時刻を求める際
のルールは、 ・縮小行列の行/列の時刻は、その任意の行または列の
設定済時刻と対応有効要素の値を用いて、要求時刻
(列)に関しては「行の設定済時刻+対応有効要素の
値」の演算により、また到達時刻(行)に関しては「列
の設定済時刻−対応有効要素の値」の演算によりそれぞ
れ設定し、 ・削除された行/列の時刻は、それを支配する行/列の
時刻と両者(支配行/列と被支配行/列)の距離distを
用いて、行に関しては「時刻−dist」の演算により、ま
た列に関しては「時刻+dist」の演算によりそれぞれ設
定する、ことである。
The rules for obtaining the above arrival time and request time are as follows: The row / column time of the reduced matrix is calculated by using the set time of the arbitrary row or column and the value of the corresponding effective element. (Column) is set by the operation of “set time of row + value of corresponding effective element”, and arrival time (row) is set by operation of “set time of column−value of corresponding effective element”. The time of the deleted row / column is obtained by using the time of the dominating row / column and the distance dist between the two (the dominant row / column and the dominated row / column). This is to be set by calculation, and for columns, by calculation of “time + dist”.

【0085】このようにして、図1の論理回路を構成す
るすべてのFF(FF0〜12)の到達時刻および要求
時刻を、CCSごとに、FF間の各パスの時間制約を満
足する形で一意に設定することができる。
As described above, the arrival time and the request time of all the FFs (FF0 to 12) constituting the logic circuit of FIG. 1 are uniquely determined for each CCS in such a manner as to satisfy the time constraint of each path between the FFs. Can be set to

【0086】図9は、CCS生成システムの構成例を示
す説明図であり、3はCCS生成システム,31はパス
解析・コマンド解析部,32はタイミング制約行列生成
部,33は縮小処理部,34は分割処理部,35はCC
S候補生成部,36は最小被覆問題処理部,37は到達
時刻・要求時刻生成部,41は対象回路のネットリス
ト,42はユーザから与えられたFFタイミング情報
(各始点FF/終点FFの使用クロックやマルチサイク
ル指定など),43はCCSごとに一意なタイミング制
約をそれぞれ示している。
FIG. 9 is an explanatory diagram showing an example of the configuration of a CCS generation system. 3 is a CCS generation system, 31 is a path analysis / command analysis unit, 32 is a timing constraint matrix generation unit, 33 is a reduction processing unit, 34 Is a division processing unit, 35 is CC
S candidate generation unit, 36 is the minimum covering problem processing unit, 37 is the arrival time / request time generation unit, 41 is the netlist of the target circuit, 42 is FF timing information given by the user (use of each start FF / end FF) 43 designates a unique timing constraint for each CCS.

【0087】パス解析・コマンド解析部31は、図2の
処理により、ネットリスト41およびFFタイミング情
報42を用いて各始点FF/終点FFの接続関係を調べ
るとともに、この接続関係に基づく各パスの時間制約を
生成する。
The path analysis / command analysis unit 31 checks the connection relationship between each start point FF / end point FF using the netlist 41 and the FF timing information 42 by the processing of FIG. Generate a time constraint.

【0088】タイミング制約行列生成部32は、パス解
析・コマンド解析部31の処理結果を用いて図1のタイ
ミング制約行列を作成する。
The timing constraint matrix generator 32 creates the timing constraint matrix shown in FIG. 1 using the processing result of the path analyzer / command analyzer 31.

【0089】縮小処理部33は、図3の処理により、タ
イミング制約行列の所定の行および列を削除する。
The reduction processing section 33 deletes predetermined rows and columns of the timing constraint matrix by the processing of FIG.

【0090】分割処理部34は、縮小処理部33が生成
した縮小行列をその有効要素の位置情報に基づいて部分
行列M1,M2に分割する(図4参照)。
The dividing section 34 divides the reduced matrix generated by the reducing section 33 into sub-matrices M1 and M2 based on the position information of the effective elements (see FIG. 4).

【0091】CCS候補生成部35は、図5の処理によ
り、分割後の部分行列M1のCCS候補(コンパティブ
ルプライム)A,B,C,Dを作成する。
The CCS candidate generator 35 creates CCS candidates (compatible primes) A, B, C, and D of the divided sub-matrix M1 by the processing of FIG.

【0092】最小被覆問題処理部36は、図6,図7の
処理により、このCCS候補の中から、カバー対象のす
べての有効要素a,b,c,d,eを含むといった条件
の下での、最小数のCCS単位A,Bを特定する。
The minimum covering problem processing section 36 performs the processing shown in FIGS. 6 and 7 under the condition that all the valid elements a, b, c, d, and e to be covered are included from the CCS candidates. , The minimum number of CCS units A and B are specified.

【0093】到達時刻・要求時刻生成部37は、CCS
単位A, M2に基づくCCS1とCCS単位Bに基づく
CCS2とを作成し、それぞれのCCSごとに一意のタ
イミング制約43を生成している。
The arrival time / requested time generation unit 37 generates the CCS
A CCS1 based on the units A and M2 and a CCS2 based on the CCS unit B are created, and a unique timing constraint 43 is generated for each CCS.

【0094】図10は、タイミング制約行列の縮小と分
割の一例を示す説明図である。ここでは、各データに対
するタイミング制約行列の行数, 列数, 有効要素数が縮
小処理および分割処理によってどれだけ小さくなったか
を示している。
FIG. 10 is an explanatory diagram showing an example of reduction and division of the timing constraint matrix. Here, it is shown how much the number of rows, the number of columns, and the number of effective elements of the timing constraint matrix for each data are reduced by the reduction processing and the division processing.

【0095】原行列, 縮小および分割の各項目は、上段
が行数/列数であり、下段が有効要素数である。
In each item of the original matrix, reduction and division, the upper row is the number of rows / columns, and the lower row is the number of effective elements.

【0096】また、縮小項目の値は原行列に対して縮小
処理を繰り返し適用した結果を示し、分割項目の値は縮
小結果に対して分割処理を行なったときの最大の部分行
列を示している。
The value of the reduction item indicates the result of repeatedly applying the reduction processing to the original matrix, and the value of the division item indicates the maximum submatrix when the division processing is performed on the reduction result. .

【0097】例えばデータ4の場合は非常に小さな部分
に分割されている、すなわち(11171×2727
9)のタイミング制約行列が最大でも(23×22)の
部分行列に分割されていることがわかる。このときの部
分行列の総数は「5259」である。
For example, data 4 is divided into very small parts, that is, (11171 × 2727)
It can be seen that the timing constraint matrix of 9) is divided at most into (23 × 22) sub-matrices. The total number of sub-matrices at this time is “5259”.

【0098】図11は、コンピュータ読み取り可能な記
録媒体からプログラムを読み取って実行するコンピュー
タシステムの概要を示す説明図であり、5はコンピュー
タシステム,51はCPUやディスクドライブ装置など
を内蔵した本体部,52は本体部51からの指示により
画像などを表示するディスプレイ,53は表示画面,5
4はコンピュ−タシステム5に種々の情報を入力するた
めのキーボード,55は表示画面53の任意の位置を指
定するマウス,56は外部のデータベース(DASDな
どの回線先メモリ),57は外部のデータベースにアク
セスするためのモデム,58はCD−ROMやフレキシ
ブルディスクなどの可搬型記録媒体をそれぞれ示してい
る。
FIG. 11 is an explanatory diagram showing an outline of a computer system which reads a program from a computer-readable recording medium and executes the program. 5 is a computer system, 51 is a main unit incorporating a CPU and a disk drive device, etc. 52, a display for displaying images and the like in accordance with instructions from the main body 51; 53, a display screen;
Reference numeral 4 denotes a keyboard for inputting various information to the computer system 5; 55, a mouse for specifying an arbitrary position on the display screen 53; 56, an external database (line destination memory such as DASD); 57, an external database And 58, a portable recording medium such as a CD-ROM or a flexible disk.

【0099】プログラムを格納する記録媒体としては、 ・プログラム提供者側のデータベース56(回線先メモ
リ) ・可搬型記録媒体58 ・本体部51側のRAMやハードディスク などのいずれでもよく、当該プログラムは本体部51に
ローディングされてその主メモリ上で実行される。
The recording medium for storing the program may be any of a database 56 (line destination memory) on the program provider side, a portable recording medium 58, and a RAM or hard disk on the main unit 51 side. It is loaded into the unit 51 and executed on its main memory.

【0100】[0100]

【発明の効果】本発明は、このように、論理回路の始点
側/終点側フリップフロップ間の各パスに対する制約条
件からなるタイミング制約行列を作成して、この行列か
ら、この制約条件に基づく始点側/終点側フリップフロ
ップの到達時刻および要求時刻をすべて同時に満足でき
る形の制約集合を求めているので、その個数の最適性化
を可能にし、各パスの遅延検査の効率化を図ることがで
きる。
As described above, according to the present invention, a timing constraint matrix composed of constraints for each path between the flip-flops on the starting point side and the ending point side of the logic circuit is created, and the starting point based on the constraints is created from this matrix. Since a constraint set in a form that satisfies both the arrival time and the required time of the side / end point flip-flops at the same time is required, the number of the constraint sets can be optimized, and the delay test of each path can be made more efficient. .

【0101】また、制約集合を求めるに先だって、タイ
ミング制約行列の行および列の支配関係や、タイミング
制約行列の部分同士における始点側/終点側フリップフ
ロップの到達時刻・要求時刻算出の相互依存性に基づく
当該行列の縮小・分割を実行しているので、制約集合作
成の効率化を図ることができる。
Prior to obtaining the constraint set, the relationship between the dominance of the rows and columns of the timing constraint matrix and the interdependence of the calculation of the arrival time / request time of the start point / end point flip-flop between the parts of the timing constraint matrix are described. Since the matrix is reduced / divided based on this, it is possible to increase the efficiency of constraint set creation.

【0102】また、制約集合を求めるに先だって、その
複数の候補を含む部分行列を対象にした最小被覆問題を
解いているので、制約集合個数の最小性を保証し、各パ
スの遅延検査の一層の効率化を図ることができる。
Since the minimum coverage problem for the sub-matrix including the plurality of candidates is solved prior to obtaining the constraint set, the minimumness of the number of constraint sets is guaranteed, and the delay check of each path is further performed. Efficiency can be improved.

【図面の簡単な説明】[Brief description of the drawings]

【図1】本発明の、図12に対応のタイミング制約グラ
フとタイミング制約行列を示す説明図である。
FIG. 1 is an explanatory diagram showing a timing constraint graph and a timing constraint matrix corresponding to FIG. 12 of the present invention.

【図2】本発明の、タイミング制約行列の生成処理手順
を示す説明図である。
FIG. 2 is an explanatory diagram showing a procedure for generating a timing constraint matrix according to the present invention;

【図3】本発明の、タイミング制約行列の縮小処理を示
す説明図である。
FIG. 3 is an explanatory diagram showing a process of reducing a timing constraint matrix according to the present invention.

【図4】本発明の、図3の縮小行列の分割処理を示す説
明図である。
FIG. 4 is an explanatory diagram showing a process of dividing the reduced matrix of FIG. 3 according to the present invention.

【図5】本発明の、CCS候補の生成処理手順を示す説
明図である。
FIG. 5 is an explanatory diagram showing a procedure for generating a CCS candidate according to the present invention.

【図6】本発明の、CCS候補に対する最小被覆問題の
解法プロセスを示す説明図である。
FIG. 6 is an explanatory diagram showing a process of solving a minimum coverage problem for CCS candidates according to the present invention.

【図7】本発明の、最小被覆問題の解決処理手順を示す
説明図である。
FIG. 7 is an explanatory diagram showing a processing procedure for solving the minimum covering problem according to the present invention.

【図8】本発明の、CCSに基づく各FFの到達時刻
(ATIME), 要求時刻(RTIME)を示す説明図
である。
FIG. 8 is an explanatory diagram showing arrival time (ATIME) and request time (RTIME) of each FF based on CCS according to the present invention.

【図9】本発明の、CCS生成システムの構成例を示す
説明図である。
FIG. 9 is an explanatory diagram illustrating a configuration example of a CCS generation system according to the present invention.

【図10】本発明の、タイミング制約行列の縮小と分割
の一例を示す説明図である。
FIG. 10 is an explanatory diagram illustrating an example of reduction and division of a timing constraint matrix according to the present invention.

【図11】本発明の、コンピュータ読み取り可能な記録
媒体からプログラムを読み取って実行するコンピュータ
システムの概要を示す説明図である。
FIG. 11 is an explanatory diagram showing an outline of a computer system for reading and executing a program from a computer-readable recording medium according to the present invention.

【図12】一般的な、対象とする論理回路やクロック定
義などの説明図である。
FIG. 12 is an explanatory diagram of a general target logic circuit, clock definition, and the like.

【符号の説明】[Explanation of symbols]

1:組み合わせ回路 21:CCS単位Aの拡大部分行列 22:CCS単位M2の拡大部分行列 23:CCS単位Bの拡大部分行列 3:CCS生成システム 31:パス解析・コマンド解析部 32:タイミング制約行列生成部 33:縮小処理部 34:分割処理部 35:CCS候補生成部 36:最小被覆問題処理部 37:到達時刻・要求時刻生成部 41:対象回路のネットリスト 42:ユーザから与えられたFFタイミング情報 43:CCSごとに一意なタイミング制約 5:コンピュ−タシステム 51:CPUやディスクドライブ装置などを内蔵した本
体部 52:ディスプレイ 53:表示画面 54:キ−ボ−ド 55:マウス 56:ディスク装置 57:CD−ROMやフレキシブルディスクなどの可搬
型記録媒体 A,B:CCS候補/CCS単位 C,D:CCS候補 a〜e:分割処理後の部分行列の有効要素
1: Combination circuit 21: Expanded partial matrix of CCS unit A 22: Expanded partial matrix of CCS unit M23: Expanded partial matrix of CCS unit B 3: CCS generation system 31: Path analysis / command analysis unit 32: Timing constraint matrix generation Unit 33: reduction processing unit 34: division processing unit 35: CCS candidate generation unit 36: minimum coverage problem processing unit 37: arrival time / request time generation unit 41: target circuit net list 42: FF timing information given by the user 43: Timing constraint unique to each CCS 5: Computer system 51: Main body with built-in CPU, disk drive, etc. 52: Display 53: Display screen 54: Keyboard 55: Mouse 56: Disk device 57: Portable recording media such as CD-ROM and flexible disk A, B: CCS candidate CCS unit C, D: CCS candidates a to e: effective elements of division processing after partial matrix

Claims (6)

【特許請求の範囲】[Claims] 【請求項1】 始点側/終点側フリップフロップを有す
る論理回路のタイミング制約生成方式において、 前記始点側/終点側フリップフロップのそれぞれを行/
列とし、かつ当該フリップフロップ間の各パスに対する
制約条件を有効要素として示すタイミング制約行列を作
成する第1の手段と、 少なくとも一部の前記有効要素からなり、それに対応の
前記制約条件に基づく前記始点側フリップフロップの到
達時刻と前記終点側フリップフロップの要求時刻とをす
べて同時に満足できる形の制約集合を、前記タイミング
制約行列から求める第2の手段と、 前記制約集合に対応の前記到達時刻および前記要求時刻
を算出する第3の手段とを有する、ことを特徴とする論
理回路のタイミング制約生成方式。
1. A timing constraint generation method for a logic circuit having a start point / end point flip-flop, wherein each of the start point / end point flip-flops is a row /
A first means for creating a timing constraint matrix as a column and indicating a constraint condition for each path between the flip-flops as an effective element, the timing constraint matrix comprising at least a part of the effective elements, and based on the corresponding constraint condition. A second means for obtaining, from the timing constraint matrix, a constraint set that can simultaneously satisfy the arrival time of the start-point flip-flop and the request time of the end-point flip-flop; and the arrival time and the arrival time corresponding to the constraint set. And a third means for calculating the request time. 3. A timing constraint generation method for a logic circuit, comprising:
【請求項2】 前記第2の手段は、あらかじめ前記タイ
ミング制約行列の処理対象部分の行および列それぞれの
支配関係に基づいてその被支配行および被支配列を削除
する、ことを特徴とする請求項1記載の論理回路のタイ
ミング制約生成方式。
2. The method according to claim 1, wherein the second means deletes a controlled row and a supported array of the timing constraint matrix based on a dominant relation of each of a row and a column of a processing target portion of the timing constraint matrix in advance. Item 4. A timing constraint generation method for a logic circuit according to item 1.
【請求項3】 前記第2の手段は、あらかじめ前記タイ
ミング制約行列の処理対象部分を、それぞれが互いに独
立して前記到達時刻および前記要求時刻を算出すること
が可能な部分行列に分割する、ことを特徴とする請求項
1または2記載の論理回路のタイミング制約生成方式。
3. The method according to claim 2, wherein the second means divides in advance a processing target portion of the timing constraint matrix into partial matrices each of which can calculate the arrival time and the request time independently of each other. 3. The timing constraint generation method for a logic circuit according to claim 1, wherein:
【請求項4】 前記第2の手段は、あらかじめ複数の制
約集合候補を対象にした最小被覆問題を解く、ことを特
徴とする請求項1乃至3記載の論理回路のタイミング制
約生成方式。
4. The method according to claim 1, wherein said second means solves a minimum coverage problem for a plurality of constraint set candidates in advance.
【請求項5】 始点側/終点側フリップフロップを有す
る論理回路のタイミング制約生成で用いられるプログラ
ムにおいて、 当該プログラムが、 前記始点側/終点側フリップフロップのそれぞれを行/
列とし、かつ当該フリップフロップ間の各パスに対する
制約条件を有効要素として示すタイミング制約行列を作
成し、 少なくとも一部の前記有効要素からなり、それに対応の
前記制約条件に基づく前記始点側フリップフロップの到
達時刻と前記終点側フリップフロップの要求時刻とをす
べて同時に満足できる形の制約集合を、前記タイミング
制約行列から求め、 前記制約集合に対応の前記到達時刻および前記要求時刻
を算出する機能をコンピュータに実現させるためのもの
である、ことを特徴とする論理回路のタイミング制約生
成用プログラム。
5. A program used for generating a timing constraint of a logic circuit having a start point / end point flip-flop, wherein the program executes the start point / end point flip-flop in a row /
A timing constraint matrix that indicates a constraint condition for each path between the flip-flops as an effective element, and includes at least a part of the effective elements, and generates a timing constraint matrix of the starting-side flip-flop based on the corresponding constraint condition. A constraint set in a form that can simultaneously satisfy the arrival time and the request time of the end-point side flip-flop is obtained from the timing constraint matrix, and the computer has a function of calculating the arrival time and the request time corresponding to the constraint set. A program for generating a timing constraint of a logic circuit, which is to be realized.
【請求項6】 始点側/終点側フリップフロップを有す
る論理回路のタイミング制約生成で用いられるプログラ
ムを記憶したコンピュータ読み取り可能な記録媒体にお
いて、 当該プログラムが、 前記始点側/終点側フリップフロップのそれぞれを行/
列とし、かつ当該フリップフロップ間の各パスに対する
制約条件を有効要素として示すタイミング制約行列を作
成し、 少なくとも一部の前記有効要素からなり、それに対応の
前記制約条件に基づく前記始点側フリップフロップの到
達時刻と前記終点側フリップフロップの要求時刻とをす
べて同時に満足できる形の制約集合を、前記タイミング
制約行列から求め、 前記制約集合に対応の前記到達時刻および前記要求時刻
を算出する機能をコンピュータに実現させるためのもの
である、ことを特徴とする論理回路のタイミング制約生
成用プログラム記録媒体。
6. A computer-readable recording medium storing a program used for generating a timing constraint of a logic circuit having a start-point side / end-point side flip-flop, wherein the program reads the start-point side / end-point side flip-flop. line/
A timing constraint matrix that indicates a constraint condition for each path between the flip-flops as an effective element as a column, and includes at least a part of the effective elements, and the starting-point-side flip-flop based on the constraint condition corresponding thereto. A computer obtains a constraint set that satisfies both the arrival time and the request time of the end-point side flip-flop at the same time from the timing constraint matrix, and calculates the arrival time and the request time corresponding to the constraint set in a computer. A program recording medium for generating a timing constraint of a logic circuit, which is to be realized.
JP2001347206A 2000-11-16 2001-11-13 Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit Withdrawn JP2002215711A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2001347206A JP2002215711A (en) 2000-11-16 2001-11-13 Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2000349915 2000-11-16
JP2000-349915 2000-11-16
JP2001347206A JP2002215711A (en) 2000-11-16 2001-11-13 Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit

Publications (1)

Publication Number Publication Date
JP2002215711A true JP2002215711A (en) 2002-08-02

Family

ID=26604096

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2001347206A Withdrawn JP2002215711A (en) 2000-11-16 2001-11-13 Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit

Country Status (1)

Country Link
JP (1) JP2002215711A (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010262647A (en) * 2009-04-30 2010-11-18 Internatl Business Mach Corp <Ibm> Method and device for detecting contradictory timing constraint conflict
WO2011161771A1 (en) * 2010-06-22 2011-12-29 富士通株式会社 Timing restriction generation support device, timing restriction generation support program, and, method of timing restriction generation support

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2010262647A (en) * 2009-04-30 2010-11-18 Internatl Business Mach Corp <Ibm> Method and device for detecting contradictory timing constraint conflict
WO2011161771A1 (en) * 2010-06-22 2011-12-29 富士通株式会社 Timing restriction generation support device, timing restriction generation support program, and, method of timing restriction generation support
US8683399B2 (en) 2010-06-22 2014-03-25 Fujitsu Limited Timing constraint generating support apparatus and method of supporting generation of timing constraint

Similar Documents

Publication Publication Date Title
US20240045865A1 (en) Multi-step query execution in sql server
US7162706B2 (en) Method for analyzing and validating clock integration properties in circuit systems
US9152742B1 (en) Multi-phase models for timing closure of integrated circuit designs
US8977995B1 (en) Timing budgeting of nested partitions for hierarchical integrated circuit designs
US8935642B1 (en) Methods for single pass parallel hierarchical timing closure of integrated circuit designs
US20120095746A1 (en) Novel modeling approach for timing closure in hierarchical designs leveraging the separation of horizontal and vertical aspects of the design flow
CN109145320B (en) Static time sequence analysis method and device in chip hierarchical physical design
US11062066B2 (en) Information processing apparatus, computer-readable recording medium, and information processing method
US8607186B2 (en) Automatic verification of merged mode constraints for electronic circuits
US8627262B2 (en) Automatic generation of merged mode constraints for electronic circuits
US20040210861A1 (en) System and method for optimizing exceptions
US8375347B2 (en) Driven metal critical dimension (CD) biasing
US8566768B1 (en) Best clock frequency search for FPGA-based design
US20060184912A1 (en) Automatic design apparatus for semiconductor integrated circuits, method for automatically designing semiconductor integrated circuits, and computer program product for executing an application for an automatic design apparatus for semiconductor integrated circuits
JP2002215711A (en) Timing constraint generating method to logical circuit, timing constraint generating program to logical circuit, and program recording medium for generating timing constraint to logical circuit
US7512923B2 (en) Automatic estimation method, apparatus, and recording medium
US9489478B2 (en) Simplifying modes of an electronic circuit by reducing constraints
US7945882B2 (en) Asynchronous circuit logical verification method, logical verification apparatus, and computer readable storage medium
JP2003216672A (en) Semiconductor circuit design support system and method, and semiconductor circuit design support program
US8037085B2 (en) Predicate selection in bit-level compositional transformations
JP2006309748A (en) Rectangular element placement method, rectangular element placement device and rectangular element placement program
JP4649337B2 (en) Library creation apparatus and method, and computer-readable recording medium on which library creation program is recorded
JP4448048B2 (en) Structural analysis program
Yang et al. Automating logic transformations with approximate spfds
JP2008198160A (en) Redundant circuit detecting method and program

Legal Events

Date Code Title Description
A300 Application deemed to be withdrawn because no request for examination was validly filed

Free format text: JAPANESE INTERMEDIATE CODE: A300

Effective date: 20050201