Я напечатал это электронное письмо, чтобы кто-нибудь объяснил, в чем заключаются кеши, но я думаю, что оно может оказаться полезным и для вас.
У вас есть 32-битные адреса, которые могут ссылаться на байты в ОЗУ. Вы хотите иметь возможность кэшировать данные, к которым вы обращаетесь, чтобы использовать их позже.
Допустим, вам нужен кеш размером 1 МиБ (2 20 байтов).
Что вы делаете?
У вас есть 2 ограничения, которые необходимо соблюдать:
- Caching should be as uniform as possible across all addresses. i.e. you don't want to bias toward any particular kind of address.
- How do you do this? Use remainder! With mod, you can evenly distribute any integer over whatever range you want.
- You want to help minimize bookkeeping costs. That means e.g. if you're caching in blocks of 1 byte, you don't want to store 4 bytes of data just to keep track of where 1 byte belongs to.
- How do you do that? You store blocks that are bigger than just 1 byte.
Допустим, вы выбрали 16-байтовые (2 4 -байтовые) блоки. Это означает, что вы можете кэшировать 2 20 / 2 4 = 2 16 = 65 536 блоков данных.
Теперь у вас есть несколько вариантов:
- Вы можете спроектировать кэш так, чтобы данные из любого блока памяти могли храниться в любом из блоков кеша. Это будет называться полностью ассоциативным кешем.
- Преимущество в том, что это самый «честный» вид кеша: все блоки обрабатываются совершенно одинаково.
- Компромисс - скорость: чтобы найти, где разместить блок памяти, вы должны искать свободное пространство в каждом блоке кеша. Это очень медленно.
- Вы можете спроектировать кэш так, чтобы данные из любого блока памяти могли только храниться в одиночном блоке кеша. Это будет называться кешем с прямым отображением.
- Преимущество заключается в том, что это самый быстрый вид кеша: вы делаете только одну проверку, чтобы увидеть, находится ли элемент в кеше или нет.
- Компромисс заключается в том, что теперь, если у вас случается неправильный шаблон доступа к памяти, вы можете иметь 2 блока, которые последовательно выталкивают друг друга, а неиспользуемые блоки все еще остаются в кеше.
- Вы можете использовать и то, и другое: сопоставить один блок памяти с несколькими блоками. Это то, что делают настоящие процессоры - у них есть N-полосный ассоциативный кэш.
Кэш с прямым отображением:
Теперь у вас есть 65 536 блоков данных, каждый из которых состоит из 16 байтов.
Вы сохраняете их в виде 65 536 "строк" внутри вашего кеша, причем каждая "строка" состоит из самих данных вместе с метаданными (относительно того, где находится блок принадлежит, действителен ли он, был ли он записан и т. д.).
Вопрос: Каким образом каждый блок в памяти сопоставляется с каждым блоком в кэше?
Ответ: Ну, вы используете кеш с прямым отображением, используя mod. Это означает, что адреса от 0 до 15 будут сопоставлены с блоком 0 в кэше; 16-31 сопоставляются с блоком 2 и т. Д., И он оборачивается, когда вы достигаете отметки 1 МБ.
Итак, учитывая адрес памяти M, как найти номер строки N? Просто: N = M% 2 20 / 2 4.
Но это только говорит вам, где хранить данные, а не как получить его. После того, как вы сохранили его и попытаетесь получить к нему доступ снова, вы должны знать, какая часть памяти размером 1 МБ была сохранена здесь, верно?
Это одна часть метаданных: биты тега. Если он находится в строке N, все, что вам нужно знать, это то, каким было частное во время операции модификации. Что для 32-битного адреса составляет 12 бит (так как остаток составляет 20 бит).
Таким образом, ваш тег становится 12-битным, в частности, верхними 12-битами любого адреса памяти.
И вы уже знали, что самые младшие 4 бита используются для смещения внутри em> блок (поскольку память имеет байтовую адресацию, а размер блока - 16 байтов).
Это оставляет 16 бит для "индексных" битов адреса памяти, которые можно использовать для поиска , который em> строка, которой принадлежит адрес. (Это просто операция деления + остатка, но в двоичном формате.)
Вам также понадобятся другие биты: например, вам нужно знать, действительно ли блок действителен или нет, потому что, когда процессор включен, он содержит недопустимые данные. Итак, вы добавляете 1 бит метаданных: действительный бит.
Вы узнаете и о других битах, используемых для оптимизации, синхронизации и т. Д., Но это основные. :)