Algorithm of global escape routing problem based on linear programming

Abstract

As a key part of PCB design, the ordered escape routing problem is a special NP-hard problem, which has been studied extensively in recent years. In the traditional method, both ILP method and the heuristic algorithms based on ripping-up and rerouting are only applicable to small-scaled pin arrays with fewer pins, which easily lead to time violation. Aiming at the difficulty of large-scale global routing in traditional methods, the iteration-driven method is proposed to solve the global escaping routing problem by linear programming (LP), and to optimize area congestion by reducing capacity. Compared with the latest work, this algorithm can not only escape all pins but also achieve up to 50% times speed up and save 31% wire length.

Keywords

• pcb design
• ordered escape routing
• lp
• congestion-driven