景東　范鑫湖　詹瑞典,2

學術研究

適用于平面多邊形區(qū)域的定阻值自動布線算法*

景東1范鑫湖1詹瑞典1,2

（1.廣東工業(yè)大學自動化學院，廣東 廣州 510006 2.佛山芯珠微電子有限公司，廣東 佛山 528000）

在柔性電路板和平板顯示器設計中，常需要將兩組對應的端口用多邊形導線連接起來，且每個端口的導線都有電阻約束。針對矩形布線區(qū)域，改進傳統(tǒng)的左邊算法，用垂直約束圖描述布線優(yōu)先級，采用三段式方法進行布線并根據電阻計算線寬；針對不規(guī)則的多邊形通道布線區(qū)域，采用剖分映射算法，將多邊形剖分后穿過剖分線進行布線，并根據電阻與線寬的反比例特點，利用迭代法求解線寬。為驗證該算法的有效性，對3個實際設計進行布線，成功布通全部端口對，實現了無人工干預的定阻值定區(qū)域布線。

定阻值布線；多邊形區(qū)域；端口對布線；左邊算法

0　引言

隨著電子技術的發(fā)展，柔性電路板（flexible printed circuit, FPC）和平板顯示器（flat panel display，FPD）廣泛應用于手機、筆記本電腦、數碼相機等產品。隨著用戶對屏占比的要求逐漸提高，電子產品留給布線的空間越來越少。定阻值定區(qū)域布線是FPC和FPD設計的一個重要研究課題。如何快速高效地在復雜形狀中布線是該課題的熱點和難點，原因主要有2方面：1）布線有最大阻值限定，每根導線都有規(guī)定的電阻范圍，以符合IC驅動芯片的負載規(guī)定；2）布線區(qū)域形狀復雜，既有規(guī)則的矩形，又有不規(guī)則的多邊形或者環(huán)狀通道，導致布線難度增加。

根據布線角度，當前主流的布線算法可分為曼哈頓互聯結構布線和非曼哈頓互聯結構布線2大類。其中，曼哈頓互聯結構布線算法只允許垂直和水平2種布線方向，通常不考慮電阻限制[1-3]，在矩形等規(guī)則布線區(qū)域有較好的布線效果和較低的設計復雜度，但此類算法需要離散的布線軌道和至少2個金屬層，且布線區(qū)域資源的利用率不高；非曼哈頓互聯結構布線算法允許45°、60°等特定角度的布線方向，目前處于理論研究階段[4-6]，僅有少量研究成果應用于印刷電路板的布線。韓奧等提出的算法一定程度解決了矩形區(qū)域的定阻值布線問題，但無法用于更復雜的多邊形區(qū)域[7]。

本文提出的改進左邊算法是一種適用于平面矩形區(qū)域的無軌道布線算法。該算法采用三段式布線技術，通過垂直約束圖確定端口對的布線優(yōu)先級，按照布線優(yōu)先級從上而下依次布線，只需一次迭代就可以完成布線；對于復雜的多邊形布線區(qū)域，本文提出的剖分映射算法利用多邊形剖分，將復雜多邊形內的布線問題簡化為穿過剖分線進行走線，使導線形狀與布線區(qū)域多邊形形狀基本一致，再根據電阻與線寬的反比例特性迭代求解導線在每一條剖分線上對應的線寬。

1　平面多邊形區(qū)域的定阻值布線算法

1.1 定阻值布線的左邊算法

左邊算法是解決通道布線問題的經典算法，該算法將通道（矩形布線區(qū)域）劃分為離散的布線軌道，求解每個端口使用的軌道長度和位置來進行布線[8]。為滿足FPC和FPD設計的電阻約束和其他設計規(guī)則，需要對導線寬度和形狀進行調整，因此不適合采用離散的布線軌道。本文改進的左邊算法不需要離散化的布線軌道，采用3個矩形描述導線多邊形，可直接在布線區(qū)域中進行布線。

首先，根據端口的寬度和位置信息求解垂直約束圖；然后，按照垂直約束圖的優(yōu)先級自上而下進行三段式布線；最后，根據三段式導線的特點生成導線的形狀并求解線寬。

改進的左邊算法生成的導線多邊形均由3個矩形構成，分別為橫向矩形、從橫向矩形到布線區(qū)域上邊界的縱向矩形、從橫向矩形到布線區(qū)域下邊界的縱向矩形。其中，難點在于確定橫向矩形的高度。左邊算法的三段式布線如圖1所示。

圖1 左邊算法的三段式布線

圖1中，黃色（0、1）矩形表示起始端口線段，位于在布線區(qū)域上邊界；藍色（0、1）矩形表示終止端口線段，位于布線區(qū)域下邊界；用斜線填充的矩形（0,0、0,2、1,0、1,2）是三段式中的縱向矩形；綠色（0,1、1,1）矩形表示三段式中的橫向矩形。端口對1的橫向矩形（1,1）必須高于端口對0的橫向矩形（0,1）才能保證不重疊地布通2個端口對。對于橫向矩形之間的高低關系，本文采用垂直約束圖來描述。

垂直約束定義為：假設是端口對兩端端口的橫坐標跨度，是端口對下邊界端口的橫坐標范圍。如果、集合存在交集，說明在的上方，那么有向邊從指向。垂直約束可用VCG(,)表示[9]，其中，為端口對的集合；為有向邊的集合，有向邊從高優(yōu)先級端口指向低優(yōu)先級端口。如圖1中，1與0在橫坐標上存在交集，因此有向邊從端口1指向端口0。

根據垂直約束圖從上到下的順序對端口對進行布線。在三段式導線中，2個縱向矩形的寬度采用盡可能寬的策略，相鄰端口對之間的間隔等于最小間距，靠近左右兩側的端口直接占滿兩側的剩余空間，即確定了兩個縱向矩形的寬度。橫向矩形的高度由左邊算法在布線過程中決定。高度確定后，三段式導線多邊形中只有橫向矩形的寬度未知，其寬度根據端口對的電阻約束可計算得出。

改進的左邊算法輸入為矩形點鏈、起始端口組、終止端口組；輸出為每個端口對的導線多邊形點鏈，布線步驟如下：

1）求垂直約束圖并提取最頂部的端口集合，將高度資源設置為布線區(qū)域高度。

2）根據自左向右的順序布通集合中的端口。首先，根據端口對的位置信息求出2個縱向導線線寬W,0和W,2；然后，結合求出2個縱向矩形的電阻以及橫向導線的電阻范圍；最后，根據橫向導線電阻計算橫向矩形W,1的線寬。

3）如果?W,1<布線區(qū)域下邊界，說明縱向資源不足，退出；否則，=h? W,1。

4）從垂直約束圖中刪除已布線端口，待所有端口成功布線則進行步驟5），否則從垂直約束圖中提取最頂端的端口更新集合，返回步驟2）。

5）微調導線多邊形，使其滿足物理設計規(guī)則，輸出每個端口對的導線多邊形點鏈。

1.2 剖分映射算法

采用剖分映射算法對不規(guī)則的多邊形通道區(qū)域進行定阻值自動布線。首先，對多邊形進行剖分，將不規(guī)則的多邊形通道區(qū)域盡可能剖分成規(guī)則的四邊形與三角形，同時得到一系列的剖分線；然后，根據剖分結果求解連接圖，確定每個端口對需要穿過的剖分線，并在穿過的剖分線上為該端口對分配一個長度為最小線寬的線段；最后，利用迭代法求解所有剖分線上的線段寬度。剖分映射算法的示意圖如圖2所示。

圖2 剖分映射算法示意圖

剖分映射算法的輸入為多邊形點鏈、起始端口組、終止端口組；輸出為每個端口對的導線多邊形點鏈，布線步驟如下：

1）在不規(guī)則多邊形的所有頂點處進行剖分，得到剖分線列表；

2）刪除剖分線列表中重復的剖分線，構成Z型和X型剖分線；

3）構造連通圖，求解每個端口對在連通圖中的路徑，即確定端口穿過的剖分線；

4）為所有端口對在其穿過的剖分線上分配線寬，寬度初始化為最小線寬；

5）選擇編號最小的不滿足電阻約束的端口對，生成導線多邊形并計算電阻；

6）根據式(4)調整線寬W,；

7）重復步驟5）直到所有端口滿足電阻約束或用盡寬度資源；

8）微調導線多邊形以滿足物理設計規(guī)則，輸出每個端口對的導線多邊形點鏈。

1.2.1 多邊形剖分

不規(guī)則多邊形布線的難點是導線需要拐彎，本文解決方法是分段布線。利用基于可見點的全局剖分算法[10]將不規(guī)則的布線區(qū)域劃分為四邊形或三角形，在剖分后的子圖形中進行分段布線。對于不規(guī)則多邊形的任一頂點來說，可見點定義為：多邊形中所有頂點與連線形成的線段，若全部在多邊形內部或者上面，這樣的頂點稱為可見點。若從頂點引出的剖分線正好是頂點夾角的平分線，此時多邊形剖分效果最好[11]。對不規(guī)則多邊形布線區(qū)域的所有頂點，計算該頂點的可見點與該頂點的角平分線向量之間的夾角，選取夾角最小的可見點與該頂點的連線作為剖分線。

1.2.2 初始布線

剖分后的不規(guī)則多邊形布線區(qū)域由一系列相鄰的三角形和四邊形組成。相鄰子圖形的公共邊為剖分線，這些子圖形與剖分線構成連通圖。連通圖的節(jié)點是剖分后得到的子圖形，邊為剖分線。圖2中，3個子圖形分別對應3個節(jié)點，2條剖分線為2個邊，連通圖如圖3所示。

對于不包含洞的布線區(qū)域，連通圖是一串依次相連的節(jié)點和邊，從s到e有且僅有一條路徑。當通道中存在障礙物或布線區(qū)域由多個子通道組成時，連通圖存在分支，導致有多條路徑可以從起始端口到達終止端口。將起始端口和終止端口所在的子圖形（連通圖中的節(jié)點）分別作為導線的起點和終點，采用左邊優(yōu)先的策略確定端口穿過的剖分線，并在穿過的剖分線上為該端口的導線分配一個長度為最小線寬的線段。將起始端口、終止端口以及在剖分線上分配的線段兩端串連起來即構成一個初始的布線結果。

圖3 圖2對應的連通圖

1.2.3 反比例線寬調整

在FPC和FPD設計中，每根導線都有規(guī)定的電阻范圍，前文僅考慮用最小線寬將端口對布通，為使導線電阻滿足電阻約束，需對線寬進行調整。由于剖分線上分配的線段僅由寬度來確定其具體位置，因此調整剖分線上的線段寬度會影響同一條剖分線上其他線段的位置，導致線段之間互相影響。并且由于線寬值是連續(xù)的，因此直接求解每條剖分線上所有線段的寬度是不現實的。本文利用迭代法在所有線寬均為最小線寬的基礎解上逐漸優(yōu)化解的質量。

分析端口對的設計約束可得到如下3個公式。

對于每條剖分線：

式中，為端口對的數量；W,為端口對在剖分線上分配的線段寬度；L為剖分線的總長度。

對于每段線寬：

min_width ≤ W,(2)

式中，為最小線寬。

目標函數，對每個端口對：

{(W,)?r|} (3)

式中，函數根據所有線寬W,計算端口對的導線電阻；r為端口對的目標電阻。

本文采用貪心策略，根據端口對的順序，依次調整每一個端口對的連線寬度，直到所有端口滿足電阻約束或用盡線寬資源。根據電阻與線寬成反比例的特點，線寬迭代的公式為

2　實驗結果

本算法利用C/C++語言在3.2 GHz CPU和8 GB RAM（Ubuntu 18.04系統(tǒng)）平臺上實現。用于驗證算法性能的3個設計及電阻計算函數，均來自2020年全國大學生集成電路創(chuàng)新創(chuàng)業(yè)大賽華大九天杯[12]。

設計1的布線區(qū)域為矩形，共19個端口對需要布線，起始端口均位于布線區(qū)域上邊界，終止端口均位于布線區(qū)域下邊界，應用左邊算法進行布線，布線結果如圖4所示。

圖4 設計1布線結果

設計2的布線區(qū)域為39個頂點描述的復雜多邊形，共有12個端口對需要布線，起始端口和終止端口分別位于布線區(qū)域的右上方和左下方，應用剖分映射算法進行布線，布線結果如圖5所示。

圖5中，端口對1違反電阻約束，因為該端口的目標電阻過小，導致用盡寬度資源也無法滿足其電阻約束。

設計3的布線區(qū)域是一個由147個頂點圍成的弧形通道，共13個端口對需要布線，起始端口位于布線區(qū)域上邊界，終止端口分布在布線區(qū)域左側邊界，應用剖分映射算法進行布線，布線結果如圖6所示。

由圖4～圖6可以看出：本文算法可最大化利用布線區(qū)域，3個布線結果均未出現大量空余布線區(qū)域。在圖5帶有拐角的布線區(qū)域和圖6近似弧形的布線區(qū)域中，剖分映射算法能夠沿著布線區(qū)域進行自動布線。

3個設計的屬性及布線結果的相關數據如表1所示。

圖5 設計2布線結果

圖6 設計3布線結果

表1 3個設計的屬性以及布線結果數據

從表1的數據可以看出，電阻計算是整個布線過程中耗時最多的部分，占總運行時間的98%以上，因此減少線寬求解時的迭代次數，能有效減少算法運行的時間。

3　結論

本文設計改進的左邊算法和剖分映射算法，應用于華大九天給出的3個實際工程設計，有效布通了全部端口，并且能充分利用布線空間。其中，改進的左邊算法相比文獻[7]更為簡潔，在同樣布通并且滿足設計約束的情況下，運行時間減少了61%。剖分映射算法中的初始布線能夠保證在復雜多邊形區(qū)域內以最小線寬布通端口對，在資源足夠的情況下可根據電阻約束調整線寬。剖分映射算法在拐角、近似弧形的多邊形區(qū)域中自動完成的布線結果證明了該算法具有一定的可行性。但本文算法也存在一些局限性：1）改進的左邊算法布線結果中，橫向矩形均為水平放置，可能導致該算法在高度資源緊缺且電阻約束小的設計中不能布通全部端口對；2）剖分映射算法在通道型布線區(qū)域布線效果較好，但是對于凸起的布線空間利用率有待提高。

[1] Akihiro Hashimoto, James Stevens. Wire routing by optimizing channel assignment within large apertures[J]. Proceedings of Design Automation Workshop, 1971(1):155-169.

[2] Deutsch, David N. A dogleg channel router[C]. Proceedings of Design Automation Conference: Association for Computing Machinery,1976.

[3] Yoshimura T, Kuh E S. Efficient algorithms for channel routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982,1(1):25-35.

[4] GREENBERG R I, SHIH JAU-DER. Single-layer channel routing and placement with single-sided nets[J]. Computers and Mathematics with Applications, 1996,32(4):1-7.

[5] 于永斌.基于冒泡排序的非曼哈頓通道布線問題中的串擾最小化研究[D].成都:電子科技大學,2004.

[6] Peter E. Hart, Nils J. Nilsson, Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968,4(2): 100-107.

[7]韓奧,趙振宇,劉國強,等.FPD平行端口矩形區(qū)域內電阻驅動的自動布線算法[J].計算機工程與科學,2021,43(6): 969-975.

[8] MURESAN V, WANG X , MURESAN V, et al. The left edge algorithm in block test scheduling under power constraints[C]. IEEE International Symposium on Circuits & Systems. IEEE, 2000.

[9] KAHNG A B, LIENIG J, MARKOV I L et al. VLSI physical design: from graph partitioning to timing closure[M]. Springer Netherlands, 2011.

[10] 金文華,饒上榮,唐衛(wèi)清,等.基于頂點可見性的凹多邊形快速凸分解算法[J].計算機研究與發(fā)展,1999(12):1455-1460.

[11] 朱傳敏,唐珺,許田貴.凹多邊形凸分解算法在快速原型中的應用[J].現代制造工程,2010(2):53-56.

[12] 全國大學生集成電路創(chuàng)新創(chuàng)業(yè)大賽.華大九天杯[EB/OL]. [2020.8.22].http://univ.ciciec.com/nd.jsp?id=240#_jcp=1.

A Resistance-driven Automatic Routing Algorithm for Planar Polygon Region

Jing Dong1Fan Xinhu1Zhan Ruidian1,2

(1. Guangdong University of Technology, School of Automation, Guangzhou 510006, China 2. Foshan Xinzhu Microelectronics Co., Ltd. Guangzhou 510006, China)

In the design of flexible circuit board and flat panel display, it is often necessary to connect two groups of corresponding ports with polygonal wires, and the wires of each port have resistance constraints. For the rectangular routing area, the traditional left algorithm is improved, the routing priority is described by vertical constraint graph, the three-stage method is used for routing, and the linewidth is calculated according to the resistance; For the irregular polygon channel routing area, the subdivision mapping algorithm is used to route the polygon through the subdivision line. According to the inverse proportion between resistance and linewidth, the linewidth is solved by iterative method. In order to verify the effectiveness of the algorithm, three actual designs are wired, all port pairs are successfully arranged, and the fixed resistance and fixed area wiring without manual intervention is realized.

fixed resistance routing; polygon region;port pairs routing; left algorithm

廣東省重點領域研發(fā)計劃項目（2019B010140002）

景東，男，1997年生，碩士研究生，主要研究方向：布局布線算法。E-mail: 2111904037@mail2.gdut.edu.cn

范鑫湖，男，1997年生，碩士研究生，主要研究方向：強化學習算法。E-mail: 1743568012@qq.com

詹瑞典，男，1991年生，碩士研究生，工程師，主要研究方向：IC設計、制造。E-mail: zhanruidian@chipeye.cn

TP303

A

1674-2605(2021)06-0004-06

10.3969/j.issn.1674-2605.2021.06.004