劉貴宅 于芳 劉忠立 刁嵐松

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)對(duì)有相同輸入端口的模塊進(jìn)行資源共享，其過(guò)程和步驟(3)類(lèi)似，將相同的操作合并為一個(gè)操作，公共端口作為一個(gè)輸入端口，另一個(gè)輸入端口添加一個(gè)MUX 選擇輸入信號(hào)，輸出端口直接驅(qū)動(dòng)兩個(gè)信號(hào).

(5)對(duì)其他可共享的模塊進(jìn)行資源共享，其過(guò)程和步驟(4)類(lèi)似，分別在兩個(gè)輸入端口插入MUX來(lái)選擇驅(qū)動(dòng)信號(hào)，輸出端口直接驅(qū)動(dòng)兩個(gè)信號(hào).

1.3 優(yōu)先級(jí)資源共享的優(yōu)點(diǎn)

改進(jìn)的優(yōu)先級(jí)資源共享的優(yōu)點(diǎn)敘述如下.

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

以EP1 為實(shí)例，其代碼如下:

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

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

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

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

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

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

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

以EP2 為實(shí)例，其代碼如下:

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

［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 導(dǎo)航布局布線(xiàn)方法實(shí)現(xiàn)與應(yīng)用［J］.深圳大學(xué)學(xué)報(bào)理工版，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.