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

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

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

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

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