[發(fā)明專利]一種基于拓?fù)渑判虻娜蝿?wù)調(diào)度方法及系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202110252562.5
• 申請(qǐng)日: 2021-03-09
• 公開（公告）號(hào): CN112948087A
• 公開（公告）日: 2021-06-11
• 發(fā)明（設(shè)計(jì)）人: 李肯立;雷直航;陳岑;肖正;劉楚波;段明星;陽(yáng)王東;唐卓
• 申請(qǐng)（專利權(quán)）人: 湖南大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48
• 代理公司: 武漢臻誠(chéng)專利代理事務(wù)所(普通合伙) 42233
• 代理人: 宋業(yè)斌

1.一種基于拓?fù)渑判虻娜蝿?wù)調(diào)度方法，其特征在于，包括：

獲取大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖，并基于拓?fù)渑判虻拇只惴▽?duì)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖進(jìn)行多級(jí)粗化處理，以獲得對(duì)應(yīng)的有向無(wú)環(huán)初始調(diào)度圖；

基于小規(guī)模調(diào)度算法對(duì)所述有向無(wú)環(huán)初始調(diào)度圖進(jìn)行初始劃分，以獲得所述有向無(wú)環(huán)初始調(diào)度圖的粗化圖劃分結(jié)果；

基于細(xì)化算法將所述粗化圖劃分結(jié)果映射回所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖，并進(jìn)行細(xì)化調(diào)整，以獲得所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖的任務(wù)調(diào)度劃分結(jié)果。

2.如權(quán)利要求1所述的基于拓?fù)渑判虻娜蝿?wù)調(diào)度方法，其特征在于，所述基于拓?fù)渑判虻拇只惴▽?duì)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖進(jìn)行多級(jí)粗化處理，以獲得對(duì)應(yīng)的有向無(wú)環(huán)初始調(diào)度圖這一過(guò)程進(jìn)一步包括：

根據(jù)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中每一節(jié)點(diǎn)的輸入順序，對(duì)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中的節(jié)點(diǎn)依次遍歷以進(jìn)行聚類，若所有節(jié)點(diǎn)完成遍歷聚類后，所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中的節(jié)點(diǎn)數(shù)量大于預(yù)設(shè)閾值，則重復(fù)上述遍歷聚類過(guò)程，直至所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中的節(jié)點(diǎn)數(shù)量不大于所述預(yù)設(shè)閾值，以得到所述有向無(wú)環(huán)初始調(diào)度圖。

3.如權(quán)利要求2所述的基于拓?fù)渑判虻娜蝿?wù)調(diào)度方法，其特征在于，所述根據(jù)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中每一節(jié)點(diǎn)的輸入順序，對(duì)所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中的節(jié)點(diǎn)依次遍歷以進(jìn)行聚類這一過(guò)程進(jìn)一步包括：

對(duì)于所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中的任一節(jié)點(diǎn)，若所述任一節(jié)點(diǎn)滿足第一預(yù)設(shè)條件，則從所述任一節(jié)點(diǎn)的候選節(jié)點(diǎn)集合中選取好鄰居節(jié)點(diǎn)，并將選取的好鄰居節(jié)點(diǎn)與所述任一節(jié)點(diǎn)進(jìn)行聚類；若所述任一節(jié)點(diǎn)不滿足所述第一預(yù)設(shè)條件，則不對(duì)所述任一節(jié)點(diǎn)進(jìn)行聚類，并根據(jù)所述輸入順序，繼續(xù)對(duì)所述任一節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)進(jìn)行聚類，直至所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖中所有節(jié)點(diǎn)均完成遍歷聚類；

其中，所述候選節(jié)點(diǎn)集合是由能夠與所述任一節(jié)點(diǎn)進(jìn)行聚類的候選節(jié)點(diǎn)所確定的，所述第一預(yù)設(shè)條件為所述任一節(jié)點(diǎn)為單一節(jié)點(diǎn)且所述候選節(jié)點(diǎn)集合不為空；

所述任一節(jié)點(diǎn)的候選節(jié)點(diǎn)滿足第二預(yù)設(shè)條件，所述第二預(yù)設(shè)條件包括與所述任一節(jié)點(diǎn)為鄰居節(jié)點(diǎn)、與所述任一節(jié)點(diǎn)之間Top值差值的絕對(duì)值小于1以及第二預(yù)設(shè)子條件，所述第二預(yù)設(shè)子條件為所述任一節(jié)點(diǎn)的壞鄰居節(jié)點(diǎn)數(shù)量為0或者所述任一節(jié)點(diǎn)的壞鄰居節(jié)點(diǎn)數(shù)量為1且所述任一節(jié)點(diǎn)的壞鄰居節(jié)點(diǎn)位于所述候選節(jié)點(diǎn)所處的聚類；

所述任一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)指的是與所述任一節(jié)點(diǎn)直接相連的直接前驅(qū)節(jié)點(diǎn)或者直接后繼節(jié)點(diǎn)；所述任一節(jié)點(diǎn)的好鄰居節(jié)點(diǎn)指的是基于預(yù)設(shè)規(guī)則選取的以能夠與所述任一節(jié)點(diǎn)進(jìn)行聚類的鄰居節(jié)點(diǎn)；若所述任一節(jié)點(diǎn)所處聚類中每一節(jié)點(diǎn)與所述任一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)所處聚類中每一節(jié)點(diǎn)之間Top值差值的絕對(duì)值小于1，則所述鄰居節(jié)點(diǎn)為所述任一節(jié)點(diǎn)的壞鄰居節(jié)點(diǎn)；所述任一節(jié)點(diǎn)的Top值指的是從所述大規(guī)模有向無(wú)環(huán)任務(wù)調(diào)度圖的入度節(jié)點(diǎn)至所述任一節(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。

4.如權(quán)利要求3所述的基于拓?fù)渑判虻娜蝿?wù)調(diào)度方法，其特征在于，所述方法進(jìn)一步包括將選取的好鄰居節(jié)點(diǎn)與所述任一節(jié)點(diǎn)進(jìn)行聚類之后的如下步驟：

將所述任一節(jié)點(diǎn)作為節(jié)點(diǎn)u，對(duì)于所述節(jié)點(diǎn)u的任一鄰居節(jié)點(diǎn)v，若所述節(jié)點(diǎn)u與所述節(jié)點(diǎn)v之間Top值差值的絕對(duì)值大于1，則不對(duì)所述節(jié)點(diǎn)u的壞鄰居信息進(jìn)行更新；

若所述節(jié)點(diǎn)u與所述節(jié)點(diǎn)之間Top值差值的絕對(duì)值不大于1且所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)數(shù)量為0，則將所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)數(shù)量賦值為1，并將所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)記為所述節(jié)點(diǎn)u所處的聚類；

若所述節(jié)點(diǎn)u與所述節(jié)點(diǎn)之間Top值差值的絕對(duì)值不大于1、所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)數(shù)量為1且所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)不位于所述節(jié)點(diǎn)v所處的聚類，則將所述節(jié)點(diǎn)v的壞鄰居節(jié)點(diǎn)數(shù)量賦值為2。