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

遗传算法在多核系统上的性能分析和优化

作　者: 丁孟为
导　师: 过敏意
学　校: 上海交通大学
专　业: 计算机软件与理论
关键词: 遗传算法 片上多核处理器 对称多处理器 并行计算 体系结构
分类号: TP18
类　型: 硕士论文
年　份: 2012年
下　载: 44次
引　用: 0次
阅　读: 论文下载
 

内容摘要


遗传算法是一种被广泛应用在工程领域的随机算法。它是一种模拟自然界生物进化和自然淘汰的计算模型。在遗传算法的主要操作算子(选择、交叉和变异)中,种群中每个个体之间的数据独立性强,非常适合并行化,因此,遗传算法的并行化研究也随着遗传算法的诞生而开始。当前,随着多核处理器的普及,进行遗传算法并行化计算的研究的成本也随之降低。大多数研究人员将注意力放在了遗传算法本身的研究以及特定的应用场景。然而,由于缺乏对多核处理器体系结构的深入理解,并没有针对体系结构角度的遗传算法性能分析和优化的通用结论。本文首先立足于片上多核处理器的系统结构,根据片上多核处理器的结构特点分析了并行遗传算法的三种模型——主从式、分岛式和混合式的性能表现,并提出了达到指定精度的速度这一分析性能的全新角度。对于主从式模型,我们提出了线程对齐的指导意见,从而避免了额外的性能开销;对于分岛式模型,我们从理论角度分析了同步与异步方式在性能上的优劣;对于混合式模型,我们引入了并行度(PD)的概念,提出了存在一个PD值可以使得混合式模型在片上多核处理器上最快地达到指定精度。我们的实验验证了存在这样的一个最优的PD值点,使得混合式模型在速度和精度上具有最好的折中,从而具有达到指定精度的最快速度。根据混合式模型的性能表现,本文将目标系统进一步延伸到对称多处理器上。我们在分析了对称多处理器的体系结构特点的基础上,提出了遗传算法混合式模型的线程组织优化策略,力图从降低处理器之间的维护缓存一致性的开销的角度来提升混合式模型的性能。该线程组织优化策略可以指导用户在使用混合式模型时,手动去分配线程与处理器的处理核心的绑定关系。实验证明,优化的线程组织策略可以提升混合式模型10%的性能。本文最后从增加遗传算法本身随机性的角度出发,提出了一个衍生的随机数模型。该模型试图牺牲遗传算法程序的空间复杂度,从而换取在结果的精度上的提升。实验表明,该衍生随机数模型对遗传算法的诸多模型具有普遍的精度提升效果。

全文目录


摘要  3-5
ABSTRACT  5-10
表格索引  10-11
插图索引  11-13
第一章 绪论  13-17
  1.1 研究背景  13-14
  1.2 研究目标和意义  14-15
  1.3 本文的组织结构  15-16
  1.4 本章小节  16-17
第二章 相关背景和工作  17-27
  2.1 遗传算法  17-19
  2.2 遗传算法的并行化  19-23
    2.2.1 主从式  19-21
    2.2.2 分岛式  21-23
    2.2.3 蜂窝式  23
  2.3 相关工作  23-25
  2.4 本章小结  25-27
第三章 遗传算法在多核系统上的性能分析  27-47
  3.1 片上多核处理器的系统结构  27-29
  3.2 主从式模型在多核上的性能分析  29-32
    3.2.1 主从式模型在多核上的线程组织结构  29-31
    3.2.2 主从式模型的性能分析和线程对齐优化  31-32
  3.3 分岛式模型在多核上的性能分析  32-34
    3.3.1 分岛式模型在多核上的线程组织结构  32-33
    3.3.2 分岛式模型的性能分析  33-34
  3.4 主从式和分岛式的性能比较  34-35
  3.5 混合式模型在多核上的性能分析  35-36
    3.5.1 混合式模型在多核上的线程组织结构  35-36
    3.5.2 混合式模型的性能分析  36
  3.6 实验验证  36-44
    3.6.1 实验环境配置  36-39
    3.6.2 实验结果  39-44
  3.7 本章小节  44-47
第四章 遗传算法在对称多处理器上的线程优化  47-59
  4.1 对称多处理器  47-51
    4.1.1 对称多处理器的系统结构  47-48
    4.1.2 缓存的一致性  48-50
    4.1.3 线程的绑定技术  50-51
  4.2 混合式模型的线程优化  51-54
  4.3 实验验证  54-57
    4.3.1 实验环境配置  54-55
    4.3.2 实验结果  55-57
  4.4 本章小节  57-59
第五章 遗传算法的衍生随机数模型  59-65
  5.1 传统的随机数模型  59-60
  5.2 衍生随机数模型  60-62
  5.3 实验验证  62-64
    5.3.1 实验环境  62-63
    5.3.2 实验结果  63-64
  5.4 本章小节  64-65
第六章 全文总结  65-69
  6.1 主要结论  65-67
    6.1.1 遗传算法在多核系统上的性能分析  65-66
    6.1.2 遗传算法在对称多处理器上的线程优化  66-67
    6.1.3 遗传算法的衍生随机数模型  67
  6.2 研究展望  67-69
参考文献  69-75
致谢  75-77
攻读学位期间发表的学术论文目录  77-79

相似论文

  1. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  2. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  3. 面向SMDA的服务建模方法及工具实现,TP311.52
  4. 基于WEB的仿真互操作性测试工具研究,TP391.9
  5. 基于遗传算法的模糊层次综合评判在高职教学评价中的应用,G712
  6. 部队人员网上训练与考核系统的开发,TP311.52
  7. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  8. 基于神经网络的牡蛎呈味肽制备及呈味特性研究,TS254.4
  9. 基于遗传算法的中短波磁天线的设计及实现,TN820
  10. 基于遗传算法的柑橘图像分割,TP391.41
  11. 基于混合自适应遗传算法的动态网格调度问题研究,TP393.09
  12. 基于遗传—牛顿算法的公交优化调度,TP18
  13. 基于遗传算法优化的BP网络对生物柴油制备工艺的优化,TE667
  14. 基于云理论和蜜蜂进化型遗传算法的纹理合成研究,TP391.41
  15. 基于遗传算法和粗糙集的聚类算法研究,TP18
  16. 软件可信性增长测试用例生成方法的研究,TP311.53
  17. 基于遗传算法的淠史杭灌区渠系配水优化编组模型的研究,S274
  18. 遗传算法在物流仓储优化中的应用研究,F259.2
  19. 基于遗传算法的矿山资源优化调度模型的研究,O224
  20. Web容器差分服务技术研究,TP393.09
  21. 机械臂轨迹规划研究,TP242

中图分类: > 工业技术 > 自动化技术、计算机技术 > 自动化基础理论 > 人工智能理论
© 2012 www.xueweilunwen.com