Иерархия памяти, кэширование

ВВЕДЕНИЕ

Главная задача компьютерной системы – выполнять программы. Программы вместе с данными, к которым они имеют доступ, в процессе выполнения должны (по крайней мере частично) находиться в оперативной памяти. Операционной системе приходится решать задачу распределения памяти между пользовательскими процессами и компонентами ОС. Эта деятельность называется управлением памятью. Таким образом, память (storage, memory) является важнейшим ресурсом, требующим тщательного управления. [1]

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

В идеале каждому программисту хотелось бы иметь предоставленную только ему неограниченную по объему и скорости работы память, которая к тому же не теряет своего содержимого при отключении питания. Раз уж мы так размечтались, то почему бы не сделать память еще и совсем дешевой? К сожалению, существующие технологии пока не могут дать нам желаемое. Тогда чем же нам придется довольствоваться? Со временем была разработана концепция иерархии памяти, согласно которой компьютеры обладают несколькими мегабайтами очень быстродействующей, дорогой и энергозависимой кэш-памяти, несколькими гигабайтами памяти, средней как по скорости, так и по цене, а также несколькими терабайтами памяти на довольно медленных, сравнительно дешевых дисковых накопителях, не говоря уже о сменных накопителях, таких как DVD – диски и флеш – устройства USB. [3]

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

1 ИЕРАРХИЧЕСКАЯ СТРУКТУРА ПАМЯТИ

Рисунок 1 – Четырехуровневая организация памяти

Виды памяти:

1) регистры микропроцессорной памяти, а также кэш-память первого и второго уровня;

2) внутренняя память ПЗУ, ОЗУ;

3) внешняя память;

4) массовая или архивная память.[3]

Эта система запоминающих устройств работает как единое ЗУ с большой емкостью (за счет внешних ЗУ) и высоким быстродействием (за счет внутренних ЗУ).

Микропроцессорная память – высокоскоростная память небольшой емкости, входящая в МП и используемая АЛУ для хранения операндов и промежуточных результатов вычислений. КЭШ-память – это буферная, не доступная для пользователя память, автоматически используемая компьютером для ускорения операций с информацией, хранящейся в медленно действующих запоминающих устройствах. Для ускорения операций с основной памятью организуется регистровая КЭШ-память внутри микропроцессора (КЭШ-память первого уровня) или вне микропроцессора на материнской плате (КЭШ-память второго уровня); для ускорения операций с дисковой памятью организуется КЭШ-память на ячейках электронной памяти.

Внутренняя память состоит из ПЗУ (ROM – Read Only Memory) и ОЗУ (RAM – Random Access Memory – память с произвольным доступом). ПЗУ состоит из установленных на материнской плате микросхем и используется для хранения неизменяемой информации: загрузочных программ операционной системы (ОС), программ тестирования устройств компьютера и некоторых драйверов базовой системы ввода-вывода (BIOS – Base Input-Output System) и др. Из ПЗУ можно только считывать информацию, емкость ПЗУ – сотни Кбайт. Это энергонезависимая память, – при отключении ЭВМ информация сохраняется.

Внешняя память относится к внешним устройствам ЭВМ и используется для долговременного хранения любой информации, которая может потребоваться. В ВЗУ хранится программное обеспечение ЭВМ. Внешняя память: НЖМД и ЖМД, НГМД и ГМД (магнитный диск), стример (НМЛ – накопитель на магнитной ленте), оптические накопители для CD-ROM и DVD-дисков. [4]

Информационная структура внешней памяти – файловая. Наименьшей именуемой единицей является файл, – наименованная совокупность однородных данных. Информация в файле состоит из битов и байтов, но они не имеют адресов, так как носитель (магнитный диск) не дискретный. [5]

2 КЭШИРОВАНИЕ

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

Кэш имеет совокупность строк (cache-lines), каждая из которых состо­ит из фиксированного количества адресуемых единиц памяти (байтов, слов) с последовательными адресами. Типичный размер строки: 16, 64, 128, 256 байтов.

Наиболее часто используются три способа организации кэш-памяти, отличающиеся объемом аппаратуры, требуемой для их реализации. Это так называемые кэш-память с прямым отображением (direct-mapped cache), частично ассоциативная кэш-память (set-associative cache) и ассоциатив­ная кэш-память (fully associative cache). [3]

При использовании кэш-памяти с прямым отображением адрес пред­ставляется как набор трех компонент, составляющих группы старших, средних и младших разрядов адреса, соответственно тега, номера строки, смещения. Например, при 16-разрядном адресе старшие 5 разрядов могут представлять тег, следующие 7 разрядов - номер строки и последние 4 раз­ряда - смещение в строке. В этом случае строка состоит из 16 адресуемых единиц памяти, всего строк в кэше 128. Кэш-память с прямым отображе­нием представляет собой набор строк, каждая из которых содержит ком­поненту тег и элементы памяти строки, адрес которых идентифицируется смещением относительно начала строки. При этом устанавливается однозначное соответствие между адресом элемента памяти и возможным расположением этого

элемента памяти в кэше, а именно: элемент памяти всегда располагается в строке, задавае­мой компонентой "номер строки" адреса, и находится на позиции строки, задаваемой компонентой "смещение" адреса. [2]

Наличие элемента данных по запрашиваемому адресу в кэше опреде­ляется значением тега. Если тег строки кэш-памяти равен компоненте "тег" адреса, то элемент данных содержится в кэш-памяти.

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

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

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

Ассоциативная кэш-память использует двухкомпонентное представле­ние адреса: группа старших разрядов трактуется как тег, а группа млад­ших разрядов - как смещение в строке.

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

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

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

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

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

Другой способ предполагает отображение изменений в основной па­мяти только в момент вытеснения строки данных из кэша. Если данные по адресу памяти, в который необходимо произвести запись, находятся в кэш-памяти, то идет запись только в кэш-память. При отсутствии данных в кэш-памяти производится запись в основную память. Такой режим рабо­ты кэша получил название обратной записи (write-back).

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

Кэш-память с обратной записью (write-back) создает меньшую нагрузку на шину процессора и обеспечивает большую производительность, однако контрол­лер для write-back кэша значительно сложнее.

Контроллер кэша отслеживает адреса памяти, выдаваемые процессо­ром, и если адрес соответствует данным, содержащимся в одной из строк кэша, то отмечается "попадание в кэш", и данные из кэша направляются в процессор. Если данных в кэше не оказывается, то фиксируется "промах", и инициируются действия по доставке в кэш из памяти требуемой строки. В ряде процессоров, выполняющих одновременно совокупность команд, допускается несколько промахов, прежде чем будет запущен механизм за­мены строк. [2]

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

Так как области памяти программ и данных различны и к ним проис­ходит одновременный доступ, то для повышения параллелизма при рабо­те с памятью делают отдельные кэши команд и данных. [4]

ЗАКЛЮЧЕНИЕ

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

А так же рассмотрели принципы работы и виды кэш-памяти. Кэш – это память с большей скоростью доступа, предназначенная для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа (далее «основная память»). Кэширование применяется ЦПУ, жёсткими дисками, браузерами и веб-серверами. Основная идея кэш-памяти проста: в ней находятся слова, которые чаще всего используются. Если процессору нужно какое-нибудь слово, сначала он обращается к кэш-памяти. Только в том случае, если слова там нет, он обращается к основной памяти. Если значительная часть слов находится в кэш-памяти, среднее время доступа значительно сокращается.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1 Майер, Р.В. Информатика: Кодирование информации. Принципы работы ЭВМ. [Текст] / Учебн. пособ. для вузов.// Р.В. Майер – М.: ФАИР – ПРЕСС, 2004. – 24 c.

2 Шнитман, В. Архитектура процессоров UltraSPARC. [Текст]/ В. Шнитман // Открытые системы №2, 1996.– c. 5

3 Таненбаум, Э. Современные операционные системы. 3-е изд. [Текст]/ – СПб.: Питер, 2002.–1120 с.

4 Трофимова, И.П. Системы обработки и хранения информации: Учеб. для вузов. [Текст] / И.П. Трофимова – М.: Высш. шк., 1989. – 191 c.

5 Бикташев, Р.А. , Князьков, В.С. Многопроцессорные системы. Архитектура, топология, анализ производительности: Учебное пособие. [Текст]/– Пенза: Пенз. гос. ун-т, 2003. –105 c.