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

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

Донецький національний технічний університет

Автореферат

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

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

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

Бабаков Роман Маркович

Донецьк - 2003

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

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

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

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

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

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

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

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

Анотація

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

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 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.

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

мікропрограмний пристрій керуючий пам'ять

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Основний зміст

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

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

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

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

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

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

Рис. 1. Структурна схема композиційного мікропрограмного пристрою керування

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

КМПК функціонує таким чином. Нехай автомат S₁ перейшов у стан a_mA, де A - безліч станів автомата S₁, і заніс у СЧАМК адресу початкової вершини I_g ОЛЛ _g. Якщо ця адреса не збігається з адресою виходу O_g, то автомат S₂ одночасно з набором мікрооперацій Y_t Y, де Y={y₁, ..., y} - безліч мікрооперацій, формує сигнал y₀. По цьому сигналу до вмісту СЧАМК додається одиниця й адресується чергова МК. Автомат S₁ залишається в стані a_m. Якщо в СЧАМК записана адреса вершини, останньої в ОЛЛ _g, то сигнал y₀ не формується. У наступному такті автомат S₁ переходить зі стану a_m, під дією логічних умов з безлічі X={x₁, ..., x}, у стан a_s, заносячи в СЧАМК адресу входу наступного ОЛЛ. Процес продовжується до переходу автомата S₁ у кінцевий стан.

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

Формування безлічі ОЛЛ вихідної ГСА.

Адресація мікрокоманд.

Формування вмісту КП.

Завдання закону функціонування автомата S₁.

Синтез схем автоматів у заданому елементному базисі.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2. Структурна схема КМПК з кеш-пам'яттю

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

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

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

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

Блок перевірки кеш-влучень (БПКВ): на основі тега поточної мікрокоманди, регістрів тегів і бітів вірогідності блок перевіряє, відбулося в поточному такті кеш-влучення чи кеш-промах.

Блок керування КПМК (БК КПМК): блок керує читанням і записом даних у кеш-пам'ять мікрокоманд КПМК.

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

Блок регістрів тегів (БРТ): блок містить теги блоків мікрокоманд, що зберігаються в даний момент у кеш-пам'яті.

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

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

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

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

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

Блок перевірки кеш-влучень (БПКВ): на основі тега поточної мікрокоманди, регістрів тегів і бітів вірогідності перевіряє, що саме відбулося: кеш-влучення чи кеш-промах.

Блок керування КПМК (БК КПМК): керує читанням і записом даних у кеш-пам'ять мікрокоманд КПМК.

Блок вибору рядка, що заміщається, (БВЗР): вибирає рядок, що заміщається у випадку кеш-промаха новим блоком даних з КП відповідно до алгоритму заміщення LRU.

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

Блок регістрів тегів (БРТ): містить теги блоків мікрокоманд, що зберігаються в даний момент у кеш-пам'яті.

Блок регістрів тактів звертання (БРТЗ): для кожного рядка кеш-пам'яті містить порядковий номер такту, у якому вироблялося останнє звертання до мікрокоманди з цього рядка.

Лічильник тактів (ЛТ): збільшується на одиницю в кожнім такті роботи КМПК і таким чином зберігає порядковий номер такту роботи пристрою.

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

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

Рис. 4. Структурна схема підсистеми кеш-пам'яті цілком асоціативного типу

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

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

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

, (1)

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

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

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

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

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

Формування і рішення системи рівнянь, що відбивають переходи в кожну мікрокоманду ГСА, з метою визначення імовірностей виконання кожної мікрокоманди ГСА.

Формування безлічі V мікрокоманд, для яких можливий кеш-промах.

Формування для кожного рядка кеш-пам'яті підграфа ГСА, що відбиває переходи між мікрокомандами з безлічі V, блоки яких відносяться до даного рядка.

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

Визначення імовірності кеш-влучень для розглянутого алгоритму як суми імовірностей кеш-влучень для кожної мікрокоманди ГСА.

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

Визначення імовірностей виконання кожної мікрокоманди ГСА.

Розбивка безлічі мікрокоманд на блоки відповідно до розміру рядка кеш-пам'яті.

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

Перетворення ГСА в граф блоків мікрокоманд.

Формування дерев кеш-влучень і визначення імовірностей кеш-влучень для всіх МК, для яких можливі кеш-промахи.

Визначення сумарної імовірності кеш-влучень алгоритму.

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

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

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

, (2)

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

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

Залежність E(t_КП) має нелінійно зростаючий характер, причому при t_КП значення E прагне до величини t_КП/(t_КП - 0.9t_КП) = 10.

Залежність E(t_c) майже лінейна й спадає зі збільшенням t_c. При t_c значення E прагне до нуля.

Залежність E(t_a) нелінійно спадає зі збільшенням t_a. При t_a значення E прагне до одиниці.

Залежність E(P_h) нелінійно зростає зі збільшенням P_h. При P_h 100% величина E (t_УП+t_a)/(t_c+t_a)=4.8.

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

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

N\S	2	4	8	16	32	64	128	256
2	48,7	73,1	86,0	92,7	95,5	97,3	98,7	99,2
4	49,3	76,2	88,7	94,0	96,3	98,0	99,1
8	57,6	80,2	90,0	94,3	97,4	98,8
16	61,7	81,6	90,8	96,3	98,5
32	64,0	83,3	94,2	97,7
64	67,3	89,6	96,5
128	79,9	93,6
256	87,5

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

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

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

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

Рис. 5. Залежність Ph(S) (1) и E(S) (2) для кеш-пам'яті з прямим відображенням при N=2

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

N\S	2	4	8	16	32	64	128	256
2	248 0,5	246 0,4	249 0,4	248 0,3	253 0,3	270 0,3	262 0,3	263 0,3
4	251 1,0	253 0,8	254 0,7	246 0,7	254 0,7	269 0,7	254 0,7
8	238 2,6	237 2,2	241 2,0	238 1,9	252 1,7	246 1,6
16	237 9,1	231 7,9	222 6,6	225 5,1	224 4,1
32	230 46,2	228 33,4	215 21,6	216 13,2
64	230 223	216 120	213 59
128	218 821	210 336
256	186 2029

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

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

Таблиця 3. Витрати часу на експериментальне та аналітичне визначення імовірності кеш-влучень для кеш-пам'яті цілком асоціативного типу

N\S	2	4	8	16	32	64	128	256
2	318 0,3	316 0,3	302 0,2	315 0,2	342 0,2	320 0,2	326 0,2	359 0,2
3	329 0,4	321 0,3	309 0,2	339 0,2	315 0,2	335 0,2	324 0,2
4	329 0,4	339 0,3	317 0,3	326 0,3	319 0,3	345 0,3	300 0,3
5	360 0,5	350 0,3	369 0,3	324 0,3	326 0,3	335 0,3
8	377 0,8	361 0,6	362 0,5	353 0,4	358 0,5	353 0,7
10	394 1,0	352 0,7	368 0,6	378 0,6	344 0,8
14	454 1,5	385 1,1	400 1,0	363 1,2	371 1,8
16	476 1,8	413 1,3	407 1,2	421 1,6	357 2,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.

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