一種基于時序的加/減法器組優(yōu)化方法

胡平科　余建德

摘要：針對現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）電路模塊中混合加/減法器組的時序優(yōu)化問題，本文提出了一種在寄存器傳輸級（Register-Transfer-Level，RTL）綜合優(yōu)化階段考慮加/減法器的輸入端口數(shù)據(jù)位時延的正負矩陣優(yōu)化方法，有效地利用了FPGA芯片中的進位鏈結構。在FPGA公司軟件工具平臺上的算法實現(xiàn)和芯片測試結果顯示，這種正負矩陣優(yōu)化方法相比于傳統(tǒng)方法取得了很好的時序優(yōu)化效果。

關鍵詞：混合加/減法器組；RTL綜合；輸入端口數(shù)據(jù)位時延；正負矩陣

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）18-0221-02

近年來云計算、人工智能等方面的技術越來越火熱，在性能、上市時間、成本、穩(wěn)定性和長期維護方面擁有先天優(yōu)勢的FPGA也備受關注。

EDA（Electronic design automation）工具作為FPGA電路設計的核心工具，采用自頂向下的設計方法。使用行為級描述語言（verilog HDL或VHDL）將用戶的需求轉換成EDA工具的輸入，再通過EDA工具的RTL綜合優(yōu)化、門級優(yōu)化、布局布線、仿真與調(diào)試等步驟，完成整個電路模塊的設計。

針對加/減法器的優(yōu)化是EDA工具在RTL綜合優(yōu)化過程中不可或缺的一部分。目前已有的針對加法器優(yōu)化的方法主要分兩類：一類是針對兩輸入端口加法器的內(nèi)部實現(xiàn)進行優(yōu)化，如超前進位加法器、進位保留加法器、進位選擇加法器等，通過優(yōu)化進位鏈上的結構來達到優(yōu)化時序的目的；另一類是針對多輸入端口加法器的輸入端口進行優(yōu)化，如樹型加法、Sklansk加法、Kogge-Stone加法、Brent-Kung加法等，通過樹型化的思想來減少路徑上的延時。本文針對電路模塊中混合加/減法器組的時序問題，提出了一種基于輸入端口數(shù)據(jù)位時延對加/減法器進行優(yōu)化的方法。它通過考慮一組可重構的加/減法器中的每一個輸入端口數(shù)據(jù)位的時延（即數(shù)據(jù)的到達時間），重新構建一組加/減法器，并替代原加/減法器組，優(yōu)化電路模塊的時序，使從加/減法器組的輸入到輸出的最大延時最小。

1加/減法器優(yōu)化時的時序問題

在RTL電路綜合過程中，對一組加/減法器進行優(yōu)化是一個很常見的問題。通常對一組加/減法器的優(yōu)化方法是，將一組加/減法器樹型化，使得邏輯電路的物理級數(shù)最小化，達到優(yōu)化RTL邏輯電路的目標。例如，有一組鏈狀的加/減法器“al+a2-a3-a4”樹型化后如式1所示：

（a1+a2）-（a3+a4） （1）

然而一個物理級數(shù)最少的電路在時序上卻不一定是最好的。例如，式1中若‘a(chǎn)l+a2計算出結果時，a3的數(shù)據(jù)已經(jīng)到達，但a4的數(shù)據(jù)仍未到達。則此時先用‘a(chǎn)l+a2的結果減去a3，然后再和a4相減，電路級數(shù)會多一級，但時序反而變好。如式2所示：

（（a1+a2）-a3）-a4 （2）

更進一步地，如果式2中的輸入端都為6位，a4[2：0]的數(shù)據(jù)比a3[2：0]先到達；a3[5：3]的數(shù)據(jù)比a4[5：3]先到達。此時式2的時序也將不再是最好的。其最好時序的運算順序如式3所示：

（（al+a2）-{a3[5：3]，a4[2：0]}）-{a4[5：3]，a3[2：0]} （3）

由此可見，在加/減法器樹型化思想的基礎之上，需要一種基于輸入端口數(shù)據(jù)位時延的加/減法器的化優(yōu)化方法，考慮每一位輸入的時延對RTL電路時序的影響，最大化地優(yōu)化RTL電路中的時序。

2基于時延的加法器進行優(yōu)化

該優(yōu)化過程是將一組加/減法器的所有輸入端口數(shù)據(jù)位放人正值和負值兩個矩陣上；然后對這兩個矩陣進行一些優(yōu)化處理（如優(yōu)化連續(xù)相同值、抵消正負值等）；最后根據(jù)輸入端口數(shù)據(jù)位的時延排序并生成多個兩輸入端加法器。其中，輸入端口數(shù)據(jù)位矩陣中的一行相當于是加法器的一個輸入端口，且高位在前；而它的列則包含了同一位置上的所有輸入端口數(shù)據(jù)位。其具體實現(xiàn)步驟如算法2-1所示。

3實驗結果分析

本文中提到的所有算法都使用C++程序設計語言實現(xiàn)。為了對比，同時實現(xiàn)了基于最短路徑的樹型加/減法器優(yōu)化算法和基于輸入端口數(shù)據(jù)位時延的加/減法器優(yōu)化算法。算法在上海安路信息科技有限公司的商用FPGA軟件工具TangDynas-ty3.0（TD3.0）上進行測試。為了測試本文中提出的算法在實際應用中的可適應性，考慮實際應用中的各種可能的情況，在本次實驗中增加了測試用例的隨機性。從兩個方面對算法的優(yōu)化結果進行對比：

一方面，加/減法器個數(shù)（num=4）不變；所有輸入端口的位寬在指定的范圍（[1，bits]）內(nèi)隨機生成，bits取值范圍為[4，128]；輸入端口的時序約束在[1ns，12ns]內(nèi)隨機生成；測試隨著指定的位寬范圍（即bits值）增大時，其時序優(yōu)化結果將如何變化。其最終的優(yōu)化結果如圖1所示。

另一方面，加/減法器的所有輸入端口的位寬在指定的位寬范圍（[1，bits]）內(nèi)隨機生成，取bits=8；輸入端口的時序約束在[1ns，10ns]內(nèi)隨機生成；測試隨著加/減法個數(shù)（hum）在[4，128]范圍內(nèi)增長時，其時序優(yōu)化結果將如何變化。其最終的優(yōu)化結果如圖2所示。

上述兩個方面的測試是在上海安路信息科技有限公司的FPGA軟件平臺TD3.0下完成的。從圖1和圖2中可以看出，slack（Timing）折線基本都在slack（Tree）折線之上，這表明在不同輸入端口的位寬或者不同加/減法器個數(shù)的情況下，基于輸入端口數(shù)據(jù)位時延的加/減法器優(yōu)化算法優(yōu)化后的最小slack普遍都要大于基于最短路徑的樹型加/減法器優(yōu)化算法優(yōu)化后的最小slack；而slack值越大說明電路模塊的時序優(yōu)化得越好。因此，基于輸入端口數(shù)據(jù)位時延的加/減法器優(yōu)化能得到更好的時序電路。

4結束語

本文針對EDA工具中的RTL綜合優(yōu)化問題展開研究。在加/減法器的時序優(yōu)化問題上，做出了以下貢獻。一方面，與針對單個加減法內(nèi)部進行優(yōu)化的超前進位加法器、進位保留加法器、進位選擇加法器等優(yōu)化方法不同，本文提出的優(yōu)化方法是針對相關聯(lián)的一組加減法器進行優(yōu)化。另一方面，與一組加減法器進行輸入端口重新組合的樹型加法、Sklansk加法、Kogge-Stone加法、Brent-Kung加法等方法不同，本文提出的優(yōu)化方法是基于所有輸入端口中的每一個數(shù)據(jù)輸入位時序來驅動優(yōu)化的，同時利用了FPGA器件中的進位鏈延時短的優(yōu)點。在FP-GA公司軟件工具平臺上的算法實現(xiàn)和芯片測試結果顯示，這種正負矩陣優(yōu)化方法相比于傳統(tǒng)方法取得了很好的時序優(yōu)化效果。endprint