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

Authors

  • Alexander Thomas Kurniawan Pratomo Program Studi Informatika
  • Henry Novianus Palit Program Studi Informatika
  • Darian Gunamardi Program Studi Informatika

Keywords:

pile integrity test, reduksi penampang tiang, pondasi tiang, quality assurance

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.

References

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

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

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

[4] 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.

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

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

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

[9] 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

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

[11] 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

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

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

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

Downloads

Published

2020-04-22

Issue

Vol. 8 No. 1 (2020)

Section

Articles