Кэширование данных

Содержание.

Введение……………………………………………………………………………………….1

Описание  устройства. Принципы кэширования………………………………………...5

Основные  режимы работы…………………………………………………………………9

Алгоритм  и принцип действия…………………………………………………………...13

Недостатки  работы устройства при  кэшировании……………………………………15

Предложения по повышению эффективности  доступа к данным…………………..16

Список  используемой литературы………………………………………………………20

Введение.

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

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

Иерархия  ЗУ

     Диаграмма кэша памяти ЦПУ:

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

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

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

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

     Если  кэш ограничен в объёме, то при  промахе может быть принято решение  отбросить некоторую запись для  освобождения пространства. Для выбора отбрасываемой записи используется так называемый алгоритм вытеснения (см. алгоритмы вытеснения).

     При модификации элементов данных в  кэше выполняется их обновление в  основной памяти. Задержка во времени  между модификацией данных в кэше и обновлением основной памяти управляется  так называемой политикой записи.

     В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.

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

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

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

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

     Архитектура современных 32-разрядных процессоров  включает ряд средств кэширования  памяти: два уровня кэша инструкций и данных (L1 Cache и L2 Cache), буферы ассоциативной  трансляции (TLB) блока страничной переадресации и буферы записи. Эти средства в разных вариациях (на кристалле, картридже процессора или на системной плате) представлены в системах с процессорами 486, Pentium и Р6. В процессоре 80386 (Intel) имелся только TLB, a кэш-память, устанавливаемая на системной плате, не имела поддержки со стороны процессора.

1. Описание  устройства. Принципы кэширования.

     Основная  память компьютеров реализуется  на относительно медленной динамической памяти (DRAM), обращение к ней приводит к простою процессора — появляются такты ожидания (wait states). Статическая память (SRAM), построенная, как и процессор, на триггерных ячейках, по своей природе способна догнать современные процессоры по быстродействию и сделать ненужными такты ожидания (или хотя бы сократить их количество). Разумным компромиссом для построения экономичных и производительных систем явился иерархический способ организации оперативной памяти. Идея заключается в сочетании основной памяти большого объема на DRAM с относительно небольшой кэш-памятью на быстродействующих микросхемах SRAM.

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

     При каждом обращении к памяти контроллер кэш-памяти по каталогу проверяет, есть ли действительная копия затребованных данных в кэше. Если она там есть, то это случай кэш-попадания (cache hit), и данные берутся из кэш-памяти. Если действительной копии там нет, это случай кэш-промаха (cache miss), и данные берутся из основной памяти. В соответствии с алгоритмом кэширования блок данных, считанный из основной памяти, при определенных условиях заместит один из блоков кэша. От интеллектуальности алгоритма замещения зависит процент попаданий и, следовательно, эффективность кэширования. Поиск блока в списке должен производиться достаточно быстро, чтобы «задумчивостью» в принятии решения не свести на нет выигрыш от применения быстродействующей памяти. Обращение к основной памяти может начинаться одновременно с поиском в каталоге, а в случае попадания — прерываться (архитектура Look aside). Это экономит время, но лишние обращения к основной памяти ведут к увеличению энергопотребления. Другой вариант: обращение к внешней памяти начинается только после фиксации промаха (архитектура Look Through), при этом теряется по крайней мере один такт процессора, зато экономится энергия.

     В современных компьютерах кэш  обычно строится по двухуровневой схеме. Первичный кэш (L1 Cache) встроен во все процессоры класса 486 и старше; это внутренний кэш. Объем этого кэша невелик (8-32 Кбайт). Для повышения производительности для данных и команд часто используется раздельный кэш (так называемая Гарвардская архитектура — противоположность Принстонской, использующей общую память для команд и данных). Вторичный кэш (L2 Cache) для процессоров 486 и Pentium является внешним (устанавливается на системной плате), а у Р6 располагается в одной упаковке с ядром и подключается к специальной внутренней шине процессора.

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

     Контроллер  кэша оперирует строками (cache line) фиксированной длины. Строка может хранить копию блока основной памяти, размер которого, естественно, совпадает с длиной строки. С каждой строкой кэша связана информация об адресе скопированного в нее блока основной памяти и об ее состоянии. Строка может быть действительной (valid) — это означает, что в текущий момент времени она достоверно отражает соответствующий блок основной памяти, или недействительной. Информация о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы), и о ее состоянии называется тегом (tag) и хранится в связанной с данной строкой ячейке специальной памяти тегов (tag RAM). В операциях обмена с основной памятью обычно строка участвует целиком (несекторированный кэш), для процессоров 486 и старше длина строки совпадает с объемом данных, передаваемых за один пакетный цикл (для 486 это 4х4=16 байт, для Pentium 4x8=32 байт). Возможен и вариант секторированного (sectored) кэша, при котором одна строка содержит несколько смежных ячеек — секторов, размер которых соответствует минимальной порции обмена данных кэша с основной памятью. При этом в записи каталога, соответствующей каждой строке, должны храниться биты действительности для каждого сектора данной строки. Секторирование позволяет экономить память, необходимую для хранения каталога при увеличении объема кэша, поскольку большее количество бит каталога отводится под тег и выгоднее использовать дополнительные биты действительности, чем увеличивать глубину индекса (количество элементов) каталога.

     Строки  кэша под отображение блока памяти выделяются при промахах операций чтения, в Р6 строки заполняются и при записи. Запись блока, не имеющего копии в кэше, производится в основную память (для повышения быстродействия запись может производиться через буфер отложенной записи). Поведение кэш-контроллера при операции записи в память, когда копия затребованной области находится в некоторой строке кэша, определяется его алгоритмом, или политикой записи (Write Policy). Существуют две основные политики записи данных из кэша в основную память: сквозная запись WT (Write Through) и обратная запись WB (Write Back).

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

     Политика WB позволяет уменьшить количество операций записи на шине основной памяти. Если блок памяти, в который должна производиться запись, отображен в кэше, то физическая запись сначала будет произведена в эту действительную строку кэша, и она будет отмечена как грязная (dirty), или модифицированная, то есть требующая выгрузки в основную память. Только после этой выгрузки (записи в основную память) строка станет чистой (clean), и ее можно будет использовать для кэширования других блоков без потери целостности данных. В основную память данные переписываются только целой строкой. Эта выгрузка контроллером может откладываться до наступления крайней необходимости (обращение к кэшированной памяти другим абонентом, замещение в кэше новыми данными) или выполняться в свободное время после модификации всей строки. Данный алгоритм сложнее в реализации, но существенно эффективнее, чем WT. Поддержка системной платой кэширования с обратной записью требует обработки дополнительных интерфейсных сигналов для выгрузки модифицированных строк в основную память, если к этой области производится обращение со стороны таких контроллеров шины, как другие процессоры, графические адаптеры, контроллеры дисков, сетевые адаптеры и т. п.