Adaptive optimal load balancing in a nonhomogeneous multiserver system with a central job scheduler

A model comprising several servers, each equipped with its own queue and with possibly different service speeds, is considered. Each server receives a dedicated arrival stream of jobs; there is also a stream of generic jobs that arrive to a job scheduler and can be individually allocated to any of the servers. It is shown that if the arrival streams are all Poisson and all jobs have the same exponentially distributed service requirements, the probabilistic splitting of the generic stream that minimizes the average job response time is such that it balances the server idle times in a weighted least-squares sense, where the weighting coefficients are related to the service speeds of the servers. The corresponding result holds for nonexponentially distributed service times if the service speeds are all equal. This result is used to develop adaptive quasi-static algorithms for allocating jobs in the generic arrival stream when the load parameters are unknown. The algorithms utilize server idle-time measurements which are sent periodically to the central job scheduler. A model is developed for these measurements, and the result mentioned is used to cast the problem into one of finding a projection of the root of an affine function, when only noisy values of the function can be observed

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

Relay Load Balancing in Queued Cooperative Wireless Networks with Rateless Codes

Relay selection combined with buffering of packets of relays can substantially increase the throughput of a cooperative network that uses rateless codes. However, buffering also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In this paper we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a packet from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the packet is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive explicit necessary and sufficient conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times.

Load Balancing with Availability Checker and Load Reporters (LB-ACLRs) for improved Performance in Distributed Systems

Distributed system has quite a lot of servers to attain increased availability of service and for fault tolerance. Balancing the load among these servers is an important task to achieve better performance. There are various hardware and software based load balancing solutions available. However there is always an overhead on Servers and the Load Balancer while communicating with each other and sharing their availability and the current load status information. Load balancer is always busy in listening to clients' request and redirecting them. It also needs to collect the servers' availability status frequently, to keep itself up-to-date. Servers are busy in not only providing service to clients but also sharing their current load information with load balancing algorithms. In this paper we have proposed and discussed the concept and system model for software based load balancer along with Availability-Checker and Load Reporters (LB-ACLRs) which reduces the overhead on server and the load balancer. We have also described the architectural components with their roles and responsibilities. We have presented a detailed analysis to show how our proposed Availability Checker significantly increases the performance of the system.

ELISA: An Estimated Load Information Scheduling Algorithm for Distributed Computing Systems

In this paper, we present a decentralized dynamic load scheduling/balancing algorithm called ELISA (Estimated Load Information Scheduling Algorithm) for general purpose distributed computing systems. ELISA uses estimated state information based upon periodic exchange of exact state information between neighbouring nodes to perform load scheduling. The primary objective of the algorithm is to cut down on the communication and load transfer overheads by minimizing the frequency of status exchange and by restricting the load transfer and status exchange within the buddy set of a processor. It is shown that the resulting algorithm performs almost as well as a perfect information algorithm and is superior to other load balancing schemes based on the random sharing and Ni-Hwang algorithms. A sensitivity analysis to study the effect of various design parameters on the effectiveness of load balancing is also carried out. Finally, the algorithm's performance is tested on large dimensional hypercubes in the presence of time-varying load arrival process and is shown to perform well in comparison to other algorithms. This makes ELISA a viable and implementable load balancing algorithm for use in general purpose distributed computing systems.

Information and Decision Technologies

Production scheduling in a flexible manufacturing system (FMS) is a real-time combinatorial optimization problem that has been proved to be NP-complete. Solving this problem needs on-line monitoring of plan execution and requires real-time decision-making in selecting alternative routings, assigning required resources, and rescheduling when failures occur in the system. Expert systems provide a natural framework for solving this kind of NP-complete problems.In this paper an expert system with a novel parallel heuristic approach is implemented for automatic short-term dynamic scheduling of FMS. The principal features of the expert system presented in this paper include easy rescheduling, on-line plan execution, load balancing, an on-line garbage collection process, and the use of advanced knowledge representational schemes. Its effectiveness is demonstrated with two examples.

A Flat Concurrent Prolog compiler for PARAM

We describe a compiler for the Flat Concurrent Prolog language on a message passing multiprocessor architecture. This compiler permits symbolic and declarative programming in the syntax of Guarded Horn Rules, The implementation has been verified and tested on the 64-node PARAM parallel computer developed by C-DAC (Centre for the Development of Advanced Computing, India), Flat Concurrent Prolog (FCP) is a logic programming language designed for concurrent programming and parallel execution, It is a process oriented language, which embodies dataflow synchronization and guarded-command as its basic control mechanisms. An identical algorithm is executed on every processor in the network, We assume regular network topologies like mesh, ring, etc, Each node has a local memory, The algorithm comprises of two important parts: reduction and communication, The most difficult task is to integrate the solutions of problems that arise in the implementation in a coherent and efficient manner. We have tested the efficacy of the compiler on various benchmark problems of the ICOT project that have been reported in the recent book by Evan Tick, These problems include Quicksort, 8-queens, and Prime Number Generation, The results of the preliminary tests are favourable, We are currently examining issues like indexing and load balancing to further optimize our compiler.

Multipath routing to provide quality of service in mobile ad hoc networks

Because of frequent topology changes and node failures, providing quality of service routing in mobile ad hoc networks becomes a very critical issue. The quality of service can be provided by routing the data along multiple paths. Such selection of multiple paths helps to improve reliability and load balancing, reduce delay introduced due to route rediscovery in presence of path failures. There are basically two issues in such a multipath routing Firstly, the sender node needs to obtain the exact topology information. Since the nodes are continuously roaming, obtaining the exact topology information is a tough task. Here, we propose an algorithm which constructs highly accurate network topology with minimum overhead. The second issue is that the paths in the path set should offer best reliability and network throughput. This is achieved in two ways 1) by choice of a proper metric which is a function of residual power, traffic load on the node and in the surrounding medium 2) by allowing the reliable links to be shared between different paths.

Coupled Climate Model on Grids

Community Climate System Model (CCSM) is a Multiple Program Multiple Data (MPMD) parallel global climate model comprising atmosphere, ocean, land, ice and coupler components. The simulations have a time-step of the order of tens of minutes and are typically performed for periods of the order of centuries. These climate simulations are highly computationally intensive and can take several days to weeks to complete on most of today’s multi-processor systems. ExecutingCCSM on grids could potentially lead to a significant reduction in simulation times due to the increase in number of processors. However, in order to obtain performance gains on grids, several challenges have to be met. In this work,we describe our load balancing efforts in CCSM to make it suitable for grid enabling.We also identify the various challenges in executing CCSM on grids. Since CCSM is an MPI application, we also describe our current work on building a MPI implementation for grids to grid-enable CCSM.

Compiler/Runtime Framework for Dynamic Dataflow Parallelization of Tiled Programs

Task-parallel languages are increasingly popular. Many of them provide expressive mechanisms for intertask synchronization. For example, OpenMP 4.0 will integrate data-driven execution semantics derived from the StarSs research language. Compared to the more restrictive data-parallel and fork-join concurrency models, the advanced features being introduced into task-parallelmodels in turn enable improved scalability through load balancing, memory latency hiding, mitigation of the pressure on memory bandwidth, and, as a side effect, reduced power consumption. In this article, we develop a systematic approach to compile loop nests into concurrent, dynamically constructed graphs of dependent tasks. We propose a simple and effective heuristic that selects the most profitable parallelization idiom for every dependence type and communication pattern. This heuristic enables the extraction of interband parallelism (cross-barrier parallelism) in a number of numerical computations that range from linear algebra to structured grids and image processing. The proposed static analysis and code generation alleviates the burden of a full-blown dependence resolver to track the readiness of tasks at runtime. We evaluate our approach and algorithms in the PPCG compiler, targeting OpenStream, a representative dataflow task-parallel language with explicit intertask dependences and a lightweight runtime. Experimental results demonstrate the effectiveness of the approach.

Static Balancing of Spring-loaded Planar Revolute-joint Linkages without Auxiliary Links

We present a method to statically balance a general treestructured,planar revolute-joint linkage loaded with linear springs or constant forces without using auxiliary links. The balancing methods currently documented in the literature use extra links; some do not apply when there are spring loads and some are restricted to only two-link serial chains. In our method, we suitably combine any non-zero-free-length load spring with another spring to result in an effective zero-free-length spring load. If a link has a single joint (with the parent link), we give a procedure to attach extra zero-free-length springs to it so that forces and moments are balanced for the link. Another consequence of this attachment is that the constraint force of the joint on the parent link becomes equivalent to a zero-free-length spring load. Hence, conceptually,for the parent link, the joint with its child is removed and replaced with the zero-free-length spring. This feature allows recursive application of this procedure from the end-branches of the tree down to the root, satisfying force and moment balance of all the links in the process. Furthermore, this method can easily be extended to the closed-loop revolute-joint linkages, which is also illustrated in the paper.

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.

An Efficient Load Distribution Strategy for a Distributed Linear Network of Processors with Communication Delays

In this paper, we present an improved load distribution strategy, for arbitrarily divisible processing loads, to minimize the processing time in a distributed linear network of communicating processors by an efficient utilization of their front-ends. Closed-form solutions are derived, with the processing load originating at the boundary and at the interior of the network, under some important conditions on the arrangement of processors and links in the network. Asymptotic analysis is carried out to explore the ultimate performance limits of such networks. Two important theorems are stated regarding the optimal load sequence and the optimal load origination point. Comparative study of this new strategy with an earlier strategy is also presented.

Numerical prediction of load-displacement behaviors of adhesively bonded joints at different extension rates and temperatures

The present work focuses on simulation of nonlinear mechanical behaviors of adhesively bonded DLS (double lap shear) joints for variable extension rates and temperatures using the implicit ABAQUS solver. Load-displacement curves of DLS joints at nine combinations of extension rates and environmental temperatures are initially obtained by conducting tensile tests in a UTM. The joint specimens are made from dual phase (DP) steel coupons bonded with a rubber-toughened adhesive. It is shown that the shell-solid model of a DLS joint, in which substrates are modeled with shell elements and adhesive with solid elements, can effectively predict the mechanical behavior of the joint. Exponent Drucker-Prager or Von Mises yield criterion together with nonlinear isotropic hardening is used for the simulation of DLS joint tests. It has been found that at a low temperature (-20 degrees C), both Von Mises and exponent Drucker-Prager criteria give close prediction of experimental load-extension curves. However. at a high temperature (82 degrees C), Von Mises condition tends to yield a perceptibly softer joint behavior, while the corresponding response obtained using exponent Drucker-Prager criterion is much closer to the experimental load-displacement curve.

Load-Commutated SCR Current-Source-Inverter-Fed Induction Motor Drive With Sinusoidal Motor Voltage and Current

Current source inverter (CSI) is an attractive solution in high-power drives. The conventional gate turn-off thyristor (GTO) based CSI-fed induction motor drives suffer from drawbacks such as low-frequency torque pulsation, harmonic heating, and unstable operation at low-speed ranges. These drawbacks can be overcome by connecting a current-controlled voltage source inverter (VSI) across the motor terminal replacing the bulky ac capacitors. The VSI provides the harmonic currents, which results in sinusoidal motor voltage and current even with the CSI switching at fundamental frequency. This paper proposes a CSI-fed induction motor drive scheme where GTOs are replaced by thyristors in the CSI without any external circuit to assist the turning off of the thyristors. Here, the current-controlled VSI, connected in shunt, is designed to supply the volt ampere reactive requirement of the induction motor, and the CSI is made to operate in leading power factor mode such that the thyristors in the CSI are autosequentially turned off. The resulting drive will be able to feed medium-voltage, high-power induction motors directly. A sensorless vector-controlled CSI drive based on the proposed configuration is developed. The experimental results from a 5 hp prototype are presented. Experimental results show that the proposed drive has stable operation throughout the operating range of speeds.