Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.325

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

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

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

.

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

.

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

,

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

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

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

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

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

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

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

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

,

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

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

,

де R – складність алгоритму, яка визначається кількістю елементарних арифметичних операцій необхідних для його реалізації; to – час реалізації алгоритмів управління та обробки сигналів; WФУі – витрати обладнання на реалізацію і-го функціонального вузла, di – кількість функціональних вузлів і-го типу, k1 – коефіцієнт врахування однорідності k1=f(s), s – кількість видів функціональних вузлів, Q – загальна кількість зв’язків, k2 – коефіцієнт врахування регулярності зв’язків k2=f(),  – просторова зв’язкова віддаль, Y кількість виводів інтерфейсу, k3 – коефіцієнт врахування кількості виводів інтерфейсу зв’язку k3=f(Y).

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

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

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

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

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

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

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

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

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

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

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

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

Табл.1

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

Ієрархічний

рівень

Види забезпечення та виконувані розробки

Алгоритмічне

Апаратне

Програмне

1-й

Алгоритми функціонування СКС

Структура апаратних засобів СКС

Структура програмних засобів СКС

2-й

Алгоритми функціонування процесорів та їх складових

Структури процесорів

Модуль програми реалізації алгоритмів обробки

3-й

Алгоритми реалізації базових операцій (макрооперацій)

Структури операційних пристроїв для реалізації базових операцій (макрооперацій)

Підпрограми реалізацій базових операцій (макрооперацій)

4-й

Алгоритми реалізації арифметичних операцій

Структури арифметичних пристроїв

Підпрограми реалізацій арифметичних операцій

 

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                                        (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

.

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

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

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

h=ù1/Ré

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

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

v£ û DСКС /Pd ë

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

При об’єднанні функціональних операторів 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с.

 





Ответы на вопросы [_Задать вопроос_]

Информационно-управляющие комплексы и системы

Теленик С.Ф., Ролік О.І., Букасов М.М., Андросов С.А. Генетичні алгоритми вирішення задач управління ресурсами і навантаженням центрів оброблення даних

Богушевский В.С., Сухенко В.Ю., Сергеева Е.А., Жук С.В. Реализация модели управления конвертерной плавкой в системе принятия решений

Бень А.П., Терещенкова О.В. Применение комбинированных сетевых методов планирования в судоремонтной отрасли

Теленик С.Ф., РолікО.І., Букасов М.М., РимарР.В., Ролік К.О. Управління навантаженням і ресурсами центрів оброблення даних при виділених серверах

Селякова С. М. Структура інтелектуальної системи управління збиральною кампанією

Еременко А.П., Передерий В.И. Принятие решений в автоматизированных системах с учетом психофункциональных характеристик оператора на основе генетических алгоритмов

Львов М.С. Алгоритм перевірки правильності границь змінення змінних у послідовних програмах

Ляшенко Е.Н. Анализ пожарной опасности сосновых насаждений в зоне Нижне-днепровских песков – самой большой пустыни в Европе

Кучеров Д.П., Копылова З.Н. Принципы построения интеллектуального автору-левого

Касаткина Н.В., Танянский С.С., Филатов В.А. Методы хранения и обработки нечетких данных в среде реляционных систем

Ходаков В.Е., Жарикова М.В., Ляшенко Е.Н. Применение когнитивного подхода для решения задачи поддержки принятия управленческих решений при ликвидации лесных пожаров

Гончаренко А.В. Моделювання впливу ентропії суб’єктивних переваг на прийняття рішень стосовно ремонту суднової енергетичної установки

Фарионова Н.А. Системный подход построения алгоритмов и моделей систем поддержки принятия решений при возникновении нештатных ситуаций

Биленко М.С., Серов А.В., Рожков С.А., Буглов О.А. Многоканальная система контроля качества текстильных материалов

Мотылев K.И., Михайлов M.В., Паслен В.В. Обработка избыточной траекторной информации в измерительно-вычислительных системах

Гончаренко А.В. Вплив суб’єктивних переваг на показники роботи суднової енергетичної установки

Гульовата Х.Г., Цмоць І.Г., Пелешко Д.Д. Архітектура автоматизованої системи моніторингу і дослідження характеристик мінеральних вод

Соломаха А.В. Разработка метода упреждающей компенсации искажений статорного напряжения ад, вносимых выходными силовыми фильтрами

ПотапенкоЕ.М., Казурова А.Е. Высокоточное управление упругой электромеханической системой с нелинейным трением.

Кузьменко А.С., Коломіц Г.В., Сушенцев О.О. Результати розробки методу еквівалентування функціональних особливостей fuzzy-контролерів

Кравчук А. Ф., Ладанюк А.П., Прокопенко Ю.В. Алгоритм ситуационного управления процессом кристаллизации сахара в вакуум-аппарате периодического действия с механическим циркулятором

Абрамов Г.С., Иванов П.И., Купавский И.С., Павленко И.Г. Разработка навигационного комплекса для автоматического наведения на цель системы груз-управляемый парашют

Литвиненко В.И., Четырин С.П. Компенсация ошибок оператора в контуре управления следящей системы на основе синтезируемых вейвелет-сетей

Бардачев Ю.Н., Дидык А.А. Использование положений теории опасности в искусственных иммунных системах

Рожков С.О., Кузьміна Т.О., Валько П.М. Інформаційна база як основа для створення асортименту лляних виробів.

Ускач А.Ф., Становский А.Л., Носов П.С. Разработка модели автоматизированной системы управления учебным процессом

Мазурок Т.Л., Тодорцев Ю.К. Актуальные направления интеллектуализации системы управления процессом обучения.

Ускач А.Ф., Гогунский В.Д., Яковенко А.Е. Модели задачи распределения в теории расписания.

Сідлецький В.М., Ельперін І.В., Ладанюк А.П. Розробка алгоритмів підсистеми підтримки прийняття рішень для контролю якості роботи дифузійного відділення.

Пономаренко Л.А., Меликов А.З., Нагиев Ф.Н. Анализ системы обслуживания с различными уровнями пространственных и временных приоритетов.

Коршевнюк Л.О. Застосування комітетами експертів системи нечіткого логічного виводу із зваженою істинністю.. – С. 73 – 79.

Кирюшатова Т.Г., Григорова А.А Влияние направленности отдельных операторов и направленности всей группы на конечный результат выполнения поставленной задачи.

Петрушенко А.М., Хохлов В.А., Петрушенко І.А. Про підключення до мови САА/Д деяких засобів паралельного програмування пакету МРІСН.

Ходаков В.Е., Граб М.В., Ляшенко Е.Н. Структура и принципы функционирования системы поддержки принятия решений при ликвидации лесных пожаров на базе новых геоинформационных технологий.

Сидорук М.В., Сидорук В.В. Информационные системы управления корпорацией в решении задач разработки бюджета.

Нагорный Ю.И. Решение задачи автоматизированного расчета надежности иасуп с использованием модифицированного метода вероятностной логики

Козак Ю.А. Колчин Р.В. Модель информационного обмена в автоматизированной системе управления запасами материальных ресурсов в двухуровневой логистической системе

Гожий А.П., Коваленко И.И. Системные технологии генерации и анализа сценариев

Вайсман В.А., Гогунский В.Д., Руденко С.В. Формирование структур организационного управления проектами

Бараненко Р.В., Шаганян С.М., Дячук М.В. Аналіз алгоритмів взаємних виключень критичних інтервалів процесів у розподілених системах

Бабенко Н.И., Бабичев С.А. Яблуновская Ю.А. Автоматизированная информационная система управления учебным заведением

Яковенко А.Е. Проектирование автоматизированных систем принятия решений в условиях адаптивного обучения с учетом требований болонского процесса

Бараненко Р.В Лінеаризація шкали і збільшення діапазону вимірювання ємностей резонансних вимірювачів

Головащенко Н.В. Математичні характеристики шумоподібно кодованих сиг-налів.

Шерстюк В.Г. Формальная модель гибридной сценарно-прецедентной СППР.

Шекета В.І. Застосування процедури Append при аналізі абстрактних типів даних модифікаційних запитів.

Цмоць І.Г. Алгоритми та матричні НВІС-структури пристроїв ділення для комп'-ютерних систем реального часу.

Кухаренко С.В., Балтовский А.А. Решение задачи календарного планирования с использованием эвристических алгоритмов.

Бараненко Р.В., Козел В.Н., Дроздова Е.А., Плотников А.О. Оптимизация рабо-ты корпоративных компьютерных сетей.

Нестеренко С.А., Бадр Яароб, Шапорин Р.О. Метод расчета сетевых транзакций абонентов локальных компьютерных сетей.

Григорова А.А., Чёрный С. Г. Формирование современной информационно-аналитической системы для поддержки принятия решений.

Шаганян С.Н., Бараненко Р.В. Реализация взаимных исключений критических интервалов как одного из видов синхронизации доступа процессов к ресурсам в ЭВМ

Орлов В.В. Оценка мощности случайного сигнала на основе корреляционной пространственной обработки

Коджа Т.И., Гогунский В.Д. Эффективность применения методов нечеткой логики в тестировании.

Головащенко Н.В., Боярчук В.П. Аппаратурный состав для улучшения свойств трактов приёма – передачи информации в системах промышленной автоматики.