标题: 客制化绕线模型与演算法
Models and Algorithms for Custom Routing Tasks
作者: 秦敬雨
陈宏明
Chin, Ching-Yu
Chen, Hung-Ming
电子研究所
关键字: 实体设计自动化;绕线;演算法;印刷电路板;类比电路布局原型设计;Physical Design Automation;Routing;Algorithm;Printed Circuit Board;Analog Layout Prototype
公开日期: 2017
摘要: 今日的奈米科技技术使得积体电路与系统设计愈趋复杂。当封装元件的尺寸不断缩小,印刷电路板上的组件仍不断增加,上千条讯号线与上百个元件被摆放在一个印刷电路板上成为常态。印刷电路板层级的绕线成为关键议题,必须利用自动化工具以完成设计。印刷电路板的绕线条件与限制与积体电路晶片内的绕线不同,讯号干扰、电源供应不稳、阻抗匹配等因素都必须考虑才能达成设计需求。除此之外,电路板绕线使用非直角连线,且偏好平面绕线。以上各种特性都使得电路板绕线必须仔细安排路径形状与长度。

除了印刷电路板设计,由于类比电路电路的效能对于实体布局设计也相当敏感,设计早期对寄生效应与实体布局相关影响的估计,对类比电路而言非常关键。因此,在电路合成阶段与实体布局阶段之间可快速交流资讯并据此调整的设计方法,较传统的流程更符合需求。原型设计成为受欢迎而重要的设计方法。然而此方法需要快速而自动化的布局产生器以达成不同设计阶段间的资讯交流与效能估计,使得类比电路自动绕线成为必须的技术。

在这篇论文中,我们探讨了印刷电路板与类比电路设计中的各种绕线问题,并针对其中三个绕线问题提出适合之模型与演算法。
针对印刷电路板区域绕线,我们提出了一个两阶段的绕线方法。根据电路板上组件的位置,计算适合的绕线顺序并安排路径。接者利用整数线性规划调整每条讯号线的线长,以符合设计要求。针对印刷电路板上之逃脱绕线,我们提出之演算法可以同时考虑多个封装元件的位置,并据此计算绕线路径以避免不同封装元件的讯号路径彼此交错。在类比电路绕线问题上,我们提出了一个以限制性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.
URI: http://etd.lib.nctu.edu.tw/cdrfb3/record/nctu/#GT079711616
http://hdl.handle.net/11536/142845
显示于类别:Thesis