劉林東, 覃躍海

(1.廣東第二師范學(xué)院 計(jì)算機(jī)科學(xué)系, 廣東 廣州 510303； 2.華南理工大學(xué) 計(jì)算機(jī)系統(tǒng)研究所，

?

性能異構(gòu)多核處理器調(diào)度策略研究

劉林東1,2, 覃躍海3

(1.廣東第二師范學(xué)院 計(jì)算機(jī)科學(xué)系, 廣東 廣州 510303； 2.華南理工大學(xué) 計(jì)算機(jī)系統(tǒng)研究所，

廣東 廣州 510006；3.廣東第二師范學(xué)院 數(shù)學(xué)系， 廣東 廣州 510303)

多核處理器體系結(jié)構(gòu)越來越多地被應(yīng)用于高性能計(jì)算中，處理器核心的異構(gòu)特性能更好地發(fā)揮多核處理器的性能.基于多核處理器的DHCMP(Dynamic Heterogeneous Chip Multiprocessor)結(jié)構(gòu)，分析性能異構(gòu)多核處理器的體系結(jié)構(gòu)與任務(wù)負(fù)載的并行特性，將基本核組合為邏輯核與并行任務(wù)進(jìn)行映射，在邏輯核調(diào)度中融入分類挖掘的思想，建立一種性能異構(gòu)多核處理器調(diào)度模型和算法.實(shí)驗(yàn)證明，采用文中的調(diào)度策略和算法比同類算法在邏輯核調(diào)度的利用率等方面有明顯的改進(jìn).

多核處理器；性能異構(gòu)；資源調(diào)度；分類挖掘

0　引言

多核處理器[1-2]以核心多、主頻高、功耗低、擴(kuò)展性好等優(yōu)點(diǎn)，成為當(dāng)前主流的微處理器架構(gòu)，被廣泛地應(yīng)用在高性能計(jì)算環(huán)境中.從處理器系統(tǒng)內(nèi)核結(jié)構(gòu)的差異，可以將多核處理器分為同構(gòu)多核處理器和異構(gòu)多核處理器；從編程的角度，可以將異構(gòu)多核處理器分為功能異構(gòu)和性能異構(gòu)兩種，性能異構(gòu)多核處理器[3-4]是指片上集成的各個處理器核支持相同的指令集、主頻、緩存、通信帶寬等參數(shù)不同.

目前大部分多核處理器調(diào)度策略以同構(gòu)多核處理器[5-6]為研究對象，針對異構(gòu)多核處理器的任務(wù)調(diào)度策略相對較少.異構(gòu)多核處理器調(diào)度包括靜態(tài)調(diào)度和動態(tài)調(diào)度兩種策略，靜態(tài)調(diào)度策略[7]大部分基于啟發(fā)式算法、隨機(jī)搜索算法；動態(tài)調(diào)度策略一般基于邏輯核分配的思想，基于異構(gòu)多核處理器的DHCMP結(jié)構(gòu)，在調(diào)度過程中動態(tài)地對基本核進(jìn)行動態(tài)調(diào)整，形成邏輯核，再將邏輯核與負(fù)載任務(wù)進(jìn)行映射，主要的邏輯核調(diào)度算法[7]包括：EQUI、PDPA(Performance Driven Processor Allocation)、PERA(Phase-aware Efficiency-driven Resource Allocation)和EDP(Efficiency-based Dynamic Priority)算法等.

圖1　動態(tài)異構(gòu)多核　　　處理器結(jié)構(gòu)

圖2　邏輯核結(jié)構(gòu)

1　動態(tài)異構(gòu)多核處理器結(jié)構(gòu)

基于動態(tài)異構(gòu)多核處理器[7](DHCMP)結(jié)構(gòu)的芯片是由多個同構(gòu)的、性能相同的“基本核”(Base Core,BC)組成，如圖1所示，每個基本核同構(gòu)且性能相同.由于每個基本核的處理能力較弱，不能獨(dú)立完成任務(wù)的處理要求，因此需要對基本核進(jìn)行擴(kuò)展.

在多核處理器與并行任務(wù)的調(diào)度過程中，借助處理器調(diào)度程序，在并行任務(wù)運(yùn)行的不同階段以及不同的并行任務(wù)間動態(tài)地分配基本核，因此在多核處理器調(diào)度的過程中，可以根據(jù)任務(wù)以及任務(wù)運(yùn)行的需要，將基本核靈活地組合成相應(yīng)粒度的邏輯單元，稱之為“邏輯核”(Logical Core,LC)，如圖2所示，共包括4個邏輯核(L1～L4)，L1的粒度為2，L2的粒度為6，L3和L4的粒度為4.邏輯核由2～n/2(n為基本核的數(shù)量)個基本核組成，邏輯核既可以保證處理能力的增長，也可以減少基本核之間的通信開銷.

2　任務(wù)調(diào)度模型

2.1系統(tǒng)模型

2.2任務(wù)模型

設(shè)并行任務(wù)系統(tǒng)的任務(wù)模型[8]T包含有M個并行任務(wù)，分別為：T0,T1,…,TM-1，每個任務(wù)Ti可以表示為一個三元組(Thread,Cost,Comm)，其中Thread表示任務(wù)的線程數(shù)，Cost表示計(jì)算開銷，Comm表示通信開銷，為了簡單任務(wù)調(diào)度模型，忽略進(jìn)程間的通信開銷，即將任務(wù)模型定義為Ti={Thread,Cost}.

圖3　性能異構(gòu)多核處理器調(diào)度模型

2.3調(diào)度模型

為有效地實(shí)現(xiàn)性能異構(gòu)多核處理器調(diào)度，將分類挖掘的思想融入到性能異構(gòu)多處理器調(diào)度過程中，對邏輯核與并行任務(wù)間的歷史調(diào)度信息進(jìn)行采集、分析和挖掘，得出邏輯核和并行任務(wù)之間的調(diào)度模式，圖3為提出的一種性能異構(gòu)多核處理器調(diào)度模型，在邏輯核集L和并行任務(wù)集T之間采用PHMP算法實(shí)現(xiàn)邏輯核與并行任務(wù)間的映射，得出相應(yīng)的調(diào)度模式，利用調(diào)度模式指導(dǎo)邏輯核與并行任務(wù)之間的映射.

為了便于在邏輯核和并行任務(wù)間進(jìn)行調(diào)度，對邏輯核和并行任務(wù)中的各個參數(shù)進(jìn)行分類劃分.將邏輯核的粒度劃分為3種，用s1,s2,s3分別表示粒度為小(1～Nc/8)、中(Nc/8+1～Nc/4)、大(Nc/4+1～Nc/2)的3種類型邏輯核；按每個任務(wù)的線程數(shù)，將任務(wù)的線程分為t1,t2,t33種，分別表示線程數(shù)小、適中、大；對于每個并行任務(wù)T的計(jì)算開銷，將任務(wù)的開銷分為c1,c22種，其中c1表示任務(wù)的Cost值較小，c2表示任務(wù)的Cost值較大.

在表1中，描述了3個邏輯核(L1,L2,L3)與3個并行任務(wù)(T1,T2,T3)之間的映射關(guān)系，同一個邏輯核的粒度并非完全一致，如編號為2的邏輯核L1與編號為3的邏輯核L1粒度不同，主要是因?yàn)檫壿嫼嗽谡{(diào)度過程中可以動態(tài)的調(diào)整其基本核的粒度；同一個任務(wù)在不同的運(yùn)行階段其線程數(shù)和計(jì)算開銷也不一定相同，如編號為2的任務(wù)T1與編號為3的任務(wù)T1其線程數(shù)和計(jì)算開銷完全不同，表示同一個任務(wù)隨著任務(wù)的運(yùn)行，相應(yīng)的線程數(shù)和計(jì)算開銷可能會有所變化.

表1邏輯核與并行任務(wù)映射表

編號邏輯核粒度線程開銷任務(wù)1L1s1t1c1T12L1s1t1c1T13L1s2t2c2T14L2s2t2c2T25L2s2t3c1T26L2s3t3c1T37L3s3t3c2T38L3s3t3c2T3

3　任務(wù)調(diào)度

3.1調(diào)度策略

性能異構(gòu)多核處理器資源調(diào)度的目標(biāo)是實(shí)現(xiàn)基本核與邏輯核的組合以及邏輯核與并行任務(wù)的映射.在調(diào)度過程中爭取基本核、邏輯核資源利用率的最大化以及并行任務(wù)執(zhí)行時間的最短.

在基本核數(shù)量一定的前提下，將基本核組合成不同粒度的邏輯核，根據(jù)處理器資源調(diào)度的歷史數(shù)據(jù)，利用分類挖掘?qū)φ{(diào)度信息進(jìn)行分析，得出不同任務(wù)調(diào)度邏輯核的調(diào)度模型，基于調(diào)度模式，對于調(diào)度模式中出現(xiàn)的任務(wù)，直接在任務(wù)與邏輯核間建立映射；對于調(diào)度模式中未出現(xiàn)的任務(wù)，從事務(wù)集中選擇一個粒度適中的邏輯核與之匹配.

對表1中的3個邏輯核與3個任務(wù)之間的映射進(jìn)行分類挖掘，根據(jù)改進(jìn)的Apriori算法[9-10]對表1中的事務(wù)集進(jìn)行分類挖掘，設(shè)最小支持度計(jì)數(shù)min_sup=2，得出包含邏輯核和任務(wù)在內(nèi)的頻繁模式集為：{,,}.設(shè)最小置信度min_conf=65%，得出邏輯核和任務(wù)間的分類模式：T1=>L1∧s1∧t1∧c1，T2=>L2∧s2，T3=>L3∧s3∧t3∧c2，根據(jù)邏輯核以及并行任務(wù)的定義，得出相應(yīng)的調(diào)度規(guī)則為：T1=>L1，T2=>L2，T3=>L3，但在3個調(diào)度規(guī)則中，需要滿足粒度、線程數(shù)以及開銷的要求.

3.2調(diào)度算法

基于性能異構(gòu)多核處理器調(diào)度模型，設(shè)計(jì)了一種性能異構(gòu)多核處理器調(diào)度算法(PHMP算法)，算法具體描述如下：

input:Classification_rules_setp[N][M],r[N][M],l[N],s[N],T[M];

Initializer[N][M]=0;

for (j=0;j<=M-1,j++){

for (i=0;i<=N-1;i++){

ifp[i][j]=1 //邏輯核Li與任務(wù)Tj存在映射關(guān)系;

r[i][j]=1; //AssignLitoTj;

else{ //調(diào)度模式中沒被映射的任務(wù);

select three logic coreLk,Lm,LnfromLwherep[k]=0,p[m]=0,p[n]=0 randomly ;

ifs[k]>=s[m] ands[k]<=s[n]{

p[k][j]=1; //將邏輯核Lk與任務(wù)Tj的映射關(guān)系添加到調(diào)度規(guī)則中;

r[k][j]=1; //將邏輯核Lk映射給任務(wù)Tj;

}

else ifs[m]>=s[k] ands[m]<=s[n]{

p[m][j]=1; //將邏輯核Lm與任務(wù)Tj的映射關(guān)系添加到調(diào)度規(guī)則中;

r[m][j]=1; //將邏輯核Lm映射給任務(wù)Tj;

}

else{

p[n][j]=1; //將邏輯核Ln與任務(wù)Tj的映射關(guān)系添加到調(diào)度規(guī)則中;

r[n][j]=1; //將邏輯核Ln映射給任務(wù)Tj;

}

}

updater[N][M];

}

}

output:r[N][M];

在PHMP算法中，將分類挖掘產(chǎn)生的處理器調(diào)度規(guī)則p[N][M](p[i][j]=1表示調(diào)度規(guī)則中邏輯核Li與任務(wù)Tj存在映射關(guān)系，否則不存在映射關(guān)系)、邏輯核l[N]及其粒度s[N]和任務(wù)T[M]作為輸入條件，在調(diào)度規(guī)則中如果存在有未被映射的任務(wù)，從未被映射的邏輯核中隨機(jī)選擇3個邏輯核，選擇粒度為中間值的邏輯核與任務(wù)建立映射，對r[i][j]的值進(jìn)行更新(r[i][j]=1表示邏輯核Li和任務(wù)Tj存在映射關(guān)系，r[i][j]=0表示邏輯核Li和任務(wù)Tj不存在映射關(guān)系)，并將相應(yīng)的映射關(guān)系加入到調(diào)度規(guī)則p[i][j]中，最后輸出邏輯核與任務(wù)之間的調(diào)度關(guān)系集r[N][M].

4　實(shí)驗(yàn)與分析

利用GridSim仿真器對PHMP算法進(jìn)行仿真實(shí)驗(yàn)，設(shè)DHCMP結(jié)構(gòu)中包括32個基本核，初始化為5個邏輯核，分別為2個2粒度的邏輯核、1個4粒度的邏輯核、1個8粒度的邏輯核和1個16粒度的邏輯核，5個不同開銷的并行任務(wù)，共進(jìn)行10次實(shí)驗(yàn)，通過實(shí)驗(yàn)得出PHMP算法對邏輯核進(jìn)行調(diào)度時的資源利用率，對比其它兩種邏輯核調(diào)度算法(EQUI、PERA)，得到如圖4所示的邏輯核利用率對比圖.圖5中對比了3種不同數(shù)量(32,64,128)的基本核利用PHMP算法調(diào)度邏輯核的利用率.

從圖4中可以得出，通過多次實(shí)驗(yàn)得出，采用PHMP算法對邏輯核進(jìn)行調(diào)度時，邏輯核的利用率總體上是優(yōu)于EQUI、PERA兩種調(diào)度算法，能提高3%～5%的利用率，提高了邏輯核的利用率和并行系統(tǒng)的性能；從圖5的數(shù)據(jù)可以得出，采用PHMP算法對3種不同數(shù)量的基本核進(jìn)行調(diào)度，基本核數(shù)量越大，邏輯核的利用率越高，可以理解為基本核的數(shù)量越大，組合為邏輯核的類型越多，邏輯核組合更靈活.

5　結(jié)束語

文中基于動態(tài)異構(gòu)多核處理器結(jié)構(gòu)，將基本核組合成不同粒度的邏輯核，將分類挖掘思想應(yīng)用到邏輯核的調(diào)度，根據(jù)邏輯核與任務(wù)之間的歷史調(diào)度信息，產(chǎn)生相應(yīng)的調(diào)度規(guī)則，并通過PHMP算法對邏輯核和任務(wù)進(jìn)行調(diào)度，實(shí)現(xiàn)性能異構(gòu)多核處理器調(diào)度.對比其他邏輯核調(diào)度算，PHMP算法對提高資源利用率以及系統(tǒng)性能具有較明顯的優(yōu)勢.

性能異構(gòu)處理器模型中，性能異構(gòu)的處理器是由不同粒度的基本核組成的，在實(shí)際調(diào)度過程中需要將基本核間以及邏輯核間的通信開銷考慮進(jìn)去；另外，在PHMP調(diào)度算法中，對于未被映射的任務(wù)與邏輯核的映射，在后續(xù)的研究中可以對比多種調(diào)度策略，進(jìn)一步優(yōu)化調(diào)度效率.

[1] WAN Zhi-tao. A network virtualization approach in many-core processor based cloud computing environment[C]. Third International Conference on Computational Intelligence,2011:304-307.

[2] BORKAR S,CHIEN A A.The future of microprocessors.Communications of the ACM,2011,54(5):67-77.

[3] 王川.異構(gòu)多核系統(tǒng)混合任務(wù)調(diào)度算法[J].微電子學(xué)與計(jì)算機(jī),2013,30(6):61-62.

[4] 金勝男.基于異構(gòu)多核的靜態(tài)任務(wù)調(diào)度策略研究[D].哈爾濱:哈爾濱工程大學(xué),2012:12.

[5] LIU Yi,ZHANG Xin,LI He,et al.Allocating tasks in multi-core processor based parallel system[C].Proceedings of the 2007 IFIP International Conference on Network and Parallel Computing Workshop,2007:748-753.

[6] LEE Jinho,CHUNG Moo-Kyoung,CHO Yeon-Gon,et al. Mapping and scheduling of tasks and communications on many-core SoC under local memory constraint[J].IEEE Transactions on Computer-aided Design of Intergraded Circuits and Systems,2013,32(11):1748-1761.

[7] 孫濤.面向動態(tài)異構(gòu)眾核處理器的任務(wù)調(diào)度研究[D].合肥:中國科技大學(xué),2013:2.

[8] CHEN Quan,CHEN Ya-wen,HUANG Zhi-yi,et al.WATS:Workload-Aware Task Scheduling in asymmetric multi-core architectures[C].26th International Parallel and Distributed Processing Symposium,2012:249-260.

[9] YE Y,CHIANG C.A parallel Apriori algorithm for frequent itemset mining[C].Proc Forth Int Conf Software Engineering Research,Management and Applications,2006:8794.

[10]LIULin-dong,CHENHong-bin.Analgorithmofdynamicresourceallocationingridenvironment[J].ACTAScientiarumNaturalismUniversitiesSUNYATSENI,2013,52(2):47-51.

Efficient Scheduling Mechanism for Performance-heterogeneous Multicore Processor

LIU Lin-dong1,2, QIN Yue-hai3

(1.Department of Computer Science, Guangdong University of Education, Guangzhou, Guangdong, 510303,P.R.China; 2. Research Institute of Computer Systems, South China University of Technology, Guangzhou, Guangdong, 510006, P.R.China; 3.Department of Mathematics, Guangdong University of Education, Guangzhou, Guangdong, 510303, P.R.China)

Multicore processor architectures are increasingly being used in high-performance computing environment because heterogeneous characteristics of the processor cores can play an important role in the performance of multicore processors. In the paper, we analyze the architecture and tasks’ parallel features of performance-heterogeneous multicore processor based on DHCMP (Dynamic Heterogeneous Chip Multiprocessor). By grouping all of the basic cores into several logic cores, establishing a mapping rule from basic cores to logic cores, and applying classification data mining to scheduling process of logic cores, we establish a performance-heterogeneous multicore processor scheduling model and algorithms. Experiments show that the scheduling strategies and algorithms in this paper can improve the utilization of logic cores than other algorithms.

multicore processor; performance-heterogeneous; resource scheduling; classification data mining

2016-03-12

廣東省2013年高等教育教學(xué)改革項(xiàng)目

劉林東，男，湖南邵陽人，廣東第二師范學(xué)院計(jì)算機(jī)科學(xué)系副教授．

TP391.9

A

2095-3798(2016)05-0086-06