Розробка та дослідження моделі розв’язання задач проектування з використанням методу гілок і границь та технології Cuda

Размещено на http://www.allbest.ru/

Розробка та дослідження моделі розв'язання задач проектування з використанням методу гілок і границь та технології CUDA

Однією з найскладніших задач проектування є структурний синтез. Цей процес передбачає створення множини альтернативних рішень (МАР). При проектуванні складних систем з'являється велика кількість варіантів її побудови, що може досягати тисяч і десятків тисяч елементів. Тому, логічним буде зменшення потужності МАР. Для розв'язання цієї задачі використовується метод гілок та границь (МГГ). В результаті буде одержано одне або ж декілька рішень задачі, при чому, кожне з рішень, відповідатиме вимогам завдання проектування.

При застосуванні МГГ для розв'язання задачі проектування, виникає велика кількість складних обчислювальних завдань. Для того, аби збільшити швидкість обчислень, можна використати паралельні обчислення за допомогою технології CUDA. [1, с. 266-271]

Головною метою МГГ є знаходження максимуму функції на допустимій множині. При чому, множина може бути як дискретною, так і раціональною. В ході роботи алгоритму виконується дві операції: розбиття вихідної множини на підмножини(гілки), та знаходження оцінок(границь). Існує оцінка множини згори та оцінка знизу. Оцінка згори - точка що гарантовано не менша за максимум на заданій підмножині. Оцінка знизу - точка що гарантовано не більша за максимум на заданій підмножині. Множина, що має найбільшу оцінку зверху зветься рекордною. На початку вся множина вважається рекордною. Алгоритм знаходження рішення задачі виглядає наступним чином:

1. Рекордна множина розбивається на підмножини;

2. Знайти оцінки згори та знизу для нових підмножин;

3. Визначити максимальну оцінку знизу серед усіх підмножин;

4. Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;

5. Знайти максимальну оцінку згори серед усіх підмножин та вважати її рекордною; проектування синтез процесорний гілка

6. Якщо не досягнуто дискретності, або необхідної точності перейти по пункту 1;

Результатом роботи є значення між оцінкою згори та знизу для рекордної множини. Точністю є різниця між верхньою та нижньою оцінками, тобто для дискретних множин алгоритм завершений тоді, коли ці оцінки співпадають. [2]

Для прискорення перебору МГГ, використовується відсів підмножин допустимих рішень, які свідомо не містять оптимальних рішень. Існує два підходи до розпаралелювання :

· Перший підхід - побудова конвеєра. Нехай алгоритм співвідношення Ek(x)=y можна представити у вигляді ланцюжка найпростіших дій (операцій): O1, O2, ..., ON. Візьмемо N процесорів A1, A2, …, AN. Задамо їх порядок і покладемо, що i-ий процесор виконує три однакові за часом операції:

1. прийом даних від (i-1)- го процесора;

2. виконання операції Oi;

3. передача даних наступному (i+1)-му процесору.

Тоді конвеєр з N послідовно з'єднаних, паралельно і синхронно працюючих процесорів працює зі швидкістю V/3, Де V- швидкість виконання однієї операції одним процесором.

· Другий підхід полягає в тому, що безліч K всіх можливих ключів розбивається на непересічні підмножини K1, K2, … , KN. Система з Q машин перебирає ключі так, що i-та машина здійснює перебір ключів з безлічі Ki, i=1..Q. Система припиняє роботу, якщо одна з машин знайшла ключ. Найважче - це поділ ключової безлічі. Але якщо кожен процесор почне обчислення з якогось довільного ключа, то час знаходження збільшиться, а схема значно спроститься. Середнє число кроків в цьому випадку становить

|K|/N,

Де |K|- Число елементів у множині ключів, а N- Число процесорів. [3]

Припустимо, що маємо функцію, яка паралельно додає два числа і записує результат у третю змінну.

Маючи два ядра отримуємо код на С++ (Рис 1):

Рис 1. Опис функції додавання двох чисел використовуючи два ядра CPU.

Змінна tid - це номер ядра, тобто перше ядро буде додавати першу і кожну непарну по порядку пари чисел а і b. Друге ядро почне рахувати з другої пари і кожну парну по порядку пари чисел.

Використання CPU (central processor unit) для задача паралельного обчислення потребує додаткового інфраструктурного коду для створення робочих циклів, що виконують обрахунки, а також для дійсно паралельного їх виконання. Тому дане припущення, що вони опрацьовуються одночасно, вірне не завжди.

Та ж функція для додавання чисел з використанням CUDA C матиме вигляд (Рис 2):

Рис 2. Опис функції додавання двох чисел використовуючи CUDA C.

При чому виклик функції у головній програмі матиме вигляд (Рис 3):

Рис 3. Виклик функції на CUDA C.

Числа, записані у трикутних дужках, говорять про те, як саме запускати ядро. Перший параметр задає кількість паралельних блоків, в яких виконує операції наше ядро. В даному випадку це число N. Проте, виникає питання: GPU (graphics processor unit) виконує N копій коду ядра, але як в середині коду визначити, в якому блоці він виконується? Повернувшись до прикладу (Рис 2), а саме - до зміної blockIdx.x.

На перший погляд здається, що компілятор має видати помилку про просвоєння змінній tid, ніде не оголошену змінну blockIdx.x. Оголошувати її не потрібно, адже вона є однією із вбудованих змінних середовища CUDA. Вона містить індекс того блоку пристрою, в якому виконується поточний код.

При запуску ядра ми задали N в якості кількості блоків. Таким чином ми говоримо середовищу, що хочемо мати одновимірну сітку з N блоків (Рис 4). Згадуючи приклад з CPU, нам доводилось обходити першу і всі непарні змінні, для того, щоб друге ядро рахувало всі парні. Проте, наше середовище запустило ядро в N блоках, і в кожному блоці виконується рівно одна операція додавання, то наша робота фактично виконана. В кожен блок буде передаватись лище одне значення чисел a і b, а сам процес обрахунку матиме приблизно такий вигляд:

Рис 4. Зображення блоків виконання додавання засобами CUDA C. [4, с 46-49]

Отже, використовуючи GPU не лише як графічний процесор, а й як процесор для обчислення, засобами технології CUDA, можна пришвидшити обчислення при розв'язанні складних задач проектування. А також використовувати цей метод в різноманітних галузях, оскільки, потрібно буде лише згенерувати МАР для поточної системи, яку ми проектуємо.

Метод гілок і границь є одним з най поширеніших методів дискретної оптимізації. Результатами досліджень буде внесок у подальший розвиток вирішення задач проектування, використовуючи незначні ресурсні затрати, невеликі затрати часу та знаходження найоптимальнішого результату, за рахунок використання нової технології паралельних обчислень на базі архітектури CUDA.

Література

1. Наконечний С.І., Савіна С.С. Н-22 Математичне програмування: Навч. посіб. -- К.: КНЕУ, 2003. -- 452 с. А.Е. Дорошенко Математические модели и методы организации высокопроизводительных параллельных вычислений. - Киев: "Наук. думка",2000.-177С.

2. А.Е. Дорошенко Математические модели и методы организации высокопроизводительных параллельных вычислений. - Киев: "Наук. думка", 2000. - 177С.

3. Dakin, R.J. (1965). A tree-search algorithm for mixed integer programming problems. In: The Computer Journal.

4. Технология CUDA в примерах Джейсон Сандерс, Эдвард Кэндрот "Технология CUDA в примерах. Введение в программирование графических процессоров" ДМК Пресс, 2011 г.

Размещено на Allbest.ru