Библиотечный каталог авторефератов Украины

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

       Структура (рис.3) реалізує алгоритм заміщення даних, при якому у випадку кеш-промаха заміщається той рядок, номер якого збігається з розрядами поля рядка в адресі запитуваної мікрокоманди.

       На рис. 4 показана структурна схема підсистеми кеш-пам'яті цілком асоціативного типу. Схема включає наступні блоки.

• Блок перевірки кеш-влучень (БПКВ): на основі тега поточної мікрокоманди, регістрів тегів і бітів вірогідності перевіряє, що саме відбулося: кеш-влучення чи кеш-промах.
• Блок керування КПМК (БК КПМК): керує читанням і записом даних у кеш-пам'ять мікрокоманд КПМК.
• Блок вибору рядка, що заміщається, (БВЗР): вибирає рядок, що заміщається у випадку кеш-промаха новим блоком даних з КП відповідно до алгоритму заміщення LRU.
• Блок керування синхронізацією КМПК (БКС): в залежності від того, відбулося кеш-влучення чи кеш-промах, задає відповідно “короткий” чи “довгий” такти синхронізації КМПК. На роботу схеми БКС також впливає значення сигналу y0, що дозволяє роботу автомата з програмувальною логікою: так, якщо виконується умовний перехід з використанням автомата з “жорсткою” логікою, то кеш-контролер не може керувати синхронізацією КМПК.
• Блок регістрів тегів (БРТ): містить теги блоків мікрокоманд, що зберігаються в даний момент у кеш-пам'яті.
• Блок регістрів тактів звертання (БРТЗ): для кожного рядка кеш-пам'яті містить порядковий номер такту, у якому вироблялося останнє звертання до мікрокоманди з цього рядка.
• Лічильник тактів (ЛТ): збільшується на одиницю в кожнім такті роботи КМПК і таким чином зберігає порядковий номер такту роботи пристрою.

       У контролері кеш-пам'яті цілком асоціативного типу реалізований алгоритм заміщення даних LRU (“що найбільше давно використовувався”), при якому у випадку кеш-промаха заміщається той блок даних, звертання до мікрокоманд якого відбувалося раніш, ніж до мікрокоманд інших блоків, що знаходяться в даний момент у кеш-пам'яті.

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

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

       Ефективність використання кеш-пам'яті в КМПК визначається по формулі

                                    ,                        (1)

де tКП – час доступу до керуючого пам'яті в системі без кеш-пам'яті; tЕ – середній час доступу в системі з кеш-пам'яттю; Ph – імовірність кеш-влучень алгоритму керування, що реалізується; tc – час доступу до даних у випадку кеш-влучення; tm – час доступу до даних у випадку кеш-промаха.

       У формулі (1) величини tКП, tc, tm залежать тільки від елементної бази, що використовується, і у деякій мірі можуть вважатися відомими. Величина Ph залежить від алгоритму керування, що реалізується, і від характеристик кеш-пам'яті (кількості рядків, кількості слів у рядку і типу архітектури). В залежності від цих параметрів ця величина може змінюватися від 0 до 1 і не є очевидною зі структури ГСА.

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

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

       Методика аналітичного визначення імовірності кеш-влучень по ГСА для кеш-пам'яті з прямим відображенням складається з наступних основних етапів:

1. Формування і рішення системи рівнянь, що відбивають переходи в кожну мікрокоманду ГСА, з метою визначення імовірностей виконання кожної мікрокоманди ГСА.
2. Формування безлічі V мікрокоманд, для яких можливий кеш-промах.
3. Формування для кожного рядка кеш-пам'яті підграфа ГСА, що відбиває переходи між мікрокомандами з безлічі V, блоки яких відносяться до даного рядка.
4. Визначення по побудованим підграфам імовірності виникнення ситуації кеш-влучення для кожної мікрокоманди кожного підграфа. Можливість виникнення ситуацій кеш-влучень чи кеш-промахів визначається відповідно до алгоритму заміщення даних для кеш-пам'яті з прямим відображенням.
5. Визначення імовірності кеш-влучень для розглянутого алгоритму як суми імовірностей кеш-влучень для кожної мікрокоманди ГСА.

       Методика аналітичного визначення імовірності кеш-влучень по ГСА для кеш-пам'яті цілком асоціативного типу складається з наступних основних етапів:

1. Визначення імовірностей виконання кожної мікрокоманди ГСА.
2. Розбивка безлічі мікрокоманд на блоки відповідно до розміру рядка кеш-пам'яті.
3. Визначення безлічі мікрокоманд, для яких можлива ситуація кеш-промаха, відповідно до алгоритму заміщення даних LRU.
4. Перетворення ГСА в граф блоків мікрокоманд.
5. Формування дерев кеш-влучень і визначення імовірностей кеш-влучень для всіх МК, для яких можливі кеш-промахи.
6. Визначення сумарної імовірності кеш-влучень алгоритму.

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

       У четвертому розділі приводяться результати експериментальних досліджень розроблених структур і методів оцінки ефективності КМПК з кеш-пам’яттю мікрокоманд. Експерименти були проведені на прикладі абстрактного алгоритму керування, що включає 1000 мікрокоманд, 33 ОЛЛ, 10 логічних умов і 26 умовних вершин.

       Уточнена формула визначення ефективності використання кеш-пам'яті в КМПК має наступний вигляд:

                               ,                                (2)

де ta – час спрацьовування схем, асинхронних щодо сигналу синхронізації КМПК. До таких схем відносяться, наприклад, операційний автомат, схеми КС і СФМО.

       По формулі (2) отримані аналітичні залежності ефективності від кожного з параметрів формули (2) при заданих інших параметрах (tКП=200 нс, tc=10 нс, ta=40 нс, Ph=0.9). При цьому зроблені наступні висновки:

1. Залежність E(tКП) має нелінійно зростаючий характер, причому при tКП→∞ значення E прагне до величини tКП/(tКП – 0.9tКП) = 10.
2. Залежність E(tc) майже лінейна й спадає зі збільшенням tc. При tc→∞ значення E прагне до нуля.
3. Залежність E(ta) нелінійно спадає зі збільшенням ta. При ta→∞ значення E прагне до одиниці.
4. Залежність E(Ph) нелінійно зростає зі збільшенням Ph. При  Ph → 100% величина E → (tУП+ta)/(tc+ta)=4.8.

       У роботі отримані залежності імовірності кеш-влучень від розмірів кеш-пам'яті. У таблиці 1 приведені значення Ph для кеш-пам'яті з прямим відображенням у залежності від кількості рядків і слів у рядку кеш-пам'яті.

Таблиця 1

Залежність імовірності кеш-влучень від розмірів кеш-пам’яті

для кеш-пам’яті з прямим відображенням

       Криві залежностей E(S) при заданій кількості рядків мають нелінійно зростаючий характер. На рис. 5 показані залежності імовірності кеш-влучень Ph (1) і ефективності E (2) від числа слів у рядку кеш-пам’яті з прямим відображенням при числі рядків, рівному двом.

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

       У таблицях 2 і 3 показані витрати часу на експериментальне й аналітичне визначення імовірності кеш-влучень для випадків кеш-пам’яті з прямим відображенням і кеш-пам’яті цілком асоціативного типу відповідно. При цьому у верхній частині осередку зазначена кількість секунд, витрачена на експериментальне визначення імовірності, а в нижній частині – на аналітичне.

Таблиця 2

Витрати часу на експериментальне та аналітичне визначення імовірності

кеш-влучень для кеш-пам’яті з прямим відображенням

       Усі тимчасові значення отримані на комп'ютері з процесором iP-III 733 МГц під керуванням операційної системи Windows 98 у віконному режимі при відсутності інших програм, що виконуються.

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

Таблиця 3

Витрати часу на експериментальне та аналітичне визначення імовірності

кеш-влучень для кеш-пам’яті цілком асоціативного типу

ВИСНОВКИ

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

1. Виконано аналіз: сучасних архітектур кеш-пам'яті і їхніх особливостей; сучасного елементного базису, використовуваного при синтезі схем пристроїв керування; методів оптимізації композиційних мікропрограмних пристроїв керування на програмувальних ВІС.
2. Розроблено структури і методи синтезу функціональних схем композиційних мікропрограмних пристроїв керування з кеш-пам'яттю з прямим відображенням і кеш-пам'яттю цілком асоціативного типу.
3. Розроблено методики аналітичного визначення імовірності кеш-влучень для заданої граф-схеми алгоритму керування і характеристик кеш-пам'яті.
4. Отримано аналітичні оцінки збільшення швидкодії при використанні кеш-пам'яті в композиційних мікропрограмних пристроях керування.
5. Розроблено методику вибору оптимальних характеристик кеш-пам'яті, що дозволяє для заданої граф-схеми підібрати кількість рядків і розмір рядка кеш-пам'яті, при яких забезпечуються максимально можлива імовірність кеш-влучень і збільшення швидкодії.

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

       1. Баркалов А.А., Зеленева И.Я., Бабаков Р.М. Структуры логических схем управляющих автоматов на программируемых БИС. / Зб. наукових праць ДДТУ. Серія “Інформатика, кібернетика та обчислювальна техніка”. Вип. 6. – Донецьк: ДонДТУ, 1999. – С. 208-211.

       2. Бабаков Р.М., Самир Нахлави, Зайцев В.В. Синтез двухуровневой схемы автомата Мура на счетчике. / Зб. наукових праць ДДТУ. Серія “Проблеми моделювання та автоматизації проектування динамічних систем”. Вип. 10. – Донецьк, ДонДТУ, 1999. – С. 301-305.

       3. Ковалев С.А., Бабаков Р.М. Баркалов А.А. Применение принципов кэширования в композиционных микропрограммных устройствах управления.  // Зб. наукових праць ДДТУ. Серія “Інформатика, кібернетика та обчислювальна техніка”. Вип. 15. – Донецьк, ДонДТУ, 2000. – С. 118-123.

       4. Баркалов А.А., Ковалев С.А., Бабаков Р.М. Применение принципов кэширования в композиционных микропрограммных устройствах управления. // Управляющие системы и машины. – 2001. – № 5. – С. 26-33.

       5. Баркалов А.А., Ковалев С.А., Бабаков Р.М. Определение вероятности кэш-попаданий в композиционных микропрограммных устройствах управления по граф-схеме алгоритма. // Автоматика и вычислительная техника. – 2001. –№ 4. – С. 44-52.

       Особистий внесок здобувача в публікаціях: [1] – аналіз багаторівневих структур керуючих автоматів і визначення їх недоліків; [2] – аналіз і приклад використання метода синтезу автомата Мура з лічильником для граф-схеми алгоритму, розділеної на лінійні послідовності станів; [3] – загальний метод збільшення швидкодії КМПК за рахунок використання в його структурі кеш-пам'яті мікрокоманд; [4] – структура КМПК з кеш-пам'яттю з прямим відображенням і визначення основних вимог для її ефективного використання; [5] – методика аналітичного визначення імовірності кеш-влучень по граф-схемі алгоритму для КМПК з кеш-пам'яттю з прямим відображенням.

Анотація

       Бабаков Р.М. Розробка і дослідження методів синтезу швидкодіючих пристроїв керування на ВІС. – Рукопис.

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

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

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

АННОТАЦИЯ

       Бабаков Р.М. Разработка и исследование методов синтеза быстродействующих устройств управления на БИС. – Рукопись.

       Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.13 – вычислительные машины, системы и сети. – Донецкий национальный технический университет, Донецк, 2003.

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

       Эффективность использования кэш-памяти в композиционных микропрограммных устройствах управления зависит от вероятности кэш-попаданий, значение которой определяется как структурой реализуемого алгоритма управления, так и характеристиками кэш-памяти (типом архитектуры, количеством строк и слов в строке). Жесткая привязка структуры композиционного микропрограммного устройства управления к реализуемому алгоритму позволяет подобрать такие характеристики кэш-памяти, при которых значение вероятности кэш-попаданий для заданного алгоритма оказывается максимальным.

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

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

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

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

       В диссертационной работе решены следующие основные задачи:

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

       2. Разработаны методы аналитического определения значения вероятности кэш-попаданий для заданного алгоритма управления и характеристик кэш-памяти.

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

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

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

ABSTRACT

Babakov R.M. Development and research of methods of synthesis of high-speed control units on LSI. – Manuscript.

        The Dissertation on competition of a scientific degree of the candidate of  technical sciences on a speciality 05.13.13 – computers, systems and networks. – Donetsk national technical university, Donetsk, 2003.

        On the basis of theoretical and experimental researches new structures and formal methods of synthesis of compositional microprogram control units with direct-mapped and fully-associative cache-memory are offered. It is shown, that for optimization of performance of the circuit of the compositional microprogram control unit there may be used cache-memory intended for temporary storage of microinstructions, using during several last steps of operation of the unit that allows to increase average performance of the circuit in 2-5 times in comparison with earlier known structures. On the basis of the developed structures of compositional microprogram control units with direct-mapped and fully-associative cache-memory the methods of analytical estimation of exact value of probability of cache-hits for the given flow-chart of algorithm of control and characteristics of cache-memory where developed. These methods are used at a choosing of optimum characteristics of cache-memory for given algorithm. The carried out researches have allowed to determine area of an effective using of the offered structures of compositional microprogram control units with cache-memory of microinstructions at their implementation in basis of LSI.

        Key words: the compositional microprogram control unit, cache-memory, probability of cache-hit, the microinstructions, programmable LSI.