Cache-oblivious алгоритмы - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:23:56Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:06, 1 сентября 2022

2022-09-01T05:06:42Z

Mervap в 10:47, 20 июня 2019

2019-06-20T10:47:50Z

Infovarius в 12:26, 14 ноября 2018

2018-11-14T12:26:39Z

Nemzs в 14:41, 31 августа 2017

2017-08-31T14:41:36Z

Nemzs в 14:35, 31 августа 2017

2017-08-31T14:35:44Z

Nemzs: tex правки

2017-08-31T13:21:49Z

tex правки

Внесённые изменения

Nemzs: переименовал Cache-oblivious алгоритм в Cache-oblivious алгоритмы

2017-08-31T13:21:26Z

переименовал Cache-oblivious алгоритм в Cache-oblivious алгоритмы

Nemzs: Очень сырая версия статьи

2017-08-30T18:55:21Z

Очень сырая версия статьи

Новая страница

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

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

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

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

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

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

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

← Предыдущая		Версия 16:23, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Введение ==		== Введение ==
	В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.		В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.

← Предыдущая		Версия 05:06, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Введение ==		== Введение ==
	В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.		В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.

@@ Строка 36: / Строка 36: @@
 == Источники информации ==
-* [http://logic.pdmi.ras.ru/csclub/courses/hugedataalgorithms Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
+* [https://www.lektorium.tv/course/22905 Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
 * [https://en.wikipedia.org/wiki/Cache-oblivious_algorithm Английская Википедия о cache-oblivious алгоритмах]
 [[Category:Кэш-память]]
 [[Категория:Алгоритмы]]

@@ Строка 38: / Строка 38: @@
 * [http://logic.pdmi.ras.ru/csclub/courses/hugedataalgorithms Максим Бабенко {{---}} Курс алгоритмов во внешней памяти.]
 * [https://en.wikipedia.org/wiki/Cache-oblivious_algorithm Английская Википедия о cache-oblivious алгоритмах]
 [[Category: Кэш память]]

@@ Строка 1: / Строка 1: @@
 В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.
 ''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи...
@@ Строка 23: / Строка 24: @@
-== Примеры ==
+== Примеры алгоритмов ==
 Простейший пример cache-oblivious алгоритма представлен в виде транспозиции матриц, причём в более сложном случае, когда матрицы не квадратные.

@@ Строка 1: / Строка 1: @@
-В программировании, cache-oblivious алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать кэш процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.
+В программировании, '''cache-oblivious''' алгоритмы {{---}} это алгоритмы спроектированные таким образом, чтобы использовать '''кэш''' (англ. ''cache'') процессора без привязки к значению размера кэша(или длины кэш-линий). Оптимальный cache-oblivious алгоритм {{---}} это cache-oblivious алгоритм, который использует кэш оптимально, в асимптотическом смысле, игнорируя не изменяющиеся факторы. Такие алгоритмы работают эффективно и без модификаций на различных машинах, не зависимо от размеров кэша на различных уровнях памяти.
 ''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи...
 Обычно, cache-oblivious алгоритмы используют метод Разделяй-и-властвуй, в котором задача разбивается на маленькие задачи и подзадачи. В процессе разделения, у нас получаются небольшие подзадачи. В какой-то момент, эти подзадачи начинают помещаться в размер кэша, мы не знаем в какой, но продолжаем делить до какого-то базового размера. Это исключит множественные перезаписи кэша, затем мы применим эффективный алгоритм для задачи небольших размеров, а дальше соединим результаты работы в ответ на исходную задачу. Например, cache-oblivious алгоритм перемножения матриц, получается рекурсивно разделяя каждую из матриц в четыре меньших матрицы, когда матрица полностью помещается в кэш {{---}} мы используем оптимизированный для небольших примеров матриц алгоритм, позже соединим результат функций в результирующую матрицу. Для перемножения можно использовать поиск в глубину.
@@ Строка 33: / Строка 33: @@
 Большинство cache-oblivious алгоритмов полагаются на метод разделяй-и-властвуй. Они разделяют задачу на подзадачи, которые в какой-то момент помещаются в размер кэша, каким бы маленьким он бы ни был. Затем завершают вызов рекурсии функцией на небольшом массиве, которая работает быстро используя оптимизации не зависимые от кэша. А потом из множества мелких результатов, эффективно соединяет ответ на задачу, используя базовые принципы работы кэша.

← Предыдущая	Версия 13:21, 31 августа 2017
(нет различий)