Load Balancing Problems For Parallel And Distributed Computing

Emerging multi-core computing and cloud computing, as well as cluster computing currently have become main three computing paradigms. Industry and research community have generally accepted that the universal multi-core parallel computing is now growing as a future mainstream computing paradigm. Multi-core clusters are coming from the introduction of multi-core processors within the compute nodes and the trend towards building clusters out of a larger number of smaller compute nodes. Cloud computing is a specialized distributed computing paradigm and has recently gained extensive attention from both research community and industry. Multi-core, cluster or cloud computing systems, with an increasing number of cores, compute nodes or concurrent client requests for providing cloud services, are encountering performance and scalability issues to be urgently addressed. Load balancing technology can effectively exploit potential enormous compute power available on parallel and distributed systems and can achieve scalability, and some load balancing problems for parallel and distributed computing need to be investigated.This dissertation frames the research landscape with applicability-, topology-and software/programmability-driven research perspectives to study load balancing problems, and the main work includes following:1) Aiming at the general problem of dynamic load balancing (DLB), the major goal of load balancing is presented, and a general model for dynamic load balancing problem is developed, based on which a locality-constrained dynamic load balancing problem is also proposed. Following that, a comprehensive taxonomic approach to classifying DLB strategies is proposed.2) Aiming at the applicability issue of load balancing strategies, a greedy dynamic load balancing (GDLB) strategy is investigated. The presented GDLB strategy can achieve a better tradeoff between simplicity and performance. It performs well in prediction time and scale by applying this strategy to large-scale traffic flow predicting based on BP and SVM.3) As the traditional work-stealing (WS) strategies may suffer from high communication costs for applications transferring large amounts of data or platforms with large-scale and complex network topologies, a hierarchical WS strategy, namely DaCHWS, is presented for divide-and-conquer computation, and experimental results show that the DaCHWS strategy outperforms work-sharing and Statin-CRS strategies in a number of performance metrics such as speedup, CPU utilization and load distribution.4) A hierarchical dynamic load balancing strategy based on generalized neural network (GNN), considering the communication overhead and time-varying delay feature, is presented for large-scale distributed computing systems, and the simulation results demonstrate that the strategy outperforms other strategies in terms of communication and load balancing overhead. Aiming at the hierarchical structure characteristics of multi-core clusters, on which the intra-node communication cost has become a key factor to be considered in the task allocation problem (TAP), a new TAP (MCTAP), which aims at minimizing the intra-and inter-node communication cost, and total computing cost, is proposed. And then the thesis analyzes and proves the effects of the intra-node communication cost on the complexity of the MCTAP via constructing equivalence relation between the MCTAP and minimum cost flow problem. In order for solving the MCTAP, a solution model is presented. The excellent results indicate that presented solution model to the MCTAP is more efficient and faster than existing approaches when a large number of tasks communicate.5) Aiming at the core goal of multi-core universal parallel computing achieving required performance and productivity gains, a lightweight user-level multithreaded parallel program-ming library based on WS scheduler is developed. The library is built upon task primitive concept, and supports two patterns for expressing logical parallelism, namely data parallelism and task parallelism. The library can simplify parallel programming by encapsulating complexity for obviating the need for programmer to worry about locking and races, and thus increases productivity. The implementation performance techniques surround WS load balancing scheduling algorithm, efficient construction and management of task queues. The measured performance shows good parallel speedups comparable to that of Microsoft TPL but also suggests possible improvements and some issues to be further investigated. Furthermore, several key issues for future research on multi-core software are analyzed.