Заметки CPU designer'a

Продолжаю делиться интересными заметками и материалами из мира hwdesign. Сегодня в прицеле книга - Hacker's Delight (есть в русском переводе, называется "Алгоритмические трюки для программистов")

Что интересного из этой книге можно подчерпнуть в контексте разработки микропроцессоров?

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

Есть два основных принципа, по которым можно судить/предполагать. Какие данные потребуются процессору в будущем, а какие нет. Это принципы пространственной и временной локальности. 

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

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

Не касаясь вопросов организации $ (direct mapped, Fully associative, N-way set associative, об этом поговорим в другом посте), задачу замещения неактуальных данных выполняют "политики замещения данных в $) Наиболее популярные: fifo, random, lru, plru.

В современных процессорах в основном применяются два последних подхода Least recently used/pseudo Least recently used

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

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

Элегантное мат.решение, которое прекрасно ложится на hw представлено в вышеупомянутой книге Hacker's Delight [7–9 An LRU Algorithm]. 

https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685