Существенную часть кристалла современных ЦП занимает кэш-память. Дальнейшее увеличение кэш-памяти без изменения технологических норм приведет к соответствующему увеличению кристалла. Одним из способов увеличения объема хранимой информации в кэше без увеличения объёма самого кэша является использование алгоритмов компрессии. Среди них выделяются алгоритмы Base+Delta и Base-Delta-Immediate. Данная статья посвящена реализации первого алгоритма

Кэш-память состоит из кэш-строк фиксированного объема. 

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

B8-∆1 (Base = 8 Byte, ∆ = 1 Byte)B8-∆2B8-∆4B4-∆1B4-∆2B2-∆1

Ниже представлены примеры компрессии 32-ух байтовых кэш-строк

Декомпрессия происходит с помощью суммы базы и дельт. В данном примере осуществляется компрессия в режиме B4-∆1. Исходная строка, равная 32-ум байтам, сжимается до 12-ти байт

Данный алгоритм компрессии обоснован, во-первых, регулярностью расположения данных в памяти и, во-вторых, малым динамическим диапазоном значений в кэш-памяти. Объем сегментов отличается в зависимости от типа сжимаемых данных. Он может быть равен 2, 4 и 8 байтам. Использование только одного фиксированного объема сегментов может существенно повлиять на степень компрессии в худшую сторону. Например, для массива указателей объемом 4 байта оптимально использовать 4-ех байтовые сегменты, а для массива 2-ух байтовых целых чисел - сегменты объемом по 2 байта

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

Кэш-память имеет 16 кэш-строк объемом 64 байта, что позволяет хранить 1КБ данных без компрессии. У каждой кэш-строки помимо данных имеется бит достоверности, определяющий актуальность и достоверность данных, 8-ми байтовое поле тега, хранящий адрес младшего слова в памяти, 8 невидимых байт, о предназначении которых будет упомянуто в последующих разделах, и 3 младших бита, в которых хранится код компрессии

Каждая кэш-строка имеет вход, куда подаются данные, которые можно записать, если активен управляющий сигнал WE (Write Enable). Имеется асинхронный сброс, контролируемый сигналом reset. При сбросе все биты строки заполняются нулями. Выходные данные проходят через буферы трех состояний, контролируемые сигналом OE (Output Enable). На выходе появляются данные только при активности данного сигнала. Описание кэш-строки представлено ниже

С пословной адресацией (64 бит) требуется 8 слов для заполнения кэш-строки объемом 64 байт. Отсюда следует, что 3 младших бита поля тега (адрес младшего слова в памяти) должны быть равны 0. А в теге запроса младшие три бита будут обеспечивать выбор слова в кэш-строке. Для выбора самой кэш-строки (адрес кэш-памяти) нужно считать следующие 4 бита (так как кэш-строк 16 = 2^4) тега запроса (при чтении), либо тега в буфере чтения (при записи)

Когда включена компрессия, каждая кэш-строка может содержать 8, либо 16 слов. Тогда младшие 4 бита поля тега будут равны 0. Младшие 4 бита тега запроса будут обеспечивать выбор слова из кэш-памяти. Следующие 4 бита в теге запроса или в поле тега буфера чтения будут обеспечивать выбор кэш-строки

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

Операция чтения (RD активен) происходит следующим образом. По тегу запроса известно, в какой кэш-строке находятся данные. Затем поле тега передается и бит достоверности вместе с тегом запроса, а также вместе с сигналом CON передаются в фильтр запросов. Там происходит сравнение старших бит поля тега и старших бит тега запроса. Младшие 3 или 4 бита (в зависимости от сигнала CON) не сравниваются по той причине, что у тега запроса они служат для выбора слова. Если равенство устанавливается, а также бит достоверности равен 1, то сигнал кэш-попадание устанавливается в 0. В противном случае данный сигнал устанавливается в 1. 

Когда компрессия включена, но для строки нет режимов компрессии, отсеиваются запросы в первые 4 слова

Схема фильтра запросов описана ниже

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

Затем, имея адрес слова, схема WSU (Word Select UnIt) выводит одно из слов памяти на выход. Её описание представлено ниже

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

Вся система выглядит следующим образом

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

В статье, как вы увидели, отсутствуют тесты. Их вы можете посмотреть у авторов-разработчиков

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

Залил на github