Question at hand
Agibalov O.I., Ventsov N.N. —
Assessing Time Dependencies of the Genetic Algorithm Carried Out on CPU and GPU
// Cybernetics and programming. – 2017. – ¹ 6.
– P. 1 - 8.
Read the article
Review: The subject of the research is the problem of choosing the most efficient hardware architecture to execute a stochastic population-based algorithm. The object of the research is the genetic algorithm carried out using the central processing unit (CPU) or graphics processing unit (GPU). In their research the authors give results of a computational experiment aimed at comparing time dependencies of the genetic algorithm executed on the central processing unit or graphics processing unit based on the number of chromosomes used. The authors also compare the overall time of task solutions and time necessary to initialize CPU and GPU. Due to the fact that it was impossible to obtain the precise time assessment of the genetic algorithm, the authors have developed a loose time assessment of GPU-algorithm for 3000 chromosomes. The research method is based on the experimental assessment of time dependencies of the genetic algorithm executed using CPU or GPU based on the number of species in the population. The computational complexity of the genetic algorithm for both types of processing units is approximately O(n)-O(n2). Based on the results the authors have stated that in cases when the population is 2000-2500 chromosomes, the genetic algorithm should be better executed using CPU and when the population exceeds 3000-4000 chromosomes it is better to execute it using GPU. Such unclarity of efficiency frontiers is caused by the stochastic nature of the genetic algorithm. It should be also noted that these frontiers for choosing the most efficient hardware architecture are right exclusively for solving the above mentioned task. The results will be different for simpler tasks and other hardware and software conditions. The present research focuses not only on the numerical assessment of efficiency frontiers but on whether such crossing point can be defined or not.
Keywords: optimization of the algorithm, population, chromosome, genetic algorithm, graphics processing unit, time complexity, central processing unit, optimization, population-based algorithms, efficient frontier
Saprykin A.N., Akinina K.D., Saprykina E.N. Nakhozhdenie optimal'nogo chisla poleznykh osobey v populyatsii i konvergiruemykh pokoleniy geneticheskogo algoritma optimizatsii prostykh mnogoekstremal'nykh funktsiy //Actualscience. 2016. T. 2. ¹ 11. S. 168-169.
Zololaterev A.A., Agibalov O.I. Abilities of Modern Graphics Adapters for Optimizing Parallel Computing//World Applied Scientific Journal, 2013. V. 23 (5). P. 644-649.
Zolotarev A.A., Ventsov N.N., Agibalov O.I., Deeva A.S. Optimizatsiya raspredelitel'nykh protsessov na osnove analiticheskikh metodov i evristicheskikh algoritmov //Vestnik nauki i obrazovaniya Severo-Zapada Rossii. 2016. T. 2. ¹ 1. S. 74-82.
Agibalov O.I., Zolotarev A.A. Sovremennye graficheskie protsessory kak sredstva optimizatsii parallel'nykh vychisleniy // Naukoemkie tekhnologii v kosmicheskikh issledovaniyakh Zemli, 2014. T.6. ¹ S. 60-63.
Sukhoroslov O.V. Organizatsiya vychisleniy v geterogennykh raspredelennykh sredakh // Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskiy vypusk: Superkomp'yuternye tekhnologii. 2016