[發(fā)明專利]一種基于貓頭鷹搜索算法的計(jì)算密集型云工作流調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811336040.8
• 申請(qǐng)日: 2018-11-12
• 公開（公告）號(hào): CN109710372B
• 公開（公告）日: 2020-10-13
• 發(fā)明（設(shè)計(jì)）人: 袁艷;李慧芳;韋琬雯;胡光政;鄒偉東;柴森春;夏元清
• 申請(qǐng)（專利權(quán)）人: 北京理工大學(xué)
• 主分類號(hào): G06F9/455
• 分類號(hào): G06F9/455;G06F9/48;G06N3/00;G06F16/9535
• 代理公司: 北京正陽理工知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11639
• 代理人: 唐華

本發(fā)明提出了一種基于貓頭鷹搜索算法的計(jì)算密集型云工作流調(diào)度方法，屬于云計(jì)算技術(shù)領(lǐng)域。通過在貓頭鷹搜索算法中修改種群迭代更新公式，使每個(gè)調(diào)度方案根據(jù)最優(yōu)調(diào)度方案對(duì)其影響大小來更新，使尋優(yōu)更具針對(duì)性；在種群迭代更新機(jī)制中，通過利用遺傳變異思想，引入隨機(jī)性，避免搜索過程陷入局部最優(yōu)，可以在更短的時(shí)間內(nèi)得到最優(yōu)調(diào)度方案，實(shí)現(xiàn)對(duì)虛擬機(jī)進(jìn)行合理的分配，對(duì)任務(wù)進(jìn)行高效調(diào)度。本發(fā)明能夠有效克服現(xiàn)有方法中最優(yōu)解搜索隨機(jī)性大、易于陷入局部最優(yōu)且收斂速度慢的缺點(diǎn)，提升搜索效率、縮短搜索時(shí)間，可在更短的時(shí)間內(nèi)尋找到更優(yōu)的調(diào)度方案，減少工作流調(diào)度的時(shí)間開銷。

技術(shù)領(lǐng)域

本發(fā)明涉及一種云工作流調(diào)度方法，具體涉及一種基于貓頭鷹搜索算法的計(jì)算密集型云工作流調(diào)度方法，屬于云計(jì)算技術(shù)領(lǐng)域。

背景技術(shù)

云計(jì)算作為一種商業(yè)計(jì)算模式，采用虛擬化技術(shù)，將數(shù)據(jù)中心的存儲(chǔ)、計(jì)算以及網(wǎng)絡(luò)通信等資源整合為一個(gè)共享的、可動(dòng)態(tài)配置的計(jì)算資源池，為用戶提供按使用付費(fèi)的計(jì)算服務(wù)。用戶無需購置任何服務(wù)器等硬件資源，即可通過可用的、便捷的網(wǎng)絡(luò)訪問，進(jìn)入可配置的共享計(jì)算資源池(例如服務(wù)器、存儲(chǔ)、應(yīng)用軟件和網(wǎng)絡(luò)等)，按需獲取計(jì)算能力、存儲(chǔ)空間和信息服務(wù)。

隨著云計(jì)算的不斷發(fā)展，大規(guī)模的復(fù)雜工作流成為云計(jì)算應(yīng)用的新模式。云工作流的執(zhí)行主要包括任務(wù)調(diào)度和資源供給兩個(gè)階段。在任務(wù)調(diào)度過程中，需要根據(jù)適當(dāng)?shù)恼{(diào)度策略，為用戶請(qǐng)求的任務(wù)選擇合適的虛擬機(jī)，并滿足其服務(wù)質(zhì)量(QoS)等約束，從而完成整個(gè)調(diào)度過程。計(jì)算密集型云工作流，由多個(gè)具有相互依賴關(guān)系的子任務(wù)組成，因此，在整個(gè)工作流調(diào)度過程中，不僅要考慮任務(wù)的執(zhí)行時(shí)間，還需要滿足任務(wù)之間的依賴關(guān)系約束并使得整個(gè)工作流的執(zhí)行跨度時(shí)間(makespan)最短。不同的任務(wù)分配策略會(huì)直接影響整個(gè)云工作流的執(zhí)行時(shí)間與成本，如何為云工作流任務(wù)分配最合適的計(jì)算資源，并在滿足任務(wù)間邏輯依賴約束的同時(shí)實(shí)現(xiàn)其調(diào)度目標(biāo)，成為各個(gè)云服務(wù)提供商亟需解決的問題。

云工作流調(diào)度是一類典型的NP-hard問題，目前，主要采用啟發(fā)式算法和隨機(jī)搜索算法求解。啟發(fā)式算法主要分為列表調(diào)度、任務(wù)復(fù)制、任務(wù)集合簇等，例如HEFT、MIN-MIN、MIN-MAX，不易找到近優(yōu)解。隨機(jī)搜索算法，主要包括遺傳算法、粒子群算法、免疫進(jìn)化算法等，本質(zhì)是設(shè)計(jì)一種高效的搜索策略。其中，遺傳算法等進(jìn)化算法具有全局搜索優(yōu)勢以及避免陷入局部最優(yōu)的能力，但搜索時(shí)間過長，影響算法的實(shí)時(shí)性；群智能優(yōu)化算法具有收斂速度快，且適應(yīng)面廣，但是缺乏有效的局部搜索機(jī)制。

發(fā)明內(nèi)容

本發(fā)明的目的是為了解決計(jì)算密集型云工作調(diào)度問題，提出一種基于改進(jìn)貓頭鷹搜索算法的計(jì)算密集型云工作流調(diào)度方法。其基本思想是：采用貓頭鷹搜索算法，對(duì)云工作流中所有依賴任務(wù)到虛擬機(jī)資源映射的不同調(diào)度方案進(jìn)行遍歷搜索，尋找具有最小工作流執(zhí)行跨度時(shí)間的調(diào)度方案。同時(shí)，根據(jù)云工作流的特點(diǎn)，對(duì)現(xiàn)有的貓頭鷹搜索算法進(jìn)行改進(jìn)，一是通過聲強(qiáng)平方反比定律將強(qiáng)度變化量定義為最優(yōu)解(即最優(yōu)調(diào)度方案)對(duì)其它不同個(gè)體(或調(diào)度方案)的影響大小，并以此對(duì)不同個(gè)體的尋優(yōu)步長進(jìn)行自適應(yīng)調(diào)節(jié)，從而大大提高了最優(yōu)解的搜索效率；二是針對(duì)云工作流調(diào)度問題的特點(diǎn)，修改了個(gè)體的尋優(yōu)方向，以避免產(chǎn)生過多的無效解，并使所有個(gè)體根據(jù)不同的步長直接向最優(yōu)解逐漸逼近，從而提高了個(gè)體解的穩(wěn)定性、改善了整個(gè)算法的尋優(yōu)速度；三是針對(duì)群智能優(yōu)化算法容易陷入局部最優(yōu)的問題，利用進(jìn)化計(jì)算的變異思想，通過在種群迭代更新機(jī)制中增加變異策略來引入隨機(jī)性，并當(dāng)最優(yōu)解迭代l次尚未更新時(shí)，隨機(jī)更改一些調(diào)度方案中個(gè)別任務(wù)與虛擬機(jī)的映射關(guān)系，以跳出局部最優(yōu)，尋找全局更好的調(diào)度方案。

本發(fā)明方法包括以下步驟：

步驟一、輸入用戶提交的待調(diào)度計(jì)算密集型云工作流模型及其所包含的依賴子任務(wù)集合，可供租賃的虛擬機(jī)集合；

步驟二、將各云工作流子任務(wù)調(diào)度至最合適虛擬機(jī)上執(zhí)行的過程，建模為標(biāo)準(zhǔn)的最小值求解問題。其調(diào)度目標(biāo)為：優(yōu)化整個(gè)云工作流的執(zhí)行跨度時(shí)間makespan，使所有云工作流任務(wù)執(zhí)行完畢所花費(fèi)的時(shí)間最短。