Определение стратегии вытеснения PseudoLRU на ветвях бинарного дерева Евгений Корныхин (ВМК / ИСП РАН)
2 Кэш-память a1a1 a2a2 a3a3 d1d1 d2d2 d3d3 a1a1 a2a2 d1d1 d2d … кэш-память оперативная память a … anan dndn a
3 PseudoLRU: определение на бинарном дереве A / B C / D AB / CD A B C D v1v1 v2v2 v3v3 0 1
4 Классическое определение: пример A B C D A
5 0 A B C D 0 A
6 0 A B C D 0 A B
7 0 A B C D 1 A B
8 0 A B C D 1 A B D
9 1 A B C D 1 1 A B D
10 Классическое определение: пример 1 A B C D 1 1 A B D EA
11 Где классическое определение не подходит 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) x1x1 x2x2 n · w · R w ~ R ~ w · R ~ слишком много переменных
12 Новое определение: ветви бинарного дерева A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 )
13 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 )
14 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 )
15 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 ) B ( 0 1 )
16 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 ) B ( 0 1 )
17 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 ) B ( 0 1 ) C ( 1 0 )
18 Новое определение: пример A B C D ( 0 0 ) ( 0 1 ) ( 1 0 ) ( 1 1 ) A ( 0 0 ) B ( 0 1 ) C ( 1 0 ) при промахе сейчас вытеснится А