论文部分内容阅读
采用计算机辅助系统建模与仿真方法,系统研发人员能够在设计早期对整个系统的方案进行验证和改进,从而达到缩短研发周期、降低研发成本等目的。由于即使简单的系统模型也可能产生大量计算,并且在设计过程中通常需要对系统的不同设计方案、不同参数配置、不同工作环境等作大量仿真实验,因此仿真程序的加速方法具有很高的研究价值。目前,通过提高CPU主频来获得更高的CPU运算速度需要耗费巨大的能量,单个CPU的计算速度达到一个峰值,世界主流的CPU厂商均致力于生产多核并行处理器。因此,并行化成为提高计算机程序速度的重要方法。本文主要研究复杂机电系统(机械与电子、液压、气动、热流等相关物理领域耦合系统)的仿真并行化方法。系统仿真程序实质是系统本构方程的求解程序。复杂机电系统的本构方程通常为微分代数方程组(Differential Algebraic Equations,DAEs),其中代数方程求解任务的计算量经常占整个仿真程序计算量的绝大部分,因此代数方程求解任务的计算速度提升对改进整个仿真程序性能起到决定作用。针对复杂机电系统仿真中代数方程求解任务的并行化,本文研究具体分为如下三个方面:1)机械系统模型通常为高指标DAEs,其中位置约束方程通常为非线性方程组。非线性方程组一般采用迭代方法求解。获得一定精度的求解结果所需要的迭代次数不确定,造成任务计算量动态变化且无法预估,引起并行调度困难。此外,非线性方程组的系数是时变的,雅可比矩阵奇异将造成迭代求解失败。为解决该问题须引入额外的计算。本文提出一种机械系统建模与求解的线性化方法,一方面直接降低计算量,另一方面避免求解非线性方程组,为后续的并行化提供静态任务图。新方法采用方向余弦坐标替代部分相对角度坐标,并采用坐标划分方法求解系统的支配方程。仅从方向余弦坐标和平移坐标中选择合适的变量(避免选择角度坐标)作为位置约束方程的未知量,位置约束方程是关于未知变量的线性方程组。而方向余弦坐标本应满足的非线性正交约束则被构造为惩罚项增加到速度约束方程中。新方法将传统方法中的非线性位置约束方程组替换为同等规模(未知数数量相等)的线性代数方程组。此外,通过合理选择未知变量,线性方程组甚至可以是常系数的。通过符号变换,常系数线性方程组能够转换为赋值语句,进一步减少计算量并避免雅可比矩阵奇异问题。实验结果表明新方法具有很好的速度、精度和稳定性。2)采用上述线性化方法,机电系统中机械部分与其它物理领域系统具有统一的方程形式,即指标1(或指标0)微分代数方程组,且其中大部分代数方程(例如上述常系数线性方程组)的求解任务可通过符号运算换为赋值语句,其余方程相互耦合形成需联立求解的代数方程组。这些方程(组)求解任务之间具有先后约束关系,即部分方程(组)的求解依赖其它方程(组)的计算结果,因此其并行化问题属于约束任务的并行调度问题。复杂机电系统模型的代数方程中通常含有大量的、计算量较小的赋值语句,其并行化存在两方面问题:①提取大规模约束任务的内在并行度较为困难;②并行程序中用于管理、调度任务的额外计算量与仿真程序有效计算量的比值较高,进一步降低实际并行效果。因此,通常需采用聚合方法以减少任务数量、缩减问题规模、降低额外计算量。然而,当前文献中采用的聚合方法通常根据任务之间是否满足一定的拓扑关系判断是否执行任务合并,未考虑任务之间的计算量差异特点,在减少任务数量的同时容易改变代数方程块求解任务之间的并行关系,从而造成程序内在并行度严重损失。为此,本文提出一种针对代数方程求解任务的自动聚合方法。新方法将计算量较小任务合并至较大任务中,在减小节点数量同时保持大计算量任务间的并行关系,从而基本维持程序的原有可并行特性。本文还提出一种基于简化任务图的可并行性预估方法,对采用上述聚合方法后能够取得的并行效果进行预估,从而避免无效的并行化尝试。本文通过大量实验(包括与文献中基准模型的对比实验),验证了上述聚合方法和可并行性预估方法的有效性。3)即使采用上述任务聚合方法,复杂机电系统仍然可能产生较大规模的约束任务。对于大规模约束调度问题,文献实验结果表明,当前应用中所采用的高阶调度算法(例如随机导向搜索算法)提供的调度结果并未明显优于启发式算法。由此,本文推测当前文献所采用的算法未能有效提取大规模约束任务(包括代数方程求解任务)的内在并行度。本文首次引入元胞遗传算法(Cellular Genetic Algorithm,CGA)解决约束任务的并行调度问题。实验结果表明,CGA方法提供的调度结果明显优于当前文献采用的并行调度算法,且相比基本遗传算(Basic Genetic Algorithm,BGA)法更为稳定。此外,本文结合GPU计算架构特点,提出基于GPU的遗传算法簇,有效缓解遗传算法在解决大规模约束任务调度问题时存在的过于耗时的问题。最后介绍根据上述研究成果研制的软件原型,并通过一个较复杂的机电系统仿真案例展示本文所述线性化和并行化方法的效果和价值。