多層印刷電路板自動繞線問題之設計及解析

Design and Analysis of Multi-Layer Printed Ciucuit Board Problem

本文對印刷電路板繞線時會遇到的各種幾何與物理性質的問題做出分析與應對，將上述演算法擴展為兩個新的演算法，分別為多層多對節點連結演算法與含權重區間(Weighted Regions)之多層多對節點連結演算法，前者解決了單層多對節點連結演算法中會產生的繞死與連續型的節點無法完成繞線的問題。後者解決了完全屏蔽、降低密度與非佈線區的問題。幾何問題則是使用pins extension進行前處理，之後多層多對節點連結演算法使用Higher Geometry Maze Router演算法快速將各組對線路連結，藉由組對連結路線的交叉點數及長度與優先權排出優先序，使用分團覆蓋(Clique Cover)的概念進行初步分層，再降低印刷電路板多餘的層數與總線長，最後得到最佳化層數及優化的總線長。含權重區間之多層多對節點連結演算法則在多層多對節點連結演算法的基礎中針對物理特性限制再加入權重區間及優先值的概念，達到完全屏蔽敏感信號組對，降低組對間的佈線密度，與劃立非佈線區域三種功能。本文的兩個演算法時間複雜度皆為O(p2N)，空間複雜度皆為O(N)，其中p、N各為在平面自由空間中組對以及網格的總數。

"We proposed previously a fast single-layer two-terminal nets routing algorithm with time complexity of O(pN) and space complexity of O(N), where p is the number of two-terminal nets and N is the number of free nodes in the raster. The algorithm, a heuristic solution which performs reasonably well in the aspect of wire length, is based on prioritizing and reordering of the nets to be routed considering the number of intersections each net encounters and the total wire length. This article extends the above-mentioned algorithm to obtain two new algorithms: one is a sophisticated multi-layer two-terminal nets routing algorithm with the capability to optimize the number of layers and total wire length, and the other has the capacity to deal with physical constrains in PCB routing by creating weighted regions along the routing paths and priority modification. Both algorithms have the time complexity of O(p2N) and space complexity of O(N), where p is the number of two-terminal nets and N is the number of raster cells. The foundational multi-layer two-terminal nets routing algorithm first utilizes the Higher Geometry Maze Router algorithm to connect all nets, and then performs prioritized reordering of the nets before applying the concept of Clique Cover for initial layering. Finally, the number of layers is reduced and the total wire length is optimized. The algorithm with weighted region has great potential to cope with physical design problems commonly faced by PCB routing tools, such as shielding the paths of sensitive signals or dealing with keep out zones."