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

Размещено на http://www.allbest.ru/

Введение

Впервые слово «кэш» в компьютерном контексте было использовано в 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. Поддержка системной платой кэширования с обратной записью требует обработки дополнительных интерфейсных сигналов для выгрузки модифицированных строк в основную память, если к этой области производится обращение со стороны таких контроллеров шины, как другие процессоры, графические адаптеры, контроллеры дисков, сетевые адаптеры и т. п.

В зависимости от способа определения взаимного соответствия строки кэша и области основной памяти различают три архитектуры кэш-памяти: кэш прямого отображения (direct-mapped cache), полностью ассоциативный кэш (fully associative cache) и их комбинация -- частично- или наборно-ассоциативный кэш (set-associative cache).

2. Основные режимы работы

2.1 Кэш прямого отображения

Рис. 2. Кэш прямого отображения.

В кэш-памяти прямого отображения адрес памяти, по которому происходит обращение, однозначно определяет строку кэша, в которой может находиться требуемый блок. Принцип работы такого кэша поясним на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт -- типичный кэш системной платы для Pentium. Структуру памяти в такой системе иллюстрирует рис. 2.

Кэшируемая основная память условно разбивается на страницы (в данном случае 256), размер которых совпадает с размером кэш-памяти (256 Кбайт). Кэш-память (и условно страницы основной памяти) делится на строки (256К / 32 = 8К строк). Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы кэшируемой памяти только соответствующую ей строку (на рисунке они находятся на одном горизонтальном уровне). Поскольку объем основной памяти много больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса (смещением внутри страницы). Одна строка в определенный момент может, естественно, содержать копию только одного из этих блоков. Номер (адрес) строки в кэш-памяти называется индексом (index). Тег несет информацию о том, какой именно блок занимает данную строку (то есть старшая часть адреса или номер страницы). Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти. Кроме адресной части тега с каждой строкой кэша связаны биты признаков действительности и модифицированности данных.

В начале каждого обращения к кэшируемой памяти контроллер первым делом считывает ячейку каталога с заданным индексом, сравнивает биты адреса тега со старшими битами адреса памяти и анализирует признак действительности. Этот анализ выполняется в специальном цикле слежения (snoop cycle), иногда его называют циклом запроса (inquire). Если в результате анализа выясняется, что требуемый блок не находится в кэше, то генерируется (или продолжается) цикл обращения к основной памяти (случай кэш-промаха). В случае попадания запрос обслуживается кэш-памятью. В случае промаха после считывания основной памяти приемником информации новые данные помещаются в строку кэша (если она чистая), а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных из основной памяти строка переписывается в кэш вся целиком (поскольку признак действительности относится ко всем ее байтам). Если контроллер кэша реализует упреждающее считывание (read ahead), то в последующие свободные циклы шины обновится и следующая строка (если она была чистой). Чтение «про запас» позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.

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

Объем кэшируемой памяти (M_CACHED) при архитектуре прямого отображения определяется объемом кэш-памяти (V_CACHE) и разрядностью памяти тегов (N):

M_CACHED = V_CACHE x 2^N, в нашем случае M_CACHED = 256 Кбайт х 2⁸ = 64 Мбайт.

Иногда в описании кэша прямого отображения фигурирует понятие набор (set), что может сбить с толку. Оно применяется вместо термина строка (line) в секторированном кэше прямого отображения, а сектор тогда называют строкой.

С набором (как и строкой несекторированного кэша) связана информация о теге, относящаяся ко всем элементам набора (строкам или секторам). Кроме того, каждый элемент набора (строка или сектор) имеет собственный бит действительности в кэш-каталоге (рис. 3).

Рис. 3. Секторированный кэш прямого отображения.

2.2 Наборно-ассоциативный кэш

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

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

В простейшем случае каждый блок памяти может помещаться в одну из двух строк (Two Way SetAssociative Cache). Такой кэш должен содержать два банка памяти и тегов (рис. 4).

Рис. 4. Двухканальный наборно-ассоциативный кэш.

Номер набора (индекс), в котором может отображаться затребованный блок данных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый блок, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. Кроме того, с каждым набором должен быть связан признак, определяющий строку набора, подлежащую замещению новым блоком данных в случае кэш-промаха (на рис. 4 в ее сторону указывает стрелка). Кандидатом на замещение обычно выбирается строка, к которой дольше всего не обращались (алгоритм LRU -- Least Recently Used). При относительно большом количестве каналов (строк в наборе) прибегают к некоторому упрощению -- алгоритм PseudoLRU для четырех строк (Four Way Set Associative Cache) позволяет принимать решения, используя всего 3 бита. Возможно также применение алгоритма замещения FIFO (первым вошел -- первым и вышел) или даже случайного (random) замещения, что проще, но менее эффективно.

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

2.3 Ассоциативный кэш

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

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

3.1 Алгоритмы замещения данных

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

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

Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used).

Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. В таблице показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма.

Таблица. Сравнение долей промахов для алгоритма LRU и случайного алгоритма замещения при нескольких размерах кэша и разных ассоциативностях при размере блока 16 байт

3.2 Алгоритмы псевдо-LRU

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

Обозначим строки в множестве через L0, L1, L2 и L3. Каждому множеству в блоке LRU соответствуют три бита В0, В1 и В2, которые модифицируются при каждом попадании и заполнении следующим образом:

-- если последнее обращение в паре L0--L1 было к строке L0, то бит В1 устанавливается в состояние 1, а при обращении к строке L1 бит В1 сбрасывается в 0;

-- если последнее обращение в паре L2--L3 было к строке L2, то бит В2 устанавливается в состояние 1, а при обращении к строке L3 бит В2 сбрасывается в 0. Выбор заменяемой строки (когда все строки в множестве достоверны) определяет содержимое бит В0, В1 и В2:

Таблица

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

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

вычислительный машина кэширование

Недостатки рассмотрим на примере трех видов процессоров: Intel, AMD, IBM. Большинство недостатков процессора P-4 являются следствием нововведений, направленных на достижение высокой производительности -- повышенной тактовой частоты и увеличенной длины конвейера, а также спекулятивного характера многих действий и оптимизации выполнения «типичных» операций в ущерб «нетипичным». Основными недостатками являются:

· острая проблема алиасинга при выборке данных из L1-кэша и, как следствие, значительные потери на реплей (в первоначальном процессоре P-4);

· половинная частота запуска скалярных операций SSE;

· неэффективная реализация некоторых операций сдвига (всех сдвигов в процессоре P-4, сдвигов вправо и циклических в 64-битном режиме в процессоре P-4E);

· высокая латентность инструкций, работающих с флагом переноса CF (ADC, SBB);

· большая длина конвейера непредсказанного перехода;

· недостаточная эффективность Т-кэша для плохо структурированных кодов;

· малый размер L1-кэша и высокая латентность доступа к L2-кэшу.

Архитектуре процессора K8 (AMD) имеется и ряд недостатков, часть из которых обусловлена базовыми ограничениями микроархитектуры:

· статическое разбиение потока МОПов на группы по 3 элемента с привязкой очередей и функциональных устройств ALU/AGU к позициям этих элементов;

· слабая система предсказания переходов, использующая устаревшие алгоритмы;

· недостаточно совершенная аппаратная предвыборка из памяти;

· отсутствие механизмов переупорядочения обращений к памяти;

· взаимно эксклюзивная организация кэшей, ограничивающая скорость выборки из L2-кэша и увеличивающая время доступа;

· недостаточная ассоциативность L1-кэшей, снижающая их эффективность.

В микроархитектуре PPC970 к основным ограничениям и недостаткам можно отнести:

· статическое разбиение потока МОПов на группы по 4-5 элементов с привязкой очередей и функциональных устройств к позициям этих элементов;

· наличие множества ограничительных условий, снижающих число МОПов в формируемой группе (на выходе из декодера);

· недостаточно эффективная реализация L1-кэшей, имеющих низкий уровень ассоциативности и слишком большой размер блока;

· завышенное время выполнения предсказанного перехода (3 такта против 2 тактов у других процессоров);

· высокая латентность выполнения целочисленных операций (2 такта) и операций с плавающей точкой (6 тактов);

· недостаточная пропускная способность памяти из-за ограниченной скорости шины.

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

В современных процессорах имеются различные средства, позволяющие повысить эффективность доступа к данным в памяти и снизить потери на ожидание их прихода, а также прочие задержки и затраты на организацию этого доступа. Наиболее важными из этих средств являются механизмы предвыборки из памяти. В каждом из рассматриваемых процессоров реализовано два таких механизма -- программная предвыборка (software prefetch), и автоматическая аппаратная предвыборка (hardware prefetch).

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

Существуют различные варианты инструкций предвыборки -- считывание из памяти в L2-кэш, считывание из памяти или из L2-кэша в L1-кэш, считывание блока для его последующей модификации, либо для одноразового использования. В процессоре P-4 реализована предвыборка только в L2-кэш.

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

Наиболее совершенные механизмы программной и аппаратной предвыборки реализованы в новом процессоре P8 (Intel Core).

Ещё один механизм работы с памятью связан с особенностями загрузки и выгрузки в условиях внеочередного исполнения. В связи с тем, что операция может считаться корректно выполненной только к моменту ухода в отставку и не ранее, чем будет отставлены все предшествующие операции, физическая запись в кэши или в память не может быть произведена до этого момента. По этой причине все результаты выгрузки (записи) в память накапливаются в специальном буфере упорядочения обращений к памяти MOB (Memory Order Buffer). Физическая запись данных из этого буфера в кэш производится только в момент отставки соответствующей инструкции. Если операция загрузки (чтения) из памяти адресует элемент данных, который оказался в этом буфере, то он считывается непосредственно из буфера.

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

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

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

В заключение рассмотрим ещё один микроархитектурный механизм, который связан с вычислением адресов для обращений в память -- работу с аппаратным стеком. Адрес вершины аппаратного стека хранится в регистре ESP. Изменение этого регистра может происходить как неявно, при помещении или удалении данных из стека (инструкции PUSH и POP) либо при входе или выходе в подпрограмму (инструкции CALL и RET), так и явно, в обычной целочисленной инструкции. Традиционно инструкции, использующие регистр ESP и неявно изменяющие его, преобразовывались декодером в два МОПа, один из которых производил содержательное действие, а другой -- выполнял операцию сложения или вычитания для регистра ESP.

В процессорах P-M, P-M2 и P8 введён специальный механизм под названием «Dedicated Stack Engine». Этот механизм отслеживает (на этапе декодирования инструкций) текущее положение вершины стека и заменяет в порождаемых МОПах адресацию данных по «меняющемуся» регистру ESP на сумму некоторого «постоянного» базового адреса стека и отслеживаемого смещения. Таким образом, отпадает необходимость постоянно модифицировать регистр ESP -- теперь его нужно вычислять только в случае явного использования в качестве операнда или индекса. Благодаря этому исчезают ненужные зависимости между операциями по этому регистру, снижается число МОПов в указанных инструкциях (с двух до одного), повышается эффективность работы декодера и увеличивается общая производительность процессора.

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

вычислительный машина кэширование

Гук М., Аппаратные средства IBM PC, Энциклопедия - СПб: ПитерКом, 1999. - 816с.: ил.

Э.Танненбаум,Современные операционные системы, СПб: Питер, 2002. - 1024 с.

Григорьев В.А., Микропроцессор i486. Архитектура и программирование (в 4-х книгах). Книга 2. Внутрення архитектура М., Гранал, 1993. - с. 382, ил. 54.

Марголис А., Поиск и устранение неисправностей в персональных компьютерах. - К.: «Диалектика», 1994. - 368с., ил.

Конспект лекций.

Петровский И.И., Прибыльский А.В., Логические ИС КР1533, КР1554. Справочник. Часть 2. «Бином», 1993.

Шульгин О.А. и др., Справочник по цифровым логическим микросхемам, Часть 1 и 2, М.: ИДДК, 1998.

Размещено на Allbest.ru