Міністерство освіти і науки України

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

УДК 681.3

Ерметов Юрій Олегович

КОНВЕЄРНІ ПРОЦЕСОРИ ШВИДКИХ ОРТОГОНАЛЬНИХ

ПЕРЕТВОРЕНЬ З ДІЙСНИМИ ФАЗОВИМИ МНОЖНИКАМИ

Спеціальність 05.13.13 – Обчислювальні машини, системи і мережі

Автореферат

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

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

Львів - 2000

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

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

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

Мельник Анатолій Олексійович,

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

завідувач кафедри електронних обчислювальних машин

Офіційні опоненти: доктор технічних наук, професор

Грицьків Зенон Дмитрович,

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

завідувач кафедри радіотехнічних пристроїв, м. Львів;

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

Дунець Роман Богданович

Українська академія друкарства,

кафедра автоматизації і комп’ютерних технологій, м. Львів.

Провідна установа: Національний технічний університет України “Київський

політехнічний інститут”, м. Київ

Захист відбудеться “23” грудня 2000 р. о “11” год. на засіданні спеціалізованої вченої ради Д35.052.05 при Національному університеті “Львівська Політехніка” в ауд. 226 головного корпусу за адресою 79646, м. Львів_, вул. С.Бандери, 12.

З дисертацією можна ознайомитися у науково-технічній бібліотеці Національного університету “Львівська Політехніка” за адресою: 79646, м. Львів, вул. Професорська,1.

Автореферат розісланий “22” листопада 2000 р.

Вчений секретар

спеціалізованої вченої ради,

кандидат технічних наук, доцент С.П.Ткаченко

Загальна ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми.

Ортогональні тригонометричні перетворення (ОТП) є математичною основою для багатьох процедур цифрової обробки сигналів та зображень. Найширше застосування ОТП отримали для частотного опису сигналів та систем та наближенного подання (апроксимації) сигналів. Серед них до найбільш широко використовуваних відносяться дискретні перетворення Фур‘є та Хартлі, синусне та косинусне перетворення. Крім того, для вирішення задач стиснення інформації широке використовується дискретне хвильове перетворення.

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Вибраний напрямок досліджень пов’язаний з виконанням робіт в рамках пріоритетних наукових напрямків Міністерства освіти та науки України 07-“Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв’язку” та 01-“Охорона навколишнього природного середовища” по темах, які проводились та проводяться в даний час на кафедрі електронних обчислювальних машин та в науково-дослідному конструкторському інституті НДКІ ЕЛВІТ Національного університету “Львівська політехніка:

- ДБ “СЕРГ”: “Розробка метрологічних основ та принципів побудови вимірювально-обчислювальних комплексів для забезпечення сертифікаційних випробувань автотранспортних засобів” (1998-1999 рр.);

- ДБ/17.ЕС: ”Розробка нових принципів побудови вимірювально-обчислювальних мереж з елементами самоорганізації для екологічного моніторингу” (2000-2001 рр.).

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

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

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

- вдосконалення існуючих та розробка нових алгоритмів обчислення ШОП з дійсними фазовими множниками;

- розробка структур конвеєрних процесорів ШОП з дійсними фазовими множниками та порівняння їх з конвеєрними процесорами ШОП за методом Кулі-Тьюкі;

- розробка структур конвеєрних процесорів дискретного хвильового перетворення (ДХП), а також структур багатофункціональних конвеєрних процесорів ШОП та ДХП;

- розробка паралельного конвеєрного процесора оберненого швидкого косинусного перетворення та реалізація його на основі ПЛІС фірми Xilinx.

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

Наукова новизна роботи:

- удосконалено алгоритми обчислення швидкого косинусного перетворення (ШКП), швидкого перетворення Фур‘є (ШПФ) та швидкого перетворення Хартлі (ШПФ) з дійсними фазовими множниками, що дозволяє розробляти структури конвеєрних процесорів з мінімальними затратами обладнання;

- розроблено нові паралельні алгоритми прямого та оберненого ШКП, які характеризуються гранично високою швидкістю отримання результатів;

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

- розроблено нові структури конвеєрних процесорів ШПФ та ШПХ з дійсними фазовими множниками та здійснено їх порівняльний аналіз з конвеєрними процесорами ШПФ та ШПХ на основі методу Кулі-Тьюкі, який показав перевагу використання алгоритмів ШПФ та ШПХ з дійсними фазовими множниками з точки зору затрат обладнання при невеликих та середніх розмірах перетворень;

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

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

- розроблені нові алгоритми паралельного обчислення прямого та оберненого ШКП дозволяють підвищити продуктивність обчислення цих перетворень в багатопроцесорних універсальних комп‘ютерних системах та паралельних спеціалізованих комп‘ютерних системах;

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

- розроблена методика побудови багатоканальних конвеєрних процесорів прямого та оберненого ШКП створює базу для автоматизованої розробки конвеєрних процесорів з мінімальними затратами обладнання на їх реалізацію при забезпеченні заданої продуктивності;

- розроблений паралельний 8-канальний конвеєрний процесор одновимірного 8-точкового оберненого ШКП дозволяє будувати високопродуктивні системи стиснення аудіо та відео інформації, які базуються на стандартах JPEG, MPEG, H.261 та інш.

Впровадження результатів роботи. Розроблені в дисертаційній роботі методи та алгоритми впроваджені:

-

-

-

Особистий внесок здобувача. Основний зміст роботи, всі теоретичні та практичні розробки, висновки і рекомендації виконані автором особисто. В друкованих працях, опублікованих в співавторстві, здобувачу належать: [2] – розробка та аналіз структур двоканальних конвеєрних процесора ШКП; [3] – розробка структур конвеєрних процесорів ШПФ з дійсними фазовими множниками; [4] – розробка нового паралельного алгоритму ШКП та методики проектування багатоканальних конвеєрних процесорів ШКП; [5] – розробка принципів організації бібліотек стандартних елементів; [8] – розробка функціональної схеми паралельного процесора двовимірного ШКП.

Апробація результатів дисертації. Основні положення й результати дисертаційної роботи доповідались й обговорювались на таких конференціях: міжнародна науково-технічна конференція “Сучасні проблеми засобів телекомунікацій, компютерної інженерії та підготовки спеціалістів” TSCET’98, 1998 (м.Славське, Україна); 5-та міжнародна науково-технічна конференція "Досвід розробки і застосування приладо-технологічних САПР мікроелектроніки" CADSM'99, 1999 (с.Славське, Україна); International Conference on Modern Problems of Telecommunications, Computer Science and Engineers Training TCSET'2000, 2000 (Lviv-Slavsko, Ukraine).

Публікації. Основний зміст дисертаційної роботи опублікований в 7 друкованих працях загальним обсягом 42 сторінки , з яких 1 _ одноосібна, в тому числі 4 наукових статей (з яких 3 _ у фахових виданнях), 3 _ матеріали і тези доповідей на конференціях.

Структура та обсяг роботи. Дисертаційна робота складається зі вступу і п‘яти розділів, висновку, списку літературних джерел з 132 найменувань і додатків. Зміст роботи викладено на 144 сторінках, включаючи 121 рисунок та 10 таблиць. У додатках наведено тексти вихідних кодів розробленого програмного забезпечення та роздрук машинного представлення результатів його роботи.

ЗМІСТ ДИСЕРТАЦІЇ

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

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

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

Окрім основної структури МП алгоритму ШКП, оптимізованого за переміщенням даних (ШКП1), існують інші cтруктури, які відрізняються принципом перестановки даних між ярусами МП. До них відносяться структура МП, яка відповідає початковій формулі розкладу алгоритму ШКП (ШКП2), та структура з перестановкою даних алгоритму ШПФ (ШКП3).

МП складається з log2N ярусів, на кожному з яких розташовано N/2 незалежних базових операцій (БО). Тому для паралельного обчислення МП достатньо реалізувати відповідну кількість пристроїв БО (ПБО).

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

Існує декілька структур МК алгоритму ШКП, які відрізняються методом перестановки даних. Початковій формулі розкладу алгоритму ШКП відповідає структура МК з проміжною перестановкою даних, в якій перестановка даних здійснюється після кожного яруса. Відома структуру МК, в якій перестановка даних відбувається перед кожним ярусом МК. Також існує структура МК з попередньою перестановкою даних, в якій перестановка даних здійснюється перед всіма ярусами МК. В дисертаційній роботі синтезовано нову структуру МК зі змішаною перестановкою даних, в якій перестановка N елементів може бути розміщена після i-го яруса (рис.1). Нова структура МК дозволяє значно зменшити затрати обладнання при апаратній реалізації МК.

Рис.1. Структура направленого графа МК зі змішаною перестановкою даних для N=16

Часова затримка паралельного обчислення МК визначається кількістю БО у найбільшій НБО:

. (2)

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

Рис.2. Структура направленого графа МК на основі бінарних дерев

з проміжною перестановкою даних

Назвемо МК на основі бінарних дерев з проміжною перестановкою даних бінарною МК на основі сортувальної пам‘яті (СП-МК), а з попередньою перестановкою даних – бінарною МК на основі пам‘яті типу FIFO (FIFO-МК).

Загальна кількість БО в бінарних МК дорівнює:

, (3)

що в разів більше в порівнянні з послідовною МК.

Часова затримка обчислення МК

, (4)

що в разів менше в порівнянні з послідовною МК.

Таким чином, за рахунок збільшення обчислювальних затрат досягнуто зменшення затримки паралельного обчислення МК.

З метою максимального зменшення часових затрат та затрат обладнання при паралельних обчисленнях в дисертаційній роботі розроблено нові паралельні алгоритми обчислення МК прямого та оберненого ШКП, структуру яких показано на рис.3 та рис.4.

Рис.3. Структура направленого графа паралельної МК прямого ШКП

Рис.4. Структура направленого графа паралельної МК оберненого ШКП

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

Часова затримка обчислення визначається кількістю ярусів:

, (5)

що в разів менше в порівнянні з алгоритмом з послідовною схемою обчислень НБО і в разів менше в порівнянні з бінарними алгоритмами з паралельною схемою обчислень НБО.

Нові алгоритми обчислення МК дозволяють без додаткових обчислювальних затрат максимально скоротити затримку паралельного обчислення МК.

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

Згідно існуючої методики проектування спеціалізованих комп‘ютерних засобів для побудови КП алгоритму ШКП кожному ярусу МП відповідає сортувальна пам‘ять (СП), пристрій базової операції (ПБО) та пристрій управління. Внаслідок подібності структури МП до структури алгоритму ШПФ питання побудови одно- та двоканальних КП МП алгоритму ШКП є достатньо дослідженим. В дисертаційній роботі з врахуванням особливостей алгоритмів перестановки даних в структурах ШКП1, ШКП2 та ШКП3 розроблено нові багатоканальні структури СП, оптимізовані за затратами обладнання за рахунок спрощення m-входових комутаторів та зменшення кількості адресних мультиплексорів.

Окрім існуючоюї структури конвеєрного процесора МК (КПМК) на основі СП в дисертаційній роботі розроблено три нових підходи до побудови конвеєрних процесорів МК: 1) на основі пам‘яті FIFO; 2) на основі СП та пам‘яті FIFO; 3) на основі паралельного алгоритму.

Існуючу структуру КПМК на основі СП, яка базується на реалізації структури МК з проміжною перестановкою даних, показано на рис.5а. На основі реалізації структури МК з попередньою перестановкою даних в дисертаційній роботі синтезовано нову структуру КПМК на основі пам‘яті FIFO (рис.5б), в якій в порівнянні зі структурою КПМК на основі СП досягнуто скорочення затрат обладнання на релізацію пам‘яті на 25%. Оскільки затрати обладнання на реалізацію накопичуючого пристрою БО (НПБО) та пам‘яті мають відповідно логарифмічну та лінійну залежність від розміру перетворення N, то із збільшенням розміру перетворення затрати обладнання на реалізацію пам‘яті вносять визначальний вклад в загальні затрати обладнання на реалізацію КП.

а б

Рис.5. Структури КПМК: а - на основі СП; б – на основі пам‘яті FIFO

Оскільки в КПМК на основі СП зі збільшенням номера яруса розмір пам‘яті зростає, а в КПМК на основі пам‘яті FIFO зменшується, то оптимальним з точки зору затрат обладнання на реалізацію пам‘яті буде КПМК, в якому СП об‘єму N буде розміщено на ярусі . Синтез нової структури оптимізованого КПМК на основі СП та пам‘яті FIFO базується на реалізації нової структури МК зі змішаною перестановкою даних (рис.1). В КПМК на основі СП та пам‘яті FIFO (рис.6) досягнуто скорочення затрат обладнання на реалізацію пам‘яті в 2 рази в порівнянні з КПМК на основі СП і в 1,5 рази в порівнянні з КПМК на основі пам‘яті FIFO.

Рис.6. Структура оптимізованого КПМК на основі СП та пам‘яті FIFO

На рис.7 показано структуру КПМК на основі нового паралельного алгоритма ШКП, затрати обладнання на реалізацію якої при невеликій кількості каналів дорівнюють затратам обладнання на реалізацію структури КПМК на основі СП.

Рис.7 Структура КПМК на основі паралельного алгоритму

При побудові паралельних КП з кількістю каналів N на основі різних алгоритмів обчислення МК кількість ПБО визначається обчислювальними затратами відповідної МК і дорівнює кількості БО у цій МК, а кількість конвеєрних регістрів є пропорційною часовій затримці обчислення МК, тобто кількості ярусів відповідної МК. При паралельному обчисленні МК всі перестановки даних здійснюються відповідними з‘єднаннями входів та виходів сусідніх ярусів і, відповідно, зникає потреба у СП. Відповідно найменшими затратами обладнання характеризуються паралельні КП, побудовані на основі нового паралельного алгоритма ШКП.

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

Для великих розмірів перетворення та відносно невеликої кількості каналів m, при яких затрати обладнання на реалізацію ярусів у FIFO-МК менші в порівнянні з паралельною МК, можна застосувати метод оптимізації по аналогії з одноканальними КП. Якщо в бінарній FIFO-МК двійково-інверсну СП об‘ємом N розмістити на ярусі , то зліва від СП отримаємо яруси зі структурою бінарної СП-МК, а справа - яруси зі структурою бінарної FIFO-МК. Реалізувавши яруси зі структурою бінарної СП-МК на основі паралельної МК, отримуємо оптимальну за затратами обладнання структуру БКП МК. Крім того, якщо існують яруси зі структурою бінарної FIFO-МК, затрати обладнання на реалізацію яких для БКП на основі паралельної МК менші в порівнянні з БКП на основі бінарної FIFO-МК, то двійково-інверсну СП об‘єму N необхідно перемістити на відповідний ярус другої групи. При цьому перед ярусами першої групи необхідно розмістити двійково-інверсну СП об‘ємом , затрати на яку повинні бути меншими в порівнянні з отриманим виграшем у затратах обладнання від переміщення основної СП об‘ємом N. При збільшенні розміру перетворення значення затрат обладнання оптимального БКП становить 50% в порівнянні з БКП на основі паралельної МК і 67% в порівнянні з БКП на основі бінарної FIFO-МК.

При невеликих розмірів перетворення, для яких найменшими затратами обладнання характеризуються БКП на основі паралельної МК, структуру оптимального БКП необхідно будувати на основі паралельної МК. При зростанні кількості каналів m для , для яких найменшими затратами обладнання характеризуються БКП на основі бінарної СП-МК, структуру оптимального БКП необхідно будувати на основі бінарної СП-МК. Для , для яких найменшими затрати обладнання характеризуються БКП на основі паралельної МК, структуру оптимального БКП необхідно будувати на основі паралельної МК.

Запропонована методика дозволяє отримувати структури багатоканальних КП МК з мінімальними затратами обладнання на їх реалізацію.

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

Питання побудови КП алгоритмів ШПФ за методом Кулі-Тьюкі (ШПФКТ) достатньо широко освітлене в існуючій літературі.

Направлений граф оптимізованого в дисертаційній роботі алгоритму ШПФ з дійсними фазовими множниками (ШПФДФМ), показано на рис.8.

а

б

Рис.8. Структура направленого графа алгоритму ШПФДФМ для N=16:

а – матриця коригування; б – матрия перетворень

Алгоритм складається з МК та МП. МП має подібну до алгоритму ШПФКТ структуру за винятком дійсних замість комплексних фазових множників та БО, позначених на рис.7б чорним кольором, в яких використовуються коригуючі коефіцієнти q. В алгоритмі ШПФДФМ дійсна структура фазових множників дозволяє в 2 рази скоротити кількість перемножувачів та в 1,5 рази – кількість суматорів для реалізації МП, проте з‘явилась необхідність побудови КП для реалізації МК.

Окрім трьох суматорів структура ПБО МК вимагає використання пам‘яті FIFO для обчислення коригуючих коефіцієнтів q. Передача коефіцієнтів q здійснюється в загальному потоці даних на місці елементів послідовності, що дорівнюють нулю.

На рис.9 показано синтезовану структуру КП МП. Вона ідентична структурі КП алгоритму ШПФКТ за винятком тракту передачі значень q. На цьому тракті пам‘ять FIFO створює затримку, яка дорівнює затримці основного тракту.

Рис.9. Структура КП МП алгоритму ШПФДФМ

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

Аналіз затрат обладнання на реалізацію структур КП алгоритмів ШПФ та ШПХ показав, що при невеликих та середніх розмірах перетворення найбільший внесок у загальні затрати обладнання вносять перемножувачі, тому в цьому випадку менші апаратні затрати матимуть КП алгоритмів ПФ та ШПХ з дійсними фазовими множниками, при чому діапазон цих розмірів перетворень для швидкого перетворення Хартлі є більшим. Із збільшенням розміру перетворення зростає питома вага затрат обладнання на реалізацію пам‘яті, що обумовлює великі затрати обладнання на реалізацію МК в алгоритмах ШПФ та ШПХ з дійсними фазовими множниками. Тому при великих розмірах перетворення доцільно за затратами обладнання використовувати алгоритми ШПФ та ШПХ за методом Кулі-Тьюкі.

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

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

В результаті аналіза структур КП алгоритму ШПХ з дійсними фазовими множниками показано, що на основі КП МК можна реалізувати пряме ДХП, а на основі КП МП – обернене ДХП. В дисертаційній роботі розроблено структуру КП, яка дозволяє здійснювати обчислення алгоритмів ШПХ з дійсними фазовими множниками та прямого і оберненого ДХП без значних додаткових затрат обладнання. Дослідження показали, що при великих розмірах перетворення затрати обладнання КП ШПХ-ДПХ прямують до значення однакового із затратами обладнання КП ШПХРБ і в 2 рази меншого від суми затрат обладнання КП ШПХРБ та прямого та оберненого ДХП.

У п‘ятому розділі з метою апробації та експериментального підтвердження результатів теоретичних досліджень попередніх розділів на основі нового паралельного алгоритма оберненого ШКП (ОШКП) розроблено паралельний 8-канальний конвеєрний процесор алгоритму 8-точкового ОШКП. Для реалізації множень на константи розроблено спеціалізовані перемножувачі, що дозволило скоротити затрати обладнання в порівнянні з універсальними перемножувачами в 4 рази. Створено VHDL-модель паралельного процесора, на основі якої паралельний процесор реалізовано на основі ПЛІС фірми Xilinx з використанням пакету автоматизованого проектування Xilinx Foundation 2.1. Засобами цього пакету виконано симуляцію роботи паралельного процесора та перевірку точності обчислень на основі тестових послідовностей. За точністними параметрами паралельний процесор відповідає стандартам JPEG, MPEG та H.261 стиску сигналів та зображень. Отримані в результаті проектування ПЛІС значення затрат обладнання та швидкодії є найкращими серед існуючих паралельних процесорів ОШКП. Розроблений процесор може бути основою для розробки 8-канального конвеєрного процесора алгоритму двовимірного ШКП.

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

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

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

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

3) проаналізовано існуючі та розроблено ряд нових структур одно-, дво-, багатоканальних та паралельних конвеєрних процесорів прямого та оберненого швидкого косинусного перетворення. На їх основі розроблено методику проектування багатоканальних конвеєрних процесорів швидкого косинусного перетворення, яка дозволяє отримувати структури конвеєрних процесорів з мінімальними затратами обладнання;

4) розроблено нові структури конвеєрних процесорів швидкого перетворення Фур‘є та швидкого перетворенння Хартлі з дійсними фазовими множниками, здійснено їх порівняння з конвеєрними процесорами цих перетворень за методом Кулі-Тьюкі; показано, що при невеликих та середніх розмірах перетворення за затратами обладнання доцільно використовувати алгоритми ШПФ та ШПХ з дійсними фазовими множниками.

5) розроблено нові структури конвеєрних процесорів прямого та оберненого дискретного хвильового перетворення, багатофункціональних процесорів для виконання прямого та оберненого дискретного хвильового перетворення, а також багатофункціональних конвеєрних процесорів для виконанння швидкого перетворення Хартлі та прямого та оберненого дискретного хвильового перетворення, що дозволяє здійснювати проектування спеціалізованих комп‘ютерних засобів для реалізації цих перетворень з мінімальними затратами обладнання;

6) розроблено 8-канальний паралельний конвеєрний процесор 8-точкового оберненого швидкого косинусного перетворення. Розроблено VHDL-модель процесора, на основі якої процесор промодельовано та відтестовано. Розроблений процесор реалізовано на ПЛІС фірми Xilinx засобами пакету автоматизованого проектування Xilinx Foundation 2.1. Отримані в результаті проектування ПЛІС значення затрат обладнання та швидкодії є найкращими серед існуючих паралельних процесорів ОШКП.

Список праць за темою дисертації

1. Ерметов Ю.О. "Синтез конвеєрних пристроїв для реалізації матриці коригування в алгоритмі швидкого косинусного перетворення", Вісник Державного університету “Львівська Політехніка” "Комп‘ютерні системи проектування. Теорія і практика", №373, 1999, с.128-136.

2. Мельник А.О., Ерметов Ю.О. “Розробка двоканальних конвеєрних пристроїв для реалізації матриці коригування в алгоритмі швидкого косинусного перетворення”, Вісник Державного університету “Львівська Політехніка” “Комп‘ютерна інженерія та інформаційні технології”, №370, 1999, с.28-34.

3. Ерметов Ю.О., Мороз І.В. Конвеєрні пристрої швидкого перетворення Фур‘є за методом Рейдера-Бреннера. Вісник Державного університету “Львівська Політехніка” “Комп’ютерна інженерія та інформаційні технології”, № 386, 1999, с.11-18.

4. Мельник А.О., Ерметов Ю.О. “Багатоканальна конвеєрна реалізація матриці коригування в алгоритмі швидкого косинусного перетворення”, збірник наукових праць симпозіуму “Сучасні проблеми в комп‘ютерних науках” (CCU’2000), 2000, cc.89-100 (с.Славське, Україна).

5. Мельник А.О., Ерметов Ю.О. “Засоби пpоектування спеціалізованих НВІС від алгоpитмічного опису задачі до pівня міжpегістpових пеpедач”. Тези доп. на міжнародній НТК "Сучасні проблеми засобів телекомунікації, комп‘ютерної інженерії та підготовки спеціалістів" TCSET`98, 1998, с.108 (с.Славське, Україна).

6. Ерметов Ю.О. Синтез конвейєрних пристроїв для реалізації матриці коригування в алгоритмі швидкого косинусного перетворення. Тези доп. на 5-й міжнародній НТК "Досвід розробки та застосування приладо-технологічних САПР мікроелектроніки", 1999, с.149-151, (с.Славське, Україна).

7. "Two-Dimensional 8x8 Discrete Cosine Transform Parallel Processor". Proceedings of International Conference on Modern Problems of Telecommunications, Computer Science and Engineers Training TCSET'2000, 2000, p.101 (Lviv-Slavsko, Ukraine).

Анотація

Ерметов Ю.О. Конвеєрні процесори швидких ортогональних перетворень з дійсними фазовими множниками. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.13 – Обчислювальні машини, системи та мережі. – Національний університет “Львівська Політехніка”, Львів, 2000.

Дисертація присвячена питанням розробки нових та удосконалення існуючих алгоритмів обчислення швидких ортогональних перетворень з дійсними фазовими множниками та розробки на їх основі спеціалізованих конвеєрних процесорів для реалізації цих перетворень. В дисертації розроблено нові паралельні алгоритми прямого та оберненого швидкого косинусного перетворення, які дозволяють здійснювати паралельне обчислення цих перетворень без надлишкових затрат обладнання. Розроблено методику проектування одно-, дво-, багатоканальних та паралельних конвеєрних процесорів швидкого косинусного перетворення з мінімальними затратами обладнання. Вдосконалено існуючі алгоритми обчислення швидких перетворень Фур‘є та Хартлі з дійсними фазовими множниками і на їх основі розроблено структури конвеєрних процесорів для реалізації цих перетворень. Показано, що при невеликих та середніх розмірах перетворень використання швидких ортогональних перетворень з дійсними фазовими множниками є ефективнішим в порівнянні з перетвореннями за методом Кулі-Тьюкі. Розроблено структури конвеєрних процесорів для реалізації прямого та оберненого дискретного хвильового перетворення, а також запропоновано структуру багатофункціонального конвеєрного процесора для спільного виконанння дискретного хвильового перетворення та швидкого перетворення Хартлі з дійсними фазовими множниками, що дозволило значно скоротити затрати обладнання на реалізацію цих перетворень. На основі нового паралелельного алгоритма швидкого косинусного перетворення розроблено VHDL-модель 8-канального конвеєрного процесора 8-точкового оберненого швидкого косинусного перетворення, яку реалізовано на основі ПЛІС фірми Xilinx. Затрати обладнання та швидкодія розроблненого процесора є найкращими серед існуючих паралельних процесорів оберненого швидкого косинусного перетворення. Основні результати дисертації впроваджені в НДР ДБ “СЕРГ” та ДБ/17.ЕС, які проводилися в Державному університеті “Львівська політехніка”, а також в навчальному процесі кафедри ЕОМ Державного університету “Львівська політехніка”.

Аннотация

Эрметов Ю.О. Конвейерные процессоры быстрых ортогональных преобразований с действительными фазовыми множителями. – Рукопись.

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.13 – Вычислительные машины, системы и сети. – Национальный университет “Львовская политехника”, Львов, 2000.

Диссертация посвящена вопросам разработки новых и усовершенствования существующих алгоритмов вычисления быстрых ортогональных преобразований с действительными фазовыми множителями и разработки на их основе специализированных конвейерных процессоров для реализации этих преобразований. В диссертации разработаны новые параллельные алгоритмы прямого и обратного быстрого косинусного преобразования, которые позволяют осуществлять параллельные вычисления этих преобразований без избыточных затрат оборудования. Разработана методика проектирования одно-, дво-, многоканальных и параллельных конвейерных процессоров быстрого косинусного преобразования с минимальными затратами оборудования. Усовершенствованы существующие алгоритмы вычисления быстрых преобразований Фурье и Хартли с действительными фазовыми множителями и на их основе разработаны структуры конвейерных процессоров для реализации этих преобразований. Показано, что при небольших и средних размерах преобразований использование быстрых ортогональных преобразований с действительными фазовыми множителями является более эффективным по сравнению с преобразованиями на основе метода Кули-Тьюки. Разработаны структуры конвейерных процессоров для реализации прямого и обратного дискретного волнового преобразования, а также предложена структура многофункционального конвейерного процессора для выполненния дискретного волнового преобразования и быстрого преобразования Хартли с действительными фазовыми множителями, что позволило значительно сократить затраты оборудования на реализацию єтих преобразований. На основе нового паралелельного алгоритма быстрого косинусного преобразования разработана VHDL-модель 8-канального конвейерного процессора 8-точкового обратного быстрого косинусного преобразования, которая реализована на основе ПЛИС фирмы Xilinx. Затраты оборудования и быстродействие разработанного процессора являются лучшими среди существующих параллельных процессоров обратного быстрого косинусного преобразования. Основные результаты диссертации внедрены в НИР ДБ “СЕРГ” и ДБ/17.ЕС, которые проводились в Национальном университете “Львовская политехника”, а также в учебном процессе кафедры ЭВМ Национального университета “Львовская политехника”.

Abstract

Ermetov Y.O. Pipeline processors of the real-factor fast orthogonal transforms. - Manuscript.

Thesis for the Degree of Doctor of Philosophy in Computer Science in speciality 05.13.13 – Computing machines, systems and networks. – National Lviv Polytechnic University, Lviv, 2000.

The thesis deals with development of the new algorithms of the real-factor fast orthogonal transforms (FOT) and engineering of the pipeline processors for their implementation. Instead of popular Cooley-Tukey FOT (CTFOT) real-factor FOT (RFFOT) proposed by Rader and Brenner features simpler basic operations but requires additional adding operations.

Among all of the RFFOT the fast cosine transform (FCT) is the most representative. It consists of two parts: transforming matrix (TM) and correcting matrix (CM). The structure of TM is similar to the structure of Cooley-Tukey FFT algorithm. Thus pipeline implementation of the TM has been researched enough whereas implementation of the CM is practically unknown. The main peculiarity of CM is recursive structure of the basic adding operations. Sequential nature of these operations is convenient for one-channel iterative and pipeline implementations but results in large timing latency or requires significant additional hardware in multichannel cases. With the purpose to reduce hardware and timing penalties a new algorithm for parallel CM computation had been developed featuring the same number of independent parallel basic operations (BO) instead of sequential BOs of the usual FCT algorithm. The new parallel algorithm had been also developed for the inverse FCT with the same results of reducing hardware and timing penalties.

In the thesis development of the one-, two-, multichannel and parallel pipeline processors for the FCT implementation is considered. As processors with a few channels for TM implementation are investigated enough so development of the multichannel TM processors is considered. For TM implementation optimised structures of the multichannel sorting memories are developed. For CM implementation four basic structures of pipeline processors are considered. They are based on existing FCT algorithms and new parallel FCT algorithm developed in this thesis. Considering advantages and drawbacks of all structures the generalized methodics of multichannel pipeline CM processors engineering is developed which allows to design processors with minimum hardware expenditures

Fast Fourier transform (FFT) algorithm with real-factor coefficients has simpler significantly basic operation structure comparing to Cooley-Tukey FFT algorithm with complex coefficients but similar to FCT algorithm requires additional CM unit. Although usual fast Hartley transform (FHT) deals with real coefficients but real-factor FHT algorithms simplifies basic operation structure significantly although also requires CM unit. The pipeline processors for the real-factor FFT and FHT algorithms implementation are developed in the thesis and compared to the Cooley-Tukey algorithms pipeline implementations. Investigations testifies that for small and average sizes of these transforms the real-factor algorithms allows to obtain minimum hardware expenditures.

The discrete wavelet transform (DWT) is widely used in the tasks of signal and image compression. Its high computational requirements stipulates development of specialized processors for its implementation. Pipeline processors for DWT implementation are developed in the thesis. Comparing to existing implementations they feature generalized structure not depending on transform size and filter length. Investigations shows the resemblance of the RFFOT and DWT pipeline processors that allowed with the aim to reduce hardware expenditures to develop pipeline processor for implementation of the fast Hartley transform and discrete wavelet transform.

New parallel FCT algorithm was used to develop VHDL-model of the parallel 8-channel pipeline processor for 8-point inverse FCT algorithm implementation. Developed processor was implemented using FPGA of Xilinx, Inc. Simulation with Xilinx Foundation software showed the best timing and hardware parameters of this processor comparing to existing 8-channel processors.

The main scientific results of this thesis were introduced in scientific-research projects conducted by Lviv Polytechnic University and in educational process of the Department of Computer Engineering of National Lviv Polytechnic University as the part of lecturing and laboratory methodical papers.