В Грицик - Обробка даних в проблемно-орієнтованих системах - страница 1

Страницы:
1  2  3 

УДК 681.327

В. Грицик (1973 р.н)

Державний науково-дослідний інститут інформаційної інфраструктури (м. Львів)

ОБРОБКА ДАНИХ В ПРОБЛЕМНО-ОРІЄНТОВАНИХ СИСТЕМАХ ОРГАНІЗАЦІЇ АЛГОРИТМІВ РЕАЛЬНОГО ЧАСУ

© Грицик В., 2009

У роботі показано можливості синтезу складних систем паралельної обробки даних, які можна використати для реалізації у задачах комп'ютерного зору.

In the article are shown synthesis of complex systems of parallel data processing for computer vision tasks.

1. Вступ

Сьогодні досліджуються найрізноманітніші підходи розроблення проблемно-орієнтованих та спеціалізованих систем обробки даних складних алгоритмів з метою забезпечення реального часу. Однією із важливих задач є розв'язання та реалізація алгоритмів обробки зображень (попередня обробка зображень, розпізнавання та класифікація).

Актуальність полягає у з'ясуванні можливостей таких підходів, методів та алгоритмів, які би описували представлення в складних системах реального часу і здійснювати реалізацію в обчислювальних структурах [1, 5]. Особливо ця задача є важливою при розгляді та розв'язанні задач великої розмірності, високої роздільної здатності. Можна було би також відзначити актуальність проблеми різних класів задач комп'ютерного зору [6-8], забезпечити реальний час для заданих алгоритмів [1-4].

2. Постановка задачі

У цій роботі представлено задачу методу опису алгоритмів та можливості їх налаштування і реалізації у реальному часі в проблемно-орієнтованих системах або спеціалізованих обчис­лювальних пристроях чи елементах, великих інтегральних структурах, програмно-логічних інтегральних схемах.

3. Розпаралелювання в системах обробки даних в системах комп'ютерного зору

та ярусно-паралельні форми

Сьогодні, вважаючи, що проведені глибокі дослідження теоретичних розробок, необхідні відповідні підходи та опис налаштування у складних системах обробки даних. Можна відзначити нові дослідження обчислювальних біологічних систем у межах наноструктур. Тому таким важливим є підхід до налаштування обробки даних для високої кількості однорідних середовищ. У напрямку реалізації задач великої розмірності важливо провести дослідження з виявлення паралелізму алгоритму, а також розробити принципово нові підходи конструктивних алгоритмів паралельної структури для розв' язання задач великих розмірностей у системах комп' ютерного зору для різних задач предметних областей знань та практичного застосування. Незважаючи на значні досягнення, для розв' язання різних задач комп' ютерного зору необхідно розв' язувати практичні задачі обробки зображень у реальному часі [7, 8].

Важливим є надалі розвиток теоретичних досліджень розпаралелювання відносно струк­турних підходів, системних застосувань, методів [1, 4, 7, 8].

Довільну складну задачу можна розглядати для реалізації деякої системи, складеної із підсистем

S1 С Xi X Yu S2 С X2 X Y2 Sm С Xm X Ymе X = {х1,х2,...,xm } - множина вхідних даних, Y = y2,...,ym } - множина результатів при реалізації S1, S2,..., Sm .

Розглядаючи модель, яка відтворює послідовно-паралельну організацію обробки інформації -ярусно-паралельну форму (ЯПФ), побудуємо функціональну граф-схему обробки даних: 1)

поставимо у відповідність кожній підсистемі Si, i = 1, m деяку вершину графу; 2) вершина графу,

відповідно до функціональної підсистеми Sj, поєднується з вершиною графу відповідно до

функціональної підсистеми Sj, j = 1, m лише у тому випадку, якщо вихід (результат) yj є одним із входів (аргументів) підсистеми Sj. Побудована так граф-схема повністю відповідає внутрішній структурі задачі і визначає деяку систему S = {S1,S2,...,Sm } реалізації цієї задачі.

Означення 1. Функціональна підсистема вважається інформаційно залежною від Si, якщо Sj реалізує над виходом Si .

Означення   2.   Функціональна  підсистема   Si   є  керуючою   віднсно   підсистеми Sj

і SS (i, j, s = 1, m), якщо вихід Si визначає реалізацію Sj або Ss, а Si безпосередньо передує Sj і Ss.

При реалізації функціональної граф-схеми у ній виділяються ділянки, в яких немає керуючої підсистеми.

Так впорядковано функціональну граф-схему.

Означення 3. Множини функціональних підсистем WW першого ярусу назвемо множиною тих і тільки тих підсистем, які є інформативно незалежними; множина функціональних підсистем W2 другого ярусу є множиною тих і тільки тих підсистем, які інформативно залежні принаймні від однієї підсистеми першого ярусу і не є залежними від інших підсистем і т. ін. Множина функціональних підсистем Wi -го ярусу не є залежною від інших підсистем, що не належать ярусам з номерами меншими, ніж і.

Означення 4. Граф, упорядкований відповідно до функціональних підсистем за ярусами, визначеними множинами функціональних підсистем Wy,W2,W3,...,Wiназиватимемо ярусно-паралельним графом, а систему S відповідно до цього графу -ярусно-паралельною формою (ЯПФ).

Отже, розпаралелювання процесу розв'язання задачі передбачає такі етапи.

Перший етап паралельного розкладу - W1: з множин {S} с {(Xr, Yr)}, r = 1,l визначається максимальне число інформативно взаємонезалежних підсистемS^,S2,S3,...,. Число 61 визначає

максимальну кількість процесорів, необхідних для реалізації підсистем ,1 <р<81 на першому етапі паралельного розкладу W1. Останні 1- 81 підсистем є інформативно залежними від підсистем Sp . Другий етап розкладу - W2 : з множини {Sz /S1 } визначаємо максимальне число 82

2222

інформативно незалежних підсистем S1 , S2 , S3,..., Sd1,82 ^81. Число  8визначає максимальну

2

кількість елементів-процесорів, необхідних для реалізації підсистем Sp, 8<р<82 на другому етапі

2

паралельних розкладів W2 . Останні z- 81 - 82 підсистем є інформативно залежними від підсистем Sp

визначаємо     максимальне     число      8к      інформативно     взаємонезалежних підсистем

і можливо, від       і т. д. Кожний етап паралельного розкладу - Wk : з множини

к-1

S1 ,Sk ,S3 ,dk >d>k-i. Останні / -^&r підсистем є інформаційно залежними від підсистем

r=1

-1 і, можливо, від -2, -3 ,..., Sp1. Цей процес розпаралелювання продовжується доти, поки <Sr / •      >, де N - номер ярусу паралельного розкладу WN, що являє собою множину

N-1

інформативно   взаємонезалежних  підсистем.   При   цьому   5n = 1 - X 5r   визначає кількість

r=1

процесорів, необхідних на останньому етапі Wn і 5n -1. Максимальна кількість процесорів, необхідно для розв'язання відповідної задачі обробки інформації, 5max = max5k .

У загальному випадку задача розпаралелювання обробки даних в системах реального часу зводиться до побудови із функціонального графу підсистем Sr ярусно-паралельного графу. Основним недоліком цього підходу є відсутність правил формування підсистем. У роботі [ 1] запропонований підхід до розпаралелювання, де розглядається деяка глобальна характеристика внутрішньої синхронної функціональної схеми.

Розглянемо, що деяка задача реалізується за допомогою системи S с (X, C, Y), де С - канал, у якому здійснюється перетворення даних. Канал С задається у загальному випадку за допомогою матриці ймовірностей | |pj ||, де Ру - ймовірність, що характеризує перетворення вхідної множини Х

в Y. Підсистеми Sr с (Xr, Cr, Yr) можна інтерпретувати так: а) обчислювальний пристрій виконує елементарні мікрооперації; б) обчислювальний пристрій здійснює складні функціональні залежності       fn; обчислювальні середовища та ін. Якщо характеристики каналів C1kC^k у

системах одинакові, то системи Sk називаємо однорідними. Такі однорідні системи

становлять значний практичний інтерес для розв'язання задач обробки даних у реальному часі [5, 6]. Такі однорідні системи мають значні переваги порівняно з неоднорідними у вартості, технічній реалізації на основі ВІС, у компактності побудови, у забезпеченні високої надійності. Тому потрібно здійснювати такі алгоритми обробки даних, які дають можливість реалізовувати задачі на однорідні системи паралельної обробки даних.

4. Налаштування системи обробки даних. Синтез складних систем паралельної обробки даних

Розглянемо можливість розпаралелювання обробки інформації при синтезі складних систем обробки даних на рівні ярусно-паралельних структур алгоритму, застосування також магістральних методів реалізації процесу обробки даних. Такий підхід дає можливість налаштування системи на реалізацію задач у заданому режимі даних, які надходять. У цьому підході важливим є вибір основних операторів, що дають змогу налаштувати систему. Розглянемо систему

S с X х y , (1)

і нехай

X = x {Xv : j e Ixt }, Y = x [Yv : j є } Позначимо через      декартовий добуток компонентних множинX\, які можуть слугувати

для реалізації з'єднань систем; а через Zx{ - сімейство всіх компонентів множин Xt і позначимо через [4]

X* = { X у : X,j є Xr л X tj ї Zx, }, , де X - сімейство компонентних множин X ;

X* = х {Xl} : Хц є X , л XtJ і ZXi } = х { Хц  X tJ є X, }. Отже, отримаємо:

X, = X*  х (2)

Аналогічно

У = У*  х ZY. (3) Із ((1) : (3)) можна синтезувати множину синтезованих (з'єднаних) систем

S,z с (X*  х       ) х (У* Zyi ) (4)

Системи St і Stz - не одинакові системи; система S- визначає можливість з'єднання (синтезування) систем. Клас синтезованих систем із (4) визначимо так

Sz = {S,z : S,z с (х*  х ZXi) х (У*  х      )}.

У цьому класі систем знайдемо основні параметри синтезу систем.

I. Каскадний синтез (з'єднання)

Нехай Si с Хі х (у*  х Zx1 ), S2 с ( Хх Zy@) х Введемо операцію о: Sz х Sz => Sz таку, що S1 о S2 = S3, де

S3 с і х Х2) х (у*  х У2), Zx1 = Zy2 = Z

і ((Хі, Х2), і, У2) є S3 » ($z)((Хіі, Z)) є Si л ((Х2,Z), У2) є S2) Операцію о визначимо як каскадний синтез, або каскадну операцію.

II. Паралельний синтез (з'єднання)

Нехай S! с (X*  х ZX^) х Уі, S2 с ( X*  х ZX2) х У2.

Страницы:
1  2  3 


Похожие статьи

В Грицик - Обробка даних в проблемно-орієнтованих системах

В Грицик - Розпаралелювання в системах обробки даних задач комп'ютерного зору

В Грицик - Технологія нейрокомп' ютингу реального часу