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

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

1 引言

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

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

2 原始合法化流程概述

圖1 曼哈頓距離示意圖

3 最大流算法原理

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

圖2 兩方匹配問題示意圖

Min-Cost Max-Flow 問題的求解過程如下：

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

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

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

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

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

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

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

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

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

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

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

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

合法化過程的流程圖如圖3 所示。

圖3 合法化過程流程圖

將FPGA 劃分為若干區(qū)域，并對每個區(qū)域分別進行合法化。合法化按照一定大小的區(qū)域分開多次進行是因為尋找最大流的Ford-Fulkerson 算法、尋找最短路徑的dijkstra[5]算法兩者疊加使用，使得算法運行時間隨算法中節(jié)點數(shù)量增加呈指數(shù)級上升，分開多次求解雖然在一定程度上限制了解的范圍，但避免了算法帶來的不可接受的時間成本。

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

當n＞50 時，影響因子計算如式（2）所示。

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

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

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

5 實驗結果及討論

文章選取了13 個測試電路，在yxc3 的jyxlx350tff1738 器件上使用原始合法化方法和不同劃分區(qū)域大小的改進型算法在完全相同的環(huán)境下進行布局。以布局后線長為標準評價最終電路質(zhì)量，測試結果如表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 使用率超過70%。

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

表1 布局時間及線長測試結果表

表2 布局時間及線長測試結果表（續(xù)）

6 結論

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