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

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

Systems, 7th semester,2013 Dr. Mokhovikov

Cache L3.
● Кэш жертв.
Список используемой литературы
Структура записи в кэш

:
● строка кэша;
● размер тэга и индекса .

Способы отображения основной памяти на кэш :
● случайное отображение;
● детерминированное отображение;
● комбинирование отображение.

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

Архитектуры кэша:
● кэш прямого отображения;
● наборно-ассоциативный кэш;
● полностью ассоциативный кэш.

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

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

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

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

dynamic

static

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

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

который не подлежит изменению.
Если имеется N сегментов кэш-памяти, =>

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

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

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

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

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

за ошибками.

2.Как правило, поля данных защищаются либо проверкой чётности (parity checking) на уровне отдельных байт, либо одним из протоколов проверки и коррекции ошибок (ECC — Error Checking and Correcting) на уровне целого поля, большинство из которых основывается на алгоритме Хэмминга (the Hamming algorithm).

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

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

5.Если точнее, то при каждой операции чтения контрольная сумма поля данных должна быть сосчитана и сверена с сохранённой. Наиболее тяжёлым является случай частичной записи в действительную строку, т.к. контрольная сумма должна быть сосчитана дважды: до и после изменения строки.

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

универсальном процессоре в настоящее время число уровней может достигать 3.

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

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

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

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

кэш работает на частоте процессора, и, в общем случае, обращение

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

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

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

он расположен на кристалле, как и L1.
В старых процессорах —

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

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

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

кэшей, но всё равно значительно быстрее, чем оперативная память.

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

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

множества процессоров) решается когерентностью кэша.
Существует 3 варианта обмена информацией
между

кэш-памятью различных уровней

инклюзивный

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

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

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

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

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

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

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

вытеснены из основного кэша микропроцессора при их замещении.

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

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

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

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

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

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

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

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

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

отображением используется так называемый ассоциативный поиск, при котором сравнение выполняется

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

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

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

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

нет свободного места.

Выбор данных на выгрузку осуществляется среди всех записей кэша.

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

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

Ассоциативный поиск в кэше со случайным отображением

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

предполагает, что любой элемент основной памяти всегда отображается в одно

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

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

может использоваться простое выделение нескольких разрядов из адреса RAM, которые

интерпретируются как номер строки кэш-памяти (такое отображение называется прямым).

Например, пусть в кэш-памяти может храниться 1024 записи, т.е. кэш имеет 1024 строки, пронумерованные от 0 до 1023.
Тогда любой адрес RAM может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.

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

кэше обычно содержит несколько элементов данных.
При поиске данных в

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

Если же произошел кэш-промах, то данные считываются из RAM и копируются в кэш.

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

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

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

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

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

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

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

Комбинирование прямого и случайного отображения

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

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

RAM из запроса, а затем в пределах группы путем ассоциативного просмотра всех записей в группе на предмет совпадения старших частей адресов RAM

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

При промахе данные копируются по любому свободному адресу из однозначно заданной группы. Если свободных адресов в группе нет, то выполняется вытеснение данных.
Поскольку кандидатов на выгрузку несколько — все записи из данной группы — алгоритм замещения может учесть интенсивность обращений к данным и тем самым повысить Pпопаданий в будущем.

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

первым делом считывает ячейку каталога с соответствующим индексом, сравнивает биты

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

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

информации новые данные помещаются в строку кэша при условии, что

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

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

с размером строки 32 байта и объемом кэшируемой основной памяти

64 Мбайт.

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

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

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

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

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

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

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

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

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

применяется в Cache L2.
Однако ему присущ серьезный недостаток:

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

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

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

даст не очень существенный эффект, поскольку разные задачи будут претендовать

на одни и те же строки кэша.

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

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

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

semester,2013 Dr. Mokhovikov

Наборно-ассоциативная архитектура кэша позволяет каждому блоку кэшируемой памяти претендовать на одну из нескольких строк кэша, объединенных в набор (set). Можно считать, что в этой архитектуре есть несколько параллельно и согласованно работающих каналов прямого отображения, где контроллеру кэша приходится принимать решение о том, в какую из строк набора помещать очередной блок данных.
В простейшем случае каждый блок памяти может помещаться в одну из двух строк (Two Way Set-Associative Cache – двухканальный наборно-ассоциативный кэш).
Такой кэш должен содержать два банка памяти тегов.
Номер набора (индекс), в котором может отображаться затребованный блок данных, однозначно определяется средней частью адреса (как номер строки в кэше прямого отображения). Строка набора, отображающая требуемый блок, определяется сравнением тегов (как и в ассоциативном кэше), параллельно выполняемым для всех каналов кэша.

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

Как обычно,

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

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

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

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

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

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

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

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

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

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

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

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

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

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 семестр,2013 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2013 Dr. Mokhovikov

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 семестр,2013 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2013 Dr. Mokhovikov

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 семестр,2013 Доцент Моховиков А..Ю. Physics Faculty, Electronic Devices & Systems, 7th semester,2013 Dr. Mokhovikov

и системы. Часть 1», автор Моховиков
Книга «Модернизация и ремонт

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

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

ЭВУ SUPER!!!

Physics Faculty, Electronic Devices & Systems, 7th semester,2013 Dr. Mokhovikov