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

Також розроблено способи синтезу буферних схем, які дають змогу проектувати буферні схеми з ефективним використанням бібліотечних компонентів ПЛІС, таких як блоки пам'яті, буфери FIFO з відводами.

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

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

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

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

У четвертому розділі досліджені питання проектування конвеєрних обчислювачів для ЦОС. Вперше були спроектовані та випробувані конвеєрні процесори ШПФ з основами 8 і 16, які відрізняються від процесорів з основами 2 і 4 меншими кількістю блоків множення та об'ємом пам'яті, а також більшою точністю обчислень. Розроблені процесори двовимірного дискретного косинусного перетворення показали високі параметри швидкодії при низьких апаратних витратах у порівнянні з рядом кращих аналогів.

Метод синтезу конвеєрних ОП впроваджено в програмі генератора фільтрів зі скінченною імпульсною характеристикою, яка генерує моделі фільтрів на VHDL з апаратними витратами, що в середньому, на 25% менші за витрати аналогів та з тактовою частотою, яка в 1,15-1,5 разів вища, ніж у аналогічних фільтрів і досягає 550 МГц в ПЛІС Xilinx Virtex-5. Програма генератора впроваджена у засобі проектування Aldec ActiveHDL.

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

Цифровий фільтр прийнято описувати передаточною характеристикою H₀(Z) від комплексної змінної Z. Члену Z^-k в формулі H₀(Z) відповідає затримка на k ітерацій або ланцюжок з k регістрів затримки. Якщо в фільтрі збільшити кількість таких регістрів в n разів, то одержується фільтр з кратними затримками з характеристикою H_n(Z) = H₀(Zⁿ). Застосовуючи спосіб маскування амплітудо-частотних характеристик послідовно зєднаних ступенів фільтрів з кратними затримками, одержують високоякісні цифрові фільтри. ГСПД такого фільтра має вектори-дуги D_Dj із затримками величиною п, що дає змогу одержувати на його основі структури фільтрів з максимальною конвеєризацією.

Розроблено спосіб структурного синтезу рекурсивних фільтрів із кратними затримками, який забезпечує мінімізацію тактового інтервалу і апаратних витрат, включаючи мультиплексори при заданому L. Завдяки цьому способу вперше синтезовані рекурсивні цифрові фільтри з параметрами, що динамічно змінюються в широкому діапазоні. У випробуваному в ПЛІС рекурсивному фільтрі нижніх частот частота зрізу змінюється плавно в межах 0,015 - 0,4 від частоти дискретизації, рівень згасання складає не менше 7580 дб, а нахил АЧХ у перехідній смузі не менше 100 дб/октава. Апаратні витрати складають 706 CLB slices і 3 блоки множення при L=8 в ПЛІС Xilinx Virtex2P.

Запропоновано для мінімізації похибок обчислень в ЦОС, а також для вирішення задач лінійної алгебри (ЛА) застосувати представлення даних у вигляді раціональних дробів. Раціональний дріб a/b - це числовий обєкт, який складається з цілочисельних чисельника a і знаменника b. Цей дріб може з досить високою точністю наближатись до заданого числа x ? a/b. Раціональні дроби мають нескладний апарат арифметичних дій. Так, множення a/b на c/d дорівнює aс/(bd), а додавання цих дробів - (ad+bc)/(bd). При цьому власне ділення цілих чисел не виконується.

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

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

У п'ятому розділі метод синтезу конвеєрних ОС адаптовано до проектування обчислювачів для вирішення задач ЛА.

Запропоновано метод проектування паралельних ОС на основі комплексного використання відображення просторового ГСПД і решітчастого графа алгоритму. На першому етапі синтезу за цим методом базова функція f (чи ряд таких функцій) початкового алгоритму відображається у внутрішню структуру конвеєрного ПЕ. При цьому використовується метод синтезу конвеєрних ОС, який описано у другому розділі. Результатом етапу є розклад виконання операторів алгоритму обчислення функції f, причому обчислення виконуються в конвеєрному режимі з циклом T_С за час T_D = pT_С тактів, де p=2,3,... число функцій f, які виконуються в ПЕ паралельно. При синтезі структури ПЕ мінімізуються апаратні витрати і період тактового інтервалу.

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

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

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

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

Встановлено, що похибка розкладання Холецького при реалізації в арифметиці раціональних n-разрядних дробів оцінюється як 2ⁿMN^1/3, де N - розмірність матриці, M математичне сподівання вхідних даних. Моделюванням встановлено, що ОС з арифметикою дробів при n = 32 і М = = (0,01 1000) має таку саму або кращу точність обчислень, що і ОС з плаваючою комою одинарної точності. Крім того, при реалізації ОС на основі ПЛІС досягається баланс витрат в числі блоків множення і логічних схем. Якщо початкові дані представляють цілочисельну зумовлену задачу ЛА, то при достатній розрядності раціональних дробів, в такій ОС одержуються точні результати.

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

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

Запропоновано спосіб відображення ГСПД в структуру мультимедійного SIMD-процесора, який реалізований в засобі для трансляції ГСПД в асемблерну програму з командами Intel ММХ. Метод оснований на трансформації просторового ГСПД таким чином, щоб він максимальною мірою покривався шаблонами команд з системи команд ММХ. Випробування згенерованих програм, таких як програма хвильового фільтру 5-го порядку, показало, що в процесорі PentiumPro середня кількість виконуваних команд протягом одного такту (рівень суперскалярного паралелізму) складає 1,56, а сумарні простої процесора через заповнення буферу перестановки даних, непопадання в кеш тощо мінімізовані до 10%, що свідчить про високу ефективність методу.

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

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

Робота присвячена побудові методології проектування апаратних і апаратно-програмних ОС для обробки потоків даних, які адаптовані для реалізації в ПЛІС, НВІС або багатопроцесорних ОС. В роботі отримані такі теоретичні та практичні результати:

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

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

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

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

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

6. За допомогою методу синтезу конвеєрних обчислювальних пристроїв для ПЛІС вперше були спроектовані конвеєрні процесори ШПФ з основами 8 і 16, які відрізняються від інших процесорів ШПФ меншими апаратними витратами, а також більшою точністю обчислень. Розроблені за цим методом процесори прямого і зворотнього дискретного косинусного перетворення показали високу швидкодію при низьких апаратних витратах в порівнянні з рядом кращих аналогів.

7. На основі методу синтезу конвєрних обчислювальних пристроїв для ПЛІС розроблено удосконалений спосіб побудови функціональних схем фільтрів зі скінченною імпульсною характеристикою та вперше створено методику проектування рекурсивних фільтрів з кратними затримками, реалізованих на ПЛІС, що мають характеристики продуктивності та відношення продуктивність-апаратні витрати, які у 1,2 - 2 рази більше, ніж у фільтрів, спроектованих традиційними способами. У результаті синтезу ряду практичних і тестових структур цифрових фільтрів встановлено, що метод синтезу конвєрних обчислювальних пристроїв для ПЛІС дає змогу проектувати фільтри з заданим періодом L та мінімальними апаратними витратами. Причому структури рекурсивних фільтрів з L = 2 або 3 мають до двох разів менші апаратні витрати, ніж фільтри з L = 1, які одержані традиційним методом і мають таку саму пропускну спроможність.

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

9. Для вирішення задач ЛА і ЦОС вперше запропоновано представлення даних у вигляді раціональних дробів. Його застосування в процесорі для ковзного перетворення Фур'є, процесорі для авторегресійного аналізу сигналів дало змогу одержати як високу точність обчислень, так і невеликі апаратні витрати та високу тактову частоту. Застосування такого представлення для побудови спецпроцесорів на основі ПЛІС, призначених для обернення теплицевих матриць, виконання алгоритмів Дарбіна, Холецького та інших показало, що в ОС зменшуються апаратні витрати принаймні на 25% і збільшується продуктивність на 25% у порівнянні з ОС, в якій використовується плаваюча кома при такій самій точності обчислень.

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

11. Розроблено метод відображення просторового ГСПД в структуру SIMD-процесора, який, завдяки властивостям відображення ГСПД в багатопроцесорну ОС, вперше дав змогу формально складати високоефективні асемблерні програми обробки потоків даних з мінімізованими простоями як конвеєрів команд, так і пам'яті процесора. Розроблена на основі методу відображення просторового ГСПД версія транслятора виконує генерацію асемблерних кодів для мультимедійного сопроцесора, які забезпечують мінімізацію простоїв такого процесора, як Pentium-Pro, до рівня 10%.

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

1. Сергиенко А.М. VHDL для проектирования вычислительных устройств. К.: "ДиаСофт". 2003. 210 с.

2. Сергиенко А.М. Спецпроцессоры для авторегрессионного анализа сигналов // Электронное моделирование. - 2010. -Т.32, №2. -С. 87-96.

3. Сергиенко А.М. Пространственный граф синхронных потоков данных// Вісник НТУУ «КПІ»: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2010. -№.51. -с. 40-46.

4. Сергиенко А.М., Динамически перестраиваемые цифровые фильтры на ПЛИС / А.М. Сергиенко, Т.М. Лесик // Электронное моделирование. -2010. -Т.32, №6. -С. 47-56. - Запропоновано структури фільтрів, які перестроюються динамічно і синтезуються відображенням просторового ГСПД.

5. Сергиенко А.М. Реализация алгоритма Холецкого на ПЛИС/ А.М. Сергиенко, В.Л.Лепеха, Т.М Лесик. // Вісник НТУУ «КПІ»: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2010. -Т.52, -С. 40-45. Автором запропоновано представлення даних і структуру ОС.

6. Сергиенко А.М. Реализация перестраиваемых рекурсивных цифровых фильтров на ПЛИС / А.М. Сергиенко, Т.М. Лесик // Вісник НТУУ «КПІ»: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2010. -№52. -С. 47-51. Автором запропоновано спосіб реалізації фільтрів з кратними затримками.

7. Сергієнко А.М. Деякі особливості проектування мікроконтролерів для СНК / А.М.Сергієнко, В.Л.Лепеха // Вісник НТУУ «КПІ»: “ Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2009. -№50. -С. 70-73. Проаналізована будова ПЛІС і вироблено критерій ефективності структури, які в ній реалізовані.

8. Сергиенко А.М. Применение рациональных дробей в специализированных вычислителях // Вісник НТУУ «КПІ»: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2009. -№50. -С. 74-77. Запропоновано представлення даних в спеціалізованих обчислювачах.

9. Сергиенко А.М. Cпосіб демодуляції сигналів з багаточастотною модуляцією / А.М.Сергієнко, В.М. Мєлковська // Вісник НТУУ “КПІ”: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2008, -№48. -С. 8284. Запропоновано алгоритм ковзного дискретного перетворення Фурє в арифметиці дробів і виконано синтез схеми демодулятора.

10. Сергієнко А.М. Проектування обчислювачів з регістровими затримками // Вісник НТУУ “КПІ”: “Інформатика, управління та обчислювальна техніка”: зб. наук. праць. -2008, -№49. -С. 7376.

11. Сергиенко А.М. Алгоритмические модели обработки потоков данных / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. -2008. Т.30, №6. С. 4960. Автору належать критичний огляд моделей для задання алгоритмів обробки потоків даних і класифікація таких моделей.

12. Сергиенко А.М. Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. -2007. Т.29. №2. С. 4961. Розроблено метод відображення ГСПД в структуру ПЛІС, а також метод проектування структур цифрових фільтрів з багатократними затримками .

13. Сергієнко А.М. Досконалий кістяк графа алгоритма // Вісник НТУУ “КПІ”: “Інформатика і обчислювальна техніка”: зб. наук. праць. - 2007. №46. С. 6267.

14. Сергієнко А.М. Синтез структур для виконання періодичних алгоритмів з операторами керування // Вісник НТУУ “КПІ”, сер. Інформатика, управління та обчислювальна техніка. - 2007. № 47. С. 45-48.

15. Сергієнко А.М. Спецпроцесори для двовимірного дискретного косинусного перетворення / А.М. Сергієнко, В.Л. Лепеха, Т.М. Лесик // Вісник НТУУ “КПІ”: “Інформатика і обчислювальна техніка”: зб. наук. праць. -2007. № 47. С. 49-52. Автором виконано проектування процесорів методом відображення ГСПД.

16. Сергиенко А.М. Применение арифметики рациональных дробей для реализации метода сопряженных градиентов // Электронное моделирование. 2006. Т.28, № 1. С.3341.

17. Сергієнко А.М. Конфігурована обчислювальна система для вирішення задач лінійної алгебри / О.М. Клименко, А.М. Сергієнко, Ю.В. Шевченкo, С.Г. Овраменко // Электронное моделирование. 2005. Т.27, №1. С. 109114. Запропоновано метод відображення ГСПД в конвеєрну ОС .

18. Сергиенко А.М. Отображение алгоритма QR-разложения Гивенса в многопроцессорную систему // Электронное моделирование. 2004. -Т.26, №5. С. 4353.

19. Сергиенко А.М. Отображение алгоритмов обработки изображений в программируемых логических интегральных схемах / В.Л Лепеха, А.М. Сергиенко, Ю.В. Шевченко // Электронное моделирование. 2004. Т.26, №4. С. 7582. Автором запропоновано структуру процесорної матриці і алгоритми, які реалізовано в ній методом відображення ГСПД.

20. Сергиенко А.М. Особенности VHDL как языка параллельного программирования // Электронное моделирование. -2003. -Т 25, № 3.с.115-123.

21. Сергиенко А.М. Методика проектирования цифровых фильтров с помощью VHDL // Моделювання та інформаційні технології: зб. наук. праць. Ін-т проблем моделювання в енергетиці, НАН України. 2002. Вип. 12. С. 99107.

22. Сергієнко А.М. Генератор модулів фільтрів для ПЛІС / В.І. Василенко, О.М. Клименко, Л.М. Логінова, А.М. Сергієнко // Моделювання та інформаційні технології: зб. наук. праць. Ін-т проблем моделювання в енергетиці, НАН України. -2002. -Вип.12. -С. 13-18. Автором запропоновано методику автоматичного синтезу структур фільтрів.

23. Сергиенко А.М. Отображение регулярных алгоритмов в структуры специализированных процессоров / Ю.С. Каневский, С.Г. Овраменко, А.М. Сергиенко // Электронное моделирование. 2002. Т.24, №2. С. 4659. Автору належить метод відображення ГСПД в конвеєрну структуру .

24. Сергиенко А.М. Последовательная и параллельная реализация метода верхней релаксации при решении задач математической физики / Каневский Ю.С., Лепеха В.Л., Сергиенко А.М. // Электронное моделирование. 2000. T22, №6. С. 312. Автором запропоновано структуру процесорної матриці і алгоритми, які реалізовано в ній.

25. Сергиенко А.М. Последовательная и параллельная реализация метода минимальных невязок при решении задач математической физики / Р. Выжиковски, В.Л. Лепеха, А.М. Сергиенко // Электронное моделирование. 1999. Т.21, №6. С. 3547. Автором запропоновано структуру процесорної матриці і алгоритми, які реалізовано в ній.

26. Сергиенко А.М. Структурное проектирование рекурсивных цифровых фильтров / Ю.С. Каневский, Л.М. Логинова, А.М. Сергиенко // Электронное моделирование. 1995, - Т.17, № 3. -С. 18-22. Автором запропоновано метод відображення ГСПД в структуру фільтра .

27. Sergiyenko A. Applicaton specific processors for the autorgressive signal analysis / O. Maslennikow, A. Sergiyenko, N. Maslennikowa, P. Ratushnyak, M. Wozniak // 8-th Int. Conf. “Parallel Processing and Applied Mathematic”, PPAM'2009. Part I: “Lecture Notes in Computer Science”. -Berlin: Springer, 2010, V. 6068. P. 80-86. Запропоновано виконання алгоритмів в арифметиці раціональних дробів, які реалізовані в конвеєрному ПЕ.

28. Сергиенко А.М. Вычислительные модели параллельных алгоритмов, реализуемых аппаратно / А.М. Сергиенко, В.Л. Лепеха, Т.М. Лесик // Зб. праць ювілейної міжн. наук.-практ. конф. 50-річчя створення каф. ОТ. -Київ, 6-8 квітня 2010. -Київ: НТУУ «КПІ». -2010. -С. 125-127. Автором зроблено критичний огляд методів структурного синтезу ОС.

29. Сергиенко А.М. Динамически перестраиваемые цифровые фильтры на ПЛИС / А.М. Сергиенко, Т.М. Лесик // Зб. матеріалів міжн. наук. конф. «Моделювання-2010». -Київ: ІПМЕ НАН України. -2010. -Т.3. -С. 161-166. Запропоновано структури цифрових фільтрів, які перестроюються динамічно і які синтезуються відображенням просторового ГСПД.

30. Sergiyenko A.M. Tensor approach to the application specific processor design / A.M. Sergiyenko, O. Maslennikow, Y. Vinogradow // Proc.10^th Int. Conf. “The Experience of Designing and Application of CAD Systems in Microelectronics”, CADSM'2009, 24-28 Feb. 2009. -IEEE Library. -2009. -Р. 146-149. Зроблена критична оцінка тензорної методології і запропоновано метод відображення ГСПД в структуру спецпроцесора.

31. Sergiyenko A. Parallel Implementation of Cholesky LL^T Algorithm in FPGABased Processor / A. Sergiyenko, O. Maslennikow, V. Lepekha, A. Tomas, R. Wyrzykowski // “Lecture Notes in Computer Science”. Berlin: Springer. 2008. V. 4967. Р. 137-147. Запропоновано виконання алгоритму Холецького, який реалізовані з застосуванням методу відображення ГСПД.

32. Сергиенко А.М. Сперцпроцессоры для авторегрессионного анализа сигналов / А.М. Сергиенко, В.Л. Лепеха, О.В. Масленников // Тр. межд. конф. Моделирование2008. -14-16 мая 2008. -Киев: ИПМЭ НАН Украины. -2008. -Т2. -С. 499-503. -Автором синтезовано структури спецпроцесорів методами відображення ГСПД.

33. Sergiyenko А. Generator opisow VHDL blokow operacyjnych dzialajacych w arytmetyce ulamkowej / А. Sergiyenko, О. Maslennikow, P. Ratushniak // Prace XI Konferencji Naukowej „Reprogramowalne uklady cyfrowe”, RUC'2008. -Szczecin, Poland. -2008. -Р. 167-172. Автором запропоновано спосіб проектування цифрових фільтрів з кінечною імпульсною характеристикою.

34. Sergiyenko A. Mapping DSP Algorithms into FPGA / A.Sergiyenko, T. Lesyk, O. Maslennikow // Proc. of IEEE East-West Design & Test Symp., EWDTS'08. -Lviv, October 9-13, 2008. -Kharkov: KNURE. -2008. -Р. 343-348. Запропоновано метод відображення алгоритмів ЦОС в ПЛІС.

35. Сергиенко А.М., Лепеха В.Л. Масленников О.В. Сперцпроцессоры для авторегрессионного анализа сигналов / А.М. Сергиенко, В.Л. Лепеха, О.В. Масленников // Тр. межд. конф. “Моделирование-2008”. -14-16 мая, 2008. -Киев: ИПМЭ НАН Украины. -2008. -Т2. -С. 499-503. Автором синтезовано структури спецпроцесорів методами відображення ГСПД в ПЛІС.

36. Сергиенко А.М. Структурное проектирование рекурсивных цифровых фильтров / А.М. Сергиенко, О.В. Масленников // Тр. межд. конф. “Автоматизация проектирования дискретных систем”, CADDD'07. -Минск. -2007. -С.92-99. Запропоновано метод відображення ГСПД алгоритму рекурсивної фільтрації в конвеєрну структуру .

37. Sergyienko A. Implementation of Linear Algebra Algorithms in FPGA-based Fractional Arithmetic Units / A. Sergіyenko, O. Maslennikov, P. Ratushniak // Proc. 9-th Int. Conf. “The Experience of Designing and Application of CAD Systems in Microelectronics”, CADSM'2007. Lviv, Polyana, 2024 Feb., 2007. -2007. p.228234. Автором запропоновано виконання чисельних алгоритмів з застосуванням арифметики раціональних дробів.

38. Sergyienko A. Implementation of Cholesky LL^T-decomposition algorithm in FPGA-based rational fraction parallel processor / A. Sergyienko, O. Maslennikov, P. Ratushniak // Proc. 14-th Int. Conf. "Mixed Design of Integrated Circuits and Systems", MIXDES'2007. Ciechocinek, Poland. 2123 June, 2007. Technical University of Јуdџ. 2007. Р. 287292. Запропоновано виконання чисельних алгоритмів з застосуванням арифметики раціональних дробів.

39. Sergiyenko A. FPGA Implementation of the Conjugate Gradient Method / Maslennikow O., Lepekha V., Sergiyenko A. // Lecture Notes in Computer Science. Berlin: Springer. 2006. V. 3911. Р. 526533. -Автором виконано реалізацію алгоритму методом відображення ГСПД в багатопроцесорну конвеєрну структуру.

40. Sergiyenko A. Mapping DSP algorithms into FPGA / O. Maslennikow, A. Sergiyenko // Proc. IEEE Int. Symposium on Parallel Computing in Electrical Engineering, PARELEC'06. Poland: Bialystok, 13-17 Sept., 2006. -2006. Р. 208-213. Автором запропоновано метод відображення ГСПД алгоритму ЦОС в конвеєрну структуру .

41. Sergienko A. Sparse matrix solving on FPGA. / Sergienko A. Klimenko А. // Тр. межд. конф. “Информационные технологии в управлении энергетическими системами”. Киев,18-19 окт., 2005. -Киев:ИПМЭ НАН Украины. 2005. -С.4748. Запропоновано виконання алгоритму вирішення тьопліцевої системи рівнянь з застосуванням арифметики раціональних дробів.

42. Сергиенко А.М. Что делать с одним миллиардом транзисторов. Argc& Argv. Программирование/информационные технологии/стандарты. -2004. -Т.57, № 6. -С. 9-19.

43. Sergyienko A. Configurable Microprocessor Array for DSP Applications / O. Maslennikov, Ju. Shevtshenko, A. Sergyienko // Lecture Notes in Computer Science. Berlin: Springer. V. 3019. -2004. P. 3641. Автором запропоновано структуру процесорної матриці і алгоритми, які реалізовано в ній .

44. Sergiyenko A.M. Configurable encryption processor / V.I. Vasylenko, V.L. Lepekha, A.M. Sergiyenko // Proc. Int. Conf. SCALNET'2004. -in Bulletin of Kremenchuk State Polytechn. Univ. “Transactions of SCALNET'2004”. 2004. p.121123. Автором синтезовано конвеєрну схему, що реалізує алгоритм Монтгомері відображенням ГСПД .

45. Sergyienko A. Optymizacja architektury mikrokontrolerow przeznaczonych do realizacji w ukladach FPGA / Maslennikow O., Sergyienko A., Lacki M. // Prace VI Konferencji „Reprogramowalne uklady cyfrowe”, RUC'2003, Szczecin, 2003. -2003. -S. 87-92. Досліджено елементну базу ПЛІС і запропоновано критерій ефективності ОС, що реалізована в ПЛІС.

46. Sergyienko A. Configurable microcontroller array / Maslennikov O., Shevtshenko Ju., Sergyienko A. // Proc. of the 3-rd Int. Conf. on Parallel Computing in Electrical Engineering. PARELEC'2002. Warsaw, Poland. 2225 Sept. 2002. P. 4749. Запропоновано структуру процесорної матриці і алгоритми, які реалізовано в ній.

47. Sergyienko А. Implementation of Givens QR Decomposition in FPGA / А. Sergyienko, О. Maslennikov // Lecture Notes in Computer Science. Berlin: Springer. 2002. V. 2328. Р. 453459. Автором запропоновано нові версії алгоритма Гівенса, які відображаються методом програмної конвеєризації.

48. Sergyienko A. FIR filter soft core generator / A. Sergyienko, V. Vasylienko, O. Maslennikow // Prace IV Konferencji Krajowej „Reprogramowalne uklady cyfrowe”, RUC'2001. -Szczecin, Poland. -2001. -Р. 167-172. Запропоновано методику синтезу структур фільтрів та їхніх блоків множення.

49. Sergyienko A. A Method for Mapping DSP Algorithms into Pentium MMX Architecture. / Sergyienko A., Kaniewski J., Arefjev A., Kortshev D. //Proc 3-d Int. Conf. On Parallel Processing and Applied Mathematics, PPAM'99. Kazimierz Dolny, Poland. Sept. 14-17., 1999. 1999. Р. 348356. Запропоновано метод програмування SIMD-систем шляхом програмної конвеєризації .

50. Sergyienko A. Implementation of IIR Digital Filters in FPGA / A. Sergyienko, V. Lepekcha, J. Kaniewski, P. Soіtan // Pracy II Konferencji Krajowej „Reprogramowalne uklady cyfrowe”, RUC'99, Szczecin, 1999. -1999. -Р. 233-239. Автором запропоновано проектування рекурсивних фільтрів за допомогою відображення ГСПД.

51. Сергиенко А.М. Локально связанные вычисления - состояние и перспективы / Ю.С. Каневский, А.М. Сергиенко // Праці міжн. симпозіума "Компютери у Європі. Минуле, сучасне та майбутнє". -Київ: ІК НАН України. 1998. с.460467. Зроблено критичний огляд методів синтезу ОС і систолічних процесорів.

52. Sergienko A. A method for mapping DSP algorithms into application specific structures / Ju. Kanevski, A. Sergienko, O. Maslennikov, R. Wyrzykowski // Proc. 24-th Euromicro Conf. on Parallel and Distributed Processing, Euromicro'98, Sweden, Vasteras. -IEEE Comp. Soc. Press. -1998. -V. 1. -Р.365-371. Запропоновано метод відображення ГСПД алгоритму ЦОС в конвеєрну структуру .

53. Sergiyenko A. Mapping Regular Algorithms into Processor Arrays Using Software Pipelining / A. Sergiyenko, J. Kaniewski, O. Maslennikow, R. Wyrzykowski // Proc.Int. Conf. On Parallel Computing in Electrical Engineering, PARELEC'98. Poland, Bialystoc. Sept. 2-5, 1998. -1998. Р.197200. Запропоновано метод програмної конвеєризації на основі відображення ГСПД.

54. Sergienko A.M. A Method for Mapping Unіmodular Loops into Application Specific Parallel Structures / Kanevski Ju.S., Sergienko A.M., Guzinski A. // Proc. of the 2-nd Intern. Conf. "Parallel Proc. and Appl. Math. PPAM'97" -Zakopane, Poland, 1997. -1997. -Р. 362-371. Запропоновано задання гнізда циклів за допомогою ГСПД і метод його відображення.

55. Sergienko A.M. Processor Array for Signal Computing and Numerical Applications / Kanevski Ju.S., Sergienko A.M., Maslennikov O.V. // Proc. 7-th Int. Conf. "Parcella'96". Berlin: Akademie Verlag, Mathematical Research. 1996. V. 96. -Р. 47-58. Запропоновано алгоритми, які реалізовано в процесорній матриці методом програмної конвеєризації .

56. Sergienko A.M. Structured Design of Recursive Digital Filters / Ju.S. Kanevski, L.M. Loginova, A.M. Sergienko // Engineering Simulation. 1996. V.13. p. 381389. Автором запропоновано метод синтезу рекурсивних фільтрів відображенням ГСПД.

57. Sergienko A.M. Processor Array for Signal Computing and Numerical Applications / Ju.S. Kanevski, A.M. Sergienko, O.V. Maslennikov // Proc. of the Int. Conf. "ICSPAT'95" Boston. 1995. Р. 15631567. Запропоновано алгоритми, що реалізовані в ОС методом програмної конвеєризації.

58. Sergienko A.M. A Method for the Structural Synthesis of Pipelined Array Processors. / Ju.S. Kanevski, A.M. Sergienko, H. Piech // Proc. of the First Intern. Conf. "Parallel Proc. and Appl. Math. PРAM'94". Poland, Czestochova. 1994. Р. 100109. Автором запропоновано метод відображення ГСПД в конвеєрну структуру.

59. Sergienko A.M. Mapping Numerical Algorithms into Multipipelined Processors / Ju.S. Kanevski, A.M. Sergienko // Proc. of the Int. Workshop "Parallel Numerics'94", Smolenice. 1994. Р.192202. Запропоновано метод відображення ГСПД в багатопроцесорну структуру з конвеєрними ПЕ.

60. Sergiyenko A. Real time autoregressive processors / A. Sergiyenko, V. Simonenko, V. Lepekha // Abstracts of Int. Conf. “CODATA-21”. -Kyiv: NTUU ”KPI”. -2008. -Р.229-230. Запропоновано виконання чисельних алгоритмів з застосуванням арифметики раціональних дробів і методу відображення ГСПД.

61. Sergiyenko А. Implementation of linear algebra algorithms in the FPGA-based rational fraction arithmetic processor / А. Sergiyenko, О. Maslennikow // Abstracts of Int. Conf. “CODATA-21”. -Kyiv: NTUU ”KPI”. -2008. -Р. 224. Синтезовано структури спецпроцесорів методами відображення ГСПД.

62. Сергиенко А.М. САПР конвейерных вычислительных структур. / Ю.С. Каневский, Л.М. Логинова, А.М. Сергиенко // Тез. докл. межд. конф. "Автоматизация проектирования дискретных систем", CADDD'95. Минск. 1995. С. 143. Запропоновано метод відображення ГСПД в конвеєрну структуру.

АНОТАЦІЇ

Сергієнко А.М. Моделі, методи і засоби синтезу обчислювальних систем для обробки потоків даних. Рукопис.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 05.13.05 - Комп'ютерні системи та компоненти. Національний технічний університет України "Київський політехнічний інститут", м. Киів, 2011 р.

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

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

Ключові слова: граф потоків даних, ПЛІС, VHDL, відображення алгоритму, цифрова обробка сигналів.

Сергиенко А.М. Модели, методы и средства синтеза вычислительных систем для обработки потоков данных. Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 05.13.05 - Компьютерные системы и компоненты. Национальный технический университет Украины "Киевский политехнический институт", г. Киев, 2011г.

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

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

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

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

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

Разработаны также метод синтеза конвейерных ВС для ПЛИС, включая метод проектирования с использованием языка VHDL, метод отображения алгоритмов с операторами управления, а также способы синтеза буферных схем, отображения иерархических условных алгоритмов.

Методы адаптированы к синтезу ВС для цифровой обработки сигналов. При этом построены способ синтеза функциональных схем фильтров с конечной импульсной характеристикой, реализуемых в ПЛИС и программа генератора таких фильтров. Предложен способ структурного синтеза рекурсивных фильтров с кратными задержками. Методы проверены при синтезе ряда структурно-функциональных схем конвейерных ВС для цифровой обработки сигналов, таких как процессоры быстрого преобразования Фурье, дискретного косинусного преобразования, цифровые фильтры, параметры которых превосходят или не хуже параметров лучших образцов.

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

Разработан метод программной конвейеризации на основе пространственного ГСПД, который позволяет составлять эффективные программы обработки потоков данных в многопроцессорных ВС. Также предложен метод отображения пространственного ГСПД в структуру SIMD-процесора.

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

Ключевые слова: граф потоков данных, ПЛИС, VHDL, отображение алгоритма, цифровая обработка сигналов.

Sеrgiyenko А.М. Models, mеthods, and tools for the computer system synthesis intended for data flow computations. Manuscript.

Thesis for a doctoral degree in engineering sciences, speciality: 05.13.05 - Computer systems and components. National Technical University of Ukraine "Kiev Polytechnic Institute", Kiev, 2011.

A set of methods for pipelined computer systems is developed. The methods are based on mapping the spatial synchronous dataflow graph (SDF) into the computer structure, and its schedule. Methods provide minimizing clock period, hardware volume, register number, multiplexor complexity, and energy consumption by the fixed calculation period of L clock cycles. The methods for the pipelined datapath synthesis are developed, which are intended for FPGA, and widely use VHDL as the working language. The methods for mapping Boolean SDF, for buffer synthesis, for hierarchical SDF mapping are proposed as well.

The methods are proven by the design of a set of IP core modules for digital signal processing and linear algebra problem solving, which are configured in FPGA. The module parameters are equal or higher than ones for the best analogous modules. Methods of the software pipelining and SIMD system programming are proposed too.

Keywords: data flow graph, FPGA, VHDL, algorithm mapping, digital signal processing.

Размещено на Allbest.ru