Автореферат
на тему магистерской работы: «Разработка и исследование композиционных микропрограммных устройств
управления с кэш-памятью»
Введение
В настоящее время при разработке электронных устройств используется широкий спектр программируемых БИС – ПЗУ, ПЛМ, ПЛИС. Этот базис находит применение в системах вычислительной техники и цифровой автоматики, позволяя значительно улучшить такие характеристики приборов, как надежность, быстродействие, энергопотребление, габариты и др. Однако высокая сложность этого базиса вызывает необходимость в разработке эффективных структур проектируемых устройств и формальных методов их синтеза.
В основе современных цифровых систем находится принцип микропрограммного управления, предполагающий наличие в системе управляющего автомата, координирующего работу всех ее блоков. Рост сложности элементного базиса и алгоритмов управления требует разработки новых структур и алгоритмов синтеза управляющих автоматов.
Управляющий автомат может быть реализован как композиция автоматов с «жёсткой» и «программируемой» логикой. Такие автоматы были предложены А.А. Баркаловым и названы композиционными микропрограммными устройствами управления (КМУУ). В КМУУ достигается минимально возможная ёмкость управляющей памяти и максимальное быстродействие. Управляющая память обычно реализуется на постоянном запоминающем устройстве (ПЗУ), обладающем низким быстродействием относительно других узлов схемы. При этом актуальной является проблема увеличения быстродействия КМУУ за счет уменьшения времени, затрачиваемого на выборку микрокоманд. Один из путей решения этой задачи – введение в структуру КМУУ кэш-памяти, реализуемой на быстрой статической памяти и предназначенной для временного хранения микрокоманд, использовавшихся на протяжении нескольких последних тактов работы устройства.
Магистерская работа посвящена решению актуальной научной задачи разработки структур и методов оценки эффективности композиционных микропрограммных устройств управления, ориентированных на увеличение быстродействия схемы при реализации узлов КМУУ в базисе программируемых БИС.
Цель и задачи исследований
Целью работы является увеличение быстродействия композиционных микропрограммных устройств управления за счет уменьшения среднего времени доступа к управляющей памяти.
Основные задачи исследований. Для достижения поставленной цели в процессе исследований необходимо:
1. Выполнить анализ: основных архитектур кэш-памяти, используемых в современных вычислительных устройствах; современного элементного базиса, используемого при синтезе микропрограммных устройств управления; современных методов оптимизации композиционных микропрограммных устройств управления.
2. Разработать структурные и функциональные схемы КМУУ с кэш-памятью с прямым отображением и кэш-памятью полностью ассоциативного типа.
3. Разработать методы оценки эффективности использования кэш-памяти в КМУУ.
4. Исследовать разработанные структуры КМУУ с кэш-памятью с целью определения области их эффективного применения.
Научная новизна
Научная новизна определяется следующими положениями:
1. Впервые разработаны структуры и функциональные схемы композиционных микропрограммных устройств управления с кэш-памятью микрокоманд, обладающие более высоким быстродействием по сравнению с ранее известными.
2. Впервые разработаны аналитические методы определения точного значения вероятности кэш-попаданий по граф-схеме алгоритма для композиционных микропрограммных устройств управления с кэш-памятью полностью ассоциативного типа с использованием алгоритма замещения Random.
3. Получены аналитические зависимости эффективности использования кэш-памяти в композиционных микропрограммных устройствах управления от характеристик граф-схемы алгоритма управления, типа кэш-памяти и элементного базиса.
Практическая значимость
Практическая значимость работы состоит в разработке программной имитационно-аналитической модели, реализующей разработанные методы аналитического определения значения вероятности кэш-попаданий для КМУУ с кэш-памятью с прямым отображением и полностью ассоциативного типа по граф-схеме алгоритма, а также в определении области эффективного применения кэш-памяти в КМУУ. Полученные в работе результаты реализованы в виде методик синтеза композиционных микропрограммных устройств управления с улучшенными характеристиками.
Обзор существующих
исследований и разработок
В диссертационной работе Р.М. Бабакова (Научный руководитель Ковалёв С.А.) были разработаны структуры логических схем композиционных микропрограммных устройств управления с кэш-памятью микрокоманд и методы оценки их эффективности при реализации в базисе программируемых БИС.
В процессе исследований решены следующие задачи:
1. Выполнен анализ: современных архитектур кэш-памяти и их особенностей; современного элементного базиса, используемого при синтезе схем устройств управления; методов оптимизации композиционных микропрограммных устройств управления на программируемых БИС.
2. Разработаны структуры и функциональные схемы композиционных микропрограммных устройств управления с кэш-памятью с прямым отображением и кэш-памятью полностью ассоциативного типа.
3. Разработаны методы аналитического определения вероятности кэш-попаданий для заданной граф-схемы алгоритма управления и характеристик кэш-памяти. Методы разработаны для кэш-памяти с прямым отображением и полностью ассоциативного типа.
4. Получены аналитические оценки увеличения быстродействия при использовании кэш-памяти в композиционных микропрограммных устройствах управления. Применение кэш-памяти микрокоманд в композиционных микропрограммных устройствах управления приводит в общем случае к увеличению среднего быстродействия схемы устройства в 2-5 раз и выше в зависимости от характеристик элементного базиса и структуры реализуемого алгоритма управления. Предложенные в работе методы аналитического определения значения вероятности кэш-попаданий по граф-схеме алгоритма позволяют получить результат в общем случае в несколько раз быстрее, чем при использовании экспериментальных методов.
5. Разработан алгоритм выбора оптимальных характеристик кэш-памяти, позволяющий для заданного алгоритма управления подобрать количество строк и размер строки кэш-памяти, при которых обеспечиваются максимально возможная вероятность кэш-попаданий и увеличение быстродействия. Данный алгоритм может быть использован при синтезе схем композиционных микропрограммных устройств управления с кэш-памятью микрокоманд, обладающих максимально возможным быстродействием при заданном алгоритме управления и допустимой емкости кэш-памяти.
Перечень нерешенных
проблем и вопросов
Кэш-память используется для хранения последовательностей микрокоманд, которые могут формироваться КМУУ в ближайшее время. Статистический анализ работы современных компьютеров показывает, что около 90% всех данных, запрашиваемых вычислительным устройством, обычно находятся в кэш-памяти. Эта величина называется коэффициентом или вероятностью кэш-попадания [1, 2].
Для определения значения вероятности кэш-попаданий можно предложить два способа: экспериментальный и аналитический.
Экспериментальный способ определения вероятности кэш-попаданий заключается в построении программной модели КМУУ с кэш-памятью с прямым отображением с целью сбора статистической информации о количестве кэш-попаданий и кэш-промахов в процессе многократного выполнения алгоритма. Недостатком экспериментального метода является ограниченная точность, зависящая от заранее заданного числа повторений эксперимента. Кроме того, время, необходимое для многократного выполнения алгоритма, может сильно зависеть от значений вероятностей некоторых ЛУ, поскольку некоторые участки алгоритма могут образовывать длительные циклы (по этой же причине некоторые участки алгоритма могут вообще не быть промоделированы). Отсюда следует, что с увеличением сложности алгоритма время его моделирования возрастает в непропорциональной зависимости от количества микрокоманд и переходов между ОЛЦ.
Аналитический способ позволяет получить точное значение вероятности кэш-попаданий. При этом учитываются все микрокоманды и связи алгоритма, а время расчета зависит лишь от числа микрокоманд и связей между ними и не зависит от значений вероятностей переходов логических условий. При жесткой ориентации внутренней структуры композиционного микропрограммного устройства управления на реализацию конкретного алгоритма возникает необходимость в разработке точных аналитических методов определения вероятности кэш-попаданий для заданного алгоритма, что позволит выбрать наиболее оптимальные с точки зрения быстродействия характеристики кэш-памяти в КМУУ при некотором увеличении стоимости схемы устройства.
Как было сказано выше, в настоящее время уже разработаны аналитические методы оценки увеличения быстродействия при использовании кэш-памяти с прямым отображением и кэш-памяти полностью ассоциативного типа в композиционных микропрограммных устройствах управления. В кэш-памяти полностью ассоциативного типа могут использоваться различные алгоритмы замещения, такие как LRU, Random, Timer.
LRU - при очередном кэш-промахе замещается строка, имеющая наименьшее значение в регистре такта обращения.
Random - при очередном кэш-промахе замещается строка, выбранная случайным образом.
Timer - при очередном кэш-промахе замещается строка, с максимальным временем прошедшим с момента обращения.
В диссертационной работе Р.М. Бабакова был разработан аналитический метод оценки увеличения быстродействия при использовании кэш-памяти полностью ассоциативного типа только с использованием алгоритма замещения LRU. Алгоритмы Random и Timer остаются неисследованными.
Текущие и планируемые
результаты
Текущим
результатом магистерской работы является программная модель, реализующая
экспериментальный метод определения эффективности использования кэш-памяти
полностью ассоциативного типа с использованием алгоритма замещения Random. Планируется получить
результаты аналитического метода исследования кэш-памяти полностью
ассоциативного типа с использованием алгоритма замещения Random.
Заключение
В магистерской работе дано решение актуальной научной задачи, важной для промышленности средств цифровой автоматики и вычислительной техники, заключающейся в разработке новых структур логических схем композиционных микропрограммных устройств управления с кэш-памятью микрокоманд и методов оценки их эффективности при реализации в базисе программируемых БИС.
Список источников
1.
Hill Mark Donald. Ascepts of Cache
Memory and Instruction Buffer Performance. – Ph. D. Dissertation, Computer
Science Division (EECS),
2.
Smith A.J. Second Bibliography on
Cache Memories // Computer Architecture News, 19(4):154-182, June 1991.
При написании данного
реферата магистерская работа еще не завершена. Окончательное завершение –
январь 2007 года. Полный текст работы и все материалы по теме могут быть
получены у автора или его руководителя после указанной даты.