Кэширование памяти 2

Physics Faculty, Electronic Devices & Systems, 7th semester,2012

Dr. Mokhovikov

Кэширование памяти (продолжение)

Lection 14

● алгоритмы замещения.
Резюме к лекции и список используемой литературы
Кэш

память :
● историческая справка;
● общие понятия;
● назначение.

Отображение на кэш:
● тег;
● проблема вытеснения;
● факторы присутствия;
● пространственная и временная локальности данных;
● строка кэша;
● проблема согласования данных;
● политики записи в кэш.

Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov

подразделяется на так называемые строки (lines).

Было бы крайне нерационально

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

ПОЧЕМУ??

потому что это привело бы к очень тяжёлым последствиям с точки зрения производственных затрат.

ЗАЧЕМ??

Непонятно?!

?Если рассмотреть 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

Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices &

Systems, 7th semester,2012 Dr. Mokhovikov

Типичная структура записи в кэше

непосредственную копию
данных из основной памяти.

данная запись содержит
актуальную (самую свежую) копию.

Адрес памяти разделяется (от старших бит к младшим)
на тег, индекс и смещение.

Для абстрактной системы с максимальным кэшируемым объёмом оперативной памяти в 1Гб и кэш-памятью (неважно какого уровня) размером в 1Мб с 2-канальной ассоциативностью потребуется ровно 11 бит для каждого тэга.
Другими словами, для адресации любым отдельным тэгом 1Гб / 512Кб = 2048 сегментов памяти потребуется log2(2048) = 11 бит.

Размер индекса зависит от размеров сегмента кэш-памяти и строки. Фактически, его должно быть достаточно для нумерации всех строк в пределах отдельно взятого сегмента. Например, если имеется сегмент кэш-памяти в 512Кб с 32-байтными строками, то размер индекса составит log2(512Кб / 32б) = 14 бит.

dynamic

static

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

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

Каждая строка в каком-либо сегменте имеет свой постоянный номер, который не подлежит изменению.
Если имеется N сегментов кэш-памяти, => N строк кэш-памяти с одинаковым индексом.
Увеличение размера строки при неизменном размере сегмента приведёт к уменьшению размера индекса, а также и к уменьшению их количества вследствие уменьшения числа строк.
В то же время увеличение размера строки приводит к увеличению задержек при загрузке/выгрузке строк из других уровней кэш-памяти или оперативной памяти.
К тому же, больший размер строки ухудшает эффективность кэш-памяти вследствие большей степени её засорения ненужной информацией.

Среднее время доступа к кэшу можно определить следующим образом:
tср = tобр + Рпр * tпр, где tобр - время обращения при попадании;

Рпр - потери времени при промахе; tпр – вероятность промаха.

строка кэш-памяти обычно обладает некоторой избыточной информацией для надлежащего контроля

за ошибками.

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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

Кэш центрального процессора разделён на несколько уровней. В универсальном процессоре в настоящее время число уровней может достигать 3.

Кэш-память уровня N+1 как правило больше по размеру и медленнее по скорости доступа и передаче данных, чем кэш-память уровня N.

Самой быстрой памятью является кэш первого уровня — L1-cache. По сути, она является неотъемлемой частью процессора, поскольку расположена на одном с ним кристалле и входит в состав функциональных блоков.

В современных процессорах обычно кэш L1 разделен на два кэша: кэш команд (инструкций) и кэш данных (в соответствии с Гарвардской архитектурой)

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

Большинство процессоров без L1 кэша не могут функционировать.
L1 кэш работает на частоте процессора, и, в общем случае, обращение к нему может производиться каждый такт.

Зачастую является возможным выполнять несколько операций чтения/записи одновременно.
Латентность доступа обычно равна 2−4 тактам ядра, т.е. время доступа для выполнения элементарных операций.
Объём обычно невелик — не более 128 Кбайт.

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

Вторым по быстродействию является L2-cache — кэш второго уровня, обычно он расположен на кристалле, как и L1.
В старых процессорах — набор микросхем на системной плате.
Объём L2 кэша от 128 Кбайт до 1−12 Мбайт.
В современных многоядерных процессорах кэш второго уровня, находясь на том же кристалле, является памятью раздельного пользования — при общем объёме кэша в nM Мбайт на каждое ядро приходится по nM/nC Мбайта, где nC количество ядер процессора.
Обычно латентность L2 кэша, расположенного на кристалле ядра, составляет от 8 до 20 тактов ядра.

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

Кэш третьего уровня наименее быстродействующий, но он может быть очень внушительного размера — более 24 Мбайт. L3 кэш медленнее предыдущих кэшей, но всё равно значительно быстрее, чем оперативная память.

В многопроцессорных системах находится в общем пользовании и предназначен для синхронизации данных различных L2.
Иногда существует и 4 уровень кэша, обыкновенно он расположен в отдельной микросхеме. Применение кэша 4 уровня оправдано только для высоко производительных серверов и мейнфреймов.

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

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

Существует 3 варианта обмена информацией
между кэш-памятью различных уровней

инклюзивный

эксклюзивный

неэксклюзивный

Инклюзивная архитектура предполагает дублирование информации кэша верхнего уровня в нижнем

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

Неэксклюзивный кэш может вести себя как угодно.

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

«Кэш жертв» (англ. Victim cache или Victim buffer) — это небольшой специализированный кэш, хранящий те кэш-линии, которые были недавно вытеснены из основного кэша микропроцессора при их замещении.

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

замещения данных в кэше непосредственно зависят от того, каким образом

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

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

При кэшировании данных из оперативной памяти широко используются две основные схемы отображения:

случайное отображение

детерминированное отображение

Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov

Physics Faculty, Electronic Devices & Systems, 7th semester,2010

Dr. Mokhovikov

Способы отображения основной памяти на кэш 

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

Признак, по которому выполняется сравнение, называется тегом (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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

Рассмотрим на примере несекторированного кэша объемом 256 Кбайт с размером строки 32 байта и объемом кэшируемой основной памяти 64 Мбайт.

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

Кэш-память делится на строки :
(256 Кбайт/32 байт = 8к строк).

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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

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

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

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

Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems,

7th semester,2012 Dr. Mokhovikov

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

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

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

Объем кэшируемой памяти (Mcached) при архитектуре прямого отображения определяется объемом кэш-памяти (Vcache) и разрядностью памяти тегов (N):
Mcached = Vcache ˟ 2N.
В нашем примере:
Mcached = 256 Кбайт ˟ 28 = 64 Мбайт.

А..Ю. Physics Faculty, Electronic Devices & Systems, 7th

semester,2012 Dr. Mokhovikov

и только на уровне L1.

Как обычно,

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

Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov

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

Как видно, этот кэш, по сути, представляет собой сдвоенный кэш прямого отображения.

1, размещены строки с этим же индексом из 17-й и

255-й страниц кэшируемой памяти.

Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov

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

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

обращения”, который отсутствовал в кэш-памяти прямого отображения.

Этот блок используется для решения второй из задач управления кэш-памятью: определением той строки, которую приходится удалять при необходимости ввода в кэш новой строки и отсутствии в нем свободного места.

Физический факультет, ЭВУ и системы, 7 семестр,2012 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2012 Dr. Mokhovikov

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

we did for fully associate caches that we have:
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

associated with address A31-0 should go into?

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

same slot, and you could have cache lines going in

and out all the time.
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

и Duron», авторы Михаил Гук, Виктор Юров
Книга «Модернизация и

ремонт ПК»,автор Скотт Мюллер
Книга «Архитектура ЭВМ», автор Танненбаум
Книга «Организация ЭВМ», автор Хамахер

Используемая литература:

ЭВУ SUPER!!!

Physics Faculty, Electronic Computing Devices & Systems, 7th semester,2012 Dr.Mokhovikov Alexander Yurievich