賦權(quán)超圖多水平粗化階段的節(jié)點匹配策略

賦權(quán)超圖多水平粗化階段的節(jié)點匹配策略

1問題的數(shù)學(xué)模型電路劃分主要用于大規(guī)模電路設(shè)計的封閉性和集成，這是電路設(shè)計的一個重要環(huán)節(jié)。為了將電路單元劃分到電路子集上,必須從圖論和組合理論的角度來建立VLSI劃分問題的數(shù)學(xué)模型,文獻(xiàn)提出用無向賦權(quán)圖描述電路。文獻(xiàn)給出了無向賦權(quán)圖、交點圖、有向圖等數(shù)學(xué)模型建立電路構(gòu)造圖的過程。文獻(xiàn)基于電路劃分的需求,給出了ISPD98電路網(wǎng)表和VLSI設(shè)計到無向賦權(quán)圖的轉(zhuǎn)換算法和系統(tǒng),目的在于將電路劃分問題轉(zhuǎn)換為無向賦權(quán)圖劃分優(yōu)化問題。相比圖而言,賦權(quán)超圖為VLSI劃分提供了更為精確的模型:每條超邊可以連接2個以上的節(jié)點,對應(yīng)于電路單元間的連線可以連接2個以上的電路單元。然而,對于給定的賦權(quán)超圖,一般在合理的時間內(nèi)不可能給出最優(yōu)劃分。由于該問題的重要性,導(dǎo)致了大量的啟發(fā)式方法計算該問題的近似最優(yōu)解。這些方法大致分為以下幾類:即遷移方法、幾何方法、組合方法、譜方法、元胞自動機(jī)方法和多水平方法。本文給出了賦權(quán)超圖劃分優(yōu)化問題的形式化描述,闡述了基于多水平方法的賦權(quán)超圖劃分優(yōu)化算法。2超圖排序和節(jié)點匹配策略的權(quán)限2.1節(jié)點的非負(fù)權(quán)值的定義定義1對于一賦權(quán)超圖HG=(V,Eh),其中,V={vi|1≤i≤n},Eh={ejh|ejh?V,1≤j≤m}?，F(xiàn)將超圖HG的節(jié)點集合V劃分為2個節(jié)點子集V1和V2,滿足V1∪V2=V和V1∩V2=?,稱該劃分P={V1,V2}為超圖的二劃分。定義2用S:V→R定義節(jié)點的非負(fù)權(quán)值,即S(Vi)表示節(jié)點Vi的權(quán)值。用W:E→R定義超邊的非負(fù)權(quán)值,即W(ejh)表示超邊ejh的權(quán)值。定義3給定平衡約束參數(shù)r,對于一賦權(quán)超圖HG=(V,Eh),超圖二劃分優(yōu)化問題是尋找劃分P={V1,V2},使得該劃分的割切最小化,即目標(biāo)函數(shù)記為MIN(cut(P)),且同時滿足約束條件2.2多水平粗化階段的多節(jié)點優(yōu)化設(shè)計雖然超圖劃分技術(shù)不斷發(fā)展,但超圖劃分問題的規(guī)模也在不斷地增長,甚至需要劃分節(jié)點數(shù)目達(dá)到數(shù)百萬個的超大圖。這對超圖劃分的速度、準(zhǔn)確性、劃分能力有了更高程度的要求。多水平方法是近些年發(fā)展起來的劃分技術(shù),該方法基于多水平思想,包含粗化、初始劃分和遷移優(yōu)化3個階段。在粗化階段,將某些超圖節(jié)點結(jié)合在一起,得到下一級粗化超圖,重復(fù)此過程直到粗化超圖足夠小為止,即得到一個最小超圖。然后對該最小超圖進(jìn)行對分,得到一個初始劃分。因為這個粗化超圖很小,所以計算初始劃分時間也很短。最后,將劃分從最小超圖投影回初始超圖,在每一水平層的粗化超圖中對劃分進(jìn)行遷移優(yōu)化。在多水平粗化階段,節(jié)點匹配的策略有很多。從節(jié)點合并的角度,可以分為邊策略(Edgescheme,EDGE)、超邊策略(Hyper-Edgescheme,HEDGE)、改進(jìn)的超邊策略(ModifiedHyper-Edgescheme,MHEDGE)等節(jié)點匹配策略;從節(jié)點選擇的角度,可以分為隨機(jī)匹配(RandomMatching,RM)、首次匹配(FirstChoicescheme,FC)、貪心的首次匹配(GreedyFirstChoicescheme,GFC)、混合模式的首次匹配(HybridFirstChoicescheme,HFC)等節(jié)點匹配策略。2.3本一級粗化超圖的生成RM隨機(jī)匹配策略的時間復(fù)雜度是,其具體實現(xiàn)步驟如下:步驟1標(biāo)注超圖中所有節(jié)點處于未匹配狀態(tài)。步驟2隨機(jī)訪問超圖中未匹配的節(jié)點v,執(zhí)行下一步。步驟2.1如果節(jié)點v存在部分鄰接節(jié)點處于未匹配狀態(tài),那么隨機(jī)選取處于沒有匹配狀態(tài)的鄰接節(jié)點u和節(jié)點v匹配,且標(biāo)注這2個節(jié)點為匹配狀態(tài)。步驟2.2如果節(jié)點v所有鄰接匹配節(jié)點處于匹配狀態(tài),那么節(jié)點v仍處于未匹配狀態(tài),在粗化過程中直接拷貝到下一級粗化超圖中。步驟3重復(fù)步驟2,直至訪問所有節(jié)點,結(jié)束。2.4節(jié)點匹配算法重邊匹配算法(HeavyEdgeMatching,HEM)基于最大化減少所有超邊權(quán)值之和的思想,在選取處于沒有匹配狀態(tài)的鄰接節(jié)點u和節(jié)點v匹配時,采取貪心原則選取最大連接權(quán)值的鄰接節(jié)點。值得注意的是,由于超圖中每條超邊eh可以連接2個以上節(jié)點,于是將每條超邊中的個節(jié)點看作是在每2個節(jié)點之間存在著一條權(quán)值為的邊,因此節(jié)點v和鄰接節(jié)點u的連接權(quán)值為:管腳重邊匹配算法(PinHeavyEdgeMatching,PHEM)只是改進(jìn)了超邊中每2個節(jié)點邊權(quán)值的計算方法,當(dāng)超邊中只有2個節(jié)點時,其邊權(quán)值為W(eh);當(dāng)超邊中連接2個以上節(jié)點時,其邊權(quán)值為2×W(eh)。然而,上述基于節(jié)點選擇角度的RM、FC、GFC和HFC等節(jié)點匹配策略,粗化過程中隨機(jī)選中一個未匹配狀態(tài)的節(jié)點v之后,重點考慮的是節(jié)點v和鄰接節(jié)點u之間超邊e的權(quán)重W(e)、節(jié)點v和u自身的權(quán)重{S(v),S(u)}、以及節(jié)點v和u自身的度{D(v),D(u)}等局部信息,選擇相應(yīng)的鄰接節(jié)點來匹配。不同的匹配算法只是對W(e)、{S(v),S(u)}、{D(v),D(u)}局部信息的側(cè)重點不同而已。3節(jié)點匹配算法在文獻(xiàn)中,Seidman提出了反映節(jié)點在系統(tǒng)中重要程度的圖核的概念,闡述了p核的定義,同時給出了節(jié)點核值的概念。文獻(xiàn)[20-21]對圖核的概念進(jìn)行了擴(kuò)展,通過引入節(jié)點屬性函數(shù)p(v,U)和p核的概念來定義圖的一般化的核。文獻(xiàn)將圖核的概念引入到賦權(quán)圖的多水平粗化階段,借助核值的全局信息來改進(jìn)傳統(tǒng)的匹配算法,提出了基于核值排序的重邊匹配算法,并將其應(yīng)用在VLSI劃分中。相比利用節(jié)點的度、邊的權(quán)值等局部信息進(jìn)行隨機(jī)匹配、重邊匹配、最大權(quán)匹配等傳統(tǒng)的節(jié)點匹配算法,該節(jié)點匹配算法在最大化減少邊的數(shù)目以及邊權(quán)值之和的同時,將連接性好的節(jié)點合并在一起,使得到的粗化圖中粗化節(jié)點的權(quán)值趨向于大小一致。受文獻(xiàn)[21-22]的啟發(fā),文獻(xiàn)將賦權(quán)圖的核值理論擴(kuò)展到賦權(quán)超圖上,提出了超圖的核的相關(guān)概念,并基于超圖k水平p-核的構(gòu)造性屬性,給出了求解超圖核值算法。定義4對于一給定超圖HG=(V,Eh),由節(jié)點子集U(U?V)得到的子圖CG=(U,EC),其中,EC=Eh|U如滿足下列屬性,則稱子圖CG是超圖HG的序為k的核。(2)子圖CG為滿足上述屬性的最大子圖。定義5對于一給定超圖HG=(V,Eh),序值最大的核稱為該超圖的主核。節(jié)點v的核值為包含節(jié)點v的最大核的值,且超圖的核滿足嵌套關(guān)系:i<j?CiG?CjG。定義6對于一給定超圖HG=(V,Eh),由節(jié)點子集U得到的子圖CG=(U,EC),如果滿足下列屬性,則稱子圖CG為超圖HG在k水平的p-核。(2)子圖CG為滿足上述屬性的最大子圖。對超圖的核的概念進(jìn)行了擴(kuò)展,通過引入不同的節(jié)點屬性函數(shù)p(v,U)和p-core的概念來定義超圖的一般化的核,將基于節(jié)點的度屬性進(jìn)行超圖的核值求解,擴(kuò)展到節(jié)點的其他屬性進(jìn)行超圖的核值求解。定義7對于一給定超圖HG=(V,Eh),令N(v)表示節(jié)點v在超圖HG的鄰接超邊集,N(v,EC)=N(v)∩EC,其中,v∈V,EC?EH,則節(jié)點屬性函數(shù)p(v,U)可以描述下述屬性:如果p(v,U)滿足下列約束條件,則稱p(v,U)為單調(diào)函數(shù):U1?U2??v∈V:(p(v,U1)≤p(v,U2))。4比較和分析實驗結(jié)果4.1平衡約束實驗結(jié)果IBM公司Austin研究實驗室的Alpert教授給出了ISPD98測試基準(zhǔn),作為學(xué)術(shù)界和工業(yè)界的研究人員進(jìn)行電路劃分測評的基準(zhǔn)工具。按照文獻(xiàn)給出的ISPD98測試基準(zhǔn)到超圖轉(zhuǎn)換算法的偽代碼,將ISPD98電路網(wǎng)表劃分問題轉(zhuǎn)換為賦權(quán)超圖劃分優(yōu)化問題。ISPD98電路網(wǎng)表劃分要求每個電路子集所包含的元件數(shù)目相等,對應(yīng)于超圖劃分優(yōu)化問題的平衡約束條件,劃分結(jié)果使得這些電路子集之間的內(nèi)連線數(shù)達(dá)到最小,對應(yīng)于超圖劃分優(yōu)化問題的最小化總截權(quán)。ISPD98測試基準(zhǔn)的18組電路轉(zhuǎn)換到超圖后,超圖中的節(jié)點數(shù)范圍為12752~210613,超邊數(shù)范圍為14111~201920。針對每組測試基準(zhǔn)轉(zhuǎn)換后的賦權(quán)超圖,進(jìn)行了二劃分(nparts=2)的實驗;實驗設(shè)定平衡約束參數(shù)均為0.05(UBfactor=5),允許劃分得到的節(jié)點子集權(quán)值之和偏差為所有節(jié)點子集權(quán)值之和的5%。ISPD98測試基準(zhǔn)在多水平粗化階段中不同水平層粗化超圖節(jié)點數(shù)的變化趨勢表現(xiàn)為:隨著節(jié)點匹配算法對超圖H0G=(V0,E0h)中的節(jié)點進(jìn)行匹配,將它們結(jié)合在一起得到下一級粗化超圖,重復(fù)此過程得到一系列的粗化超圖,其中,節(jié)點個數(shù)滿足,直至粗化超圖達(dá)到設(shè)置的閾值(如節(jié)點數(shù)200)為止,即得到一個最小超圖。4.2多水平層粗化節(jié)點匹配策略的比較在ISPD98測試基準(zhǔn)的多水平劃分中,對其粗化階段選用的RM、HEM和PHEM不同的節(jié)點匹配算法進(jìn)行對比實驗。針對ISPD98測試基準(zhǔn)中每組超圖,以及在粗化階段中得到的每一水平層粗化超圖,按照文獻(xiàn)給出的基于節(jié)點屬性函數(shù)p5(v,U)的核值求解算法的偽代碼,進(jìn)行了節(jié)點核值屬性的求解實驗,并與節(jié)點度屬性進(jìn)行對比分析。實驗結(jié)果采用的評估指標(biāo)分別是:節(jié)點的度、核值的最大值,節(jié)點的度、核值的累加和,節(jié)點的度、核值的分布密度。其評估指標(biāo)相應(yīng)的公式定義如下:基于不同節(jié)點匹配策略的ISPD98測試基準(zhǔn),在多水平粗化階段不同水平層粗化超圖的節(jié)點度和核值最大值的對比實驗數(shù)據(jù)表明:(1)盡管粗化超圖的節(jié)點數(shù)越來越少,但由于粗化節(jié)點的連接關(guān)系取決于其合并前兩兩節(jié)點的連接關(guān)系的并集,因此無論是粗化節(jié)點度的最大值,還是粗化節(jié)點核值的最大值都在不斷地增加。(2)基于不同節(jié)點匹配策略得到的每組水平層粗化超圖,其粗化節(jié)點度的最大值均大于粗化節(jié)點核值的最大值。(3)基于RM隨機(jī)匹配算法得到的每組水平層粗化超圖,其粗化節(jié)點度和核值的最大值均大于基于HEM/PHEM重邊匹配算法所得到的度和核值最大值。這表明相比應(yīng)用隨機(jī)策略選擇鄰接節(jié)點進(jìn)行匹配的RM隨機(jī)匹配算法,HEM/PHEM重邊匹配算法在最大化減少超邊權(quán)值之和的同時,趨向于將連接性好的節(jié)點合并在一起,有效地降低粗化節(jié)點的度和核值最大值?；诓煌?jié)點匹配策略的ISPD98測試基準(zhǔn),在多水平粗化階段不同水平層粗化超圖的節(jié)點度和核值累加值的對比實驗數(shù)據(jù)表明:(1)盡管粗化節(jié)點的度和核值都在不斷地增加,但由于粗化超圖的節(jié)點數(shù)越來越少,因此無論是粗化節(jié)點度的累加值,還是粗化節(jié)點核值的累加值都在不斷地減少。(2)基于不同節(jié)點匹配策略得到的每組水平層粗化超圖,其粗化節(jié)點度的累加值均大于粗化節(jié)點核值的累加值。(3)基于RM隨機(jī)匹配算法得到的每組水平層粗化超圖,其粗化節(jié)點度和核值的累加值均大于基于HEM/PHEM重邊匹配算法所得到的度和核值累加值。這表明相比RM隨機(jī)匹配算法,HEM/PHEM重邊匹配算法不僅降低了粗化節(jié)點的度和核值最大值,而且降低了粗化節(jié)點的度和核值,最終有效地降低了粗化節(jié)點的度和核值累加值。圖1~圖18是基于不同節(jié)點匹配策略的ISPD98測試基準(zhǔn)在水平粗化階段,不同水平層粗化超圖的節(jié)點度和核值分布密度的對比。從以上的實驗結(jié)果可以看出:(1)在粗化節(jié)點度和核值的累加值不斷減少的同時,其度和核值的最大值還在不斷增加,因此,無論是粗化節(jié)點度的分布密度,還是粗化節(jié)點核值的分布密度都在迅速減少。(2)基于不同節(jié)點匹配策略得到的每組水平層粗化超圖,其粗化節(jié)點度和核值的最大值增加幅度,與粗化節(jié)點度和核值的累加值降低幅度基本同步,導(dǎo)致粗化節(jié)點度和核值的分布密度的降低幅度基本一致,因此,RM/HEM/PHEM節(jié)點匹配算法得到的不同水平層粗化超圖的節(jié)點度和核值分布密度曲線基本擬合。(3)盡管基于不同節(jié)點匹配策略得到的每組水平層粗化超圖,其粗化節(jié)點度的累加值均大于粗化節(jié)點核值的累加值,但是粗化節(jié)點核值的分布密度高于粗化節(jié)點度的分布密度,更能真實地反映出粗化節(jié)點在每組水平層粗化超圖中的重要程度。5多水平粗化階段的節(jié)點匹配策略本文將圖的核值理論擴(kuò)展到賦權(quán)超圖上,給出了超圖的核等相關(guān)概念及其形式化描述,在賦權(quán)超圖劃分優(yōu)化算法的多水平方法粗化階段,借助節(jié)點的核值屬性改進(jìn)以往僅利用節(jié)點局部信息進(jìn)行選擇的匹配策略。針對ISPD98測試基準(zhǔn)給出的18組超圖,結(jié)合多水平粗化階段的RM、HEM和PHEM節(jié)點匹配策略,采用節(jié)點的度分別和核值的最大值、累加和、分布密度為評估指標(biāo),進(jìn)行了節(jié)點的度屬性和核值屬性的對比實驗。實驗數(shù)據(jù)