2 из 21 Введение в Cache-oblivious алгоритмы: –Определение Cache-oblivious алгоритмов. –Модель памяти компьютера. –Cache-oblivious модель –Примеры сache-oblivious алгоритмов: Сумма элементов массива. Разворот массива. Cache-oblivious матричное перемножение: –Cache-aware алгоритм. –Cache-oblivious алгоритм. –Результаты экспериментов. Список литературы. Н.Новгород, 2011 г.Cache-oblivious algorithms Содержание

3 из 21 Введение в Cache-oblivious алгоритмы Н.Новгород, 2011 г.Cache-oblivious algorithms

Н.Новгород, 2011 г.Cache-oblivious algorithms 4 из 21 Cache-oblivious алгоритмы Cache-oblivious алгоритмы (кэш-независимые алгоритмы): Алгоритмы не делают никаких предположений о размере кэша и кэш линеек. Оптимальные cache-oblivious алгоритмы: Cache-oblivious алгоритмы использующие кэш оптимальным образом. Преимущества сache-oblivious алгоритмов: Алгоритмы работают одинаково эффективно на различных машинах: Различные иерархии памяти. Различные размеры кэша.

5 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Модель памяти компьютера CPU L1 L2 L3 Основная память Основная память Жесткий диск Скорость доступа к памяти Размер памяти

6 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Cache-oblivious модель B M B Доступ к кэшу считается бесплатным Память представлена в виде линеек размером B. Размер кэша M. Количество линеек в кэше M/B. Размер основной памяти считается неограниченным. В результате кэш промаха из основной памяти подгружается необходимая линейка. Если в кэше нет свободного места, происходит замена одной из линек, которая находится в кэше. Кэш Основная память

7 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Уточнение определения Cache-oblivious алгоритмы: Алгоритмы не знающие значения B и M. Оптимальные cache-oblivious алгоритмы: MT(N) (memory transfers) – количество доступов к памяти для решения задачи размером N. Оптимальные cache-oblivious алгоритмы имеют минимальную оценку MT(N). Оптимальные cache-oblivious алгоритмы работают одинаково оптимально для всех возможных B и M.

Примеры Cache-oblivious алгоритмов Н.Новгород, 2011 г.Cache-oblivious algorithms 8 из 21

9 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Сумма элементов массива int res = 0; for (int i = 0; i < N; i++) { res += array[i] } 12 34iN-1N MT(N) = O(N/B+1)

10 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Разворот массива for (int i = 0; i < N; i++) { int tmp = array[i]; array[i] = array[N-i]; array[N-i] = tmp; } 12 34iN-1N Если количество линек в кэше (M/B) >2 то: MT(N) = O(N/B+1)

Cache-oblivious матричное перемножение Н.Новгород, 2011 г.Cache-oblivious algorithms 11 из 21

12 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Постановка задачи Будут рассмотрены: Стандартная реализация. Cache-aware реализация. Cache-oblivious реализация.

Cache-aware реализация A A A 11 A 12 A 21 A 13 A 22 A 23 A 32 A 31 A 33 for (int i=0;i

14 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Cache-oblivious Рекурсивное перемножение элементов Z-блоков матрицы, используя Z-order. 4 итерации Z-ordera.*Пример 4ой итерации Z-ordera.** * Изображение с ** Изображение из Prokop H., Cache-Oblivious Algorithms by Harald Prokop

15 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Хранение матрицы A A A 11 A 12 A 22 A 21

Эксперименты Н.Новгород, 2011 г.Cache-oblivious algorithms 16 из 21

17 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Тестовая система Все эксперименты проводились на следующей машине: –Processor: Intel Core i5 2,53GHz. –L2 Cache (per Core): 256 KB. –L3 Cache: 3 MB. –RAM: 8Gb, DDR MHz. –ОС: Mac OS X (11C74) –Компилятор: i686-apple-darwin11-llvm-g (GCC) (Based on Apple Inc. build 5658) (LLVM build )

18 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Результаты t (c)

19 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Ускорение

20 из 21 Спасибо за внимание! ??? Н.Новгород, 2011 г.Cache-oblivious algorithms

21 из 21 Н.Новгород, 2011 г.Cache-oblivious algorithms Список литературы Prokop H., Cache-Oblivious Algorithms by Harald Prokop. Massachusetts Institute of Technology, Demaine Erik D., Cache-Oblivious Algorithms and Data Structures. MIT Laboratory for Computer Science. MIT's Introduction to Algorithms, Lectures 22 and 23: Cache Oblivious Algorithms. [ part-fourteen/].