4551
правка
Сортировка без явного задания параметров кэша: различия между версиями
Материал из WEGA
Сортировка без явного задания параметров кэша (посмотреть исходный код)
Версия от 15:38, 11 марта 2017
, 11 марта 2017→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача сортировки множества элементов является одной из наиболее активно изучавшихся вычислительных | Задача сортировки множества элементов является одной из наиболее активно изучавшихся вычислительных проблем. Первое исследование алгоритма сортировки без явного задания параметров кэша было представлено в 1999 году в основополагающей работе Фриго и др. [8], в которой была предложена структура без явного задания параметров кэша для разработки алгоритмов, предназначенных для компьютеров с неизвестными параметрами иерархической памяти. | ||
'''Модель''' | |||
В контексте подхода без явного задания параметров кэша вычислительная модель представляет машину с двумя уровнями памяти: кэш ограниченного объема и дополнительная память бесконечного объема. Предполагается, что объем кэша составляет M элементов, а перенос данных между двумя уровнями памяти осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над элементами, хранящимися в кэше; элементы из дополнительной памяти должны быть перемещены в кэш, прежде чем вычислительный процесс сможет получить к ним доступ. Программы пишутся так, словно они работают с единой памятью неограниченного объема, т.е. являются стандартными RAM-программами. Необходимые переносы содержимого между кэшем и дополнительной памятью выполняются моделью автоматически при помощи оптимальной автономной стратегии замещения кэша. Базовое предположение модели без явного задания параметров кэша заключается в том, что значения M и B неизвестны алгоритму, тогда как в предложенной Аггарвалом и Виттером [1] модели ввода-вывода алгоритм знает эти значения и явно выполняет перенос блоков памяти. Обстоятельное обсуждение модели без явного задания параметров кэша и ее отношения к многоуровневым иерархиям памяти приведено в [8]. | В контексте подхода без явного задания параметров кэша вычислительная модель представляет машину с двумя уровнями памяти: кэш ограниченного объема и дополнительная память бесконечного объема. Предполагается, что объем кэша составляет M элементов, а перенос данных между двумя уровнями памяти осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над элементами, хранящимися в кэше; элементы из дополнительной памяти должны быть перемещены в кэш, прежде чем вычислительный процесс сможет получить к ним доступ. Программы пишутся так, словно они работают с единой памятью неограниченного объема, т.е. являются стандартными RAM-программами. Необходимые переносы содержимого между кэшем и дополнительной памятью выполняются моделью автоматически при помощи оптимальной автономной стратегии замещения кэша. Базовое предположение модели без явного задания параметров кэша заключается в том, что значения M и B неизвестны алгоритму, тогда как в предложенной Аггарвалом и Виттером [1] модели ввода-вывода алгоритм знает эти значения и явно выполняет перенос блоков памяти. Обстоятельное обсуждение модели без явного задания параметров кэша и ее отношения к многоуровневым иерархиям памяти приведено в [8]. | ||
