буде вважати їх наступними:
· Block 1=(BS, BS, 1)
· Grid 1=(WIDTH/BS + 1, HEIGHT/BS + 1,1)
· Grid 2=(N/BS + 1, N/BS + 1,1)
Тут BS є шириною і довжиною потокового блоку, WIDTH і HEIGHT числом потоків Grid 1 в напрямку x і напрямку y відповідно. З глобальної точки зору, алгоритмом також знадобиться змінна Y min, яка буде використовуватися для зберігання оптимального значення фітнес функції. Також введемо змінну iterNum, що служить обмеженням для максимального числа ітерацій запуску алгоритму на графічних процесорах.
. Генерація випадкових чисел
Алгоритм вимагає велику кількість випадкових чисел під часЛ виконання. На жаль, графічний процесор не має генератора випадкових чисел. У зв'язку з тим, що передача даних від ЦПУ до ГПУ займає досить багато часу, вірним з практичної точки зору рішенням буде згенерувати велику кількість випадкових чисел на ЦПУ і передати їх в якості масиву на ГПУ. Вирішується це завдання наступним чином: M випадкових чисел генеруються на ЦПУ до запуску алгоритму. Потім вони один раз передаються на ГПУ, а для зберігання цих даних використовується масив RAND, що знаходиться в глобальній пам'яті. Коли функції ядра потрібно випадкове число, вона може отримати його з масиву RAND, передавши покажчик як параметр, де покажчик [0; M - N] - випадкове ціле число, що генерується на хості.
. Структура алгоритму на ГПУ
Структура алгоритму на ГПУ представлена ??алгоритмом 1. Підпроцеси в циклі for використовуються як 7 функцій ядра.
Алгоритм 1:
Ініціалізація випадкових станів риб
Ініціалізація масиву випадкових чисел
Ініціалізація параметрів алгоритму
Передача даних від ЦПУ до ГПУ
Y min
For iter to iterNum
Do Розрахувати значення фітнес функцій всіх риб: TESTF
Оновити результат оптимізації: Y min
Розрахувати відстань між рибами: DIST
Виконати процес годування
Виконати процес індивідуального руху
Виконати процес колективного руху
Оновити стан кожної риби: Х
Надіслати Y min назад в ЦПУ і вивести
A. Оголошення ядер
Розрахунок значень фітнес функцій всіх риб
Ми встановлюємо значення розміру сітки і розміру блоку рівними grid 1 і block 1 відповідно. Це означає, що при запуску ядра буде виконано N потоків і кожен з них розраховує фітнес функцію для риби.
Наведемо опис алгоритму:
) Визначаємо, який із значень фітнес функції будемо розраховувати: i
) Застосовуємо арифметичні операції до X [i] і зберігаємо полічені значення фітнес функції в TESTF [i].
Оновлення результатів оптимізації
Встановлюємо розмір сітки і блоку рівним 1, це означає, що після запуску ядра буде виконуватися тільки 1 потік. Це ядро ??сканує масив TESTF [i] і записує максимальну фітнес функцію в Y min
Розрахунок відстані між рибами
Розмір сітки і розмір блоку приймаються grid 2 і block 1 відповідно. Із запуском ядра паралельно будуть виконуватися потоків, кожен потік посилається на унікальну пару рибок і розраховує відстань між ними. Для подолання латентності доступу до глобальної пам'яті, ми прив'язуємо X до текстури для кешування елементів X і їх з текстури в той момент, коли нам це потрібно.
Наведемо алгоритм:
) Визначаємо, для якої пари риб необхідно знайти відстань: (i 1, i 2)
2) If i 1? N or i 2? N or i 2 i 1 then return
Розраховуємо відстань між двома рибами (i 1, i 2)
) Зберігаємо результат в масив DIST: DIST [i +1] [i 2] і DIST [i 2] [i +1] відповідно.
Процес видобутку
Для реалізації процесу видобутку, кожній рибі потрібно випадкових чисел і, у зв'язку з цим, потрібно підготувати таке ж число випадкових цілих чисел, які будуть служити покажчиками для масиву RAND, що зберігає велике число випадкових чисел в глобальній пам'яті ГПУ.
Наведемо алгоритм процесу видобутку:
) Визначаємо, для якої риби буде здійснено процес видобутку: i
2)