Стратегия размещения.
На сложность этого механизма существенное влияние оказывает стратегия размещения, определяющая, в какое место кэш-памяти следует поместить каждый блок из основной памяти. В зависимости от способа размещения данных основной памяти в кэш-памяти существует три типа кэш-памяти:
кэш с прямым отображением (размещением);
полностью ассоциативный кэш;
множественный ассоциативный кэш или частично-ассоциативный.
Кэш с прямым отображением (размещением) является самым простым типом буфера. Адрес памяти однозначно определяет строку кэша, в которую будет помещен блок информации. При этом предпо- лагается, что оперативная память разбита на блоки и каждому та- кому блоку в буфере отводится всего одна строка. Это простой и недорогой в реализации способ отображения. Основной его недостаток – жесткое закрепление за определенными блоками ОП одной строки в кэше. Поэтому, если программа поочередно обращается к словам из двух различных блоков, отображаемых на одну и ту же строку кэш-памяти, постоянно будет происходить обновление данной строки и вероятность попадания будет низкой.
Кэш с полностью ассоциативным отображением позволяет преодолеть недостаток прямого, разрешая загрузку любого блока ОП в любую строку кэш-памяти. Логика управления выделяет в адресе ОП два поля: поле тега и поле слова. Поле тега совпадает с адресом блока ОП. Для проверки наличия копии блока в кэш-памяти, логика управления кэша должна одновременно проверить теги всех строк на совпадение с полем тега адреса. Ассоциативное отображение обеспечивает гибкость при выборе строки для вновь записываемого блока. Принципиальный недостаток этого способа – в необходимости использования дорогой ассоциативной памяти.
Множественно-ассоциативный тип или частично-ассоциативный тип отображения – это один из возможных компромиссов, сочетающий достоинства прямого и ассоциативного способов. Кэш-память ( и тегов и данных) разбивается на некоторое количество модулей. Зависимость между модулем и блоками ОП такая же жесткая, как и при прямом отображении. А вот размещение блоков по строкам модуля произвольное и для поиска нужной строки в пределах модуля используется ассоциативный принцип. Этот способ отображения наиболее широко распространен в современных микропроцессорах.
Отображение секторов ОП в кэш-памяти.
Данный тип отображения применяется во всех современных ЭВМ и состоит в том, что вся ОП разбивается на секторы, состоящие из фиксированного числа последовательных блоков. Кэш-память также разбивается на секторы, содержащие такое же количество строк. Расположение блоков в секторе ОП и секторе кэша полностью совпадает. Отображение сектора на кэш-память осуществляется ассоциативно, те любой сектор из ОП может быть помещен в любой сектор кэша. Таким образом, в процессе работы АЛУ обращается в поисках очередной команды к ОП, в результате чего, в кэш загружается( в случае отсутствия там блока, содержащего эту команду), целый сектор информации из ОП, причем по принципу локальности, за счет этого достигается значительное увеличение быстродействия системы.
Иерархическая модель кэш-памяти
Как правило, кэш-память имеет многоуровневую архитектуру. Например, в компьютере с 32 Кбайт внутренней (в ядре ЦП) и 1 Мбайт внешней (в корпусе ЦП или на системной плате) кэш-памяти первая будет считаться кэш-памятью 1-го уровня (L1), а вторая - кэш-памятью 2-го уровня (L2). В современных серверных системах количество уровней кэш-памяти может доходить до четырех, хотя наиболее часто используется двух- или трехуровневая схема.
В некоторых процессорных архитектурах кэш-память 1-го уровня разделена на кэш команд (Instruction Cache, I-cache) и кэш данных (Data Cache, D-cache), причем необязательно одинаковых размеров. С точки зрения схемотехники проще и дешевле проектировать раздельные I-cache и D-cache: выборку команд проводит I-box, а выборку данных - Е-box и F-box, хотя в обоих случаях задействуются А-box и С-box. Все эти блоки велики, и обеспечить им одновременный и быстрый доступ к одному кэшу проблематично. Кроме того, это неизбежно потребовало бы увеличения количества портов доступа, что также усложняет задачу проектирования.
Так как I-cache и D-cache должны обеспечивать очень низкие задержки при доступе (это справедливо для любого кэша L1), приходится жертвовать их объемом - обычно он составляет от 16 до 32 Кбайт. Ведь чем меньше размер кэша, тем легче добиться низких задержек при доступе.
Кэш-память 2-го уровня, как правило, унифицирована, т. е. может содержать как команды, так и данные. Если она встроена в ядро ЦП, то говорят о S-cache (Secondary Cache, вторичный кэш), в противном случае - о B-cache (Backup Cache, резервный кэш). В современных серверных ЦП объем S-cache составляет от одного до нескольких мегабайт, a B-cache - до 64 Мбайт. Если дизайн ЦП предусматривает наличие встроенной кэш-памяти 3-го уровня, то ее именуют T-cache (Ternary Cache, третичный кэш). Как правило, каждый последующий уровень кэш-памяти медленнее, но больше предыдущего по объему. Если в системе присутствует B-cache (как последний уровень модели кэш-памяти), то он может контролироваться как ЦП, так и набором системной логики.
Если в момент выполнения некоторой команды в регистрах не окажется данных для нее, то они будут затребованы из ближайшего уровня кэш-памяти, т. е. из D-cache. В случае их отсутствия в D-Cache запрос направляется в S-cache и т. д. В худшем случае данные будут доставлены непосредственно из памяти. Впрочем, возможен и еще более печальный вариант, когда подсистема управления виртуальной памятью операционной системы (ОС) успевает вытеснить их в файл подкачки на жесткий диск. В случае доставки из оперативной памяти потери времени на получение нужных данных могут составлять от десятков до сотен тактов ЦП, а в случае нахождения данных на жестком диске речь уже может идти о миллионах тактов.
Ассоциативность кэш-памяти
Одна из фундаментальных характеристик кэш-памяти - уровень ассоциативности - отображает ее логическую сегментацию. Дело в том, что последовательный перебор всех строк кэша в поисках необходимых данных потребовал бы десятков тактов и свел бы на нет весь выигрыш от использования встроенной в ЦП памяти. Поэтому ячейки ОЗУ жестко привязываются к строкам кэш-памяти (в каждой строке могут быть данные из фиксированного набора адресов), что значительно сокращает время поиска. С каждой ячейкой ОЗУ может быть связано более одной строки кэш-памяти: например, n-канальная ассоциативность (n-way set associative) обозначает, что информация по некоторому адресу оперативной памяти может храниться в п мест кэш-памяти.
Выбор места может проводиться по различным алгоритмам, среди которых чаще всего используются принципы замещения LRU (Least Recently Used, замещается запись, запрошенная в последний раз наиболее давно) и LFU (Least Frequently Used, запись, наименее часто запрашиваемая), хотя существуют и модификации этих принципов. Например, полностью ассоциативная кэшпамять (fully associative), в которой информация, находящаяся по произвольному адресу в оперативной памяти, может быть размещена в произвольной строке. Другой вариант - прямое отображение (direct mapping), при котором информация, которая находится по произвольному адресу в оперативной памяти, может быть размещена только в одном месте кэш-памяти. Естественно, этот вариант обеспечивает наибольшее быстродействие, так как при проверке наличия информации контроллеру придется "заглянуть" лишь в одну строку кэша, но и наименее эффективен, поскольку при записи контроллер не будет выбирать "оптимальное" место. При одинаковом объеме кэша схема с полной ассоциативностью будет наименее быстрой, но наиболее эффективной.
Полностью ассоциативный кэш встречается на практике, но, как правило, у него очень небольшой объем. Например, в ЦП Cyrix 6x86 использовалось 256 байт такого кэша для команд перед унифицированным 16-или 64-Кбайт кэшем L1. Часто полноассоциативную схему применяют при проектировании TLB (о них будет рассказано ниже), кэшей адресов переходов, буферов чтения-записи и т. д. Как правило, уровни ассоциативности I-cache и D-cache довольно низки (до четырех каналов) - их увеличение нецелесообразно, поскольку приводит к увеличению задержек доступа и в итоге негативно отражается на производительности. В качестве некоторой компенсации увеличивают ассоциативность S-cache (обычно до 16 каналов), так как задержки при доступе к этому кэшу неважны. Например, согласно результатам исследований часто используемых целочисленных задач, у Intel Pentium III 16 Кбайт четырехканального D-cache было достаточно для покрытия около 93% запросов, а 16-Кбайт четырехканального I-cache - 99% запросов.
Размер строки и тега кэш-памяти
Немаловажная характеристика кэш-памяти - размер строки. Как правило, на одну строку полагается одна запись адреса (так называемый тег), которая указывает, какому адресу в оперативной памяти соответствует данная линия. Очевидно, что нумерация отдельных байтов нецелесообразна, поскольку в этом случае объем служебной информации в кэше в несколько раз превысит объем самих данных. Поэтому один тег обычно полагается на одну строку, размер которой обычно 32 или 64 байта (реально существующий максимум 1024 байта), и эквивалентен четырем (иногда восьми) разрядностям системной шины данных. Кроме того, каждая строка кэш-памяти сопровождается некоторой информацией для обеспечения отказоустойчивости: одним или несколькими битами контроля четности (parity) или восемью и более байтами обнаружения и коррекции ошибок (ЕСС, Error Checking and Correcting), хотя в массовых решениях часто не используют ни того, ни другого.
Размер тега кэш-памяти зависит от трех основных факторов: объема кэш-памяти, максимального кэшируемого объема оперативной памяти, а также ассоциативности кэш-памяти. Математически этот размер рассчитывается по формуле:
Stag=log2(Smem*A/Scache),
где Stag - размер одного тега кэш-памяти, в битах; Smem - максимальный кэшируемый объем оперативной памяти, в байтах; Scache - объем кэш-памяти, в байтах; А - ассоциативность кэш-памяти, в каналах.
Отсюда следует, что для системы с 1-Гбайт оперативной памятью и 1-Мбайт кэш-памятью с двухканальной ассоциативностью потребуется 11 бит для каждого тега. Примечательно, что собственно размер строки кэш-памяти никак не влияет на размер тега, но обратно пропорционально влияет на количество тегов. Следует понимать, что размер строки кэш-памяти не имеет смысла делать меньше разрядности системной шины данных, но многократное увеличение размера приведет к чрезмерному засорению кэш-памяти ненужной информацией и излишней нагрузке на системную шину и шину памяти. Кроме того, максимально кэшируемый объем кэш-памяти не обязан соответствовать максимально возможному устанавливаемому объему оперативной памяти в системе. Если возникнет ситуация, когда оперативной памяти окажется больше, чем может быть кэшировано, то в кэш-памяти будет присутствовать информация только из нижнего сегмента оперативной памяти. Именно такой была ситуация с платформой Socket7/Super7. Наборы микросхем для этой платформы позволяли использовать большие объемы оперативной памяти (от 256 Мбайт до 1 Гбайт), в то время как кэшируемый объем часто был ограничен первыми 64 Мбайт (речь идет о B-cache, находящемся на системной плате) по причине использования дешевых 8-бит микросхем теговой SRAM (2 бита из которых резервировалось под указатели действительности и измененности строки). Это приводило к ощутимому падению производительности.
Какая информация содержится в тегах кэш-памяти? Это информация об адресах, но как можно точно отобразить расположение строки кэш-памяти на всем пространстве кэшируемого объема оперативной памяти, используя столь незначительное количество адресных битов? Это понятие является фундаментальным в понимании принципов функционирования кэш-памяти. Рассмотрим предыдущий пример, с 11-бит тегами. Учитывая логическое сегментирование благодаря двухканальной ассоциативности, можно рассматривать данную кэш-память как состоящую из двух независимых сегментов по 512 Кбайт каждый. Представим оперативную память как состоящую из "страниц" по 512 Кбайт каждая - их будет соответственно 2048 штук. Далее, Iog2 (2048) = 11 (основание логарифма равно 2, так как возможны только два логических состояния каждого бита). Это означает, что фактически тег - не номер отдельной строки кэш-памяти, а номер "страницы" памяти, на которую отображается та или иная строка. Другими словами, в пределах "страницы" сохраняется прямое соответствие ее "строк" с соответствующими строками кэш-памяти, т. е. п-я строка кэш-памяти соответствует n-й "строке" данной "страницы" оперативной памяти.
Рассмотрим механизм работы кэш-памяти разных видов ассоциативности. Допустим, имеется абстрактная модель с восемью строками кэш-памяти и 64 эквивалентными строками оперативной памяти. Требуется поместить в кэш строку 9 оперативной памяти (заметим, что все строки нумеруются от нуля и по возрастающей). В модели с прямым отображением эта строка может занять только одно место: 9 mod 8=1 (вычисление остатка от деления нацело), т. е. место строки 1. Если взять модель с двухканальной ассоциативностью, то эта строка может занять одно из двух мест: 9 mod 4=1, т. е. строку 1 любого канала (сегмента). Полноассоциативная модель предоставляет свободу для размещения, и данная строка может занять место любой из восьми имеющихся. Другими словами, фактически имеется 8 каналов, каждый из которых состоит из 1 строки.
Ни одна из вышеуказанных моделей не позволит, разумеется, поместить в кэш больше строк, чем он физически в состоянии разместить, они лишь предлагают различные варианты, различающиеся балансом эффективности использования кэша и скорости доступа к нему.
Типы подключения кэш-памяти
Количество портов чтения-записи кэш-памяти - показатель того, сколько одновременных операций чтения-записи может быть обработано. Хотя жестких требований и нет, определенное соответствие набору функциональных устройств ЦП должно прослеживаться, так как отсутствие свободного порта во время исполнения команды приведет к вынужденному простою.
Существует два основных способа подключения кэшпамяти к ЦП для чтения: сквозной и побочный (Look-Through и Look-Aside). Суть первого в том, что при необходимости данные сначала запрашиваются у контроллера кэш-памяти самого высокого уровня, который проверяет состояние подключенных тегов и возвращает либо нужную информацию, либо отрицательный ответ, и в этом случае запрос перенаправляется в более низкий уровень иерархии кэш-памяти или в оперативную память. При реализации второго способа чтения запрос одновременно направляется как кэш-контроллеру самого высокого уровня, так и остальным кэш-контроллерам и контроллеру оперативной памяти. Недостаток первого способа очевиден: при отсутствии информации в кэше высокого уровня приходится повторять запрос, и время простоя ЦП увеличивается. Недостаток второго подхода - высокая избыточность операций и, как следствие, "засорение" внутренних шин ЦП и системной шины ненужной информацией. Логично предположить, что если для кэшей L1 оптимальна сквозная схема, то для T-cache или B-cache побочная схема может оказаться более выгодной. Для S-cache выбор неоднозначен.
Различают также локальный и удаленный кэш. Локальным называют кэш, находящийся либо в ядре ЦП, либо на той же кремниевой подложке или в корпусе ЦП, удаленным - размещенный на системной плате. Соответственно локальным кэшем управляет контроллер в ядре ЦП, а удаленным - НМС системной платы. Локальный кэш с точки зрения быстродействия предпочтительнее, так как интерфейс к удаленному кэшу обычно мультиплексируется с системной шиной. С одной стороны, когда другой ЦП захватывает общую системную шину или какой-либо периферийный контроллер обращается к памяти напрямую, удаленный кэш может оказаться временно недоступным. С другой - такой кэш легче использовать в многопроцессорных системах.
Существуют два распространенных способа записи в кэш: сквозной (Write-Through) и обратной (Write-Back) записи. В первом случае информация одновременно сохраняется как в текущий, так и в более низкий уровень иерархии кэш-памяти (или прямо в оперативную память при отсутствии такового). Во втором - данные сохраняются только в текущем уровне кэш-памяти, при этом возникает ситуация, когда информация в кэше и оперативной памяти различается, причем последняя становится устаревшей. Для того чтобы при сбросе кэша информация не была необратимо потеряна, к каждой строке кэша добавляется "грязный" бит (dirty bit, иначе известный как modified). Он нужен для обозначения того, соответствует ли информация в кэше информации в оперативной памяти, и следует ли ее записать в память при сбросе кэша.
Также следует упомянуть способ резервирования записи (write allocation). При записи данных в оперативную память часто возникает ситуация, когда записываемые данные могут скоро понадобиться, и тогда их придется довольно долго подгружать. Резервирование записи позволяет частично решить эту проблему: данные записываются не в оперативную память, а в кэш. Строка кэша, вместо которой записываются данные, полностью выгружается в оперативную память. Так как вновь записанных данных обычно недостаточно для формирования полной строки кэша, из оперативной памяти запрашивается недостающая информация. Когда она получена, новая строка записывается, и тег обновляется. Определенных преимуществ или недостатков такой подход не имеет - иногда это может дать незначительный прирост производительности, но также и привести к засорению кэша ненужной информацией.
Сегментирование кэш-памяти и быстродействие жестких дисков
В первой части данного обзора мы познакомились с режимом Performance Mode у SCSI-дисков Seagate Cheetah со скоростью вращения 10 000 и 15 000 об./мин — Cheetah 10K.7 и Cheetah 15K.4. Напомню, что утилита Seagate SeaTools Enterprise позволяет пользователю управлять политикой кэширования и, в частности, переключать новейшие SCSI-диски Seagate между двумя разными моделями кэширования — Desktop Mode и Server Mode. Этот пункт в меню SeaTools носит название Performance Mode (PM) и может принимать два значения — On (Desktop Mode) и Off (Server Mode). Отличия между этими двумя режимами чисто программные — в случае Desktop Mode кэш-память жесткого диска разбивается на фиксированное число сегментов постоянного (одинакового) объема и далее они используются для кэширования обращений при чтении и записи. Причем, в отдельном пункте меню пользователь даже может сам назначать количество сегментов (управлять сегментированием кэша): например, вместо дефолтных 32-х сегментов проставить другое значение (при этом объем каждого сегмента пропорционально уменьшится).
В случае же Server Mode сегменты буфера (кэша диска) могут динамически (пере)назначаться, меняя при этом свой размер и количество. Микропроцессор (и микропрограмма) диска сами динамически оптимизируют количество (и емкость) сегментов кэш-памяти в зависимости от поступающих для исполнения на диск команд.
Тогда мы смогли выяснить, что использование новых накопителей Seagate Cheetah в режиме «Desktop» (при фиксированном сегментировании по умолчанию — на 32 сегмента) вместо дефолтного «Server» с динамическим сегментированием способно немного поднять производительность дисков в ряде задач, более характерных для настольного компьютера или медиа-серверов. Причем, эта прибавка порой может достигать 30-100% (!) в зависимости от типа задачи и модели диска, хотя в среднем она оценивается величиной 30%, что, согласитесь, тоже неплохо. Среди таких задач — рутинная работа настольного ПК (тесты WinBench, PCmark, H2bench), чтение и копирование файлов, дефрагментация. При этом в чисто серверных приложениях производительность накопителей почти не падает (если и падает, то незначительно). Впрочем, заметный выигрыш от использования Desktop Mode мы смогли наблюдать только на диске Cheetah 10K.7, тогда как ее старшей сестрице Cheetah 15K.4 оказалось почти все равно, в каком из режимов работать над настольными приложениями.
Пытаясь разобраться дальше, как влияет сегментирование кэш-памяти этих жестких дисков на производительность в различных приложениях и какие режимы сегментирования (какое количество сегментов памяти) более выгодно при выполнении тех или иных задач, я исследовал влияние количества сегментов кэш-памяти на производительность диска Seagate Cheetah 15K.4 в широком диапазоне значений — от 4 до 128 сегментов (4, 8, 16, 32, 64 и 128). Результаты этих исследований и предлагаются вашему вниманию в этой части обзора. Подчеркну, что данные результаты интересны не только сугубо для этой модели дисков (или SCSI-дисков Seagate в целом) — сегментирование кэш-памяти и выбор количества сегментов — это одно из основных направлений оптимизации firmware, в том числе, настольных дисков с интерфейсом ATA, которые сейчас также оснащаются преимущественно буфером 8 Мбайт. Поэтому описанные в данной статье результаты производительности накопителя в различных задачах в зависимости от сегментирования его кэш-памяти имеют отношение и к индустрии настольных ATA-накопителей. А поскольку методика испытаний была описана в первой части, переходим непосредственно к самим результатам.
Впрочем, прежде, чем перейти к обсуждению результатов, взглянем чуть подробнее на устройство и работу сегментов кэш-памяти диска Seagate Cheetah 15K.4, чтобы лучше понимать, о чем идет речь. Из восьми мегабайт для собственно кэш-памяти (то есть для кэширующих операций) здесь доступно 7077 Кбайт (остальное — служебная область). Эта область делится на логические сегменты (Mode Select Page 08h, byte 13), которые используются для чтения и записи данных (для осуществления функций упреждающего чтения с пластин и отложенной записи на поверхность диска). Для обращения к данным на магнитных пластинах сегменты используют именно логическую адресацию блоков накопителя. Диски этой серии поддерживают максимум 64 сегмента кэш-памяти, причем длина каждого сегмента равна целому числу секторов диска. Объем доступной кэш-памяти, по всей видимости, распределяется поровну между сегментами, то есть если сегментов, скажем, 32, то объем каждого сегмента равен примерно 220 Кбайт. При динамической сегментации (в режиме PM=off) количество сегментов может меняться винчестером автоматически в зависимости от потока команд от хоста.
Приложения для серверов и настольных компьютеров требуют различных операций кэширования от дисков для обеспечения оптимальной производительности, поэтому сложно обеспечить единую конфигурацию для наилучшего выполнения этих задач. По мнению Seagate, для «настольных» приложений требуется сконфигурировать кэш-память так, чтобы быстро отвечать на повторяющиеся запросы большого количества небольших сегментов данных без задержек на упреждающее чтение смежных сегментов. В серверных задачах, напротив, требуется так сконфигурировать кэш, чтобы обеспечить поступление больших объемов последовательных данных в неповторяющихся запросах. В этом случае более важна способность кэш-памяти хранить больше данных из смежных сегментов при упреждающем чтении. Поэтому для Desktop Mode производитель рекомендует использовать 32 сегмента (в ранних версиях Cheetah использовались 16 сегментов), а для Server Mode адаптивное количество сегментов стартует всего с трех на весь кэш, хотя в процессе работы может и увеличиваться. Мы в своих экспериментах по поводу влияния количества сегментов на производительность в различных приложениях ограничимся диапазоном от 4 сегментов до 64 сегментов, а в качестве проверки «прогоним» диск также при 128 сегментах, установленных в программе SeaTools Enterprise (программа при этом не сообщает, что данное количество сегментов в этом диске недопустимо).
Увеличение производительности кэш-памяти
Формула для среднего времени доступа к памяти в системах с кэш-памятью выглядит следующим образом:
Среднее время доступа = Время обращения при попадании + Доля промахов x Потери при промахе
Эта формула наглядно показывает пути оптимизации работы кэш-памяти: сокращение доли промахов, сокращение потерь при промахе, а также сокращение времени обращения к кэш-памяти при попадании. На рисунке 5.38 кратко представлены различные методы, которые используются в настоящее время для увеличения производительности кэш-памяти. Использование тех или иных методов определяется прежде всего целью разработки, при этом конструкторы современных компьютеров заботятся о том, чтобы система оказалась сбалансированной по всем параметрам.