Просмотр исходного текста страницы Cache-oblivious алгоритмы

== Введение == 
В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти. 
''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи... 
Обычно, cache-oblivious алгоритмы используют метод Разделяй-и-властвуй, в котором задача разбивается на маленькие задачи и подзадачи. В процессе разделения, у нас получаются небольшие подзадачи. В какой-то момент, эти подзадачи начинают помещаться в размер кэша, мы не знаем в какой, но продолжаем делить до какого-то базового размера. Это исключит множественные перезаписи кэша, затем мы применим эффективный алгоритм для задачи небольших размеров, а дальше соединим результаты работы в ответ на исходную задачу. Например, cache-oblivious алгоритм перемножения матриц, получается рекурсивно разделяя каждую из матриц в четыре меньших матрицы, когда матрица полностью помещается в кэш {{---}} мы используем оптимизированный для небольших примеров матриц алгоритм, позже соединим результат функций в результирующую матрицу. Для перемножения можно использовать поиск в глубину. 

== Идеализированная кэш модель == 

Cache-oblivious алгоритмы обычно оцениваются при помощи упрощённой модели кэша, иногда называемой cache-oblivious модель. Эта модель куда проще для анализа по сравнению с реальными характеристиками кэша. В большинстве случаев, эта оценка оказывается близка к реальной сложности исполнения, с небольшой погрешностью. 

В частности, cache-oblivious модель является абстрактным исполнителем(то есть теоретическая модель исполнения). Она схожа с оперативной моделью памяти, которая замещает бесконечную ленту машины Тьюринга на бесконечный массив. 
В ней любое место внутри массива доступно за время <tex>O(1)</tex>, что схоже с оперативной памятью в реальном компьютере. В отличие от оперативной памяти памяти, мы так же определим кэш {{---}} это второй уровень хранения данных между оперативной памятью и процессором. Ещё некоторые различия моделей выше: 
* Память разбита на линии <tex>L</tex> слов каждая. 
* Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша. 
* Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss). 
* Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные <tex>w</tex> и строка <tex>b</tex> содержит слово <tex>w</tex>, тогда в кэш будет загружена строка <tex>b</tex>. Если же кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения. 
* Кэш содержит <tex>Z</tex> слов, где <tex>Z = \Omega (L^2)</tex>. 
* Кэш полностью ассоциативный. Это означает, что каждая строка данных основной памяти может быть загружена в любую из строк кэша. 
* Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к полному списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени <tex>t</tex>, он заглянет в последовательность следующих обращений и очистит строку, которая будет использоваться через самый длительный промежуток времени. 

Чтобы измерить сложность алгоритма, использующего cache-oblivious модель, мы можем посчитать схожую сложность работы <tex>W(n)</tex>. Иначе, мы можем измерить сложность кэша <tex>Q(n,L,Z)</tex>, число кэш промахов, которые произойдут при работе алгоритма. 

Цель в создании хорошего cache-oblivious алгоритма {{---}} приблизить сложность работы нашего алгоритма, к оптимально работающему алгоритму в модели оперативной памяти, при этом уменьшить величину <tex>Q(n,L,Z)</tex>. Так же, в отличии от
модели внешней памяти, которая имеет множество из вышеперечисленных свойств, мы хотели бы иметь алгоритм, независящий от характеристик кэша(<tex>L</tex>, и <tex>Z</tex>). Преимущество такого алгоритма в том, что при запуске на реальных машинах, нам не нужно будет для каждой настраивать параметры под систему, а значит он будет более простым и эффективным на реальных машинах. Поэтому же, оптимальный cache-oblivious алгоритм будет эффективно работать на машинах с более чем двумя уровнями иерархии памяти. 


== Примеры алгоритмов == 

Простейший пример cache-oblivious алгоритма представлен в виде транспозиции матриц, причём в более сложном случае, когда матрицы не квадратные. 
Дан массив <tex>m*n</tex> <tex>A</tex> и массив <tex>B</tex>. Мы будем хранить транспозицию из <tex>A</tex> в <tex>B</tex>. Нативное решение переворачивает строчки массива в столбцы по одной. В результате, когда матрицы становятся всё больше, мы получаем кэш промах на каждом шаге переворота столбца матрицы. Тогда общее количество кэш промахов будет <tex>O(mn)</tex> 

Cache-oblivious алгоритм имеет оптимальную сложность работы <tex>O(mn)</tex> и оптимальную сложность кэша <tex>O(1 + mn/L)</tex>. Базовая идея {{---}} разделить транспозицию большой матрицы на транспозицию двух меньших подматриц. А для этого мы делим нашу матрицу относительно её наибольшего измерения, до того момента, пока матрица не поместится в кэш. Но так как мы не знаем размера кэша, матрицы будут продолжать рекурсивно делиться даже после этого момента, но так как матрица уже будет помещаться в кэш, все дальнейшие разделения будут происходить внутри кэша, без перезаписей. Когда расширения m и n будут достаточно небольшие, так что матрица <tex>m * n</tex> и результат транспозиции будут помещаться в кэш, сложность транспозиции такой матрицы будет <tex>O(mn)</tex> при <tex>O(mn/L)</tex> кэш промахов. Используя этот метод разделяй-и-властвуй на всей матрице, мы сможем добиться такой же сложности по всей матрице. 

(В принципе, мы можем продолжить делить матрицы до размера <tex>1х1</tex>, но на практике используется больший базовый размер(например <tex>16х16</tex>), для амортизации переизбытка рекурсивных вызовов.) 

Большинство cache-oblivious алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким бы маленьким он бы ни был. Затем завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу, используя базовые принципы работы кэша.

== Источники информации ==
* [http://logic.pdmi.ras.ru/csclub/courses/hugedataalgorithms Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
* [https://en.wikipedia.org/wiki/Cache-oblivious_algorithm Английская Википедия о cache-oblivious алгоритмах]
[[Category: Кэш память]]