Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 681.325

МЕТОДИ ПРОЕКТУВАННЯ СПЕЦІАЛІЗОВАНИХ КОМП’ЮТЕРНИХ СИСТЕМ УПРАВЛІННЯ ТА ОБРОБКИ СИГНАЛІВ У РЕАЛЬНОМУ ЧАСІ

Цмоць І. Г., Демида Б.А., Подольський М.Р.

Вступ. Сучасний етап розвитку комп’ютерних систем управління та обробки сигналів характеризується розширенням галузей застосування, в значній частині з яких вимагається опрацювання за складними алгоритмами у реальному часі різних за інтенсивністю надходження потоків даних на комп’ютерних засобах, що задовольняють обмеженням щодо габаритів, енергоспоживання, вартості та часу розробки [1-3]. Режим реального часу накладає обмеження на час розв’язання задачі Тр, який не повинен перевищувати часу обміну повідомленнями Т_обм, тобто:

.

Час обміну залежить як від об’єму вхідних даних N і їх розрядності n, так і від кількості К, розрядності n_k та частоти F_d надходження даних у каналах [3]. Даний час визначається за формулою:

.

Для забезпечення розв’язання задач в реальному часі продуктивність спеціалізованих комп’ютерних систем повинна бути:

,

де R складністю алгоритмів розв’язання задач; β – коефіцієнт врахування особливостей засобів реалізації алгоритму [4].

Алгоритми управління та обробки сигналів у спеціалізованих комп’ютерних системах (СКС) можуть реалізовуватися на базі програмних, мікропрограмних або апаратних засобів. Кожний із видів реалізації алгоритмів має свої особливості, переваги і недоліки.

При програмній реалізації алгоритмів управління та обробки сигналів обчислювальні процеси переважно розгортаються в часі з великим об’ємом пересилок інформації між оперативною пам’яттю і операційними пристроями. Програмні засоби є доступними для програміста, перед яким виникає задача мінімізації об’єму програм і часу їх реалізації при заданій точності обчислень. Вказані засоби характеризуються низькою швидкодією і гнучкістю з точки зору можливості модифікації та заміни алгоритмів [5].

Мікропрограмна реалізація обчислень передбачає їхнє розгортання як в часі, так і в просторі. При мікропрограмуванні є доступ до системи мікропрограм процесора, що забезпечується застосуванням постійної пам’яті, програмованих логічних матриць, а також оперативних запам’ятовуючих пристроїв, які використовується в якості пам’яті мікропрограм [6]. Реалізація в повній мірі потенціальних можливостей мікропрограмних засобів може бути досягнута лише при глибокому вивченні як задачі, яка розв’язується, так і внутрішньої мови процесора. Мікропрограмні засобами реалізації алгоритмів управління та обробки сигналів в порівнянні з програмними є більш швидкодіючими.

Успіхи в області інтегральної технології дозволяють все більше перекладати реалізацію алгоритмів управління та обробки сигналів на апаратні засоби, які розгортають обчислення не тільки у часі, а і в просторі [2]. Такі обчислення характеризуються введенням додаткового обладнання і відсутністю проміжних пересилок інформації в процесі обчислення, а також спрощенням функції місцевого управління. В основі структурної організації апаратних засобів лежить принцип адекватного апаратного відображення потокових графів алгоритмів управління та обробки сигналів на комбінаційну матрицю, процесорні елементи якої реалізують функціональні оператори та з’єднані між собою відповідно з потоковим графом алгоритмом [3]. Синтезовані за таким принципом структури є алгоритмічними. В алгоритмічних структурах алгоритм виконується над вхідними даними при їх одноразовому проходженні через всі ПЕ. Апаратні засоби дозволять з максимальною швидкодією реалізовувати алгоритми управління та обробки сигналів.

Потрібно відзначити, що в СКС реального часу всі види реалізації алгоритмів в безпосередньому вигляді зустрічаються досить рідко. На практиці в СКС для реалізації алгоритмів управління та обробки сигналів у реальному часі використовуються комбіновані підходи з перевагою одного з перерахованих засобів. Вибір того чи іншого засобу як основного для реалізації алгоритмів у СКС реального часу здійснюється із вимог забезпечення режиму реального часу та високої ефективності використання обладнання. У СКС управління та обробка сигналів у режимі реального часу забезпечується розпаралелюванням і конвеєризацією процесів обробки [5]. В зв’язку з цим актуальною задачею є розробка високоефективних СКС узгоджено-паралельної обробки сигналів і управління у реальному часі.

Постановка задачі і мета дослідження

При реалізації СКС управління та обробки сигналів у реальному часі висока ефективність використання обладнання досягається узгодженням інтенсивності надходження даних Р_d=kn_dF_d, де k – кількість каналів надходження даних; n_d – розрядність каналів надходження даних; F_d - частота надходження даних, із інтенсивністю обчислень (обчислювальною здатністю) СКС, яку визначають так:

,

де, m_m – кількість каналів надходження даних у сходинках конвеєра, n_m – розрядність каналів надходження даних у сходинках конвеєра; Т_к – такт конвеєра.

Одним із основних інтегральних параметрів оцінки СКС управління та обробки сигналів у реальному часі є ефективність використання обладнання, який враховує кількість виводів інтерфейсу, однорідність структури, кількість і локальність зв’язків, зв’язує продуктивність з витратами обладнання та дає оцінку елементам системи за продуктивністю [4]. Кількісна величина ефективності використання обладнання визначається так:

,

де R – складність алгоритму, яка визначається кількістю елементарних арифметичних операцій необхідних для його реалізації; t_o – час реалізації алгоритмів управління та обробки сигналів; W_ФУі – витрати обладнання на реалізацію і-го функціонального вузла, d_i – кількість функціональних вузлів і-го типу, k₁ – коефіцієнт врахування однорідності k₁=f(s), s – кількість видів функціональних вузлів, Q – загальна кількість зв’язків, k₂ – коефіцієнт врахування регулярності зв’язків k₂=f(),  – просторова зв’язкова віддаль, Y – кількість виводів інтерфейсу, k₃ – коефіцієнт врахування кількості виводів інтерфейсу зв’язку k₃=f(Y).

Для розробки СКС реального часу з високою ефективністю використання обладнання необхідно використовувати НВІС-технологію і просторово-часове розпаралення. У паралельно-конвеєрній СКС реального часу висока ефективність використання обладнання досягається узгодження інтенсивності надходження потоків даних з обчислювальною інтенсивністю системи [3]. Розробка СКС реального часу з високою ефективністю використання обладнання вимагає широкого використання сучасної елементної бази (напівзамовних і замовних НВІС, однокристальних процесорів обробки сигналів), розробки нових методів, алгоритмів і спеціалізованих структур, орієнтованих на НВІС-реалізацію. Інтенсивність надходження даних, складність алгоритмів оброки та обмеження, що висуваються до часу, габаритів і споживаної потужності є визначальними при виборі архітектури спеціалізованої комп’ютерної системи управління та обробки сигналів у реальному часі [4].

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

Виклад основного матеріалу

Компонентно-ієрархічний підхід до проектування СКС управління та обробки сигналів у реальному часі. Розглянемо три основні варіанти побудови СКС управління та обробки сигналів у реальному часі[3]:

· на основі універсальних і функціонально-орієнтованих мікропроцесорів шляхом розробки спеціалізованого програмного забезпечення;

· універсального обчислювального ядра доповненого базовими апаратно-програмними компонентами, які реалізують часомісткі алгоритми функціонування ШНМ;

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

Перший варіант є доступним для широкого кола користувачів. Істотною його перевагою є можливість використання раніше розроблених програм. Його недоліками є невисока швидкодія, функціональна і структурна надлишковість комп’ютерних засобів.

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

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

Другий і третій варіанти є найперспективнішими для синтезу СКС управління та обробки сигналів у реальному часі з високою ефективністю використання обладнання.

Розробку СКС реального часу доцільно здійснювати на основі компонентно-ієрархічного підходу, який передбачає поділ процесу розробки на ієрархічні рівні та види забезпечення (алгоритмічне, апаратне та програмне) [3]. Для реалізації такого підходу використовується метод декомпозиції, який передбачає розбиття процесу проектування СКС реального часу на окремі компоненти. На кожному рівні ієрархії проектування СКС розв’язується задачі відповідної складності, які характеризуються як одиницями інформації, так і алгоритмами обробки. За складністю розв’язувані задачі діляться на чотири ієрархічні рівні. Збільшенню номера рівня ієрархії відповідає збільшення деталізації алгоритмічних, апаратних і програмних засобів. При цьому на вищих рівнях ієрархії одиниці інформації, алгоритми, програмні та апаратні засоби представляють собою впорядковані сукупності одиниць інформації та композиції алгоритмів, програмних і апаратних засобів нижчих рівнів ієрархії (табл.1). Методологія послідовної декомпозиції, яка використовується при розробці СКС реального часу, відображає процес розробки “зверху-вниз”.

Табл.1

Рівні та види розробок СКС реального часу

На першому ієрархічному рівні проектування СКС реального часу розробляються алгоритми функціонування, структури апаратних і програмних засобів СКС.

На другому ієрархічному рівні проектування СКС розв’язуються задачі проектування процесорів, що реалізують ортогональні тригонометричні та дискретні хвильові перетворення, цифрову та медіанну фільтрації, сортування даних і нейромережеві засоби для класифікації та розпізнавання зображень. Алгоритми реалізації перелічених компонентів подаються у вигляді функціонального графу з використанням функціональних операторів на рівні базових операцій. На основі аналізу функціонального графу визначаються перелік процедур для програмної і апаратної реалізації. Для виділених процедур розробляються паралельні алгоритми, НВІС-структури та програми [2].

Третій ієрархічний рівень проектування СКС зв’язаний з проектуванням операційних блоків, які реалізують базові операції алгоритмів цифрової обробки сигналів: множення комплексних чисел, обчислення базових операцій швидких алгоритмів ортогональних тригонометричних перетворень, обчислення сум парних добутків, піднесення до степеня та макрооперації логічних обчислень. Для реалізації елементів третього рівня розробляються паралельні алгоритми, НВІС-структури та підпрограми.

До четвертого рівня ієрархії проектування СКС відносяться арифметичні пристроїв, які реалізують операції множення, ділення, обчислення квадратного кореня, обчислення максимальних і мінімальних значень. В функціональному і структурному відношеннях елементи четвертого рівня ґрунтуються на операціях: передачі, інвертування, зсуву, порівняння, додавання та віднімання. На основі цього операційного базису розробляються паралельні алгоритми, НВІС-структури та підпрограми реалізації елементів третього рівня.

Компонентно-ієрархічну структуру СКС реального часу можна описати за допомогою такого виразу:

,

де , , ,  - засоби відповідно першого, другого, третього і четвертого ієрархічних рівнів; n – кількість типів процесорів; m - кількість типів операційних блоків; h - кількість типів арифметичних пристроїв.

Принципи побудови СКС управління та обробки сигналів у реальному часі. Розробку та оптимізацію апаратно-програмних параметрів СКС управління та обробки сигналів у реальному часі пропонується здійснювати на основі інтегрованого підходу, який охоплює [4]:

· алгоритмічні, апаратні, програмні засоби та сучасну елементну базу;

· сучасні методи та алгоритми управління та цифрової обробки сигналів;

· методи та засоби автоматизованого проектування апаратного і програмного забезпечення СКС реального часу;

· нові, орієнтовані на НВІС-реалізації, алгоритмічні, архітектурні та схемотехнічні рішення.

В основу побудови апаратних засобів СКС управління та обробки сигналів у реальному часі необхідно покласти принципи, які дозволять зменшити вартість, терміни і розширити галузі їх застосування. Аналіз показує, що забезпечити дані вимоги можна при використанні таких принципів побудови [3,4]:

·    змінного складу обладнання, що передбачає наявність ядра СКС та змінних модулів (алгоритмічних пристроїв), за допомогою яких ядро адаптується до вимог конкретного застосування;

·    модульності, який передбачає розробку компонентів СКС у вигляді функціонально завершених пристроїв (модулів), що мають вихід на стандартний інтерфейс;

·    узгодженості інтенсивності надходження даних з обчислювальною здатністю апаратних засобів СКС;

·    конвеєризації та просторового паралелізму обробки даних;

·    відкритості програмного забезпечення, що передбачає можливості нарощування та його вдосконалення, максимального використанням стандартних драйверів та програмних засобів;

·    спеціалізації та адаптації апаратно-програмних засобів до структури алгоритмів обробки та інтенсивності надходження даних;

·    програмованості архітектури шляхом використання репрограмованих логічних інтегральних мікросхем;

·    використання паралельної пам’яті для зберігання інформації та обміну між компонентами системи.

Етапи синтезу СКС управління та обробки сигналів у реальному часі.. Синтез СКС складається із наступних етапів:

·   розробки методів і алгоритмів узгоджено-паралельної обробки;

·   визначення основних характеристик СКС;

·   перехід від алгоритму до структури СКС.

При виборі та розробці методів і алгоритмів узгоджено-паралельної обробки враховуються вимоги R і характеристики H, але визначальним є забезпечення обмежень B. Для оцінки розроблених алгоритмів використовуються характеристики: інформаційні, операційні та точності. До інформаційних характеристик відносяться: кількість констант, вхідних, вихідних і проміжних даних, кількість каналів і їх розрядність, кількість і види операцій. Операційні характеристики дозволяють оцінити час реалізації та обчислювальну здатність. До характеристик точності алгоритму відносяться: розрядність операційних пристроїв, способи округлення. У СКС узгоджено-паралельної обробки сигналів у реальному часі необхідно забезпечити узгодженість інтенсивності надходження даних Р_d із обчислювальною інтенсивністю D_СКС комп’ютерної системи на всіх етапах обробки.

Шляхи підвищення ефективності використання обладнання. В СКС управління та обробки сигналів у реальному часі висока ефективність використання обладнання досягається мінімізацією витрат обладнання на їх реалізацію при забезпечені реального часу [3]. Перехід від алгоритму розв’язання задачі в реальному часі до структури СКС формально зводиться до мінімізації витрат обладнання:

де W_СКС, W_ПУ, W_ІП, W_П, W_ПЕ - витрати обладнання відповідно на реалізацію СКС, пристрою управління, інтерфейс них пристроїв, пам’яті, процесорних елементів; k – кількість типів процесорних елементів, і-й процесорний елемент, m_i – кількість процесорних елементів і-о типу, при забезпеченні такої умови:

                                                                        (1)

де N – кількість даних; n – розрядність даних.

Основними шляхами мінімізації затрат обладнання при проектуванні СКС управління та обробки сигналів у реальному часі є:

·   вибір ефективних методів і алгоритмів розв’язання задач і реалізації функціональних операторів;

·   зменшення розрядності операційних пристроїв, ємності пам’яті, кількості і розрядності каналів передачі даних;

·   узгодження інтенсивності надходження даних Р_d із обчислювальною здатність D_СКС апаратних засобів СКС.

Метод просторово-часового відображення алгоритмів управління та обробки сигналів у узгоджено-паралельні структури. Одна з найбільш відповідальних задач при проектуванні СКС є перехід від алгоритму розв’язання задачі до структури СКС. Алгоритми розв’язання задач можна описувати через залежність між входом і виходом або детально пояснюючи їх внутрішню структуру. Подання алгоритмів у формі стандартного математичного запису не дозволяє достатньо повно оцінити можливості розпаралелення та знайти способи їх ефективної реалізації на існуючих обчислювальних засобах або створити нові ефективні структури. Тому для вибору ефективного варіанту реалізації алгоритму є потреба подати його у формі, яка одночасно відображає просторові та часові характеристики [7-9].

Однією з форм подання алгоритму, яка дозволяє оцінити його обчислювальні та структурні характеристики, є зображення алгоритму у вигляді функціонального графу (ФГ). Він описує залежність обчислень, які виконуються в алгоритмі. Символьний запис графу алгоритму представляється як композиція функціональних операторів і має вигляд: F=(Ф,Г), де Ф={Ф₁,Ф₂,…,Ф_n} – множина функціональних операторів, Г- закон відображення зв’язків між операторами. Графічно ФГ відображається у вигляді вершин, що відповідають операторам алгоритму Ф_і та дуг, які відображають зв’язки між операторами, тобто залежності даних в алгоритмі. Відображення алгоритму в формі ФГ не дозволяє в повній мірі відобразити просторово-часові характеристики алгоритму [2].

Виявити паралелізм алгоритму та управляти ним, забезпечуючи тим самим можливість знаходити оптимальні просторово-часові рішення, які використовуються при синтезі обчислювальної структури і її основних елементів, дозволяє відображення алгоритму у ярусно-паралельній формі (ЯПФ) [5,7,8]. При такій формі подання алгоритму здійснюється розподіл всіх його функціональних операторів Ф_і за ярусами таким чином, що в j-му ярусі розміщені функціональні оператори, які залежать хоча б від одного функціонального оператора (j-1)-го ярусу і не залежать від операторів наступних ярусів. В середині ярусу функціональні оператори між собою не мають з’єднань.

Кожний j-й ярус алгоритму описується наступними параметрами:

· наборами незалежних функціональних операторів Ф_jk, де j- номер ярусу, k- номер функціонального оператора в ярусі;

· набором каналів надходження даних і видачі проміжних результатів;

· розрядністю кожного каналу зв’язку.

Кількість ярусів визначає висоту h, а максимальна ширина ярусів визначає її ширину L ЯПФ відображення алгоритму. При відображені орієнтованого графа алгоритму у ЯПФ номера ярусів j є часовими індексами, а номера k функціональних операторів у ярусі є просторовими індексами. За допомогою просторово-часових індексів у системі координат час-простір задається розміщення функціональних операторів. Параметри потокового графу: складність функціональних операторів Ф_і, ширина L і висота h є взаємно залежними, зміна одного з них веде до зміни інших.

Відображення орієнтованого графа у ЯПФ будемо називати потоковим графом (ПГ). Перехід від алгоритму розв’язання задачі до ПГ необхідно здійснюється в три етапи:

·   декомпозиція алгоритму розв’язання задачі;

·   проектування комунікацій (обмінів даними) між функціональними операторами;

·   перехід від ФГ алгоритму до ПГ.

На етапі декомпозиції алгоритм розв’язання задачі Ф розбивається на функціональні оператори Ф_і, між якими установлюються зв’язки, що відповідають даному алгоритму. Чим більшу ступінь деталізації алгоритму отримуємо у результаті декомпозиції, тим гнучкішим буде алгоритм і тим легше можна здійснити адаптацію його до виконання умови (1). Декомпозицію можна здійснювати за методом декомпозиції даних або функціональної декомпозиції. Використання методу функціональної декомпозиції дозволяє отримати просторово-часове відображення структури алгоритму на рівні операцій Ф_і, які використовуються при НВІС-реалізаціях [7,8]. При використанні методу декомпозиції даних спочатку сегментуються дані, а потім алгоритми обробки. Вибір методу декомпозиції залежить як від структури даних, так і від алгоритму розв’язання задачі. На практиці для синтезу високоефективних алгоритмічних структур реального часу використовується метод функціональної декомпозиції, при якому алгоритм Ф розбивається на операції Ф_і, кожна із яких може бути реалізована операційними блоками певного рівня ієрархії. Час і спосіб виконання операції Ф_і операційним блоком є одними із основних параметрів при визначені конвеєрного такту роботи Т_к і розрядності каналів надходження даних п_к для алгоритмічних структур реального часу. Результатом першого етапу розробки є граф схема алгоритму, де функціональні оператори Ф_і мають приблизно однаковий час виконання, а їх складність визначається засобами реалізації.

На етапі проектування комунікацій для конвеєрної алгоритмічної реалізації алгоритму необхідно визначити структуру каналів обміну даними між функціональними операторами Ф_і. Для чого виконується перехід від граф-схеми алгоритму до потокового графу, в якому здійснюється просторово-часове розміщення і закріплення функціональних операторів Ф_i за ярусами. Структура зв’язків у потоковому графі між функціональними операторами Ф_jk сусідніх ярусів визначає кількість каналів надходження даних m_j і структуру з'єднань між операційними блоками при апаратній реалізації алгоритму. У більшості алгоритмів цифрової обробки сигналів передача даних між ярусами виконується методами досконалого тасування або обмінної перестановки.

Для переходу до відображення алгоритму в ПГ необхідно його записати у вигляді матриці nxn, де “1” відповідає наявності каналу зв’язку, “0” – відсутності зв’язку [5]. Матриця формується таким чином, що для кожного функціонального оператора Ф_і джерела інформації формується стрічка, яка відображає його зв’язки з іншими функціональними операторами. Якщо позначити через вектори  відповідні стовпці матриці, то можна визначити результуючий вектор стовпець:

В векторі  визначаємо номера елементів, які дорівнюють нулю, наприклад, десятий. За визначеним номером знаходимо функціональний оператор, що не має нащадків і відповідно утворює нульовий ярус, в даному випадку Ф₁₀. Далі за формулою обчислюємо:

.

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

Для переходу від алгоритму розв’язання задачі до структури СКС реального часу необхідно розробити узгоджений ПГ [4]. Процес розробки узгодженого ПГ виконується за два етапи:

·   укрупнення функціональних операторів;

·   планування обчислень.

Розроблений ПГ дозволяє оцінити обчислювальну здатність D_к проектованої СКС. Вихідними даними для визначення обчислювальної здатності D_к є m_m - кількість каналів надходження даних, n_m – розрядність каналів даних, складність функціональних операторів Ф_і, особливості і швидкодія елементної бази. Використовувана елементна база і її швидкодія є визначальними для оцінки такту роботи Т_к апаратних засобів СКС. Для оцінки узгодженості інтенсивності надходження даних P_d із обчислювальною здатністю D_СКС вводиться коефіцієнт узгодженості, який визначається так:

.

Узгодження обчислювальної здатності D_СКС апаратних засобів СКС із інтенсивністю надходження даних P_d досягається шляхом зміни тривалості такту Т_к або кількості m_m і розрядності n_m каналів надходження даних у потоковому графі. При розробці узгодженого ПГ алгоритму для реалізації СКС з високою ефективністю використання обладнання необхідно у першу чергу максимального використати особливості та швидкодію елементної бази, тобто визначити складність функціональних операторів Ф_і і мінімізувати тривалість такту Т_к. У другу чергу, змінювати кількість m_m і розрядність n_m каналів у ПГ, що напряму зв’язано з використовуваною елементною базою. Зміна параметрів ПГ алгоритму має забезпечити узгодження обчислювальної здатності D_СКС апаратних засобів СКС із інтенсивністю надходження даних P_d.

У випадку коли R=1, то розроблений узгоджений ПГ забезпечує отримання узгоджено-паралельної структури СКС реального часу з високою ефективністю використання обладнання.

Якщо R<1, то для забезпечення обробки потоків даних у реальному часі необхідне збільшення обчислювальної здатності D_СКС, яке може бути досягнуте збільшенням кількість каналів m_m, їх розрядності n_m або зменшенням такту конвеєра Т_к., що досягається зменшенням складності функціональних операторів Ф_і. У випадку коли зміною перерахованих параметрів не вдається досягнути необхідної обчислювальної здатності D_СКС, то тоді використовується паралельне включення алгоритмічних апаратних засобів, кількість яких визначається виразом:

h=ù1/Ré

де ù  é - знак округлення до більшого цілого.

У випадку коли R>1, то для забезпечення високої ефективності використання обладнання необхідно переходити до третього етапу розробки – укрупнення функціональних операторів Ф_jk. На цьому етапі здійснюється об’єднання функціональних операторів Ф_jk i каналів передачі даних у ярусах потокового графа, або об’єднання функціональних операторів сусідніх ярусів. Граф алгоритму, який отримаємо у результаті такого об'єднання будемо називати узгодженим потоковим графом. Коефіцієнт об'єднання v визначається так:

v£ û D_СКС /P_d ë

де û ë - знак округлення до меншого цілого.

При об’єднанні функціональних операторів v сусідніх ярусів утворюється один ярус функціональних макрооператорів, у якому за v ітерацій виконується обчислення таких функціональних макрооператорів V. Обчислення у середині ярусу здійснюється із тактом Т_к, який визначається складність функціональних операторів Ф_jk а між ярусами з макротактом . Об’єднання функціональних операторів сусідніх ярусів приводить до зменшення у v разів кількості ярусів. Таке об’єднання доцільно здійснювати коли яруси ПГ є однотипними. Інше укрупнення здійснюють шляхом об’єднання функціональних операторів і каналів передачі даних у межах ярусу. Для випадку коли  укрупнення здійснюють шляхом лінійної проекції, при якій всі функціональні оператори ярусу ПГ відображаються у один функціональний макрооператор, а канали передачі даних – у оператор затримки та перестановки даних. Для забезпечення узгодженості може використовуватися комбіноване укрупнення, яке передбачає об’єднання функціональних операторів і каналів передачі даних як у середині ярусу, так і між ярусами.

Структура узгодженого потокового графу алгоритму відображається орієнтованим графом G=<V,E,D(E)>, де V - функціональні макрооператори ярусу; E – орієнтовані дуги, які моделюють зв’язки між функціональними макрооператорами. Кожна дуга еЕ зв’язує вихід одного функціонального макрооператора з входом другого та володіє вагою, рівною значенню затримки D(e) [2].

Етап укрупнення тісно пов’язаний з етапом планування, на якому після об'єднання функціональних операторів для збереження інформації про структуру потокового графа алгоритму здійснюється планування обчислень, визначаються величини затримок і перестановки даних. Для відтворення обчислень у кожний ярус узгодженого графа вводяться оператори управління затримки та перестановки даних [7,8].

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

Процес розробки узгодженого потокового графа алгоритму є ітераційним, він тісно пов’язаний з покращенням характеристик алгоритму.

Висновки

1. Для вибору апаратних засобів для СКС реального часу доцільно використовувати критерій ефективності використання обладнання, який враховує кількість виводів інтерфейсу, однорідність структури, кількість і локальність зв’язків, зв'язує продуктивність з витратами обладнання та дає оцінку елементам системи за продуктивністю.

2. Основними шляхами підвищення ефективності використання обладнання в СКС реального часу є: вибір ефективних методів і алгоритмів розв’язання задач; зменшення розрядності операційних пристроїв, ємності пам’яті, кількості і розрядності каналів передачі даних; узгодження інтенсивності надходження даних із обчислювальною здатністю апаратних засобів на всіх рівнях.

3. Визначено, що узгодження інтенсивності надходження даних із обчислювальною здатністю СКС реального часу може здійснюватися шляхом зміни тривалості конвеєрного такту, кількості і розрядності каналів надходження даних.

4. Основними етапами синтезу СКС реального часу є: вибір та розробка методів і алгоритмів узгоджено-паралельної обробки; визначення основних характеристик апаратних засобів; перехід від алгоритму до узгодженої-паралельної структури СКС.

5. Для переходу від алгоритму до структури апаратних засобів СКС реального часу використовується узгоджений потоковий граф, основними етапами формування якого є: декомпозиція алгоритму розв’язання задачі; проектування комунікацій (обмінів даними) між функціональними операторами; укрупнення функціональних операторів; планування обчислень.

ЛІТЕРАТУРА

1.                  Каневский Ю.С. Систолические процессоры. – К: Техника, 1991,-173с.

2.                  Кун С. Матричные процессоры на СБИС. М: Мир, 1991, -672 с.

3.                  Цмоць І.Г. Інформаційні технології та спеціалізовані засоби обробки сигналів і зображень у реальному часі. – Львів: УАД, 2005.- 227с.

4.                  Цмоць І.Г., Я.П. Кісь, В.Р. Іванців. Принципи розробки та оцінка основних характеристик комп’ютерних систем реального часу. Науково-технічний журнал “Технічні вісті”1/10,2/11. 2008. с.46-49.

5.                  Параллельная обработка информации: в 5т./ АН УССР. Физ-мех. ин-т. – Киев: Наукова думка, 1984. – т5: Проблемно-ориентированные и специализированные средства обработки информации / А.И. Аксенов, В.В. Аристов, Е.Ю. Барзилович и др.; Под ред. Б.Н. Малиновского и Грицика В. В. – 1990. – 504с.

6.                  Грушицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах программируемой логики. – СПб.: БХВ-Петербург, 2002. – 608с.

7.                  Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. – 608с.

8.                  Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных систем. – СПб.: БХВ – Петербург, 2002. – 400с.

9.                   Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. – СПб.: БХВ – Петербург, 2003. – 1104с.