Изменения

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

Обычно, Cachecache-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\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 алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким бы маленьким он бы ни был, . Затем завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу, используя базовые принципы работы кэша.