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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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