Программирование на JAVA

второго цикла элементы обрабатыва­ются в обратном порядке, то элементы, необходимые на первых двух проходах этого цикла, будут находиться в кэше. На третьем проходе (i = 7) элемент А(0,8) будет заменен элементом А(0,7), затем элементом А(0,6) и т. д. Таким образом, во время выполнения второго цикла в кэше будет заменено восемь элементов.

Нужно иметь в виду, что каждому блоку в кэше соответствует опре­деленный тег. На рисунке мы их не показываем, чтобы не занимать лишнего места.

Ассоциативный кэш

Как изменяется содержимое полностью ассоциативного кэша, можно судить по рис. 8.10. Если перед началом выполнения программы кэш пуст, на первых вось­ми проходах по циклу элементы массива копируются в последовательные пози­ции. Для эффективного кэширования данных важно, чтобы второй цикл переби­рал элементы массива в обратном порядке. Интересно посмотреть, что получится, если второй цикл пройдет по элементам в том же порядке, что и первый. Если используется алгоритм LRU, то во втором цикле все эле­менты будут перезаписаны еще до того, как они будут обработаны. Этого не про­изойдет, если применить алгоритм замены со случайной выборкой блоков.

Позиция блока

0

1

2

3

4

5

6

7

Содержимое кэша данных после выполнения цикла:

j = 7

j = 8

j = 9

i = 1

i = 0

А(0,0)

А(0,8)

А(0,8)

А(0,8)

А(0,0)

А(0,1)

А(0,1)

А(0,9)

А(0,1)

А(0,1)

А(0,2)

А(0,2)

А(0,2)

А(0,2)

А(0,2)

А(0,3)

А(0,3)

А(0,3)

А(0,3)

А(0,3)

А(0,4)

А(0,4)

А(0,4)

А(0,4)

А(0,4)

А(0,5)

А(0,5)

А(0,5)

А(0,5)

А(0,5)

А(0,6)

А(0,6)

А(0,6)

А(0,6)

А(0,6)

А(0,7)

А(0,7)

А(0,7)

А(0,7)

А(0,7)

Рис. 8.10. Содержимое ассоциативного кэша данных


<< назад вперед >>