隨著多核時代的到來,當(dāng)前的并行計算機系統(tǒng)通常包括多核CPU、GPU和其他處理器,CPU和GPU的融合已經(jīng)成為處理器發(fā)展的趨勢。如何充分利用當(dāng)前多核異構(gòu)系統(tǒng)的并行計算能力已經(jīng)成為一大研究熱點。OpenCL計算技術(shù)的出現(xiàn)為異構(gòu)計算資源的利用提供了技術(shù)支持,利用其對傳統(tǒng)串行算法進行并行化改進將可能獲得巨大的加速性。背包問題在實際生活中具有廣泛的應(yīng)用前景,0/1背包問題是背包問題中最基本的問題,而其它背包問題通�？梢赞D(zhuǎn)換成0/1背包問題。遺傳算法作為一種智能優(yōu)化算法,具有簡單、實用和較好的魯棒性等優(yōu)點,在求解背包問題上已經(jīng)顯示了巨大優(yōu)勢。遺傳算法其天然的并行性十分符合OpenCL技術(shù)的并行模型,而傳統(tǒng)遺傳算法求解背包問題是通過對群體中個體逐個串行計算實現(xiàn)的,不能發(fā)揮遺傳算法個體獨立的并行優(yōu)勢。于是,本文就提出了一個利用OpenCL技術(shù)提高遺傳算法運行效率來并行求解背包問題的研究課題。本文針對基于串行遺傳算法實現(xiàn)的0/1背包問題的低效率進行了并行化加速,利用個體之間遺傳操作先天獨立的特點,對背包問題的計算過程進行并行分割,并基于OpenCL實現(xiàn)該并行算法,同時使用局部緩存等技術(shù)對計算過程進行了優(yōu)...

【文章頁數(shù)】：85 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
        1.1.1 背包問題
        1.1.2 遺傳算法
        1.1.3 異構(gòu)計算技術(shù)的發(fā)展
    1.2 國內(nèi)外研究現(xiàn)狀
    1.3 本文的主要研究工作
    1.4 論文基本結(jié)構(gòu)
第二章 背包問題和遺傳算法的基本原理
    2.1 背包問題的描述
    2.2 遺傳算法的基本概念
    2.3 遺傳算法的基本流程
    2.4 遺傳操作的實現(xiàn)
        2.4.1 二進制遺傳算法進化過程
        2.4.2 選擇算子的實現(xiàn)
        2.4.3 交叉算子的實現(xiàn)
        2.4.4 變異算子的實現(xiàn)
    2.5 本章小結(jié)
第三章 異構(gòu)計算技術(shù)
    3.1 CPU與GPU架構(gòu)及差異
        3.1.1 CPU架構(gòu)的特點
        3.1.2 GPU架構(gòu)的特點
        3.1.3 CPU與GPU的優(yōu)劣對比
    3.2 OPENCL的基本介紹
    3.3 OPENCL的計算架構(gòu)
        3.3.1 平臺模型
        3.3.2 存儲器模型
        3.3.3 執(zhí)行模型
        3.3.4 編程模型
    3.4 OPENCL的計算流程
    3.5 本章小結(jié)
第四章 基于OPENCL的并行遺傳算法設(shè)計及實現(xiàn)
    4.1 基于OPENCL的并行遺傳算法實現(xiàn)流程
    4.2 OPENCL主機端的具體實現(xiàn)
        4.2.1 遺傳個體的數(shù)據(jù)結(jié)構(gòu)
        4.2.2 主機初始化的實現(xiàn)
        4.2.3 設(shè)備操作的實現(xiàn)
    4.3 內(nèi)核算法的具體實現(xiàn)
        4.3.1 隨機數(shù)函數(shù)的實現(xiàn)
        4.3.2 背包問題價值計算的實現(xiàn)
        4.3.3 初始化內(nèi)核函數(shù)的實現(xiàn)
        4.3.4 選擇操作的實現(xiàn)
        4.3.5 交叉操作的實現(xiàn)
        4.3.6 變異操作的實現(xiàn)
        4.3.7 遺傳操作內(nèi)核函數(shù)的實現(xiàn)
        4.3.8 統(tǒng)計操作內(nèi)核函數(shù)的實現(xiàn)
    4.4 本章小結(jié)
第五章 算法運行結(jié)果及分析
    5.1 算法實現(xiàn)的軟硬件環(huán)境
    5.2 算法的實驗設(shè)計
    5.3 算法的實驗結(jié)果與分析
        5.3.1 傳統(tǒng)串行實現(xiàn)與并行實現(xiàn)的對比
        5.3.2 并行執(zhí)行時間隨種群增大的差異對比
        5.3.3 并行實現(xiàn)隨種群增大求解結(jié)果的變化
        5.3.4 CPU并行性能與核數(shù)和主頻的關(guān)系
        5.3.5 GPU并行性能與驅(qū)動版本的關(guān)系
    5.4 本章小結(jié)
第六章 總結(jié)與展望
    6.1 全文總結(jié)
    6.2 問題與展望
致謝
參考文獻
附錄A (攻讀碩士學(xué)位期間所發(fā)表的論文)



本文編號：3832121