Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Программные системы и вычислительные методы
Правильная ссылка на статью:

Оценка параметров и результатов работы генетических алгоритмов выполняемых на GPU и CPU

Агибалов Олег Игоревич

Менеджер проектов

344038, Россия, г. Ростов-На-Дону, ул. Нансена, 107/1

Agibalov Oleg Igorevich

Project Manager

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

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

 
Венцов Николай Николаевич

кандидат технических наук

доцент, Донской государственный технический университет

344000, Россия, Ростовская область, г. Ростов-на-Дону, площадь Гагарина, 1

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
Другие публикации этого автора
 

 

DOI:

10.7256/2454-0714.2019.3.30502

Дата направления статьи в редакцию:

09-08-2019


Дата публикации:

26-08-2019


Аннотация: Объектом исследования являются процессы выбора оптимальной аппаратной архитектуры при организации ресурсоемких вычислений. Предметом исследования являются процессы решения оптимизационных задач генетическими алгоритмами на GPU и CPU архитектурах. Показано влияние выбора аппаратной архитектуры на процесс решения оптимизационной задачи: определены абсолютные и относительные зависимости замедления вычислительного процесса, при выборе нерациональной аппаратной архитектуры, от числа особей, обрабатываемых алгоритмом. Установлено, что для рассматриваемой задачи граница наиболее эффективной аппаратной конфигурации может находиться в диапазоне от 1000 до 5000 особей. По этой причине, размытость границы эффективной аппаратной конфигурации целесообразно описывать как множество пар «число особей- принадлежность к переходу» Метод исследования базируется на анализе результатов проведенного вычислительного эксперимента. Целью эксперимента является определение зависимостей времени выполнения генетического алгоритма (ГА) на GPU и CPU архитектурах от числа генерируемых особей (хромосом). Проведено сопоставление зависимостей минимального и максимального времени работы генетического алгоритма, выполняемого на GPU и CPU от числа особей. Показано, что при решении рассмотренной задачи минимальные и максимальные временные зависимости алгоритма, выполненного на GPU, близки к линейной функции; минимальные временные зависимости алгоритма, выполненного на СPU близки к линейной функции, а максимальные - к полиномиальной.


Ключевые слова:

Оптимизация вычислений, генетический алгоритм, адаптация, центральный процессор, графический процессор, интеллектуальные системы, предпочтительная аппаратная архитектура, эволюция, многопоточность, моделирование

Работа выполнена при поддержке РФФИ, проекты: 19-01-00357, 18-01-00314

Abstract: The object of research is the process of choosing the optimal hardware architecture for organizing resource-intensive computing. The subject of the research is the process of solving optimization problems by genetic algorithms on GPU and CPU architectures. The influence of the choice of hardware architecture on the process of solving the optimization problem is shown: the absolute and relative dependences of the slowdown of the computing process, when choosing an irrational hardware architecture, on the number of individuals processed by the algorithm are determined. It is established that for the considered problem, the boundary of the most efficient hardware configuration can be in the range from 1000 to 5000 individuals. For this reason, it is advisable to describe the blurring of the boundary of an effective hardware configuration as a set of pairs “number of individuals — membership in a transition”. The research method is based on an analysis of the results of a computational experiment. The purpose of the experiment is to determine the dependencies of the runtime of the genetic algorithm on the GPU and CPU architectures on the number of individuals generated (chromosomes). The dependences of the minimum and maximum time of the genetic algorithm running on the GPU and CPU on the number of individuals are compared. It is shown that when solving the considered problem, the minimum and maximum time dependences of the algorithm performed on the GPU are close to a linear function; the minimum time dependences of the algorithm performed on CPU are close to a linear function, and the maximum to polynomial.


Keywords:

optimize calculations, genetic algorithm, adaptation, central processing unit, graphics processing unit, intelligent system, preferred hardware architecture, evolution, multithreading, modeling

Введение. Планирование работы современных интеллектуальных систем подразумевает эффективное распределение имеющихся вычислительных ресурсов. Серверы, а также домашние персональные компьютеры, обладают вычислительными ресурсами различной архитектуры, например, наряду с центральным процессором (CPU) может присутствовать мощный графический процессор (GPU). В настоящее время GPU-процессоры активно используются для реализации вычислений, напрямую несвязанных с обработкой графической информации [1]. Поэтому, актуальной становится проблема выбора оптимальной аппаратной архитектуры, на которой будет выполняться запланированный к исполнению алгоритм. Стохастические алгоритмы являются важной частью современных архитектур интеллектуальных систем, например, таких как САПР, в которых требуется многократное итеративное решение оптимизационных задач большой размерности.

Решение современных оптимизационных задач, например, связанных с проектированием СБИС, требует итерационного нечеткого анализа декомпозированных подзадач [2]. Декомпозиция подразумевает независимое решение фрагментов рассматриваемой задачи, а итерационность – повторное решение рассмотренной ранее задачи с некоторыми изменениями. Декомпозировать задачу целесообразно, в том числе, с учетом характеристик вычислительных ресурсов таким образом, чтобы алгоритмы, решающие полученные подзадачи, успешно завершили свою работу за отведенное время на имеющейся аппаратной архитектуре. Планируя очередную итерацию, связанную с решением некоторого фрагмента проектной задачи, целесообразно оценить результаты работы алгоритма на предшествующей итерации. Для анализа решения на более высоком уровне иерархии, например, при верификации полученных результатов проектирования, необходимо, чтобы были решены все задачи, в том числе оптимизационные, на текущем уровне. По этой причине актуальной является проблема решения всех задач текущего иерархического уровня к заданному времени. В связи с этим, планируя процесс решения декомпозированной оптимизационной задачи, в ряде случаев целесообразно использовать в качестве дополнительного ограничения имеющееся в распоряжении проектировщика время. Выбор аппаратной архитектуры и параметров реализуемого алгоритма, при этом, необходимо производить с учетом ограничений по времени.

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

С целью последующего анализа проблемы исследования был проведен вычислительный эксперимент, суть которого состояла в том, что для заданного количества особей осуществлялась серия многократных запусков ГА на GPU и CPU, определяющих точки, соответствующие оптимальным значениям функции Экли [4]. Для каждой серии запусков, соответствующей количеству особей в популяции, определялось минимальное, среднее и максимальное время работы алгоритма на каждой аппаратной архитектуре. На рис. 1 приведены графики усредненных зависимостей времени t работы генетического алгоритма, выполняемого на GPU и CPU архитектурах, от количества используемых особей N.

1

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

В рассматриваемом случае (рис.1) среднее значение - это усреднённый параметр по всем запускам при некотором объёме популяции. В отличие от среднего арифметического между минимумом и максимумом, он представляет собой параметр, смещённый в сторону наибольшего скопления результатов, отражающих производительность алгоритма.

Среднее время работы и построенные на его основе временные характеристики работы алгоритмов, являются достаточно информативными характеристиками. При планировании однократных, безальтернативных, в плане использования аппаратных архитектур, и независимых, в плане применения полученных ранее результатов запуска других алгоритмов, таких характеристик может быть вполне достаточно.

В случае разработки сложных систем, подобных САПР, в которых требуется обеспечить наиболее эффективное решение большого количества задач, средних характеристик может оказаться недостаточно.

В работе [4] было показано, что при увеличении числа особей в популяции, генетический алгоритм, выполняемый на графическом процессоре, начинает опережать алгоритм на центральном процессоре. Данный факт обусловлен тем, что архитектуре GPU требуется некоторое время на этап инициализации, в процессе которого готовится процессор, загружаются библиотеки и выполняются другие операции, которые мы, как разработчики, контролировать не можем.

Так как определить точную границу предпочтительности каждого алгоритма невозможно по причине стохастичности вычислительного процесса [4], построим графики усредненной зависимости запоздания решения задачи, при нерациональном выборе аппаратной архитектуры, на которой будет реализован алгоритм. Из рис. 1 следует, что граница предпочтительности реализации алгоритма на CPU ограничена справа приблизительно 2500-3000 особей, этим же количеством особей слева ограничена предпочтительность использования GPU архитектуры.

Обозначим через to[n] – время работы наиболее предпочтительного алгоритма (реализованного на CPU или GPU) при обработке n – хромосом, tp[n] – время работы менее предпочтительного алгоритма (реализованного на CPU или GPU) при обработке n – хромосом.

График, полученный как разность tp[n] - to[n], можно трактовать как абсолютную погрешность, вызванную неправильным выбором аппаратной архитектуры, на которой будет реализован алгоритм (рис.2). Данный график описывает временные потери, вызванные неправильным выбором аппаратной архитектуры, на которой ГА будет обрабатывать заданное количество особей, например, когда вместо CPU алгоритм был реализован на GPU и наоборот.

2_19

Рис. 2 График зависимости абсолютных оценок возможного замедления выполнения алгоритма от числа особей в популяции

Известно, что диалог «эксперт – ЭВМ» наиболее эффективен, если он происходит в режиме реального времени [5,6]. В случае, если время ожидания результата выходит из зоны комфорта, человек становится самым ненадежным звеном в системе «эксперт-ЭВМ» [5]. Из данных, представленных на рис.2 следует, что в области разграничения предпочтительности используемых аппаратных архитектур, т.е. от 2000 до 4000 особей, абсолютная погрешность не превышает 400 миллисекунд. Но при выполнении алгоритма с 9000 особей замедление составляет 2000 миллисекунд, т.е. 2 секунды, что является ощутимым временным интервалом даже в границах человеческого восприятия времени. В случае итерационных корректировок, полученных ранее решений, подобные замедления при реализации алгоритмов могут оказывать существенное влияние на время проектирования.

График, полученный в соответствии с выражением (tp[n] - to[n])/ to[n], можно трактовать как относительную усреденную погрешность, вызванную неправильным выбором аппаратной архитектуры, на которой будет реализован алгоритм (рис.3).

3_19

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

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

Представленные на рис. 1-3 графики были построены на основе усредненных данных о времени работы генетического алгоритма при выполнении на GPU и CPU архитектурах. В процессе вычислительного эксперимента также фиксировались минимальные и максимальные длительности выполнения ГА на GPU и CPU архитектурах. Отклонения фактического времени выполнения алгоритма от среднего значения в каждом конкретном случае обуславливают априорное размытие границ эффективности имеющихся аппаратных архитектур.

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

Таблица 1. Зависимости минимального, максимального и среднего времени работы ГА на GPU от числа хромосом

№ п/п

Характеристика ГА

Количество хромосом (особей), N

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

1.

tmin, мс

1087

1110

1160

1244

1387

1501

1556

1561

1736

1764

2.

tmax, мс

1687

1549

1742

1830

3441

2646

2482

3164

3165

18311

3.

tmed, мс

1251

1294

1357

1488

1739

1832

1838

2021

2141

2536

4.

tmax – tmin, мс

600

439

582

586

2054

1145

926

1603

1429

16547

Из данных, представленных в таблице 1 следует, что разность между минимальным (tmin) и максимальным (tmax) временем выполнения ГА на GPU при обработке до 10000 особей, составляет от 439 до 16547 мс. При обработке 10000 особей произошло резкое (более чем в пять раз, по сравнению с временем обработки 9000 особей) увеличение максимального времени работы алгоритма до 18311 мс. При этом, среднее время работы алгоритма (tmed) на 10000 особей увеличилось приблизительно на 20%, по сравнению со временем обработки алгоритмом 9000 особей.

В таблице 2 приведены зависимости минимального, максимального и среднего времени работы ГА на CPU архитектуре от числа хромосом.

Таблица 2. Оценка зависимостей минимального, максимального и среднего времени работы ГА на CPU от числа хромосом

№ п/п

Характеристика ГА

Количество хромосом (особей), N

1000

2000

3000

4000

5000

6000

7000

8000

9000

10000

1.

tmin, мс

316

527

896

966

1397

1450

1722

2079

2102

2422

2.

tmax, мс

1574

1947

17772

13091

32625

30960

26301

25107

42279

76444

3.

tmed, мс

576

947

1524

1655

2501

2630

3222

3646

4183

4523

4.

tmax – tmin, мс

1258

1420

16876

12125

31228

29510

24579

23028

40177

74022

Из данных, представленных в таблице 2 следует, что разность между минимальным (tmin) и максимальным (tmax) временем выполнения ГА на CPU при обработке до 10000 особей составляет от 1258 до 74022 мс. При обработке 3000 особей произошло резкое (более чем в 8 раз, по сравнению с временем обработки 2000 особей) увеличение максимального времени работы алгоритма до 17772 мс. При этом, среднее время работы алгоритма (tmed) на 10000 особей увеличилось приблизительно на 60%, по сравнению со временем обработки алгоритмом 2000 особей.

Из данных, представленных в таблицах 1,2 следует, что алгоритмам свойственны единичные замедления работы.

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

4_19

Рис. 4 Графики зависимости минимального времени работы генетического алгоритма, выполняемого на GPU и CPU от числа особей

Из данных, представленных на рис. 4, следует, что для случая минимального времени выполнения алгоритмов на обеих аппаратных архитектурах точка разграничения находится в районе 5000 особей.

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

5_19

Рис. 5. Графики зависимости максимального времени работы генетического алгоритма, выполняемого на GPU и CPU от числа особей

Из данных, представленных на рис. 5, следует, что для случая максимального времени выполнения алгоритмов на обеих аппаратных архитектурах точка разграничения находится в районе 1000 особей.

Представленные на рис 1-5 результаты позволяют утверждать, что для рассматриваемой задачи граница наиболее эффективной аппаратной конфигурации может находиться в диапазоне от 1000 до 5000 особей. По этой причине, размытость R границы эффективной аппаратной конфигурации можно описать как множество пар «число особей- принадлежность к переходу»:

R=<N; f(N; TCPU; TGPU)>,

где N – число особей, обрабатываемых алгоритмом; TCPU – временные характеристики алгоритма, выполняемого на CPU; TGPU – временные характеристики алгоритма, выполняемого на GPU.

Нечеткость границ эффективности применения аппаратных архитектур гетерогенными вычислительными системами при использовании стохастических алгоритмов позволяет рассматривать решение любой четко сформулированной задачи стохастическим алгоритмом как нечеткий процесс.

Заключение

1. Фактическая граница наиболее эффективной аппаратной конфигурации, может существенно отличаться от усредненной. Для рассмотренного случая оптимизации функции Экли, граница, вычисленная на основе усредненных данных, находится в районе 2500-3000 особей, а в экстремальных случаях в диапазоне от 1000 до 5000 особей.

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

3. Минимальные и максимальные временные зависимости алгоритма, выполненного на GPU, близки к линейной функции. Минимальные временные зависимости алгоритма, выполненного на СPU, близки к линейной функции, а максимальные - к полиномиальной.

Библиография
1. Fan Zhang, Zheng Li, Bingnan Wang, Maosheng Xiang, Wen Hong. Hybrid general-purpose computation on GPU (GPGPU) and computer graphics synthetic aperture radar simulation for complex scenes// International Journal of Physical Sciences Vol. 7(8), pp. 1224-1234, 16 February, 2012
2. Курейчик В.М. Особенности построения систем поддержки принятия решений// Известия ЮФУ. Технические науки. 2012. № 7 (132). – С. 92-98.
3. Сапрыкин А.Н., Акинина К.Д., Сапрыкина Е.Н. Нахождение оптимального числа полезных особей в популяции и конвергируемых поколений генетического алгоритма оптимизации простых многоэкстремальных функций //Actualscience. 2016. Т. 2. № 11. – С. 168-169.
4. Агибалов О.И., Венцов Н.Н. Оценка зависимостей времени работы генетического алгоритма, выполняемого на CPU и GPU // Кибернетика и программирование. — 2017.-№ 6.-С.1-8. DOI: 10.25136/2306-4196.2017.6.24509. URL: http://e-notabene.ru/kp/article_24509.html
5. Глушань В.М., Лаврик П.В. Распределенные САПР. Архитектура и возможности.-Старый Оскол: ТНТ, 2014.-188 с.
6. Полковникова Н.А., Курейчик В.М. Разработка модели экспертной системы на основе нечёткой логики Известия Южного федерального университета. Технические науки. – 2014. – № 1 (150). – С. 83-92.
References
1. Fan Zhang, Zheng Li, Bingnan Wang, Maosheng Xiang, Wen Hong. Hybrid general-purpose computation on GPU (GPGPU) and computer graphics synthetic aperture radar simulation for complex scenes// International Journal of Physical Sciences Vol. 7(8), pp. 1224-1234, 16 February, 2012
2. Kureichik V.M. Osobennosti postroeniya sistem podderzhki prinyatiya reshenii// Izvestiya YuFU. Tekhnicheskie nauki. 2012. № 7 (132). – S. 92-98.
3. 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.
4. Agibalov O.I., Ventsov N.N. Otsenka zavisimostei vremeni raboty geneticheskogo algoritma, vypolnyaemogo na CPU i GPU // Kibernetika i programmirovanie. — 2017.-№ 6.-S.1-8. DOI: 10.25136/2306-4196.2017.6.24509. URL: http://e-notabene.ru/kp/article_24509.html
5. Glushan' V.M., Lavrik P.V. Raspredelennye SAPR. Arkhitektura i vozmozhnosti.-Staryi Oskol: TNT, 2014.-188 s.
6. Polkovnikova N.A., Kureichik V.M. Razrabotka modeli ekspertnoi sistemy na osnove nechetkoi logiki Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskie nauki. – 2014. – № 1 (150). – S. 83-92.

Результаты процедуры рецензирования статьи

В связи с политикой двойного слепого рецензирования личность рецензента не раскрывается.
Со списком рецензентов издательства можно ознакомиться здесь.

Оценка параметров и результатов работы генетических алгоритмов выполняемых на GPU и CPU
Журнал: Программные системы и вычислительные методы

Статья посвящена решению актуальной задачи эффективного использования вычислительных ресурсов. Авторы анализируют время работы генетического алгоритма при выполнении расчетов на центральном и графическом процессорах. В модельных экспериментах авторы изменяют объем входных данных (хромосом), использована функция оптимизации. Результат оценивается по комплексу критериев - время (минимальное, максимальное, среднее), абсолютная и относительная погрешности. В статье приведены основные количественные результаты, выполнен анализ полученных зависимостей. Достоинством статьи являются приведенные графические зависимости, наглядно отображающие полученные результаты и позволяющие оценить точку изменения предпочтительности выбора алгоритма обработки.
Для выполненных расчетов авторы оценивают минимальное, среднее и максимальное время работы алгоритма, в этом случае вероятно будет хорошо отражать результат графика биржевого типа (бары). Зависимости рис. 2 и 3 идентичны (что следует из определения абсолютной и относительной погрешностей), отличаются только значениями по оси Y, вероятно стоит их объединить. На рис.3 единицы измерения по Y - проценты?
Для рис. 5 зависимость времени от N для maxCPU имеет 3 максимума, возможно есть неточность вычисления t, или вид кривой имеет объяснение. В последнем случае необходимо указать это в анализе в тексте статье.
Для более легко восприятия графических зависимостей, рекомендуется использовать один тип линий для каждой компоненты. (Рис. 1 - CPU - черный пунктир, Рис. 4-5 - красная сплошная)
Желательно обосновать выбор объема входных данных и шага (почему Nmax=10000 с шагом дискретизации 1000, а не, например, 7000 и 500 чтобы детальнее оценить изменение функции на интервале 1000-3000).
В выводах целесообразно отразить временную компоненту и рассчитанную погрешность, в каком случае она будет минимальна (в данный момент время фигурирует в выводе 2, однако нет упоминания про погрешность).
Замечания не снижают общей ценности работы и носят рекомендательный характер.
Структура статьи отвечает требованиям к научным публикациям. Стиль изложения научный.
Библиографический список содержит публикации из рецензируемых журналов, однако для полнотекстовой статьи должен составлять не менее 12-15. Необходимо расширить библиографию.
Статья может быть опубликована после внесения исправлений.