Optimization of multiple performance criteria of integrated circuits by expanding a constraint graph with subgraphs derived from multiple PWL convex cost functions

Claim 2

In a computer aided design apparatus for defining a system, the apparatus including a database storing a structural description of the system, the structural description including a plurality of objects, each object having a binary relationship with at least one other object, a computer implemented method for optimizing at least one performance criteria of the system, where each performance criteria is described by at least one convex cost function, the method comprising: a) creating from the structural description of the system a constraint graph of the system, with each object in the structural description represented by a vertex in the constraint graph, and each binary relationship between two objects represented by an edge between the vertices representing the objects; b) for each edge of the constraint graph: i) associating a cost function with the edge according to the objects represented by the vertices coupled to the edge; ii) converting the cost function to a convex piecewise linear cost function approximating the cost function; c) minimizing the constraint graph by minimizing a total cost of all edges with the attached convex piecewise linear cost function on each edge; and, d) extracting a structural description of the system from the minimized constraint graph, wherein each performance criteria is optimized.

Claim 3

The computer implemented method of claim 1, wherein the cost function applied to an edge is a combination of a plurality of cost functions.

Claim 4

The computer implemented method of claim 1, wherein the cost function applied to an edge is a combination of a plurality of cost functions for a plurality of performance criteria.

Claim 5

The computer implemented method of claim 1, wherein the system is an electrical circuit, the objects are layout objects, and the binary relationship between two layout objects is a function of a distance between the two layout objects.

Claim 6

The computer implemented method of claim 4, wherein at least one cost function is selected from a group comprising: a) a yield cost function; b) a cross-talk cost function; c) a wire length cost function; and, d) a power consumption cost function.

Claim 7

The computer implemented method of claim 1, wherein each convex piecewise linear cost function has N segments, and N-1 transitions between segments, wherein minimizing the constraint graph comprises: a) for each edge coupling two vertices, expanding the constraint graph by replacing the edge with a subgraph having at least one edge for each of the N segments of the piecewise linear cost function and a vertex for each of the N-1 transitions between segments; and, b) minimizing the total cost of the edges of the expanded constraint graph using a network flow algorithm.

Claim 8

The computer implemented method of claim 6, wherein expanding the constraint graph by replacing the edge with a subgraph comprises: a) labeling the vertices coupling the edge as V N and V 0 ; b) for each of the i=1 to N-1 transitions of the piecewise linear cost function, each transition having a coordinate value x i+1 , storing a vertex V i in the constraint graph; c) for each vertex V i where i=1 to N, storing in the constraint graph a directed edge from vertex V i to vertex V i-1 , and storing for the edge a weight equal to (S i +k), where S 1 is the slope of a segment of the piecewise linear cost function starting at x i and k is an arbitrary number, and a constraint D min , where D min is 0 if i>1, and D min is x 1 where i=1; and, d) for each vertex V i where i=1 to N-1, storing in the constraint graph a directed edge from vertex V i-1 to vertex V i , and storing for the edge a weight equal to k and a constraint D min , where D min is (x i -x i+1 ) if i>1, and D min is -x 2 where i=1.

Claim 9

The computer implemented method of claim 6, wherein expanding the constraint graph by replacing the edge with a subgraph comprises: a) labeling the vertices coupling the edge as V N and V -1 ; b) for each of the i=1 to N-1 transitions of the piecewise linear cost function, each transition having a coordinate value x i+1 , storing a vertex V i in the constraint graph; c) storing a vertex V 0 ; d) for each vertex V i where i=1 to N storing in the constraint graph a directed edge from vertex V i to vertex V i-1 , and storing for the edge a weight equal to (S i +k), where S i is the slope of a segment of the piecewise linear cost function starting at x i and k is an arbitrary number, and a constraint D min equal to 0; e) storing an edge from vertex V 0 and vertex V -1 having a weight of any value and a constraint D min equal to x 1 ; f) storing an edge from vertex V -1 and vertex V 0 having a weight of any value and a constraint D min equal to -x 1 ; and, g) for each vertex V i where i=1 to N-1, storing in the constraint graph a directed edge from vertex V i-1 to vertex V i , and storing for the edge a weight equal to k and a constraint D min equal to (x i -x i+1 ).

Claim 10

The computer implemented method of claim 6, wherein expanding the constraint graph by replacing the edge with a subgraph comprises: a) labeling the vertices coupling the edge as V N and V -1 ; b) for each of the i=1 to N-1 transitions of the piecewise linear cost function, each transition having a coordinate value x i+1 , storing a vertex V i in the constraint graph; c) storing a vertex V 0 ; d) for each vertex V i where i=1 to N storing in the constraint graph a directed edge from vertex V i to vertex V i-1 , and storing for the edge a weight equal to (S i +k), where S i is the slope of a segment of the piecewise linear cost function starting at x i and k is an arbitrary number, and a constraint D min equal to 0; e) storing an edge from vertex V 0 and vertex V -1 having a weight equal to a substantially large value, and a constraint D min equal to x 1 ; and, f) for each vertex V i where i=1 to N-1 storing in the constraint graph a directed edge from vertex V i-1 to vertex V i , and storing for the edge a weight equal to k and a constraint D min equal to (x i -x i+1 ).

Claim 11

The computer implemented method of claim 6, wherein the network flow algorithm is a wire length minimization algorithm.

Claim 12

The computer implemented method of claim 1, wherein each cost function has the form: C(d)=Lαe.sup.-βd where: d is a distance between adjacent objects in the system in a first direction; L is length for which adjacent objects face each other in a second direction perpendicular to the first direction; α is first manufacturing technology dependent constant; and, β is a second manufacturing technology dependent constant.

Claim 13

In a computer aided design system for designing integrated circuits, computer memory including a constraint graph of an integrated circuit including a plurality of circuit elements, each circuit element having a binary relationship with at least one other circuit element, the memory readable by a processor in system for optimizing the placement of circuit elements as a function of at least one performance criteria cost model, the constraint graph in the computer memory comprising: a) a plurality of vertices, each vertex corresponding to at least one circuit element, each vertex having a weight; and, b) a plurality of edges, each edge coupling the vertices corresponding circuit elements having a binary relationship, each edge further including a convex piecewise linear cost function for at least one performance criteria cost model.

Claim 14

In a computer aided design system for designing integrated circuits, computer memory including a constraint graph of an integrated circuit including a plurality of circuit elements, each circuit element having a binary relationship with at least one other circuit element, the memory readable by a processor in system for optimizing the placement of circuit elements as a function of at least one performance criteria cost model, the constraint graph in the computer memory comprising: a) a plurality of vertices, each vertex corresponding to at least one circuit element, each vertex having a weight; and, b) a plurality of edges, each edge coupling the vertices corresponding circuit elements having a binary relationship, each edge further including a convex piecewise linear cost function for at least one performance criteria cost model.

Claim 15

A computer readable memory operable in a computer aided design apparatus for defining a system, the apparatus including a processor and a database storing a structural description of the system, the structural description including a plurality of objects, each object having a binary relationship with at least one other object, the computer readable memory comprising: a computer program for performing a computer implemented method for optimizing at least one performance criteria of the system, where each performance criteria is described by at least one convex cost function, the method comprising: a) creating from the structural description of the system a constraint graph of the system, with each object in the structural description represented by a vertex in the constraint graph, and each binary relationship between two objects represented by an edge between the vertices representing the objects; b) for each edge of the constraint graph: i) associating a cost function with the edge according to the objects represented by the vertices coupled to the edge; ii) converting the cost function to a convex piecewise linear cost function approximating the cost function; c) minimizing the constraint graph by minimizing a total cost of all edges with the attached convex piecewise linear cost function on each edge; and, d) extracting a structural description of the system from the minimized constraint graph, wherein each performance criteria is optimized.

Claim 16

A computer readable memory operable in a computer aided design apparatus for defining a system, the apparatus including a processor and a database storing a structural description of the system, the structural description including a plurality of objects, each object having a binary relationship with at least one other object, the computer readable memory comprising: a computer program for performing a computer implemented method for optimizing at least one performance criteria of the system, where each performance criteria is described by at least one convex cost function, the method comprising: a) creating from the structural description of the system a constraint graph of the system, with each object in the structural description represented by a vertex in the constraint graph, and each binary relationship between two objects represented by an edge between the vertices representing the objects; b) for each edge of the constraint graph: i) associating a cost function with the edge according to the objects represented by the vertices coupled to the edge; ii) converting the cost function to a convex piecewise linear cost function approximating the cost function; c) minimizing the constraint graph by minimizing a total cost of all edges with the attached convex piecewise linear cost function on each edge; and, d) extracting a structural description of the system from the minimized constraint graph, wherein each performance criteria is optimized.

Claim 17

In a computer aided design apparatus for defining a system, the apparatus including a database storing a structural description of the system, the structural description including a plurality of objects, each object having a binary relationship with at least one other object, each binary relationship having a cost that is determined by a convex cost function, a computer implemented method for optimizing the total costs of all binary relationships, comprising: approximating each convex cost function of the binary relationships with a piecewise linear cost function; transforming each piecewise linear cost function into a plurality of linear cost functions; and, solving the plurality of linear cost functions.

Claim 18

In a computer aided design apparatus for defining a system, the apparatus including a database storing a structural description of the system, the structural description including a plurality of objects, each object having a binary relationship with at least one other object, each binary relationship having a cost that is determined by a convex cost function, a computer implemented method for optimizing the total costs of all binary relationships, comprising: approximating each convex cost function of the binary relationships with a piecewise linear cost function; transforming each piecewise linear cost function into a plurality of linear cost functions; and, solving the plurality of linear cost functions.

Claim 19

A computer aided design apparatus for optimizing at least one performance criteria of an integrated circuit, comprising: a database storing a structural description of the integrated circuit, the structural description including a plurality of layout objects, each layout object having a binary relationship with at least one other layout object, each binary relationship having a cost as a function of a distance between the layout objects; a computer readable memory storing at least one convex cost function for each performance criteria; the computer readable memory further storing for execution by a processor: a compactor coupled to the database that creates from the structural description therein a constraint graph of the integrated circuit, with each layout object in the structural description represented by a vertex in the constraint graph, and each binary relationship between two layout objects represented by an edge between the vertices representing the objects, the compactor storing the constraint graph in the memory; a cost function module that associates with each edge of the constraint graph a cost function with the edge according to the layout objects represented by the vertices coupled to the edge; a piecewise linear cost function module that converts the cost function of each edge to a convex piecewise linear cost function approximating the cost function; and, a constraint graph minimizer that minimizes the constraint graph by minimizing a total cost of all edges with the attached convex piecewise linear cost function on each edge, and updates the structural description of the integrated circuit in the database.

Claim 20

A computer aided design apparatus for optimizing at least one performance criteria of an integrated circuit, comprising: a database storing a structural description of the integrated circuit, the structural description including a plurality of layout objects, each layout object having a binary relationship with at least one other layout object, each binary relationship having a cost as a function of a distance between the layout objects; a computer readable memory storing at least one convex cost function for each performance criteria; the computer readable memory further storing for execution by a processor: a compactor coupled to the database that creates from the structural description therein a constraint graph of the integrated circuit, with each layout object in the structural description represented by a vertex in the constraint graph, and each binary relationship between two layout objects represented by an edge between the vertices representing the objects, the compactor storing the constraint graph in the memory; a cost function module that associates with each edge of the constraint graph a cost function with the edge according to the layout objects represented by the vertices coupled to the edge; a piecewise linear cost function module that converts the cost function of each edge to a convex piecewise linear cost function approximating the cost function; and, a constraint graph minimizer that minimizes the constraint graph by minimizing a total cost of all edges with the attached convex piecewise linear cost function on each edge, and updates the structural description of the integrated circuit in the database.