Національна академія наук України

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

ОПАНАСЕНКО Володимир Миколайович

УДК 004.274

АРХІТЕКТУРНО–СТРУКТУРНА ОРГАНІЗАЦІЯ, РОЗРОБКА

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

05.13.05 – елементи та пристрої обчислювальної техніки

та систем керування

Автореферат

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

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

Київ - 2007

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

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

Науковий консультант: доктор технічних наук, професор, академік НАН України

Палагін Олександр Васильович

Інститут кібернетики НАН України, заступник директора

з наукової роботи

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

Баркалов Олександр Олександрович,

Донецький національний технічний університет Міністерства

освіти і науки України, професор кафедри електронних

обчислювальних машин,

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

Вербицький Володимир Григорович,

Інститут мікроприладів НАН України, директор, м. Київ

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

Стасюк Олександр Іонович,

Київський університет економіки і технології транспорту

Міністерства транспорту та зв’язку України, завідувач

кафедри інформаційних систем і технологій на залізничному

транспорті, проректор з наукової роботи

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

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

кафедра спеціалізованих комп’ютерних систем.

Захист відбудеться “21” березня 2007 р. о 14.30 годині на засіданні спеціалізованої вченої ради Д.26.194.03 при Інституті кібернетики імені В.М. Глушкова НАН України

за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися у бібліотеці інституту.

Автореферат розіслано “24” січня 2007 р.

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

спеціалізованої вченої ради Романов В.О.

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

Актуальність теми. Рівень інформаційних технологій, насамперед засобів обчислювальної техніки (ОТ) і систем керування (СК), значною мірою визначає технологічний прогрес багатьох галузей промисловості й народного господарства в цілому. Намітилася тенденція виконання наукових досліджень і практичних розробок в області ОТ і СК на перспективній елементній базі, тобто мікропроцесорах, мікропроцесорних комплектах і системах на чипі у сполученні з програмовними логічними інтегральними схемами (ПЛІС) – Programmable Logic Devices (PLD), які мають задовольнити вимогам широкого кола користувачів і закласти основи розвитку нових ефективних засобів обчислювальної техніки (ЗОТ).

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

Широко відомі роботи із проблем синтезу реконфігуровних пристроїв В.М. Глушкова,

В.І. Варшавського, Є.В. Євреїнова, А.В. Каляєва та ін. Певне місце займають серед них роботи Дж. Єстріна з організації реконфігуровного комп'ютера, представленого двома основними частинами: постійною – комп'ютер з твердою структурою, і змінною – у вигляді набору обчислювальних пристроїв, які можуть за допомогою програми перебудовувати свою структуру, а також роботи О.В. Палагіна з формалізованого проектування процесорів із гнучкою архітектурою. Вони сприяли появі нового напрямку в обчислювальній техніці по проектуванню реконфігуровних пристроїв із віртуальною (програмовною) архітектурою на базі ПЛІС – “Reconfigurable Computing”. Термін “Reconfigurable Computing” у загальному значенні означає двоєдине поняття: як реконфігуровної структури комп'ютера (hardware), так і процесу обробки даних, який виконує комп'ютер. Значний внесок у розвиток даної проблематики внесли також роботи О.О. Баркалова, В.П. Боюна, П.Н. Бібіла, В.Г. Вербицького, В.Ф. Євдокимова, В.І. Жабіна, І.А. Каляєва, М.М. Кузьо, В.В. Соловйова, О.І. Стасюка, В.І. Хаханова, Я.А. Хетагурова та ін.

Засоби ОТ і СК, незалежно від класів проектованих пристроїв, розвиваються за двома взаємозалежними напрямками: підвищення продуктивності й рівня інтелектуальності на базі технології НВІС, що постійно розвивається. Важливим напрямком розвитку інтелектуальних властивостей комп'ютера є інтелектуалізація їхньої внутрішньої архітектури (структури), насамперед застосування “інтелектуальних” методів і засобів аналізу складних інформаційних структур для організації обчислювального процесу, підвищення архітектурної гнучкості (реконфігуровності) комп'ютера. Реконфігуровність структури є природною потребою при створенні складних систем, які повинні мати високу надійність і пристосованість до властивостей розв'язуваних задач. При цьому принцип реконфігуровності структури є визначальним. З його реалізації автоматично випливає, зокрема, можливість паралельного виконання операцій, природно обумовлена самою структурою алгоритму й реалізована за допомогою відповідного настроювання автомата. Розвиток технології “Reconfigurable Computing” дозволяє, крім усього іншого, вирішити задачу уніфікації, стандартизації та програмної сумісності розроблювальних засобів ОТ і СК, підняти рівень внутрішньої мови шляхом програмування структури, що реалізує алгоритми або їхні фрагменти.

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

З появою сучасних кристалів ПЛІС типу FPGA з великою логічною ємністю (понад 10 мільйонів логічних вентилів) стало можливим використовувати отримані результати для побудови реконфігуровних пристроїв і систем високої складності на базі однорідних середовищ із повністю програмовною архітектурою.

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Результати дисертаційної роботи були отримані дисертантом при виконанні ряду проектів у рамках: НДР “Разработать БИС с программируемой структурой” (шифр теми Р.205.03), яка виконувалася за Постановою Президії АН СРСР і розпорядженню Президії АН УРСР № 433 від 30 березня 1989 р. (виконавець); проекти 6.03.01/018–92 “Создание элементной базы молекулярной электроники” (1992 р., відповідальний виконавець), 6.03.01/035–93 “ Разработка научных основ и инструментальных средств проектирования систем с использованием методов самоорганизации” (1993–1995 рр., відповідальний виконавець), 6.03.01/015–92 “Развитие и адаптация методов физического моделирования и логического синтеза устройств информатики на базе ПЛИС (Неймановские, матричные, нейронные и другие структуры)” (1995 р., відповідальний виконавець) згідно з Державною науково-технічною програмою 6.03.01 “Високопродуктивні професійні ЕОМ і проблемно-орієнтовані комплекси широкого призначення”; НДР “Разработать нейроподобную адаптивную логическую сеть на ПЛИС”, номер держреєстрації 0194U000364 (1993–1995 рр., відповідальний виконавець); НДР “Дослідження та розробка методів конфігурування адаптивних структур”, номер держреєстрації 0197U002350 (1996–1997 рр., відповідальний виконавець); НДР “Теоретичні основи розвитку архітектури ЕОМ нових поколінь”, номер держреєстрації 0197U01594 (1997–2000 рр., відповідальний виконавець); НДР “Дослідження та розробка принципів побудови реконфігуровних процесорів на базі ПЛІС”, номер держреєстрації 0100U003047 (2000–2002 рр., відповідальний виконавець); НДР “Розробка комп'ютерної системи з віртуальною архітектурою на базі програмованих логічних інтегральних схем (ПЛІС)”, номер держреєстрації 0103U008790 (г/д ДП/371–2003 з Міністерством освіти і науки, 2003–2005 рр., відповідальний виконавець); НДР „Розробити концепцію побудови віртуальних систем широкого призначення із застосуванням реконфігуровних процесорів”, номер держреєстрації 0103U003264 (2003–2005 рр., відповідальний виконавець); НДР „Теоретичні аспекти розвитку високопродуктивних ЕОМ з високим рівнем машинного інтелекту”, номер держреєстрації 0101U000077 (2001–2005 рр., відповідальний виконавець); НДР „Розробка теоретичних та технологічних засад знання орієнтованих комп'ютерних систем для широкого призначення”, номер держреєстрації 0102U003207 (2002–2006 рр., відповідальний виконавець).

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

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

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

розробити теоретичні основи побудови реконфігуровних цифрових структур на основі однорідного середовища, включаючи систему формалізованих методик й алгоритмів синтезу параметричних модулів і закінчених функціональних пристроїв;–

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

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

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

розробити принципи побудови реконфігуровного процесора (РПр), що реалізує конвеєрний, паралельний та змішаний принципи обробки даних;–

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

Об'єкт дослідження – технологія “Reconfigurable Computing” для створення реконфігуровних пристроїв і систем на основі однорідного середовища.

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

Методи дослідження. Виконані дослідження використовують результати, отримані у прикладній теорії автоматів стосовно структурного синтезу й логічного проектування цифрових пристроїв. Зокрема, використані і розвинуті: теорія “Reconfigurable computing”, логіко-інформаційний метод (ЛІМ) для синтезу комп'ютерів із гнучкою (програмовною) архітектурою, теорія і методологія застосування однорідних середовищ та нейронних мереж. У процесі структурної організації нейроподібних мереж Хемінга і пристроїв, що класифікуються, знайшли застосування методи теорії розпізнавання образів. У проведених дослідженнях широко використано апарат теорії множин, матриць, графів, булевої алгебри й комбінаторики.

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

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

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

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

Запропоновано ряд структур АЛМ у вигляді "трикутної", "трапецеїдальної" і “прямокутної” матриць для широкого класу задач. Процес настроювання матриць зводиться до визначення типів логічних функцій елементарних компонентів та структури зв'язку із заданої множини, яка є обмеженою. Запропоновані структури розрізняються потужністю реалізованих булевих функцій та апаратними витратами, для кожної з них визначені аналітичним шляхом асимптотичні оцінки складності (залежно від розрядності вхідних двійкових векторів) і потужність вихідної множини двійкових векторів.

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

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

Для підвищення ефективності виявлення, локалізації й виправлення помилок у цифрових кодах запропоновано використовувати розроблені алгоритми синтезу перетворювача циклічного коду Хемінга, структура зв'язків між рівнями якого, залежно від розрядності вхідних двійкових векторів, визначається аналітично, а структура зв'язків у межах одного рівня є незмінною, що відкриває нові перспективи для розробки відмовостійких засобів ОТ і СК. Запропонований підхід дозволяє за рахунок змінної (визначена аналітично) структури зв'язків кожного рівня реалізувати таку процедуру для –розрядних кодів на () рівнях (порівняно з () рівнями за постійної структури зв'язків).*

Створені методи й засоби проектування дозволили розробити нові алгоритми і проблемно-орієнтовану відкриту бібліотеку функціональних пристроїв. Зокрема, це структури пристроїв: визначення медіани з потактною конвеєрною обробкою вхідних даних; сортування даних, підвищення швидкодії якого досягається виключенням непродуктивних звертань до пам'яті; суматори Хемінга (для довільної розрядності); граничні пристрої (для довільної розрядності вхідних даних і значення порога); множення матриць; множення із плаваючою точкою (згідно зі стандартом IEEE–754) та ін.

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

Запропоновані в дисертаційній роботі основи теорії універсальних засобів обробки інформації АЛМ, принципів побудови реконфігуровних цифрових структур на основі однорідного середовища, системи формалізованих методик та алгоритмів синтезу параметричних блоків з урахуванням особливостей їхньої конструктивно-технологічної бази використано при розробці цілого комплексу пристроїв на базі ПЛІС: функціональні блоки типу "трикутна матриця", “трапецеїдальна матриця” і лінійно-блокові структури, орієнтовані на типові задачі та алгоритми їхньої структурної адаптації – визначення відстані по Хемінгу, пристрої реалізації граничних функцій (граничний елемент або компаратор), сортування даних, медіанних фільтрів, пристроїв множення матриць, арифметичних пристроїв із плаваючою точкою (згідно зі стандартом IEEE–754), реконфігуровний процесор з конвеєрною обробкою даних та ін.

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

Особистий внесок здобувача. Усі вищеперелічені наукові результати дисертаційної роботи автор отримав самостійно. У співавторстві опубліковано роботи [1–8, 10–23, 25, 27, 29–48], у яких дисертантові належать постановки задач й основні теоретичні результати (методи і підходи для вирішення поставлених задач). Зокрема, в [1] – формалізований підхід до архітектурно–структурної організації, розробці та створенню реконфігуровних пристроїв на базі ПЛІС; у [2–7, 12, 15, 18–21] – структурна організація функціональних реконфігуровних блоків, які описуються адаптивними логічними мережами типу “трикутна матриця”, “трапецеїдальна матриця” й “прямокутна матриця”, параметричні алгоритми синтезу цифрових структур з адаптацією на клас задач: граничний пристрій, суматор Хемінга, перетворювач циклічного коду Хемінга та ін.; у [16, 30, 31] – аналіз стану й тенденцій розвитку сучасних, реконфігуровних цифрових пристроїв, особливостей їхньої архітектури та структури, а також визначення основних понять, пов'язаних з математичною моделлю однорідного обробного поля; у [8, 10, 11, 13, 14, 17, 44–48] – методологія проектування, моделювання й верифікації реконфігуровних пристроїв, в [22, 23, 25, 27, 29, 32, 33, 37–39, 41–43] – математичні моделі й структурна організація мереж Хемінга з максимальною і граничною мірою близькості, розпізнавального пристрою, медіанних фільтрів, пристроїв сортування, перемножування матриць, алгоритми синтезу параметричних модулів; у [34–36, 40] – принципи побудови й алгоритми функціонування реконфігуровного процесора, пристроїв сортування та визначення медіани.

Апробація результатів дисертації. Основні результати дисертаційної роботи апробовано на 3-й Міжнародній конференції “Application of Computer Systems” (Szczecin, Poland, 1996), Українських конференціях з автоматичного керування “Автоматика-95, 96” (Львів-1995; Севастополь-1996), Міжнародних конференціях з управління “Автоматика – 2000, 2001, 2002, 2003, 2004, 2005” (Львів-2000; Одеса-2001; Донецьк-2002; Севастополь-2003; Київ-2004, Харків-2005), Міжнародних конференціях “Информационные технологии в управлении энергетическими системами” (Київ-2005), “Моделирование и компьютерная графика” (Донецьк-2005), “Моделирование-2006” (Київ-2006), 7-й Міжнародній науково-практичній конференції “Современные информационные и электронные технологии” (Одеса-2006), а також неодноразово обговорювалися на наукових семінарах наукової ради з проблеми “Кібернетика” НАН України.

Публікації. За темою дисертаційної роботи опубліковано 48 наукових праць, у тому числі 1 монографія, 16 статей у провідних вітчизняних та закордонних наукових журналах, 16 – у наукових збірниках, 3 патенти України на винаходи, 12 – у працях і тезах конференцій.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, п'яти розділів, висновків, переліку використаних джерел і додатків. Перші чотири розділи присвячено розгляду змістовної сутності побудови РП в цілому і його складових компонентів, п'ятий розділ демонструє застосування окремих положень методології до задач проектування. Роботу викладено на 423 сторінках, із них основний текст – 281 сторінка, рисунки – 120, таблиці – 45. Список використаних джерел – 20 сторінок, що містить 225 найменувань.

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

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

Перший розділ присвячений дослідженню загальних принципів побудови і проектуванню реконфігуровних структур на базі ПЛІС. Розглянуто літературу з архітектурно-структурної організації реконфігуровних пристроїв ОТ і СК. Відображено архітектурні особливості структурної організації реконфігуровних пристроїв, вимоги застосувань і технологічні основи проектування реконфігуровних пристроїв на основі ПЛІС. Розглянуто типові реконфігуровні пристрої й галузі їх застосування. Аналізуються відомі шляхи підвищення продуктивності засобів ОТ – конвеєризація й паралелізм. Наведено класифікацію конвеєрів за функціональними можливостями і фактичному застосуванні. У випадку частих змін виконуваних функцій, аж до нової функції при кожному новому виконанні, має місце конвеєр з динамічною конфігурацією. Даний клас засобів розглянутий стосовно реалізації в технології “Reconfigurable computing”. У таких пристроях логічна структура може динамічно змінюватися, залежно від специфіки розв'язуваної задачі, шляхом передачі спеціальної інформації про кожну поточну конфігурацію. Застосовуючи технологію реконфігурування, простим перепрограмуванням структури РП вдається настроювати його на ефективну реалізацію заданого алгоритму, зберігаючи структурну універсальність пристрою.

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

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

Структура реконфігуровної системи складається з двох частин: постійної (або “фіксованої”) частини (Host-комп'ютера) і змінної частини – РП, які можна поєднувати в різні конфігурації. Архітектура реконфігуровних систем залежить від потужностей множин алгоритмів (), виконуваних на обладнанні, і (), виконуваних на обладнанні. Співвідношення цих величин визначає запропоновану класифікацію реконфігуровних обчислювальних систем: а) обчислювальні системи, орієнтовані на Host-комп'ютер, у якому зосереджені основні обчислювальні потужності, а реконфігуровний комп'ютер забезпечує підвищення продуктивності тільки для вузького класу задач (); б) обчислювальні системи, орієнтовані на РП, у яких Host–комп'ютер використовується, в основному, для виконання допоміжних функцій (сервіс, введення–виведення), а всі алгоритми виконуються переважно в РП, який може мати власне поле зовнішніх пристроїв (через плати розширення) або загальне поле зовнішніх пристроїв з Host-комп'ютером, до яких РП має безпосередній доступ (); в) реконфігуровні обчислювальні системи, у яких Host-комп'ютер і РП мають приблизно однакову складність, при цьому РП орієнтовано на рішення трудомістких задач, а Host-комп'ютер забезпечує потужну підтримку в частині трансляції, введення–виведення, сервісу та ін. (); г) РП є автономним пристроєм у випадку, а Host-комп'ютер відсутній.

Виконаний аналіз показує, що РП на сьогодні ефективно застосовуються в наступних областях: реконфігуровні високопродуктивні багатопроцесорні обчислювальні системи (з можливістю реконфігурування по телеметричних каналах зв'язку, наприклад у радіоастрономії); проектування, моделювання й верифікація перспективних цифрових пристроїв; заміна логічних мікросхем в існуючих апаратних рішеннях – один корпус ПЛІС заміняє до кілька сотень корпусів мікросхем МІС і СІС; спеціалізовані автономні вмонтовані пристрої; кодування–декодування інформації (криптографія); цифрова обробка сигналів (ШПФ, ДПФ, КІХ, обробка радіотелескопічних сигналів, когнітивні радіосистеми, обробка зображень); робототехніка й нейронні мережі; бортові (авіаційна, космічна й морська техніка) і вилучені на велику відстань (газові й нафтові вишки) обчислювальні системи; комунікаційні засоби (інтерфейси, порти, канали); контролери для керування складними об'єктами (АЕС, ТЕЦ, ГЕС та ін.); онтолого–керовані інформаційні системи та ін.

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

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

(1)

Для формалізованого представлення моделі реконфігуровних пристроїв виконано модифікацію методу ЛІМ, що ілюструється наступною схемою:

(2)

Відповідно до (1), у даному випадку – множина апаратних реалізацій операторів го рівня. Причому, при синтезі оптимальної структури пристрою деякі рівні можуть бути виключені. У схемі (2) для класичних архітектур використовуються наступні рівні програмування: – фізичний або “нульовий”; – мікропрограмний; – програмний; – алгоритмічний. Програмування на “нульовому” рівні визначає фізичну структуру пристрою, що в остаточному підсумку реалізує заданий алгоритм функціонування, тобто виконує програмування структури пристрою. На відміну від схеми (1), запропонована модифікація (2) реалізує не мікропрограмну, а апаратну реалізацію алгоритмів на вентильному рівні.

Враховуючи вищевикладене, реконфігуровний обчислювальний пристрій (ОП) являє собою автомат, що виконує програмування структури для реалізації множини алгоритмів рівня потужністю на фізичному “нульовому” рівні пристрою:

Запропоновано коефіцієнт реконфігуровності (програмовності, гнучкості) пристрою , що визначає відношення числа алгоритмів, доступних для реалізації на фізичному рівні, до числа всіх можливих вхідних алгоритмів:

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

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

Запропоновано модель проектованої обчислювальної системи, що представлена четвіркою:

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

Запропоновано синтез структурної реалізації послідовності алгоритмів, коли метод / задача представляється послідовністю алгоритмів ():

У реконфігуровних ОП споконвічно задана базова (нульова) архітектура, реалізована на ПЛІС у вигляді функціонального обробного поля фіксованої розмірності, контролера шини Host-комп'ютера, поля пам'яті, а також добре структурованої бібліотеки файлів конфігурацій (БФК) структурних реалізацій методів (алгоритмів), що здійснюють відображення алгоритму в структурну реалізацію (). Кожен алгоритм має відображення в структурну реалізацію (), що являє собою файл конфігурації для кристала ПЛІС. У загальному випадку є кілька варіантів реалізації алгоритму (наприклад, послідовний, послідовнопаралельний та паралельний):

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

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

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

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

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

РИС. 1. Блок-схема алгоритму проектування РП

Розроблено алгоритм проектування структурних реалізацій РП, які представляють собою базову плату (для співпроцесорів, що підключаються до стандартної шини Host-комп'ютера) або несучу плату (для автономних пристроїв) з набором плат і модулів розширення, або ж кристал ПЛІС для реалізації SoC (System–on–Chip). Алгоритм являє собою послідовність етапів (рис. 1): аналіз проблемної області > постановка задачі > вибір підходящого алгоритму (у випадку відсутності файлу конфігурації для реалізації відповідного алгоритму виконується його синтез з наступним записом у БФК) із БФК > відображення на рівні загальної архітектури (функціональна схема) > підготовка формалізованого технічного завдання > програмування структури на основі файлу конфігурації > програмування алгоритму > вирішення задачі > оцінка характеристик параметрів (структури, процесу рішення) > перевірка параметрів на відповідність установленим критеріям (за необхідності – наступна ітерація) > введення в експлуатацію.

Блок–схема алгоритму (див. рис. 1) передбачає також корекцію критеріїв. Виконано аналіз особливостей проектування цифрових пристроїв на базі ПЛІС із використанням HDL-технології та САПР ПЛІС. Розроблена методика проектування, опираючись на дану систему алгоритмів і логіко-інформаційну модель РП, що покладена в її основу, дозволяє вирішити головну задачу проектування – формалізувати процес пошуку оптимальної пари “алгоритм – структурна реалізація”. Методика призначається для проектування: проблемно-орієнтованих співпроцесорів і автономних пристроїв, що працюють із заданим набором алгоритмів; реконфігуровних процесорів з конвеєрною обробкою даних; параметричних IP-Core для реалізації заданих алгоритмів, які представляються елементами бібліотеки файлів конфігурації; SoC. Вона може модифікуватися залежно від вихідного завдання, класу задач, елементно-технологічної бази та ін.

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

З погляду топології системи (рис. 2) АЛМ являє собою матрицю універсальних логічних елементів (ЛЕ), які групуються у функціональні вузли і блоки (ФБ), місце розташування яких закріплено. При цьому зміна їхнього функціонування відбувається залежно від класу задач і їхнього призначення.

РИС. 2. Топологія адаптивної логічної мережі

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

Структура АЛМ може бути описана такою системою:

де – розрядність вхідних двійкових векторів (розмірність АЛМ по входу); – вихідна розрядність (), розмірність АЛМ по виходу; – множина логічних функцій системи; – структура зв'язків між ЛЕ; – множина ЛЕ ( – порядковий номер елемента ЛЕ; – номер рівня обробки); – кількість рівнів обробки; – множина –мірних двійкових векторів (навчальна вибірка); – повна множина вхідних двійкових векторів; – узагальнена функція системи, – значення функції, яку реалізовано елементом, (рис. 3):, – значення індексу для входів ЛЕ.

РИС. 3. Структура ЛЕ

Будь-який рівень АЛМ представляє лінійку -входових ЛЕ, кожен з яких може бути настроєний на виконання довільної з повного набору () булевих функцій його вхідних змінних і реалізує відображення -мірних двійкових векторів в -мірні двійкові вектори. Матриця ЛЕ або ФВ являє собою комбінаційний автомат без пам'яті, що має -розрядний вхід, -розрядний вихід та – кількість рядків матриці. У рамках одного рівня тип функції може задаватися для кожного ЛЕ окремо (поелементне настроювання) або для всіх ЛЕ (порівневе настроювання).

Функціональним блоком є мережа послідовно включених автоматів (ієрархічна збірка () функціональних вузлів). Надалі обмежимося розглядом трьох типів ФБ, що розрізняють за топологічною ознакою: “прямокутна матриця” (ПМ) – (); “трикутна матриця” (ТМ) – (); “трапецеїдальна матриця” (ТпМ) – (). В залежності від структури зв'язків запропоновано наступні типи ТМ: з логарифмічною структурою зв'язків (ЛСЗ); зі стільниковою структурою зв'язків (ССЗ); з асиметричною структурою зв'язків (АСЗ). Запропоновані структури зв'язку розрізняються за потужністю реалізованих булевих функцій і апаратних витрат. Характеристики зазначених типів структур наведено в табл. 1.

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

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

Структурна складність запропонованих ТМ (табл. 1) із логарифмічною, стільниковою та асиметричною структурами зв'язку представляється відповідно

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

Таблиця 1. Параметри ТМ

Таблиця 2. Параметри ТпМ

Структурна складність запропонованих ТпМ (див. табл. 2) з логарифмічною і стільниковою структурами зв'язку, що реалізують системи булевих функцій змінних, визначається відповідно.

Для ФБ із лінійно-блоковою організацією структури (ЛБС) запропоновано алгоритм адаптації для виділення підмножини, заданого навчальною вибіркою з повної множини, який реалізує відображення, , причому, , де. На основі структур типу ЛБС реалізовуються лінійки Хемінга (циклічні структури) для виділення підмножини векторів, яка є циклічним кодом.

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

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

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

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