Пристрій для рішення задачі планування паралельного розподілу задач в grid-системах

Реферат: Пристрій для рішення задачі планування паралельного розподілу задач в GRID-системах містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті. Введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MIN і блок ідентифікації. UA 91200 U (12) UA 91200 U UA 91200 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відома "Архітектура паралельної обчислювальної структури (ПОС) систолічного типу" [1], яка містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у склад якого входять процесорні елементи (ПЕ1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації (БІ), обчислювальний пристрій 2 (ОП2) та модуль пам'яті (МП). Недоліком відомого пристрою є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними, за яким функціонує обчислювальний пристрій 1 складає 20 %. Найбільш близьким до запропонованої корисної моделі є "Пристрій для рішення задач на графах" [2], який містить блок сортування даних (БСД), блок управління систолічним процесором, обчислювальний пристрій 1, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач 1 (АО 1), який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті. Недоліком найближчого аналога є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити пристрій для рішення задачі планування паралельного розподілу задач в GRID- системах, та зменшити відносну похибку алгоритму цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 4 %. Поставлена задача вирішується тим, що пристрій для рішення задачі планування паралельного розподілу задач в GRID- системах, що містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті, згідно з корисною моделлю, введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації. У найближчому аналогу, який містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, замість блока сортування даних введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження та в обчислювальний пристрій в кожному процесорному елементі замість арифметичного обчислювача, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком). Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 4 %. На фіг. 1 представлена структурна схема запропонованого пристрою. На фіг. 2 представлено граф DΔ. Запропонований пристрій для рішення задачі планування паралельного розподілу задач в GRID- системах містить блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження 1, блок управління систолічним процесором 2, обчислювальний пристрій 3, в якому кожен процесорний елемент 4 містить блок регістрів 5, арифметичний обчислювач 6, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації 7, обчислювальний пристрій формування вектора шляху 8 і модуль пам'яті 9. Робота запропонованого пристрою для рішення задачі планування паралельного розподілу задач в GRID- системах полягає у наступному (фіг. 1). Знаходиться вектор x , що доставляє максимум функції: 60 1 UA 91200 U  fx  n  c j x j j, (1) j 1 при виконанні умов: n  a ij x j  b1 , (2) j 1   , x j  0,1 , i  1 , j  1 n , (3) 5 a1j  0 , (4). cj  0. Для рішення задачі (1-4) вводиться процедура А0, що дозволяє на основі правила відсікань L w     r  r  1  min  r   j, p  , sp   sj (5) p  r  1 nj  r, nj  p , , (6) j 10 вирішувати задачу (1-4) [3]. Блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження (фіг. 1) здійснює сортування коефіцієнтів при функціоналі та обмеженні: 15 c1 c 2 c   ...  n . 1  2 n (7) Обчислювальний пристрій здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначення (обчислення) номера вершини, у якої локальний екстремум визначений за правилом (5). 20 З множин mr виключаються, як не перспективні, шляхи mr , які задовольняють умові: sp sj      d c  r   p  max d c  *r , sp sp c  (8) j   25 30 35 де  p  c p1  c p2  ...  c n та для вершини j÷n вага  j - дорівнює нулю; dc  r - довжина sp шляху від вершини s до вершини р рангу r по вагам функціоналу. Кожен процесорний елемент обчислювального пристрою виконує обчислення паралельно та здійснює обмін даними між сусідніми процесорними елементами після завершення обчислень. Блок регістрів кожного процесорного елемента зберігає і забезпечує мікрооперації передачі даних між регістрами блока регістрів сусідніх процесорних елементів. Арифметичний обчислювач обчислює локальні екстремуми на підставі даних, що надходять з блока регістрів, вибирає локальний екстремум за правилом (5) і пересилає його в обчислювальний пристрій формування вектора шляху для обчислення глобального екстремуму та формування вектора шляху. Блок ідентифікації визначає номер вершини (фіг. 2), у якій визначений локальний екстремум. Модуль пам'яті зберігає номери вершин локальних екстремумів на кожному рангу обчислень. Дані D1, ,D2,…Dn надходять одночасно в кожну систолічну комірку, в яких здійснюється обчислення. Введення даних здійснюється під керуванням блока управління систолічним процесом із блока сортування по убуванню значень коефіцієнтів в обмеженні. Пам'ять блока управління систолічним процесором використовується як буфер між високошвидкісною 2 UA 91200 U 5 10 спеціалізованою шиною і низькошвидкісною шиною електронної обчислювальної машини. За необхідністю дані в блоці управління систолічним процесором оновлюються, зчитуються й опрацьовуються систолічною матрицею. Джерела інформації: 1. Listrovoy S.V., Tretiyk V.F., Listrovay. A.S. Parallel algorithms of calculation process optimization for the boolean programming problems. //Engineering Simulation. - 1999. - Vol. 16. - P. 569-579. 2. Патент на корисну модель № 69487, Україна, МПК G06F 15/419. Пристрій для рішення задач на графах. /В.Ф. Третяк, О.В. Коломійцев та ін. - № u201113667; заяв. 21.11.2011; опубл. 25.04.2012; Бюл. № 8. - 4 с. 3. Пономаренко B.C., Голубничий Д.Ю., Третяк В.Ф. Цілочисельне програмування в економіці. - X.: Вид. ХНУ, 2005. - 204 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 Пристрій для рішення задачі планування паралельного розподілу задач в GRID-системах, що містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті, який відрізняється тим, що введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації. 3 UA 91200 U Комп’ютерна верстка М. Ломалова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4