一種多核處理器調(diào)度策略研究

一種多核處理器調(diào)度策略研究

0多核處理器隨著半夏技術(shù)的進(jìn)步，以多核處理器為代表的體系結(jié)構(gòu)逐漸取代了單個處理器，提高了處理器的性能。目前關(guān)于多核處理器調(diào)度的策略1基于均衡種群遺傳算法的多核處理器設(shè)計(jì)多核處理器調(diào)度策略問題,目前主要針對處理器體系結(jié)構(gòu)、靜態(tài)處理器調(diào)度、能耗處理器調(diào)度、處理器資源利用率、負(fù)載均衡等問題進(jìn)行研究,同構(gòu)多核處理器調(diào)度的相關(guān)研究文獻(xiàn)如下.文獻(xiàn)[4]針對同構(gòu)多核處理器系統(tǒng)的特點(diǎn),利用靜態(tài)資源調(diào)度策略對多核處理器進(jìn)行調(diào)度,建立一種處理器任務(wù)分配及調(diào)度模型,提出了一種均衡種群遺傳算法(BPGA),提高了處理器均衡負(fù)載度以及效率.文獻(xiàn)[5-6]分析了傳統(tǒng)大規(guī)模并行系統(tǒng)環(huán)境下的多核處理器部署主要通過增加核心或處理器來提高性能,提出了一種任務(wù)分配的啟發(fā)式算法,該算法隨著線程數(shù)的增加,其效率要比一般的遺傳算法更優(yōu).文獻(xiàn)[7]根據(jù)多核處理器的特點(diǎn),先將任務(wù)分配到合適的處理器,然后將任務(wù)調(diào)度到處理器中某個內(nèi)核執(zhí)行.在對任務(wù)進(jìn)行分配調(diào)度的過程中,設(shè)計(jì)一個優(yōu)化的任務(wù)分配模型,在模型中加入了基于復(fù)制的任務(wù)調(diào)度的思想,最后采用遺傳算法對各個處理器上的任務(wù)進(jìn)行調(diào)度.文獻(xiàn)[8]針對同構(gòu)多核處理器設(shè)計(jì)了一個基于動態(tài)電壓調(diào)節(jié)的節(jié)能調(diào)度方法.首先將計(jì)算任務(wù)按照周期數(shù)降序排序并基于計(jì)算任務(wù)調(diào)度長度最短的原則安排任務(wù)映射,然后將各個處理核上具有最小通訊時間的計(jì)算任務(wù)設(shè)置為最后執(zhí)行的計(jì)算任務(wù)而其他計(jì)算任務(wù)順序保持不變,方法能有效地降低多核處理器的能量.2多核處理器的準(zhǔn)備2.1多核處理器環(huán)境下并行調(diào)度系統(tǒng)模型多核處理器調(diào)度一般分為全局調(diào)度和局部調(diào)度,調(diào)度策略主要包括:映射、核上調(diào)度以及核間遷移等.映射的主要任務(wù)是在處理器與任務(wù)之間建立某種關(guān)系.多核處理器環(huán)境下的并行調(diào)度系統(tǒng)一般由系統(tǒng)模型、調(diào)度模型和任務(wù)模型3部分構(gòu)成,如圖1所示.系統(tǒng)模型是指多核處理器物理特性的抽象集,任務(wù)模型是等待調(diào)度任務(wù)的形式化表示,調(diào)度模型是在系統(tǒng)模型和任務(wù)模型間,采用某種調(diào)度策略,將處理器資源合理地分配到相應(yīng)的調(diào)度任務(wù)上,并給出最終的調(diào)度結(jié)果.2.2多核處理器調(diào)度問題描述在傳統(tǒng)的多核處理器調(diào)度策略中,容易出現(xiàn)并行系統(tǒng)計(jì)算性能低、多核處理器資源利用率低、任務(wù)調(diào)度時間過長、負(fù)載不均衡、處理器能耗大、產(chǎn)生處理器資源調(diào)度的碎片等問題.圖2描述了多核處理器調(diào)度所出現(xiàn)的問題,其中R3調(diào)度模型和算法3.1配置模型3.1.1系統(tǒng)模型設(shè)一個多核處理器并行系統(tǒng)3.1.2勞動模型系統(tǒng)中等待被調(diào)度的有M個進(jìn)程P={P3.1.3多核處理器資源調(diào)度模型基于多核處理器調(diào)度中所出現(xiàn)的問題,為有效地實(shí)現(xiàn)并行系統(tǒng)的多核處理器資源調(diào)度,將分類挖掘的思想融入到處理器資源調(diào)度中,給出一種多核處理器資源調(diào)度模型,如圖3所示.在調(diào)度模塊中利用CMMPS(Multi-CoreProcessorSchedulingBasedonClassificationDataMining)算法實(shí)現(xiàn)處理器資源的調(diào)度,為有效地在R為便于實(shí)現(xiàn),對系統(tǒng)模型的定義進(jìn)行簡化.設(shè)處理器的核心數(shù)為2,4,8,分別用c表1列出了8個多核處理器{R3.2cmmps算法中控制器的描述基于多核處理器調(diào)度模型,設(shè)計(jì)了一種多核處理器與進(jìn)程間的調(diào)度算法(CMMPS算法),算法具體描述如下:在CMMPS算法中,分別將產(chǎn)生的調(diào)度規(guī)則、處理器和進(jìn)程集合c[N][M],R,P作為輸入條件,在調(diào)度規(guī)則中如果存在有未被調(diào)用的處理器或進(jìn)程,則將處理器或進(jìn)程中的內(nèi)核和線程平均地分配給相應(yīng)的進(jìn)程和處理器,并對r[N][M]的值進(jìn)行修改(r[i][j]=1表示處理器R4實(shí)驗(yàn)結(jié)果與分析利用GridSim仿真環(huán)境創(chuàng)建處理器、進(jìn)程任務(wù)對CMMPS算法進(jìn)行仿真實(shí)驗(yàn).創(chuàng)建20個處理器單元和8個進(jìn)程單元(如表2所示),在進(jìn)程單元保持不變的前提下,共進(jìn)行10次實(shí)驗(yàn),每次實(shí)驗(yàn)均對處理器的內(nèi)核數(shù)、主頻以及緩存進(jìn)行隨機(jī)調(diào)整,通過實(shí)驗(yàn)得出CMMPS算法在對處理器資源進(jìn)行調(diào)度時的資源利用率,對比其他兩種處理器資源調(diào)度算法(Min-min、Max-min),得到如圖4所示的處理器資源利用率對比圖.從圖4可知,通過多次實(shí)驗(yàn)得出,采用CMMPS算法對多核處理器資源進(jìn)行調(diào)度時,任務(wù)的執(zhí)行時間總體上是少于Min-min、Max-min兩種調(diào)度算法,能縮短10%~20%的執(zhí)行時間,提高了多核處理器資源的利用率和并行系統(tǒng)的性能,達(dá)到了改進(jìn)算法性能的目的.5資源調(diào)度算法文中將分類挖掘思想融入到多核處理器資源調(diào)度中,根據(jù)多核處理器與進(jìn)程任務(wù)之間的歷史調(diào)度信息,產(chǎn)生相應(yīng)的分類規(guī)則和調(diào)度規(guī)則,通過CMMPS算法對多核處理器資源和進(jìn)程進(jìn)行調(diào)度,對比其他多核處理器資源調(diào)度算,CMMPS算法對提高資源利用率以及系統(tǒng)性能具有較明顯的性能優(yōu)勢.文中的系統(tǒng)模型中,不同的處理器是異構(gòu)的,但在同一個處理器內(nèi)部,不同的核心