ПОД (пособие) (1184372), страница 17
Текст из файла (страница 17)
Как правило для замещения блоков применяются две основных стратегии:случайная и LRU.В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираютсяслучайно. В некоторых системах, чтобы получить воспроизводимое поведение, котороеособенно полезно во время отладки аппаратуры, используют псевдослучайный алгоритмзамещения.Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скороможет потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, которыйне использовался дольше всех (LRU - Least-Recently Used).Достоинство случайного способа заключается в том, что его проще реализовать ваппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритмLRU становится все более дорогим и часто только приближенным.
На рисунке 3.22показаны различия в долях промахов при использовании алгоритма замещения LRU ислучайного алгоритма. Ассоциативность: 2-канальная 4-канальная 8-канальнаяСравнение долей промахов для алгоритма LRU и случайного алгоритма замещенияпри нескольких размерах кэша и разных ассоциативностях при размере блока 16 байтРазмер кэш-памяти LRU Random LRU Random LRU Random16 KB5.18% 5.69% 4.67% 5.29% 4.39% 4.96%64 KB1.88% 2.01% 1.54% 1.66% 1.39% 1.53%256 KB1.15% 1.17% 1.13% 1.13% 1.12% 1.12%Стратегии записи в кэш-память.При обращениях к кэш-памяти на реальных программах преобладают обращения почтению. Все обращения за командами являются обращениями по чтению и большинствокоманд не пишут в память.
Обычно операции записи составляют менее 10% общеготрафика памяти. Желание сделать общий случай более быстрым означает оптимизациюкэш-памятидлявыполненияоперацийчтения,однакоприреализациивысокопроизводительной обработки данных нельзя пренебрегать и скоростью операцийзаписи.К счастью, общий случай является и более простым. Блок из кэш-памяти может бытьпрочитан в то же самое время, когда читается и сравнивается его тег.
Таким образом, чтение52блока начинается сразу как только становится доступным адрес блока. Если чтениепроисходит с попаданием, то блок немедленно направляется в процессор. Если жепроисходит промах, то от заранее считанного блока нет никакой пользы, правда нет иникакого вреда.Однако при выполнении операции записи ситуация коренным образом меняется. Именнопроцессор определяет размер записи (обычно от 1 до 8 байтов) и только эта часть блокаможет быть изменена. В общем случае это подразумевает выполнение над блокомпоследовательности операций чтение-модификация-запись: чтение оригинала блока,модификацию его части и запись нового значения блока.
Более того, модификация блока неможет начинаться до тех пор, пока проверяется тег, чтобы убедиться в том, что обращениеявляется попаданием. Поскольку проверка тегов не может выполняться параллельно сдругой работой, то операции записи отнимают больше времени, чем операции чтения.Очень часто организация кэш-памяти в разных машинах отличается именно стратегиейвыполнения записи. Когда выполняется запись в кэш-память имеются две базовыевозможности:сквозная запись (write through, store through) - информация записывается в два места: в блоккэш-памяти и в блок более низкого уровня памяти.запись с обратным копированием (write back, copy back, store in) - информация записываетсятолько в блок кэш-памяти.
Модифицированный блок кэш-памяти записывается в основнуюпамять только когда он замещается. Для сокращения частоты копирования блоков призамещении обычно с каждым блоком кэш-памяти связывается так называемый битмодификации (dirty bit). Этот бит состояния показывает был ли модифицирован блок,находящийся в кэш-памяти. Если он не модифицировался, то обратное копированиеотменяется, поскольку более низкий уровень содержит ту же самую информацию, что икэш-память.Оба подхода к организации записи имеют свои преимущества и недостатки. При записи собратным копированием операции записи выполняются со скоростью кэш-памяти, инесколько записей в один и тот же блок требуют только одной записи в память болеенизкого уровня.
Поскольку в этом случае обращения к основной памяти происходят реже,вообще говоря требуется меньшая полоса пропускания памяти, что очень привлекательнодля мультипроцессорных систем. При сквозной записи промахи по чтению не влияют назаписи в более высокий уровень, и, кроме того, сквозная запись проще для реализации, чемзапись с обратным копированием. Сквозная запись имеет также преимущество в том, чтоосновная память имеет наиболее свежую копию данных. Это важно в мультипроцессорныхсистемах, а также для организации ввода/вывода.Когда процессор ожидает завершения записи при выполнении сквозной записи, то говорят,что он приостанавливается для записи (write stall).
Общий прием минимизации остановов позаписи связан с использованием буфера записи (write buffer), который позволяет процессорупродолжить выполнение команд во время обновления содержимого памяти. Следуетотметить, что остановы по записи могут возникать и при наличии буфера записи.При промахе во время записи имеются две дополнительные возможности:сквозная запись (write-through) - информация записывается в два места: в строку кэшпамяти и одновременно в основную память (при этом содержимое кэша и памятикогерентны – совпадают).
Сквозная запись проще для реализации, чем запись с обратнымкопированием. Также преимущество в том, что основная память имеет наиболее свежуюкопию данных. Это важно в мультипроцессорных системах, а также для организацииввода/вывода.53запись с обратным копированием, отложенная запись (write-back) - информациязаписывается только в строку кэш-памяти. Модифицированная строка кэш-памятизаписывается в основную память только, когда она замещается. Для сокращения частотыкопирования строк при замещении обычно с каждой строкой кэш-памяти связывается такназываемый бит модификации (Modify).
Этот бит состояния показывает, была лимодифицирована строка, находящаяся в кэш-памяти. Если он не модифицировался, тообратное копирование отменяется, поскольку более низкий уровень содержит ту жесамую информацию, что и кэш-память. При записи с обратным копированием операциизаписи выполняются со скоростью кэш-памяти, и несколько записей в один и тот же блоктребуют только одной записи в память более низкого уровня; в этом случае обращения косновной памяти происходят реже.Обычно в кэш-памяти, реализующей запись с обратным копированием, используетсяразмещение записи в кэш-памяти (в надежде, что последующая запись в этот блок будетперехвачена), а в кэш-памяти со сквозной записью размещение записи в кэш-памяти частоне используется (поскольку последующая запись в этот блок все равно пойдет в память).Увеличение производительности кэш-памятиФормула для среднего времени доступа к памяти в системах с кэш-памятью выглядитследующим образом:Среднее время доступа = Время обращения при попадании + Доля промахов x Потери припромахеЭта формула наглядно показывает пути оптимизации работы кэш-памяти: сокращение долипромахов, сокращение потерь при промахе, а также сокращение времени обращения к кэшпамяти при попадании.
Ниже на рисунке 3.23 кратко представлены различные методы,которые используются в настоящее время для увеличения производительности кэш-памяти.Использование тех или иных методов определяется прежде всего целью разработки, приэтом конструкторы современных компьютеров заботятся о том, чтобы система оказаласьсбалансированной по всем параметрам.Расслоение памяти.Наличие в системе множества микросхем памяти позволяет использовать потенциальныйпараллелизм, заложенный в такой организации.
Для этого микросхемы памяти частообъединяются в банки или модули, содержащие фиксированное число слов, причем толькок одному из этих слов банка возможно обращение в каждый момент времени. Как ужеотмечалось, в реальных системах имеющаяся скорость доступа к таким банкам памятиредко оказывается достаточной . Следовательно, чтобы получить большую скоростьдоступа, нужно осуществлять одновременный доступ ко многим банкам памяти. Одна изобщих методик, используемых для этого, называется расслоением памяти. При расслоениибанки памяти обычно упорядочиваются так, чтобы N последовательных адресов памяти i,i+1, i+2, ..., i+ N-1 приходились на N различных банков. В i-том банке памяти находятсятолько слова, адреса которых имеют вид kN + i (где 0 ( k ( M-1, а M число слов в одномбанке).
Можно достичь в N раз большей скорости доступа к памяти в целом, чем уотдельного ее банка, если обеспечить при каждом доступе обращение к данным в каждом избанков. Имеются разные способы реализации таких расслоенных структур. Большинство изних напоминают конвейеры, обеспечивающие рассылку адресов в различные банки имультиплексирующие поступающие из банков данные. Таким образом, степень иликоэффициент расслоения определяют распределение адресов по банкам памяти. Такие54системы оптимизируют обращения по последовательным адресам памяти, что являетсяхарактерным при подкачке информации в кэш-память при чтении, а также при записи, вслучае использования кэш-памятью механизмов обратного копирования.
Однако, еслитребуется доступ к непоследовательно расположенным словам памяти, производительностьрасслоенной памяти может значительно снижаться.Обобщением идеи расслоения памяти является возможность реализации несколькихнезависимых обращений, когда несколько контроллеров памяти позволяют банкам памяти(или группам расслоенных банков памяти) работать независимо.Если система памяти разработана для поддержки множества независимых запросов (как этоимеет место при работе с кэш-памятью, при реализации многопроцессорной и векторнойобработки), эффективность системы будет в значительной степени зависеть от частотыпоступления независимых запросов к разным банкам.
Обращения по последовательнымадресам, или в более общем случае обращения по адресам, отличающимся на нечетноечисло, хорошо обрабатываются традиционными схемами расслоенной памяти. Проблемывозникают, если разница в адресах последовательных обращений четная. Одно из решений,используемое в больших компьютерах, заключается в том, чтобы статистически уменьшитьвероятность подобных обращений путем значительного увеличения количества банковпамяти. Например, в суперкомпьютере NEC SX/3 используются 128 банков памяти.Подобные проблемы могут быть решены как программными, так и аппаратнымисредствами.ДополнениеПараллелизм работы блоков оперативной памяти ("расслоение памяти", MemoryInterleaving).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
