Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью
Разработан эвристический алгоритм повышения эффективности использования модуля кэш-памяти в 
 композиционном микропрограммном устройстве управления с разделением кодов, основанный на 
 специальной адресации операторных линейных цепей. Предложен ряд стратегий объ...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/6350 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью / Р.М. Бабаков, А.А. Баркалов, С.А. Ковалев, Д.В. Николаенко // Штучний інтелект. — 2008. — № 1. — С. 20-29. — Бібліогр.: 3 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860072367033679872 |
|---|---|
| author | Бабаков, Р.М. Баркалов, А.А. Ковалев, С.А. Николаенко, Д.В. |
| author_facet | Бабаков, Р.М. Баркалов, А.А. Ковалев, С.А. Николаенко, Д.В. |
| citation_txt | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью / Р.М. Бабаков, А.А. Баркалов, С.А. Ковалев, Д.В. Николаенко // Штучний інтелект. — 2008. — № 1. — С. 20-29. — Бібліогр.: 3 назв. — рос. |
| collection | DSpace DC |
| description | Разработан эвристический алгоритм повышения эффективности использования модуля кэш-памяти в 
композиционном микропрограммном устройстве управления с разделением кодов, основанный на 
специальной адресации операторных линейных цепей. Предложен ряд стратегий объединения 
нескольких операторных цепей в одном блоке памяти, позволяющий в общем случае увеличить 
значение вероятности кэш-попаданий для граф-схемы реализуемого алгоритма управления. 
Рассмотрен пример использования предложенного эвристического алгоритма.
Евристичний алгоритм оптимізації розміщення мікрокоманд в композиційному мікропрограмному 
пристрої керування із розподілом кодів та кеш-пам’яттю 
Розроблено евристичний алгоритм збільшення ефективності використання модуля кеш-пам’яті у 
композиційному мікропрограмному пристрої керування із розподілом кодів, заснований на 
спеціальній адресації операторних лінійних кіл. Запропонований ряд стратегій поєднання кількох 
операторних кіл в одному блоці пам’яті, що дозволяє у загальному випадку збільшити значення 
імовірності кеш-попадань для граф-схеми реалізованого алгоритму керування. Розглянутий приклад 
використання запропонованого евристичного алгоритму.
The Heuristic Algorithm of Optimization of Placement of Microinstructions in Compositional 
Microprogram Control Unit with Division of Codes and Cache-memory 
The heuristic algorithm for increased efficiency of cache-memory module usage in compositional 
microprogram control unit, based on special addressing of operator linear chains, is developed. The number 
of strategies to combine some operator linear chains in one memory block are proposed; they allow in 
common case to increase value of probability of cache hits for given flow-chart. The example of using of 
proposed heuristic algorithm is given.
|
| first_indexed | 2025-12-07T17:11:35Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 1’2008 20
1Б
УДК 681.324
А.А. Баркалов1, С.А. Ковалев2, Р.М. Бабаков3, Д.В. Николаенко2
1 Институт компьютерной инженерии и электроники, г. Зеленая Гура, Польша
2 Донецкий национальный технический университет, Украина
3 Государственный университет информатики и искусственного интеллекта,
г. Донецк, Украина
a.barkalov@iie.uz.zgora.pl
cpld@mail.ru
Эвристический алгоритм оптимизации
размещения микрокоманд в композиционном
микропрограммном устройстве управления
с разделением кодов и кэш-памятью
Разработан эвристический алгоритм повышения эффективности использования модуля кэш-памяти в
композиционном микропрограммном устройстве управления с разделением кодов, основанный на
специальной адресации операторных линейных цепей. Предложен ряд стратегий объединения
нескольких операторных цепей в одном блоке памяти, позволяющий в общем случае увеличить
значение вероятности кэш-попаданий для граф-схемы реализуемого алгоритма управления.
Рассмотрен пример использования предложенного эвристического алгоритма.
Общая постановка проблемы
Одним из структурных элементов современных вычислительных систем
является устройство управления (УУ), которое может быть реализовано в виде ком-
позиционного микропрограммного устройства управления (КМУУ) с разделением
кодов, в котором достигается минимальное число выходов схемы адресации [1].
Использование элементного базиса ПЗУ при реализации управляющей памяти (УП)
удешевляет схему устройства, однако, в то же время приводит к значительному
снижению быстродействия схемы [2]. Таким образом, для промышленности средств
вычислительной техники актуальной научно-технической задачей является задача
увеличения быстродействия схемы КМУУ. Решение данной задачи повлечет за
собой увеличение быстродействия вычислительных систем, реализованных на базе
КМУУ, и, как следствие, расширит область их применения.
Для увеличения быстродействия схемы КМУУ с разделением кодов в работе
[3] предложен метод, заключающийся в использовании дополнительного модуля
кэш-памяти микрокоманд для хранения наиболее часто используемых строк
управляющей памяти. Использование кэш-памяти позволяет снизить среднее время
доступа к управляющей памяти, что приводит к уменьшению средней длительности
такта работы устройства и к увеличению его среднего быстродействия. При этом
основным параметром, влияющим на эффективность использования кэш-памяти
микрокоманд, является вероятность кэш-попаданий ph, характеризующая отношение
количества тактов, в которых произошло кэш-попадание, к общему количеству
тактов работы устройства.
Эвристический алгоритм оптимизации размещения микрокоманд…
«Штучний інтелект» 1’2008 21
1Б
Характерной особенностью всех структур КМУУ является их аппаратная
привязка к реализуемому алгоритму управления. Данная особенность позволяет
провести оптимизацию схемы КМУУ для каждого конкретного случая реализации.
В структуре КМУУ с разделением кодов и кэш-памятью, предложенной в [3], одним
из факторов, влияющих на величину вероятности кэш-попаданий, является реали-
зуемый алгоритм управления, традиционно представляемый в виде граф-схемы
алгоритма (ГСА). Количество микрокоманд (МК), операторных линейных цепей
(ОЛЦ) и переходов между ОЛЦ, а также сама структура ГСА – все это оказывает
влияние на величину ph. При этом на сегодняшний день неисследованными остаются
факторы, влияющие на увеличение значения ph и, как следствие, на увеличение
среднего быстродействия устройства управления.
Эвристический подход к оптимизации размещения
микрокоманд в управляющей памяти
В структурах КМУУ с разделением кодов имеют место естественная адресация
микрокоманд внутри каждой ОЛЦ, а также тот факт, что в первой микрокоманде
ОЛЦ адресные разряды, следующие после кода ОЛЦ, равны нулям [2]. По этим
причинам процесс адресации микрокоманд, являющийся одним из этапов синтеза
КМУУ, в структурах с разделением кодов сводится по сути к адресации ОЛЦ.
Пусть в заданной ГСА существует переход из ОЛЦ αi в ОЛЦ αj. При этом если
обе ОЛЦ в данный момент находятся в кэш-памяти, то возникнет ситуация кэш-
попадания, в противном случае – ситуация кэш-промаха. В том случае, если обе
ОЛЦ расположены в управляющей памяти последовательно и принадлежат одному
блоку памяти, они окажутся вместе в одной строке кэш-памяти, и упомянутый
переход из αi в αj всегда будет приводить к кэш-попаданию. Если же данные ОЛЦ
находятся в различных блоках памяти, то при выполнении перехода αi → αj
возможна ситуация кэш-промаха, и значение ph для ГСА будет несколько ниже. Если
же одновременное нахождение данных ОЛЦ в кэш-памяти невозможно (например,
при использовании кэш-памяти с прямым отображением данных), то данный
переход всегда будет приводить к кэш-промаху, что еще более снизит величину
вероятности кэш-попаданий для заданной ГСА.
Согласно принципу пространственной локальности данных, в случае кэш-
промаха в кэш из УП помещается не только запрашиваемая микрокоманда, но и
несколько микрокоманд из ближайших к ней адресов памяти. При этом количество
загружаемых команд определяется размером строки кэш-памяти, а для кодирования
микрокоманд внутри строки используется часть младших разрядов адреса микро-
команды. С учетом этого содержимое управляющей памяти может быть представлено
в виде блоков микрокоманд, имеющих размер, равный размеру строки кэш-памяти и
располагающихся последовательно, начиная с нулевого адреса. Деление УП на
блоки является постоянным и не зависит от размещения микрокоманд в адресном
пространстве УП.
Экспериментальным путем авторами выработаны четыре основных эвристи-
ческих правила (эвристики), характеризующие пути повышения эффективности
размещения ОЛЦ в блоках управляющей памяти:
Эвристика 1. Вероятность кэш-попаданий не зависит от того, какому по
порядку блоку памяти принадлежит ОЛЦ. Иными словами, конкретные значения
адресов памяти, занимаемые ОЛЦ, не оказывают влияния на вероятность кэш-
попаданий. Из рассмотренного правила вытекает следующий вывод: если содержимое
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 1’2008 22
1Б
блока памяти сместить в адресном пространстве УП вперед или назад на количество
ячеек, кратное размеру блока, то значение вероятности кэш-попаданий не изменится.
Эвристика 2. Вероятность кэш-попаданий не зависит от порядка следования
ОЛЦ в блоке. Эвристика действует и в том случае, если блок памяти содержит более
двух ОЛЦ. Вывод, следующий из данного правила, может быть сформулирован
следующим образом: если несколько ОЛЦ могут быть размещены в одном блоке
УП, то порядок помещения ОЛЦ в блок не влияет на результирующее значение
вероятности кэш-попаданий.
Для пояснения третьего эвристического правила введем следующие определения:
1. «Опасной» МК считается такая МК, при выполнении которой кэш-промах
возможен (но не обязателен). МК, при выполнении которой кэш-промах невозможен
ни при каких обстоятельствах, считается «безопасной». К «опасным» МК относятся
микрокоманды, являющиеся входами ОЛЦ.
2. Вероятностью выполнения (или весом) p(ai) микрокоманды ai будем
называть отношение среднего количества выполнений K(ai) МК ai за один проход
алгоритма к среднему количеству микрокоманд K, выполняющихся за один проход
алгоритма
p(ai) = K(ai) / K. (1)
3. «Опасный» вес v(ai) микрокоманды ai равен сумме весов микрокоманд
других ОЛЦ, из которых есть непосредственный переход в микрокоманду ai,
умноженных на вероятность данного перехода.
4. «Опасный» вес блока памяти равен суммарному «опасному» весу ОЛЦ,
входящих в блок.
Эвристика 3. Если ОЛЦ Oi имеет переходы в ОЛЦ Oj, то размещение этих
ОЛЦ в одном блоке памяти снижает «опасный» вес ОЛЦ Oj. Из эвристики 3 может
быть сделан следующий вывод: наиболее целесообразно добавить в текущий блок ту
ОЛЦ, при которой «опасный» вес текущего блока будет минимальным.
Эвристика 4. Увеличение количества ОЛЦ, на которые разбито множество
микрокоманд рассматриваемой ГСА, не влияет на вероятности выполнения микро-
команд, но увеличивает количество вариантов размещения ОЛЦ в управляющей памяти.
Разработка эвристического алгоритма
оптимизированного размещения ОЛЦ
в управляющей памяти
Основываясь на полученных эвристиках, построим эвристический алгоритм
оптимизации размещения ОЛЦ в адресном пространстве управляющей памяти с
целью повышения значения вероятности кэш-попаданий.
Исходными данными при этом выступают:
− исходная ГСА;
− вероятности выполнения логических условий;
− размер строки данных в модуле кэш-памяти;
− количество и содержимое ОЛЦ.
Алгоритм имеет следующие основные этапы:
1. Определение вероятностей выполнения микрокоманд.
2. Отнесение всех ОЛЦ ко множеству нераспределенных ОЛЦ.
Эвристический алгоритм оптимизации размещения микрокоманд…
«Штучний інтелект» 1’2008 23
1Б
3. Считать текущим начальный блок УП.
4. Если текущий блок полностью заполнен, считать текущим следующий
пустой блок.
5. Если текущий блок пустой, поместить в него одну из нераспределенных ОЛЦ.
6. Если текущий блок заполнен частично, добавить в него ту нераспределенную
ОЛЦ, вместе с которой суммарный «опасный» вес блока будет минимальным.
7. Если остались нераспределенные ОЛЦ, перейти к пункту 4.
8. Конец.
Отметим следующее.
В пункте 5 алгоритма в пустой блок добавляется одна из нераспределенных
ОЛЦ. Выбор нераспределенной ОЛЦ в каком-то смысле может быть произвольным:
какая бы ОЛЦ ни была выбрана первой в блоке, алгоритм в силу эвристики 3 должен
заполнить блок оптимальным способом. При этом те ОЛЦ, которые будут добавлены
к блоку, обречены на «соседство» с первой выбранной ОЛЦ и варианты их
«соседства» с другими ОЛЦ не рассматриваются. Таким образом, способ выбора
первой ОЛЦ в блоке влияет на конечное содержимое блока, то есть на «опасный»
вес блока и в конечном итоге на вероятность кэш-попаданий ГСА.
В настоящей работе предлагаются шесть вариантов способа выбора первой
ОЛЦ для пустого блока, которые условимся называть стратегиями выбора нераспре-
деленных ОЛЦ:
Стратегия 1. Выбирается ОЛЦ с максимальным весом.
Стратегия 2. Выбирается ОЛЦ с минимальным весом.
Стратегия 3. Выбирается ОЛЦ с максимальным «опасным» весом.
Стратегия 4. Выбирается ОЛЦ с минимальным «опасным» весом.
Стратегия 5. Выбирается ОЛЦ с максимальным отношением «опасного» веса
к обычному весу.
Стратегия 6. Выбирается ОЛЦ с минимальным отношением «опасного» веса
к обычному весу.
При использовании каждой из шести стратегий в общем случае может быть
получен различный результат (вариант размещения микрокоманд и значение ph).
Безусловно, помимо предложенных, может быть найдено множество других стратегий,
оказывающих различное влияние на результат алгоритма: например, стратегия, при
которой первой всегда выбирается ОЛЦ, содержащая стартовую МК a1, или стратегия
случайного выбора. Поиск наиболее оптимальной стратегии выбора ОЛЦ является
отдельно ветвью исследований и в настоящей работе не рассматривается.
Эвристический характер предложенного алгоритма заключается в следующем:
1. Оптимизация размещения производится для каждого блока в отдельности
без учета связей между блоками. Большое количество переходов между ОЛЦ,
находящимися в разных блоках, может приводить к увеличению количества кэш-
промахов и снижению величины ph.
2. Не учитывается количество строк в модуле кэш-памяти. Если кэш-память
содержит лишь одну строку фиксированной длины, алгоритм замещения данных,
предназначенный для выбора одной из нескольких строк кэш-памяти, не
используется. В этом случае значение вероятности кэш-попаданий будет одина-
ковым для любой архитектуры кэш-памяти. Если же кэш-память содержит
несколько строк, то влияние архитектуры кэш-памяти и алгоритма замещения
данных на значение вероятности кэш-попаданий может быть значительным.
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 1’2008 24
1Б
3. Не используется оптимальная стратегия выбора нераспределенной ОЛЦ.
Хотя экспериментальные исследования показывают, что предложенные стратегии
оказываются достаточно эффективными, нельзя говорить об абсолютной опти-
мальности какой-либо из них.
Пример использования эвристического алгоритма
Рассмотрим подробно пример оптимизации размещения содержимого управ-
ляющей памяти с использованием разработанного эвристического алгоритма и
третьей стратегии выбора нераспределенной ОЛЦ.
Пусть алгоритм управления задан ГСА G (рис. 1). Пусть также известны
вероятности переходов логических условий: p(x1) = 0,2; p(x2) = 0,7; p(x3) = 0,5;
p(x4) = 0,1; p(x5) = 0,9. Размер строки кэш-памяти будем считать равным 8 слов.
Сформируем ОЛЦ известным способом [2]: 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.
НАЧАЛО
КОНЕЦ
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
Эвристический алгоритм оптимизации размещения микрокоманд…
«Штучний інтелект» 1’2008 25
1Б
Выполняемые шаги эвристического алгоритма условимся обозначать в форме
«Шаг i, пункт j», где i в каждом шаге увеличивается на единицу, а j соответствует
номеру пункта алгоритма.
Шаг 1, п. 1. В результате экспериментального моделирования работы КМУУ
по заданной ГСА определяем вероятности выполнения каждой МК (табл. 1).
Таблица 1 – Вероятности выполнения микрокоманд ГСА G1
ai p(ai) ai p(ai)
a1 0,0878 a7 0,0923
a2 0,1021 a8 0,0923
a3 0,1021 a9 0,0408
a4 0,0245 a10 0,0408
a5 0,3512 a11 0,0088
a6 0,0571
Шаг 2, п. 2. Относим все ОЛЦ ко множеству нераспределенных ОЛЦ.
Шаг 3, п. 3. В качестве текущего выберем первый блок, начинающийся с адреса 0.
Шаг 4, п. 4. Текущий блок B1 не является полностью заполненным.
Шаг 5, п. 5. Текущий блок B1 полностью пустой. Определим «опасные» веса
каждой нераспределенной ОЛЦ.
v(O1) = v(a1) + v(a2);
v(a1) = p(a5)⋅(1–p(x4))⋅p(x1)⋅p(x5) + p(a8)⋅p(x1)⋅p(x5) + p(a10)⋅(1–p(x3))⋅(1–p(x2))⋅p(x5) =
= 0,3512⋅(1–0,1)⋅0,2⋅0,9 + 0,0923⋅0,2⋅0,9 + 0,0408⋅(1–0,5)⋅(1–0,7)⋅0,9 =
= 0,0569 + 0,0166 + 0,0055 = 0,0790;
v(a2) = p(a10)⋅(1–p(x3))⋅p(x2) = 0,0143;
v(O1) = 0,0790 + 0,0143 = 0,0933.
v(O2) = v(a4) + v(a5);
v(a4) = p(a3)⋅(1–p(x1))⋅(1–p(x2)) = 0,0245;
v(a5) = p(a8)⋅(1–p(x1)) = 0,0738;
v(O2) = 0,0245 + 0,0738 = 0,0983.
v(O3) = v(a6) + v(a7);
v(a6) = p(a3)⋅(1–p(x1))⋅p(x2) = 0,0572;
v(a7) = p(a5)⋅p(x4) = 0,1681⋅0,3 = 0,0351;
v(O3) = 0,0572 + 0,0351 = 0,0923.
v(O4) = v(a9);
v(a9) = p(a3)⋅p(x1) = 0,0204;
v(O4) = 0,0204.
v(O5) = v(a11);
v(a11) = p(a5)⋅(1–p(x4))⋅p(x1)⋅(1–p(x5)) + p(a8)⋅p(x1)⋅(1–p(x5))+
+ p(a10)⋅(1–p(x3))⋅(1–p(x2))⋅(1–p(x5)) = 0,0088;
v(O5) = 0,0088.
Поскольку на дальнейших шагах алгоритма полученные значения «опасных»
весов ОЛЦ могут потребоваться снова, сведем их в таблицу (табл. 2).
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 1’2008 26
1Б
Таблица 2 – «Опасные» веса ОЛЦ ГСА G1
Oi O1 O2 O3 O4 O5
v(Oi) 0,0933 0,0983 0,0923 0,0204 0,0088
Согласно стратегии 3, выбираем ОЛЦ с максимальным «опасным» весом, т.е. O2.
Данную ОЛЦ добавляем в блок B1 и размещаем, начиная с нулевого адреса
(с ближайшего свободного адреса, допустимого для размещения ОЛЦ).
ОЛЦ O2 считаем распределенной и исключаем из множества нераспре-
деленных ОЛЦ. Поскольку пока O2 – единственная в блоке, «опасный» вес блока
v(B1) считаем равным v(O2).
Шаг 6, п. 6. Текущий блок B1, способный вмещать две ОЛЦ, содержит только
одну ОЛЦ O2, то есть заполнен частично. Добавим в блок B1 ту нераспределенную
ОЛЦ, вместе с которой «опасный» вес блока будет наименьшим.
Согласно эвристике 3, добавление в блок B1 еще одной ОЛЦ может снизить
«опасные» веса каждой ОЛЦ, находящейся в блоке. Это возможно при условии, что
существуют непосредственные микропрограммные переходы между ОЛЦ, нахо-
дящимися в одном блоке.
Найдем «опасные» веса блока B1 при добавлении к нему каждой из
нераспределенных ОЛЦ.
1. Если добавляем ОЛЦ O1.
Из O1 в O2 существуют следующие переходы:
– переход из a3 в a4: вес данного перехода равен
v(a3→a4) = p(a3)⋅(1–p(x1))⋅(1–p(x2)) = 0,0245.
За счет «безопасности» этого перехода «опасный» вес O2 снижается на вели-
чину v(a3→a4) и становится равным v(O2) = 0,0983 – 0,0245 = 0,0738.
Из O2 в O1 существуют следующие переходы:
– переход из a5 в a1: вес перехода равен
v(a5→a1) = p(a5)⋅(1–p(x4))⋅p(x1)⋅p(x5) = 0,0569.
За счет «безопасности» этого перехода «опасный» вес O1 снижается на вели-
чину v(a5→a1) и становится равным v(O1) = 0,0933 – 0,0569 = 0,0364.
При этом «опасный» вес блока B1 будет равным
v(B1) = v(O2) + v(O1) = 0,0738 + 0,0364 = 0,1102.
2. Если добавляем ОЛЦ O3.
Из O3 в O2 существуют следующие переходы:
– переход из a8 в a5: вес перехода равен
v(a8→a5) = p(a8)⋅(1–p(x1)) = 0,0738.
За счет «безопасности» этого перехода «опасный» вес O2 снижается на
величину v(a8→a5) и становится равным v(O2) = 0,0983 – 0,0738 = 0,0245.
Из O2 в O3 существуют следующие переходы:
– переход из a5 в a7: вес перехода равен
v(a5→a7) = p(a5)⋅p(x4) = 0,0351.
За счет «безопасности» этого перехода «опасный» вес O3 снижается на
величину v(a5→a6) и становится равным v(O3) = 0,0923 – 0,0351 = 0,0572.
При этом «опасный» вес блока B1 будет равным
v(B1) = v(O2) + v(O3) = 0,0245 + 0,0572 = 0,0817.
Эвристический алгоритм оптимизации размещения микрокоманд…
«Штучний інтелект» 1’2008 27
1Б
3. Если добавляем ОЛЦ O4.
Из O2 в O4 непосредственные переходы отсутствуют, следовательно, при
размещении O2 и O4 в одном блоке «опасный» вес O4 не уменьшается и остается
равным v(O4) = 0,0204.
Из O4 в O2 непосредственные переходы отсутствуют, следовательно, при
размещении O4 и O2 в одном блоке «опасный» вес O2 не уменьшается и остается
равным v(O2) = 0,0983.
При этом «опасный» вес блока B1 будет равным
v(B1) = v(O2) + v(O4) = 0,0983 + 0,0204 = 0,1187.
4. Если добавляем ОЛЦ O5.
Из O5 в O2 непосредственные переходы отсутствуют, следовательно, при
размещении O5 и O2 в одном блоке «опасный» вес O2 не уменьшается и остается
равным v(O2) = 0,0983.
Из O2 в O5 существуют следующие переходы:
– переход из a5 в a11: вес перехода равен
v(a5→a11) = p(a5)⋅(1–p(x4))⋅p(x1)⋅(1–p(x5)) = 0,0063.
За счет «безопасности» этого перехода «опасный» вес O5 снижается на
величину v(a5→a1) и становится равным v(O5) = 0,0088 – 0,0063 = 0,0025.
При этом «опасный» вес блока B1 будет равным
v(B1) = v(O2) + v(O5) = 0,0983 + 0,0025 = 0,1008.
Очевидно, что минимальное значение «опасного» веса блока будет получено
при добавлении ОЛЦ O3. Таким образом, цепь O3 исключаем из множества
нераспределенных ОЛЦ, добавляем в блок B1 и размещаем в УП, начиная с адреса 4
(всегда кратно размеру блока УП).
Шаг 7, п. 7. Множество нераспределенных ОЛЦ не пусто. Переходим к п. 4.
Шаг 8, п. 4. Текущий блок B1, способный вмещать две ОЛЦ, заполнен
полностью. Переходим к блоку B2 и считаем его текущим.
Шаг 9, п. 5. Блок B2 пустой. Добавляем в него одну из нераспределенных ОЛЦ
согласно стратегии 3. Согласно табл. 2, выбираем ОЛЦ O1. Таким образом, ОЛЦ O1
исключается из множества нераспределенных ОЛЦ, распределяется в блок B2 и
размещается в УП, начиная с адреса 8.
Шаг 10, п. 6. Текущий блок B2, способный вмещать две ОЛЦ, содержит только
одну ОЛЦ O1, то есть заполнен частично. Добавим в блок B2 ту нераспределенную
ОЛЦ, вместе с которой «опасный» вес блока будет наименьшим.
Найдем «опасные» веса блока B2 при добавлении к нему каждой из нерас-
пределенных ОЛЦ.
1. Если добавляем ОЛЦ O4.
Из O1 в O4 существуют следующие переходы:
– переход из a3 в a9: вес данного перехода равен
v(a3→a9) = p(a3)⋅p(x1) = 0,0204.
За счет «безопасности» этого перехода «опасный» вес O4 снижается на
величину v(a3→a9) и становится равным v(O4) = 0,0204 – 0,0204 = 0.
Из O4 в O1 существуют следующие переходы:
– переход из a10 в a2: вес перехода равен
v(a10→a2) = p(a10)⋅(1–p(x3))⋅p(x2) = 0,0143.
Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В.
«Искусственный интеллект» 1’2008 28
1Б
– переход из a10 в a1: вес перехода равен
v(a10→a1) = p(a10)⋅(1–p(x3))⋅(1–p(x2))⋅p(x5) = 0,0055.
За счет «безопасности» этого перехода «опасный» вес O1 снижается на
величину v(a10→a2) и становится равным v(O1) = 0,0933 – 0,0143 – 0,0055 = 0,0735.
При этом «опасный» вес блока B2 будет равным
v(B2) = v(O4) + v(O1) = 0 + 0,0735 = 0,0735.
2. Если добавляем ОЛЦ O5.
Из O1 в O5 непосредственные переходы отсутствуют, следовательно, при
размещении O1 и O5 в одном блоке «опасный» вес O5 не уменьшается и остается
равным v(O5) = 0,0088.
Из O5 в O1 непосредственные переходы отсутствуют, следовательно, при
размещении O5 и O1 в одном блоке «опасный» вес O1 не уменьшается и остается
равным v(O1) = 0,0933.
При этом «опасный» вес блока B2 будет равным
v(B2) = v(O1) + v(O5) = 0,0933 + 0,0088 = 0,1021.
Очевидно, что минимальное значение «опасного» веса блока будет получено
при добавлении ОЛЦ O4. Таким образом, цепь O4 исключаем из множества
нераспределенных ОЛЦ, добавляем в блок B2 и размещаем в УП, начиная с адреса 12.
Шаг 11, п. 7. Множество нераспределенных ОЛЦ не пусто. Переходим к
пункту 4.
Шаг 12, п. 4. Текущий блок B2, способный вмещать две ОЛЦ, заполнен
полностью. Переходим к блоку B3 и считаем его текущим.
Шаг 13, п. 5. Блок B3 пустой. Добавляем в него одну из нераспределенных
ОЛЦ согласно стратегии 3. Единственной нераспределенной ОЛЦ является O5,
которая исключается из множества нераспределенных ОЛЦ, добавляется в блок B3,
начиная с адреса 16.
Шаг 14, п. 6. Блок B3 заполнен частично, однако множество нераспределенных
ОЛЦ пусто, поэтому ничего не добавляем.
Шаг 15, п. 7. Множество нераспределенных ОЦЛ пусто, переходим к п. 8.
Шаг 16, п. 8. Результатом работы алгоритма стало следующее размещение
ОЛЦ в адресном пространстве УП (табл. 3).
Таблица 3 – Адресация ОЛЦ после оптимизации (G1)
Адрес ОЛЦ Адрес ОЛЦ
0 O2 12 O4
4 O3 16 O5
8 O1
Отметим, что согласно результатам моделирования, при кэш-памяти размером
1 строка на 8 слов полученное размещение обеспечивает вероятность кэш-попаданий
ph = 0,8273. При последовательном (неоптимизированном) размещении ОЛЦ экспе-
риментальное значение ph = 0,7596. Таким образом, использование предложенного
эвристического алгоритма размещения ОЛЦ в управляющей памяти привело к
повышению эффективности использования модуля кэш-памяти почти на 9 %.
Эвристический алгоритм оптимизации размещения микрокоманд…
«Штучний інтелект» 1’2008 29
1Б
Заключение
Разработанный эвристический алгоритм оптимизации размещения микрокоманд
в управляющей памяти позволяет повысить эффективность использования модуля
кэш-памяти в структуре КМУУ с разделением кодов, что положительно отражается
на быстродействии логической схемы устройства. Практическая реализация данного
алгоритма возможна в специализированных САПР цифровых устройств управления.
В перспективе дальнейшей научной работы авторы видят исследование
особенностей применения алгоритма для различных структур КМУУ с разделением
кодов, имеющих разные архитектурные типы модулей кэш-памяти.
Литература
1. Баркалов А.А., Палагин А.В. Синтез микропрограммных устройств управления. – Киев: Институт
кибернетики НАН Украины, 1997. – 135 с.
2. Баркалов А.А. Синтез устройств управления на программируемых логических устройствах. –
Донецк: ДонНТУ, 2002. – 262 с.
3. Баркалов А.А., Ковалев С.А., Бабаков Р.М., Николаенко Д.В. Организация композиционных микро-
программных устройств управления с разделением кодов и кэш-памятью // Искусственный интел-
лект. – 2007. – № 3. – С. 135-138.
О.О. Баркалов, С.О. Ковальов, Р.М. Бабаков, Д.В. Ніколаєнко
Евристичний алгоритм оптимізації розміщення мікрокоманд в композиційному мікропрограмному
пристрої керування із розподілом кодів та кеш-пам’яттю
Розроблено евристичний алгоритм збільшення ефективності використання модуля кеш-пам’яті у
композиційному мікропрограмному пристрої керування із розподілом кодів, заснований на
спеціальній адресації операторних лінійних кіл. Запропонований ряд стратегій поєднання кількох
операторних кіл в одному блоці пам’яті, що дозволяє у загальному випадку збільшити значення
імовірності кеш-попадань для граф-схеми реалізованого алгоритму керування. Розглянутий приклад
використання запропонованого евристичного алгоритму.
A.A. Barkalov, S.A. Kovalev, R.M. Babakov, D.V. Nikolaenko
The Heuristic Algorithm of Optimization of Placement of Microinstructions in Compositional
Microprogram Control Unit with Division of Codes and Cache-memory
The heuristic algorithm for increased efficiency of cache-memory module usage in compositional
microprogram control unit, based on special addressing of operator linear chains, is developed. The number
of strategies to combine some operator linear chains in one memory block are proposed; they allow in
common case to increase value of probability of cache hits for given flow-chart. The example of using of
proposed heuristic algorithm is given.
Статья поступила в редакцию 03.12.2007.
|
| id | nasplib_isofts_kiev_ua-123456789-6350 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T17:11:35Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Бабаков, Р.М. Баркалов, А.А. Ковалев, С.А. Николаенко, Д.В. 2010-03-01T12:33:20Z 2010-03-01T12:33:20Z 2008 Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью / Р.М. Бабаков, А.А. Баркалов, С.А. Ковалев, Д.В. Николаенко // Штучний інтелект. — 2008. — № 1. — С. 20-29. — Бібліогр.: 3 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6350 681.324 Разработан эвристический алгоритм повышения эффективности использования модуля кэш-памяти в 
 композиционном микропрограммном устройстве управления с разделением кодов, основанный на 
 специальной адресации операторных линейных цепей. Предложен ряд стратегий объединения 
 нескольких операторных цепей в одном блоке памяти, позволяющий в общем случае увеличить 
 значение вероятности кэш-попаданий для граф-схемы реализуемого алгоритма управления. 
 Рассмотрен пример использования предложенного эвристического алгоритма. Евристичний алгоритм оптимізації розміщення мікрокоманд в композиційному мікропрограмному 
 пристрої керування із розподілом кодів та кеш-пам’яттю 
 Розроблено евристичний алгоритм збільшення ефективності використання модуля кеш-пам’яті у 
 композиційному мікропрограмному пристрої керування із розподілом кодів, заснований на 
 спеціальній адресації операторних лінійних кіл. Запропонований ряд стратегій поєднання кількох 
 операторних кіл в одному блоці пам’яті, що дозволяє у загальному випадку збільшити значення 
 імовірності кеш-попадань для граф-схеми реалізованого алгоритму керування. Розглянутий приклад 
 використання запропонованого евристичного алгоритму. The Heuristic Algorithm of Optimization of Placement of Microinstructions in Compositional 
 Microprogram Control Unit with Division of Codes and Cache-memory 
 The heuristic algorithm for increased efficiency of cache-memory module usage in compositional 
 microprogram control unit, based on special addressing of operator linear chains, is developed. The number 
 of strategies to combine some operator linear chains in one memory block are proposed; they allow in 
 common case to increase value of probability of cache hits for given flow-chart. The example of using of 
 proposed heuristic algorithm is given. ru Інститут проблем штучного інтелекту МОН України та НАН України Алгоритмическое и программное обеспечение интеллектуальных систем Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью Евристичний алгоритм оптимізації розміщення мікрокоманд в композиційному мікропрограмному пристрої керування із розподілом кодів та кеш-пам’яттю The Heuristic Algorithm of Optimization of Placement of Microinstructions in Compositional Microprogram Control Unit with Division of Codes and Cache-memory Article published earlier |
| spellingShingle | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью Бабаков, Р.М. Баркалов, А.А. Ковалев, С.А. Николаенко, Д.В. Алгоритмическое и программное обеспечение интеллектуальных систем |
| title | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| title_alt | Евристичний алгоритм оптимізації розміщення мікрокоманд в композиційному мікропрограмному пристрої керування із розподілом кодів та кеш-пам’яттю The Heuristic Algorithm of Optimization of Placement of Microinstructions in Compositional Microprogram Control Unit with Division of Codes and Cache-memory |
| title_full | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| title_fullStr | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| title_full_unstemmed | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| title_short | Эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| title_sort | эвристический алгоритм оптимизации размещения микрокоманд в композиционном микропрограммном устройстве управления с разделением кодов и кэш-памятью |
| topic | Алгоритмическое и программное обеспечение интеллектуальных систем |
| topic_facet | Алгоритмическое и программное обеспечение интеллектуальных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6350 |
| work_keys_str_mv | AT babakovrm évrističeskiialgoritmoptimizaciirazmeŝeniâmikrokomandvkompozicionnommikroprogrammnomustroistveupravleniâsrazdeleniemkodovikéšpamâtʹû AT barkalovaa évrističeskiialgoritmoptimizaciirazmeŝeniâmikrokomandvkompozicionnommikroprogrammnomustroistveupravleniâsrazdeleniemkodovikéšpamâtʹû AT kovalevsa évrističeskiialgoritmoptimizaciirazmeŝeniâmikrokomandvkompozicionnommikroprogrammnomustroistveupravleniâsrazdeleniemkodovikéšpamâtʹû AT nikolaenkodv évrističeskiialgoritmoptimizaciirazmeŝeniâmikrokomandvkompozicionnommikroprogrammnomustroistveupravleniâsrazdeleniemkodovikéšpamâtʹû AT babakovrm evrističniialgoritmoptimízacíírozmíŝennâmíkrokomandvkompozicíinomumíkroprogramnomupristroíkeruvannâízrozpodílomkodívtakešpamâttû AT barkalovaa evrističniialgoritmoptimízacíírozmíŝennâmíkrokomandvkompozicíinomumíkroprogramnomupristroíkeruvannâízrozpodílomkodívtakešpamâttû AT kovalevsa evrističniialgoritmoptimízacíírozmíŝennâmíkrokomandvkompozicíinomumíkroprogramnomupristroíkeruvannâízrozpodílomkodívtakešpamâttû AT nikolaenkodv evrističniialgoritmoptimízacíírozmíŝennâmíkrokomandvkompozicíinomumíkroprogramnomupristroíkeruvannâízrozpodílomkodívtakešpamâttû AT babakovrm theheuristicalgorithmofoptimizationofplacementofmicroinstructionsincompositionalmicroprogramcontrolunitwithdivisionofcodesandcachememory AT barkalovaa theheuristicalgorithmofoptimizationofplacementofmicroinstructionsincompositionalmicroprogramcontrolunitwithdivisionofcodesandcachememory AT kovalevsa theheuristicalgorithmofoptimizationofplacementofmicroinstructionsincompositionalmicroprogramcontrolunitwithdivisionofcodesandcachememory AT nikolaenkodv theheuristicalgorithmofoptimizationofplacementofmicroinstructionsincompositionalmicroprogramcontrolunitwithdivisionofcodesandcachememory |