ГЛАВНАЯ
> Вернуться к содержанию
Статьи автора Агибалов Олег Игоревич
Кибернетика и программирование, 2017-6
|
Агибалов О.И., Венцов Н.Н. - Оценка зависимостей времени работы генетического алгоритма, выполняемого на CPU и GPU |
|
c. 1-8
|
DOI: 10.25136/2644-5522.2017.6.24509
Аннотация: Предметом исследования является проблема выбора наиболее эффективной аппаратной архитектуры для реализации стохастического популяционного алгоритма. Объект исследования – генетический алгоритм, выполняемый на центральном процессоре (central processing unit, CPU) и графическом процессоре (graphics processing unit, GPU). Приведены результаты вычислительного эксперимента, проведенного с целью сравнения зависимостей времени работы генетического алгоритма, выполняемого на центральном процессоре и графическом процессоре, от используемого количества хромосом. Приведено сопоставление как общего времени решения задачи, так и времени, необходимого для инициализации CPU и GPU. По причине невозможности получения точной временной оценки генетического алгоритма построена расплывчатая оценка времени работы GPU-алгоритма на 3000 хромосом. Метод исследования базируется на экспериментальной оценке зависимостей времени работы генетического алгоритма выполняемого на CPU и GPU от количества особей в популяции. Вычислительная сложность реализации генетического алгоритма на обоих видах процессоров приблизительно соответствует величине O(n)-O(n2). На основании представленных результатов установлено, что при использовании популяции размером до 2000-2500 хромосом генетический алгоритм целесообразнее реализовывать на CPU, а при использовании более 3000-4000 хромосом - на GPU. Размытость границы эффективности обусловлена стохастичностью генетического алгоритма. Полученные оценки границ целесообразности выбора аппаратной архитектуры справедливы исключительно для данной задачи. Для прочих задач, в иных аппаратных и программных условиях эти результаты будут другими. В рассматриваемой ситуации важна не только числовая оценка границы эффективности, но и сам факт возможности определения такой точки перелома.
|