Принципы, лежащие в основе использования кэш-памяти, и организация кэш-памяти прямого отображения:
Существует весьма значительный разрыв по быстродействию между регистровой памятью и оперативной, а также между оперативной памятью и памятью внешней. Этот разрыв в современных процессорах сглаживается с помощью специальных буферных запоминающих устройств, программно недоступных и прозрачных для пользователя. Особенно неприятен разрыв по быстродействию между регистровой и оперативной памятью. Действительно, лучшие современные микросхемы динамической оперативной памяти обладают временем доступа порядка 40 нс, а обращение к регистрам современного процессора может происходить за доли наносекунды. Следовательно, для согласования скорости работы процессора и оперативной памяти приходиться вводить дополнительные циклы ожидания, а это ведет к резкому снижению производительности системы. Реализация же оперативной памяти на быстрых микросхемах памяти статического типа привело бы к существенному удорожанию системы и снижению ряда ее эксплуатационных характеристик (увеличению габаритных размеров, веса, росту потребляемой мощности, стоимости, и т.д.). Эта проблема может быть существенно упрощена, если между сравнительно медленной оперативной памятью и быстрым процессором (точнее, его регистровой памятью) поместить некоторую буферную память относительно небольшой емкости, но с возможностью работы на частоте равной или близкой тактовой частоте процессора. При этом тактов ожидания центрального процессора либо не будет вообще, либо они будут сведены к минимуму. Такая буферная память получила название кэш-памяти (от английского слова Cache – тайник, склад, «заначка»). Запоминающее устройство кэш-памяти обычно представляет собой статическое запоминающее устройство (SRAM), обладающее на порядок большим быстродействием, чем самые быстродействующие динамические RAM, на которых основана основная оперативная память. Таким образом, назначением кэш-памяти является согласование скорости работы центрального процессора и оперативной памяти системы. Впоследствии, понятие кэш-памяти распространилось и на буферные памяти другого назначения (совокупность теневых регистров в системе формирования линейного адреса с помощью дескрипторных таблиц, буфер TLB при организации страничной переадресации и даже на буферную память между внешней и оперативной памятью). Вполне понятно, что кэш-памяти организуются либо в виде регистровой памяти, либо на микросхемах памяти статического типа, как обладающих максимальным быстродействием. Увеличенное энергопотребление и меньший уровень интеграции статических микросхем ЗУ, при этом, отходит на второй план в связи со сравнительно небольшим объемом кэш-памяти. Заметим, что кэшироваться, т.е. передаваться из основной памяти в кэш-память, может не вся память, доступная процессору. Обычно кэшируется только основная динамическая память системной платы (память, установленная на адаптерах не кэшируется), и даже из этой памяти кэшируется только часть (еще совсем недавно широко распространенные версии Chipsets для Pentium часто позволяли кэшировать только первые 64 Мбайт ОЗУ). Заметим, что хотя работа кэш-памяти и прозрачна для программиста, однако знание особенностей ее функционирования позволяет в ряде случаев существенно сократить время выполнения программы.
В основу работы кэш-памяти положен принцип локальности программ, который включает в себя принцип временной локальности и принцип пространственной локальности. Суть этих принципов состоит в следующем. Поскольку обращения к оперативной памяти носят не случайный характер, а выполняются в соответствии с выполняемой программой, то при считывании данных из ОП, с высокой степенью вероятности можно предположить, что в ближайшем будущем она опять обратится к этим данным. Эта положение определяет принцип временной локальности. Например, такая ситуация имеет место при решении систем уравнений в научных и инженерных расчетах, когда короткие участки программного кода с большим количеством вложенных и зацепленных друг с другом циклов обрабатывают поочередно, переходя от точки к точке, небольшие порции данных, многократно используя одни и те же данные и внутренние результаты.
Кроме того, весьма вероятно и то, что в ближайшем будущем программа обратится к ячейке, которая следует за той, к которой она обращается в текущий момент времени. Это положение определяет принцип пространственной локальности.
В соответствии с принципом временной локальности в буфере (кэш-памяти) информацию хранить целесообразно в течение некоторого времени, а принцип пространственной локальности предполагает считывание в кэш-память ряд соседних ячеек памяти, т.е. блока информации. Каждый блок хранится в одной строке буфера, а набор таких строк и составляет кэш-память. На размере блока и, соответственно, строки кэш-памяти следует остановиться подробнее, так как он является весьма важным параметром.
В целом существует зависимость, в соответствии с которой чем больше размер блока, тем выше коэффициент удачных обращений (отношение количества обращений, которые пришлись на кэш-память без необходимости обращения к основной памяти, к общему количеству обращений процессора к памяти). С другой стороны, чем больше размер блока, тем меньше их помещается в кэш-памяти данного объема. При этом растет вероятность появления операций пересылки блоков из оперативной памяти.
Заметим, что для увеличения скорости блочных пересылок между основной памятью и кэш-памятью желательно, чтобы с увеличением размера блоков росла и разрядность шины данных между ОП и кэш-памятью. (В этом, например, заключается основной смысл введения 64-разрядной шины данных в 32-разрядных процессорах семейства Pentium).
Исследованиями виднейших специалистов в области систем программирования (в частности Д.Кнутом) было установлено, что линейные участки программ (т.е. участки, в которых отсутствуют команды переходов) обычно не превышают 3…5 команд, а значит, и нет особого смысла в использовании блоков, размер которых превышает эту величину. Поэтому типичный размер применяемых в современных компьютерах блоков составляет 16, 64, 128 и 256 байт. В персональных компьютерах, создаваемых на микропроцессорах типа i486 информация загружалась в кэш блоками по 16 байт, а в процессорах линии Pentium - по 32 байта. В современных процессорах микроархитектуры Sandy Bridge размер блока принят равным 64 байт.
При каждом обращении к кэшируемой основной памяти контроллер кэш-памяти по каталогу признаков (тэгов) проверяет, есть ли действительная копия затребованных данных в кэш-памяти. Если она там есть, то это случай кэш-попадания (cache hit), и обращение за данными происходит только к кэш-памяти. Если действительной копии там нет, то это случай кэш-промаха (cache miss), и данные берутся из основной памяти. При этом в соответствии с алгоритмом кэширования, блок данных, включающий запрашиваемые данные, считывается из основной памяти и замещает один из блоков кэш-памяти.
Обращение к основной памяти может начинаться одновременно с поиском в кэш-памяти, а в случае попадания (cache hit) – прерываться. Такая технология носит название технологии Look aside. При ее использовании время доступа к требуемой информации сокращается, но зато увеличивается энергопотребление.
Другая технология (Look through) заключается в том, что обращение к основной памяти начинается только после обнаружения промаха (cache miss). При этом экономится энергопотребление, но увеличивается время доступа к требуемым данным (теряется, по крайней мере, один такт процессора).
Организация и функционирование.
Поскольку кэш-память по объему значительно меньше основной оперативной памяти (на 2-3 порядка и более) то встает вопрос о способах отображения кэшируемой оперативной памяти в буферную кэш-память. В зависимости от способа этого отображения различают следующие разновидности кэш-памятей.
Кэш с прямым отображением (Direct-mapped cache).
Полностью ассоциативный кэш (Fully associative cache).
Наборно-ассоциативный кэш (Set-associative cache), часто называемый множественно-ассоциативным.
Кэш-память с прямым отображением.
По организации, кэш-память с прямым отображением является самым простым типом буферной памяти. Физический адрес однозначно определяет строку кэш-памяти, в которую будет помещен блок информации из оперативной памяти. При этом предполагается, что оперативная память разбита на блоки и каждому такому блоку в буферной кэш-памяти отводится всего одна строка (см. рис.IV.2).
Предположим, что в компьютере используется 32-разрядный физический адрес. Размер блока пусть будет равным 16 байтам, а е емкость кэш-памяти – 8 Кбайт. В этом случае для формирования адреса в кэш-памяти достаточно 13 разрядов, из которых 4 младших разряда определяют один из 16 байт в блоке, а 9 старших разрядов адресуют один из 512 блоков (строк) кэш-памяти
Рис.IV.2 Организация кэш-памяти объемом 8 Кбайт
с прямым отображением.
. В соответствии с этим, физический адрес, выдаваемый процессором, можно разбить на 3 поля: старшие 19 разрядов – признак или тэг (Tag), средние 9 разрядов – индекс (Index) или номер строки и младшие 4 разряда – смещение или номер байта в строке.
Тэг – определяет как бы виртуальную страницу адресного пространства оперативной памяти, где находится требуемый блок данных, т.е. некоторый массив соседних ячеек оперативной памяти. А код тэга представляет 19 старших разрядов начального адреса этой виртуальной страницы в полном адресном пространстве 4 Гбайт, в которой находится блок информации, содержащийся в строке кэш-памяти. (При этом, младшие 13 разрядов этого адреса равны нулям). Самих же таких виртуальных страниц, размером 213=8192 байта, в адресном пространстве 4 Гбайт, будет 219=512 К.
Для пояснения понятия страницы, на стр.84, приведена таблица адресов, которая иллюстрирует возможные разбиения адресного пространства на страницы. В приведенном выше перечне адресов адресного пространства, объемом 288 байт, можно выделить, например, 16 страниц 4 битовых адресов, или 8 страниц 5 битовых адресов, или 4 страницы 6 битовых адресов и т.д.
емкость кэш-памяти – 8 Кбайт. В этом случае для формирования адреса в кэш-памяти достаточно 13 разрядов, из которых 4 младших разряда определяют один из 16 байт в блоке, а 9 старших разрядов адресуют один из 512 блоков (строк) кэш-памяти
. В соответствии с этим, физический адрес, выдаваемый процессором, можно разбить на 3 поля: старшие 19 разрядов – признак или тэг (Tag), средние 9 разрядов – индекс (Index) или номер строки и младшие 4 разряда – смещение или номер байта в строке.
Тэг – определяет как бы виртуальную страницу адресного пространства оперативной памяти, где находится требуемый блок данных, т.е. некоторый массив соседних ячеек оперативной памяти. А код тэга представляет 19 старших разрядов начального адреса этой виртуальной страницы в полном адресном пространстве 4 Гбайт, в которой находится блок информации, содержащийся в строке кэш-памяти. (При этом, младшие 13 разрядов этого адреса равны нулям). Самих же таких виртуальных страниц, размером 213=8192 байта, в адресном пространстве 4 Гбайт, будет 219=512 К.
Для пояснения понятия страницы, на стр.84, приведена таблица адресов, которая иллюстрирует возможные разбиения адресного пространства на страницы. В приведенном выше перечне адресов адресного пространства, объемом 288 байт, можно выделить, например, 16 страниц 4 битовых адресов, или 8 страниц 5 битовых адресов, или 4 страницы 6 битовых адресов и т.д.
Индекс – определяет номер строки кэш-памяти, в которую заносится из оперативной памяти блок информации, размером 16 байт. Таким образом, в нашем примере кэш память насчитывает 29=512 строк. Напомним, что размер блока в 16 байт характерен для процессоров типа i386 и i486. Размер блока в процессорах линии Pentium имеет значение 32 байта, а в современных процессорах микроархитектуры Sandy Bridge размер блока принят равным 64 байт.
Смещение – определяет номер (адрес) требуемого элемента в строке (байта, слова, двойного слова и т.д.) В нашем примере один блок может содержать до 16 байт, до 8 слов или 4 двойных слова.
Биты достоверности V (Valid) (один бит на одну строку кэш-памяти) – определяют, занесен ли в данную строку достоверный блок информации или нет. Если в бите достоверности строки записана 1, это означает, что в текущий
момент времени данная строка достоверно отображает соответствующий блок основной памяти. При начальной инициализации системы все эти биты устанавливаются равными 0.
Биты модифицируемости M (Modified) (один бит на строку кэш-памяти) – определяют, изменялось ли содержимое данной достоверной строки в процессе обмена информации с процессором или нет. Если осуществлялось только считывание из нее, то строка не изменялась и остается «чистой» (clean). Если изменялось, т.е. в нее осуществлялась запись, то строка становится «грязной» (dirty) и ее содержимое подлежит перезаписи в оперативную память.
При обращении CPU к оперативной памяти поле индексов определяет выбор одной из строк (cache line) кэш-памяти. Признак, хранящийся в соответствующей строке памяти признаков (тэгов), сравнивается с 19 старшими разрядами физического адреса, выданного CPU. Если выбранная из памяти признаков информация (код признака - тэг) совпадает со значениями этих разрядов и бит достоверности равен 1, то это означает, что необходимые данные находятся в кэш-памяти (cache hit) – они считываются и передаются в CPU. Если же нет, то это свидетельствует об отсутствии запрашиваемой информации в кэш-памяти (cache miss). В этом случае затребованная информация извлекается непосредственно из оперативной памяти и, одновременно, соответствующий блок информации из оперативной памяти записывается в выбранную строку кэш-памяти.
Существенное преимущество данного типа кэш-памяти заключается в необходимости только одного сравнения признака (тэга), выбранного из соответствующей строки кэш-памяти, и старших разрядов физического адреса, выдаваемого CPU. Такое техническое решение может существенно повысить производительность системы, однако, если адреса двух блоков памяти отличаются только полем признака, то они будут отображаться на одну и ту же строку кэш-памяти. В этом случае, если в прежнем блоке памяти, расположенном в данной строке, не происходили какие либо изменения со времени его перемещения из оперативной памяти в данную строку (например, с этой строки в CPU производились только считывания), то тогда новый блок просто помещается в данную строку вместо старого. Старый блок, при этом уничтожается (учитывая, что его копии все равно находятся в оперативной памяти), а признак (тэг) изменяется на новый. Если же в этот прежний блок кэш-памяти данной строки процессором уже производилась запись, т.е. он изменялся (стал dirty), тогда перед тем, как в данную строку запишется новый блок памяти из ОП, старый блок должен быть переписан опять в оперативную память. Необходимость разрешения таких конфликтов приводит к росту числа пересылок между кэш-памятью и оперативной памятью, что в итоге влияет на эффективность работы кэш-памяти не самым благоприятным образом.
Кроме того, если в процессе выполнения программы процессору поочередно будут требоваться блоки памяти, смещенные относительно друг друга на величину, кратную размеру виртуальной страницы, то кэш будет работать интенсивно, но вхолостую (cache trashing). Очередное обращение будет замещать данные, считанные в предыдущем и потребующиеся в последующем обращении, - то есть будет сплошная череда кэш-промахов. Переключение страниц в многозадачных ОС также снижает количество кэш-попаданий, что отражается на производительности системы. Увеличение размера кэш-памяти, при сохранении архитектуры прямого отображения, дает не очень существенный эффект, поскольку разные задачи будут претендовать на одни и те же строки кэш-памяти.
В современных микропроцессорах кэш – память с прямым отображением используется редко.