Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ

"КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ"

Автореферат

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

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

Спеціальність 05.13.05 Комп'ютерні системи та компоненти

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

Сергієнко Анатолій Михайлович

Київ 2011

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

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

Науковий консультант:

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

Сімоненко Валерій Павлович,

Національний технічний університет україни "КПІ",

професор кафедри обчислювальної техніки

Офіційні опоненти:

доктор технічних наук, старший науковий співробітник

Гамаюн Володимир Петрович,

Національний авіаційний університет,

завідувач кафедри прикладної інформатики

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

Теленік Сергій Федорович,

Національний технічний університет України "КПІ",

завідувач кафедри автоматики та управління в технічних системах

доктор технічних наук, старший науковий співробітник

Чеботарьов Анатолій Миколайович,

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

в.о. завідувача відділу високопродуктивних компютерних систем

Захист відбудеться "_23_" __травня__2011 р. о __14³⁰_ годині на засіданні спеціалізованої вченої ради Д 26.002.02 у Національному технічному університеті України "КПІ" (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 516).

Відгуки на автореферат у двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 02056, м. Київ, пр. Перемоги, 37, Вченому секретарю НТУУ "КПІ".

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

Автореферат розісланий "_22_" _квітня_____ 2011 р.

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

канд. техн. наук, доцент М.М. Орлова

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами

У дисертаційну роботу включені основні результати, які одержані автором з 1991 по 2010 рр. на кафедрі обчислювальної техніки Національного технічного університету України "КПІ" при виконанні госпдоговірних робіт (теми “Розробка універсального оперативного течешукача підвищеної точності виміру для визначення місцезнаходження течі в трубопроводах транспорту води, пари, газу, нафтопродуктів”, 2001 р., № ДР 0100U000088, "Розробка архітектури та побудова дослідного модуля спеціалізованого обчислювача на базі ПЛІС", 2008 р., № ДР 0107U012770) і держбюджетних робіт (теми "Теоретичне обґрунтування нової технології паралельних обчислень", 1997 р., № ДР 0196U01080, "Розробка основних елементів матрично-графової теорії паралельних обчислень", 1999 р., № ДР 0198U000650, "Розробка методів і засобів відображення регулярних алгоритмів у програмоване обчислювальне середовище", 2001 р., № ДР 0100U000953, "Методи та засоби відображення періодичних алгоритмів в обчислювальні системи на кристалі”, 2003 р., № ДР 0102U000595, "Теоретичне обґрунтування і дослідження методів підвищення ефективності використання апаратних засобів в системах цифрової обробки сигналів", 2005 р., № ДР 0104U000643, "Теоретичне обґрунтування та дослідження методів структурного проектування процесорів для обробки мультимедійних даних", 2008 р., № ДР 0106U002325, "Створення архітектурної концепції та методів структурного проектування мережевих процесорів з інтелектуальною обробкою пакетів даних», 2011р., № ДР 0109U002268). Більшість робіт завершено створенням діючих моделей і зразків обчислювальних модулів і процесорів.

Мета і завдання дослідження

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

Для досягнення поставленої мети в дисертації вирішуються наступні задачі:

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

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

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

5. Розробити методи відображення просторового ГСПД у конвеєрні ОС, які реалізуються в ПЛІС з використанням опису алгоритму і результуючої ОС мовою високого рівня, такою як VHDL, яка використовується в галузях ЦОС та для вирішення задач ЛА.

6. Розробити методи відображення алгоритмів обробки потоків даних у багатопроцесорні ОС для вирішення задач ЛА з мінімізацією простоїв їх процесорів.

7. Проаналізувати та удосконалити представлення даних в ОС для обробки потоків даних при ЦОС і для вирішення задач ЛА.

8. Створити засоби автоматизації відображення алгоритмів обробки потоків даних в ОС.

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

Об'єктом дослідження в цій роботі є паралельні ОС для обробки потоків даних.

Предмет дослідження математичні моделі алгоритмів обробки потоків даних і методи їх відображення в ОС з переважною реалізацією на основі ПЛІС.

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

Експериментальна перевірка наукових положень, пропозицій і одержаних результатів виконувалась за допомогою проектування обчислювальних засобів розробленими методами з використанням їх опису стандартними мовами VHDL і Verilog з їх подальшим моделюванням в симуляторі, компілюванням у схему на рівні вентилів і конфігуруванням у ПЛІС фірми Xilinx.

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

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

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

1. Критерій ефективності ОС, реалізованої в ПЛІС, який точніше враховує властивості як алгоритмів обробки потоків даних, так і елементної бази.

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

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

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

5. Способи побудови функціональних схем фільтрів зі скінченною імпульсною характеристикою, рекурсивних фільтрів з кратними затримками, реалізованих на ПЛІС, що мають продуктивність та відношення продуктивність-апаратні витрати, які у 1,2 - 2 рази більше, ніж у фільтрів, розроблених традиційними способами.

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

7. Спосіб представлення даних раціональними дробами, який при такій самій точності обчислень, що дає представлення з плаваючою комою, забезпечує обчислення ЦОС і вирішення задач ЛА зі зменшеними апаратними витратами на 25% та більш ніж у 1,2 рази збільшеною швидкодією.

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

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

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

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

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

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

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

Особистий внесок здобувача

Основний зміст дисертаційної роботи та її результати повністю відображені в опублікованих наукових роботах автора. Основний зміст дисертації представлено 62 наукових роботах, з них в 13 одноосібних роботах [1, 4, 8, 9, 12-15, 18, 21-23, 58] і 49 роботах, що опубліковані у співавторстві. В роботах [3, 7, 29, 31, 56], які надруковані у співавторстві, автору належать алгоритми, які реалізовано в описаних системах, в роботах [2, 6, 10, 13, 27, 28, 30, 32-37, 47, 49] автором запропоновано методи і методики відображення ГСПД в структуру ОС, в [5, 41, 42, 51, 52, 55] автору належить метод відображення алгоритму в конвеєрну структуру і одержані структури ОС. В роботах [11, 25, 40, 43-46, 54, 57, 60, 61] автором запропоновані спосіб представлення даних та синтезовані структури пристроїв, в роботі [50] запропонована класифікація моделей алгоритмів обробки потоків даних, а в роботах [16, 17, 24, 26, 39, 45, 46, 53] автором узагальнені й уточнені одержані ним методи проектування конвеєрних ОС і досліджені результати їхнього практичного застосування. Прикладні аспекти застосування результатів розглянуті в роботах [20, 38, 48, 59, 62].

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

Апробація результатів дисертації

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

І - ІІІ та V - VІIІ міжнародних конференціях "Parallel Processing and Applied Mathematics" (PPAM'94, Czestochova, 1994, PPAM'97, Zakopane, 1997, PPAM'99, Kazimierz Dolny, 1999, PPAM'2003, Czestochova, 2003, PPAM'05, Poznan, 2005, PPAM'07, Gdansk, 2007, PPAM'09, Wroclaw, 2009, Poland), міжнародному семінарі "Parallel Numerics'94" (Smolenice, Slovakia, 1994), міжнародній конференції, присвяченій пам'яті акад. С.А. Чумихіна (Київ, 1995), I та VII міжнародних конференціях "Автоматизація проектування дискретних систем" (CADDD'95, 1995 і CADDD'07, 2007, Мінськ, Республіка Беларусь), міжнародній конференції “International Conference on Signal Processing, Application and Technology” (ICSPAT'95, Boston, USA), 7-й міжнародній конференції "Parallel Architectures and Cellular Automata" (Parcella'96, Berlin, Germany, 1996), I та ІІІ міжнародних конференціях "Parallel Computing in Electrical Engineering" (PARELEC'98, Bialystok, 1998, PARELEC'2002, Warsaw, 2002, Poland), міжнародному симпозіумі "Комп'ютери у Європі. Минуле, сучасне і майбутнє" (Київ, 1998), 24-й міжнародній конференції "Euromicro Conference on Parallel and Distributed Processing" (Euromicro'98, Vasteras, Sweden, 1998), II - IV і ХI регіональних конференціях “Reprogramowalne uklady cyfrowe” (RUC'99, 1999, RUC'2000, 2000, RUC'2001, 2001, RUC'2008, 2008, Szczecin, Poland), міжнародній конференції "International Active-VHDL Conference" (Харків, 2001), міжнародній конференції "Масштабируемые системы и компьютерные сети" (SCALNET'2004, Кременчуг, 2004), міжнародній конференції "Информационные технологии в управлении энергетическими системами" (Київ, 2005), І, ІІ та ІІІ міжнародних конференціях "Моделювання" (Київ, 2006, 2008, 2010), 9-й та 10-й міжнародних конференціях "Досвід розробки і застосування САПР в мікроелектроніці" (CADSM'2007, CADSM'2009, Львів, Поляна, 2007, 2009), 14-й міжнародній конференції "Mixed Design of Integrated Circuits and Systems" (MIXDES'2007, Ciechocinek, Poland, 2007), міжнародній конференції (CODATA-21, Київ, 2008), 2-й міжнародній конференції "East-West Design & Test" (EWDTS'08, Львів, 2008), ювілейній міжнародній науково-практичній конференції 50-річчя створення кафедри ОТ (Київ, 2010).

Публікації. Основні положення дисертації викладені у 62 роботах. Серед них 1 монографія, 25 статей у провідних фахових часописах і збірниках (10 без співавторів), 25 статей у матеріалах міжнародних конференцій, 3 тези та 8 статей в інших фахових часописах і збірниках.

Структура та обсяг дисертації

Дисертаційна робота складається зі вступу, шести розділів, висновків, списку використаних джерел з 310 найменувань, містить 27 таблиць та 110 ілюстрацій. Робота містить 286 сторінок основного тексту, 59 сторінок з таблицями та ілюстраціями і 20 сторінок використаних джерел. Повний обсяг роботи 373 сторінки.

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

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

У першому розділі розглянуті основні задачі, алгоритми та пристрої обробки потоків даних, вимоги до елементної бази та засобів проектування відповідних ОС.

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

В результаті аналізу існуючих алгоритмічних моделей обробки потоків даних була складена їх класифікація. Основна класифікаційна ознака - статичність розкладу виконання акторів, яка дозволяє подальшу апаратну реалізацію алгоритму. За цією класифікацією вибрано граф синхронних потоків даних (ГСПД, synchronous dataflow graph, SDF) як основну модель для задання алгоритмів. Направлена дуга ГСПД передає дане миттєво або з затримкою у своєму буфері типу FIFO. В ГСПД кожен актор запускається при наявності даних на його входах, протягом циклу моделювання генерує в інцидентні дуги і споживає з них дані, число яких є сталим в кожному циклі. Причому конфігурація станів потоків ГСПД (множини даних в дугах з відповідними індексами) на початку кожного циклу є сталою. Однорідний ГСПД відрізняється тим, що усі актори протягом одного циклу спрацьовують по одному разу. Таким чином, ГСПД представляє собою граф однієї ітерації алгоритму з доданою інформацією про міжітераційні звязки. При цьому дуги, які замикають ациклічний ГСПД в циклічний граф, мають буфери FIFO та відповідають міжітераційним залежностям. Сигнальний граф, який застосовується в проектуванні ОС для ЦОС, є аналогом однорідного ГСПД.

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

Згідно з поширеним підходом, розклад спрацьовування операцій шукають для одного циклу виконання ГСПД з плануванням обчислень для його ациклічної частини. Тут використовують алгоритми спискового планування, силового планування, розфарбування графа, метод з вирівнюванням положення операторів за лівою границею простору ресурси - час (метод лівої границі - left edge scheduling). Але їх безпосереднє застосування дає низьке завантаження ресурсів на початку та у кінці циклу. Для урахування циклічності алгоритму аналізують граф конфліктів ресурсів і операцій, а також граф інтервалів існування змінних.

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

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

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

Вперше була запропонована методика моделювання ГСПД з використанням мови VHDL. При цьому було встановлено, що за допомогою VHDL можна як моделювати алгоритм обробки синхронних потоків даних на існуючих стимуляторах, так і реализувати його апаратно з періодом виконання L = 1 такт, наприклад, в ПЛІС, завдяки чому прискорюється проектування ОС. Також була показано, що при орієнтації на апаратну реалізацію алгоритму, слід використовувати однорідний ГСПД, так як відображення неоднорідного (multirate) ГСПД є значно складнішим і потребує перевірки відсутності блокувань.

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

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

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

За критерії оптимізації приймаються період виконання алгоритму Q_T=Lt_C і cума зважених кількостей ПЕ різного типу: Q_S =? С_pq_p, де L - число тактів періоду, t_C -тривалість такту, яка дорівнює довжині критичного шляху проходження сигналу від одного регістра до іншого, С_p - апаратна складність ПЕ p-го типу, q_p - кількість ПЕ p-го типу. Інтегральним критерієм є відношення продуктивність-апаратні витрати Q = 1/(Q_T Q_S).

Через великі затримки у лініях зв'язку, в ПЛІС важливо досягати конвеєрної обробки даних з мінімальною довжиною критичного шляху. При відображенні ГСПД у ПЛІС з L > 1 в затримку критичного шляху додаються затримки мультиплексорів. У ПЛІС апаратні витрати мультиплексорів можуть суттєво перевищувати витрати регістрів і суматорів. Тому доцільно мінімізувати як число ПЕ, так і кількість входів їх мультиплексорів, яка крім того, пропорційна складності ліній зв'язку. Результуючі критерії оптимізації для більшості проектів ЦОС на ПЛІС фірми Xilinx визначені як наступні:

Q_S = n_R + n_А + 20n_M + (0,28…0,57)n_X ;

Q_Т = L(n_А + (1,9…2,3)n_М + (0,5…0,6) n_Х) ,

де n_R - число регістрів в ОС, n_А - число суматорів; n_M - число блоків множення; n_X - число входів мультиплексорів; n_А, n_М, n_Х - числа суматорів, блоків множення, мультиплексорів, відповідно, які стоять у критичному шляху; діапазон коефіцієнтів залежить від серії ПЛІС.

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

Будь-який граф алгоритму G_A, в тому числі ГСПД, граф залежності даних, який йому відповідає, задається матрицею інцидентності A = ||а_i,j||_NM, де a_i,j = 1, якщо дуга j графу G_A кінцем інцидентна i-й вершині або a_i,j = 1, якщо вона інцидентна i-й вершині оператора і a_i,j = 0 при відсутності інцидентності, N і M число вершин і дуг графу G_A.

У загальному випадку, просторовий ГСПД представляється в n-вимірному цілочисельному просторі ZZZ ⁿ. Вектори K_i ZZZ ⁿ ототожнюються з вершинами графу G_A, тобто вони є тегами цих вершин. Координати векторів K_i, можуть мати різну інтерпретацію. Частина координат векторів K_i представляють координати K_Si ПЕ, в якому виконується i-й оператор, а інша частина K_Тi кодує момент виконання цього оператора K_i = . В іншій інтерпретації, наприклад, при відображенні гнізда циклів алгоритму, у ядрі якого виконується цей оператор, вектор K_i дорівнює набору індексів змінних.

За іншими координатами векторів K_i може вестись відлік, наприклад, рівнів ієрархії алгоритму і структури, типу оператора та ПЕ, затримки виконання оператора, кодуватись інформація про особливості операторів і ПЕ, таких, як необхідність конвеєрної реалізації, вказівка напрямку оптимізації і т.і. Далі розглядатиметься розмірність простору n = 3. Тоді i-й оператор просторового ГСПД ототожнюється з вектором K_i = (s, p, t)^T, (i = 1...N), де p - тип операції, s просторова координата, t - часова координата.

Вершини ГСПД, як правило, генерують мітки, що відповідають окремим змінним x_j , причому на всі вихідні дуги однієї вершини передається одна й та сама змінна x_j. Якщо вершина видає змінні x_і, x_j у вихідні дуги, то необхідно розщепити її на дві вершини, одна з яких генерує x_і, а інша - x_j.

Аналогічно відповідності вершин операторів, кожна змінна x_j алгоритму ототожнюється з n-вимірним вектором D_j ZZZ³, (j = 1...M). Згідно з визначенням матриці А, яка має елементи a_l,j, a_i,j, виконується рівність

D _j = K_l - K_i = a_l,j K_l + a_i,j K_i, (1)

де K_i відповідає оператору з результатом x_j, а K_l оператору, для якого x_j - вхідний операнд, тобто K_i безпосередньо передує K_l.

Множини векторів K = {K_i} і D = {D_j} взаємозв'язані так само, як множини вершин і дуг графа алгоритму. Таким чином, представлення ГСПД в багатовимірному просторі означає його кодування матрицями векторів K_i, D_j, а також матрицею А на основі (1). Щоб точно задати багатовимірний ГСПД, введено наступні визначення:

Конфігурацією алгоритму (КА) є трійка С_А = (K,D,A), де K = (K₁,...,K_N) - матриця векторів-вершин K_i = (s_i, p_i, t_i)^Т ZZ³; D = (D₁,..., D_M+1) - матриця векторів-дуг D_j = (s_j, p_j, t_j)^Т ZZ³; A = ||а_i,j||_N(M+1) - матриця інцидентності графа G_A. Ця матриця доповнена M+1-м стовпцем з елементом а_р,M+1 = 1, що відповідає базисному вектору D_M+1 = D_В, що з'єднує початок системи координат простору ZZ³ з довільним вектором-вершиною D_В = K_р K. У загальному випадку, кількість таких стовпців дорівнює числу компонент звязності G_A.

Якщо G_A ГСПД, то КА представляє собою просторовий ГСПД. На відміну від графа залежностей даних, у такого графа є вектори-дуги D_Dj, які відповідають залежностям між і-ю та і - n -ю ітераціями алгоритму. Вони навантажені затримками FIFO глибиною n і належать до замкнених циклів графа. Тобто D_Dj відповідає змінним x_і-1,..., x_і-п, які зберігаються в буфері FIFO дуги.

Розглянемо алгоритм рекурсивного фільтра другого порядку з формулою: y[i] = x[i]+ay[i2]+by[i1]. Ця формула обчислюється програмним циклом:

for i = 1, N do

St1: y1[i] = a*y[i2]; St2: y2[i] = b*y[i1];

St3: y3[i] = x[i]+y1[i]; St4: y[i] = y2[i]+y3[i];

end.

В ньому операторам St1,...,St4 відповідають вектори-вершини K_i = = (s,p,q,t)^T, (i=1,...,4) просторового ГСПД, де s - просторова координата, p - тип операції, q часова координата відліку ітерацій алгоритму, t - часова координата відліку тактів в ітерації. Змінним y[i],...,у3[i] відповідають вектори-дуги D_j, причому змінні y[i1], y[i2] ототожнюються з векторами-дугами D_D1, D_D2 , які мають затримки на 1 та 2 ітерації.

Конфігурацією структури (КС) є трійка C_S = (K_S, D_S, A), де K_S = (K_S1,...,К_SN) і D_S = (D_S1,...,D_S(M+1)) матриці векторів-вершин K_Si = (k_Si,1,...,k_Si,m)^Т ZZ^m і векторів-дуг D_Sj = (d_Sj,1,...,d_Sj,m) ZZ^m, що дорівнюють координатам ПЕ, в яких виконується i-й оператор та відносним координатам лінії зв'язку, по якій передається j-а змінна, відповідно; A матриця інцидентності ГСПД. У простому випадку, K_Si = (s_i, p_i)^Т ZZ².

Конфігурацією передування (КП) є трійка C_Т = (K_Т,D_Т,A), де K_T = (K_Т1,...,K_ТN) - матриця векторів-вершин K_Тi = (k_Ti,1,...,k_Ti,(n-m))^T ZZ^nm, які означають моменти виконання i-х операторів і D_Т = (D_Т1, ..., D_Т(M+1)) матриця векторів-дуг D_Тj = (d_Tj,1,...,d_Tj,(n-m))^T ZZ^nm, які відповідають затримкам передачі j-х змінних. У найпростішому випадку K_Тi = (t_i) ZZ. Тоді матриці K_T відповідає вектор часової розгортки Т = (t₁,...,t_N)^Т, який вказує такти виконання операторних вершин.

Для просторового ГСПД і відповідних йому конфігурацій доведено наступні твердження.

Матриці КА зв'язані між собою лінійними залежностями, які випливають з (1):

D = KA; K = D_О A^-1_O , (2)

де A^-1_O інверсна матриця остова ГСПД. Таким чином, маючи наперед задані координати векторів-дуг D_ОjD_O остова графу, які характеризують затримки виконання операторів, за формулами (2) знаходяться шукані координати ПЕ, задані матрицею K.

КА є коректною, якщо в матриці K відсутні однакові вектори, тобто

K_i, K_j (K_i K_j, i j ) _. (3)

Якщо в ГСПД є цикли, то повинна бути нульовою сума векторів-дуг D_j, які входять у будь-який цикл графа, тобто для i-го циклу

? b_i,j D_j = 0, (4)

де b_i,j - елемент i-ї строки цикломатичної матриці ГСПД.

Размещено на http://www.allbest.ru/

КП C_T для ГСПД є коректною відносно часової функції R, якщо

i,r = 1,...,N; j = 1,...,M+1;

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

Розклад виконання операторів для просторового ГСПД, що виконується з періодом L тактів, є коректним, якщо оператори, які відображаються в один ПЕ, виконуються в різних тактах, тобто

Размещено на http://www.allbest.ru/

КА лінійним відображенням або розщепленням своїх компонентів перетворюється в КС і КП так, що:

_. (7)

За умови, що КА, КП та розклад виконання операторів є коректними, тобто задовольняють умовам (3) (6), одержана за умовою (7) модель ОС буде виконувати заданий алгоритм у конвеєрному режимі з періодом L тактів.

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

K_i,K_jK_p,q(k_i = k_j = p, s_i = s_j = q), |K_p,q| ? L, (8)

де K_p,q - множина векторів-вершин операторів p-го типу, які відображаються в q-й ПЕ p-го типу (q=1,2,… q_pmax).

На рис. 1,а показаний приклад ГСПД у двовимірному просторі, а на рис.1,б відповідний йому граф залежностей даних (ГЗД).

Размещено на http://www.allbest.ru/

Рис. 1. Приклад ГСПД а) і відповідного йому ГЗД б).

При цьому, згідно з умовами (3) (6), КА і КП цього ГСПД, а також розклад, представлений ГЗД, є коректними при L = 3. Цей приклад показує наступне:

є можливість складати розклад виконання операторів періодичного алгоритму (ГЗД на рис.1 є періодичним), коли завантаженість ПЕ наближається до 100%;

протягом одного періоду виконання алгоритму ПЕ можуть обчислювати до трьох сусідніх ітерацій, причому в довільному порядку (другий ПЕ - в порядку 1-2-3, третій ПЕ - в порядку 2-1-3);

вершини, які з'єднані векторами ітераційної залежності (D_D1, D_D2), виконуються в одному такті, тобто, вони коректно забезпечують передачу даних між ітераціями.

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

На першому етапі виконання методу вершини і дуги ГСПД розміщуються в тривимірному просторі ZZ³ як множини векторів K_i и D_j з урахуванням умов (2)(6), (8), тобто формується початкова КА. Мінімізується число ПЕ в структурі шляхом виконання вимоги: |K_p,q|>L, коли число вершин, які відображаються в один ПЕ, прямує до L. Завдяки цьому, мінімізується число ПЕ в структурі ОС, яке прямує до мінімально можливого значення для заданого алгоритму і параметру L.

Слід відзначити, що перестановки вершин відносно осі часу оt, які відбуваються на цьому етапі, еквівалентні оптимізації алгоритму відомим способом ресинхронізації (retiming). Таким чином, вирішення пр-складної задачі ресинхронізації значно спрощується завдяки відкиданню заздалегідь невигідних рішень.

На другому етапі просторовий ГСПД урівноважується. Для цього розглядається ациклічний підграф ГСПД без дуг D_Dj із затримками. Під час врівноваження у всі дуги підграфу додаються проміжні вершини операторів затримки (регістрів). У результуючій врівноваженій КА всі вектори-дуги, крім дуг D_Dj, дорівнюють D_j = (a_j, b_j, 1)^Т або D_j = (a_j, b_j, 0)^Т. В такому ГСПД вершини-оператори формують яруси, відстань між якими за координатою часу оt дорівнює 1 такт. Врівноважена КА оптимізується через взаємні перестановки векторів-вершин з одного ярусу. При цьому досягається як мінімізація числа регістрів, так і числа входів мультиплексорів. Застосовуються такі стратегії, як алгоритм лівої границі, стратегія прямування завантаженості ПЕ до повної, тобто |K_p,q|>L. Результуючі структура ОС і розклад виконання операторів алгоритму одержуються згідно з (7).

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

M_S = M M₀

де M загальна кількість векторів D_j в ГСПД, M₀ число векторів D_i,j = =(0, 0, t_i,j)^T, M_v,i число векторів D_i,j, які відображаються в одну лінію зв'язку.

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

Пошук часової складової відображення ГСПД полягає в підстановці мінімальних допустимих значень часових координат у матрицю D_ТО досконалого остову, в обчисленні шуканих координат векторів-вершин K_Тi з матриці K_T за правим рівнянням (2) і знаходженні координат решти векторів D_Tj матриці D_Т за лівим рівнянням (2) з перевіркою умов (4) і (6). Доведено, що розклад, одержаний таким чином, відповідає розкладу, складеному за принципом найшвидшого призначення (ASAP). Також доведено, що мінімізація об'єму пам'яті ПЕ досягається мінімізацією координат векторів D_Tj .

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

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

У третьому розділі представлені метод і способи проектування конвеєрних обчислювачів, орієнтовані на реалізацію в ПЛІС. Запропоновано високорівневий опис періодичного алгоритму мовою VHDL. Розроблено метод відображення просторового ГСПД в структуру конвеєрного обчислювального пристрою (ОП), який забезпечує максимальне врахування властивостей елементної бази ПЛІС та проектування ОП на рівні регістрових передач.

На першому етапі синтезу формується просторовий ГСПД згідно з умовами (2)(6), (8) так само, як це виконується за методом синтезу ОС для обробки потоків даних шляхом трансформації моделі просторового ГСПД, описаному в другому розділі. При цьому мінімізується кількість таких ресурсів, як суматори і особливо - блоки множення.

На другому етапі виконується урівноважування КА з мінімізацією числа регистрів та входів мультиплексорів. В результаті формуються L множин операторів, які відповідають умові (8), причому m-а множина K_m вміщує оператори, які відповідають векторам-вершинам, для яких

K_i = (s_i, p_i, t_i)^T, m t_i mod L , m = 0, 1,…, L1.

Для цього в результуючій КА виділяються яруси, які відстають один від одного на L тактів вздовж осі оt; вершини цих ярусів формують множини K_m. Також формуються множини K_p,Q векторів-вершин операторів p-го типу, які відображаються в q-й ПЕ. Кожна з цих множин позначається унікальним іменем, наприклад, upq. Таким чином, кожному з операторів, які позначені векторами K_i, ставиться у відповідність єдина пара: <upq, t>, де upq означає імя змінної (сигналу), яка зберігається у відповідному регістрі ПЕ, а t - номер такту, в якому виконується присвоювання цій змінній, який обчислюється за модулем L.

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

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

Спочатку описується оператор процесу синхронізації, який генерує фази алгоритму, наприклад, cycle = 0,1,…, L1. Потім описується оператор процесу функціонування ОП наступним чином. В ньому окремими операторами описується присвоюванння змінним, які відповідають векторам D_Dj із затримками. обчислювальний система потік дані

Далі в цьому операторі процесу у межах дії умовного оператора, який описує зміну станів за фронтом синхросерії, ставиться оператор case cycle, в якому розміщено L альтернатив від 0 до L1. Причому в t -й альтернативі ставляться оператори присвоювання сигналу upq результату відповідної операції, яка відмічена парою < upq, t >.

Результуюча VHDL - модель ОП може бути протестована та скомпільована стандартним компілятором-синтезатором звичайним порядком. Таким чином, за запропонованим методом формально одержується VHDL-опис результуючого проекту ОП, який придатний для синтезу ОП на ПЛІС або замовленій НВІС і який має мінімізовані апаратні витрати та тривалість тактового інтервалу. Причому власне сама структура фільтра не будується. Завдання побудови структури ОС перекладається на компілятор-синтезатор, наприклад, Synplify фірми Synopsys, який розпізнає семантику операторів мови VHDL, що кодують розділення ресурсів за різними тактами виконання.

...