面向AIC結構的FPGA映射工具

江政泓 林 郁 黃志洪 楊立群 楊海鋼

①（中國科學院電子學研究所可編程芯片與系統研究室 北京 100190）

②（中國科學院大學 北京 100049）

面向AIC結構的FPGA映射工具

江政泓①②林 郁①黃志洪①楊立群①②楊海鋼*①

①（中國科學院電子學研究所可編程芯片與系統研究室 北京 100190）

②（中國科學院大學 北京 100049）

探索新的現場可編程門陣列（FPGA）邏輯單元結構一直是FPGA結構研究的重點方向，與非邏輯錐（AIC）作為一種新的邏輯結構成為FPGA新結構的希望。然而實現高效且靈活的映射工具同樣是研究FPGA新結構中的重點環節。該文實現了一個面向AIC結構的FPGA映射工具，與當前映射工具相比，具有更高的靈活性，能夠支持AIC結構參數的調節，輔助支持進行AIC單元結構的探索改進。同時，該文提出的AIC映射工具與原工具相比，面積指標提高了33%～36%。

現場可編程門陣列；與非邏輯錐；映射

1 引言

在現場可編程門陣列（Field Programmable Gate Arrays，FPGAs）的技術發展中，改善面積、性能和功耗等指標一直是研究的重點［1］。很多新的嵌入模塊結構和研究結果被不斷提出，例如嵌入式存儲器［2］（BRAM）和數字處理器單元（DSP）等，甚至功能更加強大的微處理器核心［3，4］（MCU）也被作為組件嵌入到FPGA芯片中。然而，查找表（Look-Up Table，LUT）作為FPGA的最基本最核心的單元，二三十年來卻沒有根本性的變化。

傳統的查找表通過合理的SRAM配置來實現特定功能，具有非常高的靈活性。對于一個K輸入的LUT，一共有2K個SRAM配置位，因此存在 22K種不同的配置方案，可以實現 22K種不同的功能。如此龐大的功能集合，可以實現K輸入下的任意邏輯功能，并且極大地簡化了FPGA自動流程CAD（Computer-Aided Design）中的映射過程。但是，傳統查找表具有如此強大的靈活性是以電路面積、延遲和功耗為代價的。學術界和工業界都一直研究如何有效地改善LUT結構［57］-。

2012年，瑞士洛桑理工大學的Parandeh-Afshar等人提出了一種新的邏輯結構來替代查找表作為FPGA的基本邏輯單元［8］，這種新的邏輯結構稱為“與非邏輯錐”（And-Inverter Cones，AIC）。AIC邏輯單元在某些應用電路的性能評價指標上優于查找表，成為查找表作為FPGA基本單元的有力挑戰者［9］。然而，在最新的研究［10］中發現，AIC邏輯結構在實際的電路結構中仍存在眾多的不足之處，仍有許多方面需要進一步的研究和探索。

針對AIC的結構特點以及未來的結構探索需求，本文提出并實現了一款新的FPGA映射工具，與文獻［8，9］中所使用的映射工具相比較，新的映射工具具有以下特點：（1）支持查找表或者AIC邏輯單元兩種不同結構FPGA的映射，同時還能實現兩種單元混合的異質結構FPGA的映射。（2）支持AIC邏輯單元的不同參數約束，能夠有效支持AIC邏輯單元的結構參數探索。（3）與現有的AIC映射工具相比，新映射工具實現相同功能的用戶電路可以平均少使用33%的邏輯單元數，具有更好的面積指標。

2 AIC邏輯單元結構參數

文獻［8，9］中所采用的與非邏輯錐（AIC）結構如圖1所示，是一種二進制與非門樹，采用兩輸入與門和非門作為基本結點，每個與門的輸出都有一個多路選擇器（MUltipleXor，MUX）選擇是否對信號進行反向，如A節點所示。通過多層級的與非門單元結構的級聯，構成了一個完整的與非門邏輯錐。為了提高與非門邏輯錐的靈活性，對每個邏輯錐的第1層可配置與非門進行了強化，在與門的輸入端也增加了一組可配置MUX和非門單元，如B節點。同時，AIC單元結構中的每一個A類型節點都能夠輸出到單元外部，因此，與傳統的查找表結構相比，除了內部結構的不同，AIC單元結構還有多輸入與多輸出的端口特征。

通過圖1中的結構展示和以上對AIC單元結構的描述，我們可以了解AIC具有多個不同的結構參數，通過對這些結構參數的實驗探索，可以精簡現有結構的冗余，提高單元結構的性能和面積指標。表1總結了當前AIC單元結構中可以直接探索的結構參數。

3 AIC邏輯單元的映射原理與實現

本文所采用的AIC映射工具是在伯克利的開源軟件ABC上實現的［11］，仍然采用傳統查找表的映射方法和流程，結合AIC邏輯單元的結構特點，實現AIC邏輯單元的映射過程。

圖1 AIC邏輯單元結構

表1 AIC單元的結構參數

3.1 映射中的基本概念

對于任何一個邏輯電路的組合邏輯部分，都可以抽象成一個有向無環圖（Directed Acyclic Graph，DAG），圖中每一個結點v都代表一個邏輯門或者輸入/輸出端口，其中CIs （Combinational Inputs）代表組合邏輯電路的輸入端口（包括電路的原始輸入PI和電路中寄存器的輸出端口），COs （Combinational Outputs）代表組合邏輯電路的輸出端口（包括電路的原始輸出PO和電路中寄存器的輸入端口），node表示具有實際邏輯功能的邏輯門。

傳統映射算法的本質就是使用割子圖（Cut）來對DAG圖進行分割，將整個電路網絡劃分成一個個獨立的Cut，而每個Cut實際對應成一個查找表單元，實現從門級網表電路到以查找表為單元的電路的轉變。一般習慣上，使用Cv代表以結點v為根節點的Cut，Input（Cv）代表Cut的所有輸入結點。在傳統的查找表結構映射過程中，由于一個K輸入的查找表僅能實現K個輸入下的任意邏輯功能，因此，要求如果一個Cut滿足該端口數目約束條件，那么就稱該Cut為“K-feasible”。

3.2 基于枚舉方法的AIC映射算法

與傳統的窮盡枚舉映射方法不同，ABC工具采用的是Priority-Cuts算法。該算法在與傳統的窮盡枚舉算法相比，能夠在不損失性能和面積的前提下，有效地降低PC的內存使用率，減少整個映射過程的運行時間［12］。

3.2.1 枚舉過程（Cut enumeration）枚舉過程是整個映射算法的基礎，為網絡中所有的結點 v生成Cuts，后續的前向遍歷和后向遍歷步驟以枚舉過程生成的Cuts為基礎，進行篩選排序和遞歸組合等過程實現邏輯網表到 FPGA邏輯單元網表的轉換。Priority-Cuts算法中采用文獻［13］描述的方法來實現Cuts的枚舉過程。

在傳統的查找表映射中，要求所有的Cuts都是滿足輸入數目小于K的約束，即“K-feasible”。然而如圖1所示，對于AIC結構來說，僅有輸入個數的約束是不夠的，因為，D-AIC結構中最多只有D層可配置與非門，如果一個Cut內部包含的AIG（And-Inverter Graph）級數超過D就無法使用D-AIC單元來實現，因此，在輸入約束之外，AIC的Cut枚舉過程還需要增加一個Cut內部AIG子圖的深度約束，即aigdepth（u∪v）≤D，稱之為“D-feasible”。

3.2.2 映射的前向遍歷（forward traversal）在傳統的映射方法中，Cuts的枚舉過程是獨立的，是首先計算出整個網絡中所有結點的所有符合輸入約束條件的Cuts，然后保存下來，再開始進行前向遍歷過程，計算出每個Cut的邏輯深度和邏輯面積值，最終為每個結點v獲取其最優的Cut，即BestCv。Cut的邏輯深度使用式（1）計算獲得，而邏輯面積使用經典的“Area-Flow”方法進行評估，由式（2）獲得

AIC映射工具在Priority Cuts算法前向遍歷方法的基礎上，增加了AIC結構特有的約束，實現了AIC映射的前向遍歷過程。首先，每個結點不再保存所有的Cuts，而是僅保存排序后的前（4C≤C≤8）個有效Cuts。那么，根據3.2.1節中描述的Cuts枚舉方法，每個結點根據其扇入結點的Cuts集合進行Cuts枚舉，如此，由于扇入結點Cuts集合的不完備，每個結點并未實現Cuts的窮盡枚舉，減小了程序的計算量，同時降低了內存的占用。然而，Cuts集合的不完備并不會降低映射的性能［12］。其次，和傳統的查找表映射不同，除了要求Cuts符合輸入數目約束之外，還要符合Cuts內部可配置與門級數約束（a igdepth （Cv）≤ D）。

3.2.3 映射的后向遍歷（backward traversal）

完成前向遍歷之后，電路網絡中的每個結點v均獲得了自己的BestCv及其對應的邏輯深度和面積值。后向遍歷則以前向遍歷獲得的BestCv信息，完成邏輯網表到FPGA單元網表的最終轉換過程。

后向遍歷從電路網表的輸出（COs）開始，以反拓補順序向輸入端口（CIs）進行。在整個后向遍歷的初始階段，整個網路中僅有輸出端口（COs）具有可見性，映射隊列（frontier）為空。然后，將COs加入映射隊列F，從F中取出一個結點，選擇該結點的BestCv作為該結點的映射方案（mapping solution），該BestCv將作為一個真實的AIC單元（或查找表）出現在最終電路中。而BestCv的輸入結點作為AIC單元（或查找表）的輸入端口，需要和其他的AIC單元（或查找表）進行連接，因此，具有可見性，添加到映射隊列F中。最后，不斷地重復上述過程，直到映射隊列為空。

4 實驗結果

本文在ABC程序的基礎上，進行開發實現了一款全新的AIC映射工具。新映射工具能夠支持AIC邏輯層數，獨立輸入數目，最低輸出層次和有效輸出數目等參數的可配置，而原映射工具卻不支持，因此，僅采用6-AIC為對象進行實驗對比，比較兩個映射工具映射結果的面積和速度指標。

實驗從學術界公認的兩個測試集VTR［14］和MCNC［15］中各挑選出5個具有代表性的電路作為實現的測試電路集。實驗將測試電路輸入到新/舊映射工具中得到映射結果，然后再將映射結果送到VPR［14］程序中進行物理綜合，最后得到一個面積和延時的數據值。面積恢復優化是FPGA映射過程中用于減少面積的一種有效手段，常常在進行首輪映射過程后，在進行一次或多次帶有面積恢復優化功能的映射迭代過程，從而改善映射結果的面積指標。

4.1 不帶面積恢復（area-recovery）的實驗對比

圖2展示了經過新舊兩種映射工具映射后電路在關鍵路徑延遲和占用面積值上的比較。

從圖2的可以看出，和文獻［8，9］的映射工具相比，新映射工具在電路映射結果的性能指標比原映射工具要略遜一籌，關鍵路徑延遲平均增加了4%。而圖2中展示的映射電路的面積指標卻顯示出了完全不同的趨勢，新的AIC映射工具在所有的被測電路上都具有更優的面積結果，新映射工具在映射結果的面積指標上平均提高了35%。

仔細對兩個映射工具的電路映射結果進行分析，得到以下結論：

（1）AIC單元結果具有多輸出的特性，新的映射工具在映射過程中采用貪婪算法，盡可能地去對AIC的輸出引腳進行使用，大大提高了AIC單元的利用率，從而減少了最終映射結果中6-AIC單元的總數，提高了面積指標。

（2）由于采用貪婪算法來提高AIC多輸出引腳的利用率，導致映射過程中忽略了其對關鍵路徑的影響，使得映射反向過程中造成關鍵路徑改變，從而導致關鍵路徑指標的下降。

4.2 采用面積恢復優化的實驗對比

作為映射過程提高面積性能的重要手段，新的映射工具也支持采用面積恢復優化功能來進一步提高映射結果的面積指標。圖3展示了新映射工具在開啟面積恢復優化功能前后映射結果的對比。

從圖3的數據可以看出，面積恢復優化功能確實能非常有效地提高映射結果的面積，與前一節中未使用面積恢復優化功能的映射結果相比，面積恢復優化功能平均提高了40%的面積指標。如果對映射結果數據進行深入分析，會發現與前一節的映射結果比較，開啟面積恢復優化功能后，映射工具更加偏向于選擇小的AIC單元來實現映射結果，以期進一步提升6-AIC單元的內部利用率，減少最終映射結果中所使用到6-AIC數目，提高映射結果的面積指標。然而，更好的面積指標是以降低電路的總體性能為代價的，從圖3可以看出，開啟面積恢復優化功能后，映射電路的平均性能下降了9%。

因此，從上述的數據和結果分析來看，如果設計者是以時序性能為優先設計約束，那么采用無面積恢復優化功能的映射流程能獲得相對較好的性能指標。而如果設計者更加側重于整體結果的面積參數，那么采用帶有面積恢復優化功能的映射流程會帶來非常優異的面積指標。

5 結束語

本文以開源軟件ABC的映射程序為基礎，結合AIC單元的結構特征，實現了一款全新的AIC結構映射工具。與文獻［8］中使用的映射工具相比，新的AIC映射工具具有更高的靈活性，能夠支持AIC結構單元進行更多的結構參數探索改進。除了靈活性上的改進，新的AIC映射工具在映射結果上還有35%的面積性能提升。目前映射結果與原映射工具相比，雖然在面積之比上有了很大的提高，但是在速度指標上卻略有損失，后續需要進一步改善映射結果的速度結果。

圖2 新舊映射工具的映射結果對比

圖3 新映射工具在開啟面積恢復優化功能前后電路性能和面積的對比

［1］ Ian K and Rose J. Measuring the gap between FPGAs and ASICs［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2007，26（2）：271-285.

［2］ Ngai T，Rose J，and Wilton S. An SRAM programmable field-configurable memory［C］. Proceedings of the IEEE Custom Integrated Circuits Conference，Santa Clara，CA，1995：499-502.

［3］ Rui Jia， Lin Y，Guo Z，et al.. A survey of open source processors for FPGAs［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Munich，2014：521-526.

［4］ Altera Corporation. Excalibur device overview DSEXCARM-2.0［OL］. http：//media.digikey.com/pdf/Data Sheets/Altera PDFs/EPXA1，4，10 Excalibur.pdf，2002.

［5］ Hutton M，Schleicher J，Lewis D， et al.. Improving FPGA performance and area using an adaptive logic module［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Belgium，2004：135-144.

［6］ Lewis D，Ahmed E，Baeckler G，et al.. The stratix II logic and routing architecture［C］. Proceedings of the 2005 ACM/ SIGDA 13th ACM International Symposium on Field-Programmable Gate Grrays，Monterey，2005：14-20.

［7］ Jiang Z，Lin Y，Yang L，et al.. Exploring architecture parameters for dual-output LUT based FPGAs［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Munich，2014：436-441.

［8］ Parandeh-Afshar H，Benbihi H，Novo D，et al.. Rethinking FPGAs：elude the flexibility excess of LUTs with and-inverter cones［C］. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays，Monterey，2012：119-128.

［9］ Parandeh-Afshar H，Zgheib G，Novo D，et al.. Shadow and-inverter cones［C］. IEEE International Conference on Field Programmable Logic and Applications （FPL），Porto，2013：1-4.

［10］ Zgheib G，Yang L，Huang Z，et al.. Revisiting and-inverter cones［C］. Proceedings of the 2014 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays，ACM，Monterey，2014：45-54.

［11］ Brayton R and Mishchenko A. ABC：an academic industrialstrength verification tool［C］. Computer Aided Verification，Edinburgh，2010：24-40.

［12］ Mishchenko A， Cho S，Chatterjee S，et al.. Combinational and sequential mapping with priority cuts［C］. IEEE International Conference on Computer-Aided Design，San Jose，2007：354-361.

［13］ Cong J，Wu C，and Ding Y. Cut ranking and pruning：enabling a general and efficient FPGA mapping solution［C］. Proceedings of the 1999 ACM/SIGDA Seventh International Symposium on Field Programmable Gate Grrays，Monterey，1999：29-35.

［14］ 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（TRETS），2014，7（2）：DOI：10.1145/2617593.

［15］ Yang S. Logic synthesis and optimization benchmarks User Guide， version 3.0［OL］. http：//ddd.fit.cvut.cz/prj/ Benchmarks/LGSynth91.pdf，1991.

江政泓： 男，1990年生，博士生，研究方向為FPGA架構開發、FPGA的映射算法.

林 郁： 男，1982年生，助理研究員，研究方向為FPGA架構開發、FPGA的CAD輔助設計、FPGA高層綜合、高性能計算等.

黃志洪： 男，1984年生，助理研究員，研究方向為可編程邏輯結構研究、嵌入式存儲器結構研究.

楊立群： 女，1989年生，博士生，研究方向為FPGA架構開發.

楊海鋼： 男，1960年生，研究員，研究方向為數?；旌闲盘柤呻娐吩O計、超大規模集成電路設計等.

Mapper for AIC-based FPGAs

Jiang Zheng-hong①②Lin Yu①Huang Zhi-hong①Yang Li-qun①②Yang Hai-gang①

①（System on Programmable Chip Research Department， Institute of Electronics，Chinese Academy of Sciences，Beijing 100190，China）
②（University of Chinese Academy of Sciences，Beijing 100049，China）

Exploring a new logic element of Field Programmable Gate Array （FPGA） is always a key field in FPGAs' research，while And-Inverter Cones （AIC） is the most promising one. Implementing a highly-efficient and highly-flexible mapping tool is also an important part of exploring new FPGA architecture. In this paper，a new mapper for AIC-based FPGA is implemented. Compared with an existing mapper，the new mapper has much higher flexibility，and supports adjustments of AICs' architectural parameters to assit the design space exploration of AIC. Meanwhile，the new mapper provides area results 33%～36% better than the original mapper.

Field Programmable Gate Array （FPGA）；And-Inverter Cones （AIC）；Technology mapping

TN402

A

1009-5896（2015）07-1769-05

10.11999/JEIT141403

2014-11-20收到，2015-03-16改回，2015-06-01網絡優先出版

國家自然科學基金（61404140，61271149，61106033）資助課題

*通信作者：楊海鋼 yanghg@mail.ie.ac.cn