| 摘要 |
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 pairing constraints is also provided, as is a pin-pairing technique. |
