Изменения

''Типичные cache-oblivious алгоритмы'' : перемножение матриц, внешняя сортировка, транспозиция матриц, ну и некоторые другие задачи...

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

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