Cache-oblivious алгоритмы

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

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

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

В частности, cache-oblivious модель является абстрактным исполнителем(т.е. теоретическая модель исполнения). Она схожа с оперативной моделью памяти, которая замещает бесконечным массивом бесконечную ленту машины Тьюринга. Любое место внутри массива доступно за время O(1), схоже с оперативной памятью в реальном компьютере. В отличие от оперативной памяти, мы так же представим кэш : второй уровень хранения данных между оперативной памятью и процессором. Ещё некоторые различия моделей выше:

• Память разбита на линии L слов каждая.
• Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша.
• Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss).
• Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные [math]w[/math] и строка [math]b[/math] содержит слово [math]w[/math], тогда в кэш будет загружена строка [math]b[/math]. Если кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения.
• Кэш содержит Z слов, где Z = omega(L^2).
• Кэш полностью ассоциативный, каждая строка данных может быть загружена в любую из строк кэша.
• Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к целому списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени [math]t[/math], он заглянет в последовательность следующих обращений и очистит строку, которая будет использоваться через самый длительный промежуток времени.

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

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

Примеры

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

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

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

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