学位论文 > 优秀研究生学位论文题录展示

基于单调指标空间法的需求空间探索加速技术研究

作　者: 林忠伟
导　师: 姚益平
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 需求空间加速收敛 CGM 分布式任务池
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 9次
引　用: 0次
阅　读: 论文下载

内容摘要

自然科学和社会科学的很多领域都涉及需求空间问题,求解需求空间有助于解决寻需问题、性能优化问题、系统效能分析与评估等问题。然而,随着系统复杂程度不断提高,系统往往包含高维复杂模型,且效能度量函数形式多样,这使得目前的串行求解方法的性能越来越难以满足应用的需求,因此,开展需求空间求解加速技术研究,对于提高求解高维复杂问题需求空间的效率、缩短求解时间、满足不断发展的应用需求等具有重要的理论意义和实用价值。论文针对串行单调指标空间法在求解高维复杂问题需求空间耗时长的问题,以缩短求解时间为目标,围绕加速超盒分割点收敛、算法并行化以及减少通信开销等关键问题展开研究,主要工作及创新点如下:(1)提出了基于抛物线法的单调指标空间超盒分割点探索算法ParISearch。单调指标空间法的第一步为探索超盒分割点,当前采用的二分法,收敛速度慢,难以满足求解高维复杂问题需求空间的需求。为此,论文提出了基于抛物线法的超盒分割点探索算法ParISearch,该算法借鉴非线性方程求根中的抛物线法的思想,利用三个历史迭代点计算下一个迭代点。实验结果表明,与二分法相比,ParISearch算法在满足求解精度要求的前提下,可以有效减少迭代次数,求解时间可缩短约25%。(2)提出了基于粗粒度多处理机模型(Coarse-Grained Multicomputer model,CGM)的超盒并行处理算法CGMResolve。单调指标空间法时空复杂度高,对于高维复杂问题,当前采用的串行处理方法已越来越不能满足应用对时效性的需求。CGM是一种独立于计算机体系结构、高效、可行的并行计算模型。论文在分析单调指标空间法处理超盒时存在的并行性的基础上,提出了基于CGM的超盒并行处理算法CGMResolve。该算法将超盒作为并行处理的基本单位,不同的超盒分发到不同的计算节点上进行并行解算。实验结果表明,CGMResolve算法获得了很好的加速效果,加速比几乎随计算节点数目线性增长,如使用2个计算节点时的加速比为1.658,使用3个计算节点时的加速比为2.338。(3)提出了基于分布式任务池的超盒存储与迁移算法DTPTransfer。基于CGM改造后的单调指标空间法需要维护超盒队列,采用全局任务池存储与分发超盒,超盒分发效率低下,而采用分布式任务池存储超盒,需要保证节点间负载平衡。针对上述问题,论文提出了基于分布式任务池的超盒存储与迁移算法DTPTransfer。在该算法中,计算节点将新产生的超盒缓存在本地以分散存储压力和缩短等待超盒的时间,并根据全局控制机制在节点间迁移超盒以实现节点间的负载均衡。实验结果表明,采用DTPTransfer算法后,通信时间在程序执行时间中所占的比重明显降低,总体运行效率有较大的提高:如使用5个计算节点时,相比于采用全局任务池,算法通信时间比重下降了约50%,需求空间求解时间缩短了约5%。在上述研究成果的基础上,设计和实现了一个面向局域网集群的需求空间并行求解系统,并通过求解一个模拟防空系统的需求空间对其进行了综合测试。测试结果表明,该系统与采用二分法的串行方式相比,可获得可观的加速效果,如采用2个计算节点时的加速比为2.763,采用6个计算节点时的加速比为6.027。

基于单调指标空间法的需求空间探索加速技术研究

内容摘要

全文目录

相似论文