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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

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

аспирант

Аннотация

Предметом исследования является проблема выбора наиболее эффективной аппаратной архитектуры для реализации стохастического популяционного алгоритма. Объект исследования - генетический алгоритм, выполняемый на центральном процессоре (central processing unit, CPU) и графическом процессоре (graphics processing unit, GPU). Приведены результаты вычислительного эксперимента, проведенного с целью сравнения зависимостей времени работы генетического алгоритма, выполняемого на центральном процессоре и графическом процессоре, от используемого количества хромосом. Приведено сопоставление как общего времени решения задачи, так и времени, необходимого для инициализации CPU и GPU. По причине невозможности получения точной временной оценки генетического алгоритма построена расплывчатая оценка времени работы GPU-алгоритма на 3000 хромосом. Метод исследования базируется на экспериментальной оценке зависимостей времени работы генетического алгоритма выполняемого на CPU и GPU от количества особей в популяции. Вычислительная сложность реализации генетического алгоритма на обоих видах процессоров приблизительно соответствует величине O(n)-O(n2). На основании представленных результатов установлено, что при использовании популяции размером до 2000-2500 хромосом генетический алгоритм целесообразнее реализовывать на CPU, а при использовании более 3000-4000 хромосом - на GPU. Размытость границы эффективности обусловлена стохастичностью генетического алгоритма.Полученные оценки границ целесообразности выбора аппаратной архитектуры справедливы исключительно для данной задачи. Для прочих задач, в иных аппаратных и программных условиях эти результаты будут другими. В рассматриваемой ситуации важна не только числовая оценка границы эффективности, но и сам факт возможности определения такой точки перелома.

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

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:

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

Введение

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

Библиография

Размещено на Allbest.ru