[發明專利]云計算環境中的基于結點屬性函數的任務核值計算方法

有效

• 申請號: 201410136337.5
• 申請日: 2014-04-06
• 公開（公告）號: CN103870342A
• 公開（公告）日: 2014-06-18
• 發明（設計）人: 孫凌宇;冷明;冷子陽
• 申請（專利權）人: 冷明;孫凌宇;冷子陽
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/38;H04L29/08
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種云計算環境中基于結點屬性函數的任務核值計算方法，其特征在于，具體步驟如下：

步驟1，類型類度分析，輸入云計算環境中用戶提交的任務，并對其進行類型和類度的分析，確定任務的并行化程度和特點；

步驟2，進程粒度分解，根據用戶任務的并行化程度和特點，以及云計算的資源共享分配方式等獨特性質，對用戶任務按照進程粒度級別進行分解；

步驟3，資源特性分析，根據云計算的資源共享分配方式等獨特性質，對分解后的任務進行資源特性分析；

步驟4，賦權有向超圖文件生成，依據對任務資源特性的分析結果，建立描述其資源需求及依賴關系的賦權有向超圖模型，并按照改進壓縮的文件存儲格式保存為賦權有向超圖文件；

步驟5，賦權有向超圖核值計算，啟動賦權有向超圖核值計算程序，讀取賦權有向超圖文件，采用改進壓縮的內存存儲格式對賦權有向超圖進行存儲，對生成的賦權有向超圖中的每個結點，基于結點屬性函數計算其核值，將所有結點的核值結果存儲在賦權有向超圖核值文件中；

上述的步驟4中，所述的賦權有向超圖的改進壓縮的文件存儲格式的步驟如下：

步驟4.1，文件格式的第1行第1個參數代表著有向賦權超邊的數目m，第2個參數代表著賦權結點的數目n；

步驟4.2，文件格式的第2行開始到第m+1行的每行代表著一條有向賦權超邊的相關信息，第1個數值為有向賦權超邊的權值信息，其余數值為有向賦權超邊的結點信息，其中每行的最后一個數值代表有向賦權超邊的尾端結點信息，且有向賦權超邊的源端結點信息處于有向賦權超邊的權值信息和尾端結點信息之間；

步驟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+1個結點的起始位置減1，且xadj數組的大小為賦權有向超圖中的結點個數加1，xadj數組最后一個元素用于存放最后一個結點的終止位置；

步驟5.1.3，使用adjncy數組存儲每個結點所有鄰接有向超邊的列表信息，第i個結點的鄰接有向超邊列表存儲在adjncy數組中，從adjncy[xadj[i]]到adjncy[xadj[i+1]-1]；

步驟5.1.4，使用eptr數組存儲每條有向超邊所包含的結點列表的起始位置信息，即第j條有向超邊的終止位置為第j+1條有向超邊的起始位置減1，且eptr數組的大小為賦權有向超圖中的有向超邊條數加1，eptr數組最后一個元素用于存放最后一條有向超邊的終止位置；

步驟5.1.5，使用eind數組存儲每條有向超邊所包含結點的列表信息，其中每條有向超邊的尾端結點只有1個，且每條有向超邊尾端結點的所有直接前驅結點都包含在該有向超邊的源端子集中；

第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]；

步驟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的屬性函數值及其排序的次序。