автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Наращиваемые процессорные ядра СБИС для выполнения ортогональных преобразований в реальном масштабе времени

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

На правах рукопису У ДК 681.3 '

Аль Кхатіб Ахмад Абдул ьфат

Нарощувані процесорні ядра НВІІ5 Для виконання ортогональних перетворень в реальному масштабі часу

Спеціальність: 05.13.13.-- Обчислювальні машини, системи та

мережі

Автореферат

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

Львів — 2000

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

Работа виконана на кафедрі ’’Електронні обчислювальні машини”, Національний університет ’’Львівська політехніка", Міністерство освіти і науки України.

Науковий керівник- доктор технічних наук, професор Мельник Анатолій Олексійович,

Національний університет”Львівська політехніка”, завідувач кафери ЕОМ Офіційні опоненти- доктор технічних наук, професор

Николайчук Ярослав Миколайович, завідувач кафедри “Спеціалізовані комп’ютерні

системи” (Тернопільська академія народного

господарства).

доктор фізико-математичних наук, професор Попов Богдан Олександрович, завідувач відділу (Фізико-механічний інститут ім. Г.В. Карпенка НАН України) м. Львів.

Провідна установа- Вінницький державний технічний університет, кафедра обчислювальної техніки,

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

Захист відбудеться “ 27 ” листопада 2000р. о 14°° годині.

На засіданні спеціалізованої вченої ради.Д 35.052.05.у Національному ушверситеті”Львівська політехніка” в ауд. 226 головного корпусу (79013, м. Львів, вул. Ст.Бандери, 12).

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

автореферат розісланий “26” жовтня 2000р.

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

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

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

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

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

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

параметрів, на основі якої можуть бути синтезовані всі інші її варіанти для різних параметрів процесора, та всі. інші алгоритми., При цьому необхідно забезпечити можливість програмного задання наступних параметрів архітектури процесора: кількості каналів поступлення та видачі даних, кількості трактів обробки даних, глибини конвеєра кожного тракту, рклад системи виконуваних алгоритмів, схему з'єднання функціональних, вузлів, розрядність шин даних та констант, об'єми постійної пам’яті да пам'яті з.. ДОВІЛЬНОЮ вибіркою. .’ . :

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

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

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

- ДБ/НДКГ (Океан-інформація): ’’Створення мереж для вивчення

багатофакторних і багатофункціональних впливів на природні та штучні об'єкти оточуючого середовиша” (1998-1999 рр.);

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

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

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

з

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

2. Розробити алгоритми обчислень ортогональних перетворень на основі

базового. -

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

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

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

5. Провести синтез процесорного ядра НВІС для виконання ортогональних перетворень в реальному масштабі часу на програмованих логічних пристроях з використанням мови опису апаратних засобів УНБЬ з метою практичного підтвердження результатів теоретичних досліджень та напрацювання основних технічних рішень для перспективних розробок.

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

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

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

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

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

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

5. Розроблені нові структури та отримані аналітичні вирази для оцінки параметрів багатофункціональних процесорів • для виконання ОП в реальному масштабі часу на основі процесора базового перетворення -Фур’є дійсної послідовності, Хартлі, косинусного, що вирішило питання синтезу процесорів для всього спектру ОП та дозволило шляхом порівняльного аналізу визначити області доцільного використання запропонованих архітектур процесорів ОП та сформувати рекомендації по

' вибору оптимальних схемних рішень для конкретного використання.

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

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

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

3. Створена УІШЬ-модель процесорного ядра ОП на основі процесора косинусного перетворення для виконання алгоритмів Фур’є, Хартлі та косинусного перетворень використана при побудові спеціалізованих НВІС для вирішення задач цифрової обробки сигналів.

Впровадження результатів роботи. Результати роботи використані та впроваджені в науково-дослідному конструкторському інституті НДКІ ЕЛВІТ та на кафедрі ЕОМ Національного університету “Львівська політехніка” при виконанні науково-дослідних робіт по темах ДБ/НДКІ (Океан-інформація) в рамках якої були розроблені алгоритми обчислення ОП на основі базового та нові структури процесорів ОП, та ДБ/17.ЕС (Екологія-самоорганізація) в рамках якої були розроблені принципи побудови, струкіури та програмні моделі нарощуваних процесорних ядер ОП, а також в навчальному процесі кафедри ЕОМ, що підтвержується відповідними актами впровадження.

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

основі ядра програмованого процесора та нарощуваного параметризованого ядра процесора швидких ортогональних перетворень; в[2]- класифікація,

' аналіз ‘ та оцінка параметрів існуючих програмованих та апаратно-орієнтованих процесорів швидких ортогональних перетворень; в [3]- підхід до проектування НВІС на основі нарощуваних ядер агіаратно-орієнтованих "процесорів; в [4]- аналітичні вирази для оцінки продуктивності процесорів багатовимірних швидких ортогональних перетворень; в [5]- структури та порівняльна оцінка операційних пристроїв процесорів швидких ортогональних перетворень; в [6,7,8]- принципи побудови нарощуваних ^процесорів ОП на основі процесора базового перетворення, алгоритми виконання ОП на основі синусного та косинусного перетворень Фур’є, ■дискретного перетворення Фур’є діснйх чисел, дискретного косинусного перетворення, архітектури процесорів ОП на Основі процесорів базових перетворень,дослідження параметрів нарощуваних процесорних ядер ОП.

Апробація результатів дисертації.' Основні положення1 дисертації та ' результати досліджень доповідалися та обговорювалися на науково-технічній конференції “Комп'ютерні технології друкарства” (Львів, 1998р.); 5-ій міжнародній науково-технічній конференції “Досвід розробки та застосування приладотехнологічних САПР в мікроелектроніці“ (с.Славське, 1999р.); міжнародній науково-технічній конференції “Сучасні проблеми в комп'ютерних науках в Україні” (с.Славське, 2000р.); міжнародній науково-технічній конференції “Сучасні проблеми засобів телекомунікацій, комп'ютерної інженерії та підготовки спеціалістів” TCSET’2000 (с.Славське, 2000р.); науково-технічній конференції “Комп'ютерні технології друкарства’' (Львів, 2000р.).

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

' Структура та обсяг роботи. Дисертацій складається з чотирьох розділів, висновків і списку використаних літературних джерел в кількості 93 найменувань. Вона має 202 стор., 94 рис., 6 таблиць, і один дотаток на 5} стор.

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

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

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

їх обернені перетворення (ОШПФд) та (ОШПФк), швидкого.перетворення Хартлі (ШПХ), прямого та оберненого швидкого косинусного перетворення (ШКП), швидких синус та косинус перетворень Фур’є (ШСПФ, ШКПФ). Відзначено, що серед всіх ШОП завдяки простоті фізичної інтерпретації математичної моделі і методів побудови швидких алгоритмів на практиці найчастіше використовують пряме та обернене дискретне перетворення Фур’с (ДПФ) комплексних чисел. Пряме обчислення ДІІФ вимагає виконання Л,: множень та Л'(Л'-І) додавань комплексних чисел. Швидке перетворення Фур'с (ШПФ) вимагає виконання тільки И/2*1о§^ базових операцій. Для дійсних сигналів ДПФ с надлишкове, через тс надають перевагу дискретному перетворенню Хартлі (ДПХ), котре скорохцує обчислення, тому що визначене над дійсними числами і має симетричну форму. З точністю до постійного нормуючого множення його пряме та обернене перетворення збігаютея. Разом з тим, ШПХ є надлишковим при обробці дійсних парних та дійсних непарних сигналів. В цих випадках більш доцільно використовувати ШКПФ та ШСПФ, оскільки вони є симетричні і визначені на вужчому класі парних та непарних функцій, що дає можливість скоротити кількість операцій при їх виконанні.

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

Показаний зв’язок перетворень Фур'є та Хартлі з іншими ортогональними перетвореннями: Гільберта , Френеля, Лапласа, Меліна. Доказана доцільність розділення ШОП на дві групи. До першої групи віднесені ШПФ, ШПХ, ШКП, ШСПФ, ШКПФ, та їх часткові випадки. До другої групи віднесені інші ШОП, які можуть бути виконані на перетвореннях першої групи шляхом попереднього множення на деяку вагову функцію та послідуючої, після базового перетворення, модифікації спектральних компонент за деякою у загальному випадку нелінійною функцією.- Зроблений висновок про доцільність засередження основної уваги на питаннях реалізації перетворень першої групи, як базових.

Оцінені вимоги до комп’ютерних засобів для виконання алгоритмів ШОП. Показано, що основною вимогою є забезпечення високої продуктивності, яка може бути оцінена з виразу Р = НМ/Ы, де К - складність задачі, к - кількість каналів поступлення даних, Г - частота поступлення даних, N - розмір вибірки, причому для одновимірних ШОП Я = N/2 1оцЫ базових операцій, для

двовимірних ШОП R = N2M2/4 logM logN базових операцій, для тривимірних ШОП R = L3N3M3/4 logL logM logN базових операцій. Тут L,M,N - кількість відліків по кожній з осей координат.

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

В роботі проведено аналіз продуктивності при виконанні алгоритмів ШОП універсальних програмованих процесорів з повним та з скороченим набором команд, зокрема фірми Intel, програмованих процесорів з широким форматом команди, зокрема фірми Texas Instruments, програмованих процесорів обробки сигналів фірм Motorola, Texas Instalments, Zoran, NEC, IBM, Analog Devices, AT&T і т. д., програмованих процесорів з спеціалізованою системою команд, зокрема фірми NEC, та на паралельних системах на основі програмованих процесорів. Показано, що існуючі на сьогодні програмовані процесори та багатопроцесорні системи на їх основі забезпечують виконання алгоритмів одновимірних ортогональних перетворень лише в кілогерцовому, а найбільш продуктивні з паралельною архітектурою програмовані процесори

- в частотному діапазоні не вище 10 МГц. При обробці дво- та тривимірних сигналів програмовані процесори можуть бути використані, коли частотний діапазон сигналів не перевищує кілька десятків кГц.

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

Показано, що сучасні тенденції в створенні методів та засобів проектування спеціалізованих НВІС направлені на скорочення термінів проектування апаратно-орієнтованих процесорів, зменшення складності

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

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

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

Алгоритми таких апаратно-орієнтованих перетворень розроблені в цьому ж розділі. Ці алгоритми дозволяють виконати набір ШОП: ШПФк, ОШПФк, ШПФд, ОІИПФд, ШПХ, ШКП, ОШКП, ШСПФ, ШКТТФ, на основі одного із них, взятого за базове. Так зв’язок між дискретним перетворенням Хартлі (ДПХ) та дискретним косинусним перетворенням (ДКП) описується залежностями'. .

Н(к)= (А:)[с:,у - БІ ]/2 + Ьт(М - Аг)[с^ + 6'4\, |

ДЄ Ьт(к) = ДКЛ{хт(п)}, хт(2п)='х(п), хт(2п + \) = х(Ы-\-п), л = 0,1,...,///2-1,

а між дискретним перетворенням Фур’є дійсних чисел (ДПФд) та ДКП залежностями:

Ке{Х(к)}=^к)СІ +Ьт(Ы-кус\м 1

\т{Х(Н-к)}=-\іт(к)5І-Іт(К-к)Сі]\ ‘

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

Показані основні переваги такого підходу: спрощення процесу

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

Рис. 1. Обчислення ШОП на основі ШКП.

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

' " а) ; й>

Рис.2! Структура Л-точкового процесора ШОП а) та його процесорного

елемента б). ■ .

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

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

співвідношенні до розмірності перетворення, а також об’єми вхідної та вихідної пам’яті для впорядкування даних і об’єми памяті констант.

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

В третьому розділі проведений порівняльний аналіз різних варіантів архітектур процесорів ШСШ. Для цього спочатку вибрані принципи побудови тракту обробки даних процесорів ШОП та досліджені, відмінності процесорних ядер ШОП на базі процесорів різних базових перетворень (ПБП). Показано, що архітектури процесорних ядер ШОП відрізняються складністю операційних пристроїв ПБП та обрамленням ПБП. На основі аналізу базових операцій алгоритмів ЩОП виділено три типи різних базових операцій (БО): БО алгоритму ШПФК за основою два, БО алгоритму ШПХ та БО алгоритму ШКП, та три відповідних варіанти трактів обробки даних ПБП. Запропонований принцип порівняння складності ПБП шляхом приведення їх операційних пристроїв для виконання БО (ОПБО) до однакової кількості входів та виходів та синтезу їх для кожної базової операції та для кожного з трьох вищеназваних варіантів.

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

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

10/г (log, N + 4) + 3/f(54 + 4,75A' + +61 log, N).

Аналогічні залежності для процесорів ШПХ та ШКГІ мають вигляд 10/г (log, N + 4) + Зн(54 + 4,75jV + +611og, N),

«log, NlOSti +183 + f33A7(4 log, N)).

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

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

В четвертому розділі проведено проектування та синтез УШЗЬ-моделі процесора ШОП на основі ШКП. Для реалізації вибрані наступні найбільш вживані типи перетворень: ШПФд, ШПФе, ШПХ, ШКП, ОШКП. Розроблено інтерфейс процесора, принципи синхронізації вхідних та вихідних даних, вибрано розміри перетворень та формат представлення даних. Розроблено структуру процесора для виконання вибраних типів перетворень, яка представлена на рис.З, та принципи її програмування. Тут СП * сортувальна пам’ять, ПВ - блок повороту вектора, БК - блок керування, МП -мультиплексор.

роїмірперсіворсшм nm nepeiBOpeiDU

Рис.З. Структурна схема процесора ШОП на основі ШКП.

Створені VHDL-моделі функціональних вузлів процесора: сортувальної пам’яті, блока повороту вектора, перемножувача комплексних чиссл, блоків виконання базових операцій, блока постійної пам’яті, формувачів адрес даних, блоків управління. Для перевірки роботи моделі процесора розроблений генератор тестів. Проведено моделювання процесора ШОП на основі ШКП та оцінка його параметрів при реалізації на ПЛ1С серій ALTERA та XILINX. При розробці моделі використані результати досліджень попередніх розділів. Проведене моделювання та макетування підтвердило правильність вибраного підходу.

В додатку наведені вихідні тексти програм VHDL-моделі процесора ШОП на основі ШКП та документи про впровадження результатів дисертаційної роботи.

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

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

1. Оцінені вимоги до комп’ютерних засобів для виконання алгоритмів ШОП в реальному масштабі часу та отримані формалізовані вирази для розрахунку продуктивності процесорів ШОП з' використанням яких проведено дослідження та аналіз основних архітектур прбфамованих та апаратно-оріснтованих процесорів ШОП та визначено області доцільного використання архітектур кожного типу. Результати цих досліджень показали суттєві переваги анаратно-орієнтованих процесорів ШОП над програмованими в частині забезпечення заданої продуктивності при мінімальних затратах обладнання та напрямок підвищення їх гнучкості шляхом створення нарощуваної архітектури.

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

3. Досліджені відмінності процесорних ядер ШОП на базі процесорів різних базових перетворень, що дозволило виділити три типи базових операцій та три базових варіанти трактів обробки данних цих процесорів: одно-, дво-та чотириканальний. Та вперше Запропоновано принцип порівняння складності процесорів базових перетворень шляхом приведення їх операційних пристроїв для виконання базових операцій до однакової кількості входів та виходів та синтезу їх для кожної базової операції та для

' кожного з трьох вищеназваних варіантів.

4. Розроблені нові структури операційних та арифметичних пристроїв для виконання базових операцій алгоритмів ШПФК, ШПФЛ, ШПХ, ШКП, сортувальної пам'яті, регістрів, суматорів, перемножувачів, ПЗГІ коефіцієнтів та інших функціональних елементів тракту обробки даних процесорів ШОП для різної кількості каналів обробки даних із забезпеченням обробки в реальному масштабі часу, що дозволило отримати аналітичні вирази для оцінки їх технічних параметрів та створити базу для синтезу процесорних ядер ШОП.

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

6. Вперше створена VHDL-модель та проведено синтез НВІС на програмованих логічних пристроях процесорного ядра ШОП на основі процесора косинусного перетворення для виконання алгоритмів Фур’є, Хартлі та косинусного перетворень, яке характеризується технічними параметрами на рівні кращих світових зразків та має порівняно з ними суттєві переваги, а саме має ширші функціональні можливості та забезпечує можливість розширення типів та розмірів перетворень.

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЙНОЇ РОБОТИ .

1. Мельник А.О., Аль Кхатіб Ахмад. Система обробки сигналів на основі програмованого процесора та процесора швидких ортогональних перетворень // Технічні вісті. - 1999, № 1(8), 2(9). - с. 124-127.

2. Мельник А.О., Аль Кхатіб Ахмад. Виконання швидких ортогональних перетворень на програмованих процесорах // Вимірювальна техніка та метрологія - 2000, Ns 56. - с. 70-77.

3. Мельник А.О., Аль Кхатіб Ахмад. Концепція побудови нарощуваних параметризованих процесорних ядер спеціалізованих надвеликих інтегральних схем // Вісник Державного університету "Львівська політехніка” "Комп'ютерні системи та мережі.” 1998, № 350. - с. 44-47.

4. Мельник А.О., Аль Кхатіб Ахмад. Вимоги до продуктивності процесорів багатовимірних швидких ортогональних перетворень// Збірник наукових праць “Комп'ютерні технології друкарства”. Львів -1998. -с.113.

5. Мельник А. О., Аль Кхатіб Ахмад. Операційні пристрої швидких ортогональних перетворень // Матеріали 5-тої міжнародної науково-технічної конференції “Досвід розробки і застосування САПР в мікроелектроніці”. 1-6 лютого 1999, Львів. - с.152.

6. Мельник А. О., Аль Кхатіб Ахмад. Архітектура процесора швидких ортогональних перетворень на основі синусного та косинусного перетворень Фур’є // Матеріали 5-тої міжнародної науково-технічної конференції “Досвід розробки і застосування САПР в мікроелектроніці”. 1-6 лютого 1999, Львів. -с. 153-154.

7. Anatoly Melnyk, Ahmad al Khatib. Fast orthogonal transform processor architecture based on a real data discrete fourier transform kernel // Proceedings of international conference on modern problems of telecommunication, computer science and engineers training TCSET’2000, с.Славське, 2000. - с. 118.

8. Мельник A.O., Аль Кхатіб Ахмад. Процесорні ядра ортогональних перетворень на основі дискретного косинусного перетворення// Матеріали міжнародної науково-технічної конференції “Сучасні проблеми в комп'ютерних науках в Україні”. Славське, 2000. - с. 45.

АНОТАЦІЯ ...

Аль Кхатіб Ахмад Абдульфатах. Нарощувані процесорні ядра НВІС для виконання , ортогональних перетворень в реальному масштабі часу. - Рукопис. ^

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

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

Проведено проектування та отримані аналітичні вирази для оцінки, параметрів багатофункціональних процесорів для виконання ШОП в реальному масштабі часу на основі процесора базового перетворення - Фур’є дійсної послідовності, Хартлі, косинусного, що вирішило питання синтезу процесорів для всього спектру ШОП та дозволило шляхом порівняльного аналізу визначити області доцільного використання запропонованих архітектур процесорів ШОП та сформувати рекомендації по вибору оптимальних схемних рішень для конкретного використання. На основі результатів теоретичних досліджень створена УНГЭЬ-модель та проведено синтез НВІС на програмованих логічних пристроях процесорного ядра ШОП на основі процесора швидкого косинусного перетворення, яке характеризується технічними параметрами на рівні кращих світових зразків та має порівняно з ними суттєві переваги, а саме має ширші функціональні можливості та забезпечує можливість розширення типів та розмірів перетворень.

Ключові слова: швидкі ортогональні перетворення, ШПФ, ШПХ, ШКП, процесор, процесорне ядро, НВІС.

АННОТАЦИЯ

Аль Кхатиб Ахмад Абдульфатах. Наращиваемые процессорные ядра СБИС для выполнения ортогональных преобразований в реальном масштабе времени. - Рукопись. .

Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.13. - Вычислительные машины, системы и сети.

- Национальный университет «Львовская Политехника», Львов, 2000.

В диссертации выполнен анализ алгоритмов быстрых ортогональных преобразований (БОП) и исследована их взаимосвязь, произведена оценка требований, предъявляемых к компьютерным средствам выполнения алгоритмов БОП в реальном масштабе времени и предложены формализованные выражения для оценки продуктивности процесоров БОП, с использованием которых выполнены исследование и анализ основных архитектур программируемых и аппаратно-ориентированных процессоров БОП а также, определены области предпочтительного применения

архитектур каждого типа. Показано, что современные тенденции в создании методов и средств проектирования специализированных СБИС направлены на сокращение терминов проектирования аппаратно-ориентированных процессоров, уменьшения сложности проектирования, снижения стоимости специализированной СБИС.

Предложена концепция построения процессорных ядер для реализации ортогональных преобразований, и принцип построения ядер аппаратноориентированных процессоров с возможностью к наращиванию в

архитектуре.

Разработаны алгоритмы вычисления БОП на основе базового, а также новые архитектуры таких процессоров. Создана архитектура

многофункционального процессорного ядра ОП на основании дискретного косинусного преобразования и архитектуры однофункциональных

процессорных ядер ОП на основании дискретного косинусного преобразования. Проведена разработка арифметических устройств ОУБО.

Исследованы отличия процессорных ядер БОП на базе процессоров различных базовых преобразований и выделено три типа базовых операций и три базовых варианта трактов обработки данных этих процессоров: одно-, дво- и четырёхканальный. Предложен принцип сравнения сложности процессоров базовых преобразований путём приведения их операционных устройств для выполнения базовых операций к одинаковому количеству входов и выходов а также синтеза их для каждой базовой операции и для каждого из трёх вышеназванных вариантов.

Проведено проектирование и получены аналитические выражения для оценки параметров многофункциональных процессоров выполнения БОП в реальном масштабе времени на основе процессора базового преобразования -Фурье действительных последовательностей, Хартли, косинусного, синусного и косинусного Фурье, что обеспечило решение вопроса синтеза процессоров для всего спектра БОП и формирование рекомендаций по выбору оптимальных схемных решений для конкретного использования.

Па основе результатов теоретических исследований создана VIШЬ-модель и произведён синтез СБИС на программируемых логических устройствах процессорного ядра БОП на основе процессора быстрого косинусного преобразования для выполнения алгоритмов БОП Фурье, Хартли и косинусного, которое харакгеризируется техническими

параметрами на уровне лучших мировых образцов и обладает существенными по сравнению с ними преимуществами, а именно характеризируется более широкими функциональными возможностями и обеспечивает возможность расширения типов и размеров_преобразований.

Ключевые слова: быстрые ортогональные преобразования, БПФ, БПХ, БКП, процессор, процессорное ядро, СБИС.

ABSTRACT А1 Khatib Ahmad Abdulfatah. Scaleable VLSI processor cores for orthogonal transform execution in real-time mode. - Manuscript.

Thesis for the philosophy doctor degree in speciality 05.13.13 - Computers, computer systems and networks. - “Lviv National Polytechnic University”, Lviv, 2000.

The Fast Orthogonal Transforms (FOT) algorithms are considered in the thesis. The algorithms’ interrelation is investigated, the hardware requirements for performing FOT’s in real-time mode are evaluated, the formalized expressions for evaluation of FOT processors’ productivity are proposed. The proposed expressions are used for investigation and analysis of major architectures of programmable and hardware-oriented FOT processors. The FOT computing algorithms on the base of base one and also the new architectures are developed. The peculiarities of FOT processor cores on the base of different base transform processors are investigated.

Design is performed and analytical expressions are obtained for evaluation of parameters for multifunctional processors performing FOT in real-time mode basing on base transform processor - Fourier of real sequence, Hartley, cosine. This provided the solution for synthesis of processors for the entire range of FOT’s and allowed to determine the ranges of expedient utilization of proposed FOT processor architectures by means of comparative analysis. This also allowed for compilation of the set of recommendations for selecting the optimal scheme solutions in particular applications. Basing on the theoretical results there is a VHDL-model created and the synthesis of LSIC on programmable logical devices is performed. Theses solutions feature parameters meeting state-of-the-art standards and have the substantial advantage over them in wider functional features and allow for transform type and size scalability.

Keywords: fast orthogonal transforms, FFT, FHT, FCT, processor, processor core, VLSI.

Підписано до друку 23.10.2000 p.

Формат 60x84 1/16. Папір офсетний.

Друк на різографі. Умовн. друк. арк. 1,4. Обл.-видав, арк. 0,89.

Тираж 100 прим. Зам. 441.

Поліграфічний центр Видавництва Національного університету “Львівська політехніка”

вул. Ф.Колесси, 2, 79000, Львів '