Method and system for providing a game theory based global routing

摘要

A system and method for global routing that includes receiving nets that need to be routed and capacity constraints, ordering, using processing circuitry, the nets, routing, using the processing circuitry, the nets based on a maze routing with framing method, determining, using the processing circuitry, whether the routing is congestion free, selecting, using the processing circuitry, a subset of the nets based on a game theory method when the routing is not congestion free, applying a rip-up and re-route process on the subset of the nets, and repeating the selecting and applying steps until the routing is congestion free.

主权项

1. A method for global routing, the method comprising:
receiving nets that need to be routed and capacity constraints of global routing cells; ordering, using processing circuitry, the nets as a function of an area bounded by pins of each net; routing, using the processing circuitry, the ordered nets by applying maze routing within a frame having a size as a function of the pins of a net and a first predetermined parameter; determining, using the processing circuitry, whether the routing is congestion free based on the capacity constraints of the global routing cells; selecting, using the processing circuitry, a subset of the nets based on a game theory method based on a probability of attempting to improve the spanning tree of the net when the routing is not congestion free, the probability being calculated as a function of a plurality of factors; applying, using the processing circuitry, a rip-up and re-route process on the subset of the nets; repeating the selecting and applying steps until the routing is congestion free; and implementing, using processing circuitry, a circuit based on the routing.