论文部分内容阅读
随着仿真应用的不断深入,仿真规模正在逐步扩大,仿真模型越来越复杂,其对计算资源的要求也越来越高。特别是在实时仿真应用中,由于对时间约束的要求非常苛刻,其对处理平台的计算性能提出了更高的要求。而一些大规模系统内部往往存在一些并行因素,若能直接用分布、并行方法实现这部分的仿真当然就更符合系统的实际特征了,因此并行分布仿真逐渐成为实时仿真研究的焦点。然而,并行分布仿真有许多尚待解决的问题,其中任务调度是影响仿真系统运行性能和效率的关键因素之一,不恰当的调度不仅不会带来性能的提升,甚至会带来比串行仿真更差的结果。论文围绕并行分布实时仿真中的任务调度问题,从仿真任务分配和周期仿真任务集可调度性分析两方面展开研究。本文在对仿真任务调度策略进行了一般性研究的基础上,首先分析了实时仿真的可调度性问题。为保证并行分布实时仿真的实时性要求,需要在系统设计阶段就对仿真任务集进行可调度性分析。一般并行分布实时仿真中任务集都是周期性的,论文研究了周期仿真任务集在同构多处理器平台下采用固定作业优先级调度算法的可调度性分析。由于传统可调度性分析采用的理论方法不具备完备性,论文采用了模拟运行的方式进行可调度性分析。根据周期仿真任务集特点,可调度性分析主要是求可调度区间。论文首先给出一个基本可调度区间,并归纳出求解可调度区间的基本思路;然后从仿真任务执行状态界限出发,给出了两个改进的可调度区间,并将这两个改进结果合并得到最终结果,保证所求的可调度区间范围达到最小。然后针对分布式实时仿真平台、多核实时仿真平台和异构多处理器实时仿真平台三个典型仿真应用平台,依次展开研究:(1)对于使用最广泛的分布式仿真平台,平台的复杂性将大大增加系统失效的可能性,因此可靠性是其一个关键性需求,对运行实时仿真应用的分布式仿真平台尤为重要。使用任务分配的方法来提高分布式实时仿真平台的可靠性,不需要增加额外的软硬件资源,具备更广泛的适用性。论文通过对系统可靠性及约束条件分析,将仿真任务分配问题建模为组合优化问题,并提出了一个混沌自适应模拟退火算法XASA用以求解该问题。XASA算法首先在混沌优化算法的基础上进行解空间的混沌遍历,得到一个局部最优集,然后采用自适应策略对模拟退火算法进行改进,在局部最优集的基础上进一步寻优。(2)多核处理器集群作为当前最热门的处理平台,在并行分布实时仿真中逐渐成为主流。相比较于传统的并行分布式仿真平台,多核集群的特点是节点内通信代价不可忽略,针对这一特点,论文着重分析了节点内通信对仿真任务分配问题带来的影响。通过分析单个节点的节点内/节点间通信代价,建立关于一致代价仿真任务分配问题的最小费用流模型,进而推广到一般意义下的多核处理器集群仿真任务分配问题,并建立广义最小费用流模型。通过分析通信代价凹函数的特点将凹费用网络流转换为带固定费用网络流问题之后,设计遗传模拟退火组合算法求解该问题。(3)仿真的实时性因任务的不同而存在很大差异,因此针对不同实时性要求的仿真任务需要不同类型的处理器来处理,而同一个仿真任务在不同类型的处理器上执行结果也不尽相同。论文通过分析异构多处理器平台特性,选择仿真任务在同类处理器内部自由迁移的内迁移问题作为研究对象,将异构多处理器仿真任务调度问题转化为内迁移仿真任务分配问题。在对该问题建模为整数线性规划问题的基础上,松弛为线性规划问题,将因松弛产生的未完整分配的仿真任务称为“散碎仿真任务”,论文证明了在包含有t类处理器的异构多处理器环境下,最多只有t-1个散碎仿真任务。然后根据散碎仿真任务建立二分图模型,提出通过调整边权值的方法消除图中的环,最后设计算法将散碎仿真任务完整分配到某个处理器类上。最后,本文以一个采用分布实时仿真平台的空战任务仿真系统为背景,对仿真任务分配算法进行了验证分析,仿真试验结果表明,任务分配方法能够提高仿真系统的可靠性,而XASA算法能有效克服传统模拟退火算法和混沌优化算法收敛速度慢的问题,且不失解质量。