СКИПОДы 2007 полная версия (1127795), страница 15
Текст из файла (страница 15)
Фрагмент информации для ассоциативной адресации задается адресом47дескриптора внутри набора. Этот адрес дескриптора сравнивается с адресами А12-31 изCPU. Если они совпадают, то кэш-контроллер присоединяет весь соответствующий элементкэш-памяти, т.е. всю кэш-строку, принадлежащую соответствующей магистрали набора,который имеет нужный адрес дескриптора. Подробнее об этом будет рассказано дальше.Кэш-память с прямым отображением.Если каждая строка основной памяти может быть отображена только в однуфиксированную строку кэш-памяти, то такая кэш-память называется кэшем с прямымотображением (direct mapped). В каждый блок помещаются данные с определенными(непересекающимися) диапазонами адресов (группами диапазонов). Это наиболее простаяорганизация кэш-памяти, при которой для отображения адресов блоков основной памяти наадреса кэш-памяти просто используются младшие разряды адреса блока (выделяютсянесколько разрядов из адреса оперативной памяти и интерпретируются как номер строкикэш-памяти).(адрес блока кэш-памяти) = (адрес блока основной памяти) mod (число блоков в кэшпамяти)При этом все блоки основной памяти, имеющие одинаковые младшие разряды в своемадресе, попадают в один блок кэш-памяти.
Между номерами строк кэш-памяти и адресамиоперативной памяти устанавливается соответствие «один ко многим»: одному номерустроки соответствует несколько (обычно достаточно много) адресов оперативной памяти.При поиске данных в кэше используется быстрый прямой доступ к записи по номерустроки, полученному путем обработки адреса оперативной памяти из запроса. Однакопоскольку в найденной строке могут находиться данные из любой ячейки оперативнойпамяти, младшие разряды адреса которой совпадают с номером строки, необходимовыполнить дополнительную проверку.
Для этих целей каждая строка кэш-памяти48дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. Присовпадении тега с соответствующей частью адреса из запроса констатируется кэшпопадание.Достоинство такой организации заключается в том, что наиболее просты аппаратныерешения; поиск по кэшу производится максимально быстро, но при этом процентпопаданий (hit rate) относительно низок, из-за того, что порой невозможно одновременнокэшировать две секции часто используемых данных, т.к. они норовят занять одно и то жеместо в кэше.По версии лектораКэш память с прямым отображением.Архитектура кэш-памяти с прямым отображением (direct-mapped) характеризуется наличием явной зависимости между адресами буферной и оперативной памяти, причемкаждому адресу кэша соответствует адреса оперативной памяти, кратные размеру кэшпамяти.
Память кэша состоит их памяти данных и памяти тэгов. Пусть, длина строки кэшаравна 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 (число групп в кэшпамяти). Далее блок может размещаться на любом месте данной группы.49Все группы пронумерованы. Поиск в кэше осуществляется вначале по номеру группы,полученному из адреса оперативной памяти из запроса, а затем в пределах группы путемассоциативного просмотра всех записей в группе на предмет совпадения старших частейадресов оперативной памяти.
(То есть указанный адрес ищем в любом блоке в пределахданной группы блоков; внешне – кэш с прямой адресацией, внутри – полностьюассоциативный кэш).Адресация частично-ассоциативной кэш-памяти осуществляется путем деления адреса натри части: поле смещения используется для выбора байта внутри строки кэш-памяти, полеиндекса определяет номер группы, а поле тега используется для сравнения. Если общийразмер кэш-памяти зафиксировать, то увеличение степени ассоциативности приводит кувеличению количества строк в группе, при этом уменьшается размер индекса иувеличивается размер тега.МагистральПонятие магистрали указывает на ассоциативный характер кэш-системы. Для заданногоадреса набора адреса дескрипторов для всех магистралей одновременно сравниваются сдескрипторной частью адреса, выдаваемого процессором, чтобы определить, находятся50данные в кэш-памяти или нет.
В примере показана ассоциативная кэш-память, имеющая 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 - заменяется та строка, которая не использоваласьдольше всех (выбирается блок, частота обращения к которому была наименьшей) - чтобыуменьшить вероятность выбрасывания информации, которая скоро может потребоваться.Достоинство – этот алгоритм учитывает интенсивность обращения к данным и тем самымповышает вероятность попаданий в будущем.513)Частично-ассоциативный кэш. При промахе данные копируются по любомусвободному адресу из однозначно заданной группы.
Если свободных адресов в группе нет,то выполняется вытеснение данных – одна из стратегий. Таким образом, в данном способекомбинируется прямое отображение на группу и случайное отображение в пределахгруппы.Дополнение3. Какой блок кэш-памяти должен быть замещен при промахе?При возникновении промаха, контроллер кэш-памяти должен выбрать подлежащийзамещению блок. Польза от использования организации с прямым отображениемзаключается в том, что аппаратные решения здесь наиболее простые. Выбирать простонечего: на попадание проверяется только один блок и только этот блок может бытьзамещен. При полностью ассоциативной или множественно-ассоциативной организациикэш-памяти имеются несколько блоков, из которых надо выбрать кандидата в случаепромаха.
Как правило для замещения блоков применяются две основных стратегии:случайная и LRU.В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираютсяслучайно. В некоторых системах, чтобы получить воспроизводимое поведение, котороеособенно полезно во время отладки аппаратуры, используют псевдослучайный алгоритмзамещения.Во втором случае, чтобы уменьшить вероятность выбрасывания информации, которая скороможет потребоваться, все обращения к блокам фиксируются. Заменяется тот блок, которыйне использовался дольше всех (LRU - Least-Recently Used).Достоинство случайного способа заключается в том, что его проще реализовать ваппаратуре.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
