Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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

Agibalov Oleg Igorevich

Project Manager

344038, Russia, Rostov-on-Don, Nansena str., 107/1

agibalovo@yandex.ru
Other publications by this author
 

 
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
Other publications by this author
 

 

DOI:

10.25136/2644-5522.2017.6.24509

Received:

22-10-2017


Published:

10-11-2017


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:

population-based algorithms, optimization, time complexity, central processing unit, graphics processing unit, genetic algorithm, chromosome, population, optimization of the algorithm, efficient frontier


Введение

В настоящее время усложняются не только непосредственные процессы поиска оптимальных решений, но и связанные с ними процессы управления доступными вычислительными ресурсами [3,4]. Относительно новым подходом к распределению вычислительных ресурсов является применение GPU для решения оптимизационных задач. Изначально графические процессоры предназначались исключительно для обработки графических операций в компьютерной графике. Однако возможности архитектуры этих устройств были оценены профессионалами, занимающимися научными вычислениями. После этого производители графических процессоров перестроили архитектуры таким образом, чтобы на них можно было производить вычисления общего (не графического) характера [2].

Активное использование ресурсов GPU для решения классических оптимизационных задач требует не только исследования особенностей использования алгоритмов, ориентированных на GPU, но и сравнение эффективности использования алгоритмов, разработанных для GPU и  CPU [1,5].

 

Постановка задачи

При разработке генетических алгоритмов существенное влияние уделяется не только выбору архитектуры генетического поиска, но и количеству используемых особей (хромосом). Например, в работе [6] рассматривается задача правильного определения оптимального числа конвергируемых поколений и оптимального числа особей, используемых в генетическом алгоритме оптимизации простых многоэкстремальных функций. Установлено, что существует определенный рубеж, после превышения которого дальнейшее увеличение рассматриваемых параметров (число итераций работы алгоритма и число особей в популяции) становится неэффективным, если значения параметров находятся ниже значения рубежа, результаты работы алгоритма значительно ухудшаются. На основе полученных данных можно сделать вывод, что корректный выбор значений числа особей в популяции и числа поколений генетического алгоритма оптимизации простых многоэкстремальных функций значительно повышает его эффективность [6].

Если будет известно необходимое количество особей в популяциях, то, с точки зрения управления вычислительными ресурсами, актуальной становится задача выбора аппаратной составляющей, на которой используемый алгоритм будет реализован за наименьшее время. Примером такой задачи может быть выбор между реализацией алгоритма на GPU или CPU. Поэтому необходимо определить границы более эффективной реализации каждой версии алгоритма.

В качестве целевой функции рассмотрим 20-мерную функцию Экли:

- где n- количество аргументов функции.

 

Необходимо определить зависимости времени работы алгоритмов, реализованных для CPU и GPU, от количества особей в популяции. Поскольку генетический алгоритм носит стохастический характер, была проведена серия экспериментов, результаты которых приведены ниже.

 

Таблица 1. Зависимость общего времени работы генетического GPU-алгоритма

от числа хромосом

Количество хромосом

№ эксперимента

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

1

1023

913

1010

1275

1427

1535

1605

1571

1767

2493

2

948

1064

965

1248

1593

1369

1328

1748

1924

1957

3

827

994

1036

1147

1489

2297

1722

1582

2056

1925

4

907

1091

1078

1279

1353

1533

1633

1819

1755

2401

5

920

984

1865

1349

1348

1557

1535

1551

1575

1811

6

866

994

1142

1051

1344

1398

1296

1837

1844

1609

7

935

1025

1110

1207

1694

1437

1937

1634

1799

1820

8

1023

1080

1271

1610

1679

1413

2067

2146

1710

1776

9

967

1064

1020

1536

1440

1747

1520

1710

1719

1853

10

884

1194

1177

1268

1344

1341

1604

1824

2027

2172

Среднее время, мс

930

1040

1167

1297

1471

1563

1625

1742

1818

1982

 

 

Таблица 2. Зависимость общего времени работы генетического алгоритма, выполненного на CPU, от числа хромосом

Количество хромосом

№ эксперимента

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

1

454

788

1644

1343

1841

1708

2290

2515

2495

3378

2

674

1186

1408

1757

1886

2104

2275

2745

3039

3841

3

437

882

1043

1392

2315

1991

2178

2909

3135

2978

4

544

989

1060

1230

2224

1512

2123

2798

2545

3093

5

1253

940

1375

1339

1400

1910

2865

2436

2855

3347

6

445

695

1021

1513

1239

1556

2589

2223

2502

3071

7

434

1036

895

1583

1594

1874

1771

2386

2446

2577

8

1138

757

967

1403

1701

1662

2107

2874

2749

3433

9

796

715

1211

1512

1669

2211

2126

2064

2561

2860

10

506

923

1363

1499

1361

2036

2406

2278

2965

2793

Среднее время, мс

668

891

1199

1457

1723

1856

2273

2523

2729

3137

 

Данные, представленные в таблицах 1 и 2, позволяют построить сравнительную таблицу усредненных зависимостей времени реализации алгоритма на CPU и GPU.

Таблица 3. Усредненные зависимости общего времени

 выполнения алгоритма на GPU и ЦП

Количество хромосом

Время GPU, мс

Время ЦП, мс

1000

930

668

2000

1040

891

3000

1167

1199

4000

1297

1457

5000

1471

1723

6000

1563

1856

7000

1625

2273

8000

1742

2523

9000

1818

2729

10000

1982

3137

Графическая форма данных из таблицы 3 приведена на рисунке 1.

 

Рис. 1 Графики усредненных зависимостей общего времени выполнения алгоритмов на GPU и CPU

Из представленных на рисунке данных следует, что при увеличении популяции до 3000-4000 хромосом алгоритм на графическом процессоре начинает опережать алгоритм на центральном процессоре. Определить точную границу предпочтительности каждого алгоритма невозможно по причине стохастичности алгоритма.

Архитектуре  GPU требуется некоторое время на этап инициализации, в процессе которого готовится процессор, загружаются библиотеки и происходят другие операции, которые мы, как разработчики, контролировать не можем. Распределение времени требуемого для работы алгоритмов, на CPU и GPU,  приведено в таблице 3.

 

Таблица 3. Распределение времени, требуемое для работы алгоритмов

 

CPU-алгоритм

GPU-алгоритм

Общее время работы, мс

912

1030

Время инициализации, мс

39

563

Время без инициализации, мс

873

467

По причине стохастичности генетического алгоритма фактическое время его работы нельзя описать скалярным значением, даже при фиксированном числе особей в популяции. Для более адекватного описания времени работы можно использовать нечеткие оценки. Можно построить нечёткое число, описывающее время работы алгоритма как качественный показатель. Для этого была проведена серия экспериментов из 30 запусков алгоритма на графическом процессоре для 3000 хромосом. Результаты эксперимента приведены в таблице 4.

Таблица 4. Результаты измерений времени работы алгоритма

Запуск

Время работы, мс

1

1118

2

1009

3

1111

4

1114

5

1133

6

1053

7

1038

8

1041

9

1045

10

1246

11

1148

12

1128

13

1595

14

1122

15

1282

16

1219

17

1262

18

1382

19

1294

20

1023

21

1177

22

1392

23

1074

24

1109

25

1214

26

983

27

1075

28

1412

29

1238

30

1136

Мин

983

Макс

1595

Разбив интервал времени от 900 до 1600 мс на отрезки по 100 делений и посчитав, сколько замеров попали в каждый из них, получим таблицу частотного распределения результатов работы генетического алгоритма.

Таблица 5. Частотное распределение результатов работы генетического алгоритма.

Отрезок, мс

Количество замеров

Процент

Нормализованное значение

900-1000

1

0,03

0,1

1000-1100

8

0,27

0,8

1100-1200

10

0,33

1

1200-1300

7

0,23

0,7

1300-1400

2

0,07

0,2

1400-1500

1

0,03

0,1

1500-1600

1

0,03

0,1

Эталонное значение

 

0,33

 

На основе таблицы 5 построим график распределения частот, по отрезкам рассматриваемого временного интервала.

Рис. 2 График распределения частот, по отрезкам рассматриваемого временного интервала

На рис.3 приведен нормализованный график.

Рис. 3 Нормализованный график распределения частот

Представленные на рис.3 данные  можно трактовать как  функцию нечёткого числа, обозначающего время работы GPU-алгоритма на 3000 хромосомах.

Заключение

1. На основании представленных результатов установлено, что при использовании популяций объёмом до 2000-2500 хромосом генетический алгоритм целесообразнее реализовывать на CPU, а при использовании более 3000-4000 - на  GPU. Это утверждение справедливо исключительно для данной задачи. Для прочих задач, в иных аппаратных и программных условиях эти результаты будут другими. В рассматриваемом случае важны не cтолько количественные оценки сколько сам факт возможности определения такой точки перелома.

2. Размытость границы эффективности обусловлена стохастичностью генетического алгоритма.

3. По причине невозможности получения точной временной оценки генетического алгоритма построена расплывчатая оценка времени работы GPU-алгоритма на популяции размером 3000 хромосом.

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.