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

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

寄存器傳輸級(jí)(register transfer level，RTL)綜合將HDL 描述的設(shè)計(jì)文件轉(zhuǎn)換為門(mén)級(jí)網(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. 開(kāi)源的工具有伯克利大學(xué)的ABC［7］、Stephen Williams 團(tuán)隊(duì)的Icarus［8］和多倫多大學(xué)的Odin［9］.

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

1 擴(kuò)展型資源共享

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

1.1 資源共享

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

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

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

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

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

1.2 向普通邏輯操作的擴(kuò)展

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

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

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

圖2 邏輯門(mén)共享步驟分解圖Fig.2 Logic resource sharing decomposition view

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

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

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

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

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

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

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

本研究不包含布爾分配率，如A＆B | A＆C =A＆(B | C)和(A| B)＆(A| C)= A| (B＆C). 因?yàn)樵撉闆r通過(guò)普通邏輯優(yōu)化已能達(dá)到較優(yōu)效果.

1.3.1 乘法和除法的分配律

該方法的擴(kuò)展包括

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

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

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

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

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

1.3.2 與門(mén)和異或門(mén)組合及或門(mén)和同或門(mén)的組合

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

同樣，對(duì)n ＞2 個(gè)與門(mén)連接到同一個(gè)異或門(mén)的情況以及n ＞2 個(gè)或門(mén)連接到同一個(gè)同或門(mén)的情況成立. 本研究證明從略.

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

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

圖5 異或門(mén)和同或門(mén)Fig.5 Logic XOR and XNOR

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

1.3.3 與門(mén)和同或門(mén)的組合，以及或門(mén)和異或門(mén)的組合

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

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

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

圖6 異或門(mén)和同或門(mén)補(bǔ)充Fig.6 Extra structure of logic XOR and XNOR

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

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

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

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

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

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

2.1 普通邏輯結(jié)果

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

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

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

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

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

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

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

2.3 時(shí)序變化

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

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

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

結(jié) 語(yǔ)

本研究針對(duì)資源共享的僅處理算術(shù)邏輯單元的局限性做了改進(jìn)和擴(kuò)展，使擴(kuò)展性資源共享可以針對(duì)普通邏輯進(jìn)行優(yōu)化;同時(shí)，突破資源共享基于mux 結(jié)構(gòu)的限制，參照廣義分配律，延伸至普通邏輯結(jié)構(gòu)，針對(duì)乘除法分配律以及特定的邏輯結(jié)構(gòu)進(jìn)行優(yōu)化，進(jìn)一步改善了FPGA 面積. 實(shí)驗(yàn)結(jié)果表明，該方法不僅可以減少算術(shù)單元的個(gè)數(shù)，也可有效減少邏輯單元的個(gè)數(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è)計(jì)［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)航布局布線方法實(shí)現(xiàn)與應(yīng)用［J］. 深圳大學(xué)學(xué)報(bào)理工版，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è)計(jì)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］. 深圳大學(xué)學(xué)報(bào)理工版，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è)，張東曉，葉梅龍，等. 專(zhuān)用集成電路高級(jí)綜合理論［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.