[發(fā)明專利]基于元胞自動(dòng)機(jī)和賦權(quán)有向超圖的云計(jì)算任務(wù)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410137810.1
• 申請日: 2014-04-08
• 公開（公告）號: CN103902374B
• 公開（公告）日: 2017-01-18
• 發(fā)明（設(shè)計(jì)）人: 孫凌宇;冷明;冷子陽
• 申請（專利權(quán)）人: 冷明;孫凌宇;冷子陽
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.本發(fā)明的技術(shù)方案是這樣實(shí)現(xiàn)的：一種基于元胞自動(dòng)機(jī)和賦權(quán)有向超圖的云計(jì)算任務(wù)調(diào)度方法，其特征在于，具體步驟如下：

步驟1，類型類度分析，輸入云計(jì)算環(huán)境下用戶提交的任務(wù)，并對其進(jìn)行類型和類度的分析，確定任務(wù)的并行化程度及特點(diǎn)；

步驟2，進(jìn)程粒度分解，根據(jù)用戶任務(wù)的并行化程度及特點(diǎn)，以及云計(jì)算的資源共享分配方式等獨(dú)特性質(zhì)，對用戶任務(wù)按照進(jìn)程粒度級別進(jìn)行分解；

步驟3，資源特性分析，根據(jù)云計(jì)算的資源共享分配方式等獨(dú)特性質(zhì)，對分解后的任務(wù)進(jìn)行資源特性分析；

步驟4，賦權(quán)有向超圖文件生成，依據(jù)對任務(wù)資源特性的分析結(jié)果，建立描述其資源需求及依賴關(guān)系的賦權(quán)有向超圖模型，并按照改進(jìn)壓縮的文件存儲(chǔ)格式保存為賦權(quán)有向超圖文件；

步驟5，賦權(quán)有向超圖劃分，啟動(dòng)基于元胞自動(dòng)機(jī)的賦權(quán)有向超圖劃分程序，讀取賦權(quán)有向超圖文件，采用基于元胞自動(dòng)機(jī)的內(nèi)存壓縮存儲(chǔ)格式對賦權(quán)有向超圖進(jìn)行存儲(chǔ)，對生成的賦權(quán)有向超圖進(jìn)行劃分，將最終得到的劃分結(jié)果存儲(chǔ)在賦權(quán)有向超圖劃分文件中；

步驟6，任務(wù)子集構(gòu)造，在檢測到基于元胞自動(dòng)機(jī)的賦權(quán)有向超圖劃分程序完成劃分之后，從賦權(quán)有向超圖劃分文件中讀取相應(yīng)的劃分結(jié)果，依據(jù)賦權(quán)有向超圖的劃分結(jié)果構(gòu)造進(jìn)程級任務(wù)子集；

步驟7，任務(wù)映射調(diào)度，通過MapReduce任務(wù)調(diào)度模型，對基于賦權(quán)有向超圖優(yōu)化劃分構(gòu)造的任務(wù)子集進(jìn)行映射和調(diào)度，實(shí)現(xiàn)在云計(jì)算環(huán)境中的任務(wù)提交與執(zhí)行，有效地均衡云計(jì)算平臺(tái)的負(fù)載和縮短整個(gè)任務(wù)完成的時(shí)間跨度；

上述的步驟4中，所述的賦權(quán)有向超圖的改進(jìn)壓縮的文件存儲(chǔ)格式如下：

步驟4.1，文件格式的第1行第1個(gè)參數(shù)代表著賦權(quán)有向超邊的數(shù)目m，第2個(gè)參數(shù)代表著賦權(quán)結(jié)點(diǎn)的數(shù)目n；

步驟4.2，文件格式的第2行開始到第m+1行的每行代表著一條賦權(quán)有向超邊的相關(guān)信息，第1個(gè)數(shù)值為賦權(quán)有向超邊的權(quán)值信息，其余數(shù)值為賦權(quán)有向超邊的結(jié)點(diǎn)信息，其中每行的最后一個(gè)數(shù)值代表賦權(quán)有向超邊的尾端結(jié)點(diǎn)信息，且賦權(quán)有向超邊的源端結(jié)點(diǎn)信息處于賦權(quán)有向超邊的權(quán)值信息和尾端結(jié)點(diǎn)信息之間；

步驟4.3，文件格式的第m+2行開始到第m+n+1行的每行代表著一個(gè)賦權(quán)結(jié)點(diǎn)的權(quán)值信息；

上述的步驟5中，所述的基于元胞自動(dòng)機(jī)的賦權(quán)有向超圖劃分程序的步驟如下：

步驟5.1，讀取賦權(quán)有向超圖文件，采用基于元胞自動(dòng)機(jī)的內(nèi)存壓縮存儲(chǔ)格式對賦權(quán)有向超圖進(jìn)行存儲(chǔ)；

步驟5.2，元胞初始化，遍歷每個(gè)元胞并隨機(jī)給定元胞所處的狀態(tài)1和n之間的整數(shù)，分別代表元胞對應(yīng)結(jié)點(diǎn)所處的n個(gè)劃分子集V1…Vn中間的某個(gè)劃分子集，從而得到初始劃分；

步驟5.3，初始化二維輔助數(shù)組EDG[n][m]，依據(jù)初始劃分，初始化二維輔助數(shù)組EDG[n][m]；

步驟5.4，計(jì)算初始劃分的割切值，依據(jù)二維輔助數(shù)組EDG[n][m]，快速計(jì)算當(dāng)前劃分的割切值；

步驟5.5，循環(huán)初始化，初始化循環(huán)計(jì)數(shù)器COUNT為0；

步驟5.6，遍歷每個(gè)元胞是否結(jié)束，如果訪問未結(jié)束，即存在當(dāng)前元胞未被訪問，則轉(zhuǎn)步驟5.7；否則訪問結(jié)束，轉(zhuǎn)步驟5.13；

步驟5.7，計(jì)算當(dāng)前元胞的收益值，根據(jù)當(dāng)前元胞的狀態(tài)和鄰接元胞的狀態(tài)，快速計(jì)算當(dāng)前元胞的收益值；

步驟5.8，演化當(dāng)前元胞狀態(tài)，如果當(dāng)前元胞的收益值大于零，當(dāng)前元胞狀態(tài)一定從當(dāng)前狀態(tài)from翻轉(zhuǎn)到翻轉(zhuǎn)狀態(tài)to，否則當(dāng)前元胞狀態(tài)以設(shè)定的翻轉(zhuǎn)概率從當(dāng)前狀態(tài)from翻轉(zhuǎn)到翻轉(zhuǎn)狀態(tài)to；

步驟5.9，如果當(dāng)前元胞狀態(tài)從當(dāng)前狀態(tài)from翻轉(zhuǎn)到翻轉(zhuǎn)狀態(tài)to，則轉(zhuǎn)步驟5.10，否則轉(zhuǎn)步驟5.6；

步驟5.10，更新二維輔助數(shù)組EDG[n][m]，遍歷元胞的所有鄰接超邊e，執(zhí)行EDG[from][e]減1操作，EDG[to][e]加1操作；

步驟5.11，更新當(dāng)前劃分的割切值，依據(jù)二維輔助數(shù)組EDG[n][m]，快速計(jì)算當(dāng)前劃分的割切值；

步驟5.12，更新已找到的最優(yōu)劃分，轉(zhuǎn)步驟5.6；

步驟5.13，循環(huán)判斷，循環(huán)計(jì)數(shù)器COUNT加1，若滿足COUNT達(dá)到設(shè)定演化次數(shù)的條件1或者全部元胞都不再改變自身狀態(tài)的條件2時(shí)，執(zhí)行步驟5.14，否則返回步驟5.6；

步驟5.14，進(jìn)入到平衡階段，運(yùn)行基于FM-EE方法的賦權(quán)有向超圖劃分程序：由于在基于元胞自動(dòng)機(jī)的賦權(quán)有向超圖劃分過程中，可能違背賦權(quán)有向超圖劃分問題的平衡約束條件，因此在基于元胞自動(dòng)機(jī)的賦權(quán)有向超圖劃分所求解的基礎(chǔ)上，運(yùn)行基于FM-EE方法的賦權(quán)有向超圖劃分方法，使劃分解滿足平衡約束條件，從而得到賦權(quán)有向超圖劃分問題的劃分解；

步驟5.15，將最終得到的賦權(quán)有向超圖劃分結(jié)果存儲(chǔ)在賦權(quán)有向超圖劃分文件中；

上述的步驟5.1中，所述的賦權(quán)有向超圖的基于元胞自動(dòng)機(jī)的內(nèi)存壓縮存儲(chǔ)格式如下：

步驟5.1.1，使用ID數(shù)組存儲(chǔ)元胞對應(yīng)于賦權(quán)有向超圖中結(jié)點(diǎn)的編號信息，且ID數(shù)組的大小為賦權(quán)有向超圖中的結(jié)點(diǎn)個(gè)數(shù)；

步驟5.1.2，使用state數(shù)組存儲(chǔ)元胞的狀態(tài)信息，且state數(shù)組的大小為賦權(quán)有向超圖中的結(jié)點(diǎn)個(gè)數(shù)；

步驟5.1.3，使用vwgts數(shù)組存儲(chǔ)元胞對應(yīng)于賦權(quán)有向超圖中結(jié)點(diǎn)的權(quán)值信息，且vwgts數(shù)組的大小為賦權(quán)有向超圖中的結(jié)點(diǎn)個(gè)數(shù)；

步驟5.1.4，使用xadj數(shù)組存儲(chǔ)每個(gè)結(jié)點(diǎn)所有鄰接賦權(quán)有向超邊列表的起始位置信息，即第i個(gè)結(jié)點(diǎn)的終止位置為第i+1個(gè)結(jié)點(diǎn)的起始位置減1，且xadj數(shù)組的大小為賦權(quán)有向超圖中的結(jié)點(diǎn)個(gè)數(shù)加1，?xadj數(shù)組最后一個(gè)元素用于存放最后一個(gè)結(jié)點(diǎn)的終止位置；

步驟5.1.5，使用adjncy數(shù)組存儲(chǔ)每個(gè)結(jié)點(diǎn)所有鄰接賦權(quán)有向超邊的列表信息，第i個(gè)結(jié)點(diǎn)的鄰接賦權(quán)有向超邊列表存儲(chǔ)在adjncy數(shù)組中，從adjncy[xadj[i]]到adjncy[xadj[i+1]-1]；

步驟5.1.6，使用eptr數(shù)組存儲(chǔ)每條賦權(quán)有向超邊所包含的結(jié)點(diǎn)列表的起始位置信息，即第j條賦權(quán)有向超邊的終止位置為第j+1條賦權(quán)有向超邊的起始位置減1，且eptr數(shù)組的大小為賦權(quán)有向超圖中的賦權(quán)有向超邊條數(shù)加1，?eptr數(shù)組最后一個(gè)元素用于存放最后一條賦權(quán)有向超邊的終止位置；

步驟5.1.7，使用eind數(shù)組存儲(chǔ)每條賦權(quán)有向超邊所包含結(jié)點(diǎn)的列表信息，其中每條賦權(quán)有向超邊的尾端結(jié)點(diǎn)只有1個(gè)，且每條賦權(quán)有向超邊尾端結(jié)點(diǎn)的所有直接前驅(qū)結(jié)點(diǎn)都包含在該賦權(quán)有向超邊的源端子集中；第j條賦權(quán)有向超邊的結(jié)點(diǎn)列表存儲(chǔ)在eind數(shù)組中，從eind[eptr[j]]到eind[eptr[j+1]-1]，其中第j條賦權(quán)有向超邊的源端結(jié)點(diǎn)為eind[eptr[j]]到eind[eptr[j+1]-2]，第j條賦權(quán)有向超邊的尾端結(jié)點(diǎn)為eind[eptr[j+1]-1]；

步驟5.1.8，使用hewgts數(shù)組存儲(chǔ)賦權(quán)有向超邊的權(quán)值信息，且hewgts數(shù)組的大小為賦權(quán)有向超圖中的賦權(quán)有向超邊條數(shù)；

上述的步驟5.3中，所述的初始化二維輔助數(shù)組EDG[n][m]的步驟如下：

步驟5.3.1，二維輔助數(shù)組EDG[n][m]清零；

步驟5.3.2，讀取eptr數(shù)組和eind數(shù)組存儲(chǔ)的每條賦權(quán)有向超邊所包含的結(jié)點(diǎn)信息，基于初始劃分計(jì)算每條賦權(quán)有向超邊在n個(gè)劃分子集V1…Vn的結(jié)點(diǎn)個(gè)數(shù)，即二維輔助數(shù)組EDG[n][m]的n行分別存放m條賦權(quán)有向超邊在n個(gè)劃分子集的結(jié)點(diǎn)個(gè)數(shù)；

上述的步驟5.4和步驟5.11中，所述的快速計(jì)算當(dāng)前劃分的割切值的步驟如下：

步驟5.4.1，劃分割切值清零；

步驟5.4.2，遍歷每條賦權(quán)有向超邊是否結(jié)束，如果訪問未結(jié)束，即存在賦權(quán)有向超邊e未被訪問，則轉(zhuǎn)步驟5.4.3；否則訪問結(jié)束，返回劃分割切值；

步驟5.4.3，如果滿足EDG[i][e]?≥1的條件1和EDG[j][e]≥1的條件2時(shí)，意味著賦權(quán)有向超邊e在劃分子集Vi和Vj的結(jié)點(diǎn)個(gè)數(shù)都大于等于1，即可判定賦權(quán)有向超邊e是兩棲邊，并將劃分割切值累加上當(dāng)前賦權(quán)有向超邊的權(quán)值；否則判定賦權(quán)有向超邊e不是兩棲邊，劃分割切值不變；

步驟5.4.4，轉(zhuǎn)步驟5.4.2；

上述的步驟5.7中，所述的快速計(jì)算當(dāng)前元胞收益值的步驟如下：

步驟5.7.1，元胞收益值清零；

步驟5.7.2，讀取元胞的當(dāng)前狀態(tài)from和翻轉(zhuǎn)狀態(tài)to；

步驟5.7.3，遍歷元胞的所有鄰接賦權(quán)有向超邊e，若二維數(shù)組EDG[from][e]值為1，則將收益值加上賦權(quán)有向超邊e的權(quán)值；若二維數(shù)組EDG[to][e]值為0，則將收益值減去賦權(quán)有向超邊e的權(quán)值；

步驟5.7.4，返回元胞收益值。