Negotiation-Based Scheduling of Scientific Grid Workflows Through Advance Reservations

In its broadest sense, scheduling of Grid applications can be viewed as a negotiation process between a scheduling service optimising user-centric objectives such as execution time, and a resource manager optimising provider-centric metrics such as resource utilisation or fairness. In this paper we enhance an existing list scheduling algorithm designed for minimising the workflow makespan with advance reservation-based negotiation functionality. As an instantiation of the new negotiation phase, we investigate two advance reservation functionality from the resource provider perspective: attentive and progressive. We illustrate through real-world experiments a two-fold benefit of our approach: improved execution predictability from the user’s perspective, and higher resource utilisation fairness through a new progressive allocation strategy from the provider’s perspective.     

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。     

基于经济模型的资源代理

网格计算是为解决大规模资源密集型问题而提出的新一代计算平台,是当前并行和分布处理技术的一个发展方向,而资源管理是计算网格的关键技术之一。对各种各样可利用资源的整合和管理是网格应用的基础,而资源的分布性、动态性、异构性、自治性和需要协调一致性使得网格资源的管理调度成为一个棘手的问题。目前基于市场的经济资源管理和调度算法非常适合计算网格中的资源管理问题,但有调度价格不能更改、负载平衡等问题。文中提出了“网格环境下基于经济模型的资源代理”,依靠多维QoS指导的调度策略和经济模型的启发式调节资源价格,改进和优化计算网格资源的分配。     

Communication infrastructure in distributed scheduling

The emergence of distributed artificial intelligent (DAI) introduced a new approach to solve scheduling problems by a set of scheduling systems that interact with each other in the problem-solving process. In this paper, we describe a communication infrastructure to handle connection and communication between distributed Internet scheduling systems for distributed applications. First, we present an agent model of distributed scheduling systems where agents can communicate and coordinate activities with each other via an agent communication language. Then, we define the syntax and semantics for the agent communication languages, and negotiation mechanism. Following that, we discuss the design and development of the prototype for the multi-agent scheduling systems. We conclude with a discussion of communication issues for heterogeneous agent-based scheduling systems to solve distributed scheduling problems.     

分布事务处理中的资源管理

1 引言在分布事务处理环境中,资源管理器(数据库管理系统,可靠消息队列以及事务性文件系统等是最常见的资源管理器)扮演着数据管理的核心作用,因此,分布事务处理中的资源管理的研究显得极为重要。     

An Approach to Quality of Service Management in Distributed Multimedia Application: Design and an Implementation

Most work related to quality of service (QoS) is concerned with individual system components, such as the operating system or the network. However, to support distributed multimedia applications, the entire distributed system must participate in providing the guaranteed performance levels. In recognition of this, a number of QoS architectures have been proposed to provide QoS guarantees. The mechanisms and schemes proposed by those architectures are used in a rather static manner since the involved entities, e.g., the network, sender and receiver, are known before the connection (call) set-up phase. In contrast to these architectures, we propose a general QoS management framework which supports the dynamic choice of a configuration of system components to support the QoS requirements for the user of a specific application. We consider different possible system configurations and select the most appropriate one depending on the desired QoS and the available resources. In this paper we present an overview of this general framework; especially, we concentrate on QoS negotiation and adaptation mechanisms. To show the feasibility of this approach, we designed and implemented a QoS manager for distributed multimedia presentational applications, such as news-on-demand. The negotiation and adaptation mechanisms which are supported by the QoS manager are specializations of the general framework. The proposed framework allows to improve the utilization of system resources, and thus to increase the system availability; it also allows to recover automatically, if this is possible, from QoS degradations. Furthermore, it provides the flexibility to incorporate different resource reservation schemes and scheduling policies, and to accommodate new system component technologies.     

一种无抖动的分布式多媒体任务调度算法

在分布式多媒体系统中,资源的管理和分配算法是保证应用的服务质量（ＱｏＳ）的关键问题,而资源管理中,ＱｏＳ协商和确认都和多媒体任务调芳算法有关,任务调度算法是资源管理的重要内容。现有的调度算法ＥＤＦ,ＲＭ,ＤＳｒ适用在分布式多媒体系统中,有局限性。本文基于风车调度模型,提出了一种无抖动调度的逐步消除候选项的并行算法ＤＭＳｒ,能达到分布系统中多媒体任务周期调度的无抖动特点,并讨论了算法的计算复杂度,证     

Toward High-Performance Delta-Based Iterative Processing with a Group-Based Approach

Many systems have been built to employ the delta-based iterative execution model to support iterative algorithms on distributed platforms by exploiting the sparse computational dependencies between data items of these iterative algorithms in a synchronous or asynchronous approach. However, for large-scale iterative algorithms, existing synchronous solutions suffer from slow convergence speed and load imbalance, because of the strict barrier between iterations; while existing asynchronous approaches induce excessive redundant communication and computation cost as a result of being barrier-free. In view of the performance trade-off between these two approaches, this paper designs an efficient execution manager, called Aiter-R, which can be integrated into existing delta-based iterative processing systems to efficiently support the execution of delta-based iterative algorithms, by using our proposed group-based iterative execution approach. It can efficiently and correctly explore the middle ground of the two extremes. A heuristic scheduling algorithm is further proposed to allow an iterative algorithm to adaptively choose its trade-off point so as to achieve the maximum efficiency. Experimental results show that Aiter-R strikes a good balance between the synchronous and asynchronous policies and outperforms state-of-the-art solutions. It reduces the execution time by up to 54.1% and 84.6% in comparison with existing asynchronous and the synchronous models, respectively.

     

Online execution time prediction for computationally intensive applications with periodic progress updates

The effectiveness of distributed execution of computationally intensive applications (jobs) largely depends on the quality of the applied scheduling approach. However, most of the existing non-trivial scheduling algorithms rely on prior knowledge or on prediction of application parameters, such as execution time, size of input and output, dependencies, etc., to assign applications to the available computational resources. A major issue is that these parameters are hard to determine in advance, especially if the end user does not possess an extensive history of previous application runs. In this work we propose an online method for execution time prediction of applications, for which execution progress can be collected at run-time. Using dynamic progress information, the total job execution time can be predicted using extrapolation. However, the predictions achieved by extrapolation are far from precise and often vary over time as a result of changing application dynamics and varying resource load. Therefore, to compute the actual job execution time we match a number of predefined prediction evolution models against the consecutive extrapolations, by adopting nonlinear curve-fitting. The ??best-fit?? coefficients allow for more accurate execution time prediction. The predictions made are used to enhance a dynamic scheduling algorithm for workflows introduced in our earlier work. The scheduling algorithm is run with and without curve-fitting, showing a performance improvement of up to 15% in the former case.     

基于计算经济的网格资源管理研究

网格是为解决大规模资源密集型问题而提出的新一代计算平台,资源管理是网格的关键技术之一。但是,资源的分布性、异构性、自治性、动态性等使得网格资源的管理变得异常复杂。目前,基于市场的经济资源管理和调度算法非常适合解决网格中的资源管理问题。本文提出了网格环境下基于经济模型的各种代理,给出了一种新的资源管理模型
型,并定义了效用函数,给出了基于效用最优的资源调度算法。为解决网格资源管理的问题提供了一个有效的途径。     

Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism

The resource scheduling problem in a multi-project environment extends job-shop scheduling problems by allowing for task dependency and multiple self-interested entities. In this paper we deal with short-term scheduling of resources, which are shared by multiple projects. In specific, we address the dynamic nature of the situation. We model this as a dynamic economy, where the multiple local markets are established and cleared over time, trading resource time slots (goods). Due to the dynamic and distributed nature of the economy, through our approach we can achieve higher levels of flexibility, scalability and adaptability. Unlike most market-based mechanisms, which are based on equilibrium concepts and iterative adjustment of resources prices, we propose a novel market mechanism called precedence cost tâtonnement (P-TâTO), which solves individual resource-constrained local resource scheduling in an optimal way, and searches for a precedence conflict-free schedule through a tâtonnement type procedure. In this paper, we discuss our dynamic economy model and some details of the market mechanism along with empirical analysis results.     

基于模糊认知图的动态网格分布式资源调度

论文利用多代理的理论,通过网格节点自主选择任务来实现网格系统中的资源优化调度。由于各节点的自主性,对于任务分配方案将存在不同的支持度。论文采用模糊认知图,建立了对任务分配方案的支持度的协调控制策略,并在此基础上给出了一种智能的网格资源调度策略。考虑到各个网格节点的资源配置各不相同,提出了标准支持度的概念,保证了支持度协调策略的可行性和有效性。该调度策略无需存在处于上层的资源调度单元,各节点通过协调对任务分配方案的标准支持度即可实现网格资源的优化调度。该策略适用于分布式计算,并支持网格节点的动态变化,具有较好的实时性和鲁棒性。     

The Prospero Resource Manager: A scalable framework for processor allocation in distributed systems

Existing techniques for allocating processors in parallel and distributed systems are not suitable for use in large distributed systems. In such systems, dedicated multiprocessors should exist as an integral component of the distributed system, and idle processors should be available to applications that need them. The Prospero Resource Manager (PRM) is a scalable resource allocation system that supports the allocation of processing resources in large networks and on multiprocessor systems. PRM employs three types of managers-the job manager, the system manager and the node manager-to manage resources in a distributed system. Multiple independent instances of each type of manager exist, reducing bottlenecks. When making scheduling decisions each manager utilizes information most closely associated with the entities for which it is responsible.     

基于接纳控制和ILP资源调度模型的BDAaaS系统架构

为了使云计算平台为大数据分析提供有效支持,提出一种大数据分析即服务(BDAaaS)的系统架构;首先,当用户向系统提交大数据分析应用(BDAA)时,通过接纳控制器评估任务的执行时间和成本并作出接纳决策;然后,通过服务等级协议(SLA)管理器根据任务的服务质量(QoS)需求制定SLA;最后,利用提出的整数线性规划(ILP)资源调度模型,以最小化执行成本为目标,在满足SLA下合理调度资源来执行任务;仿真结果表明,提出的方案能够有效降低任务执行时间,具有有效性和可行性。     

Semantic-enabled CARE Resource Broker (SeCRB) for managing grid and cloud environment

Grid computing is mainly helpful for executing high-performance computing applications. However, conventional grid resources sometimes fail to offer a dynamic application execution environment and this increases the rate at which the job requests of users are rejected. Integrating emerging virtualization technologies in grid and cloud computing facilitates the provision of dynamic virtual resources in the required execution environment. Resource brokers play a significant role in managing grid and cloud resources as well as identifying potential resources that satisfy users’ application requests. This research paper proposes a semantic-enabled CARE Resource Broker (SeCRB) that provides a common framework to describe grid and cloud resources, and to discover them in an intelligent manner by considering software, hardware and quality of service (QoS) requirements. The proposed semantic resource discovery mechanism classifies the resources into three categories viz., exact, high-similarity subsume and high-similarity plug-in regions. To achieve the necessary user QoS requirements, we have included a service level agreement (SLA) negotiation mechanism that pairs users’ QoS requirements with matching resources to guarantee the execution of applications, and to achieve the desired QoS of users. Finally, we have implemented the QoS-based resource scheduling mechanism that selects the resources from the SLA negotiation accepted list in an optimal manner. The proposed work is simulated and evaluated by submitting real-world bio-informatics and image processing application for various test cases. The result of the experiment shows that for jobs submitted to the resource broker, job rejection rate is reduced while job success and scheduling rates are increased, thus making the resource management system more efficient.     

A computational economy for grid computing and its implementation in the Nimrod-G resource broker

Computational grids that couple geographically distributed resources such as PCs, workstations, clusters, and scientific instruments, have emerged as a next generation computing platform for solving large-scale problems in science, engineering, and commerce. However, application development, resource management, and scheduling in these environments continue to be a complex undertaking. In this article, we discuss our efforts in developing a resource management system for scheduling computations on resources distributed across the world with varying quality of service (QoS). Our service-oriented grid computing system called Nimrod-G manages all operations associated with remote execution including resource discovery, trading, scheduling based on economic principles and a user-defined QoS requirement. The Nimrod-G resource broker is implemented by leveraging existing technologies such as Globus, and provides new services that are essential for constructing industrial-strength grids. We present the results of experiments using the Nimrod-G resource broker for scheduling parametric computations on the World Wide Grid (WWG) resources that span five continents.     

An agent-oriented approach to resolve scheduling optimization in intelligent manufacturing

Agent technology is considered as a promising approach for developing optimizing process plans in intelligent manufacturing. As a bridge between computer aided design (CAD) and computer aided manufacturing (CAM), the computer aided scheduling optimization (CASO) plays an important role in the computer integrated manufacturing (CIM) environment. In order to develop a multi-agent-based scheduling system for intelligent manufacturing, it is necessary to build various functional agents for all the resources and an agent manager to improve the scheduling agility. Identifying the shortcomings of traditional scheduling algorithm in intelligent manufacturing, the architecture of intelligent manufacturing system based on multi-agent is put forward, among which agent represents the basic processing entity. Multi-agent-based scheduling is a new intelligent scheduling method based on the theories of multi-agent system (MAS) and distributed artificial intelligence (DAI). It views intelligent manufacturing as composed of a set of intelligent agents, who are responsible for one or more activities and interacting with other related agents in planning and executing their responsibilities. In this paper, the proposed architecture consists of various autonomous agents that are capable of communicating with each other and making decisions based on their knowledge. The architecture of intelligent manufacturing, the scheduling optimization algorithm, the negotiation processes and protocols among the agents are described in detail. A prototype system is built and validated in an illustrative example, which demonstrates the feasibility of the proposed approach. The experiments prove that the implementation of multi-agent technology in intelligent manufacturing system makes the operations much more flexible, economical and energy efficient.     

面向建材装备集团制造的分布式多项目资源调度

针对建材装备集团项目执行过程中存在的项目内和项目间多类别资源协同共用现象,提出并行调度机制下考虑多类别资源转移时间和转移成本的分布式多项目资源调度问题,以最小化资源转移成本和项目执行工期为目标建立问题的数学模型.为改善进化算法在局部搜索能力方面的不足,提出将禁忌搜索与进化算法相结合,构造一种内嵌禁忌搜索寻优搜索的多目标混合进化算法,在保证算法全局搜索能力的前提下提升局部精确搜索能力.同时,考虑资源转移成本和时间对任务选取的影响,改进任务选择的优先权值,提出并行调度机制下资源转移冲突消解策略.数据实验表明,所提算法能够有效避免不合理的资源转移,在求解质量方面具有良好的性能.     

Distributed scheduling with probabilistic and fuzzy classifications of processes

The classification of various types of processes is an important factor in large-scale distributed systems such as, grid and cloud platforms. Moreover, the coordination and control of distributed processes are research challenges in presence of unpredictable network partitioning and distributed semaphores. The process classification is important in order to allocate and schedule distributed processes enhancing overall resource utilization and throughput. The schedulers employ patterns of resource affinities of concurrent processes in order to make scheduling decisions affecting overall resource utilization in a system, where resource affinity patterns of a process may not be static. This paper proposes an estimation model and a classifier algorithm to queuing processes based on respective resource affinities. The kernel-level software architecture is designed to control scheduling of distributed processes based on classification for enhanced throughput. The classifier algorithm tracks the resource affinities of processes based on execution traces and the control algorithm performs process scheduling. Experimental results indicate that the classifier algorithm successfully manages process queues based on resource affinities of processes and, the control algorithm successfully monitors scheduler activation for a set of processes.     

基于Agent的组合构件服务工作容错研究

组合构件服务是将分布在 Internet上构件提供的服务进行链接 ,形成具有新功能构件服务的分布式网络计算技术。本文在分析了基于 agent的构件服务工作模式及构件服务组合方式可能产生的工作失败的若干情形的基础上 ,给出了构件服务工作的结构失效和源失效的概念。针对组合构件服务由于源失效可能引发的的执行失败 ,提出了局部容错的方法来解决完全备份容错导致的执行代价太高的问题 ;为了保证组合构件服务最大限度的稳定运行 ,提出利用基于 agent的服务发现和服务协商来实现执行容错。最后给出了在集中式调度模式和分布式调度模式下的基于 agent技术的组合构件服务执行容错调度算法。