Search

Abstract. In many computing and networking applications, arriving tasks have to be routed to one of many servers, with the goal of minimizing queueing delays. When the number of processors [...]

We consider the network loading problem (NLP) under a polyhedral uncertainty description of traffic demands. After giving a compact multicommodity flow formulation of the problem, we state a decomposition property [...]

The implementation and performance of network scheduling schemes for time-domain wavelength interleaved networks. The efficiency of p roposed distributed schemes is comparable to centralized schedulers at over 90%.

One of the main obstacles in obtaining high performance from heterogeneous distributed computing (HDC) system is the inevitable communication overhead. This occurs when tasks executing on different computing nodes exchange data or the assigned sub-task size is very small. In this paper, we present adaptive pre-task assignment (APA) strategy for heterogeneous distributed raytracing system. In this strategy, the master assigns pre-task to the each node. The size of sub-task for each node is proportional to the node's performance. One of the main features of this strategy is that it reduces the inter-processes communication, the cost overhead of the node's idle time and load imbalance, which normally occurs in traditional runtime task scheduling (RTS) strategies. Performances of the RTS and APA strategies are evaluated on manager/master and workers model of HDC system. The experimental results of our proposed (APA) strategy have shown a significant improvement in the performance over RTS strategy. Keywords: Task partitioning and scheduling: Load balancing: Heterogeneous distributed computing; Runtime task scheduling strategy; Adaptive pre-task assignment strategy; Distributed image/raytracing computing; Performance evaluation

A hybrid wireless network is an extension to an infrastructure network, where a mobile host may connect to an access point (AP) using multihop wireless routes via other mobile hosts. The APs are configured to operate on one of multiple available channels. Mobile hosts and wireless routers can select their operating channels dynamically through channel switching. In this environment, we propose a routing protocol that finds routes to balance load among channels while maintaining connectivity. The protocol works with nodes equipped with a single network interface, which distinguishes our work with other multichannel routing protocols that require multiple interfaces per node. The protocol discovers multiple routes to multiple APs, possibly operating on different channels. Based on traffic load information, each node selects the 'best' route to an AP and synchronizes its channel with the AP. With this behavior, the channel load is balanced, removing hot spots and improving channel utilization. The protocol assures that every node has at least one route to an AP, where all intermediate nodes are operating on the same channel. Our simulation results show that the proposed protocol successfully adapts to changing traffic conditions and improves performance over a single-channel protocol and a multichannel protocol with no load balancing. Index Terms--Communication system routing, communication systems, load-balancing, multi-channel, multi-hop, protocols, routing.

Significant effort has gone into designing robust adaptive beamforming algorithms to improve robustness against uncertainties in array manifold. These uncertainties may be caused by uncertainty in direction-of-arrival (DOA), imperfect array calibration, near-far effect, mutual coupling, and other mismatch and modeling errors. A diagonal loading technique is obligatory to fulfill the uncertainty constraint where the diagonal loading level is amended to satisfy the constrained value. The major drawback of diagonal loading techniques is that it is not clear how to get the optimum value of diagonal loading level based on the recognized level of uncertainty constraint. In this paper, an alternative realization of the robust adaptive linearly constrained minimum variance beamforming with ellipsoidal uncertainty constraint on the steering vector is developed. The diagonal loading technique is integrated into the adaptive update schemes by means of optimum variable loading technique which provides loading-on-demand mechanism rather than fixed, continuous or ad hoc loading. We additionally enrich the proposed robust adaptive beamformers by imposing a cooperative quadratic constraint on the weight vector norm to overcome noise enhancement at low SNR. Several numerical simulations with DOA mismatch, moving jamming, and mutual coupling are carried out to explore the performance of the proposed schemes and compare their performance with other traditional and robust beamformers. Index Terms--Adaptive beamforming, Capon beamformer, conjugate gradient, constrained optimization, diagonal loading, linearly constrained minimum variance (LCMV) beamforming, moving jamming, mutual coupling, steepest descent.

Abstract: The emergence of the grid computing constituted by several resources stood out as platform of development for the industrial applications treating big quantities of data. In these environments of [...]

Abstract We consider the problem of redistributing data on homogeneous and heterogeneous rings of processors. The problem arises in several applications, after each invocation of a load-balancing mechanism (but we […]

Abstract: Load balancing is a generally concerned problem in peer-to-peer (P2P) systems. Many researches on load balancing in the structured P2P systems have been launched currently, such as Chord or [...]

The approximate algorithms for placing a set of documents into M distributed web server is studied. A static document placement algorithm determines the mapping from each document to a server, and allows another algorithm to place the documents into the servers.

The interest of coupling load balancing with asychronism in algorithms is studied. After proposing a noncentralized version of dynamic load balancing which is best suited to asynchronism, its efficiency by some experiments on a general Partial Differential Equation (PDE) problem is verified.

Processing of divisible loads in systems with memory hierarchies is investigated and discussed.

A new approach is described that can be applied by a parallelizing compiler to obtain the iteration and data decompositions that minimize communication and load imbalance overheads in parallel programs that target Non-Uniform Memory Access (NUMA) architectures.

A taxonomy of redirection schemes in distributed Web systems is presented and discussed.

Parallel merge sort is useful for sorting a large quantity of data progressively. The merge sort should be parallelized carefully since the conventional algorithm has poor performance due to the successive reduction of the number of participating processors by half, and down to one in the last merging stage. The proposed load-balanced merge sort utilizes all processors throughout the computation. It evenly distributes data to all processors in each stage. Thus every processor is forced to work in all phases. Significant performance enhancement has been achieved up to a speedup of (P - 1)/log P where P is the number of processors. Experimental results demonstrate a speedup of 9.6 (upper bound of 10.7) on 32-processor Cray T3E when sorting 4M 32-bit integers, and a speed up of 2.3 (upper bound of 2.8) on an 8-node PC cluster. KEY WORDS: Merge sort; parallel algorithm; load balancing; splitter.

Opportunity cost algorithms are proposed for online assignment of jobs to machines in computing clusters (CC). The new approach is based on known theoretical results.

An application-centric characterization is presented of dynamic domain-based inverse space-filling curve partitioning techniques for distributed adaptive grid hierarchies that underlie structured adaptive mesh refinement (SAMR) applications.

Multiagent computing on clusters of workstations is discussed. Load balancing and agent theory are brought into a single perspective.

A distributed architecture for question-answering systems is presented. Experimental results indicate that a proposed load-balancing strategy is superior, compared with two traditional approaches.

Load sharing strategies are discussed. The aim is to improve performance of cluster systems by coordinating the use of CPU and memory resources.

An efficient partitioning algorithm is proposed, for dealing with the scalability issue of designing a large-scale distributed virtual environment (DVE) system. The virtual world is divided into partitions, which are assigned to different servers.

An all-to-all broadcast algorithm is proposed, for multidimensional all-port mesh and torus networks. A broadcast pattern is described that ensures a balanced traffic load in all of a network's dimensions, allowing the all-to-all broadcast algorithm to achieve near-optimal transmission time.

An innovative approach is proposed to resolve the dynamic load balancing problem for adaptive meshes. The approach relies on symmetric broadcast networks (SBN) as the communication topology.

It is shown that in a dynamic load balancing model that allows customers to choose between the shortest of two servers produces an exponential improvement, compared to distributing customers uniformly at random.

Implementation of matrix multiplication on heterogeneous computing platforms is discussed. Two classes of heterogeneous resources are examined: heterogeneous networks of workstations, and collections of heterogeneous clusters.

How a genetic algorithm can be used to used to solve a problem involving dynamic load-balancing is investigated. An algorithm is developed whereby optimal or near-optimal task allocations are 'evolved' during the operation of a parallel computing system.

A discussion of neural algorithms in a problem-oriented parallel language is presented. Topics include domain-specific language, load balancing, neural networks, node parallelism, connection location, and the cost of data distribution.

A discussion of dynamic load balancing problems within a hydrodynamic framework is presented, focusing on heterogeneous distributed systems. Topics include communication networks, global potential energy and fairness, liquid flow in a load balancing process, and the effects of topology on convergence rates.

The design and implementation of an intelligent load-management system not based on network address translation (NAT) and virtual Internet protocol (IP) addresses is described. The new solution can be integrated into existing offerings from Lucent Technologies, such as the Cajun P550 Gigabit Routing Switch.

Research was conducted to examine a bus oriented network characterized by a charge for the amount of divisible load processed on each processor. The network model used processors interconnected through a bus type communication channel. Algorithms were utilized to minimize computing costs with an upper bound on solution time. Results showed that the minimal total computing cost can be achieved by arranging the sequence of the processors to receive the workload at an earlier rate.

In distributed multimedia servers where client requests for different video streams may have different probabilities, placement of video streams is an important parameter because it may result in unbalanced requests to the system's stations, and thus to high blocking probabilities of requests. We present a method, MMPacking, to balance traffic load and storage use in a distributed server environment. Since different video streams are requested by clients with different rates, video stream replication is used to balance the traffic patterns of the stations; thus, the requests and 1/0 usage of the stations are balanced, since replication allows requests for the same video stream to be routed to different stations. MMPacking achieves load balancing by producing at most N - 1 replicas of video streams in a system with N servers. These replicas are distributed among the stations so that storage balancing is achieved as well, since no station stores more than two video streams more than any other station in the system. Index Terms - Distributed multimedia server(s), load balancing, multimedia, storage balancing, video-on-demand.

Parallel computer architecture systems may be used for real-time data and signal processing applications and may require both static and dynamic load balancing (resource allocation) prior to and during run-time. The literature reveals that each class of parallel computer architecture and its application can require a different approach to static and dynamic load balancing. Common classes of target parallel computer architectures are 1) multiprocessors (shared and distributed memories), 2) distributed processors, and 3) dataflow architectures. This paper addresses a proposed parallel hybrid dataflow architecture, a scalable dynamic load balancing circuit for the proposed architecture, and performance analysis, first, of the load balancing circuit and, second, the architecture using the load balancing circuit. The contributions and focus of this paper are: 1) that it first describes the requirements for and the framework of a parallel, medium to coarse grain, hybrid token controlled dataflow architecture. This paper only deals with real-time applications of the architecture. 2) The paper next describes the dynamic load balancing strategy for the hybrid dataflow architecture and a resulting mathematical model of the load balancing function required by the load balancing strategy. 3) The organization, design, and implementation of a basic digital circuit suitable for VLSI implementation which implements the mathematical model of the load balancing function required by the architecture is next presented. This circuit implements a control token mapping function and is therefore called a 'token mapper.' 4) It is next shown that the basic dynamic load balancing circuit (token mapper) design is scalable therefore allowing the hybrid dataflow architecture to be scalable. 5) The performance of the dynamic load balancing circuit is then analyzed at both the circuit and architectural systems level. A parallel simulation of the proposed parallel hybrid dataflow architecture employing its presented dynamic load balancing circuit was developed for two example applications and used for architectural system level performance analysis. Analysis of simulation results verified correct operation of the proposed hybrid dataflow system architecture and its dynamic load balancing circuit. Index Terms - Dataflow computer architectures, distributed computer systems, dynamic load balancing, hybrid dataflow computer architecture, multiprocessor computer architectures, parallel computer architecture, parallel signal processors, run-time resource allocation, static load balancing, task (process) allocation.

Buddy sets, preferred lists, and region-change broadcasts communication activities are related to the load sharing (LS) distributed scheduling process, which distributes overflow tasks evenly over the entire system and reduces LS-related traffic in Hexagonal Architecture for Real-Time Systems (HARTS). LS algorithms, and routing and broadcasting algorithms of HARTS develop a continuous time Markov chain to model task arrival, completion, and transfer activities. The hexagonal mesh topology and virtual cut-through property of HARTS are used to determine the distribution of packet delivery and task waiting time. LS performance is analyzed by event-driven simulators.

The Paralex program enables the development and execution of complex parallel applications on distributed systems. The programming environment of Paralex utilizes graphics extensively to edit, execute, and debug parallel scientific applications. Paralex automatically renders programs fault-tolerant by employing passive replication. A new use of replication helps implement dynamic load balancing. The principal components of Paralex and its prototype running on Unix workstations are presented.

Inverse Spacefilling Partitioning (ISP) is an efficient load balancing technique for localized non-uniform work using distributed memory MIMD parallel computers. A comparison of ISP with Orthogonal Recursive Bisection and Median of Medians variant of ORB, ORB-MM, indicates that ISP and ORB-MM outperform ORB. ISP software engineering is superior to ORB-MM as it has no detailed bookkeeping. The use of mesh by ISP algorithm reduces communication overheads and causes faster partitioning times, thus creating highly efficient and conceptually simpler partitioning.

Two new dynamic task allocation methods for large distributed computing systems are introduced. The two, which are the clustering simulated annealing model and the mean field annealing model, balance the load by optimizing resource allocation and minimizing interprocessor communication based on the simulated annealing process and other deterministic techniques. According to simulations, the two provide faster convergence over pure simulated annealing or deterministic procedures.

A study of a thread-based runtime support system, named P kernel, which can run multiple instruction multiple data (MIMD) software on single instruction multiple data (SIMD) shows that for application problems with irregular and/or unpredictable features, automatic scheduling can move some thread from overloaded processors to underloaded processors. Furthermore, the granularity of threads can be controlled to reduce system overhead. The P kernel is also able to handle book keeping and message management, as well as to make these lowering level tasks user-friendly.