Cooperative scheduling mechanism for large-scale peer-to-peer computing systems

Over recent years, peer-to-peer (P2P) systems have become an important part of Internet. Millions of users have been attracted to their structures and services. P2P computing is a distributed computing paradigm that uses Internet to connect thousands, or even millions, of users into a single large virtual computer based on the sharing of computational resources. One of the most critical aspects to the design of P2P computing systems is the development of scheduling techniques to manage the computational resources efficiently and in a scalable way. This paper proposes a cooperative scheduling mechanism with a two-level topology designed to work on large-scale distributed computing P2P systems. Our main contribution is proposing three criteria that only use local information to schedule tasks thus providing scalability to the overall scheduling system. By setting up these three criteria, the system can be easily adapted to work efficiently with very different kinds of distributed applications. The extensive experimentation carried out justifies the importance of good scheduling in such heterogeneous systems, but also emphasizes the importance of having a scheduling algorithm capable of being adapted to the requirements of different kinds of application.     

树型网格平台上任务重分配调度改进算法*

应用线性规划方法对树型异构网格平台上任务调度重分配问题进行建模,证明了树型异构网格平台上任务调度重分配机制,并提出改进后的树型网格平台上任务重分配调度算法。该算法的思想是在子树内完成任务重分配后,要将该子树内多余的任务都传输到该子树的根节点。通过对算法进行模拟实验表明,在给定时间内,该改进算法所能调度的最大任务数优于现有算法。     

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

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

云计算下负载均衡的多维QoS约束任务调度机制

高效的任务调度机制能够更好地满足用户的QoS需求,实现各物理主机间的负载均衡,从而提高云计算环境的整体性能。而传统的任务调度往往只考虑任务的响应时间或安全性等,且负载均衡策略是静态的。根据云计算的弹性化和虚拟化等新特性,综合考虑任务的性能QoS和信任QoS,提出一种在云计算环境下的任务调度机制,采用虚拟机迁移技术实现动态负载均衡。通过在CloudSim2.1仿真环境下的分析和比较,该任务调度机制不但可以提高用户满意度,而且可以有效实现负载均衡。     

Dynamic scheduling model of computing resource based on MAS cooperation mechanism

Allocation of grid resources aims at improving resource utility and grid application performance. Currently, the algorithms proposed for this purpose do not fit well the autonomic, dynamic, distributive and heterogeneous features of the grid environment. According to MAS (multi-agent system) cooperation mechanism and market bidding game rules, a model of allocating allocation of grid resources based on market economy is introduced to reveal the relationship between supply and demand. This model can make good use of the studying and negotiating ability of consumers’ agent and takes full consideration of the consumer’s behavior, thus rendering the application and allocation of resource of the consumers rational and valid. In the meantime, the utility function of consumer is given; the existence and the uniqueness of Nash equilibrium point in the resource allocation game and the Nash equilibrium solution are discussed. A dynamic game algorithm of allocating grid resources is designed. Experimental results demonstrate that this algorithm diminishes effectively the unnecessary latency, improves significantly the smoothness of response time, the ratio of throughput and resource utility, thus rendering the supply and demand of the whole grid resource reasonable and the overall grid load balanceable. Supported by the Natural Science Foundation of Hunan Province (Grant No. 06JJ2033), and the Society Science Foundation of Hunan Province (Grant No. 07YBB239)     

一种针对异构计算平台的编译期优化方法

针对OpenCL(open computing language)编译时期的特有模式, 提出了一种新的针对异构计算平台的编译期优化方法。该方法根据设备端和主机端的各自特点, 将设备端的一些冗余操作提到主机端或者新的设备端kernel中去执行, 以达到降低存储器读写的目的。这种方法充分利用了异构计算平台的特点, 较传统优化方法相对灵活。大多数情况下能有效提高OpenCL的运行速度, 测试用例中在应用原有编译器优化的基础上最快提高了270%。     

边缘计算开源平台综述

首先介绍了边缘计算(EC)的基本概念和研究现状,并从多视角讨论了边缘计算平台的设计要求;接着聚焦到4个典型的开源平台,并从应用领域、部署方式等方面比较了它们之间的异同点;随后选取了两个典型的应用案例,分别针对它们的优势、搭建进行了概述和分析;最后对边缘计算平台之间的合作、安全、标准化等问题进行了归纳和展望.     

网格计算中基于信任机制的层次任务调度模型

提出了一种分布式层次任务调度模型,该模型将任务调度分两层进行,并且将信任机制引入其中以提高网格的服务质量及运行效率。提出了适应该模型的调度算法,算法同时考虑了网格实体间的信任关系、预测执行时间、QoS需求和价格因素,并动态调整它们在交易中所占的比重,从而较好地适应不同用户的需求。分析和仿真表明,该调度模型增强了网格环境的安全性和适用性,提高了执行效率,并降低了交易失败率。     

On scheduling dag s for volatile computing platforms: Area-maximizing schedules

Many modern computing platforms—notably clouds and desktop grids—exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a new quality metric, area, for schedules that execute computations having interdependent constituent chores (jobs, tasks, etc.) on such platforms. Area measures the average number of tasks that a schedule renders eligible for execution at each step of a computation. Even though the definition of area does not mention and properties of host platforms (such as volatility), intuition suggests that rendering tasks eligible at a faster rate will have a benign impact on the performance of volatile platforms—and we report on simulation experiments that support this intuition. We derive the basic properties of the area metric and show how to efficiently craft area-maximizing (A-M) schedules for several classes of significant computations. Simulations that compare A-M scheduling against heuristics ranging from lightweight ones (e.g., FIFO) to computationally intensive ones suggest that A-M schedules complete computations on volatile heterogeneous platforms faster than their competition, by percentages that vary with computation structure and platform behavior—but are often in the double digits.     

Workload assignment for global real-time scheduling on unrelated clustered platforms

Real-Time Systems - Heterogeneous MPSoCs are being used more and more, from cellphones to critical embedded systems. Most of those systems offer heterogeneous sets of identical cores. In this...     

Iterative list scheduling for heterogeneous computing

Optimal scheduling of parallel applications on distributed computing systems represented by directed acyclic graph (DAG) is NP-complete in the general case. List scheduling is a very popular heuristic method for DAG-based scheduling. However, it is more suited to homogenous distributed computing systems. This paper presents an iterative list scheduling algorithm to deal with scheduling on heterogeneous computing systems. The main idea in this iterative scheduling algorithm is to improve the quality of the schedule in an iterative manner using results from previous iterations. The algorithm first uses the heterogeneous earliest-finish-time (HEFT) algorithm to find an initial schedule and iteratively improves it. Hence the algorithm can potentially produce shorter schedule length. The simulation results show that in the majority of the cases, there is significant improvement to the initial schedule. The algorithm is also found to perform best when the tasks to processors ratio is large.     

Mechanisms for building autonomically scalable services on cooperatively shared computing platforms

We present here a system architecture and its underlying mechanisms for building autonomically scalable and resilient services on cooperatively shared computing platforms. Specifically, our focus is on utilizing computing platforms exhibiting the following characteristics. The resources at a node in such platforms are allocated to competing users on fair‐share basis, without any reserved resource capacities for any user. There is no platform‐wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Moreover, a node can become unavailable at any time due to crashes or shutdowns. Building scalable services in such environments poses unique challenges due to node‐level fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. We present here models for estimating the service capacity at a node under fluctuating operating conditions. Furthermore, we develop adaptive and agile load distribution mechanisms for distributing load among replicas based on their time‐varying service capacities. We present the results of our evaluations of these mechanisms on PlanetLab, which exemplifies the platform level characteristics considered here.Copyright © 2013 John Wiley & Sons, Ltd.     

一种多处理器平台上的传感器事务调度算法

如何有效地调度传感器事务以维护数据的时态一致性是信息物理融合系统研究中的一个重要问题。已有的调度算法基本上都是针对单处理器平台来设计的。提出一种多处理器平台上的传感器事务调度算法,算法通过合理地分配和调整事务实例执行所需处理器资源来保证数据的时态一致性约束,通过预先计算出全局重复调度序列来降低运行开销,给出了算法的可调度性分析。实验结果表明,该算法具有较高的调度成功率,其产生的更新负载也较低。     

自愿计算环境下基于代理的自适应并行调度

描述了一个自愿计算环境下的基于代理的自适应并行调度模型,该调度代理处于服务器端与工作机端之间,可以缓解服务器端的访问竞争.在该调度模型中,服务器端直接把工作单元分配给调度代理,工作机从调度代理处获取工作单元;调度代理具有自适应并行性,高效率性,容错等特性.最后通过测试与性能分析验证了该调度模型的正确性与高效性.     

Dynamic scheduling techniques for heterogeneous computing systems

There has been a recent increase of interest in heterogeneous computing systems, due partly to the fact that a single parallel architecture may not be adequate for exploiting all of a program's available parallelism. In some cases, heterogeneous systems have been shown to produce higher performance for lower cost than a single large machine. However, there has been only limited work on developing techniques and frameworks for partitioning and scheduling applications across the components of a heterogeneous system. In this paper we propose a general model for describing and evaluating heterogeneous systems that considers the degree of uniformity in the processing elements and the communication channels as a measure of the heterogeneity in the system. We also propose a class of dynamic scheduling algorithms for a heterogeneous computing system interconnected with an arbitrary communication network. These algorithms execute a novel optimization technique to dynamically compute schedules based on the potentially non-uniform computation and communication costs on the processors of a heterogeneous system. A unique aspect of these algorithms is that they easily adapt to different task granularities, to dynamically varying processor and system loads, and to systems with varying degrees of heterogeneity. Our simulations are designed to facilitate the evaluation of different scheduling algorithms under varying degrees of heterogeneity. The results show improved performance for our algorithms compared to the performance resulting from existing scheduling techniques.     

Robust task scheduling for volunteer computing systems

Performance perturbations are a natural phenomenon in volunteer computing systems. Scheduling parallel applications with precedence-constraints is emerging as a new challenge in these systems. In this paper, we propose two novel robust task scheduling heuristics, which identify best task-resource matches in terms of makespan and robustness. Our approach for both heuristics is based on a proactive reallocation (or schedule expansion) scheme enabling output schedules to tolerate a certain degree of performance degradation. Schedules are initially generated by focusing on their makespan. These schedules are scrutinized for possible rescheduling using additional volunteer computing resources to increase their robustness. Specifically, their robustness is improved by maximizing either the total allowable delay time or the minimum relative allowable delay time over all allocated volunteer resources. Allowable delay times may occur due to precedence constraints. In this paper, two proposed heuristics are evaluated with an extensive set of simulations. Based on simulation results, our approach significantly contributes to improving the robustness of the resulting schedules.     

面向互联网计算资源共享的自适应调度模型

在面向互联网的计算资源共享平台中,如何把服务器端的子任务均匀地调度给大规模互联网环境下的志愿机运算是一个重要的研究问题。描述了该平台下的一个自适应并行调度模型。调度器处于服务器端与志愿机之间,缓解服务器端的访问瓶颈;服务器端首先根据调度器的负载对子任务进行第一次分派,在调度器端根据下属的志愿机的软硬信息再分配子任务。通过运行典型的BanchMark并行程序,把该调度策略与其他策略进行比较,验证了该调度模型针对粗粒度并行的主从（Master-Slave）风格并行应用可以获得较好的性能。     

一种应用于网格计算环境的任务调度模式*

提出了一种新的网格任务调度模式,针对网格计算资源有组织、松耦合、自治等特性,建立基于多层次虚拟组织形式的计算资源模型;根据网格环境中应用任务粗粒度、特定资源依赖等特点,建立了网格任务的描述模型;提出并实现了相应的子任务生成算法、任务初始调度算法及自动调整算法。设计实现了能够支持仿真及实际网格计算环境可扩展网格任务调度器,通过理论分析和仿真实验对算法的正确性、效果和效率进行了评价。