基于AIG 的多級邏輯電路延遲近似優化

趙維凱,于宗源,王倫耀

（寧波大學 信息科學與工程學院,浙江 寧波 315211）

隨著晶體管技術達到納米級,集成電路設計越來越復雜,通過傳統設計方法提高電路的性能變得愈發困難[1].另一方面,許多新興應用程序,例如機器學習、數據挖掘/分析和圖像處理等,其本質上是容錯的.在這種情況下,近似計算作為一種新的電路設計范式應運而生[2].其基本思想是在保證電路正常工作的情況下,通過引入誤差來修改其電路結構,從而獲得更小的面積、更低的功耗及延遲.近似計算主要分為近似電路設計以及近似邏輯綜合(Approximate Logic Synthesis,ALS)兩個方面,前者目前主要通過人工設計,對精確加法器、乘法器等電路進行近似優化[3],而后者旨在給定誤差約束條件下,為容錯應用自動生成最佳近似電路[4].

近年來,ALS 得到了研究者的廣泛關注,現有研究工作表明[5-10],利用近似計算技術,在引入較小計算誤差的情況下,能顯著地提高電路性能.文獻[5]通過尋找兩個功能近似的信號,用一個替換另一個來優化電路.文獻[6]針對文獻[5]提出了批量的精度可配置誤差估計方法,在相同誤差約束下獲得了更好的優化結果,同時縮短了程序運行時間.文獻[7]提出了一種基于深度學習的綜合流,通過在映射過程中移除或者替換網絡上的門實現電路功耗優化.文獻[8]通過搜索、獲取電路中的ACS (Approximate Care Set),并對ACS 中的節點進行近似替換,從而實現面積優化.文獻[9]通過獲取電路關鍵路徑的切割集,對其采用常量替換的方式實現電路性能優化,但常量替換的方式可能會使電路誤差激增從而無法在給定約束下獲得最優結果.文獻[10]針對關鍵路徑中的節點構建臨界誤差網絡,通過最小割的方式尋找到最優節點進行常量替換,從而實現電路延遲優化,但由于部分電路對應的解空間較大,其構建網絡過程會耗費大量運算時間.

然而,目前所提出的ALS 方法主要集中在電路面積上的優化.雖然這些ALS 方法在優化面積的同時也會降低電路延遲,但其在改善電路延遲方面的潛力并沒有被完全發掘.對于實時信號處理等應用,它們是容錯的,但對延時的要求是嚴格的[11].對于這類應用,延遲優化將成為主要目標.由于對電路全局進行近似優化十分困難,以往的ALS 方法通常對電路中某一個或幾個門不斷進行局部近似變化(Local Approximate Change,LAC),直至給定的誤差約束.在這些方法中,由于節點數量等效于電路面積且每一個節點對于電路面積的貢獻近似相同,可以認為在面積優化時任何節點的刪除都會帶來電路面積的減小.但這與電路的延遲優化思路是不相同的,因為延遲是由電路的關鍵路徑決定的,關鍵路徑指的是信號由輸入端傳遞到輸出端所經過的最長路徑,且電路的關鍵路徑往往不止一條,單純對某一條關鍵路徑進行LAC 往往無法使得電路延遲降低.因此,在每一次優化過程中要關注電路中所有的關鍵路徑,即同時縮短每一條關鍵路徑長度.為此,本文提出一種針對電路延遲優化的ALS方法.首先,根據所給定電路獲取關鍵路徑節點集.其次,針對關鍵路徑節點采取不同于常量替換的LAC 方式.本文以錯誤率作為誤差衡量標準,其估算方式采用蒙特卡洛算法[12],最后在錯誤率約束下不斷迭代獲得最優電路.實驗結果表明,與最近所提出的ALS方式相比,本文在延遲優化方面效果顯著,同時程序運行時間也存有優勢.

1 與非圖及誤差評價指標

1.1 與非圖

由于“與”“非”運算可以構成邏輯運算完備集,因此任何一個邏輯表達式都可以轉換為“與”“非”運算的表達式.與非圖(AND-Inverter-Graph,AIG)就是一種僅包含“與”和“非”運算,用來表示邏輯功能的有向無環圖[13].AIG 由二輸入與門、反相器、有向邊和輸入輸出端一同構成.以圖1 所示的C17 電路對應的AIG 為例,圖中正三角表示輸入(Primary Input,PI),倒三角表示輸出(Primary Output,PO),圓圈表示與門.AIG 中的有向連線表示節點之間存在信號輸出輸入關系,其中虛線表示對該節點的輸出信號取反,相當于接入反相器.另外,為了方便描述,通常給AIG 中的節點、PI 和PO進行編號.圖1中編號1～7為輸入,8～13為節點,22 和23 為輸出.

圖1 C17 電路AIG

一般情況下,AIG 中PI 到PO 之間存在多條路徑,其中包含節點最多的路徑稱為關鍵路徑,關鍵路徑中節點數量越多,則表示電路信號傳遞時間越長,即延遲越大.由于AIG 中的每個節點對應一個“與”運算,因此AIG 中包含的節點數越多,意味著對應的電路面積也越大.這也是基于AIG 的邏輯優化中常利用AIG 節點數和關鍵路徑長度作為電路面積和延遲評估標準的原因[14].

1.2 誤差評價指標

采用近似計算技術的邏輯優化都必須滿足給定的近似度約束.近似度有多種衡量方式,本文將錯誤率作為電路的誤差指標.

2 多級邏輯電路延遲優化算法

本文的多級邏輯電路延遲優化通過AIG 實現,并用AIG 的關鍵路徑長度來衡量邏輯電路的延遲,通過減少AIG 關鍵路徑節點數實現電路延遲優化.

2.1 獲取關鍵路徑不重復節點集

不同于面積優化,在延時優化中,首先必須考慮關鍵路徑上節點的刪除,才能達到優化延時的目的.為此,在延時優化過程中,必須先獲取當前電路的所有關鍵路徑節點集.

對于電路延遲上的優化,單單縮短一條關鍵路徑往往是不夠的.如圖1 所示的C17 電路,它一共存在節點編號為{9,10,11},{9,12,13},{9,10,13}的3 條關鍵路徑集合.例如單獨優化節點11,則無法實現電路延遲的優化.而若同時優化節點11、13,則可以使電路延遲由3 縮短到2,但意味著更多節點被優化而導致錯誤率增加.

根據C17 的關鍵路徑可以發現,所獲得的關鍵路徑存在許多重復的節點.由于本文后續需要對所有關鍵路徑節點單獨進行LAC 操作并獲得對應的錯誤率,這會使得處在不同路徑上的同一節點被重復計算.例如節點9 存在于C17 電路所有的關鍵路徑中,在計算錯誤率時會進行3 次重復的計算,而每一次優化所產生的錯誤率結果是相同的,從而造成程序運行時間增加.由此本文提出了一種獲取不重復的關鍵路徑節點方法,偽代碼如下,其中G為輸入的AIG 電路.

在step1 中,通過Col_AIG_POs 函數獲取當前輸入AIG 電路中的所有輸出端節點POs.由于電路的PO 并不一定都是關鍵路徑的起始節點,因此在step2 中通過GetNtklevel 函數獲取當前輸出端的層級,判斷輸出端層級是否與電路層級相同來選取正確的關鍵路徑起始探索節點,自頂向下搜索所有關鍵路徑集合.同時,為了避免關鍵路徑的重復記錄,step3 先判斷當前節點是否已經存在于關鍵路徑節點集中,若不存在,則將該節點進行保存;若存在,則不重復記錄.step4 中GetNextNode 函數的作用是通過當前節點獲取到關鍵路徑的下一個節點.由于AIG 中每一個節點僅有兩個對應的扇入,本算法通過判斷兩個扇入節點所處層級的大小來決定以哪一個節點作為關鍵路徑節點.若兩者不一樣大,則將層級大的節點作為關鍵路徑節點繼續進入循環,層級小的節點視為非關鍵路徑節點而舍去;若兩者一樣大,則將兩個扇入節點都作為下一次關鍵路徑的節點進行搜索.

以C17 電路為例說明算法1,從PO 端開始探索,首先節點11、13 的層級與電路層級相同,將這兩個節點作為關鍵路徑探索的首節點:

(1)以節點11 為首節點進行探索,節點8、10都為節點11 的扇入,通過判斷節點10 的level 為2,而節點8 的level 為1,將節點10 作為關鍵路徑進行保存.隨后對于節點10,同樣進行上述判斷,將節點9 保留為關鍵路徑.

(2)以節點13 為首節點進行搜索,節點10、12為節點13 的扇入節點,而節點10、12 所處層級都為2,則同時對兩個節點進行探索.由于在以節點11 為首節點探索時,節點10 已經記錄于關鍵路徑中,則不進行重復記錄,且節點10 的后續探索也已經在上一次記錄中全部完成,可以認為該路徑下的所有節點都已經被記錄.對于節點12 的扇入節點7、9,因節點9 所在層級較高,并且已經存在于關鍵路徑中,不進行重復記錄.

由此C17 電路的不重復節點集搜索已完成,該集合為{9,10,12,11,13}.

2.2 近似局部變換及錯誤率估算方法

根據AIG 節點的特性,允許某個節點擁有多個扇出端,進而可以將許多功能相同的節點合并以實現電路性能上的優化.不同于文獻[9-10]中對于節點集或者節點進行常量替換造成目標節點的所有扇入信息丟失,本文通過將目標節點在關鍵路徑上的扇入節點與扇出節點直接相連,保留了關鍵路徑上的信息,僅犧牲了非關鍵路徑上扇入節點輸入的信息,同時又避免了出現常量信號傳遞到下一個節點造成電路大量節點刪除的情況,從而以更小的錯誤率實現層級的壓縮.圖2(a)所示為C17 電路節點10 使用常量0 替換結果,節點{10,11,13}刪除,電路延遲由3 縮短為2.圖2(b)為僅對節點10 所在的關鍵路徑進行LAC 的結果.由于節點10 的扇入節點2 和9 中僅有節點9 存在于關鍵路徑中,且節點11、13 同為節點10 的關鍵路徑上的扇出,據此將節點11、13 分別與節點9 相連,忽略節點2 的輸入信息,僅刪除了節點{10,12}.相比于常量替換方法,本文的方法對電路結構的影響較小,從而控制錯誤率的增加.

圖2 關鍵節點10 不同優化方式

在本文算法中,針對每一個關鍵路徑節點,都采用上述LAC 方法獲取對應的錯誤率.在錯誤率計算方面,本文將原始電路保存,并將其與近似電路構建Miter 電路[15]后,采用文獻[8]所提供的基于蒙特卡洛算法估算電路所對應的錯誤率.

2.3 基于AIG 的邏輯電路延遲近似優化算法

本優化算法是基于錯誤率約束下的迭代優化算法,主要優化目標為在錯誤率約束下減少關鍵路徑上的節點數量.采取的策略是每一次迭代時同時縮短每一條關鍵路徑長度,以實現電路延遲優化.對于每一條關鍵路徑,刪除任意一個節點對延遲的貢獻都是相同的,使得搜索最合適的LAC節點集的空間非常龐大.假設電路的關鍵路徑長度為n,電路存在m條關鍵路徑,則需要模擬nm次才可以得到最合適的LAC 節點集.當電路規模較大時,通過上述方式來獲得最優候選集將會產生巨額的計算量.為提高運算速度,本文通過選取每一條關鍵路徑在單獨LAC 過程中產生錯誤率最低的節點,近似地將該節點作為該條關鍵路徑中的最優解節點.該方法雖然無法獲取到最優的近似結果,但是極大程度上縮短了尋找合適節點集的過程,減少了程序運行時間.

算法2 為錯誤率約束下基于近似計算技術的AIG 電路延遲優化代碼,其中G為輸入的AIG 原始電路,et為優化過程中電路允許的最大錯誤率.

算法2 Delay_opt(G,et)

在step1 中首先將最原始電路保存,用于每一次進行LAC操作后計算對應的錯誤率.在step2中,先獲取待優化電路的不重復關鍵路徑節點集合,并通過GetLAC_ER 函數計算每一個不重復節點單獨進行LAC 后對應的錯誤率.在step3 中選出每一條關鍵路徑對應的錯誤率最低節點,構成LAC 節點集.利用step3 得到的LAC 節點集,在step4 中對該節點集每一個節點同時進行LAC 操作,計算當前電路相對原始電路的錯誤率.若錯誤率超出約束,則放棄本次嘗試,將上一次優化的電路作為最終結果,輸出錯誤率以及近似優化電路;若沒有超出錯誤率,則繼續進行新的一輪循環.

同樣以C17 電路為例進行說明,由于該電路規模較小,本文僅以一輪模擬進行演示.根據算法1 得到C17 不重復關鍵路徑集合為{9,10,12,11,13},計算出單獨刪除上述節點時對應的錯誤率分別為{0.1875,0.59375,0.4375,0.8125,0.8125},選取每一條路徑中錯誤率最小的LAC節點,可以發現節點9存在于所有關鍵路徑中,且該節點在對應的關鍵路徑中錯誤率都是最小的,由此僅需對節點9 進行LAC.從圖1 可以看到與節點9 相連的扇出節點10、12 都是關鍵路徑上的節點,而節點9 的扇入節點都為輸入端節點,由于本文的輸入模式為均勻輸入,則隨機選擇一個輸入端與扇出端相連,同時對兩條關鍵路徑進行LAC,優化后的結果如圖3所示.可以發現,按照本文的方法,僅以刪除一個節點的代價將電路關鍵路徑長度由3 降低到了2.

圖3 C17 電路針對節點9 優化結果

3 實驗結果分析

本文提出的優化算法用C++語言編程實現并結合邏輯綜合工具ABC[16]完成電路延遲優化.運行環境: 處理器頻率2.6 GHz,內存16 GB,操作系統為Ubuntu 20.04.由于輸入電路可能存在冗余結構,因此對于每一個輸入電路都先用ABC 中的“resyn2”優化命令進行預處理,該命令為ABC 中內置的電路精確優化腳本命令,以提高程序優化的效率.

表1 為本次實驗中所需用到的LGsynth91[17]和ISCAS85 測試電路,其中的“面積”與“延遲”為經ABC 腳本命令優化后,用MCNC[17]通用標準單元庫映射所得到的結果,I/Os 表示該電路對應的輸入與輸出的端口數量.

表1 本文使用的測試電路信息

在錯誤率計算時,假設所有PI 輸入分布為均勻分布,通過生成百萬級別的輸入向量對近似電路進行測試,使得當前電路計算所得到的錯誤率與真實錯誤率相近,以保證實驗結果的準確性.實驗中優化程度用優化率O表示,

式中,Corg和Capp分別為原始電路和近似電路對應的面積或延遲.

表2 是本文算法與文獻[9]的對比結果,錯誤率設置與文獻[9]相同,都為25%,采用的測試電路為LGSynth91,在錯誤率約束下對AIG 電路優化完成后,再通過“amap”命令進行映射獲取最終面積及延遲.從表2 中可以發現,本文方法相較文獻[9]在面積和延遲優化上分別提升了22.96%和31.49%.同時文獻[9]中有部分電路在25%錯誤率下無法進行任何延遲和面積上的優化,這是由于其對于關鍵路徑節點或者節點集進行常量替換過程可能會造成大量節點刪除,從而導致電路錯誤率激增,無法在錯誤率約束下實現優化.而本文的LAC 方式對于電路結構影響較小,可以很好地控制錯誤率的增加,從而獲得優于文獻[9]的近似電路.

表2 本文算法與文獻[9]結果比較 %

表3 為本文算法與文獻[10]對比的結果,測試電路為ISCAS85 電路.文獻[10]結果通過該文章在GitHub 中開源的代碼測試,錯誤率約束設置為15%.由于本文與文獻[10]都是采用蒙特卡洛算法來估算錯誤率,優化電路結果存在隨機性,因此對測試電路都進行了3 次測試,取對應平均值作為最終優化結果.

從表3 中可以看出,本文算法面積優化相較于文獻[10]減少了1.15%,而延遲優化提升了1.67%,可以看作在面積與延遲優化效果相近,但是本文程序的運行時間相較于文獻[10]平均縮短了61.88%.這是由于本文僅將所有關鍵路徑中錯誤率最小的節點作為本輪優化過程中最優的LAC 節點集,并且獲取所有不重復關鍵路徑節點并計算其對應的錯誤率,減少了錯誤率的重復計算.而文獻[10]通過構建臨界誤差網絡來選擇該輪最優LAC 節點時,相較于本文直接選取錯誤率最低的節點,將會耗費更多的時間.從實驗結果來看,文獻[10]與本文算法所得到的電路優化結果近似相同,但其在部分電路測試中無法很好地逼近錯誤率上界.例如C7552 電路,文獻[10]僅能得到平均錯誤率為7.4%的優化結果,無法逼近錯誤率閾值進而無法獲得較好的近似電路.而對于C1355 電路優化,兩個方式得到的近似優化結果都幾乎將所有節點刪除,但由于本文算法每一次迭代中節點刪除數量相較于常量替換較少,導致全部節點刪除需要消耗多輪LAC,因此對于該電路程序運行時間要高于文獻[10].

表3 本文算法與文獻[10]結果比較

4 結語

本文提出了一種基于AIG 在錯誤率約束下實現多級邏輯電路延遲優化的綜合流.該優化方法獲取目標電路所有關鍵路徑并收集其中對應的不重復節點.在電路延遲優化過程中,為了避免常量替換造成的電路錯誤率激增,提出了一種針對關鍵路徑節點的LAC 方式.通過該方式,對所有不重復的關鍵路徑節點集進行LAC 并記錄其對應的錯誤率.為了縮短程序運行時間,將每一條關鍵路徑中錯誤率最低的節點近似地作為最優LAC 節點,基于此以迭代的方式不斷循環直至超過錯誤率約束,得到最終的近似電路.本文算法相對已提出的針對面積以及延遲的常量替換方式,在電路性能和程序運行時間上有著顯著的提升.