Efficient out-of-core sorting algorithms for the Parallel Disks Model

In this paper,¹ we present efficient algorithms for sorting on the Parallel Disks Model (PDM). Numerous asymptotically optimal algorithms have been proposed in the literature. However, many of these merge based algorithms have large underlying constants in the time bounds, because they suffer from the lack of read parallelism on the PDM. The irregular consumption of the runs during the merge affects the read parallelism and contributes to the increased sorting time. In this paper, we first introduce a novel idea called the dirty sequence accumulation that improves the read parallelism. Next, we show analytically that this idea can reduce the number of parallel I/O’s required to sort the input close to the lower bound of . We verify experimentally our dirty sequence idea with the standard R-Way merge and show that our idea can reduce the number of parallel I/Os to sort on the PDM significantly.     

Optimal Read-Once Parallel Disk Scheduling

An optimal prefetching and I/O scheduling algorithm L-OPT, for parallel I/O systems, using a read-once model of block references is presented. The algorithm uses knowledge of the next $L$ references, $L$-block lookahead, to create a minimal-length I/O schedule. For a system with $D$ disks and a buffer of capacity $m$ blocks, we show that the competitive ratio of L-OPT is $\Theta(\sqrt{mD/L})$ when $L \geq m$, which matches the lower bound of any prefetching algorithm with $L$-block lookahead. Tight bounds for the remaining ranges of lookahead are also presented. In addition we show that L-OPT is the optimal offline algorithm: when the lookahead consists of the entire reference string, it performs the absolute minimum possible number of I/Os. Finally, we show that L-OPT is comparable with the best online algorithm with the same amount of lookahead; the ratio of the length of its schedule to the length of the optimal schedule is always within a constant factor.     

Ancient and New Algorithms for Load Balancing in the l p Norm

We consider the on-line load balancing problem where there are m identical machines (servers) and a sequence of jobs. The jobs arrive one by one and should be assigned to one of the machines in an on-line fashion. The goal is to minimize the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. We show that for the sum of the squares the greedy algorithm performs within 4/3 of the optimum, and no on-line algorithm achieves a better competitive ratio. Interestingly, we show that the performance of Greedy is not monotone in the number of machines. More specifically, the competitive ratio is 4/3 for any number of machines divisible by 3 but strictly less than 4/3 in all the other cases (although it approaches 4/3 for a large number of machines). To prove that Greedy is optimal, we show a lower bound of 4/3 for any algorithm for three machines. Surprisingly, we provide a new on-line algorithm that performs within 4/3 -δ of the optimum, for some fixed δ>0 , for any sufficiently large number of machines. This implies that the asymptotic competitive ratio of our new algorithm is strictly better than the competitive ratio of any possible on-line algorithm. Such phenomena is not known to occur for the classic maximum load problem. Minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the l ₂ norm. We extend our techniques and analyze the exact competitive ratio of Greedy with respect to the l _p norm. This ratio turns out to be 2 - Θ(( ln p)/p) . We show that Greedy is optimal for two machines but design an algorithm whose asymptotic competitive ratio is better than the ratio of Greedy. Received January 2, 1998; revised December 12, 1998.     

Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web services

The prevalence of dynamic-content web services, exemplified by search and online social networking, has motivated an increasingly wide web-facing front end. Horizontal scaling in the Cloud is favored for its elasticity, and distributed design of load balancers is highly desirable. Existing algorithms with a centralized design, such as Join-the-Shortest-Queue (JSQ), incur high communication overhead for distributed dispatchers.We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. Unlike algorithms such as Power-of-Two, the JIQ algorithm incurs no communication overhead between the dispatchers and processors at job arrivals. We analyze the JIQ algorithm in the large system limit and find that it effectively results in a reduced system load, which produces 30-fold reduction in queueing overhead compared to Power-of-Two at medium to high load. An extension of the basic JIQ algorithm deals with very high loads using only local information of server load.     

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

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

A hybrid policy for fault tolerant load balancing in grid computing environments

Due to the emergence of grid computing over the Internet, there is a need for a hybrid load balancing algorithm which takes into account the various characteristics of the grid computing environment. Hence, this research proposes a fault tolerant hybrid load balancing strategy namely AlgHybrid_LB, which takes into account grid architecture, computer heterogeneity, communication delay, network bandwidth, resource availability, resource unpredictability and job characteristics. AlgHybrid_LB juxtaposes the strong points of neighbor-based and cluster based load balancing algorithms. Our main objective is to arrive at job assignments that could achieve minimum response time and optimal computing node utilization. Major achievements include low complexity of proposed approach and drastic reduction of number of additional communications induced due to load balancing. A simulation of the proposed approach using Grid Simulation Toolkit (GridSim) is conducted. Experimental results show that the proposed algorithm performs very well in a large grid environment.     

Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation

We study the problem of on-line scheduling on two uniformly related machines where the on-line algorithm has resources different from those of the off-line algorithm. We consider three versions of this problem, preemptive semi-online, non-preemptive on-line and preemptive on-line scheduling. For all these cases we design algorithms with best possible competitive ratios as functions of the machine speeds. This work was submitted as a part of the M.Sc. thesis of the second author. A preliminary version of this paper appeared in the proceedings of The First Workshop on Approximation and Online Algorithms (WAOA’03), pages 109–122.     

基于负载均衡的虚拟网映射随机算法

分析了基于\"尽力服务\"模式的虚拟网映射算法所存在的问题,并指出了其在资源均衡利用方面的不足,设计了物理网负载均衡代价指标,提出了负载均衡的虚拟网映射随机算法。实验表明,所提出的算法能提高物理网资源的负载均衡度和利用率,从而提高虚拟网构建请求的接受率和物理网提供商的收益。     

On-Line Load Balancing and Network Flow

In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task is restricted to run on some subset of the servers. The scheduler attempts to keep the load well-balanced. If preemptive reassignments are disallowed, Azar et al. [3] proved a lower bound of Ω(n ^1/2 ) on the ratio between the maximum load achieved by an on-line algorithm and the optimum off-line maximum load. We show that this ratio can be greatly reduced by an efficient scheduler using only a small amount of rescheduling. We then apply these ideas to network flow. Cheriyan and Hagerup [6] introduced an on-line game on a bipartite graph as a fundamental step in improving algorithms for computing the maximum flow in networks. They described a randomized strategy to play the game. King et al. [11] studied a modified version of this game, called ``node kill,' and gave a deterministic strategy. We obtain an improved deterministic algorithm for the node kill game (and hence for maximum flow) in all but the sparsest graphs. The running time achieved is O(mn log _m/n n+n ² log ^2+ε n) , compared with King et al.'s O(mn+n ^2+ε ) . These problems combine a demand for good competitive ratios with more traditional requirements of implementation efficiency. Our solutions deal with the tradeoffs between these measures. Received March 15, 1997; revised April 20, 1997.     

以太网集群并行图像处理技术

基于以太网集群的并行图像处理系统具有价格低廉、性能较高、可扩展性好、应用前景广阔的优点,实用价值十分重要。针对同构以太网集群图像处理系统建立模型,并给出了在该模型下实现静态负载均衡的最短时间划分条件,最后的实验结果证明,文中的分析与实际运行情况十分吻合。     

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

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

基于内容的网络集群负载平衡算法模型

在论述网络集群负载平衡算法的基础上,基于内容分类的方法,给出基于内容的网络集群负载平衡算法三元组模型。请求分类有利于提高缓存命中率,调度机制说明如何适当地转发请求,动态反馈避免将请求分配到重载的服务器,进而分析了调度机制的八种调度策略和六种基于内容的调度转发技术。该模型利用缓存内容来提高集群的吞吐量和响应时间,可部署多种服务类型。     

一种基于预取的集群服务器调度算法

针对集群服务器LARD调度算法只能利用已有缓存的问题,提出一种基于预取的算法Prefetch-LARD,该算法从Web访问日志中挖掘页面之间的转移概率,建立马尔科夫链模型,在调度请求时利用概率关系提前将下一次可能访问的文档从节点磁盘取到本地cache中,提高了请求的缓存命中率;算法还采用了加权的节点超载判断方法,以提高集群节点的负载均衡度,实验表明,在同样的测试环境下,Prefetch-LARD算法比LARD算法的缓存命中率提高26．9％,系统的吞吐量相应提高18．8％．     

基于规则的分层负载平衡调度模型

On a massively parallel and distributed system and a network of workstations system, it is a critical problem to increase the utilization efficiency of resources and the answer speed of tasks by using effective load balancing scheduling strategy. This paper analyzes the scheduling strategy of dynamic load balancing and static load balancing,and then proposes a hierarchical load balancing scheduling model based on rules. Finally,making somecomparisons with Other scheduling models.     

Heavy traffic optimal resource allocation algorithms for cloud computing clusters

Cloud computing is emerging as an important platform for business, personal and mobile computing applications. In this paper, we study a stochastic model of cloud computing, where jobs arrive according to a stochastic process and request resources like CPU, memory and storage space. We consider a model where the resource allocation problem can be separated into a routing or load balancing problem and a scheduling problem. We study the join-the-shortest-queue routing and power-of-two-choices routing algorithms with the MaxWeight scheduling algorithm. It was known that these algorithms are throughput optimal. In this paper, we show that these algorithms are queue length optimal in the heavy traffic limit.     

Parallel extremal optimization in processor load balancing for distributed applications

The paper concerns parallel methods for extremal optimization (EO) applied in processor load balancing in execution of distributed programs. In these methods EO algorithms detect an optimized strategy of tasks migration leading to reduction of program execution time. We use an improved EO algorithm with guided state changes (EO-GS) that provides parallel search for next solution state during solution improvement based on some knowledge of the problem. The search is based on two-step stochastic selection using two fitness functions which account for computation and communication assessment of migration targets. Based on the improved EO-GS approach we propose and evaluate several versions of the parallelization methods of EO algorithms in the context of processor load balancing. Some of them use the crossover operation known in genetic algorithms. The quality of the proposed algorithms is evaluated by experiments with simulated load balancing in execution of distributed programs represented as macro data flow graphs. Load balancing based on so parallelized improved EO provides better convergence of the algorithm, smaller number of task migrations to be done and reduced execution time of applications.     

CC-NUMA结构下共享变量并行计算的研究

探讨了如何提高CC-NUMA结构下共享变量程序的并行效率。主要介绍了几种有效的负载均衡策略和减少共享存储访问延迟的优化 手段。通过分析可以看出,通过合适的优化方法,CC-NUMA结构下共享变量的应用程序可以取得好的并行效率。     

Using imbalance metrics to optimize task clustering in scientific workflow executions

Scientific workflows can be composed of many fine computational granularity tasks. The runtime of these tasks may be shorter than the duration of system overheads, for example, when using multiple resources of a cloud infrastructure. Task clustering is a runtime optimization technique that merges multiple short running tasks into a single job such that the scheduling overhead is reduced and the overall runtime performance is improved. However, existing task clustering strategies only provide a coarse-grained approach that relies on an over-simplified workflow model. In this work, we examine the reasons that cause Runtime Imbalance and Dependency Imbalance in task clustering. Then, we propose quantitative metrics to evaluate the severity of the two imbalance problems. Furthermore, we propose a series of task balancing methods (horizontal and vertical) to address the load balance problem when performing task clustering for five widely used scientific workflows. Finally, we analyze the relationship between these metric values and the performance of proposed task balancing methods. A trace-based simulation shows that our methods can significantly decrease the runtime of workflow applications when compared to a baseline execution. We also compare the performance of our methods with two algorithms described in the literature.