【作者】 杨际祥；

【导师】 谭国真；

【作者基本信息】 大连理工大学 ， 计算机应用技术， 2012， 博士

【摘要】 多核计算、集群计算以及新兴的云计算成为当前的主要计算模式。多核大众化并行计算成为未来计算的主流已成为工业界与学术界的共识,基于多核节点的多核集群成为高性能计算(HPC)的一种发展趋势,而云计算作为一种特定的分布式计算,近年来受到了工业界和学术界的广泛关注。随着多核、集群系统的核数与计算节点数目的不断增长,以及要求提供云服务的用户数量不断增多,对计算的性能和可扩展性的需求从来没有像目前这样迫切过。负载均衡作为提高并行与分布式计算性能和可扩展性的一个关键技术,相关问题亟待得到研究与解决。本文主要从可应用性驱动、结构驱动和软件驱动三个方面对并行与分布式计算的负载均衡问题展开了研究。本文的主要研究工作如下：(1)针对动态负载均衡(DLB)的基本问题,给出了DLB的主要目标和基本定义,在此基础之上,给出了DLB问题的一种形式化描述；根据DLB策略的主要特征提出了-个综合分类方法。(2)针对负载均衡策略的可应用性问题,研究了在简单性和性能之间可获得一个较好折中的贪婪动态负载均衡(GDLB)策略。将GDLB策略应用于基于BP和SVM的大规模交通流并行预测问题,可提高预测速度和规模。(3)传统的Work-Stealing(简称WS)策略在面临需要传输大量数据的应用和具有层次结构的平台时,它的通讯时间通常令人无法忍受。针对该问题以及分治计算问题,本文提出了一种层次结构的WS (DaCHWS)策略,实验结果验证了DaCHWS策略性能优于Work-Sharing和Satin-CRS策略。(4)考虑了大规模分布式计算系统的通讯延迟开销和延迟时变性特征,提出一种基于广义神经网络的层次结构动态负载均衡(GNNDLB)策略,仿真实验验证了GNNDLB策略优于同类策略：针对多核集群通讯的层次结构特征,考虑了节点内冲突代价,提出了以最小化计算代价、节点间通讯代价和节点内冲突代价的总代价为目标的多核集群任务分配问题,通过建立任务分配问题与最小费用流问题的等价关系来分析并证明节点内冲突代价对问题复杂性的影响关系,并给出了一个求解模型,理论分析和实验结果验证了相应理论结果的正确性和求解模型的有效性。(5)针对多核大众化并行计算的提高多核应用程序开发产能同时获得并行性能收益这个核心目标,设计并实现了一个轻量级的基于用户层次的WS调度策略的多核多线程并行编程库(UCMLib)。该库基于任务原语概念,提供了数据并行性和任务并行性两种并行模式,对多线程编程的复杂性进行了封装和抽象,为开发者提供高级的编程方法而不必显示地考虑锁和竞争,简化并行编程难度,提高开发效率。性能测试表明,当计算规模较大时,UCMLib在数据并行性与任务并行性两方面获得了比TPL库略优的加速比。此外,分析了未来多核软件研究的几个关键问题。更多还原

【Abstract】 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.更多还原