Определение стратегии вытеснения PseudoLRU на ветвях бинарного дерева Евгений Корныхин (ВМК / ИСП РАН)

2 Кэш-память a1a1 a2a2 a3a3 d1d1 d2d2 d3d3 a1a1 a2a2 d1d1 d2d … кэш-память оперативная память a … hit a : a {a 1, a 2, …, a n } miss a : a {a 1, a 2, …, a n } anan dndn на чьё место поместить «а» ?

3 PseudoLRU: определение на бинарном дереве A / B C / D AB / CD A B C D v1v1 v2v2 v3v3 0 1

4 PseudoLRU: определение на бинарном дереве A / B C / D AB / CD A B C D v1v1 v2v2 v3v3 0 1 hit A: v 10 v 2 0 hit B: v 10 v 2 1 hit C: v 1 1 v 3 0 hit D: v 1 1 v 3 1 направления дуг к вытесняемому противоположны меткам вершин

5 Пример A B C D A

6 0 A B C D 0 Ahit

7 Пример 0 A B C D 0 Ahit B

8 Пример 0 A B C D 1 Ahit B

9 Пример 0 A B C D 1 Ahit B D

10 Пример 1 A B C D 1 1 Ahit B D

11 Пример 1 A B C D 1 1 Ahit B D EmissA

12 Где классическое определение не подходит ?hit ? ? ?miss miss x n x v 1 (1) v 2 (1) v 3 (1) v 1 (2) v 2 (2) v 3 (2) v 1 (3) v 2 (3) v 3 (3) hit ? n · w · R w ~ R ~ w*R ~

13 Новое определение: ветви бинарного дерева A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 )

14 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) (0 0)hit ( 0 0 )

15 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) (0 1)hit ( 0 1 ) (0 0)hit

16 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) (1 0)hit ( 1 0 ) (0 1)hit (0 0)hit

17 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) если сейчас будет miss, то вытеснится А (1 0)hit (0 1)hit (0 0)hit