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

Реферат: Пристрій для рішення задач на графах містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у склад якого входять процесорні елементи (ПЕ 1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації, а також обчислювальний пристрій 2, модуль пам'яті. Перед БУСП введено блок сортування даних, та в ОП1 в кожному ПЕ після БР замість АО введено АО1. UA 69487 U (12) UA 69487 U UA 69487 U 5 10 15 20 25 30 35 40 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відоме "Устройство для решения задач на графах" [1], яке містить багатоканальний блок реєстрації, багатоканальний блок накопичення формування шляху, багатоканальний блок вибору мінімуму, блок синхронізації, вхід пуску, входи визначення ваги ребер графа, виходи складу найкоротшого шляху в k-ту вершину графа. Недоліком відомого пристрою є високі апаратурні витрати по рішенню задачі, по визначенню найкоротшого шляху із початкової вершини у всі інші вершини графа. Найбільш близьким до запропонованого технічним рішенням, вибраним як найближчий аналог є "Паралельна обчислювальна структура систолічного типу" [2], яка містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у складі якого входять процесорні елементи (ПЕ1… ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації (БІ), а також обчислювальний пристрій 2 (ОП2) і модуль пам'яті (МП). Недоліком пристрою-найближчого аналога є високий відсоток погрішності відносної похибки наближених алгоритмів для рішення задачі цілочисельного лінійного програмування з булевими змінними. В основу корисної моделі поставлена задача створити пристрій для рішення задач на графах, який забезпечить рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу та зменшить відносну похибку і часову складність алгоритму. Поставлена задача вирішується за рахунок того, що у пристрій-найближчий аналог, що містить блок управління систолічним процесором, обчислювальний пристрій 1, у склад якого входять процесорні елементи (ПЕ1 … ПЕn), кожен з яких містить блок регістрів, арифметичний обчислювач та блок ідентифікації, а також обчислювальний пристрій 2 і модуль пам'яті, згідно з корисною моделлю, додатково перед БУСП введено блок сортування даних, а в ОП1 в кожному ПЕ після БР замість АО введено АО1, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком). [3]. Технічний результат, який може бути отриманий при здійсненні корисної моделі, полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними до 12 %, та часової складності. На фіг. 1 представлено структурну схему запропонованого пристрою. На фіг. 2 представлено граф D∆. Запропонований пристрій для рішення задач на графах містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій 1, у склад якого входять процесорні елементи (ПЕ1… ПЕn), кожен з яких містить блок регістрів, арифметичний обчислювач 1, який працює за алгоритмом МАХ та блок ідентифікації, а також обчислювальний пристрій 2 і модуль пам'яті. Робота запропонованого пристрою полягає в наступному (фіг. 1). Знаходиться вектор х, за допомогою якого забезпечується максимум функції  f ( x)  n  c jx j , j 1 (1) за умовами 45 n  aijx j  bi , (2) x j  {0,1}, i  1 j  (1 n) . ; , (3) j 1 Блок сортування даних здійснює сортування коефіцієнтів за функціоналом (фіг. 1): c1  c 2  c 3  ...  c n . (4) 50 1 UA 69487 U Обчислювальний пристрій 1 - здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначає номер вершини, у якій локальний екстремум (ЛЕ) визначений за правилом [3] r r 1  max{r  ( j, p)} , sp sj {c j } (5) 5 де, p  r  1 n, j  r,n, j  p. , З множин m r відкидаються, як неперспективні шляхи mr , за умови [3] sj sp dc (r )   p  max{dc (r ) . sp sp {c j } 10 15 20 25 30 35 40 (6) Запропонований пристрій складено з n-1-процесорних елементів систолічних комірок, реалізованих на основі простої структури та характеризується однорідністю і локальністю зв'язків. Кожна процесорна комірка має зв'язок тільки із сусідньою. Систолічні комірки працюють паралельно, після виконання обчислень відбувається обмін даними між сусідніми процесорними комірками. На першому кроці (такті) отримується у ПЕ1 ЛЕ1, на другому - у ПЕ2 ЛЕ2 тощо. Для обчислення глобального екстремуму затрачується N*(N-1)/2 тактів, що на порядок нижче при обчисленні в однопроцесорному режимі. Кожна процесорна комірка здійснює наступне: - у блоці регістрів - зберігається та забезпечується передача інформації між регістрами БР сусідніх процесорних комірок; - у арифметичному обчислювачі 1 - обчислюється ЛЕ на підставі даних, що надходять із БР, здійснюється вибірка ЛЕ за правилом (5) і передача його в блок визначення глобального екстремуму ОП2 для визначення глобального екстремуму; - у блоці ідентифікації - визначаються номери вершини, у якій ЛЕ визначений. Обчислювальний пристрій 2 визначає з ЛЕ, що надходять, глобальний екстремум і формує вектор шляху. В склад ОП2 входять два блоки: - блок визначення глобального екстремуму (БВГЕ), який визначає глобальний екстремум та складається зі схеми порівняння, регістрів локального і глобального екстремумів; - блок визначення вектора шляху, який обчислює номер останньої вершини, яка визначає вектор шляху та складається з трьох суматорів, чотирьох лічильників, двох тригерів, регістрів адреси і проміжних обчислювачів. Модуль пам'яті зберігає номери вершин локальних екстремумів на кожному ранзі обчислень та складається з дешифратора адреси і пам'яті. Ввід даних із блока сортування даних здійснюється під керуванням блока управління систолічним процесом. Для виконання обчислень дані надходять одночасно в кожний ПЕ. Джерела інформації: 1. Авторское свидетельство СССР № 1765832, G06F15/419. Устройство для решения задач на графах. /С.А. Ильин, С.В. Листровой, В.Н. Мариян и др. - № 4729168/24; заяв. 09.08.1989; опубл. 30.09.1992; Бюл. № 36 - 6 с. 2. 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. 3. Пономаренко B.C., Голубничий Д.Ю., Третяк В.Ф. Цілочисельне програмування в економіці. X: Вид. ХНУ, 2005. - 204 с 45 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 50 Пристрій для рішення задач на графах, що містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у склад якого входять процесорні елементи (ПЕ 1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації, а також обчислювальний пристрій 2, модуль пам'яті, який відрізняється тим, що перед БУСП введено блок сортування даних, та в ОП1 в кожному ПЕ після БР замість АО введено АО1, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі оптимізації за напрямком). 2 UA 69487 U 3 UA 69487 U Комп’ютерна верстка Л. Ціхановська Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4