并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

异构集群环境下负载平衡调度算法研究与实现

围绕平衡负载这一目标，针对进程级并行任务的动态调度问题进行了研究，提出了一个异构集群环境下动态负载平衡算法，它结合了自适应数据采集与交换算法，有效的解决了服务器之间负载不平衡的问题，提高了系统的吞吐率。     

一个启发式任务团调度算法

基于任务聚类的启发式任务团调度是实现并行任务调度的有效方法。面向大型复杂武器系统的实时并行仿真,在研制自动并行化系统ＡＦＰ的过程中,基于关键任务的聚类算法,设计并实现了一个启发式任务图调度算法。     

基于CORBA的海量数据加载并行任务调度技术研究与实现

基于多集群的并行任务调度技术，简要描述在使用Oracle 10g进行海量数据加载中的并行任务调度问题，设计实现了一个基于CORBA的海量信息加载服务中的并行任务调度算法。通过测试结果表明，在适当的任务并行度的前提下，采取并行任务调度算法的加载服务的数据加载能力要优于传统的加载服务。     

三维重建网格系统中资源调度的研究

网格系统中存在着大量动态、异构的资源,有效的利用这些资源可以达到提高图像三雏重构的速度的目的.设计了图像三维重建系统的资源调度结构,基于该结构提出了改进启发式调度算法,并对算法的执行过程和并行任务集的存储方法进行论述.最后,利用GridSim对调度算法进行仿真测试.仿真测试结果表明,在图像三维重建系统中,改进启发式调度算法比传统的Min-Min算法具有更高的执行效率.     

蚁群算法在服务器集群批量任务调度中的应用

服务器集群中的负载均衡和作业调度是影响系统性能的重要因素.本文描述服务器集群批量任务的作业调度问题,对该问题建立了基于图的模型.由于使用一般的启发式算法或动态规划算法解决该问题具有局限性,本文引入蚁群算法进行求解,并针对该问题具体求解提出了启发式距离合适的计算方法.最后在仿真的基础上,讨论了算法的优化效果和收敛性,结果表明蚁群算法解决该问题具有优异的性能.     

粗粒度并行任务的动态调度算法（PTDS）及其有效性证明

本文揭示和探讨了并行多机系统中粗粒度并行任务的时间变化对静态任务调度机制的影响,给出了基于预调度的粗粒度并行任务的动态调度算法PTDS,并且严格地定义和证明了PTDS算法的有效性.结果表明PTDS通过局部调整预调度方案,能够有效地获得近似最优的计算任务调度方案.     

同构DVS集群中基于自适应阈值的并行任务节能调度算法

目前,高能效的并行任务调度算法设计已经成为集群系统的研究热点.现有基于复制的节能调度算法主要利用阈值平衡系统的性能和能耗,但随机设置的阈值无法根据性能需求和环境参数等特征自动调节,导致调度算法存在一定的局限性.文中提出一种面向同构集群系统的两阶段节能调度算法ATES(Adaptive Threshold-based Energy-efficient Scheduling).首先,设计一种基于自适应阈值的任务复制策略,该策略能够自动计算最佳阈值,利用该阈值获取近似最优的任务分组.然后,将各分组任务调度到支持DVS的处理器上,并充分利用任务之间的空闲时间降低处理器电压.该算法将任务复制策略与电压调节技术有机结合,在调度过程中能够自动调整阈值,有效提高调度算法的能效.为了验证ATES算法的合理性,通过典型应用进行仿真实验,并与常见任务调度算法进行比较,结果表明ATES算法能够更好地实现性能和能耗之间的平衡.     

对硬实时时间槽分配问题的EDF算法实现

在计算机及通信网络中，实时通信变得越来越重要。为了保证通信数据的传递在指定的截止时间时限内完成，避免产生冲突，可以采用一些合适的消息调度算法，针对硬实时时间槽分配问题（HRT-TSA），简要论述了这是一个NP-问题，对可行调度的必要条件进行了讨论，并提出了用截止时间最早最优先的启发式算法(EDF)，可以在多项式时间内实现HRT-TSA问题，给出了算法描述。EDF算法具有良好的调度性能，在实时系统中得到广泛应用。     

分布存储系统上一种新的并行调度算法

在一般的分布存储系统上各个处理器可能不同且资源共享,导致了并行任务在各个处理器上的执行时间具有很大的随机性,主要根据系统及并行任务特性等引进特征参数,采用计算与通信重叠等方法设计出了一种新的并行调度算法,即使在多用户环境下应用此算法不仅能达到极高的负载平衡,充分利用系统资源而且能有效地提高并行效率及加速比。实验结果表明,提出的新的并行调度算法与已有的类似调度算法相比能更加有效地利用系统资源及提高并行效率。     

网络并行计算系统中基于多处理机任务的资源调度模型

简要描述了网络并行计算系统中任务调度问题和经典的多处理机任务调度研究现状,并将两者结合到一起建立网络并行计算系统中的新型调度模型,较详细地论述了多处理机任务的定义,然后还讨论了该模型求解的近似调度策略及其近似优化问题,给出了其特例Pm｜fix｜Cmax问题的最优调度的时间跨度下界。     

高性能计算系统中的服务质量研究

高性能计算系统的资源管理以集群作业管理为主,这种粗粒度的管理方式缺乏有效的作业资源控制手段,不能准确了解作业的资源需求,在一定程度上仍然不可避免计算资源的浪费.针对高性能计算系统中高效利用系统计算资源的问题,提出并实现了基于操作系统的QoS服务质量框架,对作业资源使用进行细粒度的统计与控制,实现了资源的动态控制与协商机制,完善作业加载与调度策略,在高效利用系统资源方面取得了较好的应用效果.     

RB-FIFT--一种结合Firstfit及预约回填策略的机群作业调度算法

机群作业管理是机群系统软件的重要组成部分,作业调度策略则是机群作业管理系统的核心．作业调度策略的选择不仅关系到机群系统的效率,还影响了用户作业的响应时间．目前,Firstfit调度算法已经相当成熟并且广泛应用于机群作业调度．传统的Firstfit算法虽然着眼于减少资源碎片,但未能解决作业饥饿问题．曙光超级服务器作业管理系统JMS改进了既有的结合Firstfit和优先级的作业调度算法P-FIFT,将预约和回填策略与Firstfit相结合,引入了新的RB-FIFT调度策略．实验结果表明,与传统Firstfit算法及P—FIFT算法比较,RB-FIFT调度策略不但能够消除系统中作业的饥饿现象,而且大大减少了资源碎片,提高了系统的吞吐率和资源利用率．     

自适应邻域的多目标网格任务调度算法研究

针对网格计算中的多目标网格任务调度问题,提出了一种基于自适应邻域的多目标网格任务调度算法。该算法通过求解多个网格任务调度目标函数的非劣解集,采用自适应邻域的方法来保持网格任务调度多目标解集的分布性,尝试解决网格任务调度中多目标协同优化问题。实验结果证明,该算法能够有效地平衡时间维度和费用维度目标,提高了资源的利用率和任务的执行效率,与Min-min和Max-min算法相比具有较好的性能。     

基于动态虚拟机模型的云计算调度方法

将虚拟机加入云计算环境,可充分利用云计算的资源共享优势及其并行、分布计算功能;提出了一种可根据需要动态添加或删除虚拟机的模型系统,可有效节约云计算的使用费用,提高成本效率;研究了可用于本模型系统的两种资源调度算法——自适应先到先得（Adaptive First Come First Serve,AFCFS）和最大者优先（Largest Job First Served,LJFS）算法,尽量避免不必要的延迟,最大可能地提高系统性能,因为这对于分布式系统资源调度算法十分重要;模拟实验中采用了响应时间、等待时间、到达率等性能指标及性价比这一成本指标,比较了几种算法的性能效率,研究验证了模型系统的成本效率。实验结果表明几种算法可高效地运用于云计算环境,并能提高系统性能效率和成本效率。     

A multi-dimensional scheduling scheme in a Grid computing environment

In this paper, we propose a novel distributed resource-scheduling algorithm capable of handling multiple resource requirements for jobs that arrive in a Grid computing environment. In our proposed algorithm, referred to as multiple resource scheduling (MRS) algorithm, we take into account both the site capabilities and the resource requirements of jobs. The main objective of the algorithm is to obtain a minimal execution schedule through efficient management of available Grid resources. We first propose a model in which the job and site resource characteristics can be captured together and used in the scheduling algorithm. To do so, we introduce the concept of a n-dimensional virtual map and resource potential. Based on the proposed model, we conduct rigorous simulation experiments with real-life workload traces reported in the literature to quantify the performance. We compare our strategy with most of the commonly used algorithms in place on performance metrics such as job wait times, queue completion times, and average resource utilization. Our combined consideration of job and resource characteristics is shown to render high-performance with respect to above-mentioned metrics in the environment. Our study also reveals the fact that MRS scheme has a capability to adapt to both serial and parallel job requirements, especially when job fragmentation occurs. Our experimental results clearly show that MRS outperforms other strategies and we highlight the impact and importance of our strategy.     

Using a sparse promoting method in linear programming approximations to schedule parallel jobs

In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the ℓ_p‐quasi‐norm for p∈(0,1). Minimization of the ℓ_p‐quasi‐norm is implemented via a successive linear programming approximation heuristic. We propose several new algorithms based on this approach, and we assess their efficiency through simulations. The experiments show that the scheme outperforms the classic Largest Task First list based algorithm for scheduling small to medium instances but needs improvements to compete on larger numbers of jobs. Copyright © 2014 John Wiley & Sons, Ltd.     

面向Flink的负载均衡任务调度算法的研究与实现

Apache Flink是现在主流的大数据分布式计算引擎之一,其中任务调度问题是分布式计算系统中的关键问题。由于集群的异构性以及不同算子复杂度不同,大数据计算系统Flink中不可避免地会出现负载不均的情况,针对这种问题,提出了基于资源反馈的负载均衡任务调度算法RFTS。通过实时资源监控、区域划分和基于人工萤火虫优化的任务调度算法3个模块,把负载过重的机器中处于等待状态的任务分配给负载较轻的机器,来实现集群的负载均衡,提高系统集群利用率和执行效率。最后通过基于TPC-C和TPC-H数据集的实验结果表明,RFTS算法从执行时间和吞吐量2个方面有效提升了Apache Flink计算系统的性能。     

基于层次化调度策略和动态数据复制的网格调度方法

针对在网格中如何有效地进行任务调度和数据复制, 以便减少任务执行时间等问题, 提出了任务调度算法（ISS）和优化动态数据复制算法（ODHRA）, 并构建一个方案将两种算法进行了有效结合。该方案采用ISS算法综合考虑任务等待队列的数量、任务需求数据的位置和站点的计算容量, 采用网络结构分级调度的方式, 配以适当的权重系数计算综合任务成本, 搜索出最佳计算节点区域; 采用ODHRA算法分析数据传输时间、存储访问延迟、等待在存储队列中的副本请求和节点间的距离, 在众多的副本中选取出最佳副本位置, 再结合副本放置和副本管理, 从而降低了文件访问时间。仿真结果表明, 提出的方案在平均任务执行时间方面, 与其他算法相比表现出了更好的性能。