Load Balancing in Parallel and Distributed Databases

This dissertation addresses the load balancing problem for parallel computations in the presence of time delays from a control system design perspective. Extensive experiments in a parallel computing environment have been made to evaluate load balancing strategies, and have driven the continued evolution of the parallel computation model and the load balancing strategies.

The critical feature of the load balancing problem is the delayed receipt of information and transferred load. In this work, load balancing in a parallel computer architecture is first modeled as a deterministic time-delay system with saturations. Three essential properties of the load balancing strategy, including consistency, stability, and conservation of tasks, have been analyzed. The excess load on each sending node is portioned out among the other nodes according to the amounts they are below the sending node's estimate of network average load. It is found that the feedback gain in the controller (load balancer) on each node affects the performance of load balancing, and a judicious choice of the feedback gain is necessary to achieve a faster balancing response without breaking into oscillatory behavior.

Load distribution and task processing contend for the same resources on each computational element (node). A deterministic dynamic nonlinear system is developed to model load balancing for parallel computations and incorporate both time delays and resource constraints. This model accounts for the trade-off between using processor resources to process tasks and the advantage of distributing the load evenly between the nodes to reduce overall processing time. The model is shown to be consistent and the open-loop system is Lyapunov stable, but not asymptotically stable. A distributed closed-loop controller is proposed to balance load dynamically at each node by using not only local estimates of loads at other nodes, but also estimates of the number of tasks in transit to it. Experimental results have demonstrated substantial improvements in performance using a controller based on the anticipated estimates of workloads over using a controller based on the local workloads only.

The eventual size and the search requirements for DNA databases necessitate the development of parallel DNA databases. This work presents the design of a parallel DNA database, which is the motivation and an application of the presented load balancing strategies. DNA profiles are assigned in portions to each search engine node of the parallel computer to form distributed databases to be searched in parallel. A multi-threaded search server is designed and implemented to achieve high performance. Experimental results for the parallel DNA database and parallel searches with load balancing integrated with the database demonstrate both the efficiency of the parallel database and the efficacy of the load balancing strategy.