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

Введение

 

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

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

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

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

 

Введение в CUDA

 

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

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

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

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

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

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

 

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

 

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

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

 

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

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

 

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

Алгоритм 1:

Инициализация случайных состояний рыб

Инициализация массива случайных чисел

Инициализация параметров алгоритма

Передача данных от ЦПУ к ГПУ

Y_min

For iter  to iterNum

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

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

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

Выполнить процесс кормления

Выполнить процесс индивидуального движения

Выполнить процесс коллективного движения

Обновить состояние каждой рыбы: Х

Передать Y_min обратно в ЦПУ и вывести

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

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

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

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

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

2) 

3) For  to tryNum

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

If preySuccess=false XP[i] X[i] + RAND [r+i]

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

 

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

 

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

Название функции	Уравнение функции	Область поиска
Сфера
Растригина
Гривонка
Розенброка

 

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

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

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

·   Алгоритм на ГПУ выполняется гораздо быстрее, чем на ЦПУ. К примеру, в первом эксперименте лучшая производительность была отмечена при запуске алгоритма для функции сферы: ускорение дошло до отметки в 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

.   Anthony J.C.C. Lins, Carmelo J.A. Bastos-Filho, Débora 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.

Введение

 

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

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

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

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

 

Введение в CUDA

 

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

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

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

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

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

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

 

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

 

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