JPH0642253B2 - Critical path analysis processing method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Overview] Regarding a delay time analysis processing method in a large-scale digital circuit, each flip-flop is provided for the purpose of reducing a storage capacity necessary for speeding up a critical pulse tracking and a clock skew check. Alternatively, a critical delay table creating means for creating a critical delay table storing the integrated delay time value and the previous stage flip-flop or the terminal pin number of the gate circuit for each terminal pin of the gate circuit, and the next stage flip-flop for which the delay time is to be calculated next Alternatively, an event table creating means for creating an event table that stores the terminal pin number of the gate circuit and the starting pin number of the critical path traced back to the starting point is provided, and the flip-flop or the gate of the flip-flop or the gate of Critical for each stage The lay tables and event table, create with reference to the other party table together, configured to execute the delay time calculation process.

[Industrial application field]

The present invention relates to CAD (Computer Aided Design), and more particularly to a delay time analysis method in a large-scale digital circuit.

In the design of a large-scale digital circuit, the correctness of logic is confirmed by logic simulation, and the delay time between flip-flops is calculated to verify whether it is within a predetermined allowable range. Since a large computer processing time is required for the delay time calculation processing of a large-scale digital circuit, an efficient calculation method is required.

[Conventional technology]

In the delay time calculation processing of a large-scale digital circuit, a huge amount of computer processing time is required to calculate all possible paths (routes), so the most severe path (usually the path with the longest delay time, In some cases, the path has the shortest delay time, which will be referred to as a critical path hereinafter, and the delay time (hereinafter referred to as delay) is calculated.

FIG. 5 is a diagram for explaining a conventional delay time calculation processing method.

FIG. (A) is an example of a digital circuit that is a target of delay time calculation processing. In Figure (a), A, B, C, H, I
Is a flip-flop circuit (hereinafter abbreviated as FF),
D, E, F, and G indicate gate circuits in the middle.

Further, a, b, c, m, and n indicate clock pins of FF, and d, e, f, g, h, i, j, k, and l indicate input pins of FF or gate.

The delay time calculation process starts delay (hereinafter referred to as critical delay) calculation by a critical path from clock pins a, b, and c of A, B, and C of FF as a starting point, and outputs data of FF-H and I. Calculation processing is performed until the input pin k or l is reached. In this example, the critical path is the path with the largest delay.

The calculation process calculates the integrated delay value by sequentially integrating delay values for each gate stage from the starting FF to the final FF, and in a multi-input gate stage, the integrated delay value up to each input pin. Of the paths, the path passing through the pin showing the largest value is taken as the critical path, and the integrated delay value is used to add the delay to the next-stage pin to obtain the integrated critical delay value of the next-stage pin. In this way, the integrated critical delay value up to the input pin of the final stage FF is calculated. The calculation process for the digital circuit shown in FIG. 5 (a) is performed by the procedure described below, as shown in FIG. 5 (b).

The delay ta from the clock input terminal CLK1 to the pin a of the FF-A is calculated from the path length based on the circuit configuration data.

Similarly, the delay tb from the clock input terminal CLK2 to the pin b of FF-B is calculated.

Similarly, the delay tc from the clock input terminal CLK3 to the pin c of FF-C is calculated.

The delay in FF-A and the delay due to the path length from the output pin of FF-A to the input pin d of gate D are added to calculate the delay from pin a to pin d, and the value obtained by adding ta to this is calculated. It is calculated as the delay td of the pin d.

Similarly, tb is added to the delay due to the delay in FF-B and the path length from the output pin of FF-B to the input pin e of gate D to calculate the delay te of pin e.

Similarly, the delay tf of the input pin f of the gate E is calculated.

Similarly, the delay tf of the input pin g of the gate E is calculated.

The delays td and te of the input pins d and e of the gate D are compared. If td <te, the path passing through the pin e is regarded as a critical path.

Similarly, the delays tf and tg of the input pins f and g of the gate E are compared, and if tf <tg, the path passing through the pin g is determined as a critical path.

The delay tg due to the critical path is added to the delay due to the delay at the gate E and the path length to the input pin h of the gate F, and the integrated value of the delay passing through the critical path at the input pin h of the gate F: the critical integrated delay th is calculated. To do.

Similarly, the delay in the gate circuit D and the delay due to the path length to the input pin i of the gate G are added with the delay te due to the critical path to calculate the critical integration delay ti of the input pin i of the gate G.

Similarly, the critical integration delay tj of the input pin j of the gate G is calculated.

The delays ti and tj of the input pins i and j of the gate G are compared. If ti <tj, the path passing through the pin j is set as a critical path.

In addition to the delay at the gate D and the delay due to the path length of the gate H to the input pin k, the critical delay t
e is added to calculate the critical integration delay tk at the input pin k of the gate H.

In addition to the delay in the gate G and the delay due to the path length to the input pin 1 of the gate I, the critical delay t
j is added to calculate the critical integration delay tl at the input pin 1 of the gate I.

As a result of the above calculation, the critical integration delays at the input pins k and l of H and I, which are the final stage FFs, are obtained, and it is possible to check whether the delays meet the design criteria.

The designer of the digital circuit that has performed this delay calculation may not only want to know the critical delay value, but may also want to know what route it was. Also, F
In order to perform the delay check (hereinafter referred to as FF check) on the F pin, the clock skew between the FFs on the start side and the end side of the critical path is also involved.

For example, if the critical path to the data input pin k of FF-H is b → e → k as indicated by the broken line, the delay check in FF-H is performed between the data input pin k and the clock pin m. The skew is determined by the relationship between clocks CLK1 and CLK2. That is, it is checked whether Tcd + Td + Tskew ≦ Tcm + τ is satisfied.

Here, Tcb: Delay from LSI terminal to pin b.

TCM: Delay from LSI terminal to pin m.

Td: Critical delay value up to pin k.

Tskew: Skew value between CLK1 and CLK2.

τ: Clock period.

For example, if the critical path to the data input pin 1 of FF-I is c → g → h → j → l as shown by the broken line, the FF check is performed between the data input pin 1 and the clock pin n. The same clock CLK3 and no clock skew.

Conventionally, the following method has been adopted in order to perform the tracking of the critical path at a high speed and to promptly check the clock skew.

(1) For all the passing pins, together with the critical integration delay value, the start pin number of the critical path,
By storing it and transmitting it to the end pin,
Quickly get information on the start clock pin at FF check.

(2) For each pin on the critical path, the pin number of the previous stage is stored together with the critical integration delay value. As a result, the critical path can be traced again without delay calculation.

(3) By using both (1) and (2), both the pin number of the preceding stage and the starting pin number are stored in addition to the critical integration delay value for each pin on the critical path.

[Problems to be solved by the invention]

According to the conventional methods (1) to (3) for obtaining clock pin information, there are the following problems.

(1) After calculating the critical delay, the delay calculation is required again to follow the critical path.

(2) The critical path can be easily found by backtracking from the end pin, but it is necessary to always backtrack when finding the start pin when checking.

(3) In a large-scale circuit, the number of pins of the whole circuit is in the range of tens of thousands to millions, and storing both the preceding-stage pin number and the starting pin number has a storage capacity problem.

The present invention is intended to provide a critical path analysis processing method that solves the above conventional problems.

[Means for solving problems]

FIG. 1 is a block diagram showing the principle of the critical path analysis processing method according to the present invention.

In the figure, 1 is a critical delay table, which stores an integrated delay time value 11 and a pin number 12 of the preceding stage for each pin.

Reference numeral 2 is an event table, which stores the next-stage pin number 21 for which the delay time value is to be calculated next and the start pin number 22 that traces back to the calculation start point of the critical path.

Reference numeral 3 is a critical delay table creation means, which creates a critical delay table for each flip-flop or gate pin of each stage while referring to the event table 2.

Reference numeral 4 is an event table creating means, which creates the event table 2 for each stage while referring to the critical delay table 1.

[Work]

The event table 2 is provided for each FF stage, the next stage pin number 21 to be calculated next is stored in the event table 2, and the delay time value calculation proceeds. This event table 2
The starting pin number 22 is stored together with the pin number 21 to be calculated next.

The calculation of the integrated delay time value for each pin is performed in the order instructed by the event table 2, and the calculated integrated delay time value 11
Are stored in the critical delay table 1 together with the preceding pin number 12. The event table 2 is created for each gate stage, and it suffices to prepare two gate stages, and the processed gate stage table region can be used as a new gate stage table region.

When the calculation is transmitted one after another and the final pin is reached, the event table 2 is saved as the starting pin table. The clock skew for the FF check can be obtained from the separately stored information on the clock to the start pin and the clock to the last pin.

As described above, the start pin information does not have to be provided for each pin, and only the pins for two FF stages are required, so that the required storage capacity is greatly reduced.

For example, if the number of pins is 500,000 and the number of gate stages is 20,
Assuming that the number of stages is 8 bytes per start pin, the storage capacity required for start pin information is 500,000 × 8 bytes = 40 when provided in the critical delay table.
When it is stored in the event table, the expected amount of the event table 2 for one gate stage is 500,000 pins / 20 stages = 25,000, so about 25,000 x 2 x 8 bytes = 400,000 bytes. Become.

〔Example〕

The present invention will be described in more detail with reference to the examples shown in FIGS. 2 to 4.

FIG. 2 is a diagram showing a memory usage state in the main memory in the processing apparatus according to the embodiment of the present invention.

In the figure, 20 is an event table area, which is large enough to store an event table for two gate stages.

Reference numeral 10 is a critical delay table area, which requires a size for storing the critical table for the number of pins of the analysis processing target circuit.

Reference numeral 30 is a critical delay table creation program area, which stores an integration delay routine and the like.

An event table creation program area 40 stores a next stage pin detection routine, a delay comparison routine, and a start pin detection routine.

A circuit configuration data area 50 stores various data indicating the configuration of the designed digital circuit.

An initial data area 60 stores initial conditions such as a start pin number, an end pin number, and critical definition (delay maximum or minimum).

FIG. 4 is a flow chart showing the processing according to one embodiment of the present invention.

FIG. 3 is a diagram showing a processing example according to an embodiment of the present invention.

In FIG. 3, A to I, a to l, and CLK1 to CLK3 indicate FFs or gates, pins, and clock terminals, respectively, as in FIG.

Table (2) -1 shows the event table of the first gate stage, and table (2) -2 shows the event table of the second gate stage. Table (1) -1 shows a critical delay table for each pin of the FF belonging to the first gate stage, and table (1) -2 shows a critical delay table for each pin of the gate belonging to the second gate stage. . The table (3) is the event table of the final gate stage, and shows that this is the start pin table.

Hereinafter, according to each step of the flowchart of FIG.
The flow of processing according to this embodiment will be described with reference to FIGS. 2 and 3.

The event table creation program reads the start pin information in the initial condition data stored in the data area, creates the table (2) -0 by referring to the circuit configuration data, and stores it in the event table area. In this, a, b, and c are both described as the next-stage pin and start pin information. When the table (2) -0 has been created, control is passed to the critical delay table creation program.

The critical delay table creation program calculates the integrated critical delay values ta, tb, tc of the pins a, b, c according to the table (2) -0, and also writes the previous stage pin number to obtain the table (1) -1. Create and store in the critical delay table area. The integrated critical delay values ta, tb, tc are clock terminals CLK1, CLK2, CLK3, respectively.
To the pins a, b, and c, and the preceding-stage pin numbers are a, b, and c. When the table (1) -1 has been created, control is passed to the event table creation program.

The event table creation program is a table (2 which describes the next stage pin d and its start pin a, the next stage pin f and its start pin a, and similarly e and b, g and c to be calculated next from the circuit configuration data. ) -1 is created and stored in the event table area.

The critical delay table creation program calculates the delay values from pin a to pin d, pin a to pin f, pin b to pin e, and pin c to pin g according to table (2) -1. ) -1 ta, t
Table (1) -2 is created using the values ta, te, tf, and tg obtained by adding b and tc as integrated critical delay values and stored in the critical delay table area.

The event table creation program reads the circuit configuration data and sets the next-stage pins to be calculated next as k, i, and h. Next, read the critical direction from the initial data area, recognize that it is the side with the larger delay, read the integrated critical delay values of pins d and e from table (1) -2 and compare them, and find that td <te Since the path passing through the pin e is a critical path to the pin k, the starting pin is b. Similarly, since tf <tg, the path passing through the pin g is a critical path to the pin h and the starting pin is c. Table (2) -for the next-stage pins k, i, h and start pins b, b, c
2 is created, and the table (2) -0 in the event table area
Store it in the place where it was stored.

The critical delay table creation program calculates the delay of pin h according to Table (2) -2,
Make table (1) -3. Since the path passing through the pin g is critical, the delay value from the pin g to the pin h is calculated, and the value obtained by adding tg to this is set as the integrated critical delay value th, and the preceding pin number g is added to the table (1)- 3 is created and stored in the critical delay table area.

The event table creation program uses table (1)-
Create table (2) -3 for pin j from the result of 3,
Store in the location where the table (2) -1 in the event table area was stored.

The critical delay table creation program calculates delays for pin i and pin j,
(1) -4 is created and stored in the critical delay table area.

The event table creation program creates the event table (2) -4 for pin l. To do so, read Table (1) -4, compare the integrated critical delay values of pin i and pin j, and since ti <tj, pin l
It is found that the critical path to the path is a path passing through the pin j, and c is described as the starting pin number. The created table (2) -4 is the table (2) -2 in the event table area.
Store it where there was.

The critical delay table creation program performs delay calculation for pin k and creates table (1) -5. That is, from Table (2) -2, the critical path is b
Since it is known that → e → k, the delay from the pin e to the pin k is calculated, te is added to calculate tk, and the preceding pin number e is added. Next, the delay calculation is made for the pin l, and Table (1) -5 is created. That is, since the critical path is a path passing through the pin j, the delay from the pin j to the pin l is calculated, tj is added to this, and the integrated delay value tl is added, and the preceding pin number j is added. table
(1) -5 is the integrated critical delay values tk and tl of the pins k and l at the final stage to be obtained. Store the created table in the critical delay table area.

The event table creation program uses table (2)-
2 and the starting pin information b and c of the final pin k and the pin 1 from the table (2) -4 are extracted and stored in the event table area as the table (3). The starting pin required for clock skew check can be found from table (3).

〔The invention's effect〕

As described above, according to the present invention, in the delay analysis of the large-scale digital circuit, the required storage capacity is small,
The tracking of the critical path and the checking of the clock skew can be performed at high speed, and the effect of improving the data processing efficiency is great.

[Brief description of drawings]

FIG. 1 is a block diagram of the principle of the present invention, FIG. 2 is a diagram showing a memory use situation in one embodiment of the present invention, FIG. 4 is a flowchart showing a process according to one embodiment of the present invention, and FIG. FIG. 5 is a diagram showing a processing example according to an embodiment of the invention, and FIG. 5 is a diagram showing a processing example according to a conventional example. In the drawings, 1 is a critical delay table, 2 is an event table, 3 is a critical delay table creating means, 4 is an event table creating means, 10 is a critical delay table area, 11 is an accumulated delay time value, 12 is a previous pin number, 20 Is the event table area, 21 is the next pin number, 22 is the start pin number, 30 is the critical delay table creation program area, 40 is the event table creation program area, 50 is the circuit configuration data area, and 60 is the initial data area. Show.

Claims (1)

[Claims] 1. A method of analyzing delay time in a large-scale digital circuit, comprising: an integrated delay time value (11) for each terminal pin of each flip-flop or gate circuit and a terminal pin number ( 12), a critical delay table creating means (3) for creating a critical delay table (1), and a terminal pin number (21) of the next-stage flip-flop or gate circuit for which the delay time is to be calculated and a critical path are started. Equipped with event table creation means (4) that creates an event table (2) that stores the starting pin number (22) traced back to the point, from the start point to the final point of delay time calculation, for each stage of the flip-flop or gate. In addition, the critical delay table (1) and the event table (2) are created while referencing each other's table, and the delay time calculation process is performed. A critical path analysis processing method characterized by being configured to execute processing.