Кэш – память и принципы ее организации, страница 5

Рассмотрим подробнее конкретный пример четырехвходовой  множественно-ассоциативной    кэш-памяти объемом  8 Кбайт (рис.IV.4), которая использовалась в процессорах i486.

Блок                     0000h

Блок                     0010h

Блок                     0020h

Блок                     0030h

               Рис.IV.4. Организация множественно-ассоциативной кэш-памяти

                                                          объемом   8 Кбайт.

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

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

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

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

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

Поясним суть метода псевдо-LRU более подробно. Обозначим строки во множестве (наборе) через L3,L2,L1,L0. Каждому множеству  строк соответствует трехразрядный двоичный код с битами B2,B1,B0, которые модифицируются при каждом попадании (cachehit) и заполнении строки следующим образом:

·  Если обращение во множестве было к строке L0 или L1, то бит B0 устанавливается в состояние 1, а при обращении к строке L2 или L3, 

     бит B0 сбрасывается в 0;

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

·  Если последнее обращение в паре L2, L3 было к строке L2, то бит B2 устанавливается в состояние 1, а при обращении к строке L3 бит B2 сбрасывается в 0.

Таким образом, в зависимости от временной последовательности обращения к строкам каждого множества, в блоке LRU данного множества формируется определенный код B2, B1, B0. Выбор заменяемой строки (когда все строки во множестве достоверны) определяется содержимым бит B2, B1, B0 следующим образом:

·  при   00Х – заменяется строка L0;

·  при   01Х – заменяется строка L1;

·  при   1Х0 – заменяется строка L2;

·  при   1Х1 – заменяется строка L3;

где Х – любое значение: 0 или 1.

Заметим, что кроме алгоритма Pseudo-LRU иногда используется алгоритм замещения по принципу FIFO (First-In, First-Out), при котором для замещения выбирается та строка, к которой было первое обращение в данном множестве строк. Использовался, также, принцип случайного (random) выбора строки для замещения. Эти алгоритмы проще в реализации, но не так эффективны.

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

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

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