Введення
Алгоритм пошуку косяком риб, розроблений в 2002 році, - стохастичний алгоритм оптимізації, заснований на поведінці косяка риб. З часом стало зрозуміло, що, із зростанням вимірювань і популяцій, час виконання неухильно зростає.
Сучасні графічні процесори перетворилися на сильно розпаралеленого, багатопотокових і багатоядерні процесори з неймовірною обчислювальною потужністю і пропускною спроможністю пам'яті. У зв'язку з цим, інженери та вчені зацікавилися тим, щоб використовувати графічні процесори для обчислень загального призначення. Для полегшення виконання даного завдання були розроблені деякі технології, такі як CUDA (Compute Unified Device Architecture), підтримувана NVIDIA.
У даній роботі представлений незвіданий раніше спосіб запуску алгоритму пошуку косяком риб на паралельних графічних процесорах і виконання його в CUDA.
програма графічний алгоритм
1. Введення в CUDA
Останнім часом можливістю для прискорення роботи додатків стали графічні процесори (ГПУ), які, в першу чергу, завдяки своєму паралельному обчислювальному механізму і швидким виконанням операцій з плаваючою точкою, були успішно використані в різних додатках для самих різних областей, починаючи фізикою і закінчуючи фінансами.
Незважаючи на зусилля по створенню інтерфейсу програмування додатків на ГПУ, програмування на CUDA так і залишалося досить трудомістким. Для подолання складнощів, пов'язаних з програмуванням на ГПУ, компанія NVIDIA представила паралельну обчислювальну платформу загального користування, що називається CUDA. CUDA дозволяє автоматично розподіляти і управляти потоками в ГПУ.
CUDA дозволяє програмам безпосередньо взаємодіяти з командами ГПУ, використовуючи при цьому мінімальний набір розширень. У CUDA є 3 головні абстракції: ієрархія груп потоків, Колективна пам'ять і бар'єри для синхронізації NVIDIA. Ці абстракції дозволяють розділити задачу на підзадачі, які, у свою чергу, можуть бути вирішені незалежно і паралельно. Кожна подзадача потім може бути розбита на операції, які вирішуються паралельно всіма потоками з блоку.
Головним вузьким місцем в архітектурі CUDA є передача даних між хостом (ЦПУ) і ГПУ. Будь-яка передача даних від ЦПУ до ГПУ знижує продуктивність, таким чином потрібно прагнути уникати даної операції. Зокрема, в якості альтернативи можна назвати переміщення деяких операцій з ЦПУ на ГПУ. Навіть якщо такий підхід здається нелогічним або що не забезпечує достатню розпаралелювання задачі, генерація даних на ГПУ буде виконуватися швидше, ніж передача даних.
Платформа CUDA представляє цілком певну ієрархію пам'яті, яка включає в себе різні типи пам'яті ГПУ, при цьому час доступу до цих різним типам пам'яті різниться. Кожен потік має свою вбудовану пам'ять, а кожен блок потік має поділювану пам'ять, доступну всім потокам всередині блоку. Також всі потоки мають доступ до однієї і тієї ж глобальної пам'яті. Всі ці простору для пам'яті підпорядковані наступним правилам: найшвидшою є вбудована пам'ять, а самій повільній глобальна; найменш місткою, відповідно, буде вбудована, а найбільшим об'ємом володіє глобальна пам'ять.
Дуже важливим аспектом є необхідність установки бар'єрів синхронізації. Його суть полягає в тому, що він змушує потік чекати, поки всі потоки з блоку досягнутий бар'єр. Це гарантує правильність виконання алгоритму на ГПУ, але може погіршити показники продуктивності.
2. Виконання алгоритму з використанням CUDA
Нашою метою є прискорення процесу виконання алгоритму за допомогою запуску оптимізаційного процесу на паралельних графічних процесорах.
Оголошення змінних і констант
Покладемо, що:
) значення фітнес функції, яку ми позначимо як f (X), лежать в області [-r; r];
) розмірності задачі D;
) розмір популяції N.
Тоді оголосимо змінні:
· X: масив станів рибки
· ХР: масив станів видобутку рибок
· XS: масив станів рою рибок
· XF: масив переміщень рибки
· DIST: масив відстаней, подоланих рибкою
· TESTF: масив фітнес-функції рибки.
Розмір X, XP, XS та XF рівні; розмір DIST дорівнює; розмір TESTF дорівнює Змінні X, XP, XS, XF можна представити у вигляді матриці з N рядками і D стовпцями.
Найважливішим чинником, визначальним паралельну роботу ядра, є оголошення розміру блоку і розміру сітки. Доречним...
