This paper investigates dynamic load balancing issues in the multidomain environment where local area networks (LANs) are interconnected by the Internet. Because of the much slower Internet communication speed and limited bandwidth, existing load balancing algorithms for LANs are unsuitable for the multidomain environment. New issues such as lag time in updating load information and network cost of transferring jobs must be addressed. To tackle these problems, the conventional least load scheduler is extended to the multidomain environment by employing a hierarchical structure, and several quick update techniques are proposed. Also, a heuristic taking both the machine load and the network cost into consideration is developed to evaluate the benefits of sending jobs to computers in different domains. A set of experiments conducted on the BALANCE testbed showed that the proposed techniques provide significant performance improvement over existing algorithms.

This paper presents a hydrodynamic framework to solving the dynamic load balancing problem in heterogeneous distributed systems. In this approach, each processor is viewed as a liquid cylinder where the cross-sectional area corresponds to the capacity of the processor, the communication links are modeled as liquid channels between the cylinders, the workload is represented by liquid, and the load balancing algorithm manages the flow of the liquid. It is proven that all algorithms under this framework converge geometrically to the state of equilibrium, in which the heights of the liquid columns are the same in all the cylinders. In this way, each processor obtains an amount of workload proportional to its capacity. A hydrodynamic algorithm is presented and its performance is evaluated. The algorithm is applied to solve several practical applications to demonstrate the applicability of the framework.

The paper investigates the use of group communication to improve the efficiency of load balancing in interconnected LANs. Conventional load balancing techniques usually assume point-to-point connections among the computers and typically work on a single LAN only. This may waste network bandwidth and lengthen the load balancing time in LANs that support group communication such as the Ethernet. To tackle this problem a two level algorithm is proposed. At the LAN level, all computers in a LAN maintain loading information in the entire LAN using a globally ordered group channel. The workload in the different LANs is balanced by moving load from the overloaded LANs to the underloaded ones. It is proved that the proposed algorithm converges to the state of global balance geometrically. Experimental results show that the algorithm reduces load balancing time and network utilization significantly, compared to the single level algorithm without group communication.

This paper presents the design philosophy and implementation of the BALANCE system. BALANCE is a flexible, network independent and computer architecture independent load balancing system which allows the building of reusable parallel and distributed applications. By implementing related services as bi generic servers with their connection endpoints registered in BALANCE, the clients can easily access the servers by server system calls. To demonstrate the flexibility of BALANCE, several widely different applications have been implemented and evaluated, including system servers, parallel and distributed applications and a scheduling testbed. The use of generic servers to improve system modularity and code reuse is also discussed. © 1997 John Wiley & Sons, Ltd.

The problem of allocating task interaction graphs (TIGs) to heterogeneous computing systems to minimize job completion time is investigated. The only restriction is that the interprocessor communication cost is the same for any pair of processors. This is suitable for local area network based systems, such as Ethernet, as well as fully interconnected multiprocessor systems. An optimal polynomial solution exists if sufficient homogeneous processors and communication capacity are available. This solution is generalized to obtain two faster heuristics, one for the case of homogeneous processors and the other for heterogeneous processors. The heuristics were tested extensively with 60,900 systematically generated random TIGs and shown to be stable independent of the size of the TIG. A performance model is also proposed to predict the performance of the heuristic algorithms, and it is successful in explaining the experimental results qualitatively.

The design philosophy and implementation of the BALANCE system is described. BALANCE is a flexible, network independent and computer architecture independent load balancing system which is designed to support a wide range of software, including parallel and distributed applications as well as schedulers. The generic server and server system call structures are used as bases to enhance flexibility and to build complex services. BALANCE is not tied to a particular scheduling algorithm, rather the users are allowed to build their own schedulers. To demonstrate the flexibility and power of BALANCE, a set of system services and scheduling algorithms has been implemented and evaluated. A new delay scheduling algorithm which postpones the execution of jobs in high load situation is proposed. It is shown that this algorithm effectively improves system throughput and yet bounds the response times for the console commands.

Distributed systems such as networks of workstations are becoming an increasingly viable alternative to traditional supercomputer systems for running complex scientific applications. A large number of these applications require solving sets of partial differential equations (PDEs). In this paper, we describe the implementation and performance of SPEED (Scalable Partial differential Equation Environment on Distributed systems), a parallel platform which provides an efficient solution for time-dependent PDEs. SPEED allows the inclusion of a wide range of parameters and programming aids. PVM is employed as the underlying message-passing system. The parallel implementation has been performed using two algorithms. The first algorithm is a two-phase scheme which uses the conventional technique of alternating phases of computation and communication. The second algorithm employs a pre-computation technique that allows overlapping of computation and communication. Both methods yield significant speedups. The pre-computation technique reduces the communication time between the workstations but incurs additional overhead in buffer management. Hence, if the saving in communication time is larger than the overhead, the pre-computation technique outperforms the two-phase algorithm. SPEED also provides a performance prediction methodology that can accurately predict the performance of a given application on the system before running the application. This methodology allows the user to tune various parameters in order to identify system bottlenecks and maximize the performance.

The paper describes the implementation and performance of a parallel platform for solving partial differential equations (PDEs) on distributed systems. The platform has been implemented using PVM for a network of workstations. It allows the inclusion of a wide range of parameters and programming aids. The PDEs are specified in the form of finite difference equations. With a given set of parameters and a partitioning strategy, the platform provides facilities to record and predict the performance of an application before running it. The performance prediction model helps the user to identify the major bottlenecks of the platform such that by reducing them, the speedup can be improved. We also present analysis of various factors that can have drastic effect on the speedup, which allows the user to tune a number of parameters to maximize the performance.

The use of a network of workstations as a single unit for speeding up computationally intensive applications is becoming a cost-effective alternative to traditional parallel computers. We present the implementation of an application-driven parallel platform for solving partial differential equations (PDEs) on this computing environment. The platform provides a general and efficient parallel solution for time-dependent PDEs and an easy-to-use interface that allows the inclusion of a wide range of parallel programming tools. We have used two different parallelization methods in this platform. The first method is a two-phase algorithm which uses the conventional technique of alternating computation and communication phases. The second method uses a novel pre-computation technique which allows overlapping of computation and communication. Both methods yield significant speedup. However the pre-computation technique is shown to be more efficient and scalable.>