ДонНТУ   Портал магистров

Реферат по теме выпускной работы

Содержание

Введение

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

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

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

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

1. Структурa кэширования в миркопроцессорной системе

Как известно, скорость работы микропроцессора намного превышает скорость работы основной памяти. В виду того, что шина обмена данными не позволяет работать с высокой частотой, такая память должна располагаться рядом с самим микропроцессором. Это накладывает значительные ограничение на объем памяти и существенно увеличивают ее стоимость. Поскольку, в основном, производители выпускают медленную, но дешёвую память с большим объемом оправдано использование многоуровневой памяти.

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

Впервые слово «кэш» в компьютерном контексте было использовано в 1967 году во время подготовки статьи для публикации в журнале «IBM Systems Journal». Статья касалась усовершенствования памяти в разрабатываемой модели 85 из серии IBM System/360. Редактор журнала Лайл Джонсон попросил придумать более описательный термин, нежели «высокоскоростной буфер», но из-за отсутствия идей сам предложил слово «кэш».

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

Иерархия памяти в микропроцессорной системе

Рисунок 1 – Иерархия памяти в микропроцессорной системе

Идея использования быстрой буферной памяти между микропроцессором и основной памятью появилась давно и в IBM System/360 она была использована уже не впервые. В советских ЭВМ функцию кэша выполняла память на сверхбыстрых регистрах, которые так же размещались между основной памятью и процессором примером являются машины БЭСМ [2]. Кэш использует небольшую, очень быструю память (обычно типа SRAM).

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

Структурная схема расположение кэш-памяти

Рисунок 2 – Структурная схема расположение кэш-памяти

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

Работа кэш-памяти

Рисунок 3 – Работа кэш-памяти
(Анімація 12 кадрів, 7 циклів повторення, 14.2 Кб)

Основу всех систем кэш-памяти составляет принцип локальности. Это когда при последовательном обращении к памяти в течении определенного времени используется только ее часть. Идея состоит в том что при обращении к какому-либо слову оно вместе с соседними переносится в кэш-память, что позволит быстро к ним обратится при следующем запросе[1].

В настоящее время используется многоуровневая структура кэш-памяти. Как правило, используется три уровня кэш-памяти (L1, L2, L3), при чем кэш-память третьего уровня в массовых процессорах начала использоваться недавно. Кеш-память первого уровня (L1) располагается прямо на кристалле процессора и имеет объем от 16 до 64 Кбайт, но при этом является самой быстрой. Кэш-память второго уровня (L2) располагается в одном корпусе с микропроцессором и имеет объем от 512 Кбайт до 1Мбайта, но при этом она в два три раза медленнее ее. Кэш-память третьего уровня (L3) находится дальше всего от процессора и имеет объем несколько мегабайт и так же является самой медленной кэш-памятью. Кэш-память третьего уровня является общей для ядер микропроцессора. Но все же его скорость, намного выше скорость системной памяти [5],[1]. Примером трех уровневой кэш-памяти можно привести структуру памяти в AMD K10 [4] рис. 4.

Пример многоуровневой кэш-памяти

Рисунок 4 – Пример многоуровневой кэш-памяти

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

Еще кэш-память может быть объединённой (unified cache) или разделенной (split cache). В объединённой хранятся как команды так и инструкции. (U-cache). В разделенной кэш-памяти существует кэш команд (I-cache) и кэш данных (D-cache). Это позволяет производить параллельную обработку данных и команд. В большинстве процессоров разделенной бывает лишь кэш-память первого уровня. А кэш память второго и третьего уровня являются унифицированными. Иногда кэш-память третьего уровня называют T-cache (ternary - третьестепенная). Структура расположения кэш-памяти разных уровней рис. 5.

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

Рисунок 5 – Пример структуры расположения кэш-памяти с тремя уровнями

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

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

Основная памяти и кэш-память делятся на блоки фиксированного размера с учетом принципа локальности [1]. Блоки внутри кэш-памяти обычно называют строками кэша. Строка кэш-памяти состоит из нескольких байтов. Строки нумеруются начиная с нуля. Например если строка кэш памяти 4байта то – нулевая строка это байты с нулевого по третий, вторая строка с четвертого по седьмой и так далее. В любой момент времени в кэш-памяти находится несколько строк [5].

2. Структура учебно-отладочного стенда 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)[8].

Структурная схема стенда

Рисунок 6 – Структурная схема стенда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как следствие, можно рассчитать показатель усредненного времени доступа к данным:

Усредненное время доступа к данным

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

Выводы

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

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

Магистерская работа посвящена актуальной научной задаче исследовать работу кэш-памяти. И разработать модель кэш-контроллера при помощи стенда EV 8031.

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

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

Список источников

  1. Таненбаум Э. Архитектура компьютера / Таненбаум. Э. – Питер, 2010. – 5е издание. – 844с.
  2. Королев Л.Н. Архитектура ЭВМ БЭСМ-6 [Электронный ресурс]. – Режим доступа: http://www.parallel.ru/history/besm6.html
  3. Касперский К. Кэш-память, как она есть [Электронный ресурс]. – Режим доступа: http://www.insidepro.com/kk/008/008r.shtml
  4. Пахомов С. Долгожданные процессоры с микроархитектурой AMD K10/ Пахомов. С. – КомпьютерПресс 10'2007
  5. Гук М.Ю. Апаратные средства IBM PC. Энциклопедия / Гук М.Ю. – Питер 2006. – 1072 с.
  6. Anand Lal Shimpi The Cache Debate, LGA-1156 and the 32nm Future [Электронный ресурс]. – Режим доступа: http://www.anandtech.com/show/2671
  7. Жмакин А.П. Архитектура ЭВМ / Жмакин. А. П. - СПб. – 2006 – С. 259
  8. Учебно-отладочный стенд EV8031/AVR / Техническое описание. Инструкция по эксплуатации.
  9. Учебный-отладочный стенд "EV8031/AVR"[Электронный ресурс]. – Режим доступа: http://opensys.com.ua/Stend/Ev8031