Method and apparatus for circuit partitioning and trace assignment in circuit design
US7237214B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 3, 2004 |
| Grant date | Jun 26, 2007 |
| Priority date | — |
| Expiry date | Apr 19, 2025 |
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.