Abstract:
A method and a system for selecting timing points in an electrical interconnect network to be used in electrical simulations for a static timing analysis for improved accuracy. The present method includes discovering choke points in an electrical model of the interconnect for which all the paths from drivers to receivers must pass through on certain types of nets. The method then uses the choke point electrical nodes, where they exist, as an output timing point of the logic gate driving the net. The method solves the problem of inaccuracies due to resistances between different driver pins on the same interconnect net, though it can also be applied to solving analogous inaccuracies due to resistances between different receiver pins associated with the same receiver timing point. It further also applies to interconnect with other two-port parasitic elements, to cases where only a subset of receiver pins on the net require accurate timing, and to cases where a set of electrical nodes, rather than a single node, partition all paths from drivers to receivers on a net.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to the field of Electronic Design Automation, and, more particularly, to a method and a system for performing a static timing analysis on digital transistor circuits using embedded simulation. 
       BACKGROUND 
       [0002]    For many years, the performance of digital machine designs has been evaluated by performing static timing analysis on the designs. Timing analysis is a design automation tool which provides an alternative to the hardware debugging of timing problems. The program is intended to establish whether all the paths within the design meet stated predetermined timing criteria, i.e., whether data signals arrive at storage elements early enough for a valid capture, but not so early as to cause premature capture. 
       Propagation Segments, Timing Points, and Timing Graph: 
       [0003]    Static timing analysis (STA) of digital systems has been used for decades to analyze the performance of digital designs. When performing an STA, elements of the design which can delay signals, such as logic gates, wires, and combinations thereof, are represented by propagation segments, also referred to as ‘psegs’, and which represent the delays of the elements. The prior art includes systems where delays are preferably determined by circuit simulations, as well as systems where delays are computed by various approximations to a simulated result. Each pseg includes two timing points, a “from” timing point representing an input to the delay element and a “to” timing point representing an output of the delay element. The timing graph of the design as a whole includes a full set of all the timing points and psegs of all logic gates, wires, and other delay elements in the design. 
         [0004]    One conventional formulation of analysis partitions delays of the system into logic gate delays and interconnect delays, which are represented by propagation segments. An example thereof is shown in the relationship between an example of a combinational network, shown in  FIG. 1  and a corresponding example of the formulation of a timing model shown in  FIG. 2 . For example, the delays of the NAND logic gate g 4  in  FIG. 1  are represented by three propagation segments shown in  FIG. 2  from g 4 _i 1  to g 4 _o, from g 4 _i 2  to g 4 _o, and from g 4 _i 3  to g 4 _o, referred to as an input to output to input or net/gate/net timing model. 
       Transistor Pins, Drivers, Receivers, Nets, Electrical Nodes 
       [0005]    The representation generally views the output of a logic gate as a single point in the timing graph. Electrically, however, the logic gates consist of many transistors with many output electrical nodes. For example, referring to  FIG. 3A , the inverter g 1  and its input and output timing points g 1 _i and g 1 _o represent an approximate view of the electrical system shown in  FIG. 3B . Herein, timing point g 1 _i can represent either of electrical nodes c or d, the gates of transistors p 1  or n 1 , respectively. Similarly, timing point g 1 _o can represent either of electrical nodes e or g, the drains of transistors p 1  or n 1 , respectively. A transistor pin can refer to a transistor gate, source, or drain. At the electrical circuit level of representation, each transistor pin is an electrical node in the circuit. Other electrical nodes in the circuit, such as a, b, f, or h, in  FIG. 3B  can be connected to other electrical elements, such as the resistors shown. A logical net is all the electrical nodes connected by resistors (or inductors), such as e, f, g, and h ( FIG. 3B ) and all the electrical elements interconnecting them. They represent one interconnect net at the electrical level. Alternatively, an interconnect net is the set of all the electrical nodes having DC connections and which will reach very similar voltages, if the circuit is operated slowly. 
         [0006]      FIG. 4  illustrates in more detail gates g 4 , g 5 , g 6 , and g 7  and the interconnect net between them. Shown is a resistive interconnect network linking electrical nodes a, b, c, d, e, f, g, h, i, j, k, l, and m, showing an example of an interconnect net to which the invention applies. Gate g 4  is the driver of the interconnect net, and gates g 5 , g 6 , and g 7  are receivers of the net. The output of gate g 4  and the inputs of gates g 5 , g 6 , and g 7  are logical ports of the net, i.e., places through which logic signals travel. Two of the logical ports include several electrical nodes. The driving logical port of the net, i.e., the output of gate g 4  contains electrical nodes a, b, c, and d. One of the receiving logical ports of the net, the input to gate g 7 , includes electrical nodes l and m. It is possible for a logical port on a net to contain only a single electrical node. The input to gate g 5  illustrates this possibility in the figure, and shows a receiving logical port consisting of only the single electrical node j. 
         [0007]    Transistor pins which can pull the voltage of an interconnect net up or down (channel pins—either sources or drains) are considered driver pins, since they drive a logical signal into the net. Transistor gate pins sensing the voltage on an electrical node of an interconnect net are considered receiver pins, since they receive a logical signal from the net. At a coarser level of analysis, the logic gate inputs are also receivers on the nets to which they are connected, and logic gate outputs are also drivers on the nets to which they are connected. Additional drivers and receivers exist on nets at the boundary of the system under analysis. An input to the system under analysis (i.e., a primary input or PI) is a driver of the interconnect net that it is on. An output of the system under analysis (i.e., a primary output or PO) is a receiver of the interconnect net that it is on. 
         [0008]    In an STA with an embedded simulator, the delay through a pseg is measured by applying a voltage waveform at an electrical node chosen as representing the “from” timing point of the pseg and measuring the voltage that the circuit simulation produced at an electrical node chosen to represent the “to” timing point of the pseg. More generally, the voltage applied to the “from” end may be applied to several electrical nodes. 
         [0009]    Typically, one of the transistor pins is selected as “the” output timing point for a logic gate, resulting in numerical inaccuracies in the calculation of system delays through both the logic gate and the interconnect that it drives. A simplified example of the source of the inaccuracy is shown with reference to  FIG. 5 . Therein, an inverter consisting of pFET p 1  and nFET n 1  drives a net comprising electrical nodes b, c, and d and resistors r 1  and r 2 . An example of the inaccuracy can occur if node b, the drain of pFET p 1 , is chosen to represent the output of the inverter. Considering the case of a rising input propagating through the inverter, the bulk of the electrical effect of the inverter on the output net is produced by nFET n 1 . The delay from the input of the inverter to its output is measured from electrical node a, through the intrinsic delay of nFET n 1  (effectively to electrical node c, n 1 &#39;s drain), then backwards through r 1  to node b. The delay through the net is then calculated forwards from node b through r 1  (to node c) and through r 2  to the receiver node d. The total delay through the two psegs, both logic gate and net, therefore counts the delay through r 1  twice. Physically, however, the rising signal applied to the inverter input only needs to propagate through the nFET n 1  to electrical node c, n 1 &#39;s drain, then through r 2  to the receiver on electrical node d. This illustrates the primary prior art limitation. 
         [0010]    A second prior art formulation of the static timing analysis is a “simulate-to-sinks” approach or input to input approach. An example thereof is shown in the relationship between an example of a combinational network, shown in  FIG. 6A  and a corresponding example of a “simulate-to-sinks” timing model shown in  FIG. 6B .  FIG. 6A  illustrates logic gate g 4 , the interconnect net that gate g 4  drives, and receiver logic gates g 5 , g 6 , and g 7  on the net.  FIG. 6B  shows all the psegs derived from logic gate g 4  and the following interconnect net. The psegs extend from all the inputs of gate g 4 , timing points g 4 _i 1 , g 4 _i 2 , and g 4 _i 3  to all the receivers on the net it drives, timing points g 5 _i, g 6 _i, and g 7 _i. The second conventional approach avoids the inaccuracy due to resistances between the driving transistor pins of a logical net by including all of these pins within a single electrical simulation. The limitation of the methodology is that it increases the number of psegs needed. Generally, an M-input gate driving a net with N receivers needs M+N psegs to model it in the input-to-output-to-input approach, but M×N psegs in the input-to-input approach. 
       Biconnected Components and Articulation Vertices: 
       [0011]    A biconnected graph (or component in an undirected graph) is a set of vertices and edges such that every pair of vertices in the set has at least two disjoint paths between them. An articulation vertex is a vertex in an undirected graph whose removal breaks up the graph into disconnected pieces. Biconnected components cannot be broken up into disconnected pieces by removal of a single vertex. 
         [0012]      FIG. 7  illustrates what the partitioning of an undirected graph into biconnected components and articulation vertices does. The undirected graph with vertices a, b, c, d, e, f, g, h, i, j in  FIG. 7A  has only one vertex, c, which breaks the graph up into disconnected pieces if removed. The vertex is the sole articulation vertex for the graph. Splitting it up into two copies, c 1  and c 2 , yields the two biconnected components, a, b, c 1 , d, e, and c 2 , f, g, h, i, j shown in  FIG. 7B . 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0013]    The accompanying drawings, which are incorporated in and which constitute part of the specification, illustrate the presently preferred embodiments of the invention which, together with the general description given above and the detailed description of the preferred embodiments given below serve to explain the principles of the invention. 
           [0014]      FIG. 1  is an example of a prior art combinational network; 
           [0015]      FIG. 2  illustrates a prior art gate/net/gate pseg timing model; 
           [0016]      FIGS. 3   a - 3   b  show an example of the correspondence of a gate view and an electrical view of a conventional gate; 
           [0017]      FIG. 4  is an example of a prior art resistive interconnect network; 
           [0018]      FIG. 5  is an example of a prior art error source; 
           [0019]      FIGS. 6   a - 6   b  illustrate an example of a prior art simulate-to-sinks timing model; 
           [0020]      FIGS. 7   a - 7   b  depict an example of partitioning a prior art undirected graph into biconnected components and articulation vertices; 
           [0021]      FIG. 8  is a flowchart illustrating a choke point discovery, according to an embodiment of the present invention; 
           [0022]      FIG. 9  is an example of an augmented graph of an interconnect network, according to one embodiment of the invention; 
           [0023]      FIG. 10  is an example of partitioning an augmented graph of an interconnect network into biconnected components and articulation vertices, according to one embodiment of the invention; 
           [0024]      FIG. 11  illustrates an example of a network, where excluding a feedback inverter from the receivers enables selecting a choke point, according to one embodiment of the invention; 
           [0025]      FIG. 12  is a flowchart illustrating an implementation of the algorithm for bottleneck discovery, according to one embodiment of the invention; 
           [0026]      FIGS. 13   a - 13   b  show a graph of an interconnect network displaying a bottleneck, according to one embodiment of the invention; 
           [0027]      FIG. 14  shows an augmented graph of an interconnect network, according to one embodiment of the invention; and 
           [0028]      FIG. 15  is still another example of partitioning an augmented graph of an interconnect network into biconnected components and articulation vertices, according to one embodiment of the invention. 
       
    
    
     SUMMARY 
       [0029]    The objects, aspects and advantages of the invention are achieved by a method and a system for improving the accuracy of the static timing analysis in instances where there are resistances or other two-port parasitic elements between multiple transistor pins, and where certain topological criteria are true of the interconnect network. 
         [0030]    In one embodiment of the invention, the method selects timing points in static timing analysis in the presence of an interconnect by choosing the timing points from electrical nodes which, if removed, would separate all the driving electrical nodes on the logical network from all the receiving electrical nodes on the logical network. The “choke points” improve the accuracy of the delay calculation because all electrical effects of the output must funnel through the electrical node; therefore, choosing a choke point as the driver output timing point for a logic gate captures all the effects of any resistances between driver transistor pins. The existence of one or more electrical nodes meeting this condition is the topological criterion for the interconnect network which primarily determines the applicability of the inventive method. The embodiment, as described, applies not only to interconnect resistors, but also to interconnect electrical models containing any two-terminal parasitic elements between the driving transistor pins and the receiving transistor pins. Resistors, inductors, and coupling capacitors (though not grounded capacitors) can all be used as edges in the graph. 
         [0031]    In another embodiment, the invention chooses the choke point closest to the driver biconnected component along the path from the driver component to the receiver component. While any of the choke points along the path can be selected as a timing point, in order to improve accuracy, choosing the one closest to the driver component has the further advantage of keeping the partitioning of the delays between gate psegs and net psegs as close to the prior art as possible. 
         [0032]    In still another embodiment, the invention provides a method and system for separating driving electrical nodes from a relevant subset of receiving electrical nodes, in which the receiving nodes that are only used for feedback or which are irrelevant to the timing analysis, are excluded. 
         [0033]    In a further embodiment, the invention enables discovering interconnect net bottlenecks, sets of electrical nodes, rather than purely single nodes, which separate the net drivers from the receivers. Regarding the bottlenecks (not to be confused with choke points), in one embodiment, repeated searches are made for “choke points” in the interconnect network, interleaved with reducing the networks in ways that can create “choke points” (such as shorting resistors) in the event that none have yet been found. 
         [0034]    In still a further embodiment, the invention selects receiver timing points and improves the numerical accuracy of delay calculations to these points in the design. Furthermore, an analogous approach finds choke points between all the transistor pins which include one of the receiver timing points on a logical net and all the other transistor pins in the net. Alternatively, just as a numerically accurate timing point for the driver can be found by finding a choke point electrical node between all electrical driving nodes in the driver and all receiving electrical nodes on the net, one can similarly find a numerically accurate choke point electrical node for a particular receiver. This is achieved by finding a choke point electrical node between the receiver electrical nodes for the particular receiver and all other receiver or driver electrical nodes in the net. Thus, timing points for a logical port (either driver or receiver) are chosen from the electrical nodes which separate the logical port (and its electrical nodes) from all the other logical ports in the net (and corresponding electrical nodes). These points, wherever they exist, can be used to eliminate errors due to parasitic electrical elements between the transistor pins comprising a receiver timing point. 
         [0035]    In yet another embodiment, a method and a system are provided for selecting timing points in an electrical interconnect network to be used in electrical simulations used in a static timing analysis (STA) to improve the numerical accuracy of the STA, the method including: a) inputting the interconnect network and converting it into a graph; b) augmenting the graph by adding a set of edges to connect all the vertices of the selected logical port and another set of edges to connect all the vertices of all the other logical ports; c) partitioning the graph into biconnected components and articulation vertices; d) determining if the selected logical port&#39;s biconnected component is separate from the other ports&#39; biconnected component, and if the components are separate, then selecting an articulation vertex on a path from the first component to the second component as a timing point for the first component; and e) incorporating the selected articulation vertex into the selected port&#39;s timing point. 
       DETAILED DESCRIPTION 
       [0036]    Detailed embodiments of the present invention are disclosed herein. However, it is to be understood that the disclosed embodiments are merely illustrative of the invention that may be embodied in various forms. In addition, each of the examples given in connection with the various embodiments of the invention is intended to be illustrative, and not restrictive. 
         [0037]    In the following description, and for the purpose of explanation, specific details are set forth in order to provide a thorough understanding of various aspects of the invention. It will be apparent to those skilled in the art that the present invention may be practiced without those specific details. In other instances, well-known structures and devices are shown in block diagram to avoid unnecessarily obscuring the present invention. Therefore, specific structural and functional details disclosed herein are not to be interpreted as limiting, but merely as a representative basis for teaching one skilled in the art how to variously employ the present invention. 
         [0038]    In one embodiment, the inventive method improves the accuracy of the static timing analysis in cases where there are resistances between multiple transistor pins and where a topological condition to be described hereinafter holds for the interconnect network. Previous existing solutions pick a single transistor pin to represent, e.g., an output static timing point for a channel connected component (CCC), resulting in either optimistic or pessimistic errors in the timing analysis. 
         [0039]    Referring now to  FIG. 8 , a flow chart of one embodiment of the present invention is shown that illustrates some of the most important steps of the inventive method. 
         [0040]    Step  1000 : For a given logical signal net, capture the network as an undirected graph where the two-port parasitic elements are edges. The elements include resistances, inductances, coupling capacitances, wire models or any other two port electrical element. The electrical nodes in the interconnect electrical model are the vertices of the undirected graph. 
         [0041]    Step  1010 : Add additional edges to the undirected graph to connect all the driver transistor pins (or other drivers, such as logic gate outputs or system PIs). More specifically, it is only necessary to add edges between vertices where less than two disjoint paths between them already exist. One can similarly connect all the electrical nodes of a selected logical port. 
         [0042]    Step  1020 : Add additional edges to the undirected graph between receiver transistor pins (and other receivers, such as gate inputs) like those in step  1010 . One can similarly connect all the electrical nodes of all the other logical ports of the net. 
         [0043]    Step  1030 : Find the biconnected components and articulation vertices in the augmented undirected graph created in step  1020 . 
         [0044]    Step  1040 : Determine if the biconnected component containing the drivers of the net is the same as the biconnected component containing the receivers of the net. If the components are the same, the network is too heavily interconnected for the invention to apply, in which case, fallback to prior art techniques (Step  1060 ) is acceptable. One can similarly determine if the component for the selected logical port is the same as the component for all the other logical ports on the net. 
         [0045]    Step  1050 : Find the articulation vertex (the electrical node in the interconnect net) which is on the driver biconnected component and on the path from the driver component to the receiver component. Return the electrical node as the node to be used as the driver output timing point. One can similarly find the vertex in the path from the selected logical port&#39;s component to the other ports&#39; component and return it to be used as the selected port&#39;s timing point. 
         [0046]    Step  1060 : Select one of the logical port&#39;s transistor pins as the port&#39;s timing point. 
         [0047]    When the process is successful at finding a ‘choke point’ on an interconnect net, the choke point in the electrical simulations of the timing analysis is preferably used. Furthermore, when measuring the delay to this point, the delay from the usual voltage crossing (typically 50%) on the input of the driving CCC to the usual voltage crossing of the waveform at the choke point is measured. When measuring the delays from this point, the delay from the usual voltage crossing on the choke point, which is now the input of the interconnect net, to the usual voltage crossings of the receivers, i.e., the outputs of the interconnect net, are measured. 
         [0048]    Note that one does not want to simply break the unmodified graph of, e.g., resistors in an interconnect net up into articulation vertices and biconnected components. If the step were applied to, e.g., the interconnect shown in  FIG. 4 , one would find that, e.g., node e would be an articulation vertex, because removing it separates node a from the rest of the graph, leaving the partitioning too finely grained for the purposes of the invention, since the only interest of the articulation vertices is to separate all the drivers from all the receivers or, more generally, to separate the selected logical port from all the other logical ports. 
         [0049]      FIG. 9  shows the resistive network of  FIG. 4  after being converted to an undirected graph and augmented by additional edges between the drivers (e.g., where the driver port is the selected logical port), and by additional edges between the receivers. Alternatively, it is the product of steps  1000 ,  1010 , and  1020  operating on  FIG. 4 . The augmented edges are represented by thick double-headed arrows between nodes a and b, b and c, c and d, d and a on the driver side, and between j and k, k and l, l and m, and m and j on the receiver side. All remaining edges represent resistors of the original interconnect net. 
         [0050]      FIG. 10  shows the undirected graph after being broken into biconnected components. The driver component consists of a, b, c, d, e, f, g 1 , while the receiver component consists of i 2 , j, k, l, and m, leaving the two remaining components g 2 , h 1  and h 2 , i 1  between them, the product of step  1030  operating on  FIG. 9 . 
         [0051]    The driver component, a, b, c, d, e, f, g 1  differs from the receiver component i 2 , j, k, l, m so that step  1040  branches to step  1050 . Step  1050  finds that the vertex g 1  representing the electrical node g is the articulation vertex of the driver component along the path to the receiver component, the method of the present invention establishes that it becomes the electrical node to be used as the output timing point of the driving gate g 4 . 
         [0052]      FIG. 11  shows an example where an additional refinement to an embodiment of the invention is applied. In the discussion thus far, the choke point located separates all the drivers of the interconnect net from all the receivers of the net. The choke point can actually satisfy a weaker condition and still provide the accuracy improvement provided by the present invention. It suffices to separate the driver pins from the receiver pins which must be accurately simulated when simulating the propagation of a signal to the rest of the design. In the case of feedback structures, such as electrical node a driving inverter g 2 , which in turn drives back through the separate logical net feedback into transistor p 1 , becomes unnecessary. Instead, gate g 1  (transistors p 1 , p 2 , and n 1 ) can be simulated together with inverter g 2  as one block, including electrical node a as part of the simulation. Another way to view the combined simulation is to view logic gate g 1  as having been extended to include inverter g 2 , whose input a no longer needs to be considered as a receiver of net a, b, c, d, e, f. As a result of the combined simulation, electrical node a is no longer an input to the combined simulation, but is instead an internal node of the simulation. Since node a is no longer an input to a gate, it no longer requires timing information and no longer requires treatment as a receiver electrical node of the net. With the refinement, electrical node d now splits driving nodes c and d from the remaining receiver electrical nodes, e and f, and now acts as a choke point for the network. 
         [0053]    Generally, the receivers that can be omitted from the choke point analysis may include any type of feedback to the driving logic gate, NANDs, NORs, and inverters. It can also include receivers which are known to be irrelevant to the timing analysis for other reasons, such as being turned off during a normal system operation. 
         [0054]      FIG. 12  shows an extension of the choke point detection that covers a more general case where there is a bottleneck in the interconnect net but not a choke point in the original graph. Assuming that there is a small set of electrical nodes which, if they are removed from the network, separate all the drivers from all the receivers of the network, even if none of them individually separate the sets. In such an instance, there may be cases where using one of the nodes at the timing point, or shorting them and using the shorted electrical node as the timing point, are still more accurate than the prior art. The steps in the process include step  2000  that captures the logical interconnect net as an undirected graph; and step  2010  that applies the method of  FIG. 8  to the interconnect graph. 
         [0055]    If the attempt to find a choke point in the interconnect graph succeeds, reaching the return step  1050  ( FIG. 8 ), then the extended process also succeeds, proceeding through the Y branch of the decision block  2010  to the return step  2040 . If the attempt to find a choke point fails and reaches step  1060  ( FIG. 8 ), then, the process proceeds through the N branch of decision block  2010  to step  2020 . Step  2020  reduces the interconnect network, and finds the smallest resistor (or, alternatively, the interconnect element with the shortest time constant) in the network and shorts it. It combines the two electrical nodes on the two ends of the resistor, and combines in parallel the appropriate network elements from the nodes to the shared neighboring nodes. 
         [0056]    Decision block  2030  determines if the accumulated error of the partially shorted interconnect network is still acceptable. If too much error has accumulated, then the process follows the N branch to step  2050  and preferably falls back to using prior art by choosing an FET pin as the timing point. If the amount of error is still tolerable, then the process returns to step  2010  in an attempt to find a choke point in the partially shorted network. 
         [0057]      FIG. 13  shows an example of an interconnect network having a bottleneck and how the process shown in  FIG. 12  discovers the bottleneck. Network a, b, c, d, e, f in  FIG. 13A  connects drivers a and b with receivers e and f, but no single vertex can be removed to separate all the drivers from all the receivers, so the initial network does not include the choke point. The network will be processed with steps  2000  and  2010  of  FIG. 12 , following the N branch to step  2020 . Assume that the smallest resistor in the network is the one between nodes c and d. Step  2020  shorts the nodes, while keeping node c in the modified network in  FIG. 13B . Correspondingly, it converts the edge between b and d in  FIG. 13A  into an edge between b and c in  FIG. 13B . Similarly, the edge between c and e is combined with the one between d and e, yielding the edge between c and e in  FIG. 13B  and the same with the edges to f. If the resistance originally between c and d is found to be small, the error introduced by shorting will, likely, also be small. Then, decision block  2030  sends the modified network back to step  2010 . Since node c now separates all the drivers from all the receivers, it will successfully locate the new choke point at c, which represents the bottleneck at c and d in the original network. The process then proceeds to step  2040  and returns the result. 
         [0058]      FIG. 14  shows the resistive network of  FIG. 4  after being converted to an undirected graph and augmented by additional edges between the selected logical port and additional edges between all the vertices of the other logical ports. The selected logical port becomes an input of gate g 7 , a receiver in the net having electrical nodes l and m. The other logical ports are the driver, the output of gate g 4  with electrical nodes c and d, the input to gate g 5 , a separate receiver, with electrical node j, and the input to gate g 6 , another separate receiver, with electrical node k. Alternatively, it is the product of steps  1000 ,  1010 , and  1020  operating on  FIG. 4  in the case where the selected logical port is the input of gate g 7 . Augmentation edges are represented by thick double-headed arrows between nodes l and m on the selected logical port side, and between c and d, b and c, a and b, j and a, and k and j on the side with all the other logical ports. All the other edges represent resistors in the original interconnect net. 
         [0059]      FIG. 15  shows the undirected graph after being broken into biconnected components in the case where the selected logical port is the input of gate g 7 . The selected logical port component consists of l, m, and i 2 , while the component with all other ports consists of a, b, c, d, e, f, g, h, i 1 , j and k.  FIG. 15  shows the product of step  1030  operating on  FIG. 14 . 
         [0060]    Selected receiver component, l, m, i 2  differ from the other logical ports&#39; components a, b, c, d, e, f, g, h, i 1 , j, k, accordingly, step  1040  branches to step  1050 . In this case, step  1050  finds that the vertex i 2  representing the electrical node i is the articulation vertex on the selected receiver component on the path to the other logical ports&#39; component, the inventive method establishes that it becomes the electrical node to be used as the input timing point of the receiver logic gate g 7 . 
         [0061]    The present method achieves a numerically more accurate timing point at a driving gate&#39;s output when compared to the prior art input to output to input method while avoiding an excessive number of psegs generated by the prior art input to input method. 
         [0062]    The present invention can be realized in hardware, software, or a combination of hardware and software. The present invention can be realized in a centralized fashion in one computer system or in a distributed fashion where different elements are spread across several interconnected computer systems. Any kind of computer system—or other apparatus adapted for carrying out the methods described herein—is suitable. A typical combination of hardware and software could be a general purpose computer system with a computer program that, when being loaded and executed, controls the computer system such that it carries out the methods described herein. 
         [0063]    The present invention can also be embedded in a computer program product, which comprises all the features enabling the implementation of the methods described herein, and which—when loaded in a computer system—is able to carry out the methods. 
         [0064]    Computer program means or computer program in the present context mean any expression, in any language, code or notation, of a set of instructions intended to cause a system having an information processing capability to perform a particular function either directly or after conversion to another language, code or notation and/or reproduction in a different material form. 
         [0065]    While the present invention has been particularly described in conjunction of a simple illustrative embodiment, it is to be understood that one of ordinary skill in the art that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.