客製化繞線模型與演算法

Abstract

今日的奈米科技技術使得積體電路與系統設計愈趨複雜。當封裝元件的尺寸不斷縮小，印刷電路板上的組件仍不斷增加，上千條訊號線與上百個元件被擺放在一個印刷電路板上成為常態。印刷電路板層級的繞線成為關鍵議題，必須利用自動化工具以完成設計。印刷電路板的繞線條件與限制與積體電路晶片內的繞線不同，訊號干擾、電源供應不穩、阻抗匹配等因素都必須考慮才能達成設計需求。除此之外，電路板繞線使用非直角連線，且偏好平面繞線。以上各種特性都使得電路板繞線必須仔細安排路徑形狀與長度。

除了印刷電路板設計，由於類比電路電路的效能對於實體佈局設計也相當敏感，設計早期對寄生效應與實體佈局相關影響的估計，對類比電路而言非常關鍵。因此，在電路合成階段與實體布局階段之間可快速交流資訊並據此調整的設計方法，較傳統的流程更符合需求。原型設計成為受歡迎而重要的設計方法。然而此方法需要快速而自動化的佈局產生器以達成不同設計階段間的資訊交流與效能估計，使得類比電路自動繞線成為必須的技術。

在這篇論文中，我們探討了印刷電路板與類比電路設計中的各種繞線問題，並針對其中三個繞線問題提出適合之模型與演算法。 針對印刷電路板區域繞線，我們提出了一個兩階段的繞線方法。根據電路板上組件的位置，計算適合的繞線順序並安排路徑。接者利用整數線性規劃調整每條訊號線的線長，以符合設計要求。針對印刷電路板上之逃脫繞線，我們提出之演算法可以同時考慮多個封裝元件的位置，並據此計算繞線路徑以避免不同封裝元件的訊號路徑彼此交錯。在類比電路繞線問題上，我們提出了一個以限制性Delaunay 三角化為基礎的繞線路徑特性抽取與保存技術。此路徑抽取與保存技術可將一個佈局上的繞線，在另一 個類似但不同的佈局上重新自動產生繞線。利用此技術，我們提出了一套類比電路原型設計流程，可在設計早期探索不同佈局的效能，達成原型設計的目的。

本論文中提出之三種客製化繞線演算法，其實驗結果皆展示了所提出方法的正確性與效率。

In today’s nanometer technology, IC design and system design become more complex. There are thousands of nets and hundreds of components on a printed circuit board while package dimensions keep shrinking. Board-level routing issues are more critical than before and are unable to do them manually. The conditions and constraints of boardlevel routing are different from on-chip signal routing. Crosstalk, IR drop, impedance matching must be considered to satisfy board routing requirement. Besides, board routing uses non-orthogonal paths and prefers planar paths. As a result, board routing must take net shape and net length into consideration.

In addition to board design, analog design performance is also sensitive to layout. Early estimation of parasitic and layout dependent effect is essential to analog design flow. Fast information exchange between schematic and layout design stages are desired instead of conventional one-pass flow. Design prototyping becomes a popular way to explore design performance. In design prototyping, multiple layout candidates are generated for early estimation of overall performance. However, these candidate layouts must be generated carefully such that it can demonstrate its own strength and weakness. Symmetry constraint, topology matching, and length matching all affect circuit performance. Similar to board-level routing, the needs of special constraint routing in analog design flow is more important than ever.

In this dissertation, we introduce the conditions and constraints in board-level routing and analog routing. We review routing approaches that have been used to solve these special constraint routing tasks. Novel routing models and algorithms are presented. A two stage routing method for board-level area routing is proposed to arrange routing paths among board components while considering min-max length constraint. A sequence-based approach is proposed to consider multiple component escaping problem. A routing path extraction and preservation technique based on constrained Delaunay triangulation (CDT) is proposed, which makes fast layout prototyping flow work.

In chapter 2, we focus on board-level area routing problem. A sequence based planar path search algorithm is presented. The algorithm selects cross-free nets from given nets, calculates a planar routing order, and form the routing paths on board. An ILP-based net length adjustment is then used to refine routing paths to mitigate length constraints while maintaining net shapes. Combined with the planar path searching and length adjustment, we propose a two stage routing approach to complete signal routing among board components while considering min-max length constraints. Experimental results show that the proposed approach uses routing resource effectively while min-max length constraints are satisfied.

In chapter 3, we discuss escape routing problem among multiple components. A sequence-based approach is presented to search planar routing solutions among multiple components. In the proposed approach, an escape order generation is first applied to generate a set of possible escape order candidates. A dynamic routing graph is designed for planar path finding among multiple components. By considering component positions, the proposed method can avoid possible crossings among nets belonging to different busses or components. Area routing topologies are also provided through the proposed method. Experimental results show that the proposed approach can produce feasible escape routing solutions for multiple components.

In chapter 4, we introduce the path topology extraction and preservation problem for analog design prototyping and migration. A constrained Delaunay triangulation (CDT) based routing topology extraction and preservation technique is proposed. For a given layout, the proposed method extracts routing topology and stored the extracted information on a CDT-based graph data structure called crossing graph. The extracted information can be reconstructed on a new placement. The path preservation technique is applied on layout reusing in analog layout prototyping and migration. Based on the preservation technique, a hierarchical layout prototyping/migration flow is presented. In the proposed flow, we generate placements using a slicing-based approach, and extract/reconstruct routing results using the proposed CDT preservation. The simulation results of the generated layout candidates is comparable with manual layout. The proposed automatic flow allows designer to fast explore design performance in circuit development.