Кэш-память

Как уже говорилось выше, назначение кэш-памяти – временное хранение данных и команд, часто используемых процессором. Основной структурной единицей кэш-памяти является так называемая строка кэша (cache line). Длина строки кэша составляет обычно 32, 64, 128 или 256 байт.

Рассмотрим способы организации кэш-памяти, принятые в современных ЭВМ. Опишем возможные способы отображения адресов данных в оперативной памяти на адреса данных в кэш-памяти и, соответсвенно, способы поиска требуемых данных в кэш-памяти. Пусть, в качестве упрощенного примера, существует ЭВМ с десятибитным адресом. Следовательно, объем непосредственно адресуемой оперативной памяти составляет 2¹⁰ байт. Пусть имеется кэш-память из восьми строк, каждая строка из восьми байт. Организация кэш-памяти показана на рис 18. С каждой строкой кэша связано поле тэга. Тэг (tag – пометка, отметка) – признак, используемый при поиске требуемых данных.

Существуют три основных способа организации кэш-памяти: 1) кэш с прямым отображением; 2) полностью ассоциативный кэш; 3) наборно ассоциативный кэш.

В случае кэша с прямым отображением адрес, формируемый процессором, имеет вид, показаный на рис 18 а). Адрес состоит из трех частей. Младшие биты адреса определяют конкретный байт в строке кэша. Их количество k определяется длиной строки кэша L

k = log₂L.

Средние биты адреса определяют одну из строк кэша. Количество n средних битов определяется количеством M строк кэша

n = log₂M.

											тэг

тэг	строка	байт

а)

											тэг

Тэг	байт

б)

											тэг

тэг	набор	байт

в)

Рис 18. Кэш-память. а) с прямым отображением; б) полностью ассоциативная; в) наборно-ассоциативная.

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

Достоинство кэша с прямым отображением – очевидная простота реализации. Недостаток состоит в том, что несколько адресов с одинаковыми младшими k + n битами могут претендовать на одну и ту же ячейку кэша.

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

Третий вид кэш-памяти – наборно-ассоциативная (см. рис 18 в)) – это смешанная конструкция, сочетающая в себе простоту памяти с прямым отображением и эффективность ассоциативного кэша. Строки кэша объединяются в наборы по 2, 4, 8 и т.д. штук. Средние биты определяют не строку, а набор. Конкретная строка в наборе выбирается с помощью ассоциативного сравнения для всех строк, входящих в набор.

Пусть контроллер кэш-памяти обнаружил, что данные, требуе­мые в настоящий момент для процессора, в кэш-памяти отсутст­вуют. Нужно прочитать строку, содержащую необходимые данные из оперативной памяти, и разместить ее в кэш-памяти. Для этого не­обходимо решить, какую из строк кэша сле­дует удалить для разме­щения вновь поступивших данных. Для выбора строки, подлежащей замещению, чаще всего используется так называемый алгоритм LRU (от Least Recently Used – дольше всего неиспользуемый). Суть алгоритма в том, что совместно с каждым элементом хранится исто­рия его использования за последнее время. Из всех существующих элементов выбирается тот, к которому дольше всего не было обра­щений. Недостатком алгоритма можно считать необ­ходимость хра­нения и обработки большого количества информации об истории использования элемента данных, что становится особенно важным при исполь­зовании кэша большого объема. Поэтому в системах с кэш памятью большого объема часто применяется более простой алгоритм, по которому вытесняемая строка выбирается случайным образом. Как показывает практический опыт, при большом объеме кэш-памяти алгоритм случайного замещения незначительно проиг­рывает алгоритму LRU по эффективности, но значительно выигры­вает по простоте реализации.

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

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

Существенно уменьшить потери производительности позволяет другой способ записи, который называется буферизированной сквозной записью (buffered write through). Процессор передает запи­сываемые данные контроллеру кэша и на этом операция записи для процессора считается законченной. Записываемые данные сохра­нятся в буфере контроллера кэша и переписываются из буфера в оперативную память в те моменты времени, когда процессор не производит обращений к памяти и системная шина свободна.

Третий способ организации называется обратной записью (write back). При этом способе нагрузка на тракты обмена данными между процессором и памятью максимально снижается. Процессор произ­водит запись только в кэш-память. В каждый момент времени суще­ствует только одна «истинная» копия данных, находящаяся в кэш-памяти. Перезапись данных из кэш-памяти в основную память про­изводится только тогда, когда одна строка кэша заменяется другой, причем перезаписывается только строка целиком. Для этого каждая строка кэша снабжается дополнительным признаком «грязных» данных, который устанавливается, если в данную строку произво­дилась запись. При установленном признаке строка, вытесняемая из кэша, переписывается в оперативную память, иначе она не перепи­сывается. Подобный способ записи, в сочетании с алгоритмом вы­теснения данных LRU описанным выше, позволяет избавиться от «лишних» обращений к памяти для часто используемых данных, на­пример счетчиков циклов, временных рабочих переменных и т.д.