Пристрій для обробки та захисту інформації в розподілених сховищах даних

Реферат: Пристрій для обробки та захисту інформації в розподілених сховищах даних містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху, модуль пам'яті, додатково містить блок сортування даних по зростанню значень коефіцієнтів в обмеженні, в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації. UA 90214 U (12) UA 90214 U UA 90214 U 5 10 15 20 25 30 35 40 45 50 Запропонована корисна модель належить до галузі кібернетики і обчислювальної техніки та може бути використана при вирішенні задач комбінаторної оптимізації на графах. Відома "Архітектура паралельної обчислювальної структури (ПОС) систолічного типу" [1], яка містить блок управління систолічним процесором (БУСП), обчислювальний пристрій 1 (ОП1), у склад якого входять процесорні елементи (ПЕ1 … ПЕn), кожен з яких містить блок регістрів (БР), арифметичний обчислювач (АО) та блок ідентифікації (БІ), обчислювальний пристрій 2 (ОП2) та модуль пам'яті (МП). Недоліком відомого пристрою є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними, за яким функціонує обчислювальний пристрій 1 складає 20 %. Найближчим аналогом є "Пристрій для рішення задач на графах" [2], який містить блок сортування даних (БСД), блок управління систолічним процесором, обчислювальний пристрій 1, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач 1 (АО 1), який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті. Недоліком найближчого аналогу є те, що відносна похибка наближеного алгоритму для рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу складає 12 %. В основу корисної моделі поставлено задачу створити пристрій для обробки та захисту інформації в розподілених сховищах даних, який дозволить зменшити відносну похибку алгоритму цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 5 %. Поставлена задача вирішується за рахунок корисної моделі, яка містить блок сортування даних, блок управління систолічним процесором, обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, арифметичний обчислювач, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) і блок ідентифікації, обчислювальний пристрій формування вектора шляху і модуль пам'яті, замість блока сортування даних введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні та в обчислювальний пристрій в кожному процесорному елементі замість арифметичного обчислювача, який працює за алгоритмом МАХ (вибір максимального значення довжини шляху в графі за вагою функціоналу на основі принципу оптимізації за напрямком) введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком). Технічний результат, який може бути отриманий при здійсненні корисної моделі, полягає у зменшенні відносної похибки алгоритму рішення задачі цілочисельного лінійного програмування з булевими змінними на основі рангового підходу до 5 %. На фіг. 1 представлена структурна схема запропонованого пристрою. На фіг. 2 представлено граф DΔ. Запропонований пристрій для обробки та захисту інформації в розподілених сховищах даних містить блок сортування даних по зростанню значень коефіцієнтів в обмеженні 1, блок управління систолічним процесором 2, обчислювальний пристрій 3, в якому кожен процесорний елемент 4 містить блок регістрів 5, арифметичний обчислювач 6, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації 7, обчислювальний пристрій формування вектора шляху 8 і модуль пам'яті 9. Робота запропонованого пристрою для визначення маршруту в графі полягає у наступному (фіг. 1). Знаходиться вектор х, що доставляє максимум функції:  fx  n  c jx j (1) j 1 при виконанніумов:  fx  n  c jx j (1) j 1 1 UA 90214 U n  aij x j  b1 (2) j1 x j   ,1 0   , i  1, j  1,n (3) a1j  0 cj  0 (4) . Для рішення задачі (1-4) вводиться процедура А0, що дозволяє на основі правила відсікань L w     r r 1  min  r   j,p  sp sj   (5) j p  r  1,nj  r,nj  p (6) 5 вирішувати задачу (1-4). [3] Блок сортування даних по зростанню значень коефіцієнтів в обмеженні (фіг. 1) здійснює сортування коефіцієнтів при функціоналі та обмеженні: 1  2  3  ...  n (7) 10 Обчислювальний пристрій здійснює обчислення локальних екстремумів при заданому функціоналі та обмеженні, а також визначення (обчислення) номеру вершини, у якої локальний екстремум визначений за правилом (5). З множин mr виключаються як не перспективні шляхи mr , які задовольняють умові: sj sp 15      dc r   p  max dc  *r sp sp c  (8) j де  p  c p 1  c p  2  ...  c n та для вершини j÷n вага  j - дорівнює нулю; ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 Пристрій для обробки та захисту інформації в розподілених сховищах даних, який містить блок управління систолічним процесором, обчислювальний пристрій формування вектора шляху та модуль пам'яті, який відрізняється тим, що введено блок сортування даних по зростанню значень коефіцієнтів в обмеженні та в обчислювальний пристрій, в якому кожен процесорний елемент містить блок регістрів, введено арифметичний обчислювач, який працює за алгоритмом MIN (вибір мінімального значення довжини шляху в графі за вагою обмеження на основі принципу оптимізації за напрямком) і блок ідентифікації.   dc r - довжина шляху від вершини s до вершини р рангу r по вагах функціоналу. sp Кожен процесорний елемент обчислювального пристрою виконує обчислення паралельно та здійснює обмін даними між сусідніми процесорними елементами після завершення обчислень. Блок регістрів кожного процесорного елемента зберігає і забезпечує мікрооперації передачі даних між регістрами блока регістрів сусідніх процесорних елементів. Арифметичний обчислювач обчислює локальні екстремуми на підставі даних, що надходять з блока регістрів, вибирає локальний екстремум за правилом (5) і пересилає його в обчислювальний пристрій формування вектора шляху для обчислення глобального екстремуму та формування вектора шляху. Блок ідентифікації визначає номер вершини (фіг. 2), у якій визначений локальний екстремум. Модуль пам'яті зберігає номери вершин локальних екстремумів на кожному рангу обчислень. Дані D1, D2,…Dn надходять одночасно в кожну систолічну комірку, в яких здійснюється обчислення. Введення даних здійснюється під керуванням блока управління систолічним процесом із блока сортування даних по зростанню значень коефіцієнтів в обмеженні. Пам'ять 2 UA 90214 U блока управління систолічним процесором використовується як буфер між високошвидкісною спеціалізованою шиною і низькошвидкісною шиною електронної обчислювальної машини. За необхідністю дані в блоці управління систолічним процесором оновлюються, зчитуються й опрацьовуються систолічною матрицею. Джерела інформації: 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 с. 3 UA 90214 U Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4