面向高通量应用的众核处理器任务调度
徐远超 1,2 , 杨璐 1     
1. 首都师范大学 信息工程学院, 北京 100048;
2. 中国科学院 计算技术研究所, 计算机体系结构国家重点实验室, 北京 100190
摘要:具有高通量特征的大数据应用已成为目前数据中心的主流应用,这些应用在传统处理器平台上的运行效率不高,原因之一是任务调度的低效。针对高通量应用的一些典型特征以及现有任务窃取算法的不足,该文提出一种程序行为和环境感知的任务调度机制,通过软硬件结合实现了处理器核的分区管理和任务的分级调度,减小了不同应用之间因争用共享资源对性能产生的不利影响,同时利用线程相似度高的特点提高指令缓存的命中率,从而提升系统的整体吞吐率。初步的模拟评估表明:该算法在混合负载情况下性能明显优于现有算法的,在测试的混合负载中平均优于现有算法20%。
关键词众核处理器    大数据应用    高通量    任务调度    
Task scheduling on a many-core processor for high-volume throughput applications
XU Yuanchao1,2, YANG Lu1     
1. College of Information Engineering, Capital Normal University, Beijing 100048, China;
2. State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
Abstract: Big data applications with high-volume throughputs have become the most common applications in datacenters. The efficiencies of these applications running on traditional processors are very low for various reasons, one of which is the low-efficiency task scheduling. This paper presents a task scheduling framework that identifies program behavior and the running environment and then partitions the cores with hierarchical task scheduling though hardware and software co-design to reduce the negative effect of shared resource contention and improving the instruction cache hit rate using thread similarity. Tests show this algorithm improves performance by 20% on average over the legacy work-stealing scheduling algorithm.
Key words: many-core processor     big data applications     high-volume throughput     task scheduling    

通过对大数据[1]进行深度分析,可以获取有价值的信息,如事物发展趋势,然而,大数据分析对计算机系统提出了更高的要求。分析发现,在面向社交网络、搜索引擎和网络流媒体等网络大数据应用时,传统的众核/多核处理器能效低下,原因是现有处理器体系结构与新型大数据应用的特征需求不匹配,使得片上资源利用率明显不足。与高性能应用不同,大数据应用表现为线程级并行度高、线程之间耦合度低、并发用户数量大,学术界将其称之为高通量特征[2]。例如微博、Twitter等社交网站,用户众多且相互交织,组成复杂的图关系,一次简单的互动可能引发底层硬件在非常大的地址空间中访问非规则的离散数据。设计面向具有高通量特征大数据应用的处理器体系结构成为学术界的共识。

国际半导体技术发展路线图[3]指出,芯片内可集成的晶体管数目仍符合指数趋势增长。在技术限制和功耗约束的情况下,片上众核/多核处理器是一个切实可行的发展方向。众核处理器片内集成多个简单处理器核,具有强大的线程级并行处理能力,可以同时响应成千上万的高并发用户请求,非常适合高通量大数据应用的高吞吐需求。众核处理器虽然带宽、存储和计算资源丰富,但是如果任务调度不合理,将造成网络负载和计算负载不均衡,继而出现局部网络拥塞、共享资源争用加剧,而其他部分却出现资源闲置的现象,与按需资源分配的理念背道而驰。多任务环境下共享资源争用有2种原因:一是共享资源本身不足,二是程序行为相似,例如同为访存密集型程序或两个程序恰好同时访存,会造成共享缓存和访存带宽的争用。

众核任务调度由运行时系统 (runtime system) 来完成。运行时系统是轻量级操作系统,主要功能是给编程模型提供支持,此外还负责任务调度及资源管理等。任务调度是将细粒度线程映射到底层硬件资源上高效执行。运行时系统的任务调度策略与并行编程模型密切相关,例如OpenMP编程模型同时支持静态、动态和有指导的调度算法[4],Cilk和TBB为支持深度优先任务窃取调度算法[5-6],X10支持广度优先任务窃取和混合调度策略等[7]。众核任务调度算法需要解决的另一个问题是算法的扩展能力以及对异构的支持。异构具有很好的加速作用和执行效能,但也增加了编程和调度的复杂性,因为资源和指令集的异构使得运行时系统需要进行更多的分析和判断,Harmony[8]、StarPU[9]、Helios[10]和Barrelfish[11]是异构众核运行时系统或操作系统的典型代表。Barrelfish[11]和Fos[12]基于消息来进行核间或组件之间通信以及全局一致性维护。Corey[13]和Akaros[14]让用户显式控制核间共享和维护一致性,无疑增加了用户编程的复杂度。资源的争用也是一个突出的问题,为了减少资源竞争,可以通过虚拟机技术将处理器核划分为多个不同的资源集合,使应用程序运行在不同的虚拟机中[15],通过任务簇的拆分与合并,动态构建可弹性伸缩的核逻辑分组,实现核资源的隔离[16]以及避免内核级线程与用户级线程之间的干扰问题[17]。但资源隔离是一种粗粒度的冲突避免方式,为了提高资源的利用率,需要对资源细粒度精细化动态管理。现有的任务窃取算法在选择任务时具有一定的盲目性,可能加剧共享资源争用。

针对以上问题,本文提出了程序行为和运行环境感知的众核处理器任务调度算法,通过分析大数据应用负载时刻变化的资源需求特征,建立动态灵活、高效的自适应调度机制。在分配线程时考虑了片上网络的负载状况,避免局部网络拥塞,同时能做到将相似的线程分配到同一个处理器核上避免线程之间的数据干扰,同时提高了指令缓存的利用率。

1 程序行为和环境感知的众核任务调度算法

众核处理器结构目前普遍采用的是一种基于随机性的任务窃取算法,选择任务时不评估被选任务对运行在现有处理器核上其他任务的影响,因此可能造成缓存资源、访存带宽及片上网络的争用,影响片上资源的利用率。为此,需要实现程序感知和环境感知的任务调度机制 (见图 1) 即同时知晓程序的属性和环境特征,以做出更加智能的调度决策,减少资源争用。

图 1 程序感知与环境感知的任务调度机制

1.1 分区管理

在高通量应用中,数据的共享读写程度低,全局的一致性和节点间的高带宽互连对性能提升不大,因而可以将片内资源分成多个区域进行管理,只维护局部一致性。例如900核的众核处理器分成30个区域,每个区域有30个处理器核,分区后需要维护数据一致性的处理器核规模比分区前下降了一个数量级,如果线程调度器能做到将有数据同步的多个线程安排到一个分区上,不仅扩展性好,而且不影响程序性能,同时,传统的基于目录的缓存一致性协议仍然可用,也可以考虑基于程序员显式编程的便签式存储器 (scratchpad memory)。基于以上分析,设计了双环拓扑的高通量众核结构,如图 2所示,分为大环和子环 (R表示路由器)。

图 2 环状拓扑的高通量众核结构

1.2 程序行为分析

多任务环境下共享资源争用的主要原因是程序行为的相似,例如2个同为访存密集型的程序同时访存,会造成共享缓存和访存带宽的争用。通过程序行为分析及合理调度,错开访存请求或将程序行为互补的多个线程安排在共享缓存的处理器核上,可以有效缓解这一现象。但现有的众核任务调度算法是一种随机的任务窃取算法,不保证共享数据的任务恰好运行在线程核组 (thread core group,TCG) 上,要做到这一点就要求运行时系统识别应用的类型甚至行为。识别程序的类别或行为有3种方法:一是由程序员通过编程模型直接在程序中标识;二是通过编译器静态识别;三是在程序运行过程中动态识别。编译器识别会大大增加编译程序的复杂度,动态识别将影响调度效率。因此,本文采取动静结合的方式,通过给程序员提供必要的编程指导,由程序员标识程序或程序段的类别。由于程序员对自己编写的程序最为了解,因此标识的信息最为准确。

程序的行为特征包括微体系结构相关特征和微体系结构无关特征。微体系结构相关特征包括每个时钟周期执行的指令数 (instructions per cycle,IPC)、缓存失效率、分支误测率、旁路转换缓冲 (translation lookaside buffer,TLB) 失效率等,一般通过硬件性能计数器在线测量。微体系结构无关特征包括混合指令分布、指令集并行度、工作集大小、数据流步长和分支预测度等,一般通过离线测量。在线测量的信息是实时的,但调度是针对未执行的代码,因此需要提前进行预测。预测的效率和准确度是其中的重要挑战,需要在准确度和效率之间进行权衡。在线预测的另一个缺点是在程序执行结束以前,无法预知程序的整个视图,只能看到局部;而离线分析在程序运行之前进行,可以看到整个视图,但离线分析与输入相关。因此本文将在线分析与离线分析结合起来,对数据中心运行的一些常见程序进行离线分析 (见图 3),确定其中的程序段 (program phase) 数量,在线分析只针对单个的程序段进行分析,明确其对片上资源的需求,同一个程序中的相同程序段不再进行重复分析,从而可以大大提高预测准确度。

图 3 程序段离线分析流程

1.3 降低分析开销

程序行为分析如果开销过大,不但提高不了调度性能,反而给程序性能的提升带来负面影响。本文采取多种办法减小开销:一是通过硬件支持缓解纯软件分析的不足;二是通过采样方法减少分析的代码量;三是结合大数据应用的特征如线程之间代码相似度高的特点,避免重复分析。

1.4 运行环境感知

任务的分配不均将导致片上网络的局部拥塞和共享资源的争用。解决这一问题的技术路线是监控网络负载和计算负载的实时状况,并将这些信息传给任务分配器 (task dispatcher) 作为任务调度的决策依据。众核处理器中核的数量多,可以拿出部分处理器核专门负责某一类任务如监控处理器核的运行状态、片上网络的负载状况,并实时反馈给主任务分配器 (main task dispatcher)。运行时系统通过主任务分配器分配任务时,要考虑这些运行时数据,同时结合整个片上资源的分布状况、网络拓扑,做出合理的任务分配,还可以考虑能效感知调度,即用户量不是很大时,可以将部分分区关闭,以节省能耗,避免任务过度集中导致局部过热影响芯片稳定性。

1.5 异构环境支持

高通量众核处理器主要面向高通量应用,但从微观上来讲,同一个应用的多个线程或同一个线程的不同程序段之间仍存在资源的不对称需求,即计算与访存所占比例不完全相同,因此可以考虑将众核处理器设计成不对称结构,如图 4所示,除高通量应用偏好的小核 (small core) 外,适当安排一些性能较高的大核 (big core)。使用大核加速以计算为主的关键路径 (critical path) 代码或计算密集型线程,降低它们对整个任务执行进度的影响。针对高通量应用中子线程随着用户请求动态创建的特点,可以将应用程序的主线程运行在大核上,动态创建的子线程分发到小核上。为此,运行时系统要能够正确预测即将执行的代码是以访存为主还是以计算为主,其次还要知道不同类型处理器核的分布、数量以及动态负载。

图 4 异构众核设计

1.6 分级任务调度

众核中线程数量和处理器核规模大、核间通信和同步速度快,必须降低线程管理的开销。在处理器核分区管理基础上,设计两级任务管理机制,如图 5所示,主任务分发器针对传统的粗粒度多线程程序,子任务分发器针对细粒度多线程程序。主任务分发器位于请求收集结构中,将整个芯片收到的请求整理成为任务,并将任务分派给子任务分发器 (subtask dispatcher)。主任务分发器负责整个芯片任务的负载均衡,确保所有子环的计算负载和片上网络负载基本一致,还需要尽可能把相似的任务分发到同一个子环,这样有助于任务共享指令缓存。主任务分发器设计为“push”分发方式,即实时监测每个子环的计算负载和网络负载,然后将任务分发给负载最轻的子环子任务分发器。子任务分发器位于每个子环的主节点上,仍然设计为集中式的work-stealing调度算法,即在每个小核上执行的软件线程数低于硬件线程数时,向子任务分发器发出请求。子任务分发器还支持任务优先级机制来处理实时性要求较高的高通量应用,给用户更好的实时性体验。

图 5 两级任务分发

利用程序行为感知,将相似的任务分发到同一个子环,有助于提高指令缓存利用率,减少片上网络流量。利用环境感知来实时监测每个子环的计算负载和网络负载,然后将任务分发给负载最轻的子环。子任务分发器实现细粒度管理,通过程序行为分析,错开访存请求或将程序行为互补的多个线程安排在共享缓存的处理器核上。最终实现运行时程序行为和运行环境感知的任务调度机制,以有效平衡网络负载和计算负载,提高片上资源利用率。

2 模拟评估 2.1 模拟环境和测试程序

中国科学院计算技术研究所正在研制面向大数据应用的高通量众核处理器,已经开发完成了一个模块化的千核万线程众核模拟平台SimICT[18],可以方便地修改设计结构、统计关键运行数据,为目标硬件系统结构设计提供详细的数据支持和评估依据。本文模拟了图 2的双环网络结构,重点是片上网络、缓存、访存方式控制、任务分发控制等功能模块,整个众核处理器初步设计为20个子环,每个子环20个处理器核。

学术界对数据中心典型应用程序的各种行为特点和特征分析基本形成共识,虽然分类方法不一样,但包含的程序基本一致。高通量应用程序虽然特征明显,但实际上还可以进一步细分,使得在设计处理器时难以统一,或者放弃一些非共有特征的体系结构支持,或者针对细分类型进行专门设计。参照文[2]和[19],本文选择了部分大数据应用程序 (见表 1)。

表 1 测试程序
程序名称 描述 类别
Search 搜索引擎 搜索服务类程序
Wordcount 单词计数 数据处理应用
Terasort 数据排序 数据处理应用
Memcached 内存缓存系统 数据处理应用
RNC 无线网络控制程序 实时类交互式应用

2.2 模拟结果分析

Cilk运行时系统使用的是传统任务窃取算法,使用该算法与本文提出的应用感知推拉算法进行对比分析。

1) 单一负载时的性能比较。

使用表 1中的测试程序进行逐一测试,实验结果如图 6所示。可以看出,2种算法的性能差异并不明显,原因在于高通量应用程序的行为单一,除Terasort外,其他应用线程之间的数据共享几乎没有,线程之间接近没有数据通信和同步操作,因此此时分区隔离的作用并不明显。

图 6 单一负载时的性能比较

2) 混合负载时的性能比较。

众核处理器拥有上千个处理器核,数据中心为了降低运行成本,往往在一个众核处理器上同时运行多个应用程序。为了2种算法在混合负载下的性能差异,对5个负载进行了几种组合测试,实验结果如图 7所示。可以看出,应用感知推拉算法表现出较大的优势,原因在于:通过程序感知将不同的应用程序推到不同的分区上,避免了应用程序之间的相互干扰,也减少了Terasort、Wordcount应用之间跨分区的线程间通信,同时提高了指令缓存的利用率。

图 7 混合负载时的性能比较

3) 程序行为分析开销。

程序行为分析和运行环境监测是硬件完成的,任务分发器周期性读取相关寄存器信息,开销可忽略不计。本文的分区是通过结构设计实现的,不同于传统意义上通过软件实现的分区管理方式[16]。很多高通量应用的线程是根据用户的请求动态创建的,无法提前预知线程数量,因此无法实现静态分区。

3 结论

任务调度是将任务映射到底层硬件上执行,映射的质量直接影响系统的执行效能。众核处理器可以有多达成百上千个处理器核,具有复杂的片上网络和异构环境,因此良好的扩展性是任务调度算法的基本要求。针对大数据应用的高通量特征,本文提出了一种程序行为和环境感知的调度机制,通过软硬件结合实现了处理器核的分区管理和任务的分级调度机制,减小不同应用之间因争用共享资源对性能产生的不利影响,利用线程相似度高的特点提高指令缓存的命中率,提升了系统的整体吞吐率。将相似线程聚合到同一个分区,由于行为相似,难免引入更大的竞争,但聚合在一个分区可以减少线程之间的通信和同步效率以及提高指令缓存的利用率,这是一个需要权衡的问题。

参考文献
[1] 王元卓, 靳小龙, 程学旗. 网络大数据:现状与展望[J]. 计算机学报, 2013, 36(6): 1–15. WANG Yuanzhuo, JIN Xiaolong, CHENG Xueqi. Network big data:Present and future[J]. Chinese Journal of Computers, 2013, 36(6): 1–15. (in Chinese)
[2] 詹剑锋, 王磊, 孙凝晖. 高通量计算机的性能评价[J]. 中国计算机学会通讯, 2011, 7(7): 40–43. ZHAN Jianfeng, WANG Lei, SUN Ninghui. Performance evaluation of high-volume throughput computer[J]. Communication of CCF, 2011, 7(7): 40–43. (in Chinese)
[3] Allan A, Edenfeld D, Joyner W H, et al. 2001 technology roadmap for semiconductors[J]. Computer, 2002, 35(1): 42–53.
[4] Broquedis F, Diakhaté F, Thibault S, et al. Scheduling dynamic OpenMP applications over multicore architectures[C]//Proc of the International Workshop on OpenMP. Berlin, Germany:Springer, 2008:170-180.
[5] Frigo M, Leiserson C E, Randall K H. The implementation of the Cilk-5 multithreaded language[C]//ACM Sigplan Notices. Montreal, Quebec, Canada:ACM, 1998:212-223.
[6] Blumofe R D, Leiserson C E. Scheduling multithreaded computations by work stealing[C]//Proc 35th Annual Symposium on Foundations of Computer Science. New York, NY, USA:IEEE, 1994:356-368.
[7] Ebrahimi E, Lee C J, Mutlu O, et al. Fairness via source throttling:A configurable and high-performance fairness substrate for multi-core memory systems[C]//ACM Sigplan Notices. Pittsburgh, PA, USA:ACM, 2010, 45(3):335-346.
[8] Diamos G F, Yalamanchili S. Harmony:An execution model and runtime for heterogeneous many core systems[C]//Proc 17th International Symposium on High Performance Distributed Computing. Boston, MA, USA:ACM, 2008:197-200.
[9] Augonnet C, Thibault S, Namyst R, et al. StarPU:A unified platform for task scheduling on heterogeneous multicore architectures[C]//Proc of the European Conference on Parallel Processing. Berlin, Germany:Springer, 2009:863-874.
[10] Nightingale E B, Hodson O, McIlroy R, et al. Helios:Heterogeneous multiprocessing with satellite kernels[C]//Proc 22nd ACM SIGOPS Symposium on Operating Systems Principles. Big Sky, MT, USA:ACM, 2009:221-234.
[11] Baumann A, Barham P, Dagand P E, et al. The multikernel:A new OS architecture for scalable multicore systems[C]//Proc 22nd ACM SIGOPS Symposium on Operating Systems Principles. Big Sky, MT, USA:ACM, 2009:29-44.
[12] Wentzlaff D, Agarwal A. Factored operating systems (fos):The case for a scalable operating system for multicores[J]. ACM SIGOPS Operating Systems Review, 2009, 43(2): 76–85.
[13] Boyd-Wickizer S, Chen H, Chen R, et al. Corey:An operating system for many cores[C]//Proc 8th USENIX Symposium on Operating Systems Design and Implementation. San Diego, CA, USA:USENIX, 2008, 8:43-57.
[14] Rhoden B, Klues K, Zhu D, et al. Improving per-node efficiency in the datacenter with new OS abstractions[C]//Proc 2nd ACM Symposium on Cloud Computing. Cascais, Portugal:ACM, 2011:25.
[15] Kumar V, Fedorova A. Towards better performance per Watt in virtual environments on asymmetric single-ISA multi-core systems[J]. ACM SIGOPS Operating Systems Review, 2009, 43(3): 105–109. DOI:10.1145/1618525
[16] 曹仰杰, 钱德沛, 伍卫国, 等. 众核处理器系统核资源动态分组的自适应调度算法[J]. 软件学报, 2012, 23(2): 240–252. CAO Yangjie, QIAN Depei, WU Weiguo, et al. Adaptive scheduling algorithm based on dynamic core-resource partitions for many-core processor systems[J]. Journal of Software, 2012, 23(2): 240–252. (in Chinese)
[17] Mogul J C, Mudigonda J, Binkert N, et al. Using asymmetric single-ISA CMPs to save energy on operating systems[J]. IEEE Micro, 2008, 28(3): 26–41. DOI:10.1109/MM.2008.47
[18] Ye X, Fan D, Sun N, et al. SimICT:A fast and flexible framework for performance and power evaluation of large-scale architecture[C]//Proc of the 2013 International Symposium on Low Power Electronics and Design. Beijing, China:IEEE Press, 2013:273-278.
[19] Ferdman M, Adileh A, Kocberber O, et al. Clearing the clouds:A study of emerging scale-out workloads on modern hardware[C]//ACM SIGPLAN Notices. London, UK:ACM, 2012:37-48.