簡易檢索 / 詳目顯示

回結果列表
研究生： 何泳陖
論文名稱： 基於繪圖處理器之疊代層級平行演化演算法軟體框架
A software framework for iteration-level parallel evolutionary algorithm on graphics processing units
指導教授： 蔣宗哲
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2014
畢業學年度： 102
語文別： 中文
論文頁數： 68
中文關鍵詞： 演化演算法 、CUDA 、平行處理 、PEAC
論文種類： 學術論文
相關次數： 點閱：278  下載：11 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 生活中常會遇到最佳化問題滿例如搭乘交通工具從甲地前往乙地，可選擇的交通工具組合可能有很多種，選擇考慮的因素有最快抵達或交通費最低等等。此類問題經常使用演化演算法來求解，而撰寫一個完整的演化演算法需耗費一些時間。

    NVIDIA公司致力於平行環境CUDA的開發，使用者可以將C++程式碼修改成可運行CUDA程式碼。以現今的平行計算技術，使用不高的成本購入可運行CUDA的硬體，加速數十倍至數百倍是有可能的，數小時的實驗加速後可能僅需數分鐘即可完成。

    本論文開發一個演化演算法的軟體框架，PEAC(Parallel Evolutionary Algorithms base on CUDA)，提供演化演算法的基本設定，也提供演化演算法中常見的運算子供使用。讓使用者可以降低撰寫程式碼的時間。也不需要額外花費時間學習CUDA的程式開發。

    中文摘要 i 致謝 ii 目錄 iii 圖目錄 vi 表目錄 viii 1 緒論 1 1.1 研究動機 1 1.2 演化演算法 2 1.3 CUDA 3 1.3.1 主機端與設備端 5 1.3.2 執行緒結構 6 1.3.3 記憶體結構 8 1.4 研究範圍 9 2 文獻探討 11 2.1 平行局部搜索演算法 11 2.2 平行演化演算法 15 2.3 平行最佳化演算法軟體框架 18 3 基於 CUDA 之平行演化演算法框架 23 3.1 平行處理層級 23 3.1.1 層級平行 23 3.2 平行分配函式 24 3.2.1 傳遞函式至設備端呼叫 24 3.2.2 thrust 31 3.2.3 平行分配函式實作 32 3.3 平行處理記憶體結構 35 3.4 平行演化演算法框架 37 3.5 設定參機制 39 3.6 使用守則 44 4 實驗設計 46 4.1 測試問題 46 4.2 實驗環境 47 4.3 效能比較 47 4.4 結構比較 48 4.5 框架比較 50 5 結論與未來展望 51 A PEAC 安裝與環境建置 55 A.1 安裝 CUDA 55 A.2 CUDA 環境設 55 A.3 編譯一般CUDA程式並執行 55 A.4 PEAC環境設定 56 A.5 編譯PEAC程式並執行 57 B 使用 PEAC 59 B.1 建立PEAC陣列並賦值 59 B.2 建立可供PEAC呼叫之主機端與設備端函式 62 B.3 複製資料與呼叫函式 63 B.4 使用演算法與設定檔 64 B.5 建立演算法部分函式並更換 66

    [1] Cuda toolkit documentation, http://docs.nvidia.com/cuda/.
    [2] R. Couturier, “Introduction to cuda,” Designing Scientific Applications on GPUs, p. 13, 2013.
    [3] Cuda c programming guide, http://docs.nvidia.com/cuda/cuda-c-programming-guide/.
    [4] T. Van Luong, N. Melab, and E.-G. Talbi, “Gpu computing for parallel local search metaheuristic algorithms,” IEEE Transactions on Computers, vol. 62, no. 1, pp. 173–185, 2013.
    [5] M. Czapiński and S. Barnes, “Tabu search with two approaches to parallel flowshop evaluation on CUDA platform,” Journal of Parallel and Distributed Computing, vol. 71, no. 6, pp. 802–811, 2011.
    [6] M. Pedemonte, E. Alba, and F. Luna, “Bitwise operations for gpu implementation of genetic algorithms,” in Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, ACM, 2011, pp. 439–446.
    [7] H. Wang, S. Rahnamayan, and Z. Wu, “Parallel differential evolution with self-adapting control parameters and generalized opposition-based learning for solving high-dimensional optimization problems,” Journal of Parallel and Distributed Computing, vol. 73, no. 1, pp. 62–73, 2013.
    [8] M. L. Wong, “Parallel multi-objective evolutionary algorithms on graph-ics processing units,” in Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, ACM, 2009, pp. 2515–2522.
    [9] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and eli- tist multiobjective genetic algorithm: nsga-ii,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002.
    [10] P. Vidal and E. Alba, “A multi-gpu implementation of a cellular genetic algorithm,” in IEEE Congress on Evolutionary Computation, 2010, pp. 1–7.
    [11] M. Arenas, G Romero, A. Mora, P. Castillo, and J. Merelo, “Gpu parallel computation in bioinspired algorithms: a review,” in Advances in Intelligent Modelling and Simulation, Springer, 2012, pp. 113–134.
    [12] L. Mussi, F. Daolio, and S. Cagnoni, “Evaluation of parallel particle swarm optimization algorithms within the CUDA™ architecture,” Information Sciences, vol. 181, no. 20, pp. 4642–4657, 2011.
    [13] D. Izzo, “PyGMO and PyKEP: open source tools for massively parallel optimization in astrodynamics (the case of interplanetary trajectory optimization),” Proceedings of the Fifth International Conference on Astrodynamics Tools and Techniques, ICATT, 2012.
    [14] Y. S. Nashed, R. Ugolotti, P. Mesejo, and S. Cagnoni, “libcudaoptimize: an open source library of gpu-based metaheuristics,” in Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation Conference, ACM, 2012, pp. 117–124.
    [15] O. Maitre, F. Krüger, S. Querry, N. Lachiche, and P. Collet, “Easea: specification and execution of evolutionary algorithms on gpgpu,” Soft Computing, vol. 16, no. 2, pp. 261–279, 2012.
    [16] N. Melab, T. Luong, K Boufaras, and E.-G. Talbi, “Towards paradiseo-mo-gpu: a framework for gpu-based local search metaheuristics,” in Advances in Computational Intelligence, Springer, 2011, pp. 401–408.
    [17] Thrust::cuda toolkit documentation, http://docs.nvidia.com/cuda/thrust/index.html.
    [18] E. Taillard, “Benchmarks for basic scheduling problems,” European Journal of Operational Research, vol. 64, no. 2, pp. 278 –285, 1993, Project Management anf Scheduling, issn: 0377-2217. doi: http://dx.doi.org/10.1016/0377-2217(93)90182-M. [Online]. Avail-able: http://www.sciencedirect.com/science/article/pii/037722179390182M.

    QR CODE