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

В контексте подхода без явного задания параметров кэша вычислительная модель представляет машину с двумя уровнями памяти: кэш ограниченного объема и дополнительная память бесконечного объема. Предполагается, что объем кэша составляет M элементов, а перенос данных между двумя уровнями памяти осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над элементами, хранящимися в кэше; элементы из дополнительной памяти должны быть перемещены в кэш, прежде чем вычислительный процесс сможет получить к ним доступ. Программы пишутся так, словно они работают с единой памятью неограниченного объема, т.е. являются стандартными RAM-программами. Необходимые переносы содержимого между кэшем и дополнительной памятью выполняются моделью автоматически при помощи оптимальной автономной стратегии замещения кэша. Базовое предположение модели без явного задания параметров кэша заключается в том, что значения M и B неизвестны алгоритму, тогда как в предложенной Аггарвалом и Виттером [1] модели ввода-вывода алгоритм знает эти значения и явно выполняет перенос блоков памяти. Обстоятельное обсуждение модели без явного задания параметров кэша и ее отношения к многоуровневым иерархиям памяти приведено в [8].