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

Введение

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

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

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

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

• Память разбита на линии [math]L[/math] слов каждая.
• Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша.
• Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss).
• Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные [math]w[/math] и строка [math]b[/math] содержит слово [math]w[/math], тогда в кэш будет загружена строка [math]b[/math]. Если же кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения.
• Кэш содержит [math]Z[/math] слов, где [math]Z = \Omega (L^2)[/math].
• Кэш полностью ассоциативный. Это означает, что каждая строка данных основной памяти может быть загружена в любую из строк кэша.
• Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к полному списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени [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 алгоритма представлен в виде транспозиции матриц, причём в более сложном случае, когда матрицы не квадратные. Дан массив [math]m*n[/math] [math]A[/math] и массив [math]B[/math]. Мы будем хранить транспозицию из [math]A[/math] в [math]B[/math]. Нативное решение переворачивает строчки массива в столбцы по одной. В результате, когда матрицы становятся всё больше, мы получаем кэш промах на каждом шаге переворота столбца матрицы. Тогда общее количество кэш промахов будет [math]O(mn)[/math]

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

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

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

Источники информации

• Максим Бабенко — Курс алгоритмов во внешней памяти.
• Английская Википедия о cache-oblivious алгоритмах