Принципы построения кэш



Pdf просмотр
страница1/11
Дата12.02.2017
Размер1.72 Mb.
Просмотров1855
Скачиваний0
ТипАнализ
  1   2   3   4   5   6   7   8   9   10   11

1

Содержание
1.
Введение .................................................................................................. 7 2.
Принципы построения кэш
- памяти: Три основных способа реализации ............................................................................ 14 2.1.
Принцип построения кэш-памяти
14 2.2. Три основных способа реализации кэш-памяти
21 2.3. Основные параметры кэш-памяти
26 3.
Анализ модели поведения и повышение производительности кэш
- памяти ..................................................... 31 3.1.
Анализ составляющих повышения производительности 31 3.3.
Уменьшение доли промахов
35 3.4.
Способы уменьшения доли промахов при обращении в кэш
42 3.5.
Уменьшение задержки при промахе
50 4.
Виртуальная память в вычислительных системах .................... 60 4.1.
Концепция виртуальной памяти.
60 4.2.
Характеристики и параметры механизма виртуальной памяти
65 4.3.
Пример механизма виртуальной памяти со страничной организацией
71 4.4.
Повышение производительности механизма виртуальной памяти
75 5.
Многоуровневая организация памяти с трансляцией адресов ................................................................................................... 80 5.1.
Интеграция двухуровневой кэш-памяти в общую систему виртуальной памяти
80 5.2. Иерархия памяти ЦП Альфа 21264 83

2

6.
Примеры иерархии памяти современных микропроцессоров ............................................................................... 89 6.1.
Иерархия памяти в процессорах семейства ARM
89 6.3.
Иерархия памяти в ЦП Intel-HP Itanium и Эльбрус Е2К 98 7.
Краткий обзор организации и модулей, используемых в иерархии памяти ................................................................................ 107 7.1.
Организация интерфейса в иерархии памяти
107 7.2.
Модули динамической памяти DRAM
110 7.3.
Модули статической памяти SRAM
124 7.4.
Встроенная память ROM и FLASH
128
Список литературы .................................................................................. 128
Упражнения и задачи .............................................................................. 129
КОНТРОЛЬНЫЕ ВОПРОСЫ .................................................................. 133


3

Список рисунков
Рис. 1. Иерархия памяти в компьютерной системе. ........................... 11
Рис. 2. Пример упрощенного кэша прямого отображения, имеющего вдвое меньший объем по сравнению с основной памятью. ........................ 16
Рис. 3. Кэш-память прямого отображения объемом 4К байт с компаратором адресного тэга. ........................................................................ 19
Рис. 4. Отображение блоков данных из основной памяти в кэш- память прямого отображения, ассоциативную кэш-память и частично- ассоциативную кэш-память. ........................................................................... 22
Рис. 5. Структура ассоциативной кэш-памяти. ..................................... 23
Рис. 6. Иллюстрация доступа к различным типам кэш-памяти на примере кэша с 8 блоками (строками. ........................................................... 25
Рис. 7. Структура частично-ассоциативного кэша с двумя банками памяти. ............................................................................................................... 30
Рис. 8. Кэш команд процессора Альфа 21264, использующий предсказание доступа ...................................................................................... 34
Рис. 9. Использование кэша замещения для уменьшения конфликтов в кэше прямого отображения. ......................................................................... 45
Рис. 10. Структуры псевдо-ассоциативных КЭШей ........................... 47
Рис. 11. Структура кэша с потоковым буфером. .................................. 48
Рис. 12. Использование двух-уровневой кэш-памяти. ......................... 51
Рис. 13. Использование слияния операций записи. .............................. 55
Рис. 14. Упрощенная структура кэша с подблоками............................ 55
Рис. 15. Структура тракта чтения простейшего неблокирующего
КЭШа. ................................................................................................................ 58
Рис. 16. Размещение блоков (страниц) данных в основной памяти и внешней дисковой памяти. .............................................................................. 62

4

Рис. 17. Механизм виртуальной памяти ................................................ 64
Рис. 18. Таблица страниц в механизме виртуальной памяти ............. 69
Рис. 19. Организация таблицы страниц в механизме ВП ЦП Альфа
21264 .................................................................................................................. 72
Рис. 20. Механизм виртуальной памяти с кэшем, использующим физические адреса. ........................................................................................... 75
Рис. 21. Механизм виртуальной памяти с кэшем и буфером быстрой трансляции адресов .......................................................................................... 76
Рис. 22. Абстрактная структура двухуровневого кэша, комбинированного с ББТ адресов .................................................................. 81
Рис. 23. Тракт выборки команд в ЦП Альфа 21264 ............................. 86
Рис. 24. Тракт чтения/записи данных в ЦП Альфа 21264 ................... 88
Рис. 25. Структура кэша процессора ARM3 ......................................... 89
Рис. 26. Логика управляющего автомата кэша ARM .......................... 91
Рис. 27. Трансляция адресов в устройстве управления памятью процессора ARM .............................................................................................. 92
Рис. 28. Схема проверки прав доступа в устройстве управления памятью процессора ARM .............................................................................. 93
Рис. 29. Упрощенная структура ЦП Intel Pentium P4 ........................... 96
Рис. 30. Иерархия кэш-памяти в ЦП Intel-HP Itanium 2..................... 100
Рис. 31. Механизм защиты памяти и трансляции адресов в ЦП Intel-
HP Itanium ....................................................................................................... 102
Рис. 32. Транслирующий кэш L1 в ЦП Itanium 2 ............................... 104
Рис. 33. Интеграция блоков памяти и исполнительных устройств в
ЦП Itanium 2 .................................................................................................... 105
Рис. 34. Иерархия памяти в ЦП Эльбрус Е2К..................................... 107

5

Рис. 35. Увеличение пропускной способности памяти за счет ширины интерфейса ...................................................................................................... 108
Рис. 36. Организация интерфейса с многобанковой памятью. ......... 110
Рис. 37. Базовые элементы и структура модулей динамической
DRAM и статической SRAM памяти. .......................................................... 111
Рис. 38. Структуры интерфейса ЦП и модулей динамической памяти
DRAM различных типов. .............................................................................. 124



6

Список таблиц
Табл. 1. Параметры различных типов памяти. ................................... 10
Табл. 2. Структура модуля памяти упрощенного кэша прямого отображения. ..................................................................................................... 17
Табл. 3. Зависимость скорости доступа в кэш-память от объема и степени ассоциативности ................................................................................ 32
Табл. 4. Пример: последовательность обращений к памяти ............... 37
Табл. 5. Изменение доли промахов в зависимости от степени ассоциативности и объема кэш-памяти ......................................................... 44
Табл. 6. Сравнение сегментной и страничной организации механизма виртуальной памяти ......................................................................................... 66
Табл. 7. Структура прав доступа в ЦП Альфа 21264 ........................... 73
Табл. 8. Упрощенная структура Буфера Быстрой Трансляции (ББТ) 76
Табл. 9. Сравнение механизмов адресной трансляции в ЦП Pentium
Р4 и Opteron ...................................................................................................... 94
Табл. 10. Сравнение кэшей L1 и L2 ЦП Pentium Р4 и Opteron ......... 97
Табл. 11. Характеристики кэш-памяти в ЦП Itanium 2 ...................... 100
Табл. 12. Характеристики механизма трансляции адресов в ЦП
Itanium 2 .......................................................................................................... 103
Табл. 13. Параметры микросхем динамической памяти. .................. 113
Табл. 14. Возможная эволюция процессоров и DRAM с развитием технологии. ..................................................................................................... 122


7

«Видит око, да зуб неймет!»
(с) Народная пословица
1.
ВВЕДЕНИЕ
С самых ранних дней существования вычислительных машин программисты-пользователи хотели иметь практически неограниченный объем быстродействующей памяти, но возможности технологии и проблемы высокой стоимости всегда ограничивали реально доступный объем. Что можно было сделать разработчикам вычислительных систем в таких случаях?? Ведь фундаментальное противоречие между
«быстродействущий» и «большой объем» отменить в принципе нельзя, если брать в расчет стоимость аппаратуры.
Выход всегда был один – если нельзя сделать в реальности, то нужно попробовать создать иллюзию, что такая память существует. Но эта иллюзорная быстрая память, тем не менее, должна обеспечивать решение тех же самых задач для программиста, желающего иметь неограниченный объем быстродействующей памяти. И что самое главное
– сделать его счастливым обладателем уникального компьютера, который позволит нашему программисту забыть (хотя бы на время) о купленных им иллюзиях.
Содержание этого пособия посвящается методам и технологии иллюзионистов от инженерного сообщества, разрабатывавших компьютеры во второй половине 20-го века и делающих это сейчас.
Но прежде чем пытаться создать любую иллюзию необходимо провести анализ реальных жизненных ситуаций у потенциальных клиентов и создать специальные технические средства, которые позволят исполнить задуманное с выгодой для клиента и собственного кармана.
Поговорим о конкретной ситуации пользователя, программа которого обрабатывает большой объем данных, в принципе не помещающийся в быстрой памяти ЦП, но в тоже время ему нужно обработать эту информацию значительно быстрее по сравнению с доступом к данным во внешнюю медленную память из каждой команды
ЦП. Попробуем сравнить характер доступа программы пользователя к данным с работой студента в университетской библиотеке во время подготовки реферата.
ПРИМЕР ДОСТУПА К ДАННЫМ:
Шаг 1. Студент: Найти книги из рекомендованного списка
литературы по каталогу.

8


Программа:

Cгенерировать
адреса
расположения
данных.
Шаг 2. Студент: Заказать и получить все книги из списка
литературы.
Программа: Выкачать данные из внешней памяти во
внутреннюю регистровую память ЦП.
Ограничения для обоих: Сколько книг может поднять
студент и сколько данных может поместиться в регистровой
памяти ЦП.
Шаг 3. Студент: Сесть за стол и начать работать над
первой частью реферата, используя первую книгу из
списка, читая страница за страницей и часто возвращаясь
назад для уяснения деталей..
Программа: Начать обрабатывать данные из первого
массива, делая частые циклы обращения к последовательным
элементам массива.
Шаг 4. Студент: Повторить шаг 3 для всех источников
литературы из списка и закончить первую часть реферата.
Программа: Повторить шаг 3 для всех массивов данных,
перегружая
их
во
внутреннюю
память
по
мере
необходимости.
Шаг 5. Студент: Перейти к работе над второй частью
реферата и вернуться к использованию первой книги из
списка, читая страница за страницей и часто возвращаясь
назад для уяснения деталей.
Программа: Вернуться к обработке данных из первого
массива, делая частые циклы обращения к последовательным
элементам массива.
Шаг 6. Студент: Повторить шаг 5 для всех источников
литературы из списка и закончить вторую часть реферата.
Программа: Повторить шаг 5 для всех массивов данных,
перегружая
их
во
внутреннюю
память
по
мере
необходимости.
Дальнейшие действия будут повторением уже описанных с учетом различий для последующих разделов реферата и массивов данных.

9

Беглый анализ действий студента и программы показывает, что имеется два вида локальности доступа к источникам литературы и данным.
Локальность
доступа
во
времени
(temporal
locality) – когда книга или массив данных имеют тенденцию быть востребованы для повторного чтения или доступа в течении относительно короткого промежутка времени.
Локальность доступа в пространстве (spatial
locality) – когда страницы книги или элементы массива данных имеют тенденцию быть прочитаны последовательно один за другим в предсказуемой манере.
Что это значит с точки жизненных ситуаций пользователя программ? Говоря по-простому, ему абсолютно не нужны все массивы данных для обработки сразу, но в каждом массиве он может обрабатывать соседние элементы либо последовательно, либо в коротких циклах.
Иногда ему нужно перегрузить заново уже удаленный массив, чтобы продолжить обработку отдельных элементов, которые по какой-либо причине не были обработаны в первых проходах. Характер действий программы и характеристика доступа к данным в большинстве случаев предсказуемы и имеют последовательный характер.
Локальность доступа в программах происходит из самой природы программ. К примеру, большинство программ содержат циклы, доступ как к командам так и элементам данных будет повторяться во времени, создавая локальность доступа во времени. С другой стороны, программа исполняется всегда последовательно, и мы почти всегда можем предугадать, какие команды будут выбираться для исполнения в ближайших тактах ЦП. Похожая ситуация возникает и с данными при обработке массивов; следущий в последовательности элемент массива с большой вероятностью будет обрабатываться в последующей группе инструкций. Это создает локальность доступа в пространстве.
Как можно использовать данную ситуацию для создания иллюзии
«быстрой памяти большого объема», имея в распоряжении быструю и крайне дорогую регистровую память ЦП, более дешевые элементы статической памяти SRAM и еще более дешевые, но медленные элементы динамической памяти DRAM? Можно также включить в рассмотрение дисковую память большого объема (массовую память) и почти исчезнувшую память на магнитных лентах, которые на несколько порядков величины медленнее кремниевых аналогов.
Ответом и главным принципом создания иллюзии «быстрая память большого объема» является иерархическая организация памяти компьютерной системы, в которой с помощью специальных аппаратных

10
средств соединены все вышеуказанные типы памяти, образуя конфигурацию, вполне приемлемую по цене и быстродействию. Причем, эти специальные аппаратные средства для объединения различных видов памяти в единую иерархическую структуру должны быть абсолютно прозрачны (невидимы) для пользователя программ, который даже и не подозревает, что его откровенно «надувают» иллюзионисты.
Как выглядят с точки зрения стоимости и скорости доступа технические средства, которые можно было бы использовать для создания иллюзии «быстрой памяти большого объема»? В Табл. 1 приведены типовые данные по технологии памяти на 2004 год.
Табл. 1. Параметры различных типов памяти.
Технология памяти
Типичное время
доступа
Стоимость за Мегабайт
Register RAM Регистровая память
250 – 1000 пикосекунд
Очень дорого, на порядок величины по сравнению со статической памятью
SRAM Статическая память
0.5 – 5 наносекунд
$4 - $10 , достаточно дорого
DRAM Динамическая память
50 – 70 наносекунд
$0.1 - $0.2 вполне доступно
Магнитные диски
5 – 20 миллисекунд
$0.0005-$0.002 очень недорого
Магнитные ленты
Секунды и минуты
Совсем дешево
Теперь поговорим об инженерных делах и внутреннем устройстве иллюзиона, а также о том, как снизить затраты на его построение.
Главный принцип – иерархическое построение, которое предусматривает предоставление пользователю максимально возможного объема памяти, типичного для наиболее дешевой технологии памяти с одновременным представлением скорости доступа, которую предусматривают наиболее быстрые и дорогие технологии памяти.
Рис. 1 иллюстрирует иерархию памяти с отображением базовых характеристик памяти на каждом уровне и ширины обмена между уровнями.
Можно заметить, что объем доступной памяти в системе возрастает с номером уровня иерархии (уровень иерархии регистров ЦП=0) с одновременным падением стоимости.

11

Регистры ЦП
1K - 16K байт
Статическая
RAM
Память уровня +1
16K - 8M байт
Память уровня + 2
64M - 64G байт
Память уровня + 3
100G - 500T байт
Накопитель на жестком диске
Вентили
Динамическая
RAM
Объем памяти
Стоимость/бит
Скорость доступа
Наименьший
Наибольший
Высокая
Низкая
Быстрая
Медленная
Рис. 1. Иерархия памяти в компьютерной системе.
Следует отметить наиболее важные особенности иерархической структуры памяти:

Требование унифицированности доступа к элементу данных на всех уровнях, программа пользователя использует один и тот же унифицированный формат адреса команды или данных для доступа к памяти на любом уровне иерархии;

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

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

12


Обмен данными между уровнями памяти полностью скрыт от программы пользователя специальными аппаратными средствами и служебными утилитами операционной системы;

Обмен данными между уровнями может иметь разную ширину, которая варьируется от нескольких байт до К байт ( машинное слово 4-
8 байт, блок или строка 16, 32, 64 или 128 байт, страница или сегмент в
4К байт или больше).
Рассмотрим в деталях, что происходит при исполнении программы пользователя на машине с иерархической организацией памяти.
Каждый раз, когда исполняемая команда ЦП нуждается в данных из памяти, она обращается к ближайшему быстрому уровню памяти предполагая, что эти данные там окажутся. Если предположение оправдывается, то ЦП получает данные с минимально возможной задержкой и происходит «попадание» (Hit) в ближайший к ЦП уровень иерархии памяти. Если ожидание не оправдывается и необходимых данных на ближайшем уровне памяти нет, то происходит «промах»
(Miss). Тогда поиск необходимых данных производится на следующем
(+1) уровне иерархии памяти, что приводит к значительному простою ЦП в ожидании необходимых данных.
Мы можем характеризовать любой уровень иерархии памяти, кроме последнего, специальным «коэффициентом попаданий» (Hit rate), который показывает, какое количество обращений к данному уровню памяти было успешным, когда данные были найдены и считаны ЦП или предшествующим уровнем иерархии памяти. Коэффициент попаданий связан с «коэффициентом промахов» (Miss rate) следующим выражением:
Miss_Rate= 1 – Hit_Rate
«Коэффициент промахов» = (1 - «Коэффициент попаданий»)
И часто гораздо удобнее пользоваться вторым ввиду его относительно малой величин; предполагается, что система оптимизируется для минимизации промахов.
Другой характеристикой, которая связана с аппаратными возможностями является «Время успешного доступа» (Hit time), которое определяется аппаратной задержкой в определении самого факта попадания или промаха, к которой добавляется задержка в считывании самих данных, если данные найдены на этом уровне иерархии памяти.
Для характеристики последствий промахов используется «Время
промаха» (Miss penalty), которое включает в себя время, которое

13
необходимо для поиска и доставки необходимого блока данных с последующего уровня иерархии памяти.
Пожалуй это самые важные моменты в организации иерархической системы памяти, которая является критическим элементом в любой вычислительной системе, как с точки зрения производительности, так и стоимости.
Причем от качества исполнения иллюзиона
«Быстродействующая память большого объема» зависит производительность и стоимость многих миллионов больших и малых вычислительных систем.
Построение реальных подсистем памяти для компьютеров следующих поколений является сложной задачей, над которой бьются лучшие инженерные умы и крупные электронные компании всего мира. В данном учебном пособии описаны самые базовые принципы построения иерархических систем памяти в надежде, что в вашей последующей профессиональной деятельности вы сможете значительно глубже изучить все детали и даже разрабатывать аппаратное и программные средства для вычислительных систем следующего поколения.
В разделе 2 будут описаны принципы построения кэш-памяти
(Cache memory), которая является ближайшим уровнем памяти по отношению к ЦП. Уровень детализации примеров исполнения кэш- памяти является вполне достаточным для понимания работы большинства современных ЦП. Три основных способа реализации включают кэши прямого отображения, полностью ассоциативные и частично- ассоциативные кэши. Рассмотрены детали построения каждого типа кэшей с оценкой аппаратных затрат.
В разделе 3 основное внимание будет уделено оценке производительности и улучшению параметров кэш-памяти различной организации. Рассматривается многоуровневая кэш-память как один из типичных вариантов исполнения иерархической структуры памяти в современных микропроцессорах.
Приводятся способы оценки быстродействия и уровня аппаратных затрат.
В разделе 4 рассмотрена концепция виртуальной памяти, которая является основой построения практически всех современных компьютерных систем и включает в себя все уровни иерархии памяти.
В разделе 5 рассматривается многоуровневая организация памяти в вычислительной системе, которая включает интеграцию двухуровневой кэш-памяти в в общую систему виртуальной памяти. Рассматриваются механизмы трансляции виртуальных адресов в физические на всех уровнях системы памяти на примере ЦП Alpha 21264.

14

Раздел 6 предназначен для углубленного изучения реальных вариантов исполнения иерархии памяти в семействе процессоров ARM,
Intel Pentium P4 и AMD Opteron, Intel Itanium и Эльбрус Е2К. Его изучение является первым шагом на пути совершенствования вашего профессионализма.
Раздел 7 посвящен обзору уровня технологии и особенностям технического исполнения модулей памяти SRAM и DRAM, различных типов энергонезависимой памяти, используемых для реализации различных уровней иерархии памяти.
2.
ПРИНЦИПЫ ПОСТРОЕНИЯ КЭШ
-
ПАМЯТИ
:
ТРИ
ОСНОВНЫХ СПОСОБА РЕАЛИЗАЦИИ
2.1.
Принцип построения кэш
- памяти
В самом начале попробуем разобраться, что такое кэш-память
(



Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   10   11


База данных защищена авторским правом ©nethash.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал