Алгоритм без кеширования

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

Оптимальные алгоритмы кэш-забывающий известны матрицы умножения , транспонирования матрицы , сортировки и ряд других проблем. Некоторые более общие алгоритмы, такие как БПФ Кули – Тьюки , оптимально игнорируют кеш-память при определенном выборе параметров. Поскольку эти алгоритмы оптимальны только в асимптотическом смысле (без учета постоянных факторов), для получения почти оптимальной производительности в абсолютном смысле может потребоваться дополнительная настройка для конкретной машины. Цель алгоритмов, не обращающих внимания на кэш, - уменьшить объем такой настройки, которая требуется.

Как правило, алгоритм без учета кеширования работает по рекурсивному алгоритму « разделяй и властвуй» , где проблема делится на меньшие и меньшие подзадачи. В конце концов, каждый достигает размера подзадачи, который умещается в кеш, независимо от размера кеша. Например, оптимальное умножение матриц без учета кеширования получается путем рекурсивного деления каждой матрицы на четыре подматрицы, которые должны быть умножены, умножая подматрицы в глубину . При настройке для конкретной машины можно использовать гибридный алгоритм, который использует блокировку, настроенную для конкретных размеров кеша на нижнем уровне, но в остальном использует алгоритм без учета кеша.

История [ править ]

Идея (и название) алгоритмов, не обращающих внимания на кеш-память, была придумана Чарльзом Э. Лейзерсоном еще в 1996 году и впервые опубликована Харальдом Прокопом в его магистерской диссертации в Массачусетском технологическом институте в 1999 году. ^[1] Обычно было много предшественников. анализ конкретных проблем; они подробно обсуждаются в Frigo et al. 1999. Процитированные ранние примеры включают Singleton 1969 для рекурсивного быстрого преобразования Фурье, аналогичные идеи у Aggarwal et al. 1987 г., Frigo 1996 г. для умножения матриц и LU-разложения и Todd Veldhuizen 1996 г. для матричных алгоритмов в библиотеке Blitz ++ .

Идеализированная модель кеша [ править ]

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

В частности, модель без кеширования - это абстрактная машина (то есть теоретическая модель вычислений ). Это похоже на модель машины RAM, которая заменяет бесконечную ленту машины Тьюринга на бесконечный массив. К каждому месту в массиве можно получить доступ во времени, аналогично оперативной памяти на реальном компьютере. В отличие от модели RAM-машины, здесь также присутствует кэш: второй уровень хранения между RAM и CPU. Другие различия между двумя моделями перечислены ниже. В модели без кеширования: ${\ displaystyle O (1)}$

Кэш слева содержит блоки размером каждый, всего

M

объектов. Объем внешней памяти справа неограничен.

{\ displaystyle {\ tfrac {M} {B}}}

{\ displaystyle B}

Память разбита на блоки объектов каждый. ${\ displaystyle B}$
Загрузка или хранение между основной памятью и регистром ЦП теперь может обслуживаться из кеша.
Если загрузка или хранилище не могут обслуживаться из кеша, это называется промахом кеша .
Промах кэша приводит к загрузке одного блока из основной памяти в кеш. А именно, если ЦП пытается получить доступ к слову и содержит строку , то загружается в кеш. Если кэш был ранее заполнен, строка также будет исключена (см. Политику замены ниже). ${\ displaystyle w}$ ${\ displaystyle x}$ ${\ displaystyle w}$ ${\ displaystyle x}$
Кеш хранит объекты, где . Это также известно как предположение о высоком кэше . ${\ displaystyle M}$ ${\ Displaystyle М = \ Омега (В ^ {2})}$
Кэш полностью ассоциативен: каждую строку можно загрузить в любое место кеша. ^[2]
Политика замены оптимальна. Другими словами, предполагается, что кеш-память получает всю последовательность обращений к памяти во время выполнения алгоритма. Если ему нужно удалить строку во время , он проанализирует свою последовательность будущих запросов и исключит строку, доступ к которой будет осуществляться дальше всего в будущем. Это можно эмулировать на практике с помощью политики наименее недавно использованного , которая, как показано, находится в пределах небольшого постоянного коэффициента автономной оптимальной стратегии замены ^[3]^[4] ${\ displaystyle t}$

Чтобы измерить сложность алгоритма, который выполняется в рамках модели без учета кеша, мы измеряем количество промахов кеша, которые испытывает алгоритм. Поскольку модель учитывает тот факт, что доступ к элементам в кэше происходит намного быстрее, чем доступ к объектам в основной памяти , время работы алгоритма определяется только количеством передач памяти между кешем и основной памятью. Это похоже на модель внешней памяти , которая имеет все вышеперечисленные функции, но алгоритмы без учета кеша не зависят от параметров кеша ( и ). ^[5] ${\ displaystyle B}$ ${\ displaystyle M}$ Преимущество такого алгоритма состоит в том, что то, что эффективно на машине без кеширования, вероятно, будет эффективным на многих реальных машинах без точной настройки конкретных параметров реальной машины. Для многих проблем оптимальный алгоритм без учета кеша также будет оптимальным для машины с более чем двумя уровнями иерархии памяти . ^[3]

Примеры [ править ]

Иллюстрация порядка строк и столбцов

Простейший алгоритм без учета кеширования, представленный Frigo et al. - это операция транспонирования матрицы не на месте ( для транспонирования также были разработаны алгоритмы на месте , но для неквадратных матриц они намного сложнее). Учитывая м × п массива и н × м массив B , мы хотели бы хранить транспонирование $А$ в $В$ . Наивное решение обходит один массив в порядке строк, а другой - в порядке столбцов. В результате, когда матрицы большие, мы получаем пропуск кэша на каждом этапе обхода по столбцам. Общее количество промахов кеша составляет . ${\ Displaystyle \ Theta (мин)}$

Принцип алгоритма без кеширования для транспонирования матриц с использованием подхода «разделяй и властвуй». На графике показан рекурсивный шаг ( a → b ) разделения матрицы и транспонирования каждой части по отдельности.

Алгоритм без кеширования имеет оптимальную сложность работы и оптимальную сложность кеширования . Основная идея состоит в том, чтобы свести транспонирование двух больших матриц к транспонированию малых (под) матриц. Мы делаем это, разделяя матрицы пополам по их большему размеру, пока нам не нужно просто выполнить транспонирование матрицы, которая поместится в кеш. Поскольку размер кэша неизвестен алгоритму, матрицы будут продолжать рекурсивно делиться даже после этого момента, но эти дальнейшие подразделения будут в кэше. Как только размеры $m$ и $n$ становятся достаточно малыми, чтобы входной массив размера и выходной массив размера помещались в кэш, обходы как по строкам, так и по столбцам приводят к ${\ Displaystyle О (мин)}$ ${\ Displaystyle О (1 + мин / В)}$ ${\ Displaystyle м \ раз п}$ ${\ Displaystyle п \ раз м}$ ${\ Displaystyle О (мин)}$ работа и кеш промахов. Используя этот подход «разделяй и властвуй», мы можем достичь того же уровня сложности для всей матрицы. ${\ Displaystyle О (мин / В)}$

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

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

Как и внешняя сортировка в модели внешней памяти , сортировка без учета кеша возможна в двух вариантах: сортировка воронкой , которая напоминает сортировку слиянием , и сортировка распределения без учета кеша , которая напоминает быструю сортировку . Как и их аналоги с внешней памятью, оба достигают времени работы , которое соответствует нижней границе и, таким образом, является асимптотически оптимальным . ^[5] ${\ displaystyle O \ left ({\ tfrac {N} {B}} \ log _ {\ tfrac {M} {B}} {\ tfrac {N} {B}} \ right)}$

См. Также [ править ]

Алгоритм внешней памяти
Funnelsort
Сортировка распределения без учета кэша

Ссылки [ править ]

^ Харальд Прокоп. Алгоритмы, не обращающие внимания на кеш . Магистерская диссертация, Массачусетский технологический институт. 1999 г.
↑ Кумар, Пиюш. «Алгоритмы, не обращающие внимания на кеш». Алгоритмы иерархий памяти . LNCS 2625. Springer Verlag: 193–212. CiteSeerX 10.1.1.150.5426 .
^ a b Frigo, M .; Лейзерсон, CE ; Прокоп, Х .; Рамачандран, С. (1999). Алгоритмы без учета кеширования (PDF) . Proc. IEEE Symp. по основам компьютерных наук (FOCS). С. 285–297.
^ Даниэль Слейтор, Роберт Тарьян. Амортизированная эффективность правил обновления списков и пейджинга . В сообщениях ACM , том 28, номер 2, стр. 202–208. Февраль 1985 г.
^ a b Эрик Демейн . Алгоритмы и структуры данных , не обращающие внимания на кеш, в конспектах лекции Летней школы EEF по массивным наборам данных, БРИКС, Орхусский университет, Дания, 27 июня - 1 июля 2002 г.

[Prokop-1] Харальд Прокоп. Алгоритмы, не обращающие внимания на кеш . Магистерская диссертация, Массачусетский технологический институт. 1999 г.

[Kumar-2] Кумар, Пиюш. «Алгоритмы, не обращающие внимания на кеш». Алгоритмы иерархий памяти . LNCS 2625. Springer Verlag: 193–212. CiteSeerX 10.1.1.150.5426 .

[Frigo99-3] Frigo, M .; Лейзерсон, CE ; Прокоп, Х .; Рамачандран, С. (1999). Алгоритмы без учета кеширования (PDF) . Proc. IEEE Symp. по основам компьютерных наук (FOCS). С. 285–297.

[Sleator-4] Даниэль Слейтор, Роберт Тарьян. Амортизированная эффективность правил обновления списков и пейджинга . В сообщениях ACM , том 28, номер 2, стр. 202–208. Февраль 1985 г.

[Demaine02-5] Эрик Демейн . Алгоритмы и структуры данных , не обращающие внимания на кеш, в конспектах лекции Летней школы EEF по массивным наборам данных, БРИКС, Орхусский университет, Дания, 27 июня - 1 июля 2002 г.

[1]