Circuit simulation with improved circuit partitioning

One or more groups, into which a circuit simulator may partition an overall circuit, that are determined to belong to a feedback loop, also known as cycles, may be merged into a single group. The length of the loop, which is the number of groups in the loop, determines whether or not the groups of a loop will be merged into a single group. More particularly, loops of a length less than or equal to a number are merged. The number may be specified by the user, or otherwise determined. Once a merged group is formed, its inputs and outputs are determined, and it is treated like any other previously existing group. Preferably, not all the groups are merged into a single group.

TECHNICAL FIELD
 This invention relates to circuit simulators, and more particularly, to
 circuit simulators which partition the overall circuit into disjoint
 groups of components which are separately solved during the simulation
 process.
 BACKGROUND OF THE INVENTION
 It is well known in the art that it is desirable to simulate the operation
 of a circuit, e.g., to determine how the circuit will perform prior to
 physically building it. One prior art simulation technique develops a
 mathematical model to represent the circuit, which is then solved to
 indicate the operation of the circuit. This model is developed by entering
 into the circuit simulator a representation of the circuit, such as may be
 produced as the output of a schematic capture system, e.g. in the form of
 a netlist. The elements of a netlist generally correspond one to one with
 the schematic of the circuit to be simulated as it was input into the
 schematic capture system.
 Next, the overall circuit is partitioned into disjoint groups of components
 as a function of circuit connectivity as described in the netlist. When a
 circuit is partitioned for eventual simulation, the various resulting
 groups of components typically have many inputs and outputs, each of which
 connect to others of the groups, or are inputs or outputs of the overall
 circuit. For purposes herein, the term "group" includes either the
 components which result from a partition of the circuit, or a behavioral
 model of a circuit which is merely a software description of the operation
 of a circuit without being embodied in a particular circuit implementation
 of the behavioral model. It is possible that one or more feedback loops,
 also known as cycles, will be formed among the interconnected groups, a
 loop being a sequence of groups such that each group in the sequence has
 an output connected to an input of the next group in the sequence and the
 last group in the sequence has an output connected to an input of the
 first group in the sequence.
 The simulator has access to mathematical models for--i.e., equations and,
 if necessary, parameters representing--the devices included within the
 netlist, and, after partitioning, these models are employed to represent
 the individual devices. The resulting equations of groups are then
 separately solved during the simulation process. By solving each of the
 groups separately the computation burden of solving the circuit is
 reduced. Furthermore, this solution takes into account feedback within the
 group. Feedback among the groups is taken into account by circulating
 events, but such feedback cannot be solved in all cases.
 Note that the circuit simulator may be implemented by a computer with
 appropriate software. One such commercially available simulator is ATTSIM
 available from Lucent Technologies, Inc., the documentation of which is
 incorporated herein by reference.
 SUMMARY OF THE INVENTION
 We have recognized that, disadvantageously, the presence of feedback loops
 among the groups can result in either multiple re-evaluations of many
 groups, or worse, oscillation, preventing further simulation. Therefore,
 in accordance with the principles of the invention, groups which are
 determined to belong to a loop may be merged into a single group. The
 length of the loop, which is the number of groups in the loop, determines
 whether or not the groups of a loop will be merged into a single group.
 More particularly, loops of a length less than or equal to a number are
 merged. The number may be specified by the user, or otherwise determined.
 Once a merged group is formed, its inputs and outputs are determined, and
 it is treated like any other previously existing group. In other words,
 the equations for the merged group are derived from the components in the
 merged group just as for any originally existing group. Preferably, not
 all the groups are merged into a single group, which would eliminate the
 advantages of partitioning the circuit to simulating it.

DETAILED DESCRIPTION
 FIG. 1 shows an exemplary network of groups that results when an exemplary
 circuit (not shown) is initially partitioned for simulation. In FIG. 1,
 groups G1 through G10 are shown and they are connected by signals S1
 through S6, S75, S78 and S8 through S10.
 When a circuit is partitioned into groups for simulation, there are two
 types of feedback that may result. The first is feedback within a group,
 and the second is feedback among the groups. Typically, e.g., in ATTSIM,
 feedback within a group is handled during the iterative solution of the
 differential equations which represent the circuits within the group. This
 feedback is taken into account essentially by simultaneous solution of the
 appropriate equations. Feedback among the groups is taken into account by
 the technique of circulating events but such feedback cannot be solved in
 all cases.
 Feedback among the groups can arise because there is explicit feedback in
 the design, of which the designer is aware, or because of implicit
 feedback in the partitioned design, of which the designer is unaware. For
 example, a set-reset (S-R) latch built from two NAND gates has explicit
 feedback. If the NAND gates are built from MOSFETS, by default two groups
 will be created, with the output of each connected to an input of the
 other. Although a circuit designer may know about the internal feedback
 within an S-R latch, the designer may not be aware that the latch was
 partitioned into two cross-coupled groups. Similarly, if a large circuit
 has complicated behavior due to an effective internal state machine,
 partitioning may result in the creation of many groups, with there being
 feedback among the groups of which the circuit designer was not explicitly
 aware.
 In the present invention, loops, starting with the shortest, i.e., of
 length two, if any, are identified, and then increasingly longer loops are
 identified, up to some limit, which may be determined experimentally.
 Since long loops can arise when there is naturally occurring feedback in
 the design, it is often unnecessary to merge such long loops, since in the
 limit, the entire design would be merged into a single group, entirely
 defeating the purpose of partitioning. Also, note that, for purposes of
 the invention, self feedback, which is a loop of length one, which occurs
 when a group has an output connected to one of its own inputs, is not
 important, and is, therefore, ignored and treated as if it didn't exist.
 Identifying feedback among the groups is equivalent to finding loops of
 groups. A loop, also known as a cycle, is defined as a sequence of groups
 such that each group in the sequence has an output connected to an input
 of the next group in the sequence, and the last group in the sequence has
 an output connected to an input of the first group in the sequence. The
 number of groups in the sequence is the order or length of the loops. FIG.
 1 shows four loops: two of length 2, the first consisting of groups G2 and
 G3 and the second consisting of G9 and G10; one of length 3, consisting of
 G5, G6, and G7; and one of length 8, consisting of G1, G2, G3, G4, G5, G6,
 G7, and G8.
 In accordance with the principles of the invention, loops of increasing
 length, from two-group loops up to an n-group loop, where n is a
 parameter, are found. There be any number, including zero, of loops of any
 given length n. The groups forming a loop are then merged into a new
 group.
 The interconnection of groups by signals can be described as a graph, the
 so-called group graph. In a group graph the groups are the nodes of the
 graph, and there is an edge of the graph from group i to group j if there
 is at least one signal which connects an output pin of group i to an input
 pin of group j. Thus, the group graph is a directed graph. Edges which
 correspond to self feedback are omitted. As a result, the graph has no
 edges from any node to itself.
 FIG. 2 shows the corresponding group graph for the network of groups shown
 in FIG. 1. It is possible that one signal in the network gives rise to
 more than one edge in the graph. This occurs when a signal fans out to
 more than one group. For example signal S3 fans out to groups G4 and G2,
 thus giving rise to edges E34 and E32. For purposes herein, fanout from a
 group to itself group does not result in an edge in the graph from a node
 to itself.
 In accordance with an aspect of the invention, the group graph, in turn, is
 represented by a square adjacency matrix, A, which has one row and column
 for each group into which the circuit is currently partitioned. It has a
 non-null entry in row i, column j, if the corresponding graph has an edge
 from group i to group j. Thus, A.sub.ij is non-null if there is at least
 one signal from group i to group j. Because, as noted above, self feedback
 is ignored, A has no non-null diagonal elements. A is often a so-called
 "sparse matrix", since each group typically connects to only a few of the
 other groups. Table 1 shows the adjacency matrix for the sample group
 graph of FIG. 2.
 TABLE 1
 Adjacency matrix A for exemplary graph
 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
 G1 0 1 0 0 0 0 0 0 0 0
 G2 0 0 1 0 0 0 0 0 0 0
 G3 0 1 0 1 0 0 0 0 0 0
 G4 0 0 0 0 1 0 0 0 1 0
 G5 0 0 0 0 0 1 0 0 0 0
 G6 0 0 0 0 0 0 1 0 0 0
 G7 0 0 0 0 1 0 0 1 0 0
 G8 1 0 0 0 0 0 0 0 0 0
 G9 0 0 0 0 0 0 0 0 0 1
 G10 0 0 0 0 0 0 0 0 1 0
 The adjacency matrix, A, can be derived from an incidence matrix, M,
 defined as follows: M has one row, i, for each group and one column, j,
 for each signal in the circuit that is an input or an output of any group.
 M.sub.ij is+1 if signal j is an output of group i, -1 if signal j is an
 input to group i but not also an output, and 0 otherwise. Since as noted,
 each group typically connects to only a few of the other groups, matrix M,
 like the adjacency matrix A, is often a sparse matrix. Incidence matrix M
 can be derived directly from the input-output lists for each group, which
 are developed in a well known manner as part of the partitioning process.
 The adjacency matrix A may be developed by taking the product of the
 incidence matrix by its transpose, i.e., A=M.multidot.M.sup.T,
 alternatively written as, A.sub.ij =.SIGMA.M.sub.ik.multidot.M.sub.jk,
 where the non-commuting inner product operator is (+1).multidot.(-1)=1,
 other products being 0, and where 0+0=0, other sums being 1. To state the
 same in words, group i is adjacent to group j if there is at least one
 signal S.sub.k which is an output of group i, i.e., M.sub.ik =+1 and an
 input to group j, i.e., M.sub.jk =-1. That is to say, there is a path from
 group i to group j if there is at least one signal which is an output of
 group i and an input of group j. Table 2 is the incidence matrix M for the
 exemplary network of groups shown in FIG. 1. It can be shown that
 A=(M&gt;0).multidot.(M.sup.T &lt;0).
 TABLE 2
 Incidence Matrix M for exemplary graph
 S1 S2 S3 S4 S5 S6 S75 S78 S8 S9 S10
 G1 1 0 0 0 0 0 0 0 -1 0 0
 G2 -1 1 -1 0 0 0 0 0 0 0 0
 G3 0 -1 1 0 0 0 0 0 0 0 0
 G4 0 0 -1 1 0 0 0 0 0 0 0
 G5 0 0 0 -1 1 0 -1 0 0 0 0
 G6 0 0 0 0 -1 1 0 0 0 0 0
 G7 0 0 0 0 0 -1 1 1 0 0 0
 G8 0 0 0 0 0 0 0 -1 1 0 0
 G9 0 0 0 -1 0 0 0 0 0 1 -1
 G10 0 0 0 0 0 0 0 0 0 -1 1
 In accordance with an aspect of the invention, the diagonal elements of
 powers of the adjacency matrix A are used to identify loops. More
 specifically, the non-null diagonal elements of the matrix that are
 produced when matrix A is raised to a power indicate the existence of a
 path from group i to itself through one or more other groups, i.e., a
 loop, with a length equal to the power to which A is raised. For example,
 where the power is 2, the resulting matrix is A.sup.2. Since A.sub.ij is
 non-null when there is a path from group i to group j, the matrix A.sup.2
 has non-zero elements if there is a path from group i to group j through
 some intermediate group k. In other words, there is a group k such that
 some signal is an output of group i and an input to group k, and another
 signal which is an output of group k and an input to group j. If
 A.sup.2.sub.ij is non-null, there is a path from group i to itself through
 some group k, in other words, group i is in a loop of length two. Thus,
 the non-null diagonal elements of A.sup.2 identify loops of length two.
 In any circuit there may be more than one loop of length two. Subsets of
 the non-null diagonal elements identify disjoint loops of length two. To
 find the subsets of non-null diagonal elements it is necessary to save the
 contributions to the terms of the inner product when doing the
 multiplication of A by itself to find A.sup.2. It is necessary to save the
 set of intermediate groups k on the path from i to j, and to identify
 paths having the same set of groups. This generalizes to higher powers of
 A. In a similar fashion, the non-null diagonal elements of higher powers
 of A correspond to longer loops.
 TABLE 3
 Square of Adjacency matrix for exemplary graph (A.sup.2)
 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
 G1 0 0 1 0 0 0 0 0 0 0
 G2 0 1 0 1 0 0 0 0 0 0
 G3 0 0 1 0 1 0 0 0 1 0
 G4 0 0 0 0 0 1 0 0 0 1
 G5 0 0 0 0 0 0 1 0 0 0
 G6 0 0 0 0 1 0 0 1 0 0
 G7 1 0 0 0 0 1 0 0 0 0
 G8 0 1 0 0 0 0 0 0 0 0
 G9 0 0 0 0 0 0 0 0 1 0
 G10 0 0 0 0 0 0 0 0 0 1
 Table 3 shows the matrix A.sup.2 for the exemplary network of groups shown
 in FIG. 1. The non-null diagonal elements of Table 3 are shown in bold.
 The terms of the inner product which gave rise to both A.sup.2.sub.2,2 and
 A.sup.2.sub.3,3 are G2, G3, while the terms which gave rise to both
 A.sup.2.sub.9,9 and A.sup.2.sub.10,10 are G9, G10. Hence G2 and G3 are in
 a loop of length two, and G9 and G10 are likewise in a separate loop of
 length two.
 Further higher powers of A are obtained by multiplying the previously
 obtained power of A by A again. Non-null diagonal elements of the higher
 powers indicate longer loops. For example, Table 4, which shows A.sup.3
 for the exemplary network of groups shown in FIG. 1, indicates the loop
 formed by G5, G6, and G7. The inner product terms giving rise to
 A.sup.3.sub.5,5 are A.sup.2.sub.5,7 and A.sub.7,5. Those for
 A.sup.3.sub.6,6 are A.sup.2.sub.6,5 and A.sup.2.sub.5,6 comes from
 A.sub.6,7.multidot.A.sub.7,5 yielding the same set of three groups).
 Similarly, the groups involved in the inner product yielding
 A.sup.3.sub.7,7 also reduce to the same loop. Hence there is only one loop
 of length three consisting of groups G5, G6, and G7. The formation of
 higher powers of A, including saving the terms of the inner products for
 the diagonal elements, is repeated until loops of the desired length are
 found. In no case can a loop be longer than the total number of groups.
 TABLE 4
 Square of Adjacency matrix for exemplary graph (A.sup.3)
 G1 G2 G3 G4 G5 G6 G7 G8 G9 G10
 G1 0 1 0 1 0 0 0 0 0 0
 G2 0 0 1 0 1 0 0 0 1 0
 G3 0 1 0 1 0 1 0 0 0 1
 G4 0 0 0 0 0 0 1 0 1 0
 G5 0 0 0 0 1 0 0 1 0 0
 G6 1 0 0 0 0 1 0 0 0 0
 G7 0 1 0 0 0 0 1 0 0 0
 G8 0 0 1 0 0 0 0 0 0 0
 G9 0 0 0 0 0 0 0 0 0 1
 G10 0 0 0 0 0 0 0 0 1 0
 In the event that a group appears in more than one subset of groups
 corresponding to the terms of the inner product from which a non-null
 diagonal element of a power of A was formed, this indicates that the group
 is part of more than one loop of the same length. In such a case, the
 various separate subsets of groups for each of the loops in which the
 common group appears are replaced by a single group having as its members
 the union of the groups corresponding to the subsets of groups in which
 the common group appears. For example, if there exists two loops of length
 three, one including groups A, B, and C, the other including groups A, D,
 and E, then when groups of length three are determined a union will be
 formed of all five groups A, B, C, D, and E. Subsequently, all the groups
 in the several loops of the same length that have a common group will be
 merged, as described hereinbelow.
 In accordance with the principles of the invention, after loops of the
 desired length are identified, the groups in each loop are merged into a
 single group. This operation has two parts: a) the elements in all of the
 groups in the loops have to be combined; and b) the boundary signals of
 the merged group are established, with their directions appropriately
 determined.
 Combining the elements of all groups on a loop is performed by taking the
 union of the elements of each of the groups to be merged.
 To determine the boundary signals, and the directions thereof, for the
 merged group first an initial set S, which is the union of boundary
 signals of all of the groups to be merged is developed, i.e., S={S.sub.k
 }. Next, each signal S.sub.k of set S is processed in turn.
 If signal S.sub.k connects to only groups in the set to be merged, i.e.,
 groups on the loop, and is an input to at least one and an output of at
 least one, then signal S.sub.k has become an internal signal of the merged
 group, i.e., it is not connected to any point outside the merged group.
 Therefore, signal S.sub.k is not a boundary signal of the merged group and
 it is removed from set S.
 If signal S.sub.k is not an output of any of the groups in the set to be
 merged, then signal S.sub.k is designated as an input of the merged group.
 Otherwise, if signal S.sub.k connects to a group not on the loop, or to a
 behavioral model, then signal S.sub.k is designated as an output of the
 merged group. Note that this is because such a signal S.sub.k cannot be an
 input of the merged group since it was an output of one of the groups
 being merged, and therefore could not have also been an output of any
 other group or model.
 After detecting and eliminating loops of length two, the group graph of the
 exemplary network of FIG. 1 is shown in FIG. 3. Note that the signals
 corresponding to edges E23, E32, E109, and E910, which were edges in the
 group graph of FIG. 2 for the fully partitioned network of FIG. 1 have, in
 FIG. 3, become internal to their respective merged groups. Signal S1
 corresponding to edge E12 has been designated an input to merged group
 G2/G3 and signal S4 corresponding to edge E49 has been designated an input
 to merged group G9/G10. Similarly, signal S3 corresponding to edge E34 has
 been designated an output of merged group G2/G3.
 Similarly, FIG. 4 shows the group graph of the exemplary network of FIG. 1
 after detection and elimination of both loops of length two and loops of
 length three. Likewise, FIG. 5 shows the group graph of the exemplary
 network of FIG. 1 after all loops have been removed.
 In one embodiment of the invention, the matrix operations described above
 are not performed using any standard or sparse matrix package. Instead,
 the adjacency matrix A, and its powers, A.sup.n, are represented by a list
 of their rows, which consist of lists of group identifiers, e.g.,
 represented by pointers, which correspond to their non-empty columns. In
 other words, each row of the nth power of the adjacency matrix is the list
 of groups reachable from each group in n-steps. The inner products are
 performed by employing nested for loops, with implicit indexing controlled
 by comparison of group pointers. A union operation is used to identify
 loops corresponding to common subsets of groups of each given length. Only
 the original adjacency matrix, A, and the current power are retained. Each
 subsequent power is obtained from the previous power by adding the
 additional groups reachable by one additional edge of the original
 adjacency matrix; this corresponds to multiplication by adjacency matrix
 A. The subsets of common groups on a loop are accumulated only when
 computing the diagonal elements of each new power.
 Some possible policies for applying feedback elimination are: 1) remove all
 loops up to a fixed length; 2) remove only all instances of the shortest
 loops; or 3) remove all loops, which, as noted above, may negate the
 benefits of partitioning.
 FIG. 6 shows a generalized flow chart of a process for implementing the
 foregoing in an exemplary manner. The process begins in step 601 when the
 simulator is activated to simulate a circuit. Next, in step 603, the
 circuit, e.g., its netlist, is loaded into the circuit simulator.
 Thereafter, the partitioning of the circuit in the conventional manner is
 performed in step 605.
 The process then undertakes to identify the loops that exist among the
 groups. To this end, in step 607, the incidence matrix M is derived from
 the group input/output lists which were developed as part of the
 partitioning process, and, in step 609, the adjacency matrix A is derived
 from the incidence matrix M by computing A=M.multidot.M.sup.T.
 Next, the loops of groups which resulted from the partitioning process and
 having a length of less than or equal to N, a predetermined number, e.g.,
 selected by the user, are merged. To this end, the value of a variable n,
 which determines the loop length that is currently being processed, is
 initialized to two, in step 611. Then, in step 613, the nth power of A is
 determined, e.g., by computing A.sup.n =A.sup.n-1.multidot.A. The non-null
 diagonal elements of A.sup.n, which indicate groups within loops of length
 n, and which particular groups belong to which particular loops, if any,
 are identified in step 615. In other words, the subsets of groups that
 give rise to non-zero diagonal elements of A.sup.n are identified. If
 there are two or more loops that have a group that is common to those
 loops, i.e., a contribution is made by such a group to a non-zero diagonal
 element that belongs to the subsets identifying such loops, then all the
 groups of those loops will be identified as part of a single subset of
 groups.
 Thereafter, conditional branch point 617 tests to determine if n&lt;N. If
 the test result in step 617 is YES, control passes to step 619, in which n
 is incremented. Control then passes to conditional branch point 621, which
 tests to determine if n&lt;G, where G is the number of groups produced as
 a result of the original partitioning of the circuit. If the test result
 in step 621 is YES, indicating that greater length loops may still be
 found, control passes back to step 613, and the process continues as
 described above.
 If the test result in step 617 is NO, or the test result in step 621 is NO,
 which indicates that all the loops of groups from the original
 partitioning which have a length of less than or equal to the lesser of G
 or N have been identified, control passes to step 623 to begin the process
 of merging the groups of each loop into a single group. More specifically,
 in step 623, unique subsets of groups which are part of a particular loop
 and correspond to the non-null diagonal elements of A.sup.n accumulated in
 step 615 are identified. Next, the elements of the identified groups are
 merged, which is achieved by: a) combining the elements of the identified
 groups on the loop in step 625; and then b) determining the group boundary
 signals, and their appropriate direction; in step 627. Conditional branch
 point 629 tests to determine if there remain any unique subset of groups
 that correspond to a loop that have not yet been processed. If the test
 result in step 629 is YES, control passes back to step 623 to process the
 groups on the next as-yet-unprocessed loop. If the test result in step 629
 is NO, control passes to step 631, in which the circuit is simulated as it
 is currently partitioned into groups, which may include original groups as
 well as merged groups. The process then exits in step 633.
 The foregoing merely illustrates the principles of the inventions. It will
 thus be appreciated that those skilled in the art will be able to devise
 various arrangements which, although not explicitly described or shown
 herein, embody the principles of the invention and are included within its
 spirit and scope.