超大规模分布式系统负载平衡研究

论文摘要

经半个世纪的努力,计算机硬件设计已获得令人不可思议的提升并趋向于高性能低开销化。例如:IBM正在试图研发的蓝色基因P的目标是达到峰值1petaflops,处理节点达到256K个。在如此大规模分布式系统中,如果不能实现合理任务调度将使世界顶级计算机无用武之地。在国家自然科学基金赞助下,本文针对超大规模分布式系统负载平衡问题展开深入研究。主要工作包括以下几方面:首先,研究并分析了几种典型的完全集中式以及分布式策略在解决超大规模分布式系统负载平衡的局限性。集中式策略包括:贪婪策略（GreedyLB）、精细化策略（RefineLB）、正交递归半分策略（orthogonal recursive bisection algorithm,OrbLB）、贪婪通信策略（GreedyCommlLB）。分布式策略包括:相邻分配策略（Neighborhood Averaging）、任务偷取策略（Work-Stealing）。并通过仿真实验验证了集中式负载平衡策略在内存开销以及负载平衡开销存在的瓶颈以及分布式负载平衡策略CPU利用率低等缺点。其次,研究并分析了解决超大规模分布式系统负载平衡问题经典策略所存在的缺陷。包括层次策略以及混合式负载平衡策略的通讯开销以及负载平衡开销。然而,以上所有策略都是基于通讯是固定的或是不考虑通讯延迟开销,近几年的研究发现延迟依赖于通讯介质呈现出时变性。这是由于网络中的通信量、阻塞情况以及一些未知因素所决定。目前提出的基于延迟的负载平衡策略并不能针对该特性进行有效预测。最后,本文根据大规模分布式系统通讯开销时变的特点,提出一种基于随机延迟论的层次结构负载平衡策略。此策略具有以下三个特点:（1）应用通讯优化的层次结构减小超大规模机群的负载平衡开销。（2）考虑到节点计算速率以及通讯介质的随机延迟性。（3）通过广义神经网络理论建模进行延迟预测,从而优化任务通讯延迟及迁移延迟。此方法为基于延迟的一类负载平衡策略提供了优化方案。仿真实验验证了应用广义神经网络进行延迟预测优于目前同类预测算法,适用于超大规模机群。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 研究现状及分析
• 1.2.1 传统分布式系统负载平衡研究现状
• 1.2.2 超大规模分布式系统负载平衡研究现状
• 1.2.3 负载平衡框架研究现状
• 1.3 超大规模分布式系统负载平衡研究难点以及技术路线
• 1.4 本文的主要工作
• 1.5 本文组织结构
• 2 动态负载平衡框架
• 2.1 负载平衡问题
• 2.1.1 基本定义
• 2.2 负载平衡相关工作
• 2.2.1 非迭代应用
• 2.2.2 可预测迭代应用
• 2.2.3 不可预测迭代应用
• 2.2.4 分割算法
• 2.3 实际负载平衡方法论
• 2.3.1 负载指标的选择
• 2.3.2 负载信息的收集方式
• 2.3.3 负载信息的管理
• 2.3.4 负载平衡策略
• 2.4 CHARM++负载平衡框架
• 2.5 小结
• 3 传统分布式系统负载平衡策略研究与分析
• 3.1 集中式负载平衡策略研究与分析
• 3.1.1 GreedyLB
• 3.1.2 RefineLB
• 3.1.3 OrbLB
• 3.1.4 GreedyCommlLB
• 3.1.5 各种集中式算法性能比较与分析
• 3.2 分布式负载平衡策略研究与分析
• 3.2.1 相邻分配策略
• 3.2.2 Work-Stealing策略
• 3.2.3 各种分布式算法性能比较与分析
• 3.3 小结
• 4 超大规模分布式系统负载平衡策略研究与分析
• 4.1 层次结构负载平衡策略
• 4.2 混合式负载平衡策略
• 4.3 基于随机延迟的负载平衡策略
• 4.4 各种超大规模分布式系统负载平衡策略性能比较与分析
• 4.4.1 层次结构与混合式结构负载平衡策略性能比较
• 4.4.2 基于随机延迟负载平衡策略性能比较
• 4.5 小结
• 5 一种新的基于广义网络的层次结构负载平衡策略（GNNLB）
• 5.1 引言
• 5.2 传统模型的不足
• 5.3 新的广义神经网络模型的提出
• 5.4 新的广义神经网络模型完整建模
• 5.4.1 智能神经元模型
• 5.4.2 基于广义神经网络延迟预测模型及其学习算法
• 5.4.3 新的超大规模负载平衡框架
• 5.4.4 负载平衡过程
• 5.4.5 层次结构负载平衡策略
• 5.5 新的基于广义神经网络预测模型性能比较与分析
• 5.5.1 GNNLB与传统集中式策略相比较
• 5.5.2 GNNLB与传统分布式策略相比较
• 5.5.3 GNNLB与混合式策略相比较
• 5.5.4 GNNLB与其它随机延迟模型相比较
• 5.6 小结
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢