Назначение, концепции и принципы организации кэш-памяти

Определение:

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

Назначение:

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

Концепции:

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

2) Кэш память строится на основе элементов статической памяти SRAM, которая представляет собой триггеры.

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

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

5)эффективность использования кэша опеределяется принципом локальности ссылок. Два вида локальности: пространствнная и временная.

Пространственная локальность: вероятность обращения к слову данных пили выборки команды по следующему адресу больше вероятности обращения к данным по другому адресу.

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

6)Численной оценкой эффективности построения кэш-памяти - процент кэш попаданий.

7)при построении кэш-памяти необходимо выбрать принципы организации .

Принципы организации кэш-памяти:

- принцип отображения блоков ОП на блоки кэш -памяти (стратегии отображения/распределения)

-принцип удаления блоков из кэш-памяти (принцип замещения)

- принцип поддержания актуальности копий блоков кэш-памяти в блоках оп (стратегия обновления ОП)

Стратегии отображения (распределения): прямое отображение, полностью ассоциативное отображение, множественно-ассоциативное отображение, секторированное отображение (распределение секторов) — принципы их реализации и сравнительный анализ.

Стратегии отображения(распределения):

-Прямое отображение (любой блок оп может отображаться только на один конкретный блок кэш-памяти)

-полностью ассоциативное отображение (любой блок оп может отображаться на любой блок кэш-памяти)

-множественно-ассоциативное ( любой блок оп может отображаться на любой блок в кэш-памяти, но внутри конкретного множества)

-секторированное отображение (любой блок оп может отображаться на конкретный блок внутри сектора кэш-памяти. Сам же сектор может быть любым)

Кэш память с прямым отображением.Реализация:

Кэш-память делится на память тегов и память данных. (любой блок оп может отображаться только на один конкретный блок кэш-памяти)

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

Принцип работы кэш-памяти с прямым отображением:

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

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

Достоинства и недостатки:

Простой и недорогой в реализации способ отображения.

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

Кэш память с полностью ассоциативным отображением.Описание:

Любой блок ОП может быть помещен на место любого блока в кэш-памяти.

Такая кэш-память делится на память тегов и память данных.

В адресе оп выделяют два поля - поле тега и поле слова. Поле тега совпадает с адресом блока в оп.

Принцип работы:

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

Поиск происходит по следующей схеме(упрощенная схема):

ITR - записывается тег по которому производится поиск.

TR- теги в кэш памяти

На компораторе они сравниваются, и если совпадение находится, то вырабатывается сигнал Е, разрешающий доступ к регистру данных (DR)

ODR- выходной регистр данных.

Достоинства и недостатки:

Достоинство - гибкость при выборе строки .

Недостаток - использование дорогостоящей ассоциативной памяти.

Кэш память с множественно-ассоциативным отображением.Описание:

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

Принцип работы:

1)При обращении к кэш памяти из памяти тегов выбираются по одному тегу из каждого банка по адресу группы.

2)Далее тег сравнивается с тегом блока на компораторе.

3)При совпадении одного из тегов формируется адрес банка для управления пересылкой данных между регистром данных и памятью через мультиплексор/демультиплексор.

Достоинства:

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

Кэш память с секторированным отображением.Описание:

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

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

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

Принцип работы:

1) при обращении к кэшу проверяется наличие нужного сектора в памяти.

2) если сектор находится, то проверяется бит достоверности на наличие нужного блока в данном секторе.

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

3) если сектор находится, но нет нужного блока, осуществляется пересылка блока из оп в этот сектор кэша и устанавливаются для него биты достоверности.

Основные стратегии замещения блоков в кэш-памяти: RAND, FIFO, LFU, LRU — принципы их реализации и сравнительн анализ. Стратегия Pseudo LRU и принципы ее реализации в кэш-памяти процессоров фирмы Intel.

Стратегии замещения.Множество блоков для замещения:

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

1) для ассоциативной кэш-памяти - на всем множестве блоков

2) для множественно-ассоциативной - среди блоков одного множества

3) для секторированного отображения - среди смножества секторов

Стратегии замещения:

- RAND- случайный выбор

- FIFO - первый вышел, первый ушел

- LFU - наименее частое использование

- LRU - наиболее давно использовавшийся

Реализация стартегий замещений:

1) RAND

кандидат на удаление выбирается случайным образом из допустимого множества блоков.

Реализация:с помощью счечика , содержимое которого инкрементируется с каким-либо периодом.

2) FIFO. удалению подлежит тот блок из допустмого множества, который был раньше помещен в стек.

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

3) LFU - удаляется блок с наименьшей частотой обращений из допустимого множества.

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

4) LRU - удалению подлежит тот блок, к котрому наиболее долго не было обращений.

Реализация:

1. с помощью счетчика. Счетчики инкрементируются через какие то интервалы времени.При обращении к блоку счетчик обнуляется. Кандидат на удаление - тот, у которого наибольшее число в счетчике.

2.с помощью LRU-стека. при каждом обращении ссылка на блок помещается в конец очреди. Кандидат на удаление - тот кто первый в очереди.

LRU стек реализован на автоматной модели с жесткой логикой, т.к сдвиг информации в стеке носит случайный характер. Реализация такого автомата усложняется по мере увеличения числа блоков в множестве кэша, т.к число состояний автомата = n!, где N число блоков.

Сравнение:

LRU считается наиболее эффективным алгоритмом.

RAND- наиболее простой алгоритм. Сложность реализации возрастает от стартегии RAND к стратегии LRU. Однако на практике RAND лишь незначительно снижает эффективность использвоания кэша по сравнению с остальными статегиями.

При большом объеме кэш-памяти процентное соотношение кэш-промохов для RAND и LRU практически схожи.

Pseudo LRU в кэш памяти процессора INTEL:

Заключается в том, что кандидат на удаление - предпоследний блок.

В процессорах INTEL для каждого множества блоков используются три бита LRU- b0 b1 b2.

Выбор кандидата на удаление среди блоков L0, L1,L2,L3 производится следующим образом:

1 ) каждый раз устанавливаются биты в зависмости от последовательности обращения к блокам. Для этого:

1- проверяет к какой паре было последнее обращение. Если L0 L1, то b0=1, иначе 0

2- Далее проверяется к какому блоку именно было обращение внутри пары.

Если b0=1 ,то проверяется внутри пары L0,L1. Если к L0 то b1=1, иначе 0.

3- Если b0=0, то проверяется внутри пары L2 L3. Если L2, то b2 =1, иначе 0.

2) выбирается кандидат на удаление по текущему состоянию битов LRU.

если b0=0,b1=0 то кандидат - L0

если b0=0,b1=1, то кандидат - L1

если b0=1, b2=0, то кандидат - L2

если b0=1,b2=1, то кандидат - L3

Пример:

У нас были последовательные обращения к блокам L0 L2 L3 L1.

Тогда состояния битов меняются следующим образом: 1 1 X, 0 1 1, 010,100

Соответственно кандидат в конце по состоянию бита - L2

Поиск по сайту: