Мультипроцесорні моделі рішення булевих рівнянь великої розмірності

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

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

Автореферат

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

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

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

Виконав Каменюка Євген Олександрович

Харків - 2009

АНОТАЦІЯ

програмний комп'ютер мультипроцесор булевий

Каменюка Е.А. Мультипроцесорні моделі рішення булевих рівнянь великої розмірності. - Рукопис. - Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - компьютерні системи та компоненти. - Харківський національний університет радіоелектроніки, Харків, 2008. Ключові слова: функціональна верифікація, апаратне прискорення моделювання, логічне моделювання, паралельні обчислення, цифрова система, компіляція, тестування.

Дисертація присвячена питанням значного підвищення швидкодії функціональної верифікації складних проектованих цифрових систем на кристалах. Програмне забезпечення логічного моделювання, виконуване на послідовному комп'ютері. У роботі удосконалено модель сферичного мультипроцесора PRUS, імплементованого в кристал ASІС. Удосконалено модель і структуру секвенсора, як базового осередку PRUS. Отримано нову модель пристрою керування й систему команд, достатню для паралельного програмування й розв'язання булевих рівнянь на основі мультипроцесора PRUS. Одержала подальший розвиток модель процесу розподілу системи булевих рівнянь між секвенсорами PRUS. Удосконалено модель (System Desіgn Flow) спільного використання сучасних засобів проектування й мультипроцесора PRUS. Розроблено програмне й апаратне забезпечення мультипроцесора, проведено достовірну верифікацію тестування функціональних властивостей мультипроцесора на валідних прикладах систем булевих рівнянь, що мають промисловий і науковий інтерес, з метою оцінювання швидкодії та апаратних витрат на реалізацію проекту; виконано програмну реалізацію та тестування компілятора для перетворення HDL-опису системи булевих рівнянь у мову машинних кодів мультипроцесора PRUS.

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

Актуальність теми. Для аналізу систем булевих рівнянь великої розмірності, існує декілька практично орієнтованих технологій. 1. Використання робочої станції, де система рівнянь розв'язується програмним шляхом і послідовно, оскільки існує тільки один процесор, хоча й досить потужний. 2. Розробка спеціалізованого паралельного процесора на основі PLD. Високий паралелізм обробки рівнянь компенсує досить низьку у порівнянні з CPU тактову частоту. Таке схемотехнічне рішення з можливістю перепрограмування є виграшним за продуктивністю. Недолік - відсутність гнучкості програмних методів розв'язання рівнянь і висока вартість реалізації системи на кристалі PLD при великих обсягах майбутніх продажів. 3. Краще рішення пов'язане з об'єднанням переваг CPU, PLD і ASIC, таких як: гнучкість програмування системи рівнянь, що дозволяє оперативно корегувати специфікацію у вигляді вихідних кодів; мінімально можлива потужність системи команд, що приводить до простих схемотехнічних рішень апаратурної реалізації процесора; розпаралелювання процесу розв'язання рівнянь завдяки ідеології PLD, але з елементами CPU - структура простих однобітових взаємозалежних між собою процесорів із власною системою команд для паралельного програмування; імплементація мультипроцесора в кристал ASIC для одержання максимально можливої тактової частоти, мінімальної вартості однієї мікросхеми при великих обсягах (більше 10 000) продажів, низького енергоспоживання; конвеєризація розв'язання системи рівнянь як виняткова властивість мультипроцесорної системи поряд з паралельним і послідовним способами вирішення задач.

Крім того, актуальність розробки мультипроцесора для розв'язання булевих рівнянь підтверджується існуючими тенденціями на ринку електронних технологій. Корпорація Intel з 2006 року випускає тільки багатоядерні архітектури, які підтримуються не лише власними програмними засобами, але й новою лінійкою продукції від Microsoft. Intel підтримує всіх розробників в області створення нових паралельних компіляторів, методів і засобів, орієнтованих на вирішення NP-важких задач. Важливо тут відзначити також той факт, що всі багатоядерні або мультипроцесорні архітектури орієнтовані на низьке енергоспоживання, що в умовах мобільності, безпроводовості й компактності має максимальний пріоритет на ринку комп'ютерних технологій. Крім того, прем'єр-конференції 2006 року (DAC, DATE) задекларували, що актуальні та обчислювально складні проблеми повинні вирішуватися спеціалізованими обчислювальними мікро- й мультипроцесорами. Зростає показник спеціалізованої орієнтації на вирішення конкретних задач - customization. Можливості універсальних комп'ютерів перевищують потреби даної області ринку. Зміщується акцент конкуренції з підвищення загальної продуктивності на удосконалення властивостей, які користувач готовий оплачувати додатково. Це - не тільки надійність і зручність, але й швидкодія вирішення складної проблеми, енергозбереження, автономність, мініатюризація, гнучкість і перепрограмовність.

Найбільший внесок у наукові досягнення, що стосуються автоматизації проектування і тестування цифрових систем, зробили такі вчені: D. Gajski, J. Roth, D.B. Аrmstrong, Y. Levendel, M. Breuer, M. Abramovici, Y. Zorian, P. Prinetto, J. Abraham, H. Fujiwara, I. Pomeranz, T. Nishida, F. Fummi, О.Г. Біргер, Д.В. Сперанський, П.П. Пархоменко, Ю.В. Малишенко, Р. Убар, В.П. Чіпуліс, Н.П. Байда, С.С. Бадулин, В.С. Харченко, Л.В. Дербунович, І.В. Кузьмин, В.Н. Ярмолик.

Зв'язок роботи з науковими програмами, планами, темами. Розробка основних положень дисертаційного дослідження виконувалася відповідно до планів НДР, програм і договорів Харківського національного університету радіоелектроніки: 1) Договір про науково-технічне співробітництво з фірмою Аldec Inc. (USA), № 02 від 19.11.2001 “Розробка програмних і апаратних засобів верифікації систем на кристалах, що реалізуються на основі програмувальних логічних інтегральних схем”; 2) Договір про науково-технічне співробітництво з Таллінським технічним університетом № 01 від 07.04.2004; 3) Договір про науково-технічне співробітництво з фірмою «Лаборатория Касперского», Москва, Росія, № 01 від 14.04.2005; 4) Дослідницький проект за грантом «SIGETEST - моделювання та синтез тестів для складних цифрових систем» за пропозицією компанії Intel, 2003; 5) Господарський договір № 05-19 з ЗАТ Северодонецкое НПО «Импульс» «Розробка технології автоматизованого проектування відмовостійких програмно-технічних комплексів (ПТК)»; 6) Держбюджетна НДР “Дослідження і розробка методів, структурних і архітектурних принципів апаратних і програмних засобів швидких цифрових перетворень зображень”, розділ “Система тестування цифрових засобів, що проектуються” (№ ДР 0104U004074); 7) Держбюджетна НДР “Розробка математичних методів, алгоритмів та інструментальних засобів надшвидких перетворень зображень”, розділ “Розробка основ нових інформаційних технологій в автоматизованому проектуванні, діагностиці засобів обчислювальної техніки” (№ ДР 0101U001948).

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

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

Мета досягається шляхом розв'язання таких задач дослідження:

1) розробка структурної моделі сферичного мультипроцесора PRUS, імплементованого в кристал ASIC, для вирішення систем булевих рівнянь великої розмірності;

2) розробка моделі пристрою керування з системою команд мультипроцесора, достатньою для паралельного програмування, з метою розв'язання системи булевих рівнянь великої розмірності;

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

4) удосконалення моделі (System Design Flow) маршруту проектування на основі використання сучасних засобів EDA (Electronic Design Automation) і мультипроцесора для ефективного розв'язання системи булевих рівнянь великої розмірності;

5) удосконалення моделі й структури секвенсора як базового осередку мультипроцесора, призначеної для апаратної емуляції примітивного елемента, що виконує функції: AND, OR, NOT, XOR;

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

Об'єкт дослідження - процес проектування цифрової системи на кристалі, що містить кілька процесорів.

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

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

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

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

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

2) уперше запропоновано модель пристрою керування з системою команд мультипроцесора, що складається з мінімального набору інструкцій для паралельного програмування, а саме: AND, OR, NOT, XOR, та дозволяє зменшити час розв'язання систем булевих рівнянь великої розмірності;

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

4) удосконалено модель (System Design Flow) маршруту проектування мультипроцесора на основі використання засобів автоматизації EDA (Electronic Design Automation), яка на відміну від існуючіх, орієнтована на розподіл булевих рівнянь між секвенсорами і програмування мультипроцесора, що дозволяє скоротити час циклу проектування за рахунок зменшення кількості операцій;

5) удосконалено структурну модель секвенсора як базового осередку мультипроцесора, яка на відміну від аналогів передбачає зменшення базового набору функцій до AND, OR, NOT, XOR, що забезпечує мінімальну апаратну реалізацію секвенсора та підвищення швидкості виконання операцій.

Практичне значення отриманих результатів обумовлюється: розробкою програмного й апаратного забезпечень мультипроцесора, достовірною верифікацією й тестуванням функціональних властивостей мультипроцесора на валідних прикладах систем булевих рівнянь, що становлять промисловий і науковий інтерес з метою оцінювання швидкодії й апаратурних витрат на реалізацію проекту; істотним (х10?-?х100) підвищенням швидкодії системи моделювання й верифікації проектованих цифрових виробів на основі використання мультипроцесора; програмною реалізацією та тестуванням компілятора для перетворення HDL-опису системи булевих рівнянь у мову машинних кодів мультипроцесора PRUS; впровадженням практичних результатів у технологічний і навчальний процеси у вигляді мультипроцесора PRUS, що дозволяє в автоматичному режимі здійснювати спільне моделювання й верифікацію цифрових проектів SoС у середовищі Active HDL v.6.3.

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

Результати дисертаційного дослідження у вигляді програмних додатків використовуються на підприємствах: ЗАТ НДІРВ, Харків (довідка про впровадження від 17 листопада 2005); ЗАТ “Импульс”, Сєвєродонецьк (довідка про впровадження від 22 грудня 2005); міжнародний консорціум «Энергосбережение», Харків (довідка про впровадження від 26 грудня 2005); у навчальному процесі ХНУРЕ на кафедрі автоматизованого проектування обчислювальної техніки (довідка про впровадження від 27 листопада 2006).

Особистий внесок здобувача. Усі основні результати, що виносяться на захист, отримано здобувачем особисто. У роботах, написаних у співавторстві, здобувачеві належить: [1] - дедуктивно-паралельний алгоритм моделювання, модель (System Design Flow) маршруту проектування мультипроцесора; [2] - структура даних і програмно-орієнтовані алгоритми для реалізації дедуктивного методу у складі автоматичної системи генерації тестів; [3] - структурна модель сферичного мультипроцесора PRUS, структурна модель секвенсора як базового осередку мультипроцесора; [4] - модель пристрою керування з системою команд мультипроцесора, модель процесу розподілу системи булевих рівнянь між секвенсорами мультипроцесорів; [6] - аналіз систем автоматизованого проектування мультипроцесорів; [7] - таблична дедуктивна модель несправності; [8] - детермінований алгоритм синтезу тестів; [9] - графова модель цифрового пристрою; [10] - алгоритми структурного аналізу цифрової системи; [11] - реалізація пристрою в FPGA, порівняльний аналіз характеристик; [12] - модель організації обчислювальних процесів; [13] - високопродуктивний метод моделювання несправностей; [14] - огляд ринкових тенденцій САПР; [15] - технології апаратного прискорення; [16] - дедуктивний метод справного моделювання цифрових систем; [17] - розробка архітектури сферичного мультипроцесора; [18] - методи тестопридатного аналізу; [19] - архітектура мультипроцесора; [20] - математична модель змістовного графа автомата.

Апробація результатів дисертаційної роботи. Основні результати роботи були представлені й обговорені на таких конференціях: 1) 2-а міжнародна науково-технічна конференція «Проблемы информатики и моделирования», Харків, 28-30 листопада 2002; 2) 7-й міжнародний молодіжний форум “Радиоэлектроника и молодежь в ХХІ веке”, Харків, 22-24 квітня 2003; 3) 16-а міжнародна науково-технічна конференція: “Перспективні ІУС на залізничному, промисловому й міському транспорті”, Алушта, 2003; 4) Науково-практична конференція “Сучасні технології проектування систем на мікросхемах програмувальної логіки”, Харків, 2003; 5) International Conference: «Modern Problems of Radio Engineering, Telecommunications and Computer Science», Lviv-Slavsko, February 24-28, 2004; 6) 10_а ювілейна міжнародна наукова конференція «Теорія й техніка передачі, прийому й обробки інформації», Туапсе, 28 вересня - 1 жовтня 2004; 7) 2-а міжнародна конференція «East-West Design and Test Conference», Алушта, 2004; 8) 5-а міжнародна науково-практична конференція «Сучасні інформаційні й електронні технології», Одеса, 17-21 травня 2004; 9) 8-а міжнародна конференція «CADSM 2005», Львів, 2005; 10) 9-й міжнародний молодіжний форум “Радіоелектроніка й молодь в ХХІ столітті”, Харків, 2005; 11) Науково-практична конференція «Інформаційні технології - у науці й утворенні», Харків, 21-22 березня 2005; 12) 12th International Conference “Mixed Design of Integrated Circuits and Systems”, Krakow, Poland, June 22-25, 2005; 13) 3-я міжнародна конференція «East-West Design and Test Conference», Одеса, 2005; 14) 4-а міжнародна конференція «East-West Design and Test Conference», Сочі, 2006.

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

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

У першому розділі розглянуто моделі й методи проектування систем на кристалі, технології реалізації цифрових систем, сучасні маршрути проектування, підтримувані засобами проектування провідних фірм світу Cadence Desіgn Systems, Synopsys, Mentor Graphіcs, Magma, Vіrage Logіc, Aldec, Alatek, системи й мережі на кристалі, розглянуто також основні типи паралельних обчислювальних систем: мультипроцесори й мультикомп'ютери, способи організації зв'язків між вузлами та апаратне прискорення верифікації.

У другому розділі удосконалено модель (System Design Flow) маршруту проектування мультипроцесора на основі використання засобів автоматизації EDA (Electronic Design Automation), розроблено нову модель пристрою керування з системою команд мультипроцесора, що складається з мінімального набору інструкцій для паралельного програмування, а саме: AND, OR, NOT, XOR, удосконалено структурну модель секвенсора як базового осередку мультипроцесора. Маршрут проектування містить у собі: загальну структуру системи компіляції та розподілу систем булевих рівнянь, який представлен на рис. 1. Система складається з таких підсистем: компіляції вихідних VHDL файлів, розподілу булевих рівнянь, зв'язування підсхем, асемблера. Підготовка вихідних моделей здійснюється в засобах уведення проектів Aldec Active-HDL, Riviera. Стандартні засоби логічного синтезу (Synplicity Synplify, Altera Quartus, Xilinx ISE) перетворюють вхідний опис до списку міжз'єднань на вентильному рівні (gate level netlist). Інтеграція з існуючими засобами САПР здійснюється за допомогою підтримки стандарту VHDL. Вихідні моделі, описані мовою VHDL, подаються на парсер. У процесі синтаксичного аналізу в моменти виявлення граматичних правил парсер робить виклики певних CALLBACK-функцій підключеного семантичного клієнта. Ключовим компонентом будь-якого компілятора є система аналізу формально визначеної мови. Розроблено компілятор-аналізатор мови VHDL: принципи побудови лексичного й синтаксичного аналізатора, взаємодія з генератором семантичної моделі, підходи до відновлення аналізатора у випадку виявлення помилок у коді, що подається. Синтаксичний аналізатор мови VHDL реалізований у компіляторі “FSC” із застосуванням інструментального засобу BISON - сучасної високопродуктивної реалі-зації системи YACC. Вихідною інформацією для BISON є конструкції у вигляді граматичних правил у формі Backus-Naur Form (BNF) і відповідні їм семантичні підпрограми мовою C/C++. BISON генерує вихідний код програми, що являє собою модель, подібну до автомата з магазинною пам'яттю, у якому переходи між станами виконуються в процесі реєстрації терміналів і нетерміналів. Цей автомат містить стек правил, виконуваних парсером, і стек терміналів і нетерміналів з відповідними їм семантичними об'єктами. Якщо аналізатор формально визначеної мови можна назвати ключовим керуючим компонентом, характерним для будь-якого компілятора, то ключовим компонентом даних, безумовно є внутрішня семантична модель - модель подання змісту трансльованих мовних конструкцій. Розроблена модель AGLM - Abstract Gate-Level Model (абстрактна модель вентильного рівня) будується семантичним клієнтом парсера в результаті розпізнавання в VHDL-коді певних синтаксичних конструкцій. Структури даних AGLM оперують узагальненими HDL-поняттями, тому, у перспективі, вони здатні представити модель пристрою вентильного рівня, задану будь-якою мовою опису апаратури.

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

Для виконання поставлених задач розроблено спеціалізовану паралельну обчислювальну архітектуру. ЇЇ модель є ієрархічною параметризованою структурою, що являє собою IP-Core - протестований, верифікований і функціонально оптимальний модуль. Гнучкість використання моделі досягається за рахунок використання ряду параметрів: розрядність програмного лічильника PC_WIDTH, розмірність обчислювальної матриці MD, розрядність програмного слова WORD_BITS.

Секвенсор - це обчислювальний пристрій, що виконує елементарні логічні операції в точно визначеній послідовності та не має інструкцій умовного й безумовного переходу (розгалужень). Структурна модель секвенсора як базового осередку мультипроцесора зображена на рис. 4. Отже, визначається кількість тактів роботи секвенсора, що дорівнює кількості інструкцій у програмній пам'яті. Час обробки T одного тест-вектора визначається як , де Тi - кількість тактів роботи i-го секвенсора в обчислювальній матриці розміром n.

Розроблено систему команд секвенсора, що містить такі чотири інструкції: NOP, NAND, BYPASS, STORE: NOP - немає операції. Секвенсор зберігає результат попередньої операції DATA_OUT. Команда не має операндів. Фактично здійснюється простій секвенсора на одному такті роботи; NAND - виконання послідовної операції И-НЕ над вмістом секвенсора DATA_OUT (результат опередньої операції) і вхідною змінною DATA. Операнд - адреса зовнішнього порту секвенсора; BYPASS - комутація виходу й одного з входів. Під час виконання інструкції секвенсор зберігає результат попередньої операції. Операнд - адреса зовнішнього порту секвенсора; STORE - збереження вмісту секвенсора у відповідному вихідному буфері. Команда не має операндів. Усі команди виконуються за один такт роботи пристрою. Формат команди представлений на рис. 5. Операнд адресує вісім сусідніх секвенсорів, зовнішній вихід, константи 0/1 (як зазначено в пристрої вхідного мультиплексора).

Емуляція мультипроцесора здійснюється на платі Aldec HES2x2000MB. Апаратна частина HES (Hardware Embedded Simulator) є нестандартним PCI пристроєм, виконаним у вигляді системи на платі, що містить у собі контроллер PCI шини й мікросхему програмувальної логіки FPGA Virtex 2 Pro, ємністю 2 мільйони еквівалентних логічних вентилів. HES - технологія для апаратного прискорення, що підвищує продуктивність моделювання ASIC і FPGA проектів в 10-50 разів у порівнянні із традиційними методами. Ідея прискорення HES лежить у поділі проекту між програмним ядром моделювання і PCI-платою апаратного прискорення.

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

У третьому розділі запропоновано структурну модель сферичного мультипроцесора PRUS для розв'язання систем булевих рівнянь великої розмірності, імплементованого в кристал ASIC, модель процесу розподілу системи булевих рівнянь між секвенсорами мультипроцесорів. Для дослідження структури цифрового пристрою використовується математичний опис у вигляді логічних схем. Дослідження в даній роботі обмежені класом комбінаційних схем (без зворотних зв'язків). Обробка послідовносних схем здійснюється шляхом розриву ліній глобальних зворотних зв'язків. На рис. 7 показана схема З17 з бібліотеки ISCAS87 та її граф.

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

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

Кожний процесор в PRUS пов'язаний з вісьмома сусідніми: з двома - по горизонталі, з двома - по вертикалі і з чотирма - по діагоналях. При цьому крайні процесори в матриці P теж мають вісім сусідів, тому що PRUS має сферичну структуру. Множина процесорів, безпосередньо пов'язаних з даним процесором, має вигляд, показаний на рис. 8, праворуч. , де операції та визначаються у формі:

,

.

В останніх виразах x(mod n) - це остача цілого числа x при діленні на n, . На рис. 9 показані вертикальна й горизонтальна відстані між двома вершинами графа GS(7).

Завдяки наявності діагональних зв'язків, з однієї вершини в іншу можна добратися або за k, або за l кроків (рис. 9). Фактично, відстань між вершинами та на графі GS(n) є найбільшим з чисел k і l, що визначається в такий спосіб: .

У загальному випадку довжина всього графа GC(n) дорівнює n, тому довжина другого ланцюга, що з'єднує вершини x і y, визначається як . Тоді відстань між вершинами x, y у графі GC(n) буде дорівнювати . Для зручності введемо позначення:

.

Метрика, що визначає відстань між довільними вершинами та на графі GS(n), буде мати вигляд: .

Діаметр dm(n) графа GC(n) дорівнює

,

де ][ - ціла частина.

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

;

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

Для пошуку найкоротшого шляху використовуються методи теорії графів. При цьому планарна структура процесора інтерпретується неорієнтованим графом, представленим на рис. 8, у якому кожному процесору ставлять у відповідність вершину графа, а міжз'єднанням - його ребра. Граф G задається множиною точок або вершин і множиною ліній або ребер , що з'єднують між собою всі або частину точок. Ребра позначаються парою, що складається з початкової та кінцевої вершин (тобто двома кінцевими вершинами ребра) . Отже, граф G повністю задається та позначається парою (X,A).

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

Метод знаходить один з мінімальних маршрутів (що проходять через мінімальну кількість вершин) у графі G=(X,A), заданому матрицею зв'язності C. Маршрут шукається з вершини номер s до вершини номер t.

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

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

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

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

У типовому маршруті проектування найнижчим прийнятним рівнем опису цифрового проекту є вентильна схема (Gate-level netlist). Переваги використання даного рівня опису полягають в наступному: елементами вентильної схеми є винятково логічні примітиви (І, АБО, НЕ); система булевих рівнянь може бути однозначно представлена вентильною схемою; зберігається достатній рівень абстракції від цільової архітектури (ASIC або FPGA). Як засіб уведення проекту (Behavioral Description, RTL Description) використовується програма Aldec Active-HDL 7.1. Як програма логічного синтезу використовується Synplicity Synpilfy Pro 8.1 або Synopsys Design Compiler.

Розроблений маршрут проектування має ряд переваг перед традиційним. Можна виділити такі: менша кількість етапів проектування, що значно скорочує час верифікації цифрового пристрою; виключені етапи Timing Verification і Layout Verification, які є «вузьким місцем» у традиційному циклі. Можна відзначити недолік, який полягає у тому, що реалізований цифровий пристрій буде мати меншу продуктивність, ніж аналогічний реалізований в архітектурі ASIC. Запропонований цикл проектування припускає інтеграцію з сучасними засобами проектування: уведення проекту, логічне моделювання, діагностика, верифікація, логічний синтез, тестування, імплементація.

Уведення проекту підтримується системою Aldec Active-HDL 7.1, що є інтегрованим середовищем розробки для VHDL, Verilog, EDIF і System проектів. Логічний синтез проекту підтримується засобом Synplicity Synplify 8.1 Pro.

Підтримка імплементації здійснюється інтеграцією із САПР Xilinx XST у складі Xilinx ISE. Завантаження проекту на плату прототипування здійснюються системою Aldec DVM 3.3.

Аналіз функціонування програмно-апаратного комплексу проведений на більш ніж 500 комбінаційних і послідовносних схемах з бібліотек ISCAS, Aldec IP-Core Library та інших вільнодоступних бібліотек [www.opencores.org]. Розроблено автоматизовану інфраструктуру, що полегшує проведення тестів і аналіз результатів.

Експериментальні дослідження параметрів продуктивності компілятора показали помітну перевагу над існуючими комерційними аналогами відомих компаній-виробників. Статистика часу компіляції великих VHDL-моделей у системі PRUS (компілятор FSC) і Active-HDL (компілятор COMP96). У середньому, компілятор FSC в 3-3,5 рази швидший, однак існують схеми, на яких співвідношення швидкості коливається в обидва боки. Це можна пояснити особливостями ієрархії тестових моделей. Тест Blowfish має дуже маленьку глибину ієрархії (1 рівень), але дуже велику кількість екземплярів, у той час, як тести Ydelay, LZS мають більшу вкладеність. Алгоритми компіляції орієнтовані на обробку моделей з розвинутою ієрархією компонентів, тому на "плоских" моделях перевага у продуктивності не помітна.

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

Швидкість моделювання мульти-процесора порівнювалася зі швидкістю моделювання САПР Active-HDL 7.1. Матриця PRUS мала конфігурацію 8 на 8, тактова частота - 160 млн. тактів за секунду. На рис. 17 i в табл. 2 представлена залежність прискорення апаратної емуляції пристрою від розміру модельованої схеми. У загальному випадку прискорення становить 500-600 разів для схем великої розмірності. Тут можна відзначити недолік PRUS архітектури, у якій емуляція внутрішніх функцій схеми здійснюється повністю для кожного тест-вектора, незалежно від того, відбуваються нові події на входах пристрою чи ні.

Таблиця 1 - Оцінка прискорення моделювання системи PRUS (S_a - швидкість моделювання Active-HDL, S_p - швидкість моделювання PRUS)

ВИСНОВКИ

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

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

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

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

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

4. Удосконалено модель (System Design Flow) маршруту проектування на основі використання сучасних засобів EDA (Electronic Design Automation) і мультипроцесора, яка на відміну від існуючих підтримує сучасні стандарти та інтерфейси проектування, що забезпечує її просту інтеграцію з зовнішніми засобами введення проекту, логічного синтезу і моделювання, а також дозволяє ефективно розв'язувати системи булевих рівнянь великої розмірності та скоротити час циклу проектування за рахунок зменшення кількості кроків.

5. Удосконалено модель і структуру секвенсора як базового осередку мультипроцесора, призначеного для апаратної емуляції примітивного елемента, що виконує функції AND, OR, NOT, XOR, яка відрізняється мінімальною апаратною реалізацією та дозволяє моделювати схеми довільної складності, підвищити швидкість моделювання і скоротити вартість виробництва.

6. Розроблені моделі реалізовано у вигляді програмного й апаратного забезпечень мультипроцесора, що дозволяють істотно (х10?-?х100) підвищити швидкодію системи моделювання та верифікації проектованих цифрових виробів. Здійснено програмну реалізацію і тестування нового компілятора для перетворення HDL-опису системи булевих рівнянь у мову машинних кодів мультипроцесора PRUS.

7. Впроваджено практичні результати у технологічний і навчальний процеси у вигляді мультипроцесора PRUS, що дозволяє в автоматичному режимі здійснювати спільне моделювання й верифікацію цифрових проектів SoС у середовищі Active HDL v.6.3.

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

1. Hahanov V. Advanced software tools for fault simulation and test generation / V. Hahanov, A. Egorov, O. Melnikova, V. Obrizan, E. Kamenuka, O. Krapchunova, O. Guz // Радиоэлектроника и информатика. - Харьков, 2003. - №3. - C. 77-82.

2. Хаханов В.И. Модифицированный дедуктивный метод моделирования неисправностей цифровых систем / В.И. Хаханов, Е.А. Каменюка, А.Н. Парфентий // Электронное моделирование. - Киев, 2003. - №4. - С. 57-77.

3. Гайдук С.М. Сферический мультипроцессор PRUS для решения булевых уравнений / С.М. Гайдук, В.И. Хаханов, В.И. Обризан, Е.А. Каменюка // Радиоэлектроника и информатика. - Харьков - 2004. - № 4(29). - С. 107-116.

4. Хаханов В.И. Специализированный процессор для решения систем булевых уравнений большой размерности / В.И. Хаханов, Е.А. Каменюка, О.В. Мельникова // Вестник Херсонского национального технического университета. - 2005. - №1(21). - C. 440-444.

5. Каменюка Е.А. PRUS- средство моделирования систем булевых уравнений / Е.А. Каменюка // Вестник Национального технического университета «ХПИ» Харьков, 2005. - №41. - C. 19-27.

6. Хаханов В.И. САПР и международный рынок электронных технологий / В.И. Хаханов, В.И. Обризан, Е.А. Каменюка, А.В. Хаханова // Контрольно-измерительные приборы и автоматика. - Харьков. - 2004. - №8. - C. 4-13.

7. Хаханов В.И. Дедуктивный метод обратного моделирования неисправностей для цифровых проектов / В.И. Хаханов, А.Л. Чамян, Е.А. Каменюка // Материалы 2-й Международной научно-технической конференции “Проблемы информатики и моделирования” - Харьков. - 2002. - C. 44.

8. Хаханов В.И. Структурный анализ цифровых проектов в системе моделирования / В.И. Хаханов, Е.А. Каменюка, А.Н. Парфентий // Материалы 7-го Международного молодежного форума “Радиоэлектроника и молодежь в 21 веке ”. - Харьков, 22-24 апреля 2003г. - С.458.

9. Hahanov V.I. SIGETEST - Test generation and fault simulation for digital designs / V.I. Hahanov, D.M. Gorbunov, Y.V. Miroshnichenko, O.V. Melnikova, V.I. Obrizan, E.A. Kamenuka // Материалы научно-практической конференции “Современные технологии проектирования систем на микросхемах программируемой логики”. - Харьков, 2003г. - С. 50-53.

10. Хаханова И.В. Метод структурного анализа для цифровых систем / И.В. Хаханова, Е.А. Каменюка, О.А. Гузь, В.И. Шевченко // Материалы 16-й международной научно-технической конф. “Перспективные ИУС на железнодорожном, промышленном и городском транспорте”. - Алушта, 2003г. - С. 21.

11. Егоров А.А. Совместная верификация аппаратной и программной частей систем на кристалле (SOC) реализуемых на FPGA и CPLD / А.А. Егоров, Я.В. Мирошниченко, Е.А. Каменюка // Тезисы докладов 10 юбилейной международной научной конференции «Теория и техника передачи, приема и обработки информации». - Туапсе, 28 сентября - 1 октября 2004 г. С. 141-142.

12. Hahanova Irina. Computing Process Organization Based on Logic Nets / Irina Hahanova, Evgeniy Kamenuka, Olga Lukashenko, Khavar Parvez // Proceedings of the International Conference “Modern Problems of Radio Engineering, Telecommunications and Computer Science. - Lviv-Slavsko, February 24-28, 2004. - P. 451-454.

13. Zaychenko S.A. Set Operation Speed-up of Fault Simulation / S.A. Zaychenko, A.N. Parfentiy, E.A. Kamenuka, H. Ktiaman // Proceedings of the 2nd East-West Design and Test Workshop. - Alushta, 23-26 September, 2004. - P. 231-237.

14. Хаханов В.И. САПР и международный рынок электронных технологий / В.И. Хаханов, В.И. Обризан, Е.А. Каменюка, А.В. Хаханова // Труды пятой международной научно-практической конференции «Современные информационные и электронные технологии». - Одесса, 17-21 мая 2004г. - C. 137.

15. Kamenuka E.A. Set operations speed-up in Deductive Fault Simulation Method / E.A. Kamenuka, A.V. Kiyashenko, Hassan Ktiaman. // Proceedings of the 8th International Conference CADSM. - Lviv, 2005. - P 356-361.

16. Ковалев Е.В. ASFTEST система тестирования цифровых автоматов / Е.В. Ковалев, А.Н. Парфентий, А.В. Киященко, Е.А. Каменюка // Материалы научно - практической конференции «Информационные технологии - в науке и образование». - Харьков, 21-22 марта 2005г. - С. 42-45.

17. Обризан В.И. Сферический мультипроцессор для решения систем булевых уравнений / В.И. Обризан, Е.А. Каменюка, Хассан Ктейман, Ваде Гриби // Материалы 9-го международного молодежного форума “Радиоэлектроника и молодежь в ХХІ веке”. - Харьков: ХНУРЭ. - 2005.- 541с.

18. Kaminskaya M.O. Quantitive Estimation of the Testability for Complexity Digital Devices Before Test Generation / M.O. Kaminskaya, V.I Hahanov, W.Ghribi, E.A. Kamenuka // Proceedings of the 12th International Conference “Mixed Design of Integrated Circuits and Systems”. - Krakow, June 22-25, 2005. - P. 451-454.

19. Hyduke S. Emulation Processor Network for Gate-Level Digital Systems / S. Hyduke, E. Kamenuka, I. Pobezhenko, O. Melnikova // Proceedings of the 3rd East-West Design and Test Workshop. - Odessa, September 15-19, 2005. - P. 257-260.

20. Babich Anna. The Development and Application of FSM-Models in Active-HDL Environment for Network Protocols Testing / Anna Babich, Oleksandr Parfentiy, Eugene Kamenuka, Karina Mostovaya // Proceedings of the 4th IEEE East-West Design and Test Workshop. - Sochi, 15-19 September 2006. - P.279-281.

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