Алгоритм кеширования LRU - PullRequest
Новая
       34

Алгоритм кеширования LRU

0 голосов
/ 28 мая 2020

Мне нужен алгоритм LRU для 4-стороннего ассоциативного кеша с дополнительными 5 битами на набор, чтобы указать, какая строка должна быть исключена. 

       -------------------------------------
Set x: | line_0 | line_1 | line_2 | line_3 |
       -------------------------------------

      -----------------------------------------
      | bit_4 | bit_3 | bit_2 | bit_1 | bit_0 |
      -----------------------------------------

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

Жертвой будет строка с битом, установленным на 0 (при условии, что набор заполнен).

Я думал, что могу использовать это в 4-стороннем кеш-памяти, имеющем биты bit_4, bit_3, bit_1, bit_0, соответствующие line_0, line_1, line_2, line_3 и средний бит, указывающий, какая сторона использовалась последней. Я быстро понял, что это недостаточно точно. Т.е. после последовательности line_0, line_2, line_3, line_1 биты будут: 10101, что будет означать, что левая сторона ссылалась совсем недавно (что верно), но это не обязательно означает, что эта сторона не упоминался в последнее время.

Буду очень признателен за любые подсказки.

1 Ответ

1 голос
/ 28 мая 2020

Чтобы постоянно находить наименее недавно использованный элемент, вам необходимо отслеживать порядок, в котором 4 строки кэша использовались последними.

Их 4! возможные заказы. 4! это 24 возможности, и есть 32 возможных конфигурации ваших дополнительных 5 бит, так что у вас достаточно бит (ура!). Однако у вас не так много лишних битов, поэтому вы не можете ожидать, что с кодировкой заказа будет очень легко работать. сделайте это так:

  • 2 бита для наименее использованного элемента: 0–3. Это тот, который нужно выселить, если вам нужно.
  • 2 бита для 2-го наименее недавно использованного элемента: 0-3
  • 1 бит для 3-го наименее недавно использованного элемента. Есть только две возможности, потому что две другие уже используются. 0 означает оставшуюся строку кэша с меньшим номером.
  • 0 бит для последнего использования (4-е из последних использованных). Остался только один, поэтому вам не нужно ничего хранить, чтобы знать, какой именно.
...