性能非对称多核处理器下异构感知调度技术

为了满足应用程序的多样化需求,异构多核处理器出现并逐渐进入市场,其中的处理核心（core）具有不同的微架构或者指令集架构（ISA）,为应用提供多样化特性支持,比如指令级并行（ILP）、内存级并行（MLP）,这些核心协同工作满足整个计算系统的优化目标,比如高性能、低功耗或者良好的能效.然而,目前主流的调度技术主要是针对传统同构处理器架构设计,没有考虑异构硬件能力的差异性.在异构多核处理器环境下,调度技术如何感知硬件的异构特性,为不同类型的应用程序提供更加合适和匹配的硬件资源,这是值得探索的问题.对近年来在该研究领域的成果进行了综述研究,特别是在性能非对称多核处理器架构下,异构调度技术面临的优化目标、分析模型、调度决策和算法评估等主要问题进行了分析和描述,并依次对相关技术进行了系统的总结,最后从软硬件融合的角度对今后的研究工作进行了展望.     

一种面向非对称多核处理器的虚拟机集成调度算法

在计算机体系结构领域,非对称多核处理器将成为未来的主流.对于非对称多核处理器上的虚拟处理器调度问题,现有研究缺乏理论分析,且没有考虑虚拟处理器的同步特性.针对该问题,文中首先建立非线性规划模型,分析得出全面考虑虚拟处理器同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法定义了效用因子、比例系数、比例资源的概念,结合虚拟处理器的同步特性和核心的非对称性对资源和负载进行全面度量;同时通过运行队列分解降低调度开销.提出的算法是第一个在非对称多核处理器上利用虚拟处理器同步特性的调度算法.实际平台上的实验表明:该算法实现了公平调度,并且性能比其他同类算法提高19%~48%.     

虚拟集群上面向功耗的形式化的VM调度策略

针对虚拟化集群上日益严重的功耗问题,在定义集群、物理机、操作点、能耗、任务集、虚拟机等概念的基础上,提出了形式化的虚拟机(Virtual Machine,VM)调度策略,并有针对性地利用动态电压和频率调整(Dynamic Voltage and Frequency Scaling,DVFS)技术对普通算法进行了扩展改进,提出一个功耗敏感的VM调度算法。首先,利用FFD(First-Fit Decreasing)算法解决虚拟机的初始布局问题,然后尽可能地将虚拟机部署在低电压的物理机上,此外加入性能感知策略,尽量将物理机的电压调节至刚好满足虚拟机性能需求,以避免"奢侈"能耗的浪费,同时增加了虚拟机调度失败时灵活调整电压的规则,以减少错误先验知识对虚拟机后续部署的误导。在理想模型中的仿真实验表明:与现有部署算法相比,本算法具有更好的节能效应,以及相对不大的性能损失。     

一种面向非对称多核处理器的综合性调度算法

在非对称多核处理器上进行任务调度时,现有的操作系统调度器没有考虑其非对称性.针对单一指令集非对称多核处理器上的操作系统调度问题,首先建立线性规划模型,分析各种因素,得出行为匹配、减少迁移和负载均衡的调度原则.然后,基于调度原则提出一种综合性调度算法.该算法包括两个部分:1) 集成负载表征,提出集成行为的概念,全面衡量任务的整体性和阶段性行为;2) 基于集成行为的调度算法,有效开发非对称多核处理器的特性,能够保证各核心负载均衡,同时可以避免不必要的任务迁移.另外,该算法通过参数调整机制实现了算法的通用性.该算法是一种综合处理任务的整体性和阶段性行为,并具备通用性的调度算法.实际平台上的实验结果表明,该算法可通用于多种环境,且性能比其他对应算法提高6%～22%.     

面向多核处理器系统的Cache感知调度算法

Cache空间的不公平使用和争用直接影响系统的整体性能,现有Linux操作系统的默认调度算法不能感知程序的行为,包括访问cache的失效次数,不了解线程之间访存模式和频度上可能存在的差异,因而无法做出更加合理的调度.本文提出并在Linux环境下实现了一种Cache感知的调度算法CAS,通过监测每个任务每千条指令的共享cache失效次数,把cache失效次数相近的任务聚合到同一个核上,使得cache失效次数差异较大的任务运行在不同的核上,避免了cache失效次数都很大的任务在不同的核上同时运行,从而减小了cache空间的不公平使用和争用.实验表明,CAS算法在大多数情况下,减少了整个负载的共享cache失效次数,提高系统的平均吞吐量约5％左右.     

基于同构多核处理器的任务调度

随着现代应用对计算机性能要求的提高,计算机主频不断提升。由于功耗和半导体工艺的限制,仅靠提高单核主频难以继续维持“摩尔定律”,同构多核处理器（Homogeneous Multi-core）应运而生。在同构多核处理器的支持下,一个芯片汇集多个地位对等、结构相同的通用处理器核,以最小的代价满足了提高系统性能、负载均衡、处理器容错的需要。并行体系结构需要结合与之适应的软件实现性能效益的倍增。本文从操作系统层面,针对处理器结构的变化,研究并实现多核任务调度。系统采用混合调度策略,簇间独立调度,簇内统一调度。从调度模式、调度算法、分配算法、调度时机等方面详细分析了多核调度的原理和实现机制。最后通过模拟实验证明功能正确性及算法可调度性。     

异构多核下兼顾应用公平性和能耗的调度方法研究

异构多核处理器通常由高性能的大核和低能耗的小核组成,在其上进行合理的线程调度可以有效地提高资源利用率,节省能耗。之前论文提出的大小核上的公平性调度并没有考虑核上有不同频率/电压状态的情况,而现在支持DVFS调节的处理器越来越普遍,因此很有必要将线程间公平度的计算进行扩展和改进。提出在每个核有若干种不同的DVFS状态时异构多核处理器上线程公平度的计算方法,对已有的性能预测模型进行改进,采用自适应算法调整模型中的系数,并在此基础上提出了一种调度策略,维持各线程之间的公平度和处理器功率满足提前设定的阈值,同时选取能效最优化的配置,实现减小应用运行能耗的目的。实验结果表明,与所提出的调度策略相比,采用static、DVFS-only、swap-only三种调度方法时,在总的运行时间几乎相同的情况下,平均要多产生20%以上能耗,对于有些应用甚至达到了50%。     

基于多核处理器系统多维限制的节能实时调度

介绍了多核处理器系统所面对的处理器实际限制、抢占调度实际限制和并行任务模型实际限制等多维限制挑战, 主要针对处理器开销模型、有限抢占模型和复杂并行任务模型等方面, 深入探讨了基于系统实际多维模型的多核节能实时调度研究, 为促进多核处理器系统在实时嵌入式领域的应用提供理论和技术参考.     

多核多线程处理器的随机测试流量生成技术

以可编程多核多线程处理器IXP2400为例,围绕随机测试流量的生成问题进行讨论,推导出随机测试流量生成公式,利用分解法对GI/G/m/∞/FCFS多类型客户输入开放排队网络求解,给出输出流到达时间间隔变异系数的求解方法,通过控制测试帧间时延使得生成的测试流量符合多种概率分布。提出的技术应用于“基于IXP2400的网络测试系统”,并对其进行测试,实验验证了该技术的可用性及有 效性。     

非对称多核处理器上的操作系统集成调度

相对于对称多核处理器,非对称多核处理器具有更高的效能,将成为未来并行操作系统中的主流体系结构.对于非对称多核处理器上操作系统的并行任务调度问题,现有的研究假设所有核心频率恒定,缺乏理论分析,也没有考虑算法的效能和通用性.针对该问题,该文首先建立非线性规划模型,分析得出全面考虑并行任务同步特性、核心非对称性以及核心负载的调度原则.然后,基于调度原则提出一个集成调度算法,该算法通过集成线程调度和动态电压频率调整来提高效能,并通过参数调整机制实现了算法的通用性.提出的算法是第一个在非对称多核处理器上结合线程调度和动态电压频率调整的调度算法.实际平台上的实验表明:该算法可适用于多种环境,且效能比其他同类算法高24%～50%.     

单处理器系统的实时调度算法研究

实时调度算法是实时系统中的关键技术。文章在研究单处理器系统中常用实时调度算法：固定优先级调度算法和动态优先级调度算法基础上，详细分析了常用固定优先级调度算法RM、DM算法和动态优先级调度算法EDF、LLF和MLLF算法的运算过程和使用条件，提出了各个算法在实际应用中存在的问题，为实际应用中选择何种实时调度算法确定了依据。     

一种基于同构多核处理器的动态节能调度算法

在节能计算系统中节能调度是一个重要的研究方向。目前针对节能调度的研究中,多从动态电压频率调节（DVFS）的角度进行。但是随着芯片制造工艺的改进,处理器核心电压越来越低,所能调节的电压范围越来越小,通过DVFS技术实现节能遇到了理论上的瓶颈。提出了一种基于同构多核处理器的动态节能调度算法。在系统负载较轻的情况下,通过将系统任务分配到较少的处理核心上而使其他处理核心处于休眠状态来达到动态节能的效果。实验表明该算法具有较好的节能效果。     

温度感知的Linux多核调度算法研究

多核处理器温度升高会影响芯片的稳定性和性能的发挥,硬件层面的DTM(Dynamic Thermal Management)方法以牺牲处理器性能为代价来降低功耗,提出了在一种软件层面的温度感知调度算法,它可以在线实时获取处理器性能计数器的值并计算各个执行核温度,根据各执行核的温度状况在各个核上合理分配进程,给出了温度感知的启发式方法。基于ATMI温度仿真器的仿真表明,温度感知调度算法较无温度感知的算法可以创建更均匀的功率密度图,且带MST启发式方法的温度感知调度算法能明显减少进程的迁移次数。     

基于通用多核处理器平台的并行基因表达式编程算法

基因表达式编程(Gene Expression Programming, GEP)是一种计算量大且通用性强的新型进化算法,其传统计算形式不能充分利用目前主流的多核处理器。为提高算法效率,提出了基于通用多核处理器平台的并行基因表达式编程算法(Parallel Gene Expression Programming Based on General Multi-core Processor, PGEP-MP)。主要工作包括:O)分析通用多核处理器平台下并行基因表达式编程算法的机理;(2)利用MPI和()pcnMP混合编程模型设计基于通用多核处理器平台的基因表达式编程算法的粗粒度与细粒度相结合的并行模型;(3)提出改进PEEP-MP算法效率的进化策略;(4)通过对函数挖掘和分类的实验证明,PEEP-Ml〕算法提高了函数挖掘和分类的效率,在并行双核处理器数为4的情况下,PEEP-MP的平均并行加速比分别是传统GEP算法的4. 22倍和 4. 06倍。     

Linux系统中多核实时调度平台的设计

为使各种实时调度算法能够在Linux环境中得到运行和验证,设计一种Linux系统中的公共多核调度平台。该平台由调度模块和跟踪测试模块组成,调度模块实现系统调用、调度处理以及同步功能,跟踪测试模块实现日志和跟踪功能。测试结果表明,该平台可正确显示调度算法的运行结果。     

一种针对依赖性周期任务的实时多核调度算法

针对软实时系统中的一类同时具有依赖性与周期性的任务,提出一种基于单行树矩阵(MST)的动态因子均衡调度算法SMD(schedule on matrix of the single tree and dynamic load factor)。该算法通过对MST矩阵的特性进行分析,将任务划分为若干并行集,再综合考虑已执行时间、任务间的依赖关系及任务最早截止时间几个要素,以动态因子的形式对任务进行实时调度。最后,还以证明的形式给出了可充分调动的任务集的充分条件,并以此为基础随机生成了测试任务集,进行了对比实验。实验表明,与文献中现有经典算法相比,新算法使处理器利用率提升近15%,任务丢失率降低2%。     

一种面向多核处理器并行系统的启发式任务分配算法

多核处理器使得并行系统的结构更加复杂并且其中任务个数大大增加,为了在这类系统中高效地进行任务分配,建立了任务分配模型,并提出了一种包含两轮操作的启发式任务分配算法,分别完成进程到处理节点和进程内线程到处理器核的分配.每轮操作经过带回溯的多次迭代处理,最终得到任务到处理器核的分配方案.与穷举查找法和遗传算法的对比测试表明该算法能在较短时间内求得近优解,并且当线程个数增大时,算法的求解时间远小于遗传算法.     

众核处理器系统核资源动态分组的自适应调度算法

针对众核处理器系统的核资源优化使用问题,提出了一种支持核资源动态分组的自适应调度算法CASM(core-partitioned adaptive scheduling for many-core systems).该算法通过对任务簇的拆分与合并,动态构建可弹性分区的核逻辑组,实现核资源的隔离优化访问.为了平衡核资源利用率及任务调度效率,CASM算法针对任务簇间和簇内的不同特点,分别采用公平性较好的均衡调度算法和资源利用率较高的自适应调度算法.在线竞争理论分析表明,CASM算法的任务执行时间在线竞争比为常数2,其性能可扩展性较好.实验结果表明,与WS(work-stealing),AGDEQ(adaptive greedy dynamicequi-partitioning)和EQUI°EQUI算法相比,CASM算法使任务集运行时间分别减少了近46％,32％和15％.在相同能耗情况下,CASM算法大幅度地提升了系统吞吐量.     

三维芯片多层与多核并行测试调度优化方法

针对测试环节在三维（3D）芯片制造过程中成本过高的问题,提出一种基于时分复用（TDM）的协同优化各层之间、层与核之间测试资源的调度方法。首先,在3D芯片各层配置移位寄存器,通过移位寄存器组对输入数据的控制,实现对各层之间以及同一层的各个芯核之间的测试频率的合理划分,使位于不同位置的芯核能够被并行测试;其次,使用贪心算法优化寄存器的分配,减少芯核并行测试的空闲周期;最后,采用离散二进制粒子群优化（DBPSO）算法求出最优3D堆叠的布图,以便充分利用硅通孔（TSV）的传输潜力,提高并行测试效率,减少测试时间。实验结果表明,在功耗约束下,优化后整个测试访问机制（TAM）利用率平均上升16.28%,而3D堆叠的测试时间平均下降13.98%。所提方法减少了测试时间,降低了测试成本。