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

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

БАБАКОВ РОМАН МАРКОВИЧ

УДК 681.324

Розробка і дослідження методів синтезу

швидкодіючих пристроїв керування на ВІС

Спеціальність 05.13.13 – Обчислювальні машини, системи та мережі

АВТОРЕФЕРАТ

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

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

Донецьк – 2003

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

Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України.

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

Офіційні опоненти: д.т.н., проф. Скобцов Юрій Олександрович,   завідувач кафедри “Автоматизовані системи управління” Донецького національного технічного університету.

       к.т.н., доц. Вороний Сергій Михайлович,    завідувач кафедри “Технічна інформатика” Донецького державного інституту штучного інтелекту.

Провідна установа:  Інститут кібернетики ім. В.М. Глушкова НАН України, відділ 205, м. Київ.

Захист відбудеться “20” березня 2003 р. о 14 годині на засіданні спеціалізованої вченої ради К 11.052.03 Донецького національного технічного університету (адреса: 83000, м. Донецьк, вул. Артема, 58, I уч. корп., ауд. 201)

З дисертацією можна ознайомитись у бібліотеці ДонНТУ (адреса: 83000,   м. Донецьк, вул. Артема, 58, I уч. корп.)

Автореферат розісланий                        “18”  лютого  2003 р.

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

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

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

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

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

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

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

       Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана протягом 1999 – 2002 р.р. відповідно до наукового напрямку кафедри “Електронні обчислювальні машини” Донецького національного технічного університету.

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

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

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

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

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

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

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

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

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

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

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

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

       Апробація. Основні результати роботи доповідалися й обговорювалися на Міжнародній науково-технічній конференції “Інформаційна техніка та електромеханіка на порозі XXI-го століття” (м. Луганськ, квітень 2001 р.), на Четвертій міжнародній конференції “Computer-Aided Design of Discrete Devices” (м. Мінськ, Бєларусь, листопад 2001 р.), на науково-технічних семінарах кафедри ЕОМ Донецького національного технічного університету (2001, 2002 р.р.)

       Публікації. Основні положення і результати досліджень опубліковані в 5 друкованих працях. З них: 3 – в збірниках наукових праць, 2 – в журналах. Усі роботи опубліковані у виданнях, рекомендованих ВАК України.

       Структура й обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох розділів основної частини, висновку, викладених на 149 сторінках машинописного тексту; містить 63 рисунка, 17 таблиць, список використаних літературних джерел з 138 найменувань, один додаток на 9 сторінках.

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

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

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

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

       У КМПК комбінаційна схема КС і регістр пам'яті РП являють собою автомат з “жорсткою” логікою S1, призначений для адресації мікрокоманд при порушенні природного порядку їхнього виконання. Керуюча пам'ять КП, призначена для збереження мікропрограми, лічильник адреси мікрокоманд СЧАМК та схема формування мікрооперацій СФМО, призначена для декодування мікрокоманд, являють собою автомат S2 з “програмувальною” логікою і природною адресацією мікрокоманд.

       В основі структури КМПК лежить формування безлічі операторних лінійних ланцюгів (ОЛЛ) інтерпретуємої граф-схеми алгоритму (ГСА) Г(B, E), де B – безліч вершин, E – безліч дуг. Операторним лінійним ланцюгом називається кінцева послідовність операторних вершин , така, що , де i∈{1, ..., Fg-1}. Кожен ОЛЛ має як мінімум один вхід і точно один вихід. ОЛЛ, що має тільки один вхід, називається простим ОЛЛ.

       Перехід у межах будь-якого ОЛЛ відбувається під дією керуючого сигналу   y0 # СЧАМК:=СЧАМК+1. Перехід автомата S1 можливий тільки при y0=0, у цьому випадку в РП записується код Ф2. Якщо y0=0, то в СЧАМК заноситься адреса наступної МК, сформована схемою КС (Ф1).

       КМПК функціонує таким чином. Нехай автомат S1 перейшов у стан am∈A, де    A – безліч станів автомата S1, і заніс у СЧАМК адресу початкової вершини Ig ОЛЛ αg. Якщо ця адреса не збігається з адресою виходу Og, то автомат S2 одночасно з набором мікрооперацій Yt­ ⊆Y, де Y={y1, ..., y} – безліч мікрооперацій,  формує сигнал y0. По цьому сигналу до вмісту СЧАМК додається одиниця й адресується чергова МК. Автомат S1 залишається в стані am. Якщо в СЧАМК записана адреса вершини, останньої в ОЛЛ αg, то сигнал y0 не формується. У наступному такті автомат S1 переходить зі стану am, під дією логічних умов з безлічі X={x1, ..., x}, у стан as, заносячи в СЧАМК адресу входу наступного ОЛЛ. Процес продовжується до переходу автомата S1 у кінцевий стан.

       Алгоритм синтезу КМПК включає наступні основні етапи:

1. Формування безлічі ОЛЛ вихідної ГСА.
2. Адресація мікрокоманд.
3. Формування вмісту КП.
4. Завдання закону функціонування автомата S1­ .
5. Синтез схем автоматів у заданому елементному базисі.

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

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

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

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

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

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

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

       У дисертаційній роботі вирішуються наступні основні задачі:

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

       Як елементний базис для синтезу вузлів КМПК і кеш-контролера використовуються програмувальні ВІС типу ПЛМ, ПЛІС, ПЗП.

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

       Розташування кеш-пам'яті в структурі КМПК показане на рис. 2. Тут К – кеш-контролер, призначений для керування процесом вибору мікрокоманди з пам'яті; КЕШ – модуль кеш-пам'яті, час доступу до якого значно менше, ніж до керуючої пам’яті. Кеш-контролер, крім керування КП і КЕШ, також керує синхронізацією СЧАМК і РП. Якщо шукане слово знайдене в кеші (має місце кеш-влучення), то кеш-контролер дозволяє проходження імпульсу синхронізації СЧАМК (при цьому тривалість синхроімпульсу достатня для читання даних зі швидкої кеш-пам'яті). Якщо ж шукана МК не знайдена в кеш-пам'яті, то виконується “довгий” цикл читання даних з КП; при цьому синхронізація СЧАМК і РП не подається доти, поки цикл читання з КП не буде довершений. Це може зайняти кілька тактів синхронізації (у залежності від тривалості спрацьовування схеми КП).

       У КМПК керуюча пам'ять містить тільки операційні мікрокоманди. Нехай розрядність адреси R=]log2M[, де M – число операторних вершин у ГСА. Нехай також число розрядів у мікрокоманді дорівнює RY. Таким чином, КП може містити до 2R слів (під словом розуміється мікрокоманда розрядності RY).

       КП представляється як набір послідовно розташованих блоків по S слів у кожнім. Кількість таких блоків дорівнює ]2R/S[. Кількість слів у кожному блоці кратна ступені двійки. Тоді кеш-пам'ять представляється як деяка безліч рядків, кожен з яких має довжину одного блоку КП.

       У кожнім з N рядків може бути розміщений блок з S слів. Число рядків N багато менше кількості блоків в КП:  N << 2R/S. У будь-який момент часу в кеш-пам'яті міститься деяка підмножина блоків з керуючої пам'яті. Якщо СЧАМК формує адресу деякого слова в КП, то в рядок кеш-пам'яті передається весь блок, у якому знаходиться необхідне слово. Для ідентифікації блоку, що зберігається в рядку кеш-пам'яті, служить тег – частина старших розрядів повної адреси КП.

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

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

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