A dual model node based optimization algorithm for simultaneous escape routing in PCBs.

Area of Science:

• Electrical Engineering and Computer Science
• Integrated Circuit Design
• Printed Circuit Board (PCB) Layout

Background:

• Simultaneous Escape Routing (SER) involves simultaneously routing pins from multiple pin arrays, a complex task not adequately addressed by prior research.
• Increasing pin array complexity makes manual SER in PCBs inefficient and time-consuming, necessitating automated solutions.
• Existing routing algorithms often struggle with high routability or exhibit large time complexities.

Purpose of the Study:

• To develop an optimal, automated algorithm for solving the Simultaneous Escape Routing (SER) and area routing problems.
• To improve routability and reduce processing time compared to existing state-of-the-art algorithms.
• To provide a solution that is independent of grid topology and component pin arrangement.

Main Methods:

• A network flow-based optimal algorithm utilizing integer linear programming (ILP) was developed.
• The algorithm solves the SER problem in two stages: escaping pins to array boundaries and then connecting them.
• The approach was tested on various benchmark grid sizes.

Main Results:

• The proposed algorithm achieves 99.9% routability, surpassing existing methods.
• It demonstrates superior performance in terms of time consumption compared to current algorithms.
• The algorithm's independence from grid topology and component pin arrangement highlights its robustness.

Conclusions:

• The proposed network flow-based ILP algorithm effectively solves the complex SER problem.
• It offers significant improvements in both routability and efficiency for PCB design.
• This automated approach represents a superior alternative to existing methods for complex routing challenges.