在CUDA平台上加速ECGA的模型建造

Abstract

為了提供電動遊戲所需要的即時、高畫質的3D立體繪圖，圖形 處理器在 過去二十年進步成擁有強大的運算能力的處理器。自從輝 達(NVIDIA)釋出 統一計算架構(CUDA)之後, 圖形處理器也成為可以在 更廣泛的用途上 提供平行計算並促進與CPU協同運算的裝置。 圖形處 理器已經在各種領域平行化了大量的可規模化的應用程式。 因為演化 式計算具有平行的本質， 平行化一直是一種直覺上可以增進效率的 方式。 然而將分佈估計演算法(EDA)運用在圖形處理器上的研究並不 多。 在這篇論文裡我們提出了兩種在CUDA上能夠加速擴展的 緊湊型基 因遺傳演算法(ECGA)的模型建立的實作方式。 第一個實作方式與原 本的ECGA在演算法上完全一致。 第二種實作修改了模型建立的演算 法，透過犧牲模型建立的精準度，獲得了 更高的加速。在實驗中，第 一個實作相對於基準的實作在一個長度為550 並且子問題長度為5的陷 阱問題上加速了大約374 倍。第二個 實作方式在相同的問題上加速了 大約531 倍。這兩種實作法 在一張Tesla C2050的圖形顯示卡上可以規 模化到長度為9800的陷阱問題。

Due to the demand for realtime, high-defination 3D graphics in video game, graphic processing unit (GPU) has advanced to have tremendous computational power in the past two decades. Since NVIDIA released the compute unified device architecture (CUDA), GPU has become a general parallel computing device that facilitates heterogeneous computing between CPU and GPU. GPU has enabled lots of scalable parallel programs in a wide range of fields and parallelization is a straightforward approach to enhance the efficiency for evolutionary computation due to its inherently parallel nature. However, parallelization of model building for EDA on GPU is rarely studied. In this thesis, we propose two implementations on CUDA to speed up the model building in the extended compact genetic algorithm (ECGA). The first implementation is algorithmically identical to original ECGA. Aiming at a greater speed boost, the second implementation modifies the model building. It slightly decreases the accuracy of models in exchange for more speedup. Empirically, the first implementation achieves a speedup of roughly 374 to the baseline on 550-bit trap problem with order 5, and the second implementation achieves a speedup of roughly 531 to the baseline on the same problem. Finally, both of our implementations scale up to 9,800-bit trap problem with order 5 on one single Tesla C2050 GPU card.