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

Помимо концептуально простого отображения иерархии памяти, модель ввода-вывода также имеет и другие преимущества. Алгоритмы, разработанные на основе этой модели, не полагаются на знание параметров иерархии памяти; это может пригодиться, например, при разработке программ, которые будут работать на различных или неизвестных архитектурах (таких как библиотечные программы или программы для гетерогенных распределенных вычислений – например, сетевых коллективных вычислений и проектов наподобие 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].