Пристрій для рішення задач на графах
Номер патенту: 89600
Опубліковано: 25.04.2014
Автори: Малюга Володимир Геннадійович, Тюрін Віталій Вікторович, Третяк В'ячеслав Федорович, Місюра Олег Миколайович, Щепанський Павло Володимирович, Хмелевський Сергій Іванович, Опенько Павло Вікторович, Дранник Павло Анатолійович, Звєрєв Олексій Олексійович, Гогонянц Спартак Юрійович
Формула / Реферат
Пристрій для рішення задач на графах, який містить блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, який відрізняється тим, що введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні.
Текст
Реферат: Пристрій для рішення задач на графах, який містить блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті. Введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні. UA 89600 U (12) UA 89600 U UA 89600 U 5 10 15 20 25 30 35 40 45 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відома "Архітектура паралельної обчислювальної структури (ПОС) систолічного типу" [1], яка містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у склад якого входять процесорні елементи (ПЕ1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації (БІ), обчислювальний пристрій 2 (ОП2) та модуль пам'яті (МП). Недоліком відомого пристрою є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними, за яким функціонує обчислювальний пристрій 1 складає 20 %. Найбільш близьким до запропонованого технічного рішення, вибраним як прототип, є "Пристрій для рішення задач на графах" [2], який містить блок сортування даних (БСД), блок управління систолічним процесором, обчислювальний пристрій 1, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач 1 (АО 1), який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій 2 і модуль пам'яті. Недоліком пристрою-прототипу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлена задача створити пристрій для рішення задач на графах, який забезпечить рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу, який дозволить зменшити відносну похибку алгоритму до 10 %. Поставлена задача вирішується за рахунок того, що у пристрій-прототип, який містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, замість блока сортування даних введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 10 %. На фіг. 1 представлена структурна схема запропонованого пристрою. На фіг. 2 представлено граф DΔ. Запропонований пристрій для рішення задач на графах містить блок сортування даних по зростанню значень коефіцієнтів в обмеженні 1, блок управління систолічним процесором 2, обчислювальний пристрій 3, в якому кожен процесорний елемент 4 містить блок регістрів 5, арифметичний обчислювач 6, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації 7, обчислювальний пристрій формування вектора шляху 8 та модуль пам'яті 9. Робота запропонованого пристрою для рішення задач на графах полягає у наступному (фіг. 1). Знаходиться вектор x , що доставляє максимум функції: n f x c j x j , (1) j 1 при виконанні умов: n a x j1 ij j b1 , (2) x j 0,1 , i 1, 50 a1 j 0 , c j 0. j 1 n , (3) , (4) Для рішення задачі (1-4) вводиться процедура А0, що дозволяє на основі правила відсікань {Lw} 1 UA 89600 U rspr 1 max rsj j,p p r 1,n j r , n j p , (5) 5 c j вирішувати задачу (1-4). [3] Блок сортування даних по зростанню значень коефіцієнтів в обмеженні (фіг. 1) здійснює сортування коефіцієнтів при обмеженні: 1 2 3 ... n . (6) Обчислювальний пристрій здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначення (обчислення) номеру вершини, у якої локальний екстремум (ЛЕ) визначений за правилом (5). З множин 10 mrsj виключаються як не перспективні шляхи rsp , які задовольняють умові: dC rsp p max dC r , (7) sp c j де γp=cp+1+cp+2 + … + cn та для вершини jn вага γj - дорівнює нулю; dC rsp - довжина шляху від вершини s до вершини p рангу r по вагах функціоналу. 15 20 25 30 35 Кожен процесорний елемент обчислювального пристрою виконує обчислення паралельно та здійснює обмін даними між сусідніми процесорними елементами після завершення обчислень. Блок регістрів кожного процесорного елементу зберігає і забезпечує мікрооперації передачі даних між регістрами блока регістрів сусідніх процесорних елементів. Арифметичний обчислювач обчислює локальні екстремуми на підставі даних, що надходять з блока регістрів, вибирає локальний екстремум за правилом (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. Патент на корисну модель №69487, Україна, МПК G 06 F15/419. Пристрій для рішення задач на графах. /В.Ф. Третяк, О.В. Коломійцев та ін. - № и201113667; заяв. 21.11.2011; опубл. 25.04.2012; Бюл. №8.- 4 с. 3. Пономаренко B.C., Голубничий Д.Ю., Третяк В.Ф. Цілочисельне програмування в економіці. - X: Вид. ХНУ, - 2005. - 204 с. 40 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 45 Пристрій для рішення задач на графах, який містить блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, який відрізняється тим, що введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні. 2 UA 89600 U 3 UA 89600 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4
ДивитисяДодаткова інформація
Автори англійськоюTretiak Viacheslav Fedorovych, Hohoniants Spartak Yuriiovych, Maliuga Volodymyr Genadiiovych, Misiura Oleh Mykolaiovych, Openko Pavlo Viktorovych, Tiurin Vitalii Ivanovich, Khmelevskyi Serhii Ivanovych
Автори російськоюТретяк Вячеслав Федорович, Гогонянц Спартак Юрьевич, Малюга Владимир Геннадиевич, Мисюра Олег Николаевич, Опенько Павел Викторович, Тюрин Виталий Иванович, Хмелевский Сергей Иванович
МПК / Мітки
МПК: G06F 15/00
Мітки: пристрій, графах, задач, рішення
Код посилання
<a href="https://ua.patents.su/6-89600-pristrijj-dlya-rishennya-zadach-na-grafakh.html" target="_blank" rel="follow" title="База патентів України">Пристрій для рішення задач на графах</a>
Попередній патент: Пристрій для оптимізації паралельної обробки великих масивів даних в кластерних системах
Наступний патент: Пристрій для визначення знаку похідної пневматичного сигналу
Випадковий патент: Спосіб консервування ооцист еймерій і яєць гельмінтів