论文部分内容阅读
负载平衡是并行计算中的一个重点研究领域,节点间负载的不平衡会严重影响并行计算的效率。负载平衡算法按照调度时可用资源信息和任务运行状态的即时性可划分为静态和动态两种,其中动态负载平衡算法由于其灵活性和处理非规则问题时所具有的优势逐渐成为研究的热点。时延现象在并行计算环境中是普遍存在的,尤其在分布式存储结构情况下,在动态负载平衡的过程中,并行系统为了保持信息的准确性及实现过量负载的迁移不可避免地要进行大量的通信和传输,在这类过程中均会产生不同程度的时延。时延给准确地收集和管理负载信息带来了困难,很容易引起动态负载平衡算法的一些不稳定的振荡现象,从而严重地影响并行计算的效率。因此,如何有效地分析及减少时延所带来的影响成为动态负载平衡中亟待解决的重要问题之一。针对此情况,本文采用了控制论中的线性时延系统理论对分布式存储结构下的时延动态负载平衡(DDLB: Delay Dynamic Load balancing)系统进行建模和稳定性分析,并以此为依据,通过使用适当的反馈增益来减少时延所带来的影响。 首先,针对并行环境下的DDLB系统,本文在前人工作的基础上,提出了一个更贴近实际的频域模型,并在其基础上给出了一个与之等价的异构时域模型。两类模型充分地考虑了实际并行环境下任务的不可划分性和负载队列的非负性,描述了现实环境中影响DDLB系统稳定性的外界干扰因素。同时,负载平衡阈值的引入增加了模型的灵活性,使其能够在负载平衡质量与负载平衡速度之间做出一个符合实际要求的折中。最后,根据控制论中的稳定性理论,本文提出了一些符合实际环境的假设和定义,并在其基础上将所提出的时域模型转换为便于时域分析的标准形式,为后续的理论分析工作奠定基础。 其次,针对所提出的频域模型,本文提出了DDLB系统稳定性的充分必要条件。采用了频域分析方法对DDLB系统的同构模型进行稳定性分析,通过laplace变换及一系列矩阵变换推导出系统的传递函数矩阵,并根据Routh-Hurwitz判据,通过分析时DDLB系统的闭环极点得出了系统渐近稳定的充分必要条件,从而找到了时延、系统规模及负载平衡增益之间较为直观的近似关系。同时,在所得出DDLB系统稳定性的充分必要条件的基础上,提出了一种基于局部优化的自适应控制策略,与原有局部优化方法相比,本文所提出的方法在对实际控制增益进行优化调节的同时,还保证了DDLB系统的稳定性,在一定程度上弥补了传统局部优化自适应控制方法的不足,使得本文所提出方法更加接近实际应用。 再次,为了清晰地揭示各类时延对动态负载平衡稳定性的影响,本文提出了常数时延条件下DDLB系统稳定性的充分条件。在常数时延情况下采用了时域分析方法对DDLB系统的异构模型进行了稳定性分析。通过选取适当的Lyapunov-Krasovskii泛函,使用Newton-Leibniz公式、Moon不等式及矩阵的Schur补性质得出了系统渐进稳定的充分条件,拓展了分析结果的理论适用范围,并通过引入指数稳定的概念提高系统的收敛速度,所得出结论适用于时延变化较小的动态负载平衡系统。 同时,针对时延变化较大的异构动态负载平衡系统,本文提出了时变时延条件下DDLB系统稳定性的充分条件。通过选取适当的Lyapunov-Krasovskii泛函,使用积分的基本性质、Jenssen不等式及矩阵的Schur补性质得出了时变时延情况下系统指数稳定的充分条件,该条件适用于时延在一定区间内变化且其变化率有界的动态负载平衡系统。另外,在上述稳定性分析工作的基础上,本文将几类稳定性条件转换为标准的LMI优化问题,并通过使用Matlab中的LMI工具箱对动态负载平衡系统的理论增益值进行求解。 最后,针对实际DDLB系统,本文给出了一种基于多线程的离散事件模拟方法,并其基础上对理论分析中的各类情况进行了模拟验证。实验结果表明,DDLB系统的最优负载平衡增益与传输及通信时延成反比,与系统规模及负载平衡时延成正比,通信、传输时延、系统规模及信息确定化程度对动态负载平衡系统的稳定性均有较大的影响,通过选择适当的划分策略及负载平衡增益可以有效地减少这一类影响。本文所提出的理论与方法对寻找到DDLB系统的最优控制规律、设计时延环境下实用的动态负载平衡算法有指导性意义。