Patent ID: 6412102
Filing Date: 2002-06-25
Classification: G06F

Abstract:
A method for optimizing an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins, said method comprising:a dividing step of dividing the surface into a set of areas; a boundary pin defining step of defining a boundary pin at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net; a routing optimization step of independently performing a routing optimization in at least one of the areas, wherein the routing optimization optimizes the routing among the net pins and the boundary pins within said at least one of the areas; a shifting step of shifting the boundaries of the areas in order to obtain a second set of areas; a boundary pin eliminating step of eliminating the boundary pins defined in said boundary pin defining step; a second boundary pin defining step of defining a new boundary pin at each point on a boundary of one of the areas in the second set where the boundary of the one of the areas in the second set intersects a net; and a second routing optimization step of independently performing a second routing optimization in at least one of the areas in the second set, wherein the second routing optimization optimizes the routing among the net pins and the new boundary pins within said at least one of the areas in the second set, wherein each area in the set overlaps at least two areas in the second set, and wherein each area in the second set overlaps at least two areas in the set.