CN114186519A - Timing bottleneck detection method, device, terminal device and storage medium - Google Patents
Timing bottleneck detection method, device, terminal device and storage medium Download PDFInfo
- Publication number
- CN114186519A CN114186519A CN202111362990.XA CN202111362990A CN114186519A CN 114186519 A CN114186519 A CN 114186519A CN 202111362990 A CN202111362990 A CN 202111362990A CN 114186519 A CN114186519 A CN 114186519A
- Authority
- CN
- China
- Prior art keywords
- node
- time
- demand time
- timing
- demand
- 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.)
- Granted
Links
- 238000001514 detection method Methods 0.000 title claims abstract description 12
- 238000010586 diagram Methods 0.000 claims abstract description 56
- 238000000034 method Methods 0.000 claims abstract description 55
- 238000013507 mapping Methods 0.000 claims description 53
- 238000004364 calculation method Methods 0.000 claims description 29
- 238000004590 computer program Methods 0.000 claims description 25
- 238000013461 design Methods 0.000 description 9
- 230000006870 function Effects 0.000 description 6
- 238000005457 optimization Methods 0.000 description 6
- 230000003068 static effect Effects 0.000 description 5
- 238000004458 analytical method Methods 0.000 description 4
- 238000012163 sequencing technique Methods 0.000 description 4
- 230000006835 compression Effects 0.000 description 3
- 238000007906 compression Methods 0.000 description 3
- 239000000523 sample Substances 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 230000015572 biosynthetic process Effects 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 238000012938 design process Methods 0.000 description 2
- 230000005284 excitation Effects 0.000 description 2
- 238000003786 synthesis reaction Methods 0.000 description 2
- 238000012360 testing method Methods 0.000 description 2
- 238000012300 Sequence Analysis Methods 0.000 description 1
- 238000009825 accumulation Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004422 calculation algorithm Methods 0.000 description 1
- 230000001413 cellular effect Effects 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 230000001934 delay Effects 0.000 description 1
- 239000002360 explosive Substances 0.000 description 1
- 238000005259 measurement Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000012545 processing Methods 0.000 description 1
- 230000011218 segmentation Effects 0.000 description 1
- 230000008054 signal transmission Effects 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/32—Circuit design at the digital level
- G06F30/33—Design verification, e.g. functional simulation or model checking
- G06F30/3315—Design verification, e.g. functional simulation or model checking using static timing analysis [STA]
Landscapes
- Engineering & Computer Science (AREA)
- Computer Hardware Design (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Tests Of Electronic Circuits (AREA)
Abstract
The invention discloses a time sequence bottleneck probing method, a device, terminal equipment and a storage medium, wherein the method comprises the steps of initializing a circuit timing diagram, traversing each node in the circuit timing diagram from front to back according to a topological sorting result of the circuit timing diagram, and calculating the arrival time of each node; traversing each node in the circuit timing diagram from back to front according to the topological sorting result of the circuit timing diagram, and calculating the required time from each node to each corresponding sub-node; calculating the total fan-out negative allowance of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node; and calculating the total fan-out negative margin of each combinational logic unit in the circuit timing diagram according to the total fan-out negative margin of each node, and then determining a timing bottleneck according to the total fan-out negative margin of each combinational logic unit. By implementing the invention, the detection of the timing bottleneck in the circuit can be realized.
Description
Technical Field
The invention relates to the technical field of electronic design automation, in particular to a time sequence bottleneck probing method, a time sequence bottleneck probing device, terminal equipment and a storage medium.
Background
Static timing analysis is a work flow for calculating and predicting the timing of a digital circuit in electronic engineering, and the flow does not need to be simulated by means of input excitation. Traditionally, one often has the operating clock frequency as one of the characteristics of a high performance integrated circuit. In order to test the ability of a circuit to operate at a specified rate, it is necessary to measure the delay of the circuit at different stages of operation during the design process. Furthermore, delay calculations for the internal paths of the circuit are required at different design stages (e.g., logic synthesis, placement, routing, and some subsequent stages) to guide the optimization. The paths through which signals travel during conduction from one sequential element to another are the timing paths, and one or more timing paths that are critical to the ultimate timing performance of the circuit are defined as critical paths. Timing bottlenecks are combinatorial logic cells or nets in the overall design that determine the critical path delay size, number, and maximum impact on the optimization goal, often represented as high-delay logic or high-fan-out nets. Reducing the delay or the number of the timing bottleneck can significantly improve the convergence rate of software and the overall performance of a circuit, and how to probe the timing bottleneck in the circuit is an urgent problem to be solved in order to reduce the delay or the number of the timing bottleneck, the timing bottleneck in the circuit needs to be probed first.
Disclosure of Invention
The embodiment of the invention provides a time sequence bottleneck probing method, a time sequence bottleneck probing device, terminal equipment and a storage medium, which can probe a time sequence bottleneck in a circuit.
An embodiment of the present invention provides a timing bottleneck probing method, including: initializing a circuit timing diagram, traversing each node in the circuit timing diagram from front to back according to a topological sorting result of the circuit timing diagram, and calculating the arrival time of each node;
traversing each node in the circuit timing diagram from back to front according to the topological sorting result of the circuit timing diagram, and calculating the required time from each node to each corresponding sub-node;
calculating the total fan-out negative allowance of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node;
and calculating the total fan-out negative margin of each combinational logic unit in the circuit timing diagram according to the total fan-out negative margin of each node, and then determining a timing bottleneck according to the total fan-out negative margin of each combinational logic unit.
Further, the determining a timing bottleneck according to the total fan-out negative margin of each combinational logic unit specifically includes:
calculating the absolute value of the total fan-out negative allowance of each combinational logic unit to obtain the time sequence bottleneck value of each combinational logic unit;
and sequencing the time sequence bottleneck values of all the combinational logic units from large to small, and taking the combinational logic units arranged in front of the preset sequence as the time sequence bottlenecks.
Further, after calculating the required time from each node to each corresponding sub-node, the method further includes:
and generating a demand time record table of each node by taking the demand time as a key and the total number of the sub-nodes corresponding to the same demand time as a value according to the demand time from each node to each corresponding sub-node, and storing the demand time record table.
Further, after generating the demand time record table of each node, the method further includes:
when determining that the data pair entry recorded in a demand time recording table exceeds a preset threshold value N, equally dividing the interval duration between the maximum demand time and the minimum demand time in the demand time recording table into N-1 parts;
taking the required maximum demand time, the minimum demand time and the time corresponding to each equant point as mapping time;
projecting each required time to a coordinate axis formed by each mapping time, calculating the offset between each required time projection and the two closest mapping times, and then taking the mapping time with smaller offset as the mapping time corresponding to the required time;
and replacing each demand time with the corresponding mapping time to obtain a plurality of updated demand times, and then updating the demand time recording list according to each updated demand time.
Further, the calculating the total negative fan-out margin of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node specifically includes:
acquiring each required time corresponding to each node and the sub-node number corresponding to each required time according to the required time record table of each node;
and calculating the total fan-out negative allowance of each node according to the required time corresponding to each node, the sub-node number corresponding to each required time and the arrival time of each node.
On the basis of the embodiment of the method item, the invention correspondingly provides an embodiment of a device item;
the invention provides a sequential bottleneck probing device, which comprises an arrival time calculation module, a required time calculation module, a total fan-out negative allowance calculation module and a sequential bottleneck determination module, wherein the total fan-out negative allowance calculation module comprises a total fan-out negative allowance calculation module and a total fan-out negative allowance calculation module;
the arrival time calculation module is used for initializing the circuit timing diagram, traversing each node in the circuit timing diagram from front to back according to the topological sorting result of the circuit timing diagram and calculating the arrival time of each node;
the required time calculation module is used for traversing each node in the circuit timing diagram from back to front according to the topological sorting result of the circuit timing diagram and calculating the required time from each node to each corresponding sub-node;
the total fan-out negative margin calculation module is used for calculating the total fan-out negative margin of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node;
the timing bottleneck determining module is used for calculating the total fan-out negative margin of each combinational logic unit in the circuit timing diagram according to the total fan-out negative margin of each node, and then determining the timing bottleneck according to the total fan-out negative margin of each combinational logic unit.
Further, the system also comprises a demand time recording table generating module; and the demand time record table generating module is used for generating a demand time record table of each node by taking the demand time as a key and the total number of the sub-nodes corresponding to the same demand time as a value according to the demand time from each node to each corresponding sub-node, and storing the demand time record table.
Further, the system also comprises a demand time recording table updating module;
the demand time recording list updating module is used for equally dividing the interval duration between the maximum demand time and the minimum demand time in the demand time recording list into N-1 parts when determining that the data pair entry recorded in the demand time recording list exceeds a preset threshold value N;
taking the required maximum demand time, the minimum demand time and the time corresponding to each equant point as mapping time;
projecting each required time to a coordinate axis formed by each mapping time, calculating the offset between each required time projection and the two closest mapping times, and then taking the mapping time with smaller offset as the mapping time corresponding to the required time;
and replacing each demand time with the corresponding mapping time to obtain a plurality of updated demand times, and then updating the demand time recording list according to each updated demand time.
On the basis of the embodiment of the method item, the invention correspondingly provides an embodiment of the terminal equipment item;
an embodiment of the present invention provides a timing bottleneck probing terminal device, including: the invention also relates to a computer program stored in the memory and configured to be executed by the processor, wherein the processor implements the timing bottleneck probing method according to any item of the invention when executing the computer program.
On the basis of the above method item embodiment, the present invention correspondingly provides a storage medium item embodiment;
an embodiment of the present invention provides a storage medium, where the storage medium includes a stored computer program, where, when the computer program runs, a device where the storage medium is located is controlled to execute the timing bottleneck detection method according to any one of the present invention.
The embodiment of the invention has the following beneficial effects:
the embodiment of the invention provides a time sequence bottleneck probing method, which comprises the steps of firstly initializing a circuit time sequence chart, then traversing each node in the circuit time sequence chart from front to back according to a topological sorting result of the circuit time sequence chart, calculating the arrival time of each node, then traversing each node from back to front, calculating the required time from each node to each corresponding sub-node, calculating the total fan-out negative allowance of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node, finally calculating the fan-out negative allowance of each combinational logic unit, and determining the time sequence bottleneck of a circuit according to the fan-out negative allowance of each combinational logic unit. The timing sequence bottleneck probing method provided by the invention can probe the timing sequence bottleneck in the circuit, and lays a foundation for subsequently improving the overall performance of the circuit.
Drawings
Fig. 1 is a flowchart illustrating a timing bottleneck probing method according to an embodiment of the present invention.
Fig. 2 is a schematic diagram illustrating the principle of the trace-back path information according to an embodiment of the present invention.
Fig. 3 is another schematic diagram of the trace-back path information according to an embodiment of the present invention.
Fig. 4 is a schematic diagram of a demand time map according to an embodiment of the present invention.
Fig. 5 is a schematic structural diagram of a timing bottleneck probing apparatus according to an embodiment of the present invention.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
To better illustrate the invention, several concepts are described below:
static timing analysis: in electronic engineering, the timing sequence of a digital circuit is calculated and predicted to work, and the process does not need to be simulated by means of input excitation. Traditionally, one often has the operating clock frequency as one of the characteristics of a high performance integrated circuit. In order to test the ability of a circuit to operate at a specified rate, one needs to measure the delay of the circuit at different stages of operation during the design process. Furthermore, delay calculations for the internal paths of the circuit are required at different design stages (e.g., logic synthesis, placement, routing, and some subsequent stages) to guide the optimization. Static timing analysis plays an important role in the rapid and accurate measurement of circuit timing.
A time sequence path: the path through which a signal travels during conduction from a sequential element to another sequential element. Typically consisting of combinational logic elements and net crossovers.
A critical path: one or more timing paths that are critical to the ultimate timing performance of the circuit. Generally representing the timing path with the largest delay of the combined path in the design. The overall performance of the circuit, namely the highest working frequency, can be effectively improved by reducing the time delay of the critical path through an optimization means.
Time sequence bottleneck: the combinatorial logic cells or nets that determine the critical path delay size, number, and maximum impact on the optimization objectives in the overall design often behave as high-delay logic or high-fan-out nets. Reducing the delay or number of timing bottlenecks can significantly improve the convergence speed of software and the overall performance of the circuit.
Timing diagram: a directed acyclic graph depicting a circuit structure. In the diagram, the nodes represent the input and output pins of a basic cell circuit, such as a register or a logic gate, and the edges represent the input-to-output connections of a combinational logic cell circuit, or connections specified by a circuit netlist. Each edge is labeled with the delay needed to pass through the cell circuit or routing resource.
Arrival delay (arrival time): the time it takes for the signal to reach the circuit's specified location. The time of arrival of the clock signal is typically taken as the reference time, or zero time. To calculate the arrival time, a delay accumulation calculation of all combinational logic paths on the path needs to be performed.
Demand delay (demand): for any location, the signal can arrive without violating the timing design requirements of the overall circuit. Typically the path end point is back-calculated in conjunction with this programmed position to end point delay.
And (3) delay allowance: the difference between the demand time and the arrival time of the same location. A positive margin at any position of the circuit indicates that the arrival time can be increased by the time indicated by the margin, and the overall delay condition of the circuit is still not influenced. Conversely, a negative margin indicates that the transmission is too slow on the path whose transmission rate must be increased, otherwise the overall circuit formed by it cannot operate at the expected rate.
Time sequence arc: an edge between any two adjacent nodes in the timing diagram.
As an important engine, static timing analysis is widely used in various stages of circuit design and in the field of optimization, and various technical routes appear according to different requirements. The mainstream static time sequence analysis method is mainly divided into two types: graph scan method and path enumeration method.
The graph scanning method is a linear traversal scanning method, traversal is performed in sequence from low to high or from high to low according to the topological sorting depth of the nodes in the time sequence diagram, each node is visited once (arrival time and required time are respectively calculated), and the time sequence information of any node can be obtained after completion.
The path enumeration method is intuitive, and the path enumeration method starts to propagate from a starting point to a downstream node to a terminal point according to the signal transmission direction, and obtains the whole propagation footprint, namely all path information from the starting point to the terminal point. The basic operation object of the algorithm is a path. And accumulating the delay of all nodes from the starting point to the end point of each path to obtain the total delay of the path.
The present invention is described below, and as shown in fig. 1, an implementation of the present invention provides a timing bottleneck probing method, which at least includes:
step S101: initializing a circuit timing diagram, traversing each node in the circuit timing diagram from front to back according to a topological sorting result of the circuit timing diagram, and calculating the arrival time of each node.
Step S102: and traversing each node in the circuit timing diagram from back to front according to the topological sorting result of the circuit timing diagram, and calculating the required time from each node to each corresponding sub-node.
Step S103: and calculating the total fan-out negative allowance of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node.
Step S104: and calculating the total fan-out negative margin of each combinational logic unit in the circuit timing diagram according to the total fan-out negative margin of each node, and then determining a timing bottleneck according to the total fan-out negative margin of each combinational logic unit.
For step S101, preferably, after initializing the circuit timing diagram, traversing each node in the circuit timing diagram based on a graph scanning method according to a topology sorting result of the circuit timing diagram, and calculating an arrival time of each node in the traversal process;
in the conventional graph scanning method, for step S102, the required time of any node is determined by its child nodes. If the node is the end of the timing path, its required time is the clock cycle. If the node is a time sequence path intermediate node, the required time of the node is obtained by subtracting the time delay of the time sequence arc from the required time of the sub-node. And when the number of the sub-nodes is large, taking the minimum value of the demand time obtained by converting each sub-node as the demand time of the current node. The above process shows that if the nodes in the circuit timing diagram are traversed from back to front by adopting the existing graph scanning method, the required time of each node only comes from one sub-node, the required time obtained by conversion from other sub-nodes is ignored, that is, the traced-back path information from other sub-nodes is completely discarded, so that the calculation of the total negative margin of the fan-out of the node in the subsequent steps becomes impossible, and the time sequence of the whole fan-out region cannot be reflected. In order to solve the problem, in a preferred embodiment, when traversing each node in the circuit timing diagram from back to front based on a graph scanning method, the storage path information is recorded simultaneously so as to obtain the required time from each node to each corresponding sub-node;
schematically, as shown in fig. 2: 201. 202, 205 are intermediate nodes of the timing path, 203, 204, 206, 207 are end points of the timing path, and the required time is clock cycle 10. The delays are noted on the timing arcs. When backward traversal proceeds to 202, the required time for backward traversal from child nodes 203 and 204 is recorded as req # 203: 5 and req # 204: 9. similarly, node 205 records the demand time req # 206, deduced back from 206 and 207: 7 and req # 207: 7. when the flow proceeds to 201, the downstream path information of 202 and 205 is transmitted and summarized, and it can be visually obtained that there are 4 downstream paths of 201: 201-. Their demand times are recorded on node 201 and thus passed to the parent node of 201. The required time of the downstream path of 201 is req # 203: 0. req # 204: 4. req # 206: 4. req # 207: 4.
although the required time from each node to each corresponding child node can be calculated by adopting the method, with the progress of backward traversal or the improvement of the connectivity of the timing graph, the path information required to be recorded on the node shows explosive growth and shows the remarkable characteristics of the path enumeration method. The complexity needs to be reduced, so that the backward traversal process can return to the basic attribute of the graph traversal method.
Since only statistical information of all paths is required for subsequent calculation of the total fan-out margin of each node, no specific information of the paths is required. Therefore, in a preferred embodiment, after calculating the required time from each node to the corresponding sub-node, the method further includes: and generating a demand time record table of each node by taking the demand time as a key and the total number of the sub-nodes corresponding to the same demand time as a value according to the demand time from each node to each corresponding sub-node, and storing the demand time record table.
Specifically, a required time recording table (key, value) is established on each node, the required time is key, and the total number of paths corresponding to the required time is value. After the above method is adopted, the information of each node shown in fig. 2 can be compressed to obtain the trace-back path information shown in fig. 3, as shown in fig. 3, the required time deduced from 203, 204 on the node 202 is 5 and 9 respectively, so the required time record table stores two pairs (key, value): req # 1: (5,1) and req # 2: (9, 1); at node 205, the demand times inferred from 206, 207 are equal (both 7), so only one pair (key, value) of req # 1: (7,2), meaning that the number of paths requiring time 7 in the fan-out area is 2. On node 201, two pairs (key, value) of req # 1: (0,1) and req # 1: (4,3), that is, the number of paths requiring time 4 in the fan-out area is 3, and the number of paths requiring time 0 is 1. Compared to fig. 2, the entries required to be stored on nodes 201 and 205 are halved. The merged information also reduces the computational complexity of the parent node when passed to the parent node.
The above embodiment can implement compression of trace-back path information, but the above compression method requires that the number of paths can be merged under the condition that the required time is completely equal. When the design scale is increased and the time sequence model is more complex, the required time values of the nodes are widely distributed. Simple compression fails when the fan-out paths are in the tens of thousands.
Therefore, in a preferred embodiment, after generating the demand time record table of each node, the method further includes:
when determining that the data pair entry recorded in a demand time recording table exceeds a preset threshold value N, equally dividing the interval duration between the maximum demand time and the minimum demand time in the demand time recording table into N-1 parts;
taking the required maximum demand time, the minimum demand time and the time corresponding to each equant point as mapping time;
projecting each required time to a coordinate axis formed by each mapping time, calculating the offset between each required time projection and the two closest mapping times, and then taking the mapping time with smaller offset as the mapping time corresponding to the required time;
and replacing each demand time with the corresponding mapping time to obtain a plurality of updated demand times, and then updating the demand time recording list according to each updated demand time.
Specifically, in order to further control the increase of node storage entries along with traversal progress, a method for projecting the required time and approximating a segmented target value is proposed, and the storage entries in any node are controlled within a fixed upper limit (i.e. the preset threshold) N. This upper limit value does not vary from node to node. And when the required time entry of the node is less than N, all the required time is saved according to the original value without projection calculation. When the required time entry has more than N, projection approximation needs to be performed on the required time to replace the corresponding mapping time.
Illustratively, as shown in fig. 4, when N is 6, it is assumed that there are 8 demand times recorded in the original demand time recording table: rmin (minimum demand time), Rmax (maximum demand time), R1-R6 (demand times other than the minimum demand time and the maximum demand time in the demand time recording table); equally dividing the closed interval determined by Rmin-Rmax into 5 parts (N-1) to obtain 6 mapping times: dmin, Dmax, D1-D4, that is, the required time stored in the node is only any one of 6 mapping times. By projecting R1-R6 to Dmin-Dmain determined coordinate axes respectively, it can be seen that R1 and R2 are approximately represented as D1, R3 is approximately represented as D2, R4, R5 and R6 are approximately represented as D3, and D4 is not matched as mapping time. The principle of approximate value is as follows: and taking the mapping time with smaller offset between the original required time projection and the latest two mapping times. If the projection of R6 falls between D3 and D4 and the offset from D3 is small, the mapping time corresponding to R6 is D3. According to the method, the mapping time corresponding to Rmin is Dmin, the mapping time corresponding to Rmax is Dmax, the mapping time corresponding to R1 and R2 is D1, the mapping time corresponding to R3 is D2, the mapping time corresponding to R4, R5 and R6 is D3; then replacing each demand time with corresponding mapping time, and then updating a demand time recording table; suppose the original demand time record table stores data pairs as: (Rmin, Nmin), (R1, N1), (R2, N2), (R3, N3), (R4, N4), (R5, N5), (R6, N6), (Rmax, Nmax), the updated demand time table is: (Dmin, Nmin), (D1, N1+ N2), (D2, N3), (D3, N4+ N5+ N6), (Dmax, Nmax), the amount of data stored is reduced from 8 to 4, the amount of data is greatly reduced, and it can be known from the above process that: no matter the scale of the required time entries input by the sub-nodes, the number of the compressed entries does not exceed a constant N, namely, in any node. On the other hand, the larger the value of N, the smaller the segmentation, the smaller the projection approximation error, and the more accurate the result.
In addition, in other preferred embodiments, the time difference value between each demand time and each mapping time in the demand time recording table can be calculated one by one, and the mapping time corresponding to each demand time is determined according to the time difference value; the mapping time corresponding to a demand time is the mapping time with the minimum time difference value;
step S103, a total fan-out negative margin of each node is described first, where the total fan-out negative margin of a node is a sum of timing margins from the node to each sub-node, which are negative values;
in a preferred embodiment, if the required time from the node to each corresponding child node is obtained only according to the principle shown in fig. 2, but the required time record table of each child node is not generated, then when the total fan-out negative margin of each node is calculated, the time sequence margins from the node to each child node are calculated one by one directly according to the required time from the node to each corresponding child node and the arrival time of the node, and then the total fan-out negative margin of each node can be obtained by counting the sum of negative values of the time sequence margins; specifically, as shown in FIG. 2, the required time from node 202 to sub-nodes 203 and 204 is 5 and 9, respectively, the arrival time of node 202 is 8 (i.e., "arr: 8" in the figure), then the timing margin from node 202 to sub-node 203 is-3, the timing margin from node 202 to sub-node 204 is 1, then the total negative fan-out margin of node 202 is-3, i.e., the timing margin from node 202 to sub-node 203; the demand time for node 205 to sub-nodes 206 and 207 are both 7, the arrival time of node 205 is 6 (i.e., "arr: 6" in the figure), then the timing margin for node 205 to sub-node 206 is 1, the timing margin for node 205 to sub-node 207 is 1, there is no negative timing margin, and the total fan-out negative margin for node 205 is 0. Similarly, the arrival time of node 201 is 3 (i.e., "arr: 3" in the figure), the required time is 0, 4, respectively, and the corresponding margins are-3, 1, respectively, so the total fan-out margin of 201 is-3.
In another preferred embodiment of the present invention, if the required time record table of each sub-node is generated, then when the total fan-out negative allowance of each node is calculated, each required time corresponding to the node in the required time record table and the number of sub-nodes corresponding to each required time are obtained, then each time sequence allowance corresponding to the node is calculated, the number corresponding to each time sequence allowance is determined according to the number of sub-nodes, and finally, the total fan-out negative allowance of each node is calculated according to each time sequence allowance and the number corresponding to each time sequence allowance; specifically, as shown in fig. 3, the demand time table of the node 201 has two data: req # 1: (0,1) and req # 2: (4, 1); then the timing margin of-3, number 1 can be obtained; timing margin 1, number 3; the final total fan-out negative margin is then: -3 x 1 ═ 3.
For step S104, in a preferred embodiment, the determining a timing bottleneck according to the total fan-out negative margin of each combinational logic unit specifically includes: calculating the absolute value of the total fan-out negative allowance of each combinational logic unit to obtain the time sequence bottleneck value of each combinational logic unit; and sequencing the time sequence bottleneck values of all the combinational logic units from large to small, and taking the combinational logic units arranged in front of the preset sequence as the time sequence bottlenecks.
In the present invention, the definition of the total fan-out negative margin is proposed for a general combinational logic cell in a sequential path: taking all output pins of the combinational logic unit as a starting point, and taking all paths from the output pins of the combinational logic unit to a timing end point, the path delay margin is the sum of negative values (namely the total negative margin of each combinational logic unit is the sum of the total fan-out negative margins of all output nodes of each combinational logic unit). After the total fan-out negative allowances of the nodes are obtained through calculation in the step S103, the sum of the total fan-out negative allowances of the output nodes corresponding to the combinational logic units is calculated, the total fan-out negative allowances of the combinational logic units are finally obtained, then the absolute value of the total fan-out negative allowances of each combinational logic unit is used as the time sequence bottleneck value of each combinational logic unit, the combinational logic units arranged in front of the preset sequence are used as the time sequence bottleneck value according to the time sequence bottleneck value in a descending order; for example, if the predetermined order is 3, the combinational logic cell with the first two bits is used as the timing bottleneck. The preset sequence can be adjusted according to actual requirements.
In a preferred embodiment, after sorting the sequential bottleneck values of each combinational logic unit from large to small, a sequential bottleneck sorting table is generated. Subsequent users can debug each combinational logic unit in the circuit one by one before and after the sequencing according to the generated time sequence bottleneck sequencing table so as to improve the circuit performance.
On the basis of the above method item embodiments, the present invention correspondingly provides apparatus item embodiments;
as shown in fig. 5, an embodiment of the present invention provides a timing bottleneck probing apparatus, including: the system comprises an arrival time calculation module, a demand time calculation module, a total fan-out negative allowance calculation module and a time sequence bottleneck determination module;
the arrival time calculation module is used for initializing the circuit timing diagram, traversing each node in the circuit timing diagram from front to back according to the topological sorting result of the circuit timing diagram and calculating the arrival time of each node;
the required time calculation module is used for traversing each node in the circuit timing diagram from back to front according to the topological sorting result of the circuit timing diagram and calculating the required time from each node to each corresponding sub-node;
the total fan-out negative margin calculation module is used for calculating the total fan-out negative margin of each node according to the arrival time of each node and the required time from each node to each corresponding sub-node;
the timing bottleneck determining module is used for calculating the total fan-out negative margin of each combinational logic unit in the circuit timing diagram according to the total fan-out negative margin of each node, and then determining the timing bottleneck according to the total fan-out negative margin of each combinational logic unit.
In a preferred embodiment, further comprising: a demand time recording table generating module; and the demand time record table generating module is used for generating a demand time record table of each node by taking the demand time as a key and the total number of the sub-nodes corresponding to the same demand time as a value according to the demand time from each node to each corresponding sub-node, and storing the demand time record table.
In an alternative embodiment, the method further comprises: a demand time recording table updating module; the demand time recording list updating module is used for equally dividing the interval duration between the maximum demand time and the minimum demand time in the demand time recording list into N-1 parts when determining that the data pair entry recorded in the demand time recording list exceeds a preset threshold value N;
taking the required maximum demand time, the minimum demand time and the time corresponding to each equant point as mapping time;
projecting each required time to a coordinate axis formed by each mapping time, calculating the offset between each required time projection and the two closest mapping times, and then taking the mapping time with smaller offset as the mapping time corresponding to the required time;
and replacing each demand time with the corresponding mapping time to obtain a plurality of updated demand times, and then updating the demand time recording list according to each updated demand time.
On the basis of the embodiment of the method item, the invention correspondingly provides an embodiment of the terminal equipment item;
an embodiment of the present invention provides a timing bottleneck probing terminal device, including a processor, a memory, and a computer program stored in the memory and configured to be executed by the processor, where the processor implements the timing bottleneck probing method described in any one of the above items when executing the computer program.
On the basis of the above method item embodiments, the present invention correspondingly provides storage medium item embodiments;
an embodiment of the present invention provides a storage medium, where the storage medium includes a stored computer program, where when the computer program runs, a device on which the storage medium is located is controlled to execute any one of the above timing bottleneck detection methods.
It should be noted that the timing bottleneck probing apparatus/terminal device includes: a processor, a memory, and a computer program stored in the memory and executable on the processor. The processor, when executing the computer program, implements the steps in the above-described embodiments of the timing bottleneck probing method, such as the step timing bottleneck probing method shown in fig. 1. Alternatively, the processor implements the functions of the modules in the above device embodiments when executing the computer program.
Illustratively, the computer program may be partitioned into one or more modules that are stored in the memory and executed by the processor to implement the invention. The one or more modules may be a series of computer program instruction segments capable of performing specific functions, which are used for describing the execution process of the computer program in the timing bottleneck probing apparatus/terminal device.
The timing bottleneck exploring device/terminal equipment can be computing equipment such as a desktop computer, a notebook computer, a palm computer and a cloud server. The timing bottleneck probing apparatus/terminal device may include, but is not limited to, a processor, a memory. It will be understood by those skilled in the art that the schematic diagram is merely an example of a timing bottleneck probing apparatus/terminal device, and does not constitute a limitation of the timing bottleneck probing apparatus/terminal device, and may include more or less components than those shown, or combine some components, or different components, for example, the timing bottleneck probing apparatus/terminal device may further include an input/output device, a network access device, a bus, etc.
The Processor may be a Central Processing Unit (CPU), other general purpose Processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), an off-the-shelf Programmable Gate Array (FPGA) or other Programmable logic device, discrete Gate or transistor logic, discrete hardware components, etc. The general purpose processor may be a microprocessor or the processor may be any conventional processor or the like, the processor is a control center of the timing bottleneck probing apparatus/terminal device, and various interfaces and lines are used to connect various parts of the whole timing bottleneck probing apparatus/terminal device.
The memory may be used for storing the computer programs and/or modules, and the processor may implement various functions of the timing bottleneck probing apparatus/terminal device by running or executing the computer programs and/or modules stored in the memory and calling data stored in the memory. The memory may mainly include a storage program area and a storage data area, wherein the storage program area may store an operating system, an application program required by at least one function (such as a sound playing function, an image playing function, etc.), and the like; the storage data area may store data (such as audio data, a phonebook, etc.) created according to the use of the cellular phone, and the like. In addition, the memory may include high speed random access memory, and may also include non-volatile memory, such as a hard disk, a memory, a plug-in hard disk, a Smart Media Card (SMC), a Secure Digital (SD) Card, a Flash memory Card (Flash Card), at least one magnetic disk storage device, a Flash memory device, or other volatile solid state storage device.
Wherein, the module integrated by the timing bottleneck exploring device/terminal equipment can be stored in a computer readable storage medium if the module is realized in the form of a software functional unit and sold or used as an independent product. Based on such understanding, all or part of the flow of the method according to the embodiments of the present invention may also be implemented by a computer program, which may be stored in a computer-readable storage medium, and when the computer program is executed by a processor, the steps of the method embodiments may be implemented. Wherein the computer program comprises computer program code, which may be in the form of source code, object code, an executable file or some intermediate form, etc. The computer-readable medium may include: any entity or device capable of carrying the computer program code, recording medium, usb disk, removable hard disk, magnetic disk, optical disk, computer Memory, Read-Only Memory (ROM), Random Access Memory (RAM), electrical carrier wave signals, telecommunications signals, software distribution medium, and the like. It should be noted that the computer readable medium may contain content that is subject to appropriate increase or decrease as required by legislation and patent practice in jurisdictions, for example, in some jurisdictions, computer readable media does not include electrical carrier signals and telecommunications signals as is required by legislation and patent practice.
It should be noted that the above-described device embodiments are merely illustrative, where the units described as separate parts may or may not be physically separate, and the parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on multiple network units. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution of the present embodiment. In addition, in the drawings of the embodiment of the apparatus provided by the present invention, the connection relationship between the modules indicates that there is a communication connection between them, and may be specifically implemented as one or more communication buses or signal lines. One of ordinary skill in the art can understand and implement it without inventive effort.
While the foregoing is directed to the preferred embodiment of the present invention, it will be understood by those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111362990.XA CN114186519B (en) | 2021-11-17 | 2021-11-17 | Timing bottleneck detection method, device, terminal equipment and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202111362990.XA CN114186519B (en) | 2021-11-17 | 2021-11-17 | Timing bottleneck detection method, device, terminal equipment and storage medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN114186519A true CN114186519A (en) | 2022-03-15 |
| CN114186519B CN114186519B (en) | 2025-02-14 |
Family
ID=80540283
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202111362990.XA Active CN114186519B (en) | 2021-11-17 | 2021-11-17 | Timing bottleneck detection method, device, terminal equipment and storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN114186519B (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114861579A (en) * | 2022-05-25 | 2022-08-05 | 上海安路信息科技股份有限公司 | Method and system for analyzing time sequence bottleneck node and optimizing time sequence in integrated circuit |
| CN115293083A (en) * | 2022-09-30 | 2022-11-04 | 深圳鸿芯微纳技术有限公司 | Integrated circuit time sequence prediction method and device, electronic equipment and storage medium |
| CN117787163A (en) * | 2023-12-28 | 2024-03-29 | 苏州异格技术有限公司 | A timing analysis method, device, equipment and medium based on graph traversal |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7191417B1 (en) * | 2004-06-04 | 2007-03-13 | Sierra Design Automation, Inc. | Method and apparatus for optimization of digital integrated circuits using detection of bottlenecks |
| US7219048B1 (en) * | 2001-01-02 | 2007-05-15 | Magma Design Automation, Inc. | Methodology and applications of timing-driven logic resynthesis for VLSI circuits |
| CN112232005A (en) * | 2020-09-25 | 2021-01-15 | 山东云海国创云计算装备产业创新中心有限公司 | Method, system, equipment and storage medium for repairing hold time violation |
| CN112632887A (en) * | 2020-12-18 | 2021-04-09 | 展讯通信（上海）有限公司 | Clock delay adjusting method and device of memory, storage medium and terminal |
-
2021
- 2021-11-17 CN CN202111362990.XA patent/CN114186519B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7219048B1 (en) * | 2001-01-02 | 2007-05-15 | Magma Design Automation, Inc. | Methodology and applications of timing-driven logic resynthesis for VLSI circuits |
| US7191417B1 (en) * | 2004-06-04 | 2007-03-13 | Sierra Design Automation, Inc. | Method and apparatus for optimization of digital integrated circuits using detection of bottlenecks |
| CN112232005A (en) * | 2020-09-25 | 2021-01-15 | 山东云海国创云计算装备产业创新中心有限公司 | Method, system, equipment and storage medium for repairing hold time violation |
| CN112632887A (en) * | 2020-12-18 | 2021-04-09 | 展讯通信（上海）有限公司 | Clock delay adjusting method and device of memory, storage medium and terminal |
Non-Patent Citations (1)
| Title |
|---|
| 杨磊，孙丰刚，柳平增，孙赛赛: "芯片层次化物理设计中的时序预算及时序收敛", 计算机与数字工程, vol. 39, no. 10, 20 October 2011 (2011-10-20), pages 60 - 63 * |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN114861579A (en) * | 2022-05-25 | 2022-08-05 | 上海安路信息科技股份有限公司 | Method and system for analyzing time sequence bottleneck node and optimizing time sequence in integrated circuit |
| CN115293083A (en) * | 2022-09-30 | 2022-11-04 | 深圳鸿芯微纳技术有限公司 | Integrated circuit time sequence prediction method and device, electronic equipment and storage medium |
| CN117787163A (en) * | 2023-12-28 | 2024-03-29 | 苏州异格技术有限公司 | A timing analysis method, device, equipment and medium based on graph traversal |
Also Published As
| Publication number | Publication date |
|---|---|
| CN114186519B (en) | 2025-02-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN114186519B (en) | Timing bottleneck detection method, device, terminal equipment and storage medium | |
| US10776547B1 (en) | Infinite-depth path-based analysis of operational timing for circuit design | |
| CN101317178B (en) | System and method for criticality prediction in statistical time series analysis | |
| US20210287120A1 (en) | Machine learning-based prediction of metrics at early-stage circuit design | |
| CN105138769B (en) | A kind of temporal model generation method and device for programmable circuit | |
| CN112613259B (en) | System-on-chip post-emulation method, device and electronic device | |
| CN109710998B (en) | Memory optimization type static time sequence analysis method and system thereof | |
| US7822591B2 (en) | Logic circuit model conversion apparatus and method thereof; and logic circuit model conversion program | |
| US8938703B1 (en) | Method and apparatus for comprehension of common path pessimism during timing model extraction | |
| US8028260B1 (en) | Determination of most critical timing paths in digital circuits | |
| US11055458B1 (en) | Functional coverage of designs using transition bins and cross coverage | |
| JP3851357B2 (en) | Timing characteristic extraction method for transistor circuit, storage medium storing timing characteristic library, LSI design method, and gate extraction method | |
| KR20220143809A (en) | Glitch Power Analysis with Register Transfer Level Vector | |
| CN113033132B (en) | A method for determining port timing constraints and related device | |
| Meng et al. | HEDALS: Highly efficient delay-driven approximate logic synthesis | |
| US11443088B1 (en) | Simulation using accelerated models | |
| CN110147139A (en) | Computer-implemented method, clock data processing system, and computer-readable storage medium | |
| JP2002108958A (en) | System and method for designing circuit and computer readable recording medium stored with circuit design program | |
| Chou et al. | Average-case technology mapping of asynchronous burst-mode circuits | |
| US7222039B2 (en) | Estimation of average-case activity for digital state machines | |
| US20060282803A1 (en) | Estimation of average-case activity for digital circuits | |
| US6876940B2 (en) | Measuring constraint parameters at different combinations of circuit parameters | |
| JPH06282600A (en) | Logic simulation device | |
| CN118709622B (en) | Method and device for incrementally improving FPGA time sequence performance | |
| US11586791B1 (en) | Visualization of data buses in circuit designs |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |