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

РГ8 ОД

А (| 6 5 І I) 'роо

і Ь І.ІЙІІ і.-'С. КИЇВСЬКИЙ ПОЛІТ ЕЖ ІЧНИЯ ІНСТИТУТ -

На правах рукопису МАРЧЕНКО ОЛЕКСАНДР ІВАНОВИЧ

ЗАСОБИ АВТОМАТИЗАЦІї ПРОГРАМУВАННЯ ПРОЦЕСОРІВ ЦИФРОВОЇ ОБРОБКИ СИГНАЛІВ

Спеціальність 05.13.11.- Математичне та програмне

забезпечення обчислювальних мапшн, комплексів, систем та мереж

Автореферат

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

Київ - 1993

Науковий тері вник : кандидат технічних наук, доцент СТЕБЛЯНКО а Г.

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

Провідна установа : Інститут кібернетики ім. В. М. Глушкова АЦ України

Захист відбудеться " 17 " травня 1993 р. о 14.30 годиш на засіданні спеціалізованої Ради Д 068.14.09 у Київському політехнічному інституті (м.Киів, проспект Перемоги 37, корп. 18).

Відгуки на автореферат у двох примірниках, засвідчені печаткою установи, просимо надсилати за адресою : 252056,

Київ-56, проспект Перемоги 37, КПІ, Ученому секретареві Ш.

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

Автореферат розісланий ” _________1993 р.

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

ЗАЙЦЕВ а г.

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

павловсьш а і.

д. т. н., професор

МЕТОЮ дисертаційно! роботи є дослідження існуючих та розробка нових мовних засобів високого рівня для автоматизації програмування процесорів класу Однокристальних Цифрових Процесорів Сигналів (ОЦПС), а також Однопроцесорних Систем (ОС) Цифрової Обробки Сигналів (ЦОС), побудованих на основі ОЦПС.

. Для досягнення мети вирішувались такі задачі:

- класифікація існуючих Мов Високого Рівня (МВР), щр застосовуються для вирішення задач ЦОС;

- обгрунтування критеріїв вибору конструкцій для нової МВР;

- аналіз відомих МВР з точки зору їх принадності для вирішення

задач ЦОС та можливості реалізації трансляторів для ОЦПС і процесорів на основі ОЦПС; '

- розробка нової МВР, орієнтованої на програмування алгоритмів ЦОС з врахуванням особливостей архітектури процесорів класу ОЦПС.

АВТОР ЗАХИЩАЄ такі основні положення та результати;

- класифікацію МВР, що використовуються у галузі ЦОС;

- спеціалізовану МВР Сигнал, орієнтовану на вирішення задач ЦОС та засоби її реалізації;

- способи оптимальної реалізації спеціалізованих конструкцій МВР для процесорів класу ОЦІЮ;

- алгоритми оптимизації коду, щр генерується, для процесорів класу ОЦПС.

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

АКТУАЛЬНІСТЬ ДОСЛІДЖЕНЬ. За останні десятиліття цифрові ме тоди обробки сигналів, що швидко поширюються, були впроваджені у різні розділи науки та техніки і стали для них міцною теоретичною базою. Обчислювальні машини та інші цифрові пристрої, будучи впровадженими у ті галузі техніки, в яких раніше вони не використовувались, прискорюють науково-технічний прогрес. З кожним роком по мірі збільшення швидкодії комп'ютерів, зменшення вартості та розмірів інтегральніх схем зростають можливості вирішення задач все більшої складності. До таких задач належить і цифрова обробка сигналів. Відповідно, широке використання почали знаходить пристрої ЦОС.

Більшість сучасних пристроїв цифрової обробки сигналів

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

Програмування ОЦПС, внаслідок специфічності архітектури та системи команд, становить собою складну і трудомістку задачу як ,8 точки зору самих алгоритмів ЦОС, так і з точки зору їх відображення на архітектуру ОЦПС. Ці особливості ОЦПС визначають високу складність і низьку якість трансляторів а поширених універсальній мов програмування високого рівня, реалізованих для них. У зв'язку з цим спеціалізовані МЕР, конструкції яких орієнтовані на вирішування задач ЦОС і враховують особливості процесорів класу ОЦПС, можуть стати надійною сполучною ланкою міа алгоритмістами ЦОС та складною апаратурою на основі ОЦПС. Тому-то, розробка і реалізація таких МВР, до дозволяють автоматизувати процес програмування вказаних процесорів, являє собою актуальну проблему.

МЕТА РОБОТИ. Метою дисертаційної роботи є дослідження існуючих та розробка нових мовних засобів високого рівня для автоматизації програмування процесорів класу однокристальних цифрових процесорів сигналів, а також однопроцесорних систем цифрової обробки сигналів, побудованих на основі ОЦПС.

МЕТОДИ ДОСЛІДЖЕННЯ дисертації базувались на методах і засобах системного аналізу, теорій структур даних, алгоритмів, формальних граматик, мов, синтаксичного аналізу та перекладу.

НАУКОВА НОВІТНІСТЬ роботи полягає у такому :

- у розробці новоі МВР, відмітними якостями якої є простота та орієнтація її засобів 1 конструкцій на прикладну галузь ЦОС та на нетрадиційну архітектуру процесорів класу ОЦПС;

- у запропонованих способах генерування оптимального по швидкодії коду процесорів цифрової обробки сигналів, що належать до класу ОЦІЮ;

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

- з -

вання.

ПРАКТИЧНА ЗНАЧНІСТЬ одержаних результатів полягає в такому:

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

на клас ОЦПС, вона може бути використана для програмування

будь-якого процесора вказаного класу. Запропоновані способи і

алгоритми оптимізаці! можуть використовуватись при реаліааці! трансляторів інших МВР, щр застосовуються для програмування процесорів класу ОЦПС.

РЕАЛІЗАЦІЯ результатів роботи. Теоретичні та практичні результати дисертації були використані при розробці системи автоматизації програмування процесорів ЦОС, реалізованої в рамках науково-дослідницьких робіт, виконаних на кафедрі обчислювальної техніки Київського політехнічного інституту, а також частково включені в матеріал курсу "Математичне забезпечення ЕОМ", щр викладається студентам спеціальності "ЕОМ, комплекси, системи та мережі". Програмне забезпечення реалізоване на мові Турбо-Паскаль в середовищі операційної системи КБ БОБ і може експлуатуватися на комп'ютерах типу ІВМ ХГ/АТ. Система автоматизації програмування упроваджена на підприємстві ННДПІ "Кварц", м. Нижній Новгород. Річний економічний ефект складає 70 тис. карбованців в цінах 1990 р. Акти, пр підтвержуїоть упровадження та економічну ефективність результатів дисертації, наведені в додатках до неї.

АПРОБАЦІЯ РОБОТИ. Основні положення та результати дисертаційної роботи доповідались і обговорювались на таких конференціях та семінарах: Шоста Міжреспубліканська школа-семінар

"Інтерактивні системи"(Батумі, 1984), IV Всесоюзна конференція "Діалог людина - ЕОМ” (Київ,1985), Республіканський семінар "Проблемно - орієнтовані мови і системи'ЧКиїв, 1985), Республіканський семінар "Автоматизація проектування програмного,

еабеэпечення мікро-ЕОМ та мікропроцесорних систем" (Київ,1986), Республіканський семінар "Теорія мов і автоматизація програмування" (Київ,1086), Всесоюзний семінар "Передача та обробка даних в інформаційних керуючих системах і мережах ЕОМ" (Київ,1987), Всесоюзна конференція "Сучасні інструментальні комплекси і технології створення програмних систем реального часу" (Київ,1988), Республіканська конференція "Використання мікропроцесорів в народному господарстві"(Таллінн,1988), Всесоюзна конференція "Методи та мікроелектроні засоби цифрової обробки та перетворення сигналів"(Рига,1989), Міжнародний симпозіум "Інформатика-89" (Мінськ, 1989).

Основні положення дисертації відображені у 14 опублікованих роботах та в 2 науково-технічних ввітах.

СТРУКТУРА ТА ОБСЯГ РОБОТИ. Дисертаційна робота складається 8 вступу, чотирьох глав, заключения, 29 малюнків, 3 таблиць, списку літератури з 122 назв, додатків. Основний зміст роботи викладений на 129 сторінках машинописного тексту.

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

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

У другій главі обгрунтований підхід до вибору мовних засобів та конструкцій, виконана специфікація синтаксису і зроблений неформальний опис семантики нової МВР Сигнал, орієнтованої на прикладну галузь ЦОС та реалізацію для процесорів класу ОЦІЮ.

У третій главі досліджені особливості реалізації мов високого рівня для процесорів класу ОЦПС, наведений опис процесора ЦОС, основним обчислювальним элементом якого є ОЦІЮ. Запропоновані способи оптимального використання ресурсів процесорів вказаного класу.

У четвертій главі обгрунтований вибір засобів реалізації семантики та розроблені структури даних І алгоритми генерації

оптимального вихідного асемблерного тексту, які відповідають запропонованим способам оптимізації використання ресурсів процесорів класу ОЩІС.

У заключенні сформульовані основні результати дисертації.

У додатках наведені документи, ир підтверджують впровадження запропонованих в роботі засобів, синтаксис мови Сигнал, ліс-тинги основних розроблених програм та приклади програмування на мові Сигнал. .

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

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

Узагальнюючи характеристику алгоритмів ЦОС відзначимо їх головні особливості: 1) сувора математична основа; 2) великий

обсяг числових обчислень; 3) високі вимоги до швидкості обробки даних; 4) "внутрішній" паралелізм; 5) допустимість асинхронного виконання операцій; 6) безперервний (потоковий) характер вхідних та вихідних даних; 7) широке використання операцій "множення-додавання" та "метелик"; 8) використання в алгоритмах Швидкого Перетворення Фур'є(ПШ) двоїчно-інверсних чисел. .

Після технологічного прориву у виробництві НВІС на початку 80-х років продуктивність нових пристроїв ЦОС рі8ко абільшилась, щр дозволило використовувати для їх програмування МВР. Можливість використання МВР для програмування спеціалізованих

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

Узагальнюючи результати класифікації та аналізу можна зробити такі висновки:

- великі наробки програмного забезпечення на сучасних популярних мовах ( С, ГогЬгал, Разсаі ) є тормозом для розвитку нових мов;

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

- на теперішній час МВР в застосуванні до задач ЦОС використовуються для двох різних цілей: 1) для моделювання систем ЦОС

та вивчення характеристик сигналів, шр перетворюються за різними алгоритмами, не в реальному масштабі часу; 2) для програмування процесорів та багатопроцесорних систем ЦОС, що працюють у реальному часі;

- для програмування задач ЦОС до теперішнього моменту часу використовувались МВР як загального призначення, так і спеціалізовані МВР, орієнтовані на клас задач ЦОС та архітектуру обчислювальних систем, щр застосовуються у ЦОС;

- у розвитку МВР для ЦОС перспективними уявляються два напрями: 1) створення спеціалізованої об'єктно-орієнтованої надбудови до якої-небудь існуючої МВР ( як зроблено у ЗІРШЬ та БИ. ) з надаванням користувачу вже готової численної бібліотеки підпрограм, щр буде добре для поширених ОС з потужними операційними системами; 2) розробка нової оригінальної мови з простим і гармонійно підібраним набором спеціалізованих мовних конструкцій ( представники цього напряму - мови РЬ/ЗЕХ}, М2, МОП. ), щр доцільно для спеціалізованих васобів ЦОС на основі МП;

- практично неможливо одну й ту ж саму МВР однаково ефективно реалізувати для процесорів ЦОС різних архітектур;

- оскільки задачі ЦОС вимагають максимальної швидкості обробки, то в галузі обробки сигналів доцільно для кожного класу обчислювальних систем (систолічні вектори, швильові матриці, ОС на основі ОЦПС ) створювать окрему МВР, конструкції якої будуть відображати загальні для даного класу ОС особливості і, завдяки

цьому, дозволять досягнути генерації ефективного вихідного коду;

- майже всі МВР, щр використовуються на практиці для програму-

вання задач ЦОС в реальному масштабі часу, належать до класу процедурних МВР; *.

- МВР, яка орієнтована на задачі ЦОС та враховує особливості архітектури процесорів класу ОЦПС, створена ще не була;

- МВР, орієнтовану на архітектуру ОЦПС доцільно розроблювати у класі процедурних МВР.

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

Для встановлення загального підходу до вибору мовних конструкцій, визначимо МВР як сукупність наборів конструкцій

І, - { БТ, БР/, , ... , БЕп} , де

БТ - набір основних стандартних мовних конструкцій, які традиційно включаються практично у всі процедурні МВР; - набір мовних конструкцій, відображаючих особливості і-ї прикладної галузі; п - конечне натуральне число.

Для процедурних МВР до стандартних були віднесені передвиз-начені типи та керуючі конструкції мови РаБсаІ, які стали вже класичними. ■

Оцінку доцільності розробки та використання нової МВР (М) можна визначити як залежність від чотирьох параметрів М - { V, Рй, РЦ РЕ > , де

V - діапазон охоплення алгоритмів рівних класів задач; Рй -витрати на реалізацію всіх конструкцій МВР; РЬ - витрати на вивчення усіх конструкцій МВР; РЕ - витрати на розробку програм а використанням даної МВР та їх супроводження.

Уведемо позначення :

/ - збільшення ( розширення ) відповідного параметра;

V - зменшення ( зниження ) відповідного параметра;

■—> - приводить до .

Між параметрами V, РЯ, РЬ, РЕ та показником М існують такі якісні співвідношення:

/ V —> і М ; * РП, РЬ, РЕ ~> ЧН,

- 8 - ' Шрб оцінити доцільність включення у МЕР, щр розроблюється ТИХ; чи інших конструкцій БТ 1 БР визначиш їх вплив на параметри V, РЯ, PL та РЕ. Кількісна оцінка такого впливу практично неможлива через залежність від кваліфікації конкретних спеціалістів, щр займаються розробкою та використанням МЕР. Тому, обмежимося якісними взаємозалежностями. Набір БТ стандартних мовних конструкцій включається практично у всі процедурні МВР і визначає базовий рівень витрат Рй, РЬ, РЕ та диапазону охоплення алгоритмів V. Включення додаткових наборів конструкцій БР/, орієнтованих на і-у прикладну галузь, справляє неоднозначний еплив на параметри оцінки М і може привести як до їх покраа^ння, так і до погіршання відносно базового рівня.

Оскільки в даній роботі досліджуються проблеми розробки МВР для конкретної прикладної галузі цифрової обробки сигналів (позначимо її індексом ‘і) при використанні конкретного класу процесорів (позначимо індексом к), то, враховуючи вказану неоднозначність впливу наборів конструкцій Б^, 1 в подальшому будемо розглядать взаємозалежності між та параметрами більш конкретизованої оцінки застосування МВР М;^ яка в цьому випадку одержить вигляд

м¡к- < V; . Рй*. РЬ; , РЕ; > , де

V; - діапазон охоплення алгоритмів 1-і прикладної галузі; РІ?* - витрати на реалізацію усіх конструкцій МВР для к-го класу процесорів; - витрати на вивчення усіх конструкцій МВР спеціалістом і-ї прикладно! галузі; РЕ; - витрати на розробку та супроводження програм для вирішення задач ]-ї прикладної галузі засобами даної МВР. .

Проаналізуємо окремо випадок Б^-,; , коли включаються конструкції, орієнтовані на задану 1-у проблемну галузь, та випадок БІ, коли включаються конструкції, не відображаючі алгоритмів цієї галузі.

Включення будь-якого БРі —> / Рй*.

Включення --> * V; , \ РЬ; , Ч РЕ; .

Включення ^ РЬ; , і не впливає на V; та РЕ;

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

проблемно! галузі, для яко! створюється нова мова. Аналогічні висновки можна вробити 1 для переліку стандартних конструкцій ST , ОСКІЛЬКИ ВСІ вони в повному обсязі будуть потрібні не для кожного класу прикладних задач.

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

Lj.k - { STj.k , SF,y > , де

ST;* - набір стандартних мовних конструкцій, які орієнтовані на j-y прикладну галузь і відображаються на архітектуру k-ї ОС;

SF;* - набір спеціалізованих конструкцій, які орієнтовані на j-y проблемну галузь 1 відображаються на архітектуру к-! ОС.

Такий вибір конструкцій спеціалізовано! МВР приведе до мінімальності витрат PR* , PL; , РЕ j. при достатній повноті охоплення алгоритмів J-І проблемної галузі Vj. та, відповідно, визначить високу оцінку UjK.

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

Спеціалізованими типами даних є типи blockfloat та complex. Включення у мову типу blockfloat доцільно з таких причин: 1) дані у формі а поблочно-плаваючою комою вимагають менше пам'яті, ніж дані з плаваючою комою; 2) велика кількість вхідних та вихідних даних у задачах ЦОС задається саме у такій формі. Тому, шрб використовувати плаваючу кому, треба виконати перетворення спочатку з форми з поблочною комою у форму з плаваючою, а потім -навпаки; 3) операції над числами у формі з поблочною комою вико-

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

Ще однією характерною особливістю алгоритмів ЦОС є. часте використання спеціальних функцій, які називають вікнами і які визначаються у задачах, як правило, у аналітичному вигляді. Враховуючи це, у мову Сигнал був включений спеціальний розділ define для опису таких функцій, визначених у аналітичному вигляді і які при трансляції перетворюються у масив дискретних значень на заданому інтервалі зміни аргументу.

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

Крім стандартних керуючих конструкцій в мові Сигнал були специфіковані ще два спеціалізовані різновиди циклів for : for lnv та for butfly. Ці спеціалізовані конструкції орієнтовані на спрощення програмування алгоритмів ШПФ і дозволяють генерувати оптимізований вихідний код. .

Цикл for lnv призначений для написання фрагментів програм обчислення ПШ, у яких використовуються двоїчно-інверсні числа (ДІЧ). Він має вигляд:

for lnv (KN) і:-1 to n do , де NN - верхня межа двоїчно-інверсного лічильника. Частина опису inv(NN) вказує компілятору на необхідність виконання деяких підготовчих дій перед циклом та обчислення на кожній ітерації циклу наступного ДІЧ 8 діапазону від 0 до NN-1. Крім того, оскільки конструкція for lnv носить функціональний характер, тобто не вказує, яким чином вираховується чергове двоїчно-інверсне число, то розробник компілятора може вибирати найбільш оптимальний по пам'яті та часу варіант реалізації обчислення ДІЧ.

Конотрукція for butfly надав програмюту гнучкий інструмент

' It -

роботи з операцією "метелик" та ефективної реалізації різних алгоритмів ШПФ. Вона дозволяє легко написати програму обчислення ШПФ по основі 2 практично за будь-якою схемою. Зміст конструкції for butfly базується на таких властивостях та особливостях алгоритмів ШПФ. Усі алгоритми ШПФ можна поділити на дві великі групи: в прорідженням по часу (time) і по частоті (freq). На кожному окремому етапі обчислення ІІШ залишаються сталими: 1) відстані

між індексами точок козиного "метелика" як для вхідного масива, так і для вихідного; 2) кроки переходу від одного "метелика" до наступного і для вхідного, і для вихідного масивів, і для масива коефіцієнтів. Загальний вигляд циклу for butfly зображується таким чином.

for butfly ( < time, freq } ) <опис цикла> do геЦ<іден-р вх. масивах індекс верх, точних індекс них точки><крок>; put( < і ден-р вих. масивах індекс верх, точних індекс ниж. точки><крок>; соеП<іден-р масива коефіцієнтах індекс почат. коеф-тахкрок>;

endfor ,

де у фігурні скобки взяті альтернативні терміни, а у квадратні -необов'язкові. Такою синтаксичною конструкцією описується одночасно декілька законів зміни індексів (а не одного, як для звичайного циклу for ), і розробник компілятора не обмежується жорсткими рамками чисто імперативних конструкцій на этапі генерації вихідного коду. Це дозволяє обчислення індексів для елементів кожного масива замінити на організацію лічильників 8 визначеним кроком, шр зменшує кількість команд, витрачених на виборну чергового елемента масива." У результаті швидкодія вихідного коду збільшується. .

Машинозалежна оптимівація коду, щр генерується, зв'язана з проблемами розподілу регістрів та виключення зайвих пересилок між Регістрами Загального Призначення(РЗП), регістрами АЛЛ та ОЗП. Ці задачі вже достатньо глибоко досліджені 1 на теперішній час запропоновано декілька алгоритмів їх вирішення. Однак, ці алгоритми орієнтовані на архітектури універсальних процесорів, у яких відсутній апаратний пристрій множення, є РЗП-и та гнучка система адресації при звертанні до ОЗП. При цьому РЗП-и, як правило, у таких процесорах можуть використовуватись і як швидкі комірки пам'яти, і як адресні регістри. У порівнянні з універсальними процесорами, для процесорів класу ОЦІЮ задача

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

Для задач ЦОС цикл for використовується найчастіше і є найбільш важливим. Тому оптимізація коду, ир генерується для такого типу циклів, у великій мірі визначає одержання ефективних вихідних програм. Відповідно цьому, у дисертації таким конструкціям приділена велика увага як при розробці мови Сигнал (специфіковано три різновиди циклу з лічильником for, for lnv, for butfly), так і при реалізації компілятора ( для кожного різновиду циклу for розроблений спосіб оптимізації вихідного коду ).

Розглянемо запропоновані машинозалежні способи оптимізації вихідного коду по критерію часу для циклу for. Перший спосіб зв'язаний з питаннями організації лічильника ітерацій циклу та збільшення (зменшення) значення змінної циклу. Він базується на можливості у процесорах класу ОЦГЮ використання для вказаних дій адресних регістрів (АР). Робота з акумулятором і з адресними регістрами в ОЩЮ здійснюється паралельно, щр визначає ефективність і бажаність шрнайширшого використання АР-їв. Однак кількість адресних регістрів та їх розрядність у багатьох таких процесорах невеликі, щр обмежує застосування АР-їв для виконання дій, не зв'язаних з їх прямим призначенням, і приводить до необхідності врахування контексту кожної конкретної ситуації. Зміст запропонованого способу полягає в урахуванні обмежених можливостей адресних регістрів і використанні їх для збільшення (зменшення) змінної або лічильника циклу тільки тоді, якщр верхня межа циклу або кількість його ітерацій не перевищують максимально можливого для АР-їв значення. Крім того, при організації лічильників ітерацій для вкладених циклів треба враховувати співвідношення кількості адресних регістрів конкретного ОЦІЮ та глибини вкладеності циклів. У випадку, коли використання АР-їв неможливе, перевірка закінчення циклу виконується через акумулятор стандартним чином шляхом обчислення та аналізу різниці поточного значення змінної циклу і значення верхньої межі циклу. Другий спосіб оптимізації стосується швидкого звертання до елементів масивів всередині циклу. Цей спосіб базується на попередньо^ аналізі операторів тіла циклу, збиранні інформації про

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

Спосіб оптимізації вихідного коду для спеціалізованої конструкції for inv. Запропонований спосіб пов'язаний з характерним для алгоритмів ШПФ питанням обчислення двоїчно-інверсних чисел. Він базується на особливостях системи команд процесорів класу ОЦПС та семантичній гнучкості конструкції for inv і полягає у використанні для рахування двоїчно-інверсних чисел алгоритму зворотнього двоїчного складання зліва направо (тобто від старших розрядів до молодших) замість класичного алгоритму Рейдера.

Наведемо порівняльні розрахунки. Для ОЦПС першого покоління сімейства ТМ3320 при довжині масива N-512 за алгоритмом Рейдера загальна кількість'команд на алгоритм буде дорівнювати 8612 командам. При використанні алгоритму зворотнього складання - 5598 командам. Середня кількість команд на алгоритм для алгоритму Рейдера буде дорівнювати 8612 / 512 - 16.8 команди. Для алгоритму зворотнього складання - 5598 / 512 -10.9 команди. Відносний виграш другого алгоритму буде 8612 / 5598 - 1.538 раз. Різницевий виграш буде 8612 - 5598 - 3014 команд або 3014 команд *

0.2 мкс - 602. 8 мкс. -

Спосіб оптимізації вихідного коду для спеціалізованої конструкції for butfly. Запропонований спосіб оптимізації базується так само, як і спосіб для циклу for inv, на особливостях системи команд та архітектури процесорів класу ОЦПС, на частково функціональному характері конструкції for butfly і полягає у виключенні команд обчислення індексів масивів (вхідного, вихідного, коефіцієнтів) шляхом встановлення режимів адресації, відповідних законам зміни індексів, та у винесенні команд встановлення режиму адресації за межі циклу.

У дисертації показано, шр перевага від використання циклу for butfly та способу його оптимізації, в порівнянні з використанням звичайного циклу for, складає, для ОЦПС першого покоління сімейства процесорів TKG320, 10.2 мкс на кожну ітерацію цгаслу.

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

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

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

1. Запропонована класифікація і вроблений аналіз відомих

ШР, що застосовуються у галузі ЦОС при використанні процесорів класу ОЦПС. . .

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

3. Запропоновані способи оптимального по швидкодії викорис-

тання ресурсів процесорів цифрової обробки сигналів, шр належать до класу ОЦПС; .

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

6. Розроблені васоби реалізації мови Сигнал, які включені у

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

Основні положення дисертації відображені у 14 опублікованих роботах та у 2 науково-технічних звітах. .

1. Самофалов К. Г., Стеблянко В. Г., Марченко А. И., Ко линько Р. Ф. Диалог в кроссовых СПТ. // Диалог человек - ЭВМ.: Тез. докл. всесоюзн. науч.-техн. конф., часть 1, (Киев,1985), Киев, ИК АН УССР, с. 79-80.

2. Ананьевский С. А., Беднекко В. Е , Марченко А. И. Интерактивные средства кроссовой отладки программ реального масштаба времени. // Интерактивные системы : Тез. докл. межресп. науч.-техн. школы- семинара (г. Батуми,1984), Тбилиси, с.242- 243, 1984.

3. Бедненко Е а , Бею Т. Е , Марченко А. И., Тригуб Н. Ф. Реа-

лизация транслирующей части кроссовой системы подготовки программ. // Организация взаимодействия человека с ЭВМ : Сб. на-

учи. тр. , Киев: ИК АН УССР, 1985, с. 42-47.

4. Стеблянко R Г., Марченко А. И., Подобед Л. Ф. Разработка входных языков кроссовых систем подготовки программ реального времени. // Теория языков и автоматизация программирования.: Сб. науч. тр. , Киев, ИК АН УССР, с. 41-48, 1986.

5. Бею Т. Е , Марченко А. И., Колинько Р. Ф. Особенности задания семантики языков для программирования процессоров цифровой обработки сигналов. // Методы реализации систем программирования. : Сб. науч. тр., Киев, ИК АН УССР, с. 68-71,1987.

6. Марченко А. И. , Бею Т. а , ■ Стеблянко В. Г. и др. Исследование и разработка многопроцессорных систем для обработки сигналов в реальном масштабе времени. - Отчет по НИР. (промеиуточный), Киев, КПИ, 1987.

7. Марченко А. И., Бедненко R а Отладка программного

обеспечения систем реального времени в кроссовых системах подготовки программ. // Вестник КПИ, серия Автоматика и электроприборостроение. Вып. 24, 1987, с. 90-92. .

8. Марченко А. И., Каневский К1 С., Сергиенко А. М. Выбор язы-

ка для задач цифровой обработки сигналов в реальном времени. // Средства реализации систем программирования.: Сб. науч. тр., Ки-

ев, ИК АН УССР, с. 59-65, 1988.

9. Марченко А. И., Логинова Л. М., Третьяк А. Л. Проектирова-

ние фильтров на базе микропроцессоров сигналов. // Обработка сигналов на базе микропроцессоров и микро-ЭВМ.: Тез. докл.

респ. науч.техн. конф. (г.Таллинн, 1988), Таллинн, с. 29-31,1988.

10. Марченко А. И., Стеблянко В. Г., Механикова М. II Отображе-

ние специальных Функций языка программирования Сигнал на архитектуру процессора цифровой обработки сигналов. // Обработка сигналов на базе микропроцессоров и микро-ЭВМ.: Тез.

докл. респ. науч. техн. конф. (г. Таллинн, 1988), Таллинн, с. 29-31, 1988.

11. Марченко А. И., Бею Т. R, Колинько Р. Ф., Механикова М. П. Система автоматизации программирования процессоров сигналов . // Методы и микроэлектронные средства цифрового преобразования и обработки сигналов. SIAP-89: Тез.докл. науч.-техн. конф., том.2, (г. Рига, 1989), Рига, с. 261-263, 1989.

12. Марченко А. И., Стеблянко В. Г., Каневский Ю. С., Сергиенко А. М. Пакет прикладных программ подготовки программного обеспечения сигнальных процессоров. // INF0-89, Тез. докл. мездунар. сим-поз. , том. 1, часть. 1, (г. Минск, 1989), с. 380 - 382, Минск, 1989.

13. Марченко А. И., Светловская JL А., Васецкая А. П. и др. Реализация семантики выражения и оператора цикла for для языка высокого уровня Сигнал. // Вестник КПИ, серия Автоматика и электроприборостроение. Вып. 27, с. 12-17, 1990.

14. Стеблянко В.Г., Марченко А.И. , Бею Т.Б. и др. Исследование и разработка многопроцессорных систем для обработки сигналов в реальном масштабе времени. - Отчет по НИР (заключительный), Киев, КПИ, 1990.

16. Марченко А. И., Марченко JL А., . Колинько Р. Ф. Сравнение способов представления простого дерева разбора. // Вестник КПИ, серия Автоматика и электроприборостроение. Вып. 28, с. 8-12,1992.

16. Марченко А. И. Обзор и классификация языков высокого уровня, используемых в цифровой обработке сигналов.// Вестник КПИ, серия Автоматика и электроприборостроение. Вып. 29, с. 2128, 1992.

Автор

Марченко 0. I.