性能異構多核處理器調度策略研究

劉林東, 覃躍海

(1.廣東第二師范學院 計算機科學系, 廣東 廣州 510303； 2.華南理工大學 計算機系統研究所，

?

性能異構多核處理器調度策略研究

劉林東1,2, 覃躍海3

(1.廣東第二師范學院 計算機科學系, 廣東 廣州 510303； 2.華南理工大學 計算機系統研究所，

廣東 廣州 510006；3.廣東第二師范學院 數學系， 廣東 廣州 510303)

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

多核處理器；性能異構；資源調度；分類挖掘

0　引言

多核處理器[1-2]以核心多、主頻高、功耗低、擴展性好等優點，成為當前主流的微處理器架構，被廣泛地應用在高性能計算環境中.從處理器系統內核結構的差異，可以將多核處理器分為同構多核處理器和異構多核處理器；從編程的角度，可以將異構多核處理器分為功能異構和性能異構兩種，性能異構多核處理器[3-4]是指片上集成的各個處理器核支持相同的指令集、主頻、緩存、通信帶寬等參數不同.

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

圖1　動態異構多核　　　處理器結構

圖2　邏輯核結構

1　動態異構多核處理器結構

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

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

2　任務調度模型

2.1系統模型

2.2任務模型

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

圖3　性能異構多核處理器調度模型

2.3調度模型

為有效地實現性能異構多核處理器調度，將分類挖掘的思想融入到性能異構多處理器調度過程中，對邏輯核與并行任務間的歷史調度信息進行采集、分析和挖掘，得出邏輯核和并行任務之間的調度模式，圖3為提出的一種性能異構多核處理器調度模型，在邏輯核集L和并行任務集T之間采用PHMP算法實現邏輯核與并行任務間的映射，得出相應的調度模式，利用調度模式指導邏輯核與并行任務之間的映射.

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

在表1中，描述了3個邏輯核(L1,L2,L3)與3個并行任務(T1,T2,T3)之間的映射關系，同一個邏輯核的粒度并非完全一致，如編號為2的邏輯核L1與編號為3的邏輯核L1粒度不同，主要是因為邏輯核在調度過程中可以動態的調整其基本核的粒度；同一個任務在不同的運行階段其線程數和計算開銷也不一定相同，如編號為2的任務T1與編號為3的任務T1其線程數和計算開銷完全不同，表示同一個任務隨著任務的運行，相應的線程數和計算開銷可能會有所變化.

表1邏輯核與并行任務映射表

編號邏輯核粒度線程開銷任務1L1s1t1c1T12L1s1t1c1T13L1s2t2c2T14L2s2t2c2T25L2s2t3c1T26L2s3t3c1T37L3s3t3c2T38L3s3t3c2T3

3　任務調度

3.1調度策略

性能異構多核處理器資源調度的目標是實現基本核與邏輯核的組合以及邏輯核與并行任務的映射.在調度過程中爭取基本核、邏輯核資源利用率的最大化以及并行任務執行時間的最短.

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

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

3.2調度算法

基于性能異構多核處理器調度模型，設計了一種性能異構多核處理器調度算法(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與任務Tj存在映射關系;

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

else{ //調度模式中沒被映射的任務;

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與任務Tj的映射關系添加到調度規則中;

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

}

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

p[m][j]=1; //將邏輯核Lm與任務Tj的映射關系添加到調度規則中;

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

}

else{

p[n][j]=1; //將邏輯核Ln與任務Tj的映射關系添加到調度規則中;

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

}

}

updater[N][M];

}

}

output:r[N][M];

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

4　實驗與分析

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

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

5　結束語

文中基于動態異構多核處理器結構，將基本核組合成不同粒度的邏輯核，將分類挖掘思想應用到邏輯核的調度，根據邏輯核與任務之間的歷史調度信息，產生相應的調度規則，并通過PHMP算法對邏輯核和任務進行調度，實現性能異構多核處理器調度.對比其他邏輯核調度算，PHMP算法對提高資源利用率以及系統性能具有較明顯的優勢.

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

[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] 王川.異構多核系統混合任務調度算法[J].微電子學與計算機,2013,30(6):61-62.

[4] 金勝男.基于異構多核的靜態任務調度策略研究[D].哈爾濱:哈爾濱工程大學,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] 孫濤.面向動態異構眾核處理器的任務調度研究[D].合肥:中國科技大學,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年高等教育教學改革項目

劉林東，男，湖南邵陽人，廣東第二師范學院計算機科學系副教授．

TP391.9

A

2095-3798(2016)05-0086-06