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

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

Національний університет “Львівська політехніка”

05.13.05 - Комп'ютерні системи та компоненти

УДК 004.272:004.31

Автореферат

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

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

Яковлєва Інна

Дмитрівна

Львів - 2010

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

Роботу виконано у Національному університеті “Львівська політехніка” Міністерства освіти і науки України

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

Мельник Анатолій Олексійович, завідувач кафедри “Електронні обчислювальні машини” Національного університету “Львівська політехніка”

Офіційні опоненти - доктор технічних наук, доцент Максимович Володимир Миколайович,

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

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

Кулик Анатолій Ярославович,

професор кафедри “Автоматика та інформаційно- вимірювальна техніка” Вінницького національного технічного університету

Захист відбудеться 25 червня 2010 р. о 1630 годині на засіданні спеціалізованої вченої ради Д 35.052.08 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул. С. Бандери,12, ауд. 226 головного корпусу).

Із дисертацією можна ознайомитися в бібліотеці Національного університету “Львівська політехніка” (79013, Львів, вул. Професорська,1)

Автореферат розіслано 21 травня 2010 р.

Вчений секретар спеціалізованої вченої ради, д.т.н., проф. Я.Т. Луцик

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

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

Висока швидкодія забезпечується використанням алгоритмічних операційних пристроїв (АОП), в яких алгоритм виконання операції реалізовується апаратно.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася відповідно до напрямку наукової діяльності кафедри електронних обчислювальних машин Національного університету “Львівська політехніка”: “Питання теорії, проектування та реалізації комп'ютерних систем та мереж, а також математичних засобів, вузлів, приладів і пристроїв вимірювальних, інформаційних і керуючих систем” і кафедри комп'ютерних систем та мереж Чернівецького національного університету імені Юрія Федьковича за темою Міністерства освіти і науки України протягом 2005-2009 років: “Наукові основи створення, діагностики та підвищення надійності первинних перетворювачів сигналів автоматизованих систем керування, елементів і пристроїв обчислювальної техніки та захисту інформації в комп'ютерних засобах”.

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

Відповідно до поставленої мети в рамках дисертаційної роботи розв'язано такі задачі:

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

- розроблено новий метод запису алгоритму на рівні зв'язків між окремими операціями або блоками операцій, який зберігає паралельну структуру алгоритму;

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

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

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

Об'єкт дослідження - процес проектування алгоритмічних операційних пристроїв.

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

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

Наукова новизна роботи.

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

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

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

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

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

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

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

1. Розроблений метод запису ПГА у формі СМ, що може бути використано для збереження в комп'ютері структури алгоритму.

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

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

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

Впровадження результатів роботи. Теоретичні та практичні результати роботи впроваджено при виконанні науково-дослідних робіт з теми “Наукові основи створення, діагностики та підвищення надійності первинних перетворювачів сигналів автоматизованих систем керування, елементів і пристроїв обчислювальної техніки та захисту інформації в комп'ютерних засобах” (№ державної реєстрації 0105U007365) в Чернівецькому національному університеті імені Юрія Федьковича; на науково-виробничому підприємстві “Інтрон” при реалізації програмного комплексу “ОСКАР” для оперативного синтезу комп'ютерних пристроїв з алгоритмічного рівня та графічної системи “ОСА”, а також у навчальному процесі кафедри КСМ Чернівецького національного університету імені Юрія Федьковича в рамках дисциплін: “Технологія проектування VHDL і Protel”, “Автоматизоване проектування комп'ютерних систем”. Дані про впровадження підтверджено відповідними актами.

Особистий внесок здобувача. Основний зміст роботи, всі теоретичні та практичні розробки, висновки та рекомендації, виконані автором особисто. У друкованих працях, опублікованих у співавторстві, здобувачу належать: підхід до побудови вектора готовності даних [1, 12, 13]; метод запису потокового графа алгоритму у формі СМ [3]; метод побудови СМ потокових графів інваріантних до зсуву алгоритмів, які використовують множинні операції [4]; удосконалено метод проектування АОП, який передбачає апаратне відображення ПГА шляхом введення процедури їх схемотехнічного опису з СМ [5]; метод перетворення графічного подання алгоритму в ПГА, відображення ПГА в СМ, а також здійснення оберненої процедури відображення потокового графа із СМ [8, 15]; метод автоматичної модифікації поведінкового опису АОП ділення, описаного мовою VHDL, залежно від розрядності дільників [9, 18]; аналіз застосування принципів теорії потоків даних до побудови ПГА [10]; аналіз методів побудови й подання ПГА для проектування АОП [11]; використання ПГА, що зберігається в СМ, для керування розпаралелюванням алгоритмів у багатопроцесорних системах [16]; реалізація графічної системи для дослідження й опрацювання алгоритмів, методи відображення, модифікації й аналізу ГА [19].

Апробація результатів дисертації. Основні положення та результати дисертаційної роботи доповідались і обговорювались на VIII International Conference “The Experience of Designing and Application of CAD Systems in Microelectronics” (Lviv _ Polyana, 2005); V International Scientific Conference for Students and Young Scientists „Telecommunication in XXI Century” (Poland, Kielce -Wulka Milanowska, 2005); 3 International Conference “Advanced Computer Systems and Networks: Design and Application” (Lviv, 2007); V міжнародній науково-практичній конференції „Комп'ютерні системи в автоматизації виробничих процесів” (Хмельницький, 2007); IX мiжнародній конференцiї "Контроль i управлiння в складних системах " (Вінниця, 2008); X International Conference “The Experience of Designing and Application of CAD Systems in Microelectronics” (Lviv _ Polyana, 2009); 16-й міжнародній конференції з автоматичного управління “Автоматика _ 2009” (Чернівці, 2009); 4-й міжнародній конференції “Сучасні комп'ютерні системи та мережі: Розробка та використання” (Львів, 2009).

Публікації. За результатами виконаних досліджень опубліковано 19 праць загальним обсягом 78 сторінок, з них 9 статей у фахових виданнях за переліком ВАК (3 одноособові), 10 матеріалів доповідей у збірниках міжнародних науково-технічних конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел (126 позицій), 7 додатків на 59 сторінках. У роботі подано 53 рисунки, 23 таблиці. Повний обсяг роботи _ 214 сторінок, з них 142 _ основного тексту.

2. ОСНОВНИЙ ЗМІСТ

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

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

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

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

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

Поставлена задача розв'язана на основі збереження в пам'яті комп'ютера інформації про ПГА, а саме: розподіл його вершин за ярусами структурною матрицею.

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

Даний метод запису ПГА у формі СМ передбачає виконання: етапу маркування ПГА та етапу запису інформації.

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

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

Дана СМ має такий вигляд:

де N (всі елементи СМ належать множині натуральних чисел), , , l - кількість ярусів, n - кількість вхідних дуг ГА.

СМ зберігає множину параметрів, де

- - множина вхідних дуг ПГА (, а M - множина всіх дуг, яка відображає організацію з'єднань між операціями), - номер вхідної дуги ПГА, по якій надходять дані, n - кількість вхідних дуг ПГА і дорівнює кількості вхідних даних;

- - множина ярусів , - номер ярусу ПГА, l - загальна кількість ярусів ПГА;

- - множина ФО ПГА, N (N - множина натуральних чисел), - номер ФО ПГА, , , - загальна кількість ФО ПГА;

- - множина, яка визначає кількість ФО на кожному і-му ярусі і ширину ПГА - w.

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

На рис. 1 показано ГА (рис. 1, а) обчислення виразу, його ПГА (рис. 1, б), процес нумерації вершин та дуг (рис. 1, в), а також СМ (рис. 1, г) та таблиця операцій (рис. 1, д) .

б - ПГА; в - нумерація дуг ПГА; г - СМ; д - таблиця операцій;

ФО - функціональний оператор

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

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

- множина вершин ГА,

Р - множина портів, М - множина дуг ГА

За цим методом граф алгоритму описується трійкою (рис. 2), де - множина вершин ГА, Р - множина портів, М - множина дуг ГА. Для зображення ГА передбачено відображення трьох типів вершин: вхідні вершини - з яких надходять вхідні дані на ФО, вершини-ФО, які виконують операцію або блок операцій алгоритму та вихідні вершини, на які надходить результат виконання всіх операцій. Усі вершини отримують ідентифікатори (порядкові номери) в процесі створення. Порти вершини (порт - це точка входу операнда

у вершину ГА або з неї):характеризуються 1) ідентифікатором порту I1, який отримується конкатенацією двох складових - ідентифікатора вершини Ik, якій належить даний порт, та порядкового номеру порту Ip всередині вершини; 2) ідентифікатором порту I2 - іншої вершини, з якою з'єднаний даний порт дугою та 3) номером дуги j, яка зв'язує порти I1 та I2 даної вершин. Такий підхід дозволяє зберегти порядок надходження даних у вершину, виконувати збереження ГА у XML-документі та здійснювати його об'єктне подання.

Для переходу від об'єктного подання ГА до СМ розроблено метод переходу від графічного подання алгоритму в комп'ютері до структурної матриці, який полягає у виявленні вершин-ФО ГА, що можуть виконуватися паралельно, та збереженні за допомогою СМ розподілу даних вершин за ярусами ПГА. Для побудови ярусу ПГА використовують процедуру визначення готовності даних для поточної вершини, в результаті чого вершина отримує властивість „готова”. Вершина „готова” у двох випадках, якщо: 1) вершина k вже має властивість „готова”; 2) якщо на всі порти вершини-ФО k надходять дуги від вхідної вершини та/або від вершини, що має властивість „готова”. Значення ідентифікатора вершини k, що має властивість „готова”, записують в елементі, де і - номер кроку, на якому визначена готовність, j - номер дуги для даного порту вершини. Даний метод дозволяє одразу переходити від ГА до СМ без відображення ПГА або паралельно із ним.

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

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

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

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

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

За методами побудови СМ алгоритму з його опису на рівні тріад і побудови СМ алгоритмів з множинними операціями отримані СМ для схеми Горнера, сортування та ШПФ для діапазону від 8 до 65536 точок відліку. Використовуючи метод графічного подання потокового графа алгоритму з СМ, виконано відображення отриманих СМ та порівняно з еталонними. Результати експерименту показали коректність розроблених алгоритмів.

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

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

Декларація сигналів з'єднання КС АОП, яка виконується за синтаксисом signal <ідентифікатор>: <тип>;,

за СМ формується шляхом конкатенації ідентифікатору сигналу t та індексів i та j для всіх елементів СМ F:

SIGNAL ti_j:std_logic_vector(width downto 0);.

Для опису сигналів, який виконується за синтаксисом

<мітка>: <ім'я_компонента> [<дійсний_port_map>];,

за СМ для елементів СМ F, які задовольняють умові формується:

- <мітка> аналогічно до <ідентифікатор> в (1);

- <ім'я_компонента> шляхом вибору k-того ФО з ТО та зіставленні його з КС із VHDL-бібліотеки;

- [<дійсний_port_map>] за правилом нумерації дуг СМ:

port map (ti_j, ti_z, ti+1_j, ti+1_z);.

Перепризначення сигналу з одного ярусу АОП на інший за СМ виконується для елементів СМ F, які задовольняють умові :

U_i+1_j <= U_i_j.

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

signal ri_j_nxt: STD_LOGIC_vector (width downto 0);,

а запис проміжних даних в регістри виконується за правилом

U_REG_i_j: reg port map (clk, rst, ti_j, ri_j_nxt);.

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

Програмний засіб дослідження, опрацювання структури алгоритмів і проектування АОП з їх графічного подання складається з двох віконних редакторів. Перший - це графічна система для дослідження й опрацювання структури алгоритмів, другий - засіб синтезу АОП на основі СМ і ТО. Крім VHDL синтезу однотактового та/або конвеєрного АОП, відповідно до модифікованого алгоритму, виконується синтез test-bench для верифікації роботи АОП.

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

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

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

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

Автоматично синтезовані АОП показують кращі характеристики за тактовою частотою й апаратними затратами, ніж аналогічні зразки інших фірм.

Якщо V - це обсяг пам'яті, необхідний для збереження ПГА матрицею інциденцій або матрицею суміжності і дорівнює 100%, а Vстр - це обсяг пам'яті, необхідний для збереження ПГА структурною матрицею, то ефективність е використання пам'яті, яка показує наскільки менше пам'яті займає СМ по відношенню до матриць інциденцій та суміжності, розраховується за формулою

Результат синтезу алгоритмічних операційних пристроїв RGB2YUV

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

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

в - ПГА сортування за методом парно-непарної перестановки; г - ПГА сортування за методом Бетчера; д - ПГА двійкового множення з горизонтальним розповсюдженням переносу; е - двійкового множення з діагональним розповсюдженням переносу та за алгоритмом Дадда;

квадратиком -?- позначена ефективність використання СМ п відношенню до матриці інциденцій; кружечком -_- позначена ефективність використання СМ по відношенню до матриці суміжності

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

У дисертаційній роботі поставлено і розв'язано актуальну наукову задачу вдосконалення процесу проектування АОП на основі розробки та практичного використання методів і засобів проектування АОП з графічного подання виконуваних алгоритмів.

Основні наукові та практичні результати полягають у тому, що:

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

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

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

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

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

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

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Яковлєва І. Д. Підхід до побудови потокового графа алгоритму / І. Д. Яковлєва, І. Д. Лісовенко // Вісник “Комп'ютерні системи та мережі”. - Львів: Національний університет “Львівська політехніка”, 2005. - № 546. - С. 162-165.

2. Яковлєва І. Д. Модифікація потокових графів алгоритмів на засадах готовності даних / І. Д. Яковлєва // Науковий журнал “Технічні науки” - Хмельницький: Хмельницький національний університет, 2007. - Т.2, №2 - С. 39-43.

3. Мельник А. О. Подання потокового графа алгоритму структурною матрицею / А. О. Мельник, І. Д. Яковлєва // Науковий журнал “Технічні науки” - Хмельницький: Хмельницький національний університет, 2008. - №4 - С. 124-129.

4. Мельник А. О. Особливості побудови структурної матриці потокових графів алгоритмів з множинними операціями / А. О. Мельник, І. Д. Яковлєва // Науковий журнал “Технічні науки” - Хмельницький: Хмельницький національний університет, 2008. - №5 - С. 117-120.

5. Мельник А. О. Метод перетворення графічного подання алгоритму в його апаратну модель / А. О. Мельник, І. Д. Яковлєва // Науковий вісник Чернівецькеого ун-ту. Фізика. Електроніка. Вип. 423. - Чернівці: Чернівецький національний університет імені Юрія Федьковича, 2008. - С. 19_23. - (Тематичний випуск: Комп'ютерні системи та компоненти).

6. Яковлєва І. Д. Оцінка варіантів синтезу паралельних обчислювальних пристроїв сортування / І. Д. Яковлєва // Вісник “Комп'ютерні системи та мережі”. - Львів: Національний університет “Львівська політехніка”, 2008. _ №630. - С. 124_130.

7. Яковлєва І. Д Синтез та оцінка різних варіантів паралельних перемножувачів двійкових чисел / І. Д. Яковлєва // Науковий вісник Чернівецького ун-ту. Фізика. Електроніка. Вип. 426. - Чернівці: Чернівецький національний університет імені Юрія Федьковича, 2008. - С. 33 _ 38. - (Тематичний випуск: Комп'ютерні системи та компоненти).

8. Мельник А. О. Побудова та матричне подання потокового графа алгоритму / А. О. Мельник, І. Д. Яковлєва, В. Ю. Ющенко // Вісник Вінницького політехнічного інституту - Вінниця: Вінницький національний технічний університет, 2009. - №3. - С. 93_99.

9. Мельник А. О. Синтез алгоритмічного операційного пристрою ділення двійкових чисел довільної розрядності в форматі з фіксованою комою / А. О Мельник. І. Д. Яковлєва, З. Р. Кудринський // Науковий вісник Чернівецького ун-ту. Комп'ютерні системи та компоненти. Вип.464. - Чернівці: Чернівецький національний університет імені Юрія Федьковича, 2009. _ №464. - С. 29_34.

10. Melnyk А. Approaches to dataflow machine construction / Anatoliy Melnyk, Iryna Lisovenko, Inna Yakovleva // Proceedings of VIIIth International Conference “The Experience of Designing and Application of CAD Systems in Microelectronics”. - Lviv-Polyana, Lviv Polytechnic National University, 2005. - P. 205.

11. Melnyk А. Graph methods of parallel processes description / Anatoliy Melnyk, Iryna Lisovenko, Inna Yakovleva // Proceedings of VIIIth International Conference “The Experience of Designing and Application of CAD Systems in Microelectronics”. - Lviv-Polyana, Lviv Polytechnic National University, 2005. - P. 206.

12. Yakovleva І. Construction algorithm of ready-to-run operands matrix in the dataflow machine / I. Yakovleva, I. Lisovenko // Proceedings of the Vth International Scientific Conference for Students and Young Scientists „Telecommunication in XXI Century”. - Kielce-Wulka Milanowska: IT press, 2005, _ P. 73_77.

13. Lisovenko І., Method of dataflow graph building”/ I. Lisovenko, I. Yakovleva // Proceedings of the Vth International Scientific Conference for Students and Young Scientists „Telecommunication in XXI Century”. - Kielce-Wulka Milanowska: IT press, 2005, _ P.69_72.

14. Iakovlieva І. Space-Time Algorithm Transformations / І. Iakovlieva // Proceedings of 3rd International Conference “Advanced Computer Systems and Networks: Design and Application”. - Lviv: Lviv Polytechnic National University, 2007. - P. 70_72.

15. Мельник А. О. Побудова потокового графа алгоритму та його матричне подання. [Електронний ресурс] / А. О. Мельник, І. Д. Яковлєва, В. Ю. Ющенко. // Матеріали 9-ї міжнародної конференції “Контроль i управлiння в складних системах” - Вінниця, Вiнницький нацiональний технiчний унiверситет, 2008.

16. Мельник А. О. Розпаралелювання виконання алгоритмів в багатопроцесорній системі [Електронний ресурс] / А.О. Мельник, І. Д. Яковлєва, Є. В. Грушка, О.В. Денисюк // Матеріали 9-ї міжнародної конференції “Контроль i управлiння в складних системах” - Вінниця, Вiнницький нацiональний технiчний унiверситет, 2008.

17. Iakovlieva I. Design and estimation of parallel multiplier versions / I. Iakovlieva // Proceedings of Xth International Conference “The Experience of Designing and Application of CAD Systems in Microelectronics”. - Lviv - Polyana, Lviv Polytechnic National University, 2009. - P. 420-423.

18. Яковлєва І. Д., Кудринський З. Р Покращена реалізація модуля ділення 64-розрядних чисел з плаваючою крапкою за SRT алгоритмом / 16 Міжнародна конференція з автоматичного управління “Автоматика-2009”, Чернівці, 22-25 вересня, 2009. - С. 408-410.

19. Мельник А. Графічна система для дослідження та опрацювання структури алгоритмів / А. Мельник, І. Яковлєва // Матеріали 4-ї міжнародної конференції “Сучасні комп'ютерні системи та мережі: Розробка та використання” - Львів: Національний університет “Львівська політехніка”, 2009. _ С. 67_71.

АНОТАЦІЯ

Яковлєва І.Д. Методи та засоби проектування алгоритмічних операційних пристроїв з графічного подання виконуваних алгоритмів. - Рукопис.

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

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

Ключові слова: потоковий граф алгоритму, алгоритмічний операційний пристрій, автоматизоване проектування, структурна матриця.

Яковлева И.Д. Методы и средства проектирования алгоритмических операционных устройств с графического представления алгоритмов. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук по специальностью 05.13.05 - компьютерные системы и компоненты. - Национальный университет ”Львовская политехника”, Львов, 2010.

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

Iakovlieva I.D. Methods and Means of Designing Algorithmic Operational Devices for Graphic Presentation of Performed Algorithms. - Manuscript.

Dissertation for the Degree of Candidate of Science in Technical Sciences, Speciality: 05.13.13 - Computer Systems and Components. - Lviv Polytechnic National University. - Lviv, 2010.

The dissertation deals with the problems of improving the process of designing algorithmic operational devices by development and practical application of methods and means of designing algorithmic operational devices for graphic representation of performed algorithms. In this dissertation the method of recording the algorithm flow graph in the form of structural matrix is suggested. This method does not require the performance of operations of determination and distribution of the vertices of algorithm flow graph in tiers. This enabled to formalize the stage of high-level synthesis of algorithmic operational devices. A new method of building a structural matrix out of the text of the algorithm performance program is suggested. It consists in the program text analysis and determination of operations that can be performed simultaneously with further recording their parallel performance order in the structural matrix. This enables to obtain operations distribution by the tiers of algorithm flow graph directly during the process of program analysis. The main results obtained are applied during the operational synthesis of computer devices from the algorithmic level.

Key words: algorithm flow graph, algorithmic operational device, automated designing, structural matrix.

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

...