Patent ID: 6915501
Filing Date: 2005-07-05
Classification: G06F,G11B

Abstract:
1. A method of routing nets within a particular region of a design layout, each net having a set of pins, the method comprising: a) partitioning the design region into a first set of sub-regions, wherein a plurality of inter-sub-region edges exist between the sub-regions, and wherein a plurality of the inter-sub-region edges are diagonal; b) for each particular net, identifying a set of routes, wherein each route in the route set identified for a particular net traverses a set of sub-regions containing the particular net's pins, wherein each route includes a set of route edges, and each route edge connects two sub-regions, and wherein routes are defined with respect to the inter-sub-region edges; c) formulating a linear-programming (“LP”) problem based on the identified routes, wherein formulating an LP problem includes using the identified routes to specify an objective function to optimize; and d) solving the LP problem to identify one route for each net.