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

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