應用於印刷電路板之多組對連結演算法

Two-Terminal Nets Routing Algorithms on Printed Circuit Boards

郭芳誠(Fang-Cheng Kuo)

指導教授 ： 詹景裕

國立臺北大學/電機資訊學院/通訊工程研究所/碩士(2009年)

摘要

在超大型積體電路(VLSI)的實體設計(Physical Design)過程中，共可以區分為五大主要步驟：分割(Partitioning)、平面規劃與擺置 (Floor planning & Placement)、繞線(Routing)、壓縮(Compaction)以及最後的驗證(extraction & Verification)。而其中繞線的部份也一直是電子設計自動化(Electronic Design Automation)的主要研究議題，不論在超大型積體電路或是印刷電路板(PCB)的應用上，良好的繞線策略不但可以減少所的面積更可以大幅縮小線路的長度，以達到節省繞線成本及降低能源損耗的目的。
在印刷電路板的常見結構可以分為單層板（single Layer PCB）、雙層板（Double Layer PCB）和多層板（Multi Layer PCB）三種，其中單層板的繞線更可以延伸應用到雙層板及多層板的設計。因此針對已處理過分割、平面規劃與擺置後，進入到第三階段的各組節點對在單層的環境下進行多組對的繞線，而提出本文的快速單層多組對節點繞線演算法。
將先利用High Geometry Maze Router算出每對節點的繞線長度以及每對節點與其它線路之交叉數目加以排出先後順序，並依此循序連線，再輔以兩種重新調整先後順序的機制，提出快速單層多組對節點繞線演算法(Fast single-layer two-terminal nets routing algorithm)。而針對印刷電路板其元件有節點連續的特生，對於兩種常見的樣式，加以進行閃避的前置處理。最後統計出其所得的誤差值分別為0.56與0.64單位長度，且其時間複雜度為O(pN)、空間複雜度為O(N)，其中p為欲連結節點的組對線路數目，N為二維矩陣中節點的數目。

關鍵字

High Geometry Maze Router、印刷電路板、超大型積體電路實體設計、最短路徑演算法、單層多組對節點繞線演算法

並列摘要

In the physical design cycle for very large scale integration (VLSI), there is several stage should be discussed such as partitioning, floor planning & placement, routing, compaction, extraction & verification. The part of routing is one of the major issue should be discussed for Electronic Design Automation (EDA).A quality routing plan will reduce actual cost in area and total metal length for VLSI and Printed circuit board (PCB). There are three common architectures for PCB: single Layer, Double Layer PCB, and Multi Layer. Single Layer PCB is fundamental of the others.
In this article, we applied the lengths and number of intersections based on High Geometry Maze Router to find the order for each two-terminal net. The two reordering policy in the fast single-layer two-terminal nets routing algorithm to obtain a heuristic solution with reasonable lengths of nets. The space and time complexities are O(N) and O(pN), respectively, where N is the number of elements in the 2-D matrix and p is the number of two-terminal pairs. In order to avoid the continual terminals , we discuss two preprocess for observable pattern in PCB.

並列關鍵字

High Geometry Maze Router, Printed Circuit Board, Single-Layer Two-Terminal Nets Routing Algorithm, Shortest Path Algorithm, Very Large Scale Integration

參考文獻

[3] D. S. Chen and M. Sarrafzadeh, “A wire-length minimization algorithm for single-layer layouts,” IEEE/ACM International Conference on Computer- Aided Design, pp. 390-393, Nov. 1992.

[5] J. Fawcett and P. Robinson, “Adaptive Routing for Road Traffic,” IEEE Computer Graph, vol. 20, no. 3, pp. 46-53, June 2000.

[9] M.V. Lent, “Game Smarts,” IEEE Computer Society, vol. 40, Issue 4, pp. 99-101, Apr. 2007.

[10] C. E. Leiserson and R. Y. Pinter, “Optimal placement for river routing,” SIAM Journal of Computing, 12, No. 3: 447- 462, August 1983.

[12] M. Marek-Sadowska. and T. T. Trang, “Single-layer routing for VLSI: Analysis and algorithms,” IEEE Transactions on Computer-Aided Design, pages 246-259, October 1983.