景東　范鑫湖　詹瑞典,2

學(xué)術(shù)研究

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

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

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

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

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

0　引言

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

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

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

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

1.1 定阻值布線的左邊算法

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

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

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

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

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

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

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

改進(jìn)的左邊算法輸入為矩形點(diǎn)鏈、起始端口組、終止端口組；輸出為每個(gè)端口對(duì)的導(dǎo)線多邊形點(diǎn)鏈，布線步驟如下：

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

2）根據(jù)自左向右的順序布通集合中的端口。首先，根據(jù)端口對(duì)的位置信息求出2個(gè)縱向?qū)Ь€線寬W,0和W,2；然后，結(jié)合求出2個(gè)縱向矩形的電阻以及橫向?qū)Ь€的電阻范圍；最后，根據(jù)橫向?qū)Ь€電阻計(jì)算橫向矩形W,1的線寬。

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

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

5）微調(diào)導(dǎo)線多邊形，使其滿足物理設(shè)計(jì)規(guī)則，輸出每個(gè)端口對(duì)的導(dǎo)線多邊形點(diǎn)鏈。

1.2 剖分映射算法

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

圖2 剖分映射算法示意圖

剖分映射算法的輸入為多邊形點(diǎn)鏈、起始端口組、終止端口組；輸出為每個(gè)端口對(duì)的導(dǎo)線多邊形點(diǎn)鏈，布線步驟如下：

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

2）刪除剖分線列表中重復(fù)的剖分線，構(gòu)成Z型和X型剖分線；

3）構(gòu)造連通圖，求解每個(gè)端口對(duì)在連通圖中的路徑，即確定端口穿過(guò)的剖分線；

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

5）選擇編號(hào)最小的不滿足電阻約束的端口對(duì)，生成導(dǎo)線多邊形并計(jì)算電阻；

6）根據(jù)式(4)調(diào)整線寬W,；

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

8）微調(diào)導(dǎo)線多邊形以滿足物理設(shè)計(jì)規(guī)則，輸出每個(gè)端口對(duì)的導(dǎo)線多邊形點(diǎn)鏈。

1.2.1 多邊形剖分

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

1.2.2 初始布線

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

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

圖3 圖2對(duì)應(yīng)的連通圖

1.2.3 反比例線寬調(diào)整

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

分析端口對(duì)的設(shè)計(jì)約束可得到如下3個(gè)公式。

對(duì)于每條剖分線：

式中，為端口對(duì)的數(shù)量；W,為端口對(duì)在剖分線上分配的線段寬度；L為剖分線的總長(zhǎng)度。

對(duì)于每段線寬：

min_width ≤ W,(2)

式中，為最小線寬。

目標(biāo)函數(shù)，對(duì)每個(gè)端口對(duì)：

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

式中，函數(shù)根據(jù)所有線寬W,計(jì)算端口對(duì)的導(dǎo)線電阻；r為端口對(duì)的目標(biāo)電阻。

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

2　實(shí)驗(yàn)結(jié)果

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

設(shè)計(jì)1的布線區(qū)域?yàn)榫匦?，?9個(gè)端口對(duì)需要布線，起始端口均位于布線區(qū)域上邊界，終止端口均位于布線區(qū)域下邊界，應(yīng)用左邊算法進(jìn)行布線，布線結(jié)果如圖4所示。

圖4 設(shè)計(jì)1布線結(jié)果

設(shè)計(jì)2的布線區(qū)域?yàn)?9個(gè)頂點(diǎn)描述的復(fù)雜多邊形，共有12個(gè)端口對(duì)需要布線，起始端口和終止端口分別位于布線區(qū)域的右上方和左下方，應(yīng)用剖分映射算法進(jìn)行布線，布線結(jié)果如圖5所示。

圖5中，端口對(duì)1違反電阻約束，因?yàn)樵摱丝诘哪繕?biāo)電阻過(guò)小，導(dǎo)致用盡寬度資源也無(wú)法滿足其電阻約束。

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

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

3個(gè)設(shè)計(jì)的屬性及布線結(jié)果的相關(guān)數(shù)據(jù)如表1所示。

圖5 設(shè)計(jì)2布線結(jié)果

圖6 設(shè)計(jì)3布線結(jié)果

表1 3個(gè)設(shè)計(jì)的屬性以及布線結(jié)果數(shù)據(jù)

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

3　結(jié)論

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

[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] 于永斌.基于冒泡排序的非曼哈頓通道布線問(wèn)題中的串?dāng)_最小化研究[D].成都:電子科技大學(xué),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]韓奧,趙振宇,劉國(guó)強(qiáng),等.FPD平行端口矩形區(qū)域內(nèi)電阻驅(qū)動(dòng)的自動(dòng)布線算法[J].計(jì)算機(jī)工程與科學(xué),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)清,等.基于頂點(diǎn)可見性的凹多邊形快速凸分解算法[J].計(jì)算機(jī)研究與發(fā)展,1999(12):1455-1460.

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

[12] 全國(guó)大學(xué)生集成電路創(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

廣東省重點(diǎn)領(lǐng)域研發(fā)計(jì)劃項(xiàng)目（2019B010140002）

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

范鑫湖，男，1997年生，碩士研究生，主要研究方向：強(qiáng)化學(xué)習(xí)算法。E-mail: 1743568012@qq.com

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

TP303

A

1674-2605(2021)06-0004-06

10.3969/j.issn.1674-2605.2021.06.004