最大流算法應(yīng)用于二次線性規(guī)劃布局合法化過(guò)程

（無(wú)錫中微億芯有限公司，江蘇無(wú)錫 214072）

1 引言

現(xiàn)場(chǎng)可編程邏輯門陣列（Field-Programmable Gate Array,FPGA）是一種在日用家電、大型機(jī)械乃至航空航天領(lǐng)域都有廣泛應(yīng)用的芯片。而FPGA 的設(shè)計(jì)離不開(kāi)電子設(shè)計(jì)自動(dòng)化（Electronic Design Automation,EDA）工具。布局則是EDA 工具中重要的一環(huán)，其對(duì)EDA 工具本身運(yùn)行速度、所處理電路的最終質(zhì)量有著很大影響。

近年來(lái)，F(xiàn)PGA 芯片電路的規(guī)模快速增長(zhǎng)，使其功能更加強(qiáng)大，但同時(shí)也給相應(yīng)的EDA 工具帶來(lái)了挑戰(zhàn)。解析型的算法以其可以使用數(shù)學(xué)方法快速求得全局最優(yōu)解的特性成為當(dāng)今布局算法的主流方向之一。二次線性規(guī)劃算法[1-2]是解析型算法的一種，其在具體應(yīng)用于解決布局問(wèn)題的時(shí)候體現(xiàn)出了快速求解的特性，但在求解完成后，依然存在不合法的布局，需要再次進(jìn)行合法化操作。原始的合法化操作僅是在不合法布局的周圍尋找一個(gè)最近的合法位置，這樣的操作不具備任何導(dǎo)向性，往往導(dǎo)致最終的解不盡如人意。業(yè)界有使用綜合型算法[3]來(lái)彌補(bǔ)這一缺點(diǎn)，本文則將最大流算法應(yīng)用于二次線性規(guī)劃算法求解后的合法化操作，以求提高最終解的質(zhì)量。

2 原始合法化流程概述

圖1 曼哈頓距離示意圖

3 最大流算法原理

如圖2 所示是最大流算法中一個(gè)經(jīng)典問(wèn)題——兩方匹配問(wèn)題。每個(gè)節(jié)點(diǎn)有自己可以放入的位置，位置個(gè)數(shù)有限，要使盡量多的節(jié)點(diǎn)可以放入。將布局合法化問(wèn)題抽象成圖，將不合法節(jié)點(diǎn)與空置位置抽象為圖中節(jié)點(diǎn)，將不合法節(jié)點(diǎn)與空置位置間的關(guān)系抽象為邊。為每一個(gè)不合法節(jié)點(diǎn)建立一個(gè)節(jié)點(diǎn)，為每一個(gè)空置位置建立一個(gè)節(jié)點(diǎn)，在其間建立有向邊代表不合法節(jié)點(diǎn)可以放入該空置位置；建立一個(gè)虛擬的源點(diǎn)S，在S 與每個(gè)不合法節(jié)點(diǎn)間建立有向邊；建立一個(gè)虛擬的終點(diǎn)T，在每個(gè)空置位置節(jié)點(diǎn)與T 之間建立有向邊；這樣布局合法化問(wèn)題就變成了求解由S 到T 的最大流。為了使尋找的過(guò)程具有導(dǎo)向性，使用線長(zhǎng)來(lái)進(jìn)行評(píng)價(jià)并給每條不合法節(jié)點(diǎn)到空置位置的邊賦權(quán)值，記為cost。這樣又進(jìn)一步將布局合法化問(wèn)題轉(zhuǎn)化為了最大流算法中的Min-Cost Max-Flow 問(wèn)題。

圖2 兩方匹配問(wèn)題示意圖

Min-Cost Max-Flow 問(wèn)題的求解過(guò)程如下：

(1)在剩余圖中尋找cost 最小的路徑；

(2)對(duì)路徑進(jìn)行增廣，形成新的剩余圖，具體到布局合法化問(wèn)題中即將（1）中所找到的路徑上所有的邊反向，并將這些邊的cost 取負(fù)；

(3)不斷重復(fù)（1）、（2），直到S 到T 不存在路徑，所得到的圖即為流最大，且在相同流量情況下cost 最小的圖。

上述過(guò)程使用了Ford-Fulkerson[4]算法以確保最終找到最大流，并可以使用數(shù)學(xué)歸納法簡(jiǎn)單證明求解過(guò)程每次循環(huán)都找出了當(dāng)前流量下cost 最小的流，數(shù)學(xué)歸納法的證明過(guò)程如下：

(1)流量為1 時(shí)，顯然成立；

(2)設(shè)流量為i 時(shí)，f 是cost 最小的流，則其剩余圖中必不含有負(fù)cost 的環(huán)路；

閑暇時(shí)，黃婉秋喜歡翻閱介紹養(yǎng)生保健知識(shí)的書(shū)籍，記一些容易做到的保健方法。因此，她的生活起居有了些講究：“我根據(jù)自己的體質(zhì)，少吃蘋(píng)果、酸菜等食物，因?yàn)樘O(píng)果會(huì)產(chǎn)生胃酸，酸菜對(duì)牙齒不好。每天起床時(shí)，我都做到‘三個(gè)一’：在床上躺一分鐘、坐一分鐘，起床后站一分鐘，這都是從保健書(shū)上學(xué)來(lái)的。”

(3)由求解方法推導(dǎo)出的流量為i+1 時(shí)的流記為g，則g-f 為一條S 到T 的cost 最小的路徑，將該路徑記為r；

(4)若在流量為i+1 時(shí)存在比g cost 更小的流h，則對(duì)于這兩個(gè)流量相同的流，h-g 必存在環(huán)路，又因?yàn)閔 的cost 小于g，則h-g 的環(huán)路中必包含至少一個(gè)負(fù)cost 的環(huán)路，則h-f 是路徑r 與存在負(fù)cost 環(huán)路的若干環(huán)路組成，即f 的剩余圖中存在cost 為負(fù)的環(huán)路；

(5)f 的剩余圖中存在cost 為負(fù)的環(huán)路，則f 不是流量為i 時(shí)cost 最小的流，這與假設(shè)條件相悖；

(6)所以流量為i+1 時(shí)g 即為cost 最小的流，原結(jié)論得證。

4 最大流算法實(shí)現(xiàn)

合法化過(guò)程的流程圖如圖3 所示。

圖3 合法化過(guò)程流程圖

將FPGA 劃分為若干區(qū)域，并對(duì)每個(gè)區(qū)域分別進(jìn)行合法化。合法化按照一定大小的區(qū)域分開(kāi)多次進(jìn)行是因?yàn)閷ふ易畲罅鞯腇ord-Fulkerson 算法、尋找最短路徑的dijkstra[5]算法兩者疊加使用，使得算法運(yùn)行時(shí)間隨算法中節(jié)點(diǎn)數(shù)量增加呈指數(shù)級(jí)上升，分開(kāi)多次求解雖然在一定程度上限制了解的范圍，但避免了算法帶來(lái)的不可接受的時(shí)間成本。

首先需要選取一個(gè)FPGA 中的區(qū)域。隨后按照當(dāng)前的布局狀態(tài)建立bounding box 結(jié)構(gòu)以線長(zhǎng)為目標(biāo)計(jì)算cost，該結(jié)構(gòu)以邊界位置、位于邊界上的節(jié)點(diǎn)數(shù)量來(lái)記錄線網(wǎng)的狀態(tài)。這樣做的好處是，只有少數(shù)情況下需要遍歷線網(wǎng)中所有的節(jié)點(diǎn)來(lái)得出半周長(zhǎng)。線網(wǎng)半周長(zhǎng)再乘以線網(wǎng)大小所決定的影響因子即得到該線網(wǎng)的線長(zhǎng)。記線網(wǎng)中節(jié)點(diǎn)個(gè)數(shù)為n，當(dāng)n≤3 時(shí)，影響因子為1。當(dāng)3＜n≤50 時(shí)，影響因子計(jì)算如式（1）所示。

當(dāng)n＞50 時(shí)，影響因子計(jì)算如式（2）所示。

對(duì)所選取區(qū)域中的布局狀態(tài)進(jìn)行抽象，建立圖。除了按照第2 節(jié)的方式建圖，還需要使用前一步所計(jì)算的cost 為每一條不合法節(jié)點(diǎn)到空置位置的路徑賦值。此外，為了更高效地尋找cost 最小的路徑，選取了dijkstra 算法，而dijkstra 算法不允許圖中路徑出現(xiàn)負(fù)值，因此要為每一個(gè)圖中節(jié)點(diǎn)加勢(shì)，使可能含有負(fù)cost路徑的圖轉(zhuǎn)化為不含有負(fù)cost 路徑的圖，以適用dijkstra 算法。之后再依照第2 節(jié)所述方法進(jìn)行求解，為該區(qū)域中的非法節(jié)點(diǎn)尋找最優(yōu)的合法空置位置。

在一個(gè)區(qū)域合法化完成后，再選取下一個(gè)區(qū)域重復(fù)以上操作，直至所有區(qū)域遍歷完成，布局處于合法狀態(tài)。

由于區(qū)域中資源有限，在一個(gè)區(qū)域中有可能出現(xiàn)資源耗盡時(shí)仍有節(jié)點(diǎn)處于非法放置狀態(tài)。先將這些節(jié)點(diǎn)標(biāo)記，待所有區(qū)域遍歷完成，再將所有區(qū)域中的這些個(gè)別非法節(jié)點(diǎn)一次性處理，使其合法。處理的過(guò)程以剩余非法節(jié)點(diǎn)和剩余空置資源建立圖，求解。

5 實(shí)驗(yàn)結(jié)果及討論

文章選取了13 個(gè)測(cè)試電路，在yxc3 的jyxlx350tff1738 器件上使用原始合法化方法和不同劃分區(qū)域大小的改進(jìn)型算法在完全相同的環(huán)境下進(jìn)行布局。以布局后線長(zhǎng)為標(biāo)準(zhǔn)評(píng)價(jià)最終電路質(zhì)量，測(cè)試結(jié)果如表1 和表2 所示。

所選取的電路slice 使用率從2%至98%不等。其中3des_vhdl 與igt_single_cpuv3 的slice 使用率小于10%；igt_quad_cpuv3、igt_noc_10v3、igt_noc_3v3、igt_ten_cpuv3 的slice 使用率在10%到40%之間；igt_noc_4v3、igt_noc_5v3、s1_core_no_dsp、s1_core_with_dsp 的slice 使用率在40%到70%之間；igt_noc_6v3、igt_fixpt_cordicv3、igt_float_cordicv3 的slice 使用率超過(guò)70%。

從表1 和表2 中可以看出，改進(jìn)后的算法不論如何選取區(qū)域以布局后線長(zhǎng)為標(biāo)準(zhǔn)進(jìn)行評(píng)價(jià)都有普遍的提升，但布局過(guò)程的運(yùn)行時(shí)間都有不同程度的增長(zhǎng)。線長(zhǎng)方面呈現(xiàn)出選取區(qū)域面積越大最終線長(zhǎng)越小的趨勢(shì)。運(yùn)行時(shí)間方面，區(qū)域選擇過(guò)小或過(guò)大都使運(yùn)行時(shí)間顯著增長(zhǎng)。其中，區(qū)域大小為4×4 時(shí)與原始合法化方法相比平均增加運(yùn)行時(shí)間34%，減少線長(zhǎng)2.1%；區(qū)域大小為8×8 時(shí)與原始合法化方法相比平均增加運(yùn)行時(shí)間12.5%，減少線長(zhǎng)3.1%；區(qū)域大小為16×16 時(shí)與原始合法化方法相比平均增加運(yùn)行時(shí)間21.8%，減少線長(zhǎng)4.1%；區(qū)域大小為32×32 時(shí)與原始合法化方法相比平均增加運(yùn)行時(shí)間96.7%，減少線長(zhǎng)4.6%；區(qū)域大小為FPGA 自身region 時(shí)與原始合法化方法相比平均增加運(yùn)行時(shí)間75.4%，減少線長(zhǎng)4.3%。綜合來(lái)看，選取區(qū)域大小為8×8 或16×16 較為合適。

表1 布局時(shí)間及線長(zhǎng)測(cè)試結(jié)果表

表2 布局時(shí)間及線長(zhǎng)測(cè)試結(jié)果表（續(xù)）

6 結(jié)論

本文將最大流算法應(yīng)用于二次線性規(guī)劃算法的合法化部分，使原本不具有導(dǎo)向性的合法化流程變得具有導(dǎo)向性，并在一定程度上提高了最終解的質(zhì)量。今后將嘗試在算法中加入時(shí)序驅(qū)動(dòng)，以適應(yīng)更多的需求。