一種用于加速FPGA設計空間探索的電路特性驅動半監督建模方法

楊立群李 威黃志洪孫嘉斌楊海鋼*

1 引言

現場可編程門陣列（Field Programmable Gate Array, FPGA）的架構對在其上實現的電路性能有顯著影響。架構指FPGA內部可編程邏輯單元的結構以及邏輯單元之間的互連結構，其可由一系列的架構參數進行表征。隨著工藝尺寸的縮減以及應用電路的復雜化，FPGA架構設計過程中需要考慮的架構參數日益增多。所有架構參數的組合構成了FPGA的架構設計空間，顯然，從呈指數型擴增的FPGA架構設計空間中快速選擇一個滿足設計指標的優化架構成為FPGA設計初期需要解決的重要問題。

一種傳統的架構選擇方法是借助特定 CAD流程工具，例如 VTR[1]，來探索 FPGA 架構設計空間[24]-。設計空間中的所有待選架構通過VTR獲得相應的性能，如面積、延時等。通過對所有架構的性能進行比較，獲得最佳性能（最小面積或最小延時）的架構被選作最優架構。由于 VTR包含綜合、映射、裝箱、布局和布線一系列步驟[5]，并且設計空間隨著架構參數增長，因此將設計空間中的每一個架構通過 VTR來獲得相應的性能非常耗時且不符合工程應用實際。另一種解析建模方法通過構建FPGA性能解析模型來對FPGA架構設計空間進行探索[69]-。解析建模方法手工推導FPGA架構性能關于架構參數的數學模型[1012]-。基于該性能模型并借助于幾何規劃，就可從設計空間中獲得滿足具體設計指標的優化架構。這種方法省時，而且推導出的性能模型是關于架構參數的顯示模型，更加直觀。然而，在模型推導過程中進行的一些簡化和假設使得該性能模型不是十分精確和通用。此外，這種方法需要推導性能模型的設計人員對FPGA架構有非常全面的了解。

半監督模型樹（Semi-supervised Model Tree, SMT）方法被提出以解決上述實驗方法和解析建模方法中存在的問題[13]。首先，從設計空間中選出部分架構通過 VTR獲得相應性能。然后采用半監督模型樹算法學習表征這些架構的架構參數與相應性能之間的關系，而后自動建立關于架構參數的顯示性能模型。獲得的性能模型可預測設計空間中其他架構的性能。最后，結合非線性規劃可從整體架構設計空間中獲取優化架構。因為這種方法不需要將設計空間中的每一個架構通過VTR獲得性能，所以SMT方法比實驗方法更省時。同時，SMT方法是通過對基于VTR得到實際性能的FPGA架構進行學習來構建性能模型，因此它比解析建模方法更精確。然而SMT方法沒有考慮實驗電路信息。對于待學習的每一個架構，需要通過 VTR將實驗電路集中的所有電路映射到這個架構上，對所有電路的性能結果取幾何平均后作為這個架構的性能。這就導致了較長的建模時間。例如，要獲得17個VTR實驗電路在68個架構上的性能需要多達500 h[13]。此外，SMT方法只使用了 VTR電路集，如果實驗電路集中加入新的電路時，就需要再運行 VTR獲得新增的電路的性能來更新架構性能。

針對上述情況，本文提出一種基于電路特性的半監督建模方法。該方法能精確預測特定實驗電路在指定架構上的實現性能，并加速FPGA性能建模過程，從而進一步加速FPGA設計空間探索過程。實驗結果顯示本文方法在預測FPGA實現面積和延時時預測精度分別高達6.25%和4.23%，與SMT方法的預測精度可比擬。同時，相較于SMT方法，建模時間可至少減半。此外，本文提出方法構建了一個通用的FPGA性能模型，當預測新的電路在新的FPGA架構上的實現性能時不需要再額外運行VTR。

2 FPGA性能建模框架

本文方法采用類似 SMT[7]方法機制來構建FPGA性能模型。然而，本文加入了電路相關特性作為先驗知識使得構建的 FPGA性能模型更加通用。

圖 1展示了本文方法的建模過程。首先，從FPGA架構設計空間中選擇一些架構1A。然后，借助于VTR，將實驗電路集中的部分電路1S分別映射到1A上。裝箱、布局和布線之后，獲得1S中每個電路在1A中每個架構上的實現性能（面積和延時）。以獲得性能的架構和電路為基礎，應用半監督模型樹算法，開發未獲得性能的架構2A和電路特性2S，構建一個關于架構參數和電路特性參數的FPGA性能模型。

表1簡要呈現了上述建模過程中采用的改進的機器學習算法—半監督模型樹算法[13]。該算法使用M5P[14]算法先對電路在特定架構上的實現性能進行學習構建初始性能模型，然后以半監督的方式對沒有性能結果的架構和電路進行開發、學習，精煉模型。最終獲得的性能模型可以預測新的電路在設計空間中其他架構上實現的性能。

3 FPGA性能模型參數選擇

本文旨在通過構建FPGA實現面積和延時關于FPGA架構參數以及電路參數的模型進而探索FPGA架構設計空間。即采用FPGA架構參數和電路參數對FPGA實現面積和延時進行表征，以得到解析模型。基于該模型預測FPGA架構的性能，并研究模型參數對性能的影響，探索FPGA架構設計空間。本節主要介紹性能建模過程中采用的架構參數與電路特性參數。

圖1 本文方法的建模框架

表1 半監督模型樹算法偽代碼

3.1 架構參數

目前主流的商用FPGA芯片都采用基于查找表的島式結構[5]，本文以此為研究對象。如圖2所示，基于查找表的FPGA主要架構參數包括查找表的輸入數目（K），邏輯塊中的查找表數目（N），邏輯塊的輸入數目（I），邏輯塊的扇入系數（inFc ）和扇出系數（outFc ）。上述架構參數反映了FPGA的邏輯和互連結構，影響電路在FPGA上實現的面積和延時。K值越大，在一個K輸入查找表中可以實現的邏輯功能越多，關鍵路徑上的查找表數目減小，電路的延時越小，而同時K值的增大使得查找表的面積增大。N值的變化對面積與延時的影響效果與K值類似。I, N與inFc,outFc 聯合作用影響邏輯塊與其周圍互連通道之間的通信能力。inFc與outFc 變大，邏輯塊與通道的通信能力增強，與此同時卻帶來FPGA互連面積的增加。因此，要設計一個滿足設計指標的FPGA架構，需要在上述架構參數之間進行折中選擇。

3.2 電路特性參數

對于任一應用電路，可用5個基本電路參數來對其進行描述。這5個電路參數分別為實現電路需要的 2輸入查找表的數目（n2），電路網表中觸發器之間的最大門數（d2），電路的輸入輸出數目（nio），電路中觸發器的數目（nDFF）以及線網數目（nnet）[9]。其中， n2,nio,nDFF和 nnet反映了應用電路的規模，而 d2,nDFF和 nnet則表征了應用電路的性能。本文基于VTR和MCNC兩個實驗電路集中的25個電路來探索上述電路參數與電路實現的面積和延時的關系。表2列出各個電路參數與電路面積和延時之間的相關系數。從表2可以看出 n2與面積之間相關系數最大，d2與延時最相關，而 nio對面積和延時的影響最小。此外， nnet與 nDFF也與面積密切相關，其與 n2之間的相關系數分別為0.9989, 0.7893，這說明nnet,nDFF與 n2不是相互獨立的。因此，在本文提出的建模方法中，使用兩個電路特性參數 n2和 d2來表征一個電路。

n2與 d2反映了電路的規模和時序信息。從這兩個特性參數的定義上理解， n2的增大會使得電路面積增大，電路延時會隨 d2的增加而增加。圖3顯示了VTR各電路中面積、延時隨 n2, d2的變化趨勢。

表2 各電路參數與面積和延時之間的相關系數

圖2 FPGA架構示意圖

圖3 VTR電路中 2n,2d與面積、延時的變化關系

本文中FPGA性能模型涉及的參數，包括架構和電路特性參數總結在表3中。

表3 FPGA性能模型參數

4 實驗及結果分析

本節通過實驗來驗證本文方法的精確性、時效性和通用性。

本文使用VTR和MCNC兩個實驗電路集中的電路進行相關實驗。由于規模較大，VTR工具運行時間較長，兩個最大的電路 LU32PEEng和 mcml被排除VTR實驗電路集之外。MCNC實驗電路集中的電路規模普遍較小，因此從中選擇了8個最大的電路。使用ABC[15]來提取電路特性參數。表4列出了選用的17個VTR電路和8個MCNC電路的特性參數值。這些電路涵蓋了不同領域的典型應用。本文采用VTR工具對電路在FPGA上實現的過程進行模擬，獲得架構和電路對應的實現性能。

本文采用平均相對誤差（Mean Relative Error,MRE）作為評估指標來評價本文方法的精確性。MRE定義見式（1）。其中， xi是通過 VTR獲得的FPGA實現性能，而 x'i是通過本文方法獲得的性能模型預測得到的性能。tN代表測試集中測試項的數目。

表4 VTR和MCNC電路特性參數

使用本文方法進行性能模型建模過程中，訓練集的選擇決定了最終生成的性能模型。為使模型更加精確和通用，訓練集應該包含盡可能多的信息供學習算法進行學習。對于FPGA架構性能進行建模，訓練集即為FPGA架構參數、電路特性參數和其相應的性能的數值組合。因此，訓練集中FPGA架構參數和電路特性參數的數值選取應該具有代表性和多樣性。以FPGA架構參數中的查找表輸入數目K為例，K的取值范圍為[4,10]，那么在選擇訓練集時，FPGA架構參數中K值的選取不應該集中于其取值范圍中的某一區域，防止訓練得到的性能模型只能預測該區域附近K值的性能值，而不能精確預測其他值。其他模型參數的數值選擇也遵循此規則。

4.1 預測精度

本實驗首先通過VTR獲得了11個VTR電路在 6個 FPGA架構上的實現面積和延時作為訓練集。基于該訓練集使用本文方法學習FPGA實現面積和延時與其對應的電路特性和架構參數之間的關系。學習后構建的面積/延時模型用于預測測試集中另外6個VTR電路在2個新的FPGA架構上的實現性能。同時，通過 VTR獲得測試集中電路的實現性能。針對測試集中的電路和架構組合，將本文方法構建模型預測的性能與通過 VTR獲得的實現性能進行比較，計算兩者之間的MRE，檢驗本文方法的預測精度。然后，減少訓練集中本文方法學習的電路數目，觀察預測MRE的變化。

圖4展示了這一實驗過程中MRE的變化過程。如圖所示，學習11個VTR電路的性能得到的FPGA性能模型進行面積預測時MRE可達6.25%，延時預測時可達4.23%。SMT方法中不考慮電路特性（學習所有17個VTR電路的性能）預測面積和延時時的平均相對誤差分別為5.96%和2.70%[13]。本文方法與文獻[13]中方法預測精度可比擬。此外，當學習的實驗電路數目從10個降到7個時，面積預測精度保持不變。并且當學習的電路數目從11個降到7個時，預測MRE僅從6.25%增長到7.80%。這說明通過使用本文方法可以減少學習的電路數目從而降低面積/延時模型建模過程的時間開銷，同時仍保持一定的預測精度。從圖4中還可以觀察到當學習的實驗電路數目從10降到9時，MRE減少。這是因為這個移除的電路與測試電路差異較大，學習這個電路的性能從而構建的性能模型會降低預測測試電路時的精度。當只學習3個電路的性能來構建面積/延時模型時，預測測試電路時的 MRE驟增，這說明學習的電路數目太少，不足以構建一個精確的性能模型。

4.2 時間開銷

圖4 MRE隨學習的電路數目的變化趨勢

利用半監督模型樹算法進行FPGA性能建模的時間僅為1～5 min，探索FPGA架構設計空間的時間成本主要在于通過 VTR為學習算法提供帶有性能結果的FPGA架構，如式（2）所示。

其中，n和m分別代表需要學習的架構和電路數目。總的時間成本tolT 為將m個電路在n個FPGA架構上通過VTR實現的時間之和。

文獻[13]中方法在對 FPGA架構性能建模過程中沒有考慮電路參數的影響，該算法需要將實驗電路集中的所有電路在一個FPGA架構上實現，取電路性能的幾何平均作為該FPGA架構的性能。因此，對于文獻[13]中方法，時間成本中的 m為電路集的大小，并且文獻[13]中方法不能預測某個指定電路在FPGA上的實現性能。而本文方法通過構建關于架構參數和電路參數的FPGA性能模型，可以預測特定電路在特定FPGA架構上的實現性能。

如表5所示，本文方法學習11個VTR電路（近似VTR電路集的2/3）構建面積/延時性能模型預測性能時與文獻[13]學習所有17個VTR實驗電路的建模方法預測性能的精度可比擬。學習7個電路（小于 1/2VTR電路集）性能構建的面積模型預測精度只降低到文獻[13]中方法精度的92%。并且學習的電路數目從17減少到9個時，延時預測的精度幾乎不變。

上述實驗結果說明在保證預測精度的前提下，學習的電路數目可至少減半。因此，對于本文方法，時間成本中的 m為實驗電路集的一半。文獻[13]方法在Intel Xeon E7-4807上探索具有百萬FPGA架構的設計空間時需要 500 h，采用本文方法僅需要250 h。此外，學習的實驗電路數目可以進一步減少，這就需要在時間開銷和預測精度之間進行折中選擇。

表5 預測精度與時間開銷隨學習的電路數目的變化趨勢

4.3 通用性

本文加入電路特性作為先驗知識來構建FPGA性能模型，所以獲得的性能模型能夠精確預測新的電路的實現性能。這一節進行兩組相關實驗來驗證本文方法的通用性。

在第1組實驗中，基于訓練集中2個VTR電路在8個架構上的實現性能，構建性能模型來預測測試集中另外一個VTR電路在相同8個架構上的實現性能。使用上述流程測試了預測每一個 VTR電路性能的預測精度。在第2組實驗中，基于2個VTR電路在8個架構上的實現性能，構建性能模型來預測MCNC電路集中的電路在相同8個架構上的實現性能。

圖 5顯示了本文方法在預測 VTR（圖 5（a））和MCNC（圖 5（b））中每個電路時預測性能與實際性能之間的平均相對誤差。可見，在預測 VTR電路的面積和延時時，除個別電路外，預測MRE在10%左右。然而在預測ch_intrinsics和stereovision3這兩個電路的面積, 以及在預測 LU8PEEng和stereovision2這兩個電路的延時時，預測結果不精確。如表 4所示，這是因為在 VTR電路集中stereovision3電路的2n值最小，stereovision2的2n最大。類似地，ch_intrinsics的2d是最小的而LU8PEEng的2d是最大的。這4個電路體現了VTR電路集中2n和2d特性參數的4個極端值，沒有合適的電路去學習來表征這4個電路的性能。結果，獲得的面積/延時模型對于這些電路來說不是足夠精確。因此，為使最終的性能模型足夠精確，所選取的待學習電路的特性需要有代表性。在用學習VTR電路性能構建的性能模型預測 MCNC電路的性能時，最大的平均相對誤差不超過13%，證明了本文提出的基于電路特性的建模方法可以較好地預測新電路的性能，提供了一個通用的性能建模方法。

圖5 預測來自不同電路集的電路性能時本文方法的MRE

4.4 電路特性對性能的影響

本文采用的半監督模型樹算法最終生成一個關于FPGA架構和電路特性參數的顯示性能模型。該模型能反映出電路特性對性能的影響趨勢。

圖 6為使用本文方法生成的面積（圖 6（a））和延時（圖6（b））性能模型示例。如圖所示，面積模型中2n和延時模型中2d的系數均為正，說明在相同FPGA架構上（模型中FPGA架構參數相同時），面積和延時隨電路參數2n和2d正比例增長，這與圖3實驗分析得到的趨勢一致。因此，本文方法能對電路參數的影響進行良好的預測。

4.5 探索半監督模型樹算法中的參數

在表1呈現的半監督模型樹算法中，主要有兩個參數1L和2L，代表了建模過程中兩個模型樹上葉端存在的最小樣本數目。上述實驗使用了這兩個參數的經驗值。本實驗改變這兩個參數的數值并觀察MRE的變化。

圖6 面積、延時模型樹

表6呈現了變化的L 值對MRE的影響。可見，當這兩個參數取相同值時，預測精度通常較差。因為兩個模型樹之間的相似性使得他們為彼此挑選相似的未標記樣本。一旦挑選了一個不合適的樣本，誤差就會循環累積，最終導致一個不是十分精確的性能模型產生。此外，當兩個參數數值都較小時，預測精度也不高。這是因為模型樹葉端較少的樣本數目使得性能模型過于精細，也就是說獲得的性能模型在擬合訓練樣本時產生了過擬合的現象，這在一定程度上降低了預測測試樣本的精度，尤其當測試樣本與訓練樣本特性相差較大時。

5 結束語

本文呈現了一個電路特性驅動的FPGA架構性能半監督建模方法。該方法通過學習電路特性與實現性能之間的關系來構建FPGA性能模型。本文方法不需要獲得所有應用電路在FPGA架構上的實現性能就可構建一個精確且通用的性能模型，加快了FPGA性能建模及架構設計探索過程。實驗結果顯示該方法能以6.25%的MRE預測FPGA性能，并可將具有百萬架構的 FPGA設計空間探索時間由500 h降低為250 h。此外，本文方法不局限于只對基于LUT結構的FPGA性能進行建模，未來工作將對基于新型邏輯結構的FPGA性能建模，如基于與非錐結構的FPGA[16]。

表6 L值對MRE的影響

[1] Luu J, Goeders J, Wainberg M, et al.. VTR 7.0: next generation architecture and CAD system for FPGAs[J].ACM Transactions on Reconfigurable Technology and Systems, 2014, 7（2）: 6:1-6:30.

[2] Marquardt A, Betz V, and Rose J. Speed and area tradeoffs in cluster-based FPGA architectures[J]. IEEE Transactions on Very Large Scale Integration （VLSI） Systems, 2000, 8（1）:84-93.

[3] Ahmed E and Rose J. The effect of LUT and cluster size on deep-submicron FPGA performance and density[J]. IEEE Transactions on Very Large Scale Integration （VLSI） Systems,2004, 12（3）: 288-298.

[4] Jiang Zheng-hong, Lin C Y, Yang Li-qun, et al.. Exploring architecture parameters for dual-output LUT based FPGAs[C]. Proceedings of the 24th International Conference on Field Programmable Logic and Applications, Munich,Germany, 2014: 1-6.

[5] Betz V, Rose J, and Marquardt A. Architecture and CAD for Deep-Submicron FPGAs [M]. Netherlands, Kluwer Academic Publishers, 1999: 15-20.

[6] Gao Hai-xia, Yang Yin-tang, Ma Xiao-hua, et al.. Analysis of the effect of LUT size on FPGA area and delay using theoretical derivations[C]. Proceedings of the 6th International Symposium on Quality of Electronic Design,San Jose, CA, USA, 2005: 370-374.

[7] Smith A, Wilton S, and Das J. Wirelength modeling for homogeneous and heterogeneous FPGA architectural development[C]. Proceedings of the 17th ACM/SIGDA international symposium on Field programmable gate arrays,Monterey, CA, USA, 2009: 181-190.

[8] Das J, Lam A, Wilton S, et al.. An analytical model relating FPGA architecture to logic density and depth[J]. IEEE Transactions on Very Large Scale Integration （VLSI） Systems,2011, 19（12）: 2229-2242.

[9] Smith A, Constantinides G, and Cheung P. FPGA architecture optimization using geometric programming[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29（8）: 1163-1176.

[10] Pandurangaiah Y, Reddy V, and Chakravarthy K.Area-delay estimation by concurrent optimization of FPGA architecture parameters using geometric programming[J].International Journal of Computer Applications, 2013, 82（18）:4-11.

[11] Mehri H and Alizadeh B. An analytical dynamic and leakage power model for FPGAs[C]. Proceedings of the 22nd Iranian Conference on Electrical Engineering （ICEE）, Tehran, 2014:300-305.

[12] Leow Yoon-kah. Post-routing analytical models for homogeneous FPGA architectures[D]. [Ph. D. dissertation],The University of Arizona, 2013.

[13] Yang Li-qun, Yang Hai-gang, Li Wei, et al.. A semi-supervised modeling approach for performance characterization of FPGA architectures[C]. Proceedings of the 24th International Conference on Field Programmable Logic and Applications, Munich, Germany, 2014: 1-6.

[14] Wang Y and Witten I H. Inducing model trees for continuous classes[C]. Proceedings of the Ninth European Conference on Machine Learning, Prague, Czech Republic, 1997: 128-137.

[15] Brayton R and Mishchenko A. ABC: an academic industrial-strength verification tool[J]. Computer Aided Verification, 2010, 6174: 24-40.

[16] Zgheib G, Yang Li-qun, Huang Zhi-hong, et al.. Revisiting and-inverter cones[C]. Proceedings of the 2014 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Monterey, CA, USA, 2014: 45-54.