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

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

异构总线网络的可分负载优化调度算法

研究了异构总线网络的负载优化调度问题,详细讨论了处理机选择、任务分配顺序和各处理机分配任务数量。结论表明：通过按照处理机速度递减的顺序配置处理机,并据此分配相应的任务,即可实现负载的优化调度。     

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

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

基于集群的负载平衡调度算法研究与实现

在集群系统的负载调度研究中,针对请求的服务时间变化大的特点,该文提出了一个动态反馈负载平衡算法,它结合内核中的加权连接调度算法,根据动态反馈回来的负载信息来调整服务器的权值,从而有效地解决服务器问的负载不平衡问题,提高了系统的吞吐率。     

一种面向数据密集型应用的并行程序执行模型

随着各领域需要处理的数据量越来越大,数据密集型应用也变得越来越被重视.该文提出一种包含数据访存层次和访存冲突等信息的新并行程序执行模型PSRAM(h).针对数据密集型应用以访存为主的特点,PSRAM(h)模型将程序执行时间简化为访存时间,通过分析各程序子段的访存层次和数量来预测串行程序的执行时间,进而通过使用各线程执行时间的最大值来预测并行程序的执行时间.使用PSRAM(h)模型下对最典型的数据密集型应用矩阵向量乘进行分析,在龙芯3A处理器和Intel Xeon E5520处理器两个平台上的测试结果表明,PSRAM(h)模型分析结果与实测结果大部分情况下误差小于20%.由此可见,针对数据密集型应用,PSRAM(h)不但可以给出程序执行时间的下限,还可以有效的预测程序的执行时间.     

Improving Performance on Data-Intensive Applications Using a Load Balancing Methodology Based on Divisible Load Theory

Data-intensive applications are those that explore, query, analyze, and, in general, process very large data sets. Generally, these applications can be naturally implemented in parallel but, in many cases, these implementations show severe performance problems mainly due to load imbalances, inefficient use of available resources, and improper data partition policies. It is worth noticing that the problem becomes more complex when the conditions causing these problems change at run time. This paper proposes a methodology for dynamically improving the performance of certain data-intensive applications based on: adapting the size and number of data partitions, and the number of processing nodes, to the current application conditions in homogeneous clusters. To this end, the processing of each exploration is monitored and gathered data is used to dynamically tune the performance of the application. The tuning parameters included in the methodology are: (i) the partition factor of the data set, (ii) the distribution of the data chunks, and (iii) the number of processing nodes to be used. The methodology assumes that a single execution includes multiple related explorations on the same partitioned data set, and that data chunks are ordered according to their processing times during the application execution to assign first the most time consuming partitions. The methodology has been validated using the well-known bioinformatics tool—BLAST—and through extensive experimentation using simulation. Reported results are encouraging in terms of reducing total execution time of the application (up to a 40 % in some cases).     

异构集群环境下负载平衡调度算法研究与实现

围绕平衡负载这一目标,针对进程级并行任务的动态调度问题进行了研究,提出了一个异构集群环境下动态负载平衡算法,它结合了自适应数据采集与交换算法,有效的解决了服务器之间负载不平衡的问题,提高了系统的吞吐率。     

网格环境下可靠的可分割作业调度机制

针对传统可分割作业多路调度算法不能适应动态网格环境的不足,基于统一多路(Uniform Multi-Round:UMR)算法,提出一种可靠的可分割作业调度机制.系统动态地监控网格资源的变化,当资源发生变化时,通过性能预测与评估,及时地对剩余作业进行再调度.实验表明,较之传统的多路调度算法,该机制在动态的网格环境下,降低了作业完成时间,有效地利用了网格资源,提高了作业调度的可靠性.     

Strategyproof Mechanisms for Scheduling Divisible Loads in Bus-Networked Distributed Systems

The scheduling of arbitrarily divisible loads on a distributed system is studied by Divisible Load Theory (DLT). DLT has the underlying assumption that the processors will not cheat. In the real world, this assumption is unrealistic as the processors are owned and operated by autonomous rational organizations that have no a priori motivation for cooperation. Consequently, they will manipulate the algorithms if it benefits them to do so. In this work, we propose strategyproof mechanisms for scheduling divisible loads on three types of bus-connected distributed systems. These mechanisms provide incentives to the processors to obey the prescribed algorithms and to truthfully report their parameters, leading to an efficient load allocation and execution.     

New Algorithms for Disk Scheduling

Abstract. Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function that determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2 -approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly distributed requests arrive over time. We present an algorithm related to the above ATSP-Δ .     

New Algorithms for Disk Scheduling

Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/ O performance could become an important bottleneck. Methods are needed for using disks more efficiently. Past analysis of disk scheduling algorithms has largely been experimental and little attempt has been made to develop algorithms with provable performance guarantees. We consider the following disk scheduling problem. Given a set of requests on a computer disk and a convex reachability function that determines how fast the disk head travels between tracks, our goal is to schedule the disk head so that it services all the requests in the shortest time possible. We present a 3/2 -approximation algorithm (with a constant additive term). For the special case in which the reachability function is linear we present an optimal polynomial-time solution. The disk scheduling problem is related to the special case of the Asymmetric Traveling Salesman Problem with the triangle inequality (ATSP-Δ ) in which all distances are either 0 or some constant α . We show how to find the optimal tour in polynomial time and describe how this gives another approximation algorithm for the disk scheduling problem. Finally we consider the on-line version of the problem in which uniformly distributed requests arrive over time. We present an algorithm related to the above ATSP-Δ .     

Robust Algorithms for Preemptive Scheduling

Preemptive scheduling problems on parallel machines are classic problems. Given the goal of minimizing the makespan, they are polynomially solvable even for the most general model of unrelated machines. In these problems, a set of jobs is to be assigned to run on a set of m machines. A job can be split into parts arbitrarily and these parts are to be assigned to time slots on the machines without parallelism, that is, for every job, at most one of its parts can be processed at each time. Motivated by sensitivity analysis and online algorithms, we investigate the problem of designing robust algorithms for constructing preemptive schedules. Robust algorithms receive one piece of input at a time. They may change a small portion of the solution as an additional part of the input is revealed. The capacity of change is based on the size of the new piece of input. For scheduling problems, the supremum ratio between the total size of the jobs (or parts of jobs) which may be re-scheduled upon the arrival of a new job j, and the size of j, is called migration factor. We design a strongly optimal algorithm with the migration factor $1-\frac{1}{m}$ for identical machines. Strongly optimal algorithms avoid idle time and create solutions where the (non-increasingly) sorted vector of completion times of the machines is lexicographically minimal. In the case of identical machines this results not only in makespan minimization, but the created solution is also optimal with respect to any ? _p norm (for p>1). We show that an algorithm of a smaller migration factor cannot be optimal with respect to makespan or any other ? _p norm, thus the result is best possible in this sense as well. We further show that neither uniformly related machines nor identical machines with restricted assignment admit an optimal algorithm with a constant migration factor. This lower bound holds both for makespan minimization and for any ? _p norm. Finally, we analyze the case of two machines and show that in this case it is still possible to maintain an optimal schedule with a small migration factor in the cases of two uniformly related machines and two identical machines with restricted assignment.     

无线调度算法

为满足无线应用中的Qos要求,调度算法是很重要的。由于无线网络变化的链路错误率和容量,因此为其设计调度算法非常有挑战性。近来提出了多种适合无线网络的调度算法。该文分析了3种基于TDD的调度算法。讨论了各种算法的实现过程和优缺点,最后对它们的性能进行比较．得出了有意义的结论。     

Competitive Algorithms for Due Date Scheduling

We consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates.     

Approximation Algorithms for Average Stretch Scheduling

We study the basic problem of preemptive scheduling of a stream of jobs on a single processor. Consider an on-line stream of jobs, and let the ith job arrive at time r(i) and have processing time p(i). If C(i) is the completion time of job i, then the flow time of i is C(i) − r(i) and the stretch of i is the ratio of its flow time to its processing time; that is, . Flow time measures the time that a job is in the system regardless of the service it requests; the stretch measure relies on the intuition that a job that requires a long service time must be prepared to wait longer than jobs that require small service times. We present the improved algorithmic results for the average stretch metric in preemptive uniprocessor scheduling. Our first result is an off-line polynomial-time approximation scheme (PTAS) for average stretch scheduling. This improves upon the 2-approximation achieved by the on-line algorithm srpt that always schedules a job with the shortest remaining processing time. In a recent work, Chekuri and Khanna (Proc. 34th Ann. Symp. Theory Comput., 297–305, 2002) have presented approximation algorithms for weighted flow time, which is a more general metric than average stretch; their result also yields a PTAS for average stretch. Our second set of results considers the impact of incomplete knowledge of job sizes on the performance of on-line scheduling algorithms. We show that a constant-factor competitive ratio for average stretch is achievable even if the processing times (or remaining processing times) of jobs are known only to within a constant factor of accuracy.     

Optimal Scheduling Algorithms for Tertiary Storage

The ever growing needs of large multimedia systems cannot be met by magnetic disks due to their high cost and low storage density. Consequently, cheaper and denser tertiary storage systems are being integrated into the storage hierarchies of these applications. Although tertiary storage is cheaper, the access latency is very high due to the need to load and unload media on the drives. This high latency and the bursty nature of I/O traffic result in the accumulation of I/O requests for tertiary storage. We study the problem of scheduling these requests to improve performance. In particular we address the issues of scheduling across multiple tapes or disks as opposed to most other studies which consider only one or two media. We focus on algorithms that minimize the number of switches and show through simulation that these result in near-optimal schedules. For single drive libraries an efficient algorithm that produces optimal schedules is developed. Formultiple drives the problem is shown to be NP-Complete. Efficient and effective heuristics are presented for both single and multiple drives. The scheduling policies developed achieve significant performance gains over naive policies. The algorithms are simple to implement and are not restrictive. The study encompasses all types of storage libraries handling removable media, such as tapes and optical disks.     

Approximation Algorithms for Time Constrained Scheduling

In this paper we consider the following time constrained scheduling problem. Given a set of jobsJwith execution timese(j)(0, 1] and an undirected graphG=(J, E), we consider the problem to find a schedule for the jobs such that adjacent jobs (j, j′)Eare assigned to different machines and that the total execution time for each machine is at most 1. The goal is to find a minimum number of machines to execute all jobs under this time constraint. This scheduling problem is a natural generalization of the classical bin-packing problem. We propose and analyse several approximation algorithms with constant absolute worst case ratio for graphs that can be colored in polynomial time.     

Barely Random Algorithms for Multiprocessor Scheduling

We consider randomized algorithms for on-line scheduling on identical machines. For two machines, a randomized algorithm achieving a competitive ratio of was found by Bartal et al. (1995). Seiden has presented a randomized algorithm which achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m=3,4,5,6,7, respectively (Seiden, 2000). A barely random algorithm is one which is a distribution over a constant number of deterministic strategies. The algorithms of Bartal et al. and Seiden are not barely random–in fact, these algorithms potentially make a random choice for each job scheduled. We present the first barely random on-line scheduling algorithms. In addition, our algorithms use less space and time than the previous algorithms, asymptotically.     

Performance of Channel-Aware Scheduling Algorithms for HDR-WPAN

In this paper, we consider the performances in terms of system throughput and response time of various channel-aware scheduling algorithms for both MPEG streams and non-MPEG flows in a high-data-rate (HDR) wireless personal area network (WPAN). The algorithms under investigation are the shortest remaining processing time rule, the exponential rule, the modified largest weighted delay first rule, the maximum rate rule, and the proportionally fair rule. Decodability issues are taken care of by means of the frame-decodability aware technique and the burst transfer eligibility decision mechanism. The impacts of a number of factors including deadline and interference-plus-noise level are also examined. The investigations are carried out through extensive ns-2 simulations. Based on the numerical results, we propose a heuristic scheduling algorithm for MPEG streams that outperforms the above algorithms in terms of system throughput. The findings are useful for system designers.     

网络处理器负载均衡算法综述

本文针对网络处理器中多个处理单元的负载均衡方法展开了讨论,详细介绍了多种负载均衡方法,给出了网络处理器负载均衡的特点和性能度量标准,提出了该领域进一步研究方向和基本思路.对同类研究有一定的帮助.