Ассоциативная кэш-память. Множественно-ассоциативная кэш-память Иерархическая модель кэш-памяти
· кэш с прямым отображением (размещением);
· полностью ассоциативный кэш;
· множественный ассоциативный кэш или частично-ассоциативный.
Кэш с прямым отображением
(размещением) является самым
простым типом буфера. Адрес памяти однозначно определяет строку
кэша, в которую будет помещен блок информации. При этом предпо-
лагается, что оперативная память разбита на блоки и каждому та-
кому блоку в буфере отводится всего одна строка. Это простой и недорогой в реализации способ отображения. Основной его недостаток – жесткое закрепление за определенными блоками ОП одной строки в кэше. Поэтому, если программа поочередно обращается к словам из двух различных блоков, отображаемых на одну и ту же строку кэш-памяти, постоянно будет происходить обновление данной строки и вероятность попадания будет низкой.
Кэш с полностью ассоциативным отображением позволяет преодолеть недостаток прямого, разрешая загрузку любого блока ОП в любую строку кэш-памяти. Логика управления выделяет в адресе ОП два поля: поле тега и поле слова. Поле тега совпадает с адресом блока ОП. Для проверки наличия копии блока в кэш-памяти, логика управления кэша должна одновременно проверить теги всех строк на совпадение с полем тега адреса. Ассоциативное отображение обеспечивает гибкость при выборе строки для вновь записываемого блока. Принципиальный недостаток этого способа – в необходимости использования дорогой ассоциативной памяти.
Множественно-ассоциативный тип или частично-ассоциативный тип отображения – это один из возможных компромиссов, сочетающий достоинства прямого и ассоциативного способов. Кэш-память (и тегов и данных) разбивается на некоторое количество модулей. Зависимость между модулем и блоками ОП такая же жесткая, как и при прямом отображении. А вот размещение блоков по строкам модуля произвольное и для поиска нужной строки в пределах модуля используется ассоциативный принцип. Этот способ отображения наиболее широко распространен в современных микропроцессорах.
Отображение секторов ОП в кэш-памяти.
Данный тип отображения применяется во всех современных ЭВМ и состоит в том, что вся ОП разбивается на секторы, состоящие из фиксированного числа последовательных блоков. Кэш-память также разбивается на секторы, содержащие такое же количество строк. Расположение блоков в секторе ОП и секторе кэша полностью совпадает. Отображение сектора на кэш-память осуществляется ассоциативно, те любой сектор из ОП может быть помещен в любой сектор кэша. Таким образом, в процессе работы АЛУ обращается в поисках очередной команды к ОП, в результате чего, в кэш загружается(в случае отсутствия там блока, содержащего эту команду), целый сектор информации из ОП, причем по принципу локальности, за счет этого достигается значительное увеличение быстродействия системы.
Иерархическая модель кэш-памяти
Как правило, кэш-память имеет многоуровневую архитектуру. Например, в компьютере с 32 Кбайт внутренней (в ядре ЦП) и 1 Мбайт внешней (в корпусе ЦП или на системной плате) кэш-памяти первая будет считаться кэш-памятью 1-го уровня (L1), а вторая - кэш-памятью 2-го уровня (L2). В современных серверных системах количество уровней кэш-памяти может доходить до четырех, хотя наиболее часто используется двух- или трехуровневая схема.
В некоторых процессорных архитектурах кэш-память 1-го уровня разделена на кэш команд (InstructionCache, I-cache) и кэш данных (DataCache, D-cache), причем необязательно одинаковых размеров. С точки зрения схемотехники проще и дешевле проектировать раздельные I-cache и D-cache: выборку команд проводит I-box, а выборку данных - Е-box и F-box, хотя в обоих случаях задействуются А-box и С-box. Все эти блоки велики, и обеспечить им одновременный и быстрый доступ к одному кэшу проблематично. Кроме того, это неизбежно потребовало бы увеличения количества портов доступа, что также усложняет задачу проектирования.
Так как I-cache и D-cache должны обеспечивать очень низкие задержки при доступе (это справедливо для любого кэша L1), приходится жертвовать их объемом - обычно он составляет от 16 до 32 Кбайт. Ведь чем меньше размер кэша, тем легче добиться низких задержек при доступе.
Кэш-память 2-го уровня, как правило, унифицирована, т. е. может содержать как команды, так и данные. Если она встроена в ядро ЦП, то говорят о S-cache (SecondaryCache, вторичный кэш), в противном случае - о B-cache (BackupCache, резервный кэш). В современных серверных ЦП объем S-cache составляет от одного до нескольких мегабайт, aB-cache - до 64 Мбайт. Если дизайн ЦП предусматривает наличие встроенной кэш-памяти 3-го уровня, то ее именуют T-cache (TernaryCache, третичный кэш). Как правило, каждый последующий уровень кэш-памяти медленнее, но больше предыдущего по объему. Если в системе присутствует B-cache (как последний уровень модели кэш-памяти), то он может контролироваться как ЦП, так и набором системной логики.
Если в момент выполнения некоторой команды в регистрах не окажется данных для нее, то они будут затребованы из ближайшего уровня кэш-памяти, т. е. из D-cache. В случае их отсутствия в D-Cache запрос направляется в S-cache и т. д. В худшем случае данные будут доставлены непосредственно из памяти. Впрочем, возможен и еще более печальный вариант, когда подсистема управления виртуальной памятью операционной системы (ОС) успевает вытеснить их в файл подкачки на жесткий диск. В случае доставки из оперативной памяти потери времени на получение нужных данных могут составлять от десятков до сотен тактов ЦП, а в случае нахождения данных на жестком диске речь уже может идти о миллионах тактов.
Ассоциативность кэш-памяти
Одна из фундаментальных характеристик кэш-памяти - уровень ассоциативности - отображает ее логическую сегментацию. Дело в том, что последовательный перебор всех строк кэша в поисках необходимых данных потребовал бы десятков тактов и свел бы на нет весь выигрыш от использования встроенной в ЦП памяти. Поэтому ячейки ОЗУ жестко привязываются к строкам кэш-памяти (в каждой строке могут быть данные из фиксированного набора адресов), что значительно сокращает время поиска. С каждой ячейкой ОЗУ может быть связано более одной строки кэш-памяти: например, n-канальная ассоциативность (n-waysetassociative) обозначает, что информация по некоторому адресу оперативной памяти может храниться в п мест кэш-памяти.
Выбор места может проводиться по различным алгоритмам, среди которых чаще всего используются принципы замещения LRU (LeastRecentlyUsed, замещается запись, запрошенная в последний раз наиболее давно) и LFU (LeastFrequentlyUsed, запись, наименее часто запрашиваемая), хотя существуют и модификации этих принципов. Например, полностью ассоциативная кэшпамять (fullyassociative), в которой информация, находящаяся по произвольному адресу в оперативной памяти, может быть размещена в произвольной строке. Другой вариант - прямое отображение (directmapping), при котором информация, которая находится по произвольному адресу в оперативной памяти, может быть размещена только в одном месте кэш-памяти. Естественно, этот вариант обеспечивает наибольшее быстродействие, так как при проверке наличия информации контроллеру придется "заглянуть" лишь в одну строку кэша, но и наименее эффективен, поскольку при записи контроллер не будет выбирать "оптимальное" место. При одинаковом объеме кэша схема с полной ассоциативностью будет наименее быстрой, но наиболее эффективной.
Полностью ассоциативный кэш встречается на практике, но, как правило, у него очень небольшой объем. Например, в ЦП Cyrix 6x86 использовалось 256 байт такого кэша для команд перед унифицированным 16-или 64-Кбайт кэшем L1. Часто полноассоциативную схему применяют при проектировании TLB (о них будет рассказано ниже), кэшей адресов переходов, буферов чтения-записи и т. д. Как правило, уровни ассоциативности I-cache и D-cache довольно низки (до четырех каналов) - их увеличение нецелесообразно, поскольку приводит к увеличению задержек доступа и в итоге негативно отражается на производительности. В качестве некоторой компенсации увеличивают ассоциативность S-cache (обычно до 16 каналов), так как задержки при доступе к этому кэшу неважны. Например, согласно результатам исследований часто используемых целочисленных задач, у IntelPentiumIII 16 Кбайт четырехканального D-cache было достаточно для покрытия около 93% запросов, а 16-Кбайт четырехканального I-cache - 99% запросов.
Размер строки и тега кэш-памяти
Немаловажная характеристика кэш-памяти - размер строки. Как правило, на одну строку полагается одна запись адреса (так называемый тег), которая указывает, какому адресу в оперативной памяти соответствует данная линия. Очевидно, что нумерация отдельных байтов нецелесообразна, поскольку в этом случае объем служебной информации в кэше в несколько раз превысит объем самих данных. Поэтому один тег обычно полагается на одну строку, размер которой обычно 32 или 64 байта (реально существующий максимум 1024 байта), и эквивалентен четырем (иногда восьми) разрядностям системной шины данных. Кроме того, каждая строка кэш-памяти сопровождается некоторой информацией для обеспечения отказоустойчивости: одним или несколькими битами контроля четности (parity) или восемью и более байтами обнаружения и коррекции ошибок (ЕСС, ErrorCheckingandCorrecting), хотя в массовых решениях часто не используют ни того, ни другого.
Размер тега кэш-памяти зависит от трех основных факторов: объема кэш-памяти, максимального кэшируемого объема оперативной памяти, а также ассоциативности кэш-памяти. Математически этот размер рассчитывается по формуле:
Stag=log2(Smem*A/Scache),
где Stag - размер одного тега кэш-памяти, в битах; Smem - максимальный кэшируемый объем оперативной памяти, в байтах; Scache - объем кэш-памяти, в байтах; А - ассоциативность кэш-памяти, в каналах.
Отсюда следует, что для системы с 1-Гбайт оперативной памятью и 1-Мбайт кэш-памятью с двухканальной ассоциативностью потребуется 11 бит для каждого тега. Примечательно, что собственно размер строки кэш-памяти никак не влияет на размер тега, но обратно пропорционально влияет на количество тегов. Следует понимать, что размер строки кэш-памяти не имеет смысла делать меньше разрядности системной шины данных, но многократное увеличение размера приведет к чрезмерному засорению кэш-памяти ненужной информацией и излишней нагрузке на системную шину и шину памяти. Кроме того, максимально кэшируемый объем кэш-памяти не обязан соответствовать максимально возможному устанавливаемому объему оперативной памяти в системе. Если возникнет ситуация, когда оперативной памяти окажется больше, чем может быть кэшировано, то в кэш-памяти будет присутствовать информация только из нижнего сегмента оперативной памяти. Именно такой была ситуация с платформой Socket7/Super7. Наборы микросхем для этой платформы позволяли использовать большие объемы оперативной памяти (от 256 Мбайт до 1 Гбайт), в то время как кэшируемый объем часто был ограничен первыми 64 Мбайт (речь идет о B-cache, находящемся на системной плате) по причине использования дешевых 8-бит микросхем теговой SRAM (2 бита из которых резервировалось под указатели действительности и измененности строки). Это приводило к ощутимому падению производительности.
В ассоциативной памяти элементы выбираются не по адресу, а по содержимому. Поясним последнее понятие более подробно. Для памяти с адресной организацией было введено понятие минимальной адресуемой единицы (МАЕ) как порции данных, имеющей индивидуальный адрес. Введем аналогичное понятие для ассоциативной памяти , и будем эту минимальную единицу хранения в ассоциативной памяти называть строкой ассоциативной памяти (СтрАП). Каждая СтрАП содержит два поля: поле тега (англ. tag - ярлык, этикетка, признак) и поле данных. Запрос на чтение к ассоциативной памяти словами можно выразить следующим образом: выбрать строку (строки), у которой (у которых) тег равен заданному значению.
Особо отметим, что при таком запросе возможен один из трех результатов:
- имеется в точности одна строка с заданным тегом;
- имеется несколько строк с заданным тегом;
- нет ни одной строки с заданным тегом.
Поиск записи по признаку - это действие, типичное для обращений к базам данных, и поиск в базе зачастую чвляется ассоциативным поиском. Для выполнения такого поиска следует просмотреть все записи и сравнить заданный тег с тегом каждой записи. Это можно сделать и при использовании для хранения записей обычной адресуемой памяти (и понятно, что это потребует достаточно много времени - пропорционально количеству хранимых записей!). Об ассоциативной памяти говорят тогда, когда ассоциативная выборка данных из памяти поддержана аппаратно. При записи в ассоциативную память элемент данных помещается в СтрАП вместе с присущим этому элементу тегом. Для этого можно использовать любую свободную СтрАП. Рассмотрим разновидности структурной организации КЭШ-памяти или способы отображения оперативной памяти на КЭШ .
Полностью ассоциативный КЭШ
Схема полностью ассоциативного КЭШа представлена на рисунке (см. рисунок ниже).
Опишем алгоритм работы системы с КЭШ-памятью. В начале работы КЭШ-память пуста. При выполнении первой же команды во время выборки ее код, а также еще несколько соседних байтов программного кода, - будут перенесены (медленно) в одну из строк КЭШа, и одновременно старшая часть адреса будет записана в соответствующий тег. Так происходит заполнение КЭШ-строки.
Если следующие выборки возможны из этого участка, они будут сделаны уже из КЭШа (быстро) - "КЭШ-попадание". Если же окажется, что нужного элемента в КЭШе нет, - "КЭШ-промахом". В этом случае обращение происходит к ОЗУ (медленно), и при этом одновременно заполняется очередная КЭШ-строка.
Схема полностью ассоциативной КЭШ-памяти
Обращение к КЭШу происходит следующим образом. После формирования исполнительного адреса его старшие биты, образующие тег, аппаратно (быстро) и одновременно сравниваются с тегами всех КЭШ-строк. При этом возможны только две ситуации из трех, перечисленных ранее: либо все сравнения дадут отрицательный результат (КЭШ-промах), либо положительный результат сравнения будет зафиксирован в точности для одной строки (КЭШ-попадание).
При считывании, если зафиксировано КЭШ-попадание, младшие разряды адреса определяют позицию в КЭШ-строке, начиная с которой следует выбирать байты, а тип операции определяет количество байтов. Очевидно, что если длина элемента данных превышает один байт, то возможны ситуации, когда этот элемент (частями) расположен в двух (или более) разных КЭШ-строках, тогда время на выборку такого элемента увеличится. Противодействовать этому можно, выравнивая операнды и команды по границам КЭШ-строк, что и учитывают при разработке оптимизирующих трансляторов или при ручной оптимизации кода.
Если произошел КЭШ-промах, а в КЭШе нет свободных строк, необходимо заменить одну строку КЭШа на другую строку.
Основная цель стратегии замещения - удерживать в КЭШ-памяти строки, к которым наиболее вероятны обращения в ближайшем будущем, и заменять строки, доступ к которым произойдет в более отдаленном времени или вообще не случится. Очевидно, что оптимальным будет алгоритм, который замещает ту строку, обращение к которой в будущем произойдет позже, чем к любой другой строке-КЭШ.
К сожалению, такое предсказание практически нереализуемо, и приходится привлекать алгоритмы, уступающие оптимальному. Вне зависимости от используемого алгоритма замещения, для достижения высокой скорости он должен быть реализован аппаратными средствами.
Среди множества возможных алгоритмов замещения наиболее распространенными являются четыре, рассматриваемые в порядке уменьшения их относительной эффективности. Любой из них может быть применен в полностью ассоциативном КЭШ.
Наиболее эффективным является алгоритм замещения на основе наиболее давнего использования (LRU - Least Recently Used ), при котором замещается та строка КЭШ-памяти, к которой дольше всего не было обращения. Проводившиеся исследования показали, что алгоритм LRU, который "смотрит" назад, работает достаточно хорошо в сравнении с оптимальным алгоритмом, "смотрящим" вперед.
Наиболее известны два способа аппаратурной реализации этого алгоритма. В первом из них с каждой строкой КЭШ-памяти ассоциируют счетчик. К содержимому всех счетчиков через определенные интервалы времени добавляется единица. При обращении к строке ее счетчик обнуляется. Таким образом, наибольшее число будет в счетчике той строки, к которой дольше всего не было обращений и эта строка - первый кандидат на замещение.
Второй способ реализуется с помощью очереди, куда в порядке заполнения строк КЭШ-памяти заносятся ссылки на эти строки. При каждом обращении к строке ссылка на нее перемещается в конец очереди. В итоге первой в очереди каждый раз оказывается ссылка на строку, к которой дольше всего не было обращений. Именно эта строка прежде всего и заменяется.
Другой возможный алгоритм замещения - алгоритм, работающий по принципу "первый вошел, первый вышел" (FIFO - First In First Out ). Здесь заменяется строка, дольше всего находившаяся в КЭШ-памяти. Алгоритм легко реализуется с помощью рассмотренной ранее очереди, с той лишь разницей, что после обращения к строке положение соответствующей ссылки в очереди не меняется.
Еще один алгоритм - замена наименее часто использовавшейся строки (LFU - Least Frequently Used). Заменяется та строка в КЭШ-памяти, к которой было меньше всего обращений. Принцип можно воплотить на практике, связав каждую строку со счетчиком обращений, к содержимому которого после каждого обращения добавляется единица. Главным претендентом на замещение является строка, счетчик которой содержит наименьшее число.
Простейший алгоритм - произвольный выбор строки для замены. Замещаемая строка выбирается случайным образом. Реализовано это может быть, например, с помощью счетчика, содержимое которого увеличивается на единицу с каждым тактовым импульсом, вне зависимости от того, имело место попадание или промах. Значение в счетчике определяет заменяемую строку.
Кроме тега и байтов данных в КЭШ-строке могут содержаться дополнительные служебные поля, среди которых в первую очередь следует отметить бит достоверности V (от valid - действительный имеющий силу) и бит модификации M (от modify - изменять, модифицировать). При заполнении очередной КЭШ-строки V устанавливается в состояние "достоверно", а M - в состояние "не модифицировано". В случае, если в ходе выполнения программы содержимое данной строки было изменено, переключается бит M, сигнализируя о том, что при замене данной строки ее содержимое следует переписать в ОЗУ. Если по каким-либо причинам произошло изменение копии элемента данной строки, хранимого в другом месте (например в ОЗУ), переключается бит V. При обращении к такой строке будет зафиксирован КЭШ-промах (несмотря на то, что тег совпадает), и обращение произойдет к основному ОЗУ. Кроме того, служебное поле может содержать биты, поддерживающие алгоритм LRU.
Оценка объема оборудования
Типовой объем КЭШ-памяти в современной системе - 8…1024 кбайт, а длина КЭШ-строки 4…32 байт. Дальнейшая оценка делается для значений объема КЭШа 256 кбайт и длины строки 32 байт, что характерно для систем с процессорами Pentium и PentiumPro. Длина тега при этом равна 27 бит, а количество строк в КЭШе составит 256К/ 32=8192. Именно столько цифровых компараторов 27 битных кодов потребуется для реализации вышеописанной структуры.
Приблизительная оценка затрат оборудования для построения цифрового компаратора дает значение 10 транз/бит, а общее количество транзисторов только в блоке компараторов будет равно:
10*27*8192 = 2 211 840,
что приблизительно в полтора раза меньше общего количества транзисторов на кристалле Pentium. Таким образом, ясно, что описанная структура полностью ассоциативной КЭШ-памяти () реализуема только при малом количестве строк в КЭШе, т.е. при малом объеме КЭШа (практически не более 32…64 строк). КЭШ большего объема строят по другой структуре.
Разработчики кэш-памяти столкнулись с проблемой, состоящей в том, что потенциально в кэш-памяти может оказаться любая ячейка огромной основной памяти. Если рабочий набор данных, используемых в программе, достаточно большой, то это означает, что за каждое место в кэш-памяти будут соревноваться многие фрагменты основной памяти. Как ранее уже сообщалось, нередко соотношение между кэш-памятью и основной памятью составляет 1 к 1000.
3.3.1 Ассоциативность
Можно было бы реализовать кэш-память, в которой каждая кэш-строка может хранить копию любой ячейки памяти. Это называется полностью ассоциативной кэш-памятью (fully associative cache ). Чтобы получить доступ к кэш-строке, ядро процессора должно было бы сравнить теги всех до единой кэш-строк с тегом запрашиваемого адреса. Тег должен будет хранить весь адрес, который не будет указываться смещение в кэш-строке (это означает, что значение S, показанное на рисунке в разделе 3.2, будет равно нулю).
Есть кэш-память, которая реализована подобным образом, но взглянуть на размеры кэш-памяти L2, используемой в настоящее время, то видно, что это непрактично. Учтите, что 4 Мб кэш-памяти с кэш-строками размером в 64Б должна иметь 65 536 записей. Чтобы получить адекватную производительность, логические схемы кэш-памяти должны быть в состоянии в течение нескольких циклов выбрать из всех этих записей ту, которая соответствует заданному тегу. Затраты на реализацию такой схемы будут огромными.
Рис.3.5: Схематическое изображение полностью ассоциативной кэш-памяти
Для каждой кэш-строки требуется, чтобы компаратор выполнил сравнение тега большого размера (заметьте, S равно нулю). Буква, стоящая рядом с каждым соединением, обозначает ширину соединения в битах. Если ничего не указано, то ширина соединения равна одному биту. Каждый компаратор должен сравнивать два значения, ширина каждого из которых равна Т бит. Затем, исходя из результата, должно выбираться и стать доступным содержимое соответствующей кэш-строки. Для этого потребуется объединить столько наборов линий данных О, сколько есть сегментов кэш-памяти (cache buckets). Число транзисторов, необходимых для реализации одного компаратора будет большим в частности из-за того, что компаратор должен работать очень быстро. Итеративный компаратор использовать нельзя. Единственный способ сэкономить на количестве компараторов, это снизить их число с помощью итеративного сравнения тегов. Это не подходит по той же самой причине, по которой не подходят итеративные компараторы: на это потребуется слишком много времени.
Полностью ассоциативная кэш-память практична для кэш-памяти малого размера (например, кэш-память TLB в некоторых процессорах Intel является полностью ассоциативной), но эта кэш-память должна быть небольшой - действительно небольшой. Речь идет максимум о нескольких десятках записей.
Для кэш-памяти L1i, L1d и кэш-памяти более высокого уровня необходим другой подход. Все, что можно сделать, это ограничить поиск. В самом крайнем случае каждый тег отображается точно в одну кэш-запись. Расчет прост: для кэш-памяти 4MB/64B с 65 536 записями мы можем напрямую обращаться к каждому элементу и использовать для этого с 6-го по 21-й биты адреса (16 битов). Младшие 6 битов являются индексом кэш-строки.
Рис.3.6: Схематическое изображение кэш-памяти с прямым отображением
Как видно из рисунка 3.6 реализация такой кэш-памяти с прямым отображением (direct-mapped cache ) может быть быстрой и простой. Для нее требуется только один компаратор, один мультиплексор (на этой схеме приведены два, поскольку тег и данные разделены, но это не является строгим конструктивным требованием) и некоторая логическая схема для выбора контента, содержащего действительно допустимые кэш-строки. Компаратор сложный из-за требований, касающихся скорости, но теперь он только один; в результате можно потратить больше усилий, чтобы сделать его более быстрым. Реальная сложность такого подхода заключена в мультиплексорах. Количество транзисторов в простом мультиплексоре растет по закону O(log N), где N является количеством кэш-строк. Это приемлемо, но может получиться медленный мультиплексор, и в этом случае скорость можно увеличить, если потратиться на транзисторы в мультиплексорах и для увеличения скорости распараллелить часть работы. Общее количество транзисторов будет расти медленное в сравнении с ростом размера кэш-памяти, что делает это решение очень привлекательным. Но у такого подхода есть недостаток: он работает только в случае, если адреса, используемые в программе, равномерно распределены относительно битов, используемых для прямого отображения. Если это не так, и это обычно бывает, некоторые кэш-записи используются активно и, поэтому, неоднократно высвобождаются, в то время как другие практически вообще не используются, либо остаются пустыми.
Рис.3.7: Схематическое изображение кэш-памяти с множественной ассоциативностью
Эту проблему можно решить с помощью кэш-памяти с множественной ассоциативностью (set associative ). Кэш-память с множественностью ассоциативностью сочетает в себе черты кэш-памяти с полной ассоциативностью и кэш-памяти с прямым отображением, что позволяет в значительной степени избежать недостатков этих решений. На рис.3.7 показана схема кэш-памяти с множественной ассоциативностью. Память под теги и под данные разделена на наборы, выбор которых осуществляется в соответствие с адресом. Это похоже на кэш-память с прямым отображением. Но вместо того, чтобы для каждого значения из набора использовать отдельный элемент, один и тот же набор используется для кэширования некоторого небольшого количества значений. Теги для всех элементов набора сравниваются параллельно, что похоже на функционирование полностью ассоциативной кэш-памяти.
Результатом является кэш-память, которая достаточно устойчива к промахам из-за неудачного или преднамеренного выбора адресов с одними и теми же номерами наборов в одно и то же время, а размер кэш-памяти не ограничен количеством компараторов, которые могут работать параллельно. Если кэш-память увеличивается (смотрите рисунок), то увеличивается только количество столбцов, а не количество строк. Число строк увеличивается только в том случае, если повышается ассоциативность кэш-памяти. Сегодня процессоры для кэш-памяти L2 используют уровни ассоциативности до 16 и выше. Для кэш-памяти L1 обычно используется уровень, равный 8.
Таблица 3.1: Влияние размера кэш-памяти, ассоциативности и размера кэш-строки
| Размер кэш-памяти L2 |
Ассоциативность | |||||||
|---|---|---|---|---|---|---|---|---|
| Прямое отображение | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512k | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1M | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2M | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8M | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16M | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Если у нас кэш-память 4MB/64B и 8-канальная ассоциативность, то в кэш-памяти у нас будет 8192 наборов и для адресации кэш-наборов потребуется только 13 битов тега. Чтобы определить, какая из записей (если таковая имеется) содержит в кэш-наборе адресуемую кэш-строку, потребуется сравнить 8 тегов. Это можно сделать за очень короткое время. Как видно из практики, в этом смысл есть.
В таблице 3.1 показано количество промахов кэш-памяти L2 для некоторой программы (в данном случае — для компилятора gcc, который, по мнению разработчиков ядра Linux, является наиболее важным бенчмарком) при изменении размера кэш-памяти, размера кэш-строки, а также значения множественной ассоциативности. В разделе 7.2 мы познакомимся с инструментальным средством, предназначенным для моделирования кэш-памяти, которое необходимо для этого теста.
Просто, если это еще не очевидно, взаимосвязь всех этих значений в том, что размер кэш-памяти равен
размер кэш-строки х ассоциативность х количество множеств
Отображение адресов в кэш-память вычисляется как
O = log2 от размера кэш-строки
S = log2 от числа наборов
согласно рисунку в разделе 3.2.
Рис.3.8: Размер кэш-памяти и уровень ассоциативности (CL=32)
Рис. 3.8 делает данные таблицы более понятными. На рисунке приведены данные для кэш-строки фиксированного размера, равного 32 байта. Если посмотреть на цифры для заданного размера кэш-памяти, то видно, что ассоциативность действительно может существенно помочь сократить число промахов кэш-памяти. Для кэш-памяти размером 8 МБ при переходе от прямого отображения на кэш-память с 2-канальной ассоциативностью экономится почти 44% кэш-памяти. В случае, если используется кэш-память со множественной ассоциативностью, то процессор может хранить в кэш-памяти рабочий набор большего размера, чем в случае кэш-памяти с прямым отображением.
В литературе иногда можно прочитать, что введение ассоциативности имеет тот же самый эффект, как удвоение размера кэш-памяти. Это, как это видно для случая перехода от кэш-памяти размером 4 МБ к кэш-памяти размером 8 МБ, верно в некоторых крайних случаях. Но это, конечно, не верно при последующем увеличении ассоциативности. Как видно из данных, последующее увеличение ассоциативности дает существенно меньший выигрыш. Нам, однако, не следует абсолютно не учитывать этот факт. В программе нашего примера пик использования памяти равен 5,6 MB. Так что при размере кэш-памяти в 8 Мб, что те же самые кэш-наборы будут использоваться многократно (более, чем дважды). С увеличением рабочего набора экономия может увеличиться, поскольку, как мы видим, при меньших размерах кэш-памяти преимущество от использования ассоциативности будет больше.
В целом, увеличение ассоциативность кэш-памяти выше 8, как кажется, дает слабый эффект при одном потоке рабочей нагрузки. С появлением многоядерных процессоров, которые используют общую кэш-память L2, ситуация меняется. Теперь у вас в основном есть две программы, которые обращаются к одной и той же кэш-памяти, в результате чего на практике эффект от использования ассоциативности должен увеличиться вдвое (или в четыре раза для четырехядерных процессоров). Таким образом, можно ожидать, что с увеличением числа ядер, ассоциативность общей кэш-памяти должна расти. Как это станет делать невозможным (16-канальную ассоциативность реализовывать уже трудно) разработчики процессоров начнут использовать общую кэш-память уровня L3 и далее, в то время как кэш-память уровня L2 будет, потенциально, совместно использоваться некоторым подмножеством ядер.
Другой эффект, который мы можем увидеть на рис.3.8, это то, как увеличение размера кэш-памяти способствует увеличению производительности. Эти данные нельзя интерпретировать без знания размера рабочего набора. Очевидно, что кэш-память такого размера, как основная память, должен привести к лучшим результатам, нежели кэш-память меньшего размера, так что в целом нет никаких ограничений на увеличение размера кэш-памяти и получения ощутимых преимуществ.
Как уже упоминалось выше, размер рабочего набора в его пиковом значении равен 5,6 Мб. Это значение не позволяет нам рассчитать размер памяти, который бы принес максимальную выгоду, но позволяет оценить этот размер. Проблема в том, что вся память используется не непрерывно и, следовательно, у нас есть конфликты даже при наличии 16M кэш-памяти и рабочего набора, размер которого равен 5,6M (вспомните преимущество 2-канальной ассоциативной кэш-памяти размером в 16 МБ над версией с прямым отображением). Но можно с уверенностью сказать, что при такой нагрузке преимущество кэш-памяти размером в 32 МБ будет несущественным. Однако кто сказал, что рабочий набор должен оставаться неизменным? С течением времени рабочие нагрузки растут и то же самое должно касаться размера кэш-памяти. Когда покупаются машины и принимается решение, за какой размер кэш-памяти требуется заплатить, стоит измерить размер рабочего набора. Почему это важно, можно увидеть на рис. 3.10.
Рис.3.9: Размещение памяти, используемой при тестировании
Запускается два типа тестов. В первом тесте элементы обрабатываются последовательно. В тестовой программе используется указатель n , но элементы массива связаны друг с другом, так что они обходятся в том порядке, в котором они находятся в памяти. Этот вариант показан в нижней части рис.3.9. Есть одна обратная ссылка, идущая от последнего элемента. Во втором тесте (верхняя часть рисунка) элементы массива обходятся в произвольном порядке. В обоих случаях элементы массива образуют циклический односвязный список.
В такой памяти любая строка ОП может находиться в любом месте кэш-памяти, причем в любой комбинации с другими строками. Комбинационные схемы сравнения СС1-СС4 (рис. 6.4) одновременно анализируют все теги строк, находящихся в кэше в данный момент, и сравнивают их с адресом, поступившим с шины адреса от процессора. При кэш-попадании строка считывается в шину данных (ШД). При кэш-промахе происходит замещение строки в кэш-памяти на требуемую строку из ОП.
Преимущество
данной памяти в высокой скорости
считывания. Недостаток – сложность
аппаратной реализации. Поэтому полностью
ассоциативная кэш-память чаще всего
используется в специализированных
буферах, таких, как буфер целевых адресов
переходов, с небольшим объемом строк.
3. Множественно-ассоциативная кэш-память
Этот вид памяти является промежуточным между двумя вышерассмотренными. В нем сочетаются простота кэша с прямым отображением и скорость ассоциативного поиска.
Кэш-память делится на непересекающиеся подмножества (блоки) строк. Каждая строка основной памяти может попадать только в одно подмножество кэша. Для поиска блоков используется прямое отображение, а для поиска внутри подмножества - полностью ассоциативный поиск. Число строк в подмножестве кэша определяет число входов (портов) самого кэша.
Если 2 n строк кэша разбивается на 2 s непересекающихся подмножеств, то S младших разрядов оперативной памяти показывают, в каком из подмножеств (индексов) должен вестись ассоциативный поиск. Старшиеn-sразрядов адреса основной памяти являются тегами.
Если
S=0, то получим одно подмножество, что
соответствует полностью ассоциативной
кэш-памяти. Если S=n, то получим 2 n подмножеств (то есть одна строка - одно
подмножество). Это кэш-память с прямым
отображением. Если 1Sn-1, то имеем
множественно-ассоциативную кэш-память.
На
рисунке 6.5 приведен пример кэша, где
S=1, то есть имеются два подмножества
кэш- памяти. Физический адрес 0111,
выработанный процессором, разделяется
на индекс 1, равный младшему разряду, и
тег 011. По индексу выбирается второе
подмножество строк в кэш-памяти, а затем
происходит ассоциативный поиск среди
тегов строк выбранного подмножества.
Найденная строка 7 с тегом 011 передается
в шину данных (ШД). Ассоциативный поиск
производится одно
временно
по всем тегам с помощью комбинационных
схем сравнения СС1 и СС2.
Рис. 6.5. Множественно-ассоциативная кэш-память
В современных процессорах используется 4-х и 8-ми входовая кэш-память. Увеличение числа ее входов приводит к быстрому увеличению сложности аппаратной реализации той части кэша, которая обеспечивает ассоциативный поиск тегов.
Особенности записи и замещения информации в кэш-памяти. Когерентность кэш-памяти
Обращение по чтению можно начинать сразу и к КЭШ, и к оперативной памяти. Тогда, если информация отсутствует в КЭШе, к моменту установления этого факта будет уже выполнена часть цикла обращения к ОЗУ, что может повысить производительность. Если информация имеется в КЭШе, то обращение к оперативной памяти можно остановить.
При обращении по записи используется два метода: запись производится только в КЭШ или сразу и в КЭШ, и в ОЗУ. Эти методы получили название алгоритмов обратной WB (Write Back) и сквозной записи WT (Write Through) соответственно. Второй из них более простой, но и более медленный, хотя и гарантирует, что копии одной и той же информации в КЭШе и оперативной памяти всегда совпадают. Большинство ранних процессоров Intel используют именно этот алгоритм.
Алгоритм обратной записи WB более быстрый. Передача информации в ОЗУ производится только тогда, когда на место данной строки КЭШа передается строка из другой страницы ОП или при выполнении команды обновления содержимого КЭШа. Этот алгоритм требует более аккуратного управления, поскольку существуют моменты, когда копии одной и той же информации различны в КЭШе и ОП. Кроме того, не каждая строка изменяется за время своего пребывания в КЭШе. Если изменения не было, то нет необходимости переписывать строку обратно в оперативную память. Обычно используют флаг M (modified – изменена) в памяти тэгов. Он сбрасывается в “0” при первоначальной загрузке строки в КЭШ и устанавливается в “1” при записи в нее информации. При выгрузке строки из КЭШа запись в ОП выполняется только при единичном значении флага M.
При возникновении промаха контроллер кэш-памяти должен выбрать подлежащую замещению строку. Для с прямого отображения аппаратные решения наиболее простые. На попадание проверяется только одна строка, и только эта строка может быть замещена. При полностью ассоциативной или множественно-ассоциативной организации кэш-памяти имеются несколько строк, из которых надо выбрать кандидата в случае промаха. Для решения этой задачи используют следующие специальные правила, называемые алгоритмами замещения .
FIFO (First In First Out – первый пришедший – первым выбывает);
LRU (Least Recently Used – дольше других неиспользуемый);
LFU (Least Frequently Used – реже других используемый);
Случайный (random).
Первый и последний методы являются самыми простыми в реализации, но они не учитывают, насколько часто используется та или иная строка КЭШ-памяти. При этом может быть удалена строка, к которой в самом ближайшем будущем будет обращение. Вероятность ошибки для указанных методов гораздо выше, чем у второго и третьего.
В алгоритме FIFO для замещения выбирается строка, первой попавшая в КЭШ. Каждая вновь размещаемая в КЭШе строка добавляется в хвост этой очереди. Алгоритм не учитывает фактическое ее использование. Например, первые загруженные строки могут содержать данные, требующиеся на протяжении всей работы. Это приводит к немедленному возвращению к только что замещенной строке.
Алгоритм LRU предусматривает, что для удаления следует выбирать ту строку, которая не использовалась дольше других. При каждом обращении к строке ее временная метка обновляется. Это может быть сопряжено с существенными издержками. Однако алгоритм LRU наиболее часто используется на практике. Недостаток его заключается в том, что если программа проходит большой цикл, охватывающий множество строк, может случиться так, что строка, к которой дольше всего не было обращений, в действительности станет следующей используемой.
Одним из близких к LRU является алгоритм LFU, согласно которому удаляется наименее часто использовавшаяся строка. При этом необходимо подсчитывать количество обращений к каждой строке и контролировать его. Может оказаться, что наименее интенсивно используется та строка, которая только что записана в КЭШ-память и к которой успели обратиться только один раз (в то время как к другим строкам обращались больше). Она может быть удалена, что является недостатком алгоритма LFU.
Содержимое кэш-памяти меняется под управлением процессора. При этом основная память может оставаться неизменной. С другой стороны, внешние устройства могут изменять данные в ОП в режиме прямого доступа. При этом кэш-память не меняет своих данных. Еще сложнее ситуация в мультипроцессорных системах, когда несколько процессоров обращаются к общей памяти. Возникает проблема когерентности кэш-памяти.
Вычислительная система имеет когерентную память , если каждая операция чтения по адресу, выполненная каким-либо устройством, возвращает значение последней копии по этому адресу, независимо от того, какое из них производило запись последним. Проблема когерентности является наиболее важной для систем с обратным копированием. В них используются специальные протоколы, а к каждому тегу добавляются флаги модифицированности и достоверности информации. Эти флаги разрешают доступ к данным или запрещают его.
Известные варианты отображения основной памяти на кэш-память можно свести к трем видам: прямому , полностью ассоциативному и частично-ассоциативному .
При прямом отображении адрес строки i кэш-памяти, на которую может быть отображен блок j из ОП, однозначно определяется выражением: i = j mod m , где m – общее число строк в кэш-памяти, т. е. на строку кэша с номером i отображается каждый m -й блок ОП, если отсчет начинать с блока, номер которого равен i .
Прямое отображение – простой и недорогой в реализации способ отображения. Основной его недостаток – жесткое закрепление за определенными блоками ОП одной строки в кэше. Поэтому если программа поочередно обращается к словам из двух различных блоков, отображаемых на одну и тут же строку кэш-памяти, постоянно станет происходить обновление данной строки и вероятность попадания будет низкой.
Полностью ассоциативное отображение позволяет преодолеть недостаток прямого, разрешая загрузку любого блока ОП в любую строку кэш-памяти. Ассоциативное отображение обеспечивает гибкость при выборе строки для вновь записываемого блока. Принципиальный недостаток этого способа – необходимость выполнения проверки для всех строк кэш-памяти.
Частично-ассоциативное отображение является одним из возможных компромиссов, сочетающим достоинства прямого и ассоциативного способов отображения и, в известной мере, свободным от их недостатков. Кэш-память разбивается на v подмножеств (наборов), каждое из которых содержит k строк (принято говорить, что набор имеет k входов). Зависимость между набором и блоками ОП такая же, как и при прямом отображении: на строки, входящие в набор i , могут быть отображены только вполне определенные блоки основной памяти, в соответствии с соотношением i = j mod v , где j – адрес блока ОП. В то же время размещение блоков по строкам модуля – произвольное, и для поиска нужной строки в пределах модуля используется ассоциативный принцип.
В предельных случаях, когда v = m , k = 1, множественно-ассоциативное отображение сводится к прямому, а при v = 1, k = m – к ассоциативному.
В зависимости от способа определения взаимного соответствия строки кэша и блока основной памяти различают три архитектуры кэш-памяти:
· полностью ассоциативный кэш (fully associative cache);
· кэш прямого отображения (direct-mapped cache);
· наборно- (частично- или множественно-) ассоциативный кэш (set-associative cache).
В полностью ассоциативном кэше любой блок основной памяти может находиться в любой строке кэш-памяти или любая строка кэш-памяти может отображать любой блок основной памяти. При этом старшие разряды адреса кэшированных данных, за вычетом разрядов, определяющих положение (смещение) данных в строке (блоке), заносятся в каталог и используются в качестве тега. В такой архитектуре для определения наличия в кэше данных с определенным адресом необходимо сравнивать старшие разряды этого адреса с тегами всех строк в каталоге кэш-памяти. Если такое сравнение делать последовательно, то на это уйдет слишком много времени, и кэш-память теряет смысл из-за низкого быстродействия. Поэтому такое сравнение необходимо выполнять параллельно для всех тегов. Этому требованию наилучшим образом отвечает ассоциативная память, то есть тег должен храниться в ассоциативной памяти тегов кэша.
Такая организация кэш-памяти является сложной аппаратной задачей, которая решается только для небольших объемов, т. е. полностью ассоциативный кэш из-за своей сложности не может иметь большой объем и используется, как правило, для вспомогательных целей. Например, в процессорах Intel полностью ассоциативный кэш используется в блоке страничной переадресации для построения буфера ассоциативной трансляции TLB (Translation Look aside Buffer), предназначенного для ускорения доступа к интенсивно используемым страницам.
Противоположной архитектурой является кэш прямого отображения . В кэше прямого отображения конкретный блок основной памяти может находиться только в строго определенной строке кэш-памяти. Основная память условно разбивается на страницы, размер которых совпадает с размером кэш-памяти. Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы основной памяти только соответствующий ей блок. Блоки с одинаковыми номерами всех страниц попадают в одну и ту же строку кэш-памяти. Следовательно, на каждую строку кэша претендует множество блоков основной памяти с одинаковыми номерами внутри страницы. Одна строка в каждый момент времени может содержать копию только одного из этих блоков. В качестве тега используется номер страницы, блок которой занимает соответствующую строку кэша. В такой архитектуре для определения наличия в кэше данных с определенным адресом необходимо сравнивать номер страницы, которой принадлежит этот адрес, с тегом той строки в каталоге кэш-памяти, которая соответствует блоку на странице, содержащему заданный адрес, т. е. необходимо выполнить только одно сравнение.
Кэш прямого отображения имеет самую простую аппаратную реализацию, так как кэш-память имеет структуру обычной прямо адресуемой памяти и необходимо всего одно устройство сравнения. Поэтому такой кэш может иметь большой объем.
Промежуточным между полностью ассоциативным кэшем и кэшем прямого отображения является наборно-ассоциативный кэш , который в основном и используется в современных микропроцессорах. В наборно-ассоциативном кэше в отличие от кэша прямого отображения каждый блок основной памяти может претендовать на одну из нескольких строк кэш-памяти, объединенных в набор (set). Это увеличивает вероятность удачного обращения. Упрощенно можно считать, что наборно-ассоциативный кэш представляет собой несколько параллельно и согласовано работающих каналов прямого отображения, в которых строки с одинаковыми номерами образуют соответствующий набор. Строка набора, отображающая требуемый блок основной памяти, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша. С каждым набором связан признак, определяющий строку набора, подлежащую замещению новым блоком в случае кэш-промаха. Кандидатом на замещение обычно выбирается строка, к которой дольше всего не было обращения (алгоритм LRU – Least Recently Used). Возможно также применение алгоритма замещения FIFO или даже случайного замещения, что проще, но менее эффективно.