Method and apparatus for circuit partitioning and trace assignment in circuit design
US8176452B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 9, 2010 |
| Grant date | May 8, 2012 |
| Priority date | — |
| Expiry date | Nov 9, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/394
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods and apparatuses for incremental circuit partitioning and incremental trace assignment. In one embodiment of the present invention, a cost function based on both the partitioning solution and the trace assignment solution is used for the partitioning of a circuit; in reducing the cost function, blocks of circuits are moved among partitions and the trace assignment are updated accordingly to evaluate the cost function. In one embodiment, the traces and nets are grouped according to the partitions they connect for trace assignment. In one embodiment, a flow diagram is constructed for assigning nets to traces; and, maximum flow algorithms are used. In one embodiment, a flow diagram includes feedthrough solutions, in which flow conservation is not preserved at certain nodes. In one embodiment, integer linear programming techniques are used for assigning nets to traces. In one embodiment, a distribution of nets, which defines the numbers of blocks that each net has in each partition, is computed and maintained for efficient determination of the number of nets in net groups.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.