Simultaneous Escape Routing using Network Flow Optimization

Abstract

With the advancement in technology, the size of electronic components and printed circuit boards (PCB) is becoming small while the pin count of each component is increasing. This has necessitated the use of ball grid array (BGA) type of components where pins are attached under the body of component as a grid. The problem of routing pins from under the body of component to the boundary of the component is known as escape routing. It is often desirable to perform ordered simultaneous escape routing (SER) to facilitate area routing and produce elegant PCB design. The task of SER is non-trivial, given the small size of components and hundreds of pins arranged in random order in each component that needs ordered connectivity. In this paper, first we propose flow models for different inter pin capacities. We then propose linear network flow optimization model that simultaneously solves the net ordering and net escape problem. The model routes maximum possible nets between two components of the PCB, by considering the design rules. Comparative analysis shows that the proposed optimization model performs better than the existing routing algorithms in terms of number of nets routed.