Cache-oblivious алгоритмы
Введение
В программировании, cache-oblivious алгоритмы — это алгоритмы спроектированные таким образом, чтобы использовать кэш (англ. cache) процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм — это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти. Типичные cache-oblivious алгоритмы : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи... Обычно, cache-oblivious алгоритмы используют метод Разделяй-и-властвуй, в котором задача разбивается на маленькие задачи и подзадачи. В процессе разделения, у нас получаются небольшие подзадачи. В какой-то момент, эти подзадачи начинают помещаться в размер кэша, мы не знаем в какой, но продолжаем делить до какого-то базового размера. Это исключит множественные перезаписи кэша, затем мы применим эффективный алгоритм для задачи небольших размеров, а дальше соединим результаты работы в ответ на исходную задачу. Например, cache-oblivious алгоритм перемножения матриц, получается рекурсивно разделяя каждую из матриц в четыре меньших матрицы, когда матрица полностью помещается в кэш — мы используем оптимизированный для небольших примеров матриц алгоритм, позже соединим результат функций в результирующую матрицу. Для перемножения можно использовать поиск в глубину.
Идеализированная кэш модель
Cache-oblivious алгоритмы обычно оцениваются при помощи упрощённой модели кэша, иногда называемой cache-oblivious модель. Эта модель куда проще для анализа по сравнению с реальными характеристиками кэша. В большинстве случаев, эта оценка оказывается близка к реальной сложности исполнения, с небольшой погрешностью.
В частности, cache-oblivious модель является абстрактным исполнителем(то есть теоретическая модель исполнения). Она схожа с оперативной моделью памяти, которая замещает бесконечную ленту машины Тьюринга на бесконечный массив. В ней любое место внутри массива доступно за время , что схоже с оперативной памятью в реальном компьютере. В отличие от оперативной памяти памяти, мы так же определим кэш — это второй уровень хранения данных между оперативной памятью и процессором. Ещё некоторые различия моделей выше:
- Память разбита на линии слов каждая.
- Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша.
- Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss).
- Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные и строка содержит слово , тогда в кэш будет загружена строка . Если же кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения.
- Кэш содержит слов, где .
- Кэш полностью ассоциативный. Это означает, что каждая строка данных основной памяти может быть загружена в любую из строк кэша.
- Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к полному списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени , он заглянет в последовательность следующих обращений и очистит строку, которая будет использоваться через самый длительный промежуток времени.
Чтобы измерить сложность алгоритма, использующего cache-oblivious модель, мы можем посчитать схожую сложность работы . Иначе, мы можем измерить сложность кэша , число кэш промахов, которые произойдут при работе алгоритма.
Цель в создании хорошего cache-oblivious алгоритма — приблизить сложность работы нашего алгоритма, к оптимально работающему алгоритму в модели оперативной памяти, при этом уменьшить величину . Так же, в отличии от модели внешней памяти, которая имеет множество из вышеперечисленных свойств, мы хотели бы иметь алгоритм, независящий от характеристик кэша(, и ). Преимущество такого алгоритма в том, что при запуске на реальных машинах, нам не нужно будет для каждой настраивать параметры под систему, а значит он будет более простым и эффективным на реальных машинах. Поэтому же, оптимальный cache-oblivious алгоритм будет эффективно работать на машинах с более чем двумя уровнями иерархии памяти.
Примеры алгоритмов
Простейший пример cache-oblivious алгоритма представлен в виде транспозиции матриц, причём в более сложном случае, когда матрицы не квадратные. Дан массив и массив . Мы будем хранить транспозицию из в . Нативное решение переворачивает строчки массива в столбцы по одной. В результате, когда матрицы становятся всё больше, мы получаем кэш промах на каждом шаге переворота столбца матрицы. Тогда общее количество кэш промахов будет
Cache-oblivious алгоритм имеет оптимальную сложность работы и оптимальную сложность кэша . Базовая идея — разделить транспозицию большой матрицы на транспозицию двух меньших подматриц. А для этого мы делим нашу матрицу относительно её наибольшего измерения, до того момента, пока матрица не поместится в кэш. Но так как мы не знаем размера кэша, матрицы будут продолжать рекурсивно делиться даже после этого момента, но так как матрица уже будет помещаться в кэш, все дальнейшие разделения будут происходить внутри кэша, без перезаписей. Когда расширения m и n будут достаточно небольшие, так что матрица и результат транспозиции будут помещаться в кэш, сложность транспозиции такой матрицы будет при кэш промахов. Используя этот метод разделяй-и-властвуй на всей матрице, мы сможем добиться такой же сложности по всей матрице.
(В принципе, мы можем продолжить делить матрицы до размера , но на практике используется больший базовый размер(например ), для амортизации переизбытка рекурсивных вызовов.)
Большинство cache-oblivious алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким бы маленьким он бы ни был. Затем завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу, используя базовые принципы работы кэша.
