Національний університет “Львівська політехніка”

БАЧИНСЬКИЙ РУСЛАН ВОЛОДИМИРОВИЧ

УДК 004.272, 004.383.3

РЕКОНФІГУРОВАНІ ПРОЦЕСОРИ СТИСКУ ПОТОКІВ ДАНИХ

05.13.05 – Комп’ютерні системи та компоненти

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

кандидата технічних наук

Львів-2008

Дисертацією є рукопис

Робота виконана у Національному університеті "Львівська політехніка" Міністерства освіти і науки України

Науковий керівник – доктор технічних наук, професор

Мельник Анатолій Олексійович,
завідувач кафедри “Електронні обчислювальні машини”
Національного університету "Львівська політехніка"

Офіційні опоненти – доктор технічних наук, професор
Наконечний Адріан Йосифович,
завідувач кафедри “Комп'ютеризовані системи автоматики” Національного університету "Львівська політехніка".

кандидат технічних наук, доцент

Іщеряков Сергій Михайлович,
доцент кафедри “Програмне забезпечення автоматизованих систем” Івано-Франківського Національного технічного університету нафти і газу

Захист відбудеться “27” червня 2008р. о “1400” годині на засіданні спеціалізованої вченої ради Д 35.052.08 у Національному університеті "Львівська політехніка" (79013, Львів-13, вул.С.Бандери,12, ауд.226 головного корпусу).

З дисертацією можна ознайомитися у бібліотеці Національного університету "Львівська політехніка" (79013, Львів, вул.Професорська,1)

Автореферат розісланий “23” травня 2008 р.

Вчений секретар спеціалізованої

вченої ради, д.т.н., проф. Я.Т. Луцик

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась відповідно до напрямків наукової діяльності кафедри електронних обчислювальних машин Національного університету “Львівська політехніка” за темою Міністерства освіти і науки України:

· ДБ/АВАГ “Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища”, 2004 р. (номер державної реєстрації 0104U002284).

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

Для досягнення мети в роботі розв’язані наступні задачі:

1. Проведено аналіз найбільш вживаних алгоритмів стиску даних з метою виявлення та узагальнення їх характерних особливостей з точки зору їх реалізації.

2. Сформовано основні вимоги до апаратних засобів систем стиску даних. Проаналізовано існуючі апаратні засоби та визначено їх відповідность сформованим вимогам.

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

4. Розроблено базові вузли конфігурованої структури комп’ютерної системи стиску потоків даних.

5. Проаналізовано вплив конфігураційних параметрів запропонованої структури комп’ютерної системи стиску потоків даних на її характеристики.

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

Предмет дослідження – комп’ютерні системи стиску потоків даних з можливістю перебудови апаратних засобів.

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

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

При цьому отримано такі основні наукові результати:

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

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

3. Запропоновано новий метод керування потоками даних, який, на відміну від відомих, враховує статичні та динамічні характеристики потоків даних при плануванні розподілу апаратних ресурсів процесора, що дозволяє скоротити час обробки потоків даних.

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

Практичне значення одержаних результатів.

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

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

3. Розроблена VHDL модель багатоканального контролера потоків даних може бути використана при побудові систем паралельної обробки та комутації потоків даних.

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

Теоретичні та практичні результати дисертаційної роботи впровадженні у:

§ держбюджетній темі ДБ/АВАГ “Конфігуровані вимірювально-обчислювальні мережі інтелектуальних автономних агентів для вирішення задач моніторингу навколишнього середовища”, 2004 р.;

§ корпорації Cypress Semiconductor Corp. (США) в рамках створення базових та замовних проектів.

Дані про впровадження підтверджені відповідними актами.

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

Апробація результатів дисертації. Основні положення й результати дисертаційної роботи доповідались і обговорювались на таких наукових конференціях:

§ Міжнародна науково-технічна конференція “Сучасні проблеми радіоелектроніки, телекомунікацій, комп’ютерної інженерії – TCSET’2004” (Львів-Славсько, Україна, 24-28 лютого, 2004 р.);

§ Міжвузівська науково-технічна конференція науково-педагогічних працівників (Львів, Україна, 21-22 березня, 2006р.);

§ 16-а науково-технічна конференція “Моделювання” (Київ, Україна, 12-13 січня 2007р.);

§ 3-а міжнародна наукова конференція студентів, аспірантів і молодих вчених “Комп’ютерний моніторинг та інформаційні технології” (Донецьк, Україна, 22-23 травня 2007р.);

§ 3-а міжнародна науково-технічна конференція “Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування – СПРТП-2007” (Вінниця, Україна, 31 травня - 2 червня 2007р.);

§ 3-я міжнародна науково-технічна конференція “Сучасні комп’ютерні системи та мережі: розробка та використання – ACSN-2007” (Львів, Україна, 20-22 вересня, 2007 р.);

§ 2-а міжнародна конференція молодих науковців “Комп’ютерні науки та інженерія – CSE-2007” (Львів, Україна, 4-6 жовтня, 2007 р.).

Публікації. За результатами виконаних досліджень опубліковано 15 робіт загальним обсягом 66 сторінок, з них 8 статей у фахових наукових журналах та збірниках, 7 матеріалів доповідей у збірниках міжнародних науково-технічних конференцій.

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів, висновку, списку використаних джерел і 3-х додатків. Загальний обсяг роботи 224 сторінки, в тому числі 146 сторінок основного тексту, містить 45 рисунків, 5 таблиць, 3 додатки на 67 сторінках, список використаних джерел зі 119 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

В першому розділі проведено аналіз найбільш вживаних алгоритмів стиску та апаратних засобів їх реалізації. З точки зору апаратної реалізації слід виділити наступні особливості спеціалізованих (призначених для стиску даних певного типу – зображень, відео, аудіо даних …) алгоритмів стиску:

1. Дані обробляються впродовж декількох незалежних етапів, що дозволяє конвеєризувати та розпаралелити обробку потоків даних на різних етапах виконання алгоритму.

2. Дані розділяються на блоки, які обробляються незалежно. Це дає можливість розпаралелити обробку різних блоків даних на певних етапах виконання алгоритму.

3. Алгоритми стиску вимагають математичні обчислення різної складності на різних етапах свого виконання. Ця особливість вимагає ефективного планування використання апаратних ресурсів та буферизації даних для збільшення завантаження апаратних ресурсів та зменшення часу обробки.

Більшість алгоритмів стиску можна представити таким узагальненим аналітичним виразом:

,

де – результат обробки за алгоритмом стиску частини даних n на етапі m, – функція обробки даних за алгоритмом стиску на етапі m, – кількість блоків даних, які обробляються незалежно, М – кількість етапів обробки даних за алгоритмом стиску.

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

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

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

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

1. БкКПД – багатоканальний контролер потоків даних, до складу якого входять: БП0 – БПM – буферна пам’ять вхідних потоків даних; БкКП – багатоканальний контролер пам’яті; БкП – багатоканальна пам’ять; БП0 – БПL – буферна пам’ять проміжних потоків даних; БП0 – БПК – буферна пам’ять вихідних потоків даних.

2. БкПОД – багатоканальний процесор обробки даних, до складу якого входять: КМС – комутуюче середовище; ПОД0 – ПОДK – процесори обробки даних; БП0 – БПK – буферна пам’ять вхідних/вихідних потоків даних ПОД.

3. ППКПД – пристрій планування і керування потоками даних.

БкКПД виконує тимчасове зберігання вхідних і проміжних потоків даних, для подальшої обробки в БкПОД. Запити на зберігання і видачу потоків даних формує ППКПД, який виконує планування обробки потоків даних. Потоки даних в БкКПД ідентифікуються за допомогою унікальних ідентифікаторів потоків даних, які формуються БкКПД і видаються за вимогою від ППКПД.

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

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

Рис. . Базова реконфігурована структура комп’ютерної системи для автоматичного синтезу процесорів стиску потоків даних

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

Запропонований БкКПД із незалежним вхідним і вихідним трактами даних дозволяє виконувати видачу і зберігання декількох потоків даних одночасно, що забезпечує можливість завантаження нового потоку даних в БкПОД під час обробки попереднього потоку (конвеєрне завантаження потоків даних на обробку). Такий підхід зменшує час простою ПОД і збільшує ефективність використання апаратних ресурсів процесора. Структурна схема БкКПД зображена на рис.2.

Рис. – Структурна схема багатоканального контролера потоків даних

де КРПД – контролер ресурсів потоків даних, КК – контролер команд, КІдПД – контролер ідентифікаторів потоків даних, КВхПДx – контролер вхідних потоків даних ( x = 1 .. M), КВихПДx – контролер вихідних потоків даних ( x = 1 .. N), БкП – багатоканальна пам’ять, КБкП – контролер багатоканальної пам’яті, КВкБкП – контролер вказівників багатоканальної пам’яті.

Інформація про наявні потоки даних в БкКПД та апаратні ресурси БкКПД, які використовують ці потоки, міститься в КРПД та використовується КК для визначення розташування потоків даних в БкП для подальшого їх зчитування. При цьому КК виконує обробку команд, які надходять до БкКПД від ППКПД, та для забезпечення коректного вичитування потоків даних та звільнення апаратних ресурсів БкКПД, звертається до КРПД та КІдПД. У випадку зчитування потоку даних зі звільненням апаратних ресурсів, КК повертає в КІдПД ідентифікатор цього потоку. КІдПД містить інформацію про всі вільні ідентифікатори потоків даних, які є доступними в БкКПД, обробляє звертання від КК, який виконує запити на виділення нових та звільнення використаних ідентифікатори потоків даних. Елементи потоків даних зберігаються в БкП, яка може приймати і видавати їх паралельно декількома каналами за запитом від КВихПДx. При цьому коректне функціонування БкП в режимі одночасного звертання до БкП за всіма вхідними і вихідними каналами забезпечує КБкП. КВкБкП керує вільним адресним простором в БкП і виділяє вказівники на вільну пам’ять в БкП за запитом від КВхПДx, який керує збереженням потоків даних, що поступають на вхід БкКПД. По мірі надходження елементів даних вхідного потоку КВхПДx виконує запити до КВкБкП для отримання вказівників на вільний адресний простір у БкП. Після отримання вказівника КВхПДx перетворює його в лінійні адреси і виконує запис даних у БкП. Невикористана частина виділеного адресного простору повертається назад у КВкБкП. Інформація про вхідний потік даних та використаний ним адресний простір в БкП передається в КРПД. КВхПДx перетворює вхідні потоки даних БкКПД в елементи даних, які можуть зберігатись в БкП. КВихПДx зчитує елементи потоку даних з областей БкП, вказівники на які отримує від КК і, у випадку звільнення апаратних ресурсів, займаних потоком даних, повертає вказівник в КВкБкП.

Для забезпечення обробки даних за різними алгоритмами на одних і тих же апаратних засобах, а також для підвищення продуктивності системи стиску шляхом оптимізації структури апаратних засобів для різних алгоритмів стиску даних необхідно забезпечити можливість змінювати функціональність апаратних засобів БкПОД у процесі його функціонування. Це досягається завдяки використанню динамічно змінюваних процесорів обробки даних.

Структурна схема динамічно змінюваного ПОД зображена на рис.3,

Рис. – Структурна схема динамічно змінюваного процесора обробки даних

де ВхПД0 – ВхПДG-1 – вхідні потоки даних, ВихПД0 – ВихПДH-1 – вихідні потоки даних, ПК – пам'ять конфігурацій (зберігає конфігурації апаратних засобів ДРМ для реалізації всіх алгоритмів стиску, які будуть виконуватись в БкПОД), КРк – контролер реконфігурування (аналізує службову інформацію потоку даних і вибирає необхідну для обробки цього потоку конфігурацію ПОД, яка зчитується з ПК і завантажується в ДРМ), ДРМ – динамічно реконфігурована матриця (множина апаратних елементів із змінюваною функціональністю, яка забезпечує можливість реалізації різних алгоритмів стиску з високою швидкістю обробки), ПМк – пам'ять мікропрограм (містить набір мікрокоманд для виконання заданого алгоритму, який керує роботою ДРМ залежно від умов, які виникли в процесі обробки потоку даних), ДПОЗП – локальний двопортовий ОЗП даних (зберігає локальні проміжні дані, які виникають у процесі обробки потоків даних).

При плануванні обробки потоків даних ППКПД виконує такі завдання: планування обробки потоків даних згідно з їхніми пріоритетами, які задаються при надходженні потоку на обробку; запобігання переповнення БкКПД проміжними потоками даних; мінімізація простоїв апаратних ресурсів БкПОД, спричинених недостатньою інтенсивністю надходження елементів потоків даних на обробку.

Для виконання цих завдань ППКПД обчислює три незалежні коефіцієнти доцільності обробки (по одному для кожного завдання) для кожного потоку даних і на їхній основі загальний коефіцієнт доцільності відправки потоку даних на обробку в БкПОД.

Розрахунок коефіцієнта доцільності за пріоритетами потоків даних. Пріоритети потоків даних надходять у процесор стиску даних разом із потоками даних і є цілими значеннями, які характеризують терміновість обробки потоків даних. Потоки даних із більшим значенням пріоритетів потребують швидшої обробки, ніж потоки даних із меншими значеннями пріоритетів. Для забезпечення надійної обробки всіх потоків даних, включаючи і низькопріоритетні, враховується час, який витрачався на обробку потоку в БкПОД і розраховується коефіцієнт відповідності затраченого часу на обробку кожного потоку даних до пріоритету цього потоку даних. Потік даних з максимальним значенням цього коефіцієнта (чим більший коефіцієнт від одиниці, тим більша невідповідність затраченого часу до пріоритету цього потоку) відповідності отримає доступ до ресурсів БкПОД. Формула для розрахунку коефіцієнта відповідності затраченого часу на обробку потоку даних до пріоритету цього потоку (коефіцієнта доцільності за пріоритетами потоків даних) має вигляд:

,

де ki – коефіцієнт відповідності затраченого часу на обробку потоку даних до пріоритету цього потоку, pi – пріоритет потоку даних і, L – кількість потоків даних, які знаходяться на обробці в процесорі в даний момент часу, Tei – процесорний час (залежить від кількості процесорів в БкПОД), затрачений на обробку потоку даних і, TTotal – загальний процесорний час (залежить від кількості процесорів в БкПОД), який пройшов від моменту надходження потоку даних і на обробку в процесор.

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

Розрахунок коефіцієнта доцільності за мінімізацією навантаження на БкКПД. Для розрахунку коефіцієнта доцільності за мінімізацією навантаження на БкКПД використовуються розміри потоків даних, які беруть участь в обробці на певному етапі виконання алгоритму (виконанні задачі) та отримуються в результаті виконання цієї задачі. Чим більша різниця розмірів вхідних і вихідних потоків даних певної задачі, тим більшою є доцільність відправки цієї задачі на обробку. Це відображено розрахунком коефіцієнта за формулою (2):

,

де / – сума розмірів всіх вхідних/вихідних потоків даних, які необхідні/отримуються при виконання задачі j при обробці потоку i; K – кількість вхідних потоків даних для виконання задачі j при обробці потоку i; L – кількість вихідних потоків даних в результаті виконання задачі j.

Проте враховувати тільки різницю розмірів вхідних і вихідних потоків даних недостатньо для розрахунку коефіцієнта доцільності за мінімізацією навантаження на БкКПД тому, що не враховується можливе переповнення БкКПД в результаті обробки потоку даних. Тому враховується наступний коефіцієнт:

,

де - розмір вільної області пам'яті в БкКПД;

Коефіцієнт доцільності за мінімізацією навантаження на БкКПД розраховується за наступною формулою:

,

де J – кількість готових до обробки задач потоку i.

Розрахунок коефіцієнта доцільності за мінімізацією простоїв БкПОД. Існує два випадки при надходженні елементів потоку даних на обробку в БкПОД:

1.; 2. ;

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

У першому випадку простоїв апаратних ресурсів БкПОД не буде тому, що елементи даних вхідного потоку надходять швидше, ніж ПОД їх зчитує.

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

,

де NSize – кількість елементів даних у вхідному потоці, N – кількість попередньо накопичених елементів даних вхідного потоку.

З формули (5) випливає наступне співвідношення, яке є умовою відсутності простоїв ПОД:

При виконанні співвідношення (6) потік даних може бути відправлений на обробку без загрози виникнення простоїв ПОД. При невиконанні цього співвідношення на його основі вираховується коефіцієнт доцільності відправки потоку даних на обробку, призначений для мінімізації простоїв ПОД. Отже, коефіцієнт доцільності за мінімізацією простоїв БкПОД розраховується за наступною формулою:

,

де – кількість попередньо накопичених елементів даних підпотоку j потоку i; – загальна кількість елементів даних підпотоку j потоку i.

Розрахунок загального коефіцієнта доцільності відправки потоку даних на обробку. Загальний коефіцієнт доцільності розраховується як добуток трьох його складових частин:

,

Чим більше значення цього коефіцієнта, тим доцільніше відправити задачу на обробку в БкПОД. Отже, ППКПД після розрахунку коефіцієнтів для всіх завдань, готових до обробки, вибирає завдання з найбільшим розрахованим значенням і відправляє її на обробку в БкПОД. Низькопріоритетні завдання при цьому не будуть “зависати” в процесорі тому, що з часом їх загальний коефіцієнт доцільності буде зростати за рахунок зростання значення коефіцієнта .

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

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

Таблиця – Характеристика моделі алгоритму стиску

Назва характеристики | Значення

Кількість незалежних етапів обробки потоку даних | 4

Кількість незалежних завдань, з яких складається алгоритм | 601

Кількість вхідних потоків/підпотоків даних для 1-ого етапу обробки | 1

Кількість вихідних підпотоків даних 1-ого етапу обробки | 200

Кількість вхідних підпотоків даних для 2-ого етапу обробки | 1

Кількість вихідних підпотоків даних 2-ого етапу обробки | 1

Кількість вхідних підпотоків даних для 3-ого етапу обробки | 1

Кількість вихідних підпотоків даних 3-ого етапу обробки | 1

Кількість вхідних підпотоків даних для 4-ого етапу обробки | 1

Кількість вихідних підпотоків даних 4-ого етапу обробки | 1

Рис. – Залежність часу обробки потоку даних від кількості процесорів обробки даних

З рис.4 видно, що при 50-ти процесорах обробки даних досягається час обробки, близький до мінімального. Подальше збільшення кількості процесорів для приведеної моделі алгоритму та використаної моделі потоку даних не призведе до зменшення часу обробки. Нелінійність зменшення часу обробки від кількості процесорів пояснюється тим, що не всі процесори обробки даних можуть бути задіяні від початку обробки, оскільки спочатку на обробку надходить один вхідний потік даних, а через деякий час (час обробки частини вхідного потоку до отримання першого проміжного потоку) поступово формуються проміжні підпотоки даних, які й починають використовувати незадіяні ПОД. У випадку одночасної обробки багатьох потоків даних, які будуть завантажувати більшу кількість ПОД, залежність часу обробки від кількості ПОД буде наближатись до лінійної. Крім цього, при паралельній обробці більшої кількості потоків даних збільшення кількості ПОД призведе до зростання продуктивності процесора.

Запропонована модель ППКПД планує обробку потоків даних таким чином, щоб співвідношення часу доступу до апаратних ресурсів процесора для різних потоків даних відповідало співвідношенню їхніх пріоритетів. Для дослідження процесів доступу потоків даних до апаратних ресурсів процесора було використано модель алгоритму стиску даних, описану в таблиці 1, та моделі трьох потоків даних із різними пріоритетами. Характеристики моделей потоків даних та результати моделювання зображено в таблиці 2.

Таблиця - Характеристики потоків даних та результати моделювання процесів доступу потоків даних до апаратних ресурсів процесора

№ потоку даних | Пріоритет потоку даних | Середнє значення частки процесорного часу, виділеного для обробки потоку даних

1 | 10 | 0.02

2 | 200 | 0.28

3 | 500 | 0.70

На рис.5 зображено динамічний процес виділення апаратних ресурсів процесора потокам даних під час їх обробки.

Рис. - Процес виділення доступу до багатоканального процесора обробки даних потокам даних під час їхньої обробки

З рис.5 видно, що ППКПД утримує середній час доступу потоків даних до БкПОД у відповідності до співвідношення пріоритетів цих потоків даних. В результаті цього, середня частка доступу потоків даних до БкПОД здійснює коливання навколо свого середнього значення.

На рис.6(a) зображено співвідношення пріоритетів потоків даних, а на рис.6(b) -співвідношення часток доступу цих потоків даних до апаратних ресурсів БкПОД.

Рис. – Співвідношення між пріоритетами потоків даних (а); Співвідношення часток доступу потоків даних до багатоканального процесора обробки даних (b)

З рис.6(a та b) видно, що частка доступу потоків даних до БкПОД відповідає частці пріоритетів цих потоків даних по відношенню до пріоритетів всіх потоків даних, які знаходяться на обробці в процесорі. Отже, ППКПД планує доступ потоків даних до БкПОД у відповідності з призначеними пріоритетами потоків даних.

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

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

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ

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

1.

2.

3.

4.

5.

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Мельник А., Бачинський Р. Процесори стиску даних з плаваючим вікном буфера попередньо збережених даних // Вісник Національного університету “Львівська політехніка” : “Комп’ютерні системи та мережі”.-2004, №523.–С. 98-101.

2. Бачинський Р. Вибір структури процесора стиску зображень для типових алгоритмів // Вісник Національного університету “Львівська політехніка” “Комп’ютерні науки та інформаційні технології”.-2006.-№565.–С. 3-8.

3. Бачинський Р. Апаратні засоби реалізації алгоритмів стиску даних // Моделювання в енергетиці. Національна академія наук України. Збірник наукових праць. Вип. 34 - К., . – С. 116-122.

4. Бачинський Р. Багатоканальна пам'ять для процесорів стиску даних // Моделювання в енергетиці. Національна академія наук України. Збірник наукових праць. Вип.. 38 - К., . – С. 168-173.

5. Бачинський Р. Конфігурований процесор стиску даних // Моделювання в енергетиці. Національна академія наук України. Збірник наукових праць. Вип. 39 - К., . – С. 125-131.

6. Бачинський Р. Конфігурований багатоканальний контролер потоків даних // Моделювання та інформаційні технології. Національна академія наук України. Збірник наукових праць. Вип. 40 - К., . – С. 138-145.

7. Бачинський Р. Процесор обробки потоків даних для паралельних потокових процесорів стиску даних // Моделювання в енергетиці. Національна академія наук України. Збірник наукових праць. Вип. 41 - К., . – С. 174-178.

8. Бачинський Р. Пристрій планування та керування обробкою потоків даних для процесорів стискання даних // Комп’ютерні технології друкарства. Українська академія друкарства. Збірник наукових праць. Вип. 17.-Львів, . – С. 113-119.

9. Melnyk A., Bachinsky R. Compression system architecture based on Lempel-Ziv algorithm with sliding window history buffer // Сучасні проблеми радіоелектроніки, телекомунікацій, комп’ютерної інженерії – TCSET’2004. Матеріали міжнародної конференції TCSET’2004. Львів-Славсько, Україна, 24-28 лютого 2004. – С. 203-205.

10. Бачинський Р. Особливості побудови процесорів стискання даних // Збірник матеріалів міжвузівської науково-технічної конференції науково-педагогічних працівників. Львів, 21 - 22 березня 2006р. – С. 186-187.

11. Бачинський Р. Процесор стиску даних // Моделювання. Матеріали 16-ї науково-технічної конференції. Київ, 12 - 13 січня 2007р. – С. 73-74.

12. Бачинський Р. Процесор обробки потоків даних для процесорів стиску даних // Комп’ютерний моніторинг та інформаційні технології. Матеріали 3-ї міжнародної наукової конференції студентів, аспірантів і молодих вчених. Донецьк, 22 - 23 травня 2007р.

13. Бачинський Р. Багатоканальний контролер потоків даних для процесорів стиску даних // Сучасні проблеми радіоелектроніки, телекомунікацій та приладобудування – СПРТП-2007. Матеріали 3-ї міжнародної науково-технічної конференції. Вінниця, 31 травня - 2 червня 2007р. – С. 164-165.

14. Bachynskyy R. Data streams processing planning and controlling for multichannel data compression processors // Сучасні комп’ютерні системи та мережі: розробка та використання – ACSN-2007. Матеріали 3-ї міжнародної науково-технічної конференції. Львів, 20-22 вересня 2007 р. – с. 50-52.

15. Бачинський Р. Принципи планування обробки потоків даних в паралельних потокових процесорах // Комп’ютерні науки та інженерія – CSE-2007. Матеріали 2-ї міжнародної наукової конференції молодих науковців. Львів, 4-6 жовтня 2007 р. – с. 76-77.

АНОТАЦІЯ

Бачинський Р.В. Реконфігуровані процесори стиску потоків даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 – комп’ютерні системи та компоненти. – Національний університет “Львівська політехніка”, Львів, 2007.

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

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

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

АННОТАЦИЯ

Бачинский Р.В. Реконфигурированные процессоры сжатия потоков данных. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 – компьютерные системы и компоненты. – Национальный университет “Львовская политехника”, Львов, 2008.

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

Ключевые слова: алгоритмы сжатия данных, процессоры сжатия данных, параллельные вычисления, потоки данных, компьютерные системы, системы на кристалле.

ABSTRACT

Bachynskyy R.V. Reconfigurable data streams compression processors. – Manuscript.

Thesis for the Ph.D. (candidate of science) degree