Пристрій для визначення маршруту в графі

Реферат: Пристрій для визначення маршруту в графі містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті. Крім цього введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MAX-MIN (вибір максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком), і блок ідентифікації. UA 91199 U (12) UA 91199 U UA 91199 U 5 10 15 20 25 30 35 40 45 50 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відома "Архітектура паралельної обчислювальної структури (ПОС) систолічного типу" [1], яка містить блок управління систолічним процесором (БУСП), обчислювальний пристрій (ОП 1), у склад якого входять процесорні елементи (ПЕ1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації (БІ), обчислювальний пристрій (ОП 2) та модуль пам'яті (МП). Недоліком відомого пристрою є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними, за яким функціонує обчислювальний пристрій, складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибраним як найближчий аналог, є "Пристрій для рішення задач на графах" [2], який містить блок сортування даних (БСД), блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач (АО 1), який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком), і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті. Недоліком найближчого аналога є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити пристрій для визначення маршруту в графі, який дозволить зменшити відносну похибку алгоритму до 5 %. Поставлена задача вирішується за рахунок того, що у пристрій, який містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком), і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, замість блока сортування даних введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні, та в обчислювальний пристрій в кожному процесорному елементі замість арифметичного обчислювача, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком), введено арифметичний обчислювач, який працює за алгоритмом MAX-MIN (вибір максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком). Технічний результат, який може бути отриманий при здійсненні корисної моделі, полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 5 %. На фіг. 1 представлена структурна схема запропонованого пристрою. На фіг. 2 представлено граф DΔ. Запропонований пристрій для визначення маршруту в графі містить блок сортування даних по зростанню значень коефіцієнтів в обмеженні 1, блок управління систолічним процесором 2, обчислювальний пристрій 3, в якому кожен процесорний елемент 4 містить блок регістрів 5, арифметичний обчислювач 6, який працює за алгоритмом MAX-MIN (вибір максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації 7, обчислювальний пристрій формування вектора шляху 8 і модуль пам'яті 9. Робота запропонованого пристрою для визначення маршруту в графі полягає у наступному (фіг. 1).  Знаходиться вектор x , що доставляє максимум функції:  f x   n  c jx j , (1) j 1 при виконанні умов: n  a ij x j  b1 , (2) j 1 1 UA 91199 U   x j  0,1, i  1, j  1, n , (3) a1j  0, (4) c j  0. Для рішення задачі (1-4) вводиться процедура A 0 , що дозволяє на основі правила відсікань L w  5      r  r 1  max  r  j, p ; sj  sp cj L 3 :  r  r 1  min  r  j, p .   sp sj j  p  r  1 nj  r, nj  p , , 10 (5) (6) вирішувати задачу (1-4). [3] Блок сортування даних по зростанню значень коефіцієнтів в обмеженні (фіг. 1) здійснює сортування коефіцієнтів при функціоналі та обмеженні: 1   2   3     n . 15 (7) Обчислювальний пристрій здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначення (обчислення) номеру вершини, у якої локальний екстремум визначений за правилом (5). З множин mr виключаються, як не перспективні, шляхи r , які задовольняють умові: sp sj      d c  r   p  max d c  r , sp sp c  (8) j де  p  c p 1  c p  2    c n та для вершини j  n вага  j - дорівнює нулю; 20 25 30 35 40   dc r - довжина шляху від вершини s до вершини p рангу r по вагах функціоналу. sp Кожен процесорний елемент обчислювального пристрою виконує обчислення паралельно та здійснює обмін даними між сусідніми процесорними елементами після завершення обчислень. Блок регістрів кожного процесорного елементу зберігає і забезпечує мікрооперації передачі даних між регістрами блока регістрів сусідніх процесорних елементів. Арифметичний обчислювач обчислює локальні екстремуми на підставі даних, що надходять з блока регістрів, вибирає локальний екстремум за правилом (5) і пересилає його в обчислювальний пристрій формування вектора шляху для обчислення глобального екстремуму та формування вектора шляху. Блок ідентифікації визначає номер вершини (фіг. 2), у якій визначений локальний екстремум. Модуль пам'яті зберігає номери вершин локальних екстремумів на кожному рангу обчислень. Дані D1,D2 ,Dn надходять одночасно в кожну систолічну комірку, в яких здійснюється обчислення. Введення даних здійснюється під керуванням блока управління систолічним процесом із блока сортування даних по зростанню значень коефіцієнтів в обмеженні. Пам'ять блока управління систолічним процесором використовується як буфер між високошвидкісною спеціалізованою шиною і низькошвидкісною шиною електронної обчислювальної машини. За необхідністю дані в блоці управління систолічним процесором оновлюються, зчитуються й опрацьовуються систолічною матрицею. Джерела інформації: 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. - PP. 569-579. 2 UA 91199 U 5 2. Патент на корисну модель № 69487, Україна, МПК G06F 15/419. Пристрій для рішення задач на графах. / В.Ф. Третяк, О.В. Коломійцев та ін. - № u201113667; заяв. 21.11.2011; опубл. 25.04.2012; Бюл. № 8. - 4 с. 3. Пономаренко B.C., Голубничий Д.Ю., Третяк В.Ф. Цілочисельне програмування в економіці. - X: Вид. ХНУ, - 2005. - 204 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 10 15 Пристрій для визначення маршруту в графі, який містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті, який відрізняється тим, що введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MAX-MIN (вибір максимального значення довжини шляху в графі за вагою функціоналу та мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком), і блок ідентифікації. 3 UA 91199 U Комп’ютерна верстка М. Ломалова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4