Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием
Разработан метод синтеза базовой структуры композиционного микропрограммного устройства управления с разделением кодов и кэшированием микрокоманд. В основе метода лежит эвристическое распределение операторных линейных цепей в адресном пространстве управляющей памяти, обеспечивающее максимальное д...
Gespeichert in:
| Datum: | 2008 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6711 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием / А.А. Баркалов, С.А. Ковалев, Р.М. Бабаков, Д.В. Николаенко // Штучний інтелект. — 2008. — № 2. — С. 59-64. — Бібліогр.: 3 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-6711 |
|---|---|
| record_format |
dspace |
| spelling |
Баркалов, А.А. Ковалев, С.А. Бабаков, Р.М. Николаенко, Д.В. 2010-03-15T13:41:09Z 2010-03-15T13:41:09Z 2008 Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием / А.А. Баркалов, С.А. Ковалев, Р.М. Бабаков, Д.В. Николаенко // Штучний інтелект. — 2008. — № 2. — С. 59-64. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6711 681.324 Разработан метод синтеза базовой структуры композиционного микропрограммного устройства управления с разделением кодов и кэшированием микрокоманд. В основе метода лежит эвристическое распределение операторных линейных цепей в адресном пространстве управляющей памяти, обеспечивающее максимальное для реализуемого алгоритма управления значение вероятности кэш-попаданий. Приведен пример использования разработанного метода синтеза. Розроблено метод синтезу базової структури композиційного мікропрограмного пристрою керування з розподілом кодів і кешуванням мікрокоманд. В основі методу лежить евристичний розподіл операторних лінійних ланцюгів в адресному просторі керуючої пам'яті, що забезпечує максимальне для реалізованого алгоритму керування значення ймовірності кеш-влучень. Наведено приклад використання розробленого методу синтезу. The method of synthesis of base structure of the compositional microprogram control unit with division of codes and caching of microinstructions is developed. It is based on heuristic distribution of operational linear circuits in address space of the managing memory, providing maximal for realized control algorithm value of probability of cache-hits. The example of using of the developed method of synthesis is resulted. ru Інститут проблем штучного інтелекту МОН України та НАН України Системы и методы искусственного интеллекта Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием Метод синтезу композиційного мікропрограмного пристрою керування з розподілом кодів і кешуванням The method of Synthesis of Compositional Microprogram Control Unit with Division of Codes and Caching Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| spellingShingle |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием Баркалов, А.А. Ковалев, С.А. Бабаков, Р.М. Николаенко, Д.В. Системы и методы искусственного интеллекта |
| title_short |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| title_full |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| title_fullStr |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| title_full_unstemmed |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| title_sort |
метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием |
| author |
Баркалов, А.А. Ковалев, С.А. Бабаков, Р.М. Николаенко, Д.В. |
| author_facet |
Баркалов, А.А. Ковалев, С.А. Бабаков, Р.М. Николаенко, Д.В. |
| topic |
Системы и методы искусственного интеллекта |
| topic_facet |
Системы и методы искусственного интеллекта |
| publishDate |
2008 |
| language |
Russian |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Метод синтезу композиційного мікропрограмного пристрою керування з розподілом кодів і кешуванням The method of Synthesis of Compositional Microprogram Control Unit with Division of Codes and Caching |
| description |
Разработан метод синтеза базовой структуры композиционного микропрограммного устройства
управления с разделением кодов и кэшированием микрокоманд. В основе метода лежит
эвристическое распределение операторных линейных цепей в адресном пространстве управляющей
памяти, обеспечивающее максимальное для реализуемого алгоритма управления значение
вероятности кэш-попаданий. Приведен пример использования разработанного метода синтеза.
Розроблено метод синтезу базової структури композиційного мікропрограмного пристрою керування
з розподілом кодів і кешуванням мікрокоманд. В основі методу лежить евристичний розподіл
операторних лінійних ланцюгів в адресному просторі керуючої пам'яті, що забезпечує максимальне
для реалізованого алгоритму керування значення ймовірності кеш-влучень. Наведено приклад
використання розробленого методу синтезу.
The method of synthesis of base structure of the compositional microprogram control unit with division of
codes and caching of microinstructions is developed. It is based on heuristic distribution of operational linear
circuits in address space of the managing memory, providing maximal for realized control algorithm value of
probability of cache-hits. The example of using of the developed method of synthesis is resulted.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/6711 |
| citation_txt |
Метод синтеза композиционного микропрограммного устройства управления с разделением кодов и кэшированием / А.А. Баркалов, С.А. Ковалев, Р.М. Бабаков, Д.В. Николаенко // Штучний інтелект. — 2008. — № 2. — С. 59-64. — Бібліогр.: 3 назв. — рос. |
| work_keys_str_mv |
AT barkalovaa metodsintezakompozicionnogomikroprogrammnogoustroistvaupravleniâsrazdeleniemkodovikéširovaniem AT kovalevsa metodsintezakompozicionnogomikroprogrammnogoustroistvaupravleniâsrazdeleniemkodovikéširovaniem AT babakovrm metodsintezakompozicionnogomikroprogrammnogoustroistvaupravleniâsrazdeleniemkodovikéširovaniem AT nikolaenkodv metodsintezakompozicionnogomikroprogrammnogoustroistvaupravleniâsrazdeleniemkodovikéširovaniem AT barkalovaa metodsintezukompozicíinogomíkroprogramnogopristroûkeruvannâzrozpodílomkodívíkešuvannâm AT kovalevsa metodsintezukompozicíinogomíkroprogramnogopristroûkeruvannâzrozpodílomkodívíkešuvannâm AT babakovrm metodsintezukompozicíinogomíkroprogramnogopristroûkeruvannâzrozpodílomkodívíkešuvannâm AT nikolaenkodv metodsintezukompozicíinogomíkroprogramnogopristroûkeruvannâzrozpodílomkodívíkešuvannâm AT barkalovaa themethodofsynthesisofcompositionalmicroprogramcontrolunitwithdivisionofcodesandcaching AT kovalevsa themethodofsynthesisofcompositionalmicroprogramcontrolunitwithdivisionofcodesandcaching AT babakovrm themethodofsynthesisofcompositionalmicroprogramcontrolunitwithdivisionofcodesandcaching AT nikolaenkodv themethodofsynthesisofcompositionalmicroprogramcontrolunitwithdivisionofcodesandcaching |
| first_indexed |
2025-11-25T22:19:25Z |
| last_indexed |
2025-11-25T22:19:25Z |
| _version_ |
1850559301587828736 |
| fulltext |
«Штучний інтелект» 2’2008 59
3Б
УДК 681.324
А.А. Баркалов1, С.А. Ковалев2, Р.М. Бабаков3, Д.В. Николаенко2
1 Университет Зеленогурский, г. Зеленая Гура, Польша
2 Донецкий национальный технический университет, Украина
3 Государственный университет информатики и искусственного интеллекта, Украина
Метод синтеза композиционного
микропрограммного устройства управления
с разделением кодов и кэшированием
Разработан метод синтеза базовой структуры композиционного микропрограммного устройства
управления с разделением кодов и кэшированием микрокоманд. В основе метода лежит
эвристическое распределение операторных линейных цепей в адресном пространстве управляющей
памяти, обеспечивающее максимальное для реализуемого алгоритма управления значение
вероятности кэш-попаданий. Приведен пример использования разработанного метода синтеза.
Общая постановка проблемы
Важным составным элементом современных цифровых вычислительных сис-
тем является устройство управления (УУ), одним из способов реализации которого
является композиционное микропрограммное устройство управления (КМУУ) с
разделением кодов, характеристики которого во многом определяют характеристики
системы в целом [1]. В работе [2] для увеличения быстродействия схемы базовой
структуры КМУУ с разделением кодов предлагается использовать принцип кэширо-
вания сигналов, что требует модификации исходной структуры путем введения
дополнительного блока, реализующего функции кэш-памяти. Использование данного
модуля позволяет снизить среднее время доступа к относительно медленным
блокам, реализованным в базисе ПЗУ или ППЗУ, что приводит к уменьшению
средней длительности такта работы устройства и к увеличению его среднего быстро-
действия. Условимся обозначать полученную в [2] базовую структуру КМУУ с
разделением кодов и кэшированием через S1k.
Характерной особенностью всех структур КМУУ является их аппаратная
привязка к реализуемому алгоритму управления. Данная особенность позволяет
провести оптимизацию схемы КМУУ для каждого конкретного случая реализации.
В работе [3] предложен эвристический метод оптимизации эффективности структу-
ры S1k, основанный на специальной адресации микрокоманд в управляющей памяти.
В настоящей статье предлагается метод синтеза логической схемы базовой
структуры КМУУ с разделением кодов и кэш-памятью, основанный на предложен-
ном в [3] эвристическом алгоритме адресации микрокоманд.
Метод синтеза КМУУ с разделением кодов
и кэш-памятью микрокоманд
Исходными данными при синтезе структуры S1k являются:
– исходная граф-схема алгоритма (ГСА);
– вероятности выполнения логических условий;
– тип архитектуры и размеры блока данных модуля кэш-памяти.
Для синтеза структуры S1k предлагается метод, включающий следующие
основные этапы:
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 2’2008 60
3Б
1. Разбиение множества микрокоманд заданной ГСА на операторные линейные
цепи.
2. Получение с использованием разработанного эвристического алгоритма шести
значений вероятности кэш-попаданий, обусловленных шестью стратегиями выбора
нераспределенных операторных линейных цепей (ОЛЦ), и выбор варианта размеще-
ния ОЛЦ с максимальным значением вероятности кэш-попаданий.
3. Кодирование ОЛЦ и адресация микрокоманд согласно выбранному варианту
размещения.
4. Формирование содержимого ПЗУ управляющей памяти.
5. Построение прямой структурной таблицы.
6. Формирование системы функций переходов.
7. Синтез функциональной схемы устройства в заданном элементном базисе.
Пример синтеза базовой структуры КМУУ
с разделением кодов и кэш-памятью микрокоманд
Рассмотрим пример синтеза структуры S1k для ГСА G1 (рис. 1). Содержимое
операторных вершин ГСА представлено в табл. 1.
Отметим, что для обеспечения функционирования КМУУ в микрокоманды,
являющиеся выходами ОЛЦ, добавлена микрооперация y0, а в МК a11, являющейся
последней в ГСА, добавлена микрооперация yk.
НАЧАЛО
КОНЕЦ
a1
a2
a3
a9
a10 a6
a7
a8
a4
a5
a11
x1
x2
x5
x3
x2
x1
x4
1
0 0
1
1
0
0
1
0
0 1
1
0
Рисунок 1 – Граф-схема алгоритма G
1
Метод синтеза композиционного микропрограммного устройства управления…
«Штучний інтелект» 2’2008 61
3Б
Пусть известны (на основании теоретических или экспериментальных исследо-
ваний) вероятности переходов: p(x1) = 0,2; p(x2) = 0,7; p(x3) = 0,5; p(x4) = 0,1; p(x5) = 0,9.
Таблица 1 – Содержимое операторных вершин ГСА G1
ai Y(ai) ai Y(ai)
a1 y1 y2 y3 a7 y1 y4
a2 y4 a8 y2 y5 y0
a3 y2 y5 y0 a9 y3
a4 y1 y3 a10 y2 y0
a5 y3 y0 a11 y1 y2 y4 yk
a6 y2 y3 y5
1. Сформируем ОЛЦ известным способом [1]: O1 = {a1, a2, a3}, O2 = {a4, a5},
O3 = {a6, a7, a8}, O4 = {a9, a10}, O5 = {a11}. Максимальный размер ОЛЦ Nmax = 3, следо-
вательно, R(T) = ]log2(Nmax)[ = 2. Для пяти ОЛЦ R(τ) = ]log25[ = 3. Разрядность адреса
микрокоманды R = R(T) + R(τ) = 5, емкость ПЗУ схемы управляющей памяти (УП)
составит 2R = 32 слова. При размере строки кэша NC = 8 слов адресное пространство
УП делится на четыре блока: B1 – B4. Внутри каждой ОЛЦ микрокоманды имеют по-
следовательные номера, начиная с нулевого.
Определим входы ОЛЦ i
jI , где i – номер входа, j – номер ОЛЦ:
1
1I = a1; 1
2I = a2; 1
2I = a4; 2
2I = a5; 1
3I = a6; 2
3I = a7; 1
4I = a9; 1
5I = a11.
2. В табл. 2 показаны экспериментальные значения вероятности кэш-попада-
ний для различных стратегий [3], полученные с помощью специально разработанной
программной имитационно-аналитической модели рассматриваемой структуры.
Определение значений вероятности кэш-попаданий выполнено для кэш-памяти, блок
данных которой имеет одну строку размером в 8 слов. Это исключает влияние на
результат типа архитектуры кэш-памяти.
Таблица 2 – Значения ph для различных стратегий
Стратегия ph Стратегия ph
1 0,8273 4 0,7877
2 0,7877 5 0,7877
3 0,8273 6 0,7877
Сходность значений ph для различных стратегий объясняется относительно
низкой сложностью исходной ГСА.
Очевидно, что стратегии 1 и 3 дают максимальные значения вероятности кэш-
попаданий. В качестве варианта размещения ОЛЦ выберем результат для стратегии 3.
Для данной стратегии размещение ОЛЦ в УП выполнено в работе [3] и в оконча-
тельном виде отражено в табл. 3.
Таблица 3 – Адресация ОЛЦ после оптимизации (G1)
Адрес ОЛЦ Адрес ОЛЦ
0 O2 12 O4
4 O3 16 O5
8 O1
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 2’2008 62
3Б
3. С учетом выбранного варианта размещения кодирование ОЛЦ представлено
в табл. 4, а адресация микрокоманд – в табл. 5.
Таблица 4 – Кодирование ОЛЦ
Oi K(Oi)
τ1 τ2 τ3
Oi K(Oi)
τ1 τ2 τ3
O1 0 1 0 O4 0 1 1
O2 0 0 0 O5 1 0 0
O3 0 0 1
Таблица 5 – Адресация микрокоманд
ai τ1 τ2 τ3 T1 T2 ai τ1 τ2 τ3 T1 T2
a1 0 1 0 0 0 a7 0 0 1 0 1
a2 0 1 0 0 1 a8 0 0 1 1 0
a3 0 1 0 1 1 a9 0 1 1 0 0
a4 0 0 0 0 0 a10 0 1 1 0 1
a5 0 0 0 0 1 a11 1 0 0 0 0
a6 0 0 1 0 0
4. Содержимое ПЗУ управляющей памяти строится на основании табл. 1 и 5 и
представлено в табл. 6.
Таблица 6 – Содержимое ПЗУ управляющей памяти
Адрес
τ1 τ2 τ3 T1 T2
Микрооперации
y1 y2 y3 y4 y5 y0 yk
Адрес
τ1 τ2 τ3 T1 T2
Микрооперации
y1 y2 y3 y4 y5 y0 yk
0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1
0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 * * * * * * *
0 0 0 1 0 * * * * * * * 1 0 0 1 0 * * * * * * *
0 0 0 1 1 * * * * * * * 1 0 0 1 1 * * * * * * *
0 0 1 0 0 0 1 1 0 1 0 0 1 0 1 0 0 * * * * * * *
0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 0 1 * * * * * * *
0 0 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 * * * * * * *
0 0 1 1 1 * * * * * * * 1 0 1 1 1 * * * * * * *
0 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 * * * * * * *
0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 * * * * * * *
0 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1 0 * * * * * * *
0 1 0 1 1 * * * * * * * 1 1 0 1 1 * * * * * * *
0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 * * * * * * *
0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 * * * * * * *
0 1 1 1 0 * * * * * * * 1 1 1 1 0 * * * * * * *
0 1 1 1 1 * * * * * * * 1 1 1 1 1 * * * * * * *
Метод синтеза композиционного микропрограммного устройства управления…
«Штучний інтелект» 2’2008 63
3Б
Можно констатировать, что при емкости ПЗУ 32 слова используются лишь 11
адресов, то есть 34,4 % емкости УП. Данный факт обусловлен особенностями прин-
ципа разделения кодов [1].
5. После того, как известны адреса микрокоманд (табл. 5), прямая структурная
таблица строится известным способом [1] и для нашего примера представлена в
табл. 7. Таблица включает следующие столбцы:
Oi – текущая ОЛЦ;
K(Oi) – код текущей ОЛЦ;
i
jI – i-й вход ОЛЦ Oj;
K( i
jI ) – полный адрес МК, являющейся i-м входом ОЛЦ Oj;
Xh – логические условия, обеспечивающие данный переход;
Фh – функции возбуждения регистра памяти;
Ψh – функции возбуждения счетчика адреса;
h – номер перехода.
При построении ПСТ предполагается использование в качестве элементов
памяти триггеров D-типа.
Таблица 7 – Прямая структурная таблица КМУУ S1k (G1)
Oi K(Oi) i
jI K( i
jI ) Xh Фh Ψh h
1
2I 0 0 0 0 0 21xx – – 1
1
3I 0 0 1 0 0 21xx D3 – 2
O1 0 1 0
1
4I 0 1 1 0 0 1x D2 D3 – 3
2
3I 0 0 1 0 1 4x D3 D5 4
2
2I 0 0 0 0 1 14xx – D5 5
1
1I 0 1 0 0 0 514 xxx D2 – 6
O2 0 0 0
1
5I 1 0 0 0 0 514 xxx D1 – 7
2
2I 0 0 0 0 1 1x – D5 8
1
1I 0 1 0 0 0 51xx D2 – 9
O3 0 0 1
1
5I 1 0 0 0 0 51xx D1 – 10
1
4I 0 1 1 0 0 3x D2 D3 – 11
1
2I 0 1 0 0 1 23xx D2 D5 12
1
1I 0 1 0 0 0 523 xxx D2 – 13
O4 0 1 1
1
5I 1 0 0 0 0 523 xxx D1 – 14
6. Система функций переходов образовывается функциями D1 – D3, отождеств-
ляемыми с кодом ОЛЦ τ1τ2τ3, и функциями D4, D5, отождествляемыми с кодом МК
внутри ОЛЦ T1T2.
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 2’2008 64
3Б
Функции строятся по известной методике [1] на основании содержимого
ПСТ (табл. 7). Например: 332143211321213213 xфффxфффxфффxxфффD ∨∨∨= .
С целью уменьшения аппаратурных затрат в схеме устройства может быть
выполнена минимизация функций переходов.
7. Построение функциональной схемы КМУУ S1k выполняется традиционно и
рассмотрено в [1].
Заключение
Предложенный в статье метод синтеза базовой структуры композиционного
микропрограммного устройства управления с разделением кодов и кэш-памятью
позволяет эвристически выбрать оптимальное размещение ОЛЦ реализуемой ГСА в
адресном пространстве ПЗУ управляющей памяти, дающее максимальную величину
вероятности кэш-попаданий алгоритма. Проведенные авторами эксперименты пока-
зали, что разработанный метод на всех этапах поддается алгоритмизации и может
быть в дальнейшем использован в системах автоматизированного проектирования
цифровых устройств управления.
Литература
1. Баркалов А.А. Синтез устройств управления на программируемых логических устройствах. –
Донецк: ДонНТУ, 2002. – 262 с.
2. Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. Организация композиционных
микропрограммных устройств управления с разделением кодов и кэш-памятью // Искусственный
интеллект. – 2007. – № 3. – С. 135-138.
3. Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. Эвристический алгоритм оптими-
зации размещения микрокоманд в композиционном микропрограммном устройстве управления с
разделением кодов и кэш-памятью // Искусственный интеллект. – 2008. – № 1. – С. 20-29.
О.О. Баркалов, С.О. Ковальов, Р.М. Бабаков, Д.В. Ніколаєнко
Метод синтезу композиційного мікропрограмного пристрою керування з розподілом кодів і
кешуванням
Розроблено метод синтезу базової структури композиційного мікропрограмного пристрою керування
з розподілом кодів і кешуванням мікрокоманд. В основі методу лежить евристичний розподіл
операторних лінійних ланцюгів в адресному просторі керуючої пам'яті, що забезпечує максимальне
для реалізованого алгоритму керування значення ймовірності кеш-влучень. Наведено приклад
використання розробленого методу синтезу.
A.A. Barkalov, S.A. Kovalev, R.M. Babakov, D.V. Nikolaenko
The method of Synthesis of Compositional Microprogram Control Unit with Division of Codes and
Caching
The method of synthesis of base structure of the compositional microprogram control unit with division of
codes and caching of microinstructions is developed. It is based on heuristic distribution of operational linear
circuits in address space of the managing memory, providing maximal for realized control algorithm value of
probability of cache-hits. The example of using of the developed method of synthesis is resulted.
Статья поступила в редакцию 17.04.2008.
|