赋权超图划分算法的电路划分实验比较研究

给出了赋权超图优化划分问题的形式化描述,并结合电路划分的具体应用,采用赋权超图来构造ISPD98电路测试基准的数学模型。阐述了基于迁移方法和多水平方法的赋权超图优化划分算法,并重点讨论了粗化阶段的不同结点匹配策略、迁移优化阶段的不同结点迁移优化策略。基于ISPD98测试基准给出的18 组电路,进行了迁移方法和多水平方法的对比实验,以及五种结点匹配和三种结点迁移优化不同组合策略的对比实验,实验数据对比充分验证了多水平方法的可行性和效率。     

网格优化有向超图任务调度算法

任务调度是网格计算的一个重要部分.分析网格环境下任务调度的特点以及传统DAG图的优缺点,吸取有向超图的优点,将有向超图理论融合网格环境特征,建立了网格环境下的优化有向超图模型,并在此基础上通过网格优化有向超图的水平构形、标号及带宽计算实现任务对网格资源的映射与调度,提出网格优化有向超图任务调度算法GODHTS.模拟实验结果证明了该模型及其算法的有效性和优越性.     

超图划分问题的元胞自动机模型及算法研究

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点。实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低。     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

一种基于能耗优化的云计算系统任务调度方法

服务器执行任务产生的能耗是云计算系统动态能耗的重要组成部分。为降低云计算系统任务执行的总能耗,提出了一种基于能耗优化的最早完成时间任务调度方法,建立了服务器动态功率计算模型,基于动态功率的服务器执行能耗模型,以及云计算系统的能耗优化模型。调度策略根据任务的截止时间要求和在不同服务器上的执行能耗,选择不同的调度算法,以获得最小任务执行总能耗。实验结果证明,提出的任务调度方法,能够较好地满足任务截止时间的要求,降低云计算系统任务执行的总能耗。     

基于代价优化的云工作流调度改进PSO算法

云计算可以通过即付即用的方式向用户工作流提供资源。为了解决资源服务代价异构环境下的云工作流任务调度代价问题,提出一种基于改进粒子群算法的云工作流任务调度算法WSA-IPSO。通过综合考虑任务的执行代价和依赖任务间发生数据传输时的通信代价,算法将总代价优化问题形式化为有向无环图DAG中的任务调度模型,并提出基于改进粒子群算法的优化模型对其进行求解。通过改进传统粒子群算法的粒子速度更新策略和惯性权重更新策略,算法可以以更快的收敛速度得到代价最小化的调度方案。通过仿真实验,与MCT算法及标准粒子群算法进行性能比较。实验结果表明,WSA-IPSO算法在降低总代价、任务分布的负载均衡以及算法收敛性方面比较同类算法均表现出更好的性能。     

云环境下基于强化学习的多目标任务调度算法

针对云计算环境下的多目标任务调度问题,提出一种新的基于Q学习的多目标优化任务调度算法(Multi-objective Task Scheduling Algorithm based on Q-learning,QM TS).该算法的主要思想是:首先,在任务排序阶段利用Q-learning算法中的自学习过程得到更加合理的任务序列;然后,在虚拟机分配阶段使用线性加权法综合考虑任务最早完成时间和计算节点的计算成本,达到同时优化多目标问题的目的;最后,以产生更小的makespan和总成本为目标函数对任务进行调度,得到任务完成后的实验结果.实验结果表明,QMTS算法在使用Q-learning对任务进行排序后可以得到比HEFT算法更小的makespan;并且根据优化多目标调度策略在任务执行过程中减少了makespan和总成本,是一种有效的多目标优化任务调度算法.     

云计算环境下基于时间和可靠性的调度策略

云计算中,调度策略对于用户任务的运行和服务提供方均有很大的影响,直接影响到云平台的运行效果。针对传统任务调度算法难以适用于云计算环境这一问题进行了研究,采用由星型结构演化而成的多代理模型,首先给出多代理模型的体系结构,然后针对多代理系统,提出了基于服务时间和可靠性为优化目标的任务调度策略,并采用模拟退火算法进行求解。最后进行了仿真实验,实验结果表明我们的调度策略是高效的。     

云环境下基于DO-GAPSO的任务调度算法

为了找到合理的云计算任务调度方案,仅从单一方面来优化调度策略已不能满足用户需求,但从多个方面优化调度策略又面临着权重分配问题。针对上述问题,从任务完成时间、任务完成成本、服务质量3个方面考虑,提出一种基于遗传与粒子群算法相融合的动态目标任务调度算法,在算法的适应度评价函数建模中引入线性权重动态分配策略。通过CloudSim平台进行云环境仿真实验,并将此算法与经典的双适应遗传算法(DFGA)、离散粒子群优化算法(DPSO)进行比较。实验结果表明,在相同的设置条件下,该算法在执行效率、寻优能力等方面优于其他两个算法,是一种云计算环境下有效的任务调度算法。     

随机任务在云计算平台中能耗的优化管理方法

针对云计算系统在运行过程中由于计算节点空闲而产生大量空闲能耗,以及由于不匹配任务调度而产生大量“奢侈”能耗的能耗浪费问题,提出一种通过任务调度方式的能耗优化管理方法.首先,用排队模型对云计算系统进行建模,分析云计算系统的平均响应时间和平均功率,建立云计算系统的能耗模型.然后提出基于大服务强度和小执行能耗的任务调度策略,分别针对空闲能耗和“奢侈”能耗进行优化控制.基于该调度策略,设计满足性能约束的最小期望执行能耗调度算法ME3PC(minimum expectation execution energy with performance constraints).实验结果表明,该算法在保证执行性能的前提下,可大幅度降低云计算系统的能耗开销.     

云中多媒体应用中基于混合DAG的最优任务调度研究

云计算的平台优势使得它在多媒体应用中得到广泛使用。由于多媒体服务的多样性和异构性,如何将多媒体任务有效地调度至虚拟机进行处理成为当前多媒体应用的研究重点。对此,研究了云中多媒体最优任务调度问题,首先引入有向无环图来模拟任务中的优先级及任务之间的依赖性,分别对串行、并行、混合结构任务调度模型进行任务调度研究,根据有限资源成本将关键路径中任务节点融合,提出一种实用的启发式近似最优调度方法。实验结果表明,所提调度方法能够以最短的执行时间在有限的资源成本下完成最优的任务分配。     

改进蚁群算法的云计算任务调度方法

针对蚁群算法在云计算任务调度问题求解过程存在的不足,以找到最佳的云计算任务调度方案为目标,提出了一种基于改进蚁群算法的云计算任务调度方法.首先对当前云计算任务调度研究现状进行分析,并对问题进行了具体描述,然后采用蚁群算法对云计算任务调度问题进行求解,并针对标准蚁群算法缺陷进行改进,最后在CloudSim平台对该方法的性能进行测试.结果表明,改进蚁群算法可以找到较好的云计算任务问题调度方案,加快云计算任务完成速度,具有一定的实际应用价值.     

云环境下周期和非周期混合实时任务双容错调度算法

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

Efficient task scheduling for budget constrained parallel applications on heterogeneous cloud computing systems

As the cost-driven public cloud services emerge, budget constraint is one of the primary design issues in large-scale scientific applications executed on heterogeneous cloud computing systems. Minimizing the schedule length while satisfying the budget constraint of an application is one of the most important quality of service requirements for cloud providers. A directed acyclic graph (DAG) can be used to describe an application consisted of multiple tasks with precedence constrains. Previous DAG scheduling methods tried to presuppose the minimum cost assignment for each task to minimize the schedule length of budget constrained applications on heterogeneous cloud computing systems. However, our analysis revealed that the preassignment of tasks with the minimum cost does not necessarily lead to the minimization of the schedule length. In this study, we propose an efficient algorithm of minimizing the schedule length using the budget level (MSLBL) to select processors for satisfying the budget constraint and minimizing the schedule length of an application. Such problem is decomposed into two sub-problems, namely, satisfying the budget constraint and minimizing the schedule length. The first sub-problem is solved by transferring the budget constraint of the application to that of each task, and the second sub-problem is solved by heuristically scheduling each task with low-time complexity. Experimental results on several real parallel applications validate that the proposed MSLBL algorithm can obtain shorter schedule lengths while satisfying the budget constraint of an application than existing methods in various situations.     

基于改进GA的云计算任务调度算法

云计算通常需要处理大量的计算任务,任务调度策略在决定云计算效率方面起着关键作用。如何合理地分配计算资源,有效地调度任务运行,使所有任务运行完成所需的时间较短、成本较小是个重要的问题。提出一种考虑时间-成本约束的遗传算法(TCGA),通过此算法调度产生的结果不仅能使任务完成所需的时间较短,而且成本较小。通过实验,将TCGA与考虑时间约束的遗传算法(TGA)、考虑成本约束的遗传算法(CGA)进行比较,实验结果表明,该算法是云计算中一种有效的任务调度算法。     

异构集群下的任务调度算法研究

针对异构集群下高效节能的任务调度算法进行了研究, 提出了一种基于复制的任务调度算法, 在任务初始分配的基础上, 分别从能源感知和性能—能源平衡两个角度考虑任务的复制。建立了由计算和通信造成的能源消耗的数学模型, 并进行了大量的实验。实验结果表明, 与已有的BEATA算法相比, 该算法能明显地减少异构集群处理并行应用的调度长度和能耗。分析结果发现, 任务复制的方法在减少调度长度的同时会增加相应的能耗, 能同比优化调度长度和能耗的任务调度方法是今后的研究方向。     

某演练评估系统中云计算任务调度研究

研究合同战术演练评估系统应用中的云计算任务调度问题。针对目前的云计算调度算法研究大都是基于通用性或者商业需求,对军事应用特点考虑不多,应用到合同战术演练评估系统中无法满足系统对于调度实时性等性能的要求的问题,通过分析云计算的任务调度特点,引入数据存储节点优先和节点效能的概念提出了一种改进的基于负载均衡的任务调度算法,算法减少了数据存取时间并采用节点效能的概念能更准确地描述主机性能。仿真结果验证了改进后的算法在任务数量增大时任务执行的速度有所提升,能更好地满足合同战术演练评估系统复杂度和规模增大对实时性的需求。     

基于动态关键任务的多处理器任务分配算法

多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要点,调度过程中动态计算任务时间参数,准确确定处理器的关键任务,以关键任务为核心优化调度,逐步改善调度结果,最终取得最优的调度结果.分析和实验证明,DCT算法优于现有其它同类算法.