Analisis Kinerja Genetic Algorithm yang diakselerasi untuk Travelling Salesman Problem pada Platform Multicore CPU dan CUDA

Alexander Thomas Kurniawan Pratomo(1*), Henry Novianus Palit(2), Darian Gunamardi(3),


(1) Program Studi Informatika
(2) Program Studi Informatika
(3) Program Studi Informatika
(*) Corresponding Author

Abstract


Advancement in technology brings about both new challenges and opportunities. One of which is the opportunity to accelerate an algorithm which usually took a very long time to finish. Genetic algorithm is one such algorithm that can be accelerated using these advancements. Certain ways to accelerate this algorithm is done by tuning the parameters, but these methods are usually unable to retain the quality that is obtained from previous, non-accelerated method. This research applies parallel computing using the multicore technology of CPU and GPU to accelerate genetic algorithm without any changes to the parameters. The purpose of the research is to analyze the differences in performance of the algorithm upon being accelerated with the technologies. The technologies used are CUDA platform and OpenMP API for GPU and CPU respectively. Aside from the technology itself, choosing the algorithm segments on which the implementation is done will also greatly affect the performance of the algorithm. According the testing results, Genetic Algorithm can be accelerated with parallelization using either OpenMP with CPU or CUDA with GPU.

Keywords


Genetic Algorithm; Parallel Computing; Compute Unified Device Architecture; Graphics Processing Unit; Multicore Central Processing Unit; OpenMP

Full Text:

PDF

References


Barney, B. URI=https://computing.llnl.gov/tutorials/parallel_comp/

Greco, F. 2008. Traveling salesman problem. SL: Sciyo.com.

Horton, I. 2015. Using the C standard template libraries. New York: Apress.

Intel. 2015, January 01. Threading Models for High-Performance Computing: Pthreads or OpenMP? URI=https://software.intel.com/en-us/articles/threadingmodels-for-high-performance-computing-pthreads-oropenmpNvidia.[5] Kramer, O. 2017. Genetic algorithm essentials. Cham: Springer.

McCool, M. D., Robison, A. D., & Reinders, J. 2012. Structured parallel programming: patterns for efficient computation. Waltham: Morgan Kaufmann.

Nvidia. CUDA Zone. URI=https://developer.nvidia.com/cuda-zone

Nvidia. 2019, November. Thrust Quick Star Guide. URI=https://docs.nvidia.com/pdf/Thrust_Quick_Start_Guide.pdf

Oiso, M., Matsumura, Y., Yasuda, T., & Ohkura, K. 2011. Implementation Method of Genetic Algorithms to the CUDA Environment using Data Parallelization. Journal of Japan Society for Fuzzy Theory and Intelligent Informatics, 23(1), 18-28. doi:10.3156/jsoft.23.18

OpenMP ARB. OpenMP FAQ. URI=https://www.openmp.org/about/openmp-faq/

Werkhoven, B. V., Maassen, J., Seinstra, F., & Bal, H. 2014. Performance Models for CPU-GPU Data Transfers. 2014 14th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. doi:10.1109/ccgrid.2014.16

University of Waterloo. 2001. CA4663 [Data file]. Retrieved from University of Waterloo. URI=http://www.math.uwaterloo.ca/tsp/world/ca4663.tsp

University of Waterloo. 2001. FI10639 [Data file]. Retrieved from University of Waterloo. URI=http://www.math.uwaterloo.ca/tsp/world/fi10639.tsp

University of Waterloo. 2001. IT16862 [Data file]. Retrieved from University of Waterloo. URI=http://www.math.uwaterloo.ca/tsp/world/it16862.tsp


Refbacks

  • There are currently no refbacks.


Jurnal telah terindeks oleh :