К. Касперски - Техника оптимизации программ, Эффективное использование памяти (1127752), страница 52
Текст из файла (страница 52)
Выражение "кэшконтроллер обратился к кэш-линейке )Ча 69" лишено смысла и правильнее сказать: "кэш-контроллер, обратился к кэш-линейке 999", где 999 — содержшиое связанного с ней тэта. Таким образом, полезная емкость кэш-памяти всегда меньше ее полной (физической) емкости, т. к.
некоторая часть ячеек расходуется на создание тэгов, совокупность которых так и называется плмягль глэгов (остальные ячейки образуют лаиять кэш-строк). Следует заметить, что производители всегда указывают именно полезную, а не полную емкость кэш-памяти, поэтому за память, "отьедаемую" тэгами, можно не волноваться.
Блокируеиая и неблокируемая кэш-память Существуют две основные разновидности сверхоперативной памяти: блокивуемая кэгя-память и неблокируемая. Странно, но расшифровка этого термина во многих популярных изданиях отсутствует (я, например, впервые обнаружил ее в технической документации по процессору АМ(э К5), поэтому имеет смыл рассмотреть этот вопрос поподробнее. Блокируемая кэш память, как и следует из ее названия, блокирует доступ к кашу после всякого кэш-промаха. Независимо от того, присутствуют ли запрашиваемые данные в сверхоперативной памяти или нет, до тех пор, пока кэш-строка, вызвавшая промах, не будет целиком загружена (выгружена), кэш не сможет обрабатывать никакие другие запросы ("л ген лг! ог лцгх и!гег а геог! тгзв ха!!э илб! гле рпог тт !)))х гле сасЬе", — как говорят англичане).
В настоящее время блокируемая кэш-память практически не используется, поскольку при частных кэш-промахах она работает крайне непроизводительно, Неблокируемая кэш память, напротив, позволяет работать с кэшем параллельно с загрузкой (выгрузкой) кэш-строк. То есть кэш-промахи не препятствует кэш-попаданиям. И это — хорошо! Несмотря на то, что неблокируемая кэш память имеет значительно большую аппаратную сложность (а, значит, и стоимость), в силу своей привлекательности она широко используется в старших процессорах семейства х86, как, впрочем, и во многих других современных процессорах. Глава 3 Понятие ассоциативности каша Проследим по шагам как работает кэш. Вот процессор обращается к ячейке памяти с адресом хуг. Кзш-контроллер, перехватив это обращение, первым делом пытается выяснить: присутствуют ли запрошенные данные в кэшпамяти или нет? Вот тут-то и начинается самое интересное! Легко показать, что проверка наличия ячейки в кэш-памяти фактически сводится к поиску соответствующего диапазона адресов в памяти тэгов.
В зависимости от архитектуры кзш-контроллера просмотр всех тзгов осуществляется либо параллельно, либо они последовательно перебираются один за другим. Параллельный поиск, конечно, чрезвычайно быстр, но вместе с тем и сложен в реализации (а потому — дорог). Последовательный же просмотр при большом количестве тэгов крайне непроизводителен. Кстати, а сколько у нас тэгов? Правильно — ровно столько, сколько и кэш-строк. Так, в частности, в 32-килобайтовом кэше насчитывается немногим более тысячи гэгов. Стоп! Сколько времени потребует просмотр тысячи тзгов?! Даже если несколько тэгов будут просматриваться за один такт, поиск нужной нам линейки растянется на сотни тактов, что "съест" весь выигрыш в производительности.
Нет уж, какая динамическая память ни тормозная, а к ней обратиться побыстрее будет, чем сканировать такой кэш. Но ведь кэш все-таки работает! Спрашивается; как? Оказывается (и это следовало ожидать), что последовательный поиск — не самый "продвинутый" алгоритм поиска. Существуют и более элегантные решения. Рассмотрим два наиболее популярных из них. В кэше прямого отображения проблема поиска решается так: пусть каждая ячейка памяти соответствует не любой, а одной строго определенной строке каша.
В свою очередь, каждой строке кэша будет соответствовать не одна, а множество ячеек кэшируемой памяти, но, опять-таки, не любых, а строго определенных. Пусть наш кэш состоит из четырех строк, тогда (рис. 3.10) первый пакет кэшируемой памяти связан с первой строкой кэша, второй — со второй, третий — с третьей, четвертый — с четвертой, а пятый — вновь с первой! Достаточно очевидно, что адреса ячеек кэшируемой памяти связаны с номерами кэш-строк следующим отношением: А1313й о САСНЕ.ЫЕЕ САСНЕ.).1ХЕ.ЫЕЕ САСНЕ.).1ХЕ.ЫХЕ где Аà — условный номер кэш-линейки, А(31)К вЂ” адрес ячейки кэшируемой памяти; САСНЕ.1.1ХЕ.ЫЕŠ— длина кэш-линейки в байтах; САСНЕ.ЫУЕ— размер кэш-памяти в байтах; "—" — операция целочисленного деления. Необходимость просматривать все тэги в этой схеме естественным образом отпадает.
Да, отпадает, но возникает другая проблема. Задумайтесь, что произойдет, если процессор попытается последовательно обратиться ко второй, шестой и десятой ячейкам кэшируемой памяти? Правильно — несмотря на то, что в кэше будет полно свободных строк, каждая очередная ячейка будет вытеснять предыдущую, т.
к. все они жестко закреплены именно за второй строкой кэша. В результате кэш будет работать максимально неэффективно, полностью вхолостую ((гайто. Программист, заботящийся об оптимизации своих программ, должен организовать структуры данных так, чтобы исключить частое чтение ячеек памяти с адресами, кратными размеру кэша. Понятное дело — такое требование не всегда выполнимо и кэш прямого отображения обеспечивает далеко не лучшую производительность.
Поэтому в настоящее время он практически нигде не встречается и полностью вытеснен наборно-ассоциативной сверхоперативной памятью. Рис. 3.10. Устройство кэша прямого отображения Таким образом, чтобы узнать: присутствует ли искомая ячейка в кэшпамяти или нет, достаточно просмотреть всего один-единственный тэг соответствующей кэш-линейки, для вычисления номера которого требуется совершить всего три арифметические операции (поскольку длина кэш-линеек и размер кэш-памяти всегда представляют собой степень двойки, операции деления и взятия остатка допускают эффективную и простую аппаратную реализацию). гбг Глава 3 Наборио-ассоциативный кэш состоит из нескольких независимых банков, каждый из которых представляет собой самостоятельный кэш прямого отображения.
Взгляните на рис. 3.! !. Видите, каждая ячейка кэшируемой памяти может быть сохранена в любой из двух строк кэш-памяти. Допустим, процессор читает шестую и десятую ячейки кзшируемой памяти. Шестая ячейка идет во вторую строку первого банка, в десятая — во вторую строку следуюшего банка, т. к.
первый уже занят. Кзаирувмвя память Кзв Рис. 3.11. Устройство нвбсрно-всссцнатнвногс кэшв Количество банков кэша и называют его ассоциаошвностью (юау). Легко видеть, что с увеличением степени ассошгативности, эффективность каша существенно возрастает (редкие исключения из этого правила рассмотрены в разд. "Влияние размера обрабатываемых данных на производительность" этой главы). В идеале, при наивысшей степени дробления в каждом банке будет только одна линейка, и тогда любая ячейка кзшируемой памяти сможет быть сохранена в любой строке каша. Такой кэш называют полностью ассойиативным кэюем или просто ассоциативным кэшем. Ассоциативность кэш-памяти, используемой в современных персональных компьютерах, колеблется от двух (2-туау сасйе) до восьми (8-туау сасйе), а чаше всего равна четырем (4-вау сас(зе).
Политики записи и поддержка когерентности Если бы ячейки памяти были доступны только на чтение, то их копия, паходягцаяся в кзш-памяти, всегда совпадала бы с оригиналом. Возможность Кэш гбЗ записи (ну, какая же программа обходится без операций записи?) рождает следующие проблемы: во-первых, кэш-контроллер должен отслеживать модификацию ячеек кэш-памяти, выгружая в основную память модифицированные ячейки при их замещении, а, во-вторых, необходимо как-то отслеживать обращения всех периферийных устройств (включая остальные микропроцессоры в многопроцессорных системах) к основной памяти.
В противном случае мы рискуем считать совсем не то, что записывали! Кэш-контроллер обязан обеспечивать когерентность (сойегепсу) — согласованность кэш-памяти с основной памятью. Допустим, к некоторой ячейке памяти, уже модифицированной в кэше, но еще не выгруженной в основную память, обращается периферийное устройство (или другой процессор) — кэш-контроллер должен немедленно обновить основную память, иначе оттуда считаются "старые" данные. Аналогично, если периферийное устройство (другой процессор) модифицирует основную память, например посредством 0МА (Бйгесг Мепюгу Ассезз, прямого доступа к памяти), кэшконтроллер должен выяснить — загружены ли модифицированные ячейки в его кэш-память, и если да — обновить соотвествующие им ячейки оперативной памяти.
Поддержка когерентности — задача серьезная. Самое простое (но не самое лучшее) решение, мгновенно приходящее на ум, — это кэшировать ячейки основной памяти только для чтения, а запись осуществлять напрямую, минуя кэш, сразу в основную память. Это, так называемая, сквозная (%Т— %гйе Тгце чт)ге ро11су) политика, или, иначе, режим сквозной записи. Сквозная политика легка в аппаратной реализации, но крайне неэффективна. Частично компенсировать задержки обращения к памяти помогает буферизация.
Записываемые данные на первом этапе попадают не в основную память, а в специальный буфер записи (згоге/итие биЯеГ), размером порядка 32 байт. Там они накапливаются до тех пор, пока буфер целиком не заполнится или не освободится шина, а затем все содержимое буфера записывается в память "одним скопом". Такой режим сквозной записи с бу4еризацией (%С вЂ” %пге СогпЬ(п(пя ъпге ро11су) значительно увеличивает производительность системы, но решает далеко не все проблемы. В частности, значительная часть процессорного времени по-прежнему расходуется именно на выгрузку буфера в основную память.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
