[發(fā)明專利]一種基于競(jìng)態(tài)條件的任務(wù)調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010031828.9
• 申請(qǐng)日: 2020-01-13
• 公開（公告）號(hào): CN111258730A
• 公開（公告）日: 2020-06-09
• 發(fā)明（設(shè)計(jì)）人: 李思照;韓新宇;孫建國(guó);鞏建光;閻梓寧;王文衫
• 申請(qǐng)（專利權(quán)）人: 哈爾濱工程大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明屬于任務(wù)調(diào)度技術(shù)領(lǐng)域，具體涉及一種基于競(jìng)態(tài)條件的任務(wù)調(diào)度方法。本發(fā)明通過(guò)不確定矩陣描述時(shí)間序列特征以及測(cè)量任務(wù)執(zhí)行不確定性，利用最大熵優(yōu)化發(fā)提出的任務(wù)調(diào)度算法確保任務(wù)執(zhí)行期間發(fā)生的競(jìng)態(tài)條件概率最低。本發(fā)明的任務(wù)調(diào)度優(yōu)化方法在低功耗系統(tǒng)平臺(tái)有更高的CPU利用率，吞吐量和更低的計(jì)算復(fù)雜度和任務(wù)執(zhí)行時(shí)間，具有一定的研究和使用價(jià)值。

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

本發(fā)明屬于任務(wù)調(diào)度技術(shù)領(lǐng)域，具體涉及一種基于競(jìng)態(tài)條件的任務(wù)調(diào)度方法。

背景技術(shù)

在多任務(wù)計(jì)算系統(tǒng)中，線程通常被用來(lái)為響應(yīng)某些事件而來(lái)執(zhí)行并行操作。由于這些事件的內(nèi)在不確定性，當(dāng)不同的線程以非因果順序訪問(wèn)一個(gè)共享資源(例如總線、內(nèi)存)并且至少有一個(gè)線程必須在共享資源上寫入時(shí)，就會(huì)出現(xiàn)競(jìng)態(tài)條件。由于競(jìng)態(tài)條件會(huì)導(dǎo)致不可預(yù)知的后果，因此，通過(guò)智能的競(jìng)態(tài)條件檢測(cè)和有效的任務(wù)調(diào)度來(lái)減少競(jìng)爭(zhēng)是至關(guān)重要的。

如今已經(jīng)有一些現(xiàn)有的研究對(duì)競(jìng)態(tài)條件進(jìn)行檢測(cè)。通過(guò)在編譯時(shí)識(shí)別所有可能的競(jìng)態(tài)條件，靜態(tài)方法是可以有高覆蓋率的，但是通過(guò)靜態(tài)分析檢測(cè)競(jìng)態(tài)條件在系統(tǒng)運(yùn)行時(shí)是不可判定的。因此又有人提出了動(dòng)態(tài)檢測(cè)方法，一般將動(dòng)態(tài)方法分類為“on-the-fly”或“post-mortem”兩種，這些方法都可以檢測(cè)系統(tǒng)在執(zhí)行的過(guò)程中出現(xiàn)的競(jìng)態(tài)條件。

雖然研究者提出了眾多優(yōu)化任務(wù)調(diào)度技術(shù)，但是，在復(fù)雜的多核計(jì)算系統(tǒng)中應(yīng)用上述提到的現(xiàn)有的方法，競(jìng)態(tài)條件檢測(cè)的性能就會(huì)嚴(yán)重下降，因?yàn)檫@些方法沒(méi)有考慮硬件相關(guān)的因素。在面向硬件的方法中，需要考慮與硬件相關(guān)的因素，如內(nèi)存的層次結(jié)構(gòu)或者緩存一致性模型。此外，由于不同的執(zhí)行環(huán)境表現(xiàn)出不同的事件發(fā)生概率分布，多核計(jì)算系統(tǒng)中的任務(wù)執(zhí)行環(huán)境對(duì)競(jìng)態(tài)條件有很大的影響。這里的執(zhí)行環(huán)境指的是系統(tǒng)硬件平臺(tái)(例如并行處理器的核數(shù))、應(yīng)用程序(例如FFT)，輸入?yún)?shù)(例如輸入數(shù)據(jù)的大小)等。不過(guò)，這些現(xiàn)有的方法都沒(méi)有將執(zhí)行環(huán)境視為設(shè)計(jì)參數(shù)。因此，他們的競(jìng)態(tài)條件檢測(cè)性能在多核計(jì)算系統(tǒng)中并不是最佳的。

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

本發(fā)明的目的在于提供通過(guò)不確定矩陣描述時(shí)間序列特征以及測(cè)量任務(wù)執(zhí)行不確定性，利用最大熵優(yōu)化法提出的新算法確保任務(wù)執(zhí)行期間發(fā)生的競(jìng)態(tài)條件概率最低的一種基于競(jìng)態(tài)條件的任務(wù)調(diào)度方法。

本發(fā)明的目的通過(guò)如下技術(shù)方案來(lái)實(shí)現(xiàn)：包括以下步驟：

步驟1：輸入任務(wù)調(diào)度序列；

步驟2：構(gòu)造競(jìng)態(tài)條件檢測(cè)模型；

某操作事件e作為輸入，識(shí)別競(jìng)態(tài)條件和Happened-Before關(guān)系；

若輸入的操作事件e為接收消息事件，則其對(duì)應(yīng)于發(fā)送消息事件e_s，并且會(huì)在相同任務(wù)中發(fā)現(xiàn)每一個(gè)前置的接收消息事件e′；如果e′||e_s，則判定在e_s和e′_s之間存在競(jìng)態(tài)條件，用表示；

若輸入的操作事件e為獲取信號(hào)量事件，則其對(duì)應(yīng)于發(fā)送信號(hào)量事件e_g，并且會(huì)在相同任務(wù)中發(fā)現(xiàn)每一個(gè)前置的獲取信號(hào)量e′；如果e′||e_g，則在e′和e_g之間存在競(jìng)態(tài)條件，用表示；

如果n個(gè)操作事件形成了執(zhí)行序列且產(chǎn)生的時(shí)間序列t₁t₂…t_nt₁，則判定為非災(zāi)難性的競(jìng)態(tài)條件；

步驟3：確定競(jìng)態(tài)集合；

由于競(jìng)態(tài)條件的不確定性，最大熵模型函數(shù)p(y|x)是競(jìng)態(tài)條件可能發(fā)生的最大概率，因此可以獲得最大發(fā)生概率的競(jìng)態(tài)集合；最大熵模型函數(shù)p(y|x)求解方法為：