趙維凱,于宗源,王倫耀

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

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

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

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

1 與非圖及誤差評價指標

1.1 與非圖

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

圖1 C17 電路AIG

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

1.2 誤差評價指標

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

2 多級邏輯電路延遲優(yōu)化算法

本文的多級邏輯電路延遲優(yōu)化通過AIG 實現(xiàn),并用AIG 的關(guān)鍵路徑長度來衡量邏輯電路的延遲,通過減少AIG 關(guān)鍵路徑節(jié)點數(shù)實現(xiàn)電路延遲優(yōu)化.

2.1 獲取關(guān)鍵路徑不重復(fù)節(jié)點集

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

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

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

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

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

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

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

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

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

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

圖2 關(guān)鍵節(jié)點10 不同優(yōu)化方式

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

2.3 基于AIG 的邏輯電路延遲近似優(yōu)化算法

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

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

算法2 Delay_opt(G,et)

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

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

圖3 C17 電路針對節(jié)點9 優(yōu)化結(jié)果

3 實驗結(jié)果分析

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

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

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

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

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

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

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

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

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

表3 本文算法與文獻[10]結(jié)果比較

4 結(jié)語

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