Granted Patent B1

US 7,086,027 · App. 10/332,111 · Granted Aug 1, 2006

Abstract

Claims (29)

1. A method of compacting a circuit layout, the method comprising:

determining a critical path of the circuit layout, the critical path having a length not less than a length of each other path of the circuit layout;

representing the critical path to include a plurality of vertices and a plurality of edges, each one of the vertices being coupled to another of the vertices by an edge, the plurality of vertices including a flexible vertex corresponding to a flexible element of the circuit layout, the plurality of edges including a first shear edge;

representing the flexible vertex to include a first jogging edge; and

determining an optimal cutset of the graph of the critical path, the cutset including at least one of the group consisting of the first jogging edge and the first shear edge.

2. The method of claim 1 wherein the optimal cutset includes both the first jogging edge and the first shear edge.

3. The method of claim 1 further comprising:

reducing the length of the critical path by performing a jog insertion and a shear movement along the optimal cutset.

4. The method of claim 1 further comprising:

reducing the length of the critical path by performing at least one of the group consisting of a jog insertion at the first jogging edge of the flexible vertex and a shear movement at the first shear edge.

5. The method of claim 1 further comprising:

reducing the length of the critical path by performing a jog insertion at the first jogging edge of the flexible vertex and a shear movement at the first shear edge.

6. The method of claim 1 further comprising:

performing a one-dimensional compaction of the circuit layout in a first direction before determining the critical path; and

performing a one-dimensional compaction of the circuit layout in a second direction after performing the one-dimensional compaction in the first direction.

7. The method of claim 6 further comprising selecting the critical path in the first direction of the circuit layout.

8. The method of claim 1 wherein:

each vertex corresponds to a circuit element of the circuit layout; and

each edge defines a minimum space relationship between circuit elements corresponding to vertices to which each edge is coupled.

9. The method of claim 1 wherein

the flexible vertex is represented to further include a second jogging edge;

the optimal cutset is determined to include at least one of the first and second jogging edges and to include the shear edge.

10. The method of claim 9 wherein

the plurality of edges further includes a second shear edge; and

the optimal cutset is determined to include at least one of the first and second jogging edges and at least one of the first and second shear edges.

11. A computer program product encoded in computer readable media, the computer program product comprising:

first instructions, executable on a data processing system, for determining a critical path of a circuit layout;

second instructions, executable on the data processing system, for representing the critical path to include a plurality of vertices and a plurality of edges, each one of the plurality of vertices being coupled to another of the vertices by an edge, the plurality of vertices including a flexible vertex corresponding to a flexible element of the circuit layout, the plurality of edges including a first shear edge;

third instructions, executable on the data processing system, for representing the flexible vertex to include a first jogging edge; and fourth instructions, executable on the data processing system, for determining a optimal cutset of the graph of the critical path, the cutset including at least one of the group consisting of the first jogging edge and the first shear edge.

Assignments (8)