Модель без явного задания параметров кэша: различия между версиями

Система памяти современного компьютера включает несколько иерархических уровней, каждый из которых выступает в качестве кэша для следующего; типичная иерархия может состоять из регистров, кэша 1 уровня, кэша 2 уровня, кэша 3 уровня, основной памяти и дисковой памяти (рис. 1). Одна из характеристик иерархии заключается в том, что уровни памяти становятся больше и медленнее по мере удаления от процессора; разница в скорости доступа оказывается самой масштабной при переходе от оперативной памяти к дисковой. Еще одно свойство заключается в том, что данные перемещаются между уровнями в виде блоков.

Для более адекватного отражения влияния иерархии памяти было разработано несколько вычислительных моделей. Самая простая и успешная из них – двухуровневая модель ввода-вывода, предложенная Аггарвалом и Виттером [2] (рис. 3). В этой модели используется двухуровневая иерархия памяти, состоящей из быстрой памяти размера M и более медленной памяти неограниченного размера, при этом перенос данных между уровнями осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над данными в быстрой памяти. Предполагается, что алгоритмы полностью контролируют перенос блоков между двумя уровнями. Этот процесс будет называться переносом содержимого памяти. Мерой сложности является количество выполненных переносов содержимого памяти. Преимущество модели ввода-вывода заключается в том, что она частично отражает иерархию памяти и при этом достаточно проста, чтобы на ее основе можно было выполнять разработку и анализ алгоритмов. За последние двадцать лет было получено множество результатов применения модели ввода-вывода, охватывающих большинство областей теории алгоритмов. Довольно полное представление можно получить в обзорах [3, 24, 26, 27].

Были также предложены более замысловатые модели многоуровневой памяти (см. обзор в [ ]), однако они оказались менее успешными – главным образом из-за их сложности, затрудняющей анализ алгоритмов. Все эти модели, включая модель ввода-выводы, предполагают, что характеристики иерархии памяти (уровень и размер блоков) заранее известны.

Модель памяти без явного задания параметров кэша была предложена в 1999 году Фриго и др. [ ]. Алгоритм без явного задания параметров кэша представляет собой алгоритм, формулируемый в рамках RAM-модели, но анализируемый в рамках модели ввода-вывода, причем анализ должен быть действительным при любых значениях размера блока B и размера памяти M. Предполагается, что перенос содержимого памяти выполняется автоматически при помощи оптимальной автономной стратегии замещения кэша.

Главное достоинство модели ввода-вывода заключается в следующем: в силу того, что анализ в рамках модели ввода-вывода действителен при любых значениях размера блока и размера памяти, он оказывается верен для всех уровней иерархии памяти (детальное обоснование этого утверждения см. в [22, 25]). Иначе говоря, если оптимизировать алгоритм на одном, неизвестном, уровне иерархии, он будет одновременно оптимизирован на всех уровнях. Таким образом, модель явного задания параметров кэша изящно обобщает модель ввода-вывода до многоуровневой модели за счет одного простого условия: алгоритму не позволено знать значения B и M. Задача заключается в разработке алгоритмов, демонстрирующих при этих условиях наилучшее значение количество переносов.

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

Что касается сортировки, то фундаментальной особенностью модели ввода-вывода является то, что сортировка N элементов при помощи сравнения требует ® (Sort(N)) переносов содержимого памяти [ ], где Sort(N) = NB logM/B MN. В модели без явного задания параметров кэша сортировка может быть выполнена за @(Sort(JV)) переносов содержимого памяти при условии принятия так называемого «предположения о высоте кэша» M > B1+" [15,22]. Было показано, что выполнение этого предположения обязательно [16], так как оно обеспечивает разницу в эффективности между алгоритмами без явного задания параметров кэша и алгоритмами в модели ввода-вывода (где это предположение не требуется для определения границы сортировки).

При выполнении поиска B-деревья обеспечивают стоимость O(logB N), что является оптимальным в модели ввода-вывода для поиска на базе сравнения. Эта стоимость достижима и в модели без явного задания параметров кэша, что было показано для статического [ ] и для динамического случая [13]. Позднее было предложено несколько вариантов деревьев поиска без явного задания параметров кэша. Кроме того, в [ ] было показано различие между алгоритмами без явного задания параметров кэша и алгоритмами модели ввода-вывода, а именно – что константы в границе O(logB N) доказуемо различаются.

Перестановка в модели ввода-вывода имеет сложность @(min{ Sort(N); Ng) в предположении, что элементы неделимы [2]. Было доказано [ ], что эта асимптотическая сложность не может быть получена в модели без явного задания параметров кэша, так что и в случае этой задачи разделение имеет место.

Была предложена реализация очередей с приоритетами на базе модели без явного задания параметров кэша с O(1/BlogM/B N/M) амортизированных переносов содержимого памяти .

К настоящему времени также разработаны алгоритмы модели без явного задания параметров кэша для задач вычислительной геометрии [1, 6, 7, 8, 10, 15], графовых задач [4, 17, 18, 23], для сканирования динамических множеств [ ], укладки статических деревьев [11], задач поиска на мультимножествах [21], динамического программирования [19], частичной устойчивости [10], матричных операций [22] и быстрого преобразования Фурье [22].