Ответы 190 страниц (1184228), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Ассоциативная адресация выполняется набор за набором, поэтому работают оба вида ассоциаций. Адресация набора, однако, выполняется явным образом посредством адреса набора А5-А11. Фрагмент информации для ассоциативной адресации задается адресом дескриптора внутри набора. Этот адрес дескриптора сравнивается с адресами А12-31 из CPU. Если они совпадают, то кэш-контроллер присоединяет весь соответствующий элемент кэш-памяти, т.е. всю кэш-строку, принадлежащую соответствующей магистрали набора, который имеет нужный адрес дескриптора. Подробнее об этом будет рассказано дальше.

Кэш-память с прямым отображением.

Если каждая строка основной памяти может быть отображена только в одну фиксированную строку кэш-памяти, то такая кэш-память называется кэшем с прямым отображением (direct mapped). В каждый блок помещаются данные с определенными (непересекающимися) диапазонами адресов (группами диапазонов). Это наиболее простая организация кэш-памяти, при которой для отображения адресов блоков основной памяти на адреса кэш-памяти просто используются младшие разряды адреса блока (выделяются несколько разрядов из адреса оперативной памяти и интерпретируются как номер строки кэш-памяти).

(адрес блока кэш-памяти) = (адрес блока основной памяти) mod (число блоков в кэш-памяти)

При этом все блоки основной памяти, имеющие одинаковые младшие разряды в своем адресе, попадают в один блок кэш-памяти. Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти.

При поиске данных в кэше используется быстрый прямой доступ к записи по номеру строки, полученному путем обработки адреса оперативной памяти из запроса. Однако поскольку в найденной строке могут находиться данные из любой ячейки оперативной памяти, младшие разряды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку. Для этих целей каждая строка кэш-памяти дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. При совпадении тега с соответствующей частью адреса из запроса констатируется кэш-попадание.

Достоинство такой организации заключается в том, что наиболее просты аппаратные решения; поиск по кэшу производится максимально быстро, но при этом процент попаданий (hit rate) относительно низок, из-за того, что порой невозможно одновременно кэшировать две секции часто используемых данных, т.к. они норовят занять одно и то же место в кэше.

По версии лектора

Кэш память с прямым отображением.

Архитектура кэш-памяти с прямым отображением (direct-map­ped) характеризуется на­личием явной зависимости между адресами буферной и оперативной памяти, причем каждому адресу кэша соответствует адреса оперативной памяти, кратные размеру кэш памяти. Память кэша состоит их памяти данных и памяти тэгов. Пусть, длина строки кэша равна 32 байтам, размер кэша – 4 Кбайт, тогда кэш память для данных состоит из 128 строк. ОЗУ разделено на блоки, размером в 4Кбайт, каждый содержит 128 строк. В нулевой строке кэша может быть размещены 0 или 128, или .... строки ОЗУ, в первой – 1 или 129 или.. строки т и.д. Для каждой заполненной строки данных кэша известен тэг – номер блока ОЗУ, которому принадлежит строка. Тэги хранятся в специальной памяти - памяти тэгов, размер которой – 128 строк. Длина строки памяти тэгов зависит от размера ОЗУ. Если объем ОЗУ – 4 Гбайт, тогда полный адрес - 32 бита можно представить в виде полей: 20 рр – тэг (T), 7 рр – номер строки таблиц кэша (S), 5 рр – номер байта в строке (N). Поиск запрошенного байта (T-S-N) в кэше с прямым распределением производится так:

1.Из памяти данных и памяти тэгов кэша одновременно считываются S-ные строки.

Если содержимое считанной строки памяти тэгов равно Т – кэш попадание, это значит, что считанная S строка памяти данных кэша содержит запрашиваемый байт и его номер в строке есть N.

3. Если содержимое считанной строки памяти тэгов не равно Т – кэш промах, и тогда T-S строка ОЗУ переписывается в S строку памяти данных кэша, а Т записывается в S строку памяти тэгов. Затем, см по п. 1.

Частично ассоциативная кэш-память.

Если некоторая строка основной памяти может располагаться на ограниченном множестве мест в кэш-памяти, то кэш называется частично-ассоциативным (set associative). То есть произвольный адрес оперативной памяти отображается на некоторую группу адресов кэш-памяти. Если группа состоит из n строк, то такое размещение называется частично-ассоциативным с n каналами (n-way set associative). Группа определяется младшими разрядами адреса строки:

(адрес группы кэш-памяти) = (адрес строки основной памяти) mod (число групп в кэш-памяти). Далее блок может размещаться на любом месте данной группы.

Все группы пронумерованы. Поиск в кэше осуществляется вначале по номеру группы, полученному из адреса оперативной памяти из запроса, а затем в пределах группы путем ассоциативного просмотра всех записей в группе на предмет совпадения старших частей адресов оперативной памяти. (То есть указанный адрес ищем в любом блоке в пределах данной группы блоков; внешне – кэш с прямой адресацией, внутри – полностью ассоциативный кэш).

Адресация частично-ассоциативной кэш-памяти осуществляется путем деления адреса на три части: поле смещения используется для выбора байта внутри строки кэш-памяти, поле индекса определяет номер группы, а поле тега используется для сравнения. Если общий размер кэш-памяти зафиксировать, то увеличение степени ассоциативности приводит к увеличению количества строк в группе, при этом уменьшается размер индекса и увеличивается размер тега.

Магистраль

Понятие магистрали указывает на ассоциативный характер кэш-системы. Для заданного адреса набора адреса дескрипторов для всех магистралей одновременно сравниваются с дескрипторной частью адреса, выдаваемого процессором, чтобы определить, находятся данные в кэш-памяти или нет. В примере показана ассоциативная кэш-память, имеющая 4 магистрали. Это означает, что массив данных, соответствующий кэш-строке, может храниться в кэш-памяти в четырех различных местах. Каждая магистраль в примере содержит 256 наборов, каждый из которых имеет кэш-строку длиной 16 байт. Это, в соответствии с формулой: емкость=число магистралей х число наборов х длина кэш-строки, обеспечивает указанные 16 кбайт кэш-памяти. Элементу набора для всех четырех магистралей назначается 3-битный элемент LRU; кэш-контроллер использует эти биты для того, чтобы определить, какая из четырех кэш-строк должна обновляться в случае кэш-промаха. Для этого существует ряд алгоритмов.

Заметим, что в данном случае адрес памяти в верхней части рисунка 8.2 не содержит элемента для магистрали. При наличии магистрали в игру вступает ассоциативность. Кэш с непосредственно отображаемой памятью имеет только одну магистраль и поэтому не является ассоциативным; массив данных, хранящийся в кэш-памяти, может занимать в ней только одно положение, определяемое 12 младшими битами. В рассматриваемом примере данные, расположенные по двоичному адресу хххх хххх хххх хххх хххх ssss sssx xxxb, всегда будут храниться в наборе sssssss. Элемент, который ранее там размещался, должен быть заменен новым. В 4-магистральной ассоциативной кэш-памяти данные с двоичным адресом хххх хххх хххх хххх хххх ssss sssx xxxb, также будут всегда храниться в наборе sssssss. В этом случае, однако, для каждого набора доступны четыре магистрали, поэтому предыдущий элемент не всегда приходится перезаписывать. Если кэш-строка в другой магистрали свободна, то кэш-контроллер может поместить данные в свободную магистраль. Это увеличивает и число кэш-попаданий, поскольку для одного и того же адреса набора имеется четыре элемента. 8-магистральные ассоциативные модели кэш-памяти имеют соответственно большее число кэш-попаданий, но увеличивается и техническая сложность. В противоположность этому, часто реализуемые 2-магистральные ассоциативные модели кэш-памяти имеют существенно меньшее число попаданий, но и логики для определения кэш-попадания нужно значительно меньше. Это приводит к увеличению скорости работы. Такая организация используется особенно часто для высокоскоростных моделей кэш-памяти (например, для встроенной в чип кэш-памяти в Pentium).

Дисциплина обновления кэш-памяти.

При возникновении промаха происходит обновление содержимого КЭШа – вытеснение.

1. Кэш с прямым отображением. Если произошел промах, то данные считываются из оперативной памяти и копируются в кэш. Если строка кэш-памяти, в которую должен быть скопирован элемент данных из оперативной памяти, содержит другие данные, то последние вытесняются из кэша. Заметим, что процесс замещения данных в кэш-памяти на основе прямого отображения существенно отличается от процесса замещения данных в ассоциативной кэш-памяти. Во-первых, вытеснение данных происходит не только в случае отсутствия свободного места в кэше, во-вторых, никакого выбора данных на замещение не существует.

2. Полностью ассоциативный кэш. Вытеснение старых данных происходит только в том случае, когда вся кэш-память заполнена и нет свободного места. Выбор данных на выгрузку осуществляется среди всех записей кэша. Стратегии вытеснения:

   • случайная – с кэшем ассоциируется датчик случайных чисел. Достоинство – этот алгоритм проще реализовать.

   • LRU - Least-Recently Used - заменяется та строка, которая не использовалась дольше всех (выбирается блок, частота обращения к которому была наименьшей) - чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться. Достоинство – этот алгоритм учитывает интенсивность обращения к данным и тем самым повышает вероятность попаданий в будущем.

3. Частично-ассоциативный кэш. При промахе данные копируются по любому свободному адресу из однозначно заданной группы. Если свободных адресов в группе нет, то выполняется вытеснение данных – одна из стратегий. Таким образом, в данном способе комбинируется прямое отображение на группу и случайное отображение в пределах группы.

Дополнение

3. Какой блок кэш-памяти должен быть замещен при промахе?

При возникновении промаха, контроллер кэш-памяти должен выбрать подлежащий замещению блок. Польза от использования организации с прямым отображением заключается в том, что аппаратные решения здесь наиболее простые. Выбирать просто нечего: на попадание проверяется только один блок и только этот блок может быть замещен. При полностью ассоциативной или множественно-ассоциативной организации кэш-памяти имеются несколько блоков, из которых надо выбрать кандидата в случае промаха. Как правило для замещения блоков применяются две основных стратегии: случайная и LRU.

В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираются случайно. В некоторых системах, чтобы получить воспроизводимое поведение, которое особенно полезно во время отладки аппаратуры, используют псевдослучайный алгоритм замещения.

Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скоро может потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, который не использовался дольше всех (LRU - Least-Recently Used).

Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. На рисунке 3.22 показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма. Ассоциативность: 2-канальная 4-канальная 8-канальная

Сравнение долей промахов для алгоритма LRU и случайного алгоритма замещения

при нескольких размерах кэша и разных ассоциативностях при размере блока 16 байт

Размер кэш-памяти LRU Random LRU Random LRU Random

16 KB 5.18% 5.69% 4.67% 5.29% 4.39% 4.96%

64 KB 1.88% 2.01% 1.54% 1.66% 1.39% 1.53%

256 KB 1.15% 1.17% 1.13% 1.13% 1.12% 1.12%

Стратегии записи в кэш-память.

При обращениях к кэш-памяти на реальных программах преобладают обращения по чтению. Все обращения за командами являются обращениями по чтению и большинство команд не пишут в память. Обычно операции записи составляют менее 10% общего трафика памяти. Желание сделать общий случай более быстрым означает оптимизацию кэш-памяти для выполнения операций чтения, однако при реализации высокопроизводительной обработки данных нельзя пренебрегать и скоростью операций записи.

Характеристики

Список файлов ответов (шпаргалок)