Как работает кеш с прямым сопоставлением?

Ответ 1

Хорошо. Поэтому давайте сначала понять, как процессор взаимодействует с кешем.

Существует три уровня памяти (в широком смысле) - cache (обычно из чипов SRAM), main memory (обычно из чипов DRAM) и storage (обычно магнитных, диски). Всякий раз, когда ЦП нуждается в каких-либо данных из определенного места, он сначала ищет кеш, чтобы узнать, есть ли он. Кэш-память лежит ближе всего к процессору с точки зрения иерархии памяти, поэтому его время доступа наименее (и стоимость является наивысшей), поэтому, если процессор данных, который ищет данные, можно найти там, он представляет собой "хит", а данные получается оттуда для использования CPU. Если его нет, то данные должны быть перенесены из основной памяти в кеш, прежде чем к нему будет доступен ЦП (процессор обычно взаимодействует только с кешем), что накладывает штраф времени.

Итак, чтобы узнать, есть ли данные в кэше или нет, применяются различные алгоритмы. Один из них - это метод прямого сопоставления кеша. Для простоты предположим, что система памяти, в которой имеется 10 доступных кэш-памяти (с номерами от 0 до 9), и 40 основных мест памяти (с номерами от 0 до 39). Это изображение подводит итог:

Доступно 40 основных мест памяти, но в кеше может быть размещено только до 10. Итак, теперь, каким-то образом, входящий запрос от ЦП необходимо перенаправить в местоположение кэша. У этого есть две проблемы:

• Как перенаправить? В частности, как это сделать предсказуемым образом, который со временем не изменится?

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

В нашем простом примере мы можем перенаправить с помощью простой логики. Учитывая, что нам необходимо отобразить 40 основных мест памяти, последовательно пронумерованных от 0 до 39 до 10 мест кэширования с номерами от 0 до 9, местоположение кэша для ячейки памяти n может быть n%10. Таким образом, 21 соответствует 1, 37 соответствует 7 и т.д. Это становится index.

Но 37, 17, 7 все соответствуют 7. Итак, чтобы различать их, появляется тег . Так что, как индекс n%10, тег int(n/10). Итак, теперь 37, 17, 7 будут иметь один и тот же индекс 7, но разные теги, такие как 3, 1, 0 и т.д. То есть отображение может быть полностью определено двумя тегами данных и индексом.

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

Ответ 2

Давайте используем пример. Кэш объемом 64 килобайта с 16-байтовыми линиями кэша имеет 4096 различных строк кэша.

Вам нужно разбить адрес на три разные части.

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

Число бит, которое вы используете для индекса, - log_base_2 (number_of_cache_lines) [это действительно количество наборов, но в прямом сопоставленном кеше есть одинаковое количество строк и наборов]

Ответ 3

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

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

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

Преимущество состоит в том, что чтение в основном представляет собой простой поиск в таблице и сравнение.

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

Ответ 4

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

В книге "Компьютерная архитектура - количественный подход" 3-е издание Хеннеси и Паттерсона, стр. 390.

Во-первых, имейте в виду, что основная память разделяется на блоки для кеша. Если у нас есть кеш на 64 байта и 1 ГБ ОЗУ, ОЗУ будет разделено на блоки размером 128 КБ (1 ГБ ОЗУ/64В кэша = 128 КБ Размер блока).

Из книги:

Где можно разместить блок в кеше?

• Если в каждом блоке есть только одно место, которое может появиться в кеше, кеш считается прямым отображением. Целевой блок вычисляется по следующей формуле: <RAM Block Address> MOD <Number of Blocks in the Cache>

Итак, предположим, что у нас есть 32 блока ОЗУ и 8 блоков кеша.

Если мы хотим сохранить блок 12 из ОЗУ в кеш, блок 12 ОЗУ будет храниться в блоке 4 кэша. Почему? Поскольку 12/8 = 1 остаток 4. Остаток - это целевой блок.

• Если блок может быть размещен в любом месте кеша, кеш считается полностью ассоциативным.

• Если блок можно разместить где угодно в ограниченном наборе мест в кеше, кеш устанавливается ассоциативно.

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

Формула: <RAM Block Address> MOD <Number of Sets in the Cache>

Итак, предположим, что у нас есть 32 блока ОЗУ и кеш, разделенный на 4 набора (каждый набор имеет два блока, что означает всего 8 блоков). Таким образом, значение 0 будет иметь блоки 0 и 1, для набора 1 будут блоки 2 и 3 и т.д....

Если мы хотим сохранить блок 12 RAM в кеш, блок ОЗУ будет храниться в блоках кэша 0 или 1. Почему? Поскольку 12/4 = 3 остатка 0. Поэтому выбирается 0, и блок может быть размещен где угодно внутри набора 0 (что означает блок 0 и 1).

Теперь я вернусь к исходной проблеме с адресами.

Как обнаружен блок, если он находится в кеше?

Каждый блок-блок в кеше имеет адрес. Просто, чтобы сделать это ясно, блок имеет как адрес, так и данные.

Адрес блока разделен на несколько частей: тег, индекс и смещение.

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

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

Итак, если вы хотите представить таблицу, это будут столбцы:

TAG | INDEX | OFFSET | DATA 1 | DATA 2 | ... | DATA N

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

Я надеюсь, что мое понимание этого правильное, если это не пожалуйста, сообщите мне.