基于OpenCL的并行遗传算法在0/1背包问题的研究及实现

发布时间：2023-06-06 19:57

　　随着多核时代的到来,当前的并行计算机系统通常包括多核CPU、GPU和其他处理器,CPU和GPU的融合已经成为处理器发展的趋势。如何充分利用当前多核异构系统的并行计算能力已经成为一大研究热点。OpenCL计算技术的出现为异构计算资源的利用提供了技术支持,利用其对传统串行算法进行并行化改进将可能获得巨大的加速性。背包问题在实际生活中具有广泛的应用前景,0/1背包问题是背包问题中最基本的问题,而其它背包问题通常可以转换成0/1背包问题。遗传算法作为一种智能优化算法,具有简单、实用和较好的鲁棒性等优点,在求解背包问题上已经显示了巨大优势。遗传算法其天然的并行性十分符合OpenCL技术的并行模型,而传统遗传算法求解背包问题是通过对群体中个体逐个串行计算实现的,不能发挥遗传算法个体独立的并行优势。于是,本文就提出了一个利用OpenCL技术提高遗传算法运行效率来并行求解背包问题的研究课题。本文针对基于串行遗传算法实现的0/1背包问题的低效率进行了并行化加速,利用个体之间遗传操作先天独立的特点,对背包问题的计算过程进行并行分割,并基于OpenCL实现该并行算法,同时使用局部缓存等技术对计算过程进行了优...

【文章页数】：85 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
        1.1.1 背包问题
        1.1.2 遗传算法
        1.1.3 异构计算技术的发展
    1.2 国内外研究现状
    1.3 本文的主要研究工作
    1.4 论文基本结构
第二章 背包问题和遗传算法的基本原理
    2.1 背包问题的描述
    2.2 遗传算法的基本概念
    2.3 遗传算法的基本流程
    2.4 遗传操作的实现
        2.4.1 二进制遗传算法进化过程
        2.4.2 选择算子的实现
        2.4.3 交叉算子的实现
        2.4.4 变异算子的实现
    2.5 本章小结
第三章 异构计算技术
    3.1 CPU与GPU架构及差异
        3.1.1 CPU架构的特点
        3.1.2 GPU架构的特点
        3.1.3 CPU与GPU的优劣对比
    3.2 OPENCL的基本介绍
    3.3 OPENCL的计算架构
        3.3.1 平台模型
        3.3.2 存储器模型
        3.3.3 执行模型
        3.3.4 编程模型
    3.4 OPENCL的计算流程
    3.5 本章小结
第四章 基于OPENCL的并行遗传算法设计及实现
    4.1 基于OPENCL的并行遗传算法实现流程
    4.2 OPENCL主机端的具体实现
        4.2.1 遗传个体的数据结构
        4.2.2 主机初始化的实现
        4.2.3 设备操作的实现
    4.3 内核算法的具体实现
        4.3.1 随机数函数的实现
        4.3.2 背包问题价值计算的实现
        4.3.3 初始化内核函数的实现
        4.3.4 选择操作的实现
        4.3.5 交叉操作的实现
        4.3.6 变异操作的实现
        4.3.7 遗传操作内核函数的实现
        4.3.8 统计操作内核函数的实现
    4.4 本章小结
第五章 算法运行结果及分析
    5.1 算法实现的软硬件环境
    5.2 算法的实验设计
    5.3 算法的实验结果与分析
        5.3.1 传统串行实现与并行实现的对比
        5.3.2 并行执行时间随种群增大的差异对比
        5.3.3 并行实现随种群增大求解结果的变化
        5.3.4 CPU并行性能与核数和主频的关系
        5.3.5 GPU并行性能与驱动版本的关系
    5.4 本章小结
第六章 总结与展望
    6.1 全文总结
    6.2 问题与展望
致谢
参考文献
附录A (攻读硕士学位期间所发表的论文)



本文编号：3832121