Параллельный алгоритм поиска косяком рыб

Алгоритм поиска косяком рыб, разработанный в 2002 году, — стохастический алгоритм оптимизации, основанный на поведении косяка рыб. Со временем стало понятно, что, с ростом измерений и популяций, время выполнения неуклонно растёт.

Современные графические процессоры превратились в сильно распараллеленные, многопотоковые и многоядерные процессоры с невероятной вычислительной мощностью и пропускной способностью памяти. В связи с этим, инженеры и ученые заинтересовались тем, чтобы использовать графические процессоры для вычислений общего назначения. Для облегчения выполнения данной задачи были разработаны некоторые технологии, такие как CUDA (Compute Unified Device Architecture), поддерживаемая NVIDIA.

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

программа графический алгоритм

1.

Введение

в CUDA

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

Несмотря на усилия по созданию интерфейса программирования приложений на ГПУ, программирование на CUDA так и оставалось довольно трудозатратным. Для преодоления сложностей, связанных с программированием на ГПУ, компания NVIDIA представила параллельную вычислительную платформу общего пользования, называющуюся CUDA. CUDA позволяет автоматически распределять и управлять потоками в ГПУ.

CUDA позволяет программам напрямую взаимодействовать с командами ГПУ, используя при этом минимальный набор расширений. У CUDA есть 3 главные абстракции: иерархия групп потоков, разделяемая память и барьеры для синхронизации NVIDIA. Эти абстракции позволяют разделить задачу на подзадачи, которые, в свою очередь, могут быть решены независимо и параллельно. Каждая подзадача затем может быть разбита на операции, решаемые параллельно всеми потоками из блока.

Главным узким местом в архитектуре CUDA является передача данных между хостом (ЦПУ) и ГПУ. Любая передача данных от ЦПУ к ГПУ снижает производительность, таким образом нужно стараться избегать данной операции. В частности, в качестве альтернативы можно назвать перемещение некоторых операций из ЦПУ на ГПУ. Даже если такой подход кажется нелогичным или не обеспечивающим достаточное распараллеливание задачи, генерация данных на ГПУ будет выполняться быстрее, нежели передача данных.

Платформа CUDA представляет вполне определенную иерархию памяти, которая включает в себя различные типы памяти ГПУ, при этом время доступа к этим различным типам памяти разнится. Каждый поток имеет свою встроенную память, а каждый блок поток имеет разделяемую память, доступную всем потокам внутри блока. Также все потоки имеют доступ к одной и той же глобальной памяти. Все эти пространства для памяти подчинены следующим правилам: самой быстрой является встроенная память, а самой медленной глобальная; наименее вместительной, соответственно, будет встроенная, а наибольшим объёмом обладает глобальная память.

Очень важным аспектом является необходимость установки барьеров синхронизации. Его суть состоит в том, что он заставляет поток ждать, пока все потоки из блока достигнут барьер. Это гарантирует правильность выполнения алгоритма на ГПУ, но может ухудшить показатели производительности.

2. Выполнение алгоритма с использованием CUDA

Нашей целью является ускорение процесса выполнения алгоритма посредством запуска оптимизационного процесса на параллельных графических процессорах.

Объявление переменных и констант

Положим, что:

1) значения фитнесс функции, которую мы обозначим как f (X), лежат в области [-r; r];

2) размерности задачи D;

3) размер популяции N.

Тогда объявим переменные:

· X: массив состояний рыбки

· ХР: массив состояний добычи рыбок

· XS: массив состояний роя рыбок

· XF: массив перемещений рыбки

· DIST: массив расстояний, преодоленных рыбкой

· TESTF: массив фитнесс-функции рыбки.

Размер X, XP, XS и XF равны; размер DIST равен; размер TESTF равен Переменные X, XP, XS, XF можно представить в виде матрицы с N строками и D столбцами.

Важнейшим фактором, определяющим параллельную работу ядра, является объявление размера блока и размера сетки. Уместным будет считать их следующими:

· Block₁ = (BS, BS, 1)

· Grid₁ = (WIDTH/BS + 1, HEIGHT/BS + 1,1)

· Grid₂ =(N/BS + 1, N/BS + 1,1)

Здесь BS является шириной и длиной потокового блока, WIDTH и HEIGHT числом потоков Grid₁ в направлении x и направлении y соответственно. С глобальной точки зрения, алгоритму также понадобится переменная Y_min, которая будет использоваться для хранения оптимального значения фитнесс функции. Также введем переменную iterNum, служащую ограничением для максимального числа итераций запуска алгоритма на графических процессорах.

3. Генерация случайных чисел

Алгоритм требует большое количество случайных чисел во времяего выполнения. К сожалению, графический процессор не имеет генератора случайных чисел. В связи с тем, что передача данных от ЦПУ к ГПУ занимает довольно много времени, верным с практической точки зрения решением будет сгенерировать большое количество случайных чисел на ЦПУ и передать их в качестве массива на ГПУ. Решается эта задача следующим образом: M случайных чисел генерируются на ЦПУ до запуска алгоритма. Затем они один раз передаются на ГПУ, а для хранения этих данных используется массив RAND, находящийся в глобальной памяти. Когда функции ядра требуется случайное число, она может получить его из массива RAND, передав указатель в качестве параметра, где указатель [0; M-N] - случайное целое число, генерируемое на хосте.

4. Структура алгоритма на ГПУ

Структура алгоритма на ГПУ представлена алгоритмом 1. Подпроцессы в цикле for используются в качестве 7 функций ядра.

Алгоритм 1:

Инициализация случайных состояний рыб Инициализация массива случайных чисел Инициализация параметров алгоритма Передача данных от ЦПУ к ГПУ

Y_min

For iter to iterNum

Do Рассчитать значения фитнесс функций всех рыб: TESTF

Обновить результат оптимизации: Y_min

Рассчитать расстояние между рыбами: DIST

Выполнить процесс кормления Выполнить процесс индивидуального движения Выполнить процесс коллективного движения Обновить состояние каждой рыбы: Х Передать Y_min обратно в ЦПУ и вывести

A. Объявления ядер

Расчет значений фитнесс функций всех рыб

Мы устанавливаем значения размера сетки и размера блока равными grid₁ и block₁ соответственно. Это означает, что при запуске ядра будет выполнено N потоков и каждый из них рассчитывает фитнесс функцию для рыбы.

Приведем описание алгоритма:

1) Определяем, какое из значений фитнесс функции будем рассчитывать: i

2) Применяем арифметические операции к X[i] и храним посчитанные значения фитнесс функции в TESTF[i].

Обновление результатов оптимизации

Устанавливаем размер сетки и блока равным 1, это означает, что после запуска ядра будет выполняться только 1 поток. Это ядро сканирует массив TESTF[i] и записывает максимальную фитнесс функцию в Y_min

Расчет расстояния между рыбами

Размер сетки и размер блока принимаются grid₂ и block₁ соответственно. С запуском ядра параллельно будут выполняться потоков, каждый поток ссылается на уникальную пару рыбок и рассчитывает расстояние между ними. Для преодоления латентности доступа к глобальной памяти, мы привязываем X к текстуре для кэширования элементов X и получения их из текстуры в тот момент, когда нам это нужно.

Приведём алгоритм:

1) Определяем, для какой пары рыб необходимо найти расстояние: (i₁, i₂)

2) If i₁? N or i₂? N or i₂i₁ then return

Рассчитываем расстояние между двумя рыбами (i₁, i₂)

3) Сохраняем результат в массив DIST: DIST[i₁] [i₂] и DIST[i₂] [i₁] соответственно.

Процесс добычи

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

Приведём алгоритм процесса добычи:

1) Определяем, для какой рыбы будет осуществлён процесс добычи: i

2)

3) For to tryNum

Do PREY (pr_2t-1, pr_2t, XP, i)

If preySuccess=false

Then XP[i]X[i] + RAND [r+i]

Процесс инстинктивно-коллективного перемещения

Приведём описание для алгоритма для функции, осуществляющей коллективно-инстинктивное движение. X_c и n_f здесь вляются центром позиции спутников рыбы и числом спутников рыбы соответственно. X_c-X[i]

Алгоритм:

1) Определяем процесс добычи для исполнения: i

2)

3) If i? N

Then return

Рассчитываем. X_c и n_f

If удовлетворяет условиям инстинктивно-коллективного движения

Then

If

Then продолжать процесс добычи

Процесс инстинктивно-волевого перемещения

Приведем описание алгоритма для функции инстинктивно-волевого перемещения. Здесь X_min используется для записи состояния рыб с минимальной фитнесс функцией, а F_min — минимальная фитнесс функция компаньонов данной рыбы.

Алгоритм:

1) Определяем процесс добычи для выполнения

2)

3) If i? N

Then return

4) Находим компаньона рыбы с минимальной фитнесс функцией

5) Рассчитываем число компаньонов рыбы n_f

If n_f≠ 0 and F_min < TESTF[i] and n_f/N < д

Then

If then выполнить процесс добычи

Обновление состояний всех рыб

Устанавливаем размер сетки и размера блока равным grid₁ и block₁ соответственно. После запуска ядра будет выполнено N потоков, каждый из которых обновит состояние одной рыбы. Приведём алгоритм функции.

Алгоритм:

1) Определяем, позицию какой рыбы обновить: i

2) Вычисляем фитнесс-значение XP[i] и храним результат в разделяемой памяти pF[i]

3) Вычисляем фитнесс-значение XS[i] и храним результат в разделяемой памяти sF[i]

4) Вычисляем фитнесс-значение XF[i] и храним результат в разделяемой памяти fF[i]

5) Сохраняем лучшее состояние из трёх вышеперечисленных в переменную X[i]

5. Оценка производительности

Эксперименты для оценки производительности были запущены на системе со следующей конфигурацией: Intel® Core™ 2 Duo CPU E7500 2.93 Ггц, с 4.0 ГБ RAM. Графический процессор — NVIDIA GTX 260. Сравнение производительности основано на четырех стандартных тестовых функциях (см. таблицу 1)

Таблица 1. Тестовые функции

Время выполнения и ускорение в зависимости от размера популяции

Для измерения времени выполнения и ускорения в зависимости от размера популяции, установим D=50 для всех экспериментов, а количество итераций iterNum положим равным 100. Шаг и д положим 3.5 и 0.618 соответственно. Результаты представлены ниже, см. таблицы 2,3,4,5.

Таблица 2. Результаты выполнения алгоритма на функции сферы

Таблица 3. Результаты выполнения алгоритма на функции Растригина

Таблица 4. Результаты выполнения алгоритма на функции Гринвонка

Таблица 5. Результаты выполнения алгоритма на функции Розенброка

Время выполнения и ускорение в зависимости от размерности пространства

Проведем еще одну группу тестов, с фиксированным размером популяции (N=1000). Шаг и д положим 3.5 и 0.618 соответственно. Результаты приведены ниже, см. таблицы 6,7,8,9.

Таблица 6. Результаты выполнения алгоритма на функции сферы

Таблица 7. Результаты выполнения алгоритма на функции Растригина

Таблица 8. Результаты выполнения алгоритма на функции Гринвонка

Таблица 8. Результаты выполнения алгоритма на функции Розенброка

Анализ результатов

Из результатов экспериментов можно сделать следующие выводы:

· Алгоритм, выполненный с помощью ЦПУ, и алгоритм, выполненный с помощью ГПУ, дают примерно одинаковые результаты. Таким образом, наше реализация эффективна и надежна.

· Алгоритм на ГПУ выполняется гораздо быстрее, чем на ЦПУ. К примеру, в первом эксперименте лучшая производительность была отмечена при запуске алгоритма для функции сферы: ускорение дошло до отметки в 32 раза. Во втором эксперименте лучшая производительность была отмечена при запуске алгоритма для функции Растригина: ускорение достигло отметки в 18.4.

Важно будет отметить, что в нашей реализации показатели ускорения всегда будут выше для первого эксперимента, в силу того, что наше решение ориентировано на выполнение параллельно оптимизационного процесса для каждой рыбы. Таким образом, при увеличении количества измерений ГПУ требуется больше последовательных вычислений.

Заключение

В данной работе мы представили базовые блоки, необходимые для выполнения алгоритма поиска косяком рыб на ГПУ с использованием CUDA. Результаты показали, что такая реализация алгоритма гораздо более эффективна в план производительности, нежели оная на ЦПУ. Наш алгоритм очень эффективен в решении задач реального мира, в случае их большой размерности или наличия большой популяции.

1. Yifan Hu, Baozhong Yu, Jianliang Ma, Tianzhou Chen, Parallel Fish Swarm Algorithm Based on GPU-Acceleration // College of Computer Science and Technology, Zhejiang University, Hangzhou, P.R. China, Intelligent Systems and Applications (ISA), 2011

2. Anthony J.C.C. Lins, Carmelo J.A. Bastos-Filho, Debora N.O. Nascimento, Marcos A.C. Oliveira Junior and Fernando B. de Lima-Neto, Analysis of the Performance of the Fish School Search Algorithm Running in Graphic Processing Units // Polytechnic School of Pernambuco, University of Pernambuco, Brazil, Theory and New Applications of Swarm Intelligence, 2012, pp. 18−31.