A Negotiation Protocol for Dynamic Load Distribution Using Batch Task Assignments

Adynamic load distribution(LD) algorithm improves the performance of a distributed system by using current system load information to relocate application tasks among processing nodes, so that workload imbalance in the system can be smoothed out. In this paper, we propose aguarantee and reservation protocol(GR protocol) which can be used by dynamic LD algorithms. In contrast to the commonly usedsingle task assignments, GR protocol usesbatch task assignments, meaning that multiple tasks can be selected for remote execution during each single sender–receiver negotiation session. GR protocol is used to obtain a mutual agreement between a task sender and a receiver on an appropriate task batch size. GR protocol is based on avirtual workload modelwhich ensures coordinated even dispersements of tasks in the system. This model also avoidsprocessor thrashing, a situation when a receiver node is flooded with excessive remotely assigned tasks and thus becomes overloaded inadvertently.     

An adaptive threshold based hybrid load balancing scheme with sender and receiver initiated approach using random information exchange

The primary objective of load balancing for distributed systems is to minimize the job execution time while maximizing the resource utilization. Load balancing on decentralized systems need effective information exchange policy so that with minimum amount of communication the nodes have up to date information about other nodes in the system. Periodic, event‐based and on‐demand information exchange are some important policies used for the same. All these approaches involve a lot of overhead and even sometime leading toward obsolete data with the nodes if there is a delay in the updation. This work presents an adaptive threshold‐based hybrid load balancing scheme with sender and receiver initiated approach (HLBWSR) using random information exchange (RIE). RIE ensures that the information is exchanged in such a way that each node in the system has up‐to‐date state of the other nodes with much reduced communication overhead. Further, the adaptive threshold ensures that almost an average numbers of jobs are executed by all the nodes in the system. The study of the effect of the use of RIE on sender initiated, receiver initiated and hybrid of sender and receiver initiated load balancing approach establishes the superior performance of HLBWSR among its RIE‐based peers. A comparative analysis of HLBWSR, with periodic information exchange strategy, modified estimated load information scheduling algorithm and load balancing on arrival reveals its effectiveness under various test conditions. Copyright © 2016 John Wiley & Sons, Ltd.     

分布式系统中的双向启动自适应任务分配算法

本文讨论一种分布式系统中的任务分配算法，对它所使用的数据结构、算法实现以及性能等给予阐述，本算法采用双向启动策略，而且能根据系统总负功情况等自动选择发送者或接受者启动，所以称为双向启动自适应算法，同时，利用阈值和阈长两种参数把系统中的节点分为接受节点，负载适中节点和发送节点，它保证了寻找合作节点的优化和寻找速度的提高，是一种启发式算法。     

Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems

Most computer systems use a global page replacement policy based on the LRU principle to approximately select a Least Recently Used page for a replacement in the entire user memory space. During execution interactions, a memory page can be marked as LRU even when its program is conducting page faults. We define the LRU pages under such a condition as false LRU pages because these LRU pages are not produced by program memory reference delays, which is inconsistent with the LRU principle. False LRU pages can significantly increase page faults, even cause system thrashing. This poses a more serious risk in a large parallel systems with distributed memories because of the existence of coordination among processes running on individual node. In the case, the process thrashing in a single node or a small number of nodes could severely affect other nodes running coordinating processes, even crash the whole system. In this paper, we focus on how to improve the page replacement algorithm running on one node.

After a careful study on characterizing the memory usage and the thrashing behaviors in the multi-programming system using LRU replacement. we propose an LRU replacement alternative, called token-ordered LRU, to eliminate or reduce the unnecessary page faults by effectively ordering and scheduling memory space allocations. Compared with traditional thrashing protection mechanisms such as load control, our policy allows more processes to keep running to support synchronous distributed process computing. We have implemented the token-ordered LRU algorithm in a Linux kernel to show its effectiveness.     

An adaptive load distribution algorithm for resolving bursty workload

Most existing dynamic load distribution (LD) algorithms assume fairly stable task arrival pattern. With this assumption, single task assignments are adequate to provide reasonably good performance. They are, however, inadequate when tasks arrive in bursts. In this paper, we propose a LD algorithm based on batch task assignments. The algorithm is tailored to systems subject to bursty workload. The key of this algorithm is the dynamic negotiation on the amount of workload to be transferred between a sender–receiver pair. Dynamic negotiations ensure the algorithm's adaptive behavior, thus allow task congestions to be resolved quickly. Consequently, CPU utilization can be increased and average task response time reduced substantially. The dynamic negotiations are conducted by the GR Protocol, which also avoids processor thrashing and state waggling – two undesirable phenomena that commonly exist in LD algorithms. © 1999 John Wiley & Sons, Ltd.     

面向同构型多处理机系统的动态负载平衡算法

为了解决同构型多处理机系统中的负载不平衡问题,提出一种分布式控制、发送者驱动的动态平衡算法,该算法利用CPU队列长度衡量处理机负载状态、利用进程执行时间选取适合被迁移的负载、利用较完备的消息机制传播处理机负载状态和负载平衡要求,适用于计算密集型任务.实验结果验证了该算法的有效性.     

芯片级多线程处理器的操作系统调度研究

随着芯片级多线程（CMT）处理器体系结构的迅速发展,操作系统必须采用新型CMT调度,以发挥其体系结构的性能优势。分析CMT调度面临的问题,通过扩展调度域的层次和结构支持CMT处理器内部的负载均衡,利用协同调度避免cache抖动等问题。采用效率、效率瓦特比和公平性等多种指标对操作系统进行性能评价,证明其性能得到优化。     

Adaptive load distribution algorithms for heterogeneous distributed systems with multiple task classes

A load distribution (LD) algorithm achieves better system performance by smoothing out any workload imbalance that may exist in a distributed system. This is done by relocating application tasks from busy nodes to lightly loaded (or idle) nodes. Previous studies on LD algorithms allow only one single task to be transferred for each sender–receiver negotiation session. While this approach is effective for a homogeneous system, it is too conservative to be applied to a heterogeneous system where nodes may have drastically different processing speeds.In this paper, we propose a class of LD algorithms that allow a batch of tasks to be transferred during each negotiation session. The core of the algorithms is a protocol that ensures a sender–receiver pair to negotiate and arrive at a suitable batch size. The protocol takes into consideration the processing speeds of the sender and receiver, as well as their relative workload, thus ensuring the maximal benefit for each negotiation session. An additional advantage of the algorithms is that a task batch can be composed according to different performance objectives.     

多路并行传输中数据调度算法的优化

针对异构无线网络环境中,基于流控制传输协议（SCTP）的多路并行传输协议（CMT-SCTP）存在接收缓存阻塞和路径负载失衡等问题,提出一种改进的轮询数据调度算法。该算法根据每条路径上的发送队列信息和拥塞状况对网络状况进行估计,并按照各路径上的网络状况分配相应的传输任务量,缩短数据包在接收端缓冲区的平均排队时延,减少接收端乱序数据包的数量。仿真结果表明,改进的轮询数据调度算法能有效提升CMT-SCTP在异构无线网络环境中的传输效率,有效缓解接收缓存的阻塞,且对不同的网络场景具有很好的适应性。     

Task cluster scheduling in a grid system

Effective load distribution and resource management is of great importance in designing complex distributed systems as grid. This pre-assumes the capability of partitioning the arriving jobs into independent tasks that can be executed simultaneously, assigning the tasks to processors and scheduling the task execution on each processor. A simulation model, consisting of two homogeneous clusters, is considered to evaluate the performance for various workloads. The Deferred policy is applied to collect global system information about processor queues. This paper proposes a special scheduling method referred to as task clustering method. We examine the efficiency of two task routing policies – one static and one adaptive – and six task scheduling policies, which rearrange processor queues regarding to a criterion. Our simulation results indicate that the adaptive task routing policy in conjunction with SGFS-ST scheduling algorithm, which uses more efficiently the task clustering method, leads to a significant performance improvement.     

Communication styles for parallel systems

Distributed-memory parallel systems rely on explicit message exchange for communication, but the communication operations they support can differ in many aspects. One key difference is the way messages are generated or consumed. With systolic communication, a message is transmitted as it is generated. For example, the result computed by the multiplier is sent directly to the communication subsystem for transmission to another node. With memory communication, the complete message is generated and stored in memory, and then transmitted to its destination. Since sender and receiver nodes are individually controlled, they can use different communication styles. One example of memory communication is message passing: both the sender and receiver buffer the message in memory. These two communication styles place different demands on processor design. This article illustrates each style's effect on processor resources for some key application kernels. We are targeting the iWarp system because it supports both communication styles. Two parallel-program generators, one for each communication style, automatically map the sample programs     

一种基于自适应MR_ARQ协议性能的研究

自动重传请求(ARQ)协议是网络端_端传输中必不可少的一个环节。基于ARQ协议的在无反馈错误环境下的传输性能分析已得到广泛的研究。论文给出了一种在具有无线不可靠信道条件下根据传输性能要求自适应回传应答确认算法,有效地避免了不必要的重传,从而在一定条件下节省了宝贵的无线资源。模型分析及仿真结果表明:在一定的传输信道条件下使用自适应的MR_ARQ协议可有效地提高传输效率。     

无线网络中基于网络编码的重传机制

鉴于目前网络编码在单跳无线网络重传中的应用研究都是基于单发-多收场景的局限性,提出一种应用于多发-多收无线网络中的重传机制NCWRM。该重传机制中,网络节点既可以是发送方也可以是接收方,节点发送的数据包在直传和第一次重传中都失败后,第二次重传时广播发送由多个丢失数据包编码组合得到的编码包。多个接收方通过解码编码包得到丢失的数据包,从而实现一次重传获得多个丢失的数据包,可以有效提高重传效率。理论分析和仿真结果表明,NCWRM算法能够明显提高系统的饱和吞吐量,同时减小开销及丢包率。     

一种高效的动态概率广播算法及其概率模型检测分析

在Ad Hoc网络中,广播有着相当广泛的应用,其算法的效率极大地影响着网络的性能.本文基于DP算法提出了BN-DP算法,考虑了节点分布、计数器值以及收发节点间距离对广播算法的影响,赋予处于接收边缘的节点更高的转发概率.然后使用概率模型检测工具PRISM,分析了计数器值和节点分布对BN-DP算法性能的影响.结果表明:在相同可达率的情况下,所提出的BN-DP算法与FP、DP算法相比,减少了转发分组的数量,提高了广播效率.     

Hierarchical Partitioning Techniques for Structured Adaptive Mesh Refinement Applications

This paper presents the design and preliminary evaluation of hierarchical partitioning and load-balancing techniques for distributed structured adaptive mesh refinement (SAMR) applications. The overall goal of these techniques is to enable the load distribution to reflect the state of the adaptive grid hierarchy and exploit it to reduce synchronization requirements, improve load-balance, and enable concurrent communications and incremental redistribution. The hierarchical partitioning algorithm (HPA) partitions the computational domain into subdomains and assigns them to hierarchical processor groups. Two variants of HPA are presented in this paper. The static hierarchical partitioning algorithm (SHPA) assigns portions of overall load to processor groups. In SHPA, the group size and the number of processors in each group is setup during initialization and remains unchanged during application execution. It is experimentally shown that SHPA reduces communication costs as compared to the Non-HPA scheme, and reduces overall application execution time by up to 59%. The adaptive hierarchical partitioning algorithm (AHPA) dynamically partitions the processor pool into hierarchical groups that match the structure of the adaptive grid hierarchy. Initial evaluations of AHPA show that it can reduce communication costs by up to 70%.     

无线自组网中TCP按需确认机制

分析无线自组网中关于传输控制协议(TCP)的问题,研究基于按需确认的TCP协议在无线自组网中的改进算法。该算法规定接收方须根据发送方的要求对数据报文进行确认,减少确认(ACK)数量并消除延迟ACK对TCP传输效率的影响,提高了无线自组网中TCP的性能。仿真试验结果证明了该算法的有效性。     

减轻CMT中乱序程度的发送端数据分配方案

为减轻多径并行传输（concurrent multipath transfer,CMT）系统中的接收端数据包乱序对系统传输性能的影响,提出一种新的发送端数据分配方案。方案基于路径带宽、往返传输时延和拥塞窗口预测数据包前向传输时延,并将其作为划分系统中路径传输优先级的度量因子,发送端根据路径传输优先级和发送缓存区状态为各路径分配待发送队列中不会导致接收端乱序的数据包。仿真结果表明,与轮询和一种基于分组到达时间的负载均衡算法（arrival-time matching load-balancing,ATLB）算法相比,所提发送端数据分配方案可有效减少接收端乱序数据包个数。     

一种自适应动态负载均衡算法

负载均衡问题是一个经典的组合优化难题,该文建立了一个集群中的负载均衡问题模型,并提出了一种旨在最小化负载均衡开销的动态自适应算法。由于集群中存在网络延时,所以负载重分配的开销很大一部分取决于CPU间发送、接受的消息的最大数量。该负载均衡算法以最小化负载重分配时CPU间消息发送、接受的数量为目标,根据过载、轻载CPU数量的变化动态调用D算法和R算法,以降低负载均衡开销。     

异构环境下层次编码多视频源多共享信道分层组播

视频组播是许多当前和将来网络服务的重要组成部分,如视频会议,远程学习、远地展示及视频点播,随着网络传送基础设施的改善和端系统处理能力的增强,组播视频应用日益变得可行,组播视频传输中存在的主要问题是网络送资源的异构性和动态性,其使得视频流的多个接收方都达到可接受的流量特性变得异常困难,目前该问题的一个有效解决方式就是利用自适应的分层视频传输机制,在该机制中,各源产生层次媒体流,并在多个网络信道中传输。对视频会议类的多点到多点视频组播应用,信道往往被所有潜在的发送方共享,任何发送方都可在任何一个共享信道中发送其视频层次。在该多点到多点、共享信道、分层视频组播模型下,一个关键问题就是如何动态确定各视频源层次到各共享组播信道的映射,映射策略直接影响到会话整体视频接收质量和网络带宽利用率。典型的方式是顺序映射,该映射方式同等对待各发送方,但利用该方式,随源数目的增加,在各共享网络信度上会出现带宽可伸缩性问题,而且顺序映射方式无法适应网络传送资源和会话状态的动态变化。为此,该文设计了一种基于接收方反馈信息的自适应的层次映射算法,接收方周期性地将其当前感兴趣的发送方及接收速率的信息反馈给某控制节点,而控制节点就利用当前反馈信息动态地调整映射策略。经证实,该算法始终能比顺序层次映射算法获得更高的整体视频接收质量,并具有高的带宽利用率和很小的复杂度。     

Generating Communication for Array Statements: Design,Implementation, and Evaluation

Array statements as included in Fortran 90 or High Performance Fortran (HPF) are a well-accepted way to specify data parallelism in programs. When generating code for such a data parallel program for a private memory parallel system, the compiler must determine when array elements must be moved from one processor to another. This paper describes a practical method to compute the set of array elements that are to be moved; it covers all the distributions that are included in HPF: block, cyclic, and block-cyclic. This method is the foundation for an efficient protocol for modern private memory parallel systems: for each block of data to be sent, the sender processor computes the local address in the receiver′s address space, and the address is then transmitted together with the data. This strategy increases the communication load but reduces the overhead on the receiving processor. We implemented this optimization in an experimental Fortran compiler, and this paper reports an empirical evaluation on a 64-node private memory iWarp system, using a number of different distributions.