Patent ID: 8261226

Claim:
A method for assigning bottom surface metal pins to corresponding device pins on at least one outside device, using multiple routing layers, and without pairing constraints, said method comprising the steps of: constructing a network flow graph comprising a plurality of nodes and a plurality of edges, said plurality of nodes corresponding to: a device pin node for each of said corresponding device pins: a node for each of said bottom surface metal pins on each of said multiple routing layers; a source node connected to each of said device pin nodes; a sub-sink node for each of said bottom surface metal pins, each of said sub-sink nodes being connected to corresponding ones of said nodes for each of said bottom surface metal pins on each of said multiple routing layers; and a sink node connected to said sub-sink nodes; assigning a capacity and a cost to each of said edges of said network flow graph; applying a min-cost-max-flow technique to said network flow graph with said assigned capacities and costs to obtain an optimal flow solution; and assigning said bottom surface metal pins to said corresponding device pins, and routing connections there-between, in accordance with said optimal flow solution.