УДК 681.324

 

Р.М. Бабаков, И.В. Ярош, И.О. Вавринюк

Донецкий национальный технический университет, г. Донецк

кафедра систем искусственного интеллекта

 

МОДЕЛИРОВАНИЕ РАБОТЫ КЭШ-ПАМЯТИ

В СОСТАВЕ ЦИФРОВОГО УСТРОЙСТВА УПРАВЛЕНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ

 

Аннотация

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

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

 

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

 

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

 

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

 

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

-      определить перечень параметров модуля кэш-памяти, влияющих на величину эффективности;

-      получить аналитические выражения для определения эффективности;

-      сформулировать основные требования к программной модели.

 

Решение задачи и результаты исследований.

Кэш-память используется для хранения последовательностей микрокоманд, которые могут формироваться композиционным микропрограммным устройством управления (КМУУ) в ближайшее время. Статистический анализ работы современных компьютеров показывает, что около 90% всех данных, запрашиваемых вычислительным устройством, обычно находятся в кэш-памяти. Эта величина называется коэффициентом или вероятностью кэш-попадания.

Поскольку кэш-память работает быстрее, чем управляющая память, строящаяся в элементном базисе ПЗУ, можно определить среднее время ожидания всей системы памяти (среднее время доступа к памяти относительно комбинационной части КМУУ).

Введем следующие обозначения:

–           P_h – вероятность кэш-попаданий;

–           t_УП – время доступа к управляющей памяти;

–           t_c – время поиска в кэш-памяти и выбор требуемых данных в случае кэш-попадания;

–           t_m – время доступа к данным в случае кэш-промаха; при этом t_m=t_УП+t_п, где  t_п – так называемое время потерь при кэш-промахе, затрачиваемое на поиск запрашиваемых данных в кэш-памяти и помещение данных из управляющей памяти в кэш.

Тогда среднее время t_E ожидания системы памяти, включающей в себя кэш-память, определяется как

                                               .                                                          (1)

Из выражения (1) следует, что для достижения высокой скорости доступа, близкой к скорости доступа кэш-памяти, потребуется частота попаданий порядка 90%.

Другой способ оценки эффективности использования кэш-памяти состоит в определении того, насколько кэш-память повышает скорость доступа к системе памяти. Полагая, что в общем случае t_c < t_УП < t_m, эффективность использования кэш-памяти  E (выигрыш в скорости доступа к данным в системе с кэш-памятью по сравнению с системой без кэш-памяти) можно определить как отношение t_УП к t_E:

                                    .                                       (2)

Проанализируем выражение (2).

1) Зависимость E(P_h) нелинейно возрастает с увеличением P_h и наоборот.

2) Если t_m®t_УП, то в случае кэш-промаха цикл доступа равен по времени циклу обращения в системе без кэш-памяти. Тогда выражение (2) можно преобразовать следующим образом:

 .        (3)

Выражение (3) наглядно показывает, что при t_УП=t_m значение E>1 при любом P_h>0, то есть имеется постоянный выигрыш в быстродействии. Поскольку t_m=t_УП+t_п, то очевидным является стремление уменьшить t_п с целью максимального приближения t_m к t_УП.

3) Если t_УП>>t_c, то при P_h >0,9 имеем многократный выигрыш E. Например, при t_УП=200 нс, t_c=10 нс и P_h=0.9 выигрыш составит 6.9, то есть почти 700%.

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

–           увеличение вероятности кэш-попаданий P_h;

–           снижение времени потерь при кэш-промахе t_п;

–           уменьшение времени доступа к кэш-памяти t_c.

В выражении (2) величины t­_с и t_п определяются элементной базой и функциональной организацией аппаратуры. Конкретные значения этих величин можно определить, зная времена и порядок срабатывания электронных компонентов схем кэш-памяти и кэш-контроллера.

Наиболее сложно определить значение вероятности кэш-попаданий P_h, поскольку эта величина зависит как от выбранных характеристик кэш-памяти, так и от реализуемого КМУУ алгоритма управления. При этом величина P_h может изменяться на всем диапазоне вероятности – от 0 до 1 – и тем самым существенно влиять на эффективность использования кэш-памяти в КМУУ.

Если для величин t­_с и t_m можно легко получить точные значения, то даже приблизительное определение значения P_h является затруднительным, поскольку ситуации кэш-попаданий и кэш-промахов не являются очевидными из заданной микропрограммы и характеристик кэш-памяти.

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

Исходными данными для определения вероятности кэш-попаданий P_h будем считать:

–         граф-схему алгоритма управления, интерпретируемого схемой КМУУ;

–         вероятности переходов по логическим условиям, анализируемым в ГСА;

–         адресацию микрокоманд, определяющую расположение микрокоманд в адресном пространстве управляющей памяти;

–         число строк и слов в кэш-памяти.

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

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

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

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

Таким образом, сформулируем основные требования к разрабатываемой модели:

1. Использование в качестве исходных данных значений следующей информации:

– микропрограмма, соответствующая заданному алгоритму управления;

– значения вероятностей логических условий;

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

2. Моделирование процесса функционирования КМУУ с кэш-памятью со сбором статистической информации о ситуациях кэш-попаданий и кэш-промахов.

3. Аналитическое определение эффективности различных архитектур кэш-памяти для заданного алгоритма управления.

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

 

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

 

Список литературы

1.         Баркалов А.А. Синтез устройств управления на программируемых логических устройствах / А.А. Баркалов. – Донецк: ДонНТУ, 2002. –262 с.

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

3.         Бабаков Р.М. Организация композиционных микропрограммных устройств управления с кэш-памятью / С.А. Ковалев, Р.М. Бабаков // Вісник східноукраїнського національного університету ім. Володимира Даля. – 2002. – №8. – С. 123-126.

4.         Бабаков Р.М. Кэш-память микрокоманд в композиционных микропрограммных устройствах управления / А.А. Баркалов, С.А. Ковалев, Р.М. Бабаков // Зб. наукових праць ДНТУ. Серія “Інформатика, кібернетика та обчислювальна техніка”. Вип. 70. – Донецьк: ДонДТУ, 2003. – С. 90-97.

5.        Бабаков Р.М. Эвристический подход к оптимизации работы кэш-памяти в композиционном микропрограммном устройстве управления / С.А. Ковалев, И.И. Агаркова, Р.М. Бабаков, Д.В. Николаенко // Сборник трудов XVIII международной научно-технической конференции «Машиностроение и техносфера XXI века», г. Севастополь, 12-17 сентября 2011 г. В 4-х томах. – Донецк: ДонНТУ, 2011. Т. 2. – С. 57-61.