Иерархическая организация памяти

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

Обычно рассматривается взаимодействие внутри иерархии памяти между двумя соседними уровнями.

Минимальную единицу информации, которая может либо присутствовать, либо отсутствовать на одном из двух взаимодействующих уровней в иерархии, мы будем называть блоком. Размер блока может быть либо фиксированным, либо переменным. Если этот размер зафиксирован, то объем памяти является кратным размеру блока.

При обращении к каждому уровню иерархии возможны два исхода. Либо искомый блок находится на запрашиваемом уровне (попадание – hit) либо он отсутствует (промах – miss) и приходится обращаться к следующему уровню иерархии, обладающему меньшей скоростью выборки. Эффективность механизма хранения данных можно описать долей попаданий (hit rate). Механизм организации каждого уровня иерархии должен обеспечивать возможность размещения любого блока из более низкого уровня иерархии. Отсюда – необходим некий ассоциативный механизм отображения блока из нижележащего уровня иерархии на вышележащий.

Иерархия памяти в ЭВМ показана на рис. 17. Емкость памяти растет сверху вниз на рисунке, стоимость хранения байта (слова) и скорость выборки байта (слова) растет снизу вверх.

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

Массовая оперативная память имеет объем от нескольких десятков килобайт до нескольких сотен мегабайт. В силу ряда технологических особенностей скорость обращения к оперативной памяти растет значительно медленнее, чем скорость работы центральных процессоров и обычно время выборки составляет от 5 до 15 тактов процессора. Для ускорения выборки информации между основной памятью и центральным процессором вводится еще один уровень иерархии – промежуточная, сверхоперативная память или кэш память. Слово cache в переводе с английского яыка означает тайник, тайный склад, потаенный запас. Смысл этого термина состоит в том, что кэш-память невидима, прозрачна для центрального процессора. Работой кэш-памяти управляет контроллер кэш-памяти. Он просматривает обращения центрального процессора к основной памяти и определяет хранятся ли требуемые данные в кэше (cache hit) и,следовательно, могут быть прочитаны из него, или нет (cache miss), и следовательно, придется производить обращение к более медленной основной памяти. Скорость доступа к ячейке кэш-памяти может составлять от 3 до 7 тактов процессора. Кэш-память в свою очередь сама может быть реализована по иерархическому принципу, т.е. может быть разделена на несколько уровней:

· кэш первого уровня, объемом несколько килобайт со временем доступа 2-3 такта, встроенный непосредственно в процессор;

· кэш второго уровня со временем доступа 3-5 тактов и объемом несколько десятков килобайт, расположенный на одной плате с центральным процессором;

· кэш третьего уровня со временем доступа 5-7 тактов и объемом несколько сотен килобайт на системной плате и так далее.

Ниже в этом разделе мы вернемся обсуждению кэш-памяти и рассмотрим ее функционирование подробнее.

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

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

В системе с виртуальной памятью программы «считают», что им предоставлено некоторое, достаточно большое адресное пространство (пространство, предоставленное программе или группе программ, может существенно превышать объем физической памяти, имеющейся в ЭВМ). При этом рабочее пространство разделяется на блоки – страницы (типичный размер страницы 2–4 Кбайта). Страницы, относящиеся к выполняемой задаче, частично располагаются в быстродействующей памяти, частично на некотором, более медленном и более дешевом запоминающем устройстве. Устройство управления виртуальной памяти отслеживает обращения к памяти, и, если требуемая страница отсутствует в физической памяти, происходит прерывание. Обработчик прерывания производит обращение к внешнему устройству для считывания отсутствующей страницы, после чего выполнение команды, вызвавшей прерывание, повторяется снова. Таким образом, прикладная программа “не замечает”, что ее страница отсутствовала в памяти. Естественно, что из-за необходимости периодических обращений к внешней памяти за отсутствующими страницами скорость выполнения программы снижается. Это снижение скорости есть “необходимое зло” - плата за большой размер доступного адресного пространства. Разработчики процессоров с виртуальной адресацией предусматривают различные средства максимального снижения эффекта замедления.

Системы виртуальной памяти можно разделить на два класса: системы с фиксированным размером блоков, называемых страницами, и системы с переменным размером блоков, называемых сегментами. Ниже рассмотрены оба типа организации виртуальной памяти.

Кэш-память

Как уже говорилось выше, назначение кэш-памяти – временное хранение данных и команд, часто используемых процессором. Основной структурной единицей кэш-памяти является так называемая строка кэша (cache line). Длина строки кэша составляет обычно 32, 64, 128 или 256 байт.

Рассмотрим способы организации кэш-памяти, принятые в современных ЭВМ. Опишем возможные способы отображения адресов данных в оперативной памяти на адреса данных в кэш-памяти и, соответсвенно, способы поиска требуемых данных в кэш-памяти. Пусть, в качестве упрощенного примера, существует ЭВМ с десятибитным адресом. Следовательно, объем непосредственно адресуемой оперативной памяти составляет 2¹⁰ байт. Пусть имеется кэш-память из восьми строк, каждая строка из восьми байт. Организация кэш-памяти показана на рис 18. С каждой строкой кэша связано поле тэга. Тэг (tag – пометка, отметка) – признак, используемый при поиске требуемых данных.

Существуют три основных способа организации кэш-памяти: 1) кэш с прямым отображением; 2) полностью ассоциативный кэш; 3) наборно ассоциативный кэш.

В случае кэша с прямым отображением адрес, формируемый процессором, имеет вид, показаный на рис 18 а). Адрес состоит из трех частей. Младшие биты адреса определяют конкретный байт в строке кэша. Их количество k определяется длиной строки кэша L

k = log₂L.

Средние биты адреса определяют одну из строк кэша. Количество n средних битов определяется количеством M строк кэша

n = log₂M.

											тэг

тэг	строка	байт

а)

											тэг

Тэг	байт

б)

											тэг

тэг	набор	байт

в)

Рис 18. Кэш-память. а) с прямым отображением; б) полностью ассоциативная; в) наборно-ассоциативная.

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

Достоинство кэша с прямым отображением – очевидная простота реализации. Недостаток состоит в том, что несколько адресов с одинаковыми младшими k + n битами могут претендовать на одну и ту же ячейку кэша.

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

Третий вид кэш-памяти – наборно-ассоциативная (см. рис 18 в)) – это смешанная конструкция, сочетающая в себе простоту памяти с прямым отображением и эффективность ассоциативного кэша. Строки кэша объединяются в наборы по 2, 4, 8 и т.д. штук. Средние биты определяют не строку, а набор. Конкретная строка в наборе выбирается с помощью ассоциативного сравнения для всех строк, входящих в набор.

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

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

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

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

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