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

ДЕРЖАВНИЙ ВИЩИЙ НАВЧАЛЬНИЙ ЗАКЛАД

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

УДК 681.324

Автореферат

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

Розробка і дослідження методів синтезу швидкодіючих мікропрограмних пристроїв керування

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

Ніколаєнко Денис Володимирович

ДОНЕЦЬК - 2010

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

Робота виконана в Державному вищому навчальному закладі «Донецький національний технічний університет» Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент Ковальов Сергій Олександрович, доцент кафедри «Електронні обчислювальні машини» ДВНЗ «Донецький національний технічний університет», м. Донецьк.

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

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

доктор технічних наук, професор Данилов Володимир Васильович, завідувач кафедри радіофізики Донецького національного університету МОН України, м. Донецьк.

Захист відбудеться 21 жовтня 2010 р. о 14 годині на засіданні спеціалізованої вченої ради Д 11.052.03 Державного вищого навчального закладу «Донецький національний технічний університет» за адресою: 83001, м. Донецьк, вул. Артема, 58, уч. корпус 8, ауд. 704.

З дисертацією можна ознайомитися в бібліотеці Державного вищого навчального закладу «Донецький національний технічний університет» за адресою: 83001, м. Донецьк, вул. Артема, 58, уч. корпус 2.

Автореферат розісланий “17” вересня 2010 р.

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

Загальна характеристика роботи

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана протягом 2007-2009 р.р. відповідно до тематичного плану Державного вищого навчального закладу «Донецький національний технічний університет» за темою НДР №Н-5-06 «Теорія і методи проектування і тестування цифрових пристроїв комп'ютерних систем», а також відповідно до наукового напрямку кафедри «Електронні обчислювальні машини» державного вищого навчального закладу «Донецький національний технічний університет».

Мета і завдання дослідження. Метою роботи є збільшення швидкодії схем КМПК з розділенням кодів за рахунок застосування методів кешування сигналів.

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

1. Аналіз існуючих структур КМПК з розділенням кодів з метою виявлення шляхів їх удосконалення.

2. Розробка структур і методів синтезу КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд.

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

4. Моделювання структур КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд.

5. Дослідження розроблених структур з метою визначення області їх ефективного застосування.

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

Предмет дослідження - методи оптимізації швидкодії схем КМПК.

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

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

1. Запропоновано використовувати метод кешування сигналів у структурах КМПК з розділенням кодів з метою збільшення середнього швидкодії пристроїв.

2. Розроблено нові структури та методи синтезу КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд, що володіють більш високим середнім швидкодією в порівнянні з раніше відомими структурами.

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

Практичне значення отриманих результатів:

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

2. Отримано аналітичні залежності апаратурних витрат у модулі кеш-пам'яті від параметрів модуля кеш-пам'яті, що дозволяють оцінити приріст витрат апаратури в структурах КМПК з розділенням кодів за рахунок додавання модуля кеш-пам'яті мікрокоманд.

3. Визначено область ефективного застосування розроблених структур КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд.

4. Результати теоретичних і практичних досліджень дисертаційної роботи використані на підприємстві «Національна енергетична компанія УКРЕНЕРГО». Також результати роботи використані в навчальному процесі кафедри «Технічна експлуатація автомобілів» і при проведенні науково-дослідних робіт НІЧ Горлівського автомобільно-дорожнього інституту Донецького національного технічного університету.

Особистий внесок здобувача. Здобувачем виконано розробку структур КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд. Запропоновано евристичний алгоритм розміщення даних в керуючої пам'яті, спрямований на підвищення ймовірності кеш-попадань використовуваного модуля кеш-пам'яті. Також особисто здобувачем побудовано моделі структур з використанням мови опису апаратури VHDL, за допомогою яких проведено дослідження розроблених структур і визначена область їх ефективного використання.

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

Друга міжнародна науково-практична конференція молодих вчених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія» (Донецьк, 13-14 травня 2008 року);

Десятий міжнародний науково-практичний семінар «Практика і перспективи розвитку партнерства в сфері вищої школи» (Донецьк, 4-7 травня 2009 року);

Третя міжнародна науково-практична конференція молодих вчених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія» (Донецьк, 14-15 травня 2009 року);

П'ята Міжнародна науково-технічна конференція «Гарантоздатні системи, сервіси та технології» (Кіровоград, 11-15 травня 2010 року);

наукові семінари кафедри «Електронні обчислювальні машини» Державного вищого навчального закладу «Донецький національний технічний університет».

Публікації. За матеріалами дисертаційної роботи опубліковано 9 наукових робіт, з яких 6 статей опубліковані у виданнях, включених до переліку ВАК України, і 3 праці в матеріалах наукових конференцій.

Структура і обсяг роботи. Дисертація складається зі вступу, 4 розділів, висновків, списку використаних джерел з 144 найменувань, розміщеного на 12 сторінках, і одного додатка, розміщеного на 4 сторінках. Повний обсяг дисертації становить 164 сторінки друкованого тексту, містить 35 малюнків і 27 таблиць.

Основний зміст роботи

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

Алгоритми управління цифрових систем можуть бути реалізовані у вигляді мікропрограмних пристроїв керування (МУУ). Однією з різновидів МУУ є композиційне микропрограммное пристрій управління, структура якого представляє собою композицію автоматів з «жорсткою» та «програмованої» логікою.

В КМПК схема адресації СА і регістр пам'яті РП є автомат з «жорсткою» логікою P1, призначений для адресації мікрокоманд при порушенні природного порядку їх виконання.

Керуюча пам'ять УП, призначена для зберігання прошивки, і лічильник адреси мікрокоманд СТ є автомат P2 з «програмованої» логікою і природною адресацією мікрокоманд. Схема формування мікрооперацій СФМО формує безліч мікрооперацій Y, яке надходить в операційний автомат (ОА). Мікрооперацій y0 управляє СТ і РП, реалізуючи умовні та безумовні мікропрограмні переходи.

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

Визначення 1. операторної лінійної ланцюгом ДСА називається кінцева послідовність операторних вершин

,,

де i - номер компоненти кортежу; , існує дуга .

Визначення 2. Входом ОЛЦ , називається вершина , де Оg - безліч компонент ОЛЛ , вхід якої пов'язаний тільки з виходами початкової, умовної або входять до інших ОЛЦ операторних вершин.

Визначення 3. Вхід ОЛЦ називається головним входом, якщо відсутній зв'язок цього входу з виходами операторних вершин.

Визначення 4. Виходом ОЛЦ називається вершина b_qО^g, вихід якої пов'язаний зі входами кінцевої, умовної або операторної вершини, що не входить в ОЛЦ .

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

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

1. КМПК з розділенням кодів і Неелементарні ОЛЦ.

2. КМУУ з розділенням кодів і елементарними ОЛЛ.

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

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

Оскільки робота кеш-пам'яті в складі цифрового пристрою є «прозорою», впровадження модуля кеш-пам'яті не повинно позначатися на логіці роботи КМПК, отже, основні етапи синтезу структур КМПК з розділенням кодів і кеш-пам'яттю будуть збігатися з методами для структур-прототипів без кеш-пам'яті.

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

У другому розділі - «Композиційні мікропрограмні пристрою керування з розподілом кодів і кеш-пам'яттю» - розроблені структури КМПК c поділом кодів і кеш-пам'яттю мікрокоманд, для яких отримано аналітичні вирази для визначення середньої тривалості такту роботи даних структур. Також розроблений евристичний алгоритм оптимізації розміщення ОЛЦ в адресному просторі керуючої пам'яті.

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

У даних структурах блок управління кеш-пам'яттю БО управляє керуючої пам'яттю і блоком даних кеш-пам'яті БД, для чого виробляє безлічі керуючих сигналів Z1 і Z2 відповідно.

Блок даних виконано з використанням елементного базису статичної пам'яті (наприклад, на кристалі ПЛІС). Швидкодія БД в кілька разів перевищує швидкодію УП, в той час як інформаційна ємність БД складає в середньому не більше 10% ємності УП. У разі кеш-попадання з БД зчитується мікрокоманда відповідно до адреси, утвореним конкатенацией сигналів ? і T. У випадку кеш-промаху в БД з керуючої пам'яті переписується блок микрокоманд D, причому кількість мікрокоманд в блоці визначається кількістю інформаційних слів в рядку кеш-пам'яті (тут під інформаційним словом кеш-пам'яті мається на увазі мікрокоманда, розрядність якої зазвичай відповідає потужності безлічі мікрооперацій).

Якщо БО виявив запитану команду в кеш-пам'яті (ситуація кеш-попадання), з поточного такту роботи виключається тривалість спрацьовування УП, і тривалість такту роботи th (S1k) в даному випадку складе

t_h(S_1k) = t_СА + max(t_СТ, t_РП) + t_БУ + t_БД + t_ОА,(1)

де tОА - тривалість спрацьовування автомата, що працює під управлінням КМУУ.

Якщо запитана команда не виявлена в кеш-пам'яті (ситуація кеш-промаху), то потрібно читання відповідних даних з УП і завантаження їх в БД, в результаті чого тривалість такту роботи tm (S1k) складе

t_m(S_1k) = t_СА + max(t_СТ, t_РП) + t_БУ + t_УП + t_БД + t_ОА.(2)

Оскільки ситуації кеш-влучень і кеш-промахів виникають з певними можливостями і є несумісними подіями, середня тривалість такту роботи структури S1k буде визначатися як середнє між th (S1k) і tm (S1k):

t_ср(S_1k) = p_ht_h(S_1k) + (1 - p_h)t_m(S_1k),(3)

де ph - ймовірність кеш-влучень модуля кеш-пам'яті.

В силу схожості структур S1k і S2k вираження (1) - (3) справедливі і для структури S2k.

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

Таким чином, збільшення ефективності використання модуля кеш-пам'яті можливо за рахунок збільшення значення ймовірності кеш-попадань ph при заданих значеннях th і tm.

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

Як показали дослідження, виконані за допомогою розробленої програмної імітаційної моделі, значення ймовірності кеш-попадань алгоритму залежить від порядку проходження ОЛЦ в адресному просторі ПЗУ схеми УП, а точніше - від спільного перебування ОЛЦ в одному блоці пам'яті.

Кожна ОЛЛ може бути охарактеризована наступними параметрами:

1. Вага ОЛЦ ¬- величина, яка дорівнює сумі ймовірностей (частот) виконання всіх микрокоманд даної ОЛЦ.

2. «Небезпечний» вага ОЛЦ - величина, що характеризує ймовірність виникнення кеш-промаху при переході в дану ОЛЦ. «Небезпечний» вага ОЛЦ чисельно дорівнює сумі частот микрокоманд, у тому числі є перехід в дану ОЛЦ, помножених на імовірність відповідного переходу.

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

Подібний алгоритм повинен мати наступні властивості:

1. Безліч всіх можливих варіантів розміщення ОЛЦ має зводитися до деякій підмножині, що дозволяє розглянути включені в нього варіанти розміщення за прийнятний час. Таким чином, алгоритм не повинен виконувати повний перебір варіантів розміщення ОЛЦ.

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

3. Не маючи прив'язки до архітектури кеш-пам'яті, алгоритм не повинен визначати абсолютно оптимальний варіант розміщення даних. Проте, результат роботи алгоритму (або безліч результатів) повинен в загальному випадку бути близький до результатів, які могли б бути отримані при повному переборі або точному аналітичному розрахунку.

Відповідно до даних вимог в дисертаційній роботі запропонований алгоритм, в основі якого лежить ряд евристичних правил (евристик), заснованих на експериментальній очевидності:

Евристика 1. Імовірність кеш-влучень ДСА не залежить від того, яким по порядку блоку пам'яті належить ОЛЦ.

Евристика 2. Імовірність кеш-влучень не залежить від порядку проходження ОЛЦ в блоці.

Евристика 3. Якщо ОЛЦ Oi має переходи в ОЛЦ Oj, то розміщення цих ОЛЦ в одному блоці пам'яті знижує «небезпечний» вага ОЛЦ Oj.

Евристика 4. Збільшення кількості ОЛЦ, на які розбита безліч мікрокоманд розглянутої ДСА, не впливає на ймовірності виконання мікрокоманд, але збільшує кількість варіантів розміщення ОЛЦ.

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

Евристичний алгоритм включає наступні етапи:

1. Визначення частот виконання мікрокоманд.

2. Віднесення всіх ОЛЦ до безлічі нерозподілених ОЛЛ.

3. Вважати поточним початковий блок УП.

4. Якщо поточний блок повністю заповнений, вважати поточним наступний порожній блок.

5. Якщо поточний блок порожній, помістити в нього одну з нерозподілених ОЛЛ.

6. Якщо поточний блок заповнений частково, додати в нього ту нерозподілений ОЛЛ, яка максимально знизить «небезпечний» вага ОЛЦ, що знаходяться в даному блоці.

7. Якщо залишилися нерозподілені ОЛЛ, перейти до пункту 4.

8. Кінець.

У пункті 5 алгоритму в порожній блок додається одна з нерозподілених ОЛЛ. Вибір нерозподіленого ОЛЛ в якомусь сенсі може бути довільним: яка б ОЛЦ не була обрана першою в блоці, алгоритм повинен заповнити блок оптимальним способом. При цьому ті ОЛЦ, які будуть додані до блок, приречені на «сусідство» з першої обраної ОЛЦ, і варіанти їх «сусідства» з іншими ОЛЦ не розглядаються. Таким чином, спосіб вибору першої ОЛЦ в блоці впливає на кінцеве вміст блоку і, в кінцевому підсумку, на ймовірність кеш-влучень ДСА.

У роботі пропонуються шість варіантів способу вибору першої ОЛЦ для порожнього блоку, які умовно названі стратегіями вибору нерозподілених ОЛЛ:

Стратегія 1: Вибирається ОЛЛ з максимальною вагою.

Стратегія 2. Вибирається ОЛЛ мінімальною вагою.

Стратегія 3. Вибирається ОЛЛ з максимальним «небезпечним» вагою.

Стратегія 4. Вибирається ОЛЛ з мінімальним «небезпечним» вагою.

Стратегія 5. Вибирається ОЛЛ з максимальним відношенням «небезпечного» ваги до звичайного вазі.

Стратегія 6. Вибирається ОЛЛ з мінімальним відношенням «небезпечного» ваги до звичайного вазі.

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

Евристичний характер запропонованого алгоритму полягає в наступному:

1. Оптимізація розміщення проводиться для кожного блоку окремо без урахування зв'язків між блоками. Велика кількість переходів між ОЛЛ, що знаходяться в різних блоках, може призводити до збільшення кількості кеш-промахів і зниження величини ph.

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

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

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

Також для запропонованих в дисертації структур S1k і S2k розроблений алгоритм синтезу логічної схеми, що включає наступні етапи:

1. Розбиття безлічі мікрокоманд заданої ДСА на операторні лінійні ланцюги.

2. Отримання з використанням розробленого евристичного алгоритму шести значень ймовірності кеш-попадань, обумовлених шістьма стратегіями вибору нерозподілених ОЛЛ, і вибір варіанту розміщення ОЛЦ з максимальним значенням ймовірності кеш-попадань.

3. Кодування ОЛЛ і адресація мікрокоманд відповідно до обраного варіанту розміщення.

4. Формування вмісту ПЗУ керуючої пам'яті.

5. Побудова прямої структурної таблиці.

6. Формування системи функцій переходів.

7. Синтез функціональної схеми пристрою в заданому елементному базисі.

Підкреслимо, що перший крок алгоритму буде різним для неелементарних і елементарних ОЛЛ.

У третьому розділі - «Моделювання композиційних мікропрограмних пристроїв керування з розділенням кодів і кеш-пам'яттю» - розроблені моделі запропонованих структур КМПК c поділом кодів і кеш-пам'яттю мікрокоманд на мові опису апаратури VHDL і мовою програмування високого рівня C ++.

Моделювання КМУУ з розділенням кодів і кеш-пам'яттю мікрокоманд переслідує такі цілі:

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

2. Експериментальне дослідження впливу модуля кеш-пам'яті на апаратурні витрати в схемі КМПК.

3. Експериментальні дослідження впливу модуля кеш-пам'яті на швидкодію схеми.

4. Експериментальні дослідження ефективності розробленого евристичного алгоритму розміщення ОЛЦ в адресному просторі керуючої пам'яті КМПК з розділенням кодів.

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

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

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

Розроблені моделі використані при проведенні експериментальних досліджень (четвертий розділ дисертаційної роботи).

У четвертому розділі - «Дослідження структур композиційних мікропрограмних пристроїв керування з розділенням кодів і кеш-пам'яттю» - проводиться дослідження розроблених структур КМПК і визначається область їх ефективного застосування. Досліджено ефективність розробленого евристичного алгоритму оптимізації розміщення ОЛЦ в адресному просторі керуючої пам'яті. Також дана оцінка апаратурним витратам, які виникають за рахунок додавання в структуру КМПК модуля кеш-пам'яті мікрокоманд.

При дослідженні ефективності розроблених структур використано такий вираз

,(4)

представляє відношення часу спрацьовування T (Si) схеми раніше відомої структури до середнього часу спрацьовування T (Sik) схеми аналогічної структури з кешуванням. З урахуванням схожості в послідовності спрацьовування вузлів в структурах S1k і S2k, результати дослідження ефективності можна вважати загальними для обох структур.

Дослідження показали, що значення ефективності для запропонованих структур в середньому лежить в діапазоні від 1.1 до 3, що відповідає приросту середнього швидкодії від 10% до 300% в залежності від характеристик використовуваного елементного базису та ймовірності кеш-попадань.

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

Дослідження ефективності евристичного алгоритму, а також запропонованих в роботі шести стратегій вибору першої ОЛЦ в блоці, для кожної із запропонованих в роботі структур проведені на прикладі тестових ДСА середньої складності (1000 операторних вершин, 100 умовних вершин). Результати досліджень дозволили зробити наступні висновки:

1. У більшості випадків евристичний алгоритм дозволяє домогтися приросту величини ймовірності кеш-попадань для заданої ДСА. Приблизно в 13% випадків для всіх стратегій алгоритму величина ph виявлялася нижче, ніж при неоптимізованими розміщенні ОЛЦ. Даний факт підкреслює евристичний характер алгоритму, що не гарантує отримання позитивного результату в 100% випадків.

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

Таблиця 1. Ефективність евристичного алгоритму (%)

Розмір кеш-пам'яті	неелементарні ОЛЦ	Елементарні ОЛЦ
	Середня	Максимальна	Середня	Максимальна
1x32	3,038844	8,165900	2,767319	6,647300
1x64	1,514025	3,373400	1,113588	2,752300
1x128	0,291094	1,922900	0,269031	1,032100

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

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

Використання в структурах КМПК з розділенням кодів модуля кеш-пам'яті призводить до збільшення витрат апаратури в схемі пристрою, що в ряді випадків може зробити його використання неприйнятним.

З цієї причини в роботі досліджені витрати апаратури в модулі кеш-пам'яті повністю асоціативного типу з алгоритмом заміщення даних Random. Дослідження проведені з використанням розробленої VHDL-моделі кеш-пам'яті для мікросхеми 5VLX50FF1153 типу FPGA серії Virtex5 фірми Xilinx. Результати виражені в еквівалентних логічних вентилях (Equivalent Gates) і в логічних таблицях пошуку (Look-Up Tables, LUTs), що сьогодні є стандартною одиницею вимірювання для більшості САПР програмованих інтегральних схем.

В роботі розглянуті залежності величини витрат апаратури від таких параметрів модуля кеш-пам'яті, як розрядність мікрокоманд (параметр R), кількість рядків (параметр N) і слів в рядку (параметр S) блоку даних. В силу регулярності структури модуля кеш-пам'яті залежно підкреслюють пропорційне зростання витрат апаратури при збільшенні параметрів модуля кеш-пам'яті. За отриманими кривим були виведені наступні аппроксимирующие аналітичні вирази:

F₁(R) = 230*R+1594; F₂(R) = 10*R + 161 [LUTs];

F₃(N) = 1330*N + 1362; F₄(N) = 73,5*N + 67,5 [LUTs];

F₅(S) = 576,2*S + 1682; F₆(S) = 25,5*S + 169,3 [LUTs].

Тут Fi - функції, що характеризують витрати апаратури. Відзначимо, що в даних експериментах для незмінних величин були використані значення R = 20, N = 4, S = 8.

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

Висновки

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

У процесі досліджень отримані наступні наукові результати:

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

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

3. Побудовано моделі розроблених структур КМПК з розділенням кодів і кеш-пам'яттю мікрокоманд, що використовують в якості засобу опису мову VHDL.

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

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

1. Николаенко Д.В. Организация композиционных микропрограммных устройств управления с разделением кодов и кэш-памятью / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Искусственный интеллект. - 2007. - №3. - С. 135-138.

2. Николаенко Д.В. Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Искусственный интеллект. - 2008. - №1. - С. 20-29.

3. Николаенко Д.В. Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Искусственный интеллект. - 2008. - №2. - С. 59-64.

4. Николаенко Д.В. Эвристический подход к адресации микрокоманд в композиционных микропрограммных устройствах управления с разделением кодов и кэш-памятью / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика і обчислювальна техніка» (ІКОТ-2008). Випуск 9 (132) - Донецьк: ДонНТУ. - 2008. - С. 188-194.

5. Николаенко Д.В. Моделирование композиционного микропрограммного устройства управления с разделением кодов и кэш-памятью / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика і обчислювальна техніка» (ІКОТ-2009). Випуск 10 (153) - Донецьк: ДонНТУ. - 2009. - С. 190-197.

6. Николаенко Д.В. Исследование эффективности эвристического алгоритма оптимизации размещения данных в композиционных микропрограммных устройствах управления с разделением кодов и кэш-памятью микрокоманд / Николаенко Д.В. // Радіоелектронні і комп'ютерні системи. Випуск 5 (46) - Харків: «ХАІ». - 2010. - С. 116-119.

7. Николаенко Д.В. Оптимизация композиционных микропрограммных устройств управления с разделением кодов / Николаенко Д.В. // Матеріали доповідей II Міжнародної науково-практичної конференції молодих учених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія», 13-14 мая 2008 г., Донецк, 2008. Т.1. - С. 262-268.

8. Николаенко Д.В. Моделирование композиционных микропрограммных устройств управления с разделением кодов и кэш-памятью / Бабаков Р.М., Николаенко Д.В. // Матеріали доповідей III Міжнародної науково-практичної конференції молодих учених, аспірантів, студентів «Сучасна інформаційна Україна: інформатика, економіка, філософія», 14-15 мая 2009 року, Донецк, 2009. Т. 1. - С. 14-17.

9. Николаенко Д.В. Повышение эффективности использования кэш-памяти в композиционных микропрограммных устройствах управления с разделением кодов / Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. // Материалы десятого международного научно-практического семинара «Практика и перспективы развития партнерства в сфере высшей школы», 4-7 мая 2009 года, г. Донецк. В 2-х томах. Т. 1. - Донецк, ДонНТУ. - С. 190-193.

Анотація

Ніколаєнко Денис Володимирович. Розробка й дослідження методів синтезу швидкодіючих мікропрограмних пристроїв керування. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за фахом 05.13.05 - комп'ютерні системи та компоненти. - ДВНЗ «Донецький національний технічний університет», Донецьк, 2010.

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

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

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

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

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

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

Ключові слова: композиційний мікропрограмний пристрій керування з поділом кодів, кеш-пам'ять, операторні лінійні ланцюги, евристичний алгоритм оптимізації швидкодії, імовірність кеш-влучень.

Аннотация

Николаенко Денис Владимирович. Разработка и исследование методов синтеза быстродействующих микропрограммных устройств управления. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - ГВУЗ «Донецкий национальный технический университет», Донецк, 2010.

На основе теоретических и экспериментальных исследований в работе предложены новые структуры композиционных микропрограммных устройств управления с разделением кодов. Показано, что для оптимизации быстродействия в схемах устройств управления может быть использован метод кэширования сигналов. Метод применяется для снижения среднего времени доступа к блокам структур устройств управления, реализованным в базисе ПЗУ или ППЗУ. В качестве такого блока в исследуемых структурах выступает управляющая память, хранящая множество микрокоманд реализуемого алгоритма управления.

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

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

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

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

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

Также выполнено исследование эвристического алгоритма оптимизации размещения операторных линейных цепей. Исследование показало, что повышение величины вероятности кэш-попаданий за счет оптимизации размещения операторных линейных цепей может достигать 8% и выше, что при вероятности кэш-попаданий, близкой к единице, дает значительный прирост среднего быстродействия схемы устройства управления.

С помощью разработанной VHDL-модели модуля кэш-памяти получены аналитические зависимости аппаратурных затрат в модуле кэш-памяти от параметров модуля. Данные зависимости могут быть использованы проектировщиками аппаратуры для оценки возможностей использования разработанных структур с кэш-памятью при проектировании вычислительных систем на их базе.

Ключевые слова: композиционное микропрограммное устройство управления с разделением кодов, кэш-память, операторные линейные цепи, эвристический алгоритм оптимизации быстродействия, вероятность кэш-попаданий.

Abstract

Nikolaenko Denis Vladimirovich. Development and research of methods of synthesis of high-speed microprogram control units. - Manuscript.

The dissertation on competition of a scientific degree of Candidate of Technical sciences on a speciality 05.13.05 - computer systems and components. - State high education institution «Donetsk National Technical University», Donetsk, 2008.

On the basis of theoretical and experimental researches in dissertation new structures of compositional microprogram control units with codes division are offered. It is shown, that for speed optimization in circuits of control units the method of signals caching can be used. The method is applied to decreasing of average access time to the control memory storing set of microinstructions of realized control algorithm appears.

Application of a method of caching of signals has allowed to develop new structures of compositional microprogram control units with codes division and cache memory of microinstructions, possessing higher speed in comparison with earlier known structures-prototypes. Analytical expressions for definition of efficiency of the developed structures are received at usage of average speed of the circuit as criterion of optimization.

The method of increasing of efficiency of developed structures of compositional microprogram control units with codes division is offered, allowing to increase value of probability of caches-hits for the realized control algorithm with chosen parameters of cache memory unit. The offered method is realized in the form of heuristic algorithm of optimization of allocation of operator linear chains in control memory address space.

The program models using as simulars the hardware description language VHDL are developed for the offered structures of compositional microprogram control units with codes division and cache memory of microinstructions. Also program implementation of heuristic algorithm of optimization of allocation of operator linear chains builded in programming language C ++ is fulfilled.

Research of the developed structures for the purpose of definition of area of their effective application is carried out. The structures of compositional microprogram control units offered in operation with codes division and cache memory of microinstructions appear from the point of view of speed to 3 times more effectively the structures-prototypes without cache memory.

Also research of heuristic algorithm of optimization of allocation of operator linear chains is fulfilled. Research has shown, that rise of the value of probability of caches-hits at the expense of optimization of allocation of operator linear chains can reach 8% and above, that at the probability of caches-hits close to one, gives considerable increase of average speed of the circuit of the control unit.

Keywords: compositional microprogram control unit with codes division, cache memory, operator linear chains, heuristic algorithm of optimization of speed, probability of caches-hits.

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

...