雲計算環境中的基於結點屬性函數的任務核值計算方法
2023-06-19 20:41:11
雲計算環境中的基於結點屬性函數的任務核值計算方法
【專利摘要】本發明涉及一種雲計算環境中的基於結點屬性函數的任務核值計算方法，採用賦權有向超圖對雲計算環境中的元任務和依賴任務進行數學建模，描述任務的資源需求及依賴關係，並生成相應的賦權有向超圖文件，然後啟動賦權有向超圖的核值計算程序，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲，並基於結點屬性函數計算結點的核值，將所有結點的核值結果存儲在賦權有向超圖核值文件中。採用本發明的核值計算方法，不僅能有效地提高核值計算的效率，還有利於在賦權超圖的結點匹配過程中，改善結點匹配的性能。
【專利說明】雲計算環境中的基於結點屬性函數的任務核值計算方法
【技術領域】
[0001]本發明涉及一種雲計算環境中的基於結點屬性函數的任務核值計算方法。
【背景技術】
[0002]雲計算作為分布式計算、並行計算、網格計算等傳統技術和網絡編程模型、分布式數據存儲技術、虛擬化技術等新型技術融合發展的產物，是引領未來信息產業創新的關鍵戰略性技術和手段，將對我國發展高新技術產業具有重要的戰略意義。雲計算通過將計算任務劃分在大規模的廉價伺服器集群上，使得人們能夠利用分布在各地的閒散資源來處理較為複雜的應用程式，以極低的成本投入獲得極高的計算品質。
[0003]在滿足雲計算環境要求的前提下，將大量分散的應用程式任務劃分成多個具有一定約束關係的任務子集，調度到不同的虛擬機上，獲得比其他一些針對網格計算或並行計算的任務調度算法更短的時間跨度和更好的運行質量，是實現雲計算高性能的關鍵核心技術。
[0004]現有技術的劃分系統中有若干種任務的劃分法，這些劃分法從依賴關係數目最小、劃分後任務子集的任務數目均勻分布等不同的方面來實現。目前，現有的劃分大多採用多水平劃分法的技術方案。Karypis針對結點規模達到幾百萬的劃分問題，提出了多水平劃分的概念，在相對較短的時間可以得到高質量的劃分。該方法包含粗化、初始劃分和遷移優化三個階段。首先，它採用隨機匹配將某些任務結合在一起，得到下一水平層的粗化任務圖，重複此過程直到粗化任務圖足夠小為止，即得到一個最小任務圖。然後，採用劃分法對最小任務圖進行對分，得到一個初始劃分。之後，將最小任務圖投影回初始任務圖，在每一水平層的細化任務劃分中，按照貪心原則選擇收益值最大的任務進行遷移優化，得到最後的任務劃分結果。
[0005]多水平劃分法在電路劃分中的應用。自多水平劃分的概念提出以來，得到了廣泛地重視，並應用在電路劃分等許多研究領域。2008年中國專利局公告的由冷明、鬱松年和孫凌宇申報，中國專利號為200710043765.3號《基於多水平劃分法的大規模集成電路劃分方法》的發明專利，針對現有技術方案中因採用隨機策略進行匹配和貪心原則進行遷移優化，導致無法逃離局部最優的劃分，提供了一種改進的基於多水平劃分法的大規模集成電路劃分方法，有效地提高了大規模集成電路劃分的效率和性能。該發明專利在多水平劃分法的粗化階段，通過對結點屬性進行賦權無向圖中所有結點的核值求解排序，按照基於結點核值的非嚴格降序訪問處於未匹配狀態的結點，依據一定規則對其進行匹配，從而將連接性好的結點合併在一起；在多水平劃分法的優化階段，採用免疫克隆優化程序改進貪心原則的局部搜索方法，對在每一水平層投影的劃分進行優化，藉助克隆操作、克隆變異操作、接種免疫疫苗操作、克隆選擇操作，使得改進後的方法在利用啟發信息搜索局部最優解的同時，更自由地對具有潛力的解空間進行搜索，增加全局搜索能力。
[0006]2012年中國專利局公告的由孫凌宇、冷明和冷子陽申報，中國專利號為201210155738.6號《基於多水平劃分法和賦權超圖的大規模集成電路劃分方法》的發明專利，針對採用賦權無向圖作為大規模集成電路劃分問題的數學模型，存在著賦權無向圖最優劃分和大規模集成電路最優劃分的不一致性，提供了一種基於多水平劃分法和賦權無向超圖的大規模集成電路劃分方法，進一步提高了大規模集成電路劃分的效率和性能。該發明採用賦權無向超圖對電路劃分問題進行數學建模，其中電路邏輯單元表示為賦權無向超圖中的結點，電路單元間的連線表示為賦權無向超圖中的超邊。相比賦權無向圖而言，賦權無向超圖為電路提供了更為精確的模型:每條超邊可以連接兩個以上的結點，對應於電路單元間的信號可以連接兩個以上的電路邏輯單元。該發明將大規模集成電路劃分問題轉換為賦權無向超圖劃分問題，其中大規模集成電路劃分問題要求每個電路子集所包含的電路邏輯單元數目相等，對應於賦權無向超圖劃分問題的平衡約束條件，劃分結果使得這些電路子集之間的內連線數據達到最小，對應於賦權無向超圖劃分問題的最小化總割切。進而，2012年中國專利局公告的由孫凌宇、冷明和冷子陽申報，中國專利號為201210150329.7號《基於結點屬性函數的大規模集成電路的核值計算方法》的發明專利，在採用多水平劃分法求解賦權無向超圖劃分問題的粗化階段中，提供了所需的基於結點屬性函數的大規模集成電路的核值計算方法。
【發明內容】
[0007]本發明涉及的雲計算環境中任務包括元任務和依賴任務。元任務之間相互獨立，其調度不考慮任務間的數據關聯與優先約束關係，因此它只是部分地解決了資源異構性和可用性問題，缺乏普遍適用性。而依賴任務之間存在先後依賴關係，要求一個任務必須接收到它的所有前驅任務消息後才能開始執行。
[0008]本發明採用賦權有向超圖來構造任務劃分問題的數學模型，任務表示為賦權有向超圖的結點，任務結點間的先後依賴關係表示為賦權有向超圖中的有向超邊。賦權有向超圖的多對多關係提供了精確描述用戶任務的手段，其結點對應於分解後的進程級用戶任務，有向超邊對應於任務結點間的先後依賴關係，任意超邊的尾端結點所對應任務的全部前驅任務都包含在該超邊的源端子集中。相比賦權有向圖和賦權無向超圖，賦權有向超圖為依賴任務的調度提供了更為精確的模型，能全面地表示雲計算環境的異構性、分布性、廣域性等特點，從而提聞任務調度的準確性和執行效率。
[0009]相比賦權有向圖而目，賦權有向超圖為任務結點的依賴關係提供了更為精確的豐旲型:每條邊僅連接兩個結點，對應於任務結點之間的依賴關係只能連接兩個任務，而每條超邊可以連接兩個以上的結點，對應於任務結點之間的先後依賴關係可以連接兩個以上的任務，即任意超邊的尾端結點所對應任務的全部(兩個以上)前驅任務都包含在該超邊的源端子集中。
[0010]相比賦權無向超圖而言,賦權有向超圖為任務結點的先後依賴關係提供了更為精確的模型:無向超邊連接兩個以上的結點，但無法表示任務結點間的先後依賴關係，而每條有向超邊可以連接兩個以上的結點，超邊尾端結點的所有直接前驅結點都包含在該超邊的源端子集中，對應於任務結點間的先後依賴關係。
[0011]在多水平劃分法的粗化階段，依據結點屬性對賦權有向超圖中所有結點的核值進行求解排序，進而在賦權有向超圖的結點匹配過程中發揮結點核值導向性作用，進行基於結點核值的非嚴格降序的結點匹配，使相應的結點匹配算法在最大化減少有向超邊的數目以及有向超邊權值之和的同時，將連接性好的結點合併在一起，使得到的粗化賦權有向超圖中粗化結點的權值趨向於大小一致，為多水平劃分的後續階段提供更優的粗化賦權有向超圖。
[0012]本發明的目的在於針對已有技術存在的不足，提供一種雲計算環境中基於結點屬性函數的任務核值計算方法，為雲計算環境中的基於多水平劃分法和賦權有向超圖的任務劃分後續階段提供更優的粗化賦權有向超圖。為達到上述目的，本發明的構思如下:採用賦權有向超圖對雲計算環境中的元任務和依賴任務進行數學建模，描述任務的資源需求及依賴關係，並生成相應的賦權有向超圖文件，然後啟動賦權有向超圖的核值計算程序，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲，並基於結點屬性函數計算結點的核值，將所有結點的核值結果存儲在賦權有向超圖核值文件中。
[0013]根據上述的發明構思，本發明的技術方案是這樣實現的:一種雲計算環境中基於結點屬性函數的任務核值計算方法，其特徵在於，具體步驟如下。
[0014]步驟1，類型類度分析，輸入雲計算環境中用戶提交的任務，並對其進行類型和類度的分析，確定任務的並行化程度和特點。
[0015]步驟2，進程粒度分解，根據用戶任務的並行化程度和特點，以及雲計算的資源共享分配方式等獨特性質，對用戶任務按照進程粒度級別進行分解。
[0016]步驟3，資源特性分析，根據云計算的資源共享分配方式等獨特性質，對分解後的任務進行資源特性分析。
[0017]步驟4，賦權有向超圖文件生成，依據對任務資源特性的分析結果，建立描述其資源需求及依賴關係的賦權有向超圖模型，並按照改進壓縮的文件存儲格式保存為賦權有向超圖文件。
[0018]步驟5，賦權有向超圖核值計算，啟動賦權有向超圖核值計算程序，讀取賦權有向超圖文件，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲，對生成的賦權有向超圖中的每個結點，基於結點屬性函數計算其核值，將所有結點的核值結果存儲在賦權有向超圖核值文件中。
[0019]上述的步驟4中，所述的賦權有向超圖的改進壓縮的文件存儲格式的步驟如下。
[0020]步驟4.1，文件格式的第I行第I個參數代表著有向賦權超邊的數目m，第2個參數代表著賦權結點的數目η。
[0021]步驟4.2，文件格式的第2行開始到第m+1行的每行代表著一條有向賦權超邊的相關信息，第I個數值為有向賦權超邊的權值信息，其餘數值為有向賦權超邊的結點信息，其中每行的最後一個數值代表有向賦權超邊的尾端結點信息，且有向賦權超邊的源端結點信息處於有向賦權超邊的權值信息和尾端結點信息之間。
[0022]步驟4.3，文件格式的第m+2行開始到第m+n+1行的每行代表著一個賦權結點的權
值信息。
[0023]上述的步驟5中，所述的賦權有向超圖核值計算的步驟如下。
[0024]步驟5.1，讀取賦權有向超圖文件，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲。
[0025]步驟5.2，計算出所有結點的屬性函數值。
[0026]步驟5.3，對所有結點的屬性函數值進行非嚴格降序排序。[0027]步驟5.4，按照結點屬性函數值的非嚴格降序次序訪問每個結點，計算每個結點的核值。
[0028]步驟5.5，將所有結點的核值結果存儲在賦權有向超圖核值文件中。
[0029]上述的步驟5.1中，所述的賦權有向超圖的改進壓縮的內存存儲格式如下。
[0030]步驟5.1.1,使用vwgts數組存儲賦權有向超圖中結點的權值信息,且vwgts數組的大小為賦權有向超圖中的結點個數。
[0031]步驟5.1.2,使用xadj數組存儲每個結點所有鄰接有向超邊列表的起始位置信息，即第i個結點的終止位置為第i+Ι個結點的起始位置減1，且xadj數組的大小為賦權有向超圖中的結點個數加1，xadj數組最後一個元素用於存放最後一個結點的終止位置。
[0032]步驟5.1.3，使用adjncy數組存儲每個結點所有鄰接有向超邊的列表信息，第i個結點的鄰接有向超邊列表存儲在adjncy數組中，從adjncy [xadj [i]]到adjncy[xadj[i+1]-1]。
[0033]步驟5.1.4,使用eptr數組存儲每條有向超邊所包含的結點列表的起始位置信息，即第j條有向超邊的終止位置為第j+Ι條有向超邊的起始位置減1，且eptr數組的大小為賦權有向超圖中的有向超邊條數加1，eptr數組最後一個元素用於存放最後一條有向超邊的終止位置。
[0034]步驟5.1.5，使用eind數組存儲每條有向超邊所包含結點的列表信息，其中每條有向超邊的尾端結點只有I個，且每條有向超邊尾端結點的所有直接前驅結點都包含在該有向超邊的源端子集中。第j條有向超邊的結點列表存儲在eind數組中，從eind [eptr [j]]到eind [eptr [j+1]-1],其中第j條有向超邊的源端結點為eind [eptr [j]]到eind [eptr [j+1]-2],第j條有向超邊的尾端結點為eind [eptr [j+1]-1]。
[0035]步驟5.1.6,使用hewgts數組存儲有向超邊的權值信息,且hewgts數組的大小為賦權有向超圖中的有向超邊數目。
[0036]上述的步驟5.3中，所述的結點屬性函數值的非嚴格降序排序的步驟如下。
[0037]步驟5.3.1，根據結點的屬性函數值屬於一定範圍內的整數，掃描所有結點的屬性函數值，統計每一種屬性函數值的結點個數，存儲在計數輔助數組bin中。
[0038]步驟5.3.2，針對每一種屬性函數值，藉助計數輔助數組bin，計算出在所有結點的屬性函數值中，小於該屬性函數值的結點個數，存儲在位置輔助數組pos中。
[0039]步驟5.3.3，掃描所有結點的屬性函數值，針對每一個結點的屬性函數值，藉助位置輔助數組pos，得到該結點的屬性函數值在非嚴格降序排序的次序，並將該次序存儲在次序輔助數組vert中。
[0040]上述的步驟5.4中,所述的結點V的核值計算的步驟如下。
[0041]步驟5.4.1，將結點V的屬性函數值作為核值輸出。
[0042]步驟5.4.2，標記結點V從所在的超邊e中刪除。
[0043]步驟5.4.3，如果超邊e刪除結點V後，仍包含兩個及以上未被標記刪除的結點，則超邊e仍然存在，否則刪除超邊e。
[0044]步驟5.4.4,重新計算結點V的鄰接結點u的屬性函數值。
[0045]步驟5.4.5,如果鄰接結點u的屬性函數值大於結點V的屬性函數值，更新鄰接結點u的屬性函數值，並且藉助計數輔助數組bin、位置輔助數組pos和次序輔助數組vert的信息，快速更新鄰接結點U在所有結點的屬性函數值非嚴格降序排序的次序；否則不更新鄰接結點U的屬性函數值及其排序的次序。
[0046]本發明與現有技術相比較，具有如下顯而易見的突出實質性特點和顯著優點。
[0047]1、提高核值計算的效率。
[0048]本發明在所述步驟5.3中，由於結點的屬性函數值屬於一定範圍內的整數，因此藉助位置輔助數組pos，對所有結點的屬性函數值進行非嚴格降序排序。本發明在所述步驟
5.4.2中，只需標記結點V從所在的超邊e中刪除，使之在後續步驟中能正確計算出鄰接結點u的屬性函數值即可。在所述步驟5.4.5中，只需更新大於結點V屬性函數值的鄰接結點u的屬性函數值及其排序的次序，而無需更新所有鄰接結點的屬性函數值及其排序的次序。經時間複雜度分析，其賦權有向超圖的核值計算方法的總時間複雜度與賦權有向超圖的超邊數呈線性關係。
[0049]2、改善結點匹配的性能。
[0050]本發明計算出結點的核值，相比結點的度更能反映出結點在賦權有向超圖中的重要程度，有利於在賦權有向超圖的結點匹配過程中，發揮結點核值導向性作用，使得粗化後賦權有向超圖中結點權值傾向於大小一致，並最大程度地減少有向超邊的數目以及有向超邊權值之和，為多水平劃分的後續階段提供更優的粗化賦權有向超圖。
[0051]通過以下對本發明雲計算環境中基於結點屬性函數的任務核值計算方法的實例結合其附圖的描述，可以進一步理解本發明的目的、具體結構特徵和優點。
[0052]圖1是本發明雲計算環境中基於結點屬性函數的任務核值計算方法的流程圖。
[0053]圖2是本發明的賦權有向超圖的改進壓縮的內存存儲格式。
[0054]圖3是本發明的賦權有向超圖的核值計算方法的流程圖。
[0055]【具體實施方式】。
[0056]為了能夠更清楚地理解本發明雲計算環境中基於結點屬性函數的任務核值計算方法的技術內容，特舉以下實例詳細說明。
[0057]本實施例的雲計算環境中基於結點屬性函數的任務核值計算方法的流程圖如圖1所示。在雲計算環境中，輸入用戶提交的任務101，對用戶任務進行類型和類度的分析102，確定任務的並行化程度和特點；根據用戶任務的並行化程度和特點，以及雲計算的資源共享分配方式等獨特性質，對用戶任務按照進程粒度級別進行分解103 ;進而對分解後的任務進行資源特性分析104 ;依據對任務資源特性的分析結果，建立描述其資源需求及依賴關係的賦權有向超圖模型105 ;按照改進壓縮的文件存儲格式保存為賦權有向超圖文件106 ;啟動賦權有向超圖核值計算程序108，讀取賦權有向超圖文件106，得到採用改進壓縮的內存存儲格式的賦權有向超圖107 ;對每一結點進行核值計算，得到所有結點的核值結果109 ;將所有結點的核值結果存儲為賦權有向超圖核值文件110。
[0058]本實施例的賦權有向超圖改進壓縮的文件存儲格式參見在先技術[I] 「G.Karypis and V.Kumar.HMetis 1.5.3: A Hypergraph Partitioning Package [R].Technical report, Department of Computer Science, University of Minnesota,1998.」和在先技術[2] 「孫凌宇，冷明，郭愷強，朱平.一種VLSI設計到超圖的轉換系統[J].計算機工程與應用，2012，Vol.29, Issue.2, Pages 7-16.」。與在先技術[1，2]相同點:文件格式的第I行第I個參數代表著有向賦權超邊的數目m，第2個參數代表著賦權結點的數目η ;文件格式的第2行開始到第m+1行的每行代表著一條有向賦權超邊的相關信息；文件格式的第m+2行開始到第m+n+1行的每行代表著一個賦權結點的權值信息。與在先技術[1，2]區別點:文件格式的第2行開始到第m+1行中，除第I個數值之外的其餘數值為有向賦權超邊的結點信息，其中每行的最後一個數值代表有向賦權超邊的尾端結點信息，且有向賦權超邊的源端結點信息處於有向賦權超邊的權值信息和尾端結點信息之間。
[0059]本實施例的賦權有向超圖的改進壓縮的內存存儲格式如圖2所示。存儲結構使用adjncy數組204存儲每個結點所有鄰接有向超邊的列表信息。使用xadj數組203存儲每個結點所有鄰接有向超邊列表的起始位置信息，即第i個結點的終止位置為第i+Ι個結點的起始位置減1，且xadj數組203的大小為賦權有向超圖中的結點個數加1，xadj數組203最後一個元素用於存放最後一個結點的終止位置。使用eind數組207存儲每條有向超邊所包含結點的列表信息。使用eptr數組206存儲每條有向超邊所包含的結點列表的起始位置信息，即第j條有向超邊的終止位置為第j+Ι條有向超邊的起始位置減1，且eptr數組206的大小為賦權有向超圖中的有向超邊條數加1，eptr數組206最後一個元素用於存放最後一條有向超邊的終止位置。使用VWgts數組202存儲結點的權值信息,且VWgts數組202的大小為賦權有向超圖中的結點個數。使用hewgts數組205存儲有向超邊的權值信息，且hewgts數組205的大小為賦權有向超圖中的有向超邊條數。假設數組地址從零開始，結點編號從零開始，貝1J第i個結點的鄰接有向超邊列表存儲在adjncy數組204中，從adjncy [xadj [i]]到adjncy [xadj [i+Ι]-1];第j條有向超邊的鄰接結點列表存儲在eind數組207中，從eind [eptr [j]]到eind [eptr [j+1]-1]，其中第j條有向超邊的源端結點為eind [eptr [j]]到 eind [eptr [j+Ι]-2],第 j 條有向超邊的尾端結點為 eind [eptr [j+1]-1]。圖例201包含總共7個結點和8條有向超邊，其中第6個結點的權值為7，有2條鄰接有向超邊f、h，其中有向超邊f對應的權值為4，且相應的鄰接結點分別為結點7、3、6，源端結點為結點7和3，尾端結點為結點6 ;有向超邊h對應的權值為1，且相應的鄰接結點分別為結點4、6，源端結點為結點4,尾端結點為結點6。
[0060]賦權無向圖的結點核值的含義參見在先技術[3] 「SEIDMAN.S.B.Networkstructure and minimum degress.Social Networks.September 1983， Vol.5， Issue.3，Pages 269-287」和在先技術[4] 「孫凌宇，冷明，鄧曉春，鬱松年.圖壓縮存儲格式的核排序重邊匹配算法[J].計算機工程與應用，2011，Vol.47, Issue.10, Pages 41-47.」。作為賦權無向圖的核值研究的深入和延續，本發明將基於賦權無向圖的核值理論擴展到賦權有向超圖上。
[0061]本實施例的賦權有向超圖的核值計算方法的流程圖如圖3所示，步驟如下。
[0062]AOl:計算出所有結點的屬性函數值。
[0063]A02:對所有結點的屬性函數值進行非嚴格降序排序。
[0064]A03:按照結點屬性函數值的非嚴格降序次序訪問結點是否結束；如果訪問未結束，即存在結點V未被訪問，則轉步驟A04 ;否則訪問結束，賦權有向超圖核值計算結束。
[0065]A04:將結點V的屬性函數值作為核值輸出。
[0066]A05:標記結點V從所在的超邊e中刪除。
[0067]A06:如果超邊e刪除結點V後，仍包含兩個及以上未被標記刪除的結點，則轉步驟A08，否則轉步驟A07。[0068]A07:刪除超邊e。
[0069]A08:重新計算結點V的所有鄰接結點u的屬性函數值。
[0070]A09:如果鄰接結點u的屬性函數值大於結點V的屬性函數值，轉步驟A10，否則轉步驟A03。
[0071]AlO:更新鄰接結點u的屬性函數值。
[0072]All:藉助計數輔助數組bin、位置輔助數組pos和次序輔助數組vert的信息，快速更新鄰接結點u在所有結點的屬性函數值非嚴格降序排序的次序，轉步驟A03。
【權利要求】
1.一種雲計算環境中基於結點屬性函數的任務核值計算方法，其特徵在於，具體步驟如下: 步驟1，類型類度分析，輸入雲計算環境中用戶提交的任務，並對其進行類型和類度的分析，確定任務的並行化程度和特點； 步驟2，進程粒度分解，根據用戶任務的並行化程度和特點，以及雲計算的資源共享分配方式等獨特性質，對用戶任務按照進程粒度級別進行分解； 步驟3，資源特性分析，根據云計算的資源共享分配方式等獨特性質，對分解後的任務進行資源特性分析； 步驟4，賦權有向超圖文件生成，依據對任務資源特性的分析結果，建立描述其資源需求及依賴關係的賦權有向超圖模型，並按照改進壓縮的文件存儲格式保存為賦權有向超圖文件； 步驟5，賦權有向超圖核值計算，啟動賦權有向超圖核值計算程序，讀取賦權有向超圖文件，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲，對生成的賦權有向超圖中的每個結點，基於結點屬性函數計算其核值，將所有結點的核值結果存儲在賦權有向超圖核值文件中； 上述的步驟4中，所述的賦權有向超圖的改進壓縮的文件存儲格式的步驟如下: 步驟4.1，文件格式的第I行第I個參數代表著有向賦權超邊的數目m，第2個參數代表著賦權結點的數目η; 步驟4.2，文件格式的第2行開始到第m+1行的每行代表著一條有向賦權超邊的相關信息，第I個數值為有向賦權`超邊的權值信息，其餘數值為有向賦權超邊的結點信息，其中每行的最後一個數值代表有向賦權超邊的尾端結點信息，且有向賦權超邊的源端結點信息處於有向賦權超邊的權值信息和尾端結點信息之間； 步驟4.3，文件格式的第m+2行開始到第m+n+1行的每行代表著一個賦權結點的權值信息； 上述的步驟5中，所述的賦權有向超圖核值的計算步驟如下: 步驟5.1，讀取賦權有向超圖文件，採用改進壓縮的內存存儲格式對賦權有向超圖進行存儲； 步驟5.2，計算出所有結點的屬性函數值； 步驟5.3，對所有結點的屬性函數值進行非嚴格降序排序； 步驟5.4，按照結點屬性函數值的非嚴格降序次序訪問每個結點，計算每個結點的核值； 步驟5.5，將所有結點的核值結果存儲在賦權有向超圖核值文件中； 上述的步驟5.1中，所述的賦權有向超圖的改進壓縮的內存存儲格式如下: 步驟5.1.1,使用vwgts數組存儲賦權有向超圖中結點的權值信息,且vwgts數組的大小為賦權有向超圖中的結點個數； 步驟5.1.2，使用xadj數組存儲每個結點所有鄰接有向超邊列表的起始位置信息，即第i個結點的終止位置為第i+Ι個結點的起始位置減I,且xadj數組的大小為賦權有向超圖中的結點個數加1，xadj數組最後一個元素用於存放最後一個結點的終止位置； 步驟5.1.3，使用adjncy數組存儲每個結點所有鄰接有向超邊的列表信息，第i個結點的鄰接有向超邊列表存儲在adjncy數組中，從adjncy [xadj [i]]到adjncy[xadj[i+l]_l]； 步驟5.1.4，使用eptr數組存儲每條有向超邊所包含的結點列表的起始位置信息，即第j條有向超邊的終止位置為第j+Ι條有向超邊的起始位置減1，且eptr數組的大小為賦權有向超圖中的有向超邊條數加1，eptr數組最後一個元素用於存放最後一條有向超邊的終止位置； 步驟5.1.5，使用eind數組存儲每條有向超邊所包含結點的列表信息，其中每條有向超邊的尾端結點只有I個，且每條有向超邊尾端結點的所有直接前驅結點都包含在該有向超邊的源端子集中； 第j條有向超邊的結點列表存儲在eind數組中，從eind [eptr [j]]到eind[eptr[j+l]-l],其中第j條有向超邊的源端結點為eind [eptr [j]]到eind[eptr[j+l]-2],第 j 條有向超邊的尾端結點為 eind [eptr [j+1]-1]； 步驟5.1.6,使用hewgts數組存儲有向超邊的權值信息,且hewgts數組的大小為賦權有向超圖中的有向超邊數目； 上述的步驟5.3中，所述的結點屬性函數值的非嚴格降序排序的步驟如下: 步驟5.3.1，根據結點的屬性函數值屬於一定範圍內的整數，掃描所有結點的屬性函數值，統計每一種屬性函數值的結點個數，存儲在計數輔助數組bin中； 步驟5.3.2，藉助計數輔助數組bin，計算出在所有結點的屬性函數值中，小於該屬性函數值的結點個數，存儲在 位置輔助數組pos中； 步驟5.3.3，掃描所有結點的屬性函數值，針對每一個結點的屬性函數值，藉助位置輔助數組pos，得到該結點的屬性函數值在非嚴格降序排序的次序，並將該次序存儲在次序輔助數組vert中； 上述的步驟5.4中,所述的結點V的核值計算的步驟如下: 步驟5.4.1，將結點V的屬性函數值作為核值輸出； 步驟5.4.2,標記結點V從所在的超邊e中刪除； 步驟5.4.3，如果超邊e刪除結點V後，仍包含兩個及以上未被標記刪除的結點，則超邊e仍然存在，否則刪除超邊e; 步驟5.4.4，重新計算結點V的鄰接結點u的屬性函數值； 步驟5.4.5，如果鄰接結點u的屬性函數值大於結點V的屬性函數值，更新鄰接結點u的屬性函數值，並且藉助計數輔助數組bin、位置輔助數組pos和次序輔助數組vert的信息，快速更新鄰接結點u在所有結點的屬性函數值非嚴格降序排序的次序；否則不更新鄰接結點u的屬性函數值及其排序的次序。
【文檔編號】G06F9/50GK103870342SQ201410136337
【公開日】2014年6月18日 申請日期:2014年4月6日 優先權日:2014年4月6日
【發明者】孫凌宇, 冷明, 冷子陽 申請人:冷明, 孫凌宇, 冷子陽