Cache-oblivious алгоритмы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 6 промежуточных версий 4 участников)
Строка 1: Строка 1:
В программировании, cache-oblivious алгоритмы - это алгоритмы спроектированные таким образом, чтобы использовать кэш процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм - это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя константные факторы. Такие алгоритмы работают хорошо, без модификаций, на различных машинах с различными размерами кэша, не зависимо от размеров кэша на различных уровнях памяти.
+
== Введение ==
 +
В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.  
 
''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи...  
 
''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи...  
Обычно, Cache-oblivious алгоритмы используют метод Разделяй и властвуй, в котором задача разбивается на маленькие задачи и подзадачи. В процессе разделения, меньше задачи начинают решаться помещаясь в кэш, при этом сам размер кэша не играет роли. Например, cache-oblivious алгоритм перемножения матриц получается рекурсивно разделяя каждую из матриц в четыре меньших матрицы для перемножения используя поиск в глубину.
+
Обычно, cache-oblivious алгоритмы используют метод Разделяй-и-властвуй, в котором задача разбивается на маленькие задачи и подзадачи. В процессе разделения, у нас получаются небольшие подзадачи. В какой-то момент, эти подзадачи начинают помещаться в размер кэша, мы не знаем в какой, но продолжаем делить до какого-то базового размера. Это исключит множественные перезаписи кэша, затем мы применим эффективный алгоритм для задачи небольших размеров, а дальше соединим результаты работы в ответ на исходную задачу. Например, cache-oblivious алгоритм перемножения матриц, получается рекурсивно разделяя каждую из матриц в четыре меньших матрицы, когда матрица полностью помещается в кэш {{---}} мы используем оптимизированный для небольших примеров матриц алгоритм, позже соединим результат функций в результирующую матрицу. Для перемножения можно использовать поиск в глубину.  
  
== Идеализированная кэш модель ==
+
== Идеализированная кэш модель ==  
  
Cache-oblivious алгоритмы обычно оцениваются при помощи упрощённой модели кэша, иногда называется cache-oblivious модель. Эта модель куда проще для анализа, нежели реальные характеристики кэша, но в большинстве случаев можно оценить с небольшой погрешностью реальную сложность.
+
Cache-oblivious алгоритмы обычно оцениваются при помощи упрощённой модели кэша, иногда называемой cache-oblivious модель. Эта модель куда проще для анализа по сравнению с реальными характеристиками кэша. В большинстве случаев, эта оценка оказывается близка к реальной сложности исполнения, с небольшой погрешностью.  
  
В частности, cache-oblivious модель является абстрактным исполнителем(т.е. теоретическая модель исполнения). Она схожа с оперативной моделью памяти, которая замещает бесконечным массивом бесконечную ленту машины Тьюринга.
+
В частности, cache-oblivious модель является абстрактным исполнителем(то есть теоретическая модель исполнения). Она схожа с оперативной моделью памяти, которая замещает бесконечную ленту машины Тьюринга на бесконечный массив.  
Любое место внутри массива доступно за время O(1), схоже с оперативной памятью в реальном компьютере. В отличие от оперативной памяти, мы так же представим кэш : второй уровень хранения данных между оперативной памятью и процессором. Ещё некоторые различия моделей выше:
+
В ней любое место внутри массива доступно за время <tex>O(1)</tex>, что схоже с оперативной памятью в реальном компьютере. В отличие от оперативной памяти памяти, мы так же определим кэш {{---}} это второй уровень хранения данных между оперативной памятью и процессором. Ещё некоторые различия моделей выше:  
* Память разбита на линии L слов каждая.
+
* Память разбита на линии <tex>L</tex> слов каждая.  
* Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша.
+
* Загрузка или хранение данных между главной памятью и регистрами процессора сейчас обрабатывается при помощи кэша.  
* Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss).
+
* Если загрузка или хранение данных не может быть выполнено из кэша, это называется кэш промахом (cache miss).  
* Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные <tex>w</tex> и строка <tex>b</tex> содержит слово <tex>w</tex>, тогда в кэш будет загружена строка <tex>b</tex>. Если кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения.
+
* Данные кэш промаха загружаются из основной памяти в кэш. В частности, если процессор хочет получить данные <tex>w</tex> и строка <tex>b</tex> содержит слово <tex>w</tex>, тогда в кэш будет загружена строка <tex>b</tex>. Если же кэш был до этого заполнен, тогда строчка так же записывается в кэш с учётом правил замещения.  
* Кэш содержит Z слов, где Z = omega(L^2).
+
* Кэш содержит <tex>Z</tex> слов, где <tex>Z = \Omega (L^2)</tex>.  
* Кэш полностью ассоциативный, каждая строка данных может быть загружена в любую из строк кэша.
+
* Кэш полностью ассоциативный. Это означает, что каждая строка данных основной памяти может быть загружена в любую из строк кэша.  
* Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к целому списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени <tex>t</tex>, он заглянет в последовательность следующих обращений и очистит строку, которая будет использоваться через самый длительный промежуток времени.
+
* Принцип замещения строк оптимальный. Другими словами, кэш имеет доступ к полному списку запросов к памяти во время запуска алгоритма. Если нужно выбросить строку в момент времени <tex>t</tex>, он заглянет в последовательность следующих обращений и очистит строку, которая будет использоваться через самый длительный промежуток времени.  
  
Чтобы измерить сложность алгоритма, использующего cache-oblivious модель, мы можем посчитать похожую сложность работы <tex>W(n)</tex>. Иначе, мы можем измерить сложность кэша <tex>Q(n,L,Z)</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>Q(n,L,Z)</tex>. Так же, в отличии от
 +
модели внешней памяти, которая имеет множество из вышеперечисленных свойств, мы хотели бы иметь алгоритм, независящий от характеристик кэша(<tex>L</tex>, и <tex>Z</tex>). Преимущество такого алгоритма в том, что при запуске на реальных машинах, нам не нужно будет для каждой настраивать параметры под систему, а значит он будет более простым и эффективным на реальных машинах. Поэтому же, оптимальный cache-oblivious алгоритм будет эффективно работать на машинах с более чем двумя уровнями иерархии памяти.  
  
  
== Примеры ==
+
== Примеры алгоритмов ==  
  
Простейший пример cache-oblivious алгоритмы представлен в виде транспозиции матриц , в более сложном случае, когда матрицы не квадратные.
+
Простейший пример cache-oblivious алгоритма представлен в виде транспозиции матриц, причём в более сложном случае, когда матрицы не квадратные.  
Дан массив m*n <tex>A</tex> и массив <tex>B</tex>. Мы будем хранить транспозицию из A в B. Нативное решение переворачивает строчки массива в столбцы по одной. В результате, когда матрицы становятся всё больше, мы получаем кэш промах на каждом шаге переворота столбца. Тогда общее количество кэш промахов <tex>O(mn)</tex>
+
Дан массив <tex>m*n</tex> <tex>A</tex> и массив <tex>B</tex>. Мы будем хранить транспозицию из <tex>A</tex> в <tex>B</tex>. Нативное решение переворачивает строчки массива в столбцы по одной. В результате, когда матрицы становятся всё больше, мы получаем кэш промах на каждом шаге переворота столбца матрицы. Тогда общее количество кэш промахов будет <tex>O(mn)</tex>  
  
Cache-oblivious алгоритм имеет оптимальную сложность работы O(mn) и оптимальную сложность кэша O(1 + mn/L). Базовая идея - разделить транспозицию большой матрицы на две (под)матрицы. Мы делаем это разделением матрицы относительно наибольшего измерения матрицы, до того момента, пока матрица не поместится в кэш. Но так как мы не знаем размера кэша, матрицы будут продолжать рекурсивно делиться даже после этого момента, но эти дальнейшие разделения будут происходить внутри кэша. Когда расширения m и n будут достаточно небольшие, так что матрица m * n и результат транспозиции будут помещаться в кэш, сложность транспозиции такой матрицы будет O(mn) при O(mn/L) кэш промахов. Используя этот метод разделяй и властвуй на всей матрице, мы сможем добиться такой же сложности на всей матрице.
+
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> кэш промахов. Используя этот метод разделяй-и-властвуй на всей матрице, мы сможем добиться такой же сложности по всей матрице.  
  
(В принципе, мы можем продолжить делить матрицы до размера 1х1, но на практике используется больший базовый размер(например 16х16) для амортизации переизбытка рекурсивных вызовов.)
+
(В принципе, мы можем продолжить делить матрицы до размера <tex>1х1</tex>, но на практике используется больший базовый размер(например <tex>16х16</tex>), для амортизации переизбытка рекурсивных вызовов.)  
  
Большинство cache-oblivious алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким маленьким он бы ни был, завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу.
+
Большинство cache-oblivious алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким бы маленьким он бы ни был. Затем завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу, используя базовые принципы работы кэша.
 +
 
 +
== Источники информации ==
 +
* [https://www.lektorium.tv/course/22905 Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
 +
* [https://en.wikipedia.org/wiki/Cache-oblivious_algorithm Английская Википедия о cache-oblivious алгоритмах]
 +
 
 +
[[Category:Кэш-память]]
 +
[[Категория:Алгоритмы]]

Текущая версия на 19:23, 4 сентября 2022

Введение

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

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