по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Copyright & Licensing Policy > Publication in 72 hours: How do we do it? > Digital archiving policy > Open Access Policy > Open access publishing costs > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

Assessing Time Dependencies of the Genetic Algorithm Carried Out on CPU and GPU
Agibalov Oleg Igorevich

post-graduate student of the Department of Space-Making Industry and Innovation Technologies at Southern Federal University

344090, Russia, Rostov-on-Don, Mil'chakov's str., 8a

agibalovo@yandex.ru
Ventsov Nikolai Nikolaevich

PhD in Technical Science

Associate Professor, Department of Information Technology, Don State Technical University

344000, Russia, Rostovskaya oblast', g. Rostov-na-Donu, ploshchad' Gagarina, 1

vencov@list.ru
Другие публикации этого автора
 

 

Abstract.

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

DOI:

10.25136/2306-4196.2017.6.24509

Article was received:

01-11-2017


Review date:

02-11-2017


Publish date:

10-11-2017


This article written in Russian. You can find full text of article in Russian here .

References
1.
Sukhoroslov O.V. Organizatsiya vychislenii v geterogennykh raspredelennykh sredakh // Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskii vypusk: Superkomp'yuternye tekhnologii. 2016. №12 (185). S. 115-130.
2.
Chernyshev Yu.O., ,Ventsov N.N., Dolmatov A.A. Rekonfiguriruemyi agent v nechetkom geterogennom prostranstve reshenii // Inzhenernyi vestnik Dona, 2017, № 2,URL: http:// http://ivdon.ru/ru/magazine/archive/N2y2017/4163
3.
Agibalov O.I., Zolotarev A.A. Sovremennye graficheskie protsessory kak sredstva optimizatsii parallel'nykh vychislenii // Naukoemkie tekhnologii v kosmicheskikh issledovaniyakh Zemli, 2014. T.6. № S. 60-63.
4.
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.
5.
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.
6.
Saprykin A.N., Akinina K.D., Saprykina E.N. Nakhozhdenie optimal'nogo chisla poleznykh osobei v populyatsii i konvergiruemykh pokolenii geneticheskogo algoritma optimizatsii prostykh mnogoekstremal'nykh funktsii //Actualscience. 2016. T. 2. № 11. S. 168-169.
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.
"History Illustrated" Website