附加信息对负载可任意划分应用调度的影响

研究需要附加信息的可任意划分应用的调度问题.文章首先引入附加信息的概念,扩展了DLS模型,在此基础上重新分析了在这类应用中经典的平均划分(EQS)算法的缺陷,并提出了一个无空闲时间调度算法(NIS).基于这两个算法的解析表达解,严格地证明了NIS算法的调度性能总是优于EQS算法.由于在这类应用中典型的情况是每个处理器需要相同的附加信息,文章进一步研究了这类典型应用.分析表明,与EQS算法相比有更大范围的应用能利用NIS算法获得并行计算的收益,NIS算法所能利用的资源也更多.     

有控制信息的三阶段负载可任意划分应用的调度

文章研究需要控制信息的负载可任意划分应用的调度问题.控制信息是除了要处理的负载之外为了完成计算所必须的辅助信息,它的规模往往是由应用的性质和要处理的负载量所共同决定的.文章通过形式化地定义控制信息而扩展了DLS模型,在此基础上分析了LIFO和FIFO调度策略,分别得到了它们的解析形式的调度方案.基于这些解析解,分析了控制信息对两种调度策略的影响,并在此基础上对它们的调度性能进行了严格的比较.分析结果表明,与没有控制信息的情况不同,在这个新的模型下FIFO策略总是优于LIFO策略.     

乐观策略下并行离散事件仿真动态负载划分优化算法

动态负载划分是提高并行离散事件仿真运行性能的有效途径之一.现有研究往往孤立地考虑计算负载平衡和通信负载优化,使得复杂应用背景下整体性能低下.论文综合考虑仿真模型计算负载和交互模式,提出了一个基于带权重无向图有限容量k划分问题的并行离散事件仿真负载划分模型,并配合一套通用的仿真运行性能度量方法,提出了一个基于顶点交换的启发式局部搜索近似划分算法,实现了在计算负载平衡的前提下系统通信负载最优化,其近似解与全局最优解比值不小于(1-1/|N|)(1-ε).实验证明了该动态负载划分算法的有效性和实用性.     

面向多媒体系统的负载均衡策略研究

随着多媒体应用的普及,面向多媒体应用的并行文件系统负载均衡策略的研究具有现实意义。本文根据视频点播等多媒体应用的特点,提出了面向多媒体应用的并行文件系统动态负载均衡策略,构建了该策略的均衡模型,提出了适于多媒体服务系统的动态调度算法,并对该算法进行了性能分析。最后建立了NFS文件系统负载均衡实验环境,测试了该策略的高效性,充分证明了所提出的面向多媒体应用的并行文件系统负载均衡策略的优势。     

一种支持容错的任务并行程序设计模型

任务并行程序设计模型已成为并行程序设计的主流,其通过发掘任务并行性来提高并行计算机的系统性能.提出一种支持容错的任务并行程序设计模型,将容错技术融入到任务并行程序设计模型中,在保证性能的同时提高系统可靠性.该模型以任务为调度、执行、错误检测与恢复的基本单位,在应用级实现容错支持.采用一种Buffer-Commit计算模型支持瞬时错误的检测与恢复;采用应用级无盘检查点实现节点故障类型永久错误的恢复;采用一种支持容错的工作窃取任务调度策略获得动态负载均衡.实验结果表明,该模型以较低的性能开销提供了对硬件错误的容错支持.     

多核机群主节点并发发送数据的可分负载调度

对于节点计算、通信与存储能力不同、节点由多个多核处理器(多个片上多处理器)组成且共享L3cache的机群系统,采取计算与传输重叠模式,提出了主节点以多进程方式并发发送数据给从节点的可分负载调度模型.该调度模型自适应节点具有不同的计算、通信和存储能力,动态计算、确定调度轮数和每轮调度分配给各从节点的负载块规模,以平衡各节点的计算负载、减少节点之间的通信开销,缩短任务调度长度.依据各节点中的L3cache,L2cache和L1cache的可用存储容量,提出了对节点主存中接收到的负载块进行多级缓存划分的数据分配方法,以确保分配给节点中各个多核处理器、各个内核的负载平衡.基于提出的多核机群节点间可分负载调度模型和节点内多级存储数据分配方法,设计实现了节点拥有多个多核处理器的异构机群上通信和存储高效的k-选择并行算法.在曙光TC5000A多核机群系统上,测试了主节点并行与串行发送数据给从节点的任务调度方式、各级缓存利用率、每个核心执行不同数目的线程对并行算法运行性能的影响.实验结果表明:基于主节点并发发送数据给从节点的调度模型设计的k-选择并行算法,其运行性能优于基于主节点串行发送数据给从节点的调度模型设计的k-选择并行算法;L3cache和L2cache利用率大小对算法运行性能影响较大;当L3cache,L2cache和L1cache利用率取其优化组合值、每个核心运行3个线程时,算法所需的运行时间最短.     

一种异构NOWs上负载均衡的适应式并行调度算法

分析了并行作业调度算法，针对异构工作站群机系统(Network of Workstations，NOWs)提出了一种负载均衡的适应式划分(Adaptive Partition，AP)策略的并行调度算法，它利用了短作业需求优先(Shortest Demand First，SDF)的策略，主要思想是让系统中所有作业尽可能均分同时结束，以达到均衡负载。实验结果证明该算法公平和高效。     

集群计算环境下基于复杂网络的社会学仿真负载划分优化算法

负载划分是决定集群计算环境下基于复杂网络的并行社会学仿真性能的核心因素之一.由于背景负载等因素的影响,集群系统中往往需要根据实际可用计算资源非均匀分配仿真任务,而现有针对无标度特性拓扑结构的并行仿真负载划分算法无法适应集群环境下计算负载非均匀划分的需求.针对这一问题,提出了一个基于集散节点聚合的负载划分算法,将集群计算...     

并行循环的乐观自调度模式

并行循环的自调度模式是研究以最小运行开销和最佳负载平衡将循环体分布到各处理器上做并行计算，早期的自调度模式基于悲观的思想，认为并行循环是非均匀分布的，因此为克服负载不平衡，循环体被分割成大量任务包，因而导致较大的调度开销，本文提出一类乐观自调度模式，假定循环是均匀分布的，按现有处理器数对循环做初始划分可取得较好的负载平衡，同时，乐观模式还提出克服初始划分不良引起负载不平衡的一种简单且有效的方法，模     

基于任务图的多处理器负载均衡调度算法

针对共享存储多处理机系统中各处理机负载不均衡的问题,提出一种新的任务调度算法--多重波前法.在任务图划分的基础上,采用分层调度方式对原波前法进行改进,通过对任务序列进行多重遍历和重组以降低各处理器的分配误差,利用循环调度算法提高任务调度结果的精度,并给出该算法的并行实现.实验结果证明,该算法具有较低的任务分配误差和较高...     

An energy‐aware scheduling algorithm for divisible loads in a bus network

The schedule of divisible loads is one of the most typical problems in the research and application of parallel and distributed systems. For these large‐scale systems, the energy consumption problem has drawn great attention in recent years because of falling hardware costs and the growing concern of energy costs. In computing‐intensive systems, energy is primarily consumed by CPUs, and dynamic voltage‐frequency scaling technology is capable of adjusting CPUs' speed as well as saving energy. In this paper, we focus on computing‐intensive applications and study the energy‐aware scheduling problem for divisible loads in a bus network. The energy‐speed model is introduced to characterize the problem based on dynamic voltage scaling, and the energy‐aware scheduling problem is analyzed in the application layer above the operating system. The problem can be formulated mathematically as a nonlinear programming problem, and the solution is achieved using the Lagrange multiplier method under Kuhn–Tucker conditions. Based on the analytical results, an energy‐aware scheduling scheme called ENERG for divisible loads is presented. Finally, the energy‐aware scheme is compared with two other schemes to show the effectiveness and efficiency of the energy savings of our algorithm. Additionally, the experimental results illustrate the influence of network transmission delay on energy consumption. Copyright © 2015 John Wiley & Sons, Ltd.     

Real-time scheduling of divisible loads in cluster computing environments

Cluster computing has become an important paradigm for solving large-scale problems. To enhance the quality of service (QoS) and provide performance guarantees in a cluster computing environment, various real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent tasks represent many real-world applications. However, the problem of providing performance guarantees to divisible load applications has only recently been studied systematically. In this work, three important and necessary design decisions, (1) workload partitioning, (2) node assignment, and (3) task execution order, are identified for real-time divisible load scheduling. A scheduling framework that can configure different policies for each of the three design decisions is proposed and used to generate various algorithms. This paper systematically studies these algorithms and identifies scenarios where the choices of design parameters have significant effects.     

Requirement-aware strategies for scheduling real-time divisible loads on clusters

This paper investigates the real-time scheduling problem for handling heterogeneous divisible loads on cluster systems. Divisible load applications occur in many fields of science and engineering. Such applications can be easily parallelized in a master–worker fashion, but pose several scheduling challenges. We consider divisible loads associated with deadlines to enhance quality-of-service (QoS) and provide performance guarantees in distributed computing environments. In addition, since the divisible loads to be performed may widely vary in terms of their required hardware and software, we capture the loads’ various processing requirements in our load distribution strategies, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus in our problem formulation each load can only be processed by certain processors as both the loads and processors are heterogeneous. We propose scheduling algorithms referred to as Requirements-Aware Real-Time Scheduling (RARTS) algorithms, which consist of a novel scheduling policy, referred to as Minimum Slack Capacity First (MSCF), and two multi-round load distribution strategies, referred to as All Eligible Processors (AEP) and Least Capability First (LCF). We perform rigorous performance evaluation studies to quantify the performance of our strategies on a variety of scenarios.     

异构机群系统上带返回信息的可分负载多轮调度算法

针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题的求解在处理完任务后向中心处理机节点返回处理结果信息的情形,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出一种带返回结果信息的调度轮数可变的可分负载多轮调度算法.实验结果表明,该算法对于处理具有返回结果信息的应用的调度性能优于UMR可分负载多轮调度算法,并且可以获得近似最优的调度轮数.     

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

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

异构集群系统的可分负载多轮调度算法*

针对更实际的异构集群计算环境,充分考虑处理机具有不同的计算速度、通信能力和存储容量的特性,通过允许计算和通信操作重叠执行,采取多次并行分配计算任务的方法,设计一种可分负载多轮调度算法。实验结果表明,该算法不但能获得与均匀多轮调度(UMR)算法相当的渐近最优调度时间长度,并且能够处理更大规模的应用负载,实用性更强。     

Distributing and Scheduling Divisible Task on Parallel Communicating Processors

In this paper we propose a novel scheme for scheduling divisible task on parallel processors connected by system interconnection network with arbitrary topology,The divisible task is a computation that can be divided into arbitrary independent subtasks solved in parallel.Our model takes into consideration communication initial time and communication delays between processors.Moreover,by constructing the corresponding Network Spanning present the concept of Balanced Task Distribution Tree and use it to design the Equation Set Creation Algorithm in which the set of linear equations is created by traversing the NST in Post-order.After solving the created equations,we get the optimal task assignment scheme.Experiments confirm the applicability of our scheme in real-life situations.     

Multi-objective method for divisible load scheduling in multi-level tree network

There is extensive literature concerning the divisible load theory. Based on the divisible load theory (DLT) the load can be divided into some arbitrary independent parts, in which each part can be processed independently by a processor. The divisible load theory has also been examined on the processors that cheat the algorithm, i.e., the processors do not report their true computation rates. According to the literature, if the processors do not report their true computation rates, the divisible load scheduling model fails to achieve its optimal performance. This paper focuses on the divisible load scheduling, where the processors cheat the algorithm. In this paper, a multi-objective method for divisible load scheduling is proposed. The goal is to improve the performance of the divisible load scheduling when the processors cheat the algorithm. The proposed method has been examined on several function approximation problems. The experimental results indicate the proposed method has approximately 66% decrease in finish time in the best case.     

Bandwidth‐aware divisible task scheduling for cloud computing

Task scheduling is a fundamental issue in achieving high efficiency in cloud computing. However, it is a big challenge for efficient scheduling algorithm design and implementation (as general scheduling problem is NP‐complete). Most existing task‐scheduling methods of cloud computing only consider task resource requirements for CPU and memory, without considering bandwidth requirements. In order to obtain better performance, in this paper, we propose a bandwidth‐aware algorithm for divisible task scheduling in cloud‐computing environments. A nonlinear programming model for the divisible task‐scheduling problem under the bounded multi‐port model is presented. By solving this model, the optimized allocation scheme that determines proper number of tasks assigned to each virtual resource node is obtained. On the basis of the optimized allocation scheme, a heuristic algorithm for divisible load scheduling, called bandwidth‐aware task‐scheduling (BATS) algorithm, is proposed. The performance of algorithm is evaluated using CloudSim toolkit. Experimental result shows that, compared with the fair‐based task‐scheduling algorithm, the bandwidth‐only task‐scheduling algorithm, and the computation‐only task‐scheduling algorithm, the proposed algorithm (BATS) has better performance. Copyright © 2012 John Wiley & Sons, Ltd.