Архитектуры SRAM

     Однако, если запись в каждую строку кэша происходит в среднем более одного раза до смены этой строки́, то выгодна другая стратегия. Очень частый сценарий работы с конкретным элементом памяти — «запись, чтение, запись, чтение, ...». Здравый смысл подсказывает, что запись в оперативную память нужно произвести лишь в самом конце подобной цепочки. А когда у цепочки операций со строкой кэша наступает конец? Тогда, когда эта строка выбрасывается из кэша.

     Таким образом, когда строка выбрасывается из кэша, она должна быть записана в оперативную память. Но что, если она не была изменена? Тогда её не нужно записывать. Для того, чтобы отслеживать изменения строк кэша, снабдим каждую строку дополнительным битом (рисунок 11), который будет устанавливаться в единицу при модификации данных в строке. Тогда при вытеснении строки́ нужно будет проверить этот бит, и, если он равен единице, произвести запись в оперативную память.

     

     Рисунок 11. Бит модификации строки.

     Итак, процессор записывает данные в память. Если эти данные есть в кэше, то они перезаписываются и помечаются, как изменённые. Если данных в кэше нет, то самая старая строка вытесняется, и на её место записываются новые данные, опять же помеченные как изменённые. Недостаток такого подхода в том, что при промахе кэша теперь часто будут происходить две операции: запись данных старой строки́ из кэша в оперативную память, и загрузка требуемых данных из памяти в кэш. Поэтому иногда делают так, что кэш в свободное время сам переписывает модифицированные данные в оперативную память, обнуляя соответствующие биты модификации[9].

     Нам осталось решить две проблемы:

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

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

     Для решения этих проблем будем хранить в каждой строке кэша не один байт данных, а несколько байт, идущих подряд в оперативной памяти. Тегом строки́ будем считать адрес первого содержащегося в ней байта. Рассмотрим пример, когда в строке кэша хранятся 16 байт. Для того, чтобы данные в строках не могли «перекрываться» (перекрытие данных значительно усложнит логику работы), потребуем, чтобы теги всех строк были кратны 16. Тогда 4 последних бита тега будут равны нулю, и их не нужно хранить. Мы видим, что отношение «полезного» объёма кэша к общему значительно улучшилось (рисунок 12).

     

     Рисунок 12. Каждая строка кэша имеет несколько байт данных.

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

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

     Теперь, если процессор будет запрашивать байты из памяти подряд, то лишь каждое 16-е обращение к памяти будет приводить к промаху кэша. Конечно, есть и недостаток: соседние 15 байт будут загружаться (и занимать часть кэш-памяти) даже тогда, когда они процессору не понадобятся. Можно усложнить алгоритм, чтобы чтение или запись данных подряд вообще не приводило к промахам кэша: для этого нужно загружать в кэш следующие 16 байт, если произошло обращение к последнему байту строки́[10].

     2.1.2 Кэш с прямым отображением адресов

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

     Как и раньше, разделим кэш на стро́ки, и в каждой строке кэша будем хранить несколько (например, 16) байт оперативной памяти. Кроме того, предположим, что кэш имеет 65536 строк (таким образом, объём кэш-памяти равен 16×65536 = 1 Мегабайт).

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

     

     Рисунок 13. Разделение адреса на части.

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

     

     Рисунок 14. Прямое отображение адресов 
(на примере кэш-памяти объёмом 1 МБ).

     Так как каждый байт оперативной памяти может находиться только в одном месте кэш-памяти, при записи новых данных в кэш нет необходимости решать, какие данные будут из кэша вытеснены: вытеснять нужно ту́ строку, на место которой приходит новый байт. Поэтому нет необходимости хранить «возраст» строки́ кэша[10].

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

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

     

     Рисунок 15. Строка кэша с прямым отображением адресов.

     Когда процессор выдаёт запрос на чтение байта оперативной памяти, кэш-контроллер выполняет следующие действия:

     разбивает адрес требуемого байта на части (как показано на рисунке 1), определяя тэг, номер строки́ кэша, и смещение в строке;

     сверяет тэг, записанный в нужной строке кэша, с тэгом, выделенным из адреса;

     если тэги не совпали (данные в кэше отсутствуют), то выполняются следующие действия:

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

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

     тэг строки́ заменяется на тэг, выделенный из адреса требуемого байта;

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

     Когда процессор выдаёт запрос на запись байта в оперативную память, кэш-контроллер выполняет следующие действия:

     разбивает адрес требуемого байта на части (как показано на рисунке 14), определяя тэг, номер строки́ кэша, и смещение в строке;

     сверяет тэг, записанный в нужной строке кэша, с тэгом, выделенным из адреса;

     если тэги не совпали (перезаписываемые данные не прокэшированы), то выполняются следующие действия:

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

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

     тэг строки́ заменяется на тэг, выделенный из адреса требуемого байта;

     теперь перезаписываемые данные точно присутствуют в кэше, и контроллер модифицирует байт строки́ кэша в соответствии со смещением, выделенным из адреса;

бит модификации строки́ устанавливается в 1.

     Кэш с прямым отображением адресов является частным случаем полностью ассоциативного кэша, если стратегию вытеснения данных заменить с «вытеснения самой старой строки́» на «вытеснение строки́, имеющей то же самое смещение в своём мегабайте данных, что и требуемая/записываемая строка». Иногда это приводит к ситуациям, при которых кэш вообще не работает. Например, представим, что мы складываем соответствующие элементы двух массивов А и B, и так оказалось, что расстояние между этими элементами кратно размеру кэша. Тогда при поочерёдном обращении к элементам массивов A и B, они будут вытеснять друг друга из кэша, так как отображаются в одно и то же место кэш-памяти.

     Из-за примитивной «стратегии замещения» кэш с прямым отображением адресов в среднем проигрывает по скорости полностью ассоциативному кэшу того же объёма, вытесняющему самую старую строку. Для того, чтобы сравнять скорости, объём кэша с прямым отображением должен быть увеличен в 4–8 раз.

     Кэш с прямым отображением адресов, будучи самым простым с точки зрения аппаратной реализации, исторически был первым распространённым видом кэшей. Однако из-за своей низкой эффективности он был быстро вытеснен гораздо более совершенным N-ассоциативным кэшом[10].

     2.1.3 N-ассоциативный кэш

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

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

     Пусть, как и раньше, адрес состоит из 4-х байт, объём кэша равен одному мегабайту, длина строки́ — 16 байт. Для определённости рассмотрим пример работы четырёх-ассоциативного кэша.

     Когда процессор производит обращение к оперативной памяти, адрес разделяется на компоненты, как показано на рисунке:

     

     Рисунок 16. Разделение адреса на части в четырёх-ассоциативном кэше.

     Отличие от кэша с прямым отображением здесь в том, что контроллер кэш-памяти вправе выбирать два старших бита номера строки́ (hint) по своему усмотрению, тем самым записывая данные из оперативной памяти в одно из четырёх возможных для данного адреса мест кэш-памяти. В общем случае число бит в поле hint равно  .

     Важно понимать, что сначала адрес разбивается на компоненты (тег, номер строки́, смещение), а затем производится выбор двух старших битов но́мера строки́. Таким образом, тег содержит неизменённые старшие биты адреса, тем самым позволяя определять, какие же на самом деле данные находятся в данной строке. Например, в строку кэш-памяти №1 (стро́ки нумеруются с нуля) могут попасть байты   из оперативной памяти, где N — любое число. При этом тэг как раз и хранит это N.

     Но  как выбрать эти два произвольных бита? Самое лучшее, что можно сделать — это заместить ту́ строку (из четырёх возможных), к которой наиболее долго не было обращений. Это опять приводит нас к необходимости хранить «возраст» каждой строки́ кэша. Однако в данном случае возраст может быть реализован гораздо проще, чем в полностью ассоциативном кэше. Посмотрим, как это можно сделать.

     Мысленно разобьём кэш-память на непересекающиеся подмножества из четырёх строк таким образом, чтобы номера строк каждого подмножества имели одинаковые младшие биты, но отличались двумя старшими битами. Например, в первое подмножество войдут стро́ки номер 0, 16384, 32768 и 49152; во второе подмножество войдут стро́ки с номерами 1, 16385, 32769, 49153 и так далее.