Mustafa Servet KIRAN, Ahmet Cevahir ÇINAR

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

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.

Anahtar Kelimeler:

Tree-seed algorithm, CUDA; parallel computation; benchmark function

PDF

___

Çınar, A.C., A Cuda-based Parallel Programming Approach to Tree-Seed Algorithm, MSc Thesis, Selçuk University, GRADUATE SCHOOL OF NATURAL SCIENCES, 2016.
Akyol, S. ve Alataş, B., “Kedi sürüsü optimizasyon algoritmasıyla doğru ve anlaşılabilir nümerik sınıflandırma kurallarının otomatik keşfi”, Journal of the Faculty of Engineering and Architecture of Gazi University, Cilt 31, No 4, 839-857, 2016.
Haklı, H., Sürekli Fonksiyonların Optimizasyonu için Doğa Esinli Algoritmaların Geliştirilmesi, Yüksek Lisans Tezi, Selçuk Üniversitesi Fen Bilimleri Enstitüsü, 2013.
Kıran, M.S., “TSA: Tree-seed algorithm for continuous optimization”, Expert Systems with Applications, Cilt 42, No 19, 6686-6698, 2015.
Kıran, M.S., “An Implementation of Tree-Seed Algorithm (TSA) for Constrained Optimization”, Intelligent and Evolutionary Systems, Springer, 189-197, 2016.
Muneeswaran, V. ve Rajasekaran, M.P.“Performance evaluation of radial basis function networks based on tree seed algorithm”, in 2016 International Conference on Circuit, Power and Computing Technologies (ICCPCT). 2016.
Nvidia, “Compute unified device architecture programming guide”, 2007.
Mussi, L. ve Cagnoni, S., “Particle swarm optimization within the CUDA architecture”, Viale G. Usberti 181a, I-43124 Parma, Italy, 2009.
Molnár, F., Szakaly, T., Meszaros, R. ve Lagzi, I., “Air pollution modelling using a Graphics Processing Unit with CUDA”, Computer Physics Communications, Cilt 181, No 1, 105-112, 2010.
Mussi, L., Daolio, F. ve Cagnoni, S., “Evaluation of parallel particle swarm optimization algorithms within the CUDA™ architecture”, Information Sciences, Cilt 181, No 20, 4642-4657, 2011.
Solomon, S., Thulasiraman, P. ve Thulasiram, R.“Collaborative multi-swarm PSO for task matching using graphics processing units”, in Proceedings of the 13th annual conference on Genetic and evolutionary computation. 2011. ACM.
Zhang, Z. ve Seah, H.S.“CUDA acceleration of 3D dynamic scene reconstruction and 3D motion estimation for motion capture”, in Parallel and Distributed Systems (ICPADS), 2012 IEEE 18th International Conference on. 2012. IEEE.
Platos, J., Snasel, V., Jezowicz, T., Kromer, P. ve Abraham, A.“A PSO-based document classification algorithm accelerated by the CUDA platform”, in Systems, Man, and Cybernetics (SMC), 2012 IEEE International Conference on. 2012. IEEE.
Kumar, J., Singh, L. ve Paul, S.“GPU based parallel cooperative particle swarm optimization using C-CUDA: a case study”, in Fuzzy Systems (FUZZ), 2013 IEEE International Conference on. 2013. IEEE.
Wang, H., Rahnamayan, S. ve Wu, Z., “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, Cilt 73, No 1, 62-73, 2013.
Wang, H., Wu, Z. ve Rahnamayan, S., “Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems”, Soft Computing, Cilt 15, No 11, 2127-2140, 2011.
Kneusel, R., “Curve-Fitting on Graphics Processors Using Particle Swarm Optimization”, International Journal of Computational Intelligence Systems, Cilt 7, No 2, 213-224, 2014.
Luo, G.-H., Huang, S.-K., Chang, Y.-S. ve Yuan, S.-M., “A parallel Bees Algorithm implementation on GPU”, Journal of Systems Architecture, Cilt 60, No 3, 271-279, 2014.
Janousešek, J., Gajdoš, P., Radecký, M. ve Snášel, V.“Classification via Nearest Prototype Classifier Utilizing Artificial Bee Colony on CUDA”, in International Joint Conference SOCO’14-CISIS’14-ICEUTE’14. 2014. Springer.
Rymut, B. ve Kwolek, B., “Real‐time multiview human pose tracking using graphics processing unit‐accelerated particle swarm optimization”, Concurrency and Computation: Practice and Experience, Cilt 27, No 6, 1551-1563, 2015.
Yuan, H., Zhao, T., Yang, W. ve Pan, H., “1821. Annealing evolutionary parallel algorithm analysis of optimization arrangement on mistuned blades with non-linear friction”, Journal of Vibroengineering, Cilt 17, No 8, 2015.
Bukharov, O.E. ve Bogolyubov, D.P., “Development of a decision support system based on neural networks and a genetic algorithm”, Expert Systems with Applications, Cilt 42, No 15, 6177-6183, 2015.
Wang, P., Li, H. ve Zhang, B., “A GPU-based Parallel Ant Colony Algorithm for Scientific Workflow Scheduling”, International Journal of Grid and Distributed Computing, Cilt 8, No 4, 37-46, 2015.
Kai, Z., Ming, Q., Lin, L. ve Xiaoming, L., “Solving Graph Coloring Problem by Parallel Genetic Algorithm Using Compute Unified Device Architecture”, Journal of Computational and Theoretical Nanoscience, Cilt 12, No 7, 1201-1205, 2015.
Kalivarapu, V. ve Winer, E., “A study of graphics hardware accelerated particle swarm optimization with digital pheromones”, Structural and Multidisciplinary Optimization, Cilt 51, No 6, 1281-1304, 2015.
Silva, E.H. ve Bastos Filho, C.J., “PSO Efficient Implementation on GPUs Using Low Latency Memory”, Latin America Transactions, IEEE (Revista IEEE America Latina), Cilt 13, No 5, 1619-1624, 2015.
Akgün, D. ve Erdoğmuş, P., “GPU accelerated training of image convolution filter weights using genetic algorithms”, Applied Soft Computing, Cilt 30, 585-594, 2015.
Zarrabi, A., Samsudin, K. ve Karuppiah, E.K., “Gravitational search algorithm using CUDA: a case study in high-performance metaheuristics”, The Journal of Supercomputing, Cilt 71, No 4, 1277-1296, 2015.
Tsuchida, Y. ve Yoshioka, M., “A Parallelization Method for Neural Network Learning”, Electrical Engineering in Japan, Cilt 191, No 2, 17-23, 2015.
Ouyang, A., Tang, Z., Zhou, X., Xu, Y., Pan, G. ve Li, K., “Parallel hybrid pso with cuda for ld heat conduction equation”, Computers & Fluids, Cilt 110, 198-210, 2015.
Bukata, L., Šůcha, P. ve Hanzálek, Z., “Solving the Resource Constrained Project Scheduling Problem using the parallel Tabu Search designed for the CUDA platform”, Journal of Parallel and Distributed Computing, Cilt 77, 58-68, 2015.
Peker, M., Şen, B. ve Gürüler, H., “Rapid Automated Classification of Anesthetic Depth Levels using GPU Based Parallelization of Neural Networks”, Journal of medical systems, Cilt 39, No 2, 1-11, 2015.
Lastra, M., Molina, D. ve Benítez, J.M., “A high performance memetic algorithm for extremely high-dimensional problems”, Information Sciences, Cilt 293, 35-58, 2015.
ÇINAR, A.C. ve KIRAN, M.S.“A Parallel Version of Tree-Seed Algorithm (TSA) within CUDA Platform”, in Selçuk International Scientific Conference On Applied Sciences. 2016. Antalya.
Nvidia, “CUDA C PROGRAMMING GUIDE”, 2016.
Zarrabi, A., Karuppiah, E.K., Kok, Y.K., Hai, N.C. ve See, S.“Gravitational Search Algorithm Using CUDA”, in Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2014 15th International Conference on. 2014. IEEE.