[發明專利]基于多層次方法和離散粒子群的賦權超圖優化劃分方法

有效

• 申請號: 201510135672.8
• 申請日: 2015-03-26
• 公開（公告）號: CN104679966B
• 公開（公告）日: 2017-06-16
• 發明（設計）人: 冷明;孫凌宇;冷子陽
• 申請（專利權）人: 孫凌宇;冷明;冷子陽
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種電路劃分和云計算任務調度中基于多層次方法和離散粒子群的賦權超圖優化劃分方法。

背景技術

現有技術的劃分系統中有若干種結點的劃分方法，這些劃分方法從依賴關系數目最小、劃分后結點子集的結點數目均勻分布等不同的方面來實現，主要有基于遷移的劃分方法、水平嵌套劃分方法和多層次劃分方法等。

基于遷移的劃分方法。該方法首先產生結點的隨機初始劃分，同一個結點不能同時屬于兩個結點子集。在遷移優化階段，從兩個結點子集中各選取一個結點進行成對交換，這兩個結點分別屬于兩個不同的結點子集且收益最大，從而每次都利用交換過程最大限度地改進結點劃分質量。記錄割切達到最小值時刻的結點劃分結果，且一旦交換了所選擇的兩個結點，在整個遷移過程余下的優化改進中，將這兩個結點鎖定使得它們不再被選中。重復上述過程直到所有可能的結點都經過遷移之后，回滾到累計收益最大值即割切最小值的時刻。該劃分方法得到的結點劃分結果不穩定，離散性很大，因此限制了該劃分方法所能解決問題的規模。

水平嵌套劃分方法。該方法首先選擇一個結點，將這個結點標上號碼0，然后將所有和這個結點相連的結點標上號碼1，之后對于那些還未標上號碼，但是和已經標上號碼的結點相連的結點，將其標號為相連結點的號碼加1。直到一半的結點標上號碼，標號過程才結束。那些已經標上號碼的結點集合設為一個結點子集，其他結點為另一個結點子集。該劃分方法只有在選取的初始結點接近外圍時，得到的結點劃分結果相對較好，總的來說該結點劃分結果也不穩定。

多層次劃分方法。Karypis針對結點規模達到幾百萬的劃分問題，提出了多層次劃分的概念，在相對較短的時間內可以得到高質量的劃分。該方法包含粗化、初始劃分和遷移優化三個階段。首先，它采用隨機匹配策略將某些結點結合在一起，得到下一水平層的粗化圖，重復此過程直到粗化圖足夠小為止，即得到一個最小圖。然后，采用劃分方法對最小圖進行對分，得到一個初始劃分。之后，將最小圖投影回初始圖，在每一水平層的細化劃分中，按照貪心原則選擇收益值最大的結點進行遷移優化，得到最后的結點劃分結果。

多層次劃分方法在電路劃分和云計算任務調度中的應用。自多層次劃分的概念提出以來，得到了廣泛地重視，并應用在電路劃分和云計算任務調度等多個研究領域。

2008年中國專利局公告的由冷明、郁松年和孫凌宇申報，中國專利號為200710043765.3號《基于多水平劃分法的大規模集成電路劃分方法》的發明專利，針對現有技術方案中因采用隨機策略進行匹配和貪心原則進行遷移優化，導致無法逃離局部最優的劃分，提供了一種改進的基于多水平劃分法的大規模集成電路劃分方法，有效地提高了大規模集成電路劃分的效率和性能。該發明專利在多水平劃分方法的粗化階段，通過對結點屬性進行賦權無向圖中所有結點的核值求解排序，按照基于結點核值的非嚴格降序訪問處于未匹配狀態的結點，依據一定規則對其進行匹配，從而將連接性好的結點合并在一起；在多水平劃分方法的優化階段，采用免疫克隆優化程序改進貪心原則的局部搜索方法，對在每一水平層投影的劃分進行優化，借助克隆操作、克隆變異操作、接種免疫疫苗操作和克隆選擇操作，使得改進后的方法在利用啟發信息搜索局部最優解的同時，能更自由地對具有潛力的解空間進行搜索，增加全局搜索能力。

2012年中國專利局公告的由孫凌宇、冷明和冷子陽申報，中國專利號為201210155738.6號《基于多水平劃分法和賦權超圖的大規模集成電路劃分方法》的發明專利，針對采用賦權無向圖作為大規模集成電路劃分問題的數學模型，存在著賦權無向圖最優劃分和大規模集成電路最優劃分的不一致性，提供了一種基于多水平劃分法和賦權無向超圖的大規模集成電路劃分方法，進一步提高了大規模集成電路劃分的效率和性能。該發明采用賦權無向超圖對電路劃分問題進行數學建模，其中電路邏輯單元表示為賦權無向超圖中的結點，電路單元間的連線表示為賦權無向超圖中的超邊。相比賦權無向圖而言，賦權無向超圖為電路提供了更為精確的模型：每條超邊可以連接兩個以上的結點，對應于電路單元間的信號可以連接兩個以上的電路邏輯單元。該發明將大規模集成電路劃分問題轉換為賦權無向超圖劃分問題，其中大規模集成電路劃分問題要求每個電路子集所包含的電路邏輯單元數目相等，對應于賦權無向超圖劃分問題的平衡約束條件，劃分結果使得這些電路子集之間的內連線數據達到最小，對應于賦權無向超圖劃分問題的最小化總割切。