Пристрій для розподілу та кодування інформаційного ресурсу в мультисервісних мережах

Реферат: Пристрій для розподілу та кодування інформаційного ресурсу в мультисервісних мережах містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті. Введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. UA 91075 U (12) UA 91075 U UA 91075 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 %. В основу корисної моделі поставлена задача створити пристрій для розподілу та кодування інформаційного ресурсу в мультисервісних мережах, який забезпечить рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу, та зменшить відносну похибку алгоритму до 8 %. Поставлена задача вирішується за рахунок того, що у пристрій-прототип, який містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, замість блока сортування даних введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. Технічний результат, який може бути отриманий при здійсненні корисної моделі полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 8 %. На фіг. 1 представлена структурна схема запропонованого пристрою. На фіг. 2 представлено граф DA. Запропонований пристрій для розподілу та кодування інформаційного ресурсу в мультисервісних мережах містить блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження 1, блок управління систолічним процесором 2, обчислювальний пристрій 3, в якому кожен процесорний елемент 4 містить блок регістрів 5, арифметичний обчислювач 6, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації 7, обчислювальний пристрій формування вектора шляху 8 і модуль пам'яті 9. Робота запропонованого пристрою для розподілу та кодування інформаційного ресурсу в  мультисервісних мережах полягає у наступному (фіг. 1). Знаходиться вектор x , що доставляє максимум функції: n  f x    c j x j , (1) j 1 50 при виконанні умов: n a x j 1 ij j  b1 , (2) 1 UA 91075 U x j  0,1   j  1, n i 1 a 1j  0 (3) (4) cj  0 Для рішення задачі розподілу та кодування інформаційного ресурсу в мультисервісних мережах вводиться процедура А0, що дозволяє на основі правила відсікань L w 5  r r 1 sp    max    j, p  p  r  1, n j  r, n j  p (5) c j  r sj   вирішувати задачу (1-4) [3]. Блок сортування по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження (фіг. 1) здійснює сортування коефіцієнтів: c1 c 2 c   ...  n . (6) 1  2 n 10 Обчислювальний пристрій здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначення (обчислення) номеру вершини, у якої локальний екстремум визначений за правилом (5). З множин   mrsj виключаються як не перспективні шляхи mrsp , які задовольняють умові:   dc  rsp   p  max dc  * r , (7) sp 15 c j  де  p  c p 1  c p  2  ...  c n та для вершини j÷n вага γj - дорівнює нулю;   dc rsp - довжина шляху від вершини s до вершини р рангу r по вагах функціоналу. 20 25 30 35 40 45 Кожен процесорний елемент обчислювального пристрою виконує обчислення паралельно та здійснює обмін даними між сусідніми процесорними елементами після завершення обчислень. Кожний процесорний елемент містить блок регістрів, який зберігає і забезпечує мікрооперації передачі інформації між регістрами блока регістрів сусідніх процесорних комірок, арифметичний обчислювач, який обчислює локальні екстремуми на підставі даних, що надходять з блока регістрів, вибирає локальний екстремум за правилом (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. Пристрій для рішення задач на графах. /В.Ф. Третяк, О.В. Коломійцев та ін. - № u201113667; заяв. 21.11.2011; опубл. 25.04.2012; Бюл. № 8. - 4 с. 3. Пономаренко B.C., Голубничий Д.Ю., Третяк В.Ф. Цілочисельне програмування в економіці. - X: Вид. ХНУ, - 2005. - 204 с. ФОРМУЛА КОРИСНОЇ МОДЕЛІ Пристрій для розподілу та кодування інформаційного ресурсу в мультисервісних мережах, який містить блок сортування даних, блок управління систолічним процесором, обчислювальний 2 UA 91075 U 5 пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, який відрізняється тим, що введено блок сортування даних по убуванню значень відношень коефіцієнтів в фунціоналі до обмеження. 3 UA 91075 U Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4