[發(fā)明專利]面向多源多核系統(tǒng)的基于超任務(wù)網(wǎng)的多核調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201710026904.5
• 申請日: 2017-01-15
• 公開（公告）號: CN107329822B
• 公開（公告）日: 2022-01-28
• 發(fā)明（設(shè)計）人: 齊德昱;周娜琴;沈陽;郭靖;張長建;李雯霖
• 申請（專利權(quán)）人: 齊德昱
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發(fā)明公開了一種多源多核系統(tǒng)的調(diào)度方法，綜合處理了任務(wù)模塊間的生產(chǎn)者?消費者相關(guān)性和結(jié)構(gòu)相關(guān)性，以及任務(wù)間由于競爭資源而存在的動態(tài)間接相關(guān)性，實現(xiàn)任務(wù)到多源多核系統(tǒng)的面向性能的最優(yōu)分配。該方法以描述任務(wù)的兩種相關(guān)性的超任務(wù)網(wǎng)為輸入，通過超任務(wù)網(wǎng)的最優(yōu)拓?fù)湫蛄袠?gòu)造與多源多處理器的核協(xié)同網(wǎng)構(gòu)造,實現(xiàn)兩次空載消減,解決了假忙問題，使傳統(tǒng)調(diào)度算法相關(guān)性約束條件“旋轉(zhuǎn)”到超任務(wù)網(wǎng)，解決了調(diào)度算法不能解決這種動態(tài)性的問題.該方法也可用硬件或軟硬件結(jié)合實現(xiàn),給出一種軟件定義CPU的模式SD?CPU，成為一種新的基礎(chǔ)計算實體。

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

本發(fā)明涉及計算機(jī)軟件領(lǐng)域，尤其是計算機(jī)操作系統(tǒng)的調(diào)度模型(體系)。

背景技術(shù)

非對稱多核系統(tǒng)是指由單一CPU的多核或多CPU(含SMP、NoC-MP、Mesh-MP等多CPU體系)的多核,通過網(wǎng)絡(luò)互聯(lián)構(gòu)成的計算系統(tǒng)。在非對稱多核系統(tǒng)中，要實現(xiàn)高效的多任務(wù)和大任務(wù)執(zhí)行,任務(wù)調(diào)度問題是必須解決的一個關(guān)鍵問題。高效的任務(wù)調(diào)度策略和算法可以充分利用非對稱多核系統(tǒng)的處理能力。然而，一般任務(wù)調(diào)度問題已被證明是一個NP完全問題，因此，它引起了眾多學(xué)者的關(guān)注，成為目前計算機(jī)研究領(lǐng)域中的一個焦點。

在任務(wù)調(diào)度方面，已有人做了大量研究，然而，歸納起來，目前相關(guān)研究中主要存在下列問題：

(A)算法缺乏對任務(wù)相關(guān)性的考慮

目前的大多數(shù)調(diào)度算法都沒有考慮任務(wù)的相關(guān)性。有的雖然考慮了相關(guān)性，也是只考慮了多線程同步引起的相關(guān)性，對于大任務(wù)中模塊間的相關(guān)性、多任務(wù)間的因為資源競爭引起的相關(guān)性(稱為間接相關(guān)性)，都缺乏考慮。有的研究雖然考慮過競爭資源引起的相關(guān)性，但也局限于考慮不同類型的計算行為調(diào)配不同類型的核，而沒有根據(jù)相關(guān)關(guān)系組織核的分配。事實上，相關(guān)性既是個提高調(diào)度質(zhì)量(減少空載)的根本問題，也是個難以處理的問題。

(B)算法模式的局限性

目前的針對OS下的任務(wù)的多核調(diào)度方法，大多數(shù)是直接的基于集合映射，中間未采用有效的數(shù)據(jù)結(jié)構(gòu)。相應(yīng)的算法實現(xiàn)，大多是基于集合映射的整數(shù)規(guī)劃方法。雖然也有采用進(jìn)化算法的，但由于時間復(fù)雜度的原因，無法實用。

整數(shù)規(guī)劃的求解的基本思想是一個多步?jīng)Q策模式，每一步都是一種試探，可行則往下進(jìn)行，不可行則重新計算(產(chǎn)生回溯)。具體的整數(shù)規(guī)劃法有分枝定界法、割平面法、隱枚舉法等。

這種方法與約束條件密切相關(guān)，當(dāng)約束條件很復(fù)雜時，很難找到較為理想的規(guī)劃，導(dǎo)致回溯的增多。特別是，對于約束條件動態(tài)變化的情況(例如，任務(wù)的間接相關(guān)性，因為任務(wù)的新增與完成以及任務(wù)的處于不同計算階段，相關(guān)性會動態(tài)變化)，這種方法的效率將更差。

(C)相關(guān)性的解決路線問題

目前的調(diào)度算法，盡管有些考慮了任務(wù)的相關(guān)性，但仍然采用基于整數(shù)規(guī)劃的方法，將相關(guān)性作為了約束條件，但相關(guān)性動態(tài)復(fù)雜化或者動態(tài)變化時，不適合針對約束條件進(jìn)行決策。這種路線，既不能充分處理相關(guān)性，也不可能獲得有效的算法。

(D)缺乏考慮可再入分配

目前的調(diào)度算法，遇到需要重新分配物理核的時候，大多采用“遷移”的方式，產(chǎn)生較大的遷移代價，這種遷移相當(dāng)于處理器的中斷體系。事實上，有些重新分配的情況，可以充分利用一些不可避免的相關(guān)性等待(某些核由于相關(guān)性處在空載)，對這些空載核進(jìn)行再入式分配，可以有效降低遷移代價。

(E)缺乏虛擬化分配

目前的針對OS下的多核調(diào)度，大多數(shù)都是直接進(jìn)行任務(wù)集到核集或者多CPU的映射，中間沒有設(shè)置一層虛擬化核。這樣會使任務(wù)分配與核調(diào)度兩個問題糾纏在一起，缺乏獨立性，增加優(yōu)化解決的復(fù)雜度。另外，任務(wù)內(nèi)負(fù)載的并行特征和資源需求是動態(tài)變化的，而這種直接把任務(wù)集映射到核集的方式，會降低非對稱多核系統(tǒng)的計算效率，這是因為只有當(dāng)多核系統(tǒng)上的處理器核的配置與任務(wù)內(nèi)負(fù)載的并行特征匹配時，才能有效提高非對稱多核系統(tǒng)的計算效率。