Содержание
- 2. Outline Функционрование: ● взаимодействие с прикладными программами; ● принцип работы кэш-памяти; ● алгоритмы замещения. Резюме к
- 3. В предыдущей серии: Размер строки, тэга и индекса Любая кэш-память подразделяется на так называемые строки
- 4. В предыдущей серии: Размер строки, тэга и индекса ?Наконец, строка кэш-памяти может быть либо полностью
- 5. Структура записи в кэш Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty,
- 6. Строка кэша Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 7. Кэш-память: Размер строки, тэга и индекса 1.Ко всему прочему, каждая строка кэш-памяти обычно обладает некоторой
- 8. Уровни кэша Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 9. L1 Cache Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 10. Cache L2 Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 11. Cache L3 Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 12. Уровни кэша Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 13. Кэш жертв Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 14. Способы отображения основной памяти на кэш Алгоритм поиска и алгоритм замещения данных в кэше непосредственно
- 15. Физический факультет, ЭВУ и системы, 7 семестр,2010 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,
- 16. В кэшах, построенных на основе случайного отображения, вытеснение старых данных происходит только в том случае, когда
- 17. Способы отображения основной памяти на кэш Второй, детерминированный способ отображения предполагает, что любой элемент основной
- 18. Способы отображения основной памяти на кэш Второй, детерминированный способ отображения предполагает, что любой элемент основной
- 19. Способы отображения основной памяти на кэш В действительности запись в кэше обычно содержит несколько элементов
- 20. Способы отображения основной памяти на кэш Во многих современных процессорах кэш-память строится на основе сочетания
- 21. Кэш прямого отображения ПРИНЦИП Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty,
- 22. Кэш прямого отображения ПРИНЦИП Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty,
- 23. Кэш прямого отображения Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic
- 24. Кэш прямого отображения Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic
- 25. Кэш прямого отображения Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic
- 26. Наборно-ассоциативный кэш Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices
- 27. Наборно-ассоциативный кэш Поэтому полностью ассоциативный кэш используется редко и только на уровне L1. Как обычно, более
- 28. Наборно-ассоциативный кэш Например, на рис. в строках банков кэш-памяти, имеющих индекс 1, размещены строки с этим
- 29. Наборно-ассоциативный кэш Есть еще один блок – “флаги обращения”, который отсутствовал в кэш-памяти прямого отображения. Этот
- 30. Кэш-память: Кэш прямого отображения Direct Mapped Cache Introduction Let's assume, as we did for fully associate
- 31. Кэш-память: How do we decide which slot the cache line associated with address A31-0 should go
- 32. Кэш-память: The data you have might simply map to the same slot, and you could have
- 34. Скачать презентацию
Outline
Функционрование:
● взаимодействие с прикладными программами;
● принцип работы кэш-памяти;
●
Outline
Функционрование:
● взаимодействие с прикладными программами;
● принцип работы кэш-памяти;
●
Резюме к лекции и список используемой литературы
Кэш память :
● историческая справка;
● общие понятия;
● назначение.
Отображение на кэш:
● тег;
● проблема вытеснения;
● факторы присутствия;
● пространственная и временная локальности данных;
● строка кэша;
● проблема согласования данных;
● политики записи в кэш.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
В предыдущей серии: Размер строки, тэга и индекса
Любая кэш-память подразделяется
В предыдущей серии: Размер строки, тэга и индекса
Любая кэш-память подразделяется
Было бы крайне нерационально наделять каждый байт в кэш-памяти адресным полем, указывающим на его местонахождение в оперативной памяти
ПОЧЕМУ??
потому что это привело бы к очень тяжёлым последствиям с точки зрения производственных затрат.
ЗАЧЕМ??
Непонятно?!
?Если рассмотреть 32-битное линейное физическое адресное пространство, позволяющее непосредственно поддерживать до 4Гб оперативной памяти, каждый байт в кэш-памяти должен обслуживаться 4 адресными байтами!
?Кроме того, такая кэш-память была бы очень плоха с точки зрения производительности
Поэтому куда удобнее адресовать некоторые группы из соседствующих байт, которые и будут формировать строки кэш-памяти. На практике широко используются строки по 32 или 64 байта, хотя их размер может достигать даже 1024 байт. Естественно, размер строки должен быть эквивалентен двойке в некоторой целой положительной степени
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
В предыдущей серии: Размер строки, тэга и индекса
?Наконец, строка кэш-памяти
В предыдущей серии: Размер строки, тэга и индекса
?Наконец, строка кэш-памяти
?Промежуточные варианты не поддерживаются. Из этого правила есть одно исключение: если у двух строк кэш-памяти имеется одно общее адресное поле, тогда их можно рассматривать как подстроки одной строки, которые могут функционировать относительно независимо одна от другой.
Nota Bene: не путать с динамическими и статическими ячейками памяти, это другое.
Понятно! Однако, даже если требование по размеру выполнено, не каждая группа из соседствующих байт может быть кэширована по причине дополнительного ограничения, известного как адресное выравнивание (address alignment)
Коля в теме!
Другими словами, группа соседствующих байт может помещена в строку кэш-памяти ↔ , если её начальный адрес выровнен по границе, равной размеру строки.
Например, 32-байтная строка может быть заполнена информацией из оперативной памяти, находящейся по шестнадцатеричным (десятичным) адресам 00-1F (00-31), 20-3F (32-63), 40-5F (64-95) и т. д.
? Кроме иных преимуществ, это простое правило позволяет сократить число адресных бит в расчёте на одну строку. Если точнее, то на 5 в вышеприведённом примере, т. е. log2(32) = 5.
Каждое адресное поле состоит из двух основных частей:
статическая (index),
которая содержит младшие биты адреса:
значение зафиксировано
динамическая (tag),
которая содержит старшие биты адреса:
может быть изменена в процессе работы
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Структура записи в кэш
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент
Структура записи в кэш
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент
Типичная структура записи в кэше
непосредственную копию
данных из основной памяти.
данная запись содержит
актуальную (самую свежую) копию.
Адрес памяти разделяется (от старших бит к младшим)
на тег, индекс и смещение.
Для абстрактной системы с максимальным кэшируемым объёмом оперативной памяти в 1Гб и кэш-памятью (неважно какого уровня) размером в 1Мб с 2-канальной ассоциативностью потребуется ровно 11 бит для каждого тэга.
Другими словами, для адресации любым отдельным тэгом 1Гб / 512Кб = 2048 сегментов памяти потребуется log2(2048) = 11 бит.
Размер индекса зависит от размеров сегмента кэш-памяти и строки. Фактически, его должно быть достаточно для нумерации всех строк в пределах отдельно взятого сегмента. Например, если имеется сегмент кэш-памяти в 512Кб с 32-байтными строками, то размер индекса составит log2(512Кб / 32б) = 14 бит.
dynamic
static
При обращении к такой кэшу происходит сравнение тега адреса с тегами всех строк кэша, причем это сравнение происходит за один такт. если в результате сравнения тег адреса совпадет с тегом одной из строк, то это значит, что произошло КЭШ попадание, и нужный байт будет прочитан из выбранной строки по полю смещения. Если же тег адреса не совпал ни с одним тегом строк, то это –промах и нужная строка в кэша отсутствует.
Строка кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Строка кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Каждая строка в каком-либо сегменте имеет свой постоянный номер, который не подлежит изменению.
Если имеется N сегментов кэш-памяти, => N строк кэш-памяти с одинаковым индексом.
Увеличение размера строки при неизменном размере сегмента приведёт к уменьшению размера индекса, а также и к уменьшению их количества вследствие уменьшения числа строк.
В то же время увеличение размера строки приводит к увеличению задержек при загрузке/выгрузке строк из других уровней кэш-памяти или оперативной памяти.
К тому же, больший размер строки ухудшает эффективность кэш-памяти вследствие большей степени её засорения ненужной информацией.
Среднее время доступа к кэшу можно определить следующим образом:
tср = tобр + Рпр * tпр, где tобр - время обращения при попадании;
Рпр - потери времени при промахе; tпр – вероятность промаха.
Кэш-память: Размер строки, тэга и индекса
1.Ко всему прочему, каждая строка
Кэш-память: Размер строки, тэга и индекса
1.Ко всему прочему, каждая строка
2.Как правило, поля данных защищаются либо проверкой чётности (parity checking) на уровне отдельных байт, либо одним из протоколов проверки и коррекции ошибок (ECC — Error Checking and Correcting) на уровне целого поля, большинство из которых основывается на алгоритме Хэмминга (the Hamming algorithm).
3.Тэги могут защищаться однобитовой проверкой чётности, хотя эта практика распространена в значительно меньшей степени, чем защита полей данных.
4.Тем не менее, какой бы из алгоритмов защиты информации ни был выбран, его обслуживающая логика привнесёт сложности в существующую разработку и неминуемо отразится на задержках при работе.
5.Если точнее, то при каждой операции чтения контрольная сумма поля данных должна быть сосчитана и сверена с сохранённой. Наиболее тяжёлым является случай частичной записи в действительную строку, так как контрольная сумма должна быть сосчитана дважды: до и после изменения строки.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Уровни кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Уровни кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш центрального процессора разделён на несколько уровней. В универсальном процессоре в настоящее время число уровней может достигать 3.
Кэш-память уровня N+1 как правило больше по размеру и медленнее по скорости доступа и передаче данных, чем кэш-память уровня N.
Самой быстрой памятью является кэш первого уровня — L1-cache. По сути, она является неотъемлемой частью процессора, поскольку расположена на одном с ним кристалле и входит в состав функциональных блоков.
В современных процессорах обычно кэш L1 разделен на два кэша: кэш команд (инструкций) и кэш данных (в соответствии с Гарвардской архитектурой)
L1 Cache
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
L1 Cache
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Большинство процессоров без L1 кэша не могут функционировать.
L1 кэш работает на частоте процессора, и, в общем случае, обращение к нему может производиться каждый такт.
Зачастую является возможным выполнять несколько операций чтения/записи одновременно.
Латентность доступа обычно равна 2−4 тактам ядра, т.е. время доступа для выполнения элементарных операций.
Объём обычно невелик — не более 128 Кбайт.
Cache L2
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Cache L2
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Вторым по быстродействию является L2-cache — кэш второго уровня, обычно он расположен на кристалле, как и L1.
В старых процессорах — набор микросхем на системной плате.
Объём L2 кэша от 128 Кбайт до 1−12 Мбайт.
В современных многоядерных процессорах кэш второго уровня, находясь на том же кристалле, является памятью раздельного пользования — при общем объёме кэша в nM Мбайт на каждое ядро приходится по nM/nC Мбайта, где nC количество ядер процессора.
Обычно латентность L2 кэша, расположенного на кристалле ядра, составляет от 8 до 20 тактов ядра.
Cache L3
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Cache L3
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Кэш третьего уровня наименее быстродействующий, но он может быть очень внушительного размера — более 24 Мбайт. L3 кэш медленнее предыдущих кэшей, но всё равно значительно быстрее, чем оперативная память.
В многопроцессорных системах находится в общем пользовании и предназначен для синхронизации данных различных L2.
Иногда существует и 4 уровень кэша, обыкновенно он расположен в отдельной микросхеме. Применение кэша 4 уровня оправдано только для высоко производительных серверов и мейнфреймов.
Уровни кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Уровни кэша
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Проблема синхронизации между различными кэшами (как одного, так и множества процессоров) решается когерентностью кэша.
Существует 3 варианта обмена информацией
между кэш-памятью различных уровней
инклюзивный
эксклюзивный
неэксклюзивный
Инклюзивная архитектура предполагает дублирование информации кэша верхнего уровня в нижнем
Эксклюзивная кэш-память предполагает уникальность информации, находящейся в различных уровнях кэша
Неэксклюзивный кэш может вести себя как угодно.
Кэш жертв
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Кэш жертв
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
«Кэш жертв» (англ. Victim cache или Victim buffer) — это небольшой специализированный кэш, хранящий те кэш-линии, которые были недавно вытеснены из основного кэша микропроцессора при их замещении.
Обычно кэш жертв является полностью ассоциативным и служит для уменьшения количества конфликтных промахов (conflict miss). Многие часто используемые программы не требуют полного ассоциативного отображения для всех попыток доступа к памяти. По статистике, только небольшая доля обращений к памяти потребует высокой степени ассоциативности.
Именно для таких обращений служит кэш жертв, предоставляющий высокую ассоциативность для подобных редких запросов.
Размер такого кэша может составлять от 4 до 16 кэш-линий.
Способы отображения основной памяти на кэш
Алгоритм поиска и алгоритм замещения
Способы отображения основной памяти на кэш
Алгоритм поиска и алгоритм замещения
Принцип прозрачности требует, чтобы правило отображения основной памяти на кэш-память не зависело от работы программ и пользователей.
При случайном отображении элемент оперативной памяти в общем случае может быть размещен в произвольном месте кэш-памяти.
Для того чтобы в дальнейшем можно было найти нужные данные в кэше, они помещаются туда вместе со своим адресом, то есть тем адресом, который данные имеют в оперативной памяти.
При каждом запросе к оперативной памяти выполняется поиск в кэше, причем критерием поиска выступает адрес оперативной памяти из запроса.
Очевидная схема простого перебора для поиска нужных данных в случае кэша оказывается непригодной из-за недопустимо больших временных затрат.
При кэшировании данных из оперативной памяти широко используются две основные схемы отображения:
случайное отображение
детерминированное отображение
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Физический факультет, ЭВУ и системы, 7 семестр,2010 Доцент Моховиков А..Ю. Physics
Физический факультет, ЭВУ и системы, 7 семестр,2010 Доцент Моховиков А..Ю. Physics
Способы отображения основной памяти на кэш
Для кэшей со случайным отображением используется так называемый ассоциативный поиск, при котором сравнение выполняется не последовательно с каждой записью кэша, а параллельно со всеми его записями.
Признак, по которому выполняется сравнение, называется тегом (tag). В данном случае тегом является адрес данных в оперативной памяти. Электронная реализация такой схемы приводит к удорожанию памяти, причем стоимость существенно возрастает с увеличением объема запоминающего устройства. Поэтому ассоциативная кэш-память используется в тех случаях, когда для обеспечения высокого процента попадания достаточно небольшого объема памяти.
В кэшах, построенных на основе случайного отображения, вытеснение старых данных происходит
В кэшах, построенных на основе случайного отображения, вытеснение старых данных происходит
Выбор данных на выгрузку осуществляется среди всех записей кэша.
Обычно этот выбор основывается на тех же приемах, что и в алгоритмах замещения страниц, например выгрузка данных, к которым дольше всего не было обращений, или данных, к которым было меньше всего обращений.
Способы отображения основной памяти на кэш
Ассоциативный поиск в кэше со случайным отображением
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Способы отображения основной памяти на кэш
Второй, детерминированный способ отображения предполагает,
Способы отображения основной памяти на кэш
Второй, детерминированный способ отображения предполагает,
В этом случае кэш-память разделена на строки, каждая из которых предназначена для хранения одной записи об одном элементе данных1 и имеет свой номер.
Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти.
В качестве отображающей функции может использоваться простое выделение нескольких разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти (такое отображение называется прямым).
Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Способы отображения основной памяти на кэш
Второй, детерминированный способ отображения предполагает,
Способы отображения основной памяти на кэш
Второй, детерминированный способ отображения предполагает,
В качестве отображающей функции может использоваться простое выделение нескольких разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти (такое отображение называется прямым).
Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Способы отображения основной памяти на кэш
В действительности запись в кэше
Способы отображения основной памяти на кэш
В действительности запись в кэше
При поиске данных в кэше используется быстрый прямой доступ к записи по номеру строки, полученному путем обработки адреса оперативной памяти из запроса.
Однако поскольку в найденной строке могут находиться данные из любой ячейки оперативной памяти, младшие разряды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку.
Для этих целей каждая строка кэш-памяти дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. При совпадении тега с соответствующей частью адреса из запроса констатируется кэш-попадание.
Если же произошел кэш-промах, то данные считываются из оперативной памяти и копируются в кэш.
Заметим, что процесс замещения данных в кэш-памяти на основе прямого отображения существенно отличается от процесса замещения данных в кэш-памяти со случайным отображением.
Во-первых, вытеснение данных происходит не только в случае отсутствия свободного места в кэше,
Во-вторых, никакого выбора данных на замещение не существует.
Если строка кэш-памяти, в которую должен быть скопирован элемент данных из оперативной памяти, содержит другие данные, то последние вытесняются из кэша.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Способы отображения основной памяти на кэш
Во многих современных процессорах кэш-память
Способы отображения основной памяти на кэш
Во многих современных процессорах кэш-память
Все группы пронумерованы.
Поиск в кэше осуществляется вначале по номеру группы, полученному из адреса оперативной памяти из запроса, а затем в пределах группы путем ассоциативного просмотра всех записей в группе на предмет совпадения старших частей адресов оперативной памяти
При смешанном подходе произвольный адрес оперативной памяти отображается не на один адрес кэш-памяти (как это характерно для прямого отображения) и не на любой адрес кэш-памяти (как это делается при случайном отображении), а на некоторую группу адресов.
Комбинирование прямого и случайного отображения
При промахе данные копируются по любому свободному адресу из однозначно заданной группы. Если свободных адресов в группе нет, то выполняется вытеснение данных. Поскольку кандидатов на выгрузку несколько — все записи из данной группы — алгоритм замещения может учесть интенсивность обращений к данным и тем самым повысить вероятность попаданий в будущем.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Кэш прямого отображения
ПРИНЦИП
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш прямого отображения
ПРИНЦИП
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
В начале каждого обращения к кэшируемой памяти контроллер первым делом считывает ячейку каталога с соответствующим индексом, сравнивает биты адреса тега со старшими битами адреса памяти и анализирует признак действительности.
Этот анализ выполняется в специальном цикле слежения, который иногда называют циклом запроса. Если в результате анализа выясняется, что требуемого блока нет в кэше, генерируется цикл обращения к основной памяти - кэш-промах.
В случае попадания запрос обслуживается кэш-памятью.
Кэш прямого отображения
ПРИНЦИП
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш прямого отображения
ПРИНЦИП
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
В случае промаха после считывания основной памяти приемником информации новые данные помещаются в строку кэша при условии, что она чистая, а в ее тег помещаются старшие биты адреса и устанавливается признак действительности данных. Независимо от объема затребованных данных в кэш из основной памяти строка переписывается вся целиком.
Если контроллер кэша реализует упреждающее считывание, то в последующие свободные циклы шины обновляется также следующая строка, при условии, что она была чистой.
Чтение "про запас" позволяет при необходимости осуществлять пакетный цикл чтения из кэша через границу строки.
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Рассмотрим на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт.
Кэшируемая основная память условно разбивается на страницы (в данном случае по 256 Кбайт), размер которых совпадает с размером кэш-памяти(256 Кбайт).
Кэш-память делится на строки :
(256 Кбайт/32 байт = 8к строк).
Архитектура прямого отображения подразумевает, что каждая строка кэша может отображать из любой страницы кэшируемой памяти только соответствующую ей строку
(на рис. они находятся на одном горизонтальном уровне).
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Поскольку объем основной памяти больше объема кэша, на каждую строку кэша может претендовать множество блоков памяти с одинаковой младшей частью адреса (смещение внутри страницы).
Одна строка в определенный момент может, естественно, содержать копию только одного из этих блоков.
Номер (адрес) строки в кэш-памяти - это Index.
Кроме адресной части тега, с каждой строкой кэша связаны биты признаков действительности и модифицированности данных.
Тег несет информацию о том, какой именно блок занимает данную строку (т.е. старшая часть адреса или номер страницы).
Память тегов должна иметь количество ячеек, равное количеству строк кэша, а ее разрядность должна быть достаточной, чтобы вместить старшие биты адреса кэшируемой памяти, не попавшие на шину адреса кэш-памяти.
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Кэш прямого отображения
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков
Такой кэш имеет самую простую аппаратную реализацию и применяется во вторичном кэше большинства системных плат. Однако ему присущ серьезный недостаток
Если в процессе выполнения программы процессору поочередно будут требоваться блоки памяти, смещенные относительно друг друга на величину, кратную размеру страницы (на рисунке эти блоки расположены на одной горизонтали в разных страницах), то кэш будет "буксовать" - работать интенсивно, но вхолостую.
Очередное обращение будет замещать данные, считанные в предыдущем и необходимые в последующем обращении, то есть будет иметь место сплошная череда кэш-промахов.
Увеличение размера кэша при сохранении архитектуры прямого отображения даст не очень существенный эффект, поскольку разные задачи будут претендовать на одни и те же строки кэша.
Объем кэшируемой памяти (Mcached) при архитектуре прямого отображения определяется объемом кэш-памяти (Vcache) и разрядностью памяти тегов (N):
Mcached = Vcache ˟ 2N.
В нашем примере:
Mcached = 256 Кбайт ˟ 28 = 64 Мбайт.
Наборно-ассоциативный кэш
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Наборно-ассоциативный кэш
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю.
Наборно-ассоциативный кэш
Поэтому полностью ассоциативный кэш используется редко и только на
Наборно-ассоциативный кэш
Поэтому полностью ассоциативный кэш используется редко и только на
Как обычно, более приемлемым техническим решением оказывается сочетание механизма прямого отображения и ассоциативного поиска.
Именно так и организован наборно-ассоциативный кэш, двухканальный (two ways) вариант которого показан на рисунке.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Каждый банк кэш-памяти в паре со связанным с ним одним блоком тэговой памяти работает по схеме кэша прямого отображения.
Однако наличие двух банков позволяет размещать в двухканальной наборно-ассоциативной кэш памяти сразу две строки, расположенные одинаково по отношению к границам двух различных страниц кэшируемой памяти.
Как видно, этот кэш, по сути, представляет собой сдвоенный кэш прямого отображения.
Наборно-ассоциативный кэш
Например, на рис. в строках банков кэш-памяти, имеющих индекс 1,
Наборно-ассоциативный кэш
Например, на рис. в строках банков кэш-памяти, имеющих индекс 1,
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Собственно в этом и заключается все, что можно отнести к термину “ассоциативный” в названии этого типа памяти. Однако это различие оказывается достаточным, чтобы заметно повысить вероятность нахождения в кэше нужной информации и производительность памяти в целом.
При обращении к памяти поиск нужной строки в кэше выполняется точно так же, как и в кэш-памяти прямого отображения, только этот поиск производится сразу для двух банков (точнее, в двух блоках тэговой памяти).
Наборно-ассоциативный кэш
Есть еще один блок – “флаги обращения”, который отсутствовал
Наборно-ассоциативный кэш
Есть еще один блок – “флаги обращения”, который отсутствовал
Этот блок используется для решения второй из задач управления кэш-памятью: определением той строки, которую приходится удалять при необходимости ввода в кэш новой строки и отсутствии в нем свободного места.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
В кэш-памяти прямого отображения такую задачу решать не приходилось, так как место для размещения любой строки определялось однозначно и при вводе новой строки удалялась информация, которая ранее на этом месте располагалась.
Кэш-память: Кэш прямого отображения
Direct Mapped Cache
Introduction
Let's assume, as we
Кэш-память: Кэш прямого отображения
Direct Mapped Cache
Introduction
Let's assume, as we
128 slots
32 bytes per slot
Parking Lot Analogy
Suppose we have 1000 parking spots. However, instead of being unnumbered, each parking spot is given a 3 digit number from 000 to 999.
Your parking spot is based on the first 3 digits of your student ID number.
What problem can occur? If you received your social security number (student ID) in Maryland, the first three digits of your student ID is likely to be in the low 200's.
Thus, there's a much higher chance someone will be in your parking spot. There's also a chance that parking spots numbered in the 900's might be mostly empty since few students may have student IDs with the first 3 digits in that range.
This is basically the direct-mapped scheme. The advantages of this scheme are that it's simple to find your parking spot. It can only be in one location.
Direct Mapped Scheme
In a direct mapped cache, we treat the 128 slots as if they were an array of slots. We can index into the array using binary numbers. For 128 slots, you need 7 bits. Thus, the index of the array is from 0000000two up to 1111111two.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Кэш-память:
How do we decide which slot the cache line associated
Кэш-память:
How do we decide which slot the cache line associated
Here's how we do it:
Since we have 128 slots, we need to specify which one slot we need the cache line to go in. This requires lg 128 = 7 bits. Where do we get the bits from? Directly from the address itself.
Bits A4-0 is still the offset. The slot number are the next 7 bits, Bits A11-5. The remaining bits, A31-12 is the tag.
Finding the Slot
Finding a slot is now easy. Suppose you have address B31-0.
Use bits B11-5 to find the slot.
See if bits B31-12 match the tag of the slot.
If so, get the byte at offset B4-0.
If not, fetch the 32 bytes from memory, and place it in the slot, updating valid bit, dirty bit, and tag as neededx
Drawbacks
The drawback of this scheme is obvious. Effectively, we have a hash table with a very simple hash function (use bits B11-5). This can cause collisions at that particular slot.
Unlike a hash table, we do not resolve such collisions by finding the next free slot. Instead, we overwrite the value in the slot.
Just think of the parking lot analogy. A direct mapped scheme works poorly if many students have permits for the same spot, while other spots have very few permits.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov
Кэш-память:
The data you have might simply map to the same
Кэш-память:
The data you have might simply map to the same
Advantages
If there's an advantage to the scheme, it's that it's very simple. You don't have to simultaneously match tags with all slots. You just have one slot to check.
If the data isn't in the slot, it's obvious that this is the slot to get evicted.
Why the Middle Bits?
We can pick any bits we want in the address, instead of the middle bits nearest the offset. Why did we pick those bits.
The problem with picking the high bits is that data and program tend to occupy a small section of memory. Because of that, they tend to share the same high bits.
This isn't so surprising. Consider a 10,000 page book, where each page has 5 digits (thus, there are pages 03401 and pages 00023). Grab any 100 consecutive pages, and the top two digits are highly like to be the same.
This can happen with data too. All the data will have very similar high bits. You want the bits as low as possible, so you get enough variation so that data can go into each slot with equal likelihood (so you hope).
You can't pick the low bits, because you need them to serve as the offset.
Summary
A direct-mapped cache scheme makes picking the slot very simple. It treats the slot as a large array, and the index of the array is picked from bits of the address (which is why we need the number of slots to be a power of 2---otherwise we can't select bits from the address)
The scheme can suffer from many addresses "colliding" to the same slot, thus causing the cache line to be repeatedly evicted, even though there may be empty slots that aren't being used, or being used with less frequency.
Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov