A Detailed Routing Algorithm with Optimized Pin Mapping Strategy

A new multi layer area routing algorithm with optimized pin mapping strategy is presented. The algorithm can handle large routing problems,in which terminals and obstacles arbitrarily located in the routing area.Firstly,it divides each net into two-pin subnets according to their relative positions.Then, every subnet is routed in turn by an improved Maze algorithm.The routing conflicts are solved by rip-up and rerouting approach.An optimized pin mapping strategy is proposed as a pre-process before routing.The best matching of a bipartite graph is used to solve the pin-mapping problem.We tested our algorithm on a set of benchmark examples and compared our routing results with the results without pin-optimized mapping.Experimental results show that,the algorithm efficiently shortens the total wire length greatly and increases the routing completion rate.