Ağaç-tohum algoritması için cuda tabanlı bir paralel programlama yaklaşımı

Abstract

Son yıllarda, grafik işlem birimi ile genel amaçlı hesaplama (GPGPU) paralel hesaplama alanında büyük bir popülerlik kazanmıştır ve GPGPU kullanımı gün geçtikçe merkezi işlem birimi (CPU) üretim teknolojisinin fiziksel sınırlarına yaklaşmasından dolayı pek çok yüksek boyutlu zaman alıcı sorunları çözmek için artmaktadır.GPGPU popülerleşmesinde son yıllarda veri miktarında meydana gelen artış gösterilebilir çünkü seri programlama ile bu verinin işlenmesinde zaman sorunu ortaya çıkmıştır. Ayrıca kolay kullanılabilir paralel programlama geliştirme ortamlarının artması da bu süreci desteklemiştir. Bu çalışmada popülasyon tabanlı metesezgisel algoritmalardan ağaçlar ile tohumları arasındaki neslin devamını modelleyen Ağaç-Tohum Algoritması' nın (TSA) paralelleştirilmesi üzerinde durulmuştur. Bu tezde TSA paralel geliştirme ortamlarından CUDA üzerinde gerçeklenmiştir. Deneysel sonuçlar yüksek boyutlu ve yüksek ağaç sayılı(popülasyon boyutu) problemlerin çözümünde paralel TSA'nın seri olan gerçeklenmesine göre yaklaşık 184 kat daha hızlı olduğunu göstermiştir.

In recent years, the general purpose computing on graphical processing unit (GPGPU) have gained a huge popularity in field of parallel computing and the usage of GPGPU has increased to solve many high-dimensional time-consuming problems day by day because central processing unit (CPU) technology approaches to the physical limits in increment processor speed.The main motivation behind the popularity of GPGPU is the huge amount of data emergent in recent years, time problem in serial programming to process these data and developed lucidity and wieldy tools for parallel programming.This paper focuses on parallelization of tree-seed algorithm (TSA) which is one of the population-based metaheuristic algorithms, inspired by natural behaviors of trees and their seed production. In this thesis, TSA is implemented on the computer unified device architecture (CUDA) parallel development environment. Experimental results show that when the high-dimensional or high number of trees (population) is used while the problemis solved, parallel implementation of TSA is faster than serial implementation about 184 times.