一個創新的平行蜂群演算法實作在圖形處理器架構

Abstract

尋求最佳解在電腦科學或和其他工程領域裡面是很重要的一環，然而尋求最佳解屬於NP問題，取而代之去尋近似最佳解的演算法也越來越多。Swarm Intelligence是透過觀察大自然中社會型動物的生活方式應用在人工智慧來解決問題，蜂群演算法就是其中一個。由於找尋近似最佳解的演算法也CPU bound job，一些平行處理的演算法也因此相繼被人提出，到目前為止，鮮少人關心蜂群演算法的平行化。 圖形處理器(GPU)是專門針對圖形處理而設計的架構，因為影像處理具備高度平行化的特性，造就了GPGPU的發展，許多的研究也開始利用GPU進行大量的平行運算。近年，由NVIDIA提出GPGPU的解決方案CUDA(Compute Unified Device Architecture)讓開發者利用熟悉的C/C++就可以在上面開發自己的平行應用程式。 本論文針對需要大量運算的蜂群演算法提出許多方法使其平行化且適合在CUDA的平行架構運行，並針對幾個知名的最佳化問題做了效能上面的測試。根據我們的實驗結果，可以發現平行化的CUDA Bees Algorithm (CUBA) 利用龐大數量的處理器，在各個最佳化問題比起傳統的Bees Algorithm(BA)至少有3X倍效能的加速。

Searching the solution of optimization problems is a very important work in computer science and engineering field. The problems are belong to NP problem, so more and more algorithms are developed to find approximate solutions instead of the real solutions. Swarm Intelligence is the collective behavior of the system of social animals in nature. The concept is used in algorithm on artificial intelligence(AI). The Bees Algorithm is one of the works. Because these algorithms are computational bound jobs, some parallel swarm based algorithms are proposed in recent years. Even so, few works are developed base on The Bees Algorithm. GPU is a special architecture of graphic processor. The highly parallel features of graphic processing made the rapid development of General Purpose GPU(GPGPU). A lot works for massive parallel computing on GPU are proposed. NVIDIA provide a general purpose parallel model, thus programmer could use their familiar language C/C++ to develop own parallel applications. In this paper, we do many modifications for The Bees Algorithm and make it adapt to run in the parallel architecture of CUDA. We also test the performance accelerations for numerous famous optimization problems. Finally, the result shows the CUDA Bees Algorithm(CUBA) we proposed perform at least 3x times faster than traditional BA in numerous different optimization problems.