最小費(fèi)用最大流的資源調(diào)度

并行作業(yè)是大規(guī)模資源調(diào)度的研究熱點(diǎn).已有的研究工作通常采用隊(duì)列進(jìn)行資源調(diào)度建模,僅能滿足局部最優(yōu)解且只能適應(yīng)調(diào)度目標(biāo)固定不變的場(chǎng)景,靈活性不夠.提出了一種基于最小費(fèi)用最大流的大規(guī)模資源調(diào)度建模方法,將任務(wù)的資源需求和物理資源供給問(wèn)題轉(zhuǎn)換成最小費(fèi)用最大流圖的構(gòu)造和求解問(wèn)題.首先,選擇公平性、優(yōu)先級(jí)和放置約束這 3 種典型度量作為切入點(diǎn),從資源視角映射為圖的構(gòu)造問(wèn)題,通過(guò)改變圖的結(jié)構(gòu),使其具備適應(yīng)性調(diào)整能力;其次,針對(duì)圖的求解時(shí)間復(fù)雜度高的問(wèn)題,實(shí)現(xiàn)了一種增量式優(yōu)化算法;最后,實(shí)驗(yàn)對(duì)比公平性、優(yōu)先級(jí)和放置約束這 3 種資源調(diào)度典型系統(tǒng),驗(yàn)證了該方法可通過(guò)按需配置,支持多種調(diào)度目標(biāo),具備靈活性.并通過(guò)實(shí)驗(yàn)仿真,驗(yàn)證了萬(wàn)級(jí)規(guī)模下,基于圖的資源調(diào)度延遲比基于未優(yōu)化圖算法的資源調(diào)度延遲最多降低 90%.