基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图（DAG）的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行。OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本。Nimrod/G模型中提出基于时间和成本限制下的优化调度算法（DBC）考虑了时间和成本,但没考虑任务间的优先关系。本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法。通过仿真表明,相对OGS算法,该算法减少了所需成本。     

基于有向无环图的成本-时间优化调度算法

网格计算环境下,基于有向无环图(DAG)的成本-时间优化调度算法运用经济规律把网格用户的任务映射到网格资源中运行.OGS算法考虑了任务间的优先关系,使得任务完成时间最小,但没考虑到在网格环境中所需的成本.Nimrod/G模型中提出基于时间和成本限制下的优化调度算法(DBC)考虑了时间和成本,但没考虑任务问的优先关系.本文综合考虑了成本-时间因素以及任务间的优先关系,在不增加完成时间的基础上,把任务映射到价格便宜的机器上,提出了基于有向无环图的成本-时间优化调度算法.通过仿真表明,相对OGS算法,该算法减少了所需成本.     

网格原子化作业的二分图调度方法

对于网格系统中计算力调度等问题,结合有向无环作业图DATG和无向节点图UNG,采用并行集APS建立了一种基于二分图的网格调度算法BGS,并在惩罚策略、负载均衡、复活机制的引导下,使系统的调度动态地逐步趋向优化.实验结果表明:该算法能够更加适应网格资源的变化,降低作业负载,提高作业的并行化程度,并能根据系统负载合理地利用节点资源.     

一种用于网格任务调度的退火进化算法*

针对网格环境下具有约束关系的任务调度问题,基于有向无环图DAG（directed acyclic graph）设计了调度模型;提出了一种改进的退火进化算法,对任务的执行次序和资源的具体分配分离编码,给出适应度函数计算方法和算法步骤。最后将算法和传统的遗传算法比较,实验结果显示该算法能获得更好的调度结果。     

基于网格资源预测的任务优先级调度算法

根据网格工作流中任务的依赖关系和截止时间,以及资源的有效度和MIPS（每秒百万条指令）,提出基于网格资源预测的任务优先级调度算法。把网格任务工作流抽象为有向无环图,找到该工作流的关键路径,计算每个任务的最迟开始执行时间,作为任务的优先级。在算法中考虑用户的要求和资源的类型,以及任务调度失败后重新分配的问题。实验验证了该算法的有效性。     

网格任务调度方法研究

网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法（QGA）的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图（DAG）来描述子任务间的依赖关系,根据深度值来给子任务的执行顺序进行排序。仿真结果显示,无论是任务完成时间还是资源利用率,此方法都明显优于基于遗传算法（GA）的网格调度算法。     

网格环境中基于负载均衡的工作流调度算法

由于网格工作流任务之间存在时序和数据依赖等关系,使得网格环境中工作流的调度问题成为一个NP完全问题。针对有向无环图(DAG)类型工作流提出一种调度算法,先确定关键路径,从而优先调度关键路径成员节点,该算法追求在最优时间跨度下的系统均衡负载,最后通过实验验证了该算法的有效性。     

分布式系统下的DAG任务调度研究综述

近年来随着网格、云计算工作流等分布式计算技术的发展,关于DAG(有向无环图)模型任务在分布式系统环境下的调度问题逐渐成为备受关注的研究热点。根据最新研究进展,对分布式系统下的DAG任务调度问题和有关技术进行了研究与讨论,主要包括四个方面:系统地描述了分布式系统和异构分布式系统的有关概念,异构分布式系统下的DAG任务调度问题、调度模型及其典型应用;对现有分布式系统下DAG任务调度的研究按照不同的方式进行了分类;探讨了多DAG共享异构分布式资源调度的研究现状;讨论了目前多DAG共享异构分布式资源调度研究存在的问题和未来可能的研究方向。     

经济模式下基于有向无环图的优化调度算法设计

Buyya提出的费用-时间优化算法运用经济规律把网格用户的任务映射到网格资源,但没有考虑任务间的优先关系。本文综合考虑时间、费用以及任务间的优先关系等诸多QoS需求,提出了基于有向无环图的优化调度算法。通过仿真实例,论证了该算法的优越性。     

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

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

Parallel resource co-allocation for the computational grid

Resource co-allocation is one of the crucial problems affecting the utility of the grid. Because the numbers of the application tasks and amounts of required resources are enormous and quick responses to the requirements of users are necessary in the real grid environment, real-time resource co-allocation may be large-scale. A parallel resource co-allocation algorithm based on the framework for mapping with resource co-allocation is proposed in this paper. Through the result of experiments, it is concluded that the parallel method reduces the execution time of the resource co-allocation algorithm significantly, and makes the overall response time to the end-users small.     

元计算系统的一个可扩展层次型资源管理模型

资源管理是元计算系统中的关键问题，为了支持大规模元计算应用，必须有效地解决资源联合分配问题。提出了一种可扩展层次型资源管理模型，在充分利用已有的批处理调度系统的基础上，通过核心资源管理器与局域资源调度系统的交互，为异构资源提供统一的接口，为解决资源的联合分配问题，提出了基于站点的层次型管理机制，可将应用程序的资源请求分布在相对紧密的资源集合上，不仅减小了元计算应用程序的整体通信开销，而且计算提供了资源预约服务。     

具有QoS保证的服务资源联合分配与管理

提出一种具有QoS保证的资源管理系统架构,理论分析表明,该系统架构能够较好地适应资源的动态性;其次将服务资源联合分配问题归化为MMKP(multiple-choice multiple-dimension knapsack problem)问题,并提出两种资源联合分配算法:最优解算法RA_BBLP和启发式算法RA_MHEU,实验结果表明,RA_BBLP保证求得最优解,可作为其他算法的参照系,而RA_MHEU收敛速度极快且所求出的解集接近最优,是一种理想的资源联合分配 算法.     

An Improved Protocol for Deadlock and Livelock Avoidance Resource Co-allocation in Network Computing

A multitude of applications require simultaneous access to multiple kinds of resources scatted in distributed sites. This problem is known as resource co-allocation which has evolved as a hot topic in network computing. How to design a kind of high-performance protocol for deadlock and livelock avoidance resource co-allocation becomes a challenging problem. In this paper, we propose a new protocol OODP³ (Optimal ODP³) which is based on the currently popular protocol ODP³ (Order-based Deadlock Prevention Protocol with Parallel requests).OODP³ not only inherits the advantage of ODP³ but also guarantees the fulfillment of resource co-allocation within polynomial time. Theoretical proof is conducted to verify the correctness of OODP³. Experimental results also show that OODP³ achieves the better performance improvements than the existing deadlock and livelock avoidance protocol.     

多用户分布式MIMO-OFDM系统的多维资源分配算法

针对多用户分布式MIMO-OFDM系统中的资源分配问题,结合分布式架构特点,提出了一种基于分级优化的天线、子载波与功率联合分配算法.该算法将三维的资源联合分配问题分级转换为两次二维资源联合分配问题,即先引入端口并行处理机制,完成天线与子载波的分配,形成"用户-子信道对",进而采用注水功率分配的方式,完成功率在"用户-子...     

Slot selection algorithms in distributed computing

In this work, we introduce slot selection and co-allocation algorithms for parallel jobs in distributed computing with non-dedicated and heterogeneous resources. A single slot is a time span that can be assigned to a task, which is a part of a job. The job launch requires a co-allocation of a specified number of slots starting synchronously. The challenge is that slots associated with different resources of distributed computational environments may have arbitrary start and finish points that do not match. Some existing algorithms assign a job to the first set of slots matching the resource request without any optimization (the first fit type), while other algorithms are based on an exhaustive search. In this paper, algorithms for effective slot selection of linear complexity on an available slots number are studied and compared with known approaches. The novelty of the proposed approach consists of allocating alternative sets of slots. It provides possibilities to optimize job scheduling.     

The DataGrid Workload Management System: Challenges and Results

The workload management task of the DataGrid project was mandated to define and implement a suitable architecture for distributed scheduling and resource management in a Grid environment. The result was the design and implementation of a Grid Workload Management System, a super-scheduler with the distinguishing property of being able to take data access requirements into account when scheduling jobs to the available Grid resources. Many novel issues in various fields were faced such as resource management, resource reservation and co-allocation, Grid accounting. In this paper, the architecture and the functionality provided by the DataGrid Workload Management System are presented.     

Supporting schedules of resource co-allocation for distributed computing in scalable systems

This paper proposes a model of scheduling and validates methods of resource co-allocation for distributed computations in scalable systems. Solution of the problem of allocating heterogeneous computing resources for performing complex sets of tasks (jobs) is related to the formation of strategies (families of admissible supporting schedules). The choice of a specific schedule depends on the nature of events occurring in the distributed environment and related primarily to the load and accessibility of computing nodes.     

Multilevel strategies of resource co-allocation in distributed computations with control periods

A scalable model and methods of resource co-allocation to organize data processing in distributed systems by families of basic plans—strategies—are proposed. The character of strategies is multilevel since they are designed for structurally different but functionally equivalent models of the same job which is a complex set of interrelated tasks. A concrete basic plan of computations is selected depending on time parameters of control events that occur in the system and are related first of all to the load and dynamics of the composition of heterogeneous computational nodes.