基于动态任务调度的STDS算法设计研究

任务调度是计算机多核处理器系统获得高性能的关键,而现有的多核任务调度算法研究,大多侧重于静态调度下的算法优化和负载均衡,对动态调度及动态负载均衡研究较少。针对动态调度,并结合异构多核的特点,提出一种基于核负载均衡的动态任务调度算法STDS。算法通过合理设定调度粒度,降低调度频率,从而减少调度消耗时间;根据异构多核处理器各核处理性能的差异,设置内核负载上下限值,控制内核负载保持在同一水平,以达到负载均衡效果。算法依据等待时间长短、任务间通信大小和内核负载轻重因素对任务进行实时调度,并可通过实时因子、负载因子等参数设置3种因素的影响比重,以满足系统的不同需求。仿真实验显示,在内核数目较多的系统中,STDS算法更加高效,在保证任务处理速度的同时有较好负载均衡。     

P2P分布实时数据交换的高可用混合负载均衡算法

负载分配是分布式系统的资源管理和任务调度的关键问题之一，本文在分析当前已有算法在负载的实时分配方面存在的问题基础上，提出了适用于P2P分布实时数据交换的高可用性混合负载均衡算法2PLB．该算法将处理结点的处理能力和网络流情况协同考虑，以一种静态负载均衡和动态负载均衡结合的自调节混合负载均衡算法实现用于实时任务调度和负载调节．相比单纯的静态负载均衡或者动态负载均衡算法，本文所提的算法避免了纯静态负载均衡算法在处理任务时不能满足可适应性问题，又克服了纯动态负载均衡在任务处理过程中由于维护动态负载状态和任务迁移而导致的计算复杂度等问题的缺点，所提算法对于大规模实时任务处理具有实时性强，易于调度，具有显著的可比性等特点，广域网络环境下的系统测试表明所提算法能够以对等模式提供高质量实时数据交换和共享服务．     

多处理器系统的在线节能调度算法

随着多处理器系统计算性能的提高,能耗管理已变得越来越重要,如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统,针对随机到达的任务,提出一种在线节能调度算法(OLEAS)。该算法在满足任务截止期限的前提下,尽量将任务调度到产生能耗最少的处理器,当某个任务在所有处理器上都不能满足截止期限要求时,则调整处理器之间的部分任务,使之尽量满足截止期限要求。同时,OLEAS尽量使单个处理器上的任务按平均电压/频率执行,以降低能耗,只有当新到任务不满足截止期限要求时,才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先(EFF)、最高电压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG)和最小能耗最小完成时间(ME-MC)的性能,结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势     

一种批优化调度策略的实时异构系统的集成动态调度算法

针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.     

一种基于实时负载的动态负载平衡策略

在分布式系统中采用动态负载平衡算法分配系统中的工作负载,能够提高系统的性能。在简述目前常用的几种动态负栽平衡策略的基础上,提出了一种基于实时负载的动态负载平衡策略,并给出了其调度算法。     

基于混合任务模型的动态电压调度在无线传感器网络中的应用

为了最大限度节约能量,延长无线传感器网络(WSN)的使用寿命,针对计算复杂度较高的WSN应用背景及其普遍存在的任务模式,提出一种相对更通用的、基于混合任务模型的动态电压调度算法(H-DVS)。H-DVS算法能在任务相对期限没有限制的情况下,与最早截止时间优先(EDF)调度算法结合,支持周期任务和零散任务同时存在的混合任务模型。H-DVS根据CPU的工作负载,由调频(FM)因子对CPU进行实时电压和频率调节,从而在降低能耗的同时保证任务的实时性要求。理论分析和仿真实验结果表明,该方法可行且有效。     

基于反馈机制的动态负载平衡算法研究*

动态负载平衡是提高多处理器系统资源利用率和并行计算性能的重要途径。为了解决变化负载系统中子任务可并行计算的双重循环(PTM-NL)问题,提出一种基于反馈机制的动态负载平衡算法。该算法以处理器作业速度为负载指标,在循环计算中根据反馈的负载指标分配计算任务,动态适应负载变化。实验结果表明,该算法在变化负载的系统中能有效提高PTM-NL问题并行效率。     

基于截止时间满意度的网格工作流调度算法

动态网格环境中用户截止时间保障是工作流调度问题的一个挑战.利用随机服务模型来描述网格资源的动态处理能力及其动态负载压力,提出了截止时间满意度的概念和工作流截止时间满意度的计算方法.将以DAG图形式表示的任务执行关系转换为以数值表示的任务执行优先级,并根据最大截止时间满意度优先的思想,确定执行工作流子任务的候选资源;将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题,提出了一种截止时间满意度增强的工作流调度算法(DSESAW).仿真实验采用实际网格应用和系统数据来验证所提出算法的性能表现,实验结果表明新算法在网格环境的自适应性和用户截止时间保障方面优于其他两种实际网格系统中的调度算法.     

基于动态负载均衡的层次性移动IPv6路由优化方案

针对层次性移动IPv6网络负载过重时存在的MAP负载分配失衡的问题,提出一种动态的MAP负载调度方案。方案中,MAP通过提出的计算模型,以带宽使用情况作为参数计算当前的负载。当检测到网络负载分配失衡时,根据MN的移动趋向调度MAP之间的负载,使网络中的计算资源合理分配,优化网络性能。仿真结果表明,该方案能有效地改善网络的整体服务质量,降低通信时延和减少通信过程中的丢包率。     

一种面向非对称多核处理器的综合性调度算法

在非对称多核处理器上进行任务调度时,现有的操作系统调度器没有考虑其非对称性.针对单一指令集非对称多核处理器上的操作系统调度问题,首先建立线性规划模型,分析各种因素,得出行为匹配、减少迁移和负载均衡的调度原则.然后,基于调度原则提出一种综合性调度算法.该算法包括两个部分:1) 集成负载表征,提出集成行为的概念,全面衡量任务的整体性和阶段性行为;2) 基于集成行为的调度算法,有效开发非对称多核处理器的特性,能够保证各核心负载均衡,同时可以避免不必要的任务迁移.另外,该算法通过参数调整机制实现了算法的通用性.该算法是一种综合处理任务的整体性和阶段性行为,并具备通用性的调度算法.实际平台上的实验结果表明,该算法可通用于多种环境,且性能比其他对应算法提高6%～22%.     

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.     

Comments on “Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks”

Min, Veeravalli, and Barlas have proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments [Han Min Wong, Bharadwaj Veeravalli, Scheduling divisible loads on heterogeneous linear daisy chain networks with arbitrary processor release times, IEEE Trans. Parallel Distrib. Syst. 15 (3) (2004) 273–288; Han Min Wong, Bharadwaj Veeravalli, Gerassimos Barlas, Design and performance evaluation of load distribution strategies for multiple divisible loads on heterogeneous linear daisy chain networks, J. Parallel Distrib. Comput. 65 (12) (2005) 1558–1577]. We show using a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Finally, we formally prove that under a linear cost model, as in both the above-mentioned references, an optimal schedule has an infinite number of installments. Therefore such a cost model should not be used to design practical multi-installment algorithms.     

A new load distribution strategy for linear network with communication delays

In this paper, we propose a new load distribution strategy called ‘send-and-receive’ for scheduling divisible loads, in a linear network of processors with communication delay. This strategy is designed to optimally utilize the network resources and thereby minimizes the processing time of entire processing load. A closed-form expression for optimal size of load fractions and processing time are derived when the processing load originates at processor located in boundary and interior of the network. A condition on processor and link speed is also derived to ensure that the processors are continuously engaged in load distributions. This paper also presents a parallel implementation of ‘digital watermarking problem’ on a personal computer-based Pentium Linear Network (PLN) topology. Experiments are carried out to study the performance of the proposed strategy and results are compared with other strategies found in literature.     

Optimizing computing costs using divisible load analysis

A bus oriented network where there is a charge for the amount of divisible load processed on each processor is investigated. A cost optimal processor sequencing result is found which involves assigning load to processors in nondecreasing order of the cost per load characteristic of each processor. More generally, one can trade cost against solution time. Algorithms are presented to minimize computing cost with an upper bound on solution time and to minimize solution time with an upper bound on cost. As an example of the use of this type of analysis, the effect of replacing one fast but expensive processor with a number of cheap but slow processors is also discussed. The type of questions investigated here are important for future computer utilities that perform distributed computation for some charge     

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

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

Minimizing the stretch when scheduling flows of divisible requests

In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed for this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive single processor case, and we show how to extend algorithms that have been proposed in the literature for the single processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any online algorithm, we present new competitiveness results for existing algorithms, and we develop several new online heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics under realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the single processor model are inefficient in practice. In contrast, we show that our online algorithms based on linear programming are in practice near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case.     

负载平衡无关的并行程序最适处理器网格选择

用户在编写并行程序时,通常是把物理处理器看成逻辑的处理器(进程)网格,以便于算法的实现.随着用户可用处理器的不断增多,可选择的网格形状也随之增加,如何为基于消息传递的并行程序选择合适的、能发挥出并行机潜在性能的处理器网格形状,是一个迫切需要解决的问题.在提出基于通信点概念的最小度数通信点集合法之后,通过对并行程序通信模式的分析,试图解决与负载平衡无关的并行程序的最适处理器网格选择问题.通过对ScaLAPACK软件包中的一个并行测试程序——并行Cholesky(对称正定矩阵分解)通信点集合度的分析,此方法成功地选择了最适处理器网格形状,并与实验结果相一致.     

Scheduling divisible loads on heterogeneous linear daisy chain networks with arbitrary processor release times

The problem of distributing and processing a divisible load in a heterogeneous linear network of processors with arbitrary processors release times is considered. A divisible load is very large in size and has computationally intensive CPU requirements. Further, it has the property that the load can be partitioned arbitrarily into any number of portions and can be scheduled onto processors independently for computation. The load is assumed to arrive at one of the farthest end processors, referred to as boundary processors, for processing. The processors in the network are assumed to have nonzero release times, i.e., the time instants from which the processors are available for processing the divisible load. Our objective is to design a load distribution strategy by taking into account the release times of the processors in such a way that the entire processing time of the load is a minimum. We consider two generic cases in which all processors have identical release times and when all processors have arbitrary release times. We adopt both the single and multiinstallment strategies proposed in the divisible load scheduling literature in our design of load distribution strategies, wherever necessary, to achieve a minimum processing time. Finally, when optimal strategies cannot be realized, we propose two heuristic strategies, one for the identical case, and the other for nonidentical release times case, respectively. Several conditions are derived to determine whether or not optimal load distribution exists and illustrative examples are provided for the ease of understanding.     

Scheduling divisible loads with time and cost constraints

In distributed computing, divisible load theory provides an important system model for allocation of data-intensive computations to processing units working in parallel. The main task is to define how a computation job should be split into parts, to which processors those parts should be allocated and in which sequence. The model is characterized by multiple parameters describing processor availability in time, transfer times of job parts to processors, their computation times and processor usage costs. The main criteria are usually the schedule length and cost minimization. In this paper, we provide the generalized formulation of the problem, combining key features of divisible load models studied in the literature, and prove its NP-hardness even for unrestricted processor availability windows. We formulate a linear program for the version of the problem with a fixed number of processors. For the case with an arbitrary number of processors, we close the gaps in the study of special cases, developing efficient algorithms for single criterion and bicriteria versions of the problem, when transfer times are negligible.

     

异构计算中的负载共享

在基于消息传递的异构并行计算系统中 ,各处理器或计算机具有自制和独立地调度、执行作业的能力 .当一个可划分的作业初始位于一个处理器上时 ,为了提高计算性能 ,该处理器可以请求其他异构处理器负载共享 ,参与协同计算 ,减少作业的完成时间 .该文提出了异构计算负载共享的一种方案 .首先 ,调用负载共享协议 ,收集当前各处理器参与负载共享的许可数据 ,包括共享时间段、计算能力等 .然后 ,构造一个作业量与作业完成时间之间的关系函数 .该函数是选择一组合适的处理器群、优化作业划分、作业完成时间最小的理论基础 .最