劉貴宅 于芳 劉忠立 刁嵐松

(1.中國科學院 微電子研究所，北京100029;2.北京飄石科技有限公司，北京 100029)

電子設計自動化(EDA)工具是現(xiàn)場可編程門陣列(FPGA)領(lǐng)域的一個重要組成部分.隨著FPGA以其特有的優(yōu)勢逐步擴大應用領(lǐng)域，人們越來越意識到FPGA 的EDA 工具的重要性.FPGA 配套的EDA工具流程包括綜合、映射［1］、布局、布線［2］、碼流生成、碼流下載等，如圖1 所示.

圖1 FPGA EDA 流程圖Fig.1 Flowchart of FPGA EDA

寄存器傳輸級(RTL)綜合［3］處于FPGA 的EDA工具流程的最前端，將行為級的描述文件轉(zhuǎn)換為門級的網(wǎng)表，承擔了絕大部分的優(yōu)化任務，包括針對面積、時序和功耗的優(yōu)化，是FPGA 的EDA 工具重要的部分［4］，綜合結(jié)果直接影響整個設計的好壞.

RTL 綜合涉及到多個知識領(lǐng)域，包含優(yōu)化算法、計算機編譯［5］、硬件描述語言(HDL)［6］、軟件工程等，也是FPGA 的EDA 工具流程中難度最大的部分.對FPGA 綜合優(yōu)化技術(shù)的深入研究十分有意義.

RTL 綜合就是將HDL 描述的設計文件轉(zhuǎn)化為門級網(wǎng)表并優(yōu)化的過程，這個過程包括解析［7］、確立、邏輯優(yōu)化、工藝映射［8］.RTL 綜合過程中的優(yōu)化包括對時序［9］、面積［10］和功耗的優(yōu)化［11］，而優(yōu)先級的資源共享就是針對面積進行的優(yōu)化.

資源共享是時序互斥的兩個或多個相同算術(shù)邏輯單元(ALU)用同一資源實現(xiàn)的方法，是FPGA 綜合中的關(guān)鍵技術(shù)之一［12］，成熟的綜合工具Synplify(Synopsis 公司)、XST(Xilinx 公司)、Leonardo spectrum(Mentor 公司)均采用資源共享方案，但具體實現(xiàn)方案沒有公開.而開源的綜合工具(如伯克利大學的ABC［13］和Stephen Williams 團隊的Icarus［14］)均未采用資源共享方案.

文中基于中國科學院微電子研究所與北京飄石科技公司聯(lián)合開發(fā)的Verilog RTL 綜合工具HqFpga，提出了一種優(yōu)先級資源共享方法，通過改進普通的資源共享方法，將可共享的資源按照相同輸出、相同輸入、無共同端口的優(yōu)先順序依次進行共享，以減少ALU 個數(shù)，使有限的資源得到充分利用，用較小的芯片實現(xiàn)更大的設計，進而實現(xiàn)面積優(yōu)化.

1 優(yōu)先級資源共享方法

文中的資源共享是將設計描述中不同時進行的相同算符(算術(shù)操作符)按照規(guī)定的順序依次進行共享，以達到優(yōu)化的效果，屬于RTL 綜合中針對面積進行的優(yōu)化.

1.1 優(yōu)先級資源共享的約束

RTL 綜合中的優(yōu)先級資源共享方法有一些約束，主要包括以下兩部分:

(1)資源共享主要針對比較復雜的算符，如* 、+、-、/等.資源共享在減少ALU 的同時，會增加多路選擇器(MUX)，但總體資源減少，達到面積優(yōu)化的作用.對于普通的邏輯操作(如與、或操作等)，在減少邏輯操作的同時會引入MUX，總體結(jié)果面積未必減少.

(2)只有功能相同且不同時執(zhí)行的算術(shù)操作才可以進行共享，而且只有互斥分支之間功能相同的算術(shù)操作才可以用同一ALU 共享實現(xiàn).如if、else 或case語句的不同互斥分支，在某一時刻只有一個分支執(zhí)行.

1.2 優(yōu)先級資源共享的流程

優(yōu)先級資源共享就是不同分支的時序互斥的相同復雜操作按照規(guī)定的優(yōu)先級次序依次進行共享.

優(yōu)先級資源共享的實現(xiàn)偽代碼如下:

優(yōu)先級資源共享的步驟如下:

(1)收集所有if、else、case 互斥分支，這些互斥分支在某一時刻只有一個分支工作，滿足優(yōu)先級資源共享的約束.

(2)收集互斥分支之間相同的算術(shù)操作符.該步驟僅檢測收集相同的算術(shù)操作符，不考慮普通的邏輯操作符.

(3)對于檢測到的可以共享的算術(shù)操作符，優(yōu)先對輸出端口相同的算術(shù)邏輯單元進行資源共享.具有相同輸出端口的模塊，輸出端口一定會連接到同一個或同一組MUX 來選擇驅(qū)動信號，如圖2(a)所示.資源共享要先檢測輸入端是否有公用端口，若沒有公共輸入端口，則將相同的操作合并，將輸出端的MUX 分別平移到兩個輸入端口，以選擇信號驅(qū)動，如圖2(b)所示;若含有公共輸入端口，則將公共端口固定在一個輸入端口上，另一端口將輸出的MUX 平移過來，共享之后可減少ALU 的數(shù)量，如圖2(c)所示.

圖2 資源共享分解示意圖Fig.2 Schematic diagram of resource sharing decomposition

(4)對有相同輸入端口的模塊進行資源共享，其過程和步驟(3)類似，將相同的操作合并為一個操作，公共端口作為一個輸入端口，另一個輸入端口添加一個MUX 選擇輸入信號，輸出端口直接驅(qū)動兩個信號.

(5)對其他可共享的模塊進行資源共享，其過程和步驟(4)類似，分別在兩個輸入端口插入MUX來選擇驅(qū)動信號，輸出端口直接驅(qū)動兩個信號.

1.3 優(yōu)先級資源共享的優(yōu)點

改進的優(yōu)先級資源共享的優(yōu)點敘述如下.

(1)增加的MUX 數(shù)量減少

以EP1 為實例，其代碼如下:

實例EP1 不采用資源共享的綜合結(jié)果如圖3所示，包含3 個加法器和1 個MUX.

圖3 EP1 不采用資源共享的綜合結(jié)果Fig.3 Synthesis result of EP1 without resource sharing

EP1 采用非優(yōu)先級的普通資源共享方法的綜合結(jié)果如圖4 所示，ADD1 和ADD3 共享，包含2 個加法器和3 個MUX，輸入到輸出的信號延時為2 級MUX 延時+2 級加法器延時.

圖4 EP1 采用普通資源共享方法的綜合結(jié)果Fig.4 Synthesis result of EP1 using normal resource sharing method

EP1 采用優(yōu)先級資源共享方法的綜合結(jié)果如圖5所示，ADD2 和ADD3 共享，只包含2 個加法器和2 個MUX，與不采用資源共享方法相比減少了1個加法器，而與采用普通資源共享方法相比減少了1 個MUX，輸入到輸出的信號延時為1 級MUX 延時+2 級加法器延時.

圖5 EP1 采用優(yōu)先級資源共享方法的綜合結(jié)果Fig.5 Synthesis result of EP1 using priority resource sharing method

(2)避免數(shù)據(jù)流沖突錯誤

以EP2 為實例，其代碼如下:

EP2 不采用資源共享的綜合結(jié)果如圖6 所示，該網(wǎng)表包含4 個加法器和1 個MUX.

圖6 EP2 不采用資源共享的綜合結(jié)果Fig.6 Synthesis result of EP2 without resource sharing

EP2 采用非優(yōu)先級的普通資源共享方法的綜合結(jié)果如圖7 所示，ADD1 和ADD4 共享，ADD2 和ADD3 共享，與不采用資源共享方法相比減少了2 個加法器，增加了4 個MUX，還產(chǎn)生了組合回路和數(shù)據(jù)流沖突［15］的錯誤.

圖7 EP2 采用普通資源共享方法的綜合結(jié)果Fig.7 Synthesis result of EP2 using normal resource sharing method

EP2 采用優(yōu)先級資源共享方法的綜合結(jié)果如圖8所示，ADD2 和ADD4 共享，ADD1 和ADD3 共享，包含2 個加法器和3 個MUX，與不采用資源共享方法相比減少了2 個加法器且不會出現(xiàn)組合回路，與采用普通資源共享方法相比減少了2 個MUX和2 級MUX 延時.

圖8 EP2 采用優(yōu)先級資源共享方法的綜合結(jié)果Fig.8 Synthesis result of EP2 using priority resource sharing method

2 實驗結(jié)果與分析

為驗證文中優(yōu)先級資源共享方法的優(yōu)化效果，從工業(yè)界實際電路中隨機選取了8 個不同種類的電路進行測試.測試環(huán)境如下:CPU 為Intel core i7 CPU 870 2.93 GHz，內(nèi)存為4 GB，操作系統(tǒng)為Windows XP，編譯環(huán)境為Visual C ++2008.運行結(jié)果網(wǎng)表均通過ABC［13］中的驗證工具證明其與原始電路等價.

優(yōu)先級資源共享后的綜合結(jié)果和未進行資源共享的結(jié)果比較如表1 所示，主要以加法為例，比較ALU 的個數(shù).表1 表明，優(yōu)先級資源共享方法可以減少所需的ALU 個數(shù)，達到資源優(yōu)化的目的.

優(yōu)先級資源共享方法和普通資源共享方法所需的ALU 個數(shù)相同，主要是減少了MUX 的個數(shù)，進一步實現(xiàn)面積優(yōu)化，具體結(jié)果如表2 所示.

表1 優(yōu)先級資源共享前后的ALU 個數(shù)對比Table1 Comparison of ALU numbers before and after using priority resource sharing method

表2 優(yōu)先級資源共享和普通資源共享方法的MUX 個數(shù)對比Table 2 Comparison of MUX numbers between priority resource sharing method and normal resource sharing method

表2 表明，采用優(yōu)先級資源共享方法后，MUX的個數(shù)比普通資源共享方法減少了10%左右，優(yōu)化效果更好.

3 結(jié)語

針對FPGA 中算術(shù)操作資源較為復雜、占用面積大且算術(shù)單元數(shù)量有限的問題，文中通過改進普通資源共享方法，提出了資源共享的優(yōu)先級順序.該優(yōu)先級資源共享方法不僅減少了復雜ALU 的個數(shù)，而且所需的MUX 個數(shù)也比普通資源共享方法減少了10%左右，達到了面積優(yōu)化的效果.文中提出的資源共享方法僅針對ALU 進行優(yōu)化，今后將進一步研究可以同時優(yōu)化時序互斥的普通邏輯單元和共享時序互斥的實例的方法.

［1］Zhang Qianli，Chen Stanley L，Li Yan，et al.Mapper design for an SOI-based FPGA［C］∥Proceedings of the 10th IEEE International Conference on Solid-State and Integrated Circuit Technology.Shanghai:IEEE，2010:821-823.

［2］陳亮，李艷，李明，等.基于SRAM 的FPGA 導航布局布線方法實現(xiàn)與應用［J］.深圳大學學報理工版，2012，29(3):217-223.Chen Liang，Li Yan，Li Ming，et al.Implementation and application of navigated place and route for an SRAMbased FPGA［J］.Journal of Shenzhen University Science and Engineering，2012，29(3):217-223.

［3］Deniziak S.A symbolic RTL synthesis for LUT-based FPGAs［C］∥Proceedings of the 12th International Symposium on Design and Diagnostics of Electronic Circuits ＆Systems.Liberec:IEEE，2009:102-107.

［4］Piga L，Rigo S.Comparing RTL and high-level synthesis methodologies in the design of a theora video decoder IP core［C］∥Proceedings of the 5th Southern Conference on Programmable Logic.Sao Paulo:IEEE，2009:135-140.

［5］Sussman A，Lo N，Anderson T.Automatic computer system characterization for a parallelizing compiler ［C］∥Proceedings of 2011 IEEE International Conference on Cluster Computing.Austin:IEEE，2011:216-224.

［6］Chinedu O K，Genevera E C，Akinyele O O.Hardware description language (HDL):an efficient approach to device independent designs for VLSI market segments ［C］∥Proceedings of the 3rd IEEE International Conference on Adaptive Science and Technology.Abuja:IEEE，2011:262-267.

［7］Pakray P，Bandyopadhyay S，Gelbukh A.Dependency parser based textual entailment system［C］∥Proceedings of 2010 International Conference on Artificial Intelligence and Computational Intelligence.Sanya:IEEE，2010:393-397.

［8］Jeong C，Nowick S M.Technology mapping and cell merger for asynchronous threshold networks［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2008，27(4):659-672.

［9］Awan M，Harris F，Koch P.Time and power optimizations in FPGA-based architectures for polyphase channelizers［C］∥Proceedings of the Forty-Fifth Asilomar Conference on Signals，Systems and Computers.Pacific Grove:IEEE，2011:914-918.

［10］Cong J，Minkovich K.Optimality study of logic synthesis for LUT-based FPGAs［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2007，26(2):230-239.

［11］Aksoy L，Costa E，F(xiàn)lores P，et al.Optimization of area and delay at gate-level in multiple constant multiplications［C］∥Proceedings of the 13th Euromicro Conference on Digital System Design:Architectures，Methods and Tools.Lille:IEEE，2010:3-10.

［12］Mondal S，Memik S O.Resource sharing in pipelined CDFG synthesis ［C］∥Proceedings of the IEEE/ACM Asia and South Pacific Design Automation Conference.Shanghai:IEEE，2005:795-798.

［13］Berkeley Logic Synthesis and Verification Group.ABC:a system for sequential synthesis and verification，release 70319［EB/OL］.(2007-10-01)［2012-10-15］.http:∥www.eecs.berkeley.edu/～alanmi/abc/.

［14］Stephen W.Icarus:a Verilog simulation and synthesis tool［EB/OL］.(2006-12-26)［2012-10-15］.http:∥iverilog.icarus.com/.

［15］Synopsis.VHDL compiler reference manual［R］.Mountain View:Synopsis，2004.