Кэш-память

Кэш-память

29

Государственный университет информационно - коммуникационных технологий

Курсовая работа

на тему:

Кэш-память

практическое задание: Дефрагментация диска

по предмету:

Операционные системы

выполнил:

Волоха Алексей Владимирович

группа ИБД-32б

Киев-2006

План

Теоретическая часть

Кэш-память

Введение 3

Причины внедрения кэш-памяти 4

Раздел 1 4

Что такое кэш-память? 4

Уровень за уровнем 5

Внутренний кэш 6

Смешанная и разделенная кэш-память 9

Статическая и динамическая память 10

TLB как разновидность кэш-памяти 11

Раздел 2 11

Организация кэш-памяти 11

Стратегия размещения 15

Отображение секторов ОП в кэш-памяти 15

Иерархическая модель кэш-памяти 16

Ассоциативность кэш-памяти 16

Размер строки и тега кэш-памяти 17

Типы подключения кэш-памяти 18

Сегментирование кэш-памяти и быстродействие жестких дисков 19

Увеличение производительности кэш-памяти 21

Зачем увеличивать кэш? 21

Выводы 23

Практическая часть

Дефрагментация диска 24

Литература 27

Введение

В качестве элементной базы основной памяти в большинстве ЭВМ используются микросхемы динамических ОЗУ, на порядок уступающие по быстродействию центральному процессору. В результате, процессор вынужден простаивать несколько периодов тактовой частоты, пока информация из ИМС памяти установится на шине данных ЭВМ. Если же ОП выполнить на быстрых микросхемах статической памяти, стоимость ЭВМ возрастет весьма существенно.

Экономически приемлемое решение этой проблемы возможно при использовании двухуровневой памяти, когда между основной памятью и процессором размещается небольшая, но быстродействующая буферная память или кэш-память. Вместе с основной памятью она входит в иерархическую структуру и ее действие эквивалентно быстрому доступу к основной памяти. Использование кэш-памяти позволяет избежать полного заполнения всей машины быстрой RAM памятью. Обычно программа использует память какой либо ограниченной области, храня нужную информацию в кэш-памяти, работа с которой позволяет процессору обходиться без всяких циклов ожидания. В больших универсальных ЭВМ, основная память которых имеет емкость порядка 1-32 Гбайт, обычно используется кэш-память емкость 1-12 Мбайт, т.е. емкость кэш-память составляет порядка 1/100-1/500 емкости основной памяти, а быстродействие в 5-10 раз выше быстродействия основной памяти. Выбор объема кэш-памяти - всегда компромисс между стоимостными показателями ( в сравнении с ОП ) и ее емкостью, которая должна быть достаточно большой, чтобы среднее время доступа в системе, состоящей из основной и кэш-памяти, определялось временем доступа к последней. Реальная эффективность использования кэш-памяти зависит от характера решаемых задач и невозможно определить заранее, какой объем ее будет действительно оптимальным.

Не всякая кэш-память равнозначна. Большое значение имеет тот факт, как много информации может содержать кэш-память. Чем больше кэш-память, тем больше информации может быть в ней размещено, а следовательно, тем больше вероятность, что нужный байт будет содержаться в этой быстрой памяти. Очевидно, что самый лучший вариант - это когда объём кэш-памяти соответствует объёму всей оперативной памяти. В этом случае вся остальная память становится не нужной. Крайне противоположная ситуация - 1 байт кэш-памяти - тоже не имеет практического значения, так как вероятность того, что нужная информация окажется в этом байте, стремится к нулю.

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

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

Причины внедрения кэш-памяти

Явная необходимость в кэш-памяти при проектировании массовых ЦП проявилась в начале 1990-х гг., когда тактовые частоты ЦП значительно превысили частоты системных шин, и, в частности, шины памяти. В настоящее время частоты серверных ЦП достигают почти 4 ГГц, а оперативной памяти, массово применяемой в серверах, - только 400 МГц (200 МГц с удвоением благодаря передаче по обоим фронтам сигнала). В этой ситуации при прямом обращении к памяти функциональные устройства ЦП значительную часть времени простаивают, ожидая доставки данных. В какой-то мере проблемы быстродействия оперативной памяти могут быть решены увеличением разрядности шины памяти, но даже в серверах младшего уровня нередко встречается 8-16 гнезд для модулей памяти, поэтому такое решение усложняет дизайн системной платы. Проложить же 256- или даже 512-бит шину к расположенной внутри кристалла ЦП кэш-памяти сравнительно несложно. Таким образом, эффективной альтернативы кэш-памяти в современных высокопроизводительных системах не существует.

Раздел 1

Что такое кэш-память?

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

Кэш-память напрямую влияет на скорость вычислений и помогает процессору работать с более равномерной загрузкой. Представьте себе массив информации, используемой в вашем офисе. Небольшие объемы информации, необходимой в первую очередь, скажем список телефонов подразделений, висят на стене над вашим столом. Точно так же вы храните под рукой информацию по текущим проектам. Реже используемые справочники, к примеру, городская телефонная книга, лежат на полке, рядом с рабочим столом. Литература, к которой вы обращаетесь совсем редко, занимает полки книжного шкафа.

Компьютеры хранят данные в аналогичной иерархии. Когда приложение начинает работать, данные и команды переносятся с медленного жесткого диска в оперативную память произвольного доступа (Dynamic Random Access Memory -- DRAM), откуда процессор может быстро их получить. Оперативная память выполняет роль кэша для жесткого диска.

Для достаточно быстрых компьютеров (например, на основе intel-80386 с тактовой частотой более 25 мгц или intel-80486) необходимо обеспечить быстрый доступ к оперативной памяти, иначе микропроцессор будет простаивать и быстродействие компьютера уменьшится. Для этого такие компьютеры могут оснащаться кэш-памятью, т.е. "сверхоперативной" памятью относительно небольшого объема (обычно от 64 до 256 кбайт), в которой хранятся наиболее часто используемые участки оперативной памяти. Кэш-память располагается "между" микропроцессором и оперативной памятью, и при обращении микропроцессора к памяти сначала производится поиск нужных данных в кэш-памяти. Поскольку время доступа к кэш-памяти в несколько раз меньше, чем к обычной памяти, а в большинстве случаев необходимые микропроцессору данные содержаться в кэш-памяти, среднее время доступа к памяти уменьшается. Для компьютеров на основе intel-80386dx или 80486sx размер кэш-памяти в 64 кбайт является удовлетворительным, 128 кбайт - вполне достаточным. Компьютеры на основе intel-80486dx и dx2 обычно оснащаются кэш-памятью емкостью 256 кбайт.

Уровень за уровнем

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

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

Процессор Pentium III компании Intel имеет кэш-память первого уровня емкостью 32 Кбайт на микросхеме процессора и либо кэш-память второго уровня емкостью 256 Кбайт на микросхеме, либо кэш-память второго уровня емкостью 512 Кбайт, не интегрированную с процессором.

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

Когда процессор обнаруживает данные в одном из кэшей, это называют «попаданием»; неудачу называют «промахом». Каждый промах вызывает задержку, поскольку процессор будет пытаться обнаружить данные на другом, более медленном уровне. В хорошо спроектированных системах с программными алгоритмами, которые выполняют предварительную выборку данных до того, как они потребуются, процент «попаданий» может достигать 90.

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

Кэш-память для серверов даже более важна, чем для настольных ПК, поскольку серверы поддерживают между процессором и памятью весьма высокий уровень трафика, генерируемого клиентскими транзакциями. В 1991 году Intel превратила ПК на базе процессора 80486 с тактовой частотой 50 МГц в сервер, добавив на процессорную плату кэш с тактовой частотой 50 МГц. Хотя шина, связывающая процессор и память, работала с частотой всего 25 МГц, такая кэш-память позволила многие программы во время работы полностью размещать в процессоре 486 с тактовой частотой 50 МГц.

Иерархическая организация памяти помогает компенсировать разрыв между скоростями процессоров, ежегодно увеличивающимися примерно на 50% в год, и скоростями доступа к DRAM, которые растут лишь на 5%. Как считает Джон Шен, профессор Университета Карнеги-Меллона, по мере усиления этого диссонанса производители аппаратного обеспечения добавят третий, а возможно и четвертый уровень кэш-памяти.

Действительно, уже в этом году Intel намерена представить кэш-память третьего уровня в своих 64-разрядных процессорах Itanium. Кэш емкостью 2 или 4 Мбайт будет связан с процессором специальной шиной, тактовая частота которой совпадает с частотой процессора.

IBM также разработала собственную кэш-память третьего уровня для 32- и 64-разрядных ПК-серверов Netfinity. По словам Тома Бредикича, директора по вопросам архитектуры и технологий Netfinity, сначала кэш будет размещаться на микросхеме контроллера памяти, выпуск которой начнется к концу следующего года.

Кэш-память третьего уровня корпорации IBM станет общесистемным кэшем, куда смогут обращаться от 4 до 16 процессоров сервера. С кэш-памятью третьего уровня Intel сможет работать только тот процессор, к которому она подключена, но представители IBM подчеркнули, что их кэш третьего уровня способен увеличить пропускную способность всей системы. Бредикич отметил, что новая кэш-память производства IBM также поможет реализовать компьютерные системы высокой готовности, необходимые для электронной коммерции, поскольку с ее помощью можно будет менять модули основной памяти и выполнять модернизацию, не прерывая работу системы.

Внутренний кэш

Внутренне кэширование обращений к памяти применяется в процессорах, начиная с 486-го. С кэшированием связаны новые функции процессоров, биты регистров и внешние сигналы.

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

Строки в кэш-памяти выделяются только при чтении, политика записи первых процессоров 486 - только Write Through (сквозная запись) - полностью программно-прозрачная. Более поздние модификации 486-го и все старшие процессоры позволяют переключаться на политику Write Back (обратная запись).

Работу кэша рассмотрим на примере четырехканального наборно-ассоциативного кэша процессора 486, его физическая структура приведена на рис.1. Кэш является несекторированным - каждый бит достоверности (Valid bit) относится к целой строке, так что стока не может являться “частично достоверной”.

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

Любой внутренний запрос процессора на обращение к памяти направляется на внутренний кэш. Теги четырех строк набора, который обслуживает данный адрес, сравниваются со старшими битами запрошенного физического адреса. Если адресуемая область представлена в строке кэш-памяти (случая попадания -cache hit), запрос на чтение обслуживается только кэш-памятью, не выходя на внешнюю шину. Запрос на запись модифицирует данную строку, и в зависимости от политики записи либо сразу выходит на внешнюю шину (при сквозной записи), либо несколько позже (при использовании алгоритма обратной записи).

Рис 1. Структура первичного кэша процессора 486

В случае промаха (Cache Miss) запрос на запись направляется только на внешнюю шину, а запрос на чтение обслуживается сложнее. Если этот зарос относится к кэшируемой области памяти, выполняется цикл заполнения целой строки кэша - все 16 байт (32 для Pentium) читаются из оперативной памяти и помещаются в одну из строк кэша, обслуживающего данный адрес. Если затребованные данные не укладываются в одной строке, заполняется и соседняя. Заполнение строки процессор старается выполнить самым быстрым способом - пакетным циклом с 32-битными передачами (64-битными для Pentium и старше).

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

Таким образом, выделение и замещение строк выполнятся только кэш-промахов чтения, при промахах записи заполнение строк не производится. Если затребованная область памяти присутствует в строке внутреннего кэша, то он обслужит этот запрос. Управлять кэшированием можно только на этапе заполнения строк; кроме того, существует возможность их аннулирования - объявления недостоверными и очистка всей кэш-памяти.

Очистка внутренней кэш-памяти при сквозной записи (обнуление бит достоверности всех строк) осуществляется внешним сигналом FLUSH# за один такт системной шины (и, конечно же, по сигналу RESET). Кроме того, имеются инструкции аннулирования INVD и WBINVD. Инструкция INVD аннулирует строки внутреннего кэша без выгрузки модифицированных строк, поэтому ее неосторожное использование при включенной политике обратной записи может привести к нарушению целостности данных в иерархической памяти. Инструкция WBINVD предварительно выгружает модифицированные строки в основную память (при сквозной записи ее действие совпадает с INVD). При обратной записи очистка кэша подразумевает и выгрузку всех модифицированных строк в основную память. Для этого, естественно, может потребоваться и значительное число тактов системной шины, необходимых для проведения всех операций записи.

Аннулирование строк выполняется внешними схемами - оно необходимо в системах, у которых в оперативную память запись может производить не только один процессор, а и другие контроллеры шины - процессор или периферийные контроллеры. В этом случае требуются специальные средства для поддержания согласованности данных во всех ступенях памяти - в первичной и вторичной кэш-памяти и динамического ОЗУ. Если внешний (по отношению к рассматриваемому процессору) контроллер выполняет запись в память, процессору должен быть подан сигнал AHOLD. По этому сигналу процессор немедленно отдает управление шиной адреса A[31:4], на которой внешним контроллером устанавливается адрес памяти, сопровождаемый стробом EADS#. Если адресованная память присутствует в первичном кэше, процессор аннулирует строку - сбрасывает бит достоверности этой строки (она освобождается). Аннулирование строки процессор выполняет в любом состоянии.

Управление заполнением кэша возможно и на аппаратном и на программном уровнях. Процессор позволяет кэшировать любую область физической памяти. Внешние схемы могут запрещать процессору кэшировать определенные области памяти установкой высокого уровня сигнала KEN# во время циклов доступа к этим областям памяти. Этот сигнал управляет только возможностью заполнения строк кэша из адресованной области памяти. Программно можно управлять кэшируемостью каждой страницы памяти - запрещать единичным значением бита PCD (Page Cache Disable) в таблице или каталоге страниц. Для процессоров с WB-кэшем бит PWT (Page Write Through) позволяет постранично управлять и алгоритмом записи. Общее программное управление кэшированием осуществляется посредством бит управляющего регистра CR0:CD (Cache Disable) и NW (No Write Through). Возможны следующие сочетания бит регистра:

CD=1, NW=1 - если после установки такого значения выполнить очистку кэша, кэш будет полностью отключен. Если же перед установкой этого сочетания бит кэша был заполнен, а очистка не производилась, кэш превращается в “замороженную” область статической памяти;

CD=1, CW=0 - заполнение кэша запрещено, но сквозная запись разрешена. Эффект аналогичен временному переводу сигнала KEN# в высокое (пассивное) состояние. Этот режим может использоваться для временного отключения кэша, после которого возможно его включение без очистки;

CD=0, NW=1 - запрещенная комбинация (вызывает отказ общей защиты);

CD=0, NW=0 - нормальный режим работы со сквозной записью.

Для полного запрета кэша необходимо установить CD=1 и NW=1, после чего выполнить очистку (Flush). Без очистки кэш будет обслуживать запросы в случае попаданий.

Процессоры 486 и старше имеют выходные сигналы PCD и PWT, управляющие работой вторичного (внешнего) кэша (они же управляют и внутренним кэшем). В циклах обращения к памяти, когда страничные преобразования не используются (например, при обращении к таблице каталогов страниц), источником сигналов являются биты PCD и PWT регистра CR3, при обращении к каталогу страниц - биты PCD и PWT из дескриптора соответствующего вхождения каталога, при обращении к самим данным - биты PCD и PWT из дескриптора страницы. Кроме того, оба этих сигнала могут принудительно устанавливаться общими битами управления кэшированием CD и NW регистра CRO.

Режим обратной записи может разрешаться только аппаратно сигналом WB/WT#, вырабатываемым внешними схемами.

В пространстве памяти РС имеются области, для которых кэширование принципиально недопустимо (например, разделяемая память адаптеров) или непригодна политика обратной записи. Кроме того, кэширование иногда полезно отключать при выполнении однократно исполняемых участков программы (например, инициализации) с тем, чтобы из кэша не вытиснялись более часто используемые фрагменты. Напомним, что запретить можно только заполнение строк, а обращение к памяти, уже представленной действительными строками кэша, все равно будет обслуживаться из кэша. Для полного запрета работы кэша строки должны быть аннулированы.

Программно при включенном режиме страничного преобразования кэшированием управляют биты атрибутов страниц (на уровне таблицы страниц и их каталога), биты PCD и PWT регистра CR3, и, наконец, глобально кэшированием управляют биты CD и NW регистра CR0.

Аппаратно (сигналом KEN#) внешние схемы могут управлять кэшированием (разрешать заполнение строк) для каждого конкретного адреса обращения к физической памяти.

Благодаря использованию нанотехнологий, для снижения потребляемой мощности, увеличения быстродействия ЭВМ( что достигается сокращением времени обмена данными между процессором и кэш-памятью) существует возможность, а более того имеются реальные примеры того, что кэш-память реализуют в одном кристале с процессором. Такая внутренняя кэш-память реализуется по технологии статического ОЗУ и является наиболее быстродействующей. Объем ее обычно составляет 64-128 Кбайт, причем дальнейшее увеличение ее объема приводит обычно к снижению быстродействия из-за усложнения схем управления и дешифрации адреса.

Альтернативой, широко применяемой в настоящее время, является вторая (внешняя) кэш-память большего объема, расположенная между внутренней кэш-памятью и ОП. В этой двухуровневой системе кэш-памяти, внутренней памяти отводится роль первого уровня L1, а внешней - второго L2. емкость L2 обычно на порядок и более выше, чем L1, а быстродействие и стоимость ниже. Память второго уровня также строится обычно как статическое ОЗУ. Емкость ее может составлять от 256 Кбайт до 1 Мбайта и технически реализуется как в виде отдельной микросхемы, однако может размещаться и на одном кристалле с процессором.

Самые современные процессоры от крупнейших производителей оснащаются сегодня кэш-памятью емкостью у Intel Pentium 4 на ядре Northwood - 512 Кбайт кэш-памяти L2, а процессоры Prescott будут выпускаться по 0,09-микронной технологии и получат кэш-память второго уровня удвоенного объема, который составит 1 Мбайт. Intel продолжает широко рекламировать свой "экстремальный" игровой процессор Pentium 4 Extreme Edition на основе модифицированного серверного ядра Gallatin с тактовой частотой 3,40 ГГц и кэш-памятью третьего уровня объемом 2 Мбайта. Она дополняет стандартный нортвудовский кэш L2 512 Кбайт и тоже работает на частоте ядра процессора (правда, с большей раза в два латентностью). Таким образом, в сумме новый Pentium 4 Extreme Edition имеет кэш-память объемом 2,5 Мбайт.

Дополнительная кэш-память третьего уровня ведет начало от серверных процессоров Xeon MP на 0,13-микронном ядре Gallatin и не имеет ничего общего с грядущим 90-нанометровым Prescott, однако этот кристалл (ядро) все же немного переработали с целью поддержки системной шины 800 МГц, уменьшения энергопотребления и др. и упаковали в стандартный корпус от текущих Pentium 4. В свою очередь AMD Athlon 64 и AMD Opteron работающие на более высокой частоте 2200 МГц, производятся по 0,13-микронной технологии (SOI) и содержат 105,9 млн. транзисторов и отличаются от предшествующих Athlon XP новым ядром с 64-битными возможностями вычислений (наряду с улучшенными 32-битными на базе прежнего ядра Athlon XP), кэш-памятью второго уровня объемом 1 Мбайт (причем кэш у Атлонов инклюзивный, то есть полный объем с учетом 128 Кбайт L1 составляет 1152 Кбайт).

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

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

Статическая и динамическая память

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

Одна ячейка статической памяти состоит из шести транзисторов и двух резисторов (для техпроцессов с проектными нормами до 0,5 мкм могли быть использованы только четыре транзистора на одну ячейку, с дополнительным слоем поликремния и с более жесткими ограничениями по максимальной тактовой частоте), в то время как аналогичная структура динамической памяти состоит из одного транзистора и одного конденсатора.

Быстродействие статической памяти намного выше (емкость, используемая в динамической памяти, имеет определенную скорость зарядки до требуемого уровня, определяющую "частотный потолок"), но из-за большего количества составляющих элементов она существенно дороже в производстве и отличается более высоким энергопотреблением. Битовое значение ячейки статической памяти характеризуется состоянием затворов транзисторов, а динамической - уровнем заряда конденсатора. Так как конденсаторы имеют свойство с течением времени разряжаться, то для поддержания их состояния требуется регулярная перезарядка (для современных микросхем динамической памяти - приблизительно 15 раз в секунду). Кроме того, при операции чтения из ячейки динамической памяти конденсатор разряжается, т. е. ячейка утрачивает свой первоначальный заряд, а следовательно должна быть перезаряжена.

Очевидно, что статическая память используется там, где требуется максимальное быстродействие (регистры ЦП, кэш-память, локальная память сигнального процессора), а динамическая - там, где приоритетом является объем, а не скорость чтения-записи (оперативная память, буферы периферийных устройств).

TLB как разновидность кэш-памяти

Почти все современные ЦП обладают TLB (Translation Look-aside Buffers, вспомогательные буфера преобразования). Своим существованием они обязаны тому факту, что ЦП в работе используют преимущественно виртуальные адреса оперативной памяти, в то время как контроллеры оперативной и кэш-памяти работают преимущественно с реальными адресами. Для того чтобы не вычислять при каждом обращении к памяти реальный адрес из виртуального, в ЦП присутствуют таблицы соответствия виртуальных адресов страниц памяти реальным. Как правило, их объем невелик (от единиц до сотен записей), но этого вполне достаточно, поскольку часто запрашиваемые данные или команды обычно хорошо локализуются в пределах страницы памяти размером 4 или 8 Кбайт.

Что же происходит, если запрашиваемого реального адреса какой-либо страницы не находится в TLB? A-box ЦП отрабатывает специальный вызов (exception trap), на который ОС должна адекватно отреагировать, т. е. произвести поиск нужной страницы в своих таблицах подсистемы виртуальной памяти. Если в процессе поиска окажется, что указанная страница находится в файле или разделе подкачки, то она должна незамедлительно быть оттуда считана в оперативную память. В итоге А-box ЦП получит реальный адрес нужной страницы памяти и процесс пойдет своим путем.

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

Раздел 2

Организация кэш-памяти

Концепция кэш-памяти возникла раньше чем архитектура IBM/360, и сегодня кэш-память имеется практически в любом классе компьютеров, а в некоторых компьютерах - во множественном числе.

Рис. 2. Типовые значения ключевых параметров для кэш-памяти рабочих станций и серверов

Все термины, которые были определены раньше могут быть использованы и для кэш-памяти, хотя слово "строка" (line) часто употребляется вместо слова "блок" (block).

На рисунке 2 представлен типичный набор параметров, который используется для описания кэш-памяти.

Рассмотрим организацию кэш-памяти более детально, отвечая на четыре вопроса об иерархии памяти.

1. Где может размещаться блок в кэш-памяти?

Принципы размещения блоков в кэш-памяти определяют три основных типа их организации:

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

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

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

Если некоторый блок основной памяти может располагаться на любом месте кэш-памяти, то кэш называется полностью ассоциативным (fully associative).

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

(адрес множества кэш-памяти) =

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

Далее, блок может размещаться на любом месте данного множества.

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

2. Как найти блок, находящийся в кэш-памяти?

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

Кроме того, необходим способ определения того, что блок кэш-памяти содержит достоверную или пригодную для использования информацию. Наиболее общим способом решения этой проблемы является добавление к тегу так называемого бита достоверности (valid bit).

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

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

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

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

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

Достоинство случайного способа заключается в том, что его проще реализовать в аппаратуре. Когда количество блоков для поддержания трассы увеличивается, алгоритм LRU становится все более дорогим и часто только приближенным. На рисунке 3 показаны различия в долях промахов при использовании алгоритма замещения LRU и случайного алгоритма.

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

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

4. Что происходит во время записи?

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

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

Однако при выполнении операции записи ситуация коренным образом меняется. Именно процессор определяет размер записи (обычно от 1 до 8 байтов) и только эта часть блока может быть изменена. В общем случае это подразумевает выполнение над блоком последовательности операций чтение-модификация-запись: чтение оригинала блока, модификацию его части и запись нового значения блока. Более того, модификация блока не может начинаться до тех пор, пока проверяется тег, чтобы убедиться в том, что обращение является попаданием. Поскольку проверка тегов не может выполняться параллельно с другой работой, то операции записи отнимают больше времени, чем операции чтения.

Страницы: 1, 2