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

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

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

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

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

Рис. 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 График зависимости абсолютных оценок возможного замедления выполнения алгоритма от числа особей в популяции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 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, близки к линейной функции, а максимальные - к полиномиальной.