性能异构多核处理器调度策略研究

刘林东, 覃跃海

(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