Вопрос 21. Организация кэш-памяти: кэш прямого отображения, наборно-ассоциативный кэш, полностью ассоциативный кэш

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

При прямом отображении адрес строки 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 или даже случайного замещения, что проще, но менее эффективно.