Ağaç-tohum algoritmasının CUDA destekli grafik işlem birimi üzerinde paralel uygulaması

Abstract

Son yıllarda toplanan verinin artmasıyla birlikte verimli hesaplama yöntemlerinin de geliştirilmesi ihtiyacı artmaktadır. Çoğunlukla gerçek dünya problemlerinin zor olması sebebiyle optimal çözümü garanti etmese dahi makul zamanda yakın optimal çözümü garanti edebilen sürü zekâsı veya evrimsel hesaplama yöntemlerine olan ilgi de artmaktadır. Diğer bir açıdan seri hesaplama yöntemlerinde verinin veya işlemin paralelleştirilebileceği durumlarda paralel algoritmaların da geliştirilmesi ihtiyacı ortaya çıkmıştır. Bu çalışmada literatüre son yıllarda kazandırılmış olan popülasyon tabanlı ağaç-tohum algoritması ele alınmış ve CUDA platformu içerisinde paralel versiyonu geliştirilmiştir. Algoritmanın paralel versiyonunun performansı kıyas fonksiyonları üzerinde analiz edilmiş ve seri versiyonunun performansı ile karşılaştırılmıştır. Kıyas fonksiyonlarında problem boyutluluğu 10 olarak alınmış ve farklı popülasyon ve blok sayıları altında performans analizi yapılmıştır. Deneysel çalışmalar algoritmanın paralel versiyonunun algoritmanın seri sürümüne göre bazı problemler için 184,65 kata performans artışı sağladığı görülmüştür.

In recent years, while the collected data are increased, we need effective computation methods to process these data. Due to the fact that most of the real world problems are difficult to solve, swarm intelligence and evolutionary computation algorithms are interested because they guarantee the near optimal solution for the problem in a reasonable time but not guarantee the optimal solution. In another perspective, if the data or process can be parallelized, the parallel computation is a good choice instead of serial programming approaches in terms of time effectiveness. In this study, the tree-seed algorithm, which is a recently proposed population-based iterative search algorithm, is implemented within CUDA platform in parallel. The performance of the parallel version of the algorithm has been investigated on the benchmark functions and compared with the performance of the serial version of the algorithm. The dimensionality of the problems is taken as 10 and the performance analysis and comparisons have been conducted under the condition of different sizes of the population. Experimental studies show that the parallel version of the algorithm is accelerated to 184.65 times in accordance with the serial version of the algorithm on some problems.