Alasir Enterprises
Main Page >  Articles >  Принципы работы кэш-памяти  

 
Main Page
 
 
Reviews
 
Articles
 
Software
 
Reference
 
Motley
 
 
About Us
 
 
Принципы работы кэш-памяти

Павел Болотов
 
Дата публикации: 20 апреля 2007
Дата последнего изменения: 20 апреля 2007

Содержание:
in English

 
Индикаторы состояния строки

Логично предположить, что любая строка кэш-памяти должна обладать некой служебной информацией, описывающей её состояние. Например, как узнать, является ли некоторая строка действительной (т. е. содержит полезную информацию) или недействительной (т. е. заполненной мусором)? Для этого необходимо определиться с соответствующей политикой. Допустим, считать строку недействительной, если все биты поля тэгов и данных являются высокими, т. е. находятся в положении единиц. Впрочем, такой подход превратит жизнь любого контроллера кэш-памяти в ужас без конца. Допустим, контроллер получил запрос на чтение или запись некоторых данных, находящихся в оперативной памяти по определённому адресу. Он активирует все строки кэш-памяти с требуемым индексом и начинает проверять их биты тэгов и данных на построчной основе (последовательное логическое умножение, AND). Если в результате получилась единица, то данную строку следует рассматривать как недействительную. К примеру, если речь идёт о кэш-памяти размером в 256Кб с 16-канальной ассоциативностью и с 64-байтными строками, а кэшируемый диапазон определён в 4Гб, то при обслуживании каждого запроса в худшем случае потребуется обработать 288 тэговых бит и 8192 бит данных! Ситуация ухудшится ещё более при использовании алгоритмов целостности информации. Конечно же, такой подход не имеет никакой практической ценности. Даже если ограничиться проверкой лишь тэговых бит, обрекая последний сегмент памяти на некэшируемость, этот метод может найти лишь ограниченное применение. К слову, B-caches времён 486 и Pentium систем иногда проектировали подобным образом, но не стоит забывать о том, что они были с прямым отображением и их тэги были относительно небольшого размера. Таким образом, этот подход является исключением, а не правилом. В то же время ситуация меняется кардинальным образом при добавлении в модель кэш-памяти по одному биту на каждую строку, описывающему её состояние. Допустим, что строка считается действительной, если этот бит является высоким. Жизнь становится проще: теперь контроллеру незачем проверять что-либо ещё, чтобы определить состояние какой-либо строки.
 
Хотя бит действительности (validity bit) сам по себе является отличным решением, он может стать источником серьёзных проблем при случайном инвертировании. В реальной жизни вероятность того, что недействительная строка станет действительной, очень мала, но не исключена. Существует несколько способов предотвращения этого нежелательного происшествия, но самым простым из них можно считать добавление в пару к биту действительности ещё одного, хранящего его противоположное значение. Если при чтении обоих бит окажется, что они одинаковы, то сооветствующая строка должна быть признана недействительной. Вероятность изменения обоими битами своих значений на противоположные практически исключена, так как все известные на этой планете электромагнитные помехи однополярны.
 
Также весьма полезен бит изменённости (modified bit), иначе именуемый грязным битом (dirty bit), который является показателем того, является ли данная строка копией соответствующей строки в оперативной памяти или отличается от неё. Если этот бит отсутствует, то строка будет считаться неизменённой/чистой, а любая запись в неё будет также направляться в оперативную память. Такая кэш-память называется согласованной с оперативной памятью (memory coherent). В целом, подобная организация работы кэш-памяти не является особенно привлекательной из-за увеличения нагрузки на оперативную память. С другой стороны, уменьшаются накладные расходы при записи, так как любая неизменённая строка в кэш-памяти может быть заменена другой строкой без каких-либо дополнительных действий. В то же время любая изменённая строка не может быть вытеснена без предварительного копирования в низлежащий уровень кэш-памяти или в оперативную память из-за очевидной потери информации. Контроллер обязан отслеживать состояние этих строк, для чего и необходим бит изменённости. Кстати, D-caches и U-caches могут включать или не включать поддержку изменённых строк, в то время как I-caches всегда согласованы с оперативной памятью. Впрочем, возможность хранения изменённых строк в кэш-памяти без использования бит изменённости всё же существует, хотя этот подход и малопопулярен. Дело в том, что все строки кэш-памяти можно попросту считать изначально грязными вне зависимости от того, являются ли они таковыми на самом деле. Побочным эффектом такой авантюры будет очень большая нагрузка по записи на низлежащую кэш-память или оперативную память, поскольку каждая загруженная строка в такую кэш-память должна быть неминуемо выгружена назад через некоторое время. Некоторые наборы системной логики прошлого, такие как VIA Apollo VP2/97 (также известный как AMD-640) для процессоров Pentium-класса, поддерживали этот режим как опцию для B-cache с целью увеличения размера кэшируемого пространства оперативной памяти, но производительность всё же оставляла желать лучшего.
 
Третьим важным индикатором состояния строки кэш-памяти является бит общности (shared bit). Он служит для определения факта того, имеются ли копии данной строки в других кэшах, включая принадлежащие другим процессорам. Например, если один из процессоров изменит свою локальную копию, то другие процессоры должны быть поставлены в известность и предпринять действия по отношению к своим копиям. Для этой цели существуют два метода: Write Update (также известный как Write Broadcast) и Write Invalidate. Первый обязывает модифицирующий процессор отправить изменения другим процессорам, чтобы они смогли обновить свои копии. Второй метод отличается от первого тем, что вместо собственно изменений пересылается специальное сообщение, согласно которому другие процессоры должны изменить состояние своих копий на недействительное. В целом, Write Update утилизирует системную шину в значительно большей степени, чем Write Invalidate, поэтому хорошо подходит для систем с звездообразной топологией (star-based topology; также известной как топология "точка-точка" (point to point)), а особенно хорошо — для систем с прямыми межпроцессорными связями. С другой стороны, Write Invalidate оптимален для конфигураций с топологией общей шины (bus-based topology).
 
Используя вышеприведённую информацию, можно приступать к рассмотрению логических протоколов состояния и согласованности, которые формируют основу почти всех физических реализаций. Наиболее популярным считается MESI (Modified, Exclusive, Shared, Invalid):
 
Состояние бит 0 бит 1
Modified 1 0
Exclusive 0 1
Shared 1 1
Invalid 0 0

Этот протокол предполагает наличие двух физических бит для реализации всех четырёх возможных состояний. Строка с состоянием Invalid не содержит полезной информации, поэтому её можно рассматривать как пустую. Состояние Exclusive подразумевает, что информация в данной строке полностью соответствует оперативной памяти (так называемая чистая строка, clean line) и не содержится в других кэшах — данная копия в буквальном смысле эксклюзивна. Строка с состоянием Modified не соответствует оперативной памяти (так называемая грязная строка, dirty line) и также не имеет копий в других кэшах. Shared является чистая строка, которая может иметь копии в других кэшах (если точнее, то копии присутствовали в момент установки состояния, но могли исчезнуть со временем).
 
Протокол MESI несовершенен, но довольно прост и неплохо подходит для однопроцессорных конфигураций с одним или двумя уровнями кэш-памяти. Кратко рассмотрим механизм его работы на примере. Допустим, в D-cache была загружена свежая строка из оперативной памяти, которая получает состояние Exclusive. При её вытеснении другой строкой из D-cache в S-cache она сохраняет свой прежний статус. Когда она снова будет загружена в D-cache, её состояние изменится на Shared, равно как и состояние оставшейся в S-cache копии. При изменении хранящегося в D-cache клона возможны два эффективных варианта дальнейшего развития событий: а) изменения будут направлены как в S-cache, так и в оперативную память, а состояния обеих строк сохранятся как Shared; б) изменения не будут никуда направляться, строка в S-cache будет помечена как Invalid, а изменяемая в D-cache примет статус Modified. Прочие варианты являются значительно менее рациональными и здесь рассматриваться не будут.
 
Существуют несколько разновидностей протокола MESI, таких как MSI (Modified, Shared, Invalid), MOSI (Modified, Owned, Shared, Invalid), MOESI (Modified, Owned, Exclusive, Shared, Invalid) и MOWESI (Modified, Owned, Written, Exclusive, Shared, Invalid). Последние два наиболее многофункциональны, поэтому рассмотрим их более пристально. MOESI требует наличие уже трёх физических бит для реализации своих состояний, а его основным предназначением была ликвидация основного недостатка MESI, связанного с невозможностью хранения изменённых строк в более чем одной кэш-памяти. Для этого и было введено новое состояние, Owned, которое означает владение правами собственности на данную строку кэш-памяти, её клоны в других кэшах и в оперативной памяти. Эти права изначально принадлежат системной логике, на которой лежит обязанность по обеспечению всех агентов в системе (nota bene: подразумеваются не только процессоры, но и устройства типа bus master) верной информацией. Первым посягательством на эту обязанность стало состояние Modified, которое значительно усложнило жизнь системной логике. При каждом запросе агентом информации из кэшируемого пространства оперативной памяти системная логика была вынуждена его приостанавливать, затем генерировать запрос всем процессорам на предмет наличия соответствующей грязной строки в их кэшах. Если у одного из них имеется такая строка, то он был обязан записать её в оперативную память и изменить состояние на Exclusive. По окончании этой операции системная логика перезапускала изначальный запрос и доставляла информацию. Если бы поддержка состояния Modified отсутствовала, тогда кэши всех процессоров всегда были бы согласованны с оперативной памятью, а системной логике было бы незачем проводить какие-либо дополнительные мероприятия, так как она могла бы просто доставить запрашиваемую информацию непосредственно из оперативной памяти. Теперь о состоянии Owned. По предоставлении строке этого состояния процессор-хозяин берёт на себя все права и обязанности относительно неё у системной логики. Если какой-либо системный агент запросит эту строку, то процессор-хозяин обязан ответить и предоставить свою копию. Даже если системная логика активно участвует в этой операции, оперативная память не обновляется. Фактически, если состояние Modified можно представить как Exclusive Modified, то Owned — не иначе как Shared Modified. Если какая-либо строка становится Owned, то её копии в других кэшах, включая принадлежащие другим процессорам, должны иметь состояние Shared.
 
Однако, протокол MOESI также оказался неидеальным. Фактически, состояние Owned давало все преимущества процессору-хозяину, но ставило остальные процессоры в положение только для чтения. А если кому-нибудь из них было необходимо произвести запись в свою строку с состоянием Shared, то приходилось производить её и в оперативную память, что приводило к ликвидации состояния Owned у другого процессора. Это не представляет проблемы для большинства многопроцессорных сред, типично имеющих один активно записывающий процессор и несколько читающих процессоров на строку, но ситуация несколько иная в многопоточных средах, где разные процессоры или процессорные ядра могут одновременно выполнять разные потоки одного и того же процесса. Для улучшения производительности в этом случае и было введено состояние Written, которое привело к созданию протокола MOWESI. При записи в строку с состоянием Shared оно изменялось на Written, остальные процессоры оповещались о факте и обязывались ликвидировать или обновить свои устаревшие копии, после чего состояние строки изменялось на Modified или Owned соответственно. Обновления оперативной памяти удавалось избежать в обоих случаях. Поддержка этого протокола впервые появилась в 2-ядерном процессоре IBM POWER5.
 
Существуют многочисленные низкоуровневые протоколы состояния и согласованности, которые оперируют разными комбинациями индикаторов состояния, методами записи, шинного сигналирования и пр. Среди наиболее старых можно назвать Illinois, Write Once, Berkeley, DEC Firefly, Xerox Dragon. К примеру, большая часть систем на основе процессоров DEC Alpha использует MOESI-подобный протокол с поддержкой Write Invalidate, оперирующий битами tagCtlV (Valid), tagCtlS (Shared) и tagCtlD (Dirty), дополненных битом tagCtlP для реализации алгоритма чётного равенства (even parity). В нижеследующей таблице приводятся возможные комбинации смысловых бит с описанием соответствующих им состояний, а знак "x" означает, что состояние данного бита значения не имеет (nota bene: для однопроцессорных систем также поддерживается более простая реализация, не использующая tagCtlS, но о ней речь идти не будет).
 
Состояние tagCtlV tagCtlS tagCtlD
Invalid 0 x x
Clean 1 0 0
Dirty 1 0 1
Clean Shared 1 1 0
Dirty Shared 1 1 1

Состояния Clean и Dirty полностью соответствуют Exclusive и Modified из протоколa MOESI, равно как и состояние Invalid, однако Clean Shared и Dirty Shared несколько отличаются от Shared и Owned. При записи в строку с одним из этих состояний процессор всегда изменяет его на Clean и обновляет оперативную память, а другие процессоры удаляют свои устаревшие копии. Другими словами, строка со статусом Clean или Dirty может изменить его на Clean Shared и Dirty Shared соответственно, но Clean Shared не сможет стать Dirty Shared и наоборот.
 
<< Предыдущая страница Следующая страница >>

Copyright (c) Болотов Павел Владимирович, 2007. Все права сохранены.
Полная или частичная перепечатка без разрешения автора запрещена.
 
Designed and maintained by Alasir Enterprises, 1999-2007
rhett from alasir.com, walter from alasir.com