Network flow based module bottom surface metal pin assignment
US8261226B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 20, 2011 |
| Grant date | Sep 4, 2012 |
| Priority date | — |
| Expiry date | Jul 20, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2111/06
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A scaled network flow graph is constructed, including a plurality of nodes and a plurality of edges. The plurality of nodes correspond to: (i) a pseudo device pin node for each pair of corresponding paired device pins; (ii) a pseudo bottom surface metal node for each pair of bottom surface metal pins on each of multiple routing layers; (iii) a source node connected to each of the pseudo device pin nodes; (iv) a sub-sink node for each pair of the paired bottom surface metal pins (each of the sub-sink nodes is connected to corresponding ones of the pseudo bottom surface metal nodes for each of the pairs of bottom surface metal pins on each of the multiple routing layers); and (v) a sink node connected to the sub-sink nodes. A capacity and a cost are assigned to each of the edges of the scaled network flow graph. A min-cost-max-flow technique is applied to the scaled network flow graph with the assigned capacities and costs to obtain an optimal flow solution. The paired bottom surface metal pins are assigned to the corresponding paired device pins, and routing connections there-between are assigned, in accordance with the optimal flow solution. A technique for use in the absence of pa…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.