Организация кэш-памяти современных процессоров

Федеральное агентство по образованию

Государственное образовательное  учреждение

высшего профессионального образования

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра прикладной математики

КУРСОВАЯ РАБОТА

По дисциплине: «Архитектура ЭВМ»

На тему: «Организация кэш-памяти современных процессоров»

Выполнил: студент группы ММ-313 Тюкавкина Н.С.

Дата сдачи: ____________________

Работа защищена с оценкой: ____________________

Руководитель: Лепинин Е.Ф. ______________

ЧЕЛЯБИНСК 2008

АННОТАЦИЯ

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

СОДЕРЖАНИЕ

Введение 3

1. Соответствие между строками кэша и блоками оперативной памяти 7
2. Функция прямого отображения 8
3. Ассоциативная функция отображения 10
4. Секционированная ассоциативная функция отображения 12
5. Алгоритм замены строк кэша 14
6. Целостность информации в кэше и оперативной памяти 16
7. Размер блока 19
8. Кэширование в современных процессорах 21
9. Управление кэшированием 26
10. Кэш трасс 35
11. Общая организация и способ хранения трасс в кэше 38
12. Сравнение с альтернативной организацией кэша инструкций 42

Заключение 46

Список литературы 47

ВВЕДЕНИЕ

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

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

Основные характеристики кэш-памяти представлены в таблице №1.

Таблица №1: функциональные характеристики блоков кэш-памяти

1. СООТВЕТСТВИЕ МЕЖДУ СТРОКАМИ КЭША И БЛОКАМИ ОПЕРАТИВНОЙ ПАМЯТИ

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

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

• объем кэша 64 Кбайт;
• размер блока, которым обмениваются кэш и оперативная память, 4 байт; это означает, что кэш состоит из 16К =214 строк по 4 байт в каждой;
• объем оперативной памяти 16 Мбайт, т.е. длина кода адреса – 24 бит

Таким образом, с точки зрения обмена информацией с кэшем оперативная память состоит из 4М блоков по 4 байт в каждом.

Простейший вариант функции  отображения – прямое отображение (direct mapping). При таком способе за каждым блоком оперативной памяти «закрепляется» фиксированная строка кэша. Схема на рис. 4.17 поясняет общий принцип прямого отображения. Для определения номера строки кэша i используется простое соотношение: i =j mod m, где j – номер блока в оперативной памяти; m – общее количество строк в кэше.

2. ФУНКЦИЯ ПРЯМОГО ОТОБРАЖЕНИЯ

Функция прямого отображения, использующая в качестве исходной информации адрес слова, довольно просто реализуется. Схема поиска информации в кэше рассматривает переданный процессором код адреса слова как состоящий из трех полей. Младшие w бит идентифицируют слово (в нашем случае – байт, поскольку длина слова равна 1 байт) внутри блока оперативной памяти. Старшие s бит определяют один из 2^s блоков в оперативной памяти. В схемах управления кэшем эти s бит разбиваются на два поля: старшие s-r бит – поле тэга, а младшие r бит – поле номера строки, которое однозначно задает одну из m=2^r строк кэша. Результат реализации такой функции отображения следующий:

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

На рисунке №2 показано, как будет выглядеть применение прямой функции отображения в той системе, параметры которой мы оговорили в начале этого раздела. В системе, взятой для примера, m=16К=2¹⁴ и i=о mod 2¹⁴. При таких параметрах функция прямого отражения дает следующие результаты:

Важно, что все блоки  оперативной памяти, назначенные  одной и той же строке кэша, имеют  разные значения тэга – значения восьми старших двоичных (двух шестнадцатеричных) разрядов адреса. Например, блоки с адресами 000000, 010000, ..., FF0000 имеют, соответственно, значения тэгов 00, 01, ..., FF.

Рассмотрим, как будет  выполняться операция чтения при  использовании в кэше прямой функции  отображения. От процессора поступает  запрос байта, сопровождаемый 24-разрядным кодом адреса. Из него извлекается 14-разрядное поле номера строки, которое однозначно указывает, в какой строке кэша следует искать затребованный байт. Если значение в поле тэга переданного адреса (старшие 8 разрядов) совпадает со значением в поле тэга этой строки, то младшие 2 разряда кода адреса указывают, какой из четырех байтов этой строки следует передать процессору. В противном случае старшие 22 разряда кода адреса (поле тэга плюс поле номера строки) используются для обращения к оперативной памяти и, дополненные нулями в двух младших разрядах, задают начальный адрес блока размером в 4 байт.

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

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

3. АССОЦИАТИВНАЯ  ФУНКЦИЯ ОТОБРАЖЕНИЯ

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

На рисунке №6 схематически представлено соответствие между содержимым строк кэша и блоков оперативной памяти при реализации ассоциативной функции отображения. Код адреса в оперативной памяти рассматривается как состоящий из двух полей: 22-разрядного поля тэга и 2-разрядного поля номера байта. Таким образом, в каждой строке кэша нужно хранить помимо блока данных длиной в 4 байт (32 бит) еще и 22-разрядный код тэга этого блока. Так 24-разрядному адресу 16339С будет соответствовать 22-разрядный код тэга 058СЕ7 (коды представляются в шестнадцатеричной нотации). Как формируется такой код, легко проследить, если воспользоваться двоичной нотацией:

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

4. СЕКЦИОНИРОВАННАЯ  АССОЦИАТИВНАЯ ФУНКЦИЯ ОТОБРАЖЕНИЯ

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

m=v*k, i = j mod v, где

i – номер секции кэша;

j – номер блока в оперативной памяти;

m – общее количество строк в кэше.

В каждой секции используется ассоциативная функция отображения, и блок B_j может быть передан в любую строку секции i. Схемы управления блока кэш-памяти анализируют три поля в составе кода адреса, поступившего от процессора: тэг, номер секции, и номер слова (байта). Поле номера секции имеет длину d разрядов, и задает одну из v=2^d секций. Поле тэга длиной s разрядов совместно с полем номера секции определяют один из 2^s блоков в оперативной памяти, который может быть помещен в любую строку этой секции. На рисунке №5 приведена схема управления блоком кэш-памяти, в котором использована секционированная ассоциативная функция отображения. При использовании чисто ассоциативной функции поле тэга в строке кэша имело довольно большую длину и значение тэга из кода адреса, полученного от процессора, нужно было сравнить со значениями в полях тэга всех строк кэша. При использовании секционированной ассоциативной функции поле тэга в коде адреса имеет несколько меньшую длину, и при анализе адреса это поле нужно сравнивать только с полями тэгов строк одной секции (обычно их бывает 2, 4 или 8).

На рисунке №5 схематически представлено соответствие между содержимым строк кэша и блоков оперативной памяти при реализации секционированной ассоциативной функции отображения. Каждая секция включает две строки кэша и, следовательно, номер секции задается 13-разрядным двоичным числом. Блоки в оперативной памяти, номера которых, взятые по модулю 2¹³, совпадают с номером секции, будут отображаться на строки этой секции кэша. Так блоки 000000, 00A000, ..., FF4000 будут отображаться на строки секции 0. Каждый из этих блоков может быть помещен в любую из двух строк секции 0. Важно, что ни один из двух блоков, которые отображаются на одну и ту же секцию, не имеют одинаковых кодов тэга. При выполнении операции чтения 13-разрядный номер секции определяет, какую из двухстрочных секций кэша следует анализировать на предмет того, не содержится ли в ней искомый блок. При этом анализируются поля тэгов обеих строк секции.

Если v=m, k=1, то секционированная ассоциативная функция сводится к прямой функции отображения, а при v=1, k=m секционированная ассоциативная функция сводится к чистой ассоциативной. Разделение кэша на 2-строчные секции (v=m/2, k=2) – самый распространенный вариант использования секционированной ассоциативной функции, который дает наибольший прирост эффективности по сравнению с прямой функцией отображения. Если еще более увеличить размер секции – включить в нее 4 строки (v = m/4, k = 4), – то повышение эффективности кэша будет довольно скромным. Дальнейшее увеличение размера секции оказывает очень незначительное влияние на повышение эффективности.

5. Алгоритм замены строк кэша

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

Возможно, наиболее эффективным  является алгоритм LRU (least recently used), предполагающий выбор той из строк – кандидатов на замену, к которой дольше всего не обращался процессор. Вполне резонно предположить, что процессору скорее понадобится информация из той строки, к которой он недавно обращался, и, следовательно, этот алгоритм обеспечит более эффективное в вероятностном смысле использование кэша. Алгоритм LRU реализуется довольно просто, если в кэше использована 2-строчная секционированная ассоциативная функция отображения. В состав строки включается специальный бит USE. При каждом обращении к строке в ее бите USE устанавливается 1, а в бите USE второй строки той же секции устанавливается 0. Когда возникает необходимость записать в эту секцию новый блок, выбирается строка, бит USE которой равен 0.

Другой вариант – алгоритм FIFO (first in, first out), который реализует принцип «первым вошел – первым вышел». При этом новый блок записывается в ту из строк секции, в которую текущая информация была записана раньше, чем в другие. Алгоритм FIFO несложно реализовать, используя принцип циклического буфера.

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

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

6. Целостность информации в кэше и оперативной памяти

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

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

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

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

Альтернативный вариант – обратная запись (write back) – минимизирует количество обращений к оперативной памяти. В этом варианте процессор вносит изменения только в содержимое своего кэша. При изменении содержимого определенной строки в специальном бите UPDATE этой строки устанавливается 1. Когда возникает необходимость очистить эту строку для приема нового блока из оперативной памяти, анализируется бит UPDATE. Если этот бит установлен, содержимое строки переписывается в оперативную память. Очевидно, что при та кой политике блок оперативной памяти некоторое время содержит неверную, устаревшую информацию и, следовательно, если к нему в это время обратится модуль ввода-вывода, обращение нужно будет каким-то образом переадресовать кэшу. Реализация такого алгоритма серьезно усложняет компоненты системы, и процедура проверки достоверности данных может стать ее узким местом. Эксперименты показали, что на долю операций записи приходится примерно 15% всех обращений к памяти.

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

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

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