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

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

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