并行与分布式计算负载均衡问题研究

发布时间：2020-01-21 17:59

【摘要】：多核计算、集群计算以及新兴的云计算成为当前的主要计算模式。多核大众化并行计算成为未来计算的主流已成为工业界与学术界的共识,基于多核节点的多核集群成为高性能计算(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库略优的加速比。此外,分析了未来多核软件研究的几个关键问题。
【学位授予单位】：大连理工大学
【学位级别】：博士
【学位授予年份】：2012
【分类号】：TP338

【参考文献】