高实时性异构多核处理器任务调度算法

在异构多核处理器条件下,Min-Min算法调度性能较好但在系统实时响应方面存在不足。最小空闲时间优先调度算法(LSF)、最早截止时间优先调度算法(EDF)和最大价值优先调度算法(HVF)虽然在系统任务调度响应实时性方面表现优异,但却不适用于异构多核处理器环境。为此,提出一种高实时性任务调度算法HRSA。在Min-Min调度算法的基础上融合LSF,EDF,HVF算法的调度策略,将任务能耗、任务完成价值和任务响应比相结合,在实现异构多核处理器任务动态调度的同时缩短系统对高实时性任务的响应时间。实验结果表明,相对于EDF算法和Min-Min算法,HRSA算法消耗单位能量所带来的价值较高,对高实时性任务处理的响应时间较短。     

异构系统中针对通信密集型任务调度的算法*

针对异构多核系统的通信密集型任务的调度,提出了一种综合算法即,HCDUL。该算法首先进行聚簇,然后优先调度就绪关键路径节点,其他就绪节点根据节点的ranku值排序,当处理器有空闲时复制上层节点。使用随机生成图法进行模拟实验,与其他算法相比,HCDUL算法有更小的调度长度。     

异构边缘资源的任务卸载和协同调度

边缘计算广泛应用于物联网、车联网和在线游戏等新兴领域,通过网络边缘部署计算资源为终端设备提供低延迟计算服务.针对如何进行任务卸载以权衡任务执行时间与传输时间、如何调度多个不同截止期任务以最小化总延迟时间等挑战性问题,提出1种异构边缘协同的任务卸载和调度框架,包括边缘网络拓扑节点排序、边缘节点内任务排序、任务卸载策略、任务调度和结果调优等算法组件;设计多种任务卸载策略和任务调度策略;借助多因素方差分析（multi-factor analysis of variance,ANOVA）技术在大规模随机实例上校正算法算子和参数,得到统计意义上的最佳调度算法.基于EdgeCloudSim仿真平台,将所提出调度算法与其3个变种算法从边缘节点数量、任务数量、任务分布、截止期取值区间等角度进行性能比较.实验结果表明,所提出调度算法在各种情形下性能都优于对比算法.     

基于有向无环图网格独立任务调度算法*

提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时, MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的MinMin 算法。     

非集中调度模型下的网格资源调度研究*

针对当前网格资源调度系统扩展性差的问题,提出了基于非集中调度模型的以保守Backfilling算法为核心的网格资源调度算法.探讨了网格任务在站点处理器数目异构情况下,网格作业多站点协同调度问题.实验仿真证明,在跨网格站的资源调度中,运用资源预留策略和多站点作业分块可以改善作业的平均响应时间,并起到负载平衡的效果.     

Storm集群下基于性能感知的负载均衡策略

Storm计算框架具有为多源异构大数据提供高效、快速、实时处理的能力.然而因Storm默认的调度策略使用了简单的轮询方法,无法根据集群动态的负载状态调整其任务的分配.针对该问题,提出了基于性能感知的负载均衡策略,根据节点的处理效率计算其性能感知值,并通过贪心调度保证节点的任务量与节点处理能力相匹配,以达到负载均衡的目的.通过与默认调度算法实验比较,结果表明该算法能够有效降低Storm处理时延,提高吞吐量和实现集群负载均衡.     

基于遗传算法的网格资源调度算法

网格将多种资源组织在一个统一的框架下，为各种复杂的计算任务提供资源．因此计算任务在各种资源之间的调度成为了一个关键的问题．简述了在异构资源之间调度任务的重要性，提出了一种基于遗传算法的任务调度算法，该算法采用资源一任务的间接编码方式，通过DAG图获取子任务的层次关系，并将子任务按照层次深度排序，解决了种群中的非法问题．在单一资源上采用短任务优先和父节点优先两个原则来安排子任务的执行次序，以避免出现任务堵塞的现象．     

多核机群主节点并发发送数据的可分负载调度

对于节点计算、通信与存储能力不同、节点由多个多核处理器(多个片上多处理器)组成且共享L3cache的机群系统,采取计算与传输重叠模式,提出了主节点以多进程方式并发发送数据给从节点的可分负载调度模型.该调度模型自适应节点具有不同的计算、通信和存储能力,动态计算、确定调度轮数和每轮调度分配给各从节点的负载块规模,以平衡各节点的计算负载、减少节点之间的通信开销,缩短任务调度长度.依据各节点中的L3cache,L2cache和L1cache的可用存储容量,提出了对节点主存中接收到的负载块进行多级缓存划分的数据分配方法,以确保分配给节点中各个多核处理器、各个内核的负载平衡.基于提出的多核机群节点间可分负载调度模型和节点内多级存储数据分配方法,设计实现了节点拥有多个多核处理器的异构机群上通信和存储高效的k-选择并行算法.在曙光TC5000A多核机群系统上,测试了主节点并行与串行发送数据给从节点的任务调度方式、各级缓存利用率、每个核心执行不同数目的线程对并行算法运行性能的影响.实验结果表明:基于主节点并发发送数据给从节点的调度模型设计的k-选择并行算法,其运行性能优于基于主节点串行发送数据给从节点的调度模型设计的k-选择并行算法;L3cache和L2cache利用率大小对算法运行性能影响较大;当L3cache,L2cache和L1cache利用率取其优化组合值、每个核心运行3个线程时,算法所需的运行时间最短.     

面向节点异构GPU集群的能量有效调度方案

GPU集群已经成为高性能计算(HPC)领域的主流组件。随着处理单元的发展和集群节点的拓展,GPU集群将在节点层面趋于异构化。提出一套针对异构任务在节点异构GPU集群上的能量有效调度方案。形式化地描述其任务和资源模型以及能耗评估模型。通过特定的节点选择策略,减少空闲状态的能耗损失。通过任务类型划分和组合分配以及DVFS,增加CPU资源利用率。该方案从系统层面着手,能够与现有的算法和指令层面的优化方法兼容。     

面向边缘计算的Storm边缘节点调度优化方法

边缘计算有高实时性和大数据交互处理的需求,边缘异构节点间的调度时耗长、通信时延高以及负载不均衡是影响边缘计算性能的核心问题,传统的云计算平台难以满足新的要求。文中研究了在边缘计算环境下Storm边缘节点的调度优化方法,建立了面向边缘计算的Storm任务卸载调度模型。针对拓扑任务在边缘异构节点间的实时动态分配问题,提出了一种启发式动态规划算法(Inspire Dynamic Programming,IDP),通过改变Storm的Task实例的排序分配方式以及Task实例和Slot任务槽的映射关系实现全局的优化调度;同时,针对拓扑任务的并发度受限于JVM栈深度的缺陷,提出了一种基于蝙蝠算法的调度策略。实验结果表明,与Storm调度算法相比,所提算法在边缘节点CPU利用率指标上平均提升了约60%,在集群的吞吐量指标上平均提升了约8.2%,因此能够满足边缘节点之间的高实时性处理要求。     

Scheduling online mixed-parallel workflows of rigid tasks in heterogeneous multi-cluster environments

Workflow scheduling on parallel systems has long been known to be a NP-complete problem. As modern grid and cloud computing platforms emerge, it becomes indispensable to schedule mixed-parallel workflows in an online manner in a speed-heterogeneous multi-cluster environment. However, most existing scheduling algorithms were not developed for online mixed-parallel workflows of rigid data-parallel tasks and multi-cluster environments, therefore they cannot handle the problem efficiently. In this paper, we propose a scheduling framework, named Mixed-Parallel Online Workflow Scheduling (MOWS), which divides the entire scheduling process into four phases: task prioritizing, waiting queue scheduling, task rearrangement, and task allocation. Based on this framework, we developed four new methods: shortest-workflow-first, priority-based backfilling, preemptive task execution and All-EFT task allocation, for scheduling online mixed-parallel workflows of rigid tasks in speed-heterogeneous multi-cluster environments. To evaluate the proposed scheduling methods, we conducted a series of simulation studies and made comparisons with previously proposed approaches in the literature. The experimental results indicate that each of the four proposed methods outperforms existing approaches significantly and all these approaches in MOWS together can achieve more than 20% performance improvement in terms of average turnaround time.     

基于动态适应度的独立任务调度算法

在分析现有启发式调度算法的优缺点的基础上，综合考虑负载平衡和使尽可能多的任务调度到更适合它的机器上，提出了基于动态适应度（DFD）的调度算法，任务的DFD描述了最早完成时间所在机器对任务的适应程度，本算法以任务的DFD为优先级，优先调度DFD高的任务。与参考文献中其他算法进行比较表明，本算法能产生更好的调度结果。     

网格计算中任务调度算法的研究和改进

任务调度一直是网格计算中的热点问题,任务调度的目的是最优地分配任务,实现最佳的调度策略,以高效地完成计算任务。在网格环境中,资源的合理有效利用是实现任务调度的关键问题之一。本文首先论述静态任务调度算法和动态任务算法的原理和优缺点等,然后结合Min-min、Max-min算法的优点设计一种新的调度算法SA-MM,根据资源的使用情况自适应调度相应算法进行任务到资源的映射。最后,用GridSim模拟工具对网格计算中Min-min、Max-min和SA-MM任务调度算法进行仿真实验,分析和比较它们的调度长度(MakeSpan)和资源负载情况等影响任务调度效率的指标。     

基于优先级的任务调度与负载均衡模型研究

在分布式计算环境下，为了有效地利用计算资源、快速完成协同计算任务，提出了基于优先级的任务调度与负载均衡模型．首先根据就绪任务队列和任务调度器所处的位置以及两者之间的关系，将任务调度划分为集中式任务调度和非集中式任务调度两种方式，在此基础上，利用时间Petri网建模技术，分别给出了采用这两种任务调度方式的、基于优先级的任务调度与负载均衡模型，并对各种模型的特点进行了详细分析．以此模型为基础，可以利用现有的时间Petri分析技术，对采用上述任务调度方式的任务调度算法进行模拟和分析，以便找出满足给定条件的最优的任务调度算法．     

可重构系统中的实时任务在线调度与放置算法

有效的任务调度与放置是发挥可重构计算性能优势的重要因素.针对实时任务在二维可重构器件上的在线调度问题,定义了调度算法完全识别的概念,即算法不会拒绝能够成功调度的任务.提出了新的实时在线调度与放置算法,充分利用了任务的时间信息,实现了完全识别的调度.实验表明,与已有的算法相比,新算法显著地改善了调度效果,而运行开销没有明显增加.     

HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta-heuristic algorithms

Cloud computing is becoming a profitable technology because of it offers cost-effective IT solutions globally. A well-designed task scheduling algorithm ensures the optimal utilization of clouds resources and reducing execution time dynamically. This research article deals with the task scheduling of inter-dependent subtasks on unrelated parallel computing machines in a cloud computing environment. This article considers two variants of the problem-based on two different objective function values. The first variant considers the minimization of the total completion time objective function while the second variant considers the minimization of the makespan objective function. Heuristic and meta-heuristic (HEART) based algorithms are proposed to solve the task scheduling problems. These algorithms utilize the property of list scheduling algorithm of unrelated parallel machine scheduling problem. A mixed integer linear programming (MILP) formulation has been provided for the two variants of the problem. The optimal solution is obtained by solving MILP formulation using A Mathematical Programming Language (AMPL) software. Extensive numerical experiments have been performed to evaluate the performance of proposed algorithms. The solutions obtained by the proposed algorithms are found to out-perform the existing algorithms. The proposed algorithms can be used by cloud computing service providers (CCSPs) for enhancing their resources utilization to reduce their operating cost.     

一种优先满足最小服务需求的动态网格资源调度算法

资源调度问题是网格研究必须解决的关键问题之一。目前,围绕着网格中的资源调度算法,国内外已做了大量的研究工作,先后提出了各种静态和动态调度算法。本文针对目前网格调度机制存在的问题,介绍了一种新的网格调度技术--优先满足最小服务需求的动态网格资源调度算法。该调度算法优先满足现有任务对资源的最小要求,从而减小小单个任务的等待时间。实验结果表明,该方法不但可以有效减少单个任务的延迟,而且在任务的吞吐率及CPU效率方面都比较好。     

一种面向自动驾驶推理任务的工作流调度策略

目前自动驾驶推理任务调度中要解决的关键问题是如何在不同的时间窗内,让实时推理任务满足可容忍时间约束的前提下,在相应的处理设备上被调度执行完成.在不同时间窗内,依据边缘节点的数量变化以及推理任务的不同,设计了一种边缘环境下基于强化学习算法的工作流调度策略.首先,利用推理任务工作流调度算法计算任务的完成时间;其次,采用基于模拟退火的Q学习算法(Q-learning based on simulated annealing,SA-QL)来优化推理任务的完成时间;最后,从可行性、收敛性、有效性和探索性四个角度来体现基于模拟退火的强化学习算法(Reinforement learning based on simulated annealing,SA-RL)和粒子群优化算法(Particle Swarm Optimization,PSO)的性能差异.实验结果表明,模拟退火的强化学习算法和粒子群优化算法都具有可行性和有效性,单步时序差分算法(TD(0))具有更强的探索性,多步时序差分算法(TD(λ))具有更强的收敛性.     

改进K-means聚类的云任务调度算法

针对云任务调度中存在的效率低、费用高等问题,提出一种基于改进K-means聚类算法的云任务调度算法。依据虚拟资源的硬件属性,使用改进聚类算法对虚拟资源进行聚类划分;计算任务偏好,使不同偏好的任务在不同的聚类中选择资源;考虑到调度费用问题,对每个聚类使用改进后的Min-min算法进行任务调度。针对K-means聚类算法初始聚类中心随机选取,易陷入局部最优解的问题,对聚类算法进行改进。最后,利用云仿真平台CloudSim进行实验,结果表明,与无聚类的调度算法相比,本文提出的算法在执行效率方面有所提高。     

基于多QoS约束的网格任务调度算法

提出一种基于QoS的网格资源管理模型和此模型下基于多QoS约束的网格任务调度算法。引入效益函数对QoS描述建模,为网格任务调度算法提供合理的优化目标。在此基础上改进传统调度算法得到基于多QoS约束的调度算法。实验表明,改进后的算法有更好的性能,更适合应用于网格环境中。