Введение
Эффективный алгоритм ввода-вывода, не зависящий от размера кэша. В вычислительной технике алгоритм, нечувствительный к кэшу (или алгоритм, превосходящий кэш), — это алгоритм, разработанный для использования кэша процессора без учета размера кэша (или длины кэш-линий и т. д.) в качестве явного параметра. Оптимальный алгоритм, нечувствительный к кэшу, — это алгоритм, нечувствительный к кэшу, который использует кэш оптимально (в асимптотическом смысле, игнорируя постоянные множители). Таким образом, алгоритм, нечувствительный к кэшу, предназначен для эффективной работы без изменений на различных машинах с разными размерами кэша или для иерархии памяти с разными уровнями кэша, имеющими разные размеры. Алгоритмы, нечувствительные к кэшу, противопоставляются явному разбиению циклов на блоки (loop tiling), которое явно разбивает задачу на блоки оптимального размера для заданного кэша. Оптимальные алгоритмы, нечувствительные к кэшу, известны для умножения матриц, транспонирования матриц, сортировки и ряда других задач. Некоторые более общие алгоритмы, такие как Cooley–Tukey FFT, оптимально нечувствительны к кэшу при определенных значениях параметров. Поскольку эти алгоритмы оптимальны только в асимптотическом смысле (игнорируя постоянные множители), для достижения почти оптимальной производительности в абсолютном выражении может потребоваться дополнительная настройка, специфичная для конкретной машины. Цель алгоритмов, нечувствительных к кэшу, — уменьшить объем необходимой настройки. Как правило, алгоритм, нечувствительный к кэшу, работает по рекурсивному принципу "разделяй и властвуй", где задача разбивается на все более мелкие подзадачи. В конечном итоге достигается размер подзадачи, который помещается в кэш, независимо от размера кэша. Например, оптимальное умножение матриц, нечувствительное к кэшу, достигается путем рекурсивного деления каждой матрицы на четыре подматрицы для умножения, умножая подматрицы в порядке глубины. При настройке для конкретной машины можно использовать гибридный алгоритм, который использует разбиение циклов на блоки, настроенное для конкретных размеров кэша на нижнем уровне, но в остальном использует алгоритм, нечувствительный к кэшу.
In computing, a cache oblivious algorithm (or cache transcendent algorithm) is an algorithm designed to take advantage of a processor cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter. An optimal cache oblivious algorithm is a cache oblivious algorithm that uses the cache optimally (in an asymptotic sense, ignoring constant factors). Thus, a cache oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache. Optimal cache oblivious algorithms are known for matrix multiplication, matrix transposition, sorting, and several other problems. Some more general algorithms, such as Cooley–Tukey FFT, are optimally cache oblivious under certain choices of parameters. As these algorithms are only optimal in an asymptotic sense (ignoring constant factors), further machine specific tuning may be required to obtain nearly optimal performance in an absolute sense. The goal of cache oblivious algorithms is to reduce the amount of such tuning that is required. Typically, a cache oblivious algorithm works by a recursive divide and conquer algorithm, where the problem is divided into smaller and smaller subproblems. Eventually, one reaches a subproblem size that fits into the cache, regardless of the cache size. For example, an optimal cache oblivious matrix multiplication is obtained by recursively dividing each matrix into four sub matrices to be multiplied, multiplying the submatrices in a depth first fashion. In tuning for a specific machine, one may use a hybrid algorithm which uses loop tiling tuned for the specific cache sizes at the bottom level but otherwise uses the cache oblivious algorithm.
История
Идея (и название) алгоритмов, нечувствительных к кэшу, была выдвинута Чарльзом Лейзерсоном еще в 1996 году и впервые опубликована Харальдом Прокопом в его магистерской диссертации в Массачусетском технологическом институте в 1999 году. Существовало множество предшествующих работ, как правило, анализирующих конкретные задачи; они подробно рассматриваются в Frigo et al. 1999. К ранним примерам относятся Singleton 1969 года для рекурсивного быстрого преобразования Фурье, схожие идеи в Aggarwal et al. 1987, Frigo 1996 для умножения матриц и LU-разложения, а также Todd Veldhuizen 1996 для матричных алгоритмов в библиотеке Blitz++.