- снять ограничения, связанные с объемом памяти, при раз­работки алгоритмов;

- предоставлять программисту область памяти в виде логи­чески непрерывного пространства;

• способствовать более эффективному управлению физической памятью.

Процесс преобразование виртуальных адресов в физические при выполнении программы называется трансляцией адресов, наи­более распространенный механизм для этого - страничная память. Механизмы виртуальной памяти реализуется путем разбиения памяти и виртуальной и физической на одинаковые страницы, обычно, раз­мером 4 Кбайта. Адрес разделяется на две части в соот­ветствии с принятой длиной страницы: номер страницы (а) и адрес внутри страницы - сдвиг, смещение (б ). Трансляция адреса

Виртуальный адрес Физический адрес

а б - > с б

Аппаратно трансляция адресов производится при помощи таблицы страниц. Каждой страни­це виртуальной памяти соответствует строка в таблице страниц, объем которой соответствует числу страниц виртуальной памяти. В i строке таблицы хранится: N страницы (блока) физической па­мяти, которая соответствует данной виртуальной, статус доступа (чтение, запись), признак записи. Полный физический адрес получается добавлением к физи­ческому адресу, полученного из таблице страниц, смещения внутри страницы (б). Реальная структура таблицы страниц имеет более сложный вид.

1. Ассоциативная память.

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

1924021

9448304

3336167

Для получения номера телефона второго абонента следует обратиться: load (2) и получить в регистре ответа R = 9448304. Такой вид памяти, при котором необходимая информация определяется номером строки памяти, называется адресной. Другой вид оперативной памяти – ассоциативной можно рассматривать также как двумерную таблицу, но у каждой строки которой есть дополнительное поле, поле ключа. Например:

Ключ Содержимое

Иванов 1924021

Петров 9448304

Сидоров 3336167

После обращение к ассоциативной памяти с запросом : load (Петров) для данного примера получим ответ: R = 9448304. Здесь задание координаты строки памяти производится не по адресу, а по ключу. Но при состоянии ассоциативной памяти:

Ключ Содержимое

1 1924021

2 9448304

3 3336167

можно получить номер телефона из второй строки запросом: load (2). Таким образом на ассоциативной памяти можно моделировать работу адресной. Ассоциативная память имеет очевидное преимущества перед адресной, однако, у нее есть большой недостаток - ее аппаратная реализация невозможна для памяти большого объема.

ВОПРОС: Предложите схему реализации модели ассоциативной памяти при помощи адресной.

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

1. Назначение и структура кэш-памяти.

Для ускорения доступа к оперативной памяти используется буферизация данных и объектного кода в памяти, скорость которой значительно выше основной. Если бы доступ к любым типам данных был случайным, то буферизация была бы бесполезным. Эффект от буферизации можно определить среднему времени выборки: t = t2*p+ t1*(1-p), где t1 - среднее время доступа к данным основной памяти, t2 - среднее время доступа к данным из буфера (t2<t1), p - вероятность наличия данного в буфере. Очевидно, среднее время зависит от вероятности р и изменяется от среднего времени доступа к основной памяти (при p=0) до среднего времени доступа непосредственно в буфер (при p=1). Кэш (cache, cache memory) память, как правило, на порядок более быстрая, чем основная, размещается в качестве буферной, между процессором и основной памятью и служит для временного хранения (в рамках своего объема) всех данных, потребляемых или генерирумых процессором. В много-уровневых кэшах элементами связки: "процессор - основная память" могут выступать сами кеши. Алгоритм кэширования состоит в следующем:

1. По каждому запросу процессора происходит поиск требуемого дан­ного в кэш памяти (места для записи генерируемого данного).

2. Если данное (место) есть в кэше - кэш попадание (cache hit), то оно передается в процессор (из процессора).

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

Традиционным кэшем является "процессорный" кэш или кэш первого уровня (первичный) или кэш (L1 Cache), имеющийся на любом микропроцессоре. Это буферная память объемом от 4 Кбайт до 16 Мбайт, в которой размещаются все данные, адресуемые процессором, и из которой данные поставляются процессору. Эта память значительно быстрее основной, но меньшего объема, поэтому механизм кэширования обеспечивает обновление кэша, обычно, сохраняя в нем только наиболее часто употребляемые дан­ные. Обмен между основной и кэш памятями производится квантами, объ­емами 4 - 128 байт - копируются "строки кэша" (cache line), содержа­щие адресуемое данное.

Обычно, программный код кешируется через особый, I кэш память, отделенной от кэша данных D-кэша. Выборка данных из кэша (hit time) прозводится, обычно, за один такт синхронизации (оценки 1 - 4 такта), потери при кеш промахе оцени­ваются в 8 - 32 такта синхронизации, доля промахов (miss rate) - 1% -20%. По определению, эффект кэширования основан на предположении о многократном использовании данных (Data reuse) из кэш памяти. Принято различать две формы многократного использования данных кэша:- временное использование (temporal reuse). - пространственное использование (spatial reuse). Временное использование означает, что некоторое данное, загружен­ные в кэш, может использоваться, по крайней мере, более двух раз. Пространственное использование кэша предполагает возможность ис­пользовать некоторый пространственный набор данных - строки кэша. Архитектура кэш памяти: полностью ассоциативная, частично ассоциативная и кэш память с прямым отображением.

Для согласования содержимого кэш-памяти и оперативной памяти используют три метода записи:

• Сквозная запись (write through) - одновременно с кэш-памятью обновляется оперативная память.

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

• Обратная запись (write back) - используется бит изменения в поле тега, и строка переписывается в оперативную память только в том случае, если бит изменения равен 1.

Как правило, все методы записи, кроме сквозной, позволяют для увеличения производительности откладывать и группировать операции записи в оперативную память.

В структуре кэш-памяти выделяют два типа блоков данных:

• память отображения данных (собственно сами данные, дублированные из оперативной памяти);

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

Пространство памяти отображения данных в кэше разбивается на строки - блоки фиксированной длины (например, 32, 64 или 128 байт). Каждая строка кэша может содержать непрерывный выровненный блок байт из оперативной памяти. Какой именно блок оперативной памяти отображен на данную строку кэша, определяется тегом строки и алгоритмом отображения. По алгоритмам отображения оперативной памяти в кэш выделяют три типа кэш-памяти:

• полностью ассоциативный кэш;

• кэш прямого отображения;

• множественный ассоциативный кэш.

1. Полностью ассоциативная кэш-память.

http://www.intuit.ru/department/hardware/csorg/9/2.html

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

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

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

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

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

Пример:

Если объем ОЗУ – 4 Гбайт, тогда полный адрес - 32 бита можно представить в виде полей: 20 рр. – тэг (T), 7 рр – номер строки таблиц кэша (S), 5 рр – номер байта в строке (N). Поиск запрошенного байта (T-S-N) в кэше с прямым распределением производится так:

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

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

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

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

См. также Вопросы 15, 16. Компромиссным вариантом между первыми двумя алгоритмами является множественный ассоциативный кэш или частично-ассоциативный кэш (рис.). При этом способе организации кэш-памяти строки объединяются в группы, в которые могут входить 2, 4, 8, и т.д. строк. В соответствии с количеством строк в таких группах различают 2-входовый, 4-входовый и т.п. ассоциативный кэш. При обращении к памяти физический адрес разбивается на три части: смещение в блоке (строке кэша), номер группы (набора) и тег. Блок памяти, адрес которого соответствует определенной группе, может быть размещен в любой строке этой группы, и в теге строки размещается соответствующее значение. Очевидно, что в рамках выбранной группы соблюдается принцип ассоциативности. С другой стороны, тот или иной блок может попасть только в строго определенную группу, что перекликается с принципом организации кэша прямого отображения. Для того чтобы процессор смог идентифицировать кэш-промах, ему надо будет проверить теги лишь одной группы (2/4/8/… строк).