A dual model node based optimization algorithm for simultaneous escape routing in PCBs
Simultaneous Escape Routing (SER) is the escaping of circuit pins simultaneously from inside two or more pin arrays. This is comparatively difficult as compared to routing in a single array and has not been addressed by previous studies. The increase in pin array complexity has made the manual SER i...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
PeerJ Inc.
2021-04-01
|
| Series: | PeerJ Computer Science |
| Subjects: | |
| Online Access: | https://peerj.com/articles/cs-499.pdf |
| _version_ | 1819296868633411584 |
|---|---|
| author | Asad Ali Anjum Naveed Muhammad Zeeshan |
| author_facet | Asad Ali Anjum Naveed Muhammad Zeeshan |
| author_sort | Asad Ali |
| collection | DOAJ |
| description | Simultaneous Escape Routing (SER) is the escaping of circuit pins simultaneously from inside two or more pin arrays. This is comparatively difficult as compared to routing in a single array and has not been addressed by previous studies. The increase in pin array complexity has made the manual SER in PCBs a very inefficient and tedious task and there surely is need for the automated routing algorithms. In this work, we propose network flow based optimal algorithm that uses integer linear program to solve SER problem and area routing problem in two stages. In the first stage, pins are escaped to the boundaries of pin arrays simultaneously. These escaped pins are connected with each other in the second stage. The proposed algorithm is tested for different benchmark sizes of grids and the results show that it is not only better in terms of routability but also outperforms existing state of the art algorithms in terms of time consumption. The existing algorithms either fails to achieve higher routability or have larger time complexities, whereas the proposed algorithm achieves 99.9% routability and is also independent of grid topology and component pin arrangement, which shows the superiority of proposed algorithm over the existing algorithms. |
| first_indexed | 2024-12-24T05:04:57Z |
| format | Article |
| id | doaj.art-3f8f6304886b4e2281a9d7e7ad55bd3c |
| institution | Directory Open Access Journal |
| issn | 2376-5992 |
| language | English |
| last_indexed | 2024-12-24T05:04:57Z |
| publishDate | 2021-04-01 |
| publisher | PeerJ Inc. |
| record_format | Article |
| series | PeerJ Computer Science |
| spelling | doaj.art-3f8f6304886b4e2281a9d7e7ad55bd3c2022-12-21T17:13:50ZengPeerJ Inc.PeerJ Computer Science2376-59922021-04-017e49910.7717/peerj-cs.499A dual model node based optimization algorithm for simultaneous escape routing in PCBsAsad Ali0Anjum Naveed1Muhammad Zeeshan2National Chiao Tung University, Taiwan, TaiwanNational University of Sciences and Technology (NUST), Islamabad, PakistanNational University of Sciences and Technology (NUST), Islamabad, PakistanSimultaneous Escape Routing (SER) is the escaping of circuit pins simultaneously from inside two or more pin arrays. This is comparatively difficult as compared to routing in a single array and has not been addressed by previous studies. The increase in pin array complexity has made the manual SER in PCBs a very inefficient and tedious task and there surely is need for the automated routing algorithms. In this work, we propose network flow based optimal algorithm that uses integer linear program to solve SER problem and area routing problem in two stages. In the first stage, pins are escaped to the boundaries of pin arrays simultaneously. These escaped pins are connected with each other in the second stage. The proposed algorithm is tested for different benchmark sizes of grids and the results show that it is not only better in terms of routability but also outperforms existing state of the art algorithms in terms of time consumption. The existing algorithms either fails to achieve higher routability or have larger time complexities, whereas the proposed algorithm achieves 99.9% routability and is also independent of grid topology and component pin arrangement, which shows the superiority of proposed algorithm over the existing algorithms.https://peerj.com/articles/cs-499.pdfEscape routingPrinted Circuit Boards (PCB)Simultaneous escape routing (SER)Optimization |
| spellingShingle | Asad Ali Anjum Naveed Muhammad Zeeshan A dual model node based optimization algorithm for simultaneous escape routing in PCBs PeerJ Computer Science Escape routing Printed Circuit Boards (PCB) Simultaneous escape routing (SER) Optimization |
| title | A dual model node based optimization algorithm for simultaneous escape routing in PCBs |
| title_full | A dual model node based optimization algorithm for simultaneous escape routing in PCBs |
| title_fullStr | A dual model node based optimization algorithm for simultaneous escape routing in PCBs |
| title_full_unstemmed | A dual model node based optimization algorithm for simultaneous escape routing in PCBs |
| title_short | A dual model node based optimization algorithm for simultaneous escape routing in PCBs |
| title_sort | dual model node based optimization algorithm for simultaneous escape routing in pcbs |
| topic | Escape routing Printed Circuit Boards (PCB) Simultaneous escape routing (SER) Optimization |
| url | https://peerj.com/articles/cs-499.pdf |
| work_keys_str_mv | AT asadali adualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs AT anjumnaveed adualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs AT muhammadzeeshan adualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs AT asadali dualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs AT anjumnaveed dualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs AT muhammadzeeshan dualmodelnodebasedoptimizationalgorithmforsimultaneousescaperoutinginpcbs |