劉貴宅，于 芳，劉忠立，刁嵐松，吳 洋

1)中國科學(xué)院微電子研究所，北京100029;2)中國科學(xué)院大學(xué)物理學(xué)院，北京100049;3)飄石科技有限公司，北京100029

寄存器傳輸級(register transfer level，RTL)綜合將HDL 描述的設(shè)計文件轉(zhuǎn)換為門級網(wǎng)表并進(jìn)行優(yōu)化［1］，是FPGA EDA 工具［2-3］的重要組成部分，包括解析(parse)［4］、確立(elaborate)、邏輯優(yōu)化(logic optimization)和工藝映射 (technology mapping)［5-6］. 目前較成熟的綜合工具有Synopsis 的Synplify、Xilinx 的XST 及Mentor 的Leonardo Spectrum. 開源的工具有伯克利大學(xué)的ABC［7］、Stephen Williams 團(tuán)隊的Icarus［8］和多倫多大學(xué)的Odin［9］.

RTL 綜合中的優(yōu)化包括針對面積、時序和功耗的優(yōu)化. 面積優(yōu)化是綜合優(yōu)化的重點之一，面積優(yōu)化的好壞是衡量綜合工具優(yōu)劣的一個重要指標(biāo). 資源共享是將兩個或多個時序互斥且功能相同的算術(shù)邏輯單元(arithmetic logic unit，ALU)進(jìn)行合并共享，是FPGA 面積優(yōu)化的關(guān)鍵技術(shù)之一. Synopsis的VHDL compiler Reference Manual 顯示其VHDL compiler 資源共享是基于MUX 針對算術(shù)操作進(jìn)行的優(yōu)化［10］. 商用工具Synplify、XST 和Leonardo spectrum 雖均采用資源共享，但也僅共享算術(shù)單元，且未見具體實現(xiàn)方案. 開源工具包括伯克利大學(xué)的ABC、Stephen Williams 團(tuán)隊的Icarus 及多倫多大學(xué)的Odin 均未采用資源共享方案.

1 擴展型資源共享

本研究基于中國科學(xué)院微電子研究所與飄石科技有限公司聯(lián)合開發(fā)的RTL 綜合工具HqFpga. 擴展型資源共享通過改進(jìn)資源共享，不僅可用于算術(shù)運算，同樣適用于普通邏輯運算，且該方法不局限于基于多路選擇器(multiplexer，MUX)結(jié)構(gòu)，還可實現(xiàn)其他結(jié)構(gòu)的算術(shù)操作優(yōu)化及邏輯優(yōu)化.

1.1 資源共享

資源共享滿足兩個約束:①共享的操作時序互斥;②可共享的操作是相同的算術(shù)操作.

首先檢測并收集時序互斥的分支，包括if、else 分支和case 分支，以及結(jié)構(gòu)級HDL 語言描述連接到MUX 的不同分支. 然后檢測每組互斥分支中相同的算術(shù)操作，將這2 個或多個相同的算術(shù)操作用1 個ALU 來實現(xiàn).

圖1 (a)中2 個加法操作時序互斥，滿足資源共享的兩個約束，A、B、C 和D 為數(shù)據(jù)輸入，cond為MUX 的選擇輸入端，Z 為輸出端. 共享過程將2個(或多個)加法操作合并，用1 個加法單元實現(xiàn)，并將輸出端的MUX 平移到輸入端選擇驅(qū)動信號，如圖1 (b)和圖1 (c).

圖1 資源共享步驟分解圖Fig.1 Resource sharing decomposition view

資源共享著眼于時序互斥且功能相同的算術(shù)操作，能減少算術(shù)單元的數(shù)量，實現(xiàn)面積優(yōu)化［12］.

1.2 向普通邏輯操作的擴展

資源共享只針對復(fù)雜算術(shù)操作，如+、 -、 ×和÷等，并不優(yōu)化普通邏輯單元. 該方法可擴展到對邏輯單元進(jìn)行共享，優(yōu)化所有二元邏輯操作，包括與、或、異或、同或、與非及或非.

對普通邏輯門共享擴展的實現(xiàn)和資源共享類似，需滿足約束:①所有可共享的分支是時序互斥的;②可共享的n ≥2 個操作的邏輯操作相同;③可共享的邏輯操作有1 個公共輸入端口. 只有滿足上述約束的邏輯資源共享，其資源共享后的邏輯單元數(shù)量才會減少，面積才會被優(yōu)化.

以n = 2 時的與門為例，說明共享過程. 如圖2 (a)的網(wǎng)表結(jié)構(gòu)，2 個與門有1 個公共輸入端A，且時序互斥，滿足上述3 個約束. 邏輯門共享過程和資源共享類似，將2 個可共享與門操作合并為1個與門，并將公共輸入端連接到與門的一個輸入端口，將輸出端的MUX 連接到與門的另一輸入端來選擇與門非公共輸入端的驅(qū)動信號，見圖2 (b)和圖2 (c).

圖2 邏輯門共享步驟分解圖Fig.2 Logic resource sharing decomposition view

當(dāng)n = 2 時，該邏輯共享方法對ASIC 綜合優(yōu)化效果明顯，但對于FPGA 綜合，優(yōu)化前后如圖2(a)和圖2 (c)均可用1 個LUT4 實現(xiàn)，并未減少LUT 數(shù)，即未實現(xiàn)面積優(yōu)化.

但是，對于n ≥3 個與門合并成1 個與門的情況，該邏輯共享方法的優(yōu)化效果明顯. 如圖3，n(此例n =4)個與門可合并為1 個與門，優(yōu)化前的網(wǎng)表如圖3 (a)，4 個LUT2 和1 個MUX4 (2 個LUT4 實現(xiàn))，優(yōu)化結(jié)果如圖3 (b)，實現(xiàn)僅用1 個LUT2 和1 個MUX4 (2 個LUT4 實現(xiàn))，優(yōu)化后減少3 個LUT2. 在FPGA 實現(xiàn)中，LUT2 最終都是由LUT4 實現(xiàn)，因此該實例優(yōu)化后的結(jié)果是減少了3個LUT4. 網(wǎng)表結(jié)構(gòu)中與門數(shù)目越多，優(yōu)化效果越明顯.

圖3 邏輯門共享結(jié)果Fig.3 Result of logic resource sharing

擴展型資源共享方法著眼于基本邏輯門，在減少算術(shù)單元個數(shù)的同時也減少普通邏輯單元的數(shù)量，進(jìn)而減少LUT 數(shù)量，實現(xiàn)面積優(yōu)化.

1.3 向非MUX 結(jié)構(gòu)優(yōu)化的擴展

資源共享是基于MUX 結(jié)構(gòu)進(jìn)行的優(yōu)化，而擴展型資源共享擴展到非MUX 結(jié)構(gòu)的算術(shù)優(yōu)化及邏輯優(yōu)化，仿照乘法分配律進(jìn)行，實現(xiàn)表達(dá)式優(yōu)化及邏輯優(yōu)化效果.

本研究除了對乘法分配律進(jìn)行優(yōu)化，還參照廣義分配律［11］，延伸至布爾邏輯，針對滿足分配律結(jié)構(gòu)的布爾網(wǎng)表進(jìn)行優(yōu)化. 該擴展只支持幾種情況，主要包括:①乘法和除法分配律;②與門和異或門的組合，以及或門和同或門的組合;③與門和同或門的組合，以及或門和異或門的組合.

本研究不包含布爾分配率，如A＆B | A＆C =A＆(B | C)和(A| B)＆(A| C)= A| (B＆C). 因為該情況通過普通邏輯優(yōu)化已能達(dá)到較優(yōu)效果.

1.3.1 乘法和除法的分配律

該方法的擴展包括

以式(1)為例說明共享過程. A × B + A × C 在RTL 正常綜合的結(jié)果如圖4 (a)，由2 個乘法器和1個加法器組成，A、B、C 為輸入，Z 為輸出. 共享過程首先檢測待優(yōu)化的網(wǎng)表是否滿足以下網(wǎng)表結(jié)構(gòu):①n ≥2 個乘法器連接到同一個加法器(或減法器)的輸入端;②滿足條件①的乘法器有公共輸入端.

如圖4 (b)，共享過程首先將n(此例n = 2)個乘法器合并為1 個，將公共輸入端A 連接到乘法器的1 個輸入端;然后將輸出端的加法器平移到輸入端，連接非公共輸入端驅(qū)動信號B 和C.

圖4 乘法分配律Fig.4 Distributive law of multiplication

乘法分配率優(yōu)化結(jié)果如表1，優(yōu)化后比優(yōu)化前減少1 個乘法器，加法器位寬亦減少，乘法器的位寬不變或增加1 位. 這說明該方法可針對算術(shù)運算中乘除法的分配率進(jìn)行優(yōu)化，通過減少乘法和除法的復(fù)雜算術(shù)單元個數(shù)，達(dá)到面積優(yōu)化效果，且n 值越大，優(yōu)化效果越明顯.

表1 乘法分配率優(yōu)化前后結(jié)果對比Table 1 Comparison of the results of before and after the optimization of distributive law of multiplication sharing

1.3.2 與門和異或門組合及或門和同或門的組合

擴展型資源共享還針對異或門和同或門的特定結(jié)構(gòu)網(wǎng)表進(jìn)行優(yōu)化，如式(5)和式(6)，其結(jié)構(gòu)類似布爾定律中的分配率.

同樣，對n ＞2 個與門連接到同一個異或門的情況以及n ＞2 個或門連接到同一個同或門的情況成立. 本研究證明從略.

共享過程和乘法分配率類似，以式(5)說明共享過程. (A＆B)^(A＆C)在RTL 綜合中正常的綜合結(jié)果如圖5 (a)，2 個與門連接到同一個異或門，A、B和C 為輸入端，Z 為輸出端. 共享過程首先檢測滿足以下兩點的網(wǎng)表結(jié)構(gòu):①n ≥2 個與門連接到同一個異或門的輸入端;②滿足條件①的與門有1 個公共輸入端.

檢測到滿足上述結(jié)構(gòu)的網(wǎng)表，如圖5 (a)，將n(此例n =2)個與門合并成1 個與門，公共輸入端A 連接到與門的一個輸入;將異或門前移只與門的輸入端，異或門的輸入端連接2 個與門的非公共輸入端的驅(qū)動信號B 和C，共享后的結(jié)果如圖5 (b)，比優(yōu)化前減少了1 個與門.

圖5 異或門和同或門Fig.5 Logic XOR and XNOR

該實例表明，擴展型資源共享針對異或門和同或門的特定電路進(jìn)行優(yōu)化，減少了與門和或門的邏輯單元個數(shù). 當(dāng)n = 2 時，對ASIC 綜合實現(xiàn)面積優(yōu)化，而對FPGA 綜合結(jié)果沒影響，優(yōu)化前后均用1個LUT3 實現(xiàn). 但當(dāng)n ≥4 時，對于FPGA 綜合，結(jié)果會減少LUT 數(shù)，且n 越大，減少的LUT 數(shù)越多，面積優(yōu)化效果越明顯.

1.3.3 與門和同或門的組合，以及或門和異或門的組合

該組2 種情況分別可化作1.3.2 節(jié)的2 種情況和1 個反相器的組合，可按照1.3.2 節(jié)的共享方法對本節(jié)的2 種組合進(jìn)行共享.

該方法和1.3.2 節(jié)類似，以式(7)說明共享過程. (A＆B)^ ～(A＆C)在RTL 綜合中正常的綜合結(jié)果如圖5 (a)，n ≥2 個與門連接到同一個同或門，A、B、C 為輸入，Z 為輸出. 共享過程首先檢測滿足以下兩點的網(wǎng)表結(jié)構(gòu):①n ≥2 個與門連接到同一個同或門的輸入端;②滿足條件①的與門有一個公共輸入端.

檢測到滿足上述結(jié)構(gòu)的網(wǎng)表，如圖6 (a)，將同或門用一個異或門和一個反相器的組合實現(xiàn)，如圖6 (b)，然后按照1.3.2 節(jié)的方法實現(xiàn)共享. 共享后的結(jié)果如圖6 (c)，比優(yōu)化前減少了一個與門.

圖6 異或門和同或門補充Fig.6 Extra structure of logic XOR and XNOR

結(jié)果表明，本研究針對異或門和同或門的特定電路優(yōu)化進(jìn)行補充，更好的實現(xiàn)了面積優(yōu)化.

1.4 實現(xiàn)方案及流程

以上不同的結(jié)構(gòu)均可用統(tǒng)一的方案實現(xiàn). 實現(xiàn)過程如圖7.

圖7 擴展性資源共享實現(xiàn)代碼Fig.7 Expanded resource sharing code

代碼第1 行是遍歷整個網(wǎng)表，收集所有滿足結(jié)構(gòu)的網(wǎng)表，只有滿足結(jié)構(gòu)的網(wǎng)表才能進(jìn)行優(yōu)化;第3 行for 循環(huán)遍歷每組可優(yōu)化的網(wǎng)表結(jié)構(gòu);第4 行和第5 行是對每組可進(jìn)行優(yōu)化的網(wǎng)表進(jìn)行優(yōu)化，先將多個可合并的單元合并為一，將另一類型的單元向前平移;連接輸入輸出端信號，完成整個優(yōu)化過程.

2 實驗結(jié)果

2.1 普通邏輯結(jié)果

為驗證本擴展型資源共享的優(yōu)化效果，從開源benchmark MCNC［13］和IWLS［14］中隨機選取12 個不同種類的邏輯電路進(jìn)行測試. 測試所用CPU 為Intel core i7 CPU870 2.93 GHz，內(nèi)存4 Gbit，操作系統(tǒng)為Windows XP，編譯環(huán)境為Visual C++2008. 運行結(jié)果網(wǎng)表均通過ABC 驗證證明與原始電路等價.

實驗結(jié)果和伯克利大學(xué)的ABC 的結(jié)果LUT 數(shù)對比如表2. 實例s5378、C7552 和x3 中的設(shè)計文件多為不適合該方法優(yōu)化的電路結(jié)構(gòu)，因此該方法對這3 個實例的優(yōu)化效果不佳. 但實現(xiàn)總體結(jié)果和ABC 對比，采用同一組實例，資源LUT 數(shù)平均比ABC 的少19.1%，實現(xiàn)邏輯單元面積優(yōu)化.

表2 資源共享擴展方案與ABC 邏輯結(jié)果對比Table 2 Logic comparison between expanding resource sharing and ABC

2.2 算術(shù)結(jié)果

為驗證算術(shù)邏輯的優(yōu)化效果，本研究從工業(yè)界實際電路中隨機選取了12 個不同種類的電路進(jìn)行測試，比較優(yōu)化前后算術(shù)邏輯單元數(shù)，結(jié)果見表3.

表3 資源共享擴展優(yōu)化前后結(jié)果對比Table 3 Arithmetic comparison between with and without Expanding resource sharing

結(jié)果顯示擴展型資源共享后的算數(shù)單元數(shù)比共享前平均減少13.0%，實現(xiàn)算數(shù)單元面積優(yōu)化.

2.3 時序變化

為驗證本算法對電路時序的優(yōu)化效果，從工業(yè)界實際電路中隨機選取10 個不同種類的電路進(jìn)行測試，比較優(yōu)化前后電路工作頻率，如表4.

表4 資源共享擴展優(yōu)化前后時序結(jié)果對比Table 3 Timing comparison between with and without expanding resource sharing

由表4 可知，擴展型資源共享在減少面積的同時，時序性能也有明顯提升.

結(jié) 語

本研究針對資源共享的僅處理算術(shù)邏輯單元的局限性做了改進(jìn)和擴展，使擴展性資源共享可以針對普通邏輯進(jìn)行優(yōu)化;同時，突破資源共享基于mux 結(jié)構(gòu)的限制，參照廣義分配律，延伸至普通邏輯結(jié)構(gòu)，針對乘除法分配律以及特定的邏輯結(jié)構(gòu)進(jìn)行優(yōu)化，進(jìn)一步改善了FPGA 面積. 實驗結(jié)果表明，該方法不僅可以減少算術(shù)單元的個數(shù)，也可有效減少邏輯單元的個數(shù)，更好的實現(xiàn)面積優(yōu)化.

/ References:

［1］Xia Yuwen. The Design of Verilog HDL Digital ［M］.2nd edition. Beijing:Electronic Industry Press，2004:201-215.(in Chinese)夏宇聞. Verilog HDL 數(shù)字設(shè)計［M］. 2 版. 北京:電子工業(yè)出版社，2004:201-215.

［2］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. (in Chinese)陳 亮，李 艷，李 明，等. 基于SRAM 的FPGA導(dǎo)航布局布線方法實現(xiàn)與應(yīng)用［J］. 深圳大學(xué)學(xué)報理工版，2012，29(3):217-223.

［3］Zhang Feng，Li Yan，Han Xiaowei，et al. Design and implementation of an integrated multi-level FPGA design system ［J］. Journal of Shenzhen University Science and Engineering，2012，29(5):377-385.(in Chinese)張 峰，李 艷，韓小煒，等. 用于FPGA 的多層次集成設(shè)計系統(tǒng)的設(shè)計與實現(xiàn)［J］. 深圳大學(xué)學(xué)報理工版，2012，29(5):377-385.

［4］ Cheng Tina. Sieve:An XML-based Structural Verilog Rules Check Tool ［D］. Cambridge (USA):Massachusetts Institute of Technology，2003:25-29.

［5］Liu Mingye，Zhang Dongxiao，Ye Meilong，et al. The Theory of ASIC High Level Synthesis ［M］. Beijing:Beijing Institute of Technology Press，1998:179-246.(in Chinese)劉明業(yè)，張東曉，葉梅龍，等. 專用集成電路高級綜合理論［M］. 北京:北京理工大學(xué)出版社，1998:179-246.

［6］Zhang Qianli，Chen S L C，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 (China):IEEE Press，2010:821-823.

［7］Berkeley Logic Synthesis and Verification Group. ABC:a system for sequential synthesis and verification ［DB/OL］. Berkeley (USA ): University of California.(2005-07-29) ［2012-10-15］. http://www.eecs.berkeley.edu/ ～alanmi/abc/.

［8］Stephen Williams. Icarus:a Verilog simulation and synthesis tool ［CP/OL］. (2006-12-26) ［2012-10-15］.http://iverilog.icarus.com/.

［9］Jamieson P，Kent K B，Gharibian F，et al. Odin II:an open-source Verilog HDL synthesis tool for CAD research.proceedings ［C］// Proceedings of the 18th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines. Washington: IEEE Computer Society，2010:149-156.

［10］ Synopsis. VHDL Compiler Reference Manual ［M］.Mountain View (USA):Synopsys，2004.

［11］ Aji S，McEliece R. The generalized distributive law［J］. IEEE Transactions on Information Theory，2000，46(2):325-343.

［12］Mondal S，Memik S ?gˇrenci. Resource sharing in pipelined CDFG synthesis ［C］// Proceedings of the Asia and South Pacific Design Automation Conference. New York:ACM，2005:795-798.

［13］Yang Saeyang. Logic Synthesis and Optimization Benchmarks User Guide Version 3.0 ［M］. Research Triangle Park:Microelectronics Center of North Carolina (MCNC)，1991.

［14］Albrecht C. IWLS 2005 Benchmarks ［M］. Lake Arrowhead (USA):［s.n.］，2005.