4446
правок
Модель без явного задания параметров кэша: различия между версиями
Перейти к навигации
Перейти к поиску
Модель без явного задания параметров кэша (посмотреть исходный код)
Версия от 12:45, 27 февраля 2017
, 27 февраля 2017→Определение модели
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Разница в скорости доступа между уровнями приводит к тому, что стоимость обращений к памяти в значительной мере зависит от того, на каким самом внутреннем уровне памяти находится нужный элемент. Таким образом, схема обращений к памяти некоторого алгоритма в значительной мере определяет время его выполнения на практике. К сожалению, RAM-модель (рис. 2), традиционно используемая для разработки и анализа алгоритмов, не отражает этого, поскольку предполагает, что все обращения к памяти занимают одинаковое время. | Разница в скорости доступа между уровнями приводит к тому, что стоимость обращений к памяти в значительной мере зависит от того, на каким самом внутреннем уровне памяти находится нужный элемент. Таким образом, схема обращений к памяти некоторого алгоритма в значительной мере определяет время его выполнения на практике. К сожалению, RAM-модель (рис. 2), традиционно используемая для разработки и анализа алгоритмов, не отражает этого, поскольку предполагает, что все обращения к памяти занимают одинаковое время. | ||
[[Файл:COM_01.PNG]] | |||
Рис. 1. Иерархия памяти | Рис. 1. Иерархия памяти | ||
[[Файл:COM_02.png]] | |||
Рис. 2. RAM-модель | Рис. 2. RAM-модель | ||
Для более адекватного отражения влияния иерархии памяти было разработано несколько вычислительных моделей. Самая простая и успешная из них – двухуровневая модель ввода-вывода, предложенная Аггарвалом и Виттером [2] (рис. 3). В этой модели используется двухуровневая иерархия памяти, состоящей из быстрой памяти размера M и более медленной памяти неограниченного размера, при этом перенос данных между уровнями осуществляется блоками по B последовательных элементов. Вычисления могут выполняться только над данными в быстрой памяти. Предполагается, что алгоритмы полностью контролируют перенос блоков между двумя уровнями. Этот процесс будет называться переносом содержимого памяти. Мерой сложности является количество выполненных переносов содержимого памяти. Преимущество модели ввода-вывода заключается в том, что она частично отражает иерархию памяти и при этом достаточно проста, чтобы на ее основе можно было выполнять разработку и анализ алгоритмов. За последние двадцать лет было получено множество результатов применения модели ввода-вывода, охватывающих большинство областей теории алгоритмов. Довольно полное представление можно получить в обзорах [3, 24, 26, 27]. | |||
[[Файл:COM_03.png]] | |||
Рис. 3. Модель ввода-вывода | Рис. 3. Модель ввода-вывода | ||
[[Файл:COM_04.png]] | |||
Рис. 4. Модель без явного задания параметров кэша | Рис. 4. Модель без явного задания параметров кэша | ||