Alasir Enterprises
Main Page >  Articles >  Принципы работы кэш-памяти  

 
Main Page
 
 
Reviews
 
Articles
 
Software
 
Reference
 
Motley
 
 
About Us
 
 
Принципы работы кэш-памяти

Павел Болотов
 
Дата публикации: 20 апреля 2007
Дата последнего изменения: 20 апреля 2007

Содержание:
in English

 
Ассоциативность

Ассоциативность кэш-памяти является непосредственным показателем её логической сегментации: сколько каналов, столько и сегментов. Другими словами, кэш-память с N-канальной ассоциативностью (N-way set associative) предполагает, что информация, размещённая по некоторому адресу в оперативной памяти, может находиться (кэшироваться) в N местах (строках) этой кэш-памяти. Основополагающим принципом логического сегментирования является тот факт, что в пределах любого отдельно взятого сегмента только одна строка может кэшировать информацию, находящуюся по некоторому адресу в оперативной памяти. Отсюда следует, что если адрес известен, то контроллеру во всём сегменте следует обработать только одну строку. Таким образом, при получении запроса на чтение или запись контроллер опросит нужные строки во всех имеющихся сегментах на предмет наличия (cache hit) или отсутствия (cache miss) информации, соответствующей полученному адресу. Либо все сегменты возвратят сигнал отсутствия, либо за исключением одного, ответившего сигналом наличия. В случае положительного отзыва контроллеру нет необходимости проводить какой-либо дальнейший анализ, достаточно просто довести операцию до конца. Если все сегменты ответили негативно на запрос о чтении информации, то он будет перенаправлен к контроллеру кэш-памяти более низкого уровня и так далее вплоть до контроллера оперативной памяти. Если же запрос был на запись, то контроллеру предстоит задача выбора сегмента, куда будет осуществлена операция. Для этого он анализирует строки-кандидаты, а если точнее, то их биты состояния и прочие вспомогательные, после чего принимает решение согласно одному из нижеследующих популярных алгоритмов:
  • LRU (Least Recently Used, то есть "наименее новый из запрашиваемых") — запись идёт в строку, находящаяся в которой информация запрашивалась в последний раз наиболее давно;
     
  • LRR (Least Recently Replaced, то есть "наименее новый из записанных"), также известный как FIFO (First In, First Out, то есть "первым пришёл, первым ушёл") — вытесняется строка, находящаяся в которой информация характеризуется наиболее старой записью;
     
  • LFU (Least Frequently Used, то есть "наименее часто запрашиваемый") — для записи выбирается строка, находящаяся в которой информация запрашивалась наименее часто;
     
  • Random — запись идёт в произвольно выбираемую строку.

Как можно предположить, более сложные по сравнению с Random алгоритмы являются более эффективными, но используют более сложную обслуживающую логику. LFU предполагает, что каждая строка кэш-памяти снабжена соответствующим счётчиком, обновляемым при каждом удачном запросе. LRU и LRR используют вместо него счётчик времени в той или иной форме, причём LRU требует его обновления при каждом удачном запросе. Random не предполагает каких-либо строчных счётчиков и вполне может быть основан на одном генераторе случайных чисел или чём-то подобном.
 
Существует два частных варианта политики ассоциативности, фактически являющиеся противоположными друг другу. В полностью ассоциативной (fully associative) кэш-памяти информация, находящаяся по некоторому адресу в оперативной памяти, может быть записана в произвольную строку кэш-памяти. В случае кэш-памяти с прямым отображением (direct mapped) эта же информация может быть размещена только в одной из всех имеющихся строк кэш-памяти. Если точнее, то в полноассоциативной модели каждая строка выступает в качестве самостоятельного сегмента, а в модели с прямым отображением имеется только один сегмент на все строки. Отсюда следует, что кэш-память с прямым отображением может быть охарактеризована как таковая с 1-канальной ассоциативностью, а в кэш-памяти с полной ассоциативностью количество каналов равняется количеству строк. Модель с прямым отображением определённо является наиболее быстрой в работе, так как перед контроллером не стоит проблема выбора строки при операции чтения/записи. С другой стороны, эта модель является наименее эффективной в работе, так как при записи у контроллера не будет возможности выбора строки. Таким образом, если два или более адреса постоянно конфликтуют между собой за одну и ту же строку кэш-памяти, это может привести к значительному падению производительности. Логично предположить, что полноассоциативная модель является наиболее эффективной в работе, но в то же время и наиболее медленной. Тем не менее, существуют и промежуточные варианты политики ассоциативности, компромиссные по отношению к быстродействию и эффективности. В частности, 2-, 4- и 8-канальные модели являются наиболее популярными.
 
Нижеследующая схема наглядно демонстрирует разные варианты политики ассоциативности в работе. Имеется некоторая абстрактная модель в составе 8 строк кэш-памяти и физического пространства оперативной памяти, эквивалентного по размеру 64 строкам кэш-памяти. Необходимо записать в кэш 10-ю так называемую строку оперативной памяти (nota bene: все строки номеруются от 0 и по возрастающей, так что у этой будет номер 9). В случае кэш-памяти с прямым отображением она может быть записана только в одно место: 9 mod 8 = 1 (остаток от деления), т. е. строка номер 1 единственного 8-строчного сегмента. Кэш-память с 2-канальной ассоциативностью предоставляет возможность выбора из двух мест: 9 mod 4 = 1, т. е. строка номер 1 любого 4-строчного сегмента. Полноассоциативная кэш-память даёт максимальную свободу выбора: 9 mod 1 = 0, т. е. строка номер 0 любого 1-строчного сегмента, фактически, любая строка. Действия при чтении подобны вышеописанным. В случае кэш-памяти с прямым отображением надлежит опросить строку номер 1, кэш-памяти с 2-канальной ассоциативностью — строки номер 1 и 5, полноассоциативной кэш-памяти — все строки.
 
Cache associativities explained

В реальной жизни полноассоциативная кэш-память встречается, но редко и небольших размеров. Например, в процессорах семейства Cyrix 6x86 имелось 256 байт такой кэш-памяти "нолевого уровня" под названием instruction line buffer, предназначавшегося исключительно для команд. Она поддерживалась двухпортовой U-cache размером в 16Кб (6x86 и 6x86L) или 64Кб (6x86MX и 6x86MII). Основным предназначением этой необычно малой кэш-памяти было уменьшение нагрузки на U-cache и минимизация простоев процессора при чрезмерном заполнении U-cache данными. Часто полноассоциативную схему применяют при проектировке TLB (о которых речь пойдёт позже), кэшей адресов переходов, буферов ввода/вывода и т. д. Как правило, ассоциативности I-cache и D-cache низки (обычно 2 или 4 канала), так как увеличение их числа приводит к увеличению задержек доступа, что серьёзным образом отражается на производительности. В качестве некоторой компенсации показатель ассоциативности S-cache определяют более высоким (обычно 8 или 16 каналов), так как величина задержек доступа к этой кэш-памяти не так важна. Тем не менее, ассоциативности B-cache типично низки: от прямого отображения для расположенных на материнских платах кэшей до 2- или 4-канальных ассоциативностей для размещённых на процессорных модулях. Причиной этого является сложность построения высокоассоциативных кэшей при использовании стандартных дискретных компонент.
 
<< Предыдущая страница Следующая страница >>

Copyright (c) Болотов Павел Владимирович, 2007. Все права сохранены.
Полная или частичная перепечатка без разрешения автора запрещена.
 
Designed and maintained by Alasir Enterprises, 1999-2007
rhett from alasir.com, walter from alasir.com