{'fraction_non_alphanumeric': 0.0236722571628232, 'fraction_numerical': 0.009390286512928022, 'mean_word_length': 4.225239616613418, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Static Timing Model Extraction for Combinational Circuits

For large circuits, static timing analysis (STA) needs to be performed in a hierarchical manner to achieve higher performance in arrival time propagation. In hierarchical STA, efficient and accurate timing models of sub-modules need to be created. We propose a timing model extraction method that significantly reduces the size of timing models without losing any accuracy by removing redundant timing information. Circuit components which do not contribute to the delay of any input to output pair are removed. The proposed method is deterministic. Compared to the original models, the numbers of edges and vertices of the resulting timing models are reduced by 84% and 85% on average, respectively, which are significantly more than the results achieved by other methods.


Introduction
Static timing analysis (STA) is widely used in digital circuit designs. The timing information of each circuit component is extracted from a design library. Combined with the result of parasitic extraction and the slopes of input signals, arrival times are propagated to compute the delays between the inputs and outputs of combinational circuits. Together with the timing characteristics of sequential components, e.g. the setup/hold time of flip-flops, the maximum/minimum of the computed delays determines the performance of the circuits.
In a hierarchical design flow, a design is composed of a series of circuit modules on different levels. To run static timing analysis for such a design style, the intuitive idea is to flatten all the sub-modules and run the propagation algorithm on this flat netlist. The disadvantage of this method is that the timing propagation through the full netlist is slow and very memory-consuming. Furthermore this flattening method will thwart the application of IP (Intellectual Property) macros from third-party vendors. The complete netlist of IP macros must be given to designers for static timing analysis, which is not always feasible for IP protection. In view of the reasons above, static timing analysis must also be hierarchical in such a design flow. As the first step, timing models of the sub-modules are generated from the original netlists. Then the arrival time propagation algorithm is run at circuit level, using the extracted timing models as the replacement of the netlists of the sub-modules. Naturally the extracted timing models must contain the exact delay information required by the high level analysis. To speed up the high level arrival time propagation, a timing model must be as compact as possible.
In [3] serial and parallel merges are introduced to reduce the size of combinational circuits and the compressed circuit netlists are used as timing models. The serial merge replaces two consecutive timing edges by a new one from the source of the first edge to the sink of the second edge. The parallel merge replaces parallel edges sharing the same source and sink by a single edge. Both operations are applied to the timing graph of the circuit iteratively until the size of the graph can not be reduced further. The application of these two fundamental operations heavily depends on the circuit structure and usually does not result in very small timing models for combinational circuits. In [5], a graph manipulation method is used to reduce the number of optimization constraints and timing variables in circuit optimization. In order to reduce the optimization complexity, circuit nodes whose removal can lead to fewer constraints and timing variables are deleted from the timing graph. This method transforms the circuit netlist targeting to effectively lower the optimization effort, but can not guarantee to generate a compact static timing model. In [2] a delay edge shrink method is used to merge several parallel delay edges followed by a single delay edge in series, and vice versa. Additionally, a parallel to serial graph transformation algorithm is also introduced to increase the possibility that the circuit can be compressed using the shrink method. These algorithms are applied to the original timing graph and the timing graph formed by directly connecting all the outputs of the original circuit with their driving inputs. Then, the smaller extracted timing model is selected as the final result. In [6] a timing model extraction method based on biclique-star replacement allowing don't care edges is introduced. This method extends the parallel to serial algorithm in [2] to deal with more than two inputs and outputs in the transformation. In order to find the proper replacement candidates for the biclique-star algorithm, an algorithm which maximizes edge coverage and the size of bicliques is also suggested in [6]. Both methods proposed in [2] and [6] are not deterministic and rely on heuristic pattern matching algorithms.
In this paper, we propose a method to extract timing models for combinational circuits by removing redundant timing information in the original timing graph. Without relying on heuristic pattern matching algorithms, the proposed method is deterministic and will always give compact results. Additionally, the proposed method does not use the graph manipulation algorithm in [2] and [6] and hence can be used as a pre-processing step before applying those algorithms.
In Section 2 we will formulate the problem and task of hierarchical timing model extraction. Then the proposed algorithms will be introduced in Section 3. In Section 4 we will show the extraction results of the proposed method using ISCAS85 benchmark circuits. Finally we will conclude our work.
In this section we will introduce the definition of a timing graph briefly. This timing graph will be used to illustrate our algorithms. Then, the requirement of the hierarchical timing model extraction for combinational circuits will be discussed. In the following sections, we will only discuss the worst-case timing model. The method for extracting the best-case timing model can be deduced similarly.

Timing Graph
A timing graph G is a weighted directed graph representing the timing information of a circuit. A vertex v i corresponds to a net in the circuit. An edge e ij represents a delay between vertices v i and v j . Each e ij has a weight d ij , which is the magnitude of the delay between vertices v i and v j . Compared with the circuit netlist, e ij corresponds to a pin to pin delay of a circuit component. When interconnects are considered, the delay of an interconnect is also represented by an edge. A timing path denoted as p ij is a set of consecutive connected edges between vertices v i and v j . The path delay is the sum of the weights of all the edges on path p ij and is also denoted as d ij . The set of all paths and their delays between vertices v i and v j are denoted as P ij and D ij respectively. A sub-graph is a set of edges from the timing graph and their source/sink vertices, denoted as G{e i1j1 , e i2j2 , . . .}. In Fig. 1 the circuit c17 from the ISCAS85 benchmarks and its corresponding timing graph are illustrated without considering interconnects.

Formulation of the Hierarchical Timing Model
The target of static timing analysis is to compute the maximum delay between the inputs and the outputs of a circuit. In order to do this, a variable a i is assigned to each vertex v i in the timing graph, called arrival time. Then the timing graph is traversed by propagating the arrival times through all vertices until the output vertices are reached.
In hierarchical timing analysis, sub-modules are replaced by pre-characterized timing models. A timing model is a timing graph including a new set of internal edges and vertices but with the same inputs and outputs as the original timing graph. A timing model must contain the exact timing information needed by the higher level. Additionally, the timing model of a sub-module should be as small as possible to accelerate the arrival time propagation at high level. When characterizing a sub-module, especially an IP block, the application environment is unknown. For this reason, no assumption about the arrival times at the inputs of the sub-module should be made. Fig. 2 illustrates the computation of the arrival time for an output v j of a sub-module during high level arrival time propagation. Firstly we consider the arrival time computation from only one input v i to the output v j . Normally there is more than one path between v i and v j , denoted as P ij with delay D ij . The arrival time from v i through a path p ij to v j can be computed as a i +d ij . If we enumerate all the paths between v i and v j , the maximum of these arrival times can be computed using (1), where M ij denotes the maximum path delay in D ij . Now considering all the inputs of the module, the arrival time a j is the maximum arrival time from all the inputs to v j . We get formula (2) to compute the arrival time a j , where V I is the set of all the inputs of the module. (2) we can conclude that the arrival time at an output of a sub-module is determined by the arrival times at all the inputs and the maximum delays between the input/output pairs. The arrival times at the inputs of the module are computed during high level arrival time propagation and are still unknown when characterizing timing models. On the contrary, the maximum of the input to output delays M ij in (2) are provided by the timing model. In order to propagate arrival times correctly, a timing model must have the same input to output delays M ij as the original timing graph.
Definition: The delay matrix of a circuit with m inputs and n outputs is an m × n matrix with item M ij , which is the maximum path delay between input v i and output v j . Theorem: The requirement for timing model extraction is that the characterized timing model must have the same delay matrix as the original timing graph.

The Timing Graph Reduction Algorithm
In this section we will explain a timing graph reduction method to extract compact timing models for combinational circuits. The basic edge shrink operation from [2] is introduced first. Thereafter two algorithms are explained which preprocess the original timing graph so that the basic shrink operation can be applied more effectively. Furthermore an output edge reduction algorithm will also be explained to compress the timing model. The target of the proposed timing model extraction method is to reduce the number of edges and vertices in the timing graph while maintaining the same delay matrix.

Basic Edge Shrink Operation
The basic edge shrink operation is illustrated in Fig. 3. If n edges with sink vertices v j1 . . . v jn leave the same vertex v k and v k has only one fanin edge respectively. This shrink transformation is illustrated in Fig. 3(a). Similarly, this transformation can be applied in reverse direction, as shown in Fig. 3(b). Fig. 4 shows an example of applying the basic shrink operation to the timing graph in Fig. 1. Two sub-graphs G{e 17 , e 67 , e 7a } and G{e 49 , e 59 , e 9b } can be compressed using the basic shrink operation. After this reduction, the number of the edges of the timing graph is reduced from 12 to 10 and the number of the vertices is reduced from 11 to 9.
In Fig. 4(b), the timing graph can not be reduced further because no vertex except the inputs has only one fanin/fanout edge. In the following, we will propose several algorithms to pre-process the original timing graph so that the basic shrink operation can be applied more effectively to reduce the number of the edges and vertices.

Primary Input/Output Transformation (PIT/POT)
The principle of the timing graph reduction is that the delay matrix remains unchanged. A row in the delay matrix contains the maximal delays from one input to all the outputs, and a column contains the maximal delays from all the inputs to one output.
In many circuits with abundant datapaths there is delay symmetry, which means the rows or columns in the delay matrix share some patterns. If the subtraction of two rows or columns in the delay matrix is a vector whose elements are the same, the timing model needs to contain only the timing information for one of the rows or columns. This means both inputs or outputs can share the same delay paths in the timing graph and the edges and vertices constructing the delay paths for one of them can be deleted to simplify the timing graph.
If two rows R i and R j in the delay matrix have constant difference, that is, R i − R j = C r , where C r is a row vector with constant element c r , the two inputs v i and v j corresponding to R i and R j can be transformed by the algorithm illustrated in Fig. 5.
Assume the vertices v 1 and v 2 in Fig. 5 meet the condition R 1 − R 2 = C r , we create a new vertex v 1 between v 1 and all its fanout vertices. v 1 is connected to all the fanout vertices of v 1 with the original edges from v 1 . The new edge e 11 has weight 0 so that the delays between v 1 and all the outputs do not change. In order to make v 1 and v 2 share the same timing paths, v 2 is disconnected from all its original fanout edges and a new edge between v 2 and v 1 is created, as in Fig. 5(b). The weight d 21 is set to −c r so that the delays from v 2 to all the outputs are also maintained because of R 1 − R 2 = C r . After this transformation, the unconnected vertices and edges are deleted recursively, illustrated in Fig. 5(c). Thereafter there may be sub-graphs which can be reduced using the basic shrink operation, e.g. G{e 35 , e 56 , e 57 }. These subgraphs are compressed further, as shown in Fig. 5(d). By creating a new vertex v 1 for the input transformation the necessity to create edges between v 2 and all the original fanout vertices of v 1 is avoided. Similar to PIT, POT transforms the primary outputs of the original timing graph. If two columns C i and C j in the delay matrix meet C i − C j = C c , where C c is a constant column vector with the element c c , the output v j is disconnected from its driving edges and connected with the vertex of output v i , through a new edge with weight −c c . Similarly, the edges and vertices which originally drive only v j are deleted to reduce the graph size. The POT algorithm is illustrated in Fig. 6, where v 7 changes its connection to v 6 . Because v 6 is an output in Fig. 6, it should not be deleted by applying the basic shrink operation to the sub-graph G{e 26 , e 36 , e 46 , e 67 }.

Non-Critical Edge/Vertex Removal (NCR)
Normally there is more than one path for an input/output pair in the original timing graph. In the view of the static timing analysis, only the path with the maximum delay, called critical path of the input/output pair, is needed in the high level arrival time propagation, as shown in (2). The other paths are dominated by the critical one and have no effect on the result of the timing analysis. From this observation, the edges which do not contribute to the delay matrix can be deleted to reduce the timing graph. Be aware that the definition of critical path here is different from the classical one, where the critical path dominates the paths starting from all the inputs of the timing graph. In our  definition, the critical path dominates all the paths starting from a specified input to a specified output. Fig. 7 illustrates the concept of the non-critical edge/vertex removal using the timing graph in Fig. 4(b). All the edge delays in Fig. 7 are assumed as unit for simplicity. Firstly, the redundant edge e 6a directly between v 6 and v a is removed because there is another path through v 6 , v 8 and v a with dominant delay, as shown in Fig. 7(b). After this removal a basic shrink operation can be applied to sub-graph G{e 26 , e 46 , e 68 } and the resulted timing graph is shown in Fig. 7(c). Similarly the redundant edge e 4b can also be deleted. The final timing model is shown in Fig. 7(d).
To reduce the size of the timing graph, only the edges and vertices which are not on the critical path of any input/output pair can be removed safely. Because timing edges and vertices may be shared by the critical paths between different input/output pairs, we firstly traverse the timing graph and mark the vertices which are on at least one critical path. After identifying the critical paths for all the input/output pairs, the vertices and the edges which are never critical are deleted from the timing graph.
Instead of visiting all the input-output pairs one by one, whose number is the product of the number of the inputs m and the number of the outputs n in the worst case, the original timing graph is traversed only m times [4]. At each traversal, the arrival times from a specified input to all the vertices are computed. We use the computed arrival times to trace the critical paths and mark the vertices on the critical paths backward. Fig. 8 shows the single input traversal and backward vertex mark algorithm-singleMark().
Because the arrival times at the inputs except v i are set to −∞ in Fig. 8, the arrival time of a vertex v j computed by (3) is the maximum delay from v i to v j . To mark the critical vertices from the input v i to an output v o , the algorithm traverses backward from v o to v i recursively. At each intermediate vertex v c , the fanin vertex v k is marked as critical, when the sum of the arrival time a k and the delay d kc is the largest one in all the fanin vertices of v c . v c is updated to v k for further backward traversal. At each run the tracing from an output to the input marks the path whose delay dominates the delays between the input and the output. All the edges and vertices on such a path will be kept in order to guarantee the conformability of the delay matrix.
The algorithm in Fig. 8 is applied to each input of the timing graph so that the vertices on the critical paths of all input/output pairs are marked. All the edges without marked fanin and fanout vertices do not contribute to the delay matrix. From the view of a timing model, these edges and unmarked vertices can be deleted to simplify the timing graph. Fig. 9 shows the complete non-critical edge/vertex removal algorithm.

Output Backward Merge (OBM)
If a primary output of a timing graph has only one fanin edge and its fanin vertex is not an output, we can simply merge this edge backwards. Fig. 10 illustrates this operation, where all the vertices except v 4 are primary inputs/outputs. In the OBM algorithm, vertex v 5 is merged with its fanin vertex v 4 so that the new vertex v 5(4) represents also a primary output. All the weights of the fanin edges of v 4 are increased by d 45 . This weight increase guarantees that the delays from v 1 and v 2 to the output v 5 remain unchanged. The weights of the other fanout edges of v 4 are all decreased with d 45 so that the delays from the inputs to the outputs besides v 5 are also unchanged. Note that the graph in Fig. 10(b) can not be reduced further using the basic shrink operation because v 5(4) is already a primary output now and should be kept in the timing model. An application example of the OBM algorithm is the reduction of the sub-graph G{e 14 , e 24 , e 46 , e 48 } in Fig. 6(d).

Complete Algorithm
apply PIT/POT to the timing graph apply NCR algorithm to delete redundant vertices and edges visit each vertex vi starting from the inputs sequentially for sub-graph with vi and its fanin/out edges and vertices run the basic shrink operation to the sub-graph apply the output backward merge algorithm

Experimental Results
In this section the results of the application of the proposed method using the ISCAS85 benchmarks are shown. The algorithms are implemented in C++ and tested using a Pentium M 1.6GHz computer. The gates in the benchmarks are mapped to a library from an industrial partner. To model the impact of layout capacitance, the pin-to-pin delays of a gate are increased by 20% for each fanout. Interconnect delays are ignored for simplification. Table 1 shows the extraction results. m and n are the numbers of the inputs and outputs of the circuit. n eo and n vo are the numbers of the edges and vertices in the original timing graph G o . n er and n vr denote the numbers of the edges and vertices of the final timing graph G r after applying the complete reduction method proposed in this paper. p er and p vr are defined as n er /n eo and n vr /n vo to show the ratios of the edges and vertices before and after the application of the proposed method. T is the runtime of the proposed method. From Table 1 we can see that the proposed method compresses the timing graphs effectively.
According to [1] the benchmark c6288 is a 16×16 multiplier so that many critical paths are shared by different input to output pairs. This can explain why c6288 has the very drastic compression ratio. c499 and c1355 have the same circuit function, but all the XOR gates in c499 are expanded to NAND gates in c1355. This expansion increases the symmetry in the delay paths because smaller gates have better pin-to-pin delay symmetry than larger gates. This can explain why c1355 has a smaller timing model than c499.
For comparison we have implemented the serial/parallel method in [3]. Table. 1 shows the reduction results, where n es and n vs are the numbers of the edges and vertices in the resulted timing graph respectively. p es and p vs are defined as n es /n eo and n vs /n vo respectively. In [2] only the edge numbers of the reduction results are given, which are listed as n et in Table. 1. p t is defined as n et /n eo . Compared to our method, the method in [6] achieves slightly better edge compression ratios, but their resulting models involve error bounds and usually deviate from the original timing models. From these comparisons the efficiencies of the generated timing models by the proposed method are confirmed.

Conclusion
In this paper we proposed a method to effectively extract timing models for combinational circuits. After applying the primary input/output transformation and the non-critical edge/vertex removal algorithms, timing graphs are drastically compressed using the basic shrink operation recursively. Thereafter the primary output backward merge algorithm is applied to compress the timing graphs further. Compared to the original timing graphs, the numbers of edges and vertices of the resulting models are reduced by 84% and 85% on average, respectively. The extracted timing models have exactly the same delay matrix as their original timing graphs so that the accuracy of the high level arrival time propagation is maintained. The proposed method mainly focuses on the structural transformation of the original timing graph. Therefore, it can also be used as a pre-processing step before applying the method introduced in [2] and [6]. Future work will incorporate slope propagation and load effect into the timing model extraction.