Представим, что перед нами стоит задача перемножить две матрицы A и B размера n×n. Как можно это осуществить?

Применим алгоритм, действующий прямо по определению (назовем его Iterative). for i

Время его выполнения на реальной машине: 140 c (N = 2 10 ) Тестирование происходило на системе: Intel Core i5 2.27Ghz 4096 Mb L1 32 Kb x2 64 B L2 256 Kb x2 64 B Windows 7

Разобьём каждую матрицу на (n/s)*(n/s) подматриц Мij размером s×s Следующий алгоритм использует эту стратегию( Block-Mult ): for i

Изменение времени работы алгоритма от параметра s:

Для умножения можно воспользоваться следующим алгоритмом (обозначим его за Mult(A)): Для умножения матрицы A размером m×n на матрицу размером n×p рассматривается три случая: m >= max{n, p} AB = ( )B = ( ) n> = max{m,p} AB = (A 1 A 2 )( ) = A 1 B 1 + A 2 B 2 p> = max{m,n} AB = A(B 1 B 2 ) = (AB 1 AB 2 ) Это продолжается пока m = n = p = 1. A1 A2 A1B A2B B1 B2

Время его работы можно увидеть на графике:

Исследователи из MIT 1994 Чарльз Лейзерсон 1997 Гаральд Прокоп 1999

(Z, L) – идеальная модель кэша(ideal-cache model)(она будет использоваться для оценки сложности кэша (cache complexity))

Кэш-линии(cache lines) Высокий кэш(tall cache) (Z = (L 2 )) Попадание в кэш (cache hit) Промах кэша (cache miss) W(n) - рабочая сложность (work complexity) Q(n, Z, L) - кэш сложность (cache complexity). Кэш зависимый (cash aware) Кэш-независимый (cache oblivious)

Будут ли кэш-независимые алгоритмы, разработанные в рамках идеальной модели, работать также эффективно для модели с политиками LRU и FIFO или другой иерархией кэша? (Кэш сложность будет называться нормальной (regular), если Q(n; Z, L) = O(Q(n; 2Z, L))) Теорема: Оптимальный кэш-независимый алгоритм с нормальной кэш сложностью остается оптимальным в двухуровневой модели с вытесняющими политиками (LRU, FIFO).

- многоуровневая идеальная модель Свойство вложенности (inclusion property): Ʉi є [1,…, r-1] значения, хранимые в кэше i, хранятся и в кэше i+1 W(n), Qi(n; Zi, Li) - кэш сложности для i є[1,…,r] Теорема: Если кэш-независимый алгоритм оптимален в многоуровневой идеальной модели, то он вызывает оптимальное количество потерь кэша и на каждом уровне кэша. Теорема: Оптимальный кэш независимый алгоритм с нормальной кэш сложностью вызывает асимптотически оптимальное количество потерь кэша на каждом уровне кэша с оптимальной вытесняющей политикой или LRU. (Доказательство этих теорем можно найти в Harald Prokop. Cache-Oblivious Algorithms. Masters thesis, MIT )

Нужно перемножить две матрицы A и B размера n×n. Будем считать, что матрицы хранятся в построчном порядке и что n>L(чтобы упростить анализ). Построчный (row major) По столбцам (column major)

Iterative: for i

Block-Mult: for i

Mult(A): Для умножения матрицы A размером m×n на матрицу размером n×p рассматривается три случая: m >= max{n, p} AB = ( )B = ( ) n> = max{m,p} AB = (A 1 A 2 )( ) = A 1 B 1 + A 2 B 2 p> = max{m,n} AB = A(B 1 B 2 ) = (AB 1 AB 2 ) Это продолжается пока m = n = p = 1. ϴ(mnp), ϴ(m + n + p + (mn + np + mp)/L + mnp/L(Z 1/2 )) A1 A2 A1B A2B B1 B2

1. Самый быстрый с точки зрения асимптотической сложности алгоритм имеет не больше (lg Z) промахов кэша, чем асимптотически самый быстрый кэш зависимый алгоритм. 2. Если существует класс оптимальных кэш зависимых алгоритмов, решающих определённую задачу, то существует кэш-независимый алгоритм, решающий ту же задачу.

Нужно транспонировать квадратную A матрицу размера N×N. Применим алгоритм, действующий прямо по определению (назовем его Iterative). for (i = 0; i < N; i++) { for (j = i+1; j < N; j++) { tmp = A[i][j]; A[i][j] = A[j][i]; A[j][i] = tmp; }

Рассмотрим время его выполнения на реальной машине: Тестирование происходило на системе: UltraSPARC-II 300 MHz 512 мб L1 32 б 16 кб L2 64 б 2 мб SunOS 5.6 SUNs Workshop 4.2.

Время работы от размера от изменения входных данных можно увидеть на графике:

Если учесть затраты на ввод и вывод данных между кэшем и основной памятью, то можно в несколько раз уменьшить время работы алгоритма. Z - размер всего кэша L - длина линий кэша Aʳ΄ˢ = { ai,j | rL

Пример его применения: L =

Время его работы можно увидеть на графике:

Для транспонирования можно воспользоваться следующим алгоритмом (обозначим его за Transpose(A)): Вход: Матрица A размера m×n Выход: Матрица B размера n×m Если n>=m A = (A1 A2) B = ( ) Если n

Время его работы можно увидеть на графике:

Изменим размер линий кэша (L = 2 7 )

Изменим размер линий кэша (L = 2 6 )

Изменим размер линий кэша (L = 2 5 )

Гареев Роман КН - 301, 2011 год