УДК

ПОДСИСТЕМА МОДЕЛИРОВАНИЯ КЭШИРОВАНИЯ ДАННЫХ С ПОМОЩЬЮ УЧЕБНО-ОТЛАДОЧНОГО СТЕНДА EV8031/AVR

Лебединский А.А., Самощенко А.В.

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

кафедра компьютерной инженерии

E-mail: lebedinskiy@mail.ua

Аннотация

Лебединский А.А., Самощенко А.В. Подсистема моделирования кэширования данных с помощью учебно-отладочного стенда EV8031/AVR. Рассмотрена структура учебно-отладочного стенда EV8031/AVR. По результатам анализа структуры и работы кэш-памяти промоделирован один из алгоритмов кэширования.

Введение

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

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

В данном случае использование стенда позволяет детально изучить структуру кэш-памяти прямого отображения и алгоритм работы MSI.

Структура учебно-отладочного стенда EV8031/AVR

Учебно-отладочный стенд EV8031/AVR предназначен для работы с микроконтроллерами AT89C51, AT89C52, AT90S8515 (ATmega8515) (корпус DIP-40). Структурная схема стенда приведена на рис 1. Стенд оснащен ОЗУ емкостью 32 Кб, из которых 16 Кб память данных и 16 Кб память команд. Стенд имеет последовательный порт (RS-232), интерфейс RS-485, матричную клавиатуру 3*4, дискретные кнопки (линии INT0, INT1). По каналу I2C можно получить доступ к таймеру реального времени (DS1307), интегральному цифровому датчику температуры (DS1621) и EEPROM (AT24C02). Также возможна статическая четырехразрядная индикация. К стенду может быть подключен жидкокристаллический индикатор 4*10 (BC1004A).

Имеется возможность подключения к стенду плат расширений EV8031/АN или EV8031/АU. Данные платы расширения позволяют измерять аналоговые и частотные сигналы, регулировать работу вентилятора и измерять температуру. На платах расширения находится восьмиразрядный цифро-аналоговый преобразователь (AD7801), динамический и знакосинтезирующий индикаторы, генератор с фиксированной и переменной частотой, динамик, N-кодер, датчик Холла (SS4433), датчик температуры (ТMP03), интегральный аналого-цифровой преобразователь (AD7813).

После перепрошивки микросхемы ALTERA появляется возможность активации платы расширения EV8031/RF, которая позволяет работать с модулями GSM SIM300 или SIM900 (держатель SIM карты, аудио-разъём Jack-3.5 мм) , инфракрасным приемо-передатчиком (ТFDU4100), протоколом однопроводной связи (разъём 1-Wire (DS9094), идентификатор (DS1990A)). Также на плате расширения присутствуют GPS модуль SSF-1919P, гибридный модуль на 433Мгц частотной модуляции (передатчик RTFQ1, приёмник RRFQ1).

Рис. 1. Структурная схема стенда

Исследование структуры кэш-памяти

Кэш состоит из строк, скомпонованных в множества. Каждая строка сопоставлена (ассоциирована) элементу данных. Каждая строка имеет идентификатор, указывающий на соответствие между элементами данных в кэше и их копиями в основной памяти.

В микропроцессорах широкое применение получила четырехканальная ассоциативная по множеству кэш-память (рис.2). Каждый из каналов имеет 128 16-байтных строк кэш-памяти (cache-line), что в целом определяет размер блока данных 8Кбайт. Строка содержит данные из 16 соседних байтовых адресов памяти, начиная с адреса, кратного 16.

Рис.2 Структура внутренней 4-канальной кэш-памяти

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

Успех или неудача операции обращения к кэш памяти называется кэш-попаданием (hit ratio) или кэш-промахом (miss ratio) соответственно. Эти случаи напрямую зависят от того, какие именно данные находятся в текущий момент в кэш-памяти. Известным фактом является то, что программы обращаются к памяти упорядоченно. Зачастую с высокой вероятностью запрашиваемый адрес по значению близок с предыдущим активным адресом. Подавляющее большинство команд и данных, которые используются в обычной программе, вызываются из последовательной области памяти. Так же известно, что большая часть времени работы программ занимает выполнение однотипных зацикленных наборов команд.

В настоящее время типовой является многоуровневая структура кэш-памяти. Как правило, кэш-память реализуется в трех структурных уровнях (L1, L2, L3). Кэш-память первого уровня (L1) располагается непосредственно на кристалле процессора, имеет разделенное (split cache) функциональное назначение, сопоставлена исполнительному ядру и имеет объем от 16 до 64 Кбайт. В разделенной кэш-памяти существует кэш команд (I-cache) и кэш данных (D-cache), что позволяет распараллелить обработку данных и команд. Кэш-память второго уровня (L2) также располагается в одном корпусе с микропроцессором и имеет объем от 512 Кбайт до 1Мбайта, но при этом она в несколько раз медленнее кэша первого уровня. Зачастую кэш-память второго уровня унифицирована (unified cache) и может быть сопоставлена отдельным ядрам. Кэш-память третьего уровня (L3) удалена от исполнительных блоков процессора, имеет объем несколько мегабайт и является самой медленной кэш-памятью. Кэш-память третьего уровня является общей для ядер микропроцессора и располагается с ними в единой интегральной схеме. Структура подсистемы кэширования в микропроцессорах Intel Core i7 показана на рис.3.

Рис.3 Пример подсистемы кэширования в 4-ядерном процессоре

Моделирование работы кэш-памяти при помощи стенда EV8031/AVR

Выполнено моделирования работы кэш-памяти прямого отображения (одноканальной кэш-памяти). Кэшируемая область памяти разбивается на блоки, размер которых равен объему кэш-памяти. Адрес строки кэш-памяти, на которую отображается блок из основной памяти, однозначно определяется выражением: i =j mod m, где m — общее число строк в кэш-памяти.

Кэш-память прямого отображения – простой тип кэш-памяти, эффективно используемый в кэш-команд (I-cache).

Достоинствами кэш-памяти прямого отображения являются:

• Высокая скорость определения факта попадание/промах,

• Простота поиска строки-кандидата на удаление, т.к. присутствует жесткая привязка к адресам.

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

В модели реализована память размером 16 байт и кэш-память размером строки 1 байт с четырьмя строками. Таким образом, нулевой строке кэш-памяти могут соответствовать байты памяти с номерами 0,4,8,12; первой строке с номерами 1,5,9,13 и т.д. При этом в кэш-памяти помимо данных хранится тег, который указывает на ячейку памяти, сопоставленную в текущий момент активной строке кэш-памяти. Структура кэш-памяти прямого отображения показана на рис 4.

Рис.4 Структура кэш-памяти прямого отображения

Запись строки в кэш-память сопровождается записью в память тэгов номера соответствующей страницы основной памяти.

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

В модели реализован режим обратной записи в кэш-память (WB – Write Back). Для указания на факт изменения строки без ее копирования в основную память используется признак модификации M (Modified). Строка с признаком M не соответствует содержимому сопоставленной ячейки основной памяти. Признак сбрасывается в ноль при первоначальной загрузке строки в кэш-память и устанавливается в единицу при записи обновленной строки. Таким образом, для обеспечения когерентности данных перезаписывать в основную память необходимо только строки с единичным значением признака модификации. Режим обратной записи рационален, но допускает временное различие данных кэша и основной памяти.

При чтении из памяти в кэш строка помечается признаком S (Shared), что указывает на полное соответствие содержимому памяти. Строки кэш-памяти, которые не содержат достоверную информацию, помечаются признаком I (Invalid), а обращение к такой строке приводит к кэш-промаху.

Для указания каждого признака отводится по одному биту, тега – 3 бита. Структура одной строки кэш-памяти представлена на рис. 5.

Рис. 5. Структура одной строки кэш-памяти

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

Модель позволяет оценить эффективность работы кэш-памяти прямого отображения с обратной записью, для чего рассчитывается коэффициент кэш-попаданий. В качестве исходных показателей принимается количество кэш-попаданий и общее количество обращений к слову в памяти. Например, к слову с адресом А было 15 обращений, из них 10 раз имел факт кэш-попаданий. Таким образом, коэффициент будет равен 10/15=0,66, что указывает на 66% случаев кэш-попаданий.

Как следствие, можно рассчитать показатель усредненного времени доступа к данным: D = с + (1-h) m, где:

с – время доступа к кэш-памяти;

m – время доступа к основной памяти;

h – коэффициент кэш-попаданий (соответственно (1-h) - коэффициент кэш-промахов).

Предположим, что время срабатывания кэш-памяти 2 мкс, а время обращения к основной памяти 200мкс, при этом коэффициент кэш-промахов равен 3%. Следовательно, среднее время доступа к данным будет равняться 2 + 200 * 0,03 = 8 мкс.

Выводы

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

Литература

1. Таненбаум, Э. Архитектура компьютера [Текст] / Э. Таненбаум // Питер. – 2010 – С. 330-334.

2. Жмакин, А.П. Архитектура ЭВМ [Текст] / А. П. Жмакин // СПб. – 2006 – С. 259, 290-294.

3. Касперский К. Подсистема кэш-памяти, как она есть [Electronic resourse] / К. Касперский // Интернет-ресурс – Режим доступа: www/ URL: http://www.insidepro.com/kk/008/008r.shtml. - Загл. с экрана.