Рус Eng Cn 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

Software systems and computational methods
Reference:

Assessment of parameters and results of genetic algorithms performed on the GPU and CPU

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.7256/2454-0714.2019.3.30502

Received:

09-08-2019


Published:

26-08-2019


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

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

Введение. Планирование работы современных интеллектуальных систем подразумевает эффективное распределение имеющихся вычислительных ресурсов. Серверы, а также домашние персональные компьютеры, обладают вычислительными ресурсами различной архитектуры, например, наряду с центральным процессором (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, близки к линейной функции, а максимальные - к полиномиальной.

References
1.
2.
3.
4.
5.
6.