Структуры
логических схем управляющих автоматов на программируемых БИС
Баркалов
А.А., Зеленева И.Я., Бабаков Р.М.
Баркалов А.А., Зеленева И.Я., Бабаков Р.М.
Структуры логических схем управляющих автоматов на программируемых БИС. / Зб.
наукових праць ДДТУ. Серія “Інформатика, кібернетика та обчислювальна техніка”.
Вип. 6. – Донецьк: ДонДТУ, 1999. – С.
208-211.
3.1. Определение эффективности
использования кэш-памяти в КМУУ
Кэш-память используется для хранения последовательностей микрокоманд, которые могут формироваться КМУУ в ближайшее время. Статистический анализ работы современных компьютеров показывает, что около 90% всех данных, запрашиваемых вычислительным устройством, обычно находятся в кэш-памяти. Эта величина называется коэффициентом или вероятностью кэш-попадания [81, 115].
Поскольку кэш-память работает быстрее, чем управляющая память, то можно определить среднее время ожидания всей системы памяти (среднее время доступа к памяти относительно комбинационной части КМУУ).
Введем
следующие обозначения:
– Ph – вероятность кэш-попаданий;
– tУП – время доступа к управляющей памяти;
– tc – время поиска в кэш-памяти и выбор требуемых данных в случае кэш-попадания;
– tm – время доступа к данным в случае кэш-промаха; при этом tm=tУП+tп, где tп – так называемое время потерь при кэш-промахе, затрачиваемое на поиск запрашиваемых данных в кэш-памяти и помещение данных из управляющей памяти в кэш.
Тогда среднее время tE ожидания системы памяти, включающей в себя кэш-память, определяется как [79, 81]
Из
(3.1) следует, что для достижения высокой скорости доступа, близкой к скорости
доступа кэш-памяти, потребуется частота попаданий порядка 90%.
Другой способ оценки эффективности использования кэш-памяти состоит в определении того, насколько кэш-память повышает скорость доступа к системе памяти. Полагая, что в общем случае tc < tУП < tm, эффективность использования кэш-памяти E (выигрыш в скорости доступа к данным в системе с кэш-памятью по сравнению с системой без кэш-памяти) можно определить как отношение tУП к tE:
Проанализируем формулу (3.2).
1) Зависимость E(Ph) нелинейно возрастает с увеличением Ph и наоборот.
2) Если tm®tУП, то в случае кэш-промаха цикл доступа равен по времени циклу обращения в системе без кэш-памяти. Тогда формулу (3.2) можно преобразовать следующим образом:
Формула (3.3) наглядно показывает, что при tУП=tm значение E>1 при любом Ph >0, то есть имеется постоянный выигрыш в быстродействии. Поскольку tm=tУП+tп, то очевидным является стремление уменьшить tп с целью максимального приближения tm к tУП.
3) Если tУП>>tc, то при Ph >0,9 имеем многократный выигрыш E. Например, при tУП=200 нс, tc=10 нс и Ph=0.9 выигрыш составит 6.9, то есть почти 700%.
На основании вышесказанного можно сделать вывод, что для увеличения выигрыша в быстродействии в системе с кэш-памятью по сравнению с системой без кэш-памяти необходимы:
– увеличение вероятности кэш-попаданий Ph;
– снижение времени потерь при кэш-промахе tп;
– уменьшение времени доступа к кэш-памяти tc.
В формуле (3.2) величины tс и tп определяются элементной базой и функциональной организацией аппаратуры. Конкретные значения этих величин можно определить, зная времена и порядок срабатывания электронных компонентов схем кэш-памяти и кэш-контроллера (см. раздел 2).
Наиболее сложно определить значение вероятности кэш-попаданий Ph, поскольку эта величина зависит как от выбранных характеристик кэш-памяти, так и от реализуемого КМУУ алгоритма управления. При этом величина Ph может изменяться на всем диапазоне вероятности – от 0 до 1 – и тем самым фундаментально влиять на эффективность использования кэш-памяти в КМУУ.
Если для величин tс и tm можно легко получить точные значения, то даже приблизительное определение значения Ph является затруднительным, поскольку ситуации кэш-попаданий и кэш-промахов не являются очевидными из заданной ГСА и характеристик кэш-памяти.
Рассмотрим предлагаемый метод определения вероятности кэш-попаданий для КМУУ с кэш-памятью с прямым отображением и кэш-памятью полностью ассоциативного типа.
Исходными данными для определения вероятности кэш-попаданий Ph будем считать:
– граф-схему
реализуемого алгоритма;
– вероятности переходов по логическим условиям, анализируемым в ГСА;
– адресацию микрокоманд, определяющую расположение микрокоманд в адресном пространстве УП;
– число строк и слов в кэш-памяти.
Граф-схему алгоритма будем считать преобразованной для реализации схемой УУ с естественной адресацией микрокоманд. Также будем считать, что первой и последней вершинами в ГСА всегда являются операторные вершины (при их отсутствии они должны быть добавлены искусственно). Это условие необходимо для установления точек начала и конца выполнения алгоритма управления.
Вероятности переходов логических условий мы считаем известными потому, что эти значения могут зависеть не только от результатов выполнения микрокоманд, но и от внешних факторов (например, от датчиков). Эти значения не могут быть получены аналитически, а лишь опытным путем в процессе функционирования КМУУ, реализующего рассматриваемый алгоритм, в реальных условиях.
Адреса микрокоманд и размеры кэш-памяти являются теми факторами, изменение которых может привести к увеличению или уменьшению вероятности кэш-попаданий для заданного алгоритма. В работе рассматривается метод определения вероятности кэш-попаданий при заданных адресах микрокоманд. Начальное задание адресов микрокоманд может быть вызвано различными причинами, например, заранее отлаженным алгоритмом со сложными микропрограммными переходами или реализованным автоматом с «жесткой» логикой.
Содержимое операционных микрокоманд (ОМК) на этапе определения вероятности кэш-попаданий не имеет значения. Действия, выполняемые в ОМК, либо никак не влияют на процесс выполнения алгоритма, либо влияют на вероятности переходов ЛУ, которые уже считаются заданными. Поэтому алгоритм, анализируемый с применением методов, разработанных в данной главе, принимает абстрактный характер.
Для определения значения вероятности кэш-попаданий Ph можно предложить два способа: экспериментальный и аналитический.
Экспериментальный способ определения вероятности кэш-попаданий заключается в построении программной модели КМУУ с кэш-памятью с прямым отображением с целью сбора статистической информации о количестве кэш-попаданий и кэш-промахов в процессе многократного выполнения алгоритма. Недостатком экспериментального метода является ограниченная точность, зависящая от заранее заданного числа повторений эксперимента. Кроме того, время, необходимое для многократного выполнения алгоритма, может сильно зависеть от значений вероятностей некоторых ЛУ, поскольку некоторые участки алгоритма могут образовывать длительные циклы (по этой же причине некоторые участки алгоритма могут вообще не быть промоделированы). Отсюда следует, что с увеличением сложности алгоритма время его моделирования возрастает в непропорциональной зависимости от количества микрокоманд и переходов между ОЛЦ.
Аналитический способ позволяет получить точное значение вероятности кэш-попаданий. При этом учитываются все микрокоманды и связи алгоритма, а время расчета зависит лишь от числа микрокоманд и связей между ними и не зависит от значений вероятностей переходов логических условий.
В настоящее время существующие аналитические способы определения вероятности кэш-попаданий алгоритма основываются либо на эмпирически выведенных аппроксимированных зависимостях [50], либо на методах, представляющих собой статистическую обработку результатов экспериментов [55]. Отсутствие точных методов определения вероятности кэш-попаданий объясняется преимущественно тем, что большинство вычислительных систем являются универсальными, то есть могут решать широкий круг задач, для которых подбор абсолютно оптимальных характеристик кэш-памяти затруднителен. Однако при жесткой ориентации внутренней структуры композиционного микропрограммного устройства управления на реализацию конкретного алгоритма возникает необходимость в разработке точных аналитических методов определения вероятности кэш-попаданий для заданного алгоритма, что позволит выбрать наиболее оптимальные с точки зрения быстродействия характеристики кэш-памяти в КМУУ при некотором увеличении стоимости схемы устройства.