Цели и задачи кэш-памяти
…кэш (называемый так же сверхоперативной памятью) представляет собой высокоскоростное запоминающее устройство небольшой емкости для временного хранения данных, значительно более быстродействующее, чем основная память, но, в отличии от оперативной памяти, не адресуемое и непосредственно не "видимое" для программиста.
В задачи кэша входит:
а) обеспечение быстрого доступа к интенсивно используемым данным;
b) согласование интерфейсов процессора и контроллера памяти;
с) упреждающая загрузка данных;
d) отложенная запись данных.
Обеспечение быстрого доступа к интенсивно используемым данным. Архитектурно кэш-память расположена между процессором основной оперативной памятью (см. рис. 0x009) и охватывает все (реже часть) адресного пространства. Перехватывая запросы к основной памяти, кэш-контроллер смотрит: есть ли действительная (валидная от английского valid) копия затребованных данных в кэше. Если такая копия там действительно есть, то данные наскоро извлекаются из сверхоперативной памяти и происходит так называемое кэш-попадание (cache hit). В противном случае говорят о промахе
– (cache miss), и тогда запрос данных переадресуется к основной оперативной памяти.
Рисунок 9 0х009 Расположение кэша в иерархии оперативной памяти
Для достижения наивысшей производительности кэш-промахи должны происходить как можно реже (а в идеале – не происходить вообще). Учитывая, что емкость сверхоперативной памяти намного меньше емкости основной оперативной памяти, добиться этого не так-то просто! И в служебные обязанности кэш-контроллера в первую очередь входит накопление в сверхоперативной памяти действительно нужных данных и своевременное удаление оттуда всякого "мусора", – данных, которые более не понадобятся. Поскольку, кэш-контроллер не имеет абсолютно никакого представления о назначении обрабатываемых данных, эта задача требует нехилого искусственного интеллекта. Но, увы, кэш-контроллеры персональных процессоров интеллектом не обременены и слепо действуют по одному из нескольких шаблонов, называемых стратегиями кэширования.
Стратегия помещения данных в кэш- память представляет собой алгоритм, определяющий: стоит ли помещать копию запрошенных данных в сверхоперативную память или нет? Процессоры класса Intel Pentium (и совместимые с ними процессоры AMD) не мудрствуя лукаво, помещают в кэш все данные, к которым хотя бы однократно происходит обращение.
Поскольку, мы не можем сохранить в кэше содержимое всей оперативной памяти и рано или поздно кэш заполняется по самую макушку (а с такой стратегией он заполняется скорее рано, чем поздно) настанет время, когда для помещения новой порции данных, нам придется в спешном порядке выкинуть из кэша что-нибудь ненужное, чтобы освобождать для них место. (Помните, как говорил кот Матрискин: "…чтобы продать что-нибудь ненужное, надо сначала купить что-нибудь ненужное..")
Поиск вот таких наименее нужных данных и называется стратегия замещения. Можно принимать решение, основываясь на количестве обращений к каждой порции данных (частотный анализ), можно – на времени последнего обращения, выбрав ту, к которой дольше всего не обращались (алгоритм LRU – Least Recently Used), можно – на времени загрузки из основной памяти, вытеснив ту, которая была загружена раньше всех (алгоритм FIFO – First Input First Output), а можно просто подкинуть монетку (randomize-алгоритм)– на кого судьба ляжет, – ту и вытеснять (кстати, именно такая стратегия замещения использовалась в процессорах AMD K5).
В современных процессорах семейства x86 встречаются исключительно стратегии FIFO и LRU, частотный же анализ ввиду сложности его реализации в них не используется.
Согласование интерфейсов процессора и контроллера памяти. "Ячейка памяти" в понятии современных процессоров представляет как правило байт или двойное слово. С другой стороны, минимальной порцией обмена с физической оперативной памятью является пакет, состоящий по меньшей мере из четырех 64-разрядных ячеек.
Здесь можно провести аналогию с оптовой торговлей, – производитель не отпускает товар по штукам и если нам, положим, требуется один карандаш, мы все равно вынуждены приобретать целую упаковку.
Естественно, до той поры, пока остальные карандаши не будут реально востребованы (конечно, если они вообще будут востребованы), их необходимо где-то хранить. Решение: извлечь один-единственный карандаш из упаковки и выбросить остатки, – слишком нерационально, поэтому здесь не рассматривается. Тем более, что подходящее хранилище для пакетов данных у нас есть – это кэш. Получив пакет данных со склада, пардон, загрузив их из основной оперативной памяти, кэш позволяет процессору обрабатывать эти данные с любой разрядностью. Именно этим, кстати, объясняется выбранная стратегия загрузки данных (см. "Стратегия помещения данных"). Кэш-контроллер вынужден помещать в сверхоперативную памяти все ячейки, к которым происходит обращение, уже хотя бы потому, что выкидывать их, как карандаши, в приведенном выше примере, было бы крайне нерационально.
Упреждающая загрузка данных. Существует несколько стратегий загрузки данных из основной оперативной памяти в кэш-память. Простейший алгоритм загрузки, называемый загрузкой по требованию (on demand), предписывает обращаться к основной памяти только после того, как затребованных процессором данные не окажется в кэше (то есть, попросту говоря, после возникновения кэш-промаха). В результате, в кэше окажутся действительно именно те данные, которые нам нужны (и это плюс!), однако, при первом обращении к ячейке, процессору придется очень долго ждать – приблизительно 20 тактов системной шины, если не дольше, – а вот это минус!
Стратегия спекулятивной (speculative) загрузки, напротив, предписывает помещать данные в кэш задолго то того, как к ним произойдет реальное обращение. Откуда же кэш-контроллер может знать, какие именно ячейки памяти потребуется процессору в ближайшем будущем? Ну… наверняка знать этого он этого, конечно, не может, но почему бы ему не попробовать просто угадать?
Алгоритмы угадывания делятся на интеллектуальные и неинтеллектуальные. Типичный пример неинтеллектуального алгоритма – опережающая загрузка.
Исходя из предположения, что данные из оперативной памяти обрабатываются последовательно в порядке возрастания адресов, кэш-контроллер, перехватив запрос на чтение первой ячейки, в порядке собственной инициативы загружает некоторое количество ячеек, последующих за ней. Если данные действительно обрабатываются последовательно, то остальные запросы процессора будут выполнены практически мгновенно, ведь запрошенные ячейки уже присутствуют в кэше! Следует заметить, что стратегия опережающей загрузки возникает уже в силу необходимости согласования разрядности оперативной памяти и процессора (см. "Согласование интерфейсов процессора и контроллера памяти").
Серьезный минус опережающей (и вообще неинтеллектуальной) загрузки состоит в том, что алгоритм обработки данных далеко не всегда совпадает с алгоритмом их загрузки и зачастую ячейки памяти востребуются процессором не в том порядке, в котором кэш-контроллер запрашивает их из основной памяти. Как следствие, – мы имеем значительный падеж производительности, поскольку данные были загружены в холостую.
Интеллектуальный кэш-контроллер предсказывает адрес следующей запрашиваемой ячейки не по слепому шаблону, а на основе анализа предыдущих обращений. Исследуя последовательность кэш-промахов, контроллер пытается установить какой именно зависимостью связны ее элементы и, если это ему удается, предвычисляет ее последующие члены. Если обращение к памяти происходит по регулярному шаблону, интеллектуальная стратегия спекулятивной загрузки при благоприятном стечении обстоятельств может полностью ликвидировать задержки, возникающие при ожидании загрузки данных из основной памяти.
До недавнего прошлого интеллектуальные кэш-контроллеры использовались разве что в суперкомпьютерах и высокопроизводительных рабочих станциях, но теперь они реализованы в процессорах P-4 и AMD Athlon XP (см. "Оптимизация обращения к памяти и кэшу. Управление кэшированием в x86 процессорах старших поколений. Аппаратная предвыборка в микропроцессоре P-4")
Стратегии поиска данных. В соответствии с выбранной стратегией загрузка данных из памяти может начинаться либо после фиксации кэш-промаха (стратегия Look Through), либо осуществляться параллельно с проверкой наличия соответствующей копии данных в сверхоперативной памяти и прерываться в случае кэш-попадания (стратегия Look aside). Последнее сокращает накладные расходы на кэш-промахи, уменьшая тем самым латентность загрузки данных, но зато увеличивает энергопотребление, что в ряде случаев оказывается неприемлемо большой платой за в общем-то довольно незначительную прибавку производительности.
Отложенная запись данных. Наличие временного хранилища данных позволяет накапливать записываемые данные и затем, дождавшись освобождения системой шины, выгружать их в оперативную память "одним махом". Это ликвидирует никому не нужные задержки и значительно увеличивает производительность подсистемы памяти (подробнее об этом см. "Организация кэша. Политики записи и поддержка когерентности").
Механизм отложенной записи в x86 процессорах, реализован начиная с Pentium и AMD K6. Более ранние модели были вынужденные непосредственно записывать в основную память каждую модифицируемую ячейку, что серьезно ограничивало их быстродействие. К счастью, сегодня такие процессоры практически не встречаются и об этой проблеме уже можно забыть.
